vendor/llvm/llvm-trunk-r300422

1 files changed, 15 insertions, 222 deletions

diff --git a/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp b/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp
index 49b9754e6b62c..bd11d1b469063 100644
--- a/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp
+++ b/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp
@@ -10,12 +10,7 @@
 /// \file
 /// \brief This file implements a CFG stacking pass.
 ///
-/// This pass reorders the blocks in a function to put them into topological
-/// order, ignoring loop backedges, and without any loop being interrupted
-/// by a block not dominated by the loop header, with special care to keep the
-/// order as similar as possible to the original order.
-///
-/// Then, it inserts BLOCK and LOOP markers to mark the start of scopes, since
+/// This pass 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
@@ -28,8 +23,6 @@
 #include "WebAssemblyMachineFunctionInfo.h"
 #include "WebAssemblySubtarget.h"
 #include "WebAssemblyUtilities.h"
-#include "llvm/ADT/PriorityQueue.h"
-#include "llvm/ADT/SetVector.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
@@ -68,217 +61,6 @@ FunctionPass *llvm::createWebAssemblyCFGStackify() {
   return new WebAssemblyCFGStackify();
 }
 
-/// Return the "bottom" block of a loop. This differs from
-/// MachineLoop::getBottomBlock in that it works even if the loop is
-/// discontiguous.
-static MachineBasicBlock *LoopBottom(const MachineLoop *Loop) {
-  MachineBasicBlock *Bottom = Loop->getHeader();
-  for (MachineBasicBlock *MBB : Loop->blocks())
-    if (MBB->getNumber() > Bottom->getNumber())
-      Bottom = MBB;
-  return Bottom;
-}
-
-static void MaybeUpdateTerminator(MachineBasicBlock *MBB) {
-#ifndef NDEBUG
-  bool AnyBarrier = false;
-#endif
-  bool AllAnalyzable = true;
-  for (const MachineInstr &Term : MBB->terminators()) {
-#ifndef NDEBUG
-    AnyBarrier |= Term.isBarrier();
-#endif
-    AllAnalyzable &= Term.isBranch() && !Term.isIndirectBranch();
-  }
-  assert((AnyBarrier || AllAnalyzable) &&
-         "AnalyzeBranch needs to analyze any block with a fallthrough");
-  if (AllAnalyzable)
-    MBB->updateTerminator();
-}
-
-namespace {
-/// Sort blocks by their number.
-struct CompareBlockNumbers {
-  bool operator()(const MachineBasicBlock *A,
-                  const MachineBasicBlock *B) const {
-    return A->getNumber() > B->getNumber();
-  }
-};
-/// Sort blocks by their number in the opposite order..
-struct CompareBlockNumbersBackwards {
-  bool operator()(const MachineBasicBlock *A,
-                  const MachineBasicBlock *B) const {
-    return A->getNumber() < B->getNumber();
-  }
-};
-/// Bookkeeping for a loop to help ensure that we don't mix blocks not dominated
-/// by the loop header among the loop's blocks.
-struct Entry {
-  const MachineLoop *Loop;
-  unsigned NumBlocksLeft;
-
-  /// List of blocks not dominated by Loop's header that are deferred until
-  /// after all of Loop's blocks have been seen.
-  std::vector<MachineBasicBlock *> Deferred;
-
-  explicit Entry(const MachineLoop *L)
-      : Loop(L), NumBlocksLeft(L->getNumBlocks()) {}
-};
-}
-
-/// Sort the blocks, taking special care to make sure that loops are not
-/// interrupted by blocks not dominated by their header.
-/// TODO: There are many opportunities for improving the heuristics here.
-/// Explore them.
-static void SortBlocks(MachineFunction &MF, const MachineLoopInfo &MLI,
-                       const MachineDominatorTree &MDT) {
-  // Prepare for a topological sort: Record the number of predecessors each
-  // block has, ignoring loop backedges.
-  MF.RenumberBlocks();
-  SmallVector<unsigned, 16> NumPredsLeft(MF.getNumBlockIDs(), 0);
-  for (MachineBasicBlock &MBB : MF) {
-    unsigned N = MBB.pred_size();
-    if (MachineLoop *L = MLI.getLoopFor(&MBB))
-      if (L->getHeader() == &MBB)
-        for (const MachineBasicBlock *Pred : MBB.predecessors())
-          if (L->contains(Pred))
-            --N;
-    NumPredsLeft[MBB.getNumber()] = N;
-  }
-
-  // Topological sort the CFG, with additional constraints:
-  //  - Between a loop header and the last block in the loop, there can be
-  //    no blocks not dominated by the loop header.
-  //  - It's desirable to preserve the original block order when possible.
-  // We use two ready lists; Preferred and Ready. Preferred has recently
-  // processed sucessors, to help preserve block sequences from the original
-  // order. Ready has the remaining ready blocks.
-  PriorityQueue<MachineBasicBlock *, std::vector<MachineBasicBlock *>,
-                CompareBlockNumbers>
-      Preferred;
-  PriorityQueue<MachineBasicBlock *, std::vector<MachineBasicBlock *>,
-                CompareBlockNumbersBackwards>
-      Ready;
-  SmallVector<Entry, 4> Loops;
-  for (MachineBasicBlock *MBB = &MF.front();;) {
-    const MachineLoop *L = MLI.getLoopFor(MBB);
-    if (L) {
-      // If MBB is a loop header, add it to the active loop list. We can't put
-      // any blocks that it doesn't dominate until we see the end of the loop.
-      if (L->getHeader() == MBB)
-        Loops.push_back(Entry(L));
-      // For each active loop the block is in, decrement the count. If MBB is
-      // the last block in an active loop, take it off the list and pick up any
-      // blocks deferred because the header didn't dominate them.
-      for (Entry &E : Loops)
-        if (E.Loop->contains(MBB) && --E.NumBlocksLeft == 0)
-          for (auto DeferredBlock : E.Deferred)
-            Ready.push(DeferredBlock);
-      while (!Loops.empty() && Loops.back().NumBlocksLeft == 0)
-        Loops.pop_back();
-    }
-    // The main topological sort logic.
-    for (MachineBasicBlock *Succ : MBB->successors()) {
-      // Ignore backedges.
-      if (MachineLoop *SuccL = MLI.getLoopFor(Succ))
-        if (SuccL->getHeader() == Succ && SuccL->contains(MBB))
-          continue;
-      // Decrement the predecessor count. If it's now zero, it's ready.
-      if (--NumPredsLeft[Succ->getNumber()] == 0)
-        Preferred.push(Succ);
-    }
-    // Determine the block to follow MBB. First try to find a preferred block,
-    // to preserve the original block order when possible.
-    MachineBasicBlock *Next = nullptr;
-    while (!Preferred.empty()) {
-      Next = Preferred.top();
-      Preferred.pop();
-      // If X isn't dominated by the top active loop header, defer it until that
-      // loop is done.
-      if (!Loops.empty() &&
-          !MDT.dominates(Loops.back().Loop->getHeader(), Next)) {
-        Loops.back().Deferred.push_back(Next);
-        Next = nullptr;
-        continue;
-      }
-      // If Next was originally ordered before MBB, and it isn't because it was
-      // loop-rotated above the header, it's not preferred.
-      if (Next->getNumber() < MBB->getNumber() &&
-          (!L || !L->contains(Next) ||
-           L->getHeader()->getNumber() < Next->getNumber())) {
-        Ready.push(Next);
-        Next = nullptr;
-        continue;
-      }
-      break;
-    }
-    // If we didn't find a suitable block in the Preferred list, check the
-    // general Ready list.
-    if (!Next) {
-      // If there are no more blocks to process, we're done.
-      if (Ready.empty()) {
-        MaybeUpdateTerminator(MBB);
-        break;
-      }
-      for (;;) {
-        Next = Ready.top();
-        Ready.pop();
-        // If Next isn't dominated by the top active loop header, defer it until
-        // that loop is done.
-        if (!Loops.empty() &&
-            !MDT.dominates(Loops.back().Loop->getHeader(), Next)) {
-          Loops.back().Deferred.push_back(Next);
-          continue;
-        }
-        break;
-      }
-    }
-    // Move the next block into place and iterate.
-    Next->moveAfter(MBB);
-    MaybeUpdateTerminator(MBB);
-    MBB = Next;
-  }
-  assert(Loops.empty() && "Active loop list not finished");
-  MF.RenumberBlocks();
-
-#ifndef NDEBUG
-  SmallSetVector<MachineLoop *, 8> OnStack;
-
-  // Insert a sentinel representing the degenerate loop that starts at the
-  // function entry block and includes the entire function as a "loop" that
-  // executes once.
-  OnStack.insert(nullptr);
-
-  for (auto &MBB : MF) {
-    assert(MBB.getNumber() >= 0 && "Renumbered blocks should be non-negative.");
-
-    MachineLoop *Loop = MLI.getLoopFor(&MBB);
-    if (Loop && &MBB == Loop->getHeader()) {
-      // Loop header. The loop predecessor should be sorted above, and the other
-      // predecessors should be backedges below.
-      for (auto Pred : MBB.predecessors())
-        assert(
-            (Pred->getNumber() < MBB.getNumber() || Loop->contains(Pred)) &&
-            "Loop header predecessors must be loop predecessors or backedges");
-      assert(OnStack.insert(Loop) && "Loops should be declared at most once.");
-    } else {
-      // Not a loop header. All predecessors should be sorted above.
-      for (auto Pred : MBB.predecessors())
-        assert(Pred->getNumber() < MBB.getNumber() &&
-               "Non-loop-header predecessors should be topologically sorted");
-      assert(OnStack.count(MLI.getLoopFor(&MBB)) &&
-             "Blocks must be nested in their loops");
-    }
-    while (OnStack.size() > 1 && &MBB == LoopBottom(OnStack.back()))
-      OnStack.pop_back();
-  }
-  assert(OnStack.pop_back_val() == nullptr &&
-         "The function entry block shouldn't actually be a loop header");
-  assert(OnStack.empty() &&
-         "Control flow stack pushes and pops should be balanced.");
-#endif
-}
-
 /// Test whether Pred has any terminators explicitly branching to MBB, as
 /// opposed to falling through. Note that it's possible (eg. in unoptimized
 /// code) for a branch instruction to both branch to a block and fallthrough
