3
$\begingroup$

Given $n$ inputs and $k$ outputs and $j$ identical binary function calls to $g$, how many possible distinct single-assignment forms are there?

The only assumption made about $g$ is that if $a = c \wedge b = d$ then $g(a, b) = g(c,d)$.

Each SSA form consists of two parts. The first is a temporary assignment part:

t1 = g(_, _)
...
tj = g(_, _)

Where each _ can be any of the inputs $i_1$ through $i_n$ or a previously calculated $t_x$. After that follows an output assignment part:

o1 = _
...
ok = _

where _ can be $i_1$ through $i_n$ or $t_1$ through $t_j$, but not another $o_x$. The output of the SSA form is $(o_1, o_2, \dots, o_k)$.

Trivial counting doesn't work, because the following two SSA forms seem different, but are equivalent (with $n = 4$, $k = 1$, $j = 3$):

t1 = g(i1, i2)       t1 = g(i3, i4)
t2 = g(i3, i4)       t2 = g(i1, i2)
t3 = g(t1, t2)       t3 = g(t2, t1)
o = t3               o = t3

Also this doesn't account for irrelevant changes that are still equivalent (with $n = 3, k = j = 1$):

t1 = g(i1, i2)       t1 = g(i1, i3)
o = i1               o = i1

Questions:

  1. What is $f(n, k, j)$, giving the number of distinct SSA forms?

  2. Does there exist an efficient way of iterating over these SSA forms?

  3. What if we also assume $g(a, b) = g(b, a)$?

$\endgroup$
  • $\begingroup$ @D.W. Note that t1 is never used in the output, therefore the two SSA forms behave identically for any input. Only the output $(o_1, \dots, o_k)$ is considered for equivalence of SSA forms. $\endgroup$ – orlp Mar 20 '18 at 15:16
  • $\begingroup$ @D.W. Does it help to think of them as the number of DAGs with $n$ sources, $k$ sinks and $j$ internal nodes with in-degree 2, but only considering the subset connected to the $k$ sinks for equivalence? Or alternatively the number of non-cyclic logic circuits made with a single gate type, with arbitrary splits allowed? $\endgroup$ – orlp Mar 20 '18 at 16:17
  • $\begingroup$ Ahh, I see. That's a nice way to think about this! Tricky case: we want t1 = g(i1, i2), t2 = g(i1, i2), o = g(t1, t2) to be equivalent to t1 = g(i1, i2), o = g(t1, t1), even though they naively lead to different DAGs. Or, to put it another way, we can't just count the number of DAGs; we have to restrict to DAGs where no pair of internal nodes are equivalent. $\endgroup$ – D.W. Mar 20 '18 at 16:22
  • $\begingroup$ Perhaps the generating function techniques at cs.stackexchange.com/q/368/755 could be useful here? Not sure how exactly to account for the equivalences, though. $\endgroup$ – D.W. Mar 20 '18 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.