[Pixel]<DATools7.0>NewSC25>SCExprGlobalRouteImpl.mesa!2

SCExprGlobalRouteImpl.mesa

Jason Cong, August 28, 1987 2:33:06 pm PDT

Jean-Marc Frailong October 11, 1987 4:26:30 pm PDT

Bryan Preas March 26, 1988 6:05:12 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;

};

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[ newEdges: EdgeList ← NIL] ~ {

FOR edges: EdgeList ← edgeList, edges.rest WHILE edges # NIL DO

edge: Edge ← edges.first;

IF ~ DeleteTest[edge] THEN {

edge.weight ← Cost[handle, edge];

newEdges ← CONS[edge, newEdges]};

ENDLOOP

};

RemoveNetEdge: PROC[net: SCPrivate.Net, edge: Edge] = {

remove a net edge from net.edgelist

netEdges: EdgeList ← NARROW[net.edgeList];

net.edgeList ← Remove[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;

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 ← 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: 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};

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 ← 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: 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 ← Remove[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 ← Remove[edge, adjList1];

pin2.adjList ← Remove[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: NAT ← DFS[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: 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]};