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