LARA

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
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:

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?