lib/Analysis/DataStructure/Steensgaard.cpp

   1 //===- Steensgaard.cpp - Context Insensitive Alias Analysis ---------------===//
   2 //
   3 // This pass uses the data structure graphs to implement a simple context
   4 // insensitive alias analysis.  It does this by computing the local analysis
   5 // graphs for all of the functions, then merging them together into a single big
   6 // graph without cloning.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "llvm/Analysis/DataStructure.h"
  11 #include "llvm/Analysis/DSGraph.h"
  12 #include "llvm/Analysis/AliasAnalysis.h"
  13 #include "llvm/Module.h"
  14 #include "Support/Statistic.h"
  15
  16 namespace {
  17   class Steens : public Pass, public AliasAnalysis {
  18     DSGraph *ResultGraph;
  19   public:
  20     Steens() : ResultGraph(0) {}
  21     ~Steens() { assert(ResultGraph == 0 && "releaseMemory not called?"); }
  22
  23     //------------------------------------------------
  24     // Implement the Pass API
  25     //
  26
  27     // run - Build up the result graph, representing the pointer graph for the
  28     // program.
  29     //
  30     bool run(Module &M);
  31
  32     virtual void releaseMemory() { delete ResultGraph; ResultGraph = 0; }
  33
  34     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  35       AU.setPreservesAll();                    // Does not transform code...
  36       AU.addRequired<LocalDataStructures>();   // Uses local dsgraph
  37       AU.addRequired<AliasAnalysis>();         // Chains to another AA impl...
  38     }
  39
  40     // print - Implement the Pass::print method...
  41     void print(std::ostream &O, const Module *M) const {
  42       assert(ResultGraph && "Result graph has not yet been computed!");
  43       ResultGraph->writeGraphToFile(O, "steensgaards");
  44     }
  45
  46     //------------------------------------------------
  47     // Implement the AliasAnalysis API
  48     //
  49
  50     // alias - This is the only method here that does anything interesting...
  51     Result alias(const Value *V1, const Value *V2);
  52
  53     /// canCallModify - Not implemented yet: FIXME
  54     ///
  55     Result canCallModify(const CallInst &CI, const Value *Ptr) {
  56       return MayAlias;
  57     }
  58
  59     /// canInvokeModify - Not implemented yet: FIXME
  60     ///
  61     Result canInvokeModify(const InvokeInst &I, const Value *Ptr) {
  62       return MayAlias;
  63     }
  64
  65   private:
  66     void ResolveFunctionCall(Function *F, const DSCallSite &Call,
  67                              DSNodeHandle &RetVal);
  68   };
  69
  70   // Register the pass...
  71   RegisterOpt<Steens> X("steens-aa",
  72                         "Steensgaard's FlowInsensitive/ConIns alias analysis");
  73
  74   // Register as an implementation of AliasAnalysis
  75   RegisterAnalysisGroup<AliasAnalysis, Steens> Y;
  76 }
  77
  78
  79 /// ResolveFunctionCall - Resolve the actual arguments of a call to function F
  80 /// with the specified call site descriptor.  This function links the arguments
  81 /// and the return value for the call site context-insensitively.
  82 ///
  83 void Steens::ResolveFunctionCall(Function *F,
  84                                  const DSCallSite &Call,
  85                                  DSNodeHandle &RetVal) {
  86   assert(ResultGraph != 0 && "Result graph not allocated!");
  87   std::map<Value*, DSNodeHandle> &ValMap = ResultGraph->getScalarMap();
  88
  89   // Handle the return value of the function...
  90   if (Call.getRetVal().getNode() && RetVal.getNode())
  91     RetVal.mergeWith(Call.getRetVal());
  92
  93   // Loop over all pointer arguments, resolving them to their provided pointers
  94   unsigned PtrArgIdx = 0;
  95   for (Function::aiterator AI = F->abegin(), AE = F->aend(); AI != AE; ++AI) {
  96     std::map<Value*, DSNodeHandle>::iterator I = ValMap.find(AI);
  97     if (I != ValMap.end())    // If its a pointer argument...
  98       I->second.addEdgeTo(Call.getPtrArg(PtrArgIdx++));
  99   }
 100
 101   assert(PtrArgIdx == Call.getNumPtrArgs() && "Argument resolution mismatch!");
 102 }
 103
 104
 105 /// run - Build up the result graph, representing the pointer graph for the
 106 /// program.
 107 ///
 108 bool Steens::run(Module &M) {
 109   assert(ResultGraph == 0 && "Result graph already allocated!");
 110   LocalDataStructures &LDS = getAnalysis<LocalDataStructures>();
 111
 112   // Create a new, empty, graph...
 113   ResultGraph = new DSGraph();
 114
 115   // RetValMap - Keep track of the return values for all functions that return
 116   // valid pointers.
 117   //
 118   std::map<Function*, DSNodeHandle> RetValMap;
 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       std::map<Value*, DSNodeHandle> ValMap;
 126       {  // Scope to free NodeMap memory ASAP
 127         std::map<const DSNode*, DSNodeHandle> NodeMap;
 128         const DSGraph &FDSG = LDS.getDSGraph(*I);
 129         DSNodeHandle RetNode = ResultGraph->cloneInto(FDSG, ValMap, NodeMap);
 130
 131         // Keep track of the return node of the function's graph if it returns a
 132         // value...
 133         //
 134         if (RetNode.getNode())
 135           RetValMap[I] = RetNode;
 136       }
 137
 138       // Incorporate the inlined Function's ScalarMap into the global
 139       // ScalarMap...
 140       std::map<Value*, DSNodeHandle> &GVM = ResultGraph->getScalarMap();
 141
 142       while (!ValMap.empty()) { // Loop over value map, moving entries over...
 143         const std::pair<Value*, DSNodeHandle> &DSN = *ValMap.begin();
 144         std::map<Value*, DSNodeHandle>::iterator I = GVM.find(DSN.first);
 145         if (I == GVM.end())
 146           GVM[DSN.first] = DSN.second;
 147         else
 148           I->second.mergeWith(DSN.second);
 149         ValMap.erase(ValMap.begin());
 150       }
 151     }
 152
 153   // FIXME: Must recalculate and use the Incomplete markers!!
 154
 155   // Now that we have all of the graphs inlined, we can go about eliminating
 156   // call nodes...
 157   //
 158   std::vector<DSCallSite> &Calls =
 159     ResultGraph->getAuxFunctionCalls();
 160   assert(Calls.empty() && "Aux call list is already in use??");
 161
 162   // Start with a copy of the original call sites...
 163   Calls = ResultGraph->getFunctionCalls();
 164
 165   for (unsigned i = 0; i != Calls.size(); ) {
 166     DSCallSite &CurCall = Calls[i];
 167
 168     // Loop over the called functions, eliminating as many as possible...
 169     std::vector<GlobalValue*> CallTargets =
 170       CurCall.getCallee().getNode()->getGlobals();
 171     for (unsigned c = 0; c != CallTargets.size(); ) {
 172       // If we can eliminate this function call, do so!
 173       bool Eliminated = false;
 174       if (Function *F = dyn_cast<Function>(CallTargets[c]))
 175         if (!F->isExternal()) {
 176           ResolveFunctionCall(F, CurCall, RetValMap[F]);
 177           Eliminated = true;
 178         }
 179       if (Eliminated)
 180         CallTargets.erase(CallTargets.begin()+c);
 181       else
 182         ++c;  // Cannot eliminate this call, skip over it...
 183     }
 184
 185     if (CallTargets.empty())          // Eliminated all calls?
 186       Calls.erase(Calls.begin()+i);   // Remove from call list...
 187     else
 188       ++i;                            // Skip this call site...
 189   }
 190
 191   // Update the "incomplete" markers on the nodes, ignoring unknownness due to
 192   // incoming arguments...
 193   ResultGraph->maskIncompleteMarkers();
 194   ResultGraph->markIncompleteNodes(false);
 195
 196   // Remove any nodes that are dead after all of the merging we have done...
 197   ResultGraph->removeTriviallyDeadNodes();
 198
 199   DEBUG(print(std::cerr, &M));
 200   return false;
 201 }
 202
 203 // alias - This is the only method here that does anything interesting...
 204 AliasAnalysis::Result Steens::alias(const Value *V1, const Value *V2) {
 205   assert(ResultGraph && "Result grcaph has not yet been computed!");
 206
 207   std::map<Value*, DSNodeHandle> &GVM = ResultGraph->getScalarMap();
 208
 209   std::map<Value*, DSNodeHandle>::iterator I = GVM.find(const_cast<Value*>(V1));
 210   if (I != GVM.end() && I->second.getNode()) {
 211     DSNodeHandle &V1H = I->second;
 212     std::map<Value*, DSNodeHandle>::iterator J=GVM.find(const_cast<Value*>(V2));
 213     if (J != GVM.end() && J->second.getNode()) {
 214       DSNodeHandle &V2H = J->second;
 215       // If the two pointers point to different data structure graph nodes, they
 216       // cannot alias!
 217       if (V1H.getNode() != V2H.getNode())
 218         return NoAlias;
 219
 220       // FIXME: If the two pointers point to the same node, and the offsets are
 221       // different, and the LinkIndex vector doesn't alias the section, then the
 222       // two pointers do not alias.  We need access size information for the two
 223       // accesses though!
 224       //
 225     }
 226   }
 227
 228   // If we cannot determine alias properties based on our graph, fall back on
 229   // some other AA implementation.
 230   //
 231   return getAnalysis<AliasAnalysis>().alias(V1, V2);
 232 }