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