include/llvm/Analysis/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> ValueMap;
  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   /// getValueMap - Get a map that describes what the nodes the scalars in this
  62   /// function point to...
  63   ///
  64   std::map<Value*, DSNodeHandle> &getValueMap() { return ValueMap; }
  65   const std::map<Value*, DSNodeHandle> &getValueMap() const { return ValueMap;}
  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 ValueMap[V]; }
  78
  79   const DSNodeHandle &getRetNode() const { return RetNode; }
  80         DSNodeHandle &getRetNode()       { return RetNode; }
  81
  82   unsigned getGraphSize() const {
  83     return Nodes.size();
  84   }
  85
  86   void print(std::ostream &O) const;
  87   void dump() const;
  88   void writeGraphToFile(std::ostream &O, const std::string &GraphName) const;
  89
  90   // maskNodeTypes - Apply a mask to all of the node types in the graph.  This
  91   // is useful for clearing out markers like Scalar or Incomplete.
  92   //
  93   void maskNodeTypes(unsigned char Mask);
  94   void maskIncompleteMarkers() { maskNodeTypes(~DSNode::Incomplete); }
  95
  96   // markIncompleteNodes - Traverse the graph, identifying nodes that may be
  97   // modified by other functions that have not been resolved yet.  This marks
  98   // nodes that are reachable through three sources of "unknownness":
  99   //   Global Variables, Function Calls, and Incoming Arguments
 100   //
 101   // For any node that may have unknown components (because something outside
 102   // the scope of current analysis may have modified it), the 'Incomplete' flag
 103   // is added to the NodeType.
 104   //
 105   void markIncompleteNodes(bool markFormalArgs = true);
 106
 107   // removeTriviallyDeadNodes - After the graph has been constructed, this
 108   // method removes all unreachable nodes that are created because they got
 109   // merged with other nodes in the graph.
 110   //
 111   void removeTriviallyDeadNodes(bool KeepAllGlobals = false);
 112
 113   // removeDeadNodes - Use a more powerful reachability analysis to eliminate
 114   // subgraphs that are unreachable.  This often occurs because the data
 115   // structure doesn't "escape" into it's caller, and thus should be eliminated
 116   // from the caller's graph entirely.  This is only appropriate to use when
 117   // inlining graphs.
 118   //
 119   void removeDeadNodes(bool KeepAllGlobals = false, bool KeepCalls = true);
 120
 121   // cloneInto - Clone the specified DSGraph into the current graph, returning
 122   // the Return node of the graph.  The translated ValueMap for the old function
 123   // is filled into the OldValMap member.
 124   // If StripScalars (StripAllocas) is set to true, Scalar (Alloca) markers
 125   // are removed from the graph as the graph is being cloned.
 126   //
 127   DSNodeHandle cloneInto(const DSGraph &G,
 128                          std::map<Value*, DSNodeHandle> &OldValMap,
 129                          std::map<const DSNode*, DSNode*> &OldNodeMap,
 130                          bool StripScalars = false, bool StripAllocas = false);
 131
 132 #if 0
 133   // cloneGlobalInto - Clone the given global node (or the node for the given
 134   // GlobalValue) from the GlobalsGraph and all its target links (recursively).
 135   //
 136   DSNode* cloneGlobalInto(const DSNode* GNode);
 137   DSNode* cloneGlobalInto(GlobalValue* GV) {
 138     assert(!GV || (((DSGraph*) GlobalsGraph)->ValueMap[GV] != 0));
 139     return GV? cloneGlobalInto(((DSGraph*) GlobalsGraph)->ValueMap[GV]) : 0;
 140   }
 141 #endif
 142
 143 private:
 144   bool isNodeDead(DSNode *N);
 145 };
 146
 147 #endif