Coverage Report

Created: 2019-07-24 05:18

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