AliasAnalysisEvaluator.cpp revision 68963a47e7b3c2d6474a618a06a7bcaf6bb6d664 
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
19namespace {
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
38bool 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
66bool 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  std::cerr << "  Alias Analysis Evaluator Summary: " << No*100/Sum << "%/"
74            << May*100/Sum << "%/" << Must*100/Sum<<"%\n";
75  return false;
76}
77