include/llvm/Analysis/DataStructure.h

   1 //===- DataStructure.h - Build a Module's call graph -------------*- C++ -*--=//
   2 //
   3 // Implement the LLVM data structure analysis library.
   4 //
   5 //===----------------------------------------------------------------------===//
   6
   7 #ifndef LLVM_ANALYSIS_DATA_STRUCTURE_H
   8 #define LLVM_ANALYSIS_DATA_STRUCTURE_H
   9
  10 #include "llvm/Pass.h"
  11 #include <string>
  12
  13 class Type;
  14 class CallInst;
  15 class AllocationInst;
  16 class FunctionArgument;
  17 class DSNode;
  18 class FunctionRepBuilder;
  19 class GlobalValue;
  20 class FunctionDSGraph;
  21 class DataStructure;
  22
  23 // FIXME: move this somewhere private
  24 unsigned countPointerFields(const Type *Ty);
  25
  26 // PointerVal - Represent a pointer to a datastructure.  The pointer points to
  27 // a node, and can index into it.  This is used for getelementptr instructions,
  28 // which do not affect which node a pointer points to, but does change the field
  29 // index
  30 //
  31 struct PointerVal {
  32   DSNode *Node;
  33   unsigned Index;  // Index into Node->FieldLinks[]
  34 public:
  35   PointerVal(DSNode *N, unsigned Idx = 0) : Node(N), Index(Idx) {}
  36
  37   DSNode *getNode() const { return Node; }
  38   unsigned getIndex() const { return Index; }
  39
  40   inline bool operator==(DSNode *N) const { return Node == N; }
  41   inline bool operator!=(DSNode *N) const { return Node != N; }
  42
  43   // operator< - Allow insertion into a map...
  44   bool operator<(const PointerVal &PV) const {
  45     return Node < PV.Node || (Node == PV.Node && Index < PV.Index);
  46   }
  47
  48   inline bool operator==(const PointerVal &PV) const {
  49     return Node == PV.Node && Index == PV.Index;
  50   }
  51   inline bool operator!=(const PointerVal &PV) const { return !operator==(PV); }
  52
  53   void print(std::ostream &O) const;
  54 };
  55
  56
  57 // PointerValSet - This class represents a list of pointer values.  The add
  58 // method is used to add values to the set, and ensures that duplicates cannot
  59 // happen.
  60 //
  61 class PointerValSet {
  62   std::vector<PointerVal> Vals;
  63   void dropRefs();
  64   void addRefs();
  65 public:
  66   PointerValSet() {}
  67   PointerValSet(const PointerValSet &PVS) : Vals(PVS.Vals) { addRefs(); }
  68   ~PointerValSet() { dropRefs(); }
  69   const PointerValSet &operator=(const PointerValSet &PVS);
  70
  71   // operator< - Allow insertion into a map...
  72   bool operator<(const PointerValSet &PVS) const;
  73   bool operator==(const PointerValSet &PVS) const;
  74
  75   const PointerVal &operator[](unsigned i) const { return Vals[i]; }
  76
  77   unsigned size() const { return Vals.size(); }
  78   bool empty() const { return Vals.empty(); }
  79   void clear() { dropRefs(); Vals.clear(); }
  80
  81   // add - Add the specified pointer, or contents of the specified PVS to this
  82   // pointer set.  If a 'Pointer' value is provided, notify the underlying data
  83   // structure node that the pointer is pointing to it, so that it can be
  84   // invalidated if neccesary later.  True is returned if the value is new to
  85   // this pointer.
  86   //
  87   bool add(const PointerVal &PV, Value *Pointer = 0);
  88   bool add(const PointerValSet &PVS, Value *Pointer = 0) {
  89     bool Changed = false;
  90     for (unsigned i = 0, e = PVS.size(); i != e; ++i)
  91       Changed |= add(PVS[i], Pointer);
  92     return Changed;
  93   }
  94
  95   // removePointerTo - Remove a single pointer val that points to the specified
  96   // node...
  97   void removePointerTo(DSNode *Node);
  98
  99   void print(std::ostream &O) const;
 100 };
 101
 102
 103 //===----------------------------------------------------------------------===//
 104 // DSNode - Base class for all data structure nodes...
 105 //
 106 // This class keeps track of its type, the pointer fields in the data structure,
 107 // and a list of LLVM values that are pointing to this node.
 108 //
 109 class DSNode {
 110   friend class FunctionDSGraph;
 111   const Type *Ty;
 112   std::vector<PointerValSet> FieldLinks;
 113   std::vector<Value*> Pointers;   // Values pointing to me...
 114   std::vector<PointerValSet*> Referrers;
 115
 116   DSNode(const DSNode &);         // DO NOT IMPLEMENT
 117   void operator=(const DSNode &); // DO NOT IMPLEMENT
 118 public:
 119   enum NodeTy {
 120     NewNode, CallNode, ShadowNode, ArgNode, GlobalNode
 121   } NodeType;
 122
 123   DSNode(enum NodeTy NT, const Type *T);
 124   virtual ~DSNode() {
 125     dropAllReferences();
 126     assert(Referrers.empty() && "Referrers to dead node exist!");
 127   }
 128
 129   unsigned getNumLinks() const { return FieldLinks.size(); }
 130   PointerValSet &getLink(unsigned i) {
 131     assert(i < getNumLinks() && "Field links access out of range...");
 132     return FieldLinks[i];
 133   }
 134
 135   // addReferrer - Keep the referrer set up to date...
 136   void addReferrer(PointerValSet *PVS) { Referrers.push_back(PVS); }
 137   void removeReferrer(PointerValSet *PVS);
 138   const std::vector<PointerValSet*> &getReferrers() const { return Referrers; }
 139
 140   // removeAllIncomingEdges - Erase all edges in the graph that point to
 141   // this node
 142   void removeAllIncomingEdges();
 143
 144   void addPointer(Value *V) { Pointers.push_back(V); }
 145   const std::vector<Value*> &getPointers() const { return Pointers; }
 146
 147   const Type *getType() const { return Ty; }
 148
 149   void print(std::ostream &O) const;
 150
 151   virtual std::string getCaption() const = 0;
 152   virtual const std::vector<PointerValSet> *getAuxLinks() const {
 153     return 0;  // Default to nothing...
 154   }
 155
 156   // isEquivalentTo - Return true if the nodes should be merged...
 157   virtual bool isEquivalentTo(DSNode *Node) const = 0;
 158
 159   DSNode *clone() const {
 160     DSNode *New = cloneImpl();
 161     // Add all of the pointers to the new node...
 162     for (unsigned pn = 0, pe = Pointers.size(); pn != pe; ++pn)
 163       New->addPointer(Pointers[pn]);
 164     return New;
 165   }
 166
 167
 168   virtual void dropAllReferences() {
 169     FieldLinks.clear();
 170   }
 171
 172   static bool classof(const DSNode *N) { return true; }
 173 protected:
 174   virtual DSNode *cloneImpl() const = 0;
 175   virtual void mapNode(std::map<const DSNode*, DSNode*> &NodeMap,
 176                        const DSNode *Old);
 177 };
 178
 179
 180 // AllocDSNode - Represent all allocation (malloc or alloca) in the program.
 181 //
 182 class AllocDSNode : public DSNode {
 183   AllocationInst *Allocation;
 184 public:
 185   AllocDSNode(AllocationInst *V);
 186
 187   virtual std::string getCaption() const;
 188
 189   bool isAllocaNode() const;
 190   bool isMallocNode() const { return !isAllocaNode(); }
 191
 192   AllocationInst *getAllocation() const { return Allocation; }
 193
 194   // isEquivalentTo - Return true if the nodes should be merged...
 195   virtual bool isEquivalentTo(DSNode *Node) const;
 196
 197   // Support type inquiry through isa, cast, and dyn_cast...
 198   static bool classof(const AllocDSNode *) { return true; }
 199   static bool classof(const DSNode *N) { return N->NodeType == NewNode; }
 200 protected:
 201   virtual AllocDSNode *cloneImpl() const { return new AllocDSNode(Allocation); }
 202 };
 203
 204
 205 // GlobalDSNode - Represent the memory location that a global variable occupies
 206 //
 207 class GlobalDSNode : public DSNode {
 208   GlobalValue *Val;
 209 public:
 210   GlobalDSNode(GlobalValue *V);
 211
 212   GlobalValue *getGlobal() const { return Val; }
 213
 214   virtual std::string getCaption() const;
 215
 216   // isEquivalentTo - Return true if the nodes should be merged...
 217   virtual bool isEquivalentTo(DSNode *Node) const;
 218
 219   // Support type inquiry through isa, cast, and dyn_cast...
 220   static bool classof(const GlobalDSNode *) { return true; }
 221   static bool classof(const DSNode *N) { return N->NodeType == GlobalNode; }
 222 private:
 223   virtual GlobalDSNode *cloneImpl() const { return new GlobalDSNode(Val); }
 224 };
 225
 226
 227 // CallDSNode - Represent a call instruction in the program...
 228 //
 229 class CallDSNode : public DSNode {
 230   friend class FunctionDSGraph;
 231   CallInst *CI;
 232   std::vector<PointerValSet> ArgLinks;
 233 public:
 234   CallDSNode(CallInst *CI);
 235
 236   CallInst *getCall() const { return CI; }
 237
 238   const std::vector<PointerValSet> *getAuxLinks() const { return &ArgLinks; }
 239   virtual std::string getCaption() const;
 240
 241   bool addArgValue(unsigned ArgNo, const PointerValSet &PVS) {
 242     return ArgLinks[ArgNo].add(PVS);
 243   }
 244
 245   unsigned getNumArgs() const { return ArgLinks.size(); }
 246   const PointerValSet &getArgValues(unsigned ArgNo) const {
 247     assert(ArgNo < ArgLinks.size() && "Arg # out of range!");
 248     return ArgLinks[ArgNo];
 249   }
 250   const std::vector<PointerValSet> &getArgs() const { return ArgLinks; }
 251
 252   virtual void dropAllReferences() {
 253     DSNode::dropAllReferences();
 254     ArgLinks.clear();
 255   }
 256
 257   // isEquivalentTo - Return true if the nodes should be merged...
 258   virtual bool isEquivalentTo(DSNode *Node) const;
 259
 260   // Support type inquiry through isa, cast, and dyn_cast...
 261   static bool classof(const CallDSNode *) { return true; }
 262   static bool classof(const DSNode *N) { return N->NodeType == CallNode; }
 263 private:
 264   virtual CallDSNode *cloneImpl() const { return new CallDSNode(CI); }
 265   virtual void mapNode(std::map<const DSNode*, DSNode*> &NodeMap,
 266                        const DSNode *Old);
 267 };
 268
 269
 270 // ArgDSNode - Represent an incoming argument to the current function...
 271 //
 272 class ArgDSNode : public DSNode {
 273   FunctionArgument *FuncArg;
 274 public:
 275   ArgDSNode(FunctionArgument *MA);
 276   virtual std::string getCaption() const;
 277
 278   // isEquivalentTo - Return true if the nodes should be merged...
 279   virtual bool isEquivalentTo(DSNode *Node) const;
 280
 281   // Support type inquiry through isa, cast, and dyn_cast...
 282   static bool classof(const ArgDSNode *) { return true; }
 283   static bool classof(const DSNode *N) { return N->NodeType == ArgNode; }
 284 private:
 285   virtual ArgDSNode *cloneImpl() const { return new ArgDSNode(FuncArg); }
 286 };
 287
 288
 289 // ShadowDSNode - Represent a chunk of memory that we need to be able to
 290 // address.  These are generated due to (for example) pointer type method
 291 // arguments... if the pointer is dereferenced, we need to have a node to point
 292 // to.  When functions are integrated into each other, shadow nodes are
 293 // resolved.
 294 //
 295 // Shadow nodes may be marked as "critical" nodes when they are created.  This
 296 // mark indicates that the node is the result of a function call, the value
 297 // pointed to by an incoming argument, or the value pointed to by a global
 298 // variable [fixme todo].  Since it is not possible to know what these nodes
 299 // point to, given just the current context, they are marked "Critical" to avoid
 300 // having the shadow node merger eliminate them.
 301 //
 302 class ShadowDSNode : public DSNode {
 303   friend class FunctionDSGraph;
 304   DSNode *Parent;
 305   Module *Mod;
 306   ShadowDSNode *ShadowParent;   // Nonnull if this is a synthesized node...
 307   std::vector<std::pair<const Type *, ShadowDSNode *> > SynthNodes;
 308   bool CriticalNode;
 309 public:
 310   ShadowDSNode(DSNode *Parent, Module *M, bool Critical = false);
 311   virtual std::string getCaption() const;
 312
 313   // synthesizeNode - Create a new shadow node that is to be linked into this
 314   // chain..
 315   //
 316   ShadowDSNode *synthesizeNode(const Type *Ty, FunctionRepBuilder *Rep);
 317
 318   bool isCriticalNode() const { return CriticalNode; }
 319   void resetCriticalMark() { CriticalNode = false; }
 320
 321   // isEquivalentTo - Return true if the nodes should be merged...
 322   virtual bool isEquivalentTo(DSNode *Node) const;
 323
 324   // Support type inquiry through isa, cast, and dyn_cast...
 325   static bool classof(const ShadowDSNode *) { return true; }
 326   static bool classof(const DSNode *N) { return N->NodeType == ShadowNode; }
 327
 328 private:
 329   ShadowDSNode(const Type *Ty, Module *M, ShadowDSNode *ShadParent);
 330 protected:
 331   virtual void mapNode(std::map<const DSNode*, DSNode*> &NodeMap,
 332                        const DSNode *Old);
 333   virtual ShadowDSNode *cloneImpl() const {
 334     if (ShadowParent)
 335       return new ShadowDSNode(getType(), Mod, ShadowParent);
 336     else
 337       return new ShadowDSNode(Parent, Mod, CriticalNode);
 338   }
 339 };
 340
 341
 342 // FunctionDSGraph - The graph that represents a method.
 343 //
 344 class FunctionDSGraph {
 345   Function *Func;
 346   std::vector<ArgDSNode*>    ArgNodes;
 347   std::vector<AllocDSNode*>  AllocNodes;
 348   std::vector<ShadowDSNode*> ShadowNodes;
 349   std::vector<GlobalDSNode*> GlobalNodes;
 350   std::vector<CallDSNode*>   CallNodes;
 351   PointerValSet RetNode;             // Node that gets returned...
 352   std::map<Value*, PointerValSet> ValueMap;
 353
 354   // cloneFunctionIntoSelf - Clone the specified method graph into the current
 355   // method graph, returning the Return's set of the graph.  If ValueMap is set
 356   // to true, the ValueMap of the function is cloned into this function as well
 357   // as the data structure graph itself.
 358   //
 359   PointerValSet cloneFunctionIntoSelf(const FunctionDSGraph &G, bool ValueMap);
 360   bool RemoveUnreachableNodes();
 361   bool UnlinkUndistinguishableNodes();
 362   void MarkEscapeableNodesReachable(std::vector<bool> &RSN,
 363                                     std::vector<bool> &RAN);
 364
 365 private:
 366   // Define the interface only accessable to DataStructure
 367   friend class DataStructure;
 368   FunctionDSGraph(Function *F);
 369   FunctionDSGraph(const FunctionDSGraph &DSG);
 370   ~FunctionDSGraph();
 371
 372   void computeClosure(const DataStructure &DS);
 373 public:
 374
 375   Function *getFunction() const { return Func; }
 376
 377   // getEscapingAllocations - Add all allocations that escape the current
 378   // function to the specified vector.
 379   //
 380   void getEscapingAllocations(std::vector<AllocDSNode*> &Allocs);
 381
 382   // getNonEscapingAllocations - Add all allocations that do not escape the
 383   // current function to the specified vector.
 384   //
 385   void getNonEscapingAllocations(std::vector<AllocDSNode*> &Allocs);
 386
 387   // getValueMap - Get a map that describes what the nodes the scalars in this
 388   // function point to...
 389   //
 390   std::map<Value*, PointerValSet> &getValueMap() { return ValueMap; }
 391
 392
 393
 394   void printFunction(std::ostream &O, const char *Label) const;
 395 };
 396
 397
 398 // FIXME: This should be a FunctionPass.  When the pass framework sees a 'Pass'
 399 // that uses the output of a FunctionPass, it should automatically build a map
 400 // of output from the method pass that the pass can use.
 401 //
 402 class DataStructure : public Pass {
 403   // DSInfo, one intraprocedural and one closed graph for each method...
 404   typedef std::map<Function*, std::pair<FunctionDSGraph*,
 405                                         FunctionDSGraph*> > InfoMap;
 406   mutable InfoMap DSInfo;
 407 public:
 408   static AnalysisID ID;            // DataStructure Analysis ID
 409
 410   DataStructure(AnalysisID id) { assert(id == ID); }
 411   ~DataStructure() { releaseMemory(); }
 412
 413   // run - Do nothing, because methods are analyzed lazily
 414   virtual bool run(Module *TheModule) { return false; }
 415
 416   // getDSGraph - Return the data structure graph for the specified method.
 417   // Since method graphs are lazily computed, we may have to create one on the
 418   // fly here.
 419   //
 420   FunctionDSGraph &getDSGraph(Function *F) const {
 421     std::pair<FunctionDSGraph*, FunctionDSGraph*> &N = DSInfo[F];
 422     if (N.first) return *N.first;
 423     return *(N.first = new FunctionDSGraph(F));
 424   }
 425
 426   // getClosedDSGraph - Return the data structure graph for the specified
 427   // method. Since method graphs are lazily computed, we may have to create one
 428   // on the fly here. This is different than the normal DSGraph for the method
 429   // because any function calls that are resolvable will have the data structure
 430   // graphs of the called function incorporated into this function as well.
 431   //
 432   FunctionDSGraph &getClosedDSGraph(Function *F) const {
 433     std::pair<FunctionDSGraph*, FunctionDSGraph*> &N = DSInfo[F];
 434     if (N.second) return *N.second;
 435     N.second = new FunctionDSGraph(getDSGraph(F));
 436     N.second->computeClosure(*this);
 437     return *N.second;
 438   }
 439
 440   // invalidateFunction - Inform this analysis that you changed the specified
 441   // function, so the graphs that depend on it are out of date.
 442   //
 443   void invalidateFunction(Function *F) const {
 444     // FIXME: THis should invalidate all functions who have inlined the
 445     // specified graph!
 446     //
 447     std::pair<FunctionDSGraph*, FunctionDSGraph*> &N = DSInfo[F];
 448     delete N.first;
 449     delete N.second;
 450     N.first = N.second = 0;
 451   }
 452
 453   // print - Print out the analysis results...
 454   void print(std::ostream &O, Module *M) const;
 455
 456   // If the pass pipeline is done with this pass, we can release our memory...
 457   virtual void releaseMemory();
 458
 459   // getAnalysisUsageInfo - This obviously provides a call graph
 460   virtual void getAnalysisUsageInfo(AnalysisSet &Required,
 461                                     AnalysisSet &Destroyed,
 462                                     AnalysisSet &Provided) {
 463     Provided.push_back(ID);
 464   }
 465 };
 466
 467 #endif