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/DataLayout.h"
00025 #include "llvm/IR/DerivedTypes.h"
00026 #include "llvm/IR/Function.h"
00027 #include "llvm/IR/Module.h"
00028 #include "llvm/IR/InstIterator.h"
00029 #include "llvm/IR/Instructions.h"
00030 #include "llvm/Pass.h"
00031 #include "llvm/Support/CommandLine.h"
00032 #include "llvm/Support/Debug.h"
00033 #include "llvm/Support/raw_ostream.h"
00034 using namespace llvm;
00035 
00036 static cl::opt<bool> PrintAll("print-all-alias-modref-info", cl::ReallyHidden);
00037 
00038 static cl::opt<bool> PrintNoAlias("print-no-aliases", cl::ReallyHidden);
00039 static cl::opt<bool> PrintMayAlias("print-may-aliases", cl::ReallyHidden);
00040 static cl::opt<bool> PrintPartialAlias("print-partial-aliases", cl::ReallyHidden);
00041 static cl::opt<bool> PrintMustAlias("print-must-aliases", cl::ReallyHidden);
00042 
00043 static cl::opt<bool> PrintNoModRef("print-no-modref", cl::ReallyHidden);
00044 static cl::opt<bool> PrintMod("print-mod", cl::ReallyHidden);
00045 static cl::opt<bool> PrintRef("print-ref", cl::ReallyHidden);
00046 static cl::opt<bool> PrintModRef("print-modref", cl::ReallyHidden);
00047 
00048 static cl::opt<bool> EvalAAMD("evaluate-aa-metadata", cl::ReallyHidden);
00049 
00050 namespace {
00051   class AAEval : public FunctionPass {
00052     unsigned NoAliasCount, MayAliasCount, PartialAliasCount, MustAliasCount;
00053     unsigned NoModRefCount, ModCount, RefCount, ModRefCount;
00054 
00055   public:
00056     static char ID; // Pass identification, replacement for typeid
00057     AAEval() : FunctionPass(ID) {
00058       initializeAAEvalPass(*PassRegistry::getPassRegistry());
00059     }
00060 
00061     void getAnalysisUsage(AnalysisUsage &AU) const override {
00062       AU.addRequired<AAResultsWrapperPass>();
00063       AU.setPreservesAll();
00064     }
00065 
00066     bool doInitialization(Module &M) override {
00067       NoAliasCount = MayAliasCount = PartialAliasCount = MustAliasCount = 0;
00068       NoModRefCount = ModCount = RefCount = ModRefCount = 0;
00069 
00070       if (PrintAll) {
00071         PrintNoAlias = PrintMayAlias = true;
00072         PrintPartialAlias = PrintMustAlias = true;
00073         PrintNoModRef = PrintMod = PrintRef = PrintModRef = true;
00074       }
00075       return false;
00076     }
00077 
00078     bool runOnFunction(Function &F) override;
00079     bool doFinalization(Module &M) override;
00080   };
00081 }
00082 
00083 char AAEval::ID = 0;
00084 INITIALIZE_PASS_BEGIN(AAEval, "aa-eval",
00085                 "Exhaustive Alias Analysis Precision Evaluator", false, true)
00086 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
00087 INITIALIZE_PASS_END(AAEval, "aa-eval",
00088                 "Exhaustive Alias Analysis Precision Evaluator", false, true)
00089 
00090 FunctionPass *llvm::createAAEvalPass() { return new AAEval(); }
00091 
00092 static void PrintResults(const char *Msg, bool P, const Value *V1,
00093                          const Value *V2, const Module *M) {
00094   if (P) {
00095     std::string o1, o2;
00096     {
00097       raw_string_ostream os1(o1), os2(o2);
00098       V1->printAsOperand(os1, true, M);
00099       V2->printAsOperand(os2, true, M);
00100     }
00101     
00102     if (o2 < o1)
00103       std::swap(o1, o2);
00104     errs() << "  " << Msg << ":\t"
00105            << o1 << ", "
00106            << o2 << "\n";
00107   }
00108 }
00109 
00110 static inline void
00111 PrintModRefResults(const char *Msg, bool P, Instruction *I, Value *Ptr,
00112                    Module *M) {
00113   if (P) {
00114     errs() << "  " << Msg << ":  Ptr: ";
00115     Ptr->printAsOperand(errs(), true, M);
00116     errs() << "\t<->" << *I << '\n';
00117   }
00118 }
00119 
00120 static inline void
00121 PrintModRefResults(const char *Msg, bool P, CallSite CSA, CallSite CSB,
00122                    Module *M) {
00123   if (P) {
00124     errs() << "  " << Msg << ": " << *CSA.getInstruction()
00125            << " <-> " << *CSB.getInstruction() << '\n';
00126   }
00127 }
00128 
00129 static inline void
00130 PrintLoadStoreResults(const char *Msg, bool P, const Value *V1,
00131                       const Value *V2, const Module *M) {
00132   if (P) {
00133     errs() << "  " << Msg << ": " << *V1
00134            << " <-> " << *V2 << '\n';
00135   }
00136 }
00137 
00138 static inline bool isInterestingPointer(Value *V) {
00139   return V->getType()->isPointerTy()
00140       && !isa<ConstantPointerNull>(V);
00141 }
00142 
00143 bool AAEval::runOnFunction(Function &F) {
00144   const DataLayout &DL = F.getParent()->getDataLayout();
00145   AliasAnalysis &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
00146 
00147   SetVector<Value *> Pointers;
00148   SmallSetVector<CallSite, 16> CallSites;
00149   SetVector<Value *> Loads;
00150   SetVector<Value *> Stores;
00151 
00152   for (auto &I : F.args())
00153     if (I.getType()->isPointerTy())    // Add all pointer arguments.
00154       Pointers.insert(&I);
00155 
00156   for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
00157     if (I->getType()->isPointerTy()) // Add all pointer instructions.
00158       Pointers.insert(&*I);
00159     if (EvalAAMD && isa<LoadInst>(&*I))
00160       Loads.insert(&*I);
00161     if (EvalAAMD && isa<StoreInst>(&*I))
00162       Stores.insert(&*I);
00163     Instruction &Inst = *I;
00164     if (auto CS = CallSite(&Inst)) {
00165       Value *Callee = CS.getCalledValue();
00166       // Skip actual functions for direct function calls.
00167       if (!isa<Function>(Callee) && isInterestingPointer(Callee))
00168         Pointers.insert(Callee);
00169       // Consider formals.
00170       for (Use &DataOp : CS.data_ops())
00171         if (isInterestingPointer(DataOp))
00172           Pointers.insert(DataOp);
00173       CallSites.insert(CS);
00174     } else {
00175       // Consider all operands.
00176       for (Instruction::op_iterator OI = Inst.op_begin(), OE = Inst.op_end();
00177            OI != OE; ++OI)
00178         if (isInterestingPointer(*OI))
00179           Pointers.insert(*OI);
00180     }
00181   }
00182 
00183   if (PrintNoAlias || PrintMayAlias || PrintPartialAlias || PrintMustAlias ||
00184       PrintNoModRef || PrintMod || PrintRef || PrintModRef)
00185     errs() << "Function: " << F.getName() << ": " << Pointers.size()
00186            << " pointers, " << CallSites.size() << " call sites\n";
00187 
00188   // iterate over the worklist, and run the full (n^2)/2 disambiguations
00189   for (SetVector<Value *>::iterator I1 = Pointers.begin(), E = Pointers.end();
00190        I1 != E; ++I1) {
00191     uint64_t I1Size = MemoryLocation::UnknownSize;
00192     Type *I1ElTy = cast<PointerType>((*I1)->getType())->getElementType();
00193     if (I1ElTy->isSized()) I1Size = DL.getTypeStoreSize(I1ElTy);
00194 
00195     for (SetVector<Value *>::iterator I2 = Pointers.begin(); I2 != I1; ++I2) {
00196       uint64_t I2Size = MemoryLocation::UnknownSize;
00197       Type *I2ElTy =cast<PointerType>((*I2)->getType())->getElementType();
00198       if (I2ElTy->isSized()) I2Size = DL.getTypeStoreSize(I2ElTy);
00199 
00200       switch (AA.alias(*I1, I1Size, *I2, I2Size)) {
00201       case NoAlias:
00202         PrintResults("NoAlias", PrintNoAlias, *I1, *I2, F.getParent());
00203         ++NoAliasCount;
00204         break;
00205       case MayAlias:
00206         PrintResults("MayAlias", PrintMayAlias, *I1, *I2, F.getParent());
00207         ++MayAliasCount;
00208         break;
00209       case PartialAlias:
00210         PrintResults("PartialAlias", PrintPartialAlias, *I1, *I2,
00211                      F.getParent());
00212         ++PartialAliasCount;
00213         break;
00214       case MustAlias:
00215         PrintResults("MustAlias", PrintMustAlias, *I1, *I2, F.getParent());
00216         ++MustAliasCount;
00217         break;
00218       }
00219     }
00220   }
00221 
00222   if (EvalAAMD) {
00223     // iterate over all pairs of load, store
00224     for (SetVector<Value *>::iterator I1 = Loads.begin(), E = Loads.end();
00225          I1 != E; ++I1) {
00226       for (SetVector<Value *>::iterator I2 = Stores.begin(), E2 = Stores.end();
00227            I2 != E2; ++I2) {
00228         switch (AA.alias(MemoryLocation::get(cast<LoadInst>(*I1)),
00229                          MemoryLocation::get(cast<StoreInst>(*I2)))) {
00230         case NoAlias:
00231           PrintLoadStoreResults("NoAlias", PrintNoAlias, *I1, *I2,
00232                                 F.getParent());
00233           ++NoAliasCount;
00234           break;
00235         case MayAlias:
00236           PrintLoadStoreResults("MayAlias", PrintMayAlias, *I1, *I2,
00237                                 F.getParent());
00238           ++MayAliasCount;
00239           break;
00240         case PartialAlias:
00241           PrintLoadStoreResults("PartialAlias", PrintPartialAlias, *I1, *I2,
00242                                 F.getParent());
00243           ++PartialAliasCount;
00244           break;
00245         case MustAlias:
00246           PrintLoadStoreResults("MustAlias", PrintMustAlias, *I1, *I2,
00247                                 F.getParent());
00248           ++MustAliasCount;
00249           break;
00250         }
00251       }
00252     }
00253 
00254     // iterate over all pairs of store, store
00255     for (SetVector<Value *>::iterator I1 = Stores.begin(), E = Stores.end();
00256          I1 != E; ++I1) {
00257       for (SetVector<Value *>::iterator I2 = Stores.begin(); I2 != I1; ++I2) {
00258         switch (AA.alias(MemoryLocation::get(cast<StoreInst>(*I1)),
00259                          MemoryLocation::get(cast<StoreInst>(*I2)))) {
00260         case NoAlias:
00261           PrintLoadStoreResults("NoAlias", PrintNoAlias, *I1, *I2,
00262                                 F.getParent());
00263           ++NoAliasCount;
00264           break;
00265         case MayAlias:
00266           PrintLoadStoreResults("MayAlias", PrintMayAlias, *I1, *I2,
00267                                 F.getParent());
00268           ++MayAliasCount;
00269           break;
00270         case PartialAlias:
00271           PrintLoadStoreResults("PartialAlias", PrintPartialAlias, *I1, *I2,
00272                                 F.getParent());
00273           ++PartialAliasCount;
00274           break;
00275         case MustAlias:
00276           PrintLoadStoreResults("MustAlias", PrintMustAlias, *I1, *I2,
00277                                 F.getParent());
00278           ++MustAliasCount;
00279           break;
00280         }
00281       }
00282     }
00283   }
00284 
00285   // Mod/ref alias analysis: compare all pairs of calls and values
00286   for (auto C = CallSites.begin(), Ce = CallSites.end(); C != Ce; ++C) {
00287     Instruction *I = C->getInstruction();
00288 
00289     for (SetVector<Value *>::iterator V = Pointers.begin(), Ve = Pointers.end();
00290          V != Ve; ++V) {
00291       uint64_t Size = MemoryLocation::UnknownSize;
00292       Type *ElTy = cast<PointerType>((*V)->getType())->getElementType();
00293       if (ElTy->isSized()) Size = DL.getTypeStoreSize(ElTy);
00294 
00295       switch (AA.getModRefInfo(*C, *V, Size)) {
00296       case MRI_NoModRef:
00297         PrintModRefResults("NoModRef", PrintNoModRef, I, *V, F.getParent());
00298         ++NoModRefCount;
00299         break;
00300       case MRI_Mod:
00301         PrintModRefResults("Just Mod", PrintMod, I, *V, F.getParent());
00302         ++ModCount;
00303         break;
00304       case MRI_Ref:
00305         PrintModRefResults("Just Ref", PrintRef, I, *V, F.getParent());
00306         ++RefCount;
00307         break;
00308       case MRI_ModRef:
00309         PrintModRefResults("Both ModRef", PrintModRef, I, *V, F.getParent());
00310         ++ModRefCount;
00311         break;
00312       }
00313     }
00314   }
00315 
00316   // Mod/ref alias analysis: compare all pairs of calls
00317   for (auto C = CallSites.begin(), Ce = CallSites.end(); C != Ce; ++C) {
00318     for (auto D = CallSites.begin(); D != Ce; ++D) {
00319       if (D == C)
00320         continue;
00321       switch (AA.getModRefInfo(*C, *D)) {
00322       case MRI_NoModRef:
00323         PrintModRefResults("NoModRef", PrintNoModRef, *C, *D, F.getParent());
00324         ++NoModRefCount;
00325         break;
00326       case MRI_Mod:
00327         PrintModRefResults("Just Mod", PrintMod, *C, *D, F.getParent());
00328         ++ModCount;
00329         break;
00330       case MRI_Ref:
00331         PrintModRefResults("Just Ref", PrintRef, *C, *D, F.getParent());
00332         ++RefCount;
00333         break;
00334       case MRI_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 }