SXConflictsImpl.mesa;
Copyright © 1984, 1985, 1986 by Xerox Corporation. All rights reserved.
Written by: Beretta, January 3, 1985 6:23:57 pm PST
Last Edited by Mark Shand, March 9, 1985 12:22:24 pm PST
Last Edited by: Jacobi, April 8, 1985 10:51:01 am PST
Bowers, September 4, 1985 5:40:59 pm PDT
Last edited by: gbb January 9, 1986 5:54:46 pm PST
This module contains only the procedures ComputeConflicts and ResolveConstraints which previously were in the module SpinifexLayersImpl, which is its only client. The operation was necessary because of storage problems in the compiler.
DIRECTORY
CD USING [Instance, Error, ErrorCode, Number, Object, Orientation, Position, Rect],
CDBasics USING [BaseOfRect, Intersect, Intersection, NonEmpty],
CDOrient USING [ComposeOrient, DeMapRect, MapRect, original, RectAt],
CornerStitching USING [ChangeRect, FuncChangeRect, PerTileChangeProc, Tesselation],
SX USING [Circuit, CircuitNode, Constraint, ConstraintResolution, nodeIndex, SpinifexLayerIndex],
SXAccess USING [design, stopFlag, sxTech],
SXAccessInternal USING [GetSXData],
SXConflicts USING [],
SXQuadTree USING [AreaSplit, QuadTree, Rectangle, Rectangles];
SXConflictsImpl:
CEDAR
PROGRAM
IMPORTS CD, CDBasics, CDOrient, CornerStitching, SXAccessInternal, SXAccess
EXPORTS SXConflicts =
BEGIN
Constraint: TYPE = SX.Constraint;
Rectangle: TYPE = SXQuadTree.Rectangle;
Node: TYPE = SX.CircuitNode;
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:
PUBLIC
PROC [
qt:
REF SXQuadTree.QuadTree,
conflictWorld:
REF CornerStitching.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: CornerStitching.PerTileChangeProc =
BEGIN
[plane: REF Tesselation, rect: CsRect, newValue: 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.
CornerStitching.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
CornerStitching.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
CornerStitching.ChangeRect [conflictWorld, rect, $Conflict];
Else no change.
ENDCASE =>
IF oldValue =
NIL
THEN
Initially the plane is empty, hence tile = NIL. Insert a new tile.
CornerStitching.ChangeRect [conflictWorld, rect, data]
ELSE CD.Error [ec: other, explanation: "Tesselation screwed up (alien tile)"]
END; -- OccupyByNode
OccupyByConstr: CornerStitching.PerTileChangeProc =
BEGIN
[plane: REF Tesselation, rect: CsRect, newValue: 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
CornerStitching.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 CornerStitching.ChangeRect [conflictWorld, rect, $Conflict]
ELSE
IF
NOT SameConstraints[resolution, c]
THEN
CornerStitching.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.
CornerStitching.ChangeRect [conflictWorld, rect, data]
ELSE CD.Error [ec: other, explanation: "Tesselation screwed up (alien tile)"]
END; -- OccupyByConstr
OccupyByAppl: CornerStitching.PerTileChangeProc =
BEGIN
[plane: REF Tesselation, rect: CsRect, newValue: 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.
CornerStitching.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.
CornerStitching.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
appl: CD.Instance = NARROW [applRef.first.nodeInformation];
FlattenCell:
PROC [appl:
CD.Instance, pos:
CD.Position, orient:
CD.Orientation] =
BEGIN
MapRect:
PROC [inCellRect:
CD.Rect]
RETURNS [inWorldRect:
CD.Rect] =
INLINE
BEGIN
inWorldRect ← CDBasics.Intersection [
CDOrient.MapRect [itemInCell: inCellRect,
cellSize: appl.ob.size,
cellInstOrient: orient,
cellInstPos: pos],
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
CornerStitching.FuncChangeRect [conflictWorld, r, OccupyByNode, applRef.first]
};
constr:
REF Constraint => {
r: CD.Rect = MapRect[boxes.first.interestBound];
IF CDBasics.NonEmpty[r]
THEN
conflictWorld.FuncChangeRect[r, OccupyByConstr, constr]
};
subAppl:
CD.Instance =>
IF CDBasics.Intersect [boxes.first.interestBound, mappedClip]
THEN {
FlattenCell [
subAppl,
CDBasics.BaseOfRect [CDOrient.MapRect [
itemInCell: CDOrient.RectAt [pos: subAppl.location, size: subAppl.ob.size, orient: subAppl.orientation],
cellSize: appl.ob.size,
cellInstOrient: orient,
cellInstPos: pos]],
CDOrient.ComposeOrient [subAppl.orientation, orient]]
};
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 = CDOrient.DeMapRect [itemInWorld: clipRect,
cellSize: appl.ob.size,
cellInstOrient: orient,
cellInstPos: pos];
cellQt ← SXAccessInternal.GetSXData[appl.ob].circuit.spinifexLayers[layer].geometry;
IF cellQt #
NIL
THEN
FlattenTree [cellQt]
END; -- FlattenCell
FlattenCell[appl, appl.location, appl.orientation]
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: CornerStitching.PerTileChangeProc =
BEGIN
[plane: REF Tesselation, rect: CsRect, 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 => CornerStitching.ChangeRect [conflictWorld, rect, data];
c: REF Constraint => CornerStitching.ChangeRect [conflictWorld, rect, data];
ENDCASE => ERROR
END; -- BidByNode
BidByConstr: CornerStitching.PerTileChangeProc =
BEGIN
[plane: REF Tesselation, rect: CsRect, 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 CornerStitching.ChangeRect [conflictWorld, rect, data];
c:
REF Constraint =>
BEGIN
resolution: REF ANY = ResolveConstraints [c, data, SXAccess.sxTech.constraintResolutions [layer]];
IF
NOT SameConstraints [resolution, c]
THEN
CornerStitching.ChangeRect [conflictWorld, rect, resolution];
END;
ENDCASE => ERROR;
END; -- BidByConstr
BidByAppl: CornerStitching.PerTileChangeProc =
BEGIN
[plane: REF Tesselation, rect: CsRect, 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 CornerStitching.ChangeRect [conflictWorld, rect, data];
c: REF Constraint => CornerStitching.ChangeRect [conflictWorld, rect, data];
ENDCASE => ERROR;
END; -- BidByAppl
DescendCell:
PROC [appl:
CD.Instance, pos:
CD.Position, orient:
CD.Orientation] =
BEGIN
MapRect:
PROC [inCellRect:
CD.Rect]
RETURNS [inWorldRect:
CD.Rect] =
INLINE
BEGIN
(local of DescendCell, local of DescendOneLevel)
inWorldRect ← CDBasics.Intersection [
CDOrient.MapRect [
itemInCell: inCellRect,
cellSize: appl.ob.size,
cellInstOrient: orient,
cellInstPos: pos],
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
CornerStitching.FuncChangeRect [conflictWorld, r, BidByNode, new.first]
};
constr:
REF Constraint => {
r: CD.Rect = MapRect [boxes.first.interestBound];
IF CDBasics.NonEmpty[r]
THEN
CornerStitching.FuncChangeRect [conflictWorld, r, BidByConstr, constr]
};
subAppl:
CD.Instance =>
IF CDBasics.Intersect [boxes.first.interestBound, mappedClip]
THEN {
IF levelCount > 0
THEN
DescendCell [
subAppl,
CDBasics.BaseOfRect [CDOrient.MapRect [
itemInCell: CDOrient.RectAt [pos: subAppl.location, size: subAppl.ob.size, orient: subAppl.orientation],
cellSize: appl.ob.size,
cellInstOrient: orient,
cellInstPos: pos]],
CDOrient.ComposeOrient [subAppl.orientation, orient]]
ELSE {
r: CD.Rect = MapRect [boxes.first.interestBound];
IF CDBasics.NonEmpty[r]
THEN
CornerStitching.FuncChangeRect [conflictWorld, r, BidByAppl, new]
}
};
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 = CDOrient.DeMapRect [itemInWorld: clipRect,
cellSize: appl.ob.size,
cellInstOrient: orient,
cellInstPos: pos];
cellQt ← SXAccessInternal.GetSXData[appl.ob].circuit.spinifexLayers[layer].geometry;
levelCount ← levelCount-1;
DescendTree [cellQt];
levelCount ← levelCount+1;
END; -- DescendCell
appl: CD.Instance = NARROW [new.first.nodeInformation];
descentDepth ← descentDepth + 1;
levelCount ← descentDepth/2; -- Descend until levelCount = 0
DescendCell [appl, appl.location, appl.orientation];
CornerStitching.FuncChangeRect [conflictWorld, clipRect, OccupyByAppl, old];
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 =>
CornerStitching.FuncChangeRect 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:
CornerStitching.FuncChangeRect [conflictWorld, boxes.first.interestBound, OccupyByNode, boxes.first];
constr:
REF Constraint =>
CornerStitching.FuncChangeRect [conflictWorld, boxes.first.interestBound, OccupyByConstr, constr];
appl:
CD.Instance =>
CornerStitching.FuncChangeRect [conflictWorld, boxes.first.interestBound, OccupyByAppl, boxes];
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
CD.Error [ec: other, explanation: "ComputeConflicts: descentDepth#1"]
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:
PUBLIC
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
END.
Edited on January 3, 1985 6:23:58 pm PST, by Beretta
Created the module taking ComputeConflicts & ResolveConstraints out of SpinifexLayersImpl.mesa.
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 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 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 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 April 8, 1985 3:54:18 pm PST, by Jacobi
reformatted
gbb January 9, 1986 5:53:46 pm PST
Cosmetic changes tracking an error
changes to: here and there