Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Analysis/AliasAnalysis.cpp
Line
Count
Source (jump to first uncovered line)
1
//==- AliasAnalysis.cpp - Generic Alias Analysis Interface Implementation --==//
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
// This file implements the generic AliasAnalysis interface which is used as the
10
// common interface used by all clients and implementations of alias analysis.
11
//
12
// This file also implements the default version of the AliasAnalysis interface
13
// that is to be used when no other implementation is specified.  This does some
14
// simple tests that detect obvious cases: two different global pointers cannot
15
// alias, a global cannot alias a malloc, two different mallocs cannot alias,
16
// etc.
17
//
18
// This alias analysis implementation really isn't very good for anything, but
19
// it is very fast, and makes a nice clean default implementation.  Because it
20
// handles lots of little corner cases, other, more complex, alias analysis
21
// implementations may choose to rely on this pass to resolve these simple and
22
// easy cases.
23
//
24
//===----------------------------------------------------------------------===//
25
26
#include "llvm/Analysis/AliasAnalysis.h"
27
#include "llvm/Analysis/BasicAliasAnalysis.h"
28
#include "llvm/Analysis/CFLAndersAliasAnalysis.h"
29
#include "llvm/Analysis/CFLSteensAliasAnalysis.h"
30
#include "llvm/Analysis/CaptureTracking.h"
31
#include "llvm/Analysis/GlobalsModRef.h"
32
#include "llvm/Analysis/MemoryLocation.h"
33
#include "llvm/Analysis/ObjCARCAliasAnalysis.h"
34
#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
35
#include "llvm/Analysis/ScopedNoAliasAA.h"
36
#include "llvm/Analysis/TargetLibraryInfo.h"
37
#include "llvm/Analysis/TypeBasedAliasAnalysis.h"
38
#include "llvm/Analysis/ValueTracking.h"
39
#include "llvm/IR/Argument.h"
40
#include "llvm/IR/Attributes.h"
41
#include "llvm/IR/BasicBlock.h"
42
#include "llvm/IR/Instruction.h"
43
#include "llvm/IR/Instructions.h"
44
#include "llvm/IR/Module.h"
45
#include "llvm/IR/Type.h"
46
#include "llvm/IR/Value.h"
47
#include "llvm/Pass.h"
48
#include "llvm/Support/AtomicOrdering.h"
49
#include "llvm/Support/Casting.h"
50
#include "llvm/Support/CommandLine.h"
51
#include <algorithm>
52
#include <cassert>
53
#include <functional>
54
#include <iterator>
55
56
using namespace llvm;
57
58
/// Allow disabling BasicAA from the AA results. This is particularly useful
59
/// when testing to isolate a single AA implementation.
60
static cl::opt<bool> DisableBasicAA("disable-basicaa", cl::Hidden,
61
                                    cl::init(false));
