contrib/llvm/lib/Target/WebAssembly/WebAssemblyExceptionInfo.cpp

   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 }