SXConflictsImpl.mesa;
Copyright © 1984, 1985 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: Beretta, June 29, 1985 8:24:27 pm PDT
Last Edited by: Jacobi, April 8, 1985 10:51:01 am 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
Atom USING [PropList],
CD USING [ApplicationPtr, Error, ErrorCode, lambda, Number, ObPtr, Orientation, Position, Properties, 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,
SXAccessInternal,
SXConflicts,
SXQuadTree USING [AreaSplit, QuadTree, Rectangle, Rectangles],
TerminalIO USING [WriteChar];
SXConflictsImpl:
CEDAR
PROGRAM
IMPORTS CD, CDBasics, CDOrient, CornerStitching, SXAccessInternal, SXAccess, TerminalIO
EXPORTS SXConflicts =
BEGIN
debug: BOOL = FALSE;
ThinLimit: CD.Number ← CD.lambda*10;
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.
RETURN [clipRect.x2 - clipRect.x1 > ThinLimit AND clipRect.y2 - clipRect.y1 > ThinLimit]
END;
--Called in the first per layer loop of SpinifexLayersImpl.AnalyzeGeometry.
Constraint: TYPE = SX.Constraint;
Rectangle: TYPE = SXQuadTree.Rectangle;
Node: TYPE = SX.CircuitNode;
ComputeConflicts:
PUBLIC
PROC [
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.
qt: REF SXQuadTree.QuadTree,
conflictWorld: REF CornerStitching.Tesselation,
layer: SX.SpinifexLayerIndex,
cir: REF SX.Circuit] =
BEGIN
descentDepth: INT ← 1;
-- 3 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.ApplicationPtr)
=> 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.
-- In addition conflictWorld will also contain:
=> ATOM ~ $Conflict being the result of an irresolvable conflict for occupancy and flagging a region as requiring instantiation and analysis.
OccupyByNode: CornerStitching.PerTileChangeProc =
-- PROC [plane: REF Tesselation, rect: CD.Rect, oldValue: REF ANY, data: REF ANY]
BEGIN
WITH oldValue
SELECT
FROM
a: ATOM => IF a#$Conflict THEN CD.Error[ec: other, explanation: "OccupyByNode: illegal value"];
r: REF Rectangle => IF data#r THEN conflictWorld.ChangeRect[rect, $Conflict];
applRef: SXQuadTree.Rectangles =>
--Subcell which needs to be flattened out: put in node and flatten subcell.
IF data#applRef.first
THEN {
conflictWorld.ChangeRect[rect, data]; -- sets the value
Flatten [rect, applRef]
}
ELSE CD.Error[ec: other, explanation: "OccupyByNode: data=applRef.first"];
c:
REF Constraint =>
IF ResolveConstraints[c, data, SXAccess.sxTech.constraintResolutions[layer]] # data
THEN
conflictWorld.ChangeRect[rect, $Conflict];
ENDCASE =>
--Initially the plane is empty, hence tile=NIL.
IF oldValue#NIL THEN CD.Error[ec: other, explanation: "OccupyByNode: oldValue#NIL"]
ELSE conflictWorld.ChangeRect[rect, data];
END; -- OccupyByNode
OccupyByConstr: CornerStitching.PerTileChangeProc =
-- PROC [plane: REF Tesselation, rect: CD.Rect, oldValue: REF ANY, data: REF ANY]
BEGIN
WITH oldValue
SELECT
FROM
a: ATOM => IF a#$Conflict THEN CD.Error[ec: other, explanation: "OccupyByConstr: illegal value"];
r:
REF Rectangle =>
IF ResolveConstraints[
NARROW[data], r, SXAccess.sxTech.constraintResolutions[layer]]#r
THEN
conflictWorld.ChangeRect[rect, $Conflict];
applRef: SXQuadTree.Rectangles => {
conflictWorld.ChangeRect[rect, data];
Flatten [rect, applRef]
};
c:
REF Constraint => {
--Resolve constraints against each other.
resolution: REF ANY = ResolveConstraints[c, data, SXAccess.sxTech.constraintResolutions[layer]];
IF resolution#c
AND resolution#data
THEN
conflictWorld.ChangeRect[rect, $Conflict]
ELSE
IF resolution#c
THEN
conflictWorld.ChangeRect[rect, resolution];
};
ENDCASE =>
--Initially the plane is empty, hence tile=NIL.
IF oldValue#NIL THEN CD.Error[ec: other, explanation: "OccupyByConstr: oldValue#NIL"]
ELSE conflictWorld.ChangeRect[rect, data];
END; -- OccupyByConstr
OccupyByAppl: CornerStitching.PerTileChangeProc =
-- PROC [plane: REF Tesselation, rect: CD.Rect, oldValue: REF ANY, data: REF ANY]
BEGIN
-- 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: "OccupyByAppl: a#$Conflict"];
r:
REF Rectangle => {
IF NARROW[data, SXQuadTree.Rectangles].first = r THEN CD.Error[ec: other, explanation: "Rectangle has already been processed"];
Flatten [rect, NARROW[data]]
};
applRef: SXQuadTree.Rectangles =>
IF data#applRef
THEN
IF UseLevelOrderHeuristic[rect, applRef,
NARROW[data]]
THEN
DescendOneLevel [rect, applRef, NARROW[data]]
ELSE {
-- Clear present occupant out of region.
conflictWorld.ChangeRect[rect, NIL];
-- Add flattened rectangles from each cell to region.
Flatten [rect, applRef];
Flatten [rect, NARROW[data]]
};
If subcell of same subcell: already done.
c: REF Constraint => Flatten [rect, NARROW[data]];
ENDCASE =>
IF oldValue#NIL THEN CD.Error[ec: other, explanation: "OccupyByAppl: oldValue#NIL"]
ELSE conflictWorld.ChangeRect[rect, data];
END; -- OccupyByAppl
Flatten:
PROC [clipRect:
CD.Rect, applRef: SXQuadTree.Rectangles] =
BEGIN
appl: CD.ApplicationPtr = NARROW[applRef.first.nodeInformation];
FlattenCell:
PROC [appl:
CD.ApplicationPtr, 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;
FlattenTree:
PROC [qt:
REF SXQuadTree.QuadTree] =
BEGIN
--(local of FlattenCell, local of Flatten)
IF debug THEN TerminalIO.WriteChar['f];
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
conflictWorld.FuncChangeRect[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.ApplicationPtr =>
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 => CD.Error[ec: programmingError, explanation: "Flatten: invalid case"];
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] =
--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.
BEGIN
levelCount: INT;
BidByNode: CornerStitching.PerTileChangeProc =
-- PROC [plane: REF Tesselation, rect: CD.Rect, oldValue: REF ANY, data: REF ANY]
BEGIN
WITH oldValue
SELECT
FROM
a: ATOM => IF a#$Conflict THEN CD.Error[ec: other, explanation: "BidByNode: a#$Conflict"];
r: REF Rectangle => IF data#r THEN CD.Error[ec: other, explanation: "BidByNode: data#r"];
applRef: SXQuadTree.Rectangles => conflictWorld.ChangeRect[rect, data];
c: REF Constraint => conflictWorld.ChangeRect[rect, data];
ENDCASE => CD.Error[ec: programmingError, explanation: "BidByNode: invalid case"];
END; -- BidByNode
BidByConstr: CornerStitching.PerTileChangeProc =
-- PROC [plane: REF Tesselation, rect: CD.Rect, oldValue: REF ANY, data: REF ANY]
BEGIN
WITH oldValue
SELECT
FROM
a: ATOM => IF a#$Conflict THEN CD.Error[ec: other, explanation: "BidByConstr: a#$Conflict"];
r: REF Rectangle => IF new.first#r THEN CD.Error[ec: other, explanation: "BidByConstr: new.first#r"];
applRef: SXQuadTree.Rectangles =>
IF applRef#new THEN conflictWorld.ChangeRect[rect, data];
c:
REF Constraint => {
resolution: REF ANY = ResolveConstraints[c, data, SXAccess.sxTech.constraintResolutions[layer]];
IF resolution#c THEN conflictWorld.ChangeRect[rect, resolution];
};
ENDCASE => ERROR;
END; -- BidByConstr
BidByAppl: CornerStitching.PerTileChangeProc =
-- PROC [plane: REF Tesselation, rect: CD.Rect, oldValue: REF ANY, data: REF ANY]
BEGIN
WITH oldValue
SELECT
FROM
a: ATOM => IF a#$Conflict THEN CD.Error[ec: other, explanation: "BidByAppl: a#$Conflict"];
r:
REF Rectangle =>
IF NARROW[data, SXQuadTree.Rectangles].first#r THEN CD.Error[ec: other, explanation: "BidByAppl: data.first#r"];
applRef: SXQuadTree.Rectangles =>
IF data#applRef THEN conflictWorld.ChangeRect[rect, data];
c: REF Constraint => conflictWorld.ChangeRect[rect, data];
ENDCASE => ERROR;
END; -- BidByAppl
DescendCell:
PROC [appl:
CD.ApplicationPtr, 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
conflictWorld.FuncChangeRect[r, BidByNode, new.first]
};
constr:
REF Constraint => {
r: CD.Rect = MapRect[boxes.first.interestBound];
IF CDBasics.NonEmpty[r]
THEN
conflictWorld.FuncChangeRect[r, BidByConstr, constr]
};
subAppl:
CD.ApplicationPtr =>
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
conflictWorld.FuncChangeRect[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.ApplicationPtr = NARROW [new.first.nodeInformation];
descentDepth ← descentDepth + 1;
levelCount ← descentDepth/2; -- Descend until levelCount = 0
DescendCell[appl, appl.location, appl.orientation];
conflictWorld.FuncChangeRect[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 debug THEN TerminalIO.WriteChar['C];
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:
conflictWorld.FuncChangeRect[boxes.first.interestBound, OccupyByNode, boxes.first];
constr:
REF Constraint =>
conflictWorld.FuncChangeRect[boxes.first.interestBound, OccupyByConstr, constr];
appl:
CD.ApplicationPtr =>
conflictWorld.FuncChangeRect[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
ResolveConstraints:
PUBLIC
PROC [newConstraint:
REF Constraint, oldValue:
REF
ANY, resolution:
REF
SX.ConstraintResolution]
RETURNS [
REF
ANY] =
-- The consistency rules for SX.ConstraintResolution are non-trivial, the order of application should not be important—this is the key attribute.
BEGIN
WITH oldValue
SELECT
FROM
oldConstraint:
REF Constraint => {
result: REF Constraint = resolution[newConstraint.index][oldConstraint.index];
IF result=NIL THEN CD.Error[ec~ other, explanation~ "Invalid ConstraintResolution"];
RETURN [result]
}; -- end oldConstraint: REF CircuitConstraint
node:
REF Node => {
result: REF Constraint = resolution[newConstraint.index][SX.nodeIndex];
IF result=NIL THEN RETURN [node]
ELSE RETURN [result]
};
rect:
REF Rectangle => {
result: REF Constraint = resolution[newConstraint.index][SX.nodeIndex];
IF result=NIL THEN RETURN [rect]
ELSE 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