[WebAssembly] Lower llvm.debugtrap properly

[tlively]

Summary

Unlike normal traps, debug traps are allowed to return and can have
additional instructions in the same basic block. Without explicit
backend support for debug traps, they are lowered in ISel as normal
traps. Since normal traps are lowered in the WebAssembly backend to
the UNREACHABLE instruction, which is a terminator, using debug traps
could lead to invalid MBBs when there are additional instructions
after the trap. This patch fixes the issue by lowering debug traps to
a new version of the UNREACHABLE instruction, DEBUG_UNREACHABLE, that
is not a terminator.

An alternative approach would have been to make UNREACHABLE not a
terminator, but that breaks a large number of tests. In particular, it
would require removing the traps inserted after noreturn calls to
@llvm.wasm.throw because otherwise the terminator throw would be
followed by a non-terminator UNREACHABLE and we would be back to
having invalid MBBs. Overall the approach in this patch seems simpler.

[aheejin]

I'm not very familiar with how wasm debugger works, but do they use unreachable for breakpoints? Binaryen assumes unreachable is really unreachable and does all sorts of optimizations including DCE and everything, so if unreachable is actually used in debugger, that seems risky..?

[tlively]

In D81055#2071862, @aheejin wrote:

I'm not very familiar with how wasm debugger works, but do they use unreachable for breakpoints? Binaryen assumes unreachable is really unreachable and does all sorts of optimizations including DCE and everything, so if unreachable is actually used in debugger, that seems risky..?

No, WebAssembly does not any sort of debugger instruction (although JS does). On other targets without dedicated debugger instructions, debugtrap is lowered to a normal trap, so that is what we are doing here. In fact, there is target-independent code to automatically change debug traps to normal traps before ISel when debugtrap is not supported. So this is the correct lowering to do, given that we don't have a debugger instruction. The reason the target-independent mechanism doesn't work for us is that it assumes the trap will lower to a non-terminator instruction.

[dschuff]

Binaryen doesn't assume an unreachable is actually unreachable, the way C compilers do, does it? (and remove code before the unreachable)? I think it just knows that instructions that come after it are unreachable and removes those. I think it's ok once it's lowered to wasm unreachable; it really won't be able to return (and so Binaryen can do DCE), but that seems like a legit behavior for @llvm.debugtrap according to the langref.

[tlively]

In D81055#2072399, @dschuff wrote:

Binaryen doesn't assume an unreachable is actually unreachable, the way C compilers do, does it? (and remove code before the unreachable)? I think it just knows that instructions that come after it are unreachable and removes those. I think it's ok once it's lowered to wasm unreachable; it really won't be able to return (and so Binaryen can do DCE), but that seems like a legit behavior for @llvm.debugtrap according to the langref.

Agreed.

[aheejin]

In D81055#2072399, @dschuff wrote:

Binaryen doesn't assume an unreachable is actually unreachable, the way C compilers do, does it? (and remove code before the unreachable)? I think it just knows that instructions that come after it are unreachable and removes those. I think it's ok once it's lowered to wasm unreachable; it really won't be able to return (and so Binaryen can do DCE), but that seems like a legit behavior for @llvm.debugtrap according to the langref.

Yeah you're right. I was confused; Binaryen's DCE only removes the code after unreachable is unreachable. But doesn't debugtrap instruction expect the control flow to return? That's why I was wondering if we can translate debugtrap to unreachable.

[tlively]

In D81055#2072648, @aheejin wrote:

Yeah you're right. I was confused; Binaryen's DCE only removes the code after unreachable is unreachable. But doesn't debugtrap instruction expect the control flow to return? That's why I was wondering if we can translate debugtrap to unreachable.

debugtrap allows control flow to return. It is ok if it doesn't return or if it is lowered to something that can't return.

[aheejin]

I see. Thanks for the explanation.

llvm/lib/Target/WebAssembly/WebAssemblyISelLowering.cpp

if (Subtarget->hasSIMD128()) {
     }
   }
 
   // Don't do anything clever with build_pairs
   setOperationAction(ISD::BUILD_PAIR, MVT::i64, Expand);
 
   // Trap lowers to wasm unreachable
   setOperationAction(ISD::TRAP, MVT::Other, Legal);
+  setOperationAction(ISD::DEBUGTRAP, MVT::Other, Legal);
 
   // Exception handling intrinsics
   setOperationAction(ISD::INTRINSIC_WO_CHAIN, MVT::Other, Custom);
   setOperationAction(ISD::INTRINSIC_VOID, MVT::Other, Custom);
 
   setMaxAtomicSizeInBitsSupported(64);
 
   // Override the __gnu_f2h_ieee/__gnu_h2f_ieee names so that the f32 name is

