SCRouteImpl.mesa: Implementation of SC.DetailedRoute
Frank Bowers November 20, 1985 4:40:40 pm PST
DIRECTORY
CD,
CDBasics,
CDCells,
CDDirectory,
CDOrient,
CDPinObjects,
CDProperties,
CDRects,
PW,
PWPins,
PWRoute,
Rope,
Route,
RouteTechnology,
RTBasic,
SC,
SCChanUtil,
SCInstUtil,
SCPrivate,
SCRowUtil,
SCUtil;
SCRouteImpl:
CEDAR
PROGRAM
IMPORTS CDBasics, CDCells, CDDirectory, CDPinObjects, CDProperties, CDRects, PW, PWRoute, Rope, Route, RouteTechnology, SCChanUtil, SCInstUtil, SCRowUtil, SCUtil
EXPORTS SCPrivate
SHARES SC = BEGIN
RowCellArray: TYPE = ARRAY [1..SCPrivate.maxLgRows] OF PW.Object;
RowCells: TYPE = REF RowCellArray;
NumSeqRec:
TYPE =
RECORD [
c: SEQUENCE size: NAT OF REF SC.Number];
NumSeq: TYPE = REF NumSeqRec;
LRSide: TYPE = SCPrivate.LRSide;
TBSide: TYPE = SCPrivate.TBSide;
LayoutData: TYPE = SCPrivate.LayoutData;
ROPE: TYPE = Rope.ROPE;
PQPos: TYPE = RTBasic.PQPos;
CreatePinsForChannel:
PROC [handle:
SC.Handle, chan:
NAT, rowCells: RowCells] =
BEGIN
side: SC.Side;
row: NAT ← 0;
layoutData: SCPrivate.LayoutData ← NARROW[handle.layoutData];
lgRows: SCPrivate.LgRows ← layoutData.lgRows;
MakeNetPin: SCInstUtil.EachPinProc = {
[instance: SCPrivate.Instance, pin: NAT, netPin: SCPrivate.PinNet]
IF side = SCInstUtil.PosOf[instance, netPin.pin].sideOn
THEN {
rect: CD.Rect ← SCInstUtil.RotateRect[instance, netPin.pin.rect];
pinOb: CD.Object ← CDPinObjects.CreatePinOb[CDBasics.SizeOfRect[rect]];
pinInst: CD.Instance;
position: CD.Position ← SCUtil.PQToXY[handle, [p: instance.offset + rect.x1, q: rect.y1]];
pinInst ← PW.IncludeInCell[cell: rowCells[row], obj: pinOb, position: position];
CDPinObjects.SetName[pinInst, netPin.net.name];
CDPinObjects.SetLayer[pinInst, netPin.pin.layer];
};
};
ForEachInstance: SCRowUtil.EachInstProc = {
[] ← SCInstUtil.EnumeratePinsOnInst[instance, MakeNetPin]};
IF chan = 1
THEN {
side ← bottom; row ← 1;
[] ← SCRowUtil.EnumerateAllInstsOnRow[handle, row, ForEachInstance]}
ELSE
IF chan = lgRows.count + 1
THEN {
side ← top; row ← lgRows.count;
[] ← SCRowUtil.EnumerateAllInstsOnRow[handle, row, ForEachInstance]}
ELSE {
side ← top; row ← chan - 1;
[] ← SCRowUtil.EnumerateAllInstsOnRow[handle, row, ForEachInstance];
side ← bottom; row ← chan;
[] ← SCRowUtil.EnumerateAllInstsOnRow[handle, row, ForEachInstance]};
END;
CreateExitsForChannel:
PROC [handle:
SC.Handle, rowChan: SCPrivate.RowChan, exitCells:
REF
ARRAY LRSide
OF
PW.ListOb] =
BEGIN
cell: CD.Object ← NIL;
parms: SCPrivate.Parms ← NARROW[handle.parms];
design: CD.Design ← parms.cdDesign;
CreateNewExit: SCChanUtil.EachExitProc = {
pinOb: CD.Object ← CDPinObjects.CreatePinOb[size: [0, 0]];
pinInst: CD.Instance ← PW.IncludeInCell[cell: cell, obj: pinOb];
CDPinObjects.SetName[pinInst, exit.net.name];
CDPinObjects.SetLayer[pinInst, exit.layer];
};
FOR side: LRSide
IN LRSide
DO
cell ← PW.CreateEmptyCell[];
[] ← SCChanUtil.EnumerateExits[handle, rowChan, side, CreateNewExit];
PW.IncludeInDirectory[design, cell, "Exits"];
exitCells[side] ← CONS[cell, exitCells[side]];
ENDLOOP;
END;
RouteChannelRetrieveImpl.StitchVias accross where branch overlaps trunk
CreateWireAndContact:
PROC [
handle: SC.Handle, pin: PW.Instance, length: CD.Number, trunkLayer: CD.Layer]
RETURNS [obj: CD.Object] =
BEGIN
parms: SCPrivate.Parms ← NARROW[handle.parms];
design: CD.Design ← parms.cdDesign;
wire, contact: CD.Object;
obj ← PW.CreateEmptyCell[];
wire ← CreateWireFromPin[handle, pin, length, design];
contact ← RouteTechnology.GetContact[handle.rules.sideRules, CDPinObjects.GetLayer[pin], trunkLayer];
[] ← PW.IncludeInCell[obj, wire];
[] ← PW.IncludeInCell[obj, contact, [length-contact.size.x, 0]];
PW.IncludeInDirectory[design, obj, "Wire"];
END;
CreateWireFromPin:
PROC [handle:
SC.Handle, pin:
PW.Instance, length:
CD.Number, design:
CD.Design]
RETURNS [wire: CD.Object] =
BEGIN
wx: CD.Number ← length;
wy: CD.Number ← pin.ob.size.y;
wSize: CD.Position ← SCUtil.PQToXY[handle, [wx, wy]];
layer: CD.Layer ← CDPinObjects.GetLayer[pin];
wire ← CDRects.CreateRect[wSize, layer];
END;
GetPinPos:
PROC [handle:
SC.Handle, wireLen:
CD.Number, inst:
PW.Instance, side: LRSide]
RETURNS [pos: CD.Position] =
BEGIN
pos ← [0, 0];
pos.x ←
SELECT side
FROM
left => 0,
right => wireLen - inst.ob.size.x,
ENDCASE => ERROR;
pos ← SCUtil.PQToXY[handle, [pos.x, pos.y]];
END;
AlwaysExtendPin:
PROC [handle:
SC.Handle, inst:
PW.Instance, extLen:
CD.Number]
RETURNS [obj: CD.Object] =
BEGIN
create wire and copy pin to end of wire
parms: SCPrivate.Parms ← NARROW[handle.parms];
design: CD.Design ← parms.cdDesign;
pinOb, wire: CD.Object;
pinInst: CD.Instance;
pinSize: CD.Position ← SCUtil.PQToXY[handle, [inst.ob.size.x, inst.ob.size.y]];
obj ← PW.CreateEmptyCell[];
wire ← CreateWireFromPin[handle, inst, extLen, design];
pinOb ← CDPinObjects.CreatePinOb[pinSize];
[] ← PW.IncludeInCell[obj, wire];
pinInst ← PW.IncludeInCell[obj, pinOb, [extLen-inst.ob.size.x, 0]];
CDPinObjects.SetName[pinInst, CDPinObjects.GetName[inst]];
CDPinObjects.SetLayer[pinInst, CDPinObjects.GetLayer[inst]];
PW.IncludeInDirectory[design, obj, "Wire"];
END;
ExtendPowerBuses:
PROC [handle:
SC.Handle, design:
CD.Design, rowList:
PW.ListOb]
RETURNS [rows: PW.ListOb ← NIL] =
BEGIN
extend power buses to length of longest row
ext: ARRAY LRSide OF PW.Object ← ALL[NIL];
extLen: CD.Number;
side: LRSide;
rl: PW.ListOb ← NIL;
abutOb: PW.Object;
pwSide: PWPins.Side;
layout: LayoutData ← NARROW[handle.layoutData];
maxRowLength: CD.Number ← SCRowUtil.FindMaxRow[handle].maxRowWidth;
ExtendPin:
PW.ForEachPinProc = {
obj ← AlwaysExtendPin[handle, inst, extLen]};
FOR rl ← rowList, rl.rest
UNTIL rl =
NIL
DO
rowLength: CD.Number ← PW.IRSize[rl.first].x;
ext ← ALL[NIL];
IF rowLength < maxRowLength
THEN
FOR side
IN LRSide
DO
extLen ←
SELECT side
FROM
left => (maxRowLength - rowLength)/2,
right => maxRowLength - rowLength - (maxRowLength - rowLength)/2,
ENDCASE => ERROR;
pwSide ← SELECT side FROM right => right, left => left, ENDCASE => ERROR;
ext[side] ← PW.TransferCell[design: design, template: rl.first, objSide: pwSide, width: extLen, objProc: ExtendPin];
ENDLOOP;
abutOb ← PW.AbutListX[design, LIST [ext[left], rl.first, ext[right]]];
rows ← CONS[CDDirectory.Expand[me: abutOb, to: design, from: design], rows];
ENDLOOP;
END;
CreateRowCell:
PROC [handle:
SC.Handle, row:
NAT, rowList:
PW.ListOb, rowCells: RowCells]
RETURNS [PW.ListOb] =
BEGIN
parms: SCPrivate.Parms ← NARROW[handle.parms];
design: CD.Design ← parms.cdDesign;
rowOb: PW.Object ← NIL;
listOb: PW.ListOb ← NIL;
rCell: CD.Object ← NIL; -- cell obtained from rowOb
ForEachInstance: SCRowUtil.EachInstProc = {
thisObj: CD.Object ← instance.object.cdOb;
listOb ← CONS[thisObj, listOb]};
[] ← SCRowUtil.EnumerateAllInstsOnRow[handle, row, ForEachInstance];
listOb ← PW.Reverse[listOb];
rowOb ← PW.AbutListX[design: design, listOb: listOb];
rCell ← CDDirectory.Expand[me: rowOb, from: design, to: design];
rowList ← CONS[rCell, rowList];
rowCells[row] ← rCell;
RETURN[rowList];
END;
EnablePinDeepEnumeration:
PROC [rowList:
PW.ListOb] =
BEGIN
FOR rl:
PW.ListOb ← rowList, rl.rest
UNTIL rl =
NIL
DO
cellPtr: CD.CellPtr ← NARROW[rl.first.specificRef];
FOR list:
CD.InstanceList ← cellPtr.contents, list.rest
UNTIL list =
NIL
DO
IF CDCells.IsCell[list.first.ob]
THEN {
cp:
CD.CellPtr ←
NARROW[list.first.ob.specificRef];
FOR iList:
CD.InstanceList ← cp.contents, iList.rest
UNTIL iList =
NIL
DO
IF CDCells.IsCell[iList.first.ob]
THEN
CDProperties.PutPropOnInstance[iList.first, $StopEnumerateDeepPins, NIL];
ENDLOOP;
};
ENDLOOP;
ENDLOOP;
END;
DisablePinDeepEnumeration:
PROC [rowList:
PW.ListOb] =
BEGIN
FOR rl:
PW.ListOb ← rowList, rl.rest
UNTIL rl =
NIL
DO
cellPtr: CD.CellPtr ← NARROW[rl.first.specificRef];
FOR list:
CD.InstanceList ← cellPtr.contents, list.rest
UNTIL list =
NIL
DO
IF CDCells.IsCell[list.first.ob]
THEN {
cp:
CD.CellPtr ←
NARROW[list.first.ob.specificRef];
FOR iList:
CD.InstanceList ← cp.contents, iList.rest
UNTIL iList =
NIL
DO
IF CDCells.IsCell[iList.first.ob]
THEN
CDProperties.PutPropOnInstance[iList.first, $StopEnumerateDeepPins, $TRUE];
ENDLOOP;
};
ENDLOOP;
ENDLOOP;
END;
LogicRoute:
PROC [handle:
SC.Handle, design:
CD.Design]
RETURNS [logicOb:
PW.Object] =
BEGIN
exitCells: REF ARRAY LRSide OF PW.ListOb ← NEW[ARRAY LRSide OF PW.ListOb ← ALL[NIL]];
rowList: PW.ListOb ← NIL;
rowCells: RowCells ← NEW[RowCellArray];
abutOb: PW.Object;
ForEachRow: SCRowUtil.EachRowProc = {
rowList ← CreateRowCell[handle, row, rowList, rowCells];
};
ForEachChannel: SCChanUtil.EachRowChanProc = {
CreatePinsForChannel[handle: handle, chan: chan, rowCells: rowCells];
CreateExitsForChannel[handle: handle, rowChan: rowChan, exitCells: exitCells];
};
SCInstUtil.AllOffsets[handle];
[] ← SCRowUtil.EnumerateRows[handle: handle, eachRow: ForEachRow];
[] ← SCChanUtil.EnumerateRowChans[handle: handle, eachRowChan: ForEachChannel];
rowList ← ExtendPowerBuses[handle, design, rowList];
logicOb ← rowCells[1];
DisablePinDeepEnumeration[rowList];
abutOb ← PWRoute.AbutChRouteListY[
design: design, listOb: rowList, rightListOb: exitCells[right], leftListOb: exitCells[left]
! Route.Signal => RESUME];
logicOb ← CDDirectory.Expand[me: abutOb, to: design, from: design];
EnablePinDeepEnumeration[rowList];
END;
IncludeTrunkPin:
PROC [handle:
SC.Handle, cell:
CD.Object, name:
ROPE, tbSide: TBSide, trunkSize, trunkPos: PQPos, layer:
CD.Layer] =
BEGIN
pin: CD.Object ← CDPinObjects.CreatePinOb[[trunkSize.p, trunkSize.p]];
pos: CD.Position;
pinInst: CD.Instance;
trunkPos.q ← trunkPos.q + (IF tbSide = top THEN trunkSize.q - trunkSize.p ELSE 0);
pos ← SCUtil.PQToXY[handle, trunkPos];
pinInst ← PW.IncludeInCell[cell, pin, pos];
CDPinObjects.SetName[pinInst, name];
CDPinObjects.SetLayer[pinInst, layer];
END;
PowerRoute:
PROC [handle:
SC.Handle, pwOb:
PW.Object, design:
CD.Design]
RETURNS [ob: PW.Object] =
BEGIN
ext end power pins on edges and put in power rails
ext: ARRAY LRSide OF PW.Object ← ALL[NIL];
trunkLayer: CD.Layer ← handle.rules.sideRules.trunkLayer;
pwSide: PWPins.Side;
pBus: SCPrivate.PowerBus;
side: LRSide;
trunk, abutOb: CD.Object;
trunkSize, trunkPos: PQPos;
extLen, width, trunkWidth: SC.Number;
layout: LayoutData ← NARROW[handle.layoutData];
ExtendPin:
PW.ForEachPinProc = {
name: ROPE ← CDPinObjects.GetName[inst];
otherPBus: SCPrivate.PowerBus = layout.powerBuses[IF side = right THEN left ELSE right];
SELECT
TRUE
FROM
Rope.Equal[name, pBus.name] =>
obj ← CreateWireAndContact[handle, inst, width, trunkLayer];
Rope.Equal[name, otherPBus.name] => NULL;
ENDCASE => obj ← AlwaysExtendPin[handle, inst, width]};
FOR side
IN LRSide
DO
pBus ← layout.powerBuses[side];
width ← 20; -- pBus.width; (width was 0)?
trunkWidth ← 10; -- pBus.net.trunkWidth; (net was NIL)?
extLen ← width - trunkWidth;
trunkSize ← [p: trunkWidth, q: PW.IRSize[pwOb].y];
trunkPos ← [IF side = right THEN extLen ELSE 0, 0];
pwSide ← SELECT side FROM right => right, left => left, ENDCASE => ERROR;
ext[side] ← PW.TransferCell[design: design, template: pwOb, objSide: pwSide, width: width, objProc: ExtendPin];
trunk ← MakeTrunk[handle: handle, trunkSize: trunkSize, lev: trunkLayer];
[] ← PW.IncludeInCell[ext[side], trunk, SCUtil.PQToXY[handle, trunkPos]];
FOR tbSide: TBSide
IN TBSide
DO
IncludeTrunkPin[handle, ext[side], pBus.name, tbSide, trunkSize, trunkPos , trunkLayer];
ENDLOOP;
ENDLOOP;
abutOb ← PW.AbutListX[design, LIST [ext[left], pwOb, ext[right]]];
ob ← CDDirectory.Expand[me: abutOb, to: design, from: design];
END;
MakeTrunk:
PROC [handle:
SC.Handle, trunkSize: PQPos, lev:
CD.Layer]
RETURNS [obj: CD.Object] =
BEGIN
parms: SCPrivate.Parms ← NARROW[handle.parms];
design: CD.Design ← parms.cdDesign;
obj ← CDRects.CreateRect[SCUtil.PQToXY[handle, trunkSize], lev];
END;
AcBusForName:
PROC [handle:
SC.Handle, side: LRSide, name:
ROPE]
RETURNS [acBus: SCPrivate.AcBus ←
NIL, i:
NAT] =
BEGIN
layout: LayoutData ← NARROW[handle.layoutData];
sigs: SCPrivate.AcBusSigs ← layout.acBuses[side].sigs;
FOR i
IN [0..sigs.size)
DO
IF Rope.Equal[name, sigs[i].name] THEN RETURN [sigs[i], i];
ENDLOOP;
END;
ComputeTrunkEnd:
PROC [trunkEnd: NumSeq, q:
SC.Number, index:
NAT, fromTB: TBSide] =
BEGIN
prev: REF SC.Number ← trunkEnd[index];
trunkEnd[index] ← NEW[SC.Number];
trunkEnd[index]^ ←
IF prev =
NIL
THEN q
ELSE
SELECT fromTB
FROM
top => MIN[q, prev^],
bottom => MAX[q, prev^],
ENDCASE => ERROR;
END;
CreateAcTrunks:
PROC [handle:
SC.Handle, cell:
CD.Object, acBusSide: SCPrivate.AcBusSides, trunkEnd: NumSeq, layer:
CD.Layer] =
BEGIN
side: LRSide;
trunk: CD.Object;
trunkSize, trunkPos: PQPos;
bus: SCPrivate.AcBus;
parms: SCPrivate.Parms ← NARROW[handle.parms];
design: CD.Design ← parms.cdDesign;
FOR i:
NAT
IN [0..acBusSide.sigs.size)
DO
bus ← acBusSide.sigs[i];
side ← bus.onSide;
trunkPos.p ←
SELECT side
FROM
left => PW.IRSize[cell].x - bus.depth, right => bus.depth, ENDCASE => ERROR;
trunkPos.q ←
SELECT bus.fromTB
FROM
bottom => 0, top => trunkEnd[i]^, ENDCASE => ERROR;
trunkSize.p ← bus.net.trunkWidth;
trunkSize.q ←
SELECT bus.fromTB
FROM
bottom => trunkEnd[i]^, top => PW.IRSize[cell].y - trunkEnd[i]^, ENDCASE => ERROR;
trunk ← MakeTrunk[handle: handle, trunkSize: trunkSize, lev: layer];
[] ← PW.IncludeInCell[cell, trunk, SCUtil.PQToXY[handle, trunkPos]];
IncludeTrunkPin[handle, cell, bus.name, bus.fromTB, trunkSize, trunkPos, layer];
ENDLOOP;
END;
ClockRoute:
PROC [handle:
SC.Handle, pwOb:
PW.Object, design:
CD.Design]
RETURNS [ob: PW.Object] =
BEGIN
trunkEnd: NumSeq; -- "q" coordinate of trunk end point
ext: ARRAY LRSide OF PW.Object ← ALL[NIL];
trunkLayer: CD.Layer ← handle.rules.sideRules.trunkLayer;
side: LRSide;
abutOb: CD.Object;
pwSide: PWPins.Side;
width: SC.Number;
layout: LayoutData ← NARROW[handle.layoutData];
ExtendPin:
PW.ForEachPinProc = {
[inst: Instance] RETURNS [obj: Object];
pinName: ROPE ← CDPinObjects.GetName[inst];
acBus: SCPrivate.AcBus;
sigIndex: NAT;
[acBus, sigIndex] ← AcBusForName[handle, side, pinName];
IF acBus = NIL THEN obj ← AlwaysExtendPin[handle, inst, width]
ELSE {
ComputeTrunkEnd[trunkEnd: trunkEnd, q: inst.location.y, index: sigIndex, fromTB: acBus.fromTB];
obj ← CreateWireAndContact[handle, inst, acBus.depth, trunkLayer]};
};
FOR side
IN LRSide
DO
acBusSide: SCPrivate.AcBusSides ← layout.acBuses[side];
IF acBusSide = NIL OR acBusSide.sigs = NIL THEN LOOP;
trunkEnd ← NEW[NumSeqRec[acBusSide.sigs.size]];
FOR i: NAT IN [0..trunkEnd.size) DO trunkEnd[i] ← NIL; ENDLOOP;
pwSide ← SELECT side FROM right => right, left => left, ENDCASE => ERROR;
width ← acBusSide.width;
ext[side] ← PW.TransferCell[design: design, template: pwOb, objSide: pwSide, width: width, objProc: ExtendPin];
CreateAcTrunks[handle, ext[side], acBusSide, trunkEnd, trunkLayer];
ENDLOOP;
abutOb ← PW.AbutListX[design, LIST [ext[left], pwOb, ext[right]]];
ob ← CDDirectory.Expand[me: abutOb, to: design, from: design];
END;
IORoute:
PROC [handle:
SC.Handle, pwOb:
PW.Object, design:
CD.Design]
RETURNS [ob: PW.Object] =
BEGIN
layout: LayoutData ← NARROW[handle.layoutData];
bpRows: SCPrivate.BpRows ← layout.bpRows;
FOR side:
SC.Side
IN
SC.Side
DO
IF bpRows[side].fnlBpFxd THEN {
expand bprow to length of corresponding cell's side.
PWRoute.AbutRoute to pwOb
SCInstutil.BpPos
right side => position in bp
bottom => origin lower left hand side
top => lower right hand side origin
left => upper left side
};
ENDLOOP;
BpRowRec: TYPE = RECORD [
bpSpacing: INT ← 0,
size, sideOrg: PQPos ← [0, 0], -- sideorg is origin of side
dimInvalid: BOOLEAN ← TRUE,
initMaxBpsOnSide, maxBpsOnSide, nBpsOnSide: ZMaxPosSr ← 0,
bpsOnSide: ARRAY ZMaxPosSr OF Instance ← ALL[NIL],
fnlBpFxd, initBpFxd, routeSideChans: BOOLEAN ← FALSE];
handle: for each side for which side.fnlBpFxd invoke PWRoute.AbutRoute else
extend exit pins to edge of cell
END;
DetailRoute:
PUBLIC
PROC [handle:
SC.Handle]
RETURNS [result:
SC.Result] =
BEGIN
pwOb: PW.Object ← NIL;
parms: SCPrivate.Parms ← NARROW[handle.parms];
design: CD.Design ← parms.cdDesign;
pwOb ← LogicRoute[handle, design];
pwOb ← PowerRoute[handle, pwOb, design];
pwOb ← ClockRoute[handle, pwOb, design];
result ← NEW[SC.ResultRec ← []];
result.object ← pwOb;
result.handle ← handle;
pwOb ← IORoute[handle, pwOb, design];
END;