lib/Analysis/DataStructure/FunctionRepBuilder.h

   1 //===- FunctionRepBuilder.h - Structures for graph building ------*- C++ -*--=//
   2 //
   3 // This file defines the FunctionRepBuilder and InitVisitor classes that are
   4 // used to build the local data structure graph for a method.
   5 //
   6 //===----------------------------------------------------------------------===//
   7
   8 #ifndef DATA_STRUCTURE_METHOD_REP_BUILDER_H
   9 #define DATA_STRUCTURE_METHOD_REP_BUILDER_H
  10
  11 #include "llvm/Analysis/DataStructure.h"
  12 #include "llvm/Support/InstVisitor.h"
  13
  14 // DEBUG_DATA_STRUCTURE_CONSTRUCTION - Define this to 1 if you want debug output
  15 //#define DEBUG_DATA_STRUCTURE_CONSTRUCTION 1
  16
  17 class FunctionRepBuilder;
  18
  19 // InitVisitor - Used to initialize the worklists for data structure analysis.
  20 // Iterate over the instructions in the method, creating nodes for malloc and
  21 // call instructions.  Add all uses of these to the worklist of instructions
  22 // to process.
  23 //
  24 class InitVisitor : public InstVisitor<InitVisitor> {
  25   FunctionRepBuilder *Rep;
  26   Function *Func;
  27 public:
  28   InitVisitor(FunctionRepBuilder *R, Function *F) : Rep(R), Func(F) {}
  29
  30   void visitCallInst(CallInst *CI);
  31   void visitAllocationInst(AllocationInst *AI);
  32   void visitInstruction(Instruction *I);
  33
  34   // visitOperand - If the specified instruction operand is a global value, add
  35   // a node for it...
  36   //
  37   void visitOperand(Value *V);
  38 };
  39
  40
  41 // FunctionRepBuilder - This builder object creates the datastructure graph for
  42 // a method.
  43 //
  44 class FunctionRepBuilder : InstVisitor<FunctionRepBuilder> {
  45   friend class InitVisitor;
  46   FunctionDSGraph *F;
  47   PointerValSet RetNode;
  48
  49   // ValueMap - Mapping between values we are processing and the possible
  50   // datastructures that they may point to...
  51   map<Value*, PointerValSet> ValueMap;
  52
  53   // CallMap - Keep track of which call nodes correspond to which call insns.
  54   // The reverse mapping is stored in the CallDSNodes themselves.
  55   //
  56   map<CallInst*, CallDSNode*> CallMap;
  57
  58   // Worklist - Vector of (pointer typed) instructions to process still...
  59   std::vector<Instruction *> WorkList;
  60
  61   // Nodes - Keep track of all of the resultant nodes, because there may not
  62   // be edges connecting these to anything.
  63   //
  64   std::vector<AllocDSNode*>  AllocNodes;
  65   std::vector<ShadowDSNode*> ShadowNodes;
  66   std::vector<GlobalDSNode*> GlobalNodes;
  67   std::vector<CallDSNode*>   CallNodes;
  68
  69   // addAllUsesToWorkList - Add all of the instructions users of the specified
  70   // value to the work list for further processing...
  71   //
  72   void addAllUsesToWorkList(Value *V);
  73
  74 public:
  75   FunctionRepBuilder(FunctionDSGraph *f) : F(f) {
  76     initializeWorkList(F->getFunction());
  77     processWorkList();
  78   }
  79
  80   const std::vector<AllocDSNode*>  &getAllocNodes() const { return AllocNodes; }
  81   const std::vector<ShadowDSNode*> &getShadowNodes() const {return ShadowNodes;}
  82   const std::vector<GlobalDSNode*> &getGlobalNodes() const {return GlobalNodes;}
  83   const std::vector<CallDSNode*>   &getCallNodes() const { return CallNodes; }
  84
  85
  86   ShadowDSNode *makeSynthesizedShadow(const Type *Ty, DSNode *Parent);
  87
  88   const PointerValSet &getRetNode() const { return RetNode; }
  89
  90   const map<Value*, PointerValSet> &getValueMap() const { return ValueMap; }
  91 private:
  92   static PointerVal getIndexedPointerDest(const PointerVal &InP,
  93                                           const MemAccessInst *MAI);
  94
  95   void initializeWorkList(Function *Func);
  96   void processWorkList() {
  97     // While the worklist still has instructions to process, process them!
  98     while (!WorkList.empty()) {
  99       Instruction *I = WorkList.back(); WorkList.pop_back();
 100 #ifdef DEBUG_DATA_STRUCTURE_CONSTRUCTION
 101       cerr << "Processing worklist inst: " << I;
 102 #endif
 103
 104       visit(I);  // Dispatch to a visitXXX function based on instruction type...
 105 #ifdef DEBUG_DATA_STRUCTURE_CONSTRUCTION
 106       if (I->hasName() && ValueMap.count(I)) {
 107         cerr << "Inst %" << I->getName() << " value is:\n";
 108         ValueMap[I].print(cerr);
 109       }
 110 #endif
 111     }
 112   }
 113
 114   //===--------------------------------------------------------------------===//
 115   // Functions used to process the worklist of instructions...
 116   //
 117   // Allow the visitor base class to invoke these methods...
 118   friend class InstVisitor<FunctionRepBuilder>;
 119
 120   void visitGetElementPtrInst(GetElementPtrInst *GEP);
 121   void visitReturnInst(ReturnInst *RI);
 122   void visitLoadInst(LoadInst *LI);
 123   void visitStoreInst(StoreInst *SI);
 124   void visitCallInst(CallInst *CI);
 125   void visitPHINode(PHINode *PN);
 126   void visitSetCondInst(SetCondInst *SCI) {}  // SetEQ & friends are ignored
 127   void visitFreeInst(FreeInst *FI) {}         // Ignore free instructions
 128   void visitInstruction(Instruction *I) {
 129     std::cerr << "\n\n\nUNKNOWN INSTRUCTION type: ";
 130     I->dump();
 131     std::cerr << "\n\n\n";
 132     assert(0 && "Cannot proceed");
 133   }
 134 };
 135
 136 #endif