62
63
AAResults::AAResults(AAResults &&Arg)
64
1.18M
    : TLI(Arg.TLI), AAs(std::move(Arg.AAs)), AADeps(std::move(Arg.AADeps)) {
65
1.18M
  for (auto &AA : AAs)
66
4.64M
    AA->setAAResults(this);
67
1.18M
}
68
69
11.7M
AAResults::~AAResults() {
70
11.7M
// FIXME; It would be nice to at least clear out the pointers back to this
71
11.7M
// aggregation here, but we end up with non-nesting lifetimes in the legacy
72
11.7M
// pass manager that prevent this from working. In the legacy pass manager
73
11.7M
// we'll end up with dangling references here in some cases.
74
#if 0
75
  for (auto &AA : AAs)
76
    AA->setAAResults(nullptr);
77
#endif
78
}
79
80
bool AAResults::invalidate(Function &F, const PreservedAnalyses &PA,
81
4.21k
                           FunctionAnalysisManager::Invalidator &Inv) {
82
4.21k
  // AAResults preserves the AAManager by default, due to the stateless nature
83
4.21k
  // of AliasAnalysis. There is no need to check whether it has been preserved
84
4.21k
  // explicitly. Check if any module dependency was invalidated and caused the
85
4.21k
  // AAManager to be invalidated. Invalidate ourselves in that case.
86
4.21k
  auto PAC = PA.getChecker<AAManager>();
87
4.21k
  if (!PAC.preservedWhenStateless())
88
830
    return true;
89
3.38k
90
3.38k
  // Check if any of the function dependencies were invalidated, and invalidate
91
3.38k
  // ourselves in that case.
92
3.38k
  for (AnalysisKey *ID : AADeps)
93
5.61k
    if (Inv.invalidate(ID, F, PA))
94
622
      return true;
95
3.38k
96
3.38k
  // Everything we depend on is still fine, so are we. Nothing to invalidate.
97
3.38k
  
return false2.76k
;
98
3.38k
}
99
100
//===----------------------------------------------------------------------===//
101
// Default chaining methods
102
//===----------------------------------------------------------------------===//
103
104
AliasResult AAResults::alias(const MemoryLocation &LocA,
105
28.9M
                             const MemoryLocation &LocB) {
106
28.9M
  AAQueryInfo AAQIP;
107
28.9M
  return alias(LocA, LocB, AAQIP);
108
28.9M
}
109
110
AliasResult AAResults::alias(const MemoryLocation &LocA,
111
81.3M
                             const MemoryLocation &LocB, AAQueryInfo &AAQI) {
112
199M
  for (const auto &AA : AAs) {
113
199M
    auto Result = AA->alias(LocA, LocB, AAQI);
114
199M
    if (Result != MayAlias)
115
47.6M
      return Result;
116
199M
  }
117
81.3M
  
return MayAlias33.6M
;
118
81.3M
}
119
120
bool AAResults::pointsToConstantMemory(const MemoryLocation &Loc,
121
31.2M
                                       bool OrLocal) {
122
31.2M
  AAQueryInfo AAQIP;
123
31.2M
  return pointsToConstantMemory(Loc, AAQIP, OrLocal);
124
31.2M
}
125
126
bool AAResults::pointsToConstantMemory(const MemoryLocation &Loc,
127
37.7M
                                       AAQueryInfo &AAQI, bool OrLocal) {
128
37.7M
  for (const auto &AA : AAs)
129
135M
    if (AA->pointsToConstantMemory(Loc, AAQI, OrLocal))
130
572k
      return true;
131
37.7M
132
37.7M
  
return false37.1M
;
133
37.7M
}
134
135
564k
ModRefInfo AAResults::getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) {
136
564k
  ModRefInfo Result = ModRefInfo::ModRef;
137
564k
138
2.20M
  for (const auto &AA : AAs) {
139
2.20M
    Result = intersectModRef(Result, AA->getArgModRefInfo(Call, ArgIdx));
140
2.20M
141
2.20M
    // Early-exit the moment we reach the bottom of the lattice.
142
2.20M
    if (isNoModRef(Result))
143
1
      return ModRefInfo::NoModRef;
144
2.20M
  }
145
564k
146
564k
  
return Result564k
;
147
564k
}
148
149
583
ModRefInfo AAResults::getModRefInfo(Instruction *I, const CallBase *Call2) {
150
583
  AAQueryInfo AAQIP;
151
583
  return getModRefInfo(I, Call2, AAQIP);
152
583
}
153
154
ModRefInfo AAResults::getModRefInfo(Instruction *I, const CallBase *Call2,
155
44.6k
                                    AAQueryInfo &AAQI) {
156
44.6k
  // We may have two calls.
157
44.6k
  if (const auto *Call1 = dyn_cast<CallBase>(I)) {
158
20.2k
    // Check if the two calls modify the same memory.
159
20.2k
    return getModRefInfo(Call1, Call2, AAQI);
160
24.3k
  } else if (I->isFenceLike()) {
161
1
    // If this is a fence, just return ModRef.
162
1
    return ModRefInfo::ModRef;
163
24.3k
  } else {
164
24.3k
    // Otherwise, check if the call modifies or references the
165
24.3k
    // location this memory access defines.  The best we can say
166
24.3k
    // is that if the call references what this instruction
167
24.3k
    // defines, it must be clobbered by this location.
168
24.3k
    const MemoryLocation DefLoc = MemoryLocation::get(I);
169
24.3k
    ModRefInfo MR = getModRefInfo(Call2, DefLoc, AAQI);
170
24.3k
    if (isModOrRefSet(MR))
171
11.4k
      return setModAndRef(MR);
172
12.9k
  }
173
12.9k
  return ModRefInfo::NoModRef;
174
12.9k
}
175
176
ModRefInfo AAResults::getModRefInfo(const CallBase *Call,
177
332k
                                    const MemoryLocation &Loc) {
178
332k
  AAQueryInfo AAQIP;
179
332k
  return getModRefInfo(Call, Loc, AAQIP);
180
332k
}
181
182
ModRefInfo AAResults::getModRefInfo(const CallBase *Call,
183
                                    const MemoryLocation &Loc,
184
8.60M
                                    AAQueryInfo &AAQI) {
185
8.60M
  ModRefInfo Result = ModRefInfo::ModRef;
186
8.60M
187
31.1M
  for (const auto &AA : AAs) {
188
31.1M
    Result = intersectModRef(Result, AA->getModRefInfo(Call, Loc, AAQI));
189
31.1M
190
31.1M
    // Early-exit the moment we reach the bottom of the lattice.
191
31.1M
    if (isNoModRef(Result))
192
685k
      return ModRefInfo::NoModRef;
193
31.1M
  }
194
8.60M
195
8.60M
  // Try to refine the mod-ref info further using other API entry points to the
196
8.60M
  // aggregate set of AA results.
197
8.60M
  auto MRB = getModRefBehavior(Call);
198
7.91M
  if (MRB == FMRB_DoesNotAccessMemory ||
199
7.91M
      
MRB == FMRB_OnlyAccessesInaccessibleMem7.84M
)
200
72.8k
    return ModRefInfo::NoModRef;
201
7.84M
202
7.84M
  if (onlyReadsMemory(MRB))
203
47.4k
    Result = clearMod(Result);
204
7.79M
  else if (doesNotReadMemory(MRB))
205
415
    Result = clearRef(Result);
206
7.84M
207
7.84M
  if (onlyAccessesArgPointees(MRB) || 
onlyAccessesInaccessibleOrArgMem(MRB)6.70M
) {
208
1.14M
    bool IsMustAlias = true;
209
1.14M
    ModRefInfo AllArgsMask = ModRefInfo::NoModRef;
210
1.14M
    if (doesAccessArgPointees(MRB)) {
211
4.39M
      for (auto AI = Call->arg_begin(), AE = Call->arg_end(); AI != AE; 
++AI3.24M
) {
212
3.24M
        const Value *Arg = *AI;
213
3.24M
        if (!Arg->getType()->isPointerTy())
214
1.92M
          continue;
215
1.32M
        unsigned ArgIdx = std::distance(Call->arg_begin(), AI);
216
1.32M
        MemoryLocation ArgLoc =
217
1.32M
            MemoryLocation::getForArgument(Call, ArgIdx, TLI);
218
1.32M
        AliasResult ArgAlias = alias(ArgLoc, Loc);
219
1.32M
        if (ArgAlias != NoAlias) {
220
417k
          ModRefInfo ArgMask = getArgModRefInfo(Call, ArgIdx);
221
417k
          AllArgsMask = unionModRef(AllArgsMask, ArgMask);
222
417k
        }
223
1.32M
        // Conservatively clear IsMustAlias unless only MustAlias is found.
224
1.32M
        IsMustAlias &= (ArgAlias == MustAlias);
225
1.32M
      }
226
1.14M
    }
227
1.14M
    // Return NoModRef if no alias found with any argument.
228
1.14M
    if (isNoModRef(AllArgsMask))
229
796k
      return ModRefInfo::NoModRef;
230
348k
    // Logical & between other AA analyses and argument analysis.
231
348k
    Result = intersectModRef(Result, AllArgsMask);
232
348k
    // If only MustAlias found above, set Must bit.
233
348k
    Result = IsMustAlias ? 
setMust(Result)45.4k
:
clearMust(Result)303k
;
234
348k
  }
235
7.84M
236
7.84M
  // If Loc is a constant memory location, the call definitely could not
237
7.84M
  // modify the memory location.
238
7.84M
  
if (7.04M
isModSet(Result)7.04M
&&
pointsToConstantMemory(Loc, /*OrLocal*/ false)6.92M
)
239
22.9k
    Result = clearMod(Result);
240
7.04M
241
7.04M
  return Result;
242
7.84M
}
243
244
ModRefInfo AAResults::getModRefInfo(const CallBase *Call1,
245
798k
                                    const CallBase *Call2) {
246
798k
  AAQueryInfo AAQIP;
247
798k
  return getModRefInfo(Call1, Call2, AAQIP);
248
798k
}
249
250
ModRefInfo AAResults::getModRefInfo(const CallBase *Call1,
251
818k
                                    const CallBase *Call2, AAQueryInfo &AAQI) {
252
818k
  ModRefInfo Result = ModRefInfo::ModRef;
253
818k
254
3.26M
  for (const auto &AA : AAs) {
255
3.26M
    Result = intersectModRef(Result, AA->getModRefInfo(Call1, Call2, AAQI));
256
3.26M
257
3.26M
    // Early-exit the moment we reach the bottom of the lattice.
258
3.26M
    if (isNoModRef(Result))
259
215
      return ModRefInfo::NoModRef;
260
3.26M
  }
261
818k
262
818k
  // Try to refine the mod-ref info further using other API entry points to the
263
818k
  // aggregate set of AA results.
264
818k
265
818k
  // If Call1 or Call2 are readnone, they don't interact.
266
818k
  auto Call1B = getModRefBehavior(Call1);
267
818k
  if (Call1B == FMRB_DoesNotAccessMemory)
268
8
    return ModRefInfo::NoModRef;
269
818k
270
818k
  auto Call2B = getModRefBehavior(Call2);
271
818k
  if (Call2B == FMRB_DoesNotAccessMemory)
272
276
    return ModRefInfo::NoModRef;
273
818k
274
818k
  // If they both only read from memory, there is no dependence.
275
818k
  if (onlyReadsMemory(Call1B) && 
onlyReadsMemory(Call2B)40.7k
)
276
35.1k
    return ModRefInfo::NoModRef;
277
782k
278
782k
  // If Call1 only reads memory, the only dependence on Call2 can be
279
782k
  // from Call1 reading memory written by Call2.
280
782k
  if (onlyReadsMemory(Call1B))
281
5.64k
    Result = clearMod(Result);
282
777k
  else if (doesNotReadMemory(Call1B))
283
28
    Result = clearRef(Result);
284
782k
285
782k
  // If Call2 only access memory through arguments, accumulate the mod/ref
286
782k
  // information from Call1's references to the memory referenced by
287
782k
  // Call2's arguments.
288
782k
  if (onlyAccessesArgPointees(Call2B)) {
289
35.8k
    if (!doesAccessArgPointees(Call2B))
290
0
      return ModRefInfo::NoModRef;
291
35.8k
    ModRefInfo R = ModRefInfo::NoModRef;
292
35.8k
    bool IsMustAlias = true;
293
142k
    for (auto I = Call2->arg_begin(), E = Call2->arg_end(); I != E; 
++I106k
) {
294
112k
      const Value *Arg = *I;
295
112k
      if (!Arg->getType()->isPointerTy())
296
63.9k
        continue;
297
48.2k
      unsigned Call2ArgIdx = std::distance(Call2->arg_begin(), I);
298
48.2k
      auto Call2ArgLoc =
299
48.2k
          MemoryLocation::getForArgument(Call2, Call2ArgIdx, TLI);
300
48.2k
301
48.2k
      // ArgModRefC2 indicates what Call2 might do to Call2ArgLoc, and the
302
48.2k
      // dependence of Call1 on that location is the inverse:
303
48.2k
      // - If Call2 modifies location, dependence exists if Call1 reads or
304
48.2k
      //   writes.
305
48.2k
      // - If Call2 only reads location, dependence exists if Call1 writes.
306
48.2k
      ModRefInfo ArgModRefC2 = getArgModRefInfo(Call2, Call2ArgIdx);
307
48.2k
      ModRefInfo ArgMask = ModRefInfo::NoModRef;
308
48.2k
      if (isModSet(ArgModRefC2))
309
35.8k
        ArgMask = ModRefInfo::ModRef;
310
12.3k
      else if (isRefSet(ArgModRefC2))
311
12.3k
        ArgMask = ModRefInfo::Mod;
312
48.2k
313
48.2k
      // ModRefC1 indicates what Call1 might do to Call2ArgLoc, and we use
314
48.2k
      // above ArgMask to update dependence info.
315
48.2k
      ModRefInfo ModRefC1 = getModRefInfo(Call1, Call2ArgLoc);
316
48.2k
      ArgMask = intersectModRef(ArgMask, ModRefC1);
317
48.2k
318
48.2k
      // Conservatively clear IsMustAlias unless only MustAlias is found.
319
48.2k
      IsMustAlias &= isMustSet(ModRefC1);
320
48.2k
321
48.2k
      R = intersectModRef(unionModRef(R, ArgMask), Result);
322
48.2k
      if (R == Result) {
323
5.61k
        // On early exit, not all args were checked, cannot set Must.
324
5.61k
        if (I + 1 != E)
325
3.01k
          IsMustAlias = false;
326
5.61k
        break;
327
5.61k
      }
328
48.2k
    }
329
35.8k
330
35.8k
    if (isNoModRef(R))
331
19.1k
      return ModRefInfo::NoModRef;
332
16.7k
333
16.7k
    // If MustAlias found above, set Must bit.
334
16.7k
    return IsMustAlias ? 
setMust(R)37
:
clearMust(R)16.7k
;
335
16.7k
  }
336
747k
337
747k
  // If Call1 only accesses memory through arguments, check if Call2 references
338
747k
  // any of the memory referenced by Call1's arguments. If not, return NoModRef.
339
747k
  if (onlyAccessesArgPointees(Call1B)) {
340
10.8k
    if (!doesAccessArgPointees(Call1B))
341
0
      return ModRefInfo::NoModRef;
342
10.8k
    ModRefInfo R = ModRefInfo::NoModRef;
343
10.8k
    bool IsMustAlias = true;
344
33.1k
    for (auto I = Call1->arg_begin(), E = Call1->arg_end(); I != E; 
++I22.3k
) {
345
29.2k
      const Value *Arg = *I;
346
29.2k
      if (!Arg->getType()->isPointerTy())
347
10.8k
        continue;
348
18.3k
      unsigned Call1ArgIdx = std::distance(Call1->arg_begin(), I);
349
18.3k
      auto Call1ArgLoc =
350
18.3k
          MemoryLocation::getForArgument(Call1, Call1ArgIdx, TLI);
351
18.3k
352
18.3k
      // ArgModRefC1 indicates what Call1 might do to Call1ArgLoc; if Call1
353
18.3k
      // might Mod Call1ArgLoc, then we care about either a Mod or a Ref by
354
18.3k
      // Call2. If Call1 might Ref, then we care only about a Mod by Call2.
355
18.3k
      ModRefInfo ArgModRefC1 = getArgModRefInfo(Call1, Call1ArgIdx);
356
18.3k
      ModRefInfo ModRefC2 = getModRefInfo(Call2, Call1ArgLoc);
357
18.3k
      if ((isModSet(ArgModRefC1) && 
isModOrRefSet(ModRefC2)10.8k
) ||
358
18.3k
          
(8.29k
isRefSet(ArgModRefC1)8.29k
&&
isModSet(ModRefC2)7.53k
))
359
16.9k
        R = intersectModRef(unionModRef(R, ArgModRefC1), Result);
360
18.3k
361
18.3k
      // Conservatively clear IsMustAlias unless only MustAlias is found.
362
18.3k
      IsMustAlias &= isMustSet(ModRefC2);
363
18.3k
364
18.3k
      if (R == Result) {
365
6.86k
        // On early exit, not all args were checked, cannot set Must.
366
6.86k
        if (I + 1 != E)
367
6.53k
          IsMustAlias = false;
368
6.86k
        break;
369
6.86k
      }
370
18.3k
    }
371
10.8k
372
10.8k
    if (isNoModRef(R))
373
427
      return ModRefInfo::NoModRef;
374
10.4k
375
10.4k
    // If MustAlias found above, set Must bit.
376
10.4k
    return IsMustAlias ? 
setMust(R)2
:
clearMust(R)10.4k
;
377
10.4k
  }
378
736k
379
736k
  return Result;
380
736k
}
381
382
17.7M
FunctionModRefBehavior AAResults::getModRefBehavior(const CallBase *Call) {
383
17.7M
  FunctionModRefBehavior Result = FMRB_UnknownModRefBehavior;
384
17.7M
385
67.3M
  for (const auto &AA : AAs) {
386
67.3M
    Result = FunctionModRefBehavior(Result & AA->getModRefBehavior(Call));
387
67.3M
388
67.3M
    // Early-exit the moment we reach the bottom of the lattice.
389
67.3M
    if (Result == FMRB_DoesNotAccessMemory)
390
268k
      return Result;
391
67.3M
  }
392
17.7M
393
17.7M
  
return Result17.4M
;
394
17.7M
}
395
396
17.0M
FunctionModRefBehavior AAResults::getModRefBehavior(const Function *F) {
397
17.0M
  FunctionModRefBehavior Result = FMRB_UnknownModRefBehavior;
398
17.0M
399
65.4M
  for (const auto &AA : AAs) {
400
65.4M
    Result = FunctionModRefBehavior(Result & AA->getModRefBehavior(F));
401
65.4M
402
65.4M
    // Early-exit the moment we reach the bottom of the lattice.
403
65.4M
    if (Result == FMRB_DoesNotAccessMemory)
404
21.0k
      return Result;
405
65.4M
  }
406
17.0M
407
17.0M
  
return Result16.9M
;
408
17.0M
}
409
410
5.73k
raw_ostream &llvm::operator<<(raw_ostream &OS, AliasResult AR) {
411
5.73k
  switch (AR) {
412
5.73k
  case NoAlias:
413
2.47k
    OS << "NoAlias";
414
2.47k
    break;
415
5.73k
  case MustAlias:
416
207
    OS << "MustAlias";
417
207
    break;
418
5.73k
  case MayAlias:
419
3.00k
    OS << "MayAlias";
420
3.00k
    break;
421
5.73k
  case PartialAlias:
422
41
    OS << "PartialAlias";
423
41
    break;
424
5.73k
  }
425
5.73k
  return OS;
426
5.73k
}
427
428
//===----------------------------------------------------------------------===//
429
// Helper method implementation
430
//===----------------------------------------------------------------------===//
431
432
ModRefInfo AAResults::getModRefInfo(const LoadInst *L,
433
1
                                    const MemoryLocation &Loc) {
434
1
  AAQueryInfo AAQIP;
435
1
  return getModRefInfo(L, Loc, AAQIP);
436
1
}
437
ModRefInfo AAResults::getModRefInfo(const LoadInst *L,
438
                                    const MemoryLocation &Loc,
439
3.11M
                                    AAQueryInfo &AAQI) {
440
3.11M
  // Be conservative in the face of atomic.
441
3.11M
  if (isStrongerThan(L->getOrdering(), AtomicOrdering::Unordered))
442
1.31k
    return ModRefInfo::ModRef;
443
3.11M
444
3.11M
  // If the load address doesn't alias the given address, it doesn't read
445
3.11M
  // or write the specified memory.
446
3.11M
  if (Loc.Ptr) {
447
50.2k
    AliasResult AR = alias(MemoryLocation::get(L), Loc, AAQI);
448
50.2k
    if (AR == NoAlias)
449
28.9k
      return ModRefInfo::NoModRef;
450
21.2k
    if (AR == MustAlias)
451
3.27k
      return ModRefInfo::MustRef;
452
3.08M
  }
453
3.08M
  // Otherwise, a load just reads.
454
3.08M
  return ModRefInfo::Ref;
455
3.08M
}
456
457
ModRefInfo AAResults::getModRefInfo(const StoreInst *S,
458
10.7M
                                    const MemoryLocation &Loc) {
459
10.7M
  AAQueryInfo AAQIP;
460
10.7M
  return getModRefInfo(S, Loc, AAQIP);
461
10.7M
}
462
ModRefInfo AAResults::getModRefInfo(const StoreInst *S,
463
                                    const MemoryLocation &Loc,
464
16.9M
                                    AAQueryInfo &AAQI) {
465
16.9M
  // Be conservative in the face of atomic.
466
16.9M
  if (isStrongerThan(S->getOrdering(), AtomicOrdering::Unordered))
467
11.6k
    return ModRefInfo::ModRef;
468
16.9M
469
16.9M
  if (Loc.Ptr) {
470
14.8M
    AliasResult AR = alias(MemoryLocation::get(S), Loc, AAQI);
471
14.8M
    // If the store address cannot alias the pointer in question, then the
472
14.8M
    // specified memory cannot be modified by the store.
473
14.8M
    if (AR == NoAlias)
474
12.5M
      return ModRefInfo::NoModRef;
475
2.29M
476
2.29M
    // If the pointer is a pointer to constant memory, then it could not have
477
2.29M
    // been modified by this store.
478
2.29M
    if (pointsToConstantMemory(Loc, AAQI))
479
11.3k
      return ModRefInfo::NoModRef;
480
2.28M
481
2.28M
    // If the store address aliases the pointer as must alias, set Must.
482
2.28M
    if (AR == MustAlias)
483
136k
      return ModRefInfo::MustMod;
484
4.27M
  }
485
4.27M
486
4.27M
  // Otherwise, a store just writes.
487
4.27M
  return ModRefInfo::Mod;
488
4.27M
}
489
490
0
ModRefInfo AAResults::getModRefInfo(const FenceInst *S, const MemoryLocation &Loc) {
491
0
  AAQueryInfo AAQIP;
492
0
  return getModRefInfo(S, Loc, AAQIP);
493
0
}
494
495
ModRefInfo AAResults::getModRefInfo(const FenceInst *S,
496
                                    const MemoryLocation &Loc,
497
36.4k
                                    AAQueryInfo &AAQI) {
498
36.4k
  // If we know that the location is a constant memory location, the fence
499
36.4k
  // cannot modify this location.
500
36.4k
  if (Loc.Ptr && 
pointsToConstantMemory(Loc, AAQI)26.5k
)
501
15
    return ModRefInfo::Ref;
502
36.4k
  return ModRefInfo::ModRef;
503
36.4k
}
504
505
ModRefInfo AAResults::getModRefInfo(const VAArgInst *V,
506
1
                                    const MemoryLocation &Loc) {
507
1
  AAQueryInfo AAQIP;
508
1
  return getModRefInfo(V, Loc, AAQIP);
509
1
}
510
511
ModRefInfo AAResults::getModRefInfo(const VAArgInst *V,
512
                                    const MemoryLocation &Loc,
513
1.11k
                                    AAQueryInfo &AAQI) {
514
1.11k
  if (Loc.Ptr) {
515
807
    AliasResult AR = alias(MemoryLocation::get(V), Loc, AAQI);
516
807
    // If the va_arg address cannot alias the pointer in question, then the
517
807
    // specified memory cannot be accessed by the va_arg.
518
807
    if (AR == NoAlias)
519
558
      return ModRefInfo::NoModRef;
520
249
521
249
    // If the pointer is a pointer to constant memory, then it could not have
522
249
    // been modified by this va_arg.
523
249
    if (pointsToConstantMemory(Loc, AAQI))
524
0
      return ModRefInfo::NoModRef;
525
249
526
249
    // If the va_arg aliases the pointer as must alias, set Must.
527
249
    if (AR == MustAlias)
528
1
      return ModRefInfo::MustModRef;
529
552
  }
530
552
531
552
  // Otherwise, a va_arg reads and writes.
532
552
  return ModRefInfo::ModRef;
533
552
}
534
535
ModRefInfo AAResults::getModRefInfo(const CatchPadInst *CatchPad,
536
0
                                    const MemoryLocation &Loc) {
537
0
  AAQueryInfo AAQIP;
538
0
  return getModRefInfo(CatchPad, Loc, AAQIP);
539
0
}
540
541
ModRefInfo AAResults::getModRefInfo(const CatchPadInst *CatchPad,
542
                                    const MemoryLocation &Loc,
543
17
                                    AAQueryInfo &AAQI) {
544
17
  if (Loc.Ptr) {
545
1
    // If the pointer is a pointer to constant memory,
546
1
    // then it could not have been modified by this catchpad.
547
1
    if (pointsToConstantMemory(Loc, AAQI))
548
0
      return ModRefInfo::NoModRef;
549
17
  }
550
17
551
17
  // Otherwise, a catchpad reads and writes.
552
17
  return ModRefInfo::ModRef;
553
17
}
554
555
ModRefInfo AAResults::getModRefInfo(const CatchReturnInst *CatchRet,
556
0
                                    const MemoryLocation &Loc) {
557
0
  AAQueryInfo AAQIP;
558
0
  return getModRefInfo(CatchRet, Loc, AAQIP);
559
0
}
560
561
ModRefInfo AAResults::getModRefInfo(const CatchReturnInst *CatchRet,
562
                                    const MemoryLocation &Loc,
563
26
                                    AAQueryInfo &AAQI) {
564
26
  if (Loc.Ptr) {
565
10
    // If the pointer is a pointer to constant memory,
566
10
    // then it could not have been modified by this catchpad.
567
10
    if (pointsToConstantMemory(Loc, AAQI))
568
0
      return ModRefInfo::NoModRef;
569
26
  }
570
26
571
26
  // Otherwise, a catchret reads and writes.
572
26
  return ModRefInfo::ModRef;
573
26
}
574
575
ModRefInfo AAResults::getModRefInfo(const AtomicCmpXchgInst *CX,
576
1
                                    const MemoryLocation &Loc) {
577
1
  AAQueryInfo AAQIP;
578
1
  return getModRefInfo(CX, Loc, AAQIP);
579
1
}
580
581
ModRefInfo AAResults::getModRefInfo(const AtomicCmpXchgInst *CX,
582
                                    const MemoryLocation &Loc,
583
27.9k
                                    AAQueryInfo &AAQI) {
584
27.9k
  // Acquire/Release cmpxchg has properties that matter for arbitrary addresses.
585
27.9k
  if (isStrongerThanMonotonic(CX->getSuccessOrdering()))
586
27.8k
    return ModRefInfo::ModRef;
587
34
588
34
  if (Loc.Ptr) {
589
0
    AliasResult AR = alias(MemoryLocation::get(CX), Loc, AAQI);
590
0
    // If the cmpxchg address does not alias the location, it does not access
591
0
    // it.
592
0
    if (AR == NoAlias)
593
0
      return ModRefInfo::NoModRef;
594
0
595
0
    // If the cmpxchg address aliases the pointer as must alias, set Must.
596
0
    if (AR == MustAlias)
597
0
      return ModRefInfo::MustModRef;
598
34
  }
599
34
600
34
  return ModRefInfo::ModRef;
601
34
}
602
603
ModRefInfo AAResults::getModRefInfo(const AtomicRMWInst *RMW,
604
1
                                    const MemoryLocation &Loc) {
605
1
  AAQueryInfo AAQIP;
606
1
  return getModRefInfo(RMW, Loc, AAQIP);
607
1
}
608
609
ModRefInfo AAResults::getModRefInfo(const AtomicRMWInst *RMW,
610
                                    const MemoryLocation &Loc,
611
114k
                                    AAQueryInfo &AAQI) {
612
114k
  // Acquire/Release atomicrmw has properties that matter for arbitrary addresses.
613
114k
  if (isStrongerThanMonotonic(RMW->getOrdering()))
614
113k
    return ModRefInfo::ModRef;
615
557
616
557
  if (Loc.Ptr) {
617
145
    AliasResult AR = alias(MemoryLocation::get(RMW), Loc, AAQI);
618
145
    // If the atomicrmw address does not alias the location, it does not access
619
145
    // it.
620
145
    if (AR == NoAlias)
621
4
      return ModRefInfo::NoModRef;
622
141
623
141
    // If the atomicrmw address aliases the pointer as must alias, set Must.
624
141
    if (AR == MustAlias)
625
0
      return ModRefInfo::MustModRef;
626
553
  }
627
553
628
553
  return ModRefInfo::ModRef;
629
553
}
630
631
/// Return information about whether a particular call site modifies
632
/// or reads the specified memory location \p MemLoc before instruction \p I
633
/// in a BasicBlock. An ordered basic block \p OBB can be used to speed up
634
/// instruction-ordering queries inside the BasicBlock containing \p I.
635
/// FIXME: this is really just shoring-up a deficiency in alias analysis.
636
/// BasicAA isn't willing to spend linear time determining whether an alloca
637
/// was captured before or after this particular call, while we are. However,
638
/// with a smarter AA in place, this test is just wasting compile time.
639
ModRefInfo AAResults::callCapturesBefore(const Instruction *I,
640
                                         const MemoryLocation &MemLoc,
641
                                         DominatorTree *DT,
642
1.74M
                                         OrderedBasicBlock *OBB) {
643
1.74M
  if (!DT)
644
0
    return ModRefInfo::ModRef;
645
1.74M
646
1.74M
  const Value *Object =
647
1.74M
      GetUnderlyingObject(MemLoc.Ptr, I->getModule()->getDataLayout());
648
1.74M
  if (!isIdentifiedObject(Object) || 
isa<GlobalValue>(Object)733k
||
649
1.74M
      
isa<Constant>(Object)458k
)
650
1.29M
    return ModRefInfo::ModRef;
651
458k
652
458k
  const auto *Call = dyn_cast<CallBase>(I);
653
458k
  if (!Call || 
Call == Object431k
)
654
27.0k
    return ModRefInfo::ModRef;
655
431k
656
431k
  if (PointerMayBeCapturedBefore(Object, /* ReturnCaptures */ true,
657
431k
                                 /* StoreCaptures */ true, I, DT,
658
431k
                                 /* include Object */ true,
659
431k
                                 /* OrderedBasicBlock */ OBB))
660
406k
    return ModRefInfo::ModRef;
661
24.6k
662
24.6k
  unsigned ArgNo = 0;
663
24.6k
  ModRefInfo R = ModRefInfo::NoModRef;
664
24.6k
  bool IsMustAlias = true;
665
24.6k
  // Set flag only if no May found and all operands processed.
666
24.6k
  for (auto CI = Call->data_operands_begin(), CE = Call->data_operands_end();
667
52.0k
       CI != CE; 
++CI, ++ArgNo27.3k
) {
668
42.2k
    // Only look at the no-capture or byval pointer arguments.  If this
669
42.2k
    // pointer were passed to arguments that were neither of these, then it
670
42.2k
    // couldn't be no-capture.
671
42.2k
    if (!(*CI)->getType()->isPointerTy() ||
672
42.2k
        
(34.2k
!Call->doesNotCapture(ArgNo)34.2k
&&
ArgNo < Call->getNumArgOperands()17.5k
&&
673
34.2k
         
!Call->isByValArgument(ArgNo)17.5k
))
674
25.0k
      continue;
675
17.2k
676
17.2k
    AliasResult AR = alias(MemoryLocation(*CI), MemoryLocation(Object));
677
17.2k
    // If this is a no-capture pointer argument, see if we can tell that it
678
17.2k
    // is impossible to alias the pointer we're checking.  If not, we have to
679
17.2k
    // assume that the call could touch the pointer, even though it doesn't
680
17.2k
    // escape.
681
17.2k
    if (AR != MustAlias)
682
2.51k
      IsMustAlias = false;
683
17.2k
    if (AR == NoAlias)
684
2.33k
      continue;
685
14.9k
    if (Call->doesNotAccessMemory(ArgNo))
686
0
      continue;
687
14.9k
    if (Call->onlyReadsMemory(ArgNo)) {
688
21
      R = ModRefInfo::Ref;
689
21
      continue;
690
21
    }
691
14.9k
    // Not returning MustModRef since we have not seen all the arguments.
692
14.9k
    return ModRefInfo::ModRef;
693
14.9k
  }
694
24.6k
  
return IsMustAlias 9.74k
?
setMust(R)9.20k
:
clearMust(R)536
;
695
24.6k
}
696
697
/// canBasicBlockModify - Return true if it is possible for execution of the
698
/// specified basic block to modify the location Loc.
699
///
700
bool AAResults::canBasicBlockModify(const BasicBlock &BB,
701
805
                                    const MemoryLocation &Loc) {
702
805
  return canInstructionRangeModRef(BB.front(), BB.back(), Loc, ModRefInfo::Mod);
703
805
}
704
705
/// canInstructionRangeModRef - Return true if it is possible for the
706
/// execution of the specified instructions to mod\ref (according to the
707
/// mode) the location Loc. The instructions to consider are all
708
/// of the instructions in the range of [I1,I2] INCLUSIVE.
709
/// I1 and I2 must be in the same basic block.
710
bool AAResults::canInstructionRangeModRef(const Instruction &I1,
711
                                          const Instruction &I2,
712
                                          const MemoryLocation &Loc,
713
8.24k
                                          const ModRefInfo Mode) {
714
8.24k
  assert(I1.getParent() == I2.getParent() &&
715
8.24k
         "Instructions not in same basic block!");
716
8.24k
  BasicBlock::const_iterator I = I1.getIterator();
717
8.24k
  BasicBlock::const_iterator E = I2.getIterator();
718
8.24k
  ++E;  // Convert from inclusive to exclusive range.
719
8.24k
720
46.2k
  for (; I != E; 
++I38.0k
) // Check every instruction in range
721
39.1k
    if (isModOrRefSet(intersectModRef(getModRefInfo(&*I, Loc), Mode)))
722
1.16k
      return true;
723
8.24k
  
return false7.07k
;
724
8.24k
}
725
726
// Provide a definition for the root virtual destructor.
727
39.9M
AAResults::Concept::~Concept() = default;
728
729
// Provide a definition for the static object used to identify passes.
730
AnalysisKey AAManager::Key;
731
732
namespace {
733
734
735
} // end anonymous namespace
736
737
char ExternalAAWrapperPass::ID = 0;
738
739
INITIALIZE_PASS(ExternalAAWrapperPass, "external-aa", "External Alias Analysis",
740
                false, true)
