RouteChannelConstraintsImpl.mesa
Copyright Ó 1985, 1986, 1987, 1989 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
Altered version for improved dogleg routes
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,
chainLength: INT ← 0];
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,
chainLength: 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[chanData, parms, rules, seg, NIL, whichEnd, pins];
IF BreaksFound[break] > 0
THEN {
DoBreak[chanData, 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[chanData, parms, rules, leftToRightSegList, density, whichEnd, pins];
IF BreaksFound[segBreak] > 0 THEN DoBreak[chanData, 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[chanData, parms, rules, rightToLeftSegList, density, whichEnd, pins];
IF BreaksFound[segBreak] > 0 THEN DoBreak[chanData, 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[chanData, parms, rules, LIST[seg, leftSeg], density, whichEnd, pins];
IF BreaksFound[segBreak] > 0 THEN DoBreak[chanData, 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];
lowerAltSeg: RouteChannel.Segment ← lowerPin.altConctSeg[lowerSegIndex];
upperAltSeg: RouteChannel.Segment ← upperPin.altConctSeg[upperSegIndex];
IF HackedDoConstraint[chanData, parms, rules, lowerSeg, upperSeg, whichEnd, pins] THEN segBroken ← TRUE;
IF HackedDoConstraint[chanData, parms, rules, lowerSeg, upperAltSeg, whichEnd, pins] THEN segBroken ← TRUE;
IF HackedDoConstraint[chanData, parms, rules, lowerAltSeg, upperSeg, whichEnd, pins] THEN segBroken ← TRUE;
IF HackedDoConstraint[chanData, parms, rules, lowerAltSeg, upperAltSeg, 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[chanData, parms, rules, segList, density, whichEnd, pins];
IF BreaksFound[segBreak] > 0 THEN DoBreak[chanData, parms, segBreak]
ELSE {
-- choose a victim --
segList.first.failed ← TRUE;
Route.Signal[noResource, Rope.Cat["net: ", 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 = {
-- PROC[graph: Graph, arc: Arc, node: Node, direction: Direction] RETURNS [quit: BOOLEAN ← FALSE];
IF arc.inferiorNode = upperNode
THEN
{nodeInfo: RouteChannel.SegmentConstraint ← NARROW[upperNode.nodeInfo];
segList ← CONS[nodeInfo.segment, segList];
quit ← TRUE}
ELSE {
IF ~List.Memb[arc.inferiorNode, visitedNodes]
THEN {
visitedNodes ← CONS[arc.inferiorNode, visitedNodes];
quit ← RouteDiGraph.EnumArcsFromNode[graph, arc.inferiorNode, in, ArcProc]}};
IF quit
THEN
{nodeInfo: RouteChannel.SegmentConstraint ← NARROW[node.nodeInfo];
segList ← CONS[nodeInfo.segment, segList]}};
visitedNodes: RouteDiGraph.ArcList ← NIL;
[] ← RouteDiGraph.EnumArcsFromNode[graph, lowerNode, in, ArcProc]};
PrintSegs:
PROC [
segList: RouteChannel.SegmentList] = {
print segments on list
FOR segs: RouteChannel.SegmentList ← segList, segs.rest
WHILE segs #
NIL
DO
seg: RouteChannel.Segment ← segs.first;
range: RTBasic.Range ← RouteChannel.SegRange[seg];
TerminalIO.PutF["\n\tnet: %g at %g , %g ( %g, %g )", IO.rope[seg.net.name], IO.int[range.l], IO.int[range.r], IO.int[range.l/8], IO.int[range.r/8]];
ENDLOOP};
FindBreak:
PROC [chanData: RouteChannel.ChannelData,
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
chanPins: RouteChannel.RoutingChannelPins ← chanData.chanPins;
bestResult: BreakResult ← [LAST[INT], LAST[INT], LAST[INT], LAST[INT]];
run through the segs in the cycle. find the best
TerminalIO.PutRope["\nSegements in Cycle:"];
FOR segs: RouteChannel.SegmentList ← segList, segs.rest
WHILE segs #
NIL
DO
seg: RouteChannel.Segment ← segs.first;
break: FullSegBreakSpec ← BreakOneSeg[chanData, parms, rules, seg, density, whichEnd, pins];
result: BreakResult ← EvalBreak[chanPins, parms, break, density];
range: RTBasic.Range ← RouteChannel.SegRange[seg];
TerminalIO.PutF["\n\tnet: %g at %g , %g ( %g, %g )", IO.rope[seg.net.name], IO.int[range.l], IO.int[range.r], IO.int[range.l/8], IO.int[range.r/8]];
TerminalIO.PutF["\n\t\tdeltaDensity: %g duplicateLength: %g numDogLegs: %g , chainLength: %g", IO.int[result.deltaDensity], IO.int[result.duplicateLength], IO.int[result.numDogLegs], IO.int[result.chainLength]];
-- try breaks at ALL places as an experiment
IF BreaksFound[break] > 0 THEN HackedDoBreak[chanData, parms, rules, break];
IF CompareResult[result, bestResult] = less
THEN
{bestResult ← result; bestBreak ← break};
ENDLOOP;
IF bestBreak.seg = NIL THEN RETURN[[NIL, [NIL, NIL, NIL]]]};
BreakOneSeg:
PROC [chanData: RouteChannel.ChannelData,
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
chanPins: RouteChannel.RoutingChannelPins ← chanData.chanPins;
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]];
IF ~HasDogleg[seg]
THEN {
SELECT parms.routerUsed
FROM
channel => {
FOR ranges: RangeWithDirList ← rangeList, ranges.rest
WHILE ranges #
NIL
DO
break.breaks[middle] ← HackedBreakWithInRange[chanData, 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[chanData, 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[chanData, 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[chanData, 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."]
}};
HasDogleg:
PROC [seg: RouteChannel.Segment]
RETURNS [hasDogleg:
BOOLEAN ←
FALSE] ~ {
returns TRUE if seg has a dogleg
EachPin: RouteChannel.EachPinActionProc ~ {
PROC[pinPosition: PinPosition, pin: ChanPin] RETURNS [quit: BOOLEAN ← FALSE];
IF pin.kindOfPin = dogLeg THEN quit ← TRUE};
hasDogleg ← RouteChannel.EnumPinsOnSeg[seg, EachPin]};
BreakWithInRange:
PROC [chanData: RouteChannel.ChannelData,
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;
chanPins: RouteChannel.RoutingChannelPins ← chanData.chanPins;
minPinD2: DABasics.Number ← rules.branchWidth/2;
widestPinD2: DABasics.Number;
SELECT range.dir
FROM
leftToRight => {
nextLower: RouteChannel.ZMPinsOnCh ← ClosestPins[chanPins, range.range.l].nextLower;
IF ~DogLegNotAllowed[chanPins, parms, rules, seg, range.range.l, pins] THEN
break ← NEW[SegBreakSpecRec ← [range.range.l, dogLeg]];
FOR pos: DABasics.Number ← NextPosToRight[nextLower], NextPosToRight[nextLower]
WHILE pos <= range.range.r
AND break =
NIL
DO
IF ~DogLegNotAllowed[chanPins, parms, rules, seg, pos, pins] THEN
break ← NEW[SegBreakSpecRec ← [pos, dogLeg]];
nextLower ← MIN[chanPins.count+1, nextLower + 1];
ENDLOOP};
rightToLeft => {
nextHigher: RouteChannel.ZMPinsOnCh ← ClosestPins[chanPins, range.range.r].nextHigher;
IF ~DogLegNotAllowed[chanPins, parms, rules, seg, range.range.r, pins] THEN
break ← NEW[SegBreakSpecRec ← [range.range.r, dogLeg]];
FOR pos: DABasics.Number ← NextPosToLeft[nextHigher], NextPosToLeft[nextHigher]
WHILE pos >= range.range.l
AND break =
NIL
DO
IF ~DogLegNotAllowed[chanPins, parms, rules, seg, pos, pins]
THEN
break ← NEW[SegBreakSpecRec ← [pos, dogLeg]];
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];
chain: INT ← LAST[INT];
IF BreaksFound[break] = 0 THEN RETURN[[LAST[INT], 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."];
chain ← break.breaks[middle].chainLength}
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;
result.chainLength ← chain;
FOR lmr: Lmr
IN Lmr
DO
IF break.breaks[lmr] # NIL THEN result.numDogLegs ← result.numDogLegs + 1;
ENDLOOP};
DoBreak:
PROC [chanData: RouteChannel.ChannelData, 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;
};
chanPins: RouteChannel.RoutingChannelPins ← chanData.chanPins;
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[chanPins]};
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.conctSeg[chanRight] = NIL THEN chanPin.conctSeg[chanRight] ← seg
ELSE chanPin.altConctSeg[chanRight] ← seg};
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};
BTP August 1, 1988 6:37:29 pm PDT
seg.exteriorPins[chanLeft] ← chanPin}
ELSE
IF chanPin = rightPin
THEN {
update old seg pointer
{IF chanPin.conctSeg[chanLeft] = NIL THEN chanPin.conctSeg[chanLeft] ← seg
ELSE chanPin.altConctSeg[chanLeft] ← seg};
IF chanPin # newPin THEN
{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};
BTP August 1, 1988 6:37:29 pm PDT
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.chainLength, r2.chainLength];
IF result # equal THEN RETURN;
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
Code for improved dogleg routes. Should be made permenent or deleted
BTP April 18, 1989 11:32:59 am PDT
this code taken from this module or from RouteChannelInitImpl.mesa
HackedBreakWithInRange:
PROC [chanData: RouteChannel.ChannelData,
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
Special for DDE: don't try dogleg positions between pins positions
BTP: April 17, 1989 3:27:49 pm PDT
minPinD2: DABasics.Number ← RouteUtil.GetWidthWithContact[routingArea, routingArea.rules.branchWidth]/2;
chanPins: RouteChannel.RoutingChannelPins ← chanData.chanPins;
minPinD2: DABasics.Number ← rules.branchWidth/2;
chainLength: INT;
notAllowed: BOOLEAN;
SELECT range.dir
FROM
leftToRight => {
FOR pos: DABasics.Number ← range.range.l, pos + 4*11
WHILE pos <= range.range.r
AND break =
NIL
DO
[notAllowed, chainLength] ← NewDogLegNotAllowed[chanData, parms, rules, seg, pos, pins];
IF ~notAllowed
THEN
break ← NEW[SegBreakSpecRec ← [pos, dogLeg, chainLength]];
ENDLOOP};
rightToLeft => {
FOR pos: DABasics.Number ← range.range.r, pos- 4*11
WHILE pos >= range.range.l
AND break =
NIL
DO
[notAllowed, chainLength] ← NewDogLegNotAllowed[chanData, parms, rules, seg, pos, pins];
IF ~notAllowed
THEN
break ← NEW[SegBreakSpecRec ← [pos, dogLeg, chainLength]];
ENDLOOP};
ENDCASE};
NewDogLegNotAllowed:
PROC [chanData: RouteChannel.ChannelData,
parms: RoutePrivate.RoutingAreaParms,
rules: Route.DesignRules,
seg: RouteChannel.Segment,
pos: DABasics.Number,
pins: TestPins]
RETURNS [notAllowed: BOOLEAN ← FALSE, chainLength: INT ← LAST[INT]] = {
BTP April 13, 1989 3:18:33 pm PDT
Implements dogleg rules in ICCAD paper
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};
chanPins: RouteChannel.RoutingChannelPins ← chanData.chanPins;
minLimit, maxLimit, leftIndex, rightIndex: RouteChannel.ZMPinsOnCh;
width: DABasics.Number ← MAX[seg.net.trunkWidth, seg.net.branchWidth];
graph: RouteDiGraph.Graph ← chanData.constraints;
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 (Rule 0: unstated, but obvious)
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 (Rule 2)
[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;
IF ~notAllowed
THEN {
-- see if this dogleg position participates in a cycle
originalNode: RouteDiGraph.Node ← seg.constraintNode;
originalArcs: RouteDiGraph.ArcList ← RouteDiGraph.RemoveNode[graph, seg.constraintNode];
upperSeg: RouteChannel.Segment ← NEW[RouteChannel.SegmentRec ← [net: seg.net, qWidth: seg.qWidth, exitBreak: seg.exitBreak]];
upperConstraint: RouteChannel.SegmentConstraint ← NEW[RouteChannel.SegmentConstraintRec ← [Rope.Cat[upperSeg.net.name, "-upperSegment"], upperSeg]];
newUpperConstraintNode: RouteDiGraph.Node ← RouteDiGraph.AddNewNode[graph, upperConstraint];
lowerSeg: RouteChannel.Segment ← NEW[RouteChannel.SegmentRec ← [net: seg.net, qWidth: seg.qWidth, exitBreak: seg.exitBreak]];
lowerConstraint: RouteChannel.SegmentConstraint ← NEW[RouteChannel.SegmentConstraintRec ← [Rope.Cat[lowerSeg.net.name, "-lowerSegment"], lowerSeg]];
newLowerConstraintNode: RouteDiGraph.Node ← RouteDiGraph.AddNewNode[graph, lowerConstraint];
TransferConstraints[graph, originalArcs, originalNode, newUpperConstraintNode, newLowerConstraintNode];
see if outer pins can cross the channel
[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];
bottomNet: RoutePrivate.Net ← FindConnectedNet[bottomPin];
constrainBottom: BOOLEAN ← Constraining[rules, bottomPin, pins.trialPin];
IF constrainBottom
THEN {
IF bottomNet = seg.net THEN notAllowed ← TRUE; -- Don't let a dogleg constratin its own net
add constraints for new trial segments
AddConstraintsToPin[graph, newLowerConstraintNode, bottomPin]};
Check if bottom and top pins constrain each other (Rule 1)
Check if bottom and top pins belong to the same net (Rule 3)
see if any nets within the range cross the channels
FOR i: RouteChannel.MPinsOnCh
IN [minLimit .. maxLimit]
WHILE ~notAllowed
DO
pP: RouteChannel.PinPosition ← chanPins.sides[i];
topPin: RouteChannel.ChanPin ← pP.pins[chanTop];
topNet: RoutePrivate.Net ← FindConnectedNet[topPin];
constrainTop: BOOLEAN ← Constraining[rules, topPin, pins.trialPin];
IF constrainTop
THEN {
IF topNet = seg.net THEN notAllowed ← TRUE; -- Don't let a dogleg constratin its own net
add constraints for new trial segments
AddConstraintsFromPin[graph, topPin, newUpperConstraintNode]};
IF constrainBottom
AND constrainTop
THEN {
IF bottomNet = topNet THEN notAllowed ← TRUE; -- Rule 1
};
ENDLOOP;
ENDLOOP;
check Rule 3
IF ~RouteDiGraph.PathExists[graph, newUpperConstraintNode, newLowerConstraintNode]
THEN
[] ← RouteDiGraph.AddNewArc[graph, NIL, newUpperConstraintNode, newLowerConstraintNode];
IF notAllowed OR SegsInCycle[graph, newLowerConstraintNode, newUpperConstraintNode] # NIL THEN notAllowed ← TRUE;
IF notAllowed OR SegsInCycle[graph, newUpperConstraintNode, newUpperConstraintNode] # NIL THEN notAllowed ← TRUE;
IF notAllowed OR SegsInCycle[graph, newLowerConstraintNode, newLowerConstraintNode] # NIL THEN notAllowed ← TRUE;
IF ~notAllowed
THEN
chainLength ← UpperConstrainedNodes[graph, newUpperConstraintNode] + LowerConstrainedNodes[graph, newLowerConstraintNode];
put things back the way they were
[] ← RouteDiGraph.RemoveNode[graph, newUpperConstraintNode];
[] ← RouteDiGraph.RemoveNode[graph, newLowerConstraintNode];
RouteDiGraph.IncludeNode[graph, originalNode];
RouteDiGraph.IncludeArcs[graph, originalArcs]};
};
GetBreakSpec:
PROC [break: FullSegBreakSpec]
RETURNS [segBreak: SegBreakSpec ←
NIL] ~ {
extract the break spec for the full break
FOR lmr: Lmr
IN Lmr
DO
IF break.breaks[lmr] # NIL THEN segBreak ← break.breaks[lmr];
ENDLOOP;
};
GetLmr:
PROC [break: FullSegBreakSpec]
RETURNS [lmr: Lmr ← middle] ~ {
extract the Lmr spec for the full break
FOR where: Lmr
IN Lmr
DO
IF break.breaks[where] # NIL THEN lmr ← where;
ENDLOOP;
};
HackedDoBreak:
PROC [chanData: RouteChannel.ChannelData, parms: RoutePrivate.RoutingAreaParms, rules: Route.DesignRules, 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;
};
chanPins: RouteChannel.RoutingChannelPins ← chanData.chanPins;
oldSeg: RouteChannel.Segment ← fullSegBreak.seg;
branchWidth: DABasics.Number ← oldSeg.net.branchWidth;
trunkWidth: DABasics.Number ← oldSeg.net.trunkWidth;
segBreak: SegBreakSpec ← GetBreakSpec[fullSegBreak];
lmr: Lmr ← GetLmr[fullSegBreak];
pinIndex: RouteChannel.ZMPinsOnCh ← RouteChannel.FindPinPos[chanPins, segBreak.pos];
pinPosition: RouteChannel.PinPosition ← chanPins.sides[pinIndex];
upperPin, lowerPin: RouteChannel.ChanPin ← NIL;
pinListPair: ChanPinListPair;
segRange: RTBasic.Range ← RouteChannel.SegRange[oldSeg];
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]];
IF (segRange.l < pinPosition.pLoc AND pinPosition.pLoc < segRange.r) OR segBreak.type = exit
THEN {
break this one segment
[] ← RouteChannel.EnumPinsOnSeg[oldSeg, UnlinkSegFromPins];
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: rules.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]];
}
ELSE {
-- replace all segments for net with one segment
net: RoutePrivate.Net ← oldSeg.net;
pinLists: ChanPinListSet ← GetPinsOnNet[chanPins, net];
parms.widestPin ← MAX[rules.branchWidth, parms.widestPin];
upperPin ← lowerPin ← NEW[RouteChannel.ChanPinRec ← [pinSide: none, qLoc: 0, pWidth: rules.branchWidth, kindOfPin: dogLeg, pinPosition: pinPosition]];
pinPosition.innerPins ← CONS[upperPin, pinPosition.innerPins];
pinListPair ← DividePins[middle, pinLists, lowerPin, upperPin];
UnlinkPinsOnNet[chanPins, net]; -- unlink the old segments
LinkSegsToPins[seg1, pinListPair.list1, lowerPin];
LinkSegsToPins[seg2, pinListPair.list2, upperPin];
SetTrackConstraints[seg1, oldSeg.trackConstraint];
SetTrackConstraints[seg2, oldSeg.trackConstraint];
TerminalIO.PutRope[Rope.Cat["\ntrunk segment divided for net: ", fullSegBreak.seg.net.name ]];
TerminalIO.PutF1[" dogleg at: %g", IO.int[chanPins.sides[pinIndex].pLoc/8]];
};
remove this statment for production
RouteChannel.AuditPins[chanPins]
};
GetPinsOnNet:
PROC [chanPins: RouteChannel.RoutingChannelPins, net: RoutePrivate.Net]
RETURNS [pinLists: ChanPinListSet← [
NIL,
NIL,
NIL,
NIL]] ~ {
get the pins attached to the net on the indicated side
bottomList == lowerPinList and topList == upperPinList
this is a heavy duty way to perform this action; needs to be improved
EachPinPosition: RouteChannel.EachPinPositionActionProc ~ {
PROC[pinPosition: PinPosition, pinIndex: MPinsOnCh] RETURNS [quit: BOOLEAN ← FALSE];
EachPin: RouteChannel.EachPinActionProc ~ {
PROC[pinPosition: PinPosition, pin: ChanPin] RETURNS [quit: BOOLEAN ← FALSE];
IF OnNet[net, pin]
THEN {
SELECT pin.pinSide
FROM
chanBottom => pinLists.bottomList ← CONS[pin, pinLists.bottomList];
chanTop => pinLists.topList ← CONS[pin, pinLists.topList];
chanLeft => leftPin ← pin;
chanRight => rightPin ← pin;
ENDCASE => Route.Error[programmingError, "Invalid pin on net."];
}
};
[] ← RouteChannel.EnumPins[pinPosition, EachPin]};
leftPin, rightPin: RouteChannel.ChanPin;
[] ← RouteChannel.EnumPinPositions[chanPins, EachPinPosition];
IF leftPin #
NIL
THEN {
result: ChanPinListPair ← AddToClosestList[[pinLists.bottomList, pinLists.topList], leftPin];
pinLists.bottomList ← result.list1;
pinLists.topList ← result.list2};
IF rightPin #
NIL
THEN {
result: ChanPinListPair ← AddToClosestList[[pinLists.bottomList, pinLists.topList], rightPin];
pinLists.bottomList ← result.list1;
pinLists.topList ← result.list2};
};
UnlinkPinsOnNet:
PROC [chanPins: RouteChannel.RoutingChannelPins, net: RoutePrivate.Net] ~ {
Unlink the old segments for Garbage collection
EachPinPosition: RouteChannel.EachPinPositionActionProc ~ {
PROC[pinPosition: PinPosition, pinIndex: MPinsOnCh] RETURNS [quit: BOOLEAN ← FALSE];
EachPin: RouteChannel.EachPinActionProc ~ {
PROC[pinPosition: PinPosition, pin: ChanPin] RETURNS [quit: BOOLEAN ← FALSE];
IF OnNet[net, pin]
THEN {
pin.conctSeg[chanLeft] ← NIL;
pin.conctSeg[chanRight] ← NIL;
pin.altConctSeg[chanLeft] ← NIL;
pin.altConctSeg[chanRight] ← NIL;
}};
[] ← RouteChannel.EnumPins[pinPosition, EachPin]};
[] ← RouteChannel.EnumPinPositions[chanPins, EachPinPosition]};
OnNet:
PROC [net: RoutePrivate.Net, pin: RouteChannel.ChanPin]
RETURNS [onNet:
BOOLEAN ←
FALSE] ~ {
Returns TRUE if pin is connected to net
IF pin #
NIL
THEN {
IF pin.conctSeg[chanLeft] # NIL AND pin.conctSeg[chanLeft].net = net THEN onNet ← TRUE;
IF pin.conctSeg[chanRight] # NIL AND pin.conctSeg[chanRight].net = net THEN onNet ← TRUE;
IF pin.altConctSeg[chanLeft] # NIL AND pin.altConctSeg[chanLeft].net = net THEN onNet ← TRUE;
IF pin.altConctSeg[chanRight] # NIL AND pin.altConctSeg[chanRight].net = net THEN onNet ← TRUE;
}};
CycleFromPins:
PROC [chanData: RouteChannel.ChannelData, lowerPin, upperPin: RouteChannel.ChanPin]
RETURNS [cycleExists:
BOOLEAN ←
FALSE] ~ {
graph: RouteDiGraph.Graph ← chanData.constraints;
FOR lowerSegIndex: RouteChannel.ChanLRSide
IN [chanLeft .. chanRight]
WHILE ~cycleExists
DO
FOR upperSegIndex: RouteChannel.ChanLRSide
IN [chanLeft .. chanRight]
WHILE ~cycleExists
DO
IF lowerPin #
NIL
AND upperPin #
NIL
THEN {
lowerSeg: RouteChannel.Segment ← lowerPin.conctSeg[lowerSegIndex];
upperSeg: RouteChannel.Segment ← upperPin.conctSeg[upperSegIndex];
IF lowerSeg #
NIL
AND upperSeg #
NIL
AND lowerSeg # upperSeg
THEN
IF ~lowerSeg.net.num # upperSeg.net.num
THEN {
lowerNode: RouteDiGraph.Node ← lowerSeg.constraintNode;
upperNode: RouteDiGraph.Node ← upperSeg.constraintNode;
IF SegsInCycle[graph, lowerNode, upperNode] # NIL THEN cycleExists ← TRUE}};
ENDLOOP; -- FOR upperSegIndex
ENDLOOP; -- FOR lowerSegIndex
};
HackedDoConstraint:
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
add constraint that caused this
dummy: RouteDiGraph.Arc ← RouteDiGraph.AddNewArc[graph, NIL, upperNode, lowerNode];
density: RouteChannel.Density ← RouteChannel.ComputeDensity[chanPins, rules];
segBreak: FullSegBreakSpec ← FindBreak[chanData, parms, rules, segList, density, whichEnd, pins];
IF BreaksFound[segBreak] > 0 THEN HackedDoBreak[chanData, parms, rules, segBreak]
ELSE {
-- choose a victim --
segList.first.failed ← TRUE;
Route.Signal[noResource, Rope.Cat["net: ", segList.first.net.name, " failed, unable to find a place to dogleg"]]};
segBroken ← TRUE}
ELSE {
-- add a segment constraint
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]}}};
AddConstraintsToPin:
PROC [graph: RouteDiGraph.Graph, constraintNode: RouteDiGraph.Node, pin: RouteChannel.ChanPin] ~ {
add constraints from the constraint node to the segments on the pin
segList: RouteChannel.SegmentList ← RouteChannel.GetSegsOnPin[pin];
FOR segs: RouteChannel.SegmentList ← segList, segs.rest
WHILE segs #
NIL
DO
lowerNode: RouteDiGraph.Node ← segs.first.constraintNode;
IF lowerNode =
NIL
THEN {
constraint: RouteChannel.SegmentConstraint ← NEW[RouteChannel.SegmentConstraintRec ← [segs.first.net.name, segs.first]];
lowerNode ← RouteDiGraph.AddNewNode[graph, constraint];
segs.first.constraintNode ← lowerNode};
IF ~RouteDiGraph.PathExists[graph, constraintNode, lowerNode]
THEN
[] ← RouteDiGraph.AddNewArc[graph, NIL, constraintNode, lowerNode];
ENDLOOP;
};
AddConstraintsFromPin:
PROC [graph: RouteDiGraph.Graph, pin: RouteChannel.ChanPin, constraintNode: RouteDiGraph.Node] ~ {
add constraints from the constraint node to the segments on the pin
segList: RouteChannel.SegmentList ← RouteChannel.GetSegsOnPin[pin];
FOR segs: RouteChannel.SegmentList ← segList, segs.rest
WHILE segs #
NIL
DO
upperNode: RouteDiGraph.Node ← segs.first.constraintNode;
IF upperNode =
NIL
THEN {
constraint: RouteChannel.SegmentConstraint ← NEW[RouteChannel.SegmentConstraintRec ← [segs.first.net.name, segs.first]];
upperNode ← RouteDiGraph.AddNewNode[graph, constraint];
segs.first.constraintNode ← upperNode};
IF ~RouteDiGraph.PathExists[graph, upperNode, constraintNode]
THEN
[] ← RouteDiGraph.AddNewArc[graph, NIL, upperNode, constraintNode];
ENDLOOP;
};
TransferConstraints:
PROC [graph: RouteDiGraph.Graph, originalArcs: RouteDiGraph.ArcList, originalNode, newUpperConstraintNode, newLowerConstraintNode: RouteDiGraph.Node] ~ {
transfer constraints from removed arcs to new nodes
FOR aList: RouteDiGraph.ArcList ← originalArcs, aList.rest
WHILE aList #
NIL
DO
arc: RouteDiGraph.Arc ← NARROW[aList.first];
IF arc.superiorNode = originalNode THEN [] ← RouteDiGraph.AddNewArc[graph, NIL, newUpperConstraintNode, arc.inferiorNode]
ELSE IF arc.inferiorNode = originalNode THEN [] ← RouteDiGraph.AddNewArc[graph, NIL, arc.superiorNode, newLowerConstraintNode]
ELSE Route.Error;
ENDLOOP;
};
LowerConstrainedNodes:
PROCEDURE[graph: RouteDiGraph.Graph, node: RouteDiGraph.Node]
RETURNS [constrainedNodes: INT ← 0] = {
recursively go through the constraints
ArcProc: RouteDiGraph.EnumArcsFromNodeProc = {
PROC[graph: Graph, arc: Arc, node: Node, direction: Direction] RETURNS [quit: BOOLEAN ← FALSE];
IF ~List.Memb[arc.inferiorNode, visitedNodes]
THEN {
visitedNodes ← CONS[arc.inferiorNode, visitedNodes];
constrainedNodes ← constrainedNodes + 1;
quit ← RouteDiGraph.EnumArcsFromNode[graph, arc.inferiorNode, in, ArcProc]}};
visitedNodes: RouteDiGraph.NodeList ← NIL;
[] ← RouteDiGraph.EnumArcsFromNode[graph, node, in, ArcProc]};
UpperConstrainedNodes:
PROCEDURE[graph: RouteDiGraph.Graph, node: RouteDiGraph.Node]
RETURNS [constrainedNodes: INT ← 0] = {
recursively go through the constraints
ArcProc: RouteDiGraph.EnumArcsFromNodeProc = {
PROC[graph: Graph, arc: Arc, node: Node, direction: Direction] RETURNS [quit: BOOLEAN ← FALSE];
IF ~List.Memb[arc.superiorNode, visitedNodes]
THEN {
visitedNodes ← CONS[arc.superiorNode, visitedNodes];
constrainedNodes ← constrainedNodes + 1;
quit ← RouteDiGraph.EnumArcsFromNode[graph, arc.superiorNode, out, ArcProc]}};
visitedNodes: RouteDiGraph.NodeList ← NIL;
[] ← RouteDiGraph.EnumArcsFromNode[graph, node, out, ArcProc]};
}.