GCDetailRouteImpl.mesa
Copyright Ó 1986, 1987 by Xerox Corporation. All rights reserved.
Bryan Preas, February 19, 1987 9:06:53 pm PST
Don Curry January 15, 1988 7:27:49 pm PST
DIRECTORY
CD, CDBasics, CDCells, CDProperties, CDRects, CDSymbolicObjects, Convert, Core, CoreGeometry, CoreOps, DABasics, GC, GCPrivate, IP, IPCTG, IPTop, RefTab, Rope, Route, RTBasic, CoreRouteFlat, Sinix, SinixOps, SymTab;
GCDetailRouteImpl: CEDAR PROGRAM
IMPORTS CD, CDBasics, CDCells, CDProperties, CDRects, CDSymbolicObjects, Convert, CoreGeometry, CoreOps, GC, GCPrivate, IPCTG, Route, RTBasic, RefTab, Rope, CoreRouteFlat, Sinix, SinixOps, SymTab
EXPORTS GCPrivate = BEGIN
Local Types
NetInChan:  TYPE = REF NetInChanRec; -- routing description for a net on a channel
NetInChanRec: TYPE = RECORD [
segmentCount: INT     ← 0,   -- count of existing segments
segsInNet:  LIST OF Segment ← NIL];  -- segments for this net on this channel
Segment:   TYPE = REF SegmentRec;
SegmentRec:  TYPE = RECORD[
name:     Rope.ROPENIL,
trunkSize:   INT   ← 0,
leftOrBottomExit: BOOL   ← FALSE,  -- used for channels only (not SB's)
rightOrTopExit:  BOOL   ← FALSE,  -- used for channels only (not SB's)
pinsInSeg:   LIST OF Pin ← NIL];  -- pins for this net on this channel
Pin:    TYPE = REF PinRec; -- pin description for pins in a net on a channel
PinRec:   TYPE = RECORD[
min:  CD.Number ← 0,
max:  CD.Number ← 0,
depth:  CD.Number ← 0,
layer:  CD.Layer,
side:  DABasics.Side];
DetailRoute
DoDetailRoute: PUBLIC PROC [context: GC.Context] RETURNS [result: GC.Result] = {
Determine actual wiring paths.
MakeChannel: GCPrivate.EachChannelAction ~ {
PROC[context: GC.Context, channel: Channel] RETURNS [quit: BOOLEANFALSE];
construct a channel
InitNet: SymTab.EachPairAction =
{net: CoreRouteFlat.Net ← NARROW[val]; net.any ← NIL};
rulesParameters: Route.DesignRulesParameters ← IF channel.direction = horizontal
THEN context.rules.horizParams
ELSE context.rules.vertParams;
rules: Route.DesignRules ← IF channel.direction = horizontal
THEN context.rules.horizRules
ELSE context.rules.vertRules;
lower, upper: RTBasic.PQPos;
[] ← SymTab.Pairs[context.structure.nets, InitNet];
GCPrivate.AssignCoordinates[context];
lower ← GCPrivate.LowerChannelPQ[channel];
upper ← GCPrivate.UpperChannelPQ[channel];
SELECT TRUE FROM
channel.ch = bottomChannel => {
channel.topOrRightShell ← MakeSide[context, rules, channel, top, TRUE];
channel.bottomOrLeftShell ← MakeSide[context, rules, channel, bottom, FALSE]};
channel.ch = rightChannel => {
channel.bottomOrLeftShell ← MakeSide[context, rules, channel, left, TRUE];
channel.topOrRightShell ← MakeSide[context, rules, channel, right, FALSE]};
channel.ch = topChannel => {
channel.bottomOrLeftShell ← MakeSide[context, rules, channel, bottom, TRUE];
channel.topOrRightShell ← MakeSide[context, rules, channel, top, FALSE]};
channel.ch = leftChannel => {
channel.topOrRightShell ← MakeSide[context, rules, channel, right, TRUE];
channel.bottomOrLeftShell ← MakeSide[context, rules, channel, left, FALSE]};
ENDCASE => {
channel.bottomOrLeftShell ← MakeSide[context, rules, channel, ChanSide[channel, bottom], TRUE];
channel.topOrRightShell ← MakeSide[context, rules, channel, ChanSide[channel, top], TRUE]};
MakeEnd[context, rules, channel, ChanSide[channel, left]]; -- lower end of channel
MakeEnd[context, rules, channel, ChanSide[channel, right]]; -- upper end of channel
channel.intermediateResult ← Route.ChannelRoute[enumerateNets: EnumerateChannelNets, min: lower.p, max: upper.p, rulesParameters: rulesParameters, rules: rules, name: NIL, enumerateObstructions: NIL, channelData: context, optimization: context.parms.opt, signalSinglePinNets: context.parms.signalSinglePinNets];
channel.cdObject ← Route.ChannelRetrieve[intermediateResult: channel.intermediateResult, brokenNets: NIL, channelData: channel, retrieveRect: NIL].object;
channel.width ← IF channel.direction = horizontal THEN CDBasics.SizeOfRect[channel.intermediateResult.routingRect].y
ELSE CDBasics.SizeOfRect[channel.intermediateResult.routingRect].x;
IPCTG.SetWidth[channel.ch, channel.width]};
IncludeChannel: GCPrivate.EachChannelAction ~ {
PROC[context: GC.Context, channel: Channel] RETURNS [quit: BOOLEANFALSE];
Include a previously routed channel into the object being constructed
first the channel
IF channel.cdObject # NIL THEN {
chanInst: CD.Instance;
chanInst ← GCPrivate.IncludeOb[cell: object, ob: channel.cdObject, position: channel.position];
RTBasic.SetCDCellName[channel.cdObject, Rope.Cat[context.name, "Channel", channel.name]];
CDProperties.PutInstanceProp[chanInst, $InstanceName, Rope.Cat["Channel", channel.name]]};
next include the cells containing the wires to get from the channel edges to cells
SELECT TRUE FROM
channel.ch = bottomChannel => {
topPos: CD.Position ← [channel.position.x, channel.position.y + channel.width];
[] ← GCPrivate.IncludeOb[cell: object, ob: channel.topOrRightShell, position: topPos]};
channel.ch = rightChannel => {
bottomPos: CD.Position ← [channel.position.x - CD.InterestSize[channel.bottomOrLeftShell].x, channel.position.y];
[] ← GCPrivate.IncludeOb[cell: object, ob: channel.bottomOrLeftShell, position: bottomPos]};
channel.ch = topChannel => {
bottomPos: CD.Position ← [channel.position.x, channel.position.y - CD.InterestSize[channel.bottomOrLeftShell].y];
[] ← GCPrivate.IncludeOb[cell: object, ob: channel.bottomOrLeftShell, position: bottomPos]};
channel.ch = leftChannel => {
topPos: CD.Position ← [channel.position.x + channel.width, channel.position.y];
[] ← GCPrivate.IncludeOb[cell: object, ob: channel.topOrRightShell, position: topPos]};
ENDCASE => {
topPos: CD.Position ← IF channel.direction = horizontal THEN [channel.position.x, channel.position.y + channel.width]
ELSE [channel.position.x + channel.width, channel.position.y];
bottomPos: CD.Position ← IF channel.direction = horizontal THEN [channel.position.x, channel.position.y - CD.InterestSize[channel.bottomOrLeftShell].y]
ELSE [channel.position.x - CD.InterestSize[channel.bottomOrLeftShell].x, channel.position.y];
[] ← GCPrivate.IncludeOb[cell: object, ob: channel.topOrRightShell, position: topPos];
[] ← GCPrivate.IncludeOb[cell: object, ob: channel.bottomOrLeftShell, position: bottomPos]}};
topology: IPTop.Ref ← NARROW[context.topology];
bottomChannel, rightChannel, topChannel, leftChannel: IPCTG.Channel;
object: CD.Object ← CDCells.CreateEmptyCell[];
[bottomChannel, rightChannel, topChannel, leftChannel] ← IPCTG.GetBoundingChannels[topology.ctg];
[] ← GCPrivate.EnumerateChannelsInTopologicalOrder[context, MakeChannel];
GCPrivate.AssignCoordinates[context];
[] ← GCPrivate.EnumerateChannelsInTopologicalOrder[context, IncludeChannel];
FOR insts: LIST OF CoreRouteFlat.Instance ← context.structure.instances, insts.rest
WHILE insts#NIL DO
IF insts.first.layObject # NIL THEN {
cdInst: CD.Instance ← GCPrivate.IncludeOb
[object, insts.first.layObject, insts.first.position, insts.first.orientation];
CDProperties.PutInstanceProp[cdInst, $InstanceName, insts.first.name]} ENDLOOP;
RTBasic.RepositionCell[object];
result ← NEW[GC.ResultRec ← [context: context, object: object]]};
Construction Utilities
MakeSide: PROC [context: GC.Context, rules: Route.DesignRules, channel: GCPrivate.Channel, chanSide: RTBasic.Side, internal: BOOLEAN] RETURNS [shell: CD.Object ← CDCells.CreateEmptyCell[]] ~ {
construct a shell for the chanSide of a channel and insert global routing info for this channel
DoExternalPins: IPCTG.EachComponentAction ~ {
PROC[co: Component] RETURNS[quit: BOOLFALSE];
add the external pins accross the channel for boundry channels
IF co # NIL THEN {
instance: CoreRouteFlat.Instance ← NARROW[co.any];
FOR nns: LIST OF CoreRouteFlat.NetONode ← instance.netONodes, nns.rest
WHILE nns#NIL DO
IF ~ExternalNet[context.structure, nns.first.net] THEN LOOP;
FOR pins: LIST OF CoreRouteFlat.Pin ← nns.first.oNode.pins, pins.rest
WHILE pins#NIL DO
IF pins.first.side = otherSide AND internal OR pins.first.side = chanSide AND ~internal
THEN {
netDesc: GCPrivate.NetDesc  ← NARROW
[RefTab.Fetch[channel.connections, nns.first.net].val];
phyPin: GCPrivate.PhyPinDesc ← NEW[GCPrivate.PhyPinDescRec ←
[instance, nns.first.oNode, pins.first]];
tabIndex: Rope.ROPEIF GCPrivate.PinOnList[netDesc, phyPin]
THEN nns.first.net.name
ELSE Rope.Cat[nns.first.net.name, "@", instance.name, "@",
Convert.RopeFromInt[pins.first.range.min]];
netDat: NetInChan ← IF nns.first.net.any = NIL
THENNEW[NetInChanRec]
ELSENARROW[nns.first.net.any];
range: CoreRouteFlat.Range ← CoreRouteFlat.TranslateRange[instance, pins.first];
AddPin[nns.first.net, netDat, tabIndex, range, rules.branchLayer, chanSide,0];
maxWidth ← MAX[maxWidth, IncludePin[
phyPin: NEW[GCPrivate.PhyPinDescRec ←
[instance, nns.first.oNode, pins.first]],
name:  tabIndex,
side:  chanSide,
lower:  lower,
upper: upper,
shell:  shell ] ] };
ENDLOOP;
ENDLOOP } };
EachNet: RefTab.EachPairAction ~ {
PROC [key: Key, val: Val] RETURNS [quit: BOOLFALSE];
add the pins from the nets
netDesc: GCPrivate.NetDesc ← NARROW[val];
FOR list: LIST OF GCPrivate.PhyPinDesc ← netDesc.pinList, list.rest WHILE list # NIL DO
net: CoreRouteFlat.Net ← NARROW[key];
exteriorPublic: BOOLEANIPCTG.IsBoundingChannel[topology.ctg, channel.ch] AND ExternalNet[context.structure, net]; -- External pins already included
phyPin: GCPrivate.PhyPinDesc ← list.first;
IF phyPin.pPin.side = otherSide AND ~exteriorPublic THEN {
netDat: NetInChan ← IF net.any = NIL
THENNEW[NetInChanRec]
ELSENARROW[net.any];
range: CoreRouteFlat.Range ← CoreRouteFlat.TranslateRange
[phyPin.instance, phyPin.pPin];
AddPin[net, netDat, net.name, range, rules.branchLayer, chanSide, 0];
maxWidth ← MAX[maxWidth, IncludePin
[list.first, net.name, chanSide, lower, upper, shell]]};
ENDLOOP};
DoChannelIntersection: IPCTG.EachIntersectionAction ~ {
PROC[i: Intersection] RETURNS[quit: BOOLFALSE];
add the pins from the channel intersections
EachExit: PublicEnumerator ~ {
[name: Rope.ROPE, min, max: INT, side: DABasics.Side, layer: CD.Layer] RETURNS [quit: BOOLFALSE]
net: CoreRouteFlat.Net ← NARROW[SymTab.Fetch[context.structure.nets, name].val];
IF (internal AND side = otherSide) OR
(~internal AND ExternalNet[context.structure, net] AND side = chanSide) THEN {
range: CoreRouteFlat.Range ← SELECT chanSide FROM
bottom, top => [otherChannel.position.x + min, otherChannel.position.x + max],
left, right => [otherChannel.position.y + min, otherChannel.position.y + max],
ENDCASE => GC.Error[programmingError, "Call maintainer"];
netDat: NetInChan ← IF net.any = NIL THEN NEW[NetInChanRec] ELSE NARROW[net.any];
AddPin[net, netDat, name, range, rules.branchLayer, chanSide, 0]}};
otherChannel: GCPrivate.Channel ← NARROW[i.ch.any];
[] ← EnumerateEdgePins[context, otherChannel, EachExit]};
rect:    CD.Rect;
maxWidth:  INT    ← rules.branchWidth;
otherSide:   RTBasic.Side  ← RTBasic.OtherSide[chanSide];
bottomOrLeft: BOOLEAN   ← chanSide = bottom OR chanSide = left;
topOrRight:  BOOLEAN   ← ~bottomOrLeft;
lower:    RTBasic.PQPos ← GCPrivate.LowerChannelPQ[channel];
upper:   RTBasic.PQPos ← GCPrivate.UpperChannelPQ[channel];
topology:   IPTop.Ref   ← NARROW[context.topology];
polarity: IP.PolarityTypes ← IF (internal AND bottomOrLeft) OR (~internal AND topOrRight) THEN neg ELSE pos;
IF IPCTG.IsBoundingChannel[topology.ctg, channel.ch]
THEN [] ← IPCTG.Components[channel.ch, polarity, DoExternalPins];
[] ← RefTab.Pairs[channel.connections, EachNet];
[] ← IPCTG.Intersections[channel.ch, polarity, DoChannelIntersection];
IF channel.lowerIntType = inverted
THEN [] ← DoChannelIntersection[IPCTG.End[channel.ch, neg]];
IF channel.upperIntType = inverted
THEN [] ← DoChannelIntersection[IPCTG.End[channel.ch, pos]];
rect ← SELECT chanSide FROM
bottom => [lower.p, lower.q - maxWidth, upper.p, lower.q],
right  => [upper.q, lower.p, upper.q + maxWidth, upper.p],
top  => [lower.p, upper.q, upper.p, upper.q + maxWidth],
left  => [lower.q - maxWidth, lower.p, lower.q, upper.p],
ENDCASE => GC.Error[programmingError, "Call maintainer"];
CDCells.SetInterestRect[design: NIL, cell: shell, r: rect]; -- set interestRect of shell
RTBasic.RepositionCell[shell]};
MakeEnd: PROC [context: GC.Context, rules: Route.DesignRules, channel: GCPrivate.Channel, side: RTBasic.Side] ~ {
construct the end object of a channel
EachNet: RefTab.EachPairAction ~ {
PROC [key: Key, val: Val] RETURNS [quit: BOOLEANFALSE];
netDesc: GCPrivate.NetDesc ← NARROW[val];
net: CoreRouteFlat.Net ← NARROW[key];
publicNet: BOOLEAN ← CoreRouteFlat.IsPublic[net];
needsExit: BOOLEAN ← (side = bottom OR side = left) AND netDesc.bottomOrLeftExit OR (side = top OR side = right) AND netDesc.topOrRightExit;
IF needsExit AND (ordinaryIntersection OR publicNet) THEN {
netDat: NetInChan ← IF net.any = NIL THEN NEW[NetInChanRec] ELSE NARROW[net.any];
AddEnd[net, netDat, net.name, side, 0]}};
ordinaryIntersection: BOOLEAN ← (channel.lowerIntType = normal AND (side = left OR side = bottom)) OR (channel.upperIntType = normal AND (side = right OR side = top));
[] ← RefTab.Pairs[channel.connections, EachNet]};
SideToOrientation: PROC [side: RTBasic.Side] RETURNS [orientation: CD.Orientation] ~ {
translate a side to an orientation
orientation ← SELECT side FROM
top  => CDSymbolicObjects.OrientFromDirection[south],
left  => CDSymbolicObjects.OrientFromDirection[east],
bottom => CDSymbolicObjects.OrientFromDirection[north],
right  => CDSymbolicObjects.OrientFromDirection[west],
ENDCASE => GC.Error[programmingError, "Call maintainer"]};
ChanSide: PROC [channel: GCPrivate.Channel, side: DABasics.Side] RETURNS [sideToUse: DABasics.Side] ~ {
sideToUse ← IF channel.direction = horizontal THEN side
ELSE SELECT side FROM
bottom => left,
right  => top,
top  => right,
left  => bottom,
ENDCASE => GC.Error[programmingError, "Call maintainer"]};
ExternalNet: PROC [struc: CoreRouteFlat.Structure, net: CoreRouteFlat.Net]
RETURNS [isExternal: BOOLEANFALSE] ~ {
FOR nns: LIST OF CoreRouteFlat.NetONode ← struc.outerInstance.netONodes, nns.rest
WHILE nns#NIL DO IF nns.first.oNode.public THEN RETURN[TRUE] ENDLOOP};
IncludePin: PROC [phyPin: GCPrivate.PhyPinDesc, name: Rope.ROPE, side: RTBasic.Side, lower, upper: RTBasic.PQPos, shell: CD.Object] RETURNS[width: INT]~ {
include a pin in a shell; also extend a wire if necessary
instance:  CoreRouteFlat.Instance ← phyPin.instance;
pPin:   CoreRouteFlat.Pin  ← phyPin.pPin;
range:   CoreRouteFlat.Range ← CoreRouteFlat.TranslateRange[instance, pPin];
rangeSize: INT ← range.max - range.min;
wireLoc:  CD.Position;
wireSize:  CD.Position;
SELECT side FROM
top => {
width  ← instance.position.y - upper.q; -- + pPin.depth
wireSize ← [rangeSize, width];
wireLoc ← [range.min, upper.q]};
left => {
sidePos: INT ← instance.position.x + CD.InterestSize[instance.layObject].x;
width  ← lower.q - sidePos; -- + pPin.depth;
wireSize ← [width, rangeSize];
wireLoc ← [sidePos -- -pPin.depth--, range.min]};
bottom => {
sidePos: INT ← instance.position.y + CD.InterestSize[instance.layObject].y;
width  ← lower.q - sidePos; -- + pPin.depth;
wireSize ← [rangeSize, width];
wireLoc ← [range.min, sidePos -- -pPin.depth--]};
right => {
width  ← instance.position.x - upper.q; -- + pPin.depth;
wireSize ← [width, rangeSize];
wireLoc ← [upper.q, range.min]};
ENDCASE;
IF width # 0 THEN {
wire: CD.Object ← CDRects.CreateRect[wireSize, pPin.layer];
CDProperties.PutProp[wire, $SignalName, name];
[] ← GCPrivate.IncludeOb[cell: shell, ob: wire, position: wireLoc]}};
Routing Area Manipulation
EnumerateEdgePins: PROC [context: GC.Context, channel: GCPrivate.Channel, eachEdgeEntity: PublicEnumerator] RETURNS [quit: BOOLFALSE] ~ {
apply EachEdgeEntity to entities of ob
HACK, This needs to enumerate routing class entries directly
ChanPublics: CoreGeometry.EachWirePinProc ~ {
PROC [wire: Wire, min, max: INT, side: Side, layer: CD.Layer] RETURNS [quit: BOOLFALSE];
quit ← eachEdgeEntity[CoreOps.GetShortWireName[wire], min, max, side, layer]};
mode: Sinix.Mode = SinixOps.GetExtractMode[context.rules.technology];
cellType: Core.CellType ← NARROW [Sinix.Extract[channel.cdObject, mode].result];
[] ← CoreGeometry.EnumerateNonOverlappingSides[mode.decoration, cellType, ChanPublics]};
PublicEnumerator: TYPE = PROC[name: Rope.ROPE, min, max: INT, side: DABasics.Side, layer: CD.Layer] RETURNS [quit: BOOLFALSE];
Detail Route Entry
AddPin: PROC [net: CoreRouteFlat.Net, netDat: NetInChan, name: Rope.ROPE, range: CoreRouteFlat.Range, layer: CD.Layer, side: DABasics.Side, trunkWidth: INT] ~ {
add a pin to the appropriate segment in net
pin: Pin ← NEW[PinRec ← [min: range.min, max: range.max, --depth: 0,-- layer: layer, side: side]];
segment: Segment ← LookUpSegment[netDat, name];
segment.pinsInSeg ← CONS[pin, segment.pinsInSeg];
segment.trunkSize ← trunkWidth;
net.any ← netDat};
AddEnd: PROC [net: CoreRouteFlat.Net, netDat: NetInChan, name: Rope.ROPE, side: DABasics.Side, trunkWidth: INT] ~ {
add a channel end connection
segment: Segment ← LookUpSegment[netDat, name];
SELECT side FROM
bottom, left => segment.leftOrBottomExit ← TRUE;
right, top  => segment.rightOrTopExit ← TRUE;
ENDCASE;
segment.trunkSize ← trunkWidth;
net.any ← netDat};
LookUpSegment: PROC [netDat: NetInChan, name: Rope.ROPE] RETURNS [segment: Segment ← NIL] ~ {
find an existing segment by name; if none, make a NEW one
FOR segList: LIST OF Segment ← netDat.segsInNet, segList.rest WHILE segList # NIL AND segment = NIL DO
IF Rope.Equal[segList.first.name, name] THEN segment ← segList.first;
ENDLOOP;
IF segment = NIL THEN { -- not found, make a NEW one
segment ← NEW[SegmentRec ← [name: name]];
netDat.segmentCount ← netDat.segmentCount + 1;
netDat.segsInNet ← CONS[segment, netDat.segsInNet]}};
Router Callbacks
EnumerateChannelNets: Route.EnumerateChannelNetsProc ~ {
PROC [channelData: REF, eachNet: EachChannelNetProc];
ChannelNet: SymTab.EachPairAction ~ {
net: CoreRouteFlat.Net ← NARROW[val];
IF net.any # NIL THEN {
netDat: NetInChan ← NARROW[net.any];
FOR segs: LIST OF Segment ← netDat.segsInNet, segs.rest UNTIL segs = NIL DO
seg: Segment ← segs.first;
eachNet[name: seg.name,
enumeratePins:  ChannelSignalPins,
exitLeftOrBottom: seg.leftOrBottomExit,
exitRightOrTop:  seg.rightOrTopExit,
trunkSize:   seg.trunkSize,
channelData:   channelData,
netData:    seg];
ENDLOOP}};
structure: CoreRouteFlat.Structure ← NARROW[channelData, GC.Context].structure;
[] ← SymTab.Pairs[structure.nets, ChannelNet]};
ChannelSignalPins: Route.EnumerateChannelPinsProc ~ {
PROC [channelData, netData: REF, eachPin: EachChannelPinProc];
seg: Segment ← NARROW[netData];
FOR pins: LIST OF Pin ← seg.pinsInSeg, pins.rest UNTIL pins = NIL DO
pin: Pin ← pins.first;
bottomOrLeftSide: BOOL ← pin.side = bottom OR pin.side = left;
eachPin[bottomOrLeftSide: bottomOrLeftSide, min: pin.min, max: pin.max, --depth: pin.depth,-- layer: pin.layer];
ENDLOOP};
END.