[WebAssembly] Add br_unless, implement ReverseBranchCondition, and re-enable MachineBlockPlacement

[sunfish]

Summary

Pending https://github.com/WebAssembly/design/pull/481 , this is a patch implementing br_unless in LLVM and some optimizations that are significantly easier to implement using it.

[sunfish]

This would also be accompanied by this change: https://github.com/WebAssembly/experimental/commit/cfd8a9dab3c188f9919bd938fcfa5446711ab6fe

The test diffs in that commit also give a pretty good illustration of the effect of this patch on codegen.

[sunfish]

As an interim solution, to let this patch move forward without waiting for the spec process, this update adds a patch to lower br_unless into br_if, reversing the condition in place if possible, or negating the condition manually if necessary.

This may also motivate adding more floating-point comparison operators, or a dedicated not operator, if br_unless itself does not advance.

[jfb]

Don't you want an option to disable the pass as well, so that we can let people compare the code for both easily?

lib/Target/WebAssembly/WebAssemblyInstrControl.td

37

This is only I32 because that's what we lower bool to, correct? Could you add a comment explaining it?

lib/Target/WebAssembly/WebAssemblyInstrInfo.cpp

133–143

&& "comment"

153–155

Ditto.

lib/Target/WebAssembly/WebAssemblyLowerBrUnless.cpp

103

Start with Inverted = true and set Inverted = false for default?

[sunfish]

Updated for review comments.

[jfb]

One file got lost in the update I think.

[sunfish]

I hadn't planned to add an option; I tend to prefer to avoid checking in command-line options for experiments.

lib/Target/WebAssembly/WebAssemblyInstrControl.td

37

Correct.

[sunfish]

Fix missing file in previous patch.

[jfb]

I think it would make the discussion easier if folks could try both, but the patch looks fine for now.

lib/Target/WebAssembly/CMakeLists.txt

add_llvm_target(WebAssemblyCodeGen
   Relooper.cpp
   WebAssemblyAsmPrinter.cpp
   WebAssemblyCFGStackify.cpp
   WebAssemblyFastISel.cpp
   WebAssemblyFrameLowering.cpp
   WebAssemblyISelDAGToDAG.cpp
   WebAssemblyISelLowering.cpp
   WebAssemblyInstrInfo.cpp
+  WebAssemblyLowerBrUnless.cpp
   WebAssemblyMachineFunctionInfo.cpp
   WebAssemblyMCInstLower.cpp
   WebAssemblyOptimizeReturned.cpp
   WebAssemblyPeephole.cpp
   WebAssemblyRegisterInfo.cpp
   WebAssemblyRegColoring.cpp
   WebAssemblyRegNumbering.cpp
   WebAssemblyRegStackify.cpp

lib/Target/WebAssembly/WebAssembly.h

 
 FunctionPass *createWebAssemblyISelDag(WebAssemblyTargetMachine &TM,
                                        CodeGenOpt::Level OptLevel);
 
 FunctionPass *createWebAssemblyStoreResults();
 FunctionPass *createWebAssemblyRegStackify();
 FunctionPass *createWebAssemblyRegColoring();
 FunctionPass *createWebAssemblyCFGStackify();
+FunctionPass *createWebAssemblyLowerBrUnless();
 FunctionPass *createWebAssemblyRegNumbering();
 FunctionPass *createWebAssemblyPeephole();
 
 FunctionPass *createWebAssemblyRelooper();
 
 } // end namespace llvm
 
 #endif

