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) const;
  52
  53     /// canCallModify - We are not interprocedural, so we do nothing exciting.
  54     ///
  55     Result canCallModify(const CallInst &CI, const Value *Ptr) const {
  56       return MayAlias;
  57     }
  58
  59     /// canInvokeModify - We are not interprocedural, so we do nothing exciting.
  60     ///
  61     Result canInvokeModify(const InvokeInst &I, const Value *Ptr) const {
  62       return MayAlias;  // We are not interprocedural
  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->getValueMap();
  88
  89   // Handle the return value of the function...
  90   if (Call.getReturnValueNode().getNode() && RetVal.getNode())
  91     RetVal.mergeWith(Call.getReturnValueNode());
  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.getPtrArgNode(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*, DSNode*> 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 ValueMap into the global ValueMap...
 139       std::map<Value*, DSNodeHandle> &GVM = ResultGraph->getValueMap();
 140
 141       while (!ValMap.empty()) { // Loop over value map, moving entries over...
 142         const std::pair<Value*, DSNodeHandle> &DSN = *ValMap.begin();
 143         std::map<Value*, DSNodeHandle>::iterator I = GVM.find(DSN.first);
 144         if (I == GVM.end())
 145           GVM[DSN.first] = DSN.second;
 146         else
 147           I->second.mergeWith(DSN.second);
 148         ValMap.erase(ValMap.begin());
 149       }
 150     }
 151
 152   // FIXME: Must recalculate and use the Incomplete markers!!
 153
 154   // Now that we have all of the graphs inlined, we can go about eliminating
 155   // call nodes...
 156   //
 157   std::vector<DSCallSite> &Calls =
 158     ResultGraph->getFunctionCalls();
 159   for (unsigned i = 0; i != Calls.size(); ) {
 160     DSCallSite &CurCall = Calls[i];
 161
 162     // Loop over the called functions, eliminating as many as possible...
 163     std::vector<GlobalValue*> CallTargets = CurCall.getCalleeNode().getNode()->getGlobals();
 164     for (unsigned c = 0; c != CallTargets.size(); ) {
 165       // If we can eliminate this function call, do so!
 166       bool Eliminated = false;
 167       if (Function *F = dyn_cast<Function>(CallTargets[c]))
 168         if (!F->isExternal()) {
 169           ResolveFunctionCall(F, CurCall, RetValMap[F]);
 170           Eliminated = true;
 171         }
 172       if (Eliminated)
 173         CallTargets.erase(CallTargets.begin()+c);
 174       else
 175         ++c;  // Cannot eliminate this call, skip over it...
 176     }
 177
 178     if (CallTargets.empty())          // Eliminated all calls?
 179       Calls.erase(Calls.begin()+i);   // Remove from call list...
 180     else
 181       ++i;                            // Skip this call site...
 182   }
 183
 184   // Update the "incomplete" markers on the nodes, ignoring unknownness due to
 185   // incoming arguments...
 186   ResultGraph->maskIncompleteMarkers();
 187   ResultGraph->markIncompleteNodes(false);
 188
 189   // Remove any nodes that are dead after all of the merging we have done...
 190   ResultGraph->removeTriviallyDeadNodes();
 191
 192   DEBUG(print(std::cerr, &M));
 193   return false;
 194 }
 195
 196 // alias - This is the only method here that does anything interesting...
 197 AliasAnalysis::Result Steens::alias(const Value *V1, const Value *V2) const {
 198   assert(ResultGraph && "Result grcaph has not yet been computed!");
 199
 200   std::map<Value*, DSNodeHandle> &GVM = ResultGraph->getValueMap();
 201
 202   std::map<Value*, DSNodeHandle>::iterator I = GVM.find(const_cast<Value*>(V1));
 203   if (I != GVM.end() && I->second.getNode()) {
 204     DSNodeHandle &V1H = I->second;
 205     std::map<Value*, DSNodeHandle>::iterator J=GVM.find(const_cast<Value*>(V2));
 206     if (J != GVM.end() && J->second.getNode()) {
 207       DSNodeHandle &V2H = J->second;
 208       // If the two pointers point to different data structure graph nodes, they
 209       // cannot alias!
 210       if (V1H.getNode() != V2H.getNode())
 211         return NoAlias;
 212
 213       // FIXME: If the two pointers point to the same node, and the offsets are
 214       // different, and the LinkIndex vector doesn't alias the section, then the
 215       // two pointers do not alias.  We need access size information for the two
 216       // accesses though!
 217       //
 218     }
 219   }
 220
 221   // If we cannot determine alias properties based on our graph, fall back on
 222   // some other AA implementation.
 223   //
 224   return getAnalysis<AliasAnalysis>().alias(V1, V2);
 225 }