lib/Analysis/AliasAnalysisEvaluator.cpp

   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/Support/InstIterator.h"
  17 #include "llvm/Type.h"
  18
  19 namespace {
  20   class AAEval : public FunctionPass {
  21     unsigned No, May, Must;
  22
  23   public:
  24     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  25       AU.addRequired<AliasAnalysis>();
  26       AU.setPreservesAll();
  27     }
  28
  29     bool doInitialization(Module &M) { No = May = Must = 0; return false; }
  30     bool runOnFunction(Function &F);
  31     bool doFinalization(Module &M);
  32   };
  33
  34   RegisterOpt<AAEval>
  35   X("aa-eval", "Exhaustive Alias Analysis Precision Evaluator");
  36 }
  37
  38 bool AAEval::runOnFunction(Function &F) {
  39   AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
  40
  41   std::vector<Value *> Pointers;
  42
  43   for (Function::aiterator I = F.abegin(), E = F.aend(); I != E; ++I)
  44     if (isa<PointerType>(I->getType()))    // Add all pointer arguments
  45       Pointers.push_back(I);
  46
  47   for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
  48     if (isa<PointerType>((*I)->getType())) // Add all pointer instructions
  49       Pointers.push_back(*I);
  50
  51   // iterate over the worklist, and run the full (n^2)/2 disambiguations
  52   for (std::vector<Value *>::iterator I1 = Pointers.begin(), E = Pointers.end();
  53        I1 != E; ++I1)
  54     for (std::vector<Value *>::iterator I2 = Pointers.begin(); I2 != I1; ++I2)
  55       switch (AA.alias(*I1, *I2)) {
  56       case AliasAnalysis::NoAlias:   ++No; break;
  57       case AliasAnalysis::MayAlias:  ++May; break;
  58       case AliasAnalysis::MustAlias: ++Must; break;
  59       default:
  60         std::cerr << "Unknown alias query result!\n";
  61       }
  62
  63   return false;
  64 }
  65
  66 bool AAEval::doFinalization(Module &M) {
  67   unsigned Sum = No+May+Must;
  68   std::cerr << "===== Alias Analysis Evaluator Report =====\n";
  69   std::cerr << "  " << Sum << " Total Alias Queries Performed\n";
  70   std::cerr << "  " << No << " no alias responses (" << No*100/Sum << "%)\n";
  71   std::cerr << "  " << May << " may alias responses (" << May*100/Sum << "%)\n";
  72   std::cerr << "  " << Must << " must alias responses (" <<Must*100/Sum<<"%)\n";
  73   return false;
  74 }