10b57cec5SDimitry Andric //===- GCMetadata.h - Garbage collector metadata ----------------*- C++ -*-===// 20b57cec5SDimitry Andric // 30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 60b57cec5SDimitry Andric // 70b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 80b57cec5SDimitry Andric // 90b57cec5SDimitry Andric // This file declares the GCFunctionInfo and GCModuleInfo classes, which are 100b57cec5SDimitry Andric // used as a communication channel from the target code generator to the target 110b57cec5SDimitry Andric // garbage collectors. This interface allows code generators and garbage 120b57cec5SDimitry Andric // collectors to be developed independently. 130b57cec5SDimitry Andric // 140b57cec5SDimitry Andric // The GCFunctionInfo class logs the data necessary to build a type accurate 150b57cec5SDimitry Andric // stack map. The code generator outputs: 160b57cec5SDimitry Andric // 170b57cec5SDimitry Andric // - Safe points as specified by the GCStrategy's NeededSafePoints. 180b57cec5SDimitry Andric // - Stack offsets for GC roots, as specified by calls to llvm.gcroot 190b57cec5SDimitry Andric // 200b57cec5SDimitry Andric // As a refinement, liveness analysis calculates the set of live roots at each 210b57cec5SDimitry Andric // safe point. Liveness analysis is not presently performed by the code 220b57cec5SDimitry Andric // generator, so all roots are assumed live. 230b57cec5SDimitry Andric // 240b57cec5SDimitry Andric // GCModuleInfo simply collects GCFunctionInfo instances for each Function as 250b57cec5SDimitry Andric // they are compiled. This accretion is necessary for collectors which must emit 260b57cec5SDimitry Andric // a stack map for the compilation unit as a whole. Therefore, GCFunctionInfo 270b57cec5SDimitry Andric // outlives the MachineFunction from which it is derived and must not refer to 280b57cec5SDimitry Andric // any code generator data structures. 290b57cec5SDimitry Andric // 300b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 310b57cec5SDimitry Andric 320b57cec5SDimitry Andric #ifndef LLVM_CODEGEN_GCMETADATA_H 330b57cec5SDimitry Andric #define LLVM_CODEGEN_GCMETADATA_H 340b57cec5SDimitry Andric 350b57cec5SDimitry Andric #include "llvm/ADT/DenseMap.h" 360b57cec5SDimitry Andric #include "llvm/ADT/SmallVector.h" 370b57cec5SDimitry Andric #include "llvm/ADT/StringMap.h" 380b57cec5SDimitry Andric #include "llvm/ADT/StringRef.h" 390b57cec5SDimitry Andric #include "llvm/IR/DebugLoc.h" 40fe6060f1SDimitry Andric #include "llvm/IR/GCStrategy.h" 415f757f3fSDimitry Andric #include "llvm/IR/PassManager.h" 420b57cec5SDimitry Andric #include "llvm/Pass.h" 430b57cec5SDimitry Andric #include <algorithm> 440b57cec5SDimitry Andric #include <cstddef> 450b57cec5SDimitry Andric #include <cstdint> 460b57cec5SDimitry Andric #include <memory> 470b57cec5SDimitry Andric #include <vector> 480b57cec5SDimitry Andric 490b57cec5SDimitry Andric namespace llvm { 500b57cec5SDimitry Andric 510b57cec5SDimitry Andric class Constant; 520b57cec5SDimitry Andric class Function; 530b57cec5SDimitry Andric class MCSymbol; 540b57cec5SDimitry Andric 550b57cec5SDimitry Andric /// GCPoint - Metadata for a collector-safe point in machine code. 560b57cec5SDimitry Andric /// 570b57cec5SDimitry Andric struct GCPoint { 580b57cec5SDimitry Andric MCSymbol *Label; ///< A label. 590b57cec5SDimitry Andric DebugLoc Loc; 600b57cec5SDimitry Andric GCPointGCPoint610b57cec5SDimitry Andric GCPoint(MCSymbol *L, DebugLoc DL) 620b57cec5SDimitry Andric : Label(L), Loc(std::move(DL)) {} 630b57cec5SDimitry Andric }; 640b57cec5SDimitry Andric 650b57cec5SDimitry Andric /// GCRoot - Metadata for a pointer to an object managed by the garbage 660b57cec5SDimitry Andric /// collector. 670b57cec5SDimitry Andric struct GCRoot { 680b57cec5SDimitry Andric int Num; ///< Usually a frame index. 690b57cec5SDimitry Andric int StackOffset = -1; ///< Offset from the stack pointer. 700b57cec5SDimitry Andric const Constant *Metadata; ///< Metadata straight from the call 710b57cec5SDimitry Andric ///< to llvm.gcroot. 720b57cec5SDimitry Andric GCRootGCRoot730b57cec5SDimitry Andric GCRoot(int N, const Constant *MD) : Num(N), Metadata(MD) {} 740b57cec5SDimitry Andric }; 750b57cec5SDimitry Andric 760b57cec5SDimitry Andric /// Garbage collection metadata for a single function. Currently, this 770b57cec5SDimitry Andric /// information only applies to GCStrategies which use GCRoot. 780b57cec5SDimitry Andric class GCFunctionInfo { 790b57cec5SDimitry Andric public: 800b57cec5SDimitry Andric using iterator = std::vector<GCPoint>::iterator; 810b57cec5SDimitry Andric using roots_iterator = std::vector<GCRoot>::iterator; 820b57cec5SDimitry Andric using live_iterator = std::vector<GCRoot>::const_iterator; 830b57cec5SDimitry Andric 840b57cec5SDimitry Andric private: 850b57cec5SDimitry Andric const Function &F; 860b57cec5SDimitry Andric GCStrategy &S; 870b57cec5SDimitry Andric uint64_t FrameSize; 880b57cec5SDimitry Andric std::vector<GCRoot> Roots; 890b57cec5SDimitry Andric std::vector<GCPoint> SafePoints; 900b57cec5SDimitry Andric 910b57cec5SDimitry Andric // FIXME: Liveness. A 2D BitVector, perhaps? 920b57cec5SDimitry Andric // 930b57cec5SDimitry Andric // BitVector Liveness; 940b57cec5SDimitry Andric // 950b57cec5SDimitry Andric // bool islive(int point, int root) = 960b57cec5SDimitry Andric // Liveness[point * SafePoints.size() + root] 970b57cec5SDimitry Andric // 980b57cec5SDimitry Andric // The bit vector is the more compact representation where >3.2% of roots 990b57cec5SDimitry Andric // are live per safe point (1.5% on 64-bit hosts). 1000b57cec5SDimitry Andric 1010b57cec5SDimitry Andric public: 1020b57cec5SDimitry Andric GCFunctionInfo(const Function &F, GCStrategy &S); 1030b57cec5SDimitry Andric ~GCFunctionInfo(); 1040b57cec5SDimitry Andric 1055f757f3fSDimitry Andric /// Handle invalidation explicitly. 1065f757f3fSDimitry Andric bool invalidate(Function &F, const PreservedAnalyses &PA, 1075f757f3fSDimitry Andric FunctionAnalysisManager::Invalidator &Inv); 1085f757f3fSDimitry Andric 1090b57cec5SDimitry Andric /// getFunction - Return the function to which this metadata applies. getFunction()1100b57cec5SDimitry Andric const Function &getFunction() const { return F; } 1110b57cec5SDimitry Andric 1120b57cec5SDimitry Andric /// getStrategy - Return the GC strategy for the function. getStrategy()1130b57cec5SDimitry Andric GCStrategy &getStrategy() { return S; } 1140b57cec5SDimitry Andric 1150b57cec5SDimitry Andric /// addStackRoot - Registers a root that lives on the stack. Num is the 1160b57cec5SDimitry Andric /// stack object ID for the alloca (if the code generator is 1170b57cec5SDimitry Andric // using MachineFrameInfo). addStackRoot(int Num,const Constant * Metadata)1180b57cec5SDimitry Andric void addStackRoot(int Num, const Constant *Metadata) { 1190b57cec5SDimitry Andric Roots.push_back(GCRoot(Num, Metadata)); 1200b57cec5SDimitry Andric } 1210b57cec5SDimitry Andric 1220b57cec5SDimitry Andric /// removeStackRoot - Removes a root. removeStackRoot(roots_iterator position)1230b57cec5SDimitry Andric roots_iterator removeStackRoot(roots_iterator position) { 1240b57cec5SDimitry Andric return Roots.erase(position); 1250b57cec5SDimitry Andric } 1260b57cec5SDimitry Andric 1270b57cec5SDimitry Andric /// addSafePoint - Notes the existence of a safe point. Num is the ID of the 1280b57cec5SDimitry Andric /// label just prior to the safe point (if the code generator is using 1290b57cec5SDimitry Andric /// MachineModuleInfo). addSafePoint(MCSymbol * Label,const DebugLoc & DL)1300b57cec5SDimitry Andric void addSafePoint(MCSymbol *Label, const DebugLoc &DL) { 1310b57cec5SDimitry Andric SafePoints.emplace_back(Label, DL); 1320b57cec5SDimitry Andric } 1330b57cec5SDimitry Andric 1340b57cec5SDimitry Andric /// getFrameSize/setFrameSize - Records the function's frame size. getFrameSize()1350b57cec5SDimitry Andric uint64_t getFrameSize() const { return FrameSize; } setFrameSize(uint64_t S)1360b57cec5SDimitry Andric void setFrameSize(uint64_t S) { FrameSize = S; } 1370b57cec5SDimitry Andric 1380b57cec5SDimitry Andric /// begin/end - Iterators for safe points. begin()1390b57cec5SDimitry Andric iterator begin() { return SafePoints.begin(); } end()1400b57cec5SDimitry Andric iterator end() { return SafePoints.end(); } size()1410b57cec5SDimitry Andric size_t size() const { return SafePoints.size(); } 1420b57cec5SDimitry Andric 1430b57cec5SDimitry Andric /// roots_begin/roots_end - Iterators for all roots in the function. roots_begin()1440b57cec5SDimitry Andric roots_iterator roots_begin() { return Roots.begin(); } roots_end()1450b57cec5SDimitry Andric roots_iterator roots_end() { return Roots.end(); } roots_size()1460b57cec5SDimitry Andric size_t roots_size() const { return Roots.size(); } 1470b57cec5SDimitry Andric 1480b57cec5SDimitry Andric /// live_begin/live_end - Iterators for live roots at a given safe point. live_begin(const iterator & p)1490b57cec5SDimitry Andric live_iterator live_begin(const iterator &p) { return roots_begin(); } live_end(const iterator & p)1500b57cec5SDimitry Andric live_iterator live_end(const iterator &p) { return roots_end(); } live_size(const iterator & p)1510b57cec5SDimitry Andric size_t live_size(const iterator &p) const { return roots_size(); } 1520b57cec5SDimitry Andric }; 1530b57cec5SDimitry Andric 1545f757f3fSDimitry Andric struct GCStrategyMap { 1555f757f3fSDimitry Andric StringMap<std::unique_ptr<GCStrategy>> StrategyMap; 1565f757f3fSDimitry Andric 1575f757f3fSDimitry Andric GCStrategyMap() = default; 1585f757f3fSDimitry Andric GCStrategyMap(GCStrategyMap &&) = default; 1595f757f3fSDimitry Andric 1605f757f3fSDimitry Andric /// Handle invalidation explicitly. 1615f757f3fSDimitry Andric bool invalidate(Module &M, const PreservedAnalyses &PA, 1625f757f3fSDimitry Andric ModuleAnalysisManager::Invalidator &Inv); 1635f757f3fSDimitry Andric }; 1645f757f3fSDimitry Andric 1655f757f3fSDimitry Andric /// An analysis pass which caches information about the entire Module. 1665f757f3fSDimitry Andric /// Records a cache of the 'active' gc strategy objects for the current Module. 1675f757f3fSDimitry Andric class CollectorMetadataAnalysis 1685f757f3fSDimitry Andric : public AnalysisInfoMixin<CollectorMetadataAnalysis> { 1695f757f3fSDimitry Andric friend struct AnalysisInfoMixin<CollectorMetadataAnalysis>; 1705f757f3fSDimitry Andric static AnalysisKey Key; 1715f757f3fSDimitry Andric 1725f757f3fSDimitry Andric public: 1735f757f3fSDimitry Andric using Result = GCStrategyMap; 1745f757f3fSDimitry Andric Result run(Module &M, ModuleAnalysisManager &MAM); 1755f757f3fSDimitry Andric }; 1765f757f3fSDimitry Andric 1775f757f3fSDimitry Andric /// An analysis pass which caches information about the Function. 1785f757f3fSDimitry Andric /// Records the function level information used by GCRoots. 1795f757f3fSDimitry Andric /// This pass depends on `CollectorMetadataAnalysis`. 1805f757f3fSDimitry Andric class GCFunctionAnalysis : public AnalysisInfoMixin<GCFunctionAnalysis> { 1815f757f3fSDimitry Andric friend struct AnalysisInfoMixin<GCFunctionAnalysis>; 1825f757f3fSDimitry Andric static AnalysisKey Key; 1835f757f3fSDimitry Andric 1845f757f3fSDimitry Andric public: 1855f757f3fSDimitry Andric using Result = GCFunctionInfo; 1865f757f3fSDimitry Andric Result run(Function &F, FunctionAnalysisManager &FAM); 1875f757f3fSDimitry Andric }; 1885f757f3fSDimitry Andric 1891db9f3b2SDimitry Andric /// LowerIntrinsics - This pass rewrites calls to the llvm.gcread or 1901db9f3b2SDimitry Andric /// llvm.gcwrite intrinsics, replacing them with simple loads and stores as 1911db9f3b2SDimitry Andric /// directed by the GCStrategy. It also performs automatic root initialization 1921db9f3b2SDimitry Andric /// and custom intrinsic lowering. 1931db9f3b2SDimitry Andric /// 1941db9f3b2SDimitry Andric /// This pass requires `CollectorMetadataAnalysis`. 1951db9f3b2SDimitry Andric class GCLoweringPass : public PassInfoMixin<GCLoweringPass> { 1961db9f3b2SDimitry Andric public: 1971db9f3b2SDimitry Andric PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM); 1981db9f3b2SDimitry Andric }; 1991db9f3b2SDimitry Andric 2000b57cec5SDimitry Andric /// An analysis pass which caches information about the entire Module. 2010b57cec5SDimitry Andric /// Records both the function level information used by GCRoots and a 2020b57cec5SDimitry Andric /// cache of the 'active' gc strategy objects for the current Module. 2030b57cec5SDimitry Andric class GCModuleInfo : public ImmutablePass { 2040b57cec5SDimitry Andric /// An owning list of all GCStrategies which have been created 2050b57cec5SDimitry Andric SmallVector<std::unique_ptr<GCStrategy>, 1> GCStrategyList; 2060b57cec5SDimitry Andric /// A helper map to speedup lookups into the above list 2070b57cec5SDimitry Andric StringMap<GCStrategy*> GCStrategyMap; 2080b57cec5SDimitry Andric 2090b57cec5SDimitry Andric public: 2100b57cec5SDimitry Andric /// Lookup the GCStrategy object associated with the given gc name. 2110b57cec5SDimitry Andric /// Objects are owned internally; No caller should attempt to delete the 2120b57cec5SDimitry Andric /// returned objects. 2130b57cec5SDimitry Andric GCStrategy *getGCStrategy(const StringRef Name); 2140b57cec5SDimitry Andric 2150b57cec5SDimitry Andric /// List of per function info objects. In theory, Each of these 2160b57cec5SDimitry Andric /// may be associated with a different GC. 2170b57cec5SDimitry Andric using FuncInfoVec = std::vector<std::unique_ptr<GCFunctionInfo>>; 2180b57cec5SDimitry Andric 2190b57cec5SDimitry Andric FuncInfoVec::iterator funcinfo_begin() { return Functions.begin(); } 2200b57cec5SDimitry Andric FuncInfoVec::iterator funcinfo_end() { return Functions.end(); } 2210b57cec5SDimitry Andric 2220b57cec5SDimitry Andric private: 2230b57cec5SDimitry Andric /// Owning list of all GCFunctionInfos associated with this Module 2240b57cec5SDimitry Andric FuncInfoVec Functions; 2250b57cec5SDimitry Andric 2260b57cec5SDimitry Andric /// Non-owning map to bypass linear search when finding the GCFunctionInfo 2270b57cec5SDimitry Andric /// associated with a particular Function. 2280b57cec5SDimitry Andric using finfo_map_type = DenseMap<const Function *, GCFunctionInfo *>; 2290b57cec5SDimitry Andric finfo_map_type FInfoMap; 2300b57cec5SDimitry Andric 2310b57cec5SDimitry Andric public: 2320b57cec5SDimitry Andric using iterator = SmallVector<std::unique_ptr<GCStrategy>, 1>::const_iterator; 2330b57cec5SDimitry Andric 2340b57cec5SDimitry Andric static char ID; 2350b57cec5SDimitry Andric 2360b57cec5SDimitry Andric GCModuleInfo(); 2370b57cec5SDimitry Andric 2380b57cec5SDimitry Andric /// clear - Resets the pass. Any pass, which uses GCModuleInfo, should 2390b57cec5SDimitry Andric /// call it in doFinalization(). 2400b57cec5SDimitry Andric /// 2410b57cec5SDimitry Andric void clear(); 2420b57cec5SDimitry Andric 2430b57cec5SDimitry Andric /// begin/end - Iterators for used strategies. 2440b57cec5SDimitry Andric /// 2450b57cec5SDimitry Andric iterator begin() const { return GCStrategyList.begin(); } 2460b57cec5SDimitry Andric iterator end() const { return GCStrategyList.end(); } 2470b57cec5SDimitry Andric 2480b57cec5SDimitry Andric /// get - Look up function metadata. This is currently assumed 2490b57cec5SDimitry Andric /// have the side effect of initializing the associated GCStrategy. That 2500b57cec5SDimitry Andric /// will soon change. 2510b57cec5SDimitry Andric GCFunctionInfo &getFunctionInfo(const Function &F); 2520b57cec5SDimitry Andric }; 2530b57cec5SDimitry Andric 2540b57cec5SDimitry Andric } // end namespace llvm 2550b57cec5SDimitry Andric 2560b57cec5SDimitry Andric #endif // LLVM_CODEGEN_GCMETADATA_H 257