<> <> <> <> <> <> <> <> DIRECTORY Atom USING [GetPName, GetPropFromList, PropList, PutPropOnList, RemPropFromList], Basics USING [CompareINT, Comparison], CD USING [CreateDrawRef, DrawProc, DrawRectProc, DrawRef, highLightError, Instance, InstanceList, InstanceRep, Layer, Object, Orientation, Number, Position, Properties, Rect], CDInstances USING [NewInstance], CDBasics USING [Center, NonEmpty, RectAt, SubPoints], CDObjectProcs USING [FetchFurther], CDOps USING [LayerName], CDOrient USING [MapPoint, MapRect, original], CDProperties USING [GetPropFromInstance, PutPropOnInstance], Convert USING [RopeFromInt], RedBlackTree USING [Compare, Create, DuplicateKey, GetKey, Insert, LookupNextLarger, LookupSmallest, Table], RefTab USING [Create, EachPairAction, Fetch, GetSize, Insert, Pairs, Ref, Store], Rope USING [Cat, Equal, ROPE], SX USING [AdjustmentMode, AreaPerimRec, AttachedNode, BoxMapProc, Circuit, CircuitNode, Constraint, ConversionProc, LogicalCell, MapRec, MergeRec, MergeRecList, NodeLinkage, SignalName, SpinifexLayerIndex], SXAccess USING [stopFlag, sxTech], SXAccessInternal USING [GetSXData, PutError], SXAtoms USING [export, InstanceName, Rect, SignalName, spinifex], SXQuadTree USING [AreaSplit, Store, QuadTree, QuadTreeRoot, Rectangle, RectDelta]; <> SXImpl: CEDAR PROGRAM IMPORTS Atom, Basics, CD, CDInstances, CDBasics, CDObjectProcs, CDOps, CDOrient, CDProperties, Convert, RedBlackTree, RefTab, Rope, SXAccess, SXAccessInternal, SXAtoms, SXQuadTree --, TerminalIO EXPORTS SX = BEGIN <<-- TYPES from Interface.>> LogicalCell: TYPE = SX.LogicalCell; Circuit: TYPE = SX.Circuit; AreaPerimRec: TYPE = SX.AreaPerimRec; Constraint: TYPE = SX.Constraint; NodeLinkage: TYPE = SX.NodeLinkage; AttachedNode: TYPE = SX.AttachedNode; MergeRec: TYPE = SX.MergeRec; SpinifexLayerIndex: TYPE = SX.SpinifexLayerIndex; MapRec: TYPE = SX.MapRec; SignalName: TYPE = SX.SignalName; <<-- Implementation.>> IllegalConstruct: PUBLIC ERROR [rect: CD.Rect, reason: Rope.ROPE] = CODE; IllegalLayer: PUBLIC ERROR [rect: CD.Rect, lev: CD.Layer] = CODE; repetitionInstanceNamePrefix: Rope.ROPE _ ""; repetitionInstanceNamePostfix: Rope.ROPE _ ""; IsSimpleRect: PROC [ob: CD.Object] RETURNS [BOOL] = INLINE BEGIN RETURN [ob.class.objectType = SXAtoms.Rect] END; TranslateChild: CD.DrawProc = <<-- PROC [aptr: Instance, pos: Position, orient: Orientation, pr: REF DrawInformation] >> BEGIN sxThrough: REF SX.LogicalCell = NARROW[pr.devicePrivate]; cir: REF SX.Circuit = sxThrough.circuit; sx: REF SX.LogicalCell; IF IsSimpleRect[inst.ob] THEN { IF inst.ob.layer # CD.highLightError THEN { box: CD.Rect = CDOrient.MapRect[ itemInCell: CDBasics.RectAt[pos: [0, 0], size: inst.ob.size], cellSize: inst.ob.size, cellInstOrient: orient, cellInstPos: pos ]; node: REF SX.CircuitNode = AddRect[ cir: cir, lev: inst.ob.layer, dim: box ! IllegalLayer => { SXAccessInternal.PutError[sxThrough.cellObj, rect, Rope.Cat["Material on layer ", CDOps.LayerName[lev], " may not appear as an isolated rectangle.\n" ] ]; GOTO BadRect } ]; IF node#NIL THEN CopyNodeProperties[cir, node, inst.properties]; EXITS BadRect => NULL }; RETURN }; -- end simple rectangle. sx _ SXAccessInternal.GetSXData[inst.ob]; IF sx#NIL AND sx.analysisState=useCircuit THEN { <<-- This object is a logical subcircuit.>> subcircuit: REF Circuit = sx.circuit; newAppl: CD.Instance = NEW[CD.InstanceRep _ [ ob: inst.ob, location: pos, orientation: orient, -- selected: TRASH, properties: CopyProperties[inst.properties]]]; <> numLayers: SpinifexLayerIndex = SXAccess.sxTech.numSpinifexLayers; FOR i: SpinifexLayerIndex IN [0..numLayers) DO IF subcircuit.spinifexLayers[i].private=NIL THEN LOOP; -- no geom. IF cir.subcircuits=NIL OR cir.subcircuits.first#newAppl THEN { <> cir.subcircuits _ CONS[newAppl, cir.subcircuits]; }; [] _ AddBox [ cir: cir, inst: 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; } ELSE { -- expand special objects (transistors) and conditional objects convProc: REF ANY = CDObjectProcs.FetchFurther[p: inst.ob.class, key: SXAtoms.spinifex]; IF convProc#NIL THEN <<-- object has special layout analysis code.>> NARROW[convProc, REF SX.ConversionProc]^[inst, pos, orient, cir ! IllegalConstruct => { SXAccessInternal.PutError [sxThrough.cellObj, CDOrient.MapRect [itemInCell: rect, cellSize: inst.ob.size, cellInstOrient: orient, cellInstPos: pos], reason]; CONTINUE } ] ELSE inst.ob.class.drawMe[inst, pos, orient, pr] -- analysis state: notYetDone } END; -- TranslateChild CopyProperties: PROC [from: CD.Properties] RETURNS [to: CD.Properties] = BEGIN to _ NIL; FOR from _ from, from.rest WHILE from#NIL DO to _ CONS[from.first, to]; ENDLOOP; END; TranslateRect: CD.DrawRectProc = <<-- PROC [r: DesignRect, l: Layer, pr: DrawRef] -- >> BEGIN IF ~CDBasics.NonEmpty[r] THEN RETURN; IF l # CD.highLightError THEN { sxc: REF SX.LogicalCell = NARROW[pr.devicePrivate]; [] _ AddRect[cir: sxc.circuit, lev: l, dim: r ! IllegalLayer => { SXAccessInternal.PutError[sxc.cellObj, rect, Rope.Cat["Rectangle on layer ", CDOps.LayerName[lev], " cannot be analyzed in this context.\n" ] ]; CONTINUE } ]; } END; -- TranslateRect <<>> <> SKey: TYPE = REF CD.Position; -- RedBlackTree.Key SRec: TYPE = RECORD [key: SKey, instance: CD.Instance]; SData: TYPE = REF SRec; -- RedBlackTree.UserData InstKey: RedBlackTree.GetKey = BEGIN RETURN [NARROW [data, SData].key] END; -- InstKey InstComp: RedBlackTree.Compare = BEGIN c: Basics.Comparison; sk: SKey = NARROW [k]; d: SData = NARROW [data]; c _ Basics.CompareINT [sk.x, d.key.x]; IF c = equal THEN c _ Basics.CompareINT [sk.y, d.key.y]; RETURN [c] END; -- InstComp SInsert: PROCEDURE [s: RedBlackTree.Table, inst: CD.Instance] RETURNS [duplicate: BOOL] = BEGIN ENABLE RedBlackTree.DuplicateKey => GOTO dupl; sk: SKey _ NEW [CD.Position _ inst.location]; data: SData _ NEW [SRec _ [key: sk, instance: inst]]; RedBlackTree.Insert [s, data, sk]; <> RETURN [FALSE]; EXITS dupl => RETURN [TRUE] END; -- SInsert <<>> TranslateGeometry: PUBLIC PROC [cell: REF LogicalCell] = <<--Translates ChipNDale layers into Spinifex layers (e.g. only explicit contacts [which must be correct and hence are not checked] are allowed. Also a node number is assigned, which is used to identify the nodes. The translation is performed using the drawRect mechanism of ChipNDale. The ChipNDale design is translated into a quad-tree. It is not possible to use a tesselation because of overlaps. The quad-tree contains only cells already analysed. There are three types of rectangles in the Quad-Tree: 1. constraints; 2. material; 3. bounding boxes for subcell rectangles.>> BEGIN cir: REF Circuit = cell.circuit; dr: CD.DrawRef = CD.CreateDrawRef[NIL]; fakeAppl: CD.Instance = CDInstances.NewInstance[cell.cellObj]; fakeAppl.location _ [0, 0]; dr.drawRect _ TranslateRect; dr.drawChild _ TranslateChild; dr.devicePrivate _ cell; dr.stopFlag _ SXAccess.stopFlag; cell.cellObj.class.drawMe [fakeAppl, [0, 0], CDOrient.original, dr]; <<--Translation of the geometry.>> FOR link: LIST OF REF NodeLinkage _ cir.linkages, link.rest WHILE link#NIL DO cir.linkageCount.inSelf _ cir.linkageCount.inSelf+1 <<--Number of devices.>> ENDLOOP; IF cir.subcircuits#NIL AND cir.subcircuits.rest#NIL AND cir.subcircuits.rest.rest#NIL THEN { <<-- There are at least three subcircuits.>> FOR sub: CD.InstanceList _ cir.subcircuits, sub.rest WHILE sub#NIL DO IF cir.subcircuits.first.orientation # sub.first.orientation THEN EXIT; IF cir.subcircuits.first.ob # sub.first.ob THEN EXIT; REPEAT FINISHED => { <> sTab: RedBlackTree.Table = RedBlackTree.Create [InstKey, InstComp]; lastApp, currApp: SData; delta: CD.Position; FOR sub: CD.InstanceList _ cir.subcircuits, sub.rest WHILE sub#NIL DO IF SInsert [sTab, sub.first] THEN GOTO EqualAppls; ENDLOOP; lastApp _ NARROW [RedBlackTree.LookupSmallest[sTab]]; currApp _ NARROW [RedBlackTree.LookupNextLarger[sTab,lastApp.key]]; delta _ CDBasics.SubPoints[currApp.instance.location, lastApp.instance.location]; lastApp _ currApp; WHILE (currApp _ NARROW[RedBlackTree.LookupNextLarger[sTab, lastApp.key]]) # NIL DO IF delta # CDBasics.SubPoints[currApp.instance.location, lastApp.instance.location] THEN EXIT; lastApp _ currApp; REPEAT FINISHED => { <<-- They are sorted. Hence they are logically a repetition.>> index: INT _ 1; FOR a: SData _ NARROW[RedBlackTree.LookupSmallest[sTab]], NARROW[RedBlackTree.LookupNextLarger[sTab, a.key]] WHILE a # NIL DO IF CDProperties.GetPropFromInstance[from: a.instance, prop: SXAtoms.InstanceName]=NIL THEN { <<--Provide default instance names for repetition elements.>> <<--Added by Spreitzer November 24, 1984 12:08:57 pm PST.>> <<--Genralized by Shand, March 13, 1985 2:20:08 pm PST.>> instanceName: Rope.ROPE _ repetitionInstanceNamePrefix.Cat[Convert.RopeFromInt[index], repetitionInstanceNamePostfix]; CDProperties.PutPropOnInstance[a.instance, SXAtoms.InstanceName, instanceName]; }; index _ index+1 ENDLOOP }; ENDLOOP; EXITS EqualAppls => NULL } ENDLOOP; } END; -- TranslateGeometry AddRect: PUBLIC PROC [ cir: REF SX.Circuit, lev: CD.Layer, dim: CD.Rect, inst: CD.Instance _ NIL, pos: CD.Position _ [0, 0], orient: CD.Orientation _ CDOrient.original, value: REF SX.CircuitNode _ NIL] RETURNS [cirNode: REF SX.CircuitNode _ NIL] = BEGIN UniformBloat: PROC [d: INT] RETURNS [SXQuadTree.RectDelta] = INLINE { RETURN [[d,d,d,d]] }; IF SXAccess.sxTech.illegalLayer[lev] THEN { ERROR IllegalLayer[ (IF inst=NIL THEN dim ELSE CDOrient.MapRect[ itemInCell: dim, cellSize: inst.ob.size, cellInstOrient: orient, cellInstPos: pos] ), lev]; }; IF CDBasics.NonEmpty[dim] THEN -- Silently ignore empty boxes FOR map: LIST OF MapRec _ SXAccess.sxTech.cdLayerMapping[lev], map.rest WHILE map#NIL DO cn: REF SX.CircuitNode; WITH map.first.value SELECT FROM mappingFunc: REF SX.BoxMapProc => cn _ mappingFunc^[ cir: cir, dim: dim, inst: inst, pos: pos, orient: orient, node: IF cirNode#NIL THEN cirNode ELSE value ]; ENDCASE => cn _ AddBox[ cir: cir, spinifexLayer: map.first.spinifexLayer, dim: dim, inst: inst, 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; END; -- AddRect AddEmptyBox: ERROR = CODE; AddBox: PUBLIC PROC [ cir: REF Circuit, spinifexLayer: SpinifexLayerIndex, dim: CD.Rect, inst: CD.Instance _ NIL, pos: CD.Position _ [0, 0], orient: CD.Orientation _ CDOrient.original, interestBloat: SXQuadTree.RectDelta _ [0,0,0,0], value: REF ANY _ NIL] RETURNS [cirNode: REF SX.CircuitNode _ NIL] = BEGIN <<--In this context `appl = NIL' means that transformation has not to be applied.>> A: PROC [r: CD.Rect] RETURNS [area: INT] = INLINE { area _ (r.x2-r.x1)*(r.y2-r.y1) }; P: PROC [r: CD.Rect] RETURNS [perim: INT] = INLINE { perim _ ((r.x2-r.x1)+(r.y2-r.y1))*2 }; IF CDBasics.NonEmpty [dim] THEN BEGIN bloatedDim, bloatedMapped, mappedDim: CD.Rect; newRect: REF SXQuadTree.Rectangle; bloatedDim _ [x1: dim.x1-interestBloat.dx1, y1: dim.y1-interestBloat.dy1, x2: dim.x2+interestBloat.dx2, y2: dim.y2+interestBloat.dy2]; IF inst = NIL THEN {bloatedMapped _ bloatedDim; mappedDim _ dim} ELSE BEGIN bloatedMapped _ CDOrient.MapRect [itemInCell: bloatedDim, cellSize: inst.ob.size, cellInstOrient: orient, cellInstPos: pos]; mappedDim _ CDOrient.MapRect [itemInCell: dim, cellSize: inst.ob.size, cellInstOrient: orient, cellInstPos: pos] END; -- appl # NIL WITH value SELECT FROM cn: REF SX.CircuitNode => { cirNode _ cn; AdjustNode [cirNode, spinifexLayer, A[dim], P[dim]] }; ENDCASE => IF value=NIL THEN { value _ cirNode _ NEW [SX.CircuitNode _ [dim: LIST[[layer: spinifexLayer, area: A[dim], perim: P[dim]]], loc: [CDBasics.Center[mappedDim], spinifexLayer]]]; AddCircuitNode [cir, cirNode] }; newRect _ NEW[SXQuadTree.Rectangle _ [interestBound: bloatedMapped, dimDecr: [ dx1: mappedDim.x1-bloatedMapped.x1, dy1: mappedDim.y1-bloatedMapped.y1, dx2: bloatedMapped.x2-mappedDim.x2, dy2: bloatedMapped.y2-mappedDim.y2], nodeInformation: value]]; cir.spinifexLayers[spinifexLayer] _ SXQuadTree.Store [quadTree: cir.spinifexLayers[spinifexLayer], rect: newRect] END -- if dim not empty ELSE ERROR AddEmptyBox END; -- AddBox MergeNode: PUBLIC PROC [circuit: REF Circuit, to, from: REF SX.CircuitNode] = BEGIN <<--calling LookupNode and equal test introduced by Ch. J. Jan 30, 1985>> IF from.superceded#NIL THEN from _ LookupNode[from]; IF to.superceded#NIL THEN to _ LookupNode[to]; IF from=to THEN RETURN; <<-- 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; from.superceded _ to; END; CopyNodeProperties: PROC [ circuit: REF Circuit, node: REF SX.CircuitNode, properties: Atom.PropList, qual: LIST OF CD.Instance _ NIL] = BEGIN CopySignal: PROC [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.>> BEGIN IF sig=NIL THEN RETURN [NIL]; WITH sig SELECT FROM r: Rope.ROPE => RETURN [NEW[SignalName _ [depth: depth, name: r]]]; a: ATOM => RETURN [NEW[SignalName _ [depth: depth, name: Atom.GetPName[a]]]]; s: REF SignalName => { copyHead, copyTail: REF SignalName; copyHead _ NEW[SignalName _ [depth: s.depth+depth, name: s.name, makePort: s.makePort]]; 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; END; -- CopySignal MergeAliases: PROC [to, from: REF SignalName] = BEGIN 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; END; -- MergeAliases fromSigProp: REF ANY ~ Atom.GetPropFromList [properties, SXAtoms.SignalName]; exportProp: REF ANY = Atom.GetPropFromList [properties, SXAtoms.export]; toSigProp: REF ANY ~ Atom.GetPropFromList [node.properties, SXAtoms.SignalName]; <<--Copy Technology Dependent Properties>> IF SXAccess.sxTech.combineNodeProperties#NIL AND properties#NIL THEN node.properties _ SXAccess.sxTech.combineNodeProperties[circuit, node.properties, properties, qual]; <<--Copy SignalName property>> { fromSignal: REF SignalName; toSignal: REF SignalName; depth: INTEGER _ 0; FOR q: LIST OF CD.Instance _ qual, q.rest WHILE q#NIL DO depth _ depth.SUCC ENDLOOP; fromSignal _ CopySignal [fromSigProp, depth]; IF fromSignal # NIL THEN fromSignal.makePort _ (fromSignal.makePort OR exportProp=$TRUE); toSignal _ NARROW[toSigProp]; IF toSignal#NIL AND fromSignal#NIL THEN { IF toSignal.depth > fromSignal.depth THEN { node.properties _ node.properties.PutPropOnList[SXAtoms.SignalName, fromSignal]; MergeAliases[fromSignal, toSignal] } ELSE MergeAliases[toSignal, fromSignal] } ELSE IF fromSignal#NIL THEN node.properties _ node.properties.PutPropOnList[SXAtoms.SignalName, fromSignal] }; <<--Delete UnMerged property.>> node.properties _ node.properties.RemPropFromList[UnMerged]; END; -- CopyNodeProperties AdjustNode: PUBLIC PROC [ node: REF SX.CircuitNode, layer: SpinifexLayerIndex, area: INT, perim: INT, mode: SX.AdjustmentMode _ relative] = BEGIN <<-- Search for a AreaPerimRec on this layer.>> apRec: LIST OF AreaPerimRec _ node.dim; IF node.superceded#NIL THEN node _ LookupNode[node]; -- added Ch. J. Jan 30, 1985 WHILE apRec#NIL DO IF apRec.first.layer = layer THEN EXIT; apRec _ apRec.rest; REPEAT FINISHED => { node.dim _ 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 END; -- AdjustNode NormalizeCircuit: PUBLIC PROC [cir: REF Circuit] = BEGIN <<-- This is an important step ...>> <<-- It results in the deallocation of superceded SX.CircuitNodes, and the removal of duplicates, superceded and UnMerged nodes from cir.nodes, and >> CompressCircuitNodeList: PROC = BEGIN mySpecialCN: REF SX.CircuitNode = NEW[SX.CircuitNode]; indirectList: LIST OF REF SX.CircuitNode ~ CONS[mySpecialCN, cir.nodes]; cn: LIST OF REF SX.CircuitNode; IF cir.nodes=NIL THEN RETURN; <<-- Discard superceded & UnMerged nodes.>> mySpecialCN.superceded _ NIL; mySpecialCN.properties _ NIL; cn _ indirectList; WHILE cn.rest#NIL DO node: REF SX.CircuitNode ~ cn.rest.first; IF node.superceded # NIL OR node.properties.GetPropFromList[UnMerged] # NIL THEN cn.rest _ cn.rest.rest ELSE cn _ cn.rest ENDLOOP; <<-- Discard duplicated nodes.>> IF cir.nodes=NIL THEN ERROR; -- Impossible! We would have returned at start if NIL list, and at least some of the nodes must be non-superceded. cn _ indirectList; WHILE cn.rest#NIL DO IF cn.rest.first.superceded = mySpecialCN THEN cn.rest _ cn.rest.rest ELSE { cn _ cn.rest; cn.first.superceded _ mySpecialCN } ENDLOOP; cn _ cir.nodes _ indirectList.rest; WHILE cn#NIL DO cn.first.superceded _ NIL; cn _ cn.rest ENDLOOP; END; -- CompressCircuitNodeList CompressLinkages: PROC = BEGIN 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 END; CompressMergeDirectoryEntries: PROC = BEGIN IF cir.mergeDirectory#NIL THEN { dummy: SX.MergeRecList = CONS[[], NIL]; <<-- Normally no SX.CircuitNodes in subcells will be unmerged at this point, however this is not true in the case of Normalization following SpinifexOutput. SpinifexOutput introduces extra intermediate nodes, such merge directory entries should be deleted.>> CountUnMerged: RefTab.EachPairAction = BEGIN IF NARROW[key, REF SX.CircuitNode].properties.GetPropFromList[UnMerged] # NIL THEN oldSize _ oldSize.PRED; RETURN [FALSE] END; CompressMerge: RefTab.EachPairAction = BEGIN mergeList: SX.MergeRecList; IF NARROW[key, REF SX.CircuitNode].properties.GetPropFromList[UnMerged] = NIL THEN { dummy.rest _ NARROW[val]; mergeList _ dummy; WHILE mergeList.rest # NIL DO mergeList.rest.first.becomes _ LookupNode[mergeList.rest.first.becomes]; IF mergeList.rest.first.becomes.properties.GetPropFromList[UnMerged]#NIL THEN mergeList.rest _ mergeList.rest.rest ELSE mergeList _ mergeList.rest ENDLOOP; IF dummy.rest#NIL THEN IF ~newTab.Insert[key, dummy.rest] THEN ERROR }; RETURN [FALSE] END; -- CompressMerge <<>> <<-- Ensure size is not a power of 2 (seems like a good idea).>> oldSize: INT _ RefTab.GetSize[cir.mergeDirectory]; newTab: RefTab.Ref; [] _ RefTab.Pairs[cir.mergeDirectory, CountUnMerged]; IF oldSize <= 0 THEN { cir.mergeDirectory _ NIL; RETURN }; newTab _ RefTab.Create[ ((oldSize/3)*4)+1]; [] _ RefTab.Pairs[cir.mergeDirectory, CompressMerge]; cir.mergeDirectory _ newTab; IF RefTab.GetSize[newTab] = 0 THEN { <> cir.mergeDirectory _ NIL } <> <> <> <<[] _ RefTab.Pairs[cir.mergeDirectory, CompressMerge];>> <> <<}>> <<}>> } END; -- CompressMergeDirectoryEntries CompressBoxPaths: PROC [qt: REF SXQuadTree.QuadTree] = BEGIN FOR boxes: LIST OF REF SXQuadTree.Rectangle _ qt.boxes, boxes.rest WHILE boxes#NIL DO WITH boxes.first.nodeInformation SELECT FROM inst: CD.Instance => NULL; cn: REF SX.CircuitNode => boxes.first.nodeInformation _ LookupNode[cn]; cc: REF Constraint => NULL; ENDCASE => ERROR; ENDLOOP; FOR quad: SXQuadTree.AreaSplit IN SXQuadTree.AreaSplit DO IF qt.subTrees[quad]#NIL THEN CompressBoxPaths[qt.subTrees[quad]] ENDLOOP; END; <<--Main of Normalize Circuit>> CompressCircuitNodeList[]; CompressLinkages[]; CompressMergeDirectoryEntries[]; FOR layer: SpinifexLayerIndex IN [0..SXAccess.sxTech.numSpinifexLayers) DO IF cir.spinifexLayers[layer].geometry#NIL THEN CompressBoxPaths[cir.spinifexLayers[layer].geometry] ENDLOOP; END; -- Normalise Circuit LookupNode: PUBLIC PROC [node: REF SX.CircuitNode] RETURNS [REF SX.CircuitNode] = <<--Takes the node and returns the most recent version of it.>> <<--Side effect: cleans all intermediate version to point to the most recent one.>> <<--Mark called this "(partial) Galler-Fisher path compression", had a recursive>> <<--solution which was more elegant but slower.>> <> <<--Implements (partial) Galler-Fisher path compression.>> <> <<};>> BEGIN IF node.superceded#NIL THEN { n1: REF SX.CircuitNode _ node; <<--find the actual node>> WHILE node.superceded#NIL DO node _ node.superceded ENDLOOP; <<--now node is the result>> <<--but as side effect, set all superceded fields to point to the result node>> WHILE n1.superceded#NIL DO n2: REF SX.CircuitNode _ n1.superceded; n1.superceded _ node; n1 _ n2; ENDLOOP; }; RETURN [node] END; -- LookupNode CheckNodeInCircuit: PROC [node: REF SX.CircuitNode, circuit: REF Circuit] = BEGIN FOR nl: LIST OF REF SX.CircuitNode _ circuit.nodes, nl.rest WHILE nl#NIL DO IF nl.first = node THEN EXIT; < TerminalIO.WriteRope [ "\n\n*** Spinifex has lost a node. Extracted output might be wrong.\n"]>> REPEAT FINISHED => NULL -- TerminalIO.WriteRope ["~"] ENDLOOP; END; LookupMergeDirectory: PROC [ dir: RefTab.Ref, cn: REF SX.CircuitNode, qual: LIST OF CD.Instance] RETURNS [merge: SX.MergeRecList, newQual: LIST OF CD.Instance] = BEGIN found: BOOL; val: REF ANY; [found, val] _ dir.Fetch[cn]; IF found THEN { <<-- Search mergeList for qual>> FOR mergeList: SX.MergeRecList _ NARROW[val], mergeList.rest WHILE mergeList#NIL DO <<-- Compare mergeList.first.applChain to qual>> qApplChain: LIST OF CD.Instance _ qual; FOR applChain: LIST OF CD.Instance _ 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] END; -- LookupMergeDirectory tiptoe: BOOL _ TRUE; UnMerged: ATOM = $SpinifexPrivateUnMerged; <> FindRootNode: PUBLIC PROC [ circuit: REF Circuit, subcircuitNode: REF SX.CircuitNode, qualifier: LIST OF CD.Instance, insertIfNotInCircuit: BOOL _ FALSE] RETURNS [node: REF SX.CircuitNode, rootQualifier: LIST OF CD.Instance] = BEGIN AddCircuitNodeMerge: PROC [sourceNode: REF SX.CircuitNode, qual: LIST OF CD.Instance] RETURNS [newNode: REF SX.CircuitNode] = BEGIN found: BOOL; mergeList: SX.MergeRecList _ NIL; <> IF circuit.mergeDirectory=NIL THEN { IF insertIfNotInCircuit THEN { <<-- Make it big, it will get cleaned up in NormalizeCircuit anyway.>> circuit.mergeDirectory _ RefTab.Create[521]; -- A prime. found _ FALSE } } ELSE { -- circuit.mergeDirectory # NIL val: REF ANY; [found, val] _ circuit.mergeDirectory.Fetch[sourceNode]; IF found THEN { mergeList _ NARROW[val]; <<--Check we don't already know about it.>> FOR m: SX.MergeRecList _ mergeList, m.rest WHILE m#NIL DO q: LIST OF CD.Instance _ qual; FOR applChain: LIST OF CD.Instance _ 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 _ NEW[SX.CircuitNode _ [NIL, NIL, sourceNode.loc, NIL]]; FOR qa: LIST OF CD.Instance _ qual, qa.rest WHILE qa # NIL DO inst: CD.Instance = qa.first; newNode.loc.xy _ CDOrient.MapPoint[ pointInCell: newNode.loc.xy, cellSize: inst.ob.size, cellInstOrient: inst.orientation, cellInstPos: inst.location ] ENDLOOP; CopyNodeProperties[circuit, newNode, sourceNode.properties, qual]; newNode.properties _ newNode.properties.PutPropOnList[UnMerged, UnMerged]; mergeList _ CONS[[applChain: qual, becomes: newNode], mergeList]; IF RefTab.Store[circuit.mergeDirectory, sourceNode, mergeList] = found THEN ERROR; AddCircuitNode[circuit, newNode] END; -- AddCircuitNodeMerge <> IF qualifier=NIL THEN RETURN [subcircuitNode, NIL]; <> FOR q: LIST OF CD.Instance _ qualifier.rest, q.rest WHILE q#NIL DO subcircuit: REF Circuit _ SXAccessInternal.GetSXData[q.first.ob].circuit; IF subcircuit.mergeDirectory#NIL THEN { tmp: SX.MergeRecList; oldQual: LIST OF CD.Instance _ qualifier; IF tiptoe AND oldQual#NIL THEN { bottomCircuit: REF Circuit _ SXAccessInternal.GetSXData[oldQual.first.ob].circuit; CheckNodeInCircuit [subcircuitNode, bottomCircuit]; }; [merge: tmp, newQual: qualifier] _ LookupMergeDirectory[subcircuit.mergeDirectory, subcircuitNode, qualifier]; IF tmp#NIL THEN { IF oldQual=NIL THEN ERROR; IF qualifier#NIL AND qualifier.first.ob#q.first.ob THEN ERROR; IF tiptoe THEN { CheckNodeInCircuit[tmp.first.becomes, subcircuit]; }; subcircuitNode _ tmp.first.becomes; } } ENDLOOP; <> IF (node _ AddCircuitNodeMerge[sourceNode: subcircuitNode, qual: qualifier])=NIL THEN { node _ subcircuitNode; rootQualifier _ qualifier } ELSE rootQualifier _ NIL END; -- FindRootNode AddCircuitNode: PROC [cir: REF Circuit, cn: REF SX.CircuitNode] = INLINE { cir.nodes _ CONS[cn, cir.nodes] }; CreateLinkage: PUBLIC PROC [cir: REF Circuit, source: CD.Instance, length, width: CD.Number] RETURNS [REF NodeLinkage] = { cir.linkages _ CONS[NEW[NodeLinkage _ [source: source, l: length, w: width]], cir.linkages]; RETURN [cir.linkages.first]; }; LinkageAttach: PUBLIC PROC [ link: REF NodeLinkage, attachType: ATOM, node: REF SX.CircuitNode _ NIL] = { link.nodes _ CONS[NEW[AttachedNode _ [attachType, node]], link.nodes]; }; END. <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <<1st: Extensions to NormalizeCircuit to remove nodes which were inserted by FindRootNode but never actually merged into other nodes in this cell. This is done using a special property UnMerged which is attached to nodes created for subcell nodes and then deleted during merging by CopyNodeProperties. If node is never merged it still has UnMerged property during NormalizeCircuit, and should be removed from both node list and mergeDirectory.>> <<2nd: When first created mergeDirectory is made large (521 entries). During NormalizeCircuit it is remade with slightly more space than required number of entries. This is to improve performance on large designs.>> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <<>>