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