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