
<<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;

END.