[_CD4_]<datools7.0>Extract>CoreGeometry.mesa!10

CoreGeometry.mesa

Copyright Ó 1986, 1987 by Xerox Corporation. All rights reversed.

Created by Bertrand Serlet August 6, 1986 0:38:23 am PDT

Bertrand Serlet September 14, 1987 11:22:41 pm PDT

DIRECTORY CD, CDAtomicObjects, CDBasicsInline, Core, CoreClasses, CoreFlat, DABasics, RefTab;

CoreGeometry: CEDAR DEFINITIONS IMPORTS CDBasicsInline = BEGIN

Theory and Trade-offs

This interface defines how to attach geometry onto Core data structures. Geometry is represented using ChipNDale data types, for convenience and easy links to the editor. All instances are expressed in the CD coordinate system of the parent object.

Two kinds of decorations are defined in this interface:

Interface decorations: The geometric interface of a decorated CellType consists in its pins (attached on each public wire), and its object (the corresponding CD object).

Private decorations: Record cells and transistors record the geometry of the internal wires (but only the geometry found at that level), and record cells also record the geometrical transformation for each CellInstance.

Previous experience has shown that, if pins are stored in the trivial way [Instances], most of the memory goes into those pins, and that seriously limits the size of designs the DA system can handle. Therefore, it is important to be able to store pins in a lazy way: every time the time penalty is not too important, recompute pins instead of storing them. Enumerations are prefered to explicit lists for both storage efficiency [enumerations create less objects] and time efficiency [enumerations may return early].

Common cases when pins can be recomputed:

Indirection: pins of a given wire are the same as the ones of some other wire. This is heavily used in PWCore that generates lots of indirections. The time penalty in that case is a constant time.

Indirection and transformation: pins of a given wire are the same as the ones of some other wire, once applied a geometrical transformation. This case is very frequent for abuts (think of the vertical wires of lines). The time penalty is a constant time.

Routing Cell: both pins and geometry can be deduced from the routing object itself.

RecordCell: pins of a public of a RecordCell can always be obtained by enumerating the instances to which the public is bound, assuming that some geometric transformations and some clipping are done. This is of course a very common case, but the time penalty might be quite high (looping both on instances and bindings).

Common case when it is better to store explicitly pins:

Small number of instances.

The implementation of this interface tries to make the best space/time trade-offs using those heuristics.

Conveniences

CellType : TYPE = Core.CellType;

Properties : TYPE = Core.Properties;

ROPE: TYPE = Core.ROPE;

Wire: TYPE = Core.Wire;

CellInstance: TYPE = CoreClasses.CellInstance;

FlatWire: TYPE = CoreFlat.FlatWire;

FlatWireRec: TYPE = CoreFlat.FlatWireRec;

FlatCellType: TYPE = CoreFlat.FlatCellType;

FlatCellTypeRec: TYPE = CoreFlat.FlatCellTypeRec;

Bindings: TYPE = CoreFlat.Bindings;

InstancePath: TYPE = CoreFlat.InstancePath;

Types defining Geometry

Rect: TYPE = DABasics.Rect;

Layer: TYPE = CD.Layer;

Object: TYPE = CD.Object;

The classes of objects found in decorations depend on the producers of the decorated Core data structure. FlattenInstance allows programs dealing with masks to only know about rectangles, even though they might want to know about other classes of objects.

As an example, the standard CMosB extractor generates pins and geometry decorations containing the following classes: rectangles, symbolic objects, contacts, diffusion rectangles, cells. FlattenInstance knows how to expand all the previous categories except rectangles. A DRC program will probably want to deal with rectangles, contacts, and diffusion rectangles, and leave the rest to FlattenInstance.

Transformation: TYPE = CD.Transformation;

Instance: TYPE = RECORD [obj: Object, trans: Transformation];

Instances: TYPE = LIST OF Instance;

Decoration and other Types

Decoration: TYPE = REF DecorationRec;

Decoration holds names of properties.

Should only be created by CreateDecoration

Definition of DecorationRec is only given for implementors' information. Access to all decorations should only be made via the procedural interface.

