<> <> <> <> <> <<>> <> <<>> 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] = { <> <<>> 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 / 8; 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] = {}; <> GlobalRouteAllNets: PUBLIC PROCEDURE[handle: SC.Handle] = { <> 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] = { <> <> ChanExitProc: SCChanUtil.EachRowChanProc = { <> IF onChan[(chan) - 1] THEN AddExit[handle, rowChan, side, net]}; EachPinProc: SCNetUtil.EachPinProc = { <> instance: SCPrivate.Instance _ netPin.instance; pin: SCPrivate.ObjectPin _ netPin.pin; <> 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 { <> ChanProc: SCChanUtil.EachRowChanProc = { <> 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; <> [] _ SCChanUtil.EnumerateRowChans[handle, ChanProc]; <> 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]; <<>> <> [] _ SCChanUtil.EnumerateRowChans[handle, ChanExitProc]}; AddExit: PUBLIC PROCEDURE[handle: SC.Handle, rowChan: SCPrivate.RowChan, side: SC.Side, net: SCPrivate.Net] = { <> 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 = { <> <<>> 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 = { <> IF lgRow.size.p = maxRowWidth THEN lgRow.weight _ 4 ELSE lgRow.weight _ 1}; maxRowWidth, maxRowNo : SC.Number _ 0; [maxRowWidth, maxRowNo] _ SCRowUtil.FindMaxRow[handle]; [] _ 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] = { <> netEdges: EdgeList _ NARROW[net.edgeList]; net.edgeList _ DRemove[edge, netEdges]}; Cost1: WeightFun = { <> 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 = { <> <<>> 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 = { <> <<>> pin1: SCExprRoutePinsUtil.PinInChan _ edge.pin1; pin2: SCExprRoutePinsUtil.PinInChan _ edge.pin2; IF (pin1.component = pin2.component) THEN delete _ TRUE ELSE delete _ FALSE; }; EdgeTest2: EdgeTest = { <> <<>> 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 = { <> InstProc: SCRowUtil.EachInstProc = { <> 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 = { <> [ ] _ SCRowUtil.EnumerateAllInstsOnRow[handle, row, MarkBuildInEdgeOnInst]}; [ ] _ SCRowUtil.EnumerateRows[handle, EachRow]}; MarkBuildInEdgeOnInst: SCRowUtil.EachInstProc = { <> 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; <> 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] = { <> <> 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; <<>> <> 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 = { <> 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 = { <> 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 = { <> 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]; }; }.