DIRECTORY Core, CoreClasses, RefTab; CoreFlat: CEDAR DEFINITIONS = BEGIN PathError: ERROR [msg: ROPE _ NIL]; ROPE: TYPE = Core.ROPE; Wire: TYPE = Core.Wire; WireSeq: TYPE = Core.WireSeq; CellType: TYPE = Core.CellType; CellClass: TYPE = Core.CellClass; CellInstance: TYPE = CoreClasses.CellInstance; CutSet: TYPE = REF CutSetRec; CutSetRec: TYPE = RECORD [ instances, cellTypes, cellClasses, labels: LIST OF ROPE _ NIL, flatCells: FlatCellTypes _ NIL, flatten: FlatCellTypes _ NIL, change: FlatCellTypeCutSets _ NIL]; FlatCellTypeCutSets: TYPE = LIST OF FlatCellTypeCutSetRec; FlatCellTypeCutSetRec: TYPE = RECORD [ flatCell: FlatCellTypeRec, cutSet: CutSet _ NIL]; InstancePath: TYPE = RECORD [ length: InstancePathIndex _ 0, bits: PACKED ARRAY InstancePathIndex OF BOOL _ ALL[FALSE]]; InstancePathIndex: TYPE = [0..64); nullInstancePath: InstancePath = []; FlatCellTypes: TYPE = LIST OF FlatCellType; FlatCellType: TYPE = REF FlatCellTypeRec; FlatCellTypeRec: TYPE = RECORD [ path: InstancePath, recastCount: NAT _ 0]; -- do not include recasts that return the same ref rootCellType: FlatCellTypeRec = []; allFlatCells: FlatCellTypeRec = [[], LAST[NAT]]; WireRoot: TYPE = {internal, public, actual}; WirePath: TYPE = RECORD [ length: WirePathIndex _ 0, bits: PACKED ARRAY WirePathIndex OF BOOL _ ALL[FALSE]]; WirePathIndex: TYPE = [0..32); FlatWires: TYPE = LIST OF FlatWire; FlatWire: TYPE = REF FlatWireRec; FlatWireRec: TYPE = RECORD [ flatCell: FlatCellTypeRec _ rootCellType, instanceIndex: NAT _ 0, wireRoot: WireRoot _ internal, validPath: BOOL _ FALSE, path: WirePath, wire: Wire _ NIL]; Bindings: TYPE = RefTab.Ref; CellInstanceCutLabels: PROC [on: CellInstance, l1, l2, l3, l4, l5, l6: ROPE _ NIL] RETURNS [same: CellInstance]; CellInstanceCutLabelList: PROC [on: CellInstance, labels: LIST OF ROPE] RETURNS [same: CellInstance]; CellTypeCutLabels: PROC [on: CellType, l1, l2, l3, l4, l5, l6: ROPE _ NIL] RETURNS [same: CellType]; CellTypeCutLabelList: PROC [on: CellType, labels: LIST OF ROPE] RETURNS [same: CellType]; CellClassCutLabels: PROC [on: CellClass, l1, l2, l3, l4, l5, l6: ROPE _ NIL] RETURNS [same: CellClass]; CellClassCutLabelList: PROC [on: CellClass, labels: LIST OF ROPE] RETURNS [same: CellClass]; CreateCutSet: PROC [instances, cellTypes, cellClasses, labels: LIST OF ROPE _ NIL, flatCells: FlatCellTypes _ NIL, flatten: FlatCellTypes _ NIL, change: FlatCellTypeCutSets _ NIL] RETURNS [cutSet: CutSet]; CutSetMember: PROC [root: CellType, flatCell: FlatCellTypeRec, cutSet: CutSet] RETURNS [member: BOOL]; CutSetMemberResolved: PROC [flatCell: FlatCellTypeRec, instance: CellInstance, cellType: CellType, cutSet: CutSet] RETURNS [member: BOOL]; ParseInstancePath: PROC [root: CellType, pathRope: ROPE, cutSet: CutSet _ NIL] RETURNS [path: InstancePath]; InstancePathRope: PROC [root: CellType, path: InstancePath] RETURNS [pathRope: ROPE]; InstancePathEqual: PROC [one, other: InstancePath] RETURNS [equal: BOOL]; InstancePathHash: PROC [path: InstancePath] RETURNS [hash: CARDINAL]; AddInstance: PROC [currentPath: InstancePath, instance: CoreClasses.CellInstance, parent: CellType] RETURNS [newPath: InstancePath]; ExtendPath: PROC [currentPath: InstancePath, index: NAT, rct: CoreClasses.RecordCellType] RETURNS [newPath: InstancePath]; BindInstance: PROC [parent: FlatCellTypeRec, actual, public: WireSeq, bindings: Bindings] RETURNS [newBindings: Bindings]; RaiseRootOfInstancePath: PROC [by, path: InstancePath] RETURNS [raised: InstancePath]; ParseCellTypePath: PROC [root: CellType, pathRope: ROPE, cutSet: CutSet _ NIL] RETURNS [flatCell: FlatCellTypeRec]; CellTypePathRope: PROC [root: CellType, flatCell: FlatCellTypeRec] RETURNS [pathRope: ROPE]; FlatCellTypeEqual: RefTab.EqualProc; FlatCellTypeEqualRec: PROC [one, other: FlatCellTypeRec] RETURNS [equal: BOOL]; FlatCellTypeHash: RefTab.HashProc; FlatCellTypeHashRec: PROC [flatCell: FlatCellTypeRec] RETURNS [hash: CARDINAL]; ResolveFlatCellType: PROC [root: CellType, flatCell: FlatCellTypeRec] RETURNS [parent: CellType, instance: CellInstance, cellType: CellType]; BoundFlatCellType: PROC [root: CellType, flatCell: FlatCellTypeRec] RETURNS [bindings: Bindings, instance: CellInstance, cellType: CellType]; FindAnyFlatCell: PROC [root: Core.CellType, cellType: Core.CellType] RETURNS [flatCellType: CoreFlat.FlatCellTypeRec _ []]; RaiseRootOfFlatCell: PROC [by: InstancePath, flatCell: FlatCellTypeRec] RETURNS [raised: FlatCellTypeRec]; ParseWirePath: PROC [root: CellType, pathRope: ROPE, cutSet: CutSet _ NIL] RETURNS [flatWire: FlatWireRec]; WirePathRope: PROC [root: CellType, wire: FlatWireRec] RETURNS [pathRope: ROPE]; FlatWireEqual: RefTab.EqualProc; FlatWireEqualRec: PROC [one, other: FlatWireRec] RETURNS [equal: BOOL]; FlatWireHash: RefTab.HashProc; FlatWireHashRec: PROC [wire: FlatWireRec] RETURNS [hash: CARDINAL]; CanonizeWire: PROC [root: CellType, child: FlatWireRec] RETURNS [parent: FlatWireRec]; RaiseRootOfFlatWire: PROC [by: InstancePath, flatWire: FlatWireRec] RETURNS [raised: FlatWireRec]; NextUnboundCellType: PROC [cell: CellType, target: FlatCellTypeRec, flatCell: FlatCellTypeRec, instance: CellInstance, index: NAT, parent: CellType, flatParent: FlatCellTypeRec, data: REF ANY, proc: UnboundFlatCellProc]; UnboundFlatCellProc: TYPE = PROC [cell: CellType, target: FlatCellTypeRec _ allFlatCells, flatCell: FlatCellTypeRec _ [], instance: CellInstance _ NIL, index: NAT _ LAST[NAT], parent: CellType _ NIL, flatParent: FlatCellTypeRec _ [], data: REF ANY _ NIL]; NextBoundCellType: PROC [cell: CellType, target: FlatCellTypeRec, flatCell: FlatCellTypeRec, instance: CellInstance, index: NAT, parent: CellType, flatParent: FlatCellTypeRec, data: REF ANY, bindings: Bindings, proc: BoundFlatCellProc]; BoundFlatCellProc: TYPE = PROC [cell: CellType, target: FlatCellTypeRec _ allFlatCells, flatCell: FlatCellTypeRec _ [], instance: CellInstance _ NIL, index: NAT _ LAST[NAT], parent: CellType _ NIL, flatParent: FlatCellTypeRec _ [], data: REF ANY _ NIL, bindings: Bindings _ NIL]; InitialBindingTable: PROC [root: CellType] RETURNS [bindings: Bindings]; END. úCoreFlat.mesa Copyright Ó 1985, 1987 by Xerox Corporation. All rights reserved. Barth, June 19, 1987 12:39:56 pm PDT Spreitzer, April 8, 1986 4:29:29 pm PST Bertrand Serlet March 28, 1987 11:10:19 pm PST Mike Spreitzer February 27, 1987 2:39:53 pm PST Last tweaked by Mike Spreitzer on November 2, 1987 3:51:48 pm PST Theory This interface supports the enumeration of cell types reachable from a root cell type and syntatic sugar for describing textually the hierarchical structure. A cut set defines a slice through the instantiation tree. It controls the boundaries of the design which can be explored by the enumeration and parsing procedures. The limitation of the search space is needed to prevent unwanted recasting which may be very expensive or impossible to compute. A cut is a place in the instantiation tree beyound which the design is not to be explored if the cut is a member of the current cut set. A cut set may contain a collection of any of a specific flat cell type, the name of a cell type, the name of a cell class, or a rope that specifies a cut label. Cut labels may be placed on cell instances, cell types, and cell classes. Cell types, instances, and wires may be named with ropes and data structures defined by this interface. Procedures are provided to convert from a rope to a data structure and back again. The following grammar gives the syntax for each type of name. Syntax Notation item | item = choose one ?item = zero or one item SMALL CAPS or puncuation other than bold ()?| = terminals ::= = keyword on left hand side is defined by expression on right hand side Grammar InstancePath ::= ?( / ( Name | (Number ?( ( Name ) )) ) ?( InstancePath ) ) CellTypePath ::= CellTypeLeftSide ?(* ( Name | (Number ?( ( Name ) ))) CellTypeLeftSide ::= CellTypePath | InstancePath WirePath ::= WireLeftSide ( ( . ( Name | Number )) | ( [Number] ) ) WireLeftSide ::= WirePath | ( CellTypePath ?( . (PUBLIC | INTERNAL | ACTUAL))) Name ::= Letter ?LetterDigitString LetterDigitString ::= (Letter | Digit) ?LetterDigitString Number ::= Digit ?Number Letter ::= one of a-z | one of A-Z Digit ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Grammar Notes White space may appear anywhere except inside Name or Number. Reserved words are matched ignoring case. ACTUAL causes the wire path to begin at the actual of the last instance of the instance path and then use the public names of the last cell type to index the actual. PUBLIC and INTERNAL cause the wire path to begin at the public or internal of the last cell type. If none of ACTUAL, PUBLIC, or INTERNAL appear then INTERNAL is assumed. The name in the instance path may be the instance name or, if unambiguous, the cell type name. The name in parantheses in the InstancePath rule must be the cell type name. A name in the CellTypePath rule must be the name of a cell class into which the cell type may be recasted. The number in a cell type path is the number of times the cell type is recasted to get to the named cell type. When a cell class name appears the cell type is recasted until the cell class named is found. Types Instance An InstancePath can only be interpreted given a root cell type. An InstancePath contains the same information as an InstantiationPath but in a more compact form. Clients should not need to interpret an instance path directly. They should use the procedures in this interface. Caution!!! Look at the implementation of InstancePathEqual and InstancePathHash before changing this type!!! Cell Type Wire flatCell names the CellType which contains the wire as an internal or public. IF wireRoot=actual THEN instanceIndex says of which instance of flatCell the wire is an actual. The wirePath is for clients which wish to keep track of exactly how this wire was reached from the wire root. ParseWirePath sets this field and then sets validPath to TRUE. No procedure in this interface relies on validPath being TRUE. A number of procedures in this interface have bindings as arguments or results. The bindings are hash tables which have wires for keys and FlatWires for values. The value in a binding indicates to which wire the key is bound. Cut Sets instances, cellTypes, cellClasses, labels are all short ropes which identify a cell type which is not to be flattened. The labels are attached to any of instances, cellTypes, or cellClasses with the above defined procedures. The instance and cellType ropes refer to short names, not CoreFlat path names. flat cell types listed in the flatten argument will be flattened even if they are included in the cut set due to some other label or name. This allows flattening a particular instance of a cell type when the cell type is marked as a cut point. The change argument allows the cut set to be changed when a particular instance of a cell type is encountered. change has precedence over flatten which has precedence over instances, cellTypes, cellClasses, labels, and flatCells. Returns TRUE if the flatCell is a member of the cutset. Faster version of CutSetMember for clients that already know the instance and cellType of flatCell. Instances Given the current path to a parent, the RecordCellType of the parent, and the index of an instance in the RecordCellType, extends the old path to include the instance. Creates a new binding table which contains only the public wires as keys. raised is the concatenation of by and path (in that order). CellTypes Parameters of this function are two REFs that must be of type FlatCellType. It is supplied to help create RefTabs indexed by FlatCellTypes. Parameters of this function are two REFs that must be of type FlatCellType. It is supplied to help create RefTabs indexed by FlatCellTypes. parent and instance may be NIL if flatCell is the root or a recast of it. parent.class=CoreClasses.recordCellClass Creates bindings which contain only the public wires as keys. Construct a path to the cell type. Wires Parameters of this function are two REFs that must be of the type FlatWire. It is supplied to help create RefTabs indexed by FlatWires. Parameters of this function are two REFs that must be of the type FlatWire. It is supplied to help create RefTabs indexed by FlatWires. Discovers the leftmost, highest wire to which the wire is bound. Enumeration This is a prototype for using the enumeration procedures. Flatten: PROC [root: CellType] = { FlattenCell: CoreFlat.BoundFlatCellProc = { IF -- cell is not a leaf cell -- THEN { -- Handle nonleaf cells here. -- Handle initialization prior to visiting children here. IF cell.class=CoreClasses.recordCellClass THEN { -- Handle special initialization for record cells here. }; CoreFlat.NextBoundCellType[cell, target, flatCell, instance, parent, flatParent, bindings, FlattenCell] -- Handle cleanup after visiting children here. } ELSE { -- Handle leaf cells here. }; }; FlattenCell[root]; }; Moves from CellType to CellType according to the Core hierarchy by Recasting and enumerating children. May be directed by target, or made to explore all by target=allFlatCells. [instance, cell] = ResolveFlatCellType[root, flatCell]. index is the number of the instance in the parent record cell type. [, parent] = ResolveFlatCellType[root, flatParent]. The flatCell is a child of flatParent, possibly recasted some. Except when the flatCell is (a Recast of) the root, in which case flatParent=rootCellType and parent=NIL. data is for client use. It is passed through unmodified to proc. Same invariants apply. Normally a procedure of this type is called with the root cell type to start the recursion. If cell=instance.type then a new recast chain is starting. If index is the default value then the index is unknown. Same as UnboundFlatCellProc but bindings are included. Only public wires of cell are in the bindings. The root call to start the recursion has bindings=NIL. Makes entries for all the public wires of root. Ê 7˜codešœ ™ KšœB™BK™$K™'K™.K™/K™A—K™šÏk œ˜$K˜—KšÏnœœ œ˜#head™Ibody™Mšœ™M™û™MšœÏbœ™MšŸœ™Mš œŸœ ™9MšŸœH™K—Lšœ™IitemšŸœŸœŸœŸœŸœŸœ ŸœŸœŸœ Ÿ™LNš ŸœŸœŸœŸœŸœŸœ Ÿ™FNšŸœŸœ ™1Nš Ÿ œŸœŸœŸœŸœ Ÿ™CNšŸœ ŸœŸœŸœŸœŸœœŸœŸ™NN™NšŸ œŸœ™"NšŸœŸœŸœ™9NšŸ œŸœ™NšŸ œ Ÿœ ™"NšŸ œœŸŸŸŸŸŸŸŸŸ™/šœ ™ Mšœ.ŸœŸœ.œ¡œœ[œœœ œõ™¤K˜—Kšœ œœœ˜#—™Kšœœœ˜Kšœœ ˜Kšœ œ˜Kšœ œ˜Kšœ œ˜!Kšœœ˜.K˜Kšœœœ ˜šœ œœ˜Kš œ+œœœœ˜>Kšœœ˜Kšœœ˜šœœ˜#K˜——Kšœœœœ˜:šœœœ˜&K˜Kšœœ˜K˜—™Mšœ–™–K™šœœœ˜Kšœ˜Kš œœœœœœœ˜;K˜—šœœ ˜"Kšœm™m—K˜šœ$˜$K™——™ Kšœœœœ˜+Kšœœœ˜)šœœœ˜ Kšœ˜Kšœ œÏc2˜J—K˜Kšœ#˜#šœ%œœ˜0K˜——™šœ œ˜,K˜—šœ œœ˜Kšœ˜Kš œœœœœœœ˜7—K˜šœœ ˜K™—Kšœ œœœ ˜#Kšœ œœ ˜!šœ œœ˜Kšœ)˜)Kšœœ˜K˜Kšœ œœ˜Kšœ˜Kšœ œ˜Kš œOœœòœ<œ™K˜—šœ œ˜K™ãK˜———™š žœœ,œœœ˜pJ˜—š žœœœœœœ˜eJ˜—š žœœ(œœœ˜dJ˜—š žœœœœœœ˜YJ˜—š žœœ)œœœ˜gJ˜—š žœœœœœœ˜\J˜—šž œœ-œœœœœœ œœ˜ÍKšœ™K˜—šž œœ=œ œ˜fKšœœ+™7K˜—šžœœYœ œ˜ŠKšœc™cK˜——™ š žœœœœœ˜lK˜—šžœœ&œ œ˜UK˜—šžœœœ œ˜IK˜—šžœœœœ˜EK˜—šž œœSœ˜„K˜—šž œœ$œ#œ˜zKšœ§™§K™—šž œœHœ˜zK™IK˜—šžœœœ˜VKšÏeœ¡œ¡œ™;——™ š žœœœœœ˜sK˜—šžœœ-œ œ˜\K˜—šžœ˜$Jšœ$œd™ŒK˜—šžœœœ œ˜OK˜—šžœ˜"Jšœ$œd™ŒK˜—šžœœœœ˜OK˜—šžœœ-œ@˜KšœœU™sK˜—šžœœ-œB˜Kšœ=™=K˜—šžœœ0œ/˜{K™"K˜—Kšžœœ/œ˜j—™š ž œœœœœ˜kK˜—šž œœ%œ œ˜PK˜—šž œ˜ Jšœ$œ œ4 œ™ˆK˜—šžœœœ œ˜GK˜—šž œ˜Jšœ$œ œ4 œ™ˆK˜—šžœœœœ˜CK˜—šž œœ&œ˜VK™@K˜—šžœœ+œ˜bK˜——™ ™Kšœ9™9K™šžœœ™"K™šž œ ™+šœœ™'K™K™9™0K™7K™—Kšœg™gK™/K™—šœ™Kšœ™Kšœ™—Kšœ™K™—Kšœ™K™K™——š žœœeœ7œœ˜ÜKšœ±™±Kšœ7™7K™CKšœ3™3Kšœì™ìK˜šœœœsœ œœœœ*œœœ˜ÿKšœé™éK˜——š žœœeœ7œœ/˜ìK˜šœœœsœ œœœœ*œœœœ˜—Jšœš™žK˜——šžœœœ˜HK™/K™——Kšœ˜—…—þA/