<> <> <> <> <> DIRECTORY Basics, CD, CDSymbolicObjects, Convert, Rope, Route, RouteChannel, RouteDiGraph, RoutePrivate, RouteUtil, TerminalIO; RouteChannelTopolImpl: CEDAR PROGRAM IMPORTS CD, CDSymbolicObjects, Convert, Rope, Route, RouteChannel, RouteDiGraph, RoutePrivate, RouteUtil, TerminalIO EXPORTS RouteChannel SHARES Route = BEGIN <> ActiveTrackSpec: TYPE = REF ActiveTrackSpecRec; ActiveTrackSpecRec: TYPE = RECORD[ track: RouteChannel.ZMaxTracks _ 0, going: RouteChannel.GoingDirection _ leftToRight, freeArea: RouteChannel.AboveOrBelow _ below]; ActiveSegSpec: TYPE = REF ActiveSegSpecRec; ActiveSegSpecRec: TYPE = RECORD[ seg: RouteChannel.Segment _ NIL, segLayer: RoutePrivate.RoutingLayerOrNone _ trunk]; SegProc: TYPE = PROC[seg: RouteChannel.Segment, activeTrackSpec: ActiveTrackSpec] RETURNS [quit: BOOLEAN _ FALSE, segment: RouteChannel.Segment, segLayer: RoutePrivate.RoutingLayerOrNone]; debug: BOOLEAN _ FALSE; stopTrack: NAT _ 50; TopoWiring: PUBLIC PROCEDURE[routingArea: Route.RoutingArea, opt: Route.Optimization] RETURNS [bestResult: Route.RoutingResult] = { <> <<>> lastMethod: RouteChannel.Method _ NEW[RouteChannel.MethodRec]; bestMethod: RouteChannel.Method; result: Route.RoutingResult; parms: RoutePrivate.RoutingAreaParms _ NARROW[routingArea.parms]; <> maxL: NAT = LAST[NAT]; bestResult _ NEW[Route.RoutingResultRec _ [routingArea, maxL, maxL, maxL, maxL, maxL, maxL, maxL, Route.Rect[maxL, maxL, maxL, maxL]]]; <> FOR method: RouteChannel.Method _ GetNextMethod[lastMethod], GetNextMethod[lastMethod] WHILE method # NIL DO result _ RouteOneChan[routingArea, method]; lastMethod _ method; IF debug THEN RouteChannel.WriteResult[result, method]; IF RouteUtil.CompareResult[result, bestResult] = less THEN {bestResult _ result; bestMethod _ method}; IF opt = noIncompletes AND bestResult.numIncompletes = 0 THEN EXIT; ENDLOOP; <> IF bestMethod # lastMethod THEN bestResult _ RouteOneChan[routingArea, bestMethod]; RouteChannel.WriteResult[bestResult, bestMethod]}; GetNextMethod: PROCEDURE [currentMethod: RouteChannel.Method] RETURNS [nextMethod: RouteChannel.Method] = { SELECT currentMethod.directionSequence FROM start => nextMethod _ NEW[RouteChannel.MethodRec _ [outsideInTop, leftToRight]]; leftToRight => nextMethod _ NEW[RouteChannel.MethodRec _ [currentMethod.trackSequence, rightToLeft]]; rightToLeft => nextMethod _ NEW[RouteChannel.MethodRec _ [currentMethod.trackSequence, alternateLeft]]; alternateLeft => nextMethod _ NEW[RouteChannel.MethodRec _ [currentMethod.trackSequence, alternateRight]]; alternateRight => BEGIN nextMethod _ NEW[RouteChannel.MethodRec _ [currentMethod.trackSequence, leftToRight]]; SELECT currentMethod.trackSequence FROM start => nextMethod.trackSequence _ outsideInTop; outsideInTop => nextMethod.trackSequence _ outsideInBottom; outsideInBottom => nextMethod.trackSequence _ botToTop; botToTop => nextMethod.trackSequence _ topToBot; topToBot => nextMethod _ NIL; ENDCASE; END; ENDCASE; IF debug AND nextMethod # NIL THEN { TerminalIO.WriteRope[Rope.Cat["\nNew method: ", RouteChannel.directionSequenceName[nextMethod.directionSequence], ", ", RouteChannel.trackSequenceName[nextMethod.trackSequence]]]}; }; RouteOneChan: PROCEDURE[routingArea: Route.RoutingArea, method: RouteChannel.Method] RETURNS [result: Route.RoutingResult] = { <> InitOneChan[routingArea]; PreAssignSegs[routingArea, method]; AssignVariableSegs[routingArea, method]; result _ AnalyzeResult[routingArea]; }; -- RouteOneChan InitOneChan: PROCEDURE[routingArea: Route.RoutingArea] = { <> <> SetTrackPos: RouteChannel.EachTrackActionProc = { chanTracks.tracks[trackIndex].trackNum _ trackIndex; chanTracks.tracks[trackIndex].firstSeg _ NIL; chanTracks.tracks[trackIndex].keep _ FALSE; chanTracks.tracks[trackIndex].maxFeatureOnTrack _ 0}; ClearSegs: RouteChannel.EachPinActionProc = { IF pin # NIL THEN {FOR LRSide: RouteChannel.ChanLRSide IN RouteChannel.ChanLRSide DO seg: RouteChannel.Segment _ pin.conctSeg[LRSide]; IF seg # NIL THEN {seg.trackNum _ 0; seg.nextSeg _ NIL} ENDLOOP}}; chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins; chanTracks: RouteChannel.RoutingChannelTracks _ chanData.chanTracks; chanTracks.count _ chanTracks.maxCount; [] _ RouteChannel.EnumTracks[routingArea, SetTrackPos]; <> FOR posIndex: RouteChannel.MPinsOnCh IN [1 .. chanPins.count] DO pinPos: RouteChannel.PinPosition _ chanPins.sides[posIndex]; [] _ RouteChannel.EnumPins[routingArea, pinPos, ClearSegs] ENDLOOP}; -- InitOneChan PreAssignSegs: PROCEDURE[routingArea: Route.RoutingArea, method: RouteChannel.Method] = { <> PreSegProc: SegProc = { IF seg # NIL THEN IF seg.trackNum = 0 AND seg.trackConstraint # 0 AND ~seg.failed THEN { segment _ seg; segLayer _ CanConvert[routingArea, seg]; segSpec.seg _ segment; segSpec.segLayer _ segLayer; quit _ FitSegment[routingArea, segSpec, activeTrackSpec, FALSE]}; }; chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; parms: RoutePrivate.RoutingAreaParms _ NARROW[routingArea.parms]; segSpec: ActiveSegSpec _ NEW[ActiveSegSpecRec]; <> FOR activeTrackSpec: ActiveTrackSpec _ NextTrack[routingArea, NIL, method], NextTrack[routingArea, activeTrackSpec, method] WHILE activeTrackSpec # NIL DO <<>> <> FOR activeSegSpec: ActiveSegSpec _ GetNextSegment[routingArea, NIL, activeTrackSpec, PreSegProc], GetNextSegment[routingArea, activeSegSpec, activeTrackSpec, PreSegProc] WHILE activeSegSpec # NIL DO <> PlaceSegment[routingArea, activeSegSpec, activeTrackSpec]; ENDLOOP; -- FOR GetNextSegment ENDLOOP; -- FOR activeTrackSpec: }; -- PreAssignSegs AssignVariableSegs: PROCEDURE[routingArea: Route.RoutingArea, method: RouteChannel.Method] = { <> AsgnSegProc: SegProc = { IF seg # NIL THEN IF seg.trackNum = 0 AND ~seg.failed THEN { segment _ seg; segLayer _ CanConvert[routingArea, seg]; segSpec.seg _ seg; segSpec.segLayer _ segLayer; quit _ FitSegment[routingArea, segSpec, activeTrackSpec, TRUE]}; }; moreToDo: BOOLEAN _ TRUE; numTracksWOSegs: NAT _ 0; chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; parms: RoutePrivate.RoutingAreaParms _ NARROW[routingArea.parms]; segSpec: ActiveSegSpec _ NEW[ActiveSegSpecRec]; <> FOR activeTrackSpec: ActiveTrackSpec _ NextTrack[routingArea, NIL, method], NextTrack[routingArea, activeTrackSpec, method] WHILE moreToDo AND activeTrackSpec # NIL DO segOnThisTrack: BOOLEAN _ FALSE; <<>> <> FOR activeSegSpec: ActiveSegSpec _ GetNextSegment[routingArea, NIL, activeTrackSpec, AsgnSegProc], GetNextSegment[routingArea, activeSegSpec, activeTrackSpec, AsgnSegProc] WHILE activeSegSpec # NIL DO <> stillGoing: BOOLEAN _ TRUE; nextSegSpec: ActiveSegSpec; PlaceSegment[routingArea, activeSegSpec, activeTrackSpec]; segOnThisTrack _ TRUE; nextSegSpec _ FollowingSeg[routingArea, activeSegSpec, activeTrackSpec]; WHILE nextSegSpec # NIL AND stillGoing DO nextSegSpec.segLayer _ CanConvert[routingArea, nextSegSpec.seg]; IF FitSegment[routingArea, nextSegSpec, activeTrackSpec, TRUE] THEN {PlaceSegment[routingArea, nextSegSpec, activeTrackSpec]; nextSegSpec _ FollowingSeg[routingArea, nextSegSpec, activeTrackSpec]} ELSE stillGoing _ FALSE; ENDLOOP; -- WHILE nextSeg # NIL ENDLOOP; -- FOR GetNextSegment <> IF segOnThisTrack THEN {numTracksWOSegs _ 0; moreToDo _ TRUE} ELSE { numTracksWOSegs _ numTracksWOSegs+ 1; IF parms.routerUsed = channel AND numTracksWOSegs >= chanData.chanParms.emptyTrackLimit THEN moreToDo _ FALSE}; ENDLOOP; -- WHILE moreToDo }; -- AssignVariableSegs NextTrack: PROCEDURE[routingArea: Route.RoutingArea, activeTrackSpec: ActiveTrackSpec, method: RouteChannel.Method] RETURNS [nextTrackSpec: ActiveTrackSpec] = { <> OutsideInTopStop: PROCEDURE[track: RouteChannel.MaxTracks] RETURNS [BOOLEAN] = { IF chanTracks.count MOD 2 # 0 THEN RETURN[track = chanTracks.count/2 + 1] ELSE RETURN[track = chanTracks.count/2]}; OutsideInBottomStop: PROCEDURE[track: RouteChannel.MaxTracks] RETURNS [BOOLEAN] = { RETURN[track = chanTracks.count/2 + 1]}; trialTrack: RouteChannel.ZMaxTracks; freeArea: RouteChannel.AboveOrBelow; going: RouteChannel.GoingDirection; chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; chanTracks: RouteChannel.RoutingChannelTracks _ chanData.chanTracks; IF activeTrackSpec = NIL THEN { SELECT method.trackSequence FROM outsideInTop => {trialTrack _ chanTracks.count; freeArea _ below}; outsideInBottom => {trialTrack _ 1; freeArea _ above}; botToTop => {trialTrack _ 1; freeArea _ above}; topToBot => {trialTrack _ chanTracks.count; freeArea _ below}; ENDCASE => Route.Error[programmingError, "Pack direction error"]; SELECT method.directionSequence FROM leftToRight, alternateLeft => going _ leftToRight; rightToLeft, alternateRight => going _ rightToLeft; ENDCASE => Route.Error[programmingError, "Pack direction error"]} ELSE { -- keep going IF ~(activeTrackSpec.track IN RouteChannel.MaxTracks) THEN Route.Error[programmingError, "Invalid track state"]; SELECT method.trackSequence FROM outsideInTop => IF OutsideInTopStop[activeTrackSpec.track] THEN trialTrack _ 0 ELSE IF activeTrackSpec.track > chanTracks.count/2 THEN {trialTrack _ chanTracks.count - activeTrackSpec.track + 1; freeArea _ above} ELSE {trialTrack _ chanTracks.count - activeTrackSpec.track; freeArea _ below}; outsideInBottom => IF OutsideInBottomStop[activeTrackSpec.track] THEN trialTrack _ 0 ELSE IF activeTrackSpec.track <= chanTracks.count/2 THEN {trialTrack _ chanTracks.count - activeTrackSpec.track + 1; freeArea _ below} ELSE {trialTrack _ chanTracks.count - activeTrackSpec.track + 2; freeArea _ above}; botToTop => IF activeTrackSpec.track >= chanTracks.count THEN trialTrack _ 0 ELSE {trialTrack _ activeTrackSpec.track + 1; freeArea _ above}; topToBot => IF activeTrackSpec.track <= 1 THEN trialTrack _ 0 ELSE {trialTrack _ activeTrackSpec.track - 1; freeArea _ below}; ENDCASE => Route.Error[programmingError, "Pack direction error"]; SELECT method.directionSequence FROM leftToRight => going _ leftToRight; rightToLeft => going _ rightToLeft; alternateLeft => IF activeTrackSpec.going = leftToRight THEN going _ rightToLeft ELSE going _ leftToRight; alternateRight => IF activeTrackSpec.going = rightToLeft THEN going _ leftToRight ELSE going _ rightToLeft; ENDCASE => Route.Error[programmingError, "Pack direction error"]}; <> IF ~(trialTrack IN [1 .. chanTracks.count]) THEN nextTrackSpec _ NIL ELSE {nextTrackSpec _ NEW[ActiveTrackSpecRec _ [trialTrack, going, freeArea]]; IF debug THEN {TerminalIO.WriteRope[Rope.Cat["\n New track: ", Convert.RopeFromInt[trialTrack]]]; TerminalIO.WriteRope[Rope.Cat["\n going: ", RouteChannel.GoingName[going], ", free area: ", RouteChannel.AboveOrBelowName[freeArea]]]}}; }; -- NextTrack <> PlaceSegment: PROCEDURE[routingArea: Route.RoutingArea, activeSegSpec: ActiveSegSpec, activeTrackSpec: ActiveTrackSpec] = { chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; chanTracks: RouteChannel.RoutingChannelTracks _ chanData.chanTracks; track: RouteChannel.ZMaxTracks _ activeTrackSpec.track; trackLoc: Route.Number _ RouteChannel.TrackLoc[routingArea, track]; mustKeep: RouteChannel.ZMaxTracks _ RouteChannel.InfluenceTracks[routingArea, activeSegSpec.seg.net.trunkWidth]; lowerTrack: RouteChannel.ZMaxTracks _ MAX[track - mustKeep, 1]; upperTrack: RouteChannel.ZMaxTracks _ MIN[track + mustKeep, chanTracks.count]; firstSeg: RouteChannel.Segment _ RouteChannel.TrackSeg[routingArea, track]; featureSize: Route.Number _ MAX[routingArea.rules.contactSize, activeSegSpec.seg.net.trunkWidth]; distance: Route.Number _ (featureSize + routingArea.rules.trunkSpacing + routingArea.rules.trunkToTrunk)/2; <> IF activeSegSpec.seg.trackNum # 0 THEN Route.Error[programmingError, "Track state error"] ELSE activeSegSpec.seg.trackNum _ track; activeSegSpec.seg.routingLayer _ activeSegSpec.segLayer; FOR keepTrack: RouteChannel.ZMaxTracks IN [lowerTrack .. upperTrack] DO IF ABS[trackLoc - RouteChannel.TrackLoc[routingArea, keepTrack]] < distance THEN chanTracks.tracks[keepTrack].keep _ TRUE ENDLOOP; chanTracks.tracks[track].maxFeatureOnTrack _ MAX[chanTracks.tracks[track].maxFeatureOnTrack, featureSize]; <> IF firstSeg = NIL THEN { <> activeSegSpec.seg.nextSeg _ NIL; chanTracks.tracks[track].firstSeg _ activeSegSpec.seg} ELSE IF activeSegSpec.seg.exteriorPins[chanRight].pinPosition.pLoc <= firstSeg.exteriorPins[chanLeft].pinPosition.pLoc THEN { <> activeSegSpec.seg.nextSeg _ firstSeg; chanTracks.tracks[track].firstSeg _ activeSegSpec.seg} ELSE { nextSeg: RouteChannel.Segment; lastSeg: RouteChannel.Segment _ firstSeg; FOR nextSeg _ lastSeg.nextSeg, lastSeg.nextSeg WHILE nextSeg # NIL DO IF lastSeg.exteriorPins[chanRight].pinPosition.pLoc <= activeSegSpec.seg.exteriorPins[chanLeft].pinPosition.pLoc THEN EXIT; lastSeg _ nextSeg; ENDLOOP; lastSeg.nextSeg _ activeSegSpec.seg; activeSegSpec.seg.nextSeg _ nextSeg}}; -- PlaceSegment <<>> FitSegment: PROCEDURE[routingArea: Route.RoutingArea, nextSegSpec: ActiveSegSpec, activeTrackSpec: ActiveTrackSpec, useConstraints: BOOLEAN] RETURNS [fitsSoFar: BOOLEAN _ FALSE] = { <> chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; trackNum: RouteChannel.MaxTracks _ activeTrackSpec.track; blocked: BOOLEAN _ chanData.chanTracks.tracks[trackNum].blocked; trackConstraint: RouteChannel.ZMaxTracks _ nextSegSpec.seg.trackConstraint; IF (trackConstraint # 0 AND trackConstraint # activeTrackSpec.track) OR blocked THEN RETURN[fitsSoFar]; <<>> <> fitsSoFar _ FitSegmentThisTrack[routingArea, nextSegSpec, activeTrackSpec]; <<>> <> IF fitsSoFar THEN fitsSoFar _ FitSegmentAdjTracks[routingArea, nextSegSpec, activeTrackSpec, chanData.chanTracks.count]; <<>> <> IF fitsSoFar AND useConstraints THEN fitsSoFar _ FitSegmentConstraints[routingArea, nextSegSpec, activeTrackSpec]; RETURN[fitsSoFar]}; -- FitSegment FitSegmentThisTrack: PROCEDURE[routingArea: Route.RoutingArea, nextSegSpec: ActiveSegSpec, activeTrackSpec: ActiveTrackSpec] RETURNS [fitsSoFar: BOOLEAN _ TRUE] = { <> chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; rules: Route.DesignRules _ routingArea.rules; trialSeg: RouteChannel.Segment _ nextSegSpec.seg; trackNum: RouteChannel.MaxTracks _ activeTrackSpec.track; segLayer: RoutePrivate.RoutingLayerOrNone _ nextSegSpec.segLayer; <> FOR existingSeg: RouteChannel.Segment _ RouteChannel.TrackSeg[routingArea, trackNum], existingSeg.nextSeg WHILE existingSeg # NIL AND fitsSoFar DO IF existingSeg.net.netNum # trialSeg.net.netNum OR existingSeg.net.netPart # trialSeg.net.netPart THEN { SELECT TRUE FROM segLayer = trunk AND existingSeg.routingLayer = trunk => fitsSoFar _ ~OverlapCheck[routingArea, existingSeg, trialSeg, rules.branchSpacing]; segLayer = trunk AND existingSeg.routingLayer = branch => fitsSoFar _ ~EndOverlapCheck[routingArea, existingSeg, trialSeg, rules.branchSpacing]; segLayer = branch AND existingSeg.routingLayer = trunk => fitsSoFar _ ~EndOverlapCheck[routingArea, trialSeg, existingSeg, rules.branchSpacing]; segLayer = branch AND existingSeg.routingLayer = branch => fitsSoFar _ ~OverlapCheck[routingArea, existingSeg, trialSeg, rules.branchSpacing]; ENDCASE}; ENDLOOP}; -- FitSegmentThisTrack FitSegmentAdjTracks: PROCEDURE[routingArea: Route.RoutingArea, nextSegSpec: ActiveSegSpec, activeTrackSpec: ActiveTrackSpec, maxTrack: RouteChannel.ZMaxTracks] RETURNS [fitsSoFar: BOOLEAN _ TRUE] = { <> chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; chanTracks: RouteChannel.RoutingChannelTracks _ chanData.chanTracks; firstPass: BOOLEAN _ TRUE; rules: Route.DesignRules _ routingArea.rules; trialSeg: RouteChannel.Segment _ nextSegSpec.seg; trackNum: RouteChannel.MaxTracks _ activeTrackSpec.track; trialPos: Route.Number _ RouteChannel.TrackLoc[routingArea, trackNum]; maxPos: Route.Number _ RouteChannel.TrackLoc[routingArea, maxTrack] + rules.trunkToEdge - rules.trunkSpacing; minPos: Route.Number _ RouteChannel.TrackLoc[routingArea, 1] - rules.trunkToEdge + rules.trunkSpacing; parms: RoutePrivate.RoutingAreaParms _ NARROW[routingArea.parms]; influence: Route.Number _ RouteChannel.InfluenceTracks[routingArea, parms.widestTrunk/2] + RouteChannel.InfluenceTracks[routingArea, trialSeg.net.trunkWidth/2]; lowerTrack: RouteChannel.MaxTracks _ MAX[trackNum - influence, 1]; upperTrack: RouteChannel.MaxTracks _ MIN[trackNum + influence, chanTracks.count]; <<>> <> IF maxPos < trialPos + trialSeg.qWidth/2 OR trialPos - trialSeg.qWidth/2 < minPos THEN fitsSoFar _ FALSE; <> FOR adjTrack: RouteChannel.MaxTracks IN [lowerTrack .. upperTrack] WHILE fitsSoFar DO IF adjTrack # activeTrackSpec.track THEN { adjTrackPos: Route.Number _ RouteChannel.TrackLoc[routingArea, adjTrack]; distance: Route.Number _ ABS[adjTrackPos - trialPos] - chanTracks.tracks[adjTrack].maxFeatureOnTrack/2 - trialSeg.net.trunkWidth/2; pinsOnTrialSeg: RouteChannel.ChanPinList; IF distance < rules.trunkSpacing THEN { <> IF firstPass THEN { -- don't get pinsOnTrialSeg until needed firstPass _ FALSE; pinsOnTrialSeg _ RouteChannel.GetPinsOnSeg[trialSeg]}; FOR existingSeg: RouteChannel.Segment _ RouteChannel.TrackSeg[routingArea, adjTrack], existingSeg.nextSeg WHILE existingSeg # NIL AND fitsSoFar DO contactToContact: Route.Number _ rules.contactToContact; segLayer: RoutePrivate.RoutingLayerOrNone _ nextSegSpec.segLayer; IF existingSeg.net.netNum # trialSeg.net.netNum OR existingSeg.net.netPart # trialSeg.net.netPart THEN { -- check to see if wires interfere with each other IF ABS[trialPos - adjTrackPos] < trialSeg.qWidth/2 + rules.trunkSpacing + existingSeg.qWidth/2 THEN fitsSoFar _ ~OverlapCheck[routingArea, existingSeg, trialSeg, rules.branchSpacing]}; <> IF contactToContact > rules.trunkToTrunk THEN { IF segLayer = trunk AND existingSeg.routingLayer = trunk THEN { pinsOnExistSeg: RouteChannel.ChanPinList _ RouteChannel.GetPinsOnSeg[existingSeg]; FOR trialPins: RouteChannel.ChanPinList _ pinsOnTrialSeg, trialPins.rest WHILE trialPins # NIL AND fitsSoFar DO trialPin: RouteChannel.ChanPin _ trialPins.first; FOR existPins: RouteChannel.ChanPinList _ pinsOnExistSeg, existPins.rest WHILE existPins # NIL AND fitsSoFar DO existPin: RouteChannel.ChanPin _ existPins.first; fitsSoFar _ ~ContactCheck[routingArea, trialPin, trialPos, existPin, adjTrackPos, rules.branchSpacing]; ENDLOOP; ENDLOOP}}; ENDLOOP}}; ENDLOOP}; -- FitSegmentAdjTracks FitSegmentConstraints: PROCEDURE[routingArea: Route.RoutingArea, nextSegSpec: ActiveSegSpec, activeTrackSpec: ActiveTrackSpec] RETURNS [fitsSoFar: BOOLEAN _ TRUE] = { <> <> chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; graph: RouteDiGraph.Graph _ chanData.constraints; trialSeg: RouteChannel.Segment _ nextSegSpec.seg; <<>> <> IF activeTrackSpec.freeArea = above THEN { <> IF fitsSoFar THEN fitsSoFar _ ~ConstraintCheck[graph, trialSeg, below, activeTrackSpec.track, TRUE]; <<>> <> IF fitsSoFar THEN fitsSoFar _ ~ConstraintCheck[graph, trialSeg, above, activeTrackSpec.track, FALSE]}; <> IF activeTrackSpec.freeArea = below THEN { <> IF fitsSoFar THEN fitsSoFar _ ~ConstraintCheck[graph, trialSeg, above, activeTrackSpec.track, TRUE]; <<>> <> IF fitsSoFar THEN fitsSoFar _ ~ConstraintCheck[graph, trialSeg, below, activeTrackSpec.track, FALSE]}; RETURN[fitsSoFar]}; -- FitSegmentConstraints EndOverlapCheck: PROCEDURE[routingArea: Route.RoutingArea, branchSeg, trunkSeg: RouteChannel.Segment, dist: Route.Number] RETURNS [overlap: BOOLEAN] = { EachPin: RouteChannel.EachPinActionProc ~ { leftTrunkPinLoc: Route.Number _ pin.pinPosition.pLoc - RouteUtil.GetWidthWithContact[routingArea, pin.pWidth]/2; rightTrunkPinLoc: Route.Number _ pin.pinPosition.pLoc + RouteUtil.GetWidthWithContact[routingArea, pin.pWidth]/2; gap: RoutePrivate.Range _ RouteChannel.Gap[[leftBranchLoc, rightBranchLoc], [leftTrunkPinLoc, rightTrunkPinLoc]]; IF gap.l > gap.r THEN overlap _ TRUE ELSE overlap _ gap.r - gap.l < dist }; leftBranchPin: RouteChannel.ChanPin _ branchSeg.exteriorPins[chanLeft]; leftBranchLoc: Route.Number _ leftBranchPin.pinPosition.pLoc - RouteUtil.GetWidthWithContact[routingArea, leftBranchPin.pWidth]/2; rightBranchPin: RouteChannel.ChanPin _ branchSeg.exteriorPins[chanRight]; rightBranchLoc: Route.Number _ rightBranchPin.pinPosition.pLoc + RouteUtil.GetWidthWithContact[routingArea, rightBranchPin.pWidth]/2; overlap _ RouteChannel.EnumPinsOnSeg[routingArea, trunkSeg, EachPin]}; HalfOverlapCheck: PROCEDURE[routingArea: Route.RoutingArea, seg1, seg2: RouteChannel.Segment, dist: Route.Number] RETURNS [overlap: BOOLEAN] = { leftPin1: RouteChannel.ChanPin _ seg1.exteriorPins[chanLeft]; left1Loc: Route.Number _ leftPin1.pinPosition.pLoc - RouteUtil.GetWidthWithContact[routingArea, leftPin1.pWidth]/2; rightPin1: RouteChannel.ChanPin _ seg1.exteriorPins[chanRight]; right1Loc: Route.Number _ rightPin1.pinPosition.pLoc + RouteUtil.GetWidthWithContact[routingArea, rightPin1.pWidth]/2; leftPin2: RouteChannel.ChanPin _ seg2.exteriorPins[chanLeft]; left2Loc: Route.Number _ leftPin2.pinPosition.pLoc - RouteUtil.GetWidthWithContact[routingArea, leftPin2.pWidth]/2; rightPin2: RouteChannel.ChanPin _ seg2.exteriorPins[chanRight]; right2Loc: Route.Number _ rightPin2.pinPosition.pLoc + RouteUtil.GetWidthWithContact[routingArea, rightPin2.pWidth]/2; gap: RoutePrivate.Range _ RouteChannel.Gap[[left1Loc, right1Loc], [left2Loc, right2Loc]]; IF gap.l > gap.r THEN overlap _ TRUE ELSE overlap _ gap.r - gap.l < dist}; OverlapCheck: PROCEDURE[routingArea: Route.RoutingArea, seg1, seg2: RouteChannel.Segment, dist: Route.Number] RETURNS [overlap: BOOLEAN] = { overlap _ HalfOverlapCheck[routingArea, seg1, seg2, dist] OR HalfOverlapCheck[routingArea, seg2, seg1, dist]}; ContactCheck: PROCEDURE[routingArea: Route.RoutingArea, pin1: RouteChannel.ChanPin, qPos1: Route.Number, pin2: RouteChannel.ChanPin, qPos2, dist: Route.Number] RETURNS [overlap: BOOLEAN _ FALSE] = BEGIN IF ABS[qPos1 - qPos2] < dist THEN { left1Loc: Route.Number _ pin1.pinPosition.pLoc - RouteUtil.GetWidthWithContact[routingArea, pin1.pWidth]/2; right1Loc: Route.Number _ pin1.pinPosition.pLoc + RouteUtil.GetWidthWithContact[routingArea, pin1.pWidth]/2; left2Loc: Route.Number _ pin2.pinPosition.pLoc - RouteUtil.GetWidthWithContact[routingArea, pin2.pWidth]/2; right2Loc: Route.Number _ pin2.pinPosition.pLoc + RouteUtil.GetWidthWithContact[routingArea, pin2.pWidth]/2; gap: RoutePrivate.Range _ RouteChannel.Gap[[left1Loc, right1Loc], [left2Loc, right2Loc]]; IF gap.l > gap.r THEN overlap _ TRUE ELSE overlap _ gap.r - gap.l < dist}; END; -- ContactCheck ConstraintCheck: PROCEDURE[graph: RouteDiGraph.Graph, segment: RouteChannel.Segment, direction: RouteChannel.AboveOrBelow, track: RouteChannel.MaxTracks, mustBePlaced: BOOLEAN] RETURNS [constrained: BOOLEAN _ FALSE] = { <> CheckConstraints: RouteDiGraph.EnumArcsFromNodeProc = { nextNode: RouteDiGraph.Node _ IF direction = in THEN arc.inferiorNode ELSE arc.superiorNode; nodeInfo: RouteChannel.SegmentConstraint _ NARROW[nextNode.nodeInfo]; segment: RouteChannel.Segment _ nodeInfo.segment; IF segment.trackNum = 0 THEN { IF mustBePlaced THEN quit _ TRUE} -- segment must be placed ELSE { IF direction = out THEN quit _ track >= segment.trackNum ELSE quit _ track <= segment.trackNum}; IF ~quit THEN quit _ RouteDiGraph.EnumArcsFromNode[graph, nextNode, direction, CheckConstraints]}; node: RouteDiGraph.Node _ segment.constraintNode; gDirection: RouteDiGraph.Direction _ IF direction = above THEN out ELSE in; constrained _ RouteDiGraph.EnumArcsFromNode[graph, node, gDirection, CheckConstraints]; }; GetNextSegment: PROCEDURE[routingArea: Route.RoutingArea, activeSegSpec: ActiveSegSpec, activeTrackSpec: ActiveTrackSpec, segProc: SegProc] RETURNS [nextSegSpec: ActiveSegSpec _ NIL] = { <> CheckSegs: RouteChannel.EachPinActionProc = { IF pin # NIL THEN { [quit, seg, segLayer] _ segProc[pin.conctSeg[whichSide], activeTrackSpec]; IF ~quit THEN [quit, seg, segLayer] _ segProc[pin.altConctSeg[whichSide], activeTrackSpec]}}; found: BOOLEAN _ FALSE; whichSide: RouteChannel.ChanLRSide; pinPos: RouteChannel.ZMPinsOnCh; chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; lastIndex: RouteChannel.ZMPinsOnCh _ chanData.chanPins.count; seg: RouteChannel.Segment; segLayer: RoutePrivate.RoutingLayerOrNone; <> SELECT activeTrackSpec.going FROM leftToRight => { IF activeSegSpec = NIL THEN pinPos _ 1 ELSE pinPos _ activeSegSpec.seg.exteriorPins[chanLeft].pinPosition.pinIndex; whichSide _ chanRight; FOR posIndex: RouteChannel.MPinsOnCh IN [pinPos .. lastIndex] WHILE ~ found DO pinPosition: RouteChannel.PinPosition _ chanData.chanPins.sides[posIndex]; found _ RouteChannel.EnumPins[routingArea, pinPosition, CheckSegs] ENDLOOP}; -- posIndex rightToLeft => { IF activeSegSpec = NIL THEN pinPos _ lastIndex ELSE pinPos _ activeSegSpec.seg.exteriorPins[chanRight].pinPosition.pinIndex; whichSide _ chanLeft; FOR posIndex: RouteChannel.MPinsOnCh DECREASING IN [1 .. pinPos] WHILE ~ found DO pinPosition: RouteChannel.PinPosition _ chanData.chanPins.sides[posIndex]; found _ RouteChannel.EnumPins[routingArea, pinPosition, CheckSegs] ENDLOOP}; -- posIndex ENDCASE; IF found THEN { <> nextSegSpec _ IF activeSegSpec = NIL THEN NEW[ActiveSegSpecRec] ELSE activeSegSpec; nextSegSpec.seg _ seg; nextSegSpec.segLayer _ segLayer}; IF debug AND nextSegSpec # NIL THEN IF nextSegSpec.seg # NIL THEN {TerminalIO.WriteRope[Rope.Cat["\n New segment: ", nextSegSpec.seg.net.name, ", ", RoutePrivate.RoutingLayerName[nextSegSpec.segLayer]]]}; }; -- GetNextSegment FollowingSeg: PROCEDURE [routingArea: Route.RoutingArea, activeSegSpec: ActiveSegSpec, activeTrackSpec: ActiveTrackSpec] RETURNS [nextSegSpec: ActiveSegSpec _ NIL] = { <> <> CheckFitSegs: RouteChannel.EachPinActionProc = { IF pin # NIL THEN {seg: RouteChannel.Segment _ pin.conctSeg[existingSide]; IF seg # NIL THEN IF seg = activeSegSpec.seg THEN {trialSegSpec: ActiveSegSpec _ NEW[ActiveSegSpecRec _ [seg: pin.conctSeg[newSide]]]; IF trialSegSpec.seg # NIL THEN IF trialSegSpec.seg.trackNum = 0 THEN nextSegSpec _ trialSegSpec; quit _ TRUE}}}; existingSide, newSide: RouteChannel.ChanLRSide; pinPos: RouteChannel.PinPosition; found: BOOLEAN _ FALSE; SELECT activeTrackSpec.going FROM leftToRight => {pinPos _ activeSegSpec.seg.exteriorPins[chanRight].pinPosition; existingSide _ chanLeft; newSide _ chanRight}; rightToLeft => {pinPos _ activeSegSpec.seg.exteriorPins[chanLeft].pinPosition; existingSide _ chanRight; newSide _ chanLeft}; ENDCASE; <> found _ RouteChannel.EnumPins[routingArea, pinPos, CheckFitSegs] }; -- FollowingSeg AnalyzeResult: PROCEDURE[routingArea: Route.RoutingArea] RETURNS [result: Route.RoutingResult] = { RemoveTrackIfPossible: PROCEDURE[routingArea: Route.RoutingArea, track, oldNumTracks: RouteChannel.MaxTracks] RETURNS [numTracks: RouteChannel.ZMaxTracks] = { <> chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; chanTracks: RouteChannel.RoutingChannelTracks _ chanData.chanTracks; IF track = stopTrack THEN track _ stopTrack; IF ~chanTracks.tracks[track].blocked AND ~chanTracks.tracks[track].keep THEN numTracks _ RemoveTrack[routingArea, track, oldNumTracks] -- assume track can be removed ELSE numTracks _ oldNumTracks}; EnumExits: RouteChannel.EnumExitsProc = { <> IF constructedExit THEN IF ~RouteChannel.MembRopeList[name, breakAtExitList] THEN breakAtExitList _ CONS[name, breakAtExitList]}; EnumSegments: RouteChannel.EnumSegmentsProc = { length: Route.Number _ RouteUtil.Length[pos1, pos2]; SELECT TRUE FROM layer = metalLayer => metal1length _ metal1length + length; layer = metal2Layer => metal2length _ metal2length + length; layer = polyLayer => polyLength _ polyLength + length; ENDCASE => otherLength _ otherLength + length}; EnumPins: RouteChannel.EnumPinsProc = { <> pinLayer: Route.Layer _ CDSymbolicObjects.GetLayer[pin.pin]; IF layer = polyLayer AND pinLayer = metalLayer OR layer = metalLayer AND pinLayer = polyLayer THEN polyToMetal _ polyToMetal +1 ELSE IF layer = metalLayer AND pinLayer = metal2Layer OR layer = metal2Layer AND pinLayer = metalLayer THEN metalToMetal2 _ metalToMetal2 +1}; EnumVias: RouteChannel.EnumViasProc = { <> IF layer1 = polyLayer AND layer2 = metalLayer OR layer1 = metalLayer AND layer2 = polyLayer THEN polyToMetal _ polyToMetal +1 ELSE IF layer1 = metalLayer AND layer2 = metal2Layer OR layer1 = metal2Layer AND layer2 = metalLayer THEN metalToMetal2 _ metalToMetal2 +1}; EnumIncompletes: RouteChannel.EnumIncompletesProc = { <> numIncompletes _ numIncompletes +1; IF ~RouteChannel.MembRopeList[name, incompleteList] THEN incompleteList _ CONS[name, incompleteList]}; ElimUselessTracks: RouteChannel.EachTrackActionProc = { <<>> <> IF RouteChannel.TrackSeg[routingArea, trackIndex] = NIL THEN -- this track has no segments numTracks _ RemoveTrackIfPossible[routingArea, trackIndex, numTracks]}; <> chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; chanTracks: RouteChannel.RoutingChannelTracks _ chanData.chanTracks; parms: RoutePrivate.RoutingAreaParms _ NARROW[routingArea.parms]; metal1length, metal2length, polyLength, otherLength: Route.Number _ 0; polyToMetal, metalToMetal2, numIncompletes: NAT _ 0; technology: CD.Technology _ NARROW[routingArea.rules.technology]; metalLayer: Route.Layer _ CD.FetchLayer[technology, $met]; metal2Layer: Route.Layer _ CD.FetchLayer[technology, $met2]; polyLayer: Route.Layer _ CD.FetchLayer[technology, $pol]; rect: Route.Rect; loc1, loc2: Route.Position; incompleteList: LIST OF Rope.ROPE _ NIL; breakAtExitList: LIST OF Rope.ROPE _ NIL; numTracks: RouteChannel.ZMaxTracks _ chanTracks.count; lowerTrackSpec: ActiveTrackSpec _ NEW[ActiveTrackSpecRec]; upperTrackSpec: ActiveTrackSpec _ NEW[ActiveTrackSpecRec]; segSpec: ActiveSegSpec _ NEW[ActiveSegSpecRec]; <<>> <> <> <> IF parms.routerUsed = channel THEN { [] _ RouteChannel.EnumTracks[routingArea, ElimUselessTracks]; chanTracks.count _ numTracks}; loc1 _ RouteUtil.PQToXY[routingArea, [chanData.chanPins.cEnd1, chanData.chanSides[chanBottom].routeAreaCoord]]; IF parms.routerUsed = channel THEN { thisChanWidth: Route.Number _ RouteChannel.ChannelWidth[routingArea]; loc2 _ RouteUtil.PQToXY[routingArea, [chanData.chanPins.cEnd2, chanData.chanSides[chanBottom].routeAreaCoord + thisChanWidth]]} ELSE IF parms.routerUsed = switchBox THEN loc2 _ RouteUtil.PQToXY[routingArea, [chanData.chanPins.cEnd2, chanData.chanSides[chanTop].routeAreaCoord]]; rect _ [loc1.x, loc1.y, loc2.x, loc2.y]; [] _ RouteChannel.GetRouting[routingArea, rect, NIL, EnumSegments, EnumPins, EnumVias, EnumExits, EnumIncompletes]; result _ NEW[Route.RoutingResultRec _ [routingArea, polyLength, metal1length, metal2length, polyToMetal, metalToMetal2, chanTracks.count, numIncompletes, rect, FALSE, incompleteList, breakAtExitList]]; }; -- AnalyzeResult CanConvert: PROCEDURE[routingArea: Route.RoutingArea, seg: RouteChannel.Segment] RETURNS [segLayer: RoutePrivate.RoutingLayerOrNone _ trunk] = { -- see if this trunk routingLayer seg can be pulled down onto the branch routingLayer chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; leftPin: RouteChannel.ChanPin _ seg.exteriorPins[chanLeft]; rightPin: RouteChannel.ChanPin _ seg.exteriorPins[chanRight]; leftPinPosition: RouteChannel.PinPosition _ leftPin.pinPosition; rightPinPosition: RouteChannel.PinPosition _ rightPin.pinPosition; segLength: Route.Number _ rightPinPosition.pLoc - leftPinPosition.pLoc; IF leftPin.kindOfPin = exitPin OR rightPin.kindOfPin = exitPin THEN RETURN; IF segLength <= chanData.chanParms.maxToConvert AND ABS[leftPinPosition.pinIndex - rightPinPosition.pinIndex] <= 1 THEN segLayer _ branch}; RemoveTrack: PROCEDURE [routingArea: Route.RoutingArea, track, oldNumTracks: RouteChannel.ZMaxTracks] RETURNS [numTracks: RouteChannel.ZMaxTracks] = { <> chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; chanTracks: RouteChannel.RoutingChannelTracks _ chanData.chanTracks; trackNum, oldTrackNum: RouteChannel.MaxTracks; FOR upperTrack: RouteChannel.MaxTracks DECREASING IN [track+1 .. chanTracks.count] DO chanTracks.tracks[upperTrack].oldTrackNum _ chanTracks.tracks[upperTrack].trackNum; chanTracks.tracks[upperTrack].trackNum _ chanTracks.tracks[upperTrack-1].trackNum; ENDLOOP; IF track # 1 THEN chanTracks.tracks[track].trackNum _ chanTracks.tracks[track-1].trackNum; FOR upperTrack: RouteChannel.MaxTracks IN [track+1 .. chanTracks.count] DO trackNum _ chanTracks.tracks[upperTrack].trackNum; oldTrackNum _ chanTracks.tracks[upperTrack].oldTrackNum; chanTracks.tracks[trackNum].firstSeg _ chanTracks.tracks[oldTrackNum].firstSeg; ENDLOOP; IF track # chanTracks.count THEN { oldTrackNum _ chanTracks.tracks[chanTracks.count].oldTrackNum; chanTracks.tracks[oldTrackNum].firstSeg _ NIL}; numTracks _ oldNumTracks - 1}; END.