DIRECTORY Basics, CD, List, IO, Rope, Route, RouteChannel, RouteDiGraph, RoutePrivate, RouteUtil, TerminalIO; RouteChannelConstraintsImpl: CEDAR PROGRAM IMPORTS List, IO, 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 = { spacing: INT _ MAX[routingArea.rules.branchSpacing, routingArea.rules.trunkSpacing]; 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 + spacing > pLoc - widestPinD2 ELSE -- pinPos >= pLoc quit _ pLoc + widestPinD2 + spacing > 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.PutRope[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.PutRope[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.PutRope[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] = { spacing: INT _ MAX[routingArea.rules.branchSpacing, routingArea.rules.trunkSpacing]; 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 + spacing > p2 - w2) OR (p1 + w1 + spacing > p2 - w2WContact) ELSE -- p1 > p2 constraining _ (p2 + w2WContact + spacing > p1 - w1) OR (p2 + w2 + spacing > 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.PutRope[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] ~ { spacing: INT _ MAX[routingArea.rules.branchSpacing, routingArea.rules.trunkSpacing]; IF pinIndex = 0 THEN pos _ chanPins.cEnd1 + spacing + 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 + spacing + RouteUtil.GetWidthWithContact[routingArea, seg.net.branchWidth]/2}}; NextPosToLeft: PROC [pinIndex: RouteChannel.ZMPinsOnCh] RETURNS[pos: Route.Number] ~ { spacing: INT _ MAX[routingArea.rules.branchSpacing, routingArea.rules.trunkSpacing]; IF pinIndex <= 0 THEN pos _ FIRST[INT] ELSE IF pinIndex = chanPins.count THEN pos _ chanPins.cEnd2 - spacing - seg.net.branchWidth ELSE { pinPosition: RouteChannel.PinPosition _ chanPins.sides[pinIndex]; widestPinD2 _ minPinD2; [] _ RouteChannel.EnumPins[routingArea, pinPosition, WidestPinProc]; pos _ pinPosition.pLoc - widestPinD2 - spacing - RouteUtil.GetWidthWithContact[routingArea, 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.PutRope[Rope.Cat["\ntrunk segment for net: ", fullSegBreak.seg.net.name, ]]; TerminalIO.PutF1[" divided at: %g", IO.int[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 => {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) => {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) => {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) => {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) => {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 => {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 }. ΞRouteChannelConstraintsImpl.mesa Copyright c 1985, 1986 by Xerox Corporation. All rights reserved. by Bryan Preas July 10, 1985 6:57:00 pm PDT last edited by Bryan Preas February 11, 1987 6:26:48 pm PST run through the pins on the channel, create segment constraints from the pin to pin relationships return if no pins outer loop can be removed whe constraints by seg is added generate constraints for this coordinate, if any now do constraints for doglegs and exits wrt the upper pins first the upper pin, if any do the exits wrt each other if this is a switchBox and a channel end process pin to pin constraints break any segments that must be in 2 tracks IF index = chanPins.count THEN { Must resolve constraints accross the ends of the switchbox. If there is a constraint from a segment on one end to a segment on the other, it must be resolved. these are the pins on the left side of the channel these are the segments on the left pin choose a segment to break and the position to dogleg choose a segment to break and the position to dogleg must explicitly destroy the old data add a segment constraint if it does not create a loop do upper to lower pin constraint generate pin to pin constraints, process all segments attached to these pins determining if pin1 actually constrains pin2 add a segment constraint if it does not create a loop choose a segment to break and the position to dogleg need to change so I don't add duplicate constraints constrain Upper above Lower arcName: Rope.ROPE _ Rope.Cat[upperSeg.net.name,"-above-", lowerSeg.net.name]; recursively go through the constraints decide on which segment to divide and the position run through the segs in the cycle. find the best find the best position to break this seg find the best position to break this seg within this range see if a dogleg is allowed here must reserve place for future exits see if inner pins interfere see if there are existing dog legs see if outer pins interfere see if any nets within th range cross the channels see if a constraint loop is created later -- for now dont use pin positions that could cause constraint loops find the best exit to break this seg evaluate the break of ths seg at break break the segment at position: add pin position at fullSegBreak.breaks[mumble].pos unlink segBreak create 2 new segments link in the pins if this segment already has an exit on this side, then use that one, otherwise make a new pin remove these statments for production RouteChannel.AuditPins[routingArea]; RouteChannel.AuditSegs[routingArea]; link the segment to the pin in the list and vice versa update old seg pointer chanPin.conctSeg[chanLeft] _ NIL no old seg pointer, but make sure both segs on new pin are initialized update old seg pointer no old seg pointer, but make sure both segs on new pin are initialized compute the track density when this range is added compare r1 and r2 find the PinPosition closest to target. get the pins attached to the segment on the indicated side bottomList == lowerPinList and topList == upperPinList Compiler problem: [pinLists.bottomList, pinLists.topList] _ AddToClosestList[[pinLists.bottomList, pinLists.topList], pin]}; first include the obvious pins: top, bottom and dogleg next decide which segments the exit pins go in next decide which segments the dogleg pins go in Compiler problem: [pinLists.bottomList, pinLists.topList] _ AddToClosestList[[pinLists.bottomList, pinLists.topList], list.first]; find distinct ranges for this seg, use enumeration -- ur:  -- lr:  -- ur:  -- lr:  -- ur:  lr:  ur:  -- lr:  -- ur:  -- lr:  -- ur:  -- lr:  Κ"y˜codešœ#™#Kšœ Οmœ7™BKšœ.™.Kšœ=™=K™—šΟk ˜ KšœžœY˜cK˜—šΟnœžœž˜*KšžœI˜PKšžœ ˜Kšžœ ˜K˜KšœžœΟc ˜EKšœžœžœ˜)šœžœžœ˜ Kšœ˜Kšœ˜—Kšœžœ˜"šœžœžœ˜!Kšœžœ˜Kš œžœžœžœžœ˜.K˜—šœ žœžœ˜Kšœ˜Kšœ˜Kšœ˜K˜—Kšœžœžœžœ˜.šœžœžœ˜Kšœ˜Kšœ"˜"K˜—šœžœžœ˜Kšœ,žœ˜0Kšœ0žœ˜5K˜—šœžœžœ˜ Kšœ)žœ˜.K˜—Kšœ žœžœ ˜!šœ žœžœ˜Kšœ<žœ˜A—K˜š Ÿœžœž œFžœžœ˜ŽKšœ$™$Kšœ<™˜>Kšœ'žœ˜AKšœžœ˜.Kšœ žœžœ˜Kšœ-žœ7˜gKšœ!žœr˜–Kšœ-žœD˜tKšœ$žœs˜šKšœ.žœD˜uKšœ%žœt˜œKšœJ˜JKšžœžœžœžœ˜)K˜šžœ ž˜Kšœ9™9Kšœ žœ˜Kšžœžœžœ% ˜^Kšœ;˜;K˜šžœžœž˜=K˜šŸ œ$˜1šžœžœž˜KšœžœI˜Z—K˜—šŸ œ$˜-KšœT˜Tšžœžœž˜KšœP˜PK˜,šžœž˜Kšœž˜ —šžœžœž˜Kšœ4˜4—šžœ ˜Kšœ7˜7——K˜—Kšœ>˜>Kšœ&˜&Kšœh˜hKšœ+˜+K˜Kšœ0™0KšœD˜DKšœ_˜_šžœ$žœž˜CKšœH˜HKšœ@˜@Kšœ>˜>K˜KšžœCžœžœ ˜WK™Kšœ;™;šžœMžœ žœž˜hKšœ1˜1K™Kšœ™KšžœCžœžœ ˜WKšžœCžœžœ ˜WKšžœ ˜—šžœ ˜K˜——KšœD™Dšžœžœ žœžœ˜KK˜šŸ œ˜!Kšœžœ"˜;Kšœžœ"˜;šžœžœ žœ˜-Kšžœžœ žœ˜,Kšžœ˜!——K˜Kšœžœ žœžœ˜2Kšœžœ(˜@Kšœžœ)˜Aš žœ žœ œžœ žœž˜dKšœ!žœ˜5KšœF˜FK˜Kšœ™šžœžœžœ˜Kšœ!žœ˜:KšžœEžœžœ ˜Z—K˜Kšœ+™+šžœ3žœžœž˜IKšœ'˜'š žœžœžœ.žœ žœ˜Kšœ8žœ˜Mšžœžœ˜ Kšœžœ ˜*—šžœ ˜ Kšœ žœ˜Kšœe˜e——Kšžœžœžœ˜šœ ™ KšœŸ™ŸKšœ>˜>KšœB˜BKšœ2™2šžœ=žœ žœž˜UKšœ žœ˜5KšœF˜FKšœ&™&šžœ6žœ žœž˜MKšœ,˜,Kšœ8˜8Kšœ5˜5Kšœ]˜]Kšœ-˜-Kšœ%žœ˜EKšœ1˜1šžœžœž˜ Kšœ4™4KšœJ˜JKšœa˜aKšžœžœ˜@šžœ ˜Kšœžœ˜Kšœl˜l—K˜Kšœ žœžœ ˜ —KšœC˜Cšžœžœž˜ Kšœ4™4KšœJ˜JKšœa˜aKšžœžœ˜@šžœ ˜Kšœžœ˜Kšœl˜l—K˜Kšœ žœžœ ˜ —Kšžœ˜—Kšžœ˜—Kšœ˜—Kšžœ˜—Kšžœ˜ ——Kšžœžœ˜#Kšžœ ˜—Kšžœ ˜—šžœžœ ˜%K˜——šŸœžœžœ%˜GKšœ$™$K˜Kšœ%žœ˜EKšœ>˜>KšŸ œ žœ˜2K˜KšŸ œžœ˜.K˜šŸ œ˜*Kšœ+žœ˜AKšœžœ˜—K˜šŸœ$˜4Kšœ7˜7Kšœ9˜9Kšžœ žœžœžœ˜3Kšžœ žœžœžœ˜6K˜—šžœžœž˜=Kšœ>˜>KšœG˜GKšžœ˜—K˜KšœX˜XK˜—š Ÿœž œjžœ žœžœ˜―Kšœ5™5K˜Kšœ ™ š žœ žœžœ žœž˜)šžœžœž˜Bš žœžœžœžœžœž˜ šžœ/ž˜5KšœL™Lšžœ(žœžœ ž˜Yšžœ(žœžœ ž˜YKšœB˜BKšœB˜BKšžœ?žœ žœ˜WKšžœ ˜—Kšžœ ˜————Kšœ˜K˜——š Ÿ œžœDžœžœžœ˜K™,K˜KšœT˜Tš žœžœžœžœž˜!Kšœ*˜*KšœU˜UKšœ!˜!Kšœ)˜)KšœU˜UKšœ!˜!šžœ ž˜Kšœž˜—šžœžœ ž˜šœ4˜4Kšœ(˜(——šžœ  ˜šœ4˜4Kšœ+˜+———K˜—š Ÿ œž œjžœ žœžœ˜©Kšœ5™5K˜š žœ žœžœ žœžœž˜Aš žœžœžœ,žœ.žœ˜ŽK˜"Kšœ%žœ˜EKšœ1˜1Kšœžœ˜5Kšœ7˜7Kšœ7˜7šžœ žœž˜Kšœ.žœD˜uKšœ7˜7Kšœ%˜%—šžœ žœž˜Kšœ.žœD˜uKšœ7˜7Kšœ%˜%K˜—Kšœ3˜3šžœ žœž˜Kšœ4™4KšœJ˜JKšœV˜VKšžœžœ˜@šžœ ˜Kšœžœ˜Kšœn˜nK˜—Kšœ žœ˜—šžœ ˜"K˜Kšœ3™3Kšœ™šžœ7ž˜=KšœN™NKšœ#žœ˜A————K˜—šŸ œž œD˜ZKšžœ&žœ˜5K˜Kšœ&™&šŸœ'˜.šžœž˜$Kšœ,žœ˜GKšœ žœ˜*Kšœžœ˜ —KšžœM˜Qšžœž˜ Kšœ,žœ˜BKšœ žœ˜,—K˜—KšœD˜DK˜—šŸ œžœƒžœ!žœžœžœžœ˜ΤKšœ2™2K˜Kš œžœžœžœžœžœžœ˜žœž˜^šžœ0žœ˜8Kšœžœ#˜.Kšžœ˜—Kšœ žœ"˜1Kšžœ˜ ——šœ˜KšœY˜Yšžœ>žœž˜^šžœ0žœ˜9Kšœžœ#˜.Kšžœ˜—Kšœ žœ˜$Kšžœ˜ ——Kšžœ˜ —K˜—š Ÿœžœ`žœžœžœ˜ŸK™K˜šŸœžœžœžœ˜Zšœžœžœž˜Kšœ3˜3Kšœ3˜3Kšžœžœžœ ˜Kšžœžœžœžœ ˜"KšžœD˜H—K˜—šŸ œ$˜.šžœžœž˜šžœžœž˜9Kšžœ/žœžœ˜C—K˜——šŸœ$˜4šžœžœž˜šžœžœž˜>šžœ/žœžœ˜CK˜————Kšœ%žœ˜EKšœžœ˜7Kšœ>˜>KšœC˜CKšœžœ*˜CKšœ%˜%Kšœ˜Kšœ ˜ Kšœ!˜!Kšœ8˜8K˜Kšœ#™#Kšžœ<žœžœ˜UKšžœ=žœžœ˜VK˜K™Kšœi˜išžœžœžœ ž˜PKšœ"™"Kšœ>˜>KšœI˜IKšžœ˜—K™K™Kšœo˜ošžœžœžœ ž˜PKšœ>˜>Kšœ?˜?Kšœ9˜9Kšœ:˜:Kšœ4˜4Kšœžœ4˜IKšœžœ7˜OK˜Kšœ2™2šžœžœžœ ž˜LKšœ1˜1Kšœ/˜/Kšœ,˜,Kšœ,˜,Kšœ,˜,Kš žœžœ'žœžœžœžœ˜xKš žœ žœ*žœžœžœžœ˜xKšžœ˜—K˜Kšœ#™#KšœJ™JKšžœžœžœžœ˜:Kšžœ˜ —K˜—šŸ œžœ\žœ˜ŽK™$K˜Kšœ%žœ˜EKšœ>˜>Kšœžœ+˜HKšœ4žœžœ˜?Kšœžœ+˜IKšœ*žœžœ˜AKšœI˜IKšœK˜KKšžœ/žœžœ ˜HKšžœžœ˜K˜—šŸ œžœZžœ˜ŠK™&K˜Kšœ˜Kšœ4˜4Kšœ'žœ˜AKš œžœžœžœžœžœžœ˜LKšœ=˜=Kšžœžœžœžœžœžœžœžœžœ˜IK˜šžœžœžœ˜%Kšœ˜Kšœ~˜~Kšœ7˜7Kšžœžœ=˜Z—Kšžœ˜K˜KšœE˜EKšœ6˜6Kšœ/˜/Kšœ˜šžœ žœž˜Kšžœžœžœ+˜JKšžœ˜ —K˜—šŸœžœE˜Ršœ™Kšœ3™3Kšœ™Kšœ™Kšœ™K™—šŸœ$˜5Kšžœ!žœžœ˜EKšžœ"žœžœ˜GKšžœ$žœžœ˜KKšžœ%žœžœ˜MKšœ˜K˜—Kšœ%žœ˜EKšœ>˜>Kšœ'žœ˜AKšœ0˜0Kšœ3˜3Kšœ1˜1šžœ ž˜&Kšœ7˜7—KšœH˜HK˜šžœ žœž˜Kšœ2˜2šžœ žœžœ˜KšœW˜WKšœA˜AKšœ+žœ˜/Kšœ˜Kšœžœ_˜Kšœžœ_˜K˜šžœž˜˜ Kš œžœžœžœžœžœžœ˜LKšœ:˜:Kšœžœ˜4Kšœžœw˜Kšœžœ"˜>Kšœ=˜=K˜—˜ šœ"˜"Kšžœ žœ ˜/Kšžœžœ žœ ˜5KšžœA˜E—Kšœ#žœ ˜1Kšœžœ˜Kšœžœ˜Kšœ žœq˜Kšœžœ"˜>Kšœ]™]Kšœ žœžœžœ˜Qšžœ žœžœ˜Kšœ žœq˜Kšœžœ"˜>—šžœ˜Kšœ˜—Kšœ<˜˜>K˜šžœ žœž˜šžœžœž˜=Kšœ/˜/šœžœ žœ žœ˜[Kšžœ˜—Kšœ žœ˜*Kšžœ˜ ——K˜—šŸ œžœžœ ˜QK™K˜Kšœ?˜?Kšžœžœžœ˜K˜KšœC˜CKšžœžœžœ˜K˜KšœI˜IKšžœ˜K˜K˜—šŸ œžœ8žœ9˜‰Kšœ'™'K˜Kšœ%žœ˜EKšœ>˜>Kšœ˜Kšœ˜Kšœ˜K˜šžœžœž˜(Kšœ"˜"Kšžœ%žœ˜>Kšžœžœ%žœ˜BKšžœ ˜$Kšžœ˜ —K˜—šŸœžœžœžœžœžœžœžœ˜K™:Kšœ6™6K˜šŸ œžœ ˜0Kšžœžœžœ˜WKšžœžœžœžœ˜QKšžœžœžœžœ˜HK˜—šŸ œžœA˜Ršžœž˜šœžœž˜šžœ˜ Kšœ|™|KšœY˜YKšœ#˜#Kšœ!˜!—šžœ˜ Kšžœ1žœ˜OKšžœ˜—Kšžœ6˜=——Kšœ˜K˜—Kšœ6™6Kšœ'žœ˜+Kšœ;˜;Kšœ=˜=Kšœ˜Kšœ˜šžœ>žœžœž˜TKšœ˜Kšžœ˜K˜—Kšœ.™.Kšœ˜Kšœ!˜!K˜Kšœ0™0šžœ8žœžœž˜NKšœ‚™‚Kšœ`˜`Kšœ#˜#Kšœ ˜ Kšžœ˜—Kšœ˜K˜—šŸ œžœ<žœ"˜tK™2K˜Kšœ%žœ˜EKšœ>˜>KšœD˜DKšœA˜AKšœ#˜#Kšœ#˜#Kšœžœ ˜$Kšœžœ ˜$Kšœžœ žœžœ˜aKšœžœ žœžœ˜aK˜šžœžœž˜šœ žœ˜Kšœ žœ(˜8K˜—˜Kšœ ™ Kšœ ™ Kšœ1˜1Kšœ žœ:˜J—K˜šœžœžœžœ˜FKšœ™Kšœ™Kšœ2˜2Kšœ7˜7Kšœ7˜7Kšœ žœ˜-K˜—šœžœžœžœ˜EKšœ™Kšœ™Kšœ0˜0Kšœ/˜/Kšœ žœ*˜:K˜—šœžœžœžœ˜FKšœ™Kš  œ ™Kšœ0˜0Kšœ/˜/Kšœ žœ*˜:K˜—šœžœžœžœ˜FKš  œ™Kš  œ  ™Kšœ2˜2Kšœ7˜7Kšœ7˜7Kšœ žœ˜-K˜—˜Kš  œ™Kš  œ™&Kšœ1˜1Kšœ žœ:˜JK˜—Kšžœ=˜D—K˜—šŸ œž œžœ žœ ˜QK˜šžœ žœž˜Kšžœžœžœ˜:Kšžœ˜ K˜——šŸ œžœ"žœ žœ˜PKšœžœ˜ šžœžœž˜Kšœžœ˜K˜Kšžœ˜—Kšžœ˜ Kšœ ˜K˜—Kšœ˜—K˜K˜K˜—…—‘ζΓ-