741
742
ImmutablePass *
743
2.65k
llvm::createExternalAAWrapperPass(ExternalAAWrapperPass::CallbackT Callback) {
744
2.65k
  return new ExternalAAWrapperPass(std::move(Callback));
745
2.65k
}
746
747
360k
AAResultsWrapperPass::AAResultsWrapperPass() : FunctionPass(ID) {
748
360k
  initializeAAResultsWrapperPassPass(*PassRegistry::getPassRegistry());
749
360k
}
750
751
char AAResultsWrapperPass::ID = 0;
752
753
102k
INITIALIZE_PASS_BEGIN(AAResultsWrapperPass, "aa",
754
102k
                      "Function Alias Analysis Results", false, true)
755
102k
INITIALIZE_PASS_DEPENDENCY(BasicAAWrapperPass)
756
102k
INITIALIZE_PASS_DEPENDENCY(CFLAndersAAWrapperPass)
757
102k
INITIALIZE_PASS_DEPENDENCY(CFLSteensAAWrapperPass)
758
102k
INITIALIZE_PASS_DEPENDENCY(ExternalAAWrapperPass)
759
102k
INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
760
102k
INITIALIZE_PASS_DEPENDENCY(ObjCARCAAWrapperPass)
761
102k
INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass)
762
102k
INITIALIZE_PASS_DEPENDENCY(ScopedNoAliasAAWrapperPass)
763
102k
INITIALIZE_PASS_DEPENDENCY(TypeBasedAAWrapperPass)
764
102k
INITIALIZE_PASS_END(AAResultsWrapperPass, "aa",
765
                    "Function Alias Analysis Results", false, true)
