AliasAnalysisEvaluator.cpp revision 198892
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" 31198090Srdivacky#include "llvm/Support/raw_ostream.h" 32198090Srdivacky#include "llvm/ADT/SetVector.h" 33193323Sedusing namespace llvm; 34193323Sed 35193323Sedstatic cl::opt<bool> PrintAll("print-all-alias-modref-info", cl::ReallyHidden); 36193323Sed 37193323Sedstatic cl::opt<bool> PrintNoAlias("print-no-aliases", cl::ReallyHidden); 38193323Sedstatic cl::opt<bool> PrintMayAlias("print-may-aliases", cl::ReallyHidden); 39193323Sedstatic cl::opt<bool> PrintMustAlias("print-must-aliases", cl::ReallyHidden); 40193323Sed 41193323Sedstatic cl::opt<bool> PrintNoModRef("print-no-modref", cl::ReallyHidden); 42193323Sedstatic cl::opt<bool> PrintMod("print-mod", cl::ReallyHidden); 43193323Sedstatic cl::opt<bool> PrintRef("print-ref", cl::ReallyHidden); 44193323Sedstatic cl::opt<bool> PrintModRef("print-modref", cl::ReallyHidden); 45193323Sed 46193323Sednamespace { 47198892Srdivacky class AAEval : public FunctionPass { 48193323Sed unsigned NoAlias, MayAlias, MustAlias; 49193323Sed unsigned NoModRef, Mod, Ref, ModRef; 50193323Sed 51193323Sed public: 52193323Sed static char ID; // Pass identification, replacement for typeid 53193323Sed AAEval() : FunctionPass(&ID) {} 54193323Sed 55193323Sed virtual void getAnalysisUsage(AnalysisUsage &AU) const { 56193323Sed AU.addRequired<AliasAnalysis>(); 57193323Sed AU.setPreservesAll(); 58193323Sed } 59193323Sed 60193323Sed bool doInitialization(Module &M) { 61193323Sed NoAlias = MayAlias = MustAlias = 0; 62193323Sed NoModRef = Mod = Ref = ModRef = 0; 63193323Sed 64193323Sed if (PrintAll) { 65193323Sed PrintNoAlias = PrintMayAlias = PrintMustAlias = true; 66193323Sed PrintNoModRef = PrintMod = PrintRef = PrintModRef = true; 67193323Sed } 68193323Sed return false; 69193323Sed } 70193323Sed 71193323Sed bool runOnFunction(Function &F); 72193323Sed bool doFinalization(Module &M); 73193323Sed }; 74193323Sed} 75193323Sed 76193323Sedchar AAEval::ID = 0; 77193323Sedstatic RegisterPass<AAEval> 78193323SedX("aa-eval", "Exhaustive Alias Analysis Precision Evaluator", false, true); 79193323Sed 80193323SedFunctionPass *llvm::createAAEvalPass() { return new AAEval(); } 81193323Sed 82198090Srdivackystatic void PrintResults(const char *Msg, bool P, const Value *V1, 83198090Srdivacky const Value *V2, const Module *M) { 84193323Sed if (P) { 85198090Srdivacky std::string o1, o2; 86198090Srdivacky { 87198090Srdivacky raw_string_ostream os1(o1), os2(o2); 88198090Srdivacky WriteAsOperand(os1, V1, true, M); 89198090Srdivacky WriteAsOperand(os2, V2, true, M); 90198090Srdivacky } 91198090Srdivacky 92193323Sed if (o2 < o1) 93198090Srdivacky std::swap(o1, o2); 94198090Srdivacky errs() << " " << Msg << ":\t" 95198090Srdivacky << o1 << ", " 96198090Srdivacky << o2 << "\n"; 97193323Sed } 98193323Sed} 99193323Sed 100193323Sedstatic inline void 101193323SedPrintModRefResults(const char *Msg, bool P, Instruction *I, Value *Ptr, 102193323Sed Module *M) { 103193323Sed if (P) { 104198090Srdivacky errs() << " " << Msg << ": Ptr: "; 105198090Srdivacky WriteAsOperand(errs(), Ptr, true, M); 106198090Srdivacky errs() << "\t<->" << *I << '\n'; 107193323Sed } 108193323Sed} 109193323Sed 110193323Sedbool AAEval::runOnFunction(Function &F) { 111193323Sed AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 112193323Sed 113198090Srdivacky SetVector<Value *> Pointers; 114198090Srdivacky SetVector<CallSite> CallSites; 115193323Sed 116193323Sed for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) 117193323Sed if (isa<PointerType>(I->getType())) // Add all pointer arguments 118193323Sed Pointers.insert(I); 119193323Sed 120193323Sed for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) { 121193323Sed if (isa<PointerType>(I->getType())) // Add all pointer instructions 122193323Sed Pointers.insert(&*I); 123193323Sed Instruction &Inst = *I; 124193323Sed User::op_iterator OI = Inst.op_begin(); 125193323Sed CallSite CS = CallSite::get(&Inst); 126193323Sed if (CS.getInstruction() && 127193323Sed isa<Function>(CS.getCalledValue())) 128193323Sed ++OI; // Skip actual functions for direct function calls. 129193323Sed for (; OI != Inst.op_end(); ++OI) 130193323Sed if (isa<PointerType>((*OI)->getType()) && !isa<ConstantPointerNull>(*OI)) 131193323Sed Pointers.insert(*OI); 132193323Sed 133193323Sed if (CS.getInstruction()) CallSites.insert(CS); 134193323Sed } 135193323Sed 136193323Sed if (PrintNoAlias || PrintMayAlias || PrintMustAlias || 137193323Sed PrintNoModRef || PrintMod || PrintRef || PrintModRef) 138198090Srdivacky errs() << "Function: " << F.getName() << ": " << Pointers.size() 139198090Srdivacky << " pointers, " << CallSites.size() << " call sites\n"; 140193323Sed 141193323Sed // iterate over the worklist, and run the full (n^2)/2 disambiguations 142198090Srdivacky for (SetVector<Value *>::iterator I1 = Pointers.begin(), E = Pointers.end(); 143193323Sed I1 != E; ++I1) { 144198090Srdivacky unsigned I1Size = ~0u; 145193323Sed const Type *I1ElTy = cast<PointerType>((*I1)->getType())->getElementType(); 146198090Srdivacky if (I1ElTy->isSized()) I1Size = AA.getTypeStoreSize(I1ElTy); 147193323Sed 148198090Srdivacky for (SetVector<Value *>::iterator I2 = Pointers.begin(); I2 != I1; ++I2) { 149198090Srdivacky unsigned I2Size = ~0u; 150193323Sed const Type *I2ElTy =cast<PointerType>((*I2)->getType())->getElementType(); 151198090Srdivacky if (I2ElTy->isSized()) I2Size = AA.getTypeStoreSize(I2ElTy); 152193323Sed 153193323Sed switch (AA.alias(*I1, I1Size, *I2, I2Size)) { 154193323Sed case AliasAnalysis::NoAlias: 155193323Sed PrintResults("NoAlias", PrintNoAlias, *I1, *I2, F.getParent()); 156193323Sed ++NoAlias; break; 157193323Sed case AliasAnalysis::MayAlias: 158193323Sed PrintResults("MayAlias", PrintMayAlias, *I1, *I2, F.getParent()); 159193323Sed ++MayAlias; break; 160193323Sed case AliasAnalysis::MustAlias: 161193323Sed PrintResults("MustAlias", PrintMustAlias, *I1, *I2, F.getParent()); 162193323Sed ++MustAlias; break; 163193323Sed default: 164198090Srdivacky errs() << "Unknown alias query result!\n"; 165193323Sed } 166193323Sed } 167193323Sed } 168193323Sed 169193323Sed // Mod/ref alias analysis: compare all pairs of calls and values 170198090Srdivacky for (SetVector<CallSite>::iterator C = CallSites.begin(), 171193323Sed Ce = CallSites.end(); C != Ce; ++C) { 172193323Sed Instruction *I = C->getInstruction(); 173193323Sed 174198090Srdivacky for (SetVector<Value *>::iterator V = Pointers.begin(), Ve = Pointers.end(); 175193323Sed V != Ve; ++V) { 176198090Srdivacky unsigned Size = ~0u; 177193323Sed const Type *ElTy = cast<PointerType>((*V)->getType())->getElementType(); 178198090Srdivacky if (ElTy->isSized()) Size = AA.getTypeStoreSize(ElTy); 179193323Sed 180193323Sed switch (AA.getModRefInfo(*C, *V, Size)) { 181193323Sed case AliasAnalysis::NoModRef: 182193323Sed PrintModRefResults("NoModRef", PrintNoModRef, I, *V, F.getParent()); 183193323Sed ++NoModRef; break; 184193323Sed case AliasAnalysis::Mod: 185193323Sed PrintModRefResults(" Mod", PrintMod, I, *V, F.getParent()); 186193323Sed ++Mod; break; 187193323Sed case AliasAnalysis::Ref: 188193323Sed PrintModRefResults(" Ref", PrintRef, I, *V, F.getParent()); 189193323Sed ++Ref; break; 190193323Sed case AliasAnalysis::ModRef: 191193323Sed PrintModRefResults(" ModRef", PrintModRef, I, *V, F.getParent()); 192193323Sed ++ModRef; break; 193193323Sed default: 194198090Srdivacky errs() << "Unknown alias query result!\n"; 195193323Sed } 196193323Sed } 197193323Sed } 198193323Sed 199193323Sed return false; 200193323Sed} 201193323Sed 202193323Sedstatic void PrintPercent(unsigned Num, unsigned Sum) { 203198090Srdivacky errs() << "(" << Num*100ULL/Sum << "." 204198090Srdivacky << ((Num*1000ULL/Sum) % 10) << "%)\n"; 205193323Sed} 206193323Sed 207193323Sedbool AAEval::doFinalization(Module &M) { 208193323Sed unsigned AliasSum = NoAlias + MayAlias + MustAlias; 209198090Srdivacky errs() << "===== Alias Analysis Evaluator Report =====\n"; 210193323Sed if (AliasSum == 0) { 211198090Srdivacky errs() << " Alias Analysis Evaluator Summary: No pointers!\n"; 212193323Sed } else { 213198090Srdivacky errs() << " " << AliasSum << " Total Alias Queries Performed\n"; 214198090Srdivacky errs() << " " << NoAlias << " no alias responses "; 215193323Sed PrintPercent(NoAlias, AliasSum); 216198090Srdivacky errs() << " " << MayAlias << " may alias responses "; 217193323Sed PrintPercent(MayAlias, AliasSum); 218198090Srdivacky errs() << " " << MustAlias << " must alias responses "; 219193323Sed PrintPercent(MustAlias, AliasSum); 220198090Srdivacky errs() << " Alias Analysis Evaluator Pointer Alias Summary: " 221198090Srdivacky << NoAlias*100/AliasSum << "%/" << MayAlias*100/AliasSum << "%/" 222198090Srdivacky << MustAlias*100/AliasSum << "%\n"; 223193323Sed } 224193323Sed 225193323Sed // Display the summary for mod/ref analysis 226193323Sed unsigned ModRefSum = NoModRef + Mod + Ref + ModRef; 227193323Sed if (ModRefSum == 0) { 228198090Srdivacky errs() << " Alias Analysis Mod/Ref Evaluator Summary: no mod/ref!\n"; 229193323Sed } else { 230198090Srdivacky errs() << " " << ModRefSum << " Total ModRef Queries Performed\n"; 231198090Srdivacky errs() << " " << NoModRef << " no mod/ref responses "; 232193323Sed PrintPercent(NoModRef, ModRefSum); 233198090Srdivacky errs() << " " << Mod << " mod responses "; 234193323Sed PrintPercent(Mod, ModRefSum); 235198090Srdivacky errs() << " " << Ref << " ref responses "; 236193323Sed PrintPercent(Ref, ModRefSum); 237198090Srdivacky errs() << " " << ModRef << " mod & ref responses "; 238193323Sed PrintPercent(ModRef, ModRefSum); 239198090Srdivacky errs() << " Alias Analysis Evaluator Mod/Ref Summary: " 240198090Srdivacky << NoModRef*100/ModRefSum << "%/" << Mod*100/ModRefSum << "%/" 241198090Srdivacky << Ref*100/ModRefSum << "%/" << ModRef*100/ModRefSum << "%\n"; 242193323Sed } 243193323Sed 244193323Sed return false; 245193323Sed} 246