[llvm-dev] Canonicalize induction variables

[Michael Kruse via llvm-dev]

Not sure whether these are the actual reasons, but to explain the
difficulties with those loops.

2016-08-25 3:48 GMT+02:00 Yaoqing Gao via llvm-dev <llvm-dev at lists.llvm.org>:
> I just subscribed this group.  This is my first time to post a question (not
> sure if this is a right place for discussion) after I have a brief look at
> LLVM OPT (dev trunk).   I would expect loop simplification and induction
> variable canonicalization pass (IndVarSimplify pass) should be able to
> convert the following loops into a simple canonical form, i.e., there is a
> canonical induction variable which starts at zero and steps by one,
> getCanonicalInductionVariable() returns  the first PHI node in the loop
> header block.
>
> int test1 (int x[], int k, int s) {
>   int sum = 0;
>   for (int i = 0; i < k; i+=s) {
>     sum += x[i];
>   }
>   return sum;
> }

s could be zero making this an endless loop (C has some rules saying
that it can assume that certain loops do terminate, but I think it
does not apply to LLVM IR)


> int test2(int x[], int k, int s) {
>   int sum = 0;
>   for (int i = k; i > 0; i--) {
>     sum += x[i];
>   }
>   return sum;
> }

with k = INT_MIN where is no upper limit in that range. Neither

for (int j = 0; j < -INT_MIN; j++)

nor

for (int j = 0; j <= INT_MAX; j++)

do work here.

>
> Anyone can help explain why the current LLVM cannot canonicalize induction
> variables for the above loops (by design or a limitation to be fixed in the
> future)?  Thanks.

The first could be tackled with loop versioning of the s==0 case. The
second might be converted to

for (int j = -1; j < -(k+1); j++)

although this isn't the canonical form.


Michael