#ifndef LLVM_ANALYSIS_DATA_STRUCTURE_H
#define LLVM_ANALYSIS_DATA_STRUCTURE_H
-#include "llvm/Analysis/DSGraph.h"
#include "llvm/Pass.h"
-#if 0
-#include "llvm/GlobalValue.h"
-#include "Support/HashExtras.h"
#include "Support/hash_set"
-#endif
-#include <set>
class Type;
-class GlobalValue;
-#if 0
-class GlobalDSGraph; // A common graph for globals in a program
-#endif
-class LocalDataStructures; // A collection of local graphs for a program
-class BUDataStructures; // A collection of bu graphs for a program
-class TDDataStructures; // A collection of td graphs for a program
-
+class CallInst;
+class DSGraph;
+class DSNode;
+class DSCallSite;
// FIXME: move this stuff to a private header
namespace DataStructureAnalysis {
}
-#if 0
-// GlobalDSGraph - A common graph for all the globals and their outgoing links
-// to externally visible nodes. This includes GlobalValues, New nodes,
-// Cast nodes, and Calls. This graph can only be used by one of the
-// individual function graphs, and it goes away when they all go away.
-//
-class GlobalDSGraph : public DSGraph {
- hash_set<const DSGraph*> Referrers;
- void addReference(const DSGraph* referrer);
- void removeReference(const DSGraph* referrer);
- friend class DSGraph; // give access to Referrers
-
- GlobalDSGraph(const GlobalDSGraph &GlobalDSG); // Do not implement
-
- // Helper function for cloneGlobals and cloneCalls
- DSNode* cloneNodeInto(DSNode *OldNode,
- std::map<const DSNode*, DSNode*> &NodeCache,
- bool GlobalsAreFinal = false);
-
-public:
- GlobalDSGraph(); // Create an empty DSGraph
- virtual ~GlobalDSGraph();
-
- void cloneGlobals(DSGraph& Graph, bool CloneCalls = false);
- void cloneCalls (DSGraph& Graph);
-};
-#endif
-
// LocalDataStructures - The analysis that computes the local data structure
// graphs for all of the functions in the program.
//
//
class LocalDataStructures : public Pass {
// DSInfo, one graph for each function
- std::map<const Function*, DSGraph*> DSInfo;
+ hash_map<Function*, DSGraph*> DSInfo;
+ DSGraph *GlobalsGraph;
public:
~LocalDataStructures() { releaseMemory(); }
virtual bool run(Module &M);
+ bool hasGraph(const Function &F) const {
+ return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
+ }
+
// getDSGraph - Return the data structure graph for the specified function.
DSGraph &getDSGraph(const Function &F) const {
- std::map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
+ hash_map<Function*, DSGraph*>::const_iterator I =
+ DSInfo.find(const_cast<Function*>(&F));
assert(I != DSInfo.end() && "Function not in module!");
return *I->second;
}
+ DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
+
// print - Print out the analysis results...
void print(std::ostream &O, const Module *M) const;
}
};
-#if 0
+
// 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" propogation (hence the name).
+// only performs a "Bottom Up" propagation (hence the name).
//
class BUDataStructures : public Pass {
// DSInfo, one graph for each function
- std::map<const Function*, DSGraph*> DSInfo;
+ hash_map<Function*, DSGraph*> DSInfo;
+ DSGraph *GlobalsGraph;
+ hash_multimap<CallInst*, Function*> ActualCallees;
public:
~BUDataStructures() { releaseMemory(); }
virtual bool run(Module &M);
+ bool hasGraph(const Function &F) const {
+ return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
+ }
+
// getDSGraph - Return the data structure graph for the specified function.
DSGraph &getDSGraph(const Function &F) const {
- std::map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
+ hash_map<Function*, DSGraph*>::const_iterator I =
+ DSInfo.find(const_cast<Function*>(&F));
assert(I != DSInfo.end() && "Function not in module!");
return *I->second;
}
+ DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
+
// print - Print out the analysis results...
void print(std::ostream &O, const Module *M) const;
// If the pass pipeline is done with this pass, we can release our memory...
virtual void releaseMemory();
- // getAnalysisUsage - This obviously provides a data structure graph.
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
AU.addRequired<LocalDataStructures>();
}
+
+ typedef hash_multimap<CallInst*, Function*> ActualCalleesTy;
+ const ActualCalleesTy &getActualCallees() const {
+ return ActualCallees;
+ }
+
private:
- DSGraph &calculateGraph(Function &F);
+ void calculateGraph(DSGraph &G);
+
+ void calculateReachableGraphs(Function *F);
+
+
+ DSGraph &getOrCreateGraph(Function *F);
+
+ unsigned calculateGraphs(Function *F, std::vector<Function*> &Stack,
+ unsigned &NextID,
+ hash_map<Function*, unsigned> &ValMap);
};
//
class TDDataStructures : public Pass {
// DSInfo, one graph for each function
- std::map<const Function*, DSGraph*> DSInfo;
+ hash_map<Function*, DSGraph*> DSInfo;
+ hash_set<Function*> ArgsRemainIncomplete;
+ DSGraph *GlobalsGraph;
public:
- ~TDDataStructures() { releaseMemory(); }
+ ~TDDataStructures() { releaseMyMemory(); }
virtual bool run(Module &M);
+ bool hasGraph(const Function &F) const {
+ return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
+ }
+
// getDSGraph - Return the data structure graph for the specified function.
DSGraph &getDSGraph(const Function &F) const {
- std::map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
+ hash_map<Function*, DSGraph*>::const_iterator I =
+ DSInfo.find(const_cast<Function*>(&F));
assert(I != DSInfo.end() && "Function not in module!");
return *I->second;
}
+ DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
+
// print - Print out the analysis results...
void print(std::ostream &O, const Module *M) const;
// If the pass pipeline is done with this pass, we can release our memory...
- virtual void releaseMemory();
+ virtual void releaseMyMemory();
// getAnalysisUsage - This obviously provides a data structure graph.
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
AU.addRequired<BUDataStructures>();
}
+
private:
- DSGraph &calculateGraph(Function &F);
- void pushGraphIntoCallee(DSGraph &callerGraph, DSGraph &calleeGraph,
- std::map<Value*, DSNodeHandle> &OldValMap,
- std::map<const DSNode*, DSNode*> &OldNodeMap);
+ void inlineGraphIntoCallees(DSGraph &G);
+ DSGraph &getOrCreateDSGraph(Function &F);
+ void ComputePostOrder(Function &F, hash_set<DSGraph*> &Visited,
+ std::vector<DSGraph*> &PostOrder,
+ const BUDataStructures::ActualCalleesTy &ActualCallees);
};
-#endif
#endif
projects / oota-llvm.git / blobdiff