[llvm-bugs] [Bug 31412] New: SCEV unable to infer loop max bound for remainder loops

[via llvm-bugs]

https://llvm.org/bugs/show_bug.cgi?id=31412

            Bug ID: 31412
           Summary: SCEV unable to infer loop max bound for remainder
                    loops
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: normal
          Priority: P
         Component: Loop Optimizer
          Assignee: unassignedbugs at nondot.org
          Reporter: mkuper at google.com
                CC: llvm-bugs at lists.llvm.org,
                    sanjoy at playingwithpointers.com
    Classification: Unclassified

Consider:

void foo0(int* in, int* out, unsigned k) {
  k %= 4;
  for (int i = 0; i < k; ++i) {
    in[i] += out[i];
  }
}

$ bin/clang -m32 -c -S -o - -O2 ~/llvm/temp/smallmax.cpp -emit-llvm | bin/opt
-analyze -scalar-evolution
[...]
Loop %for.body: backedge-taken count is (-1 + (zext i2 (trunc i32 %k to i2) to
i32))<nsw>
Loop %for.body: max backedge-taken count is -1


After talking to Sanjoy, it seems that the main issue is that
max-backedge-taken computation does not take the fact that "if the backedge is
taken, necessarily k > 0" into account.

Indeed:

void foo2(int* in, int* out, unsigned k) {
  k %= 4;
  k += 2;
  for (int i = 0; i < k; ++i) {
    in[i] += out[i];
  }
}

$ bin/clang -m32 -c -S -o - -O2 ~/llvm/temp/smallmax.cpp -emit-llvm | bin/opt
-analyze -scalar-evolution
[...]
Loop %for.body: backedge-taken count is (1 + (zext i2 (trunc i32 %k to i2) to
i32))<nuw><nsw>
Loop %for.body: max backedge-taken count is 4

But I think this is not the only problem.
If it were, adding 1 to k should have been sufficient, but:

void foo1(int* in, int* out, unsigned k) {
  k %= 4;
  k += 1;
  for (int i = 0; i < k; ++i) {
    in[i] += out[i];
  }
}

$ bin/clang -m32 -c -S -o - -O2 ~/llvm/temp/smallmax.cpp -emit-llvm | bin/opt
-analyze -scalar-evolution
[...]
Loop %for.body: backedge-taken count is (zext i2 (trunc i32 %k to i2) to i32)
Loop %for.body: max backedge-taken count is -1

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20161217/57738b0a/attachment-0001.html>