1 | //===- GCMetadata.h - Garbage collector metadata ----------------*- 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 | // This file declares the GCFunctionInfo and GCModuleInfo classes, which are |
10 | // used as a communication channel from the target code generator to the target |
11 | // garbage collectors. This interface allows code generators and garbage |
12 | // collectors to be developed independently. |
13 | // |
14 | // The GCFunctionInfo class logs the data necessary to build a type accurate |
15 | // stack map. The code generator outputs: |
16 | // |
17 | // - Safe points as specified by the GCStrategy's NeededSafePoints. |
18 | // - Stack offsets for GC roots, as specified by calls to llvm.gcroot |
19 | // |
20 | // As a refinement, liveness analysis calculates the set of live roots at each |
21 | // safe point. Liveness analysis is not presently performed by the code |
22 | // generator, so all roots are assumed live. |
23 | // |
24 | // GCModuleInfo simply collects GCFunctionInfo instances for each Function as |
25 | // they are compiled. This accretion is necessary for collectors which must emit |
26 | // a stack map for the compilation unit as a whole. Therefore, GCFunctionInfo |
27 | // outlives the MachineFunction from which it is derived and must not refer to |
28 | // any code generator data structures. |
29 | // |
30 | //===----------------------------------------------------------------------===// |
31 | |
32 | #ifndef LLVM_CODEGEN_GCMETADATA_H |
33 | #define LLVM_CODEGEN_GCMETADATA_H |
34 | |
35 | #include "llvm/ADT/DenseMap.h" |
36 | #include "llvm/ADT/SmallVector.h" |
37 | #include "llvm/ADT/StringMap.h" |
38 | #include "llvm/ADT/StringRef.h" |
39 | #include "llvm/IR/DebugLoc.h" |
40 | #include "llvm/IR/GCStrategy.h" |
41 | #include "llvm/IR/PassManager.h" |
42 | #include "llvm/Pass.h" |
43 | #include <algorithm> |
44 | #include <cstddef> |
45 | #include <cstdint> |
46 | #include <memory> |
47 | #include <vector> |
48 | |
49 | namespace llvm { |
50 | |
51 | class Constant; |
52 | class Function; |
53 | class MCSymbol; |
54 | |
55 | /// GCPoint - Metadata for a collector-safe point in machine code. |
56 | /// |
57 | struct GCPoint { |
58 | MCSymbol *Label; ///< A label. |
59 | DebugLoc Loc; |
60 | |
61 | GCPoint(MCSymbol *L, DebugLoc DL) |
62 | : Label(L), Loc(std::move(DL)) {} |
63 | }; |
64 | |
65 | /// GCRoot - Metadata for a pointer to an object managed by the garbage |
66 | /// collector. |
67 | struct GCRoot { |
68 | int Num; ///< Usually a frame index. |
69 | int StackOffset = -1; ///< Offset from the stack pointer. |
70 | const Constant *Metadata; ///< Metadata straight from the call |
71 | ///< to llvm.gcroot. |
72 | |
73 | GCRoot(int N, const Constant *MD) : Num(N), Metadata(MD) {} |
74 | }; |
75 | |
76 | /// Garbage collection metadata for a single function. Currently, this |
77 | /// information only applies to GCStrategies which use GCRoot. |
78 | class GCFunctionInfo { |
79 | public: |
80 | using iterator = std::vector<GCPoint>::iterator; |
81 | using roots_iterator = std::vector<GCRoot>::iterator; |
82 | using live_iterator = std::vector<GCRoot>::const_iterator; |
83 | |
84 | private: |
85 | const Function &F; |
86 | GCStrategy &S; |
87 | uint64_t FrameSize; |
88 | std::vector<GCRoot> Roots; |
89 | std::vector<GCPoint> SafePoints; |
90 | |
91 | // FIXME: Liveness. A 2D BitVector, perhaps? |
92 | // |
93 | // BitVector Liveness; |
94 | // |
95 | // bool islive(int point, int root) = |
96 | // Liveness[point * SafePoints.size() + root] |
97 | // |
98 | // The bit vector is the more compact representation where >3.2% of roots |
99 | // are live per safe point (1.5% on 64-bit hosts). |
100 | |
101 | public: |
102 | GCFunctionInfo(const Function &F, GCStrategy &S); |
103 | ~GCFunctionInfo(); |
104 | |
105 | /// Handle invalidation explicitly. |
106 | bool invalidate(Function &F, const PreservedAnalyses &PA, |
107 | FunctionAnalysisManager::Invalidator &Inv); |
108 | |
109 | /// getFunction - Return the function to which this metadata applies. |
110 | const Function &getFunction() const { return F; } |
111 | |
112 | /// getStrategy - Return the GC strategy for the function. |
113 | GCStrategy &getStrategy() { return S; } |
114 | |
115 | /// addStackRoot - Registers a root that lives on the stack. Num is the |
116 | /// stack object ID for the alloca (if the code generator is |
117 | // using MachineFrameInfo). |
118 | void addStackRoot(int Num, const Constant *Metadata) { |
119 | Roots.push_back(x: GCRoot(Num, Metadata)); |
120 | } |
121 | |
122 | /// removeStackRoot - Removes a root. |
123 | roots_iterator removeStackRoot(roots_iterator position) { |
124 | return Roots.erase(position: position); |
125 | } |
126 | |
127 | /// addSafePoint - Notes the existence of a safe point. Num is the ID of the |
128 | /// label just prior to the safe point (if the code generator is using |
129 | /// MachineModuleInfo). |
130 | void addSafePoint(MCSymbol *Label, const DebugLoc &DL) { |
131 | SafePoints.emplace_back(args&: Label, args: DL); |
132 | } |
133 | |
134 | /// getFrameSize/setFrameSize - Records the function's frame size. |
135 | uint64_t getFrameSize() const { return FrameSize; } |
136 | void setFrameSize(uint64_t S) { FrameSize = S; } |
137 | |
138 | /// begin/end - Iterators for safe points. |
139 | iterator begin() { return SafePoints.begin(); } |
140 | iterator end() { return SafePoints.end(); } |
141 | size_t size() const { return SafePoints.size(); } |
142 | |
143 | /// roots_begin/roots_end - Iterators for all roots in the function. |
144 | roots_iterator roots_begin() { return Roots.begin(); } |
145 | roots_iterator roots_end() { return Roots.end(); } |
146 | size_t roots_size() const { return Roots.size(); } |
147 | |
148 | /// live_begin/live_end - Iterators for live roots at a given safe point. |
149 | live_iterator live_begin(const iterator &p) { return roots_begin(); } |
150 | live_iterator live_end(const iterator &p) { return roots_end(); } |
151 | size_t live_size(const iterator &p) const { return roots_size(); } |
152 | }; |
153 | |
154 | struct GCStrategyMap { |
155 | StringMap<std::unique_ptr<GCStrategy>> StrategyMap; |
156 | |
157 | GCStrategyMap() = default; |
158 | GCStrategyMap(GCStrategyMap &&) = default; |
159 | |
160 | /// Handle invalidation explicitly. |
161 | bool invalidate(Module &M, const PreservedAnalyses &PA, |
162 | ModuleAnalysisManager::Invalidator &Inv); |
163 | }; |
164 | |
165 | /// An analysis pass which caches information about the entire Module. |
166 | /// Records a cache of the 'active' gc strategy objects for the current Module. |
167 | class CollectorMetadataAnalysis |
168 | : public AnalysisInfoMixin<CollectorMetadataAnalysis> { |
169 | friend struct AnalysisInfoMixin<CollectorMetadataAnalysis>; |
170 | static AnalysisKey Key; |
171 | |
172 | public: |
173 | using Result = GCStrategyMap; |
174 | Result run(Module &M, ModuleAnalysisManager &MAM); |
175 | }; |
176 | |
177 | /// An analysis pass which caches information about the Function. |
178 | /// Records the function level information used by GCRoots. |
179 | /// This pass depends on `CollectorMetadataAnalysis`. |
180 | class GCFunctionAnalysis : public AnalysisInfoMixin<GCFunctionAnalysis> { |
181 | friend struct AnalysisInfoMixin<GCFunctionAnalysis>; |
182 | static AnalysisKey Key; |
183 | |
184 | public: |
185 | using Result = GCFunctionInfo; |
186 | Result run(Function &F, FunctionAnalysisManager &FAM); |
187 | }; |
188 | |
189 | /// LowerIntrinsics - This pass rewrites calls to the llvm.gcread or |
190 | /// llvm.gcwrite intrinsics, replacing them with simple loads and stores as |
191 | /// directed by the GCStrategy. It also performs automatic root initialization |
192 | /// and custom intrinsic lowering. |
193 | /// |
194 | /// This pass requires `CollectorMetadataAnalysis`. |
195 | class GCLoweringPass : public PassInfoMixin<GCLoweringPass> { |
196 | public: |
197 | PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM); |
198 | }; |
199 | |
200 | /// An analysis pass which caches information about the entire Module. |
201 | /// Records both the function level information used by GCRoots and a |
202 | /// cache of the 'active' gc strategy objects for the current Module. |
203 | class GCModuleInfo : public ImmutablePass { |
204 | /// An owning list of all GCStrategies which have been created |
205 | SmallVector<std::unique_ptr<GCStrategy>, 1> GCStrategyList; |
206 | /// A helper map to speedup lookups into the above list |
207 | StringMap<GCStrategy*> GCStrategyMap; |
208 | |
209 | public: |
210 | /// Lookup the GCStrategy object associated with the given gc name. |
211 | /// Objects are owned internally; No caller should attempt to delete the |
212 | /// returned objects. |
213 | GCStrategy *getGCStrategy(const StringRef Name); |
214 | |
215 | /// List of per function info objects. In theory, Each of these |
216 | /// may be associated with a different GC. |
217 | using FuncInfoVec = std::vector<std::unique_ptr<GCFunctionInfo>>; |
218 | |
219 | FuncInfoVec::iterator funcinfo_begin() { return Functions.begin(); } |
220 | FuncInfoVec::iterator funcinfo_end() { return Functions.end(); } |
221 | |
222 | private: |
223 | /// Owning list of all GCFunctionInfos associated with this Module |
224 | FuncInfoVec Functions; |
225 | |
226 | /// Non-owning map to bypass linear search when finding the GCFunctionInfo |
227 | /// associated with a particular Function. |
228 | using finfo_map_type = DenseMap<const Function *, GCFunctionInfo *>; |
229 | finfo_map_type FInfoMap; |
230 | |
231 | public: |
232 | using iterator = SmallVector<std::unique_ptr<GCStrategy>, 1>::const_iterator; |
233 | |
234 | static char ID; |
235 | |
236 | GCModuleInfo(); |
237 | |
238 | /// clear - Resets the pass. Any pass, which uses GCModuleInfo, should |
239 | /// call it in doFinalization(). |
240 | /// |
241 | void clear(); |
242 | |
243 | /// begin/end - Iterators for used strategies. |
244 | /// |
245 | iterator begin() const { return GCStrategyList.begin(); } |
246 | iterator end() const { return GCStrategyList.end(); } |
247 | |
248 | /// get - Look up function metadata. This is currently assumed |
249 | /// have the side effect of initializing the associated GCStrategy. That |
250 | /// will soon change. |
251 | GCFunctionInfo &getFunctionInfo(const Function &F); |
252 | }; |
253 | |
254 | } // end namespace llvm |
255 | |
256 | #endif // LLVM_CODEGEN_GCMETADATA_H |
257 | |