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/MachineFunctionPass.h"
20
21namespace llvm {
22
23class MachineDominatorTree;
24class MachineDominanceFrontier;
25
26// WebAssembly instructions for exception handling are structured as follows:
27// try
28// instructions*
29// catch ----|
30// instructions* | -> A WebAssemblyException consists of this region
31// end ----|
32//
33// A WebAssemblyException object contains BBs that belong to a 'catch' part of
34// the try-catch-end structure to be created later. 'try' and 'end' markers
35// are not present at this stage and will be generated in CFGStackify pass.
36// Because CFGSort requires all the BBs within a catch part to be sorted
37// together as it does for loops, this pass calculates the nesting structure of
38// catch part of exceptions in a function.
39//
40// An exception catch part is defined as a BB with catch instruction and all
41// other BBs dominated by this BB.
42class WebAssemblyException {
43 MachineBasicBlock *EHPad = nullptr;
44
45 WebAssemblyException *ParentException = nullptr;
46 std::vector<std::unique_ptr<WebAssemblyException>> SubExceptions;
47 std::vector<MachineBasicBlock *> Blocks;
48 SmallPtrSet<MachineBasicBlock *, 8> BlockSet;
49
50public:
51 WebAssemblyException(MachineBasicBlock *EHPad) : EHPad(EHPad) {}
52 WebAssemblyException(const WebAssemblyException &) = delete;
53 const WebAssemblyException &operator=(const WebAssemblyException &) = delete;
54
55 MachineBasicBlock *getEHPad() const { return EHPad; }
56 MachineBasicBlock *getHeader() const { return EHPad; }
57 WebAssemblyException *getParentException() const { return ParentException; }
58 void setParentException(WebAssemblyException *WE) { ParentException = WE; }
59
60 bool contains(const WebAssemblyException *WE) const {
61 if (WE == this)
62 return true;
63 if (!WE)
64 return false;
65 return contains(WE: WE->getParentException());
66 }
67 bool contains(const MachineBasicBlock *MBB) const {
68 return BlockSet.count(Ptr: MBB);
69 }
70
71 void addToBlocksSet(MachineBasicBlock *MBB) { BlockSet.insert(Ptr: MBB); }
72 void removeFromBlocksSet(MachineBasicBlock *MBB) { BlockSet.erase(Ptr: MBB); }
73 void addToBlocksVector(MachineBasicBlock *MBB) { Blocks.push_back(x: MBB); }
74 void addBlock(MachineBasicBlock *MBB) {
75 Blocks.push_back(x: MBB);
76 BlockSet.insert(Ptr: MBB);
77 }
78 ArrayRef<MachineBasicBlock *> getBlocks() const { return Blocks; }
79 using block_iterator = typename ArrayRef<MachineBasicBlock *>::const_iterator;
80 block_iterator block_begin() const { return getBlocks().begin(); }
81 block_iterator block_end() const { return getBlocks().end(); }
82 inline iterator_range<block_iterator> blocks() const {
83 return make_range(x: block_begin(), y: block_end());
84 }
85 unsigned getNumBlocks() const { return Blocks.size(); }
86 std::vector<MachineBasicBlock *> &getBlocksVector() { return Blocks; }
87 SmallPtrSetImpl<MachineBasicBlock *> &getBlocksSet() { return BlockSet; }
88
89 const std::vector<std::unique_ptr<WebAssemblyException>> &
90 getSubExceptions() const {
91 return SubExceptions;
92 }
93 std::vector<std::unique_ptr<WebAssemblyException>> &getSubExceptions() {
94 return SubExceptions;
95 }
96 void addSubException(std::unique_ptr<WebAssemblyException> E) {
97 SubExceptions.push_back(x: std::move(E));
98 }
99 using iterator = typename decltype(SubExceptions)::const_iterator;
100 iterator begin() const { return SubExceptions.begin(); }
101 iterator end() const { return SubExceptions.end(); }
102
103 void reserveBlocks(unsigned Size) { Blocks.reserve(n: Size); }
104 void reverseBlock(unsigned From = 0) {
105 std::reverse(first: Blocks.begin() + From, last: Blocks.end());
106 }
107
108 // Return the nesting level. An outermost one has depth 1.
109 unsigned getExceptionDepth() const {
110 unsigned D = 1;
111 for (const WebAssemblyException *CurException = ParentException;
112 CurException; CurException = CurException->ParentException)
113 ++D;
114 return D;
115 }
116
117 void print(raw_ostream &OS, unsigned Depth = 0) const;
118 void dump() const;
119};
120
121raw_ostream &operator<<(raw_ostream &OS, const WebAssemblyException &WE);
122
123class WebAssemblyExceptionInfo final : public MachineFunctionPass {
124 // Mapping of basic blocks to the innermost exception they occur in
125 DenseMap<const MachineBasicBlock *, WebAssemblyException *> BBMap;
126 std::vector<std::unique_ptr<WebAssemblyException>> TopLevelExceptions;
127
128 void discoverAndMapException(WebAssemblyException *WE,
129 const MachineDominatorTree &MDT,
130 const MachineDominanceFrontier &MDF);
131 WebAssemblyException *getOutermostException(MachineBasicBlock *MBB) const;
132
133public:
134 static char ID;
135 WebAssemblyExceptionInfo() : MachineFunctionPass(ID) {
136 initializeWebAssemblyExceptionInfoPass(*PassRegistry::getPassRegistry());
137 }
138 ~WebAssemblyExceptionInfo() override { releaseMemory(); }
139 WebAssemblyExceptionInfo(const WebAssemblyExceptionInfo &) = delete;
140 WebAssemblyExceptionInfo &
141 operator=(const WebAssemblyExceptionInfo &) = delete;
142
143 bool runOnMachineFunction(MachineFunction &) override;
144 void releaseMemory() override;
145 void recalculate(MachineFunction &MF, MachineDominatorTree &MDT,
146 const MachineDominanceFrontier &MDF);
147 void getAnalysisUsage(AnalysisUsage &AU) const override;
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 = nullptr) const override;
172};
173
174} // end namespace llvm
175
176#endif
177