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