<> <> <> <> <> <> <> <> 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; <<4 things are put into the conflictWorld they are:>> <> <> <> <> 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)"]; <> 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 <<[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)"]; <> 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 <<[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)"]; <> 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 <<(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; <> 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> 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.y1qt.midX AND qt.subTrees[east]#NIL THEN DescendTree [qt.subTrees[east]]; IF mappedClip.x1> 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 <
> <> 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 [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. <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <<>>