lib/Analysis/DataStructure/Steensgaard.cpp

   1 //===- Steensgaard.cpp - Context Insensitive 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 data structure graphs to implement a simple context
  11 // insensitive alias analysis.  It does this by computing the local analysis
  12 // graphs for all of the functions, then merging them together into a single big
  13 // graph without cloning.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "llvm/Analysis/DataStructure/DataStructure.h"
  18 #include "llvm/Analysis/DataStructure/DSGraph.h"
  19 #include "llvm/Analysis/AliasAnalysis.h"
  20 #include "llvm/Analysis/Passes.h"
  21 #include "llvm/Module.h"
  22 #include "llvm/Support/Debug.h"
  23 using namespace llvm;
  24
  25 namespace {
  26   class Steens : public ModulePass, public AliasAnalysis {
  27     DSGraph *ResultGraph;
  28
  29     EquivalenceClasses<GlobalValue*> GlobalECs;  // Always empty
  30   public:
  31     Steens() : ResultGraph(0) {}
  32     ~Steens() {
  33       releaseMyMemory();
  34       assert(ResultGraph == 0 && "releaseMemory not called?");
  35     }
  36
  37     //------------------------------------------------
  38     // Implement the Pass API
  39     //
  40
  41     // run - Build up the result graph, representing the pointer graph for the
  42     // program.
  43     //
  44     bool runOnModule(Module &M);
  45
  46     virtual void releaseMyMemory() { delete ResultGraph; ResultGraph = 0; }
  47
  48     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  49       AliasAnalysis::getAnalysisUsage(AU);
  50       AU.setPreservesAll();                    // Does not transform code...
  51       AU.addRequired<LocalDataStructures>();   // Uses local dsgraph
  52     }
  53
  54     // print - Implement the Pass::print method...
  55     void print(std::ostream &O, const Module *M) const {
  56       assert(ResultGraph && "Result graph has not yet been computed!");
  57       ResultGraph->writeGraphToFile(O, "steensgaards");
  58     }
  59
  60     //------------------------------------------------
  61     // Implement the AliasAnalysis API
  62     //
  63
  64     AliasResult alias(const Value *V1, unsigned V1Size,
  65                       const Value *V2, unsigned V2Size);
  66
  67     ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size);
  68
  69   private:
  70     void ResolveFunctionCall(Function *F, const DSCallSite &Call,
  71                              DSNodeHandle &RetVal);
  72   };
  73
  74   // Register the pass...
  75   RegisterOpt<Steens> X("steens-aa",
  76                         "Steensgaard's alias analysis (DSGraph based)");
  77
  78   // Register as an implementation of AliasAnalysis
  79   RegisterAnalysisGroup<AliasAnalysis, Steens> Y;
  80 }
  81
  82 ModulePass *llvm::createSteensgaardPass() { return new Steens(); }
  83
  84 /// ResolveFunctionCall - Resolve the actual arguments of a call to function F
  85 /// with the specified call site descriptor.  This function links the arguments
  86 /// and the return value for the call site context-insensitively.
  87 ///
  88 void Steens::ResolveFunctionCall(Function *F, const DSCallSite &Call,
  89                                  DSNodeHandle &RetVal) {
  90   assert(ResultGraph != 0 && "Result graph not allocated!");
  91   DSGraph::ScalarMapTy &ValMap = ResultGraph->getScalarMap();
  92
  93   // Handle the return value of the function...
  94   if (Call.getRetVal().getNode() && RetVal.getNode())
  95     RetVal.mergeWith(Call.getRetVal());
  96
  97   // Loop over all pointer arguments, resolving them to their provided pointers
  98   unsigned PtrArgIdx = 0;
  99   for (Function::arg_iterator AI = F->arg_begin(), AE = F->arg_end();
 100        AI != AE && PtrArgIdx < Call.getNumPtrArgs(); ++AI) {
 101     DSGraph::ScalarMapTy::iterator I = ValMap.find(AI);
 102     if (I != ValMap.end())    // If its a pointer argument...
 103       I->second.mergeWith(Call.getPtrArg(PtrArgIdx++));
 104   }
 105 }
 106
 107
 108 /// run - Build up the result graph, representing the pointer graph for the
 109 /// program.
 110 ///
 111 bool Steens::runOnModule(Module &M) {
 112   InitializeAliasAnalysis(this);
 113   assert(ResultGraph == 0 && "Result graph already allocated!");
 114   LocalDataStructures &LDS = getAnalysis<LocalDataStructures>();
 115
 116   // Create a new, empty, graph...
 117   ResultGraph = new DSGraph(GlobalECs, getTargetData());
 118   ResultGraph->spliceFrom(LDS.getGlobalsGraph());
 119
 120   // Loop over the rest of the module, merging graphs for non-external functions
 121   // into this graph.
 122   //
 123   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
 124     if (!I->isExternal())
 125       ResultGraph->spliceFrom(LDS.getDSGraph(*I));
 126
 127   ResultGraph->removeTriviallyDeadNodes();
 128
 129   // FIXME: Must recalculate and use the Incomplete markers!!
 130
 131   // Now that we have all of the graphs inlined, we can go about eliminating
 132   // call nodes...
 133   //
 134   std::list<DSCallSite> &Calls = ResultGraph->getAuxFunctionCalls();
 135   assert(Calls.empty() && "Aux call list is already in use??");
 136
 137   // Start with a copy of the original call sites.
 138   Calls = ResultGraph->getFunctionCalls();
 139
 140   for (std::list<DSCallSite>::iterator CI = Calls.begin(), E = Calls.end();
 141        CI != E;) {
 142     DSCallSite &CurCall = *CI++;
 143
 144     // Loop over the called functions, eliminating as many as possible...
 145     std::vector<Function*> CallTargets;
 146     if (CurCall.isDirectCall())
 147       CallTargets.push_back(CurCall.getCalleeFunc());
 148     else
 149       CurCall.getCalleeNode()->addFullFunctionList(CallTargets);
 150
 151     for (unsigned c = 0; c != CallTargets.size(); ) {
 152       // If we can eliminate this function call, do so!
 153       Function *F = CallTargets[c];
 154       if (!F->isExternal()) {
 155         ResolveFunctionCall(F, CurCall, ResultGraph->getReturnNodes()[F]);
 156         CallTargets[c] = CallTargets.back();
 157         CallTargets.pop_back();
 158       } else
 159         ++c;  // Cannot eliminate this call, skip over it...
 160     }
 161
 162     if (CallTargets.empty()) {        // Eliminated all calls?
 163       std::list<DSCallSite>::iterator I = CI;
 164       Calls.erase(--I);               // Remove entry
 165     }
 166   }
 167
 168   // Remove our knowledge of what the return values of the functions are, except
 169   // for functions that are externally visible from this module (e.g. main).  We
 170   // keep these functions so that their arguments are marked incomplete.
 171   for (DSGraph::ReturnNodesTy::iterator I =
 172          ResultGraph->getReturnNodes().begin(),
 173          E = ResultGraph->getReturnNodes().end(); I != E; )
 174     if (I->first->hasInternalLinkage())
 175       ResultGraph->getReturnNodes().erase(I++);
 176     else
 177       ++I;
 178
 179   // Update the "incomplete" markers on the nodes, ignoring unknownness due to
 180   // incoming arguments...
 181   ResultGraph->maskIncompleteMarkers();
 182   ResultGraph->markIncompleteNodes(DSGraph::IgnoreGlobals |
 183                                    DSGraph::MarkFormalArgs);
 184
 185   // Remove any nodes that are dead after all of the merging we have done...
 186   // FIXME: We should be able to disable the globals graph for steens!
 187   //ResultGraph->removeDeadNodes(DSGraph::KeepUnreachableGlobals);
 188
 189   DEBUG(print(std::cerr, &M));
 190   return false;
 191 }
 192
 193 AliasAnalysis::AliasResult Steens::alias(const Value *V1, unsigned V1Size,
 194                                          const Value *V2, unsigned V2Size) {
 195   assert(ResultGraph && "Result graph has not been computed yet!");
 196
 197   DSGraph::ScalarMapTy &GSM = ResultGraph->getScalarMap();
 198
 199   DSGraph::ScalarMapTy::iterator I = GSM.find(const_cast<Value*>(V1));
 200   DSGraph::ScalarMapTy::iterator J = GSM.find(const_cast<Value*>(V2));
 201   if (I != GSM.end() && !I->second.isNull() &&
 202       J != GSM.end() && !J->second.isNull()) {
 203     DSNodeHandle &V1H = I->second;
 204     DSNodeHandle &V2H = J->second;
 205
 206     // If at least one of the nodes is complete, we can say something about
 207     // this.  If one is complete and the other isn't, then they are obviously
 208     // different nodes.  If they are both complete, we can't say anything
 209     // useful.
 210     if (I->second.getNode()->isComplete() ||
 211         J->second.getNode()->isComplete()) {
 212       // If the two pointers point to different data structure graph nodes, they
 213       // cannot alias!
 214       if (V1H.getNode() != V2H.getNode())
 215         return NoAlias;
 216
 217       // See if they point to different offsets...  if so, we may be able to
 218       // determine that they do not alias...
 219       unsigned O1 = I->second.getOffset(), O2 = J->second.getOffset();
 220       if (O1 != O2) {
 221         if (O2 < O1) {    // Ensure that O1 <= O2
 222           std::swap(V1, V2);
 223           std::swap(O1, O2);
 224           std::swap(V1Size, V2Size);
 225         }
 226
 227         if (O1+V1Size <= O2)
 228           return NoAlias;
 229       }
 230     }
 231   }
 232
 233   // If we cannot determine alias properties based on our graph, fall back on
 234   // some other AA implementation.
 235   //
 236   return AliasAnalysis::alias(V1, V1Size, V2, V2Size);
 237 }
 238
 239 AliasAnalysis::ModRefResult
 240 Steens::getModRefInfo(CallSite CS, Value *P, unsigned Size) {
 241   AliasAnalysis::ModRefResult Result = ModRef;
 242
 243   // Find the node in question.
 244   DSGraph::ScalarMapTy &GSM = ResultGraph->getScalarMap();
 245   DSGraph::ScalarMapTy::iterator I = GSM.find(P);
 246
 247   if (I != GSM.end() && !I->second.isNull()) {
 248     DSNode *N = I->second.getNode();
 249     if (N->isComplete()) {
 250       // If this is a direct call to an external function, and if the pointer
 251       // points to a complete node, the external function cannot modify or read
 252       // the value (we know it's not passed out of the program!).
 253       if (Function *F = CS.getCalledFunction())
 254         if (F->isExternal())
 255           return NoModRef;
 256
 257       // Otherwise, if the node is complete, but it is only M or R, return this.
 258       // This can be useful for globals that should be marked const but are not.
 259       if (!N->isModified())
 260         Result = (ModRefResult)(Result & ~Mod);
 261       if (!N->isRead())
 262         Result = (ModRefResult)(Result & ~Ref);
 263     }
 264   }
 265
 266   return (ModRefResult)(Result & AliasAnalysis::getModRefInfo(CS, P, Size));
 267 }