[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

61

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

69

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

7

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

69

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

8

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

161

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/WebAssemblyAsmPrinter.cpp

private:
   }
 
   //===------------------------------------------------------------------===//
   // AsmPrinter Implementation.
   //===------------------------------------------------------------------===//
 
   void EmitGlobalVariable(const GlobalVariable *GV) override;
 
+  void EmitJumpTableInfo() override;
   void EmitConstantPool() override;
   void EmitFunctionEntryLabel() override;
   void EmitFunctionBodyStart() override;
   void EmitFunctionBodyEnd() override;
 
   void EmitInstruction(const MachineInstr *MI) override;
 };
 
void WebAssemblyAsmPrinter::EmitGlobalVariable(const GlobalVariable *GV) {
   OutStreamer->EmitRawText(OS.str());
 }
 
 void WebAssemblyAsmPrinter::EmitConstantPool() {
   assert(MF->getConstantPool()->getConstants().empty() &&
          "WebAssembly disables constant pools");
 }
 
+void WebAssemblyAsmPrinter::EmitJumpTableInfo() {
+  // Nothing to do; jump tables are incorporated into the instruction stream.
+}
+
 void WebAssemblyAsmPrinter::EmitFunctionEntryLabel() {
   SmallString<128> Str;
   raw_svector_ostream OS(Str);
 
   CurrentFnSym->redefineIfPossible();
 
   // The function label could have already been emitted if two symbols end up
   // conflicting due to asm renaming.  Detect this and emit an error.
for (const MachineOperand &MO : MI->uses())
         OS << ' ' << MO.getImm();
       } break;
       case MachineOperand::MO_FPImmediate: {
         OS << ' ' << toString(MO.getFPImm()->getValueAPF());
       } break;
       case MachineOperand::MO_GlobalAddress: {
         OS << ' ' << toSymbol(MO.getGlobal()->getName());
       } break;
+      case MachineOperand::MO_MachineBasicBlock: {
+        OS << ' ' << toSymbol(MO.getMBB()->getSymbol()->getName());
+      } break;
       }
     OS << ')';
   }
 
   if (NumDefs != 0)
     OS << ')';
 
   OutStreamer->EmitRawText(OS.str());
 }
 
 // Force static initialization.
 extern "C" void LLVMInitializeWebAssemblyAsmPrinter() {
   RegisterAsmPrinter<WebAssemblyAsmPrinter> X(TheWebAssemblyTarget32);
   RegisterAsmPrinter<WebAssemblyAsmPrinter> Y(TheWebAssemblyTarget64);
 }

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());
+    // Branch instructions may utilize a fallthrough, so update them if a
+    // fallthrough has been added or removed.
+    if (MBB->back().isBranch())
+      MBB->updateTerminator();
+    Stack.pop_back();
+  } while (!Stack.empty());
+}
+
+static void PlaceBlockMarkers(MachineBasicBlock *MBB, MachineBasicBlock *Succ,
+                              MachineFunction &MF,
+                              const MachineLoopInfo &MLI,
+                              const WebAssemblyInstrInfo *TII) {
+  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.
+    for (; I->getOpcode() == WebAssembly::BLOCK; ++I) {
+      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)
+        return;
+    }
+
+    BuildMI(*Header, I, DebugLoc(), TII->get(WebAssembly::BLOCK)).addMBB(Succ);
+  }
+}
+
+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 and switches to handle.
+    for (auto &Term : MBB.terminators())
+      for (auto &MO : Term.operands())
+        if (MO.isMBB())
+          PlaceBlockMarkers(&MBB, MO.getMBB(), MF, MLI, TII);
+  }
+}
+
+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)
+HANDLE_NODETYPE(SWITCH)
 
 // add memory opcodes starting at ISD::FIRST_TARGET_MEMORY_OPCODE here...

lib/Target/WebAssembly/WebAssemblyISelLowering.h

