[WebAssembly] Eliminate range checks on br_tables

[tlively]

Summary

Jump tables for most targets cannot handle out of range indices by
themselves, so LLVM emits range checks to guard the jump
tables. WebAssembly, on the other hand, implements jump tables using
the br_table instruction, which takes a default branch target as an
operand, making the range checks redundant. This patch introduces a
new MachineFunction pass in the WebAssembly backend to find and
eliminate the redundant range checks.

[tlively]

• Update documentation and handle unreachable target blocks

[sbc100]

llvm/lib/Target/WebAssembly/WebAssemblyFixBrTableDefaults.cpp

120

Lies!

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

652–654

Can this be CHECK-NEXT too now? So we know the br_if is not there?

llvm/test/CodeGen/WebAssembly/switch-unreachable-default.ll

8

So if the default label contains unreachable then we end up in some special case where that target doesn't actually exist in the final output, and we instead just arbitrarily jump to any other the labels?

Is this standard llvm behaviour? Is is that default target in this case eliminated by some earlier pass?

[aheejin]

I didn't know about this optimization opportunity! Please make sure to run emscripten tests before landing because it contains some new assumptions.

llvm/lib/Target/WebAssembly/WebAssemblyFixBrTableDefaults.cpp

46

Nit: It might help readers if there's a comment that prior to this function, br_table is missing the last (= default) operand, which will be added here

48

Nit: This might be more intuitive:

assert(MBB->pred_size() == 1);

By the way, is it guaranteed that we always have a single predecessor that is a guard BB, which ends with a conditional branch when the default BB is reachable and no branch when it is unreachable? Are other patterns possible?

60

Is this guaranteed that br_table BB is always a fallthrough, so the operand 0 is the default target? Can they be swapped?

65

Would there be performance implications based on what we choose arbitrarily for the default target, in case there's no guard hints? (I don't know and I'm just asking) If we are unsure, can it be safer to choose the first one, as we are doing now?

76

Why is this process (checking if Succ is a successor of HeaderMBB and deleting it from the successors) necessary?

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

652–654

Or we can explicitly check if it's not there, like

CHECK-NOT: br_if ...

[aheejin]

llvm/lib/Target/WebAssembly/WebAssemblyFixBrTableDefaults.cpp

60

If it is somehow guaranteed, it is fine, but if we are unsure, we can compare br_if's argument to MBB to figure it out.

[tlively]

• Address comments

[tlively]

llvm/lib/Target/WebAssembly/WebAssemblyFixBrTableDefaults.cpp

46

Done.

48

Done.

There is always a single guard BB that contains a conditional branch to the default target if the default target exists. Then the guard BB either falls through or has an unconditional jump to the jump table BB.

60

They would only be swapped if something in between SelectionDAG building and this pass swapped them, but I'll add an assert in case some later change swaps the order.

65

I suppose it might affect register allocation or something, but I'm not sure. I'll switch to using the first target.

76

We need to remove the shared successors first because otherwise transferSuccessorsAndUpdatePHIs could introduce duplicate successors, which is invalid. I'll add a comment to that effect.

120

Oops!

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

652–654

Used the CHECK-NOT because IIRC there's a bunch of extra junk in there preventing us from using CHECK-NEXT.

llvm/test/CodeGen/WebAssembly/switch-unreachable-default.ll

8

Correct. The target-independent code doesn't emit any jump to a default target to begin with when the default is unreachable, so on other targets if the default did turn out to be reachable at runtime, then there would be an out-of-bounds access to the jump table.

The relevant code that creates the jump to the default block is here: https://github.com/llvm/llvm-project/blob/f027cfa37e6757bb2d17ac3bea944df4e06bcff4/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp#L2475-L2482.

[kcc]

Hi, 
This made our ubsan bots red. Please fix or revert ASAP
http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-fast/builds/42256

[uabelho]

In D80863#2070105, @kcc wrote:

Hi, 
This made our ubsan bots red. Please fix or revert ASAP
http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-fast/builds/42256

Same for our downstream bots. When we build llc with gcc 7.4 we get crashes when running the following tests:

08:01:10 Failing Tests (5):
08:01:10 LLVM :: CodeGen/WebAssembly/cfg-stackify.ll
08:01:10 LLVM :: CodeGen/WebAssembly/indirectbr.ll
08:01:10 LLVM :: CodeGen/WebAssembly/stack-insts.ll
08:01:10 LLVM :: CodeGen/WebAssembly/switch-unreachable-default.ll
08:01:10 LLVM :: CodeGen/WebAssembly/switch.ll

[tlively]

For some reason I have not been able to reproduce these failure locally. I am reverting the change pending further investigation. @kcc what compiler version is your bot using?

[paolosev]

