SCExprRoutePinsUtilImpl.mesa
Copyright Ó 1987 by Xerox Corporation. All rights reserved.
Jason Cong, August 25, 1987 6:10:14 pm PDT
last edited by Preas, August 4, 1987 10:59:25 am PDT
Bryan Preas August 25, 1987 10:58:04 am PDT
Jean-Marc Frailong October 11, 1987 10:12:38 pm PDT
DIRECTORY
DABasics, Rope, SC, SCNetUtil, SCPrivate, SCExprRoutePinsUtil;
SCExprRoutePinsUtilImpl: CEDAR PROGRAM
IMPORTS Rope, SC, SCNetUtil
EXPORTS SCExprRoutePinsUtil
SHARES SC = {
initialize for determining the width of a channel
InitGetChanPins: PUBLIC PROCEDURE [handle: SC.Handle, rowChan: SCPrivate.RowChan] = {
InitNet: SCNetUtil.EachNetProc = {net.netDat ← NIL};
chanDat: SCExprRoutePinsUtil.ChanDat ← NEW[SCExprRoutePinsUtil.ChanDatRec];
chanDat.head ← chanDat.tail ← NEW[SCExprRoutePinsUtil.PinInChanRec ← [min: FIRST[INT], max: FIRST[INT], depth: 0, layer: 0]];
rowChan.chanDat ← chanDat;
rowChan.wireLength ← rowChan.chanDensity ← rowChan.chanWidth ← 0;
[] ← SCNetUtil.EnumerateNets[handle, InitNet]};
terminate determining the width of a channel
TermGetChanPins: PUBLIC PROCEDURE [handle: SC.Handle, rowChan: SCPrivate.RowChan] = {
TermNet: SCNetUtil.EachNetProc = {
netDat: SCExprRoutePinsUtil.NetDat ← NARROW[net.netDat];
IF netDat # NIL THEN {
chanNetDat: SCExprRoutePinsUtil.ChanNetDat ← netDat[rowChan.chanNum];
IF chanNetDat # NIL THEN
chanNetDat.firstPin ← chanNetDat.lastPin ← chanNetDat.leftmost ← chanNetDat.rightmost ← chanNetDat.exits[left] ← chanNetDat.exits[right] ← NIL;
net.netDat ← NIL};
net.pinList ← NIL;
net.edgeList ← NIL};
EachPin: SCExprRoutePinsUtil.EachPinProc = {
PROC[rowChan: SCPrivate.RowChan, pin: PinInChan];
pin.prevPinInChan ← pin.nextPinInNet ← NIL};
EnumPinsInChan[rowChan, EachPin];
[] ← SCNetUtil.EnumerateNets[handle, TermNet];
rowChan.chanDat ← NIL};
enter a net on a channel into data structure
EnterPin: PUBLIC PROCEDURE[rowChan: SCPrivate.RowChan, min, max, depth: SC.Number, layer: SC.Layer, net: SCPrivate.Net, side: DABasics.TBSide, alwaysUse: BOOLEAN] RETURNS[pinInChan: SCExprRoutePinsUtil.PinInChan] = {
chanDat: SCExprRoutePinsUtil.ChanDat ← NARROW[rowChan.chanDat];
tail: SCExprRoutePinsUtil.PinInChan ← chanDat.tail;
chanDat.tail ← tail.nextPinInChan ← pinInChan ← NEW[SCExprRoutePinsUtil.PinInChanRec ← [
layer: layer,
net: net,
chanNet: NIL,
min: min, max: max, depth: depth,
pinClass: isPin,
chanSide: side,
nextPinInChan: NIL,
prevPinInChan: tail,
pinConn: unconnected,
nextPinInNet: NIL, prevPinInNet: NIL,
localDensity: 0 ,
alwaysUse: alwaysUse,
chanNum: rowChan.chanNum]];
rowChan.chanDat ← chanDat};
enter exit data for a channel into routing data base
EnterExit: PUBLIC PROCEDURE[rowChan: SCPrivate.RowChan, pos: SC.Number, layer: SC.Layer, net: SCPrivate.Net, side: DABasics.LRSide] RETURNS[pinInChan: SCExprRoutePinsUtil.PinInChan] = {
chanDat: SCExprRoutePinsUtil.ChanDat ← NARROW[rowChan.chanDat];
tail: SCExprRoutePinsUtil.PinInChan ← chanDat.tail;
chanDat.tail ← tail.nextPinInChan ← pinInChan ← NEW[SCExprRoutePinsUtil.PinInChanRec ← [
layer: layer,
net: net,
chanNet: NIL,
min: pos, max: pos, depth: 0,
pinClass: isExit,
chanSide: side,
nextPinInChan: NIL,
prevPinInChan: tail,
pinConn: unconnected,
nextPinInNet: NIL, prevPinInNet: NIL,
localDensity: 0 ,
alwaysUse: TRUE,
chanNum: rowChan.chanNum]];
rowChan.chanDat ← chanDat};
NoChange: PROCEDURE[mpin, pin: SCExprRoutePinsUtil.PinInChan] RETURNS[yes: BOOLEAN ← FALSE] = {
IF mpin.nextPinInNet # NIL THEN
yes ← (mpin.nextPinInNet.min = pin.min) AND (mpin.nextPinInNet.pinConn #unconnected);
IF mpin.prevPinInNet # NIL THEN
yes ← yes OR (mpin.prevPinInNet.min = pin.min) AND (mpin.prevPinInNet.pinConn # unconnected) };
MoveAPinInChan: PUBLIC PROCEDURE[rowChan: SCPrivate.RowChan, pin: SCExprRoutePinsUtil.PinInChan, deltaX: SC.Number] RETURNS[scan: BOOLEAN ← FALSE] = {
next: SCExprRoutePinsUtil.PinInChan ← pin;
prev: SCExprRoutePinsUtil.PinInChan ← pin;
origX, currX, dX: SC.Number;
origX ← currX ← pin.min;
pin.min ← pin.min + deltaX;
pin.max ← pin.max + deltaX;
IF pin.min = rowChan.chanDensity THEN scan ← TRUE;
IF deltaX > 0 THEN {
prev ← pin.prevPinInChan;
IF (prev # NIL) AND (prev.min = currX) AND (pin.pinConn = left) THEN
prev.localDensity ← prev.localDensity - 1;
WHILE (pin.nextPinInChan # NIL) AND (pin.nextPinInChan.min <= pin.min) DO
next ← pin.nextPinInChan;
IF next.localDensity = rowChan.chanDensity THEN scan ← TRUE;
dX ← next.min - currX;
currX ← next.min;
SwapTwoPins[pin, next];
SELECT pin.pinConn FROM
left => {
IF pin.net = next.net THEN {
SELECT next.pinConn FROM
interior => {
pin.pinConn ← interior;
next.pinConn ← left;
pin.chanNet.leftmost ← next};
right => {
pin.pinConn ← right;
next.pinConn ← left;
pin.chanNet.leftmost ← next;
pin.chanNet.rightmost ← pin};
ENDCASE};
rowChan.wireLength ← rowChan.wireLength - dX};
interior => {
IF pin.net = next.net THEN
IF next.pinConn = right THEN {
next.pinConn ← interior;
pin.pinConn ← right;
pin.chanNet.rightmost ← pin}};
right => {
rowChan.wireLength ← rowChan.wireLength + dX};
ENDCASE;
IF pin.net = next.net THEN
SwapTwoPinsInNet[pin, next];
ENDLOOP;
dX ← pin.min - currX;
IF pin.pinConn = right THEN
rowChan.wireLength ← rowChan.wireLength + dX;
IF pin.pinConn = left THEN
rowChan.wireLength ← rowChan.wireLength - dX;
next ← pin.nextPinInChan}
ELSE IF deltaX < 0 THEN {
next ← pin.nextPinInChan;
IF (next # NIL) AND (next.min = currX) AND (pin.pinConn = right) THEN
next.localDensity ← next.localDensity - 1;
WHILE (pin.prevPinInChan # NIL) AND (pin.prevPinInChan.min >= pin.min) DO
prev ← pin.prevPinInChan;
IF prev.localDensity = rowChan.chanDensity THEN scan ← TRUE;
dX ← currX - prev.min;
currX ← prev.min;
SwapTwoPins[prev, pin];
SELECT pin.pinConn FROM
right => {
IF pin.net = prev.net THEN {
SELECT prev.pinConn FROM
interior => {
pin.pinConn ← interior;
prev.pinConn ← right;
pin.chanNet.rightmost ← prev};
left => {
pin.pinConn ← left;
prev.pinConn ← right;
pin.chanNet.leftmost ← pin;
pin.chanNet.rightmost ← prev};
ENDCASE};
rowChan.wireLength ← rowChan.wireLength - dX};
interior => {
IF pin.net = prev.net THEN
IF prev.pinConn = left THEN {
prev.pinConn ← interior;
pin.pinConn ← left;
pin.chanNet.leftmost ← pin}};
left => {
rowChan.wireLength ← rowChan.wireLength + dX};
ENDCASE;
IF pin.net = prev.net THEN
SwapTwoPinsInNet[prev, pin];
ENDLOOP;
dX ← currX - pin.min;
IF pin.pinConn = left THEN
rowChan.wireLength ← rowChan.wireLength + dX;
IF pin.pinConn = right THEN
rowChan.wireLength ← rowChan.wireLength - dX}};
SortPins: PROCEDURE[chanDat: SCExprRoutePinsUtil.ChanDat] = {
stop: BOOLEAN ← FALSE;
temp: SCExprRoutePinsUtil.PinInChan;
head: SCExprRoutePinsUtil.PinInChan ← chanDat.head;
WHILE ~stop DO
rList: SCExprRoutePinsUtil.PinInChan ← head;
stop ← TRUE;
WHILE rList.nextPinInChan # NIL DO
temp ← rList.nextPinInChan;
IF rList.min > temp.min THEN {
stop ← FALSE;
SwapTwoPins[rList, temp]};
rList ← temp;
ENDLOOP;
ENDLOOP};
SwapTwoPins: PROCEDURE[pin1, pin2: SCExprRoutePinsUtil.PinInChan] = {
IF pin2.nextPinInChan # NIL THEN
pin2.nextPinInChan.prevPinInChan ← pin1;
IF pin1.prevPinInChan # NIL THEN
pin1.prevPinInChan.nextPinInChan ← pin2;
pin1.nextPinInChan ← pin2.nextPinInChan;
pin2.prevPinInChan ← pin1.prevPinInChan;
pin1.prevPinInChan ← pin2;
pin2.nextPinInChan ← pin1};
SwapTwoPinsInNet: PROCEDURE[pin1, pin2: SCExprRoutePinsUtil.PinInChan] = {
chanNetDat: SCExprRoutePinsUtil.ChanNetDat ← pin1.chanNet;
IF pin2.nextPinInNet # NIL THEN
pin2.nextPinInNet.prevPinInNet ← pin1;
IF pin1.prevPinInNet # NIL THEN
pin1.prevPinInNet.nextPinInNet ← pin2;
pin1.nextPinInNet ← pin2.nextPinInNet;
pin2.prevPinInNet ← pin1.prevPinInNet;
pin1.prevPinInNet ← pin2;
pin2.nextPinInNet ← pin1;
IF chanNetDat.firstPin = pin1 THEN chanNetDat.firstPin ← pin2;
IF chanNetDat.lastPin = pin2 THEN chanNetDat.lastPin ← pin1};
enumerate all the pins on this channel (all nets)
EnumPinsInChan: PUBLIC PROCEDURE[rowChan: SCPrivate.RowChan, doEachPin: SCExprRoutePinsUtil.EachPinProc] = {
chanDat: SCExprRoutePinsUtil.ChanDat ← NARROW[rowChan.chanDat];
IF chanDat # NIL THEN {
head: SCExprRoutePinsUtil.PinInChan ← chanDat.head;
FOR chanPin: SCExprRoutePinsUtil.PinInChan ← head.nextPinInChan, chanPin.nextPinInChan WHILE chanPin # NIL DO
doEachPin[rowChan, chanPin];
ENDLOOP}};
enumerate the pins on this net on this channel (including exits)
EnumAllPinsInNetChan: PUBLIC PROCEDURE[chanNetDat: SCExprRoutePinsUtil.ChanNetDat, doEachNetPin: SCExprRoutePinsUtil.EachNetPinProc] = {
IF chanNetDat # NIL THEN {
FOR chanPin: SCExprRoutePinsUtil.PinInChan ← chanNetDat.firstPin, chanPin.nextPinInNet WHILE chanPin # NIL DO
doEachNetPin[chanNetDat, chanPin];
ENDLOOP}};
enumerate the pins on this net on this channel on side (including exits)
EnumPinsInNetChan: PUBLIC PROCEDURE[chanNetDat: SCExprRoutePinsUtil.ChanNetDat, side: DABasics.Side, doEachNetPin: SCExprRoutePinsUtil.EachNetPinProc] = {
IF chanNetDat # NIL THEN {
FOR chanPin: SCExprRoutePinsUtil.PinInChan ← chanNetDat.firstPin, chanPin.nextPinInNet WHILE chanPin # NIL DO
IF chanPin.chanSide = side OR chanPin.pinClass = isExit THEN doEachNetPin[chanNetDat, chanPin];
ENDLOOP}};
initialize the data for a channel
CreateNetDat: PUBLIC PROCEDURE[handle: SC.Handle, rowChan: SCPrivate.RowChan] = {
DoEachPin: SCExprRoutePinsUtil.EachPinProc = {
EachPinProc: TYPE = PROC[rowChan: SCPrivate.RowChan, pin:PinInChan];
net: SCPrivate.Net ← pin.net;
netDat: SCExprRoutePinsUtil.NetDat ← NARROW[net.netDat];
chanNum: NAT ← rowChan.chanNum;
chanNetDat: SCExprRoutePinsUtil.ChanNetDat ← NIL;
IF netDat = NIL THEN
net.netDat ← netDat ← NARROW[NEW[SCExprRoutePinsUtil.NetDatRec ← ALL[NIL]]];
IF netDat[chanNum] = NIL THEN
netDat[chanNum] ← NEW[SCExprRoutePinsUtil.ChanNetDatRec];
chanNetDat ← netDat[chanNum];
IF pin.pinClass = isExit THEN {
IF chanNetDat.exits[pin.chanSide] # NIL THEN
SC.Error[programmingError, "More than two exits for a net one side of a channel"]
ELSE chanNetDat.exits[pin.chanSide] ← pin};
IF chanNetDat.firstPin = NIL THEN {
chanNetDat.firstPin ← (chanNetDat.lastPin ← pin);
chanNetDat.net ← net}
ELSE {
pin.prevPinInNet ← chanNetDat.lastPin;
chanNetDat.lastPin.nextPinInNet ← pin;
chanNetDat.lastPin ← pin};
chanNetDat.pinCount ← chanNetDat.pinCount + 1;
pin.chanNet ← chanNetDat};
main body of 'CreateNetDat'
SortPins[NARROW[rowChan.chanDat]];
EnumPinsInChan[rowChan, DoEachPin]};
enter a net segment into chanNetDat, and enter pin connection info in pin.
GetANetSegInChan: PUBLIC PROC [handle: SC.Handle, rowChan: SCPrivate.RowChan, net: SCPrivate.Net, segProc: SCExprRoutePinsUtil.SegProc, pinProc: SCExprRoutePinsUtil.PinProc, exitProc: SCExprRoutePinsUtil.ExitProc] ~ {
main body of GetANetSegInChan
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
lgRows: SCPrivate.LgRows ← layoutData.lgRows;
netDat: SCExprRoutePinsUtil.NetDat ← NARROW[net.netDat];
chan: SCPrivate.ZMaxChanSr ← rowChan.chanNum;
segNum: SC.Number ← 1;
chanNetDat: SCExprRoutePinsUtil.ChanNetDat ← netDat[chan];
IF chanNetDat # NIL THEN {
firstPin: SCExprRoutePinsUtil.PinInChan ← chanNetDat.firstPin;
lastPin: SCExprRoutePinsUtil.PinInChan ← chanNetDat.lastPin;
pin: SCExprRoutePinsUtil.PinInChan ← firstPin;
IF firstPin # NIL THEN {
DO
IF pin.pinClass = isExit THEN
{IF exitProc # NIL THEN exitProc[pin.chanSide, pin.layer, pin.net]}
ELSE IF pin.pinClass = isPin AND pin.pinConn # unconnected THEN
{IF pinProc # NIL THEN pinProc[pin.min, pin.max, pin.depth, pin.chanSide, pin.layer, pin.net]};
IF pin.pinConn = right THEN {
segNum ← segNum + 1;
IF segProc # NIL THEN segProc[segNum, net]};
IF pin = lastPin THEN EXIT
ELSE pin ← pin.nextPinInNet;
ENDLOOP}}};
GetAllNetSegInChan: PUBLIC PROC [handle: SC.Handle, rowChan: SCPrivate.RowChan, segProc: SCExprRoutePinsUtil.SegProc, pinProc: SCExprRoutePinsUtil.PinProc, exitProc: SCExprRoutePinsUtil.ExitProc] ~ {
enter all net segment into the netDats, and enter pin connection info.
EachNet: SCNetUtil.EachNetProc ~ {
PROC [net: SCPrivate.Net] RETURNS [quit: BOOL ← FALSE];
IF net.netDat # NIL THEN
GetANetSegInChan[handle, rowChan, net, segProc, pinProc, exitProc]};
[] ← SCNetUtil.EnumerateNets[handle, EachNet]};
NextPinState: PROC [pinState: SCExprRoutePinsUtil.ConnectionType, pin: SCExprRoutePinsUtil.PinInChan] RETURNS [newPinState: SCExprRoutePinsUtil.ConnectionType] ~ {
compute connection of this pin as a function of its position and the previous state
IF pin.pinConn = unconnected THEN { -- this pin is unconnected
newPinState ← unconnected;
IF pin.pinClass = isExit THEN
SC.Signal[programmingError, Rope.Cat["Exit is unconnected for wire: ", pin.net.name, ". Call maintainer"]]}
ELSE IF pin.pinConn = interior THEN { -- this pin is unconnected; determine which type
IF pinState = unconnected THEN  -- fitst pin we have come to
newPinState ← left
ELSE newPinState ← interior}};
PosOfPin: PROC [chanPin: SCExprRoutePinsUtil.PinInChan] RETURNS [INT] ~ INLINE{
RETURN[(chanPin.min+chanPin.max)/2]};
}.