DecorationRec: TYPE = PRIVATE RECORD [

name: ROPE, -- Documentation purpose only

pinsProp: ATOM, -- Hangs on each public wire to specify the pins of the public. Pins should be understood as the more general meaning of "interface geometry", and are not only pins but also contacts, rectangles...

objectProp: ATOM, -- Hangs on some cellTypes to specify the corresponding object. Currently only cellTypes of the recordCellClass and transistors have this decoration.

geometryProp: ATOM, -- Hangs on every internal wires of record cellTypes to specify the geometry of the internal (but only at this level in the record).

transProp: ATOM, -- hangs on every CoreClasses.CellInstance of record cellTypes to specify the corresponding transformation.

expandPinsCount: INT ← 3 -- allows playing with space/time tradeoffs

];

CreateDecoration: PROC [name: ROPE] RETURNS [decoration: Decoration];

Initializes of the fields of decoration properly.

All decorations must have different names (because properties atoms are computed using name).

Currently, the only clients are the one registering an extraction mode. A handle on an existing decoration can be found in an extraction mode.

EachInstanceProc: TYPE = PROC [instance: Instance] RETURNS [quit: BOOL ← FALSE];

LazyEnumerateProc: TYPE = PROC [eachInstance: EachInstanceProc, data1, data2: REF ← NIL] RETURNS [quit: BOOL ← FALSE];

Pins

In this section public stand for any wire, atomic or not, part of the public. All the functions of this section apply to publics of any cellType.

EnumeratePins: PROC [decoration: Decoration, public: Wire, eachInstance: EachInstanceProc] RETURNS [quit: BOOL];

Enumerates all the pins of public.

Instances can be enumerated more than once.

CountPins: PROC [decoration: Decoration, public: Wire] RETURNS [count: INT ← 0];

Counts the number of pins

HasPins: PROC [decoration: Decoration, public: Wire] RETURNS [BOOL];

Tests for public decorated with at least a pin.

GetPins: PROC [decoration: Decoration, public: Wire] RETURNS [pins: Instances];

Inefficient proc for clients who really want to create all those instances.

Instances can be enumerated more than once.

May change the internal representation of pins to increase space/time efficiency.

PutPins: PROC [decoration: Decoration, public: Wire, pins: Instances];

Used for explicitly setting pins of a public. Previous pins discarded.

See further for lazyness.

AddPins: PROC [decoration: Decoration, public: Wire, pins: Instances];

Used for explicitly adding pins to the ones already on public.

No action is taken if pins=NIL.

See further for lazyness.

Object

All the functions of this section apply to any cellType.

HasObject: PROC [decoration: Decoration, cellType: CellType] RETURNS [BOOL];

GetObject: PROC [decoration: Decoration, cellType: CellType] RETURNS [object: Object];

PutObject: PROC [decoration: Decoration, cellType: CellType, object: Object];

Geometry

All the functions of this section apply to internals of record cells, or to publics of transistors.

EachFlatWireProc: TYPE = PROC [wire: Wire, flatWire: FlatWireRec, trans: Transformation] RETURNS [quit: BOOL ← FALSE];

trans is the current transformation, expressed in the coordinate system of root, for flatCell.

flatWire is the canonized FlatWireRec at the highest level that defines wire.

EachFlatCellProc: TYPE = PROC [bindings: Bindings, cell: CellType, flatCell: FlatCellTypeRec, trans: Transformation] RETURNS [quit: BOOL ← FALSE];

bindings is a HashTable [public of cellType -> CoreFlat.FlatWire]. When cell=root, bindings=NIL

trans is the current transformation, expressed in the coordinate system of root, for flatCell.

LeafProc: TYPE = PROC [cellType: CellType, bindings: Bindings] RETURNS [BOOL];

TRUE stops enumeration and this cellType is not explored recursively.

EnumerateFlatGeometry: PROC [decoration: Decoration, root: CellType, target: FlatCellTypeRec ← CoreFlat.allFlatCells, leafProc: LeafProc, eachFlatWire: EachFlatWireProc ← NIL, eachFlatCell: EachFlatCellProc ← NIL] RETURNS [quit: BOOL];

