DIRECTORY CD, CDBasics, CDRects, CDRoutingObjects, DABasics, Rope, Route, RouteChannel, RoutePrivate, RouteUtil, RTBasic, SymTab; RouteChannelRetrieveImpl: CEDAR PROGRAM IMPORTS CDBasics, CDRects, Rope, Route, RouteChannel, RouteUtil, RTBasic, SymTab EXPORTS RouteChannel = { GetRouting: PUBLIC PROC [chanData: RouteChannel.ChannelData, parms: RoutePrivate.RoutingAreaParms, rules: Route.DesignRules, rect: DABasics.Rect, brokenNetName: Route.BrokenNetProc, channelData: REF ANY, enumSegments: RouteChannel.EnumSegmentsProc, enumVias: RouteChannel.EnumViasProc, enumIncompletes: RouteChannel.EnumIncompletesProc] = { DoVias: PROC [chanTracks: RouteChannel.RoutingChannelTracks, parms: RoutePrivate.RoutingAreaParms, rules: Route.DesignRules, enumVias: RouteChannel.EnumViasProc, seg: RouteChannel.Segment, name: Rope.ROPE, intervalList: RTBasic.RangeList] ~ { trunkL: CD.Layer _ RouteUtil.RoutingLayerToLayer[rules, trunk]; branchL: CD.Layer _ RouteUtil.RoutingLayerToLayer[rules, branch]; trackLoc: DABasics.Number _ RouteChannel.TrackLoc[chanTracks, parms, rules, seg.trackNum]; FOR list: RTBasic.RangeList _ intervalList, list.rest WHILE list # NIL DO range: RTBasic.Range _ list.first; enumVias[parms, name, RouteUtil.PQToXY[rules, [(range.l+range.r)/2, trackLoc]], RouteUtil.PQToXY[rules, [range.r-range.l, seg.qWidth]], trunkL, branchL]; ENDLOOP }; PinPos: PROC [pin: RouteChannel.ChanPin] RETURNS [pos: DABasics.Number] = { IF pin.kindOfPin # exitPin THEN pos _ pin.pinPosition.pLoc ELSE SELECT pin.pinSide FROM chanLeft => pos _ pos1.p; chanRight => pos _ pos2.p; ENDCASE => Route.Error[programmingError, "Invalid data. Call maintainer."]; }; ExitSegPos: PROC [pin: RouteChannel.ChanPin, width: DABasics.Number] RETURNS [pos: DABasics.Number] = { pos _ IF pin.pinSide = chanLeft THEN pos1.p + width/2 ELSE IF pin.pinSide = chanRight THEN pos2.p - width/2 ELSE Route.Error[programmingError, "Invalid data. Call maintainer."]; }; AnalyzeBranch: PROC [ branchPos: RouteChannel.PinPosition, segmentLink: RouteChannel.Segment, name: Rope.ROPE, branchSide, segmentSide: RouteChannel.ChanLRSide, intervalList: RTBasic.RangeList] RETURNS [branchWidth: DABasics.Number, newIntervalList: RTBasic.RangeList] = { AnalyzeEachPin: RouteChannel.EachPinActionProc = { IF pin # NIL THEN { SELECT pin.kindOfPin FROM chanConnect, compPin => { seg: RouteChannel.Segment _ pin.conctSeg[segmentSide]; IF seg # NIL THEN { segLength: DABasics.Number _ RouteChannel.Length[seg]; IF seg = segmentLink THEN { trackLoc: DABasics.Number _ RouteChannel.TrackLoc[chanTracks, parms, rules, seg.trackNum]; otherSeg: RouteChannel.Segment; qLoc: DABasics.Number; pLoc: DABasics.Number _ pin.pinPosition.pLoc; SELECT pin.pinSide FROM chanTop => { qLoc _ topLoc + pin.qLoc; upperMaxQ _ MAX[upperMaxQ, qLoc]; upperMinQ _ MIN[upperMinQ, qLoc]; upperBranchWidth _ MAX[upperBranchWidth, pin.pWidth]; }; chanBottom => { qLoc _ bottomLoc + pin.qLoc; lowerMaxQ _ MAX[lowerMaxQ, qLoc]; lowerMinQ _ MIN[lowerMinQ, qLoc]; lowerBranchWidth _ MAX[lowerBranchWidth, pin.pWidth]; }; ENDCASE; IF seg.routingLayer = trunk AND segLength > 0 THEN intervalList _ AddInterval[pin.pinPosition.pLoc, pin.pWidth, rules.branchSpacing, intervalList]; otherSeg _ pin.conctSeg[branchSide]; IF otherSeg # NIL THEN IF otherSeg.trackNum # 0 THEN { otherTrackLoc: DABasics.Number _ RouteChannel.TrackLoc[chanTracks, parms, rules, otherSeg.trackNum]; IF (otherTrackLoc # 0) AND (otherTrackLoc # trackLoc OR otherSeg.routingLayer # segmentLink.routingLayer) THEN { otherSegLength: DABasics.Number _ RouteChannel.Length[otherSeg]; upperMaxQ _ MAX[upperMaxQ, otherTrackLoc + otherSeg.qWidth/2]; upperMinQ _ MIN[upperMinQ, otherTrackLoc - otherSeg.qWidth/2]; lowerMaxQ _ MAX[lowerMaxQ, otherTrackLoc + otherSeg.qWidth/2]; lowerMinQ _ MIN[lowerMinQ, otherTrackLoc - otherSeg.qWidth/2]; IF otherSeg.routingLayer = trunk AND otherSegLength > 0 THEN intervalList _ AddInterval[pin.pinPosition.pLoc, pin.pWidth, rules.branchSpacing, intervalList]; }; }; }; }; }; dogLeg => { segList: RouteChannel.SegmentList _ RouteChannel.GetSegsOnPin[pin]; trackNum: INT _ IF segList.first # NIL THEN segList.first.trackNum ELSE 0; differentTracks: BOOLEAN _ FALSE; FOR segs: RouteChannel.SegmentList _ segList.rest, segs.rest WHILE segs # NIL AND ~differentTracks DO seg: RouteChannel.Segment _ segs.first; IF seg.trackNum # 0 AND trackNum # seg.trackNum THEN differentTracks _ TRUE; trackNum _ seg.trackNum; ENDLOOP; IF differentTracks THEN { FOR segs: RouteChannel.SegmentList _ segList, segs.rest WHILE segs # NIL DO seg: RouteChannel.Segment _ segs.first; IF seg.trackNum # 0 THEN { trackLoc: DABasics.Number _ RouteChannel.TrackLoc[chanTracks, parms, rules, seg.trackNum]; IF trackLoc # 0 THEN {lowerBranchWidth _ MAX[lowerBranchWidth, pin.pWidth]; upperBranchWidth _ MAX[upperBranchWidth, pin.pWidth]; upperMaxQ _ MAX[upperMaxQ, trackLoc + seg.qWidth/2]; upperMinQ _ MIN[upperMinQ, trackLoc - seg.qWidth/2]; lowerMaxQ _ MAX[lowerMaxQ, trackLoc + seg.qWidth/2]; lowerMinQ _ MIN[lowerMinQ, trackLoc - seg.qWidth/2]; IF seg.routingLayer = trunk AND seg = segmentLink THEN intervalList _ AddInterval[pin.pinPosition.pLoc, pin.pWidth, rules.branchSpacing, intervalList]; }; }; ENDLOOP; }; }; exitPin => { seg: RouteChannel.Segment _ pin.conctSeg[segmentSide]; IF seg # NIL THEN IF seg = segmentLink AND seg.trackNum # 0 THEN { layer: CD.Layer _ RouteUtil.RoutingLayerToLayer[rules, seg.routingLayer]; exitP: DABasics.Number _ PinPos[pin]; trackQ: DABasics.Number _ RouteChannel.TrackLoc[chanTracks, parms, rules, seg.trackNum]; exitQ: DABasics.Number; IF parms.routerUsed = channel THEN exitQ _ trackQ ELSE { maxQ: DABasics.Number _ MAX[trackQ+seg.qWidth/2, pin.qLoc+seg.qWidth/2]; minQ: DABasics.Number _ MIN[trackQ-seg.qWidth/2, pin.qLoc-seg.qWidth/2]; pPos: DABasics.Number _ ExitSegPos[pin, rules.trunkWidth]; enumSegments[ parms, name, RouteUtil.PQToXY[rules, [pPos, maxQ]], RouteUtil.PQToXY[rules, [pPos, minQ]], rules.trunkWidth, layer]; exitQ _ pin.qLoc}}}; ENDCASE; }; }; trackLoc: DABasics.Number _ RouteChannel.TrackLoc[chanTracks, parms, rules, segmentLink.trackNum]; branchL: CD.Layer _ RouteUtil.RoutingLayerToLayer[rules, branch]; lowerMaxQ, upperMaxQ: DABasics.Number _ trackLoc + segmentLink.qWidth/2; lowerMinQ, upperMinQ: DABasics.Number _ trackLoc - segmentLink.qWidth/2; lowerBranchWidth, upperBranchWidth: DABasics.Number _ 0; [] _ RouteChannel.EnumPins[branchPos, AnalyzeEachPin]; IF lowerMaxQ > lowerMinQ + segmentLink.qWidth AND lowerBranchWidth > 0 THEN enumSegments[parms, name, RouteUtil.PQToXY[rules, [branchPos.pLoc, lowerMinQ]], RouteUtil.PQToXY[rules, [branchPos.pLoc, lowerMaxQ]], lowerBranchWidth, branchL]; IF upperMaxQ > upperMinQ + segmentLink.qWidth AND upperBranchWidth > 0 AND (lowerMaxQ # upperMaxQ OR lowerMinQ # upperMinQ) THEN enumSegments[parms, name, RouteUtil.PQToXY[rules, [branchPos.pLoc, upperMinQ]], RouteUtil.PQToXY[rules, [branchPos.pLoc, upperMaxQ]], upperBranchWidth, branchL]; branchWidth _ MAX[lowerBranchWidth, upperBranchWidth]; newIntervalList _ intervalList; }; -- AnalyzeBranch EachTrack: RouteChannel.EachTrackActionProc = { FOR seg: RouteChannel.Segment _ RouteChannel.TrackSegAbs[chanTracks, trackIndex], seg.nextSeg WHILE seg # NIL DO trackLoc: DABasics.Number _ RouteChannel.TrackLoc[chanTracks, parms, rules, seg.trackNum]; leftPin: RouteChannel.ChanPin _ seg.exteriorPins[chanLeft]; rightPin: RouteChannel.ChanPin _ seg.exteriorPins[chanRight]; leftBranchWidth, rightBranchWidth: DABasics.Number _ 0; segLayer: CD.Layer _ RouteUtil.RoutingLayerToLayer[rules, seg.routingLayer]; intervalList: RTBasic.RangeList _ NIL; nextSeg: RouteChannel.Segment; doRight: BOOLEAN; name: Rope.ROPE _ GetSegmentName[channelData, seg, brokenNetName]; RouteChannel.CheckPins[seg, leftPin, chanRight]; RouteChannel.CheckPins[seg, rightPin, chanLeft]; [leftBranchWidth, intervalList] _ AnalyzeBranch[seg.exteriorPins[chanLeft].pinPosition, seg, name, chanLeft, chanRight, intervalList]; FOR pinList: RouteChannel.ChanPinList _ seg.interiorPins, pinList.rest WHILE pinList # NIL DO pin: RouteChannel.ChanPin _ pinList.first; [, intervalList] _ AnalyzeBranch[pin.pinPosition, seg, name, chanLeft, chanRight, intervalList]; ENDLOOP; nextSeg _ NextSegment[seg]; IF nextSeg # NIL THEN doRight _ seg.trackNum # nextSeg.trackNum ELSE doRight _ TRUE; IF doRight THEN [rightBranchWidth, intervalList] _ AnalyzeBranch[rightPin.pinPosition, seg, name, chanRight, chanLeft, intervalList]; DoVias[chanTracks, parms, rules, enumVias, seg, name, intervalList]; enumSegments[parms, name, RouteUtil.PQToXY[rules, [PinPos[leftPin] - leftBranchWidth/2, trackLoc]], RouteUtil.PQToXY[rules, [PinPos[rightPin] + rightBranchWidth/2, trackLoc]], seg.qWidth, segLayer]; ENDLOOP; }; EachPin: RouteChannel.EachPinActionProc = { IF pin # NIL THEN IF pin.kindOfPin # noPin THEN { seg: RouteChannel.Segment _ pin.conctSeg[chanRight]; IF seg # NIL THEN { leftPinPosition: DABasics.Number _ seg.exteriorPins[chanLeft].pinPosition.pLoc; rightPinPosition: DABasics.Number _ seg.exteriorPins[chanRight].pinPosition.pLoc; RouteChannel.CheckSegs[seg, pin]; IF (seg.trackNum = 0 AND leftPinPosition # rightPinPosition) OR seg.failed THEN { qLoc: DABasics.Number _ IF seg.trackNum = 0 THEN 0 ELSE RouteChannel.TrackLoc[chanTracks, parms, rules, seg.trackNum]; enumIncompletes[parms, seg.net.name, RouteUtil.PQToXY[rules, [leftPinPosition, qLoc]], RouteUtil.PQToXY[rules, [rightPinPosition, qLoc]]]; }; }; }; }; chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins; chanTracks: RouteChannel.RoutingChannelTracks _ chanData.chanTracks; nRect: DABasics.Rect _ CDBasics.ReInterpreteRect[rect]; pos1: RTBasic.PQPos _ RouteUtil.XYToPQ[rules, [nRect.x1, nRect.y1]]; pos2: RTBasic.PQPos _ RouteUtil.XYToPQ[rules, [nRect.x2, nRect.y2]]; bottomLoc: DABasics.Number _ pos1.q; topLoc: DABasics.Number _ pos2.q; [] _ RouteChannel.EnumTracks[chanTracks, EachTrack]; FOR index: RouteChannel.MPinsOnCh IN [1 .. chanPins.count] DO [] _ RouteChannel.EnumPins[chanPins.sides[index], EachPin]; ENDLOOP }; AddInterval: PROC [pos, size, minGap: DABasics.Number, intervalList: RTBasic.RangeList] RETURNS [list: RTBasic.RangeList _ NIL] ~ { thisRange: RTBasic.Range _ [pos - size/2, pos+size/2]; found: BOOLEAN _ FALSE; FOR l: RTBasic.RangeList _ intervalList, l.rest WHILE l # NIL DO currentRange: RTBasic.Range _ l.first; gap: RTBasic.Range _ RTBasic.Gap[thisRange, currentRange]; lengthGap: INT _ gap.r - gap.l; IF RTBasic.Overlaps[thisRange, currentRange] OR (0 <= lengthGap AND lengthGap < minGap) THEN { currentRange _ RTBasic.Span[thisRange, currentRange]; found _ TRUE; }; list _ CONS[currentRange, list]; ENDLOOP; IF ~found THEN list _ CONS[thisRange, list]; intervalList _ list }; RetrieveSegments: PUBLIC RouteChannel.EnumSegmentsProc = { cell: CD.Object; rectSize, position: CD.Position; [position, rectSize] _ RouteUtil.LineToRect[pos1, pos2, width]; cell _ CDRects.CreateRect[rectSize, layer]; AddToList[parms.entityTable, name, [cell, position]];}; RetrieveVias: PUBLIC RouteChannel.EnumViasProc ={ cell: CD.Object _ RouteUtil.StitchVias[size, layer1, layer2, parms.lambda, parms.viaTable]; cellSize: CD.Position _ CDBasics.SizeOfRect[cell.bbox]; position: CD.Position _ [pos.x - cellSize.x/2, pos.y - cellSize.y/2]; AddToList[parms.entityTable, name, [cell, position]]}; RetrieveIncompletes: PUBLIC RouteChannel.EnumIncompletesProc = { Route.Signal[noResource, Rope.Cat["Incomplete routint of net: ", name]]}; NextSegment: PROC [seg: RouteChannel.Segment] RETURNS [nextSeg: RouteChannel.Segment] ~ { nextSeg _ seg.exteriorPins[chanRight].conctSeg[chanRight]; IF nextSeg = NIL THEN nextSeg _ seg.exteriorPins[chanRight].altConctSeg[chanRight]; }; PlOs: TYPE = REF PlOList; PlOList: TYPE = LIST OF CDRoutingObjects.PlacedObject; AddToList: PROC [table: SymTab.Ref, key: SymTab.Key, placedObj: CDRoutingObjects.PlacedObject] ~ { val: SymTab.Val _ SymTab.Fetch[table, key].val; geometry: PlOList = IF val = NIL THEN NIL ELSE NARROW [val, PlOs]^; newGeometry: PlOList _ CONS[placedObj, geometry]; [] _ SymTab.Store[table, key, NEW[PlOList _ newGeometry]]}; GetSegmentName: PROC [channelData: REF ANY, seg: RouteChannel.Segment, brokenNetName: Route.BrokenNetProc] RETURNS [label: Route.Label] ~ { IF ~seg.exitBreak OR brokenNetName = NIL THEN label _ seg.net.name ELSE { label _ brokenNetName[channelData, seg.net.netData, seg.net.name, seg.part, 2]; IF label=NIL THEN Route.Signal[noResource, "A constraint loop requires a net to be broken which client forbids breaking."]; }; }; }. 6RouteChannelRetrieveImpl.mesa Copyright Σ 1985, 1986, 1987 by Xerox Corporation. All rights reserved. by Bryan Preas July 26, 1985 2:29:20 pm PDT last edited by Bryan Preas April 3, 1987 3:06:14 pm PST Christian Le Cocq December 3, 1987 12:55:20 pm PST Enumerate routing results entities analyze the branch for this segment problems with dogleg outside pin range PROC[pinPosition: PinPosition, pin: ChanPin] RETURNS [quit: BOOLEAN _ FALSE]; check if dogleg spans more than one track dogleg spans at least two tracks, put it in analyze component pin branches enumerate this branch segment run through the segments on the track audit the pins to which this segment point figure out the left branch process the interior pins do the right branch if no following segment in this track do the vias collected during the AnalyzeBranch Calls enumerate trunk segment PROC[pinPosition: PinPosition, pin: ChanPin] RETURNS [quit: BOOLEAN _ FALSE]; pin is present, look at the segments on the right side a routing failure enumerate the incompletes and audit the segments Call back for wiring segments TYPE = PROCEDURE[ parms: RoutePrivate.RoutingAreaParms, name: Rope.ROPE, pos1, pos2: DABasics.Position, width: DABasics.Number, layer: CD.Layer]; Call back for branch ends TYPE = PROCEDURE[ parms: RoutePrivate.RoutingAreaParms, name: Rope.ROPE, pos, size: DABasics.Position, rectangle of size centered on pos layer1, layer2: CD.Layer]; TYPE = PROCEDURE[ parms: RoutePrivate.RoutingAreaParms, name: Rope.ROPE, pos1, pos2: DABasics.Position]; add placedObj to the appropriate list Κ η˜codešœ™KšœH™HKšœ*Οkœ™.Kšœ6™9K™2—˜š œœu˜K˜——šΠlnœœ˜'KšœI˜PKšœ˜K˜—šΟn œœœ$˜Kšœ œ/˜>Kšœ œ/˜>Kšœ œ/˜>šœœ˜˜>KšœD˜DKšœ7˜7KšœD˜DKšœD˜DKšœ$˜$Kšœ!˜!K˜Kšœ4˜4K™Kšœ0™0šœœ˜=Kšœ;˜;Kš˜—Kšœ˜K˜—šŸ œœGœœ˜ƒKšœ6˜6Kšœœœ˜šœ-œœ˜@Kšœ&˜&Kšœ:˜:K˜šœ+œœœ˜^Kšœ5˜5Kšœœ˜ Kšœ˜—Kšœœ˜ Kšœ˜Kšœœœ˜,Kšœ˜—Kšœ˜K˜—šŸœœ"˜:Kšœ™šœ œ™Kšœ%™%Kšœ œ™Kšœ™Kšœ™Kšœœ ™K˜—Kšœœ˜Kšœœ ˜ Kšœ?˜?Kšœ+˜+Kšœ7˜7K˜—šŸ œœ˜1Kšœ™šœ œ™Kšœ%™%Kšœ œ™KšœC™CKšœœ™—K˜KšœœS˜[Kšœ œ+˜7Kšœ œ9˜EKšœ6˜6K˜—šŸœœ%˜@šœ œ™Kšœ%™%Kšœ œ™Kšœ™—KšœI˜IK˜—šŸ œœœ$˜YKšœ:˜:šœ œ˜Kšœ=˜=—Kšœ˜K˜—Kšœœœ ˜šœ œœœ˜6K˜—šŸ œœS˜bKšœ%™%K˜Kšœ/˜/Kš œœœœœœœ˜CKšœœ˜1Kšœœ˜;K˜—š ŸœœœœAœ˜‹Kšœœœœ˜Bšœ˜KšœO˜OKšœœœj˜{Kšœ˜—Kšœ˜—Kšœ˜K˜K˜K˜—…—1D-