
<<CoreRouteStack.mesa>>
<<Copyright Ó 1985, 1986, 1987 by Xerox Corporation.  All rights reserved.>>
<<Don Curry May 1, 1987 1:00:41 am PDT>>
<<Last Edited by: Don Curry August 9, 1988 1:28:52 pm PDT>>
    <<Christian Le Cocq January 4, 1988 5:47:46 pm PST>>
    <<Bertrand Serlet September 21, 1987 5:31:09 pm PDT>>
<<>>
DIRECTORY
Atom, CD, CDSimpleRules, CedarProcess, CMosB, Core, CoreClasses, CoreGeometry, CoreOps, CoreProperties, CoreRoute, DABasics, 
D2Orient, IO, PW, PWCore, RefTab, Rope, RopeList, Route, Sisyph, SymTab, TerminalIO;

CoreRouteStack: CEDAR PROGRAM
IMPORTS  Atom, CD, CDSimpleRules, CedarProcess, CMosB, CoreGeometry, CoreOps, CoreProperties, CoreRoute, IO, PW, PWCore, RefTab, 
Rope, RopeList, Route, Sisyph, SymTab, TerminalIO
EXPORTS CoreRoute =
BEGIN
<<Types and constants>>
StackForm:        TYPE    = CoreRoute.StackForm;
StackFormRec:    TYPE    = CoreRoute.StackFormRec;
StackSection:        TYPE    = CoreRoute.StackSection;
StackAbutRec:    TYPE    = CoreRoute.StackAbutRec;
StackChanRec:    TYPE    = CoreRoute.StackChanRec;
LaySize:            TYPE    = CoreRoute.LaySize;
WirePin:            TYPE    = CoreRoute.WirePin;
WirePins:            TYPE    = CoreRoute.WirePins;
Segment:            TYPE    = CoreRoute.Segment;
Segments:            TYPE    = LIST OF Segment;
RelativeSide:        TYPE    = {first,        last,        min,        max};
Side:                TYPE    = CoreGeometry.Side;
CellType:            TYPE    = Core.CellType;
Wire:                TYPE    = Core.Wire;
NetInfo:            TYPE = REF NetInfoRec;
NetInfoRec:        TYPE = RECORD [
mayExit:                BOOL                _ FALSE,
trunkSize:            INT                _ 0,
exitLeftOrBottom:    BOOL                _ FALSE,
exitRightOrTop:        BOOL                _ FALSE,
pins:                    LIST OF PinInfo    _ NIL];
PinInfo:            TYPE = RECORD [
bottomOrLeftSide:    BOOL, 
min:                    CD.Number _ 0, 
max:                    CD.Number _ 0, 
layer:                    CD.Layer];
stackLayoutProp:        ATOM _ $Stack;
stackLayoutRawProp:    ATOM _ $RawStack;
stackFormProp:            ATOM _ $StackForm;
horStackProp:            ATOM _ $HorizontalStack;
branchLayerProp:        ATOM _ $Branch;
trunkLayerProp:            ATOM _ $Trunk;
verticalLayerProp:        ATOM _ $VerticalMetal;
wireWidthProp:            ATOM _ $w;
technologyKey:            ATOM _ $cmosB;
lambda:            INT    _ CDSimpleRules.GetTechnology[technologyKey].lambda;
Signal:            SIGNAL[msg: IO.ROPE] = CODE;
schDeco:            CoreGeometry.Decoration _ Sisyph.mode.decoration;
OffSetCnt:        TYPE = RECORD[offSet: INT, count: CARDINAL];
OffSetCnts:        TYPE = LIST OF OffSetCnt;
<<Stack Attribute, Layout and Decorate Procs>>
StackAttributes:    PWCore.AttributesProc    = {
IRCord: PROC[ir: CD.Rect] RETURNS[first, last, min, max: INT] = {
IF form.inX
THEN    RETURN[    first: ir.x1,    last: ir.x2,        min: ir.y1,    max: ir.y2]
ELSE    RETURN[    first: ir.y1,    last: ir.y2,    min: ir.x1,    max: ir.x2] };
CellLaySize: PROC[ct: CellType] RETURNS[laySize: LaySize] = {
first, last, min, max: INT;
[first, last, min, max] _ IRCord[CD.InterestRect[PWCore.Layout[ct]]];
RETURN[[width: max-min, height: last-first]]};
BLayerUnKnown: PROC RETURNS[BOOL] =
{RETURN[form.branchLayer=CD.commentLayer]};
data:            CoreClasses.RecordCellType _ NARROW[cellType.data];
form:            StackForm    _ NEW[StackFormRec _ [inX: SchSort[cellType]]];
irFirst:        INT _ IRCord[CD.InterestRect[CoreGeometry.GetObject[schDeco, cellType]]].first;
irLast:            INT _ IRCord[CD.InterestRect[CoreGeometry.GetObject[schDeco, cellType]]].last;
loPos:            INT            _ 0;
hiPos:            INT            _ 0;
index:            INT            _ 0;
sections:        LIST OF StackSection    _ NIL;
previous:        LIST OF StackSection    _ NIL;
lastSection:    LIST OF StackSection    _ NIL;
globals:        Core.Wires    _ CoreRoute.GlobalWires[cellType];
firstWires:    Core.Wires    _ CoreRoute.OrderedAtomicSchWires[cellType, RSide[form.inX, first]];
lastWires:        Core.Wires    _ CoreRoute.OrderedAtomicSchWires[cellType, RSide[form.inX, last]];
form.justification _ GetJustification[cellType];
<<Build first cut at section list.  Add channels where gaps between subcells exist.>>
FOR index _ 0, index+1 DO
minWires, maxWires: Core.Wires _ NIL;
abut: StackAbutRec;
loPos    _ hiPos;
hiPos    _ IF index = data.size
THEN irLast-irFirst ELSE IRCord[CoreRoute.SchMappedIR[data[index]].ir].first - irFirst;
IF hiPos > loPos THEN {
chan: REF StackChanRec _ NEW[StackChanRec _ []];
form.sec _ CONS[[chan: chan], form.sec];
chan.minPins _  SwitchBoxPins[    CoreRoute.OrderedAtomicSchWires
[cellType, RSide[form.inX, min], loPos, hiPos]];
chan.maxPins _  SwitchBoxPins[    CoreRoute.OrderedAtomicSchWires
[cellType, RSide[form.inX, max], loPos, hiPos]]};
IF index = data.size THEN EXIT;
IF form.sec=NIL OR form.sec.first.chan#NIL THEN -- need new abut section
{form.sec _ CONS[[abuts: NIL], form.sec]};
abut _ [
inst:        index,
firstPins:    CoreRoute.FilteredInstanceLayoutPins[data[index],    RSide[form.inX, first]],
lastPins:    CoreRoute.FilteredInstanceLayoutPins[data[index],    RSide[form.inX, last]],
minPins:    CoreRoute.FilteredInstanceLayoutPins[data[index],    RSide[form.inX, min]],
maxPins:    CoreRoute.FilteredInstanceLayoutPins[data[index],    RSide[form.inX, max]],
laySize:    CellLaySize[data[index].type] ];
loPos    _ hiPos;
hiPos    _ IRCord[CoreRoute.SchMappedIR[data[index]].ir].last - irFirst;
minWires _ CoreRoute.OrderedAtomicSchWires[cellType, RSide[form.inX, min], loPos, hiPos];
maxWires _ CoreRoute.OrderedAtomicSchWires[cellType, RSide[form.inX, max], loPos, hiPos];
abut.minPins    _ FilterPins[abut.minPins, minWires, globals];
abut.maxPins    _ FilterPins[abut.maxPins, maxWires, globals];
form.sec.first.abuts _ CONS[abut, form.sec.first.abuts] ENDLOOP;
<<Reverse lists.>>
form.sec _ ReverseSections[form.sec];
FOR sections _ form.sec, sections.rest WHILE sections#NIL DO
sections.first.abuts _ ReverseAbuts[sections.first.abuts] ENDLOOP;
<<Insert channel sections between incompatible abuts.>>
IF CoreProperties.GetCellTypeProp[cellType, $TrustMe]=NIL THEN
FOR sections _ form.sec,    sections.rest WHILE sections#NIL DO
abuts:    LIST OF StackAbutRec _ sections.first.abuts;
FOR abuts _ abuts, abuts.rest WHILE abuts#NIL AND abuts.rest#NIL DO
IF CheckInterface[data, form.inX, abuts.first.inst, abuts.rest.first.inst ] THEN LOOP;
sections.rest        _ CONS[[abuts: abuts.rest],                sections.rest];
sections.rest        _ CONS[[chan: NEW[StackChanRec _ []]],    sections.rest];
abuts.rest _ NIL;
ENDLOOP ENDLOOP;
<<Compute the min/max for each abut section as well as the overall min/max or max (width).>>
previous _ NIL;
FOR sections _ form.sec,    sections.rest WHILE sections#NIL DO
abuts:    LIST OF StackAbutRec _ sections.first.abuts;
IF abuts#NIL
THEN {
sections.first.abutMin    _ abuts.first.off;
sections.first.abutMax    _ abuts.first.off + abuts.first.laySize.width;
FOR abuts _ abuts, abuts.rest WHILE abuts#NIL AND abuts.rest#NIL DO
index:            INT    _ abuts.first.inst;
thisWidth:    INT    _ abuts.first.laySize.width;
nextWidth:    INT    _ abuts.rest.first.laySize.width;
offset:            INT    _ IF abuts.rest.first.firstPins#NIL
THEN    abuts.first.lastPins.first.min - abuts.rest.first.firstPins.first.min
ELSE    SELECT form.justification FROM
bottomLeft    => 0,
topRight        => (thisWidth - nextWidth),
ENDCASE        => 0;    -- really should be two sections with null channel
loc:            INT        _ abuts.rest.first.off    _ abuts.first.off + offset;
sections.first.abutMin    _ MIN[loc,                    sections.first.abutMin];
sections.first.abutMax    _ MAX[loc + nextWidth,    sections.first.abutMax];
ENDLOOP;
IF form.justification = bestFit
THEN {
form.min    _ MIN[form.min,    sections.first.abutMin];
form.max    _ MAX[form.max,    sections.first.abutMax]}
ELSE {
form.min    _ 0;
form.max    _ MAX[form.max,    sections.first.abutMax-sections.first.abutMin]} }
ELSE IF form.justification=bestFit AND sections.rest#NIL AND previous#NIL THEN {
FOR abuts _ previous.first.abuts, abuts.rest WHILE abuts.rest#NIL DO ENDLOOP;
sections.rest.first.abuts.first.off _ abuts.first.off + FindBestOffset
[abuts.first.lastPins, sections.rest.first.abuts.first.firstPins]};
previous _ sections ENDLOOP;
<<Propagate max (=maxWidth) or (if justify bestFit) min/max to sections.>>
<<Examine layouts of channel bounding subcells to discover routing layers.>>
IF BLayerUnKnown[] THEN [form.branchLayer, form.trunkLayer] _
GetCellTypePropLayer[cellType, branchLayerProp];
IF BLayerUnKnown[] THEN [form.trunkLayer, form.branchLayer] _
GetCellTypePropLayer[cellType, trunkLayerProp];
IF BLayerUnKnown[] THEN IF form.inX
THEN    [form.trunkLayer, form.branchLayer] _
GetCellTypePropLayer[cellType, verticalLayerProp]
ELSE    [form.branchLayer, form.trunkLayer] _
GetCellTypePropLayer[cellType, verticalLayerProp];
previous _ NIL;
FOR sections _ form.sec,    sections.rest WHILE sections#NIL DO
IF sections.first.abuts#NIL
THEN    SELECT form.justification FROM
bottomLeft    => sections.first.abutMax _ sections.first.abutMin +    form.max; -- width
topRight        => sections.first.abutMin _ sections.first.abutMax -    form.max; -- width
ENDCASE        => {sections.first.abutMin_form.min; sections.first.abutMax_form.max}
ELSE {
Ck: PROC[lay: CD.Layer] = {
IF lay#CD.commentLayer AND lay#form.branchLayer THEN
TerminalIO.PutF["***Warning: Routing layers are incompatible.\n"]};
chan: REF StackChanRec _  sections.first.chan;
top: CD.Layer _ IF sections.rest#NIL
THEN    GetRoutingLayer[sections.rest.first.abuts.first.firstPins]
ELSE    CD.commentLayer;
bot: CD.Layer _ IF previous#NIL
THEN    GetRoutingLayer[ReverseAbuts[previous.first.abuts].first.lastPins]
ELSE    CD.commentLayer;
IF chan=NIL THEN ERROR;
sections.first.abutMin    _ form.min;    -- just clean up, not really needed
sections.first.abutMax    _ form.max;    -- just clean up, not really needed
IF BLayerUnKnown[] THEN form.branchLayer _ top ELSE Ck[top];
IF BLayerUnKnown[] THEN form.branchLayer _ bot ELSE Ck[bot]};
previous _ sections ENDLOOP;
IF BLayerUnKnown[] THEN {
form.branchLayer _ IF form.inX THEN CMosB.met ELSE CMosB.met2;
TerminalIO.PutF["Warning: Unconstrained branchLayer.  Defaulting to %g\n",
IO.rope[IF form.inX THEN "metal" ELSE "metal2"]] };
form.trunkLayer _ ResolveRoutingLayer [form.trunkLayer, form.branchLayer];
<<Initialize channel first and last WirePins;>>
FOR sections _ form.sec, sections.rest WHILE sections#NIL DO
offset:    INT;
pins:    WirePins;
abuts:    LIST OF StackAbutRec;
abut:    StackAbutRec;
IF sections.first.chan=NIL THEN {lastSection _ sections; LOOP};
IF lastSection#NIL THEN {
FOR abuts _ lastSection.first.abuts, abuts.rest WHILE abuts.rest#NIL DO ENDLOOP;
abut    _ abuts.first;
offset    _ abut.off - lastSection.first.abutMin;
pins    _ abut.lastPins;
FOR pins _ pins, pins.rest WHILE pins#NIL DO
pin: WirePin _ pins.first;
sections.first.chan.firstPins _ CONS
[[pin.wire, pin.min+offset, pin.max+offset, pin.layer], sections.first.chan.firstPins];
ENDLOOP};
IF sections.rest#NIL THEN {
abut    _ sections.rest.first.abuts.first;
offset    _ abut.off - sections.rest.first.abutMin;
pins    _ abut.firstPins;
FOR pins _ pins, pins.rest WHILE pins#NIL DO
pin: WirePin _ pins.first;
sections.first.chan.lastPins _ CONS
[[pin.wire, pin.min+offset, pin.max+offset, pin.layer], sections.first.chan.lastPins];
ENDLOOP};
IF lastSection=NIL THEN sections.first.chan.firstPins _
FilterPins[sections.first.chan.lastPins, firstWires, globals];
IF sections.rest=NIL THEN sections.first.chan.lastPins _
FilterPins[sections.first.chan.firstPins, lastWires, globals];
ENDLOOP;
CoreProperties.PutCellTypeProp[cellType, stackFormProp, form];
<<CoreRoute.FlushSchPinCache[cellType];    -- Don't Flush, Save for next level>>
<<CoreRoute.FlushLayPinCache[cellType];    -- Don't Flush, Save for next level>>
FOR i: INT IN [0..data.size) DO
CoreRoute.FlushSchPinCache[data[i].type];
CoreRoute.FlushLayPinCache[data[i].type] ENDLOOP;
ShowStackForm[cellType]};

