include/llvm/Analysis/DataStructure/DSNode.h

   1 //===- DSNode.h - Node definition for datastructure graphs ------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // Data structure graph nodes and some implementation of DSNodeHandle.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_ANALYSIS_DSNODE_H
  15 #define LLVM_ANALYSIS_DSNODE_H
  16
  17 #include "llvm/Analysis/DSSupport.h"
  18
  19 template<typename BaseType>
  20 class DSNodeIterator;          // Data structure graph traversal iterator
  21
  22 //===----------------------------------------------------------------------===//
  23 /// DSNode - Data structure node class
  24 ///
  25 /// This class represents an untyped memory object of Size bytes.  It keeps
  26 /// track of any pointers that have been stored into the object as well as the
  27 /// different types represented in this object.
  28 ///
  29 class DSNode {
  30   /// NumReferrers - The number of DSNodeHandles pointing to this node... if
  31   /// this is a forwarding node, then this is the number of node handles which
  32   /// are still forwarding over us.
  33   ///
  34   unsigned NumReferrers;
  35
  36   /// ForwardNH - This NodeHandle contain the node (and offset into the node)
  37   /// that this node really is.  When nodes get folded together, the node to be
  38   /// eliminated has these fields filled in, otherwise ForwardNH.getNode() is
  39   /// null.
  40   DSNodeHandle ForwardNH;
  41
  42   /// Size - The current size of the node.  This should be equal to the size of
  43   /// the current type record.
  44   ///
  45   unsigned Size;
  46
  47   /// ParentGraph - The graph this node is currently embedded into.
  48   ///
  49   DSGraph *ParentGraph;
  50
  51   /// Ty - Keep track of the current outer most type of this object, in addition
  52   /// to whether or not it has been indexed like an array or not.  If the
  53   /// isArray bit is set, the node cannot grow.
  54   ///
  55   const Type *Ty;                 // The type itself...
  56
  57   /// Links - Contains one entry for every sizeof(void*) bytes in this memory
  58   /// object.  Note that if the node is not a multiple of size(void*) bytes
  59   /// large, that there is an extra entry for the "remainder" of the node as
  60   /// well.  For this reason, nodes of 1 byte in size do have one link.
  61   ///
  62   std::vector<DSNodeHandle> Links;
  63
  64   /// Globals - The list of global values that are merged into this node.
  65   ///
  66   std::vector<GlobalValue*> Globals;
  67
  68   void operator=(const DSNode &); // DO NOT IMPLEMENT
  69   DSNode(const DSNode &);         // DO NOT IMPLEMENT
  70 public:
  71   enum NodeTy {
  72     ShadowNode  = 0,        // Nothing is known about this node...
  73     AllocaNode  = 1 << 0,   // This node was allocated with alloca
  74     HeapNode    = 1 << 1,   // This node was allocated with malloc
  75     GlobalNode  = 1 << 2,   // This node was allocated by a global var decl
  76     UnknownNode = 1 << 3,   // This node points to unknown allocated memory
  77     Incomplete  = 1 << 4,   // This node may not be complete
  78
  79     Modified    = 1 << 5,   // This node is modified in this context
  80     Read        = 1 << 6,   // This node is read in this context
  81
  82     Array       = 1 << 7,   // This node is treated like an array
  83     //#ifndef NDEBUG
  84     DEAD        = 1 << 8,   // This node is dead and should not be pointed to
  85     //#endif
  86
  87     Composition = AllocaNode | HeapNode | GlobalNode | UnknownNode,
  88   };
  89
  90   /// NodeType - A union of the above bits.  "Shadow" nodes do not add any flags
  91   /// to the nodes in the data structure graph, so it is possible to have nodes
  92   /// with a value of 0 for their NodeType.
  93   ///
  94 private:
  95   unsigned short NodeType;
  96 public:
  97
  98   DSNode(const Type *T, DSGraph *G);
  99   DSNode(const DSNode &, DSGraph *G);
 100
 101   ~DSNode() {
 102     dropAllReferences();
 103     assert(hasNoReferrers() && "Referrers to dead node exist!");
 104   }
 105
 106   // Iterator for graph interface... Defined in DSGraphTraits.h
 107   typedef DSNodeIterator<DSNode> iterator;
 108   typedef DSNodeIterator<const DSNode> const_iterator;
 109   inline iterator begin();
 110   inline iterator end();
 111   inline const_iterator begin() const;
 112   inline const_iterator end() const;
 113
 114   //===--------------------------------------------------
 115   // Accessors
 116
 117   /// getSize - Return the maximum number of bytes occupied by this object...
 118   ///
 119   unsigned getSize() const { return Size; }
 120
 121   // getType - Return the node type of this object...
 122   const Type *getType() const { return Ty; }
 123   bool isArray() const { return NodeType & Array; }
 124
 125   /// hasNoReferrers - Return true if nothing is pointing to this node at all.
 126   ///
 127   bool hasNoReferrers() const { return getNumReferrers() == 0; }
 128
 129   /// getNumReferrers - This method returns the number of referrers to the
 130   /// current node.  Note that if this node is a forwarding node, this will
 131   /// return the number of nodes forwarding over the node!
 132   unsigned getNumReferrers() const { return NumReferrers; }
 133
 134   DSGraph *getParentGraph() const { return ParentGraph; }
 135   void setParentGraph(DSGraph *G) { ParentGraph = G; }
 136
 137   /// getForwardNode - This method returns the node that this node is forwarded
 138   /// to, if any.
 139   DSNode *getForwardNode() const { return ForwardNH.getNode(); }
 140   void stopForwarding() {
 141     assert(!ForwardNH.isNull() &&
 142            "Node isn't forwarding, cannot stopForwarding!");
 143     ForwardNH.setNode(0);
 144   }
 145
 146   /// hasLink - Return true if this memory object has a link in slot #LinkNo
 147   ///
 148   bool hasLink(unsigned Offset) const {
 149     assert((Offset & ((1 << DS::PointerShift)-1)) == 0 &&
 150            "Pointer offset not aligned correctly!");
 151     unsigned Index = Offset >> DS::PointerShift;
 152     assert(Index < Links.size() && "Link index is out of range!");
 153     return Links[Index].getNode();
 154   }
 155
 156   /// getLink - Return the link at the specified offset.
 157   DSNodeHandle &getLink(unsigned Offset) {
 158     assert((Offset & ((1 << DS::PointerShift)-1)) == 0 &&
 159            "Pointer offset not aligned correctly!");
 160     unsigned Index = Offset >> DS::PointerShift;
 161     assert(Index < Links.size() && "Link index is out of range!");
 162     return Links[Index];
 163   }
 164   const DSNodeHandle &getLink(unsigned Offset) const {
 165     assert((Offset & ((1 << DS::PointerShift)-1)) == 0 &&
 166            "Pointer offset not aligned correctly!");
 167     unsigned Index = Offset >> DS::PointerShift;
 168     assert(Index < Links.size() && "Link index is out of range!");
 169     return Links[Index];
 170   }
 171
 172   /// getNumLinks - Return the number of links in a node...
 173   ///
 174   unsigned getNumLinks() const { return Links.size(); }
 175
 176   /// mergeTypeInfo - This method merges the specified type into the current
 177   /// node at the specified offset.  This may update the current node's type
 178   /// record if this gives more information to the node, it may do nothing to
 179   /// the node if this information is already known, or it may merge the node
 180   /// completely (and return true) if the information is incompatible with what
 181   /// is already known.
 182   ///
 183   /// This method returns true if the node is completely folded, otherwise
 184   /// false.
 185   ///
 186   bool mergeTypeInfo(const Type *Ty, unsigned Offset,
 187                      bool FoldIfIncompatible = true);
 188
 189   /// foldNodeCompletely - If we determine that this node has some funny
 190   /// behavior happening to it that we cannot represent, we fold it down to a
 191   /// single, completely pessimistic, node.  This node is represented as a
 192   /// single byte with a single TypeEntry of "void" with isArray = true.
 193   ///
 194   void foldNodeCompletely();
 195
 196   /// isNodeCompletelyFolded - Return true if this node has been completely
 197   /// folded down to something that can never be expanded, effectively losing
 198   /// all of the field sensitivity that may be present in the node.
 199   ///
 200   bool isNodeCompletelyFolded() const;
 201
 202   /// setLink - Set the link at the specified offset to the specified
 203   /// NodeHandle, replacing what was there.  It is uncommon to use this method,
 204   /// instead one of the higher level methods should be used, below.
 205   ///
 206   void setLink(unsigned Offset, const DSNodeHandle &NH) {
 207     assert((Offset & ((1 << DS::PointerShift)-1)) == 0 &&
 208            "Pointer offset not aligned correctly!");
 209     unsigned Index = Offset >> DS::PointerShift;
 210     assert(Index < Links.size() && "Link index is out of range!");
 211     Links[Index] = NH;
 212   }
 213
 214   /// getPointerSize - Return the size of a pointer for the current target.
 215   ///
 216   unsigned getPointerSize() const { return DS::PointerSize; }
 217
 218   /// addEdgeTo - Add an edge from the current node to the specified node.  This
 219   /// can cause merging of nodes in the graph.
 220   ///
 221   void addEdgeTo(unsigned Offset, const DSNodeHandle &NH);
 222
 223   /// mergeWith - Merge this node and the specified node, moving all links to
 224   /// and from the argument node into the current node, deleting the node
 225   /// argument.  Offset indicates what offset the specified node is to be merged
 226   /// into the current node.
 227   ///
 228   /// The specified node may be a null pointer (in which case, nothing happens).
 229   ///
 230   void mergeWith(const DSNodeHandle &NH, unsigned Offset);
 231
 232   /// addGlobal - Add an entry for a global value to the Globals list.  This
 233   /// also marks the node with the 'G' flag if it does not already have it.
 234   ///
 235   void addGlobal(GlobalValue *GV);
 236   const std::vector<GlobalValue*> &getGlobals() const { return Globals; }
 237
 238   /// maskNodeTypes - Apply a mask to the node types bitfield.
 239   ///
 240   void maskNodeTypes(unsigned Mask) {
 241     NodeType &= Mask;
 242   }
 243
 244   /// getNodeFlags - Return all of the flags set on the node.  If the DEAD flag
 245   /// is set, hide it from the caller.
 246   unsigned getNodeFlags() const { return NodeType & ~DEAD; }
 247
 248   bool isAllocaNode()  const { return NodeType & AllocaNode; }
 249   bool isHeapNode()    const { return NodeType & HeapNode; }
 250   bool isGlobalNode()  const { return NodeType & GlobalNode; }
 251   bool isUnknownNode() const { return NodeType & UnknownNode; }
 252
 253   bool isModified() const   { return NodeType & Modified; }
 254   bool isRead() const       { return NodeType & Read; }
 255
 256   bool isIncomplete() const { return NodeType & Incomplete; }
 257   bool isComplete() const   { return !isIncomplete(); }
 258   bool isDeadNode() const   { return NodeType & DEAD; }
 259
 260   DSNode *setAllocaNodeMarker()  { NodeType |= AllocaNode;  return this; }
 261   DSNode *setHeapNodeMarker()    { NodeType |= HeapNode;    return this; }
 262   DSNode *setGlobalNodeMarker()  { NodeType |= GlobalNode;  return this; }
 263   DSNode *setUnknownNodeMarker() { NodeType |= UnknownNode; return this; }
 264
 265   DSNode *setIncompleteMarker() { NodeType |= Incomplete; return this; }
 266   DSNode *setModifiedMarker()   { NodeType |= Modified;   return this; }
 267   DSNode *setReadMarker()       { NodeType |= Read;       return this; }
 268
 269   void makeNodeDead() {
 270     Globals.clear();
 271     assert(hasNoReferrers() && "Dead node shouldn't have refs!");
 272     NodeType = DEAD;
 273   }
 274
 275   /// forwardNode - Mark this node as being obsolete, and all references to it
 276   /// should be forwarded to the specified node and offset.
 277   ///
 278   void forwardNode(DSNode *To, unsigned Offset);
 279
 280   void print(std::ostream &O, const DSGraph *G) const;
 281   void dump() const;
 282
 283   void assertOK() const;
 284
 285   void dropAllReferences() {
 286     Links.clear();
 287     if (!ForwardNH.isNull())
 288       ForwardNH.setNode(0);
 289   }
 290
 291   /// remapLinks - Change all of the Links in the current node according to the
 292   /// specified mapping.
 293   void remapLinks(hash_map<const DSNode*, DSNodeHandle> &OldNodeMap);
 294
 295   /// markReachableNodes - This method recursively traverses the specified
 296   /// DSNodes, marking any nodes which are reachable.  All reachable nodes it
 297   /// adds to the set, which allows it to only traverse visited nodes once.
 298   ///
 299   void markReachableNodes(hash_set<DSNode*> &ReachableNodes);
 300
 301 private:
 302   friend class DSNodeHandle;
 303
 304   // static mergeNodes - Helper for mergeWith()
 305   static void MergeNodes(DSNodeHandle& CurNodeH, DSNodeHandle& NH);
 306 };
 307
 308
 309 //===----------------------------------------------------------------------===//
 310 // Define inline DSNodeHandle functions that depend on the definition of DSNode
 311 //
 312 inline DSNode *DSNodeHandle::getNode() const {
 313   assert((!N || Offset < N->Size || (N->Size == 0 && Offset == 0) ||
 314           !N->ForwardNH.isNull()) && "Node handle offset out of range!");
 315   if (!N || N->ForwardNH.isNull())
 316     return N;
 317
 318   return HandleForwarding();
 319 }
 320
 321 inline void DSNodeHandle::setNode(DSNode *n) {
 322   assert(!n || !n->getForwardNode() && "Cannot set node to a forwarded node!");
 323   if (N) N->NumReferrers--;
 324   N = n;
 325   if (N) {
 326     N->NumReferrers++;
 327     if (Offset >= N->Size) {
 328       assert((Offset == 0 || N->Size == 1) &&
 329              "Pointer to non-collapsed node with invalid offset!");
 330       Offset = 0;
 331     }
 332   }
 333   assert(!N || ((N->NodeType & DSNode::DEAD) == 0));
 334   assert((!N || Offset < N->Size || (N->Size == 0 && Offset == 0) ||
 335           !N->ForwardNH.isNull()) && "Node handle offset out of range!");
 336 }
 337
 338 inline bool DSNodeHandle::hasLink(unsigned Num) const {
 339   assert(N && "DSNodeHandle does not point to a node yet!");
 340   return getNode()->hasLink(Num+Offset);
 341 }
 342
 343
 344 /// getLink - Treat this current node pointer as a pointer to a structure of
 345 /// some sort.  This method will return the pointer a mem[this+Num]
 346 ///
 347 inline const DSNodeHandle &DSNodeHandle::getLink(unsigned Off) const {
 348   assert(N && "DSNodeHandle does not point to a node yet!");
 349   return getNode()->getLink(Offset+Off);
 350 }
 351 inline DSNodeHandle &DSNodeHandle::getLink(unsigned Off) {
 352   assert(N && "DSNodeHandle does not point to a node yet!");
 353   return getNode()->getLink(Off+Offset);
 354 }
 355
 356 inline void DSNodeHandle::setLink(unsigned Off, const DSNodeHandle &NH) {
 357   assert(N && "DSNodeHandle does not point to a node yet!");
 358   getNode()->setLink(Off+Offset, NH);
 359 }
 360
 361 ///  addEdgeTo - Add an edge from the current node to the specified node.  This
 362 /// can cause merging of nodes in the graph.
 363 ///
 364 inline void DSNodeHandle::addEdgeTo(unsigned Off, const DSNodeHandle &Node) {
 365   assert(N && "DSNodeHandle does not point to a node yet!");
 366   getNode()->addEdgeTo(Off+Offset, Node);
 367 }
 368
 369 /// mergeWith - Merge the logical node pointed to by 'this' with the node
 370 /// pointed to by 'N'.
 371 ///
 372 inline void DSNodeHandle::mergeWith(const DSNodeHandle &Node) {
 373   if (N != 0)
 374     getNode()->mergeWith(Node, Offset);
 375   else     // No node to merge with, so just point to Node
 376     *this = Node;
 377 }
 378
 379 #endif