SXLayersImpl.mesa
Copyright © 1984, 1985 by Xerox Corporation. All rights reserved.
Creates a representation of the layout suitable for hierarchical analysis. Spinifex produces a hierarchical circuit representation, and list of regions containing design rule violations.
Written by Shand, September 12, 1983 11:40 pm
Last Edited by Mark Shand, March 13, 1985 2:50:54 am PST
Last Edited by: Jacobi, April 8, 1985 4:39:46 pm PST
Last edited by: Christian Jacobi, November 14, 1986 7:05:28 pm PST
Bowers, September 6, 1985 11:50:22 am PDT
Last edited by: gbb October 29, 1986 6:20:25 pm PST
DIRECTORY
CD USING [Error, ErrorCode, Instance, Number, Object, Orientation, Position, Rect, Transformation],
CDBasics,
CStitching USING [Area, DumpCache, IsEmpty, ChangeRect, Rect, EEdge, EN, EnumerateArea, ResetTesselation, ChangeEnumerateArea, ListArea, NE, NewTesselation, NEdge, RectProc, TileProc, Region, SEdge, SW, Tesselation, Tile, FindTile, WEdge, WS],
PrincOpsUtils USING [],
SX USING [AdjustNode, Circuit, CircuitNode, Constraint, ConstraintResolution, FindRootNode, GeometricRule, LogicalCell, LookupNode, MergeNode, nodeIndex, NormalizeCircuit, spaceIndex, SpinifexLayerIndex],
SXAccess USING [design, stopFlag, sxTech],
SXAccessInternal USING [GetLogicalCell, PutError],
SXLayers USING [],
SXQuadTree USING [AreaSplit, Create, Dimension, Enumerate, PerRectProc, QuadTree, QuadTreeRoot, Rectangle, Rectangles],
TerminalIO USING [PutRope];
SXLayersImpl:
CEDAR
PROGRAM
IMPORTS CD, CStitching, CDBasics, SX, SXAccess, SXAccessInternal, SXQuadTree, TerminalIO
EXPORTS SXLayers = BEGIN
Global Types and Variables
Tesselation: TYPE ~ CStitching.Tesselation;
Tile: TYPE ~ CStitching.Tile;
nothing: REF INT ~ NEW [INT];
Constraint: TYPE = SX.Constraint;
Rectangle: TYPE = SXQuadTree.Rectangle;
Node: TYPE = SX.CircuitNode;
ConflictWorlds:
TYPE =
ARRAY
SX.SpinifexLayerIndex
OF Tesselation;
The conflict worlds are used to find the regions where interactions occour.
GeometryWorlds:
TYPE =
ARRAY
SX.SpinifexLayerIndex
OF Tesselation;
The geometry worlds contain the flattened regions where conflicts occour.
ConstraintQueue: TYPE = ARRAY SX.SpinifexLayerIndex OF LIST OF REF CStitching.Region ← ALL[NIL];
The following two data structures are global for maintenance purposes.
conflictWorlds: ConflictWorlds;
The conflict worlds are used to find the regions where interactions occour.
geometryWorlds: GeometryWorlds;
The geometry worlds contain the flattened regions where conflicts occour.
Maintenance aids
saveTesselations: BOOL ← FALSE;
freeTesselations: BOOL ← FALSE;
Conflict Resolution
UseLevelOrderHeuristic:
PROC [clipRect:
CD.Rect, old, new: SXQuadTree.Rectangles]
RETURNS [
BOOLEAN] =
BEGIN
Only bother with Level-order Conflict Resolution when the contended region is not too narrow.
ThinLimit: CD.Number = SXAccess.design.technology.lambda * 10;
RETURN [(clipRect.x2 - clipRect.x1 > ThinLimit) AND (clipRect.y2 - clipRect.y1 > ThinLimit)]
END; -- UseLevelOrderHeuristic
ComputeConflicts:
PROC [
qt:
REF SXQuadTree.QuadTree,
conflictWorld: Tesselation,
layer:
SX.SpinifexLayerIndex,
cir:
REF
SX.Circuit] =
BEGIN
The quad-trees are enumerated and the conflict world is constructed. Each rectangle has an area of interest depending on the material. Constraints do not overlap: they are ordered into the technology dependent part; the larger prevails. Every constraint is represented by a number which is an index in a boolean array to infere whether it is there.
descentDepth: INT ← 1;
4 things are put into the conflictWorld they are:
REF Rectangle: occupied by a node (possibly within a subcell as determined by val.nodeInformation's TYPE, either REF circuitNode or CD.Instance)
REF Constraint: occupied by a constraint or some resolution of constraints such that the resolution at each step was one of the two contending constraints vying for occupancy of the region.
SXQuadTree.Rectangles: Bid for occupancy by a subcell to some unspecified depth.
ATOM ~ $Conflict being the result of an irresolvable conflict for occupancy and flagging a region as requiring instantiation and analysis.
OccupyByNode: CStitching.RectProc =
BEGIN
[plane: REF Tesselation, rect: Rect, new: REF ← NIL]
WITH oldValue
SELECT
FROM
a:
ATOM =>
IF a # $Conflict
THEN
CD.Error [ec: other, explanation: "Tesselation screwed up (alien tile)"];
If there already is a conflict nothing needs to be done.
r:
REF Rectangle =>
IF data # r
THEN
Different rectangle Ò conflict.
CStitching.ChangeRect [conflictWorld, rect, $Conflict];
s: SXQuadTree.Rectangles =>
Old contents is subcell which needs to be flattened out: insert node and flatten subcell.
IF data # s.first
THEN
BEGIN
CStitching.ChangeRect [conflictWorld, rect, data];
Flatten [rect, s]
END
ELSE CD.Error [ec: other, explanation: "Quad-tree screwed up (subcell found twice)"];
c:
REF Constraint =>
IF
NOT SameConstraints [ResolveConstraints [c, data, SXAccess.sxTech.constraintResolutions[layer]], data]
THEN
CStitching.ChangeRect [conflictWorld, rect, $Conflict];
Else no change.
ENDCASE =>
IF oldValue =
NIL
THEN
Initially the plane is empty, hence tile = NIL. Insert a new tile.
CStitching.ChangeRect [conflictWorld, rect, data]
ELSE CD.Error [ec: other, explanation: "Tesselation screwed up (alien tile)"]
END; -- OccupyByNode
OccupyByConstr: CStitching.RectProc =
BEGIN
[plane: REF Tesselation, rect: Rect, new: REF ← NIL]
WITH oldValue
SELECT
FROM
a:
ATOM =>
IF a # $Conflict
THEN
CD.Error [ec: other, explanation: "Tesselation screwed up (alien tile)"];
If there already is a conflict nothing needs to be done.
r:
REF Rectangle =>
IF
NOT SameConstraints [ResolveConstraints[
NARROW[data], r, SXAccess.sxTech.constraintResolutions[layer]], r]
THEN
CStitching.ChangeRect [conflictWorld, rect, $Conflict];
s: SXQuadTree.Rectangles =>
BEGIN
conflictWorld.ChangeRect[rect, data];
Flatten [rect, s]
END;
c:
REF Constraint =>
BEGIN
Resolve constraints against each other.
resolution: REF ANY = ResolveConstraints [c, data, SXAccess.sxTech.constraintResolutions [layer]];
IF (NOT SameConstraints[resolution, c] AND NOT SameConstraints[resolution, data]) THEN CStitching.ChangeRect [conflictWorld, rect, $Conflict]
ELSE
IF
NOT SameConstraints[resolution, c]
THEN
CStitching.ChangeRect [conflictWorld, rect, resolution];
END;
ENDCASE =>
Initially the plane is empty, hence tile=NIL.
IF oldValue =
NIL
THEN
Initially the plane is empty, hence tile = NIL. Insert a new tile.
CStitching.ChangeRect [conflictWorld, rect, data]
ELSE CD.Error [ec: other, explanation: "Tesselation screwed up (alien tile)"]
END; -- OccupyByConstr
OccupyByAppl: CStitching.RectProc =
BEGIN
[plane: REF Tesselation, rect: Rect, new: REF ← NIL]
If oldValue is a subcell, then rect is the intersection of the subcell oldValue and the cell data. Otherwise it is a conflict, a a rectangle or a constraint.
WITH oldValue
SELECT
FROM
a:
ATOM =>
IF a # $Conflict
THEN
CD.Error [ec: other, explanation: "Tesselation screwed up (alien tile)"];
If there already is a conflict nothing needs to be done.
r:
REF Rectangle =>
BEGIN
IF
NARROW[data, SXQuadTree.Rectangles].first = r
THEN
CD.Error [ec: other, explanation: "Rectangle has already been processed"];
Flatten [rect, NARROW[data]]
END;
s: SXQuadTree.Rectangles =>
IF data # s
THEN
IF UseLevelOrderHeuristic [rect, s,
NARROW[data]]
THEN
DescendOneLevel [rect, s, NARROW[data]]
ELSE
BEGIN
Clear present occupant out of region.
CStitching.ChangeRect [conflictWorld, rect, NIL];
Add flattened rectangles from each cell to region.
Flatten [rect, s];
Flatten [rect, NARROW[data]]
END;
If subcell of same subcell: already done.
c: REF Constraint => Flatten [rect, NARROW[data]];
ENDCASE =>
IF oldValue =
NIL
THEN
Initially the plane is empty, hence tile = NIL. Insert a new tile.
CStitching.ChangeRect [conflictWorld, rect, data]
ELSE CD.Error [ec: other, explanation: "Tesselation screwed up (alien tile)"]
END; -- OccupyByAppl
Flatten:
PROC [clipRect:
CD.Rect, applRef: SXQuadTree.Rectangles] =
BEGIN
inst: CD.Instance = NARROW [applRef.first.nodeInformation];
FlattenCell:
PROC [inst:
CD.Instance, trans:
CD.Transformation] =
BEGIN
--as in CD.DrawProc inst.trans is ignored but trans is used
MapRect:
PROC [inCellRect:
CD.Rect]
RETURNS [inWorldRect:
CD.Rect] =
INLINE
BEGIN
inWorldRect ← CDBasics.Intersection [CDBasics.MapRect [itemInCell: inCellRect, cellInWorld: trans], clipRect]
END; -- MapRect
FlattenTree:
PROC [qt:
REF SXQuadTree.QuadTree] =
BEGIN
(local of FlattenCell, local of Flatten)
FOR boxes: SXQuadTree.Rectangles ← qt.boxes, boxes.rest
WHILE boxes#
NIL
DO
WITH boxes.first.nodeInformation
SELECT
FROM
node:
REF Node => {
r: CD.Rect = MapRect [boxes.first.interestBound];
IF CDBasics.NonEmpty[r]
THEN
CStitching.ChangeEnumerateArea [conflictWorld, r, OccupyByNode, applRef.first, nothing]
};
constr:
REF Constraint => {
r: CD.Rect = MapRect[boxes.first.interestBound];
IF CDBasics.NonEmpty[r]
THEN
CStitching.ChangeEnumerateArea [conflictWorld, r, OccupyByConstr, constr, nothing]
};
subAppl:
CD.Instance =>
IF CDBasics.Intersect [boxes.first.interestBound, mappedClip]
THEN {
FlattenCell [subAppl, CDBasics.ComposeTransform[itemInCell: subAppl.trans, cellInWorld: trans].itemInWorld]
};
ENDCASE => ERROR; -- Quad tree srewed up
ENDLOOP;
Use quad-tree to filter what has to be flattened.
IF SXAccess.stopFlag^ THEN ERROR ABORTED;
IF mappedClip.y2>qt.midY
AND qt.subTrees[north]#
NIL
THEN
FlattenTree[qt.subTrees[north]];
IF mappedClip.y1<qt.midY
AND qt.subTrees[south]#
NIL
THEN
FlattenTree[qt.subTrees[south]];
IF mappedClip.x2>qt.midX
AND qt.subTrees[east]#
NIL
THEN
FlattenTree[qt.subTrees[east]];
IF mappedClip.x1<qt.midX
AND qt.subTrees[west]#
NIL
THEN
FlattenTree[qt.subTrees[west]];
END; -- FlattenTree
cellQt: REF SXQuadTree.QuadTree;
mappedClip: CD.Rect = CDBasics.DeMapRect [itemInWorld: clipRect, cellInWorld: trans];
cellQt ← SXAccessInternal.GetLogicalCell[inst.ob].circuit.spinifexLayers[layer].geometry;
IF cellQt # NIL THEN FlattenTree [cellQt]
END; -- FlattenCell
FlattenCell [inst, inst.trans]
END; -- Flatten
DescendOneLevel:
PROC [clipRect:
CD.Rect, old, new: SXQuadTree.Rectangles] =
BEGIN
Situation: two cells overlap. Goal: Try not to flatten unnecessary cells (i.e. which do not have material or constraints in the overlap or interacting material.
levelCount: INT;
BidByNode: CStitching.RectProc =
BEGIN
[plane: REF Tesselation, rect: Rect, oldValue: REF, data: REF]
WITH oldValue
SELECT
FROM
a:
ATOM =>
IF a # $Conflict
THEN
CD.Error [ec: other, explanation: "Tesselation screwed up (alien tile)"];
r:
REF Rectangle =>
IF data # r
THEN
CD.Error [ec: other, explanation: "Tesselation screwed up"];
s: SXQuadTree.Rectangles => CStitching.ChangeRect [conflictWorld, rect, data];
c: REF Constraint => CStitching.ChangeRect [conflictWorld, rect, data];
ENDCASE => ERROR
END; -- BidByNode
BidByConstr: CStitching.RectProc =
BEGIN
[plane: REF Tesselation, rect: Rect, oldValue: REF, data: REF]
WITH oldValue
SELECT
FROM
a:
ATOM =>
IF a # $Conflict
THEN
CD.Error [ec: other, explanation: "Tesselation screwed up (alien tile)"];
r:
REF Rectangle =>
IF new.first # r
THEN
CD.Error [ec: other, explanation: "Tesselation screwed up"];
s: SXQuadTree.Rectangles =>
IF s # new THEN CStitching.ChangeRect [conflictWorld, rect, data];
c:
REF Constraint =>
BEGIN
resolution: REF ANY = ResolveConstraints [c, data, SXAccess.sxTech.constraintResolutions [layer]];
IF
NOT SameConstraints [resolution, c]
THEN
CStitching.ChangeRect [conflictWorld, rect, resolution];
END;
ENDCASE => ERROR;
END; -- BidByConstr
BidByAppl: CStitching.RectProc =
BEGIN
[plane: REF Tesselation, rect: Rect, oldValue: REF, data: REF]
WITH oldValue
SELECT
FROM
a:
ATOM =>
IF a # $Conflict
THEN
CD.Error [ec: other, explanation: "Tesselation screwed up (alien tile)"];
r:
REF Rectangle =>
IF
NARROW[data, SXQuadTree.Rectangles].first # r
THEN
CD.Error [ec: other, explanation: "Tesselation screwed up"];
s: SXQuadTree.Rectangles =>
IF data # s THEN CStitching.ChangeRect [conflictWorld, rect, data];
c: REF Constraint => CStitching.ChangeRect [conflictWorld, rect, data];
ENDCASE => ERROR;
END; -- BidByAppl
DescendCell:
PROC [inst:
CD.Instance, trans:
CD.Transformation] =
BEGIN
--as in CD.DrawProc inst.trans is ignored but trans is used
MapRect:
PROC [inCellRect:
CD.Rect]
RETURNS [inWorldRect:
CD.Rect] =
INLINE
BEGIN
(local of DescendCell, local of DescendOneLevel)
inWorldRect ← CDBasics.Intersection [
CDBasics.MapRect [itemInCell: inCellRect, cellInWorld: trans],
clipRect]
END; -- MapRect
DescendTree:
PROC [qt:
REF SXQuadTree.QuadTree] =
BEGIN
(local of DescendCell, local of DescendOneLevel)
IF qt=NIL THEN RETURN;
FOR boxes: SXQuadTree.Rectangles ← qt.boxes, boxes.rest
WHILE boxes#
NIL
DO
WITH boxes.first.nodeInformation
SELECT
FROM
node:
REF Node => {
r: CD.Rect = MapRect [boxes.first.interestBound];
IF CDBasics.NonEmpty[r]
THEN
CStitching.ChangeEnumerateArea [conflictWorld, r, BidByNode, new.first, nothing]
};
constr:
REF Constraint => {
r: CD.Rect = MapRect [boxes.first.interestBound];
IF CDBasics.NonEmpty[r]
THEN
CStitching.ChangeEnumerateArea [conflictWorld, r, BidByConstr, constr, nothing]
};
subAppl:
CD.Instance =>
IF CDBasics.Intersect [boxes.first.interestBound, mappedClip]
THEN {
IF levelCount > 0
THEN
DescendCell [
subAppl,
CDBasics.ComposeTransform[itemInCell: subAppl.trans, cellInWorld: trans].itemInWorld
]
ELSE {
r: CD.Rect = MapRect [boxes.first.interestBound];
IF CDBasics.NonEmpty[r]
THEN
CStitching.ChangeEnumerateArea [conflictWorld, r, BidByAppl, new, nothing]
}
};
ENDCASE => ERROR;
ENDLOOP;
IF mappedClip.y2 > qt.midY
AND qt.subTrees[north] #
NIL
THEN
DescendTree [qt.subTrees[north]];
IF mappedClip.y1<qt.midY
AND qt.subTrees[south]#
NIL
THEN
DescendTree [qt.subTrees[south]];
IF mappedClip.x2>qt.midX
AND qt.subTrees[east]#
NIL
THEN
DescendTree [qt.subTrees[east]];
IF mappedClip.x1<qt.midX
AND qt.subTrees[west]#
NIL
THEN
DescendTree [qt.subTrees[west]];
END; -- DescendTree
main of DescendCell
cellQt: REF SXQuadTree.QuadTree;
mappedClip: CD.Rect = CDBasics.DeMapRect [itemInWorld: clipRect,
cellInWorld: trans];
cellQt ← SXAccessInternal.GetLogicalCell[inst.ob].circuit.spinifexLayers[layer].geometry;
levelCount ← levelCount-1;
DescendTree [cellQt];
levelCount ← levelCount+1;
END; -- DescendCell
inst: CD.Instance = NARROW [new.first.nodeInformation];
descentDepth ← descentDepth + 1;
levelCount ← descentDepth/2; -- Descend until levelCount = 0
DescendCell [inst, inst.trans];
CStitching.ChangeEnumerateArea [conflictWorld, clipRect, OccupyByAppl, old, nothing];
descentDepth ← descentDepth -1
END; -- DescendOneLevel
Main of ComputeConflicts
The big boxes are inserted first, then the smaller stuff. Having radix sorted the boxes into sub-trees increases locality of reference to the corner stitched data structure.
IF qt = NIL THEN RETURN;
FOR boxes: SXQuadTree.Rectangles ← qt.boxes, boxes.rest
WHILE boxes#
NIL
DO
WITH boxes.first.nodeInformation
SELECT
FROM
node:
REF Node =>
CStitching.ChangeEnumerateArea is for local changes. For each rectangle in the first parameter, the function which is the second parameter is called the third parameter as the function's parameter:
CStitching.ChangeEnumerateArea [conflictWorld, boxes.first.interestBound, OccupyByNode, boxes.first, nothing];
constr:
REF Constraint =>
CStitching.ChangeEnumerateArea [conflictWorld, boxes.first.interestBound, OccupyByConstr, constr, nothing];
inst:
CD.Instance =>
CStitching.ChangeEnumerateArea [conflictWorld, boxes.first.interestBound, OccupyByAppl, boxes, nothing];
Only the first box is of interest. A list is passed because the type is used as a discriminant to decide:
1. if list then may or may not have actual geometry and needs further discrimination.
2. if ref then cell is known to have geometry there.
ENDCASE => ERROR;
ENDLOOP;
FOR quad: SXQuadTree.AreaSplit
IN SXQuadTree.AreaSplit
DO
ComputeConflicts [qt.subTrees[quad], conflictWorld, layer, cir]
Recursive because of quad-trees.
ENDLOOP;
IF descentDepth#1 THEN ERROR
END; -- ComputeConflicts
SameConstraints:
PROC [c1, c2:
REF
ANY]
RETURNS [
BOOLEAN] = {
IF c1 = c2 THEN RETURN[TRUE];
WITH c1
SELECT
FROM
con1:
REF Constraint => {
WITH c2
SELECT
FROM
con2: REF Constraint => RETURN [con1.name = con2.name];
ENDCASE => RETURN [FALSE];
};
ENDCASE => RETURN[FALSE];
}; -- SameConstraints
ResolveConstraints:
PROC [newConstraint:
REF Constraint, oldValue:
REF
ANY, resolution:
REF
SX.ConstraintResolution]
RETURNS [
REF
ANY] =
BEGIN
The consistency rules for SX.ConstraintResolution are non-trivial, the order of application should not be important—this is the key attribute.
Check for side effects of returning NEW Constraint!!!
WITH oldValue
SELECT
FROM
oldConstraint:
REF Constraint => {
specificNode: REF SX.CircuitNode ← NIL;
result: REF Constraint ← resolution[newConstraint.index][oldConstraint.index];
IF result=NIL THEN CD.Error[ec~ other, explanation~ "Invalid ConstraintResolution"];
specificNode ← IF newConstraint.specificCorrespondingNode # NIL THEN newConstraint.specificCorrespondingNode ELSE oldConstraint.specificCorrespondingNode;
Be careful if you have more than one constraint type with a specificCorrespondingNode
Bowers September 4, 1985 4:13:08 pm PDT
IF specificNode #
NIL
THEN {
result ← NEW[Constraint ← result^];
result.specificCorrespondingNode ← specificNode};
RETURN [result]
}; -- end oldConstraint: REF CircuitConstraint
node:
REF Node => {
result: REF Constraint ← resolution[newConstraint.index][SX.nodeIndex];
IF result=NIL THEN RETURN [node]
ELSE {
IF newConstraint.specificCorrespondingNode #
NIL
THEN {
result ← NEW[Constraint ← result^];
result.specificCorrespondingNode ← newConstraint.specificCorrespondingNode};
RETURN [result]};
};
rect:
REF Rectangle => {
result: REF Constraint ← resolution[newConstraint.index][SX.nodeIndex];
IF result=NIL THEN RETURN [rect]
ELSE {
IF newConstraint.specificCorrespondingNode #
NIL
THEN {
result ← NEW[Constraint ← result^];
result.specificCorrespondingNode ← newConstraint.specificCorrespondingNode};
RETURN [result]};
};
ENDCASE => ERROR
END; -- ResolveConstraints
Procedures For First Per Layer Loop
[BloatConflictsIntoAOIs (AOI = Area Of Interest)]
TileIsIsolated:
PROC [plane: Tesselation, tile: Tile]
RETURNS [
BOOL ←
TRUE] ~
BEGIN
Marches along the periphery to determine whether there is material.
RETURN [FALSE]
END; -- TileIsIsolated
BloatConflictsIntoAOIs:
PROC [
cir:
REF
SX.Circuit,
layer:
SX.SpinifexLayerIndex,
conflictWorld: Tesselation]
RETURNS [cleanedConflictWorld: Tesselation] = BEGIN
All rectangles where there is no overlap are deleted. Since the area of interest is 1/2 of the maximal interaction distance, at the end there may be regions which contain none of the original material. For this reason the areas of interest are bloated by 1/2 of the maximal interaction distance.
CopyBloated: CStitching.TileProc =
BEGIN
[tile: Tile, data: REF ANY] RETURNS [REF ANY]
IF (tile.value = $Conflict) THEN
IF ((tile.value = $Conflict) OR (TileIsIsolated [conflictWorld, tile])) THEN
TileIsIsolated is needed, because isolated tiles were not copied in the new conflict world when conflicts are bloated into areas of interest. The consequence was that the width rules were not tested. This additional check is not really needed, because Lichen would complain about a bogus isolated node. However, the way Lichen complains is ungenly opening an event viewer with a spurious reason. Therefore, designers expressed the wish that Spinifex gently reports width violations in this case.
cleanedConflicts.ChangeRect [
rect: CDBasics.Extend[tile.Area, bloatValue],
new: $AOI];
END; -- CopyBloated
bloatValue: INT ← SXAccess.sxTech.layerInterestBloat [layer];
cleanedConflicts: Tesselation ← CStitching.NewTesselation [];
[] ← conflictWorld.EnumerateArea [cir.spinifexLayers[layer].size, CopyBloated];
CStitching.ResetTesselation [conflictWorld];
cleanedConflictWorld ← cleanedConflicts;
END; -- BloatConflictsIntoAOIs
InstantiateAOIs:
PROC [
cir:
REF
SX.Circuit,
qt:
REF SXQuadTree.QuadTree,
cellBBox:
CD.Rect,
flatTrans:
CD.Transformation ← [],
nameQualifier:
LIST
OF
CD.Instance ←
NIL,
layer:
SX.SpinifexLayerIndex,
conflictWorld: Tesselation,
geometryWorld: Tesselation,
constraintQueue: ConstraintQueue]
RETURNS [newConstraintQueue: ConstraintQueue] = BEGIN
Depth first instantiation of those regions of the hierarchy that were found to be interesting.
InstantiateTree:
PROC [qt:
REF SXQuadTree.QuadTree, qtBranchBox:
CD.Rect] =
BEGIN
EnqueueConstraintRegion:
PROC [cc:
REF Constraint, r: CStitching.Rect] =
BEGIN
constraintQueue[layer] ← CONS [
NEW [CStitching.Region ← [rect: r, value: cc]],
constraintQueue[layer]]
END; -- EnqueueConstraintRegion
InstantiateTree
branchBox: CD.Rect = CDBasics.MapRect [itemInCell: qtBranchBox, cellInWorld: flatTrans];
IF conflictWorld.IsEmpty [branchBox] THEN RETURN;
FOR boxes: SXQuadTree.Rectangles ← qt.boxes, boxes.rest
WHILE boxes#
NIL
DO
mappedDim: CD.Rect = CDBasics.MapRect [
itemInCell: SXQuadTree.Dimension [boxes.first],
cellInWorld: flatTrans];
IF
NOT conflictWorld.IsEmpty[mappedDim]
THEN {
WITH boxes.first.nodeInformation
SELECT
FROM
subAppl:
CD.Instance => {
cellQt: REF SXQuadTree.QuadTree;
subcellBBox: CD.Rect;
[size: subcellBBox, geometry: cellQt] ← SXAccessInternal.GetLogicalCell[subAppl.ob].circuit.spinifexLayers[layer];
IF cellQt = NIL THEN LOOP;
constraintQueue ← InstantiateAOIs [qt: cellQt,
cellBBox: subcellBBox,
flatTrans: CDBasics.ComposeTransform[itemInCell: subAppl.trans, cellInWorld: flatTrans],
nameQualifier: CONS [subAppl, nameQualifier],
-- following are the parameters added in the restructuration: --
cir: cir,
layer: layer,
conflictWorld: conflictWorld,
geometryWorld: geometryWorld,
constraintQueue: constraintQueue];
}; -- end rectangle is a subcell
cNode:
REF
SX.CircuitNode => {
nameQualifier is not NIL when this node comes from a subcell of the cell currently being processed:
name: REF SX.CircuitNode = IF (nameQualifier=NIL) THEN cNode ELSE cir.FindRootNode [subcircuitNode: cNode,
qualifier: nameQualifier,
insertIfNotInCircuit: TRUE].node;
occupants: LIST OF REF CStitching.Region ← NARROW[geometryWorld.ListArea[mappedDim] ];
newList: LIST OF REF SX.CircuitNode ← LIST[name];
geometryWorld.ChangeRect [rect: mappedDim, new: newList];
WHILE occupants #
NIL
DO
IF
NOT conflictWorld.IsEmpty[occupants.first.rect]
THEN
WITH occupants.first.value
SELECT
FROM
oldList:
LIST
OF
REF
SX.CircuitNode =>
-- oldList forms shared tail in all multiply occupied areas. Subsequent processing allows this. We must ensure that each node appears only once and that the list head is unique.
IF ~(oldList.first = name
AND oldList.rest=
NIL)
THEN {
old: LIST OF REF SX.CircuitNode ← oldList;
replaceList: LIST OF REF SX.CircuitNode;
WHILE old#
NIL
DO
check not already on list.
IF old.first = name THEN EXIT;
old ← old.rest;
ENDLOOP;
replaceList ←
IF old#
NIL
THEN
CONS [oldList.first, oldList.rest]
ELSE CONS [name, oldList];
geometryWorld.ChangeRect [rect: occupants.first.rect, new: replaceList]
};
ENDCASE => ERROR;
occupants ← occupants.rest;
ENDLOOP;
}; -- end rectangle is a node
cc: REF Constraint => EnqueueConstraintRegion[cc, mappedDim];
ENDCASE => ERROR -- This type not expected in quad tree
}
ENDLOOP; -- instantiate all rectangles in this Quad Tree node
{
IF qt.subTrees[north] #
NIL
THEN
InstantiateTree [qt.subTrees[north],
[x1: qtBranchBox.x1, y1: qt.midY, x2: qtBranchBox.x2, y2: qtBranchBox.y2]];
IF qt.subTrees[south] #
NIL
THEN
InstantiateTree [qt.subTrees[south],
[x1: qtBranchBox.x1, y1: qtBranchBox.y1, x2: qtBranchBox.x2, y2: qt.midY]];
IF qt.subTrees[east] #
NIL
THEN
InstantiateTree [qt.subTrees[east],
[x1: qt.midX, y1: qtBranchBox.y1, x2: qtBranchBox.x2, y2: qtBranchBox.y2]];
IF qt.subTrees[west] #
NIL
THEN
InstantiateTree [qt.subTrees[west],
[x1: qtBranchBox.x1, y1: qtBranchBox.y1, x2: qt.midX, y2: qtBranchBox.y2]];
}
END; -- InstantiateTree
Main of InstantiateAOIs
InstantiateTree [qt, cellBBox];
newConstraintQueue ← constraintQueue
END; -- InstantiateAOIs
AnalyzeNodesInAOIs:
PROC [
cir:
REF
SX.Circuit,
layer:
SX.SpinifexLayerIndex,
geometryWorld: Tesselation] =
BEGIN
The nodes are analysed. Problem: parasitics. The constraints are put in and resolved (additional complexity for electrical conductivity).
MergeNodeTiles: CStitching.TileProc =
BEGIN
[tile: Tile, data: REF ANY] RETURNS [REF ANY]
This is quite an embarassment to me, but ...
This code deals with area and perimeter calculation, perhaps it could be done better. I could think of two ways to do this, neither of them particularly great. I chose to implement the one I understood best although it is perhaps the less efficient of the two. Each cornersitched tile is a list of CircuitNodes which had tiles in the area, think of them as the set of sources for any tile. I'm sure with a bit more time someone could come up with a better way to represent these sets than lists, however it should not be too bad as I expect the list will only ever contain a couple of members. Just be warned that pathological behaviour may arise. Note the length of source lists is precisely the degree of overlap of boxes with the proviso that subcells only contribute one box. Actually it hasn't turned out too badly.
CountEdge:
PROC [nl1, nl2:
LIST
OF
REF
SX.CircuitNode]
RETURNS [
INT] =
BEGIN
There is an edge for every SX.CircuitNode not shared by the two lists.
InAButNotB:
PROC [a,b:
LIST
OF
REF
SX.CircuitNode]
RETURNS [c:
INT ← 0] =
BEGIN
FOR s1:
LIST
OF
REF
SX.CircuitNode ← a, s1.rest
WHILE s1#
NIL
DO
s2: LIST OF REF SX.CircuitNode ← b;
WHILE s2#
NIL
DO
IF s1.first=s2.first THEN EXIT; -- Shared sources.
s2 ← s2.rest;
ENDLOOP;
IF s2=NIL THEN c ← c+1; -- node in s1 not in s2
ENDLOOP;
END; -- InAButNotB
RETURN [InAButNotB[a: nl1, b: nl2] + InAButNotB[a: nl2, b: nl1]]
END; -- CountEdge
MergeNodeTiles:
IF SXAccess.stopFlag^ THEN ERROR ABORTED;
WITH tile.value
SELECT
FROM
cnList:
LIST
OF
REF
SX.CircuitNode => {
Process merging and area changes in the interior of the tile.
list: LIST OF REF SX.CircuitNode ← cnList.rest;
eastBound: INT = tile.EEdge;
northBound: INT = tile.NEdge;
westBound: INT = tile.WEdge;
southBound: INT = tile.SEdge;
r: CD.Rect = tile.Area;
extraNodes: INT ← 0;
n1: REF SX.CircuitNode = SX.LookupNode [cnList.first];
WHILE list #
NIL
DO
n2: REF SX.CircuitNode = SX.LookupNode [list.first];
IF n1 # n2 THEN cir.MergeNode [to: n1, from: n2];
Area adjustment.
SX.AdjustNode [node: n1, layer: layer, area: -((r.x2 - r.x1)*(r.y2 - r.y1)), perim: 0];
extraNodes ← extraNodes+1;
list ← list.rest;
ENDLOOP;
Process merging and perim changes at the tile southern and western boundary.
To do this we must count the number of edges at each tile-pair boundary. MARK
FOR tileSouth: Tile ← tile.WS, tileSouth.NE
WHILE tileSouth.WEdge < eastBound
DO
IF tileSouth.value#
NIL
THEN
WITH tileSouth.value
SELECT
FROM
cnSouthList:
LIST
OF
REF
SX.CircuitNode => {
n2: REF SX.CircuitNode = SX.LookupNode [cnSouthList.first];
IF n1 # n2 THEN cir.MergeNode [to: n1, from: n2];
SX.AdjustNode [node: n1,
layer: layer,
area: 0,
perim: -(CountEdge[cnList, cnSouthList] * (MIN[eastBound, tileSouth.EEdge] - MAX[westBound, tileSouth.WEdge]))]
};
constraint: REF Constraint => NULL; -- Ignore
ENDCASE => ERROR
ELSE
--
tileSouth.value=NIL
IF extraNodes > 0
THEN
SX.AdjustNode [node: n1,
layer: layer,
area: 0,
perim: -(extraNodes * (MIN[eastBound, tileSouth.EEdge] - MAX[westBound, tileSouth.WEdge]))]
ENDLOOP; -- end FOR tileSouth
FOR tileWest: Tile ← tile.
SW, tileWest.
EN
WHILE tileWest.SEdge < northBound
DO
IF tileWest.value#
NIL
THEN
WITH tileWest.value
SELECT
FROM
cnWestList:
LIST
OF
REF
SX.CircuitNode => {
n2: REF SX.CircuitNode;
IF n1 # (n2←
SX.LookupNode[cnWestList.first])
THEN
cir.MergeNode [to: n1, from: n2];
SX.AdjustNode [node: n1,
layer: layer,
area: 0,
perim: -(CountEdge[cnList, cnWestList] * (MIN[northBound, tileWest.NEdge] - MAX[southBound, tileWest.SEdge]))]
};
constraint: REF Constraint => NULL; -- Ignore
ENDCASE => ERROR
ELSE
IF extraNodes > 0
THEN
SX.AdjustNode [node: n1,
layer: layer, area: 0,
perim: -(extraNodes * (MIN[northBound,tileWest.NEdge] - MAX[southBound,tileWest.SEdge]))]
ENDLOOP; -- tileWest
FOR tileNorth: Tile ← tile.
EN, tileNorth.
SW
WHILE tileNorth.EEdge > westBound
DO
IF (tileNorth.value =
NIL)
AND (extraNodes > 0)
THEN
SX.AdjustNode [node: n1,
layer: layer,
area: 0,
perim: -(extraNodes * (MIN[eastBound, tileNorth.EEdge] - MAX[westBound, tileNorth.WEdge]))]
ENDLOOP; -- tileNorth
FOR tileEast: Tile ← tile.
NE, tileEast.
WS
WHILE tileEast.NEdge > southBound
DO
IF (tileEast.value=
NIL)
AND (extraNodes > 0)
THEN
SX.AdjustNode [node: n1,
layer: layer,
area: 0,
perim: -(extraNodes * (MIN[northBound, tileEast.NEdge] - MAX[southBound, tileEast.SEdge]))]
ENDLOOP; -- tileEast
};
ENDCASE => ERROR
END; -- MergeNodeTiles
AnalyzeNodesInAOIs.
[] ← geometryWorld.EnumerateArea [rect: cir.spinifexLayers[layer].size,
eachTile: MergeNodeTiles];
END; -- AnalyzeNodesInAOIs
Procedures For Third Per Layer Loop
MixRec: TYPE = RECORD [newConstraint: REF Constraint,
rect: CD.Rect,
resolution: REF SX.ConstraintResolution,
tilesToPaint: LIST OF REF CStitching.Region];
CheckRec: TYPE = RECORD [conflictWorld: Tesselation,
geometryWorld: Tesselation,
rules: LIST OF REF SX.GeometricRule,
cell: REF SX.LogicalCell,
cir: REF SX.Circuit];
DesignRuleCheckAOIs:
PROC [
cir:
REF
SX.Circuit,
cell:
REF
SX.LogicalCell,
constraintQueue: ConstraintQueue,
layer:
SX.SpinifexLayerIndex,
geometryWorld: Tesselation,
conflictWorld: Tesselation] =
BEGIN
Corner based checking. The tesselation is enumerated, etc. Fine point: inside/outside (concave corners).
Tile types: Space (0), Current (1), Constraint (2-7).
Each rule has two boolean vectors:
trigger1 identifies whether it is really a corner and gives the orientation.
trigger2 gives the checking rectangle.
CStitching.Enumerate is called to find all rectangles which intersect the checking rectangle. Trigger2 is used to see whether the type is there. If yes, the design rule is checked. If there is connection and it is legal, then it is not flagged as an error. This (CheckValue) is the place where the Euclidean distance would complement the Manhattan distance.
mixRef: REF MixRec = NEW [MixRec]; -- used to transfer parameters to MixConstraints
checkRef: REF CheckRec = NEW[CheckRec]; -- used to transfer parameters to CheckTile
First add the constraint regions to the geometry.
FOR newCc:
LIST
OF
REF CStitching.Region ← constraintQueue[layer], newCc.rest
WHILE newCc#
NIL
DO
mixRef^ ← [newConstraint: NARROW [newCc.first.value],
rect: newCc.first.rect,
resolution: SXAccess.sxTech.constraintResolutions[layer],
tilesToPaint: NIL];
[] ← geometryWorld.EnumerateArea [rect: mixRef.rect,
eachTile: MixConstraints,
skip: $Nothing,
data: mixRef];
FOR tilesToPaint:
LIST
OF
REF CStitching.Region ← mixRef.tilesToPaint, tilesToPaint.rest
WHILE tilesToPaint#
NIL
DO
geometryWorld.ChangeRect [rect: tilesToPaint.first.rect, new: tilesToPaint.first.value]
ENDLOOP;
ENDLOOP;
examine every tile
checkRef^ ← [conflictWorld: conflictWorld,
geometryWorld: geometryWorld,
cell: cell,
cir: cir,
rules: SXAccess.sxTech.rules[layer]];
[] ← geometryWorld.EnumerateArea [rect: cir.spinifexLayers[layer].size,
eachTile: CheckTile,
skip: $Nothing,
data: checkRef]
END; -- DesignRuleCheckAOIs
MixConstraints: CStitching.TileProc =
BEGIN
called from DesignRuleCheckAOIs only
[tile: Tile, data: REF ANY] RETURNS [REF ANY]
mixRef: REF MixRec = NARROW [data];
newval: REF ANY ← mixRef.newConstraint;
IF (tile.value =
NIL)
OR (tile.value # (newval ← ResolveConstraints [mixRef.newConstraint, tile.value, mixRef.resolution]))
THEN
mixRef.tilesToPaint ← CONS [
NEW [CStitching.Region ← [rect: CDBasics.Intersection [mixRef.rect, tile.Area],
value: newval]],
mixRef.tilesToPaint]
END; -- MixConstraints
FindNode:
PROC [handle:
REF CheckRec, nodeLayer:
SX.SpinifexLayerIndex, r:
CD.Rect]
RETURNS [
REF
ANY] =
BEGIN
logically local to CheckTile
node: REF SX.CircuitNode;
FoundIt: SIGNAL [n: REF SX.CircuitNode];
{
ENABLE FoundIt => {node ← n; GOTO Done};
FindNodeInner:
PROC [circuit:
REF
SX.Circuit, rect:
CD.Rect, aChain:
LIST
OF
CD.Instance] =
BEGIN
SearchForNode: SXQuadTree.PerRectProc =
BEGIN
[r: REF Rectangle, data: REF ANY]
(local of FindNodeInner, local of FindNode, local of DesignRuleCheckAOIs, local of AnalyzeGeometry)
WITH r.nodeInformation
SELECT
FROM
n:
REF
SX.CircuitNode =>
IF CDBasics.Intersect[r.Dimension, rect]
THEN {
parentNode: REF SX.CircuitNode;
newChain: LIST OF CD.Instance;
[parentNode, newChain] ← handle.cir.FindRootNode[n, aChain];
IF newChain=NIL THEN SIGNAL FoundIt[parentNode]
};
a:
CD.Instance => {
Compose Clip and recurse
subcir: REF SX.Circuit = SXAccessInternal.GetLogicalCell[a.ob].circuit;
subR: CD.Rect = CDBasics.DeMapRect [itemInWorld: rect, cellInWorld: a.trans];
FindNodeInner[subcir, subR, CONS[a, aChain]];
};
ENDCASE;
END; -- SearchForNode
FindNodeInner
SXQuadTree.Enumerate [circuit.spinifexLayers[nodeLayer], rect, SearchForNode, NIL]
END; -- FindNodeInner
FindNodeInner[handle.cir, r, NIL];
RETURN [NEW[INT]];
EXITS Done => RETURN [node];
}
END; -- FindNode
CheckTile: CStitching.TileProc =
BEGIN
[tile: Tile, data: REF ANY] RETURNS [REF ANY]
called from DesignRuleCheckAOIs only
Quadrants: TYPE = {ne, nw, sw, se};
DesignRuleCheckCorner:
PROC [quadVals:
ARRAY Quadrants
OF
REF
ANY, pos:
CD.Position] =
BEGIN
CheckArea:
PROC [rule:
REF
SX.GeometricRule, orient:
CD.Orientation, flavour: { convex, concave}] =
BEGIN
--this damm procedure has a non standard way of interpreting orient
FindNodeAtCorner:
PROC [n:
REF
ANY]
RETURNS [
REF
ANY] =
BEGIN
WITH n
SELECT
FROM
cn: REF SX.CircuitNode => RETURN [cn];
cc:
REF Constraint => {
IF cc.specificCorrespondingNode # NIL THEN RETURN[SX.LookupNode[cc.specificCorrespondingNode]]; --Bowers, September 4, 1985 2:10:58 pm PDT
IF ~cc.hasCorrespondingNode THEN CD.Error[ec: other, explanation: "FindNodeAtCorner: ~cc.hasCorrespondingNode"];
RETURN [FindNode[handle, cc.correspondingNodeLayer, CDBasics.Extend[CDBasics.ToRect[pos, pos], 1]] ]
};
ENDCASE => RETURN [NEW[INT]];
END;
FindNodeInTile:
PROC [n:
REF
ANY, area:
CD.Rect]
RETURNS [
REF
ANY] =
BEGIN
WITH n
SELECT
FROM
cn: REF SX.CircuitNode => RETURN [cn];
cc:
REF Constraint => {
IF ~cc.hasCorrespondingNode THEN CD.Error[ec: other, explanation: "FindNodeInTile: ~cc.hasCorrespondingNode"];
RETURN [FindNode[handle, cc.correspondingNodeLayer, area]]
};
ENDCASE => RETURN [NEW[INT]];
END;
CheckTileValue: CStitching.TileProc =
BEGIN
PROC [tile: Tile, data: REF ANY] RETURNS [REF ANY]
CheckValue[tile.value, tile.Area]
END;
CheckValue:
PROC [value:
REF
ANY, area:
CD.Rect] =
BEGIN
Each rule has two boolean vectors:
trigger1 identifies whether it is really a corner and gives the orientation.
trigger2 gives the checking rectangle.
CStitching.Enumerate is called to find all rectangles which intersect the checking rectangle. Trigger2 is used to see whether the type is there. If yes, the design rule is checked. If there is connection and it is legal, then it is not flagged as an error. This (CheckValue) is the place where the Euclidean distance would complement the Manhattan distance.
IF SXAccess.stopFlag^ THEN ERROR ABORTED;
WITH value
SELECT
FROM
cn:
REF
SX.CircuitNode => {
IF ~rule.trigger2[SX.nodeIndex] THEN RETURN;
IF (rule.okIfConnected
AND nodeAtCorner#
NIL
AND FindNodeAtCorner[nodeAtCorner] =
SX.LookupNode[cn])
THEN
RETURN;
};
cc:
REF Constraint => {
IF ~rule.trigger2[cc.index] THEN RETURN;
IF (rule.okIfConnected
AND nodeAtCorner#
NIL
AND cc.hasCorrespondingNode
AND FindNodeAtCorner[nodeAtCorner] = FindNodeInTile[cc, area]
OR
(cc.specificCorrespondingNode # NIL AND FindNodeAtCorner[nodeAtCorner] = SX.LookupNode[cc.specificCorrespondingNode])) THEN
RETURN;
};
cnList:
LIST
OF
REF
SX.CircuitNode =>
CD.Error [ec: other, explanation: "CheckValue: found a list of circuit nodes where a single one was expected"];
ENDCASE => {
IF value=NIL THEN {IF ~rule.trigger2[SX.spaceIndex] THEN RETURN}
ELSE CD.Error [ec: other, explanation: "CheckValue: unexpected value"]
};
Check it is really an error. (Kind of funny sort of empty!
What we mean is empty of non-$AOI tiles)
IF notReportedYet
AND conflictWorld.IsEmpty [
rect: CDBasics.MapRect [itemInCell: [x1: -delta, y1: -delta, x2: len, y2: len],
cellInWorld: [pos, orient]],
skip: $AOI] -- where skip actually means 'do not skip'
THEN
BEGIN
-- FOUND AN ERROR
rect: CD.Rect = CDBasics.MapRect [
itemInCell: [x1: 0, y1: 0, x2: rule.extent, y2: rule.extent],
cellInWorld: [pos, orient]];
SXAccessInternal.PutError [ob: handle.cell.cellObj, r: rect, message: rule.message];
notReportedYet ← FALSE
END
END; -- CheckValue
notReportedYet: BOOLEAN ← TRUE;
len: INT = rule.extent;
delta: INT = 1;
IF len = 0
THEN {
Optimize purely local checks.
IF notReportedYet
THEN
CheckValue[quadVals[ne], [pos.x, pos.y, pos.x+delta, pos.y+delta]];
IF notReportedYet
THEN
CheckValue[quadVals[nw], [pos.x, pos.y-delta, pos.x+delta, pos.y]];
IF notReportedYet
THEN
CheckValue[quadVals[sw], [pos.x-delta, pos.y-delta, pos.x, pos.y]];
IF notReportedYet
THEN
CheckValue[quadVals[se], [pos.x-delta, pos.y, pos.x, pos.y+delta]];
}
ELSE {
SELECT flavour
FROM
convex => {
[] ← handle.geometryWorld.EnumerateArea [
rect: CDBasics.MapRect [itemInCell: [x1: -delta, y1: 0, x2: len, y2: len], cellInWorld: [pos, orient]],
eachTile: CheckTileValue,
skip: $Nix];
[] ← handle.geometryWorld.EnumerateArea [
rect: CDBasics.MapRect [itemInCell: [x1: 0, y1: -delta, x2: len, y2: 0], cellInWorld: [pos, orient]],
eachTile: CheckTileValue,
skip: $Nix];
};
concave => {
[] ← handle.geometryWorld.EnumerateArea [
rect: CDBasics.MapRect [itemInCell: [x1: 0, y1: 0, x2: len, y2: len], cellInWorld: [pos, orient]],
eachTile: CheckTileValue,
skip: $Nix];
};
ENDCASE
}
END; -- CheckArea
DesignRuleCheckCorner
or0: CD.Orientation = original;
or90: CD.Orientation = rotate90;
or180: CD.Orientation = rotate180;
or270: CD.Orientation = rotate270;
nodeAtCorner: REF ANY ← NIL;
IF SXAccess.stopFlag^ THEN ERROR ABORTED;
FOR ruleList:
LIST
OF
REF
SX.GeometricRule ← handle.rules, ruleList.rest
WHILE ruleList#
NIL
DO
rule: REF SX.GeometricRule = ruleList.first;
bitIndex: ARRAY Quadrants OF INTEGER = [8, 4, 2, 1];
quadBits: INTEGER ← 0;
nodeAtCorner ← NIL;
Translate the quadrant contents into bit vector values.
FOR q: Quadrants
IN Quadrants
DO
WITH quadVals[q]
SELECT
FROM
cn:
REF
SX.CircuitNode => {
IF rule.trigger1[
SX.nodeIndex]
THEN {
quadBits ← quadBits + bitIndex[q];
nodeAtCorner ← cn
}
};
cc:
REF Constraint => {
IF rule.trigger1[cc.index]
THEN {
quadBits ← quadBits + bitIndex[q];
IF cc.hasCorrespondingNode AND nodeAtCorner=NIL THEN nodeAtCorner ← cc
}
};
cnList:
LIST
OF
REF
SX.CircuitNode => {
CD.Error [ec: other, explanation: "DesignRuleCheckCorner: 'LIST OF REF SX.CircuitNode' should have been squashed to 'REF SX.CircuitNode' in `AnalyzeNodesInAOIs'.\nPLEASE save a copy of this design and make it available to Giordano. Thanks"]
};
ENDCASE => {
IF quadVals[q]=
NIL
THEN {
IF rule.trigger1[SX.spaceIndex] THEN quadBits ← quadBits + bitIndex[q]
}
ELSE CD.Error[ec: other, explanation: "DesignRuleCheckCorner: quadVals[q]#NIL"]
};
ENDLOOP; -- end Translate the quadrant contents into bit vector values
Is this really a corner in the terms of this rule?
Bits are ne=8, nw=4, sw=2, se=1. The check is applied to the quad opposite the generating corner. (IE rot. 180)
Here are are some diagrams to make it explicit, X=TRUE, O=FALSE
0 - OO 1 - OO 2 - OO 3 - OO
OO OX XO XX
4 - XO 5 - XO 6 - XO 7 - XO
OO OX XO XX
8 - OX 9 - OX 10- OX 11- OX
OO OX XO XX
12- XX 13- XX 14- XX 15- XX
OO OX XO XX
SELECT quadBits
FROM
0 => NULL;
1 => CheckArea[rule, or90, convex];
2 => CheckArea[rule, or0, convex];
3 => NULL;
4 => CheckArea[rule, or270, convex];
5 => { CheckArea[rule, or90, convex]; CheckArea[rule, or270, convex] };
6 => NULL;
7 => CheckArea[rule, or0, concave];
8 => CheckArea[rule, or180, convex];
9 => NULL;
10 => { CheckArea[rule, or0, convex]; CheckArea[rule, or180, convex] };
11 => CheckArea[rule, or90, concave];
12 => NULL;
13 => CheckArea[rule, or180, concave];
14 => CheckArea[rule, or270, concave];
15 => NULL;
ENDCASE => ERROR;
ENDLOOP;
END; -- DesignRuleCheckCorner
CheckTile
Since tile are stitched at their North-East and South-West corners these are favoured points from which to DRC. We exploit the fact that every corner has either 3 or (rarely) 4 edges meeting at it, and thus contains a NE or SW or (rarely) both tile corner at it.
handle: REF CheckRec = NARROW[data];
conflictWorld: Tesselation = handle.conflictWorld;
tileBound: CD.Rect = tile.Area;
SW corner
IF conflictWorld.FindTile[[x: tileBound.x1, y: tileBound.y1]].value = $AOI
THEN {
IF tile.
SW.SEdge = tileBound.y1
THEN {
IF tile.WS.WEdge = tileBound.x1 THEN NULL -- This is a (rare I suspect) 4 way corner it is handled at the NE corner.
ELSE {
IF tile.value = tile.
SW.value
THEN
CD.Error[ec: other, explanation: "CheckTile: violated Max horz rule"];
Get the quadrants at the SW corner and call DesignRuleCheckCorner
DesignRuleCheckCorner[
[ne: tile.value, nw: tile.SW.value, sw: tile.WS.value, se: tile.WS.value],
[tileBound.x1, tileBound.y1]
];
}
}
ELSE {
-- tile.WS.WEdge = tileBound.x1 IMPLICITLY
IF tile.value = tile.WS.value THEN NULL -- No corner really
ELSE {
Get the quadrants at the SW corner and call DesignRuleCheckCorner
DesignRuleCheckCorner [
[ne: tile.value, nw: tile.SW.value, sw: tile.SW.value, se: tile.WS.value],
[tileBound.x1, tileBound.y1]];
}
}
};
NE corner
IF conflictWorld.FindTile[[x: tileBound.x2, y: tileBound.y2]].value = $AOI
THEN {
IF tile.
NE.NEdge = tileBound.y2
THEN {
IF tile.
EN.EEdge = tileBound.x2
THEN {
4 way corner, damn it
neQTile: Tile ← tile.EN.NE;
WHILE neQTile.SEdge > tileBound.y2
DO
neQTile ← neQTile.WS;
ENDLOOP;
DesignRuleCheckCorner [
[ne: neQTile.value, nw: tile.EN.value, sw: tile.value, se: tile.NE.value],
[tileBound.x2, tileBound.y2]];
}
ELSE {
IF tile.value = tile.
NE.value
THEN
CD.Error[ec: other, explanation: "CheckTile: violated Max horz rule NEast"];
Get the quadrants at the NE corner and call DesignRuleCheckCorner
DesignRuleCheckCorner [
[ne: tile.EN.value, nw: tile.EN.value, sw: tile.value, se: tile.NE.value],
[tileBound.x2, tileBound.y2]];
}
}
ELSE {
-- tile.EN.EEdge = tileBound.x2 IMPLICITLY
IF tile.value = tile.EN.value THEN NULL -- No corner really
ELSE {
Get the quadrants at the NE corner and call DesignRuleCheckCorner
DesignRuleCheckCorner [
[ne: tile.NE.value, nw: tile.EN.value, sw: tile.value, se: tile.NE.value],
[tileBound.x2, tileBound.y2]];
}
}
}
END; -- CheckTile
Main Procedure
AnalyzeGeometry:
PUBLIC
PROC [cell:
REF
SX.LogicalCell] =
BEGIN
Process each of the analysis layers.
cir: REF SX.Circuit = cell.circuit;
constraintQueue: ConstraintQueue;
IF freeTesselations THEN FreeTesselations[circuit: cir];
First per layer loop. The quad-trees are enumerated and the conflict world is constructed. Then the areas of interest are bloated. Finally the quad-tree is instantiated into the geometry world and the nodes are analysed.
FOR layer:
SX.SpinifexLayerIndex
IN [0 .. SXAccess.sxTech.numSpinifexLayers)
DO
conflictWorld: Tesselation ← conflictWorlds[layer] ← CStitching.NewTesselation[];
geometryWorld: Tesselation ← geometryWorlds[layer] ← CStitching.NewTesselation[];
cir.spinifexLayers[layer] ← SXQuadTree.Create [cir.spinifexLayers[layer]];
IF cir.spinifexLayers[layer].geometry = NIL THEN LOOP;
IF SXAccess.stopFlag^ THEN ERROR ABORTED;
ComputeConflicts [cir.spinifexLayers[layer].geometry, conflictWorld, layer, cir];
The quad-trees are enumerated and the conflict world is constructed. Each rectangle has an area of interest depending on the material. Constraints do not overlap: they are ordered into the technology dependent part; the larger prevails. Every constraint is represented by a number which is an index in a boolean array to infere whether it is there.
Set break point here to look at the conflict world !
SXAccess.sxTech.spinifexLayerNames[layer].layerId
CSMonitor.Monitor [plane: conflictWorld, name: "conflictWorld", paintDark: NIL];
conflictWorld ← conflictWorlds[layer] ← BloatConflictsIntoAOIs [cir, layer, conflictWorld];
All rectangles where there is no overlap are deleted. Since the area of interest is 1/2 of the maximal interaction distance, at the end there may be regions which contain none of the original material. For this reason the areas of interest are bloated by 1/2 of the maximal interaction distance.
The quad-tree is instantiated into the geometry world. This is done in two steps, because a tile can have only one value. First the electrical carrying stuff is handled, then the constraints.
constraintQueue ← InstantiateAOIs [cir: cir,
qt: cir.spinifexLayers[layer].geometry,
cellBBox: cir.spinifexLayers[layer].size,
layer: layer,
conflictWorld: conflictWorld,
geometryWorld: geometryWorld,
constraintQueue: constraintQueue];
Now the nodes are analysed. Problem: parasitics. The constraints are put in and resolved (additional complexity for electrical conductivity).
AnalyzeNodesInAOIs [cir, layer, geometryWorld];
ENDLOOP; -- end of FOR "layer: SX.SpinifexLayerIndex IN [0..SXAccess.sxTech.numSpinifexLayers) DO"
TerminalIO.PutRope [". "];
Second per layer loop. For each conductive region in the geometry worlds, change the "LIST OF REF SX.CircuitNode"s (which have already been compressed into a single node per region) to a REF SX.CircuitNode. Normalises the geometrical representation of nodes (All electrically connected regions are made to point to the same node [which was determined in `AnalyzeNodesInAOIs']).
The loop in plain text:
for every Spinifex layer
for every rectangle of material in the design
get the list of the electrically connected rectangles in the circuit
collapse the attributes (value) of all rectangle to a single instance of the attributes
transform the list consisting of a single element in a single element (attributes).
FOR layer:
SX.SpinifexLayerIndex
IN [0..SXAccess.sxTech.numSpinifexLayers)
DO
geometryWorld: Tesselation ← geometryWorlds[layer];
IF SXAccess.stopFlag^ THEN ERROR ABORTED;
FOR tiles:
LIST
OF
REF CStitching.Region ← CStitching.ListArea[plane: geometryWorld, rect: cir.spinifexLayers[layer].size], tiles.rest
WHILE tiles#
NIL
DO
CStitching.ChangeRect [plane: geometryWorld, rect: tiles.first.rect,
new: SX.LookupNode[NARROW[tiles.first.value, LIST OF REF SX.CircuitNode].first]]
ENDLOOP;
ENDLOOP;
SX.NormalizeCircuit [cir];
TerminalIO.PutRope [". "];
Third per layer loop. Corner based checking. The tesselation is enumerated, etc. Fine point: inside/outside (concave corners).
FOR layer:
SX.SpinifexLayerIndex
IN [0..SXAccess.sxTech.numSpinifexLayers)
DO
conflictWorld: Tesselation ← conflictWorlds[layer];
geometryWorld: Tesselation ← geometryWorlds[layer];
DesignRuleCheckAOIs [cir, cell, constraintQueue, layer, geometryWorld, conflictWorld];
ENDLOOP;
TerminalIO.PutRope [". "];
IF saveTesselations THEN freeTesselations ← TRUE ELSE FreeTesselations [circuit: cir];
END; -- AnalyzeGeometry
Maintenance Aids
SaveTesselations:
PUBLIC
PROC [save:
BOOL ←
FALSE] =
BEGIN
saveTesselations ← save
END;
GetTesselation:
PUBLIC
PROC [conflicts:
BOOL ←
TRUE, layer:
SX.SpinifexLayerIndex]
RETURNS [Tesselation] =
BEGIN
RETURN [IF conflicts THEN conflictWorlds[layer] ELSE geometryWorlds[layer]]
END;
FreeTesselations:
PROC [circuit:
REF
SX.Circuit] =
BEGIN
FOR layer:
SX.SpinifexLayerIndex
IN [0..SXAccess.sxTech.numSpinifexLayers)
DO
CStitching.ResetTesselation [conflictWorlds[layer]];
CStitching.ResetTesselation [geometryWorlds[layer]]
ENDLOOP;
TerminalIO.PutRope [". "]; CStitching.DumpCache [];
freeTesselations ← FALSE
END;
END.
Edited on January 3, 1985 11:45:56 am PST, by Jacobi
Fehler umgangen, nicht wirklich korrigiert da nicht verstanden.
Edited on January 3, 1985 4:58:12 pm PST, by Beretta
Tried to improve readability & debuggability.
Took out ComputeConflicts and ResolveConstraints to create a new module SXConflicts. Reason: storage overflow in the compiler.
Edited on January 23, 1985 3:45:47 pm PST, by Beretta
Improved structure
Edited on February 26, 1985 11:46:36 am PST, by Jacobi
stopFlag test feature
Edited on March 6, 1985, by Shand
Made Constraint to node conflict detection more uniform so that OccupyByConstr and OccupyByNode implement same approach.
changes to: OccupyByConstr $Conflict results only if ResolveConstraints[Constraint, Node] # Node.
Edited on March 7, 1985 1:21:40 am PST, by Shand
Removed unnecessary parameters from Tree enumeration procedures
Added Heuristic procedure to override Level-order Conflict Resolution based on value returned by UseLevelOrderHeuristic.
changes to: FlattenCell (local of Flatten), DescendTree (local of DescendCell, local of DescendOneLevel), DescendCell (local of DescendOneLevel)
changes to: UseLevelOrderHeuristic to choose when to apply Level-order Conflict Resolution, ComputeConflicts, OccupyByAppl in case where region is currently occupied by another cell, either DescendOneLevel, or Flatten., OccupyByAppl, ThinLimit, UseLevelOrderHeuristic, OccupyByAppl, DIRECTORY, FlattenTree (local of FlattenCell, local of Flatten), DescendTree (local of DescendCell, local of DescendOneLevel)
Edited on March 7, 1985 2:50:27 am PST, by Shand
Fixed bug in FlattenTree when calling back to bid for Node. Used to call on subcell's REF Rectangle (boxes.first) rather than topcell's REF Rectangle (applRef.first)
changes to: FlattenTree (local of FlattenCell, local of Flatten) case node
Edited on March 8, 1985 6:04:21 pm PST, by Shand
Added parameter to SXConflicts.ResolveConstraints from TechHandle.
changes to: MixConstraints
Edited on March 9, 1985 12:22:24 pm PST, by Shand
Changed name of CircuitConstraint in SX to Constraint, added tech parameter to ComputeConflicts, changed ResolveConstraints to deal with new constraint resolution representation.
changes to: DIRECTORY, ComputeConflicts, OccupyByNode, ResolveConstraints, node (local of ResolveConstraints), rect (local of ResolveConstraints), ComputeConflicts
Edited on March 13, 1985 0:39:24 am PST, by Shand
Optimizations and enhancements to allow zero extent rules.
changes to: DesignRuleCheckAOIs
Edited on March 19, 1985 6:20:07 pm PST, by Beretta
Added maintenance aids section.
changes to: saveTesselations: new, freeTesselations: new, AnalyzeGeometry: check whether old tessellations hang around and fourth loop is done only if necessary in a separate procedure, SaveTesselations: new, GetTesselation: new, FreeTesselations: new
Edited on March 27, 1985 8:02:00 pm PST, by Beretta
procedures MixConstraints, CheckTile made global
Edited on April 8, 1985 3:36:29 pm PST, by Jacobi
reformatted
Edited on June 29, 1985 8:25:03 pm PDT, by Beretta
Tried to fix Quad Tree stuff
gbb December 3, 1985 4:13:28 pm PST
Partially re-re-restored formatting; cleaned up.
gbb February 10, 1986 11:46:37 am PST
Tracked change in Compiler and merged in again ComputeConflicts and ResolveConstraints., SXLayersImpl, BEGIN, ComputeConflicts, ResolveConstraints, AnalyzeGeometry
gbb July 31, 1986 6:07:36 pm PDT
changes to: DIRECTORY, FreeTesselations: now really disposes the tiles.