StackLayout:        PWCore.LayoutProc        = {
data:    CoreClasses.RecordCellType _ NARROW[cellType.data];
form:    StackForm _ NARROW[CoreProperties.GetCellTypeProp[cellType, stackFormProp]];
primary:        LIST OF CD.Object    _ NIL;
minSide:        Side _ RSide[form.inX, min];
maxSide:        Side _ RSide[form.inX, max];
totalLength:    REF INT _ NARROW[CoreProperties.GetCellTypeProp[cellType, $TotalLength]];
length:        INT _ 0;
chanCnt:        INT _ 0;
chanIndex:    INT _ 0;
form.auxLabels _ SymTab.Create[];
<<Count channels and compute starting length for use with totalLength>>
FOR sections:    LIST OF StackSection _ form.sec,    sections.rest WHILE sections#NIL DO
IF sections.first.chan # NIL
THEN chanCnt _ chanCnt+1
ELSE {
abuts: LIST OF StackAbutRec _ sections.first.abuts;
FOR abuts _ abuts, abuts.rest WHILE abuts#NIL DO
length _ length + abuts.first.laySize.height ENDLOOP } ENDLOOP;
<<Make section objects>>
FOR sections:    LIST OF StackSection _ form.sec,    sections.rest WHILE sections#NIL DO
IF sections.first.chan # NIL THEN {
adjustChan:    BOOL    _ chanIndex+1=chanCnt AND totalLength#NIL;
brLen:        INT    _ IF adjustChan THEN lambda*totalLength^-length ELSE 0;
rtObj:    CD.Object _ MakeStackChannel[cellType, chanIndex, sections.first.chan, brLen];
objSize:    CD.Position _ CD.InterestSize[rtObj];
primary        _ CONS[rtObj, primary];
length        _ length + (IF form.inX THEN objSize.x ELSE objSize.y);
chanIndex    _ chanIndex+1;
IF adjustChan AND length>lambda*totalLength^ THEN
TerminalIO.PutF["*** Total Stack length exceeded by %g lambda.\n",
IO.int[(length/lambda)-totalLength^]]};
FOR abuts: LIST OF StackAbutRec _ sections.first.abuts, abuts.rest WHILE abuts#NIL DO
secondary:    LIST OF CD.Object    _ NIL;
gapMin:        INT    _ abuts.first.off - sections.first.abutMin;
gapMax:        INT    _ sections.first.abutMax - abuts.first.off - abuts.first.laySize.width;
length:        INT    _ abuts.first.laySize.height;
IF gapMax > 0 THEN {
enumSegs: PROC [eachSeg: PROC[Segment]] =
{FOR segs _ segs, segs.rest WHILE segs#NIL DO eachSeg[segs.first] ENDLOOP};
segs:        Segments        _ GetSegs[data.internal, abuts.first.maxPins, form.trunkLayer];
size:        CD.Position    _ IF form.inX THEN [length,gapMax] ELSE [gapMax,length];
extObj:    CD.Object        _ CoreRoute.ExtendObject[enumSegs, size, maxSide];
secondary _ CONS[extObj, secondary]};
secondary _ CONS[PWCore.Layout[data[abuts.first.inst].type], secondary];
IF gapMin > 0 THEN {
enumSegs: PROC [eachSeg: PROC[Segment]] =
{FOR segs _ segs, segs.rest WHILE segs#NIL DO eachSeg[segs.first] ENDLOOP};
segs:        Segments        _ GetSegs[data.internal, abuts.first.minPins, form.trunkLayer];
size:        CD.Position    _ IF form.inX THEN [length,gapMin] ELSE [gapMin, length];
extObj:    CD.Object        _ CoreRoute.ExtendObject[enumSegs, size, minSide];
secondary _ CONS[extObj, secondary]};
primary _ CONS[IF secondary.rest=NIL
THEN    secondary.first
ELSE    IF form.inX -- pimary inX => secondary inY
THEN    PW.CreateNewAbutY[secondary]
ELSE    PW.CreateNewAbutX[secondary], primary];
ENDLOOP;
ENDLOOP;
primary _ ReverseObj[primary];
obj _ IF form.inX
THEN    PW.CreateNewAbutX[primary]
ELSE    PW.CreateNewAbutY[primary]}; 
<<>>
StackDecorate:     PWCore.DecorateProc    = {
WireToLabels: PROC [wire: Core.Wire] RETURNS [labels: LIST OF Route.Label _ NIL] = {
label:            Route.Label    =  CoreRoute.LabelInternal[data.internal, wire];
auxLabels:    LIST OF Route.Label = NARROW[SymTab.Fetch[form.auxLabels, label].val];
labels _ CONS [label, auxLabels]};
data:    CoreClasses.RecordCellType _ NARROW [cellType.data];
form:    StackForm _ NARROW[CoreProperties.GetCellTypeProp[cellType, stackFormProp]];
CoreRoute.DecorateRoutedArea[
cellType:            cellType,
obj:                obj,
wireToLabels:    WireToLabels,
compareIR:        CoreRoute.CompareXorYStack]};
<<Stack channel generator>>
MakeStackChannel: PROC
[cell: CellType, chanIndex: INT, chan: REF StackChanRec, branchLength: INT _ 0]
RETURNS[channel: CD.Object] = {
form:    StackForm _ NARROW[CoreProperties.GetCellTypeProp[cell, stackFormProp].value];
channel _ MakeChannel[
parent:            cell,
chanIndex:        chanIndex,
auxLabelTab:        form.auxLabels,
trunkLength:    form.max - form.min, 
branchLength:    branchLength, 
trunkDirection:    (IF form.inX THEN vertical ELSE horizontal),
horizLayer:        (IF form.inX THEN form.branchLayer ELSE form.trunkLayer),
vertLayer:        (IF form.inX THEN form.trunkLayer ELSE form.branchLayer),
minPins:            chan.minPins,
maxPins:            chan.maxPins,
firstPins:            chan.firstPins,
lastPins:            chan.lastPins ]};

MakeChannel: PUBLIC PROC[
parent:            CellType,
chanIndex:        INT,            -- Insures unique names in auxLabelTab for multi chans.
auxLabelTab:        SymTab.Ref,    -- LIST OF Route.Label for broken nets.
trunkLength:    INT,             -- firstPins/lastPins min/max must be IN [0..trunkLength]
branchLength:    INT,              -- minPins/maxPins min/max ignored (for now)
trunkDirection:    DABasics.Direction,
horizLayer:        CD.Layer,
vertLayer:        CD.Layer,
minPins:            WirePins    _ NIL,    -- IF trunkDirection=vertical THEN bottom
maxPins:            WirePins    _ NIL,    -- IF trunkDirection=vertical THEN top
firstPins:            WirePins    _ NIL,    -- IF trunkDirection=vertical THEN left
lastPins:            WirePins    _ NIL ]    -- IF trunkDirection=vertical THEN right
RETURNS[channel: CD.Object] = {
BrokenNets: Route.BrokenNetProc = {
auxLabels: LIST OF Route.Label _ NARROW[SymTab.Fetch[auxLabelTab, sourceNet].val];
newLabel _ IO.PutFR["%g#Ch%g#%g",
IO.rope[sourceNet], IO.int[chanIndex], IO.int[regionNumber]];
IF NOT RopeList.Memb[auxLabels, newLabel] THEN {
auxLabels _ CONS [newLabel, auxLabels];
[]_SymTab.Store[auxLabelTab, sourceNet, auxLabels]} };
name:    IO.ROPE _ IO.PutFR["%gChan%g",
IO.rope[CoreOps.GetCellTypeName[parent]], IO.int[chanIndex]];
data:    CoreClasses.RecordCellType _ NARROW[parent.data];
priority:        CedarProcess.Priority _ CedarProcess.GetPriority[];
rulesParameters:    Route.DesignRulesParameters = Route.DefaultDesignRulesParameters[
technologyHint:    technologyKey, 
horizLayer:        horizLayer, 
vertLayer:        vertLayer, 
trunkDirection:    trunkDirection];
intermediateResult:    Route.IntermediateResult;
nets:                    SymTab.Ref _ SymTab.Create[];    -- Label -> NetInfo
retrieveRect: REF DABasics.Rect _ NEW[DABasics.Rect _ IF trunkDirection=vertical
THEN    [x1: 0, y1: 0, x2: branchLength,    y2: trunkLength]
ELSE    [x1: 0, y1: 0, x2: trunkLength,        y2: branchLength]];
branchLayer: CD.Layer _ IF trunkDirection=vertical
THEN    horizLayer
ELSE    vertLayer;
FOR pins: WirePins _ minPins, pins.rest WHILE pins#NIL DO -- can be structured
netInfo: NetInfo _ FetchNetInfo[nets, data.internal, pins.first.wire];
netInfo.exitLeftOrBottom    _ TRUE;
netInfo.mayExit                _ TRUE;
IF pins.first.wire.size#0 THEN ERROR ENDLOOP;
FOR pins: WirePins _ maxPins, pins.rest WHILE pins#NIL  DO -- can be structured
netInfo: NetInfo _ FetchNetInfo[nets, data.internal, pins.first.wire];
netInfo.exitRightOrTop        _ TRUE;
netInfo.mayExit                _ TRUE;
IF pins.first.wire.size#0 THEN ERROR ENDLOOP;
FOR pins: WirePins _ firstPins, pins.rest WHILE pins#NIL  DO
netInfo: NetInfo _ FetchNetInfo[nets, data.internal, pins.first.wire];
IF pins.first.layer#branchLayer THEN LOOP;
netInfo.pins    _ CONS [[TRUE, pins.first.min, pins.first.max, pins.first.layer], netInfo.pins];
IF pins.first.wire.size#0 THEN ERROR ENDLOOP;
FOR pins: WirePins _ lastPins, pins.rest WHILE pins#NIL  DO
netInfo: NetInfo _ FetchNetInfo[nets, data.internal, pins.first.wire];
IF pins.first.layer#branchLayer THEN LOOP;
netInfo.pins    _ CONS [[FALSE, pins.first.min, pins.first.max, pins.first.layer], netInfo.pins];
IF pins.first.wire.size#0 THEN ERROR ENDLOOP;
CedarProcess.CheckAbort[];
CedarProcess.SetPriority[background];
intermediateResult _ Route.ChannelRoute[
name:                name,
enumerateNets:    EnumerateChannelNets, 
min:                0,
max:                trunkLength,
rulesParameters:    rulesParameters,
rules:                Route.DefaultDesignRules[rulesParameters],
optimization: IF CoreProperties.GetCellTypeProp[parent, $FastRoute]#NIL
THEN noIncompletes ELSE full,
channelData:        nets ! Route.Signal =>{
TerminalIO.PutF["*** Route channel %g preliminary warning:\n  %g\n",
IO.rope[name], IO.rope[explanation]];
RESUME}];
channel _ Route.ChannelRetrieve[
intermediateResult:    intermediateResult,
enumerateNets:        EnumerateChannelNets, 
brokenNets:            BrokenNets, 
channelData:            nets, 
retrieveRect:            retrieveRect ! Route.Signal => {
TerminalIO.PutF["*** Route channel %g final warning:\n  %g\n",
IO.rope[name], IO.rope[explanation]];
RESUME}
].object;
IF channel=NIL THEN ERROR;
CedarProcess.SetPriority[priority]};

FetchNetInfo:    PROC [nets: SymTab.Ref, root, wire: Wire] RETURNS[netInfo: NetInfo] = {
label: Route.Label = CoreRoute.LabelInternal[root, wire];
rw: REF INT = NARROW [CoreProperties.GetWireProp[wire, wireWidthProp]];
netInfo _ NARROW [SymTab.Fetch[nets, label].val];
IF netInfo#NIL THEN RETURN;
netInfo _ NEW [NetInfoRec _ [trunkSize: IF rw=NIL THEN 0 ELSE rw^*lambda]];
[] _ SymTab.Store[nets, label, netInfo]};

EnumerateChannelNets: Route.EnumerateChannelNetsProc = {
nets: SymTab.Ref = NARROW [channelData];
EachNet: SymTab.EachPairAction = {
label:        Route.Label    = key;
netInfo:    NetInfo        = NARROW[val];
IF netInfo.exitLeftOrBottom OR netInfo.exitRightOrTop OR netInfo.pins#NIL THEN eachNet[
name:                    label,
enumeratePins:        EnumerateChannelPins,
exitLeftOrBottom:    netInfo.exitLeftOrBottom,
exitRightOrTop:        netInfo.exitRightOrTop,
mayExit:                netInfo.mayExit,
trunkSize:            netInfo.trunkSize,
channelData:            NIL,
netData:                netInfo]};
[] _ SymTab.Pairs[nets, EachNet]};

