[WebAssembly] Handle unstackified TEE dest in ExplicitLocals

[aheejin]

Summary

When created in RegStackify pass, tee has two destinations, where
operand 0 is stackified and operand 1 is not. But it is possible that
operand 0 is unstackified in fixUnwindMismatches function in CFGStackify
pass when a nested try-catch-end is introduced. In this case,
local.tee has lost its purpose, so we generate local.tee as planned
when op0 remains stackified, and generate local.set instead if op0 got
unstackified.

Related explanation in RegStackify: https://github.com/llvm/llvm-project/blob/339177d1da0c6f0cf181ba987836148acb526926/llvm/lib/Target/WebAssembly/WebAssemblyRegStackify.cpp#L611-L630

For example,

1. In RegStackify. (r0 is stackified and r1 is not)

r0, r1 = tee defreg
... use r0 ...
... use r1 ...

2. In CFGStackify, r0 may get unstackified

3. In ExplicitLocals,

3-a. If r0 remains stackified, use local.tee as planned:

r0 = local.tee N defreg
...
... use r0 ... (from stackified r0)
...
local.get N
... use r1 ... (from local.get N)

3-b. If r0 got unstackified, use local.set instead:

local.set N defrag
...
local.get N
... use r0 ... (from local.get N)
local.get N
... use r1 ... (from local.get N)

[aheejin]

• Fix typo in comment

[dschuff]

(I'll use the term "de-stackify" as a verb to avoid confusion).
If fixUnwindMismatches de-stackifies the tee result, does that violate some kind of invariant? is it better to fix it up in fixUnwindMismatches?

llvm/lib/Target/WebAssembly/WebAssemblyExplicitLocals.cpp

277

does this mean that fixUnwindMismatches makes it unstackified or that it's already unstackified when fixUnwindMismatches runs?
edit:
I think it means the former, so maybe this could say "operand 0 becomes unstackified" instead. I guess this is all because "unstackified" could be a noun or a verb.... thanks English...

[aheejin]

In D81758#2090825, @dschuff wrote:

(I'll use the term "de-stackify" as a verb to avoid confusion).

The relevant function name in CFGStackify is unstackifyVRegsUsedInSplitBB. Do you think this is better to be renamed to destackify- as well?

If fixUnwindMismatches de-stackifies the tee result, does that violate some kind of invariant? is it better to fix it up in fixUnwindMismatches?

That unstackifying behavior was added in D68218. This happens because, for example,

bb0:
  r0, r1 = tee defreg
  ...
  call @bar
  ...
  use stackified r0

This basic block can be split while we introduce inner try-catch for call @bar, in case its unwind destination mismatches. Then this becomes something like

bb0:
  r0, r1 = tee defreg
  ...
  try
  call @bar

bb1:
  catch
  ...

bb2:
  end_try
  ...
  use stackified r0??

We do register stackification only within a BB, so r0 cannot be stackified at this point. This is the reason why we unstackify it there. I don't think we can fix it in fixUnwindMismatches as long as we split BBs there.

Not sure what you mean by the invariant, but that means if one of tee's dest is stackified and the other is not, that violation can't be avoided because of the reason above. Where we check and deal with that invariant is ExplicitLocals, which this CL fixes.

llvm/lib/Target/WebAssembly/WebAssemblyExplicitLocals.cpp

277

Yeah it means former. Changed to 'becomes' as you suggested. And.. isn't it an adjective or a verb..?

[aheejin]

• is -> gets / becomes

[dschuff]

Maybe we could keep using "unstackify" as a verb and use "non-stackified" as an adjective. I like that better than "destackify" anyway.

Not sure what you mean by the invariant, but that means if one of tee's dest is stackified and the other is not, that violation can't be avoided because of the reason above. Where we check and deal with that invariant is ExplicitLocals, which this CL fixes.

Yeah, I would think that anytime there is a tee, one of its dest would be stackified, because that's the point of having a tee in the first place.

I get that we have to do the BB-splitting you mentioned. Would it be possible to replace the tee with a copy?
e.g.

bb0:
  r0 = copy defreg
  ... use defreg (instead of r1)
  try:
  call @bar

...
use use non-stackified r0

or if that's not possible, maybe even inserting a copy directly after the tee that immediately consumes the stackified r0 and sets a non-stackified reg would be ok, since the final result (after copies are eliminated) should probably be the same.

llvm/lib/Target/WebAssembly/WebAssemblyExplicitLocals.cpp

277

Yeah, I'm just saying it could be used as either, which is what can make things confusing.

[aheejin]

Closing in favor of D81851.

llvm/lib/Target/WebAssembly/WebAssemblyExplicitLocals.cpp

for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E;) {
         Changed = true;
         continue;
       }
 
       // Replace tee instructions with local.tee. The difference is that tee
       // instructions have two defs, while local.tee instructions have one def
       // and an index of a local to write to.
       if (WebAssembly::isTee(MI.getOpcode())) {
-        assert(MFI.isVRegStackified(MI.getOperand(0).getReg()));
         assert(!MFI.isVRegStackified(MI.getOperand(1).getReg()));
         Register OldReg = MI.getOperand(2).getReg();
         const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
 
         // Stackify the input if it isn't stackified yet.
         if (!MFI.isVRegStackified(OldReg)) {
           unsigned LocalId = getLocalId(Reg2Local, MFI, CurLocal, OldReg);
           Register NewReg = MRI.createVirtualRegister(RC);
           unsigned Opc = getLocalGetOpcode(RC);
           BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(Opc), NewReg)
               .addImm(LocalId);
           MI.getOperand(2).setReg(NewReg);
           MFI.stackifyVReg(NewReg);
         }
 
         // Replace the TEE with a LOCAL_TEE.
         unsigned LocalId =
             getLocalId(Reg2Local, MFI, CurLocal, MI.getOperand(1).getReg());
+
+        // When created in RegStackify pass, TEE has two destinations, where
+        // operand 0 gets stackified and operand 1 is not. But it is possible
+        // that operand 0 becomes unstackified in fixUnwindMismatches function
+        // in CFGStackify pass when a nested try-catch-end is introduced. In
+        // this case, LOCAL_TEE has lost its purpose, so we generate LOCAL_TEE
+        // as planned when op0 remains stackified, and generate LOCAL_SET
+        // instead if op0 got unstackified.
+        if (MFI.isVRegStackified(MI.getOperand(0).getReg())) {
           unsigned Opc = getLocalTeeOpcode(RC);
           BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(Opc),
                   MI.getOperand(0).getReg())
               .addImm(LocalId)
               .addReg(MI.getOperand(2).getReg());
+        } else {
+          unsigned Opc = getLocalSetOpcode(RC);
+          BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(Opc))
+              .addImm(LocalId)
+              .addReg(MI.getOperand(2).getReg());
+          MRI.replaceRegWith(MI.getOperand(0).getReg(),
+                             MI.getOperand(1).getReg());
+        }
 
         WebAssemblyDebugValueManager(&MI).replaceWithLocal(LocalId);
 
         MI.eraseFromParent();
         Changed = true;
         continue;
       }
 

