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