EnumerateChannelPins: Route.EnumerateChannelPinsProc = {
netInfo: NetInfo = NARROW [netData];
FOR pins: LIST OF PinInfo _ netInfo.pins, pins.rest WHILE pins#NIL DO
pin: PinInfo = pins.first;
eachPin[
bottomOrLeftSide:    pin.bottomOrLeftSide,
min:                    pin.min,
max:                    pin.max,
layer:                    pin.layer];
ENDLOOP };
<<Exported procedures>>
WirePinWires:    PUBLIC PROC[pins: WirePins] RETURNS[wires: Core.Wires] = {
FOR pins _ CoreRoute.ReverseWirePins[pins], pins.rest WHILE pins#NIL DO
wires _ CONS[pins.first.wire, wires] ENDLOOP};

FilterPins: PUBLIC PROC[pins: WirePins, wires0, wires1: Core.Wires]
RETURNS[sel: WirePins _ NIL] = {
FOR pins _ pins, pins.rest WHILE pins#NIL DO
IF CoreOps.Member[wires1, pins.first.wire] OR
CoreOps.Member[wires0, pins.first.wire] THEN sel _ CONS[pins.first, sel] ENDLOOP;
sel _ CoreRoute.ReverseWirePins[sel]};

GetCellTypePropLayer: PUBLIC PROC[cellType: CellType, key: ATOM, default: REF _ NIL]
RETURNS[layer, other: CD.Layer_CD.commentLayer]={
<<Really just looks for 2 in the name to distinguish Metal Metal2, $met, #met2;>>
prop: REF _ CoreProperties.GetCellTypeProp[cellType, key];
IF prop=NIL THEN prop _ default;
IF prop#NIL THEN {
name: IO.ROPE _ WITH prop SELECT FROM
atom:    ATOM        => Atom.GetPName[atom],
rope:    IO.ROPE    => rope,
ENDCASE        => ERROR;
IF name.Find["2"]=-1
THEN    RETURN[CMosB.met, CMosB.met2]
ELSE    RETURN[CMosB.met2, CMosB.met]}};