llvm/test/CodeGen/WebAssembly/cfg-stackify-eh.ll

 ; REQUIRES: asserts
 ; RUN: llc < %s -disable-wasm-fallthrough-return-opt -wasm-disable-explicit-locals -wasm-keep-registers -disable-block-placement -verify-machineinstrs -fast-isel=false -machine-sink-split-probability-threshold=0 -cgp-freq-ratio-to-skip-merge=1000 -exception-model=wasm -mattr=+exception-handling | FileCheck %s
 ; RUN: llc < %s -disable-wasm-fallthrough-return-opt -disable-block-placement -verify-machineinstrs -fast-isel=false -machine-sink-split-probability-threshold=0 -cgp-freq-ratio-to-skip-merge=1000 -exception-model=wasm -mattr=+exception-handling
 ; RUN: llc < %s -O0 -disable-wasm-fallthrough-return-opt -wasm-disable-explicit-locals -wasm-keep-registers -verify-machineinstrs -exception-model=wasm -mattr=+exception-handling | FileCheck %s --check-prefix=NOOPT
 ; RUN: llc < %s -disable-wasm-fallthrough-return-opt -wasm-disable-explicit-locals -wasm-keep-registers -disable-block-placement -verify-machineinstrs -fast-isel=false -machine-sink-split-probability-threshold=0 -cgp-freq-ratio-to-skip-merge=1000 -exception-model=wasm -mattr=+exception-handling -wasm-disable-ehpad-sort | FileCheck %s --check-prefix=NOSORT
