[WebAssembly] CFG Stackifier

[sunfish]

Summary

This is a prototype of the CFG "stackifier" algorithm for creating structured control flow out of a CFG.

[sunfish]

• Implement switch statements
• Misc fixes

[sunfish]

• Rebase
• Include AsmPrinter.cpp change

[sunfish]

• add tests for interesting loop-with-split-backedge cases
• rewrite the successor sorting code to be more readable
• misc cleanups

[sunfish]

• include the AsmPrinter.h diff (again)

[jfb]

include/llvm/CodeGen/AsmPrinter.h

239 ↗

(On Diff #34456)

This should probably be in its own patch once this one is ready to go, just so other folks who care can notice it.

lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp

12

Could you have a bit of a longer description of what that means?

59

std::vector, or non-zero size.

68

Can this be Succs(MBB->successors())?

71

Could you explain the strategy? You leave me hanging!

88

It's a bit obvious, but it would be nice to have a comment here that says that A and B are now in the same loop depth. It doesn't mean it's the same loop, though! Would it make sense to check that too, and order them based on which of their loop heads is earlier in PO?

96

Could you also take into account "furthest from backedge" in ordering?
We can also be a bit silly by trying to line up similarly-conditioned diamonds the same way, but that requires keeping some more state around for previous conditions so I'm not sure it's worth it.

It also seems like you want a tie-breaker here, and that can be as arbitrary as the block name? Maybe also something about instructions contained, including "ends with a non-reachable instr".

What does this do with unlikely/cold/landingpad?

105

Expand on why we want that control.

108

4 seems pretty conservative for most functions! I'd do 16 as a random guess (though of course data would win here...).

122

This code is written as a test for itself? ;-)

[jfb]

A few more high-level comments...

lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp

131

Shouldn't this instead test for isConditionalBranch, not isBranch?

Also: conservatively, isInlineAsm?

lib/Target/WebAssembly/WebAssemblyInstrControl.td

53