GetRoutingLayer: PUBLIC PROC[pins: WirePins] RETURNS[layer: CD.Layer] = {
polyFound:    BOOL _ FALSE;
metFound:    BOOL _ FALSE;
met2Found:    BOOL _ FALSE;
FOR pins _ pins, pins.rest WHILE pins#NIL DO
SELECT pins.first.layer FROM
CMosB.pol    => polyFound    _ TRUE;
CMosB.met    => metFound        _ TRUE;
CMosB.met2    => met2Found    _ TRUE;
ENDCASE ENDLOOP;
layer _ SELECT TRUE FROM
met2Found AND metFound        =>  CD.commentLayer,
met2Found AND polyFound    =>  CD.commentLayer,
metFound AND polyFound        =>  CD.commentLayer,
met2Found                        =>  CMosB.met2,
metFound                        =>  CMosB.met,
polyFound                        =>  CMosB.pol,
ENDCASE                            =>  CD.commentLayer;
layer _ CD.commentLayer};

GetJustification: PUBLIC PROC[cellType: CellType]
RETURNS[justification: CoreRoute.Justification] = {
ref: REF _ CoreProperties.GetCellTypeProp[cellType, $Justify];
IF CoreProperties.GetCellTypeProp[cellType, $JustifyTopOrRight]#NIL THEN {
TerminalIO.PutRope[" *** JustifyTopOrRight: (nonNil) should be Justify: $TopRight\n"];
RETURN[topRight]};
justification _ IF ref=NIL
THEN    bottomLeft
ELSE    SELECT NARROW[ref, ATOM] FROM
$TopRight    => topRight,
$BottomLeft    => bottomLeft,
$BestFit        => bestFit,
ENDCASE        => ERROR};
<<Auxillary procedures>>
AtomicWires:    PROC[struc: Core.Wires] RETURNS[atomics: Core.Wires] = {
AddAtomic: PROC[wire: Core.Wire] = {
IF wire.size=0
THEN    atomics _ CONS[wire, atomics]
ELSE    FOR i: INT IN [0..wire.size) DO AddAtomic[wire[i]] ENDLOOP};
FOR struc _ struc, struc.rest WHILE struc#NIL DO AddAtomic[struc.first] ENDLOOP;
atomics _ CoreOps.Reverse[atomics]};

