[WebAssembly] Don't analyze branches after CFGStackify

[aheejin]

Summary

WebAssembly::analyzeBranch now does not analyze anything if the
function is CFG stackified. We were previously doing similar things by
checking if a branch's operand is whether an integer or an MBB, but this
failed to bail out when a BB did not have any terminators.

Consider this case:

bb0:
  try $label0
  call @foo    // unwinds to %ehpad
bb1:
  ...
  br $label0   // jumps to %cont. can be deleted
ehpad:
  catch
  ...
cont:
  end_try

Here br $label0 will be deleted in CFGStackify's
removeUnnecessaryInstrs function, because we jump to the %cont block
even without the branch. But in this case, MachineVerifier fails to
verify this, because ehpad is not a successor of bb1 even if bb1
does not have any terminators. MachineVerifier incorrectly thinks bb1
falls through to the next block.

This pass now consistently rejects all analysis after CFGStackify
whether a BB has terminators or not, also making the MachineVerifier
work. (MachineVerifier does not try to verify relationships between BBs
if analyzeBranch fails, the behavior we want after CFGStackify.)

This also adds a new option -wasm-disable-ehpad-sort for testing. This
option helps create the sorted order we want to test, and without the
fix in this patch, the tests in cfg-stackify-eh.ll fail at
MachineVerifier with -wasm-disable-ehpad-sort.

[arsenm]

lib/Target/WebAssembly/WebAssemblyInstrInfo.cpp

106–107 ↗