766
767
0
FunctionPass *llvm::createAAResultsWrapperPass() {
768
0
  return new AAResultsWrapperPass();
769
0
}
770
771
/// Run the wrapper pass to rebuild an aggregation over known AA passes.
772
///
773
/// This is the legacy pass manager's interface to the new-style AA results
774
/// aggregation object. Because this is somewhat shoe-horned into the legacy
775
/// pass manager, we hard code all the specific alias analyses available into
776
/// it. While the particular set enabled is configured via commandline flags,
777
/// adding a new alias analysis to LLVM will require adding support for it to
778
/// this list.
779
9.40M
bool AAResultsWrapperPass::runOnFunction(Function &F) {
780
9.40M
  // NB! This *must* be reset before adding new AA results to the new
781
9.40M
  // AAResults object because in the legacy pass manager, each instance
782
9.40M
  // of these will refer to the *same* immutable analyses, registering and
783
9.40M
  // unregistering themselves with them. We need to carefully tear down the
784
9.40M
  // previous object first, in this case replacing it with an empty one, before
785
9.40M
  // registering new results.
786
9.40M
  AAR.reset(
787
9.40M
      new AAResults(getAnalysis<TargetLibraryInfoWrapperPass>().getTLI()));
788
9.40M
789
9.40M
  // BasicAA is always available for function analyses. Also, we add it first
790
9.40M
  // so that it can trump TBAA results when it proves MustAlias.
791
9.40M
  // FIXME: TBAA should have an explicit mode to support this and then we
792
9.40M
  // should reconsider the ordering here.
793
9.40M
  if (!DisableBasicAA)
794
9.40M
    AAR->addAAResult(getAnalysis<BasicAAWrapperPass>().getResult());
795
9.40M
796
9.40M
  // Populate the results with the currently available AAs.
797
9.40M
  if (auto *WrapperPass = getAnalysisIfAvailable<ScopedNoAliasAAWrapperPass>())
798
9.38M
    AAR->addAAResult(WrapperPass->getResult());
799
9.40M
  if (auto *WrapperPass = getAnalysisIfAvailable<TypeBasedAAWrapperPass>())
800
9.38M
    AAR->addAAResult(WrapperPass->getResult());
801
9.40M
  if (auto *WrapperPass =
802
1.29k
          getAnalysisIfAvailable<objcarc::ObjCARCAAWrapperPass>())
803
1.29k
    AAR->addAAResult(WrapperPass->getResult());
804
9.40M
  if (auto *WrapperPass = getAnalysisIfAvailable<GlobalsAAWrapperPass>())
805
6.96M
    AAR->addAAResult(WrapperPass->getResult());
806
9.40M
  if (auto *WrapperPass = getAnalysisIfAvailable<SCEVAAWrapperPass>())
807
7
    AAR->addAAResult(WrapperPass->getResult());
808
9.40M
  if (auto *WrapperPass = getAnalysisIfAvailable<CFLAndersAAWrapperPass>())
809
42
    AAR->addAAResult(WrapperPass->getResult());
810
9.40M
  if (auto *WrapperPass = getAnalysisIfAvailable<CFLSteensAAWrapperPass>())
811
64
    AAR->addAAResult(WrapperPass->getResult());
812
9.40M
813
9.40M
  // If available, run an external AA providing callback over the results as
814
9.40M
  // well.
815
9.40M
  if (auto *WrapperPass = getAnalysisIfAvailable<ExternalAAWrapperPass>())
816
198k
    if (WrapperPass->CB)
817
198k
      WrapperPass->CB(*this, F, *AAR);
818
9.40M
819
9.40M
  // Analyses don't mutate the IR, so return false.
820
9.40M
  return false;
821
9.40M
}
822
823
360k
void AAResultsWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
824
360k
  AU.setPreservesAll();
