DIRECTORY CD, CDBasics, CDSymbolicObjects, CDProperties, CDRects, Rope, Route, RouteChannel, RoutePrivate, RouteUtil; RouteChannelRetrieveImpl: CEDAR PROGRAM IMPORTS CDBasics, CDSymbolicObjects, CDProperties, CDRects, Route, RouteChannel, RouteUtil EXPORTS RouteChannel SHARES Route = { GetRouting: PUBLIC PROCEDURE[routingArea: Route.RoutingArea, rect: Route.Rect, properties: Route.PropList, EnumSegments: RouteChannel.EnumSegmentsProc, EnumPins: RouteChannel.EnumPinsProc, EnumVias: RouteChannel.EnumViasProc, EnumExits: RouteChannel.EnumExitsProc, EnumIncompletes: RouteChannel.EnumIncompletesProc] RETURNS [externalConnections: Route.PinList _ NIL] = { EachTrack: RouteChannel.EachTrackActionProc = { FOR seg: RouteChannel.Segment _ RouteChannel.TrackSegAbs[routingArea, trackIndex], seg.nextSeg WHILE seg # NIL DO AddInterval: PosSizeProc ~ { thisRange: RoutePrivate.Range _ [pos - size/2, pos+size/2]; found: BOOLEAN _ FALSE; list: RoutePrivate.RangeList _ NIL; FOR l: RoutePrivate.RangeList _ intervalList, l.rest WHILE l # NIL DO currentRange: RoutePrivate.Range _ l.first; IF RouteChannel.Overlaps[thisRange, currentRange] THEN { currentRange _ RouteChannel.Span[thisRange, currentRange]; found _ TRUE}; list _ CONS[currentRange, list]; ENDLOOP; IF ~found THEN list _ CONS[thisRange, list]; intervalList _ list}; trackLoc: Route.Number _ RouteChannel.TrackLoc[routingArea, seg.trackNum]; leftPin: RouteChannel.ChanPin _ seg.exteriorPins[chanLeft]; rightPin: RouteChannel.ChanPin _ seg.exteriorPins[chanRight]; leftBranchWidth, rightBranchWidth: Route.Number _ 0; segLayer: Route.Layer _ RouteUtil.RoutingLayerToLayer[routingArea, seg.routingLayer]; intervalList: RoutePrivate.RangeList _ NIL; nextSeg: RouteChannel.Segment; doRight: BOOLEAN; RouteChannel.CheckPins[seg, leftPin, chanRight]; RouteChannel.CheckPins[seg, rightPin, chanLeft]; leftBranchWidth _ AnalyzeBranch[routingArea, seg.exteriorPins[chanLeft].pinPosition, seg, chanLeft, chanRight, AddInterval]; FOR pinList: RouteChannel.ChanPinList _ seg.interiorPins, pinList.rest WHILE pinList # NIL DO pin: RouteChannel.ChanPin _ pinList.first; [] _ AnalyzeBranch[routingArea, pin.pinPosition, seg, chanLeft, chanRight, AddInterval]; ENDLOOP; nextSeg _ NextSegment[seg]; IF nextSeg # NIL THEN doRight _ seg.trackNum # nextSeg.trackNum ELSE doRight _ TRUE; IF doRight THEN rightBranchWidth _ AnalyzeBranch[routingArea, rightPin.pinPosition, seg, chanRight, chanLeft, AddInterval]; DoVias[routingArea, seg, intervalList]; EnumSegments[routingArea, seg.net.name, seg.net.netPart, RouteUtil.PQToXY[routingArea, [PinPos[leftPin] - leftBranchWidth/2, trackLoc]], RouteUtil.PQToXY[routingArea, [PinPos[rightPin] + rightBranchWidth/2, trackLoc]], seg.qWidth, segLayer]; ENDLOOP}; DoVias: PROC [routingArea: Route.RoutingArea, seg: RouteChannel.Segment, intervalList: RoutePrivate.RangeList] ~ { trunkL: Route.Layer _ RouteUtil.RoutingLayerToLayer[routingArea, trunk]; branchL: Route.Layer _ RouteUtil.RoutingLayerToLayer[routingArea, branch]; trackLoc: Route.Number _ RouteChannel.TrackLoc[routingArea, seg.trackNum]; FOR list: RoutePrivate.RangeList _ intervalList, list.rest WHILE list # NIL DO range: RoutePrivate.Range _ list.first; EnumVias[routingArea, seg.net.name, seg.net.netPart, RouteUtil.PQToXY[routingArea, [(range.l+range.r)/2, trackLoc]], RouteUtil.PQToXY[routingArea, [range.r-range.l, seg.qWidth]], trunkL, branchL]; ENDLOOP}; PinPos: PROCEDURE[pin: RouteChannel.ChanPin] RETURNS [pos: Route.Number] = { IF pin.kindOfPin # exitPin THEN pos _ pin.pinPosition.pLoc ELSE { pos _ IF pin.pinSide = chanLeft THEN pos1.p ELSE IF pin.pinSide = chanRight THEN pos2.p ELSE Route.Error[programmingError, "Invalid data. Call maintainer."]}}; ExitSegPos: PROCEDURE[pin: RouteChannel.ChanPin, width: Route.Number] RETURNS [pos: Route.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."]}; EachPin: RouteChannel.EachPinActionProc = { IF pin # NIL THEN IF pin.kindOfPin # noPin THEN { seg: RouteChannel.Segment _ pin.conctSeg[chanRight]; IF seg # NIL THEN { leftPinPosition: Route.Number _ seg.exteriorPins[chanLeft].pinPosition.pLoc; rightPinPosition: Route.Number _ seg.exteriorPins[chanRight].pinPosition.pLoc; RouteChannel.CheckSegs[seg, pin]; IF (seg.trackNum = 0 AND leftPinPosition # rightPinPosition) OR seg.failed THEN { qLoc: Route.Number _ IF seg.trackNum = 0 THEN 0 ELSE RouteChannel.TrackLoc[routingArea, seg.trackNum]; EnumIncompletes[routingArea, seg.net.name, seg.net.netPart, RouteUtil.PQToXY[routingArea, [leftPinPosition, qLoc]], RouteUtil.PQToXY[routingArea, [rightPinPosition, qLoc]]]}}}}; PosSizeProc: TYPE = PROC[pos, size: Route.Number]; AnalyzeBranch: PROCEDURE[routingArea: Route.RoutingArea, branchPos: RouteChannel.PinPosition, segmentLink: RouteChannel.Segment, branchSide, segmentSide: RouteChannel.ChanLRSide, callBack: PosSizeProc] RETURNS [branchWidth: Route.Number] = { AnalyzeEachPin: RouteChannel.EachPinActionProc = { IF pin # NIL THEN { SELECT pin.kindOfPin FROM chanConnect, compPin => { seg: RouteChannel.Segment _ pin.conctSeg[segmentSide]; IF seg # NIL THEN { segLength: Route.Number _ RouteChannel.Length[seg]; IF seg = segmentLink THEN {trackLoc: Route.Number _ RouteChannel.TrackLoc[routingArea, seg.trackNum]; otherSeg: RouteChannel.Segment; qLoc: Route.Number; pLoc: Route.Number _ pin.pinPosition.pLoc; newPin: Route.Pin; 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; newPin _ BuildPin[routingArea, pin, seg, [pLoc, qLoc]]; EnumPins[routingArea, seg.net.name, seg.net.netPart, RouteUtil.PQToXY[routingArea, [pLoc, qLoc]], branchL, newPin]; IF seg.routingLayer = trunk AND segLength > 0 THEN callBack[pin.pinPosition.pLoc, pin.pWidth]; otherSeg _ pin.conctSeg[branchSide]; IF otherSeg # NIL THEN IF otherSeg.trackNum # 0 THEN { otherTrackLoc: Route.Number _ RouteChannel.TrackLoc[routingArea, otherSeg.trackNum]; IF (otherTrackLoc # 0) AND (otherTrackLoc # trackLoc OR otherSeg.routingLayer # segmentLink.routingLayer) THEN { otherSegLength: Route.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 callBack[pin.pinPosition.pLoc, pin.pWidth]; }}}}; }; dogLeg => { segList: RouteChannel.SegmentList _ RouteChannel.GetSegsOnPin[pin]; FOR segs: RouteChannel.SegmentList _ segList, segs.rest WHILE segs # NIL DO seg: RouteChannel.Segment _ segs.first; IF seg.trackNum # 0 THEN { trackLoc: Route.Number _ RouteChannel.TrackLoc[routingArea, 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 callBack[pin.pinPosition.pLoc, pin.pWidth]; }}; ENDLOOP}; exitPin => { seg: RouteChannel.Segment _ pin.conctSeg[segmentSide]; IF seg # NIL THEN IF seg = segmentLink AND seg.trackNum # 0 THEN { layer: Route.Layer _ RouteUtil.RoutingLayerToLayer[routingArea, seg.routingLayer]; exitP: Route.Number _ PinPos[pin]; trackQ: Route.Number _ RouteChannel.TrackLoc[routingArea, seg.trackNum]; exitQ: Route.Number; exitPos: Route.Position; newPin: Route.Pin; IF parms.routerUsed = channel THEN exitQ _ trackQ ELSE { maxQ: Route.Number _ MAX[trackQ+seg.qWidth/2, pin.qLoc+seg.qWidth/2]; minQ: Route.Number _ MIN[trackQ-seg.qWidth/2, pin.qLoc-seg.qWidth/2]; pPos: Route.Number _ExitSegPos[pin, routingArea.rules.trunkWidth]; EnumSegments[routingArea, segmentLink.net.name, segmentLink.net.netPart, RouteUtil.PQToXY[routingArea, [pPos, maxQ]], RouteUtil.PQToXY[routingArea, [pPos, minQ]], routingArea.rules.trunkWidth, layer]; exitQ _ pin.qLoc}; exitPos _ RouteUtil.PQToXY[routingArea, [exitP, exitQ]]; newPin _ BuildPin[routingArea, pin, seg, [exitP, exitQ]]; externalConnections _ CONS[newPin, externalConnections]; EnumExits[routingArea, seg.net.name, seg.net.netPart, exitPos, layer, newPin, seg.exitBreak]}}; ENDCASE}}; trackLoc: Route.Number _ RouteChannel.TrackLoc[routingArea, segmentLink.trackNum]; branchL: Route.Layer _ RouteUtil.RoutingLayerToLayer[routingArea, branch]; lowerMaxQ, upperMaxQ: Route.Number _ trackLoc + segmentLink.qWidth/2; lowerMinQ, upperMinQ: Route.Number _ trackLoc - segmentLink.qWidth/2; lowerBranchWidth, upperBranchWidth: Route.Number _ 0; parms: RoutePrivate.RoutingAreaParms _ NARROW[routingArea.parms]; [] _ RouteChannel.EnumPins[routingArea, branchPos, AnalyzeEachPin]; IF lowerMaxQ > lowerMinQ + segmentLink.qWidth AND lowerBranchWidth > 0 THEN EnumSegments[routingArea, segmentLink.net.name, segmentLink.net.netPart, RouteUtil.PQToXY[routingArea, [branchPos.pLoc, lowerMinQ]], RouteUtil.PQToXY[routingArea, [branchPos.pLoc, lowerMaxQ]], lowerBranchWidth, branchL]; IF upperMaxQ > upperMinQ + segmentLink.qWidth AND upperBranchWidth > 0 AND (lowerMaxQ # upperMaxQ OR lowerMinQ # upperMinQ) THEN EnumSegments[routingArea, segmentLink.net.name, segmentLink.net.netPart, RouteUtil.PQToXY[routingArea, [branchPos.pLoc, upperMinQ]], RouteUtil.PQToXY[routingArea, [branchPos.pLoc, upperMaxQ]], upperBranchWidth, branchL]; branchWidth _ MAX[lowerBranchWidth, upperBranchWidth]; }; -- AnalyzeBranch chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins; nRect: Route.Rect _ CDBasics.NormalizeRect[rect]; pos1: RoutePrivate.PQPosition _ RouteUtil.XYToPQ[routingArea, [nRect.x1, nRect.y1]]; pos2: RoutePrivate.PQPosition _ RouteUtil.XYToPQ[routingArea, [nRect.x2, nRect.y2]]; bottomLoc: Route.Number _ pos1.q - chanData.chanSides[chanBottom].routeAreaCoord; topLoc: Route.Number _ pos2.q; [] _ RouteChannel.EnumTracks[routingArea, EachTrack]; FOR index: RouteChannel.MPinsOnCh IN [1 .. chanPins.count] DO [] _ RouteChannel.EnumPins[routingArea, chanPins.sides[index], EachPin]; ENDLOOP}; BuildPin: PROCEDURE[routingArea: Route.RoutingArea, iPin: RouteChannel.ChanPin, seg: RouteChannel.Segment, pos: RoutePrivate.PQPosition] RETURNS [pin: Route.Pin] = { chanData: RouteChannel.ChannelData _ NARROW[routingArea.privateData]; chanPins: RouteChannel.RoutingChannelPins _ chanData.chanPins; pinName: Rope.ROPE; layer: Route.Layer; loc: Route.Rect; side: Route.Side; cdPin: CD.Instance; p1, p2: Route.Position; p, q, pO, qO: Route.Number; iSide: RouteChannel.ChanSide; IF iPin.pin = NIL THEN { -- this is a constructed pin iSide _ IF pos.p <= chanPins.cEnd1 THEN chanLeft ELSE chanRight; side _ RouteChannel.IntSideToExtSide[routingArea, iSide]; q _ seg.net.trunkWidth/2; p _ routingArea.rules.CDLambda/2; layer _ RouteUtil.RoutingLayerToLayer[routingArea, trunk]; pinName _ seg.net.name} ELSE { -- this exit came from the client iSide _ iPin.pinSide; IF iSide = chanBottom OR iSide = chanTop THEN {p _ iPin.pWidth/2; q _ routingArea.rules.CDLambda/2} ELSE { p _ routingArea.rules.CDLambda/2; q _ seg.net.trunkWidth/2}; side _ RouteChannel.IntSideToExtSide[routingArea, iPin.pinSide]; layer _ RouteUtil.RoutingLayerToLayer[routingArea, iPin.pin.layer]; pinName _ iPin.pin.name}; SELECT iSide FROM chanBottom => {pO _ 0; qO _ q}; chanRight => {pO _ -p; qO _ 0}; chanTop => {pO _ 0; qO _ -q}; chanLeft => {pO _ p; qO _ 0}; ENDCASE; p1 _ RouteUtil.PQToXY[routingArea, [pos.p - p + pO, pos.q - q + qO]]; p2 _ RouteUtil.PQToXY[routingArea, [pos.p + p + pO, pos.q + q + qO]]; loc _ [p1.x, p1.y, p2.x, p2.y]; cdPin _ RouteUtil.CreateCDPin[pinName, loc, layer]; pin _ NEW[Route.PinRec _ [cdPin, side]]; }; RetrieveSegments: PUBLIC RouteChannel.EnumSegmentsProc = { application: CD.Instance; ob: CD.Object; rectSize, position: CD.Position; parms: RoutePrivate.RoutingAreaParms _ NARROW[routingArea.parms]; [position, rectSize] _RouteUtil.LineToRect[pos1, pos2, width]; ob _ CDRects.CreateRect[rectSize, layer]; application _ RouteUtil.Include[parms.object, ob, position]; CDProperties.PutProp[application, $SignalName, name]}; RetrieveVias: PUBLIC RouteChannel.EnumViasProc ={ parms: RoutePrivate.RoutingAreaParms _ NARROW[routingArea.parms]; RouteUtil.AddVia[parms.object, name, pos, size, layer1, layer2, routingArea.rules.CDLambda]}; RetrievePins: PUBLIC RouteChannel.EnumPinsProc = { pinLayer: Route.Layer _ CDSymbolicObjects.GetLayer[pin.pin]; parms: RoutePrivate.RoutingAreaParms _ NARROW[routingArea.parms]; RouteUtil.AddPin[parms.object, pin]; IF pinLayer # layer THEN Route.Signal[errorType: callingError, explanation: "Pin on invalid layer"]}; RetrieveExits: PUBLIC RouteChannel.EnumExitsProc = { pinLayer: Route.Layer _ CDSymbolicObjects.GetLayer[pin.pin]; parms: RoutePrivate.RoutingAreaParms _ NARROW[routingArea.parms]; RouteUtil.AddPin[parms.object, pin]; IF pinLayer # layer THEN Route.Signal[errorType: callingError, explanation: "Channel or switchBox exit on invalid layer"]}; RetrieveIncompletes: PUBLIC RouteChannel.EnumIncompletesProc = {}; 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]; }; }. †RouteChannelRetrieveImpl.mesa ///Route/RouteChannelRetrieveImpl.mesa Bryan Preas February 13, 1986 7:26:57 pm PST Copyright c 1985, 1986 by Xerox Corporation. All rights reserved. by Bryan Preas July 26, 1985 2:29:20 pm PDT last edited by Bryan Preas July 26, 1985 2:29:22 pm PDT Enumerate routing results entities 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 pin is present, look at the segments on the right side a routing failure analyze the branch for this segment problems with dogleg outside pin range analyze component pin branches enumerate this branch segment enumerate the incompletes and audit the segments build a pin record for the external exit Κ ˜šœF™FIcode™,—˜Jšœ Οmœ7™BJšœ.™.Jšœ9™9—J˜šΟk ˜ Jšžœ˜J˜ Jšœ˜Jšœ ˜ J˜J˜Jšœ˜J˜ J˜ Jšœ ˜ J˜—šΟnœžœž˜'JšžœS˜ZJšžœ ˜Jšžœ ˜J˜šŸ œžœž œ ˜Jšœ žœ/˜>Jšœ žœ/˜>Jšœ žœ/˜>šžœžœž˜˜>J˜1J˜TJ˜TJšœQ˜QJšœ˜J˜Jšœ5˜5J™Jšœ0™0šžœžœž˜=JšœH˜HJšžœ˜ ——J˜šŸœž œvžœ˜₯J™(J˜Jšœ%žœ˜EJšœ>˜>Jšœžœ˜Jšœ˜J˜Jšœ˜Jšœžœ ˜Jšœ˜J˜Jšœ˜J˜šžœ žœžœ ˜5Jšœžœžœ žœ ˜@Jšœ9˜9J˜Jšœ!˜!Jšœ:˜:Jšœ˜—šœžœ !˜)Jšœ˜šžœžœž˜-Jšœ5˜5—šžœ˜Jšœ<˜<—Jšœ@˜@JšœC˜CJšœ˜—J˜šžœž˜J˜J˜J˜J˜Jšžœ˜J˜—JšœE˜EJšœE˜EJ˜Jšœ3˜3Jšœžœ˜(Jšœ˜—J˜šŸœžœ"˜:J˜Jšœ žœ ˜Jšœžœ˜Jšœžœ ˜ Jšœ'žœ˜AJšœ>˜>Jšœ)˜)Jšœ=˜=Jšœ6˜6J˜—šŸ œžœ˜1J˜Jšœ'žœ˜AJšœ]˜]J˜—šŸ œžœ˜2J˜Jšœ<˜