DIRECTORY CD, CDBasics, CDSymbolicObjects, CDRects, HashTable, PWObjects, Rope, Route, RouteChannel, RoutePrivate, RouteUtil; RouteChannelRetrieveImpl: CEDAR PROGRAM IMPORTS CDBasics, CDSymbolicObjects, CDRects, HashTable, 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.ReInterpreteRect[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 = { cell: CD.Object; rectSize, position: CD.Position; parms: RoutePrivate.RoutingAreaParms _ NARROW[routingArea.parms]; [position, rectSize] _RouteUtil.LineToRect[pos1, pos2, width]; cell _ CDRects.CreateRect[rectSize, layer]; AddToList[parms.entityTable, name, [cell, position]]; }; RetrieveVias: PUBLIC RouteChannel.EnumViasProc ={ parms: RoutePrivate.RoutingAreaParms _ NARROW[routingArea.parms]; cell: Route.Object _ RouteUtil.StitchVias[size, layer1, layer2, routingArea.rules.CDLambda, 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]]; }; 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]; }; PlOs: TYPE = REF PlORec; PlORec: TYPE = RECORD[ list: LIST OF REF PWObjects.PlacedObject _ NIL]; AddToList: PROC [table: HashTable.Table, key: HashTable.Key, placedObj: PWObjects.PlacedObject] ~ { value: HashTable.Value _ HashTable.Fetch[table, key].value; geometry: PlOs = IF value = NIL THEN NEW[PlORec] ELSE NARROW [value, PlOs]; geometry.list _ CONS[NEW[PWObjects.PlacedObject _ placedObj], geometry.list]; [] _ HashTable.Store[table, key, geometry]}; }. NRouteChannelRetrieveImpl.mesa Bryan Preas February 5, 1987 7:46:00 pm PST Copyright c 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 December 18, 1986 2:57:09 pm PST 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 Call back for wiring segments TYPE = PROCEDURE[ routingArea: Route.RoutingArea, name: Rope.ROPE, netPart: NAT, pos1, pos2: Route.Position, width: Route.Number, layer: Route.Layer]; application _ RouteUtil.Include[parms.object, ob, position]; CDProperties.PutProp[application, $SignalName, name]}; Call back for branch ends TYPE = PROCEDURE[ routingArea: Route.RoutingArea, name: Rope.ROPE, netPart: NAT, pos, size: Route.Position, rectangle of size centered on pos layer1, layer2: Route.Layer]; RouteUtil.AddVia[parms.object, name, pos, size, layer1, layer2, routingArea.rules.CDLambda]}; Call back for channel pins TYPE = PROCEDURE[ routingArea: Route.RoutingArea, name: Rope.ROPE, netPart: NAT, pos: Route.Position, layer: Route.Layer, pin: Route.Pin]; Call back for channel exits TYPE = PROCEDURE[ routingArea: Route.RoutingArea, name: Rope.ROPE, netPart: NAT, pos: Route.Position, layer: Route.Layer, pin: Route.Pin, constructedExit: BOOLEAN]; add placedObj to the appropriate list Κ j˜codešœ™Kšœ Οk™+—˜Kšœ Οmœ=™HKšœ*œ™.Kšœ:™=—K˜š ˜ Kšœq˜sK˜—šΟnœœ˜'KšœP˜WKšœ ˜Kšœ ˜K˜šŸ œœ œ ˜Kšœ œ/˜>Kšœ œ/˜>Kšœ œ/˜>šœœ˜˜>Kšœ4˜4K˜TK˜TKšœQ˜QKšœ˜K˜Kšœ5˜5K˜K™Kšœ0™0šœœ˜=KšœH˜HKšœ˜ ——K˜šŸœ œvœ˜₯K™(K˜Kšœ%œ˜EKšœ>˜>Kšœœ˜Kšœ˜K˜Kšœ˜Kšœœ ˜Kšœ˜K˜Kšœ˜K˜šœ œœ ˜5Kšœœœ œ ˜@Kšœ9˜9K˜Kšœ!˜!Kšœ:˜:Kšœ˜—šœœ !˜)Kšœ˜šœœ˜-Kšœ5˜5—šœ˜Kšœ<˜<—Kšœ@˜@KšœC˜CKšœ˜—K˜šœ˜K˜K˜K˜K˜Kšœ˜K˜—KšœE˜EKšœE˜EK˜Kšœ3˜3Kšœœ˜(Kšœ˜—K˜šŸœœ"˜:Kšœ™šœ™Kšœ™Kšœ™Kšœ™Kšœ™Kšœ™Kšœ™K˜—Kšœœ˜Kšœœ ˜ Kšœ'œ˜AKšœ>˜>Kšœ+˜+Kšœ5˜5K˜Kšœ=™=Kšœ6™6K˜K˜—šŸ œœ˜1Kšœ™šœ™Kšœ™Kšœ™Kšœ™Kšœ@™@Kšœ™—K˜Kšœ'œ˜AKšœl˜lKšœ œ+˜7Kšœ œ9˜EKšœ5˜5K˜Kšœ]™]K˜K˜—šŸ œœ˜2Kšœ™šœ™Kšœ™Kšœ™Kšœ™Kšœ™Kšœ™Kšœ™—K˜Kšœ<˜