<> <> <> <> <> DIRECTORY Basics, CD, List, Rope, Route, RouteChannel, RouteDiGraph, RoutePrivate, RouteUtil, TerminalIO; RouteChannelConstraintsImpl: CEDAR PROGRAM IMPORTS List, Rope, Route, RouteChannel, RouteDiGraph, RouteUtil, TerminalIO EXPORTS RouteChannel SHARES Route = { SegBreakType: TYPE = {dogLeg, exit}; -- should add pinDogLeg sometime SegBreakSpec: TYPE = REF SegBreakSpecRec; SegBreakSpecRec: TYPE = RECORD [ pos: Route.Number _ 0, type: SegBreakType _ dogLeg]; Lmr: TYPE = {left, middle, right}; FullSegBreakSpec: TYPE = RECORD [ seg: RouteChannel.Segment _NIL, breaks: ARRAY Lmr OF SegBreakSpec _ ALL[NIL]]; BreakResult: TYPE = RECORD [ deltaDensity: Route.Number, duplicateLength: Route.Number, numDogLegs: Route.Number]; RangeWithDirList: TYPE = LIST OF RangeWithDir; RangeWithDir: TYPE = RECORD [ range: RoutePrivate.Range, dir: RouteChannel.GoingDirection]; ChanPinListSet: TYPE = RECORD [ leftExit, rightExit: RouteChannel.ChanPin _ NIL, bottomList, topList: RouteChannel.ChanPinList _ NIL]; ChanPinListPair: TYPE = RECORD [ list1, list2: RouteChannel.ChanPinList _ NIL]; TestPins: TYPE = REF TestPinsRec; TestPinsRec: TYPE = RECORD [ trialPin, leftExitPin, rightExitPin: RouteChannel.ChanPin _ NIL]; GenerateConstraints: PUBLIC PROCEDURE[routingArea: Route.RoutingArea, routerUsed: RoutePrivate.RouterUsed] RETURNS [anythingToDo: BOOLEAN] = { <> <> <<>> <> chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins; parms: RoutePrivate.RoutingAreaParms _ NARROW[routingArea.parms]; 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[routingArea]; -- unlink the old graph chanData.constraints _ RouteDiGraph.CreateGraph[graphName]; FOR index: RouteChannel.MPinsOnCh IN [1 .. chanPins.count] DO WidestPinProc: RouteChannel.EachPinActionProc = { IF pin # NIL THEN widestPinD2 _ MAX[widestPinD2, RouteUtil.GetWidthWithContact[routingArea, pin.pWidth]/2]}; LimitProc: RouteChannel.EachPinActionProc = { IF pin # NIL THEN {width: Route.Number _ RouteUtil.GetWidthWithContact[routingArea, pin.pWidth]/2; pinPos: Route.Number _ pin.pinPosition.pLoc; IF pinPos = pLoc THEN quit _ TRUE ELSE IF pinPos < pLoc THEN quit _ pinPos + width + routingArea.rules.branchSpacing > pLoc - widestPinD2 ELSE -- pinPos >= pLoc quit _ pLoc + widestPinD2 + routingArea.rules.branchSpacing > pinPos - width}}; pinPosition: RouteChannel.PinPosition _ chanPins.sides[index]; pLoc: Route.Number _ pinPosition.pLoc; widestPinD2: Route.Number _ RouteUtil.GetWidthWithContact[routingArea, routingArea.rules.branchWidth]/2; minLimit, maxLimit: RouteChannel.MPinsOnCh; <> [] _ RouteChannel.EnumPins[routingArea, pinPosition, WidestPinProc]; [minLimit, maxLimit] _ RouteChannel.FindConstraintLimits[routingArea, index, index, LimitProc]; FOR upperIndex: RouteChannel.MPinsOnCh IN [minLimit .. maxLimit] DO upperPinPosition: RouteChannel.PinPosition _ chanPins.sides[upperIndex]; upperPin: RouteChannel.ChanPin _ upperPinPosition.pins[chanTop]; lowerPin: RouteChannel.ChanPin _ pinPosition.pins[chanBottom]; IF ProcessConstraints[routingArea, upperPin, lowerPin, middle, pins] THEN GOTO GoRound; <<>> <> FOR innerPins: RouteChannel.ChanPinList _ pinPosition.innerPins, innerPins.rest WHILE innerPins # NIL DO innerPin: RouteChannel.ChanPin _ innerPins.first; <<>> <> IF ProcessConstraints[routingArea, upperPin, innerPin, middle, pins] THEN GOTO GoRound; IF ProcessConstraints[routingArea, 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: Route.Number _ NARROW[ref1, RouteChannel.ChanPin].qLoc; p2: Route.Number _ NARROW[ref2, RouteChannel.ChanPin].qLoc; RETURN[IF p1 < p2 THEN Basics.Comparison.less ELSE IF p1 = p2 THEN Basics.Comparison.equal ELSE Basics.Comparison.greater]}; whichEnd: Lmr _ IF index = 1 THEN left ELSE right; mungedPinList: 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[routingArea, 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[routingArea, seg, NIL, whichEnd, pins]; IF BreaksFound[break] > 0 THEN { DoBreak[routingArea, break]; GOTO GoRound} ELSE { -- mark seg as failed -- seg.failed _ TRUE; TerminalIO.WriteRope[Rope.Cat["\nunable to find a place to dogleg, net: ", seg.net.name, " failed"]]}}; IF FALSE 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 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; chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; graph: RouteDiGraph.Graph _ chanData.constraints; IF leftToRightSegList # NIL THEN <> {density: RouteChannel.Density _ RouteChannel.ComputeDensity[routingArea]; segBreak: FullSegBreakSpec _ FindBreak[routingArea, leftToRightSegList, density, whichEnd, pins]; IF BreaksFound[segBreak] > 0 THEN DoBreak[routingArea, segBreak] ELSE { -- choose a victim -- lSegs.first.failed _ TRUE; TerminalIO.WriteRope[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[routingArea]; segBreak: FullSegBreakSpec _ FindBreak[routingArea, rightToLeftSegList, density, whichEnd, pins]; IF BreaksFound[segBreak] > 0 THEN DoBreak[routingArea, segBreak] ELSE { -- choose a victim -- lSegs.first.failed _ TRUE; TerminalIO.WriteRope[Rope.Cat["\nnet: ", lSegs.first.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 [routingArea: Route.RoutingArea] = { <> chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins; DestroyGraph: RouteDiGraph.EnumGraphProc = {NULL}; DestroyArc: RouteDiGraph.EnumArcProc = {NULL}; DestroyNode: RouteDiGraph.EnumNodeProc = { nodeInfo: RouteChannel.SegmentConstraint _ NARROW[node.nodeInfo]; nodeInfo.segment _ NIL}; ClearConstraints: RouteChannel.EachPinActionProc = { leftSeg: RouteChannel.Segment _ pin.conctSeg[chanLeft]; rightSeg: RouteChannel.Segment _ pin.conctSeg[chanRight]; IF leftSeg # NIL THEN leftSeg.constraintNode _ NIL; IF rightSeg # NIL THEN rightSeg.constraintNode _ NIL}; FOR index: RouteChannel.MPinsOnCh IN [1 .. chanPins.count] DO pinPosition: RouteChannel.PinPosition _ chanPins.sides[index]; [] _ RouteChannel.EnumPins[routingArea, pinPosition, ClearConstraints]; ENDLOOP; RouteDiGraph.DestroyGraph[chanData.constraints, DestroyGraph, DestroyNode, DestroyArc]}; ProcessConstraints: PROCEDURE[routingArea: Route.RoutingArea, upperPin, lowerPin: RouteChannel.ChanPin, whichEnd: Lmr, 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[routingArea, 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]; IF DoConstraint[routingArea, lowerSeg, upperSeg, whichEnd, pins] THEN segBroken _ TRUE; ENDLOOP; -- FOR upperSegIndex ENDLOOP; -- FOR lowerSegIndex }; Constraining: PROC [routingArea: Route.RoutingArea, pin1, pin2: RouteChannel.ChanPin] RETURNS [constraining: BOOLEAN _ FALSE] = { <> IF pin1 # NIL AND pin2 # NIL THEN {p1: Route.Number _ pin1.pinPosition.pLoc; w1WContact: Route.Number _ RouteUtil.GetWidthWithContact[routingArea, pin1.pWidth]/2; w1: Route.Number _ pin1.pWidth/2; p2: Route.Number _ pin2.pinPosition.pLoc; w2WContact: Route.Number _ RouteUtil.GetWidthWithContact[routingArea, pin2.pWidth]/2; w2: Route.Number _ pin2.pWidth/2; IF p1 = p2 THEN constraining _ TRUE ELSE IF p1 < p2 THEN constraining _ (p1 + w1WContact + routingArea.rules.branchSpacing > p2 - w2) OR (p1 + w1 + routingArea.rules.branchSpacing > p2 - w2WContact) ELSE -- p1 > p2 constraining _ (p2 + w2WContact + routingArea.rules.branchSpacing > p1 - w1) OR (p2 + w2 + routingArea.rules.branchSpacing > p1 - w1WContact)}}; DoConstraint: PROCEDURE[routingArea: Route.RoutingArea, 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.netNum # upperSeg.net.netNum OR lowerSeg.net.netPart # upperSeg.net.netPart) THEN { segList: RouteChannel.SegmentList; chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; graph: RouteDiGraph.Graph _ chanData.constraints; nets: RoutePrivate.NetTab _ NARROW[routingArea.nets]; lowerNode: RouteDiGraph.Node _ lowerSeg.constraintNode; upperNode: RouteDiGraph.Node _ upperSeg.constraintNode; IF lowerNode = NIL THEN {constraint: RouteChannel.SegmentConstraint _ NEW[RouteChannel.SegmentConstraintRec _ [lowerSeg.net.name, lowerSeg]]; lowerNode _ RouteDiGraph.AddNewNode[graph, constraint]; lowerSeg.constraintNode _ lowerNode}; IF upperNode = NIL THEN {constraint: RouteChannel.SegmentConstraint _ NEW[RouteChannel.SegmentConstraintRec _ [upperSeg.net.name, upperSeg]]; upperNode _ RouteDiGraph.AddNewNode[graph, constraint]; upperSeg.constraintNode _ upperNode}; segList _ SegsInCycle[graph, lowerNode, upperNode]; IF segList # NIL THEN <> {density: RouteChannel.Density _ RouteChannel.ComputeDensity[routingArea]; segBreak: FullSegBreakSpec _ FindBreak[routingArea, segList, density, whichEnd, pins]; IF BreaksFound[segBreak] > 0 THEN DoBreak[routingArea, segBreak] ELSE { -- choose a victim -- segList.first.failed _ TRUE; TerminalIO.WriteRope[Rope.Cat["\nnet: ", segList.first.net.name, " failed, unable to find a place to dogleg"]]}; segBroken _ TRUE} ELSE { -- add a segment constraint <> <> 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 = { IF arc.superiorNode = lowerNode THEN {nodeInfo: RouteChannel.SegmentConstraint _ NARROW[lowerNode.nodeInfo]; segList _ CONS[nodeInfo.segment, segList]; quit _ TRUE} ELSE quit _ RouteDiGraph.EnumArcsFromNode[graph, arc.superiorNode, out, ArcProc]; IF quit THEN {nodeInfo: RouteChannel.SegmentConstraint _ NARROW[node.nodeInfo]; segList _ CONS[nodeInfo.segment, segList]}}; [] _ RouteDiGraph.EnumArcsFromNode[graph, upperNode, out, ArcProc]}; FindBreak: PROC [routingArea: Route.RoutingArea, segList: RouteChannel.SegmentList, density: RouteChannel.Density, whichEnd: Lmr, pins: TestPins] RETURNS [bestBreak: FullSegBreakSpec _ [NIL, [NIL, NIL, NIL]]] = { <> bestResult: BreakResult _ [LAST[INT], LAST[INT], LAST[INT]]; <> FOR segs: RouteChannel.SegmentList _ segList, segs.rest WHILE segs # NIL DO seg: RouteChannel.Segment _ segs.first; break: FullSegBreakSpec _ BreakOneSeg[routingArea, seg, density, whichEnd, pins]; result: BreakResult _ EvalBreak[routingArea, break, density]; IF CompareResult[result, bestResult] = less THEN {bestResult _ result; bestBreak _ break}; ENDLOOP; IF bestBreak.seg = NIL THEN RETURN[[NIL, [NIL, NIL, NIL]]]}; BreakOneSeg: PROC [routingArea: Route.RoutingArea, seg: RouteChannel.Segment, density: RouteChannel.Density, whichEnd: Lmr, pins: TestPins] RETURNS [break: FullSegBreakSpec] = { <> parms: RoutePrivate.RoutingAreaParms _ NARROW[routingArea.parms]; exitsSeparate: BOOLEAN _ IF parms.routerUsed = channel THEN FALSE ELSE TRUE; pinLists: ChanPinListSet _ GetPins[exitsSeparate, seg]; rangeList: RangeWithDirList _ SegRanges[routingArea, pinLists]; break _ [seg, [NIL, NIL, NIL]]; SELECT parms.routerUsed FROM channel => { FOR ranges: RangeWithDirList _ rangeList, ranges.rest WHILE ranges # NIL DO break.breaks[middle] _ BreakWithInRange[routingArea, seg, ranges.first, pins]; IF break.breaks[middle] # NIL THEN EXIT; ENDLOOP; IF break.breaks[middle] = NIL THEN break.breaks[middle] _ BreakAtExit[routingArea, seg, density]}; switchBox => { DoMiddle: PROC [] ~ { IF top AND bottom AND BreaksFound[break] = 0 THEN { FOR ranges: RangeWithDirList _ rangeList, ranges.rest WHILE ranges # NIL DO break.breaks[middle] _ BreakWithInRange[routingArea, seg, ranges.first, 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[routingArea, 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[routingArea, seg, rightRange, pins]}}; chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; cEnd1: Route.Number _ chanData.chanPins.cEnd1; cEnd2: Route.Number _ chanData.chanPins.cEnd2; left, top, right, bottom: BOOLEAN; [left, top, right, bottom] _ RouteChannel.PinsOnSide[routingArea, seg]; SELECT TRUE FROM whichEnd = left => {DoLeft; DoRight; DoMiddle}; whichEnd = right => {DoRight; DoLeft; DoMiddle}; seg.trackConstraint # 0 => {DoRight; DoLeft; DoMiddle}; ENDCASE => {DoMiddle; DoRight; DoLeft}; }; ENDCASE => Route.Error[programmingError, "Invalid router being used."]; }; BreakWithInRange: PROC [routingArea: Route.RoutingArea, seg: RouteChannel.Segment, range: RangeWithDir, pins: TestPins] RETURNS [break: SegBreakSpec _ NIL] = { <> WidestPinProc: RouteChannel.EachPinActionProc = { IF pin # NIL THEN widestPinD2 _ MAX[widestPinD2, RouteUtil.GetWidthWithContact[routingArea, pin.pWidth]/2]}; NextPosToRight: PROC [pinIndex: RouteChannel.ZMPinsOnCh] RETURNS[pos: Route.Number] ~ { IF pinIndex = 0 THEN pos _ chanPins.cEnd1 + routingArea.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[routingArea, pinPosition, WidestPinProc]; pos _ pinPosition.pLoc + widestPinD2 + routingArea.rules.branchSpacing + seg.net.branchWidth/2}}; NextPosToLeft: PROC [pinIndex: RouteChannel.ZMPinsOnCh] RETURNS[pos: Route.Number] ~ { IF pinIndex <= 0 THEN pos _ FIRST[INT] ELSE IF pinIndex = chanPins.count THEN pos _ chanPins.cEnd2 - routingArea.rules.branchSpacing - seg.net.branchWidth ELSE { pinPosition: RouteChannel.PinPosition _ chanPins.sides[pinIndex]; widestPinD2 _ minPinD2; [] _ RouteChannel.EnumPins[routingArea, pinPosition, WidestPinProc]; pos _ pinPosition.pLoc - widestPinD2 - routingArea.rules.branchSpacing - seg.net.branchWidth/2}}; -- minPinD2: Route.Number _ RouteUtil.GetWidthWithContact[routingArea, routingArea.rules.branchWidth]/2; minPinD2: Route.Number _ routingArea.rules.branchWidth/2; chanPins: RouteChannel.RoutingChannelPins _ NARROW[routingArea.privateData, RouteChannel.ChannelData].chanPins; widestPinD2: Route.Number; SELECT range.dir FROM leftToRight => { nextLower: RouteChannel.ZMPinsOnCh _ ClosestPins[routingArea, range.range.l].nextLower; FOR pos: Route.Number _ range.range.l, NextPosToRight[nextLower] WHILE pos <= range.range.r DO IF ~DogLegNotAllowed[routingArea, seg, pos, pins] THEN { break _ NEW[SegBreakSpecRec _ [pos, dogLeg]]; EXIT}; nextLower _ MIN[chanPins.count+1, nextLower + 1]; ENDLOOP}; rightToLeft => { nextHigher: RouteChannel.ZMPinsOnCh _ ClosestPins[routingArea, range.range.r].nextHigher; FOR pos: Route.Number _ range.range.r, NextPosToLeft[nextHigher] WHILE pos >= range.range.l DO IF ~DogLegNotAllowed[routingArea, seg, pos, pins] THEN { break _ NEW[SegBreakSpecRec _ [pos, dogLeg]]; EXIT}; nextHigher _ MAX[0, nextHigher - 1]; ENDLOOP}; ENDCASE}; DogLegNotAllowed: PROC [routingArea: Route.RoutingArea, seg: RouteChannel.Segment, pos: Route.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[routingArea, pin, pins.trialPin] THEN quit _ TRUE}; OuterConstraints: RouteChannel.EachPinActionProc = { IF pin # NIL THEN IF pin.kindOfPin = chanConnect OR pin.kindOfPin = compPin THEN IF Constraining[routingArea, pin, pins.trialPin] THEN quit _ TRUE}; chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; netTab: RoutePrivate.NetTab _ NARROW[routingArea.nets]; chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins; minLimit, maxLimit, leftIndex, rightIndex: RouteChannel.ZMPinsOnCh; width: Route.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[routingArea, pos]; <> IF Constraining[routingArea, pins.trialPin, pins.leftExitPin] THEN notAllowed _ TRUE; IF Constraining[routingArea, pins.trialPin, pins.rightExitPin] THEN notAllowed _ TRUE; <> [minLimit, maxLimit] _ RouteChannel.FindConstraintLimits[routingArea, leftIndex, rightIndex, CheckInner]; FOR index: RouteChannel.MPinsOnCh IN [minLimit .. maxLimit] WHILE ~notAllowed DO <> pinPosition: RouteChannel.PinPosition _ chanPins.sides[index]; notAllowed _ RouteChannel.EnumPins[routingArea, pinPosition, CheckInner]; ENDLOOP; <<>> <> [minLimit, maxLimit] _ RouteChannel.FindConstraintLimits[routingArea, leftIndex, rightIndex, OuterConstraints]; FOR index: RouteChannel.MPinsOnCh IN [minLimit .. maxLimit] WHILE ~notAllowed DO pinPosition: RouteChannel.PinPosition _ chanPins.sides[index]; bottomPin: RouteChannel.ChanPin _ pinPosition.pins[chanBottom]; topPin: RouteChannel.ChanPin _ pinPosition.pins[chanTop]; bottomNet: RoutePrivate.Net _ FindConnectedNet[bottomPin]; topNet: RoutePrivate.Net _ FindConnectedNet[topPin]; constrainTop: BOOLEAN _ Constraining[routingArea, topPin, pins.trialPin]; constrainBottom: BOOLEAN _ Constraining[routingArea, 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[routingArea, topPin, bP] AND constrainTop AND constrainBottom THEN notAllowed _ TRUE; IF topNet = bN AND Constraining[routingArea, bottomPin, tP] AND constrainTop AND constrainBottom THEN notAllowed _ TRUE; ENDLOOP; <> <> IF constrainTop OR constrainBottom THEN notAllowed _ TRUE; ENDLOOP}; BreakAtExit: PROC [routingArea: Route.RoutingArea, seg: RouteChannel.Segment, density: RouteChannel.Density] RETURNS [break: SegBreakSpec] = { <> chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins; leftBreak: SegBreakSpec _ NEW[SegBreakSpecRec _ [chanPins.cEnd1, exit]]; leftFullBreak: FullSegBreakSpec _ [seg, [leftBreak, NIL, NIL]]; rightBreak: SegBreakSpec _ NEW[SegBreakSpecRec _ [chanPins.cEnd2, exit]]; rightFullBreak: FullSegBreakSpec _ [seg, [NIL, NIL, rightBreak]]; leftResult: BreakResult _ EvalBreak[routingArea, leftFullBreak, density]; rightResult: BreakResult _ EvalBreak[routingArea, rightFullBreak, density]; IF CompareResult[leftResult, rightResult] = less THEN RETURN [leftBreak] ELSE RETURN [rightBreak]}; EvalBreak: PROC [routingArea: Route.RoutingArea, break: FullSegBreakSpec, density: RouteChannel.Density] RETURNS [result: BreakResult] = { <> maxDensity: Route.Number; lowerRange, upperRange, overlap: RoutePrivate.Range; parms: RoutePrivate.RoutingAreaParms _ NARROW[routingArea.parms]; exitsSeparate: BOOLEAN _ IF parms.routerUsed = channel THEN FALSE ELSE TRUE; pinLists: ChanPinListSet _ GetPins[exitsSeparate, break.seg]; IF BreaksFound[break] = 0 THEN RETURN[[LAST[INT], LAST[INT], LAST[INT]]]; IF break.breaks[middle] # NIL THEN { lowerRange _ RouteChannel.Span[[break.breaks[middle].pos, break.breaks[middle].pos], RouteChannel.GetRange[pinLists.bottomList]]; upperRange _ RouteChannel.Span[[break.breaks[middle].pos, break.breaks[middle].pos], RouteChannel.GetRange[pinLists.topList]]; overlap _ RouteChannel.Overlap[lowerRange, upperRange]; IF overlap.l > overlap.r THEN Route.Error[programmingError, "overlap should not be NIL."]} ELSE overlap _ [0,0]; maxDensity _ AddSeg[routingArea, density, overlap, break.seg.qWidth]; result.deltaDensity _ maxDensity - density.maxDensity; result.duplicateLength _ overlap.r - overlap.l; result.numDogLegs _ 0; FOR lmr: Lmr IN Lmr DO IF break.breaks[lmr] # NIL THEN result.numDogLegs _ result.numDogLegs + 1; ENDLOOP}; DoBreak: PROC [routingArea: Route.RoutingArea, fullSegBreak: FullSegBreakSpec] = { <> <> <> <> <> <<>> UnlinkSegFromPins: RouteChannel.EachPinActionProc ~ { IF pin.conctSeg[chanLeft] = oldSeg THEN pin.conctSeg[chanLeft] _ NIL; IF pin.conctSeg[chanRight] = oldSeg THEN pin.conctSeg[chanRight] _ NIL; IF pin.altConctSeg[chanLeft] = oldSeg THEN pin.altConctSeg[chanLeft] _ NIL; IF pin.altConctSeg[chanRight] = oldSeg THEN pin.altConctSeg[chanRight] _ NIL; }; chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins; parms: RoutePrivate.RoutingAreaParms _ NARROW[routingArea.parms]; oldSeg: RouteChannel.Segment _ fullSegBreak.seg; branchWidth: Route.Number _ oldSeg.net.branchWidth; trunkWidth: Route.Number _ oldSeg.net.trunkWidth; IF BreaksFound[fullSegBreak] # 1 THEN Route.Error[programmingError, "Not suppose to happen"]; [] _ RouteChannel.EnumPinsOnSeg[routingArea, oldSeg, UnlinkSegFromPins]; FOR lmr: Lmr IN Lmr DO segBreak: SegBreakSpec _ fullSegBreak.breaks[lmr]; IF segBreak # NIL THEN { pinIndex: RouteChannel.ZMPinsOnCh _ RouteChannel.FindPinPos[routingArea, segBreak.pos]; pinPosition: RouteChannel.PinPosition _ chanPins.sides[pinIndex]; upperPin, lowerPin: RouteChannel.ChanPin _ NIL; pinListPair: ChanPinListPair; seg1: RouteChannel.Segment _ NEW[RouteChannel.SegmentRec _ [net: oldSeg.net, qWidth: trunkWidth, exitBreak: oldSeg.exitBreak]]; seg2: RouteChannel.Segment _ NEW[RouteChannel.SegmentRec _ [net: oldSeg.net, qWidth: trunkWidth, exitBreak: oldSeg.exitBreak]]; SELECT segBreak.type FROM dogLeg => { exitsSeparate: 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; seg2.exitBreak _ TRUE; 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[routingArea, seg1, oldSeg.trackConstraint]; SetTrackConstraints[routingArea, seg2, oldSeg.trackConstraint]; TerminalIO.WriteRope[Rope.Cat["\ntrunk segment for net: ", fullSegBreak.seg.net.name, " divided at: "]]; TerminalIO.WriteInt[chanPins.sides[pinIndex].pLoc/routingArea.rules.CDLambda]; <<>> <> <> <> }; ENDLOOP; }; DividePins: PROC [which: Lmr, pinLists: ChanPinListSet, pin1, pin2: RouteChannel.ChanPin] RETURNS [pinListPair: ChanPinListPair _ [NIL, NIL]] = { SELECT which FROM left => { IF pinLists.leftExit = NIL THEN Route.Error[programmingError, "exit dogleg with no exit"]; pinListPair.list1 _ LIST[pin1, pinLists.leftExit]; pinListPair.list2 _ RouteChannel.Combine[pinLists.bottomList, pinLists.topList, LIST[pinLists.rightExit, pin2]]}; middle => { pinListPair.list1 _ RouteChannel.Combine[LIST[pin1], pinLists.bottomList, NIL]; pinListPair.list2 _ RouteChannel.Combine[LIST[pin2], pinLists.topList, NIL]; pinListPair _ AddToClosestList[pinListPair, pinLists.leftExit]; pinListPair _ AddToClosestList[pinListPair, pinLists.rightExit]}; right => { IF pinLists.rightExit = NIL THEN Route.Error[programmingError, "exit dogleg with no exit"]; pinListPair.list1 _ LIST[pin1, pinLists.rightExit]; pinListPair.list2 _ RouteChannel.Combine[pinLists.bottomList, pinLists.topList, LIST[pinLists.leftExit, pin2]]}; ENDCASE; }; SetTrackConstraints: PROC [routingArea: Route.RoutingArea, seg: RouteChannel.Segment, trackConstraint: Route.Number] = { EachPin: RouteChannel.EachPinActionProc = { IF pin # NIL THEN { IF pin.trackConstraint # 0 THEN seg.trackConstraint _ pin.trackConstraint}}; [] _ RouteChannel.EnumPinsOnSeg[routingArea, seg, EachPin] }; AddToClosestList: PROC [pinListPair: ChanPinListPair, pin: RouteChannel.ChanPin] RETURNS [result: ChanPinListPair] ~ { l1Range: RoutePrivate.Range _ RouteChannel.GetRange[pinListPair.list1]; l2Range: RoutePrivate.Range _ RouteChannel.GetRange[pinListPair.list2]; IF pin # NIL THEN { pLoc: Route.Number _ pin.pinPosition.pLoc; IF l1Range.l <= pLoc AND pLoc <= l1Range.r THEN RETURN[[CONS[pin, pinListPair.list1], pinListPair.list2]] ELSE IF l2Range.l <= pLoc AND pLoc <= l2Range.r THEN RETURN[[pinListPair.list1, CONS[pin, pinListPair.list2]]] ELSE { distToL1: Route.Number _ MIN[ABS[pLoc - l1Range.l], ABS[pLoc - l1Range.r]]; distToL2: Route.Number _ MIN[ABS[pLoc - l2Range.l], ABS[pLoc - l2Range.r]]; IF distToL1 < distToL2 THEN RETURN[[CONS[pin, pinListPair.list1], pinListPair.list2]] ELSE RETURN[[pinListPair.list1, CONS[pin, pinListPair.list2]]]}} ELSE RETURN[pinListPair]}; LinkSegsToPins: PROC [seg: RouteChannel.Segment, pinList: RouteChannel.ChanPinList, newPin: RouteChannel.ChanPin] = { <> PinCompare: List.CompareProc = { p1: Route.Number _ NARROW[ref1, RouteChannel.ChanPin].pinPosition.pLoc; p2: Route.Number _ NARROW[ref2, RouteChannel.ChanPin].pinPosition.pLoc; RETURN[IF p1 < p2 THEN Basics.Comparison.less ELSE IF p1 = p2 THEN Basics.Comparison.equal ELSE Basics.Comparison.greater]}; mungedPinList: 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 # newPin THEN {chanPin.conctSeg[chanRight] _ seg} <> ELSE <> {IF chanPin.conctSeg[chanRight] = NIL THEN chanPin.conctSeg[chanRight] _ seg ELSE chanPin.altConctSeg[chanRight] _ seg}; seg.exteriorPins[chanLeft] _ chanPin} ELSE IF chanPin = rightPin THEN {IF chanPin # newPin THEN <> {chanPin.conctSeg[chanLeft] _ seg; -- chanPin.conctSeg[chanRight] _ NIL -- } ELSE <> {IF chanPin.conctSeg[chanLeft] = NIL THEN chanPin.conctSeg[chanLeft] _ seg ELSE chanPin.altConctSeg[chanLeft] _ seg}; seg.exteriorPins[chanRight] _ chanPin} ELSE {seg.interiorPins _ CONS[chanPin, seg.interiorPins]; SELECT chanPin.kindOfPin FROM chanConnect, compPin => { chanPin.conctSeg[chanRight] _ seg; chanPin.conctSeg[chanLeft] _ seg}; dogLeg => { IF chanPin.conctSeg[chanRight] = NIL AND chanPin.conctSeg[chanLeft] = NIL THEN {chanPin.conctSeg[chanRight] _ seg; chanPin.conctSeg[chanLeft] _ seg} ELSE {chanPin.altConctSeg[chanLeft] _ seg; chanPin.altConctSeg[chanRight] _ seg}}; exitPin => Route.Error[programmingError, "Exit pin not on end of segment"]; ENDCASE}; ENDLOOP}; AddSeg: PROC [routingArea: Route.RoutingArea, density: RouteChannel.Density, r: RoutePrivate.Range, width: Route.Number] RETURNS [maxDensity: Route.Number _ 0] = { <> chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins; IF density # NIL THEN FOR index: RouteChannel.MPinsOnCh IN [1 .. chanPins.count] DO pos: Route.Number _ chanPins.sides[index].pLoc; thisDensity: Route.Number _ IF r.l <= pos AND pos <= r.r THEN density.values[index] + width ELSE density.values[index]; maxDensity _ MAX[maxDensity, thisDensity]; ENDLOOP}; CompareResult: PROC [r1, r2: BreakResult] RETURNS [result: Basics.Comparison] = { <> result _ RouteUtil.SimpleCompare[r1.numDogLegs, r2.numDogLegs]; IF result # equal THEN RETURN; result _ RouteUtil.SimpleCompare[r1.deltaDensity, r2.deltaDensity]; IF result # equal THEN RETURN; result _ RouteUtil.SimpleCompare[r1.duplicateLength, r2.duplicateLength]; RETURN}; ClosestPins: PROC [routingArea: Route.RoutingArea, target: Route.Number] RETURNS [nextLower, nextHigher: RouteChannel.ZMPinsOnCh _ 0] = { <> chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins; 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 [routingArea: Route.RoutingArea, pinLists: ChanPinListSet] RETURNS [rangeList: RangeWithDirList] = { <> chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins; lr: RoutePrivate.Range _ RouteChannel.GetRange[pinLists.bottomList]; ur: RoutePrivate.Range _ RouteChannel.GetRange[pinLists.topList]; ce1: Route.Number _ chanPins.cEnd1; ce2: Route.Number _ chanPins.cEnd2; min: Route.Number _ MIN[lr.l, ur.l]; max: Route.Number _ MAX[lr.r, ur.r]; left: RangeWithDir _ IF ce1 < min THEN [[ce1, min], rightToLeft] ELSE [[ce1, ce1], rightToLeft]; right: RangeWithDir _ IF ce2 > max THEN [[max, ce2], leftToRight] ELSE [[ce2, ce2], leftToRight]; SELECT TRUE FROM lr.r < lr.l OR ur.r < ur.l => rangeList _ LIST[RangeWithDir[[ce1, ce2], leftToRight]]; lr.r < ur.l => <<-- ur: >> <<-- lr: >> {gap: RangeWithDir _ [[lr.r, ur.l], leftToRight]; rangeList _ LIST[gap, [lr, rightToLeft], [ur, leftToRight], left, right]}; (lr.l <= ur.l AND ur.l <= lr.r) AND (ur.l <= lr.r AND lr.r <= ur.r) => <<-- ur: >> <<-- lr: >> {dual: RangeWithDir _ [[ur.l, lr.r], leftToRight]; ls: RangeWithDir _ [[lr.l, dual.range.l], rightToLeft]; rs: RangeWithDir _ [[dual.range.r, ur.r], leftToRight]; rangeList _ LIST[dual, ls, rs, left, right]}; (lr.l <= ur.l AND ur.l < lr.r) AND (lr.l <= ur.r AND ur.r <= lr.r) => <<-- ur: >> <> {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 }.