X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FDataStructure%2FDSGraph.h;h=7e19212abefbcfa6c890a0a9261d1b5bd96ffa3a;hb=e187d565207682978185624e8fcd8f2c9f31d290;hp=fae11f4abe2ff32b79b5efdd24e30ac47214e914;hpb=6fbcc26f1460eaee4e0eb8b426fc1ff0c7af11be;p=oota-llvm.git diff --git a/include/llvm/Analysis/DataStructure/DSGraph.h b/include/llvm/Analysis/DataStructure/DSGraph.h index fae11f4abe2..7e19212abef 100644 --- a/include/llvm/Analysis/DataStructure/DSGraph.h +++ b/include/llvm/Analysis/DataStructure/DSGraph.h @@ -7,7 +7,8 @@ // //===----------------------------------------------------------------------===// // -// This header defines the data structure graph. +// This header defines the data structure graph (DSGraph) and the +// ReachabilityCloner class. // //===----------------------------------------------------------------------===// @@ -15,16 +16,83 @@ #define LLVM_ANALYSIS_DSGRAPH_H #include "llvm/Analysis/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 ValueMapTy; + ValueMapTy ValueMap; + + typedef hash_set 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)); } + + DSNodeHandle &operator[](Value *V) { + std::pair IP = + ValueMap.insert(std::make_pair(V, DSNodeHandle())); + if (IP.second) { // Inserted the new entry into the map. + if (GlobalValue *GV = dyn_cast(V)) + GlobalSet.insert(GV); + } + return IP.first->second; + } + + void erase(iterator I) { + assert(I != ValueMap.end() && "Cannot erase end!"); + if (GlobalValue *GV = dyn_cast(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 hash_map ScalarMapTy; + typedef DSScalarMap ScalarMapTy; typedef hash_map ReturnNodesTy; - typedef hash_set GlobalSetTy; + typedef hash_set GlobalSetTy; + typedef std::vector 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 @@ -34,7 +102,7 @@ private: DSGraph *GlobalsGraph; // Pointer to the common graph of global objects bool PrintAuxCalls; // Should this graph print the Aux calls vector? - std::vector Nodes; + NodeListTy Nodes; ScalarMapTy ScalarMap; // ReturnNodes - A return value for every function merged into this graph. @@ -62,12 +130,19 @@ private: // 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() : GlobalsGraph(0), PrintAuxCalls(false) {} - DSGraph(Function &F, DSGraph *GlobalsGraph); // Compute the local 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 @@ -84,16 +159,21 @@ public: DSGraph *getGlobalsGraph() const { return GlobalsGraph; } void setGlobalsGraph(DSGraph *G) { GlobalsGraph = G; } - // setPrintAuxCalls - If you call this method, the auxillary call vector will - // be printed instead of the standard call vector to the dot file. - // + /// 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; } /// getNodes - Get a vector of all the nodes in the graph /// - const std::vector &getNodes() const { return Nodes; } - std::vector &getNodes() { return Nodes; } + typedef NodeListTy::const_iterator node_iterator; + node_iterator node_begin() const { return Nodes.begin(); } + node_iterator node_end() const { return Nodes.end(); } /// getFunctionNames - Return a space separated list of the name of the /// functions in this graph (if any) @@ -226,26 +306,25 @@ public: DontCloneAuxCallNodes = 1 << 2, CloneAuxCallNodes = 0, StripModRefBits = 1 << 3, KeepModRefBits = 0, StripIncompleteBit = 1 << 4, KeepIncompleteBit = 0, + UpdateInlinedGlobals = 1 << 5, DontUpdateInlinedGlobals = 0, }; -private: - void cloneReachableNodes(const DSNode* Node, - unsigned BitsToClear, - NodeMapTy& OldNodeMap, - NodeMapTy& CompletedNodeMap); - -public: void updateFromGlobalGraph(); - void cloneReachableSubgraph(const DSGraph& G, - const hash_set& RootNodes, - NodeMapTy& OldNodeMap, - NodeMapTy& CompletedNodeMap, - unsigned CloneFlags = 0); + /// 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. /// @@ -270,7 +349,7 @@ public: // Methods for checking to make sure graphs are well formed... void AssertNodeInGraph(const DSNode *N) const { - assert((!N || find(Nodes.begin(), Nodes.end(), N) != Nodes.end()) && + assert((!N || N->getParentGraph() == this) && "AssertNodeInGraph: Node is not in graph!"); } void AssertNodeContainsGlobal(const DSNode *N, GlobalValue *GV) const { @@ -297,13 +376,6 @@ public: void AssertGraphOK() const; - /// mergeInGlobalsGraph - This method is useful for clients to incorporate the - /// globals graph into the DS, BU or TD graph for a function. This code - /// retains all globals, i.e., does not delete unreachable globals after they - /// are inlined. - /// - void mergeInGlobalsGraph(); - /// 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 @@ -312,4 +384,49 @@ public: 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 clonedNode() const { return !NodeMap.empty(); } + + void destroy() { NodeMap.clear(); } + }; +} // End llvm namespace + #endif