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 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 descentDepth: INT _ 1; OccupyByNode: CornerStitching.PerTileChangeProc = BEGIN 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 CornerStitching.ChangeRect [conflictWorld, rect, $Conflict]; s: SXQuadTree.Rectangles => 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]; ENDCASE => IF oldValue = NIL THEN CornerStitching.ChangeRect [conflictWorld, rect, data] ELSE CD.Error [ec: other, explanation: "Tesselation screwed up (alien tile)"] END; -- OccupyByNode OccupyByConstr: CornerStitching.PerTileChangeProc = BEGIN WITH oldValue SELECT FROM a: ATOM => IF a # $Conflict THEN CD.Error [ec: other, explanation: "Tesselation screwed up (alien tile)"]; 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 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 => IF oldValue = NIL THEN CornerStitching.ChangeRect [conflictWorld, rect, data] ELSE CD.Error [ec: other, explanation: "Tesselation screwed up (alien tile)"] END; -- OccupyByConstr OccupyByAppl: CornerStitching.PerTileChangeProc = BEGIN WITH oldValue SELECT FROM a: ATOM => IF a # $Conflict THEN CD.Error [ec: other, explanation: "Tesselation screwed up (alien tile)"]; 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 CornerStitching.ChangeRect [conflictWorld, rect, NIL]; Flatten [rect, s]; Flatten [rect, NARROW[data]] END; c: REF Constraint => Flatten [rect, NARROW[data]]; ENDCASE => IF oldValue = NIL THEN 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 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; IF SXAccess.stopFlag^ THEN ERROR ABORTED; IF mappedClip.y2>qt.midY AND qt.subTrees[north]#NIL THEN FlattenTree[qt.subTrees[north]]; IF mappedClip.y1qt.midX AND qt.subTrees[east]#NIL THEN FlattenTree[qt.subTrees[east]]; IF mappedClip.x1 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 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 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 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 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.y1qt.midX AND qt.subTrees[east]#NIL THEN DescendTree [qt.subTrees[east]]; IF mappedClip.x1 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]; ENDCASE => ERROR; ENDLOOP; FOR quad: SXQuadTree.AreaSplit IN SXQuadTree.AreaSplit DO ComputeConflicts [qt.subTrees[quad], conflictWorld, layer, cir] 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 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; 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. ¬SXConflictsImpl.mesa; Copyright c 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. Only bother with Level-order Conflict Resolution when the contended region is not too narrow. 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. 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. [plane: REF Tesselation, rect: CsRect, newValue: REF _ NIL] If there already is a conflict nothing needs to be done. Different rectangle g conflict. Old contents is subcell which needs to be flattened out: insert node and flatten subcell. Else no change. Initially the plane is empty, hence tile = NIL. Insert a new tile. [plane: REF Tesselation, rect: CsRect, newValue: REF _ NIL] If there already is a conflict nothing needs to be done. Resolve constraints against each other. Initially the plane is empty, hence tile=NIL. Initially the plane is empty, hence tile = NIL. Insert a new tile. [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. If there already is a conflict nothing needs to be done. Clear present occupant out of region. Add flattened rectangles from each cell to region. If subcell of same subcell: already done. Initially the plane is empty, hence tile = NIL. Insert a new tile. (local of FlattenCell, local of Flatten) Use quad-tree to filter what has to be flattened. 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. [plane: REF Tesselation, rect: CsRect, oldValue: REF, data: REF] [plane: REF Tesselation, rect: CsRect, oldValue: REF, data: REF] [plane: REF Tesselation, rect: CsRect, oldValue: REF, data: REF] (local of DescendCell, local of DescendOneLevel) (local of DescendCell, local of DescendOneLevel) main of DescendCell 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. 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: 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. Recursive because of quad-trees. The consistency rules for SX.ConstraintResolution are non-trivial, the order of application should not be importantthis is the key attribute. Check for side effects of returning NEW Constraint!!! Be careful if you have more than one constraint type with a specificCorrespondingNode Bowers September 4, 1985 4:13:08 pm PDT 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 ʉ˜šœ™Icodešœ Ïmœ=™HJ™3K™8J™5K™(K™2Icode2šœ(Ïnœžœ$Ïbœd™ë—šÏk ˜ Kš œ œK˜SKšœ  œ1˜?Kšœ  œ7˜EKšœ œ>˜SKšœ œY˜aKšœ  œ˜*Kšœ œ ˜#Kšœ  œ˜Kšœ  œ.˜>—šÐblœ œ ˜Lš œ œA˜KLš œ˜—Lš ˜Lšœ  œ œ ˜!Kšœ  œ˜'Kšœ œ œ ˜š žœ œ  œ( œ œ ˜kK™]Kšœ  œ1˜>Kš œ* œ)˜\Kš œÏc˜—šžœ œ œ œ% œ& œ œ œ  ˜ªKšœÜ™ÜIunit•StartOfExpansiona -- [plane: REF CornerStitching.Tesselation, rect: CD.Rect, oldValue: REF ANY, data: REF ANY] -- šœ œ˜šœ1™1JšÏe œƒ™Jš£œ¯™½Jš£œ;™PJš£œ†™Š—šŸ œ& ˜7Kšœ œ& œ œ™<š œ  œ ˜šœ œ œ ˜ Kš œG˜IK™8—šœ œ œ  ˜$Kšœœ ™Kšœ<˜<—šœ˜K™Yš œ œ ˜Kšœ7˜7Kšœ˜Kš ˜—Kš œ œN˜U—šœ œ˜š œ œd ˜nKšœ<˜<—K™—š œ˜ š œ  œ ˜KšœB™BKšœ6˜6—Kš œ œF˜M——Kš œ¢Ðce ˜—šŸœ& ˜9Kšœ œ& œ œ™<š œ  œ ˜šœ œ œ ˜ Kš œG˜IK™8—šœ œ ˜š œ œ% œ= ˜rKšœ<˜<——šœ ˜!Kšœ%˜%Kšœ˜Kš œ˜—šœ œ ˜K™'Kšœ  œ œO˜bKš  œ œ  œ œ$ œ<˜’š œ œ œ  ˜/Kšœ=˜=—Kš œ˜—š œ˜ Kšœ-™-š œ  œ ˜KšœB™BKšœ6˜6—Kš œ œF˜M——Kš œ¢¤˜—šŸ œ& ˜7Kšœ œ& œ œ™