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