AliasAnalysisEvaluator.cpp revision 198090
1193323Sed//===- AliasAnalysisEvaluator.cpp - Alias Analysis Accuracy Evaluator -----===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file implements a simple N^2 alias analysis accuracy evaluator. 11193323Sed// Basically, for each function in the program, it simply queries to see how the 12193323Sed// alias analysis implementation answers alias queries between each pair of 13193323Sed// pointers in the function. 14193323Sed// 15193323Sed// This is inspired and adapted from code by: Naveen Neelakantam, Francesco 16193323Sed// Spadini, and Wojciech Stryjewski. 17193323Sed// 18193323Sed//===----------------------------------------------------------------------===// 19193323Sed 20193323Sed#include "llvm/Constants.h" 21193323Sed#include "llvm/DerivedTypes.h" 22193323Sed#include "llvm/Function.h" 23193323Sed#include "llvm/Instructions.h" 24193323Sed#include "llvm/Pass.h" 25193323Sed#include "llvm/Analysis/Passes.h" 26193323Sed#include "llvm/Analysis/AliasAnalysis.h" 27193323Sed#include "llvm/Assembly/Writer.h" 28193323Sed#include "llvm/Target/TargetData.h" 29193323Sed#include "llvm/Support/InstIterator.h" 30193323Sed#include "llvm/Support/CommandLine.h" 31193323Sed#include "llvm/Support/Compiler.h" 32198090Srdivacky#include "llvm/Support/raw_ostream.h" 33198090Srdivacky#include "llvm/ADT/SetVector.h" 34193323Sedusing namespace llvm; 35193323Sed 36193323Sedstatic cl::opt<bool> PrintAll("print-all-alias-modref-info", cl::ReallyHidden); 37193323Sed 38193323Sedstatic cl::opt<bool> PrintNoAlias("print-no-aliases", cl::ReallyHidden); 39193323Sedstatic cl::opt<bool> PrintMayAlias("print-may-aliases", cl::ReallyHidden); 40193323Sedstatic cl::opt<bool> PrintMustAlias("print-must-aliases", cl::ReallyHidden); 41193323Sed 42193323Sedstatic cl::opt<bool> PrintNoModRef("print-no-modref", cl::ReallyHidden); 43193323Sedstatic cl::opt<bool> PrintMod("print-mod", cl::ReallyHidden); 44193323Sedstatic cl::opt<bool> PrintRef("print-ref", cl::ReallyHidden); 45193323Sedstatic cl::opt<bool> PrintModRef("print-modref", cl::ReallyHidden); 46193323Sed 47193323Sednamespace { 48193323Sed class VISIBILITY_HIDDEN AAEval : public FunctionPass { 49193323Sed unsigned NoAlias, MayAlias, MustAlias; 50193323Sed unsigned NoModRef, Mod, Ref, ModRef; 51193323Sed 52193323Sed public: 53193323Sed static char ID; // Pass identification, replacement for typeid 54193323Sed AAEval() : FunctionPass(&ID) {} 55193323Sed 56193323Sed virtual void getAnalysisUsage(AnalysisUsage &AU) const { 57193323Sed AU.addRequired<AliasAnalysis>(); 58193323Sed AU.setPreservesAll(); 59193323Sed } 60193323Sed 61193323Sed bool doInitialization(Module &M) { 62193323Sed NoAlias = MayAlias = MustAlias = 0; 63193323Sed NoModRef = Mod = Ref = ModRef = 0; 64193323Sed 65193323Sed if (PrintAll) { 66193323Sed PrintNoAlias = PrintMayAlias = PrintMustAlias = true; 67193323Sed PrintNoModRef = PrintMod = PrintRef = PrintModRef = true; 68193323Sed } 69193323Sed return false; 70193323Sed } 71193323Sed 72193323Sed bool runOnFunction(Function &F); 73193323Sed bool doFinalization(Module &M); 74193323Sed }; 75193323Sed} 76193323Sed 77193323Sedchar AAEval::ID = 0; 78193323Sedstatic RegisterPass<AAEval> 79193323SedX("aa-eval", "Exhaustive Alias Analysis Precision Evaluator", false, true); 80193323Sed 81193323SedFunctionPass *llvm::createAAEvalPass() { return new AAEval(); } 82193323Sed 83198090Srdivackystatic void PrintResults(const char *Msg, bool P, const Value *V1, 84198090Srdivacky const Value *V2, const Module *M) { 85193323Sed if (P) { 86198090Srdivacky std::string o1, o2; 87198090Srdivacky { 88198090Srdivacky raw_string_ostream os1(o1), os2(o2); 89198090Srdivacky WriteAsOperand(os1, V1, true, M); 90198090Srdivacky WriteAsOperand(os2, V2, true, M); 91198090Srdivacky } 92198090Srdivacky 93193323Sed if (o2 < o1) 94198090Srdivacky std::swap(o1, o2); 95198090Srdivacky errs() << " " << Msg << ":\t" 96198090Srdivacky << o1 << ", " 97198090Srdivacky << o2 << "\n"; 98193323Sed } 99193323Sed} 100193323Sed 101193323Sedstatic inline void 102193323SedPrintModRefResults(const char *Msg, bool P, Instruction *I, Value *Ptr, 103193323Sed Module *M) { 104193323Sed if (P) { 105198090Srdivacky errs() << " " << Msg << ": Ptr: "; 106198090Srdivacky WriteAsOperand(errs(), Ptr, true, M); 107198090Srdivacky errs() << "\t<->" << *I << '\n'; 108193323Sed } 109193323Sed} 110193323Sed 111193323Sedbool AAEval::runOnFunction(Function &F) { 112193323Sed AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 113193323Sed 114198090Srdivacky SetVector<Value *> Pointers; 115198090Srdivacky SetVector<CallSite> CallSites; 116193323Sed 117193323Sed for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) 118193323Sed if (isa<PointerType>(I->getType())) // Add all pointer arguments 119193323Sed Pointers.insert(I); 120193323Sed 121193323Sed for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) { 122193323Sed if (isa<PointerType>(I->getType())) // Add all pointer instructions 123193323Sed Pointers.insert(&*I); 124193323Sed Instruction &Inst = *I; 125193323Sed User::op_iterator OI = Inst.op_begin(); 126193323Sed CallSite CS = CallSite::get(&Inst); 127193323Sed if (CS.getInstruction() && 128193323Sed isa<Function>(CS.getCalledValue())) 129193323Sed ++OI; // Skip actual functions for direct function calls. 130193323Sed for (; OI != Inst.op_end(); ++OI) 131193323Sed if (isa<PointerType>((*OI)->getType()) && !isa<ConstantPointerNull>(*OI)) 132193323Sed Pointers.insert(*OI); 133193323Sed 134193323Sed if (CS.getInstruction()) CallSites.insert(CS); 135193323Sed } 136193323Sed 137193323Sed if (PrintNoAlias || PrintMayAlias || PrintMustAlias || 138193323Sed PrintNoModRef || PrintMod || PrintRef || PrintModRef) 139198090Srdivacky errs() << "Function: " << F.getName() << ": " << Pointers.size() 140198090Srdivacky << " pointers, " << CallSites.size() << " call sites\n"; 141193323Sed 142193323Sed // iterate over the worklist, and run the full (n^2)/2 disambiguations 143198090Srdivacky for (SetVector<Value *>::iterator I1 = Pointers.begin(), E = Pointers.end(); 144193323Sed I1 != E; ++I1) { 145198090Srdivacky unsigned I1Size = ~0u; 146193323Sed const Type *I1ElTy = cast<PointerType>((*I1)->getType())->getElementType(); 147198090Srdivacky if (I1ElTy->isSized()) I1Size = AA.getTypeStoreSize(I1ElTy); 148193323Sed 149198090Srdivacky for (SetVector<Value *>::iterator I2 = Pointers.begin(); I2 != I1; ++I2) { 150198090Srdivacky unsigned I2Size = ~0u; 151193323Sed const Type *I2ElTy =cast<PointerType>((*I2)->getType())->getElementType(); 152198090Srdivacky if (I2ElTy->isSized()) I2Size = AA.getTypeStoreSize(I2ElTy); 153193323Sed 154193323Sed switch (AA.alias(*I1, I1Size, *I2, I2Size)) { 155193323Sed case AliasAnalysis::NoAlias: 156193323Sed PrintResults("NoAlias", PrintNoAlias, *I1, *I2, F.getParent()); 157193323Sed ++NoAlias; break; 158193323Sed case AliasAnalysis::MayAlias: 159193323Sed PrintResults("MayAlias", PrintMayAlias, *I1, *I2, F.getParent()); 160193323Sed ++MayAlias; break; 161193323Sed case AliasAnalysis::MustAlias: 162193323Sed PrintResults("MustAlias", PrintMustAlias, *I1, *I2, F.getParent()); 163193323Sed ++MustAlias; break; 164193323Sed default: 165198090Srdivacky errs() << "Unknown alias query result!\n"; 166193323Sed } 167193323Sed } 168193323Sed } 169193323Sed 170193323Sed // Mod/ref alias analysis: compare all pairs of calls and values 171198090Srdivacky for (SetVector<CallSite>::iterator C = CallSites.begin(), 172193323Sed Ce = CallSites.end(); C != Ce; ++C) { 173193323Sed Instruction *I = C->getInstruction(); 174193323Sed 175198090Srdivacky for (SetVector<Value *>::iterator V = Pointers.begin(), Ve = Pointers.end(); 176193323Sed V != Ve; ++V) { 177198090Srdivacky unsigned Size = ~0u; 178193323Sed const Type *ElTy = cast<PointerType>((*V)->getType())->getElementType(); 179198090Srdivacky if (ElTy->isSized()) Size = AA.getTypeStoreSize(ElTy); 180193323Sed 181193323Sed switch (AA.getModRefInfo(*C, *V, Size)) { 182193323Sed case AliasAnalysis::NoModRef: 183193323Sed PrintModRefResults("NoModRef", PrintNoModRef, I, *V, F.getParent()); 184193323Sed ++NoModRef; break; 185193323Sed case AliasAnalysis::Mod: 186193323Sed PrintModRefResults(" Mod", PrintMod, I, *V, F.getParent()); 187193323Sed ++Mod; break; 188193323Sed case AliasAnalysis::Ref: 189193323Sed PrintModRefResults(" Ref", PrintRef, I, *V, F.getParent()); 190193323Sed ++Ref; break; 191193323Sed case AliasAnalysis::ModRef: 192193323Sed PrintModRefResults(" ModRef", PrintModRef, I, *V, F.getParent()); 193193323Sed ++ModRef; break; 194193323Sed default: 195198090Srdivacky errs() << "Unknown alias query result!\n"; 196193323Sed } 197193323Sed } 198193323Sed } 199193323Sed 200193323Sed return false; 201193323Sed} 202193323Sed 203193323Sedstatic void PrintPercent(unsigned Num, unsigned Sum) { 204198090Srdivacky errs() << "(" << Num*100ULL/Sum << "." 205198090Srdivacky << ((Num*1000ULL/Sum) % 10) << "%)\n"; 206193323Sed} 207193323Sed 208193323Sedbool AAEval::doFinalization(Module &M) { 209193323Sed unsigned AliasSum = NoAlias + MayAlias + MustAlias; 210198090Srdivacky errs() << "===== Alias Analysis Evaluator Report =====\n"; 211193323Sed if (AliasSum == 0) { 212198090Srdivacky errs() << " Alias Analysis Evaluator Summary: No pointers!\n"; 213193323Sed } else { 214198090Srdivacky errs() << " " << AliasSum << " Total Alias Queries Performed\n"; 215198090Srdivacky errs() << " " << NoAlias << " no alias responses "; 216193323Sed PrintPercent(NoAlias, AliasSum); 217198090Srdivacky errs() << " " << MayAlias << " may alias responses "; 218193323Sed PrintPercent(MayAlias, AliasSum); 219198090Srdivacky errs() << " " << MustAlias << " must alias responses "; 220193323Sed PrintPercent(MustAlias, AliasSum); 221198090Srdivacky errs() << " Alias Analysis Evaluator Pointer Alias Summary: " 222198090Srdivacky << NoAlias*100/AliasSum << "%/" << MayAlias*100/AliasSum << "%/" 223198090Srdivacky << MustAlias*100/AliasSum << "%\n"; 224193323Sed } 225193323Sed 226193323Sed // Display the summary for mod/ref analysis 227193323Sed unsigned ModRefSum = NoModRef + Mod + Ref + ModRef; 228193323Sed if (ModRefSum == 0) { 229198090Srdivacky errs() << " Alias Analysis Mod/Ref Evaluator Summary: no mod/ref!\n"; 230193323Sed } else { 231198090Srdivacky errs() << " " << ModRefSum << " Total ModRef Queries Performed\n"; 232198090Srdivacky errs() << " " << NoModRef << " no mod/ref responses "; 233193323Sed PrintPercent(NoModRef, ModRefSum); 234198090Srdivacky errs() << " " << Mod << " mod responses "; 235193323Sed PrintPercent(Mod, ModRefSum); 236198090Srdivacky errs() << " " << Ref << " ref responses "; 237193323Sed PrintPercent(Ref, ModRefSum); 238198090Srdivacky errs() << " " << ModRef << " mod & ref responses "; 239193323Sed PrintPercent(ModRef, ModRefSum); 240198090Srdivacky errs() << " Alias Analysis Evaluator Mod/Ref Summary: " 241198090Srdivacky << NoModRef*100/ModRefSum << "%/" << Mod*100/ModRefSum << "%/" 242198090Srdivacky << Ref*100/ModRefSum << "%/" << ModRef*100/ModRefSum << "%\n"; 243193323Sed } 244193323Sed 245193323Sed return false; 246193323Sed} 247