include/llvm/Analysis/DataStructure.h

   1 //===- DataStructure.h - Build data structure 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 // Implement the LLVM data structure analysis library.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_ANALYSIS_DATA_STRUCTURE_H
  15 #define LLVM_ANALYSIS_DATA_STRUCTURE_H
  16
  17 #include "llvm/Pass.h"
  18 #include "llvm/Target/TargetData.h"
  19 #include "Support/hash_set"
  20
  21 namespace llvm {
  22
  23 class Type;
  24 class Instruction;
  25 class DSGraph;
  26 class DSNode;
  27
  28 // FIXME: move this stuff to a private header
  29 namespace DataStructureAnalysis {
  30   // isPointerType - Return true if this first class type is big enough to hold
  31   // a pointer.
  32   //
  33   bool isPointerType(const Type *Ty);
  34 }
  35
  36
  37 // LocalDataStructures - The analysis that computes the local data structure
  38 // graphs for all of the functions in the program.
  39 //
  40 // FIXME: This should be a Function pass that can be USED by a Pass, and would
  41 // be automatically preserved.  Until we can do that, this is a Pass.
  42 //
  43 class LocalDataStructures : public Pass {
  44   // DSInfo, one graph for each function
  45   hash_map<Function*, DSGraph*> DSInfo;
  46   DSGraph *GlobalsGraph;
  47 public:
  48   ~LocalDataStructures() { releaseMemory(); }
  49
  50   virtual bool run(Module &M);
  51
  52   bool hasGraph(const Function &F) const {
  53     return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
  54   }
  55
  56   // getDSGraph - Return the data structure graph for the specified function.
  57   DSGraph &getDSGraph(const Function &F) const {
  58     hash_map<Function*, DSGraph*>::const_iterator I =
  59       DSInfo.find(const_cast<Function*>(&F));
  60     assert(I != DSInfo.end() && "Function not in module!");
  61     return *I->second;
  62   }
  63
  64   DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
  65
  66   // print - Print out the analysis results...
  67   void print(std::ostream &O, const Module *M) const;
  68
  69   // If the pass pipeline is done with this pass, we can release our memory...
  70   virtual void releaseMemory();
  71
  72   // getAnalysisUsage - This obviously provides a data structure graph.
  73   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  74     AU.setPreservesAll();
  75     AU.addRequired<TargetData>();
  76   }
  77 };
  78
  79
  80 // BUDataStructures - The analysis that computes the interprocedurally closed
  81 // data structure graphs for all of the functions in the program.  This pass
  82 // only performs a "Bottom Up" propagation (hence the name).
  83 //
  84 class BUDataStructures : public Pass {
  85   // DSInfo, one graph for each function
  86   hash_map<Function*, DSGraph*> DSInfo;
  87   DSGraph *GlobalsGraph;
  88   hash_multimap<Instruction*, Function*> ActualCallees;
  89 public:
  90   ~BUDataStructures() { releaseMemory(); }
  91
  92   virtual bool run(Module &M);
  93
  94   bool hasGraph(const Function &F) const {
  95     return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
  96   }
  97
  98   // getDSGraph - Return the data structure graph for the specified function.
  99   DSGraph &getDSGraph(const Function &F) const {
 100     hash_map<Function*, DSGraph*>::const_iterator I =
 101       DSInfo.find(const_cast<Function*>(&F));
 102     assert(I != DSInfo.end() && "Function not in module!");
 103     return *I->second;
 104   }
 105
 106   DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
 107
 108   // print - Print out the analysis results...
 109   void print(std::ostream &O, const Module *M) const;
 110
 111   // If the pass pipeline is done with this pass, we can release our memory...
 112   virtual void releaseMemory();
 113
 114   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 115     AU.setPreservesAll();
 116     AU.addRequired<LocalDataStructures>();
 117   }
 118
 119   typedef hash_multimap<Instruction*, Function*> ActualCalleesTy;
 120   const ActualCalleesTy &getActualCallees() const {
 121     return ActualCallees;
 122   }
 123
 124 private:
 125   void calculateGraph(DSGraph &G);
 126
 127   void calculateReachableGraphs(Function *F);
 128
 129
 130   DSGraph &getOrCreateGraph(Function *F);
 131
 132   unsigned calculateGraphs(Function *F, std::vector<Function*> &Stack,
 133                            unsigned &NextID,
 134                            hash_map<Function*, unsigned> &ValMap);
 135 };
 136
 137
 138 // TDDataStructures - Analysis that computes new data structure graphs
 139 // for each function using the closed graphs for the callers computed
 140 // by the bottom-up pass.
 141 //
 142 class TDDataStructures : public Pass {
 143   // DSInfo, one graph for each function
 144   hash_map<Function*, DSGraph*> DSInfo;
 145   hash_set<Function*> ArgsRemainIncomplete;
 146   DSGraph *GlobalsGraph;
 147 public:
 148   ~TDDataStructures() { releaseMyMemory(); }
 149
 150   virtual bool run(Module &M);
 151
 152   bool hasGraph(const Function &F) const {
 153     return DSInfo.find(const_cast<Function*>(&F)) != DSInfo.end();
 154   }
 155
 156   // getDSGraph - Return the data structure graph for the specified function.
 157   DSGraph &getDSGraph(const Function &F) const {
 158     hash_map<Function*, DSGraph*>::const_iterator I =
 159       DSInfo.find(const_cast<Function*>(&F));
 160     assert(I != DSInfo.end() && "Function not in module!");
 161     return *I->second;
 162   }
 163
 164   DSGraph &getGlobalsGraph() const { return *GlobalsGraph; }
 165
 166   // print - Print out the analysis results...
 167   void print(std::ostream &O, const Module *M) const;
 168
 169   // If the pass pipeline is done with this pass, we can release our memory...
 170   virtual void releaseMyMemory();
 171
 172   // getAnalysisUsage - This obviously provides a data structure graph.
 173   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 174     AU.setPreservesAll();
 175     AU.addRequired<BUDataStructures>();
 176   }
 177
 178 private:
 179   void markReachableFunctionsExternallyAccessible(DSNode *N,
 180                                                   hash_set<DSNode*> &Visited);
 181
 182   void inlineGraphIntoCallees(DSGraph &G);
 183   DSGraph &getOrCreateDSGraph(Function &F);
 184   void ComputePostOrder(Function &F, hash_set<DSGraph*> &Visited,
 185                         std::vector<DSGraph*> &PostOrder,
 186                         const BUDataStructures::ActualCalleesTy &ActualCallees);
 187 };
 188
 189 } // End llvm namespace
 190
 191 #endif