Jump Threading produces invalid IR in the presence of endless loop

[Quuxplusone]

Bugzilla Link	PR41320
Status	CONFIRMED
Importance	P enhancement
Reported by	Zhide Zhou (cszide@163.com)
Reported on	2019-03-30 19:39:26 -0700
Last modified on	2019-04-01 13:12:26 -0700
Version	trunk
Hardware	PC Linux
CC	efriedma@quicinc.com, hfinkel@anl.gov, jdoerfert@anl.gov, llvm-bugs@lists.llvm.org
Fixed by commit(s)
Attachments	small.bc (3420 bytes, application/octet-stream) small-opt.bc (3368 bytes, application/octet-stream)
Blocks
Blocked by
See also

Created attachment 21710
.bc file of the source code

$clang -v
clang version 9.0.0 (trunk 355281)
Target: x86_64-unknown-linux-gnu
Thread model: posix
InstalledDir: /home/jack-zhou/Documents/llvm/llvm_truck/llvm/build4/bin
Found candidate GCC installation: /usr/lib/gcc/i686-linux-gnu/8
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/5
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/5.5.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.5.0
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/7
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/7.3.0
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/8
Selected GCC installation: /usr/lib/gcc/x86_64-linux-gnu/7.3.0
Candidate multilib: .;@m64
Candidate multilib: 32;@m32
Candidate multilib: x32;@mx32
Selected multilib: .;@m64

$clang -O3 -c -emit-llvm  -mllvm -disable-llvm-optzns small.c

$opt -slp-vectorizer -sroa -loop-rotate -jump-threading  small.bc -o small-
opt.bc

$opt -functionattrs small-opt.bc
In this step, opt will run a long time and cannot terminate.
I check it using godbolt, the problem also occurs for llvm 7/trunk. The
following is the output.

/compiler-explorer/c-preload/compiler-wrapper: line 21: 24515 Killed
"$@"

Compiler returned: 137

--------------------------------------------
a[];
b;
c() {
  int d;
  int *e = &d;
  int *f[][6] = {a, a};
  for (;;)
    for (d = 9; d > 13;) {
      int **g = &f[0][1];
      *g = f[0][0];
      h(**g);
      e[b];
    }
}

[Quuxplusone]

Attached small.bc (3420 bytes, application/octet-stream): .bc file of the source code

[Quuxplusone]

Attached small-opt.bc (3368 bytes, application/octet-stream): optimized .bc file of source code

[Quuxplusone]

The "problem" is not the attribute deduction it is just the first to expose it.

The small-opt.bc source contains this beautiful, dead, and endless looping
basic block that does not adhere to fundamental SSA properties:

; <label>:3:                                      ; preds = %3
    %.sroa.0.0.vec.extract = extractelement <2 x i32*> %.sroa.0.8.vec.insert, i32 0
    %.sroa.0.8.vec.insert = insertelement <2 x i32*> %.sroa.0.8.vec.insert, i32* %.sroa.0.0.vec.extract, i32 1
    %.sroa.0.8.vec.extract = extractelement <2 x i32*> %.sroa.0.8.vec.insert, i32 1
    [...]
    br label %3

Once that block is analyzed anywhere, things will explode. (In this case
llvm::findScalarElemen(..) in VectorUtils got stuck in an endless loop when it
followed the self referencing insertelement vector).

The culprit here is jump-threading, before that, the IR was valid (or at least
looked that way to me).

I'm not an expert on the jump-threading code so I'd suggest the following:
  - could you change the bug title to name the actual problem, maybe something along the lines of:  "Jump Threading produces invalid IR in the presence of endless loops"
  - we then try to get somebody else to look into it.

[Quuxplusone]

Our dominance predicate states that any instruction dominates an instruction in an unreachable block, including other unreachable instructions. (By "unreachable block", I mean a block where there is no CFG path from the entry block of the function to that block.) So the IR is valid, I think, and this is actually a bug in attribute deduction.

Granted, this does come up from time to time as something possibly worth changing; it's an edge case people writing passes often forget.