This is tested with rev. 314335. $ clangpolly -v clang version 6.0.0 (http://llvm.org/git/clang.git 31a16c4f5bc89d8e9ca6c0a52a34b98c18058b6b) Target: x86_64-unknown-linux-gnu Thread model: posix InstalledDir: /home/su/bin Found candidate GCC installation: /usr/lib/gcc/i686-linux-gnu/4.9 Found candidate GCC installation: /usr/lib/gcc/i686-linux-gnu/4.9.4 Found candidate GCC installation: /usr/lib/gcc/i686-linux-gnu/5 Found candidate GCC installation: /usr/lib/gcc/i686-linux-gnu/5.3.0 Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.4 Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.4.7 Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.6 Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.6.4 Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.7 Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.7.3 Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.8 Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.8.5 Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.9 Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.9.4 Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/5 Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/5.3.0 Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/6 Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/6.2.0 Selected GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.9 Candidate multilib: .;@m64 Candidate multilib: 32;@m32 Candidate multilib: x32;@mx32 Selected multilib: .;@m64 $ $ clangpolly -O3 -mllvm -disable-llvm-optzns -c -emit-llvm -o small.bc small.c $ optpolly -instcombine -early-cse-memssa -loop-rotate -loop-unroll -newgvn -simplifycfg -licm -loop-reroll -o small-opt.bc small.bc $ clangpolly small-opt.bc $ ./a.out 8 $ $ clangpolly -O0 small.c; ./a.out 1 $ ------------------------------------ int printf (const char *, ...); int a, b, c[1][8]; int main () { for (; a < 1; a++) for (b = 0; b < 8; b++) c[a][b] = 0; printf ("%d\n", a); return 0; }
I do not think this is NewGVN related, it also fails if I replace -newgvn with -gvn
Created attachment 22272 [details] Reproducer before -loop-reroll It looks like this is a loop-reroll issue. I've attached the bitcode before -loop-reroll. In the reproducer, we print the final value of the loop induction variable, but it is not adjusted properly after re-rolling the loop. After re-rolling the loop gets executed 8 times and the induction value is 8 when exiting the loop, instead of 1 in the original loop.
I found a possible problematic code in the loop-reroll pass through discussion of <https://reviews.llvm.org/D79549>. The reporter's loop is as follows. -------------------------------- for (; a < 1; a++) for (b = 0; b < 8; b++) c[a][b] = 0; -------------------------------- It is unrolled by `opt ... -loop-rotate -loop-unroll ...` as follows (written in C for readability). This has no problem. -------------------------------- if (a < 1) { do { c[a][0] = 0; c[a][1] = 0; ... c[a][7] = 0; a++; } while (a < 1); } -------------------------------- The corresponding GEP instrctions are as follows. -------------------------------- %arrayidx5 = getelementptr inbounds [1 x [8 x i32]], [1 x [8 x i32]]* @c, \ i64 0, i64 %idxprom, i64 0 %arrayidx5.1 = getelementptr inbounds [1 x [8 x i32]], [1 x [8 x i32]]* @c, \ i64 0, i64 %idxprom, i64 1 %arrayidx5.2 = getelementptr inbounds [1 x [8 x i32]], [1 x [8 x i32]]* @c, \ i64 0, i64 %idxprom, i64 2 ... -------------------------------- Using the current algorithm of the loop-reroll pass, this loop cannot be rerolled by `opt -loop-reroll` because the PHIs are `c[a][i]`, not `c[a+i][N]`. However, it is rerolled incorrectly. I think the problem is in the LoopReroll::DAGRootTracker::collectPossibleRoots function of the llvm/lib/Transforms/Scalar/LoopRerollPass.cpp file. https://github.com/llvm/llvm-project/blob/llvmorg-10.0.0/llvm/lib/Transforms/Scalar/LoopRerollPass.cpp#L795 It always uses the last operand of a PHI. In the case above, the assumed induction variable is `a`. It is not the last operand of the `c` array. Probably we must find a proper operand of a PHI.
I'd focus on making sure we reject cases the pass doesn't understand, before trying to look into improved unrolling.