RouteChannelInitImpl.mesa
Copyright Ó 1985, 1987, 1988 by Xerox Corporation. All rights reserved.
by Bryan Preas July 10, 1985 6:57:00 pm PDT
last edited by Bryan Preas July 26, 1988 5:24:09 pm PDT
Christian Le Cocq January 19, 1988 9:52:19 am PST
DIRECTORY
Basics, CD, CDBasics, DABasics, List, Rope, Route, RouteChannel, RoutePrivate, RouteUtil, RTBasic;
RouteChannelInitImpl:
CEDAR
PROGRAM
IMPORTS CDBasics, List, Rope, Route, RouteChannel, RouteUtil, RTBasic
EXPORTS RouteChannel = {
ChanSideName: PUBLIC ARRAY RouteChannel.ChanSide OF Rope.ROPE ← ["chanBottom", "chanTop", "chanLeft", "chanRight"];
AboveOrBelowName: PUBLIC ARRAY RouteChannel.AboveOrBelow OF Rope.ROPE ← ["above", "below"];
GoingName:
PUBLIC
ARRAY RouteChannel.GoingDirection
OF Rope.
ROPE ← ["leftToRight", "rightToLeft"];
InitChannel:
PUBLIC
PROC [extSidesData: RoutePrivate.RoutingAreaSides,
parms: RoutePrivate.RoutingAreaParms,
rules: Route.DesignRules,
netTab: RoutePrivate.NetTab,
signalSinglePinNets,
signalCoincidentPins,
okToDiddleLLPins,
okToDiddleURPins: BOOLEAN]
RETURNS [chanData: RouteChannel.ChannelData] = {
Initialize for channel routing
nRect: DABasics.Rect ← CDBasics.ReInterpreteRect[parms.routingRect];
lowPos: RTBasic.PQPos ← RouteUtil.XYToPQ[rules, [nRect.x1, nRect.y1]];
upPos: RTBasic.PQPos ← RouteUtil.XYToPQ[rules, [nRect.x2, nRect.y2]];
rRect: RTBasic.PQRect ← [lowPos, upPos];
build the channel routing area; privatePart.constraints initialized in RouteChannelConstraintsImpl
chanData ← NEW[RouteChannel.ChannelDataRec];
chanData.constraints ← NIL;
chanData.chanSides[chanTop] ← NEW[RouteChannel.RoutingChannelSidesRec];
chanData.chanSides[chanBottom] ← NEW[RouteChannel.RoutingChannelSidesRec];
chanData.chanSides[chanLeft] ← NEW[RouteChannel.RoutingChannelSidesRec];
chanData.chanSides[chanRight] ← NEW[RouteChannel.RoutingChannelSidesRec];
chanData.chanTracks ← NEW[RouteChannel.RoutingChannelTracksRec];
chanData.chanPins ← NEW[RouteChannel.RoutingChannelPinsRec];
chanData.chanParms ← NEW[RouteChannel.ChanParmsRec];
chanData.chanParms.emptyTrackLimit ← MAX[2, RouteChannel.InfluenceTracks[rules, parms.widestTrunk]];
chanData.chanParms.maxToConvert ← 10*rules.branchToBranch;
convert sides to p-q space and build side data structures
ConvertSide[chanData, extSidesData, rules, chanBottom, rRect];
ConvertSide[chanData, extSidesData, rules, chanTop, rRect];
ConvertEnd[chanData, extSidesData, rules, chanLeft, rRect];
ConvertEnd[chanData, extSidesData, rules, chanRight, rRect];
fix up the routing area orgins
FixOrigins[chanData, rRect];
convert the nets from x-y space to p-q space
FOR netIndex: RoutePrivate.ZMaxNets
IN [1 .. netTab.count]
DO
InitNet[chanData, parms, rules, netTab, netTab.n[netIndex], signalSinglePinNets, signalCoincidentPins];
ENDLOOP;
SELECT parms.routerUsed
FROM
switchBox => MakeSBTracks[chanData, rules, okToDiddleLLPins, okToDiddleURPins];
channel => MakeCRTracks[chanData.chanTracks, rules, parms.numTracksToUse];
ENDCASE => ERROR; --may be channel should be the default ?
IF parms.routerUsed = switchBox THEN MakeSBTracks[routingArea, okToDiddleLLPins, okToDiddleURPins]
ELSE MakeCRTracks[routingArea, parms.numTracksToUse];
DoTBBarriers[chanData, parms, rules, chanBottom];
DoTBBarriers[chanData, parms, rules, chanTop];
DoLRBarriers[chanData, chanLeft];
DoLRBarriers[chanData, chanRight];
};
ConvertSide:
PROC [chanData: RouteChannel.ChannelData,
extSidesData: RoutePrivate.RoutingAreaSides,
rules: Route.DesignRules,
chanSide: RouteChannel.ChanSide,
routingRect: RTBasic.PQRect] = {
Convert a channel side to p-q space and set up side data
activeSide: RouteChannel.RoutingChannelSides ← chanData.chanSides[chanSide];
chanPins: RouteChannel.RoutingChannelPins ← chanData.chanPins;
extSide: DABasics.Side ← RouteChannel.IntSideToExtSide[rules, chanSide];
extSideData: RoutePrivate.RoutingAreaSide ← extSidesData[extSide];
activeSide.enclosingBarrier ← [[0, 0], [0, 0]];
activeSide.extSide ← extSide;
chanPins.cEnd1 ← routingRect.c1.p; chanPins.cEnd2 ← routingRect.c2.p;
IF extSideData #
NIL
THEN {
encloseBranch: RTBasic.PQRect ← TranslateBarriers[extSidesData, rules, activeSide, branch];
encloseTrunk: RTBasic.PQRect ← TranslateBarriers[extSidesData, rules, activeSide, trunk];
activeSide.enclosingBarrier ← Surround[encloseBranch, encloseTrunk];
};
};
TranslateBarriers:
PROC [extSidesData: RoutePrivate.RoutingAreaSides,
rules: Route.DesignRules,
activeSide: RouteChannel.RoutingChannelSides,
rLayer: RoutePrivate.RoutingLayer]
RETURNS [enclosingRect: RTBasic.PQRect ← [[0, 0], [0, 0]]] = {
convert routing barriers for a side
extSide: DABasics.Side ← activeSide.extSide;
extSideData: RoutePrivate.RoutingAreaSide ← extSidesData[extSide];
chanDirection: DABasics.Direction ← rules.trunkDirection;
IF extSideData #
NIL
THEN {
FOR bList: RoutePrivate.RoutingBarrierList ← extSideData.barrierList, bList.rest
WHILE bList #
NIL
DO
barrierItem: RoutePrivate.RoutingBarrier ← bList.first;
generalLayer: CD.Layer ← barrierItem.layer;
IF generalLayer =
CD.undefLayer
OR RouteUtil.LayerToRoutingLayer[rules, generalLayer] = rLayer
THEN {
FOR rList:
LIST
OF DABasics.Rect ← barrierItem.barrier, rList.rest
WHILE rList #
NIL
DO
cleanRectangle: RTBasic.PQRectRef ← CheckRect[rules, rList.first, activeSide];
IF cleanRectangle #
NIL
THEN {
enclosingRect ← Surround[enclosingRect, cleanRectangle^];
activeSide.barrierList[rLayer] ← CONS[cleanRectangle^, activeSide.barrierList[rLayer]]};
ENDLOOP;
}
ENDLOOP;
};
};
CheckRect:
PROC [rules: Route.DesignRules, rect: DABasics.Rect, activeSide: RouteChannel.RoutingChannelSides]
RETURNS[cleanRect: RTBasic.PQRectRef] = {
clean up the rectangle and return it.
*** CHECK THAT PROC... ***
chanDirection: DABasics.Direction ← rules.trunkDirection;
c1: RTBasic.PQPos ← RouteUtil.XYToPQ[rules, [rect.x1, rect.y1]];
c2: RTBasic.PQPos ← RouteUtil.XYToPQ[rules, [rect.x2, rect.y2]];
RETURN[NEW[RTBasic.PQRect ← [c1, c2]]];
};
ConvertEnd:
PROC [chanData: RouteChannel.ChannelData,
extSidesData: RoutePrivate.RoutingAreaSides,
rules: Route.DesignRules,
chanSide: RouteChannel.ChanSide,
routingRect: RTBasic.PQRect] = {
convert a channel end to p-q space and set up side data
activeSide: RouteChannel.RoutingChannelSides ← chanData.chanSides[chanSide];
extSide: DABasics.Side ← RouteChannel.IntSideToExtSide[rules, chanSide];
extSideData: RoutePrivate.RoutingAreaSide ← extSidesData[extSide];
activeSide.extSide ← extSide;
activeSide.enclosingBarrier ← [[0, 0], [0, 0]];
IF extSideData #
NIL
THEN {
encloseBranch: RTBasic.PQRect ← TranslateBarriers[extSidesData, rules, activeSide, branch];
encloseTrunk: RTBasic.PQRect ← TranslateBarriers[extSidesData, rules, activeSide, trunk];
activeSide.enclosingBarrier ← Surround[encloseBranch, encloseTrunk];
};
};
FixOrigins:
PROC [chanData: RouteChannel.ChannelData, routingRect: RTBasic.PQRect] = {
now that all side data is available, compute the routing area
chanPins: RouteChannel.RoutingChannelPins ← chanData.chanPins;
leftSide: RouteChannel.RoutingChannelSides ← chanData.chanSides[chanLeft];
rightSide: RouteChannel.RoutingChannelSides ← chanData.chanSides[chanRight];
bottomSide: RouteChannel.RoutingChannelSides ← chanData.chanSides[chanBottom];
topSide: RouteChannel.RoutingChannelSides ← chanData.chanSides[chanTop];
zero: DABasics.Number ← 0; -- don't laugh
fix up the routing area
leftSide.routeAreaCoord ← chanPins.cEnd1;
rightSide.routeAreaCoord ← chanPins.cEnd2;
chanPins.cEnd1 ← chanPins.cEnd1 + MAX[zero, leftSide.enclosingBarrier.c2.p];
chanPins.cEnd2 ← chanPins.cEnd2 + MAX[zero, rightSide.enclosingBarrier.c1.p];
bottomSide.routeAreaCoord ← routingRect.c1.q;
topSide.routeAreaCoord ← routingRect.c2.q;
};
InitNet:
PROC [chanData: RouteChannel.ChannelData,
parms: RoutePrivate.RoutingAreaParms,
rules: Route.DesignRules,
netTab: RoutePrivate.NetTab,
net: RoutePrivate.Net,
signalSinglePinNets, signalCoincidentPins: BOOLEAN] = {
Initialize for channel routing
PPinCompare: List.CompareProc = {
p1: DABasics.Number ← NARROW[ref1, RouteChannel.InternPin].location.p;
p2: DABasics.Number ← NARROW[ref2, RouteChannel.InternPin].location.p;
RETURN[
IF p1 < p2
THEN Basics.Comparison.less
ELSE IF p1 = p2 THEN Basics.Comparison.equal
ELSE Basics.Comparison.greater];
};
mungedPinList, sortedPinList: List.LORA;
chanDirection: DABasics.Direction ← routingArea.rules.trunkDirection;
chanPins: RouteChannel.RoutingChannelPins ← chanData.chanPins;
net.internPinList ← FixPins[chanData, parms, rules, net.pinList];
mungedPinList ← ConvertToLORA[NARROW[net.internPinList]];
sortedPinList ← List.Sort[mungedPinList, PPinCompare];
IF CheckChanPins[chanPins, rules, netTab, net, sortedPinList, signalSinglePinNets, signalCoincidentPins]
THEN
BuildChanPinForDogleg[chanPins, parms, rules, net, sortedPinList]; -- Multiple segments per net
BuildChanPin[chanPins, parms, rules, net, sortedPinList]; -- Single segments per net
};
FixPins:
PROC [chanData: RouteChannel.ChannelData,
parms: RoutePrivate.RoutingAreaParms,
rules: Route.DesignRules,
pList: Route.PinList]
RETURNS [fixedPins: -- List.LORA ← NIL -- RouteChannel.InternPinList ← NIL ] = {
Translate the pin coordinates from x-y space to p-q space.
chanPins: RouteChannel.RoutingChannelPins ← chanData.chanPins;
routingRect: DABasics.Rect ← parms.routingRect;
FOR list: Route.PinList ← pList, list.rest
WHILE list #
NIL
DO
old: Route.Pin ← list.first;
loc: RTBasic.PQPos;
new: RouteChannel.InternPin;
chanSide: RouteChannel.ChanSide ← RouteChannel.ExtSideToIntSide[rules, old.side];
activeSide: RouteChannel.RoutingChannelSides ← chanData.chanSides[chanSide];
rLayer: RoutePrivate.RoutingLayer ← RouteUtil.LayerToRoutingLayer[rules, old.layer];
width: DABasics.Number ← old.max - old.min;
oldLoc: DABasics.Position ←
SELECT old.side
FROM
bottom => [old.min + width/2, routingRect.y1 - old.depth],
top => [old.min + width/2, routingRect.y2 + old.depth],
left => [routingRect.x1 - old.depth, old.min + width/2],
right => [routingRect.x2 + old.depth, old.min + width/2],
ENDCASE => Route.Error[programmingError, "not suppose to happen."];
SELECT chanSide
FROM
chanBottom, chanTop => {
loc ← RouteUtil.XYToPQ[rules, oldLoc];
loc.q ← loc.q - activeSide.routeAreaCoord};
chanLeft => {
SELECT parms.routerUsed
FROM
channel => {
loc ← [chanPins.cEnd1, 0];
width ← 0;
};
switchBox => {
loc ← RouteUtil.XYToPQ[rules, oldLoc];
loc.p ← chanPins.cEnd1};
ENDCASE => ERROR;
};
chanRight => {
SELECT parms.routerUsed
FROM
channel => {
loc ← [chanPins.cEnd2, 0];
width ← 0;
};
switchBox => {
loc ← RouteUtil.XYToPQ[rules, oldLoc];
loc.p ← chanPins.cEnd2;
};
ENDCASE => ERROR;
};
ENDCASE;
new ← NEW[RouteChannel.InternPinRec ← [NIL, chanSide, loc, width, rLayer, old]];
fixedPins ← CONS[new, fixedPins];
ENDLOOP;
CheckChanPins:
PROC [chanPins: RouteChannel.RoutingChannelPins,
rules: Route.DesignRules,
netTab: RoutePrivate.NetTab,
net: RoutePrivate.Net,
pinList: List.LORA -- RouteChannel.InternPinList --,
signalSinglePinNets, signalCoincidentPins: BOOLEAN]
RETURNS [ok: BOOLEAN ← TRUE] = {
Check the pins for this net.
-- number of pins > 1
-- pins within range
-- pin overlap
-- pin spacing
-- max number of pins
numPins, numOverlaps: NAT ← 0;
leftExit, rightExit: BOOLEAN ← FALSE;
branchLayer: CD.Layer ← rules.branchLayer;
trunkLayer: CD.Layer ← rules.trunkLayer;
previousPin: RouteChannel.InternPin ←
NIL;
FOR pList: List.
LORA
-- RouteChannel.InternPinList -- ← pinList, pList.rest
WHILE pList #
NIL
DO
this: RouteChannel.InternPin ← NARROW[pList.first];
numPins ← numPins + 1;
IF previousPin #
NIL
THEN {
-- check for overlapping pins.
IF previousPin.chanSide = this.chanSide
THEN {
rLast, rThis: RTBasic.Range;
IF previousPin.chanSide = chanBottom
OR previousPin.chanSide = chanTop
THEN {
rLast ← [previousPin.location.p - previousPin.pWidth/2, previousPin.location.p + previousPin.pWidth/2];
rThis ← [this.location.p - this.pWidth/2, this.location.p + this.pWidth/2]}
ELSE {
-- chanSide = chanLeft OR chanSide = chanRight
rLast ← [previousPin.location.q - previousPin.pWidth/2, previousPin.location.q + previousPin.pWidth/2];
rThis ← [this.location.q - this.pWidth/2, this.location.q + this.pWidth/2]};
IF RTBasic.Overlaps[rLast, rThis]
THEN {
numOverlaps ← numOverlaps + 1;
IF signalCoincidentPins
OR ~(previousPin.location = this.location
AND previousPin.pWidth = this.pWidth)
THEN
Route.Signal[callingError, Rope.Cat[Rope.Cat["Pins overlap, net: ", net.name, ", pins: "], Rope.Cat[this.name, ", ", previousPin.name]]]; ok ← FALSE}}
};
SELECT this.chanSide
FROM
chanBottom, chanTop => {
pos: DABasics.Number ← this.location.p;
IF chanPins.cEnd1 > pos
OR chanPins.cEnd2 < pos
THEN {
Route.Signal[callingError, Rope.Cat["Pin location out of range, net: ", net.name, ", pin: ", this.name]]; ok ← FALSE};
IF this.pin.layer # branchLayer
THEN {
Route.Signal[callingError, Rope.Cat["Pin not on branch layer, net: ", net.name, ", pin: ", this.name]]; ok ← FALSE}};
chanLeft => {
IF this.pin.layer # trunkLayer
THEN {
Route.Signal[callingError, Rope.Cat["Pin not on trunk layer, net: ", net.name, ", pin: ", this.name]]; ok ← FALSE};
IF leftExit
THEN {
Route.Signal[callingError, Rope.Cat["Multiple channel exits: ", net.name, ", pin: ", this.name]]; ok ← FALSE};
leftExit ← TRUE};
chanRight => {
IF this.pin.layer # trunkLayer
THEN {
Route.Signal[callingError, Rope.Cat["Pin not on trunk layer, net: ", net.name, ", pin: ", this.name]]; ok ← FALSE};
IF rightExit
THEN {
Route.Signal[callingError, Rope.Cat["Multiple channel exits: ", net.name, ", pin: ", this.name]]; ok ← FALSE};
rightExit ← TRUE};
ENDCASE;
previousPin ← this;
ENDLOOP;
IF numPins - numOverlaps <= 1
THEN {
IF signalSinglePinNets THEN Route.Signal[callingError, Rope.Cat["Too few pins for net: ", net.name]];
ok ← FALSE};
IF netTab.count + numPins > netTab.size
THEN {
Route.Signal[noResource, "Net table is too small"]; ok ← FALSE};
};
BuildChanPinForDogleg:
PROC [chanPins: RouteChannel.RoutingChannelPins,
parms: RoutePrivate.RoutingAreaParms,
rules: Route.DesignRules,
net: RoutePrivate.Net,
pinList: List.LORA -- RouteChannel.InternPinList -- ] = {
NOTE: this is an experimental version for DogLeg testing. Must either be made permanent or discarded. Functionally replaces BuildChanPin. BTP July 26, 1988
build the channel pins data structure for this net.
NOTE: this assumes that CheckChanPins has been invoked and that the inputs are valid!!!
set up for the leftmost pin in the net
previousSeg: RouteChannel.Segment ← NIL;
previousPin: RouteChannel.InternPin ← NARROW[pinList.first];
previousPinPosition: RouteChannel.PinPosition ← chanPins.sides[FindPinPos[chanPins, previousPin.location.p]];
previousChanPin: RouteChannel.ChanPin ← BuildPin[parms, previousPin, previousPinPosition, rules.branchWidth];
SELECT previousPin.chanSide
FROM
chanBottom, chanTop =>
IF ~PinViolation[chanPins, parms, rules, previousChanPin, net]
THEN
previousPinPosition.pins[previousChanPin.pinSide] ← previousChanPin;
chanLeft, chanRight =>
previousPinPosition.innerPins ← CONS[previousChanPin, previousPinPosition.innerPins];
ENDCASE;
FOR pList: List.
LORA
-- RouteChannel.InternPinList -- ← pinList.rest, pList.rest
WHILE pList #
NIL
DO
this: RouteChannel.InternPin ← NARROW[pList.first];
allPinsOverlap: BOOLEAN ← TRUE;
useThisOne: BOOLEAN ← TRUE;
rLast, rThis: RTBasic.Range;
IF previousPin.chanSide = chanBottom
OR previousPin.chanSide = chanTop
THEN {
rLast ← [previousPin.location.p - previousPin.pWidth/2, previousPin.location.p + previousPin.pWidth/2];
rThis ← [this.location.p - this.pWidth/2, this.location.p + this.pWidth/2]}
ELSE {
-- chanSide = chanLeft OR chanSide = chanRight
rLast ← [previousPin.location.q - previousPin.pWidth/2, previousPin.location.q + previousPin.pWidth/2];
rThis ← [this.location.q - this.pWidth/2, this.location.q + this.pWidth/2]};
IF previousPin.chanSide = this.chanSide
AND RTBasic.Overlaps[rLast, rThis]
THEN
useThisOne ← FALSE;
IF this.chanSide = chanLeft
OR this.chanSide = chanRight
THEN
allPinsOverlap ← FALSE
ELSE
allPinsOverlap ← allPinsOverlap AND RTBasic.Equal[rLast, rThis];
IF useThisOne
THEN {
-- this pin is not a duplicate
seg: RouteChannel.Segment ← NEW[RouteChannel.SegmentRec ← [net: net]];
pinPosition: RouteChannel.PinPosition ← chanPins.sides[FindPinPos[chanPins, this.location.p]];
chanPin: RouteChannel.ChanPin ← BuildPin[parms, this, pinPosition, rules.branchWidth];
SELECT this.chanSide
FROM
chanBottom, chanTop =>
IF ~PinViolation[chanPins, parms, rules, chanPin, net]
THEN
pinPosition.pins[chanPin.pinSide] ← chanPin;
chanLeft, chanRight =>
pinPosition.innerPins ← CONS[chanPin, pinPosition.innerPins];
ENDCASE;
previousChanPin.conctSeg[chanLeft] ← previousSeg; previousChanPin.conctSeg[chanRight] ← seg;
chanPin.conctSeg[chanLeft] ← seg; chanPin.conctSeg[chanRight] ← NIL;
now update the segment
seg.exteriorPins[chanLeft] ← previousChanPin;
seg.exteriorPins[chanRight] ← chanPin;
seg.interiorPins ← NIL;
make a narrow trunk if pins overlap
seg.qWidth ← IF allPinsOverlap THEN rules.trunkWidth ELSE net.trunkWidth;
previousChanPin ← chanPin;
previousSeg ← seg;
previousPin ← this;
ENDLOOP;
};
BuildChanPin:
PROC [chanPins: RouteChannel.RoutingChannelPins,
parms: RoutePrivate.RoutingAreaParms,
rules: Route.DesignRules,
net: RoutePrivate.Net,
pinList: List.LORA -- RouteChannel.InternPinList -- ] = {
build the channel pins data structure for this net.
NOTE: this assumes that CheckChanPins has been invoked and that the inputs are valid!!!
interiorPins: RouteChannel.ChanPinList ← NIL;
rightInternPin: RouteChannel.InternPin ← NARROW[List.NthElement[pinList, -1]];
previousPin: RouteChannel.InternPin ← NIL;
leftPin, rightPin: RouteChannel.ChanPin ← NIL;
allPinsOverlap: BOOLEAN ← TRUE;
seg: RouteChannel.Segment ←
NEW[RouteChannel.SegmentRec ← [net: net]];
FOR pList: List.
LORA
-- RouteChannel.InternPinList -- ← pinList, pList.rest
WHILE pList #
NIL
DO
pinIndex: RouteChannel.ZMPinsOnCh;
pinPosition: RouteChannel.PinPosition;
chanPin: RouteChannel.ChanPin;
this: RouteChannel.InternPin ← NARROW[pList.first];
useThisOne: BOOLEAN ← TRUE;
IF previousPin #
NIL
THEN {
rLast, rThis: RTBasic.Range;
IF previousPin.chanSide = chanBottom
OR previousPin.chanSide = chanTop
THEN {
rLast ← [previousPin.location.p - previousPin.pWidth/2, previousPin.location.p + previousPin.pWidth/2];
rThis ← [this.location.p - this.pWidth/2, this.location.p + this.pWidth/2]}
ELSE {
-- chanSide = chanLeft OR chanSide = chanRight
rLast ← [previousPin.location.q - previousPin.pWidth/2, previousPin.location.q + previousPin.pWidth/2];
rThis ← [this.location.q - this.pWidth/2, this.location.q + this.pWidth/2]};
IF previousPin.chanSide = this.chanSide
AND RTBasic.Overlaps[rLast, rThis]
THEN
useThisOne ← FALSE;
IF this.chanSide = chanLeft
OR this.chanSide = chanRight
THEN
allPinsOverlap ← FALSE
ELSE
-- make a narrow trunk if pins overlap
allPinsOverlap ← allPinsOverlap AND RTBasic.Equal[rLast, rThis]
};
IF useThisOne
THEN {
pinIndex ← FindPinPos[chanPins, this.location.p];
pinPosition ← chanPins.sides[pinIndex];
chanPin ← BuildPin[parms, this, pinPosition, rules.branchWidth];
SELECT this.chanSide
FROM
chanBottom, chanTop =>
IF ~PinViolation[chanPins, parms, rules, chanPin, net]
THEN
pinPosition.pins[chanPin.pinSide] ← chanPin;
chanLeft, chanRight =>
pinPosition.innerPins ← CONS[chanPin, pinPosition.innerPins];
ENDCASE;
IF leftPin =
NIL
THEN {
leftPin ← chanPin; chanPin.conctSeg[chanLeft] ← NIL; chanPin.conctSeg[chanRight] ← seg}
ELSE
IF this = rightInternPin
THEN {
rightPin ← chanPin; chanPin.conctSeg[chanRight] ← NIL; chanPin.conctSeg[chanLeft] ← seg}
ELSE {
interiorPins ← CONS[chanPin, interiorPins]; chanPin.conctSeg[chanRight] ← seg; chanPin.conctSeg[chanLeft] ← seg}};
previousPin ← this;
ENDLOOP;
now update the segment
seg.exteriorPins[chanLeft] ← leftPin;
seg.exteriorPins[chanRight] ← rightPin;
seg.interiorPins ← interiorPins;
seg.qWidth ← IF allPinsOverlap THEN rules.trunkWidth ELSE net.trunkWidth;
};
FindPinPos:
PUBLIC
PROC [chanPins: RouteChannel.RoutingChannelPins, thisPLoc: DABasics.Number]
RETURNS [index: RouteChannel.ZMPinsOnCh ← 0] = {
build the PinPosition data structure for this pin at thisPLoc.
NOTE: this assumes that CheckChanPins has been invoked and that the inputs are valid!!!
found: BOOLEAN ← FALSE;
FOR pIndex: RouteChannel.ZMPinsOnCh
IN [1 .. chanPins.count]
WHILE ~found
DO
pLoc: DABasics.Number ← chanPins.sides[pIndex].pLoc;
IF pLoc > thisPLoc
THEN
{ -- add a new pinPosition
found ← TRUE;
MovePins[chanPins, pIndex];
index ← pIndex;
chanPins.sides[pIndex] ← NEW[RouteChannel.PinPositionRec ← [index, thisPLoc]]}
ELSE
IF pLoc = thisPLoc
THEN
{ -- pin position already taken, use it
found ← TRUE;
index ← pIndex};
ENDLOOP;
IF ~found
THEN {
-- this pin goes after the last pin
chanPins.count ← chanPins.count +1;
index ← chanPins.count;
chanPins.sides[index] ← NEW[RouteChannel.PinPositionRec ← [index, thisPLoc]]};
};
MovePins:
PROC [chanPins: RouteChannel.RoutingChannelPins, pIndex: RouteChannel.ZMPinsOnCh] = {
chanPins.count ← chanPins.count +1;
FOR index: RouteChannel.ZMPinsOnCh
DECREASING
IN [pIndex+1 .. chanPins.count]
DO
pinPos: RouteChannel.PinPosition ← chanPins.sides[index-1];
pinPos.pinIndex ← index;
chanPins.sides[index] ← pinPos;
ENDLOOP;
};
BuildPin:
PROC [parms: RoutePrivate.RoutingAreaParms, iPin: RouteChannel.InternPin, pinPosition: RouteChannel.PinPosition, pinWidth: DABasics.Number]
RETURNS [pin: RouteChannel.ChanPin] = {
build the channel segment data structure for this net.
kindOfPin: RouteChannel.ChanPinType ←
IF iPin.chanSide = chanLeft OR iPin.chanSide = chanRight THEN exitPin
ELSE compPin;
thisPinWidth: DABasics.Number ←
IF kindOfPin = exitPin THEN iPin.pWidth
ELSE MAX[pinWidth, iPin.pWidth];
parms.widestPin ← MAX[thisPinWidth, parms.widestPin];
pin ←
NEW[RouteChannel.ChanPinRec ← [
pinSide: iPin.chanSide,
qLoc: iPin.location.q,
pWidth: thisPinWidth,
kindOfPin: kindOfPin,
pinPosition: pinPosition,
pin: iPin
]];
};
PinViolation:
PROC [chanPins: RouteChannel.RoutingChannelPins,
parms: RoutePrivate.RoutingAreaParms,
rules: Route.DesignRules,
pin: RouteChannel.ChanPin,
net: RoutePrivate.Net]
RETURNS [violation: BOOLEAN ← FALSE] = {
check for pin to pin violations.
LimitProc: RouteChannel.EachPinActionProc = {
IF pin #
NIL
THEN
IF pin.pinSide = pinSide
THEN
{width: DABasics.Number ← RouteUtil.GetWidthWithContact[rules, pin.pWidth]/2;
pinPos: DABasics.Number ← pin.pinPosition.pLoc;
IF pinPos < pLoc
THEN
quit ← pinPos + width + rules.branchSpacing > pLoc - pWidth
ELSE
-- pinPos >= pLoc
quit ← pLoc + pWidth + rules.branchSpacing > pinPos - width};
IF quit THEN violationPin ← pin.pin};
pinSide: RouteChannel.ChanSide ← pin.pinSide;
pinIndex: RouteChannel.ZMPinsOnCh ← pin.pinPosition.pinIndex;
pLoc: DABasics.Number ← pin.pinPosition.pLoc;
pWidth: DABasics.Number ← RouteUtil.GetWidthWithContact[rules, pin.pWidth]/2;
testWidth: DABasics.Number ← RouteUtil.GetWidthWithContact[rules, parms.widestPin] + rules.branchSpacing;
violationPin: RouteChannel.InternPin ← NIL;
count down from index to find the pin that can still effect index
iPos: DABasics.Number ← chanPins.sides[pinIndex].pLoc;
FOR limitIndex: RouteChannel.MPinsOnCh
DECREASING
IN [1 .. pinIndex]
WHILE chanPins.sides[limitIndex].pLoc + testWidth > iPos
AND ~violation
DO
violation ← RouteChannel.EnumPins[chanPins.sides[limitIndex], LimitProc];
IF violation
THEN
Route.Signal[callingError, Rope.Cat[Rope.Cat["Pins are too close. net 1: ", net.name, ", pin 1: ", pin.pin.name], Rope.Cat[ ", pin 2: ", violationPin.name]]];
ENDLOOP;
count up from index to find the pin that can still effect index
iPos ← chanPins.sides[pinIndex].pLoc;
FOR limitIndex: RouteChannel.MPinsOnCh
IN [pinIndex .. chanPins.count]
WHILE chanPins.sides[limitIndex].pLoc - testWidth < iPos
AND ~violation
DO
violation ← RouteChannel.EnumPins[chanPins.sides[limitIndex], LimitProc];
IF violation
THEN
Route.Signal[callingError, Rope.Cat[Rope.Cat["Pins are too close. net 1: ", net.name, ", pin 1: ", pin.pin.name], Rope.Cat[ ", pin 2: ", violationPin.name]]];
ENDLOOP;
};
GetExitPins:
PROC [chanPins: RouteChannel.RoutingChannelPins]
RETURNS [exitPins: List.
LORA ←
NIL] = {
get the exit pins for this net.
NOTE: this assumes that CheckChanPins has been invoked and that the inputs are valid!!!
ReallyGetExits:
PROC [pinPos: RouteChannel.PinPosition] = {
IF pinPos #
NIL
THEN {
FOR pList: RouteChannel.ChanPinList ← pinPos.innerPins, pList.rest
WHILE pList #
NIL
DO
this: RouteChannel.ChanPin ← pList.first;
SELECT this.pin.chanSide
FROM
chanLeft, chanRight => exitPins ← CONS[this, exitPins];
ENDCASE;
ENDLOOP;
};
ReallyGetExits[chanPins.sides[1]];
IF chanPins.count > 0 THEN ReallyGetExits[chanPins.sides[chanPins.count]];
};
MakeSBTracks:
PROC [chanData: RouteChannel.ChannelData,
rules: Route.DesignRules,
okToDiddleLLPins, okToDiddleURPins: BOOLEAN] = {
find the track positions
ExitPinCompare: List.CompareProc = {
q1: DABasics.Number ← NARROW[ref1, RouteChannel.ChanPin].pin.location.q;
q2: DABasics.Number ← NARROW[ref2, RouteChannel.ChanPin].pin.location.q;
RETURN[
IF q1 < q2
THEN Basics.Comparison.less
ELSE IF q1 = q2 THEN Basics.Comparison.equal
ELSE Basics.Comparison.greater];
DoUp:
PROC [thisPos: DABasics.Number]~ {
FOR trackPos: DABasics.Number ← lastPos + trackDist, trackPos + trackDist
WHILE trackPos <= thisPos - trackDist
DO
[] ← AddTrack[chanTracks, trackPos];
lastPos ← trackPos;
ENDLOOP;
};
ClosestTrack:
PROC [thisPos: DABasics.Number]
RETURNS [track: RouteChannel.Track ←
NIL] ~ {
dist: INT ← LAST[INT];
FOR trackNum:
INT
IN [1 .. chanTracks.count]
DO
trialTrack: RouteChannel.Track ← chanTracks.tracks[trackNum];
trialDist: INT ← ABS[trialTrack.trackPos - thisPos];
IF trialDist < dist
THEN {
track ← trialTrack;
dist ← trialDist}
ENDLOOP;
};
chanPins: RouteChannel.RoutingChannelPins ← chanData.chanPins;
chanTracks: RouteChannel.RoutingChannelTracks ← chanData.chanTracks;
exitPinList: List.LORA ← GetExitPins[chanPins];
sortedExitPinList: List.LORA ← List.Sort[exitPinList, ExitPinCompare];
lastPos: DABasics.Number ← chanData.chanSides[chanBottom].routeAreaCoord;
previousPin: RouteChannel.ChanPin ← NIL;
trackDist: DABasics.Number ← rules.trunkToTrunk;
lastTrack: RouteChannel.Track ← NIL;
the complexity of this code comes from the requirement to move pins on the end of a switchbox under certain conditions (okToDiddleLLPins or okToDiddleURPins).
FOR pList: List.
LORA
-- RouteChannel.InternPinList -- ← sortedExitPinList, pList.rest
WHILE pList #
NIL
DO
this: RouteChannel.ChanPin ← NARROW[pList.first];
thisPos: DABasics.Number ← this.pin.location.q;
pin2Name: Rope.ROPE ← IF previousPin = NIL THEN "none" ELSE previousPin.pin.name;
track: RouteChannel.Track ← NIL;
SELECT
TRUE
FROM
~okToDiddleLLPins
AND ~okToDiddleURPins => {
-- can't move any pins
IF thisPos = lastPos
THEN
-- already have a track here
track ← lastTrack
ELSE
IF thisPos >= lastPos + trackDist
THEN {
-- lots of room here
DoUp[thisPos];
track ← AddTrack[chanTracks, thisPos]}
ELSE {
Route.Signal[callingError, Rope.Cat["Pins too close on ends of switchbox, pin 1: ", this.pin.name, ", pin 2: ", pin2Name]];
track ← AddTrack[chanTracks, thisPos]};
BindPinToTrack[this, track];
previousPin ← this;
lastTrack ← track;
lastPos ← thisPos};
okToDiddleLLPins
AND okToDiddleURPins => {
-- can move pins on both sides
IF thisPos = lastPos
THEN
-- already have a track here
track ← lastTrack
ELSE
IF thisPos >= lastPos + trackDist
THEN {
-- lots of room here
DoUp[thisPos];
track ← AddTrack[chanTracks, thisPos]}
ELSE {
thisPos ← lastPos + trackDist;
track ← AddTrack[chanTracks, thisPos]};
BindPinToTrack[this, track];
previousPin ← this;
lastTrack ← track;
lastPos ← thisPos};
okToDiddleLLPins => {
-- can move only pins on the left
IF this.pin.chanSide = chanRight
THEN {
-- this pin is on the right
IF thisPos >= lastPos + trackDist
THEN
-- lots of room here
DoUp[thisPos]
ELSE
-- not enough room, error
Route.Signal[callingError, Rope.Cat["Pins too close on ends of switchbox, pin 1: ", this.pin.name, ", pin 2: ", pin2Name]];
track ← AddTrack[chanTracks, thisPos];
BindPinToTrack[this, track];
previousPin ← this;
lastTrack ← track;
lastPos ← thisPos;
};
};
okToDiddleURPins => {
-- can move only pins on the right
IF this.pin.chanSide = chanLeft
THEN {
-- this pin is on the left
IF thisPos >= lastPos + trackDist
THEN
-- lots of room here
DoUp[thisPos]
ELSE
-- not enough room, error
Route.Signal[callingError, Rope.Cat["Pins too close on ends of switchbox, pin 1: ", this.pin.name, ", pin 2: ", pin2Name]];
track ← AddTrack[chanTracks, thisPos];
BindPinToTrack[this, track];
previousPin ← this;
lastTrack ← track;
lastPos ← thisPos;
};
};
ENDCASE;
ENDLOOP;
run the tracks to the top of the switchbox
IF previousPin #
NIL
AND lastPos > chanData.chanSides[chanTop].routeAreaCoord - trackDist
THEN {
Route.Signal[callingError, Rope.Cat["Pins too close on ends of switchbox, pin : ", previousPin.pin.name]]};
FOR trackPos: DABasics.Number ← lastPos + trackDist, trackPos + trackDist
WHILE trackPos < chanData.chanSides[chanTop].routeAreaCoord - trackDist
DO
[] ← AddTrack[chanTracks, trackPos];
lastPos ← trackPos;
ENDLOOP;
chanTracks.maxCount ← chanTracks.count;
IF okToDiddleLLPins # okToDiddleURPins
THEN {
fix up the other side now
FOR pList: List.
LORA
-- RouteChannel.InternPinList -- ← sortedExitPinList, pList.rest
WHILE pList #
NIL
DO
this: RouteChannel.ChanPin ← NARROW[pList.first];
thisPos: DABasics.Number ← this.pin.location.q;
pin2Name: Rope.ROPE ← IF previousPin = NIL THEN "none" ELSE previousPin.pin.name;
track: RouteChannel.Track;
SELECT
TRUE
FROM
okToDiddleLLPins => {
-- can move only pins on the left
IF this.pin.chanSide = chanLeft
THEN {
-- this pin is on the left
track ← ClosestTrack[thisPos];
BindPinToTrack[this, track]};
};
okToDiddleURPins => {
-- can move only pins on the right
IF this.pin.chanSide = chanRight
THEN {
-- this pin is on the right
track ← ClosestTrack[thisPos];
BindPinToTrack[this, track]};
};
ENDCASE;
ENDLOOP;
};
};
MakeCRTracks:
PROC [chanTracks: RouteChannel.RoutingChannelTracks,
rules: Route.DesignRules,
maxTracksRequired: NAT] = {
find the track positions
trackLimit: RouteChannel.ZMaxTracks ← MIN[chanTracks.size, maxTracksRequired];
loc: DABasics.Number ← rules.trunkToEdge;
FOR trackIndex: RouteChannel.ZMaxTracks
IN [1 .. trackLimit]
DO
loc: DABasics.Number ← rules.trunkToEdge + (trackIndex - 1) * rules.trunkToTrunk;
[] ← AddTrack[chanTracks, loc];
loc ← loc + rules.trunkToTrunk;
ENDLOOP;
chanTracks.maxCount ← chanTracks.count;
};
AddTrack:
PROC [chanTracks: RouteChannel.RoutingChannelTracks, trackPos: DABasics.Number]
RETURNS [track: RouteChannel.Track] = {
insert a track at the position
IF chanTracks.count >= RouteChannel.maxTrack
THEN
Route.Signal[noResource, "Too many tracks needed, call implementor"];
chanTracks.count ← chanTracks.count + 1;
track ← chanTracks.tracks[chanTracks.count] ← NEW[RouteChannel.TrackRec ← [trackNum: chanTracks.count, trackPos: trackPos]]};
BindPinToTrack:
PROC [pin: RouteChannel.ChanPin, track: RouteChannel.Track] ~ {
IF pin #
NIL
THEN {
update the track constraints for the segments attached to the pin
sList: RouteChannel.SegmentList ← RouteChannel.GetSegsOnPin[pin];
pin.trackConstraint ← track.trackNum;
FOR segs: RouteChannel.SegmentList ← sList, segs.rest
WHILE segs #
NIL
DO
seg: RouteChannel.Segment ← segs.first;
IF seg #
NIL
THEN {
IF seg.trackConstraint = 0 THEN seg.trackConstraint ← track.trackNum
ELSE seg.secTrackConstraint ← track.trackNum};
ENDLOOP;
};
};
DoTBBarriers:
PROC [chanData: RouteChannel.ChannelData,
parms: RoutePrivate.RoutingAreaParms,
rules: Route.DesignRules,
chanSide: RouteChannel.ChanSide] = {
Block the tracks covered by the layer.
chanTracks: RouteChannel.RoutingChannelTracks ← chanData.chanTracks;
activeSide: RouteChannel.RoutingChannelSides ← chanData.chanSides[chanSide];
chanPins: RouteChannel.RoutingChannelPins ← chanData.chanPins;
trackDist: DABasics.Number ← rules.trunkToTrunk;
FOR rlayer: RoutePrivate.RoutingLayer
IN [trunk .. branch]
DO
FOR bList: RTBasic.PQRectList ← activeSide.barrierList[rlayer], bList.rest
WHILE bList #
NIL
DO
BlockProc: RouteChannel.EachTrackActionProc = {
trackPos: DABasics.Number ← RouteChannel.TrackLoc[chanTracks, parms, rules, trackIndex];
IF minQ < trackPos - trackDist
AND trackPos + trackDist < maxQ
THEN
track.blocked ← TRUE};
barrierItem: RTBasic.PQRect ← bList.first;
minQ: DABasics.Number ← MIN[barrierItem.c1.q, barrierItem.c2.q];
maxQ: DABasics.Number ← MAX[barrierItem.c1.q, barrierItem.c2.q];
[] ← RouteChannel.EnumTracks[chanTracks, BlockProc];
ENDLOOP;
ENDLOOP;
};
DoLRBarriers:
PROC [chanData: RouteChannel.ChannelData,
chanSide: RouteChannel.ChanSide] = {
Block the tracks covered by the layer.
activeSide: RouteChannel.RoutingChannelSides ← chanData.chanSides[chanSide];
FOR rlayer: RoutePrivate.RoutingLayer
IN [trunk .. branch]
DO
FOR bList: RTBasic.PQRectList ← activeSide.barrierList[rlayer], bList.rest
WHILE bList #
NIL
DO
BlockProc: RouteChannel.EachTrackActionProc = {
NULL };
barrierItem: RTBasic.PQRect ← bList.first;
minQ: DABasics.Number ← MIN[barrierItem.c1.q, barrierItem.c2.q];
maxQ: DABasics.Number ← MAX[barrierItem.c1.q, barrierItem.c2.q];
[] ← RouteChannel.EnumTracks[chanData.chanTracks, BlockProc];
ENDLOOP;
ENDLOOP;
};
Surround:
PROC [r1, r2: RTBasic.PQRect]
RETURNS [RTBasic.PQRect] =
INLINE {
RETURN [RTBasic.PQRect[
[MIN[r1.c1.p, r2.c1.p], MIN[r1.c1.q, r2.c1.q]],
[MAX[r1.c2.p, r2.c2.p], MAX[r1.c2.q, r2.c2.q]]]]};
ConvertToLORA:
PROC [list: RouteChannel.InternPinList]
RETURNS[val: List.
LORA] = {
val ← NIL;
UNTIL list =
NIL
DO
val ← CONS[list.first, val];
list ← list.rest;
ENDLOOP;
RETURN[val];
}; -- of ConvertToLORA
}.