+; RUN: llc < %s -disable-wasm-fallthrough-return-opt -disable-block-placement -verify-machineinstrs -fast-isel=false -machine-sink-split-probability-threshold=0 -cgp-freq-ratio-to-skip-merge=1000 -exception-model=wasm -mattr=+exception-handling -wasm-disable-ehpad-sort | FileCheck %s --check-prefix=NOSORT-LOCALS
 ; RUN: llc < %s -disable-wasm-fallthrough-return-opt -wasm-disable-explicit-locals -wasm-keep-registers -disable-block-placement -verify-machineinstrs -fast-isel=false -machine-sink-split-probability-threshold=0 -cgp-freq-ratio-to-skip-merge=1000 -exception-model=wasm -mattr=+exception-handling -wasm-disable-ehpad-sort -stats 2>&1 | FileCheck %s --check-prefix=NOSORT-STAT
 
 target datalayout = "e-m:e-p:32:32-i64:64-n32:64-S128"
 target triple = "wasm32-unknown-unknown"
 
 @_ZTIi = external constant i8*
 @_ZTId = external constant i8*
 
catch.start0:                                     ; preds = %catch.dispatch0
   %3 = call i8* @llvm.wasm.get.exception(token %2)
   %j = call i32 @llvm.wasm.get.ehselector(token %2)
   catchret from %2 to label %try.cont
 
 try.cont:                                         ; preds = %catch.start0
   ret i32 0
 }
 
+; Tests the case when TEE stackifies a register in RegStackify but it gets
+; unstackified in fixUnwindMismatches in CFGStackify.
+
+; NOSORT-LOCALS-LABEL: test8
+define void @test8(i32 %x) personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
+bb0:
+  invoke void @foo()
+          to label %bb1 unwind label %catch.dispatch0
+
+bb1:                                              ; preds = %bb0
+  %t = add i32 %x, 4
+  ; This %addr is used in multiple places, so TEE is introduced in RegStackify,
+  ; which stackifies the use of %addr in store instruction. But in
+  ; fixUnwindMismatches in CFGStackify, we introduce a nested try-catch around
+  ; call @baz, splitting this BB and unstackifing store's %addr operand. In this
+  ; case, in ExplicitLocals, we should convert TEE to not local.tee but
+  ; local.set, because there's no stackified operand anymore.
+  %addr = inttoptr i32 %t to i32*
+  %load = load i32, i32* %addr
+  %call = call i32 @baz()
+  %add = add i32 %load, %call
+  store i32 %add, i32* %addr
+  ret void
+; NOSORT-LOCALS:       i32.add
+; NOSORT-LOCALS-NOT:   local.tee  0
+; NOSORT-LOCALS-NEXT:  local.set  0
+
+catch.dispatch0:                                  ; preds = %bb0
+  %0 = catchswitch within none [label %catch.start0] unwind to caller
+
+catch.start0:                                     ; preds = %catch.dispatch0
+  %1 = catchpad within %0 [i8* null]
+  %2 = call i8* @llvm.wasm.get.exception(token %1)
+  %3 = call i32 @llvm.wasm.get.ehselector(token %1)
+  catchret from %1 to label %try.cont
+
+try.cont:                                         ; preds = %catch.start0
+  ret void
+}
+
 ; If not for the unwind destination mismatch, the LOOP marker here would have an
 ; i32 signature. But because we add a rethrow instruction at the end of the
 ; appendix block, now the LOOP marker does not have a signature (= has a void
 ; signature). Here the two calls two 'bar' are supposed to throw up to the
 ; caller, but incorrectly unwind to 'catch19' after linearizing the CFG.
 
-; NOSORT-LABEL: test8
+; NOSORT-LABEL: test9
 ; NOSORT: block
 ; NOSORT-NOT: loop      i32
-; NOSORT:   loop                                       # label40:
+; NOSORT:   loop                                       # label42:
 ; NOSORT:     try
 ; NOSORT:       call      foo
 ; --- Nested try/catch/end_try starts
 ; NOSORT:       try
 ; NOSORT:         call      bar
 ; NOSORT:         call      bar
 ; NOSORT:       catch     $[[REG:[0-9]+]]=
-; NOSORT:         br        1                          # 1: down to label41
+; NOSORT:         br        1                          # 1: down to label43
 ; NOSORT:       end_try
 ; --- Nested try/catch/end_try ends
 ; NOSORT:       return    {{.*}}
-; NOSORT:     catch     $drop=                         # catch21:
-; NOSORT:       br        1                            # 1: up to label40
-; NOSORT:     end_try                                  # label41:
+; NOSORT:     catch     $drop=                         # catch23:
+; NOSORT:       br        1                            # 1: up to label42
+; NOSORT:     end_try                                  # label43:
 ; NOSORT:   end_loop
 ; NOSORT: end_block
 ; NOSORT: rethrow   $[[REG]]                           # to caller
 
