# Tree Tiling of xyz Example

We write 'reg' to denote arbitrary reg_i .

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

 instruction cost ri ← rj 1 ri ← Plus(ri,rj) 2 r1 ← Plus(ri,rj) 2 r2 ← Mul(r2,r3) 3 r4 ← Mul(r4,r5) 3 ri ← Load(mem) 10 r1 ← Plus(mem,mem) 21 r1 ← Plus(const,mem) 14 ri ← const 2 r2 ← r2 + 1 1

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

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:

 current expression cost of reduction Plus(Plus(Plus(Mul(r5,Mem(yAddr)),Mem(zAddr)),r5),1) 10 Plus(Plus(Plus(Mul(r5,r1),Mem(zAddr)),r5),1) 10 Plus(Plus(Plus(Mul(r5,r1),r2),r5),1) 1 Plus(Plus(Plus(Mul(r2,r1),r2),r5),1) 1 Plus(Plus(Plus(Mul(r2,r3),r2),r5),1) 3 Plus(Plus(Plus(r3,r2),r5),1) 2 Plus(Plus(r1,r5),1) 2 Plus(r1,1) 2 Plus(r1,r2) 2 r1 1 r2

An alternative ending is

 Plus(r1,1) 2 Plus(r2,1) 1 r2

and there are many other tilings.

How to choose the one with minimal estimated cost?