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