path: root/include/llvm/Analysis/DataStructure/DSGraph.h

//===- DSGraph.h - Represent a collection of data structures ----*- C++ -*-===//
//
// This header defines the primative classes that make up a data structure
// graph.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_DSGRAPH_H
#define LLVM_ANALYSIS_DSGRAPH_H

#include <vector>
#include <map>
#include <functional>

class Function;
class CallInst;
class Value;
class GlobalValue;
class Type;

class DSNode;                  // Each node in the graph
class DSGraph;                 // A graph for a function
class DSNodeIterator;          // Data structure graph traversal iterator


//===----------------------------------------------------------------------===//
/// DSNodeHandle - Implement a "handle" to a data structure node that takes care
/// of all of the add/un'refing of the node to prevent the backpointers in the
/// graph from getting out of date.  This class represents a "pointer" in the
/// graph, whose destination is an indexed offset into a node.
///
class DSNodeHandle {
  DSNode *N;
  unsigned Offset;
public:
  // Allow construction, destruction, and assignment...
  DSNodeHandle(DSNode *n = 0, unsigned offs = 0) : N(0), Offset(offs) {
    setNode(n);
  }
  DSNodeHandle(const DSNodeHandle &H) : N(0), Offset(H.Offset) { setNode(H.N); }
  ~DSNodeHandle() { setNode((DSNode*)0); }
  DSNodeHandle &operator=(const DSNodeHandle &H) {
    setNode(H.N); Offset = H.Offset;
    return *this;
  }

  bool operator<(const DSNodeHandle &H) const {  // Allow sorting
    return N < H.N || (N == H.N && Offset < H.Offset);
  }
  bool operator>(const DSNodeHandle &H) const { return H < *this; }
  bool operator==(const DSNodeHandle &H) const { // Allow comparison
    return N == H.N && Offset == H.Offset;
  }
  bool operator!=(const DSNodeHandle &H) const { return !operator==(H); }

  // Allow explicit conversion to DSNode...
  DSNode *getNode() const { return N; }
  unsigned getOffset() const { return Offset; }

  inline void setNode(DSNode *N);  // Defined inline later...
  void setOffset(unsigned O) { Offset = O; }

  void addEdgeTo(unsigned LinkNo, const DSNodeHandle &N);
  void addEdgeTo(const DSNodeHandle &N) { addEdgeTo(0, N); }

  /// mergeWith - Merge the logical node pointed to by 'this' with the node
  /// pointed to by 'N'.
  ///
  void mergeWith(const DSNodeHandle &N);

  // hasLink - Return true if there is a link at the specified offset...
  inline bool hasLink(unsigned Num) const;

  /// getLink - Treat this current node pointer as a pointer to a structure of
  /// some sort.  This method will return the pointer a mem[this+Num]
  ///
  inline const DSNodeHandle *getLink(unsigned Num) const;
  inline DSNodeHandle *getLink(unsigned Num);

  inline void setLink(unsigned Num, const DSNodeHandle &NH);
};


//===----------------------------------------------------------------------===//
/// DSNode - Data structure node class
///
/// This class represents an untyped memory object of Size bytes.  It keeps
/// track of any pointers that have been stored into the object as well as the
/// different types represented in this object.
///
class DSNode {
  /// Links - Contains one entry for every _distinct_ pointer field in the
  /// memory block.  These are demand allocated and indexed by the MergeMap
  /// vector.
  ///
  std::vector<DSNodeHandle> Links;

  /// MergeMap - Maps from every byte in the object to a signed byte number.
  /// This map is neccesary due to the merging that is possible as part of the
  /// unification algorithm.  To merge two distinct bytes of the object together
  /// into a single logical byte, the indexes for the two bytes are set to the
  /// same value.  This fully general merging is capable of representing all
  /// manners of array merging if neccesary.
  ///
  /// This map is also used to map outgoing pointers to various byte offsets in
  /// this data structure node.  If this value is >= 0, then it indicates that
  /// the numbered entry in the Links vector contains the outgoing edge for this
  /// byte offset.  In this way, the Links vector can be demand allocated and
  /// byte elements of the node may be merged without needing a Link allocated
  /// for it.
  ///
  /// Initially, each each element of the MergeMap is assigned a unique negative
  /// number, which are then merged as the unification occurs.
  ///
  std::vector<signed char> MergeMap;

