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