include/llvm/Analysis/DataStructure/DSGraph.h

   1 //===- DSGraph.h - Represent a collection of data structures ----*- C++ -*-===//
   2 //
   3 // This header defines the data structure graph.
   4 //
   5 //===----------------------------------------------------------------------===//
   6
   7 #ifndef LLVM_ANALYSIS_DSGRAPH_H
   8 #define LLVM_ANALYSIS_DSGRAPH_H
   9
  10 #include "llvm/Analysis/DSNode.h"
  11
  12 //===----------------------------------------------------------------------===//
  13 /// DSGraph - The graph that represents a function.
  14 ///
  15 class DSGraph {
  16   Function *Func;
  17   std::vector<DSNode*> Nodes;
  18   DSNodeHandle RetNode;                          // Node that gets returned...
  19   std::map<Value*, DSNodeHandle> ScalarMap;
  20
  21 #if 0
  22   // GlobalsGraph -- Reference to the common graph of globally visible objects.
  23   // This includes GlobalValues, New nodes, Cast nodes, and Calls.
  24   //
  25   GlobalDSGraph* GlobalsGraph;
  26 #endif
  27
  28   // FunctionCalls - This vector maintains a single entry for each call
  29   // instruction in the current graph.  Each call entry contains DSNodeHandles
  30   // that refer to the arguments that are passed into the function call.  The
  31   // first entry in the vector is the scalar that holds the return value for the
  32   // call, the second is the function scalar being invoked, and the rest are
  33   // pointer arguments to the function.
  34   //
  35   std::vector<DSCallSite> FunctionCalls;
  36
  37   void operator=(const DSGraph &); // DO NOT IMPLEMENT
  38 public:
  39   DSGraph() : Func(0) {}           // Create a new, empty, DSGraph.
  40   DSGraph(Function &F);            // Compute the local DSGraph
  41
  42   // Copy ctor - If you want to capture the node mapping between the source and
  43   // destination graph, you may optionally do this by specifying a map to record
  44   // this into.
  45   DSGraph(const DSGraph &DSG);
  46   DSGraph(const DSGraph &DSG, std::map<const DSNode*, DSNode*> &BUNodeMap);
  47   ~DSGraph();
  48
  49   bool hasFunction() const { return Func != 0; }
  50   Function &getFunction() const { return *Func; }
  51
  52   /// getNodes - Get a vector of all the nodes in the graph
  53   ///
  54   const std::vector<DSNode*> &getNodes() const { return Nodes; }
  55         std::vector<DSNode*> &getNodes()       { return Nodes; }
  56
  57   /// addNode - Add a new node to the graph.
  58   ///
  59   void addNode(DSNode *N) { Nodes.push_back(N); }
  60
  61   /// getScalarMap - Get a map that describes what the nodes the scalars in this
  62   /// function point to...
  63   ///
  64   std::map<Value*, DSNodeHandle> &getScalarMap() { return ScalarMap; }
  65   const std::map<Value*, DSNodeHandle> &getScalarMap() const {return ScalarMap;}
  66
  67   std::vector<DSCallSite> &getFunctionCalls() {
  68     return FunctionCalls;
  69   }
  70   const std::vector<DSCallSite> &getFunctionCalls() const {
  71     return FunctionCalls;
  72   }
  73
  74   /// getNodeForValue - Given a value that is used or defined in the body of the
  75   /// current function, return the DSNode that it points to.
  76   ///
  77   DSNodeHandle &getNodeForValue(Value *V) { return ScalarMap[V]; }
  78
  79   const DSNodeHandle &getNodeForValue(Value *V) const {
  80     std::map<Value*, DSNodeHandle>::const_iterator I = ScalarMap.find(V);
  81     assert(I != ScalarMap.end() &&
  82            "Use non-const lookup function if node may not be in the map");
  83     return I->second;
  84   }
  85
  86   const DSNodeHandle &getRetNode() const { return RetNode; }
  87         DSNodeHandle &getRetNode()       { return RetNode; }
  88
  89   unsigned getGraphSize() const {
  90     return Nodes.size();
  91   }
  92
  93   void print(std::ostream &O) const;
  94   void dump() const;
  95   void writeGraphToFile(std::ostream &O, const std::string &GraphName) const;
  96
  97   // maskNodeTypes - Apply a mask to all of the node types in the graph.  This
  98   // is useful for clearing out markers like Scalar or Incomplete.
  99   //
 100   void maskNodeTypes(unsigned char Mask);
 101   void maskIncompleteMarkers() { maskNodeTypes(~DSNode::Incomplete); }
 102
 103   // markIncompleteNodes - Traverse the graph, identifying nodes that may be
 104   // modified by other functions that have not been resolved yet.  This marks
 105   // nodes that are reachable through three sources of "unknownness":
 106   //   Global Variables, Function Calls, and Incoming Arguments
 107   //
 108   // For any node that may have unknown components (because something outside
 109   // the scope of current analysis may have modified it), the 'Incomplete' flag
 110   // is added to the NodeType.
 111   //
 112   void markIncompleteNodes(bool markFormalArgs = true);
 113
 114   // removeTriviallyDeadNodes - After the graph has been constructed, this
 115   // method removes all unreachable nodes that are created because they got
 116   // merged with other nodes in the graph.
 117   //
 118   void removeTriviallyDeadNodes(bool KeepAllGlobals = false);
 119
 120   // removeDeadNodes - Use a more powerful reachability analysis to eliminate
 121   // subgraphs that are unreachable.  This often occurs because the data
 122   // structure doesn't "escape" into it's caller, and thus should be eliminated
 123   // from the caller's graph entirely.  This is only appropriate to use when
 124   // inlining graphs.
 125   //
 126   void removeDeadNodes(bool KeepAllGlobals = false, bool KeepCalls = true);
 127
 128   // cloneInto - Clone the specified DSGraph into the current graph, returning
 129   // the Return node of the graph.  The translated ScalarMap for the old
 130   // function is filled into the OldValMap member.  If StripScalars
 131   // (StripAllocas) is set to true, Scalar (Alloca) markers are removed from the
 132   // graph as the graph is being cloned.
 133   //
 134   DSNodeHandle cloneInto(const DSGraph &G,
 135                          std::map<Value*, DSNodeHandle> &OldValMap,
 136                          std::map<const DSNode*, DSNode*> &OldNodeMap,
 137                          bool StripAllocas = false);
 138
 139   /// mergeInGraph - The method is used for merging graphs together.  If the
 140   /// argument graph is not *this, it makes a clone of the specified graph, then
 141   /// merges the nodes specified in the call site with the formal arguments in
 142   /// the graph.  If the StripAlloca's argument is true then Alloca markers are
 143   /// removed from nodes.
 144   ///
 145   void mergeInGraph(DSCallSite &CS, const DSGraph &Graph, bool StripAllocas);
 146
 147
 148 #if 0
 149   // cloneGlobalInto - Clone the given global node (or the node for the given
 150   // GlobalValue) from the GlobalsGraph and all its target links (recursively).
 151   //
 152   DSNode* cloneGlobalInto(const DSNode* GNode);
 153   DSNode* cloneGlobalInto(GlobalValue* GV) {
 154     assert(!GV || (((DSGraph*) GlobalsGraph)->ScalarMap[GV] != 0));
 155     return GV? cloneGlobalInto(((DSGraph*) GlobalsGraph)->ScalarMap[GV]) : 0;
 156   }
 157 #endif
 158
 159 private:
 160   bool isNodeDead(DSNode *N);
 161 };
 162
 163 #endif