TwoifyAllTrees:
PUBLIC
PROC [ctcoll: Treeset] ~ {
Given a set of trees with only nands, nots and prims, finds all decompositions where only two-input-nands, nots, and prims are used --
count: INT ← 0;
repiter : Node;
representativesInAcc: Dag ← MakeNewTree[]; --This is used to detect identical cover trees. It contains a representative of each processed tree already made. It is done in a kludgey sort of fashion. For each tree to be represented, a node is created in representativesInAcc whose brother field point to the root of the tree being represented.
acc: Treeset ← MakeNewCTreeSet[]; --acc stands for accumulated
WHILE ctcoll^.top #
NIL
DO
--for each tree in ctcoll
kludge: BOOL ← TRUE;
temp : Treeset ← MakeNewCTreeSet[]; --we will make a new Treeset consisting of that tree only (and then remove that tree from ctcoll)
[] ← MakeNewTreeA[temp, NIL];
temp^.top^.size ← ctcoll^.top^.size;
temp^.top^.csucs ← ctcoll^.top^.csucs;
temp^.top^.val ← ctcoll^.top^.val;
temp^.top^.cell ← ctcoll^.top^.cell;
RemoveTree[ctcoll, ctcoll^.top];
TwoifyAllWays[temp]; --Then we generate all representations of this where the fanin of each nand is limited to 2.
repiter ← representativesInAcc^.csucs;
WHILE repiter #
NIL
DO
--Now, for each of the representatives in representativesInAcc
IF RecurseCSimilar[repiter^.brother, temp^.top^.csucs]
-- we compare it to the first of the processed decompositions in temp (Assumes that temp^.top^.csucs is actually the root of a tree) --
THEN {
--Here they are found to be similar, so we set a flag not to splice this set of trees in with the rest
kludge ← FALSE;
EXIT}
ELSE repiter ← repiter^.next;
ENDLOOP;
IF kludge
THEN {
--If it was a new tree (to the best of our ability to determine so)
RemoveDuplicates[temp]; --This eliminates duplicate trees within the newly processed tree
MakeNewNodeA[representativesInAcc, NIL]^.brother ← temp^.top^.csucs; --Pick a representative
Splice[temp,acc]}; --Add it right in to the growing set.
ENDLOOP;
ctcoll^.top ← acc^.top; --Here we give everything back to ctcoll, after having taken it all away
ctcoll^.size ← acc^.size;
FOR iter: Dag ← ctcoll^.top, iter^.next
UNTIL iter =
NIL
DO
--for each tree
FOR nodeIter: Node ← iter^.csucs, nodeIter^.next
UNTIL nodeIter =
NIL
DO
IF nodeIter^.parnum > 1
THEN {
--If we have a non true tree then we had better expand it so that we can use it to match covers.
iter^.unmap ← MakeUnmappingOfCTree[iter]; --This is where an unmapped version is stored
EXIT}
ENDLOOP;
ENDLOOP;
FOR iter: Dag ← ctcoll^.top, iter^.next
UNTIL iter =
NIL
DO
IF iter^.unmap =
NIL
THEN
--for each tree not unmapped
FOR niter: Node ← iter^.csucs, niter^.next
UNTIL niter =
NIL
DO
IF niter^.type = nand THEN niter^.sim ← RecurseCSimilar[niter^.kidlist^.child, niter^.kidlist^.next^.child]; --Check whether it has similar subtrees.
ENDLOOP;
ENDLOOP;
};
MakeUnmappingOfCTree:
PROC [oldtree: Dag]
RETURNS [newtree: Dag] ~ {
Given an oldtree (which may not be a true tree) this will yield a true tree with equal vertices being mapped onto the same original vertex (via the map field). This new tree is placed onto the unmap field of the old one (used to be internal but is now external and up to the caller)
newtree ← MakeNewBoolTree[];
FOR iter: Node ← oldtree^.csucs, iter^.next
UNTIL iter =
NIL
DO
IF iter^.parnum = 0 THEN [] ← RCopyNode[iter, newtree];
ENDLOOP;
newtree^.val ← oldtree^.val;
};
MakeNewBoolTree:
PROC []
RETURNS [tree: Dag] ~ {
This creates a new Dag with no children
tree ← NEW[Degree]
};
RCopyNode:
PROC [vertex: Node, newtree: Dag]
RETURNS [unmapped: Node] ~ {
This unmaps the selected node and its subtree in the fashion of MakeUnmappingOfCTree. Returns the unmapped node
unmapped ← MakeNewNodeB[newtree, NIL, vertex^.type, vertex^.inname, vertex^.varname, vertex^.outname, vertex^.output];
unmapped^.map ← vertex;
FOR iter: Kidptr ← vertex^.kidlist, iter^.next
UNTIL iter =
NIL
DO
w: Node ← RCopyNode[iter^.child, newtree];
MakeLink[unmapped, w];
ENDLOOP;
};
TwoifyAllWays:
PROC [ctcoll: Treeset] ~ {
Given a Treeset with only nots, nands, and prims, this will find all equivalent trees where no gate has more than two inputs. Currently, the way this is done is to call it with only one tree in the treeset at a time (this was originally going to make eliminating duplicates easier. I think it's still a slight win) --
tree: Dag ← ctcoll^.top;
OrphansToFront[tree];
WHILE
NOT tree^.done
DO
--The done field is naturally set when you are done processing a particular tree
special: Node ← SelectVertex[tree^.csucs]; --This is the vertex we are going to expand on this pass
IF special =
NIL
THEN {
--then we're all done
tree^.done ← TRUE;
PlaceTreeAtEnd[ctcoll, tree]}
ELSE {
offsethalf: INT ← IntPower[2, special^.kidnum - 1];
offset: INT ← 2*offsethalf;
This is the means by which the splitting up of the children of special is controlled. After all, they must be split up in all possible ways. Fortunately, with gates of three or four inputs this is not much.
count: INT ← 1;
WHILE count < offsethalf
DO
--while we have not yet split it up in all possible ways
nt: Dag ← MakeNewTreeA[ctcoll, tree];
ClearScratch[tree]; --Replicate demands that the scratch fields be cleared
PlaceAtBeg[nt, Replicate[tree^.csucs, nt, special, offset + count]];
This produces a copy of tree, modified according to count at special
nt^.val ← tree^.val;
nt^.cell ← tree^.cell;
nt^.csucs^.outname ← tree^.csucs^.outname; --nt^.csucs assumed to be the root
nt^.csucs^.output ← TRUE;
count ← count + 1;
ENDLOOP;
RemoveTree[ctcoll, tree]}; --If we've had to process a tree, we now get rid of it
tree ← ctcoll^.top;
ENDLOOP;
};
SelectVertex:
PROC [vertex: Node]
RETURNS [res: Node ←
NIL] ~ {
This yields a vertex (if it does not exist then NIL is returned) which is as far down as possible (in some sense), is not of prim, not, or buf type and has fanin at least 3
IF vertex^.type # prim
THEN
IF vertex^.type = not
OR vertex^.type = buf
THEN res ← SelectVertex[vertex^.kidlist^.child]
ELSE {
FOR kiditer: Kidptr ← vertex^.kidlist, kiditer^.next
UNTIL kiditer =
NIL
DO
res ← SelectVertex[kiditer^.child];
IF res # NIL THEN RETURN;
ENDLOOP;
IF vertex^.kidnum > 2 THEN res ← vertex};
RETURN
};
IntPower:
PROC [base, exp:
INT]
RETURNS [
INT] ~ {
Computes base ** exp. It is naturally more efficient than the version for reals. --
SELECT exp
FROM
0 => RETURN[1];
1 => RETURN[base];
ENDCASE => RETURN[IntPower[base, exp MOD 2] * IntPower[base * base, exp/2]];
};
Splice:
PROC [ezt, ebbe: Treeset] ~ {
This takes ezt (meaning from) and merges it into ebbe (meaning into). Every tree in ezt will follow every tree in ebbe in linear order (Ie. ezt is put at the end of ebbe)
IF ebbe^.top =
NIL
THEN ebbe^.top ← ezt^.top
ELSE
IF ezt^.top #
NIL
THEN {
temp : Dag ← ebbe^.top^.prev;
FOR iter: Dag ← ezt^.top, iter^.next
UNTIL iter =
NIL
DO
iter^.number ← iter^.number + ebbe^.size;
ENDLOOP;
temp^.next ← ezt^.top;
ebbe^.top^.prev ← ezt^.top^.prev;
ezt^.top^.prev ← temp};
ebbe^.size ← ebbe^.size + ezt^.size
};
RemoveDuplicates:
PROC [ctcoll: Treeset] ~ {
Given a collection of trees (not Dags) this will remove any obviously identical ones. Assumes that the trees are composed of only nands, nots, and prims. --
iter1: Dag ← ctcoll^.top;
WHILE iter1 #
NIL
DO
iter2: Dag ← iter1^.next;
WHILE iter2 #
NIL
DO
IF RecurseCSimilar[iter1^.csucs,iter2^.csucs]
--This yields whether two subtrees are similar
THEN {
temp : Dag ← iter2^.next;
RemoveTree[ctcoll, iter2];
iter2 ← temp}
ELSE iter2 ← iter2^.next;
ENDLOOP;
iter1 ← iter1^.next;
ENDLOOP;
};