lib/Analysis/DataStructure/DataStructureAA.cpp

   1 //===- DataStructureAA.cpp - Data Structure Based Alias Analysis ----------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass uses the top-down data structure graphs to implement a simple
  11 // context sensitive alias analysis.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/Constants.h"
  16 #include "llvm/DerivedTypes.h"
  17 #include "llvm/Module.h"
  18 #include "llvm/Analysis/AliasAnalysis.h"
  19 #include "llvm/Analysis/Passes.h"
  20 #include "llvm/Analysis/DataStructure/DataStructure.h"
  21 #include "llvm/Analysis/DataStructure/DSGraph.h"
  22 using namespace llvm;
  23
  24 namespace {
  25   class DSAA : public ModulePass, public AliasAnalysis {
  26     TDDataStructures *TD;
  27     BUDataStructures *BU;
  28
  29     // These members are used to cache mod/ref information to make us return
  30     // results faster, particularly for aa-eval.  On the first request of
  31     // mod/ref information for a particular call site, we compute and store the
  32     // calculated nodemap for the call site.  Any time DSA info is updated we
  33     // free this information, and when we move onto a new call site, this
  34     // information is also freed.
  35     CallSite MapCS;
  36     std::multimap<DSNode*, const DSNode*> CallerCalleeMap;
  37   public:
  38     DSAA() : TD(0) {}
  39     ~DSAA() {
  40       InvalidateCache();
  41     }
  42
  43     void InvalidateCache() {
  44       MapCS = CallSite();
  45       CallerCalleeMap.clear();
  46     }
  47
  48     //------------------------------------------------
  49     // Implement the Pass API
  50     //
  51
  52     // run - Build up the result graph, representing the pointer graph for the
  53     // program.
  54     //
  55     bool runOnModule(Module &M) {
  56       InitializeAliasAnalysis(this);
  57       TD = &getAnalysis<TDDataStructures>();
  58       BU = &getAnalysis<BUDataStructures>();
  59       return false;
  60     }
  61
  62     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  63       AliasAnalysis::getAnalysisUsage(AU);
  64       AU.setPreservesAll();                         // Does not transform code
  65       AU.addRequiredTransitive<TDDataStructures>(); // Uses TD Datastructures
  66       AU.addRequiredTransitive<BUDataStructures>(); // Uses BU Datastructures
  67     }
  68
  69     //------------------------------------------------
  70     // Implement the AliasAnalysis API
  71     //
  72
  73     AliasResult alias(const Value *V1, unsigned V1Size,
  74                       const Value *V2, unsigned V2Size);
  75
  76     ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size);
  77     ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) {
  78       return AliasAnalysis::getModRefInfo(CS1,CS2);
  79     }
  80
  81     virtual void deleteValue(Value *V) {
  82       InvalidateCache();
  83       BU->deleteValue(V);
  84       TD->deleteValue(V);
  85     }
  86
  87     virtual void copyValue(Value *From, Value *To) {
  88       if (From == To) return;
  89       InvalidateCache();
  90       BU->copyValue(From, To);
  91       TD->copyValue(From, To);
  92     }
  93
  94   private:
  95     DSGraph *getGraphForValue(const Value *V);
  96   };
  97
  98   // Register the pass...
  99   RegisterOpt<DSAA> X("ds-aa", "Data Structure Graph Based Alias Analysis");
 100
 101   // Register as an implementation of AliasAnalysis
 102   RegisterAnalysisGroup<AliasAnalysis, DSAA> Y;
 103 }
 104
 105 ModulePass *llvm::createDSAAPass() { return new DSAA(); }
 106
 107 // getGraphForValue - Return the DSGraph to use for queries about the specified
 108 // value...
 109 //
 110 DSGraph *DSAA::getGraphForValue(const Value *V) {
 111   if (const Instruction *I = dyn_cast<Instruction>(V))
 112     return &TD->getDSGraph(*I->getParent()->getParent());
 113   else if (const Argument *A = dyn_cast<Argument>(V))
 114     return &TD->getDSGraph(*A->getParent());
 115   else if (const BasicBlock *BB = dyn_cast<BasicBlock>(V))
 116     return &TD->getDSGraph(*BB->getParent());
 117   return 0;
 118 }
 119
 120 AliasAnalysis::AliasResult DSAA::alias(const Value *V1, unsigned V1Size,
 121                                        const Value *V2, unsigned V2Size) {
 122   if (V1 == V2) return MustAlias;
 123
 124   DSGraph *G1 = getGraphForValue(V1);
 125   DSGraph *G2 = getGraphForValue(V2);
 126   assert((!G1 || !G2 || G1 == G2) && "Alias query for 2 different functions?");
 127
 128   // Get the graph to use...
 129   DSGraph &G = *(G1 ? G1 : (G2 ? G2 : &TD->getGlobalsGraph()));
 130
 131   const DSGraph::ScalarMapTy &GSM = G.getScalarMap();
 132   DSGraph::ScalarMapTy::const_iterator I = GSM.find((Value*)V1);
 133   if (I == GSM.end()) return NoAlias;
 134
 135   DSGraph::ScalarMapTy::const_iterator J = GSM.find((Value*)V2);
 136   if (J == GSM.end()) return NoAlias;
 137
 138   DSNode  *N1 = I->second.getNode(),  *N2 = J->second.getNode();
 139   unsigned O1 = I->second.getOffset(), O2 = J->second.getOffset();
 140   if (N1 == 0 || N2 == 0)
 141     // Can't tell whether anything aliases null.
 142     return AliasAnalysis::alias(V1, V1Size, V2, V2Size);
 143
 144   // We can only make a judgment if one of the nodes is complete.
 145   if (N1->isComplete() || N2->isComplete()) {
 146     if (N1 != N2)
 147       return NoAlias;   // Completely different nodes.
 148
 149     // See if they point to different offsets...  if so, we may be able to
 150     // determine that they do not alias...
 151     if (O1 != O2) {
 152       if (O2 < O1) {    // Ensure that O1 <= O2
 153         std::swap(V1, V2);
 154         std::swap(O1, O2);
 155         std::swap(V1Size, V2Size);
 156       }
 157
 158       if (O1+V1Size <= O2)
 159         return NoAlias;
 160     }
 161   }
 162
 163   // FIXME: we could improve on this by checking the globals graph for aliased
 164   // global queries...
 165   return AliasAnalysis::alias(V1, V1Size, V2, V2Size);
 166 }
 167
 168 /// getModRefInfo - does a callsite modify or reference a value?
 169 ///
 170 AliasAnalysis::ModRefResult
 171 DSAA::getModRefInfo(CallSite CS, Value *P, unsigned Size) {
 172   DSNode *N = 0;
 173   // First step, check our cache.
 174   if (CS.getInstruction() == MapCS.getInstruction()) {
 175     {
 176       const Function *Caller = CS.getInstruction()->getParent()->getParent();
 177       DSGraph &CallerTDGraph = TD->getDSGraph(*Caller);
 178
 179       // Figure out which node in the TD graph this pointer corresponds to.
 180       DSScalarMap &CallerSM = CallerTDGraph.getScalarMap();
 181       DSScalarMap::iterator NI = CallerSM.find(P);
 182       if (NI == CallerSM.end()) {
 183         InvalidateCache();
 184         return DSAA::getModRefInfo(CS, P, Size);
 185       }
 186       N = NI->second.getNode();
 187     }
 188
 189   HaveMappingInfo:
 190     assert(N && "Null pointer in scalar map??");
 191
 192     typedef std::multimap<DSNode*, const DSNode*>::iterator NodeMapIt;
 193     std::pair<NodeMapIt, NodeMapIt> Range = CallerCalleeMap.equal_range(N);
 194
 195     // Loop over all of the nodes in the callee that correspond to "N", keeping
 196     // track of aggregate mod/ref info.
 197     bool NeverReads = true, NeverWrites = true;
 198     for (; Range.first != Range.second; ++Range.first) {
 199       if (Range.first->second->isModified())
 200         NeverWrites = false;
 201       if (Range.first->second->isRead())
 202         NeverReads = false;
 203       if (NeverReads == false && NeverWrites == false)
 204         return AliasAnalysis::getModRefInfo(CS, P, Size);
 205     }
 206
 207     ModRefResult Result = ModRef;
 208     if (NeverWrites)      // We proved it was not modified.
 209       Result = ModRefResult(Result & ~Mod);
 210     if (NeverReads)       // We proved it was not read.
 211       Result = ModRefResult(Result & ~Ref);
 212
 213     return ModRefResult(Result & AliasAnalysis::getModRefInfo(CS, P, Size));
 214   }
 215
 216   // Any cached info we have is for the wrong function.
 217   InvalidateCache();
 218
 219   Function *F = CS.getCalledFunction();
 220
 221   if (!F) return AliasAnalysis::getModRefInfo(CS, P, Size);
 222
 223   if (F->isExternal()) {
 224     // If we are calling an external function, and if this global doesn't escape
 225     // the portion of the program we have analyzed, we can draw conclusions
 226     // based on whether the global escapes the program.
 227     Function *Caller = CS.getInstruction()->getParent()->getParent();
 228     DSGraph *G = &TD->getDSGraph(*Caller);
 229     DSScalarMap::iterator NI = G->getScalarMap().find(P);
 230     if (NI == G->getScalarMap().end()) {
 231       // If it wasn't in the local function graph, check the global graph.  This
 232       // can occur for globals who are locally reference but hoisted out to the
 233       // globals graph despite that.
 234       G = G->getGlobalsGraph();
 235       NI = G->getScalarMap().find(P);
 236       if (NI == G->getScalarMap().end())
 237         return AliasAnalysis::getModRefInfo(CS, P, Size);
 238     }
 239
 240     // If we found a node and it's complete, it cannot be passed out to the
 241     // called function.
 242     if (NI->second.getNode()->isComplete())
 243       return NoModRef;
 244     return AliasAnalysis::getModRefInfo(CS, P, Size);
 245   }
 246
 247   // Get the graphs for the callee and caller.  Note that we want the BU graph
 248   // for the callee because we don't want all caller's effects incorporated!
 249   const Function *Caller = CS.getInstruction()->getParent()->getParent();
 250   DSGraph &CallerTDGraph = TD->getDSGraph(*Caller);
 251   DSGraph &CalleeBUGraph = BU->getDSGraph(*F);
 252
 253   // Figure out which node in the TD graph this pointer corresponds to.
 254   DSScalarMap &CallerSM = CallerTDGraph.getScalarMap();
 255   DSScalarMap::iterator NI = CallerSM.find(P);
 256   if (NI == CallerSM.end()) {
 257     ModRefResult Result = ModRef;
 258     if (isa<ConstantPointerNull>(P) || isa<UndefValue>(P))
 259       return NoModRef;                 // null is never modified :)
 260     else {
 261       assert(isa<GlobalVariable>(P) &&
 262     cast<GlobalVariable>(P)->getType()->getElementType()->isFirstClassType() &&
 263              "This isn't a global that DSA inconsiderately dropped "
 264              "from the graph?");
 265
 266       DSGraph &GG = *CallerTDGraph.getGlobalsGraph();
 267       DSScalarMap::iterator NI = GG.getScalarMap().find(P);
 268       if (NI != GG.getScalarMap().end() && !NI->second.isNull()) {
 269         // Otherwise, if the node is only M or R, return this.  This can be
 270         // useful for globals that should be marked const but are not.
 271         DSNode *N = NI->second.getNode();
 272         if (!N->isModified())
 273           Result = (ModRefResult)(Result & ~Mod);
 274         if (!N->isRead())
 275           Result = (ModRefResult)(Result & ~Ref);
 276       }
 277     }
 278
 279     if (Result == NoModRef) return Result;
 280     return ModRefResult(Result & AliasAnalysis::getModRefInfo(CS, P, Size));
 281   }
 282
 283   // Compute the mapping from nodes in the callee graph to the nodes in the
 284   // caller graph for this call site.
 285   DSGraph::NodeMapTy CalleeCallerMap;
 286   DSCallSite DSCS = CallerTDGraph.getDSCallSiteForCallSite(CS);
 287   CallerTDGraph.computeCalleeCallerMapping(DSCS, *F, CalleeBUGraph,
 288                                            CalleeCallerMap);
 289
 290   // Remember the mapping and the call site for future queries.
 291   MapCS = CS;
 292
 293   // Invert the mapping into CalleeCallerInvMap.
 294   for (DSGraph::NodeMapTy::iterator I = CalleeCallerMap.begin(),
 295          E = CalleeCallerMap.end(); I != E; ++I)
 296     CallerCalleeMap.insert(std::make_pair(I->second.getNode(), I->first));
 297
 298   N = NI->second.getNode();
 299   goto HaveMappingInfo;
 300 }