We write 'reg' to denote arbitrary reg_i .

Suppose we have the following instructions, with associated costs (cycle estimate):

Suppose that we treat each of these as a grammar rule

• tree grammars have trees on right-hand side instead of sequences of terminals and non-terminals

Consider expression

v = ((x*y + z) + x) + 1

and suppose that initially we have variables in these places:

x : r5
y : Mem(yAddr)
z : Memo(zAddr)

and we expect result v in r2.

Our expression has the pattern has the pattern

r2 = Plus(Plus(Plus(Mul(r5,Mem(yAddr)),Mem(zAddr)),r5),1)

We can derive this pattern from the grammar rules as follows, in bottom up way:

An alternative ending is

and there are many other tilings.

How to choose the one with minimal estimated cost?