AliasAnalysisEvaluator.cpp revision 02896c97ffa5f25f9fb7823607b23935b4e4ed92
1//===- AliasAnalysisEvaluator.cpp - Alias Analysis Accuracy Evaluator -----===// 2// 3// This file implements a simple N^2 alias analysis accuracy evaluator. 4// Basically, for each function in the program, it simply queries to see how the 5// alias analysis implementation answers alias queries between each pair of 6// pointers in the function. 7// 8// This is inspired and adapted from code by: Naveen Neelakantam, Francesco 9// Spadini, and Wojciech Stryjewski. 10// 11//===----------------------------------------------------------------------===// 12 13#include "llvm/Analysis/AliasAnalysis.h" 14#include "llvm/Pass.h" 15#include "llvm/Function.h" 16#include "llvm/Type.h" 17#include "llvm/Support/InstIterator.h" 18#include "llvm/Assembly/Writer.h" 19#include "Support/CommandLine.h" 20 21namespace { 22 cl::opt<bool> PrintNo ("print-no-aliases", cl::ReallyHidden); 23 cl::opt<bool> PrintMay ("print-may-aliases", cl::ReallyHidden); 24 cl::opt<bool> PrintMust("print-must-aliases", cl::ReallyHidden); 25 26 class AAEval : public FunctionPass { 27 unsigned No, May, Must; 28 29 public: 30 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 31 AU.addRequired<AliasAnalysis>(); 32 AU.setPreservesAll(); 33 } 34 35 bool doInitialization(Module &M) { No = May = Must = 0; return false; } 36 bool runOnFunction(Function &F); 37 bool doFinalization(Module &M); 38 }; 39 40 RegisterOpt<AAEval> 41 X("aa-eval", "Exhaustive Alias Analysis Precision Evaluator"); 42} 43 44static inline void PrintResults(const char *Msg, bool P, Value *V1, Value *V2) { 45 if (P) { 46 std::cerr << " " << Msg << ":\t"; 47 WriteAsOperand(std::cerr, V1) << ", "; 48 WriteAsOperand(std::cerr, V2) << "\n"; 49 } 50} 51 52bool AAEval::runOnFunction(Function &F) { 53 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 54 55 std::vector<Value *> Pointers; 56 57 for (Function::aiterator I = F.abegin(), E = F.aend(); I != E; ++I) 58 if (isa<PointerType>(I->getType())) // Add all pointer arguments 59 Pointers.push_back(I); 60 61 for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) 62 if (isa<PointerType>((*I)->getType())) // Add all pointer instructions 63 Pointers.push_back(*I); 64 65 if (PrintNo || PrintMay || PrintMust) 66 std::cerr << "Function: " << F.getName() << "\n"; 67 68 // iterate over the worklist, and run the full (n^2)/2 disambiguations 69 for (std::vector<Value *>::iterator I1 = Pointers.begin(), E = Pointers.end(); 70 I1 != E; ++I1) 71 for (std::vector<Value *>::iterator I2 = Pointers.begin(); I2 != I1; ++I2) 72 switch (AA.alias(*I1, *I2)) { 73 case AliasAnalysis::NoAlias: 74 PrintResults("No", PrintNo, *I1, *I2); 75 ++No; break; 76 case AliasAnalysis::MayAlias: 77 PrintResults("May", PrintMay, *I1, *I2); 78 ++May; break; 79 case AliasAnalysis::MustAlias: 80 PrintResults("Must", PrintMust, *I1, *I2); 81 ++Must; break; 82 default: 83 std::cerr << "Unknown alias query result!\n"; 84 } 85 86 return false; 87} 88 89bool AAEval::doFinalization(Module &M) { 90 unsigned Sum = No+May+Must; 91 std::cerr << "===== Alias Analysis Evaluator Report =====\n"; 92 if (Sum == 0) { 93 std::cerr << " Alias Analysis Evaluator Summary: No pointers!\n"; 94 return false; 95 } 96 97 std::cerr << " " << Sum << " Total Alias Queries Performed\n"; 98 std::cerr << " " << No << " no alias responses (" << No*100/Sum << "%)\n"; 99 std::cerr << " " << May << " may alias responses (" << May*100/Sum << "%)\n"; 100 std::cerr << " " << Must << " must alias responses (" <<Must*100/Sum<<"%)\n"; 101 std::cerr << " Alias Analysis Evaluator Summary: " << No*100/Sum << "%/" 102 << May*100/Sum << "%/" << Must*100/Sum<<"%\n"; 103 return false; 104} 105