<div dir="ltr">On Thu, Apr 25, 2013 at 2:07 AM, Andrew Trick <span dir="ltr"><<a href="mailto:atrick@apple.com" target="_blank">atrick@apple.com</a>></span> wrote:<br><div class="gmail_extra"><div class="gmail_quote">

<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><br>
On Apr 23, 2013, at 10:37 AM, Shuxin Yang <<a href="mailto:shuxin.llvm@gmail.com" target="_blank">shuxin.llvm@gmail.com</a>> wrote:<br>
<br>
> As far as I can understand of the code, the Reassociate tries to achieve this result by its "ranking" mechanism.<br>
><br>
> If it dose not, it is not hard to achieve this result, just restructure the expression in a way such that<br>
> the earlier definition of the sub-expression is permute earlier in the resulting expr.<br>
><br>
> e.g.<br>
>   outer-loop1<br>
>       x=<br>
>       outer-loop2<br>
>          y =<br>
><br>
>          inner-loop3<br>
>              z =<br>
>              t = z * y * z<br></div></blockquote><div><br></div><div>I assume this was meant to be z * y * x.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">

<div>
><br>
>    the RHS is better restructured into "x * y * z", such that x * y can moved as early as possible.<br>
> Restructuring expr this expr is also able to reduce the critical path even if no sub-expr is<br>
> moved out of loop.<br></div></blockquote><div>> ></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div>
><br>
>   By no means can "canonicalization" can achieve this result, because as this transformation need<br>
> some context. (It seems the name "cannonicalization" is badly abused in LLVM; it could refers<br>
> to this kind of xform. IMO, cannonicalization is sort of blind but consistent restructuring)<br></div></blockquote><div><br></div><div>Actually, canonicalization is not quite that blind; it does intentionally achieve exactly the result you want in your example.</div>

<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div>
>   BTW, I did similar stuff before in other compiler, I didn't see any %.<br>
<br>
</div>Right. Reassociate ranks expressions by their order in the IR, so shouldn't make matters worse, but it doesn't know about loops so can't expose more of these opportunities AFAIK.<br></blockquote><div><br>

</div><div>Reassociate orders instruction with a reverse post order "which effectively gives values in deep loops higher rank than values not in loops".</div><div><br></div><div>The problem in the original testcase is that %next.0 is not trivially loop-invariant when reassociate sees it. It's a phi node, and it's in the same block as %total.0. It's hard to say since we don't have a complete testcase, but probably this is causing it to turn into something actually loop-invariant under loop-simplify. Consequently, this may just be a phase-ordering problem. Alternatively, perhaps reassociate should rank phi nodes in the same block by the ranks of their inputs.</div>

<div><br></div><div>Dan</div><div><br></div></div></div></div>