399 lines · 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-exception6//7//===----------------------------------------------------------------------===//8///9/// \file10/// This file implements a CFG sorting pass.11///12/// This pass reorders the blocks in a function to put them into topological13/// order, ignoring loop backedges, and without any loop or exception being14/// interrupted by a block not dominated by the its header, with special care15/// to keep the order as similar as possible to the original order.16///17////===----------------------------------------------------------------------===//18 19#include "WebAssembly.h"20#include "WebAssemblyExceptionInfo.h"21#include "WebAssemblySortRegion.h"22#include "WebAssemblyUtilities.h"23#include "llvm/ADT/PriorityQueue.h"24#include "llvm/ADT/SetVector.h"25#include "llvm/CodeGen/MachineDominators.h"26#include "llvm/CodeGen/MachineFunction.h"27#include "llvm/CodeGen/MachineLoopInfo.h"28#include "llvm/CodeGen/MachineRegisterInfo.h"29#include "llvm/CodeGen/Passes.h"30#include "llvm/CodeGen/WasmEHFuncInfo.h"31#include "llvm/Support/Debug.h"32#include "llvm/Support/raw_ostream.h"33using namespace llvm;34using WebAssembly::SortRegion;35using WebAssembly::SortRegionInfo;36 37#define DEBUG_TYPE "wasm-cfg-sort"38 39// Option to disable EH pad first sorting. Only for testing unwind destination40// mismatches in CFGStackify.41static cl::opt<bool> WasmDisableEHPadSort(42 "wasm-disable-ehpad-sort", cl::ReallyHidden,43 cl::desc(44 "WebAssembly: Disable EH pad-first sort order. Testing purpose only."),45 cl::init(false));46 47namespace {48 49class WebAssemblyCFGSort final : public MachineFunctionPass {50 StringRef getPassName() const override { return "WebAssembly CFG Sort"; }51 52 void getAnalysisUsage(AnalysisUsage &AU) const override {53 AU.setPreservesCFG();54 AU.addRequired<MachineDominatorTreeWrapperPass>();55 AU.addPreserved<MachineDominatorTreeWrapperPass>();56 AU.addRequired<MachineLoopInfoWrapperPass>();57 AU.addPreserved<MachineLoopInfoWrapperPass>();58 AU.addRequired<WebAssemblyExceptionInfo>();59 AU.addPreserved<WebAssemblyExceptionInfo>();60 MachineFunctionPass::getAnalysisUsage(AU);61 }62 63 bool runOnMachineFunction(MachineFunction &MF) override;64 65public:66 static char ID; // Pass identification, replacement for typeid67 WebAssemblyCFGSort() : MachineFunctionPass(ID) {}68};69} // end anonymous namespace70 71char WebAssemblyCFGSort::ID = 0;72INITIALIZE_PASS(WebAssemblyCFGSort, DEBUG_TYPE,73 "Reorders blocks in topological order", false, false)74 75FunctionPass *llvm::createWebAssemblyCFGSort() {76 return new WebAssemblyCFGSort();77}78 79static void maybeUpdateTerminator(MachineBasicBlock *MBB) {80#ifndef NDEBUG81 bool AnyBarrier = false;82#endif83 bool AllAnalyzable = true;84 for (const MachineInstr &Term : MBB->terminators()) {85#ifndef NDEBUG86 AnyBarrier |= Term.isBarrier();87#endif88 AllAnalyzable &= Term.isBranch() && !Term.isIndirectBranch();89 }90 assert((AnyBarrier || AllAnalyzable) &&91 "analyzeBranch needs to analyze any block with a fallthrough");92 93 // Find the layout successor from the original block order.94 MachineFunction *MF = MBB->getParent();95 MachineBasicBlock *OriginalSuccessor =96 unsigned(MBB->getNumber() + 1) < MF->getNumBlockIDs()97 ? MF->getBlockNumbered(MBB->getNumber() + 1)98 : nullptr;99 100 if (AllAnalyzable)101 MBB->updateTerminator(OriginalSuccessor);102}103 104namespace {105// EH pads are selected first regardless of the block comparison order.106// When only one of the BBs is an EH pad, we give a higher priority to it, to107// prevent common mismatches between possibly throwing calls and ehpads they108// unwind to, as in the example below:109//110// bb0:111// call @foo // If this throws, unwind to bb2112// bb1:113// call @bar // If this throws, unwind to bb3114// bb2 (ehpad):115// handler_bb2116// bb3 (ehpad):117// handler_bb3118// continuing code119//120// Because this pass tries to preserve the original BB order, this order will121// not change. But this will result in this try-catch structure in CFGStackify,122// resulting in a mismatch:123// try124// try125// call @foo126// call @bar // This should unwind to bb3, not bb2!127// catch128// handler_bb2129// end130// catch131// handler_bb3132// end133// continuing code134//135// If we give a higher priority to an EH pad whenever it is ready in this136// example, when both bb1 and bb2 are ready, we would pick up bb2 first.137 138/// Sort blocks by their number.139struct CompareBlockNumbers {140 bool operator()(const MachineBasicBlock *A,141 const MachineBasicBlock *B) const {142 if (!WasmDisableEHPadSort) {143 if (A->isEHPad() && !B->isEHPad())144 return false;145 if (!A->isEHPad() && B->isEHPad())146 return true;147 }148 149 return A->getNumber() > B->getNumber();150 }151};152/// Sort blocks by their number in the opposite order..153struct CompareBlockNumbersBackwards {154 bool operator()(const MachineBasicBlock *A,155 const MachineBasicBlock *B) const {156 if (!WasmDisableEHPadSort) {157 if (A->isEHPad() && !B->isEHPad())158 return false;159 if (!A->isEHPad() && B->isEHPad())160 return true;161 }162 163 return A->getNumber() < B->getNumber();164 }165};166/// Bookkeeping for a region to help ensure that we don't mix blocks not167/// dominated by the its header among its blocks.168struct Entry {169 const SortRegion *TheRegion;170 unsigned NumBlocksLeft;171 172 /// List of blocks not dominated by Loop's header that are deferred until173 /// after all of Loop's blocks have been seen.174 std::vector<MachineBasicBlock *> Deferred;175 176 explicit Entry(const SortRegion *R)177 : TheRegion(R), NumBlocksLeft(R->getNumBlocks()) {}178};179} // end anonymous namespace180 181/// Sort the blocks, taking special care to make sure that regions are not182/// interrupted by blocks not dominated by their header.183/// TODO: There are many opportunities for improving the heuristics here.184/// Explore them.185static void sortBlocks(MachineFunction &MF, const MachineLoopInfo &MLI,186 const WebAssemblyExceptionInfo &WEI,187 MachineDominatorTree &MDT) {188 // Remember original layout ordering, so we can update terminators after189 // reordering to point to the original layout successor.190 MF.RenumberBlocks();191 MDT.updateBlockNumbers();192 193 // Prepare for a topological sort: Record the number of predecessors each194 // 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 be208 // 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 recently211 // processed successors, to help preserve block sequences from the original212 // order. Ready has the remaining ready blocks. EH blocks are picked first213 // 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 const auto *EHInfo = MF.getWasmEHFuncInfo();222 SortRegionInfo SRI(MLI, WEI);223 SmallVector<Entry, 4> Entries;224 for (MachineBasicBlock *MBB = &MF.front();;) {225 const SortRegion *R = SRI.getRegionFor(MBB);226 if (R) {227 // If MBB is a region header, add it to the active region list. We can't228 // put any blocks that it doesn't dominate until we see the end of the229 // region.230 if (R->getHeader() == MBB)231 Entries.push_back(Entry(R));232 // For each active region the block is in, decrement the count. If MBB is233 // the last block in an active region, take it off the list and pick up234 // any blocks deferred because the header didn't dominate them.235 for (Entry &E : Entries)236 if (E.TheRegion->contains(MBB) && --E.NumBlocksLeft == 0)237 for (auto *DeferredBlock : E.Deferred)238 Ready.push(DeferredBlock);239 while (!Entries.empty() && Entries.back().NumBlocksLeft == 0)240 Entries.pop_back();241 }242 // The main topological sort logic.243 for (MachineBasicBlock *Succ : MBB->successors()) {244 // Ignore backedges.245 if (MachineLoop *SuccL = MLI.getLoopFor(Succ))246 if (SuccL->getHeader() == Succ && SuccL->contains(MBB))247 continue;248 // Decrement the predecessor count. If it's now zero, it's ready.249 if (--NumPredsLeft[Succ->getNumber()] == 0) {250 // When we are in a SortRegion, we allow sorting of not only BBs that251 // belong to the current (innermost) region but also BBs that are252 // dominated by the current region header. But we should not do this for253 // exceptions because there can be cases in which, for example:254 // EHPad A's unwind destination (where the exception lands when it is255 // not caught by EHPad A) is EHPad B, so EHPad B does not belong to the256 // exception dominated by EHPad A. But EHPad B is dominated by EHPad A,257 // so EHPad B can be sorted within EHPad A's exception. This is258 // incorrect because we may end up delegating/rethrowing to an inner259 // scope in CFGStackify. So here we make sure those unwind destinations260 // are deferred until their unwind source's exception is sorted.261 if (EHInfo && EHInfo->hasUnwindSrcs(Succ)) {262 SmallPtrSet<MachineBasicBlock *, 4> UnwindSrcs =263 EHInfo->getUnwindSrcs(Succ);264 bool IsDeferred = false;265 for (Entry &E : Entries) {266 if (UnwindSrcs.count(E.TheRegion->getHeader())) {267 E.Deferred.push_back(Succ);268 IsDeferred = true;269 break;270 }271 }272 if (IsDeferred)273 continue;274 }275 Preferred.push(Succ);276 }277 }278 // Determine the block to follow MBB. First try to find a preferred block,279 // to preserve the original block order when possible.280 MachineBasicBlock *Next = nullptr;281 while (!Preferred.empty()) {282 Next = Preferred.top();283 Preferred.pop();284 // If X isn't dominated by the top active region header, defer it until285 // that region is done.286 if (!Entries.empty() &&287 !MDT.dominates(Entries.back().TheRegion->getHeader(), Next)) {288 Entries.back().Deferred.push_back(Next);289 Next = nullptr;290 continue;291 }292 // If Next was originally ordered before MBB, and it isn't because it was293 // loop-rotated above the header, it's not preferred.294 if (Next->getNumber() < MBB->getNumber() &&295 (WasmDisableEHPadSort || !Next->isEHPad()) &&296 (!R || !R->contains(Next) ||297 R->getHeader()->getNumber() < Next->getNumber())) {298 Ready.push(Next);299 Next = nullptr;300 continue;301 }302 break;303 }304 // If we didn't find a suitable block in the Preferred list, check the305 // general Ready list.306 if (!Next) {307 // If there are no more blocks to process, we're done.308 if (Ready.empty()) {309 maybeUpdateTerminator(MBB);310 break;311 }312 for (;;) {313 Next = Ready.top();314 Ready.pop();315 // If Next isn't dominated by the top active region header, defer it316 // until that region is done.317 if (!Entries.empty() &&318 !MDT.dominates(Entries.back().TheRegion->getHeader(), Next)) {319 Entries.back().Deferred.push_back(Next);320 continue;321 }322 break;323 }324 }325 // Move the next block into place and iterate.326 Next->moveAfter(MBB);327 maybeUpdateTerminator(MBB);328 MBB = Next;329 }330 assert(Entries.empty() && "Active sort region list not finished");331 MF.RenumberBlocks();332 MDT.updateBlockNumbers();333 334#ifndef NDEBUG335 SmallSetVector<const SortRegion *, 8> OnStack;336 337 // Insert a sentinel representing the degenerate loop that starts at the338 // function entry block and includes the entire function as a "loop" that339 // executes once.340 OnStack.insert(nullptr);341 342 for (auto &MBB : MF) {343 assert(MBB.getNumber() >= 0 && "Renumbered blocks should be non-negative.");344 const SortRegion *Region = SRI.getRegionFor(&MBB);345 346 if (Region && &MBB == Region->getHeader()) {347 // Region header.348 if (Region->isLoop()) {349 // Loop header. The loop predecessor should be sorted above, and the350 // other predecessors should be backedges below.351 for (auto *Pred : MBB.predecessors())352 assert(353 (Pred->getNumber() < MBB.getNumber() || Region->contains(Pred)) &&354 "Loop header predecessors must be loop predecessors or "355 "backedges");356 } else {357 // Exception header. All predecessors should be sorted above.358 for (auto *Pred : MBB.predecessors())359 assert(Pred->getNumber() < MBB.getNumber() &&360 "Non-loop-header predecessors should be topologically sorted");361 }362 assert(OnStack.insert(Region) &&363 "Regions should be declared at most once.");364 365 } else {366 // Not a region header. All predecessors should be sorted above.367 for (auto *Pred : MBB.predecessors())368 assert(Pred->getNumber() < MBB.getNumber() &&369 "Non-loop-header predecessors should be topologically sorted");370 assert(OnStack.count(SRI.getRegionFor(&MBB)) &&371 "Blocks must be nested in their regions");372 }373 while (OnStack.size() > 1 && &MBB == SRI.getBottom(OnStack.back()))374 OnStack.pop_back();375 }376 assert(OnStack.pop_back_val() == nullptr &&377 "The function entry block shouldn't actually be a region header");378 assert(OnStack.empty() &&379 "Control flow stack pushes and pops should be balanced.");380#endif381}382 383bool WebAssemblyCFGSort::runOnMachineFunction(MachineFunction &MF) {384 LLVM_DEBUG(dbgs() << "********** CFG Sorting **********\n"385 "********** Function: "386 << MF.getName() << '\n');387 388 const auto &MLI = getAnalysis<MachineLoopInfoWrapperPass>().getLI();389 const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>();390 auto &MDT = getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();391 // Liveness is not tracked for VALUE_STACK physreg.392 MF.getRegInfo().invalidateLiveness();393 394 // Sort the blocks, with contiguous sort regions.395 sortBlocks(MF, MLI, WEI, MDT);396 397 return true;398}399