Enumerates all wires and all instances under root.

When target is present, only enumerates wires and cells below target.

Call-back proc leafProc is called to direct recursion.

Call-back proc eachFlatWire gives as argument the geometry (transformed to be in root coordinate system). All enumerations are stopped if eachFlatWire RETURNS TRUE.

Call-back proc eachFlatCell gives as argument the current trans (transformed to be in root coordinate system). All enumerations are stopped if eachFlatWire RETURNS TRUE.

Instances can be enumerated more than once.

EnumerateAllGeometry: PROC [decoration: Decoration, cell: CellType, wire: Wire, eachInstance: EachInstanceProc] RETURNS [quit: BOOL];

Given a specified wire of cell, enumerates all the instances that comprise that wire.

Instances can be enumerated more than once.

EnumerateGeometry: PROC [decoration: Decoration, wire: Wire, eachInstance: EachInstanceProc] RETURNS [quit: BOOL];

Enumerates all the geometry of wire.

Instances can be enumerated more than once.

May change the internal representation of geometry to increase space/time efficiency.

HasGeometry: PROC [decoration: Decoration, wire: Wire] RETURNS [BOOL];

Tests for wire decorated with at least an instance.

GetGeometry: PROC [decoration: Decoration, wire: Wire] RETURNS [geometry: Instances];

Inefficient proc for clients who really want to create all those instances.

PutGeometry: PROC [decoration: Decoration, wire: Wire, geometry: Instances];

Used for explicitly setting geometry of a wire. Previous geometry discarded.

See further for lazyness.

AddGeometry: PROC [decoration: Decoration, wire: Wire, geometry: Instances];

Used for explicitly adding geometry to the one already on wire.

See further for lazyness.

Transformation

All the functions of this section apply only to CellInstances of record cells.

HasTrans: PROC [decoration: Decoration, cellInstance: CellInstance] RETURNS [BOOL];

For record decorations only.

GetTrans: PROC [decoration: Decoration, cellInstance: CellInstance] RETURNS [trans: Transformation];

For record decorations only.

PutTrans: PROC [decoration: Decoration, cellInstance: CellInstance, trans: Transformation];

For record decorations only.

Enumeration of Sides for Routers

These functions are not primitive, and are implemented using primitives of this interface. They are applicable for all Core data structures decorated with layout (not for structures not yet decorated), and should simplify the task of interfacing routers.

Pin should be understand, for the following functions, in the sense of segment of interface geometry. Min and Max refer to the interesting projection in X or Y (depending on the side of the pin), relatively to the InterestRect of the object. Note that the coordinate system is different from the other functions in this interface.

The only classes of decorations understood by these functions are rectangles, symbolic objects, atomic objects, and objects for which FlattenInstance is meaningful. Layers without a $RoutingLayer property are discarded.

Side: TYPE = DABasics.Side;

Sides: TYPE = DABasics.Sides;

noSide: Sides = DABasics.noSide;

GetSides: PROC [ir: Rect, pin: Instance] RETURNS [sides: Sides ← noSide];

EachPinProc: TYPE = PROC [min, max: INT, side: Side, layer: CD.Layer] RETURNS [quit: BOOL ← FALSE];

EnumerateSides: PROC [decoration: Decoration, cellType: CellType, wire: Wire, eachPin: EachPinProc] RETURNS [quit: BOOL];

Enumerates all the pins for wire.

EachWirePinProc: TYPE = PROC [wire: Wire, min, max: INT, side: Side, layer: CD.Layer] RETURNS [quit: BOOL ← FALSE];

EnumerateWireSides: PROC [decoration: Decoration, cellType: CellType, eachWirePin: EachWirePinProc] RETURNS [quit: BOOL];

Enumerates all the pins of the public wires of cellType.

May enumerate several times the overlapping segments.

EnumerateNonOverlappingSides: PROC [decoration: Decoration, cellType: CellType, eachWirePin: EachWirePinProc] RETURNS [quit: BOOL];