@@ -488,6 +270,15 @@ static void FixEndsAtEndOfFunction(
   }
 }
 
+// WebAssembly functions end with an end instruction, as if the function body
+// were a block.
+static void AppendEndToFunction(
+    MachineFunction &MF,
+    const WebAssemblyInstrInfo &TII) {
+  BuildMI(MF.back(), MF.back().end(), DebugLoc(),
+          TII.get(WebAssembly::END_FUNCTION));
+}
+
 /// Insert LOOP and BLOCK markers at appropriate places.
 static void PlaceMarkers(MachineFunction &MF, const MachineLoopInfo &MLI,
                          const WebAssemblyInstrInfo &TII,
@@ -555,6 +346,11 @@ static void PlaceMarkers(MachineFunction &MF, const MachineLoopInfo &MLI,
   // Fix up block/loop signatures at the end of the function to conform to
   // WebAssembly's rules.
   FixEndsAtEndOfFunction(MF, MFI, BlockTops, LoopTops);
+
+  // Add an end instruction at the end of the function body.
+  if (!MF.getSubtarget<WebAssemblySubtarget>()
+        .getTargetTriple().isOSBinFormatELF())
+    AppendEndToFunction(MF, TII);
 }
 
 bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) {
@@ -569,9 +365,6 @@ bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) {
   WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
   MF.getRegInfo().invalidateLiveness();
 
-  // Sort the blocks, with contiguous loops.
-  SortBlocks(MF, MLI, MDT);
-
   // Place the BLOCK and LOOP markers to indicate the beginnings of scopes.
   PlaceMarkers(MF, MLI, TII, MDT, MFI);