contrib/llvm/lib/Target/WebAssembly/WebAssemblyCFGSort.cpp

   1 //===-- WebAssemblyCFGSort.cpp - CFG Sorting ------------------------------===//
   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 sorting pass.
  12 ///
  13 /// This pass reorders the blocks in a function to put them into topological
  14 /// order, ignoring loop backedges, and without any loop being interrupted
  15 /// by a block not dominated by the loop header, with special care to keep the
  16 /// order as similar as possible to the original order.
  17 ///
  18 ////===----------------------------------------------------------------------===//
  19
  20 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
  21 #include "WebAssembly.h"
  22 #include "WebAssemblySubtarget.h"
  23 #include "WebAssemblyUtilities.h"
  24 #include "llvm/ADT/PriorityQueue.h"
  25 #include "llvm/ADT/SetVector.h"
  26 #include "llvm/CodeGen/MachineDominators.h"
  27 #include "llvm/CodeGen/MachineFunction.h"
  28 #include "llvm/CodeGen/MachineLoopInfo.h"
  29 #include "llvm/CodeGen/MachineRegisterInfo.h"
  30 #include "llvm/CodeGen/Passes.h"
  31 #include "llvm/Support/Debug.h"
  32 #include "llvm/Support/raw_ostream.h"
  33 using namespace llvm;
  34
  35 #define DEBUG_TYPE "wasm-cfg-sort"
  36
  37 namespace {
  38 class WebAssemblyCFGSort final : public MachineFunctionPass {
  39   StringRef getPassName() const override { return "WebAssembly CFG Sort"; }
  40
  41   void getAnalysisUsage(AnalysisUsage &AU) const override {
  42     AU.setPreservesCFG();
  43     AU.addRequired<MachineDominatorTree>();
  44     AU.addPreserved<MachineDominatorTree>();
  45     AU.addRequired<MachineLoopInfo>();
  46     AU.addPreserved<MachineLoopInfo>();
  47     MachineFunctionPass::getAnalysisUsage(AU);
  48   }
  49
  50   bool runOnMachineFunction(MachineFunction &MF) override;
  51
  52 public:
  53   static char ID; // Pass identification, replacement for typeid
  54   WebAssemblyCFGSort() : MachineFunctionPass(ID) {}
  55 };
  56 } // end anonymous namespace
  57
  58 char WebAssemblyCFGSort::ID = 0;
  59 FunctionPass *llvm::createWebAssemblyCFGSort() {
  60   return new WebAssemblyCFGSort();
  61 }
  62
  63 static void MaybeUpdateTerminator(MachineBasicBlock *MBB) {
  64 #ifndef NDEBUG
  65   bool AnyBarrier = false;
  66 #endif
  67   bool AllAnalyzable = true;
  68   for (const MachineInstr &Term : MBB->terminators()) {
  69 #ifndef NDEBUG
  70     AnyBarrier |= Term.isBarrier();
  71 #endif
  72     AllAnalyzable &= Term.isBranch() && !Term.isIndirectBranch();
  73   }
  74   assert((AnyBarrier || AllAnalyzable) &&
  75          "AnalyzeBranch needs to analyze any block with a fallthrough");
  76   if (AllAnalyzable)
  77     MBB->updateTerminator();
  78 }
  79
  80 namespace {
  81 /// Sort blocks by their number.
  82 struct CompareBlockNumbers {
  83   bool operator()(const MachineBasicBlock *A,
  84                   const MachineBasicBlock *B) const {
  85     return A->getNumber() > B->getNumber();
  86   }
  87 };
  88 /// Sort blocks by their number in the opposite order..
  89 struct CompareBlockNumbersBackwards {
  90   bool operator()(const MachineBasicBlock *A,
  91                   const MachineBasicBlock *B) const {
  92     return A->getNumber() < B->getNumber();
  93   }
  94 };
  95 /// Bookkeeping for a loop to help ensure that we don't mix blocks not dominated
  96 /// by the loop header among the loop's blocks.
  97 struct Entry {
  98   const MachineLoop *Loop;
  99   unsigned NumBlocksLeft;
 100
 101   /// List of blocks not dominated by Loop's header that are deferred until
 102   /// after all of Loop's blocks have been seen.
 103   std::vector<MachineBasicBlock *> Deferred;
 104
 105   explicit Entry(const MachineLoop *L)
 106       : Loop(L), NumBlocksLeft(L->getNumBlocks()) {}
 107 };
 108 } // end anonymous namespace
 109
 110 /// Sort the blocks, taking special care to make sure that loops are not
 111 /// interrupted by blocks not dominated by their header.
 112 /// TODO: There are many opportunities for improving the heuristics here.
 113 /// Explore them.
 114 static void SortBlocks(MachineFunction &MF, const MachineLoopInfo &MLI,
 115                        const MachineDominatorTree &MDT) {
 116   // Prepare for a topological sort: Record the number of predecessors each
 117   // block has, ignoring loop backedges.
 118   MF.RenumberBlocks();
 119   SmallVector<unsigned, 16> NumPredsLeft(MF.getNumBlockIDs(), 0);
 120   for (MachineBasicBlock &MBB : MF) {
 121     unsigned N = MBB.pred_size();
 122     if (MachineLoop *L = MLI.getLoopFor(&MBB))
 123       if (L->getHeader() == &MBB)
 124         for (const MachineBasicBlock *Pred : MBB.predecessors())
 125           if (L->contains(Pred))
 126             --N;
 127     NumPredsLeft[MBB.getNumber()] = N;
 128   }
 129
 130   // Topological sort the CFG, with additional constraints:
 131   //  - Between a loop header and the last block in the loop, there can be
 132   //    no blocks not dominated by the loop header.
 133   //  - It's desirable to preserve the original block order when possible.
 134   // We use two ready lists; Preferred and Ready. Preferred has recently
 135   // processed successors, to help preserve block sequences from the original
 136   // order. Ready has the remaining ready blocks.
 137   PriorityQueue<MachineBasicBlock *, std::vector<MachineBasicBlock *>,
 138                 CompareBlockNumbers>
 139       Preferred;
 140   PriorityQueue<MachineBasicBlock *, std::vector<MachineBasicBlock *>,
 141                 CompareBlockNumbersBackwards>
 142       Ready;
 143   SmallVector<Entry, 4> Loops;
 144   for (MachineBasicBlock *MBB = &MF.front();;) {
 145     const MachineLoop *L = MLI.getLoopFor(MBB);
 146     if (L) {
 147       // If MBB is a loop header, add it to the active loop list. We can't put
 148       // any blocks that it doesn't dominate until we see the end of the loop.
 149       if (L->getHeader() == MBB)
 150         Loops.push_back(Entry(L));
 151       // For each active loop the block is in, decrement the count. If MBB is
 152       // the last block in an active loop, take it off the list and pick up any
 153       // blocks deferred because the header didn't dominate them.
 154       for (Entry &E : Loops)
 155         if (E.Loop->contains(MBB) && --E.NumBlocksLeft == 0)
 156           for (auto DeferredBlock : E.Deferred)
 157             Ready.push(DeferredBlock);
 158       while (!Loops.empty() && Loops.back().NumBlocksLeft == 0)
 159         Loops.pop_back();
 160     }
 161     // The main topological sort logic.
 162     for (MachineBasicBlock *Succ : MBB->successors()) {
 163       // Ignore backedges.
 164       if (MachineLoop *SuccL = MLI.getLoopFor(Succ))
 165         if (SuccL->getHeader() == Succ && SuccL->contains(MBB))
 166           continue;
 167       // Decrement the predecessor count. If it's now zero, it's ready.
 168       if (--NumPredsLeft[Succ->getNumber()] == 0)
 169         Preferred.push(Succ);
 170     }
 171     // Determine the block to follow MBB. First try to find a preferred block,
 172     // to preserve the original block order when possible.
 173     MachineBasicBlock *Next = nullptr;
 174     while (!Preferred.empty()) {
 175       Next = Preferred.top();
 176       Preferred.pop();
 177       // If X isn't dominated by the top active loop header, defer it until that
 178       // loop is done.
 179       if (!Loops.empty() &&
 180           !MDT.dominates(Loops.back().Loop->getHeader(), Next)) {
 181         Loops.back().Deferred.push_back(Next);
 182         Next = nullptr;
 183         continue;
 184       }
 185       // If Next was originally ordered before MBB, and it isn't because it was
 186       // loop-rotated above the header, it's not preferred.
 187       if (Next->getNumber() < MBB->getNumber() &&
 188           (!L || !L->contains(Next) ||
 189            L->getHeader()->getNumber() < Next->getNumber())) {
 190         Ready.push(Next);
 191         Next = nullptr;
 192         continue;
 193       }
 194       break;
 195     }
 196     // If we didn't find a suitable block in the Preferred list, check the
 197     // general Ready list.
 198     if (!Next) {
 199       // If there are no more blocks to process, we're done.
 200       if (Ready.empty()) {
 201         MaybeUpdateTerminator(MBB);
 202         break;
 203       }
 204       for (;;) {
 205         Next = Ready.top();
 206         Ready.pop();
 207         // If Next isn't dominated by the top active loop header, defer it until
 208         // that loop is done.
 209         if (!Loops.empty() &&
 210             !MDT.dominates(Loops.back().Loop->getHeader(), Next)) {
 211           Loops.back().Deferred.push_back(Next);
 212           continue;
 213         }
 214         break;
 215       }
 216     }
 217     // Move the next block into place and iterate.
 218     Next->moveAfter(MBB);
 219     MaybeUpdateTerminator(MBB);
 220     MBB = Next;
 221   }
 222   assert(Loops.empty() && "Active loop list not finished");
 223   MF.RenumberBlocks();
 224
 225 #ifndef NDEBUG
 226   SmallSetVector<MachineLoop *, 8> OnStack;
 227
 228   // Insert a sentinel representing the degenerate loop that starts at the
 229   // function entry block and includes the entire function as a "loop" that
 230   // executes once.
 231   OnStack.insert(nullptr);
 232
 233   for (auto &MBB : MF) {
 234     assert(MBB.getNumber() >= 0 && "Renumbered blocks should be non-negative.");
 235
 236     MachineLoop *Loop = MLI.getLoopFor(&MBB);
 237     if (Loop && &MBB == Loop->getHeader()) {
 238       // Loop header. The loop predecessor should be sorted above, and the other
 239       // predecessors should be backedges below.
 240       for (auto Pred : MBB.predecessors())
 241         assert(
 242             (Pred->getNumber() < MBB.getNumber() || Loop->contains(Pred)) &&
 243             "Loop header predecessors must be loop predecessors or backedges");
 244       assert(OnStack.insert(Loop) && "Loops should be declared at most once.");
 245     } else {
 246       // Not a loop header. All predecessors should be sorted above.
 247       for (auto Pred : MBB.predecessors())
 248         assert(Pred->getNumber() < MBB.getNumber() &&
 249                "Non-loop-header predecessors should be topologically sorted");
 250       assert(OnStack.count(MLI.getLoopFor(&MBB)) &&
 251              "Blocks must be nested in their loops");
 252     }
 253     while (OnStack.size() > 1 && &MBB == LoopBottom(OnStack.back()))
 254       OnStack.pop_back();
 255   }
 256   assert(OnStack.pop_back_val() == nullptr &&
 257          "The function entry block shouldn't actually be a loop header");
 258   assert(OnStack.empty() &&
 259          "Control flow stack pushes and pops should be balanced.");
 260 #endif
 261 }
 262
 263 bool WebAssemblyCFGSort::runOnMachineFunction(MachineFunction &MF) {
 264   DEBUG(dbgs() << "********** CFG Sorting **********\n"
 265                   "********** Function: "
 266                << MF.getName() << '\n');
 267
 268   const auto &MLI = getAnalysis<MachineLoopInfo>();
 269   auto &MDT = getAnalysis<MachineDominatorTree>();
 270   // Liveness is not tracked for VALUE_STACK physreg.
 271   MF.getRegInfo().invalidateLiveness();
 272
 273   // Sort the blocks, with contiguous loops.
 274   SortBlocks(MF, MLI, MDT);
 275
 276   return true;
 277 }