correlated-propagation crashes: Assertion `BI->getSuccessor(!isTrueDest) == BBTo && "BBTo isn't a successor of BBFrom"' failed.

[Quuxplusone]

Bugzilla Link	PR42431
Status	CONFIRMED
Importance	P enhancement
Reported by	Zhide Zhou (cszide@163.com)
Reported on	2019-06-27 18:50:11 -0700
Last modified on	2020-01-21 08:11:47 -0800
Version	trunk
Hardware	PC Linux
CC	llvm-bugs@lists.llvm.org, paulsson@linux.vnet.ibm.com, spatel+llvm@rotateright.com
Fixed by commit(s)
Attachments	small.bc (3580 bytes, application/octet-stream) tc_bb2isntsucc.ll (2218 bytes, text/plain)
Blocks
Blocked by
See also

Created attachment 22155
.bc file of the source code

Though the assert message of this bug is the same as bug 35801, the reason of
this bug maybe different from bug 35801, since one developer pointed out that
bug 35801 is a bug in NewGVN.

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

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

opt -slp-vectorizer -lowerswitch -loop-rotate -sroa -jump-threading -scalarizer
-break-crit-edges -correlated-propagation small.bc -o small-opt.bc
opt: /home/jack-
zhou/Documents/llvm/llvm_truck/llvm2/lib/Analysis/LazyValueInfo.cpp:1338: bool
getEdgeValueLocal(llvm::Value*, llvm::BasicBlock*, llvm::BasicBlock*,
llvm::ValueLatticeElement&): Assertion `BI->getSuccessor(!isTrueDest) == BBTo
&& "BBTo isn't a successor of BBFrom"' failed.
Stack dump:
0.  Program arguments: /home/jack-
zhou/Documents/llvm/llvm_truck/llvm2/build1/bin/opt -slp-vectorizer -
lowerswitch -loop-rotate -sroa -jump-threading -scalarizer -break-crit-edges -
correlated-propagation small.bc -o small-opt.bc
1.  Running pass 'Function Pass Manager' on module 'small.bc'.
2.  Running pass 'Value Propagation' on function '@g'
 #0 0x0000555d46c2887a llvm::sys::PrintStackTrace(llvm::raw_ostream&) (/home/jack-zhou/Documents/llvm/llvm_truck/llvm2/build1/bin/opt+0x257887a)
 #1 0x0000555d46c26534 llvm::sys::RunSignalHandlers() (/home/jack-zhou/Documents/llvm/llvm_truck/llvm2/build1/bin/opt+0x2576534)
 #2 0x0000555d46c26672 SignalHandler(int) (/home/jack-zhou/Documents/llvm/llvm_truck/llvm2/build1/bin/opt+0x2576672)
 #3 0x00007ff520c52890 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x12890)
 #4 0x00007ff51f904e97 raise /build/glibc-OTsEL5/glibc-2.27/signal/../sysdeps/unix/sysv/linux/raise.c:51:0
 #5 0x00007ff51f906801 abort /build/glibc-OTsEL5/glibc-2.27/stdlib/abort.c:81:0
 #6 0x00007ff51f8f639a __assert_fail_base /build/glibc-OTsEL5/glibc-2.27/assert/assert.c:89:0
 #7 0x00007ff51f8f6412 (/lib/x86_64-linux-gnu/libc.so.6+0x30412)
 #8 0x0000555d45f5fab8 (anonymous namespace)::LazyValueInfoImpl::getEdgeValue(llvm::Value*, llvm::BasicBlock*, llvm::BasicBlock*, llvm::ValueLatticeElement&, llvm::Instruction*) (/home/jack-zhou/Documents/llvm/llvm_truck/llvm2/build1/bin/opt+0x18afab8)
 #9 0x0000555d45f611b8 (anonymous namespace)::LazyValueInfoImpl::solve() (/home/jack-zhou/Documents/llvm/llvm_truck/llvm2/build1/bin/opt+0x18b11b8)
