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-exception 6 // 7 //===----------------------------------------------------------------------===// 8 /// 9 /// \file 10 /// \brief This file implements WebAssemblyException information analysis. 11 /// 12 //===----------------------------------------------------------------------===// 13 14 #include "WebAssemblyExceptionInfo.h" 15 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h" 16 #include "WebAssemblyUtilities.h" 17 #include "llvm/ADT/PostOrderIterator.h" 18 #include "llvm/CodeGen/MachineDominanceFrontier.h" 19 #include "llvm/CodeGen/MachineDominators.h" 20 21 using namespace llvm; 22 23 #define DEBUG_TYPE "wasm-exception-info" 24 25 char WebAssemblyExceptionInfo::ID = 0; 26 27 INITIALIZE_PASS_BEGIN(WebAssemblyExceptionInfo, DEBUG_TYPE, 28 "WebAssembly Exception Information", true, true) 29 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 30 INITIALIZE_PASS_DEPENDENCY(MachineDominanceFrontier) 31 INITIALIZE_PASS_END(WebAssemblyExceptionInfo, DEBUG_TYPE, 32 "WebAssembly Exception Information", true, true) 33 34 bool WebAssemblyExceptionInfo::runOnMachineFunction(MachineFunction &MF) { 35 LLVM_DEBUG(dbgs() << "********** Exception Info Calculation **********\n" 36 "********** Function: " 37 << MF.getName() << '\n'); 38 releaseMemory(); 39 auto &MDT = getAnalysis<MachineDominatorTree>(); 40 auto &MDF = getAnalysis<MachineDominanceFrontier>(); 41 recalculate(MDT, MDF); 42 return false; 43 } 44 45 void WebAssemblyExceptionInfo::recalculate( 46 MachineDominatorTree &MDT, const MachineDominanceFrontier &MDF) { 47 // Postorder traversal of the dominator tree. 48 SmallVector<WebAssemblyException *, 8> Exceptions; 49 for (auto DomNode : post_order(&MDT)) { 50 MachineBasicBlock *EHPad = DomNode->getBlock(); 51 if (!EHPad->isEHPad()) 52 continue; 53 // We group catch & catch-all terminate pads together, so skip the second 54 // one 55 if (WebAssembly::isCatchAllTerminatePad(*EHPad)) 56 continue; 57 auto *WE = new WebAssemblyException(EHPad); 58 discoverAndMapException(WE, MDT, MDF); 59 Exceptions.push_back(WE); 60 } 61 62 // Add BBs to exceptions 63 for (auto DomNode : post_order(&MDT)) { 64 MachineBasicBlock *MBB = DomNode->getBlock(); 65 WebAssemblyException *WE = getExceptionFor(MBB); 66 for (; WE; WE = WE->getParentException()) 67 WE->addBlock(MBB); 68 } 69 70 // Add subexceptions to exceptions 71 for (auto *WE : Exceptions) { 72 if (WE->getParentException()) 73 WE->getParentException()->getSubExceptions().push_back(WE); 74 else 75 addTopLevelException(WE); 76 } 77 78 // For convenience, Blocks and SubExceptions are inserted in postorder. 79 // Reverse the lists. 80 for (auto *WE : Exceptions) { 81 WE->reverseBlock(); 82 std::reverse(WE->getSubExceptions().begin(), WE->getSubExceptions().end()); 83 } 84 } 85 86 void WebAssemblyExceptionInfo::releaseMemory() { 87 BBMap.clear(); 88 DeleteContainerPointers(TopLevelExceptions); 89 TopLevelExceptions.clear(); 90 } 91 92 void WebAssemblyExceptionInfo::getAnalysisUsage(AnalysisUsage &AU) const { 93 AU.setPreservesAll(); 94 AU.addRequired<MachineDominatorTree>(); 95 AU.addRequired<MachineDominanceFrontier>(); 96 MachineFunctionPass::getAnalysisUsage(AU); 97 } 98 99 void WebAssemblyExceptionInfo::discoverAndMapException( 100 WebAssemblyException *WE, const MachineDominatorTree &MDT, 101 const MachineDominanceFrontier &MDF) { 102 unsigned NumBlocks = 0; 103 unsigned NumSubExceptions = 0; 104 105 // Map blocks that belong to a catchpad / cleanuppad 106 MachineBasicBlock *EHPad = WE->getEHPad(); 107 108 // We group catch & catch-all terminate pads together within an exception 109 if (WebAssembly::isCatchTerminatePad(*EHPad)) { 110 assert(EHPad->succ_size() == 1 && 111 "Catch terminate pad has more than one successors"); 112 changeExceptionFor(EHPad, WE); 113 changeExceptionFor(*(EHPad->succ_begin()), WE); 114 return; 115 } 116 117 SmallVector<MachineBasicBlock *, 8> WL; 118 WL.push_back(EHPad); 119 while (!WL.empty()) { 120 MachineBasicBlock *MBB = WL.pop_back_val(); 121 122 // Find its outermost discovered exception. If this is a discovered block, 123 // check if it is already discovered to be a subexception of this exception. 124 WebAssemblyException *SubE = getOutermostException(MBB); 125 if (SubE) { 126 if (SubE != WE) { 127 // Discover a subexception of this exception. 128 SubE->setParentException(WE); 129 ++NumSubExceptions; 130 NumBlocks += SubE->getBlocksVector().capacity(); 131 // All blocks that belong to this subexception have been already 132 // discovered. Skip all of them. Add the subexception's landing pad's 133 // dominance frontier to the worklist. 134 for (auto &Frontier : MDF.find(SubE->getEHPad())->second) 135 if (MDT.dominates(EHPad, Frontier)) 136 WL.push_back(Frontier); 137 } 138 continue; 139 } 140 141 // This is an undiscovered block. Map it to the current exception. 142 changeExceptionFor(MBB, WE); 143 ++NumBlocks; 144 145 // Add successors dominated by the current BB to the worklist. 146 for (auto *Succ : MBB->successors()) 147 if (MDT.dominates(EHPad, Succ)) 148 WL.push_back(Succ); 149 } 150 151 WE->getSubExceptions().reserve(NumSubExceptions); 152 WE->reserveBlocks(NumBlocks); 153 } 154 155 WebAssemblyException * 156 WebAssemblyExceptionInfo::getOutermostException(MachineBasicBlock *MBB) const { 157 WebAssemblyException *WE = getExceptionFor(MBB); 158 if (WE) { 159 while (WebAssemblyException *Parent = WE->getParentException()) 160 WE = Parent; 161 } 162 return WE; 163 } 164 165 void WebAssemblyException::print(raw_ostream &OS, unsigned Depth) const { 166 OS.indent(Depth * 2) << "Exception at depth " << getExceptionDepth() 167 << " containing: "; 168 169 for (unsigned I = 0; I < getBlocks().size(); ++I) { 170 MachineBasicBlock *MBB = getBlocks()[I]; 171 if (I) 172 OS << ", "; 173 OS << "%bb." << MBB->getNumber(); 174 if (const auto *BB = MBB->getBasicBlock()) 175 if (BB->hasName()) 176 OS << "." << BB->getName(); 177 178 if (getEHPad() == MBB) 179 OS << " (landing-pad)"; 180 } 181 OS << "\n"; 182 183 for (auto &SubE : SubExceptions) 184 SubE->print(OS, Depth + 2); 185 } 186 187 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 188 LLVM_DUMP_METHOD void WebAssemblyException::dump() const { print(dbgs()); } 189 #endif 190 191 raw_ostream &operator<<(raw_ostream &OS, const WebAssemblyException &WE) { 192 WE.print(OS); 193 return OS; 194 } 195 196 void WebAssemblyExceptionInfo::print(raw_ostream &OS, const Module *) const { 197 for (auto *WE : TopLevelExceptions) 198 WE->print(OS); 199 } 200