diff options
| -rw-r--r-- | llvm/include/llvm/Analysis/DataStructure/DSGraph.h | 448 | ||||
| -rw-r--r-- | llvm/include/llvm/Analysis/DataStructure/DSGraphTraits.h | 155 | ||||
| -rw-r--r-- | llvm/include/llvm/Analysis/DataStructure/DSNode.h | 468 | ||||
| -rw-r--r-- | llvm/include/llvm/Analysis/DataStructure/DSSupport.h | 313 | ||||
| -rw-r--r-- | llvm/include/llvm/Analysis/DataStructure/DataStructure.h | 248 |
5 files changed, 1632 insertions, 0 deletions
diff --git a/llvm/include/llvm/Analysis/DataStructure/DSGraph.h b/llvm/include/llvm/Analysis/DataStructure/DSGraph.h new file mode 100644 index 00000000000..81c12fcad65 --- /dev/null +++ b/llvm/include/llvm/Analysis/DataStructure/DSGraph.h @@ -0,0 +1,448 @@ +//===- 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 "llvm/Analysis/DataStructure/DSNode.h" + +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<Value*, DSNodeHandle> ValueMapTy; + ValueMapTy ValueMap; + + typedef hash_set<GlobalValue*> GlobalSetTy; + GlobalSetTy GlobalSet; +public: + + // 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(); } + iterator find(Value *V) { return ValueMap.find(V); } + const_iterator find(Value *V) const { return ValueMap.find(V); } + unsigned count(Value *V) const { return ValueMap.count(V); } + + void erase(Value *V) { erase(find(V)); } + + /// 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(Value *Old, 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); + } + + DSNodeHandle &operator[](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 (GlobalValue *GV = dyn_cast<GlobalValue>(V)) + GlobalSet.insert(GV); + } + return IP.first->second; + } + + void erase(iterator I) { + assert(I != ValueMap.end() && "Cannot erase end!"); + if (GlobalValue *GV = dyn_cast<GlobalValue>(I->first)) + GlobalSet.erase(GV); + ValueMap.erase(I); + } + + void clear() { + ValueMap.clear(); + GlobalSet.clear(); + } + + // 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(); } +}; + + +//===----------------------------------------------------------------------===// +/// DSGraph - The graph that represents a function. +/// +struct DSGraph { + // Public data-type declarations... + typedef DSScalarMap ScalarMapTy; + typedef hash_map<Function*, DSNodeHandle> ReturnNodesTy; + typedef hash_set<GlobalValue*> GlobalSetTy; + 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; +private: + DSGraph *GlobalsGraph; // Pointer to the common graph of global objects + bool PrintAuxCalls; // 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 vector 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::vector<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::vector<DSCallSite> AuxFunctionCalls; + + // InlinedGlobals - This set records which globals have been inlined from + // other graphs (callers or callees, depending on the pass) into this one. + // + GlobalSetTy InlinedGlobals; + + /// TD - This is the target data object for the machine this graph is + /// constructed for. + const TargetData &TD; + + void operator=(const DSGraph &); // DO NOT IMPLEMENT + +public: + // Create a new, empty, DSGraph. + DSGraph(const TargetData &td) + : GlobalsGraph(0), PrintAuxCalls(false), TD(td) {} + + // Compute the local DSGraph + DSGraph(const TargetData &td, Function &F, DSGraph *GlobalsGraph); + + // 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(const DSGraph &DSG); + DSGraph(const DSGraph &DSG, NodeMapTy &NodeMap); + ~DSGraph(); + + DSGraph *getGlobalsGraph() const { return GlobalsGraph; } + void setGlobalsGraph(DSGraph *G) { GlobalsGraph = G; } + + /// getTargetData - Return the TargetData object for the current target. + /// + const TargetData &getTargetData() const { return TD; } + + /// setPrintAuxCalls - If you call this method, the auxillary call vector will + /// be printed instead of the standard call vector to the dot file. + /// + void setPrintAuxCalls() { PrintAuxCalls = true; } + bool shouldPrintAuxCalls() const { return PrintAuxCalls; } + + /// 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::compat_iterator node_iterator; + node_iterator node_begin() const { return Nodes.compat_begin(); } + node_iterator node_end() const { return Nodes.compat_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::vector<DSCallSite> &getFunctionCalls() const { + return FunctionCalls; + } + + /// getAuxFunctionCalls - Get the call sites as modified by whatever passes + /// have been run. + /// + std::vector<DSCallSite> &getAuxFunctionCalls() { + return AuxFunctionCalls; + } + const std::vector<DSCallSite> &getAuxFunctionCalls() const { + return AuxFunctionCalls; + } + + /// getInlinedGlobals - Get the set of globals that are have been inlined + /// (from callees in BU or from callers in TD) into the current graph. + /// + GlobalSetTy& getInlinedGlobals() { + return InlinedGlobals; + } + + /// 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(Value *V) { return ScalarMap[V]; } + + const DSNodeHandle &getNodeForValue(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; + } + + /// 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(Function &F) { + ReturnNodesTy::iterator I = ReturnNodes.find(&F); + assert(I != ReturnNodes.end() && "F not in this DSGraph!"); + return I->second; + } + + const DSNodeHandle &getReturnNodeFor(Function &F) const { + ReturnNodesTy::const_iterator I = ReturnNodes.find(&F); + assert(I != ReturnNodes.end() && "F not in this DSGraph!"); + return I->second; + } + + /// getGraphSize - Return the number of nodes in this graph. + /// + unsigned getGraphSize() const { + return Nodes.size(); + } + + /// print - Print a dot graph to the specified ostream... + /// + void print(std::ostream &O) const; + + /// dump - call print(std::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)->maskNodeTypes(Mask); + } + void maskIncompleteMarkers() { maskNodeTypes(~DSNode::Incomplete); } + + // 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, + }; + 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, + UpdateInlinedGlobals = 1 << 5, DontUpdateInlinedGlobals = 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); + + + /// cloneInto - Clone the specified DSGraph into the current graph. The + /// translated ScalarMap for the old function is filled into the OldValMap + /// member, and the translated ReturnNodes map is returned into ReturnNodes. + /// OldNodeMap contains a mapping from the original nodes to the newly cloned + /// nodes. + /// + /// The CloneFlags member controls various aspects of the cloning process. + /// + void cloneInto(const DSGraph &G, ScalarMapTy &OldValMap, + ReturnNodesTy &OldReturnNodes, NodeMapTy &OldNodeMap, + unsigned CloneFlags = 0); + + /// mergeInGraph - The method is used for merging graphs together. If the + /// argument graph is not *this, it makes a clone of the specified graph, then + /// merges the nodes specified in the call site with the formal arguments in + /// the graph. If the StripAlloca's argument is 'StripAllocaBit' then Alloca + /// markers are removed from nodes. + /// + void mergeInGraph(const DSCallSite &CS, 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(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, GlobalValue *GV) const { + assert(std::find(N->getGlobals().begin(), N->getGlobals().end(), GV) != + N->getGlobals().end() && "Global value not in node!"); + } + + 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(); +}; + + +/// 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 = ~DSNode::DEAD; + if (CloneFlags & DSGraph::StripAllocaBit) + BitsToKeep &= ~DSNode::AllocaNode; + if (CloneFlags & DSGraph::StripModRefBits) + BitsToKeep &= ~(DSNode::Modified | DSNode::Read); + if (CloneFlags & DSGraph::StripIncompleteBit) + BitsToKeep &= ~DSNode::Incomplete; + } + + 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(const DSCallSite &DestCS, 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/llvm/include/llvm/Analysis/DataStructure/DSGraphTraits.h b/llvm/include/llvm/Analysis/DataStructure/DSGraphTraits.h new file mode 100644 index 00000000000..608cd198efc --- /dev/null +++ b/llvm/include/llvm/Analysis/DataStructure/DSGraphTraits.h @@ -0,0 +1,155 @@ +//===- 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 "llvm/Analysis/DataStructure/DSGraph.h" +#include "Support/GraphTraits.h" +#include "Support/iterator" +#include "Support/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() << DS::PointerShift; + if (Offset == 0 && Node->getForwardNode() && + Node->isDeadNode()) // Model Forward link + Offset += DS::PointerSize; + } 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->isDeadNode()) + return Node->getForwardNode(); + else + return Node->getLink(Offset).getNode(); + } + pointer operator->() const { return operator*(); } + + _Self& operator++() { // Preincrement + Offset += (1 << DS::PointerShift); + 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; } +static const DSNode &dereferenceC(const 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; + + typedef std::pointer_to_unary_function<const DSNode *,const 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(const DSGraph *G) { + return map_iterator(G->node_begin(), DerefFun(dereferenceC)); + } + static nodes_iterator nodes_end(const DSGraph *G) { + return map_iterator(G->node_end(), DerefFun(dereferenceC)); + } + + 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/llvm/include/llvm/Analysis/DataStructure/DSNode.h b/llvm/include/llvm/Analysis/DataStructure/DSNode.h new file mode 100644 index 00000000000..27ae67ee1dd --- /dev/null +++ b/llvm/include/llvm/Analysis/DataStructure/DSNode.h @@ -0,0 +1,468 @@ +//===- 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 "llvm/Analysis/DataStructure/DSSupport.h" + +namespace llvm { + +template<typename BaseType> +class DSNodeIterator; // Data structure graph traversal iterator +class TargetData; + +//===----------------------------------------------------------------------===// +/// 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 class 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; + + /// Globals - The list of global values that are merged into this node. + /// + std::vector<GlobalValue*> Globals; + + void operator=(const DSNode &); // DO NOT IMPLEMENT + DSNode(const DSNode &); // DO NOT IMPLEMENT +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 var decl + UnknownNode = 1 << 3, // This node points to unknown allocated memory + Incomplete = 1 << 4, // This node may not be complete + + Modified = 1 << 5, // This node is modified in this context + Read = 1 << 6, // This node is read in this context + + Array = 1 << 7, // This node is treated like an array + //#ifndef NDEBUG + DEAD = 1 << 8, // This node is dead and should not be pointed to + //#endif + + Composition = AllocaNode | HeapNode | GlobalNode | UnknownNode, + }; + + /// 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. + /// +private: + unsigned short NodeType; +public: + + /// 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); + + ~DSNode() { + dropAllReferences(); + assert(hasNoReferrers() && "Referrers to dead node exist!"); + } + + // 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; } + + bool isArray() const { return NodeType & Array; } + + /// 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; } + + + /// getTargetData - Get the target data object used to construct this node. + /// + const TargetData &getTargetData() 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 { + assert((Offset & ((1 << DS::PointerShift)-1)) == 0 && + "Pointer offset not aligned correctly!"); + unsigned Index = Offset >> DS::PointerShift; + 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) { + assert((Offset & ((1 << DS::PointerShift)-1)) == 0 && + "Pointer offset not aligned correctly!"); + unsigned Index = Offset >> DS::PointerShift; + assert(Index < Links.size() && "Link index is out of range!"); + return Links[Index]; + } + const DSNodeHandle &getLink(unsigned Offset) const { + assert((Offset & ((1 << DS::PointerShift)-1)) == 0 && + "Pointer offset not aligned correctly!"); + unsigned Index = Offset >> DS::PointerShift; + 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(); } + + /// 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) { + assert((Offset & ((1 << DS::PointerShift)-1)) == 0 && + "Pointer offset not aligned correctly!"); + unsigned Index = Offset >> DS::PointerShift; + assert(Index < Links.size() && "Link index is out of range!"); + Links[Index] = NH; + } + + /// getPointerSize - Return the size of a pointer for the current target. + /// + unsigned getPointerSize() const { return DS::PointerSize; } + + /// 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(GlobalValue *GV); + void mergeGlobals(const std::vector<GlobalValue*> &RHS); + const std::vector<GlobalValue*> &getGlobals() const { return Globals; } + + typedef std::vector<GlobalValue*>::const_iterator global_iterator; + global_iterator global_begin() const { return Globals.begin(); } + global_iterator global_end() const { return Globals.end(); } + + + /// maskNodeTypes - Apply a mask to the node types bitfield. + /// + void maskNodeTypes(unsigned Mask) { + NodeType &= Mask; + } + + void mergeNodeFlags(unsigned RHS) { + NodeType |= RHS; + } + + /// 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 & ~DEAD; } + + bool isAllocaNode() const { return NodeType & AllocaNode; } + bool isHeapNode() const { return NodeType & HeapNode; } + bool isGlobalNode() const { return NodeType & GlobalNode; } + bool isUnknownNode() const { return NodeType & UnknownNode; } + + bool isModified() const { return NodeType & Modified; } + bool isRead() const { return NodeType & Read; } + + bool isIncomplete() const { return NodeType & Incomplete; } + bool isComplete() const { return !isIncomplete(); } + bool isDeadNode() const { return NodeType & DEAD; } + + DSNode *setAllocaNodeMarker() { NodeType |= AllocaNode; return this; } + DSNode *setHeapNodeMarker() { NodeType |= HeapNode; return this; } + DSNode *setGlobalNodeMarker() { NodeType |= GlobalNode; return this; } + DSNode *setUnknownNodeMarker() { NodeType |= UnknownNode; return this; } + + DSNode *setIncompleteMarker() { NodeType |= Incomplete; return this; } + DSNode *setModifiedMarker() { NodeType |= Modified; return this; } + DSNode *setReadMarker() { NodeType |= Read; return this; } + DSNode *setArrayMarker() { NodeType |= Array; return this; } + + void makeNodeDead() { + Globals.clear(); + assert(hasNoReferrers() && "Dead node shouldn't have refs!"); + NodeType = DEAD; + } + + /// 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(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<DSNode*> &ReachableNodes); + +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 setPrev(DSNode *N, DSNode *Prev) { N->Prev = Prev; } + static void setNext(DSNode *N, DSNode *Next) { N->Next = Next; } + + static DSNode *createNode() { return new DSNode(0,0); } + //static DSNode *createNode(const DSNode &V) { return new DSNode(V); } + + + void addNodeToList(DSNode *NTy) {} + void removeNodeFromList(DSNode *NTy) {} + void transferNodesFromList(iplist<DSNode, ilist_traits> &L2, + ilist_iterator<DSNode> first, + ilist_iterator<DSNode> last) {} +}; + +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. + 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 void 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 & DSNode::DEAD) == 0)); + assert((!N || Offset < N->Size || (N->Size == 0 && Offset == 0) || + N->isForwarding()) && "Node handle offset out of range!"); +} + +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/llvm/include/llvm/Analysis/DataStructure/DSSupport.h b/llvm/include/llvm/Analysis/DataStructure/DSSupport.h new file mode 100644 index 00000000000..8cce6c98fde --- /dev/null +++ b/llvm/include/llvm/Analysis/DataStructure/DSSupport.h @@ -0,0 +1,313 @@ +//===- 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 "Support/hash_set" +#include "llvm/Support/CallSite.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; + +namespace DS { // FIXME: After the paper, this should get cleaned up + enum { PointerShift = 2, // 64bit ptrs = 3, 32 bit ptrs = 2 + PointerSize = 1 << PointerShift + }; + + /// isPointerType - Return true if this first class type is big enough to hold + /// a pointer. + /// + bool isPointerType(const Type *Ty); +}; + +//===----------------------------------------------------------------------===// +/// 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... + inline DSNode *getNode() const; // Defined inline in DSNode.h + unsigned getOffset() const { return Offset; } + + void setOffset(unsigned O) { + //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; + } + + inline void 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; +}; + +} // End llvm namespace + +namespace std { + template<> + inline void swap<llvm::DSNodeHandle>(llvm::DSNodeHandle &NH1, llvm::DSNodeHandle &NH2) { NH1.swap(NH2); } +} + +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 + 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, 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... + 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(); + } + 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 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)); + } + + /// 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<DSNode*> &Nodes); + + 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/llvm/include/llvm/Analysis/DataStructure/DataStructure.h b/llvm/include/llvm/Analysis/DataStructure/DataStructure.h new file mode 100644 index 00000000000..f210003213c --- /dev/null +++ b/llvm/include/llvm/Analysis/DataStructure/DataStructure.h @@ -0,0 +1,248 @@ +//===- 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 "Support/hash_set" + +namespace llvm { + +class Type; +class Instruction; +class DSGraph; +class DSNode; + +// FIXME: move this stuff to a private header +namespace DataStructureAnalysis { + /// isPointerType - Return true if this first class type is big enough to hold + /// a pointer. + /// + bool isPointerType(const Type *Ty); +} + + +// 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 Pass { + // DSInfo, one graph for each function + 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 { + 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; + + /// releaseMemory - 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<TargetData>(); + } +}; + + +/// 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 Pass { +protected: + // DSInfo, one graph for each function + hash_map<Function*, DSGraph*> DSInfo; + DSGraph *GlobalsGraph; + hash_multimap<Instruction*, 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 { + 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; + + /// releaseMemory - if the pass pipeline is done with this pass, we can + /// release our memory... + /// + virtual void releaseMemory(); + + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); + AU.addRequired<LocalDataStructures>(); + } + + typedef hash_multimap<Instruction*, Function*> ActualCalleesTy; + const ActualCalleesTy &getActualCallees() const { + return ActualCallees; + } + +private: + 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); +}; + + +/// 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 Pass { + // DSInfo, one graph for each function + hash_map<Function*, DSGraph*> DSInfo; + hash_set<Function*> ArgsRemainIncomplete; + DSGraph *GlobalsGraph; +public: + ~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 { + 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 releaseMyMemory(); + + /// getAnalysisUsage - This obviously provides a data structure graph. + /// + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); + AU.addRequired<BUDataStructures>(); + } + +private: + void markReachableFunctionsExternallyAccessible(DSNode *N, + hash_set<DSNode*> &Visited); + + void inlineGraphIntoCallees(DSGraph &G); + DSGraph &getOrCreateDSGraph(Function &F); + void ComputePostOrder(Function &F, hash_set<DSGraph*> &Visited, + std::vector<DSGraph*> &PostOrder, + const BUDataStructures::ActualCalleesTy &ActualCallees); +}; + + +/// 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. +/// +struct CompleteBUDataStructures : public BUDataStructures { + 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 { + hash_map<Function*, DSGraph*>::const_iterator I = + DSInfo.find(const_cast<Function*>(&F)); + assert(I != DSInfo.end() && "Function not in module!"); + return *I->second; + } + + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); + AU.addRequired<BUDataStructures>(); + + // FIXME: TEMPORARY (remove once finalization of indirect call sites in the + // globals graph has been implemented in the BU pass) + AU.addRequired<TDDataStructures>(); + } + + /// print - Print out the analysis results... + /// + void print(std::ostream &O, const Module *M) const; + +private: + unsigned calculateSCCGraphs(DSGraph &FG, std::vector<DSGraph*> &Stack, + unsigned &NextID, + hash_map<DSGraph*, unsigned> &ValMap); + DSGraph &getOrCreateGraph(Function &F); + void processGraph(DSGraph &G); +}; + +} // End llvm namespace + +#endif |