SDValue LowerFormalArguments(SDValue Chain, CallingConv::ID CallConv,
                                bool IsVarArg,
                                const SmallVectorImpl<ISD::InputArg> &Ins,
                                SDLoc DL, SelectionDAG &DAG,
                                SmallVectorImpl<SDValue> &InVals) const override;
 
   // Custom lowering hooks.
   SDValue LowerOperation(SDValue Op, SelectionDAG &DAG) const override;
   SDValue LowerGlobalAddress(SDValue Op, SelectionDAG &DAG) const;
+  SDValue LowerBR_JT(SDValue Op, SelectionDAG &DAG) const;
+  SDValue LowerJumpTable(SDValue Op, SelectionDAG &DAG) const;
 };
 
 namespace WebAssembly {
 FastISel *createFastISel(FunctionLoweringInfo &funcInfo,
                          const TargetLibraryInfo *libInfo);
 } // end namespace WebAssembly
 
 } // end namespace llvm
 
 #endif

lib/Target/WebAssembly/WebAssemblyISelLowering.cpp

 #include "WebAssemblyISelLowering.h"
 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
 #include "WebAssemblyMachineFunctionInfo.h"
 #include "WebAssemblySubtarget.h"
 #include "WebAssemblyTargetMachine.h"
 #include "WebAssemblyTargetObjectFile.h"
 #include "llvm/CodeGen/Analysis.h"
 #include "llvm/CodeGen/CallingConvLower.h"
+#include "llvm/CodeGen/MachineJumpTableInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/SelectionDAG.h"
 #include "llvm/IR/DiagnosticInfo.h"
 #include "llvm/IR/DiagnosticPrinter.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