#10 0x0000555d45f633d8 (anonymous
namespace)::LazyValueInfoImpl::getValueOnEdge(llvm::Value*, llvm::BasicBlock*,
llvm::BasicBlock*, llvm::Instruction*) (/home/jack-
zhou/Documents/llvm/llvm_truck/llvm2/build1/bin/opt+0x18b33d8)
#11 0x0000555d45f63538 llvm::LazyValueInfo::getConstantOnEdge(llvm::Value*,
llvm::BasicBlock*, llvm::BasicBlock*, llvm::Instruction*) (/home/jack-
zhou/Documents/llvm/llvm_truck/llvm2/build1/bin/opt+0x18b3538)
#12 0x0000555d4696fbf6 runImpl(llvm::Function&, llvm::LazyValueInfo*,
llvm::DominatorTree*, llvm::SimplifyQuery const&) (/home/jack-
zhou/Documents/llvm/llvm_truck/llvm2/build1/bin/opt+0x22bfbf6)
#13 0x0000555d46971aa5 (anonymous
namespace)::CorrelatedValuePropagation::runOnFunction(llvm::Function&)
(/home/jack-zhou/Documents/llvm/llvm_truck/llvm2/build1/bin/opt+0x22c1aa5)
#14 0x0000555d465e1189 llvm::FPPassManager::runOnFunction(llvm::Function&)
(/home/jack-zhou/Documents/llvm/llvm_truck/llvm2/build1/bin/opt+0x1f31189)
#15 0x0000555d465e1281 llvm::FPPassManager::runOnModule(llvm::Module&)
(/home/jack-zhou/Documents/llvm/llvm_truck/llvm2/build1/bin/opt+0x1f31281)
#16 0x0000555d465e03e1 llvm::legacy::PassManagerImpl::run(llvm::Module&)
(/home/jack-zhou/Documents/llvm/llvm_truck/llvm2/build1/bin/opt+0x1f303e1)
#17 0x0000555d44ec90a9 main (/home/jack-
zhou/Documents/llvm/llvm_truck/llvm2/build1/bin/opt+0x8190a9)
#18 0x00007ff51f8e7b97 __libc_start_main /build/glibc-OTsEL5/glibc-
2.27/csu/../csu/libc-start.c:344:0
#19 0x0000555d44f4e3fa _start (/home/jack-
zhou/Documents/llvm/llvm_truck/llvm2/build1/bin/opt+0x89e3fa)
Aborted (core dumped)

--------------------------------
int a, d, e, f;
unsigned b;
short c;
int g() {
  long h[] = {4, 4, 4, 4, 4};
j:
  b = -6;
  for (; b < 9;) {
    int i = 0;
    for (; i < 6; i++)
      for (; c;) {
        if (a)
          goto j;
        return d;
      }
    if (f) {
      long *k = &h[2];
      *k = 0;
    } else
      goto j;
  }
  return e;
}

[Quuxplusone]

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

[Quuxplusone]

Looks like a bug in the scalarizer pass - that's the first place that I see a
block with a misplaced phi:

LeafBlock1:                                       ; preds = %for.end7,
%for.body5
  %cleanup.dest.lcssa = phi i32 [ 2, %for.body5 ], [ 2, %for.end7 ]
  %h.sroa.4.2 = phi <2 x i64> [ %h.sroa.4.16.vec.insert, %for.body5 ], [ %h.sroa.4.16.vec.insert, %for.end7 ]
  %h.sroa.4.2.i0 = extractelement <2 x i64> %h.sroa.4.2, i32 0
  %h.sroa.4.2.i1 = extractelement <2 x i64> %h.sroa.4.2, i32 1
  %cleanup.dest.slot.0 = phi i32 [ 2, %for.body5 ], [ 2, %for.end7 ]
  br label %j.for.end11_crit_edge

PHI nodes not grouped at top of basic block!
  %cleanup.dest.slot.0 = phi i32 [ 2, %for.body5 ], [ 2, %for.end7 ]

[Quuxplusone]

Attached tc_bb2isntsucc.ll (2218 bytes, text/plain): SystemZ reduced test case