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 /// 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 or exception being
  15 /// interrupted by a block not dominated by the its header, with special care
  16 /// to keep the order as similar as possible to the original order.
  17 ///
  18 ////===----------------------------------------------------------------------===//
  19
  20 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
  21 #include "WebAssembly.h"
  22 #include "WebAssemblyExceptionInfo.h"
  23 #include "WebAssemblySubtarget.h"
  24 #include "WebAssemblyUtilities.h"
  25 #include "llvm/ADT/PriorityQueue.h"
  26 #include "llvm/ADT/SetVector.h"
  27 #include "llvm/CodeGen/MachineDominators.h"
  28 #include "llvm/CodeGen/MachineFunction.h"
  29 #include "llvm/CodeGen/MachineLoopInfo.h"
  30 #include "llvm/CodeGen/MachineRegisterInfo.h"
  31 #include "llvm/CodeGen/Passes.h"
  32 #include "llvm/Support/Debug.h"
  33 #include "llvm/Support/raw_ostream.h"
  34 using namespace llvm;
  35
  36 #define DEBUG_TYPE "wasm-cfg-sort"
  37
  38 namespace {
  39
  40 // Wrapper for loops and exceptions
  41 class Region {
  42 public:
  43   virtual ~Region() = default;
  44   virtual MachineBasicBlock *getHeader() const = 0;
  45   virtual bool contains(const MachineBasicBlock *MBB) const = 0;
  46   virtual unsigned getNumBlocks() const = 0;
  47   using block_iterator = typename ArrayRef<MachineBasicBlock *>::const_iterator;
  48   virtual iterator_range<block_iterator> blocks() const = 0;
  49   virtual bool isLoop() const = 0;
  50 };
  51
  52 template <typename T> class ConcreteRegion : public Region {
  53   const T *Region;
  54
  55 public:
  56   ConcreteRegion(const T *Region) : Region(Region) {}
  57   MachineBasicBlock *getHeader() const override { return Region->getHeader(); }
  58   bool contains(const MachineBasicBlock *MBB) const override {
  59     return Region->contains(MBB);
  60   }
  61   unsigned getNumBlocks() const override { return Region->getNumBlocks(); }
  62   iterator_range<block_iterator> blocks() const override {
  63     return Region->blocks();
  64   }
  65   bool isLoop() const override { return false; }
  66 };
  67
  68 template <> bool ConcreteRegion<MachineLoop>::isLoop() const { return true; }
  69
  70 // This class has information of nested Regions; this is analogous to what
  71 // LoopInfo is for loops.
  72 class RegionInfo {
  73   const MachineLoopInfo &MLI;
  74   const WebAssemblyExceptionInfo &WEI;
  75   std::vector<const Region *> Regions;
  76   DenseMap<const MachineLoop *, std::unique_ptr<Region>> LoopMap;
  77   DenseMap<const WebAssemblyException *, std::unique_ptr<Region>> ExceptionMap;
  78
  79 public:
  80   RegionInfo(const MachineLoopInfo &MLI, const WebAssemblyExceptionInfo &WEI)
  81       : MLI(MLI), WEI(WEI) {}
  82
  83   // Returns a smallest loop or exception that contains MBB
  84   const Region *getRegionFor(const MachineBasicBlock *MBB) {
  85     const auto *ML = MLI.getLoopFor(MBB);
  86     const auto *WE = WEI.getExceptionFor(MBB);
  87     if (!ML && !WE)
  88       return nullptr;
  89     if ((ML && !WE) || (ML && WE && ML->getNumBlocks() < WE->getNumBlocks())) {
  90       // If the smallest region containing MBB is a loop
  91       if (LoopMap.count(ML))
  92         return LoopMap[ML].get();
  93       LoopMap[ML] = llvm::make_unique<ConcreteRegion<MachineLoop>>(ML);
  94       return LoopMap[ML].get();
  95     } else {
  96       // If the smallest region containing MBB is an exception
  97       if (ExceptionMap.count(WE))
  98         return ExceptionMap[WE].get();
  99       ExceptionMap[WE] =
 100           llvm::make_unique<ConcreteRegion<WebAssemblyException>>(WE);
 101       return ExceptionMap[WE].get();
 102     }
 103   }
 104 };
 105
 106 class WebAssemblyCFGSort final : public MachineFunctionPass {
 107   StringRef getPassName() const override { return "WebAssembly CFG Sort"; }
 108
 109   void getAnalysisUsage(AnalysisUsage &AU) const override {
 110     AU.setPreservesCFG();
 111     AU.addRequired<MachineDominatorTree>();
 112     AU.addPreserved<MachineDominatorTree>();
 113     AU.addRequired<MachineLoopInfo>();
 114     AU.addPreserved<MachineLoopInfo>();
 115     AU.addRequired<WebAssemblyExceptionInfo>();
 116     AU.addPreserved<WebAssemblyExceptionInfo>();
 117     MachineFunctionPass::getAnalysisUsage(AU);
 118   }
 119
 120   bool runOnMachineFunction(MachineFunction &MF) override;
 121
 122 public:
 123   static char ID; // Pass identification, replacement for typeid
 124   WebAssemblyCFGSort() : MachineFunctionPass(ID) {}
 125 };
 126 } // end anonymous namespace
 127
 128 char WebAssemblyCFGSort::ID = 0;
 129 INITIALIZE_PASS(WebAssemblyCFGSort, DEBUG_TYPE,
 130                 "Reorders blocks in topological order", false, false)
 131
 132 FunctionPass *llvm::createWebAssemblyCFGSort() {
 133   return new WebAssemblyCFGSort();
 134 }
 135
 136 static void MaybeUpdateTerminator(MachineBasicBlock *MBB) {
 137 #ifndef NDEBUG
 138   bool AnyBarrier = false;
 139 #endif
 140   bool AllAnalyzable = true;
 141   for (const MachineInstr &Term : MBB->terminators()) {
 142 #ifndef NDEBUG
 143     AnyBarrier |= Term.isBarrier();
 144 #endif
 145     AllAnalyzable &= Term.isBranch() && !Term.isIndirectBranch();
 146   }
 147   assert((AnyBarrier || AllAnalyzable) &&
 148          "AnalyzeBranch needs to analyze any block with a fallthrough");
 149   if (AllAnalyzable)
 150     MBB->updateTerminator();
 151 }
 152
 153 namespace {
 154 // EH pads are selected first regardless of the block comparison order.
 155 // When only one of the BBs is an EH pad, we give a higher priority to it, to
 156 // prevent common mismatches between possibly throwing calls and ehpads they
 157 // unwind to, as in the example below:
 158 //
 159 // bb0:
 160 //   call @foo      // If this throws, unwind to bb2
 161 // bb1:
 162 //   call @bar      // If this throws, unwind to bb3
 163 // bb2 (ehpad):
 164 //   handler_bb2
 165 // bb3 (ehpad):
 166 //   handler_bb3
 167 // continuing code
 168 //
 169 // Because this pass tries to preserve the original BB order, this order will
 170 // not change. But this will result in this try-catch structure in CFGStackify,
 171 // resulting in a mismatch:
 172 // try
 173 //   try
 174 //     call @foo
 175 //     call @bar    // This should unwind to bb3, not bb2!
 176 //   catch
 177 //     handler_bb2
 178 //   end
 179 // catch
 180 //   handler_bb3
 181 // end
 182 // continuing code
 183 //
 184 // If we give a higher priority to an EH pad whenever it is ready in this
 185 // example, when both bb1 and bb2 are ready, we would pick up bb2 first.
 186
 187 /// Sort blocks by their number.
 188 struct CompareBlockNumbers {
 189   bool operator()(const MachineBasicBlock *A,
 190                   const MachineBasicBlock *B) const {
 191     if (A->isEHPad() && !B->isEHPad())
 192       return false;
 193     if (!A->isEHPad() && B->isEHPad())
 194       return true;
 195
 196     return A->getNumber() > B->getNumber();
 197   }
 198 };
 199 /// Sort blocks by their number in the opposite order..
 200 struct CompareBlockNumbersBackwards {
 201   bool operator()(const MachineBasicBlock *A,
 202                   const MachineBasicBlock *B) const {
 203     // We give a higher priority to an EH pad
 204     if (A->isEHPad() && !B->isEHPad())
 205       return false;
 206     if (!A->isEHPad() && B->isEHPad())
 207       return true;
 208
 209     return A->getNumber() < B->getNumber();
 210   }
 211 };
 212 /// Bookkeeping for a region to help ensure that we don't mix blocks not
 213 /// dominated by the its header among its blocks.
 214 struct Entry {
 215   const Region *TheRegion;
 216   unsigned NumBlocksLeft;
 217
 218   /// List of blocks not dominated by Loop's header that are deferred until
 219   /// after all of Loop's blocks have been seen.
 220   std::vector<MachineBasicBlock *> Deferred;
 221
 222   explicit Entry(const class Region *R)
 223       : TheRegion(R), NumBlocksLeft(R->getNumBlocks()) {}
 224 };
 225 } // end anonymous namespace
 226
 227 /// Sort the blocks, taking special care to make sure that regions are not
 228 /// interrupted by blocks not dominated by their header.
 229 /// TODO: There are many opportunities for improving the heuristics here.
 230 /// Explore them.
 231 static void SortBlocks(MachineFunction &MF, const MachineLoopInfo &MLI,
 232                        const WebAssemblyExceptionInfo &WEI,
 233                        const MachineDominatorTree &MDT) {
 234   // Prepare for a topological sort: Record the number of predecessors each
 235   // block has, ignoring loop backedges.
 236   MF.RenumberBlocks();
 237   SmallVector<unsigned, 16> NumPredsLeft(MF.getNumBlockIDs(), 0);
 238   for (MachineBasicBlock &MBB : MF) {
 239     unsigned N = MBB.pred_size();
 240     if (MachineLoop *L = MLI.getLoopFor(&MBB))
 241       if (L->getHeader() == &MBB)
 242         for (const MachineBasicBlock *Pred : MBB.predecessors())
 243           if (L->contains(Pred))
 244             --N;
 245     NumPredsLeft[MBB.getNumber()] = N;
 246   }
 247
 248   // Topological sort the CFG, with additional constraints:
 249   //  - Between a region header and the last block in the region, there can be
 250   //    no blocks not dominated by its header.
 251   //  - It's desirable to preserve the original block order when possible.
 252   // We use two ready lists; Preferred and Ready. Preferred has recently
 253   // processed successors, to help preserve block sequences from the original
 254   // order. Ready has the remaining ready blocks. EH blocks are picked first
 255   // from both queues.
 256   PriorityQueue<MachineBasicBlock *, std::vector<MachineBasicBlock *>,
 257                 CompareBlockNumbers>
 258       Preferred;
 259   PriorityQueue<MachineBasicBlock *, std::vector<MachineBasicBlock *>,
 260                 CompareBlockNumbersBackwards>
 261       Ready;
 262
 263   RegionInfo SUI(MLI, WEI);
 264   SmallVector<Entry, 4> Entries;
 265   for (MachineBasicBlock *MBB = &MF.front();;) {
 266     const Region *R = SUI.getRegionFor(MBB);
 267     if (R) {
 268       // If MBB is a region header, add it to the active region list. We can't
 269       // put any blocks that it doesn't dominate until we see the end of the
 270       // region.
 271       if (R->getHeader() == MBB)
 272         Entries.push_back(Entry(R));
 273       // For each active region the block is in, decrement the count. If MBB is
 274       // the last block in an active region, take it off the list and pick up
 275       // any blocks deferred because the header didn't dominate them.
 276       for (Entry &E : Entries)
 277         if (E.TheRegion->contains(MBB) && --E.NumBlocksLeft == 0)
 278           for (auto DeferredBlock : E.Deferred)
 279             Ready.push(DeferredBlock);
 280       while (!Entries.empty() && Entries.back().NumBlocksLeft == 0)
 281         Entries.pop_back();
 282     }
 283     // The main topological sort logic.
 284     for (MachineBasicBlock *Succ : MBB->successors()) {
 285       // Ignore backedges.
 286       if (MachineLoop *SuccL = MLI.getLoopFor(Succ))
 287         if (SuccL->getHeader() == Succ && SuccL->contains(MBB))
 288           continue;
 289       // Decrement the predecessor count. If it's now zero, it's ready.
 290       if (--NumPredsLeft[Succ->getNumber()] == 0)
 291         Preferred.push(Succ);
 292     }
 293     // Determine the block to follow MBB. First try to find a preferred block,
 294     // to preserve the original block order when possible.
 295     MachineBasicBlock *Next = nullptr;
 296     while (!Preferred.empty()) {
 297       Next = Preferred.top();
 298       Preferred.pop();
 299       // If X isn't dominated by the top active region header, defer it until
 300       // that region is done.
 301       if (!Entries.empty() &&
 302           !MDT.dominates(Entries.back().TheRegion->getHeader(), Next)) {
 303         Entries.back().Deferred.push_back(Next);
 304         Next = nullptr;
 305         continue;
 306       }
 307       // If Next was originally ordered before MBB, and it isn't because it was
 308       // loop-rotated above the header, it's not preferred.
 309       if (Next->getNumber() < MBB->getNumber() &&
 310           (!R || !R->contains(Next) ||
 311            R->getHeader()->getNumber() < Next->getNumber())) {
 312         Ready.push(Next);
 313         Next = nullptr;
 314         continue;
 315       }
 316       break;
 317     }
 318     // If we didn't find a suitable block in the Preferred list, check the
 319     // general Ready list.
 320     if (!Next) {
 321       // If there are no more blocks to process, we're done.
 322       if (Ready.empty()) {
 323         MaybeUpdateTerminator(MBB);
 324         break;
 325       }
 326       for (;;) {
 327         Next = Ready.top();
 328         Ready.pop();
 329         // If Next isn't dominated by the top active region header, defer it
 330         // until that region is done.
 331         if (!Entries.empty() &&
 332             !MDT.dominates(Entries.back().TheRegion->getHeader(), Next)) {
 333           Entries.back().Deferred.push_back(Next);
 334           continue;
 335         }
 336         break;
 337       }
 338     }
 339     // Move the next block into place and iterate.
 340     Next->moveAfter(MBB);
 341     MaybeUpdateTerminator(MBB);
 342     MBB = Next;
 343   }
 344   assert(Entries.empty() && "Active sort region list not finished");
 345   MF.RenumberBlocks();
 346
 347 #ifndef NDEBUG
 348   SmallSetVector<const Region *, 8> OnStack;
 349
 350   // Insert a sentinel representing the degenerate loop that starts at the
 351   // function entry block and includes the entire function as a "loop" that
 352   // executes once.
 353   OnStack.insert(nullptr);
 354
 355   for (auto &MBB : MF) {
 356     assert(MBB.getNumber() >= 0 && "Renumbered blocks should be non-negative.");
 357     const Region *Region = SUI.getRegionFor(&MBB);
 358
 359     if (Region && &MBB == Region->getHeader()) {
 360       if (Region->isLoop()) {
 361         // Loop header. The loop predecessor should be sorted above, and the
 362         // other predecessors should be backedges below.
 363         for (auto Pred : MBB.predecessors())
 364           assert(
 365               (Pred->getNumber() < MBB.getNumber() || Region->contains(Pred)) &&
 366               "Loop header predecessors must be loop predecessors or "
 367               "backedges");
 368       } else {
 369         // Not a loop header. All predecessors should be sorted above.
 370         for (auto Pred : MBB.predecessors())
 371           assert(Pred->getNumber() < MBB.getNumber() &&
 372                  "Non-loop-header predecessors should be topologically sorted");
 373       }
 374       assert(OnStack.insert(Region) &&
 375              "Regions should be declared at most once.");
 376
 377     } else {
 378       // Not a loop header. All predecessors should be sorted above.
 379       for (auto Pred : MBB.predecessors())
 380         assert(Pred->getNumber() < MBB.getNumber() &&
 381                "Non-loop-header predecessors should be topologically sorted");
 382       assert(OnStack.count(SUI.getRegionFor(&MBB)) &&
 383              "Blocks must be nested in their regions");
 384     }
 385     while (OnStack.size() > 1 && &MBB == WebAssembly::getBottom(OnStack.back()))
 386       OnStack.pop_back();
 387   }
 388   assert(OnStack.pop_back_val() == nullptr &&
 389          "The function entry block shouldn't actually be a region header");
 390   assert(OnStack.empty() &&
 391          "Control flow stack pushes and pops should be balanced.");
 392 #endif
 393 }
 394
 395 bool WebAssemblyCFGSort::runOnMachineFunction(MachineFunction &MF) {
 396   LLVM_DEBUG(dbgs() << "********** CFG Sorting **********\n"
 397                        "********** Function: "
 398                     << MF.getName() << '\n');
 399
 400   const auto &MLI = getAnalysis<MachineLoopInfo>();
 401   const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>();
 402   auto &MDT = getAnalysis<MachineDominatorTree>();
 403   // Liveness is not tracked for VALUE_STACK physreg.
 404   MF.getRegInfo().invalidateLiveness();
 405
 406   // Sort the blocks, with contiguous sort regions.
 407   SortBlocks(MF, MLI, WEI, MDT);
 408
 409   return true;
 410 }