SXImpl.mesa
Creates a representation of the layout suitable for hierarchical analysis.
Copyright © 1984, 1985 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, January 4, 1985 6:23:06 pm PST
Last Edited by: Jacobi, April 8, 1985 5:07:49 pm PST
Last Edited by: Beretta, July 8, 1985 4:47:54 pm PDT
DIRECTORY
Atom USING [GetPName, GetPropFromList, PropList, PutPropOnList, RemPropFromList],
Basics,
CD,
CDApplications USING [NewApplicationI],
CDBasics,
CDObjectProcs USING [FetchFurther],
CDOps USING [LayerName],
CDOrient USING [MapPoint, MapRect, original],
CDProperties USING [GetPropFromApplication, PutPropOnApplication],
Convert USING [RopeFromInt],
OrderedSymbolTableRef,
RefTab USING [Create, EachPairAction, Fetch, GetSize, Insert, Pairs, Ref, Store],
Rope USING [Cat, Equal, ROPE],
SX,
SXAccess,
SXAccessInternal,
SXAtoms USING [export, InstanceName, Rect, SaveRect, SignalName, spinifex],
SXQuadTree USING [AreaSplit, Store, QuadTree, QuadTreeRoot, Rectangle, RectDelta];
TerminalIO USING [WriteRope];
SXImpl:
CEDAR
PROGRAM
IMPORTS Atom, Basics, CD, CDApplications, CDBasics, CDObjectProcs, CDOps, CDOrient, CDProperties, Convert, OrderedSymbolTableRef, RefTab, Rope, SXAccess, SXAccessInternal, SXAtoms, SXQuadTree --, TerminalIO
EXPORTS SX =
BEGIN
-- TYPES from Interface.
LogicalCell: TYPE = SX.LogicalCell;
Circuit: TYPE = SX.Circuit;
AreaPerimRec: TYPE = SX.AreaPerimRec;
Constraint: TYPE = SX.Constraint;
NodeLinkage: TYPE = SX.NodeLinkage;
AttachedNode: TYPE = SX.AttachedNode;
MergeRec: TYPE = SX.MergeRec;
SpinifexLayerIndex: TYPE = SX.SpinifexLayerIndex;
MapRec: TYPE = SX.MapRec;
SignalName: TYPE = SX.SignalName;
-- Implementation.
IllegalConstruct: PUBLIC ERROR [rect: CD.Rect, reason: Rope.ROPE] = CODE;
IllegalLayer: PUBLIC ERROR [rect: CD.Rect, lev: CD.Layer] = CODE;
repetitionInstanceNamePrefix: Rope.ROPE ← "";
repetitionInstanceNamePostfix: Rope.ROPE ← "";
IsSimpleRect:
PROC [ob:
CD.ObPtr]
RETURNS [
BOOL] =
INLINE BEGIN
RETURN [ob.p.objectType = SXAtoms.Rect OR ob.p.objectType = SXAtoms.SaveRect]
END;
TranslateChild:
CD.DrawProc =
-- PROC [aptr: ApplicationPtr, pos: DesignPosition, orient: Orientation, pr: REF DrawInformation]
BEGIN
sxThrough: REF SX.LogicalCell = NARROW[pr.devicePrivate];
cir: REF SX.Circuit = sxThrough.circuit;
sx: REF SX.LogicalCell;
IF IsSimpleRect[aptr.ob]
THEN {
IF aptr.ob.layer #
CD.highLightError
THEN {
box:
CD.Rect = CDOrient.MapRect[
itemInCell: CDBasics.RectAt[pos: [0, 0], size: aptr.ob.size],
cellSize: aptr.ob.size,
cellInstOrient: orient,
cellInstPos: pos
];
node:
REF SX.CircuitNode = AddRect[
cir: cir,
lev: aptr.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, aptr.properties];
EXITS BadRect => NULL
};
RETURN
}; -- end simple rectangle.
sx ← SXAccessInternal.GetSXData[aptr.ob];
IF sx#
NIL
AND sx.analysisState=useCircuit
THEN {
-- This object is a logical subcircuit.
subcircuit: REF Circuit = sx.circuit;
newAppl:
CD.ApplicationPtr =
NEW[
CD.Application ← [
ob: aptr.ob,
location: pos,
orientation: orient,
-- selected: TRASH,
properties: CopyProperties[aptr.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 {
It is the 1st non-empty geom-layer.
cir.subcircuits ← CONS[newAppl, cir.subcircuits];
};
[] ← AddBox [
cir: cir,
appl: 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;
}
ELSE {
-- expand special objects (transistors) and conditional objects
convProc: REF ANY = CDObjectProcs.FetchFurther[p: aptr.ob.p, key: SXAtoms.spinifex];
IF convProc#
NIL
THEN
-- object has special layout analysis code.
NARROW[convProc,
REF
SX.ConversionProc]^[aptr, pos, orient, cir
! IllegalConstruct => {
SXAccessInternal.PutError [sxThrough.cellObj,
CDOrient.MapRect [itemInCell: rect,
cellSize: aptr.ob.size,
cellInstOrient: orient,
cellInstPos: pos],
reason];
CONTINUE
}
]
ELSE aptr.ob.p.drawMe[aptr, pos, orient, pr] -- analysis state: notYetDone
}
END; -- TranslateChild
CopyProperties:
PROC [from:
CD.Properties]
RETURNS [to:
CD.Properties] =
BEGIN
to ← NIL;
FOR from ← from, from.rest
WHILE from#
NIL
DO
to ← CONS[from.first, to];
ENDLOOP;
END;
TranslateRect:
CD.DrawRectProc =
-- PROC [r: DesignRect, l: Layer, pr: DrawRef] --
BEGIN
IF ~CDBasics.NonEmpty[r] THEN RETURN;
IF l #
CD.highLightError
THEN {
sxc: REF SX.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; -- TranslateRect
TranslateGeometry:
PUBLIC
PROC [cell:
REF LogicalCell] =
--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.
BEGIN
cir: REF Circuit = cell.circuit;
dr: CD.DrawRef = CD.CreateDrawRef[NIL];
fakeAppl: CD.ApplicationPtr = CDApplications.NewApplicationI[cell.cellObj];
fakeAppl.location ← [0, 0];
dr.drawRect ← dr.saveRect ← TranslateRect;
dr.drawChild ← TranslateChild;
dr.devicePrivate ← cell;
dr.stopFlag ← SXAccess.stopFlag;
cell.cellObj.p.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 {
-- There are at least three subcircuits.
FOR sub:
CD.ApplicationList ← 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 => {
-- They all have the same orientation, and are all are of the same type.
ENABLE OrderedSymbolTableRef.DuplicateKey => GOTO EqualAppls;
sTab: OrderedSymbolTableRef.Table = OrderedSymbolTableRef.CreateTable[ApplComp];
lastApp: CD.ApplicationPtr;
currApp: CD.ApplicationPtr;
delta: CD.Position;
FOR sub:
CD.ApplicationList ← cir.subcircuits, sub.rest
WHILE sub#
NIL
DO
sTab.Insert[sub.first];
-- Raises DuplicateKey if appl with same location already added.
ENDLOOP;
lastApp ← NARROW[sTab.LookupSmallest[]];
currApp ← NARROW[sTab.LookupNextLarger[lastApp]];
delta ← CDBasics.SubPoints[currApp.location, lastApp.location];
lastApp ← currApp;
WHILE (currApp ←
NARROW[sTab.LookupNextLarger[lastApp]]) #
NIL
DO
IF delta # CDBasics.SubPoints[currApp.location, lastApp.location] THEN EXIT;
lastApp ← currApp;
REPEAT
FINISHED => {
-- They are sorted. Hence they are logically a repetition.
index: INT ← 1;
FOR a:
CD.ApplicationPtr ←
NARROW[sTab.LookupSmallest[]],
NARROW[sTab.LookupNextLarger[a]]
WHILE a #
NIL
DO
IF CDProperties.GetPropFromApplication[from: a, prop: SXAtoms.InstanceName]=
NIL
THEN {
--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.PutPropOnApplication[a, SXAtoms.InstanceName, instanceName];
};
index ← index+1
ENDLOOP
};
ENDLOOP;
EXITS EqualAppls => NULL
}
ENDLOOP;
}
END; -- TranslateGeometry
ApplComp:
PROC [r1, r2:
REF
ANY]
RETURNS [c: OrderedSymbolTableRef.Comparison] =
BEGIN
a1: CD.ApplicationPtr = NARROW[r1];
a2: CD.ApplicationPtr = NARROW[r2];
c ← Basics.CompareINT[a1.location.x, a2.location.x];
IF c=equal
THEN
c ← Basics.CompareINT[a1.location.y, a2.location.y];
END;
AddRect:
PUBLIC
PROC [
cir: REF SX.Circuit,
lev: CD.Layer,
dim: CD.Rect,
appl: CD.ApplicationPtr ← NIL,
pos: CD.DesignPosition ← [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 {
RETURN [[d,d,d,d]]
};
IF SXAccess.sxTech.illegalLayer[lev]
THEN {
ERROR IllegalLayer[
(IF appl=NIL THEN dim
ELSE CDOrient.MapRect[
itemInCell: dim,
cellSize: appl.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,
appl: appl,
pos: pos,
orient: orient,
node: IF cirNode#NIL THEN cirNode ELSE value
];
ENDCASE => cn ← AddBox[
cir: cir,
spinifexLayer: map.first.spinifexLayer,
dim: dim,
appl: appl,
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,
appl:
CD.ApplicationPtr ←
NIL,
pos:
CD.DesignPosition ← [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 {
area ← (r.x2-r.x1)*(r.y2-r.y1)
};
P:
PROC [r:
CD.Rect]
RETURNS [perim:
INT] =
INLINE {
perim ← ((r.x2-r.x1)+(r.y2-r.y1))*2
};
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 appl = NIL THEN {bloatedMapped ← bloatedDim; mappedDim ← dim}
ELSE
BEGIN
bloatedMapped ← CDOrient.MapRect [itemInCell: bloatedDim, cellSize: appl.ob.size, cellInstOrient: orient, cellInstPos: pos];
mappedDim ← CDOrient.MapRect [itemInCell: dim, cellSize: appl.ob.size, cellInstOrient: orient, cellInstPos: pos]
END; -- appl # NIL
WITH value
SELECT
FROM
cn:
REF
SX.CircuitNode => {
cirNode ← cn;
AdjustNode [cirNode, spinifexLayer, A[dim], P[dim]]
};
ENDCASE =>
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]
};
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;
CopyNodeProperties:
PROC [
circuit:
REF Circuit,
node:
REF
SX.CircuitNode,
properties: Atom.PropList,
qual:
LIST
OF
CD.ApplicationPtr ←
NIL] =
BEGIN
CopySignal:
PROC [sig:
REF
ANY, depth:
INTEGER]
RETURNS [
REF SignalName] =
-- Creates a SignalName RECORD with appropriate depth from a ChipNDale Signal name (ROPE) or an existing SignalName RECORD.
BEGIN
IF sig=NIL THEN RETURN [NIL];
WITH sig
SELECT
FROM
r: Rope.ROPE => RETURN [NEW[SignalName ← [depth: depth, name: r]]];
a: ATOM => RETURN [NEW[SignalName ← [depth: depth, name: Atom.GetPName[a]]]];
s:
REF SignalName => {
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];
};
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 {
IF from.depth < existingAlias.depth
THEN
existingAlias.depth ← from.depth;
from ← from.alias;
EXIT
}
REPEAT
FINISHED => {
-- Insert in list.
tmp: REF SignalName = from;
from ← from.alias;
tmp.alias ← to.alias;
to.alias ← tmp
}
ENDLOOP;
ENDLOOP;
END; -- MergeAliases
fromSigProp: REF ANY ~ Atom.GetPropFromList [properties, SXAtoms.SignalName];
exportProp: REF ANY = Atom.GetPropFromList [properties, SXAtoms.export];
toSigProp: REF ANY ~ Atom.GetPropFromList [node.properties, SXAtoms.SignalName];
--Copy Technology Dependent Properties
IF SXAccess.sxTech.combineNodeProperties#
NIL
AND properties#
NIL
THEN
node.properties ←
SXAccess.sxTech.combineNodeProperties[circuit, node.properties, properties, qual];
--Copy SignalName property
{
fromSignal: REF SignalName;
toSignal: REF SignalName;
depth: INTEGER ← 0;
FOR q:
LIST
OF
CD.ApplicationPtr ← 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 {
IF toSignal.depth > fromSignal.depth
THEN {
node.properties ← node.properties.PutPropOnList[SXAtoms.SignalName, fromSignal];
MergeAliases[fromSignal, toSignal]
}
ELSE
MergeAliases[toSignal, fromSignal]
}
ELSE
IF fromSignal#
NIL
THEN
node.properties ← node.properties.PutPropOnList[SXAtoms.SignalName, fromSignal]
};
--Delete UnMerged property.
node.properties ← node.properties.RemPropFromList[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 => {
node.dim ← CONS[AreaPerimRec[layer: layer, area: area, perim: perim], node.dim];
RETURN
}
ENDLOOP;
SELECT mode
FROM
relative => {
apRec.first.area ← apRec.first.area + area;
apRec.first.perim ← apRec.first.perim + perim;
};
absolute => {
apRec.first.area ← area;
apRec.first.perim ← perim;
};
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 node.properties.GetPropFromList[UnMerged] #
NIL
THEN
cn.rest ← cn.rest.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;
CompressMergeDirectoryEntries:
PROC =
BEGIN
IF cir.mergeDirectory#
NIL
THEN {
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
NARROW[key,
REF
SX.CircuitNode].properties.GetPropFromList[UnMerged] #
NIL
THEN
oldSize ← oldSize.PRED;
RETURN [FALSE]
END;
CompressMerge: RefTab.EachPairAction =
BEGIN
mergeList: SX.MergeRecList;
IF
NARROW[key,
REF
SX.CircuitNode].properties.GetPropFromList[UnMerged] =
NIL
THEN {
dummy.rest ← NARROW[val];
mergeList ← dummy;
WHILE mergeList.rest #
NIL
DO
mergeList.rest.first.becomes ← LookupNode[mergeList.rest.first.becomes];
IF mergeList.rest.first.becomes.properties.GetPropFromList[UnMerged]#
NIL
THEN
mergeList.rest ← mergeList.rest.rest
ELSE
mergeList ← mergeList.rest
ENDLOOP;
IF dummy.rest#
NIL
THEN
IF ~newTab.Insert[key, dummy.rest] THEN ERROR
};
RETURN [FALSE]
END; -- CompressMerge
-- 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 {
TerminalIO.WriteRope[" It shrank to zero!\n"];
cir.mergeDirectory ← NIL
}
ELSE IF RefTab.GetSize[newTab] < oldSize/2 THEN {
TerminalIO.WriteRope[" mergeDirectory shrank a lot?\n"];
newTab ← RefTab.Create[ ((RefTab.GetSize[newTab]/3)*4)+1];
[] ← RefTab.Pairs[cir.mergeDirectory, CompressMerge];
cir.mergeDirectory ← newTab;
}
}
}
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
appl: CD.ApplicationPtr => 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;
--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] =
--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]
};
BEGIN
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
CheckNodeInCircuit:
PROC [node:
REF SX.CircuitNode, circuit:
REF Circuit] =
BEGIN
FOR nl:
LIST
OF
REF SX.CircuitNode ← circuit.nodes, nl.rest
WHILE nl#
NIL
DO
IF nl.first = node THEN EXIT;
REPEAT FINISHED => TerminalIO.WriteRope [
"\n\n*** Spinifex has lost a node. Extracted output might be wrong.\n"]
REPEAT FINISHED => NULL -- TerminalIO.WriteRope ["~"]
ENDLOOP;
END;
LookupMergeDirectory:
PROC [
dir: RefTab.Ref,
cn:
REF
SX.CircuitNode,
qual:
LIST
OF
CD.ApplicationPtr]
RETURNS [merge: SX.MergeRecList, newQual: LIST OF CD.ApplicationPtr] =
BEGIN
found: BOOL;
val: REF ANY;
[found, val] ← dir.Fetch[cn];
IF found
THEN {
-- 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.ApplicationPtr ← qual;
FOR applChain:
LIST
OF
CD.ApplicationPtr ← mergeList.first.applChain, applChain.rest
DO
IF applChain=
NIL
THEN {
-- This is a renaming of cn, qual gets to be what's left, and we continue looking for higher intervening renamings.
RETURN [mergeList, qApplChain];
};
IF qApplChain=NIL OR qApplChain.first#applChain.first THEN EXIT;
qApplChain ← qApplChain.rest
ENDLOOP;
ENDLOOP;
};
RETURN [NIL, qual]
END; -- LookupMergeDirectory
tiptoe: BOOL ← TRUE;
UnMerged:
ATOM = $SpinifexPrivateUnMerged;
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.ApplicationPtr,
insertIfNotInCircuit:
BOOL ←
FALSE]
RETURNS [node: REF SX.CircuitNode, rootQualifier: LIST OF CD.ApplicationPtr] =
BEGIN
AddCircuitNodeMerge:
PROC [sourceNode:
REF SX.CircuitNode, qual:
LIST
OF
CD.ApplicationPtr]
RETURNS [newNode:
REF SX.CircuitNode] =
BEGIN
found: BOOL;
mergeList: SX.MergeRecList ← NIL;
TerminalIO.WriteRope ["!"];
IF circuit.mergeDirectory=
NIL
THEN {
IF insertIfNotInCircuit
THEN {
-- Make it big, it will get cleaned up in NormalizeCircuit anyway.
circuit.mergeDirectory ← RefTab.Create[521]; -- A prime.
found ← FALSE
}
}
ELSE {
-- circuit.mergeDirectory # NIL
val: REF ANY;
[found, val] ← circuit.mergeDirectory.Fetch[sourceNode];
IF found
THEN {
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.ApplicationPtr ← qual;
FOR applChain:
LIST
OF
CD.ApplicationPtr ← 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
}
};
IF ~insertIfNotInCircuit THEN RETURN [newNode ← NIL];
newNode ← NEW[SX.CircuitNode ← [NIL, NIL, sourceNode.loc, NIL]];
FOR qa:
LIST
OF
CD.ApplicationPtr ← qual, qa.rest
WHILE qa #
NIL
DO
appl: CD.ApplicationPtr = qa.first;
newNode.loc.xy ← CDOrient.MapPoint[
pointInCell: newNode.loc.xy,
cellSize: appl.ob.size,
cellInstOrient: appl.orientation,
cellInstPos: appl.location
]
ENDLOOP;
CopyNodeProperties[circuit, newNode, sourceNode.properties, qual];
newNode.properties ← newNode.properties.PutPropOnList[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.ApplicationPtr.
FOR q:
LIST
OF
CD.ApplicationPtr ← qualifier.rest, q.rest
WHILE q#
NIL
DO
subcircuit: REF Circuit ← SXAccessInternal.GetSXData[q.first.ob].circuit;
IF subcircuit.mergeDirectory#
NIL
THEN {
tmp: SX.MergeRecList;
oldQual: LIST OF CD.ApplicationPtr ← qualifier;
IF tiptoe
AND oldQual#
NIL
THEN {
bottomCircuit: REF Circuit ← SXAccessInternal.GetSXData[oldQual.first.ob].circuit;
CheckNodeInCircuit [subcircuitNode, bottomCircuit];
};
[merge: tmp, newQual: qualifier] ← LookupMergeDirectory[subcircuit.mergeDirectory, subcircuitNode, qualifier];
IF tmp#
NIL
THEN {
IF oldQual=NIL THEN ERROR;
IF qualifier#NIL AND qualifier.first.ob#q.first.ob THEN ERROR;
IF tiptoe
THEN {
CheckNodeInCircuit[tmp.first.becomes, subcircuit];
};
subcircuitNode ← tmp.first.becomes;
}
}
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
}
END; -- FindRootNode
AddCircuitNode:
PROC [cir:
REF Circuit, cn:
REF SX.CircuitNode] =
INLINE {
cir.nodes ← CONS[cn, cir.nodes]
};
CreateLinkage:
PUBLIC
PROC [cir:
REF Circuit, source:
CD.ApplicationPtr]
RETURNS [
REF NodeLinkage] = {
cir.linkages ← CONS[NEW[NodeLinkage ← [source]], cir.linkages];
RETURN [cir.linkages.first];
};
LinkageAttach:
PUBLIC
PROC [
link:
REF NodeLinkage,
attachType:
ATOM,
node:
REF SX.CircuitNode ←
NIL] = {
link.nodes ← CONS[NEW[AttachedNode ← [attachType, node]], link.nodes];
};
END.
Edited on January 4, 1985 6:23:42 pm PST, by Jacobi
NewApplicationI 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.