DIRECTORY
Convert, Core, CoreCreate, CoreDirectory, CoreOps, CoreProperties, Drot, DrotBool, DrotCover, Rope, SymTab, TerminalIO;
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];
InputOK[be];
[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;
};
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];
InputOK[be];
[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;
};
AddCell:
PROC [ctcoll: Treeset, name, expression:
ROPE] = {
AddInputToCover[expression, ctcoll];
ctcoll.top.cell ← NARROW [SymTab.Fetch[CoreDirectory.FetchLibrary["CMOSB"], name].val];
ctcoll.top.val ← NARROW[CoreProperties.GetCellTypeProp[ctcoll.top.cell, $CellArea], REF INT]^;
};
AssembleCTree:
PROC [ctcoll: Treeset] ~ {
This is where the trees to be used in the cover are created.
1 input
AddCell[ctcoll, "inv", "X ← ~I"];
2 inputs
AddCell[ctcoll, "nand2", "X ← ~(I-A * I-B)"];
AddCell[ctcoll, "and2", "X ← I-A * I-B"];
AddCell[ctcoll, "nor2", "X ← ~(I-A + I-B)"];
AddCell[ctcoll, "or2", "X ← I-A + I-B"];
AddCell[ctcoll, "xor2", "X ← I-A * I-B + ~I-A * ~I-B"];
AddCell[ctcoll, "xnor2", "X ← I-A * ~I-B + ~I-A * I-B"];
AddCell[ctcoll, "xnor2", "X ← ~( I-A * ~I-B + ~I-A * I-B)"]; -- might produce other mappings than the previous one!
3 inputs (some missing)
AddCell[ctcoll, "nand3", "X ← ~(I-A * I-B * I-C)"];
AddCell[ctcoll, "and3", "X ← I-A * I-B * I-C"];
AddCell[ctcoll, "nor3", "X ← ~(I-A + I-B + I-C)"];
AddCell[ctcoll, "or3", "X ← I-A + I-B + I-C"];
AddCell[ctcoll, "a21o2i", "X ← ~(A*B+C)"];
4 inputs (many missing)
AddCell[ctcoll, "nand4", "X ← ~(I-A * I-B * I-C * I-D)"];
AddCell[ctcoll, "nor4", "X ← ~(I-A + I-B + I-C + I-D)"];
AddCell[ctcoll, "and4", "X ← I-A * I-B * I-C * I-D"];
AddCell[ctcoll, "or4", "X ← I-A + I-B + I-C + I-D"];
AddCell[ctcoll, "a22o2i", "X ← ~(A*B+C*D)"];
AddCell[ctcoll, "o22a2i", "X ← ~((A+B)*(C+D))"];
};
InputOK:
PUBLIC PROC [output:
ROPE] ~ {
Verifies that be1 is a legitimate boolean expression--
len: INT ← Rope.Length[output];
asspos: INT ← Rope.Find[output, "←", 0];
be : ROPE ← Rope.Substr[output, asspos + 1, len - asspos - 1];
IF
NOT ParensMatch[be]
THEN {TerminalIO.PutF["Parens not OK\n"]; ERROR};
IF
NOT AndOrOK[be]
THEN {TerminalIO.PutF["Chars not OK"]; ERROR}
};
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;
};
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
AND kiditer^.child^.type # prim
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 modified ← 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
TRUE
FROM
Rope.Equal[iter.inname, "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;
};
Rope.Equal[iter.inname, "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
};
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]
};
Find:
PROC [number:
INT, tree: Dag]
RETURNS [vertex: Node] ~ {
FOR iter: Node ← tree^.csucs, iter^.next
UNTIL iter =
NIL
DO
IF iter^.number = number THEN RETURN[iter];
ENDLOOP;
};