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