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
Last edited by: Christian Jacobi, November 7, 1986 1:22:50 pm PST
DIRECTORY
Basics USING [CompareInt, Comparison],
CD USING [Instance, InstanceList, InterestRect, Number, Object, Rect],
CDBasics,
CDInstances USING [InstRectO],
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],
Properties 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, CDProperties, FS, IO, Properties, Real, RedBlackTree, RefTab, Rope, SX, SXAccess, SXAccessInternal, SXOutput, SXOutputPrivate, UserCredentials
EXPORTS SXOutputPrivate = BEGIN
OPEN SXOutputPrivate;
tiptoe: BOOL ← FALSE;
ValidMerge:
PUBLIC
PROC [merge: MergeRec]
RETURNS [valid:
BOOL] = {
valid ← merge.applChain.rest = NIL;
};
GetANaming:
PUBLIC
PROC [thing:
REF
ANY, insistValid:
BOOL ←
TRUE]
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:
BOOL ←
TRUE] = {
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: INT ← LOOPHOLE [sk^];
n2i: INT ← LOOPHOLE [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:
BOOL ←
FALSE;
For detecting name segments matching {n|C|Q}{0..9}+
lastWasGen, lastWasDash, lastWasAlpha, nextLastWasAlpha: BOOL ← FALSE;
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: BOOL ← FALSE;
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:
ROPE ←
NIL] = {
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: BOOL ← TRUE;
IntTransform: TYPE = RECORD [dxdx, dxdy, dx, dydx, dydy, dy: INT];
PrintRoseInstantiationTransformation:
PUBLIC
PROC [to:
IO.
STREAM, appl:
CD.Instance] = {
IF SXOutput.outputGeometricInfo
THEN {
t: ImagerTransformation.Transformation ← CDBasics.ImagerTransform[appl.trans];
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 ← CDInstances.InstRectO[appl];
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.