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: gbb June 9, 1986 4:55:58 pm PDT
DIRECTORY
Atom USING [GetPName],
Basics USING [CompareINT, Comparison],
CD USING [backgroundLayer, commentLayer, CreateDrawRef, DrawProc, DrawRectProc, DrawRef, errorLayer, Instance, InstanceList, InstanceRep, Layer, Number, Object, Orientation, outlineLayer, Position, Rect, selectionLayer, shadeLayer],
CDInstances USING [NewInst],
CDBasics USING [Center, NonEmpty, RectAt, SubPoints],
CDOps USING [LayerName],
CDOrient USING [MapPoint, MapRect, original],
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, CDOrient, 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];
Warning: CD.undefLayer should be included in this list. However, its value is zero and the compiler erroneously issues a warning, which prevents MakeDo from binding the package. Hence be alert when the values of these layers change.
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
[inst: Instance, pos: Position, orient: Orientation, pr: REF DrawInformation]
sxThrough: REF LogicalCell = NARROW [pr.devicePrivate];
cir: REF Circuit = sxThrough.circuit;
sx: REF LogicalCell;
IF IsSimpleRect[inst.ob]
THEN
BEGIN
IF inst.ob.layer > specialLayers
THEN
BEGIN
box: CD.Rect = CDOrient.MapRect [
itemInCell: CDBasics.RectAt[pos: [0, 0], size: inst.ob.size],
cellSize: inst.ob.size,
cellInstOrient: orient,
cellInstPos: pos];
node: REF SX.CircuitNode = AddRect [
cir: cir,
lev: inst.ob.layer,
dim: box
! IllegalLayer => {SXAccessInternal.PutError[sxThrough.cellObj, rect, Rope.Cat["Material on layer ", CDOps.LayerName[lev], " may not appear as an isolated rectangle.\n"]];
GOTO BadRect}];
IF node # NIL THEN CopyNodeProperties [cir, node, inst.properties];
EXITS BadRect => NULL
END;
RETURN
END; -- end simple rectangle.
sx ← SXAccessInternal.GetLogicalCell [inst.ob];
IF (sx #
NIL)
AND (sx.analysisState = useCircuit)
THEN
BEGIN
This object is a logical subcircuit.
subcircuit: REF Circuit = sx.circuit;
newAppl:
CD.Instance =
NEW [
CD.InstanceRep ← [
ob: inst.ob,
location: pos,
orientation: orient,
properties: CDProperties.DCopyProps [propList: inst.properties]]];
Preserving properties added by Spreitzer November 23, 1984 8:06:02 pm PST to get cell instance names; why didn't Shand have this here?
numLayers: SpinifexLayerIndex = SXAccess.sxTech.numSpinifexLayers;
FOR i: SpinifexLayerIndex
IN [0..numLayers)
DO
IF subcircuit.spinifexLayers[i].private = NIL THEN LOOP; -- no geom.
IF (cir.subcircuits =
NIL)
OR (cir.subcircuits.first # newAppl)
THEN
BEGIN
It is the 1st non-empty geom-layer.
cir.subcircuits ← CONS [newAppl, cir.subcircuits];
END;
[] ← AddBox [
cir: cir,
inst: newAppl,
pos: pos,
orient: orient,
spinifexLayer: i,
dim: subcircuit.spinifexLayers[i].size,
value: newAppl];
ENDLOOP;
cir.linkageCount.inChildren ← cir.linkageCount.inChildren + subcircuit.linkageCount.inSelf + subcircuit.linkageCount.inChildren;
END -- (sx # NIL) AND (sx.analysisState = useCircuit)
ELSE
BEGIN
-- expand special objects (transistors) and conditional objects
convProc: REF ANY = CDProperties.GetProp [from: inst.ob.class.properties, prop: SXAtoms.spinifex];
IF convProc #
NIL
THEN
object has special layout analysis code.
NARROW [convProc,
REF
SX.ConversionProc]^[inst, pos, orient, cir
! IllegalConstruct => {
SXAccessInternal.PutError [sxThrough.cellObj,
CDOrient.MapRect [itemInCell: rect,
cellSize: inst.ob.size,
cellInstOrient: orient,
cellInstPos: pos],
reason];
CONTINUE}]
ELSE inst.ob.class.drawMe[inst, pos, orient, pr] -- analysis state: notYetDone
END
END; -- TranslateChild
TranslateRect:
CD.DrawRectProc =
BEGIN
PROC [r: DesignRect, l: Layer, pr: DrawRef]
IF NOT CDBasics.NonEmpty[r] THEN RETURN;
IF l #
CD.errorLayer
THEN
BEGIN
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.LayerName [lev], " cannot be analyzed in this context.\n"]];
CONTINUE}]
END
END; -- TranslateRect
——————————
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 ← inst.location];
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
——————————
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 [[]];
fakeAppl: CD.Instance = CDInstances.NewInst [cell.cellObj];
fakeAppl.location ← [0, 0];
dr.drawRect ← TranslateRect;
dr.drawChild ← TranslateChild;
dr.devicePrivate ← cell;
dr.stopFlag ← SXAccess.stopFlag;
cell.cellObj.class.drawMe [fakeAppl, [0, 0], CDOrient.original, dr];
Translation of the geometry.
FOR link:
LIST
OF
REF NodeLinkage ← cir.linkages, link.rest
WHILE link#
NIL
DO
cir.linkageCount.inSelf ← cir.linkageCount.inSelf + 1 -- Number of devices.
ENDLOOP;
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.orientation # sub.first.orientation 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.location, lastApp.instance.location];
lastApp ← currApp;
WHILE (currApp ←
NARROW[RedBlackTree.LookupNextLarger[sTab, lastApp.key]]) #
NIL
DO
IF delta # CDBasics.SubPoints[currApp.instance.location, lastApp.instance.location] 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
END; -- TranslateGeometry
AddRect:
PUBLIC
PROC [
cir:
REF Circuit,
lev:
CD.Layer,
dim:
CD.Rect,
inst:
CD.Instance ←
NIL,
pos:
CD.Position ← [0, 0],
orient:
CD.Orientation ← CDOrient.original,
value:
REF
SX.CircuitNode ←
NIL]
RETURNS [cirNode:
REF
SX.CircuitNode ←
NIL] =
BEGIN
UniformBloat:
PROC [d:
INT]
RETURNS [SXQuadTree.RectDelta] =
INLINE
BEGIN
RETURN [[d,d,d,d]] END; -- UniformBloat
IF SXAccess.sxTech.illegalLayer[lev]
THEN
ERROR IllegalLayer [(IF inst=NIL THEN dim
ELSE CDOrient.MapRect [itemInCell: dim, cellSize: inst.ob.size, cellInstOrient: orient, cellInstPos: pos]), 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, inst: inst, pos: pos, orient: orient,
node: IF cirNode#NIL THEN cirNode ELSE value];
ENDCASE => cn ← AddBox [
cir: cir,
spinifexLayer: map.first.spinifexLayer,
dim: dim, inst: inst, pos: pos, orient: orient,
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,
inst:
CD.Instance ←
NIL,
pos:
CD.Position ← [0, 0],
orient:
CD.Orientation ← CDOrient.original,
interestBloat: SXQuadTree.RectDelta ← [0,0,0,0],
value:
REF
ANY ←
NIL]
RETURNS [cirNode:
REF
SX.CircuitNode ←
NIL] =
BEGIN
In this context `appl = NIL' means that transformation has not to be applied.
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
BEGIN
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];
IF inst = NIL THEN {bloatedMapped ← bloatedDim; mappedDim ← dim}
ELSE
BEGIN
bloatedMapped ← CDOrient.MapRect [itemInCell: bloatedDim, cellSize: inst.ob.size, cellInstOrient: orient, cellInstPos: pos];
mappedDim ← CDOrient.MapRect [itemInCell: dim, cellSize: inst.ob.size, cellInstOrient: orient, cellInstPos: pos]
END; -- appl # NIL
WITH value
SELECT
FROM
cn:
REF
SX.CircuitNode =>
BEGIN
cirNode ← cn; AdjustNode [cirNode, spinifexLayer, A[dim], P[dim]]
END;
ENDCASE =>
IF value =
NIL
THEN
BEGIN
value ← cirNode ← NEW [SX.CircuitNode ←
[dim: LIST[[layer: spinifexLayer, area: A[dim], perim: P[dim]]],
loc: [CDBasics.Center[mappedDim], spinifexLayer]]];
AddCircuitNode [cir, cirNode]
END;
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 -- if dim not empty
ELSE ERROR AddEmptyBox
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:
BOOL ←
FALSE]
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
inst: CD.Instance = qa.first;
newNode.loc.xy ← CDOrient.MapPoint [
pointInCell: newNode.loc.xy,
cellSize: inst.ob.size,
cellInstOrient: inst.orientation,
cellInstPos: inst.location]
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
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