[SPIR-V] sortBlocks() hangs for irreducible CFGs

[VyacheslavLevytskyy]

The following reproducer causes sortBlocks() to loop without ending:

@G2 = internal unnamed_addr addrspace(3) global ptr addrspace(4) undef, align 8

define weak_odr dso_local spir_kernel void @foo(ptr addrspace(4) %p, i1 %f1, i1 %f2, i1 %f3) {
entry:
  br label %l0

l0:
  br label %l2

l2:
  %val2 = phi ptr addrspace(4) [ %p, %l0 ], [ %val3, %l3 ]
  br i1 %f2, label %l1, label %l3

l1:
  %val1 = phi ptr addrspace(4) [ %p, %l3 ], [ %val2, %l2 ]
  br i1 %f1, label %exit, label %l3

l3:
  %val3 = load ptr addrspace(4), ptr addrspace(3) @G2, align 8
  br i1 %f3, label %l1, label %l2

exit:
  ret void
}

CC: @Keenuts

[Keenuts]

Hi! Thanks for the repro!

This CFG is irreducible if I'm correct. Thus the topological sort is not possible to determine, and it hangs because it cannot decide what node to start with in the loop.

For DXC/HLSL, we had a simple way to handle that: assert(0 && 'CFG is irreducible'). Are irreducible CFG something common in OpenCL?

[VyacheslavLevytskyy]

Hi! Thanks for the repro!

This CFG is irreducible if I'm correct. Thus the topological sort is not possible to determine, and it hangs because it cannot decide what node to start with in the loop.

For DXC/HLSL, we had a simple way to handle that: assert(0 && 'CFG is irreducible'). Are irreducible CFG something common in OpenCL?

Yes, I understand that CFG is not a normal or expected one. It's not common in OpenCL as well.

Probably it's better to don't try to sort blocks in that case that to fire an error though. IMO it's better to let common llvm passes to do their work, eliminating unreachable BB's or anything related, but sorting of blocks inside of SPIR-V Backend looks more like a best effort than a precondition to proceed with translation further. If this is indeed a precondition for some further steps, an error can be fired later, at the beginning of the step that requires sorted blocks to succeed. What do you think?

[Keenuts]

It looks like I may be able to use a mix of LowerSwitchPass and FixIrreducible before handling structurizing/sorting, but I agree, an error is better than the crash.

On another bit, It looks like it is valid to generate a SPIR-V module with an irreducible CFG for OpenCL SPIR-V, so I shall make sure the sortBlock method can handle that.