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