Re: Maximum number of temporary variables needed for math expressions

  <ehsan.akhgari@gmail.com> wrote:
>Is there any upper bounds on the number of temporary variables that are
>needed to translate any given mathematical expression? By intuition, I
>guess the answer is 2,


To start at the end, I think commutativity is not relevant with three
address code, since if c and d are the wrong way around in "/ c, d,
t2", then you just write "/ d, c, t2".


To answer the original question, it firstly depends on what you include
in the definition of a mathematical expression. If you include
arbitrary mathematical expressions, there is no limit:
f(a0+b, f(a1+b, f(a2+b, f(a3+b, ... f(aN+b)... ))))
requires N+1 temporaries. Of course you might want to disregard
function arguments on the grounds that you're going to push them on a
stack, so they don't take up registers. In that case it depends on the
number of precedences in the language and operator properties. For
example, with (+, *, ^) you may need three:


a^b * c^d + e^f * g^h


^ a, b, t1
^ c, d, t2
* t1, t2, t1
^ e, f, t2
^ g, h, t3
* t2, t3, t2
+ t1, t2, t1


However, note that the number of precedences might not be fixed. For
example, if you want brackets to force order of evaluation, then:


((a + b) + (c + d)) + ((e + f) + (g + h))


needs three temporaries, otherwise only one. If you then allow an
arbitrary number of brackets in expressions, then you need an arbitrary
number of temporaries.


However operators such as C's &&, ||, and ?: do not add temporaries,
since their effect is encoded implicitly in the program code:


(a + b) ? (c + d) : (e + f)


+ a, b, t1
if t1 jump yes
+ e, f, t1
jump done
yes: + c, d, t1
done:


Only one temporary is needed, even though (a + b) * (c + b) would need
two.

Return to the comp.compilers page.
Search the comp.compilers archives again.