[llvm-dev] Question on induction variable simplification pass

[Hal Finkel via llvm-dev]

[+Sanjoy]

The fact that we lose information by widening during induction-variable 
simplification is certainly a known problem. I don't recall if we've 
ever really decided on a path forward. I personally suspect that, as an 
information-destroying transformation, the widening should be moved to 
the lowering phase (i.e. near where we do vectorization, etc.). Unless 
the widening itself enables other transformations, I don't see why we 
should do it early. The one exception I can think of is where it might 
enable us to collapse redundant PHIs, as is:

int i = 0; long j = 0;
for (; i < n; ++i, ++j) { ... using i and j ... }

but that seems like a special case we could handle separately.

  -Hal

On 04/12/2017 07:21 PM, Chawla, Pankaj via llvm-dev wrote:
>
> Hi all,
>
> It looks like the induction variable simplification pass prefers doing 
> a zero-extension to compute the wider trip count of loops when 
> extending the IV. This can sometimes result in loss of information 
> making ScalarEvolution’s analysis conservative which can lead to 
> missed performance opportunities.
>
> For example, consider this loopnest-
>
>   int i, j;
>
>   for(i=0; i< 40; i++)
>
>   for(j=0; j< i-1; j++)
>
>     A[i+j] = j;
>
> We are mainly interested in the backedge taken count of the inner loop.
>
> Before indvars, the backedge information computed by ScalarEvolution 
> is as follows-
>
> Outer loop-
>
> backedge-taken count is 39
>
> max backedge-taken count is 39
>
> Inner loop-
>
> backedge-taken count is {-2,+,1}<nsw><%for.cond1.preheader>
>
> max backedge-taken count is 37
>
> After indvars, the backedge information computed by ScalarEvolution is 
> as follows-
>
> Outer loop-
>
> backedge-taken count is 39
>
> max backedge-taken count is 39
>
> Inner loop-
>
> backedge-taken count is (-1 + (zext i32 
> {-1,+,1}<nsw><%for.cond1.preheader> to i64))<nsw>
>
> max backedge-taken count is -1
>
> If we generate sext instead of zext, the information computed by 
> ScalarEvolution is as follows-
>
> Outer loop-
>
> backedge-taken count is 39
>
> max backedge-taken count is 39
>
> Inner loop-
>
> backedge-taken count is {-2,+,1}<nw><%for.cond1.preheader>
>
> max backedge-taken count is -2
>
> We now have a simplified backedge taken count for the inner loop which 
> is almost as precise as before indvars, except for the <nw> flag 
> instead of <nsw> flag. I think ScalarEvolution should be able to 
> precisely deduce wrap flags in the presence of sext but this may 
> require a separate fix. The reason for the conservative max backedge 
> taken count may be the same.
>
> Thanks,
>
> Pankaj
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170412/68ec1432/attachment.html>