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