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   public:
  29     DSAA() : TD(0) {}
  30
  31     //------------------------------------------------
  32     // Implement the Pass API
  33     //
  34
  35     // run - Build up the result graph, representing the pointer graph for the
  36     // program.
  37     //
  38     bool runOnModule(Module &M) {
  39       InitializeAliasAnalysis(this);
  40       TD = &getAnalysis<TDDataStructures>();
  41       BU = &getAnalysis<BUDataStructures>();
  42       return false;
  43     }
  44
  45     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  46       AliasAnalysis::getAnalysisUsage(AU);
  47       AU.setPreservesAll();                         // Does not transform code
  48       AU.addRequiredTransitive<TDDataStructures>(); // Uses TD Datastructures
  49       AU.addRequiredTransitive<BUDataStructures>(); // Uses BU Datastructures
  50     }
  51
  52     //------------------------------------------------
  53     // Implement the AliasAnalysis API
  54     //
  55
  56     AliasResult alias(const Value *V1, unsigned V1Size,
  57                       const Value *V2, unsigned V2Size);
  58
  59     ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size);
  60     ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) {
  61       return AliasAnalysis::getModRefInfo(CS1,CS2);
  62     }
  63
  64     virtual void deleteValue(Value *V) {
  65       BU->deleteValue(V);
  66       TD->deleteValue(V);
  67     }
  68
  69     virtual void copyValue(Value *From, Value *To) {
  70       if (From == To) return;
  71       BU->copyValue(From, To);
  72       TD->copyValue(From, To);
  73     }
  74
  75   private:
  76     DSGraph *getGraphForValue(const Value *V);
  77   };
  78
  79   // Register the pass...
  80   RegisterOpt<DSAA> X("ds-aa", "Data Structure Graph Based Alias Analysis");
  81
  82   // Register as an implementation of AliasAnalysis
  83   RegisterAnalysisGroup<AliasAnalysis, DSAA> Y;
  84 }
  85
  86 ModulePass *llvm::createDSAAPass() { return new DSAA(); }
  87
  88 // getGraphForValue - Return the DSGraph to use for queries about the specified
  89 // value...
  90 //
  91 DSGraph *DSAA::getGraphForValue(const Value *V) {
  92   if (const Instruction *I = dyn_cast<Instruction>(V))
  93     return &TD->getDSGraph(*I->getParent()->getParent());
  94   else if (const Argument *A = dyn_cast<Argument>(V))
  95     return &TD->getDSGraph(*A->getParent());
  96   else if (const BasicBlock *BB = dyn_cast<BasicBlock>(V))
  97     return &TD->getDSGraph(*BB->getParent());
  98   return 0;
  99 }
 100
 101 AliasAnalysis::AliasResult DSAA::alias(const Value *V1, unsigned V1Size,
 102                                        const Value *V2, unsigned V2Size) {
 103   if (V1 == V2) return MustAlias;
 104
 105   DSGraph *G1 = getGraphForValue(V1);
 106   DSGraph *G2 = getGraphForValue(V2);
 107   assert((!G1 || !G2 || G1 == G2) && "Alias query for 2 different functions?");
 108
 109   // Get the graph to use...
 110   DSGraph &G = *(G1 ? G1 : (G2 ? G2 : &TD->getGlobalsGraph()));
 111
 112   const DSGraph::ScalarMapTy &GSM = G.getScalarMap();
 113   DSGraph::ScalarMapTy::const_iterator I = GSM.find((Value*)V1);
 114   if (I == GSM.end()) return NoAlias;
 115
 116   DSGraph::ScalarMapTy::const_iterator J = GSM.find((Value*)V2);
 117   if (J == GSM.end()) return NoAlias;
 118
 119   DSNode  *N1 = I->second.getNode(),  *N2 = J->second.getNode();
 120   unsigned O1 = I->second.getOffset(), O2 = J->second.getOffset();
 121   if (N1 == 0 || N2 == 0)
 122     return MayAlias;  // Can't tell whether anything aliases null.
 123
 124   // We can only make a judgment of one of the nodes is complete...
 125   if (N1->isComplete() || N2->isComplete()) {
 126     if (N1 != N2)
 127       return NoAlias;   // Completely different nodes.
 128
 129     // See if they point to different offsets...  if so, we may be able to
 130     // determine that they do not alias...
 131     if (O1 != O2) {
 132       if (O2 < O1) {    // Ensure that O1 <= O2
 133         std::swap(V1, V2);
 134         std::swap(O1, O2);
 135         std::swap(V1Size, V2Size);
 136       }
 137
 138       if (O1+V1Size <= O2)
 139         return NoAlias;
 140     }
 141   }
 142
 143   // FIXME: we could improve on this by checking the globals graph for aliased
 144   // global queries...
 145   return AliasAnalysis::alias(V1, V1Size, V2, V2Size);
 146 }
 147
 148 /// getModRefInfo - does a callsite modify or reference a value?
 149 ///
 150 AliasAnalysis::ModRefResult
 151 DSAA::getModRefInfo(CallSite CS, Value *P, unsigned Size) {
 152   AliasAnalysis::ModRefResult Result =AliasAnalysis::getModRefInfo(CS, P, Size);
 153   Function *F = CS.getCalledFunction();
 154
 155   if (!F || Result == NoModRef)
 156     return Result;
 157
 158   if (F->isExternal()) {
 159     // If we are calling an external function, and if this global doesn't escape
 160     // the portion of the program we have analyzed, we can draw conclusions
 161     // based on whether the global escapes the program.
 162     Function *Caller = CS.getInstruction()->getParent()->getParent();
 163     DSGraph *G = &TD->getDSGraph(*Caller);
 164     DSScalarMap::iterator NI = G->getScalarMap().find(P);
 165     if (NI == G->getScalarMap().end()) {
 166       // If it wasn't in the local function graph, check the global graph.  This
 167       // can occur for globals who are locally reference but hoisted out to the
 168       // globals graph despite that.
 169       G = G->getGlobalsGraph();
 170       NI = G->getScalarMap().find(P);
 171       if (NI == G->getScalarMap().end())
 172         return Result;
 173     }
 174
 175     // If we found a node and it's complete, it cannot be passed out to the
 176     // called function.
 177     if (NI->second.getNode()->isComplete())
 178       return NoModRef;
 179     return Result;
 180   }
 181
 182   // Get the graphs for the callee and caller.  Note that we want the BU graph
 183   // for the callee because we don't want all caller's effects incorporated!
 184   const Function *Caller = CS.getInstruction()->getParent()->getParent();
 185   DSGraph &CallerTDGraph = TD->getDSGraph(*Caller);
 186   DSGraph &CalleeBUGraph = BU->getDSGraph(*F);
 187
 188   // Figure out which node in the TD graph this pointer corresponds to.
 189   DSScalarMap &CallerSM = CallerTDGraph.getScalarMap();
 190   DSScalarMap::iterator NI = CallerSM.find(P);
 191   if (NI == CallerSM.end()) {
 192     if (isa<ConstantPointerNull>(P) || isa<UndefValue>(P))
 193       Result = NoModRef;                 // null is never modified :)
 194     else {
 195       assert(isa<GlobalVariable>(P) &&
 196     cast<GlobalVariable>(P)->getType()->getElementType()->isFirstClassType() &&
 197              "This isn't a global that DSA inconsiderately dropped "
 198              "from the graph?");
 199
 200       DSGraph &GG = *CallerTDGraph.getGlobalsGraph();
 201       DSScalarMap::iterator NI = GG.getScalarMap().find(P);
 202       if (NI != GG.getScalarMap().end() && !NI->second.isNull()) {
 203         // Otherwise, if the node is only M or R, return this.  This can be
 204         // useful for globals that should be marked const but are not.
 205         DSNode *N = NI->second.getNode();
 206         if (!N->isModified())
 207           Result = (ModRefResult)(Result & ~Mod);
 208         if (!N->isRead())
 209           Result = (ModRefResult)(Result & ~Ref);
 210       }
 211     }
 212     return Result;
 213   }
 214
 215   const DSNode *N = NI->second.getNode();
 216   assert(N && "Null pointer in scalar map??");
 217
 218   // Compute the mapping from nodes in the callee graph to the nodes in the
 219   // caller graph for this call site.
 220   DSGraph::NodeMapTy CalleeCallerMap;
 221   DSCallSite DSCS = CallerTDGraph.getDSCallSiteForCallSite(CS);
 222   CallerTDGraph.computeCalleeCallerMapping(DSCS, *F, CalleeBUGraph,
 223                                            CalleeCallerMap);
 224
 225   // Loop over all of the nodes in the callee that correspond to "N", keeping
 226   // track of aggregate mod/ref info.
 227   bool NeverReads = true, NeverWrites = true;
 228   for (DSGraph::NodeMapTy::iterator I = CalleeCallerMap.begin(),
 229          E = CalleeCallerMap.end(); I != E; ++I)
 230     if (I->second.getNode() == N) {
 231       if (I->first->isModified())
 232         NeverWrites = false;
 233       if (I->first->isRead())
 234         NeverReads = false;
 235       if (NeverReads == false && NeverWrites == false)
 236         return Result;
 237     }
 238
 239   if (NeverWrites)      // We proved it was not modified.
 240     Result = ModRefResult(Result & ~Mod);
 241   if (NeverReads)       // We proved it was not read.
 242     Result = ModRefResult(Result & ~Ref);
 243
 244   return Result;
 245 }