AliasAnalysisEvaluator.cpp revision 360784 
1//===- AliasAnalysisEvaluator.cpp - Alias Analysis Accuracy Evaluator -----===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "llvm/Analysis/AliasAnalysisEvaluator.h"
10#include "llvm/ADT/SetVector.h"
11#include "llvm/Analysis/AliasAnalysis.h"
12#include "llvm/IR/Constants.h"
13#include "llvm/IR/DataLayout.h"
14#include "llvm/IR/DerivedTypes.h"
15#include "llvm/IR/Function.h"
16#include "llvm/IR/InstIterator.h"
17#include "llvm/IR/Instructions.h"
18#include "llvm/IR/Module.h"
19#include "llvm/InitializePasses.h"
20#include "llvm/Pass.h"
21#include "llvm/Support/CommandLine.h"
22#include "llvm/Support/Debug.h"
23#include "llvm/Support/raw_ostream.h"
24using namespace llvm;
25
26static cl::opt<bool> PrintAll("print-all-alias-modref-info", cl::ReallyHidden);
27
28static cl::opt<bool> PrintNoAlias("print-no-aliases", cl::ReallyHidden);
29static cl::opt<bool> PrintMayAlias("print-may-aliases", cl::ReallyHidden);
30static cl::opt<bool> PrintPartialAlias("print-partial-aliases", cl::ReallyHidden);
31static cl::opt<bool> PrintMustAlias("print-must-aliases", cl::ReallyHidden);
32
33static cl::opt<bool> PrintNoModRef("print-no-modref", cl::ReallyHidden);
34static cl::opt<bool> PrintRef("print-ref", cl::ReallyHidden);
35static cl::opt<bool> PrintMod("print-mod", cl::ReallyHidden);
36static cl::opt<bool> PrintModRef("print-modref", cl::ReallyHidden);
37static cl::opt<bool> PrintMust("print-must", cl::ReallyHidden);
38static cl::opt<bool> PrintMustRef("print-mustref", cl::ReallyHidden);
39static cl::opt<bool> PrintMustMod("print-mustmod", cl::ReallyHidden);
40static cl::opt<bool> PrintMustModRef("print-mustmodref", cl::ReallyHidden);
41
42static cl::opt<bool> EvalAAMD("evaluate-aa-metadata", cl::ReallyHidden);
43
44static void PrintResults(AliasResult AR, bool P, const Value *V1,
45                         const Value *V2, const Module *M) {
46  if (PrintAll || P) {
47    std::string o1, o2;
48    {
49      raw_string_ostream os1(o1), os2(o2);
50      V1->printAsOperand(os1, true, M);
51      V2->printAsOperand(os2, true, M);
52    }
53
54    if (o2 < o1)
55      std::swap(o1, o2);
56    errs() << "  " << AR << ":\t" << o1 << ", " << o2 << "\n";
57  }
58}
59
60static inline void PrintModRefResults(const char *Msg, bool P, Instruction *I,
61                                      Value *Ptr, Module *M) {
62  if (PrintAll || P) {
63    errs() << "  " << Msg << ":  Ptr: ";
64    Ptr->printAsOperand(errs(), true, M);
65    errs() << "\t<->" << *I << '\n';
66  }
67}
68
69static inline void PrintModRefResults(const char *Msg, bool P, CallBase *CallA,
70                                      CallBase *CallB, Module *M) {
71  if (PrintAll || P) {
72    errs() << "  " << Msg << ": " << *CallA << " <-> " << *CallB << '\n';
73  }
74}
75
76static inline void PrintLoadStoreResults(AliasResult AR, bool P,
77                                         const Value *V1, const Value *V2,
78                                         const Module *M) {
79  if (PrintAll || P) {
80    errs() << "  " << AR << ": " << *V1 << " <-> " << *V2 << '\n';
81  }
82}
83
84static inline bool isInterestingPointer(Value *V) {
85  return V->getType()->isPointerTy()
86      && !isa<ConstantPointerNull>(V);
87}
88
89PreservedAnalyses AAEvaluator::run(Function &F, FunctionAnalysisManager &AM) {
90  runInternal(F, AM.getResult<AAManager>(F));
91  return PreservedAnalyses::all();
92}
93
94void AAEvaluator::runInternal(Function &F, AAResults &AA) {
95  const DataLayout &DL = F.getParent()->getDataLayout();
96
97  ++FunctionCount;
98
99  SetVector<Value *> Pointers;
100  SmallSetVector<CallBase *, 16> Calls;
101  SetVector<Value *> Loads;
102  SetVector<Value *> Stores;
103
104  for (auto &I : F.args())
105    if (I.getType()->isPointerTy())    // Add all pointer arguments.
106      Pointers.insert(&I);
107
108  for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
109    if (I->getType()->isPointerTy()) // Add all pointer instructions.
110      Pointers.insert(&*I);
111    if (EvalAAMD && isa<LoadInst>(&*I))
112      Loads.insert(&*I);
113    if (EvalAAMD && isa<StoreInst>(&*I))
114      Stores.insert(&*I);
115    Instruction &Inst = *I;
116    if (auto *Call = dyn_cast<CallBase>(&Inst)) {
117      Value *Callee = Call->getCalledValue();
118      // Skip actual functions for direct function calls.
119      if (!isa<Function>(Callee) && isInterestingPointer(Callee))
120        Pointers.insert(Callee);
121      // Consider formals.
122      for (Use &DataOp : Call->data_ops())
123        if (isInterestingPointer(DataOp))
124          Pointers.insert(DataOp);
125      Calls.insert(Call);
126    } else {
127      // Consider all operands.
128      for (Instruction::op_iterator OI = Inst.op_begin(), OE = Inst.op_end();
129           OI != OE; ++OI)
130        if (isInterestingPointer(*OI))
131          Pointers.insert(*OI);
132    }
133  }
134
135  if (PrintAll || PrintNoAlias || PrintMayAlias || PrintPartialAlias ||
136      PrintMustAlias || PrintNoModRef || PrintMod || PrintRef || PrintModRef)
137    errs() << "Function: " << F.getName() << ": " << Pointers.size()
138           << " pointers, " << Calls.size() << " call sites\n";
139
140  // iterate over the worklist, and run the full (n^2)/2 disambiguations
141  for (SetVector<Value *>::iterator I1 = Pointers.begin(), E = Pointers.end();
142       I1 != E; ++I1) {
143    auto I1Size = LocationSize::unknown();
144    Type *I1ElTy = cast<PointerType>((*I1)->getType())->getElementType();
145    if (I1ElTy->isSized())
146      I1Size = LocationSize::precise(DL.getTypeStoreSize(I1ElTy));
147
148    for (SetVector<Value *>::iterator I2 = Pointers.begin(); I2 != I1; ++I2) {
149      auto I2Size = LocationSize::unknown();
150      Type *I2ElTy = cast<PointerType>((*I2)->getType())->getElementType();
151      if (I2ElTy->isSized())
152        I2Size = LocationSize::precise(DL.getTypeStoreSize(I2ElTy));
153
154      AliasResult AR = AA.alias(*I1, I1Size, *I2, I2Size);
155      switch (AR) {
156      case NoAlias:
157        PrintResults(AR, PrintNoAlias, *I1, *I2, F.getParent());
158        ++NoAliasCount;
159        break;
160      case MayAlias:
161        PrintResults(AR, PrintMayAlias, *I1, *I2, F.getParent());
162        ++MayAliasCount;
163        break;
164      case PartialAlias:
165        PrintResults(AR, PrintPartialAlias, *I1, *I2, F.getParent());
166        ++PartialAliasCount;
167        break;
168      case MustAlias:
169        PrintResults(AR, PrintMustAlias, *I1, *I2, F.getParent());
170        ++MustAliasCount;
171        break;
172      }
173    }
174  }
175
176  if (EvalAAMD) {
177    // iterate over all pairs of load, store
178    for (Value *Load : Loads) {
179      for (Value *Store : Stores) {
180        AliasResult AR = AA.alias(MemoryLocation::get(cast<LoadInst>(Load)),
181                                  MemoryLocation::get(cast<StoreInst>(Store)));
182        switch (AR) {
183        case NoAlias:
184          PrintLoadStoreResults(AR, PrintNoAlias, Load, Store, F.getParent());
185          ++NoAliasCount;
186          break;
187        case MayAlias:
188          PrintLoadStoreResults(AR, PrintMayAlias, Load, Store, F.getParent());
189          ++MayAliasCount;
190          break;
191        case PartialAlias:
192          PrintLoadStoreResults(AR, PrintPartialAlias, Load, Store, F.getParent());
193          ++PartialAliasCount;
194          break;
195        case MustAlias:
196          PrintLoadStoreResults(AR, PrintMustAlias, Load, Store, F.getParent());
197          ++MustAliasCount;
198          break;
199        }
200      }
201    }
202
203    // iterate over all pairs of store, store
204    for (SetVector<Value *>::iterator I1 = Stores.begin(), E = Stores.end();
205         I1 != E; ++I1) {
206      for (SetVector<Value *>::iterator I2 = Stores.begin(); I2 != I1; ++I2) {
207        AliasResult AR = AA.alias(MemoryLocation::get(cast<StoreInst>(*I1)),
208                                  MemoryLocation::get(cast<StoreInst>(*I2)));
209        switch (AR) {
210        case NoAlias:
211          PrintLoadStoreResults(AR, PrintNoAlias, *I1, *I2, F.getParent());
212          ++NoAliasCount;
213          break;
214        case MayAlias:
215          PrintLoadStoreResults(AR, PrintMayAlias, *I1, *I2, F.getParent());
216          ++MayAliasCount;
217          break;
218        case PartialAlias:
219          PrintLoadStoreResults(AR, PrintPartialAlias, *I1, *I2, F.getParent());
220          ++PartialAliasCount;
221          break;
222        case MustAlias:
223          PrintLoadStoreResults(AR, PrintMustAlias, *I1, *I2, F.getParent());
224          ++MustAliasCount;
225          break;
226        }
227      }
228    }
229  }
230
231  // Mod/ref alias analysis: compare all pairs of calls and values
232  for (CallBase *Call : Calls) {
233    for (auto Pointer : Pointers) {
234      auto Size = LocationSize::unknown();
235      Type *ElTy = cast<PointerType>(Pointer->getType())->getElementType();
236      if (ElTy->isSized())
237        Size = LocationSize::precise(DL.getTypeStoreSize(ElTy));
238
239      switch (AA.getModRefInfo(Call, Pointer, Size)) {
240      case ModRefInfo::NoModRef:
241        PrintModRefResults("NoModRef", PrintNoModRef, Call, Pointer,
242                           F.getParent());
243        ++NoModRefCount;
244        break;
245      case ModRefInfo::Mod:
246        PrintModRefResults("Just Mod", PrintMod, Call, Pointer, F.getParent());
247        ++ModCount;
248        break;
249      case ModRefInfo::Ref:
250        PrintModRefResults("Just Ref", PrintRef, Call, Pointer, F.getParent());
251        ++RefCount;
252        break;
253      case ModRefInfo::ModRef:
254        PrintModRefResults("Both ModRef", PrintModRef, Call, Pointer,
255                           F.getParent());
256        ++ModRefCount;
257        break;
258      case ModRefInfo::Must:
259        PrintModRefResults("Must", PrintMust, Call, Pointer, F.getParent());
260        ++MustCount;
261        break;
262      case ModRefInfo::MustMod:
263        PrintModRefResults("Just Mod (MustAlias)", PrintMustMod, Call, Pointer,
264                           F.getParent());
265        ++MustModCount;
266        break;
267      case ModRefInfo::MustRef:
268        PrintModRefResults("Just Ref (MustAlias)", PrintMustRef, Call, Pointer,
269                           F.getParent());
270        ++MustRefCount;
271        break;
272      case ModRefInfo::MustModRef:
273        PrintModRefResults("Both ModRef (MustAlias)", PrintMustModRef, Call,
274                           Pointer, F.getParent());
275        ++MustModRefCount;
276        break;
277      }
278    }
279  }
280
281  // Mod/ref alias analysis: compare all pairs of calls
282  for (CallBase *CallA : Calls) {
283    for (CallBase *CallB : Calls) {
284      if (CallA == CallB)
285        continue;
286      switch (AA.getModRefInfo(CallA, CallB)) {
287      case ModRefInfo::NoModRef:
288        PrintModRefResults("NoModRef", PrintNoModRef, CallA, CallB,
289                           F.getParent());
290        ++NoModRefCount;
291        break;
292      case ModRefInfo::Mod:
293        PrintModRefResults("Just Mod", PrintMod, CallA, CallB, F.getParent());
294        ++ModCount;
295        break;
296      case ModRefInfo::Ref:
297        PrintModRefResults("Just Ref", PrintRef, CallA, CallB, F.getParent());
298        ++RefCount;
299        break;
300      case ModRefInfo::ModRef:
301        PrintModRefResults("Both ModRef", PrintModRef, CallA, CallB,
302                           F.getParent());
303        ++ModRefCount;
304        break;
305      case ModRefInfo::Must:
306        PrintModRefResults("Must", PrintMust, CallA, CallB, F.getParent());
307        ++MustCount;
308        break;
309      case ModRefInfo::MustMod:
310        PrintModRefResults("Just Mod (MustAlias)", PrintMustMod, CallA, CallB,
311                           F.getParent());
312        ++MustModCount;
313        break;
314      case ModRefInfo::MustRef:
315        PrintModRefResults("Just Ref (MustAlias)", PrintMustRef, CallA, CallB,
316                           F.getParent());
317        ++MustRefCount;
318        break;
319      case ModRefInfo::MustModRef:
320        PrintModRefResults("Both ModRef (MustAlias)", PrintMustModRef, CallA,
321                           CallB, F.getParent());
322        ++MustModRefCount;
323        break;
324      }
325    }
326  }
327}
328
329static void PrintPercent(int64_t Num, int64_t Sum) {
330  errs() << "(" << Num * 100LL / Sum << "." << ((Num * 1000LL / Sum) % 10)
331         << "%)\n";
332}
333
334AAEvaluator::~AAEvaluator() {
335  if (FunctionCount == 0)
336    return;
337
338  int64_t AliasSum =
339      NoAliasCount + MayAliasCount + PartialAliasCount + MustAliasCount;
340  errs() << "===== Alias Analysis Evaluator Report =====\n";
341  if (AliasSum == 0) {
342    errs() << "  Alias Analysis Evaluator Summary: No pointers!\n";
343  } else {
344    errs() << "  " << AliasSum << " Total Alias Queries Performed\n";
345    errs() << "  " << NoAliasCount << " no alias responses ";
346    PrintPercent(NoAliasCount, AliasSum);
347    errs() << "  " << MayAliasCount << " may alias responses ";
348    PrintPercent(MayAliasCount, AliasSum);
349    errs() << "  " << PartialAliasCount << " partial alias responses ";
350    PrintPercent(PartialAliasCount, AliasSum);
351    errs() << "  " << MustAliasCount << " must alias responses ";
352    PrintPercent(MustAliasCount, AliasSum);
353    errs() << "  Alias Analysis Evaluator Pointer Alias Summary: "
354           << NoAliasCount * 100 / AliasSum << "%/"
355           << MayAliasCount * 100 / AliasSum << "%/"
356           << PartialAliasCount * 100 / AliasSum << "%/"
357           << MustAliasCount * 100 / AliasSum << "%\n";
358  }
359
360  // Display the summary for mod/ref analysis
361  int64_t ModRefSum = NoModRefCount + RefCount + ModCount + ModRefCount +
362                      MustCount + MustRefCount + MustModCount + MustModRefCount;
363  if (ModRefSum == 0) {
364    errs() << "  Alias Analysis Mod/Ref Evaluator Summary: no "
365              "mod/ref!\n";
366  } else {
367    errs() << "  " << ModRefSum << " Total ModRef Queries Performed\n";
368    errs() << "  " << NoModRefCount << " no mod/ref responses ";
369    PrintPercent(NoModRefCount, ModRefSum);
370    errs() << "  " << ModCount << " mod responses ";
371    PrintPercent(ModCount, ModRefSum);
372    errs() << "  " << RefCount << " ref responses ";
373    PrintPercent(RefCount, ModRefSum);
374    errs() << "  " << ModRefCount << " mod & ref responses ";
375    PrintPercent(ModRefCount, ModRefSum);
376    errs() << "  " << MustCount << " must responses ";
377    PrintPercent(MustCount, ModRefSum);
378    errs() << "  " << MustModCount << " must mod responses ";
379    PrintPercent(MustModCount, ModRefSum);
380    errs() << "  " << MustRefCount << " must ref responses ";
381    PrintPercent(MustRefCount, ModRefSum);
382    errs() << "  " << MustModRefCount << " must mod & ref responses ";
383    PrintPercent(MustModRefCount, ModRefSum);
384    errs() << "  Alias Analysis Evaluator Mod/Ref Summary: "
385           << NoModRefCount * 100 / ModRefSum << "%/"
386           << ModCount * 100 / ModRefSum << "%/" << RefCount * 100 / ModRefSum
387           << "%/" << ModRefCount * 100 / ModRefSum << "%/"
388           << MustCount * 100 / ModRefSum << "%/"
389           << MustRefCount * 100 / ModRefSum << "%/"
390           << MustModCount * 100 / ModRefSum << "%/"
391           << MustModRefCount * 100 / ModRefSum << "%\n";
392  }
393}
394
395namespace llvm {
396class AAEvalLegacyPass : public FunctionPass {
397  std::unique_ptr<AAEvaluator> P;
398
399public:
400  static char ID; // Pass identification, replacement for typeid
401  AAEvalLegacyPass() : FunctionPass(ID) {
402    initializeAAEvalLegacyPassPass(*PassRegistry::getPassRegistry());
403  }
404
405  void getAnalysisUsage(AnalysisUsage &AU) const override {
406    AU.addRequired<AAResultsWrapperPass>();
407    AU.setPreservesAll();
408  }
409
410  bool doInitialization(Module &M) override {
411    P.reset(new AAEvaluator());
412    return false;
413  }
414
415  bool runOnFunction(Function &F) override {
416    P->runInternal(F, getAnalysis<AAResultsWrapperPass>().getAAResults());
417    return false;
418  }
419  bool doFinalization(Module &M) override {
420    P.reset();
421    return false;
422  }
423};
424}
425
426char AAEvalLegacyPass::ID = 0;
427INITIALIZE_PASS_BEGIN(AAEvalLegacyPass, "aa-eval",
428                      "Exhaustive Alias Analysis Precision Evaluator", false,
429                      true)
430INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
431INITIALIZE_PASS_END(AAEvalLegacyPass, "aa-eval",
432                    "Exhaustive Alias Analysis Precision Evaluator", false,
433                    true)
434
435FunctionPass *llvm::createAAEvalPass() { return new AAEvalLegacyPass(); }
436