[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

11 ↗

(On Diff #34456)

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

58 ↗

(On Diff #34456)

std::vector, or non-zero size.

67 ↗

(On Diff #34456)

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

70 ↗

(On Diff #34456)

Could you explain the strategy? You leave me hanging!

87 ↗

(On Diff #34456)

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?

95 ↗

(On Diff #34456)

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?

104 ↗

(On Diff #34456)

Expand on why we want that control.

107 ↗

(On Diff #34456)

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

121 ↗

(On Diff #34456)

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

[jfb]

A few more high-level comments...

lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp

130 ↗

(On Diff #34456)

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

Also: conservatively, isInlineAsm?

lib/Target/WebAssembly/WebAssemblyInstrControl.td

61 ↗

(On Diff #34456)

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

69 ↗

(On Diff #34456)

Aggressive multiclass for SELECT?

lib/Target/WebAssembly/WebAssemblyInstrInfo.cpp

52 ↗

(On Diff #34456)

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

58 ↗

(On Diff #34456)

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

87 ↗

(On Diff #34456)

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

95 ↗

(On Diff #34456)

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.

121 ↗

(On Diff #34456)

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.

130 ↗

(On Diff #34456)

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 ↗

(On Diff #34456)

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

lib/Target/WebAssembly/WebAssemblyInstrInfo.cpp

52 ↗

(On Diff #34456)

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

58 ↗

(On Diff #34456)

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!

95 ↗

(On Diff #34456)

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

59 ↗

(On Diff #34714)

(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 ;-).

96 ↗

(On Diff #34714)

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.

108 ↗

(On Diff #34714)

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

59 ↗

(On Diff #34714)

Much appreciated :-)

lib/Target/WebAssembly/WebAssemblyInstrControl.td

41 ↗

(On Diff #34757)

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 ↗

(On Diff #34770)

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 ↗

(On Diff #34770)

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

llvm/trunk/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

llvm/trunk/lib/Target/WebAssembly/WebAssembly.h

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

llvm/trunk/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);
 }

llvm/trunk/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.
+///
+/// This pass reorders the blocks in a function to put them into a reverse
+/// post-order [0], with special care to keep the order as similar as possible
+/// to the original order, and to keep loops contiguous even in the case of
+/// split backedges.
+///
+/// Then, it inserts BLOCK and LOOP markers to mark the start of scopes, since
+/// scope boundaries serve as the labels for WebAssembly's control transfers.
+///
+/// This is sufficient to convert arbitrary CFGs into a form that works on
+/// WebAssembly, provided that all loops are single-entry.
+///
+/// [0] https://en.wikipedia.org/wiki/Depth-first_search#Vertex_orderings
+///
+//===----------------------------------------------------------------------===//
+
+#include "WebAssembly.h"
+#include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
+#include "WebAssemblySubtarget.h"
+#include "llvm/ADT/SCCIterator.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 {
+  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;
+
+public:
+  static char ID; // Pass identification, replacement for typeid
+  WebAssemblyCFGStackify() : MachineFunctionPass(ID) {}
+};
+} // end anonymous namespace
+
+char WebAssemblyCFGStackify::ID = 0;
+FunctionPass *llvm::createWebAssemblyCFGStackify() {
+  return new WebAssemblyCFGStackify();
+}
+
+static void EliminateMultipleEntryLoops(MachineFunction &MF,
+                                        const MachineLoopInfo &MLI) {
+  SmallPtrSet<MachineBasicBlock *, 8> InSet;
+  for (scc_iterator<MachineFunction *> I = scc_begin(&MF), E = scc_end(&MF);
+       I != E; ++I) {
+    const std::vector<MachineBasicBlock *> &CurrentSCC = *I;
+
+    // Skip trivial SCCs.
+    if (CurrentSCC.size() == 1)
+      continue;
+
+    InSet.insert(CurrentSCC.begin(), CurrentSCC.end());
+    MachineBasicBlock *Header = nullptr;
+    for (MachineBasicBlock *MBB : CurrentSCC) {
+      for (MachineBasicBlock *Pred : MBB->predecessors()) {
+        if (InSet.count(Pred))
+          continue;
+        if (!Header) {
+          Header = MBB;
+          break;
+        }
+        // TODO: Implement multiple-entry loops.
+        report_fatal_error("multiple-entry loops are not supported yet");
+      }
+    }
+    assert(MLI.isLoopHeader(Header));
+
+    InSet.clear();
+  }
+}
+
+namespace {
+/// Post-order traversal stack entry.
+struct POStackEntry {
+  MachineBasicBlock *MBB;
+  SmallVector<MachineBasicBlock *, 0> Succs;
+
+  POStackEntry(MachineBasicBlock *MBB, MachineFunction &MF,
+               const MachineLoopInfo &MLI);
+};
+} // end anonymous namespace
+
+POStackEntry::POStackEntry(MachineBasicBlock *MBB, MachineFunction &MF,
+                           const MachineLoopInfo &MLI)
+    : MBB(MBB), Succs(MBB->successors()) {
+  // 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.
+  // Sort them strategically (see below).
+  MachineLoop *Loop = MLI.getLoopFor(MBB);
+  MachineFunction::iterator Next = next(MachineFunction::iterator(MBB));
+  MachineBasicBlock *LayoutSucc = Next == MF.end() ? nullptr : &*Next;
+  std::stable_sort(
+      Succs.begin(), Succs.end(),
+      [=, &MLI](const MachineBasicBlock *A, const MachineBasicBlock *B) {
+        if (A == B)
+          return false;
+
+        // Keep loops contiguous by preferring the block that's in the same
+        // loop.
+        MachineLoop *LoopA = MLI.getLoopFor(A);
+        MachineLoop *LoopB = MLI.getLoopFor(B);
+        if (LoopA == Loop && LoopB != Loop)
+          return true;
+        if (LoopA != Loop && LoopB == Loop)
+          return false;
+
+        // Minimize perturbation by preferring the block which is the immediate
+        // layout successor.
+        if (A == LayoutSucc)
+          return true;
+        if (B == LayoutSucc)
+          return false;
+
+        // TODO: More sophisticated orderings may be profitable here.
+
+        return false;
+      });
+}
+
+/// 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) {
+  // Note that we do our own RPO rather than using
+  // "llvm/ADT/PostOrderIterator.h" because we want control over the order that
+  // successors are visited in (see above). Also, we can sort the blocks in the
+  // MachineFunction as we go.
+  SmallPtrSet<MachineBasicBlock *, 16> Visited;
+  SmallVector<POStackEntry, 16> Stack;
+
+  MachineBasicBlock *Entry = MF.begin();
+  Visited.insert(Entry);
+  Stack.push_back(POStackEntry(Entry, MF, MLI));
+
+  for (;;) {
+    POStackEntry &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(POStackEntry(Succ, MF, MLI));
+      continue;
+    }
+
+    // Put the block in its position in the MachineFunction.
+    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.empty() && MBB.back().isTerminator() && !MBB.back().isBranch() &&
+        !MBB.back().isBarrier())
+      report_fatal_error(
+          "Non-branch terminator with fallthrough cannot yet be rewritten");
+    if (MBB.empty() || !MBB.back().isTerminator() || MBB.back().isBranch())
+      MBB.updateTerminator();
+
+    Stack.pop_back();
+    if (Stack.empty())
+      break;
+  }
+
+  // Now that we've sorted the blocks in RPO, renumber them.
+  MF.RenumberBlocks();
+
+#ifndef NDEBUG
+  for (auto &MBB : MF)
+    if (MachineLoop *Loop = MLI.getLoopFor(&MBB)) {
+      // Assert that loops are contiguous.
+      assert(Loop->getHeader() == Loop->getTopBlock());
+      assert(Loop->getHeader() == &MBB ||
+             MLI.getLoopFor(prev(MachineFunction::iterator(&MBB))) == Loop);
+    } else {
+      // Assert that non-loops have no backedge predecessors.
+      for (auto Pred : MBB.predecessors())
+        assert(Pred->getNumber() < MBB.getNumber() &&
+               "CFG still has multiple-entry loops");
+    }
+#endif
+}
+
+/// Insert BLOCK markers at appropriate places.
+static void PlaceBlockMarkers(MachineBasicBlock &MBB, MachineBasicBlock &Succ,
+                              MachineFunction &MF, const MachineLoopInfo &MLI,
+                              const WebAssemblyInstrInfo &TII) {
+  // Backward branches are loop backedges, and we place the LOOP markers
+  // separately. So only consider forward branches here.
+  if (Succ.getNumber() <= MBB.getNumber())
+    return;
+
+  // Place the BLOCK for a forward branch. For simplicity, we just insert
+  // blocks immediately inside loop boundaries.
+  MachineLoop *Loop = MLI.getLoopFor(&Succ);
+  MachineBasicBlock &Header = *(Loop ? Loop->getHeader() : &MF.front());
+  MachineBasicBlock::iterator InsertPos = Header.begin(), End = Header.end();
+  if (InsertPos != End) {
+    if (InsertPos->getOpcode() == WebAssembly::LOOP)
+      ++InsertPos;
+    int SuccNumber = Succ.getNumber();
+    // Position the BLOCK in nesting order.
+    for (; InsertPos != End && InsertPos->getOpcode() == WebAssembly::BLOCK;
+         ++InsertPos) {
+      int N = InsertPos->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, InsertPos, DebugLoc(), TII.get(WebAssembly::BLOCK))
+      .addMBB(&Succ);
+}
+
+/// Insert LOOP and BLOCK markers at appropriate places.
+static void PlaceMarkers(MachineFunction &MF, const MachineLoopInfo &MLI,
+                         const WebAssemblyInstrInfo &TII) {
+  for (auto &MBB : MF) {
+    // Place the LOOP for loops.
+    if (MachineLoop *Loop = MLI.getLoopFor(&MBB))
+      if (Loop->getHeader() == &MBB)
+        BuildMI(MBB, MBB.begin(), DebugLoc(), TII.get(WebAssembly::LOOP))
+            .addMBB(Loop->getBottomBlock());
+
+    // Check for forward branches and switches that need BLOCKS placed.
+    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 auto &MLI = getAnalysis<MachineLoopInfo>();
+  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
+
+  // RPO sorting needs all loops to be single-entry.
+  EliminateMultipleEntryLoops(MF, MLI);
+
+  // Sort the blocks in RPO, with contiguous loops.
+  SortBlocks(MF, MLI);
+
+  // Place the BLOCK and LOOP markers to indicate the beginnings of scopes.
+  PlaceMarkers(MF, MLI, TII);
+
+  return true;
+}

llvm/trunk/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...

llvm/trunk/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

llvm/trunk/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;
+
+  // 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]));
+
+  // 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();
 }

llvm/trunk/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
+
+// TODO: SelectionDAG's lowering insists on using a pointer as the index for
+// jump tables, so in practice we don't ever use SWITCH_I64 in wasm32 mode
+// currently.
+let isTerminator = 1, hasCtrlDep = 1, isBarrier = 1 in {
+def SWITCH_I32 : I<(outs), (ins Int32:$index, variable_ops),
+                   [(WebAssemblyswitch Int32:$index)]>;
+def SWITCH_I64 : I<(outs), (ins Int64:$index, variable_ops),
+                   [(WebAssemblyswitch Int64:$index)]>;
+} // isTerminator = 1, hasCtrlDep = 1, isBarrier = 1
+
+// Placemarkers to indicate the start of a block or loop scope.
+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

llvm/trunk/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

llvm/trunk/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;
+}

llvm/trunk/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"

llvm/trunk/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);
+
+  // TODO: 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());
+}

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

+; RUN: llc < %s -asm-verbose=false | FileCheck %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: (add
+; CHECK: (brif
+; CHECK: (call
+; CHECK: (br $BB0_1)
+; CHECK: (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: (add
+; CHECK: (brif
+; CHECK: (call
+; CHECK: (br $BB1_1)
+; CHECK: (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
+
+  %c = icmp sge i32 %i.next, %n
+  br i1 %c, label %exit, label %back
+
+exit:
+  ret void
+
+back:
+  call void @something()
+  br label %header
+}
+
+; Test that a simple loop is handled as expected.
+
+; CHECK-LABEL: test2
+; CHECK: (block $BB2_2)
+; CHECK: (brif $BB2_2 {{.*}})
+; CHECK: BB2_1:
+; CHECK: (brif $BB2_1 @14)
+; CHECK: BB2_2:
+; CHECK: (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.body:
+  %i.05 = phi i32 [ %inc, %for.body ], [ 0, %for.body.preheader ]
+  %arrayidx = getelementptr inbounds double, double* %p, i32 %i.05
+  %0 = load double, double* %arrayidx, align 8
+  %mul = fmul double %0, 3.200000e+00
+  store double %mul, double* %arrayidx, align 8
+  %inc = add nuw nsw i32 %i.05, 1
+  %exitcond = icmp eq i32 %inc, %n
+  br i1 %exitcond, label %for.end.loopexit, label %for.body
+
+for.end.loopexit:
+  br label %for.end
+
+for.end:
+  ret void
+}
+
+; CHECK-LABEL: doublediamond
+; CHECK: (block $BB3_5)
+; CHECK: (block $BB3_4)
+; CHECK: (block $BB3_2)
+; CHECK: (brif $BB3_2 @4)
+; CHECK: (br $BB3_5)
+; CHECK: BB3_2:
+; CHECK: (brif $BB3_4 @7)
+; CHECK: (br $BB3_5)
+; CHECK: BB3_4:
+; CHECK: BB3_5:
+; CHECK: (return @3)
+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
+  br label %exit
+false:
+  store volatile i32 2, i32* %p
+  br i1 %d, label %ft, label %ff
+ft:
+  store volatile i32 3, i32* %p
+  br label %exit
+ff:
+  store volatile i32 4, i32* %p
+  br label %exit
+exit:
+  store volatile i32 5, i32* %p
+  ret i32 0
+}
+
+; CHECK-LABEL: triangle
+; CHECK: (block $BB4_2)
+; CHECK: (brif $BB4_2 @3)
+; CHECK: BB4_2:
+; CHECK: (return @2)
+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: (brif $BB5_2 @3)
+; CHECK: (br $BB5_3)
+; CHECK: BB5_2:
+; CHECK: BB5_3:
+; CHECK: (return @2)
+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 @1)
+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: (store_i32 @0 @2)
+; CHECK: (br $BB7_1)
+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_1)
+; CHECK: (brif $BB8_1 @4)
+; CHECK: (return @2)
+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: (block $BB9_3)
+; CHECK: (brif $BB9_4 @4)
+; CHECK: (brif $BB9_3 @7)
+; CHECK: BB9_3:
+; CHECK: BB9_4:
+; CHECK: (return @3)
+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: (brif $BB10_2 @4)
+; CHECK: (br $BB10_4)
+; CHECK: BB10_2:
+; CHECK: (brif $BB10_4 @7)
+; CHECK: BB10_4:
+; CHECK: (return @3)
+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
+  br label %exit
+false:
+  store volatile i32 2, i32* %p
+  br i1 %d, label %ft, label %exit
+ft:
+  store volatile i32 3, i32* %p
+  br label %exit
+exit:
+  store volatile i32 4, i32* %p
+  ret i32 0
+}

llvm/trunk/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:

llvm/trunk/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: bar32
+; 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 @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
+    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
+}
+
+; CHECK-LABEL: bar64
+; CHECK: (block $BB1_8)
+; CHECK: (block $BB1_7)
+; CHECK: (block $BB1_6)
+; CHECK: (block $BB1_5)
+; CHECK: (block $BB1_4)
+; CHECK: (block $BB1_3)
+; CHECK: (block $BB1_2)
+; CHECK: (switch {{.*}} $BB1_2 $BB1_2 $BB1_2 $BB1_2 $BB1_2 $BB1_2 $BB1_2 $BB1_2 $BB1_3 $BB1_3 $BB1_3 $BB1_3 $BB1_3 $BB1_3 $BB1_3 $BB1_3 $BB1_4 $BB1_4 $BB1_4 $BB1_4 $BB1_4 $BB1_4 $BB1_5 $BB1_6 $BB1_7)
+; CHECk: BB1_2:
+; CHECK:   (setlocal {{.*}} (global $foo0))
+; CHECK: BB1_3:
+; CHECK:   (setlocal {{.*}} (global $foo1))
+; CHECK: BB1_4:
+; CHECK:   (setlocal {{.*}} (global $foo2))
+; CHECK: BB1_5:
+; CHECK:   (setlocal {{.*}} (global $foo3))
+; CHECK: BB1_6:
+; CHECK:   (setlocal {{.*}} (global $foo4))
+; CHECK: BB1_7:
+; CHECK:   (setlocal {{.*}} (global $foo5))
+; CHECK: BB1_8:
+; 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
+    i64 4, label %sw.bb
+    i64 5, label %sw.bb
+    i64 6, label %sw.bb
+    i64 7, label %sw.bb.1
+    i64 8, label %sw.bb.1
+    i64 9, label %sw.bb.1
+    i64 10, label %sw.bb.1
+    i64 11, label %sw.bb.1
+    i64 12, label %sw.bb.1
+    i64 13, label %sw.bb.1
+    i64 14, label %sw.bb.1
+    i64 15, label %sw.bb.2
+    i64 16, label %sw.bb.2
+    i64 17, label %sw.bb.2
+    i64 18, label %sw.bb.2
+    i64 19, label %sw.bb.2
+    i64 20, label %sw.bb.2
+    i64 21, label %sw.bb.3
+    i64 22, label %sw.bb.4
+    i64 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
+}