lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp

   1 //===-- WebAssemblyCFGStackify.cpp - CFG Stackification -------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 ///
  10 /// \file
  11 /// \brief This file implements a CFG stacking pass.
  12 ///
  13 /// This pass reorders the blocks in a function to put them into a reverse
  14 /// post-order [0], with special care to keep the order as similar as possible
  15 /// to the original order, and to keep loops contiguous even in the case of
  16 /// split backedges.
  17 ///
  18 /// Then, it inserts BLOCK and LOOP markers to mark the start of scopes, since
  19 /// scope boundaries serve as the labels for WebAssembly's control transfers.
  20 ///
  21 /// This is sufficient to convert arbitrary CFGs into a form that works on
  22 /// WebAssembly, provided that all loops are single-entry.
  23 ///
  24 /// [0] https://en.wikipedia.org/wiki/Depth-first_search#Vertex_orderings
  25 ///
  26 //===----------------------------------------------------------------------===//
  27
  28 #include "WebAssembly.h"
  29 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
  30 #include "WebAssemblySubtarget.h"
  31 #include "llvm/ADT/SCCIterator.h"
  32 #include "llvm/CodeGen/MachineFunction.h"
  33 #include "llvm/CodeGen/MachineInstrBuilder.h"
  34 #include "llvm/CodeGen/MachineLoopInfo.h"
  35 #include "llvm/CodeGen/Passes.h"
  36 #include "llvm/Support/Debug.h"
  37 #include "llvm/Support/raw_ostream.h"
  38 using namespace llvm;
  39
  40 #define DEBUG_TYPE "wasm-cfg-stackify"
  41
  42 namespace {
  43 class WebAssemblyCFGStackify final : public MachineFunctionPass {
  44   const char *getPassName() const override {
  45     return "WebAssembly CFG Stackify";
  46   }
  47
  48   void getAnalysisUsage(AnalysisUsage &AU) const override {
  49     AU.setPreservesCFG();
  50     AU.addRequired<MachineLoopInfo>();
  51     AU.addPreserved<MachineLoopInfo>();
  52     MachineFunctionPass::getAnalysisUsage(AU);
  53   }
  54
  55   bool runOnMachineFunction(MachineFunction &MF) override;
  56
  57 public:
  58   static char ID; // Pass identification, replacement for typeid
  59   WebAssemblyCFGStackify() : MachineFunctionPass(ID) {}
  60 };
  61 } // end anonymous namespace
  62
  63 char WebAssemblyCFGStackify::ID = 0;
  64 FunctionPass *llvm::createWebAssemblyCFGStackify() {
  65   return new WebAssemblyCFGStackify();
  66 }
  67
  68 static void EliminateMultipleEntryLoops(MachineFunction &MF,
  69                                         const MachineLoopInfo &MLI) {
  70   SmallPtrSet<MachineBasicBlock *, 8> InSet;
  71   for (scc_iterator<MachineFunction *> I = scc_begin(&MF), E = scc_end(&MF);
  72        I != E; ++I) {
  73     const std::vector<MachineBasicBlock *> &CurrentSCC = *I;
  74
  75     // Skip trivial SCCs.
  76     if (CurrentSCC.size() == 1)
  77       continue;
  78
  79     InSet.insert(CurrentSCC.begin(), CurrentSCC.end());
  80     MachineBasicBlock *Header = nullptr;
  81     for (MachineBasicBlock *MBB : CurrentSCC) {
  82       for (MachineBasicBlock *Pred : MBB->predecessors()) {
  83         if (InSet.count(Pred))
  84           continue;
  85         if (!Header) {
  86           Header = MBB;
  87           break;
  88         }
  89         // TODO: Implement multiple-entry loops.
  90         report_fatal_error("multiple-entry loops are not supported yet");
  91       }
  92     }
  93     assert(MLI.isLoopHeader(Header));
  94
  95     InSet.clear();
  96   }
  97 }
  98
  99 namespace {
 100 /// Post-order traversal stack entry.
 101 struct POStackEntry {
 102   MachineBasicBlock *MBB;
 103   SmallVector<MachineBasicBlock *, 0> Succs;
 104
 105   POStackEntry(MachineBasicBlock *MBB, MachineFunction &MF,
 106                const MachineLoopInfo &MLI);
 107 };
 108 } // end anonymous namespace
 109
 110 POStackEntry::POStackEntry(MachineBasicBlock *MBB, MachineFunction &MF,
 111                            const MachineLoopInfo &MLI)
 112     : MBB(MBB), Succs(MBB->successors()) {
 113   // RPO is not a unique form, since at every basic block with multiple
 114   // successors, the DFS has to pick which order to visit the successors in.
 115   // Sort them strategically (see below).
 116   MachineLoop *Loop = MLI.getLoopFor(MBB);
 117   MachineFunction::iterator Next = next(MachineFunction::iterator(MBB));
 118   MachineBasicBlock *LayoutSucc = Next == MF.end() ? nullptr : &*Next;
 119   std::stable_sort(
 120       Succs.begin(), Succs.end(),
 121       [=, &MLI](const MachineBasicBlock *A, const MachineBasicBlock *B) {
 122         if (A == B)
 123           return false;
 124
 125         // Keep loops contiguous by preferring the block that's in the same
 126         // loop.
 127         MachineLoop *LoopA = MLI.getLoopFor(A);
 128         MachineLoop *LoopB = MLI.getLoopFor(B);
 129         if (LoopA == Loop && LoopB != Loop)
 130           return true;
 131         if (LoopA != Loop && LoopB == Loop)
 132           return false;
 133
 134         // Minimize perturbation by preferring the block which is the immediate
 135         // layout successor.
 136         if (A == LayoutSucc)
 137           return true;
 138         if (B == LayoutSucc)
 139           return false;
 140
 141         // TODO: More sophisticated orderings may be profitable here.
 142
 143         return false;
 144       });
 145 }
 146
 147 /// Sort the blocks in RPO, taking special care to make sure that loops are
 148 /// contiguous even in the case of split backedges.
 149 static void SortBlocks(MachineFunction &MF, const MachineLoopInfo &MLI) {
 150   // Note that we do our own RPO rather than using
 151   // "llvm/ADT/PostOrderIterator.h" because we want control over the order that
 152   // successors are visited in (see above). Also, we can sort the blocks in the
 153   // MachineFunction as we go.
 154   SmallPtrSet<MachineBasicBlock *, 16> Visited;
 155   SmallVector<POStackEntry, 16> Stack;
 156
 157   MachineBasicBlock *Entry = &*MF.begin();
 158   Visited.insert(Entry);
 159   Stack.push_back(POStackEntry(Entry, MF, MLI));
 160
 161   for (;;) {
 162     POStackEntry &Entry = Stack.back();
 163     SmallVectorImpl<MachineBasicBlock *> &Succs = Entry.Succs;
 164     if (!Succs.empty()) {
 165       MachineBasicBlock *Succ = Succs.pop_back_val();
 166       if (Visited.insert(Succ).second)
 167         Stack.push_back(POStackEntry(Succ, MF, MLI));
 168       continue;
 169     }
 170
 171     // Put the block in its position in the MachineFunction.
 172     MachineBasicBlock &MBB = *Entry.MBB;
 173     MBB.moveBefore(&*MF.begin());
 174
 175     // Branch instructions may utilize a fallthrough, so update them if a
 176     // fallthrough has been added or removed.
 177     if (!MBB.empty() && MBB.back().isTerminator() && !MBB.back().isBranch() &&
 178         !MBB.back().isBarrier())
 179       report_fatal_error(
 180           "Non-branch terminator with fallthrough cannot yet be rewritten");
 181     if (MBB.empty() || !MBB.back().isTerminator() || MBB.back().isBranch())
 182       MBB.updateTerminator();
 183
 184     Stack.pop_back();
 185     if (Stack.empty())
 186       break;
 187   }
 188
 189   // Now that we've sorted the blocks in RPO, renumber them.
 190   MF.RenumberBlocks();
 191
 192 #ifndef NDEBUG
 193   for (auto &MBB : MF)
 194     if (MachineLoop *Loop = MLI.getLoopFor(&MBB)) {
 195       // Assert that loops are contiguous.
 196       assert(Loop->getHeader() == Loop->getTopBlock());
 197       assert((Loop->getHeader() == &MBB ||
 198               Loop->contains(
 199                   MLI.getLoopFor(&*prev(MachineFunction::iterator(&MBB))))) &&
 200              "Loop isn't contiguous");
 201     } else {
 202       // Assert that non-loops have no backedge predecessors.
 203       for (auto Pred : MBB.predecessors())
 204         assert(Pred->getNumber() < MBB.getNumber() &&
 205                "CFG still has multiple-entry loops");
 206     }
 207 #endif
 208 }
 209
 210 /// Insert BLOCK markers at appropriate places.
 211 static void PlaceBlockMarkers(MachineBasicBlock &MBB, MachineBasicBlock &Succ,
 212                               MachineFunction &MF, const MachineLoopInfo &MLI,
 213                               const WebAssemblyInstrInfo &TII) {
 214   // Backward branches are loop backedges, and we place the LOOP markers
 215   // separately. So only consider forward branches here.
 216   if (Succ.getNumber() <= MBB.getNumber())
 217     return;
 218
 219   // Place the BLOCK for a forward branch. For simplicity, we just insert
 220   // blocks immediately inside loop boundaries.
 221   MachineLoop *Loop = MLI.getLoopFor(&Succ);
 222   MachineBasicBlock &Header = *(Loop ? Loop->getHeader() : &MF.front());
 223   MachineBasicBlock::iterator InsertPos = Header.begin(), End = Header.end();
 224   if (InsertPos != End) {
 225     if (InsertPos->getOpcode() == WebAssembly::LOOP)
 226       ++InsertPos;
 227     int SuccNumber = Succ.getNumber();
 228     // Position the BLOCK in nesting order.
 229     for (; InsertPos != End && InsertPos->getOpcode() == WebAssembly::BLOCK;
 230          ++InsertPos) {
 231       int N = InsertPos->getOperand(0).getMBB()->getNumber();
 232       if (N < SuccNumber)
 233         break;
 234       // If there's already a BLOCK for Succ, we don't need another.
 235       if (N == SuccNumber)
 236         return;
 237     }
 238   }
 239
 240   BuildMI(Header, InsertPos, DebugLoc(), TII.get(WebAssembly::BLOCK))
 241       .addMBB(&Succ);
 242 }
 243
 244 /// Insert LOOP and BLOCK markers at appropriate places.
 245 static void PlaceMarkers(MachineFunction &MF, const MachineLoopInfo &MLI,
 246                          const WebAssemblyInstrInfo &TII) {
 247   for (auto &MBB : MF) {
 248     // Place the LOOP for loops.
 249     if (MachineLoop *Loop = MLI.getLoopFor(&MBB))
 250       if (Loop->getHeader() == &MBB) {
 251         // The operand of a LOOP is the first block after the loop. If the loop
 252         // is the bottom of the function, insert a dummy block at the end.
 253         MachineBasicBlock *Bottom = Loop->getBottomBlock();
 254         auto Iter = next(MachineFunction::iterator(Bottom));
 255         if (Iter == MF.end()) {
 256           MF.push_back(MF.CreateMachineBasicBlock());
 257           Iter = next(MachineFunction::iterator(Bottom));
 258         }
 259         BuildMI(MBB, MBB.begin(), DebugLoc(), TII.get(WebAssembly::LOOP))
 260             .addMBB(&*Iter);
 261       }
 262
 263     // Check for forward branches and switches that need BLOCKS placed.
 264     for (auto &Term : MBB.terminators())
 265       for (auto &MO : Term.operands())
 266         if (MO.isMBB())
 267           PlaceBlockMarkers(MBB, *MO.getMBB(), MF, MLI, TII);
 268   }
 269 }
 270
 271 bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) {
 272   DEBUG(dbgs() << "********** CFG Stackifying **********\n"
 273                   "********** Function: "
 274                << MF.getName() << '\n');
 275
 276   const auto &MLI = getAnalysis<MachineLoopInfo>();
 277   const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
 278
 279   // RPO sorting needs all loops to be single-entry.
 280   EliminateMultipleEntryLoops(MF, MLI);
 281
 282   // Sort the blocks in RPO, with contiguous loops.
 283   SortBlocks(MF, MLI);
 284
 285   // Place the BLOCK and LOOP markers to indicate the beginnings of scopes.
 286   PlaceMarkers(MF, MLI, TII);
 287
 288   return true;
 289 }