WebAssemblyTargetLowering::WebAssemblyTargetLowering(
   addRegisterClass(MVT::i32, &WebAssembly::Int32RegClass);
   addRegisterClass(MVT::i64, &WebAssembly::Int64RegClass);
   addRegisterClass(MVT::f32, &WebAssembly::Float32RegClass);
   addRegisterClass(MVT::f64, &WebAssembly::Float64RegClass);
   // Compute derived properties from the register classes.
   computeRegisterProperties(Subtarget->getRegisterInfo());
 
   setOperationAction(ISD::GlobalAddress, MVTPtr, Custom);
+  setOperationAction(ISD::JumpTable, MVTPtr, Custom);
 
   for (auto T : {MVT::f32, MVT::f64}) {
     // Don't expand the floating-point types to constant pools.
     setOperationAction(ISD::ConstantFP, T, Legal);
     // Expand floating-point comparisons.
     for (auto CC : {ISD::SETO, ISD::SETUO, ISD::SETUEQ, ISD::SETONE,
                     ISD::SETULT, ISD::SETULE, ISD::SETUGT, ISD::SETUGE})
       setCondCodeAction(CC, T, Expand);
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.
+  for (auto T : {MVT::i32, MVT::i64, MVT::f32, MVT::f64})
+    for (auto Op : {ISD::BR_CC, ISD::SELECT_CC})
+      setOperationAction(Op, T, Expand);
+
+  // We have custom switch handling.
+  setOperationAction(ISD::BR_JT, MVT::Other, Custom);
+
   // 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})

 SDValue WebAssemblyTargetLowering::LowerOperation(SDValue Op,
                                                   SelectionDAG &DAG) const {
   switch (Op.getOpcode()) {
   default:
     llvm_unreachable("unimplemented operation lowering");
     return SDValue();
   case ISD::GlobalAddress:
     return LowerGlobalAddress(Op, DAG);
+  case ISD::JumpTable:
+    return LowerJumpTable(Op, DAG);
+  case ISD::BR_JT:
+    return LowerBR_JT(Op, DAG);
   }
 }
 
 SDValue WebAssemblyTargetLowering::LowerGlobalAddress(SDValue Op,
                                                       SelectionDAG &DAG) const {
   SDLoc DL(Op);
   const auto *GA = cast<GlobalAddressSDNode>(Op);
   EVT VT = Op.getValueType();
   assert(GA->getOffset() == 0 &&
          "offsets on global addresses are forbidden by isOffsetFoldingLegal");
   assert(GA->getTargetFlags() == 0 && "WebAssembly doesn't set target flags");
   if (GA->getAddressSpace() != 0)
     fail(DL, DAG, "WebAssembly only expects the 0 address space");
   return DAG.getNode(WebAssemblyISD::Wrapper, DL, VT,
                      DAG.getTargetGlobalAddress(GA->getGlobal(), DL, VT));
 }
 
+SDValue WebAssemblyTargetLowering::LowerJumpTable(SDValue Op,
+                                                  SelectionDAG &DAG) const {
+  // There's no need for a Wrapper node because we always incorporate a jump
+  // table operand into a SWITCH instruction, rather than ever materializing
+  // it in a register.
+  const JumpTableSDNode *JT = cast<JumpTableSDNode>(Op);
+  return DAG.getTargetJumpTable(JT->getIndex(), Op.getValueType(),
+                                JT->getTargetFlags());
+}
+
+SDValue WebAssemblyTargetLowering::LowerBR_JT(SDValue Op,
+                                              SelectionDAG &DAG) const {
+  SDLoc DL(Op);
+  SDValue Chain = Op.getOperand(0);
+  const auto *JT = cast<JumpTableSDNode>(Op.getOperand(1));
+  SDValue Index = Op.getOperand(2);
+  assert(JT->getTargetFlags() == 0 && "WebAssembly doesn't set target flags");
+
+  SmallVector<SDValue, 8> Ops;
+  Ops.push_back(Chain);
+  Ops.push_back(Index);
+
+  MachineJumpTableInfo *MJTI = DAG.getMachineFunction().getJumpTableInfo();
+  const auto &MBBs = MJTI->getJumpTables()[JT->getIndex()].MBBs;
+
+  // FIXME: 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]));
+
+  // Add an operand for each case.
+  for (auto MBB : MBBs)
+    Ops.push_back(DAG.getBasicBlock(MBB));
+
+  return DAG.getNode(WebAssemblyISD::SWITCH, DL, MVT::Other, Ops);
+}
+
 //===----------------------------------------------------------------------===//
 //                          WebAssembly Optimization Hooks
 //===----------------------------------------------------------------------===//
 
 MCSection *WebAssemblyTargetObjectFile::SelectSectionForGlobal(
     const GlobalValue *GV, SectionKind Kind, Mangler &Mang,
     const TargetMachine &TM) const {
   return getDataSection();
 }

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)]>;
+} // isBarrier = 1
+} // isBranch = 1, isTerminator = 1, hasCtrlDep = 1
+
+let isTerminator = 1, hasCtrlDep = 1, isBarrier = 1 in {
+def SWITCH_I32 : I<(outs), (ins Int32:$index, variable_ops),
+                   [(WebAssemblyswitch Int32:$index)]>, Requires<[HasAddr32]>;
+def SWITCH_I64 : I<(outs), (ins Int64:$index, variable_ops),
+                   [(WebAssemblyswitch Int64:$index)]>, Requires<[HasAddr64]>;
+} // isTerminator = 1, hasCtrlDep = 1, isBarrier = 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

 // WebAssembly-specific DAG Node Types.
 //===----------------------------------------------------------------------===//
 
 def SDT_WebAssemblyCallSeqStart : SDCallSeqStart<[SDTCisVT<0, iPTR>]>;
 def SDT_WebAssemblyCallSeqEnd :
     SDCallSeqEnd<[SDTCisVT<0, iPTR>, SDTCisVT<1, iPTR>]>;
 def SDT_WebAssemblyCall0    : SDTypeProfile<0, -1, [SDTCisPtrTy<0>]>;
 def SDT_WebAssemblyCall1    : SDTypeProfile<1, -1, [SDTCisPtrTy<1>]>;
