# 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?