AddWirePin: PROC[pin: WirePin, pins: WirePins] RETURNS[new: WirePins] = {
FOR temp: WirePins _ pins, temp.rest WHILE temp#NIL DO
IF temp.first.wire=pin.wire THEN RETURN[pins] ENDLOOP;
RETURN[CONS[pin, pins]]};

InstanceLayoutPins: PROC[inst: CoreClasses.CellInstance, side: Side]
RETURNS[pins: WirePins] = {
bindings:        RefTab.Ref    _ CoreOps.CreateBindingTable[inst.type.public, inst.actual];
ctPins:        WirePins        _ CoreRoute.LayPins[inst.type, side];
FOR ctPins _ ctPins, ctPins.rest WHILE ctPins#NIL DO
actual: Wire _ NARROW[RefTab.Fetch[bindings, ctPins.first.wire].val];
IF actual=NIL THEN ERROR;
pins _ CONS[ctPins.first, pins];
pins.first.wire _ actual;
ENDLOOP;
pins _ CoreRoute.ReverseWirePins[pins]};

CheckInterface: PROC[data: CoreClasses.RecordCellType, inX: BOOL, iFirst, iLast: INT]
RETURNS[ok: BOOL _ FALSE] = {
Nm: PROC[wp: WirePins] RETURNS[IO.ROPE] =
{RETURN[CoreRoute.LabelInternal[data.internal, wp.first.wire]]};
l1: WirePins _ InstanceLayoutPins[data[iFirst],        RSide[inX, last]];
l2: WirePins _ InstanceLayoutPins[data[iLast],        RSide[inX, first]];
msg: IO.ROPE _ NIL;
delta:    INT;
IF l1=NIL AND l2=NIL THEN RETURN[TRUE];
IF l1=NIL THEN msg _ IO.PutFR["First cell has no pins"];
IF l2=NIL THEN msg _ IO.PutFR["Second cell has no pins"];
IF msg=NIL THEN {
delta _ l2.first.min - l1.first.min;
FOR l1 _ l1, l1.rest WHILE l1#NIL DO
IF l2=NIL    THEN
{msg _ IO.PutFR["%g has unmatched pin", IO.rope[Nm[l1]]];        EXIT};
IF l1.first.wire        # l2.first.wire    THEN {
msg _ IO.PutFR["%g is not %g", IO.rope[Nm[l1]], IO.rope[Nm[l2]]];    EXIT};
IF l1.first.min+delta    # l2.first.min THEN
{msg _ IO.PutFR["%g position shifted.", IO.rope[Nm[l1]]];            EXIT};
IF l1.first.max+delta    # l2.first.max    THEN
{msg _ IO.PutFR["%g size change.", IO.rope[Nm[l1]]];                EXIT};
IF l1.first.layer        # l2.first.layer    THEN
{msg _ IO.PutFR["%g has different layers", IO.rope[Nm[l1]]];            EXIT};
l2 _ l2.rest;
REPEAT FINISHED => {
IF l2=NIL THEN RETURN [TRUE];
msg _ IO.PutFR["%g has unmatched pin.", IO.rope[Nm[l2]]]}
ENDLOOP};
TerminalIO.PutF["**** Channel inserted between %g and %g  because: \n****   %g\n",
IO.int[iFirst], IO.int[iLast], IO.rope[msg]];
};

