<> <> <> <> <> DIRECTORY CD, Convert, DABasics, IO, Rope, Route, RouteChannel, RouteDiGraph, RoutePrivate, RouteUtil, RTBasic, TerminalIO; RouteChannelUtilImpl: CEDAR PROGRAM IMPORTS Convert, IO, Rope, Route, RouteChannel, RouteDiGraph, RouteUtil, TerminalIO EXPORTS RouteChannel SHARES Route = { trackSequenceName: PUBLIC ARRAY RouteChannel.TrackSequence OF Rope.ROPE _ ["start", "outsideInTop", "outsideInBottom", "botToTop", "topToBot"]; directionSequenceName: PUBLIC ARRAY RouteChannel.DirectionSequence OF Rope.ROPE _ ["start", "leftToRight", "rightToLeft", "alternateLeft", "alternateRight"]; EnumPins: PUBLIC PROC [pinPosition: RouteChannel.PinPosition, eachAction: RouteChannel.EachPinActionProc] RETURNS [quit: BOOLEAN _ FALSE]= { pin: RouteChannel.ChanPin; IF pinPosition = NIL THEN RETURN; <> pin _ pinPosition.pins[chanBottom]; IF pin # NIL AND pin.kindOfPin # noPin THEN { quit _ eachAction[pinPosition, pin]; IF quit THEN RETURN; }; <> pin _ pinPosition.pins[chanTop]; IF pin # NIL AND pin.kindOfPin # noPin THEN { quit _ eachAction[pinPosition, pin]; IF quit THEN RETURN; }; <> FOR interiorList: RouteChannel.ChanPinList _ pinPosition.innerPins, interiorList.rest WHILE interiorList # NIL DO quit _ eachAction[pinPosition, interiorList.first]; IF quit THEN RETURN; ENDLOOP; }; EnumPinsOnSeg: PUBLIC PROC [seg: RouteChannel.Segment, eachAction: RouteChannel.EachPinActionProc] RETURNS [quit: BOOLEAN _ FALSE]= { pin: RouteChannel.ChanPin; IF seg = NIL THEN RETURN; <> pin _ seg.exteriorPins[chanLeft]; IF pin # NIL THEN { quit _ eachAction[pin.pinPosition, pin]; IF quit THEN RETURN; }; <> pin _ seg.exteriorPins[chanRight]; IF pin # NIL THEN { quit _ eachAction[pin.pinPosition, pin]; IF quit THEN RETURN; }; <> FOR interiorList: RouteChannel.ChanPinList _ seg.interiorPins, interiorList.rest WHILE interiorList # NIL DO quit _ eachAction[pin.pinPosition, interiorList.first]; IF quit THEN RETURN; ENDLOOP; }; EnumTracks: PUBLIC PROC [chanTracks: RouteChannel.RoutingChannelTracks, eachAction: RouteChannel.EachTrackActionProc] RETURNS [quit: BOOLEAN _ FALSE] = { FOR trackIndex: RouteChannel.ZMaxTracks IN [1..chanTracks.count] WHILE ~quit DO quit _ eachAction[chanTracks.tracks[trackIndex], trackIndex]; ENDLOOP; }; EnumPinPositions: PUBLIC PROC [chanPins: RouteChannel.RoutingChannelPins, eachAction: RouteChannel.EachPinPositionActionProc] RETURNS [quit: BOOLEAN _ FALSE] = { FOR pinIndex: RouteChannel.ZMPinsOnCh IN [1..chanPins.count] WHILE ~quit DO quit _ eachAction[chanPins.sides[pinIndex], pinIndex]; ENDLOOP; }; Destroy: PUBLIC PROC [chanData: RouteChannel.ChannelData] ~ { <> RouteChannel.DestroyOldConstraints[chanData]; RouteChannel.ClearChan[chanData]; }; ClearChan: PUBLIC PROCEDURE[chanData: RouteChannel.ChannelData] = { <> <> EachPin: RouteChannel.EachPinActionProc = { pin.conctSeg[chanLeft] _ pin.conctSeg[chanRight] _ NIL; pin.altConctSeg[chanLeft] _ pin.altConctSeg[chanRight] _ NIL; pin.pinPosition _ NIL; pin.pin _ NIL}; ClearTrack: RouteChannel.EachTrackActionProc = { nextSeg: RouteChannel.Segment; FOR seg: RouteChannel.Segment _ track.firstSeg, nextSeg WHILE seg # NIL DO [] _ RouteChannel.EnumPinsOnSeg[seg, EachPin]; seg.constraintNode _ NIL; seg.exteriorPins[chanLeft] _ seg.exteriorPins[chanRight] _ NIL; seg.interiorPins _ NIL; nextSeg _ seg.nextSeg; seg.nextSeg _ NIL; ENDLOOP; track.firstSeg _ NIL}; ClearPinPositions: RouteChannel.EachPinPositionActionProc = { [] _ RouteChannel.EnumPins[pinPosition, EachPin]; pinPosition.pins[chanBottom] _ pinPosition.pins[chanTop] _ NIL; pinPosition.innerPins _ NIL}; [] _ RouteChannel.EnumTracks[chanData.chanTracks, ClearTrack]; [] _ RouteChannel.EnumPinPositions[chanData.chanPins, ClearPinPositions]}; TrackLoc: PUBLIC PROC [chanTracks: RouteChannel.RoutingChannelTracks, parms: RoutePrivate.RoutingAreaParms, rules: Route.DesignRules, track: RouteChannel.ZMaxTracks] RETURNS [loc: DABasics.Number _ 0] = { IF track <= 0 THEN RETURN; SELECT parms.routerUsed FROM channel => { trackNum: RouteChannel.ZMaxTracks _ chanTracks.tracks[track].trackNum; tMinusOne: DABasics.Number _ trackNum - 1; --to coerce to 32 bits loc _ rules.trunkToEdge + tMinusOne*rules.trunkToTrunk; }; switchBox => loc _ chanTracks.tracks[track].trackPos; ENDCASE => ERROR; --??? call the implementor }; TrackSeg: PUBLIC PROC [chanTracks: RouteChannel.RoutingChannelTracks, track: RouteChannel.MaxTracks] RETURNS [RouteChannel.Segment] = { trackNum: RouteChannel.ZMaxTracks _ chanTracks.tracks[track].trackNum; RETURN[chanTracks.tracks[trackNum].firstSeg]}; TrackSegAbs: PUBLIC PROC [chanTracks: RouteChannel.RoutingChannelTracks, track: RouteChannel.MaxTracks] RETURNS [RouteChannel.Segment] = { RETURN[chanTracks.tracks[track].firstSeg]}; ChannelWidth: PUBLIC PROC [chanTracks: RouteChannel.RoutingChannelTracks, parms: RoutePrivate.RoutingAreaParms, rules: Route.DesignRules] RETURNS [loc: DABasics.Number _ 0] = { SELECT parms.routerUsed FROM channel => { countMinusOne: DABasics.Number _ chanTracks.count-1; -- to coerce to 32 bits loc _ 2*rules.trunkToEdge + countMinusOne * rules.trunkToTrunk; }; switchBox => loc _ chanTracks.tracks[chanTracks.count].trackPos + rules.trunkToEdge; ENDCASE => ERROR; --??? call the implementor... }; ExtSideToIntSide: PUBLIC PROC [rules: Route.DesignRules, extSide: DABasics.Side] RETURNS [intSide: RouteChannel.ChanSide] = { <> <<>> chanDirection: DABasics.Direction _ rules.trunkDirection; IF chanDirection = horizontal THEN SELECT extSide FROM bottom => intSide _ chanBottom; right => intSide _ chanRight; top => intSide _ chanTop; left => intSide _ chanLeft; ENDCASE ELSE SELECT extSide FROM bottom => intSide _ chanLeft; right => intSide _ chanTop; top => intSide _ chanRight; left => intSide _ chanBottom; ENDCASE}; IntSideToExtSide: PUBLIC PROC [rules: Route.DesignRules, intSide: RouteChannel.ChanSide] RETURNS [extSide: DABasics.Side] = { <> <<>> chanDirection: DABasics.Direction _ rules.trunkDirection; IF chanDirection = horizontal THEN SELECT intSide FROM chanBottom => extSide _ bottom; chanRight => extSide _ right; chanTop => extSide _ top; chanLeft => extSide _ left; ENDCASE ELSE SELECT intSide FROM chanBottom => extSide _ left; chanRight => extSide _ top; chanTop => extSide _ right; chanLeft => extSide _ bottom; ENDCASE}; InfluenceTracks: PUBLIC PROC [rules: Route.DesignRules, wireWidth: NAT] RETURNS [tracks: NAT] = { <> spacing: DABasics.Number _ rules.trunkToTrunk - MAX[rules.trunkWidth, rules.contactSize]; tracks _ (wireWidth + spacing + rules.trunkToTrunk -1) /rules.trunkToTrunk; }; WriteResult: PUBLIC PROC [result: Route.ResultData, parms: RoutePrivate.RoutingAreaParms, rules: Route.DesignRules, method: RouteChannel.Method] = { <> lambda: DABasics.Number _ parms.lambda; width: INT _ IF rules.trunkDirection = horizontal THEN result.routingRect.y2 - result.routingRect.y1 ELSE result.routingRect.x2 - result.routingRect.x1; <> TerminalIO.PutRope[Rope.Cat["\n channel width: ", Convert.RopeFromInt[width/lambda]]]; TerminalIO.PutRope[Rope.Cat[", number tracks: ", Convert.RopeFromInt[result.numTrunkTracks], "\n"]]; IF result.polyLength > 0 THEN TerminalIO.PutRope[Rope.Cat["\n poly length: ", Convert.RopeFromInt[result.polyLength/lambda], ", "]]; IF result.metalLength > 0 THEN TerminalIO.PutRope[Rope.Cat[" metal1 length: ", Convert.RopeFromInt[result.metalLength/lambda], ", "]]; IF result.metal2Length > 0 THEN TerminalIO.PutRope[Rope.Cat[" metal2 length: ", Convert.RopeFromInt[result.metal2Length/lambda], ", "]]; IF result.polyToMetal > 0 THEN TerminalIO.PutRope[Rope.Cat["\n number contacts: ", Convert.RopeFromInt[result.polyToMetal], ", "]]; IF result.metalToMetal2 > 0 THEN TerminalIO.PutRope[Rope.Cat["\n number vias: ", Convert.RopeFromInt[result.metalToMetal2], ", "]]; TerminalIO.PutF1[" number fails: %g", IO.int[result.numIncompletes]]; TerminalIO.PutRope[Rope.Cat["\n method: ", trackSequenceName[method.trackSequence],", ", directionSequenceName[method.directionSequence], "\n"]]}; FindConstraintLimits: PUBLIC PROC [ chanPins: RouteChannel.RoutingChannelPins, parms: RoutePrivate.RoutingAreaParms, rules: Route.DesignRules, nextLower, nextHigher: RouteChannel.MPinsOnCh, pinAction: RouteChannel.EachPinActionProc] RETURNS [minLimit, maxLimit: RouteChannel.MPinsOnCh] = { <> <> testWidth: DABasics.Number _ RouteUtil.GetWidthWithContact[rules, parms.widestPin] + rules.branchSpacing; <> iPos: DABasics.Number _ chanPins.sides[nextLower].pLoc; minLimit _ nextLower; FOR limitIndex: RouteChannel.MPinsOnCh DECREASING IN [1 .. nextLower] WHILE chanPins.sides[limitIndex].pLoc + testWidth > iPos DO constraining: BOOLEAN _ RouteChannel.EnumPins[chanPins.sides[limitIndex], pinAction]; IF constraining THEN minLimit _ MIN[minLimit, limitIndex]; ENDLOOP; <> iPos _ chanPins.sides[nextHigher].pLoc; maxLimit _ nextHigher; FOR limitIndex: RouteChannel.MPinsOnCh IN [nextHigher .. chanPins.count] WHILE chanPins.sides[limitIndex].pLoc - testWidth < iPos DO constraining: BOOLEAN _ RouteChannel.EnumPins[chanPins.sides[limitIndex], pinAction]; IF constraining THEN maxLimit _ MAX[maxLimit, limitIndex]; ENDLOOP}; CheckPins: PUBLIC PROCEDURE[seg: RouteChannel.Segment, pin: RouteChannel.ChanPin, sideOfSeg: RouteChannel.ChanLRSide] = { <> IF seg = NIL THEN Route.Error[programmingError, "Pin data inconsistant"] ELSE IF pin = NIL THEN Route.Error[programmingError, "Pin data inconsistant"] ELSE { found: BOOLEAN _ FALSE; IF pin.conctSeg[sideOfSeg] # NIL THEN found _ pin.conctSeg[sideOfSeg] = seg; IF pin.altConctSeg[sideOfSeg] # NIL THEN found _ found OR pin.altConctSeg[sideOfSeg] = seg; IF ~found THEN Route.Error[programmingError, "Pin data inconsistant"]}}; CheckSegs: PUBLIC PROC [seg: RouteChannel.Segment, pin: RouteChannel.ChanPin] = { <> IF seg = NIL THEN Route.Error[programmingError, "Segment data inconsistant"] ELSE IF pin = NIL THEN Route.Error[programmingError, "Segment data inconsistant"] ELSE IF seg = pin.conctSeg[chanLeft] OR seg = pin.conctSeg[chanRight] THEN RETURN ELSE IF seg = pin.altConctSeg[chanLeft] OR seg = pin.altConctSeg[chanRight] THEN RETURN ELSE { found: BOOLEAN _ FALSE; FOR testPins: RouteChannel.ChanPinList _ seg.interiorPins, testPins.rest WHILE testPins # NIL AND ~found DO testPin: RouteChannel.ChanPin _ testPins.first; IF seg = testPin.conctSeg[chanLeft] OR seg = testPin.conctSeg[chanRight] THEN found _ TRUE; IF seg = testPin.altConctSeg[chanLeft] OR seg = testPin.altConctSeg[chanRight] THEN found _ TRUE; ENDLOOP; IF ~found THEN Route.Error[programmingError, "Segment data inconsistant"]}; }; AuditPins: PUBLIC PROC [chanPins: RouteChannel.RoutingChannelPins] = { <> EachPin: RouteChannel.EachPinActionProc = { segList: RouteChannel.SegmentList _ RouteChannel.GetSegsOnPin[pin]; IF segList = NIL THEN Route.Error[programmingError, "Pin not attatched to any segment"]; FOR segs: RouteChannel.SegmentList _ segList, segs.rest WHILE segs # NIL DO RouteChannel.CheckSegs[segs.first, pin]; ENDLOOP}; FOR index: RouteChannel.MPinsOnCh IN [1 .. chanPins.count] DO [] _ RouteChannel.EnumPins[chanPins.sides[index], EachPin]; ENDLOOP; }; AuditSegs: PUBLIC PROC [chanTracks: RouteChannel.RoutingChannelTracks] = { <> EachTrack: RouteChannel.EachTrackActionProc = { FOR seg: RouteChannel.Segment _ track.firstSeg, seg.nextSeg WHILE seg # NIL DO EachPin: RouteChannel.EachPinActionProc = { found: BOOLEAN _ FALSE; IF pin.conctSeg[chanLeft] # NIL THEN found _ pin.conctSeg[chanLeft] = seg; IF pin.conctSeg[chanRight] # NIL THEN found _ found OR pin.conctSeg[chanRight] = seg; IF pin.altConctSeg[chanLeft] # NIL THEN found _ found OR pin.altConctSeg[chanLeft] = seg; IF pin.altConctSeg[chanRight] # NIL THEN found _ found OR pin.altConctSeg[chanRight] = seg; IF ~found THEN Route.Error[programmingError, "Pin data inconsistant"]}; [] _ RouteChannel.EnumPinsOnSeg[seg, EachPin]; ENDLOOP}; [] _ RouteChannel.EnumTracks[chanTracks, EachTrack]; }; WriteConstraints: PUBLIC PROC [graph: RouteDiGraph.Graph] = { NodeProc: RouteDiGraph.EnumNodeProc = { nodeInfo: RouteChannel.SegmentConstraint _ NARROW[node.nodeInfo]; TerminalIO.PutRope[Rope.Cat["\n", " name: ", nodeInfo.name]]}; TerminalIO.PutRope[Rope.Cat["\n Constraint Graph: ", RouteDiGraph.SimpleRefAny[graph.graphInfo], "\n"]]; RouteDiGraph.WriteNodes[graph, NodeProc, RouteDiGraph.SimpleListArcNodeProc]; RouteDiGraph.WriteArcs[graph, RouteDiGraph.SimpleListArcProc, NodeProc]}; GetSegsOnPin: PUBLIC PROC [pin: RouteChannel.ChanPin] RETURNS [segList: RouteChannel.SegmentList _ NIL] = { <> <> cSegL: RouteChannel.Segment _ pin.conctSeg[chanLeft]; cSegR: RouteChannel.Segment _ pin.conctSeg[chanRight]; aSegL: RouteChannel.Segment _ pin.altConctSeg[chanLeft]; aSegR: RouteChannel.Segment _ pin.altConctSeg[chanRight]; IF cSegL # NIL THEN segList _ CONS[cSegL, segList]; IF cSegR # NIL AND cSegR # cSegL THEN segList _ CONS[cSegR, segList]; IF aSegL # NIL THEN segList _ CONS[aSegL, segList]; IF aSegR # NIL AND aSegR # aSegL THEN segList _ CONS[aSegR, segList]}; GetPinsOnSeg: PUBLIC PROC [seg: RouteChannel.Segment] RETURNS [pinList: RouteChannel.ChanPinList] = { <> pinList _ CONS[seg.exteriorPins[chanLeft], seg.interiorPins]; pinList _ CONS[seg.exteriorPins[chanRight], pinList] }; ComputeDensity: PUBLIC PROC [chanPins: RouteChannel.RoutingChannelPins, rules: Route.DesignRules] RETURNS [density: RouteChannel.Density] = { <> GetDensity: RouteChannel.EachPinActionProc = { leftSeg: RouteChannel.Segment _ pin.conctSeg[chanLeft]; rightSeg: RouteChannel.Segment _ pin.conctSeg[chanRight]; pinIndex: RouteChannel.MPinsOnCh _ pinPosition.pinIndex; IF rightSeg # NIL THEN IF rightSeg.exteriorPins[chanLeft] = pin THEN {lastDensity _ lastDensity + MAX[rules.trunkToTrunk, rightSeg.qWidth + rules.trunkSpacing]}; density.maxDensity _ MAX[density.maxDensity, lastDensity]; density.values[pinIndex] _ MAX[density.values[pinIndex], lastDensity]; IF leftSeg # NIL THEN IF leftSeg.exteriorPins[chanRight] = pin THEN {lastDensity _ lastDensity - MAX[rules.trunkToTrunk, leftSeg.qWidth + rules.trunkSpacing]}}; lastDensity: DABasics.Number _ 0; density _ NEW[RouteChannel.DensityRec]; FOR index: RouteChannel.MPinsOnCh IN [1 .. chanPins.count] DO pinPosition: RouteChannel.PinPosition _ chanPins.sides[index]; density.values[index] _ lastDensity; [] _ RouteChannel.EnumPins[pinPosition, GetDensity]; ENDLOOP; }; Combine: PUBLIC PROC [l1, l2, l3: RouteChannel.ChanPinList] RETURNS [RouteChannel.ChanPinList] = { RETURN[Union[l1, Union[l2, l3]]]}; Union: PROC [l1, l2: RouteChannel.ChanPinList] RETURNS[RouteChannel.ChanPinList] = { l: RouteChannel.ChanPinList _ NIL; UNTIL l2 = NIL DO IF l2.first # NIL THEN l _ CONS[l2.first, l]; l2 _ l2.rest; ENDLOOP; UNTIL l1 = NIL DO IF l1.first # NIL THEN IF ~MembChanPinList[l1.first, l] THEN l _ CONS[l1.first, l]; l1 _ l1.rest; ENDLOOP; RETURN[l]; }; -- of Union MembChanPinList: PROC [ref: RouteChannel.ChanPin, list: RouteChannel.ChanPinList] RETURNS [BOOL] = { UNTIL list = NIL DO IF list.first = ref THEN RETURN[TRUE]; list _ list.rest; ENDLOOP; RETURN[FALSE]; }; MembRopeList: PUBLIC PROC [ref: Rope.ROPE, list: LIST OF Rope.ROPE] RETURNS [BOOL] = { UNTIL list = NIL DO IF list.first = ref THEN RETURN[TRUE]; list _ list.rest; ENDLOOP; RETURN[FALSE]; }; GetRange: PUBLIC PROC [pinList: RouteChannel.ChanPinList] RETURNS [range: RTBasic.Range] = { <> range.l _ LAST[INT]; range.r _ - LAST[INT]; FOR list: RouteChannel.ChanPinList _ pinList, list.rest WHILE list # NIL DO pos: DABasics.Number _ list.first.pinPosition.pLoc; range.l _ MIN[range.l, pos]; range.r _ MAX[range.r, pos]; ENDLOOP}; PinsOnSide: PUBLIC PROC [seg: RouteChannel.Segment] RETURNS [left, top, right, bottom: BOOLEAN _ FALSE] ~ { EachPin: RouteChannel.EachPinActionProc = { IF pin.pinSide = chanBottom THEN bottom _ TRUE; IF pin.pinSide = chanTop THEN top _ TRUE; IF pin.pinSide = chanLeft THEN left _ TRUE; IF pin.pinSide = chanRight THEN right _ TRUE}; [] _ RouteChannel.EnumPinsOnSeg[seg, EachPin]; }; Length: PUBLIC PROC [seg: RouteChannel.Segment] RETURNS [length: DABasics.Number] = { <> <<>> length _ seg.exteriorPins[chanRight].pinPosition.pLoc - seg.exteriorPins[chanLeft].pinPosition.pLoc }; }.