PWCoreLichenImpl.mesa
Copyright © 1986 by Xerox Corporation. All rights reversed.
Created by Bertrand Serlet, July 14, 1986 5:49:00 pm PDT
Bertrand Serlet, July 15, 1986 2:10:29 am PDT
Mike Spreitzer January 15, 1987 12:51:56 pm PST
DIRECTORY CD, CDCommandOps, CDDirectory, CDInstances, CDMenus, CDOps, CDSequencer, CDViewer, Core, CoreClasses, CoreFlat, CoreOps, CoreProperties, CoreStructuralComparison, HashTable, IO, PW, PWCLCoreFlatExtras, PWCore, PWCoreLichen, Rope, SinixOps, Sisyph, StructuredStreams, TerminalIO, UnparserBuffer, ViewerClasses;
PWCoreLichenImpl:
CEDAR
PROGRAM
IMPORTS CD, CDCommandOps, CDDirectory, CDInstances, CDMenus, CDOps, CDViewer, CoreClasses, CoreFlat, CoreOps, CoreProperties, CoreStructuralComparison, HashTable, IO, PW, PWCLCoreFlatExtras, PWCore, Rope, SinixOps, Sisyph, StructuredStreams, TerminalIO, UnparserBuffer
EXPORTS PWCoreLichen
SHARES PWCore =
BEGIN OPEN CC: CoreClasses, CF: CoreFlat, CFE: PWCLCoreFlatExtras, CO: CoreOps, CP: CoreProperties, CSC: CoreStructuralComparison, PWCoreLichen, SS: StructuredStreams, UB: UnparserBuffer;
FlatWireRecList: TYPE = LIST OF CF.FlatWireRec;
DescendantList: TYPE = CSC.DescendantList;
ActualID: TYPE = CSC.ActualID;
Which: TYPE = {Source, Extracted};
HighlightData: TYPE = REF HighlightDataPrivate;
HighlightDataPrivate:
TYPE =
RECORD [
design: CD.Design,
viewer: ViewerClasses.Viewer
];
WhichOther: ARRAY Which OF Which = [Extracted, Source];
WhichName: ARRAY Which OF ROPE = ["Source", "Extracted"];
sourceToExtractedsKey: ATOM = CP.RegisterProperty[$PWCoreLichenSourceToExtracteds, CP.Props[[CP.propPrint, CP.PropDontPrint]]];
compared: ATOM = CP.RegisterProperty[$PWCoreLichenCompared, CP.Props[[CP.propPrint, CP.PropDontPrint]]];
done: REF INT ← NEW [INT ← 1];
hd: HighlightData ← NIL;
autoHack: BOOL ← FALSE;
CompareCmd:
PROC [cmd: CDSequencer.Command]
--CDSequencer.CommandProc-- = {
selected: CD.InstanceList ~ CDInstances.OnlySelected[CDOps.InstList[cmd.design]];
IF selected = NIL THEN TerminalIO.WriteF["You %ldo%l realize you have nothing selected, don't you?\n", [rope["e"]], [rope["E"]]];
FOR insts:
CD.InstanceList ← selected, insts.rest
WHILE insts #
NIL
DO
inst: CD.Instance = insts.first;
TerminalIO.WriteF["Extracting and comparing %g.\n", [rope[CDCommandOps.InstRope[inst]]]];
{objName: ROPE = CDDirectory.Name[inst.ob];
cx: Sisyph.Context = Sisyph.Create[cmd.design];
root: CellType = Sisyph.ExtractSchematicByName[objName, cx];
Compare[root];
TerminalIO.WriteF["Done extracting and comparing.\n"];
}ENDLOOP;
};
ForgetCmd:
PROC [cmd: CDSequencer.Command]
--CDSequencer.CommandProc-- = {
ForgetComparisons[];
};
EnableAutomorphismHack:
PROC [cmd: CDSequencer.Command]
--CDSequencer.CommandProc-- = {
SetAutomorphismHack[TRUE];
};
DisableAutomorphismHack:
PROC [cmd: CDSequencer.Command]
--CDSequencer.CommandProc-- = {
SetAutomorphismHack[FALSE];
};
ForgetComparisons: PUBLIC PROC = {done ← NEW [INT ← done^ + 1]};
SetAutomorphismHack: PUBLIC PROC [enabled: BOOL] = {autoHack ← enabled};
Compare:
PUBLIC
PROC [root: CellType] = {
key: REF INT = NARROW[CP.GetCellTypeProp[root, compared]];
layoutAtom: ATOM = PWCore.GetLayoutAtom[root];
SELECT
TRUE
FROM
key = done => RETURN; -- already done
layoutAtom#
NIL => {
indirectObj: CD.Object = PWCore.Layout[root];
layoutCellType: CellType = PWCore.CorrespondingCellType[indirectObj];
layoutData: PWCore.LayoutData = NARROW[layoutCellType.data];
source, extracted: CellType;
extractedToSource: HashTable.Table;
[sourceCellType: source, extractedCellType: extracted, extractedToSource: extractedToSource] ← PWCore.LayoutCellTypeInfo[layoutCellType];
MatchLeaves[extracted, source, extractedToSource, indirectObj, layoutData.mode.decoration, hd];
CP.PutCellTypeProp[root, compared, done];
};
root.class=CC.recordCellClass => ERROR;
ENDCASE => Compare[CO.Recast[root]];
};
SourceSubtree:
PROC [instance:
CC.CellInstance, path:
CF.InstancePath]
RETURNS [leafType: CellType]
--CSC.SubtreeSpec-- = {
ct: CellType ← instance.type;
DO
IF PWCore.GetLayoutAtom[ct] # NIL THEN RETURN [ct];
IF ct.class.recast = NIL THEN RETURN [IF ct.class # CC.recordCellClass THEN ct ELSE NIL];
ct ← CO.Recast[ct];
ENDLOOP;
};
ExtractedSubtree:
PROC [instance:
CC.CellInstance, path:
CF.InstancePath]
RETURNS [leafType: CellType]
--CSC.SubtreeSpec-- = {
ct: CellType ← instance.type;
DO
IF ct.class = PWCore.layoutClass
THEN {
sourceCellType: CellType = PWCore.LayoutCellTypeInfo[ct].sourceCellType;
Compare[sourceCellType];
RETURN [sourceCellType];
};
IF ct.class.recast = NIL THEN RETURN [IF ct.class # CC.recordCellClass THEN ct ELSE NIL];
ct ← CO.Recast[ct];
ENDLOOP;
};
Signal:
SIGNAL [msg:
ROPE] =
CODE;
-- to give the possibility to continue
namesOfCellTypesToIgnore: HashTable.Table ← HashTable.Create[equal: HashTable.RopeEqualModCase, hash: HashTable.HashRopeModCase];
MatchLeaves:
PROC [extractedRoot, sourceRoot: CellType, extractedToSource: HashTable.Table, indirectObj:
CD.Object, decoration: SinixOps.Decoration, hd: HighlightData] = {
extractedRoot ← FuseTransistors[extractedRoot]; -- Patch good enough for now
{
sourceToExtracteds: HashTable.Table = ReverseHashTable[extractedToSource];
GiveHints:
PROC [
Consume:
PROC [dA, dB:
CSC.Descendant]]
--HintsGiver-- = {
PassPair:
PROC [key, value:
REF
ANY]
RETURNS [quit:
BOOL ←
FALSE]
--EachPairProc-- = {
sourcePublic: Wire = NARROW[key];
extractedPublics: DescendantList = NARROW[value];
Consume[extractedPublics.first, NEW [CF.FlatWireRec ← [wireRoot: public, wire: sourcePublic]]];
};
[] ← sourceToExtracteds.Pairs[PassPair];
};
ii: CD.Instance ← NIL;
PerMismatch:
PROC
[
kind: CSC.MismatchKind,
ctA, ctB: Core.CellType,
fromA, fromB: DescendantList,
AnsA, AnsB: CSC.QueryAnswerer
]
= {
cellTypeName: ROPE = CO.GetCellTypeName[sourceRoot];
Ignore: PROC = {IF cellTypeName.Length[] > 0 THEN [] ← namesOfCellTypesToIgnore.Store[cellTypeName, $TRUE] ELSE ERROR--can't do it, you turkey--};
PrintNeighborhoods:
PROC [to:
IO.
STREAM] = {
IF NOT SS.IsAnSS[to] THEN to ← SS.Create[UB.NewInittedHandle[[margin: 50, output: [stream[to]]]]];
to.PutRope["Neighborhoods are: "];
PrintNeighborhood[to, sourceRoot, Source, fromB];
PrintNeighborhood[to, extractedRoot, Extracted, fromA];
};
PrintNeighborhood:
PROC [to:
IO.
STREAM, root: CellType, which: Which, ds: DescendantList] = {
other: Which = WhichOther[which];
CutTest:
PROC [cutData:
REF
ANY, root, cellType: CellType, flatCell:
CF.FlatCellTypeRec, instance:
CC.CellInstance]
RETURNS [
BOOL]
--CFE.CutMembershipTester-- = {
RETURN [instance # NIL AND (SELECT which FROM Source => SourceSubtree, Extracted => ExtractedSubtree, ENDCASE => ERROR)[instance, flatCell.path] # NIL];
};
Annotate:
PROC [subject:
CFE.Descendant, to:
IO.
STREAM] = {
PrintDL:
PROC [which: Which, dls: DescendantList, except:
CSC.Descendant] = {
first: BOOL ← TRUE;
to.PutRope["{"];
FOR dls ← dls, dls.rest
WHILE dls #
NIL
DO
IF except =
NIL
OR
NOT
CSC.DescendantEqual[except, dls.first]
THEN {
IF first THEN first ← FALSE ELSE to.PutRope[", "];
to.PutRope[
WITH dls.first
SELECT
FROM
x: CF.FlatWire => CF.WirePathRope[root, x^],
x: REF CF.InstancePath => CF.InstancePathRope[root, x^],
ENDCASE => ERROR];
};
ENDLOOP;
to.PutRope["}"];
};
WITH subject
SELECT
FROM
x: CF.FlatWire => NULL;
x: REF CF.InstancePath => NULL;
x: CF.FlatCellType => subject ← NEW [CF.InstancePath ← x.path];
ENDCASE => ERROR;
{dlp:
CSC.DescendantListPair =
SELECT which
FROM
Extracted => AnsA[subject],
Source => AnsB[subject],
ENDCASE => ERROR;
IF dlp # [
NIL,
NIL]
THEN {
dls: ARRAY Which OF DescendantList = [Extracted: dlp.A, Source: dlp.B];
IF dls[which].rest #
NIL
THEN {
to.PutRope["&"];
PrintDL[which, dls[which], subject];
};
to.PutRope["~"];
PrintDL[other, dls[other], NIL];
};
}};
Printit:
PROC =
TRUSTED {
to.PutRope[WhichName[which].Concat[": "]];
CFE.PrintNeighborhood[root, ds, to, Annotate, [CutTest]];
};
PrintObject[to, Printit, always, " "];
to ← to;
};
fws: FlatWireRecList ← NIL;
IF cellTypeName.Length[] > 0 AND namesOfCellTypesToIgnore.Fetch[cellTypeName].found THEN RETURN;
PW.WriteF["*** %g between extracted and source for %g:\n", IO.rope[IF kind=difference THEN "Difference" ELSE "Stuck"], IO.rope[cellTypeName]];
PW.WriteF["\textracted\t=> %g\n", IO.rope[DescendantsToRope[fromA, ctA]]];
PW.WriteF["\tsource\t=> %g\n", IO.rope[DescendantsToRope[fromB, ctB]]];
FOR eds: DescendantList ← fromA, eds.rest
UNTIL eds =
NIL
DO
WITH eds.first
SELECT
FROM
di: CSC.DescendantCellInstance => NULL;
dw: CSC.DescendantWire => fws ← CONS[dw^, fws];
ENDCASE => ERROR;
ENDLOOP;
{highlight: BOOL = fws # NIL;
IF highlight
THEN {
IF ii=NIL THEN ii ← CDInstances.NewInstI[ob: indirectObj];
IF hd=
NIL
THEN {
hd ← NEW [HighlightDataPrivate ← []];
hd.design ← CDOps.CreateDesign[CD.FetchTechnology[$cmosB]];
hd.viewer ← CDViewer.CreateViewer[hd.design];
};
CDOps.IncludeInstance[hd.design, ii];
SinixOps.HighlightNets[decoration, hd.design, ii, extractedRoot, fws];
};
Signal["Joe Bob sez check it out"];
IF highlight
THEN {
SinixOps.HighlightDesign[hd.design, NIL];
};
}};
CP.PutCellTypeProp[extractedRoot, sourceToExtractedsKey, sourceToExtracteds];
IF NOT CSC.FlattenAndCompare[extractedRoot, sourceRoot, --we need them in this order because ExtractedSubtree would side-effect the data-structure created from sourceRoot if it came second--ExtractedSubtree, SourceSubtree, MergeByPinsAndFuseTransistors, CSC.MergeNothing, GiveHints, NIL, PerMismatch, NIL, autoHack].isomorphic THEN Signal["Done with that cell type"];
}};
MergeByPinsAndFuseTransistors:
PROC
[
original, parent: Core.CellType,
path: CF.InstancePath,
EnumerateInstances: PROC [Consume: PROC [ci: CC.CellInstance] RETURNS [stop: BOOL ← FALSE]],
IdentifyActual: PROC [ci: CC.CellInstance, actual: Core.Wire, describe: BOOL ← FALSE] RETURNS [ActualID],
Consume: CSC.MergeConsumer] =
{nFused: NAT ← 0;
fkey: REF ~ NEW [ROPE ← "fused"];
FuseTransistors:
PROC = {
Describe:
PROC [ci:
CC.CellInstance]
RETURNS [description:
ROPE] = {
ip: CF.InstancePath = CF.AddInstance[CF.nullInstancePath, ci, parent];
description ← CF.InstancePathRope[parent, ip];
};
CheckChild:
PROC [ci:
CC.CellInstance]
RETURNS [stop:
BOOL ←
FALSE] = {
IF ci.type.class # CC.transistorCellClass THEN RETURN;
{ci1: CC.CellInstance = ci;
g1: ActualID = IdentifyActual[ci1, ci1.actual[0], debug];
c1a: ActualID = IdentifyActual[ci1, ci1.actual[1], debug];
c1b: ActualID = IdentifyActual[ci1, ci1.actual[2], debug];
CheckOthers:
PROC [ci:
CC.CellInstance]
RETURNS [stop:
BOOL ←
FALSE] = {
IF ci.type.class # CC.transistorCellClass OR CP.GetCellInstanceProp[ci, fused] = fkey THEN RETURN;
IF ci = ci1 THEN RETURN [TRUE];
{ci2: CC.CellInstance = ci;
g2: ActualID = IdentifyActual[ci2, ci2.actual[0], debug];
IF g1.id = g2.id
THEN {
c2a: ActualID = IdentifyActual[ci2, ci2.actual[1], debug];
c2b: ActualID = IdentifyActual[ci2, ci2.actual[2], debug];
IF c1a.id=c2a.id
AND c1b.id=c2b.id
OR c1a.id=c2b.id
AND c1b.id=c2a.id
THEN {
t1: CC.Transistor = NARROW [ci1.type.data];
t2: CC.Transistor = NARROW [ci2.type.data];
IF t1.type=t2.type
AND t1.length=t2.length
THEN {
IF debug THEN PW.WriteF["%g || %g\n", [rope[Describe[ci1]]], [rope[Describe[ci2]]]];
CP.PutCellInstanceProp[ci2, fused, fkey];
nFused ← nFused + 1;
Consume[
LIST[
NEW [CF.InstancePath ← CF.AddInstance[path, ci1, parent]],
NEW [CF.InstancePath ← CF.AddInstance[path, ci2, parent]]]];
}
ELSE IF debug THEN PW.WriteF["%g # %g\n", [rope[Describe[ci1]]], [rope[Describe[ci2]]]];
}
ELSE
IF debug
THEN {
PW.WriteF["%g[%g, %g] # ", [rope[Describe[ci1]]], [rope[c1a.description]], [rope[c1b.description]]];
PW.WriteF["%g[%g, %g]\n", [rope[Describe[ci2]]], [rope[c2a.description]], [rope[c2b.description]]];
};
}
ELSE IF debug THEN PW.WriteF["%g.gate~%g # %g.gate~%g\n", [rope[Describe[ci1]]], [rope[g1.description]], [rope[Describe[ci2]]], [rope[g2.description]]];
}};
EnumerateInstances[CheckOthers];
}};
EnumerateInstances[CheckChild];
IF nFused # 0
THEN {
PW.WriteF["*** PWCoreLichen: %g pairwise transistor fusions in CellType %g.\n", [integer[nFused]], [rope[CO.GetCellTypeName[parent]]]];
};
};
FuseTransistors[];
IF path.length = 0
THEN {
sourceToExtracteds: HashTable.Table = NARROW[CP.GetCellTypeProp[original, sourceToExtractedsKey]];
MergeExtracted:
PROC [key, value:
REF
ANY]
RETURNS [quit:
BOOL ←
FALSE]
--EachPairProc-- = {
sourcePublic: Wire = NARROW[key];
extractedPublics: DescendantList = NARROW[value];
IF extractedPublics.rest # NIL THEN Consume[extractedPublics];
};
[] ← sourceToExtracteds.Pairs[MergeExtracted];
};
};
fused: ATOM = CP.RegisterProperty[$PWCoreLichenTransistorFused, CP.Props[[CP.propPrint, CP.PropDontPrint]]];
debug: BOOL ← FALSE;
DescendantsToRope:
PROC [descendants:
LIST
OF
REF, root: CellType]
RETURNS [rope:
ROPE ←
NIL] = {
sep: ROPE ← NIL;
WHILE descendants#
NIL
DO
rope ← rope.Cat[sep,
WITH descendants.first
SELECT
FROM
fi: REF CF.InstancePath => CF.InstancePathRope[root, fi^],
fw: CF.FlatWire => CF.WirePathRope[root, fw^],
ENDCASE => ERROR];
descendants ← descendants.rest;
sep ← ", ";
ENDLOOP;
};
FuseTransistors: PROC [recordCell: CellType] RETURNS [new: CellType] = {
oldData, newData, data: CC.RecordCellType;
nb, fused: NAT ← 0;
IF recordCell.class#CC.recordCellClass THEN RETURN [recordCell];
oldData ← NARROW [recordCell.data];
data ← NEW [CC.RecordCellTypeRec[oldData.size]];
data.internal ← oldData.internal;
FOR i: NAT IN [0 .. data.size) DO data[i] ← oldData[i] ENDLOOP;
FOR i: NAT IN [0 .. data.size) DO
IF data[i]=NIL THEN LOOP;
data[i].type ← FuseTransistors[data[i].type];
IF data[i].type.class#CC.transistorCellClass THEN LOOP;
FOR j: NAT IN [0 .. i) DO
IF data[j]=NIL THEN LOOP;
IF data[j].type.class#CC.transistorCellClass THEN LOOP;
IF data[i].actual[0]=data[j].actual[0] AND ((data[i].actual[1]=data[j].actual[1] AND data[i].actual[2]=data[j].actual[2]) OR (data[i].actual[2]=data[j].actual[1] AND data[i].actual[1]=data[j].actual[2])) THEN {
t1: CC.Transistor ← NARROW [data[i].type.data];
t2: CC.Transistor ← NARROW [data[j].type.data];
IF t1.type=t2.type AND t1.length=t2.length THEN {
data[i] ← CC.CreateInstance[
actual: data[i].actual,
type: CC.CreateTransistor[
args: [type: t1.type, length: t1.length, width: t1.width + t2.width],
props: data[i].type.properties
],
props: data[i].properties
];
data[j] ← NIL;
fused ← fused + 1;
};
};
ENDLOOP;
ENDLOOP;
IF fused=0 THEN RETURN [recordCell];
PW.WriteF["*** Lichen for PWCore.Get: fused %g transistors.\n", IO.int[fused]];
new ← CO.CreateCellType[CC.recordCellClass, recordCell.public, NEW [CC.RecordCellTypeRec[data.size-fused]], NIL, recordCell.properties];
newData ← NARROW [new.data];
newData.internal ← data.internal;
FOR i: NAT IN [0 .. data.size) DO
IF data[i]=NIL THEN LOOP;
newData[nb] ← data[i]; nb ← nb + 1;
ENDLOOP;
};
ReverseHashTable:
PROC [fwd: HashTable.Table]
RETURNS [bkwd: HashTable.Table] = {
CopyPair:
PROC [key, value:
REF
ANY]
RETURNS [quit:
BOOL ←
FALSE]
--HashTable.EachPairProc-- = {
wfrom: Wire = NARROW[key];
wto: Wire = NARROW[value];
lfrom: DescendantList ← NARROW[bkwd.Fetch[wto].value];
lfrom ← CONS[NEW [CF.FlatWireRec ← [wireRoot: public, wire: wfrom]], lfrom];
[] ← bkwd.Store[wto, lfrom];
};
bkwd ← HashTable.Create[];
[] ← fwd.Pairs[CopyPair];
bkwd ← bkwd;
};
HashPath:
PROC [ra:
REF
ANY]
RETURNS [hash:
CARDINAL]
--HashTable.HashProc-- = {
path: REF CF.InstancePath = NARROW[ra];
hash ← CF.InstancePathHash[path^];
};
EqualPath:
PROC [r1, r2:
REF
ANY]
RETURNS [eq:
BOOL]
--HashTable.EqualProc-- = {
p1: REF CF.InstancePath = NARROW[r1];
p2: REF CF.InstancePath = NARROW[r2];
eq ← CF.InstancePathEqual[p1^, p2^];
};
PrintObject:
PROC [to:
IO.
STREAM,
PrintIt:
PROC, cond:
UB.BreakCondition ← width, sep:
ROPE ←
NIL] = {
SS.Bp[to, cond, step, sep];
SS.Begin[to];
PrintIt[!UNWIND => SS.End[to]];
SS.End[to];
};
step: NAT ← 3;
Start:
PROC = {
CDMenus.ImplementEntryCommand[
menu: $ProgramMenu,
entry: "Sisyph Extract design & structurally compare to layout",
p: CompareCmd
];
CDMenus.ImplementEntryCommand[
menu: $ProgramMenu,
entry: "Forget comparison results",
p: ForgetCmd
];
CDMenus.ImplementEntryCommand[
menu: $ProgramMenu,
entry: "Enable Automorphism Hack",
p: EnableAutomorphismHack
];
CDMenus.ImplementEntryCommand[
menu: $ProgramMenu,
entry: "Disable Automorphism Hack",
p: DisableAutomorphismHack
];
};
Start[];
END.