CoreRouteImpl.mesa
Copyright Ó 1985, 1986, 1987 by Xerox Corporation. All rights reserved.
Bertrand Serlet September 26, 1987 2:08:17 pm PDT
Louis Monier September 7, 1987 2:44:20 am PDT
Ross November 7, 1986 3:41:23 pm PST
Don Curry February 24, 1988 9:25:11 am PST
Barth, October 6, 1987 3:56:51 pm PDT
Christian Le Cocq January 4, 1988 5:48:06 pm PST
DIRECTORY
CD, CDBasics, CDCells, CDDirectory, CDInstances, CDRects, CDRoutingObjects, CDSimpleRules,
CedarProcess,
Core, CoreClasses, CoreFlat, CoreGeometry, CoreOps, CoreProperties,
CoreRoute,
DABasics,
GList, IO, Properties, PW, PWCore, RefTab, Rope, RopeList, Route, Sinix, Sisyph, SymTab, TerminalIO;
CoreRouteImpl: CEDAR PROGRAM    
IMPORTS CD, CDBasics, CDCells, CDDirectory, CDInstances, CDRects, CoreRoute, CDRoutingObjects, CDSimpleRules, CedarProcess, CoreClasses, CoreFlat, CoreGeometry, CoreOps, CoreProperties, GList, IO, Properties, PW, PWCore, RefTab, Rope, RopeList, Route, Sinix, Sisyph, SymTab, TerminalIO
EXPORTS CoreRoute
SHARES CDCells, CDRects =
BEGIN OPEN CoreRoute;
Belongs in CoreFlat
MakeAcceptableShortName: PROC [proposed: Rope.ROPE]
RETURNS [name: Rope.ROPENIL] = {
name ← proposed;
FOR i: INT IN [0..Rope.Length[proposed]) DO
char: CHAR ← Rope.Fetch[proposed, i];
IF NOT (char IN ['0..'9] OR char IN ['A..'Z] OR char IN ['a..'z]) THEN
{name ← Rope.Cat["{", proposed, "}"]; EXIT} ENDLOOP};
Labelling
LabelInternal: PUBLIC PROC [internal: Core.WireSeq, wire: Wire] RETURNS [Route.Label]={
RETURN [MakeAcceptableShortName[CoreOps.GetFullWireName[internal, wire]]]};
LabelFlatWire: PUBLIC PROC [root: Core.CellType, flatWire: CoreFlat.FlatWireRec]
RETURNS [Route.Label] = {
name: Rope.ROPE ← CoreFlat.WirePathRope[root, CoreFlat.CanonizeWire[root, flatWire]];
IF Rope.EqualSubstrs[s1: name, len1: 7, s2: "public."] THEN name ← Rope.Substr[name, 7];
RETURN [MakeAcceptableShortName[name]]};
LabelBrokenNet: PUBLIC PROC [label: Route.Label, number: NAT] RETURNS [Route.Label] =
{RETURN [IO.PutFR["{%g#%g}", IO.rope[label], IO.int[number]]]};
Schematics Analysis
layoutDecoration: CoreGeometry.Decoration ← PWCore.extractMode.decoration;
schDecoration:  CoreGeometry.Decoration ← Sisyph.mode.decoration;
WirePinSides:  TYPE = REF WirePinSidesArray;
WirePinSidesArray: TYPE = ARRAY Side OF WirePins ← ALL[NIL];
fudge:    INT = CD.FetchTechnology[$cmosB].lambda/2;
ReverseWirePins: PUBLIC PROC[pins: WirePins] RETURNS[rev: WirePins] =
{FOR pins ← pins, pins.rest WHILE pins#NIL DO rev ← CONS[pins.first, rev] ENDLOOP};
LayPins: PUBLIC PROC[cellType: CellType, side: Side] RETURNS[pins: WirePins] = {
[]←PWCore.Layout[cellType];
pins ← GetPins[$CoreRouteLayPins, side, cellType]};
SchPins: PUBLIC PROC[cellType: CellType, side: Side] RETURNS[pins: WirePins] =
{pins ← GetPins[$CoreRouteSchPins, side, cellType]};
GlobalWires: PUBLIC PROC[cellType: CellType] RETURNS[wires: Core.Wires] = {
FOR i: INT IN [0..cellType.public.size) DO
wire:  Wire ← cellType.public[i];
global: BOOL ← wire.size=0 AND ~CoreGeometry.HasPins[schDecoration, wire];
IF global THEN
FOR list: Core.Wires ← wires, list.rest WHILE list#NIL DO
IF list.first=wire THEN EXIT;
REPEAT FINISHED => wires ← CONS[wire, wires];
ENDLOOP;
ENDLOOP};
GetPins: PROC[key: ATOM, cSide: Side, cellType: CellType]
RETURNS[wirePins: WirePins ← NIL] = {
sides: WirePinSides ← NARROW[CoreProperties.GetCellTypeProp[cellType, key]];
IF sides=NIL THEN {
EachPin: CoreGeometry.EachWirePinProc =
{sides[side] ← CONS[[wire, min, max, layer], sides[side]]};
deco: CoreGeometry.Decoration ← SELECT key FROM
$CoreRouteSchPins => schDecoration,
$CoreRouteLayPins => layoutDecoration, ENDCASE => ERROR;
sides ← NEW[WirePinSidesArray];
[]𡤌oreGeometry.EnumerateNonOverlappingSides[deco, cellType, EachPin];
FOR side: Side IN Side DO sides[side] ← ReverseWirePins[sides[side]] ENDLOOP;
CoreProperties.PutCellTypeProp[cellType, key, sides]};
RETURN[sides[cSide]]};
FlattenWiresWithUnambiguousSchPins: PROC[struc: Core.Wires]
RETURNS[atomics: Core.Wires] = {
AddSchAtomic: PROC[wire: Wire, parentalPins: BOOL] = {
hasPins: BOOL ← CoreGeometry.HasPins[schDecoration, wire];
IF parentalPins AND hasPins THEN RETURN; -- inherit only if unspecified
IF wire.size=0
THEN atomics ← CONS[wire, atomics]
ELSEFOR i: INT IN [0..wire.size)
DO AddSchAtomic[wire[i], parentalPins OR hasPins] ENDLOOP};
FOR struc ← struc, struc.rest WHILE struc#NIL DO
AddSchAtomic[struc.first, FALSE] ENDLOOP;
atomics ← CoreOps.Reverse[atomics]};
FilteredCellTypeLayoutPins: PUBLIC PROC[cellType: CellType, side: Side]
RETURNS[pins: WirePins] = {
pins ← LayPins[cellType, side];
IF CoreGeometry.HasObject[schDecoration, cellType] THEN pins ← FilterPins[pins, OrderedAtomicSchWires[cellType, side], GlobalWires[cellType]]};
FilteredInstanceLayoutPins: PUBLIC PROC[inst: CoreClasses.CellInstance, side: Side]
RETURNS[pins: WirePins] = {
bindings:  RefTab.Ref ← CoreOps.CreateBindingTable[inst.type.public, inst.actual];
ctPins:  WirePins  ← FilteredCellTypeLayoutPins[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 ← ReverseWirePins[pins]};
OrderedAtomicSchWires: PUBLIC PROC
[cellType: CellType, side: Side, min: INTFIRST[INT], max: INTLAST[INT]]
RETURNS [wires: Core.Wires] = {
schWires: Core.Wires;
wirePins: WirePins  ← SchPins[cellType, side];
FOR wirePins ← wirePins, wirePins.rest WHILE wirePins#NIL DO
IF wirePins.first.min>=min THEN EXIT ENDLOOP;
FOR wirePins ← wirePins, wirePins.rest WHILE wirePins#NIL DO
IF wirePins.first.max>max THEN EXIT;
schWires ← CONS[wirePins.first.wire, schWires] ENDLOOP;
schWires ← CoreOps.Reverse[schWires];
wires  ← FlattenWiresWithUnambiguousSchPins[schWires]};
FlushSchPinCache: PUBLIC PROC[cellType: CellType] =
{CoreProperties.PutCellTypeProp[cellType, $CoreRouteSchPins, NIL]};
FlushLayPinCache: PUBLIC PROC[cellType: CellType] =
{CoreProperties.PutCellTypeProp[cellType, $CoreRouteLayPins, NIL]};
Sort2DInstances: PUBLIC PROC[cellType: CellType] = {
TwoInstances: TYPE = RECORD[i0, i1: CoreClasses.CellInstance];
data: CoreClasses.RecordCellType ← NARROW [cellType.data];
DO
done: BOOLTRUE;
FOR i: NAT IN [0..data.size-1) DO
ir1: CD.Rect ← SchMappedIR[data[i]];
ir2: CD.Rect ← SchMappedIR[data[i+1]];
IF CompareOrigin[ir1, ir2] THEN LOOP;
[data[i], data[i+1]] ← TwoInstances[data[i+1], data[i]];
done ← FALSE; ENDLOOP;
IF done THEN EXIT ENDLOOP};
SortedInstanceArray: PUBLIC PROC[cellType: CellType] RETURNS[ia: InstanceArray] = {
data:   CoreClasses.RecordCellType ← NARROW [cellType.data];
xIntervals: Intervals  ← NIL;
yIntervals: Intervals  ← NIL;
rows:   INT   ← 0;
cols:   INT   ← 0;
index:   INT   ← 0;
FOR i: NAT IN [0..data.size) DO
ir:  CD.Rect ← SchMappedIR[data[i]];
xIntervals  ← MergeInterval[[ir.x1, ir.x2], xIntervals];
yIntervals  ← MergeInterval[[ir.y1, ir.y2], yIntervals] ENDLOOP;
FOR list: Intervals ← xIntervals, list.rest WHILE list#NIL DO cols ← cols+1  ENDLOOP;
FOR list: Intervals ← yIntervals, list.rest WHILE list#NIL DO rows ← rows+1 ENDLOOP;
ia ← NEW[InstanceArraySeq[rows]];
FOR row: INT IN [0..rows) DO ia[row] ← NEW[InstanceRowSeq[cols]] ENDLOOP;
FOR i: NAT IN [0..data.size) DO
ir:  CD.Rect ← SchMappedIR[data[i]];
row, col: INT ← 0;
FOR list: Intervals ← xIntervals, list.rest WHILE list#NIL DO
IF list.first.max >=ir.x2 THEN EXIT; col ← col+1 ENDLOOP;
FOR list: Intervals ← yIntervals, list.rest WHILE list#NIL DO
IF list.first.max >= ir.y2 THEN EXIT; row ← row+1 ENDLOOP;
IF ia[row][col]#NIL THEN ERROR; -- confused positions
ia[row][col] ← data[i] ENDLOOP;
FOR row: INT IN [0..rows) DO
FOR col: INT IN [0..cols) DO
IF ia[row][col]#NIL THEN {data[index] ← ia[row][col]; index ← index+1};
ENDLOOP;
ENDLOOP;
IF index#data.size THEN ERROR};
ShowInstanceArray: PUBLIC PROC [ia: InstanceArray] ~ {
TerminalIO.PutF["Instance Array: %g x %g\n", IO.int[ia.size], IO.int[ia[0].size]]};
MergeInterval : PROC[intvl: Interval, intvls: Intervals] RETURNS[result: Intervals] = {
result ← CONS[intvl, intvls];
FOR intvls ← result, intvls.rest WHILE intvls#NIL AND intvls.rest#NIL DO
TwoIntervals: TYPE = RECORD[A, B: Interval];
pair:    TwoIntervals ← [intvls.first, intvls.rest.first];
IF pair.A.max <= pair.B.min + fudge THEN RETURN;
IF pair.B.max  <= pair.A.min + fudge
THEN [intvls.first, intvls.rest.first] ← TwoIntervals[intvls.rest.first, intvls.first]
ELSE {
intvls.first ← [MIN[pair.A.min, pair.B.min], MAX[pair.A.max, pair.B.max]];
intvls.rest ← intvls.rest.rest; RETURN}
ENDLOOP};
Interval: TYPE = RECORD[min, max: INT ← 0];
Intervals: TYPE = LIST OF Interval ← NIL;
Decorate Procs
CompareRecordCellInstances: PUBLIC CompareFlatCTProc = {
index1, index2: NAT;
UnboundFlatCell1: CoreFlat.UnboundFlatCellProc = {
IF flatCell=flatCT1 THEN {index1 ← index; RETURN};
CoreFlat.NextUnboundCellType[cell: cell, target: target, flatCell: flatCell, instance: instance, index: index, parent: parent, flatParent: flatParent, data: data, proc: UnboundFlatCell1]};
UnboundFlatCell2: CoreFlat.UnboundFlatCellProc = {
IF flatCell=flatCT2 THEN {index2 ← index; RETURN};
CoreFlat.NextUnboundCellType[cell: cell, target: target, flatCell: flatCell, instance: instance, index: index, parent: parent, flatParent: flatParent, data: data, proc: UnboundFlatCell2]};
UnboundFlatCell1[cell: root, target: flatCT1];
UnboundFlatCell2[cell: root, target: flatCT2];
RETURN [index1 < index2]};
CompareInX:     PUBLIC PROC [rect1: CD.Rect, rect2: CD.Rect] RETURNS [BOOL] =
{RETURN[rect1.x1 < rect2.x1]};
CompareInY:     PUBLIC PROC [rect1: CD.Rect, rect2: CD.Rect] RETURNS [BOOL] =
{RETURN[rect1.y1 < rect2.y1]};
CompareReverseInX:   PUBLIC PROC [rect1: CD.Rect, rect2: CD.Rect] RETURNS [BOOL] =
{RETURN[rect1.x1 > rect2.x1]};
CompareReverseInY:   PUBLIC PROC [rect1: CD.Rect, rect2: CD.Rect] RETURNS [BOOL] =
{RETURN[rect1.y1 > rect2.y1]};
CompareXorYStack: PUBLIC PROC [rect1: CD.Rect, rect2: CD.Rect] RETURNS [BOOL] = {
overlappingInY: BOOL ← rect1.y1+fudge<rect2.y2 AND rect2.y1+fudge<rect1.y2;
RETURN[IF overlappingInY
THEN rect1.x1 < rect2.x1
ELSE rect1.y1 < rect2.y1]};
CompareOrigin: PUBLIC PROC [rect1: CD.Rect, rect2: CD.Rect] RETURNS [BOOL] = {
RETURN[IF rect1.y1 = rect2.y1
THEN rect1.x1 <= rect2.x1
ELSE rect1.y1 < rect2.y1]};
EnumerateRoutedArea: PUBLIC PROC [obj: CD.Object, eachRoutingCell, eachPatchWorkCell: EachComponentProc, trans: CoreGeometry.Transformation ← []]
RETURNS [quit: BOOLFALSE] = {
SELECT TRUE FROM
obj=NIL => ERROR; -- somehow the previous call returned a NIL expansion. Walkstack and debug!
PWCore.IsPWCoreGenerated[obj]  => IF eachPatchWorkCell#NIL THEN quit ← eachPatchWorkCell[obj, trans];
obj.class=CDRoutingObjects.routingClass => IF eachRoutingCell#NIL THEN quit ← eachRoutingCell[obj, trans];
obj.class=CDCells.pCellClass => {
EachInst: CDCells.InstEnumerator = {
quit ← EnumerateRoutedArea[inst.ob, eachRoutingCell, eachPatchWorkCell, CDBasics.ComposeTransform[itemInCell: inst.trans, cellInWorld: trans]];
};
quit ← CDCells.EnumerateInstances[obj, EachInst];
};
ENDCASE => quit ← EnumerateRoutedArea[CDDirectory.Expand1[obj].new, eachRoutingCell, eachPatchWorkCell, trans]};
ObjectIR: PROC [instance: REF CoreGeometry.Instance] RETURNS [ir: CD.Rect] =
{RETURN[CDBasics.MapRect[CD.InterestRect[instance^.obj], instance^.trans]]};
Returns
a table [Label -> CoreGeometry.Instances] that matches labels of Routing cells to geometry;
a list of all instances coming from Layout[].
CumulateRoutingsAndPWCells: PROC [obj: CD.Object] RETURNS [geometry: SymTab.Ref, pwCells: LIST OF REF CoreGeometry.Instance ← NIL] = {
EachRoutingCell: EachComponentProc = {
data: CDRoutingObjects.RoutingSpecific = NARROW [component.specific];
FOR i: NAT IN [0 .. data.size) DO
label: Route.Label ← NARROW [Properties.GetProp[data[i].properties, $SignalName]];
instances: CoreGeometry.Instances ← NARROW [SymTab.Fetch[geometry, label].val];
IF label=NIL THEN ERROR; -- What about the labels?!
FOR j: NAT IN [0 .. data[i].size) DO
po: CDRoutingObjects.PlacedObject = data[i][j];
instance: CoreGeometry.Instance ← CoreGeometry.Transform[trans, [po.object, [po.position]]];
IF CoreGeometry.AtEdge[ir, instance] THEN instances ← CONS [instance, instances];
ENDLOOP;
[] ← SymTab.Store[geometry, label, instances];
ENDLOOP;
};
EachPatchWorkCell: EachComponentProc = {
pwCells ← CONS [NEW [CoreGeometry.Instance ← [component, trans]], pwCells];
};
ir: CD.Rect = CD.InterestRect[obj];
geometry ← SymTab.Create[]; -- table [Label -> CoreGeometry.Instances] that matches labels of Routing cells to geometry.
[] ← EnumerateRoutedArea[obj, EachRoutingCell, EachPatchWorkCell]};
BoundCT: TYPE = RECORD [
cell: Core.CellType,
flatCell: CoreFlat.FlatCellTypeRec,
bindings: CoreFlat.Bindings,
trans: CoreGeometry.Transformation ← []];-- filled later, once sort is done
AddTransWireIRLazyPins: PROC [decoration: CoreGeometry.Decoration, public: Wire, indirect: Wire, trans: CoreGeometry.Transformation, ir: CD.Rect] = {
pins: CoreGeometry.Instances ← CoreGeometry.GetPins[decoration, public];
CoreGeometry.PutTransWireIRLazyPins[decoration, public, indirect, trans, ir];
CoreGeometry.AddPins[decoration, public, pins]};
DecorateRoutedArea: PUBLIC PROC [
cellType:   Core.CellType,
obj:    CD.Object,
wireToLabels: PROC [Wire] RETURNS [LIST OF Route.Label],
compareIR:  CompareIRProc   ← CompareOrigin,
compareCT:  CompareFlatCTProc  ← CompareRecordCellInstances] = {
ir: CD.Rect = CD.InterestRect[obj];
geometry: SymTab.Ref; -- table [Label -> CoreGeometry.Instances] that matches labels of Routing cells to geometry.
pwCells: LIST OF REF CoreGeometry.Instance; -- strange type, but makes sort easy
flatCTs: LIST OF REF BoundCT ← NIL; -- strange type, but makes sort easy
ComparePWCells: GList.CompareProc = {
RETURN [IF compareIR[ObjectIR[NARROW [ref1]], ObjectIR[NARROW [ref2]]]
THEN less ELSE greater]};
CompareBoundCT: GList.CompareProc = {
RETURN [IF compareCT[cellType, NARROW [ref1, REF BoundCT].flatCell, NARROW [ref2, REF BoundCT].flatCell] THEN less ELSE greater]};
BoundFlatCell: CoreFlat.BoundFlatCellProc = {
IF CoreGeometry.GetObject[layoutDecoration, cell]#NIL AND cell#cellType
THEN flatCTs ← CONS [NEW [BoundCT ← [cell, flatCell, RefTab.Copy[bindings]]], flatCTs]
ELSE CoreFlat.NextBoundCellType[cell: cell, target: target, flatCell: flatCell, instance: instance, index: index, parent: parent, flatParent: flatParent, data: data, bindings: bindings, proc: BoundFlatCell]};
DecoratePublic: PROC [wire: Wire] = {
flatWire: CoreFlat.FlatWire = NEW [CoreFlat.FlatWireRec ← [wire: wire]];
IF ~RefTab.Store[visitOnceTab, wire, wire] THEN RETURN; -- only once
FOR labels: LIST OF Route.Label ← wireToLabels[wire], labels.rest WHILE labels#NIL DO
CoreGeometry.AddPins[layoutDecoration, wire, NARROW [SymTab.Fetch[geometry, labels.first].val]];
ENDLOOP;
FOR list: LIST OF REF BoundCT ← flatCTs, list.rest WHILE list#NIL DO
EachSubPublic: PROC [subPub: Wire] = {
IF NOT CoreFlat.FlatWireEqual[RefTab.Fetch[list.first.bindings, subPub].val, flatWire] THEN RETURN;
AddTransWireIRLazyPins[layoutDecoration, wire, subPub, list.first.trans, ir];
};
CoreOps.VisitRootAtomics[list.first.cell.public, EachSubPublic];
ENDLOOP};
visitOnceTab: RefTab.Ref ← RefTab.Create[];
[geometry, pwCells] ← CumulateRoutingsAndPWCells[obj];
pwCells ← NARROW [GList.Sort[pwCells, ComparePWCells]];
BoundFlatCell[cell: cellType];
flatCTs ← NARROW [GList.Sort[flatCTs, CompareBoundCT]];
IF GList.Length[pwCells]#GList.Length[flatCTs] THEN ERROR;
FOR list: LIST OF REF BoundCT ← flatCTs, list.rest WHILE list#NIL DO
ct: Core.CellType = list.first.cell;
IF PWCore.Layout[ct]#pwCells.first.obj THEN ERROR;
list.first.trans ← pwCells.first.trans; -- the real aim of all that!
pwCells ← pwCells.rest;
ENDLOOP;
CoreOps.VisitRootAtomics[cellType.public, DecoratePublic];
RefTab.Erase[visitOnceTab]; visitOnceTab ← NIL};
IntanceToPObj: PROC [instance: CoreGeometry.Instance] RETURNS [po: CDRoutingObjects.PlacedObject] = {
IF instance.trans.orient=original THEN RETURN [[instance.obj, instance.trans.off]];
po.object ← SELECT TRUE FROM
instance.obj.class=CDRects.bareRectClass => CDRects.CreateRect[CDBasics.OrientedSize[CD.InterestSize[instance.obj], instance.trans.orient], instance.obj.layer],
-- Following class would be better, but not technology independent. So it is omitted!
instance.obj.class.atomicOb  => CDAtomicObjects.CreateAtomicOb[instance.obj.class.objectType, CDBasics.OrientedSize[CD.InterestSize[instance.obj], instance.trans.orient], CMosB.cmosB, instance.obj.layer],
ENDCASE => PW.CreateRotation[instance.obj, instance.trans.orient];
po.position ← CDBasics.SubPoints[CDBasics.BaseOfRect[CoreGeometry.BBox[instance]], CDBasics.BaseOfRect[CoreGeometry.BBox[[po.object, []]]]]};
MakeRoutingCell: PUBLIC PROC [cell: CD.Object, publicToLabel: PROC [Rope.ROPE] RETURNS [Route.Label]] RETURNS [routingCell: CD.Object] = {
Leaf: CoreGeometry.LeafProc = {RETURN [FALSE]};
EachFlatWire: CoreGeometry.EachFlatWireProc = {
EachInstance: CoreGeometry.EachInstanceProc = {
geometry^ ← CONS [IntanceToPObj[CoreGeometry.Transform[trans, instance]], geometry^];
};
name: Rope.ROPE;
geometry: REF LIST OF CDRoutingObjects.PlacedObject;
IF flatWire.flatCell#CoreFlat.rootCellType THEN ERROR; -- wire is an internal, not a public!
name ← publicToLabel[CoreOps.GetShortWireName[flatWire.wire]];
geometry ← NARROW [SymTab.Fetch[nodes, name].val];
IF geometry=NIL THEN {geometry ← NEW [LIST OF CDRoutingObjects.PlacedObject ← NIL]; [] ← SymTab.Store[nodes, name, geometry]};
[] ← CoreGeometry.EnumerateGeometry[mode.decoration, wire, EachInstance]};
nodes: SymTab.Ref ← SymTab.Create[]; -- Table Real names -> REF LIST OF PObj
mode: Sinix.Mode = PWCore.extractMode;
ct: Core.CellType ← NARROW [Sinix.Extract[cell, mode].result];
[] ← CoreGeometry.EnumerateFlatGeometry[decoration: mode.decoration, root: ct, leafProc: Leaf, eachFlatWire: EachFlatWire];
routingCell ← CDRoutingObjects.CreateRoutingObject[CDRoutingObjects.CreateNodes[nodes], CD.InterestRect[cell]]};
Extension
ExtendSegment: PUBLIC ExtendSegmentProc = {
IF extension=0 THEN RETURN;
RETURN [CDRects.CreateRect[
IF side=top OR side=bottom THEN [size, extension] ELSE [extension, size],
layer]]};
ExtendObject: PUBLIC PROC [enumerateSegments: PROC [PROC [Segment]], size: CD.Position, side: CoreGeometry.Side, extendProc: ExtendSegmentProc ← ExtendSegment] RETURNS [extension: CD.Object] = {
EachSegment: PROC [segment: Segment] = {
pos: REF LIST OF CDRoutingObjects.PlacedObject ← NARROW [SymTab.Fetch[nodes, segment.label].val];
extobj: CD.Object ← extendProc[segment.label, segment.max-segment.min, segment.layer, side, extend];
IF extobj=NIL THEN RETURN;
IF pos=NIL THEN {pos ← NEW [LIST OF CDRoutingObjects.PlacedObject ← NIL]; [] ← SymTab.Store[nodes, segment.label, pos]};
pos^ ← CONS [
[object: extobj,
position: IF side=top OR side=bottom THEN [segment.min, 0] ELSE [0, segment.min]],
pos^]};
nodes: SymTab.Ref ← SymTab.Create[];
extend: INTIF side=top OR side=bottom THEN size.y ELSE size.x;
enumerateSegments[EachSegment];
extension ← CDRoutingObjects.CreateRoutingObject[nodes: CDRoutingObjects.CreateNodes[nodes], ir: [0, 0, size.x, size.y]]};
Old Layout Proc for Extension
LayoutExtend: PWCore.LayoutProc = {
l:    INT        = CD.FetchTechnology[$cmosB].lambda;
rct:   CoreClasses.RecordCellType = NARROW [cellType.data];
subObject: CD.Object       = PWCore.Layout[rct[0].type];
isize:   CD.Position      = CD.InterestSize[subObject];
cdInstances: CD.InstanceList     ← LIST [CDInstances.NewInst
[ob: subObject, trans: [CDBasics.NegOffset[CD.InterestBase[subObject]]] ] ];
globals:  Core.Wires      ← GlobalWires[cellType];
IF rct.size#1 THEN ERROR;
FOR eside: CoreGeometry.Side IN CoreGeometry.Side DO
ePins:  WirePins;
eWires: Core.Wires;
sideProperty: ATOM = SELECT eside FROM
top  => $Top,
bottom => $Bottom,
right  => $Right,
left  => $Left,
ENDCASE => ERROR;
refExtension: REF INTNARROW [CoreProperties.GetCellTypeProp[cellType, sideProperty]];
extension: INT = IF refExtension=NIL THEN 0 ELSE refExtension^*l;
extensionSize: CD.Position = SELECT eside FROM
top, bottom => [isize.x, extension],
right, left => [extension, isize.y],
ENDCASE  => ERROR;
extensionPosition: CD.Position = SELECT eside FROM
top  => [0, isize.y],
bottom => [0, -extension],
right  => [isize.x, 0],
left  => [-extension, 0],
ENDCASE => ERROR;
EnumerateSegments: PROC [eachSegment: PROC [Segment]] = {
FOR pins: WirePins ← ePins, pins.rest WHILE pins#NIL DO
label: Route.Label ← LabelInternal[rct.internal, pins.first.wire];
eachSegment[[label, pins.first.min, pins.first.max, pins.first.layer]] ENDLOOP};
IF extension=0 THEN LOOP;
eWires  ← OrderedAtomicSchWires[cellType, eside];  -- parent
ePins   ← FilteredInstanceLayoutPins[rct[0], eside]; -- child
ePins   ← FilterPins[ePins, eWires, globals];
cdInstances ← CONS [
CDInstances.NewInst[
ob: ExtendObject[EnumerateSegments, extensionSize, eside],
trans: [extensionPosition]],
cdInstances];
ENDLOOP;
obj ← PW.CreateCell[instances: cdInstances];
don't flush parent since likely to need
FlushLayPinCache[rct[0].type]; -- flush childs layout pins cache
FlushSchPinCache[rct[0].type]}; -- flush childs schematic pins cache
DecorateExtend: PWCore.DecorateProc = {
rct: CoreClasses.RecordCellType = NARROW [cellType.data];
WireToLabels: PROC [wire: Wire] RETURNS [LIST OF Route.Label] = {
RETURN [LIST [LabelInternal[rct.internal, wire]]]};
DecorateRoutedArea[cellType, obj, WireToLabels, CompareInX]};
Channel
SchMappedIR: PUBLIC PROC [instance: CoreClasses.CellInstance] RETURNS [ir: CD.Rect] = {
trans: CD.Transformation = CoreGeometry.GetTrans[schDecoration, instance];
IF trans.orient#original THEN ERROR; -- Rotated instances are not allowed.
ir ← CD.InterestRect[CoreGeometry.GetObject[schDecoration, instance.type]];
ir ← CDBasics.MapRect[ir, trans]};
ChannelAttribute: PWCore.AttributesProc = {
ambiguous, inX: BOOL;
rules: REF = CoreProperties.GetCellTypeProp[cellType, $DesignRules];
tech: REF = IF rules=NIL THEN $cmosB ELSE rules;
trunk: REF = CoreProperties.GetCellTypeProp[cellType, $Trunk];
branch: REF = CoreProperties.GetCellTypeProp[cellType, $Branch];
justifyTopOrRight: BOOL = GetJustification[cellType] = topRight;
refWidth: REF INT = NARROW [CoreProperties.GetCellTypeProp[cellType, $TotalWidth]];
rct: CoreClasses.RecordCellType = NARROW [cellType.data]; -- we assume here we have a record cell
min, max: INT;
IF rct.size#2 THEN ERROR; -- exactly two cells per channel
[ambiguous, inX] ← PWCore.InstancesInXOrY[schDecoration, cellType, fudge];
IF ambiguous THEN ERROR;
PWCore.SortInstances[schDecoration, cellType, IF inX THEN PWCore.SortInX ELSE PWCore.SortInY];
IF inX
THEN {min ← SchMappedIR[rct[0]].x2; max ← SchMappedIR[rct[1]].x1}
ELSE {min ← SchMappedIR[rct[0]].y2; max ← SchMappedIR[rct[1]].y1};
CoreProperties.PutCellTypeProp[
cellType, $ChannelInfo,
NEW [ChannelInfoRec ← [
direction: IF inX THEN vertical ELSE horizontal,
tech: tech,
trunk: IF trunk=NIL THEN "metal" ELSE trunk,
branch: IF branch=NIL THEN "metal2" ELSE branch,
justify: TRUE, 
justifyBottomOrLeft: ~justifyTopOrRight,
bottomOrLeftWires: OrderedAtomicSchWires[cellType, IF inX THEN bottom ELSE left, min, max],
topOrRightWires: OrderedAtomicSchWires[cellType, IF inX THEN top ELSE right, min, max],
totalWidth: IF refWidth=NIL THEN 0 ELSE refWidth^ ]] ]};
TrunkDim: PROC [obj: CD.Object, direction: DABasics.Direction] RETURNS [INT] ~
{RETURN[IF direction=vertical THEN CD.InterestSize[obj].y ELSE CD.InterestSize[obj].x]};
BranchDim: PROC [obj: CD.Object, direction: DABasics.Direction] RETURNS [INT] ~
{RETURN[IF direction=vertical THEN CD.InterestSize[obj].x ELSE CD.InterestSize[obj].y]};
Member: PROC [wires: Core.Wires, wire: Wire] RETURNS [BOOL] = {
IF CoreOps.Member[wires, wire] THEN RETURN [TRUE];
WHILE wires#NIL DO
IF CoreOps.RecursiveMember[wires.first, wire] THEN RETURN [TRUE];
wires ← wires.rest;
ENDLOOP;
RETURN [FALSE]};
Nets: TYPE = SymTab.Ref;
Nets is a SymTab Route.Label -> NetInfo that records all the information necessary for calling the channel router. It is stored under the property $Nets, on the cellType, and the decorateProc assumes that this property is present.
NetInfo: TYPE = REF NetInfoRec;
NetInfoRec: TYPE = RECORD [
auxLabels: LIST OF Route.Label ← NIL, -- for broken nodes
mayExit: BOOLFALSE,
trunkSize: INT ← 0,
exitLeftOrBottom, exitRightOrTop: BOOLFALSE,
pins: LIST OF SMMLNIL ];
SMML: TYPE = RECORD [
bottomOrLeftSide: BOOL,
min, max: CD.Number ← 0,
layer: CD.Layer ];
wireWidthProp: ATOM = $w;
Creates a new netInfo if not already there.
FetchNetInfo: PROC [nets: Nets, root: Core.WireSeq, wire: Wire] RETURNS [netInfo: NetInfo] = {
lambda: INT ← CDSimpleRules.GetTechnology[$cmosB].lambda;
label: Route.Label = 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]};
NotePinsEdge: PROC [nets: Nets, root: Core.WireSeq, inst: CoreClasses.CellInstance, side: DABasics.Side, layer: CD.Layer, extension: INT] = {
FOR wirePins: WirePins ← FilteredInstanceLayoutPins[inst, side], wirePins.rest WHILE wirePins#NIL DO
pin: WirePin = wirePins.first;
IF pin.layer=layer THEN {
netInfo: NetInfo ← FetchNetInfo[nets, root, pin.wire];
netInfo.pins ← CONS [[bottomOrLeftSide: side=top OR side=right, min: pin.min+extension, max: pin.max+extension, layer: layer], netInfo.pins]};
ENDLOOP};
ExtendChannelObject: PROC [nets: Nets, root: Core.WireSeq, inst: CoreClasses.CellInstance, direction: DABasics.Direction, layer: CD.Layer, extension: INT, justifyBottomOrLeft: BOOL] RETURNS [extended: CD.Object] = {
extensionSide: CoreGeometry.Side = IF justifyBottomOrLeft
THEN (IF direction=vertical THEN top ELSE right)
ELSE (IF direction=vertical THEN bottom ELSE left);
EnumerateSegments: PROC [eachSegment: PROC [Segment]] = {
EachWirePin: CoreGeometry.EachWirePinProc = {
actualWire: Wire = CoreClasses.CorrespondingActual[inst, wire];
IF side#extensionSide THEN RETURN;
[] ← FetchNetInfo[nets, root, actualWire];
eachSegment[[LabelInternal[root, actualWire], min, max, layer]]};
[] ← CoreGeometry.EnumerateWireSides[layoutDecoration, inst.type, EachWirePin]};
cell: CD.Object = PWCore.Layout[inst.type];
extensionCell: CD.Object;
IF extension=0 THEN RETURN [cell];
extensionCell ← ExtendObject[
EnumerateSegments,
IF direction=vertical THEN [CD.InterestSize[cell].x, extension] ELSE [extension, CD.InterestSize[cell].y],
extensionSide ];
extended ← IF justifyBottomOrLeft
THEN (IF direction=vertical THEN PW.AbutY ELSE PW.AbutX)[cell, extensionCell]
ELSE (IF direction=vertical THEN PW.AbutY ELSE PW.AbutX)[extensionCell, cell]};
Assumes channelData is the cellType itself, and that the field nets is properly filled in channelInfo.
EnumerateChannelNets: Route.EnumerateChannelNetsProc = {
cellType: Core.CellType = NARROW [channelData];
channelInfo: ChannelInfo = NARROW [CoreProperties.GetCellTypeProp[cellType, $ChannelInfo]];
nets: Nets = NARROW [CoreProperties.GetCellTypeProp[cellType, $Nets]];
EachNet: SymTab.EachPairAction = {
label: Route.Label = key;
netInfo: NetInfo = NARROW [val];
IF netInfo.exitLeftOrBottom OR netInfo.exitRightOrTop OR netInfo.pins#NIL THEN eachNet[
name: key, enumeratePins: EnumerateChannelPins,
exitLeftOrBottom: netInfo.exitLeftOrBottom, exitRightOrTop: netInfo.exitRightOrTop,
mayExit: netInfo.mayExit, trunkSize: netInfo.trunkSize,
channelData: channelData, netData: netInfo ]};
[] ← SymTab.Pairs[nets, EachNet]};
Assumes that netData is of type NetInfo.
EnumerateChannelPins: Route.EnumerateChannelPinsProc = {
netInfo: NetInfo = NARROW [netData];
FOR pins: LIST OF SMML ← netInfo.pins, pins.rest WHILE pins#NIL DO
pin: SMML = pins.first;
eachPin[bottomOrLeftSide: pin.bottomOrLeftSide, min: pin.min, max: pin.max, layer: pin.layer];
ENDLOOP};
Assumes that netData is of type NetInfo.
BrokenNets: Route.BrokenNetProc = {
netInfo: NetInfo = NARROW [netData];
auxLabels: LIST OF Route.Label ← netInfo.auxLabels;
newLabel ← IO.PutFR["{%g#%g}", IO.rope[sourceNet], IO.int[regionNumber]];
IF NOT RopeList.Memb[auxLabels, newLabel]
THEN netInfo.auxLabels ← CONS [newLabel, auxLabels]};
ChannelLayout: PUBLIC PWCore.LayoutProc = {
channelInfo: ChannelInfo ← NARROW [CoreProperties.GetCellTypeProp[cellType, $ChannelInfo]];
BEGIN OPEN channelInfo;
MarkBreakable: PROC [wire: Wire] = {
netInfo: NetInfo ← FetchNetInfo[nets, data.internal, wire];
netInfo.mayExit ← TRUE};
NoteBottomOrLeft: PROC [wire: Wire] = {
netInfo: NetInfo ← FetchNetInfo[nets, data.internal, wire];
netInfo.exitLeftOrBottom ← TRUE};
NoteTopOrRight: PROC [wire: Wire] = {
netInfo: NetInfo ← FetchNetInfo[nets, data.internal, wire];
netInfo.exitRightOrTop ← TRUE};
l: INT = CD.FetchTechnology[$cmosB].lambda;
data: CoreClasses.RecordCellType ← NARROW [cellType.data];
nets: SymTab.Ref ← SymTab.Create[];
priority: CedarProcess.Priority ← CedarProcess.GetPriority[];
channel, extended1, extended2: CD.Object;
leftOrBottom: CD.Object ← PWCore.Layout[data[0].type];
rightOrTop: CD.Object ← PWCore.Layout[data[1].type];
leftOrBottomHeight: INT ← TrunkDim[leftOrBottom, direction];
rightOrTopHeight: INT ← TrunkDim[rightOrTop, direction];
channelHeight: INT = MAX[leftOrBottomHeight, rightOrTopHeight];
wantedWidth: INT = totalWidth*l-BranchDim[leftOrBottom, direction]-BranchDim[rightOrTop, direction]; -- only meaningful if totalWidth#0
leftOrBottomExtend: INTIF justify THEN channelHeight - leftOrBottomHeight ELSE 0;
rightOrTopExtend: INTIF justify THEN channelHeight - rightOrTopHeight ELSE 0;
rulesParameters: Route.DesignRulesParameters = Route.DefaultDesignRulesParameters[
technologyHint: tech,
horizLayer: CDSimpleRules.GetLayer[tech, IF direction=horizontal THEN trunk ELSE branch],
vertLayer: CDSimpleRules.GetLayer[tech, IF direction=vertical THEN trunk ELSE branch],
trunkDirection: direction ];
intermediateResult: Route.IntermediateResult;
IF data.size#2 THEN ERROR;
We mark the public as wires which can be broken at exit
CoreOps.VisitRootAtomics[cellType.public, MarkBreakable];
We note the wires which exit
CoreOps.VisitRootAtomics[CoreOps.CreateWire[bottomOrLeftWires], NoteBottomOrLeft];
CoreOps.VisitRootAtomics[CoreOps.CreateWire[topOrRightWires], NoteTopOrRight];
We note the pins on the edges
NotePinsEdge[nets, data.internal, data[0], IF direction=vertical THEN right ELSE top, CDSimpleRules.GetLayer[tech, branch], IF justifyBottomOrLeft THEN 0 ELSE leftOrBottomExtend];
NotePinsEdge[nets, data.internal, data[1], IF direction=vertical THEN left ELSE bottom, CDSimpleRules.GetLayer[tech, branch], IF justifyBottomOrLeft THEN 0 ELSE rightOrTopExtend];
We make the extended objects and note the pins, on the way
extended1 ← ExtendChannelObject[nets, data.internal, data[0], direction, CDSimpleRules.GetLayer[tech, trunk], leftOrBottomExtend, justifyBottomOrLeft];
extended2 ← ExtendChannelObject[nets, data.internal, data[1], direction, CDSimpleRules.GetLayer[tech, trunk], rightOrTopExtend, justifyBottomOrLeft];
check if interestRects do not match
IF TrunkDim[extended1, direction]#TrunkDim[extended2, direction] THEN ERROR;
CedarProcess.CheckAbort[];
CedarProcess.SetPriority[background];
CoreProperties.PutCellTypeProp[cellType, $Nets, nets];
intermediateResult ← Route.ChannelRoute[
enumerateNets: EnumerateChannelNets,
min: 0, max: channelHeight,
rulesParameters: rulesParameters,
rules: Route.DefaultDesignRules[rulesParameters],
channelData: cellType,
optimization: IF CoreProperties.GetCellTypeProp[cellType, $FastRoute]#NIL
THEN noIncompletes ELSE full,
signalSinglePinNets: TRUE,
signalCoincidentPins: TRUE
! Route.Signal => {TerminalIO.PutF["*** Routing warning: %g\n", IO.rope[explanation]]} ];
channel ← Route.ChannelRetrieve[
intermediateResult: intermediateResult,
enumerateNets: EnumerateChannelNets,
brokenNets: BrokenNets,
channelData: cellType,
retrieveRect: IF totalWidth=0
THEN NIL ELSE NEW [CD.Rect ← [0, 0, channelHeight, wantedWidth]]
! Route.Signal => {TerminalIO.PutF["*** Routing warning: %g\n", IO.rope[explanation]]}
].object;
IF channel=NIL THEN ERROR;
obj ← (IF direction=vertical THEN PW.AbutX ELSE PW.AbutY)[extended1, channel, extended2];
CedarProcess.SetPriority[priority];
END};
DecorateChannel: PWCore.DecorateProc = {
WireToLabels: PROC [wire: Wire] RETURNS [labels: LIST OF Route.Label ← NIL] = {
label: Route.Label = LabelInternal[data.internal, wire];
netInfo: NetInfo = FetchNetInfo[nets, data.internal, wire];
labels ← CONS [label, netInfo.auxLabels]};
data: CoreClasses.RecordCellType ← NARROW [cellType.data];
channelInfo: ChannelInfo ← NARROW [CoreProperties.GetCellTypeProp[cellType, $ChannelInfo]];
nets: Nets ← NARROW [CoreProperties.GetCellTypeProp[cellType, $Nets]];
DecorateRoutedArea[cellType, obj, WireToLabels, IF channelInfo.direction=horizontal THEN CompareInY ELSE CompareInX];
We make a sanity check that all wires appearing in bottomOrLeftWires and topOrRightWires have pins on their relative sides.
SanityCheck[cellType, channelInfo.bottomOrLeftWires, IF channelInfo.direction=horizontal THEN left ELSE bottom];
SanityCheck[cellType, channelInfo.topOrRightWires, IF channelInfo.direction=horizontal THEN right ELSE top]};
SanityCheck: PROC [cellType: Core.CellType, wires: Core.Wires, side: CoreGeometry.Side] = {
WHILE wires#NIL DO
EachSortedPin: CoreGeometry.EachSortedPinProc = {quit ← wire=wires.first};
IF wires.first.size=0 AND NOT CoreGeometry.EnumerateSortedSides[layoutDecoration, cellType, side, EachSortedPin] THEN SIGNAL SanityFailed[];
wires ← wires.rest;
ENDLOOP};
SanityFailed: SIGNAL [] = CODE; -- call implementor
Initialization
[] ← PWCore.RegisterLayoutAtom[$Extend, LayoutExtend, DecorateExtend];
[] ← PWCore.RegisterLayoutAtom[$RawChannelRoute, ChannelLayout, DecorateChannel];
[] ← PWCore.RegisterLayoutAtom[$ChannelRoute, ChannelLayout, DecorateChannel, ChannelAttribute];
END.