[llvm-dev] Regarding ScalarEvolution's loop backedge computation
Sanjoy Das via llvm-dev
llvm-dev at lists.llvm.org
Wed Jun 29 17:01:40 PDT 2016
Hi Pankaj,
Chawla, Pankaj via llvm-dev wrote:
> It looks like ScalarEvolution bails out of loop backedge computation if
> it cannot prove the IV stride as either positive or negative (based on
> loop control condition). I think this logic can be refined for signed
IVs.
>
> Consider this simple loop-
>
> void foo(int *A, int n, int s) {
>
> int i;
>
> for(i=0; i<n; i += s) {
>
> A[i]++;
>
> }
>
> }
>
> The IV of this loop has this SCEV form-
>
> {0,+,%s}<nsw><%for.body>
This looks valid -- we already do things like this for
for (i = A; i != B; i += 5)
...
and compute the backedge taken count as "(B - A) / 5" (roughly :) )
since if (B - A) is not divisible by 5 then we have UB due to
overflow. We just have to be careful around cases like:
for(i = 0; i < 60; i += s) {
may_exit();
}
"s" can be (say) -3 and the loop can take 160 backedges and then
"exit(0)", avoiding the undefined behavior due to underflow. "s" can
also be zero, in which case the loop can potentially take an infinite
number of backedges.
However, in the example you gave (written in LLVM's canonical rotated
form):
if (0 < N) {
i = 0;
do {
a[i]++;
i += s; // NSW add
} while (i < N);
}
For any s <= 0 we have undefined behavior, so it is sound to assume s
> 0.
Do you want to take a crack at fixing this? I'm traveling till the
10th of July, but I can review your change once I'm back.
-- Sanjoy
More information about the llvm-dev
mailing list