825
360k
  AU.addRequired<BasicAAWrapperPass>();
826
360k
  AU.addRequired<TargetLibraryInfoWrapperPass>();
827
360k
828
360k
  // We also need to mark all the alias analysis passes we will potentially
829
360k
  // probe in runOnFunction as used here to ensure the legacy pass manager
830
360k
  // preserves them. This hard coding of lists of alias analyses is specific to
831
360k
  // the legacy pass manager.
832
360k
  AU.addUsedIfAvailable<ScopedNoAliasAAWrapperPass>();
833
360k
  AU.addUsedIfAvailable<TypeBasedAAWrapperPass>();
834
360k
  AU.addUsedIfAvailable<objcarc::ObjCARCAAWrapperPass>();
835
360k
  AU.addUsedIfAvailable<GlobalsAAWrapperPass>();
836
360k
  AU.addUsedIfAvailable<SCEVAAWrapperPass>();
837
360k
  AU.addUsedIfAvailable<CFLAndersAAWrapperPass>();
838
360k
  AU.addUsedIfAvailable<CFLSteensAAWrapperPass>();
839
360k
}
840
841
AAResults llvm::createLegacyPMAAResults(Pass &P, Function &F,
842
1.17M
                                        BasicAAResult &BAR) {
843
1.17M
  AAResults AAR(P.getAnalysis<TargetLibraryInfoWrapperPass>().getTLI());
844
1.17M
845
1.17M
  // Add in our explicitly constructed BasicAA results.
846
1.17M
  if (!DisableBasicAA)
847
1.17M
    AAR.addAAResult(BAR);
848
1.17M
849
1.17M
  // Populate the results with the other currently available AAs.
850
1.17M
  if (auto *WrapperPass =
851
1.14M
          P.getAnalysisIfAvailable<ScopedNoAliasAAWrapperPass>())
852
1.14M
    AAR.addAAResult(WrapperPass->getResult());
853
1.17M
  if (auto *WrapperPass = P.getAnalysisIfAvailable<TypeBasedAAWrapperPass>())
854
1.14M
    AAR.addAAResult(WrapperPass->getResult());
855
1.17M
  if (auto *WrapperPass =
856
119
          P.getAnalysisIfAvailable<objcarc::ObjCARCAAWrapperPass>())
857
119
    AAR.addAAResult(WrapperPass->getResult());
858
1.17M
  if (auto *WrapperPass = P.getAnalysisIfAvailable<GlobalsAAWrapperPass>())
859
1.14M
    AAR.addAAResult(WrapperPass->getResult());
860
1.17M
  if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLAndersAAWrapperPass>())