lib/Target/WebAssembly/WebAssemblyInstrControl.td

 /// \file
 /// \brief WebAssembly control-flow code-gen constructs.
 ///
 //===----------------------------------------------------------------------===//
 
 let Defs = [ARGUMENTS] in {
 
 let isBranch = 1, isTerminator = 1, hasCtrlDep = 1 in {
-def BR_IF : I<(outs), (ins I32:$a, bb_op:$dst),
-              [(brcond I32:$a, bb:$dst)],
-               "br_if   \t$a, $dst">;
+// The condition operand is a boolean value which WebAssembly represents as i32.
+def BR_IF : I<(outs), (ins I32:$cond, bb_op:$dst),
+              [(brcond I32:$cond, bb:$dst)],
+               "br_if   \t$cond, $dst">;
+let isCodeGenOnly = 1 in
+def BR_UNLESS : I<(outs), (ins I32:$cond, bb_op:$dst), [],
+                   "br_unless\t$cond, $dst">;
 let isBarrier = 1 in {
 def BR   : I<(outs), (ins bb_op:$dst),
              [(br bb:$dst)],
              "br      \t$dst">;
 } // isBarrier = 1
 } // isBranch = 1, isTerminator = 1, hasCtrlDep = 1
 
+} // Defs = [ARGUMENTS]
+
+def : Pat<(brcond (i32 (setne I32:$cond, 0)), bb:$dst),
+          (BR_IF I32:$cond, bb_op:$dst)>;
+def : Pat<(brcond (i32 (seteq I32:$cond, 0)), bb:$dst),
+          (BR_UNLESS I32:$cond, bb_op:$dst)>;
+
+let Defs = [ARGUMENTS] in {
+
 // TODO: SelectionDAG's lowering insists on using a pointer as the index for
 // jump tables, so in practice we don't ever use TABLESWITCH_I64 in wasm32 mode
 // currently.
 let isTerminator = 1, hasCtrlDep = 1, isBarrier = 1 in {
 def TABLESWITCH_I32 : I<(outs), (ins I32:$index, variable_ops),
                         [(WebAssemblytableswitch I32:$index)],
                         "tableswitch\t$index">;
 def TABLESWITCH_I64 : I<(outs), (ins I64:$index, variable_ops),

lib/Target/WebAssembly/WebAssemblyInstrInfo.cpp

for (MachineInstr &MI : iterator_range<MachineBasicBlock::instr_iterator>(
            MBB.getFirstInstrTerminator(), MBB.instr_end())) {
     switch (MI.getOpcode()) {
     default:
       // Unhandled instruction; bail out.
       return true;
     case WebAssembly::BR_IF:
       if (HaveCond)
         return true;
+      Cond.push_back(MachineOperand::CreateImm(true));
+      Cond.push_back(MI.getOperand(0));
+      TBB = MI.getOperand(1).getMBB();
+      HaveCond = true;
+      break;
+    case WebAssembly::BR_UNLESS:
+      if (HaveCond)
+        return true;
+      Cond.push_back(MachineOperand::CreateImm(false));
       Cond.push_back(MI.getOperand(0));
       TBB = MI.getOperand(1).getMBB();
       HaveCond = true;
       break;
     case WebAssembly::BR:
       if (!HaveCond)
         TBB = MI.getOperand(0).getMBB();
       else
unsigned WebAssemblyInstrInfo::RemoveBranch(MachineBasicBlock &MBB) const {
   return Count;
 }
 
 unsigned WebAssemblyInstrInfo::InsertBranch(MachineBasicBlock &MBB,
                                             MachineBasicBlock *TBB,
                                             MachineBasicBlock *FBB,
                                             ArrayRef<MachineOperand> Cond,
                                             DebugLoc DL) const {
-  assert(Cond.size() <= 1);
-
   if (Cond.empty()) {
     if (!TBB)
       return 0;
 
     BuildMI(&MBB, DL, get(WebAssembly::BR)).addMBB(TBB);
     return 1;
   }
 
-  BuildMI(&MBB, DL, get(WebAssembly::BR_IF)).addOperand(Cond[0]).addMBB(TBB);
+  assert(Cond.size() == 2 && "Expected a flag and a successor block");
+
+  if (Cond[0].getImm()) {
+    BuildMI(&MBB, DL, get(WebAssembly::BR_IF))
+        .addOperand(Cond[1])
+        .addMBB(TBB);
+  } else {
+    BuildMI(&MBB, DL, get(WebAssembly::BR_UNLESS))
+        .addOperand(Cond[1])
+        .addMBB(TBB);
+  }
   if (!FBB)
     return 1;
 
   BuildMI(&MBB, DL, get(WebAssembly::BR)).addMBB(FBB);
   return 2;
 }
 
 bool WebAssemblyInstrInfo::ReverseBranchCondition(
     SmallVectorImpl<MachineOperand> &Cond) const {
-  assert(Cond.size() == 1);
-
-  // TODO: Add branch reversal here... And re-enable MachineBlockPlacementID
-  // when we do.
-
-  return true;
+  assert(Cond.size() == 2 && "Expected a flag and a successor block");
+  Cond.front() = MachineOperand::CreateImm(!Cond.front().getImm());
+  return false;
 }

lib/Target/WebAssembly/WebAssemblyLowerBrUnless.cpp

+//===-- WebAssemblyLowerBrUnless.cpp - Lower br_unless --------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// \brief This file lowers br_unless into br_if with an inverted condition.
+///
+/// br_unless is not currently in the spec, but it's very convenient for LLVM
+/// to use. This pass allows LLVM to use it, for now.
+///
+//===----------------------------------------------------------------------===//
+
+#include "WebAssembly.h"
+#include "WebAssemblyMachineFunctionInfo.h"
+#include "WebAssemblySubtarget.h"
+#include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+using namespace llvm;
+
+#define DEBUG_TYPE "wasm-lower-br_unless"
+
+namespace {
+class WebAssemblyLowerBrUnless final : public MachineFunctionPass {
+  const char *getPassName() const override {
+    return "WebAssembly Lower br_unless";
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.setPreservesCFG();
+    MachineFunctionPass::getAnalysisUsage(AU);
+  }
+
+  bool runOnMachineFunction(MachineFunction &MF) override;
+
+public:
+  static char ID; // Pass identification, replacement for typeid
+  WebAssemblyLowerBrUnless() : MachineFunctionPass(ID) {}
+};
+} // end anonymous namespace
+
+char WebAssemblyLowerBrUnless::ID = 0;
+FunctionPass *llvm::createWebAssemblyLowerBrUnless() {
+  return new WebAssemblyLowerBrUnless();
+}
+
+bool WebAssemblyLowerBrUnless::runOnMachineFunction(MachineFunction &MF) {
+  DEBUG(dbgs() << "********** Lowering br_unless **********\n"
+                  "********** Function: "
+               << MF.getName() << '\n');
+
+  auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
+  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
+  auto &MRI = MF.getRegInfo();
+
+  for (auto &MBB : MF) {
+    for (auto MII = MBB.begin(); MII != MBB.end(); ) {
+      MachineInstr *MI = &*MII++;
+      if (MI->getOpcode() != WebAssembly::BR_UNLESS)
+        continue;
+
+      unsigned Cond = MI->getOperand(0).getReg();
+      bool Inverted = false;
+
+      // Attempt to invert the condition in place.
+      if (MFI.isVRegStackified(Cond)) {
+        assert(MRI.hasOneDef(Cond));
+        MachineInstr *Def = MRI.getVRegDef(Cond);
+        switch (Def->getOpcode()) {
+        using namespace WebAssembly;
+        case EQ_I32: Def->setDesc(TII.get(NE_I32)); Inverted = true; break;
+        case NE_I32: Def->setDesc(TII.get(EQ_I32)); Inverted = true; break;
+        case GT_S_I32: Def->setDesc(TII.get(LE_S_I32)); Inverted = true; break;
+        case GE_S_I32: Def->setDesc(TII.get(LT_S_I32)); Inverted = true; break;
+        case LT_S_I32: Def->setDesc(TII.get(GE_S_I32)); Inverted = true; break;
+        case LE_S_I32: Def->setDesc(TII.get(GT_S_I32)); Inverted = true; break;
+        case GT_U_I32: Def->setDesc(TII.get(LE_U_I32)); Inverted = true; break;
+        case GE_U_I32: Def->setDesc(TII.get(LT_U_I32)); Inverted = true; break;
+        case LT_U_I32: Def->setDesc(TII.get(GE_U_I32)); Inverted = true; break;
+        case LE_U_I32: Def->setDesc(TII.get(GT_U_I32)); Inverted = true; break;
+        case EQ_I64: Def->setDesc(TII.get(NE_I64)); Inverted = true; break;
+        case NE_I64: Def->setDesc(TII.get(EQ_I64)); Inverted = true; break;
+        case GT_S_I64: Def->setDesc(TII.get(LE_S_I64)); Inverted = true; break;
+        case GE_S_I64: Def->setDesc(TII.get(LT_S_I64)); Inverted = true; break;
+        case LT_S_I64: Def->setDesc(TII.get(GE_S_I64)); Inverted = true; break;
+        case LE_S_I64: Def->setDesc(TII.get(GT_S_I64)); Inverted = true; break;
+        case GT_U_I64: Def->setDesc(TII.get(LE_U_I64)); Inverted = true; break;
+        case GE_U_I64: Def->setDesc(TII.get(LT_U_I64)); Inverted = true; break;
+        case LT_U_I64: Def->setDesc(TII.get(GE_U_I64)); Inverted = true; break;
+        case LE_U_I64: Def->setDesc(TII.get(GT_U_I64)); Inverted = true; break;
+        case EQ_F32: Def->setDesc(TII.get(NE_F32)); Inverted = true; break;
+        case NE_F32: Def->setDesc(TII.get(EQ_F32)); Inverted = true; break;
+        case EQ_F64: Def->setDesc(TII.get(NE_F64)); Inverted = true; break;
+        case NE_F64: Def->setDesc(TII.get(EQ_F64)); Inverted = true; break;
+        default: break;
+        }
+      }
+
+      // If we weren't able to invert the condition in place. Insert an
+      // expression to invert it.
+      if (!Inverted) {
+        unsigned ZeroReg = MRI.createVirtualRegister(&WebAssembly::I32RegClass);
+        MFI.stackifyVReg(ZeroReg);
+        BuildMI(MBB, MI, MI->getDebugLoc(), TII.get(WebAssembly::CONST_I32), ZeroReg)
+            .addImm(0);
+        unsigned Tmp = MRI.createVirtualRegister(&WebAssembly::I32RegClass);
+        MFI.stackifyVReg(Tmp);
+        BuildMI(MBB, MI, MI->getDebugLoc(), TII.get(WebAssembly::EQ_I32), Tmp)
+            .addReg(Cond)
+            .addReg(ZeroReg);
+        Cond = Tmp;
+        Inverted = true;
+      }
+
+      // The br_unless condition has now been inverted. Insert a br_if and
+      // delete the br_unless.
+      assert(Inverted);
+      BuildMI(MBB, MI, MI->getDebugLoc(), TII.get(WebAssembly::BR_IF))
+          .addReg(Cond)
+          .addMBB(MI->getOperand(1).getMBB());
+      MBB.erase(MI);
+    }
+  }
+
+  return true;
+}

lib/Target/WebAssembly/WebAssemblyTargetMachine.cpp

void WebAssemblyPassConfig::addPostRegAlloc() {
   // virtual registers. Consider removing their restrictions and re-enabling
   // them.
   //
   // Fails with: Regalloc must assign all vregs.
   disablePass(&PrologEpilogCodeInserterID);
   // Fails with: should be run after register allocation.
   disablePass(&MachineCopyPropagationID);
 
-  // TODO: Until we get ReverseBranchCondition support, MachineBlockPlacement
-  // can create ugly-looking control flow.
-  disablePass(&MachineBlockPlacementID);
-
   // Run the register coloring pass to reduce the total number of registers.
   addPass(createWebAssemblyRegColoring());
 }
 
 void WebAssemblyPassConfig::addPreEmitPass() {
   // Put the CFG in structured form; insert BLOCK and LOOP markers.
   addPass(createWebAssemblyCFGStackify());
 
+  // Lower br_unless into br_if.
+  addPass(createWebAssemblyLowerBrUnless());
+
   // Create a mapping from LLVM CodeGen virtual registers to wasm registers.
   addPass(createWebAssemblyRegNumbering());
 
   // Perform the very last peephole optimizations on the code.
   addPass(createWebAssemblyPeephole());
 }

test/CodeGen/WebAssembly/cfg-stackify.ll

-; RUN: llc < %s -asm-verbose=false | FileCheck %s
+; RUN: llc < %s -asm-verbose=false -disable-block-placement | FileCheck %s
+; RUN: llc < %s -asm-verbose=false | FileCheck -check-prefix=OPT %s
 
 ; Test the CFG stackifier pass.
 
 target datalayout = "e-p:32:32-i64:64-n32:64-S128"
 target triple = "wasm32-unknown-unknown"
 
 declare void @something()
 
 ; Test that loops are made contiguous, even in the presence of split backedges.
 
 ; CHECK-LABEL: test0:
 ; CHECK: loop
 ; CHECK: i32.add
+; CHECK-NOT: br
 ; CHECK: br_if
+; CHECK-NOT: br
 ; CHECK: call
 ; CHECK: br BB0_1{{$}}
 ; CHECK: return{{$}}
+; OPT-LABEL: test0:
+; OPT: loop
+; OPT: i32.add
+; OPT-NOT: br
+; OPT: br_if
+; OPT-NOT: br
+; OPT: call
+; OPT: br BB0_1{{$}}
+; OPT: return{{$}}
 define void @test0(i32 %n) {
 entry:
   br label %header
 
 header:
   %i = phi i32 [ 0, %entry ], [ %i.next, %back ]
   %i.next = add i32 %i, 1
 
   %c = icmp slt i32 %i.next, %n
   br i1 %c, label %back, label %exit
 
 exit:
   ret void
 
 back:
   call void @something()
   br label %header
 }
 
 ; Same as test0, but the branch condition is reversed.
 
 ; CHECK-LABEL: test1:
 ; CHECK: loop
 ; CHECK: i32.add
+; CHECK-NOT: br
 ; CHECK: br_if
+; CHECK-NOT: br
 ; CHECK: call
 ; CHECK: br BB1_1{{$}}
 ; CHECK: return{{$}}
+; OPT-LABEL: test1:
+; OPT: loop
+; OPT: i32.add
+; OPT-NOT: br
+; OPT: br_if
+; OPT-NOT: br
+; OPT: call
+; OPT: br BB1_1{{$}}
+; OPT: return{{$}}
 define void @test1(i32 %n) {
 entry:
   br label %header
 
 header:
   %i = phi i32 [ 0, %entry ], [ %i.next, %back ]
   %i.next = add i32 %i, 1
 

 }
 
 ; Test that a simple loop is handled as expected.
 
 ; CHECK-LABEL: test2:
 ; CHECK: block BB2_2{{$}}
 ; CHECK: br_if {{.*}}, BB2_2{{$}}
 ; CHECK: BB2_1:
-; CHECK: br_if $pop{{[0-9]+}}, BB2_1{{$}}
+; CHECK: br_if ${{[0-9]+}}, BB2_1{{$}}
 ; CHECK: BB2_2:
 ; CHECK: return{{$}}
+; OPT-LABEL: test2:
+; OPT: block BB2_2{{$}}
+; OPT: br_if {{.*}}, BB2_2{{$}}
+; OPT: BB2_1:
+; OPT: br_if ${{[0-9]+}}, BB2_1{{$}}
+; OPT: BB2_2:
+; OPT: return{{$}}
 define void @test2(double* nocapture %p, i32 %n) {
 entry:
   %cmp.4 = icmp sgt i32 %n, 0
   br i1 %cmp.4, label %for.body.preheader, label %for.end
 
 for.body.preheader:
   br label %for.body
 

 
 for.end:
   ret void
 }
 
 ; CHECK-LABEL: doublediamond:
 ; CHECK: block BB3_5{{$}}
 ; CHECK: block BB3_2{{$}}
-; CHECK: br_if $pop{{[0-9]+}}, BB3_2{{$}}
+; CHECK: br_if $0, BB3_2{{$}}
 ; CHECK: block BB3_4{{$}}
-; CHECK: br_if $pop{{[0-9]+}}, BB3_4{{$}}
+; CHECK: br_if $1, BB3_4{{$}}
 ; CHECK: br BB3_5{{$}}
 ; CHECK: BB3_4:
 ; CHECK: BB3_5:
 ; CHECK: return ${{[0-9]+}}{{$}}
+; OPT-LABEL: doublediamond:
+; OPT: block BB3_5{{$}}
+; OPT: block BB3_4{{$}}
+; OPT: br_if {{.*}}, BB3_4{{$}}
+; OPT: block BB3_3{{$}}
+; OPT: br_if {{.*}}, BB3_3{{$}}
+; OPT: br BB3_5{{$}}
+; OPT: BB3_4:
+; OPT: BB3_5:
+; OPT: return ${{[0-9]+}}{{$}}
 define i32 @doublediamond(i32 %a, i32 %b, i32* %p) {
 entry:
   %c = icmp eq i32 %a, 0
   %d = icmp eq i32 %b, 0
   store volatile i32 0, i32* %p
   br i1 %c, label %true, label %false
 true:
   store volatile i32 1, i32* %p
ff:
   br label %exit
 exit:
   store volatile i32 5, i32* %p
   ret i32 0
 }
 
 ; CHECK-LABEL: triangle:
 ; CHECK: block BB4_2{{$}}
-; CHECK: br_if $pop{{[0-9]+}}, BB4_2{{$}}
+; CHECK: br_if $1, BB4_2{{$}}
 ; CHECK: BB4_2:
 ; CHECK: return ${{[0-9]+}}{{$}}
+; OPT-LABEL: triangle:
+; OPT: block BB4_2{{$}}
+; OPT: br_if $1, BB4_2{{$}}
+; OPT: BB4_2:
+; OPT: return ${{[0-9]+}}{{$}}
 define i32 @triangle(i32* %p, i32 %a) {
 entry:
   %c = icmp eq i32 %a, 0
   store volatile i32 0, i32* %p
   br i1 %c, label %true, label %exit
 true:
   store volatile i32 1, i32* %p
   br label %exit
 exit:
   store volatile i32 2, i32* %p
   ret i32 0
 }
 
 ; CHECK-LABEL: diamond:
 ; CHECK: block BB5_3{{$}}
 ; CHECK: block BB5_2{{$}}
-; CHECK: br_if $pop{{[0-9]+}}, BB5_2{{$}}
+; CHECK: br_if $1, BB5_2{{$}}
 ; CHECK: br BB5_3{{$}}
 ; CHECK: BB5_2:
 ; CHECK: BB5_3:
 ; CHECK: return ${{[0-9]+}}{{$}}
+; OPT-LABEL: diamond:
+; OPT: block BB5_3{{$}}
+; OPT: block BB5_2{{$}}
+; OPT: br_if {{.*}}, BB5_2{{$}}
+; OPT: br BB5_3{{$}}
+; OPT: BB5_2:
+; OPT: BB5_3:
+; OPT: return ${{[0-9]+}}{{$}}
 define i32 @diamond(i32* %p, i32 %a) {
 entry:
   %c = icmp eq i32 %a, 0
   store volatile i32 0, i32* %p
   br i1 %c, label %true, label %false
 true:
   store volatile i32 1, i32* %p
   br label %exit
 false:
   store volatile i32 2, i32* %p
   br label %exit
 exit:
   store volatile i32 3, i32* %p
   ret i32 0
 }
 
 ; CHECK-LABEL: single_block:
 ; CHECK-NOT: br
 ; CHECK: return $pop{{[0-9]+}}{{$}}
+; OPT-LABEL: single_block:
+; OPT-NOT: br
+; OPT: return $pop{{[0-9]+}}{{$}}
 define i32 @single_block(i32* %p) {
 entry:
   store volatile i32 0, i32* %p
   ret i32 0
 }
 
 ; CHECK-LABEL: minimal_loop:
 ; CHECK-NOT: br
 ; CHECK: BB7_1:
 ; CHECK: i32.store $discard=, 0($0), $pop{{[0-9]+}}{{$}}
 ; CHECK: br BB7_1{{$}}
 ; CHECK: BB7_2:
+; OPT-LABEL: minimal_loop:
+; OPT-NOT: br
+; OPT: BB7_1:
+; OPT: i32.store $discard=, 0($0), $pop{{[0-9]+}}{{$}}
+; OPT: br BB7_1{{$}}
+; OPT: BB7_2:
 define i32 @minimal_loop(i32* %p) {
 entry:
   store volatile i32 0, i32* %p
   br label %loop
 loop:
   store volatile i32 1, i32* %p
   br label %loop
 }
 
 ; CHECK-LABEL: simple_loop:
 ; CHECK-NOT: br
 ; CHECK: BB8_1:
 ; CHECK: loop BB8_2{{$}}
 ; CHECK: br_if $pop{{[0-9]+}}, BB8_1{{$}}
 ; CHECK: BB8_2:
 ; CHECK: return ${{[0-9]+}}{{$}}
+; OPT-LABEL: simple_loop:
+; OPT-NOT: br
+; OPT: BB8_1:
+; OPT: loop BB8_2{{$}}
+; OPT: br_if {{.*}}, BB8_1{{$}}
+; OPT: BB8_2:
+; OPT: return ${{[0-9]+}}{{$}}
 define i32 @simple_loop(i32* %p, i32 %a) {
 entry:
   %c = icmp eq i32 %a, 0
   store volatile i32 0, i32* %p
   br label %loop
 loop:
   store volatile i32 1, i32* %p
   br i1 %c, label %loop, label %exit
 exit:
   store volatile i32 2, i32* %p
   ret i32 0
 }
 
 ; CHECK-LABEL: doubletriangle:
 ; CHECK: block BB9_4{{$}}
-; CHECK: br_if $pop{{[0-9]+}}, BB9_4{{$}}
+; CHECK: br_if $0, BB9_4{{$}}
 ; CHECK: block BB9_3{{$}}
-; CHECK: br_if $pop{{[0-9]+}}, BB9_3{{$}}
+; CHECK: br_if $1, BB9_3{{$}}
 ; CHECK: BB9_3:
 ; CHECK: BB9_4:
 ; CHECK: return ${{[0-9]+}}{{$}}
+; OPT-LABEL: doubletriangle:
+; OPT: block BB9_4{{$}}
+; OPT: br_if $0, BB9_4{{$}}
+; OPT: block BB9_3{{$}}
+; OPT: br_if $1, BB9_3{{$}}
+; OPT: BB9_3:
+; OPT: BB9_4:
+; OPT: return ${{[0-9]+}}{{$}}
 define i32 @doubletriangle(i32 %a, i32 %b, i32* %p) {
 entry:
   %c = icmp eq i32 %a, 0
   %d = icmp eq i32 %b, 0
   store volatile i32 0, i32* %p
   br i1 %c, label %true, label %exit
 true:
   store volatile i32 2, i32* %p
   br i1 %d, label %tt, label %tf
 tt:
   store volatile i32 3, i32* %p
   br label %tf
 tf:
   store volatile i32 4, i32* %p
   br label %exit
 exit:
   store volatile i32 5, i32* %p
   ret i32 0
 }
 
 ; CHECK-LABEL: ifelse_earlyexits:
 ; CHECK: block BB10_4{{$}}
 ; CHECK: block BB10_2{{$}}
-; CHECK: br_if $pop{{[0-9]+}}, BB10_2{{$}}
+; CHECK: br_if $0, BB10_2{{$}}
 ; CHECK: br BB10_4{{$}}
 ; CHECK: BB10_2:
-; CHECK: br_if $pop{{[0-9]+}}, BB10_4{{$}}
+; CHECK: br_if $1, BB10_4{{$}}
 ; CHECK: BB10_4:
 ; CHECK: return ${{[0-9]+}}{{$}}
+; OPT-LABEL: ifelse_earlyexits:
+; OPT: block BB10_4{{$}}
+; OPT: block BB10_3{{$}}
+; OPT: br_if {{.*}}, BB10_3{{$}}
+; OPT: br_if $1, BB10_4{{$}}
+; OPT: br BB10_4{{$}}
+; OPT: BB10_3:
+; OPT: BB10_4:
+; OPT: return ${{[0-9]+}}{{$}}
 define i32 @ifelse_earlyexits(i32 %a, i32 %b, i32* %p) {
 entry:
   %c = icmp eq i32 %a, 0
   %d = icmp eq i32 %b, 0
   store volatile i32 0, i32* %p
   br i1 %c, label %true, label %false
 true:
   store volatile i32 1, i32* %p
exit:
   ret i32 0
 }
 
 ; CHECK-LABEL: doublediamond_in_a_loop:
 ; CHECK: BB11_1:
 ; CHECK: loop            BB11_7{{$}}
 ; CHECK: block           BB11_6{{$}}
 ; CHECK: block           BB11_3{{$}}
-; CHECK: br_if           $pop{{.*}}, BB11_3{{$}}
+; CHECK: br_if           $0, BB11_3{{$}}
 ; CHECK: br              BB11_6{{$}}
 ; CHECK: BB11_3:
 ; CHECK: block           BB11_5{{$}}
-; CHECK: br_if           $pop{{.*}}, BB11_5{{$}}
+; CHECK: br_if           $1, BB11_5{{$}}
 ; CHECK: br              BB11_6{{$}}
 ; CHECK: BB11_5:
 ; CHECK: BB11_6:
 ; CHECK: br              BB11_1{{$}}
 ; CHECK: BB11_7:
+; OPT-LABEL: doublediamond_in_a_loop:
+; OPT: BB11_1:
+; OPT: loop            BB11_7{{$}}
+; OPT: block           BB11_6{{$}}
+; OPT: block           BB11_5{{$}}
+; OPT: br_if           {{.*}}, BB11_5{{$}}
+; OPT: block           BB11_4{{$}}
+; OPT: br_if           {{.*}}, BB11_4{{$}}
+; OPT: br              BB11_6{{$}}
+; OPT: BB11_4:
+; OPT: br              BB11_6{{$}}
+; OPT: BB11_5:
+; OPT: BB11_6:
+; OPT: br              BB11_1{{$}}
+; OPT: BB11_7:
 define i32 @doublediamond_in_a_loop(i32 %a, i32 %b, i32* %p) {
 entry:
   br label %header
 header:
   %c = icmp eq i32 %a, 0
   %d = icmp eq i32 %b, 0
   store volatile i32 0, i32* %p
   br i1 %c, label %true, label %false

test/CodeGen/WebAssembly/reg-stackify.ll

 }
 
 ; Don't schedule stack uses into the stack. To reduce register pressure, the
 ; scheduler might be tempted to move the definition of $2 down. However, this
 ; would risk getting incorrect liveness if the instructions are later
 ; rearranged to make the stack contiguous.
 
 ; CHECK-LABEL: stack_uses:
-; CHECK-NEXT: .param i32{{$}}
+; CHECK-NEXT: .param i32, i32, i32, i32{{$}}
 ; CHECK-NEXT: .result i32{{$}}
-; CHECK-NEXT: local i32, i32{{$}}
-; CHECK-NEXT: i32.const       $1=, 1{{$}}
-; CHECK-NEXT: i32.const       $2=, 0{{$}}
-; CHECK-NEXT: i32.and         $push0=, $0, $1{{$}}
-; CHECK-NEXT: i32.eq          $push1=, $pop0, $2{{$}}
-; CHECK-NEXT: block           BB4_2{{$}}
-; CHECK-NEXT: br_if           $pop1, BB4_2{{$}}
-; CHECK-NEXT: return          $2{{$}}
-; CHECK-NEXT: BB4_2:{{$}}
-; CHECK-NEXT: return          $1{{$}}
-define i32 @stack_uses(i32 %x) {
+; CHECK-NEXT: .local i32, i32{{$}}
+; CHECK-NEXT: i32.const   $4=, 1{{$}}
+; CHECK-NEXT: i32.const   $5=, 2{{$}}
+; CHECK-NEXT: i32.lt_s    $push0=, $0, $4{{$}}
+; CHECK-NEXT: i32.lt_s    $push1=, $1, $5{{$}}
+; CHECK-NEXT: i32.xor     $push4=, $pop0, $pop1{{$}}
+; CHECK-NEXT: i32.lt_s    $push2=, $2, $4{{$}}
+; CHECK-NEXT: i32.lt_s    $push3=, $3, $5{{$}}
+; CHECK-NEXT: i32.xor     $push5=, $pop2, $pop3{{$}}
+; CHECK-NEXT: i32.xor     $push6=, $pop4, $pop5{{$}}
+; CHECK-NEXT: i32.ne      $push7=, $pop6, $4{{$}}
+; CHECK-NEXT: block       BB4_2{{$}}
+; CHECK-NEXT: br_if       $pop7, BB4_2{{$}}
+; CHECK-NEXT: i32.const   $push8=, 0{{$}}
+; CHECK-NEXT: return      $pop8{{$}}
+; CHECK-NEXT: BB4_2:
+; CHECK-NEXT: return      $4{{$}}
+define i32 @stack_uses(i32 %x, i32 %y, i32 %z, i32 %w) {
 entry:
-  %c = trunc i32 %x to i1
-  br i1 %c, label %true, label %false
+  %c = icmp sle i32 %x, 0
+  %d = icmp sle i32 %y, 1
+  %e = icmp sle i32 %z, 0
+  %f = icmp sle i32 %w, 1
+  %g = xor i1 %c, %d
+  %h = xor i1 %e, %f
+  %i = xor i1 %g, %h
+  br i1 %i, label %true, label %false
 true:
   ret i32 0
 false:
   ret i32 1
 }
 
 !0 = !{}

test/CodeGen/WebAssembly/switch.ll

-; RUN: llc < %s -asm-verbose=false | FileCheck %s
+; RUN: llc < %s -asm-verbose=false -disable-block-placement | FileCheck %s
 
-; Test switch instructions.
+; Test switch instructions. Block placement is disabled because it reorders
+; the blocks in a way that isn't interesting here.
 
 target datalayout = "e-p:32:32-i64:64-n32:64-S128"
 target triple = "wasm32-unknown-unknown"
 
 declare void @foo0()
 declare void @foo1()
 declare void @foo2()
 declare void @foo3()