RouteChannelConstraintsImpl.mesa
Copyright Ó 1985, 1986, 1987 by Xerox Corporation. All rights reserved.
by Bryan Preas July 10, 1985 6:57:00 pm PDT
last edited by Bryan Preas July 16, 1987 8:36:23 pm PDT
Christian Le Cocq January 11, 1988 12:45:14 pm PST
DIRECTORY
Basics, CD, DABasics, List, IO, Rope, Route, RouteChannel, RouteDiGraph, RoutePrivate, RouteUtil, RTBasic, TerminalIO;
RouteChannelConstraintsImpl:
CEDAR
PROGRAM
IMPORTS Basics, List, IO, Rope, Route, RouteChannel, RouteDiGraph, RouteUtil, RTBasic, TerminalIO
EXPORTS RouteChannel = {
SegBreakType: TYPE = {dogLeg, exit}; -- should add pinDogLeg sometime
SegBreakSpec: TYPE = REF SegBreakSpecRec;
SegBreakSpecRec:
TYPE =
RECORD [
pos: DABasics.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: DABasics.Number,
duplicateLength: DABasics.Number,
numDogLegs: DABasics.Number];
RangeWithDirList: TYPE = LIST OF RangeWithDir;
RangeWithDir:
TYPE =
RECORD [
range: RTBasic.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];
TestPins: TYPE = REF TestPinsRec;
TestPinsRec:
TYPE =
RECORD [
trialPin, leftExitPin, rightExitPin: RouteChannel.ChanPin ← NIL];
GenerateConstraints:
PUBLIC PROC [chanData: RouteChannel.ChannelData,
parms: RoutePrivate.RoutingAreaParms,
rules: Route.DesignRules,
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
chanPins: RouteChannel.RoutingChannelPins ← chanData.chanPins;
graphName: Rope.ROPE ← "Vertical Constraints";
segBroken: BOOLEAN ← TRUE;
trialPinPosition: RouteChannel.PinPosition ← NEW[RouteChannel.PinPositionRec ← [pinIndex: 0, pLoc: 0]];
trialPin: RouteChannel.ChanPin ← NEW[RouteChannel.ChanPinRec ← [pinSide: none, qLoc: 0, pWidth: 0, 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: 0, 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: 0, kindOfPin: exitPin, pinPosition: rightExitPosition]];
pins: TestPins ← NEW[TestPinsRec ← [trialPin, leftExitPin, rightExitPin]];
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[chanData]; -- 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, RouteUtil.GetWidthWithContact[rules, pin.pWidth]/2]};
LimitProc: RouteChannel.EachPinActionProc = {
IF pin #
NIL
THEN
{width: DABasics.Number ← RouteUtil.GetWidthWithContact[rules, pin.pWidth]/2;
pinPos: DABasics.Number ← pin.pinPosition.pLoc;
IF pinPos = pLoc
THEN
quit ← TRUE
ELSE
IF pinPos < pLoc
THEN
quit ← pinPos + width + rules.branchSpacing > pLoc - widestPinD2
ELSE
-- pinPos >= pLoc
quit ← pLoc + widestPinD2 + rules.branchSpacing > pinPos - width}};
pinPosition: RouteChannel.PinPosition ← chanPins.sides[index];
pLoc: DABasics.Number ← pinPosition.pLoc;
widestPinD2: DABasics.Number ← RouteUtil.GetWidthWithContact[rules, rules.branchWidth]/2;
minLimit, maxLimit: RouteChannel.MPinsOnCh;
generate constraints for this coordinate, if any
[] ← RouteChannel.EnumPins[pinPosition, WidestPinProc];
[minLimit, maxLimit] ← RouteChannel.FindConstraintLimits[chanPins, parms, rules, 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[chanData, parms, rules, upperPin, lowerPin, middle, pins] 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[chanData, parms, rules, upperPin, innerPin, middle, pins] THEN GOTO GoRound;
IF ProcessConstraints[chanData, parms, rules, innerPin, lowerPin, middle, pins] THEN GOTO GoRound;
ENDLOOP; -- FOR innerPins
ENDLOOP;
-- FOR upperIndex
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: DABasics.Number ← NARROW[ref1, RouteChannel.ChanPin].qLoc;
p2: DABasics.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: List.LORA ← ConvertToLORA[pinPosition.innerPins];
sortedPinList: List.LORA ← 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[chanData, parms, rules, upperPin, lowerPin, whichEnd, pins] 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[chanPins, parms, rules, seg, NIL, whichEnd, pins];
IF BreaksFound[break] > 0
THEN {
DoBreak[chanPins, parms, break]; GOTO GoRound}
ELSE {
-- mark seg as failed --
seg.failed ← TRUE;
Route.Signal[noResource, Rope.Cat["\nunable to find a place to dogleg, net: ", seg.net.name, " failed"]]}};
IF index = chanPins.count
THEN {
Must resolve constraints accross the ends of the switchbox. If there is a constraint from a segment on one end to a segment on the other, it must be resolved.
leftPinPosition: RouteChannel.PinPosition ← chanPins.sides[1];
leftPinList: RouteChannel.ChanPinList ← leftPinPosition.innerPins;
these are the pins on the left side of the channel
FOR lPList: RouteChannel.ChanPinList ← leftPinList, lPList.rest
WHILE lPList #
NIL
DO
leftPin: RouteChannel.ChanPin ← NARROW[lPList.first];
lSList: RouteChannel.SegmentList ← RouteChannel.GetSegsOnPin[leftPin];
these are the segments on the left pin
FOR lSegs: RouteChannel.SegmentList ← lSList, lSegs.rest
WHILE lSegs #
NIL
DO
graph: RouteDiGraph.Graph ← chanData.constraints;
leftSeg: RouteChannel.Segment ← lSegs.first;
leftSegNode: RouteDiGraph.Node ← leftSeg.constraintNode;
rightSegNode: RouteDiGraph.Node ← seg.constraintNode;
leftToRightSegList: RouteChannel.SegmentList ← SegsInCycle[graph, leftSegNode, rightSegNode];
rightToLeftSegList: RouteChannel.SegmentList;
IF leftToRightSegList #
NIL
THEN
choose a segment to break and the position to dogleg
{density: RouteChannel.Density ← RouteChannel.ComputeDensity[chanPins, rules];
segBreak: FullSegBreakSpec ← FindBreak[chanPins, parms, rules, leftToRightSegList, density, whichEnd, pins];
IF BreaksFound[segBreak] > 0 THEN DoBreak[chanPins, parms, segBreak]
ELSE {
-- choose a victim --
lSegs.first.failed ← TRUE;
Route.Signal[noResource, Rope.Cat["\nnet: ", lSegs.first.net.name, " failed, unable to find a place to dogleg"]]};
segBroken ← TRUE; GOTO GoRound};
rightToLeftSegList ← SegsInCycle[graph, rightSegNode, leftSegNode];
IF rightToLeftSegList #
NIL
THEN
choose a segment to break and the position to dogleg
{density: RouteChannel.Density ← RouteChannel.ComputeDensity[chanPins, rules];
segBreak: FullSegBreakSpec ← FindBreak[chanPins, parms, rules, rightToLeftSegList, density, whichEnd, pins];
IF BreaksFound[segBreak] > 0 THEN DoBreak[chanPins, parms, segBreak]
ELSE {
-- choose a victim --
lSegs.first.failed ← TRUE;
Route.Signal[noResource, Rope.Cat["\nnet: ", lSegs.first.net.name, " failed, unable to find a place to dogleg"]]};
segBroken ← TRUE; GOTO GoRound};
next check if the external segments are in the same track, they overlap, and they are in different nets
IF seg.trackConstraint = leftSeg.trackConstraint
AND RTBasic.Overlaps[RouteChannel.SegRange[seg], RouteChannel.SegRange[leftSeg]]
AND seg.net # leftSeg.net
THEN
choose a segment to break and the position to dogleg
{density: RouteChannel.Density ← RouteChannel.ComputeDensity[chanPins, rules];
segBreak: FullSegBreakSpec ← FindBreak[chanPins, parms, rules, LIST[seg, leftSeg], density, whichEnd, pins];
IF BreaksFound[segBreak] > 0 THEN DoBreak[chanPins, parms, segBreak]
ELSE {
-- choose a victim --
seg.failed ← TRUE;
Route.Signal[noResource, Rope.Cat["\nnet: ", seg.net.name, " failed, unable to find a place to dogleg"]]};
segBroken ← TRUE; GOTO GoRound};
ENDLOOP;
ENDLOOP;
};
ENDLOOP;
ENDLOOP};
REPEAT GoRound => segBroken ← TRUE;
ENDLOOP; -- WHILE index
ENDLOOP; -- WHILE segBroken
RETURN[
TRUE]};
-- GenerateConstraints
DestroyOldConstraints:
PUBLIC
PROC [chanData: RouteChannel.ChannelData] = {
must explicitly destroy the old data
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[pinPosition, ClearConstraints];
ENDLOOP;
RouteDiGraph.DestroyGraph[chanData.constraints, DestroyGraph, DestroyNode, DestroyArc]};
ProcessConstraints:
PROC [chanData: RouteChannel.ChannelData, parms: RoutePrivate.RoutingAreaParms, rules: Route.DesignRules, upperPin, lowerPin: RouteChannel.ChanPin, whichEnd: Lmr, pins: TestPins]
RETURNS [segBroken:
BOOLEAN ←
FALSE] = {
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[rules, 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[chanData, parms, rules, lowerSeg, upperSeg, whichEnd, pins] THEN segBroken ← TRUE;
ENDLOOP; -- FOR upperSegIndex
ENDLOOP; -- FOR lowerSegIndex
};
Constraining:
PROC [rules: Route.DesignRules, pin1, pin2: RouteChannel.ChanPin]
RETURNS [constraining:
BOOLEAN ←
FALSE] = {
determining if pin1 actually constrains pin2
IF pin1 #
NIL
AND pin2 #
NIL
THEN
{p1: DABasics.Number ← pin1.pinPosition.pLoc;
w1WContact: DABasics.Number ← RouteUtil.GetWidthWithContact[rules, pin1.pWidth]/2;
w1: DABasics.Number ← pin1.pWidth/2;
p2: DABasics.Number ← pin2.pinPosition.pLoc;
w2WContact: DABasics.Number ← RouteUtil.GetWidthWithContact[rules, pin2.pWidth]/2;
w2: DABasics.Number ← pin2.pWidth/2;
IF p1 = p2
THEN
constraining ← TRUE
ELSE
IF p1 < p2
THEN
constraining ← (p1 + w1WContact + rules.branchSpacing > p2 - w2)
OR (p1 + w1 + rules.branchSpacing > p2 - w2WContact)
ELSE
-- p1 > p2
constraining ← (p2 + w2WContact + rules.branchSpacing > p1 - w1)
OR (p2 + w2 + rules.branchSpacing > p1 - w1WContact)}};
DoConstraint:
PROC [chanData: RouteChannel.ChannelData, parms: RoutePrivate.RoutingAreaParms, rules: Route.DesignRules, lowerSeg, upperSeg: RouteChannel.Segment, whichEnd: Lmr, pins: TestPins]
RETURNS [segBroken:
BOOLEAN ←
FALSE] = {
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.num # upperSeg.net.num
THEN {
segList: RouteChannel.SegmentList;
chanPins: RouteChannel.RoutingChannelPins ← chanData.chanPins;
graph: RouteDiGraph.Graph ← chanData.constraints;
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[chanPins, rules];
segBreak: FullSegBreakSpec ← FindBreak[chanPins, parms, rules, segList, density, whichEnd, pins];
IF BreaksFound[segBreak] > 0 THEN DoBreak[chanPins, parms, segBreak]
ELSE {
-- choose a victim --
segList.first.failed ← TRUE;
Route.Signal[noResource, 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 [chanPins: RouteChannel.RoutingChannelPins,
parms: RoutePrivate.RoutingAreaParms,
rules: Route.DesignRules,
segList: RouteChannel.SegmentList,
density: RouteChannel.Density,
whichEnd: Lmr,
pins: TestPins] 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[chanPins, parms, rules, seg, density, whichEnd, pins];
result: BreakResult ← EvalBreak[chanPins, parms, 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 [chanPins: RouteChannel.RoutingChannelPins,
parms: RoutePrivate.RoutingAreaParms,
rules: Route.DesignRules,
seg: RouteChannel.Segment,
density: RouteChannel.Density,
whichEnd: Lmr,
pins: TestPins]
RETURNS [break: FullSegBreakSpec] = {
find the best position to break this seg
exitsSeparate: BOOLEAN ← IF parms.routerUsed = channel THEN FALSE ELSE TRUE;
pinLists: ChanPinListSet ← GetPins[exitsSeparate, seg];
rangeList: RangeWithDirList ← SegRanges[chanPins, 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[chanPins, parms, rules, seg, ranges.first, pins];
IF break.breaks[middle] # NIL THEN EXIT;
ENDLOOP;
IF break.breaks[middle] =
NIL
AND seg.net.mayExit
THEN
break.breaks[middle] ← BreakAtExit[chanPins, parms, 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[chanPins, parms, rules, seg, ranges.first, pins];
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[chanPins, parms, rules, seg, leftRange, pins];
};
};
DoRight:
PROC [] ~ {
IF right
AND (top
OR left
OR bottom)
AND BreaksFound[break] = 0
THEN {
rightRange: RangeWithDir ← [[cEnd1, cEnd2], rightToLeft];
break.breaks[right] ← BreakWithInRange[chanPins, parms, rules, seg, rightRange, pins];
};
};
cEnd1: DABasics.Number ← chanPins.cEnd1;
cEnd2: DABasics.Number ← chanPins.cEnd2;
left, top, right, bottom: BOOLEAN;
[left, top, right, bottom] ← RouteChannel.PinsOnSide[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 [chanPins: RouteChannel.RoutingChannelPins,
parms: RoutePrivate.RoutingAreaParms,
rules: Route.DesignRules,
seg: RouteChannel.Segment,
range: RangeWithDir,
pins: TestPins]
RETURNS [break: SegBreakSpec ← NIL] = {
find the best position to break this seg within this range
WidestPinProc: RouteChannel.EachPinActionProc = {
IF pin #
NIL
THEN
widestPinD2 ← MAX[widestPinD2, RouteUtil.GetWidthWithContact[rules, pin.pWidth]/2]};
NextPosToRight:
PROC [pinIndex: RouteChannel.ZMPinsOnCh]
RETURNS[pos: DABasics.Number] ~ {
IF pinIndex = 0
THEN
pos ← chanPins.cEnd1 + rules.branchSpacing + seg.net.branchWidth
ELSE
IF pinIndex >= chanPins.count+1
THEN
pos ← LAST[INT]
ELSE {
pinPosition: RouteChannel.PinPosition ← chanPins.sides[pinIndex];
widestPinD2 ← minPinD2;
[] ← RouteChannel.EnumPins[pinPosition, WidestPinProc];
pos ← pinPosition.pLoc + widestPinD2 + rules.branchSpacing + RouteUtil.GetWidthWithContact[rules, seg.net.branchWidth]/2}};
NextPosToLeft:
PROC [pinIndex: RouteChannel.ZMPinsOnCh]
RETURNS[pos: DABasics.Number] ~ {
IF pinIndex <= 0
THEN
pos ← FIRST[INT]
ELSE
IF pinIndex = chanPins.count
THEN
pos ← chanPins.cEnd2 - rules.branchSpacing - seg.net.branchWidth
ELSE {
pinPosition: RouteChannel.PinPosition ← chanPins.sides[pinIndex];
widestPinD2 ← minPinD2;
[] ← RouteChannel.EnumPins[pinPosition, WidestPinProc];
pos ← pinPosition.pLoc - widestPinD2 - rules.branchSpacing - RouteUtil.GetWidthWithContact[rules, seg.net.branchWidth]/2}};
minPinD2: DABasics.Number ← RouteUtil.GetWidthWithContact[routingArea, routingArea.rules.branchWidth]/2;
minPinD2: DABasics.Number ← rules.branchWidth/2;
widestPinD2: DABasics.Number;
SELECT range.dir
FROM
leftToRight => {
nextLower: RouteChannel.ZMPinsOnCh ← ClosestPins[chanPins, range.range.l].nextLower;
FOR pos: DABasics.Number ← range.range.l, NextPosToRight[nextLower]
WHILE pos <= range.range.r
DO
IF ~DogLegNotAllowed[chanPins, parms, rules, seg, pos, pins]
THEN {
break ← NEW[SegBreakSpecRec ← [pos, dogLeg]];
EXIT};
nextLower ← MIN[chanPins.count+1, nextLower + 1];
ENDLOOP};
rightToLeft => {
nextHigher: RouteChannel.ZMPinsOnCh ← ClosestPins[chanPins, range.range.r].nextHigher;
FOR pos: DABasics.Number ← range.range.r, NextPosToLeft[nextHigher]
WHILE pos >= range.range.l
DO
IF ~DogLegNotAllowed[chanPins, parms, rules, seg, pos, pins]
THEN {
break ← NEW[SegBreakSpecRec ← [pos, dogLeg]];
EXIT};
nextHigher ← MAX[0, nextHigher - 1];
ENDLOOP};
ENDCASE};
DogLegNotAllowed:
PROC [chanPins: RouteChannel.RoutingChannelPins,
parms: RoutePrivate.RoutingAreaParms,
rules: Route.DesignRules,
seg: RouteChannel.Segment,
pos: DABasics.Number,
pins: TestPins]
RETURNS [notAllowed: BOOLEAN ← FALSE] = {
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[rules, pin, pins.trialPin] THEN quit ← TRUE};
OuterConstraints: RouteChannel.EachPinActionProc = {
IF pin #
NIL
THEN
IF pin.kindOfPin = chanConnect
OR pin.kindOfPin = compPin
THEN
IF Constraining[rules, pin, pins.trialPin]
THEN quit ←
TRUE};
minLimit, maxLimit, leftIndex, rightIndex: RouteChannel.ZMPinsOnCh;
width: DABasics.Number ← MAX[seg.net.trunkWidth, seg.net.branchWidth];
pins.trialPin.pinPosition.pLoc ← pos;
pins.trialPin.pWidth ← width;
pins.leftExitPin.pWidth ← width;
pins.rightExitPin.pWidth ← width;
[leftIndex, rightIndex] ← ClosestPins[chanPins, pos];
must reserve place for future exits
IF Constraining[rules, pins.trialPin, pins.leftExitPin] THEN notAllowed ← TRUE;
IF Constraining[rules, pins.trialPin, pins.rightExitPin] THEN notAllowed ← TRUE;
see if inner pins interfere
[minLimit, maxLimit] ← RouteChannel.FindConstraintLimits[chanPins, parms, rules, 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[pinPosition, CheckInner];
ENDLOOP;
see if outer pins interfere
[minLimit, maxLimit] ← RouteChannel.FindConstraintLimits[chanPins, parms, rules, 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[rules, topPin, pins.trialPin];
constrainBottom: BOOLEAN ← Constraining[rules, bottomPin, pins.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[rules, topPin, bP] AND constrainTop AND constrainBottom THEN notAllowed ← TRUE;
IF topNet = bN AND Constraining[rules, 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 [chanPins: RouteChannel.RoutingChannelPins, parms: RoutePrivate.RoutingAreaParms, seg: RouteChannel.Segment, density: RouteChannel.Density]
RETURNS [break: SegBreakSpec] = {
find the best exit to break this seg
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[chanPins, parms, leftFullBreak, density];
rightResult: BreakResult ← EvalBreak[chanPins, parms, rightFullBreak, density];
IF CompareResult[leftResult, rightResult] = less THEN RETURN [leftBreak]
ELSE RETURN [rightBreak]};
EvalBreak:
PROC [chanPins: RouteChannel.RoutingChannelPins, parms: RoutePrivate.RoutingAreaParms, break: FullSegBreakSpec, density: RouteChannel.Density]
RETURNS [result: BreakResult] = {
evaluate the break of ths seg at break
maxDensity: DABasics.Number;
lowerRange, upperRange, overlap: RTBasic.Range;
exitsSeparate: BOOLEAN ← IF 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 ← RTBasic.Span[[break.breaks[middle].pos, break.breaks[middle].pos], RouteChannel.GetRange[pinLists.bottomList]];
upperRange ← RTBasic.Span[[break.breaks[middle].pos, break.breaks[middle].pos], RouteChannel.GetRange[pinLists.topList]];
overlap ← RTBasic.Overlap[lowerRange, upperRange];
IF overlap.l > overlap.r THEN Route.Error[programmingError, "overlap should not be NIL."]}
ELSE overlap ← [0,0];
maxDensity ← AddSeg[chanPins, 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 [chanPins: RouteChannel.RoutingChannelPins, parms: RoutePrivate.RoutingAreaParms, 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;
};
oldSeg: RouteChannel.Segment ← fullSegBreak.seg;
branchWidth: DABasics.Number ← oldSeg.net.branchWidth;
trunkWidth: DABasics.Number ← oldSeg.net.trunkWidth;
IF BreaksFound[fullSegBreak] # 1
THEN
Route.Error[programmingError, "Not suppose to happen"];
[] ← RouteChannel.EnumPinsOnSeg[oldSeg, UnlinkSegFromPins];
FOR lmr: Lmr
IN Lmr
DO
segBreak: SegBreakSpec ← fullSegBreak.breaks[lmr];
IF segBreak #
NIL
THEN {
pinIndex: RouteChannel.ZMPinsOnCh ← RouteChannel.FindPinPos[chanPins, 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: BOOLEAN ← IF 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; seg1.part ← 1;
seg2.exitBreak ← TRUE; seg2.part ← 2;
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]}
pinListPair ← DividePins[lmr, pinLists, lowerPin, upperPin]};
LinkSegsToPins[seg1, pinListPair.list1, lowerPin];
LinkSegsToPins[seg2, pinListPair.list2, upperPin];
SetTrackConstraints[seg1, oldSeg.trackConstraint];
SetTrackConstraints[seg2, oldSeg.trackConstraint];
TerminalIO.PutRope[Rope.Cat["\ntrunk segment for net: ", fullSegBreak.seg.net.name, ]];
TerminalIO.PutF1[" divided at: %g", IO.int[chanPins.sides[pinIndex].pLoc/8]];
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 [seg: RouteChannel.Segment, trackConstraint: DABasics.Number] = {
EachPin: RouteChannel.EachPinActionProc = {
IF pin #
NIL
THEN {
IF pin.trackConstraint # 0
THEN
seg.trackConstraint ← pin.trackConstraint;
};
};
[] ← RouteChannel.EnumPinsOnSeg[seg, EachPin];
};
AddToClosestList:
PROC [pinListPair: ChanPinListPair, pin: RouteChannel.ChanPin]
RETURNS [result: ChanPinListPair] ~ {
l1Range: RTBasic.Range ← RouteChannel.GetRange[pinListPair.list1];
l2Range: RTBasic.Range ← RouteChannel.GetRange[pinListPair.list2];
IF pin #
NIL
THEN {
pLoc: DABasics.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: DABasics.Number ← MIN[ABS[pLoc - l1Range.l], ABS[pLoc - l1Range.r]];
distToL2: DABasics.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: DABasics.Number ← NARROW[ref1, RouteChannel.ChanPin].pinPosition.pLoc;
p2: DABasics.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: List.LORA ← ConvertToLORA[pinList];
sortedPinList: List.LORA ← List.Sort[mungedPinList, PinCompare];
rightPin: RouteChannel.ChanPin ← NARROW[List.NthElement[sortedPinList, -1]];
leftPin: RouteChannel.ChanPin ← 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 [chanPins: RouteChannel.RoutingChannelPins, density: RouteChannel.Density, r: RTBasic.Range, width: DABasics.Number]
RETURNS [maxDensity: DABasics.Number ← 0] = {
compute the track density when this range is added
IF density #
NIL
THEN
FOR index: RouteChannel.MPinsOnCh
IN [1 .. chanPins.count]
DO
pos: DABasics.Number ← chanPins.sides[index].pLoc;
thisDensity: DABasics.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 ← Basics.CompareInt[r1.numDogLegs, r2.numDogLegs];
IF result # equal THEN RETURN;
result ← Basics.CompareInt[r1.deltaDensity, r2.deltaDensity];
IF result # equal THEN RETURN;
result ← Basics.CompareInt[r1.duplicateLength, r2.duplicateLength];
RETURN};
ClosestPins:
PROC [chanPins: RouteChannel.RoutingChannelPins, target: DABasics.Number]
RETURNS [nextLower, nextHigher: RouteChannel.ZMPinsOnCh ← 0] = {
find the PinPosition closest to target.
trial: RouteChannel.ZMPinsOnCh;
nextHigher ← chanPins.count;
nextLower ← 1;
WHILE
ABS[nextHigher - nextLower] > 1
DO
trial ←(nextHigher + nextLower)/2;
IF target < chanPins.sides[trial].pLoc THEN nextHigher ← trial
ELSE IF target > chanPins.sides[trial].pLoc THEN nextLower ← trial
ELSE nextLower ← nextHigher ← trial;
ENDLOOP};
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 [chanPins: RouteChannel.RoutingChannelPins, pinLists: ChanPinListSet]
RETURNS [rangeList: RangeWithDirList] = {
find distinct ranges for this seg, use enumeration
lr: RTBasic.Range ← RouteChannel.GetRange[pinLists.bottomList];
ur: RTBasic.Range ← RouteChannel.GetRange[pinLists.topList];
ce1: DABasics.Number ← chanPins.cEnd1;
ce2: DABasics.Number ← chanPins.cEnd2;
min: DABasics.Number ← MIN[lr.l, ur.l];
max: DABasics.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};
ConvertToLORA:
PROC [list: RouteChannel.ChanPinList]
RETURNS[val: List.
LORA] = {
val ← NIL;
UNTIL list =
NIL
DO
val ← CONS[list.first, val];
list ← list.rest;
ENDLOOP;
RETURN[val];
}.