Remove unused rdsa includes.
llvm-svn: 231372
diff --git a/poolalloc/include/rdsa/CallTargets.h b/poolalloc/include/rdsa/CallTargets.h
deleted file mode 100644
index c89410f..0000000
--- a/poolalloc/include/rdsa/CallTargets.h
+++ /dev/null
@@ -1,58 +0,0 @@
-//=- llvm/Analysis/CallTargets.h - Resolve Indirect Call Targets --*- 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.
-//
-//===----------------------------------------------------------------------===//
-//
-// This pass uses DSA to map targets of all calls, and reports on if it
-// thinks it knows all targets of a given call.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_ANALYSIS_CALLTARGETS_H
-#define LLVM_ANALYSIS_CALLTARGETS_H
-
-#include "llvm/Pass.h"
-#include "llvm/IR/CallSite.h"
-
-#include <set>
-#include <list>
-#include <map>
-
-namespace llvm {
-
- class CallTargetFinder : public ModulePass {
- std::map<CallSite, std::vector<const Function*> > IndMap;
- std::set<CallSite> CompleteSites;
- std::list<CallSite> AllSites;
-
- void findIndTargets(Module &M);
- public:
- static char ID;
- CallTargetFinder() : ModulePass((intptr_t)&ID) {}
-
- virtual bool runOnModule(Module &M);
-
- virtual void getAnalysisUsage(AnalysisUsage &AU) const;
-
- virtual void print(std::ostream &O, const Module *M) const;
-
- // Given a CallSite, get an iterator of callees
- std::vector<const Function*>::iterator begin(CallSite cs);
- std::vector<const Function*>::iterator end(CallSite cs);
-
- // Iterate over CallSites in program
- std::list<CallSite>::iterator cs_begin();
- std::list<CallSite>::iterator cs_end();
-
- // Do we think we have complete knowledge of this site?
- // That is, do we think there are no missing callees
- bool isComplete(CallSite cs) const;
- };
-
-}
-
-#endif
diff --git a/poolalloc/include/rdsa/DSFlags.h b/poolalloc/include/rdsa/DSFlags.h
deleted file mode 100644
index d453c11..0000000
--- a/poolalloc/include/rdsa/DSFlags.h
+++ /dev/null
@@ -1,138 +0,0 @@
-class DSFlags {
-
- public:
- enum NodeTy {
- ShadowNode = 0, // Nothing is known about this node...
- AllocaNode = 1 << 0, // This node was allocated with alloca
- HeapNode = 1 << 1, // This node was allocated with malloc
- GlobalNode = 1 << 2, // This node was allocated by a global
- ExternGlobalNode = 1 << 3, // Tyis node was allocated by an extern global
- FunctionNode = 1 << 4, // This node contains a function
- ExternFunctionNode = 1 << 5, // This node contains an extern func
- IntToPtrNode = 1 << 7, // This node comes from an int cast
- PtrToIntNode = 1 << 8, // This node escapes to an int cast
- EscapedNode = 1 << 9, // This node escapes to external code
- ModifiedNode = 1 << 10, // This node is modified in this context
- ReadNode = 1 << 11, // This node is read in this context
- ArrayNode = 1 << 12, // This node is treated like an array
-
- UnknownNode = 1 << 13, // This node points to unknown allocated memory
- IncompleteNode = 1 << 14, // This node may not be complete
-
- //#ifndef NDEBUG
- DeadNode = 1 << 15 // This node is dead and should not be pointed to
- //#endif
- };
-
- private:
- /// NodeType - A union of the above bits. "Shadow" nodes do not add any flags
- /// to the nodes in the data structure graph, so it is possible to have nodes
- /// with a value of 0 for their NodeType.
- ///
- unsigned short NodeType;
-
- public:
- /// maskNodeTypes - Apply a mask to the node types bitfield.
- ///
- void maskFlags(unsigned short Mask) {
- NodeType &= Mask;
- }
-
- void mergeFlags(unsigned short RHS) {
- NodeType |= RHS;
- }
-
- unsigned short getFlags() const {
- return NodeType;
- }
-
- bool isAllocaNode() const { return NodeType & AllocaNode; }
- bool isHeapNode() const { return NodeType & HeapNode; }
- bool isGlobalNode() const { return NodeType & GlobalNode; }
- bool isExternGlobalNode() const { return NodeType & ExternGlobalNode; }
- bool isFunctionNode() const { return NodeType & FunctionNode; }
- bool isExternFunctionNode() const { return NodeType & FunctionNode; }
- bool isIntToPtrNode() const { return NodeType & IntToPtrNode; }
- bool isPtrToIntNode() const { return NodeType & PtrToIntNode; }
- bool isEscapedNode() const { return NodeType & EscapedNode; }
- bool isModifiedNode() const { return NodeType & ModifiedNode; }
- bool isReadNode() const { return NodeType & ReadNode; }
- bool isArrayNode() const { return NodeType & ArrayNode; }
- bool isUnknownNode() const { return NodeType & UnknownNode; }
- bool isIncompleteNode() const { return NodeType & IncompleteNode; }
- bool isCompleteNode() const { return !isIncompleteNode(); }
- bool isDeadNode() const { return NodeType & DeadNode; }
-
- bool isComputedUnknownNode() const {
- return isIntToPtrNode();
- }
-
- void setAllocaNode() { NodeType |= AllocaNode; }
- void setHeapNode() { NodeType |= HeapNode; }
- void setGlobalNode() { NodeType |= GlobalNode; }
- void setExternGlobalNode() { NodeType |= ExternGlobalNode; }
- void setFunctionNode() { NodeType |= FunctionNode; }
- void setExternFunctionNode() { NodeType |= ExternFunctionNode; }
- void setIntToPtrNode() { NodeType |= IntToPtrNode; }
- void setPtrToIntNode() { NodeType |= PtrToIntNode; }
- void setEscapedNode() { NodeType |= EscapedNode; }
- void setModifiedNode() { NodeType |= ModifiedNode; }
- void setReadNode() { NodeType |= ReadNode; }
- void setArrayNode() { NodeType |= ArrayNode; }
-
- void setUnknownNode() { NodeType |= UnknownNode; }
- void setIncompleteNode() { NodeType |= IncompleteNode; }
- void setDeadNode() { NodeType |= DeadNode; }
-
- // template to avoid std::string include
- template<class STR>
- void appendString(STR& str) const {
- if (isAllocaNode()) {
- str += "S";
- }
- if (isHeapNode()) {
- str += "H";
- }
- if (isGlobalNode()) {
- str += "Gl";
- }
- if (isExternGlobalNode()) {
- str += "Ge";
- }
- if (isFunctionNode()) {
- str += "Fl";
- }
- if (isExternFunctionNode()) {
- str += "Fe";
- }
- if (isIntToPtrNode()) {
- str += "P";
- }
- if (isPtrToIntNode()) {
- str += "2";
- }
- if (isEscapedNode()) {
- str += "E";
- }
- if (isModifiedNode()) {
- str += "M";
- }
- if (isReadNode()) {
- str += "R";
- }
- if (isArrayNode()) {
- str += "A";
- }
- if (isUnknownNode()) {
- str += "U";
- }
- if (isIncompleteNode()) {
- str += "I";
- }
- if (isDeadNode()) {
- str += "<dead>";
- }
- }
-
- DSFlags() :NodeType(0) {}
-};
diff --git a/poolalloc/include/rdsa/DSGraph.h b/poolalloc/include/rdsa/DSGraph.h
deleted file mode 100644
index 4adc6c5..0000000
--- a/poolalloc/include/rdsa/DSGraph.h
+++ /dev/null
@@ -1,628 +0,0 @@
-//===- DSGraph.h - Represent a collection of data structures ----*- 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.
-//
-//===----------------------------------------------------------------------===//
-//
-// This header defines the data structure graph (DSGraph) and the
-// ReachabilityCloner class.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_ANALYSIS_DSGRAPH_H
-#define LLVM_ANALYSIS_DSGRAPH_H
-
-#include "rdsa/DSNode.h"
-#include "llvm/ADT/EquivalenceClasses.h"
-#include "poolalloc/ADT/HashExtras.h"
-
-#include <ext/hash_map>
-#include <ext/hash_set>
-#include <list>
-#include <map>
-#include <iostream>
-
-namespace llvm {
-
-
-class GlobalValue;
-
-//===----------------------------------------------------------------------===//
-/// DSScalarMap - An instance of this class is used to keep track of all of
-/// which DSNode each scalar in a function points to. This is specialized to
-/// keep track of globals with nodes in the function, and to keep track of the
-/// unique DSNodeHandle being used by the scalar map.
-///
-/// This class is crucial to the efficiency of DSA with some large SCC's. In
-/// these cases, the cost of iterating over the scalar map dominates the cost
-/// of DSA. In all of these cases, the DSA phase is really trying to identify
-/// globals or unique node handles active in the function.
-///
-class DSScalarMap {
- typedef hash_map<const Value*, DSNodeHandle> ValueMapTy;
- ValueMapTy ValueMap;
-
- typedef hash_set<const GlobalValue*> GlobalSetTy;
- GlobalSetTy GlobalSet;
-
- EquivalenceClasses<const GlobalValue*> &GlobalECs;
-public:
- DSScalarMap(EquivalenceClasses<const GlobalValue*> &ECs) : GlobalECs(ECs) {}
-
- EquivalenceClasses<const GlobalValue*> &getGlobalECs() const { return GlobalECs; }
-
- // Compatibility methods: provide an interface compatible with a map of
- // Value* to DSNodeHandle's.
- typedef ValueMapTy::const_iterator const_iterator;
- typedef ValueMapTy::iterator iterator;
- iterator begin() { return ValueMap.begin(); }
- iterator end() { return ValueMap.end(); }
- const_iterator begin() const { return ValueMap.begin(); }
- const_iterator end() const { return ValueMap.end(); }
-
- const GlobalValue *getLeaderForGlobal(const GlobalValue *GV) const {
- EquivalenceClasses<const GlobalValue*>::iterator ECI = GlobalECs.findValue(GV);
- if (ECI == GlobalECs.end()) return GV;
- return *GlobalECs.findLeader(ECI);
- }
-
-
- iterator find(const Value *V) {
- iterator I = ValueMap.find(V);
- if (I != ValueMap.end()) return I;
-
- if (const GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
- // If this is a global, check to see if it is equivalenced to something
- // in the map.
- const GlobalValue *Leader = getLeaderForGlobal(GV);
- if (Leader != GV)
- I = ValueMap.find((const Value*)Leader);
- }
- return I;
- }
- const_iterator find(const Value *V) const {
- const_iterator I = ValueMap.find(V);
- if (I != ValueMap.end()) return I;
-
- if (const GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
- // If this is a global, check to see if it is equivalenced to something
- // in the map.
- const GlobalValue *Leader = getLeaderForGlobal(GV);
- if (Leader != GV)
- I = ValueMap.find((const Value*)Leader);
- }
- return I;
- }
-
- /// getRawEntryRef - This method can be used by clients that are aware of the
- /// global value equivalence class in effect.
- DSNodeHandle &getRawEntryRef(const Value *V) {
- std::pair<iterator,bool> IP =
- ValueMap.insert(std::make_pair(V, DSNodeHandle()));
- if (IP.second) // Inserted the new entry into the map.
- if (const GlobalValue *GV = dyn_cast<GlobalValue>(V))
- GlobalSet.insert(GV);
- return IP.first->second;
- }
-
- unsigned count(const Value *V) const { return ValueMap.find(V) != ValueMap.end(); }
-
- void erase(const Value *V) { erase(ValueMap.find(V)); }
-
- void eraseIfExists(const Value *V) {
- iterator I = find(V);
- if (I != end()) erase(I);
- }
-
- /// replaceScalar - When an instruction needs to be modified, this method can
- /// be used to update the scalar map to remove the old and insert the new.
- ///
- void replaceScalar(const Value *Old, const Value *New) {
- iterator I = find(Old);
- assert(I != end() && "Old value is not in the map!");
- ValueMap.insert(std::make_pair(New, I->second));
- erase(I);
- }
-
- /// copyScalarIfExists - If Old exists in the scalar map, make New point to
- /// whatever Old did.
- void copyScalarIfExists(const Value *Old, const Value *New) {
- iterator I = find(Old);
- if (I != end())
- ValueMap.insert(std::make_pair(New, I->second));
- }
-
- /// operator[] - Return the DSNodeHandle for the specified value, creating a
- /// new null handle if there is no entry yet.
- DSNodeHandle &operator[](const Value *V) {
- iterator I = ValueMap.find(V);
- if (I != ValueMap.end())
- return I->second; // Return value if already exists.
-
- if (const GlobalValue *GV = dyn_cast<GlobalValue>(V))
- return AddGlobal(GV);
-
- return ValueMap.insert(std::make_pair(V, DSNodeHandle())).first->second;
- }
-
- void erase(iterator I) {
- assert(I != ValueMap.end() && "Cannot erase end!");
- if (const GlobalValue *GV = dyn_cast<GlobalValue>(I->first))
- GlobalSet.erase(GV);
- ValueMap.erase(I);
- }
-
- void clear_scalars() {
- unsigned counter = 0;
- for(iterator ii = begin(); ii != end(); )
- if (isa<GlobalValue>(ii->first))
- ++ii;
- else {
- ++counter;
- iterator next = ii;
- ++ii;
- erase(next);
- }
- std::cerr << "Removed " << counter << " scalars in clear_scalars\n";
- }
-
- void clear() {
- ValueMap.clear();
- GlobalSet.clear();
- }
-
- /// spliceFrom - Copy all entries from RHS, then clear RHS.
- ///
- void spliceFrom(DSScalarMap &RHS);
-
- // Access to the global set: the set of all globals currently in the
- // scalar map.
- typedef GlobalSetTy::const_iterator global_iterator;
- global_iterator global_begin() const { return GlobalSet.begin(); }
- global_iterator global_end() const { return GlobalSet.end(); }
- unsigned global_size() const { return GlobalSet.size(); }
- unsigned global_count(const GlobalValue *GV) const { return GlobalSet.count(GV); }
-private:
- DSNodeHandle &AddGlobal(const GlobalValue *GV);
-};
-
-//===----------------------------------------------------------------------===//
-/// DSGraph - The graph that represents a function.
-///
-class DSGraph {
-public:
- // Public data-type declarations...
- typedef DSScalarMap ScalarMapTy;
- typedef hash_map<const Function*, DSNodeHandle> ReturnNodesTy;
- typedef ilist<DSNode> NodeListTy;
-
- /// NodeMapTy - This data type is used when cloning one graph into another to
- /// keep track of the correspondence between the nodes in the old and new
- /// graphs.
- typedef hash_map<const DSNode*, DSNodeHandle> NodeMapTy;
-
- // InvNodeMapTy - This data type is used to represent the inverse of a node
- // map.
- typedef hash_multimap<DSNodeHandle, const DSNode*> InvNodeMapTy;
-private:
- DSGraph *GlobalsGraph; // Pointer to the common graph of global objects
- bool UseAuxCalls; // Should this graph print the Aux calls vector?
-
- NodeListTy Nodes;
- ScalarMapTy ScalarMap;
-
- // ReturnNodes - A return value for every function merged into this graph.
- // Each DSGraph may have multiple functions merged into it at any time, which
- // is used for representing SCCs.
- //
- ReturnNodesTy ReturnNodes;
-
- // FunctionCalls - This list maintains a single entry for each call
- // instruction in the current graph. The first entry in the vector is the
- // scalar that holds the return value for the call, the second is the function
- // scalar being invoked, and the rest are pointer arguments to the function.
- // This vector is built by the Local graph and is never modified after that.
- //
- std::list<DSCallSite> FunctionCalls;
-
- // AuxFunctionCalls - This vector contains call sites that have been processed
- // by some mechanism. In pratice, the BU Analysis uses this vector to hold
- // the _unresolved_ call sites, because it cannot modify FunctionCalls.
- //
- std::list<DSCallSite> AuxFunctionCalls;
-
- /// TD - This is the target data object for the machine this graph is
- /// constructed for.
- const DataLayout &TD;
-
- void operator=(const DSGraph &); // DO NOT IMPLEMENT
- DSGraph(const DSGraph&); // DO NOT IMPLEMENT
-public:
- // Create a new, empty, DSGraph.
- DSGraph(EquivalenceClasses<const GlobalValue*> &ECs, const DataLayout &td,
- DSGraph *GG)
- :GlobalsGraph(GG), UseAuxCalls(false),
- ScalarMap(ECs), TD(td)
- { }
-
- // Copy ctor - If you want to capture the node mapping between the source and
- // destination graph, you may optionally do this by specifying a map to record
- // this into.
- //
- // Note that a copied graph does not retain the GlobalsGraph pointer of the
- // source. You need to set a new GlobalsGraph with the setGlobalsGraph
- // method.
- //
- DSGraph( DSGraph* DSG, EquivalenceClasses<const GlobalValue*> &ECs,
- DSGraph *GG, unsigned CloneFlags);
- ~DSGraph();
-
- DSGraph *getGlobalsGraph() const { return GlobalsGraph; }
-
- /// getGlobalECs - Return the set of equivalence classes that the global
- /// variables in the program form.
- EquivalenceClasses<const GlobalValue*> &getGlobalECs() const {
- return ScalarMap.getGlobalECs();
- }
-
- /// getDataLayout - Return the DataLayout object for the current target.
- ///
- const DataLayout &getDataLayout() const { return TD; }
-
- /// setUseAuxCalls - If you call this method, the auxillary call vector will
- /// be printed instead of the standard call vector to the dot file.
- ///
- void setUseAuxCalls() { UseAuxCalls = true; }
- bool shouldUseAuxCalls() const { return UseAuxCalls; }
-
- /// node_iterator/begin/end - Iterate over all of the nodes in the graph. Be
- /// extremely careful with these methods because any merging of nodes could
- /// cause the node to be removed from this list. This means that if you are
- /// iterating over nodes and doing something that could cause _any_ node to
- /// merge, your node_iterators into this graph can be invalidated.
- typedef NodeListTy::iterator node_iterator;
- node_iterator node_begin() { return Nodes.begin(); }
- node_iterator node_end() { return Nodes.end(); }
-
- typedef NodeListTy::const_iterator node_const_iterator;
- node_const_iterator node_begin() const { return Nodes.begin(); }
- node_const_iterator node_end() const { return Nodes.end(); }
-
- /// getFunctionNames - Return a space separated list of the name of the
- /// functions in this graph (if any)
- ///
- std::string getFunctionNames() const;
-
- /// addNode - Add a new node to the graph.
- ///
- void addNode(DSNode *N) { Nodes.push_back(N); }
- void unlinkNode(DSNode *N) { Nodes.remove(N); }
-
- /// getScalarMap - Get a map that describes what the nodes the scalars in this
- /// function point to...
- ///
- ScalarMapTy &getScalarMap() { return ScalarMap; }
- const ScalarMapTy &getScalarMap() const { return ScalarMap; }
-
- /// getFunctionCalls - Return the list of call sites in the original local
- /// graph...
- ///
- const std::list<DSCallSite> &getFunctionCalls() const { return FunctionCalls;}
- std::list<DSCallSite> &getFunctionCalls() { return FunctionCalls;}
-
- /// getAuxFunctionCalls - Get the call sites as modified by whatever passes
- /// have been run.
- ///
- std::list<DSCallSite> &getAuxFunctionCalls() { return AuxFunctionCalls; }
- const std::list<DSCallSite> &getAuxFunctionCalls() const {
- return AuxFunctionCalls;
- }
-
- // addAuxFunctionCall - Add a call site to the AuxFunctionCallList
- void addAuxFunctionCall(DSCallSite D) { AuxFunctionCalls.push_front(D); }
-
-
- /// removeFunction - Specify that all call sites to the function have been
- /// fully specified by a pass such as StdLibPass.
- void removeFunctionCalls(Function& F);
-
- // Function Call iteration
- typedef std::list<DSCallSite>::const_iterator fc_iterator;
- fc_iterator fc_begin() const { return FunctionCalls.begin(); }
- fc_iterator fc_end() const { return FunctionCalls.end(); }
-
-
- // Aux Function Call iteration
- typedef std::list<DSCallSite>::iterator afc_iterator;
- afc_iterator afc_begin() { return AuxFunctionCalls.begin(); }
- afc_iterator afc_end() { return AuxFunctionCalls.end(); }
- typedef std::list<DSCallSite>::const_iterator afc_const_iterator;
- afc_const_iterator afc_begin() const { return AuxFunctionCalls.begin(); }
- afc_const_iterator afc_end() const { return AuxFunctionCalls.end(); }
-
- /// getNodeForValue - Given a value that is used or defined in the body of the
- /// current function, return the DSNode that it points to.
- ///
- DSNodeHandle &getNodeForValue(const Value *V) { return ScalarMap[V]; }
-
- const DSNodeHandle &getNodeForValue(const Value *V) const {
- ScalarMapTy::const_iterator I = ScalarMap.find(V);
- assert(I != ScalarMap.end() &&
- "Use non-const lookup function if node may not be in the map");
- return I->second;
- }
-
- bool hasNodeForValue(const Value* V) const {
- ScalarMapTy::const_iterator I = ScalarMap.find(V);
- return I != ScalarMap.end();
- }
-
- void eraseNodeForValue(const Value* V) {
- ScalarMap.erase(V);
- }
-
- /// retnodes_* iterator methods: expose iteration over return nodes in the
- /// graph, which are also the set of functions incorporated in this graph.
- typedef ReturnNodesTy::const_iterator retnodes_iterator;
- retnodes_iterator retnodes_begin() const { return ReturnNodes.begin(); }
- retnodes_iterator retnodes_end() const { return ReturnNodes.end(); }
-
-
- /// getReturnNodes - Return the mapping of functions to their return nodes for
- /// this graph.
- ///
- const ReturnNodesTy &getReturnNodes() const { return ReturnNodes; }
- ReturnNodesTy &getReturnNodes() { return ReturnNodes; }
-
- /// getReturnNodeFor - Return the return node for the specified function.
- ///
- DSNodeHandle &getReturnNodeFor(const Function &F) {
- ReturnNodesTy::iterator I = ReturnNodes.find(&F);
- assert(I != ReturnNodes.end() && "F not in this DSGraph!");
- return I->second;
- }
-
- const DSNodeHandle &getReturnNodeFor(const Function &F) const {
- ReturnNodesTy::const_iterator I = ReturnNodes.find(&F);
- assert(I != ReturnNodes.end() && "F not in this DSGraph!");
- return I->second;
- }
-
- DSNodeHandle& getOrCreateReturnNodeFor(const Function& F) {
- return ReturnNodes[&F];
- }
-
- /// containsFunction - Return true if this DSGraph contains information for
- /// the specified function.
- bool containsFunction(const Function *F) const {
- return ReturnNodes.count(F);
- }
-
- /// getGraphSize - Return the number of nodes in this graph.
- ///
- unsigned getGraphSize() const {
- return Nodes.size();
- }
-
- /// addObjectToGraph - This method can be used to add global, stack, and heap
- /// objects to the graph. This can be used when updating DSGraphs due to the
- /// introduction of new temporary objects. The new object is not pointed to
- /// and does not point to any other objects in the graph. Note that this
- /// method initializes the type of the DSNode to the declared type of the
- /// object if UseDeclaredType is true, otherwise it leaves the node type as
- /// void.
- DSNode *addObjectToGraph(Value *Ptr, bool UseDeclaredType = true);
-
-
- /// print - Print a dot graph to the specified ostream...
- ///
- void print(OStream &O) const {
- if (O.stream()) print(*O.stream());
- }
- void print(std::ostream &O) const;
-
- /// dump - call print(cerr), for use from the debugger...
- ///
- void dump() const;
-
- /// viewGraph - Emit a dot graph, run 'dot', run gv on the postscript file,
- /// then cleanup. For use from the debugger.
- ///
- void viewGraph() const;
-
- void writeGraphToFile(std::ostream &O, const std::string &GraphName) const;
-
- /// maskNodeTypes - Apply a mask to all of the node types in the graph. This
- /// is useful for clearing out markers like Incomplete.
- ///
- void maskNodeTypes(unsigned Mask) {
- for (node_iterator I = node_begin(), E = node_end(); I != E; ++I)
- I->NodeType.maskFlags(Mask);
- }
- void maskIncompleteMarkers() { maskNodeTypes(~DSFlags::IncompleteNode); }
-
- // markIncompleteNodes - Traverse the graph, identifying nodes that may be
- // modified by other functions that have not been resolved yet. This marks
- // nodes that are reachable through three sources of "unknownness":
- // Global Variables, Function Calls, and Incoming Arguments
- //
- // For any node that may have unknown components (because something outside
- // the scope of current analysis may have modified it), the 'Incomplete' flag
- // is added to the NodeType.
- //
- enum MarkIncompleteFlags {
- MarkFormalArgs = 1, IgnoreFormalArgs = 0,
- IgnoreGlobals = 2, MarkGlobalsIncomplete = 0,
- MarkVAStart = 4
- };
- void markIncompleteNodes(unsigned Flags);
-
- // removeDeadNodes - Use a reachability analysis to eliminate subgraphs that
- // are unreachable. This often occurs because the data structure doesn't
- // "escape" into it's caller, and thus should be eliminated from the caller's
- // graph entirely. This is only appropriate to use when inlining graphs.
- //
- enum RemoveDeadNodesFlags {
- RemoveUnreachableGlobals = 1, KeepUnreachableGlobals = 0
- };
- void removeDeadNodes(unsigned Flags);
-
- /// CloneFlags enum - Bits that may be passed into the cloneInto method to
- /// specify how to clone the function graph.
- enum CloneFlags {
- StripAllocaBit = 1 << 0, KeepAllocaBit = 0,
- DontCloneCallNodes = 1 << 1, CloneCallNodes = 0,
- DontCloneAuxCallNodes = 1 << 2, CloneAuxCallNodes = 0,
- StripModRefBits = 1 << 3, KeepModRefBits = 0,
- StripIncompleteBit = 1 << 4, KeepIncompleteBit = 0
- };
-
- void updateFromGlobalGraph();
-
- /// computeNodeMapping - Given roots in two different DSGraphs, traverse the
- /// nodes reachable from the two graphs, computing the mapping of nodes from
- /// the first to the second graph.
- ///
- static void computeNodeMapping(const DSNodeHandle &NH1,
- const DSNodeHandle &NH2, NodeMapTy &NodeMap,
- bool StrictChecking = true);
-
- /// computeGToGGMapping - Compute the mapping of nodes in the graph to nodes
- /// in the globals graph.
- void computeGToGGMapping(NodeMapTy &NodeMap);
-
- /// computeGGToGMapping - Compute the mapping of nodes in the global
- /// graph to nodes in this graph.
- void computeGGToGMapping(InvNodeMapTy &InvNodeMap);
-
- /// computeCalleeCallerMapping - Given a call from a function in the current
- /// graph to the 'Callee' function (which lives in 'CalleeGraph'), compute the
- /// mapping of nodes from the callee to nodes in the caller.
- void computeCalleeCallerMapping(DSCallSite CS, const Function &Callee,
- DSGraph &CalleeGraph, NodeMapTy &NodeMap);
-
- /// spliceFrom - Logically perform the operation of cloning the RHS graph into
- /// this graph, then clearing the RHS graph. Instead of performing this as
- /// two seperate operations, do it as a single, much faster, one.
- ///
- void spliceFrom(DSGraph* RHS);
-
- /// cloneInto - Clone the specified DSGraph into the current graph.
- ///
- /// The CloneFlags member controls various aspects of the cloning process.
- ///
- void cloneInto(DSGraph* G, unsigned CloneFlags = 0);
-
- /// getFunctionArgumentsForCall - Given a function that is currently in this
- /// graph, return the DSNodeHandles that correspond to the pointer-compatible
- /// function arguments. The vector is filled in with the return value (or
- /// null if it is not pointer compatible), followed by all of the
- /// pointer-compatible arguments.
- void getFunctionArgumentsForCall(const Function *F,
- std::vector<DSNodeHandle> &Args) const;
-
- /// mergeInGraph - This graph merges in the minimal number of
- /// nodes from G2 into 'this' graph, merging the bindings specified by the
- /// call site (in this graph) with the bindings specified by the vector in G2.
- /// If the StripAlloca's argument is 'StripAllocaBit' then Alloca markers are
- /// removed from nodes.
- ///
- void mergeInGraph(const DSCallSite &CS, std::vector<DSNodeHandle> &Args,
- const DSGraph &G2, unsigned CloneFlags);
-
- /// mergeInGraph - This method is the same as the above method, but the
- /// argument bindings are provided by using the formal arguments of F.
- ///
- void mergeInGraph(const DSCallSite &CS, const Function &F,
- const DSGraph &Graph, unsigned CloneFlags);
-
- /// getCallSiteForArguments - Get the arguments and return value bindings for
- /// the specified function in the current graph.
- ///
- DSCallSite getCallSiteForArguments(const Function &F) const;
-
- /// getDSCallSiteForCallSite - Given an LLVM CallSite object that is live in
- /// the context of this graph, return the DSCallSite for it.
- DSCallSite getDSCallSiteForCallSite(CallSite CS) const;
-
- // Methods for checking to make sure graphs are well formed...
- void AssertNodeInGraph(const DSNode *N) const {
- assert((!N || N->getParentGraph() == this) &&
- "AssertNodeInGraph: Node is not in graph!");
- }
- void AssertNodeContainsGlobal(const DSNode *N, const GlobalValue *GV) const;
-
- void AssertCallSiteInGraph(const DSCallSite &CS) const;
- void AssertCallNodesInGraph() const;
- void AssertAuxCallNodesInGraph() const;
-
- void AssertGraphOK() const;
-
- /// removeTriviallyDeadNodes - After the graph has been constructed, this
- /// method removes all unreachable nodes that are created because they got
- /// merged with other nodes in the graph. This is used as the first step of
- /// removeDeadNodes.
- ///
- void removeTriviallyDeadNodes(bool updateForwarders = false);
-};
-
-
-/// ReachabilityCloner - This class is used to incrementally clone and merge
-/// nodes from a non-changing source graph into a potentially mutating
-/// destination graph. Nodes are only cloned over on demand, either in
-/// responds to a merge() or getClonedNH() call. When a node is cloned over,
-/// all of the nodes reachable from it are automatically brought over as well.
-///
-class ReachabilityCloner {
- DSGraph* Dest;
- const DSGraph* Src;
-
- /// BitsToKeep - These bits are retained from the source node when the
- /// source nodes are merged into the destination graph.
- unsigned BitsToKeep;
- unsigned CloneFlags;
-
- // NodeMap - A mapping from nodes in the source graph to the nodes that
- // represent them in the destination graph.
- DSGraph::NodeMapTy NodeMap;
-public:
- ReachabilityCloner(DSGraph* dest, const DSGraph* src, unsigned cloneFlags)
- : Dest(dest), Src(src), CloneFlags(cloneFlags) {
- assert(Dest != Src && "Cannot clone from graph to same graph!");
- BitsToKeep = ~DSFlags::DeadNode;
- if (CloneFlags & DSGraph::StripAllocaBit)
- BitsToKeep &= ~DSFlags::AllocaNode;
- if (CloneFlags & DSGraph::StripModRefBits)
- BitsToKeep &= ~(DSFlags::ModifiedNode | DSFlags::ReadNode);
- if (CloneFlags & DSGraph::StripIncompleteBit)
- BitsToKeep &= ~DSFlags::IncompleteNode;
- }
-
- DSNodeHandle getClonedNH(const DSNodeHandle &SrcNH);
-
- void merge(const DSNodeHandle &NH, const DSNodeHandle &SrcNH);
-
- /// mergeCallSite - Merge the nodes reachable from the specified src call
- /// site into the nodes reachable from DestCS.
- ///
- void mergeCallSite(DSCallSite &DestCS, const DSCallSite &SrcCS);
-
- DSCallSite cloneCallSite(const DSCallSite& SrcCS);
-
- bool clonedAnyNodes() const { return !NodeMap.empty(); }
-
- /// hasClonedNode - Return true if the specified node has been cloned from
- /// the source graph into the destination graph.
- bool hasClonedNode(const DSNode *N) {
- return NodeMap.count(N);
- }
-
- void destroy() { NodeMap.clear(); }
-};
-
-} // End llvm namespace
-
-#endif
diff --git a/poolalloc/include/rdsa/DSGraphTraits.h b/poolalloc/include/rdsa/DSGraphTraits.h
deleted file mode 100644
index 7c6f045..0000000
--- a/poolalloc/include/rdsa/DSGraphTraits.h
+++ /dev/null
@@ -1,152 +0,0 @@
-//===- DSGraphTraits.h - Provide generic graph interface --------*- 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.
-//
-//===----------------------------------------------------------------------===//
-//
-// This file provides GraphTraits specializations for the DataStructure graph
-// nodes, allowing datastructure graphs to be processed by generic graph
-// algorithms.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_ANALYSIS_DSGRAPHTRAITS_H
-#define LLVM_ANALYSIS_DSGRAPHTRAITS_H
-
-#include "rdsa/DSGraph.h"
-#include "llvm/ADT/GraphTraits.h"
-#include "llvm/ADT/iterator.h"
-#include "llvm/ADT/STLExtras.h"
-
-namespace llvm {
-
-template<typename NodeTy>
-class DSNodeIterator : public forward_iterator<const DSNode, ptrdiff_t> {
- friend class DSNode;
- NodeTy * const Node;
- unsigned Offset;
-
- typedef DSNodeIterator<NodeTy> _Self;
-
- DSNodeIterator(NodeTy *N) : Node(N), Offset(0) {} // begin iterator
- DSNodeIterator(NodeTy *N, bool) : Node(N) { // Create end iterator
- if (N != 0) {
- Offset = N->getNumLinks();
- if (Offset == 0 && Node->getForwardNode() &&
- Node->NodeType.isDeadNode()) // Model Forward link
- Offset += 1;
- } else {
- Offset = 0;
- }
- }
-public:
- DSNodeIterator(const DSNodeHandle &NH)
- : Node(NH.getNode()), Offset(NH.getOffset()) {}
-
- bool operator==(const _Self& x) const {
- return Offset == x.Offset;
- }
- bool operator!=(const _Self& x) const { return !operator==(x); }
-
- const _Self &operator=(const _Self &I) {
- assert(I.Node == Node && "Cannot assign iterators to two different nodes!");
- Offset = I.Offset;
- return *this;
- }
-
- pointer operator*() const {
- if (Node->NodeType.isDeadNode())
- return Node->getForwardNode();
- else
- return Node->getLink(Offset).getNode();
- }
- pointer operator->() const { return operator*(); }
-
- _Self& operator++() { // Preincrement
- Offset += 1;
- return *this;
- }
- _Self operator++(int) { // Postincrement
- _Self tmp = *this; ++*this; return tmp;
- }
-
- unsigned getOffset() const { return Offset; }
- const DSNode *getNode() const { return Node; }
-};
-
-// Provide iterators for DSNode...
-inline DSNode::iterator DSNode::begin() {
- return DSNode::iterator(this);
-}
-inline DSNode::iterator DSNode::end() {
- return DSNode::iterator(this, false);
-}
-inline DSNode::const_iterator DSNode::begin() const {
- return DSNode::const_iterator(this);
-}
-inline DSNode::const_iterator DSNode::end() const {
- return DSNode::const_iterator(this, false);
-}
-
-template <> struct GraphTraits<DSNode*> {
- typedef DSNode NodeType;
- typedef DSNode::iterator ChildIteratorType;
-
- static NodeType *getEntryNode(NodeType *N) { return N; }
- static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
- static ChildIteratorType child_end(NodeType *N) { return N->end(); }
-};
-
-template <> struct GraphTraits<const DSNode*> {
- typedef const DSNode NodeType;
- typedef DSNode::const_iterator ChildIteratorType;
-
- static NodeType *getEntryNode(NodeType *N) { return N; }
- static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
- static ChildIteratorType child_end(NodeType *N) { return N->end(); }
-};
-
-static DSNode &dereference ( DSNode *N) { return *N; }
-
-template <> struct GraphTraits<DSGraph*> {
- typedef DSNode NodeType;
- typedef DSNode::iterator ChildIteratorType;
-
- typedef std::pointer_to_unary_function<DSNode *, DSNode&> DerefFun;
-
- // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
- typedef mapped_iterator<DSGraph::node_iterator, DerefFun> nodes_iterator;
- static nodes_iterator nodes_begin(DSGraph *G) {
- return map_iterator(G->node_begin(), DerefFun(dereference));
- }
- static nodes_iterator nodes_end(DSGraph *G) {
- return map_iterator(G->node_end(), DerefFun(dereference));
- }
-
- static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
- static ChildIteratorType child_end(NodeType *N) { return N->end(); }
-};
-
-template <> struct GraphTraits<const DSGraph*> {
- typedef const DSNode NodeType;
- typedef DSNode::const_iterator ChildIteratorType;
-
- // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
- typedef DSGraph::node_const_iterator nodes_iterator;
- static nodes_iterator nodes_begin(const DSGraph *G) {
- return G->node_begin();
- }
- static nodes_iterator nodes_end(const DSGraph *G) {
- return G->node_end();
- }
-
- static ChildIteratorType child_begin(const NodeType *N) { return N->begin(); }
- static ChildIteratorType child_end(const NodeType *N) { return N->end(); }
-};
-
-} // End llvm namespace
-
-#endif
diff --git a/poolalloc/include/rdsa/DSNode.h b/poolalloc/include/rdsa/DSNode.h
deleted file mode 100644
index dce6827..0000000
--- a/poolalloc/include/rdsa/DSNode.h
+++ /dev/null
@@ -1,473 +0,0 @@
-//===- DSNode.h - Node definition for datastructure 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.
-//
-//===----------------------------------------------------------------------===//
-//
-// Data structure graph nodes and some implementation of DSNodeHandle.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_ANALYSIS_DSNODE_H
-#define LLVM_ANALYSIS_DSNODE_H
-
-#include "rdsa/DSSupport.h"
-#include "rdsa/DSFlags.h"
-#include "llvm/Support/Streams.h"
-#include "poolalloc/ADT/HashExtras.h"
-
-namespace llvm {
-
-template<typename BaseType>
-class DSNodeIterator; // Data structure graph traversal iterator
-class DataLayout;
-
-//===----------------------------------------------------------------------===//
-/// DSNode - Data structure node class
-///
-/// This class represents an untyped memory object of Size bytes. It keeps
-/// track of any pointers that have been stored into the object as well as the
-/// different types represented in this object.
-///
-class DSNode {
- /// NumReferrers - The number of DSNodeHandles pointing to this node... if
- /// this is a forwarding node, then this is the number of node handles which
- /// are still forwarding over us.
- ///
- unsigned NumReferrers;
-
- /// ForwardNH - This NodeHandle contain the node (and offset into the node)
- /// that this node really is. When nodes get folded together, the node to be
- /// eliminated has these fields filled in, otherwise ForwardNH.getNode() is
- /// null.
- ///
- DSNodeHandle ForwardNH;
-
- /// Next, Prev - These instance variables are used to keep the node on a
- /// doubly-linked ilist in the DSGraph.
- ///
- DSNode *Next, *Prev;
- friend struct ilist_traits<DSNode>;
-
- /// Size - The current size of the node. This should be equal to the size of
- /// the current type record.
- ///
- unsigned Size;
-
- /// ParentGraph - The graph this node is currently embedded into.
- ///
- DSGraph *ParentGraph;
-
- /// Ty - Keep track of the current outer most type of this object, in addition
- /// to whether or not it has been indexed like an array or not. If the
- /// isArray bit is set, the node cannot grow.
- ///
- const Type *Ty; // The type itself...
-
- /// Links - Contains one entry for every sizeof(void*) bytes in this memory
- /// object. Note that if the node is not a multiple of size(void*) bytes
- /// large, that there is an extra entry for the "remainder" of the node as
- /// well. For this reason, nodes of 1 byte in size do have one link.
- ///
- std::vector<DSNodeHandle> Links;
-
- void operator=(const DSNode &); // DO NOT IMPLEMENT
- DSNode(const DSNode &); // DO NOT IMPLEMENT
-
- /// Globals - The list of global values that are merged into this node.
- ///
- std::vector<const GlobalValue*> Globals;
-
-public:
- DSFlags NodeType;
-
- /// DSNode ctor - Create a node of the specified type, inserting it into the
- /// specified graph.
- ///
- DSNode(const Type *T, DSGraph *G);
-
- /// DSNode "copy ctor" - Copy the specified node, inserting it into the
- /// specified graph. If NullLinks is true, then null out all of the links,
- /// but keep the same number of them. This can be used for efficiency if the
- /// links are just going to be clobbered anyway.
- ///
- DSNode(const DSNode &, DSGraph *G, bool NullLinks = false);
-
-#if 0
- ~DSNode() {
- dropAllReferences();
- assert(hasNoReferrers() && "Referrers to dead node exist!");
- }
-#else
- ~DSNode();
-#endif
-
- // Iterator for graph interface... Defined in DSGraphTraits.h
- typedef DSNodeIterator<DSNode> iterator;
- typedef DSNodeIterator<const DSNode> const_iterator;
- inline iterator begin();
- inline iterator end();
- inline const_iterator begin() const;
- inline const_iterator end() const;
-
- //===--------------------------------------------------
- // Accessors
-
- /// getSize - Return the maximum number of bytes occupied by this object...
- ///
- unsigned getSize() const { return Size; }
-
- /// getType - Return the node type of this object...
- ///
- const Type *getType() const { return Ty; }
-
- /// hasNoReferrers - Return true if nothing is pointing to this node at all.
- ///
- bool hasNoReferrers() const { return getNumReferrers() == 0; }
-
- /// getNumReferrers - This method returns the number of referrers to the
- /// current node. Note that if this node is a forwarding node, this will
- /// return the number of nodes forwarding over the node!
- unsigned getNumReferrers() const { return NumReferrers; }
-
- DSGraph *getParentGraph() const { return ParentGraph; }
- void setParentGraph(DSGraph *G) { ParentGraph = G; }
-
-
- /// getDataLayout - Get the target data object used to construct this node.
- ///
- const DataLayout &getDataLayout() const;
-
- /// getForwardNode - This method returns the node that this node is forwarded
- /// to, if any.
- ///
- DSNode *getForwardNode() const { return ForwardNH.getNode(); }
-
- /// isForwarding - Return true if this node is forwarding to another.
- ///
- bool isForwarding() const { return !ForwardNH.isNull(); }
-
- /// stopForwarding - When the last reference to this forwarding node has been
- /// dropped, delete the node.
- ///
- void stopForwarding() {
- assert(isForwarding() &&
- "Node isn't forwarding, cannot stopForwarding()!");
- ForwardNH.setTo(0, 0);
- assert(ParentGraph == 0 &&
- "Forwarding nodes must have been removed from graph!");
- delete this;
- }
-
- /// hasLink - Return true if this memory object has a link in slot LinkNo
- ///
- bool hasLink(unsigned Offset) const {
- unsigned Index = Offset;
- assert(Index < Links.size() && "Link index is out of range!");
- return Links[Index].getNode();
- }
-
- /// getLink - Return the link at the specified offset.
- ///
- DSNodeHandle &getLink(unsigned Offset) {
- unsigned Index = Offset;
- assert(Index < Links.size() && "Link index is out of range!");
- return Links[Index];
- }
- const DSNodeHandle &getLink(unsigned Offset) const {
- unsigned Index = Offset;
- assert(Index < Links.size() && "Link index is out of range!");
- return Links[Index];
- }
-
- /// getNumLinks - Return the number of links in a node...
- ///
- unsigned getNumLinks() const { return Links.size(); }
-
- /// edge_* - Provide iterators for accessing outgoing edges. Some outgoing
- /// edges may be null.
- typedef std::vector<DSNodeHandle>::iterator edge_iterator;
- typedef std::vector<DSNodeHandle>::const_iterator const_edge_iterator;
- edge_iterator edge_begin() { return Links.begin(); }
- edge_iterator edge_end() { return Links.end(); }
- const_edge_iterator edge_begin() const { return Links.begin(); }
- const_edge_iterator edge_end() const { return Links.end(); }
-
-
- /// mergeTypeInfo - This method merges the specified type into the current
- /// node at the specified offset. This may update the current node's type
- /// record if this gives more information to the node, it may do nothing to
- /// the node if this information is already known, or it may merge the node
- /// completely (and return true) if the information is incompatible with what
- /// is already known.
- ///
- /// This method returns true if the node is completely folded, otherwise
- /// false.
- ///
- bool mergeTypeInfo(const Type *Ty, unsigned Offset,
- bool FoldIfIncompatible = true);
-
- /// foldNodeCompletely - If we determine that this node has some funny
- /// behavior happening to it that we cannot represent, we fold it down to a
- /// single, completely pessimistic, node. This node is represented as a
- /// single byte with a single TypeEntry of "void" with isArray = true.
- ///
- void foldNodeCompletely();
-
- /// isNodeCompletelyFolded - Return true if this node has been completely
- /// folded down to something that can never be expanded, effectively losing
- /// all of the field sensitivity that may be present in the node.
- ///
- bool isNodeCompletelyFolded() const;
-
- /// setLink - Set the link at the specified offset to the specified
- /// NodeHandle, replacing what was there. It is uncommon to use this method,
- /// instead one of the higher level methods should be used, below.
- ///
- void setLink(unsigned Offset, const DSNodeHandle &NH) {
- unsigned Index = Offset;
- assert(Index < Links.size() && "Link index is out of range!");
- Links[Index] = NH;
- }
-
- /// addEdgeTo - Add an edge from the current node to the specified node. This
- /// can cause merging of nodes in the graph.
- ///
- void addEdgeTo(unsigned Offset, const DSNodeHandle &NH);
-
- /// mergeWith - Merge this node and the specified node, moving all links to
- /// and from the argument node into the current node, deleting the node
- /// argument. Offset indicates what offset the specified node is to be merged
- /// into the current node.
- ///
- /// The specified node may be a null pointer (in which case, nothing happens).
- ///
- void mergeWith(const DSNodeHandle &NH, unsigned Offset);
-
- /// addGlobal - Add an entry for a global value to the Globals list.
- /// This also marks the node with the 'G' flag if it does not
- /// already have it.
- ///
- void addGlobal(const GlobalValue *GV);
-
- /// addFunction - Add an entry for a function value to the
- /// Functionss list. This also marks the node with the 'F' flag if
- /// it does not already have it.
- ///
- void addFunction(const Function* FV);
-
- /// removeGlobal - Remove the specified global that is explicitly in the
- /// globals list.
- void removeGlobal(const GlobalValue *GV);
-
- void mergeGlobals(const DSNode& RHS);
- void clearGlobals() { Globals.clear(); }
-
- bool isEmptyGlobals() const { return Globals.empty(); }
- unsigned numGlobals() const { return Globals.size(); }
-
- /// addFullGlobalsList - Compute the full set of global values that are
- /// represented by this node. Unlike getGlobalsList(), this requires fair
- /// amount of work to compute, so don't treat this method call as free.
- void addFullGlobalsList(std::vector<const GlobalValue*> &List) const;
-
- /// addFullFunctionList - Identical to addFullGlobalsList, but only return the
- /// functions in the full list.
- void addFullFunctionList(std::vector<const Function*> &List) const;
-
- /// globals_iterator/begin/end - Provide iteration methods over the global
- /// value leaders set that is merged into this node. Like the getGlobalsList
- /// method, these iterators do not return globals that are part of the
- /// equivalence classes for globals in this node, but aren't leaders.
- typedef std::vector<const GlobalValue*>::const_iterator globals_iterator;
- globals_iterator globals_begin() const { return Globals.begin(); }
- globals_iterator globals_end() const { return Globals.end(); }
-
- /// getNodeFlags - Return all of the flags set on the node. If the DEAD flag
- /// is set, hide it from the caller.
- ///
- unsigned getNodeFlags() const { return NodeType.getFlags() & ~DSFlags::DeadNode; }
-
- void makeNodeDead() {
- Globals.clear();
- assert(hasNoReferrers() && "Dead node shouldn't have refs!");
- NodeType.setDeadNode();
- }
-
- /// forwardNode - Mark this node as being obsolete, and all references to it
- /// should be forwarded to the specified node and offset.
- ///
- void forwardNode(DSNode *To, unsigned Offset);
-
- void print(OStream &O, const DSGraph *G) const {
- if (O.stream()) print(*O.stream(), G);
- }
- void print(std::ostream &O, const DSGraph *G) const;
- void dump() const;
-
- void assertOK() const;
-
- void dropAllReferences() {
- Links.clear();
- if (isForwarding())
- ForwardNH.setTo(0, 0);
- }
-
- /// remapLinks - Change all of the Links in the current node according to the
- /// specified mapping.
- ///
- void remapLinks(hash_map<const DSNode*, DSNodeHandle> &OldNodeMap);
-
- /// markReachableNodes - This method recursively traverses the specified
- /// DSNodes, marking any nodes which are reachable. All reachable nodes it
- /// adds to the set, which allows it to only traverse visited nodes once.
- ///
- void markReachableNodes(hash_set<const DSNode*> &ReachableNodes) const;
-
-private:
- friend class DSNodeHandle;
-
- // static mergeNodes - Helper for mergeWith()
- static void MergeNodes(DSNodeHandle& CurNodeH, DSNodeHandle& NH);
-};
-
-//===----------------------------------------------------------------------===//
-// Define the ilist_traits specialization for the DSGraph ilist.
-//
-template<>
-struct ilist_traits<DSNode> {
- static DSNode *getPrev(const DSNode *N) { return N->Prev; }
- static DSNode *getNext(const DSNode *N) { return N->Next; }
-
- static void deleteNode(llvm::DSNode *V) { delete V; }
- static void setPrev(DSNode *N, DSNode *Prev) { N->Prev = Prev; }
- static void setNext(DSNode *N, DSNode *Next) { N->Next = Next; }
-
- static DSNode *createSentinel() { return new DSNode(0,0); }
- static void destroySentinel(DSNode *N) { delete N; }
-
- void addNodeToList(DSNode *NTy) {}
- void removeNodeFromList(DSNode *NTy) {}
- void transferNodesFromList(iplist<DSNode, ilist_traits> &L2,
- ilist_iterator<DSNode> first,
- ilist_iterator<DSNode> last) {}
- DSNode *provideInitialHead() const {
- DSNode * sentinel = createSentinel();
- setPrev (sentinel, sentinel);
- return sentinel;
- }
-
- /// ensureHead - make sure that Head is either already
- /// initialized or assigned a fresh sentinel
- /// @return the sentinel
- static DSNode *ensureHead(DSNode *&Head) {
- if (!Head) {
- Head = createSentinel();
- noteHead (Head, Head);
- setNext(Head, Head);
- return Head;
- }
- return getPrev(Head);
- }
-
- /// noteHead - stash the sentinel into its default location
- static void noteHead(DSNode *NewHead, DSNode *Sentinel) {
- setPrev(NewHead, Sentinel);
- }
-};
-
-template<>
-struct ilist_traits<const DSNode> : public ilist_traits<DSNode> {};
-
-//===----------------------------------------------------------------------===//
-// Define inline DSNodeHandle functions that depend on the definition of DSNode
-//
-inline DSNode *DSNodeHandle::getNode() const {
- // Disabling this assertion because it is failing on a "magic" struct
- // in named (from bind). The fourth field is an array of length 0,
- // presumably used to create struct instances of different sizes.
- // In a variable length struct, Offset could exceed Size when getNode()
- // is called before such a node is folded. In this case, the DS Analysis now
- // correctly folds this node after calling getNode.
- /* assert((!N ||
- N->isNodeCompletelyFolded() ||
- (N->Size == 0 && Offset == 0) ||
- (int(Offset) >= 0 && Offset < N->Size) ||
- (int(Offset) < 0 && -int(Offset) < int(N->Size)) ||
- N->isForwarding()) && "Node handle offset out of range!");
- */
- if (N == 0 || !N->isForwarding())
- return N;
-
- return HandleForwarding();
-}
-
-inline const DSNodeHandle& DSNodeHandle::setTo(DSNode *n, unsigned NewOffset) const {
- assert((!n || !n->isForwarding()) && "Cannot set node to a forwarded node!");
- if (N) getNode()->NumReferrers--;
- N = n;
- Offset = NewOffset;
- if (N) {
- N->NumReferrers++;
- if (Offset >= N->Size) {
- assert((Offset == 0 || N->Size == 1) &&
- "Pointer to non-collapsed node with invalid offset!");
- Offset = 0;
- }
- }
- assert(!N || !N->NodeType.isDeadNode());
- assert((!N || Offset < N->Size || (N->Size == 0 && Offset == 0) ||
- N->isForwarding()) && "Node handle offset out of range!");
- return *this;
-}
-
-inline bool DSNodeHandle::hasLink(unsigned Num) const {
- assert(N && "DSNodeHandle does not point to a node yet!");
- return getNode()->hasLink(Num+Offset);
-}
-
-
-/// getLink - Treat this current node pointer as a pointer to a structure of
-/// some sort. This method will return the pointer a mem[this+Num]
-///
-inline const DSNodeHandle &DSNodeHandle::getLink(unsigned Off) const {
- assert(N && "DSNodeHandle does not point to a node yet!");
- return getNode()->getLink(Offset+Off);
-}
-inline DSNodeHandle &DSNodeHandle::getLink(unsigned Off) {
- assert(N && "DSNodeHandle does not point to a node yet!");
- return getNode()->getLink(Off+Offset);
-}
-
-inline void DSNodeHandle::setLink(unsigned Off, const DSNodeHandle &NH) {
- assert(N && "DSNodeHandle does not point to a node yet!");
- getNode()->setLink(Off+Offset, NH);
-}
-
-/// addEdgeTo - Add an edge from the current node to the specified node. This
-/// can cause merging of nodes in the graph.
-///
-inline void DSNodeHandle::addEdgeTo(unsigned Off, const DSNodeHandle &Node) {
- assert(N && "DSNodeHandle does not point to a node yet!");
- getNode()->addEdgeTo(Off+Offset, Node);
-}
-
-/// mergeWith - Merge the logical node pointed to by 'this' with the node
-/// pointed to by 'N'.
-///
-inline void DSNodeHandle::mergeWith(const DSNodeHandle &Node) const {
- if (!isNull())
- getNode()->mergeWith(Node, Offset);
- else { // No node to merge with, so just point to Node
- Offset = 0;
- DSNode *NN = Node.getNode();
- setTo(NN, Node.getOffset());
- }
-}
-
-} // End llvm namespace
-
-#endif
diff --git a/poolalloc/include/rdsa/DSSupport.h b/poolalloc/include/rdsa/DSSupport.h
deleted file mode 100644
index 848be46..0000000
--- a/poolalloc/include/rdsa/DSSupport.h
+++ /dev/null
@@ -1,326 +0,0 @@
-//===- DSSupport.h - Support for datastructure 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.
-//
-//===----------------------------------------------------------------------===//
-//
-// Support for graph nodes, call sites, and types.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_ANALYSIS_DSSUPPORT_H
-#define LLVM_ANALYSIS_DSSUPPORT_H
-
-#include <functional>
-#include "llvm/IR/CallSite.h"
-#include "poolalloc/ADT/HashExtras.h"
-
-namespace llvm {
-
-class Function;
-class CallInst;
-class Value;
-class GlobalValue;
-class Type;
-
-class DSNode; // Each node in the graph
-class DSGraph; // A graph for a function
-class ReachabilityCloner;
-
-//===----------------------------------------------------------------------===//
-/// DSNodeHandle - Implement a "handle" to a data structure node that takes care
-/// of all of the add/un'refing of the node to prevent the backpointers in the
-/// graph from getting out of date. This class represents a "pointer" in the
-/// graph, whose destination is an indexed offset into a node.
-///
-/// Note: some functions that are marked as inline in DSNodeHandle are actually
-/// defined in DSNode.h because they need knowledge of DSNode operation. Putting
-/// them in a CPP file wouldn't help making them inlined and keeping DSNode and
-/// DSNodeHandle (and friends) in one file complicates things.
-///
-class DSNodeHandle {
- mutable DSNode *N;
- mutable unsigned Offset;
- void operator==(const DSNode *N); // DISALLOW, use to promote N to nodehandle
-public:
- // Allow construction, destruction, and assignment...
- DSNodeHandle(DSNode *n = 0, unsigned offs = 0) : N(0), Offset(0) {
- setTo(n, offs);
- }
- DSNodeHandle(const DSNodeHandle &H) : N(0), Offset(0) {
- DSNode *NN = H.getNode();
- setTo(NN, H.Offset); // Must read offset AFTER the getNode()
- }
- ~DSNodeHandle() { setTo(0, 0); }
- DSNodeHandle &operator=(const DSNodeHandle &H) {
- if (&H == this) return *this; // Don't set offset to 0 if self assigning.
- DSNode *NN = H.getNode(); // Call getNode() before .Offset
- setTo(NN, H.Offset);
- return *this;
- }
-
- bool operator<(const DSNodeHandle &H) const { // Allow sorting
- return getNode() < H.getNode() || (N == H.N && Offset < H.Offset);
- }
- bool operator>(const DSNodeHandle &H) const { return H < *this; }
- bool operator==(const DSNodeHandle &H) const { // Allow comparison
- // getNode can change the offset, so we must call getNode() first.
- return getNode() == H.getNode() && Offset == H.Offset;
- }
- bool operator!=(const DSNodeHandle &H) const { return !operator==(H); }
-
- inline void swap(DSNodeHandle &NH) {
- std::swap(Offset, NH.Offset);
- std::swap(N, NH.N);
- }
-
- /// isNull - Check to see if getNode() == 0, without going through the trouble
- /// of checking to see if we are forwarding...
- ///
- bool isNull() const { return N == 0; }
-
- // Allow explicit conversion to DSNode...
- DSNode *getNode() const; // Defined inline in DSNode.h
- unsigned getOffset() const {
- assert(!isForwarding() && "This is a forwarding NH, call getNode() first!");
- return Offset;
- }
-
- void setOffset(unsigned O) {
- assert(!isForwarding() && "This is a forwarding NH, call getNode() first!");
- //assert((!N || Offset < N->Size || (N->Size == 0 && Offset == 0) ||
- // !N->ForwardNH.isNull()) && "Node handle offset out of range!");
- //assert((!N || O < N->Size || (N->Size == 0 && O == 0) ||
- // !N->ForwardNH.isNull()) && "Node handle offset out of range!");
- Offset = O;
- }
-
- const DSNodeHandle& setTo(DSNode *N, unsigned O) const; // Defined inline in DSNode.h
-
- void addEdgeTo(unsigned LinkNo, const DSNodeHandle &N);
- void addEdgeTo(const DSNodeHandle &N) { addEdgeTo(0, N); }
-
- /// mergeWith - Merge the logical node pointed to by 'this' with the node
- /// pointed to by 'N'.
- ///
- void mergeWith(const DSNodeHandle &N) const;
-
- /// hasLink - Return true if there is a link at the specified offset...
- ///
- inline bool hasLink(unsigned Num) const;
-
- /// getLink - Treat this current node pointer as a pointer to a structure of
- /// some sort. This method will return the pointer a mem[this+Num]
- ///
- inline const DSNodeHandle &getLink(unsigned Num) const;
- inline DSNodeHandle &getLink(unsigned Num);
-
- inline void setLink(unsigned Num, const DSNodeHandle &NH);
-private:
- DSNode *HandleForwarding() const;
-
- /// isForwarding - Return true if this NodeHandle is forwarding to another
- /// one.
- bool isForwarding() const;
-};
-
-} // End llvm namespace
-
-namespace std {
- template<>
- inline void swap<llvm::DSNodeHandle>(llvm::DSNodeHandle &NH1, llvm::DSNodeHandle &NH2) { NH1.swap(NH2); }
-}
-
-namespace __gnu_cxx {
- // Provide a hash function for arbitrary pointers...
- template <> struct hash<llvm::DSNodeHandle> {
- inline size_t operator()(const llvm::DSNodeHandle &Val) const {
- return hash<void*>()(Val.getNode()) ^ Val.getOffset();
- }
- };
-}
-
-namespace llvm {
-
-//===----------------------------------------------------------------------===//
-/// DSCallSite - Representation of a call site via its call instruction,
-/// the DSNode handle for the callee function (or function pointer), and
-/// the DSNode handles for the function arguments.
-///
-class DSCallSite {
- CallSite Site; // Actual call site
- const Function *CalleeF; // The function called (direct call)
- DSNodeHandle CalleeN; // The function node called (indirect call)
- DSNodeHandle RetVal; // Returned value
- std::vector<DSNodeHandle> CallArgs; // The pointer arguments
-
- static void InitNH(DSNodeHandle &NH, const DSNodeHandle &Src,
- const hash_map<const DSNode*, DSNode*> &NodeMap) {
- if (DSNode *N = Src.getNode()) {
- hash_map<const DSNode*, DSNode*>::const_iterator I = NodeMap.find(N);
- assert(I != NodeMap.end() && "Node not in mapping!");
- NH.setTo(I->second, Src.getOffset());
- }
- }
-
- static void InitNH(DSNodeHandle &NH, const DSNodeHandle &Src,
- const hash_map<const DSNode*, DSNodeHandle> &NodeMap) {
- if (DSNode *N = Src.getNode()) {
- hash_map<const DSNode*, DSNodeHandle>::const_iterator I = NodeMap.find(N);
- assert(I != NodeMap.end() && "Node not in mapping!");
-
- DSNode *NN = I->second.getNode(); // Call getNode before getOffset()
- NH.setTo(NN, Src.getOffset()+I->second.getOffset());
- }
- }
-
- static void InitNH(DSNodeHandle &NH, const DSNodeHandle &Src,
- ReachabilityCloner &RC);
-
-
- DSCallSite(); // DO NOT IMPLEMENT
-public:
- /// Constructor. Note - This ctor destroys the argument vector passed in. On
- /// exit, the argument vector is empty.
- ///
- DSCallSite(CallSite CS, const DSNodeHandle &rv, DSNode *Callee,
- std::vector<DSNodeHandle> &Args)
- : Site(CS), CalleeF(0), CalleeN(Callee), RetVal(rv) {
- assert(Callee && "Null callee node specified for call site!");
- Args.swap(CallArgs);
- }
- DSCallSite(CallSite CS, const DSNodeHandle &rv, const Function *Callee,
- std::vector<DSNodeHandle> &Args)
- : Site(CS), CalleeF(Callee), RetVal(rv) {
- assert(Callee && "Null callee function specified for call site!");
- Args.swap(CallArgs);
- }
-
- DSCallSite(const DSCallSite &DSCS) // Simple copy ctor
- : Site(DSCS.Site), CalleeF(DSCS.CalleeF), CalleeN(DSCS.CalleeN),
- RetVal(DSCS.RetVal), CallArgs(DSCS.CallArgs) {}
-
- /// Mapping copy constructor - This constructor takes a preexisting call site
- /// to copy plus a map that specifies how the links should be transformed.
- /// This is useful when moving a call site from one graph to another.
- ///
- template<typename MapTy>
- DSCallSite(const DSCallSite &FromCall, MapTy &NodeMap) {
- Site = FromCall.Site;
- InitNH(RetVal, FromCall.RetVal, NodeMap);
- InitNH(CalleeN, FromCall.CalleeN, NodeMap);
- CalleeF = FromCall.CalleeF;
-
- CallArgs.resize(FromCall.CallArgs.size());
- for (unsigned i = 0, e = FromCall.CallArgs.size(); i != e; ++i)
- InitNH(CallArgs[i], FromCall.CallArgs[i], NodeMap);
- }
-
- const DSCallSite &operator=(const DSCallSite &RHS) {
- Site = RHS.Site;
- CalleeF = RHS.CalleeF;
- CalleeN = RHS.CalleeN;
- RetVal = RHS.RetVal;
- CallArgs = RHS.CallArgs;
- return *this;
- }
-
- /// isDirectCall - Return true if this call site is a direct call of the
- /// function specified by getCalleeFunc. If not, it is an indirect call to
- /// the node specified by getCalleeNode.
- ///
- bool isDirectCall() const { return CalleeF != 0; }
- bool isIndirectCall() const { return !isDirectCall(); }
-
-
- // Accessor functions...
- const Function &getCaller() const;
- CallSite getCallSite() const { return Site; }
- DSNodeHandle &getRetVal() { return RetVal; }
- const DSNodeHandle &getRetVal() const { return RetVal; }
-
- DSNode *getCalleeNode() const {
- assert(!CalleeF && CalleeN.getNode()); return CalleeN.getNode();
- }
- const Function *getCalleeFunc() const {
- assert(!CalleeN.getNode() && CalleeF); return CalleeF;
- }
-
- unsigned getNumPtrArgs() const { return CallArgs.size(); }
-
- DSNodeHandle &getPtrArg(unsigned i) {
- assert(i < CallArgs.size() && "Argument to getPtrArgNode is out of range!");
- return CallArgs[i];
- }
- const DSNodeHandle &getPtrArg(unsigned i) const {
- assert(i < CallArgs.size() && "Argument to getPtrArgNode is out of range!");
- return CallArgs[i];
- }
-
- void addPtrArg(const DSNodeHandle &NH) {
- CallArgs.push_back(NH);
- }
-
- void swap(DSCallSite &CS) {
- if (this != &CS) {
- std::swap(Site, CS.Site);
- std::swap(RetVal, CS.RetVal);
- std::swap(CalleeN, CS.CalleeN);
- std::swap(CalleeF, CS.CalleeF);
- std::swap(CallArgs, CS.CallArgs);
- }
- }
-
- /// mergeWith - Merge the return value and parameters of the these two call
- /// sites.
- ///
- void mergeWith(DSCallSite &CS) {
- getRetVal().mergeWith(CS.getRetVal());
- unsigned MinArgs = getNumPtrArgs();
- if (CS.getNumPtrArgs() < MinArgs) MinArgs = CS.getNumPtrArgs();
-
- for (unsigned a = 0; a != MinArgs; ++a)
- getPtrArg(a).mergeWith(CS.getPtrArg(a));
-
- for (unsigned a = MinArgs, e = CS.getNumPtrArgs(); a != e; ++a)
- CallArgs.push_back(CS.getPtrArg(a));
- }
-
- /// markReachableNodes - This method recursively traverses the specified
- /// DSNodes, marking any nodes which are reachable. All reachable nodes it
- /// adds to the set, which allows it to only traverse visited nodes once.
- ///
- void markReachableNodes(hash_set<const DSNode*> &Nodes) const;
-
- bool operator<(const DSCallSite &CS) const {
- if (isDirectCall()) { // This must sort by callee first!
- if (CS.isIndirectCall()) return true;
- if (CalleeF < CS.CalleeF) return true;
- if (CalleeF > CS.CalleeF) return false;
- } else {
- if (CS.isDirectCall()) return false;
- if (CalleeN < CS.CalleeN) return true;
- if (CalleeN > CS.CalleeN) return false;
- }
- if (RetVal < CS.RetVal) return true;
- if (RetVal > CS.RetVal) return false;
- return CallArgs < CS.CallArgs;
- }
-
- bool operator==(const DSCallSite &CS) const {
- return CalleeF == CS.CalleeF && CalleeN == CS.CalleeN &&
- RetVal == CS.RetVal && CallArgs == CS.CallArgs;
- }
-};
-
-} // End llvm namespace
-
-namespace std {
- template<>
- inline void swap<llvm::DSCallSite>(llvm::DSCallSite &CS1,
- llvm::DSCallSite &CS2) { CS1.swap(CS2); }
-}
-#endif
diff --git a/poolalloc/include/rdsa/DataStructure.h b/poolalloc/include/rdsa/DataStructure.h
deleted file mode 100644
index 17824fe..0000000
--- a/poolalloc/include/rdsa/DataStructure.h
+++ /dev/null
@@ -1,459 +0,0 @@
-//===- 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/DataLayout.h"
-#include "llvm/IR/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;
-
- /// DataLayout, comes in handy
- DataLayout* 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 useAuxCalls, bool copyGlobalAuxCalls, bool resetAux);
- void init(DataLayout* 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; }
-
- DataLayout& getDataLayout() 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<DataLayoutPass>();
- 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<DataLayout>();
- 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<DataLayout>();
- 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<DataLayout>();
- 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<DataLayout>();
- 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<DataLayout>();
- 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<DataLayoutPass>();
- 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
