CabbageProcsImpl.mesa 
Copyright © 1986 by Xerox Corporation. All rights reversed.
Created by Bryan Preas, June 4, 1986 4:02:08 pm PDT
Louis Monier June 13, 1986 6:36:51 pm PDT
DIRECTORY
Basics,
Cabbage,
CabbagePrivate,
CD,
CDBasics,
CDCells,
CDSimpleRules,
CDSymbolicObjects,
Connections,
Convert,
List,
PW,
PWRoute,
Rope,
Route,
RTBasic,
TerminalIO;
CabbageProcsImpl: CEDAR PROGRAM
IMPORTS Basics, Cabbage, CD, CDBasics, CDCells, CDSimpleRules, CDSymbolicObjects, Connections, Convert, List, PW, PWRoute, Rope, Route, RTBasic, TerminalIO
EXPORTS CabbagePrivate =
BEGIN
Initialization
sideName: ARRAY RTBasic.Side OF Rope.ROPE ← ["bottom", "top", "left", "right"];
CreateHandle: PUBLIC PROC [inner, bottomLeft, bottom, bottomRight, right, topRight, top, topLeft, left: Cabbage.Object, connections: Connections.Table, parms: Cabbage.PadRingParams, name: Rope.ROPE, routeType: CabbagePrivate.RouteType] RETURNS [handle: CabbagePrivate.Handle]~ {
handle ← NEW[CabbagePrivate.HandleRec ← [name: name, connections: connections, parms: parms]];
handle.routeType ← routeType;
handle.rules ← CreateRouterParms[parms];
handle.globalRouting ← NEW[CabbagePrivate.GlobalRoutingRec];
IF routeType = normal THEN
handle.detailedRouting ← NEW[CabbagePrivate.DetailedRoutingRec]
ELSE
handle.detailedRoutingPL ← NEW[CabbagePrivate.DetailedRoutingPLRec];
GetSizes[handle, inner, bottomLeft, bottom, bottomRight, right, topRight, top, topLeft, left];
AssignPositions[handle]};
Define the routing design rules. technologyKey values are predefinded for now. horizLayer, vertLayer should be "poly", "metal" or "metal2".
CreateRouterParms: PROC [parms: Cabbage.PadRingParams] RETURNS [designRules: CabbagePrivate.DesignRules] = {
hLayer: CD.Layer ← CDSimpleRules.GetLayer[parms.technologyKey, parms.horizLayer];
vLayer: CD.Layer ← CDSimpleRules.GetLayer[parms.technologyKey, parms.vertLayer];
designRules ← NEW[CabbagePrivate.DesignRulesRec];
designRules.horizParms.parms ← NEW[PWRoute.RouterParamsRec ← [trunkLayer: parms.horizLayer, branchLayer: parms.vertLayer, technologyKey: parms.technologyKey, wireWidthProc: NIL, signalIncomplete: parms.signalIncomplete, signalBreakAtExit: FALSE, signalSinglePinNets: parms.signalSinglePinNets]];
designRules.vertParms.parms ← NEW[PWRoute.RouterParamsRec ← [trunkLayer: parms.vertLayer, branchLayer: parms.horizLayer, technologyKey: parms.technologyKey, wireWidthProc: NIL, signalIncomplete: parms.signalIncomplete, signalBreakAtExit: FALSE, signalSinglePinNets: parms.signalSinglePinNets]];
designRules.horizParms.rules ← Route.CreateDesignRules[parms.technologyKey, hLayer, vLayer, horizontal];
designRules.vertParms.rules ← Route.CreateDesignRules[parms.technologyKey, hLayer, vLayer, vertical]};
GetSizes: PROC [handle: CabbagePrivate.Handle, inner, bottomLeft, bottom, bottomRight, right, topRight, top, topLeft, left: Cabbage.Object] ~ {
lambda: INT ← handle.rules.horizParms.rules.CDLambda;
handle.inner ← GetObjectDescription[inner, lambda, lambda];
handle.bottom ← GetObjectDescription[bottom, lambda, lambda];
handle.right ← GetObjectDescription[right, lambda, lambda];
handle.top ← GetObjectDescription[top, lambda, lambda];
handle.left ← GetObjectDescription[left, lambda, lambda];
handle.bottomLeft ← GetObjectDescription[bottomLeft, handle.left.size.x, handle.bottom.size.y];
handle.bottomRight ← GetObjectDescription[bottomRight, handle.right.size.x, handle.bottom.size.y];
handle.topRight ← GetObjectDescription[topRight, handle.right.size.x, handle.top.size.y];
handle.topLeft ← GetObjectDescription[topLeft, handle.left.size.x, handle.top.size.y]};
GetObjectDescription: PROC [object: Cabbage.Object, minX, minY: INT] RETURNS [desc: CabbagePrivate.ObjectDescription] ~ {
desc.object ← object;
IF object = NIL THEN desc.size ← [minX, minY]
ELSE {
desc.size ← IRSize[object];
desc.size.x ← MAX[minX, desc.size.x];
desc.size.y ← MAX[minY, desc.size.y]}};
AssignPositions: PROC [handle: CabbagePrivate.Handle] ~ {
hBottom, hTop, vLeft, vRight: INT;
[hBottom, hTop, vLeft, vRight] ← GetSize[handle];
handle.bottom.orgin ← [handle.bottomLeft.size.x + (handle.size.x - hBottom)/2, 0];
handle.right.orgin ← [handle.size.x - handle.right.size.x, handle.bottomRight.size.y + (handle.size.y - vRight)/2];
handle.top.orgin ← [handle.topLeft.size.x + (handle.size.x - hTop)/2, handle.size.y - handle.top.size.y];
handle.left.orgin ← [0, handle.bottomLeft.size.y + (handle.size.y - vLeft)/2];
DoCorners[handle]};
InitWires: PROC [handle: CabbagePrivate.Handle] ~ {
LookForGndAndVdd: Connections.EachNetAction ~ {
IF Rope.Equal[net.name, "Vdd"] THEN handle.vddNet ← net
ELSE IF Rope.Equal[net.name, "Gnd"] THEN handle.gndNet ← net};
EachNet: Connections.EachNetAction ~ {
EachSegment: Connections.EachSegmentAction ~ {
IF UseSegment[handle, segment, net] THEN
newNet.width ← MAX[newNet.width, segment.range.max - segment.range.min]
ELSE TerminalIO.WriteRope[Rope.Cat[Rope.Cat["Segment ignored on net: ", net.name, ", side: ", sideName[RTBasic.OtherSide[segment.side]], ", range: ["], Rope.Cat[Convert.RopeFromInt[segment.range.min], ", ", Convert.RopeFromInt[segment.range.max], "]\n"]]]};
newNet: Connections.Net ← NEW[Connections.NetRec ← [name: net.name, width: net.width]];
IF net.width <= 0 THEN
[] ← Connections.EnumerateSegments[net, EachSegment];
[] ← Connections.Store[handle.widthTable, net.name, newNet]};
handle.widthTable ← Connections.CreateForRopes[];
[] ← Connections.EnumerateNets[handle.connections, LookForGndAndVdd];
[] ← Connections.EnumerateNets[handle.connections, EachNet]};
CheckInnerPos: PUBLIC PROC [handle: CabbagePrivate.Handle, innerPos: CD.Position] ~ {
actualInnerPos: CD.Position ← innerPos;
lowerY: INT ← handle.bottom.orgin.y + handle.bottom.size.y;
upperY: INT ← handle.top.orgin.y - handle.inner.size.y;
lowerX: INT ← handle.left.orgin.x + handle.left.size.x;
upperX: INT ← handle.right.orgin.x - handle.inner.size.x;
IF ~((lowerX <= innerPos.x AND innerPos.x <= upperX) AND (lowerY <= innerPos.y AND innerPos.y <= upperY)) THEN {
Cabbage.Signal[callingError, "The position specified for the inner object (innerPos) is invalid."];
actualInnerPos ← [(lowerX + upperX)/2, (lowerY + lowerY)/2]};
handle.inner.orgin ← actualInnerPos};
Global Routing
GlobalRoute: PUBLIC PROC [handle: CabbagePrivate.Handle] ~ {
EachNet: Connections.EachNetAction ~ {
sortedSegments: CabbagePrivate.SegmentSeq ← SortSegments[handle, net];
IF sortedSegments # NIL THEN {
segmentPair: CabbagePrivate.SegmentPair ← FindStartEndSegments[handle, net, sortedSegments];
AddNetToGlobalRoute[handle, net, segmentPair]}};
IF handle.connections # NIL THEN InitWires[handle];
AdjustPositions[handle];
[] ← Connections.EnumerateNets[handle.connections, EachNet]};
Sort the segments on this net in order arround the periphery
SortSegments: PROC [handle: CabbagePrivate.Handle, net: Connections.Net] RETURNS [sortedSegments: CabbagePrivate.SegmentSeq ← NIL] ~ {
CountSegments: Connections.EachSegmentAction ~ {
IF UseSegment[handle, segment, net] THEN numSegments ← numSegments + 1};
PinCompare: List.CompareProc ~ {
pos1, pos2: INT;
TRUSTED{
pos1 ← PosOf[handle, net, LOOPHOLE[ref1]];
pos2 ← PosOf[handle, net, LOOPHOLE[ref2]]};
RETURN [Basics.CompareINT[pos1, pos2]]};
numSegments, index: INT ← 0;
mungedSegmentList, sortedSegmentList: List.LORA;
[] ← Connections.EnumerateSegments[net, CountSegments];
IF numSegments > 1 THEN {
Use Reverse to get a new copy of the list because Sort is destructive
TRUSTED{mungedSegmentList ← List.Reverse[LOOPHOLE[net.segments]]};
sortedSegmentList ← List.Sort[mungedSegmentList, PinCompare];
sortedSegments ← NEW[CabbagePrivate.SegmentSeqRec[numSegments]];
FOR each: List.LORA ← sortedSegmentList, each.rest UNTIL each = NIL DO
segment: Connections.Segment;
TRUSTED{segment ← LOOPHOLE[each.first]};
IF UseSegment[handle, segment, net] THEN {
sortedSegments[index] ← segment;
index ← index + 1};
ENDLOOP}};
Find the start and end segments of a net arround the periphery
FindStartEndSegments: PROC [handle: CabbagePrivate.Handle, net: Connections.Net, sortedSegments: CabbagePrivate.SegmentSeq] RETURNS [segmentPair: CabbagePrivate.SegmentPair ← [NIL, NIL]] ~ {
minLength: INTLAST[INT];
perimeter: INT ← 2*(handle.size.x + handle.size.y);
length: INT;
startSeg, endSeg: Connections.Segment;
FOR index: NAT IN [0 .. sortedSegments.numSegments) DO
IF index < sortedSegments.numSegments - 1 THEN {
startSeg ← sortedSegments[index+1];
endSeg ← sortedSegments[index];
length ← perimeter - PosOf[handle, net, startSeg] + PosOf[handle, net, endSeg]}
ELSE {
endSeg ← sortedSegments[index];
startSeg ← sortedSegments[0];
length ← PosOf[handle, net, endSeg] - PosOf[handle, net, startSeg]};
IF length < minLength THEN {
minLength ← length;
segmentPair.seg1 ← startSeg;
segmentPair.seg2 ← endSeg}
ENDLOOP;
IF segmentPair.seg1 = NIL OR segmentPair.seg2 = NIL THEN
Cabbage.Error[programmingError, "Not suppose to happen"]};
Add this net to the global route
AddNetToGlobalRoute: PROC [handle: CabbagePrivate.Handle, net: Connections.Net, segmentPair: CabbagePrivate.SegmentPair] ~ {
pos1: INT ← PosOf[handle, net, segmentPair.seg1];
pos2: INT ← PosOf[handle, net, segmentPair.seg2];
IF pos1 < pos2 THEN {
FOR d: CabbagePrivate.Division IN CabbagePrivate.Division DO
IF pos1 < PosOfDivision[handle, d] AND PosOfDivision[handle, d] < pos2 THEN
handle.globalRouting.exitLists[d] ← CONS[net, handle.globalRouting.exitLists[d]]
ENDLOOP}
ELSE {
FOR d: CabbagePrivate.Division IN CabbagePrivate.Division DO
IF PosOfDivision[handle, d] > pos1 OR PosOfDivision[handle, d] < pos2 THEN
handle.globalRouting.exitLists[d] ← CONS[net, handle.globalRouting.exitLists[d]]
ENDLOOP};
};
Detailed Routing
DetailedRoute: PUBLIC PROC [handle: CabbagePrivate.Handle] ~ {
RouteChannels[handle];
AdjustPositions[handle];
IF handle.routeType = normal THEN RouteSwitchBoxes[handle]
ELSE RouteSwitchBoxesPL[handle];
AdjustPositions[handle]};
route all of the channels or just the left and right channels depending on routeType
RouteChannels: PROC [handle: CabbagePrivate.Handle] ~ {
horizParms: CabbagePrivate.ParmSet ← handle.rules.horizParms;
vertParms: CabbagePrivate.ParmSet ← handle.rules.vertParms;
horizRange: Connections.Range ← [handle.inner.orgin.x, handle.inner.orgin.x + handle.inner.size.x];
vertRange: Connections.Range ← [handle.inner.orgin.y, handle.inner.orgin.y + handle.inner.size.y];
IF handle.routeType = normal THEN {
handle.detailedRouting.channels[bottom] ← RouteChannel[handle, handle.bottom, handle.inner, bottom, bottomLeft, bottomRight, horizRange, horizParms];
handle.detailedRouting.channels[right] ← RouteChannel[handle, handle.inner, handle.right, right, rightBottom, rightTop, vertRange, vertParms];
handle.detailedRouting.channels[top] ← RouteChannel[handle, handle.inner, handle.top, top, topLeft, topRight, horizRange, horizParms];
handle.detailedRouting.channels[left] ← RouteChannel[handle, handle.left, handle.inner, left, leftBottom, leftTop, vertRange, vertParms]}
ELSE { -- routeType = padLimited
handle.detailedRoutingPL.channels[right] ← RouteChannel[handle, handle.inner, handle.right, right, rightBottom, rightTop, vertRange, vertParms];
handle.detailedRoutingPL.channels[left] ← RouteChannel[handle, handle.left, handle.inner, left, leftBottom, leftTop, vertRange, vertParms]}};
route one of the channels
RouteChannel: PROC [handle: CabbagePrivate.Handle,
llObject, urObject: CabbagePrivate.ObjectDescription,
side: Route.Side,
llDiv, urDiv: CabbagePrivate.Division, range: Connections.Range,
parms: CabbagePrivate.ParmSet]
RETURNS [channel: CabbagePrivate.Channel] ~ {
result: Route.RoutingResult;
retrieveRect: Route.RefRect;
rect: CD.Rect;
llSide, blSide: Route.Side;
isX: BOOLEAN;
dist, size, offset: INT;
obj1, obj2, bottomOrLeftObj, topOrRightObj: Cabbage.Object;
SELECT side FROM
bottom => {
isX ← FALSE; llSide ← top; blSide ← left};
right => {
isX ← TRUE; llSide ← right; blSide ← bottom};
top => {
isX ← FALSE; llSide ← top; blSide ← left};
left => {
isX ← TRUE; llSide ← right; blSide ← bottom};
ENDCASE;
obj1 ← BuildObject[handle, llObject, llSide, range, parms.rules];
obj2 ← BuildObject[handle, urObject, RTBasic.OtherSide[llSide], range, parms.rules];
bottomOrLeftObj ← BuildEnd[handle, llDiv, blSide, parms.rules];
topOrRightObj ← BuildEnd[handle, urDiv, RTBasic.OtherSide[blSide], parms.rules];
parms.parms.wireWidthProc ← GetWireWidth;
parms.parms.context ← handle.widthTable;
result ← PWRoute.DoRoute[obj1, obj2, bottomOrLeftObj, topOrRightObj, parms.parms, isX, channel];
rect ← result.routingRect;
offset ← result.routingArea.rules.trunkToTrunk;
SELECT side FROM
bottom => {
size ← urObject.orgin.y - (llObject.orgin.y + llObject.size.y);
dist ← MIN[rect.y1, rect.y2 - size + offset];
retrieveRect ← NEW[CD.Rect ← [rect.x1, dist, rect.x2, rect.y2 + offset]]};
right => {
size ← urObject.orgin.x - (llObject.orgin.x + llObject.size.x);
dist ← MAX[rect.x2, size - offset];
retrieveRect ← NEW[CD.Rect ← [rect.x1 - offset, rect.y1, dist, rect.y2]]};
top => {
size ← urObject.orgin.y - (llObject.orgin.y + llObject.size.y);
dist ← MAX[rect.y2, size - offset];
retrieveRect ← NEW[CD.Rect ← [rect.x1, rect.y1 - offset, rect.x2, dist]]};
left => {
size ← urObject.orgin.x - (llObject.orgin.x + llObject.size.x);
dist ← MIN[rect.x1, rect.x2 - size + offset];
retrieveRect ← NEW[CD.Rect ← [dist, rect.y1, rect.x2 + offset, rect.y2]]};
ENDCASE;
channel.object ← PWRoute.GetRouting[result, retrieveRect];
channel.size ← IRSize[channel.object]};
BuildObject: PROC [handle: CabbagePrivate.Handle, objectDes: CabbagePrivate.ObjectDescription, side: Route.Side, range: Connections.Range, rules: Route.DesignRules] RETURNS [shell: Cabbage.Object ← CDCells.CreateEmptyCell[]] ~ {
EachNet: Connections.EachNetAction ~ {
EachSegment: Connections.EachSegmentAction ~ {
IF (segment.object = objectDes.object AND segment.side = side) THEN {
orgin: INT
SELECT side FROM
bottom, top => objectDes.orgin.x,
right, left => objectDes.orgin.y,
ENDCASE => Cabbage.Error[programmingError, "Not suppose to happen."];
adjSeg: Connections.Range ← [orgin + segment.range.min, orgin + segment.range.max];
useThisOne: BOOLEAN ← objectDes.object # handle.inner.object AND UseSegment[handle, segment, net];
IF useThisOne AND CrossesBoundry[adjSeg, range] THEN
Cabbage.Signal[callingError, Rope.Cat["Segment on net: ", net.name, " crosses vertical seam"]];
IF (useThisOne OR objectDes.object = handle.inner.object) AND ProperSubset[adjSeg, range] THEN {
numPins ← numPins + 1;
SELECT side FROM
bottom => IncludePin[object: shell, name: net.name, denotes: [adjSeg.min, oldIR.y1, adjSeg.max, oldIR.y1+rules.trunkWidth], layer: segment.layer];
right => IncludePin[object: shell, name: net.name, denotes: [oldIR.x2-rules.trunkWidth, adjSeg.min, oldIR.x2, adjSeg.max], layer: segment.layer];
top => IncludePin[object: shell, name: net.name, denotes: [adjSeg.min, oldIR.y2-rules.trunkWidth, adjSeg.max, oldIR.y2], layer: segment.layer];
left => IncludePin[object: shell, name: net.name, denotes: [oldIR.x1, adjSeg.min, oldIR.x1+rules.trunkWidth, adjSeg.max], layer: segment.layer];
ENDCASE}}};
[] ← Connections.EnumerateSegments[net, EachSegment]};
numPins: INT ← 0;
oldIR: CD.Rect ← CD.InterestRect[objectDes.object];
interestRect: CD.Rect;
[] ← Connections.EnumerateNets[handle.connections, EachNet];
SELECT side FROM
bottom, top => interestRect ← [range.min, oldIR.y1, range.max, oldIR.y2];
left, right => interestRect ← [oldIR.x1, range.min, oldIR.x2, range.max];
ENDCASE;
CDCells.SetInterestRect[shell, interestRect];
IF numPins > 0 THEN
[] ← CDCells.RepositionCell[shell, NIL];
};
BuildEnd: PROC [handle: CabbagePrivate.Handle, division: CabbagePrivate.Division, side: Route.Side, rules: Route.DesignRules] RETURNS [shell: Cabbage.Object ← CDCells.CreateEmptyCell[]] ~ {
EachExit: EachExitAction ~ {
width: INTMAX[rules.trunkWidth, net.width];
numPins ← numPins + 1;
dist ← dist + rules.trunkWidth;
SELECT side FROM
bottom => IncludePin[object: shell, name: net.name, denotes: [dist, rules.trunkWidth, dist + width, 2*rules.trunkWidth], layer: rules.trunkLayer];
right => IncludePin[object: shell, name: net.name, denotes: [0, dist, rules.trunkWidth, dist + width], layer: rules.trunkLayer];
top => IncludePin[object: shell, name: net.name, denotes: [dist, 0, dist + width, rules.trunkWidth], layer: rules.trunkLayer];
left => IncludePin[object: shell, name: net.name, denotes: [rules.trunkWidth, dist, 2*rules.trunkWidth, dist + width], layer: rules.trunkLayer];
ENDCASE;
dist ← dist + width;
};
numPins: INT ← 0;
dist: INT ← 0;
interestRect: CD.Rect;
[] ← EnumerateExits[handle.globalRouting.exitLists[division], division, EachExit];
SELECT side FROM
bottom, top => interestRect ← [0, 0, dist + rules.trunkWidth, 2*rules.trunkWidth];
left, right => interestRect ← [0, 0, 2*rules.trunkWidth, dist + rules.trunkWidth];
ENDCASE;
CDCells.SetInterestRect[shell, interestRect];
IF numPins > 0 THEN
[] ← CDCells.RepositionCell[shell, NIL];
};
adjust he positions of everything to account for the actual channel widths
AdjustPositions: PROC [handle: CabbagePrivate.Handle] ~ {
adjust for the vertical dimension
routeType: CabbagePrivate.RouteType ← handle.routeType;
sizeBottomArea: INT ← handle.inner.orgin.y - (handle.bottom.orgin.y + handle.bottom.size.y);
sizeBottomRouting: INTIF handle.routeType = normal THEN handle.detailedRouting.channels[bottom].size.y
ELSE handle.detailedRoutingPL.switchBoxes[bottom].size.y;
adjBottom: INT ← sizeBottomRouting - sizeBottomArea;
sizeLeftArea: INT ← handle.inner.orgin.x - (handle.left.orgin.x + handle.left.size.x);
sizeLeftRouting: INTIF handle.routeType = normal THEN handle.detailedRouting.channels[left].size.x
ELSE handle.detailedRoutingPL.channels[left].size.x;
adjLeft: INT ← sizeLeftRouting - sizeLeftArea;
adjTop, adjRight, sizeTopArea, sizeTopRouting, sizeRightArea, sizeRightRouting: INT;
handle.inner.orgin ← CDBasics.AddPoints[handle.inner.orgin, [MAX[0, adjLeft], MAX[0, adjBottom]]];
handle.bottom.orgin ← CDBasics.AddPoints[handle.bottom.orgin, [MAX[0, adjLeft], 0]];
handle.right.orgin ← CDBasics.AddPoints[handle.right.orgin, [MAX[0, adjLeft], MAX[0, adjBottom]]];
handle.top.orgin ← CDBasics.AddPoints[handle.top.orgin, [MAX[0, adjLeft], MAX[0, adjBottom]]];
handle.left.orgin ← CDBasics.AddPoints[handle.left.orgin, [0, MAX[0, adjBottom]]];
sizeTopArea ← handle.top.orgin.y - (handle.inner.orgin.y + handle.inner.size.y);
sizeTopRouting ← IF handle.routeType = normal THEN handle.detailedRouting.channels[top].size.y
ELSE handle.detailedRoutingPL.switchBoxes[top].size.y;
adjTop ← sizeTopRouting - sizeTopArea;
sizeRightArea ← handle.right.orgin.x - (handle.inner.orgin.x + handle.inner.size.x);
sizeRightRouting ← IF handle.routeType = normal THEN handle.detailedRouting.channels[right].size.x
ELSE handle.detailedRoutingPL.channels[right].size.x;
adjRight ← sizeRightRouting - sizeRightArea;
handle.top.orgin ← CDBasics.AddPoints[handle.top.orgin, [0, MAX[0, adjTop]]];
handle.right.orgin ← CDBasics.AddPoints[handle.right.orgin, [MAX[0, adjRight], 0]];
[] ← GetSize[handle];
DoCorners[handle];
IF handle.routeType = normal THEN {
handle.detailedRouting.channels[bottom].orgin ← [handle.inner.orgin.x, handle.inner.orgin.y - handle.detailedRouting.channels[bottom].size.y];
handle.detailedRouting.channels[right].orgin ← [handle.inner.orgin.x + handle.inner.size.x, handle.inner.orgin.y];
handle.detailedRouting.channels[top].orgin ← [handle.inner.orgin.x, handle.inner.orgin.y + handle.inner.size.y];
handle.detailedRouting.channels[left].orgin ← [handle.inner.orgin.x - handle.detailedRouting.channels[left].size.x, handle.inner.orgin.y];
handle.detailedRouting.switchBoxes[bottomLeft].orgin ← [handle.left.orgin.x + handle.left.size.x, handle.bottom.orgin.y + handle.bottom.size.y];
handle.detailedRouting.switchBoxes[bottomRight].orgin ← [handle.inner.orgin.x + handle.inner.size.x, handle.bottom.orgin.y + handle.bottom.size.y];
handle.detailedRouting.switchBoxes[topRight].orgin ← [handle.inner.orgin.x + handle.inner.size.x, handle.inner.orgin.y + handle.inner.size.y];
handle.detailedRouting.switchBoxes[topLeft].orgin ← [handle.left.orgin.x + handle.left.size.x, handle.inner.orgin.y + handle.inner.size.y]}
ELSE { -- routeType = padLimited
handle.detailedRoutingPL.channels[right].orgin ← [handle.inner.orgin.x + handle.inner.size.x, handle.inner.orgin.y];
handle.detailedRoutingPL.channels[left].orgin ← [handle.inner.orgin.x - handle.detailedRoutingPL.channels[left].size.x, handle.inner.orgin.y];
handle.detailedRoutingPL.switchBoxes[bottom].orgin ← [handle.left.orgin.x + handle.left.size.x, handle.bottom.orgin.y + handle.bottom.size.y];
handle.detailedRoutingPL.switchBoxes[top].orgin ← [handle.left.orgin.x + handle.left.size.x, handle.inner.orgin.y + handle.inner.size.y]};
};
route all of the switchBoxes (the corners)
RouteSwitchBoxes: PROC [handle: CabbagePrivate.Handle] ~ {
horizParms: CabbagePrivate.ParmSet ← handle.rules.horizParms;
leftHorizRange: Connections.Range ← [handle.left.orgin.x + handle.left.size.x, handle.inner.orgin.x];
rightHorizRange: Connections.Range ← [handle.inner.orgin.x + handle.inner.size.x, handle.right.orgin.x];
bottomVertRange: Connections.Range ← [handle.bottom.orgin.y + handle.bottom.size.y, handle.inner.orgin.y];
topVertRange: Connections.Range ← [handle.inner.orgin.y + handle.inner.size.y, handle.top.orgin.y];
horizParms.parms.okToDiddleLLPins ← TRUE; horizParms.parms.okToDiddleURPins ← FALSE;
handle.detailedRouting.switchBoxes[bottomLeft] ← RouteSwitchBox[handle, bottomLeft, leftHorizRange, bottomVertRange, horizParms];
horizParms.parms.okToDiddleLLPins ← FALSE; horizParms.parms.okToDiddleURPins ← TRUE;
handle.detailedRouting.switchBoxes[bottomRight] ← RouteSwitchBox[handle, bottomRight, rightHorizRange, bottomVertRange, horizParms];
horizParms.parms.okToDiddleLLPins ← FALSE; horizParms.parms.okToDiddleURPins ← TRUE;
handle.detailedRouting.switchBoxes[topRight] ← RouteSwitchBox[handle, topRight, rightHorizRange, topVertRange, horizParms];
horizParms.parms.okToDiddleLLPins ← TRUE; horizParms.parms.okToDiddleURPins ← FALSE;
handle.detailedRouting.switchBoxes[topLeft] ← RouteSwitchBox[handle, topLeft, leftHorizRange, topVertRange, horizParms];
horizParms.parms.okToDiddleLLPins ← FALSE; horizParms.parms.okToDiddleURPins ← FALSE};
route the bottom and top switchBoxes
RouteSwitchBoxesPL: PROC [handle: CabbagePrivate.Handle] ~ {
horizParms: CabbagePrivate.ParmSet ← handle.rules.horizParms;
horizRange: Connections.Range ← [handle.left.orgin.x + handle.left.size.x, handle.right.orgin.x];
bottomVertRange: Connections.Range ← [handle.bottom.orgin.y + handle.bottom.size.y, handle.inner.orgin.y];
topVertRange: Connections.Range ← [handle.inner.orgin.y + handle.inner.size.y, handle.top.orgin.y];
horizParms.parms.okToDiddleLLPins ← TRUE; horizParms.parms.okToDiddleURPins ← TRUE;
handle.detailedRoutingPL.switchBoxes[bottom] ← RouteSwitchBoxPL[handle, bottom, horizRange, bottomVertRange, horizParms];
handle.detailedRoutingPL.switchBoxes[top] ← RouteSwitchBoxPL[handle, top, horizRange, topVertRange, horizParms];
horizParms.parms.okToDiddleLLPins ← FALSE; horizParms.parms.okToDiddleURPins ← FALSE};
GetWireWidth: PWRoute.WireWidthProc ~ {
PROC [netName: ROPE, context: REF ANY] RETURNS [wireWidth: INT]
table: Connections.Table ← NARROW[context];
net: Connections.Net ← Connections.Fetch[table, netName].net;
wireWidth ← net.width};
RouteSwitchBoxPL: PROC [handle: CabbagePrivate.Handle, side: RTBasic.TBSide, horizRange, vertRange: Connections.Range, parms: CabbagePrivate.ParmSet] RETURNS [switchBox: CabbagePrivate.SwitchBox] ~ {
bottomObject, topObject: Cabbage.Object;
leftObject: Cabbage.Object ← BuildObject[handle, handle.left, right, vertRange, parms.rules];
rightObject: Cabbage.Object ← BuildObject[handle, handle.right, left, vertRange, parms.rules];
innerRange: Connections.Range ← [handle.inner.orgin.x, handle.inner.orgin.x + handle.inner.size.x];
SELECT side FROM
bottom => {
innerObject: Cabbage.Object ← BuildObject[handle, handle.inner, bottom, innerRange, parms.rules];
bottomObject ← BuildObject[handle, handle.bottom, top, horizRange, parms.rules];
topObject ← PW.AbutListX[LIST[handle.detailedRoutingPL.channels[left].object, innerObject, handle.detailedRoutingPL.channels[right].object]]};
top => {
innerObject: Cabbage.Object ← BuildObject[handle, handle.inner, top, innerRange, parms.rules];
bottomObject ← PW.AbutListX[LIST[handle.detailedRoutingPL.channels[left].object, innerObject, handle.detailedRoutingPL.channels[right].object]];
topObject ← BuildObject[handle, handle.top, bottom, horizRange, parms.rules]};
ENDCASE;
parms.parms.wireWidthProc ← GetWireWidth;
parms.parms.context ← handle.widthTable;
switchBox.object ← PWRoute.MakeChannel[bottomObject, topObject, leftObject, rightObject, NIL, parms.parms, FALSE, switchBox];
switchBox.size ← IRSize[switchBox.object]};
RouteSwitchBox: PROC [handle: CabbagePrivate.Handle, corner: CabbagePrivate.Corners, horizRange, vertRange: Connections.Range, parms: CabbagePrivate.ParmSet] RETURNS [switchBox: CabbagePrivate.SwitchBox] ~ {
bottomObject, topObject, leftObject, rightObject: Cabbage.Object;
SELECT corner FROM
bottomLeft => {
bottomObject ← BuildObject[handle, handle.bottom, top, horizRange, parms.rules];
topObject ← handle.detailedRouting.channels[left].object;
leftObject ← BuildObject[handle, handle.left, right, vertRange, parms.rules];
rightObject ← handle.detailedRouting.channels[bottom].object};
bottomRight => {
bottomObject ← BuildObject[handle, handle.bottom, top, horizRange, parms.rules];
topObject ← handle.detailedRouting.channels[right].object;
rightObject ← BuildObject[handle, handle.right, left, vertRange, parms.rules];
leftObject ← handle.detailedRouting.channels[bottom].object};
topRight => {
bottomObject ← handle.detailedRouting.channels[right].object;
topObject ← BuildObject[handle, handle.top, bottom, horizRange, parms.rules];
rightObject ← BuildObject[handle, handle.right, left, vertRange, parms.rules];
leftObject ← handle.detailedRouting.channels[top].object};
topLeft => {
topObject ← BuildObject[handle, handle.top, bottom, horizRange, parms.rules];
bottomObject ← handle.detailedRouting.channels[left].object;
leftObject ← BuildObject[handle, handle.left, right, vertRange, parms.rules];
rightObject ← handle.detailedRouting.channels[top].object};
ENDCASE;
parms.parms.wireWidthProc ← GetWireWidth;
parms.parms.context ← handle.widthTable;
switchBox.object ← PWRoute.MakeChannel[bottomObject, topObject, leftObject, rightObject, NIL, parms.parms, FALSE, switchBox];
switchBox.size ← IRSize[switchBox.object];
};
Object Generation
MakeChip: PUBLIC PROC [handle: CabbagePrivate.Handle] RETURNS [chip: Cabbage.Object] ~ {
chip ← CDCells.CreateEmptyCell[];
IncludeObject[handle.inner.object, handle.inner.orgin, chip];
IncludeObject[handle.bottomLeft.object, handle.bottomLeft.orgin, chip];
IncludeObject[handle.bottom.object, handle.bottom.orgin, chip];
IncludeObject[handle.bottomRight.object, handle.bottomRight.orgin, chip];
IncludeObject[handle.right.object, handle.right.orgin, chip];
IncludeObject[handle.topRight.object, handle.topRight.orgin, chip];
IncludeObject[handle.top.object, handle.top.orgin, chip];
IncludeObject[handle.topLeft.object, handle.topLeft.orgin, chip];
IncludeObject[handle.left.object, handle.left.orgin, chip];
IF handle.routeType = normal THEN {
IncludeObject[handle.detailedRouting.channels[bottom].object, handle.detailedRouting.channels[bottom].orgin, chip];
IncludeObject[handle.detailedRouting.channels[right].object, handle.detailedRouting.channels[right].orgin, chip];
IncludeObject[handle.detailedRouting.channels[top].object, handle.detailedRouting.channels[top].orgin, chip];
IncludeObject[handle.detailedRouting.channels[left].object, handle.detailedRouting.channels[left].orgin, chip];
IncludeObject[handle.detailedRouting.switchBoxes[bottomLeft].object, handle.detailedRouting.switchBoxes[bottomLeft].orgin, chip];
IncludeObject[handle.detailedRouting.switchBoxes[bottomRight].object, handle.detailedRouting.switchBoxes[bottomRight].orgin, chip];
IncludeObject[handle.detailedRouting.switchBoxes[topRight].object, handle.detailedRouting.switchBoxes[topRight].orgin, chip];
IncludeObject[handle.detailedRouting.switchBoxes[topLeft].object, handle.detailedRouting.switchBoxes[topLeft].orgin, chip]}
ELSE {
IncludeObject[handle.detailedRoutingPL.channels[right].object, handle.detailedRoutingPL.channels[right].orgin, chip];
IncludeObject[handle.detailedRoutingPL.channels[left].object, handle.detailedRoutingPL.channels[left].orgin, chip];
IncludeObject[handle.detailedRoutingPL.switchBoxes[bottom].object, handle.detailedRoutingPL.switchBoxes[bottom].orgin, chip];
IncludeObject[handle.detailedRoutingPL.switchBoxes[top].object, handle.detailedRoutingPL.switchBoxes[top].orgin, chip]};
[] ← CDCells.RepositionCell[chip, NIL];
};
IncludeObject: PROC [object: Cabbage.Object, orgin: CD.Position, chip: Cabbage.Object] ~ {
IF object # NIL THEN
[] ← CDCells.IncludeOb[design: NIL, cell: chip, ob: object, position: orgin, orientation: CD.original, cellCSystem: interrestCoords, obCSystem: interrestCoords, mode: dontPropagate]};
Utility Procedures
Find the position of a segment projected to the periphery. The lower left corner is the orgin.
PosOf: PROC [handle: CabbagePrivate.Handle, net: Connections.Net, segment: Connections.Segment] RETURNS [INT] ~ {
RETURN[MiddleOfRange[RangeOf[handle, net, segment]]]};
Find the range of a segment projected to the periphery. The lower left corner is the orgin.
RangeOf: PROC [handle: CabbagePrivate.Handle, net: Connections.Net, segment: Connections.Segment] RETURNS [range: Connections.Range] ~ {
SELECT TRUE FROM
segment.object = handle.inner.object => range ← InnerRange[handle, net, segment];
segment.object = handle.bottom.object => range ← OuterRange[handle, net, segment, bottom];
segment.object = handle.right.object => range ← OuterRange[handle, net, segment, right];
segment.object = handle.top.object => range ← OuterRange[handle, net, segment, top];
segment.object = handle.left.object => range ← OuterRange[handle, net, segment, left];
ENDCASE => Cabbage.Signal[callingError, Rope.Cat["Invalid object in net: ", net.name]]};
Given a segment, compute the middle of the connection point
MiddleOfRange: PROC [range: Connections.Range] RETURNS [INT] ~ {
RETURN[(range.min+range.max)/2]};
InnerRange: PROC [handle: CabbagePrivate.Handle, net: Connections.Net, segment: Connections.Segment] RETURNS [range: Connections.Range] ~ {
orgin: INT;
SELECT segment.side FROM
bottom =>
{orgin ← handle.inner.orgin.x;
range ← [orgin + segment.range.min, orgin + segment.range.max]};
right =>
{orgin ← handle.size.x + handle.inner.orgin.y;
range ← [orgin + segment.range.min, orgin + segment.range.max]};
top =>
{orgin ← handle.size.x +handle.size.y + (handle.size.x - handle.inner.orgin.x);
range ← [orgin - segment.range.max, orgin - segment.range.min]};
left =>
{orgin ← 2*handle.size.x +handle.size.y + (handle.size.y - handle.inner.orgin.y);
range ← [orgin - segment.range.max, orgin - segment.range.min]};
ENDCASE};
OuterRange: PROC [handle: CabbagePrivate.Handle, net: Connections.Net, segment: Connections.Segment, side: Route.Side] RETURNS [range: Connections.Range] ~ {
orgin: INT;
IF segment.side # RTBasic.OtherSide[side] THEN Cabbage.Signal[callingError, Rope.Cat["Invalid side in net: ", net.name]];
SELECT side FROM
bottom =>
{orgin ← handle.bottom.orgin.x;
range ← [orgin + segment.range.min, orgin + segment.range.max]};
right =>
{orgin ← handle.size.x + handle.right.orgin.y;
range ← [orgin + segment.range.min, orgin + segment.range.max]};
top =>
{orgin ← handle.size.x +handle.size.y + (handle.size.x - handle.top.orgin.x);
range ← [orgin - segment.range.max, orgin - segment.range.min]};
left =>
{orgin ← 2*handle.size.x +handle.size.y + (handle.size.y - handle.left.orgin.y);
range ← [orgin - segment.range.max, orgin - segment.range.min]};
ENDCASE};
PosOfDivision: PROC [handle: CabbagePrivate.Handle, division: CabbagePrivate.Division] RETURNS [pos: INT] ~ {
SELECT division FROM
bottomLeft => pos ← handle.inner.orgin.x;
bottomRight => pos ← handle.inner.orgin.x + handle.inner.size.x;
rightBottom => pos ← handle.size.x + handle.inner.orgin.y;
rightTop => pos ← handle.size.x + handle.inner.orgin.y + handle.inner.size.y;
topRight => pos ← handle.size.x +handle.size.y + (handle.size.x - handle.inner.orgin.x - handle.inner.size.x);
topLeft => pos ← handle.size.x +handle.size.y + (handle.size.x - handle.inner.orgin.x);
leftTop => pos ← 2*handle.size.x +handle.size.y + (handle.size.y - handle.inner.orgin.y - handle.inner.size.y);
leftBottom => pos ← 2*handle.size.x +handle.size.y + (handle.size.y - handle.inner.orgin.y);
ENDCASE;
};
IRSize: PROC [obj: Cabbage.Object] RETURNS [size: CD.Position] =
{size ← CDBasics.SizeOfRect[CD.InterestRect[obj]]};
EachExitAction: TYPE = PROC [division: CabbagePrivate.Division, net: Connections.Net] RETURNS [quit: BOOLEANFALSE];
EnumerateExits: PROC [exitList: CabbagePrivate.ExitList, division: CabbagePrivate.Division, eachExitAction: EachExitAction] RETURNS [quit: BOOLEANFALSE] ~ {
FOR list: CabbagePrivate.ExitList ← exitList, list.rest WHILE ~quit AND list # NIL DO
exit: Connections.Net ← list.first;
quit ← eachExitAction[division, exit];
ENDLOOP};
returns TRUE if either end but not both ends of r1 is within r2
CrossesBoundry: PROC [r1, r2: Connections.Range] RETURNS [crosses: BOOLEAN] ~ {
crosses ←(r1.min <= r2.min AND r2.min <= r1.max) OR
(r1.min <= r2.max AND r2.max <= r1.max);
};
returns TRUE if r1 is within r2
ProperSubset: PROC [r1, r2: Connections.Range] RETURNS [subset: BOOLEAN] ~ {
subset ←((r2.min <= r1.min AND r1.min <= r2.max) AND
(r2.min <= r1.max AND r1.max <= r2.max));
};
GetSize: PROC [handle: CabbagePrivate.Handle] RETURNS [hBottom, hTop, vLeft, vRight: INT] ~ {
vMiddle, hMiddle: INT;
IF handle.routeType = normal THEN {
vMiddle ← handle.bottom.size.y + handle.detailedRouting.channels[bottom].size.y + handle.inner.size.y + handle.detailedRouting.channels[top].size.y + handle.top.size.y;
hMiddle ← handle.left.size.x + handle.detailedRouting.channels[left].size.x + handle.inner.size.x + handle.detailedRouting.channels[right].size.x + handle.right.size.x}
ELSE {
hCenter: INT ← handle.detailedRoutingPL.channels[left].size.x + handle.inner.size.x + handle.detailedRoutingPL.channels[right].size.x;
hInner: INTMAX[hCenter, handle.detailedRoutingPL.switchBoxes[top].size.x, handle.detailedRoutingPL.switchBoxes[bottom].size.x];
vMiddle ← handle.bottom.size.y + handle.detailedRoutingPL.switchBoxes[bottom].size.y + handle.inner.size.y + handle.detailedRoutingPL.switchBoxes[top].size.y + handle.top.size.y;
hMiddle ← handle.left.size.x + hInner + handle.right.size.x};
vLeft ← handle.bottomLeft.size.y + handle.left.size.y + handle.topLeft.size.y;
vRight ← handle.bottomRight.size.y + handle.right.size.y + handle.topRight.size.y;
hBottom ← handle.bottomLeft.size.x + handle.bottom.size.x + handle.bottomRight.size.x;
hTop ← handle.topLeft.size.x + handle.top.size.x + handle.topRight.size.x;
handle.size.y ← MAX[vLeft, vMiddle, vRight];
handle.size.x ← MAX[hBottom, hMiddle, hTop];
};
DoCorners: PROC [handle: CabbagePrivate.Handle] ~ {
handle.bottomLeft.orgin ← [0, 0];
handle.bottomRight.orgin ← [handle.size.x - handle.bottomRight.size.x, 0];
handle.topRight.orgin ← [handle.size.x - handle.topRight.size.x, handle.size.y - handle.topRight.size.y];
handle.topLeft.orgin ← [0, handle.size.y - handle.topLeft.size.y]};
IncludePin: PROC [object: CD.Object, name: Rope.ROPE, denotes: CD.Rect, layer: CD.Layer] ~ {
pin: CD.Object ← CDSymbolicObjects.CreatePin[CDBasics.SizeOfRect[denotes]];
pinInstance: CD.Instance ← CDCells.IncludeOb[design: NIL, cell: object, ob: pin, position: CDBasics.BaseOfRect[denotes], orientation: CD.original, cellCSystem: interrestCoords, obCSystem: interrestCoords, mode: dontPropagate].newInst;
CDSymbolicObjects.SetName[pinInstance, name];
CDSymbolicObjects.SetLayer[pinInstance, layer];
};
UseSegment: PROC [handle: CabbagePrivate.Handle, segment: Connections.Segment, net: Connections.Net] RETURNS [useIt: BOOLEANTRUE] ~ {
IF net = handle.vddNet AND
segment.object # handle.inner.object AND SegsOverlap[handle, segment, net, handle.gndNet]
THEN useIt ← FALSE
ELSE IF net = handle.gndNet AND
segment.object # handle.inner.object AND SegsOverlap[handle, segment, net, handle.vddNet]
THEN useIt ← FALSE};
SegsOverlap: PROC [handle: CabbagePrivate.Handle, testSegment: Connections.Segment, testNet, net: Connections.Net] RETURNS [overlaps: BOOLEAN] ~ {
EachSegment: Connections.EachSegmentAction ~ {
IF Overlaps[expandedRange, RangeOf[handle, net, segment]] THEN quit ← TRUE};
testRange: Connections.Range ← RangeOf[handle, testNet, testSegment];
spacing: INT ← IF testSegment.side = top OR testSegment.side = bottom THEN
handle.rules.vertParms.rules.branchToBranch
ELSE handle.rules.horizParms.rules.branchToBranch;
expandedRange: Connections.Range ← [testRange.min - spacing, testRange.max + spacing];
overlaps ← Connections.EnumerateSegments[net, EachSegment]};
Overlaps: PUBLIC PROC [r1, r2: Connections.Range] RETURNS [BOOL] = {
RETURN [(r1.min<=r2.max) AND (r2.min<=r1.max)];
};
END.