wrong code with "opt -loop-reroll": escaping induction value is not updated properly

[zhendongsu]

Bugzilla Link	34760
Version	trunk
OS	All
CC	@efriedma-quic,@fhahn,@kawashima-fj

Extended Description

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; 
}

[fhahn]

I do not think this is NewGVN related, it also fails if I replace -newgvn with -gvn

[fhahn]

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.

[kawashima-fj]

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.

[efriedma-quic]

I'd focus on making sure we reject cases the pass doesn't understand, before trying to look into improved unrolling.

[fhahn]

This still reproduces with loop-reroll on current main: https://llvm.godbolt.org/z/f7ezh337f

[nikic]

The LoopReroll pass has been removed by #80972.