LLVM API Documentation
00001 //===- DSGraph.h - Represent a collection of data structures ----*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This header defines the data structure graph (DSGraph) and the 00011 // ReachabilityCloner class. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #ifndef LLVM_ANALYSIS_DSGRAPH_H 00016 #define LLVM_ANALYSIS_DSGRAPH_H 00017 00018 #include "llvm/Analysis/DataStructure/DSNode.h" 00019 00020 namespace llvm { 00021 00022 class GlobalValue; 00023 00024 //===----------------------------------------------------------------------===// 00025 /// DSScalarMap - An instance of this class is used to keep track of all of 00026 /// which DSNode each scalar in a function points to. This is specialized to 00027 /// keep track of globals with nodes in the function, and to keep track of the 00028 /// unique DSNodeHandle being used by the scalar map. 00029 /// 00030 /// This class is crucial to the efficiency of DSA with some large SCC's. In 00031 /// these cases, the cost of iterating over the scalar map dominates the cost 00032 /// of DSA. In all of these cases, the DSA phase is really trying to identify 00033 /// globals or unique node handles active in the function. 00034 /// 00035 class DSScalarMap { 00036 typedef hash_map<Value*, DSNodeHandle> ValueMapTy; 00037 ValueMapTy ValueMap; 00038 00039 typedef hash_set<GlobalValue*> GlobalSetTy; 00040 GlobalSetTy GlobalSet; 00041 public: 00042 00043 // Compatibility methods: provide an interface compatible with a map of 00044 // Value* to DSNodeHandle's. 00045 typedef ValueMapTy::const_iterator const_iterator; 00046 typedef ValueMapTy::iterator iterator; 00047 iterator begin() { return ValueMap.begin(); } 00048 iterator end() { return ValueMap.end(); } 00049 const_iterator begin() const { return ValueMap.begin(); } 00050 const_iterator end() const { return ValueMap.end(); } 00051 iterator find(Value *V) { return ValueMap.find(V); } 00052 const_iterator find(Value *V) const { return ValueMap.find(V); } 00053 unsigned count(Value *V) const { return ValueMap.count(V); } 00054 00055 void erase(Value *V) { erase(find(V)); } 00056 00057 /// replaceScalar - When an instruction needs to be modified, this method can 00058 /// be used to update the scalar map to remove the old and insert the new. 00059 /// 00060 void replaceScalar(Value *Old, Value *New) { 00061 iterator I = find(Old); 00062 assert(I != end() && "Old value is not in the map!"); 00063 ValueMap.insert(std::make_pair(New, I->second)); 00064 erase(I); 00065 } 00066 00067 DSNodeHandle &operator[](Value *V) { 00068 std::pair<iterator,bool> IP = 00069 ValueMap.insert(std::make_pair(V, DSNodeHandle())); 00070 if (IP.second) { // Inserted the new entry into the map. 00071 if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) 00072 GlobalSet.insert(GV); 00073 } 00074 return IP.first->second; 00075 } 00076 00077 void erase(iterator I) { 00078 assert(I != ValueMap.end() && "Cannot erase end!"); 00079 if (GlobalValue *GV = dyn_cast<GlobalValue>(I->first)) 00080 GlobalSet.erase(GV); 00081 ValueMap.erase(I); 00082 } 00083 00084 void clear() { 00085 ValueMap.clear(); 00086 GlobalSet.clear(); 00087 } 00088 00089 // Access to the global set: the set of all globals currently in the 00090 // scalar map. 00091 typedef GlobalSetTy::const_iterator global_iterator; 00092 global_iterator global_begin() const { return GlobalSet.begin(); } 00093 global_iterator global_end() const { return GlobalSet.end(); } 00094 }; 00095 00096 00097 //===----------------------------------------------------------------------===// 00098 /// DSGraph - The graph that represents a function. 00099 /// 00100 struct DSGraph { 00101 // Public data-type declarations... 00102 typedef DSScalarMap ScalarMapTy; 00103 typedef hash_map<Function*, DSNodeHandle> ReturnNodesTy; 00104 typedef hash_set<GlobalValue*> GlobalSetTy; 00105 typedef ilist<DSNode> NodeListTy; 00106 00107 /// NodeMapTy - This data type is used when cloning one graph into another to 00108 /// keep track of the correspondence between the nodes in the old and new 00109 /// graphs. 00110 typedef hash_map<const DSNode*, DSNodeHandle> NodeMapTy; 00111 private: 00112 DSGraph *GlobalsGraph; // Pointer to the common graph of global objects 00113 bool PrintAuxCalls; // Should this graph print the Aux calls vector? 00114 00115 NodeListTy Nodes; 00116 ScalarMapTy ScalarMap; 00117 00118 // ReturnNodes - A return value for every function merged into this graph. 00119 // Each DSGraph may have multiple functions merged into it at any time, which 00120 // is used for representing SCCs. 00121 // 00122 ReturnNodesTy ReturnNodes; 00123 00124 // FunctionCalls - This vector maintains a single entry for each call 00125 // instruction in the current graph. The first entry in the vector is the 00126 // scalar that holds the return value for the call, the second is the function 00127 // scalar being invoked, and the rest are pointer arguments to the function. 00128 // This vector is built by the Local graph and is never modified after that. 00129 // 00130 std::vector<DSCallSite> FunctionCalls; 00131 00132 // AuxFunctionCalls - This vector contains call sites that have been processed 00133 // by some mechanism. In pratice, the BU Analysis uses this vector to hold 00134 // the _unresolved_ call sites, because it cannot modify FunctionCalls. 00135 // 00136 std::vector<DSCallSite> AuxFunctionCalls; 00137 00138 // InlinedGlobals - This set records which globals have been inlined from 00139 // other graphs (callers or callees, depending on the pass) into this one. 00140 // 00141 GlobalSetTy InlinedGlobals; 00142 00143 /// TD - This is the target data object for the machine this graph is 00144 /// constructed for. 00145 const TargetData &TD; 00146 00147 void operator=(const DSGraph &); // DO NOT IMPLEMENT 00148 00149 public: 00150 // Create a new, empty, DSGraph. 00151 DSGraph(const TargetData &td) 00152 : GlobalsGraph(0), PrintAuxCalls(false), TD(td) {} 00153 00154 // Compute the local DSGraph 00155 DSGraph(const TargetData &td, Function &F, DSGraph *GlobalsGraph); 00156 00157 // Copy ctor - If you want to capture the node mapping between the source and 00158 // destination graph, you may optionally do this by specifying a map to record 00159 // this into. 00160 // 00161 // Note that a copied graph does not retain the GlobalsGraph pointer of the 00162 // source. You need to set a new GlobalsGraph with the setGlobalsGraph 00163 // method. 00164 // 00165 DSGraph(const DSGraph &DSG); 00166 DSGraph(const DSGraph &DSG, NodeMapTy &NodeMap); 00167 ~DSGraph(); 00168 00169 DSGraph *getGlobalsGraph() const { return GlobalsGraph; } 00170 void setGlobalsGraph(DSGraph *G) { GlobalsGraph = G; } 00171 00172 /// getTargetData - Return the TargetData object for the current target. 00173 /// 00174 const TargetData &getTargetData() const { return TD; } 00175 00176 /// setPrintAuxCalls - If you call this method, the auxillary call vector will 00177 /// be printed instead of the standard call vector to the dot file. 00178 /// 00179 void setPrintAuxCalls() { PrintAuxCalls = true; } 00180 bool shouldPrintAuxCalls() const { return PrintAuxCalls; } 00181 00182 /// node_iterator/begin/end - Iterate over all of the nodes in the graph. Be 00183 /// extremely careful with these methods because any merging of nodes could 00184 /// cause the node to be removed from this list. This means that if you are 00185 /// iterating over nodes and doing something that could cause _any_ node to 00186 /// merge, your node_iterators into this graph can be invalidated. 00187 typedef NodeListTy::compat_iterator node_iterator; 00188 node_iterator node_begin() const { return Nodes.compat_begin(); } 00189 node_iterator node_end() const { return Nodes.compat_end(); } 00190 00191 /// getFunctionNames - Return a space separated list of the name of the 00192 /// functions in this graph (if any) 00193 /// 00194 std::string getFunctionNames() const; 00195 00196 /// addNode - Add a new node to the graph. 00197 /// 00198 void addNode(DSNode *N) { Nodes.push_back(N); } 00199 void unlinkNode(DSNode *N) { Nodes.remove(N); } 00200 00201 /// getScalarMap - Get a map that describes what the nodes the scalars in this 00202 /// function point to... 00203 /// 00204 ScalarMapTy &getScalarMap() { return ScalarMap; } 00205 const ScalarMapTy &getScalarMap() const { return ScalarMap; } 00206 00207 /// getFunctionCalls - Return the list of call sites in the original local 00208 /// graph... 00209 /// 00210 const std::vector<DSCallSite> &getFunctionCalls() const { 00211 return FunctionCalls; 00212 } 00213 00214 /// getAuxFunctionCalls - Get the call sites as modified by whatever passes 00215 /// have been run. 00216 /// 00217 std::vector<DSCallSite> &getAuxFunctionCalls() { 00218 return AuxFunctionCalls; 00219 } 00220 const std::vector<DSCallSite> &getAuxFunctionCalls() const { 00221 return AuxFunctionCalls; 00222 } 00223 00224 /// getInlinedGlobals - Get the set of globals that are have been inlined 00225 /// (from callees in BU or from callers in TD) into the current graph. 00226 /// 00227 GlobalSetTy& getInlinedGlobals() { 00228 return InlinedGlobals; 00229 } 00230 00231 /// getNodeForValue - Given a value that is used or defined in the body of the 00232 /// current function, return the DSNode that it points to. 00233 /// 00234 DSNodeHandle &getNodeForValue(Value *V) { return ScalarMap[V]; } 00235 00236 const DSNodeHandle &getNodeForValue(Value *V) const { 00237 ScalarMapTy::const_iterator I = ScalarMap.find(V); 00238 assert(I != ScalarMap.end() && 00239 "Use non-const lookup function if node may not be in the map"); 00240 return I->second; 00241 } 00242 00243 /// getReturnNodes - Return the mapping of functions to their return nodes for 00244 /// this graph. 00245 /// 00246 const ReturnNodesTy &getReturnNodes() const { return ReturnNodes; } 00247 ReturnNodesTy &getReturnNodes() { return ReturnNodes; } 00248 00249 /// getReturnNodeFor - Return the return node for the specified function. 00250 /// 00251 DSNodeHandle &getReturnNodeFor(Function &F) { 00252 ReturnNodesTy::iterator I = ReturnNodes.find(&F); 00253 assert(I != ReturnNodes.end() && "F not in this DSGraph!"); 00254 return I->second; 00255 } 00256 00257 const DSNodeHandle &getReturnNodeFor(Function &F) const { 00258 ReturnNodesTy::const_iterator I = ReturnNodes.find(&F); 00259 assert(I != ReturnNodes.end() && "F not in this DSGraph!"); 00260 return I->second; 00261 } 00262 00263 /// getGraphSize - Return the number of nodes in this graph. 00264 /// 00265 unsigned getGraphSize() const { 00266 return Nodes.size(); 00267 } 00268 00269 /// print - Print a dot graph to the specified ostream... 00270 /// 00271 void print(std::ostream &O) const; 00272 00273 /// dump - call print(std::cerr), for use from the debugger... 00274 /// 00275 void dump() const; 00276 00277 /// viewGraph - Emit a dot graph, run 'dot', run gv on the postscript file, 00278 /// then cleanup. For use from the debugger. 00279 /// 00280 void viewGraph() const; 00281 00282 void writeGraphToFile(std::ostream &O, const std::string &GraphName) const; 00283 00284 /// maskNodeTypes - Apply a mask to all of the node types in the graph. This 00285 /// is useful for clearing out markers like Incomplete. 00286 /// 00287 void maskNodeTypes(unsigned Mask) { 00288 for (node_iterator I = node_begin(), E = node_end(); I != E; ++I) 00289 (*I)->maskNodeTypes(Mask); 00290 } 00291 void maskIncompleteMarkers() { maskNodeTypes(~DSNode::Incomplete); } 00292 00293 // markIncompleteNodes - Traverse the graph, identifying nodes that may be 00294 // modified by other functions that have not been resolved yet. This marks 00295 // nodes that are reachable through three sources of "unknownness": 00296 // Global Variables, Function Calls, and Incoming Arguments 00297 // 00298 // For any node that may have unknown components (because something outside 00299 // the scope of current analysis may have modified it), the 'Incomplete' flag 00300 // is added to the NodeType. 00301 // 00302 enum MarkIncompleteFlags { 00303 MarkFormalArgs = 1, IgnoreFormalArgs = 0, 00304 IgnoreGlobals = 2, MarkGlobalsIncomplete = 0, 00305 }; 00306 void markIncompleteNodes(unsigned Flags); 00307 00308 // removeDeadNodes - Use a reachability analysis to eliminate subgraphs that 00309 // are unreachable. This often occurs because the data structure doesn't 00310 // "escape" into it's caller, and thus should be eliminated from the caller's 00311 // graph entirely. This is only appropriate to use when inlining graphs. 00312 // 00313 enum RemoveDeadNodesFlags { 00314 RemoveUnreachableGlobals = 1, KeepUnreachableGlobals = 0, 00315 }; 00316 void removeDeadNodes(unsigned Flags); 00317 00318 /// CloneFlags enum - Bits that may be passed into the cloneInto method to 00319 /// specify how to clone the function graph. 00320 enum CloneFlags { 00321 StripAllocaBit = 1 << 0, KeepAllocaBit = 0, 00322 DontCloneCallNodes = 1 << 1, CloneCallNodes = 0, 00323 DontCloneAuxCallNodes = 1 << 2, CloneAuxCallNodes = 0, 00324 StripModRefBits = 1 << 3, KeepModRefBits = 0, 00325 StripIncompleteBit = 1 << 4, KeepIncompleteBit = 0, 00326 UpdateInlinedGlobals = 1 << 5, DontUpdateInlinedGlobals = 0, 00327 }; 00328 00329 void updateFromGlobalGraph(); 00330 00331 /// computeNodeMapping - Given roots in two different DSGraphs, traverse the 00332 /// nodes reachable from the two graphs, computing the mapping of nodes from 00333 /// the first to the second graph. 00334 /// 00335 static void computeNodeMapping(const DSNodeHandle &NH1, 00336 const DSNodeHandle &NH2, NodeMapTy &NodeMap, 00337 bool StrictChecking = true); 00338 00339 00340 /// cloneInto - Clone the specified DSGraph into the current graph. The 00341 /// translated ScalarMap for the old function is filled into the OldValMap 00342 /// member, and the translated ReturnNodes map is returned into ReturnNodes. 00343 /// OldNodeMap contains a mapping from the original nodes to the newly cloned 00344 /// nodes. 00345 /// 00346 /// The CloneFlags member controls various aspects of the cloning process. 00347 /// 00348 void cloneInto(const DSGraph &G, ScalarMapTy &OldValMap, 00349 ReturnNodesTy &OldReturnNodes, NodeMapTy &OldNodeMap, 00350 unsigned CloneFlags = 0); 00351 00352 /// mergeInGraph - The method is used for merging graphs together. If the 00353 /// argument graph is not *this, it makes a clone of the specified graph, then 00354 /// merges the nodes specified in the call site with the formal arguments in 00355 /// the graph. If the StripAlloca's argument is 'StripAllocaBit' then Alloca 00356 /// markers are removed from nodes. 00357 /// 00358 void mergeInGraph(const DSCallSite &CS, Function &F, const DSGraph &Graph, 00359 unsigned CloneFlags); 00360 00361 /// getCallSiteForArguments - Get the arguments and return value bindings for 00362 /// the specified function in the current graph. 00363 /// 00364 DSCallSite getCallSiteForArguments(Function &F) const; 00365 00366 /// getDSCallSiteForCallSite - Given an LLVM CallSite object that is live in 00367 /// the context of this graph, return the DSCallSite for it. 00368 DSCallSite getDSCallSiteForCallSite(CallSite CS) const; 00369 00370 // Methods for checking to make sure graphs are well formed... 00371 void AssertNodeInGraph(const DSNode *N) const { 00372 assert((!N || N->getParentGraph() == this) && 00373 "AssertNodeInGraph: Node is not in graph!"); 00374 } 00375 void AssertNodeContainsGlobal(const DSNode *N, GlobalValue *GV) const { 00376 assert(std::find(N->getGlobals().begin(), N->getGlobals().end(), GV) != 00377 N->getGlobals().end() && "Global value not in node!"); 00378 } 00379 00380 void AssertCallSiteInGraph(const DSCallSite &CS) const; 00381 void AssertCallNodesInGraph() const; 00382 void AssertAuxCallNodesInGraph() const; 00383 00384 void AssertGraphOK() const; 00385 00386 /// removeTriviallyDeadNodes - After the graph has been constructed, this 00387 /// method removes all unreachable nodes that are created because they got 00388 /// merged with other nodes in the graph. This is used as the first step of 00389 /// removeDeadNodes. 00390 /// 00391 void removeTriviallyDeadNodes(); 00392 }; 00393 00394 00395 /// ReachabilityCloner - This class is used to incrementally clone and merge 00396 /// nodes from a non-changing source graph into a potentially mutating 00397 /// destination graph. Nodes are only cloned over on demand, either in 00398 /// responds to a merge() or getClonedNH() call. When a node is cloned over, 00399 /// all of the nodes reachable from it are automatically brought over as well. 00400 /// 00401 class ReachabilityCloner { 00402 DSGraph &Dest; 00403 const DSGraph &Src; 00404 00405 /// BitsToKeep - These bits are retained from the source node when the 00406 /// source nodes are merged into the destination graph. 00407 unsigned BitsToKeep; 00408 unsigned CloneFlags; 00409 00410 // NodeMap - A mapping from nodes in the source graph to the nodes that 00411 // represent them in the destination graph. 00412 DSGraph::NodeMapTy NodeMap; 00413 public: 00414 ReachabilityCloner(DSGraph &dest, const DSGraph &src, unsigned cloneFlags) 00415 : Dest(dest), Src(src), CloneFlags(cloneFlags) { 00416 assert(&Dest != &Src && "Cannot clone from graph to same graph!"); 00417 BitsToKeep = ~DSNode::DEAD; 00418 if (CloneFlags & DSGraph::StripAllocaBit) 00419 BitsToKeep &= ~DSNode::AllocaNode; 00420 if (CloneFlags & DSGraph::StripModRefBits) 00421 BitsToKeep &= ~(DSNode::Modified | DSNode::Read); 00422 if (CloneFlags & DSGraph::StripIncompleteBit) 00423 BitsToKeep &= ~DSNode::Incomplete; 00424 } 00425 00426 DSNodeHandle getClonedNH(const DSNodeHandle &SrcNH); 00427 00428 void merge(const DSNodeHandle &NH, const DSNodeHandle &SrcNH); 00429 00430 /// mergeCallSite - Merge the nodes reachable from the specified src call 00431 /// site into the nodes reachable from DestCS. 00432 /// 00433 void mergeCallSite(const DSCallSite &DestCS, const DSCallSite &SrcCS); 00434 00435 bool clonedAnyNodes() const { return !NodeMap.empty(); } 00436 00437 /// hasClonedNode - Return true if the specified node has been cloned from 00438 /// the source graph into the destination graph. 00439 bool hasClonedNode(const DSNode *N) { 00440 return NodeMap.count(N); 00441 } 00442 00443 void destroy() { NodeMap.clear(); } 00444 }; 00445 00446 } // End llvm namespace 00447 00448 #endif