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/MapVector.h" 37 #include "llvm/ADT/SmallVector.h" 38 #include "llvm/ADT/StringMap.h" 39 #include "llvm/ADT/StringRef.h" 40 #include "llvm/IR/DebugLoc.h" 41 #include "llvm/IR/GCStrategy.h" 42 #include "llvm/IR/PassManager.h" 43 #include "llvm/Pass.h" 44 #include "llvm/Support/Compiler.h" 45 #include <algorithm> 46 #include <cstddef> 47 #include <cstdint> 48 #include <memory> 49 #include <vector> 50 51 namespace llvm { 52 53 class Constant; 54 class Function; 55 class MCSymbol; 56 57 /// GCPoint - Metadata for a collector-safe point in machine code. 58 /// 59 struct GCPoint { 60 MCSymbol *Label; ///< A label. 61 DebugLoc Loc; 62 GCPointGCPoint63 GCPoint(MCSymbol *L, DebugLoc DL) 64 : Label(L), Loc(std::move(DL)) {} 65 }; 66 67 /// GCRoot - Metadata for a pointer to an object managed by the garbage 68 /// collector. 69 struct GCRoot { 70 int Num; ///< Usually a frame index. 71 int StackOffset = -1; ///< Offset from the stack pointer. 72 const Constant *Metadata; ///< Metadata straight from the call 73 ///< to llvm.gcroot. 74 GCRootGCRoot75 GCRoot(int N, const Constant *MD) : Num(N), Metadata(MD) {} 76 }; 77 78 /// Garbage collection metadata for a single function. Currently, this 79 /// information only applies to GCStrategies which use GCRoot. 80 class GCFunctionInfo { 81 public: 82 using iterator = std::vector<GCPoint>::iterator; 83 using roots_iterator = std::vector<GCRoot>::iterator; 84 using live_iterator = std::vector<GCRoot>::const_iterator; 85 86 private: 87 const Function &F; 88 GCStrategy &S; 89 uint64_t FrameSize; 90 std::vector<GCRoot> Roots; 91 std::vector<GCPoint> SafePoints; 92 93 // FIXME: Liveness. A 2D BitVector, perhaps? 94 // 95 // BitVector Liveness; 96 // 97 // bool islive(int point, int root) = 98 // Liveness[point * SafePoints.size() + root] 99 // 100 // The bit vector is the more compact representation where >3.2% of roots 101 // are live per safe point (1.5% on 64-bit hosts). 102 103 public: 104 GCFunctionInfo(const Function &F, GCStrategy &S); 105 ~GCFunctionInfo(); 106 107 /// Handle invalidation explicitly. 108 bool invalidate(Function &F, const PreservedAnalyses &PA, 109 FunctionAnalysisManager::Invalidator &Inv); 110 111 /// getFunction - Return the function to which this metadata applies. getFunction()112 const Function &getFunction() const { return F; } 113 114 /// getStrategy - Return the GC strategy for the function. getStrategy()115 GCStrategy &getStrategy() { return S; } 116 117 /// addStackRoot - Registers a root that lives on the stack. Num is the 118 /// stack object ID for the alloca (if the code generator is 119 // using MachineFrameInfo). addStackRoot(int Num,const Constant * Metadata)120 void addStackRoot(int Num, const Constant *Metadata) { 121 Roots.push_back(GCRoot(Num, Metadata)); 122 } 123 124 /// removeStackRoot - Removes a root. removeStackRoot(roots_iterator position)125 roots_iterator removeStackRoot(roots_iterator position) { 126 return Roots.erase(position); 127 } 128 129 /// addSafePoint - Notes the existence of a safe point. Num is the ID of the 130 /// label just prior to the safe point (if the code generator is using 131 /// MachineModuleInfo). addSafePoint(MCSymbol * Label,const DebugLoc & DL)132 void addSafePoint(MCSymbol *Label, const DebugLoc &DL) { 133 SafePoints.emplace_back(Label, DL); 134 } 135 136 /// getFrameSize/setFrameSize - Records the function's frame size. getFrameSize()137 uint64_t getFrameSize() const { return FrameSize; } setFrameSize(uint64_t S)138 void setFrameSize(uint64_t S) { FrameSize = S; } 139 140 /// begin/end - Iterators for safe points. begin()141 iterator begin() { return SafePoints.begin(); } end()142 iterator end() { return SafePoints.end(); } size()143 size_t size() const { return SafePoints.size(); } 144 145 /// roots_begin/roots_end - Iterators for all roots in the function. roots_begin()146 roots_iterator roots_begin() { return Roots.begin(); } roots_end()147 roots_iterator roots_end() { return Roots.end(); } roots_size()148 size_t roots_size() const { return Roots.size(); } 149 150 /// live_begin/live_end - Iterators for live roots at a given safe point. live_begin(const iterator & p)151 live_iterator live_begin(const iterator &p) { return roots_begin(); } live_end(const iterator & p)152 live_iterator live_end(const iterator &p) { return roots_end(); } live_size(const iterator & p)153 size_t live_size(const iterator &p) const { return roots_size(); } 154 }; 155 156 class GCStrategyMap { 157 using MapT = 158 MapVector<StringRef, std::unique_ptr<GCStrategy>, StringMap<unsigned>>; 159 MapT Strategies; 160 161 public: 162 GCStrategyMap() = default; 163 GCStrategyMap(GCStrategyMap &&) = default; 164 165 /// Handle invalidation explicitly. 166 bool invalidate(Module &M, const PreservedAnalyses &PA, 167 ModuleAnalysisManager::Invalidator &Inv); 168 169 using iterator = MapT::iterator; 170 using const_iterator = MapT::const_iterator; 171 using reverse_iterator = MapT::reverse_iterator; 172 using const_reverse_iterator = MapT::const_reverse_iterator; 173 begin()174 iterator begin() { return Strategies.begin(); } begin()175 const_iterator begin() const { return Strategies.begin(); } end()176 iterator end() { return Strategies.end(); } end()177 const_iterator end() const { return Strategies.end(); } 178 rbegin()179 reverse_iterator rbegin() { return Strategies.rbegin(); } rbegin()180 const_reverse_iterator rbegin() const { return Strategies.rbegin(); } rend()181 reverse_iterator rend() { return Strategies.rend(); } rend()182 const_reverse_iterator rend() const { return Strategies.rend(); } 183 empty()184 bool empty() const { return Strategies.empty(); } 185 186 const GCStrategy &operator[](StringRef GCName) const { 187 auto I = Strategies.find(GCName); 188 assert(I != Strategies.end() && "Required strategy doesn't exist!"); 189 return *I->second; 190 } 191 try_emplace(StringRef GCName)192 std::pair<iterator, bool> try_emplace(StringRef GCName) { 193 return Strategies.try_emplace(GCName); 194 } 195 contains(StringRef GCName)196 bool contains(StringRef GCName) const { return Strategies.contains(GCName); } 197 }; 198 199 /// An analysis pass which caches information about the entire Module. 200 /// Records a cache of the 'active' gc strategy objects for the current Module. 201 class CollectorMetadataAnalysis 202 : public AnalysisInfoMixin<CollectorMetadataAnalysis> { 203 friend struct AnalysisInfoMixin<CollectorMetadataAnalysis>; 204 LLVM_ABI static AnalysisKey Key; 205 206 public: 207 using Result = GCStrategyMap; 208 Result run(Module &M, ModuleAnalysisManager &MAM); 209 }; 210 211 /// An analysis pass which caches information about the Function. 212 /// Records the function level information used by GCRoots. 213 /// This pass depends on `CollectorMetadataAnalysis`. 214 class GCFunctionAnalysis : public AnalysisInfoMixin<GCFunctionAnalysis> { 215 friend struct AnalysisInfoMixin<GCFunctionAnalysis>; 216 LLVM_ABI static AnalysisKey Key; 217 218 public: 219 using Result = GCFunctionInfo; 220 Result run(Function &F, FunctionAnalysisManager &FAM); 221 }; 222 223 /// LowerIntrinsics - This pass rewrites calls to the llvm.gcread or 224 /// llvm.gcwrite intrinsics, replacing them with simple loads and stores as 225 /// directed by the GCStrategy. It also performs automatic root initialization 226 /// and custom intrinsic lowering. 227 /// 228 /// This pass requires `CollectorMetadataAnalysis`. 229 class GCLoweringPass : public PassInfoMixin<GCLoweringPass> { 230 public: 231 PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM); 232 }; 233 234 /// An analysis pass which caches information about the entire Module. 235 /// Records both the function level information used by GCRoots and a 236 /// cache of the 'active' gc strategy objects for the current Module. 237 class GCModuleInfo : public ImmutablePass { 238 /// An owning list of all GCStrategies which have been created 239 SmallVector<std::unique_ptr<GCStrategy>, 1> GCStrategyList; 240 /// A helper map to speedup lookups into the above list 241 StringMap<GCStrategy*> GCStrategyMap; 242 243 public: 244 /// Lookup the GCStrategy object associated with the given gc name. 245 /// Objects are owned internally; No caller should attempt to delete the 246 /// returned objects. 247 GCStrategy *getGCStrategy(const StringRef Name); 248 249 /// List of per function info objects. In theory, Each of these 250 /// may be associated with a different GC. 251 using FuncInfoVec = std::vector<std::unique_ptr<GCFunctionInfo>>; 252 253 FuncInfoVec::iterator funcinfo_begin() { return Functions.begin(); } 254 FuncInfoVec::iterator funcinfo_end() { return Functions.end(); } 255 256 private: 257 /// Owning list of all GCFunctionInfos associated with this Module 258 FuncInfoVec Functions; 259 260 /// Non-owning map to bypass linear search when finding the GCFunctionInfo 261 /// associated with a particular Function. 262 using finfo_map_type = DenseMap<const Function *, GCFunctionInfo *>; 263 finfo_map_type FInfoMap; 264 265 public: 266 using iterator = SmallVector<std::unique_ptr<GCStrategy>, 1>::const_iterator; 267 268 static char ID; 269 270 GCModuleInfo(); 271 272 /// clear - Resets the pass. Any pass, which uses GCModuleInfo, should 273 /// call it in doFinalization(). 274 /// 275 void clear(); 276 277 /// begin/end - Iterators for used strategies. 278 /// 279 iterator begin() const { return GCStrategyList.begin(); } 280 iterator end() const { return GCStrategyList.end(); } 281 282 /// get - Look up function metadata. This is currently assumed 283 /// have the side effect of initializing the associated GCStrategy. That 284 /// will soon change. 285 GCFunctionInfo &getFunctionInfo(const Function &F); 286 }; 287 288 } // end namespace llvm 289 290 #endif // LLVM_CODEGEN_GCMETADATA_H 291