SpinifexCircuitImpl.mesa; Creates a representation of the layout suitable for hierarchical analysis.
Copyright © 1984 by Xerox Corporation. All rights reserved.
Written by Mark Shand, September 12, 1983 11:40 pm
Last Edited by: Shand, September 3, 1984 4:41:07 am PDT
DIRECTORY
CD USING [ObPtr, Rect, DesignPosition, Position, Orientation, ApplicationPtr, ApplicationList, Number, Level, lambda, DrawRef, DrawProc, DrawRectProc, LevelKey, NewNullDeviceDrawRef],
CDDirectory USING [Name],
CDInline USING [RectAt, Inside, Surround, NonEmpty, Extend, SizeOfRect, Intersect, Intersection],
CDOrient USING [MapRect, original],
CDObjectProcs USING [FetchFurther],
CDProperties USING [GetPropFromObject, PutPropOnObject, PutPropOnApplication, GetPropFromApplication],
TerminalIO USING [WriteRope],
CDApplications USING [NewApplicationI],
CDCells USING [IncludeApplication, RemoveApplication],
CDRects USING [CreateBareRect],
Atom USING [PropList, PutPropOnList, GetPropFromList, GetPName],
RefTab USING [Ref, Create, Fetch, Store, Pairs, EachPairAction],
SafeStorage USING [GetSystemZone],
Rope USING [ROPE, Equal, Cat],
SpinifexAtoms USING [ spinifex, spinifexErrorRect, errorClient, SignalName, Rect, SaveRect],
SpinifexCircuit
;
SpinifexCircuitImpl: CEDAR PROGRAM
IMPORTS CD, CDDirectory, CDInline, CDOrient, CDObjectProcs, CDProperties, TerminalIO, Atom, RefTab, SafeStorage, Rope, SpinifexAtoms, CDApplications, CDCells, CDRects
EXPORTS SpinifexCircuit
~ BEGIN
AZ: PUBLIC ZONE ← SafeStorage.GetSystemZone[];
-- TYPES from Interface.
LogicalCell: TYPE ~ SpinifexCircuit.LogicalCell;
Circuit: TYPE ~ SpinifexCircuit.Circuit;
QuadTreeRoot: TYPE ~ SpinifexCircuit.QuadTreeRoot;
QuadTree: TYPE ~ SpinifexCircuit.QuadTree;
AreaSplit: TYPE ~ SpinifexCircuit.AreaSplit;
Rectangle: TYPE ~ SpinifexCircuit.Rectangle;
RectDelta: TYPE ~ SpinifexCircuit.RectDelta;
CircuitNode: TYPE ~ SpinifexCircuit.CircuitNode;
AreaPerimRec: TYPE ~ SpinifexCircuit.AreaPerimRec;
CircuitConstraint: TYPE ~ SpinifexCircuit.CircuitConstraint;
NodeLinkage: TYPE ~ SpinifexCircuit.NodeLinkage;
AttachedNode: TYPE ~ SpinifexCircuit.AttachedNode;
MergeRec: TYPE ~ SpinifexCircuit.MergeRec;
MergeRecList: TYPE ~ SpinifexCircuit.MergeRecList;
SpinifexLayerIndex: TYPE ~ SpinifexCircuit.SpinifexLayerIndex;
TechHandle: TYPE ~ SpinifexCircuit.TechHandle;
MapRec: TYPE ~ SpinifexCircuit.MapRec;
-- Implementation.
ErrorKey:
TYPE ~
RECORD [
ob: CD.ObPtr,
cir: REF Circuit
];
PaintErrorRect:
PUBLIC
PROCEDURE [cell:
REF LogicalCell, errorBox:
CD.Rect, message: Rope.
ROPE] ~ {
-- We clip errorBox that a cells co-ordinate system does not get translated between when we cache geometry information in the child and when we try to use the cached information in the analysis of a antecedent. The problem we are avoiding is that if a cells bounding box changes in CDCells.IncludeApplication the cells internal applications are translated to account for this, and thus become inconsistent with Spinifexes geometry cache.
errorCell: CD.ObPtr;
errorKey: REF ANY;
IF cell.errorContext #
NIL
THEN {
subcircuitKey: REF ErrorKey ← NEW[ ErrorKey ← [cell.cellObj, cell.circuit] ];
subcircuit: REF Circuit ~ cell.circuit;
errorClientList: LIST OF CD.ObPtr ← NARROW[ CDProperties.GetPropFromObject[from~ cell.errorContext, prop~ SpinifexAtoms.errorClient]];
errorKey ← subcircuitKey;
errorCell ← cell.errorContext;
errorBox ← CDOrient.MapRect[ itemInCell~ errorBox, cellSize~ cell.cellObj.size, cellInstOrient~cell.relativeOrient, cellInstPos~cell.relativePos];
message ← message.Cat[" (in sub-component \"", CDDirectory.Name[cell.cellObj], "\")"];
FOR ecl:
LIST
OF
CD.ObPtr ← errorClientList, ecl.rest
WHILE ecl #
NIL
DO
IF ecl.first = cell.cellObj THEN EXIT;
REPEAT
FINISHED => {
errorClientList ← CONS[cell.cellObj, errorClientList];
CDProperties.PutPropOnObject[onto~ cell.errorContext, prop~ SpinifexAtoms.errorClient, val~ errorClientList];
}
ENDLOOP;
}
ELSE {
errorCell ← cell.cellObj;
errorKey ← SpinifexAtoms.spinifexErrorRect
};
errorBox ← CDInline.Intersection[ CDInline.Extend[errorBox, (CD.lambda+1)/2], CDInline.RectAt[ pos~ [0,0], size~ errorCell.size]];
IF CDInline.NonEmpty[errorBox]
THEN {
appl: CD.ApplicationPtr ~ CDApplications.NewApplicationI[ ob~ CDRects.CreateBareRect[ CDInline.SizeOfRect[ errorBox], cell.circuit.technologyHandle.errorLevel], location~ [errorBox.x1, errorBox.y1], orientation~ CDOrient.original];
CDProperties.PutPropOnApplication[onto~ appl, prop~ SpinifexAtoms.SignalName, val~ message];
CDProperties.PutPropOnApplication[onto~ appl, prop~ SpinifexAtoms.spinifexErrorRect, val~ errorKey];
[] ← CDCells.IncludeApplication[ design~cell.design, cell~errorCell, aptr~appl];
};
cell.errorCount ← cell.errorCount.SUCC;
TerminalIO.WriteRope["|"]
};
IllegalConstruct: PUBLIC ERROR [rect: CD.Rect, reason: Rope.ROPE] ~ CODE;
IllegalLevel: PUBLIC ERROR [rect: CD.Rect, lev: CD.Level] ~ CODE;
ContainsIllegal: SIGNAL [rect: CD.Rect, reason: Rope.ROPE] ~ CODE;
DataForChildren:
TYPE ~
RECORD [
cir: REF Circuit,
oldErrors: LIST OF CD.ApplicationPtr
];
TranslateChild:
CD.DrawProc
--
[aptr: ApplicationPtr, pos: DesignPosition, orient: Orientation, pr: REF DrawInformation] -- ~ {
IF aptr.ob.p.objectType = SpinifexAtoms.Rect
OR aptr.ob.p.objectType = SpinifexAtoms.SaveRect
THEN {
-- This object is a simple rectangle.
data: REF DataForChildren ~ NARROW[pr.devicePrivate];
IF aptr.ob.level = data.cir.technologyHandle.errorLevel
THEN {
key: REF ANY ~ CDProperties.GetPropFromApplication[from~ aptr, prop~SpinifexAtoms.spinifexErrorRect];
IF key #
NIL
THEN
WITH key
SELECT
FROM
key:
REF ErrorKey => {
IF key.cir # CDProperties.GetPropFromObject[ from~key.ob, prop~SpinifexAtoms.spinifex]
THEN
data.oldErrors ← AZ.CONS[ aptr, data.oldErrors];
};
a:
ATOM => {
IF a # SpinifexAtoms.spinifexErrorRect THEN ERROR;
data.oldErrors ← AZ.CONS[ aptr, data.oldErrors]
};
ENDCASE => ERROR;
RETURN
};
{
box: CD.Rect ~ CDOrient.MapRect[ itemInCell~ CDInline.RectAt[pos~ [0,0], size~ aptr.ob.size], cellSize~ aptr.ob.size, cellInstOrient~ orient, cellInstPos~ pos];
node:
REF CircuitNode ~ AddRect[ cir~ data.cir, lev~ aptr.ob.level, dim~ box ! IllegalLevel => {
SIGNAL ContainsIllegal [rect, Rope.Cat["
Material on level ", Atom.GetPName[
CD.LevelKey[
lev]], "
may not appear as an isolated rectangle"]];
GOTO BadRect }
];
IF node #
NIL
THEN
CopyNodeProperties[ data.cir, node, aptr.properties];
EXITS BadRect => NULL
};
RETURN
};
WITH CDProperties.GetPropFromObject[ from~aptr.ob, prop~SpinifexAtoms.spinifex]
SELECT FROM
subcircuit:
REF Circuit => {
-- This object is a logical subcircuit.
newAppl: CD.ApplicationPtr ~ CDApplications.NewApplicationI[ ob~ aptr.ob, location~ pos, orientation~ orient];
data: REF DataForChildren ~ NARROW[pr.devicePrivate];
cir: REF Circuit ~ data.cir;
numLayers: SpinifexLayerIndex ~ data.cir.technologyHandle.numSpinifexLayers;
FOR i: SpinifexLayerIndex
IN [0..numLayers)
DO
IF subcircuit.spinifexLayers[i].geometry = NIL THEN LOOP;
IF cir.subcircuits =
NIL
OR cir.subcircuits.first # newAppl
THEN
-- It is the 1st non-empty geom-layer.
cir.subcircuits ← AZ.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;
};
ENDCASE => {
convProc: REF ANY ~ CDObjectProcs.FetchFurther[ p~aptr.ob.p, key~SpinifexAtoms.spinifex];
IF convProc #
NIL
THEN {
-- This object has special layout analysis code.
data: REF DataForChildren ~ NARROW[pr.devicePrivate];
NARROW[ convProc, REF SpinifexCircuit.ConversionProc]^[ aptr, pos, orient, data.cir ! IllegalConstruct => { SIGNAL ContainsIllegal [CDOrient.MapRect[ itemInCell~rect, cellSize~aptr.ob.size, cellInstOrient~orient, cellInstPos~pos], reason]; CONTINUE } ]
}
ELSE {
-- Use DrawProc to Process geometry in the mystery object.
aptr.ob.p.drawMe[aptr, pos, orient, pr]
}
}
};
TranslateRect:
CD.DrawRectProc
-- [r: DesignRect, l: Level, pr: DrawRef] -- ~ {
data: REF DataForChildren ~ NARROW[pr.devicePrivate];
IF ~CDInline.NonEmpty[r] THEN RETURN;
IF l # data.cir.technologyHandle.errorLevel
THEN
[] ← AddRect[ cir~data.cir, lev~l, dim~r ! IllegalLevel => { SIGNAL ContainsIllegal [rect, Rope.Cat["Rectangle on level ", Atom.GetPName[CD.LevelKey[lev]], " cannot be analyzed in this context"] ]; CONTINUE } ];
};
TranslateGeometry:
PUBLIC
PROCEDURE [cell:
REF LogicalCell] ~ {
cir: REF Circuit ~ cell.circuit;
dataRef: REF DataForChildren ← NEW[DataForChildren];
dr: CD.DrawRef ~ CD.NewNullDeviceDrawRef[NIL];
fakeAppl: CD.ApplicationPtr ~ CDApplications.NewApplicationI[ ob~ cell.cellObj, location~ [0,0], orientation~ CDOrient.original];
cellSize: CD.DesignPosition ← cell.cellObj.size;
dr.drawRect ← TranslateRect;
dr.saveRect ← TranslateRect;
dr.drawChild ← TranslateChild;
dr.devicePrivate ← dataRef;
dataRef.cir ← cir;
dataRef.oldErrors ← NIL;
cell.cellObj.p.drawMe[fakeAppl, [0,0], CDOrient.original, dr ! ContainsIllegal => { PaintErrorRect[ cell~ cell, errorBox~ rect, message~ reason ]; RESUME } ];
FOR link:
LIST
OF
REF NodeLinkage ← cir.linkages, link.rest
WHILE link #
NIL
DO
cir.linkageCount.inSelf ← cir.linkageCount.inSelf.SUCC
ENDLOOP;
FOR applList:
LIST OF CD.ApplicationPtr ← dataRef.oldErrors, applList.rest
WHILE applList #
NIL
DO
IF CDCells.RemoveApplication[ design~ cell.design, cell~ cell.cellObj, aptr~ applList.first].removed = NIL THEN ERROR;
ENDLOOP;
IF cellSize # cell.cellObj.size
THEN {
TerminalIO.WriteRope[" Removal of old Spinifex Errors from cell caused cell's boundary to change, Spinifex was unable to continue. Please try to run Spinifex again."];
ERROR ABORTED
};
-- Now we must sort it.
FOR layer: SpinifexLayerIndex
IN [0..cir.technologyHandle.numSpinifexLayers)
DO
SortBoxes:
PROCEDURE [cir:
REF Circuit, layer: SpinifexLayerIndex] ~ {
Quadrant: TYPE ~ {ne,nw,sw,se};
SubDivision: TYPE ~ {fitsNorth, fitsSouth, fitsEast, fitsWest, noFit };
boxList: LIST OF REF Rectangle;
boundary: CD.Rect;
qtRoot: REF QuadTree;
CanSubDivide:
PROCEDURE [qNE, qSW: Quadrant]
RETURNS [SubDivision] ~ {
-- This is trickier than it seems.
-- Unpleasant cases arise when degenerate boxes lie on the quadrant dividing axes. Accordingly quadNE & quadSW have slightly different semantics. quadNE is made to favour the south-west, and quadSW to favour the north-east. The choiceMatrix is encoding to interpret apparent contradictions such as quadNE in nw and quadSW in ne as indicating a degenrate box lying on the vertical splitting axis. Such a box is contained by both the ne & nw subtree.
choiceMatrix:
ARRAY Quadrant
OF
ARRAY Quadrant
OF SubDivision ~
[ ne~[ ne~fitsNorth, nw~fitsNorth, sw~noFit, se~fitsEast],
nw~[ ne~fitsNorth, nw~fitsNorth, sw~fitsWest, se~fitsWest],
sw~[ ne~fitsSouth, nw~fitsSouth, sw~fitsSouth, se~fitsSouth],
se~[ ne~fitsSouth, nw~fitsSouth, sw~fitsSouth, se~fitsSouth]
];
RETURN [choiceMatrix[qNE][qSW]]
};
SplittingSizeTooSmall:
PROCEDURE [r:
CD.Rect]
RETURNS [
BOOLEAN] ~ {
-- A heuristic to prevent ridiculous splitting.
splitLimit: CD.Number ~ 10*CD.lambda;
RETURN [(r.x2 - r.x1 < splitLimit) OR (r.y2 - r.y1 < splitLimit)];
};
-- Body of SortBoxes ———————————
cir.spinifexLayers[layer].geometry ← AZ.NEW[QuadTree ← [boxes~NIL, subTrees~ALL[NIL], midX~(cir.spinifexLayers[layer].size.x2+cir.spinifexLayers[layer].size.x1)/2, midY~(cir.spinifexLayers[layer].size.y2+cir.spinifexLayers[layer].size.y1)/2]];
boxList ← cir.spinifexLayers[layer].unsortedBoxes;
cir.spinifexLayers[layer].unsortedBoxes ← NIL;
boundary ← cir.spinifexLayers[layer].size;
qtRoot ← cir.spinifexLayers[layer].geometry;
WHILE boxList #
NIL
DO
branchBoundary: CD.Rect ← boundary;
qt: REF QuadTree ← qtRoot;
quadNE, quadSW: Quadrant;
DO
-- classify top right corner
quadNE ← IF qt.midX < boxList.first.interestBound.x2
THEN IF qt.midY < boxList.first.interestBound.y2
THEN ne
ELSE se
ELSE IF qt.midY < boxList.first.interestBound.y2
THEN nw
ELSE sw;
-- classify bottom left corner (not quite the same as quadNE! NOTE <=, NOT < )
quadSW ← IF qt.midX <= boxList.first.interestBound.x1
THEN IF qt.midY <= boxList.first.interestBound.y1
THEN ne
ELSE se
ELSE IF qt.midY <= boxList.first.interestBound.y1
THEN nw
ELSE sw;
IF SplittingSizeTooSmall[branchBoundary] THEN EXIT
ELSE {
st: AreaSplit;
SELECT CanSubDivide[quadNE, quadSW]
FROM
noFit => EXIT;
fitsNorth => { branchBoundary.y1 ← qt.midY; st ← north};
fitsSouth => { branchBoundary.y2 ← qt.midY; st ← south};
fitsEast => { branchBoundary.x1 ← qt.midX; st ← east};
fitsWest => { branchBoundary.x2 ← qt.midX; st ← west};
ENDCASE => ERROR;
IF qt.subTrees[st] =
NIL
THEN
-- The first box in a new split does not recurse; a hueristic to avoid irrational splitting. Some boxes will not be as deep as they could be, but it should not matter greatly.
IF qt.boxes #
NIL
AND qt.boxes.rest #
NIL
THEN {
qt.subTrees[st] ← AZ.NEW[QuadTree ← [boxes~NIL, subTrees~ALL[NIL], midX~(branchBoundary.x2+branchBoundary.x1)/2, midY~(branchBoundary.y2+branchBoundary.y1)/2] ];
qt ← qt.subTrees[st];
EXIT
}
qt ← qt.subTrees[st];
}
ENDLOOP;
{
temp: LIST OF REF Rectangle ← boxList.rest;
boxList.rest ← qt.boxes;
qt.boxes ← boxList;
boxList ← temp
};
ENDLOOP;
};
IF cir.spinifexLayers[layer].unsortedBoxes = NIL THEN LOOP;
SortBoxes[cir, layer];
ENDLOOP;
};
EnumerateGeometry:
PUBLIC
PROCEDURE [circuit:
REF Circuit, layer: SpinifexLayerIndex, clipRect:
CD.Rect, PerRect: SpinifexCircuit.PerRectProc, data:
REF
ANY] ~ {
FlattenTree:
PROCEDURE [qt:
REF QuadTree, bBox:
CD.Rect] ~ {
IF qt = NIL THEN RETURN;
FOR boxes:
LIST
OF
REF Rectangle ← qt.boxes, boxes.rest
WHILE boxes #
NIL
DO
IF CDInline.Intersect[clipRect, boxes.first.interestBound] THEN PerRect[boxes.first, data]
ENDLOOP;
FOR quad: AreaSplit
IN AreaSplit
DO
subBox: CD.Rect ← bBox;
SELECT quad
FROM
north => IF clipRect.y2 <= qt.midY THEN LOOP ELSE subBox.y1 ← qt.midY;
south => IF clipRect.y1 >= qt.midY THEN LOOP ELSE subBox.y2 ← qt.midY;
east => IF clipRect.x2 <= qt.midX THEN LOOP ELSE subBox.x1 ← qt.midX;
west => IF clipRect.x1 >= qt.midX THEN LOOP ELSE subBox.x2 ← qt.midX;
ENDCASE;
FlattenTree[qt.subTrees[quad], subBox]
ENDLOOP;
};
FlattenTree[circuit.spinifexLayers[layer].geometry, circuit.spinifexLayers[layer].size];
};
AddEmptyBox: ERROR ~ CODE;
AddRect:
PUBLIC
PROCEDURE [ cir:
REF SpinifexCircuit.Circuit, lev:
CD.Level, dim:
CD.Rect, appl:
CD.ApplicationPtr ←
NIL, pos:
CD.DesignPosition ← [0,0], orient:
CD.Orientation ← CDOrient.original, value:
REF SpinifexCircuit.CircuitNode ←
NIL]
RETURNS [cirNode:
REF SpinifexCircuit.CircuitNode ←
NIL] ~ {
UniformBloat:
PROCEDURE [d:
INT]
RETURNS [RectDelta] ~
INLINE {
RETURN [[d,d,d,d]]
};
IF cir.technologyHandle.illegalLevel[lev]
THEN
ERROR IllegalLevel[(IF appl = NIL THEN dim ELSE CDOrient.MapRect[ itemInCell~dim, cellSize~appl.ob.size, cellInstOrient~orient, cellInstPos~pos]), lev];
IF CDInline.NonEmpty[dim] THEN -- Silently ignore empty boxes
FOR map:
LIST
OF MapRec ← cir.technologyHandle.cdLayerMapping[lev], map.rest
WHILE map #
NIL
DO
cn: REF SpinifexCircuit.CircuitNode;
WITH map.first.value
SELECT
FROM
mappingFunc: REF SpinifexCircuit.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;
};
AddBox:
PUBLIC
PROCEDURE [cir:
REF Circuit, spinifexLayer: SpinifexLayerIndex, dim:
CD.Rect, appl:
CD.ApplicationPtr ←
NIL, pos:
CD.DesignPosition ← [0,0], orient:
CD.Orientation ← CDOrient.original, interestBloat: RectDelta ← [0,0,0,0], value:
REF
ANY ←
NIL]
RETURNS [cirNode:
REF CircuitNode ←
NIL] ~ {
A: PROCEDURE [r: CD.Rect] RETURNS [area: INT] ~ INLINE { area ← (r.x2-r.x1)*(r.y2-r.y1) };
P: PROCEDURE [r: CD.Rect] RETURNS [perim: INT] ~ INLINE { perim ← ((r.x2-r.x1)+(r.y2-r.y1))*2 };
IF value =
NIL
THEN {
value ← cirNode ← AZ.NEW[ CircuitNode ← [ dim ~ LIST[ [layer~spinifexLayer, area~A[dim], perim~P[dim]]]] ];
AddCircuitNode[ cir, cirNode]
}
ELSE
WITH value
SELECT
FROM
cn:
REF CircuitNode => {
cirNode ← cn;
AdjustNode[ cirNode, spinifexLayer, A[dim], P[dim]]
};
ENDCASE;
IF ~CDInline.NonEmpty[dim] THEN ERROR AddEmptyBox
ELSE {
mappedDim: CD.Rect ~ (IF appl = NIL THEN dim ELSE CDOrient.MapRect[ itemInCell~dim, cellSize~appl.ob.size, cellInstOrient~orient, cellInstPos~pos]);
bloatedDim: CD.Rect ~ [x1~mappedDim.x1-interestBloat.dx1, y1~mappedDim.y1-interestBloat.dy1, x2~mappedDim.x2+interestBloat.dx2, y2~mappedDim.y2+interestBloat.dy2];
newRect: REF Rectangle ~ AZ.NEW[Rectangle ← [ interestBound~bloatedDim, dimDecr~interestBloat, nodeInformation~value]];
cir.spinifexLayers[spinifexLayer].unsortedBoxes ← AZ.CONS[ newRect, cir.spinifexLayers[spinifexLayer].unsortedBoxes];
IF ~ CDInline.Inside[bloatedDim, cir.spinifexLayers[spinifexLayer].size]
THEN
cir.spinifexLayers[spinifexLayer].size ← CDInline.Surround[bloatedDim, cir.spinifexLayers[spinifexLayer].size]
}
};
MergeNode:
PUBLIC
PROCEDURE [ circuit:
REF Circuit, to, from:
REF CircuitNode] ~ {
-- 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;
to.attached ← to.attached OR from.attached;
from.superceded ← to;
};
SignalName: TYPE ~ SpinifexCircuit.SignalName;
CopyNodeProperties:
PROCEDURE [ circuit:
REF Circuit, node:
REF CircuitNode, properties: Atom.PropList, qual:
LIST
OF
CD.ApplicationPtr ←
NIL] ~ {
CopySignal:
PROCEDURE [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.
IF sig = NIL THEN RETURN [NIL];
WITH sig
SELECT
FROM
r: Rope.ROPE => RETURN [ NEW[SignalName ← [depth~ depth, name~ r]]];
s:
REF SignalName => {
copyHead, copyTail: REF SignalName;
copyHead ← NEW[SignalName ← [depth~ s.depth + depth, name~ s.name]];
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;
};
MergeAliases:
PROCEDURE [ to, from:
REF SignalName] ~ {
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;
};
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[properties.GetPropFromList[ SpinifexAtoms.SignalName], depth];
toSignal ← NARROW[node.properties.GetPropFromList[ SpinifexAtoms.SignalName]];
IF toSignal #
NIL
AND fromSignal #
NIL
THEN {
IF toSignal.depth > fromSignal.depth
THEN {
node.properties ← node.properties.PutPropOnList[ SpinifexAtoms.SignalName, fromSignal];
MergeAliases[fromSignal, toSignal]
}
ELSE
MergeAliases[toSignal, fromSignal]
}
ELSE
IF fromSignal #
NIL
THEN
node.properties ← node.properties.PutPropOnList[ SpinifexAtoms.SignalName, fromSignal]
};
Copy Technology Dependent Properties
IF circuit.technologyHandle.CombineNodeProperties #
NIL
AND properties #
NIL
THEN
node.properties ← circuit.technologyHandle.CombineNodeProperties[circuit, node.properties, properties, qual];
};
AdjustNode:
PUBLIC
PROCEDURE [node:
REF CircuitNode, layer: SpinifexLayerIndex, area:
INT, perim:
INT, mode: SpinifexCircuit.AdjustmentMode ← relative] ~ {
-- Search for a AreaPerimRec on this layer.
apRec: LIST OF AreaPerimRec ← node.dim;
WHILE apRec #
NIL
DO
IF apRec.first.layer = layer THEN EXIT;
apRec ← apRec.rest;
REPEAT
FINISHED => {
node.dim ← AZ.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
};
NormalizeCircuit:
PUBLIC
PROCEDURE [cir:
REF Circuit] ~ {
-- This is an important step ...
-- It results in the deallocation of superceded CircuitNodes, and the removal of dupliactes and superceded nodes from cir.nodes.
CompressCircuitNodeList:
PROCEDURE ~ {
mySpecialCN: REF CircuitNode~AZ.NEW[CircuitNode];
cn: LIST OF REF CircuitNode;
IF cir.nodes = NIL THEN RETURN;
-- Discard superceded nodes.
cn ← cir.nodes;
WHILE cn.rest #
NIL
DO
IF cn.rest.first.superceded # NIL THEN cn.rest ← cn.rest.rest
ELSE cn ← cn.rest
ENDLOOP;
IF cir.nodes.first.superceded # NIL THEN cir.nodes ← cir.nodes.rest;
-- Discard duplicated nodes.
IF cir.nodes = NIL THEN ERROR; -- Impossible!
cn ← cir.nodes;
WHILE cn.rest #
NIL
DO
IF cn.rest.first.superceded = mySpecialCN THEN cn.rest ← cn.rest.rest
ELSE {
cn.first.superceded ← mySpecialCN;
cn ← cn.rest
}
ENDLOOP;
cn ← cir.nodes;
WHILE cn.rest #
NIL
DO
cn.first.superceded ← NIL;
cn ← cn.rest
ENDLOOP;
};
CompressLinkages:
PROCEDURE ~ {
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
};
CompressMergeDirectoryEntries:
PROCEDURE ~ {
CompressMerge: RefTab.EachPairAction ~ {
FOR mergeList: MergeRecList ←
NARROW[val], mergeList.rest
WHILE mergeList #
NIL
DO
mergeList.first.becomes ← LookupNode[mergeList.first.becomes];
ENDLOOP;
RETURN [FALSE]
};
IF cir.mergeDirectory # NIL THEN [] ← RefTab.Pairs[cir.mergeDirectory, CompressMerge];
};
CompressBoxPaths:
PROCEDURE [qt:
REF QuadTree] ~ {
FOR boxes:
LIST
OF
REF Rectangle ← qt.boxes, boxes.rest
WHILE boxes #
NIL
DO
WITH boxes.first.nodeInformation
SELECT
FROM
appl: CD.ApplicationPtr => NULL;
cn: REF CircuitNode => boxes.first.nodeInformation ← LookupNode[cn];
cc: REF CircuitConstraint => NULL;
ENDCASE => ERROR;
ENDLOOP;
FOR quad: AreaSplit
IN AreaSplit
DO
IF qt.subTrees[quad] # NIL THEN CompressBoxPaths[qt.subTrees[quad]]
ENDLOOP;
};
CompressCircuitNodeList[];
CompressLinkages[];
CompressMergeDirectoryEntries[];
FOR layer: SpinifexLayerIndex
IN [0..cir.technologyHandle.numSpinifexLayers)
DO
IF cir.spinifexLayers[layer].geometry # NIL THEN CompressBoxPaths[cir.spinifexLayers[layer].geometry]
ENDLOOP;
};
LookupNode:
PUBLIC
PROCEDURE [l:
REF CircuitNode]
RETURNS [
REF CircuitNode] ~ {
-- Implements (partial) Galler-Fisher path compression.
RETURN [IF l.superceded # NIL THEN (l.superceded ← LookupNode[l.superceded]) ELSE l]
};
LookupMergeDirectory:
PROCEDURE [ dir: RefTab.Ref, cn:
REF CircuitNode, qual:
LIST
OF
CD.ApplicationPtr]
RETURNS [merge: MergeRecList, newQual:
LIST
OF
CD.ApplicationPtr] ~ {
found: BOOLEAN;
val: REF ANY;
[found, val] ← dir.Fetch[cn];
IF found
THEN {
-- Search mergeList for qual
FOR mergeList: 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]
};
FindRootNode:
PUBLIC
PROCEDURE [ circuit:
REF Circuit, subcircuitNode:
REF CircuitNode, qualifier:
LIST
OF
CD.ApplicationPtr, insertIfNotInCircuit:
BOOLEAN ←
FALSE]
RETURNS [node:
REF CircuitNode, rootQualifier:
LIST
OF
CD.ApplicationPtr] ~ {
AddCircuitNodeMerge:
PROCEDURE [ sourceNode:
REF CircuitNode, qual:
LIST
OF
CD.ApplicationPtr]
RETURNS [newNode:
REF CircuitNode] ~ {
found: BOOLEAN;
mergeList: MergeRecList ← NIL;
IF circuit.mergeDirectory =
NIL
THEN {
IF insertIfNotInCircuit
THEN {
circuit.mergeDirectory ← RefTab.Create[];
found ← FALSE
}
}
ELSE {
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: 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 ← AZ.NEW[CircuitNode ← sourceNode^];
Copy dim list.
IF newNode.dim #
NIL
THEN {
newNode.dim ← AZ.CONS[newNode.dim.first, newNode.dim.rest];
FOR tailDim:
LIST
OF AreaPerimRec ← newNode.dim, tailDim.rest
WHILE tailDim.rest #
NIL
DO
tailDim.rest ← AZ.CONS[tailDim.rest.first, tailDim.rest.rest];
ENDLOOP
};
newNode.properties ← NIL;
CopyNodeProperties[ circuit, newNode, sourceNode.properties, qual];
mergeList ← AZ.CONS[ [applChain~qual, becomes~newNode], mergeList];
IF RefTab.Store[circuit.mergeDirectory, sourceNode, mergeList] = found THEN ERROR;
AddCircuitNode[ circuit, newNode]
};
Main Body of FindRootNode
IF qualifier = NIL THEN RETURN [subcircuitNode, NIL];
Check each intermediate cell to see if subcircuitNode is renamed, return a 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 ← NARROW[ CDProperties.GetPropFromObject[ from~q.first.ob, prop~SpinifexAtoms.spinifex]];
IF subcircuit.mergeDirectory #
NIL
THEN {
tmp: MergeRecList;
[merge~tmp, newQual~qualifier] ← LookupMergeDirectory[ subcircuit.mergeDirectory, subcircuitNode, qualifier];
IF tmp # NIL THEN 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
}
};
AddCircuitNode:
PROCEDURE [cir:
REF Circuit, cn:
REF CircuitNode] ~
INLINE {
cir.nodes ← AZ.CONS[ cn, cir.nodes]
};
CreateLinkage:
PUBLIC
PROCEDURE [ cir:
REF Circuit, source:
CD.ApplicationPtr]
RETURNS [
REF NodeLinkage] ~ {
cir.linkages ← AZ.CONS[ AZ.NEW[ NodeLinkage ← [source]], cir.linkages];
RETURN [cir.linkages.first];
};
LinkageAttach:
PUBLIC
PROCEDURE [link:
REF NodeLinkage, attachType:
ATOM, areaAdj:
INTEGER ← 0, perimAdj:
INTEGER ← 0, node:
REF CircuitNode ←
NIL] ~ {
IF node # NIL THEN node.attached ← TRUE;
link.nodes ← AZ.CONS[ AZ.NEW[ AttachedNode ← [ attachType, areaAdj, perimAdj, node]], link.nodes];
};
END.