DrotImpl.mesa
Copyright Ó 1987 by Xerox Corporation. All rights reserved.
Csaba Gabor August 21, 1987 2:17:27 pm PDT
Bertrand Serlet August 21, 1987 2:24:21 pm PDT
DIRECTORY
Commander, IO, Process, Rope, ViewerIO, ViewerTools, Convert, Core, CoreCreate, CoreDirectory, CoreOps, CoreProperties, SymTab, DrotBool, DrotCover, Drot;
DrotImpl: CEDAR MONITOR
IMPORTS Commander, IO, Process, Rope, ViewerIO, ViewerTools, Convert, CoreCreate, CoreDirectory, CoreOps, CoreProperties, SymTab, DrotBool, DrotCover
EXPORTS Drot
~ BEGIN OPEN DrotBool, DrotCover, Drot;
Top Level Calls
CellTypeFromExpressions: PUBLIC PROC [outputs: LIST OF ROPE, fanout: INT ← 4] RETURNS [Core.CellType] ~ {
Given a list of Boolean Expressions this will return a CellType which they generate
tree: Dag ← BoolTreeFromExpressionList[outputs, TRUE];
RETURN[CreateCellTypeFromDag[tree, fanout]]
};
CreateCellTypeFromDag: PUBLIC PROC [tree: Dag, fanout: INT ← 4] RETURNS [Core.CellType] ~ {
Given a tree, this will construct a CellType which implements the equations described by the tree
ctcoll: Treeset ← MakeNewCTreeSet[];
AssembleCTree[ctcoll];
FOR ctiter: Dag ← ctcoll^.top, ctiter^.next UNTIL ctiter = NIL DO
RemoveOrs[ctiter];
ENDLOOP;
TwoifyAllTrees[ctcoll];
SimplifyDag[tree];
EstablishLevels[tree];
TwoifyTree[tree];
ReduceFanout[tree, fanout];
RemoveOrs[tree];
WHILE RemoveAllIdenticalLinks[tree] OR RemoveDuplicateNodes[tree] DO ENDLOOP;
BufferNecessaryNodes[tree];
ReduceFanout[tree, fanout];
KillHangingNodes[tree, FALSE];
ProduceTotalCovering[tree, ctcoll];
RETURN[FromDagToCellType[tree]]
};
Parse: PUBLIC PROC [tree: Dag, be: ROPE, inpos, len: INT] RETURNS [outv: Node, outpos: INT] ~ {
Given a Boolean expression, be, this will make incorporate it in tree representation into tree. Len is the length of be and is passed to avoid recomputing it--
onode, anode, temp: Node ← NIL; --the current or and and node
andcount, orcount: INT ← 0; --the number of terms encountered so far in the current or and and.
notactivep: BOOL ← FALSE; --should we negate the current expression
WHILE inpos # len DO
SELECT Rope.Fetch[be, inpos] FROM
'( => { --Parse a subexpression
[outv: temp, outpos: inpos] ← Parse[tree, be, inpos+1, len];
IF notactivep THEN temp ← Negate[tree, temp];
notactivep ← FALSE;
IF andcount > 0 THEN MakeLink[anode, temp];
andcount ← andcount + 1};
' => --Ignore spaces
NULL;
'~ => --We should negate the next expression
notactivep ← NOT notactivep;
'* => --The past item was a term in a multiply
IF andcount = 1 THEN {
[] ← MakeNewNodeA[tree, NIL, and];
anode ← tree^.csucs;
MakeLink[anode, temp]};
'+ => { --The past item was a term in an add
IF orcount = 0
THEN {
[] ← MakeNewNodeA[tree, NIL, or];
onode ← tree^.csucs};
orcount ← orcount + 1;
IF andcount = 1
THEN MakeLink[onode, temp]
ELSE MakeLink[onode, anode];
andcount ← 0};
') => { --we've just finished an expression
IF orcount # 0
THEN {
outv ← onode;
IF andcount = 1
THEN MakeLink[onode, temp]
ELSE MakeLink[onode, anode]}
ELSE IF andcount = 1
THEN outv ← temp
ELSE outv ← anode;
outpos ← inpos;
RETURN}
ENDCASE => { --there is an input variable to be processed
nomen: ROPE;
[name: nomen, outpos: inpos] ← GetName[be, inpos];
temp ← FindNodeByName[tree, nomen];
IF temp = NIL THEN {
[] ← MakeNewNodeA[tree, NIL ,prim];
temp ← tree^.csucs;
temp^.inname ← nomen};
IF notactivep THEN temp ← Negate[tree, temp];
notactivep ← FALSE;
IF andcount > 0 THEN MakeLink[anode, temp];
andcount ← andcount + 1};
inpos ← inpos + 1;
outpos ← inpos;
ENDLOOP;
};
GetName: PROC [be: ROPE, inpos: INT] RETURNS [name: ROPE, outpos: INT] ~ {
Finds the next name substring in the input ROPE, be--
endpos: INT ← Rope.SkipTo[be, inpos, "()+*"] - 1;
inpos ← Rope.SkipOver[be, inpos, " "];
outpos ← endpos;
WHILE Rope.Fetch[be,endpos] = ' DO
endpos ← endpos - 1
ENDLOOP;
name ← Rope.Substr[be, inpos, endpos - inpos + 1]
};
AugmentBoolTreeBySingleExpression: PUBLIC PROC [tree: Dag, output: ROPE] ~ {
This calls Parse after a minor amount of preprocessing, it will add the parsed contents of output to tree--
len: INT ← Rope.Length[output];
be: ROPE;
v1: Node;
asspos: INT ← Rope.Find[output, "=", 0];
internal: BOOL ← asspos > -1;
asspos ← MAX[asspos, Rope.Find[output, "←", 0]];
be ← Rope.Substr[output, asspos + 1, len - asspos - 1];
IF InputOKp[be]
THEN {
[outv: v1] ← Parse[tree, Rope.Cat["(", be, ")"], 1, Rope.Length[be]+2];
IF asspos > -1 THEN IF internal
THEN v1^.varname ← Rope.Substr[output,0,asspos -1]
ELSE v1^.outname ← CONS[Rope.Substr[output,0,asspos -1], v1^.outname];
IF NOT internal THEN v1^.output ← TRUE}
ELSE ERROR
};
AddInputToCover: PUBLIC PROC [be1: ROPE, ctcoll: Treeset] ~ {
This calls Parse after a minor amount of preprocessing but it adds the representation to the growing set of trees, ctcoll, which are used for covering the main tree--
iter: Node;
len: INT ← Rope.Length[be1];
asspos: INT ← Rope.Find[be1, "←", 0];
be : ROPE ← Rope.Substr[be1, asspos + 1, len - asspos - 1];
MakeNewCTree[ctcoll, NIL];
IF InputOKp[be]
THEN {
[outv: iter] ← Parse[ctcoll^.top, Rope.Cat["(",be,")"], 1, Rope.Length[be] + 2];
IF asspos > -1 THEN iter^.outname ← CONS[Rope.Substr[be1,0,asspos - 1], iter^.outname];
iter^.output ← TRUE}
ELSE ERROR
};
AssembleCTree: PROC [ctcoll: Treeset] ~ {
This is where the trees to be used in the cover are created.
1 input
AddInputToCover["X ← ~I", ctcoll];
ctcoll^.top^.cell ← NARROW[SymTab.Fetch[CoreDirectory.FetchLibrary["CMOSB"], "inv"].val];
ctcoll^.top^.val ← NARROW[CoreProperties.GetCellTypeProp[ctcoll^.top^.cell, $CellArea], REF INT]^;
2 inputs
AddInputToCover["X ← ~(I-A * I-B)", ctcoll];
ctcoll^.top^.cell ← NARROW[SymTab.Fetch[CoreDirectory.FetchLibrary["CMOSB"], "nand2"].val];
ctcoll^.top^.val ← NARROW[CoreProperties.GetCellTypeProp[ctcoll^.top^.cell, $CellArea], REF INT]^;
AddInputToCover["X ← I-A * I-B", ctcoll];
ctcoll^.top^.cell ← NARROW[SymTab.Fetch[CoreDirectory.FetchLibrary["CMOSB"], "and2"].val];
ctcoll^.top^.val ← NARROW[CoreProperties.GetCellTypeProp[ctcoll^.top^.cell, $CellArea], REF INT]^;
AddInputToCover["X ← ~(I-A + I-B)", ctcoll];
ctcoll^.top^.cell ← NARROW[SymTab.Fetch[CoreDirectory.FetchLibrary["CMOSB"], "nor2"].val];
ctcoll^.top^.val ← NARROW[CoreProperties.GetCellTypeProp[ctcoll^.top^.cell, $CellArea], REF INT]^;
AddInputToCover["X ← I-A + I-B", ctcoll];
ctcoll^.top^.cell ← NARROW[SymTab.Fetch[CoreDirectory.FetchLibrary["CMOSB"], "or2"].val];
ctcoll^.top^.val ← NARROW[CoreProperties.GetCellTypeProp[ctcoll^.top^.cell, $CellArea], REF INT]^;
3 inputs (some missing)
AddInputToCover["X ← ~(I-A * I-B * I-C)", ctcoll];
ctcoll^.top^.cell ← NARROW[SymTab.Fetch[CoreDirectory.FetchLibrary["CMOSB"], "nand3"].val];
ctcoll^.top^.val ← NARROW[CoreProperties.GetCellTypeProp[ctcoll^.top^.cell, $CellArea], REF INT]^;
AddInputToCover["X ← (I-A * I-B * I-C)", ctcoll];
ctcoll^.top^.cell ← NARROW[SymTab.Fetch[CoreDirectory.FetchLibrary["CMOSB"], "and3"].val];
ctcoll^.top^.val ← NARROW[CoreProperties.GetCellTypeProp[ctcoll^.top^.cell, $CellArea], REF INT]^;
AddInputToCover["X ← ~(I-A + I-B + I-C)", ctcoll];
ctcoll^.top^.cell ← NARROW[SymTab.Fetch[CoreDirectory.FetchLibrary["CMOSB"], "nor3"].val];
ctcoll^.top^.val ← NARROW[CoreProperties.GetCellTypeProp[ctcoll^.top^.cell, $CellArea], REF INT]^;
AddInputToCover["X ← (I-A + I-B + I-C)", ctcoll];
ctcoll^.top^.cell ← NARROW[SymTab.Fetch[CoreDirectory.FetchLibrary["CMOSB"], "or3"].val];
ctcoll^.top^.val ← NARROW[CoreProperties.GetCellTypeProp[ctcoll^.top^.cell, $CellArea], REF INT]^;
4 inputs (many missing)
AddInputToCover["X ← ~(I-A * I-B * I-C * I-D)", ctcoll];
ctcoll^.top^.cell ← NARROW[SymTab.Fetch[CoreDirectory.FetchLibrary["CMOSB"], "nand4"].val];
ctcoll^.top^.val ← NARROW[CoreProperties.GetCellTypeProp[ctcoll^.top^.cell, $CellArea], REF INT]^;
AddInputToCover["X ← ~(I-A + I-B + I-C + I-D)", ctcoll];
ctcoll^.top^.cell ← NARROW[SymTab.Fetch[CoreDirectory.FetchLibrary["CMOSB"], "nor4"].val];
ctcoll^.top^.val ← NARROW[CoreProperties.GetCellTypeProp[ctcoll^.top^.cell, $CellArea], REF INT]^;
xors
AddInputToCover["X ← (I-A * I-B + ~I-A * ~I-B)", ctcoll];
ctcoll^.top^.cell ← NARROW[SymTab.Fetch[CoreDirectory.FetchLibrary["CMOSB"], "xor2"].val];
ctcoll^.top^.val ← NARROW[CoreProperties.GetCellTypeProp[ctcoll^.top^.cell, $CellArea], REF INT]^;
};
InputOKp: PROC [be1: ROPE, out: IO.STREAM] RETURNS [test: BOOL] ~ {
Verifies that be1 is a legitimate boolean expression--
len: INT ← Rope.Length[be1];
asspos: INT ← Rope.Find[be1, "←", 0];
be : ROPE ← Rope.Substr[be1, asspos + 1, len - asspos - 1];
IF NOT ParensMatch[be]
THEN {IO.PutF[out, "Parens not OK\n"]; RETURN[FALSE]}
ELSE {IO.PutF[out, "Parens OK\n"]; IF AndOrOK[be]
THEN {IO.PutF[out, "Chars OK"]; RETURN[TRUE]}
ELSE {IO.PutF[out, "Chars not OK"]; RETURN[FALSE]}}
};
ParensMatch: PROC [be: ROPE] RETURNS [test: BOOL] ~ {
Verifies that the parenthesis in be match
count: INT ← 0;
len: INT ← Rope.Length[be];
FOR pos: INT ← Rope.SkipTo[be, 0, "()"], Rope.SkipTo[be,pos+1,"()"] DO
IF pos = len
THEN RETURN[count = 0]
ELSE IF Rope.Fetch[be,pos] = '(
THEN count ← count + 1
ELSE {
count ← count - 1;
IF count = -1 THEN RETURN[FALSE]};
ENDLOOP;
};
AndOrOK: PROC [be: ROPE] RETURNS [test: BOOL] ~ {
Verifies that the operators within be are OK.
len: INT ← Rope.Length[be];
FOR pos: INT ← Rope.SkipTo[be, 0, "*+~"], Rope.SkipTo[be, pos+1, "*+~"] DO
I think this section verifies that ands and ors are OK
IF pos = len
THEN EXIT
ELSE
IF Rope.Fetch[be,pos] # '~
THEN {
jobbg : INT ← Rope.SkipOver[be, pos+1, "*+ )"];
IF jobbg = len
THEN RETURN[FALSE]
ELSE IF Rope.SkipTo[be, pos+1, "*+)"] < jobbg THEN RETURN[FALSE];
FOR iter: INT ← pos - 1, iter - 1 DO
IF iter = -1
THEN RETURN[FALSE]
ELSE SELECT Rope.Fetch[be,iter] FROM
'*,'+,'(,'~ => RETURN[FALSE];
' => NULL;
ENDCASE => EXIT;
ENDLOOP}
ELSE {
jobbg : INT ← Rope.SkipOver[be, pos+1, "*+ )"];
IF jobbg = len
THEN RETURN[FALSE]
ELSE IF Rope.SkipTo[be, pos+1, "*+)"] < jobbg THEN RETURN[FALSE]}
ENDLOOP;
FOR pos: INT ← Rope.SkipTo[be, 0, "()"], Rope.SkipTo[be, pos+1, "()"] DO
I think this section verifies that the parenthesis aren't doing anything funny.
IF pos = len
THEN RETURN[TRUE]
ELSE IF Rope.Fetch[be,pos] = '(
THEN {
jobbg: INT ← Rope.SkipTo[be, pos+1, ")"];
IF Rope.SkipOver[be,pos+1,") "] > jobbg THEN RETURN[FALSE];
FOR iter: INT ← pos - 1, iter - 1 DO
IF iter = -1
THEN EXIT
ELSE SELECT Rope.Fetch[be,iter] FROM
'*,'+,'~,'( => EXIT;
' => NULL;
ENDCASE => RETURN[FALSE];
ENDLOOP}
ELSE {
jobbb: INT ← Rope.SkipOver[be, pos+1, "+* )"];
jobbg : INT ← Rope.SkipTo[be, pos+1, "*+)"];
IF jobbb < jobbg THEN RETURN[FALSE]};
ENDLOOP;
};
Commander.Register[key: "Gen", proc: MakeGenerator, doc: "Standard cells from logic equations"];
Debugging Procedures
MakeGenerator: Commander.CommandProc = TRUSTED {Process.Detach[FORK Gen]};
Gen: PUBLIC PROC ~ {
tree: Dag ← MakeNewBoolTree[];
ctcoll: Treeset ← MakeNewCTreeSet[];
gettinginput : BOOL ← TRUE;
in, out: IO.STREAM;
be: ROPE;
dummy : INT ← 0;
[] ← MakeNewNodeB[tree, NIL, prim, "Gnd"];
[] ← MakeNewNodeB[tree, NIL, prim,"Vdd"];
[in: in, out: out] ← ViewerIO.CreateViewerStreams["Logic Generator"];
AssembleCTree[ctcoll];
IO.PutF[out, "Enter Boolean expressions, <CR> to terminate sequence\n"];
WHILE gettinginput DO
IO.PutF[out, "> "];
ViewerTools.SetSelection[ViewerIO.GetViewerFromStream[in]];
be ← IO.GetLineRope[in];
IF Rope.IsEmpty[be]
THEN EXIT
ELSE IF Rope.Fetch[be,0] = ':
THEN {
be ← Rope.Substr[be,1,Rope.Length[be] - 1];
IF InputOKp[be, out]
THEN AddInputToCover[be,ctcoll]
ELSE IO.PutF[out, " Problem with cover expression. Please enter anew.\n"]}
ELSE IF InputOKp[be,out]
THEN AugmentBoolTreeBySingleExpression[tree, be]
ELSE IO.PutF[out, " Problem with input expression. Please enter anew.\n"];
dummy ← dummy + 1;
ENDLOOP;
FromLogicToCell[tree, ctcoll, out];
dummy ← dummy + 1;
};
FromLogicToCell: PROC [tree: Dag, ctcoll: Treeset, out: IO.STREAM] ~ {
foo: Core.CellType;
FOR ctiter: Dag ← ctcoll^.top, ctiter^.next UNTIL ctiter = NIL DO
RemoveOrs[ctiter];
ENDLOOP;
IO.PutF[out, "Done with first pass\n"];
TwoifyAllTrees[ctcoll];
IO.PutF[out, "Done with second pass\n"];
SimplifyDag[tree];
IO.PutF[out, "Done with third pass\n"];
EstablishLevels[tree];
IO.PutF[out, "Done with fourth pass\n"];
TwoifyTree[tree];
IO.PutF[out, "Done with fifth pass\n"];
ReduceFanout[tree, 4];
IO.PutF[out, "Done with sixth pass\n"];
RemoveOrs[tree];
IO.PutF[out, "Done with seventh pass\n"];
WHILE RemoveAllIdenticalLinks[tree] OR RemoveDuplicateNodes[tree] DO ENDLOOP;
IO.PutF[out, "Done with pass seven and a half\n"];
BufferNecessaryNodes[tree];
ReduceFanout[tree, 4];
KillHangingNodes[tree, FALSE];
IO.PutF[out, "Done with pass seven and three quarters\n"];
ProduceTotalCovering[tree, ctcoll];
IO.PutF[out, "Done with eighth pass\n"];
foo ← FromDagToCellType[tree];
IO.PutF[out, "Done\n"];
};
Disp: PUBLIC PROC [tree: Dag, out: IO.STREAM] ~ {
Given a tree, this will display it on stream out --
iter: Node ← tree^.csucs;
WHILE iter # NIL DO
kiter: Kidptr ← iter^.kidlist;
piter: Kidptr ← iter^.parlist;
IO.PutF[out, "\n%3g: ", IO.int[iter^.number]];
SELECT iter^.type FROM
and => IO.PutF[out," and"];
nand => IO.PutF[out,"nand"];
or => IO.PutF[out," or"];
nor => IO.PutF[out," nor"];
not => IO.PutF[out," not"];
buf => IO.PutF[out," buf"];
ENDCASE => IO.PutF[out,"prim"];
IO.PutF[out, Rope.Concat[" ",Rope.Concat[iter^.inname, Rope.Concat[" ", iter^.varname]]]];
IF iter^.output THEN IO.PutF[out, Rope.Concat["*^*",iter^.outname.first]];
IF iter^.sim THEN IO.PutF[out," Sim "];
IO.PutF[out, " %3g\n", IO.int[iter^.level]];
IO.PutF[out, " Kids: "];
WHILE kiter # NIL DO
IO.PutF[out, "%3g", IO.int[kiter^.child^.number]];
IF kiter^.next # NIL
THEN IO.PutF[out, ","]
ELSE IO.PutF[out, "\n"];
kiter ← kiter^.next;
ENDLOOP;
IO.PutF[out, " Pars: "];
WHILE piter # NIL DO
IO.PutF[out, "%3g", IO.int[piter^.child^.number]];
IF piter^.next # NIL
THEN IO.PutF[out, ","];
piter ← piter^.next;
ENDLOOP;
iter ← iter^.next;
ENDLOOP;
IO.PutF[out,"\n"]
};
Massaging Procedures
SimplifyDag: PROC [tree: Dag] ~ {
iter : Node;
firstPass : BOOL ← TRUE;
WHILE firstPass OR AbsorbIdenticalNodes[tree] DO
WHILE RemoveAllIdenticalLinks[tree] OR RemoveDuplicateNodes[tree] OR ProcessGndAndVdd[tree] OR ReduceExpressions[tree] DO ENDLOOP;
firstPass ← FALSE;
ENDLOOP;
This section here should just be a single routine. Chalk another one up to laziness and lack of time.
OrderNodesByPrims[tree];
iter ← tree^.csucs^.prev;
WHILE iter # tree^.csucs DO
temp : Node ← iter^.next;
RAdjustVertex[tree, iter];
IF temp = NIL
THEN IF iter = tree^.csucs^.prev
THEN iter ← iter^.prev
ELSE iter ← tree^.csucs^.prev
ELSE IF temp^.prev = iter
THEN iter ← iter^.prev
ELSE iter ← temp^.prev;
ENDLOOP;
RAdjustVertex[tree, iter];
};
AbsorbIdenticalNodes: PROC [tree: Dag] RETURNS[modified: BOOL ← FALSE] ~ {
This absorbs certain nodes into others in an attempt to make the Dag smaller.
OrderNodesByOrphans[tree];
FOR iter: Node ← tree^.csucs, iter^.next UNTIL iter = NIL DO
subtype : Vtype;
IF iter^.type = and OR iter^.type = nand THEN subtype ← and
ELSE IF iter^.type = or OR iter^.type = nor THEN subtype ← or
ELSE subtype ← iter^.type;
What do we do for not and buf?
FOR kiditer: Kidptr ← iter^.kidlist, kiditer^.next UNTIL kiditer = NIL DO
IF (kiditer^.child^.type = subtype OR iter^.type = not OR iter^.type = buf) AND kiditer^.child^.parnum = 1 AND NOT kiditer^.child^.output THEN {
FOR grandchilditer: Kidptr ← kiditer^.child^.kidlist, grandchilditer^.next UNTIL grandchilditer = NIL DO
MakeLinkE[iter, grandchilditer^.child];
ENDLOOP;
IF iter^.type = not
THEN iter^.type ← NegNodeType[kiditer^.child^.type]
ELSE IF iter^.type = buf THEN iter^.type ← kiditer^.child^.type;
RemoveNode[tree, kiditer^.child];
modified ← TRUE};
ENDLOOP;
ENDLOOP;
};
RemoveDuplicateNodes: PUBLIC PROC [tree: Dag] RETURNS[modified: BOOL ← FALSE] ~ {
This will get rid of any nodes with the same subset of children from the tree --
this should be rewritten with IntersectionSize instead of the way it is currently being done. Remember, though, IntersectionSize modifies the scratch field.
PrimitivesToEnd[tree];
IF tree^.csucs^.type # prim THEN {
front: Node ← tree^.csucs^.prev;
rear : Node ← front;
ClearScratch[tree];
WHILE front^.type = prim DO
front ← front^.prev;
ENDLOOP;
WHILE front # NIL DO
szuloiter : Kidptr ← rear^.parlist;
middle: Node ← front^.next;
WHILE szuloiter # NIL DO
KidptrToEnd[szuloiter^.parlink, szuloiter^.child];
IF szuloiter^.child^.scratch = szuloiter^.child^.kidnum - 1
THEN {
nodeiter: Node ← middle^.prev;
WHILE nodeiter # front DO
IF nodeiter^.type = szuloiter^.child^.type AND ForwardSimilar[nodeiter, szuloiter^.child]
THEN {
MergeNodes[nodeiter, szuloiter^.child, tree];
modified ← TRUE;
EXIT}
ELSE nodeiter ← nodeiter^.prev;
ENDLOOP;
front ← PlaceAfter[tree, front, szuloiter^.child]}
ELSE szuloiter^.child^.scratch ← szuloiter^.child^.scratch + 1;
szuloiter ← szuloiter^.next;
ENDLOOP;
rear ← rear^.prev;
ENDLOOP}
};
MergeNodes: PROC [bol, be: Node, tree: Dag] ~ {
If bol and be both have the same children (and type) then this causes bol to be merged into be--
be^.output ← be^.output OR bol^.output;
be^.outname ← MergeListOfRopes[bol^.outname, be^.outname];
be^.inname ← Rope.Concat[be^.inname, bol^.inname];
be^.varname ← Rope.Concat[be^.varname, bol^.varname];
FOR iter: Kidptr ← bol^.parlist, iter^.next UNTIL iter = NIL DO
MakeLink[iter^.child, be];
ENDLOOP;
RemoveNode[tree, bol]
};
RemoveAllIdenticalLinks: PROC [tree: Dag] RETURNS [modified: BOOL ← FALSE] ~ {
FOR iter: Node ← tree^.csucs, iter^.next UNTIL iter = NIL DO
modified ← modified OR RemoveIdenticalLinks[iter]
ENDLOOP;
};
RemoveIdenticalLinks: PROC [vertex: Node] RETURNS[modified: BOOL ← FALSE] ~ {
FOR kiditer: Kidptr ← vertex^.kidlist, kiditer^.next UNTIL kiditer = NIL DO
kiditer^.child^.scratch ← 0;
ENDLOOP;
FOR kiditer: Kidptr ← vertex^.kidlist, kiditer^.next UNTIL kiditer = NIL DO
IF kiditer^.child^.scratch = 1
THEN {
[] ← KillCLink[kiditer];
modified ← TRUE}
ELSE kiditer^.child^.scratch ← 1;
ENDLOOP;
FOR pariter: Kidptr ← vertex^.parlist, pariter^.next UNTIL pariter = NIL DO
pariter^.child^.scratch ← 0;
ENDLOOP;
FOR pariter: Kidptr ← vertex^.parlist, pariter^.next UNTIL pariter = NIL DO
IF pariter^.child^.scratch = 1
THEN {
[] ← KillPLink[pariter];
modified ← TRUE}
ELSE pariter^.child^.scratch ← 1;
ENDLOOP;
};
ProcessGndAndVdd: PROC [tree: Dag] RETURNS[modified: BOOL ← FALSE] ~ {
This will disconnect Gnd and Vdd from all other signals, simplifying as it goes along.
gnd: Node ← FindInputByName[tree, "Gnd"];
vdd: Node ← FindInputByName[tree, "Vdd"];
IF gnd # NIL OR vdd # NIL THEN {
IF gnd = NIL THEN [] ← MakeNewNodeB[tree, NIL, prim, "Gnd"]
ELSE IF vdd = NIL THEN [] ← MakeNewNodeB[tree, NIL, prim, "Vdd"];
IF gnd^.parlist # NIL OR vdd^.parlist # NIL THEN mdoified ← TRUE;
WHILE gnd^.parlist # NIL OR vdd^.parlist # NIL DO
IF gnd^.parlist # NIL THEN ProcessGnd[gnd, vdd, tree];
IF vdd^.parlist # NIL THEN ProcessVdd[gnd, vdd, tree];
ENDLOOP}
};
ProcessGnd: PROC [gnd, vdd: Node, tree: Dag] ~ {
This will disconnect gnd from all other nodes, simplifying as it goes along, and sometimes hooking things up to vdd.
par : Node ← gnd^.parlist^.child;
SELECT par^.type FROM
or, nor => {
[] ← KillPLink[gnd^.parlist];
RAdjustVertex[tree, par]};
and, buf => {
FOR pariter: Kidptr ← par^.parlist, pariter^.next UNTIL pariter = NIL DO
MakeLinkE[pariter^.child, gnd];
ENDLOOP;
gnd^.output ← gnd^.output OR par^.output;
gnd^.outname ← MergeListOfRopes[gnd^.outname, par^.outname];
RemoveNode[tree, par]};
nand, not => {
FOR pariter: Kidptr ← par^.parlist, pariter^.next UNTIL pariter = NIL DO
MakeLinkE[pariter^.child, vdd];
ENDLOOP;
vdd^.output ← vdd^.output OR par^.output;
vdd^.outname ← MergeListOfRopes[vdd^.outname, par^.outname];
RemoveNode[tree, par]};
ENDCASE => tree^.csucs^.prev^.next^.prev ← NIL; --This will cause an error. Shouldn't be reached.
};
ProcessVdd: PROC [gnd, vdd: Node, tree: Dag] ~ {
par: Node ← vdd^.parlist^.child;
SELECT par^.type FROM
and, nand => {
[] ← KillPLink[gnd^.parlist];
RAdjustVertex[tree, par]};
nor, not => {
FOR pariter: Kidptr ← par^.parlist, pariter^.next UNTIL pariter = NIL DO
MakeLinkE[pariter^.child, gnd];
ENDLOOP;
gnd^.output ← gnd^.output OR par^.output;
gnd^.outname ← MergeListOfRopes[gnd^.outname, par^.outname];
RemoveNode[tree, par]};
or, buf => {
FOR pariter: Kidptr ← par^.parlist, pariter^.next UNTIL pariter = NIL DO
MakeLinkE[pariter^.child, vdd];
ENDLOOP;
vdd^.output ← vdd^.output OR par^.output;
vdd^.outname ← MergeListOfRopes[vdd^.outname, par^.outname];
RemoveNode[tree, par]};
ENDCASE => tree^.csucs^.prev^.next^.prev ← NIL; --This will cause an error. Shouldn't be reached.
};
ReduceExpressions: PROC [tree: Dag] RETURNS[modified: BOOL ← FALSE] ~ {
This is supposed to eliminate several different types of expressions such as a+~a*b, a*b+~a*b, a*~a, a+b*a and simplify them. Also for the case of switching the + with the *. One test which indicates an error somewhere is foo ← a*b+~(a*b)+c. The interesting thing is that bar = a*b, foo ← bar+~bar+c works.
OrderNodesByPrims[tree];
FOR iter: Node ← tree^.csucs^.prev, iter^.prev UNTIL iter = tree^.csucs DO
modified ← modified OR ReduceExpression1[tree, iter];
modified ← modified OR ReduceExpression2[tree, iter];
ENDLOOP;
modified ← modified OR ReduceExpression1[tree, tree^.csucs];
modified ← modified OR ReduceExpression2[tree, tree^.csucs];
};
ReduceExpression1: PROC [tree: Dag, vertex: Node] RETURNS[modified: BOOL ← FALSE] ~ {
This one is supposed to take care of the cases a+~a*b and a*~a and the same with + and * switched.
subtype: Vtype ← and;
IF vertex^.kidnum > 1 THEN {
iter1: Kidptr ← vertex^.kidlist;
IF vertex^.type = and OR vertex^.type = nand THEN subtype ← or;
WHILE iter1 # NIL DO
pair : Node ← NegativeOf[iter1^.child];
IF pair = NIL
THEN iter1 ← iter1^.next
ELSE {
iter2: Kidptr ← vertex^.kidlist;
IF ConnectionBetween[vertex, pair] # NIL
THEN { This is the a*~a clause
IF subtype = or
THEN [] ← MakeLink[vertex, FindInputByName[tree, "Gnd"]]
ELSE [] ← MakeLink[vertex, FindInputByName[tree, "Vdd"]];
I would slightly redo this section to just remove the two conflicting nodes, make the hookup to gnd or vdd and let the other routine take care of fixing it up on its own. It's a few more lines code, but conceptually nicer and easier to understand.
[] ← ProcessGndAndVdd[tree];
RETURN[TRUE]};
WHILE iter2 # NIL DO
IF iter2^.child^.type # subtype OR iter2 = iter1 OR ConnectionBetween[iter2^.child, pair] = NIL
This was the a+~a*b check
THEN iter2 ← iter2^.next
ELSE IF iter2^.child^.kidnum = 2
THEN {
IF iter2^.child^.kidlist^.child = pair
THEN [] ← MakeLinkE[vertex, iter2^.child^.kidlist^.next^.child]
ELSE [] ← MakeLinkE[vertex, iter2^.child^.kidlist^.child];
iter2 ← iter2^.next;
modified ← TRUE;
IF iter2^.prev^.child^.parnum = 1
THEN RemoveNode[tree, iter2^.prev^.child]
ELSE [] ← KillCLink[iter2^.prev]}
ELSE IF iter2^.child^.parnum = 1
THEN {
temp: Kidptr ← iter2^.next;
[] ← KillCLink[ConnectionBetween[iter2^.child, pair]];
[] ← PlaceKidptrAfter[iter1, iter2, vertex];
modified ← TRUE;
iter2 ← temp}
ELSE iter2 ← iter2^.next;
Maybe you will want to add something here, but it could make the tree bigger than before
ENDLOOP;
iter1 ← iter1^.next};
ENDLOOP}
};
ReduceExpression2: PROC [tree: Dag, vertex: Node] RETURNS[modified: BOOL ← FALSE] ~ {
This takes care of the a*b+~a*b case a*b+a*b*c case and the following: bar = a*b, foo ← bar + bar*c which is really the previous case arranged in a different way. Note the use of IntersectionSize.
subtype : Vtype ← and;
IF vertex^.kidnum > 1 THEN {
front: Kidptr;
OrderKidptrsBySize[vertex];
front ← vertex^.kidlist;
IF vertex^.type = and OR vertex^.type = nand THEN subtype ← or;
WHILE front # NIL DO
nextfront: Kidptr ← front^.next;
IF front^.child^.type = subtype THEN {
rear: Kidptr ← front^.next;
WHILE rear # NIL DO
IF rear^.child^.type # subtype
THEN rear ← rear^.next
ELSE {
conFromFrontToRear: Kidptr ← ConnectionBetween[front^.child, rear^.child];
conFromRearToFront: Kidptr ← ConnectionBetween[rear^.child, front^.child];
for the third case
IF conFromRearToFront # NIL
THEN IF rear^.child^.parnum = 1
THEN
{rear ← rear^.next;
modified ← TRUE;
IF rear = NIL
THEN RemoveNode[tree, vertex^.kidlist^.prev^.child]
ELSE RemoveNode[tree, rear^.prev^.child]}
ELSE rear ← KillCLink[rear]
ELSE IF conFromFrontToRear # NIL
THEN {
nextfront ← front^.next;
IF front^.child^.parnum = 1
THEN RemoveNode[tree, front^.child]
ELSE [] ← KillCLink[front];
modified ← TRUE;
rear ← NIL}
ELSE IF rear^.child^.kidnum # front^.child^.kidnum
THEN IF IntersectionSize[front^.child, rear^.child] = rear^.child^.kidnum
This is legitimate because the kidptrs have been ordered.
THEN { --second case
nextfront ← front^.next;
IF front^.child^.parnum = 1
THEN RemoveNode[tree, front^.child]
ELSE [] ← KillCLink[front];
modified ← TRUE;
rear ← NIL}
ELSE rear ← rear^.next
ELSE { --third case
temp: Kidptr;
exp, negexp: Kidptr;
[son1 : exp, son2: negexp] ← CheckTheseTwo[front^.child, rear^.child];
IF exp = NIL
THEN rear ← rear^.next
ELSE {
IF rear^.child^.parnum = 1
THEN {
temp ← rear;
[] ← KillCLink[negexp];
Percolate[temp, vertex];
nextfront ← KillCLink[front];
modified ← TRUE;
IF exp^.parlink^.child^.parnum = 0 AND NOT exp^.parlink^.child^.output THEN RemoveNode[tree, exp^.parlink^.child]}
ELSE IF front^.child^.parnum = 1
THEN {
temp ← front;
[] ← KillCLink[exp];
[] ← KillCLink[rear];
modified ← TRUE;
nextfront ← front^.next;
Percolate[temp, vertex]}
ELSE {
MakeLink[vertex, MakeNewNodeA[tree, vertex, subtype]];
Uses the fact that MakeLink places the new link at the beginning
Also, this makes the tree bigger so I don't set modified
temp ← vertex^.next^.parlist^.parlink;
FOR iter: Kidptr ← front^.child^.kidlist, iter^.next UNTIL iter = NIL DO
IF iter # exp THEN MakeLink[temp^.child, iter^.child];
ENDLOOP;
Percolate[temp, vertex];
[] ← KillCLink[rear];
nextfront ← KillCLink[front]};
rear ← NIL}}}
ENDLOOP};
front ← nextfront;
ENDLOOP};
};
CheckTheseTwo: PROC [sib1, sib2: Node] RETURNS [son1: Kidptr ← NIL, son2: Kidptr ← NIL] ~ {
This is a genuinely dumb way to do this. Should be redone with IntersectionSize. What it does is check to see if sib1 and sib2 are of the form z*(x1*x2*...) and ~z*(x1*x2*...) where * is the the respective types of the two nodes.
FOR iter: Kidptr ← sib1^.kidlist, iter^.next UNTIL iter = NIL DO
pair: Node ← NegativeOf[iter^.child];
IF pair # NIL THEN {
dummy: BOOL ← TRUE;
sonlink: Kidptr ← ConnectionBetween[sib2, pair];
IF sonlink # NIL THEN {
Here we assume the two siblings are of equal size
FOR iter1: Kidptr ← sib1^.kidlist, iter1^.next UNTIL iter1 = NIL DO
iter1^.child^.scratch ← 0;
ENDLOOP;
FOR iter2: Kidptr ← sib2^.kidlist, iter2^.next UNTIL iter2 = NIL DO
iter2^.child^.scratch ← 1;
ENDLOOP;
FOR iter1: Kidptr ← sib1^.kidlist, iter1^.next UNTIL iter1 = NIL DO
IF iter1^.child^.scratch # 1 AND iter1^.child # iter^.child THEN dummy ← FALSE;
ENDLOOP;
IF dummy THEN {
son1 ← iter;
son2 ← sonlink;
RETURN}}}
ENDLOOP;
};
OrderKidptrsBySize: PROC [vertex: Node] ~ {
iter: Kidptr ← vertex^.kidlist;
temp: Kidptr;
IF iter # NIL
THEN iter ← iter^.prev
ELSE RETURN;
WHILE iter # vertex^.kidlist DO
temp ← iter^.prev;
Percolate[iter, vertex];
iter ← temp;
ENDLOOP;
Percolate[iter, vertex]
};
Percolate: PROC [kid: Kidptr, vertex: Node] ~ {
IF kid^.next # NIL AND kid^.next^.child^.kidnum > kid^.child^.kidnum THEN {
FOR iter: Kidptr ← kid^.next, iter^.next UNTIL iter = NIL DO
IF kid^.child^.kidnum > iter^.child^.kidnum THEN {
[] ← PlaceKidptrAfter[iter^.prev, kid, vertex];
RETURN}
ENDLOOP;
[] ← PlaceKidptrAfter[vertex^.kidlist^.prev, kid, vertex]}
};
PlaceKidptrAfter: PROC [before, after: Kidptr, tree: Node] RETURNS[Kidptr] ~ {
before stays fixed here. This procedure takes before and after in tree and causes after to be placed after before in linear order. If before = NIL then PlaceKidptrAtBeg[after,tree] is invoked. Will fail if after = NIL. Returns after^.prev (or NIL if after = tree^.kidlist). --
IF before = NIL
THEN PlaceKidptrAtBeg[after, tree]
ELSE IF before # after AND (before^.next # after) THEN
IF before^.next = NIL
THEN {
before^.next ← after;
IF after = tree^.kidlist
THEN {
tree^.kidlist ← after^.next;
after^.next ← NIL}
ELSE {
after^.prev^.next ← after^.next;
after^.next^.prev ← after^.prev;
tree^.kidlist^.prev ← after;
after^.next ← NIL;
after^.prev ← before}}
ELSE {
IF after^.next = NIL
THEN tree^.kidlist^.prev ← after^.prev
ELSE after^.next^.prev ← after^.prev;
IF after = tree^.kidlist
THEN tree^.kidlist ← after^.next
ELSE after^.prev^.next ← after^.next;
after^.prev ← before;
after^.next ← before^.next;
before^.next^.prev ← after;
before^.next ← after};
IF after = tree^.kidlist
THEN RETURN[NIL]
ELSE RETURN[after^.prev];
};
PlaceKidptrAtBeg: PROC [vertex: Kidptr, tree: Node] ~ {
This takes vertex in tree and causes it to be the first in linear order in the tree --
IF vertex # tree^.kidlist THEN {
IF vertex^.next = NIL
THEN {
vertex^.prev^.next ← NIL
}
ELSE {
vertex^.prev^.next ← vertex^.next;
vertex^.next^.prev ← vertex^.prev;
vertex^.prev ← tree^.kidlist^.prev;
tree^.kidlist^.prev ← vertex
};
vertex^.next ← tree^.kidlist;
tree^.kidlist ← vertex}
};
RAdjustVertex: PROC [tree: Dag, vertex: Node] ~ {
This cleans up dangling nodes from the bottom up.
IF vertex^.type # prim THEN
IF vertex^.kidnum = 0
THEN {
IF vertex^.output THEN vertex^.kidlist^.next ← NIL;--Error. There is a floating output
FOR iter: Kidptr ← vertex^.parlist, iter^.next UNTIL iter = NIL DO
par : Node ← iter^.child;
[] ← KillPLink[iter];
RAdjustVertex[tree, par];
ENDLOOP}
ELSE IF vertex^.kidnum = 1 THEN SELECT vertex^.type FROM
nand, nor => vertex^.type ← not;
and, or => {
son: Node ← vertex^.kidlist^.child;
son^.output ← son^.output OR vertex^.output;
son^.outname ← MergeListOfRopes[son^.outname, vertex^.outname];
FOR pariter: Kidptr ← vertex^.parlist, pariter^.next UNTIL pariter = NIL DO
MakeLink[pariter^.child, son];
ENDLOOP;
RemoveNode[tree, vertex]};
ENDCASE => NULL;
};
ReduceFanout: PUBLIC PROC [tree: Dag, fout: INT] ~ {
This splits nodes in tree where the fanout is greater than fout
OrderNodesByOrphans[tree];
ClearScratch[tree];
FOR front: Node ← tree^.csucs, front^.next UNTIL front = NIL DO
IF front^.type # prim THEN
WHILE front^.parnum > fout DO
[] ← MakeNewNodeB[tree, front, front^.type];
FOR kiditer: Kidptr ← front^.kidlist, kiditer^.next UNTIL kiditer = NIL DO
MakeLink[front^.prev, kiditer^.child];
ENDLOOP;
IF fout < 2*front^.parnum
THEN FOR i: INT IN [1..front^.parnum/2] DO
MakeLink[front^.parlist^.child,front^.prev];
[] ← KillPLink[front^.parlist];
ENDLOOP
ELSE FOR i: INT IN [1..fout] DO
MakeLink[front^.parlist^.child,front^.prev];
[] ← KillPLink[front^.parlist];
ENDLOOP;
ENDLOOP;
ENDLOOP
};
BufferNecessaryNodes: PROC [tree: Dag] ~ {
Any node which is both a prim and and output (other than Vdd and Gnd this should only happen in unaccessed signals) will be buffered, and so are multiple outputs with different names.
OrderNodesByOrphans[tree];
FOR iter: Node ← tree^.csucs, iter^.next UNTIL iter = NIL DO
IF iter^.type = prim
THEN IF iter^.output
THEN {
IF Member[iter^.inname, iter^.outname]
THEN iter^.outname ← RemoveNameFromList[iter^.inname, iter^.outname]
ELSE iter^.output ← FALSE;
SELECT iter^.inname FROM
"Gnd" => IF iter^.outname # NIL THEN {
vdd: Node ← FindInputByName[tree, "Vdd"];
WHILE iter^.outname # NIL DO
MakeLink[MakeNewNodeB[tree, iter, not, NIL, NIL, LIST[iter^.outname.first], TRUE], vdd];
iter^.outname ← iter^.outname.rest;
ENDLOOP;
"Vdd" => IF iter^.outname # NIL THEN {
gnd: Node ← FindInputByName[tree, "Gnd"];
WHILE iter^.outname # NIL DO
MakeLink[MakeNewNodeB[tree, iter, not, NIL, NIL, LIST[iter^.outname.first], TRUE], gnd];
iter^.outname ← iter^.outname.rest;
ENDLOOP;
ENDCASE =>
IF iter^.outname # NIL THEN {
notAbove: Node ← NotAbove[iter^.parlist];
IF notAbove = NIL THEN {
notAbove ← MakeNewNodeB[tree, iter, not];
MakeLink[notAbove, iter]};
WHILE iter^.outname # NIL DO
MakeLink[MakeNewNodeB[tree, notAbove, not], notAbove];
notAbove^.prev^.output ← TRUE;
notAbove^.prev^.outname ← LIST[iter^.outname.first];
iter^.outname ← iter^.outname.rest;
ENDLOOP};
IF iter^.output THEN iter^.outname ← LIST[iter^.inname];}
Why is this last thing being done? I think it's because of something I do in outputting the generated cell type, but this may be obsolete by now.
ELSE NULL
ELSE IF iter^.output THEN
IF iter^.outname # NIL AND iter^.outname.rest # NIL THEN {
notAbove: Node ← NotAbove[iter^.parlist];
IF notAbove = NIL THEN {
notAbove ← MakeNewNodeB[tree, iter, not];
MakeLink[notAbove, iter]};
WHILE iter^.outname.rest # NIL DO
MakeLink[MakeNewNodeB[tree, notAbove, not], notAbove];
notAbove^.prev^.output ← TRUE;
notAbove^.prev^.outname ← LIST[iter^.outname.first];
iter^.outname ← iter^.outname.rest;
ENDLOOP};
ENDLOOP;
};
RemoveNameFromList: PROC [name: ROPE, list: LIST OF ROPE] RETURNS [LIST OF ROPE] ~ {
Eliminates name from list, if it is there
IF list = NIL THEN RETURN[NIL]
ELSE IF Rope.Equal[list.first,name] THEN RETURN[RemoveNameFromList[name, list.rest]]
ELSE RETURN[CONS[list.first, RemoveNameFromList[name, list.rest]]]
};
Member: PROC [element: ROPE, list: LIST OF ROPE] RETURNS [BOOL] ~ {
Determines whether element is part of list
IF list = NIL THEN RETURN[FALSE]
ELSE IF Rope.Equal[element,list.first] THEN RETURN[TRUE]
ELSE RETURN[Member[element, list.rest]]
};
RemoveOrs: PROC [tree: Dag] ~ {
This eliminates all ors, nors, and ands from the tree, converting everything into nands and nots, leaving the prims alone --
OrderNodesByOrphans[tree];
FOR front: Node ← tree^.csucs, front^.next UNTIL front = NIL DO
notAbove : Node;
IF front^.type = or OR front^.type = nor THEN {
FOR kiditer: Kidptr ← front^.kidlist, kiditer^.next UNTIL kiditer = NIL DO
NegateConnection[tree, kiditer];
ENDLOOP;
IF front^.type = or
THEN front^.type ← nand
ELSE front^.type ← and};
IF front^.type = and THEN {
notAbove ← NotAbove[front^.parlist];
IF notAbove = NIL
THEN {
Splitnode[tree, front];
front^.type ← nand;
front^.prev^.type ← not}
ELSE IF front^.parnum =1 AND NOT front^.output
THEN {
FOR iter: Kidptr ← notAbove^.parlist, iter^.next UNTIL iter = NIL DO
MakeLink[iter^.child, front];
ENDLOOP;
front^.output ← notAbove^.output;
front^.varname ← notAbove^.varname;
front^.inname ← notAbove^.inname;
front^.outname ← notAbove^.outname;
RemoveNode[tree, notAbove];
front^.type ← nand}
ELSE SwitchWithNot[notAbove]};
IF front^.type = not THEN {
notAbove ← NotAbove[front^.parlist];
IF notAbove # NIL THEN {
FOR pariter: Kidptr ← notAbove^.parlist, pariter^.next UNTIL pariter = NIL DO
MakeLink[pariter^.child, front^.kidlist^.child];
ENDLOOP;
front^.kidlist^.child^.output ← front^.kidlist^.child^.output OR notAbove^.output;
front^.kidlist^.child^.inname ← Rope.Concat[front^.kidlist^.child^.inname, notAbove^.inname];
front^.kidlist^.child^.outname ← MergeListOfRopes[notAbove^.outname, front^.kidlist^.child^.outname];
RemoveNode[tree, notAbove]}};
ENDLOOP;
};
Splitnode: PROC [tree: Dag, vertex: Node, type: Vtype ← not] ~ {
This takes a vertex and makes two in its place, the original's children being the bottom's children and the original's parents being the top's parents. The top node gets type type (defaulted to not).
temp: Node ← NEW[Noderec ← [next: vertex, prev: vertex^.prev, kidlist: NEW[Kidrec ← [child: vertex]], kidnum: 1, parnum: vertex^.parnum, parlist: vertex^.parlist, type: type, output: vertex^.output, inname: vertex^.inname, outname: vertex^.outname, number: tree^.size + 1]];
pariter: Kidptr;
vertex^.parlist ← NEW[Kidrec ← [child: temp, parlink: temp^.kidlist]];
vertex^.parnum ← 1;
vertex^.output ← FALSE;
vertex^.outname ← NIL;
vertex^.inname ← NIL;
vertex^.varname ← NIL;
vertex^.parlist^.prev ← vertex^.parlist;
temp^.kidlist^.prev ← temp^.kidlist;
temp^.kidlist^.parlink ← vertex^.parlist;
IF vertex = tree^.csucs
THEN tree^.csucs ← temp
ELSE vertex^.prev^.next ← temp;
vertex^.prev ← temp;
pariter ← temp^.parlist;
WHILE pariter # NIL DO
pariter^.parlink^.parlink ← pariter;
pariter^.parlink^.child ← temp;
pariter ← pariter^.next
ENDLOOP;
tree^.size ← tree^.size + 1
};
SwitchWithNot: PROC [vertex: Node] ~ {
This assumes vertex is of type not and switches it with its child
fmarker : Kidptr ← vertex^.parlist;
rmarker : Kidptr ← NIL;
tempname: ROPE;
tempoutname: LIST OF ROPE;
IF fmarker # NIL THEN rmarker ← fmarker^.prev;
FOR piter: Kidptr ← vertex^.kidlist^.child^.parlist, piter^.next UNTIL piter = NIL DO
IF piter^.child # vertex THEN {
MakeLink[piter^.child, vertex];
[] ← KillPLink[piter]};
ENDLOOP;
IF fmarker # NIL THEN {
FOR piter: Kidptr ← fmarker, piter^.next UNTIL piter = rmarker DO
MakeLink[piter^.child, vertex^.kidlist^.child];
[] ← KillPLink[piter];
ENDLOOP;
MakeLink[rmarker^.child, vertex^.kidlist^.child];
[] ← KillPLink[rmarker]};
IF ((NOT vertex^.kidlist^.child^.output) AND vertex^.output) OR (vertex^.kidlist^.child^.output AND NOT vertex^.output) THEN {
vertex^.kidlist^.child^.output ← vertex^.output;
vertex^.output ← NOT vertex^.output};
tempname ← vertex^.inname;
vertex^.inname ← vertex^.kidlist^.child^.inname;
vertex^.kidlist^.child^.inname ← tempname;
tempname ← vertex^.varname;
vertex^.varname ← vertex^.kidlist^.child^.varname;
vertex^.kidlist^.child^.varname ← tempname;
tempoutname ← vertex^.outname;
vertex^.outname ← vertex^.kidlist^.child^.outname;
vertex^.kidlist^.child^.outname ← tempoutname;
vertex^.kidlist^.child^.type ← NegNodeType[vertex^.kidlist^.child^.type];
};
TwoifyTree: PUBLIC PROC [tree: Dag] ~ {
This will yield a tree where each node has fan-in at most 2 --
OrderNodesByOrphans[tree];
FOR iter: Node ← tree^.csucs, iter^.next UNTIL iter = NIL DO
TwoifyGate[iter, tree];
ENDLOOP;
};
TwoifyGate: PROC [vertex: Node, tree: Dag] ~ {
Given vertex with > 2 children, this will remake that node so that there are at most two inputs per gate at that node.--
IF vertex^.kidnum > 2 THEN {
level: INT ← 1;
inleft: INT;
singlep: BOOL ← FALSE;
remaining: INT ← vertex^.kidnum;
nexttype: Vtype ← and;
iter: Kidptr;
right, left: Node;
links: Links ← CreateLinkSet[vertex^.kidlist];
llinks: Links ← CreateLinkSet[NIL];
rlinks: Links ← CreateLinkSet[NIL];
OrderLinksByReq[links];
iter ← links^.top;
WHILE iter # NIL DO
IF iter^.req > 0 THEN {
temp: Kidptr ← iter^.next;
TransferLink[links, iter, llinks];
iter ← temp;
remaining ← remaining - 1;
IF Fullp[llinks] THEN
IF Fullp[rlinks]
THEN ERROR --Cannot satisfy requirements in TwoifyGate at vertex^.number
ELSE {
templs: Links ← llinks;
llinks ← rlinks;
rlinks ← templs}};
iter ← iter^.next;
ENDLOOP;
WHILE SpaceA[llinks, level] + SpaceA[rlinks, level] < remaining DO
level ← level + 1;
ENDLOOP;
inleft ← (remaining * SpaceA[llinks, level])/(SpaceA[llinks, level] + SpaceA[rlinks, level]);
FOR counter: INT IN [1..inleft] DO
TransferLink[links, links^.top, llinks];
ENDLOOP;
WHILE links^.top # NIL DO
TransferLink[links, links^.top, rlinks];
ENDLOOP;
IF inleft # 1 AND rlinks^.top^.next = NIL THEN {
templs: Links ← llinks;
llinks ← rlinks;
rlinks ← templs;
inleft ← 1};
singlep ← (inleft = 1);
IF vertex^.type = nor OR vertex^.type = or THEN nexttype ← or;
right ← MakeNewNodeA[tree, vertex, nexttype, NIL];
vertex^.kidlist ← rlinks^.top;
WHILE vertex^.kidlist # NIL DO
MakeLink[right, vertex^.kidlist^.child];
[] ← KillCLink[vertex^.kidlist];
ENDLOOP;
vertex^.kidlist ← llinks^.top;
IF NOT singlep THEN {
left ← MakeNewNodeA[tree, vertex, nexttype, NIL];
WHILE vertex^.kidlist # NIL DO
MakeLink[left, vertex^.kidlist^.child];
[] ← KillCLink[vertex^.kidlist];
ENDLOOP;
MakeLink[vertex, left]};
MakeLink[vertex, right];
IF NOT singlep THEN TwoifyGate[left, tree];
TwoifyGate[right, tree]}
};
CreateLinkSet: PROC [link: Kidptr] RETURNS [newLinks: Links] ~ {
This makes a ptr to the given link
newLinks ← NEW[Linksrec ← [top: link]];
IF link # NIL THEN newLinks^.size ← link^.parlink^.child^.kidnum
};
OrderLinksByReq: PROC [links: Links] ~ {
This does a bubble sort on the list of Kidptrs on the field req --
front : Kidptr ← links^.top;
WHILE front # NIL DO
iter: Kidptr ← front^.next;
WHILE iter # NIL DO
IF iter^.req > iter^.prev^.req THEN {
SwitchLinksB[iter, links];
IF front^.prev = iter THEN front ← iter;
iter ← iter^.next};
iter ← iter^.next
ENDLOOP;
front ← front^.next;
ENDLOOP
};
SwitchLinksB: PROC [link: Kidptr, links: Links] ~ {
This exchanges link and the Kidptr just before it. Thus, the operation will produce no result if link = links^.top --
IF link # links^.top THEN {
prev: Kidptr ← link^.prev;
IF link^.next = NIL
THEN links^.top^.prev ← prev
ELSE link^.next^.prev ← prev;
link^.next ← prev;
IF prev # links^.top
THEN prev^.prev^.next ← link
ELSE links^.top ← link;
prev^.prev ← link}
};
TransferLink: PROC [ebbol: Links, link: Kidptr, ebbe: Links] ~ {
This takes and moves link from ebbol into ebbe--
IF link^.next = NIL
THEN ebbol^.top^.prev ← link^.prev
ELSE link^.next^.prev ← link^.prev;
IF link = ebbol^.top
THEN ebbol^.top ← link^.next
ELSE link^.prev^.next ← link^.next;
link^.next ← NIL;
IF ebbe^.top = NIL
THEN ebbe^.top ← link
ELSE {
link^.prev ← ebbe^.top^.prev;
ebbe^.top^.prev^.next ← link};
ebbe^.top^.prev ← link;
ebbol^.size ← ebbol^.size - 1;
ebbe^.size ← ebbe^.size + 1;
IF link^.req > 0 THEN link^.req ← link^.req - 1
};
Fullp: PROC [links: Links] RETURNS [valasz: BOOL ← FALSE] ~ {
This yields whether or not a subtree is saturated by links with requirements. It assumes that all links have requirements, and that these are sorted. --
IF links^.top # NIL THEN RETURN[0 # SpaceA[links, links^.top^.prev^.req]]
};
SpaceA: PROC [links: Links, level: INT] RETURNS [free: INT ← 1] ~ {
Assuming that all links in links have a req field > 0 this yields the number of free nodes still left assuming a tree of maximum depth level--
iter: Kidptr ← links^.top;
atlevel: INT ← 0; -- Sort of kludgey, but TransferLink has subtracted one from the req field --
WHILE iter # NIL DO
IF iter^.req > atlevel
THEN IF atlevel = level
THEN RETURN
ELSE {
atlevel ← atlevel + 1;
free ← 2 * free}
ELSE {
free ← free - 1;
IF free = 0 THEN RETURN;
iter ← iter^.next}
ENDLOOP;
WHILE atlevel + 1 # level DO
free ← 2 * free;
atlevel ← atlevel + 1;
ENDLOOP;
RETURN
};
Constructing CellType from processed Dag
CollectWires: PROC [iter: Node] RETURNS [pas: LIST OF CoreCreate.PA ← NIL] ~ {
This makes a list of all the input and one output wires of a true tree headed by iter
IF iter # NIL THEN {
IF iter^.type = prim
THEN pas ← CONS[[iter^.inname, iter^.mate^.wire], CollectWires[iter^.next]]
ELSE IF iter^.output
THEN pas ← CONS[[iter^.outname.first, iter^.mate^.wire], CollectWires[iter^.next]]
ELSE pas ← CollectWires[iter^.next]}
};
WireNameFromNode: PROC [vertex: Node] RETURNS [name: ROPE] ~ {
This takes a node and generates a wire name from it. vertex^.number is used if no other name is found
IF vertex^.output OR vertex^.type = prim
THEN IF vertex^.type = prim
THEN name ← vertex^.inname
ELSE name ← vertex^.outname.first
ELSE IF NOT Rope.IsEmpty[vertex^.inname]
THEN name ← Rope.Concat["intrnal", vertex^.inname]
ELSE IF NOT Rope.IsEmpty[vertex^.varname]
THEN name ← Rope.Concat["intrnal", vertex^.varname]
ELSE name ← Rope.Concat["intrnal",Convert.RopeFromInt[vertex^.number,10,FALSE]];
};
MarkCoveredSubtree: PROC [vertex: Node, cover: Node] ~ {
This will put a 1 in the scratch field of the mate of every input vertex in the tree headed by cover.
IF cover^.type = prim
THEN IF vertex^.scratch # 1
THEN {
vertex^.scratch ← 1;
IF vertex^.type # prim THEN MarkCoveredSubtree[vertex, vertex^.cover^.csucs]}
ELSE NULL
ELSE IF cover^.type = not
THEN MarkCoveredSubtree[vertex^.kidlist^.child, cover^.kidlist^.child]
ELSE {
MarkCoveredSubtree[cover^.kidlist^.child^.mate, cover^.kidlist^.child];
MarkCoveredSubtree[cover^.kidlist^.next^.child^.mate, cover^.kidlist^.next^.child]}
};
FromDagToCellType: PROC [tree: Dag] RETURNS [cellType: Core.CellType] ~ {
Takes a covered Dag and returns the cell type which implements that dag, the one implied by the cover.
publics: LIST OF CoreCreate.WR ← NIL;
intOnlys: LIST OF CoreCreate.WR ← NIL;
instances: CoreCreate.CellInstances ← NIL;
ClearScratch[tree];
FOR iter: Node ← tree^.csucs, iter^.next UNTIL iter = NIL DO
This marks all nodes which contribute input, output, or internal signals
IF iter^.output AND iter^.scratch = 0 THEN {
iter^.scratch ← 1;
IF iter^.type # prim THEN MarkCoveredSubtree[iter, iter^.cover^.csucs]};
IF iter^.type = prim THEN iter^.scratch ← 1;
This is to catch floating inputs (and currently Vdd and Gnd).
ENDLOOP;
FOR iter: Node ← tree^.csucs, iter^.next UNTIL iter = NIL DO
Here we create the publics and internal signals from the marked nodes.
IF iter^.scratch = 1 THEN {
iter^.wire ← CoreOps.CreateWires[0, WireNameFromNode[iter]];
IF iter^.output OR iter^.type = prim
THEN publics ← CONS[iter^.wire, publics]
ELSE intOnlys ← CONS[iter^.wire, intOnlys]}
ENDLOOP;
FOR iter: Node ← tree^.csucs, iter^.next UNTIL iter = NIL DO
Here we create the instances from the covers
IF iter^.scratch = 1 AND iter^.type # prim
THEN instances ← CONS[CoreCreate.InstanceList[iter^.cover^.cell, CollectWires[iter^.cover^.csucs]], instances];
ENDLOOP;
RETURN [CoreCreate.Cell[
public: CoreCreate.WireList[publics],
onlyInternal: CoreCreate.WireList[intOnlys],
instances: instances
]]
};
Tree Constructors
BoolTreeFromExpressionList: PUBLIC PROC [outputs: LIST OF ROPE, includeGlobalVariablesp: BOOL ← FALSE] RETURNS [tree: Dag] ~ {
This returns a BoolTree (Dag) constructed from a list of expressions
tree ← MakeNewBoolTree[];
IF includeGlobalVariablesp THEN {
[] ← MakeNewNodeB[tree, NIL, prim, "Gnd"];
[] ← MakeNewNodeB[tree, NIL, prim, "Vdd"]};
RBoolTreeFromExpressionList[tree, outputs]
};
RBoolTreeFromExpressionList: PROC [tree: Dag, outputs: LIST OF ROPE] ~ {
This adds an expression to the given tree.
IF outputs # NIL THEN {
AugmentBoolTreeBySingleExpression[tree, outputs.first];
RBoolTreeFromExpressionList[tree, outputs.rest]}
};
MakeNewBoolTree: PUBLIC PROC [] RETURNS [tree: Dag] ~ {
This creates a new Dag with no children
tree ← NEW[Degree]
};
MakeNewVariableNode: PUBLIC PROC [tree: Dag, name: ROPE] RETURNS [newNode: Node] ~ {
This creates a new node in tree which is treated as an input node with name the given name.
newNode ← MakeNewNodeB[tree, NIL, prim, name]
};
MakeNewNotNode: PUBLIC PROC [tree: Dag, node: Node] RETURNS [newNode: Node] ~ {
This creates a new node in tree which is the not of node.
newNode ← MakeNewNodeA[tree, node, not, NIL];
MakeLink[newNode, node]
};
RMakeNewLinks: PROC [vertex: Node, nodes: LIST OF Node] ~ {
IF nodes # NIL THEN {
MakeLink[vertex, nodes.first];
RMakeNewLinks[vertex, nodes.rest]}
};
MakeNewOrNode: PUBLIC PROC [tree: Dag, nodes: LIST OF Node] RETURNS [newNode: Node] ~ {
This creates a new node in tree which is the OR of all the nodes in the list of nodes.
newNode ← MakeNewNodeA[tree, NIL, or, NIL];
RMakeNewLinks[newNode, nodes]
};
MakeNewAndNode: PUBLIC PROC [tree: Dag, nodes: LIST OF Node] RETURNS [newNode: Node] ~ {
This creates a new node in tree which is the AND of all the nodes in the list of nodes.
newNode ← MakeNewNodeA[tree, NIL, and, NIL];
RMakeNewLinks[newNode, nodes]
};
NameNode: PUBLIC PROC [node: Node, name: ROPE] ~ {
This assigns the specified (var)name to the specified node. This is useful for later referencing that node by name.
node^.varname ← name
};
MakeNamedOutputNode: PUBLIC PROC [tree: Dag, node: Node, name: ROPE] ~ {
This causes the specified node to be viewed as one of the outputs.
node^.output ← TRUE;
node^.outname ← LIST[name]
};
END.