Re: [omr-dev] When to generate TreeTops

[Dibyendu Majumdar <mobile@xxxxxxxxxxxxxxx>]

Hi Leonardo,

Many thanks for the detailed reply - very helpful.

On 12 June 2018 at 01:36, Leonardo <leonardo2718@xxxxxxxxxxxxxx> wrote:
> (small side question: perhaps part of the confusion here has to do with the, very unfortunate, dual meaning of the name "TreeTop"?)
>

I was aware that TreeTops are used to dictate program order. The
problem I have is that my C front-end generates linear IR - so it is
not obvious whether a particular instruction has side effects. As for
order too it is not obvious other than saying every instruction must
be a TreeTop. As Mark said - if the compiler can remove unnecessary
TreeTops then this may be an option. I would be interested to know how
the Java front-end decides when to emit a TreeTop. I think if I was
writing a JIT function by hand I would know when to generate a
TreeTop.

> The important rule to remember is that TreeTops define program order. With that in mind, it might be helpful to look at what IL is generated in either case. (Disclaimer: I'm going to make some educated guesses about what the IL looks like based on the code you've shown and the behaviour you've described. However, I can't guarantee that this is what you'll actually see in a log file.)
>
> When the load is *not* under its own TreeTop, the generated IL will look something like:
>
> ```
> istorei
>   aladd
>     aload "base"
>     lconst 4
>   iconst 42
> ireturn
>   iloadi
>     aladd
>       aload "base"
>       lconst 4
> ```
>
> Even though you create the load before the store, it gets "connected" to the `ireturn` node. So, the load is evaluated after the store (when the return is evaluated). However, when the load is anchored to a TreeTop, you get:
>
> ```
> treetop
>   iloadi <---------+
>     aladd          |
>       aload "base" |
>       lconst 4     |
> istorei            |
>   aladd            |
>     aload "base"   |
>     lconst 4       |
>   iconst 42        |
> ireturn            |
>   iloadi --------->+  (this is a commond node)
> ```
>

Yes I checked the trace output - above seems pretty accurate
description of what happened.


> Here, the load is "connected" (inserted into the IL) before the store and will, therefore, be evaluated first.
>
> So, to summarize, you use TreeTops to describe program order. You generate them when you need to force some evaluation order. (Disclaimer: I believe the optimizer can still reorder things if TreeTops have no side-effects but I am not very familiar with the details.)
>
> I hope this is helpful :) ,

Thank you - it is indeed!

I have to work out a strategy for generating TreeTops for reasons I
describe above.

Thanks and Regards
Dibyendu