SXOutputImplB.mesa
Copyright © 1984, 1985 by Xerox Corporation. All rights reserved.
Written by Shand, July 16, 1984 2:58:45 pm PDT
Last Edited by: Shand, March 10, 1985 11:11:35 pm PST
Last edited by: gbb June 6, 1986 4:33:51 pm PDT
Last Edited by: Spreitzer, January 16, 1985 12:04:51 pm PST
Last Edited by: Jacobi, April 5, 1985 3:54:25 pm PST
DIRECTORY
Basics USING [CompareINT, Comparison],
CD USING [Instance, InstanceList, InterestRect, Number, Object, Orientation, Position, Rect],
CDBasics USING [RectAt],
CDInstances USING [InstRectO],
CDOrient USING [CreateTransform, MapRect],
CDProperties USING [GetProp, GetInstanceProp, PutInstanceProp, PutObjectProp],
FS USING [StreamOpen],
ImagerTransformation USING [Transformation],
IO USING [atom, Close, int, PutF, PutFR, PutRope, real, refAny, rope, STREAM, time],
PropertyLists USING [GetProp, PropList, PutProp],
Real USING [Fix],
RedBlackTree USING [Compare, Create, DestroyTable, DuplicateKey, GetKey, Insert, LookupLargest, LookupNextSmaller, Table],
RefTab USING [Fetch, Key, Pairs, Ref, Store, Val],
Rope USING [Cat, Compare, Fetch, Length, ROPE],
SX USING [AreaPerimRec, Circuit, CircuitNode, FindRootNode, MergeRecList, NodeLinkage, NormalizeCircuit],
SXAccess USING [design],
SXAccessInternal USING [GetLogicalCell],
SXOutput USING [outputGeometricInfo, shortestNamesOnly],
SXOutputPrivate USING [actualCellInstanceName, actualSignalName, Circuit, CircuitNode, isPort, LogicalCell, MergeRec, MergeRecList, Naming, NodeLinkage, ROPE, ROPEList],
UserCredentials USING [Get];
SXOutputImplB: CEDAR PROGRAM
IMPORTS Basics, CD, CDBasics, CDInstances, CDOrient, CDProperties, FS, IO, PropertyLists, Real, RedBlackTree, RefTab, Rope, SX, SXAccess, SXAccessInternal, SXOutput, SXOutputPrivate, UserCredentials
EXPORTS SXOutputPrivate = BEGIN
OPEN SXOutputPrivate;
tiptoe: BOOLFALSE;
ValidMerge: PUBLIC PROC [merge: MergeRec] RETURNS [valid: BOOL] = {
valid ← merge.applChain.rest = NIL;
};
GetANaming: PUBLIC PROC [thing: REF ANY, insistValid: BOOLTRUE] RETURNS [naming: Naming] = {
WITH thing SELECT FROM
node: REF CircuitNode => {
naming ← NARROW[node.properties.GetProp[ actualSignalName]];
};
appl: CD.Instance => {
naming ← NARROW[CDProperties.GetInstanceProp[from: appl, prop: actualCellInstanceName]];
};
ENDCASE => ERROR;
IF insistValid THEN WHILE naming # NIL AND NOT Valid[naming] DO naming ← naming.next ENDLOOP;
};
Valid: PUBLIC PROC [naming: Naming] RETURNS [valid: BOOL] = {
valid ← naming.named # NIL;
};
GetAName: PUBLIC PROC [thing: REF ANY] RETURNS [name: ROPE] = {
naming: Naming ← GetANaming[thing];
name ← IF naming # NIL THEN NamingName[naming] ELSE NIL;
};
NamingName: PUBLIC PROC [naming: Naming] RETURNS [name: ROPE] = {
name ← naming.name};
HasAskedName: PUBLIC PROC [thing: REF ANY] RETURNS [asked: BOOL] = {
FOR naming: Naming ← GetANaming[thing], naming.next WHILE naming # NIL DO
IF Valid[naming] AND NamingAsked[naming] THEN RETURN [TRUE];
ENDLOOP;
asked ← FALSE;
};
NamingAsked: PUBLIC PROC [naming: Naming] RETURNS [asked: BOOL] = {
asked ← naming.explicit;
};
EnumerateNames: PUBLIC PROC [thing: REF ANY, PerName: PROC [name: ROPE, valid: BOOL], onlyValid: BOOLTRUE] = {
FOR naming: Naming ← GetANaming[thing, FALSE], naming.next WHILE naming # NIL DO
valid: BOOL ← Valid[naming];
IF valid OR NOT onlyValid THEN PerName[NamingName[naming], valid];
ENDLOOP;
};
ReverseNamings: PUBLIC PROC [oldFirst: Naming] RETURNS [newFirst: Naming] = {
prev: Naming ← oldFirst;
cur: Naming ← prev.next;
prev.next ← NIL;
WHILE cur # NIL DO
next: Naming ← cur.next;
cur.next ← prev;
prev ← cur;
cur ← next;
ENDLOOP;
newFirst ← prev;
};
——————————
Stuff for RedBlackTree (used in SortNamings)
SKey: TYPE = REF Rope.ROPE; -- RedBlackTree.Key
SRec: TYPE = RECORD [key: SKey, naming: Naming];
SData: TYPE = REF SRec; -- RedBlackTree.UserData
WorstClass: CARDINAL = 8;
classes: ARRAY [0 .. WorstClass] OF RedBlackTree.Table;
NamKey: RedBlackTree.GetKey =
BEGIN
RETURN [NARROW [data, SData].key]
END; -- NamKey
NamComp: RedBlackTree.Compare =
BEGIN
c: Basics.Comparison;
sk: SKey = NARROW [k]; -- name
d: SData = NARROW [data]; -- naming
c ← Rope.Compare [sk^, d.key^];
IF c = equal THEN BEGIN
n1i: INTLOOPHOLE [sk^];
n2i: INTLOOPHOLE [d.key^];
c ← Basics.CompareINT [n1i, n2i];
END;
RETURN [c]
END; -- NamComp
Start: PROCEDURE =
Initializes the symbol tables
BEGIN
FOR c: CARDINAL IN [0 .. WorstClass] DO
classes[c] ← RedBlackTree.Create [getKey: NamKey, compare: NamComp]
ENDLOOP
END; -- Start
SInsert: PROCEDURE [s: RedBlackTree.Table, nam: Naming] RETURNS [duplicate: BOOL] =
BEGIN
ENABLE RedBlackTree.DuplicateKey => GOTO dupl;
sk: SKey ← NEW [Rope.ROPE ← nam.name];
data: SData ← NEW [SRec ← [key: sk, naming: nam]];
RedBlackTree.Insert [s, data, sk];
Raises DuplicateKey if appl with same location already added.
RETURN [FALSE];
EXITS
dupl => RETURN [TRUE]
END; -- SInsert
——————————
SortNamings: PUBLIC PROC [oldFirst: Naming] RETURNS [newFirst: Naming] = {
IF oldFirst.next = NIL THEN RETURN [oldFirst];
FOR oldFirst ← oldFirst, newFirst WHILE oldFirst # NIL DO
class: CARDINAL ← 0;
seeingGen: BOOLFALSE;
For detecting name segments matching {n|C|Q}{0..9}+
lastWasGen, lastWasDash, lastWasAlpha, nextLastWasAlpha: BOOLFALSE;
newFirst ← oldFirst.next;
oldFirst.next ← NIL;
IF NOT Valid[oldFirst] THEN LOOP;
We save 'em now, because we might propogate them upward.
FOR i: INT IN [0 .. oldFirst.name.Length[]) DO
c: CHAR ← oldFirst.name.Fetch[i];
SELECT c FROM
'., '- => IF seeingGen THEN class ← class + 1;
ENDCASE;
SELECT c FROM
'. => {class ← class + 1; seeingGen ← FALSE};
IN ['0 .. '9] => {
IF lastWasDash THEN {class ← class + 1; IF seeingGen THEN ERROR};
IF lastWasGen AND NOT nextLastWasAlpha THEN seeingGen ← TRUE;
};
ENDCASE => seeingGen ← FALSE;
nextLastWasAlpha ← lastWasAlpha;
SELECT c FROM
'., '- => lastWasAlpha ← FALSE;
ENDCASE => lastWasAlpha ← TRUE;
SELECT c FROM
'n, 'C, 'Q => {lastWasGen ← TRUE; lastWasDash ← FALSE};
'- => {lastWasGen ← FALSE; lastWasDash ← TRUE};
ENDCASE => lastWasGen ← lastWasDash ← FALSE;
ENDLOOP;
IF seeingGen THEN class ← class + 1;
[] ← SInsert [s: classes[MIN[WorstClass, class]], nam: oldFirst]
ENDLOOP;
IF newFirst # NIL THEN ERROR;
IF SXOutput.shortestNamesOnly THEN {
FOR c: CARDINAL IN [0 .. WorstClass] DO
sNaming: SData ← NARROW [RedBlackTree.LookupLargest[classes[c]]];
foundValid: BOOLFALSE;
WHILE (sNaming # NIL) AND (sNaming.naming # NIL) DO
foundValid ← foundValid OR Valid[sNaming.naming];
sNaming.naming.next ← newFirst;
newFirst ← sNaming.naming;
sNaming ← NARROW [RedBlackTree.LookupNextSmaller[classes[c], sNaming.key]];
ENDLOOP;
RedBlackTree.DestroyTable [self: classes[c]];
IF foundValid THEN {
FOR d: CARDINAL IN (c .. WorstClass] DO
RedBlackTree.DestroyTable [self: classes[d]]
ENDLOOP;
EXIT;
}
ENDLOOP;
}
ELSE {
FOR c: CARDINAL DECREASING IN [0 .. WorstClass] DO
sNaming: SData ← NARROW [RedBlackTree.LookupLargest[classes[c]]];
WHILE (sNaming # NIL) AND (sNaming.naming # NIL) DO
sNaming.naming.next ← newFirst;
newFirst ← sNaming.naming;
sNaming ← NARROW [RedBlackTree.LookupNextSmaller[classes[c], sNaming.key]];
ENDLOOP;
RedBlackTree.DestroyTable [self: classes[c]]
ENDLOOP;
};
IF newFirst = NIL THEN ERROR;
};
PrintNaming: PUBLIC PROC [to: IO.STREAM, naming: Naming, insert: ROPENIL] = {
nth: CARDINAL ← 0;
FOR naming ← naming, naming.next WHILE naming # NIL DO
IF Valid[naming] THEN {
SELECT nth FROM
=0 => NULL;
=1 => to.PutRope[" (A ("];
>1 => to.PutRope[" ("];
ENDCASE => ERROR;
to.PutF["\"%q\"", IO.rope[NamingName[naming]]];
IF nth = 0 AND insert # NIL THEN to.PutRope[insert];
to.PutRope[IF NamingAsked[naming] THEN " (G D)" ELSE " (G P)"];
SELECT nth FROM
=0 => NULL;
>0 => to.PutRope[")"];
ENDCASE => ERROR;
nth ← nth + 1;
};
ENDLOOP;
IF nth > 1 THEN to.PutRope[")"];
};
CheckNodeInCircuit: PROC [node: REF CircuitNode, circuit: REF Circuit] = {
IF NOT tiptoe THEN RETURN;
FOR nl: LIST OF REF CircuitNode ← circuit.nodes, nl.rest WHILE nl # NIL DO
IF nl.first = node THEN EXIT;
REPEAT FINISHED => ERROR;
ENDLOOP;
};
CheckMergeDirectory: PROC [circuit: REF Circuit] ~ {
CheckMerges: PROC [key: RefTab.Key, val: RefTab.Val] RETURNS [quit: BOOLEAN] -- RefTab.EachPairAction -- ~ {
bottomNode: REF CircuitNode ~ NARROW[key];
FOR ml: MergeRecList ← NARROW[val], ml.rest WHILE ml # NIL DO
bottomCircuit: REF Circuit ← SXAccessInternal.GetLogicalCell[ml.first.applChain.first.ob].circuit;
CheckNodeInCircuit[bottomNode, bottomCircuit];
CheckNodeInCircuit[ml.first.becomes, circuit];
ENDLOOP;
quit ← FALSE;
};
IF tiptoe AND circuit.mergeDirectory#NIL THEN
[] ← circuit.mergeDirectory.Pairs[action: CheckMerges];
};
AddIntermediateNodes: PUBLIC PROC [cellList: LIST OF REF LogicalCell] ~ {
FOR cl: LIST OF REF LogicalCell ← cellList, cl.rest WHILE cl # NIL DO
CheckMergeDirectory[cl.first.circuit];
ENDLOOP;
Break long merge chains up into steps one application long:
FOR cl: LIST OF REF LogicalCell ← cellList, cl.rest WHILE cl # NIL DO
circuit: REF Circuit ← cl.first.circuit;
PiecifyMerges: PROC [key: RefTab.Key, val: RefTab.Val] RETURNS [quit: BOOLEAN] -- RefTab.EachPairAction -- ~ {
bottomNode: REF CircuitNode ~ NARROW[key];
FOR ml: MergeRecList ← NARROW[val], ml.rest WHILE ml # NIL DO
IF ml.first.applChain = NIL THEN ERROR;
IF ml.first.applChain.rest = NIL THEN
bottomNode.properties ← bottomNode.properties.PutProp[prop~ isPort, val~ isPort]
ELSE {
lowNode: REF CircuitNode ← bottomNode;
nextHigherNode: REF CircuitNode;
lastQual: LIST OF CD.Instance;
highQual: LIST OF CD.Instance;
FOR appls: LIST OF CD.Instance ← ml.first.applChain, appls.rest WHILE appls.rest # NIL DO
qual: LIST OF CD.Instance ~ LIST[appls.first];
lastStep: LIST OF CD.Instance;
parentCircuit: REF Circuit ← SXAccessInternal.GetLogicalCell[appls.rest.first.ob].circuit;
[node~ nextHigherNode, rootQualifier~ lastStep] ← SX.FindRootNode[ circuit~parentCircuit, subcircuitNode~lowNode, qualifier~qual, insertIfNotInCircuit~TRUE];
IF lastStep # NIL THEN ERROR;
IF nextHigherNode = NIL THEN ERROR;
CheckNodeInCircuit[nextHigherNode, parentCircuit];
CheckMergeDirectory[parentCircuit];
lowNode.properties ← lowNode.properties.PutProp[prop~ isPort, val~ isPort];
lowNode ← nextHigherNode;
lastQual ← appls.rest;
ENDLOOP;
[ node~ nextHigherNode, rootQualifier~ highQual] ← SX.FindRootNode[ circuit~ circuit, subcircuitNode~ lowNode, qualifier~ lastQual, insertIfNotInCircuit~ FALSE];
IF highQual = NIL AND nextHigherNode # ml.first.becomes THEN ERROR;
IF highQual # NIL AND (highQual.rest # NIL OR highQual.first # lastQual.first) THEN ERROR;
lowNode.properties ← lowNode.properties.PutProp[prop~ isPort, val~ isPort];
IF highQual # NIL THEN {
newML: MergeRecList ~ LIST[[lastQual, ml.first.becomes]];
-- Note circuit must have a mergeDirectory as we are currently enumerating it!
newML.rest ← NARROW[circuit.mergeDirectory.Fetch[ lowNode].val];
[] ← circuit.mergeDirectory.Store[ lowNode, newML];
}
};
ENDLOOP;
quit ← FALSE;
};
IF circuit.mergeDirectory # NIL THEN {
CheckMergeDirectory[circuit];
[] ← circuit.mergeDirectory.Pairs[ action~ PiecifyMerges];
CheckMergeDirectory[circuit];
};
ENDLOOP;
Introduce stopper nodes:
FOR cl: LIST OF REF LogicalCell ← cellList, cl.rest WHILE cl # NIL DO
circuit: REF Circuit = cl.first.circuit;
FOR appls: CD.InstanceList ← circuit.subcircuits, appls.rest WHILE appls # NIL DO
subcircuit: REF Circuit = SXAccessInternal.GetLogicalCell[appls.first.ob].circuit;
FOR nl: LIST OF REF CircuitNode ← subcircuit.nodes, nl.rest WHILE nl # NIL DO
IF nl.first.properties.GetProp[ isPort] # NIL THEN {
parentNode: REF CircuitNode;
qual: LIST OF CD.Instance;
[node: parentNode, rootQualifier: qual] ← SX.FindRootNode[circuit: circuit, subcircuitNode: nl.first, qualifier: LIST[appls.first], insertIfNotInCircuit: TRUE];
IF qual#NIL OR parentNode=NIL THEN ERROR;
};
ENDLOOP;
ENDLOOP;
ENDLOOP;
};
CleanUp: PUBLIC PROC [cellList: LIST OF REF LogicalCell] ~ {
Remove names and portness.
Maybe restore old node lists and merge directories.
FOR cl: LIST OF REF LogicalCell ← cellList, cl.rest WHILE cl # NIL DO
circuit: REF Circuit ← cl.first.circuit;
FOR nl: LIST OF REF CircuitNode ← circuit.nodes, nl.rest WHILE nl # NIL DO
nl.first.properties ← nl.first.properties.PutProp[ actualSignalName, NIL].PutProp[ isPort, NIL];
ENDLOOP;
FOR appls: CD.InstanceList ← circuit.subcircuits, appls.rest WHILE appls # NIL DO
CDProperties.PutInstanceProp[appls.first, actualCellInstanceName, NIL];
ENDLOOP;
FOR links: LIST OF REF NodeLinkage ← circuit.linkages, links.rest WHILE links # NIL DO
CDProperties.PutInstanceProp[ links.first.source, actualCellInstanceName, NIL];
ENDLOOP;
IF undoIntermediates THEN {
All new merges introduced by FindRootNode will be UnMerged and will therefore be removed by NormalizeCircuit.
SX.NormalizeCircuit[circuit]
};
ENDLOOP;
};
undoIntermediates: BOOLTRUE;
IntTransform: TYPE = RECORD [dxdx, dxdy, dx, dydx, dydy, dy: INT];
PrintRoseInstantiationTransformation: PUBLIC PROC [to: IO.STREAM, appl: CD.Instance] = {
IF SXOutput.outputGeometricInfo THEN {
ir: CD.Rect = CDInstances.InstRectO [appl];
pos: CD.Position = [x: ir.x1, y: ir.y1];
size: CD.Position = [x: ir.x2 - ir.x1, y: ir.y2 - ir.y1];
t: ImagerTransformation.Transformation ← CDOrient.CreateTransform[cellSize: size, cellInstOrient: appl.orientation, cellInstPos: pos];
it: IntTransform ← [dxdx: Real.Fix[t.a], dxdy: Real.Fix[t.b], dx: Real.Fix[t.c], dydx: Real.Fix[t.d], dydy: Real.Fix[t.e], dy: Real.Fix[t.f]];
IF t.a # it.dxdx OR t.b # it.dxdy OR t.c # it.dx OR t.d # it.dydx OR t.e # it.dydy OR t.f # it.dy THEN ERROR;
to.PutF[" (t6 %g %g %g", IO.int[it.dxdx], IO.int[it.dxdy], IO.int[it.dx]];
to.PutF[" %g %g %g)", IO.int[it.dydx], IO.int[it.dydy], IO.int[it.dy]];
Note that output is in CD units and not in lambdas
}
}; -- end PrintRoseInstantiationTransformation
PrintRoseInstanceBounds: PUBLIC PROC [to: IO.STREAM, appl: CD.Instance] = {
r: CD.Rect;
IF NOT SXOutput.outputGeometricInfo THEN RETURN;
r ← CDOrient.MapRect[itemInCell: CDBasics.RectAt[[0, 0], appl.ob.size], cellSize: appl.ob.size, cellInstOrient: appl.orientation, cellInstPos: appl.location];
to.PutF[" (bb %g %g %g %g)",
IO.real [REAL[r.x1]/SXAccess.design.technology.lambda],
IO.real [REAL[r.y1]/SXAccess.design.technology.lambda],
IO.real [REAL[r.x2]/SXAccess.design.technology.lambda],
IO.real [REAL[r.y2]/SXAccess.design.technology.lambda]];
};
nameCount: INT ← 0;
NameTransType: PUBLIC PROC [desWDir: ROPE, obj: CD.Object, dfStream: IO.STREAM, type, mode: ATOM, length, width: CD.Number] RETURNS [name: ROPE] = {
cellFileName: ROPE;
cellStream: IO.STREAM;
name ← NARROW[CDProperties.GetProp[from~obj, prop~dfStream]];
IF name # NIL THEN RETURN;
name ← IO.PutFR["%g%g%g", IO.atom[type], IO.atom[mode], IO.int[nameCount ← nameCount + 1]];
CDProperties.PutObjectProp[onto~obj, prop~dfStream, val~name];
cellFileName ← name.Cat[".sch"];
cellStream ← FS.StreamOpen[desWDir.Cat[cellFileName], create];
dfStream.PutF["-- (CellType \"%g\")\n %g\n", IO.rope[name], IO.rope[cellFileName]];
cellStream.PutF[
"-- %g\n\n(CreatingUser %g)\n(CreationTime \"%g\")\n",
IO.rope[cellFileName],
IO.refAny[UserCredentials.Get[].name],
IO.time[]];
cellStream.PutF[
"(CellTypeName %g)\n(EC \"Structure\" \"%g%g\")\n",
IO.refAny[name],
IO.atom[type],
IO.atom[mode]];
IF SXOutput.outputGeometricInfo THEN {
b: CD.Rect ← CD.InterestRect[obj];
cellStream.PutF["(scale %g \"lambda\")\n", IO.int[1]];
The designers prefer 1.0
cellStream.PutF[
"(bb %g %g %g %g)\n",
IO.real [REAL[b.x1]/SXAccess.design.technology.lambda],
IO.real [REAL[b.y1]/SXAccess.design.technology.lambda],
IO.real [REAL[b.x2]/SXAccess.design.technology.lambda],
IO.real [REAL[b.y2]/SXAccess.design.technology.lambda]];
};
cellStream.PutRope["(Ports
(\"gate\" (G D) (IN))
(\"ch1\" (G D) (BIDIR) (EC \"Structure\" \"channel\"))
(\"ch2\" (G D) (BIDIR) (EC \"Structure\" \"channel\"))
)\n"];
cellStream.PutF["(MOSFETFlavor %g %g)\n", IO.atom[type], IO.atom[mode]];
cellStream.PutF["(MOSFETShape %g %g)\n", IO.real[REAL[length]/SXAccess.design.technology.lambda], IO.real[REAL[width]/SXAccess.design.technology.lambda]];
cellStream.PutF["(PrivateFollows)\n(InsidesUnspecified)\n"];
cellStream.Close[];
};
UnNameTransType: PUBLIC PROC [dfStream: IO.STREAM, linkage: REF SX.NodeLinkage] --SXOutput.LinkageHousekeeper-- = {
CDProperties.PutObjectProp[onto~linkage.source.ob, prop~dfStream, val~NIL];
};
Start[];
END.
Edited on March 10, 1985 11:11:36 pm PST, by Shand
Now uses SX.NormalizeCircuit to cleanup introduced merges, rather its own ad hoc scheme. All nodes introduced by SX.FindRootNode are marked as UnMerged until they become connected to other nodes in this circuit through SX.MergeNode. Nodes which do not become connected are deleted when SX.NormalizeCircuit is called. In the case of nodes introduced by this module, they are never connected to other nodes, so the cleanup will be performed.
changes to: AddIntermediateNodes, CleanUp, CleanUp, DIRECTORY, PiecifyMerges (local of AddIntermediateNodes), PiecifyMerges (local of AddIntermediateNodes), PiecifyMerges (local of AddIntermediateNodes), PiecifyMerges (local of AddIntermediateNodes), CheckMergeDirectory, PiecifyMerges (local of AddIntermediateNodes), DIRECTORY, PiecifyMerges (local of AddIntermediateNodes), NameTransType, NameTransType
Edited on May 6, 1985 5:29:17 pm PDT, by Beretta
Converted to ChipNDale version CD20.
Edited on June 19, 1985 8:22:34 pm PDT, by Beretta
The designers definitely prefer lambda units.
changes to: PrintRoseInstantiationTransformation, PrintRoseInstanceBounds, NameTransType: sizes are in lambda units.
Edited on July 6, 1985 6:38:33 pm PDT, by Beretta
The wrong coordinate system was used for the position of instances
changes to: PrintRoseInstantiationTransformation: now uses ARectI.
Edited on July 8, 1985 10:41:14 am PDT, by Beretta
changes to: DIRECTORY, PrintRoseInstantiationTransformation
Last edited by: gbb July 17, 1985 3:56:55 pm PDT
Replaced ordered symbol table stuff by red-black trees for Cedar 6.0
Last edited by: gbb July 22, 1985 5:20:08 pm PDT
Added a test for empty symbol table.