LLVM API Documentation

DSGraph.h

Go to the documentation of this file.
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 #include "llvm/ADT/hash_map"
00020 #include "llvm/ADT/EquivalenceClasses.h"
00021 #include <list>
00022 
00023 namespace llvm {
00024 
00025 class GlobalValue;
00026 
00027 //===----------------------------------------------------------------------===//
00028 /// DSScalarMap - An instance of this class is used to keep track of all of
00029 /// which DSNode each scalar in a function points to.  This is specialized to
00030 /// keep track of globals with nodes in the function, and to keep track of the
00031 /// unique DSNodeHandle being used by the scalar map.
00032 ///
00033 /// This class is crucial to the efficiency of DSA with some large SCC's.  In
00034 /// these cases, the cost of iterating over the scalar map dominates the cost
00035 /// of DSA.  In all of these cases, the DSA phase is really trying to identify
00036 /// globals or unique node handles active in the function.
00037 ///
00038 class DSScalarMap {
00039   typedef hash_map<Value*, DSNodeHandle> ValueMapTy;
00040   ValueMapTy ValueMap;
00041 
00042   typedef hash_set<GlobalValue*> GlobalSetTy;
00043   GlobalSetTy GlobalSet;
00044 
00045   EquivalenceClasses<GlobalValue*> &GlobalECs;
00046 public:
00047   DSScalarMap(EquivalenceClasses<GlobalValue*> &ECs) : GlobalECs(ECs) {}
00048 
00049   EquivalenceClasses<GlobalValue*> &getGlobalECs() const { return GlobalECs; }
00050 
00051   // Compatibility methods: provide an interface compatible with a map of
00052   // Value* to DSNodeHandle's.
00053   typedef ValueMapTy::const_iterator const_iterator;
00054   typedef ValueMapTy::iterator iterator;
00055   iterator begin() { return ValueMap.begin(); }
00056   iterator end()   { return ValueMap.end(); }
00057   const_iterator begin() const { return ValueMap.begin(); }
00058   const_iterator end() const { return ValueMap.end(); }
00059 
00060   GlobalValue *getLeaderForGlobal(GlobalValue *GV) const {
00061     EquivalenceClasses<GlobalValue*>::iterator ECI = GlobalECs.findValue(GV);
00062     if (ECI == GlobalECs.end()) return GV;
00063     return *GlobalECs.findLeader(ECI);
00064   }
00065 
00066 
00067   iterator find(Value *V) {
00068     iterator I = ValueMap.find(V);
00069     if (I != ValueMap.end()) return I;
00070 
00071     if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
00072       // If this is a global, check to see if it is equivalenced to something
00073       // in the map.
00074       GlobalValue *Leader = getLeaderForGlobal(GV);
00075       if (Leader != GV)
00076         I = ValueMap.find((Value*)Leader);
00077     }
00078     return I;
00079   }
00080   const_iterator find(Value *V) const {
00081     const_iterator I = ValueMap.find(V);
00082     if (I != ValueMap.end()) return I;
00083 
00084     if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
00085       // If this is a global, check to see if it is equivalenced to something
00086       // in the map.
00087       GlobalValue *Leader = getLeaderForGlobal(GV);
00088       if (Leader != GV)
00089         I = ValueMap.find((Value*)Leader);
00090     }
00091     return I;
00092   }
00093 
00094   /// getRawEntryRef - This method can be used by clients that are aware of the
00095   /// global value equivalence class in effect.
00096   DSNodeHandle &getRawEntryRef(Value *V) {
00097     std::pair<iterator,bool> IP =
00098       ValueMap.insert(std::make_pair(V, DSNodeHandle()));
00099      if (IP.second)   // Inserted the new entry into the map.
00100        if (GlobalValue *GV = dyn_cast<GlobalValue>(V))
00101          GlobalSet.insert(GV);
00102      return IP.first->second;
00103   }
00104 
00105   unsigned count(Value *V) const { return ValueMap.find(V) != ValueMap.end(); }
00106 
00107   void erase(Value *V) { erase(ValueMap.find(V)); }
00108 
00109   void eraseIfExists(Value *V) {
00110     iterator I = find(V);
00111     if (I != end()) erase(I);
00112   }
00113 
00114   /// replaceScalar - When an instruction needs to be modified, this method can
00115   /// be used to update the scalar map to remove the old and insert the new.
00116   ///
00117   void replaceScalar(Value *Old, Value *New) {
00118     iterator I = find(Old);
00119     assert(I != end() && "Old value is not in the map!");
00120     ValueMap.insert(std::make_pair(New, I->second));
00121     erase(I);
00122   }
00123 
00124   /// copyScalarIfExists - If Old exists in the scalar map, make New point to
00125   /// whatever Old did.
00126   void copyScalarIfExists(Value *Old, Value *New) {
00127     iterator I = find(Old);
00128     if (I != end())
00129       ValueMap.insert(std::make_pair(New, I->second));
00130   }
00131 
00132   /// operator[] - Return the DSNodeHandle for the specified value, creating a
00133   /// new null handle if there is no entry yet.
00134   DSNodeHandle &operator[](Value *V) {
00135     iterator I = ValueMap.find(V);
00136     if (I != ValueMap.end())
00137       return I->second;   // Return value if already exists.
00138 
00139     if (GlobalValue *GV = dyn_cast<GlobalValue>(V))
00140       return AddGlobal(GV);
00141 
00142     return ValueMap.insert(std::make_pair(V, DSNodeHandle())).first->second;
00143   }
00144 
00145   void erase(iterator I) {
00146     assert(I != ValueMap.end() && "Cannot erase end!");
00147     if (GlobalValue *GV = dyn_cast<GlobalValue>(I->first))
00148       GlobalSet.erase(GV);
00149     ValueMap.erase(I);
00150   }
00151 
00152   void clear() {
00153     ValueMap.clear();
00154     GlobalSet.clear();
00155   }
00156 
00157   /// spliceFrom - Copy all entries from RHS, then clear RHS.
00158   ///
00159   void spliceFrom(DSScalarMap &RHS);
00160 
00161   // Access to the global set: the set of all globals currently in the
00162   // scalar map.
00163   typedef GlobalSetTy::const_iterator global_iterator;
00164   global_iterator global_begin() const { return GlobalSet.begin(); }
00165   global_iterator global_end() const { return GlobalSet.end(); }
00166   unsigned global_size() const { return GlobalSet.size(); }
00167   unsigned global_count(GlobalValue *GV) const { return GlobalSet.count(GV); }
00168 private:
00169   DSNodeHandle &AddGlobal(GlobalValue *GV);
00170 };
00171 
00172 
00173 //===----------------------------------------------------------------------===//
00174 /// DSGraph - The graph that represents a function.
00175 ///
00176 class DSGraph {
00177 public:
00178   // Public data-type declarations...
00179   typedef DSScalarMap ScalarMapTy;
00180   typedef hash_map<Function*, DSNodeHandle> ReturnNodesTy;
00181   typedef ilist<DSNode> NodeListTy;
00182 
00183   /// NodeMapTy - This data type is used when cloning one graph into another to
00184   /// keep track of the correspondence between the nodes in the old and new
00185   /// graphs.
00186   typedef hash_map<const DSNode*, DSNodeHandle> NodeMapTy;
00187 
00188   // InvNodeMapTy - This data type is used to represent the inverse of a node
00189   // map.
00190   typedef hash_multimap<DSNodeHandle, const DSNode*> InvNodeMapTy;
00191 private:
00192   DSGraph *GlobalsGraph;   // Pointer to the common graph of global objects
00193   bool PrintAuxCalls;      // Should this graph print the Aux calls vector?
00194 
00195   NodeListTy Nodes;
00196   ScalarMapTy ScalarMap;
00197 
00198   // ReturnNodes - A return value for every function merged into this graph.
00199   // Each DSGraph may have multiple functions merged into it at any time, which
00200   // is used for representing SCCs.
00201   //
00202   ReturnNodesTy ReturnNodes;
00203 
00204   // FunctionCalls - This list maintains a single entry for each call
00205   // instruction in the current graph.  The first entry in the vector is the
00206   // scalar that holds the return value for the call, the second is the function
00207   // scalar being invoked, and the rest are pointer arguments to the function.
00208   // This vector is built by the Local graph and is never modified after that.
00209   //
00210   std::list<DSCallSite> FunctionCalls;
00211 
00212   // AuxFunctionCalls - This vector contains call sites that have been processed
00213   // by some mechanism.  In pratice, the BU Analysis uses this vector to hold
00214   // the _unresolved_ call sites, because it cannot modify FunctionCalls.
00215   //
00216   std::list<DSCallSite> AuxFunctionCalls;
00217 
00218   /// TD - This is the target data object for the machine this graph is
00219   /// constructed for.
00220   const TargetData &TD;
00221 
00222   void operator=(const DSGraph &); // DO NOT IMPLEMENT
00223   DSGraph(const DSGraph&);         // DO NOT IMPLEMENT
00224 public:
00225   // Create a new, empty, DSGraph.
00226   DSGraph(EquivalenceClasses<GlobalValue*> &ECs, const TargetData &td)
00227     : GlobalsGraph(0), PrintAuxCalls(false), ScalarMap(ECs), TD(td) {}
00228 
00229   // Compute the local DSGraph
00230   DSGraph(EquivalenceClasses<GlobalValue*> &ECs, const TargetData &TD,
00231           Function &F, DSGraph *GlobalsGraph);
00232 
00233   // Copy ctor - If you want to capture the node mapping between the source and
00234   // destination graph, you may optionally do this by specifying a map to record
00235   // this into.
00236   //
00237   // Note that a copied graph does not retain the GlobalsGraph pointer of the
00238   // source.  You need to set a new GlobalsGraph with the setGlobalsGraph
00239   // method.
00240   //
00241   DSGraph(const DSGraph &DSG, EquivalenceClasses<GlobalValue*> &ECs,
00242           unsigned CloneFlags = 0);
00243   ~DSGraph();
00244 
00245   DSGraph *getGlobalsGraph() const { return GlobalsGraph; }
00246   void setGlobalsGraph(DSGraph *G) { GlobalsGraph = G; }
00247 
00248   /// getGlobalECs - Return the set of equivalence classes that the global
00249   /// variables in the program form.
00250   EquivalenceClasses<GlobalValue*> &getGlobalECs() const {
00251     return ScalarMap.getGlobalECs();
00252   }
00253 
00254   /// getTargetData - Return the TargetData object for the current target.
00255   ///
00256   const TargetData &getTargetData() const { return TD; }
00257 
00258   /// setPrintAuxCalls - If you call this method, the auxillary call vector will
00259   /// be printed instead of the standard call vector to the dot file.
00260   ///
00261   void setPrintAuxCalls() { PrintAuxCalls = true; }
00262   bool shouldPrintAuxCalls() const { return PrintAuxCalls; }
00263 
00264   /// node_iterator/begin/end - Iterate over all of the nodes in the graph.  Be
00265   /// extremely careful with these methods because any merging of nodes could
00266   /// cause the node to be removed from this list.  This means that if you are
00267   /// iterating over nodes and doing something that could cause _any_ node to
00268   /// merge, your node_iterators into this graph can be invalidated.
00269   typedef NodeListTy::iterator node_iterator;
00270   node_iterator node_begin() { return Nodes.begin(); }
00271   node_iterator node_end()   { return Nodes.end(); }
00272 
00273   typedef NodeListTy::const_iterator node_const_iterator;
00274   node_const_iterator node_begin() const { return Nodes.begin(); }
00275   node_const_iterator node_end()   const { return Nodes.end(); }
00276 
00277   /// getFunctionNames - Return a space separated list of the name of the
00278   /// functions in this graph (if any)
00279   ///
00280   std::string getFunctionNames() const;
00281 
00282   /// addNode - Add a new node to the graph.
00283   ///
00284   void addNode(DSNode *N) { Nodes.push_back(N); }
00285   void unlinkNode(DSNode *N) { Nodes.remove(N); }
00286 
00287   /// getScalarMap - Get a map that describes what the nodes the scalars in this
00288   /// function point to...
00289   ///
00290   ScalarMapTy &getScalarMap() { return ScalarMap; }
00291   const ScalarMapTy &getScalarMap() const { return ScalarMap; }
00292 
00293   /// getFunctionCalls - Return the list of call sites in the original local
00294   /// graph...
00295   ///
00296   const std::list<DSCallSite> &getFunctionCalls() const { return FunctionCalls;}
00297   std::list<DSCallSite> &getFunctionCalls() { return FunctionCalls;}
00298 
00299   /// getAuxFunctionCalls - Get the call sites as modified by whatever passes
00300   /// have been run.
00301   ///
00302   std::list<DSCallSite> &getAuxFunctionCalls() { return AuxFunctionCalls; }
00303   const std::list<DSCallSite> &getAuxFunctionCalls() const {
00304     return AuxFunctionCalls;
00305   }
00306 
00307   // Function Call iteration
00308   typedef std::list<DSCallSite>::const_iterator fc_iterator;
00309   fc_iterator fc_begin() const { return FunctionCalls.begin(); }
00310   fc_iterator fc_end() const { return FunctionCalls.end(); }
00311 
00312 
00313   // Aux Function Call iteration
00314   typedef std::list<DSCallSite>::const_iterator afc_iterator;
00315   afc_iterator afc_begin() const { return AuxFunctionCalls.begin(); }
00316   afc_iterator afc_end() const { return AuxFunctionCalls.end(); }
00317 
00318   /// getNodeForValue - Given a value that is used or defined in the body of the
00319   /// current function, return the DSNode that it points to.
00320   ///
00321   DSNodeHandle &getNodeForValue(Value *V) { return ScalarMap[V]; }
00322 
00323   const DSNodeHandle &getNodeForValue(Value *V) const {
00324     ScalarMapTy::const_iterator I = ScalarMap.find(V);
00325     assert(I != ScalarMap.end() &&
00326            "Use non-const lookup function if node may not be in the map");
00327     return I->second;
00328   }
00329 
00330   /// retnodes_* iterator methods: expose iteration over return nodes in the
00331   /// graph, which are also the set of functions incorporated in this graph.
00332   typedef ReturnNodesTy::const_iterator retnodes_iterator;
00333   retnodes_iterator retnodes_begin() const { return ReturnNodes.begin(); }
00334   retnodes_iterator retnodes_end() const { return ReturnNodes.end(); }
00335 
00336 
00337   /// getReturnNodes - Return the mapping of functions to their return nodes for
00338   /// this graph.
00339   ///
00340   const ReturnNodesTy &getReturnNodes() const { return ReturnNodes; }
00341         ReturnNodesTy &getReturnNodes()       { return ReturnNodes; }
00342 
00343   /// getReturnNodeFor - Return the return node for the specified function.
00344   ///
00345   DSNodeHandle &getReturnNodeFor(Function &F) {
00346     ReturnNodesTy::iterator I = ReturnNodes.find(&F);
00347     assert(I != ReturnNodes.end() && "F not in this DSGraph!");
00348     return I->second;
00349   }
00350 
00351   const DSNodeHandle &getReturnNodeFor(Function &F) const {
00352     ReturnNodesTy::const_iterator I = ReturnNodes.find(&F);
00353     assert(I != ReturnNodes.end() && "F not in this DSGraph!");
00354     return I->second;
00355   }
00356 
00357   /// containsFunction - Return true if this DSGraph contains information for
00358   /// the specified function.
00359   bool containsFunction(Function *F) const {
00360     return ReturnNodes.count(F);
00361   }
00362 
00363   /// getGraphSize - Return the number of nodes in this graph.
00364   ///
00365   unsigned getGraphSize() const {
00366     return Nodes.size();
00367   }
00368 
00369   /// addObjectToGraph - This method can be used to add global, stack, and heap
00370   /// objects to the graph.  This can be used when updating DSGraphs due to the
00371   /// introduction of new temporary objects.  The new object is not pointed to
00372   /// and does not point to any other objects in the graph.  Note that this
00373   /// method initializes the type of the DSNode to the declared type of the
00374   /// object if UseDeclaredType is true, otherwise it leaves the node type as
00375   /// void.
00376   DSNode *addObjectToGraph(Value *Ptr, bool UseDeclaredType = true);
00377 
00378 
00379   /// print - Print a dot graph to the specified ostream...
00380   ///
00381   void print(std::ostream &O) const;
00382 
00383   /// dump - call print(std::cerr), for use from the debugger...
00384   ///
00385   void dump() const;
00386 
00387   /// viewGraph - Emit a dot graph, run 'dot', run gv on the postscript file,
00388   /// then cleanup.  For use from the debugger.
00389   ///
00390   void viewGraph() const;
00391 
00392   void writeGraphToFile(std::ostream &O, const std::string &GraphName) const;
00393 
00394   /// maskNodeTypes - Apply a mask to all of the node types in the graph.  This
00395   /// is useful for clearing out markers like Incomplete.
00396   ///
00397   void maskNodeTypes(unsigned Mask) {
00398     for (node_iterator I = node_begin(), E = node_end(); I != E; ++I)
00399       I->maskNodeTypes(Mask);
00400   }
00401   void maskIncompleteMarkers() { maskNodeTypes(~DSNode::Incomplete); }
00402 
00403   // markIncompleteNodes - Traverse the graph, identifying nodes that may be
00404   // modified by other functions that have not been resolved yet.  This marks
00405   // nodes that are reachable through three sources of "unknownness":
00406   //   Global Variables, Function Calls, and Incoming Arguments
00407   //
00408   // For any node that may have unknown components (because something outside
00409   // the scope of current analysis may have modified it), the 'Incomplete' flag
00410   // is added to the NodeType.
00411   //
00412   enum MarkIncompleteFlags {
00413     MarkFormalArgs = 1, IgnoreFormalArgs = 0,
00414     IgnoreGlobals = 2, MarkGlobalsIncomplete = 0
00415   };
00416   void markIncompleteNodes(unsigned Flags);
00417 
00418   // removeDeadNodes - Use a reachability analysis to eliminate subgraphs that
00419   // are unreachable.  This often occurs because the data structure doesn't
00420   // "escape" into it's caller, and thus should be eliminated from the caller's
00421   // graph entirely.  This is only appropriate to use when inlining graphs.
00422   //
00423   enum RemoveDeadNodesFlags {
00424     RemoveUnreachableGlobals = 1, KeepUnreachableGlobals = 0
00425   };
00426   void removeDeadNodes(unsigned Flags);
00427 
00428   /// CloneFlags enum - Bits that may be passed into the cloneInto method to
00429   /// specify how to clone the function graph.
00430   enum CloneFlags {
00431     StripAllocaBit        = 1 << 0, KeepAllocaBit     = 0,
00432     DontCloneCallNodes    = 1 << 1, CloneCallNodes    = 0,
00433     DontCloneAuxCallNodes = 1 << 2, CloneAuxCallNodes = 0,
00434     StripModRefBits       = 1 << 3, KeepModRefBits    = 0,
00435     StripIncompleteBit    = 1 << 4, KeepIncompleteBit = 0
00436   };
00437 
00438   void updateFromGlobalGraph();
00439 
00440   /// computeNodeMapping - Given roots in two different DSGraphs, traverse the
00441   /// nodes reachable from the two graphs, computing the mapping of nodes from
00442   /// the first to the second graph.
00443   ///
00444   static void computeNodeMapping(const DSNodeHandle &NH1,
00445                                  const DSNodeHandle &NH2, NodeMapTy &NodeMap,
00446                                  bool StrictChecking = true);
00447 
00448   /// computeGToGGMapping - Compute the mapping of nodes in the graph to nodes
00449   /// in the globals graph.
00450   void computeGToGGMapping(NodeMapTy &NodeMap);
00451 
00452   /// computeGGToGMapping - Compute the mapping of nodes in the global
00453   /// graph to nodes in this graph.
00454   void computeGGToGMapping(InvNodeMapTy &InvNodeMap);
00455 
00456   /// computeCalleeCallerMapping - Given a call from a function in the current
00457   /// graph to the 'Callee' function (which lives in 'CalleeGraph'), compute the
00458   /// mapping of nodes from the callee to nodes in the caller.
00459   void computeCalleeCallerMapping(DSCallSite CS, const Function &Callee,
00460                                   DSGraph &CalleeGraph, NodeMapTy &NodeMap);
00461 
00462   /// spliceFrom - Logically perform the operation of cloning the RHS graph into
00463   /// this graph, then clearing the RHS graph.  Instead of performing this as
00464   /// two seperate operations, do it as a single, much faster, one.
00465   ///
00466   void spliceFrom(DSGraph &RHS);
00467 
00468   /// cloneInto - Clone the specified DSGraph into the current graph.
00469   ///
00470   /// The CloneFlags member controls various aspects of the cloning process.
00471   ///
00472   void cloneInto(const DSGraph &G, unsigned CloneFlags = 0);
00473 
00474   /// getFunctionArgumentsForCall - Given a function that is currently in this
00475   /// graph, return the DSNodeHandles that correspond to the pointer-compatible
00476   /// function arguments.  The vector is filled in with the return value (or
00477   /// null if it is not pointer compatible), followed by all of the
00478   /// pointer-compatible arguments.
00479   void getFunctionArgumentsForCall(Function *F,
00480                                    std::vector<DSNodeHandle> &Args) const;
00481 
00482   /// mergeInGraph - This graph merges in the minimal number of
00483   /// nodes from G2 into 'this' graph, merging the bindings specified by the
00484   /// call site (in this graph) with the bindings specified by the vector in G2.
00485   /// If the StripAlloca's argument is 'StripAllocaBit' then Alloca markers are
00486   /// removed from nodes.
00487   ///
00488   void mergeInGraph(const DSCallSite &CS, std::vector<DSNodeHandle> &Args,
00489                     const DSGraph &G2, unsigned CloneFlags);
00490 
00491   /// mergeInGraph - This method is the same as the above method, but the
00492   /// argument bindings are provided by using the formal arguments of F.
00493   ///
00494   void mergeInGraph(const DSCallSite &CS, Function &F, const DSGraph &Graph,
00495                     unsigned CloneFlags);
00496 
00497   /// getCallSiteForArguments - Get the arguments and return value bindings for
00498   /// the specified function in the current graph.
00499   ///
00500   DSCallSite getCallSiteForArguments(Function &F) const;
00501 
00502   /// getDSCallSiteForCallSite - Given an LLVM CallSite object that is live in
00503   /// the context of this graph, return the DSCallSite for it.
00504   DSCallSite getDSCallSiteForCallSite(CallSite CS) const;
00505 
00506   // Methods for checking to make sure graphs are well formed...
00507   void AssertNodeInGraph(const DSNode *N) const {
00508     assert((!N || N->getParentGraph() == this) &&
00509            "AssertNodeInGraph: Node is not in graph!");
00510   }
00511   void AssertNodeContainsGlobal(const DSNode *N, GlobalValue *GV) const;
00512 
00513   void AssertCallSiteInGraph(const DSCallSite &CS) const;
00514   void AssertCallNodesInGraph() const;
00515   void AssertAuxCallNodesInGraph() const;
00516 
00517   void AssertGraphOK() const;
00518 
00519   /// removeTriviallyDeadNodes - After the graph has been constructed, this
00520   /// method removes all unreachable nodes that are created because they got
00521   /// merged with other nodes in the graph.  This is used as the first step of
00522   /// removeDeadNodes.
00523   ///
00524   void removeTriviallyDeadNodes();
00525 };
00526 
00527 
00528 /// ReachabilityCloner - This class is used to incrementally clone and merge
00529 /// nodes from a non-changing source graph into a potentially mutating
00530 /// destination graph.  Nodes are only cloned over on demand, either in
00531 /// responds to a merge() or getClonedNH() call.  When a node is cloned over,
00532 /// all of the nodes reachable from it are automatically brought over as well.
00533 ///
00534 class ReachabilityCloner {
00535   DSGraph &Dest;
00536   const DSGraph &Src;
00537 
00538   /// BitsToKeep - These bits are retained from the source node when the
00539   /// source nodes are merged into the destination graph.
00540   unsigned BitsToKeep;
00541   unsigned CloneFlags;
00542 
00543   // NodeMap - A mapping from nodes in the source graph to the nodes that
00544   // represent them in the destination graph.
00545   DSGraph::NodeMapTy NodeMap;
00546 public:
00547   ReachabilityCloner(DSGraph &dest, const DSGraph &src, unsigned cloneFlags)
00548     : Dest(dest), Src(src), CloneFlags(cloneFlags) {
00549     assert(&Dest != &Src && "Cannot clone from graph to same graph!");
00550     BitsToKeep = ~DSNode::DEAD;
00551     if (CloneFlags & DSGraph::StripAllocaBit)
00552       BitsToKeep &= ~DSNode::AllocaNode;
00553     if (CloneFlags & DSGraph::StripModRefBits)
00554       BitsToKeep &= ~(DSNode::Modified | DSNode::Read);
00555     if (CloneFlags & DSGraph::StripIncompleteBit)
00556       BitsToKeep &= ~DSNode::Incomplete;
00557   }
00558 
00559   DSNodeHandle getClonedNH(const DSNodeHandle &SrcNH);
00560 
00561   void merge(const DSNodeHandle &NH, const DSNodeHandle &SrcNH);
00562 
00563   /// mergeCallSite - Merge the nodes reachable from the specified src call
00564   /// site into the nodes reachable from DestCS.
00565   ///
00566   void mergeCallSite(DSCallSite &DestCS, const DSCallSite &SrcCS);
00567 
00568   bool clonedAnyNodes() const { return !NodeMap.empty(); }
00569 
00570   /// hasClonedNode - Return true if the specified node has been cloned from
00571   /// the source graph into the destination graph.
00572   bool hasClonedNode(const DSNode *N) {
00573     return NodeMap.count(N);
00574   }
00575 
00576   void destroy() { NodeMap.clear(); }
00577 };
00578 
00579 } // End llvm namespace
00580 
00581 #endif