Why (select Int64:$a? Isn't the condition just a bool, so Int32 suffices (as for the other types)?

61

Aggressive multiclass for SELECT?

lib/Target/WebAssembly/WebAssemblyInstrInfo.cpp

52

Why instructions can these be?

test/CodeGen/WebAssembly/cfg-stackify.ll

9 ↗

(On Diff #34456)

Add a test with:

• A single-block function.
• An empty block.
• Deeper nest.
• Back-to-back diamond.
• Diamonds in different loops.
• TODO on inline asm as a terminator (though wasm probably won't have it, good to know it's missing).
• TODO on landingpad.
• Some of the code deals with instructions after branches, it would be good to test these.

test/CodeGen/WebAssembly/switch.ll

6 ↗

(On Diff #34456)

TODO on testing computed goto.

[sunfish]

lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp

59

std::vector doesn't support Succs(MBB->successors()) below ;-).

88

Ah, this was just a thinko on my part. This code should just check the actual loop, not the loop depth.

96

I'm just trying to do something simple that does reasonable things in most cases right now. There will be plenty of time for tweaking this function.

Unlikely/cold are handled by MachineBlockPlacementID, and this pass attempts to respect that by preserving the original order of the blocks when it can. However, note that MachineBlockPlacementID is currently disabled; see the comments for details.

landingpad gets lowered away before we get here.

122

Ok, it's not hard to rewrite this code to avoid a goto for the benefit of people who make remarks like this, so I've now done that.

131

It needs to accept isBranch too because moving the block could mean that the branch should turn into a fallthrough.

LLVM doesn't support 'asm goto' so we can't get isInlineAsm here. I added a check and a report_fatal_error to catch cases like this in case they do get added though.

lib/Target/WebAssembly/WebAssemblyInstrControl.td

61

SELECT isn't really part of this patch, so I dropped it for now.

lib/Target/WebAssembly/WebAssemblyInstrInfo.cpp

52

switches, for example.

test/CodeGen/WebAssembly/cfg-stackify.ll

9 ↗

(On Diff #34456)

A single-block function.
An empty block.

We have these already.

Deeper nest.
Back-to-back diamond.
Diamonds in different loops.

Patches welcome. ;-)

TODO on inline asm as a terminator (though wasm probably won't have it, good to know it's missing).

There are no asm terminators in LLVM, so it's not possible get this right now. And, I added checking code which should catch this case in case LLVM ever adds them in the future.

TODO on landingpad.

The TODO is to set our ExceptionHandling type to something other than ExceptionHandling::None so that landingpad doesn't get stripped out entirely before it gets to this pass.

Some of the code deals with instructions after branches, it would be good to test these.

They deal with multiple terminators at the MachineBasicBlock level, which isn't exposed or testable from an LLVM IR unittest.

[sunfish]

• Update and post the patch from D12787

[sunfish]

Now with the correct version of the patch.

[jfb]

You should mark comments that are addressed as "done"!

lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp

59

Non-zero size then? Most blocks won't have more than 8 successors, and that's cheap to put on the stack compared to heap allocating!

96

Could you add TODOs for the things that make sense to try out?

You still want a final tie breaker though: as it stands the code breaks std::stable_sort's contract by having A < B and B < A both false!

[sunfish]

lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp

60

(Notice how this comment is no longer displayed anywhere near the code that it's about.)
(Am I supposed to check the Done box in my own comments too?)
(There's a weird bug in phabricator where the Done checkbox is modal and you can't always click it. I am attempting to work around it. Be aware of the lengths I am attempting to go for your benefit here.)

It's inside another vector, so making it zero size is nice because it means move constructing is trivial. However, it's not really that important since neither one of us has profiled this ;-).

97

Ok, I added a TODO.

stable_sort just wants a strict weak ordering. When A < B and B < A are both false, then stable_sort treats them as equal and orders them according to their original order.

109

When data arrives, we can update these accordingly.

test/CodeGen/WebAssembly/cfg-stackify.ll

10 ↗

(On Diff #34714)

FYI, I have added several more tests now.

test/CodeGen/WebAssembly/switch.ll

7 ↗

(On Diff #34714)

That would go in a new file, rather than switch.ll.

[sunfish]

• addressed jfb's comments

[jfb]

I think this is pretty good now. I like the approach as it reuses some LLVM infrastructure, and is overall simpler than the relooper. I'd like us to revisit and compare what we're missing from the relooper, but at this point in time we want to move things forward so I think this is a good start, and we'll do more comparative science later.

lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp

60

Much appreciated :-)

lib/Target/WebAssembly/WebAssemblyInstrControl.td

41

Shouldn't we support switch 64 on either architecture?

[sunfish]

• Allow SWITCH_I64 in wasm32 mode and vice versa, and add a TODO comment to actually make use of this.

[sunfish]

lib/Target/WebAssembly/WebAssemblyInstrControl.td

41

Good point. LLVM's jump table lowering forces the index to be pointer-sized, but we don't need that restriction. I fixed this, added a test, and added a TODO comment.

[jfb]

One small comment, then lgtm. As we discussed offline, I'll unhook D12744 and commit it, since we'll probably want a hybrid approach for a while (or at least compare approaches).

lib/Target/WebAssembly/WebAssemblyISelLowering.cpp

159

Shouldn't the above be in a separate patch, since you removed select handling?

lib/Target/WebAssembly/CMakeLists.txt

 set(LLVM_TARGET_DEFINITIONS WebAssembly.td)
 
 tablegen(LLVM WebAssemblyGenAsmWriter.inc -gen-asm-writer)
 tablegen(LLVM WebAssemblyGenDAGISel.inc -gen-dag-isel)
 tablegen(LLVM WebAssemblyGenFastISel.inc -gen-fast-isel)
 tablegen(LLVM WebAssemblyGenInstrInfo.inc -gen-instr-info)
 tablegen(LLVM WebAssemblyGenMCCodeEmitter.inc -gen-emitter)
 tablegen(LLVM WebAssemblyGenRegisterInfo.inc -gen-register-info)
 tablegen(LLVM WebAssemblyGenSubtargetInfo.inc -gen-subtarget)
 add_public_tablegen_target(WebAssemblyCommonTableGen)
 
 add_llvm_target(WebAssemblyCodeGen
   Relooper.cpp
   WebAssemblyAsmPrinter.cpp
+  WebAssemblyCFGStackify.cpp
   WebAssemblyFastISel.cpp
   WebAssemblyFrameLowering.cpp
   WebAssemblyISelDAGToDAG.cpp
   WebAssemblyISelLowering.cpp
   WebAssemblyInstrInfo.cpp
   WebAssemblyMachineFunctionInfo.cpp
   WebAssemblyRegisterInfo.cpp
   WebAssemblySelectionDAGInfo.cpp

lib/Target/WebAssembly/WebAssembly.h

 namespace llvm {
 
 class WebAssemblyTargetMachine;
 class FunctionPass;
 
 FunctionPass *createWebAssemblyISelDag(WebAssemblyTargetMachine &TM,
                                        CodeGenOpt::Level OptLevel);
 
+FunctionPass *createWebAssemblyCFGStackify();
+
 } // end namespace llvm
 
 #endif

lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp

+//===-- WebAssemblyCFGStackify.cpp - CFG Stackification -------------------===//
+//
+//                     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 implements a CFG stacking pass.
+///
+//===----------------------------------------------------------------------===//
+
+#include "WebAssembly.h"
+#include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
+#include "WebAssemblySubtarget.h"
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/CodeGen/MachineLoopInfo.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-stackify"
+
+namespace {
+class WebAssemblyCFGStackify final : public MachineFunctionPass {
+public:
+  static char ID; // Pass identification, replacement for typeid
+  WebAssemblyCFGStackify() : MachineFunctionPass(ID) {}
+
+private:
+  const char *getPassName() const override {
+    return "WebAssembly CFG Stackify";
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.setPreservesCFG();
+    AU.addRequired<MachineLoopInfo>();
+    AU.addPreserved<MachineLoopInfo>();
+    MachineFunctionPass::getAnalysisUsage(AU);
+  }
+
+  bool runOnMachineFunction(MachineFunction &MF) override;
+};
+} // end anonymous namespace
+
+char WebAssemblyCFGStackify::ID = 0;
+FunctionPass *llvm::createWebAssemblyCFGStackify() {
+  return new WebAssemblyCFGStackify();
+}
+
+static bool IsNext(MachineBasicBlock *M, MachineBasicBlock *N) {
+  return next(MachineFunction::iterator(M)) == MachineFunction::iterator(N);
+}
+
+namespace {
+struct RPOStackEntry {
+  MachineBasicBlock *MBB;
+  SmallVector<MachineBasicBlock *, 0> Succs;
+
+  RPOStackEntry(MachineBasicBlock *MBB, const MachineLoopInfo &MLI) : MBB(MBB) {
+    // RPO is not a unique form, since at every basic block with multiple
+    // successors, the DFS has to pick which order to visit the successors in.
+    // This code attempts to order the successors strategically.
+    //
+    // FIXME: Right now this is some hackish code that attempts to sort the
+    // successors to make loops contiguous and to prefer to keep blocks in
+    // existing layout order when possible.
+    unsigned Depth = MLI.getLoopDepth(MBB);
+    for (auto Succ : MBB->successors())
+      if (MLI.getLoopDepth(Succ) != Depth && IsNext(MBB, Succ))
+        Succs.push_back(Succ);
+    for (auto Succ : MBB->successors())
+      if (MLI.getLoopDepth(Succ) != Depth && !IsNext(MBB, Succ))
+        Succs.push_back(Succ);
+    for (auto Succ : MBB->successors())
+      if (MLI.getLoopDepth(Succ) == Depth && IsNext(MBB, Succ))
+        Succs.push_back(Succ);
+    for (auto Succ : MBB->successors())
+      if (MLI.getLoopDepth(Succ) == Depth && !IsNext(MBB, Succ))
+        Succs.push_back(Succ);
+  }
+};
+}
+
+// Sort the blocks in RPO, taking special care to make sure that loops are
+// contiguous even in the case of split backedges.
+static void SortBlocks(MachineFunction &MF, const MachineLoopInfo &MLI) {
+  SmallPtrSet<MachineBasicBlock *, 4> Visited;
+  SmallVector<RPOStackEntry, 4> Stack;
+
+  MachineBasicBlock *Entry = MF.begin();
+  Stack.push_back(RPOStackEntry(Entry, MLI));
+  Visited.insert(Entry);
+
+  do {
+  top:
+    RPOStackEntry &Entry = Stack.back();
+    SmallVectorImpl<MachineBasicBlock *> &Succs = Entry.Succs;
+    if (!Succs.empty()) {
+      MachineBasicBlock *Succ = Succs.pop_back_val();
+      if (Visited.insert(Succ).second)
+        Stack.push_back(RPOStackEntry(Succ, MLI));
+      goto top;
+    }
+    MachineBasicBlock *MBB = Entry.MBB;
+    MBB->moveBefore(MF.begin());
+    MBB->updateTerminator();
+    Stack.pop_back();
+  } while (!Stack.empty());
+}
+
+static void PlaceMarkers(MachineFunction &MF, const MachineLoopInfo &MLI,
+                         const WebAssemblyInstrInfo *TII) {
+  for (auto &MBB : MF) {
+    // Place the LOOP for a loop.
+    if (MachineLoop *Loop = MLI.getLoopFor(&MBB)) {
+      MachineBasicBlock *Top = Loop->getTopBlock();
+      assert(Loop->getHeader() == Top);
+      if (Top == &MBB)
+        BuildMI(*Top, Top->begin(), DebugLoc(), TII->get(WebAssembly::LOOP))
+            .addMBB(Loop->getBottomBlock());
+    }
+
+    // Check for forward branches to handle.
+    for (auto &Term : MBB.terminators()) {
+      switch (Term.getOpcode()) {
+      case WebAssembly::BR:
+      case WebAssembly::BRIF: {
+        MachineBasicBlock *Succ = Term.getOperand(0).getMBB();
+        if (Succ->getNumber() > MBB.getNumber()) {
+          // Place the BLOCK for a forward branch.
+          MachineLoop *Loop = MLI.getLoopFor(Succ);
+          MachineBasicBlock *Header = Loop ? Loop->getHeader() : &MF.front();
+          MachineBasicBlock::iterator I = Header->begin();
+          if (I->getOpcode() == WebAssembly::LOOP)
+            ++I;
+          int SuccNumber = Succ->getNumber();
+          // Position the BLOCK in nesting order.
+          while (I->getOpcode() == WebAssembly::BLOCK) {
+            int N = I->getOperand(0).getMBB()->getNumber();
+            if (N < SuccNumber)
+              break;
+            // If there's already a BLOCK for Succ, we don't need another.
+            if (N == SuccNumber)
+              goto skip_block;
+            ++I;
+          }
+
+          BuildMI(*Header, I, DebugLoc(), TII->get(WebAssembly::BLOCK))
+              .addMBB(Succ);
+        }
+      skip_block:;
+        break;
+      }
+      case WebAssembly::RETURN_VOID:
+      case WebAssembly::RETURN_Int32:
+      case WebAssembly::RETURN_Float32:
+      case WebAssembly::RETURN_Int64:
+      case WebAssembly::RETURN_Float64:
+        break;
+      default:
+        llvm_unreachable("unhandled terminator");
+      }
+    }
+  }
+}
+
+bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) {
+  DEBUG(dbgs() << "********** CFG Stackifying **********\n"
+                  "********** Function: "
+               << MF.getName() << '\n');
+
+  const MachineLoopInfo &MLI = getAnalysis<MachineLoopInfo>();
+  const auto *TII = MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
+
+  // Sort the blocks in RPO, with contiguous loops.
+  SortBlocks(MF, MLI);
+
+  // Now that we've sorted the blocks in RPO, renumber them.
+  MF.RenumberBlocks();
+
+  // Place the BLOCK and LOOP markers to indicate the beginnings of scopes.
+  PlaceMarkers(MF, MLI, TII);
+
+  return true;
+}

lib/Target/WebAssembly/WebAssemblyISD.def

 
 // NOTE: NO INCLUDE GUARD DESIRED!
 
 HANDLE_NODETYPE(CALL1)
 HANDLE_NODETYPE(CALL0)
 HANDLE_NODETYPE(RETURN)
 HANDLE_NODETYPE(ARGUMENT)
 HANDLE_NODETYPE(Wrapper)
+HANDLE_NODETYPE(BRIF)
 
 // add memory opcodes starting at ISD::FIRST_TARGET_MEMORY_OPCODE here...

lib/Target/WebAssembly/WebAssemblyISelLowering.cpp

WebAssemblyTargetLowering::WebAssemblyTargetLowering(
   for (auto T : {MVT::i1, MVT::i8, MVT::i16})
     setOperationAction(ISD::SIGN_EXTEND_INREG, T, Expand);
 
   // Dynamic stack allocation: use the default expansion.
   setOperationAction(ISD::STACKSAVE, MVT::Other, Expand);
   setOperationAction(ISD::STACKRESTORE, MVT::Other, Expand);
   setOperationAction(ISD::DYNAMIC_STACKALLOC, MVTPtr, Expand);
 
+  // Expand these forms; we pattern-match the forms that we can handle in isel.
+  setOperationAction(ISD::BR_JT, MVT::Other, Expand);
+  for (auto T : {MVT::i32, MVT::i64, MVT::f32, MVT::f64})
+    for (auto Op : {ISD::BR_CC, ISD::SELECT_CC})
+      setOperationAction(Op, T, Expand);
+
   // WebAssembly doesn't have:
   //  - Floating-point extending loads.
   //  - Floating-point truncating stores.
   //  - i1 extending loads.
   setLoadExtAction(ISD::EXTLOAD, MVT::f32, MVT::f64, Expand);
   setTruncStoreAction(MVT::f64, MVT::f32, Expand);
   for (auto T : MVT::integer_valuetypes())
     for (auto Ext : {ISD::EXTLOAD, ISD::ZEXTLOAD, ISD::SEXTLOAD})

lib/Target/WebAssembly/WebAssemblyInstrControl.td

  * do_while: do while statement, basically a loop with a conditional branch
  * forever: infinite loop statement (like while (1)), basically an unconditional
  *          branch (back to the top of the loop)
  * continue: continue to start of nested loop
  * break: break to end from nested loop or block
  * switch: switch statement with fallthrough
  */
 
+let isBranch = 1, isTerminator = 1, hasCtrlDep = 1 in {
+def BRIF : I<(outs), (ins bb_op:$dst, Int32:$a),
+             [(brcond Int32:$a, bb:$dst)]>;
+let isBarrier = 1 in
+def BR   : I<(outs), (ins bb_op:$dst),
+             [(br bb:$dst)]>;
+} // isBranch = 1, isTerminator = 1, hasCtrlDep = 1
+
+def BLOCK     : I<(outs), (ins bb_op:$dst), []>;
+def LOOP      : I<(outs), (ins bb_op:$dst), []>;
+
 multiclass RETURN<WebAssemblyRegClass vt> {
   def RETURN_#vt : I<(outs), (ins vt:$val), [(WebAssemblyreturn vt:$val)]>;
 }
 let isReturn = 1, isTerminator = 1, hasCtrlDep = 1, isBarrier = 1 in {
   defm : RETURN<Int32>;
   defm : RETURN<Int64>;
   defm : RETURN<Float32>;
   defm : RETURN<Float64>;
   def RETURN_VOID : I<(outs), (ins), [(WebAssemblyreturn)]>;
 } // isReturn = 1, isTerminator = 1, hasCtrlDep = 1, isBarrier = 1
+
+def SELECT_I32 : I<(outs Int32:$dst), (ins Int32:$a, Int32:$t, Int32:$f),
+                   [(set Int32:$dst, (select Int32:$a, Int32:$t, Int32:$f))]>;
+def SELECT_I64 : I<(outs Int64:$dst), (ins Int64:$a, Int64:$t, Int64:$f),
+                   [(set Int64:$dst, (select Int64:$a, Int64:$t, Int64:$f))]>;
+def SELECT_F32 : I<(outs Float32:$dst),
+                   (ins Int32:$a, Float32:$lhs, Float32:$rhs),
+                   [(set Float32:$dst,
+                         (select Int32:$a, Float32:$lhs, Float32:$rhs))]>;
+def SELECT_F64 : I<(outs Float64:$dst),
+                   (ins Int32:$a, Float64:$lhs, Float64:$rhs),
+                   [(set Float64:$dst,
+                         (select Int32:$a, Float64:$lhs, Float64:$rhs))]>;

lib/Target/WebAssembly/WebAssemblyInstrInfo.h

 public:
   explicit WebAssemblyInstrInfo(const WebAssemblySubtarget &STI);
 
   const WebAssemblyRegisterInfo &getRegisterInfo() const { return RI; }
 
   void copyPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI,
                    DebugLoc DL, unsigned DestReg, unsigned SrcReg,
                    bool KillSrc) const override;
+
+  bool AnalyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB,
+                     MachineBasicBlock *&FBB,
+                     SmallVectorImpl<MachineOperand> &Cond,
+                     bool AllowModify = false) const override;
+  unsigned RemoveBranch(MachineBasicBlock &MBB) const override;
+  unsigned InsertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB,
+                        MachineBasicBlock *FBB,
+                        ArrayRef<MachineOperand> Cond,
+                        DebugLoc DL) const override;
+  bool
+  ReverseBranchCondition(SmallVectorImpl<MachineOperand> &Cond) const override;
 };
 
 } // end namespace llvm
 
 #endif