GetSegs: PROC[internal: Wire, pins: WirePins, layer: CD.Layer]
RETURNS[segs: LIST OF Segment] = {
FOR pins _ pins, pins.rest WHILE pins#NIL DO
label: Route.Label _ CoreRoute.LabelInternal[internal, pins.first.wire];
IF layer=pins.first.layer THEN
segs _ CONS[[label, pins.first.min, pins.first.max, pins.first.layer], segs] ENDLOOP;
segs _ ReverseSegs[segs]};

ResolveRoutingLayer: PROC[thisLayer, otherLayer: CD.Layer] RETURNS[layer: CD.Layer] = {
layer _ SELECT TRUE FROM
thisLayer#CD.commentLayer    => thisLayer,
otherLayer=CMosB.pol            => CMosB.met,
otherLayer=CMosB.met2        => CMosB.met,
otherLayer=CMosB.met            => CMosB.met2,
ENDCASE                            => ERROR};

ReverseAbuts: PROC[orig:LIST OF StackAbutRec] RETURNS[reverse:LIST OF StackAbutRec] = {
FOR orig _ orig, orig.rest WHILE orig#NIL DO reverse _ CONS[orig.first, reverse] ENDLOOP};

ReverseObj: PROC[orig:LIST OF CD.Object] RETURNS[reverse:LIST OF CD.Object] = {
FOR orig _ orig, orig.rest WHILE orig#NIL DO reverse _ CONS[orig.first, reverse] ENDLOOP};

ReverseSections: PROC[orig: LIST OF StackSection] RETURNS[reverse: LIST OF StackSection] = {
FOR orig _ orig, orig.rest WHILE orig#NIL DO reverse _ CONS[orig.first, reverse] ENDLOOP};

ReverseSegs: PROC[segs: Segments] RETURNS[rev: Segments] =
{FOR segs _ segs, segs.rest WHILE segs#NIL DO rev _ CONS[segs.first, rev] ENDLOOP};

RSide: PROC[inX: BOOL, rside: RelativeSide] RETURNS[side: Side] = {
RETURN[ IF inX
THEN    (SELECT rside FROM first=>left, last=>right, min=>bottom, ENDCASE=>top)
ELSE    (SELECT rside FROM first=>bottom, last=>top, min=>left, ENDCASE=>right)]};

SchSort: PROC[cellType: CellType] RETURNS[inX: BOOL] = {
ambiguous: BOOL;
[ambiguous, inX] _ PWCore.InstancesInXOrY[schDeco, cellType, lambda/2];
IF ambiguous THEN IF NARROW[cellType.data, CoreClasses.RecordCellType].size=1
THEN RETURN[CoreProperties.GetCellTypeProp[cellType, horStackProp]#NIL] ELSE ERROR;
PWCore.SortInstances[schDeco, cellType, IF inX THEN PWCore.SortInX ELSE PWCore.SortInY]};
<<>>
ShowPins: PROC[pins: WirePins] = {
index: INT _ 0;
FOR pins _ pins, pins.rest WHILE pins#NIL DO
TerminalIO.PutF["%2g: %-20g min:%5g max:%5g %g\n",
IO.int[index],
IO.rope[CoreOps.GetShortWireName[pins.first.wire]],
IO.int[pins.first.min],
IO.int[pins.first.max],
IO.atom[CD.LayerKey[pins.first.layer]]];
index _ index +1;
ENDLOOP};

ShowStackForm: PROC[cellType: CellType] = {
form:        StackForm _ NARROW[CoreProperties.GetCellTypeProp[cellType, stackFormProp]];
data:        CoreClasses.RecordCellType _ NARROW[cellType.data];
sections:    LIST OF StackSection;
abuts:        LIST OF StackAbutRec;
tos:        IO.STREAM _ TerminalIO.TOS[];
tos.PutF["Stack layout attributes for %g\n", IO.rope[CoreOps.GetCellTypeName[cellType]] ];
tos.PutF["    %g justify %g stack, min: %g, max: %g\n",
IO.rope[SELECT form.justification FROM
bottomLeft    => (IF form.inX THEN "Bottom"    ELSE "Left"),
topRight        => (IF form.inX THEN "Top"    ELSE "Right"),
ENDCASE        => "BestFit"],
IO.rope[IF form.inX THEN "X" ELSE "Y"],
IO.int[form.min],
IO.int[form.max]];
FOR sections _ ReverseSections[form.sec], sections.rest WHILE sections#NIL DO
IF sections.first.chan#NIL
THEN    tos.PutF["  Channel\n"]
ELSE    tos.PutF["  Abut            min:%5g  max:%5g\n",
IO.int[sections.first.abutMin],
IO.int[sections.first.abutMax]];
FOR abuts _ ReverseAbuts[sections.first.abuts], abuts.rest WHILE abuts#NIL DO
tos.PutF["  %3g  off:%5g", IO.int[abuts.first.inst], IO.int[abuts.first.off]];
tos.PutF["  width:%5g", IO.int[abuts.first.laySize.width]];
tos.PutF["  height:%5g", IO.int[abuts.first.laySize.height]];
tos.PutF["  %g\n", IO.rope[CoreOps.GetCellTypeName[data[abuts.first.inst].type]]];
ENDLOOP ENDLOOP};

SwitchBoxPins: PROC[wires: Core.Wires, layer: CD.Layer _ CD.commentLayer]
RETURNS[pins: WirePins] = {
L4:        INT _ 4*lambda;
loc:    INT _ L4;
FOR wires _ wires, wires.rest WHILE wires#NIL DO
pins _ CONS[ [wires.first, loc, loc+L4, layer], pins];
loc _ loc+L4+L4 ENDLOOP;
pins _ CoreRoute.ReverseWirePins[pins]};

FindBestOffset: PUBLIC PROC[pins1, pins2: WirePins] RETURNS[offSet: INT] = {
TwoOffSetCnt: TYPE = RECORD[o1, o2: OffSetCnt];
Store: PROC[tab: RefTab.Ref, wp: WirePin] = {
nodePins: WirePins _ NARROW[RefTab.Fetch[tab, wp.wire].val];
nodePins _ CONS[wp, nodePins];
[]_RefTab.Store[tab, wp.wire, nodePins]};
BuildSingletonOffSetCnts: RefTab.EachPairAction = {
p1: WirePins _ NARROW[val];
p2: WirePins _ NARROW[RefTab.Fetch[tab2, key].val];
IF p1#NIL AND p2#NIL AND p1.rest=NIL AND p2.rest=NIL THEN {
oSet: INT _ p1.first.min - p2.first.min;
offSetCnts _ CONS[[oSet, 1], offSetCnts];
FOR list: OffSetCnts _ offSetCnts, list.rest WHILE list#NIL AND list.rest#NIL DO
SELECT list.rest.first.offSet-list.first.offSet FROM
>0            =>    EXIT;
<0            =>    [list.rest.first, list.first] _ TwoOffSetCnt[list.first, list.rest.first];
ENDCASE    =>
{list.first.count _ list.rest.first.count + list.first.count; list.rest _ list.rest.rest; EXIT};
ENDLOOP }};
offSetCnts: OffSetCnts;
tab1:    RefTab.Ref _ RefTab.Create[];
tab2:    RefTab.Ref _ RefTab.Create[];
FOR pins1 _ pins1, pins1.rest WHILE pins1#NIL DO Store[tab1, pins1.first] ENDLOOP;
FOR pins2 _ pins2, pins2.rest WHILE pins2#NIL DO Store[tab2, pins2.first] ENDLOOP;
[] _ RefTab.Pairs[tab1, BuildSingletonOffSetCnts];
<<Reorder offSetCnts (decreasing count)>>
DO
done: BOOL _ TRUE;
FOR list: OffSetCnts _ offSetCnts, list.rest WHILE list#NIL AND list.rest#NIL DO
IF list.first.count < list.rest.first.count THEN
{[list.rest.first, list.first] _ TwoOffSetCnt[list.first, list.rest.first]; done _ FALSE};
ENDLOOP;
IF done THEN EXIT ENDLOOP;
offSet _ IF offSetCnts#NIL THEN offSetCnts.first.offSet ELSE 0;
<<Report Indeterminate cases>>
IF offSetCnts=NIL OR
offSetCnts.rest#NIL AND (offSetCnts.first.count = offSetCnts.rest.first.count)  THEN
Signal["Indeterminate offset"]}; -- take a look at offSet and offSetCnts

WirePinOffSetCnts: PROC[pins1, pins2: WirePins] RETURNS[offSetCnts: OffSetCnts] = {
<<This is unused (and untested) since it seems to be better to just check singleton pins>>
offSet: INT _ FIRST[INT];
IF pins1=NIL OR pins2=NIL THEN RETURN[NIL];
FOR list: WirePins _ pins1, list.rest WHILE list#NIL DO
offSet _ MAX[offSet, list.first.min] ENDLOOP;
DO
list1:        WirePins        _ pins1;
list2:        WirePins        _ pins2;
count:        CARDINAL    _ 0;
minDif:    INT            _ LAST[INT];
WHILE list1#NIL AND list2#NIL DO
dif: INT _ list2.first.min + offSet - list1.first.min;
SELECT dif FROM
>0            =>    {list1 _ list1.rest; minDif _ MIN[minDif, dif]};
<0            =>    {list2 _ list2.rest};
ENDCASE    =>    {list2 _ list2.rest; count _ count+1};
ENDLOOP;
IF count=0 THEN EXIT;
offSetCnts _ CONS[[offSet, count], offSetCnts];
IF minDif=LAST[INT] THEN EXIT;
offSet _ offSet-minDif;
ENDLOOP};
<<Register layout atoms>>
[] _ PWCore.RegisterLayoutAtom[stackLayoutProp, StackLayout, StackDecorate, StackAttributes];
[] _ PWCore.RegisterLayoutAtom[stackLayoutRawProp, StackLayout, StackDecorate, NIL];

END.