-define i32 @test8(i32* %p) personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
+define i32 @test9(i32* %p) personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
 entry:
   store volatile i32 0, i32* %p
   br label %loop
 
 loop:                                             ; preds = %try.cont, %entry
   store volatile i32 1, i32* %p
   invoke void @foo()
           to label %bb unwind label %catch.dispatch

 }
 
 ; When we have both kinds of EH pad unwind mismatches:
 ; - A may-throw instruction unwinds to an incorrect EH pad after linearizing the
 ;   CFG, when it is supposed to unwind to another EH pad.
 ; - A may-throw instruction unwinds to an incorrect EH pad after linearizing the
 ;   CFG, when it is supposed to unwind to the caller.
 
-; NOSORT-LABEL: test9
+; NOSORT-LABEL: test10
 ; NOSORT: block
 ; NOSORT:   block
 ; NOSORT:     try
 ; NOSORT:       try
 ; NOSORT:         call      foo
 ; --- Nested try/catch/end_try starts
 ; NOSORT:         try
 ; NOSORT:           call      bar
 ; NOSORT:         catch     $[[REG0:[0-9]+]]=
-; NOSORT:           br        2                        # 2: down to label45
+; NOSORT:           br        2                        # 2: down to label47
 ; NOSORT:         end_try
 ; --- Nested try/catch/end_try ends
-; NOSORT:         br        2                          # 2: down to label44
+; NOSORT:         br        2                          # 2: down to label46
 ; NOSORT:       catch     {{.*}}
 ; NOSORT:         block     i32
-; NOSORT:           br_on_exn   0, {{.*}}              # 0: down to label48
+; NOSORT:           br_on_exn   0, {{.*}}              # 0: down to label50
 ; --- Nested try/catch/end_try starts
 ; NOSORT:           try
-; NOSORT:             rethrow   {{.*}}                 # down to catch26
-; NOSORT:           catch     $[[REG1:[0-9]+]]=        # catch26:
-; NOSORT:             br        5                      # 5: down to label43
+; NOSORT:             rethrow   {{.*}}                 # down to catch28
+; NOSORT:           catch     $[[REG1:[0-9]+]]=        # catch28:
+; NOSORT:             br        5                      # 5: down to label45
 ; NOSORT:           end_try
 ; --- Nested try/catch/end_try ends
-; NOSORT:         end_block                            # label48:
+; NOSORT:         end_block                            # label50:
 ; NOSORT:         call      $drop=, __cxa_begin_catch
 ; --- Nested try/catch/end_try starts
 ; NOSORT:         try
 ; NOSORT:           call      __cxa_end_catch
 ; NOSORT:         catch     $[[REG1]]=
-; NOSORT:           br        4                        # 4: down to label43
+; NOSORT:           br        4                        # 4: down to label45
 ; NOSORT:         end_try
 ; --- Nested try/catch/end_try ends
-; NOSORT:         br        2                          # 2: down to label44
+; NOSORT:         br        2                          # 2: down to label46
 ; NOSORT:       end_try
 ; NOSORT:     catch     $[[REG0]]=
-; NOSORT:     end_try                                  # label45:
+; NOSORT:     end_try                                  # label47:
 ; NOSORT:     call      $drop=, __cxa_begin_catch
 ; NOSORT:     call      __cxa_end_catch
-; NOSORT:   end_block                                  # label44:
+; NOSORT:   end_block                                  # label46:
 ; NOSORT:   return
-; NOSORT: end_block                                    # label43:
+; NOSORT: end_block                                    # label45:
 ; NOSORT: rethrow   $[[REG1]]                          # to caller
-define void @test9() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
+define void @test10() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
 bb0:
   invoke void @foo()
           to label %bb1 unwind label %catch.dispatch0
 
 bb1:                                              ; preds = %bb0
   invoke void @bar()
           to label %try.cont unwind label %catch.dispatch1
 

 ; NOOPT: block
 ; NOOPT:   try
 ; NOOPT:     call      foo
 ; NOOPT:   catch
 ; NOOPT:   end_try
 ; NOOPT:   call      foo
 ; NOOPT: end_block
 ; NOOPT: return
