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