DIRECTORY CD USING [Error, ErrorCode, Instance, Number, Object, Orientation, Position, Rect], CDBasics USING [BaseOfRect, Extend, Intersect, Intersection, NonEmpty, ToRect], CDOrient USING [ComposeOrient, DeMapRect, MapRect, original, RectAt, rotate180, rotate270, rotate90], CornerStitching USING [Area, AreaEmpty, ChangeRect, CsRect, EastEdge, ENorthNeighbour, EnumerateArea, FreeTesselation, FuncChangeRect, ListArea, NEastNeighbour, NewTesselation, NorthEdge, PerTileChangeProc, PerTileProc, Region, SouthEdge, SWestNeighbour, Tesselation, Tile, TileAt, Value, WestEdge, WSouthNeighbour], PrincOpsUtils USING [], Properties USING [PropList], SX USING [AdjustNode, Circuit, CircuitNode, Constraint, ConstraintResolution, FindRootNode, GeometricRule, LogicalCell, LookupNode, MergeNode, nodeIndex, NormalizeCircuit, spaceIndex, SpinifexLayerIndex], SXAccess USING [design, stopFlag, sxTech], SXAccessInternal USING [GetSXData, PutError], SXLayers USING [], SXQuadTree USING [AreaSplit, Create, Dimension, Enumerate, PerRectProc, QuadTree, QuadTreeRoot, Rectangle, Rectangles], TerminalIO USING [WriteRope]; SXLayersImpl: CEDAR PROGRAM IMPORTS CD, CDBasics, CDOrient, CornerStitching, SX, SXAccess, SXAccessInternal, SXQuadTree, TerminalIO EXPORTS SXLayers = BEGIN TilePtr: TYPE = REF CornerStitching.Tile; Constraint: TYPE = SX.Constraint; Rectangle: TYPE = SXQuadTree.Rectangle; Node: TYPE = SX.CircuitNode; ConflictWorlds: TYPE = ARRAY SX.SpinifexLayerIndex OF REF CornerStitching.Tesselation; GeometryWorlds: TYPE = ARRAY SX.SpinifexLayerIndex OF REF CornerStitching.Tesselation; ConstraintQueue: TYPE = ARRAY SX.SpinifexLayerIndex OF LIST OF REF CornerStitching.Region _ ALL[NIL]; conflictWorlds: ConflictWorlds; geometryWorlds: GeometryWorlds; saveTesselations: BOOL _ FALSE; freeTesselations: BOOL _ FALSE; 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: 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: 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 BloatConflictsIntoAOIs: PROC [ cir: REF SX.Circuit, layer: SX.SpinifexLayerIndex, conflictWorld: REF CornerStitching.Tesselation] RETURNS [cleanedConflictWorld: REF CornerStitching.Tesselation] = BEGIN CopyBloated: CornerStitching.PerTileProc = BEGIN IF tile.Value = $Conflict THEN cleanedConflicts.ChangeRect [ rect: CDBasics.Extend[tile.Area, bloatValue], newValue: $AOI]; END; -- CopyBloated bloatValue: INT _ SXAccess.sxTech.layerInterestBloat[layer]; cleanedConflicts: REF CornerStitching.Tesselation _ CornerStitching.NewTesselation[]; [] _ conflictWorld.EnumerateArea [cir.spinifexLayers[layer].size, CopyBloated]; conflictWorld.FreeTesselation [FALSE]; cleanedConflictWorld _ cleanedConflicts; END; -- BloatConflictsIntoAOIs InstantiateAOIs: PROC [ cir: REF SX.Circuit, qt: REF SXQuadTree.QuadTree, cellBBox: CD.Rect, flatLoc: CD.Position _ [0, 0], flatOrient: CD.Orientation _ CDOrient.original, appl: CD.Instance _ NIL, nameQualifier: LIST OF CD.Instance _ NIL, layer: SX.SpinifexLayerIndex, conflictWorld: REF CornerStitching.Tesselation, geometryWorld: REF CornerStitching.Tesselation, constraintQueue: ConstraintQueue] RETURNS [newConstraintQueue: ConstraintQueue] = BEGIN InstantiateTree: PROC [qt: REF SXQuadTree.QuadTree, qtBranchBox: CD.Rect] = BEGIN EnqueueConstraintRegion: PROC [cc: REF SX.Constraint, r: CornerStitching.CsRect] = BEGIN constraintQueue[layer] _ CONS [ NEW [CornerStitching.Region _ [rect: r, value: cc]], constraintQueue[layer]] END; -- EnqueueConstraintRegion branchBox: CD.Rect = CDOrient.MapRect [itemInCell: qtBranchBox, cellSize: (IF appl=NIL THEN [0, 0] ELSE appl.ob.size), cellInstOrient: flatOrient, cellInstPos: flatLoc]; IF conflictWorld.AreaEmpty [branchBox] THEN RETURN; FOR boxes: SXQuadTree.Rectangles _ qt.boxes, boxes.rest WHILE boxes#NIL DO mappedDim: CD.Rect = CDOrient.MapRect [ itemInCell: SXQuadTree.Dimension[boxes.first], cellSize: (IF appl=NIL THEN [0, 0] ELSE appl.ob.size), cellInstOrient: flatOrient, cellInstPos: flatLoc]; IF NOT conflictWorld.AreaEmpty[mappedDim] THEN { WITH boxes.first.nodeInformation SELECT FROM subAppl: CD.Instance => { cellQt: REF SXQuadTree.QuadTree; subcellBBox: CD.Rect; rect: CD.Rect = CDOrient.RectAt [pos: subAppl.location, size: subAppl.ob.size, orient: subAppl.orientation]; mappedRect: CD.Rect = CDOrient.MapRect [itemInCell: rect, cellSize: (IF appl=NIL THEN [0, 0] ELSE appl.ob.size), cellInstOrient: flatOrient, cellInstPos: flatLoc]; orient: CD.Orientation = CDOrient.ComposeOrient [ itemOrientInCell: subAppl.orientation, cellOrientInWorld: flatOrient]; [size: subcellBBox, geometry: cellQt] _ SXAccessInternal.GetSXData[subAppl.ob].circuit.spinifexLayers[layer]; IF cellQt = NIL THEN LOOP; constraintQueue _ InstantiateAOIs [qt: cellQt, cellBBox: subcellBBox, flatLoc: CDBasics.BaseOfRect [mappedRect], flatOrient: orient, appl: subAppl, 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 => { name: REF SX.CircuitNode = IF (nameQualifier=NIL) THEN cNode ELSE cir.FindRootNode [subcircuitNode: cNode, qualifier: nameQualifier, insertIfNotInCircuit: TRUE].node; occupants: LIST OF REF CornerStitching.Region _ NARROW[geometryWorld.ListArea[mappedDim] ]; newList: LIST OF REF SX.CircuitNode _ LIST[name]; geometryWorld.ChangeRect [rect: mappedDim, newValue: newList]; WHILE occupants # NIL DO IF NOT conflictWorld.AreaEmpty[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 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, newValue: replaceList] }; ENDCASE => ERROR; occupants _ occupants.rest; ENDLOOP; }; -- end rectangle is a node cc: REF SX.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 InstantiateTree[qt, cellBBox]; newConstraintQueue _ constraintQueue END; -- InstantiateAOIs AnalyzeNodesInAOIs: PROC [ cir: REF SX.Circuit, layer: SX.SpinifexLayerIndex, geometryWorld: REF CornerStitching.Tesselation] = BEGIN MergeNodeTiles: CornerStitching.PerTileProc = BEGIN CountEdge: PROC [nl1, nl2: LIST OF REF SX.CircuitNode] RETURNS [INT] = BEGIN 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 IF SXAccess.stopFlag^ THEN ERROR ABORTED; WITH tile.Value SELECT FROM cnList: LIST OF REF SX.CircuitNode => { list: LIST OF REF SX.CircuitNode _ cnList.rest; eastBound: INT = tile.EastEdge; northBound: INT = tile.NorthEdge; westBound: INT = tile.WestEdge; southBound: INT = tile.SouthEdge; 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]; SX.AdjustNode [node: n1, layer: layer, area: -((r.x2 - r.x1)*(r.y2 - r.y1)), perim: 0]; extraNodes _ extraNodes+1; list _ list.rest; ENDLOOP; FOR tileSouth: TilePtr _ tile.WSouthNeighbour, tileSouth.NEastNeighbour WHILE tileSouth.WestEdge < 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.EastEdge] - MAX[westBound, tileSouth.WestEdge]))] }; constraint: REF SX.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.EastEdge] - MAX[westBound, tileSouth.WestEdge]))] ENDLOOP; -- end FOR tileSouth FOR tileWest: TilePtr _ tile.SWestNeighbour, tileWest.ENorthNeighbour WHILE tileWest.SouthEdge < 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.NorthEdge] - MAX[southBound, tileWest.SouthEdge]))] }; constraint: REF SX.Constraint => NULL; -- Ignore ENDCASE => ERROR ELSE IF extraNodes > 0 THEN SX.AdjustNode [node: n1, layer: layer, area: 0, perim: -(extraNodes * (MIN[northBound,tileWest.NorthEdge] - MAX[southBound,tileWest.SouthEdge]))] ENDLOOP; -- tileWest FOR tileNorth: TilePtr _ tile.ENorthNeighbour, tileNorth.SWestNeighbour WHILE tileNorth.EastEdge > westBound DO IF (tileNorth.Value = NIL) AND (extraNodes > 0) THEN SX.AdjustNode [node: n1, layer: layer, area: 0, perim: -(extraNodes * (MIN[eastBound, tileNorth.EastEdge] - MAX[westBound, tileNorth.WestEdge]))] ENDLOOP; -- tileNorth FOR tileEast: TilePtr _ tile.NEastNeighbour, tileEast.WSouthNeighbour WHILE tileEast.NorthEdge > southBound DO IF (tileEast.Value=NIL) AND (extraNodes > 0) THEN SX.AdjustNode [node: n1, layer: layer, area: 0, perim: -(extraNodes * (MIN[northBound, tileEast.NorthEdge] - MAX[southBound, tileEast.SouthEdge]))] ENDLOOP; -- tileEast }; ENDCASE => ERROR END; -- MergeNodeTiles [] _ geometryWorld.EnumerateArea [rect: cir.spinifexLayers[layer].size, perTile: MergeNodeTiles]; END; -- AnalyzeNodesInAOIs MixRec: TYPE = RECORD [newConstraint: REF SX.Constraint, rect: CD.Rect, resolution: REF SX.ConstraintResolution, tilesToPaint: LIST OF REF CornerStitching.Region]; CheckRec: TYPE = RECORD [conflictWorld: REF CornerStitching.Tesselation, geometryWorld: REF CornerStitching.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: REF CornerStitching.Tesselation, conflictWorld: REF CornerStitching.Tesselation] = BEGIN mixRef: REF MixRec = NEW [MixRec]; -- used to transfer parameters to MixConstraints checkRef: REF CheckRec = NEW[CheckRec]; -- used to transfer parameters to CheckTile FOR newCc: LIST OF REF CornerStitching.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, perTile: MixConstraints, skipValue: $Nothing, data: mixRef]; FOR tilesToPaint: LIST OF REF CornerStitching.Region _ mixRef.tilesToPaint, tilesToPaint.rest WHILE tilesToPaint#NIL DO geometryWorld.ChangeRect [rect: tilesToPaint.first.rect, newValue: tilesToPaint.first.value] ENDLOOP; ENDLOOP; checkRef^ _ [conflictWorld: conflictWorld, geometryWorld: geometryWorld, cell: cell, cir: cir, rules: SXAccess.sxTech.rules[layer]]; [] _ geometryWorld.EnumerateArea [rect: cir.spinifexLayers[layer].size, perTile: CheckTile, skipValue: $Nothing, data: checkRef] END; -- DesignRuleCheckAOIs MixConstraints: CornerStitching.PerTileProc = BEGIN 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 [CornerStitching.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 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 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 => { subcir: REF SX.Circuit = SXAccessInternal.GetSXData[a.ob].circuit; subR: CD.Rect = CDOrient.DeMapRect[ itemInWorld: rect, cellSize: a.ob.size, cellInstOrient: a.orientation, cellInstPos: a.location ]; FindNodeInner[subcir, subR, CONS[a, aChain]]; }; ENDCASE; END; -- SearchForNode 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: CornerStitching.PerTileProc = BEGIN 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 FindNodeAtCorner: PROC [n: REF ANY] RETURNS [REF ANY] = BEGIN WITH n SELECT FROM cn: REF SX.CircuitNode => RETURN [cn]; cc: REF SX.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 SX.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: CornerStitching.PerTileProc = BEGIN CheckValue[tile.Value, tile.Area] END; CheckValue: PROC [value: REF ANY, area: CD.Rect] = BEGIN 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 SX.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: value # NIL"] }; IF notReportedYet AND conflictWorld.AreaEmpty[ rect: CDOrient.MapRect[ itemInCell: [x1: -delta, y1: -delta, x2: len, y2: len], cellSize: [0, 0], cellInstOrient: orient, cellInstPos: pos ], skipValue: $AOI] THEN { -- FOUND AN ERROR rect: CD.Rect = CDOrient.MapRect [ itemInCell: [x1: 0, y1: 0, x2: rule.extent, y2: rule.extent], cellSize: [0, 0], cellInstOrient: orient, cellInstPos: pos]; SXAccessInternal.PutError [ob: handle.cell.cellObj, r: rect, message: rule.message]; notReportedYet _ FALSE } END; -- CheckValue notReportedYet: BOOLEAN _ TRUE; len: INT = rule.extent; delta: INT = 1; IF len = 0 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: CDOrient.MapRect[itemInCell: [x1: -delta, y1: 0, x2: len, y2: len], cellSize: [0, 0], cellInstOrient: orient, cellInstPos: pos ], perTile: CheckTileValue, skipValue: $Nix ]; [] _ handle.geometryWorld.EnumerateArea[ rect: CDOrient.MapRect[itemInCell: [x1: 0, y1: -delta, x2: len, y2: 0], cellSize: [0, 0], cellInstOrient: orient, cellInstPos: pos ], perTile: CheckTileValue, skipValue: $Nix ]; }; concave => { [] _ handle.geometryWorld.EnumerateArea[ rect: CDOrient.MapRect[itemInCell: [x1: 0, y1: 0, x2: len, y2: len], cellSize: [0, 0], cellInstOrient: orient, cellInstPos: pos ], perTile: CheckTileValue, skipValue: $Nix ]; }; ENDCASE } END; -- CheckArea or0: CD.Orientation = CDOrient.original; or90: CD.Orientation = CDOrient.rotate90; or180: CD.Orientation = CDOrient.rotate180; or270: CD.Orientation = CDOrient.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; 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 SX.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 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 handle: REF CheckRec = NARROW[data]; conflictWorld: REF CornerStitching.Tesselation = handle.conflictWorld; tileBound: CD.Rect = tile.Area; IF conflictWorld.TileAt[[x: tileBound.x1, y: tileBound.y1]].Value = $AOI THEN { IF tile.SWestNeighbour.SouthEdge = tileBound.y1 THEN { IF tile.WSouthNeighbour.WestEdge = 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.SWestNeighbour.Value THEN CD.Error[ec: other, explanation: "CheckTile: violated Max horz rule"]; DesignRuleCheckCorner[ [ne: tile.Value, nw: tile.SWestNeighbour.Value, sw: tile.WSouthNeighbour.Value, se: tile.WSouthNeighbour.Value], [tileBound.x1, tileBound.y1] ]; } } ELSE { -- tile.WSouthNeighbour.WestEdge = tileBound.x1 IMPLICITLY IF tile.Value = tile.WSouthNeighbour.Value THEN NULL -- No corner really ELSE { DesignRuleCheckCorner[ [ne: tile.Value, nw: tile.SWestNeighbour.Value, sw: tile.SWestNeighbour.Value, se: tile.WSouthNeighbour.Value], [tileBound.x1, tileBound.y1] ]; } } }; IF conflictWorld.TileAt[[x: tileBound.x2, y: tileBound.y2]].Value = $AOI THEN { IF tile.NEastNeighbour.NorthEdge = tileBound.y2 THEN { IF tile.ENorthNeighbour.EastEdge = tileBound.x2 THEN { neQTile: TilePtr _ tile.ENorthNeighbour.NEastNeighbour; WHILE neQTile.SouthEdge > tileBound.y2 DO neQTile _ neQTile.WSouthNeighbour; ENDLOOP; DesignRuleCheckCorner[ [ne: neQTile.Value, nw: tile.ENorthNeighbour.Value, sw: tile.Value, se: tile.NEastNeighbour.Value], [tileBound.x2, tileBound.y2] ]; } ELSE { IF tile.Value = tile.NEastNeighbour.Value THEN CD.Error[ec: other, explanation: "CheckTile: violated Max horz rule NEast"]; DesignRuleCheckCorner[ [ne: tile.ENorthNeighbour.Value, nw: tile.ENorthNeighbour.Value, sw: tile.Value, se: tile.NEastNeighbour.Value], [tileBound.x2, tileBound.y2] ]; } } ELSE { -- tile.ENorthNeighbour.EastEdge = tileBound.x2 IMPLICITLY IF tile.Value = tile.ENorthNeighbour.Value THEN NULL -- No corner really ELSE { DesignRuleCheckCorner[ [ne: tile.NEastNeighbour.Value, nw: tile.ENorthNeighbour.Value, sw: tile.Value, se: tile.NEastNeighbour.Value], [tileBound.x2, tileBound.y2] ]; } } } END; -- CheckTile AnalyzeGeometry: PUBLIC PROC [cell: REF SX.LogicalCell] = BEGIN cir: REF SX.Circuit = cell.circuit; constraintQueue: ConstraintQueue; IF freeTesselations THEN FreeTesselations[circuit: cir]; FOR layer: SX.SpinifexLayerIndex IN [0..SXAccess.sxTech.numSpinifexLayers) DO conflictWorld: REF CornerStitching.Tesselation _ conflictWorlds[layer] _ CornerStitching.NewTesselation[]; geometryWorld: REF CornerStitching.Tesselation _ geometryWorlds[layer] _ CornerStitching.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]; conflictWorld _ conflictWorlds[layer] _ BloatConflictsIntoAOIs [cir, layer, conflictWorld]; constraintQueue _ InstantiateAOIs [cir: cir, qt: cir.spinifexLayers[layer].geometry, cellBBox: cir.spinifexLayers[layer].size, layer: layer, conflictWorld: conflictWorld, geometryWorld: geometryWorld, constraintQueue: constraintQueue]; AnalyzeNodesInAOIs [cir, layer, geometryWorld]; ENDLOOP; -- end of FOR "layer: SX.SpinifexLayerIndex IN [0..SXAccess.sxTech.numSpinifexLayers) DO" TerminalIO.WriteRope [". "]; FOR layer: SX.SpinifexLayerIndex IN [0..SXAccess.sxTech.numSpinifexLayers) DO geometryWorld: REF CornerStitching.Tesselation _ geometryWorlds[layer]; IF SXAccess.stopFlag^ THEN ERROR ABORTED; FOR tiles: LIST OF REF CornerStitching.Region _ NARROW[geometryWorld.ListArea[rect: cir.spinifexLayers[layer].size]], tiles.rest WHILE tiles#NIL DO geometryWorld.ChangeRect [rect: tiles.first.rect, newValue: SX.LookupNode[NARROW[tiles.first.value, LIST OF REF SX.CircuitNode].first]] ENDLOOP; ENDLOOP; SX.NormalizeCircuit [cir]; TerminalIO.WriteRope [". "]; FOR layer: SX.SpinifexLayerIndex IN [0..SXAccess.sxTech.numSpinifexLayers) DO conflictWorld: REF CornerStitching.Tesselation _ conflictWorlds[layer]; geometryWorld: REF CornerStitching.Tesselation _ geometryWorlds[layer]; DesignRuleCheckAOIs [cir, cell, constraintQueue, layer, geometryWorld, conflictWorld]; ENDLOOP; TerminalIO.WriteRope [". "]; IF saveTesselations THEN freeTesselations _ TRUE ELSE FreeTesselations [circuit: cir]; END; -- AnalyzeGeometry SaveTesselations: PUBLIC PROC [save: BOOL _ FALSE] = BEGIN saveTesselations _ save END; GetTesselation: PUBLIC PROC [conflicts: BOOL _ TRUE, layer: SX.SpinifexLayerIndex] RETURNS [REF CornerStitching.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 conflictWorlds[layer].FreeTesselation[FALSE]; geometryWorlds[layer].FreeTesselation[FALSE]; ENDLOOP; TerminalIO.WriteRope [". "]; freeTesselations _ FALSE END; END. <�SXLayersImpl.mesa Copyright c 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 Bowers, September 6, 1985 11:50:22 am PDT Last edited by: gbb March 19, 1986 5:18:41 pm PST Global Types and Variables The conflict worlds are used to find the regions where interactions occour. The geometry worlds contain the flattened regions where conflicts occour. The following two data structures are global for maintenance purposes. The conflict worlds are used to find the regions where interactions occour. The geometry worlds contain the flattened regions where conflicts occour. Maintenance aids Conflict Resolution 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 Procedures For First Per Layer Loop [BloatConflictsIntoAOIs (AOI = Area Of Interest)] 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. [tile: TilePtr, data: REF ANY] RETURNS [REF ANY] Depth first instantiation of those regions of the hierarchy that were found to be interesting. InstantiateTree nameQualifier is not NIL when this node comes from a subcell of the cell currently being processed: -- check not already on list. Main of InstantiateAOIs The nodes are analysed. Problem: parasitics. The constraints are put in and resolved (additional complexity for electrical conductivity). [tile: TilePtr, 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. There is an edge for every SX.CircuitNode not shared by the two lists. MergeNodeTiles: Process merging and area changes in the interior of the tile. Area adjustment. 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. AnalyzeNodesInAOIs. Procedures For Third Per Layer Loop Corner based checking. The tesselation is enumerated, etc. Fine point: inside/outside (concave corners). Tile types: Space (0), Current (1), SX.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. CornerStitching.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. First add the constraint regions to the geometry. examine every tile --called from DesignRuleCheckAOIs only --[tile: TilePtr, data: REF ANY] RETURNS [REF ANY] logically local to CheckTile [r: REF SXQuadTree.Rectangle, data: REF ANY] -- (local of FindNodeInner, local of FindNode, local of DesignRuleCheckAOIs, local of AnalyzeGeometry) --Compose Clip and recurse FindNodeInner [tile: TilePtr, data: REF ANY] RETURNS [REF ANY] -- called from DesignRuleCheckAOIs only --PROC [tile: TilePtr, data: REF ANY] RETURNS [REF ANY] Each rule has two boolean vectors: trigger1 identifies whether it is really a corner and gives the orientation. trigger2 gives the checking rectangle. CornerStitching.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. Check it is really an error. (Kind of funny sort of empty! What we mean is empty of non-$AOI tiles) -- Optimize purely local checks. IF notReportedYet THEN DesignRuleCheckCorner 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 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. SW corner -- Get the quadrants at the SW corner and call DesignRuleCheckCorner -- Get the quadrants at the SW corner and call DesignRuleCheckCorner NE corner -- 4 way corner, damn it -- Get the quadrants at the NE corner and call DesignRuleCheckCorner -- Get the quadrants at the NE corner and call DesignRuleCheckCorner Main Procedure Process each of the analysis layers. 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. 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]; 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. Now the nodes are analysed. Problem: parasitics. The constraints are put in and resolved (additional complexity for electrical conductivity). 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). Third per layer loop. Corner based checking. The tesselation is enumerated, etc. Fine point: inside/outside (concave corners). Maintenance Aids 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 ��,��code��K�� m�7�BIhead��K�-K�8J�4K�)K�1�unit��k � K��K�SK�� A�OK�� W�eK��K��K��K��K�� *K��-K�� K��g�wK�� code2��bl��M��'��4�gM��M��M�� )N��!K��'K�� VK�K��VK�I�K��eM�F��K�K��K�I�M��K��K��L��n��(��kK�]K��1�>K��*��)�\K��c��%��&��K��M�StartOfExpansiona -- [plane: REF CornerStitching.Tesselation, rect: CD.Rect, oldValue: REF ANY, data: REF ANY] -- ��1�1J��e ��J��J��;�PJ��b�&��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��&��B��M��$��3��5��JK��U��B��$��0��,�� K�� K�� K��d�lK��7��B��K��n�xM��n�nK�� K��@�w��K�� K��c�cK��Z��K� ��%�[K�� 1K��>�>�� /��9��&� � ��6K� ��*K� � �� (��K�K��K�K��K��"K��K��K�KK��K��K��K��K��K��6�@K��&�7�K��K��1�=�� #�#K��K�K�� #�#K��K�K��"�"K��K�K��"�"K��K�K��K��K��J�J��K��K��$�$K�� $�� J��ck��3J��2�2J��,�,J�� LJ��F�F�� JJ�� ?J��#��J��3J�� J��J��0J��J�� M��:�@J�� M��J��)��'J�=J��/J��J��!J��J��!J��J��J��/�6��J��4J�� "�1J�J��U�WJ�J��J��LJ�H��E�� o��<� � ��,K�� ;K�� "�1K��Y��"��"��K��K�� 1K��K��G��"��"��K��C��!��n��:��+J�� 2J��!�!�K��X��#��#��J��J�� 1J��K��E��"��"��J��ew��E�� o��4K��E��"��"��J�� C��!��n��1K��E��#��#��K��J��J��J��M��K��a�aJ��L�#M��%��K�� -��%�� :��%��.�� "J�LJ�&�J��K�� 0�SK�� +�SM�2� ��=��eK��v��K��q�q� ��A��wK��\�\K��K��M�K��K��J�� 3J��&�&J��3�3J�� "J��'��d��K��x��J�� 0��mJ��J��J�� (�� J�� J�� J�� a�� -J��/��0J��c�c��"��'��HJ��J�� J��<