RouteChannelRetrieveImpl.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
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] = {
Enumerate routing results entities
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] = {
analyze the branch for this segment
problems with dogleg outside pin range
AnalyzeEachPin: RouteChannel.EachPinActionProc = {
PROC[pinPosition: PinPosition, pin: ChanPin] RETURNS [quit: BOOLEAN ← FALSE];
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, 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, intervalList];
};
};
};
};
};
dogLeg => {
segList: RouteChannel.SegmentList ← RouteChannel.GetSegsOnPin[pin];
check if dogleg spans more than one track
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 {
dogleg spans at least two tracks, put it in
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, 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;
analyze component pin branches
[] ← RouteChannel.EnumPins[branchPos, AnalyzeEachPin];
enumerate this branch segment
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 = {
run through the segments on the track
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];
audit the pins to which this segment point
RouteChannel.CheckPins[seg, leftPin, chanRight];
RouteChannel.CheckPins[seg, rightPin, chanLeft];
figure out the left branch
[leftBranchWidth, intervalList] ← AnalyzeBranch[seg.exteriorPins[chanLeft].pinPosition, seg, name, chanLeft, chanRight, intervalList];
process the interior pins
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;
do the right branch if no following segment in this track
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];
do the vias collected during the AnalyzeBranch Calls
DoVias[chanTracks, parms, rules, enumVias, seg, name, intervalList];
enumerate trunk segment
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 = {
PROC[pinPosition: PinPosition, pin: ChanPin] RETURNS [quit: BOOLEAN ← FALSE];
IF pin # NIL THEN
IF pin.kindOfPin # noPin THEN {
pin is present, look at the segments on the right side
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 {
a routing failure
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];
enumerate the incompletes and audit the segments
FOR index: RouteChannel.MPinsOnCh IN [1 .. chanPins.count] DO
[] ← RouteChannel.EnumPins[chanPins.sides[index], EachPin];
ENDLOOP
};
AddInterval: PROC [pos, size: 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;
IF RTBasic.Overlaps[thisRange, currentRange] 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 = {
Call back for wiring segments
TYPE = PROCEDURE[
parms: RoutePrivate.RoutingAreaParms,
name: Rope.ROPE,
pos1, pos2: DABasics.Position,
width: DABasics.Number,
layer: CD.Layer];
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 ={
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];
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 = {
TYPE = PROCEDURE[
parms: RoutePrivate.RoutingAreaParms,
name: Rope.ROPE,
pos1, pos2: DABasics.Position];
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] ~ {
add placedObj to the appropriate list
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."];
};
};
}.