include/llvm/Analysis/DSGraph.h

   1 //===- DSGraph.h - Represent a collection of data structures ----*- C++ -*-===//
   2 //
   3 // This header defines the primative classes that make up a data structure
   4 // graph.
   5 //
   6 //===----------------------------------------------------------------------===//
   7
   8 #ifndef LLVM_ANALYSIS_DSGRAPH_H
   9 #define LLVM_ANALYSIS_DSGRAPH_H
  10
  11 #include <vector>
  12 #include <map>
  13 #include <functional>
  14
  15 class Function;
  16 class CallInst;
  17 class Value;
  18 class GlobalValue;
  19 class Type;
  20
  21 class DSNode;                  // Each node in the graph
  22 class DSGraph;                 // A graph for a function
  23 class DSNodeIterator;          // Data structure graph traversal iterator
  24
  25
  26 //===----------------------------------------------------------------------===//
  27 /// DSNodeHandle - Implement a "handle" to a data structure node that takes care
  28 /// of all of the add/un'refing of the node to prevent the backpointers in the
  29 /// graph from getting out of date.  This class represents a "pointer" in the
  30 /// graph, whose destination is an indexed offset into a node.
  31 ///
  32 class DSNodeHandle {
  33   DSNode *N;
  34   unsigned Offset;
  35 public:
  36   // Allow construction, destruction, and assignment...
  37   DSNodeHandle(DSNode *n = 0, unsigned offs = 0) : N(0), Offset(offs) {
  38     setNode(n);
  39   }
  40   DSNodeHandle(const DSNodeHandle &H) : N(0), Offset(H.Offset) { setNode(H.N); }
  41   ~DSNodeHandle() { setNode((DSNode*)0); }
  42   DSNodeHandle &operator=(const DSNodeHandle &H) {
  43     setNode(H.N); Offset = H.Offset;
  44     return *this;
  45   }
  46
  47   bool operator<(const DSNodeHandle &H) const {  // Allow sorting
  48     return N < H.N || (N == H.N && Offset < H.Offset);
  49   }
  50   bool operator>(const DSNodeHandle &H) const { return H < *this; }
  51   bool operator==(const DSNodeHandle &H) const { // Allow comparison
  52     return N == H.N && Offset == H.Offset;
  53   }
  54   bool operator!=(const DSNodeHandle &H) const { return !operator==(H); }
  55
  56   // Allow explicit conversion to DSNode...
  57   DSNode *getNode() const { return N; }
  58   unsigned getOffset() const { return Offset; }
  59
  60   inline void setNode(DSNode *N);  // Defined inline later...
  61   void setOffset(unsigned O) { Offset = O; }
  62
  63   void addEdgeTo(unsigned LinkNo, const DSNodeHandle &N);
  64   void addEdgeTo(const DSNodeHandle &N) { addEdgeTo(0, N); }
  65
  66   /// mergeWith - Merge the logical node pointed to by 'this' with the node
  67   /// pointed to by 'N'.
  68   ///
  69   void mergeWith(const DSNodeHandle &N);
  70
  71   // hasLink - Return true if there is a link at the specified offset...
  72   inline bool hasLink(unsigned Num) const;
  73
  74   /// getLink - Treat this current node pointer as a pointer to a structure of
  75   /// some sort.  This method will return the pointer a mem[this+Num]
  76   ///
  77   inline const DSNodeHandle *getLink(unsigned Num) const;
  78   inline DSNodeHandle *getLink(unsigned Num);
  79
  80   inline void setLink(unsigned Num, const DSNodeHandle &NH);
  81 };
  82
  83
  84 //===----------------------------------------------------------------------===//
  85 /// DSNode - Data structure node class
  86 ///
  87 /// This class represents an untyped memory object of Size bytes.  It keeps
  88 /// track of any pointers that have been stored into the object as well as the
  89 /// different types represented in this object.
  90 ///
  91 class DSNode {
  92   /// Links - Contains one entry for every _distinct_ pointer field in the
  93   /// memory block.  These are demand allocated and indexed by the MergeMap
  94   /// vector.
  95   ///
  96   std::vector<DSNodeHandle> Links;
  97
  98   /// MergeMap - Maps from every byte in the object to a signed byte number.
  99   /// This map is neccesary due to the merging that is possible as part of the
 100   /// unification algorithm.  To merge two distinct bytes of the object together
 101   /// into a single logical byte, the indexes for the two bytes are set to the
 102   /// same value.  This fully general merging is capable of representing all
 103   /// manners of array merging if neccesary.
 104   ///
 105   /// This map is also used to map outgoing pointers to various byte offsets in
 106   /// this data structure node.  If this value is >= 0, then it indicates that
 107   /// the numbered entry in the Links vector contains the outgoing edge for this
 108   /// byte offset.  In this way, the Links vector can be demand allocated and
 109   /// byte elements of the node may be merged without needing a Link allocated
 110   /// for it.
 111   ///
 112   /// Initially, each each element of the MergeMap is assigned a unique negative
 113   /// number, which are then merged as the unification occurs.
 114   ///
 115   std::vector<signed char> MergeMap;
 116
 117   /// Referrers - Keep track of all of the node handles that point to this
 118   /// DSNode.  These pointers may need to be updated to point to a different
 119   /// node if this node gets merged with it.
 120   ///
 121   std::vector<DSNodeHandle*> Referrers;
 122
 123   /// TypeRec - This structure is used to represent a single type that is held
 124   /// in a DSNode.
 125   struct TypeRec {
 126     const Type *Ty;                 // The type itself...
 127     unsigned Offset;                // The offset in the node
 128     bool isArray;                   // Have we accessed an array of elements?
 129
 130     TypeRec() : Ty(0), Offset(0), isArray(false) {}
 131     TypeRec(const Type *T, unsigned O) : Ty(T), Offset(O), isArray(false) {}
 132
 133     bool operator<(const TypeRec &TR) const {
 134       // Sort first by offset!
 135       return Offset < TR.Offset || (Offset == TR.Offset && Ty < TR.Ty);
 136     }
 137     bool operator==(const TypeRec &TR) const {
 138       return Ty == TR.Ty && Offset == TR.Offset;
 139     }
 140     bool operator!=(const TypeRec &TR) const { return !operator==(TR); }
 141   };
 142
 143   /// TypeEntries - As part of the merging process of this algorithm, nodes of
 144   /// different types can be represented by this single DSNode.  This vector is
 145   /// kept sorted.
 146   ///
 147   std::vector<TypeRec> TypeEntries;
 148
 149   /// Globals - The list of global values that are merged into this node.
 150   ///
 151   std::vector<GlobalValue*> Globals;
 152
 153   void operator=(const DSNode &); // DO NOT IMPLEMENT
 154 public:
 155   enum NodeTy {
 156     ShadowNode = 0,        // Nothing is known about this node...
 157     ScalarNode = 1 << 0,   // Scalar of the current function contains this value
 158     AllocaNode = 1 << 1,   // This node was allocated with alloca
 159     NewNode    = 1 << 2,   // This node was allocated with malloc
 160     GlobalNode = 1 << 3,   // This node was allocated by a global var decl
 161     Incomplete = 1 << 4,   // This node may not be complete
 162     Modified   = 1 << 5,   // This node is modified in this context
 163     Read       = 1 << 6,   // This node is read in this context
 164   };
 165
 166   /// NodeType - A union of the above bits.  "Shadow" nodes do not add any flags
 167   /// to the nodes in the data structure graph, so it is possible to have nodes
 168   /// with a value of 0 for their NodeType.  Scalar and Alloca markers go away
 169   /// when function graphs are inlined.
 170   ///
 171   unsigned char NodeType;
 172
 173   DSNode(enum NodeTy NT, const Type *T);
 174   DSNode(const DSNode &);
 175
 176   ~DSNode() {
 177 #ifndef NDEBUG
 178     dropAllReferences();  // Only needed to satisfy assertion checks...
 179     assert(Referrers.empty() && "Referrers to dead node exist!");
 180 #endif
 181   }
 182
 183   // Iterator for graph interface...
 184   typedef DSNodeIterator iterator;
 185   typedef DSNodeIterator const_iterator;
 186   inline iterator begin() const;   // Defined in DSGraphTraits.h
 187   inline iterator end() const;
 188
 189   //===--------------------------------------------------
 190   // Accessors
 191
 192   /// getSize - Return the maximum number of bytes occupied by this object...
 193   ///
 194   unsigned getSize() const { return MergeMap.size(); }
 195
 196   // getTypeEntries - Return the possible types and their offsets in this object
 197   const std::vector<TypeRec> &getTypeEntries() const { return TypeEntries; }
 198
 199   /// getReferrers - Return a list of the pointers to this node...
 200   ///
 201   const std::vector<DSNodeHandle*> &getReferrers() const { return Referrers; }
 202
 203   /// isModified - Return true if this node may be modified in this context
 204   ///
 205   bool isModified() const { return (NodeType & Modified) != 0; }
 206
 207   /// isRead - Return true if this node may be read in this context
 208   ///
 209   bool isRead() const { return (NodeType & Read) != 0; }
 210
 211
 212   /// hasLink - Return true if this memory object has a link at the specified
 213   /// location.
 214   ///
 215   bool hasLink(unsigned i) const {
 216     assert(i < getSize() && "Field Link index is out of range!");
 217     return MergeMap[i] >= 0;
 218   }
 219
 220   DSNodeHandle *getLink(unsigned i) {
 221     if (hasLink(i))
 222       return &Links[MergeMap[i]];
 223     return 0;
 224   }
 225   const DSNodeHandle *getLink(unsigned i) const {
 226     if (hasLink(i))
 227       return &Links[MergeMap[i]];
 228     return 0;
 229   }
 230
 231   int getMergeMapLabel(unsigned i) const {
 232     assert(i < MergeMap.size() && "MergeMap index out of range!");
 233     return MergeMap[i];
 234   }
 235
 236   /// setLink - Set the link at the specified offset to the specified
 237   /// NodeHandle, replacing what was there.  It is uncommon to use this method,
 238   /// instead one of the higher level methods should be used, below.
 239   ///
 240   void setLink(unsigned i, const DSNodeHandle &NH);
 241
 242   /// addEdgeTo - Add an edge from the current node to the specified node.  This
 243   /// can cause merging of nodes in the graph.
 244   ///
 245   void addEdgeTo(unsigned Offset, const DSNodeHandle &NH);
 246
 247   /// mergeWith - Merge this node and the specified node, moving all links to
 248   /// and from the argument node into the current node, deleting the node
 249   /// argument.  Offset indicates what offset the specified node is to be merged
 250   /// into the current node.
 251   ///
 252   /// The specified node may be a null pointer (in which case, nothing happens).
 253   ///
 254   void mergeWith(const DSNodeHandle &NH, unsigned Offset);
 255
 256   /// mergeIndexes - If we discover that two indexes are equivalent and must be
 257   /// merged, this function is used to do the dirty work.
 258   ///
 259   void mergeIndexes(unsigned idx1, unsigned idx2) {
 260     assert(idx1 < getSize() && idx2 < getSize() && "Indexes out of range!");
 261     signed char MV1 = MergeMap[idx1];
 262     signed char MV2 = MergeMap[idx2];
 263     if (MV1 != MV2)
 264       mergeMappedValues(MV1, MV2);
 265   }
 266
 267
 268   /// addGlobal - Add an entry for a global value to the Globals list.  This
 269   /// also marks the node with the 'G' flag if it does not already have it.
 270   ///
 271   void addGlobal(GlobalValue *GV);
 272   const std::vector<GlobalValue*> &getGlobals() const { return Globals; }
 273   std::vector<GlobalValue*> &getGlobals() { return Globals; }
 274
 275   void print(std::ostream &O, const DSGraph *G) const;
 276   void dump() const;
 277
 278   void dropAllReferences() {
 279     Links.clear();
 280   }
 281
 282   /// remapLinks - Change all of the Links in the current node according to the
 283   /// specified mapping.
 284   void remapLinks(std::map<const DSNode*, DSNode*> &OldNodeMap);
 285
 286 private:
 287   friend class DSNodeHandle;
 288   // addReferrer - Keep the referrer set up to date...
 289   void addReferrer(DSNodeHandle *H) { Referrers.push_back(H); }
 290   void removeReferrer(DSNodeHandle *H);
 291
 292   /// rewriteMergeMap - Loop over the mergemap, replacing any references to the
 293   /// index From to be references to the index To.
 294   ///
 295   void rewriteMergeMap(signed char From, signed char To) {
 296     assert(From != To && "Cannot change something into itself!");
 297     for (unsigned i = 0, e = MergeMap.size(); i != e; ++i)
 298       if (MergeMap[i] == From)
 299         MergeMap[i] = To;
 300   }
 301
 302   /// mergeMappedValues - This is the higher level form of rewriteMergeMap.  It
 303   /// is fully capable of merging links together if neccesary as well as simply
 304   /// rewriting the map entries.
 305   ///
 306   void mergeMappedValues(signed char V1, signed char V2);
 307 };
 308
 309
 310 //===----------------------------------------------------------------------===//
 311 // Define inline DSNodeHandle functions that depend on the definition of DSNode
 312 //
 313
 314 inline void DSNodeHandle::setNode(DSNode *n) {
 315   if (N) N->removeReferrer(this);
 316   N = n;
 317   if (N) N->addReferrer(this);
 318 }
 319
 320 inline bool DSNodeHandle::hasLink(unsigned Num) const {
 321   assert(N && "DSNodeHandle does not point to a node yet!");
 322   return N->hasLink(Num+Offset);
 323 }
 324
 325
 326 /// getLink - Treat this current node pointer as a pointer to a structure of
 327 /// some sort.  This method will return the pointer a mem[this+Num]
 328 ///
 329 inline const DSNodeHandle *DSNodeHandle::getLink(unsigned Num) const {
 330   assert(N && "DSNodeHandle does not point to a node yet!");
 331   return N->getLink(Num+Offset);
 332 }
 333 inline DSNodeHandle *DSNodeHandle::getLink(unsigned Num) {
 334   assert(N && "DSNodeHandle does not point to a node yet!");
 335   return N->getLink(Num+Offset);
 336 }
 337
 338 inline void DSNodeHandle::setLink(unsigned Num, const DSNodeHandle &NH) {
 339   assert(N && "DSNodeHandle does not point to a node yet!");
 340   N->setLink(Num+Offset, NH);
 341 }
 342
 343 ///  addEdgeTo - Add an edge from the current node to the specified node.  This
 344 /// can cause merging of nodes in the graph.
 345 ///
 346 inline void DSNodeHandle::addEdgeTo(unsigned LinkNo, const DSNodeHandle &Node) {
 347   assert(N && "DSNodeHandle does not point to a node yet!");
 348   N->addEdgeTo(LinkNo+Offset, Node);
 349 }
 350
 351 /// mergeWith - Merge the logical node pointed to by 'this' with the node
 352 /// pointed to by 'N'.
 353 ///
 354 inline void DSNodeHandle::mergeWith(const DSNodeHandle &Node) {
 355   assert(N && "DSNodeHandle does not point to a node yet!");
 356   N->mergeWith(Node, Offset);
 357 }
 358
 359
 360 //===----------------------------------------------------------------------===//
 361 /// DSCallSite - Representation of a call site via its call instruction,
 362 /// the DSNode handle for the callee function (or function pointer), and
 363 /// the DSNode handles for the function arguments.
 364 ///
 365 class DSCallSite {
 366   CallInst    *Inst;                    // Actual call site
 367   DSNodeHandle RetVal;                  // Returned value
 368   DSNodeHandle Callee;                  // The function node called
 369   std::vector<DSNodeHandle> CallArgs;   // The pointer arguments
 370
 371   static DSNode *mapLookup(const DSNode *Node,
 372                            const std::map<const DSNode*, DSNode*> &NodeMap) {
 373     if (Node == 0) return 0;
 374     std::map<const DSNode*, DSNode*>::const_iterator I = NodeMap.find(Node);
 375     assert(I != NodeMap.end() && "Not not in mapping!");
 376     return I->second;
 377   }
 378
 379   DSCallSite();                         // DO NOT IMPLEMENT
 380 public:
 381   /// Constructor.  Note - This ctor destroys the argument vector passed in.  On
 382   /// exit, the argument vector is empty.
 383   ///
 384   DSCallSite(CallInst &inst, const DSNodeHandle &rv, const DSNodeHandle &callee,
 385              std::vector<DSNodeHandle> &Args)
 386     : Inst(&inst), RetVal(rv), Callee(callee) {
 387     Args.swap(CallArgs);
 388   }
 389
 390   DSCallSite(const DSCallSite &DSCS)   // Simple copy ctor
 391     : Inst(DSCS.Inst), RetVal(DSCS.RetVal),
 392       Callee(DSCS.Callee), CallArgs(DSCS.CallArgs) {}
 393
 394   /// Mapping copy constructor - This constructor takes a preexisting call site
 395   /// to copy plus a map that specifies how the links should be transformed.
 396   /// This is useful when moving a call site from one graph to another.
 397   ///
 398   DSCallSite(const DSCallSite &FromCall,
 399              const std::map<const DSNode*, DSNode*> &NodeMap) {
 400     Inst = FromCall.Inst;
 401     RetVal.setOffset(FromCall.RetVal.getOffset());
 402     RetVal.setNode(mapLookup(FromCall.RetVal.getNode(), NodeMap));
 403     Callee.setOffset(FromCall.Callee.getOffset());
 404     Callee.setNode(mapLookup(FromCall.Callee.getNode(), NodeMap));
 405     CallArgs.reserve(FromCall.CallArgs.size());
 406
 407     for (unsigned i = 0, e = FromCall.CallArgs.size(); i != e; ++i) {
 408       const DSNodeHandle &OldNH = FromCall.CallArgs[i];
 409       CallArgs.push_back(DSNodeHandle(mapLookup(OldNH.getNode(), NodeMap),
 410                                       OldNH.getOffset()));
 411     }
 412   }
 413
 414   // Accessor functions...
 415   Function           &getCaller()     const;
 416   CallInst           &getCallInst()   const { return *Inst; }
 417         DSNodeHandle &getRetVal()           { return RetVal; }
 418         DSNodeHandle &getCallee()           { return Callee; }
 419   const DSNodeHandle &getRetVal()     const { return RetVal; }
 420   const DSNodeHandle &getCallee()     const { return Callee; }
 421   unsigned            getNumPtrArgs() const { return CallArgs.size(); }
 422
 423   DSNodeHandle &getPtrArg(unsigned i) {
 424     assert(i < CallArgs.size() && "Argument to getPtrArgNode is out of range!");
 425     return CallArgs[i];
 426   }
 427   const DSNodeHandle &getPtrArg(unsigned i) const {
 428     assert(i < CallArgs.size() && "Argument to getPtrArgNode is out of range!");
 429     return CallArgs[i];
 430   }
 431
 432   bool operator<(const DSCallSite &CS) const {
 433     if (RetVal < CS.RetVal) return true;
 434     if (RetVal > CS.RetVal) return false;
 435     if (Callee < CS.Callee) return true;
 436     if (Callee > CS.Callee) return false;
 437     return CallArgs < CS.CallArgs;
 438   }
 439
 440   bool operator==(const DSCallSite &CS) const {
 441     return RetVal == CS.RetVal && Callee == CS.Callee &&
 442            CallArgs == CS.CallArgs;
 443   }
 444 };
 445
 446
 447 //===----------------------------------------------------------------------===//
 448 /// DSGraph - The graph that represents a function.
 449 ///
 450 class DSGraph {
 451   Function *Func;
 452   std::vector<DSNode*> Nodes;
 453   DSNodeHandle RetNode;                          // Node that gets returned...
 454   std::map<Value*, DSNodeHandle> ValueMap;
 455
 456 #if 0
 457   // GlobalsGraph -- Reference to the common graph of globally visible objects.
 458   // This includes GlobalValues, New nodes, Cast nodes, and Calls.
 459   //
 460   GlobalDSGraph* GlobalsGraph;
 461 #endif
 462
 463   // FunctionCalls - This vector maintains a single entry for each call
 464   // instruction in the current graph.  Each call entry contains DSNodeHandles
 465   // that refer to the arguments that are passed into the function call.  The
 466   // first entry in the vector is the scalar that holds the return value for the
 467   // call, the second is the function scalar being invoked, and the rest are
 468   // pointer arguments to the function.
 469   //
 470   std::vector<DSCallSite> FunctionCalls;
 471
 472   void operator=(const DSGraph &); // DO NOT IMPLEMENT
 473 public:
 474   DSGraph() : Func(0) {}           // Create a new, empty, DSGraph.
 475   DSGraph(Function &F);            // Compute the local DSGraph
 476   DSGraph(const DSGraph &DSG);     // Copy ctor
 477   ~DSGraph();
 478
 479   bool hasFunction() const { return Func != 0; }
 480   Function &getFunction() const { return *Func; }
 481
 482   /// getNodes - Get a vector of all the nodes in the graph
 483   ///
 484   const std::vector<DSNode*> &getNodes() const { return Nodes; }
 485         std::vector<DSNode*> &getNodes()       { return Nodes; }
 486
 487   /// addNode - Add a new node to the graph.
 488   ///
 489   void addNode(DSNode *N) { Nodes.push_back(N); }
 490
 491   /// getValueMap - Get a map that describes what the nodes the scalars in this
 492   /// function point to...
 493   ///
 494   std::map<Value*, DSNodeHandle> &getValueMap() { return ValueMap; }
 495   const std::map<Value*, DSNodeHandle> &getValueMap() const { return ValueMap;}
 496
 497   std::vector<DSCallSite> &getFunctionCalls() {
 498     return FunctionCalls;
 499   }
 500   const std::vector<DSCallSite> &getFunctionCalls() const {
 501     return FunctionCalls;
 502   }
 503
 504   /// getNodeForValue - Given a value that is used or defined in the body of the
 505   /// current function, return the DSNode that it points to.
 506   ///
 507   DSNodeHandle &getNodeForValue(Value *V) { return ValueMap[V]; }
 508
 509   const DSNodeHandle &getRetNode() const { return RetNode; }
 510         DSNodeHandle &getRetNode()       { return RetNode; }
 511
 512   unsigned getGraphSize() const {
 513     return Nodes.size();
 514   }
 515
 516   void print(std::ostream &O) const;
 517   void dump() const;
 518   void writeGraphToFile(std::ostream &O, const std::string &GraphName) const;
 519
 520   // maskNodeTypes - Apply a mask to all of the node types in the graph.  This
 521   // is useful for clearing out markers like Scalar or Incomplete.
 522   //
 523   void maskNodeTypes(unsigned char Mask);
 524   void maskIncompleteMarkers() { maskNodeTypes(~DSNode::Incomplete); }
 525
 526   // markIncompleteNodes - Traverse the graph, identifying nodes that may be
 527   // modified by other functions that have not been resolved yet.  This marks
 528   // nodes that are reachable through three sources of "unknownness":
 529   //   Global Variables, Function Calls, and Incoming Arguments
 530   //
 531   // For any node that may have unknown components (because something outside
 532   // the scope of current analysis may have modified it), the 'Incomplete' flag
 533   // is added to the NodeType.
 534   //
 535   void markIncompleteNodes(bool markFormalArgs = true);
 536
 537   // removeTriviallyDeadNodes - After the graph has been constructed, this
 538   // method removes all unreachable nodes that are created because they got
 539   // merged with other nodes in the graph.
 540   //
 541   void removeTriviallyDeadNodes(bool KeepAllGlobals = false);
 542
 543   // removeDeadNodes - Use a more powerful reachability analysis to eliminate
 544   // subgraphs that are unreachable.  This often occurs because the data
 545   // structure doesn't "escape" into it's caller, and thus should be eliminated
 546   // from the caller's graph entirely.  This is only appropriate to use when
 547   // inlining graphs.
 548   //
 549   void removeDeadNodes(bool KeepAllGlobals = false, bool KeepCalls = true);
 550
 551   // cloneInto - Clone the specified DSGraph into the current graph, returning
 552   // the Return node of the graph.  The translated ValueMap for the old function
 553   // is filled into the OldValMap member.
 554   // If StripScalars (StripAllocas) is set to true, Scalar (Alloca) markers
 555   // are removed from the graph as the graph is being cloned.
 556   // If CopyCallers is set to true, the PendingCallers list is copied.
 557   // If CopyOrigCalls is set to true, the OrigFunctionCalls list is copied.
 558   //
 559   DSNodeHandle cloneInto(const DSGraph &G,
 560                          std::map<Value*, DSNodeHandle> &OldValMap,
 561                          std::map<const DSNode*, DSNode*> &OldNodeMap,
 562                          bool StripScalars = false, bool StripAllocas = false,
 563                          bool CopyCallers = true, bool CopyOrigCalls = true);
 564
 565 #if 0
 566   // cloneGlobalInto - Clone the given global node (or the node for the given
 567   // GlobalValue) from the GlobalsGraph and all its target links (recursively).
 568   //
 569   DSNode* cloneGlobalInto(const DSNode* GNode);
 570   DSNode* cloneGlobalInto(GlobalValue* GV) {
 571     assert(!GV || (((DSGraph*) GlobalsGraph)->ValueMap[GV] != 0));
 572     return GV? cloneGlobalInto(((DSGraph*) GlobalsGraph)->ValueMap[GV]) : 0;
 573   }
 574 #endif
 575
 576 private:
 577   bool isNodeDead(DSNode *N);
 578 };
 579
 580 #endif