lib/Target/WebAssembly/WebAssemblyInstrInfo.cpp

 
 void WebAssemblyInstrInfo::copyPhysReg(MachineBasicBlock &MBB,
                                        MachineBasicBlock::iterator I,
                                        DebugLoc DL, unsigned DestReg,
                                        unsigned SrcReg, bool KillSrc) const {
   BuildMI(MBB, I, DL, get(WebAssembly::COPY), DestReg)
       .addReg(SrcReg, KillSrc ? RegState::Kill : 0);
 }
+
+// Branch analysis.
+bool WebAssemblyInstrInfo::AnalyzeBranch(MachineBasicBlock &MBB,
+                                         MachineBasicBlock *&TBB,
+                                         MachineBasicBlock *&FBB,
+                                         SmallVectorImpl<MachineOperand> &Cond,
+                                         bool AllowModify) const {
+  bool HaveCond = false;
+  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::BRIF:
+      if (HaveCond)
+        return true;
+      Cond.push_back(MI.getOperand(1));
+      TBB = MI.getOperand(0).getMBB();
+      HaveCond = true;
+      break;
+    case WebAssembly::BR:
+      if (!HaveCond)
+        TBB = MI.getOperand(0).getMBB();
+      else
+        FBB = MI.getOperand(0).getMBB();
+      break;
+    }
+    if (MI.isBarrier())
+      break;
+  }
+
+  return false;
+}
+
+unsigned WebAssemblyInstrInfo::RemoveBranch(MachineBasicBlock &MBB) const {
+  MachineBasicBlock::instr_iterator I = MBB.instr_end();
+  unsigned Count = 0;
+
+  while (I != MBB.instr_begin()) {
+    --I;
+    if (I->isDebugValue())
+      continue;
+    if (!I->isTerminator())
+      break;
+    // Remove the branch.
+    I->eraseFromParent();
+    I = MBB.instr_end();
+    ++Count;
+  }
+
+  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::BRIF))
+      .addMBB(TBB)
+      .addOperand(Cond[0]);
+  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;
+}

