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 "WebAssemblyUtilities.h"
16#include "llvm/ADT/PostOrderIterator.h"
17#include "llvm/CodeGen/MachineDominanceFrontier.h"
18#include "llvm/CodeGen/MachineDominators.h"
19#include "llvm/IR/Function.h"
20#include "llvm/InitializePasses.h"
21#include "llvm/MC/MCAsmInfo.h"
22#include "llvm/Target/TargetMachine.h"
23
24using namespace llvm;
25
26#define DEBUG_TYPE "wasm-exception-info"
27
28char WebAssemblyExceptionInfo::ID = 0;
29
30INITIALIZE_PASS_BEGIN(WebAssemblyExceptionInfo, DEBUG_TYPE,
31 "WebAssembly Exception Information", true, true)
32INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
33INITIALIZE_PASS_DEPENDENCY(MachineDominanceFrontierWrapperPass)
34INITIALIZE_PASS_END(WebAssemblyExceptionInfo, DEBUG_TYPE,
35 "WebAssembly Exception Information", true, true)
36
37bool WebAssemblyExceptionInfo::runOnMachineFunction(MachineFunction &MF) {
38 LLVM_DEBUG(dbgs() << "********** Exception Info Calculation **********\n"
39 "********** Function: "
40 << MF.getName() << '\n');
41 releaseMemory();
42 if (MF.getTarget().getMCAsmInfo().getExceptionHandlingType() !=
43 ExceptionHandling::Wasm ||
44 !MF.getFunction().hasPersonalityFn())
45 return false;
46 auto &MDT = getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
47 auto &MDF = getAnalysis<MachineDominanceFrontierWrapperPass>().getMDF();
48 recalculate(MF, MDT, MDF);
49 LLVM_DEBUG(dump());
50 return false;
51}
52
53void WebAssemblyExceptionInfo::recalculate(
54 MachineFunction &MF, MachineDominatorTree &MDT,
55 const MachineDominanceFrontier &MDF) {
56 // Postorder traversal of the dominator tree.
57 SmallVector<std::unique_ptr<WebAssemblyException>, 8> Exceptions;
58 for (auto *DomNode : post_order(G: &MDT)) {
59 MachineBasicBlock *EHPad = DomNode->getBlock();
60 if (!EHPad->isEHPad())
61 continue;
62 auto WE = std::make_unique<WebAssemblyException>(args&: EHPad);
63 discoverAndMapException(WE: WE.get(), MDT, MDF);
64 Exceptions.push_back(Elt: std::move(WE));
65 }
66
67 // Add BBs to exceptions' block set. This is a preparation to take out
68 // remaining incorect BBs from exceptions, because we need to iterate over BBs
69 // for each exception.
70 for (auto *DomNode : post_order(G: &MDT)) {
71 MachineBasicBlock *MBB = DomNode->getBlock();
72 WebAssemblyException *WE = getExceptionFor(MBB);
73 for (; WE; WE = WE->getParentException())
74 WE->addToBlocksSet(MBB);
75 }
76
77 // Add BBs to exceptions' block vector
78 for (auto *DomNode : post_order(G: &MDT)) {
79 MachineBasicBlock *MBB = DomNode->getBlock();
80 WebAssemblyException *WE = getExceptionFor(MBB);
81 for (; WE; WE = WE->getParentException())
82 WE->addToBlocksVector(MBB);
83 }
84
85 SmallVector<WebAssemblyException*, 8> ExceptionPointers;
86 ExceptionPointers.reserve(N: Exceptions.size());
87
88 // Add subexceptions to exceptions
89 for (auto &WE : Exceptions) {
90 ExceptionPointers.push_back(Elt: WE.get());
91 if (WE->getParentException())
92 WE->getParentException()->getSubExceptions().push_back(x: std::move(WE));
93 else
94 addTopLevelException(WE: std::move(WE));
95 }
96
97 // For convenience, Blocks and SubExceptions are inserted in postorder.
98 // Reverse the lists.
99 for (auto *WE : ExceptionPointers) {
100 WE->reverseBlock();
101 std::reverse(first: WE->getSubExceptions().begin(), last: WE->getSubExceptions().end());
102 }
103}
104
105void WebAssemblyExceptionInfo::releaseMemory() {
106 BBMap.clear();
107 TopLevelExceptions.clear();
108}
109
110void WebAssemblyExceptionInfo::getAnalysisUsage(AnalysisUsage &AU) const {
111 AU.setPreservesAll();
112 AU.addRequired<MachineDominatorTreeWrapperPass>();
113 AU.addRequired<MachineDominanceFrontierWrapperPass>();
114 MachineFunctionPass::getAnalysisUsage(AU);
115}
116
117void WebAssemblyExceptionInfo::discoverAndMapException(
118 WebAssemblyException *WE, const MachineDominatorTree &MDT,
119 const MachineDominanceFrontier &MDF) {
120 unsigned NumBlocks = 0;
121 unsigned NumSubExceptions = 0;
122
123 // Map blocks that belong to a catchpad / cleanuppad
124 MachineBasicBlock *EHPad = WE->getEHPad();
125 SmallVector<MachineBasicBlock *, 8> WL;
126 WL.push_back(Elt: EHPad);
127 while (!WL.empty()) {
128 MachineBasicBlock *MBB = WL.pop_back_val();
129
130 // Find its outermost discovered exception. If this is a discovered block,
131 // check if it is already discovered to be a subexception of this exception.
132 WebAssemblyException *SubE = getOutermostException(MBB);
133 if (SubE) {
134 if (SubE != WE) {
135 // Discover a subexception of this exception.
136 SubE->setParentException(WE);
137 ++NumSubExceptions;
138 NumBlocks += SubE->getBlocksVector().capacity();
139 // All blocks that belong to this subexception have been already
140 // discovered. Skip all of them. Add the subexception's landing pad's
141 // dominance frontier to the worklist.
142 for (auto &Frontier : MDF.find(B: SubE->getEHPad())->second)
143 if (MDT.dominates(A: EHPad, B: Frontier))
144 WL.push_back(Elt: Frontier);
145 }
146 continue;
147 }
148
149 // This is an undiscovered block. Map it to the current exception.
150 changeExceptionFor(MBB, WE);
151 ++NumBlocks;
152
153 // Add successors dominated by the current BB to the worklist.
154 for (auto *Succ : MBB->successors())
155 if (MDT.dominates(A: EHPad, B: Succ))
156 WL.push_back(Elt: Succ);
157 }
158
159 WE->getSubExceptions().reserve(n: NumSubExceptions);
160 WE->reserveBlocks(Size: NumBlocks);
161}
162
163WebAssemblyException *
164WebAssemblyExceptionInfo::getOutermostException(MachineBasicBlock *MBB) const {
165 WebAssemblyException *WE = getExceptionFor(MBB);
166 if (WE) {
167 while (WebAssemblyException *Parent = WE->getParentException())
168 WE = Parent;
169 }
170 return WE;
171}
172
173void WebAssemblyException::print(raw_ostream &OS, unsigned Depth) const {
174 OS.indent(NumSpaces: Depth * 2) << "Exception at depth " << getExceptionDepth()
175 << " containing: ";
176
177 for (unsigned I = 0; I < getBlocks().size(); ++I) {
178 MachineBasicBlock *MBB = getBlocks()[I];
179 if (I)
180 OS << ", ";
181 OS << "%bb." << MBB->getNumber();
182 if (const auto *BB = MBB->getBasicBlock())
183 if (BB->hasName())
184 OS << "." << BB->getName();
185
186 if (getEHPad() == MBB)
187 OS << " (landing-pad)";
188 }
189 OS << "\n";
190
191 for (auto &SubE : SubExceptions)
192 SubE->print(OS, Depth: Depth + 2);
193}
194
195#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
196LLVM_DUMP_METHOD void WebAssemblyException::dump() const { print(dbgs()); }
197#endif
198
199raw_ostream &operator<<(raw_ostream &OS, const WebAssemblyException &WE) {
200 WE.print(OS);
201 return OS;
202}
203
204void WebAssemblyExceptionInfo::print(raw_ostream &OS, const Module *) const {
205 for (auto &WE : TopLevelExceptions)
206 WE->print(OS);
207}
208