<> <> <> <> <> <> <<>> 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] ~ { <> <> <<>> <> 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 <> 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]; testPin: RouteChannel.ChanPin _ pinPosition.pins[chanBottom]; pLoc: DABasics.Number _ pinPosition.pLoc; widestPinD2: DABasics.Number _ RouteUtil.GetWidthWithContact[rules, rules.branchWidth]/2; minLimit, maxLimit: RouteChannel.MPinsOnCh; <> [] _ 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 _ upperPinPosition.pins[chanBottom]; IF ProcessConstraints[chanData, parms, rules, upperPin, testPin, middle, pins] THEN GOTO GoRound; <<>> <> FOR innerPins: RouteChannel.ChanPinList _ pinPosition.innerPins, innerPins.rest WHILE innerPins # NIL DO innerPin: RouteChannel.ChanPin _ innerPins.first; <<>> <> 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 <> 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]; <> IF pList.rest # NIL THEN { upperPin: RouteChannel.ChanPin _ NARROW[pList.rest.first]; IF ProcessConstraints[chanData, parms, rules, upperPin, lowerPin, whichEnd, pins] THEN GOTO GoRound}; <> 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 { <> leftPinPosition: RouteChannel.PinPosition _ chanPins.sides[1]; leftPinList: RouteChannel.ChanPinList _ leftPinPosition.innerPins; <> FOR lPList: RouteChannel.ChanPinList _ leftPinList, lPList.rest WHILE lPList # NIL DO leftPin: RouteChannel.ChanPin _ NARROW[lPList.first]; lSList: RouteChannel.SegmentList _ RouteChannel.GetSegsOnPin[leftPin]; <> 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 <> {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 <> {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}; <> IF seg.trackConstraint = leftSeg.trackConstraint AND RTBasic.Overlaps[RouteChannel.SegRange[seg], RouteChannel.SegRange[leftSeg]] AND seg.net # leftSeg.net THEN <> {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] = { <> 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] = { <> <> 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 <> 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] = { <> 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] = { <> 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 { <> 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 <> <> IF ~RouteDiGraph.PathExists[graph, upperNode, lowerNode] THEN <> [] _ RouteDiGraph.AddNewArc[graph, NIL, upperNode, lowerNode]}}}; SegsInCycle: PROCEDURE[graph: RouteDiGraph.Graph, lowerNode, upperNode: RouteDiGraph.Node] RETURNS [segList: RouteChannel.SegmentList _ NIL] = { <> 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] = { <> 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]]] = { <> chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins; bestResult: BreakResult _ [LAST[INT], LAST[INT], LAST[INT], LAST[INT]]; <> 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>> < 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] = { <> 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] ~ { <> EachPin: RouteChannel.EachPinActionProc ~ { <> 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] = { <> 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}}; <> 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] = { <> 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]; <> IF Constraining[rules, pins.trialPin, pins.leftExitPin] THEN notAllowed _ TRUE; IF Constraining[rules, pins.trialPin, pins.rightExitPin] THEN notAllowed _ TRUE; <> [minLimit, maxLimit] _ RouteChannel.FindConstraintLimits[chanPins, parms, rules, leftIndex, rightIndex, CheckInner]; FOR index: RouteChannel.MPinsOnCh IN [minLimit .. maxLimit] WHILE ~notAllowed DO <> pinPosition: RouteChannel.PinPosition _ chanPins.sides[index]; notAllowed _ RouteChannel.EnumPins[pinPosition, CheckInner]; ENDLOOP; <<>> <> [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]; <> 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; <> <> 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] = { <> 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] = { <> 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] = { <> <> <> <> <> <<>> 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]; <> 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]]; <<>> <> 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] = { <> 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 { <> {IF chanPin.conctSeg[chanRight] = NIL THEN chanPin.conctSeg[chanRight] _ seg ELSE chanPin.altConctSeg[chanRight] _ seg}; <> <> <> <> <<{IF chanPin.conctSeg[chanRight] = NIL THEN chanPin.conctSeg[chanRight] _ seg>> <> <> seg.exteriorPins[chanLeft] _ chanPin} ELSE IF chanPin = rightPin THEN { <> {IF chanPin.conctSeg[chanLeft] = NIL THEN chanPin.conctSeg[chanLeft] _ seg ELSE chanPin.altConctSeg[chanLeft] _ seg}; <> <<{chanPin.conctSeg[chanLeft] _ seg; -- chanPin.conctSeg[chanRight] _ NIL -- }>> <> <> <<{IF chanPin.conctSeg[chanLeft] = NIL THEN chanPin.conctSeg[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] = { <> 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] = { <> 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] = { <> 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]] = { <> <> 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 => { <> 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."]}; }; <> 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; <> IncludeExit[leftPin, chanLeft]; IncludeExit[rightPin, chanRight]; <> FOR list: RouteChannel.ChanPinList _ dogLegList, list.rest WHILE list # NIL DO <> 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] = { <> 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: >> <> {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) => <> <<-- 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 <> <> <> HackedBreakWithInRange: PROC [chanData: RouteChannel.ChannelData, parms: RoutePrivate.RoutingAreaParms, rules: Route.DesignRules, seg: RouteChannel.Segment, range: RangeWithDir, pins: TestPins] RETURNS [break: SegBreakSpec _ NIL] = { <> <> <> <> 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]] = { <<>> <> <> <<>> <> 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]; <> IF Constraining[rules, pins.trialPin, pins.leftExitPin] THEN notAllowed _ TRUE; IF Constraining[rules, pins.trialPin, pins.rightExitPin] THEN notAllowed _ TRUE; <> [minLimit, maxLimit] _ RouteChannel.FindConstraintLimits[chanPins, parms, rules, leftIndex, rightIndex, CheckInner]; FOR index: RouteChannel.MPinsOnCh IN [minLimit .. maxLimit] WHILE ~notAllowed DO <> 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]; <> [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 <> AddConstraintsToPin[graph, newLowerConstraintNode, bottomPin]}; <> <> <> 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 <> AddConstraintsFromPin[graph, topPin, newUpperConstraintNode]}; IF constrainBottom AND constrainTop THEN { IF bottomNet = topNet THEN notAllowed _ TRUE; -- Rule 1 }; ENDLOOP; ENDLOOP; <> 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]; <> [] _ RouteDiGraph.RemoveNode[graph, newUpperConstraintNode]; [] _ RouteDiGraph.RemoveNode[graph, newLowerConstraintNode]; RouteDiGraph.IncludeNode[graph, originalNode]; RouteDiGraph.IncludeArcs[graph, originalArcs]}; }; GetBreakSpec: PROC [break: FullSegBreakSpec] RETURNS [segBreak: SegBreakSpec _ NIL] ~ { <> 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] ~ { <> 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] = { <> <> <> <> <> <<>> 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 { <> [] _ 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]; <> 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]]; } 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]]; }; <> RouteChannel.AuditPins[chanPins] }; GetPinsOnNet: PROC [chanPins: RouteChannel.RoutingChannelPins, net: RoutePrivate.Net] RETURNS [pinLists: ChanPinListSet_ [NIL, NIL, NIL, NIL]] ~ { <> <> <> EachPinPosition: RouteChannel.EachPinPositionActionProc ~ { <> EachPin: RouteChannel.EachPinActionProc ~ { <> 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] ~ { <> EachPinPosition: RouteChannel.EachPinPositionActionProc ~ { <> EachPin: RouteChannel.EachPinActionProc ~ { <> 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] ~ { <> 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] = { <> 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 { <> <<>> <> 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 <> IF ~RouteDiGraph.PathExists[graph, upperNode, lowerNode] THEN <> [] _ RouteDiGraph.AddNewArc[graph, NIL, upperNode, lowerNode]}}}; AddConstraintsToPin: PROC [graph: RouteDiGraph.Graph, constraintNode: RouteDiGraph.Node, pin: RouteChannel.ChanPin] ~ { <> 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] ~ { <> 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] ~ { <> 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] = { <> ArcProc: RouteDiGraph.EnumArcsFromNodeProc = { <> 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] = { <> ArcProc: RouteDiGraph.EnumArcsFromNodeProc = { <> 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]}; }.