- LLVM-3.2 converts it into: (Notice the reversion of %total.0 and %next.0)
--after Reassociate expressions:
%add = add i32 %total.0, 1
%add1 = add i32 %add, %next.0
-- after Canonicalize natural loops:
%add = add i32 %total.0, 1
%add1 = add i32 %add, %next.0.ph
-- and during 'loop invariant code motion':
-> %next.0.ph and '1' are loop invariant, but because those are spreaded, they are not moved any more.
Is there a way that 'Reassociate expressions' of 'LICM' can rearrange the expressions (likely after 'Canonicalize natural loops'),
and group loop-invariant parts of the expression ?
Or is there another pass that I can/should enable to have this effect ?
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
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)
BTW, I did similar stuff before in other compiler, I didn't see any %.
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
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)
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.
Jeroen, it may be worth filing a bug. I'm not sure why LSR isn't handling it later.
For cases that LSR doesn't handle, we've been wanting an MI reassociate pass in the backend anyway to expose ILP. That could clean up cases like this when it's actually on the critical path and we don't mind the regpressure.
> 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.
The problem is indeed that one of the variables, becomes loop invariant after
some of the loop transformations.
From: Andrew Trick [mailto:atrick@apple.com]
[...]
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.
Jeroen, it may be worth filing a bug. I'm not sure why LSR isn't handling it
later.
For cases that LSR doesn't handle, we've been wanting an MI reassociate
pass in the backend anyway to expose ILP. That could clean up cases like this
when it's actually on the critical path and we don't mind the regpressure.
I inserted a small optimization pass to recognize and fix this exact sequence.
This did indeed improve the performance (good ), but not to the amount that I hoped..
I'll try to come up with a reduced file that shows this problem and file a bugreport for it.
The problem is indeed that one of the variables, becomes loop invariant after
some of the loop transformations.
I imagine LoopSimplify is enough to fix your loop invariant phi so it’s an obvious constant. At least obvious enough for InstCombine to remove it from the loop. Unless LoopSimplify is being defeated by an indirect branch, which is just silly in the case of a loop where the back edge is not indirect.
), but not to the amount that I hoped..