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

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