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/SetVector.h"
19 #include "llvm/CodeGen/MachineFunctionPass.h"
20 
21 namespace llvm {
22 
23 class MachineDominatorTree;
24 class 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.
42 class 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<const MachineBasicBlock *, 8> BlockSet;
49 
50 public:
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->getParentException());
66   }
67   bool contains(const MachineBasicBlock *MBB) const {
68     return BlockSet.count(MBB);
69   }
70 
71   void addBlock(MachineBasicBlock *MBB) {
72     Blocks.push_back(MBB);
73     BlockSet.insert(MBB);
74   }
75   ArrayRef<MachineBasicBlock *> getBlocks() const { return Blocks; }
76   using block_iterator = typename ArrayRef<MachineBasicBlock *>::const_iterator;
77   block_iterator block_begin() const { return getBlocks().begin(); }
78   block_iterator block_end() const { return getBlocks().end(); }
79   inline iterator_range<block_iterator> blocks() const {
80     return make_range(block_begin(), block_end());
81   }
82   unsigned getNumBlocks() const { return Blocks.size(); }
83   std::vector<MachineBasicBlock *> &getBlocksVector() { return Blocks; }
84 
85   const std::vector<std::unique_ptr<WebAssemblyException>> &getSubExceptions() const {
86     return SubExceptions;
87   }
88   std::vector<std::unique_ptr<WebAssemblyException>> &getSubExceptions() {
89     return SubExceptions;
90   }
91   void addSubException(std::unique_ptr<WebAssemblyException> E) {
92     SubExceptions.push_back(std::move(E));
93   }
94   using iterator = typename decltype(SubExceptions)::const_iterator;
95   iterator begin() const { return SubExceptions.begin(); }
96   iterator end() const { return SubExceptions.end(); }
97 
98   void reserveBlocks(unsigned Size) { Blocks.reserve(Size); }
99   void reverseBlock(unsigned From = 0) {
100     std::reverse(Blocks.begin() + From, Blocks.end());
101   }
102 
103   // Return the nesting level. An outermost one has depth 1.
104   unsigned getExceptionDepth() const {
105     unsigned D = 1;
106     for (const WebAssemblyException *CurException = ParentException;
107          CurException; CurException = CurException->ParentException)
108       ++D;
109     return D;
110   }
111 
112   void print(raw_ostream &OS, unsigned Depth = 0) const;
113   void dump() const;
114 };
115 
116 raw_ostream &operator<<(raw_ostream &OS, const WebAssemblyException &WE);
117 
118 class WebAssemblyExceptionInfo final : public MachineFunctionPass {
119   // Mapping of basic blocks to the innermost exception they occur in
120   DenseMap<const MachineBasicBlock *, WebAssemblyException *> BBMap;
121   std::vector<std::unique_ptr<WebAssemblyException>> TopLevelExceptions;
122 
123   void discoverAndMapException(WebAssemblyException *WE,
124                                const MachineDominatorTree &MDT,
125                                const MachineDominanceFrontier &MDF);
126   WebAssemblyException *getOutermostException(MachineBasicBlock *MBB) const;
127 
128 public:
129   static char ID;
130   WebAssemblyExceptionInfo() : MachineFunctionPass(ID) {
131     initializeWebAssemblyExceptionInfoPass(*PassRegistry::getPassRegistry());
132   }
133   ~WebAssemblyExceptionInfo() override { releaseMemory(); }
134   WebAssemblyExceptionInfo(const WebAssemblyExceptionInfo &) = delete;
135   WebAssemblyExceptionInfo &
136   operator=(const WebAssemblyExceptionInfo &) = delete;
137 
138   bool runOnMachineFunction(MachineFunction &) override;
139   void releaseMemory() override;
140   void recalculate(MachineDominatorTree &MDT,
141                    const MachineDominanceFrontier &MDF);
142   void getAnalysisUsage(AnalysisUsage &AU) const override;
143 
144   bool empty() const { return TopLevelExceptions.empty(); }
145 
146   // Return the innermost exception that MBB lives in. If the block is not in an
147   // exception, null is returned.
148   WebAssemblyException *getExceptionFor(const MachineBasicBlock *MBB) const {
149     return BBMap.lookup(MBB);
150   }
151 
152   void changeExceptionFor(MachineBasicBlock *MBB, WebAssemblyException *WE) {
153     if (!WE) {
154       BBMap.erase(MBB);
155       return;
156     }
157     BBMap[MBB] = WE;
158   }
159 
160   void addTopLevelException(std::unique_ptr<WebAssemblyException> WE) {
161     assert(!WE->getParentException() && "Not a top level exception!");
162     TopLevelExceptions.push_back(std::move(WE));
163   }
164 
165   void print(raw_ostream &OS, const Module *M = nullptr) const override;
166 };
167 
168 } // end namespace llvm
169 
170 #endif
171