include/llvm/Analysis/DSNode.h

   1 //===- DSSupport.h - Support for datastructure graphs -----------*- C++ -*-===//
   2 //
   3 // Support for graph nodes, call sites, and types.
   4 //
   5 //===----------------------------------------------------------------------===//
   6
   7 #ifndef LLVM_ANALYSIS_DSNODE_H
   8 #define LLVM_ANALYSIS_DSNODE_H
   9
  10 #include "llvm/Analysis/DSSupport.h"
  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 /// DSNode - Data structure node class
  28 ///
  29 /// This class represents an untyped memory object of Size bytes.  It keeps
  30 /// track of any pointers that have been stored into the object as well as the
  31 /// different types represented in this object.
  32 ///
  33 class DSNode {
  34   /// Links - Contains one entry for every _distinct_ pointer field in the
  35   /// memory block.  These are demand allocated and indexed by the MergeMap
  36   /// vector.
  37   ///
  38   std::vector<DSNodeHandle> Links;
  39
  40   /// MergeMap - Maps from every byte in the object to a signed byte number.
  41   /// This map is neccesary due to the merging that is possible as part of the
  42   /// unification algorithm.  To merge two distinct bytes of the object together
  43   /// into a single logical byte, the indexes for the two bytes are set to the
  44   /// same value.  This fully general merging is capable of representing all
  45   /// manners of array merging if neccesary.
  46   ///
  47   /// This map is also used to map outgoing pointers to various byte offsets in
  48   /// this data structure node.  If this value is >= 0, then it indicates that
  49   /// the numbered entry in the Links vector contains the outgoing edge for this
  50   /// byte offset.  In this way, the Links vector can be demand allocated and
  51   /// byte elements of the node may be merged without needing a Link allocated
  52   /// for it.
  53   ///
  54   /// Initially, each each element of the MergeMap is assigned a unique negative
  55   /// number, which are then merged as the unification occurs.
  56   ///
  57   std::vector<signed char> MergeMap;
  58
  59   /// Referrers - Keep track of all of the node handles that point to this
  60   /// DSNode.  These pointers may need to be updated to point to a different
  61   /// node if this node gets merged with it.
  62   ///
  63   std::vector<DSNodeHandle*> Referrers;
  64
  65   /// TypeEntries - As part of the merging process of this algorithm, nodes of
  66   /// different types can be represented by this single DSNode.  This vector is
  67   /// kept sorted.
  68   ///
  69   std::vector<DSTypeRec> TypeEntries;
  70
  71   /// Globals - The list of global values that are merged into this node.
  72   ///
  73   std::vector<GlobalValue*> Globals;
  74
  75   void operator=(const DSNode &); // DO NOT IMPLEMENT
  76 public:
  77   enum NodeTy {
  78     ShadowNode = 0,        // Nothing is known about this node...
  79     ScalarNode = 1 << 0,   // Scalar of the current function contains this value
  80     AllocaNode = 1 << 1,   // This node was allocated with alloca
  81     NewNode    = 1 << 2,   // This node was allocated with malloc
  82     GlobalNode = 1 << 3,   // This node was allocated by a global var decl
  83     Incomplete = 1 << 4,   // This node may not be complete
  84     Modified   = 1 << 5,   // This node is modified in this context
  85     Read       = 1 << 6,   // This node is read in this context
  86   };
  87
  88   /// NodeType - A union of the above bits.  "Shadow" nodes do not add any flags
  89   /// to the nodes in the data structure graph, so it is possible to have nodes
  90   /// with a value of 0 for their NodeType.  Scalar and Alloca markers go away
  91   /// when function graphs are inlined.
  92   ///
  93   unsigned char NodeType;
  94
  95   DSNode(enum NodeTy NT, const Type *T);
  96   DSNode(const DSNode &);
  97
  98   ~DSNode() {
  99 #ifndef NDEBUG
 100     dropAllReferences();  // Only needed to satisfy assertion checks...
 101     assert(Referrers.empty() && "Referrers to dead node exist!");
 102 #endif
 103   }
 104
 105   // Iterator for graph interface...
 106   typedef DSNodeIterator iterator;
 107   typedef DSNodeIterator const_iterator;
 108   inline iterator begin() const;   // Defined in DSGraphTraits.h
 109   inline iterator end() const;
 110
 111   //===--------------------------------------------------
 112   // Accessors
 113
 114   /// getSize - Return the maximum number of bytes occupied by this object...
 115   ///
 116   unsigned getSize() const { return MergeMap.size(); }
 117
 118   // getTypeEntries - Return the possible types and their offsets in this object
 119   const std::vector<DSTypeRec> &getTypeEntries() const { return TypeEntries; }
 120
 121   /// getReferrers - Return a list of the pointers to this node...
 122   ///
 123   const std::vector<DSNodeHandle*> &getReferrers() const { return Referrers; }
 124
 125   /// isModified - Return true if this node may be modified in this context
 126   ///
 127   bool isModified() const { return (NodeType & Modified) != 0; }
 128
 129   /// isRead - Return true if this node may be read in this context
 130   ///
 131   bool isRead() const { return (NodeType & Read) != 0; }
 132
 133
 134   /// hasLink - Return true if this memory object has a link at the specified
 135   /// location.
 136   ///
 137   bool hasLink(unsigned i) const {
 138     assert(i < getSize() && "Field Link index is out of range!");
 139     return MergeMap[i] >= 0;
 140   }
 141
 142   DSNodeHandle *getLink(unsigned i) {
 143     if (hasLink(i))
 144       return &Links[MergeMap[i]];
 145     return 0;
 146   }
 147   const DSNodeHandle *getLink(unsigned i) const {
 148     if (hasLink(i))
 149       return &Links[MergeMap[i]];
 150     return 0;
 151   }
 152
 153   /// getMergeMapLabel - Return the merge map entry specified, to allow printing
 154   /// out of DSNodes nicely for DOT graphs.
 155   ///
 156   int getMergeMapLabel(unsigned i) const {
 157     assert(i < MergeMap.size() && "MergeMap index out of range!");
 158     return MergeMap[i];
 159   }
 160
 161   /// getTypeRec - This method returns the specified type record if it exists.
 162   /// If it does not yet exist, the method checks to see whether or not the
 163   /// request would result in an untrackable state.  If adding it would cause
 164   /// untrackable state, we foldNodeCompletely the node and return the void
 165   /// record, otherwise we add an new TypeEntry and return it.
 166   ///
 167   DSTypeRec &getTypeRec(const Type *Ty, unsigned Offset);
 168
 169   /// foldNodeCompletely - If we determine that this node has some funny
 170   /// behavior happening to it that we cannot represent, we fold it down to a
 171   /// single, completely pessimistic, node.  This node is represented as a
 172   /// single byte with a single TypeEntry of "void".
 173   ///
 174   void foldNodeCompletely();
 175
 176   /// isNodeCompletelyFolded - Return true if this node has been completely
 177   /// folded down to something that can never be expanded, effectively losing
 178   /// all of the field sensitivity that may be present in the node.
 179   ///
 180   bool isNodeCompletelyFolded() const;
 181
 182   /// setLink - Set the link at the specified offset to the specified
 183   /// NodeHandle, replacing what was there.  It is uncommon to use this method,
 184   /// instead one of the higher level methods should be used, below.
 185   ///
 186   void setLink(unsigned i, const DSNodeHandle &NH);
 187
 188   /// addEdgeTo - Add an edge from the current node to the specified node.  This
 189   /// can cause merging of nodes in the graph.
 190   ///
 191   void addEdgeTo(unsigned Offset, const DSNodeHandle &NH);
 192
 193   /// mergeWith - Merge this node and the specified node, moving all links to
 194   /// and from the argument node into the current node, deleting the node
 195   /// argument.  Offset indicates what offset the specified node is to be merged
 196   /// into the current node.
 197   ///
 198   /// The specified node may be a null pointer (in which case, nothing happens).
 199   ///
 200   void mergeWith(const DSNodeHandle &NH, unsigned Offset);
 201
 202   /// mergeIndexes - If we discover that two indexes are equivalent and must be
 203   /// merged, this function is used to do the dirty work.
 204   ///
 205   void mergeIndexes(unsigned idx1, unsigned idx2) {
 206     assert(idx1 < getSize() && idx2 < getSize() && "Indexes out of range!");
 207     signed char MV1 = MergeMap[idx1];
 208     signed char MV2 = MergeMap[idx2];
 209     if (MV1 != MV2)
 210       mergeMappedValues(MV1, MV2);
 211   }
 212
 213
 214   /// addGlobal - Add an entry for a global value to the Globals list.  This
 215   /// also marks the node with the 'G' flag if it does not already have it.
 216   ///
 217   void addGlobal(GlobalValue *GV);
 218   const std::vector<GlobalValue*> &getGlobals() const { return Globals; }
 219   std::vector<GlobalValue*> &getGlobals() { return Globals; }
 220
 221   void print(std::ostream &O, const DSGraph *G) const;
 222   void dump() const;
 223
 224   void dropAllReferences() {
 225     Links.clear();
 226   }
 227
 228   /// remapLinks - Change all of the Links in the current node according to the
 229   /// specified mapping.
 230   void remapLinks(std::map<const DSNode*, DSNode*> &OldNodeMap);
 231
 232 private:
 233   friend class DSNodeHandle;
 234   // addReferrer - Keep the referrer set up to date...
 235   void addReferrer(DSNodeHandle *H) { Referrers.push_back(H); }
 236   void removeReferrer(DSNodeHandle *H);
 237
 238   /// rewriteMergeMap - Loop over the mergemap, replacing any references to the
 239   /// index From to be references to the index To.
 240   ///
 241   void rewriteMergeMap(signed char From, signed char To) {
 242     assert(From != To && "Cannot change something into itself!");
 243     for (unsigned i = 0, e = MergeMap.size(); i != e; ++i)
 244       if (MergeMap[i] == From)
 245         MergeMap[i] = To;
 246   }
 247
 248   /// mergeMappedValues - This is the higher level form of rewriteMergeMap.  It
 249   /// is fully capable of merging links together if neccesary as well as simply
 250   /// rewriting the map entries.
 251   ///
 252   void mergeMappedValues(signed char V1, signed char V2);
 253
 254   /// growNode - Attempt to grow the node to the specified size.  This may do
 255   /// one of three things:
 256   ///   1. Grow the node, return false
 257   ///   2. Refuse to grow the node, but maintain a trackable situation, return
 258   ///      false.
 259   ///   3. Be unable to track if node was that size, so collapse the node and
 260   ///      return true.
 261   ///
 262   bool growNode(unsigned RequestedSize);
 263 };
 264
 265
 266 //===----------------------------------------------------------------------===//
 267 // Define inline DSNodeHandle functions that depend on the definition of DSNode
 268 //
 269
 270 inline void DSNodeHandle::setNode(DSNode *n) {
 271   if (N) N->removeReferrer(this);
 272   N = n;
 273   if (N) N->addReferrer(this);
 274 }
 275
 276 inline bool DSNodeHandle::hasLink(unsigned Num) const {
 277   assert(N && "DSNodeHandle does not point to a node yet!");
 278   return N->hasLink(Num+Offset);
 279 }
 280
 281
 282 /// getLink - Treat this current node pointer as a pointer to a structure of
 283 /// some sort.  This method will return the pointer a mem[this+Num]
 284 ///
 285 inline const DSNodeHandle *DSNodeHandle::getLink(unsigned Num) const {
 286   assert(N && "DSNodeHandle does not point to a node yet!");
 287   return N->getLink(Num+Offset);
 288 }
 289 inline DSNodeHandle *DSNodeHandle::getLink(unsigned Num) {
 290   assert(N && "DSNodeHandle does not point to a node yet!");
 291   return N->getLink(Num+Offset);
 292 }
 293
 294 inline void DSNodeHandle::setLink(unsigned Num, const DSNodeHandle &NH) {
 295   assert(N && "DSNodeHandle does not point to a node yet!");
 296   N->setLink(Num+Offset, NH);
 297 }
 298
 299 ///  addEdgeTo - Add an edge from the current node to the specified node.  This
 300 /// can cause merging of nodes in the graph.
 301 ///
 302 inline void DSNodeHandle::addEdgeTo(unsigned LinkNo, const DSNodeHandle &Node) {
 303   assert(N && "DSNodeHandle does not point to a node yet!");
 304   N->addEdgeTo(LinkNo+Offset, Node);
 305 }
 306
 307 /// mergeWith - Merge the logical node pointed to by 'this' with the node
 308 /// pointed to by 'N'.
 309 ///
 310 inline void DSNodeHandle::mergeWith(const DSNodeHandle &Node) {
 311   assert(N && "DSNodeHandle does not point to a node yet!");
 312   N->mergeWith(Node, Offset);
 313 }
 314
 315 #endif