xref: /freebsd/contrib/llvm-project/llvm/lib/Analysis/AliasAnalysisEvaluator.cpp (revision 723da5d92f40a413585107f8455280ea575fe410) 
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/DataLayout.h"
13  #include "llvm/IR/Function.h"
14  #include "llvm/IR/InstIterator.h"
15  #include "llvm/IR/Instructions.h"
16  #include "llvm/IR/Module.h"
17  #include "llvm/Support/CommandLine.h"
18  #include "llvm/Support/raw_ostream.h"
19  using namespace llvm;
20  
21  static cl::opt<bool> PrintAll("print-all-alias-modref-info", cl::ReallyHidden);
22  
23  static cl::opt<bool> PrintNoAlias("print-no-aliases", cl::ReallyHidden);
24  static cl::opt<bool> PrintMayAlias("print-may-aliases", cl::ReallyHidden);
25  static cl::opt<bool> PrintPartialAlias("print-partial-aliases", cl::ReallyHidden);
26  static cl::opt<bool> PrintMustAlias("print-must-aliases", cl::ReallyHidden);
27  
28  static cl::opt<bool> PrintNoModRef("print-no-modref", cl::ReallyHidden);
29  static cl::opt<bool> PrintRef("print-ref", cl::ReallyHidden);
30  static cl::opt<bool> PrintMod("print-mod", cl::ReallyHidden);
31  static cl::opt<bool> PrintModRef("print-modref", cl::ReallyHidden);
32  
33  static cl::opt<bool> EvalAAMD("evaluate-aa-metadata", cl::ReallyHidden);
34  
35  static void PrintResults(AliasResult AR, bool P,
36                           std::pair<const Value *, Type *> Loc1,
37                           std::pair<const Value *, Type *> Loc2,
38                           const Module *M) {
39    if (PrintAll || P) {
40      Type *Ty1 = Loc1.second, *Ty2 = Loc2.second;
41      unsigned AS1 = Loc1.first->getType()->getPointerAddressSpace();
42      unsigned AS2 = Loc2.first->getType()->getPointerAddressSpace();
43      std::string o1, o2;
44      {
45        raw_string_ostream os1(o1), os2(o2);
46        Loc1.first->printAsOperand(os1, false, M);
47        Loc2.first->printAsOperand(os2, false, M);
48      }
49  
50      if (o2 < o1) {
51        std::swap(o1, o2);
52        std::swap(Ty1, Ty2);
53        std::swap(AS1, AS2);
54        // Change offset sign for the local AR, for printing only.
55        AR.swap();
56      }
57      errs() << "  " << AR << ":\t";
58      Ty1->print(errs(), false, /* NoDetails */ true);
59      if (AS1 != 0)
60        errs() << " addrspace(" << AS1 << ")";
61      errs() << "* " << o1 << ", ";
62      Ty2->print(errs(), false, /* NoDetails */ true);
63      if (AS2 != 0)
64        errs() << " addrspace(" << AS2 << ")";
65      errs() << "* " << o2 << "\n";
66    }
67  }
68  
69  static inline void PrintModRefResults(
70      const char *Msg, bool P, Instruction *I,
71      std::pair<const Value *, Type *> Loc, Module *M) {
72    if (PrintAll || P) {
73      errs() << "  " << Msg << ":  Ptr: ";
74      Loc.second->print(errs(), false, /* NoDetails */ true);
75      errs() << "* ";
76      Loc.first->printAsOperand(errs(), false, M);
77      errs() << "\t<->" << *I << '\n';
78    }
79  }
80  
81  static inline void PrintModRefResults(const char *Msg, bool P, CallBase *CallA,
82                                        CallBase *CallB, Module *M) {
83    if (PrintAll || P) {
84      errs() << "  " << Msg << ": " << *CallA << " <-> " << *CallB << '\n';
85    }
86  }
87  
88  static inline void PrintLoadStoreResults(AliasResult AR, bool P,
89                                           const Value *V1, const Value *V2,
90                                           const Module *M) {
91    if (PrintAll || P) {
92      errs() << "  " << AR << ": " << *V1 << " <-> " << *V2 << '\n';
93    }
94  }
95  
96  PreservedAnalyses AAEvaluator::run(Function &F, FunctionAnalysisManager &AM) {
97    runInternal(F, AM.getResult<AAManager>(F));
98    return PreservedAnalyses::all();
99  }
100  
101  void AAEvaluator::runInternal(Function &F, AAResults &AA) {
102    const DataLayout &DL = F.getDataLayout();
103  
104    ++FunctionCount;
105  
106    SetVector<std::pair<const Value *, Type *>> Pointers;
107    SmallSetVector<CallBase *, 16> Calls;
108    SetVector<Value *> Loads;
109    SetVector<Value *> Stores;
110  
111    for (Instruction &Inst : instructions(F)) {
112      if (auto *LI = dyn_cast<LoadInst>(&Inst)) {
113        Pointers.insert({LI->getPointerOperand(), LI->getType()});
114        Loads.insert(LI);
115      } else if (auto *SI = dyn_cast<StoreInst>(&Inst)) {
116        Pointers.insert({SI->getPointerOperand(),
117                         SI->getValueOperand()->getType()});
118        Stores.insert(SI);
119      } else if (auto *CB = dyn_cast<CallBase>(&Inst))
120        Calls.insert(CB);
121    }
122  
123    if (PrintAll || PrintNoAlias || PrintMayAlias || PrintPartialAlias ||
124        PrintMustAlias || PrintNoModRef || PrintMod || PrintRef || PrintModRef)
125      errs() << "Function: " << F.getName() << ": " << Pointers.size()
126             << " pointers, " << Calls.size() << " call sites\n";
127  
128    // iterate over the worklist, and run the full (n^2)/2 disambiguations
129    for (auto I1 = Pointers.begin(), E = Pointers.end(); I1 != E; ++I1) {
130      LocationSize Size1 = LocationSize::precise(DL.getTypeStoreSize(I1->second));
131      for (auto I2 = Pointers.begin(); I2 != I1; ++I2) {
132        LocationSize Size2 =
133            LocationSize::precise(DL.getTypeStoreSize(I2->second));
134        AliasResult AR = AA.alias(I1->first, Size1, I2->first, Size2);
135        switch (AR) {
136        case AliasResult::NoAlias:
137          PrintResults(AR, PrintNoAlias, *I1, *I2, F.getParent());
138          ++NoAliasCount;
139          break;
140        case AliasResult::MayAlias:
141          PrintResults(AR, PrintMayAlias, *I1, *I2, F.getParent());
142          ++MayAliasCount;
143          break;
144        case AliasResult::PartialAlias:
145          PrintResults(AR, PrintPartialAlias, *I1, *I2, F.getParent());
146          ++PartialAliasCount;
147          break;
148        case AliasResult::MustAlias:
149          PrintResults(AR, PrintMustAlias, *I1, *I2, F.getParent());
150          ++MustAliasCount;
151          break;
152        }
153      }
154    }
155  
156    if (EvalAAMD) {
157      // iterate over all pairs of load, store
158      for (Value *Load : Loads) {
159        for (Value *Store : Stores) {
160          AliasResult AR = AA.alias(MemoryLocation::get(cast<LoadInst>(Load)),
161                                    MemoryLocation::get(cast<StoreInst>(Store)));
162          switch (AR) {
163          case AliasResult::NoAlias:
164            PrintLoadStoreResults(AR, PrintNoAlias, Load, Store, F.getParent());
165            ++NoAliasCount;
166            break;
167          case AliasResult::MayAlias:
168            PrintLoadStoreResults(AR, PrintMayAlias, Load, Store, F.getParent());
169            ++MayAliasCount;
170            break;
171          case AliasResult::PartialAlias:
172            PrintLoadStoreResults(AR, PrintPartialAlias, Load, Store, F.getParent());
173            ++PartialAliasCount;
174            break;
175          case AliasResult::MustAlias:
176            PrintLoadStoreResults(AR, PrintMustAlias, Load, Store, F.getParent());
177            ++MustAliasCount;
178            break;
179          }
180        }
181      }
182  
183      // iterate over all pairs of store, store
184      for (SetVector<Value *>::iterator I1 = Stores.begin(), E = Stores.end();
185           I1 != E; ++I1) {
186        for (SetVector<Value *>::iterator I2 = Stores.begin(); I2 != I1; ++I2) {
187          AliasResult AR = AA.alias(MemoryLocation::get(cast<StoreInst>(*I1)),
188                                    MemoryLocation::get(cast<StoreInst>(*I2)));
189          switch (AR) {
190          case AliasResult::NoAlias:
191            PrintLoadStoreResults(AR, PrintNoAlias, *I1, *I2, F.getParent());
192            ++NoAliasCount;
193            break;
194          case AliasResult::MayAlias:
195            PrintLoadStoreResults(AR, PrintMayAlias, *I1, *I2, F.getParent());
196            ++MayAliasCount;
197            break;
198          case AliasResult::PartialAlias:
199            PrintLoadStoreResults(AR, PrintPartialAlias, *I1, *I2, F.getParent());
200            ++PartialAliasCount;
201            break;
202          case AliasResult::MustAlias:
203            PrintLoadStoreResults(AR, PrintMustAlias, *I1, *I2, F.getParent());
204            ++MustAliasCount;
205            break;
206          }
207        }
208      }
209    }
210  
211    // Mod/ref alias analysis: compare all pairs of calls and values
212    for (CallBase *Call : Calls) {
213      for (const auto &Pointer : Pointers) {
214        LocationSize Size =
215            LocationSize::precise(DL.getTypeStoreSize(Pointer.second));
216        switch (AA.getModRefInfo(Call, Pointer.first, Size)) {
217        case ModRefInfo::NoModRef:
218          PrintModRefResults("NoModRef", PrintNoModRef, Call, Pointer,
219                             F.getParent());
220          ++NoModRefCount;
221          break;
222        case ModRefInfo::Mod:
223          PrintModRefResults("Just Mod", PrintMod, Call, Pointer, F.getParent());
224          ++ModCount;
225          break;
226        case ModRefInfo::Ref:
227          PrintModRefResults("Just Ref", PrintRef, Call, Pointer, F.getParent());
228          ++RefCount;
229          break;
230        case ModRefInfo::ModRef:
231          PrintModRefResults("Both ModRef", PrintModRef, Call, Pointer,
232                             F.getParent());
233          ++ModRefCount;
234          break;
235        }
236      }
237    }
238  
239    // Mod/ref alias analysis: compare all pairs of calls
240    for (CallBase *CallA : Calls) {
241      for (CallBase *CallB : Calls) {
242        if (CallA == CallB)
243          continue;
244        switch (AA.getModRefInfo(CallA, CallB)) {
245        case ModRefInfo::NoModRef:
246          PrintModRefResults("NoModRef", PrintNoModRef, CallA, CallB,
247                             F.getParent());
248          ++NoModRefCount;
249          break;
250        case ModRefInfo::Mod:
251          PrintModRefResults("Just Mod", PrintMod, CallA, CallB, F.getParent());
252          ++ModCount;
253          break;
254        case ModRefInfo::Ref:
255          PrintModRefResults("Just Ref", PrintRef, CallA, CallB, F.getParent());
256          ++RefCount;
257          break;
258        case ModRefInfo::ModRef:
259          PrintModRefResults("Both ModRef", PrintModRef, CallA, CallB,
260                             F.getParent());
261          ++ModRefCount;
262          break;
263        }
264      }
265    }
266  }
267  
268  static void PrintPercent(int64_t Num, int64_t Sum) {
269    errs() << "(" << Num * 100LL / Sum << "." << ((Num * 1000LL / Sum) % 10)
270           << "%)\n";
271  }
272  
273  AAEvaluator::~AAEvaluator() {
274    if (FunctionCount == 0)
275      return;
276  
277    int64_t AliasSum =
278        NoAliasCount + MayAliasCount + PartialAliasCount + MustAliasCount;
279    errs() << "===== Alias Analysis Evaluator Report =====\n";
280    if (AliasSum == 0) {
281      errs() << "  Alias Analysis Evaluator Summary: No pointers!\n";
282    } else {
283      errs() << "  " << AliasSum << " Total Alias Queries Performed\n";
284      errs() << "  " << NoAliasCount << " no alias responses ";
285      PrintPercent(NoAliasCount, AliasSum);
286      errs() << "  " << MayAliasCount << " may alias responses ";
287      PrintPercent(MayAliasCount, AliasSum);
288      errs() << "  " << PartialAliasCount << " partial alias responses ";
289      PrintPercent(PartialAliasCount, AliasSum);
290      errs() << "  " << MustAliasCount << " must alias responses ";
291      PrintPercent(MustAliasCount, AliasSum);
292      errs() << "  Alias Analysis Evaluator Pointer Alias Summary: "
293             << NoAliasCount * 100 / AliasSum << "%/"
294             << MayAliasCount * 100 / AliasSum << "%/"
295             << PartialAliasCount * 100 / AliasSum << "%/"
296             << MustAliasCount * 100 / AliasSum << "%\n";
297    }
298  
299    // Display the summary for mod/ref analysis
300    int64_t ModRefSum = NoModRefCount + RefCount + ModCount + ModRefCount;
301    if (ModRefSum == 0) {
302      errs() << "  Alias Analysis Mod/Ref Evaluator Summary: no "
303                "mod/ref!\n";
304    } else {
305      errs() << "  " << ModRefSum << " Total ModRef Queries Performed\n";
306      errs() << "  " << NoModRefCount << " no mod/ref responses ";
307      PrintPercent(NoModRefCount, ModRefSum);
308      errs() << "  " << ModCount << " mod responses ";
309      PrintPercent(ModCount, ModRefSum);
310      errs() << "  " << RefCount << " ref responses ";
311      PrintPercent(RefCount, ModRefSum);
312      errs() << "  " << ModRefCount << " mod & ref responses ";
313      PrintPercent(ModRefCount, ModRefSum);
314      errs() << "  Alias Analysis Evaluator Mod/Ref Summary: "
315             << NoModRefCount * 100 / ModRefSum << "%/"
316             << ModCount * 100 / ModRefSum << "%/" << RefCount * 100 / ModRefSum
317             << "%/" << ModRefCount * 100 / ModRefSum << "%\n";
318    }
319  }
320