lib/Target/WebAssembly/WebAssemblyInstrInfo.td

 
 /*
  * TODO(jfb): Add the following.
  *
  * get_local: read the current value of a local variable
  * set_local: set the current value of a local variable
 */
 
+def bb_op : Operand<OtherVT>;
 def global : Operand<iPTR>;
 
 //===----------------------------------------------------------------------===//
 // WebAssembly Instruction Format Definitions.
 //===----------------------------------------------------------------------===//
 
 include "WebAssemblyInstrFormats.td"
 

lib/Target/WebAssembly/WebAssemblyTargetMachine.cpp

 void WebAssemblyPassConfig::addPostRegAlloc() {
   // FIXME: the following passes dislike virtual registers. Disable them for now
   //        so that basic tests can pass. Future patches will remedy this.
   //
   // Fails with: Regalloc must assign all vregs.
   disablePass(&PrologEpilogCodeInserterID);
   // Fails with: should be run after register allocation.
   disablePass(&MachineCopyPropagationID);
+
+  // FIXME: Until we get ReverseBranchCondition support, MachineBlockPlacement
+  // can create ugly-looking control flow.
+  disablePass(&MachineBlockPlacementID);
 }
 
 void WebAssemblyPassConfig::addPreSched2() {}
 
-void WebAssemblyPassConfig::addPreEmitPass() {}
+void WebAssemblyPassConfig::addPreEmitPass() {
+  addPass(createWebAssemblyCFGStackify());
+}

test/CodeGen/WebAssembly/phi.ll

 ; RUN: llc < %s -asm-verbose=false | FileCheck %s
 
-; This test depends on branching support, which is not yet checked in.
-; XFAIL: *
-
 ; Test that phis are lowered.
 
 target datalayout = "e-p:32:32-i64:64-v128:8:128-n32:64-S128"
 target triple = "wasm32-unknown-unknown"
 
 ; Basic phi triangle.
 
 ; CHECK-LABEL: test0