CoreFiddlingImpl.Mesa
Spreitzer, January 11, 1986 6:06:13 pm PST
Mike Spreitzer March 7, 1987 12:57:26 pm PST
Last tweaked by Mike Spreitzer on November 29, 1988 7:12:24 pm PST
DIRECTORY Atom, Core, CoreClasses, CoreOps, CoreFiddling, CoreProperties, CoreTracing, FS, IO, PartialOrders, RefTab, Rope, ViewerIO;
CoreFiddlingImpl:
CEDAR
PROGRAM
IMPORTS CoreClasses, CoreOps, CoreProperties, CoreTracing, IO, PartialOrders, RefTab, Rope
EXPORTS CoreFiddling
= BEGIN OPEN CC: CoreClasses, CO: CoreOps, CP: CoreProperties, CT: CoreTracing, PO: PartialOrders, CoreFiddling;
LORA: TYPE = LIST OF REF ANY;
InstanceList: TYPE = LIST OF CC.CellInstance;
WireList: TYPE ~ LIST OF Core.Wire;
Perm: TYPE = REF PermPrivate;
PermPrivate:
TYPE =
RECORD [
indices: SEQUENCE length: NAT OF NAT];
log: PUBLIC IO.STREAM ← NIL;
oneOutsideUse:
ATOM =
CP.RegisterProperty[
$CoreFiddlingOneOutsideUse,
CP.Props[[CP.propPrint, CP.PropDontPrint]]
];
oneInsideUse:
ATOM =
CP.RegisterProperty[
$CoreFiddlingOneInsideUse,
CP.Props[[CP.propPrint, CP.PropDontPrint]]
];
killit:
ATOM =
CP.RegisterProperty[
$CoreFiddlingKillWire,
CP.Props[[CP.propPrint, CP.PropDontPrint]]
];
PrintCellTypes:
PUBLIC
PROC [to:
IO.
STREAM, order: PartialOrder] = {
PerCellType:
PROC [rank:
INT, elt:
REF
ANY, v:
PO.Vertex]
--PO.Consumer-- = {
cellType: Core.CellType = NARROW[elt];
CO.PrintCellType[cellType, to];
};
order.Enumerate[decreasing, NIL, PerCellType];
};
PrintCellTypeGraph:
PUBLIC
PROC [to:
IO.
STREAM, order: PartialOrder] = {
row: INT ← 0;
depth: INT ← 1;
PerCellType:
PROC [rank:
INT, elt:
REF
ANY, v:
PO.Vertex]
--PO.Consumer-- = {
cellType: Core.CellType = NARROW[elt];
cellTypeName: ROPE = CO.GetCellTypeName[cellType];
to.PutF["%03g%l ",
[integer[row]],
[rope[
SELECT row
MOD 3
FROM
0 => "",
1 => "z",
2 => "y",
ENDCASE => ERROR]]
];
FOR i:
INT
IN [1 .. depth)
DO
to.PutChar['\t];
ENDLOOP;
to.PutF[
"%l%g; %g public, ",
[rope[" "]],
[rope[cellTypeName]],
[integer[cellType.public.size]]
];
WITH cellType.data
SELECT
FROM
recordCellType: CC.RecordCellType => {
to.PutF[
"%g internal, %g components",
[integer[recordCellType.internal.size]],
[integer[recordCellType.size]]
];
};
ENDCASE => {
to.PutRope["atomic"];
};
to.PutF[
", %g uses\n",
[integer[CT.Count[CT.EnumeratorForInstances[cellType]]]]
];
row ← row + 1;
depth ← depth + 1;
order.EnumerateDirectDominees[v, PerCellType];
depth ← depth - 1;
};
order.ComputeDirectDominance[];
order.EnumerateDirectDominees[NIL, PerCellType];
};
PrintCellInstanceGraph:
PUBLIC
PROC [to:
IO.
STREAM, order: PartialOrder, instanceNames:
BOOL ←
TRUE] = {
PrintCell:
PROC [cellType: Core.CellType, depth:
INT, instanceName:
ROPE] = {
cellTypeName: ROPE = CO.GetCellTypeName[cellType];
FOR i:
INT
IN [0 .. depth)
DO
to.PutChar['\t];
ENDLOOP;
IF instanceNames THEN to.PutF["%g: ", [rope[instanceName]]];
to.PutF["%g\n", [rope[cellTypeName]]];
WITH cellType.data
SELECT
FROM
recordCellType: CC.RecordCellType => {
FOR i:
INT
IN [0 .. recordCellType.size)
DO
ci: CC.CellInstance = recordCellType[i];
PrintCell[ci.type, depth+1, CC.GetCellInstanceName[ci]];
ENDLOOP;
};
ENDCASE => NULL;
to ← to;
};
PerCellType:
PROC [rank:
INT, elt:
REF
ANY, v:
PO.Vertex]
--PO.Consumer-- = {
cellType: Core.CellType = NARROW[elt];
PrintCell[cellType, 0, "root"];
};
order.ComputeDirectDominance[];
order.EnumerateDirectDominees[NIL, PerCellType];
};
SortPublics:
PUBLIC
PROC [cellTypes: Table] = {
PerCellType:
PROC [key, val:
REF
ANY]
RETURNS [quit:
BOOLEAN ←
FALSE]
--RefTab.EachPairAction-- = {
cellType: Core.CellType = NARROW[val];
SortCellTypePublics[cellType];
};
CT.Prepare[CT.EnumeratorForHashTable[cellTypes, FALSE, TRUE]];
[] ← cellTypes.Pairs[PerCellType];
};
SortCellTypePublics:
PROC [cellType: Core.CellType] = {
cellTypeName: ROPE = CO.GetCellTypeName[cellType];
perm: Perm = NEW [PermPrivate[cellType.public.size]];
inv: Perm ~ NEW [PermPrivate[cellType.public.size]];
PerInstance:
PROC [ra:
REF
ANY] = {
ci: CC.CellInstance = NARROW[ra];
IF ci.type # cellType THEN ERROR;
PermuteWire[ci.actual, perm];
};
PerSequence:
PROC [ra:
REF
ANY] = {
seqCellType: Core.CellType ~ NARROW[ra];
seq: CC.SequenceCellType ~ NARROW[seqCellType.data];
IF seq.sequence #
NIL
THEN
FOR i:
NAT
IN [0 .. seq.sequence.length)
DO
seq.sequence[i] ← inv[seq.sequence[i]];
ENDLOOP;
IF seq.flatSequence #
NIL
THEN
FOR i:
NAT
IN [0 .. seq.flatSequence.length)
DO
seq.flatSequence[i] ← inv[seq.flatSequence[i]];
ENDLOOP;
IF seq.stitch #
NIL
THEN
FOR i:
NAT
IN [0 .. seq.stitch.length)
DO
seq.stitch[i].this ← inv[seq.stitch[i].this];
seq.stitch[i].that ← inv[seq.stitch[i].that];
ENDLOOP;
};
FOR i: NAT IN [0 .. perm.length) DO perm[i] ← i ENDLOOP;
FOR i:
NAT
DECREASING
IN (0 .. perm.length)
DO
FOR j:
NAT
IN [0 .. i)
DO
jName: ROPE = CO.GetShortWireName[cellType.public[perm[j]]];
iName: ROPE = CO.GetShortWireName[cellType.public[perm[i]]];
SELECT jName.Compare[iName,
FALSE]
FROM
less => NULL;
equal => ERROR;
greater => {k: NAT ← perm[j]; perm[j] ← perm[i]; perm[i] ← k};
ENDCASE => ERROR;
ENDLOOP;
ENDLOOP;
FOR i: NAT IN [0 .. perm.length) DO inv[perm[i]] ← i ENDLOOP;
PermuteWire[cellType.public, perm];
CT.EnumerateInstances[cellType, PerInstance];
CT.EnumerateSequences[cellType, PerSequence];
cellType ← cellType;
};
PermuteWire:
PROC [wire: Core.Wire, perm: Perm] = {
temp: Core.Wire = NEW [Core.WireRec[wire.size]];
IF wire.size # perm.length THEN ERROR;
FOR i: NAT IN [0 .. wire.size) DO temp[i] ← wire[i] ENDLOOP;
FOR i:
NAT
IN [0 .. wire.size)
DO
wire[i] ← temp[perm[i]];
ENDLOOP;
perm ← perm;
};
PrintAny:
PROC [ra:
REF
ANY] = {
WITH ra
SELECT
FROM
cellType: Core.CellType => {
log.PutF[
"%g: %g CellType\n",
[rope[CO.GetCellTypeName[cellType]]],
[rope[cellType.class.name]]
];
};
wire:
--internal-- Core.Wire => {
log.PutF[
"%g.%g: %gWire\n",
[rope[CO.GetCellTypeName[CT.WireContainer[wire]]]],
[rope[CO.GetShortWireName[wire]]],
[rope[IF CT.WirePublicity[wire].public THEN "PUBLIC " ELSE ""]]
];
};
ci: CC.CellInstance => {
log.PutF[
"%g.%g: %g\n",
[rope[CO.GetCellTypeName[CT.InstanceContainer[ci]]]],
[rope[CC.GetCellInstanceName[ci]]],
[rope[CO.GetCellTypeName[ci.type]]]
];
};
lc:
CT.LocalConnection => {
log.PutF[
"%g.%g: %g[%g: %g]\n",
[rope[CO.GetCellTypeName[CT.InstanceContainer[lc.ci]]]],
[rope[CC.GetCellInstanceName[lc.ci]]],
[rope[CO.GetCellTypeName[lc.ci.type]]],
[rope[CO.GetFullWireName[lc.ci.type.public, CT.SubWire[lc.ci.type.public, lc.publicPath]]]],
[rope[CO.GetFullWireName[lc.ci.actual, CT.SubWire[lc.ci.actual, lc.publicPath]]]]
]
};
ENDCASE => log.PutF["%g\n", [refAny[ra]]];
};
SqueezeDown:
PROC [order: PartialOrder] =
--privatize public wires whose actuals never connect with anything else-- {
SqueezeCellType:
PROC [rank:
INT, elt:
PO.Element, v:
PO.Vertex]
--PO.Consumer-- = {
ct: Core.CellType = NARROW[elt];
cellTypeName: ROPE = CO.GetCellTypeName[ct];
SELECT ct.class
FROM
CC.recordCellClass => {
quaRecord: CC.RecordCellType = NARROW[ct.data];
NoteInstance:
PROC [ra:
REF
ANY] = {
ci: CC.CellInstance = NARROW[ra];
FOR pi:
INT
IN [0 .. oldSize)
DO
pw: Core.Wire = ct.public[pi];
connections: INT ~ CT.EnumeratorForLocalConnections[ci.actual[pi]].Count[2];
SELECT connections
FROM
=0 => ERROR;
=1 => NULL;
>1 => CP.PutWireProp[pw, oneOutsideUse, NIL];
ENDCASE => ERROR;
ENDLOOP;
};
ie: CT.Enumerator = CT.EnumeratorForInstances[ct];
oldSize, newSize: INT ← ct.public.size;
losses: INT ← 0;
InitPW:
PROC [wire: Core.Wire]
RETURNS [subWires:
BOOL ←
TRUE, quit:
BOOL ←
FALSE]
--CO.EachWireProc-- ~ {
CP.PutWireProp[wire, oneOutsideUse, $T];
subWires ← FALSE;
};
IF CO.VisitWireSeq[ct.public, InitPW] THEN ERROR;
ie.Enumerate[ie.data, NoteInstance];
FOR pi:
INT
IN [0 .. oldSize)
DO
pw: Core.Wire = ct.public[pi];
SELECT
CP.GetWireProp[pw, oneOutsideUse]
FROM
$T => {losses ← losses + 1; newSize ← newSize - 1};
NIL => NULL;
ENDCASE => ERROR;
ENDLOOP;
IF losses > 0
THEN {
Pass:
PROC [index:
NAT]
RETURNS [keep:
BOOL] = {
keep ← CP.GetWireProp[ct.public[index], oneOutsideUse] = NIL;
};
FixInstance:
PROC [ra:
REF
ANY] = {
ci: CC.CellInstance = NARROW[ra];
parent: Core.CellType = CT.InstanceContainer[ci];
parentRecord: CC.RecordCellType = NARROW[parent.data];
PassInternal:
PROC [index:
NAT]
RETURNS [keep:
BOOL] = {
keep ← CP.GetWireProp[parentRecord.internal[index], killit] = NIL;
};
ci.actual ← FilterWire[ci.actual, Pass, losses, killit, $T].new;
parentRecord.internal ← FilterWire[parentRecord.internal, PassInternal, losses].new;
CT.Repair[parent];
};
lostPublics: WireList;
log.PutF["Removing %g from cell type %g:\n", [integer[losses]], [rope[cellTypeName]]];
FOR pi:
INT
IN [0 .. oldSize)
DO
pw: Core.Wire = ct.public[pi];
SELECT
CP.GetWireProp[pw, oneOutsideUse]
FROM
$T => log.PutF["\t%g\n", [rope[CO.GetShortWireName[pw]]]];
NIL => NULL;
ENDCASE => ERROR;
ENDLOOP;
ie.Enumerate[ie.data, FixInstance];
[ct.public, lostPublics] ← FilterWire[ct.public, Pass, losses];
CT.Repair[ct];
FOR lostPublics ← lostPublics, lostPublics.rest
WHILE lostPublics #
NIL
DO
lp: Core.Wire ~ lostPublics.first;
connections: INT ~ CT.EnumeratorForLocalConnections[lp].Count[1];
IF connections = 0
THEN log.PutF[
"%g.%g has no connections after SqueezeDown\n",
[rope[CO.GetCellTypeName[ct]]],
[rope[CO.GetShortWireName[lp]]]
];
ENDLOOP;
};
};
ENDCASE => NULL;
};
order.Enumerate[decreasing, NIL, SqueezeCellType];
};
Enuf: ERROR = CODE;
debugSqueeze: BOOL ← FALSE;
SqueezeUp:
PROC [order: PartialOrder] =
--remove public wires not connected to anything-- {
SqueezeCellType:
PROC [rank:
INT, elt:
PO.Element, v:
PO.Vertex]
--PO.Consumer-- = {
ct: Core.CellType = NARROW[elt];
cellTypeName: ROPE = CO.GetCellTypeName[ct];
SELECT ct.class
FROM
CC.recordCellClass => {
quaRecord: CC.RecordCellType = NARROW[ct.data];
losses: NAT ← 0;
FOR i:
INT
IN [0 .. quaRecord.internal.size)
DO
iw: Core.Wire = quaRecord.internal[i];
e: CT.Enumerator = CT.EnumeratorForLocalConnections[iw];
count: NAT ← 0;
lc1: CT.LocalConnection ← NIL;
PerLC:
PROC [ra:
REF
ANY] = {
lc: CT.LocalConnection = NARROW[ra];
IF (count ← count + 1) > 2 THEN Enuf;
IF count = 1 THEN lc1 ← lc;
IF debugSqueeze
THEN log.PutF[
"%g.%g <-> %g.%g\n",
[rope[CO.GetCellTypeName[ct]]],
[rope[CO.GetFullWireName[quaRecord.internal, CT.SubWire[iw, lc.subscript]]]],
[rope[IF lc.ci = NIL THEN "<self>" ELSE CC.GetCellInstanceName[lc.ci]]],
[rope[CO.GetShortWireName[CT.SubWire[IF lc.ci = NIL THEN ct.public ELSE lc.ci.type.public, lc.publicPath]]]]
];
};
e.Enumerate[e.data, PerLC !Enuf => CONTINUE];
IF count = 0
THEN log.PutF[
"%g.%g has no connections\n",
[rope[CO.GetCellTypeName[ct]]],
[rope[CO.GetShortWireName[iw]]]
]
ELSE IF count > 1 THEN NULL
ELSE IF lc1.ci # NIL THEN NULL
ELSE {
log.PutF[
"Squeezing up %g.%g\n",
[rope[CO.GetCellTypeName[ct]]],
[rope[CO.GetShortWireName[iw]]]
];
CP.PutWireProp[iw, oneInsideUse, $T];
losses ← losses + 1;
};
ENDLOOP;
IF losses > 0
THEN {
PassExternal:
PROC [index:
NAT]
RETURNS [keep:
BOOL] = {
keep ← CP.GetWireProp[ct.public[index], oneInsideUse] = NIL;
};
PassInternal:
PROC [index:
NAT]
RETURNS [keep:
BOOL] = {
keep ← CP.GetWireProp[quaRecord.internal[index], oneInsideUse] = NIL;
};
FixInstance:
PROC [ra:
REF
ANY] = {
ci: CC.CellInstance = NARROW[ra];
parent: Core.CellType = CT.InstanceContainer[ci];
losts: WireList;
[ci.actual, losts] ← FilterWire[ci.actual, PassExternal, losses];
CT.Repair[parent];
FOR losts ← losts, losts.rest
WHILE losts #
NIL
DO
lw: Core.Wire ~ losts.first;
connections: INT ~ CT.EnumeratorForLocalConnections[lw].Count[1];
IF connections = 0
THEN log.PutF[
"%g.%g has no connections after SqueezeUp\n",
[rope[CO.GetCellTypeName[parent]]],
[rope[CO.GetShortWireName[lw]]]
];
ENDLOOP;
};
ie: CT.Enumerator = CT.EnumeratorForInstances[ct];
ie.Enumerate[ie.data, FixInstance];
quaRecord.internal ← FilterWire[quaRecord.internal, PassInternal, losses].new;
ct.public ← FilterWire[ct.public, PassExternal, losses].new;
CT.Repair[ct];
};
};
ENDCASE;
};
order.Enumerate[increasing, NIL, SqueezeCellType];
};
FilterWire:
PROC [old: Core.Wire,
Pass:
PROC [
NAT]
RETURNS [
BOOL], losses:
INT, markProp:
ATOM ←
NIL, markValue:
REF
ANY ←
NIL]
RETURNS [new: Core.Wire, gone: WireList] = {
ni: INT ← 0;
new ← NEW [Core.WireRec[old.size - losses]];
new.properties ← old.properties;
gone ← NIL;
FOR oi:
INT
IN [0 .. old.size)
DO
copy: BOOL = Pass[oi];
IF copy
THEN {
new[ni] ← old[oi];
ni ← ni + 1;
}
ELSE {
gone ← CONS[old[oi], gone];
IF markProp # NIL THEN CP.PutWireProp[old[oi], markProp, markValue];
};
ENDLOOP;
IF ni # new.size THEN ERROR;
};
END.