  /// Referrers - Keep track of all of the node handles that point to this
  /// DSNode.  These pointers may need to be updated to point to a different
  /// node if this node gets merged with it.
  ///
  std::vector<DSNodeHandle*> Referrers;

  /// TypeRec - This structure is used to represent a single type that is held
  /// in a DSNode.
  struct TypeRec {
    const Type *Ty;                 // The type itself...
    unsigned Offset;                // The offset in the node
    bool isArray;                   // Have we accessed an array of elements?

    TypeRec() : Ty(0), Offset(0) {}
    TypeRec(const Type *T, unsigned O) : Ty(T), Offset(O) {}

    bool operator<(const TypeRec &TR) const {
      // Sort first by offset!
      return Offset < TR.Offset || (Offset == TR.Offset && Ty < TR.Ty);
    }
    bool operator==(const TypeRec &TR) const {
      return Ty == TR.Ty && Offset == TR.Offset;
    }
    bool operator!=(const TypeRec &TR) const { return !operator==(TR); }
  };

  /// TypeEntries - As part of the merging process of this algorithm, nodes of
  /// different types can be represented by this single DSNode.  This vector is
  /// kept sorted.
  ///
  std::vector<TypeRec> TypeEntries;

  /// Globals - The list of global values that are merged into this node.
  ///
  std::vector<GlobalValue*> Globals;

  void operator=(const DSNode &); // DO NOT IMPLEMENT
public:
  enum NodeTy {
    ShadowNode = 0,        // Nothing is known about this node...
    ScalarNode = 1 << 0,   // Scalar of the current function contains this value
    AllocaNode = 1 << 1,   // This node was allocated with alloca
    NewNode    = 1 << 2,   // This node was allocated with malloc
    GlobalNode = 1 << 3,   // This node was allocated by a global var decl
    Incomplete = 1 << 4,   // This node may not be complete
    Modified   = 1 << 5,   // This node is modified in this context
    Read       = 1 << 6,   // This node is read in this context
  };
  
  /// NodeType - A union of the above bits.  "Shadow" nodes do not add any flags
  /// to the nodes in the data structure graph, so it is possible to have nodes
  /// with a value of 0 for their NodeType.  Scalar and Alloca markers go away
  /// when function graphs are inlined.
  ///
  unsigned char NodeType;

  DSNode(enum NodeTy NT, const Type *T);
  DSNode(const DSNode &);

  ~DSNode() {
#ifndef NDEBUG
    dropAllReferences();  // Only needed to satisfy assertion checks...
    assert(Referrers.empty() && "Referrers to dead node exist!");
#endif
  }

  // Iterator for graph interface...
  typedef DSNodeIterator iterator;
  typedef DSNodeIterator const_iterator;
  inline iterator begin() const;   // Defined in DSGraphTraits.h
  inline iterator end() const;

  //===--------------------------------------------------
  // Accessors

  /// getSize - Return the maximum number of bytes occupied by this object...
  ///
  unsigned getSize() const { return MergeMap.size(); }

  // getTypeEntries - Return the possible types and their offsets in this object
  const std::vector<TypeRec> &getTypeEntries() const { return TypeEntries; }

  /// getReferrers - Return a list of the pointers to this node...
  ///
  const std::vector<DSNodeHandle*> &getReferrers() const { return Referrers; }

  /// isModified - Return true if this node may be modified in this context
  ///
  bool isModified() const { return (NodeType & Modified) != 0; }

  /// isRead - Return true if this node may be read in this context
  ///
  bool isRead() const { return (NodeType & Read) != 0; }


  /// hasLink - Return true if this memory object has a link at