RouteChannelConstraintsImpl.mesa ///Route/RouteChannelConstraintsImpl.mesa
Bryan Preas February 21, 1986 6:15:05 pm PST
Copyright © 1985 by Xerox Corporation. All rights reserved.
by Bryan Preas July 10, 1985 6:57:00 pm PDT
last edited by Bryan Preas July 10, 1985 6:57:07 pm PDT
DIRECTORY
Basics,
CD,
List,
Rope,
Route,
RouteChannel,
RouteDiGraph,
RoutePrivate,
RouteUtil,
TerminalIO;
RouteChannelConstraintsImpl: CEDAR PROGRAM
IMPORTS List, Rope, Route, RouteChannel, RouteDiGraph, RouteUtil, TerminalIO
EXPORTS RouteChannel
SHARES Route = {
SegBreakType: TYPE = {dogLeg, exit}; -- should add pinDogLeg sometime
SegBreakSpec: TYPE = REF SegBreakSpecRec;
SegBreakSpecRec: TYPE = RECORD [
pos: Route.Number ← 0,
type: SegBreakType ← dogLeg];
Lmr: TYPE = {left, middle, right};
FullSegBreakSpec: TYPE = RECORD [
seg: RouteChannel.Segment ←NIL,
breaks: ARRAY Lmr OF SegBreakSpec ← ALL[NIL]];
BreakResult: TYPE = RECORD [
deltaDensity: Route.Number,
duplicateLength: Route.Number,
numDogLegs: Route.Number];
RangeWithDirList: TYPE = LIST OF RangeWithDir;
RangeWithDir: TYPE = RECORD [
range: RoutePrivate.Range,
dir: RouteChannel.GoingDirection];
ChanPinListSet: TYPE = RECORD [
leftExit, rightExit: RouteChannel.ChanPin ← NIL,
bottomList, topList: RouteChannel.ChanPinList ← NIL];
ChanPinListPair: TYPE = RECORD [
list1, list2: RouteChannel.ChanPinList ← NIL];
GenerateConstraints: PUBLIC PROCEDURE[routingArea: Route.RoutingArea, routerUsed: RoutePrivate.RouterUsed] RETURNS [anythingToDo: BOOLEAN] = {
run through the pins on the channel,
create segment constraints from the pin to pin relationships
return if no pins
chanData: RouteChannel.ChannelData ← NARROW[routingArea.privateData];
chanPins: RouteChannel.RoutingChannelPins ← chanData.chanPins;
parms: RoutePrivate.RoutingAreaParms ← NARROW[routingArea.parms];
graphName: Rope.ROPE ← "Vertical Constraints";
segBroken: BOOLEANTRUE;
IF chanPins.count = 0 THEN RETURN[FALSE];
WHILE segBroken DO
outer loop can be removed whe constraints by seg is added
segBroken ← FALSE;
IF chanData.constraints # NIL THEN DestroyOldConstraints[routingArea]; -- unlink the old graph
chanData.constraints ← RouteDiGraph.CreateGraph[graphName];
FOR index: RouteChannel.MPinsOnCh IN [1 .. chanPins.count] DO
WidestPinProc: RouteChannel.EachPinActionProc = {
IF pin # NIL THEN
widestPinD2 ← MAX[widestPinD2, pin.pWidth/2]};
LimitProc: RouteChannel.EachPinActionProc = {
IF pin # NIL THEN
{width: Route.Number ← pin.pWidth/2;
pinPos: Route.Number ← pin.pinPosition.pLoc;
IF pinPos = pLoc THEN
quit ← TRUE
ELSE IF pinPos < pLoc THEN
quit ← pinPos + width + spacing > pLoc - widestPinD2
ELSE -- pinPos >= pLoc
quit ← pLoc + widestPinD2 + spacing > pinPos - width}};
pinPosition: RouteChannel.PinPosition ← chanPins.sides[index];
pLoc: Route.Number ← pinPosition.pLoc;
widestPinD2: Route.Number ← routingArea.rules.pinSpacing/2;
spacing: Route.Number ← routingArea.rules.pinSpacing;
minLimit, maxLimit: RouteChannel.MPinsOnCh;
generate constraints for this coordinate, if any
[] ← RouteChannel.EnumPins[routingArea, pinPosition, WidestPinProc];
[minLimit, maxLimit] ← RouteChannel.FindConstraintLimits[routingArea, index, index, LimitProc];
FOR upperIndex: RouteChannel.MPinsOnCh IN [minLimit .. maxLimit] DO
upperPinPosition: RouteChannel.PinPosition ← chanPins.sides[upperIndex];
upperPin: RouteChannel.ChanPin ← upperPinPosition.pins[chanTop];
lowerPin: RouteChannel.ChanPin ← pinPosition.pins[chanBottom];
IF ProcessConstraints[routingArea, upperPin, lowerPin, middle] THEN GOTO GoRound;
now do constraints for doglegs and exits wrt the upper pins
FOR innerPins: RouteChannel.ChanPinList ← pinPosition.innerPins, innerPins.rest WHILE innerPins # NIL DO
innerPin: RouteChannel.ChanPin ← innerPins.first;
first the upper pin, if any
IF ProcessConstraints[routingArea, upperPin, innerPin, middle] THEN GOTO GoRound;
ENDLOOP; -- FOR innerPins
ENDLOOP; -- FOR upperIndex
next the constraints for doglegs and exits wrt the lower pin, if any
FOR lowerIndex: RouteChannel.MPinsOnCh IN [minLimit .. maxLimit] DO
lowerPinPosition: RouteChannel.PinPosition ← chanPins.sides[lowerIndex];
lowerPin: RouteChannel.ChanPin ← lowerPinPosition.pins[chanBottom];
now do constraints for doglegs and exits wrt the lower pins
FOR innerPins: RouteChannel.ChanPinList ← pinPosition.innerPins, innerPins.rest WHILE innerPins # NIL DO
innerPin: RouteChannel.ChanPin ← innerPins.first;
IF ProcessConstraints[routingArea, innerPin, lowerPin, middle] THEN GOTO GoRound;
ENDLOOP; -- FOR innerPins
ENDLOOP; -- FOR lowerIndex
do the exits wrt each other if this is a switchBox and a channel end
IF routerUsed = switchBox AND (index = 1 OR index = chanPins.count) THEN {
QPinCompare: List.CompareProc = {
p1: Route.Number ← NARROW[ref1, RouteChannel.ChanPin].qLoc;
p2: Route.Number ← NARROW[ref2, RouteChannel.ChanPin].qLoc;
RETURN[IF p1 < p2 THEN Basics.Comparison.less
ELSE IF p1 = p2 THEN Basics.Comparison.equal
ELSE Basics.Comparison.greater]};
whichEnd: Lmr ← IF index = 1 THEN left ELSE right;
mungedPinList, sortedPinList: List.LORA;
Use Reverse to get a new copy of the list because Sort is destructive
TRUSTED{mungedPinList ← List.Reverse[LOOPHOLE[pinPosition.innerPins]]};
sortedPinList ← List.Sort[mungedPinList, QPinCompare];
FOR pList: List.LORA -- RouteChannel.ChanPinList -- ← sortedPinList, pList.rest WHILE pList # NIL DO
lowerPin: RouteChannel.ChanPin ← NARROW[pList.first];
sList: RouteChannel.SegmentList ← RouteChannel.GetSegsOnPin[lowerPin];
process pin to pin constraints
IF pList.rest # NIL THEN {
upperPin: RouteChannel.ChanPin ← NARROW[pList.rest.first];
IF ProcessConstraints[routingArea, upperPin, lowerPin, whichEnd] THEN GOTO GoRound};
break any segments that must be in 2 tracks
FOR segs: RouteChannel.SegmentList ← sList, segs.rest WHILE segs # NIL DO
seg: RouteChannel.Segment ← segs.first;
IF seg.trackConstraint # 0 AND seg.secTrackConstraint # 0 AND seg.trackConstraint # seg.secTrackConstraint AND ~seg.failed THEN {
break: FullSegBreakSpec ← BreakOneSeg[routingArea, seg, NIL, whichEnd];
IF BreaksFound[break] > 0 THEN {
DoBreak[routingArea, break]; GOTO GoRound}
ELSE { -- mark seg as failed --
seg.failed ← TRUE;
TerminalIO.WriteRope[Rope.Cat["\nunable to find a place to dogleg, net: ", seg.net.name, " failed"]]}}
ENDLOOP;
ENDLOOP};
REPEAT GoRound => segBroken ← TRUE;
ENDLOOP; -- WHILE index
ENDLOOP; -- WHILE segBroken
RETURN[TRUE]}; -- GenerateConstraints
DestroyOldConstraints: PUBLIC PROC [routingArea: Route.RoutingArea] = {
must explicitly destroy the old data
chanData: RouteChannel.ChannelData ← NARROW[routingArea.privateData];
chanPins: RouteChannel.RoutingChannelPins ← chanData.chanPins;
DestroyGraph: RouteDiGraph.EnumGraphProc = {NULL};
DestroyArc: RouteDiGraph.EnumArcProc = {NULL};
DestroyNode: RouteDiGraph.EnumNodeProc = {
nodeInfo: RouteChannel.SegmentConstraint ← NARROW[node.nodeInfo];
nodeInfo.segment ← NIL};
ClearConstraints: RouteChannel.EachPinActionProc = {
leftSeg: RouteChannel.Segment ← pin.conctSeg[chanLeft];
rightSeg: RouteChannel.Segment ← pin.conctSeg[chanRight];
IF leftSeg # NIL THEN leftSeg.constraintNode ← NIL;
IF rightSeg # NIL THEN rightSeg.constraintNode ← NIL};
FOR index: RouteChannel.MPinsOnCh IN [1 .. chanPins.count] DO
pinPosition: RouteChannel.PinPosition ← chanPins.sides[index];
[] ← RouteChannel.EnumPins[routingArea, pinPosition, ClearConstraints];
ENDLOOP;
RouteDiGraph.DestroyGraph[chanData.constraints, DestroyGraph, DestroyNode, DestroyArc]};
ProcessConstraints: PROCEDURE[routingArea: Route.RoutingArea, upperPin, lowerPin: RouteChannel.ChanPin, whichEnd: Lmr] RETURNS [segBroken: BOOLEANFALSE] = {
add a segment constraint if it does not create a loop
do upper to lower pin constraint
IF upperPin # NIL AND lowerPin # NIL THEN
IF upperPin.kindOfPin # noPin AND lowerPin.kindOfPin # noPin THEN
IF (upperPin.kindOfPin # exitPin AND lowerPin.kindOfPin # exitPin) OR (whichEnd # middle AND upperPin.kindOfPin = exitPin AND lowerPin.kindOfPin = exitPin) THEN
IF Constraining[routingArea, upperPin, lowerPin] THEN
generate pin to pin constraints, process all segments attached to these pins
FOR lowerSegIndex: RouteChannel.ChanLRSide IN [chanLeft .. chanRight] WHILE ~segBroken DO
FOR upperSegIndex: RouteChannel.ChanLRSide IN [chanLeft .. chanRight] WHILE ~segBroken DO
lowerSeg: RouteChannel.Segment ← lowerPin.conctSeg[lowerSegIndex];
upperSeg: RouteChannel.Segment ← upperPin.conctSeg[upperSegIndex];
IF DoConstraint[routingArea, lowerSeg, upperSeg, whichEnd] THEN segBroken ← TRUE;
ENDLOOP; -- FOR upperSegIndex
ENDLOOP; -- FOR lowerSegIndex
};
Constraining: PROC [routingArea: Route.RoutingArea, pin1, pin2: RouteChannel.ChanPin] RETURNS [constraining: BOOLEANFALSE] = {
determining if pin1 actually constrains pin2
IF pin1 # NIL AND pin2 # NIL THEN
{p1: Route.Number ← pin1.pinPosition.pLoc;
w1: Route.Number ← pin1.pWidth/2;
p2: Route.Number ← pin2.pinPosition.pLoc;
w2: Route.Number ← pin2.pWidth/2;
dist: Route.Number ← routingArea.rules.branchToBranch - routingArea.rules.branchSpacing;
IF p1 = p2 THEN
constraining ← TRUE
ELSE IF p1 < p2 THEN
constraining ← p1 + w1 + dist > p2 - w2
ELSE -- p1 > p2
constraining ← p2 + w2 + dist > p1 - w1}};
DoConstraint: PROCEDURE[routingArea: Route.RoutingArea, lowerSeg, upperSeg: RouteChannel.Segment, whichEnd: Lmr] RETURNS [segBroken: BOOLEANFALSE] = {
add a segment constraint if it does not create a loop
IF lowerSeg # NIL AND upperSeg # NIL AND lowerSeg # upperSeg THEN
IF ~lowerSeg.failed AND ~upperSeg.failed AND (lowerSeg.net.netNum # upperSeg.net.netNum OR lowerSeg.net.netPart # upperSeg.net.netPart) THEN {
segList: RouteChannel.SegmentList;
chanData: RouteChannel.ChannelData ← NARROW[routingArea.privateData];
graph: RouteDiGraph.Graph ← chanData.constraints;
nets: RoutePrivate.NetTab ← NARROW[routingArea.nets];
lowerNode: RouteDiGraph.Node ← lowerSeg.constraintNode;
upperNode: RouteDiGraph.Node ← upperSeg.constraintNode;
IF lowerNode = NIL THEN
{constraint: RouteChannel.SegmentConstraint ← NEW[RouteChannel.SegmentConstraintRec ← [lowerSeg.net.name, lowerSeg]];
lowerNode ← RouteDiGraph.AddNewNode[graph, constraint];
lowerSeg.constraintNode ← lowerNode};
IF upperNode = NIL THEN
{constraint: RouteChannel.SegmentConstraint ← NEW[RouteChannel.SegmentConstraintRec ← [upperSeg.net.name, upperSeg]];
upperNode ← RouteDiGraph.AddNewNode[graph, constraint];
upperSeg.constraintNode ← upperNode};
segList ← SegsInCycle[graph, lowerNode, upperNode];
IF segList # NIL THEN
choose a segment to break and the position to dogleg
{density: RouteChannel.Density ← RouteChannel.ComputeDensity[routingArea];
segBreak: FullSegBreakSpec ← FindBreak[routingArea, segList, density, whichEnd];
IF BreaksFound[segBreak] > 0 THEN DoBreak[routingArea, segBreak]
ELSE { -- choose a victim --
segList.first.failed ← TRUE;
TerminalIO.WriteRope[Rope.Cat["\nnet: ", segList.first.net.name, " failed, unable to find a place to dogleg"]];
};
segBroken ← TRUE}
ELSE { -- add a segment constraint
need to change so I don't add duplicate constraints
constrain Upper above Lower
IF ~RouteDiGraph.PathExists[graph, upperNode, lowerNode] THEN
arcName: Rope.ROPE ← Rope.Cat[upperSeg.net.name,"-above-", lowerSeg.net.name];
[] ← RouteDiGraph.AddNewArc[graph, NIL, upperNode, lowerNode]}}};
SegsInCycle: PROCEDURE[graph: RouteDiGraph.Graph, lowerNode, upperNode: RouteDiGraph.Node]
RETURNS [segList: RouteChannel.SegmentList ← NIL] = {
recursively go through the constraints
ArcProc: RouteDiGraph.EnumArcsFromNodeProc = {
IF arc.superiorNode = lowerNode THEN
{nodeInfo: RouteChannel.SegmentConstraint ← NARROW[lowerNode.nodeInfo];
segList ← CONS[nodeInfo.segment, segList];
quit ← TRUE}
ELSE quit ← RouteDiGraph.EnumArcsFromNode[graph, arc.superiorNode, out, ArcProc];
IF quit THEN
{nodeInfo: RouteChannel.SegmentConstraint ← NARROW[node.nodeInfo];
segList ← CONS[nodeInfo.segment, segList]}};
[] ← RouteDiGraph.EnumArcsFromNode[graph, upperNode, out, ArcProc]};
FindBreak: PROC [routingArea: Route.RoutingArea, segList: RouteChannel.SegmentList, density: RouteChannel.Density, whichEnd: Lmr] RETURNS [bestBreak: FullSegBreakSpec ← [NIL, [NIL, NIL, NIL]]] = {
decide on which segment to divide and the position
bestResult: BreakResult ← [LAST[INT], LAST[INT], LAST[INT]];
run through the segs in the cycle. find the best
FOR segs: RouteChannel.SegmentList ← segList, segs.rest WHILE segs # NIL DO
seg: RouteChannel.Segment ← segs.first;
break: FullSegBreakSpec ← BreakOneSeg[routingArea, seg, density, whichEnd];
result: BreakResult ← EvalBreak[routingArea, break, density];
IF CompareResult[result, bestResult] = less THEN
{bestResult ← result; bestBreak ← break};
ENDLOOP;
IF bestBreak.seg = NIL THEN RETURN[[NIL, [NIL, NIL, NIL]]]};
BreakOneSeg: PROC [routingArea: Route.RoutingArea, seg: RouteChannel.Segment, density: RouteChannel.Density, whichEnd: Lmr] RETURNS [break: FullSegBreakSpec] = {
find the best position to break this seg
parms: RoutePrivate.RoutingAreaParms ← NARROW[routingArea.parms];
exitsSeparate: BOOLEANIF parms.routerUsed = channel THEN FALSE ELSE TRUE;
pinLists: ChanPinListSet ← GetPins[exitsSeparate, seg];
rangeList: RangeWithDirList ← SegRanges[routingArea, pinLists];
break ← [seg, [NIL, NIL, NIL]];
SELECT parms.routerUsed FROM
channel => {
FOR ranges: RangeWithDirList ← rangeList, ranges.rest WHILE ranges # NIL DO
break.breaks[middle] ← BreakWithInRange[routingArea, seg, ranges.first];
IF break.breaks[middle] # NIL THEN EXIT;
ENDLOOP;
IF break.breaks[middle] = NIL THEN
break.breaks[middle] ← BreakAtExit[routingArea, seg, density]};
switchBox => {
DoMiddle: PROC [] ~ {
IF top AND bottom AND BreaksFound[break] = 0 THEN {
FOR ranges: RangeWithDirList ← rangeList, ranges.rest WHILE ranges # NIL DO
break.breaks[middle] ← BreakWithInRange[routingArea, seg, ranges.first];
IF break.breaks[middle] # NIL THEN EXIT;
ENDLOOP}};
DoLeft: PROC [] ~ {
IF left AND (top OR right OR bottom) AND BreaksFound[break] = 0 THEN {
leftRange: RangeWithDir ← [[cEnd1, cEnd2], leftToRight];
break.breaks[left] ← BreakWithInRange[routingArea, seg, leftRange]}};
DoRight: PROC [] ~ {
IF right AND (top OR left OR bottom) AND BreaksFound[break] = 0 THEN {
rightRange: RangeWithDir ← [[cEnd1, cEnd2], rightToLeft];
break.breaks[right] ← BreakWithInRange[routingArea, seg, rightRange]}};
chanData: RouteChannel.ChannelData ← NARROW[routingArea.privateData];
cEnd1: Route.Number ← chanData.chanPins.cEnd1;
cEnd2: Route.Number ← chanData.chanPins.cEnd2;
left, top, right, bottom: BOOLEAN;
[left, top, right, bottom] ← RouteChannel.PinsOnSide[routingArea, seg];
SELECT TRUE FROM
whichEnd = left => {DoLeft; DoRight; DoMiddle};
whichEnd = right => {DoRight; DoLeft; DoMiddle};
seg.trackConstraint # 0 => {DoRight; DoLeft; DoMiddle};
ENDCASE => {DoMiddle; DoRight; DoLeft};
};
ENDCASE => Route.Error[programmingError, "Invalid router being used."];
};
BreakWithInRange: PROC [routingArea: Route.RoutingArea, seg: RouteChannel.Segment, range: RangeWithDir] RETURNS [break: SegBreakSpec ← NIL] = {
find the best position to break this seg within this range
noDogLeg: BOOLEANFALSE;
lambda: Route.Number;
SELECT range.dir FROM
leftToRight =>
{FOR lambda IN [range.range.l .. range.range.r] DO
noDogLeg ← DogLegNotAllowed[routingArea, seg, lambda];
IF ~ noDogLeg THEN EXIT
ENDLOOP};
rightToLeft =>
{FOR lambda DECREASING IN [range.range.l .. range.range.r] DO
noDogLeg ← DogLegNotAllowed[routingArea, seg, lambda];
IF ~ noDogLeg THEN EXIT
ENDLOOP};
ENDCASE;
IF ~noDogLeg THEN break ← NEW[SegBreakSpecRec ← [lambda, dogLeg]]};
DogLegNotAllowed: PROC [routingArea: Route.RoutingArea, seg: RouteChannel.Segment, lambda: Route.Number] RETURNS [notAllowed: BOOLEANFALSE] = {
see if a dogleg is allowed here
FindConnectedNet: PROC [pin: RouteChannel.ChanPin] RETURNS [net: RoutePrivate.Net ← NIL] =
{IF pin # NIL THEN
{s1: RouteChannel.Segment ← pin.conctSeg[chanLeft];
s2: RouteChannel.Segment ← pin.conctSeg[chanRight];
IF s1 # NIL THEN net ← s1.net
ELSE IF s2 # NIL THEN net ← s2.net
ELSE Route.Error[programmingError, "Pin not connected to a segment."]}};
CheckInner: RouteChannel.EachPinActionProc = {
IF pin # NIL THEN
IF pin.kindOfPin = exitPin OR pin.kindOfPin = dogLeg THEN
IF Constraining[routingArea, pin, trialPin] THEN quit ← TRUE};
OuterConstraints: RouteChannel.EachPinActionProc = {
IF pin # NIL THEN
IF pin.kindOfPin = chanConnect OR pin.kindOfPin = compPin THEN
IF Constraining[routingArea, pin, trialPin] THEN quit ← TRUE};
chanData: RouteChannel.ChannelData ← NARROW[routingArea.privateData];
netTab: RoutePrivate.NetTab ← NARROW[routingArea.nets];
chanPins: RouteChannel.RoutingChannelPins ← chanData.chanPins;
minLimit, maxLimit: RouteChannel.MPinsOnCh;
width: Route.Number ← MAX[seg.net.trunkWidth, seg.net.branchWidth];
spacing: Route.Number ← MAX[routingArea.rules.contactToContact - width, routingArea.rules.branchSpacing]; -- need to alllow variable dogleg width
trialPinPosition: RouteChannel.PinPosition ← NEW[RouteChannel.PinPositionRec ← [pinIndex: 0, pLoc: lambda]];
trialPin: RouteChannel.ChanPin ← NEW[RouteChannel.ChanPinRec ← [pinSide: none, qLoc: 0, pWidth: width, kindOfPin: dogLeg, pinPosition: trialPinPosition]];
leftExitPosition: RouteChannel.PinPosition ← NEW[RouteChannel.PinPositionRec ← [pinIndex: 0, pLoc: chanPins.cEnd1]];
leftExitPin: RouteChannel.ChanPin ← NEW[RouteChannel.ChanPinRec ← [pinSide: none, qLoc: 0, pWidth: width, kindOfPin: exitPin, pinPosition: leftExitPosition]];
rightExitPosition: RouteChannel.PinPosition ← NEW[RouteChannel.PinPositionRec ← [pinIndex: 0, pLoc: chanPins.cEnd2]];
rightExitPin: RouteChannel.ChanPin ← NEW[RouteChannel.ChanPinRec ← [pinSide: none, qLoc: 0, pWidth: width, kindOfPin: exitPin, pinPosition: rightExitPosition]];
leftIndex, rightIndex: RouteChannel.MPinsOnCh;
[leftIndex, rightIndex] ← ClosestPins[routingArea, lambda];
must reserve place for future exits
IF Constraining[routingArea, trialPin, leftExitPin] THEN notAllowed ← TRUE;
IF Constraining[routingArea, trialPin, rightExitPin] THEN notAllowed ← TRUE;
see if inner pins interfere
[minLimit, maxLimit] ← RouteChannel.FindConstraintLimits[routingArea, leftIndex, rightIndex, CheckInner];
FOR index: RouteChannel.MPinsOnCh IN [minLimit .. maxLimit] WHILE ~notAllowed DO
see if there are existing dog legs
pinPosition: RouteChannel.PinPosition ← chanPins.sides[index];
notAllowed ← RouteChannel.EnumPins[routingArea, pinPosition, CheckInner];
ENDLOOP;
see if outer pins interfere
[minLimit, maxLimit] ← RouteChannel.FindConstraintLimits[routingArea, leftIndex, rightIndex, OuterConstraints];
FOR index: RouteChannel.MPinsOnCh IN [minLimit .. maxLimit] WHILE ~notAllowed DO
pinPosition: RouteChannel.PinPosition ← chanPins.sides[index];
bottomPin: RouteChannel.ChanPin ← pinPosition.pins[chanBottom];
topPin: RouteChannel.ChanPin ← pinPosition.pins[chanTop];
bottomNet: RoutePrivate.Net ← FindConnectedNet[bottomPin];
topNet: RoutePrivate.Net ← FindConnectedNet[topPin];
constrainTop: BOOLEAN ← Constraining[routingArea, topPin, trialPin];
constrainBottom: BOOLEAN ← Constraining[routingArea, bottomPin, trialPin];
see if any nets within th range cross the channels
FOR i: RouteChannel.MPinsOnCh IN [minLimit .. maxLimit] WHILE ~notAllowed DO
pP: RouteChannel.PinPosition ← chanPins.sides[i];
bP: RouteChannel.ChanPin ← pP.pins[chanBottom];
tP: RouteChannel.ChanPin ← pP.pins[chanTop];
bN: RoutePrivate.Net ← FindConnectedNet[bP];
tN: RoutePrivate.Net ← FindConnectedNet[tP];
IF bottomNet = tN AND Constraining[routingArea, topPin, bP] AND constrainTop AND constrainBottom THEN notAllowed ← TRUE;
IF topNet = bN AND Constraining[routingArea, bottomPin, tP] AND constrainTop AND constrainBottom THEN notAllowed ← TRUE;
ENDLOOP;
see if a constraint loop is created
later -- for now dont use pin positions that could cause constraint loops
IF constrainTop OR constrainBottom THEN notAllowed ← TRUE;
ENDLOOP};
BreakAtExit: PROC [routingArea: Route.RoutingArea, seg: RouteChannel.Segment, density: RouteChannel.Density] RETURNS [break: SegBreakSpec] = {
find the best exit to break this seg
chanData: RouteChannel.ChannelData ← NARROW[routingArea.privateData];
chanPins: RouteChannel.RoutingChannelPins ← chanData.chanPins;
leftBreak: SegBreakSpec ← NEW[SegBreakSpecRec ← [chanPins.cEnd1, exit]];
leftFullBreak: FullSegBreakSpec ← [seg, [leftBreak, NIL, NIL]];
rightBreak: SegBreakSpec ← NEW[SegBreakSpecRec ← [chanPins.cEnd2, exit]];
rightFullBreak: FullSegBreakSpec ← [seg, [NIL, NIL, rightBreak]];
leftResult: BreakResult ← EvalBreak[routingArea, leftFullBreak, density];
rightResult: BreakResult ← EvalBreak[routingArea, rightFullBreak, density];
IF CompareResult[leftResult, rightResult] = less THEN RETURN [leftBreak]
ELSE RETURN [rightBreak]};
EvalBreak: PROC [routingArea: Route.RoutingArea, break: FullSegBreakSpec, density: RouteChannel.Density] RETURNS [result: BreakResult] = {
evaluate the break of ths seg at break
maxDensity: Route.Number;
lowerRange, upperRange, overlap: RoutePrivate.Range;
parms: RoutePrivate.RoutingAreaParms ← NARROW[routingArea.parms];
exitsSeparate: BOOLEANIF parms.routerUsed = channel THEN FALSE ELSE TRUE;
pinLists: ChanPinListSet ← GetPins[exitsSeparate, break.seg];
IF BreaksFound[break] = 0 THEN RETURN[[LAST[INT], LAST[INT], LAST[INT]]];
IF break.breaks[middle] # NIL THEN {
lowerRange ← RouteChannel.Span[[break.breaks[middle].pos, break.breaks[middle].pos], RouteChannel.GetRange[pinLists.bottomList]];
upperRange ← RouteChannel.Span[[break.breaks[middle].pos, break.breaks[middle].pos], RouteChannel.GetRange[pinLists.topList]];
overlap ← RouteChannel.Overlap[lowerRange, upperRange];
IF overlap.l > overlap.r THEN Route.Error[programmingError, "overlap should not be NIL."]}
ELSE overlap ← [0,0];
maxDensity ← AddSeg[routingArea, density, overlap, break.seg.qWidth];
result.deltaDensity ← maxDensity - density.maxDensity;
result.duplicateLength ← overlap.r - overlap.l;
result.numDogLegs ← 0;
FOR lmr: Lmr IN Lmr DO
IF break.breaks[lmr] # NIL THEN result.numDogLegs ← result.numDogLegs + 1;
ENDLOOP};
DoBreak: PROC [routingArea: Route.RoutingArea, fullSegBreak: FullSegBreakSpec] = {
break the segment at position:
add pin position at fullSegBreak.breaks[mumble].pos
unlink segBreak
create 2 new segments
link in the pins
UnlinkSegFromPins: RouteChannel.EachPinActionProc ~ {
IF pin.conctSeg[chanLeft] = oldSeg THEN pin.conctSeg[chanLeft] ← NIL;
IF pin.conctSeg[chanRight] = oldSeg THEN pin.conctSeg[chanRight] ← NIL;
IF pin.altConctSeg[chanLeft] = oldSeg THEN pin.altConctSeg[chanLeft] ← NIL;
IF pin.altConctSeg[chanRight] = oldSeg THEN pin.altConctSeg[chanRight] ← NIL;
};
chanData: RouteChannel.ChannelData ← NARROW[routingArea.privateData];
chanPins: RouteChannel.RoutingChannelPins ← chanData.chanPins;
parms: RoutePrivate.RoutingAreaParms ← NARROW[routingArea.parms];
oldSeg: RouteChannel.Segment ← fullSegBreak.seg;
branchWidth: Route.Number ← oldSeg.net.branchWidth;
trunkWidth: Route.Number ← oldSeg.net.trunkWidth;
IF BreaksFound[fullSegBreak] # 1 THEN
Route.Error[programmingError, "Not suppose to happen"];
[] ← RouteChannel.EnumPinsOnSeg[routingArea, oldSeg, UnlinkSegFromPins];
FOR lmr: Lmr IN Lmr DO
segBreak: SegBreakSpec ← fullSegBreak.breaks[lmr];
IF segBreak # NIL THEN {
pinIndex: RouteChannel.ZMPinsOnCh ← RouteChannel.FindPinPos[routingArea, segBreak.pos];
pinPosition: RouteChannel.PinPosition ← chanPins.sides[pinIndex];
upperPin, lowerPin: RouteChannel.ChanPin ← NIL;
pinListPair: ChanPinListPair;
seg1: RouteChannel.Segment ← NEW[RouteChannel.SegmentRec ← [net: oldSeg.net, qWidth: trunkWidth, exitBreak: oldSeg.exitBreak]];
seg2: RouteChannel.Segment ← NEW[RouteChannel.SegmentRec ← [net: oldSeg.net, qWidth: trunkWidth, exitBreak: oldSeg.exitBreak]];
SELECT segBreak.type FROM
dogLeg => {
exitsSeparate: BOOLEANIF parms.routerUsed = channel THEN FALSE ELSE TRUE;
pinLists: ChanPinListSet ← GetPins[exitsSeparate, oldSeg];
parms.widestPin ← MAX[branchWidth, parms.widestPin];
upperPin ← lowerPin ← NEW[RouteChannel.ChanPinRec ← [pinSide: none, qLoc: 0, pWidth: branchWidth, kindOfPin: dogLeg, pinPosition: pinPosition]];
pinPosition.innerPins ← CONS[upperPin, pinPosition.innerPins];
pinListPair ← DividePins[lmr, pinLists, lowerPin, upperPin]};
exit => {
pinSide: RouteChannel.ChanLRSide ←
IF segBreak.pos <= chanPins.cEnd1 THEN chanLeft
ELSE IF segBreak.pos >= chanPins.cEnd2 THEN chanRight
ELSE Route.Error[programmingError, "Invalid data. Call maintainer."];
pinLists: ChanPinListSet ← GetPins[TRUE, oldSeg];
seg1.exitBreak ← TRUE;
seg2.exitBreak ← TRUE;
upperPin ← NEW[RouteChannel.ChanPinRec ← [pinSide: pinSide, qLoc: 0, pWidth: 0, kindOfPin: exitPin, pinPosition: pinPosition]];
pinPosition.innerPins ← CONS[upperPin, pinPosition.innerPins];
if this segment already has an exit on this side, then use that one, otherwise make a new pin
lowerPin ← IF pinSide = chanRight THEN pinLists.rightExit ELSE pinLists.leftExit;
IF lowerPin = NIL THEN {
lowerPin ← NEW[RouteChannel.ChanPinRec ← [pinSide: pinSide, qLoc: 0, pWidth: 0, kindOfPin: exitPin, pinPosition: pinPosition]];
pinPosition.innerPins ← CONS[lowerPin, pinPosition.innerPins]}
ELSE {
};
pinListPair ← DividePins[lmr, pinLists, lowerPin, upperPin];
};
ENDCASE;
LinkSegsToPins[seg1, pinListPair.list1, lowerPin];
LinkSegsToPins[seg2, pinListPair.list2, upperPin];
SetTrackConstraints[routingArea, seg1, oldSeg.trackConstraint];
SetTrackConstraints[routingArea, seg2, oldSeg.trackConstraint];
TerminalIO.WriteRope[Rope.Cat["\ntrunk segment for net: ", fullSegBreak.seg.net.name, " divided at: "]];
TerminalIO.WriteInt[chanPins.sides[pinIndex].pLoc/routingArea.rules.CDLambda];
remove these statments for production
-- RouteChannel.AuditPins[routingArea];
-- RouteChannel.AuditSegs[routingArea];
};
ENDLOOP;
};
DividePins: PROC [which: Lmr, pinLists: ChanPinListSet, pin1, pin2: RouteChannel.ChanPin] RETURNS [pinListPair: ChanPinListPair ← [NIL, NIL]] = {
SELECT which FROM
left => {
IF pinLists.leftExit = NIL THEN Route.Error[programmingError, "exit dogleg with no exit"];
pinListPair.list1 ← LIST[pin1, pinLists.leftExit];
pinListPair.list2 ← RouteChannel.Combine[pinLists.bottomList, pinLists.topList, LIST[pinLists.rightExit, pin2]]};
middle => {
pinListPair.list1 ← RouteChannel.Combine[LIST[pin1], pinLists.bottomList, NIL];
pinListPair.list2 ← RouteChannel.Combine[LIST[pin2], pinLists.topList, NIL];
pinListPair ← AddToClosestList[pinListPair, pinLists.leftExit];
pinListPair ← AddToClosestList[pinListPair, pinLists.rightExit]};
right => {
IF pinLists.rightExit = NIL THEN Route.Error[programmingError, "exit dogleg with no exit"];
pinListPair.list1 ← LIST[pin1, pinLists.rightExit];
pinListPair.list2 ← RouteChannel.Combine[pinLists.bottomList, pinLists.topList, LIST[pinLists.leftExit, pin2]]};
ENDCASE;
};
SetTrackConstraints: PROC [routingArea: Route.RoutingArea, seg: RouteChannel.Segment, trackConstraint: Route.Number] = {
EachPin: RouteChannel.EachPinActionProc = {
IF pin # NIL THEN {
IF pin.trackConstraint # 0 THEN
seg.trackConstraint ← pin.trackConstraint}};
[] ← RouteChannel.EnumPinsOnSeg[routingArea, seg, EachPin] };
AddToClosestList: PROC [pinListPair: ChanPinListPair, pin: RouteChannel.ChanPin] RETURNS [result: ChanPinListPair] ~ {
l1Range: RoutePrivate.Range ← RouteChannel.GetRange[pinListPair.list1];
l2Range: RoutePrivate.Range ← RouteChannel.GetRange[pinListPair.list2];
IF pin # NIL THEN {
pLoc: Route.Number ← pin.pinPosition.pLoc;
IF l1Range.l <= pLoc AND pLoc <= l1Range.r THEN RETURN[[CONS[pin, pinListPair.list1], pinListPair.list2]]
ELSE IF l2Range.l <= pLoc AND pLoc <= l2Range.r THEN RETURN[[pinListPair.list1, CONS[pin, pinListPair.list2]]]
ELSE {
distToL1: Route.Number ← MIN[ABS[pLoc - l1Range.l], ABS[pLoc - l1Range.r]];
distToL2: Route.Number ← MIN[ABS[pLoc - l2Range.l], ABS[pLoc - l2Range.r]];
IF distToL1 < distToL2 THEN RETURN[[CONS[pin, pinListPair.list1], pinListPair.list2]]
ELSE RETURN[[pinListPair.list1, CONS[pin, pinListPair.list2]]]}}
ELSE RETURN[pinListPair]};
LinkSegsToPins: PROC [seg: RouteChannel.Segment, pinList: RouteChannel.ChanPinList, newPin: RouteChannel.ChanPin] = {
link the segment to the pin in the list and vice versa
PinCompare: List.CompareProc = {
p1: Route.Number ← NARROW[ref1, RouteChannel.ChanPin].pinPosition.pLoc;
p2: Route.Number ← NARROW[ref2, RouteChannel.ChanPin].pinPosition.pLoc;
RETURN[IF p1 < p2 THEN Basics.Comparison.less
ELSE IF p1 = p2 THEN Basics.Comparison.equal
ELSE Basics.Comparison.greater]};
mungedPinList, sortedPinList: List.LORA;
leftPin, rightPin: RouteChannel.ChanPin;
Use Reverse to get a new copy of the list because Sort is destructive
TRUSTED{mungedPinList ← List.Reverse[LOOPHOLE[pinList]]};
sortedPinList ← List.Sort[mungedPinList, PinCompare];
rightPin ← NARROW[List.NthElement[sortedPinList, -1]];
leftPin ← NARROW[List.NthElement[sortedPinList, 1]];
FOR pList: List.LORA -- RouteChannel.ChanPinList -- ← sortedPinList, pList.rest WHILE pList # NIL DO
chanPin: RouteChannel.ChanPin ← NARROW[pList.first];
IF chanPin = leftPin THEN {
update old seg pointer
IF chanPin # newPin THEN {chanPin.conctSeg[chanRight] ← seg}
-- chanPin.conctSeg[chanLeft] ← NIL
ELSE
no old seg pointer, but make sure both segs on new pin are initialized
{IF chanPin.conctSeg[chanRight] = NIL THEN chanPin.conctSeg[chanRight] ← seg
ELSE chanPin.altConctSeg[chanRight] ← seg};
seg.exteriorPins[chanLeft] ← chanPin}
ELSE IF chanPin = rightPin THEN {IF chanPin # newPin THEN
update old seg pointer
{chanPin.conctSeg[chanLeft] ← seg; -- chanPin.conctSeg[chanRight] ← NIL -- }
ELSE
no old seg pointer, but make sure both segs on new pin are initialized
{IF chanPin.conctSeg[chanLeft] = NIL THEN chanPin.conctSeg[chanLeft] ← seg
ELSE chanPin.altConctSeg[chanLeft] ← seg};
seg.exteriorPins[chanRight] ← chanPin}
ELSE {seg.interiorPins ← CONS[chanPin, seg.interiorPins];
SELECT chanPin.kindOfPin FROM
chanConnect, compPin => {
chanPin.conctSeg[chanRight] ← seg; chanPin.conctSeg[chanLeft] ← seg};
dogLeg => {
IF chanPin.conctSeg[chanRight] = NIL AND chanPin.conctSeg[chanLeft] = NIL THEN
{chanPin.conctSeg[chanRight] ← seg; chanPin.conctSeg[chanLeft] ← seg}
ELSE
{chanPin.altConctSeg[chanLeft] ← seg; chanPin.altConctSeg[chanRight] ← seg}};
exitPin => Route.Error[programmingError, "Exit pin not on end of segment"];
ENDCASE};
ENDLOOP};
AddSeg: PROC [routingArea: Route.RoutingArea, density: RouteChannel.Density, r: RoutePrivate.Range, width: Route.Number] RETURNS [maxDensity: Route.Number ← 0] = {
compute the track density when this range is added
chanData: RouteChannel.ChannelData ← NARROW[routingArea.privateData];
chanPins: RouteChannel.RoutingChannelPins ← chanData.chanPins;
IF density # NIL THEN
FOR index: RouteChannel.MPinsOnCh IN [1 .. chanPins.count] DO
pos: Route.Number ← chanPins.sides[index].pLoc;
thisDensity: Route.Number ← IF r.l <= pos AND pos <= r.r THEN density.values[index] + width
ELSE density.values[index];
maxDensity ← MAX[maxDensity, thisDensity];
ENDLOOP};
CompareResult: PROC [r1, r2: BreakResult] RETURNS [result: Basics.Comparison] = {
compare r1 and r2
result ← RouteUtil.SimpleCompare[r1.numDogLegs, r2.numDogLegs];
IF result # equal THEN RETURN;
result ← RouteUtil.SimpleCompare[r1.deltaDensity, r2.deltaDensity];
IF result # equal THEN RETURN;
result ← RouteUtil.SimpleCompare[r1.duplicateLength, r2.duplicateLength];
RETURN};
ClosestPins: PROC [routingArea: Route.RoutingArea, thisPLoc: Route.Number] RETURNS [nextLower, nextHigher: RouteChannel.ZMPinsOnCh ← 0] = {
find the PinPosition closest to thisPLoc.
chanData: RouteChannel.ChannelData ← NARROW[routingArea.privateData];
chanPins: RouteChannel.RoutingChannelPins ← chanData.chanPins;
found: BOOLEANFALSE;
FOR pIndex: RouteChannel.ZMPinsOnCh IN [1 .. chanPins.count] WHILE ~found DO
pLoc: Route.Number ← chanPins.sides[pIndex].pLoc;
IF pLoc = thisPLoc THEN
{found ← TRUE; nextLower ← nextHigher ← pIndex}
ELSE IF pLoc > thisPLoc THEN
{found ← TRUE; nextHigher ← pIndex;
nextLower ← IF pIndex > 1 THEN pIndex -1 ELSE 1}
ENDLOOP;
IF ~found THEN { -- this pin goes after the last pin
nextLower ← nextHigher ← chanPins.count};
};
GetPins: PROC [exitsSeparate: BOOLEAN, seg: RouteChannel.Segment] RETURNS [pinLists: ChanPinListSet ← [NIL, NIL, NIL, NIL]] = {
get the pins attached to the segment on the indicated side
bottomList == lowerPinList and topList == upperPinList
IncludePin: PROC [pin: RouteChannel.ChanPin] = {
IF pin.pinSide = chanBottom THEN pinLists.bottomList ← CONS[pin, pinLists.bottomList]
ELSE IF pin.pinSide = chanTop THEN pinLists.topList ← CONS[pin, pinLists.topList]
ELSE IF pin.kindOfPin = dogLeg THEN dogLegList ← CONS[pin, dogLegList]};
IncludeExit: PROC [pin: RouteChannel.ChanPin, chanSide: RouteChannel.ChanSide] = {
IF pin.kindOfPin = exitPin THEN
{SELECT exitsSeparate FROM
FALSE => {
Compiler problem: [pinLists.bottomList, pinLists.topList] ← AddToClosestList[[pinLists.bottomList, pinLists.topList], pin]};
result: ChanPinListPair ← AddToClosestList[[pinLists.bottomList, pinLists.topList], pin];
pinLists.bottomList ← result.list1;
pinLists.topList ← result.list2};
TRUE => {
IF pin.pinPosition.pLoc = leftPin.pinPosition.pLoc THEN pinLists.leftExit ← pin
ELSE pinLists.rightExit ← pin};
ENDCASE => Route.Error[programmingError, "Invalid Router."]};
};
first include the obvious pins: top, bottom and dogleg
dogLegList: RouteChannel.ChanPinList ← NIL;
leftPin: RouteChannel.ChanPin ← seg.exteriorPins[chanLeft];
rightPin: RouteChannel.ChanPin ← seg.exteriorPins[chanRight];
IncludePin[leftPin];
IncludePin[rightPin];
FOR list: RouteChannel.ChanPinList ← seg.interiorPins, list.rest WHILE list # NIL DO
IncludePin[list.first];
ENDLOOP;
next decide which segments the exit pins go in
IncludeExit[leftPin, chanLeft];
IncludeExit[rightPin, chanRight];
next decide which segments the dogleg pins go in
FOR list: RouteChannel.ChanPinList ← dogLegList, list.rest WHILE list # NIL DO
Compiler problem: [pinLists.bottomList, pinLists.topList] ← AddToClosestList[[pinLists.bottomList, pinLists.topList], list.first];
result: ChanPinListPair ← AddToClosestList[[pinLists.bottomList, pinLists.topList], list.first];
pinLists.bottomList ← result.list1;
pinLists.topList ← result.list2;
ENDLOOP;
};
SegRanges: PROC [routingArea: Route.RoutingArea, pinLists: ChanPinListSet] RETURNS [rangeList: RangeWithDirList] = {
find distinct ranges for this seg, use enumeration
chanData: RouteChannel.ChannelData ← NARROW[routingArea.privateData];
chanPins: RouteChannel.RoutingChannelPins ← chanData.chanPins;
lr: RoutePrivate.Range ← RouteChannel.GetRange[pinLists.bottomList];
ur: RoutePrivate.Range ← RouteChannel.GetRange[pinLists.topList];
ce1: Route.Number ← chanPins.cEnd1;
ce2: Route.Number ← chanPins.cEnd2;
min: Route.Number ← MIN[lr.l, ur.l];
max: Route.Number ← MAX[lr.r, ur.r];
left: RangeWithDir ← IF ce1 < min THEN [[ce1, min], rightToLeft] ELSE [[ce1, ce1], rightToLeft];
right: RangeWithDir ← IF ce2 > max THEN [[max, ce2], leftToRight] ELSE [[ce2, ce2], leftToRight];
SELECT TRUE FROM
lr.r < lr.l OR ur.r < ur.l =>
rangeList ← LIST[RangeWithDir[[ce1, ce2], leftToRight]];
lr.r < ur.l =>
-- ur: ———————
-- lr: —————
{gap: RangeWithDir ← [[lr.r, ur.l], leftToRight];
rangeList ← LIST[gap, [lr, rightToLeft], [ur, leftToRight], left, right]};
(lr.l <= ur.l AND ur.l <= lr.r) AND (ur.l <= lr.r AND lr.r <= ur.r) =>
-- ur: ———————
-- lr: ———————
{dual: RangeWithDir ← [[ur.l, lr.r], leftToRight];
ls: RangeWithDir ← [[lr.l, dual.range.l], rightToLeft];
rs: RangeWithDir ← [[dual.range.r, ur.r], leftToRight];
rangeList ← LIST[dual, ls, rs, left, right]};
(lr.l <= ur.l AND ur.l < lr.r) AND (lr.l <= ur.r AND ur.r <= lr.r) =>
-- ur: ———————
lr: ————————————
{ls: RangeWithDir ← [[lr.l, ur.l], rightToLeft];
rs: RangeWithDir ← [[ur.r, lr.r], leftToRight];
rangeList ← LIST[[ur, leftToRight], ls, rs, left, right]};
(ur.l <= lr.l AND lr.l <= ur.r) AND (ur.l <= lr.r AND lr.r <= ur.r) =>
ur: ————————————
-- lr: ———————
{ls: RangeWithDir ← [[ur.l, lr.l], rightToLeft];
rs: RangeWithDir ← [[lr.r, ur.r], leftToRight];
rangeList ← LIST[[lr, leftToRight], ls, rs, left, right]};
(ur.l <= lr.l AND lr.l <= ur.r) AND (lr.l <= ur.r AND ur.r <= lr.r) =>
-- ur: ———————
-- lr: ————————————
{dual: RangeWithDir ← [[lr.l, ur.r], leftToRight];
ls: RangeWithDir ← [[ur.l, dual.range.l], rightToLeft];
rs: RangeWithDir ← [[dual.range.r, lr.r], leftToRight];
rangeList ← LIST[dual, ls, rs, left, right]};
ur.r < lr.l =>
-- ur: ———————
-- lr: ———————
{gap: RangeWithDir ← [[ur.r, lr.l], leftToRight];
rangeList ← LIST[gap, [lr, leftToRight], [ur, rightToLeft], left, right]};
ENDCASE => Route.Error[programmingError, "Not suppose to happen."]};
BreaksFound: PROCEDURE [break: FullSegBreakSpec] RETURNS [numBreaks: INT ← 0] = {
FOR lmr: Lmr IN Lmr DO
IF break.breaks[lmr] # NIL THEN numBreaks ← numBreaks + 1;
ENDLOOP};
}.