lib/Analysis/IPA/GlobalsModRef.cpp

   1 //===- GlobalsModRef.cpp - Simple Mod/Ref Analysis for Globals ------------===//
   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 simple pass provides alias and mod/ref information for global values
  11 // that do not have their address taken.  For this simple (but very common)
  12 // case, we can provide pretty accurate and useful information.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #define DEBUG_TYPE "globalsmodref"
  17 #include "llvm/Analysis/Passes.h"
  18 #include "llvm/Module.h"
  19 #include "llvm/Pass.h"
  20 #include "llvm/Instructions.h"
  21 #include "llvm/Constants.h"
  22 #include "llvm/Analysis/AliasAnalysis.h"
  23 #include "llvm/Analysis/CallGraph.h"
  24 #include "Support/Debug.h"
  25 #include "Support/Statistic.h"
  26 #include "Support/SCCIterator.h"
  27 #include <set>
  28 using namespace llvm;
  29
  30 namespace {
  31   Statistic<>
  32   NumNonAddrTakenGlobalVars("globalsmodref-aa",
  33                             "Number of global vars without address taken");
  34   Statistic<>
  35   NumNonAddrTakenFunctions("globalsmodref-aa",
  36                            "Number of functions without address taken");
  37
  38   class GlobalsModRef : public Pass, public AliasAnalysis {
  39     /// ModRefFns - One instance of this record is kept for each global without
  40     /// its address taken.
  41     struct ModRefFns {
  42       /// RefFns/ModFns - Sets of functions that and write globals.
  43       std::set<Function*> RefFns, ModFns;
  44     };
  45
  46     /// NonAddressTakenGlobals - A map of globals that do not have their
  47     /// addresses taken to their record.
  48     std::map<GlobalValue*, ModRefFns> NonAddressTakenGlobals;
  49
  50     /// FunctionInfo - For each function, keep track of what globals are
  51     /// modified or read.
  52     std::map<std::pair<Function*, GlobalValue*>, unsigned> FunctionInfo;
  53
  54   public:
  55     bool run(Module &M) {
  56       InitializeAliasAnalysis(this);                 // set up super class
  57       AnalyzeGlobals(M);                          // find non-addr taken globals
  58       AnalyzeCallGraph(getAnalysis<CallGraph>(), M); // Propagate on CG
  59       return false;
  60     }
  61
  62     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  63       AliasAnalysis::getAnalysisUsage(AU);
  64       AU.addRequired<CallGraph>();
  65       AU.setPreservesAll();                         // Does not transform code
  66     }
  67
  68     //------------------------------------------------
  69     // Implement the AliasAnalysis API
  70     //
  71     AliasResult alias(const Value *V1, unsigned V1Size,
  72                       const Value *V2, unsigned V2Size);
  73     ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size);
  74     bool hasNoModRefInfoForCalls() const { return false; }
  75
  76     virtual void deleteValue(Value *V);
  77     virtual void copyValue(Value *From, Value *To);
  78
  79   private:
  80     void AnalyzeGlobals(Module &M);
  81     void AnalyzeCallGraph(CallGraph &CG, Module &M);
  82     bool AnalyzeUsesOfGlobal(Value *V, std::vector<Function*> &Readers,
  83                              std::vector<Function*> &Writers);
  84   };
  85
  86   RegisterOpt<GlobalsModRef> X("globalsmodref-aa",
  87                                "Simple mod/ref analysis for globals");
  88   RegisterAnalysisGroup<AliasAnalysis, GlobalsModRef> Y;
  89 }
  90
  91 Pass *llvm::createGlobalsModRefPass() { return new GlobalsModRef(); }
  92
  93
  94 /// AnalyzeGlobalUses - Scan through the users of all of the internal
  95 /// GlobalValue's in the program.  If none of them have their "Address taken"
  96 /// (really, their address passed to something nontrivial), record this fact,
  97 /// and record the functions that they are used directly in.
  98 void GlobalsModRef::AnalyzeGlobals(Module &M) {
  99   std::vector<Function*> Readers, Writers;
 100   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
 101     if (I->hasInternalLinkage()) {
 102       if (!AnalyzeUsesOfGlobal(I, Readers, Writers)) {
 103         // Remember that we are tracking this global, and the mod/ref fns
 104         ModRefFns &E = NonAddressTakenGlobals[I];
 105         E.RefFns.insert(Readers.begin(), Readers.end());
 106         E.ModFns.insert(Writers.begin(), Writers.end());
 107         ++NumNonAddrTakenFunctions;
 108       }
 109       Readers.clear(); Writers.clear();
 110     }
 111
 112   for (Module::giterator I = M.gbegin(), E = M.gend(); I != E; ++I)
 113     // FIXME: it is kinda dumb to track aliasing properties for constant
 114     // globals, it will never be particularly useful anyways, 'cause they can
 115     // never be modified (and the optimizer knows this already)!
 116     if (I->hasInternalLinkage()) {
 117       if (!AnalyzeUsesOfGlobal(I, Readers, Writers)) {
 118         // Remember that we are tracking this global, and the mod/ref fns
 119         ModRefFns &E = NonAddressTakenGlobals[I];
 120         E.RefFns.insert(Readers.begin(), Readers.end());
 121         E.ModFns.insert(Writers.begin(), Writers.end());
 122         ++NumNonAddrTakenGlobalVars;
 123       }
 124       Readers.clear(); Writers.clear();
 125     }
 126 }
 127
 128 /// AnalyzeUsesOfGlobal - Look at all of the users of the specified global value
 129 /// derived pointer.  If this is used by anything complex (i.e., the address
 130 /// escapes), return true.  Also, while we are at it, keep track of those
 131 /// functions that read and write to the value.
 132 bool GlobalsModRef::AnalyzeUsesOfGlobal(Value *V,
 133                                         std::vector<Function*> &Readers,
 134                                         std::vector<Function*> &Writers) {
 135   //if (!isa<PointerType>(V->getType())) return true;
 136
 137   for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI)
 138     if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) {
 139       Readers.push_back(LI->getParent()->getParent());
 140     } else if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) {
 141       if (V == SI->getOperand(0)) return true;  // Storing the pointer
 142       Writers.push_back(SI->getParent()->getParent());
 143     } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(*UI)) {
 144       if (AnalyzeUsesOfGlobal(GEP, Readers, Writers)) return true;
 145     } else if (CallInst *CI = dyn_cast<CallInst>(*UI)) {
 146       // Make sure that this is just the function being called, not that it is
 147       // passing into the function.
 148       for (unsigned i = 1, e = CI->getNumOperands(); i != e; ++i)
 149         if (CI->getOperand(i) == V) return true;
 150     } else if (CallInst *CI = dyn_cast<CallInst>(*UI)) {
 151       // Make sure that this is just the function being called, not that it is
 152       // passing into the function.
 153       for (unsigned i = 1, e = CI->getNumOperands(); i != e; ++i)
 154         if (CI->getOperand(i) == V) return true;
 155     } else if (InvokeInst *II = dyn_cast<InvokeInst>(*UI)) {
 156       // Make sure that this is just the function being called, not that it is
 157       // passing into the function.
 158       for (unsigned i = 3, e = II->getNumOperands(); i != e; ++i)
 159         if (II->getOperand(i) == V) return true;
 160     } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(*UI)) {
 161       if (CE->getOpcode() == Instruction::GetElementPtr ||
 162           CE->getOpcode() == Instruction::Cast) {
 163         if (AnalyzeUsesOfGlobal(CE, Readers, Writers))
 164           return true;
 165       } else {
 166         return true;
 167       }
 168     } else if (GlobalValue *GV = dyn_cast<GlobalValue>(*UI)) {
 169       if (AnalyzeUsesOfGlobal(GV, Readers, Writers)) return true;
 170     } else {
 171       return true;
 172     }
 173   return false;
 174 }
 175
 176 /// AnalyzeCallGraph - At this point, we know the functions where globals are
 177 /// immediately stored to and read from.  Propagate this information up the call
 178 /// graph to all callers.
 179 void GlobalsModRef::AnalyzeCallGraph(CallGraph &CG, Module &M) {
 180   if (NonAddressTakenGlobals.empty()) return;  // Don't bother, nothing to do.
 181
 182   // Invert the NonAddressTakenGlobals map into the FunctionInfo map.
 183   for (std::map<GlobalValue*, ModRefFns>::iterator I =
 184          NonAddressTakenGlobals.begin(), E = NonAddressTakenGlobals.end();
 185        I != E; ++I) {
 186     GlobalValue *GV = I->first;
 187     ModRefFns &MRInfo = I->second;
 188     for (std::set<Function*>::iterator I = MRInfo.RefFns.begin(),
 189            E = MRInfo.RefFns.begin(); I != E; ++I)
 190       FunctionInfo[std::make_pair(*I, GV)] |= Ref;
 191     MRInfo.RefFns.clear();
 192     for (std::set<Function*>::iterator I = MRInfo.ModFns.begin(),
 193            E = MRInfo.ModFns.begin(); I != E; ++I)
 194       FunctionInfo[std::make_pair(*I, GV)] |= Mod;
 195     MRInfo.ModFns.clear();
 196   }
 197
 198   // We do a bottom-up SCC traversal of the call graph.  In other words, we
 199   // visit all callees before callers (leaf-first).
 200   for (scc_iterator<CallGraph*> I = scc_begin(&CG), E = scc_end(&CG);
 201        I != E; ++I) {
 202     std::map<GlobalValue*, unsigned> ModRefProperties;
 203     const std::vector<CallGraphNode *> &SCC = *I;
 204
 205     // Collect the mod/ref properties due to called functions.
 206     for (unsigned i = 0, e = SCC.size(); i != e; ++i)
 207       for (CallGraphNode::iterator CI = SCC[i]->begin(), E = SCC[i]->end();
 208            CI != E; ++CI) {
 209         if (Function *Callee = (*CI)->getFunction()) {
 210           // Otherwise, combine the callee properties into our accumulated set.
 211           std::map<std::pair<Function*, GlobalValue*>, unsigned>::iterator
 212             CI = FunctionInfo.lower_bound(std::make_pair(Callee,
 213                                                          (GlobalValue*)0));
 214           for (;CI != FunctionInfo.end() && CI->first.first == Callee; ++CI)
 215             ModRefProperties[CI->first.second] |= CI->second;
 216         } else {
 217           // For now assume that external functions could mod/ref anything,
 218           // since they could call into an escaping function that mod/refs an
 219           // internal.  FIXME: We need better tracking!
 220           for (std::map<GlobalValue*, ModRefFns>::iterator GI =
 221                  NonAddressTakenGlobals.begin(),
 222                  E = NonAddressTakenGlobals.end(); GI != E; ++GI)
 223             ModRefProperties[GI->first] = ModRef;
 224           goto Out;
 225         }
 226       }
 227   Out:
 228     // Set all functions in the CFG to have these properties.  FIXME: it would
 229     // be better to use union find to only store these properties once,
 230     // PARTICULARLY if it's the universal set.
 231     for (unsigned i = 0, e = SCC.size(); i != e; ++i)
 232       if (Function *F = SCC[i]->getFunction()) {
 233         for (std::map<GlobalValue*, unsigned>::iterator I =
 234                ModRefProperties.begin(), E = ModRefProperties.end();
 235              I != E; ++I)
 236           FunctionInfo[std::make_pair(F, I->first)] = I->second;
 237       }
 238   }
 239 }
 240
 241
 242
 243 /// getUnderlyingObject - This traverses the use chain to figure out what object
 244 /// the specified value points to.  If the value points to, or is derived from,
 245 /// a global object, return it.
 246 static const GlobalValue *getUnderlyingObject(const Value *V) {
 247   //if (!isa<PointerType>(V->getType())) return 0;
 248
 249   // If we are at some type of object... return it.
 250   if (const GlobalValue *GV = dyn_cast<GlobalValue>(V)) return GV;
 251
 252   // Traverse through different addressing mechanisms...
 253   if (const Instruction *I = dyn_cast<Instruction>(V)) {
 254     if (isa<CastInst>(I) || isa<GetElementPtrInst>(I))
 255       return getUnderlyingObject(I->getOperand(0));
 256   } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
 257     if (CE->getOpcode() == Instruction::Cast ||
 258         CE->getOpcode() == Instruction::GetElementPtr)
 259       return getUnderlyingObject(CE->getOperand(0));
 260   }
 261   return 0;
 262 }
 263
 264 /// alias - If one of the pointers is to a global that we are tracking, and the
 265 /// other is some random pointer, we know there cannot be an alias, because the
 266 /// address of the global isn't taken.
 267 AliasAnalysis::AliasResult
 268 GlobalsModRef::alias(const Value *V1, unsigned V1Size,
 269                      const Value *V2, unsigned V2Size) {
 270   GlobalValue *GV1 = const_cast<GlobalValue*>(getUnderlyingObject(V1));
 271   GlobalValue *GV2 = const_cast<GlobalValue*>(getUnderlyingObject(V2));
 272
 273   // If the global's address is taken, pretend we don't know it's a pointer to
 274   // the global.
 275   if (GV1 && !NonAddressTakenGlobals.count(GV1)) GV1 = 0;
 276   if (GV2 && !NonAddressTakenGlobals.count(GV2)) GV2 = 0;
 277
 278   if ((GV1 || GV2) && GV1 != GV2)
 279     return NoAlias;
 280
 281   return AliasAnalysis::alias(V1, V1Size, V2, V2Size);
 282 }
 283
 284 AliasAnalysis::ModRefResult
 285 GlobalsModRef::getModRefInfo(CallSite CS, Value *P, unsigned Size) {
 286   unsigned Known = ModRef;
 287
 288   // If we are asking for mod/ref info of a direct call with a pointer to a
 289   // global, return information if we have it.
 290   if (GlobalValue *GV = const_cast<GlobalValue*>(getUnderlyingObject(P)))
 291     if (GV->hasInternalLinkage())
 292       if (Function *F = CS.getCalledFunction()) {
 293         std::map<std::pair<Function*, GlobalValue*>, unsigned>::iterator
 294           it = FunctionInfo.find(std::make_pair(F, GV));
 295         if (it != FunctionInfo.end())
 296           Known = it->second;
 297       }
 298
 299   if (Known == NoModRef)
 300     return NoModRef; // No need to query other mod/ref analyses
 301   return ModRefResult(Known & AliasAnalysis::getModRefInfo(CS, P, Size));
 302 }
 303
 304
 305 //===----------------------------------------------------------------------===//
 306 // Methods to update the analysis as a result of the client transformation.
 307 //
 308 void GlobalsModRef::deleteValue(Value *V) {
 309   if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
 310     std::map<GlobalValue*, ModRefFns>::iterator I =
 311       NonAddressTakenGlobals.find(GV);
 312     if (I != NonAddressTakenGlobals.end())
 313       NonAddressTakenGlobals.erase(I);
 314   }
 315 }
 316
 317 void GlobalsModRef::copyValue(Value *From, Value *To) {
 318   if (GlobalValue *FromGV = dyn_cast<GlobalValue>(From))
 319     if (GlobalValue *ToGV = dyn_cast<GlobalValue>(To)) {
 320       std::map<GlobalValue*, ModRefFns>::iterator I =
 321         NonAddressTakenGlobals.find(FromGV);
 322       if (I != NonAddressTakenGlobals.end())
 323         NonAddressTakenGlobals[ToGV] = I->second;
 324     }
 325 }