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