+def SDT_WebAssemblySwitch   : SDTypeProfile<0, -1, [SDTCisPtrTy<0>]>;
 def SDT_WebAssemblyArgument : SDTypeProfile<1, 1, [SDTCisVT<1, i32>]>;
 def SDT_WebAssemblyReturn   : SDTypeProfile<0, -1, []>;
 def SDT_WebAssemblyWrapper  : SDTypeProfile<1, 1, [SDTCisSameAs<0, 1>,
                                                    SDTCisPtrTy<0>]>;
 
 //===----------------------------------------------------------------------===//
 // WebAssembly-specific DAG Nodes.
 //===----------------------------------------------------------------------===//
 
 def WebAssemblycallseq_start :
     SDNode<"ISD::CALLSEQ_START", SDT_WebAssemblyCallSeqStart,
            [SDNPHasChain, SDNPOutGlue]>;
 def WebAssemblycallseq_end :
     SDNode<"ISD::CALLSEQ_END", SDT_WebAssemblyCallSeqEnd,
            [SDNPHasChain, SDNPOptInGlue, SDNPOutGlue]>;
 def WebAssemblycall0 : SDNode<"WebAssemblyISD::CALL0",
                               SDT_WebAssemblyCall0,
                               [SDNPHasChain, SDNPVariadic]>;
 def WebAssemblycall1 : SDNode<"WebAssemblyISD::CALL1",
                               SDT_WebAssemblyCall1,
                               [SDNPHasChain, SDNPVariadic]>;
