SCExprGlobalRouteImpl.mesa
Copyright Ó 1987 by Xerox Corporation. All rights reserved.
Jason Cong, August 28, 1987 2:33:06 pm PDT
Jean-Marc Frailong October 11, 1987 4:26:30 pm PDT
Bryan Preas March 28, 1988 4:29:08 pm PST
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;
SCExprGlobalRouteImpl:
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: BOOLEAN ← TRUE;
Edge: TYPE ~ REF EdgeRec;
EdgeRec:
TYPE ~
RECORD[
pin1, pin2: SCExprRoutePinsUtil.PinInChan,
cutEdge, buildInEdge: BOOLEAN,
weight: SC.Number
];
EdgeList: TYPE = LIST OF Edge;
WeightFun: TYPE = PROC[handle: SC.Handle, edge: Edge] RETURNS[cost: SC.Number];
EdgeTest:
TYPE =
PROC [edge: Edge]
RETURNS [delete:
BOOLEAN ←
FALSE];
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];
[lgRows.maxRowWidth, lgRows.numMaxRows] ← SCRowUtil.FindMaxRow[handle];
hvRatio ← lgRows.maxRowWidth / 2;
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: EdgeList ← 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];
RemoveUnusedFTs[handle, nets];
};
DecideEdgesInNets:
PROC [handle:
SC.Handle, nets: SCPrivate.NetList] ~ {
edgeList: EdgeList ← 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: BOOL ← FALSE];
IF onChan[(chan) - 1] THEN AddExit[handle, rowChan, side, net]};
EachPinProc: SCNetUtil.EachPinProc = {
PROC [netPin: SCPrivate.NetPin] RETURNS [quit: BOOL ← FALSE];
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 {
must compute the channel to put the exit on
ChanProc: SCChanUtil.EachRowChanProc = {
PROC [chan: SCPrivate.MaxChanSr, rowChan: SCPrivate.RowChan] RETURNS [quit: BOOL ← FALSE];
chanPos: SC.Number ← rowChan.chanPos + rowChan.chanWidth/2;
dist: SC.Number ← ABS[chanPos - holdBpPos];
useThisChan: BOOLEAN ← (1 < chan AND chan < rowChans.count) OR (chan = 1 AND rowChans.count = 2);
IF useThisChan AND dist < minDist THEN {minDistChan ← chan; minDist ← dist};
IF useThisChan
AND touchesChan[(chan)-1]
THEN {
IF chanPos > maxChanPos THEN {maxChan ← chan; maxChanPos ← chanPos};
IF chanPos < minChanPos THEN {minChan ← chan; minChanPos ← chanPos}}};
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 => SC.Error[programmingError, "Not suppose to happen."]}}};
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: BOOL ← FALSE];
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
rowChans: SCPrivate.RowChans ← layoutData.rowChans;
SCExprRoutePinsUtil.InitGetChanPins[handle, rowChan];
IF rowChan.chanNum = 1
THEN {
SCNewWidth.EnterSideData[rowChan, handle, bottom, top, bottom];
SCNewWidth.EnterRowData[rowChan, handle, 1, bottom]}
ELSE
IF rowChan.chanNum = rowChans.count
THEN {
SCNewWidth.EnterRowData[rowChan, handle, lgRows.count, top];
SCNewWidth.EnterSideData[rowChan, handle, top, bottom, 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: EdgeList ←
NIL] ~ {
--build complete graph for nets.
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 ← CONS[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] ~ {
--compute weight for each row.
EachRow: SCRowUtil.EachRowProc = {
EachRowProc: TYPE = PROC [row: SCPrivate.MaxRowSr, lgRow: SCPrivate.LgRow] RETURNS [quit: BOOL ← FALSE];
lgRow.weight ← 1};
[] ← SCRowUtil.EnumerateRows[handle, EachRow]};
ComputeWeights:
PROC [handle:
SC.Handle, nets: SCPrivate.NetList, edgeList: EdgeList,
Cost: WeightFun,
DeleteTest: EdgeTest]
RETURNS[ EdgeList ] ~ {
edges: EdgeList ← NIL;
WHILE edgeList #
NIL
AND DeleteTest[edgeList.first]
DO
edgeList ← edgeList.rest;
ENDLOOP;
IF edgeList #
NIL THEN
edgeList.first.weight ← Cost[handle, edgeList.first];
edges ← edgeList;
WHILE edges #
NIL
DO
IF edges.rest #
NIL
THEN
IF DeleteTest[edges.rest.first]
THEN
edges.rest ← edges.rest.rest
ELSE { edges.rest.first.weight ← Cost[handle, edges.rest.first];
edges ← edges.rest}
ELSE EXIT;
ENDLOOP;
RETURN[edgeList];
};
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 ← LengthE[edge];
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;
};
LengthE:
PROC [edge: Edge]
RETURNS [length:
SC.Number] ~ {
length ← ABS[edge.pin1.min - edge.pin2.min]
};
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: BOOLEAN ← FALSE];
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: BOOLEAN ← FALSE];
IF edge.cutEdge
OR edge.buildInEdge
THEN
delete ← TRUE
ELSE delete ← FALSE
};
BuildGraphs2:
PROC [handle:
SC.Handle, nets: SCPrivate.NetList]
RETURNS [edgeList: EdgeList ←
NIL] ~ {
SortAllChanPins[handle];
edgeList ← EnterNetEdges[handle, nets];
edgeList ← Nconc[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: EdgeList ←
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 ← CONS[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: EdgeList ←
NIL] ~ {
EachRow: SCRowUtil.EachRowProc = {
EachRowProc: TYPE = PROC [row: SCPrivate.MaxRowSr, lgRow: SCPrivate.LgRow] RETURNS [quit: BOOL ← FALSE];
InstProc: SCRowUtil.EachInstProc = {
EachInstProc: TYPE = PROC [pos: NAT, instance: SCPrivate.Instance] RETURNS [quit: BOOL ← FALSE];
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 ← CONS[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: BOOL ← FALSE];
[ ] ← SCRowUtil.EnumerateAllInstsOnRow[handle, row, MarkBuildInEdgeOnInst]};
[ ] ← SCRowUtil.EnumerateRows[handle, EachRow]};
MarkBuildInEdgeOnInst: SCRowUtil.EachInstProc = {
EachInstProc: TYPE = PROC [pos: NAT, instance: SCPrivate.Instance] RETURNS [quit: BOOL ← FALSE];
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: NAT ← MAX[pin1.component, pin2.component];
pin1.component ← compNo;
pin2.component ← compNo};
ENDLOOP;
ENDLOOP};
GetNetsSpan:
PROC [handle:
SC.Handle, nets: SCPrivate.NetList] ~ {
-- to decide pin connections, we folow the rule : left + right -> interior
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] ~ {
-- we only remove edges! nodes are shared by stage 2.
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;
};
RemoveUnusedFTs:
PROC [handle:
SC.Handle, nets: SCPrivate.NetList] ~ {
};
GenerateTrees1:
PROC [handle:
SC.Handle, nets: SCPrivate.NetList, edgeList: EdgeList] ~ {
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: EdgeList] ~ {
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: EdgeList]
RETURNS [edge: Edge ←
NIL] ~ {
minWeight: SC.Number ← LAST[INT];
FOR edges: EdgeList ← edgeList, edges.rest
WHILE edges #
NIL
DO
IF edges.first.weight < minWeight
THEN {
minWeight ← edges.first.weight;
edge ← edges.first};
ENDLOOP;
};
MaxEdge:
PROC [edgeList: EdgeList]
RETURNS [edge: Edge ←
NIL] ~ {
-- Maybe we should break tie by wire length
maxWeight: SC.Number ← FIRST[INT];
FOR edges: EdgeList ← edgeList, edges.rest
WHILE edges #
NIL
DO
IF edges.first.weight > maxWeight
THEN {
maxWeight ← edges.first.weight;
edge ← edges.first}
ELSE
IF edges.first.weight = maxWeight
THEN
{IF LengthE[edges.first] > LengthE[edge] THEN edge ← edges.first};
ENDLOOP;
};
AddTreeEdge1:
PROC [handle:
SC.Handle, edgeList: EdgeList, edge: Edge]
RETURNS[newEdgeList: EdgeList] ~ {
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 + 1) * (pinB.min - pinA.min) / (pinB.chanNum - pinA.chanNum + 1);
newEdges: EdgeList ← AddFT[handle, row, loc, pinA.net];
newEdgeList ← Nconc[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: EdgeList ←
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.ROPE ← IO.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: EdgeList ←
NIL] ~ {
PinProc: SCInstUtil.EachPinProc = {
EachPinProc: TYPE = PROC [instance: SCPrivate.Instance, pin: NAT, netPin: SCPrivate.PinNet] RETURNS [quit: BOOL ← FALSE];
IF netPin.pin #
NIL
AND netPin.net #
NIL
THEN {
pd: SCInstUtil.PinDescription ← SCInstUtil.PosOf[instance, netPin.pin];
chan: NAT ← IF 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 ← CONS[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: BOOL ← FALSE];
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: BOOL ← FALSE];
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: EdgeList, edge: Edge]
RETURNS [newEdgeList: EdgeList ←
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"];
-- re-compute net span
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 ← DRemove[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] ~ {
edgeList: EdgeList ← NARROW[pin.adjList];
labelNo ← labelNo + 1;
pin.dfsLabel ← labelNo;
pin.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.dfsLabel = 0
THEN {
DFS[nextPin, pin];
pin.minLabel ← MIN[pin.minLabel, nextPin.minLabel];
IF nextPin.minLabel > pin.dfsLabel THEN edge.cutEdge ← TRUE
ELSE edge.cutEdge ← FALSE
}
ELSE
--node has been visited
IF nextPin # father THEN
pin.minLabel ← MIN[pin.minLabel, nextPin.minLabel];
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: EdgeList, l2: EdgeList ←
NIL]
RETURNS[val: EdgeList] = {
z: EdgeList ← NIL;
val ← l2;
IF l1 = NIL THEN RETURN[val];
val ← CONS[l1.first, val];
z ← val;
UNTIL (l1 ← l1.rest) =
NIL
DO
z.rest ← CONS[l1.first, z.rest];
z ← z.rest;
ENDLOOP;
RETURN[val];
}; -- of Append
Remove:
PUBLIC
PROC [ref: Edge, list: EdgeList]
RETURNS[val: EdgeList] = {
z: EdgeList ← NIL;
val ← NIL;
UNTIL list =
NIL
DO
IF ~Eq[list.first, ref]
THEN
{IF val = NIL THEN {val ← CONS[list.first, NIL]; z ← val}
ELSE {z.rest ← CONS[list.first, z.rest]; z ← z.rest}};
list ← list.rest;
ENDLOOP;
}; -- of Remove
Eq:
PROC [x, y: Edge]
RETURNS[
BOOL] =
INLINE {
RETURN[x = y]};
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;
Nconc:
PROC [l1, l2: EdgeList]
RETURNS[EdgeList] = {
z: EdgeList ← l1;
IF z = NIL THEN RETURN[l2];
UNTIL z.rest =
NIL
DO
z ← z.rest;
ENDLOOP;
z.rest ← l2;
RETURN[l1];
};
}.