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/Analysis/Passes.h" 21252723Sdim#include "llvm/ADT/SetVector.h" 22193323Sed#include "llvm/Analysis/AliasAnalysis.h" 23193323Sed#include "llvm/Assembly/Writer.h" 24252723Sdim#include "llvm/IR/Constants.h" 25252723Sdim#include "llvm/IR/DerivedTypes.h" 26252723Sdim#include "llvm/IR/Function.h" 27252723Sdim#include "llvm/IR/Instructions.h" 28252723Sdim#include "llvm/Pass.h" 29252723Sdim#include "llvm/Support/CommandLine.h" 30201360Srdivacky#include "llvm/Support/Debug.h" 31193323Sed#include "llvm/Support/InstIterator.h" 32198090Srdivacky#include "llvm/Support/raw_ostream.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); 39218893Sdimstatic cl::opt<bool> PrintPartialAlias("print-partial-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 47252723Sdimstatic cl::opt<bool> EvalTBAA("evaluate-tbaa", cl::ReallyHidden); 48252723Sdim 49193323Sednamespace { 50198892Srdivacky class AAEval : public FunctionPass { 51218893Sdim unsigned NoAlias, MayAlias, PartialAlias, MustAlias; 52193323Sed unsigned NoModRef, Mod, Ref, ModRef; 53193323Sed 54193323Sed public: 55193323Sed static char ID; // Pass identification, replacement for typeid 56218893Sdim AAEval() : FunctionPass(ID) { 57218893Sdim initializeAAEvalPass(*PassRegistry::getPassRegistry()); 58218893Sdim } 59193323Sed 60193323Sed virtual void getAnalysisUsage(AnalysisUsage &AU) const { 61193323Sed AU.addRequired<AliasAnalysis>(); 62193323Sed AU.setPreservesAll(); 63193323Sed } 64193323Sed 65193323Sed bool doInitialization(Module &M) { 66218893Sdim NoAlias = MayAlias = PartialAlias = MustAlias = 0; 67193323Sed NoModRef = Mod = Ref = ModRef = 0; 68193323Sed 69193323Sed if (PrintAll) { 70218893Sdim PrintNoAlias = PrintMayAlias = true; 71218893Sdim PrintPartialAlias = PrintMustAlias = true; 72193323Sed PrintNoModRef = PrintMod = PrintRef = PrintModRef = true; 73193323Sed } 74193323Sed return false; 75193323Sed } 76193323Sed 77193323Sed bool runOnFunction(Function &F); 78193323Sed bool doFinalization(Module &M); 79193323Sed }; 80193323Sed} 81193323Sed 82193323Sedchar AAEval::ID = 0; 83218893SdimINITIALIZE_PASS_BEGIN(AAEval, "aa-eval", 84218893Sdim "Exhaustive Alias Analysis Precision Evaluator", false, true) 85218893SdimINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 86218893SdimINITIALIZE_PASS_END(AAEval, "aa-eval", 87218893Sdim "Exhaustive Alias Analysis Precision Evaluator", false, true) 88193323Sed 89193323SedFunctionPass *llvm::createAAEvalPass() { return new AAEval(); } 90193323Sed 91198090Srdivackystatic void PrintResults(const char *Msg, bool P, const Value *V1, 92198090Srdivacky const Value *V2, const Module *M) { 93193323Sed if (P) { 94198090Srdivacky std::string o1, o2; 95198090Srdivacky { 96198090Srdivacky raw_string_ostream os1(o1), os2(o2); 97198090Srdivacky WriteAsOperand(os1, V1, true, M); 98198090Srdivacky WriteAsOperand(os2, V2, true, M); 99198090Srdivacky } 100198090Srdivacky 101193323Sed if (o2 < o1) 102198090Srdivacky std::swap(o1, o2); 103198090Srdivacky errs() << " " << Msg << ":\t" 104198090Srdivacky << o1 << ", " 105198090Srdivacky << o2 << "\n"; 106193323Sed } 107193323Sed} 108193323Sed 109193323Sedstatic inline void 110193323SedPrintModRefResults(const char *Msg, bool P, Instruction *I, Value *Ptr, 111193323Sed Module *M) { 112193323Sed if (P) { 113198090Srdivacky errs() << " " << Msg << ": Ptr: "; 114198090Srdivacky WriteAsOperand(errs(), Ptr, true, M); 115198090Srdivacky errs() << "\t<->" << *I << '\n'; 116193323Sed } 117193323Sed} 118193323Sed 119212904Sdimstatic inline void 120212904SdimPrintModRefResults(const char *Msg, bool P, CallSite CSA, CallSite CSB, 121212904Sdim Module *M) { 122212904Sdim if (P) { 123212904Sdim errs() << " " << Msg << ": " << *CSA.getInstruction() 124212904Sdim << " <-> " << *CSB.getInstruction() << '\n'; 125212904Sdim } 126212904Sdim} 127212904Sdim 128252723Sdimstatic inline void 129252723SdimPrintLoadStoreResults(const char *Msg, bool P, const Value *V1, 130252723Sdim const Value *V2, const Module *M) { 131252723Sdim if (P) { 132252723Sdim errs() << " " << Msg << ": " << *V1 133252723Sdim << " <-> " << *V2 << '\n'; 134252723Sdim } 135252723Sdim} 136252723Sdim 137207618Srdivackystatic inline bool isInterestingPointer(Value *V) { 138207618Srdivacky return V->getType()->isPointerTy() 139207618Srdivacky && !isa<ConstantPointerNull>(V); 140207618Srdivacky} 141207618Srdivacky 142193323Sedbool AAEval::runOnFunction(Function &F) { 143193323Sed AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 144193323Sed 145198090Srdivacky SetVector<Value *> Pointers; 146198090Srdivacky SetVector<CallSite> CallSites; 147252723Sdim SetVector<Value *> Loads; 148252723Sdim SetVector<Value *> Stores; 149193323Sed 150193323Sed for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) 151207618Srdivacky if (I->getType()->isPointerTy()) // Add all pointer arguments. 152193323Sed Pointers.insert(I); 153193323Sed 154193323Sed for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) { 155207618Srdivacky if (I->getType()->isPointerTy()) // Add all pointer instructions. 156193323Sed Pointers.insert(&*I); 157252723Sdim if (EvalTBAA && isa<LoadInst>(&*I)) 158252723Sdim Loads.insert(&*I); 159252723Sdim if (EvalTBAA && isa<StoreInst>(&*I)) 160252723Sdim Stores.insert(&*I); 161193323Sed Instruction &Inst = *I; 162212904Sdim if (CallSite CS = cast<Value>(&Inst)) { 163207618Srdivacky Value *Callee = CS.getCalledValue(); 164207618Srdivacky // Skip actual functions for direct function calls. 165207618Srdivacky if (!isa<Function>(Callee) && isInterestingPointer(Callee)) 166207618Srdivacky Pointers.insert(Callee); 167207618Srdivacky // Consider formals. 168207618Srdivacky for (CallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end(); 169207618Srdivacky AI != AE; ++AI) 170207618Srdivacky if (isInterestingPointer(*AI)) 171207618Srdivacky Pointers.insert(*AI); 172212904Sdim CallSites.insert(CS); 173207618Srdivacky } else { 174207618Srdivacky // Consider all operands. 175207618Srdivacky for (Instruction::op_iterator OI = Inst.op_begin(), OE = Inst.op_end(); 176207618Srdivacky OI != OE; ++OI) 177207618Srdivacky if (isInterestingPointer(*OI)) 178207618Srdivacky Pointers.insert(*OI); 179207618Srdivacky } 180193323Sed } 181193323Sed 182218893Sdim if (PrintNoAlias || PrintMayAlias || PrintPartialAlias || PrintMustAlias || 183193323Sed PrintNoModRef || PrintMod || PrintRef || PrintModRef) 184198090Srdivacky errs() << "Function: " << F.getName() << ": " << Pointers.size() 185198090Srdivacky << " pointers, " << CallSites.size() << " call sites\n"; 186193323Sed 187193323Sed // iterate over the worklist, and run the full (n^2)/2 disambiguations 188198090Srdivacky for (SetVector<Value *>::iterator I1 = Pointers.begin(), E = Pointers.end(); 189193323Sed I1 != E; ++I1) { 190218893Sdim uint64_t I1Size = AliasAnalysis::UnknownSize; 191226890Sdim Type *I1ElTy = cast<PointerType>((*I1)->getType())->getElementType(); 192198090Srdivacky if (I1ElTy->isSized()) I1Size = AA.getTypeStoreSize(I1ElTy); 193193323Sed 194198090Srdivacky for (SetVector<Value *>::iterator I2 = Pointers.begin(); I2 != I1; ++I2) { 195218893Sdim uint64_t I2Size = AliasAnalysis::UnknownSize; 196226890Sdim Type *I2ElTy =cast<PointerType>((*I2)->getType())->getElementType(); 197198090Srdivacky if (I2ElTy->isSized()) I2Size = AA.getTypeStoreSize(I2ElTy); 198193323Sed 199193323Sed switch (AA.alias(*I1, I1Size, *I2, I2Size)) { 200193323Sed case AliasAnalysis::NoAlias: 201193323Sed PrintResults("NoAlias", PrintNoAlias, *I1, *I2, F.getParent()); 202193323Sed ++NoAlias; break; 203193323Sed case AliasAnalysis::MayAlias: 204193323Sed PrintResults("MayAlias", PrintMayAlias, *I1, *I2, F.getParent()); 205193323Sed ++MayAlias; break; 206218893Sdim case AliasAnalysis::PartialAlias: 207218893Sdim PrintResults("PartialAlias", PrintPartialAlias, *I1, *I2, 208218893Sdim F.getParent()); 209218893Sdim ++PartialAlias; break; 210193323Sed case AliasAnalysis::MustAlias: 211193323Sed PrintResults("MustAlias", PrintMustAlias, *I1, *I2, F.getParent()); 212193323Sed ++MustAlias; break; 213193323Sed } 214193323Sed } 215193323Sed } 216193323Sed 217252723Sdim if (EvalTBAA) { 218252723Sdim // iterate over all pairs of load, store 219252723Sdim for (SetVector<Value *>::iterator I1 = Loads.begin(), E = Loads.end(); 220252723Sdim I1 != E; ++I1) { 221252723Sdim for (SetVector<Value *>::iterator I2 = Stores.begin(), E2 = Stores.end(); 222252723Sdim I2 != E2; ++I2) { 223252723Sdim switch (AA.alias(AA.getLocation(cast<LoadInst>(*I1)), 224252723Sdim AA.getLocation(cast<StoreInst>(*I2)))) { 225252723Sdim case AliasAnalysis::NoAlias: 226252723Sdim PrintLoadStoreResults("NoAlias", PrintNoAlias, *I1, *I2, 227252723Sdim F.getParent()); 228252723Sdim ++NoAlias; break; 229252723Sdim case AliasAnalysis::MayAlias: 230252723Sdim PrintLoadStoreResults("MayAlias", PrintMayAlias, *I1, *I2, 231252723Sdim F.getParent()); 232252723Sdim ++MayAlias; break; 233252723Sdim case AliasAnalysis::PartialAlias: 234252723Sdim PrintLoadStoreResults("PartialAlias", PrintPartialAlias, *I1, *I2, 235252723Sdim F.getParent()); 236252723Sdim ++PartialAlias; break; 237252723Sdim case AliasAnalysis::MustAlias: 238252723Sdim PrintLoadStoreResults("MustAlias", PrintMustAlias, *I1, *I2, 239252723Sdim F.getParent()); 240252723Sdim ++MustAlias; break; 241252723Sdim } 242252723Sdim } 243252723Sdim } 244252723Sdim 245252723Sdim // iterate over all pairs of store, store 246252723Sdim for (SetVector<Value *>::iterator I1 = Stores.begin(), E = Stores.end(); 247252723Sdim I1 != E; ++I1) { 248252723Sdim for (SetVector<Value *>::iterator I2 = Stores.begin(); I2 != I1; ++I2) { 249252723Sdim switch (AA.alias(AA.getLocation(cast<StoreInst>(*I1)), 250252723Sdim AA.getLocation(cast<StoreInst>(*I2)))) { 251252723Sdim case AliasAnalysis::NoAlias: 252252723Sdim PrintLoadStoreResults("NoAlias", PrintNoAlias, *I1, *I2, 253252723Sdim F.getParent()); 254252723Sdim ++NoAlias; break; 255252723Sdim case AliasAnalysis::MayAlias: 256252723Sdim PrintLoadStoreResults("MayAlias", PrintMayAlias, *I1, *I2, 257252723Sdim F.getParent()); 258252723Sdim ++MayAlias; break; 259252723Sdim case AliasAnalysis::PartialAlias: 260252723Sdim PrintLoadStoreResults("PartialAlias", PrintPartialAlias, *I1, *I2, 261252723Sdim F.getParent()); 262252723Sdim ++PartialAlias; break; 263252723Sdim case AliasAnalysis::MustAlias: 264252723Sdim PrintLoadStoreResults("MustAlias", PrintMustAlias, *I1, *I2, 265252723Sdim F.getParent()); 266252723Sdim ++MustAlias; break; 267252723Sdim } 268252723Sdim } 269252723Sdim } 270252723Sdim } 271252723Sdim 272193323Sed // Mod/ref alias analysis: compare all pairs of calls and values 273198090Srdivacky for (SetVector<CallSite>::iterator C = CallSites.begin(), 274193323Sed Ce = CallSites.end(); C != Ce; ++C) { 275193323Sed Instruction *I = C->getInstruction(); 276193323Sed 277198090Srdivacky for (SetVector<Value *>::iterator V = Pointers.begin(), Ve = Pointers.end(); 278193323Sed V != Ve; ++V) { 279218893Sdim uint64_t Size = AliasAnalysis::UnknownSize; 280226890Sdim Type *ElTy = cast<PointerType>((*V)->getType())->getElementType(); 281198090Srdivacky if (ElTy->isSized()) Size = AA.getTypeStoreSize(ElTy); 282193323Sed 283193323Sed switch (AA.getModRefInfo(*C, *V, Size)) { 284193323Sed case AliasAnalysis::NoModRef: 285193323Sed PrintModRefResults("NoModRef", PrintNoModRef, I, *V, F.getParent()); 286193323Sed ++NoModRef; break; 287193323Sed case AliasAnalysis::Mod: 288212904Sdim PrintModRefResults("Just Mod", PrintMod, I, *V, F.getParent()); 289193323Sed ++Mod; break; 290193323Sed case AliasAnalysis::Ref: 291212904Sdim PrintModRefResults("Just Ref", PrintRef, I, *V, F.getParent()); 292193323Sed ++Ref; break; 293193323Sed case AliasAnalysis::ModRef: 294212904Sdim PrintModRefResults("Both ModRef", PrintModRef, I, *V, F.getParent()); 295193323Sed ++ModRef; break; 296193323Sed } 297193323Sed } 298193323Sed } 299193323Sed 300212904Sdim // Mod/ref alias analysis: compare all pairs of calls 301212904Sdim for (SetVector<CallSite>::iterator C = CallSites.begin(), 302212904Sdim Ce = CallSites.end(); C != Ce; ++C) { 303212904Sdim for (SetVector<CallSite>::iterator D = CallSites.begin(); D != Ce; ++D) { 304212904Sdim if (D == C) 305212904Sdim continue; 306212904Sdim switch (AA.getModRefInfo(*C, *D)) { 307212904Sdim case AliasAnalysis::NoModRef: 308212904Sdim PrintModRefResults("NoModRef", PrintNoModRef, *C, *D, F.getParent()); 309212904Sdim ++NoModRef; break; 310212904Sdim case AliasAnalysis::Mod: 311212904Sdim PrintModRefResults("Just Mod", PrintMod, *C, *D, F.getParent()); 312212904Sdim ++Mod; break; 313212904Sdim case AliasAnalysis::Ref: 314212904Sdim PrintModRefResults("Just Ref", PrintRef, *C, *D, F.getParent()); 315212904Sdim ++Ref; break; 316212904Sdim case AliasAnalysis::ModRef: 317212904Sdim PrintModRefResults("Both ModRef", PrintModRef, *C, *D, F.getParent()); 318212904Sdim ++ModRef; break; 319212904Sdim } 320212904Sdim } 321212904Sdim } 322212904Sdim 323193323Sed return false; 324193323Sed} 325193323Sed 326193323Sedstatic void PrintPercent(unsigned Num, unsigned Sum) { 327198090Srdivacky errs() << "(" << Num*100ULL/Sum << "." 328198090Srdivacky << ((Num*1000ULL/Sum) % 10) << "%)\n"; 329193323Sed} 330193323Sed 331193323Sedbool AAEval::doFinalization(Module &M) { 332218893Sdim unsigned AliasSum = NoAlias + MayAlias + PartialAlias + MustAlias; 333198090Srdivacky errs() << "===== Alias Analysis Evaluator Report =====\n"; 334193323Sed if (AliasSum == 0) { 335198090Srdivacky errs() << " Alias Analysis Evaluator Summary: No pointers!\n"; 336193323Sed } else { 337198090Srdivacky errs() << " " << AliasSum << " Total Alias Queries Performed\n"; 338198090Srdivacky errs() << " " << NoAlias << " no alias responses "; 339193323Sed PrintPercent(NoAlias, AliasSum); 340198090Srdivacky errs() << " " << MayAlias << " may alias responses "; 341193323Sed PrintPercent(MayAlias, AliasSum); 342218893Sdim errs() << " " << PartialAlias << " partial alias responses "; 343218893Sdim PrintPercent(PartialAlias, AliasSum); 344198090Srdivacky errs() << " " << MustAlias << " must alias responses "; 345193323Sed PrintPercent(MustAlias, AliasSum); 346198090Srdivacky errs() << " Alias Analysis Evaluator Pointer Alias Summary: " 347198090Srdivacky << NoAlias*100/AliasSum << "%/" << MayAlias*100/AliasSum << "%/" 348218893Sdim << PartialAlias*100/AliasSum << "%/" 349198090Srdivacky << MustAlias*100/AliasSum << "%\n"; 350193323Sed } 351193323Sed 352193323Sed // Display the summary for mod/ref analysis 353193323Sed unsigned ModRefSum = NoModRef + Mod + Ref + ModRef; 354193323Sed if (ModRefSum == 0) { 355198090Srdivacky errs() << " Alias Analysis Mod/Ref Evaluator Summary: no mod/ref!\n"; 356193323Sed } else { 357198090Srdivacky errs() << " " << ModRefSum << " Total ModRef Queries Performed\n"; 358198090Srdivacky errs() << " " << NoModRef << " no mod/ref responses "; 359193323Sed PrintPercent(NoModRef, ModRefSum); 360198090Srdivacky errs() << " " << Mod << " mod responses "; 361193323Sed PrintPercent(Mod, ModRefSum); 362198090Srdivacky errs() << " " << Ref << " ref responses "; 363193323Sed PrintPercent(Ref, ModRefSum); 364198090Srdivacky errs() << " " << ModRef << " mod & ref responses "; 365193323Sed PrintPercent(ModRef, ModRefSum); 366198090Srdivacky errs() << " Alias Analysis Evaluator Mod/Ref Summary: " 367198090Srdivacky << NoModRef*100/ModRefSum << "%/" << Mod*100/ModRefSum << "%/" 368198090Srdivacky << Ref*100/ModRefSum << "%/" << ModRef*100/ModRefSum << "%\n"; 369193323Sed } 370193323Sed 371193323Sed return false; 372193323Sed} 373