LLVM  mainline
AliasAnalysisEvaluator.cpp
Go to the documentation of this file.
00001 //===- AliasAnalysisEvaluator.cpp - Alias Analysis Accuracy Evaluator -----===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements a simple N^2 alias analysis accuracy evaluator.
00011 // Basically, for each function in the program, it simply queries to see how the
00012 // alias analysis implementation answers alias queries between each pair of
00013 // pointers in the function.
00014 //
00015 // This is inspired and adapted from code by: Naveen Neelakantam, Francesco
00016 // Spadini, and Wojciech Stryjewski.
00017 //
00018 //===----------------------------------------------------------------------===//
00019 
00020 #include "llvm/Analysis/Passes.h"
00021 #include "llvm/ADT/SetVector.h"
00022 #include "llvm/Analysis/AliasAnalysis.h"
00023 #include "llvm/IR/Constants.h"
00024 #include "llvm/IR/DerivedTypes.h"
00025 #include "llvm/IR/Function.h"
00026 #include "llvm/IR/InstIterator.h"
00027 #include "llvm/IR/Instructions.h"
00028 #include "llvm/Pass.h"
00029 #include "llvm/Support/CommandLine.h"
00030 #include "llvm/Support/Debug.h"
00031 #include "llvm/Support/raw_ostream.h"
00032 using namespace llvm;
00033 
00034 static cl::opt<bool> PrintAll("print-all-alias-modref-info", cl::ReallyHidden);
00035 
00036 static cl::opt<bool> PrintNoAlias("print-no-aliases", cl::ReallyHidden);
00037 static cl::opt<bool> PrintMayAlias("print-may-aliases", cl::ReallyHidden);
00038 static cl::opt<bool> PrintPartialAlias("print-partial-aliases", cl::ReallyHidden);
00039 static cl::opt<bool> PrintMustAlias("print-must-aliases", cl::ReallyHidden);
00040 
00041 static cl::opt<bool> PrintNoModRef("print-no-modref", cl::ReallyHidden);
00042 static cl::opt<bool> PrintMod("print-mod", cl::ReallyHidden);
00043 static cl::opt<bool> PrintRef("print-ref", cl::ReallyHidden);
00044 static cl::opt<bool> PrintModRef("print-modref", cl::ReallyHidden);
00045 
00046 static cl::opt<bool> EvalAAMD("evaluate-aa-metadata", cl::ReallyHidden);
00047 
00048 namespace {
00049   class AAEval : public FunctionPass {
00050     unsigned NoAliasCount, MayAliasCount, PartialAliasCount, MustAliasCount;
00051     unsigned NoModRefCount, ModCount, RefCount, ModRefCount;
00052 
00053   public:
00054     static char ID; // Pass identification, replacement for typeid
00055     AAEval() : FunctionPass(ID) {
00056       initializeAAEvalPass(*PassRegistry::getPassRegistry());
00057     }
00058 
00059     void getAnalysisUsage(AnalysisUsage &AU) const override {
00060       AU.addRequired<AliasAnalysis>();
00061       AU.setPreservesAll();
00062     }
00063 
00064     bool doInitialization(Module &M) override {
00065       NoAliasCount = MayAliasCount = PartialAliasCount = MustAliasCount = 0;
00066       NoModRefCount = ModCount = RefCount = ModRefCount = 0;
00067 
00068       if (PrintAll) {
00069         PrintNoAlias = PrintMayAlias = true;
00070         PrintPartialAlias = PrintMustAlias = true;
00071         PrintNoModRef = PrintMod = PrintRef = PrintModRef = true;
00072       }
00073       return false;
00074     }
00075 
00076     bool runOnFunction(Function &F) override;
00077     bool doFinalization(Module &M) override;
00078   };
00079 }
00080 
00081 char AAEval::ID = 0;
00082 INITIALIZE_PASS_BEGIN(AAEval, "aa-eval",
00083                 "Exhaustive Alias Analysis Precision Evaluator", false, true)
00084 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
00085 INITIALIZE_PASS_END(AAEval, "aa-eval",
00086                 "Exhaustive Alias Analysis Precision Evaluator", false, true)
00087 
00088 FunctionPass *llvm::createAAEvalPass() { return new AAEval(); }
00089 
00090 static void PrintResults(const char *Msg, bool P, const Value *V1,
00091                          const Value *V2, const Module *M) {
00092   if (P) {
00093     std::string o1, o2;
00094     {
00095       raw_string_ostream os1(o1), os2(o2);
00096       V1->printAsOperand(os1, true, M);
00097       V2->printAsOperand(os2, true, M);
00098     }
00099     
00100     if (o2 < o1)
00101       std::swap(o1, o2);
00102     errs() << "  " << Msg << ":\t"
00103            << o1 << ", "
00104            << o2 << "\n";
00105   }
00106 }
00107 
00108 static inline void
00109 PrintModRefResults(const char *Msg, bool P, Instruction *I, Value *Ptr,
00110                    Module *M) {
00111   if (P) {
00112     errs() << "  " << Msg << ":  Ptr: ";
00113     Ptr->printAsOperand(errs(), true, M);
00114     errs() << "\t<->" << *I << '\n';
00115   }
00116 }
00117 
00118 static inline void
00119 PrintModRefResults(const char *Msg, bool P, CallSite CSA, CallSite CSB,
00120                    Module *M) {
00121   if (P) {
00122     errs() << "  " << Msg << ": " << *CSA.getInstruction()
00123            << " <-> " << *CSB.getInstruction() << '\n';
00124   }
00125 }
00126 
00127 static inline void
00128 PrintLoadStoreResults(const char *Msg, bool P, const Value *V1,
00129                       const Value *V2, const Module *M) {
00130   if (P) {
00131     errs() << "  " << Msg << ": " << *V1
00132            << " <-> " << *V2 << '\n';
00133   }
00134 }
00135 
00136 static inline bool isInterestingPointer(Value *V) {
00137   return V->getType()->isPointerTy()
00138       && !isa<ConstantPointerNull>(V);
00139 }
00140 
00141 bool AAEval::runOnFunction(Function &F) {
00142   AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
00143 
00144   SetVector<Value *> Pointers;
00145   SetVector<CallSite> CallSites;
00146   SetVector<Value *> Loads;
00147   SetVector<Value *> Stores;
00148 
00149   for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I)
00150     if (I->getType()->isPointerTy())    // Add all pointer arguments.
00151       Pointers.insert(I);
00152 
00153   for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
00154     if (I->getType()->isPointerTy()) // Add all pointer instructions.
00155       Pointers.insert(&*I);
00156     if (EvalAAMD && isa<LoadInst>(&*I))
00157       Loads.insert(&*I);
00158     if (EvalAAMD && isa<StoreInst>(&*I))
00159       Stores.insert(&*I);
00160     Instruction &Inst = *I;
00161     if (auto CS = CallSite(&Inst)) {
00162       Value *Callee = CS.getCalledValue();
00163       // Skip actual functions for direct function calls.
00164       if (!isa<Function>(Callee) && isInterestingPointer(Callee))
00165         Pointers.insert(Callee);
00166       // Consider formals.
00167       for (CallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end();
00168            AI != AE; ++AI)
00169         if (isInterestingPointer(*AI))
00170           Pointers.insert(*AI);
00171       CallSites.insert(CS);
00172     } else {
00173       // Consider all operands.
00174       for (Instruction::op_iterator OI = Inst.op_begin(), OE = Inst.op_end();
00175            OI != OE; ++OI)
00176         if (isInterestingPointer(*OI))
00177           Pointers.insert(*OI);
00178     }
00179   }
00180 
00181   if (PrintNoAlias || PrintMayAlias || PrintPartialAlias || PrintMustAlias ||
00182       PrintNoModRef || PrintMod || PrintRef || PrintModRef)
00183     errs() << "Function: " << F.getName() << ": " << Pointers.size()
00184            << " pointers, " << CallSites.size() << " call sites\n";
00185 
00186   // iterate over the worklist, and run the full (n^2)/2 disambiguations
00187   for (SetVector<Value *>::iterator I1 = Pointers.begin(), E = Pointers.end();
00188        I1 != E; ++I1) {
00189     uint64_t I1Size = MemoryLocation::UnknownSize;
00190     Type *I1ElTy = cast<PointerType>((*I1)->getType())->getElementType();
00191     if (I1ElTy->isSized()) I1Size = AA.getTypeStoreSize(I1ElTy);
00192 
00193     for (SetVector<Value *>::iterator I2 = Pointers.begin(); I2 != I1; ++I2) {
00194       uint64_t I2Size = MemoryLocation::UnknownSize;
00195       Type *I2ElTy =cast<PointerType>((*I2)->getType())->getElementType();
00196       if (I2ElTy->isSized()) I2Size = AA.getTypeStoreSize(I2ElTy);
00197 
00198       switch (AA.alias(*I1, I1Size, *I2, I2Size)) {
00199       case NoAlias:
00200         PrintResults("NoAlias", PrintNoAlias, *I1, *I2, F.getParent());
00201         ++NoAliasCount;
00202         break;
00203       case MayAlias:
00204         PrintResults("MayAlias", PrintMayAlias, *I1, *I2, F.getParent());
00205         ++MayAliasCount;
00206         break;
00207       case PartialAlias:
00208         PrintResults("PartialAlias", PrintPartialAlias, *I1, *I2,
00209                      F.getParent());
00210         ++PartialAliasCount;
00211         break;
00212       case MustAlias:
00213         PrintResults("MustAlias", PrintMustAlias, *I1, *I2, F.getParent());
00214         ++MustAliasCount;
00215         break;
00216       }
00217     }
00218   }
00219 
00220   if (EvalAAMD) {
00221     // iterate over all pairs of load, store
00222     for (SetVector<Value *>::iterator I1 = Loads.begin(), E = Loads.end();
00223          I1 != E; ++I1) {
00224       for (SetVector<Value *>::iterator I2 = Stores.begin(), E2 = Stores.end();
00225            I2 != E2; ++I2) {
00226         switch (AA.alias(MemoryLocation::get(cast<LoadInst>(*I1)),
00227                          MemoryLocation::get(cast<StoreInst>(*I2)))) {
00228         case NoAlias:
00229           PrintLoadStoreResults("NoAlias", PrintNoAlias, *I1, *I2,
00230                                 F.getParent());
00231           ++NoAliasCount;
00232           break;
00233         case MayAlias:
00234           PrintLoadStoreResults("MayAlias", PrintMayAlias, *I1, *I2,
00235                                 F.getParent());
00236           ++MayAliasCount;
00237           break;
00238         case PartialAlias:
00239           PrintLoadStoreResults("PartialAlias", PrintPartialAlias, *I1, *I2,
00240                                 F.getParent());
00241           ++PartialAliasCount;
00242           break;
00243         case MustAlias:
00244           PrintLoadStoreResults("MustAlias", PrintMustAlias, *I1, *I2,
00245                                 F.getParent());
00246           ++MustAliasCount;
00247           break;
00248         }
00249       }
00250     }
00251 
00252     // iterate over all pairs of store, store
00253     for (SetVector<Value *>::iterator I1 = Stores.begin(), E = Stores.end();
00254          I1 != E; ++I1) {
00255       for (SetVector<Value *>::iterator I2 = Stores.begin(); I2 != I1; ++I2) {
00256         switch (AA.alias(MemoryLocation::get(cast<StoreInst>(*I1)),
00257                          MemoryLocation::get(cast<StoreInst>(*I2)))) {
00258         case NoAlias:
00259           PrintLoadStoreResults("NoAlias", PrintNoAlias, *I1, *I2,
00260                                 F.getParent());
00261           ++NoAliasCount;
00262           break;
00263         case MayAlias:
00264           PrintLoadStoreResults("MayAlias", PrintMayAlias, *I1, *I2,
00265                                 F.getParent());
00266           ++MayAliasCount;
00267           break;
00268         case PartialAlias:
00269           PrintLoadStoreResults("PartialAlias", PrintPartialAlias, *I1, *I2,
00270                                 F.getParent());
00271           ++PartialAliasCount;
00272           break;
00273         case MustAlias:
00274           PrintLoadStoreResults("MustAlias", PrintMustAlias, *I1, *I2,
00275                                 F.getParent());
00276           ++MustAliasCount;
00277           break;
00278         }
00279       }
00280     }
00281   }
00282 
00283   // Mod/ref alias analysis: compare all pairs of calls and values
00284   for (SetVector<CallSite>::iterator C = CallSites.begin(),
00285          Ce = CallSites.end(); C != Ce; ++C) {
00286     Instruction *I = C->getInstruction();
00287 
00288     for (SetVector<Value *>::iterator V = Pointers.begin(), Ve = Pointers.end();
00289          V != Ve; ++V) {
00290       uint64_t Size = MemoryLocation::UnknownSize;
00291       Type *ElTy = cast<PointerType>((*V)->getType())->getElementType();
00292       if (ElTy->isSized()) Size = AA.getTypeStoreSize(ElTy);
00293 
00294       switch (AA.getModRefInfo(*C, *V, Size)) {
00295       case AliasAnalysis::NoModRef:
00296         PrintModRefResults("NoModRef", PrintNoModRef, I, *V, F.getParent());
00297         ++NoModRefCount;
00298         break;
00299       case AliasAnalysis::Mod:
00300         PrintModRefResults("Just Mod", PrintMod, I, *V, F.getParent());
00301         ++ModCount;
00302         break;
00303       case AliasAnalysis::Ref:
00304         PrintModRefResults("Just Ref", PrintRef, I, *V, F.getParent());
00305         ++RefCount;
00306         break;
00307       case AliasAnalysis::ModRef:
00308         PrintModRefResults("Both ModRef", PrintModRef, I, *V, F.getParent());
00309         ++ModRefCount;
00310         break;
00311       }
00312     }
00313   }
00314 
00315   // Mod/ref alias analysis: compare all pairs of calls
00316   for (SetVector<CallSite>::iterator C = CallSites.begin(),
00317          Ce = CallSites.end(); C != Ce; ++C) {
00318     for (SetVector<CallSite>::iterator D = CallSites.begin(); D != Ce; ++D) {
00319       if (D == C)
00320         continue;
00321       switch (AA.getModRefInfo(*C, *D)) {
00322       case AliasAnalysis::NoModRef:
00323         PrintModRefResults("NoModRef", PrintNoModRef, *C, *D, F.getParent());
00324         ++NoModRefCount;
00325         break;
00326       case AliasAnalysis::Mod:
00327         PrintModRefResults("Just Mod", PrintMod, *C, *D, F.getParent());
00328         ++ModCount;
00329         break;
00330       case AliasAnalysis::Ref:
00331         PrintModRefResults("Just Ref", PrintRef, *C, *D, F.getParent());
00332         ++RefCount;
00333         break;
00334       case AliasAnalysis::ModRef:
00335         PrintModRefResults("Both ModRef", PrintModRef, *C, *D, F.getParent());
00336         ++ModRefCount;
00337         break;
00338       }
00339     }
00340   }
00341 
00342   return false;
00343 }
00344 
00345 static void PrintPercent(unsigned Num, unsigned Sum) {
00346   errs() << "(" << Num*100ULL/Sum << "."
00347          << ((Num*1000ULL/Sum) % 10) << "%)\n";
00348 }
00349 
00350 bool AAEval::doFinalization(Module &M) {
00351   unsigned AliasSum =
00352       NoAliasCount + MayAliasCount + PartialAliasCount + MustAliasCount;
00353   errs() << "===== Alias Analysis Evaluator Report =====\n";
00354   if (AliasSum == 0) {
00355     errs() << "  Alias Analysis Evaluator Summary: No pointers!\n";
00356   } else {
00357     errs() << "  " << AliasSum << " Total Alias Queries Performed\n";
00358     errs() << "  " << NoAliasCount << " no alias responses ";
00359     PrintPercent(NoAliasCount, AliasSum);
00360     errs() << "  " << MayAliasCount << " may alias responses ";
00361     PrintPercent(MayAliasCount, AliasSum);
00362     errs() << "  " << PartialAliasCount << " partial alias responses ";
00363     PrintPercent(PartialAliasCount, AliasSum);
00364     errs() << "  " << MustAliasCount << " must alias responses ";
00365     PrintPercent(MustAliasCount, AliasSum);
00366     errs() << "  Alias Analysis Evaluator Pointer Alias Summary: "
00367            << NoAliasCount * 100 / AliasSum << "%/"
00368            << MayAliasCount * 100 / AliasSum << "%/"
00369            << PartialAliasCount * 100 / AliasSum << "%/"
00370            << MustAliasCount * 100 / AliasSum << "%\n";
00371   }
00372 
00373   // Display the summary for mod/ref analysis
00374   unsigned ModRefSum = NoModRefCount + ModCount + RefCount + ModRefCount;
00375   if (ModRefSum == 0) {
00376     errs() << "  Alias Analysis Mod/Ref Evaluator Summary: no "
00377               "mod/ref!\n";
00378   } else {
00379     errs() << "  " << ModRefSum << " Total ModRef Queries Performed\n";
00380     errs() << "  " << NoModRefCount << " no mod/ref responses ";
00381     PrintPercent(NoModRefCount, ModRefSum);
00382     errs() << "  " << ModCount << " mod responses ";
00383     PrintPercent(ModCount, ModRefSum);
00384     errs() << "  " << RefCount << " ref responses ";
00385     PrintPercent(RefCount, ModRefSum);
00386     errs() << "  " << ModRefCount << " mod & ref responses ";
00387     PrintPercent(ModRefCount, ModRefSum);
00388     errs() << "  Alias Analysis Evaluator Mod/Ref Summary: "
00389            << NoModRefCount * 100 / ModRefSum << "%/"
00390            << ModCount * 100 / ModRefSum << "%/" << RefCount * 100 / ModRefSum
00391            << "%/" << ModRefCount * 100 / ModRefSum << "%\n";
00392   }
00393 
00394   return false;
00395 }