373 lines · cpp
1//===--- WebAssemblyExceptionInfo.cpp - Exception Infomation --------------===//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/// \brief This file implements WebAssemblyException information analysis.11///12//===----------------------------------------------------------------------===//13 14#include "WebAssemblyExceptionInfo.h"15#include "WebAssemblyUtilities.h"16#include "llvm/ADT/DepthFirstIterator.h"17#include "llvm/ADT/PostOrderIterator.h"18#include "llvm/CodeGen/MachineDominanceFrontier.h"19#include "llvm/CodeGen/MachineDominators.h"20#include "llvm/CodeGen/WasmEHFuncInfo.h"21#include "llvm/IR/Function.h"22#include "llvm/InitializePasses.h"23#include "llvm/MC/MCAsmInfo.h"24#include "llvm/Target/TargetMachine.h"25 26using namespace llvm;27 28#define DEBUG_TYPE "wasm-exception-info"29 30char WebAssemblyExceptionInfo::ID = 0;31 32INITIALIZE_PASS_BEGIN(WebAssemblyExceptionInfo, DEBUG_TYPE,33 "WebAssembly Exception Information", true, true)34INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)35INITIALIZE_PASS_DEPENDENCY(MachineDominanceFrontier)36INITIALIZE_PASS_END(WebAssemblyExceptionInfo, DEBUG_TYPE,37 "WebAssembly Exception Information", true, true)38 39bool WebAssemblyExceptionInfo::runOnMachineFunction(MachineFunction &MF) {40 LLVM_DEBUG(dbgs() << "********** Exception Info Calculation **********\n"41 "********** Function: "42 << MF.getName() << '\n');43 releaseMemory();44 if (MF.getTarget().getMCAsmInfo()->getExceptionHandlingType() !=45 ExceptionHandling::Wasm ||46 !MF.getFunction().hasPersonalityFn())47 return false;48 auto &MDT = getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();49 auto &MDF = getAnalysis<MachineDominanceFrontier>();50 recalculate(MF, MDT, MDF);51 LLVM_DEBUG(dump());52 return false;53}54 55// Check if Dst is reachable from Src using BFS. Search only within BBs56// dominated by Header.57static bool isReachableAmongDominated(const MachineBasicBlock *Src,58 const MachineBasicBlock *Dst,59 const MachineBasicBlock *Header,60 const MachineDominatorTree &MDT) {61 assert(MDT.dominates(Header, Dst));62 SmallVector<const MachineBasicBlock *, 8> WL;63 SmallPtrSet<const MachineBasicBlock *, 8> Visited;64 WL.push_back(Src);65 66 while (!WL.empty()) {67 const auto *MBB = WL.pop_back_val();68 if (MBB == Dst)69 return true;70 Visited.insert(MBB);71 for (auto *Succ : MBB->successors())72 if (!Visited.count(Succ) && MDT.dominates(Header, Succ))73 WL.push_back(Succ);74 }75 return false;76}77 78void WebAssemblyExceptionInfo::recalculate(79 MachineFunction &MF, MachineDominatorTree &MDT,80 const MachineDominanceFrontier &MDF) {81 // Postorder traversal of the dominator tree.82 SmallVector<std::unique_ptr<WebAssemblyException>, 8> Exceptions;83 for (auto *DomNode : post_order(&MDT)) {84 MachineBasicBlock *EHPad = DomNode->getBlock();85 if (!EHPad->isEHPad())86 continue;87 auto WE = std::make_unique<WebAssemblyException>(EHPad);88 discoverAndMapException(WE.get(), MDT, MDF);89 Exceptions.push_back(std::move(WE));90 }91 92 // WasmEHFuncInfo contains a map of <catchpad, its next unwind destination>,93 // which means, if an exception is not caught by the catchpad, it should end94 // up in the next unwind destination stored in this data structure. (It is95 // written as catchswitch's 'unwind' destination in ll files.) The below is an96 // intuitive example of their relationship in C++ code:97 // try {98 // try {99 // } catch (int) { // catchpad100 // ... // this catch (int) { ... } is grouped as an exception101 // }102 // } catch (...) { // next unwind destination103 // }104 // (The example is try-catches for illustration purpose, but the unwind105 // destination can be also a cleanuppad generated by destructor calls.) So the106 // unwind destination is in the outside of the catchpad's exception.107 //108 // We group exceptions in this analysis simply by including all BBs dominated109 // by an EH pad. But in case the EH pad's unwind destination does not have any110 // children outside of the exception, that unwind destination ends up also111 // being dominated by the EH pad and included in the exception, which is not112 // semantically correct, because it unwinds/rethrows into an inner scope.113 //114 // Here we extract those unwind destinations from their (incorrect) parent115 // exception. Note that the unwind destinations may not be an immediate116 // children of the parent exception, so we have to traverse the parent chain.117 //118 // We should traverse BBs in the preorder of the dominator tree, because119 // otherwise the result can be incorrect. For example, when there are three120 // exceptions A, B, and C and A > B > C (> is subexception relationship here),121 // and A's unwind destination is B and B's is C. When we visit B before A, we122 // end up extracting C only out of B but not out of A.123 const auto *EHInfo = MF.getWasmEHFuncInfo();124 assert(EHInfo);125 SmallVector<std::pair<WebAssemblyException *, WebAssemblyException *>>126 UnwindWEVec;127 for (auto *DomNode : depth_first(&MDT)) {128 MachineBasicBlock *EHPad = DomNode->getBlock();129 if (!EHPad->isEHPad())130 continue;131 if (!EHInfo->hasUnwindDest(EHPad))132 continue;133 auto *UnwindDest = EHInfo->getUnwindDest(EHPad);134 auto *SrcWE = getExceptionFor(EHPad);135 auto *DstWE = getExceptionFor(UnwindDest);136 if (SrcWE->contains(DstWE)) {137 UnwindWEVec.push_back(std::make_pair(SrcWE, DstWE));138 LLVM_DEBUG(dbgs() << "Unwind destination ExceptionInfo fix:\n "139 << DstWE->getEHPad()->getNumber() << "."140 << DstWE->getEHPad()->getName()141 << "'s exception is taken out of "142 << SrcWE->getEHPad()->getNumber() << "."143 << SrcWE->getEHPad()->getName() << "'s exception\n");144 DstWE->setParentException(SrcWE->getParentException());145 }146 }147 148 // After fixing subexception relationship between unwind destinations above,149 // there can still be remaining discrepancies.150 //151 // For example, suppose Exception A is dominated by EHPad A and Exception B is152 // dominated by EHPad B. EHPad A's unwind destination is EHPad B, but because153 // EHPad B is dominated by EHPad A, the initial grouping makes Exception B a154 // subexception of Exception A, and we fix it by taking Exception B out of155 // Exception A above. But there can still be remaining BBs within Exception A156 // that are reachable from Exception B. These BBs semantically don't belong157 // to Exception A and were not a part of this 'catch' clause or cleanup code158 // in the original code, but they just happened to be grouped within Exception159 // A because they were dominated by EHPad A. We fix this case by taking those160 // BBs out of the incorrect exception and all its subexceptions that it161 // belongs to.162 //163 // 1. First, we take out remaining incorrect subexceptions. This part is164 // easier, because we haven't added BBs to exceptions yet, we only need to165 // change parent exception pointer.166 for (auto *DomNode : depth_first(&MDT)) {167 MachineBasicBlock *EHPad = DomNode->getBlock();168 if (!EHPad->isEHPad())169 continue;170 auto *WE = getExceptionFor(EHPad);171 172 // For each source EHPad -> unwind destination EHPad173 for (auto &P : UnwindWEVec) {174 auto *SrcWE = P.first;175 auto *DstWE = P.second;176 // If WE (the current EH pad's exception) is still contained in SrcWE but177 // reachable from DstWE that was taken out of SrcWE above, we have to take178 // out WE out of SrcWE too.179 if (WE != SrcWE && SrcWE->contains(WE) && !DstWE->contains(WE) &&180 isReachableAmongDominated(DstWE->getEHPad(), EHPad, SrcWE->getEHPad(),181 MDT)) {182 LLVM_DEBUG(dbgs() << "Remaining reachable ExceptionInfo fix:\n "183 << WE->getEHPad()->getNumber() << "."184 << WE->getEHPad()->getName()185 << "'s exception is taken out of "186 << SrcWE->getEHPad()->getNumber() << "."187 << SrcWE->getEHPad()->getName() << "'s exception\n");188 WE->setParentException(SrcWE->getParentException());189 }190 }191 }192 193 // Add BBs to exceptions' block set. This is a preparation to take out194 // remaining incorect BBs from exceptions, because we need to iterate over BBs195 // for each exception.196 for (auto *DomNode : post_order(&MDT)) {197 MachineBasicBlock *MBB = DomNode->getBlock();198 WebAssemblyException *WE = getExceptionFor(MBB);199 for (; WE; WE = WE->getParentException())200 WE->addToBlocksSet(MBB);201 }202 203 // 2. We take out remaining individual BBs out. Now we have added BBs to each204 // exceptions' BlockSet, when we take a BB out of an exception, we need to fix205 // those sets too.206 for (auto &P : UnwindWEVec) {207 auto *SrcWE = P.first;208 auto *DstWE = P.second;209 210 SrcWE->getBlocksSet().remove_if([&](MachineBasicBlock *MBB){211 if (MBB->isEHPad()) {212 assert(!isReachableAmongDominated(DstWE->getEHPad(), MBB,213 SrcWE->getEHPad(), MDT) &&214 "We already handled EH pads above");215 return false;216 }217 if (isReachableAmongDominated(DstWE->getEHPad(), MBB, SrcWE->getEHPad(),218 MDT)) {219 LLVM_DEBUG(dbgs() << "Remainder BB: " << MBB->getNumber() << "."220 << MBB->getName() << " is\n");221 WebAssemblyException *InnerWE = getExceptionFor(MBB);222 while (InnerWE != SrcWE) {223 LLVM_DEBUG(dbgs()224 << " removed from " << InnerWE->getEHPad()->getNumber()225 << "." << InnerWE->getEHPad()->getName()226 << "'s exception\n");227 InnerWE->removeFromBlocksSet(MBB);228 InnerWE = InnerWE->getParentException();229 }230 LLVM_DEBUG(dbgs() << " removed from " << SrcWE->getEHPad()->getNumber()231 << "." << SrcWE->getEHPad()->getName()232 << "'s exception\n");233 changeExceptionFor(MBB, SrcWE->getParentException());234 if (SrcWE->getParentException())235 SrcWE->getParentException()->addToBlocksSet(MBB);236 return true;237 }238 return false;239 });240 }241 242 // Add BBs to exceptions' block vector243 for (auto *DomNode : post_order(&MDT)) {244 MachineBasicBlock *MBB = DomNode->getBlock();245 WebAssemblyException *WE = getExceptionFor(MBB);246 for (; WE; WE = WE->getParentException())247 WE->addToBlocksVector(MBB);248 }249 250 SmallVector<WebAssemblyException*, 8> ExceptionPointers;251 ExceptionPointers.reserve(Exceptions.size());252 253 // Add subexceptions to exceptions254 for (auto &WE : Exceptions) {255 ExceptionPointers.push_back(WE.get());256 if (WE->getParentException())257 WE->getParentException()->getSubExceptions().push_back(std::move(WE));258 else259 addTopLevelException(std::move(WE));260 }261 262 // For convenience, Blocks and SubExceptions are inserted in postorder.263 // Reverse the lists.264 for (auto *WE : ExceptionPointers) {265 WE->reverseBlock();266 std::reverse(WE->getSubExceptions().begin(), WE->getSubExceptions().end());267 }268}269 270void WebAssemblyExceptionInfo::releaseMemory() {271 BBMap.clear();272 TopLevelExceptions.clear();273}274 275void WebAssemblyExceptionInfo::getAnalysisUsage(AnalysisUsage &AU) const {276 AU.setPreservesAll();277 AU.addRequired<MachineDominatorTreeWrapperPass>();278 AU.addRequired<MachineDominanceFrontier>();279 MachineFunctionPass::getAnalysisUsage(AU);280}281 282void WebAssemblyExceptionInfo::discoverAndMapException(283 WebAssemblyException *WE, const MachineDominatorTree &MDT,284 const MachineDominanceFrontier &MDF) {285 unsigned NumBlocks = 0;286 unsigned NumSubExceptions = 0;287 288 // Map blocks that belong to a catchpad / cleanuppad289 MachineBasicBlock *EHPad = WE->getEHPad();290 SmallVector<MachineBasicBlock *, 8> WL;291 WL.push_back(EHPad);292 while (!WL.empty()) {293 MachineBasicBlock *MBB = WL.pop_back_val();294 295 // Find its outermost discovered exception. If this is a discovered block,296 // check if it is already discovered to be a subexception of this exception.297 WebAssemblyException *SubE = getOutermostException(MBB);298 if (SubE) {299 if (SubE != WE) {300 // Discover a subexception of this exception.301 SubE->setParentException(WE);302 ++NumSubExceptions;303 NumBlocks += SubE->getBlocksVector().capacity();304 // All blocks that belong to this subexception have been already305 // discovered. Skip all of them. Add the subexception's landing pad's306 // dominance frontier to the worklist.307 for (auto &Frontier : MDF.find(SubE->getEHPad())->second)308 if (MDT.dominates(EHPad, Frontier))309 WL.push_back(Frontier);310 }311 continue;312 }313 314 // This is an undiscovered block. Map it to the current exception.315 changeExceptionFor(MBB, WE);316 ++NumBlocks;317 318 // Add successors dominated by the current BB to the worklist.319 for (auto *Succ : MBB->successors())320 if (MDT.dominates(EHPad, Succ))321 WL.push_back(Succ);322 }323 324 WE->getSubExceptions().reserve(NumSubExceptions);325 WE->reserveBlocks(NumBlocks);326}327 328WebAssemblyException *329WebAssemblyExceptionInfo::getOutermostException(MachineBasicBlock *MBB) const {330 WebAssemblyException *WE = getExceptionFor(MBB);331 if (WE) {332 while (WebAssemblyException *Parent = WE->getParentException())333 WE = Parent;334 }335 return WE;336}337 338void WebAssemblyException::print(raw_ostream &OS, unsigned Depth) const {339 OS.indent(Depth * 2) << "Exception at depth " << getExceptionDepth()340 << " containing: ";341 342 for (unsigned I = 0; I < getBlocks().size(); ++I) {343 MachineBasicBlock *MBB = getBlocks()[I];344 if (I)345 OS << ", ";346 OS << "%bb." << MBB->getNumber();347 if (const auto *BB = MBB->getBasicBlock())348 if (BB->hasName())349 OS << "." << BB->getName();350 351 if (getEHPad() == MBB)352 OS << " (landing-pad)";353 }354 OS << "\n";355 356 for (auto &SubE : SubExceptions)357 SubE->print(OS, Depth + 2);358}359 360#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)361LLVM_DUMP_METHOD void WebAssemblyException::dump() const { print(dbgs()); }362#endif363 364raw_ostream &operator<<(raw_ostream &OS, const WebAssemblyException &WE) {365 WE.print(OS);366 return OS;367}368 369void WebAssemblyExceptionInfo::print(raw_ostream &OS, const Module *) const {370 for (auto &WE : TopLevelExceptions)371 WE->print(OS);372}373