[LLVMdev] 'loop invariant code motion' and 'Reassociate Expression'

[Dan Gohman]

On Thu, Apr 25, 2013 at 2:07 AM, Andrew Trick <atrick at apple.com> wrote:

>
> On Apr 23, 2013, at 10:37 AM, Shuxin Yang <shuxin.llvm at gmail.com> wrote:
>
> > As far as I can understand of the code, the Reassociate tries to achieve
> this result by its "ranking" mechanism.
> >
> > If it dose not, it is not hard to achieve this result, just restructure
> the expression in a way such that
> > the earlier definition of the sub-expression is permute earlier in the
> resulting expr.
> >
> > e.g.
> >   outer-loop1
> >       x=
> >       outer-loop2
> >          y =
> >
> >          inner-loop3
> >              z =
> >              t = z * y * z
>

I assume this was meant to be z * y * x.


>  >
> >    the RHS is better restructured into "x * y * z", such that x * y can
> moved as early as possible.
> > Restructuring expr this expr is also able to reduce the critical path
> even if no sub-expr is
> > moved out of loop.
>
> >

> >
> >   By no means can "canonicalization" can achieve this result, because as
> this transformation need
> > some context. (It seems the name "cannonicalization" is badly abused in
> LLVM; it could refers
> > to this kind of xform. IMO, cannonicalization is sort of blind but
> consistent restructuring)
>

Actually, canonicalization is not quite that blind; it does intentionally
achieve exactly the result you want in your example.


> >   BTW, I did similar stuff before in other compiler, I didn't see any %.
>
> 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.
>

Reassociate orders instruction with a reverse post order "which effectively
gives values in deep loops higher rank than values not in loops".

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.

Dan
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130425/b43d1afe/attachment.html>