CompareCellDefs:
CEDAR
PROGRAM
IMPORTS CompareOps, IO, OrderedSymbolTableRef, Real, Rope
EXPORTS CompareDataStructure, CompareOps =
BEGIN OPEN CompareDataStructure, CompareOps;
TwoCount: TYPE = ARRAY RealGraphID OF CARDINAL;
graphIDToRope: PUBLIC ARRAY GraphID OF ROPE ← [A: "A", B: "B", Unspecified: "Unspecified"];
endOfQ: PUBLIC Vertex ← NEW [VertexRep];
PortHashSize: CARDINAL = LAST[HashTableIndex];
MinHashSize: CARDINAL ← 511;
sizeFactor: REAL ← 0.25;
initialNetColor: Color ← 1;
CompareGraphs:
PUBLIC
PROC [a, b: CellType, seeAllInstanceNames:
BOOL]
RETURNS [equiv:
BOOL] =
BEGIN
ComputeColor:
PROC [v: Vertex]
RETURNS [color: Color] = {
color ← v.oldColor;
FOR e: Edge ← v.firstEdge, e.sides[v.class].next
WHILE e #
NIL
DO
nv: Vertex ← e.sides[OtherClass[v.class]].v;
IF e.sides[v.class].v # v THEN ERROR;
IF NOT nv.suspect THEN color ← (color + (e.color+1) * (nv.oldColor+1)) MOD hashTable.length;
ENDLOOP};
EnQ: PROC [v: Vertex] = {IF (NOT v.unique) AND (v.QNext = notInQ) THEN {v.QNext ← QFirst; QFirst ← v; QCount ← QCount + 1}};
AddFrontier:
PROC [v: Vertex] = {
FOR e: Edge ← v.firstEdge, e.sides[v.class].next
WHILE e #
NIL
DO
IF e.sides[v.class].v # v THEN ERROR;
EnQ[e.sides[OtherClass[v.class]].v];
ENDLOOP};
Initialize:
PROC = {
InitVertex:
PROC [ra:
REF
ANY]
RETURNS [stop:
BOOL] = {
v: Vertex;
stop ← FALSE;
WITH ra
SELECT
FROM
vtx: Vertex => v ← vtx;
a: Alias => {v ← NARROW[AntiAlias[a]]; IF a.name # PickAName[v.names] THEN RETURN};
ENDCASE => ERROR;
v.graph ← curGraph;
IF v.unique OR v.QNext # notInQ THEN ERROR;
v.equiv ← NIL;
v.suspect ← FALSE;
SELECT v.class
FROM
net => v.curColor ← initialNetColor;
cell => {
portIndex: PortIndex ← 0;
IF v.type.inittedFor # hts THEN InitCellType[v.type];
v.curColor ← v.type.color;
FOR e: Edge ← v.firstEdge, e.sides[cell].next
WHILE e #
NIL
DO
IF e.portIndex # portIndex THEN ERROR;
IF e.sides[cell].v # v THEN ERROR;
e.color ← v.type.ports[portIndex].color;
portIndex ← portIndex + 1;
ENDLOOP;
IF portIndex # v.type.ports.length THEN ERROR;
};
ENDCASE => ERROR;
v.oldColor ← v.curColor;
EnQ[v]};
InitCellType:
PROC [ct: CellType] = {
ct.inittedFor ← hts;
ct.color ← HashRope[CTEquivClass[ct], hts];
FOR pi: PortIndex
IN [0 .. ct.ports.length)
DO
ct.ports[pi].color ← HashRope[PortEquivClass[ct, pi], PortHashSize];
ENDLOOP;
};
hts: CARDINAL ← MAX[MinHashSize, Real.RoundC[sizeFactor * (a.parts.Size[] + b.parts.Size[] + 2)]];
curGraph: RealGraphID;
QFirst ← endOfQ; QCount ← 0;
hashTable ← NEW [HashTableRep[hts]];
hashTable.firstNonEmpty ← NullIndex;
FOR hti: HashTableIndex
IN [0 .. hashTable.length)
DO
hashTable[hti] ← [];
ENDLOOP;
curGraph ← A;
a.parts.EnumerateIncreasing[InitVertex]; [] ← InitVertex[a.mirror]; --AM1
curGraph ← B;
b.parts.EnumerateIncreasing[InitVertex]; [] ← InitVertex[b.mirror];
nonUniqueCount[A] ← a.parts.Size[] + 1;
nonUniqueCount[B] ← b.parts.Size[] + 1;
IF QCount # (nonUniqueCount[A] + nonUniqueCount[B]) THEN ERROR;
};
SetQToAllNonUniques:
PROC = {
AddVertex:
PROC [ra:
REF
ANY]
RETURNS [stop:
BOOL] = {
v: Vertex;
stop ← FALSE;
WITH ra
SELECT
FROM
vtx: Vertex => v ← vtx;
a: Alias => {v ← NARROW[AntiAlias[a]]; IF a.name # PickAName[v.names] THEN RETURN};
ENDCASE => ERROR;
IF v.QNext # notInQ THEN ERROR;
EnQ[v]};
wasAll ← TRUE;
a.parts.EnumerateIncreasing[AddVertex]; [] ← AddVertex[a.mirror]; --AM1
b.parts.EnumerateIncreasing[AddVertex]; [] ← AddVertex[b.mirror];
IF QCount # (nonUniqueCount[A] + nonUniqueCount[B]) THEN ERROR;
hashTable.firstNonEmpty ← NullIndex};
ChoosePairs:
PROC [useSuspects:
BOOL]
RETURNS [pairCount:
CARDINAL] = {
wasAll ← TRUE; pairCount ← 0;
FOR hti: HashTableIndex ← hashTable.firstNonEmpty, hashTable[hti].nextNonEmpty
WHILE hti # NullIndex
DO
first: ARRAY RealGraphID OF Vertex ← [NIL, NIL];
IF hashTable[hti].suspect # useSuspects THEN LOOP;
FOR v: Vertex ← hashTable[hti].v, v.colorNext
WHILE v #
NIL
DO
IF v.QNext # notInQ THEN ERROR;
IF first[v.graph] = NIL THEN first[v.graph] ← v;
ENDLOOP;
IF first[
A]#
NIL
AND first[
B]#
NIL
THEN {
IF first[A].unique # first[B].unique THEN ERROR;
IF
NOT first[
A].unique
THEN {
IF first[A].QNext # notInQ THEN ERROR;
IF first[B].QNext # notInQ THEN ERROR;
pairCount ← pairCount + 1;
EnQ[first[A]]; EnQ[first[B]]}};
ENDLOOP;
hashTable.firstNonEmpty ← NullIndex};
nonUniqueCount: TwoCount ← ALL[LAST[CARDINAL]];
hashTable: HashTable ← NIL;
pass: CARDINAL ← 0;
QFirst: Vertex;
QCount: CARDINAL;
wasAll: BOOL ← TRUE;
Initialize[];
WriteAll["CompareCDs Initialized", a, b, hashTable];
WHILE nonUniqueCount[
A]#0
AND nonUniqueCount[
B]#0
DO
mcCount: CARDINAL ← 0;
someMC: BOOL ← FALSE;
pass ← pass + 1;
WHILE QFirst # endOfQ
DO
v: Vertex ← QFirst;
oldColor: Color ← v.oldColor;
newColor: Color ← v.curColor ← ComputeColor[v];
IF QFirst = notInQ THEN ERROR;
QFirst ← v.QNext;
v.QNext ← notInQ;
IF wasAll
AND
NOT someMC
THEN {
IF hashTable[oldColor].newColor = noColor THEN hashTable[oldColor].newColor ← newColor
ELSE IF hashTable[oldColor].multicolored THEN ERROR
ELSE IF hashTable[oldColor].newColor = newColor THEN NULL
ELSE hashTable[oldColor].multicolored ← someMC ← TRUE;
};
IF hashTable[newColor].count[
A] = 0
AND hashTable[newColor].count[
B] = 0
THEN {
hashTable[newColor].v ← NIL;
hashTable[newColor].nextNonEmpty ← hashTable.firstNonEmpty;
hashTable.firstNonEmpty ← newColor};
v.colorNext ← hashTable[newColor].v;
hashTable[newColor].v ← v;
hashTable[newColor].count[v.graph] ← hashTable[newColor].count[v.graph] + 1;
ENDLOOP;
QCount ← 0;
FOR hti: HashTableIndex ← hashTable.firstNonEmpty, hashTable[hti].nextNonEmpty
WHILE hti # NullIndex
DO
uniques: ARRAY RealGraphID OF BOOL = [hashTable[hti].count[A]=1, hashTable[hti].count[B]=1];
unique: BOOL ← uniques[A] AND uniques[B];
IF unique
THEN {
a: Vertex ← hashTable[hti].v;
b: Vertex ← a.colorNext;
IF b.colorNext # NIL THEN ERROR;
IF a.graph = b.graph THEN ERROR;
IF a.unique OR b.unique THEN ERROR;
a.unique ← b.unique ← TRUE;
a.equiv ← b; b.equiv ← a;
nonUniqueCount[A] ← nonUniqueCount[A] - 1;
nonUniqueCount[B] ← nonUniqueCount[B] - 1;
};
ENDLOOP;
FOR hti: HashTableIndex ← hashTable.firstNonEmpty, hashTable[hti].nextNonEmpty
WHILE hti # NullIndex
DO
uniques: ARRAY RealGraphID OF BOOL = [hashTable[hti].count[A]=1, hashTable[hti].count[B]=1];
unique: BOOL ← uniques[A] AND uniques[B];
IF unique
THEN {
a: Vertex ← hashTable[hti].v;
b: Vertex ← a.colorNext;
IF b.colorNext # NIL THEN ERROR;
IF a.graph = b.graph THEN ERROR;
IF NOT (a.unique AND b.unique) THEN ERROR;
AddFrontier[a]; AddFrontier[b];
};
hashTable[hti].suspect← hashTable[hti].count[A] # hashTable[hti].count[B];
FOR v: Vertex ← hashTable[hti].v, v.colorNext
WHILE v #
NIL
DO
v.oldColor ← v.curColor;
v.suspect ← hashTable[hti].suspect;
ENDLOOP;
hashTable[hti].count[A] ← 0;
hashTable[hti].count[B] ← 0;
hashTable[hti].newColor ← noColor;
hashTable[hti].multicolored ← FALSE;
ENDLOOP;
WriteAll[IO.PutFR["Almost end of pass %g", IO.card[pass]], a, b, hashTable];
Log["QCount=%g, nonUniqueCount=[%g, %g], someMC=%g, wasAll=%g\n",
IO.card[QCount], IO.card[nonUniqueCount[A]],
IO.card[nonUniqueCount[B]], IO.bool[someMC], IO.bool[wasAll]];
WriteQ[QFirst];
IF QCount > 0
THEN {
wasAll ← (nonUniqueCount[A] + nonUniqueCount[B]) = QCount;
hashTable.firstNonEmpty ← NullIndex}
ELSE IF someMC OR (NOT wasAll) THEN SetQToAllNonUniques[]
ELSE {pairCount:
CARDINAL ← ChoosePairs[useSuspects:
FALSE];
IF pairCount = 0
THEN {QFirst ← endOfQ; QCount ← 0;
pairCount ← ChoosePairs[useSuspects: TRUE];
IF pairCount = 0 THEN EXIT}};
ENDLOOP;
equiv ← nonUniqueCount[A]=0 AND nonUniqueCount[B]=0;
END;
HashRope:
PROC [r:
ROPE, hashTableSize:
CARDINAL]
RETURNS [c: Color] =
BEGIN
len: INT = r.Length[];
c ← 1;
FOR i:
INT
DECREASING
IN [0 .. len)
DO
char: CHAR ← r.Fetch[i];
long: LONG CARDINAL ← rot*c + (char-0C);
c ← long MOD hashTableSize;
ENDLOOP;
END;
rot: LONG CARDINAL ← 128 + 32 + 2;
CTEquivClass:
PROC [ct: CellType]
RETURNS [equivClass: EquivClass] = {
equivClass ← IF ct.equivClass = implicitClass THEN PickAName[ct.names] ELSE ct.equivClass};
PortEquivClass:
PROC [ct: CellType, pi: PortIndex]
RETURNS [equivClass: EquivClass] = {
equivClass ← IF ct.ports[pi].equivClass = implicitClass THEN PickAName[ct.ports[pi].names] ELSE ct.ports[pi].equivClass};
WriteQ:
PROC [QFirst: Vertex] =
BEGIN
first: BOOL ← TRUE;
Log["Q = {"];
FOR QFirst ← QFirst, QFirst.QNext
WHILE QFirst # endOfQ
DO
IF QFirst = notInQ THEN ERROR;
IF first THEN first ← FALSE ELSE Log[", "];
Log["%g.%g", IO.rope[graphIDToRope[QFirst.graph]], IO.rope[PickAName[QFirst.names]]];
ENDLOOP;
Log["}\n"];
END;
Test:
PROC [da, db: Design, aName, bName:
ROPE] =
BEGIN
aType: CellType ← NARROW[Lookup[da.cellTypesByName, aName]];
bType: CellType ← NARROW[Lookup[db.cellTypesByName, bName]];
equiv: BOOL;
EnsureParts[aType];
EnsureParts[bType];
Log["\nTesting %g %g\n", IO.rope[aName], IO.rope[bName]];
equiv ← CompareGraphs[aType, bType, FALSE];
Log["\nEquiv = %g.\n", IO.bool[equiv]];
FlushLog[];
END;
END.