include/llvm/Analysis/DataStructure.h

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