AliasAnalysisEvaluator.cpp revision 1842a90e0bf7b9137fb595828c6e07c5b629b2ad
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#include <set> 21 22namespace { 23 cl::opt<bool> PrintNo ("print-no-aliases", cl::ReallyHidden); 24 cl::opt<bool> PrintMay ("print-may-aliases", cl::ReallyHidden); 25 cl::opt<bool> PrintMust("print-must-aliases", cl::ReallyHidden); 26 27 class AAEval : public FunctionPass { 28 unsigned No, May, Must; 29 30 public: 31 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 32 AU.addRequired<AliasAnalysis>(); 33 AU.setPreservesAll(); 34 } 35 36 bool doInitialization(Module &M) { No = May = Must = 0; return false; } 37 bool runOnFunction(Function &F); 38 bool doFinalization(Module &M); 39 }; 40 41 RegisterOpt<AAEval> 42 X("aa-eval", "Exhaustive Alias Analysis Precision Evaluator"); 43} 44 45static inline void PrintResults(const char *Msg, bool P, Value *V1, Value *V2) { 46 if (P) { 47 std::cerr << " " << Msg << ":\t"; 48 WriteAsOperand(std::cerr, V1) << ", "; 49 WriteAsOperand(std::cerr, V2) << "\n"; 50 } 51} 52 53bool AAEval::runOnFunction(Function &F) { 54 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 55 56 std::set<Value *> Pointers; 57 58 for (Function::aiterator I = F.abegin(), E = F.aend(); I != E; ++I) 59 if (isa<PointerType>(I->getType())) // Add all pointer arguments 60 Pointers.insert(I); 61 62 for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) { 63 if (isa<PointerType>((*I)->getType())) // Add all pointer instructions 64 Pointers.insert(*I); 65 for (User::op_iterator OI = (*I)->op_begin(); OI != (*I)->op_end(); ++OI) 66 if (isa<PointerType>((*OI)->getType())) 67 Pointers.insert(*OI); 68 } 69 70 if (PrintNo || PrintMay || PrintMust) 71 std::cerr << "Function: " << F.getName() << "\n"; 72 73 // iterate over the worklist, and run the full (n^2)/2 disambiguations 74 for (std::set<Value *>::iterator I1 = Pointers.begin(), E = Pointers.end(); 75 I1 != E; ++I1) 76 for (std::set<Value *>::iterator I2 = Pointers.begin(); I2 != I1; ++I2) 77 switch (AA.alias(*I1, 0, *I2, 0)) { 78 case AliasAnalysis::NoAlias: 79 PrintResults("No", PrintNo, *I1, *I2); 80 ++No; break; 81 case AliasAnalysis::MayAlias: 82 PrintResults("May", PrintMay, *I1, *I2); 83 ++May; break; 84 case AliasAnalysis::MustAlias: 85 PrintResults("Must", PrintMust, *I1, *I2); 86 ++Must; break; 87 default: 88 std::cerr << "Unknown alias query result!\n"; 89 } 90 91 return false; 92} 93 94bool AAEval::doFinalization(Module &M) { 95 unsigned Sum = No+May+Must; 96 std::cerr << "===== Alias Analysis Evaluator Report =====\n"; 97 if (Sum == 0) { 98 std::cerr << " Alias Analysis Evaluator Summary: No pointers!\n"; 99 return false; 100 } 101 102 std::cerr << " " << Sum << " Total Alias Queries Performed\n"; 103 std::cerr << " " << No << " no alias responses (" << No*100/Sum << "%)\n"; 104 std::cerr << " " << May << " may alias responses (" << May*100/Sum << "%)\n"; 105 std::cerr << " " << Must << " must alias responses (" <<Must*100/Sum<<"%)\n"; 106 std::cerr << " Alias Analysis Evaluator Summary: " << No*100/Sum << "%/" 107 << May*100/Sum << "%/" << Must*100/Sum<<"%\n"; 108 return false; 109} 110