SXImpl.mesa
Creates a representation of the layout suitable for hierarchical analysis.
Copyright © 1984, 1985, 1986 by Xerox Corporation. All rights reserved.
Written by Mark Shand, September 12, 1983 11:40 pm
Last Edited by: Shand, March 13, 1985 2:57:23 pm PST
Last Edited by: Spreitzer, January 15, 1985 2:09:09 pm PST
Last Edited by: Jacobi, April 8, 1985 5:07:49 pm PST
Last edited by: Christian Jacobi, November 17, 1986 6:22:56 pm PST
Last edited by: gbb June 9, 1986 4:55:58 pm PDT
DIRECTORY
Atom USING [GetPName],
Basics USING [CompareINT, Comparison],
CD,
CDInstances,
CDBasics,
CDOps USING [LayerRope],
CDProperties USING [DCopyProps, GetProp, GetInstanceProp, GetListProp, PutInstanceProp],
Convert USING [RopeFromInt],
PropertyLists USING [GetProp, PropList, PutProp],
RedBlackTree USING [Compare, Create, DuplicateKey, GetKey, Insert, LookupNextLarger, LookupSmallest, Table],
RefTab USING [Create, EachPairAction, Fetch, GetSize, Insert, Pairs, Ref, Store],
Rope USING [Cat, FromRefText, Equal, ROPE],
SX USING [AdjustmentMode, AreaPerimRec, AttachedNode, BoxMapProc, Circuit, CircuitNode, Constraint, ConversionProc, LogicalCell, MapRec, MergeRec, MergeRecList, NodeLinkage, SignalName, SpinifexLayerIndex],
SXAccess USING [stopFlag, sxTech],
SXAccessInternal USING [GetLogicalCell, PutError],
SXAtoms USING [export, InstanceName, Rect, SignalName, spinifex],
SXQuadTree USING [AreaSplit, Store, QuadTree, QuadTreeRoot, Rectangle, RectDelta];
SXImpl: CEDAR PROGRAM
IMPORTS Atom, Basics, CD, CDInstances, CDBasics, CDOps, CDProperties, Convert, PropertyLists, RedBlackTree, RefTab, Rope, SXAccess, SXAccessInternal, SXAtoms, SXQuadTree
EXPORTS SX =
BEGIN
TYPES from Interface.
AreaPerimRec: TYPE = SX.AreaPerimRec;
AttachedNode: TYPE = SX.AttachedNode;
Circuit: TYPE = SX.Circuit;
Constraint: TYPE = SX.Constraint;
LogicalCell: TYPE = SX.LogicalCell;
MapRec: TYPE = SX.MapRec;
MergeRec: TYPE = SX.MergeRec;
NodeLinkage: TYPE = SX.NodeLinkage;
SignalName: TYPE = SX.SignalName;
SpinifexLayerIndex: TYPE = SX.SpinifexLayerIndex;
Implementation.
IllegalConstruct: PUBLIC ERROR [rect: CD.Rect, reason: Rope.ROPE] = CODE;
IllegalLayer: PUBLIC ERROR [rect: CD.Rect, lev: CD.Layer] = CODE;
specialLayers: CD.Layer = MAX [CD.shadeLayer, CD.errorLayer, CD.backgroundLayer, CD.outlineLayer, CD.selectionLayer, CD.commentLayer];
repetitionInstanceNamePrefix: Rope.ROPE ← "";
repetitionInstanceNamePostfix: Rope.ROPE ← "";
IsSimpleRect: PROC [ob: CD.Object] RETURNS [BOOL] = INLINE BEGIN
RETURN [ob.class.objectType = SXAtoms.Rect]
END; -- IsSimpleRect
TranslateChild: CD.DrawProc = BEGIN
--PROC [inst: Instance, trans: Transformation, pr: REF DrawInformation]
sxThrough: REF LogicalCell = NARROW [pr.devicePrivate]; 
cir: REF Circuit = sxThrough.circuit;
IF inst.ob.class.symbolic THEN RETURN;
IF IsSimpleRect[inst.ob] THEN {
IF inst.ob.layer > specialLayers THEN {
node: REF SX.CircuitNode = AddRect [cir: cir, lev: inst.ob.layer, dim: inst.ob.bbox, trans: trans
! IllegalLayer => {
SXAccessInternal.PutError[sxThrough.cellObj, rect, Rope.Cat["material on layer ", CDOps.LayerRope[lev], " must not appear as isolated rectangles.\n"]];
GOTO BadRect
}
];
IF node # NIL THEN CopyNodeProperties [cir, node, inst.properties];
EXITS BadRect => NULL
};
RETURN
} -- end simple rectangle.
ELSE {
sx: REF LogicalCell ← SXAccessInternal.GetLogicalCell [inst.ob];
IF (sx # NIL) AND (sx.analysisState = useCircuit) THEN {
--This object is a logical subcircuit.
subcircuit: REF Circuit = sx.circuit;
myInst: CD.Instance = NEW [CD.InstanceRep ← [ob: inst.ob, trans: trans, properties: CDProperties.DCopyProps [propList: inst.properties]]];
FOR i: SpinifexLayerIndex IN [0..SXAccess.sxTech.numSpinifexLayers) DO
IF subcircuit.spinifexLayers[i].private # NIL THEN {
IF (cir.subcircuits = NIL) OR (cir.subcircuits.first # myInst) THEN {
--It is the 1st non-empty geom-layer.
cir.subcircuits ← CONS [myInst, cir.subcircuits];
};
[] ← AddBox [cir: cir, trans: trans, spinifexLayer: i, dim: subcircuit.spinifexLayers[i].size, value: myInst];
}
ENDLOOP;
cir.linkageCount.inChildren ← cir.linkageCount.inChildren + subcircuit.linkageCount.inSelf + subcircuit.linkageCount.inChildren;
}
ELSE { -- expand special objects (transistors) and conditional objects
WITH CDProperties.GetProp [from: inst.ob.class.properties, prop: SXAtoms.spinifex] SELECT FROM
convProc: REF SX.ConversionProc =>
convProc^[inst, trans, cir
! IllegalConstruct => {
SXAccessInternal.PutError [sxThrough.cellObj, CDBasics.MapRect[itemInCell: rect, cellInWorld: trans], reason];
CONTINUE}
];
ENDCASE => inst.ob.class.drawMe[inst, trans, pr] -- analysis state: notYetDone
}
}
END; -- TranslateChild
TranslateRect: CD.DrawRectProc = BEGIN
IF CDBasics.NonEmpty[r] AND l # CD.errorLayer THEN {
sxc: REF LogicalCell = NARROW [pr.devicePrivate]; 
[] ← AddRect [cir: sxc.circuit, lev: l, dim: r
! IllegalLayer => {
SXAccessInternal.PutError [sxc.cellObj, rect, Rope.Cat ["rectangle on layer ", CDOps.LayerRope [lev], " cannot be analyzed in this context.\n"]];
CONTINUE}
]
}
END;
——————————
Stuff for RedBlackTree (used in TranslateGeometry)
SKey: TYPE = REF CD.Position; -- RedBlackTree.Key
SRec: TYPE = RECORD [key: SKey, instance: CD.Instance];
SData: TYPE = REF SRec; -- RedBlackTree.UserData
InstKey: RedBlackTree.GetKey = BEGIN
RETURN [NARROW [data, SData].key]
END; -- InstKey
InstComp: RedBlackTree.Compare = BEGIN
c: Basics.Comparison;
sk: SKey = NARROW [k];
d: SData = NARROW [data];
c ← Basics.CompareINT [sk.x, d.key.x];
IF c = equal THEN c ← Basics.CompareINT [sk.y, d.key.y];
RETURN [c]
END; -- InstComp
SInsert: PROCEDURE [s: RedBlackTree.Table, inst: CD.Instance] RETURNS [duplicate: BOOL] = BEGIN
ENABLE RedBlackTree.DuplicateKey => GOTO dupl;
sk: SKey ← NEW [CD.Position ← CDBasics.BaseOfRect[CDInstances.InstRectO[inst]]];
data: SData ← NEW [SRec ← [key: sk, instance: inst]];
RedBlackTree.Insert [s, data, sk];
Raises DuplicateKey if appl with same location already added.
RETURN [FALSE];
EXITS
dupl => RETURN [TRUE]
END; -- SInsert
——————————
PutInstanceNamesIfRepetition: PROC [cir: REF Circuit] = {
IF cir.subcircuits#NIL AND cir.subcircuits.rest#NIL AND cir.subcircuits.rest.rest#NIL THEN BEGIN
There are at least three subcircuits.
FOR sub: CD.InstanceList ← cir.subcircuits, sub.rest WHILE sub#NIL DO
IF cir.subcircuits.first.trans.orient # sub.first.trans.orient THEN EXIT;
IF cir.subcircuits.first.ob # sub.first.ob THEN EXIT;
REPEAT FINISHED => BEGIN
They all have the same orientation, and are all are of the same type.
sTab: RedBlackTree.Table = RedBlackTree.Create [InstKey, InstComp];
lastApp, currApp: SData;
delta: CD.Position;
FOR sub: CD.InstanceList ← cir.subcircuits, sub.rest WHILE sub#NIL DO
IF SInsert [sTab, sub.first] THEN GOTO EqualAppls; 
ENDLOOP;
lastApp ← NARROW [RedBlackTree.LookupSmallest[sTab]];
currApp ← NARROW [RedBlackTree.LookupNextLarger[sTab,lastApp.key]];
delta ← CDBasics.SubPoints[currApp.instance.trans.off, lastApp.instance.trans.off];
lastApp ← currApp;
WHILE (currApp ← NARROW[RedBlackTree.LookupNextLarger[sTab, lastApp.key]]) # NIL DO
IF delta # CDBasics.SubPoints[currApp.instance.trans.off, lastApp.instance.trans.off] THEN EXIT;
lastApp ← currApp;
REPEAT FINISHED => BEGIN
They are sorted. Hence they are logically a repetition.
index: INT ← 1;
FOR a: SData ← NARROW[RedBlackTree.LookupSmallest[sTab]], NARROW[RedBlackTree.LookupNextLarger[sTab, a.key]] WHILE a # NIL DO
IF CDProperties.GetInstanceProp[from: a.instance, prop: SXAtoms.InstanceName]=NIL THEN BEGIN
Provide default instance names for repetition elements.
Added by Spreitzer November 24, 1984 12:08:57 pm PST.
Genralized by Shand, March 13, 1985 2:20:08 pm PST.
instanceName: Rope.ROPE ← repetitionInstanceNamePrefix.Cat[Convert.RopeFromInt[index], repetitionInstanceNamePostfix];
CDProperties.PutInstanceProp [a.instance, SXAtoms.InstanceName, instanceName];
END;
index ← index+1
ENDLOOP
END;
ENDLOOP;
EXITS EqualAppls => NULL
END
ENDLOOP;
END
};
sxContextFilter: REF CD.ContextFilter;
TranslateGeometry: PUBLIC PROC [cell: REF LogicalCell] = BEGIN
Translates ChipNDale layers into Spinifex layers (e.g. only explicit contacts [which must be correct and hence are not checked] are allowed. Also a node number is assigned, which is used to identify the nodes.
The translation is performed using the drawRect mechanism of ChipNDale. The ChipNDale design is translated into a quad-tree. It is not possible to use a tesselation because of overlaps.
The quad-tree contains only cells already analysed. There are three types of rectangles in the Quad-Tree: 1. constraints; 2. material; 3. bounding boxes for subcell rectangles.
cir: REF Circuit = cell.circuit;
dr: CD.DrawRef = CD.CreateDrawRef [[
drawRect: TranslateRect,
drawChild: TranslateChild,
devicePrivate: cell,
contextFilter: sxContextFilter,
stopFlag: SXAccess.stopFlag
]];
cell.cellObj.class.drawMe[CDInstances.NewInst[cell.cellObj], [], dr];
--count devices
FOR link: LIST OF REF NodeLinkage ← cir.linkages, link.rest WHILE link#NIL DO
cir.linkageCount.inSelf ← cir.linkageCount.inSelf + 1
ENDLOOP;
PutInstanceNamesIfRepetition[cir];
END;
UniformBloat: PROC [d: INT] RETURNS [SXQuadTree.RectDelta] = INLINE {
RETURN [[d,d,d,d]]
};
AddRect: PUBLIC PROC [
cir: REF Circuit,
lev: CD.Layer,
dim: CD.Rect,
trans: CD.Transformation ← [],
value: REF SX.CircuitNode ← NIL]
RETURNS
[cirNode: REF SX.CircuitNode ← NIL] = BEGIN
IF SXAccess.sxTech.illegalLayer[lev] THEN
ERROR IllegalLayer [CDBasics.MapRect [itemInCell: dim, cellInWorld: trans], lev];
IF CDBasics.NonEmpty[dim] THEN -- Silently ignore empty boxes
FOR map: LIST OF MapRec ← SXAccess.sxTech.cdLayerMapping[lev], map.rest WHILE map#NIL DO
cn: REF SX.CircuitNode;
WITH map.first.value SELECT FROM
mappingFunc: REF SX.BoxMapProc => cn ← mappingFunc^[ cir: cir, dim: dim, trans: trans, node: (IF cirNode#NIL THEN cirNode ELSE value)];
ENDCASE => cn ← AddBox [cir: cir, spinifexLayer: map.first.spinifexLayer, dim: dim, trans: trans, interestBloat: UniformBloat[map.first.bloatFactor], value: (IF map.first.value#NIL THEN map.first.value ELSE value)];
IF cn#NIL THEN cirNode ← cn
ENDLOOP;
END; -- AddRect
AddEmptyBox: ERROR = CODE;
AddBox: PUBLIC PROC [
cir:  REF Circuit,
spinifexLayer: SpinifexLayerIndex,
dim:  CD.Rect,
trans: CD.Transformation ← [],
interestBloat: SXQuadTree.RectDelta ← [0,0,0,0],
value:  REF ANYNIL]
RETURNS
[cirNode: REF SX.CircuitNode ← NIL] = BEGIN
A: PROC [r: CD.Rect] RETURNS [area: INT] = INLINE BEGIN
area ← (r.x2-r.x1) * (r.y2-r.y1)
END; -- A
P: PROC [r: CD.Rect] RETURNS [perim: INT] = INLINE BEGIN
perim ← ((r.x2-r.x1) + (r.y2-r.y1)) * 2
END; -- P
IF ~CDBasics.NonEmpty [dim] THEN ERROR AddEmptyBox
ELSE {
bloatedDim, bloatedMapped, mappedDim: CD.Rect;
newRect: REF SXQuadTree.Rectangle;
bloatedDim ← [x1: dim.x1-interestBloat.dx1, y1: dim.y1-interestBloat.dy1,
x2: dim.x2+interestBloat.dx2, y2: dim.y2+interestBloat.dy2];
bloatedMapped ← CDBasics.MapRect [itemInCell: bloatedDim, cellInWorld: trans];
mappedDim ← CDBasics.MapRect [itemInCell: dim, cellInWorld: trans];
IF value = NIL THEN {
value ← cirNode ← NEW [SX.CircuitNode ← [
dim: LIST[[layer: spinifexLayer, area: A[dim], perim: P[dim]]],
loc: [CDBasics.Center[mappedDim], spinifexLayer]
]];
AddCircuitNode [cir, cirNode]
}
ELSE WITH value SELECT FROM
cn: REF SX.CircuitNode => {
cirNode ← cn; AdjustNode [cirNode, spinifexLayer, A[dim], P[dim]]
};
ENDCASE => NULL;
newRect ← NEW [SXQuadTree.Rectangle ← [
interestBound: bloatedMapped,
dimDecr: [
dx1: mappedDim.x1-bloatedMapped.x1,
dy1: mappedDim.y1-bloatedMapped.y1,
dx2: bloatedMapped.x2-mappedDim.x2,
dy2: bloatedMapped.y2-mappedDim.y2],
nodeInformation: value
]];
cir.spinifexLayers[spinifexLayer] ← SXQuadTree.Store [quadTree: cir.spinifexLayers[spinifexLayer], rect: newRect]
}
END; -- AddBox
MergeNode: PUBLIC PROC [circuit: REF Circuit, to, from: REF SX.CircuitNode] = BEGIN
calling LookupNode and equal test introduced by Ch. J. Jan 30, 1985
IF from.superceded#NIL THEN from ← LookupNode [from];
IF to.superceded#NIL THEN to ← LookupNode [to];
IF from=to THEN RETURN;
Combine areas and perimeters.
FOR fromList: LIST OF AreaPerimRec ← from.dim, fromList.rest WHILE fromList#NIL DO
AdjustNode [to, fromList.first.layer, fromList.first.area, fromList.first.perim]
ENDLOOP;
Combine properties.
CopyNodeProperties [circuit, to, from.properties];
from.properties ← NIL; from.superceded ← to
END; -- MergeNode
CopyNodeProperties: PROC [
circuit:  REF Circuit,
node:  REF SX.CircuitNode,
properties: PropertyLists.PropList,
qual:  LIST OF CD.Instance ← NIL] = BEGIN
CopySignal: PROC [sig: REF ANY, depth: INTEGER] RETURNS [REF SignalName] = BEGIN
Creates a SignalName RECORD with appropriate depth from a ChipNDale Signal name (ROPE) or an existing SignalName RECORD.
IF sig=NIL THEN RETURN [NIL];
WITH sig SELECT FROM
r: Rope.ROPE => RETURN [NEW[SignalName ← [depth: depth, name: r]]];
t: REF TEXT => RETURN [NEW[SignalName ← [depth: depth, name: Rope.FromRefText[t]]]];
a: ATOM => RETURN [NEW[SignalName ← [depth: depth, name: Atom.GetPName[a]]]];
s: REF SignalName => BEGIN
copyHead, copyTail: REF SignalName;
copyHead ← NEW [SignalName ← [depth: s.depth+depth, name: s.name, makePort: s.makePort]];
copyTail ← copyHead;
FOR source: REF SignalName ← s.alias, source.alias WHILE source#NIL DO
copyTail.alias ← NEW [SignalName ← [depth: source.depth+depth, name: source.name]];
copyTail ← copyTail.alias;
ENDLOOP;
RETURN [copyHead];
END;
ENDCASE => ERROR;
END; -- CopySignal
MergeAliases: PROC [to, from: REF SignalName] = BEGIN
WHILE from # NIL DO
FOR existingAlias: REF SignalName ← to, existingAlias.alias WHILE existingAlias#NIL DO
IF from.name.Equal[existingAlias.name] THEN BEGIN
IF from.depth < existingAlias.depth THEN existingAlias.depth ← from.depth;
from ← from.alias;
EXIT
END
REPEAT FINISHED => BEGIN
Insert in list.
tmp: REF SignalName = from;
from ← from.alias; tmp.alias ← to.alias; to.alias ← tmp
END
ENDLOOP
ENDLOOP
END; -- MergeAliases
fromSigProp: REF ANY ~ PropertyLists.GetProp [properties, SXAtoms.SignalName];
exportProp: REF ANY = PropertyLists.GetProp [properties, SXAtoms.export];
toSigProp: REF ANY ~ PropertyLists.GetProp [node.properties, SXAtoms.SignalName];
Copy Technology Dependent PropertyLists
IF SXAccess.sxTech.combineNodeProperties#NIL AND properties#NIL THEN
node.properties ←
SXAccess.sxTech.combineNodeProperties[circuit, node.properties, properties, qual];
Copy SignalName property
BEGIN
fromSignal: REF SignalName;
toSignal: REF SignalName;
depth: INTEGER ← 0;
FOR q: LIST OF CD.Instance ← qual, q.rest WHILE q#NIL DO
depth ← depth.SUCC
ENDLOOP;
fromSignal ← CopySignal [fromSigProp, depth];
IF fromSignal # NIL THEN fromSignal.makePort ← (fromSignal.makePort OR exportProp=$TRUE);
toSignal ← NARROW[toSigProp];
IF (toSignal # NIL) AND (fromSignal # NIL) THEN BEGIN
IF toSignal.depth > fromSignal.depth THEN BEGIN
node.properties ← PropertyLists.PutProp [node.properties, SXAtoms.SignalName, fromSignal];
MergeAliases [fromSignal, toSignal]
END
ELSE
MergeAliases [toSignal, fromSignal]
END
ELSE IF (fromSignal # NIL) THEN
node.properties ← PropertyLists.PutProp[node.properties, SXAtoms.SignalName, fromSignal]
END;
Delete UnMerged property.
node.properties ← PropertyLists.PutProp [node.properties, UnMerged];
END; -- CopyNodeProperties
AdjustNode: PUBLIC PROC [
node: REF SX.CircuitNode,
layer: SpinifexLayerIndex,
area: INT,
perim: INT,
mode: SX.AdjustmentMode ← relative] = BEGIN
Search for a AreaPerimRec on this layer.
apRec: LIST OF AreaPerimRec ← node.dim;
IF node.superceded # NIL THEN node ← LookupNode[node]; -- added Ch. J. Jan 30, 1985
WHILE apRec # NIL DO
IF apRec.first.layer = layer THEN EXIT;
apRec ← apRec.rest;
REPEAT FINISHED => BEGIN
node.dim ← CONS [AreaPerimRec [layer: layer, area: area, perim: perim], node.dim];
RETURN
END
ENDLOOP;
SELECT mode FROM
relative => BEGIN
apRec.first.area ← apRec.first.area + area;
apRec.first.perim ← apRec.first.perim + perim
END;
absolute => BEGIN
apRec.first.area ← area; apRec.first.perim ← perim
END;
ENDCASE
END; -- AdjustNode
NormalizeCircuit: PUBLIC PROC [cir: REF Circuit] = BEGIN
This is an important step ...
It results in the deallocation of superceded SX.CircuitNodes, and the removal of duplicates, superceded and UnMerged nodes from cir.nodes, and
CompressCircuitNodeList: PROC = BEGIN
mySpecialCN: REF SX.CircuitNode = NEW [SX.CircuitNode];
indirectList: LIST OF REF SX.CircuitNode ~ CONS [mySpecialCN, cir.nodes];
cn: LIST OF REF SX.CircuitNode;
IF cir.nodes = NIL THEN RETURN;
Discard superceded & UnMerged nodes.
mySpecialCN.superceded ← NIL; mySpecialCN.properties ← NIL;
cn ← indirectList;
WHILE cn.rest # NIL DO
node: REF SX.CircuitNode ~ cn.rest.first;
IF (node.superceded # NIL) OR (CDProperties.GetListProp [propList: node.properties, prop: UnMerged] # NIL) THEN cn.rest ← cn.rest.rest
ELSE cn ← cn.rest
ENDLOOP;
Discard duplicated nodes.
IF cir.nodes = NIL THEN ERROR; -- Impossible! We would have returned at start if NIL list, and at least some of the nodes must be non-superceded.
cn ← indirectList;
WHILE cn.rest # NIL DO
IF cn.rest.first.superceded = mySpecialCN THEN cn.rest ← cn.rest.rest
ELSE {cn ← cn.rest; cn.first.superceded ← mySpecialCN}
ENDLOOP;
cn ← cir.nodes ← indirectList.rest;
WHILE cn # NIL DO
cn.first.superceded ← NIL; cn ← cn.rest
ENDLOOP;
END; -- CompressCircuitNodeList
CompressLinkages: PROC = BEGIN
FOR linkages: LIST OF REF NodeLinkage ← cir.linkages, linkages.rest WHILE linkages#NIL DO
FOR attached: LIST OF REF AttachedNode ← linkages.first.nodes, attached.rest WHILE attached#NIL DO
IF attached.first.node#NIL THEN
attached.first.node ← LookupNode[attached.first.node];
ENDLOOP
ENDLOOP
END; -- CompressLinkages
CompressMergeDirectoryEntries: PROC = BEGIN
IF cir.mergeDirectory # NIL THEN BEGIN
dummy: SX.MergeRecList = CONS [[], NIL];
Normally no SX.CircuitNodes in subcells will be unmerged at this point, however this is not true in the case of Normalization following SpinifexOutput. SpinifexOutput introduces extra intermediate nodes, such merge directory entries should be deleted.
CountUnMerged: RefTab.EachPairAction = BEGIN
IF CDProperties.GetListProp [NARROW[key, REF SX.CircuitNode].properties, UnMerged] # NIL THEN oldSize ← oldSize.PRED;
RETURN [FALSE]
END; -- CountUnMerged
CompressMerge: RefTab.EachPairAction = BEGIN
mergeList: SX.MergeRecList;
IF CDProperties.GetListProp[NARROW[key, REF SX.CircuitNode].properties, UnMerged] = NIL THEN BEGIN
dummy.rest ← NARROW [val];
mergeList ← dummy;
WHILE mergeList.rest # NIL DO
mergeList.rest.first.becomes ← LookupNode [mergeList.rest.first.becomes];
IF CDProperties.GetListProp [mergeList.rest.first.becomes.properties, UnMerged] # NIL THEN mergeList.rest ← mergeList.rest.rest
ELSE mergeList ← mergeList.rest
ENDLOOP;
IF dummy.rest # NIL THEN
IF NOT newTab.Insert [key, dummy.rest] THEN ERROR
END;
RETURN [FALSE]
END; -- CompressMerge
Main of CompressMergeDirectoryEntries:
Ensure size is not a power of 2 (seems like a good idea).
oldSize: INT ← RefTab.GetSize [cir.mergeDirectory];
newTab: RefTab.Ref;
[] ← RefTab.Pairs [cir.mergeDirectory, CountUnMerged];
IF oldSize <= 0 THEN {cir.mergeDirectory ← NIL; RETURN};
newTab ← RefTab.Create [((oldSize/3)*4)+1];
[] ← RefTab.Pairs [cir.mergeDirectory, CompressMerge];
cir.mergeDirectory ← newTab;
IF (RefTab.GetSize [newTab] = 0) THEN cir.mergeDirectory ← NIL
END-- if cir.mergeDirectory # NIL
END; -- CompressMergeDirectoryEntries
CompressBoxPaths: PROC [qt: REF SXQuadTree.QuadTree] = BEGIN
FOR boxes: LIST OF REF SXQuadTree.Rectangle ← qt.boxes, boxes.rest WHILE boxes#NIL DO
WITH boxes.first.nodeInformation SELECT FROM
inst: CD.Instance => NULL;
cn: REF SX.CircuitNode => boxes.first.nodeInformation ← LookupNode [cn];
cc: REF Constraint => NULL;
ENDCASE => ERROR;
ENDLOOP;
FOR quad: SXQuadTree.AreaSplit IN SXQuadTree.AreaSplit DO
IF qt.subTrees[quad] # NIL THEN CompressBoxPaths [qt.subTrees[quad]]
ENDLOOP
END; -- CompressBoxPaths
Main of Normalize Circuit
CompressCircuitNodeList [];
CompressLinkages [];
CompressMergeDirectoryEntries [];
FOR layer: SpinifexLayerIndex IN [0..SXAccess.sxTech.numSpinifexLayers) DO
IF (cir.spinifexLayers[layer].geometry # NIL) THEN
CompressBoxPaths [cir.spinifexLayers[layer].geometry]
ENDLOOP
END; -- Normalise Circuit
LookupNode: PUBLIC PROC [node: REF SX.CircuitNode] RETURNS [REF SX.CircuitNode] = BEGIN
Takes the node and returns the most recent version of it.
Side effect: cleans all intermediate version to point to the most recent one.
Mark called this "(partial) Galler-Fisher path compression", had a recursive
solution which was more elegant but slower.
LookupNode: PROC [l: REF SX.CircuitNode] RETURNS [REF SX.CircuitNode] ~ {
--Implements (partial) Galler-Fisher path compression.
RETURN [IF l.superceded#NIL THEN (l.superceded ← LookupNode[l.superceded]) ELSE l]
};
IF node.superceded#NIL THEN {
n1: REF SX.CircuitNode ← node;
--find the actual node
WHILE node.superceded#NIL DO node ← node.superceded ENDLOOP;
--now node is the result
--but as side effect, set all superceded fields to point to the result node
WHILE n1.superceded#NIL DO
n2: REF SX.CircuitNode ← n1.superceded;
n1.superceded ← node;
n1 ← n2;
ENDLOOP;
};
RETURN [node]
END; -- LookupNode
LookupMergeDirectory: PROC [
dir: RefTab.Ref,
cn: REF SX.CircuitNode,
qual: LIST OF CD.Instance]
RETURNS
[merge: SX.MergeRecList, newQual: LIST OF CD.Instance] = BEGIN
found: BOOL;
val: REF ANY;
[found, val] ← RefTab.Fetch [dir, cn];
IF found THEN BEGIN
Search mergeList for qual
FOR mergeList: SX.MergeRecList ← NARROW[val], mergeList.rest WHILE mergeList#NIL DO
Compare mergeList.first.applChain to qual
qApplChain: LIST OF CD.Instance ← qual;
FOR applChain: LIST OF CD.Instance ← mergeList.first.applChain, applChain.rest DO
IF applChain = NIL THEN RETURN [mergeList, qApplChain];
This is a renaming of cn, qual gets to be what's left, and we continue looking for higher intervening renamings.
IF (qApplChain = NIL) OR (qApplChain.first # applChain.first) THEN EXIT;
qApplChain ← qApplChain.rest
ENDLOOP
ENDLOOP
END; -- found
RETURN [NIL, qual]
END; -- LookupMergeDirectory
UnMerged: ATOM = $SXPrivateUnMerged;
UnMerged: Private property Key to flag unmerged nodes for removal during circuit NormalizeCircuit. This key is deleted by CopyNodeProperties, which is called when ever nodes are merged.
FindRootNode: PUBLIC PROC [
circuit:  REF Circuit,
subcircuitNode: REF SX.CircuitNode,
qualifier:  LIST OF CD.Instance,
insertIfNotInCircuit: BOOLFALSE]
RETURNS
[node: REF SX.CircuitNode, rootQualifier: LIST OF CD.Instance] = BEGIN
AddCircuitNodeMerge: PROC [sourceNode: REF SX.CircuitNode, qual: LIST OF CD.Instance] RETURNS [newNode: REF SX.CircuitNode] = BEGIN
found: BOOL;
mergeList: SX.MergeRecList ← NIL;
IF circuit.mergeDirectory = NIL THEN BEGIN
IF insertIfNotInCircuit THEN BEGIN
Make it big, it will get cleaned up in NormalizeCircuit anyway.
circuit.mergeDirectory ← RefTab.Create [521]; -- A prime.
found ← FALSE
END
END
ELSE BEGIN-- circuit.mergeDirectory # NIL
val: REF ANY;
[found, val] ← RefTab.Fetch [circuit.mergeDirectory, sourceNode];
IF found THEN BEGIN
mergeList ← NARROW [val];
Check we don't already know about it.
FOR m: SX.MergeRecList ← mergeList, m.rest WHILE m#NIL DO
q: LIST OF CD.Instance ← qual;
FOR applChain: LIST OF CD.Instance ← m.first.applChain, applChain.rest DO
IF (applChain = NIL) OR (q = NIL) THEN
IF (applChain = NIL) AND (q = NIL) THEN RETURN [newNode ← m.first.becomes]
ELSE EXIT
ELSE IF (applChain.first # q.first) THEN EXIT;
q ← q.rest
ENDLOOP
ENDLOOP
END-- found
END; -- circuit.mergeDirectory # NIL
IF ~insertIfNotInCircuit THEN RETURN [newNode ← NIL];
newNode ← NEW [SX.CircuitNode ← [NIL, NIL, sourceNode.loc, NIL]];
FOR qa: LIST OF CD.Instance ← qual, qa.rest WHILE qa # NIL DO
newNode.loc.xy ← CDBasics.MapPoint [pointInCell: newNode.loc.xy, cellInWorld: qa.first.trans]
ENDLOOP;
CopyNodeProperties [circuit, newNode, sourceNode.properties, qual];
newNode.properties ← PropertyLists.PutProp [newNode.properties, UnMerged, UnMerged];
mergeList ← CONS [[applChain: qual, becomes: newNode], mergeList];
IF RefTab.Store[circuit.mergeDirectory, sourceNode, mergeList] = found THEN ERROR;
AddCircuitNode [circuit, newNode]
END; -- AddCircuitNodeMerge
FindRootNode
IF qualifier=NIL THEN RETURN [subcircuitNode, NIL];
Check each intermediate cell to see if subcircuitNode is renamed, return a SX.CircuitNode based on the uppermost found. Note qualifier always has at least one CD.Instance.
FOR q: LIST OF CD.Instance ← qualifier.rest, q.rest WHILE q#NIL DO
subcircuit: REF Circuit ← SXAccessInternal.GetLogicalCell[q.first.ob].circuit;
IF subcircuit.mergeDirectory # NIL THEN BEGIN
tmp: SX.MergeRecList;
oldQual: LIST OF CD.Instance ← qualifier;
[merge: tmp, newQual: qualifier] ← LookupMergeDirectory [subcircuit.mergeDirectory, subcircuitNode, qualifier];
IF tmp # NIL THEN BEGIN
IF oldQual = NIL THEN ERROR;
IF (qualifier # NIL) AND (qualifier.first.ob # q.first.ob) THEN ERROR;
subcircuitNode ← tmp.first.becomes
END
END
ENDLOOP;
Add to mergeDirectory. For use in cells further up in hierarchy.
IF (node ← AddCircuitNodeMerge[sourceNode: subcircuitNode, qual: qualifier])=NIL THEN
{node ← subcircuitNode; rootQualifier ← qualifier}
ELSE rootQualifier ← NIL
END; -- FindRootNode
AddCircuitNode: PROC [cir: REF Circuit, cn: REF SX.CircuitNode] = INLINE BEGIN
cir.nodes ← CONS[cn, cir.nodes]
END; -- AddCircuitNode
CreateLinkage: PUBLIC PROC [cir: REF Circuit, source: CD.Instance, length, width: CD.Number] RETURNS [REF NodeLinkage] = BEGIN
cir.linkages ← CONS [NEW[NodeLinkage ← [source: source, l: length, w: width]], cir.linkages];
RETURN [cir.linkages.first];
END; -- CreateLinkage
LinkageAttach: PUBLIC PROC [
link: REF NodeLinkage,
attachType: ATOM,
node: REF SX.CircuitNode ← NIL] = BEGIN
link.nodes ← CONS [NEW [AttachedNode ← [attachType, node]], link.nodes]
END; -- LinkageAttach
MakeContextFilter: PROC [] = {
sxContextFilter ← NEW[CD.ContextFilter←ALL[TRUE]];
sxContextFilter[CD.errorLayer] ← FALSE;
sxContextFilter[CD.commentLayer] ← FALSE;
sxContextFilter[CD.backgroundLayer] ← FALSE;
sxContextFilter[CD.shadeLayer] ← FALSE;
sxContextFilter[CD.selectionLayer] ← FALSE;
};
MakeContextFilter[]
END.
Edited on January 4, 1985 6:23:42 pm PST, by Jacobi
NewInstanceRepI does offset position; Spinifex does not want that
Edited on January 22, 1985 4:00:55 pm PST, by Beretta
Unneseted SortBoxes; added comments.
Edited on January 30, 1985 8:25:40 pm PST, by Jacobi
MergeNode; calling LookupNode and equal test introduced
AdjustNode; calling LookupNode introduced
Edited on February 19, 1985 3:58:48 pm PST, by Shand
Fixed serious bug in ansiotropic interest bloats when box is transformed
changes to: AddBox to transform box dimension and interest bloat., TranslateGeometry, SortGeometry
Edited on February 21, 1985 6:19:44 pm PST, by Beretta
changes to: DIRECTORY, PaintErrorRect, TranslateChild, TranslateRect
Edited on March 4, 1985 3:24:49 pm PST, by Shand
Spinifex DRC errors now reported through CDErrors module. Changed role for errorContext field in LogicalCell RECORD.
changes to: DIRECTORY CDErrors, IMPORTS CDErrors, PaintErrorRect calls CDErrors.IncludeMessage, DataForChildren deleted fields which handled deletion of old errors, TranslateGeometry Replaced enumeration of old errors by call to CDErrors.RemoveMessages, TranslateGeometry, IMPORTS, TranslateChild, PaintErrorRect
Edited on March 7, 1985 12:58:15 pm PST, by Shand
changes to: DIRECTORY, CopySignal (local of CopyNodeProperties), s (local of CopySignal, local of CopyNodeProperties) Fixed bug in reading ChipMonk files- allowed case of signal name being ATOM, PaintErrorRect added bloating of error rect by half lambda, EnumerateGeometry Improved search pruning, FlattenTree (local of EnumerateGeometry) Improved search pruning
Edited on March 8, 1985 1:37:29 pm PST, by Shand
Changed name of CircuitConstraint in SX to Constraint
changes to: Constraint, CompressBoxPaths (local of NormalizeCircuit)
Edited on March 9, 1985 10:57:10 pm PST, by Shand
Two things:
1st: Extensions to NormalizeCircuit to remove nodes which were inserted by FindRootNode but never actually merged into other nodes in this cell. This is done using a special property UnMerged which is attached to nodes created for subcell nodes and then deleted during merging by CopyNodeProperties. If node is never merged it still has UnMerged property during NormalizeCircuit, and should be removed from both node list and mergeDirectory.
2nd: When first created mergeDirectory is made large (521 entries). During NormalizeCircuit it is remade with slightly more space than required number of entries. This is to improve performance on large designs.
changes to: DIRECTORY, CopySignal (local of CopyNodeProperties), CopyNodeProperties, NormalizeCircuit, CompressCircuitNodeList (local of NormalizeCircuit), CompressLinkages (local of NormalizeCircuit), CompressMergeDirectoryEntries (local of NormalizeCircuit), CompressMerge (local of CompressMergeDirectoryEntries, local of NormalizeCircuit), LookupNode, UnMerged, FindRootNode, AddCircuitNodeMerge (local of FindRootNode)
Edited on March 10, 1985 7:11:03 pm PST, by Shand
Deleted obsolete field attached from SX.CircuitNode. Added code to keep some point on the node in the SX.CircuitNode RECORD for each node.
Deleted obsolete parameters from LinkageAttach.
More work on MergeDirectory Normalization.
changes to: MergeNode, LinkageAttach, DIRECTORY, AddBox, FindRootNode, AddCircuitNodeMerge (local of FindRootNode), DIRECTORY, CountUnMerged (local of CompressMergeDirectoryEntries, local of NormalizeCircuit), CompressMerge (local of CompressMergeDirectoryEntries, local of NormalizeCircuit), CompressMergeDirectoryEntries (local of NormalizeCircuit), SortGeometry, AddBox
Edited on March 11, 1985 7:11:03 pm PST, by Shand
Deleted obsolete field unsortedBoxes from SX.QuadTreeRoot.
changes to: SortGeometry, AddBox cleaned up so as not to use unsortedBoxes.
Edited on March 13, 1985 2:28:03 pm PST, by Shand
Detection and labelling of repetitions.
changes to: DIRECTORY, IMPORTS, TranslateChild, TranslateGeometry, ApplComp
Edited on May 6, 1985 11:26:55 am PDT, by Beretta
Converted to ChipNDale CD20
Edited on July 8, 1985 4:45:21 pm PDT, by Beretta
If an object has the property export and if the value is $TRUE and the cell is at the root of analysis, then the signal name of the node with this property will be used as a parameter (port).
changes to: CopyNodeProperties: added handling of new property.
Last edited by: gbb July 17, 1985 3:56:55 pm PDT
Replaced ordered symbol table stuff by red-black trees for Cedar 6.0
Last edited by: gbb July 23, 1985 4:37:38 pm PDT
Added storage of length, width for transistors.
changes to: CreateLinkage: new parameters, NodeLinkage: new fields.
gbb January 10, 1986 6:01:50 pm PST
Clean-up while chasing a bug.
gbb May 19, 1986 9:10:23 am PDT
Instead of ignoring only material in the error layer, now all special layers are ignored.
changes to: specialLayers: max value of special layers, TranslateChild changed layer test.
gbb May 20, 1986 3:04:36 pm PDT
Circumvented a temporary bug in the compiler.
changes to: specialLayers: omitted.
gbb June 9, 1986 4:55:58 pm PDT
Added provisions for signal names that are of type REF TEXT instead of Rope.ROPE.
changes to: CopySignal (local of CopyNodeProperties): additional case., DIRECTORY
Christian Jacobi November 14, 1986 7:16:49 pm PST
Analyze non rectilinear geometry