Enumerates all the pins of the public wires of cellType, but enumerates once only segments that overlap.

EachSortedPinProc: TYPE = PROC [wire: Wire, min, max: INT, layer: CD.Layer] RETURNS [quit: BOOL ← FALSE];

EnumerateSortedSides: PROC [decoration: Decoration, cellType: CellType, side: Side, eachSortedPin: EachSortedPinProc] RETURNS [quit: BOOL];

Enumerates all the pins of all the wires for cellType. Segments are enumerated in increasing min order.

Fabrication of Shells for Routers or for IO

This function is also not primitive, but can be used by several different programs.

CreateShell: PROC [decoration: Decoration, cellType: CellType, withCuteFonts: BOOL ← FALSE] RETURNS [shell: Object];

Creates a CD cell that contains instances which correspond to the pins of the publics of cellType. Each CD instance has an $SignalName property which is the (public) full name of the wire.

Parameter withCuteFonts provokes, when TRUE, creation of text in front of each instance.

The shell has an InterestRect of the same size as the cellType interestRect.

Checking of Decorations

CheckInterface: PROC [decoration: Decoration, cellType: CellType] RETURNS [ok: BOOL];

Checks that cellType has a object and that all its atomic public are decorated.

CheckInternal: PROC [decoration: Decoration, record: CellType] RETURNS [ok: BOOL];

Checks that all the atomic public are decorated, and that each cell Instance has a transformation.

Lazy Setting of Pins

PutLazyPins: PROC [decoration: Decoration, public: Wire, lazyPinsEnumerate: LazyEnumerateProc, data1, data2: REF ← NIL];

Parameter lazyPinsEnumerate is the function that is called when enumeration of pins of public is called. Typically this function will use data1 and data2 to do the enumeration.

PutIndirectLazyPins: PROC [decoration: Decoration, public: Wire, indirect: Wire];

Special speed-up of PutLazyPins for pins that are obtained by enumerating the pins of another Wire.

Enumeration assumes that indirect is properly decorated.

PutIndirectsLazyPins: PROC [decoration: Decoration, public: Wire, indirects: LIST OF Wire];

Special speed-up of PutLazyPins for pins that are obtained by enumerating the pins of some other Wires.

Enumeration assumes that indirects are properly decorated.

AddIndirectLazyPins: PROC [decoration: Decoration, public: Wire, indirect: Wire];

Special speed-up of PutLazyPins for pins that are "also" obtained by enumerating the pins of some other Wire. If public was already decorated by PutIndirectLazyPins or PutIndirectsLazyPins, this indirect is added (if not already present) other, pins are explicitly stored.

Enumeration assumes that indirect is properly decorated.

PutTransWireIRLazyPins: PROC [decoration: Decoration, public: Wire, indirect: Wire, trans: Transformation, ir: Rect];

Special speed-up of PutLazyPins for pins that are obtained by enumerating the pins of another Wire, once transformed by trans, and clipped to be at the edge of ir.

Enumeration assumes that indirect is properly decorated.

PutRecordLazyPins: PROC [decoration: Decoration, record: CellType, ir: Rect];

Special speed-up of PutLazyPins for pins that are obtained by following the bindings of a record.

It is assumed that the instances of the record are properly decorated.

Lazy Setting of Geometry

PutLazyGeometry: PROC [decoration: Decoration, internal: Wire, lazyGeometryEnumerate: LazyEnumerateProc, data1, data2: REF ← NIL];

Parameter lazyPinsEnumerate is the function that is called when enumeration of geometry of internal is called. Typically this function will use data1 and data2 to do the enumeration.

Touch Procs

TouchProc: TYPE = PROC [touch: TouchProc, instance1, instance2: Instance] RETURNS [BOOL ← FALSE];

Returns TRUE if instance1 touches instance2.

A strong assumption made all over the code is that instances with non-overlapping bbox can not touch.

Function is passed itself for recursive calls with simpler instances.

Touch: TouchProc;

Technology-independent, only meaningful for Layout. Understands Rectangles, Symbolic Objects and objects for which FlattenInstance is meaningful.

