| //===- DataStructure.h - Build data structure graphs ------------*- C++ -*-===// |
| // |
| // The LLVM Compiler Infrastructure |
| // |
| // This file was developed by the LLVM research group and is distributed under |
| // the University of Illinois Open Source License. See LICENSE.TXT for details. |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // Implement the LLVM data structure analysis library. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef LLVM_ANALYSIS_DATA_STRUCTURE_H |
| #define LLVM_ANALYSIS_DATA_STRUCTURE_H |
| |
| #include "llvm/Pass.h" |
| #include "llvm/Target/TargetData.h" |
| #include "llvm/Support/CallSite.h" |
| #include "llvm/ADT/EquivalenceClasses.h" |
| |
| #include "poolalloc/ADT/HashExtras.h" |
| |
| #include <map> |
| #include <vector> |
| #include <algorithm> |
| |
| namespace llvm { |
| |
| class Type; |
| class Instruction; |
| class GlobalValue; |
| class DSGraph; |
| class DSCallSite; |
| class DSNode; |
| class DSNodeHandle; |
| |
| FunctionPass *createDataStructureStatsPass(); |
| FunctionPass *createDataStructureGraphCheckerPass(); |
| |
| class InstCallGraph { |
| typedef hash_map<const Instruction*, std::vector<const Function*> > ActualCalleesTy; |
| |
| // Callgraph |
| ActualCalleesTy ActualCallees; |
| |
| public: |
| |
| InstCallGraph() { |
| //Dummy node for empty call sites |
| ActualCallees[0]; |
| } |
| |
| typedef std::vector<const Function*>::const_iterator iterator; |
| |
| void add(const Instruction* I, const Function* F) { |
| std::vector<const Function*>& callees = ActualCallees[I]; |
| std::vector<const Function*>::iterator ii |
| = std::lower_bound(callees.begin(), callees.end(), F); |
| if (ii != callees.end() && *ii == F) return; |
| callees.insert(ii, F); |
| } |
| |
| iterator begin(const Instruction *I) const { |
| ActualCalleesTy::const_iterator ii = ActualCallees.find(I); |
| if (ii == ActualCallees.end()) |
| ii = ActualCallees.find(0); |
| return ii->second.begin(); |
| } |
| |
| iterator end(const Instruction *I) const { |
| ActualCalleesTy::const_iterator ii = ActualCallees.find(I); |
| if (ii == ActualCallees.end()) |
| ii = ActualCallees.find(0); |
| return ii->second.end(); |
| } |
| |
| unsigned size() const { |
| unsigned sum = 0; |
| for (ActualCalleesTy::const_iterator ii = ActualCallees.begin(), |
| ee = ActualCallees.end(); ii != ee; ++ii) |
| sum += ii->second.size(); |
| return sum; |
| } |
| |
| template<class OutputIterator> |
| void get_keys(OutputIterator keys) { |
| for (ActualCalleesTy::const_iterator ii = ActualCallees.begin(), |
| ee = ActualCallees.end(); ii != ee; ++ii) |
| *keys++ = ii->first; |
| } |
| |
| void clear() { |
| ActualCallees.clear(); |
| } |
| }; |
| |
| |
| |
| class DataStructures : public ModulePass { |
| typedef hash_map<const Function*, DSGraph*> DSInfoTy; |
| |
| /// TargetData, comes in handy |
| TargetData* TD; |
| |
| /// Pass to get Graphs from |
| DataStructures* GraphSource; |
| |
| /// Do we clone Graphs or steal them? |
| bool Clone; |
| |
| /// do we reset the aux list to the func list? |
| bool resetAuxCalls; |
| |
| /// Were are DSGraphs stolen by another pass? |
| bool DSGraphsStolen; |
| |
| // DSInfo, one graph for each function |
| DSInfoTy DSInfo; |
| |
| // Name for printing |
| const char* printname; |
| |
| protected: |
| |
| /// The Globals Graph contains all information on the globals |
| DSGraph *GlobalsGraph; |
| |
| /// GlobalECs - The equivalence classes for each global value that is merged |
| /// with other global values in the DSGraphs. |
| EquivalenceClasses<const GlobalValue*> GlobalECs; |
| |
| |
| void init(DataStructures* D, bool clone, bool printAuxCalls, bool copyGlobalAuxCalls, bool resetAux); |
| void init(TargetData* T); |
| |
| void formGlobalECs(); |
| |
| |
| DataStructures(intptr_t id, const char* name) |
| : ModulePass(id), TD(0), GraphSource(0), printname(name), GlobalsGraph(0) { |
| |
| // For now, the graphs are owned by this pass |
| DSGraphsStolen = false; |
| } |
| |
| public: |
| /// print - Print out the analysis results... |
| /// |
| void print(std::ostream &O, const Module *M) const; |
| void dumpCallGraph() const; |
| |
| typedef InstCallGraph calleeTy; |
| calleeTy callee; |
| |
| virtual void releaseMemory(); |
| |
| virtual bool hasDSGraph(const Function* F) const { |
| return DSInfo.find(F) != DSInfo.end(); |
| } |
| |
| /// getDSGraph - Return the data structure graph for the specified function. |
| /// |
| virtual DSGraph *getDSGraph(const Function* F) const { |
| hash_map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(F); |
| assert(I != DSInfo.end() && "Function not in module!"); |
| return I->second; |
| } |
| |
| void setDSGraph(const Function* F, DSGraph* G) { |
| DSInfo[F] = G; |
| } |
| |
| DSGraph* getOrFetchDSGraph(const Function* F); |
| |
| |
| DSGraph* getGlobalsGraph() const { return GlobalsGraph; } |
| |
| EquivalenceClasses<const GlobalValue*> &getGlobalECs() { return GlobalECs; } |
| |
| TargetData& getTargetData() const { return *TD; } |
| |
| /// deleteValue/copyValue - Interfaces to update the DSGraphs in the program. |
| /// These correspond to the interfaces defined in the AliasAnalysis class. |
| void deleteValue(Value *V); |
| void copyValue(Value *From, Value *To); |
| }; |
| |
| // LocalDataStructures - The analysis that computes the local data structure |
| // graphs for all of the functions in the program. |
| // |
| // FIXME: This should be a Function pass that can be USED by a Pass, and would |
| // be automatically preserved. Until we can do that, this is a Pass. |
| // |
| class LocalDataStructures : public DataStructures { |
| public: |
| static char ID; |
| LocalDataStructures() : DataStructures((intptr_t)&ID, "local.") {} |
| ~LocalDataStructures() { releaseMemory(); } |
| |
| virtual bool runOnModule(Module &M); |
| |
| /// getAnalysisUsage - This obviously provides a data structure graph. |
| /// |
| virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
| AU.addRequired<TargetData>(); |
| AU.setPreservesAll(); |
| } |
| }; |
| |
| // StdLibDataStructures - This analysis recognizes common standard c library |
| // functions and generates graphs for them. |
| class StdLibDataStructures : public DataStructures { |
| void eraseCallsTo(Function* F); |
| public: |
| static char ID; |
| StdLibDataStructures() : DataStructures((intptr_t)&ID, "stdlib.") {} |
| ~StdLibDataStructures() { releaseMemory(); } |
| |
| virtual bool runOnModule(Module &M); |
| |
| /// getAnalysisUsage - This obviously provides a data structure graph. |
| /// |
| virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
| AU.addRequired<LocalDataStructures>(); |
| AU.addPreserved<TargetData>(); |
| AU.setPreservesCFG(); |
| } |
| }; |
| |
| /// BUDataStructures - The analysis that computes the interprocedurally closed |
| /// data structure graphs for all of the functions in the program. This pass |
| /// only performs a "Bottom Up" propagation (hence the name). |
| /// |
| class BUDataStructures : public DataStructures { |
| protected: |
| |
| // This map is only maintained during construction of BU Graphs |
| std::map<std::vector<const Function*>, |
| std::pair<DSGraph*, std::vector<DSNodeHandle> > > IndCallGraphMap; |
| |
| const char* debugname; |
| bool useCallGraph; |
| bool ReInlineGlobals; |
| |
| public: |
| static char ID; |
| //Child constructor (CBU) |
| BUDataStructures(intptr_t CID, const char* name, const char* printname) |
| : DataStructures(CID, printname), debugname(name), useCallGraph(true), |
| ReInlineGlobals(true) {} |
| //main constructor |
| BUDataStructures() |
| : DataStructures((intptr_t)&ID, "bu."), debugname("dsa-bu"), |
| useCallGraph(false), ReInlineGlobals(false) {} |
| ~BUDataStructures() { releaseMemory(); } |
| |
| virtual bool runOnModule(Module &M); |
| |
| virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
| AU.addRequired<StdLibDataStructures>(); |
| AU.addPreserved<TargetData>(); |
| AU.setPreservesCFG(); |
| } |
| |
| protected: |
| bool runOnModuleInternal(Module &M); |
| |
| private: |
| void calculateGraph(DSGraph* G); |
| |
| void inlineUnresolved(DSGraph* G); |
| |
| unsigned calculateGraphs(const Function *F, |
| std::vector<const Function*> &Stack, |
| unsigned &NextID, |
| hash_map<const Function*, unsigned> &ValMap); |
| |
| |
| void CloneAuxIntoGlobal(DSGraph* G); |
| void finalizeGlobals(void); |
| }; |
| |
| /// CompleteBUDataStructures - This is the exact same as the bottom-up graphs, |
| /// but we use take a completed call graph and inline all indirect callees into |
| /// their callers graphs, making the result more useful for things like pool |
| /// allocation. |
| /// |
| class CompleteBUDataStructures : public BUDataStructures { |
| protected: |
| void buildIndirectFunctionSets(Module &M); |
| public: |
| static char ID; |
| CompleteBUDataStructures(intptr_t CID = (intptr_t)&ID, |
| const char* name = "dsa-cbu", |
| const char* printname = "cbu.") |
| : BUDataStructures(CID, name, printname) {} |
| ~CompleteBUDataStructures() { releaseMemory(); } |
| |
| virtual bool runOnModule(Module &M); |
| |
| virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
| AU.addRequired<BUDataStructures>(); |
| AU.addPreserved<TargetData>(); |
| AU.setPreservesCFG(); |
| } |
| |
| }; |
| |
| /// EquivBUDataStructures - This is the same as the complete bottom-up graphs, but |
| /// with functions partitioned into equivalence classes and a single merged |
| /// DS graph for all functions in an equivalence class. After this merging, |
| /// graphs are inlined bottom-up on the SCCs of the final (CBU) call graph. |
| /// |
| class EquivBUDataStructures : public CompleteBUDataStructures { |
| void mergeGraphsByGlobalECs(); |
| public: |
| static char ID; |
| EquivBUDataStructures() |
| : CompleteBUDataStructures((intptr_t)&ID, "dsa-eq", "eq.") {} |
| ~EquivBUDataStructures() { releaseMemory(); } |
| |
| virtual bool runOnModule(Module &M); |
| |
| virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
| AU.addRequired<CompleteBUDataStructures>(); |
| AU.addPreserved<TargetData>(); |
| AU.setPreservesCFG(); |
| } |
| |
| }; |
| |
| /// TDDataStructures - Analysis that computes new data structure graphs |
| /// for each function using the closed graphs for the callers computed |
| /// by the bottom-up pass. |
| /// |
| class TDDataStructures : public DataStructures { |
| hash_set<const Function*> ArgsRemainIncomplete; |
| |
| /// CallerCallEdges - For a particular graph, we keep a list of these records |
| /// which indicates which graphs call this function and from where. |
| struct CallerCallEdge { |
| DSGraph *CallerGraph; // The graph of the caller function. |
| const DSCallSite *CS; // The actual call site. |
| const Function *CalledFunction; // The actual function being called. |
| |
| CallerCallEdge(DSGraph *G, const DSCallSite *cs, const Function *CF) |
| : CallerGraph(G), CS(cs), CalledFunction(CF) {} |
| |
| bool operator<(const CallerCallEdge &RHS) const { |
| return CallerGraph < RHS.CallerGraph || |
| (CallerGraph == RHS.CallerGraph && CS < RHS.CS); |
| } |
| }; |
| |
| std::map<DSGraph*, std::vector<CallerCallEdge> > CallerEdges; |
| |
| |
| // IndCallMap - We memoize the results of indirect call inlining operations |
| // that have multiple targets here to avoid N*M inlining. The key to the map |
| // is a sorted set of callee functions, the value is the DSGraph that holds |
| // all of the caller graphs merged together, and the DSCallSite to merge with |
| // the arguments for each function. |
| std::map<std::vector<const Function*>, DSGraph*> IndCallMap; |
| |
| bool useEQBU; |
| |
| public: |
| static char ID; |
| TDDataStructures(intptr_t CID = (intptr_t)&ID, const char* printname = "td.", bool useEQ = false) |
| : DataStructures(CID, printname), useEQBU(useEQ) {} |
| ~TDDataStructures() { releaseMemory(); } |
| |
| virtual bool runOnModule(Module &M); |
| |
| /// getAnalysisUsage - This obviously provides a data structure graph. |
| /// |
| virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
| if (useEQBU) { |
| AU.addRequired<EquivBUDataStructures>(); |
| } else { |
| AU.addRequired<BUDataStructures>(); |
| AU.addPreserved<BUDataStructures>(); |
| } |
| AU.addPreserved<TargetData>(); |
| AU.setPreservesCFG(); |
| } |
| |
| private: |
| void markReachableFunctionsExternallyAccessible(DSNode *N, |
| hash_set<DSNode*> &Visited); |
| |
| void InlineCallersIntoGraph(DSGraph* G); |
| void ComputePostOrder(const Function* F, hash_set<DSGraph*> &Visited, |
| std::vector<DSGraph*> &PostOrder); |
| }; |
| |
| /// EQTDDataStructures - Analysis that computes new data structure graphs |
| /// for each function using the closed graphs for the callers computed |
| /// by the EQ bottom-up pass. |
| /// |
| class EQTDDataStructures : public TDDataStructures { |
| public: |
| static char ID; |
| EQTDDataStructures() |
| :TDDataStructures((intptr_t)&ID, "eqtd.", false) |
| {} |
| }; |
| |
| /// SteensgaardsDataStructures - Analysis that computes a context-insensitive |
| /// data structure graphs for the whole program. |
| /// |
| class SteensgaardDataStructures : public DataStructures { |
| DSGraph * ResultGraph; |
| DataStructures * DS; |
| void ResolveFunctionCall(const Function *F, const DSCallSite &Call, |
| DSNodeHandle &RetVal); |
| bool runOnModuleInternal(Module &M); |
| |
| public: |
| static char ID; |
| SteensgaardDataStructures() : |
| DataStructures((intptr_t)&ID, "steensgaard."), |
| ResultGraph(NULL) {} |
| ~SteensgaardDataStructures(); |
| virtual bool runOnModule(Module &M); |
| virtual void releaseMemory(); |
| |
| virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
| AU.addRequired<TargetData>(); |
| AU.addRequired<StdLibDataStructures>(); |
| AU.setPreservesAll(); |
| } |
| |
| /// getDSGraph - Return the data structure graph for the specified function. |
| /// |
| virtual DSGraph *getDSGraph(const Function* F) const { |
| return getResultGraph(); |
| } |
| |
| virtual bool hasDSGraph(const Function* F) const { |
| return true; |
| } |
| |
| /// getDSGraph - Return the data structure graph for the whole program. |
| /// |
| DSGraph *getResultGraph() const { |
| return ResultGraph; |
| } |
| |
| void print(OStream O, const Module *M) const; |
| void print(std::ostream &O, const Module *M) const; |
| |
| }; |
| |
| |
| } // End llvm namespace |
| |
| #endif |