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 25, 1988 9:47:37 am 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𡤏orm.min; sections.first.abutMax𡤏orm.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: %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.