TouchRect: PROC [touch: TouchProc, instance: Instance, rect: Rect, layer: CD.Layer] RETURNS [BOOL ← FALSE];

Only meaningful for Layout. Returns TRUE if instance touches rect.

TouchList: PROC [touch: TouchProc, instances: Instances, instance: Instance] RETURNS [BOOL ← FALSE];

Returns TRUE if some instance of instances touches instance.

TouchListList: PROC [touch: TouchProc, instances1, instances2: Instances] RETURNS [BOOL ← FALSE];

Returns TRUE if some instance of instances1 touches some instance of instances2.

EnumerateNeighbors: PROC [decoration: Decoration, touch: TouchProc, inX: BOOL, ct1, ct2: CellType, eachPair: PROC [Wire, Wire] RETURNS [quit: BOOL ← FALSE]] RETURNS [BOOL];

Enumerate all pairs of public for which some pin of ct1 touches some pin of ct2, after the appropriate transformation.

Pairs might be enumerated multiple times.

Not very efficient for numerous decorations.

WirePair: TYPE = RECORD [wire1, wire2: Wire];

CreateNeighborsCache: PROC RETURNS [cache: RefTab.Ref];

Creates a Cache for CachedEnumerateNeighbors

CachedEnumerateNeighbors: PROC [decoration: Decoration, touch: TouchProc, inX: BOOL, ct1, ct2: CellType, cache: RefTab.Ref] RETURNS [LIST OF WirePair];

Same as EnumerateNeighbors, but uses a global cache for neighbors.

Pairs are unique within the list.

Geometry Utilities

Length: PROC [instances: Instances] RETURNS [count: INT ← 0];

BBox: PROC [instance: Instance] RETURNS [rect: Rect];

InlineBBox: PROC [instance: Instance] RETURNS [rect: Rect] =

INLINE {rect ← CDBasicsInline.MapRect[instance.obj.bbox, instance.trans]};

AtEdge: PROC [ir: Rect, instance: Instance] RETURNS [BOOL];

Returns TRUE iff instance touches or extends beyond ir.

TransfedNotAtEdge: PROC [trans: Transformation, ir: Rect, instance: Instance] RETURNS [BOOL];

Returns FALSE (opposite of previous AtEdge) iff instance, once applied trans, touches or extends beyond ir.

Semantically identical to, but more efficient than:

NOT AtEdge[ir, Transform[trans, instance]].

Intersect: PROC [clipRect: Rect, instance: Instance] RETURNS [BOOL];

Returns TRUE iff instance is partly inside (or touches) clipRect.

Transform: PROC [trans: Transformation, instance: Instance] RETURNS [Instance];

Transforms instance using trans.

TransformList: PROC [trans: Transformation, instances: Instances] RETURNS [Instances];

Transforms instances using trans. New list is created.

Order not preserved.

DrawListToInstances: PROC [drawList: CDAtomicObjects.DrawList] RETURNS [Instances];

Converts from one data structure to the other!

FlattenInstance: PROC [instance: Instance, eachInstance: EachInstanceProc] RETURNS [quit: BOOL ← FALSE];

Convenience to reduce the number of primitive objects programs dealing with masks have to know.

FlattenInstance[instance of a symbolic object] -> NIL

FlattenInstance[instance of an atomic object] -> called back on each individual component

FlattenInstance[instance of an cell] -> called back on each individual component

FlattenInstance[instance of a rectangle of material] -> ERROR

The following functions allow easy hacking with CDSymbolic objects. Please, do not ask me why I had to to it...

CDPinToCoreGeometryPin: PROC [cdPin: CD.Object, props: CD.PropList] RETURNS [coreGeometryPin: Object];

CoreGeometryPinToCDPin: PROC [coreGeometryPin: Instance] RETURNS [cdPin: CD.Instance];

IsCoreGeometryPin: PROC [coreGeometryPin: Object] RETURNS [BOOL];

GetCoreGeometryPinLayer: PROC [coreGeometryPin: Instance] RETURNS [layer: CD.Layer];

END.