Initialization
cabbageXPos: ATOM ← $CabbageXPos;
cabbageYPos: ATOM ← $CabbageYPos;
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.powerDistribution ← NEW[CabbagePrivate.PowerDistributionRec];
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];
IF handle.connections # NIL THEN InitWires[handle];
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];
viaTable: HashTable.Table ← IF parms.viaTable # NIL THEN parms.viaTable ELSE HashTable.Create[equal: EqualProc, hash: HashProc];
designRules ← NEW[CabbagePrivate.DesignRulesRec];
designRules.horizParms.parms ← NEW[PWRoute.RouterParamsRec ← [trunkLayer: parms.horizLayer, branchLayer: parms.vertLayer, technologyKey: parms.technologyKey, wireWidthProc: parms.wireWidthProc, signalIncomplete: parms.signalIncomplete, signalBreakAtExit: FALSE, signalSinglePinNets: parms.signalSinglePinNets, viaTable: viaTable]];
designRules.vertParms.parms ← NEW[PWRoute.RouterParamsRec ← [trunkLayer: parms.vertLayer, branchLayer: parms.horizLayer, technologyKey: parms.technologyKey, wireWidthProc: parms.wireWidthProc, signalIncomplete: parms.signalIncomplete, signalBreakAtExit: FALSE, signalSinglePinNets: parms.signalSinglePinNets, viaTable: viaTable]];
designRules.horizParms.rules ← Route.CreateDesignRules[parms.technologyKey, hLayer, vLayer, horizontal];
designRules.vertParms.rules ← Route.CreateDesignRules[parms.technologyKey, hLayer, vLayer, vertical];
put in wider spacings at sides of channels
designRules.horizParms.rules.trunkToEdge ← designRules.horizParms.rules.trunkToTrunk;
designRules.vertParms.rules.trunkToEdge ← designRules.vertParms.rules.trunkToTrunk};
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 ← RTBasic.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.origin ← [handle.bottomLeft.size.x + (handle.size.x - hBottom)/2, 0];
handle.right.origin ← [handle.size.x - handle.right.size.x, handle.bottomRight.size.y + (handle.size.y - vRight)/2];
handle.top.origin ← [handle.topLeft.size.x + (handle.size.x - hTop)/2, handle.size.y - handle.top.size.y];
handle.left.origin ← [0, handle.bottomLeft.size.y + (handle.size.y - vLeft)/2];
DoCorners[handle];
DoRoutingAreas[handle]};
InitWires:
PROC [handle: CabbagePrivate.Handle] ~ {
LookForGndAndVdd: Connections.EachNetAction ~ {
PROC [key: Key, net: Net] RETURNS [quit: BOOLEAN ← FALSE]
IF Rope.Equal[net.name, "Vdd"] THEN handle.vddNet ← net
ELSE IF Rope.Equal[net.name, "Gnd"] THEN handle.gndNet ← net};
EachNet: Connections.EachNetAction ~ {
PROC [key: Key, net: Net] RETURNS [quit: BOOLEAN ← FALSE]
EachSegment: Connections.EachSegmentAction ~ {
PROC [net: Net, segment: Segment] RETURNS [quit: BOOLEAN ← FALSE]
newNet.width ← MAX[newNet.width, segment.range.max - segment.range.min]};
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.origin.y + handle.bottom.size.y;
upperY: INT ← handle.top.origin.y - handle.inner.size.y;
lowerX: INT ← handle.left.origin.x + handle.left.size.x;
upperX: INT ← handle.right.origin.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.origin ← actualInnerPos};
Power Distribution
DistributePower:
PUBLIC
PROC [handle: CabbagePrivate.Handle] ~ {
make the power distribution channels
horizParms: CabbagePrivate.ParmSet ← handle.rules.horizParms;
vertParms: CabbagePrivate.ParmSet ← handle.rules.vertParms;
space: INT ← 2*horizParms.rules.trunkToTrunk + horizParms.rules.trunkSpacing + vertParms.rules.contactSize + vertParms.rules.trunkSpacing + 2*vertParms.rules.trunkToTrunk;
trunkWidth: INT ← (handle.parms.powerCellWidth - space)/2;
RouteOutsideChannels[handle, trunkWidth];
AssignPositions[handle];
ConstructPowerChannels[handle, trunkWidth];
AssignPositions[handle];
RouteOutsideSwitchBoxes[handle]};
RouteOutsideChannels:
PROC [handle: CabbagePrivate.Handle, viaSize:
INT] ~ {
route the outside channels; move signal pins on the outer from the shadow of the power pins on the inner.
horizParms and vertParms specify the routing for the specified direction; horizRange and vertRange describe the projection of the inner onto the pad ring
outerChanWidth: INT ← handle.parms.outerChanWidth;
powerWidth: INT ← outerChanWidth + handle.parms.powerCellWidth;
horizParms: CabbagePrivate.ParmSet ← handle.rules.horizParms;
vertParms: CabbagePrivate.ParmSet ← handle.rules.vertParms;
horizInnerRange: Connections.Range ← [handle.inner.origin.x, handle.inner.origin.x + handle.inner.size.x];
horizOuterRange: Connections.Range ← [handle.left.origin.x + handle.left.size.x + powerWidth, handle.right.origin.x - powerWidth];
vertInnerRange: Connections.Range ← [handle.inner.origin.y, handle.inner.origin.y + handle.inner.size.y];
vertOuterRange: Connections.Range ← [handle.bottom.origin.y + handle.bottom.size.y + powerWidth, handle.top.origin.y - powerWidth];
route the outside channels
handle.powerDistribution.channels[bottom] ← RouteOutsideChannel[handle, handle.bottom, bottom, horizOuterRange, horizOuterRange, outerChanWidth, viaSize, vertParms];
handle.powerDistribution.channels[right] ← RouteOutsideChannel[handle, handle.right, right, vertInnerRange, vertOuterRange, outerChanWidth, viaSize, horizParms];
handle.powerDistribution.channels[top] ← RouteOutsideChannel[handle, handle.top, top, horizOuterRange, horizOuterRange, outerChanWidth, viaSize, vertParms];
handle.powerDistribution.channels[left] ← RouteOutsideChannel[handle, handle.left, left, vertInnerRange, vertOuterRange, outerChanWidth, viaSize, horizParms]};
ConstructPowerChannels:
PROC [handle: CabbagePrivate.Handle, trunkWidth:
INT] ~ {
construct the power routing channels; route signal pins on the outer straight accross with vias as necessary.
horizParms and vertParms specify the routing for the specified direction; horizRange and vertRange describe the projection of the inner onto the pad ring
powerCellWidth: INT ← handle.parms.powerCellWidth;
powerWidth: INT ← handle.parms.outerChanWidth + powerCellWidth;
horizParms: CabbagePrivate.ParmSet ← handle.rules.horizParms;
vertParms: CabbagePrivate.ParmSet ← handle.rules.vertParms;
horizInnerRange: Connections.Range ← [handle.inner.origin.x, handle.inner.origin.x + handle.inner.size.x];
horizOuterRange: Connections.Range ← [handle.left.origin.x + handle.left.size.x + powerWidth, handle.right.origin.x - powerWidth];
vertInnerRange: Connections.Range ← [handle.inner.origin.y, handle.inner.origin.y + handle.inner.size.y];
vertOuterRange: Connections.Range ← [handle.bottom.origin.y + handle.bottom.size.y + powerWidth, handle.top.origin.y - powerWidth];
construct the power distribution cells
handle.powerDistribution.power[bottom] ← RoutePower[handle, handle.powerDistribution.channels[bottom], bottom, horizOuterRange, powerCellWidth, trunkWidth, horizParms, vertParms];
handle.powerDistribution.power[right] ← RoutePower[handle, handle.powerDistribution.channels[right], right, vertOuterRange, powerCellWidth, trunkWidth, vertParms, horizParms];
handle.powerDistribution.power[top] ← RoutePower[handle, handle.powerDistribution.channels[top], top, horizOuterRange, powerCellWidth, trunkWidth, horizParms, vertParms];
handle.powerDistribution.power[left] ← RoutePower[handle, handle.powerDistribution.channels[left], left, vertOuterRange, powerCellWidth, trunkWidth, vertParms, horizParms]};
route one of the outside channels
RouteOutsideChannel:
PROC [handle: CabbagePrivate.Handle,
outerObject: CabbagePrivate.ObjectDescription, -- outer Cabbage object
side: Route.Side, -- the side of chip for which this channel is being constructed
innerRange, outerRange: Connections.Range, -- innerRange is the span of the inner cell, outerRange the span of the appropriate power routing cell; innerRange may equal outerRange
chWidth: INT, -- the only permitted width for channel
viaSize: INT, -- the length of the via at the end of the channel
parms: CabbagePrivate.ParmSet]
RETURNS [channel: CabbagePrivate.Channel] ~ {
result: Route.RoutingResult;
retrieveRect: Route.RefRect;
rect: CD.Rect;
otherSide: Route.Side ← RTBasic.OtherSide[side];
blSide: Route.Side ← IF side=bottom OR side=top THEN left ELSE bottom;
topOrRight: BOOLEAN ← side= right OR side=top;
direction: RTBasic.Direction ← IF side= right OR side=left THEN vertical ELSE horizontal;
construct the bonding objects to pass to the channel router
obj1: Cabbage.Object ←
IF topOrRight
THEN MappedShellFromObject[handle, outerObject, otherSide, innerRange, outerRange, viaSize, parms.rules]
ELSE ShellFromObject[handle, outerObject, otherSide, outerRange, parms.rules, TRUE];
obj2: Cabbage.Object ←
IF topOrRight
THEN ShellFromObject[handle, outerObject, otherSide, outerRange, parms.rules,
TRUE]
ELSE MappedShellFromObject[handle, outerObject, otherSide, innerRange, outerRange, viaSize, parms.rules];
bottomOrLeftObj: Cabbage.Object ← ShellFromOutsideEnd[handle, outerObject, otherSide, blSide, innerRange, outerRange, parms.rules];
topOrRightObj: Cabbage.Object ← ShellFromOutsideEnd[handle, outerObject, otherSide, RTBasic.OtherSide[blSide], innerRange, outerRange, parms.rules];
parms.parms.wireWidthProc ← GetWireWidth;
parms.parms.makeTabKeyProc ← PinName;
parms.parms.context ← NEW[PWRouteContext ← [direction: direction, table: handle.widthTable]];
result ← PWRoute.DoRoute[obj1, obj2, bottomOrLeftObj, topOrRightObj, parms.parms, side= right OR side=left, channel];
rect ← result.routingRect;
SELECT side
FROM
bottom => {
dist: INT ← MIN[rect.y1, rect.y2 - chWidth];
retrieveRect ← NEW[CD.Rect ← [rect.x1, dist, rect.x2, rect.y2]]};
right => {
dist: INT ← MAX[rect.x2, rect.x1 + chWidth];
retrieveRect ← NEW[CD.Rect ← [rect.x1, rect.y1, dist, rect.y2]]};
top => {
dist: INT ← MAX[rect.y2, rect.y1 + chWidth];
retrieveRect ← NEW[CD.Rect ← [rect.x1, rect.y1, rect.x2, dist]]};
left => {
dist: INT ← MIN[rect.x1, rect.x2 - chWidth];
retrieveRect ← NEW[CD.Rect ← [dist, rect.y1, rect.x2, rect.y2]]};
ENDCASE;
channel.object ← PWRoute.GetRouting[result, retrieveRect, parms.parms];
channel.size ← RTBasic.IRSize[channel.object];
channel.cellType ← ExtractChannel[channel, parms]};
RoutePower:
PROC [handle: CabbagePrivate.Handle,
channel: CabbagePrivate.Channel, -- inner or outer channel as determined by side
chipSide: Route.Side, -- the side of the chip for which this channel is being constructed
range: Connections.Range, -- the span along the appropriate power routing cell
powerWidth: INT, -- the only permitted width for the power cell
trunkWidth: INT, -- the width of the power trunk
insideParms, outsideParms: CabbagePrivate.ParmSet]
RETURNS [power: CabbagePrivate.Channel] ~ {
build the power routing cell for the indicated side
connect the Vdd and Gnd pin via a bus connection and transfer the signal pins across with appropriate vias
inside and outside pins are put on the [inside|outside]Parms.rules.branchLayer
ChanPublics: CoreGeometry.EachWirePinProc ~ {
PROC [wire: Wire, min, max: INT, side: Side, layer: CD.Layer] RETURNS [quit: BOOL ← FALSE];
store the pins on the appropriate side of the adjacent channel
OuterPowerBranch:
PROC [branchLength:
INT, branchLayer, trunkLayer:
CD.Layer] ~ {
pos:
CD.Position ←
SELECT chipSide
FROM
bottom => [adjustedRange.min, 0],
top => [adjustedRange.min, powerWidth - branchLength],
left => [0, adjustedRange.min],
right => [powerWidth - branchLength, adjustedRange.min],
ENDCASE => Cabbage.Error[programmingError, "Not suppose to happen"];
SELECT chipSide
FROM
bottom, top => CDProperties.PutProp[RouteUtil.Include[object, CDRects.CreateRect[[max-min, branchLength], branchLayer], pos], $SignalName, name];
left, right => CDProperties.PutProp[RouteUtil.Include[object, CDRects.CreateRect[[branchLength, max-min], branchLayer], pos], $SignalName, name];
ENDCASE => Cabbage.Error[programmingError, "Not suppose to happen"];
IF branchLayer # trunkLayer
THEN {
add the via at the right place
-- irSize stuff should be remove in Cabbage25
via:
CD.Object ←
SELECT chipSide
FROM
bottom, top => RouteUtil.StitchVias[[max-min, trunkWidth], trunkLayer, branchLayer, insideParms.rules.CDLambda, NIL],
left, right => RouteUtil.StitchVias[[trunkWidth, max-min], trunkLayer, branchLayer, insideParms.rules.CDLambda, NIL],
ENDCASE => Cabbage.Error[programmingError, "Not suppose to happen"];
irSize: CD.Position ← RTBasic.IRSize[via];
xOffset:
INT ←
SELECT chipSide
FROM
bottom, top => (max-min - irSize.x)/2,
left, right => (trunkWidth - irSize.x)/2,
ENDCASE => Cabbage.Error[programmingError, "Not suppose to happen"];
yOffset:
INT ←
SELECT chipSide
FROM
bottom, top => (trunkWidth - irSize.y)/2,
left, right => (max-min - irSize.y)/2,
ENDCASE => Cabbage.Error[programmingError, "Not suppose to happen"];
viaPos:
CD.Position ←
SELECT chipSide
FROM
bottom => [adjustedRange.min + xOffset, branchLength - trunkWidth + yOffset],
top => [adjustedRange.min + xOffset, powerWidth - branchLength + yOffset],
left => [branchLength - trunkWidth + xOffset, adjustedRange.min + yOffset],
right => [powerWidth - branchLength + xOffset, adjustedRange.min + yOffset],
ENDCASE => Cabbage.Error[programmingError, "Not suppose to happen"];
CDProperties.PutProp[RouteUtil.Include[object, via, viaPos], $SignalName, name]}};
SignalBranch:
PROC [] ~ {
outsideLength: INT ← outsideParms.rules.trunkSpacing + distToOuter;
insideLength: INT ← insideParms.rules.trunkSpacing + distToInner;
SELECT chipSide
FROM
bottom => {
CDProperties.PutProp[RouteUtil.Include[object, CDRects.CreateRect[[max-min, outsideLength], outsideLayer], [adjustedRange.min, 0]], $SignalName, name];
CDProperties.PutProp[RouteUtil.Include[object, CDRects.CreateRect[[max-min, insideLength], insideLayer], [adjustedRange.min, powerWidth - insideLength]], $SignalName, name];
[] ← RouteUtil.Include[object, RouteUtil.StitchVias[[max-min, insideParms.rules.contactSize], insideLayer, outsideLayer, insideParms.rules.CDLambda, NIL], [adjustedRange.min, outsideLength]]};
top => {
CDProperties.PutProp[RouteUtil.Include[object, CDRects.CreateRect[[max-min, outsideLength], outsideLayer], [adjustedRange.min, powerWidth - outsideLength]], $SignalName, name];
CDProperties.PutProp[RouteUtil.Include[object, CDRects.CreateRect[[max-min, insideLength], insideLayer], [adjustedRange.min, 0]], $SignalName, name];
[] ← RouteUtil.Include[object, RouteUtil.StitchVias[[max-min, insideParms.rules.contactSize], insideLayer, outsideLayer, insideParms.rules.CDLambda, NIL], [adjustedRange.min, insideLength]]};
left => {
CDProperties.PutProp[RouteUtil.Include[object, CDRects.CreateRect[[outsideLength, max-min], outsideLayer], [0, adjustedRange.min]], $SignalName, name];
CDProperties.PutProp[RouteUtil.Include[object, CDRects.CreateRect[[insideLength, max-min], insideLayer], [powerWidth - insideLength, adjustedRange.min]], $SignalName, name];
[] ← RouteUtil.Include[object, RouteUtil.StitchVias[[insideParms.rules.contactSize, max-min], insideLayer, outsideLayer, insideParms.rules.CDLambda, NIL], [outsideLength, adjustedRange.min]]};
right => {
CDProperties.PutProp[RouteUtil.Include[object, CDRects.CreateRect[[outsideLength, max-min], outsideLayer], [powerWidth - outsideLength, adjustedRange.min]], $SignalName, name];
CDProperties.PutProp[RouteUtil.Include[object, CDRects.CreateRect[[insideLength, max-min], insideLayer], [0, adjustedRange.min]], $SignalName, name];
[] ← RouteUtil.Include[object, RouteUtil.StitchVias[[insideParms.rules.contactSize, max-min], insideLayer, outsideLayer, insideParms.rules.CDLambda, NIL], [insideLength, adjustedRange.min]]};
ENDCASE};
name: Rope.ROPE ← CoreOps.GetShortWireName[wire];
adjustedRange: Connections.Range ← [channelOrigin + min, channelOrigin + max];
IF side = otherSide
THEN {
SELECT
TRUE
FROM
Rope.Equal[name, "Vdd"] => OuterPowerBranch[distToOuter, outsideLayer, insideLayer];
Rope.Equal[name, "Gnd"] => OuterPowerBranch[powerWidth - 2*insideParms.rules.trunkToTrunk, outsideLayer, outsideLayer];
ENDCASE => SignalBranch[]}};
EachNet: Connections.EachNetAction ~ {
PROC [key: Key, net: Net] RETURNS [quit: BOOLEAN ← FALSE]
store the power pins on the appropriate side of the inner object
EachSegment: Connections.EachSegmentAction ~ {
PROC [net: Net, segment: Segment] RETURNS [quit: BOOLEAN ← FALSE]
InnerPowerBranch:
PROC [branchLength:
INT, branchLayer, trunkLayer:
CD.Layer] ~ {
rectPos:
CD.Position ←
SELECT chipSide
FROM
bottom => [adjustedRange.min, powerWidth - branchLength],
top => [adjustedRange.min, 0],
left => [powerWidth - branchLength, adjustedRange.min],
right => [0, adjustedRange.min],
ENDCASE => Cabbage.Error[programmingError, "Not suppose to happen"];
SELECT chipSide
FROM
bottom, top => CDProperties.PutProp[RouteUtil.Include[object, CDRects.CreateRect[[segment.range.max-segment.range.min, branchLength], insideLayer], rectPos], $SignalName, net.name];
left, right => CDProperties.PutProp[RouteUtil.Include[object, CDRects.CreateRect[[branchLength, segment.range.max-segment.range.min], insideLayer], rectPos], $SignalName, net.name];
ENDCASE;
IF branchLayer # trunkLayer
THEN {
add the via at the right place
via:
CD.Object ←
SELECT chipSide
FROM
bottom, top => RouteUtil.StitchVias[[segment.range.max-segment.range.min, trunkWidth], trunkLayer, branchLayer, insideParms.rules.CDLambda, NIL],
left, right => RouteUtil.StitchVias[[trunkWidth, segment.range.max-segment.range.min], trunkLayer, branchLayer, insideParms.rules.CDLambda, NIL],
ENDCASE => Cabbage.Error[programmingError, "Not suppose to happen"];
irSize to go away in Cabbage25
irSize: CD.Position ← RTBasic.IRSize[via];
xOffset:
INT ←
SELECT chipSide
FROM
bottom, top => (segment.range.max-segment.range.min - irSize.x)/2,
left, right => (trunkWidth - irSize.x)/2,
ENDCASE => Cabbage.Error[programmingError, "Not suppose to happen"];
yOffset:
INT ←
SELECT chipSide
FROM
bottom, top => (trunkWidth - irSize.y)/2,
left, right => (segment.range.max-segment.range.min - irSize.y)/2,
ENDCASE => Cabbage.Error[programmingError, "Not suppose to happen"];
viaPos:
CD.Position ←
SELECT chipSide
FROM
bottom => [adjustedRange.min + xOffset, powerWidth - branchLength + yOffset],
top => [adjustedRange.min + xOffset, branchLength - trunkWidth + yOffset],
left => [powerWidth - branchLength + xOffset, adjustedRange.min + yOffset],
right => [branchLength - trunkWidth + xOffset, adjustedRange.min + yOffset],
ENDCASE => Cabbage.Error[programmingError, "Not suppose to happen"];
CDProperties.PutProp[RouteUtil.Include[object, via, viaPos], $SignalName, net.name]}};
adjustedRange: Connections.Range ← [innerOrigin + segment.range.min, innerOrigin + segment.range.max];
IF segment.object = handle.inner.object
AND segment.side = chipSide
THEN {
SELECT
TRUE
FROM
Rope.Equal[net.name, "Vdd"] => InnerPowerBranch[powerWidth - distToOuter, insideLayer, insideLayer];
Rope.Equal[net.name, "Gnd"] => InnerPowerBranch[distToInner, insideLayer, outsideLayer];
ENDCASE}};
[] ← Connections.EnumerateSegments[net, EachSegment]};
PowerTrunk:
PROC [position:
CD.Position, layer, otherLayer:
CD.Layer, name: Rope.
ROPE, addVias:
BOOLEAN] ~ {
trunkSize:
CD.Position ←
SELECT chipSide
FROM
bottom, top => [range.max-range.min, trunkWidth],
left, right => [trunkWidth, range.max-range.min],
ENDCASE => Cabbage.Error[programmingError, "Not suppose to happen"];
trunk: CD.Object ← CDRects.CreateRect[trunkSize, layer];
CDProperties.PutProp[RouteUtil.Include[object, trunk, position], $SignalName, name];
IF addVias
THEN {
via: CD.Object ← RouteUtil.StitchVias[[trunkWidth, trunkWidth], layer, otherLayer, insideParms.rules.CDLambda, NIL];
irSize: CD.Position ← RTBasic.IRSize[via];
viaPosition:
CD.Position ←
SELECT chipSide
FROM
bottom, top => [range.max-range.min - irSize.x, (trunkWidth-irSize.y)/2],
left, right => [(trunkWidth-irSize.x)/2, range.max-range.min - irSize.y],
ENDCASE => Cabbage.Error[programmingError, "Not suppose to happen"];
REMOVE branch stuff in Cabbage25
branch: CD.Object ← CDRects.CreateRect[[trunkWidth, trunkWidth], otherLayer];
branchPosition:
CD.Position ←
SELECT chipSide
FROM
bottom, top => [range.max-range.min - trunkWidth, 0],
left, right => [0, range.max-range.min - trunkWidth],
ENDCASE => Cabbage.Error[programmingError, "Not suppose to happen"];
CDProperties.PutProp[RouteUtil.Include[object, branch, position], $SignalName, name];
CDProperties.PutProp[RouteUtil.Include[object, branch, CDBasics.AddPoints[position, branchPosition]], $SignalName, name];
CDProperties.PutProp[RouteUtil.Include[object, via, position], $SignalName, name];
CDProperties.PutProp[RouteUtil.Include[object, via, CDBasics.AddPoints[position, viaPosition]], $SignalName, name]}};
insideLayer: CD.Layer ← insideParms.rules.branchLayer;
outsideLayer: CD.Layer ← outsideParms.rules.branchLayer;
distToInner: INT ← trunkWidth + 2*insideParms.rules.trunkToTrunk;
distToOuter: INT ← trunkWidth + 2*outsideParms.rules.trunkToTrunk;
object: Cabbage.Object ← CDCells.CreateEmptyCell[];
mode: Sinix.Mode = SinixOps.GetExtractMode[insideParms.rules.technology];
otherSide: CoreGeometry.Side ←
SELECT chipSide
FROM
bottom => top, right => left, top => bottom, left=> right,
ENDCASE => Cabbage.Error[programmingError, "Not suppose to happen"];
innerOrigin:
INT ←
SELECT chipSide
FROM
bottom, top => handle.inner.origin.x,
right, left => handle.inner.origin.y,
ENDCASE => Cabbage.Error[programmingError, "Not suppose to happen."];
channelOrigin:
INT ←
SELECT chipSide
FROM
bottom, top => channel.origin.x,
right, left => channel.origin.y,
ENDCASE => Cabbage.Error[programmingError, "Not suppose to happen."];
interestRect:
CD.Rect ←
SELECT chipSide
FROM
bottom, top => [range.min, 0 , range.max, powerWidth],
left, right => [0, range.min , powerWidth, range.max],
ENDCASE => Cabbage.Error[programmingError, "Not suppose to happen"];
construct power trunks
innerTrunkPos:
CD.Position ←
SELECT chipSide
FROM
bottom => [range.min, powerWidth - distToInner],
top => [range.min, 2*insideParms.rules.trunkToTrunk],
left => [powerWidth - distToInner, range.min],
right => [2*insideParms.rules.trunkToTrunk, range.min],
ENDCASE => Cabbage.Error[programmingError, "Not suppose to happen"];
outerTrunkPos:
CD.Position ←
SELECT chipSide
FROM
bottom => [range.min, 2*outsideParms.rules.trunkToTrunk],
top => [range.min, powerWidth - distToOuter],
left => [2*outsideParms.rules.trunkToTrunk, range.min],
right => [powerWidth - distToOuter, range.min],
ENDCASE => Cabbage.Error[programmingError, "Not suppose to happen"];
PowerTrunk[outerTrunkPos, insideLayer, outsideLayer, "Vdd", FALSE];
PowerTrunk[innerTrunkPos, outsideLayer, insideLayer, "Gnd", TRUE];
build the branches
[] ← CoreGeometry.EnumerateNonOverlappingSides[mode.decoration, channel.cellType, ChanPublics];
[] ← Connections.EnumerateNets[handle.connections, EachNet];
power.object ← object;
CDCells.SetInterestRect[design: NIL, cell: power.object, r: interestRect];
RTBasic.RepositionCell[power.object];
power.size ← RTBasic.IRSize[power.object];
power.cellType ← ExtractChannel[power, insideParms]};
RouteOutsideSwitchBoxes:
PROC [handle: CabbagePrivate.Handle] ~ {
route the switchboxes in the outside corners. these switchboxes connect the power busses; any signal pins on the padring get transfered to the adjacent channel
vertParms: CabbagePrivate.ParmSet ← handle.rules.vertParms;
powerWidth: INT ← handle.parms.outerChanWidth + handle.parms.powerCellWidth;
leftHorizRange: Connections.Range ← [handle.left.origin.x + handle.left.size.x, handle.left.origin.x + handle.left.size.x + powerWidth];
rightHorizRange: Connections.Range ← [handle.right.origin.x - powerWidth, handle.right.origin.x];
bottomVertRange: Connections.Range ← [handle.bottom.origin.y + handle.bottom.size.y, handle.bottom.origin.y + handle.bottom.size.y + powerWidth];
topVertRange: Connections.Range ← [handle.top.origin.y- powerWidth, handle.top.origin.y];
vertParms.parms.okToDiddleLLPins ← TRUE;
handle.powerDistribution.switchBoxes[bottomLeft] ← RouteOutsideSwitchBox[handle, bottomLeft, leftHorizRange, bottomVertRange, vertParms];
handle.powerDistribution.switchBoxes[topLeft] ← RouteOutsideSwitchBox[handle, topLeft, leftHorizRange, topVertRange, vertParms];
vertParms.parms.okToDiddleLLPins ← FALSE; vertParms.parms.okToDiddleURPins ← TRUE;
handle.powerDistribution.switchBoxes[bottomRight] ← RouteOutsideSwitchBox[handle, bottomRight, rightHorizRange, bottomVertRange, vertParms];
handle.powerDistribution.switchBoxes[topRight] ← RouteOutsideSwitchBox[handle, topRight, rightHorizRange, topVertRange, vertParms];
vertParms.parms.okToDiddleLLPins ← FALSE; vertParms.parms.okToDiddleURPins ← FALSE};
RouteOutsideSwitchBox:
PROC [handle: CabbagePrivate.Handle, corner: CabbagePrivate.Corners, horizRange, vertRange: Connections.Range, parms: CabbagePrivate.ParmSet]
RETURNS [switchBox: CabbagePrivate.Channel] ~ {
construct a switchbox for one of the power distribution corners
bottomObject, topObject, leftObject, rightObject: Cabbage.Object;
SELECT corner
FROM
bottomLeft => {
topObject ← PW.AbutListX[LIST[ShellFromFullChannel[handle.powerDistribution.channels[left], bottom, parms.rules.branchLayer, parms.rules], ShellFromFullChannel[handle.powerDistribution.power[left], bottom, parms.rules.branchLayer, parms.rules]]];
bottomObject ← ShellFromObject[handle, handle.bottom, top, horizRange, parms.rules, FALSE];
leftObject ← ShellFromObject[handle, handle.left, right, vertRange, parms.rules, FALSE];
rightObject ← PW.AbutListY[LIST[ShellFromFullChannel[handle.powerDistribution.channels[bottom], left, parms.rules.trunkLayer, parms.rules], ShellFromFullChannel[handle.powerDistribution.power[bottom], left, parms.rules.trunkLayer, parms.rules]]]};
bottomRight => {
topObject ← PW.AbutListX[LIST[ShellFromFullChannel[handle.powerDistribution.power[right], bottom, parms.rules.branchLayer, parms.rules], ShellFromFullChannel[handle.powerDistribution.channels[right], bottom, parms.rules.branchLayer, parms.rules]]];
bottomObject ← ShellFromObject[handle, handle.bottom, top, horizRange, parms.rules, FALSE];
leftObject ← PW.AbutListY[LIST[ShellFromFullChannel[handle.powerDistribution.channels[bottom], right, parms.rules.trunkLayer, parms.rules], ShellFromFullChannel[handle.powerDistribution.power[bottom], right, parms.rules.trunkLayer, parms.rules]]];
rightObject ← ShellFromObject[handle, handle.right, left, vertRange, parms.rules, FALSE]};
topRight => {
topObject ← ShellFromObject[handle, handle.top, bottom, horizRange, parms.rules, FALSE];
bottomObject ← PW.AbutListX[LIST[ShellFromFullChannel[handle.powerDistribution.power[right], top, parms.rules.branchLayer, parms.rules], ShellFromFullChannel[handle.powerDistribution.channels[right], top, parms.rules.branchLayer, parms.rules]]];
leftObject ← PW.AbutListY[LIST[ShellFromFullChannel[handle.powerDistribution.power[top], right, parms.rules.trunkLayer, parms.rules], ShellFromFullChannel[handle.powerDistribution.channels[top], right, parms.rules.trunkLayer, parms.rules]]];
rightObject ← ShellFromObject[handle, handle.right, left, vertRange, parms.rules, FALSE]};
topLeft => {
topObject ← ShellFromObject[handle, handle.top, bottom, horizRange, parms.rules, FALSE];
bottomObject ← PW.AbutListX[LIST[ShellFromFullChannel[handle.powerDistribution.channels[left], top, parms.rules.branchLayer, parms.rules], ShellFromFullChannel[handle.powerDistribution.power[left], top, parms.rules.branchLayer, parms.rules]]];
leftObject ← ShellFromObject[handle, handle.left, right, vertRange, parms.rules, FALSE];
rightObject ← PW.AbutListY[LIST[ShellFromFullChannel[handle.powerDistribution.power[top], left, parms.rules.trunkLayer, parms.rules], ShellFromFullChannel[handle.powerDistribution.channels[top], left, parms.rules.trunkLayer, parms.rules]]]};
ENDCASE;
parms.parms.wireWidthProc ← NIL;
parms.parms.makeTabKeyProc ← NIL;
parms.parms.context ← NEW[PWRouteContext ← [direction: parms.rules.trunkDirection, table: handle.widthTable]];
switchBox.object ← PWRoute.MakeChannel[bottomObject, topObject, leftObject, rightObject, NIL, parms.parms, FALSE, switchBox];
switchBox.size ← RTBasic.IRSize[switchBox.object];
switchBox.cellType ← ExtractChannel[switchBox, parms]};
Global Routing
GlobalRoute:
PUBLIC
PROC [handle: CabbagePrivate.Handle] ~ {
find the strategic paths for all nets
EachNet: Connections.EachNetAction ~ {
PROC [key: Key, net: Net] RETURNS [quit: BOOLEAN ← FALSE]
sortedSegments: CabbagePrivate.SegmentSeq ← SortSegments[handle, net];
IF sortedSegments #
NIL
THEN {
segmentPair: CabbagePrivate.SegmentPair ← FindStartEndSegments[handle, net, sortedSegments];
AddNetToGlobalRoute[handle, net, segmentPair]}};
newConnections: Connections.Table ← MakeNewConnections[handle];
[] ← Connections.EnumerateNets[newConnections, EachNet]};
MakeNewConnections:
PROC [handle: CabbagePrivate.Handle]
RETURNS [newConnections: Connections.Table ← Connections.CreateForRopes[]] ~ {
Make a new set of connections to account for new power ring
store the net and the segments on the net
InsertPinsFromInner[handle, newConnections];
now do the power objects
InsertPinsFromPower[handle, newConnections, bottom];
InsertPinsFromPower[handle, newConnections, right];
InsertPinsFromPower[handle, newConnections, top];
InsertPinsFromPower[handle, newConnections, left]};
InsertPinsFromInner:
PROC [handle: CabbagePrivate.Handle, newConnections: Connections.Table] ~ {
insert all of the pins from the inner object into the new table
EachNet: Connections.EachNetAction ~ {
PROC [key: Key, net: Net] RETURNS [quit: BOOLEAN ← FALSE]
EachSegment: Connections.EachSegmentAction ~ {
PROC [net: Net, segment: Segment] RETURNS [quit: BOOLEAN ← FALSE]
IF segment.object = handle.inner.object
THEN {
make a new copy of the segment and put it in the table
newSegment: Connections.Segment ← NEW[Connections.SegmentRec ← [name: segment.name, object: segment.object, range: segment.range, side: segment.side, layer: segment.layer]];
newNet.segments ← CONS[newSegment, newNet.segments];
[] ← Connections.Store[newConnections, net.name, newNet]}};
newNet: Connections.Net ← NEW[Connections.NetRec ← [name: net.name, width: net.width]];
[] ← Connections.Store[newConnections, net.name, newNet];
[] ← Connections.EnumerateSegments[net, EachSegment]};
store the net and the segments on the net
[] ← Connections.EnumerateNets[handle.connections, EachNet]};
InsertPinsFromPower:
PROC [handle: CabbagePrivate.Handle, newConnections: Connections.Table, chipSide: RTBasic.Side] ~ {
insert the pins on the appropriate side into the new table
ChanPublics: CoreGeometry.EachWirePinProc ~ {
PROC [wire: Wire, min, max: INT, side: Side, layer: CD.Layer] RETURNS [quit: BOOL ← FALSE];
store the pins on the appropriate side of the adjacent channel
name: Rope.ROPE ← CoreOps.GetShortWireName[wire];
segmentSide: Route.Side ←
SELECT side
FROM
bottom => bottom, right => right, top => top, left=> left,
ENDCASE => Cabbage.Error[programmingError, "Not suppose to happen"];
IF segmentSide = otherSide
THEN {
segment: Connections.Segment ← NEW[Connections.SegmentRec ← [name: name, object: handle.powerDistribution.power[chipSide].object, range: [min, max], side: segmentSide, layer: layer]];
net: Connections.Net ← Connections.Fetch[newConnections, name].net;
net.segments ← CONS[segment, net.segments];
[] ← Connections.Store[newConnections, name, net]};
};
otherSide: Route.Side ← RTBasic.OtherSide[chipSide];
mode: Sinix.Mode = SinixOps.GetExtractMode[handle.rules.horizParms.rules.technology];
[] ← CoreGeometry.EnumerateNonOverlappingSides[mode.decoration, handle.powerDistribution.power[chipSide].cellType, ChanPublics]};
SortSegments:
PROC [handle: CabbagePrivate.Handle, net: Connections.Net]
RETURNS [sortedSegments: CabbagePrivate.SegmentSeq ←
NIL] ~ {
Sort the segments on this net in order arround the periphery
CountSegments: Connections.EachSegmentAction ~ {numSegments ← numSegments + 1};
PinCompare: List.CompareProc ~ {
pos1, pos2: INT;
TRUSTED{
pos1 ← PosOf[handle, LOOPHOLE[ref1]];
pos2 ← PosOf[handle, 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]};
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: INT ← LAST[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, startSeg] + PosOf[handle, endSeg]}
ELSE {
endSeg ← sortedSegments[index];
startSeg ← sortedSegments[0];
length ← PosOf[handle, endSeg] - PosOf[handle, 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, segmentPair.seg1];
pos2: INT ← PosOf[handle, 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.origin.x, handle.inner.origin.x + handle.inner.size.x];
vertRange: Connections.Range ← [handle.inner.origin.y, handle.inner.origin.y + handle.inner.size.y];
IF handle.routeType = normal
THEN {
handle.detailedRouting.channels[bottom] ← RouteChannel[handle, handle.powerDistribution.power[bottom], bottom, bottomLeft, bottomRight, horizRange, horizParms];
handle.detailedRouting.channels[right] ← RouteChannel[handle, handle.powerDistribution.power[right], right, rightBottom, rightTop, vertRange, vertParms];
handle.detailedRouting.channels[top] ← RouteChannel[handle, handle.powerDistribution.power[top], top, topLeft, topRight, horizRange, horizParms];
handle.detailedRouting.channels[left] ← RouteChannel[handle, handle.powerDistribution.power[left], left, leftBottom, leftTop, vertRange, vertParms]}
ELSE {
-- routeType = padLimited
handle.detailedRoutingPL.channels[right] ← RouteChannel[handle, handle.powerDistribution.power[right], right, rightBottom, rightTop, vertRange, vertParms];
handle.detailedRoutingPL.channels[left] ← RouteChannel[handle, handle.powerDistribution.power[left], left, leftBottom, leftTop, vertRange, vertParms]}};
route one of the channels
RouteChannel:
PROC [handle: CabbagePrivate.Handle,
boundingChannel: CabbagePrivate.Channel, -- the power channel to use
chipSide: Route.Side, -- the side of chip for which this channel is being constructed
llDiv, urDiv: CabbagePrivate.Division, -- the lower and upper boundries of the channel
range: Connections.Range, -- the range of interest along the channel side
parms: CabbagePrivate.ParmSet]
RETURNS [channel: CabbagePrivate.Channel] ~ {
result: Route.RoutingResult;
retrieveRect: Route.RefRect;
rect: CD.Rect;
offset: INT ← parms.rules.trunkToTrunk;
otherSide: Route.Side ← RTBasic.OtherSide[chipSide];
direction: RTBasic.Direction ← IF chipSide= right OR chipSide=left THEN vertical ELSE horizontal;
blSide: Route.Side ← IF chipSide=bottom OR chipSide=top THEN left ELSE bottom;
topOrRight: BOOLEAN ← chipSide= right OR chipSide=top;
construct the bonding objects to pass to the channel router
obj1: Cabbage.Object ←
IF topOrRight
THEN ShellFromObject[handle, handle.inner, chipSide, range, parms.rules,
TRUE]
ELSE ShellFromChannel[boundingChannel, otherSide, parms.rules.branchLayer, range, parms.rules];
obj2: Cabbage.Object ←
IF topOrRight
THEN ShellFromChannel[boundingChannel, otherSide, parms.rules.branchLayer, range, parms.rules]
ELSE ShellFromObject[handle, handle.inner, chipSide, range, parms.rules, TRUE];
bottomOrLeftObj: Cabbage.Object ← ShellFromEnd[handle, llDiv, blSide, parms.rules];
topOrRightObj: Cabbage.Object ← ShellFromEnd[handle, urDiv, RTBasic.OtherSide[blSide], parms.rules];
parms.parms.wireWidthProc ← GetWireWidth;
parms.parms.makeTabKeyProc ← PinName;
parms.parms.context ← NEW[PWRouteContext ← [direction: direction, table: handle.widthTable]];
result ← PWRoute.DoRoute[obj1, obj2, bottomOrLeftObj, topOrRightObj, parms.parms, chipSide=right OR chipSide=left, channel];
rect ← result.routingRect;
SELECT chipSide
FROM
bottom => {
size: INT ← handle.inner.origin.y - (boundingChannel.origin.y + boundingChannel.size.y);
retrieveRect ← NEW[CD.Rect ← [rect.x1, MIN[rect.y1, rect.y2 - size + offset], rect.x2, rect.y2 + offset]]};
right => {
size: INT ← boundingChannel.origin.x - (handle.inner.origin.x + handle.inner.size.x);
retrieveRect ← NEW[CD.Rect ← [rect.x1 - offset, rect.y1, MAX[rect.x2, rect.x1 + size - offset], rect.y2]]};
top => {
size: INT ← boundingChannel.origin.y - (handle.inner.origin.y + handle.inner.size.y);
retrieveRect ← NEW[CD.Rect ← [rect.x1, rect.y1 - offset, rect.x2, MAX[rect.y2, rect.x1 + size - offset]]]};
left => {
size: INT ← handle.inner.origin.x - (boundingChannel.origin.x + boundingChannel.size.x);
retrieveRect ← NEW[CD.Rect ← [MIN[rect.x1, rect.x2 - size + offset], rect.y1, rect.x2 + offset, rect.y2]]};
ENDCASE;
channel.object ← PWRoute.GetRouting[result, retrieveRect, parms.parms];
channel.size ← RTBasic.IRSize[channel.object];
channel.cellType ← ExtractChannel[channel, parms]};
adjust the positions of everything to account for the actual channel widths
route all of the switchBoxes (the corners)
RouteSwitchBoxes:
PROC [handle: CabbagePrivate.Handle] ~ {
horizParms: CabbagePrivate.ParmSet ← handle.rules.horizParms;
leftHorizRange: Connections.Range ← [handle.left.origin.x + handle.left.size.x, handle.inner.origin.x];
rightHorizRange: Connections.Range ← [handle.inner.origin.x + handle.inner.size.x, handle.right.origin.x];
bottomVertRange: Connections.Range ← [handle.bottom.origin.y + handle.bottom.size.y, handle.inner.origin.y];
topVertRange: Connections.Range ← [handle.inner.origin.y + handle.inner.size.y, handle.top.origin.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;
powerWidth: INT ← handle.parms.outerChanWidth + handle.parms.powerCellWidth;
horizRange: Connections.Range ← [handle.left.origin.x + handle.left.size.x + powerWidth, handle.right.origin.x - powerWidth];
bottomVertRange: Connections.Range ← [handle.bottom.origin.y + handle.bottom.size.y + powerWidth, handle.inner.origin.y];
topVertRange: Connections.Range ← [handle.inner.origin.y + handle.inner.size.y, handle.top.origin.y - powerWidth];
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};
RouteSwitchBoxPL:
PROC [handle: CabbagePrivate.Handle, side: RTBasic.TBSide, horizRange, vertRange: Connections.Range, parms: CabbagePrivate.ParmSet]
RETURNS [switchBox: CabbagePrivate.Channel] ~ {
bottomObject, topObject: Cabbage.Object;
leftObject: Cabbage.Object ← ShellFromChannel[handle.powerDistribution.power[left], right, parms.rules.trunkLayer, vertRange, parms.rules];
rightObject: Cabbage.Object ← ShellFromChannel[handle.powerDistribution.power[right], left, parms.rules.trunkLayer, vertRange, parms.rules];
innerRange: Connections.Range ← [handle.inner.origin.x, handle.inner.origin.x + handle.inner.size.x];
direction: RTBasic.Direction ← IF side= right OR side=left THEN vertical ELSE horizontal;
SELECT side
FROM
bottom => {
innerObject: Cabbage.Object ← ShellFromObject[handle, handle.inner, bottom, innerRange, parms.rules, TRUE];
topObject ← PW.AbutListX[LIST[ShellFromFullChannel[handle.detailedRoutingPL.channels[left], bottom, parms.rules.branchLayer, parms.rules], innerObject, ShellFromFullChannel[handle.detailedRoutingPL.channels[right], bottom, parms.rules.branchLayer, parms.rules]]];
bottomObject ← ShellFromChannel[handle.powerDistribution.power[bottom], top, parms.rules.branchLayer, horizRange, parms.rules]};
top => {
innerObject: Cabbage.Object ← ShellFromObject[handle, handle.inner, top, innerRange, parms.rules, TRUE];
bottomObject ← PW.AbutListX[LIST[ShellFromFullChannel[handle.detailedRoutingPL.channels[left], top, parms.rules.branchLayer, parms.rules], innerObject, ShellFromFullChannel[handle.detailedRoutingPL.channels[right], top, parms.rules.branchLayer, parms.rules]]];
topObject ← ShellFromChannel[handle.powerDistribution.power[top], bottom, parms.rules.branchLayer, horizRange, parms.rules]};
ENDCASE;
parms.parms.wireWidthProc ← GetWireWidth;
parms.parms.makeTabKeyProc ← PinName;
parms.parms.context ← NEW[PWRouteContext ← [direction: direction, table: handle.widthTable]];
switchBox.object ← PWRoute.MakeChannel[bottomObject, topObject, leftObject, rightObject, NIL, parms.parms, FALSE, switchBox];
switchBox.size ← RTBasic.IRSize[switchBox.object];
switchBox.cellType ← ExtractChannel[switchBox, parms]};
RouteSwitchBox:
PROC [handle: CabbagePrivate.Handle, corner: CabbagePrivate.Corners, horizRange, vertRange: Connections.Range, parms: CabbagePrivate.ParmSet]
RETURNS [switchBox: CabbagePrivate.Channel] ~ {
bottomObject, topObject, leftObject, rightObject: Cabbage.Object;
SELECT corner
FROM
bottomLeft => {
topObject ← ShellFromFullChannel[handle.detailedRouting.channels[left], bottom, parms.rules.branchLayer, parms.rules];
bottomObject ← ShellFromChannel[handle.powerDistribution.power[bottom], top, parms.rules.branchLayer, horizRange, parms.rules];
leftObject ← ShellFromChannel[handle.powerDistribution.power[left], right, parms.rules.trunkLayer, vertRange, parms.rules];
rightObject ← ShellFromFullChannel[handle.detailedRouting.channels[bottom], left, parms.rules.trunkLayer, parms.rules]};
bottomRight => {
topObject ← ShellFromFullChannel[handle.detailedRouting.channels[right], bottom, parms.rules.branchLayer, parms.rules];
bottomObject ← ShellFromChannel[handle.powerDistribution.power[bottom], top, parms.rules.branchLayer, horizRange, parms.rules];
rightObject ← ShellFromChannel[handle.powerDistribution.power[right], left, parms.rules.trunkLayer, vertRange, parms.rules];
leftObject ← ShellFromFullChannel[handle.detailedRouting.channels[bottom], right, parms.rules.trunkLayer, parms.rules]};
topRight => {
bottomObject ← ShellFromFullChannel[handle.detailedRouting.channels[right], top, parms.rules.branchLayer, parms.rules];
topObject ← ShellFromChannel[handle.powerDistribution.power[top], bottom, parms.rules.branchLayer, horizRange, parms.rules];
rightObject ← ShellFromChannel[handle.powerDistribution.power[right], left, parms.rules.trunkLayer, vertRange, parms.rules];
leftObject ← ShellFromFullChannel[handle.detailedRouting.channels[top], right, parms.rules.trunkLayer, parms.rules]};
topLeft => {
bottomObject ← ShellFromFullChannel[handle.detailedRouting.channels[left], top, parms.rules.branchLayer, parms.rules];
topObject ← ShellFromChannel[handle.powerDistribution.power[top], bottom, parms.rules.branchLayer, horizRange, parms.rules];
leftObject ← ShellFromChannel[handle.powerDistribution.power[left], right, parms.rules.trunkLayer, vertRange, parms.rules];
rightObject ← ShellFromFullChannel[handle.detailedRouting.channels[top], left, parms.rules.trunkLayer, 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 ← RTBasic.IRSize[switchBox.object];
switchBox.cellType ← ExtractChannel[switchBox, parms]};
Shell Construction
MappedShellFromObject:
PROC [handle: CabbagePrivate.Handle,
objectDes: CabbagePrivate.ObjectDescription,
pinSide: Route.Side, -- the side of the object on which pins are to be considered
innerRange, outerRange: Connections.Range, -- innerRange is the span of the inner cell, outerRangethe span of the appropriate power routing cell
viaSize: INT, -- the size of the via alont the lenght of the cell
rules: Route.DesignRules]
RETURNS [shell: Cabbage.Object ← CDCells.CreateEmptyCell[]] ~ {
build a shell for inner edge of the outside channel and the outer edge of the power cell; input to PWRoute; pins are on the branch layer of rules (rules.branchLayer).
map signal pins outside outerRange to just inside outerRange
map Vdd and Gnd pins in outerRange to their same positions;
map only a single pin per wire outside innerRange but inside outerRange
EnterPowerOnInner: Connections.EachNetAction ~ {
PROC [key: Key, net: Net] RETURNS [quit: BOOLEAN ← FALSE]
store the power pins on the appropriate side of the inner object
EachSegment: Connections.EachSegmentAction ~ {
PROC [net: Net, segment: Segment] RETURNS [quit: BOOLEAN ← FALSE]
IF (segment.object = handle.inner.object
AND segment.side = otherSide)
AND (Rope.Equal[net.name, "Vdd"]
OR Rope.Equal[net.name, "Gnd"])
THEN
Insert[obstacles, [innerOrigin + segment.range.min, innerOrigin + segment.range.max], rules.branchToBranch]};
[] ← Connections.EnumerateSegments[net, EachSegment]};
EnterPowerOnOuter: Connections.EachNetAction ~ {
PROC [key: Key, net: Net] RETURNS [quit: BOOLEAN ← FALSE]
store the power pins on the appropriate side of the inner object
EachSegment: Connections.EachSegmentAction ~ {
PROC [net: Net, segment: Segment] RETURNS [quit: BOOLEAN ← FALSE]
IF (segment.object = objectDes.object
AND segment.side = pinSide)
AND (Rope.Equal[net.name, "Vdd"]
OR Rope.Equal[net.name, "Gnd"])
THEN
Insert[obstacles, [outerOrigin + segment.range.min, outerOrigin + segment.range.max], rules.branchToBranch]};
[] ← Connections.EnumerateSegments[net, EachSegment]};
EachOuterNet: Connections.EachNetAction ~ {
examine the nets on the outer object: objectDes
PROC [key: Key, net: Net] RETURNS [quit: BOOLEAN ← FALSE]
EachSegment: Connections.EachSegmentAction ~ {
keep the segments of interest on objectDes
PROC [net: Net, segment: Segment] RETURNS [quit: BOOLEAN ← FALSE]
IF (segment.object = objectDes.object
AND segment.side = pinSide)
THEN {
useThisPin: BOOLEAN ← TRUE;
newRange: Connections.Range;
powerNet: BOOLEAN ← Rope.Equal[net.name, "Vdd"] OR Rope.Equal[net. name, "Gnd"];
adjustedRange: Connections.Range ← [outerOrigin + segment.range.min, outerOrigin + segment.range.max];
IF ProperSubset[adjustedRange, outerRange]
THEN {
pin is within middle range
IF net = Vdd OR net = Gnd OR net has not been processed for this side THEN useThisPin
IF powerNet THEN newRange ← adjustedRange
ELSE
IF HashTable.Insert[netTable, net.name,
NIL]
THEN
newRange ← FindMiddleRange[adjustedRange, obstacles]
ELSE
IF ProperSubset[adjustedRange, [
FIRST[
INT], outerRange.min]]
THEN {
pin is within lower range
IF ~(net = Vdd OR net = Gnd) AND net has not been processed for this side THEN useThisPin
IF powerNet
THEN {
Cabbage.Signal[callingError, Rope.Cat[net.name, " pin on pad frame is in invalid position (within lower power bus corner)"]];
useThisPin ← FALSE}
ELSE
IF HashTable.Insert[netTable, net.name,
NIL]
THEN {
lowerRange: Connections.Range ← [outerRange.min, outerRange.min + (adjustedRange.max-adjustedRange.min)];
newRange ← FindLowerRange[lowerRange, obstacles]}
ELSE useThisPin ← FALSE}
ELSE
IF ProperSubset[adjustedRange, [outerRange.max,
LAST[
INT]]]
THEN {
pin is within upper range
IF ~(net = Vdd OR net = Gnd) AND net has not been processed for this side THEN useThisPin
IF powerNet
THEN {
Cabbage.Signal[callingError, Rope.Cat[net.name, " pin on pad frame is in invalid position (within upper power bus corner)"]];
useThisPin ← FALSE}
ELSE
IF HashTable.Insert[netTable, net.name,
NIL]
THEN {
upperRange: Connections.Range ← [outerRange.max - (adjustedRange.max-adjustedRange.min), outerRange.max];
newRange ← FindUpperRange[upperRange, obstacles]}
ELSE useThisPin ← FALSE}
ELSE {
Cabbage.Signal[callingError, Rope.Cat["Segment on net: ", net.name, " crosses boundary of power routing area"]];
useThisPin ← FALSE};
IF useThisPin
THEN {
denotes:
CD.Rect ←
SELECT pinSide
FROM
bottom => [newRange.min, oldIR.y2-rules.trunkWidth, newRange.max, oldIR.y2],
right => [oldIR.x1, newRange.min, oldIR.x1+rules.trunkWidth, newRange.max],
top => [newRange.min, oldIR.y1, newRange.max, oldIR.y1+rules.trunkWidth],
left => [oldIR.x2-rules.trunkWidth, newRange.min, oldIR.x2, newRange.max],
ENDCASE => Cabbage.Error[programmingError, "Not suppose to happen."];
IncludePin[object: shell, name: net.name, denotes: denotes, layer: rules.branchLayer];
IF ~powerNet
THEN
-- power nets were inserted first
Insert[obstacles, newRange, rules.branchToBranch];
}}};
[] ← Connections.EnumerateSegments[net, EachSegment]};
netTable: HashTable.Table ← HashTable.Create[equal: HashTable.RopeEqual, hash: HashTable.HashRope];
oldIR: CD.Rect ← CD.InterestRect[objectDes.object];
interestRect:
CD.Rect ←
SELECT pinSide
FROM
bottom, top => interestRect ← [outerRange.min, oldIR.y1, outerRange.max, oldIR.y2],
left, right => [oldIR.x1, outerRange.min, oldIR.x2, outerRange.max],
ENDCASE => Cabbage.Error[programmingError, "Not suppose to happen."];
otherSide: Route.Side ← RTBasic.OtherSide[pinSide];
innerOrigin:
INT ←
SELECT pinSide
FROM
bottom, top => handle.inner.origin.x,
right, left => handle.inner.origin.y,
ENDCASE => Cabbage.Error[programmingError, "Not suppose to happen."];
outerOrigin:
INT ←
SELECT pinSide
FROM
bottom, top => objectDes.origin.x,
right, left => objectDes.origin.y,
ENDCASE => Cabbage.Error[programmingError, "Not suppose to happen."];
insert obstacles for vias on end of power bus and at boundries of routing areas
all obstacles (pins, inner power publics, ...) are contained in a sorted table; the data is a Connections.Segment; the key is the origin, i.e. data.range.min
obstacles: BitTable ← CreateBitTable[outerRange.min, outerRange.max, rules.CDLambda];
Insert[obstacles, [outerRange.min, outerRange.min + viaSize], rules.branchToBranch];
Insert[obstacles, [outerRange.max - viaSize, outerRange.max], rules.branchToBranch];
Insert[obstacles, [innerRange.min - 3*rules.branchToBranch, innerRange.min + 3*rules.branchToBranch], rules.branchToBranch];
Insert[obstacles, [innerRange.max - 3*rules.branchToBranch, innerRange.max + 3*rules.branchToBranch], rules.branchToBranch];
process the inner power obstacles an the find places for the outer signals
[] ← Connections.EnumerateNets[handle.connections, EnterPowerOnInner];
[] ← Connections.EnumerateNets[handle.connections, EnterPowerOnOuter];
[] ← Connections.EnumerateNets[handle.connections, EachOuterNet];
CDCells.SetInterestRect[design: NIL, cell: shell, r: interestRect];
RTBasic.RepositionCell[shell]};
ShellFromOutsideEnd:
PROC [handle: CabbagePrivate.Handle,
objectDes: CabbagePrivate.ObjectDescription,
pinsOnSide, endOfChannel: Route.Side,
innerRange, outerRange: Connections.Range, -- the span along the appropriate padring cell
rules: Route.DesignRules]
RETURNS [shell: Cabbage.Object ← CDCells.CreateEmptyCell[]] ~ {
build a shell for end of the channel on the periprery; input to PWRoute
transfer pins on objectDes outside the range (on side endOfChannel) to shell.
pins go on rules.trunkLayer
EachNet: Connections.EachNetAction ~ {
PROC [key: Key, net: Net] RETURNS [quit: BOOLEAN ← FALSE]
EachSegment: Connections.EachSegmentAction ~ {
PROC [net: Net, segment: Segment] RETURNS [quit: BOOLEAN ← FALSE]
IF (segment.object = objectDes.object
AND segment.side = pinsOnSide)
THEN {
adjustedRange: Connections.Range ← [origin + segment.range.min, origin + segment.range.max];
IF CrossesBoundry[adjustedRange, interestingRange]
THEN
Cabbage.Signal[callingError, Rope.Cat["Segment on net: ", net.name, " crosses boundary of power routing areas"]];
IF ProperSubset[adjustedRange, interestingRange]
AND ~Member[net.name, netNameList]
THEN {
width: INT ← MAX[rules.trunkWidth, net.width];
dist ← dist + rules.trunkWidth;
SELECT endOfChannel
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;
netNameList ← CONS[net.name, netNameList];
dist ← dist + width}}};
[] ← Connections.EnumerateSegments[net, EachSegment]};
dist: INT ← rules.trunkWidth;
netNameList: LIST OF Rope.ROPE ← LIST["Vdd", "Gnd"]; -- pre load with power names
interestRect: CD.Rect;
interestingRange: Connections.Range ←
SELECT endOfChannel
FROM
left, bottom => [FIRST[INT], outerRange.min],
right, top => [outerRange.max, LAST[INT]],
ENDCASE => Cabbage.Error[programmingError, "Not suppose to happen."];
origin:
INT ←
SELECT pinsOnSide
FROM
bottom, top => objectDes.origin.x,
right, left => objectDes.origin.y,
ENDCASE => Cabbage.Error[programmingError, "Not suppose to happen."];
[] ← Connections.EnumerateNets[handle.connections, EachNet];
interestRect ←
SELECT endOfChannel
FROM
bottom, top => [0, 0, dist + rules.trunkWidth, 2*rules.trunkWidth],
left, right => [0, 0, 2*rules.trunkWidth, dist + 2*rules.trunkWidth],
ENDCASE => Cabbage.Error[programmingError, "Not suppose to happen"];
CDCells.SetInterestRect[design: NIL, cell: shell, r: interestRect];
RTBasic.RepositionCell[shell]};
ShellFromObject:
PROC [handle: CabbagePrivate.Handle,
objectDes: CabbagePrivate.ObjectDescription,
side: Route.Side, -- the side of the object on which pins are to be considered
range: Connections.Range, -- the span along objectDes to consider
rules: Route.DesignRules,
includePowerNets: BOOLEAN]
RETURNS [shell: Cabbage.Object ← CDCells.CreateEmptyCell[]] ~ {
build a shell for side of channel or switchbox; input to router
EachNet: Connections.EachNetAction ~ {
PROC [key: Key, net: Net] RETURNS [quit: BOOLEAN ← FALSE]
EachSegment: Connections.EachSegmentAction ~ {
PROC [net: Net, segment: Segment] RETURNS [quit: BOOLEAN ← FALSE]
IF (segment.object = objectDes.object
AND segment.side = side)
THEN {
adjustedRange: Connections.Range ← [origin + segment.range.min, origin + segment.range.max];
powerNet: BOOLEAN ← Rope.Equal[net.name, "Vdd"] OR Rope.Equal[net. name, "Gnd"];
IF CrossesBoundry[adjustedRange, range]
THEN
Cabbage.Signal[callingError, Rope.Cat["Segment on net: ", net.name, " crosses a boundary of the power routing areas"]];
IF ProperSubset[adjustedRange, range]
AND (includePowerNets
OR ~powerNet)
THEN {
SELECT side
FROM
bottom => IncludePin[object: shell, name: net.name, denotes: [adjustedRange.min, oldIR.y1, adjustedRange.max, oldIR.y1+rules.trunkWidth], layer: segment.layer];
right => IncludePin[object: shell, name: net.name, denotes: [oldIR.x2-rules.trunkWidth, adjustedRange.min, oldIR.x2, adjustedRange.max], layer: segment.layer];
top => IncludePin[object: shell, name: net.name, denotes: [adjustedRange.min, oldIR.y2-rules.trunkWidth, adjustedRange.max, oldIR.y2], layer: segment.layer];
left => IncludePin[object: shell, name: net.name, denotes: [oldIR.x1, adjustedRange.min, oldIR.x1+rules.trunkWidth, adjustedRange.max], layer: segment.layer];
ENDCASE}}};
[] ← Connections.EnumerateSegments[net, EachSegment]};
oldIR: CD.Rect ← CD.InterestRect[objectDes.object];
interestRect: CD.Rect;
origin:
INT ←
SELECT side
FROM
bottom, top => objectDes.origin.x,
right, left => objectDes.origin.y,
ENDCASE => Cabbage.Error[programmingError, "Not suppose to happen."];
[] ← Connections.EnumerateNets[handle.connections, EachNet];
interestRect ←
SELECT side
FROM
bottom, top => interestRect ← [range.min, oldIR.y1, range.max, oldIR.y2],
left, right => [oldIR.x1, range.min, oldIR.x2, range.max],
ENDCASE => Cabbage.Error[programmingError, "Not suppose to happen."];
CDCells.SetInterestRect[design: NIL, cell: shell, r: interestRect];
RTBasic.RepositionCell[shell]};
ShellFromEnd:
PROC [handle: CabbagePrivate.Handle, division: CabbagePrivate.Division, side: Route.Side, rules: Route.DesignRules]
RETURNS [shell: Cabbage.Object ← CDCells.CreateEmptyCell[]] ~ {
build a shell for end of channel; input to router
EachExit: EachExitAction ~ {
PROC [division: CabbagePrivate.Division, net: Connections.Net] RETURNS [quit: BOOLEAN ← FALSE];
IF ~(Rope.Equal[net.name, "Vdd"]
OR Rope.Equal[net. name, "Gnd"])
THEN {
width: INT ← MAX[rules.trunkWidth, net.width];
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: INT ← 0;
interestRect: CD.Rect;
[] ← EnumerateExits[handle.globalRouting.exitLists[division], division, EachExit];
interestRect ←
SELECT side
FROM
bottom, top => [0, 0, dist + rules.trunkWidth, 2*rules.trunkWidth],
left, right => [0, 0, 2*rules.trunkWidth, dist + rules.trunkWidth],
ENDCASE => Cabbage.Error[programmingError, "Not suppose to happen"];
CDCells.SetInterestRect[design: NIL, cell: shell, r: interestRect];
RTBasic.RepositionCell[shell]};
ShellFromFullChannel:
PROC [channel: CabbagePrivate.Channel, side: Route.Side, pinLayer:
CD.Layer, rules: Route.DesignRules]
RETURNS [shell: Cabbage.Object] ~ {
build a PWPins shell for the channel; use the full side of channel with pins on side
rect: CD.Rect ← CD.InterestRect[channel.object];
range: Connections.Range ←
SELECT side
FROM
bottom, top => [rect.x1, rect.x2],
left, right => [rect.y1, rect.y2],
ENDCASE => Cabbage.Error[programmingError, "Not suppose to happen"];
RETURN [ShellFromChannel[channel, side, pinLayer, range, rules]]};
ShellFromChannel:
PROC [channel: CabbagePrivate.Channel, pinSide: Route.Side, pinLayer:
CD.Layer, range: Connections.Range, rules: Route.DesignRules]
RETURNS [shell: Cabbage.Object ← CDCells.CreateEmptyCell[]] ~ {
build a PWPins shell for the channel; use the pins on side; range is the span along that side
ChanPublics: CoreGeometry.EachWirePinProc ~ {
PROC [wire: Wire, min, max: INT, side: Side, layer: CD.Layer] RETURNS [quit: BOOL ← FALSE];
add decoration for public; wire is an unbound wire
name: Rope.ROPE ← CoreOps.GetShortWireName[wire];
IF layer = pinLayer
THEN {
SELECT side
FROM
bottom => IF range.min <= rect.x1+max AND rect.x1+max <= range.max AND pinSide = bottom THEN IncludePin[object: shell, name: name, denotes: [rect.x1+min, rect.y1, rect.x1+max, rect.y1+depth], layer: layer];
right => IF range.min <= rect.y1+max AND rect.y1+max <= range.max AND pinSide = right THEN IncludePin[object: shell, name: name, denotes: [rect.x2-depth, rect.y1+min, rect.x2, rect.y1+max], layer: layer];
top => IF range.min <= rect.x1+max AND rect.x1+max <= range.max AND pinSide = top THEN IncludePin[object: shell, name: name, denotes: [rect.x1+min, rect.y2-depth, rect.x1+max, rect.y2], layer: layer];
left => IF range.min <= rect.y1+max AND rect.y1+max <= range.max AND pinSide = left THEN IncludePin[object: shell, name: name, denotes: [rect.x1, rect.y1+min, rect.x1+depth, rect.y1+max], layer: layer];
ENDCASE}};
mode: Sinix.Mode = SinixOps.GetExtractMode[rules.technology];
depth: Route.Number ← rules.trunkWidth;
rect: CD.Rect ← CD.InterestRect[channel.object];
newRect:
CD.Rect ←
SELECT pinSide
FROM
bottom, top => [range.min, rect.y1, range.max, rect.y2],
left, right => [rect.x1, range.min, rect.x2, range.max],
ENDCASE => Cabbage.Error[programmingError, "Not suppose to happen"];
[] ← CoreGeometry.EnumerateNonOverlappingSides[mode.decoration, channel.cellType, ChanPublics];
CDCells.SetInterestRect[design: NIL, cell: shell, r: newRect];
RTBasic.RepositionCell[shell]};
Utility Procedures
AdjustPositions:
PROC [handle: CabbagePrivate.Handle] ~ {
adjust the vertical and horizontal dimension
powerWidth: INT ← handle.parms.outerChanWidth + handle.parms.powerCellWidth;
routeType: CabbagePrivate.RouteType ← handle.routeType;
sizeBottomArea: INT ← handle.inner.origin.y - (handle.bottom.origin.y + handle.bottom.size.y);
sizeBottomRouting:
INT ← powerWidth + (
IF routeType = normal
THEN handle.detailedRouting.channels[bottom].size.y
ELSE handle.detailedRoutingPL.switchBoxes[bottom].size.y);
adjBottom: INT ← sizeBottomRouting - sizeBottomArea;
sizeLeftArea: INT ← handle.inner.origin.x - (handle.left.origin.x + handle.left.size.x);
sizeLeftRouting:
INT ← powerWidth + (
IF 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.origin ← CDBasics.AddPoints[handle.inner.origin, [MAX[0, adjLeft], MAX[0, adjBottom]]];
handle.bottom.origin ← CDBasics.AddPoints[handle.bottom.origin, [MAX[0, adjLeft], 0]];
handle.right.origin ← CDBasics.AddPoints[handle.right.origin, [MAX[0, adjLeft], MAX[0, adjBottom]]];
handle.top.origin ← CDBasics.AddPoints[handle.top.origin, [MAX[0, adjLeft], MAX[0, adjBottom]]];
handle.left.origin ← CDBasics.AddPoints[handle.left.origin, [0, MAX[0, adjBottom]]];
sizeTopArea ← handle.top.origin.y - (handle.inner.origin.y + handle.inner.size.y);
sizeTopRouting ← powerWidth + (
IF routeType = normal
THEN handle.detailedRouting.channels[top].size.y
ELSE handle.detailedRoutingPL.switchBoxes[top].size.y);
adjTop ← sizeTopRouting - sizeTopArea;
sizeRightArea ← handle.right.origin.x - (handle.inner.origin.x + handle.inner.size.x);
sizeRightRouting ← powerWidth + (
IF routeType = normal
THEN handle.detailedRouting.channels[right].size.x
ELSE handle.detailedRoutingPL.channels[right].size.x);
adjRight ← sizeRightRouting - sizeRightArea;
handle.top.origin ← CDBasics.AddPoints[handle.top.origin, [0, MAX[0, adjTop]]];
handle.right.origin ← CDBasics.AddPoints[handle.right.origin, [MAX[0, adjRight], 0]];
[] ← GetSize[handle];
DoCorners[handle];
DoRoutingAreas[handle]};
IncludeObject:
PROC [object: Cabbage.Object, origin:
CD.Position, chip: Cabbage.Object] ~ {
IF object #
NIL
THEN
[] ← RouteUtil.Include[cell: chip, ob: object, position: CDOps.FitObjectI[ob: object, location: origin, orientation: original].off, orientation: original]};
ExtractChannel:
PROC [channel: CabbagePrivate.Channel, parms: CabbagePrivate.ParmSet]
RETURNS [cellType: Core.CellType] ~ {
extract connectivity for the channel
mode: Sinix.Mode = SinixOps.GetExtractMode[parms.rules.technology];
cellType ← NARROW [Sinix.Extract[channel.object, mode].result]};
Find the position of a segment projected to the periphery. The lower left corner is the origin.
PosOf:
PROC [handle: CabbagePrivate.Handle, segment: Connections.Segment]
RETURNS [
INT] ~ {
range: Connections.Range ← RangeOf[handle, segment];
RETURN[(range.min+range.max)/2]};
Find the range of a segment projected to the periphery. The lower left corner is the origin.
RangeOf:
PROC [handle: CabbagePrivate.Handle, segment: Connections.Segment]
RETURNS [range: Connections.Range] ~ {
range ←
SELECT
TRUE
FROM
segment.object = handle.inner.object => InnerRange[handle, segment],
segment.object = handle.bottom.object => range ← OuterRange[handle, segment],
segment.object = handle.right.object => OuterRange[handle, segment],
segment.object = handle.top.object => OuterRange[handle, segment],
segment.object = handle.left.object => OuterRange[handle, segment],
segment.object = handle.powerDistribution.power[bottom].object => PowerRange[handle, segment],
segment.object = handle.powerDistribution.power[right].object => PowerRange[handle, segment],
segment.object = handle.powerDistribution.power[top].object => PowerRange[handle, segment],
segment.object = handle.powerDistribution.power[left].object => PowerRange[handle, segment],
ENDCASE => Cabbage.Error[callingError, Rope.Cat["Invalid object in segment: ", segment.name]]};
InnerRange:
PROC [handle: CabbagePrivate.Handle, segment: Connections.Segment]
RETURNS [range: Connections.Range] ~ {
SELECT segment.side
FROM
bottom =>
{origin: INT ← handle.inner.origin.x;
range ← [origin + segment.range.min, origin + segment.range.max]};
right =>
{origin: INT ← handle.size.x + handle.inner.origin.y;
range ← [origin + segment.range.min, origin + segment.range.max]};
top =>
{origin: INT ← handle.size.x +handle.size.y + (handle.size.x - handle.inner.origin.x);
range ← [origin - segment.range.max, origin - segment.range.min]};
left =>
{origin: INT ← 2*handle.size.x +handle.size.y + (handle.size.y - handle.inner.origin.y);
range ← [origin - segment.range.max, origin - segment.range.min]};
ENDCASE};
OuterRange:
PROC [handle: CabbagePrivate.Handle, segment: Connections.Segment]
RETURNS [range: Connections.Range] ~ {
SELECT RTBasic.OtherSide[segment.side]
FROM
bottom =>
{origin: INT ← handle.bottom.origin.x;
range ← [origin + segment.range.min, origin + segment.range.max]};
right =>
{origin: INT ← handle.size.x + handle.right.origin.y;
range ← [origin + segment.range.min, origin + segment.range.max]};
top =>
{origin: INT ← handle.size.x +handle.size.y + (handle.size.x - handle.top.origin.x);
range ← [origin - segment.range.max, origin - segment.range.min]};
left =>
{origin: INT ← 2*handle.size.x +handle.size.y + (handle.size.y - handle.left.origin.y);
range ← [origin - segment.range.max, origin - segment.range.min]};
ENDCASE};
PowerRange:
PROC [handle: CabbagePrivate.Handle, segment: Connections.Segment]
RETURNS [range: Connections.Range] ~ {
SELECT RTBasic.OtherSide[segment.side]
FROM
bottom =>
{origin: INT ← handle.powerDistribution.power[bottom].origin.x;
range ← [origin + segment.range.min, origin + segment.range.max]};
right =>
{origin: INT ← handle.size.x + handle.powerDistribution.power[right].origin.y;
range ← [origin + segment.range.min, origin + segment.range.max]};
top =>
{origin: INT ← handle.size.x +handle.size.y + (handle.size.x - handle.powerDistribution.power[top].origin.x);
range ← [origin - segment.range.max, origin - segment.range.min]};
left =>
{origin: INT ← 2*handle.size.x +handle.size.y + (handle.size.y - handle.powerDistribution.power[left].origin.y);
range ← [origin - segment.range.max, origin - segment.range.min]};
ENDCASE};
PosOfDivision:
PROC [handle: CabbagePrivate.Handle, division: CabbagePrivate.Division]
RETURNS [pos:
INT] ~ {
SELECT division
FROM
bottomLeft => pos ← handle.inner.origin.x;
bottomRight => pos ← handle.inner.origin.x + handle.inner.size.x;
rightBottom => pos ← handle.size.x + handle.inner.origin.y;
rightTop => pos ← handle.size.x + handle.inner.origin.y + handle.inner.size.y;
topRight => pos ← handle.size.x +handle.size.y + (handle.size.x - handle.inner.origin.x - handle.inner.size.x);
topLeft => pos ← handle.size.x +handle.size.y + (handle.size.x - handle.inner.origin.x);
leftTop => pos ← 2*handle.size.x +handle.size.y + (handle.size.y - handle.inner.origin.y - handle.inner.size.y);
leftBottom => pos ← 2*handle.size.x +handle.size.y + (handle.size.y - handle.inner.origin.y);
ENDCASE};
EachExitAction:
TYPE =
PROC [division: CabbagePrivate.Division, net: Connections.Net]
RETURNS [quit:
BOOLEAN ←
FALSE];
EnumerateExits:
PROC [exitList: CabbagePrivate.ExitList, division: CabbagePrivate.Division, eachExitAction: EachExitAction]
RETURNS [quit:
BOOLEAN ←
FALSE] ~ {
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;
powerWidth: INT ← handle.parms.outerChanWidth + handle.parms.powerCellWidth;
IF handle.routeType = normal
THEN {
vMiddle ← handle.bottom.size.y + powerWidth + handle.detailedRouting.channels[bottom].size.y + handle.inner.size.y + handle.detailedRouting.channels[top].size.y + powerWidth + handle.top.size.y;
hMiddle ← handle.left.size.x + powerWidth + handle.detailedRouting.channels[left].size.x + handle.inner.size.x + handle.detailedRouting.channels[right].size.x + powerWidth + handle.right.size.x}
ELSE {
hCenter: INT ← powerWidth + handle.detailedRoutingPL.channels[left].size.x + handle.inner.size.x + handle.detailedRoutingPL.channels[right].size.x + powerWidth;
hInner: INT ← MAX[hCenter, handle.detailedRoutingPL.switchBoxes[top].size.x, handle.detailedRoutingPL.switchBoxes[bottom].size.x];
vInner: INT ← powerWidth + handle.detailedRoutingPL.switchBoxes[bottom].size.y + handle.inner.size.y + handle.detailedRoutingPL.switchBoxes[top].size.y + powerWidth;
vMiddle ← handle.bottom.size.y + vInner + 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.origin ← [0, 0];
handle.bottomRight.origin ← [handle.size.x - handle.bottomRight.size.x, 0];
handle.topRight.origin ← [handle.size.x - handle.topRight.size.x, handle.size.y - handle.topRight.size.y];
handle.topLeft.origin ← [0, handle.size.y - handle.topLeft.size.y]};
DoRoutingAreas:
PROC [handle: CabbagePrivate.Handle] ~ {
outerChanWidth: INT ← handle.parms.outerChanWidth;
powerWidth: INT ← outerChanWidth + handle.parms.powerCellWidth;
routeType: CabbagePrivate.RouteType ← handle.routeType;
short hand to make the following easier to understand
leftInterior: INT ← handle.left.origin.x + handle.left.size.x; -- right of left pads
rightInterior: INT ← handle.right.origin.x; -- left of right pads
bottomInterior: INT ← handle.bottom.origin.y + handle.bottom.size.y; -- top of bottom pads
topInterior: INT ← handle.top.origin.y; -- bottom of top pads
leftOfInner: INT ← handle.inner.origin.x; -- left of inner object
rightOfInner: INT ← handle.inner.origin.x + handle.inner.size.x; -- right of inner object
bottomOfInner: INT ← handle.inner.origin.y; -- bottom of inner object
topOfInner: INT ← handle.inner.origin.y + handle.inner.size.y; -- top of inner object
IF routeType = normal
THEN {
handle.detailedRouting.channels[bottom].origin ← [leftOfInner, bottomOfInner - handle.detailedRouting.channels[bottom].size.y];
handle.detailedRouting.channels[right].origin ← [rightOfInner, bottomOfInner];
handle.detailedRouting.channels[top].origin ← [leftOfInner, topOfInner];
handle.detailedRouting.channels[left].origin ← [leftOfInner - handle.detailedRouting.channels[left].size.x, bottomOfInner];
handle.detailedRouting.switchBoxes[bottomLeft].origin ← [leftInterior + powerWidth, bottomInterior + powerWidth];
handle.detailedRouting.switchBoxes[bottomRight].origin ← [rightOfInner, bottomInterior + powerWidth];
handle.detailedRouting.switchBoxes[topRight].origin ← [rightOfInner, topOfInner];
handle.detailedRouting.switchBoxes[topLeft].origin ← [leftInterior + powerWidth, topOfInner]}
ELSE {
-- routeType = padLimited
handle.detailedRoutingPL.channels[right].origin ← [rightOfInner, bottomOfInner];
handle.detailedRoutingPL.channels[left].origin ← [leftOfInner - handle.detailedRoutingPL.channels[left].size.x, bottomOfInner];
handle.detailedRoutingPL.switchBoxes[bottom].origin ← [leftInterior + powerWidth, bottomInterior + powerWidth];
handle.detailedRoutingPL.switchBoxes[top].origin ← [leftInterior + powerWidth, topOfInner]};
the outside routing channels
handle.powerDistribution.channels[bottom].origin ← [leftInterior + powerWidth, bottomInterior];
handle.powerDistribution.channels[right].origin ← [rightInterior - outerChanWidth, bottomInterior + powerWidth];
handle.powerDistribution.channels[top].origin ← [leftInterior + powerWidth, topInterior - outerChanWidth];
handle.powerDistribution.channels[left].origin ← [leftInterior, bottomInterior + powerWidth];
the power channels
handle.powerDistribution.power[bottom].origin ← [leftInterior + powerWidth, bottomInterior + outerChanWidth];
handle.powerDistribution.power[right].origin ← [rightInterior - powerWidth, bottomInterior + powerWidth];
handle.powerDistribution.power[top].origin ← [leftInterior + powerWidth, topInterior - powerWidth];
handle.powerDistribution.power[left] .origin← [leftInterior + outerChanWidth, bottomInterior + powerWidth];
the outside corners
handle.powerDistribution.switchBoxes[bottomLeft].origin ← [leftInterior, bottomInterior];
handle.powerDistribution.switchBoxes[bottomRight].origin ← [rightInterior - powerWidth, bottomInterior];
handle.powerDistribution.switchBoxes[topRight].origin ← [rightInterior - powerWidth, topInterior - powerWidth];
handle.powerDistribution.switchBoxes[topLeft].origin ← [leftInterior, topInterior - powerWidth]};
IncludePin:
PROC [object:
CD.Object, name: Rope.
ROPE, denotes:
CD.Rect, layer:
CD.Layer] ~ {
include a pin(name, denotes, layer) in an object
properties are use to pass position info because of restrictions in PWPins
pin: CD.Object ← CDSymbolicObjects.CreatePin[CDBasics.SizeOfRect[denotes]];
pinInstance: CD.Instance ← RouteUtil.Include[cell: object, ob: pin, position: CDBasics.BaseOfRect[denotes], orientation: original];
CDProperties.PutInstanceProp[pinInstance, cabbageXPos, NEW[INT ← denotes.x1]];
CDProperties.PutInstanceProp[pinInstance, cabbageYPos, NEW[INT ← denotes.y1]];
CDSymbolicObjects.SetName[pinInstance, name];
CDSymbolicObjects.SetLayer[pinInstance, layer]};
Member:
PROC [item: Rope.
ROPE, list:
LIST
OF Rope.
ROPE]
RETURNS [
BOOLEAN] ~ {
Return TRUE if item is on list
UNTIL list =
NIL
DO
IF Rope.Equal[list.first, item] THEN RETURN [TRUE];
list ← list.rest;
ENDLOOP;
RETURN [FALSE]};
Obstacle manipulation Procedures...
-- Assertion: obstacles do not overlap: if you insert a new obstacle and it overlaps an existing one in the table, the two are fused and the resulting union is put in the table; this should be maintained at all time
-- The table contains the projection of the pins with the design rule space on each side
BitTable: TYPE = REF BitTableRec;
BitTableRec:
TYPE =
RECORD[
bitSize: NAT ← 8, -- CD.Number per lambdas
min, max: INT ← 0, -- outerRange
bits: PACKED SEQUENCE size: NAT OF BOOL]; -- TRUE=busy
-- [outerRange.min..outerRange.max] must map into [0..obstacles.size-1]
Translate:
PROC [obstacles: BitTable, pos:
INT]
RETURNS [bitIndex:
NAT] ~
INLINE {
bitIndex ← (pos-obstacles.min)/obstacles.bitSize;
IF bitIndex NOT IN [0..obstacles.size) THEN ERROR};
CreateBitTable:
PROC [min, max: INT, bitSize:
NAT]
RETURNS [bitTable: BitTable] ~ {
size: NAT ← (max/bitSize)-(min/bitSize)+1;
bitTable ← NEW[BitTableRec[size]];
bitTable.bitSize ← bitSize;
bitTable.min ← min;
bitTable.max ← max;
FOR i:
NAT
IN [0..size)
DO
bitTable[i] ← FALSE;
ENDLOOP};
PositionOccupied:
PROC [obstacles: BitTable, pos:
INT]
RETURNS [
BOOL] ~
INLINE {
RETURN[obstacles[Translate[obstacles, pos]]]};
-- Assertion: pos must be in (obstacles.min..obstacles.max)!!!
NextPos:
PROC [obstacles: BitTable, from:
INT, goingUp:
BOOL]
RETURNS [next:
INT] ~
INLINE {
next ← IF goingUp THEN from+1 ELSE from-1};
Edge:
PROC [obstacles: BitTable, goingUp:
BOOL]
RETURNS [pos:
INT] ~
INLINE {
pos ← IF goingUp THEN obstacles.max ELSE obstacles.min};
SetOccupied:
PROC [obstacles: BitTable, pos:
INT] ~
INLINE {
IF pos NOT IN [obstacles.min..obstacles.max] THEN RETURN;
obstacles[Translate[obstacles, pos]] ← TRUE};
-- Bloat range by a spacing on each side on insertion; there is space here, you know it!
Insert:
PROC [obstacles: BitTable, range: Connections.Range, spacing:
INT] ~ {
FOR pos:
INT
IN [range.min-spacing..range.max+spacing]
DO
SetOccupied[obstacles, pos];
ENDLOOP};
-- when isFree, then nextTry=range.min
-- range must be valid (within outerRange)
IsFree:
PROC [range: Connections.Range, obstacles: BitTable, goingUp:
BOOL]
RETURNS [isFree:
BOOL, nextTry:
INT] ~ {
FOR pos:
INT
IN [range.min..range.max]
DO
IF PositionOccupied[obstacles, pos] THEN RETURN[FALSE, FindNextFree[obstacles, pos, goingUp]];
ENDLOOP;
RETURN[TRUE, range.min]};
FindNextFree:
PROC [obstacles: BitTable, from:
INT, goingUp:
BOOL]
RETURNS [free:
INT] ~ {
free ← from;
WHILE PositionOccupied[obstacles, free]
AND free#Edge[obstacles, goingUp]
DO
free ← NextPos[obstacles, free, goingUp];
ENDLOOP};
FindLowerRange:
PROC [adjustedRange: Connections.Range, obstacles: BitTable]
RETURNS [newRange: Connections.Range] ~ {
find a neRange were pin is not hidden by a pin in obstacles and does not interfere with existing pin
pin should be close to outerRange.min
isFree: BOOL ← FALSE;
nextTry: INT;
newRange ← adjustedRange;
WHILE ~isFree
DO
[isFree, nextTry] ← IsFree[newRange, obstacles, TRUE];
IF nextTry>=obstacles.max THEN Cabbage.Signal[noResource, "No space for pin on power bus side."];
newRange ← [nextTry + obstacles.bitSize, nextTry + obstacles.bitSize + (adjustedRange.max-adjustedRange.min)]; -- noop if isFree
ENDLOOP};
FindUpperRange:
PROC [adjustedRange: Connections.Range, obstacles: BitTable]
RETURNS [newRange: Connections.Range] ~ {
find a newRange were pin is not hidden by a pin in obstacles and does not interfere with existing pin
pin should be close to outerRange.max
isFree: BOOL ← FALSE;
nextTry: INT;
newRange ← adjustedRange;
WHILE ~isFree
DO
[isFree, nextTry] ← IsFree[newRange, obstacles, FALSE];
IF nextTry<=obstacles.min THEN Cabbage.Signal[noResource, "No space for pin on power bus side."];
newRange ← [nextTry - obstacles.bitSize - (adjustedRange.max-adjustedRange.min), nextTry - obstacles.bitSize]; -- noop if isFree
ENDLOOP};
FindMiddleRange:
PROC [adjustedRange: Connections.Range, obstacles: BitTable]
RETURNS [newRange: Connections.Range] ~ {
find a neRange were pin is not hidden by a pin in obstacles and does not interfere with existing pin
IF IsFree[adjustedRange, obstacles, FALSE].isFree THEN RETURN[adjustedRange]
ELSE {
fellOffLower, fellOffUpper: BOOL ← FALSE;
lower, upper: Connections.Range; -- CEDAR Bug! Signals in initialization
upper ← FindLowerRange[adjustedRange, obstacles ! Cabbage.Signal => IF errorType=noResource THEN {fellOffUpper ← TRUE; CONTINUE}];
lower ← FindUpperRange[adjustedRange, obstacles ! Cabbage.Signal => IF errorType=noResource THEN {fellOffLower ← TRUE; CONTINUE}];
IF fellOffUpper AND fellOffLower THEN Cabbage.Signal[noResource, "No space for pin on power bus side."];
IF fellOffUpper THEN RETURN[lower];
IF fellOffLower THEN RETURN[upper];
IF adjustedRange.min-lower.min<upper.min-adjustedRange.min THEN RETURN[lower];
RETURN[upper]}};