SCNewGlobalRouteImpl.mesa
Copyright Ó 1987 by Xerox Corporation. All rights reserved.
Jason Cong, August 27, 1987 7:11:14 pm PDT
Jean-Marc Frailong October 11, 1987 4:26:57 pm PDT
Implementation of the new global routing algorithms based on M.S.T. approaches.
DIRECTORY
CD, IO, Real, Rope, RTBasic, RTSets, SC, SCChanUtil, SCInstUtil, SCNetUtil, SCPrivate, SCRowUtil, SCPlaceUtil, SCNewWidth, SCExprRoutePinsUtil, SCExprGlobalRoute, SCUtil, TerminalIO;
SCNewGlobalRouteImpl: CEDAR PROGRAM
IMPORTS IO, Real, RTBasic, RTSets, SC, SCChanUtil, SCInstUtil, SCNetUtil, SCNewWidth, SCExprRoutePinsUtil, SCPlaceUtil, SCRowUtil, SCUtil, TerminalIO
EXPORTS SCExprGlobalRoute
SHARES SC = {
hvRatio: NAT = 500;
debug: BOOLEANTRUE;
Edge: TYPE ~ REF EdgeRec;
EdgeRec: TYPE ~ RECORD[
pin1, pin2: SCExprRoutePinsUtil.PinInChan,
cutEdge, buildInEdge: BOOLEAN,
weight: SC.Number,
nextEdge, prevEdge: Edge ← NIL
];
EdgeList: TYPE = LIST OF Edge;
WeightFun: TYPE = PROC[handle: SC.Handle, edge: Edge] RETURNS[cost: SC.Number];
EdgeTest: TYPE = PROC [edge: Edge] RETURNS [delete: BOOLEANFALSE];
GlobalRoute: PUBLIC PROCEDURE[handle: SC.Handle, nets: SCPrivate.NetList] = {
Complete global routing for the nets specified in the input net list.
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
lgRows: SCPrivate.LgRows ← layoutData.lgRows;
TerminalIO.PutRope["Begin global route\n Stage 1\n"];
SCNewWidth.AllChanWidths[handle, areaFom];
SCInstUtil.AsgnChanPos[handle];
AddFTsInNets[handle, nets];
TerminalIO.PutRope["Stage 2\n"];
DecideEdgesInNets[handle, nets];
SCInstUtil.AllOffsets[handle];
[lgRows.maxRowWidth, lgRows.numMaxRows] ← SCRowUtil.FindMaxRow[handle];
SCNewWidth.ComputeAllChanDW[handle, areaFom];
SCInstUtil.AsgnChanPos[handle];
TerminalIO.PutRope["End global route\n"];
[] ← SCUtil.WriteResults["End global route\n estimated size:", handle, 0]};
UndoGlobalRoute: PUBLIC PROCEDURE[handle: SC.Handle, nets: SCPrivate.NetList] = {};
Undo global routing for the nets specified in the input net list.
GlobalRouteAllNets: PUBLIC PROCEDURE[handle: SC.Handle] = {
Do global routing for all nets.
EachNet: SCNetUtil.EachNetProc = { nets ← CONS[net, nets]};
nets: SCPrivate.NetList ← NIL;
[] ← SCNetUtil.EnumerateNets[handle, EachNet];
GlobalRoute[handle, nets]};
AddFTsInNets: PROC [handle: SC.Handle, nets: SCPrivate.NetList] ~ {
edgeList: Edge ← NIL;
AddExitsInNets[handle, nets];
EnterPinNodes[handle];
edgeList ← BuildGraphs1[handle, nets];
MarkBuildInEdges[handle, nets];
GetAllRowWeights[handle];
edgeList ← ComputeWeights[handle, nets, edgeList, Cost1, EdgeTest1];
GenerateTrees1[handle, nets, edgeList];
RemoveGraph1[handle, nets];
};
DecideEdgesInNets: PROC [handle: SC.Handle, nets: SCPrivate.NetList] ~ {
edgeList: Edge ← NIL;
edgeList ← BuildGraphs2[handle, nets];
GetNetsSpan[handle, nets];
GetAllChanDensity[handle];
MarkAllCutEdges[handle, nets];
edgeList ← ComputeWeights[handle, nets, edgeList, Cost2, EdgeTest2];
GenerateTrees2[handle, nets, edgeList];
};
AddExitsInNets: PROC [handle: SC.Handle, nets: SCPrivate.NetList] ~ {
EachNet: SCNetUtil.EachNetProc = {
onSide: SCPrivate.SideSet;
onRow: SCPrivate.RowSet;
leftOnChan, rightOnChan: SCPrivate.ChanSet ← RTSets.RTLgSetEmpty;
instList: SCPrivate.InstanceList ← SCNetUtil.InstsOnNets[LIST[net]];
numInstances: SCPrivate.ZMaxInstanceSr ← SCInstUtil.NumInstsOnList[instList];
[onSide, onRow] ← SCRowUtil.RowsForInsts[instList];
IF onSide[LOOPHOLE[SC.Side[left], INTEGER]] THEN
[] ← DetermineExits[handle, left, net];
IF onSide[LOOPHOLE[SC.Side[right], INTEGER]] THEN
[] ← DetermineExits[handle, right, net];
};
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
lgRows: SCPrivate.LgRows ← layoutData.lgRows;
rowChans: SCPrivate.RowChans ← layoutData.rowChans;
FOR netLst: SCPrivate.NetList ← nets, netLst.rest WHILE netLst # NIL DO
[] ← EachNet[netLst.first];
ENDLOOP;
};
DetermineExits: PROCEDURE[handle: SC.Handle, side: SCPrivate.LRSide, net: SCPrivate.Net]
RETURNS [onChan: SCPrivate.ChanSet ← RTSets.RTLgSetEmpty] = {
add side exits as required to net lists
find preferred position for exit to side surface
ChanExitProc: SCChanUtil.EachRowChanProc = {
PROC [chan: SCPrivate.MaxChanSr, rowChan: SCPrivate.RowChan] RETURNS [quit: BOOLFALSE];
IF onChan[(chan) - 1] THEN AddExit[handle, rowChan, side, net]};
EachPinProc: SCNetUtil.EachPinProc = {
PROC [netPin: SCPrivate.NetPin] RETURNS [quit: BOOLFALSE];
instance: SCPrivate.Instance ← netPin.instance;
pin: SCPrivate.ObjectPin ← netPin.pin;
get position of instance on side
IF instance.whichClass = io THEN {
sideOn: SC.Side ← SCInstUtil.PosOf[instance, pin].sideOn;
yPos: SC.Number ← SCInstUtil.InstPosOf[handle, instance, pin].q;
IF instance.curSide = side
AND instance.curPos > 0 AND sideOn = chanSide THEN {
IF rowChans.count <= 2 THEN
exit must be on bottom channel
onChan ← RTSets.RTLgSetGenerateElement[(1)-1]
ELSE {
must compute the channel to put the exit on
ChanProc: SCChanUtil.EachRowChanProc = {
PROC [chan: SCPrivate.MaxChanSr, rowChan: SCPrivate.RowChan] RETURNS [quit: BOOLFALSE];
IF touchesChan[(chan)-1] THEN {
SetMinMaxDists: PROCEDURE [] =
{IF dist < minDist THEN {minDistChan ← chan; minDist ← dist};
IF chanPos > maxChanPos THEN {maxChan ← chan; maxChanPos ← chanPos};
IF chanPos < minChanPos THEN {minChan ← chan; minChanPos ← chanPos}};
chanPos: SC.Number ← rowChan.chanPos + rowChan.chanWidth/2;
dist: SC.Number ← ABS[chanPos - holdBpPos];
layoutParms: SCPrivate.LayoutParms ← layoutData.layoutParms;
SELECT TRUE FROM
~layoutParms.useInteriorChanExits => SetMinMaxDists;
layoutParms.useInteriorChanExits =>
IF (1 < chan AND chan < rowChans.count) THEN SetMinMaxDists;
ENDCASE}};
minDist, minChanPos: SC.Number ← LAST[INT];
maxChanPos: SC.Number ← -LAST[INT];
minDistChan, maxChan, minChan: SCPrivate.ZMaxChanSr ← 0;
holdBpPos: SC.Number ← SCInstUtil.BpPos[handle, instance] + yPos;
find distance of port to closest existing channel
[] ← SCChanUtil.EnumerateRowChans[handle, ChanProc];
determine channel to exit
SELECT TRUE FROM
holdBpPos > maxChanPos AND maxChan > 0 =>
onChan ← RTSets.RTLgSetUnion[onChan, RTSets.RTLgSetGenerateElement[(maxChan)-1]];
holdBpPos < minChanPos AND minChan > 0 =>
onChan ← RTSets.RTLgSetUnion[onChan, RTSets.RTLgSetGenerateElement[(minChan)-1]];
minDistChan > 0 =>
onChan ← RTSets.RTLgSetUnion[onChan, RTSets.RTLgSetGenerateElement[(minDistChan)-1]];
ENDCASE}}}};
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
rowChans: SCPrivate.RowChans ← layoutData.rowChans;
chanSide: RTBasic.Side ← RTBasic.OtherSide[side];
instList: SCPrivate.InstanceList ← SCNetUtil.InstsOnNets[LIST[net]];
touchesChan: SCPrivate.ChanSet ← SCInstUtil.ChansForInsts[handle, instList];
net.chanExits[side] ← RTSets.RTLgSetEmpty;
[] ← SCNetUtil.EnumeratePinsOnNet[net, EachPinProc];
found channels to exit from, indicated in onChan
[] ← SCChanUtil.EnumerateRowChans[handle, ChanExitProc]};
AddExit: PUBLIC PROCEDURE[handle: SC.Handle, rowChan: SCPrivate.RowChan, side: SC.Side, net: SCPrivate.Net] = {
add an exit to a channel
IF rowChan.chanNum = 0 THEN SC.Error[programmingError, NIL]
ELSE {
index: NAT ← rowChan.numExits[side] ← rowChan.numExits[side] + 1;
net.chanExits[side] ←
RTSets.RTLgSetUnion[net.chanExits[side], RTSets.RTLgSetGenerateElement[(rowChan.chanNum)-1]];
rowChan.exits[side][index] ← NEW[SCPrivate.ExitRec ← [net: net, pos: 0, pinInChan: NIL, layer: handle.rules.rowRules.trunkLayer]]}};
EnterPinNodes: PROC [handle: SC.Handle] ~ {
EachChan: SCChanUtil.EachRowChanProc = {
EachRowChanProc: TYPE = PROC [chan: SCPrivate.MaxChanSr, rowChan: SCPrivate.RowChan] RETURNS [quit: BOOLFALSE];
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
rowChans: SCPrivate.RowChans ← layoutData.rowChans;
SCExprRoutePinsUtil.InitGetChanPins[handle, rowChan];
IF rowChan.chanNum = 1 THEN
SCNewWidth.EnterRowData[rowChan, handle, 1, bottom]
ELSE IF rowChan.chanNum = rowChans.count THEN
SCNewWidth.EnterRowData[rowChan, handle, lgRows.count, top]
ELSE {
SCNewWidth.EnterRowData[rowChan, handle, rowChan.chanNum-1, top];
SCNewWidth.EnterRowData[rowChan, handle, rowChan.chanNum, bottom]};
SCNewWidth.EnterExitData[handle, rowChan, left];
SCNewWidth.EnterExitData[handle, rowChan, right];
};
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
lgRows: SCPrivate.LgRows ← layoutData.lgRows;
IF lgRows.rows[1].lgsOnRow[1].pinNets[1].pinInChan = NIL THEN --graph nodes have not been created.
[] ← SCChanUtil.EnumerateRowChans[handle, EachChan]
};
BuildGraphs1: PROC [handle: SC.Handle, nets: SCPrivate.NetList] RETURNS [edgeList: Edge ← NIL] ~ {
EachNet: PROC [net: SCPrivate.Net] ~ {
pinList: SCExprRoutePinsUtil.PinList ← NARROW[net.pinList];
compNo: NAT ← 0;
FOR pinList1: SCExprRoutePinsUtil.PinList ← pinList, pinList1.rest WHILE pinList1 # NIL DO
pin1: SCExprRoutePinsUtil.PinInChan ← pinList1.first;
compNo ← compNo + 1;
pin1.component ← compNo;
FOR pinList2: SCExprRoutePinsUtil.PinList ← pinList1.rest, pinList2.rest WHILE pinList2 # NIL DO
pin2: SCExprRoutePinsUtil.PinInChan ← pinList2.first;
edge: Edge ← EnterAEdge[pin1, pin2, FALSE, FALSE];
edgeList ← InsertEdge[edge, edgeList];
ENDLOOP;
ENDLOOP;
};
FOR netList: SCPrivate.NetList ← nets, netList.rest WHILE netList # NIL DO
net: SCPrivate.Net ← netList.first;
EachNet[net];
ENDLOOP;
};
EnterAEdge: PROC [pin1, pin2: SCExprRoutePinsUtil.PinInChan, cutEdge, buildInEdge: BOOLEAN] RETURNS [edge: Edge] ~ {
adjList1: EdgeList ← NARROW[pin1.adjList];
adjList2: EdgeList ← NARROW[pin2.adjList];
netEdges: EdgeList ← NARROW[pin1.net.edgeList];
pinA, pinB: SCExprRoutePinsUtil.PinInChan ← NIL;
IF pin1.net # pin2.net THEN SC.Error[programmingError, "Invalid graph edge"];
IF pin1.min <= pin2.min THEN {
pinA ← pin1;
pinB ← pin2}
ELSE {
pinA ← pin2;
pinB ← pin1};
edge ← NEW[EdgeRec ← [
pin1: pinA,
pin2: pinB,
cutEdge: cutEdge,
buildInEdge: buildInEdge,
weight: 0]];
adjList1 ← CONS[edge, adjList1];
adjList2 ← CONS[edge, adjList2];
pin1.adjList ← adjList1;
pin2.adjList ← adjList2;
netEdges ← CONS[edge, netEdges];
pin1.net.edgeList ← netEdges
};
GetAllRowWeights: PROC [handle: SC.Handle] ~ {
EachRow: SCRowUtil.EachRowProc = {
EachRowProc: TYPE = PROC [row: SCPrivate.MaxRowSr, lgRow: SCPrivate.LgRow] RETURNS [quit: BOOLFALSE];
lgRow.weight ← 1};
[] ← SCRowUtil.EnumerateRows[handle, EachRow]};
ComputeWeights: PROC [handle: SC.Handle, nets: SCPrivate.NetList, edgeList: Edge, Cost: WeightFun, DeleteTest: EdgeTest] RETURNS[ newEdges: Edge ← NIL] ~ {
FOR edges: Edge ← edgeList, edges.nextEdge WHILE edges # NIL DO
edge: Edge ← edges;
IF DeleteTest[edge] THEN
edgeList ← DeleteEdge[edge, edgeList]
ELSE
edge.weight ← Cost[handle, edge];
ENDLOOP
};
RemoveNetEdge: PROC[net: SCPrivate.Net, edge: Edge] = {
remove a net edge from net.edgelist
netEdges: EdgeList ← NARROW[net.edgeList];
net.edgeList ← DRemove[edge, netEdges]};
Cost1: WeightFun = {
WeightFun: TYPE = PROC[handle: handle: SC.Handle, edge: Edge] RETURNS[cost: SC.Number];
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
lgRows: SCPrivate.LgRows ← layoutData.lgRows;
horiWeight, vertWeight: SC.Number ← 0;
pin1: SCExprRoutePinsUtil.PinInChan ← edge.pin1;
pin2: SCExprRoutePinsUtil.PinInChan ← edge.pin2;
bound1, bound2: NAT;
horiWeight ← ABS[pin1.min - pin2.min];
IF pin1.chanNum <= pin2.chanNum THEN {
bound1 ← pin1.chanNum;
bound2 ← pin2.chanNum}
ELSE {
bound1 ← pin2.chanNum;
bound2 ← pin1.chanNum};
FOR index: NAT ← bound1, index + 1 WHILE index < bound2 DO
vertWeight ← vertWeight + lgRows.rows[index].weight;
ENDLOOP;
cost ← horiWeight + hvRatio * vertWeight;
};
Cost2: WeightFun = {
WeightFun: TYPE = PROC[handle: handle: SC.Handle, edge: Edge] RETURNS[cost: SC.Number];
pin, left, right: SCExprRoutePinsUtil.PinInChan ← NIL;
pin1: SCExprRoutePinsUtil.PinInChan ← edge.pin1;
pin2: SCExprRoutePinsUtil.PinInChan ← edge.pin2;
IF edge.buildInEdge THEN cost ← 0
ELSE IF pin1.chanNum # pin2.chanNum THEN
SC.Error[programmingError, "Invalid Graph Edge"]
ELSE IF pin1.min = pin2.min THEN
cost ← 0
ELSE {
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
rowChans: SCPrivate.RowChans ← layoutData.rowChans;
left ← pin1;
right ← pin2;
cost ← 0;
pin ← left;
DO
cost ← MAX[cost, pin.localDensity];
IF pin = right THEN EXIT
ELSE pin ← pin.nextPinInChan;
ENDLOOP;
cost ← Real.InlineRound[100 * Real.FDiv[cost, rowChans.chans[pin1.chanNum].chanDensity]]}
};
EdgeTest1: EdgeTest = {
EdgeTest: TYPE = PROC [edge: Edge] RETURNS [delete: BOOLEANFALSE];
pin1: SCExprRoutePinsUtil.PinInChan ← edge.pin1;
pin2: SCExprRoutePinsUtil.PinInChan ← edge.pin2;
IF (pin1.component = pin2.component) THEN
delete ← TRUE
ELSE delete ← FALSE;
};
EdgeTest2: EdgeTest = {
EdgeTest: TYPE = PROC [edge: Edge] RETURNS [delete: BOOLEANFALSE];
IF edge.cutEdge OR edge.buildInEdge THEN
delete ← TRUE
ELSE delete ← FALSE
};
BuildGraphs2: PROC [handle: SC.Handle, nets: SCPrivate.NetList] RETURNS [edgeList: Edge ← NIL] ~ {
SortAllChanPins[handle];
edgeList ← EnterNetEdges[handle, nets];
edgeList ← Append[edgeList, EnterBuildInEdges[handle, nets]];
};
SortAllChanPins: PROC [handle: SC.Handle] ~ {
EachChan: SCChanUtil.EachRowChanProc = {
SCExprRoutePinsUtil.CreateNetDat[handle, rowChan]};
[] ← SCChanUtil.EnumerateRowChans[handle, EachChan]};
EnterNetEdges: PROC [handle: SC.Handle, nets: SCPrivate.NetList] RETURNS [edgeList: Edge ← NIL] ~ {
EachNet: PROC [net: SCPrivate.Net] ~ {
pinList: SCExprRoutePinsUtil.PinList ← NARROW[net.pinList];
FOR pins: SCExprRoutePinsUtil.PinList ← pinList, pins.rest WHILE pins # NIL DO
pin: SCExprRoutePinsUtil.PinInChan ← pins.first;
edge: Edge ← NIL;
IF pin.nextPinInNet # NIL AND InUseChan[handle, pin.chanNum] THEN {
edge ← EnterAEdge[pin, pin.nextPinInNet, FALSE, FALSE];
edgeList ← InsertEdge[edge, edgeList]};
ENDLOOP};
FOR netList: SCPrivate.NetList ← nets, netList.rest WHILE netList # NIL DO
EachNet[netList.first];
ENDLOOP};
InUseChan: PROC [handle: SC.Handle, chan: SCPrivate.MaxChanSr] RETURNS [yes: BOOLEAN ← FALSE] ~ {
rowChans: SCPrivate.RowChans ← NARROW[handle.layoutData, SCPrivate.LayoutData].rowChans;
IF chan = 1 THEN
IF rowChans.count > 2 THEN yes ← FALSE
ELSE yes ← TRUE
ELSE
IF chan = rowChans.count THEN yes ← FALSE
ELSE yes ← TRUE
};
EnterBuildInEdges: PROC [handle: SC.Handle, nets: SCPrivate.NetList] RETURNS [edgeList: Edge ← NIL] ~ {
EachRow: SCRowUtil.EachRowProc = {
EachRowProc: TYPE = PROC [row: SCPrivate.MaxRowSr, lgRow: SCPrivate.LgRow] RETURNS [quit: BOOLFALSE];
InstProc: SCRowUtil.EachInstProc = {
EachInstProc: TYPE = PROC [pos: NAT, instance: SCPrivate.Instance] RETURNS [quit: BOOLFALSE];
FOR pinNum1: NAT IN [0 .. instance.pinNets.size) DO
netPin1: SCPrivate.PinNet ← instance.pinNets.n[pinNum1];
pin1: SCExprRoutePinsUtil.PinInChan ← NARROW[netPin1.pinInChan];
FOR pinNum2: NAT IN [pinNum1 + 1 .. instance.pinNets.size) DO
netPin2: SCPrivate.PinNet ← instance.pinNets.n[pinNum2];
pin2: SCExprRoutePinsUtil.PinInChan ← NARROW[netPin2.pinInChan];
IF netPin1.net = netPin2.net AND pin1.min = pin2.min THEN {
edge: Edge ← EnterAEdge[pin1, pin2, FALSE, TRUE];
edgeList ← InsertEdge[edge, edgeList]};
ENDLOOP;
ENDLOOP}; -- end of instProc
[ ] ← SCRowUtil.EnumerateAllInstsOnRow[handle, row, InstProc]};
[ ] ← SCRowUtil.EnumerateRows[handle, EachRow]};
MarkBuildInEdges: PROC [handle: SC.Handle, nets: SCPrivate.NetList] ~ {
EachRow: SCRowUtil.EachRowProc = {
EachRowProc: TYPE = PROC [row: SCPrivate.MaxRowSr, lgRow: SCPrivate.LgRow] RETURNS [quit: BOOLFALSE];
[ ] ← SCRowUtil.EnumerateAllInstsOnRow[handle, row, MarkBuildInEdgeOnInst]};
[ ] ← SCRowUtil.EnumerateRows[handle, EachRow]};
MarkBuildInEdgeOnInst: SCRowUtil.EachInstProc = {
EachInstProc: TYPE = PROC [pos: NAT, instance: SCPrivate.Instance] RETURNS [quit: BOOLFALSE];
FOR pinNum1: NAT IN [0 .. instance.pinNets.size) DO
netPin1: SCPrivate.PinNet ← instance.pinNets.n[pinNum1];
pin1: SCExprRoutePinsUtil.PinInChan ← NARROW[netPin1.pinInChan];
FOR pinNum2: NAT IN [pinNum1 + 1 .. instance.pinNets.size) DO
netPin2: SCPrivate.PinNet ← instance.pinNets.n[pinNum2];
pin2: SCExprRoutePinsUtil.PinInChan ← NARROW[netPin2.pinInChan];
IF netPin1.net = netPin2.net THEN {
compNo: NATMAX[pin1.component, pin2.component];
pin1.component ← compNo;
pin2.component ← compNo};
ENDLOOP;
ENDLOOP};
GetNetsSpan: PROC [handle: SC.Handle, nets: SCPrivate.NetList] ~ {
EachNet: PROC [net: SCPrivate.Net] ~ {
pinList: SCExprRoutePinsUtil.PinList ← NARROW[net.pinList];
edgeList: EdgeList ← NARROW[net.edgeList];
FOR pins: SCExprRoutePinsUtil.PinList ← pinList, pins.rest WHILE pins # NIL DO
pin: SCExprRoutePinsUtil.PinInChan ← pins.first;
pin.pinConn ← unconnected;
ENDLOOP;
FOR edges: EdgeList ← edgeList, edges.rest WHILE edges # NIL DO
pin1: SCExprRoutePinsUtil.PinInChan ← edges.first.pin1;
pin2: SCExprRoutePinsUtil.PinInChan ← edges.first.pin2;
IF pin1.chanNum = pin2.chanNum AND ~ edges.first.buildInEdge THEN {
IF pin1.pinConn = unconnected THEN pin1.pinConn ← left
ELSE IF pin1.pinConn = right THEN pin1.pinConn ← interior
ELSE SC.Error[programmingError, "overlaid graph edge"];
IF pin2.pinConn = unconnected THEN pin2.pinConn ← right
ELSE IF pin2.pinConn = left THEN pin2.pinConn ← interior
ELSE SC.Error[programmingError, "overlaid graph edge"]};
ENDLOOP};
FOR netList: SCPrivate.NetList ← nets, netList.rest WHILE netList # NIL DO
EachNet[netList.first];
ENDLOOP;
};
GetAllChanDensity: PROC [handle: SC.Handle] ~ {
EachChan: SCChanUtil.EachRowChanProc = {
[rowChan.chanDensity, rowChan.wireLength] ← SCNewWidth.ComputeDW[rowChan];
IF debug THEN {}};
[] ← SCChanUtil.EnumerateRowChans[handle, EachChan]};
RemoveGraph1: PROC [handle: SC.Handle, nets: SCPrivate.NetList] ~ {
EachNet: PROC [net: SCPrivate.Net] ~ {
pinList: SCExprRoutePinsUtil.PinList ← NARROW[net.pinList];
FOR pins: SCExprRoutePinsUtil.PinList ← pinList, pins.rest WHILE pins # NIL DO
pin: SCExprRoutePinsUtil.PinInChan ← pins.first;
pin.pinConn ← unconnected;
pin.adjList ← NIL;
pin.component ← 0;
ENDLOOP;
net.edgeList ← NIL};
FOR netList: SCPrivate.NetList ← nets, netList.rest WHILE netList # NIL DO
EachNet[netList.first];
ENDLOOP;
};
GenerateTrees1: PROC [handle: SC.Handle, nets: SCPrivate.NetList, edgeList: Edge] ~ {
WHILE edgeList # NIL DO
edge: Edge ← NIL;
edge ← MinEdge[edgeList];
edgeList ← AddTreeEdge1[handle, edgeList, edge];
GetAllRowWeights[handle];
edgeList ← ComputeWeights[handle, nets, edgeList, Cost1, EdgeTest1];
ENDLOOP;
};
GenerateTrees2: PROC [handle: SC.Handle, nets: SCPrivate.NetList, edgeList: Edge] ~ {
WHILE edgeList # NIL DO
edge: Edge ← NIL;
edge ← MaxEdge[edgeList];
edgeList ← DeleteGraphEdge2[handle, edgeList, edge];
edgeList ← ComputeWeights[handle, nets, edgeList, Cost2, EdgeTest2];
ENDLOOP;
};
MinEdge: PROC [edgeList: Edge] RETURNS [edge: Edge ← NIL] ~ {
minWeight: SC.Number ← LAST[INT];
FOR edges: Edge ← edgeList, edges.nextEdge WHILE edges # NIL DO
IF edges.weight < minWeight THEN {
minWeight ← edges.weight;
edge ← edges};
ENDLOOP;
};
MaxEdge: PROC [edgeList: Edge] RETURNS [edge: Edge ← NIL] ~ {
maxWeight: SC.Number ← FIRST[INT];
FOR edges: Edge ← edgeList, edges.nextEdge WHILE edges # NIL DO
IF edges.weight > maxWeight THEN {
maxWeight ← edges.weight;
edge ← edges};
ENDLOOP;
};
AddTreeEdge1: PROC [handle: SC.Handle, edgeList: Edge, edge: Edge] RETURNS[newEdgeList: Edge] ~ {
pinA, pinB: SCExprRoutePinsUtil.PinInChan;
compNo: NAT;
pin1: SCExprRoutePinsUtil.PinInChan ← edge.pin1;
pin2: SCExprRoutePinsUtil.PinInChan ← edge.pin2;
pinList: SCExprRoutePinsUtil.PinList ← NARROW[pin1.net.pinList];
newEdgeList ← edgeList;
IF edge.pin1.chanNum <= edge.pin2.chanNum THEN {
pinA ← edge.pin1;
pinB ← edge.pin2}
ELSE {
pinA ← edge.pin2;
pinB ← edge.pin1};
IF pinA.net # pinB.net THEN SC.Error[programmingError, "Invalid graph edge"];
FOR row: SCPrivate.MaxRowSr ← pinA.chanNum, row + 1 WHILE row < pinB.chanNum DO
loc: SC.Number ← pinA.min + (row - pinA.chanNum) * (pinB.min - pinA.min) / (pinB.chanNum - pinA.chanNum);
newEdges: Edge ← AddFT[handle, row, loc, pinA.net];
newEdgeList ← Append[newEdgeList, newEdges];
ENDLOOP;
compNo ← MAX[pinA.component, pinB.component]; ---Union operation
pinList ← NARROW[pin1.net.pinList];
FOR pins: SCExprRoutePinsUtil.PinList ← pinList, pins.rest WHILE pins # NIL DO
pin: SCExprRoutePinsUtil.PinInChan ← pins.first;
IF pin.component = pinA.component OR pin.component = pinB.component OR pin.component = 0 THEN
pin.component ← compNo;
ENDLOOP;
IF debug THEN {}
};
AddFT: PROC [handle: SC.Handle, row: SCPrivate.MaxRowSr, loc: SC.Number, net: SCPrivate.Net] RETURNS[newEdges: Edge ← NIL] ~ {
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
lgRows: SCPrivate.LgRows ← layoutData.lgRows;
lgRow: SCPrivate.LgRow ← lgRows.rows[row];
savPos: SCPrivate.MaxPosSr ← 1;
nodeList: SCExprRoutePinsUtil.PinList ← NIL;
ftInst: SCPrivate.Instance← NewFt[handle, net, lgRow];
savPos ← GetFTPos[handle, lgRow, loc];
SCPlaceUtil.PutLgPos[handle, ftInst, lgRow.rowNum, savPos, SCInstUtil.defltLgOrien, TRUE];
newEdges ← AddPinNodes[handle, row, ftInst];
SCInstUtil.AsgnChanPos[handle];
UpdateNodeLoc[handle]
};
GetFTPos: PROC [handle: SC.Handle, lgRow: SCPrivate.LgRow, loc: SC.Number] RETURNS [pos: SCPrivate.MaxPosSr ← 1] ~ {
WHILE pos <= lgRow.nLgsOnRow AND lgRow.rowOrg.p + lgRow.lgsOnRow[pos].offset < loc DO
pos ← pos + 1;
ENDLOOP;
};
NewFt: PUBLIC PROCEDURE[handle: SC.Handle, net: SCPrivate.Net, lgRow: SCPrivate.LgRow] RETURNS [ftInst: SCPrivate.Instance] = {
add ft to row width
get a component entry for the ft, construct a new entry for instance
parms: SCPrivate.Parms ← NARROW[handle.parms];
name: Rope.ROPEIO.PutFR["%g-%g", IO.rope[net.name], IO.int[lgRow.rowNum]];
ftInst ← SCInstUtil.DefineInstance[handle, name, parms.ftObject, NIL];
ftInst.ftNet ← net;
construct and add an entry to net list for this instance
SCNetUtil.AddConnection[handle, net, ftInst, parms.ftObject.pins.p[0], 0, ftPin];
SCNetUtil.AddConnection[handle, net, ftInst, parms.ftObject.pins.p[1], 1, ftPin]};
AddPinNodes: PROC [handle: SC.Handle, row: SCPrivate.MaxRowSr, ftInst: SCPrivate.Instance] RETURNS[newEdges: Edge ← NIL] ~ {
PinProc: SCInstUtil.EachPinProc = {
EachPinProc: TYPE = PROC [instance: SCPrivate.Instance, pin: NAT, netPin: SCPrivate.PinNet] RETURNS [quit: BOOLFALSE];
IF netPin.pin # NIL AND netPin.net # NIL THEN {
pd: SCInstUtil.PinDescription ← SCInstUtil.PosOf[instance, netPin.pin];
chan: NATIF pd.sideOn = bottom THEN row ELSE row + 1;
pinList: SCExprRoutePinsUtil.PinList ← NARROW[netPin.net.pinList];
tail: SCExprRoutePinsUtil.PinInChan;
alwaysUse: BOOLEAN ← netPin.net.externNet AND (chan = 1 AND SCNetUtil.ExitOnSide[handle, netPin.net, bottom]) OR (chan = rowChans.count AND SCNetUtil.ExitOnSide[handle, netPin.net, top]);
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;
tail ← SCExprRoutePinsUtil.EnterPin[rowChan: rowChans.chans[chan], min: min, max: min + rect.x2 - rect.x1, depth: 0, layer: netPin.pin.layer, net: netPin.net, side: RTBasic.OtherSide[pd.sideOn], alwaysUse: alwaysUse];
netPin.pinInChan ← tail;
FOR pinList1: SCExprRoutePinsUtil.PinList ← pinList, pinList1.rest WHILE pinList1 # NIL DO
pin1: SCExprRoutePinsUtil.PinInChan ← pinList1.first;
edge: Edge ← EnterAEdge[tail, pin1, FALSE, FALSE];
newEdges ← InsertEdge[edge, newEdges];
ENDLOOP;
pinList ← CONS[tail, pinList];
netPin.net.pinList ← pinList}};
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
rowChans: SCPrivate.RowChans ← layoutData.rowChans;
lgRows: SCPrivate.LgRows ← NARROW[handle.layoutData, SCPrivate.LayoutData].lgRows;
lgRow: SCPrivate.LgRow ← layoutData.lgRows.rows[row];
[ ] ← SCInstUtil.EnumeratePinsOnInst[ftInst, PinProc];
};
UpdateNodeLoc: PROC [handle: SC.Handle] ~ {
UpdateNodeLocInRow: SCRowUtil.EachRowProc ~ {
InstProc: SCRowUtil.EachInstProc = {
EachInstProc: TYPE = PROC [pos: NAT, instance: SCPrivate.Instance] RETURNS [quit: BOOLFALSE];
FOR pinNum: NAT IN [0 .. instance.pinNets.size) DO
netPin: SCPrivate.PinNet ← instance.pinNets.n[pinNum];
pin: SCExprRoutePinsUtil.PinInChan ← NARROW[netPin.pinInChan];
IF netPin.pin # NIL AND netPin.net # NIL AND pin # NIL THEN {
rowOffset: SC.Number ← lgRows.horzRowOrg + lgRow.rowOrg.p;
rect: CD.Rect ← SCInstUtil.RotateRect[instance, netPin.pin.rect];
pin.min ← rowOffset + instance.offset + rect.x1;
pin.max ← pin.min + rect.x2 - rect.x1};
ENDLOOP};
ExitProc: SCChanUtil.EachExitProc = {
EachExitProc: TYPE = PROC [exitNum: SCPrivate.MaxExitsSr, lrSide: SCPrivate.LRSide, rowChan: SCPrivate.RowChan, exit: SCPrivate.Exit] RETURNS [quit: BOOLFALSE];
pos: SC.Number ← IF lrSide = left THEN lgRows.horzRowOrg ELSE lgRows.horzRowOrg + lgRows.maxRowWidth;
pin: SCExprRoutePinsUtil.PinInChan ← NARROW[exit.pinInChan];
IF pin # NIL THEN pin.min ← pin.max ← pos
};
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
lgRows: SCPrivate.LgRows ← layoutData.lgRows;
rowChans: SCPrivate.RowChans ← layoutData.rowChans;
[ ] ← SCRowUtil.EnumerateAllInstsOnRow[handle, row, InstProc];
FOR lrSide: RTBasic.LRSide IN [left..right] DO
[] ← SCChanUtil.EnumerateExits[handle, rowChans.chans[row], lrSide, ExitProc];
[] ← SCChanUtil.EnumerateExits[handle, rowChans.chans[row+1], lrSide, ExitProc];
ENDLOOP;
};
[] ← SCRowUtil.EnumerateRows[handle, UpdateNodeLocInRow]};
DeleteGraphEdge2: PROC [handle: SC.Handle, edgeList: Edge, edge: Edge] RETURNS [newEdgeList: Edge ← NIL] ~ {
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
rowChans: SCPrivate.RowChans ← layoutData.rowChans;
pin1: SCExprRoutePinsUtil.PinInChan ← edge.pin1;
pin2: SCExprRoutePinsUtil.PinInChan ← edge.pin2;
IF pin1.chanNum # pin2.chanNum THEN SC.Error[programmingError, "Invalid Net Segment"];
IF pin1.pinConn = left THEN {
IF pin2.pinConn = right THEN pin2.pinConn ← unconnected
ELSE IF pin2.pinConn = interior THEN pin2.pinConn ← left
ELSE SC.Error[programmingError, "Bad net segment"];
pin1.pinConn ← unconnected}
ELSE IF pin1.pinConn = interior THEN {
IF pin2.pinConn = right THEN pin2.pinConn ← unconnected
ELSE IF pin2.pinConn = interior THEN pin2.pinConn ← left
ELSE SC.Error[programmingError, "Bad net segment"];
pin1.pinConn ← right}
ELSE SC.Error[programmingError, "Bad net segment"];
RemoveAEdge[handle, edge];
newEdgeList ← DeleteEdge[edge, edgeList];
MarkCutEdges[pin1.net];
[rowChans.chans[pin1.chanNum].chanDensity, rowChans.chans[pin1.chanNum].wireLength] ← SCNewWidth.ComputeDW[rowChans.chans[pin1.chanNum]]
};
RemoveAEdge: PROC [handle: SC.Handle, edge: Edge] ~ {
pin1: SCExprRoutePinsUtil.PinInChan ← edge.pin1;
pin2: SCExprRoutePinsUtil.PinInChan ← edge.pin2;
adjList1: EdgeList ← NARROW[pin1.adjList];
adjList2: EdgeList ← NARROW[pin2.adjList];
pin1.adjList ← DRemove[edge, adjList1];
pin2.adjList ← DRemove[edge, adjList2];
RemoveNetEdge[pin1.net, edge]
};
MarkCutEdges: PROC [net: SCPrivate.Net] ~ {
DFS: PROC [pin, father: SCExprRoutePinsUtil.PinInChan] RETURNS [minLabel: NAT ← 10000] ~ {
edgeList: EdgeList ← NARROW[pin.adjList];
IF pin.dfsLabel # 0 THEN minLabel ← pin.dfsLabel
ELSE {
labelNo ← labelNo + 1;
pin.dfsLabel ← labelNo;
minLabel ← labelNo;
FOR edges: EdgeList ← edgeList, edges.rest WHILE edges # NIL DO
edge: Edge ← edges.first;
nextPin: SCExprRoutePinsUtil.PinInChan ← IF pin = edge.pin1 THEN edge.pin2 ELSE edge.pin1;
IF nextPin # father THEN {
branchMin: NATDFS[nextPin, pin];
IF branchMin > pin.dfsLabel THEN edge.cutEdge ← TRUE
ELSE edge.cutEdge ← FALSE;
minLabel ← MIN[minLabel, branchMin]}
ENDLOOP}};
pinList: SCExprRoutePinsUtil.PinList ← NARROW[net.pinList];
labelNo: NAT ← 0;
FOR pins: SCExprRoutePinsUtil.PinList ← pinList, pins.rest WHILE pins # NIL DO
pin: SCExprRoutePinsUtil.PinInChan ← pins.first;
pin.dfsLabel ← 0;
ENDLOOP;
[] ← DFS[pinList.first, NIL];
IF debug THEN {}
};
MarkAllCutEdges: PROC [handle: SC.Handle, nets: SCPrivate.NetList] ~ {
FOR netLst: SCPrivate.NetList ← nets, netLst.rest WHILE netLst # NIL DO
MarkCutEdges[netLst.first];
ENDLOOP
};
Append: PUBLIC PROC [l1, l2: Edge] RETURNS[l3 : Edge] = {
z: Edge ← NIL;
IF l1 = NIL THEN l3 ← l2
ELSE {
z ← l1;
WHILE z.nextEdge # NIL DO
z ← z.nextEdge;
ENDLOOP;
z.nextEdge ← l2;
l2.prevEdge ← z;
l3 ←l1};
}; -- of Append
DRemove: PROC [ref: Edge, list: EdgeList] RETURNS[EdgeList] = {
l, l1: EdgeList ← NIL;
l ← list;
UNTIL l = NIL DO
IF Eq[l.first, ref] THEN {
IF l1 = NIL THEN RETURN[l.rest]; -- ref was first object on list
l1.rest ← l.rest;
RETURN[list];
};
l1 ← l;
l ← l.rest;
ENDLOOP;
RETURN [list];
}; -- of Dremove;
Eq: PROC [x, y: Edge] RETURNS[BOOL] = INLINE {RETURN[x = y]};
InsertEdge: PROC [edge, edgeList: Edge] RETURNS [newEdgeList: Edge] ~ {
IF edgeList = NIL THEN {
edgeList ← edge;
edge.prevEdge ← NIL;
edge.nextEdge ← NIL}
ELSE {
edge.nextEdge ← edgeList;
edgeList.prevEdge ← edge;
edgeList ← edge};
newEdgeList ← edgeList
};
DeleteEdge: PROC [edge, edgeList: Edge] RETURNS [newEdgeList: Edge] ~ {
IF edge.prevEdge = NIL THEN {
edgeList ← edge.nextEdge;
edge.nextEdge.prevEdge ← NIL;
edge.nextEdge ← NIL}
ELSE {
edge.prevEdge.nextEdge ← edge.nextEdge;
edge.nextEdge.prevEdge ← edge.prevEdge;
edge.prevEdge ← NIL;
edge.nextEdge ← NIL};
newEdgeList ← edgeList
};
}.