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