-define void @test10(i32 %arg) personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
+define void @test11(i32 %arg) personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
 entry:
   %tobool = icmp ne i32 %arg, 0
   br i1 %tobool, label %if.then, label %if.end
 
 catch.dispatch:                                   ; preds = %if.then
   %0 = catchswitch within none [label %catch.start] unwind to caller
 
 catch.start:                                      ; preds = %catch.dispatch

 
 ; Intrinsics like memcpy, memmove, and memset don't throw and are lowered into
 ; calls to external symbols (not global addresses) in instruction selection,
 ; which will be eventually lowered to library function calls.
 ; Because this test runs with -wasm-disable-ehpad-sort, these library calls in
 ; invoke.cont BB fall within try~end_try, but they shouldn't cause crashes or
 ; unwinding destination mismatches in CFGStackify.
 
-; NOSORT-LABEL: test11
+; NOSORT-LABEL: test12
 ; NOSORT: try
 ; NOSORT:   call  foo
 ; NOSORT:   call {{.*}} memcpy
 ; NOSORT:   call {{.*}} memmove
 ; NOSORT:   call {{.*}} memset
 ; NOSORT:   return
 ; NOSORT: catch
 ; NOSORT:   rethrow
 ; NOSORT: end_try
-define void @test11(i8* %a, i8* %b) personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
+define void @test12(i8* %a, i8* %b) personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
 entry:
   %o = alloca %class.Object, align 1
   invoke void @foo()
           to label %invoke.cont unwind label %ehcleanup
 
 invoke.cont:                                      ; preds = %entry
   call void @llvm.memcpy.p0i8.p0i8.i32(i8* %a, i8* %b, i32 100, i1 false)
   call void @llvm.memmove.p0i8.p0i8.i32(i8* %a, i8* %b, i32 100, i1 false)
   call void @llvm.memset.p0i8.i32(i8* %a, i8 0, i32 100, i1 false)
   %call = call %class.Object* @_ZN6ObjectD2Ev(%class.Object* %o) #1
   ret void
 
 ehcleanup:                                        ; preds = %entry
   %0 = cleanuppad within none []
   %call2 = call %class.Object* @_ZN6ObjectD2Ev(%class.Object* %o) #1 [ "funclet"(token %0) ]
   cleanupret from %0 unwind to caller
 }
 
 ; Tests if 'try' marker is placed correctly. In this test, 'try' should be
 ; placed before the call to 'nothrow_i32' and not between the call to
 ; 'nothrow_i32' and 'fun', because the return value of 'nothrow_i32' is
 ; stackified and pushed onto the stack to be consumed by the call to 'fun'.
 
-; CHECK-LABEL: test12
+; CHECK-LABEL: test13
 ; CHECK: try
 ; CHECK: call      $push{{.*}}=, nothrow_i32
 ; CHECK: call      fun, $pop{{.*}}
-define void @test12() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
+define void @test13() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
 entry:
   %call = call i32 @nothrow_i32()
   invoke void @fun(i32 %call)
           to label %invoke.cont unwind label %terminate
 
 invoke.cont:                                      ; preds = %entry
   ret void
 
 terminate:                                        ; preds = %entry
   %0 = cleanuppad within none []
   %1 = tail call i8* @llvm.wasm.get.exception(token %0)
   call void @__clang_call_terminate(i8* %1) [ "funclet"(token %0) ]
   unreachable
 }
 
 %class.MyClass = type { i32 }
 
 ; This crashed on debug mode (= when NDEBUG is not defined) when the logic for
 ; computing the innermost region was not correct, in which a loop region
 ; contains an exception region. This should pass CFGSort without crashing.
-define void @test13() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
+define void @test14() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
 entry:
   %e = alloca %class.MyClass, align 4
   br label %for.cond
 
 for.cond:                                         ; preds = %for.inc, %entry
   %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
   %cmp = icmp slt i32 %i.0, 9
   br i1 %cmp, label %for.body, label %for.end
catch.start:                                      ; preds = %catch.dispatch
   call void @__cxa_end_catch() [ "funclet"(token %1) ]
   catchret from %1 to label %try.cont
 
 try.cont:                                         ; preds = %catch.start, %for.end
   ret void
 }
 
 ; Check if the unwind destination mismatch stats are correct
-; NOSORT-STAT: 16 wasm-cfg-stackify    - Number of EH pad unwind mismatches found
+; NOSORT-STAT: 17 wasm-cfg-stackify    - Number of EH pad unwind mismatches found
 
 declare void @foo()
 declare void @bar()
 declare i32 @baz()
 declare i32 @qux(i32)
 declare void @quux(i32)
 declare void @fun(i32)
 ; Function Attrs: nounwind