[AMDGPU] `SI annotate control flow` pass failed with error `failed to annotate CFG`

[HazyFish]

Description

The following IR code containing an infinite loop (which should compile) cause SI annotate control flow pass to fail with error failed to annotate CFG when targeting amdgcn.
The problem does not exist when targeting x86_64, aarch64, wasm64, or riscv64.

Minimal Reproduction

https://godbolt.org/z/snsTaonnr

Code

define void @f(i1 %0, i1 %1) {
BB:
  br label %BB1

BB1:                                              ; preds = %BB, %BB3
  br i1 %0, label %BB3, label %BB2

BB2:                                              ; preds = %BB2, %BB1
  br i1 %1, label %BB3, label %BB2

BB3:                                              ; preds = %BB2, %BB1
  br i1 true, label %BB1, label %BB4

BB4:                                              ; preds = %BB3
  ret void
}

Stack Trace

LLVM ERROR: failed to annotate CFG
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.	Program arguments: ./llvm-project/build-debug/bin/llc -mtriple=amdgcn ./crash-reports/dagisel-amdgcn/2.ll
1.	Running pass 'CallGraph Pass Manager' on module './crash-reports/dagisel-amdgcn/2.ll'.
2.	Running pass 'SI annotate control flow' on function '@f'
 #0 0x00000000047ada8a llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) /home/henry/aflplusplus-isel/llvm-project/llvm/lib/Support/Unix/Signals.inc:569:11
 #1 0x00000000047adc3b PrintStackTraceSignalHandler(void*) /home/henry/aflplusplus-isel/llvm-project/llvm/lib/Support/Unix/Signals.inc:636:1
 #2 0x00000000047ac286 llvm::sys::RunSignalHandlers() /home/henry/aflplusplus-isel/llvm-project/llvm/lib/Support/Signals.cpp:104:5
 #3 0x00000000047ae365 SignalHandler(int) /home/henry/aflplusplus-isel/llvm-project/llvm/lib/Support/Unix/Signals.inc:407:1
 #4 0x00007fa6c9d59980 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x12980)
 #5 0x00007fa6c8c49e87 raise /build/glibc-CVJwZb/glibc-2.27/signal/../sysdeps/unix/sysv/linux/raise.c:51:0
 #6 0x00007fa6c8c4b7f1 abort /build/glibc-CVJwZb/glibc-2.27/stdlib/abort.c:81:0
 #7 0x00000000046d5934 llvm::report_fatal_error(llvm::Twine const&, bool) /home/henry/aflplusplus-isel/llvm-project/llvm/lib/Support/ErrorHandling.cpp:125:5
 #8 0x00000000046d57a2 /home/henry/aflplusplus-isel/llvm-project/llvm/lib/Support/ErrorHandling.cpp:83:3
 #9 0x0000000001534f91 (anonymous namespace)::SIAnnotateControlFlow::runOnFunction(llvm::Function&) /home/henry/aflplusplus-isel/llvm-project/llvm/lib/Target/AMDGPU/SIAnnotateControlFlow.cpp:385:10
#10 0x0000000003c55c66 llvm::FPPassManager::runOnFunction(llvm::Function&) /home/henry/aflplusplus-isel/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1430:23
#11 0x0000000002e1c64d (anonymous namespace)::CGPassManager::RunPassOnSCC(llvm::Pass*, llvm::CallGraphSCC&, llvm::CallGraph&, bool&, bool&) /home/henry/aflplusplus-isel/llvm-project/llvm/lib/Analysis/CallGraphSCCPass.cpp:179:20
#12 0x0000000002e1bfde (anonymous namespace)::CGPassManager::RunAllPassesOnSCC(llvm::CallGraphSCC&, llvm::CallGraph&, bool&) /home/henry/aflplusplus-isel/llvm-project/llvm/lib/Analysis/CallGraphSCCPass.cpp:476:10
#13 0x0000000002e1b95f (anonymous namespace)::CGPassManager::runOnModule(llvm::Module&) /home/henry/aflplusplus-isel/llvm-project/llvm/lib/Analysis/CallGraphSCCPass.cpp:542:18
#14 0x0000000003c56539 (anonymous namespace)::MPPassManager::runOnModule(llvm::Module&) /home/henry/aflplusplus-isel/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1545:23
#15 0x0000000003c560ad llvm::legacy::PassManagerImpl::run(llvm::Module&) /home/henry/aflplusplus-isel/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:535:16
#16 0x0000000003c5ad71 llvm::legacy::PassManager::run(llvm::Module&) /home/henry/aflplusplus-isel/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1672:3
#17 0x0000000000d38a5c compileModule(char**, llvm::LLVMContext&) /home/henry/aflplusplus-isel/llvm-project/llvm/tools/llc/llc.cpp:737:41
#18 0x0000000000d36e02 main /home/henry/aflplusplus-isel/llvm-project/llvm/tools/llc/llc.cpp:418:13
#19 0x00007fa6c8c2cc87 __libc_start_main /build/glibc-CVJwZb/glibc-2.27/csu/../csu/libc-start.c:344:0
#20 0x0000000000d3660a _start (./llvm-project/build-debug/bin/llc+0xd3660a)

[llvmbot]

@llvm/issue-subscribers-backend-amdgpu

[gandhi56]

Codegen prepare invokes local transformations which eliminates the block with the return statement, the result conflicts with the invariants laid down in SIAnnotateControlFlow pass.

[gandhi56]

Related patch: D136892

EDIT: Does not fix the issue.

[gandhi56]

SIAnnotateControlFlow pass is able to annotate a simple non-nested infinite loop correctly. StructurizeCFG does not seem to perform any transformations on the following CFG after codegen-prepare pass:

I tracked SIAnnotateControlFlow and observed that BB4 is the last node visited in the depth-first traversal of this graph. When BB4 is handled by handleLoop(..), BB3 is pushed into the stack. Since BB4 is the last node to be visited in the dfs-traversal, BB3 continues to live in the stack and the pass declares the CFG as unstructured.

[gandhi56]

@tstellar thoughts?

[gandhi56]

If we ensure that no basic block is visited more than once, ie. pushed into the stack only if it was never pushed before, the code compiles. cc @arsenm

[DataCorrupted]

That make sense to me.

[gandhi56]

Differential Revision: https://reviews.llvm.org/D139780