clspv::ComputeStructuredOrder crashes on infinite loops

[mantognini]

The following IR crashes clspv in clspv::ComputeStructuredOrder. It was produced while reducing another issue using bugpoint.

target datalayout = "e-p:32:32-i64:64-v16:16-v24:32-v32:32-v48:64-v96:128-v192:256-v256:256-v512:512-v1024:1024"
target triple = "spir-unknown-unknown"

define dso_local spir_kernel void @kernel() {
entry:
  br label %for.cond

for.cond:                                         ; preds = %for.cond, %entry
  br label %for.cond
}

GDB shows:

Reading symbols from clspv...
(gdb) r
Starting program: build_shared_debug/bin/clspv -x ir reduced.ll
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".
clspv: clspv/lib/ComputeStructuredOrder.cpp:58: void clspv::ComputeStructuredOrder(llvm::BasicBlock*, llvm::DominatorTree*, const llvm::LoopInfo&, std::deque<llvm::BasicBlock*>*, llvm::DenseSet<llvm::BasicBlock*>*):
Assertion `continue_block && merge_block && "Bad loop"' failed.

Program received signal SIGABRT, Aborted.
0x00007ffff7063fb7 in raise () from /lib/x86_64-linux-gnu/libc.so.6
(gdb) bt
#0  0x00007ffff7063fb7 in raise () from /lib/x86_64-linux-gnu/libc.so.6
#1  0x00007ffff7065921 in abort () from /lib/x86_64-linux-gnu/libc.so.6
#2  0x00007ffff705548a in ?? () from /lib/x86_64-linux-gnu/libc.so.6
#3  0x00007ffff7055502 in __assert_fail () from /lib/x86_64-linux-gnu/libc.so.6
#4  0x00007ffff77655a7 in clspv::ComputeStructuredOrder (block=0x55555579c860, DT=0x5555557a7450, LI=..., order=0x7fffffffab00,
    visited=0x7fffffffaa70) at clspv/lib/ComputeStructuredOrder.cpp:58
#5  0x00007ffff776573b in clspv::ComputeStructuredOrder (block=0x55555579c6b0, DT=0x5555557a7450, LI=..., order=0x7fffffffab00,
    visited=0x7fffffffaa70) at clspv/lib/ComputeStructuredOrder.cpp:87
#6  0x00007ffff77c5563 in (anonymous namespace)::SPIRVProducerPass::PopulateStructuredCFGMaps (this=0x5555557ee9e0)
    at clspv/lib/SPIRVProducerPass.cpp:5667
#7  0x00007ffff77b31aa in (anonymous namespace)::SPIRVProducerPass::runOnModule (this=0x5555557ee9e0, M=...)
    at clspv/lib/SPIRVProducerPass.cpp:737
#8  0x00007ffff2bf9059 in (anonymous namespace)::MPPassManager::runOnModule (this=0x55555579dff0, M=...)
    at clspv/third_party/llvm/llvm/lib/IR/LegacyPassManager.cpp:1550
#9  0x00007ffff2bf4241 in llvm::legacy::PassManagerImpl::run (this=0x5555557a57b0, M=...)
    at clspv/third_party/llvm/llvm/lib/IR/LegacyPassManager.cpp:541
#10 0x00007ffff2bf98e3 in llvm::legacy::PassManager::run (this=0x7fffffffafe0, M=...)
    at clspv/third_party/llvm/llvm/lib/IR/LegacyPassManager.cpp:1677
#11 0x00007ffff785b6e7 in clspv::Compile (argc=4, argv=0x7fffffffdd68) at clspv/lib/Compiler.cpp:941
#12 0x00005555555547ca in main (argc=4, argv=0x7fffffffdd68) at clspv/tools/driver/main.cpp:18

Reading https://www.khronos.org/registry/spir-v/specs/unified1/SPIRV.html#StructuredControlFlow I'm not sure this construct can be supported. However, clspv should not crash but instead report an error if that's the case.

(This issue and #702 may be duplicate, but I was not able to get 100% confidence that's the case.)

[FROL256]

I'm not sure this construct can be supported. However, clspv should not crash but instead report an error if that's the case.

Could you please advice what exactly is not supported while() -> break? I may try transform it to do {} while or just while(someFlag) construct ... but it also didn't work for me last time. Will try with the new clspv version.

[mantognini]

I'm not very familiar with SPIR-V structured control flow, but if I read the spec correctly:

SPIR-V can explicitly declare structured control-flow constructs using merge instructions. These explicitly declare a header block before the control flow diverges and a merge block where control flow subsequently converges. These blocks delimit constructs that must nest, and must be entered and exited in structured ways, as per the following.

then this statement implies a loop must have an exit. In other words, while (true) { ... no breaks ... } cannot be represented in SPIR-V.

(I don't know about your particular setup in #702 so I cannot fully judge whether the problem is the same. It might help to have the backtraces of the crashes you've mentioned.)

[GabeRundlett]

I beleive we are running into this as well. Here's a simple repro: https://godbolt.org/z/bYhWqTYdx