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