(On Diff #192013)

I think this isn't what you want to do. analyzeBranch isn't really for turning off transformations. The verifier will stop catching useful cases with this

[aheejin]

lib/Target/WebAssembly/WebAssemblyInstrInfo.cpp

106–107 ↗

(On Diff #192013)

Please note that we were doing this already. (The part of the code I deleted)
CFGStackify is a pass near the end of WebAssembly compilation pipeline, and this pass deletes all MBB operands from branches to replace them with integers, and also deletes some other unnecessary instruction from WebAssembly standpoint, so after that it is not possible to analyze branch anyway. This patch is not introducing a new thing; it is rather filling in a hole, because we rejected analysis only when there were terminators and ignored the case of fall-throughs after CFGStackify.

[dschuff]

lib/Target/WebAssembly/WebAssemblyInstrInfo.cpp

106–107 ↗

(On Diff #192013)

I guess if we actually modeled the wasm control flow structure outside of the CFGStackify pass (e.g. the BeginToEnd mappings etc), then analyzeBranch could use them and it could return the correct successors. But since we don't yet, the control flow really is not analyzable by analyzeBranch and it should return false, right? And as a result any optimization or verification that depends on that can't run.

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

3 ↗

(On Diff #192013)

why does this CL now need the ehpad-sort option?

[dschuff]

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

3 ↗

(On Diff #192013)

nevermind, I re-read the CL description.

[aheejin]

lib/Target/WebAssembly/WebAssemblyInstrInfo.cpp

106–107 ↗

(On Diff #192013)

Not sure what you mean, but this function unintuitively returns false when it is analyzable, and true if not. Please refer to the description of its return values.

[dschuff]

lib/Target/WebAssembly/WebAssemblyInstrInfo.cpp

106–107 ↗

(On Diff #192013)

sorry yes, I meant that it should return true. I'm just saying I think that this behavior is probably consistent with the intention of analyzeBranch. Once it can no longer correctly determine the destination, analyzeBranch should fail.

[aheejin]

lib/Target/WebAssembly/WebAssemblyInstrInfo.cpp

106–107 ↗

(On Diff #192013)

I think that’s what this CL does..?

[dschuff]

lib/Target/WebAssembly/WebAssemblyInstrInfo.cpp

106–107 ↗

(On Diff #192013)

Yes; my statement was mostly just a reply to @arsenm to try to clarify what we are doing.

This CL looks fine to me; in any case it doesn't change what we are doing already.
WRT the comments, I think @arsenm's point is that if we want to prevent optimizations (as the comment in the code seems to indicate) then this isn't the way to do it because it also prevents verification. But I don't think that is actually what we are doing; in any case AFAIK there aren't any optimization passes that run after CFGStackify that try to reason about branches or the CFG, and we are controlling the pass order explicitly in WebAssemblyPassConfig. So maybe we should just clarify the comment to say something like "WebAssembly has control flow that doesn't have explicit branches or direct fallthrough (e.g. try/catch), which cant' be modeled by analyzeBranch. It is created after CFGStackify"

[aheejin]

• Add comment on CFGStackify

llvm/trunk/lib/Target/WebAssembly/WebAssemblyCFGSort.cpp

 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "wasm-cfg-sort"
 
+// Option to disable EH pad first sorting. Only for testing unwind destination
+// mismatches in CFGStackify.
+static cl::opt<bool> WasmDisableEHPadSort(
+    "wasm-disable-ehpad-sort", cl::ReallyHidden,
+    cl::desc(
+        "WebAssembly: Disable EH pad-first sort order. Testing purpose only."),
+    cl::init(false));
+
 namespace {
 
 // Wrapper for loops and exceptions
 class Region {
 public:
   virtual ~Region() = default;
   virtual MachineBasicBlock *getHeader() const = 0;
   virtual bool contains(const MachineBasicBlock *MBB) const = 0;

 //
 // If we give a higher priority to an EH pad whenever it is ready in this
 // example, when both bb1 and bb2 are ready, we would pick up bb2 first.
 
 /// Sort blocks by their number.
 struct CompareBlockNumbers {
   bool operator()(const MachineBasicBlock *A,
                   const MachineBasicBlock *B) const {
+    if (!WasmDisableEHPadSort) {
       if (A->isEHPad() && !B->isEHPad())
         return false;
       if (!A->isEHPad() && B->isEHPad())
         return true;
+    }
 
     return A->getNumber() > B->getNumber();
   }
 };
 /// Sort blocks by their number in the opposite order..
 struct CompareBlockNumbersBackwards {
   bool operator()(const MachineBasicBlock *A,
                   const MachineBasicBlock *B) const {
-    // We give a higher priority to an EH pad
+    if (!WasmDisableEHPadSort) {
       if (A->isEHPad() && !B->isEHPad())
         return false;
       if (!A->isEHPad() && B->isEHPad())
         return true;
+    }
 
     return A->getNumber() < B->getNumber();
   }
 };
 /// Bookkeeping for a region to help ensure that we don't mix blocks not
 /// dominated by the its header among its blocks.
 struct Entry {
   const Region *TheRegion;

llvm/trunk/lib/Target/WebAssembly/WebAssemblyInstrInfo.cpp

 }
 
 // Branch analysis.
 bool WebAssemblyInstrInfo::analyzeBranch(MachineBasicBlock &MBB,
                                          MachineBasicBlock *&TBB,
                                          MachineBasicBlock *&FBB,
                                          SmallVectorImpl<MachineOperand> &Cond,
                                          bool /*AllowModify*/) const {
+  const auto &MFI = *MBB.getParent()->getInfo<WebAssemblyFunctionInfo>();
+  // WebAssembly has control flow that doesn't have explicit branches or direct
+  // fallthrough (e.g. try/catch), which can't be modeled by analyzeBranch. It
+  // is created after CFGStackify.
+  if (MFI.isCFGStackified())
+    return true;
+
   bool HaveCond = false;
   for (MachineInstr &MI : MBB.terminators()) {
     switch (MI.getOpcode()) {
     default:
       // Unhandled instruction; bail out.
       return true;
     case WebAssembly::BR_IF:
       if (HaveCond)
         return true;
-      // If we're running after CFGStackify, we can't optimize further.
-      if (!MI.getOperand(0).isMBB())
-        return true;
       Cond.push_back(MachineOperand::CreateImm(true));
       Cond.push_back(MI.getOperand(1));
       TBB = MI.getOperand(0).getMBB();
       HaveCond = true;
       break;
     case WebAssembly::BR_UNLESS:
       if (HaveCond)
         return true;
-      // If we're running after CFGStackify, we can't optimize further.
-      if (!MI.getOperand(0).isMBB())
-        return true;
       Cond.push_back(MachineOperand::CreateImm(false));
       Cond.push_back(MI.getOperand(1));
       TBB = MI.getOperand(0).getMBB();
       HaveCond = true;
       break;
     case WebAssembly::BR:
-      // If we're running after CFGStackify, we can't optimize further.
-      if (!MI.getOperand(0).isMBB())
-        return true;
       if (!HaveCond)
         TBB = MI.getOperand(0).getMBB();
       else
         FBB = MI.getOperand(0).getMBB();
       break;
     case WebAssembly::BR_ON_EXN:
       if (HaveCond)
         return true;
-      // If we're running after CFGStackify, we can't optimize further.
-      if (!MI.getOperand(0).isMBB())
-        return true;
       Cond.push_back(MachineOperand::CreateImm(true));
       Cond.push_back(MI.getOperand(2));
       TBB = MI.getOperand(0).getMBB();
       HaveCond = true;
       break;
     }
     if (MI.isBarrier())
       break;

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

 ; 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 -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
 
 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*
 
 ; Simple test case with two catch clauses