SCNewRouteImpl.mesa: Implements of SC.DetailedRoute
Copyright © 1986, 1987 by Xerox Corporation. All rights reserved.
Frank Bowers June 3, 1986 10:58:48 am PDT
Last Edited by: Bryan Preas August 12, 1987 4:08:01 pm PDT
Christian Le Cocq December 2, 1987 3:00:23 pm PST
Jean-Marc Frailong October 14, 1987 5:47:12 pm PDT
DIRECTORY
CD, CDCells, CDOps, CDProperties, Convert, Core, CoreGeometry, CoreOps, CoreRoute, DABasics, Rope, Route, RouteUtil, RTBasic, SC, SCChanUtil, SCInstUtil, SCNetUtil, SCPrivate, SCNewRoutePinsUtil, SCRowUtil, SCUtil, Sinix;
SCNewRouteImpl: CEDAR PROGRAM
IMPORTS CDCells, CDOps, CDProperties, Convert, CoreGeometry, CoreOps, CoreRoute, Rope, Route, RouteUtil, RTBasic, SC, SCChanUtil, SCInstUtil, SCNetUtil, SCNewRoutePinsUtil, SCRowUtil, SCUtil
EXPORTS SCPrivate
SHARES SC = BEGIN
keepStats: BOOL ← FALSE; -- should be FALSE for production; TRUE enables collection of detailed statistics
Detail Route Operation
DetailRoute: PUBLIC PROC [handle: SC.Handle] RETURNS [result: SC.Result] = {
object: CD.Object;
stats: LIST OF SC.ChannelStats ← NIL;
lgRows: SCPrivate.LgRows ← NARROW[handle.layoutData, SCPrivate.LayoutData].lgRows;
SCInstUtil.AllOffsets[handle];
[lgRows.maxRowWidth, lgRows.numMaxRows] ← SCRowUtil.FindMaxRow[handle];
[object, stats] ← RouteChannels[handle];
result ← NEW[SC.ResultRec ← [handle: handle, object: object, stats: stats]];
SCInstUtil.AsgnChanPos[handle];
[] ← SCUtil.WriteResults["End detailed routing\n", handle, 0]};
Construct The Rows
ConstructRow: PROC [handle: SC.Handle, lgRow: SCPrivate.LgRow] RETURNS [row: CD.Object ← CDCells.CreateEmptyCell[]] ~ {
LeftEnumerateSegments: PROC [eachSegment: PROC [CoreRoute.Segment]] ~ {
enumerate public wires for left side of row
EachWirePin: CoreGeometry.EachWirePinProc = {
PROC [wire: Wire, min, max: INT, side: Side, layer: CD.Layer] RETURNS [quit: BOOL ← FALSE];
IF side=left THEN eachSegment[[label: CoreOps.GetShortWireName[wire], min: min, max: max, layer: layer]]};
[] ← CoreGeometry.EnumerateWireSides[mode.decoration, lgRow.lgsOnRow[1].object.cellType, EachWirePin]};
RightEnumerateSegments: PROC [eachSegment: PROC [CoreRoute.Segment]] ~ {
enumerate public wires for right side of row
EachWirePin: CoreGeometry.EachWirePinProc = {
PROC [wire: Wire, min, max: INT, side: Side, layer: CD.Layer] RETURNS [quit: BOOL ← FALSE];
IF side=right THEN eachSegment[[label: CoreOps.GetShortWireName[wire], min: min, max: max, layer: layer]]};
[] ← CoreGeometry.EnumerateWireSides[mode.decoration, lgRow.lgsOnRow[lgRow.nLgsOnRow].object.cellType, EachWirePin]};
ForEachInstance: SCRowUtil.EachInstProc = {
[pos: NAT, instance: SCPrivate.Instance] RETURNS [quit: BOOL ← FALSE]
LabelProc: PROC [pinName: Rope.ROPE] RETURNS [label: Route.Label ← NIL] ~ {
find label for this pin
EachPin: SCInstUtil.EachPinProc ~ {
PROC [instance: SCPrivate.Instance, pin: NAT, netPin: SCPrivate.PinNet] RETURNS [quit: BOOL ← FALSE];
IF Rope.Equal[netPin.pin.name, pinName] THEN {
label ← netPin.net.name; quit ← TRUE;
};
};
IF SCUtil.IsPowerName[handle, pinName] THEN label ← pinName
ELSE IF ~SCInstUtil.EnumeratePinsOnInst[instance: instance, eachPin: EachPin] THEN
SC.Signal[callingError, "FeedThrough definition in library does not have all rectangles marked."]};
instOrientation: CD.Orientation ← SCInstUtil.CDOrien[instance];
object: CD.Object ← IF (instance.whichClass = ft) OR (instance.object = parms.vddObject) OR (instance.object = parms.gndObject) THEN CoreRoute.MakeRoutingCell[instance.object.cdOb, LabelProc]
ELSE instance.object.cdOb;
instPosition: CD.Position ← CDOps.FitObjectI[ob: object, location: [offset, 0], orientation: instOrientation].off;
cdInst: CD.Instance ← RouteUtil.Include[cell: row, ob: object, position: instPosition, orientation: instOrientation];
CDProperties.PutInstanceProp[cdInst, $InstanceName, instance.name];
offset ← offset + RTBasic.IRSize[object].x};
parms: SCPrivate.Parms = NARROW [handle.parms];
mode: Sinix.Mode = parms.mode;
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
maxRowWidth: CD.Number ← layoutData.lgRows.maxRowWidth;
rowLength: SC.Number ← lgRow.size.p;
rowOffset: SC.Number ← lgRow.rowOrg.p - layoutData.lgRows.horzRowOrg;
offset: SC.Number ← 0;
IF rowOffset > 0 THEN {
leftObject: CD.Object ← CoreRoute.ExtendObject[enumerateSegments: LeftEnumerateSegments, size: [rowOffset, lgRow.size.q], side: left, extendProc: CoreRoute.ExtendSegment];
[] ← RouteUtil.Include[cell: row, ob: leftObject, position: [offset, 0]];
offset ← offset + RTBasic.IRSize[leftObject].x};
[] ← SCRowUtil.EnumerateAllInstsOnRow[handle, lgRow.rowNum, ForEachInstance];
IF rowOffset + rowLength < maxRowWidth THEN {
rightObject: CD.Object ← CoreRoute.ExtendObject[enumerateSegments: RightEnumerateSegments, size: [maxRowWidth - (rowOffset + rowLength), lgRow.size.q], side: right, extendProc: CoreRoute.ExtendSegment];
[] ← RouteUtil.Include[cell: row, ob: rightObject, position: [offset, 0]];
offset ← offset + RTBasic.IRSize[rightObject].x};
RTBasic.RepositionCell[row]};
Route The Channels
RouteChannels: PROC [handle: SC.Handle] RETURNS [obj: CD.Object ← CDCells.CreateEmptyCell[], stats: LIST OF SC.ChannelStats ← NIL] ~ {
route the channels and include rows and channels into the layout
RouteChannel: PROC [enumerateNets: Route.EnumerateChannelNetsProc, rowChan: SCPrivate.RowChan] ~ {
route the specified channeland include in the object being constructed
BrokenNet: Route.BrokenNetProc ~ {
PROC [netData: REF, sourceNet: Label, regionNumber, numberOfRegions: NAT] RETURNS [newLabel: Label];
net: SCPrivate.Net ← NARROW[netData];
IF NOT net.externNet THEN newLabel ← NIL
ELSE {
net.numberOfRegions ← net.numberOfRegions + 1;
newLabel ← CoreRoute.LabelBrokenNet[net.name, net.numberOfRegions];
net.brokenNets ← CONS[newLabel, net.brokenNets]}};
channel: CD.Object ← Route.Channel[enumerateNets: enumerateNets, min: lgRows.horzRowOrg, max: lgRows.horzRowOrg + lgRows.maxRowWidth, rulesParameters: handle.rules.rowParms, name: Rope.Cat[handle.name, "Chan", Convert.RopeFromInt[rowChan.chanNum]], brokenNets: BrokenNet, channelData: handle].object;
[] ← RouteUtil.Include[cell: obj, ob: channel, position: [0, offset]];
offset ← offset + RTBasic.IRSize[channel].y;
rowChan.chanWidth ← RTBasic.IRSize[channel].y};
EachChannel: SCChanUtil.EachRowChanProc ~ {
[chan: SCPrivate.MaxChanSr, rowChan: SCPrivate.RowChan] RETURNS [quit: BOOL ← FALSE]
route the channel specified by rowChan
LowerChannel: Route.EnumerateChannelNetsProc ~ {
PROC [eachNet: EachChannelNetProc];
LowerChannelNet: SCNetUtil.EachNetProc ~ {
PROC [net: SCPrivate.Net] RETURNS [quit: BOOL ← FALSE];
leftExit: BOOL ← net.chanExits[left][rowChan.chanNum-1];
rightExit: BOOL ← net.chanExits[right][rowChan.chanNum-1];
IF net.pinsOnChan # NIL OR leftExit OR rightExit THEN {
eachNet[name: net.name,
enumeratePins: LowerChannelPins,
exitLeftOrBottom: leftExit,
exitRightOrTop: rightExit,
trunkSize: net.trunkWidth,
netData: net]}};
[] ← SCNetUtil.EnumerateNets[handle, LowerChannelNet]};
InteriorChannel: Route.EnumerateChannelNetsProc ~ {
PROC [eachNet: EachChannelNetProc];
InteriorChannelNet: SCNetUtil.EachNetProc ~ {
PROC [net: SCPrivate.Net] RETURNS [quit: BOOL ← FALSE];
leftExit: BOOL ← net.chanExits[left][rowChan.chanNum-1];
rightExit: BOOL ← net.chanExits[right][rowChan.chanNum-1];
IF net.pinsOnChan # NIL OR leftExit OR rightExit THEN {
eachNet[name: net.name,
enumeratePins: InteriorChannelPins,
exitLeftOrBottom: leftExit,
exitRightOrTop: rightExit,
trunkSize: net.trunkWidth,
netData: net]}};
[] ← SCNetUtil.EnumerateNets[handle, InteriorChannelNet]};
LowerChannelPins: Route.EnumerateChannelPinsProc ~ {
PROC [netData: REF, eachPin: EachChannelPinProc];
net: SCPrivate.Net ← NARROW[netData];
pinList: LIST OF Route.Pin ← NARROW[net.pinsOnChan];
FOR pins: LIST OF Route.Pin ← pinList, pins.rest UNTIL pins = NIL DO
pin: Route.Pin ← pins.first;
bottomOrLeftSide: BOOL ← pin.side = bottom;
xfer: BOOLEAN ← net.externNet AND SCNetUtil.ExitOnSide[handle, net, bottom] AND pin.side = top;
eachPin[bottomOrLeftSide: bottomOrLeftSide, min: pin.min, max: pin.max, depth: pin.depth, layer: pin.layer];
IF xfer THEN eachPin[bottomOrLeftSide: ~bottomOrLeftSide, min: pin.min, max: pin.max, depth: pin.depth, layer: pin.layer];
ENDLOOP};
InteriorChannelPins: Route.EnumerateChannelPinsProc ~ {
PROC [netData: REF, eachPin: EachChannelPinProc];
net: SCPrivate.Net ← NARROW[netData];
pinList: LIST OF Route.Pin ← NARROW[net.pinsOnChan];
FOR pins: LIST OF Route.Pin ← pinList, pins.rest UNTIL pins = NIL DO
pin: Route.Pin ← pins.first;
bottomOrLeftSide: BOOL ← pin.side = bottom;
eachPin[bottomOrLeftSide: bottomOrLeftSide, min: pin.min, max: pin.max, depth: pin.depth, layer: pin.layer];
ENDLOOP};
GlobalRouteChannel[handle, rowChan];
IF chan # 1 THEN { -- include the specified row in the object being constructed
[] ← RouteUtil.Include[cell: obj, ob: ConstructRow[handle, lgRows.rows[chan-1]], position: [0, offset]];
offset ← offset + lgRows.rows[chan-1].size.q};
IF chan = 1 AND rowChans.count = 2 THEN {
do the bottom channel if it is the only one
IF keepStats THEN
stats ← CONS[NEW[SC.ChannelStatsRec ← [channel: chan, netStats: LowerChannelNetStats[handle, rowChan]]], stats];
RouteChannel[LowerChannel, rowChan]};
IF chan # rowChans.count AND chan # 1 THEN {
do the interior channels
IF keepStats THEN
stats ← CONS[NEW[SC.ChannelStatsRec ← [channel: chan, netStats: InteriorChannelNetStats[handle, rowChan]]], stats];
RouteChannel[InteriorChannel, rowChan]}};
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
rowChans: SCPrivate.RowChans ← layoutData.rowChans;
lgRows: SCPrivate.LgRows ← layoutData.lgRows;
offset: SC.Number ← 0;
[] ← SCChanUtil.EnumerateRowChans[handle, EachChannel];
RTBasic.SetCDCellName[obj, handle.name];
RTBasic.RepositionCell[obj]};
GlobalRouteChannel: PROC [handle: SC.Handle, rowChan: SCPrivate.RowChan] ~ {
collect the pins that are to be connected for this channel
InitNet: SCNetUtil.EachNetProc = {net.pinsOnChan ← NIL};
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
rowChans: SCPrivate.RowChans ← layoutData.rowChans;
useThisChan: BOOLEAN ← (1 < rowChan.chanNum AND rowChan.chanNum < rowChans.count) OR (rowChan.chanNum = 1 AND rowChans.count = 2);
[] ← SCNetUtil.EnumerateNets[handle, InitNet];
SCNewRoutePinsUtil.InitGetChanPins[handle, rowChan];
IF useThisChan THEN CreateExitsForChannel[handle: handle, rowChan: rowChan];
CreatePinsForChannel[handle: handle, rowChan: rowChan];
SCNewRoutePinsUtil.CreateNetDat[handle, rowChan];
SCNewRoutePinsUtil.GetAllNetSegInChan[handle, rowChan, NIL, MakeNetPin, NIL];
SCNewRoutePinsUtil.TermGetChanPins[handle, rowChan]};
CreatePinsForChannel: PROC [handle: SC.Handle, rowChan: SCPrivate.RowChan] = {
AllPins: SCInstUtil.EachPinProc = {
[instance: SCPrivate.Instance, pin: NAT, netPin: SCPrivate.PinNet]
IF netPin.net #NIL THEN {
IF side = SCInstUtil.PosOf[instance, netPin.pin].sideOn THEN {
alwaysUse: BOOLEAN ← (chan = 1 OR chan = rowChans.count) AND netPin.net.externNet AND SCNetUtil.ExitOnSide[handle, netPin.net, side];
rowOffset: SC.Number ← lgRows.horzRowOrg + lgRow.rowOrg.p;
rect: CD.Rect ← SCInstUtil.RotateRect[instance, netPin.pin.rect];
min: SC.Number ← rowOffset + instance.offset + rect.x1;
[] ← SCNewRoutePinsUtil.EnterPin[rowChan: rowChan, min: min, max: min + rect.x2 - rect.x1, depth: 0, layer: netPin.pin.layer, net: netPin.net, side: RTBasic.OtherSide[side], alwaysUse: alwaysUse]}}};
ExternalPins: SCInstUtil.EachPinProc = {
[instance: SCPrivate.Instance, pin: NAT, netPin: SCPrivate.PinNet]
IF netPin.net #NIL AND netPin.net.externNet THEN {
IF side = SCInstUtil.PosOf[instance, netPin.pin].sideOn AND SCNetUtil.ExitOnSide[handle, netPin.net, side] THEN {
rowOffset: SC.Number ← lgRows.horzRowOrg + lgRow.rowOrg.p;
rect: CD.Rect ← SCInstUtil.RotateRect[instance, netPin.pin.rect];
min: SC.Number ← rowOffset + instance.offset + rect.x1;
[] ← SCNewRoutePinsUtil.EnterPin[rowChan: rowChan, min: min, max: min + rect.x2 - rect.x1, depth: 0, layer: netPin.pin.layer, net: netPin.net, side: RTBasic.OtherSide[side], alwaysUse: TRUE]}}};
InternalPinsInstance: SCRowUtil.EachInstProc = {
[] ← SCInstUtil.EnumeratePinsOnInst[instance, AllPins]};
ExternalPinsInstance: SCRowUtil.EachInstProc = {
[] ← SCInstUtil.EnumeratePinsOnInst[instance, ExternalPins]};
lgRows: SCPrivate.LgRows ← NARROW[handle.layoutData, SCPrivate.LayoutData].lgRows;
rowChans: SCPrivate.RowChans ← NARROW[handle.layoutData, SCPrivate.LayoutData].rowChans;
chan: SCPrivate.MaxChanSr ← rowChan.chanNum;
side: SC.Side;
lgRow: SCPrivate.LgRow;
SELECT TRUE FROM
chan = 1 AND lgRows.count = 1 => {
only one row, must route one exterior channel. Choose the bottom one
side ← bottom; lgRow ← lgRows.rows[1];
[] ← SCRowUtil.EnumerateAllInstsOnRow[handle, lgRow.rowNum, InternalPinsInstance]};
chan = 1 => {
bottom exterior channel, transfer the exterior pins
side ← bottom; lgRow ← lgRows.rows[1];
[] ← SCRowUtil.EnumerateAllInstsOnRow[handle, lgRow.rowNum, ExternalPinsInstance]};
chan = lgRows.count + 1 => {
top exterior channel, transfer the exterior pins
side ← top; lgRow ← lgRows.rows[lgRows.count];
[] ← SCRowUtil.EnumerateAllInstsOnRow[handle, lgRow.rowNum, ExternalPinsInstance]};
ENDCASE => {
the interior channels
side ← top; lgRow ← lgRows.rows[chan - 1];
[] ← SCRowUtil.EnumerateAllInstsOnRow[handle, lgRow.rowNum, InternalPinsInstance];
side ← bottom; lgRow ← lgRows.rows[chan];
[] ← SCRowUtil.EnumerateAllInstsOnRow[handle, lgRow.rowNum, InternalPinsInstance]}};
CreateExitsForChannel: PROC [handle: SC.Handle, rowChan: SCPrivate.RowChan] = {
ExitPins: SCChanUtil.EachExitProc = {
PROC [exitNum: SCPrivate.MaxExitsSr, lrSide: SCPrivate.LRSide, rowChan: SCPrivate.RowChan, exit: SCPrivate.Exit] RETURNS [quit: BOOL ← FALSE]
pos: SC.Number ← IF lrSide = left THEN lgRows.horzRowOrg ELSE lgRows.horzRowOrg + lgRows.maxRowWidth;
[] ← SCNewRoutePinsUtil.EnterExit[rowChan, pos, exit.layer, exit.net, lrSide]};
EachSide: SCRowUtil.EachSideProc ~ {
[side: SC.Side, bpRow: SCPrivate.BpRow] RETURNS [quit: BOOL ← FALSE]
IF side = left OR side = right THEN {
[] ← SCChanUtil.EnumerateExits[handle, rowChan, side, ExitPins]}};
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
lgRows: SCPrivate.LgRows ← layoutData.lgRows;
[] ← SCRowUtil.EnumerateSides[handle, EachSide]};
MakeNetPin: SCNewRoutePinsUtil.PinProc = {
PROC [min, max, depth: SC.Number, side: SC.Side, layer: SC.Layer, net: SCPrivate.Net];
pin: Route.Pin ← NEW[Route.PinRec ← [min: min, max: max, depth: depth, layer: layer, side: side]];
net.pinsOnChan ← CONS[pin, net.pinsOnChan]};
InteriorChannelNetStats: PROC [handle: SC.Handle, rowChan: SCPrivate.RowChan] RETURNS [netStats: LIST OF SC.NetEntry ← NIL] ~ {
construct a list of nets with list of pins on channel for statistics
InteriorChannelNets: SCNetUtil.EachNetProc ~ {
PROC [net: SCPrivate.Net] RETURNS [quit: BOOL ← FALSE];
leftExit: BOOL ← net.chanExits[left][rowChan.chanNum-1];
rightExit: BOOL ← net.chanExits[right][rowChan.chanNum-1];
IF net.pinsOnChan # NIL OR leftExit OR rightExit THEN {
pinList: LIST OF Route.Pin ← net.pinsOnChan;
netStats ← CONS[NEW[SC.NetEntryRec ← [name: net.name, leftExit: leftExit, rightExit: rightExit, pinStats: NIL, ftStats: FTsOnNet[handle, net, rowChan]]], netStats];
FOR pins: LIST OF Route.Pin ← pinList, pins.rest UNTIL pins = NIL DO
pin: Route.Pin ← pins.first;
bottom: BOOL ← pin.side = bottom;
netStats.first.pinStats ← CONS[NEW[SC.PinEntryRec ← [bottom: bottom, position: (pin.min + pin.max)/2]], netStats.first.pinStats];
ENDLOOP}};
[] ← SCNetUtil.EnumerateNets[handle, InteriorChannelNets]};
LowerChannelNetStats: PROC [handle: SC.Handle, rowChan: SCPrivate.RowChan] RETURNS [netStats: LIST OF SC.NetEntry ← NIL] ~ {
construct a list of nets with list of pins on channel for statistics
LowerChannelNet: SCNetUtil.EachNetProc ~ {
PROC [net: SCPrivate.Net] RETURNS [quit: BOOL ← FALSE];
leftExit: BOOL ← net.chanExits[left][rowChan.chanNum-1];
rightExit: BOOL ← net.chanExits[right][rowChan.chanNum-1];
IF net.pinsOnChan # NIL OR leftExit OR rightExit THEN {
pinList: LIST OF Route.Pin ← net.pinsOnChan;
netStats ← CONS[NEW[SC.NetEntryRec ← [name: net.name, leftExit: leftExit, rightExit: rightExit, pinStats: NIL, ftStats: FTsOnNet[handle, net, rowChan]]], netStats];
FOR pins: LIST OF Route.Pin ← pinList, pins.rest UNTIL pins = NIL DO
pin: Route.Pin ← pins.first;
bottom: BOOL ← pin.side = bottom;
xfer: BOOLEAN ← net.externNet AND SCNetUtil.ExitOnSide[handle, net, bottom] AND pin.side = top;
netStats.first.pinStats ← CONS[NEW[SC.PinEntryRec ← [bottom: bottom, position: (pin.min + pin.max)/2]], netStats.first.pinStats];
IF xfer THEN
netStats.first.pinStats ← CONS[NEW[SC.PinEntryRec ← [bottom: ~bottom, position: (pin.min + pin.max)/2]], netStats.first.pinStats];
ENDLOOP}};
[] ← SCNetUtil.EnumerateNets[handle, LowerChannelNet]};
FTsOnNet: PROC [handle: SC.Handle, net: SCPrivate.Net, rowChan: SCPrivate.RowChan] RETURNS [ftStats: LIST OF SC.PinEntry ← NIL] ~ {
return a list of feedthrough pins on this net that are on this channel
EachPin: SCNetUtil.EachPinProc ~ {
PROC [netPin: SCPrivate.NetPin] RETURNS [quit: BOOL ← FALSE];
IF netPin.pinClass = ftPin AND netPin.instance.curRow = rowChan.chanNum THEN {
side: SC.Side ← SCInstUtil.PosOf[netPin.instance, netPin.pin].sideOn;
IF side = top THEN
ftStats ← CONS[NEW[SC.PinEntryRec ← [bottom: FALSE, position: SCInstUtil.InstPosOf[handle, netPin.instance, netPin.pin].pos.p]], ftStats]}
ELSE IF netPin.pinClass = ftPin AND netPin.instance.curRow = rowChan.chanNum-1 THEN {
side: SC.Side ← SCInstUtil.PosOf[netPin.instance, netPin.pin].sideOn;
IF side = bottom THEN
ftStats ← CONS[NEW[SC.PinEntryRec ← [bottom: TRUE, position: SCInstUtil.InstPosOf[handle, netPin.instance, netPin.pin].pos.p]], ftStats]}};
[] ← SCNetUtil.EnumeratePinsOnNet[net, EachPin]};
END.