llvm/lib/Target/WebAssembly/WebAssemblyInstrControl.td

 // Generic instruction, for disassembler.
 let IsCanonical = 1 in
 defm END       : NRI<(outs), (ins), [], "end", 0x0b>;
 let isTerminator = 1, isBarrier = 1 in
 defm END_FUNCTION : NRI<(outs), (ins), [], "end_function", 0x0b>;
 } // Uses = [VALUE_STACK], Defs = [VALUE_STACK]
 
 
-let isTerminator = 1, hasCtrlDep = 1, isBarrier = 1 in {
-
+let hasCtrlDep = 1, isBarrier = 1 in {
+let isTerminator = 1 in {
 let isReturn = 1 in {
 
 defm RETURN : I<(outs), (ins variable_ops), (outs), (ins),
                 [(WebAssemblyreturn)],
                 "return", "return", 0x0f>;
 // Equivalent to RETURN, for use at the end of a function when wasm
 // semantics return by falling off the end of the block.
 let isCodeGenOnly = 1 in
 defm FALLTHROUGH_RETURN : I<(outs), (ins variable_ops), (outs), (ins), []>;
 
 } // isReturn = 1
 
+let isTrap = 1 in
 defm UNREACHABLE : NRI<(outs), (ins), [(trap)], "unreachable", 0x00>;
-} // isTerminator = 1, hasCtrlDep = 1, isBarrier = 1
+
+} // isTerminator = 1
+
+// debugtrap explicitly returns despite trapping because it is supposed to just
+// get the attention of the debugger. Unfortunately, because UNREACHABLE is a
+// terminator, lowering debugtrap to UNREACHABLE can create an invalid
+// MachineBasicBlock when there is additional code after it. Lower it to this
+// non-terminator version instead.
+// TODO: Actually execute the debugger statement when running on the Web
+let isTrap = 1 in
+defm DEBUG_UNREACHABLE : NRI<(outs), (ins), [(debugtrap)], "unreachable", 0x00>;
+
+} // hasCtrlDep = 1, isBarrier = 1
 
 //===----------------------------------------------------------------------===//
 // Exception handling instructions
 //===----------------------------------------------------------------------===//
 
 let Predicates = [HasExceptionHandling] in {
 
 // Throwing an exception: throw / rethrow

llvm/test/CodeGen/WebAssembly/debugtrap.ll

+; RUN: llc < %s -asm-verbose=false -verify-machineinstrs | FileCheck %s
+
+; Test lowering of __builtin_debugtrap in cases where lowering it via
+; the normal UNREACHABLE instruction would yield invalid
+; MachineFunctions.
+
+target datalayout = "e-m:e-p:32:32-i64:64-n32:64-S128"
+target triple = "wasm32"
+
+declare void @llvm.debugtrap()
+
+; CHECK-LABEL: foo:
+; CHECK-NEXT: .functype       foo (i32) -> ()
+; CHECK-NEXT: .LBB0_1:
+; CHECK-NEXT: loop
+; CHECK-NEXT: unreachable
+; CHECK-NEXT: i32.const       0
+; CHECK-NEXT: br_if           0
+; CHECK-NEXT: end_loop
+; CHECK-NEXT: end_function
+define void @foo(i32 %g) {
+entry:
+  br label %for.body
+
+for.body:
+  call void @llvm.debugtrap()
+  %exitcond = icmp eq i32 undef, %g
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+
+for.cond.cleanup:
+  ret void
+}
+
+; CHECK-LABEL: middle_of_block:
+; CHECK-NEXT: .functype       middle_of_block (i32, i32) -> (i32)
+; CHECK-NEXT: unreachable
+; CHECK-NEXT: local.get       0
+; CHECK-NEXT: local.get       1
+; CHECK-NEXT: i32.add
+; CHECK-NEXT: end_function
+define i32 @middle_of_block(i32 %x, i32 %y) {
+  %r = add i32 %x, %y
+  call void @llvm.debugtrap()
+  ret i32 %r
+}
+
+; CHECK-LABEL: really_middle_of_block:
+; CHECK-NEXT: .functype       really_middle_of_block () -> (i32)
+; CHECK-NEXT: call    bar
+; CHECK-NEXT: drop
+; CHECK-NEXT: unreachable
+; CHECK-NEXT: call    bar
+; CHECK-NEXT: end_function
+declare i32 @bar()
+define i32 @really_middle_of_block() {
+  %x = call i32 @bar()
+  call void @llvm.debugtrap()
+  %r = call i32 @bar()
+  ret i32 %r
+}