<> <> <> <> <> <<>> DIRECTORY CD USING [Layer, Number], DABasics USING [Number, Position, Rect], List USING [Memb], Rope USING [ROPE], Route USING [DesignRules, ErrorType, ResultData, ResultDataRec], RouteChannel USING [AboveOrBelow, ChanLRSide, ChannelData, ChannelWidth, ChanPin, ChanPinList, EachPinActionProc, EachTrackActionProc, EnumIncompletesProc, EnumPins, EnumPinsOnSeg, EnumSegmentsProc, EnumTracks, EnumViasProc, GetPinsOnSeg, GetRouting, GoingDirection, InfluenceTracks, MaxTracks, MembRopeList, Method, MPinsOnCh, PinPosition, RoutingChannelPins, RoutingChannelTracks, Segment, SegmentConstraint, TrackLoc, TrackSeg, ZMaxTracks, ZMPinsOnCh], RouteChannelTopol USING [], RouteDiGraph USING [Direction, EnumArcsFromNode, EnumArcsFromNodeProc, Graph, Node], RoutePrivate USING [RoutingAreaParms, RoutingLayerOrNone], RouteUtil USING [GetWidthWithContact, Length, PQToXY], RTBasic USING [Range]; RouteChannelTopolImpl: CEDAR PROGRAM IMPORTS List, RouteChannel, RouteDiGraph, RouteUtil EXPORTS RouteChannelTopol = { <> 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; RouteOneChan: PUBLIC PROC [chanData: RouteChannel.ChannelData, parms: RoutePrivate.RoutingAreaParms, rules: Route.DesignRules, method: RouteChannel.Method, numSegmentsMustPlace: INT] RETURNS [result: Route.ResultData] = { <> InitOneChan[chanData]; PreAssignSegs[chanData, parms, rules, method]; HackedAssignVariableSegs[chanData, parms, rules, method, numSegmentsMustPlace]; result _ AnalyzeResult[chanData, parms, rules]; }; -- RouteOneChan InitOneChan: PROC [chanData: RouteChannel.ChannelData] = { <> <> 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; }; chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins; chanTracks: RouteChannel.RoutingChannelTracks _ chanData.chanTracks; chanTracks.count _ chanTracks.maxCount; [] _ RouteChannel.EnumTracks[chanTracks, SetTrackPos]; <> FOR posIndex: RouteChannel.MPinsOnCh IN [1 .. chanPins.count] DO pinPos: RouteChannel.PinPosition _ chanPins.sides[posIndex]; [] _ RouteChannel.EnumPins[pinPos, ClearSegs] ENDLOOP; }; -- InitOneChan PreAssignSegs: PROC [chanData: RouteChannel.ChannelData, parms: RoutePrivate.RoutingAreaParms, rules: Route.DesignRules, method: RouteChannel.Method] = { <> PreSegProc: SegProc = { <> <> IF seg # NIL THEN { <> noAdjacentSegs: BOOLEAN _ seg.exteriorPins[chanLeft].conctSeg[chanLeft] = NIL AND seg.exteriorPins[chanRight].conctSeg[chanRight] = NIL AND seg.exteriorPins[chanLeft].altConctSeg[chanLeft] = NIL AND seg.exteriorPins[chanRight].altConctSeg[chanRight] = NIL; IF seg.trackNum = 0 AND ~seg.failed AND (seg.trackConstraint # 0 OR (seg.exteriorPins[chanLeft].pinPosition.pLoc = seg.exteriorPins[chanRight].pinPosition.pLoc AND noAdjacentSegs)) THEN { segment _ seg; segLayer _ CanConvert[chanData, seg]; segSpec.seg _ segment; segSpec.segLayer _ segLayer; quit _ FitSegment[chanData, parms, rules, segSpec, activeTrackSpec, FALSE]}}}; segSpec: ActiveSegSpec _ NEW[ActiveSegSpecRec]; chanTracks: RouteChannel.RoutingChannelTracks _ chanData.chanTracks; chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins; <> FOR activeTrackSpec: ActiveTrackSpec _ NextTrack[chanTracks, NIL, method], NextTrack[chanTracks, activeTrackSpec, method] WHILE activeTrackSpec # NIL DO <<>> <> FOR activeSegSpec: ActiveSegSpec _ GetNextSegment[chanPins, NIL, activeTrackSpec, PreSegProc], GetNextSegment[chanPins, activeSegSpec, activeTrackSpec, PreSegProc] WHILE activeSegSpec # NIL DO <> PlaceSegment[chanTracks, parms, rules, activeSegSpec, activeTrackSpec]; ENDLOOP; -- FOR GetNextSegment ENDLOOP; -- FOR activeTrackSpec: }; -- PreAssignSegs AssignVariableSegs: PROC [chanData: RouteChannel.ChannelData, parms: RoutePrivate.RoutingAreaParms, rules: Route.DesignRules, method: RouteChannel.Method] = { <> AsgnSegProc: SegProc = { IF seg # NIL THEN IF seg.trackNum = 0 AND ~seg.failed THEN { segment _ seg; segLayer _ CanConvert[chanData, seg]; segSpec.seg _ seg; segSpec.segLayer _ segLayer; quit _ FitSegment[chanData, parms, rules, segSpec, activeTrackSpec, TRUE]}; }; moreToDo: BOOLEAN _ TRUE; numTracksWOSegs: NAT _ 0; chanTracks: RouteChannel.RoutingChannelTracks _ chanData.chanTracks; chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins; segSpec: ActiveSegSpec _ NEW[ActiveSegSpecRec]; <> FOR activeTrackSpec: ActiveTrackSpec _ NextTrack[chanTracks, NIL, method], NextTrack[chanTracks, activeTrackSpec, method] WHILE moreToDo AND activeTrackSpec # NIL DO segOnThisTrack: BOOLEAN _ FALSE; <<>> <> FOR activeSegSpec: ActiveSegSpec _ GetNextSegment[chanPins, NIL, activeTrackSpec, AsgnSegProc], GetNextSegment[chanPins, activeSegSpec, activeTrackSpec, AsgnSegProc] WHILE activeSegSpec # NIL DO <> stillGoing: BOOLEAN _ TRUE; nextSegSpec: ActiveSegSpec; PlaceSegment[chanTracks, parms, rules, activeSegSpec, activeTrackSpec]; segOnThisTrack _ TRUE; nextSegSpec _ FollowingSeg[activeSegSpec, activeTrackSpec]; stillGoing _ FALSE; WHILE nextSegSpec # NIL AND stillGoing DO nextSegSpec.segLayer _ CanConvert[chanData, nextSegSpec.seg]; IF FitSegment[chanData, parms, rules, nextSegSpec, activeTrackSpec, TRUE] THEN { PlaceSegment[chanTracks, parms, rules, nextSegSpec, activeTrackSpec]; nextSegSpec _ FollowingSeg[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 HackedAssignVariableSegs: PROC [chanData: RouteChannel.ChannelData, parms: RoutePrivate.RoutingAreaParms, rules: Route.DesignRules, method: RouteChannel.Method, numSegmentsMustPlace: INT] = { <> AsgnSegProc: SegProc = { IF seg # NIL THEN IF seg.trackNum = 0 AND ~seg.failed AND ~List.Memb[seg, segsTried] THEN { segment _ seg; segLayer _ CanConvert[chanData, seg]; segSpec.seg _ seg; segSpec.segLayer _ segLayer; quit _ FitSegment[chanData, parms, rules, segSpec, activeTrackSpec, TRUE]}; }; moreToDo: BOOLEAN _ TRUE; numTracksWOSegs: NAT _ 0; chanTracks: RouteChannel.RoutingChannelTracks _ chanData.chanTracks; chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins; segSpec: ActiveSegSpec _ NEW[ActiveSegSpecRec]; segOnThisTrack: BOOLEAN; segsTried: LIST OF REF ANY; <> FOR activeTrackSpec: ActiveTrackSpec _ NextTrack[chanTracks, NIL, method], NextTrack[chanTracks, activeTrackSpec, method] WHILE moreToDo AND activeTrackSpec # NIL DO segOnThisTrack _ FALSE; segsTried _ NIL; <<>> <> FOR activeSegSpec: ActiveSegSpec _ GetNextSegment[chanPins, NIL, activeTrackSpec, AsgnSegProc], GetNextSegment[chanPins, activeSegSpec, activeTrackSpec, AsgnSegProc] WHILE activeSegSpec # NIL DO <> stillGoing: BOOLEAN _ TRUE; <> numSegmentsPlaced: INT _ 1; nextSegSpec: ActiveSegSpec _ FollowingSeg[activeSegSpec, activeTrackSpec]; segsTried _ CONS[activeSegSpec.seg, segsTried]; WHILE nextSegSpec # NIL AND stillGoing DO nextSegSpec.segLayer _ CanConvert[chanData, nextSegSpec.seg]; IF FitSegment[chanData, parms, rules, nextSegSpec, activeTrackSpec, TRUE] THEN { numSegmentsPlaced _ numSegmentsPlaced + 1; nextSegSpec _ FollowingSeg[nextSegSpec, activeTrackSpec]; } ELSE stillGoing _ FALSE; ENDLOOP; -- WHILE nextSeg # NIL IF nextSegSpec = NIL OR numSegmentsPlaced >= numSegmentsMustPlace THEN { PlaceSegment[chanTracks, parms, rules, activeSegSpec, activeTrackSpec]; segOnThisTrack _ TRUE; nextSegSpec _ FollowingSeg[activeSegSpec, activeTrackSpec]; stillGoing _ TRUE; WHILE nextSegSpec # NIL AND stillGoing DO nextSegSpec.segLayer _ CanConvert[chanData, nextSegSpec.seg]; IF FitSegment[chanData, parms, rules, nextSegSpec, activeTrackSpec, TRUE] THEN { PlaceSegment[chanTracks, parms, rules, nextSegSpec, activeTrackSpec]; nextSegSpec _ FollowingSeg[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: PROC [chanTracks: RouteChannel.RoutingChannelTracks, activeTrackSpec: ActiveTrackSpec, method: RouteChannel.Method] RETURNS [nextTrackSpec: ActiveTrackSpec] = { <> OutsideInTopStop: PROC [track: RouteChannel.MaxTracks] RETURNS [BOOLEAN] = INLINE { IF chanTracks.count MOD 2 # 0 THEN RETURN[track = chanTracks.count/2 + 1] ELSE RETURN[track = chanTracks.count/2]; }; OutsideInBottomStop: PROC [track: RouteChannel.MaxTracks] RETURNS [BOOLEAN] = INLINE { RETURN[track = chanTracks.count/2 + 1]; }; trialTrack: RouteChannel.ZMaxTracks; freeArea: RouteChannel.AboveOrBelow; going: RouteChannel.GoingDirection; 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 => Error[programmingError, "Pack direction error"]; SELECT method.directionSequence FROM leftToRight, alternateLeft => going _ leftToRight; rightToLeft, alternateRight => going _ rightToLeft; ENDCASE => Error[programmingError, "Pack direction error"]} ELSE { -- keep going IF ~(activeTrackSpec.track IN RouteChannel.MaxTracks) THEN 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 => 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 => Error[programmingError, "Pack direction error"]}; <> IF ~(trialTrack IN [1 .. chanTracks.count]) THEN nextTrackSpec _ NIL ELSE { nextTrackSpec _ NEW[ActiveTrackSpecRec _ [trialTrack, going, freeArea]]; <> <<{TerminalIO.PutRope[Rope.Cat["\n New track: ", Convert.RopeFromInt[trialTrack]]];>> <> }; }; -- NextTrack <> PlaceSegment: PROC [chanTracks: RouteChannel.RoutingChannelTracks, parms: RoutePrivate.RoutingAreaParms, rules: Route.DesignRules, activeSegSpec: ActiveSegSpec, activeTrackSpec: ActiveTrackSpec] = { track: RouteChannel.ZMaxTracks _ activeTrackSpec.track; trackLoc: DABasics.Number _ RouteChannel.TrackLoc[chanTracks, parms, rules, track]; mustKeep: RouteChannel.ZMaxTracks _ RouteChannel.InfluenceTracks[rules, activeSegSpec.seg.net.trunkWidth]; lowerTrack: RouteChannel.ZMaxTracks _ MAX[track - mustKeep, 1]; upperTrack: RouteChannel.ZMaxTracks _ MIN[track + mustKeep, chanTracks.count]; firstSeg: RouteChannel.Segment _ RouteChannel.TrackSeg[chanTracks, track]; featureSize: NAT _ MAX[rules.contactSize, activeSegSpec.seg.qWidth]; distance: NAT _ (featureSize + rules.trunkSpacing + rules.trunkToTrunk)/2; <> IF activeSegSpec.seg.trackNum # 0 THEN 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[chanTracks, parms, rules, 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: PROC [chanData: RouteChannel.ChannelData, parms: RoutePrivate.RoutingAreaParms, rules: Route.DesignRules, nextSegSpec: ActiveSegSpec, activeTrackSpec: ActiveTrackSpec, useConstraints: BOOLEAN] RETURNS [fitsSoFar: BOOLEAN _ FALSE] = { <> chanTracks: RouteChannel.RoutingChannelTracks _ chanData.chanTracks; trackNum: RouteChannel.MaxTracks _ activeTrackSpec.track; blocked: BOOLEAN _ chanTracks.tracks[trackNum].blocked; trackConstraint: RouteChannel.ZMaxTracks _ nextSegSpec.seg.trackConstraint; IF (trackConstraint # 0 AND trackConstraint # activeTrackSpec.track) OR blocked THEN RETURN[fitsSoFar]; <<>> <> fitsSoFar _ FitSegmentThisTrack[chanTracks, rules, nextSegSpec, activeTrackSpec]; <<>> <> IF fitsSoFar THEN fitsSoFar _ FitSegmentAdjTracks[chanTracks, parms, rules, nextSegSpec, activeTrackSpec, chanTracks.count]; <<>> <> IF fitsSoFar AND useConstraints THEN fitsSoFar _ FitSegmentConstraints[chanData.constraints, nextSegSpec, activeTrackSpec]; }; -- FitSegment FitSegmentThisTrack: PROC [chanTracks: RouteChannel.RoutingChannelTracks, rules: Route.DesignRules, nextSegSpec: ActiveSegSpec, activeTrackSpec: ActiveTrackSpec] RETURNS [fitsSoFar: BOOLEAN _ TRUE] = { <> trialSeg: RouteChannel.Segment _ nextSegSpec.seg; trackNum: RouteChannel.MaxTracks _ activeTrackSpec.track; segLayer: RoutePrivate.RoutingLayerOrNone _ nextSegSpec.segLayer; <> FOR existingSeg: RouteChannel.Segment _ RouteChannel.TrackSeg[chanTracks, trackNum], existingSeg.nextSeg WHILE existingSeg # NIL AND fitsSoFar DO IF existingSeg.net.num # trialSeg.net.num THEN { SELECT TRUE FROM segLayer = trunk AND existingSeg.routingLayer = trunk => fitsSoFar _ ~OverlapCheck[rules, existingSeg, trialSeg, MAX[rules.trunkSpacing, rules.branchSpacing]]; segLayer = trunk AND existingSeg.routingLayer = branch => fitsSoFar _ ~EndOverlapCheck[rules, existingSeg, trialSeg, rules.branchSpacing]; segLayer = branch AND existingSeg.routingLayer = trunk => fitsSoFar _ ~EndOverlapCheck[rules, trialSeg, existingSeg, rules.branchSpacing]; segLayer = branch AND existingSeg.routingLayer = branch => fitsSoFar _ ~OverlapCheck[rules, existingSeg, trialSeg, rules.branchSpacing]; ENDCASE}; ENDLOOP; }; -- FitSegmentThisTrack FitSegmentAdjTracks: PROC [chanTracks: RouteChannel.RoutingChannelTracks, parms: RoutePrivate.RoutingAreaParms, rules: Route.DesignRules, nextSegSpec: ActiveSegSpec, activeTrackSpec: ActiveTrackSpec, maxTrack: RouteChannel.ZMaxTracks] RETURNS [fitsSoFar: BOOLEAN _ TRUE] = { <> firstPass: BOOLEAN _ TRUE; trialSeg: RouteChannel.Segment _ nextSegSpec.seg; trackNum: RouteChannel.MaxTracks _ activeTrackSpec.track; halfTrunkW: NAT _ trialSeg.net.trunkWidth/2; halfqWidth: NAT _ trialSeg.qWidth/2; trialPos: DABasics.Number _ RouteChannel.TrackLoc[chanTracks, parms, rules, trackNum]; maxPos: DABasics.Number _ RouteChannel.TrackLoc[chanTracks, parms, rules, maxTrack] + rules.trunkToEdge - rules.trunkSpacing; minPos: DABasics.Number _ RouteChannel.TrackLoc[chanTracks, parms, rules, 1] - rules.trunkToEdge + rules.trunkSpacing; influence: DABasics.Number _ RouteChannel.InfluenceTracks[rules, parms.widestTrunk/2] + RouteChannel.InfluenceTracks[rules, halfTrunkW]; lowerTrack: RouteChannel.MaxTracks _ MAX[trackNum - influence, 1]; upperTrack: RouteChannel.MaxTracks _ MIN[trackNum + influence, chanTracks.count]; <<>> <> IF maxPos < trialPos + halfqWidth OR trialPos - halfqWidth < minPos THEN fitsSoFar _ FALSE; <> FOR adjTrack: RouteChannel.MaxTracks IN [lowerTrack .. upperTrack] WHILE fitsSoFar DO IF adjTrack # activeTrackSpec.track THEN { adjTrackPos: DABasics.Number _ RouteChannel.TrackLoc[chanTracks, parms, rules, adjTrack]; distance: DABasics.Number _ ABS[adjTrackPos - trialPos] - chanTracks.tracks[adjTrack].maxFeatureOnTrack/2 - halfTrunkW; 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[chanTracks, adjTrack], existingSeg.nextSeg WHILE existingSeg # NIL AND fitsSoFar DO segLayer: RoutePrivate.RoutingLayerOrNone _ nextSegSpec.segLayer; IF existingSeg.net.num # trialSeg.net.num THEN { -- check to see if wires interfere with each other IF ABS[trialPos - adjTrackPos] < halfqWidth + rules.trunkSpacing + existingSeg.qWidth/2 THEN fitsSoFar _ ~OverlapCheck[rules, existingSeg, trialSeg, rules.branchSpacing]}; <> IF rules.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[rules, trialPin, trialPos, existPin, adjTrackPos, MAX[rules.trunkSpacing, rules.branchSpacing]]; ENDLOOP; ENDLOOP}}; ENDLOOP}}; ENDLOOP; }; -- FitSegmentAdjTracks FitSegmentConstraints: PROC [graph: RouteDiGraph.Graph, nextSegSpec: ActiveSegSpec, activeTrackSpec: ActiveTrackSpec] RETURNS [fitsSoFar: BOOLEAN _ TRUE] = { <> <> 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]; }; }; -- FitSegmentConstraints EndOverlapCheck: PROC [rules: Route.DesignRules, branchSeg, trunkSeg: RouteChannel.Segment, dist: DABasics.Number] RETURNS [overlap: BOOLEAN] = { EachPin: RouteChannel.EachPinActionProc ~ { leftTrunkPinLoc: DABasics.Number _ pin.pinPosition.pLoc - RouteUtil.GetWidthWithContact[rules, pin.pWidth]/2; rightTrunkPinLoc: DABasics.Number _ pin.pinPosition.pLoc + RouteUtil.GetWidthWithContact[rules, pin.pWidth]/2; gap: RTBasic.Range _ 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: DABasics.Number _ leftBranchPin.pinPosition.pLoc - RouteUtil.GetWidthWithContact[rules, leftBranchPin.pWidth]/2; rightBranchPin: RouteChannel.ChanPin _ branchSeg.exteriorPins[chanRight]; rightBranchLoc: DABasics.Number _ rightBranchPin.pinPosition.pLoc + RouteUtil.GetWidthWithContact[rules, rightBranchPin.pWidth]/2; overlap _ RouteChannel.EnumPinsOnSeg[trunkSeg, EachPin]; }; HalfOverlapCheck: PROC [rules: Route.DesignRules, seg1, seg2: RouteChannel.Segment, dist: DABasics.Number] RETURNS [overlap: BOOLEAN] = { leftPin1: RouteChannel.ChanPin _ seg1.exteriorPins[chanLeft]; left1Loc: DABasics.Number _ leftPin1.pinPosition.pLoc - RouteUtil.GetWidthWithContact[rules, leftPin1.pWidth]/2; rightPin1: RouteChannel.ChanPin _ seg1.exteriorPins[chanRight]; right1Loc: DABasics.Number _ rightPin1.pinPosition.pLoc + RouteUtil.GetWidthWithContact[rules, rightPin1.pWidth]/2; leftPin2: RouteChannel.ChanPin _ seg2.exteriorPins[chanLeft]; left2Loc: DABasics.Number _ leftPin2.pinPosition.pLoc - RouteUtil.GetWidthWithContact[rules, leftPin2.pWidth]/2; rightPin2: RouteChannel.ChanPin _ seg2.exteriorPins[chanRight]; right2Loc: DABasics.Number _ rightPin2.pinPosition.pLoc + RouteUtil.GetWidthWithContact[rules, rightPin2.pWidth]/2; gap: RTBasic.Range _ Gap[[left1Loc, right1Loc], [left2Loc, right2Loc]]; IF gap.l > gap.r THEN overlap _ TRUE ELSE overlap _ gap.r - gap.l < dist; }; OverlapCheck: PROC [rules: Route.DesignRules, seg1, seg2: RouteChannel.Segment, dist: DABasics.Number] RETURNS [overlap: BOOLEAN] = INLINE { overlap _ HalfOverlapCheck[rules, seg1, seg2, dist] OR HalfOverlapCheck[rules, seg2, seg1, dist]; }; ContactCheck: PROC [rules: Route.DesignRules, pin1: RouteChannel.ChanPin, qPos1: DABasics.Number, pin2: RouteChannel.ChanPin, qPos2, dist: DABasics.Number] RETURNS [overlap: BOOLEAN _ FALSE] = { IF ABS[qPos1 - qPos2] < dist THEN { left1Loc: DABasics.Number _ pin1.pinPosition.pLoc - RouteUtil.GetWidthWithContact[rules, pin1.pWidth]/2; right1Loc: DABasics.Number _ pin1.pinPosition.pLoc + RouteUtil.GetWidthWithContact[rules, pin1.pWidth]/2; left2Loc: DABasics.Number _ pin2.pinPosition.pLoc - RouteUtil.GetWidthWithContact[rules, pin2.pWidth]/2; right2Loc: DABasics.Number _ pin2.pinPosition.pLoc + RouteUtil.GetWidthWithContact[rules, pin2.pWidth]/2; gap: RTBasic.Range _ Gap[[left1Loc, right1Loc], [left2Loc, right2Loc]]; IF gap.l > gap.r THEN overlap _ TRUE ELSE overlap _ gap.r - gap.l < dist}; }; -- ContactCheck ConstraintCheck: PROC [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: PROC [chanPins: RouteChannel.RoutingChannelPins, activeSegSpec: ActiveSegSpec, activeTrackSpec: ActiveTrackSpec, segProc: SegProc] RETURNS [nextSegSpec: ActiveSegSpec _ NIL] = { <> CheckSegs: RouteChannel.EachPinActionProc = { <> [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; lastIndex: RouteChannel.ZMPinsOnCh _ 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 <> found _ RouteChannel.EnumPins[chanPins.sides[posIndex], 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 <> found _ RouteChannel.EnumPins[chanPins.sides[posIndex], CheckSegs] ENDLOOP; }; -- posIndex ENDCASE; IF found THEN { <> nextSegSpec _ IF activeSegSpec = NIL THEN NEW[ActiveSegSpecRec] ELSE activeSegSpec; nextSegSpec.seg _ seg; nextSegSpec.segLayer _ segLayer; }; <> <> <<{TerminalIO.PutRope[Rope.Cat["\n New segment: ", nextSegSpec.seg.net.name, ", ", RouteUtil.RoutingLayerName[nextSegSpec.segLayer]]];>> <<};>> }; -- GetNextSegment FollowingSeg: PROC [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[pinPos, CheckFitSegs] }; -- FollowingSeg AnalyzeResult: PROC [chanData: RouteChannel.ChannelData, parms: RoutePrivate.RoutingAreaParms, rules: Route.DesignRules] RETURNS [result: Route.ResultData] = { RemoveTrackIfPossible: PROC [chanTracks: RouteChannel.RoutingChannelTracks, track, oldNumTracks: RouteChannel.MaxTracks] RETURNS [numTracks: RouteChannel.ZMaxTracks] = INLINE { <> IF ~chanTracks.tracks[track].blocked AND ~chanTracks.tracks[track].keep THEN numTracks _ RemoveTrack[chanTracks, track, oldNumTracks] -- assume track can be removed ELSE numTracks _ oldNumTracks; }; EnumSegments: RouteChannel.EnumSegmentsProc = { length: DABasics.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}; EnumVias: RouteChannel.EnumViasProc = { <<-- PROC [parms: RoutePrivate.RoutingAreaParms, name: Rope.ROPE, pos, size: DABasics.Position, layer1, layer2: CD.Layer];>> <> 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[chanTracks, trackIndex] = NIL THEN -- this track has no segments numTracks _ RemoveTrackIfPossible[chanTracks, trackIndex, numTracks]; }; <> chanTracks: RouteChannel.RoutingChannelTracks _ chanData.chanTracks; chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins; metal1length, metal2length, polyLength, otherLength: DABasics.Number _ 0; polyToMetal, metalToMetal2, numIncompletes: NAT _ 0; metalLayer: CD.Layer _ parms.metalLayer; metal2Layer: CD.Layer _ parms.metal2Layer; polyLayer: CD.Layer _ parms.polyLayer; rect: DABasics.Rect; loc1, loc2: DABasics.Position; incompleteList: 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[chanTracks, ElimUselessTracks]; chanTracks.count _ numTracks; }; loc1 _ RouteUtil.PQToXY[rules, [chanPins.cEnd1, chanData.chanSides[chanBottom].routeAreaCoord]]; SELECT parms.routerUsed FROM channel => { thisChanWidth: DABasics.Number _ RouteChannel.ChannelWidth[chanTracks, parms, rules]; loc2 _ RouteUtil.PQToXY[rules, [chanPins.cEnd2, chanData.chanSides[chanBottom].routeAreaCoord + thisChanWidth]]; }; switchBox => loc2 _ RouteUtil.PQToXY[rules, [chanPins.cEnd2, chanData.chanSides[chanTop].routeAreaCoord]]; ENDCASE => ERROR; rect _ [loc1.x, loc1.y, loc2.x, loc2.y]; RouteChannel.GetRouting[chanData, parms, rules, rect, NIL, NIL, EnumSegments, EnumVias, EnumIncompletes]; result _ NEW[Route.ResultDataRec _ [polyLength, metal1length, metal2length, polyToMetal, metalToMetal2, chanTracks.count, numIncompletes, rect, FALSE, incompleteList]]; }; -- AnalyzeResult CanConvert: PROC [chanData: RouteChannel.ChannelData, seg: RouteChannel.Segment] RETURNS [segLayer: RoutePrivate.RoutingLayerOrNone _ trunk] = { <> leftPin: RouteChannel.ChanPin _ seg.exteriorPins[chanLeft]; rightPin: RouteChannel.ChanPin _ seg.exteriorPins[chanRight]; <> <> <> IF leftPin.kindOfPin = exitPin OR rightPin.kindOfPin = exitPin THEN RETURN; IF rightPin.pinPosition.pLoc - leftPin.pinPosition.pLoc <= chanData.chanParms.maxToConvert AND ABS[leftPin.pinPosition.pinIndex - rightPin.pinPosition.pinIndex] <= 1 THEN segLayer _ branch; }; RemoveTrack: PROC [chanTracks: RouteChannel.RoutingChannelTracks, track, oldNumTracks: RouteChannel.ZMaxTracks] RETURNS [numTracks: RouteChannel.ZMaxTracks] = { <> 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; }; Error: ERROR[errorType: Route.ErrorType _ callingError, explanation: Rope.ROPE _ NIL] = CODE; <> <<>> Gap: PROC [r1, r2: RTBasic.Range] RETURNS [gap: RTBasic.Range] = INLINE { <> IF r2.r