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