LLVM API Documentation

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> EvalTBAA("evaluate-tbaa", cl::ReallyHidden);
00047 
00048 namespace {
00049   class AAEval : public FunctionPass {
00050     unsigned NoAlias, MayAlias, PartialAlias, MustAlias;
00051     unsigned NoModRef, Mod, Ref, ModRef;
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       NoAlias = MayAlias = PartialAlias = MustAlias = 0;
00066       NoModRef = Mod = Ref = ModRef = 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 (EvalTBAA && isa<LoadInst>(&*I))
00157       Loads.insert(&*I);
00158     if (EvalTBAA && isa<StoreInst>(&*I))
00159       Stores.insert(&*I);
00160     Instruction &Inst = *I;
00161     if (CallSite CS = cast<Value>(&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 = AliasAnalysis::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 = AliasAnalysis::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 AliasAnalysis::NoAlias:
00200         PrintResults("NoAlias", PrintNoAlias, *I1, *I2, F.getParent());
00201         ++NoAlias; break;
00202       case AliasAnalysis::MayAlias:
00203         PrintResults("MayAlias", PrintMayAlias, *I1, *I2, F.getParent());
00204         ++MayAlias; break;
00205       case AliasAnalysis::PartialAlias:
00206         PrintResults("PartialAlias", PrintPartialAlias, *I1, *I2,
00207                      F.getParent());
00208         ++PartialAlias; break;
00209       case AliasAnalysis::MustAlias:
00210         PrintResults("MustAlias", PrintMustAlias, *I1, *I2, F.getParent());
00211         ++MustAlias; break;
00212       }
00213     }
00214   }
00215 
00216   if (EvalTBAA) {
00217     // iterate over all pairs of load, store
00218     for (SetVector<Value *>::iterator I1 = Loads.begin(), E = Loads.end();
00219          I1 != E; ++I1) {
00220       for (SetVector<Value *>::iterator I2 = Stores.begin(), E2 = Stores.end();
00221            I2 != E2; ++I2) {
00222         switch (AA.alias(AA.getLocation(cast<LoadInst>(*I1)),
00223                          AA.getLocation(cast<StoreInst>(*I2)))) {
00224         case AliasAnalysis::NoAlias:
00225           PrintLoadStoreResults("NoAlias", PrintNoAlias, *I1, *I2,
00226                                 F.getParent());
00227           ++NoAlias; break;
00228         case AliasAnalysis::MayAlias:
00229           PrintLoadStoreResults("MayAlias", PrintMayAlias, *I1, *I2,
00230                                 F.getParent());
00231           ++MayAlias; break;
00232         case AliasAnalysis::PartialAlias:
00233           PrintLoadStoreResults("PartialAlias", PrintPartialAlias, *I1, *I2,
00234                                 F.getParent());
00235           ++PartialAlias; break;
00236         case AliasAnalysis::MustAlias:
00237           PrintLoadStoreResults("MustAlias", PrintMustAlias, *I1, *I2,
00238                                 F.getParent());
00239           ++MustAlias; break;
00240         }
00241       }
00242     }
00243 
00244     // iterate over all pairs of store, store
00245     for (SetVector<Value *>::iterator I1 = Stores.begin(), E = Stores.end();
00246          I1 != E; ++I1) {
00247       for (SetVector<Value *>::iterator I2 = Stores.begin(); I2 != I1; ++I2) {
00248         switch (AA.alias(AA.getLocation(cast<StoreInst>(*I1)),
00249                          AA.getLocation(cast<StoreInst>(*I2)))) {
00250         case AliasAnalysis::NoAlias:
00251           PrintLoadStoreResults("NoAlias", PrintNoAlias, *I1, *I2,
00252                                 F.getParent());
00253           ++NoAlias; break;
00254         case AliasAnalysis::MayAlias:
00255           PrintLoadStoreResults("MayAlias", PrintMayAlias, *I1, *I2,
00256                                 F.getParent());
00257           ++MayAlias; break;
00258         case AliasAnalysis::PartialAlias:
00259           PrintLoadStoreResults("PartialAlias", PrintPartialAlias, *I1, *I2,
00260                                 F.getParent());
00261           ++PartialAlias; break;
00262         case AliasAnalysis::MustAlias:
00263           PrintLoadStoreResults("MustAlias", PrintMustAlias, *I1, *I2,
00264                                 F.getParent());
00265           ++MustAlias; break;
00266         }
00267       }
00268     }
00269   }
00270 
00271   // Mod/ref alias analysis: compare all pairs of calls and values
00272   for (SetVector<CallSite>::iterator C = CallSites.begin(),
00273          Ce = CallSites.end(); C != Ce; ++C) {
00274     Instruction *I = C->getInstruction();
00275 
00276     for (SetVector<Value *>::iterator V = Pointers.begin(), Ve = Pointers.end();
00277          V != Ve; ++V) {
00278       uint64_t Size = AliasAnalysis::UnknownSize;
00279       Type *ElTy = cast<PointerType>((*V)->getType())->getElementType();
00280       if (ElTy->isSized()) Size = AA.getTypeStoreSize(ElTy);
00281 
00282       switch (AA.getModRefInfo(*C, *V, Size)) {
00283       case AliasAnalysis::NoModRef:
00284         PrintModRefResults("NoModRef", PrintNoModRef, I, *V, F.getParent());
00285         ++NoModRef; break;
00286       case AliasAnalysis::Mod:
00287         PrintModRefResults("Just Mod", PrintMod, I, *V, F.getParent());
00288         ++Mod; break;
00289       case AliasAnalysis::Ref:
00290         PrintModRefResults("Just Ref", PrintRef, I, *V, F.getParent());
00291         ++Ref; break;
00292       case AliasAnalysis::ModRef:
00293         PrintModRefResults("Both ModRef", PrintModRef, I, *V, F.getParent());
00294         ++ModRef; break;
00295       }
00296     }
00297   }
00298 
00299   // Mod/ref alias analysis: compare all pairs of calls
00300   for (SetVector<CallSite>::iterator C = CallSites.begin(),
00301          Ce = CallSites.end(); C != Ce; ++C) {
00302     for (SetVector<CallSite>::iterator D = CallSites.begin(); D != Ce; ++D) {
00303       if (D == C)
00304         continue;
00305       switch (AA.getModRefInfo(*C, *D)) {
00306       case AliasAnalysis::NoModRef:
00307         PrintModRefResults("NoModRef", PrintNoModRef, *C, *D, F.getParent());
00308         ++NoModRef; break;
00309       case AliasAnalysis::Mod:
00310         PrintModRefResults("Just Mod", PrintMod, *C, *D, F.getParent());
00311         ++Mod; break;
00312       case AliasAnalysis::Ref:
00313         PrintModRefResults("Just Ref", PrintRef, *C, *D, F.getParent());
00314         ++Ref; break;
00315       case AliasAnalysis::ModRef:
00316         PrintModRefResults("Both ModRef", PrintModRef, *C, *D, F.getParent());
00317         ++ModRef; break;
00318       }
00319     }
00320   }
00321 
00322   return false;
00323 }
00324 
00325 static void PrintPercent(unsigned Num, unsigned Sum) {
00326   errs() << "(" << Num*100ULL/Sum << "."
00327          << ((Num*1000ULL/Sum) % 10) << "%)\n";
00328 }
00329 
00330 bool AAEval::doFinalization(Module &M) {
00331   unsigned AliasSum = NoAlias + MayAlias + PartialAlias + MustAlias;
00332   errs() << "===== Alias Analysis Evaluator Report =====\n";
00333   if (AliasSum == 0) {
00334     errs() << "  Alias Analysis Evaluator Summary: No pointers!\n";
00335   } else {
00336     errs() << "  " << AliasSum << " Total Alias Queries Performed\n";
00337     errs() << "  " << NoAlias << " no alias responses ";
00338     PrintPercent(NoAlias, AliasSum);
00339     errs() << "  " << MayAlias << " may alias responses ";
00340     PrintPercent(MayAlias, AliasSum);
00341     errs() << "  " << PartialAlias << " partial alias responses ";
00342     PrintPercent(PartialAlias, AliasSum);
00343     errs() << "  " << MustAlias << " must alias responses ";
00344     PrintPercent(MustAlias, AliasSum);
00345     errs() << "  Alias Analysis Evaluator Pointer Alias Summary: "
00346            << NoAlias*100/AliasSum  << "%/" << MayAlias*100/AliasSum << "%/"
00347            << PartialAlias*100/AliasSum << "%/"
00348            << MustAlias*100/AliasSum << "%\n";
00349   }
00350 
00351   // Display the summary for mod/ref analysis
00352   unsigned ModRefSum = NoModRef + Mod + Ref + ModRef;
00353   if (ModRefSum == 0) {
00354     errs() << "  Alias Analysis Mod/Ref Evaluator Summary: no mod/ref!\n";
00355   } else {
00356     errs() << "  " << ModRefSum << " Total ModRef Queries Performed\n";
00357     errs() << "  " << NoModRef << " no mod/ref responses ";
00358     PrintPercent(NoModRef, ModRefSum);
00359     errs() << "  " << Mod << " mod responses ";
00360     PrintPercent(Mod, ModRefSum);
00361     errs() << "  " << Ref << " ref responses ";
00362     PrintPercent(Ref, ModRefSum);
00363     errs() << "  " << ModRef << " mod & ref responses ";
00364     PrintPercent(ModRef, ModRefSum);
00365     errs() << "  Alias Analysis Evaluator Mod/Ref Summary: "
00366            << NoModRef*100/ModRefSum  << "%/" << Mod*100/ModRefSum << "%/"
00367            << Ref*100/ModRefSum << "%/" << ModRef*100/ModRefSum << "%\n";
00368   }
00369 
00370   return false;
00371 }