I was testing the performance of a program with a big switch statement in a loop, a very common pattern in C/C++ and I came across the problem with needless range checks with br_table that this patch is fixing (Sweet! :-))
However, testing the latest version of Emscripten, with this fix, I am finding that Clang now emits "worse" bytecode for my small test program (attached{F12106893}, compiled with emcc -O3 micro-interp.c -o micro-interp.js).
The code is like:

enum Op {
    A = 0, B, C, D, E, F, G, H, I, J, K, L
};
int f(Op* ops, int len) {
    int result = 0;
    for (int i = 0; i < len; i++) {
        Op op = ops[i];
        switch (op) {
            case A: { ... break; }
            case B: { ... break; }
            case C: { ... break; }
		...
            default: { ... break; }
        }
    }
    return result;
}

Before this change, the function was compiled into this Wasm code, with a single br_table that was not using its default label (see WAT file attached:

emcc-0-base.OLD.wat166 KBDownload

):

(func (;11;) (type 2) (param i32)
  (local i32 i32 i32 i32 i32 i64)
  ...
  block  ;; label = @1
    block  ;; label = @2
      loop  ;; label = @3
        local.get 4
        i32.load16_u
        local.tee 3
        i32.const 11
        i32.gt_u
        br_if 1 (;@2;)
        block  ;; label = @4
          block  ;; label = @5
            block  ;; label = @6
              block  ;; label = @7
                block  ;; label = @8
                  block  ;; label = @9
                    block  ;; label = @10
                      block  ;; label = @11
                        block  ;; label = @12
                          block  ;; label = @13
                            block  ;; label = @14
                              local.get 3
                              br_table 10 (;@4;) 0 (;@14;) 1 (;@13;) 2 (;@12;) 3 (;@11;) 4 (;@10;) 5 (;@9;) 6 (;@8;) 7 (;@7;) 8 (;@6;) 13 (;@1;) 9 (;@5;) 10 (;@4;)
                            end
                            // case 1
                          end
                          // case 2
                        end
                      ...

The x64 code jitted by V8 for the switch was reasonably compact, though not-optimal:

00000000BD10FA43    83  460fb73423     movzxwl r14,[rbx+r12*1]
00000000BD10FA48    88  4183fe0b       cmpl r14,0xB 
00000000BD10FA4C    8c  0f8741020000   ja 00000000BD10FC93  // jmp to default case
00000000BD10FA52    92  4183ee0        subl r14,0x1
00000000BD10FA56    96  458bf6         movl r14,r14
00000000BD10FA59    99  4183fe0b       cmpl r14,0xB         
00000000BD10FA5D    9d  0f830d000000   jnc 00000000BD10FA70 // jmp to br_table default label
00000000BD10FA63    a3  4c8d1556030000 leaq r10,[rip+0x356]
00000000BD10FA6A    aa  43ff24f2       jmp [r10+r14*8]      // br_table jump

There were two checks (cmp/jmp), the first for the switch default case, the second for the implementation of br_table.

But now with this change I see this code being generated (see WAT file attached:

emcc-0-base.NEW.wat177 KBDownload

)

(func (;6;) (type 6) (param i32)
  (local i32 i32 i32 i32 i64 i32)
  ...
  block  ;; label = @1
    block  ;; label = @2
      block  ;; label = @3
        block  ;; label = @4
          block  ;; label = @5
            block  ;; label = @6
              block  ;; label = @7
                block  ;; label = @8
                  block  ;; label = @9
                    block  ;; label = @10
                      block  ;; label = @11
                        block  ;; label = @12
                          block  ;; label = @13
                            block  ;; label = @14
                              local.get 4
                              i32.load16_u
                              br_table 1 (;@13;) 0 (;@14;) 2 (;@12;) 3 (;@11;) 4 (;@10;) 5 (;@9;) 6 (;@8;) 7 (;@7;) 8 (;@6;) 9 (;@5;) 13 (;@1;) 10 (;@4;) 12 (;@2;)
                            end
                            i32.const 0
                            local.set 3
                            br 10 (;@3;)
                          end
                          i32.const 10
                          local.set 3
                          br 9 (;@3;)
                        end
                        i32.const 1
                        local.set 3
                        br 8 (;@3;)
                      end
                      i32.const 2
                      local.set 3
                      br 7 (;@3;)
                    end
                    i32.const 3
                    local.set 3
                    br 6 (;@3;)
                  end
                  i32.const 4
                  local.set 3
                  br 5 (;@3;)
                end
                i32.const 5
                local.set 3
                br 4 (;@3;)
              end
              i32.const 6
              local.set 3
              br 3 (;@3;)
            end
            i32.const 7
            local.set 3
            br 2 (;@3;)
          end
          i32.const 8
          local.set 3
          br 1 (;@3;)
        end
        i32.const 9
        local.set 3
      end
      loop  ;; label = @3
        block  ;; label = @4
          block  ;; label = @5
            block  ;; label = @6
              block  ;; label = @7
                block  ;; label = @8
                  block  ;; label = @9
                    block  ;; label = @10
                      block  ;; label = @11
                        block  ;; label = @12
                          block  ;; label = @13
                            block  ;; label = @14
                              block  ;; label = @15
                                block  ;; label = @16
                                  block  ;; label = @17
                                    block  ;; label = @18
                                      block  ;; label = @19
                                        block  ;; label = @20
                                          block  ;; label = @21
                                            block  ;; label = @22
                                              block  ;; label = @23
                                                block  ;; label = @24
                                                  block  ;; label = @25
                                                    local.get 3
                                                    br_table 0 (;@25;) 1 (;@24;) 2 (;@23;) 3 (;@22;) 4 (;@21;) 5 (;@20;) 6 (;@19;) 7 (;@18;) 8 (;@17;) 9 (;@16;) 10 (;@15;) 10 (;@15;)
                                                  end
                                                  // ... case 0
                                                  ...
                                                  br_table 19 (;@5;) 20 (;@4;) 10 (;@14;) 11 (;@13;) 12 (;@12;) 13 (;@11;) 14 (;@10;) 15 (;@9;) 16 (;@8;) 17 (;@7;) 23 (;@1;) 18 (;@6;) 22 (;@2;)
                                                end
                                                // ... case 1
                                                br_table 18 (;@5;) 19 (;@4;) 9 (;@14;) 10 (;@13;) 11 (;@12;) 12 (;@11;) 13 (;@10;) 14 (;@9;) 15 (;@8;) 16 (;@7;) 22 (;@1;) 17 (;@6;) 21 (;@2;)
                                              end
                                            ...

There is a br_table that causes an indirect jump to a stub like i32.const X local.set 3 br Y that jumps to the actual code for the case branches, which all end with other strange br_tables.
Obviously also the native code jitted is much more convoluted. The result is that my small benchmark is 34% slower (33.9 sec vs 25.2).

I see that this issue disappears if I comment away addPass(createWebAssemblyFixBrTableDefaults()); in WebAssemblyPassConfig::addInstSelector() and reintroduce Ops.push_back(DAG.getBasicBlock(MBBs[0])) in WebAssemblyTargetLowering::LowerBR_JT().

Maybe there is something wrong with my configuration, in my machine, but I double-tested this reinstalling the latest Emscripten, and can reliably reproduce the problem.
Could you take a look?

[tlively]

@paolosev Hmm, I suspect that there is a bad interaction between the code with the range check removed and the algorithm that lays out and structures the basic blocks. I will take a closer look!

[paolosev]

In D80863#2080996, @tlively wrote:

@paolosev Hmm, I suspect that there is a bad interaction between the code with the range check removed and the algorithm that lays out and structures the basic blocks. I will take a closer look!

Also notice, if it can help, that this problem happens when compiling with -O3 but not with -Os.

llvm/lib/Target/WebAssembly/CMakeLists.txt

add_llvm_target(WebAssemblyCodeGen
   WebAssemblyCFGStackify.cpp
   WebAssemblyCFGSort.cpp
   WebAssemblyDebugFixup.cpp
   WebAssemblyDebugValueManager.cpp
   WebAssemblyLateEHPrepare.cpp
   WebAssemblyExceptionInfo.cpp
   WebAssemblyExplicitLocals.cpp
   WebAssemblyFastISel.cpp
+  WebAssemblyFixBrTableDefaults.cpp
   WebAssemblyFixIrreducibleControlFlow.cpp
   WebAssemblyFixFunctionBitcasts.cpp
   WebAssemblyFrameLowering.cpp
   WebAssemblyISelDAGToDAG.cpp
   WebAssemblyISelLowering.cpp
   WebAssemblyInstrInfo.cpp
   WebAssemblyLowerBrUnless.cpp
   WebAssemblyLowerEmscriptenEHSjLj.cpp

llvm/lib/Target/WebAssembly/MCTargetDesc/WebAssemblyMCTargetDesc.h

inline bool isCallIndirect(unsigned Opc) {
   case WebAssembly::RET_CALL_INDIRECT:
   case WebAssembly::RET_CALL_INDIRECT_S:
     return true;
   default:
     return false;
   }
 }
 
+inline bool isBrTable(const MachineInstr &MI) {
+  switch (MI.getOpcode()) {
+  case WebAssembly::BR_TABLE_I32:
+  case WebAssembly::BR_TABLE_I32_S:
+  case WebAssembly::BR_TABLE_I64:
+  case WebAssembly::BR_TABLE_I64_S:
+    return true;
+  default:
+    return false;
+  }
+}
+
 inline bool isMarker(unsigned Opc) {
   switch (Opc) {
   case WebAssembly::BLOCK:
   case WebAssembly::BLOCK_S:
   case WebAssembly::END_BLOCK:
   case WebAssembly::END_BLOCK_S:
   case WebAssembly::LOOP:
   case WebAssembly::LOOP_S:

llvm/lib/Target/WebAssembly/WebAssembly.h

 
 // Late passes.
 FunctionPass *createWebAssemblyReplacePhysRegs();
 FunctionPass *createWebAssemblyPrepareForLiveIntervals();
 FunctionPass *createWebAssemblyOptimizeLiveIntervals();
 FunctionPass *createWebAssemblyMemIntrinsicResults();
 FunctionPass *createWebAssemblyRegStackify();
 FunctionPass *createWebAssemblyRegColoring();
+FunctionPass *createWebAssemblyFixBrTableDefaults();
 FunctionPass *createWebAssemblyFixIrreducibleControlFlow();
 FunctionPass *createWebAssemblyLateEHPrepare();
 FunctionPass *createWebAssemblyCFGSort();
 FunctionPass *createWebAssemblyCFGStackify();
 FunctionPass *createWebAssemblyExplicitLocals();
 FunctionPass *createWebAssemblyLowerBrUnless();
 FunctionPass *createWebAssemblyRegNumbering();
 FunctionPass *createWebAssemblyDebugFixup();
 FunctionPass *createWebAssemblyPeephole();
 
 // PassRegistry initialization declarations.
 void initializeWebAssemblyAddMissingPrototypesPass(PassRegistry &);
 void initializeWebAssemblyLowerEmscriptenEHSjLjPass(PassRegistry &);
 void initializeLowerGlobalDtorsPass(PassRegistry &);
 void initializeFixFunctionBitcastsPass(PassRegistry &);
 void initializeOptimizeReturnedPass(PassRegistry &);
 void initializeWebAssemblyArgumentMovePass(PassRegistry &);
 void initializeWebAssemblySetP2AlignOperandsPass(PassRegistry &);
 void initializeWebAssemblyReplacePhysRegsPass(PassRegistry &);
 void initializeWebAssemblyPrepareForLiveIntervalsPass(PassRegistry &);
 void initializeWebAssemblyOptimizeLiveIntervalsPass(PassRegistry &);
 void initializeWebAssemblyMemIntrinsicResultsPass(PassRegistry &);
 void initializeWebAssemblyRegStackifyPass(PassRegistry &);
 void initializeWebAssemblyRegColoringPass(PassRegistry &);
+void initializeWebAssemblyFixBrTableDefaultsPass(PassRegistry &);
 void initializeWebAssemblyFixIrreducibleControlFlowPass(PassRegistry &);
 void initializeWebAssemblyLateEHPreparePass(PassRegistry &);
 void initializeWebAssemblyExceptionInfoPass(PassRegistry &);
 void initializeWebAssemblyCFGSortPass(PassRegistry &);
 void initializeWebAssemblyCFGStackifyPass(PassRegistry &);
 void initializeWebAssemblyExplicitLocalsPass(PassRegistry &);
 void initializeWebAssemblyLowerBrUnlessPass(PassRegistry &);
 void initializeWebAssemblyRegNumberingPass(PassRegistry &);

llvm/lib/Target/WebAssembly/WebAssemblyFixBrTableDefaults.cpp

+//=- WebAssemblyFixBrTableDefaults.cpp - Fix br_table default branch targets -//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file This file implements a pass that eliminates redundant range checks
+/// guarding br_table instructions. Since jump tables on most targets cannot
+/// handle out of range indices, LLVM emits these checks before most jump
+/// tables. But br_table takes a default branch target as an argument, so it
+/// does not need the range checks.
+///
+//===----------------------------------------------------------------------===//
+
+#include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
+#include "WebAssembly.h"
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/Pass.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "wasm-fix-br-table-defaults"
+
+namespace {
+
+class WebAssemblyFixBrTableDefaults final : public MachineFunctionPass {
+  StringRef getPassName() const override {
+    return "WebAssembly Fix br_table Defaults";
+  }
+
+  bool runOnMachineFunction(MachineFunction &MF) override;
+
+public:
+  static char ID; // Pass identification, replacement for typeid
+  WebAssemblyFixBrTableDefaults() : MachineFunctionPass(ID) {}
+};
+
+char WebAssemblyFixBrTableDefaults::ID = 0;
+
+// `MI` is a br_table instruction missing its default target argument. This
+// function finds and adds the default target argument and removes any redundant
+// range check preceding the br_table.
+MachineBasicBlock *fixBrTable(MachineInstr &MI, MachineBasicBlock *MBB,
+                              MachineFunction &MF) {
+  // Get the header block, which contains the redundant range check.
+  assert(MBB->pred_size() == 1 && "Expected a single guard predecessor");
+  auto *HeaderMBB = *MBB->pred_begin();
+
+  // Find the conditional jump to the default target. If it doesn't exist, the
+  // default target is unreachable anyway, so we can choose anything.
+  auto &JumpMII = --HeaderMBB->end();
+  while (JumpMII->getOpcode() != WebAssembly::BR_IF &&
+         JumpMII != HeaderMBB->begin()) {
+    --JumpMII;
+  }
+  if (JumpMII->getOpcode() == WebAssembly::BR_IF) {
+    // Install the default target and remove the jumps in the header.
+    auto *DefaultMBB = JumpMII->getOperand(0).getMBB();
+    assert(DefaultMBB != MBB && "Expected conditional jump to default target");
+    MI.addOperand(MF, MachineOperand::CreateMBB(DefaultMBB));
+    HeaderMBB->erase(JumpMII, HeaderMBB->end());
+  } else {
+    // Arbitrarily choose the first jump target as the default.
+    auto *SomeMBB = MI.getOperand(1).getMBB();
+    MI.addOperand(MachineOperand::CreateMBB(SomeMBB));
+  }
+
+  // Splice the jump table into the header.
+  HeaderMBB->splice(HeaderMBB->end(), MBB, MBB->begin(), MBB->end());
+
+  // Update CFG to skip the old jump table block. Remove shared successors
+  // before transferring to avoid duplicated successors.
+  HeaderMBB->removeSuccessor(MBB);
+  for (auto &Succ : MBB->successors())
+    if (HeaderMBB->isSuccessor(Succ))
+      HeaderMBB->removeSuccessor(Succ);
+  HeaderMBB->transferSuccessorsAndUpdatePHIs(MBB);
+
+  // Remove the old jump table block from the function
+  MF.erase(MBB);
+
+  return HeaderMBB;
+}
+
+bool WebAssemblyFixBrTableDefaults::runOnMachineFunction(MachineFunction &MF) {
+  LLVM_DEBUG(dbgs() << "********** Fixing br_table Default Targets **********\n"
+                       "********** Function: "
+                    << MF.getName() << '\n');
+
+  bool Changed = false;
+  SmallPtrSet<MachineBasicBlock *, 16> MBBSet;
+  for (auto &MBB : MF)
+    MBBSet.insert(&MBB);
+
+  while (!MBBSet.empty()) {
+    MachineBasicBlock *MBB = *MBBSet.begin();
+    MBBSet.erase(MBB);
+    for (auto &MI : *MBB) {
+      if (WebAssembly::isBrTable(MI)) {
+        auto *Fixed = fixBrTable(MI, MBB, MF);
+        MBBSet.erase(Fixed);
+        Changed = true;
+        break;
+      }
+    }
+  }
+
+  if (Changed) {
+    // We rewrote part of the function; recompute relevant things.
+    MF.RenumberBlocks();
+    return true;
+  }
+
+  return false;
+}
+
+} // end anonymous namespace
+
+INITIALIZE_PASS(WebAssemblyFixBrTableDefaults, DEBUG_TYPE,
+                "Removes range checks and sets br_table default targets", false,
+                false);
+
+FunctionPass *llvm::createWebAssemblyFixBrTableDefaults() {
+  return new WebAssemblyFixBrTableDefaults();
+}

llvm/lib/Target/WebAssembly/WebAssemblyISelLowering.cpp

SDValue WebAssemblyTargetLowering::LowerBR_JT(SDValue Op,
 
   MachineJumpTableInfo *MJTI = DAG.getMachineFunction().getJumpTableInfo();
   const auto &MBBs = MJTI->getJumpTables()[JT->getIndex()].MBBs;
 
   // Add an operand for each case.
   for (auto MBB : MBBs)
     Ops.push_back(DAG.getBasicBlock(MBB));
 
-  // TODO: For now, we just pick something arbitrary for a default case for now.
-  // We really want to sniff out the guard and put in the real default case (and
-  // delete the guard).
-  Ops.push_back(DAG.getBasicBlock(MBBs[0]));
-
+  // Do not add the default case for now. It will be added in
+  // WebAssemblyFixBrTableDefaults.
   return DAG.getNode(WebAssemblyISD::BR_TABLE, DL, MVT::Other, Ops);
 }
 
 SDValue WebAssemblyTargetLowering::LowerVASTART(SDValue Op,
                                                 SelectionDAG &DAG) const {
   SDLoc DL(Op);
   EVT PtrVT = getPointerTy(DAG.getMachineFunction().getDataLayout());
 

llvm/lib/Target/WebAssembly/WebAssemblyTargetMachine.cpp

bool WebAssemblyPassConfig::addInstSelector() {
   // Run the argument-move pass immediately after the ScheduleDAG scheduler
   // so that we can fix up the ARGUMENT instructions before anything else
   // sees them in the wrong place.
   addPass(createWebAssemblyArgumentMove());
   // Set the p2align operands. This information is present during ISel, however
   // it's inconvenient to collect. Collect it now, and update the immediate
   // operands.
   addPass(createWebAssemblySetP2AlignOperands());
+
+  // Eliminate range checks and add default targets to br_table instructions.
+  addPass(createWebAssemblyFixBrTableDefaults());
+
   return false;
 }
 
 void WebAssemblyPassConfig::addPostRegAlloc() {
   // TODO: The following CodeGen passes don't currently support code containing
   // virtual registers. Consider removing their restrictions and re-enabling
   // them.
 

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

if.end:
   call void @bar()
   br label %outer
 }
 
 ; Test switch lowering and block placement.
 
 ; CHECK-LABEL: test4:
 ; CHECK-NEXT: .functype test4 (i32) -> (){{$}}
-; CHECK:      block   {{$}}
 ; CHECK-NEXT: block   {{$}}
-; CHECK:      br_if     0, $pop{{[0-9]+}}{{$}}
-; CHECK:      br        1{{$}}
-; CHECK-NEXT: .LBB{{[0-9]+}}_2:
+; CHECK-NEXT: block   {{$}}
+; CHECK-NEXT: br_table   $0, 1, 1, 1, 1, 1, 0{{$}}
+; CHECK-NEXT: .LBB{{[0-9]+}}_1:
 ; CHECK-NEXT: end_block{{$}}
-; CHECK-NEXT: br_table   $0, 0, 0, 0, 0, 0, 0{{$}}
-; CHECK-NEXT: .LBB{{[0-9]+}}_3:
+; CHECK-NEXT: i32.const $push[[C:[0-9]+]]=, 622{{$}}
+; CHECK-NEXT: i32.eq $drop=, $0, $pop[[C]]{{$}}
+; CHECK-NEXT: .LBB{{[0-9]+}}_2:
 ; CHECK-NEXT: end_block{{$}}
 ; CHECK-NEXT: return{{$}}
 define void @test4(i32 %t) {
 entry:
   switch i32 %t, label %default [
     i32 0, label %bb2
     i32 2, label %bb2
     i32 4, label %bb1

 ; CHECK:       .LBB{{[0-9]+}}_3:
 ; CHECK-NEXT:  block   {{$}}
 ; CHECK-NEXT:  loop    {{$}}
 ; CHECK:       .LBB{{[0-9]+}}_4:
 ; CHECK-NEXT:  loop    {{$}}
 ; CHECK:       br_if     0, {{[^,]+}}{{$}}
 ; CHECK-NEXT:  end_loop{{$}}
 ; CHECK-NEXT:  block   {{$}}
-; CHECK:       br_if     0, {{[^,]+}}{{$}}
-; CHECK:       br        3{{$}}
-; CHECK-NEXT:  .LBB{{[0-9]+}}_7:
-; CHECK-NEXT:  end_block{{$}}
-; CHECK:       block   {{$}}
-; CHECK-NEXT:  br_table   $0, 0, 3, 1, 2, 0
-; CHECK-NEXT:  .LBB{{[0-9]+}}_8:
+; CHECK-NOT:   br_if
+; CHECK:       br_table   $pop{{[^,]+}}, 0, 3, 1, 2, 3
+; CHECK-NEXT:  .LBB{{[0-9]+}}_6:
 ; CHECK-NEXT:  end_block{{$}}
 ; CHECK-NEXT:  end_loop{{$}}
 ; CHECK-NEXT:  return{{$}}
-; CHECK-NEXT:  .LBB{{[0-9]+}}_9:
+; CHECK-NEXT:  .LBB{{[0-9]+}}_7:
 ; CHECK-NEXT:  end_block{{$}}
 ; CHECK:       br        0{{$}}
-; CHECK-NEXT:  .LBB{{[0-9]+}}_10:
+; CHECK-NEXT:  .LBB{{[0-9]+}}_8:
 ; CHECK-NEXT:  end_loop{{$}}
 define void @test10() {
 bb0:
   br label %bb1
 
 bb1:
   %tmp = phi i32 [ 2, %bb0 ], [ 3, %bb3 ]
   %tmp3 = phi i32 [ undef, %bb0 ], [ %tmp11, %bb3 ]
bb7:
   ret void
 bb8:
   store volatile i32 8, i32* null
   ret void
 }
 
 ; CHECK-LABEL: test12:
 ; CHECK:       .LBB{{[0-9]+}}_1:
-; CHECK-NEXT:  loop    {{$}}
 ; CHECK-NEXT:  block   {{$}}
+; CHECK-NEXT:  loop    {{$}}
 ; CHECK-NEXT:  block   {{$}}
 ; CHECK-NEXT:  block   {{$}}
+; CHECK:       br_table  {{[^,]+}}, 1, 3, 3, 3, 1, 0{{$}}
+; CHECK-NEXT:  .LBB{{[0-9]+}}_2:
+; CHECK-NEXT:  end_block{{$}}
 ; CHECK:       br_if     0, {{[^,]+}}{{$}}
 ; CHECK:       br_if     2, {{[^,]+}}{{$}}
-; CHECK:       br_if     1, {{[^,]+}}{{$}}
-; CHECK-NEXT:  br        2{{$}}
 ; CHECK-NEXT:  .LBB{{[0-9]+}}_4:
 ; CHECK-NEXT:  end_block{{$}}
-; CHECK-NEXT:  br_table   $2, 1, 0, 0, 0, 1, 1{{$}}
+; CHECK:       br        0{{$}}
 ; CHECK-NEXT:  .LBB{{[0-9]+}}_5:
+; CHECK-NEXT:  end_loop{{$}}
 ; CHECK-NEXT:  end_block{{$}}
 ; CHECK-NEXT:  return{{$}}
-; CHECK-NEXT:  .LBB{{[0-9]+}}_6:
-; CHECK-NEXT:  end_block{{$}}
-; CHECK:       br        0{{$}}
-; CHECK-NEXT:  .LBB{{[0-9]+}}_7:
-; CHECK-NEXT:  end_loop{{$}}
 define void @test12(i8* %arg) {
 bb:
   br label %bb1
 
 bb1:
   %tmp = phi i32 [ 0, %bb ], [ %tmp5, %bb4 ]
   %tmp2 = getelementptr i8, i8* %arg, i32 %tmp
   %tmp3 = load i8, i8* %tmp2

llvm/test/CodeGen/WebAssembly/indirectbr.ll

 ; RUN: llc < %s -asm-verbose=false -disable-wasm-fallthrough-return-opt -wasm-disable-explicit-locals -wasm-keep-registers | FileCheck %s
 
 ; This tests that indirectbr instructions are lowered to switches. Currently we
 ; just re-use the IndirectBrExpand Pass; it has its own IR-level test.
 ; So this test just ensures that the pass gets run and we can lower indirectbr
 
 target triple = "wasm32"
 
 @test1.targets = constant [4 x i8*] [i8* blockaddress(@test1, %bb0),
                                      i8* blockaddress(@test1, %bb1),
                                      i8* blockaddress(@test1, %bb2),
                                      i8* blockaddress(@test1, %bb3)]
 
 ; Just check the barest skeleton of the structure
 ; CHECK-LABEL: test1:
+; CHECK: block
+; CHECK: block
+; CHECK: block
+; CHECK: block
 ; CHECK: i32.load
-; CHECK: i32.load $[[DEST:.+]]=
+; CHECK: i32.load
+; CHECK: i32.const
+; CHECK: i32.add $push[[DEST:.+]]=
+; CHECK: br_table $pop[[DEST]]
+; CHECK: end_block
+; CHECK: end_block
+; CHECK: end_block
+; CHECK: end_block
 ; CHECK: loop
 ; CHECK: block
 ; CHECK: block
+; CHECK: block
+; CHECK: block
+; CHECK: br_table ${{[^,]+}}, 0, 1, 2, 2
+; CHECK: end_block
 ; CHECK: end_block
+; CHECK: end_block
+; CHECK: block
 ; CHECK: block
 ; CHECK: block
-; CHECK: br_table $[[DEST]]
+; CHECK: br_table ${{[^,]+}}, 1, 2, 0
+; CHECK: end_block
 ; CHECK: end_block
 ; CHECK: end_block
-; CHECK: i32.load $[[DEST]]=
 ; CHECK: end_loop
-
 ; CHECK: test1.targets:
 ; CHECK-NEXT: .int32
 ; CHECK-NEXT: .int32
 ; CHECK-NEXT: .int32
 ; CHECK-NEXT: .int32
 
 define void @test1(i32* readonly %p, i32* %sink) #0 {
 

llvm/test/CodeGen/WebAssembly/stack-insts.ll

 ; RUN: llc < %s -asm-verbose=false -disable-wasm-fallthrough-return-opt -disable-block-placement -verify-machineinstrs | FileCheck %s
 
 target datalayout = "e-m:e-p:32:32-i64:64-n32:64-S128"
 target triple = "wasm32-unknown-unknown"
 
 declare void @foo0()
 declare void @foo1()
 
 ; Tests if br_table is printed correctly with a tab.
 ; CHECK-LABEL: test0:
-; CHECK: br_table {0, 1, 0, 1, 0}
+; CHECK: br_table {0, 1, 0, 1, 2}
 define void @test0(i32 %n) {
 entry:
   switch i32 %n, label %sw.epilog [
     i32 0, label %sw.bb
     i32 1, label %sw.bb.1
     i32 2, label %sw.bb
     i32 3, label %sw.bb.1
   ]

llvm/test/CodeGen/WebAssembly/switch-unreachable-default.ll

+; RUN: llc < %s -asm-verbose=false -verify-machineinstrs | FileCheck %s
+
+target datalayout = "e-m:e-p:32:32-i64:64-n32:64-S128"
+target triple = "wasm32-unknown-unknown"
+
+; Test that switches are lowered correctly in the presence of an
+; unreachable default branch target.
+
+; CHECK-LABEL: foo:
+; CHECK-NEXT:    .functype foo (i32) -> (i32)
+; CHECK-NEXT:    block
+; CHECK-NEXT:    block
+; CHECK-NEXT:    local.get 0
+; CHECK-NEXT:    br_table {0, 1, 0}
+; CHECK-NEXT:  .LBB0_1:
+; CHECK-NEXT:    end_block
+; CHECK-NEXT:    i32.const 0
+; CHECK-NEXT:    return
+; CHECK-NEXT:  .LBB0_2:
+; CHECK-NEXT:    end_block
+; CHECK-NEXT:    i32.const 1
+; CHECK-NEXT:    end_function
+define i32 @foo(i32 %x) {
+entry:
+  switch i32 %x, label %unreachable [
+    i32 0, label %bb0
+    i32 1, label %bb1
+  ]
+
+bb0:
+  ret i32 0
+
+bb1:
+  ret i32 1
+
+unreachable:
+  unreachable
+}

llvm/test/CodeGen/WebAssembly/switch.ll

 ; CHECK-LABEL: bar32:
 ; CHECK: block   {{$}}
 ; CHECK: block   {{$}}
 ; CHECK: block   {{$}}
 ; CHECK: block   {{$}}
 ; CHECK: block   {{$}}
 ; CHECK: block   {{$}}
 ; CHECK: block   {{$}}
-; CHECK: br_table {{[^,]+}}, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 4, 5, 0{{$}}
-; CHECK: .LBB{{[0-9]+}}_2:
+; CHECK: br_table {{[^,]+}}, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 4, 5, 6{{$}}
+; CHECK: .LBB{{[0-9]+}}_1:
 ; CHECK:   call foo0{{$}}
-; CHECK: .LBB{{[0-9]+}}_3:
+; CHECK: .LBB{{[0-9]+}}_2:
 ; CHECK:   call foo1{{$}}
-; CHECK: .LBB{{[0-9]+}}_4:
+; CHECK: .LBB{{[0-9]+}}_3:
 ; CHECK:   call foo2{{$}}
-; CHECK: .LBB{{[0-9]+}}_5:
+; CHECK: .LBB{{[0-9]+}}_4:
 ; CHECK:   call foo3{{$}}
-; CHECK: .LBB{{[0-9]+}}_6:
+; CHECK: .LBB{{[0-9]+}}_5:
 ; CHECK:   call foo4{{$}}
-; CHECK: .LBB{{[0-9]+}}_7:
+; CHECK: .LBB{{[0-9]+}}_6:
 ; CHECK:   call foo5{{$}}
-; CHECK: .LBB{{[0-9]+}}_8:
+; CHECK: .LBB{{[0-9]+}}_7:
 ; CHECK:   return{{$}}
 define void @bar32(i32 %n) {
 entry:
   switch i32 %n, label %sw.epilog [
     i32 0, label %sw.bb
     i32 1, label %sw.bb
     i32 2, label %sw.bb
     i32 3, label %sw.bb

 ; CHECK-LABEL: bar64:
 ; CHECK: block   {{$}}
 ; CHECK: block   {{$}}
 ; CHECK: block   {{$}}
 ; CHECK: block   {{$}}
 ; CHECK: block   {{$}}
 ; CHECK: block   {{$}}
 ; CHECK: block   {{$}}
-; CHECK: br_table {{[^,]+}}, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 4, 5, 0{{$}}
-; CHECK: .LBB{{[0-9]+}}_2:
+; CHECK: br_table {{[^,]+}}, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 4, 5, 6{{$}}
+; CHECK: .LBB{{[0-9]+}}_1:
 ; CHECK:   call foo0{{$}}
-; CHECK: .LBB{{[0-9]+}}_3:
+; CHECK: .LBB{{[0-9]+}}_2:
 ; CHECK:   call foo1{{$}}
-; CHECK: .LBB{{[0-9]+}}_4:
+; CHECK: .LBB{{[0-9]+}}_3:
 ; CHECK:   call foo2{{$}}
-; CHECK: .LBB{{[0-9]+}}_5:
+; CHECK: .LBB{{[0-9]+}}_4:
 ; CHECK:   call foo3{{$}}
-; CHECK: .LBB{{[0-9]+}}_6:
+; CHECK: .LBB{{[0-9]+}}_5:
 ; CHECK:   call foo4{{$}}
-; CHECK: .LBB{{[0-9]+}}_7:
+; CHECK: .LBB{{[0-9]+}}_6:
 ; CHECK:   call foo5{{$}}
-; CHECK: .LBB{{[0-9]+}}_8:
+; CHECK: .LBB{{[0-9]+}}_7:
 ; CHECK:   return{{$}}
 define void @bar64(i64 %n) {
 entry:
   switch i64 %n, label %sw.epilog [
     i64 0, label %sw.bb
     i64 1, label %sw.bb
     i64 2, label %sw.bb
     i64 3, label %sw.bb