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