diff options
| -rw-r--r-- | include/llvm/CodeGen/CollectorMetadata.h | 195 | ||||
| -rw-r--r-- | lib/CodeGen/CollectorMetadata.cpp | 185 |
2 files changed, 380 insertions, 0 deletions
diff --git a/include/llvm/CodeGen/CollectorMetadata.h b/include/llvm/CodeGen/CollectorMetadata.h new file mode 100644 index 0000000..9924bd9 --- /dev/null +++ b/include/llvm/CodeGen/CollectorMetadata.h @@ -0,0 +1,195 @@ +//===-- CollectorMetadata.h - Garbage collector metadata ------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file was developed by Gordon Henriksen and is distributed under +// the University of Illinois Open Source License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file declares the CollectorMetadata and CollectorModuleMetadata classes, +// which are used as a communication channel from the target code generator +// to the target garbage collector. This interface allows code generators and +// garbage collectors to be developed independently. +// +// The CollectorMetadata class records the data necessary to build a type +// accurate stack map. Roots are specified in the LLVM IR using the llvm.gcroot +// intrinsic, which the code generator understands. The code generator records +// the stack offset for each GC root. Safe points are generated by the code +// generator according to the collector's declared needs (generally at function +// calls). +// +// Safe points and roots are sufficient to build type-accurate stack maps. As a +// refinement, liveness analysis calculates the set of live roots at each safe +// point. Liveness analysis is not presently performed, so all roots are assumed +// live. +// +// CollectorModuleMetadata simply collects CollectorMetadata structures for each +// Function as it is compiled. This is necessary for collectors which must emit +// a stack map for the entire compilation unit. CollectorMetadata outlives the +// MachineFunction from which it is derived, so must not refer to any code +// generator data structures. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_COLLECTORMETADATA_H +#define LLVM_CODEGEN_COLLECTORMETADATA_H + +#include "llvm/Pass.h" +#include "llvm/ADT/DenseMap.h" + +namespace llvm { + + class Constant; + + + /// Creates a pass to print collector metadata. + /// + Pass *createCollectorMetadataPrinter(std::ostream &OS); + + /// Creates a pass to destroy collector metadata. + /// + Pass *createCollectorMetadataDeleter(); + + + namespace GC { + /// PointKind - The type of a collector-safe point. + /// + enum PointKind { + Loop, //< Instr is a loop (backwards branch). + Return, //< Instr is a return instruction. + PreCall, //< Instr is a call instruction. + PostCall //< Instr is the return address of a call. + }; + } + + /// GCPoint - Metadata for a collector-safe point in machine code. + /// + struct GCPoint { + GC::PointKind Kind; //< The kind of the safe point. + unsigned Num; //< Usually a label. + + GCPoint(GC::PointKind K, unsigned N) : Kind(K), Num(N) {} + }; + + /// GCRoot - Metadata for a pointer to an object managed by the garbage + /// collector. + struct GCRoot { + int Num; //< Usually a frame index. + int StackOffset; //< Offset from the stack pointer. + Constant *Metadata; //< From the call to llvm.gcroot. + + GCRoot(int N, Constant *MD) : Num(N), StackOffset(-1), Metadata(MD) {} + }; + + + /// CollectorMetadata - Garbage collection metadata for a function. + /// + class CollectorMetadata { + public: + typedef std::vector<GCPoint>::iterator iterator; + typedef std::vector<GCRoot>::iterator roots_iterator; + typedef std::vector<GCRoot>::const_iterator live_iterator; + + private: + const Function &F; + uint64_t FrameSize; + std::vector<GCRoot> Roots; + std::vector<GCPoint> SafePoints; + + // FIXME: Liveness. A 2D BitVector, perhaps? + // + // BitVector Liveness; + // + // bool islive(int point, int root) = + // Liveness[point * SafePoints.size() + root] + // + // The bit vector is the more compact representation where >3.2% of roots + // are live per safe point (1.5% on 64-bit hosts). + + friend class CollectorModuleMetadata; + CollectorMetadata(const Function &F); + + public: + ~CollectorMetadata(); + + const Function &getFunction() const { return F; } + + /// addStackRoot - Registers a root that lives on the stack. Num is the + /// stack object ID for the alloca (if the code generator is using + /// MachineFrameInfo). + void addStackRoot(int Num, Constant *Metadata) { + Roots.push_back(GCRoot(Num, Metadata)); + } + + /// addSafePoint - Notes the existence of a safe point. Num is the ID of the + /// label just prior to the safe point (if the code generator is using + /// MachineModuleInfo). + void addSafePoint(GC::PointKind Kind, unsigned Num) { + SafePoints.push_back(GCPoint(Kind, Num)); + } + + /// getFrameSize/setFrameSize - Records the function's frame size. + /// + uint64_t getFrameSize() const { return FrameSize; } + void setFrameSize(uint64_t S) { FrameSize = S; } + + /// begin/end - Iterators for safe points. + /// + iterator begin() { return SafePoints.begin(); } + iterator end() { return SafePoints.end(); } + size_t size() const { return SafePoints.size(); } + + /// roots_begin/roots_end - Iterators for all roots in the function. + /// + roots_iterator roots_begin() { return Roots.begin(); } + roots_iterator roots_end () { return Roots.end(); } + size_t roots_size() const { return Roots.size(); } + + /// live_begin/live_end - Iterators for live roots at a given safe point. + /// + live_iterator live_begin(const iterator &p) { return roots_begin(); } + live_iterator live_end (const iterator &p) { return roots_end(); } + size_t live_size(const iterator &p) const { return roots_size(); } + }; + + + /// CollectorModuleMetadata - Garbage collection metadata for a whole module. + /// + class CollectorModuleMetadata : public ImmutablePass { + typedef std::vector<CollectorMetadata*> list_type; + typedef DenseMap<const Function*,CollectorMetadata*> map_type; + + Module *Mod; + list_type Functions; + map_type Map; + + public: + typedef list_type::iterator iterator; + + static char ID; + + CollectorModuleMetadata(); + ~CollectorModuleMetadata(); + + /// clear - Used to delete module metadata. Collector invokes this as + /// necessary. + void clear(); + + /// begin/end - Iterators for function metadata. + /// + iterator begin() { return Functions.begin(); } + iterator end() { return Functions.end(); } + + /// insert - Creates metadata for a function. + /// + CollectorMetadata& insert(const Function *F); + + /// get - Looks up existing function metadata. + /// + CollectorMetadata* get(const Function *F) const; + }; + +} + +#endif diff --git a/lib/CodeGen/CollectorMetadata.cpp b/lib/CodeGen/CollectorMetadata.cpp new file mode 100644 index 0000000..f86ee04 --- /dev/null +++ b/lib/CodeGen/CollectorMetadata.cpp @@ -0,0 +1,185 @@ +//===-- CollectorMetadata.cpp - Garbage collector metadata ----------------===// +// +// The LLVM Compiler Infrastructure +// +// This file was developed by Gordon Henriksen and is distributed under +// the University of Illinois Open Source License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements the CollectorMetadata and CollectorModuleMetadata +// classes. +// +//===----------------------------------------------------------------------===// + +#include "llvm/CodeGen/CollectorMetadata.h" +#include "llvm/CodeGen/MachineFrameInfo.h" +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/Function.h" +#include "llvm/Support/Compiler.h" + +using namespace llvm; + +namespace { + + class VISIBILITY_HIDDEN Printer : public MachineFunctionPass { + static char ID; + std::ostream &OS; + + public: + Printer(std::ostream &OS = *cerr); + + const char *getPassName() const; + void getAnalysisUsage(AnalysisUsage &AU) const; + + bool runOnMachineFunction(MachineFunction &MF); + }; + + class VISIBILITY_HIDDEN Deleter : public MachineFunctionPass { + static char ID; + + public: + Deleter(); + + const char *getPassName() const; + void getAnalysisUsage(AnalysisUsage &AU) const; + + bool runOnMachineFunction(MachineFunction &MF); + bool doFinalization(Module &M); + }; + + RegisterPass<CollectorModuleMetadata> + X("collector-metadata", "Create Garbage Collector Module Metadata"); + +} + +// ----------------------------------------------------------------------------- + +CollectorMetadata::CollectorMetadata(const Function &F) + : F(F), FrameSize(~0LL) {} + +CollectorMetadata::~CollectorMetadata() {} + +// ----------------------------------------------------------------------------- + +char CollectorModuleMetadata::ID = 0; + +CollectorModuleMetadata::CollectorModuleMetadata() + : ImmutablePass((intptr_t)&ID) {} + +CollectorModuleMetadata::~CollectorModuleMetadata() { + clear(); +} + +CollectorMetadata& CollectorModuleMetadata::insert(const Function *F) { + assert(Map.find(F) == Map.end() && "Function GC metadata already exists!"); + CollectorMetadata *FMD = new CollectorMetadata(*F); + Functions.push_back(FMD); + Map[F] = FMD; + return *FMD; +} + +CollectorMetadata* CollectorModuleMetadata::get(const Function *F) const { + map_type::iterator I = Map.find(F); + if (I == Map.end()) + return 0; + return I->second; +} + +void CollectorModuleMetadata::clear() { + for (iterator I = begin(), E = end(); I != E; ++I) + delete *I; + + Functions.clear(); + Map.clear(); +} + +// ----------------------------------------------------------------------------- + +char Printer::ID = 0; + +Pass *llvm::createCollectorMetadataPrinter(std::ostream &OS) { + return new Printer(OS); +} + +Printer::Printer(std::ostream &OS) + : MachineFunctionPass(intptr_t(&ID)), OS(OS) {} + +const char *Printer::getPassName() const { + return "Print Garbage Collector Information"; +} + +void Printer::getAnalysisUsage(AnalysisUsage &AU) const { + MachineFunctionPass::getAnalysisUsage(AU); + AU.setPreservesAll(); + AU.addRequired<CollectorModuleMetadata>(); +} + +static const char *DescKind(GC::PointKind Kind) { + switch (Kind) { + default: assert(0 && "Unknown GC point kind"); + case GC::Loop: return "loop"; + case GC::Return: return "return"; + case GC::PreCall: return "pre-call"; + case GC::PostCall: return "post-call"; + } +} + +bool Printer::runOnMachineFunction(MachineFunction &MF) { + if (CollectorMetadata *FD = + getAnalysis<CollectorModuleMetadata>().get(MF.getFunction())) { + + OS << "GC roots for " << FD->getFunction().getNameStart() << ":\n"; + for (CollectorMetadata::roots_iterator RI = FD->roots_begin(), + RE = FD->roots_end(); + RI != RE; ++RI) + OS << "\t" << RI->Num << "\t" << RI->StackOffset << "[sp]\n"; + + OS << "GC safe points for " << FD->getFunction().getNameStart() << ":\n"; + for (CollectorMetadata::iterator PI = FD->begin(), + PE = FD->end(); PI != PE; ++PI) { + + OS << "\tlabel " << PI->Num << ": " << DescKind(PI->Kind) << ", live = {"; + + for (CollectorMetadata::live_iterator RI = FD->live_begin(PI), + RE = FD->live_end(PI);;) { + OS << " " << RI->Num; + if (++RI == RE) + break; + OS << ","; + } + + OS << " }\n"; + } + } + + return false; +} + +// ----------------------------------------------------------------------------- + +char Deleter::ID = 0; + +Pass *llvm::createCollectorMetadataDeleter() { + return new Deleter(); +} + +Deleter::Deleter() : MachineFunctionPass(intptr_t(&ID)) {} + +const char *Deleter::getPassName() const { + return "Delete Garbage Collector Information"; +} + +void Deleter::getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); + AU.addRequired<CollectorModuleMetadata>(); +} + +bool Deleter::runOnMachineFunction(MachineFunction &MF) { + return false; +} + +bool Deleter::doFinalization(Module &M) { + getAnalysis<CollectorModuleMetadata>().clear(); + return false; +} |