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