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/MachineDominators.h"
  33 #include "llvm/CodeGen/MachineFunction.h"
  34 #include "llvm/CodeGen/MachineInstrBuilder.h"
  35 #include "llvm/CodeGen/MachineLoopInfo.h"
  36 #include "llvm/CodeGen/Passes.h"
  37 #include "llvm/Support/Debug.h"
  38 #include "llvm/Support/raw_ostream.h"
  39 using namespace llvm;
  40
  41 #define DEBUG_TYPE "wasm-cfg-stackify"
  42
  43 namespace {
  44 class WebAssemblyCFGStackify final : public MachineFunctionPass {
  45   const char *getPassName() const override {
  46     return "WebAssembly CFG Stackify";
  47   }
  48
  49   void getAnalysisUsage(AnalysisUsage &AU) const override {
  50     AU.setPreservesCFG();
  51     AU.addRequired<MachineDominatorTree>();
  52     AU.addPreserved<MachineDominatorTree>();
  53     AU.addRequired<MachineLoopInfo>();
  54     AU.addPreserved<MachineLoopInfo>();
  55     MachineFunctionPass::getAnalysisUsage(AU);
  56   }
  57
  58   bool runOnMachineFunction(MachineFunction &MF) override;
  59
  60 public:
  61   static char ID; // Pass identification, replacement for typeid
  62   WebAssemblyCFGStackify() : MachineFunctionPass(ID) {}
  63 };
  64 } // end anonymous namespace
  65
  66 char WebAssemblyCFGStackify::ID = 0;
  67 FunctionPass *llvm::createWebAssemblyCFGStackify() {
  68   return new WebAssemblyCFGStackify();
  69 }
  70
  71 static void EliminateMultipleEntryLoops(MachineFunction &MF,
  72                                         const MachineLoopInfo &MLI) {
  73   SmallPtrSet<MachineBasicBlock *, 8> InSet;
  74   for (scc_iterator<MachineFunction *> I = scc_begin(&MF), E = scc_end(&MF);
  75        I != E; ++I) {
  76     const std::vector<MachineBasicBlock *> &CurrentSCC = *I;
  77
  78     // Skip trivial SCCs.
  79     if (CurrentSCC.size() == 1)
  80       continue;
  81
  82     InSet.insert(CurrentSCC.begin(), CurrentSCC.end());
  83     MachineBasicBlock *Header = nullptr;
  84     for (MachineBasicBlock *MBB : CurrentSCC) {
  85       for (MachineBasicBlock *Pred : MBB->predecessors()) {
  86         if (InSet.count(Pred))
  87           continue;
  88         if (!Header) {
  89           Header = MBB;
  90           break;
  91         }
  92         // TODO: Implement multiple-entry loops.
  93         report_fatal_error("multiple-entry loops are not supported yet");
  94       }
  95     }
  96     assert(MLI.isLoopHeader(Header));
  97
  98     InSet.clear();
  99   }
 100 }
 101
 102 namespace {
 103 /// Post-order traversal stack entry.
 104 struct POStackEntry {
 105   MachineBasicBlock *MBB;
 106   SmallVector<MachineBasicBlock *, 0> Succs;
 107
 108   POStackEntry(MachineBasicBlock *MBB, MachineFunction &MF,
 109                const MachineLoopInfo &MLI);
 110 };
 111 } // end anonymous namespace
 112
 113 static bool LoopContains(const MachineLoop *Loop,
 114                          const MachineBasicBlock *MBB) {
 115   return Loop ? Loop->contains(MBB) : true;
 116 }
 117
 118 POStackEntry::POStackEntry(MachineBasicBlock *MBB, MachineFunction &MF,
 119                            const MachineLoopInfo &MLI)
 120     : MBB(MBB), Succs(MBB->successors()) {
 121   // RPO is not a unique form, since at every basic block with multiple
 122   // successors, the DFS has to pick which order to visit the successors in.
 123   // Sort them strategically (see below).
 124   MachineLoop *Loop = MLI.getLoopFor(MBB);
 125   MachineFunction::iterator Next = next(MachineFunction::iterator(MBB));
 126   MachineBasicBlock *LayoutSucc = Next == MF.end() ? nullptr : &*Next;
 127   std::stable_sort(
 128       Succs.begin(), Succs.end(),
 129       [=, &MLI](const MachineBasicBlock *A, const MachineBasicBlock *B) {
 130         if (A == B)
 131           return false;
 132
 133         // Keep loops contiguous by preferring the block that's in the same
 134         // loop.
 135         bool LoopContainsA = LoopContains(Loop, A);
 136         bool LoopContainsB = LoopContains(Loop, B);
 137         if (LoopContainsA && !LoopContainsB)
 138           return true;
 139         if (!LoopContainsA && LoopContainsB)
 140           return false;
 141
 142         // Minimize perturbation by preferring the block which is the immediate
 143         // layout successor.
 144         if (A == LayoutSucc)
 145           return true;
 146         if (B == LayoutSucc)
 147           return false;
 148
 149         // TODO: More sophisticated orderings may be profitable here.
 150
 151         return false;
 152       });
 153 }
 154
 155 /// Sort the blocks in RPO, taking special care to make sure that loops are
 156 /// contiguous even in the case of split backedges.
 157 static void SortBlocks(MachineFunction &MF, const MachineLoopInfo &MLI) {
 158   // Note that we do our own RPO rather than using
 159   // "llvm/ADT/PostOrderIterator.h" because we want control over the order that
 160   // successors are visited in (see above). Also, we can sort the blocks in the
 161   // MachineFunction as we go.
 162   SmallPtrSet<MachineBasicBlock *, 16> Visited;
 163   SmallVector<POStackEntry, 16> Stack;
 164
 165   MachineBasicBlock *EntryBlock = &*MF.begin();
 166   Visited.insert(EntryBlock);
 167   Stack.push_back(POStackEntry(EntryBlock, MF, MLI));
 168
 169   for (;;) {
 170     POStackEntry &Entry = Stack.back();
 171     SmallVectorImpl<MachineBasicBlock *> &Succs = Entry.Succs;
 172     if (!Succs.empty()) {
 173       MachineBasicBlock *Succ = Succs.pop_back_val();
 174       if (Visited.insert(Succ).second)
 175         Stack.push_back(POStackEntry(Succ, MF, MLI));
 176       continue;
 177     }
 178
 179     // Put the block in its position in the MachineFunction.
 180     MachineBasicBlock &MBB = *Entry.MBB;
 181     MBB.moveBefore(&*MF.begin());
 182
 183     // Branch instructions may utilize a fallthrough, so update them if a
 184     // fallthrough has been added or removed.
 185     if (!MBB.empty() && MBB.back().isTerminator() && !MBB.back().isBranch() &&
 186         !MBB.back().isBarrier())
 187       report_fatal_error(
 188           "Non-branch terminator with fallthrough cannot yet be rewritten");
 189     if (MBB.empty() || !MBB.back().isTerminator() || MBB.back().isBranch())
 190       MBB.updateTerminator();
 191
 192     Stack.pop_back();
 193     if (Stack.empty())
 194       break;
 195   }
 196
 197   // Now that we've sorted the blocks in RPO, renumber them.
 198   MF.RenumberBlocks();
 199
 200 #ifndef NDEBUG
 201   for (auto &MBB : MF)
 202     if (MachineLoop *Loop = MLI.getLoopFor(&MBB)) {
 203       // Assert that all containing loops are contiguous.
 204       for (MachineLoop *L = Loop; L; L = L->getParentLoop()) {
 205         if (&MBB == L->getHeader()) {
 206           assert(&MBB == L->getTopBlock());
 207         } else {
 208           assert(&MBB != L->getTopBlock());
 209           assert(L->contains(
 210                      MLI.getLoopFor(&*prev(MachineFunction::iterator(&MBB)))) &&
 211                  "Loop isn't contiguous");
 212         }
 213       }
 214     } else {
 215       // Assert that non-loops have no backedge predecessors.
 216       for (auto Pred : MBB.predecessors())
 217         assert(Pred->getNumber() < MBB.getNumber() &&
 218                "CFG still has multiple-entry loops");
 219     }
 220 #endif
 221 }
 222
 223 static unsigned GetLoopDepth(const MachineLoop *Loop) {
 224   return Loop ? Loop->getLoopDepth() : 0;
 225 }
 226
 227 /// Insert a BLOCK marker for branches to MBB (if needed).
 228 static void PlaceBlockMarkers(MachineBasicBlock &MBB,
 229                               const WebAssemblyInstrInfo &TII,
 230                               MachineDominatorTree &MDT,
 231                               const MachineLoopInfo &MLI) {
 232   // Place the BLOCK for forward non-fallthrough branches. Put it at the nearest
 233   // common dominator of all preceding predecesors so that we minimize the time
 234   // that it's on the stack, which reduces overall stack height.
 235   MachineBasicBlock *Header = nullptr;
 236   bool IsBranchedTo = false;
 237   int MBBNumber = MBB.getNumber();
 238   for (MachineBasicBlock *Pred : MBB.predecessors())
 239     if (Pred->getNumber() < MBBNumber) {
 240       Header = Header ? MDT.findNearestCommonDominator(Header, Pred) : Pred;
 241       if (!Pred->isLayoutSuccessor(&MBB) ||
 242           !(Pred->empty() || !Pred->back().isBarrier()))
 243         IsBranchedTo = true;
 244     }
 245   if (!Header)
 246     return;
 247   if (!IsBranchedTo)
 248     return;
 249
 250   MachineBasicBlock::iterator InsertPos;
 251   MachineLoop *HeaderLoop = MLI.getLoopFor(Header);
 252   unsigned MBBLoopDepth = GetLoopDepth(MLI.getLoopFor(&MBB));
 253   unsigned HeaderLoopDepth = GetLoopDepth(HeaderLoop);
 254   if (HeaderLoopDepth > MBBLoopDepth) {
 255     // The nearest common dominating point is more deeply nested. Insert the
 256     // BLOCK just above the LOOP.
 257     for (unsigned i = 0; i < HeaderLoopDepth - 1 - MBBLoopDepth; ++i)
 258       HeaderLoop = HeaderLoop->getParentLoop();
 259     Header = HeaderLoop->getHeader();
 260     InsertPos = Header->begin();
 261     // Don't insert a BLOCK if we can reuse a loop exit label though.
 262     if (InsertPos != Header->end() &&
 263         InsertPos->getOpcode() == WebAssembly::LOOP &&
 264         InsertPos->getOperand(0).getMBB() == &MBB)
 265       return;
 266   } else {
 267     // Insert the BLOCK as late in the block as we can, but before any existing
 268     // BLOCKs.
 269     InsertPos = Header->getFirstTerminator();
 270     while (InsertPos != Header->begin() &&
 271            std::prev(InsertPos)->getOpcode() == WebAssembly::BLOCK)
 272       --InsertPos;
 273   }
 274
 275   BuildMI(*Header, InsertPos, DebugLoc(), TII.get(WebAssembly::BLOCK))
 276       .addMBB(&MBB);
 277 }
 278
 279 /// Insert LOOP and BLOCK markers at appropriate places.
 280 static void PlaceMarkers(MachineFunction &MF, const MachineLoopInfo &MLI,
 281                          const WebAssemblyInstrInfo &TII,
 282                          MachineDominatorTree &MDT) {
 283   for (auto &MBB : MF) {
 284     // Place the LOOP for MBB if MBB is the header of a loop.
 285     if (MachineLoop *Loop = MLI.getLoopFor(&MBB))
 286       if (Loop->getHeader() == &MBB) {
 287         // The operand of a LOOP is the first block after the loop. If the loop
 288         // is the bottom of the function, insert a dummy block at the end.
 289         MachineBasicBlock *Bottom = Loop->getBottomBlock();
 290         auto Iter = next(MachineFunction::iterator(Bottom));
 291         if (Iter == MF.end()) {
 292           MachineBasicBlock *Label = MF.CreateMachineBasicBlock();
 293           // Give it a fake predecessor so that AsmPrinter prints its label.
 294           Label->addSuccessor(Label);
 295           MF.push_back(Label);
 296           Iter = next(MachineFunction::iterator(Bottom));
 297         }
 298         BuildMI(MBB, MBB.begin(), DebugLoc(), TII.get(WebAssembly::LOOP))
 299             .addMBB(&*Iter);
 300
 301         // Emit a special no-op telling the asm printer that we need a label
 302         // to close the loop scope, even though the destination is only
 303         // reachable by fallthrough.
 304         if (!Bottom->back().isBarrier())
 305           BuildMI(*Bottom, Bottom->end(), DebugLoc(),
 306                   TII.get(WebAssembly::LOOP_END));
 307       }
 308
 309     // Place the BLOCK for MBB if MBB is branched to from above.
 310     PlaceBlockMarkers(MBB, TII, MDT, MLI);
 311   }
 312 }
 313
 314 #ifndef NDEBUG
 315 static bool
 316 IsOnStack(const SmallVectorImpl<std::pair<MachineBasicBlock *, bool>> &Stack,
 317           const MachineBasicBlock *MBB) {
 318   for (const auto &Pair : Stack)
 319     if (Pair.first == MBB)
 320       return true;
 321   return false;
 322 }
 323 #endif
 324
 325 bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) {
 326   DEBUG(dbgs() << "********** CFG Stackifying **********\n"
 327                   "********** Function: "
 328                << MF.getName() << '\n');
 329
 330   const auto &MLI = getAnalysis<MachineLoopInfo>();
 331   auto &MDT = getAnalysis<MachineDominatorTree>();
 332   const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
 333
 334   // RPO sorting needs all loops to be single-entry.
 335   EliminateMultipleEntryLoops(MF, MLI);
 336
 337   // Sort the blocks in RPO, with contiguous loops.
 338   SortBlocks(MF, MLI);
 339
 340   // Place the BLOCK and LOOP markers to indicate the beginnings of scopes.
 341   PlaceMarkers(MF, MLI, TII, MDT);
 342
 343 #ifndef NDEBUG
 344   // Verify that block and loop beginnings and endings are in LIFO order, and
 345   // that all references to blocks are to blocks on the stack at the point of
 346   // the reference.
 347   SmallVector<std::pair<MachineBasicBlock *, bool>, 0> Stack;
 348   for (auto &MBB : MF) {
 349     while (!Stack.empty() && Stack.back().first == &MBB)
 350       if (Stack.back().second) {
 351         assert(Stack.size() >= 2);
 352         Stack.pop_back();
 353         Stack.pop_back();
 354       } else {
 355         assert(Stack.size() >= 1);
 356         Stack.pop_back();
 357       }
 358     for (auto &MI : MBB)
 359       switch (MI.getOpcode()) {
 360       case WebAssembly::LOOP:
 361         Stack.push_back(std::make_pair(&MBB, false));
 362         Stack.push_back(std::make_pair(MI.getOperand(0).getMBB(), true));
 363         break;
 364       case WebAssembly::BLOCK:
 365         Stack.push_back(std::make_pair(MI.getOperand(0).getMBB(), false));
 366         break;
 367       default:
 368         for (const MachineOperand &MO : MI.explicit_operands())
 369           if (MO.isMBB())
 370             assert(IsOnStack(Stack, MO.getMBB()));
 371         break;
 372       }
 373   }
 374   assert(Stack.empty());
 375 #endif
 376
 377   return true;
 378 }