+def WebAssemblyswitch : SDNode<"WebAssemblyISD::SWITCH",
+                               SDT_WebAssemblySwitch,
+                               [SDNPHasChain, SDNPVariadic]>;
 def WebAssemblyargument : SDNode<"WebAssemblyISD::ARGUMENT",
                                  SDT_WebAssemblyArgument>;
 def WebAssemblyreturn   : SDNode<"WebAssemblyISD::RETURN",
                                  SDT_WebAssemblyReturn, [SDNPHasChain]>;
 def WebAssemblywrapper  : SDNode<"WebAssemblyISD::Wrapper",
                                  SDT_WebAssemblyWrapper>;
 
 //===----------------------------------------------------------------------===//
 // WebAssembly-specific Operands.
 //===----------------------------------------------------------------------===//
 
 /*
  * 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 tjumptable_op : Operand<iPTR>;
 def global : Operand<iPTR>;
 
 //===----------------------------------------------------------------------===//
 // WebAssembly Instruction Format Definitions.
 //===----------------------------------------------------------------------===//
 
 include "WebAssemblyInstrFormats.td"
 
def Immediate_I32 : I<(outs Int32:$res), (ins i32imm:$imm),
                       [(set Int32:$res, imm:$imm)]>;
 def Immediate_I64 : I<(outs Int64:$res), (ins i64imm:$imm),
                       [(set Int64:$res, imm:$imm)]>;
 def Immediate_F32 : I<(outs Float32:$res), (ins f32imm:$imm),
                       [(set Float32:$res, fpimm:$imm)]>;
 def Immediate_F64 : I<(outs Float64:$res), (ins f64imm:$imm),
                       [(set Float64:$res, fpimm:$imm)]>;
 
-// Special types of immediates.
+// Special types of immediates. FIXME: Hard-coded as 32-bit for now.
 def GLOBAL : I<(outs Int32:$dst), (ins global:$addr),
                [(set Int32:$dst, (WebAssemblywrapper tglobaladdr:$addr))]>;
+def JUMP_TABLE : I<(outs Int32:$dst), (ins tjumptable_op:$addr),
+                   [(set Int32:$dst, (WebAssemblywrapper tjumptable:$addr))]>;
 
 //===----------------------------------------------------------------------===//
 // Additional sets of instructions.
 //===----------------------------------------------------------------------===//
 
 include "WebAssemblyInstrMemory.td"
 include "WebAssemblyInstrCall.td"
 include "WebAssemblyInstrControl.td"
 include "WebAssemblyInstrInteger.td"
 include "WebAssemblyInstrFloat.td"
 include "WebAssemblyInstrConv.td"
 include "WebAssemblyInstrAtomics.td"
 include "WebAssemblyInstrSIMD.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-n32:64-S128"
 target triple = "wasm32-unknown-unknown"
 
 ; Basic phi triangle.
 
 ; CHECK-LABEL: test0

 done:
   %s = phi i32 [ %a, %true ], [ %p, %entry ]
   ret i32 %s
 }
 
 ; Swap phis.
 
 ; CHECK-LABEL: test1
-; CHECK: BB0_1:
+; CHECK: BB1_1:
 ; CHECK: (setlocal [[REG0:@.*]] [[REG1:@.*]])
 ; CHECK: (setlocal [[REG1]] [[REG2:@.*]])
 ; CHECK: (setlocal [[REG2]] [[REG0]])
 define i32 @test1(i32 %n) {
 entry:
   br label %loop
 
 loop:

test/CodeGen/WebAssembly/switch.ll

+; RUN: llc < %s -asm-verbose=false | FileCheck %s
+
+; Test switch instructions.
+
+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()
+declare void @foo4()
+declare void @foo5()
+
+; CHECK-LABEL: bar
+; CHECK: (block $BB0_8)
+; CHECK: (block $BB0_7)
+; CHECK: (block $BB0_6)
+; CHECK: (block $BB0_5)
+; CHECK: (block $BB0_4)
+; CHECK: (block $BB0_3)
+; CHECK: (block $BB0_2)
+; CHECK: (switch {{.*}} $BB0_2 $BB0_2 $BB0_2 $BB0_2 $BB0_2 $BB0_2 $BB0_2 $BB0_2 $BB0_3 $BB0_3 $BB0_3 $BB0_3 $BB0_3 $BB0_3 $BB0_3 $BB0_3 $BB0_4 $BB0_4 $BB0_4 $BB0_4 $BB0_4 $BB0_4 $BB0_5 $BB0_6 $BB0_7)
+; CHECk: BB0_2:
+; CHECK:   (setlocal {{.*}} (global $foo0))
+; CHECK: BB0_3:
+; CHECK:   (setlocal {{.*}} (global $foo1))
+; CHECK: BB0_4:
+; CHECK:   (setlocal {{.*}} (global $foo2))
+; CHECK: BB0_5:
+; CHECK:   (setlocal {{.*}} (global $foo3))
+; CHECK: BB0_6:
+; CHECK:   (setlocal {{.*}} (global $foo4))
+; CHECK: BB0_7:
+; CHECK:   (setlocal {{.*}} (global $foo5))
+; CHECK: BB0_8:
+; CHECK:   (return)
+define void @bar(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
+    i32 4, label %sw.bb
+    i32 5, label %sw.bb
+    i32 6, label %sw.bb
+    i32 7, label %sw.bb.1
+    i32 8, label %sw.bb.1
+    i32 9, label %sw.bb.1
+    i32 10, label %sw.bb.1
+    i32 11, label %sw.bb.1
+    i32 12, label %sw.bb.1
+    i32 13, label %sw.bb.1
+    i32 14, label %sw.bb.1
+    i32 15, label %sw.bb.2
+    i32 16, label %sw.bb.2
+    i32 17, label %sw.bb.2
+    i32 18, label %sw.bb.2
+    i32 19, label %sw.bb.2
+    i32 20, label %sw.bb.2
+    i32 21, label %sw.bb.3
+    i32 22, label %sw.bb.4
+    i32 23, label %sw.bb.5
+  ]
+
+sw.bb:                                            ; preds = %entry, %entry, %entry, %entry, %entry, %entry, %entry
+  tail call void @foo0()
+  br label %sw.epilog
+
+sw.bb.1:                                          ; preds = %entry, %entry, %entry, %entry, %entry, %entry, %entry, %entry
+  tail call void @foo1()
+  br label %sw.epilog
+
+sw.bb.2:                                          ; preds = %entry, %entry, %entry, %entry, %entry, %entry
+  tail call void @foo2()
+  br label %sw.epilog
+
+sw.bb.3:                                          ; preds = %entry
+  tail call void @foo3()
+  br label %sw.epilog
+
+sw.bb.4:                                          ; preds = %entry
+  tail call void @foo4()
+  br label %sw.epilog
+
+sw.bb.5:                                          ; preds = %entry
+  tail call void @foo5()
+  br label %sw.epilog
+
+sw.epilog:                                        ; preds = %entry, %sw.bb.5, %sw.bb.4, %sw.bb.3, %sw.bb.2, %sw.bb.1, %sw.bb
+  ret void
+}