<> <> <> <> DIRECTORY CD USING [ObPtr, Rect, DesignPosition, Position, Orientation, ApplicationPtr, ApplicationList, Number, Level, lambda, DrawRef, DrawProc, DrawRectProc, LevelKey, NewNullDeviceDrawRef], CDDirectory USING [Name], CDInline USING [RectAt, Inside, Surround, NonEmpty, Extend, SizeOfRect, Intersect, Intersection], CDOrient USING [MapRect, original], CDObjectProcs USING [FetchFurther], CDProperties USING [GetPropFromObject, PutPropOnObject, PutPropOnApplication, GetPropFromApplication], TerminalIO USING [WriteRope], CDApplications USING [NewApplicationI], CDCells USING [IncludeApplication, RemoveApplication], CDRects USING [CreateBareRect], Atom USING [PropList, PutPropOnList, GetPropFromList, GetPName], RefTab USING [Ref, Create, Fetch, Store, Pairs, EachPairAction], SafeStorage USING [GetSystemZone], Rope USING [ROPE, Equal, Cat], SpinifexAtoms USING [ spinifex, spinifexErrorRect, errorClient, SignalName, Rect, SaveRect], SpinifexCircuit ; SpinifexCircuitImpl: CEDAR PROGRAM IMPORTS CD, CDDirectory, CDInline, CDOrient, CDObjectProcs, CDProperties, TerminalIO, Atom, RefTab, SafeStorage, Rope, SpinifexAtoms, CDApplications, CDCells, CDRects EXPORTS SpinifexCircuit ~ BEGIN AZ: PUBLIC ZONE _ SafeStorage.GetSystemZone[]; <<-- TYPES from Interface.>> LogicalCell: TYPE ~ SpinifexCircuit.LogicalCell; Circuit: TYPE ~ SpinifexCircuit.Circuit; QuadTreeRoot: TYPE ~ SpinifexCircuit.QuadTreeRoot; QuadTree: TYPE ~ SpinifexCircuit.QuadTree; AreaSplit: TYPE ~ SpinifexCircuit.AreaSplit; Rectangle: TYPE ~ SpinifexCircuit.Rectangle; RectDelta: TYPE ~ SpinifexCircuit.RectDelta; CircuitNode: TYPE ~ SpinifexCircuit.CircuitNode; AreaPerimRec: TYPE ~ SpinifexCircuit.AreaPerimRec; CircuitConstraint: TYPE ~ SpinifexCircuit.CircuitConstraint; NodeLinkage: TYPE ~ SpinifexCircuit.NodeLinkage; AttachedNode: TYPE ~ SpinifexCircuit.AttachedNode; MergeRec: TYPE ~ SpinifexCircuit.MergeRec; MergeRecList: TYPE ~ SpinifexCircuit.MergeRecList; SpinifexLayerIndex: TYPE ~ SpinifexCircuit.SpinifexLayerIndex; TechHandle: TYPE ~ SpinifexCircuit.TechHandle; MapRec: TYPE ~ SpinifexCircuit.MapRec; <<-- Implementation.>> ErrorKey: TYPE ~ RECORD [ ob: CD.ObPtr, cir: REF Circuit ]; PaintErrorRect: PUBLIC PROCEDURE [cell: REF LogicalCell, errorBox: CD.Rect, message: Rope.ROPE] ~ { <<-- We clip errorBox that a cells co-ordinate system does not get translated between when we cache geometry information in the child and when we try to use the cached information in the analysis of a antecedent. The problem we are avoiding is that if a cells bounding box changes in CDCells.IncludeApplication the cells internal applications are translated to account for this, and thus become inconsistent with Spinifexes geometry cache.>> errorCell: CD.ObPtr; errorKey: REF ANY; IF cell.errorContext # NIL THEN { subcircuitKey: REF ErrorKey _ NEW[ ErrorKey _ [cell.cellObj, cell.circuit] ]; subcircuit: REF Circuit ~ cell.circuit; errorClientList: LIST OF CD.ObPtr _ NARROW[ CDProperties.GetPropFromObject[from~ cell.errorContext, prop~ SpinifexAtoms.errorClient]]; errorKey _ subcircuitKey; errorCell _ cell.errorContext; errorBox _ CDOrient.MapRect[ itemInCell~ errorBox, cellSize~ cell.cellObj.size, cellInstOrient~cell.relativeOrient, cellInstPos~cell.relativePos]; message _ message.Cat[" (in sub-component \"", CDDirectory.Name[cell.cellObj], "\")"]; FOR ecl: LIST OF CD.ObPtr _ errorClientList, ecl.rest WHILE ecl # NIL DO IF ecl.first = cell.cellObj THEN EXIT; REPEAT FINISHED => { errorClientList _ CONS[cell.cellObj, errorClientList]; CDProperties.PutPropOnObject[onto~ cell.errorContext, prop~ SpinifexAtoms.errorClient, val~ errorClientList]; } ENDLOOP; } ELSE { errorCell _ cell.cellObj; errorKey _ SpinifexAtoms.spinifexErrorRect }; errorBox _ CDInline.Intersection[ CDInline.Extend[errorBox, (CD.lambda+1)/2], CDInline.RectAt[ pos~ [0,0], size~ errorCell.size]]; IF CDInline.NonEmpty[errorBox] THEN { appl: CD.ApplicationPtr ~ CDApplications.NewApplicationI[ ob~ CDRects.CreateBareRect[ CDInline.SizeOfRect[ errorBox], cell.circuit.technologyHandle.errorLevel], location~ [errorBox.x1, errorBox.y1], orientation~ CDOrient.original]; CDProperties.PutPropOnApplication[onto~ appl, prop~ SpinifexAtoms.SignalName, val~ message]; CDProperties.PutPropOnApplication[onto~ appl, prop~ SpinifexAtoms.spinifexErrorRect, val~ errorKey]; [] _ CDCells.IncludeApplication[ design~cell.design, cell~errorCell, aptr~appl]; }; cell.errorCount _ cell.errorCount.SUCC; TerminalIO.WriteRope["|"] }; IllegalConstruct: PUBLIC ERROR [rect: CD.Rect, reason: Rope.ROPE] ~ CODE; IllegalLevel: PUBLIC ERROR [rect: CD.Rect, lev: CD.Level] ~ CODE; ContainsIllegal: SIGNAL [rect: CD.Rect, reason: Rope.ROPE] ~ CODE; DataForChildren: TYPE ~ RECORD [ cir: REF Circuit, oldErrors: LIST OF CD.ApplicationPtr ]; TranslateChild: CD.DrawProc -- [aptr: ApplicationPtr, pos: DesignPosition, orient: Orientation, pr: REF DrawInformation] -- ~ { IF aptr.ob.p.objectType = SpinifexAtoms.Rect OR aptr.ob.p.objectType = SpinifexAtoms.SaveRect THEN { <<-- This object is a simple rectangle.>> data: REF DataForChildren ~ NARROW[pr.devicePrivate]; IF aptr.ob.level = data.cir.technologyHandle.errorLevel THEN { key: REF ANY ~ CDProperties.GetPropFromApplication[from~ aptr, prop~SpinifexAtoms.spinifexErrorRect]; IF key # NIL THEN WITH key SELECT FROM key: REF ErrorKey => { IF key.cir # CDProperties.GetPropFromObject[ from~key.ob, prop~SpinifexAtoms.spinifex] THEN data.oldErrors _ AZ.CONS[ aptr, data.oldErrors]; }; a: ATOM => { IF a # SpinifexAtoms.spinifexErrorRect THEN ERROR; data.oldErrors _ AZ.CONS[ aptr, data.oldErrors] }; ENDCASE => ERROR; RETURN }; { box: CD.Rect ~ CDOrient.MapRect[ itemInCell~ CDInline.RectAt[pos~ [0,0], size~ aptr.ob.size], cellSize~ aptr.ob.size, cellInstOrient~ orient, cellInstPos~ pos]; node: REF CircuitNode ~ AddRect[ cir~ data.cir, lev~ aptr.ob.level, dim~ box ! IllegalLevel => { SIGNAL ContainsIllegal [rect, Rope.Cat["Material on level ", Atom.GetPName[CD.LevelKey[lev]], " may not appear as an isolated rectangle"]]; GOTO BadRect } ]; IF node # NIL THEN CopyNodeProperties[ data.cir, node, aptr.properties]; EXITS BadRect => NULL }; RETURN }; WITH CDProperties.GetPropFromObject[ from~aptr.ob, prop~SpinifexAtoms.spinifex] SELECT FROM subcircuit: REF Circuit => { <<-- This object is a logical subcircuit.>> newAppl: CD.ApplicationPtr ~ CDApplications.NewApplicationI[ ob~ aptr.ob, location~ pos, orientation~ orient]; data: REF DataForChildren ~ NARROW[pr.devicePrivate]; cir: REF Circuit ~ data.cir; numLayers: SpinifexLayerIndex ~ data.cir.technologyHandle.numSpinifexLayers; FOR i: SpinifexLayerIndex IN [0..numLayers) DO IF subcircuit.spinifexLayers[i].geometry = NIL THEN LOOP; IF cir.subcircuits = NIL OR cir.subcircuits.first # newAppl THEN -- It is the 1st non-empty geom-layer. cir.subcircuits _ AZ.CONS[newAppl, cir.subcircuits]; [] _ AddBox[ cir~cir, appl~newAppl, pos~ pos, orient~ orient, spinifexLayer~i, dim~subcircuit.spinifexLayers[i].size, value~newAppl] ENDLOOP; cir.linkageCount.inChildren _ cir.linkageCount.inChildren + subcircuit.linkageCount.inSelf + subcircuit.linkageCount.inChildren; }; ENDCASE => { convProc: REF ANY ~ CDObjectProcs.FetchFurther[ p~aptr.ob.p, key~SpinifexAtoms.spinifex]; IF convProc # NIL THEN { <<-- This object has special layout analysis code.>> data: REF DataForChildren ~ NARROW[pr.devicePrivate]; NARROW[ convProc, REF SpinifexCircuit.ConversionProc]^[ aptr, pos, orient, data.cir ! IllegalConstruct => { SIGNAL ContainsIllegal [CDOrient.MapRect[ itemInCell~rect, cellSize~aptr.ob.size, cellInstOrient~orient, cellInstPos~pos], reason]; CONTINUE } ] } ELSE { <<-- Use DrawProc to Process geometry in the mystery object.>> aptr.ob.p.drawMe[aptr, pos, orient, pr] } } }; TranslateRect: CD.DrawRectProc -- [r: DesignRect, l: Level, pr: DrawRef] -- ~ { data: REF DataForChildren ~ NARROW[pr.devicePrivate]; IF ~CDInline.NonEmpty[r] THEN RETURN; IF l # data.cir.technologyHandle.errorLevel THEN [] _ AddRect[ cir~data.cir, lev~l, dim~r ! IllegalLevel => { SIGNAL ContainsIllegal [rect, Rope.Cat["Rectangle on level ", Atom.GetPName[CD.LevelKey[lev]], " cannot be analyzed in this context"] ]; CONTINUE } ]; }; TranslateGeometry: PUBLIC PROCEDURE [cell: REF LogicalCell] ~ { cir: REF Circuit ~ cell.circuit; dataRef: REF DataForChildren _ NEW[DataForChildren]; dr: CD.DrawRef ~ CD.NewNullDeviceDrawRef[NIL]; fakeAppl: CD.ApplicationPtr ~ CDApplications.NewApplicationI[ ob~ cell.cellObj, location~ [0,0], orientation~ CDOrient.original]; cellSize: CD.DesignPosition _ cell.cellObj.size; dr.drawRect _ TranslateRect; dr.saveRect _ TranslateRect; dr.drawChild _ TranslateChild; dr.devicePrivate _ dataRef; dataRef.cir _ cir; dataRef.oldErrors _ NIL; cell.cellObj.p.drawMe[fakeAppl, [0,0], CDOrient.original, dr ! ContainsIllegal => { PaintErrorRect[ cell~ cell, errorBox~ rect, message~ reason ]; RESUME } ]; FOR link: LIST OF REF NodeLinkage _ cir.linkages, link.rest WHILE link # NIL DO cir.linkageCount.inSelf _ cir.linkageCount.inSelf.SUCC ENDLOOP; FOR applList: LIST OF CD.ApplicationPtr _ dataRef.oldErrors, applList.rest WHILE applList # NIL DO IF CDCells.RemoveApplication[ design~ cell.design, cell~ cell.cellObj, aptr~ applList.first].removed = NIL THEN ERROR; ENDLOOP; IF cellSize # cell.cellObj.size THEN { TerminalIO.WriteRope[" Removal of old Spinifex Errors from cell caused cell's boundary to change, Spinifex was unable to continue. Please try to run Spinifex again."]; ERROR ABORTED }; <<-- Now we must sort it.>> FOR layer: SpinifexLayerIndex IN [0..cir.technologyHandle.numSpinifexLayers) DO SortBoxes: PROCEDURE [cir: REF Circuit, layer: SpinifexLayerIndex] ~ { Quadrant: TYPE ~ {ne,nw,sw,se}; SubDivision: TYPE ~ {fitsNorth, fitsSouth, fitsEast, fitsWest, noFit }; boxList: LIST OF REF Rectangle; boundary: CD.Rect; qtRoot: REF QuadTree; CanSubDivide: PROCEDURE [qNE, qSW: Quadrant] RETURNS [SubDivision] ~ { <<-- This is trickier than it seems.>> <<-- Unpleasant cases arise when degenerate boxes lie on the quadrant dividing axes. Accordingly quadNE & quadSW have slightly different semantics. quadNE is made to favour the south-west, and quadSW to favour the north-east. The choiceMatrix is encoding to interpret apparent contradictions such as quadNE in nw and quadSW in ne as indicating a degenrate box lying on the vertical splitting axis. Such a box is contained by both the ne & nw subtree.>> choiceMatrix: ARRAY Quadrant OF ARRAY Quadrant OF SubDivision ~ [ ne~[ ne~fitsNorth, nw~fitsNorth, sw~noFit, se~fitsEast], nw~[ ne~fitsNorth, nw~fitsNorth, sw~fitsWest, se~fitsWest], sw~[ ne~fitsSouth, nw~fitsSouth, sw~fitsSouth, se~fitsSouth], se~[ ne~fitsSouth, nw~fitsSouth, sw~fitsSouth, se~fitsSouth] ]; RETURN [choiceMatrix[qNE][qSW]] }; SplittingSizeTooSmall: PROCEDURE [r: CD.Rect] RETURNS [BOOLEAN] ~ { <<-- A heuristic to prevent ridiculous splitting.>> splitLimit: CD.Number ~ 10*CD.lambda; RETURN [(r.x2 - r.x1 < splitLimit) OR (r.y2 - r.y1 < splitLimit)]; }; <<-- Body of SortBoxes >> cir.spinifexLayers[layer].geometry _ AZ.NEW[QuadTree _ [boxes~NIL, subTrees~ALL[NIL], midX~(cir.spinifexLayers[layer].size.x2+cir.spinifexLayers[layer].size.x1)/2, midY~(cir.spinifexLayers[layer].size.y2+cir.spinifexLayers[layer].size.y1)/2]]; boxList _ cir.spinifexLayers[layer].unsortedBoxes; cir.spinifexLayers[layer].unsortedBoxes _ NIL; boundary _ cir.spinifexLayers[layer].size; qtRoot _ cir.spinifexLayers[layer].geometry; WHILE boxList # NIL DO branchBoundary: CD.Rect _ boundary; qt: REF QuadTree _ qtRoot; quadNE, quadSW: Quadrant; DO <<-- classify top right corner>> quadNE _ IF qt.midX < boxList.first.interestBound.x2 THEN IF qt.midY < boxList.first.interestBound.y2 THEN ne ELSE se ELSE IF qt.midY < boxList.first.interestBound.y2 THEN nw ELSE sw; <<-- classify bottom left corner (not quite the same as quadNE! NOTE <=, NOT < )>> quadSW _ IF qt.midX <= boxList.first.interestBound.x1 THEN IF qt.midY <= boxList.first.interestBound.y1 THEN ne ELSE se ELSE IF qt.midY <= boxList.first.interestBound.y1 THEN nw ELSE sw; IF SplittingSizeTooSmall[branchBoundary] THEN EXIT ELSE { st: AreaSplit; SELECT CanSubDivide[quadNE, quadSW] FROM noFit => EXIT; fitsNorth => { branchBoundary.y1 _ qt.midY; st _ north}; fitsSouth => { branchBoundary.y2 _ qt.midY; st _ south}; fitsEast => { branchBoundary.x1 _ qt.midX; st _ east}; fitsWest => { branchBoundary.x2 _ qt.midX; st _ west}; ENDCASE => ERROR; IF qt.subTrees[st] = NIL THEN <<-- The first box in a new split does not recurse; a hueristic to avoid irrational splitting. Some boxes will not be as deep as they could be, but it should not matter greatly.>> IF qt.boxes # NIL AND qt.boxes.rest # NIL THEN { qt.subTrees[st] _ AZ.NEW[QuadTree _ [boxes~NIL, subTrees~ALL[NIL], midX~(branchBoundary.x2+branchBoundary.x1)/2, midY~(branchBoundary.y2+branchBoundary.y1)/2] ]; qt _ qt.subTrees[st]; EXIT } ELSE EXIT; qt _ qt.subTrees[st]; } ENDLOOP; { temp: LIST OF REF Rectangle _ boxList.rest; boxList.rest _ qt.boxes; qt.boxes _ boxList; boxList _ temp }; ENDLOOP; }; IF cir.spinifexLayers[layer].unsortedBoxes = NIL THEN LOOP; SortBoxes[cir, layer]; ENDLOOP; }; EnumerateGeometry: PUBLIC PROCEDURE [circuit: REF Circuit, layer: SpinifexLayerIndex, clipRect: CD.Rect, PerRect: SpinifexCircuit.PerRectProc, data: REF ANY] ~ { FlattenTree: PROCEDURE [qt: REF QuadTree, bBox: CD.Rect] ~ { IF qt = NIL THEN RETURN; FOR boxes: LIST OF REF Rectangle _ qt.boxes, boxes.rest WHILE boxes # NIL DO IF CDInline.Intersect[clipRect, boxes.first.interestBound] THEN PerRect[boxes.first, data] ENDLOOP; FOR quad: AreaSplit IN AreaSplit DO subBox: CD.Rect _ bBox; SELECT quad FROM north => IF clipRect.y2 <= qt.midY THEN LOOP ELSE subBox.y1 _ qt.midY; south => IF clipRect.y1 >= qt.midY THEN LOOP ELSE subBox.y2 _ qt.midY; east => IF clipRect.x2 <= qt.midX THEN LOOP ELSE subBox.x1 _ qt.midX; west => IF clipRect.x1 >= qt.midX THEN LOOP ELSE subBox.x2 _ qt.midX; ENDCASE; FlattenTree[qt.subTrees[quad], subBox] ENDLOOP; }; FlattenTree[circuit.spinifexLayers[layer].geometry, circuit.spinifexLayers[layer].size]; }; AddEmptyBox: ERROR ~ CODE; AddRect: PUBLIC PROCEDURE [ cir: REF SpinifexCircuit.Circuit, lev: CD.Level, dim: CD.Rect, appl: CD.ApplicationPtr _ NIL, pos: CD.DesignPosition _ [0,0], orient: CD.Orientation _ CDOrient.original, value: REF SpinifexCircuit.CircuitNode _ NIL] RETURNS [cirNode: REF SpinifexCircuit.CircuitNode _ NIL] ~ { UniformBloat: PROCEDURE [d: INT] RETURNS [RectDelta] ~ INLINE { RETURN [[d,d,d,d]] }; IF cir.technologyHandle.illegalLevel[lev] THEN ERROR IllegalLevel[(IF appl = NIL THEN dim ELSE CDOrient.MapRect[ itemInCell~dim, cellSize~appl.ob.size, cellInstOrient~orient, cellInstPos~pos]), lev]; IF CDInline.NonEmpty[dim] THEN -- Silently ignore empty boxes FOR map: LIST OF MapRec _ cir.technologyHandle.cdLayerMapping[lev], map.rest WHILE map # NIL DO cn: REF SpinifexCircuit.CircuitNode; WITH map.first.value SELECT FROM mappingFunc: REF SpinifexCircuit.BoxMapProc => cn _ mappingFunc^[ cir~cir, dim~ dim, appl~ appl, pos~ pos, orient~ orient, node~ IF cirNode # NIL THEN cirNode ELSE value]; ENDCASE => cn _ AddBox[ cir~ cir, spinifexLayer~ map.first.spinifexLayer, dim~ dim, appl~ appl, pos~ pos, orient~ orient, interestBloat~ UniformBloat[map.first.bloatFactor], value~ (IF map.first.value # NIL THEN map.first.value ELSE value)]; IF cn # NIL THEN cirNode _ cn ENDLOOP; }; AddBox: PUBLIC PROCEDURE [cir: REF Circuit, spinifexLayer: SpinifexLayerIndex, dim: CD.Rect, appl: CD.ApplicationPtr _ NIL, pos: CD.DesignPosition _ [0,0], orient: CD.Orientation _ CDOrient.original, interestBloat: RectDelta _ [0,0,0,0], value: REF ANY _ NIL] RETURNS [cirNode: REF CircuitNode _ NIL] ~ { A: PROCEDURE [r: CD.Rect] RETURNS [area: INT] ~ INLINE { area _ (r.x2-r.x1)*(r.y2-r.y1) }; P: PROCEDURE [r: CD.Rect] RETURNS [perim: INT] ~ INLINE { perim _ ((r.x2-r.x1)+(r.y2-r.y1))*2 }; IF value = NIL THEN { value _ cirNode _ AZ.NEW[ CircuitNode _ [ dim ~ LIST[ [layer~spinifexLayer, area~A[dim], perim~P[dim]]]] ]; AddCircuitNode[ cir, cirNode] } ELSE WITH value SELECT FROM cn: REF CircuitNode => { cirNode _ cn; AdjustNode[ cirNode, spinifexLayer, A[dim], P[dim]] }; ENDCASE; IF ~CDInline.NonEmpty[dim] THEN ERROR AddEmptyBox ELSE { mappedDim: CD.Rect ~ (IF appl = NIL THEN dim ELSE CDOrient.MapRect[ itemInCell~dim, cellSize~appl.ob.size, cellInstOrient~orient, cellInstPos~pos]); bloatedDim: CD.Rect ~ [x1~mappedDim.x1-interestBloat.dx1, y1~mappedDim.y1-interestBloat.dy1, x2~mappedDim.x2+interestBloat.dx2, y2~mappedDim.y2+interestBloat.dy2]; newRect: REF Rectangle ~ AZ.NEW[Rectangle _ [ interestBound~bloatedDim, dimDecr~interestBloat, nodeInformation~value]]; cir.spinifexLayers[spinifexLayer].unsortedBoxes _ AZ.CONS[ newRect, cir.spinifexLayers[spinifexLayer].unsortedBoxes]; IF ~ CDInline.Inside[bloatedDim, cir.spinifexLayers[spinifexLayer].size] THEN cir.spinifexLayers[spinifexLayer].size _ CDInline.Surround[bloatedDim, cir.spinifexLayers[spinifexLayer].size] } }; MergeNode: PUBLIC PROCEDURE [ circuit: REF Circuit, to, from: REF CircuitNode] ~ { <<-- Combine areas and perimeters.>> FOR fromList: LIST OF AreaPerimRec _ from.dim, fromList.rest WHILE fromList # NIL DO AdjustNode[ to, fromList.first.layer, fromList.first.area, fromList.first.perim] ENDLOOP; <<-- Combine properties.>> CopyNodeProperties[ circuit, to, from.properties]; from.properties _ NIL; to.attached _ to.attached OR from.attached; from.superceded _ to; }; SignalName: TYPE ~ SpinifexCircuit.SignalName; CopyNodeProperties: PROCEDURE [ circuit: REF Circuit, node: REF CircuitNode, properties: Atom.PropList, qual: LIST OF CD.ApplicationPtr _ NIL] ~ { CopySignal: PROCEDURE [sig: REF ANY, depth: INTEGER] RETURNS [REF SignalName] ~ { <<-- Creates a SignalName RECORD with appropriate depth from a ChipNDale Signal name (ROPE) or an existing SignalName RECORD.>> IF sig = NIL THEN RETURN [NIL]; WITH sig SELECT FROM r: Rope.ROPE => RETURN [ NEW[SignalName _ [depth~ depth, name~ r]]]; s: REF SignalName => { copyHead, copyTail: REF SignalName; copyHead _ NEW[SignalName _ [depth~ s.depth + depth, name~ s.name]]; copyTail _ copyHead; FOR source: REF SignalName _ s.alias, source.alias WHILE source # NIL DO copyTail.alias _ NEW[SignalName _ [depth~ source.depth + depth, name~ source.name]]; copyTail _ copyTail.alias; ENDLOOP; RETURN [copyHead]; }; ENDCASE => ERROR; }; MergeAliases: PROCEDURE [ to, from: REF SignalName] ~ { WHILE from # NIL DO FOR existingAlias: REF SignalName _ to, existingAlias.alias WHILE existingAlias # NIL DO IF from.name.Equal[existingAlias.name] THEN { IF from.depth < existingAlias.depth THEN existingAlias.depth _ from.depth; from _ from.alias; EXIT } REPEAT FINISHED => { <<-- Insert in list.>> tmp: REF SignalName ~ from; from _ from.alias; tmp.alias _ to.alias; to.alias _ tmp } ENDLOOP; ENDLOOP; }; <> { fromSignal: REF SignalName; toSignal: REF SignalName; depth: INTEGER _ 0; FOR q: LIST OF CD.ApplicationPtr _ qual, q.rest WHILE q # NIL DO depth _ depth.SUCC ENDLOOP; fromSignal _ CopySignal[properties.GetPropFromList[ SpinifexAtoms.SignalName], depth]; toSignal _ NARROW[node.properties.GetPropFromList[ SpinifexAtoms.SignalName]]; IF toSignal # NIL AND fromSignal # NIL THEN { IF toSignal.depth > fromSignal.depth THEN { node.properties _ node.properties.PutPropOnList[ SpinifexAtoms.SignalName, fromSignal]; MergeAliases[fromSignal, toSignal] } ELSE MergeAliases[toSignal, fromSignal] } ELSE IF fromSignal # NIL THEN node.properties _ node.properties.PutPropOnList[ SpinifexAtoms.SignalName, fromSignal] }; <> IF circuit.technologyHandle.CombineNodeProperties # NIL AND properties # NIL THEN node.properties _ circuit.technologyHandle.CombineNodeProperties[circuit, node.properties, properties, qual]; }; AdjustNode: PUBLIC PROCEDURE [node: REF CircuitNode, layer: SpinifexLayerIndex, area: INT, perim: INT, mode: SpinifexCircuit.AdjustmentMode _ relative] ~ { <<-- Search for a AreaPerimRec on this layer.>> apRec: LIST OF AreaPerimRec _ node.dim; WHILE apRec # NIL DO IF apRec.first.layer = layer THEN EXIT; apRec _ apRec.rest; REPEAT FINISHED => { node.dim _ AZ.CONS[ AreaPerimRec[ layer~ layer, area~ area, perim~ perim], node.dim]; RETURN } ENDLOOP; SELECT mode FROM relative => { apRec.first.area _ apRec.first.area + area; apRec.first.perim _ apRec.first.perim + perim; }; absolute => { apRec.first.area _ area; apRec.first.perim _ perim; }; ENDCASE }; NormalizeCircuit: PUBLIC PROCEDURE [cir: REF Circuit] ~ { <<-- This is an important step ...>> <<-- It results in the deallocation of superceded CircuitNodes, and the removal of dupliactes and superceded nodes from cir.nodes.>> CompressCircuitNodeList: PROCEDURE ~ { mySpecialCN: REF CircuitNode~AZ.NEW[CircuitNode]; cn: LIST OF REF CircuitNode; IF cir.nodes = NIL THEN RETURN; <<-- Discard superceded nodes.>> cn _ cir.nodes; WHILE cn.rest # NIL DO IF cn.rest.first.superceded # NIL THEN cn.rest _ cn.rest.rest ELSE cn _ cn.rest ENDLOOP; IF cir.nodes.first.superceded # NIL THEN cir.nodes _ cir.nodes.rest; <<-- Discard duplicated nodes.>> IF cir.nodes = NIL THEN ERROR; -- Impossible! cn _ cir.nodes; WHILE cn.rest # NIL DO IF cn.rest.first.superceded = mySpecialCN THEN cn.rest _ cn.rest.rest ELSE { cn.first.superceded _ mySpecialCN; cn _ cn.rest } ENDLOOP; cn _ cir.nodes; WHILE cn.rest # NIL DO cn.first.superceded _ NIL; cn _ cn.rest ENDLOOP; }; CompressLinkages: PROCEDURE ~ { FOR linkages: LIST OF REF NodeLinkage _ cir.linkages, linkages.rest WHILE linkages # NIL DO FOR attached: LIST OF REF AttachedNode _ linkages.first.nodes , attached.rest WHILE attached # NIL DO IF attached.first.node # NIL THEN attached.first.node _ LookupNode[attached.first.node] ENDLOOP ENDLOOP }; CompressMergeDirectoryEntries: PROCEDURE ~ { CompressMerge: RefTab.EachPairAction ~ { FOR mergeList: MergeRecList _ NARROW[val], mergeList.rest WHILE mergeList # NIL DO mergeList.first.becomes _ LookupNode[mergeList.first.becomes]; ENDLOOP; RETURN [FALSE] }; IF cir.mergeDirectory # NIL THEN [] _ RefTab.Pairs[cir.mergeDirectory, CompressMerge]; }; CompressBoxPaths: PROCEDURE [qt: REF QuadTree] ~ { FOR boxes: LIST OF REF Rectangle _ qt.boxes, boxes.rest WHILE boxes # NIL DO WITH boxes.first.nodeInformation SELECT FROM appl: CD.ApplicationPtr => NULL; cn: REF CircuitNode => boxes.first.nodeInformation _ LookupNode[cn]; cc: REF CircuitConstraint => NULL; ENDCASE => ERROR; ENDLOOP; FOR quad: AreaSplit IN AreaSplit DO IF qt.subTrees[quad] # NIL THEN CompressBoxPaths[qt.subTrees[quad]] ENDLOOP; }; CompressCircuitNodeList[]; CompressLinkages[]; CompressMergeDirectoryEntries[]; FOR layer: SpinifexLayerIndex IN [0..cir.technologyHandle.numSpinifexLayers) DO IF cir.spinifexLayers[layer].geometry # NIL THEN CompressBoxPaths[cir.spinifexLayers[layer].geometry] ENDLOOP; }; LookupNode: PUBLIC PROCEDURE [l: REF CircuitNode] RETURNS [REF CircuitNode] ~ { <<-- Implements (partial) Galler-Fisher path compression.>> RETURN [IF l.superceded # NIL THEN (l.superceded _ LookupNode[l.superceded]) ELSE l] }; LookupMergeDirectory: PROCEDURE [ dir: RefTab.Ref, cn: REF CircuitNode, qual: LIST OF CD.ApplicationPtr] RETURNS [merge: MergeRecList, newQual: LIST OF CD.ApplicationPtr] ~ { found: BOOLEAN; val: REF ANY; [found, val] _ dir.Fetch[cn]; IF found THEN { <<-- Search mergeList for qual>> FOR mergeList: MergeRecList _ NARROW[val], mergeList.rest WHILE mergeList # NIL DO <<-- Compare mergeList.first.applChain to qual>> qApplChain: LIST OF CD.ApplicationPtr _ qual; FOR applChain: LIST OF CD.ApplicationPtr _ mergeList.first.applChain, applChain.rest DO IF applChain = NIL THEN <<-- This is a renaming of cn, qual gets to be what's left, and we continue looking for higher intervening renamings.>> RETURN [mergeList, qApplChain]; IF qApplChain = NIL OR qApplChain.first # applChain.first THEN EXIT; qApplChain _ qApplChain.rest ENDLOOP; ENDLOOP; }; RETURN [NIL, qual] }; FindRootNode: PUBLIC PROCEDURE [ circuit: REF Circuit, subcircuitNode: REF CircuitNode, qualifier: LIST OF CD.ApplicationPtr, insertIfNotInCircuit: BOOLEAN _ FALSE] RETURNS [node: REF CircuitNode, rootQualifier: LIST OF CD.ApplicationPtr] ~ { AddCircuitNodeMerge: PROCEDURE [ sourceNode: REF CircuitNode, qual: LIST OF CD.ApplicationPtr] RETURNS [newNode: REF CircuitNode] ~ { found: BOOLEAN; mergeList: MergeRecList _ NIL; IF circuit.mergeDirectory = NIL THEN { IF insertIfNotInCircuit THEN { circuit.mergeDirectory _ RefTab.Create[]; found _ FALSE } } ELSE { val: REF ANY; [found, val] _ circuit.mergeDirectory.Fetch[sourceNode]; IF found THEN { mergeList _ NARROW[val]; <> FOR m: MergeRecList _ mergeList, m.rest WHILE m # NIL DO q: LIST OF CD.ApplicationPtr _ qual; FOR applChain: LIST OF CD.ApplicationPtr _ m.first.applChain, applChain.rest DO IF applChain = NIL OR q = NIL THEN IF applChain = NIL AND q = NIL THEN RETURN [newNode _ m.first.becomes] ELSE EXIT ELSE IF applChain.first # q.first THEN EXIT; q _ q.rest ENDLOOP; ENDLOOP } }; IF ~insertIfNotInCircuit THEN RETURN [newNode _ NIL]; newNode _ AZ.NEW[CircuitNode _ sourceNode^]; <> IF newNode.dim # NIL THEN { newNode.dim _ AZ.CONS[newNode.dim.first, newNode.dim.rest]; FOR tailDim: LIST OF AreaPerimRec _ newNode.dim, tailDim.rest WHILE tailDim.rest # NIL DO tailDim.rest _ AZ.CONS[tailDim.rest.first, tailDim.rest.rest]; ENDLOOP }; newNode.properties _ NIL; CopyNodeProperties[ circuit, newNode, sourceNode.properties, qual]; mergeList _ AZ.CONS[ [applChain~qual, becomes~newNode], mergeList]; IF RefTab.Store[circuit.mergeDirectory, sourceNode, mergeList] = found THEN ERROR; AddCircuitNode[ circuit, newNode] }; <

> IF qualifier = NIL THEN RETURN [subcircuitNode, NIL]; <> FOR q: LIST OF CD.ApplicationPtr _ qualifier.rest, q.rest WHILE q # NIL DO subcircuit: REF Circuit _ NARROW[ CDProperties.GetPropFromObject[ from~q.first.ob, prop~SpinifexAtoms.spinifex]]; IF subcircuit.mergeDirectory # NIL THEN { tmp: MergeRecList; [merge~tmp, newQual~qualifier] _ LookupMergeDirectory[ subcircuit.mergeDirectory, subcircuitNode, qualifier]; IF tmp # NIL THEN subcircuitNode _ tmp.first.becomes } ENDLOOP; <> IF (node _ AddCircuitNodeMerge[ sourceNode~subcircuitNode, qual~qualifier]) = NIL THEN { node _ subcircuitNode; rootQualifier _ qualifier } ELSE rootQualifier _ NIL }; AddCircuitNode: PROCEDURE [cir: REF Circuit, cn: REF CircuitNode] ~ INLINE { cir.nodes _ AZ.CONS[ cn, cir.nodes] }; CreateLinkage: PUBLIC PROCEDURE [ cir: REF Circuit, source: CD.ApplicationPtr] RETURNS [REF NodeLinkage] ~ { cir.linkages _ AZ.CONS[ AZ.NEW[ NodeLinkage _ [source]], cir.linkages]; RETURN [cir.linkages.first]; }; LinkageAttach: PUBLIC PROCEDURE [link: REF NodeLinkage, attachType: ATOM, areaAdj: INTEGER _ 0, perimAdj: INTEGER _ 0, node: REF CircuitNode _ NIL] ~ { IF node # NIL THEN node.attached _ TRUE; link.nodes _ AZ.CONS[ AZ.NEW[ AttachedNode _ [ attachType, areaAdj, perimAdj, node]], link.nodes]; }; END.