861
0
    AAR.addAAResult(WrapperPass->getResult());
862
1.17M
  if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLSteensAAWrapperPass>())
863
0
    AAR.addAAResult(WrapperPass->getResult());
864
1.17M
865
1.17M
  return AAR;
866
1.17M
}
867
868
168M
bool llvm::isNoAliasCall(const Value *V) {
869
168M
  if (const auto *Call = dyn_cast<CallBase>(V))
870
11.0M
    return Call->hasRetAttr(Attribute::NoAlias);
871
157M
  return false;
872
157M
}
873
874
16.2M
bool llvm::isNoAliasArgument(const Value *V) {
875
16.2M
  if (const Argument *A = dyn_cast<Argument>(V))
876
6.94M
    return A->hasNoAliasAttr();
877
9.32M
  return false;
878
9.32M
}
879
880
161M
bool llvm::isIdentifiedObject(const Value *V) {
881
161M
  if (isa<AllocaInst>(V))
882
20.9M
    return true;
883
140M
  if (isa<GlobalValue>(V) && 
!isa<GlobalAlias>(V)24.3M
)
884
24.3M
    return true;
885
115M
  if (isNoAliasCall(V))
886
2.77M
    return true;
887
113M
  if (const Argument *A = dyn_cast<Argument>(V))
888
33.0M
    return A->hasNoAliasAttr() || 
A->hasByValAttr()30.7M
;
889
80.0M
  return false;
890
80.0M
}
891
892
19.1M
bool llvm::isIdentifiedFunctionLocal(const Value *V) {
893
19.1M
  return isa<AllocaInst>(V) || 
isNoAliasCall(V)16.8M
||
isNoAliasArgument(V)16.2M
;
894
19.1M
}
895
896
50.3k
void llvm::getAAResultsAnalysisUsage(AnalysisUsage &AU) {
897
50.3k
  // This function needs to be in sync with llvm::createLegacyPMAAResults -- if
898
50.3k
  // more alias analyses are added to llvm::createLegacyPMAAResults, they need
899
50.3k
  // to be added here also.
900
50.3k
  AU.addRequired<TargetLibraryInfoWrapperPass>();
901
50.3k
  AU.addUsedIfAvailable<ScopedNoAliasAAWrapperPass>();
902
50.3k
  AU.addUsedIfAvailable<TypeBasedAAWrapperPass>();
903
50.3k
  AU.addUsedIfAvailable<objcarc::ObjCARCAAWrapperPass>();
904
50.3k
  AU.addUsedIfAvailable<GlobalsAAWrapperPass>();
905
50.3k
  AU.addUsedIfAvailable<CFLAndersAAWrapperPass>();
906
50.3k
  AU.addUsedIfAvailable<CFLSteensAAWrapperPass>();
907
50.3k
}