1//===-- WebAssemblyExceptionInfo.h - WebAssembly Exception Info -*- C++ -*-===//
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#ifndef LLVM_LIB_TARGET_WEBASSEMBLY_WEBASSEMBLYEXCEPTIONINFO_H
15#define LLVM_LIB_TARGET_WEBASSEMBLY_WEBASSEMBLYEXCEPTIONINFO_H
16
17#include "WebAssembly.h"
18#include "llvm/ADT/SmallPtrSet.h"
19#include "llvm/CodeGen/MachineFunctionAnalysisManager.h"
20#include "llvm/CodeGen/MachineFunctionPass.h"
21#include "llvm/IR/Analysis.h"
22#include "llvm/IR/PassManager.h"
23#include "llvm/Pass.h"
24
25namespace llvm {
26
27class MachineDominatorTree;
28class MachineDominanceFrontier;
29
30// WebAssembly instructions for exception handling are structured as follows:
31// try
32// instructions*
33// catch ----|
34// instructions* | -> A WebAssemblyException consists of this region
35// end ----|
36//
37// A WebAssemblyException object contains BBs that belong to a 'catch' part of
38// the try-catch-end structure to be created later. 'try' and 'end' markers
39// are not present at this stage and will be generated in CFGStackify pass.
40// Because CFGSort requires all the BBs within a catch part to be sorted
41// together as it does for loops, this pass calculates the nesting structure of
42// catch part of exceptions in a function.
43//
44// An exception catch part is defined as a BB with catch instruction and all
45// other BBs dominated by this BB.
46class WebAssemblyException {
47 MachineBasicBlock *EHPad = nullptr;
48
49 WebAssemblyException *ParentException = nullptr;
50 std::vector<std::unique_ptr<WebAssemblyException>> SubExceptions;
51 std::vector<MachineBasicBlock *> Blocks;
52 SmallPtrSet<MachineBasicBlock *, 8> BlockSet;
53
54public:
55 WebAssemblyException(MachineBasicBlock *EHPad) : EHPad(EHPad) {}
56 WebAssemblyException(const WebAssemblyException &) = delete;
57 const WebAssemblyException &operator=(const WebAssemblyException &) = delete;
58
59 MachineBasicBlock *getEHPad() const { return EHPad; }
60 MachineBasicBlock *getHeader() const { return EHPad; }
61 WebAssemblyException *getParentException() const { return ParentException; }
62 void setParentException(WebAssemblyException *WE) { ParentException = WE; }
63
64 bool contains(const WebAssemblyException *WE) const {
65 if (WE == this)
66 return true;
67 if (!WE)
68 return false;
69 return contains(WE: WE->getParentException());
70 }
71 bool contains(const MachineBasicBlock *MBB) const {
72 return BlockSet.count(Ptr: MBB);
73 }
74
75 void addToBlocksSet(MachineBasicBlock *MBB) { BlockSet.insert(Ptr: MBB); }
76 void removeFromBlocksSet(MachineBasicBlock *MBB) { BlockSet.erase(Ptr: MBB); }
77 void addToBlocksVector(MachineBasicBlock *MBB) { Blocks.push_back(x: MBB); }
78 void addBlock(MachineBasicBlock *MBB) {
79 Blocks.push_back(x: MBB);
80 BlockSet.insert(Ptr: MBB);
81 }
82 ArrayRef<MachineBasicBlock *> getBlocks() const { return Blocks; }
83 using block_iterator = ArrayRef<MachineBasicBlock *>::const_iterator;
84 block_iterator block_begin() const { return getBlocks().begin(); }
85 block_iterator block_end() const { return getBlocks().end(); }
86 inline iterator_range<block_iterator> blocks() const {
87 return make_range(x: block_begin(), y: block_end());
88 }
89 unsigned getNumBlocks() const { return Blocks.size(); }
90 std::vector<MachineBasicBlock *> &getBlocksVector() { return Blocks; }
91 SmallPtrSetImpl<MachineBasicBlock *> &getBlocksSet() { return BlockSet; }
92
93 const std::vector<std::unique_ptr<WebAssemblyException>> &
94 getSubExceptions() const {
95 return SubExceptions;
96 }
97 std::vector<std::unique_ptr<WebAssemblyException>> &getSubExceptions() {
98 return SubExceptions;
99 }
100 void addSubException(std::unique_ptr<WebAssemblyException> E) {
101 SubExceptions.push_back(x: std::move(E));
102 }
103 using iterator = decltype(SubExceptions)::const_iterator;
104 iterator begin() const { return SubExceptions.begin(); }
105 iterator end() const { return SubExceptions.end(); }
106
107 void reserveBlocks(unsigned Size) { Blocks.reserve(n: Size); }
108 void reverseBlock(unsigned From = 0) {
109 std::reverse(first: Blocks.begin() + From, last: Blocks.end());
110 }
111
112 // Return the nesting level. An outermost one has depth 1.
113 unsigned getExceptionDepth() const {
114 unsigned D = 1;
115 for (const WebAssemblyException *CurException = ParentException;
116 CurException; CurException = CurException->ParentException)
117 ++D;
118 return D;
119 }
120
121 void print(raw_ostream &OS, unsigned Depth = 0) const;
122 void dump() const;
123};
124
125raw_ostream &operator<<(raw_ostream &OS, const WebAssemblyException &WE);
126
127class WebAssemblyExceptionInfo {
128 // Mapping of basic blocks to the innermost exception they occur in
129 DenseMap<const MachineBasicBlock *, WebAssemblyException *> BBMap;
130 std::vector<std::unique_ptr<WebAssemblyException>> TopLevelExceptions;
131
132 void discoverAndMapException(WebAssemblyException *WE,
133 const MachineDominatorTree &MDT,
134 const MachineDominanceFrontier &MDF);
135 WebAssemblyException *getOutermostException(MachineBasicBlock *MBB) const;
136
137public:
138 WebAssemblyExceptionInfo() {}
139 ~WebAssemblyExceptionInfo() { releaseMemory(); }
140 WebAssemblyExceptionInfo(const WebAssemblyExceptionInfo &) = delete;
141 WebAssemblyExceptionInfo(WebAssemblyExceptionInfo &&) = default;
142 WebAssemblyExceptionInfo &
143 operator=(const WebAssemblyExceptionInfo &) = delete;
144
145 void releaseMemory();
146 void recalculate(MachineFunction &MF, MachineDominatorTree &MDT,
147 const MachineDominanceFrontier &MDF);
148
149 bool empty() const { return TopLevelExceptions.empty(); }
150
151 // Return the innermost exception that MBB lives in. If the block is not in an
152 // exception, null is returned.
153 WebAssemblyException *getExceptionFor(const MachineBasicBlock *MBB) const {
154 return BBMap.lookup(Val: MBB);
155 }
156
157 void changeExceptionFor(const MachineBasicBlock *MBB,
158 WebAssemblyException *WE) {
159 if (!WE) {
160 BBMap.erase(Val: MBB);
161 return;
162 }
163 BBMap[MBB] = WE;
164 }
165
166 void addTopLevelException(std::unique_ptr<WebAssemblyException> WE) {
167 assert(!WE->getParentException() && "Not a top level exception!");
168 TopLevelExceptions.push_back(x: std::move(WE));
169 }
170
171 void print(raw_ostream &OS, const Module *M) const;
172
173 bool invalidate(MachineFunction &MF, const PreservedAnalyses &PA,
174 MachineFunctionAnalysisManager::Invalidator &);
175};
176
177class WebAssemblyExceptionInfoWrapperPass : public MachineFunctionPass {
178 WebAssemblyExceptionInfo WasmExceptionInfo;
179
180public:
181 static char ID;
182 WebAssemblyExceptionInfoWrapperPass() : MachineFunctionPass(ID) {}
183
184 void getAnalysisUsage(AnalysisUsage &AU) const override;
185 bool runOnMachineFunction(MachineFunction &MF) override;
186 void print(raw_ostream &OS, const Module *M = nullptr) const override {
187 WasmExceptionInfo.print(OS, M);
188 }
189 void releaseMemory() override { WasmExceptionInfo.releaseMemory(); }
190
191 WebAssemblyExceptionInfo &getWEI() { return WasmExceptionInfo; }
192 const WebAssemblyExceptionInfo &getWEI() const { return WasmExceptionInfo; }
193};
194
195class WebAssemblyExceptionAnalysis
196 : public AnalysisInfoMixin<WebAssemblyExceptionAnalysis> {
197 friend AnalysisInfoMixin<WebAssemblyExceptionAnalysis>;
198 static AnalysisKey Key;
199
200public:
201 using Result = WebAssemblyExceptionInfo;
202
203 LLVM_ABI Result run(MachineFunction &MF,
204 MachineFunctionAnalysisManager &MFAM);
205};
206
207} // end namespace llvm
208
209#endif
210