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: BOOLEANTRUE;
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: 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[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: BOOLEANFALSE] = {
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: 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.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: BOOLEANIF 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: 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[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: 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 ← 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: 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; 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]}
ELSE {
};
pinListPair ← DividePins[lmr, pinLists, lowerPin, upperPin]};
ENDCASE;
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];
}; -- of ConvertToLORA
}.