Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Analysis/BasicAliasAnalysis.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- BasicAliasAnalysis.cpp - Stateless Alias Analysis Impl -------------===//
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 defines the primary stateless implementation of the
10
// Alias Analysis interface that implements identities (two different
11
// globals cannot alias, etc), but does no stateful analysis.
12
//
13
//===----------------------------------------------------------------------===//
14
15
#include "llvm/Analysis/BasicAliasAnalysis.h"
16
#include "llvm/ADT/APInt.h"
17
#include "llvm/ADT/SmallPtrSet.h"
18
#include "llvm/ADT/SmallVector.h"
19
#include "llvm/ADT/Statistic.h"
20
#include "llvm/Analysis/AliasAnalysis.h"
21
#include "llvm/Analysis/AssumptionCache.h"
22
#include "llvm/Analysis/CFG.h"
23
#include "llvm/Analysis/CaptureTracking.h"
24
#include "llvm/Analysis/InstructionSimplify.h"
25
#include "llvm/Analysis/LoopInfo.h"
26
#include "llvm/Analysis/MemoryBuiltins.h"
27
#include "llvm/Analysis/MemoryLocation.h"
28
#include "llvm/Analysis/TargetLibraryInfo.h"
29
#include "llvm/Analysis/ValueTracking.h"
30
#include "llvm/Analysis/PhiValues.h"
31
#include "llvm/IR/Argument.h"
32
#include "llvm/IR/Attributes.h"
33
#include "llvm/IR/Constant.h"
34
#include "llvm/IR/Constants.h"
35
#include "llvm/IR/DataLayout.h"
36
#include "llvm/IR/DerivedTypes.h"
37
#include "llvm/IR/Dominators.h"
38
#include "llvm/IR/Function.h"
39
#include "llvm/IR/GetElementPtrTypeIterator.h"
40
#include "llvm/IR/GlobalAlias.h"
41
#include "llvm/IR/GlobalVariable.h"
42
#include "llvm/IR/InstrTypes.h"
43
#include "llvm/IR/Instruction.h"
44
#include "llvm/IR/Instructions.h"
45
#include "llvm/IR/IntrinsicInst.h"
46
#include "llvm/IR/Intrinsics.h"
47
#include "llvm/IR/Metadata.h"
48
#include "llvm/IR/Operator.h"
49
#include "llvm/IR/Type.h"
50
#include "llvm/IR/User.h"
51
#include "llvm/IR/Value.h"
52
#include "llvm/Pass.h"
53
#include "llvm/Support/Casting.h"
54
#include "llvm/Support/CommandLine.h"
55
#include "llvm/Support/Compiler.h"
56
#include "llvm/Support/KnownBits.h"
57
#include <cassert>
58
#include <cstdint>
59
#include <cstdlib>
60
#include <utility>
61
62
#define DEBUG_TYPE "basicaa"
63
64
using namespace llvm;
65
66
/// Enable analysis of recursive PHI nodes.
67
static cl::opt<bool> EnableRecPhiAnalysis("basicaa-recphi", cl::Hidden,
68
                                          cl::init(false));
69
70
/// By default, even on 32-bit architectures we use 64-bit integers for
71
/// calculations. This will allow us to more-aggressively decompose indexing
72
/// expressions calculated using i64 values (e.g., long long in C) which is
73
/// common enough to worry about.
74
static cl::opt<bool> ForceAtLeast64Bits("basicaa-force-at-least-64b",
75
                                        cl::Hidden, cl::init(true));
76
static cl::opt<bool> DoubleCalcBits("basicaa-double-calc-bits",
77
                                    cl::Hidden, cl::init(false));
78
79
/// SearchLimitReached / SearchTimes shows how often the limit of
80
/// to decompose GEPs is reached. It will affect the precision
81
/// of basic alias analysis.
82
STATISTIC(SearchLimitReached, "Number of times the limit to "
83
                              "decompose GEPs is reached");
84
STATISTIC(SearchTimes, "Number of times a GEP is decomposed");
85
86
/// Cutoff after which to stop analysing a set of phi nodes potentially involved
87
/// in a cycle. Because we are analysing 'through' phi nodes, we need to be
88
/// careful with value equivalence. We use reachability to make sure a value
89
/// cannot be involved in a cycle.
90
const unsigned MaxNumPhiBBsValueReachabilityCheck = 20;
91
92
// The max limit of the search depth in DecomposeGEPExpression() and
93
// GetUnderlyingObject(), both functions need to use the same search
94
// depth otherwise the algorithm in aliasGEP will assert.
95
static const unsigned MaxLookupSearchDepth = 6;
96
97
bool BasicAAResult::invalidate(Function &Fn, const PreservedAnalyses &PA,
98
3.32k
                               FunctionAnalysisManager::Invalidator &Inv) {
99
3.32k
  // We don't care if this analysis itself is preserved, it has no state. But
100
3.32k
  // we need to check that the analyses it depends on have been. Note that we
101
3.32k
  // may be created without handles to some analyses and in that case don't
102
3.32k
  // depend on them.
103
3.32k
  if (Inv.invalidate<AssumptionAnalysis>(Fn, PA) ||
104
3.32k
      (DT && Inv.invalidate<DominatorTreeAnalysis>(Fn, PA)) ||
105
3.32k
      
(1.89k
LI1.89k
&&
Inv.invalidate<LoopAnalysis>(Fn, PA)113
) ||
106
3.32k
      
(1.89k
PV1.89k
&&
Inv.invalidate<PhiValuesAnalysis>(Fn, PA)1
))
107
1.43k
    return true;
108
1.89k
109
1.89k
  // Otherwise this analysis result remains valid.
110
1.89k
  return false;
111
1.89k
}
112
113
//===----------------------------------------------------------------------===//
114
// Useful predicates
115
//===----------------------------------------------------------------------===//
116
117
/// Returns true if the pointer is to a function-local object that never
118
/// escapes from the function.
119
static bool isNonEscapingLocalObject(
120
    const Value *V,
121
63.1M
    SmallDenseMap<const Value *, bool, 8> *IsCapturedCache = nullptr) {
122
63.1M
  SmallDenseMap<const Value *, bool, 8>::iterator CacheIt;
123
63.1M
  if (IsCapturedCache) {
124
63.1M
    bool Inserted;
125
63.1M
    std::tie(CacheIt, Inserted) = IsCapturedCache->insert({V, false});
126
63.1M
    if (!Inserted)
127
34.6M
      // Found cached result, return it!
128
34.6M
      return CacheIt->second;
129
28.5M
  }
130
28.5M
131
28.5M
  // If this is a local allocation, check to see if it escapes.
132
28.5M
  if (isa<AllocaInst>(V) || 
isNoAliasCall(V)25.4M
) {
133
3.51M
    // Set StoreCaptures to True so that we can assume in our callers that the
134
3.51M
    // pointer is not the result of a load instruction. Currently
135
3.51M
    // PointerMayBeCaptured doesn't have any special analysis for the
136
3.51M
    // StoreCaptures=false case; if it did, our callers could be refined to be
137
3.51M
    // more precise.
138
3.51M
    auto Ret = !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true);
139
3.51M
    if (IsCapturedCache)
140
3.51M
      CacheIt->second = Ret;
141
3.51M
    return Ret;
142
3.51M
  }
143
25.0M
144
25.0M
  // If this is an argument that corresponds to a byval or noalias argument,
145
25.0M
  // then it has not escaped before entering the function.  Check if it escapes
146
25.0M
  // inside the function.
147
25.0M
  if (const Argument *A = dyn_cast<Argument>(V))
148
7.06M
    if (A->hasByValAttr() || 
A->hasNoAliasAttr()7.06M
) {
149
52.6k
      // Note even if the argument is marked nocapture, we still need to check
150
52.6k
      // for copies made inside the function. The nocapture attribute only
151
52.6k
      // specifies that there are no copies made that outlive the function.
152
52.6k
      auto Ret = !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true);
153
52.6k
      if (IsCapturedCache)
154
52.6k
        CacheIt->second = Ret;
155
52.6k
      return Ret;
156
52.6k
    }
157
24.9M
158
24.9M
  return false;
159
24.9M
}
160
161
/// Returns true if the pointer is one which would have been considered an
162
/// escape by isNonEscapingLocalObject.
163
84.1M
static bool isEscapeSource(const Value *V) {
164
84.1M
  if (isa<CallBase>(V))
165
3.95M
    return true;
166
80.1M
167
80.1M
  if (isa<Argument>(V))
168
16.1M
    return true;
169
64.0M
170
64.0M
  // The load case works because isNonEscapingLocalObject considers all
171
64.0M
  // stores to be escapes (it passes true for the StoreCaptures argument
172
64.0M
  // to PointerMayBeCaptured).
173
64.0M
  if (isa<LoadInst>(V))
174
36.4M
    return true;
175
27.5M
176
27.5M
  return false;
177
27.5M
}
178
179
/// Returns the size of the object specified by V or UnknownSize if unknown.
180
static uint64_t getObjectSize(const Value *V, const DataLayout &DL,
181
                              const TargetLibraryInfo &TLI,
182
                              bool NullIsValidLoc,
183
28.7M
                              bool RoundToAlign = false) {
184
28.7M
  uint64_t Size;
185
28.7M
  ObjectSizeOpts Opts;
186
28.7M
  Opts.RoundToAlign = RoundToAlign;
187
28.7M
  Opts.NullIsUnknownSize = NullIsValidLoc;
188
28.7M
  if (getObjectSize(V, Size, DL, &TLI, Opts))
189
13.2M
    return Size;
190
15.4M
  return MemoryLocation::UnknownSize;
191
15.4M
}
192
193
/// Returns true if we can prove that the object specified by V is smaller than
194
/// Size.
195
static bool isObjectSmallerThan(const Value *V, uint64_t Size,
196
                                const DataLayout &DL,
197
                                const TargetLibraryInfo &TLI,
198
85.0M
                                bool NullIsValidLoc) {
199
85.0M
  // Note that the meanings of the "object" are slightly different in the
200
85.0M
  // following contexts:
201
85.0M
  //    c1: llvm::getObjectSize()
202
85.0M
  //    c2: llvm.objectsize() intrinsic
203
85.0M
  //    c3: isObjectSmallerThan()
204
85.0M
  // c1 and c2 share the same meaning; however, the meaning of "object" in c3
205
85.0M
  // refers to the "entire object".
206
85.0M
  //
207
85.0M
  //  Consider this example:
208
85.0M
  //     char *p = (char*)malloc(100)
209
85.0M
  //     char *q = p+80;
210
85.0M
  //
211
85.0M
  //  In the context of c1 and c2, the "object" pointed by q refers to the
212
85.0M
  // stretch of memory of q[0:19]. So, getObjectSize(q) should return 20.
213
85.0M
  //
214
85.0M
  //  However, in the context of c3, the "object" refers to the chunk of memory
215
85.0M
  // being allocated. So, the "object" has 100 bytes, and q points to the middle
216
85.0M
  // the "object". In case q is passed to isObjectSmallerThan() as the 1st
217
85.0M
  // parameter, before the llvm::getObjectSize() is called to get the size of
218
85.0M
  // entire object, we should:
219
85.0M
  //    - either rewind the pointer q to the base-address of the object in
220
85.0M
  //      question (in this case rewind to p), or
221
85.0M
  //    - just give up. It is up to caller to make sure the pointer is pointing
222
85.0M
  //      to the base address the object.
223
85.0M
  //
224
85.0M
  // We go for 2nd option for simplicity.
225
85.0M
  if (!isIdentifiedObject(V))
226
57.4M
    return false;
227
27.6M
228
27.6M
  // This function needs to use the aligned object size because we allow
229
27.6M
  // reads a bit past the end given sufficient alignment.
230
27.6M
  uint64_t ObjectSize = getObjectSize(V, DL, TLI, NullIsValidLoc,
231
27.6M
                                      /*RoundToAlign*/ true);
232
27.6M
233
27.6M
  return ObjectSize != MemoryLocation::UnknownSize && 
ObjectSize < Size13.1M
;
234
27.6M
}
235
236
/// Returns true if we can prove that the object specified by V has size Size.
237
static bool isObjectSize(const Value *V, uint64_t Size, const DataLayout &DL,
238
1.03M
                         const TargetLibraryInfo &TLI, bool NullIsValidLoc) {
239
1.03M
  uint64_t ObjectSize = getObjectSize(V, DL, TLI, NullIsValidLoc);
240
1.03M
  return ObjectSize != MemoryLocation::UnknownSize && 
ObjectSize == Size139k
;
241
1.03M
}
242
243
//===----------------------------------------------------------------------===//
244
// GetElementPtr Instruction Decomposition and Analysis
245
//===----------------------------------------------------------------------===//
246
247
/// Analyzes the specified value as a linear expression: "A*V + B", where A and
248
/// B are constant integers.
249
///
250
/// Returns the scale and offset values as APInts and return V as a Value*, and
251
/// return whether we looked through any sign or zero extends.  The incoming
252
/// Value is known to have IntegerType, and it may already be sign or zero
253
/// extended.
254
///
255
/// Note that this looks through extends, so the high bits may not be
256
/// represented in the result.
257
/*static*/ const Value *BasicAAResult::GetLinearExpression(
258
    const Value *V, APInt &Scale, APInt &Offset, unsigned &ZExtBits,
259
    unsigned &SExtBits, const DataLayout &DL, unsigned Depth,
260
30.9M
    AssumptionCache *AC, DominatorTree *DT, bool &NSW, bool &NUW) {
261
30.9M
  assert(V->getType()->isIntegerTy() && "Not an integer value");
262
30.9M
263
30.9M
  // Limit our recursion depth.
264
30.9M
  if (Depth == 6) {
265
4.37k
    Scale = 1;
266
4.37k
    Offset = 0;
267
4.37k
    return V;
268
4.37k
  }
269
30.9M
270
30.9M
  if (const ConstantInt *Const = dyn_cast<ConstantInt>(V)) {
271
321
    // If it's a constant, just convert it to an offset and remove the variable.
272
321
    // If we've been called recursively, the Offset bit width will be greater
273
321
    // than the constant's (the Offset's always as wide as the outermost call),
274
321
    // so we'll zext here and process any extension in the isa<SExtInst> &
275
321
    // isa<ZExtInst> cases below.
276
321
    Offset += Const->getValue().zextOrSelf(Offset.getBitWidth());
277
321
    assert(Scale == 0 && "Constant values don't have a scale");
278
321
    return V;
279
321
  }
280
30.9M
281
30.9M
  if (const BinaryOperator *BOp = dyn_cast<BinaryOperator>(V)) {
282
6.06M
    if (ConstantInt *RHSC = dyn_cast<ConstantInt>(BOp->getOperand(1))) {
283
3.86M
      // If we've been called recursively, then Offset and Scale will be wider
284
3.86M
      // than the BOp operands. We'll always zext it here as we'll process sign
285
3.86M
      // extensions below (see the isa<SExtInst> / isa<ZExtInst> cases).
286
3.86M
      APInt RHS = RHSC->getValue().zextOrSelf(Offset.getBitWidth());
287
3.86M
288
3.86M
      switch (BOp->getOpcode()) {
289
3.86M
      default:
290
943k
        // We don't understand this instruction, so we can't decompose it any
291
943k
        // further.
292
943k
        Scale = 1;
293
943k
        Offset = 0;
294
943k
        return V;
295
3.86M
      case Instruction::Or:
296
529k
        // X|C == X+C if all the bits in C are unset in X.  Otherwise we can't
297
529k
        // analyze it.
298
529k
        if (!MaskedValueIsZero(BOp->getOperand(0), RHSC->getValue(), DL, 0, AC,
299
529k
                               BOp, DT)) {
300
994
          Scale = 1;
301
994
          Offset = 0;
302
994
          return V;
303
994
        }
304
528k
        LLVM_FALLTHROUGH;
305
2.19M
      case Instruction::Add:
306
2.19M
        V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits,
307
2.19M
                                SExtBits, DL, Depth + 1, AC, DT, NSW, NUW);
308
2.19M
        Offset += RHS;
309
2.19M
        break;
310
528k
      case Instruction::Sub:
311
1.31k
        V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits,
312
1.31k
                                SExtBits, DL, Depth + 1, AC, DT, NSW, NUW);
313
1.31k
        Offset -= RHS;
314
1.31k
        break;
315
528k
      case Instruction::Mul:
316
98.6k
        V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits,
317
98.6k
                                SExtBits, DL, Depth + 1, AC, DT, NSW, NUW);
318
98.6k
        Offset *= RHS;
319
98.6k
        Scale *= RHS;
320
98.6k
        break;
321
625k
      case Instruction::Shl:
322
625k
        V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits,
323
625k
                                SExtBits, DL, Depth + 1, AC, DT, NSW, NUW);
324
625k
325
625k
        // We're trying to linearize an expression of the kind:
326
625k
        //   shl i8 -128, 36
327
625k
        // where the shift count exceeds the bitwidth of the type.
328
625k
        // We can't decompose this further (the expression would return
329
625k
        // a poison value).
330
625k
        if (Offset.getBitWidth() < RHS.getLimitedValue() ||
331
625k
            
Scale.getBitWidth() < RHS.getLimitedValue()625k
) {
332
1
          Scale = 1;
333
1
          Offset = 0;
334
1
          return V;
335
1
        }
336
625k
337
625k
        Offset <<= RHS.getLimitedValue();
338
625k
        Scale <<= RHS.getLimitedValue();
339
625k
        // the semantics of nsw and nuw for left shifts don't match those of
340
625k
        // multiplications, so we won't propagate them.
341
625k
        NSW = NUW = false;
342
625k
        return V;
343
2.29M
      }
344
2.29M
345
2.29M
      if (isa<OverflowingBinaryOperator>(BOp)) {
346
1.76M
        NUW &= BOp->hasNoUnsignedWrap();
347
1.76M
        NSW &= BOp->hasNoSignedWrap();
348
1.76M
      }
349
2.29M
      return V;
350
2.29M
    }
351
6.06M
  }
352
27.1M
353
27.1M
  // Since GEP indices are sign extended anyway, we don't care about the high
354
27.1M
  // bits of a sign or zero extended value - just scales and offsets.  The
355
27.1M
  // extensions have to be consistent though.
356
27.1M
  if (isa<SExtInst>(V) || 
isa<ZExtInst>(V)23.4M
) {
357
5.12M
    Value *CastOp = cast<CastInst>(V)->getOperand(0);
358
5.12M
    unsigned NewWidth = V->getType()->getPrimitiveSizeInBits();
359
5.12M
    unsigned SmallWidth = CastOp->getType()->getPrimitiveSizeInBits();
360
5.12M
    unsigned OldZExtBits = ZExtBits, OldSExtBits = SExtBits;
361
5.12M
    const Value *Result =
362
5.12M
        GetLinearExpression(CastOp, Scale, Offset, ZExtBits, SExtBits, DL,
363
5.12M
                            Depth + 1, AC, DT, NSW, NUW);
364
5.12M
365
5.12M
    // zext(zext(%x)) == zext(%x), and similarly for sext; we'll handle this
366
5.12M
    // by just incrementing the number of bits we've extended by.
367
5.12M
    unsigned ExtendedBy = NewWidth - SmallWidth;
368
5.12M
369
5.12M
    if (isa<SExtInst>(V) && 
ZExtBits == 03.66M
) {
370
3.66M
      // sext(sext(%x, a), b) == sext(%x, a + b)
371
3.66M
372
3.66M
      if (NSW) {
373
3.38M
        // We haven't sign-wrapped, so it's valid to decompose sext(%x + c)
374
3.38M
        // into sext(%x) + sext(c). We'll sext the Offset ourselves:
375
3.38M
        unsigned OldWidth = Offset.getBitWidth();
376
3.38M
        Offset = Offset.trunc(SmallWidth).sext(NewWidth).zextOrSelf(OldWidth);
377
3.38M
      } else {
378
284k
        // We may have signed-wrapped, so don't decompose sext(%x + c) into
379
284k
        // sext(%x) + sext(c)
380
284k
        Scale = 1;
381
284k
        Offset = 0;
382
284k
        Result = CastOp;
383
284k
        ZExtBits = OldZExtBits;
384
284k
        SExtBits = OldSExtBits;
385
284k
      }
386
3.66M
      SExtBits += ExtendedBy;
387
3.66M
    } else {
388
1.46M
      // sext(zext(%x, a), b) = zext(zext(%x, a), b) = zext(%x, a + b)
389
1.46M
390
1.46M
      if (!NUW) {
391
74.4k
        // We may have unsigned-wrapped, so don't decompose zext(%x + c) into
392
74.4k
        // zext(%x) + zext(c)
393
74.4k
        Scale = 1;
394
74.4k
        Offset = 0;
395
74.4k
        Result = CastOp;
396
74.4k
        ZExtBits = OldZExtBits;
397
74.4k
        SExtBits = OldSExtBits;
398
74.4k
      }
399
1.46M
      ZExtBits += ExtendedBy;
400
1.46M
    }
401
5.12M
402
5.12M
    return Result;
403
5.12M
  }
404
21.9M
405
21.9M
  Scale = 1;
406
21.9M
  Offset = 0;
407
21.9M
  return V;
408
21.9M
}
409
410
/// To ensure a pointer offset fits in an integer of size PointerSize
411
/// (in bits) when that size is smaller than the maximum pointer size. This is
412
/// an issue, for example, in particular for 32b pointers with negative indices
413
/// that rely on two's complement wrap-arounds for precise alias information
414
/// where the maximum pointer size is 64b.
415
132M
static APInt adjustToPointerSize(APInt Offset, unsigned PointerSize) {
416
132M
  assert(PointerSize <= Offset.getBitWidth() && "Invalid PointerSize!");
417
132M
  unsigned ShiftBits = Offset.getBitWidth() - PointerSize;
418
132M
  return (Offset << ShiftBits).ashr(ShiftBits);
419
132M
}
420
421
109M
static unsigned getMaxPointerSize(const DataLayout &DL) {
422
109M
  unsigned MaxPointerSize = DL.getMaxPointerSizeInBits();
423
109M
  if (MaxPointerSize < 64 && 
ForceAtLeast64Bits1.64M
)
MaxPointerSize = 641.64M
;
424
109M
  if (DoubleCalcBits) 
MaxPointerSize *= 20
;
425
109M
426
109M
  return MaxPointerSize;
427
109M
}
428
429
/// If V is a symbolic pointer expression, decompose it into a base pointer
430
/// with a constant offset and a number of scaled symbolic offsets.
431
///
432
/// The scaled symbolic offsets (represented by pairs of a Value* and a scale
433
/// in the VarIndices vector) are Value*'s that are known to be scaled by the
434
/// specified amount, but which may have other unrepresented high bits. As
435
/// such, the gep cannot necessarily be reconstructed from its decomposed form.
436
///
437
/// When DataLayout is around, this function is capable of analyzing everything
438
/// that GetUnderlyingObject can look through. To be able to do that
439
/// GetUnderlyingObject and DecomposeGEPExpression must use the same search
440
/// depth (MaxLookupSearchDepth). When DataLayout not is around, it just looks
441
/// through pointer casts.
442
bool BasicAAResult::DecomposeGEPExpression(const Value *V,
443
       DecomposedGEP &Decomposed, const DataLayout &DL, AssumptionCache *AC,
444
73.2M
       DominatorTree *DT) {
445
73.2M
  // Limit recursion depth to limit compile time in crazy cases.
446
73.2M
  unsigned MaxLookup = MaxLookupSearchDepth;
447
73.2M
  SearchTimes++;
448
73.2M
449
73.2M
  unsigned MaxPointerSize = getMaxPointerSize(DL);
450
73.2M
  Decomposed.VarIndices.clear();
451
160M
  do {
452
160M
    // See if this is a bitcast or GEP.
453
160M
    const Operator *Op = dyn_cast<Operator>(V);
454
160M
    if (!Op) {
455
28.6M
      // The only non-operator case we can handle are GlobalAliases.
456
28.6M
      if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
457
0
        if (!GA->isInterposable()) {
458
0
          V = GA->getAliasee();
459
0
          continue;
460
0
        }
461
28.6M
      }
462
28.6M
      Decomposed.Base = V;
463
28.6M
      return false;
464
28.6M
    }
465
132M
466
132M
    if (Op->getOpcode() == Instruction::BitCast ||
467
132M
        
Op->getOpcode() == Instruction::AddrSpaceCast121M
) {
468
10.7M
      V = Op->getOperand(0);
469
10.7M
      continue;
470
10.7M
    }
471
121M
472
121M
    const GEPOperator *GEPOp = dyn_cast<GEPOperator>(Op);
473
121M
    if (!GEPOp) {
474
44.4M
      if (const auto *Call = dyn_cast<CallBase>(V)) {
475
2.37M
        // CaptureTracking can know about special capturing properties of some
476
2.37M
        // intrinsics like launder.invariant.group, that can't be expressed with
477
2.37M
        // the attributes, but have properties like returning aliasing pointer.
478
2.37M
        // Because some analysis may assume that nocaptured pointer is not
479
2.37M
        // returned from some special intrinsic (because function would have to
480
2.37M
        // be marked with returns attribute), it is crucial to use this function
481
2.37M
        // because it should be in sync with CaptureTracking. Not using it may
482
2.37M
        // cause weird miscompilations where 2 aliasing pointers are assumed to
483
2.37M
        // noalias.
484
2.37M
        if (auto *RP = getArgumentAliasingToReturnedPointer(Call)) {
485
1.03k
          V = RP;
486
1.03k
          continue;
487
1.03k
        }
488
44.4M
      }
489
44.4M
490
44.4M
      // If it's not a GEP, hand it off to SimplifyInstruction to see if it
491
44.4M
      // can come up with something. This matches what GetUnderlyingObject does.
492
44.4M
      if (const Instruction *I = dyn_cast<Instruction>(V))
493
44.4M
        // TODO: Get a DominatorTree and AssumptionCache and use them here
494
44.4M
        // (these are both now available in this function, but this should be
495
44.4M
        // updated when GetUnderlyingObject is updated). TLI should be
496
44.4M
        // provided also.
497
44.4M
        if (const Value *Simplified =
498
123k
                SimplifyInstruction(const_cast<Instruction *>(I), DL)) {
499
123k
          V = Simplified;
500
123k
          continue;
501
123k
        }
502
44.3M
503
44.3M
      Decomposed.Base = V;
504
44.3M
      return false;
505
44.3M
    }
506
76.7M
507
76.7M
    // Don't attempt to analyze GEPs over unsized objects.
508
76.7M
    if (!GEPOp->getSourceElementType()->isSized()) {
509
0
      Decomposed.Base = V;
510
0
      return false;
511
0
    }
512
76.7M
513
76.7M
    unsigned AS = GEPOp->getPointerAddressSpace();
514
76.7M
    // Walk the indices of the GEP, accumulating them into BaseOff/VarIndices.
515
76.7M
    gep_type_iterator GTI = gep_type_begin(GEPOp);
516
76.7M
    unsigned PointerSize = DL.getPointerSizeInBits(AS);
517
76.7M
    // Assume all GEP operands are constants until proven otherwise.
518
76.7M
    bool GepHasConstantOffset = true;
519
76.7M
    for (User::const_op_iterator I = GEPOp->op_begin() + 1, E = GEPOp->op_end();
520
264M
         I != E; 
++I, ++GTI187M
) {
521
187M
      const Value *Index = *I;
522
187M
      // Compute the (potentially symbolic) offset in bytes for this index.
523
187M
      if (StructType *STy = GTI.getStructTypeOrNull()) {
524
63.5M
        // For a struct, add the member offset.
525
63.5M
        unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue();
526
63.5M
        if (FieldNo == 0)
527
18.1M
          continue;
528
45.4M
529
45.4M
        Decomposed.StructOffset +=
530
45.4M
          DL.getStructLayout(STy)->getElementOffset(FieldNo);
531
45.4M
        continue;
532
45.4M
      }
533
123M
534
123M
      // For an array/pointer, add the element offset, explicitly scaled.
535
123M
      if (const ConstantInt *CIdx = dyn_cast<ConstantInt>(Index)) {
536
101M
        if (CIdx->isZero())
537
62.4M
          continue;
538
38.9M
        Decomposed.OtherOffset +=
539
38.9M
          (DL.getTypeAllocSize(GTI.getIndexedType()) *
540
38.9M
            CIdx->getValue().sextOrSelf(MaxPointerSize))
541
38.9M
              .sextOrTrunc(MaxPointerSize);
542
38.9M
        continue;
543
38.9M
      }
544
22.6M
545
22.6M
      GepHasConstantOffset = false;
546
22.6M
547
22.6M
      APInt Scale(MaxPointerSize, DL.getTypeAllocSize(GTI.getIndexedType()));
548
22.6M
      unsigned ZExtBits = 0, SExtBits = 0;
549
22.6M
550
22.6M
      // If the integer type is smaller than the pointer size, it is implicitly
551
22.6M
      // sign extended to pointer size.
552
22.6M
      unsigned Width = Index->getType()->getIntegerBitWidth();
553
22.6M
      if (PointerSize > Width)
554
1.14k
        SExtBits += PointerSize - Width;
555
22.6M
556
22.6M
      // Use GetLinearExpression to decompose the index into a C1*V+C2 form.
557
22.6M
      APInt IndexScale(Width, 0), IndexOffset(Width, 0);
558
22.6M
      bool NSW = true, NUW = true;
559
22.6M
      const Value *OrigIndex = Index;
560
22.6M
      Index = GetLinearExpression(Index, IndexScale, IndexOffset, ZExtBits,
561
22.6M
                                  SExtBits, DL, 0, AC, DT, NSW, NUW);
562
22.6M
563
22.6M
      // The GEP index scale ("Scale") scales C1*V+C2, yielding (C1*V+C2)*Scale.
564
22.6M
      // This gives us an aggregate computation of (C1*Scale)*V + C2*Scale.
565
22.6M
566
22.6M
      // It can be the case that, even through C1*V+C2 does not overflow for
567
22.6M
      // relevant values of V, (C2*Scale) can overflow. In that case, we cannot
568
22.6M
      // decompose the expression in this way.
569
22.6M
      //
570
22.6M
      // FIXME: C1*Scale and the other operations in the decomposed
571
22.6M
      // (C1*Scale)*V+C2*Scale can also overflow. We should check for this
572
22.6M
      // possibility.
573
22.6M
      APInt WideScaledOffset = IndexOffset.sextOrTrunc(MaxPointerSize*2) *
574
22.6M
                                 Scale.sext(MaxPointerSize*2);
575
22.6M
      if (WideScaledOffset.getMinSignedBits() > MaxPointerSize) {
576
4
        Index = OrigIndex;
577
4
        IndexScale = 1;
578
4
        IndexOffset = 0;
579
4
580
4
        ZExtBits = SExtBits = 0;
581
4
        if (PointerSize > Width)
582
0
          SExtBits += PointerSize - Width;
583
22.6M
      } else {
584
22.6M
        Decomposed.OtherOffset += IndexOffset.sextOrTrunc(MaxPointerSize) * Scale;
585
22.6M
        Scale *= IndexScale.sextOrTrunc(MaxPointerSize);
586
22.6M
      }
587
22.6M
588
22.6M
      // If we already had an occurrence of this index variable, merge this
589
22.6M
      // scale into it.  For example, we want to handle:
590
22.6M
      //   A[x][x] -> x*16 + x*4 -> x*20
591
22.6M
      // This also ensures that 'x' only appears in the index list once.
592
24.1M
      for (unsigned i = 0, e = Decomposed.VarIndices.size(); i != e; 
++i1.48M
) {
593
1.56M
        if (Decomposed.VarIndices[i].V == Index &&
594
1.56M
            
Decomposed.VarIndices[i].ZExtBits == ZExtBits76.8k
&&
595
1.56M
            
Decomposed.VarIndices[i].SExtBits == SExtBits76.8k
) {
596
76.8k
          Scale += Decomposed.VarIndices[i].Scale;
597
76.8k
          Decomposed.VarIndices.erase(Decomposed.VarIndices.begin() + i);
598
76.8k
          break;
599
76.8k
        }
600
1.56M
      }
601
22.6M
602
22.6M
      // Make sure that we have a scale that makes sense for this target's
603
22.6M
      // pointer size.
604
22.6M
      Scale = adjustToPointerSize(Scale, PointerSize);
605
22.6M
606
22.6M
      if (!!Scale) {
607
22.6M
        VariableGEPIndex Entry = {Index, ZExtBits, SExtBits, Scale};
608
22.6M
        Decomposed.VarIndices.push_back(Entry);
609
22.6M
      }
610
22.6M
    }
611
76.7M
612
76.7M
    // Take care of wrap-arounds
613
76.7M
    if (GepHasConstantOffset) {
614
54.8M
      Decomposed.StructOffset =
615
54.8M
          adjustToPointerSize(Decomposed.StructOffset, PointerSize);
616
54.8M
      Decomposed.OtherOffset =
617
54.8M
          adjustToPointerSize(Decomposed.OtherOffset, PointerSize);
618
54.8M
    }
619
76.7M
620
76.7M
    // Analyze the base pointer next.
621
76.7M
    V = GEPOp->getOperand(0);
622
87.6M
  } while (--MaxLookup);
623
73.2M
624
73.2M
  // If the chain of expressions is too deep, just return early.
625
73.2M
  Decomposed.Base = V;
626
223k
  SearchLimitReached++;
627
223k
  return true;
628
73.2M
}
629
630
/// Returns whether the given pointer value points to memory that is local to
631
/// the function, with global constants being considered local to all
632
/// functions.
633
bool BasicAAResult::pointsToConstantMemory(const MemoryLocation &Loc,
634
37.7M
                                           AAQueryInfo &AAQI, bool OrLocal) {
635
37.7M
  assert(Visited.empty() && "Visited must be cleared after use!");
636
37.7M
637
37.7M
  unsigned MaxLookup = 8;
638
37.7M
  SmallVector<const Value *, 16> Worklist;
639
37.7M
  Worklist.push_back(Loc.Ptr);
640
43.1M
  do {
641
43.1M
    const Value *V = GetUnderlyingObject(Worklist.pop_back_val(), DL);
642
43.1M
    if (!Visited.insert(V).second) {
643
809k
      Visited.clear();
644
809k
      return AAResultBase::pointsToConstantMemory(Loc, AAQI, OrLocal);
645
809k
    }
646
42.3M
647
42.3M
    // An alloca instruction defines local memory.
648
42.3M
    if (OrLocal && 
isa<AllocaInst>(V)1.56M
)
649
424k
      continue;
650
41.9M
651
41.9M
    // A global constant counts as local memory for our purposes.
652
41.9M
    if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) {
653
5.93M
      // Note: this doesn't require GV to be "ODR" because it isn't legal for a
654
5.93M
      // global to be marked constant in some modules and non-constant in
655
5.93M
      // others.  GV may even be a declaration, not a definition.
656
5.93M
      if (!GV->isConstant()) {
657
5.80M
        Visited.clear();
658
5.80M
        return AAResultBase::pointsToConstantMemory(Loc, AAQI, OrLocal);
659
5.80M
      }
660
130k
      continue;
661
130k
    }
662
35.9M
663
35.9M
    // If both select values point to local memory, then so does the select.
664
35.9M
    if (const SelectInst *SI = dyn_cast<SelectInst>(V)) {
665
119k
      Worklist.push_back(SI->getTrueValue());
666
119k
      Worklist.push_back(SI->getFalseValue());
667
119k
      continue;
668
119k
    }
669
35.8M
670
35.8M
    // If all values incoming to a phi node point to local memory, then so does
671
35.8M
    // the phi.
672
35.8M
    if (const PHINode *PN = dyn_cast<PHINode>(V)) {
673
5.34M
      // Don't bother inspecting phi nodes with many operands.
674
5.34M
      if (PN->getNumIncomingValues() > MaxLookup) {
675
50.4k
        Visited.clear();
676
50.4k
        return AAResultBase::pointsToConstantMemory(Loc, AAQI, OrLocal);
677
50.4k
      }
678
5.29M
      for (Value *IncValue : PN->incoming_values())
679
11.1M
        Worklist.push_back(IncValue);
680
5.29M
      continue;
681
5.29M
    }
682
30.5M
683
30.5M
    // Otherwise be conservative.
684
30.5M
    Visited.clear();
685
30.5M
    return AAResultBase::pointsToConstantMemory(Loc, AAQI, OrLocal);
686
30.5M
  } while (
!Worklist.empty()5.97M
&&
--MaxLookup5.43M
);
687
37.7M
688
37.7M
  Visited.clear();
689
537k
  return Worklist.empty();
690
37.7M
}
691
692
/// Returns the behavior when calling the given call site.
693
17.7M
FunctionModRefBehavior BasicAAResult::getModRefBehavior(const CallBase *Call) {
694
17.7M
  if (Call->doesNotAccessMemory())
695
268k
    // Can't do better than this.
696
268k
    return FMRB_DoesNotAccessMemory;
697
17.4M
698
17.4M
  FunctionModRefBehavior Min = FMRB_UnknownModRefBehavior;
699
17.4M
700
17.4M
  // If the callsite knows it only reads memory, don't return worse
701
17.4M
  // than that.
702
17.4M
  if (Call->onlyReadsMemory())
703
336k
    Min = FMRB_OnlyReadsMemory;
704
17.1M
  else if (Call->doesNotReadMemory())
705
856
    Min = FMRB_DoesNotReadMemory;
706
17.4M
707
17.4M
  if (Call->onlyAccessesArgMemory())
708
2.20M
    Min = FunctionModRefBehavior(Min & FMRB_OnlyAccessesArgumentPointees);
709
15.2M
  else if (Call->onlyAccessesInaccessibleMemory())
710
437
    Min = FunctionModRefBehavior(Min & FMRB_OnlyAccessesInaccessibleMem);
711
15.2M
  else if (Call->onlyAccessesInaccessibleMemOrArgMem())
712
5.58k
    Min = FunctionModRefBehavior(Min & FMRB_OnlyAccessesInaccessibleOrArgMem);
713
17.4M
714
17.4M
  // If the call has operand bundles then aliasing attributes from the function
715
17.4M
  // it calls do not directly apply to the call.  This can be made more precise
716
17.4M
  // in the future.
717
17.4M
  if (!Call->hasOperandBundles())
718
17.4M
    if (const Function *F = Call->getCalledFunction())
719
16.3M
      Min =
720
16.3M
          FunctionModRefBehavior(Min & getBestAAResults().getModRefBehavior(F));
721
17.4M
722
17.4M
  return Min;
723
17.4M
}
724
725
/// Returns the behavior when calling the given function. For use when the call
726
/// site is not known.
727
17.0M
FunctionModRefBehavior BasicAAResult::getModRefBehavior(const Function *F) {
728
17.0M
  // If the function declares it doesn't access memory, we can't do better.
729
17.0M
  if (F->doesNotAccessMemory())
730
8.13k
    return FMRB_DoesNotAccessMemory;
731
17.0M
732
17.0M
  FunctionModRefBehavior Min = FMRB_UnknownModRefBehavior;
733
17.0M
734
17.0M
  // If the function declares it only reads memory, go with that.
735
17.0M
  if (F->onlyReadsMemory())
736
343k
    Min = FMRB_OnlyReadsMemory;
737
16.6M
  else if (F->doesNotReadMemory())
738
871
    Min = FMRB_DoesNotReadMemory;
739
17.0M
740
17.0M
  if (F->onlyAccessesArgMemory())
741
2.21M
    Min = FunctionModRefBehavior(Min & FMRB_OnlyAccessesArgumentPointees);
742
14.7M
  else if (F->onlyAccessesInaccessibleMemory())
743
468
    Min = FunctionModRefBehavior(Min & FMRB_OnlyAccessesInaccessibleMem);
744
14.7M
  else if (F->onlyAccessesInaccessibleMemOrArgMem())
745
5.60k
    Min = FunctionModRefBehavior(Min & FMRB_OnlyAccessesInaccessibleOrArgMem);
746
17.0M
747
17.0M
  return Min;
748
17.0M
}
749
750
/// Returns true if this is a writeonly (i.e Mod only) parameter.
751
static bool isWriteOnlyParam(const CallBase *Call, unsigned ArgIdx,
752
564k
                             const TargetLibraryInfo &TLI) {
753
564k
  if (Call->paramHasAttr(ArgIdx, Attribute::WriteOnly))
754
227k
    return true;
755
336k
756
336k
  // We can bound the aliasing properties of memset_pattern16 just as we can
757
336k
  // for memcpy/memset.  This is particularly important because the
758
336k
  // LoopIdiomRecognizer likes to turn loops into calls to memset_pattern16
759
336k
  // whenever possible.
760
336k
  // FIXME Consider handling this in InferFunctionAttr.cpp together with other
761
336k
  // attributes.
762
336k
  LibFunc F;
763
336k
  if (Call->getCalledFunction() &&
764
336k
      TLI.getLibFunc(*Call->getCalledFunction(), F) &&
765
336k
      
F == LibFunc_memset_pattern1626.1k
&&
TLI.has(F)5.48k
)
766
5.48k
    if (ArgIdx == 0)
767
2.81k
      return true;
768
334k
769
334k
  // TODO: memset_pattern4, memset_pattern8
770
334k
  // TODO: _chk variants
771
334k
  // TODO: strcmp, strcpy
772
334k
773
334k
  return false;
774
334k
}
775
776
ModRefInfo BasicAAResult::getArgModRefInfo(const CallBase *Call,
777
564k
                                           unsigned ArgIdx) {
778
564k
  // Checking for known builtin intrinsics and target library functions.
779
564k
  if (isWriteOnlyParam(Call, ArgIdx, TLI))
780
230k
    return ModRefInfo::Mod;
781
334k
782
334k
  if (Call->paramHasAttr(ArgIdx, Attribute::ReadOnly))
783
163k
    return ModRefInfo::Ref;
784
170k
785
170k
  if (Call->paramHasAttr(ArgIdx, Attribute::ReadNone))
786
1
    return ModRefInfo::NoModRef;
787
170k
788
170k
  return AAResultBase::getArgModRefInfo(Call, ArgIdx);
789
170k
}
790
791
26.5M
static bool isIntrinsicCall(const CallBase *Call, Intrinsic::ID IID) {
792
26.5M
  const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Call);
793
26.5M
  return II && 
II->getIntrinsicID() == IID3.33M
;
794
26.5M
}
795
796
#ifndef NDEBUG
797
static const Function *getParent(const Value *V) {
798
  if (const Instruction *inst = dyn_cast<Instruction>(V)) {
799
    if (!inst->getParent())
800
      return nullptr;
801
    return inst->getParent()->getParent();
802
  }
803
804
  if (const Argument *arg = dyn_cast<Argument>(V))
805
    return arg->getParent();
806
807
  return nullptr;
808
}
809
810
static bool notDifferentParent(const Value *O1, const Value *O2) {
811
812
  const Function *F1 = getParent(O1);
813
  const Function *F2 = getParent(O2);
814
815
  return !F1 || !F2 || F1 == F2;
816
}
817
#endif
818
819
AliasResult BasicAAResult::alias(const MemoryLocation &LocA,
820
                                 const MemoryLocation &LocB,
821
81.3M
                                 AAQueryInfo &AAQI) {
822
81.3M
  assert(notDifferentParent(LocA.Ptr, LocB.Ptr) &&
823
81.3M
         "BasicAliasAnalysis doesn't support interprocedural queries.");
824
81.3M
825
81.3M
  // If we have a directly cached entry for these locations, we have recursed
826
81.3M
  // through this once, so just return the cached results. Notably, when this
827
81.3M
  // happens, we don't clear the cache.
828
81.3M
  auto CacheIt = AAQI.AliasCache.find(AAQueryInfo::LocPair(LocA, LocB));
829
81.3M
  if (CacheIt != AAQI.AliasCache.end())
830
36.6M
    return CacheIt->second;
831
44.6M
832
44.6M
  CacheIt = AAQI.AliasCache.find(AAQueryInfo::LocPair(LocB, LocA));
833
44.6M
  if (CacheIt != AAQI.AliasCache.end())
834
157k
    return CacheIt->second;
835
44.5M
836
44.5M
  AliasResult Alias = aliasCheck(LocA.Ptr, LocA.Size, LocA.AATags, LocB.Ptr,
837
44.5M
                                 LocB.Size, LocB.AATags, AAQI);
838
44.5M
839
44.5M
  VisitedPhiBBs.clear();
840
44.5M
  return Alias;
841
44.5M
}
842
843
/// Checks to see if the specified callsite can clobber the specified memory
844
/// object.
845
///
846
/// Since we only look at local properties of this function, we really can't
847
/// say much about this query.  We do, however, use simple "address taken"
848
/// analysis on local objects.
849
ModRefInfo BasicAAResult::getModRefInfo(const CallBase *Call,
850
                                        const MemoryLocation &Loc,
851
8.60M
                                        AAQueryInfo &AAQI) {
852
8.60M
  assert(notDifferentParent(Call, Loc.Ptr) &&
853
8.60M
         "AliasAnalysis query involving multiple functions!");
854
8.60M
855
8.60M
  const Value *Object = GetUnderlyingObject(Loc.Ptr, DL);
856
8.60M
857
8.60M
  // Calls marked 'tail' cannot read or write allocas from the current frame
858
8.60M
  // because the current frame might be destroyed by the time they run. However,
859
8.60M
  // a tail call may use an alloca with byval. Calling with byval copies the
860
8.60M
  // contents of the alloca into argument registers or stack slots, so there is
861
8.60M
  // no lifetime issue.
862
8.60M
  if (isa<AllocaInst>(Object))
863
1.83M
    if (const CallInst *CI = dyn_cast<CallInst>(Call))
864
1.68M
      if (CI->isTailCall() &&
865
1.68M
          
!CI->getAttributes().hasAttrSomewhere(Attribute::ByVal)175k
)
866
175k
        return ModRefInfo::NoModRef;
867
8.42M
868
8.42M
  // Stack restore is able to modify unescaped dynamic allocas. Assume it may
869
8.42M
  // modify them even though the alloca is not escaped.
870
8.42M
  if (auto *AI = dyn_cast<AllocaInst>(Object))
871
1.65M
    if (!AI->isStaticAlloca() && 
isIntrinsicCall(Call, Intrinsic::stackrestore)992
)
872
15
      return ModRefInfo::Mod;
873
8.42M
874
8.42M
  // If the pointer is to a locally allocated object that does not escape,
875
8.42M
  // then the call can not mod/ref the pointer unless the call takes the pointer
876
8.42M
  // as an argument, and itself doesn't capture it.
877
8.42M
  if (!isa<Constant>(Object) && 
Call != Object6.97M
&&
878
8.42M
      
isNonEscapingLocalObject(Object, &AAQI.IsCapturedCache)6.58M
) {
879
376k
880
376k
    // Optimistically assume that call doesn't touch Object and check this
881
376k
    // assumption in the following loop.
882
376k
    ModRefInfo Result = ModRefInfo::NoModRef;
883
376k
    bool IsMustAlias = true;
884
376k
885
376k
    unsigned OperandNo = 0;
886
376k
    for (auto CI = Call->data_operands_begin(), CE = Call->data_operands_end();
887
1.11M
         CI != CE; 
++CI, ++OperandNo735k
) {
888
829k
      // Only look at the no-capture or byval pointer arguments.  If this
889
829k
      // pointer were passed to arguments that were neither of these, then it
890
829k
      // couldn't be no-capture.
891
829k
      if (!(*CI)->getType()->isPointerTy() ||
892
829k
          
(455k
!Call->doesNotCapture(OperandNo)455k
&&
893
455k
           
OperandNo < Call->getNumArgOperands()231k
&&
894
455k
           
!Call->isByValArgument(OperandNo)231k
))
895
605k
        continue;
896
224k
897
224k
      // Call doesn't access memory through this operand, so we don't care
898
224k
      // if it aliases with Object.
899
224k
      if (Call->doesNotAccessMemory(OperandNo))
900
939
        continue;
901
223k
902
223k
      // If this is a no-capture pointer argument, see if we can tell that it
903
223k
      // is impossible to alias the pointer we're checking.
904
223k
      AliasResult AR = getBestAAResults().alias(MemoryLocation(*CI),
905
223k
                                                MemoryLocation(Object), AAQI);
906
223k
      if (AR != MustAlias)
907
113k
        IsMustAlias = false;
908
223k
      // Operand doesn't alias 'Object', continue looking for other aliases
909
223k
      if (AR == NoAlias)
910
106k
        continue;
911
116k
      // Operand aliases 'Object', but call doesn't modify it. Strengthen
912
116k
      // initial assumption and keep looking in case if there are more aliases.
913
116k
      if (Call->onlyReadsMemory(OperandNo)) {
914
10.1k
        Result = setRef(Result);
915
10.1k
        continue;
916
10.1k
      }
917
106k
      // Operand aliases 'Object' but call only writes into it.
918
106k
      if (Call->doesNotReadMemory(OperandNo)) {
919
12.8k
        Result = setMod(Result);
920
12.8k
        continue;
921
12.8k
      }
922
93.8k
      // This operand aliases 'Object' and call reads and writes into it.
923
93.8k
      // Setting ModRef will not yield an early return below, MustAlias is not
924
93.8k
      // used further.
925
93.8k
      Result = ModRefInfo::ModRef;
926
93.8k
      break;
927
93.8k
    }
928
376k
929
376k
    // No operand aliases, reset Must bit. Add below if at least one aliases
930
376k
    // and all aliases found are MustAlias.
931
376k
    if (isNoModRef(Result))
932
259k
      IsMustAlias = false;
933
376k
934
376k
    // Early return if we improved mod ref information
935
376k
    if (!isModAndRefSet(Result)) {
936
282k
      if (isNoModRef(Result))
937
259k
        return ModRefInfo::NoModRef;
938
22.2k
      return IsMustAlias ? 
setMust(Result)8.09k
:
clearMust(Result)14.1k
;
939
22.2k
    }
940
376k
  }
941
8.14M
942
8.14M
  // If the call is to malloc or calloc, we can assume that it doesn't
943
8.14M
  // modify any IR visible value.  This is only valid because we assume these
944
8.14M
  // routines do not read values visible in the IR.  TODO: Consider special
945
8.14M
  // casing realloc and strdup routines which access only their arguments as
946
8.14M
  // well.  Or alternatively, replace all of this with inaccessiblememonly once
947
8.14M
  // that's implemented fully.
948
8.14M
  if (isMallocOrCallocLikeFn(Call, &TLI)) {
949
149k
    // Be conservative if the accessed pointer may alias the allocation -
950
149k
    // fallback to the generic handling below.
951
149k
    if (getBestAAResults().alias(MemoryLocation(Call), Loc, AAQI) == NoAlias)
952
128k
      return ModRefInfo::NoModRef;
953
8.01M
  }
954
8.01M
955
8.01M
  // The semantics of memcpy intrinsics forbid overlap between their respective
956
8.01M
  // operands, i.e., source and destination of any given memcpy must no-alias.
957
8.01M
  // If Loc must-aliases either one of these two locations, then it necessarily
958
8.01M
  // no-aliases the other.
959
8.01M
  if (auto *Inst = dyn_cast<AnyMemCpyInst>(Call)) {
960
263k
    AliasResult SrcAA, DestAA;
961
263k
962
263k
    if ((SrcAA = getBestAAResults().alias(MemoryLocation::getForSource(Inst),
963
263k
                                          Loc, AAQI)) == MustAlias)
964
8.97k
      // Loc is exactly the memcpy source thus disjoint from memcpy dest.
965
8.97k
      return ModRefInfo::Ref;
966
254k
    if ((DestAA = getBestAAResults().alias(MemoryLocation::getForDest(Inst),
967
254k
                                           Loc, AAQI)) == MustAlias)
968
10.3k
      // The converse case.
969
10.3k
      return ModRefInfo::Mod;
970
243k
971
243k
    // It's also possible for Loc to alias both src and dest, or neither.
972
243k
    ModRefInfo rv = ModRefInfo::NoModRef;
973
243k
    if (SrcAA != NoAlias)
974
113k
      rv = setRef(rv);
975
243k
    if (DestAA != NoAlias)
976
84.8k
      rv = setMod(rv);
977
243k
    return rv;
978
243k
  }
979
7.75M
980
7.75M
  // While the assume intrinsic is marked as arbitrarily writing so that
981
7.75M
  // proper control dependencies will be maintained, it never aliases any
982
7.75M
  // particular memory location.
983
7.75M
  if (isIntrinsicCall(Call, Intrinsic::assume))
984
176
    return ModRefInfo::NoModRef;
985
7.75M
986
7.75M
  // Like assumes, guard intrinsics are also marked as arbitrarily writing so
987
7.75M
  // that proper control dependencies are maintained but they never mods any
988
7.75M
  // particular memory location.
989
7.75M
  //
990
7.75M
  // *Unlike* assumes, guard intrinsics are modeled as reading memory since the
991
7.75M
  // heap state at the point the guard is issued needs to be consistent in case
992
7.75M
  // the guard invokes the "deopt" continuation.
993
7.75M
  if (isIntrinsicCall(Call, Intrinsic::experimental_guard))
994
125
    return ModRefInfo::Ref;
995
7.75M
996
7.75M
  // Like assumes, invariant.start intrinsics were also marked as arbitrarily
997
7.75M
  // writing so that proper control dependencies are maintained but they never
998
7.75M
  // mod any particular memory location visible to the IR.
999
7.75M
  // *Unlike* assumes (which are now modeled as NoModRef), invariant.start
1000
7.75M
  // intrinsic is now modeled as reading memory. This prevents hoisting the
1001
7.75M
  // invariant.start intrinsic over stores. Consider:
1002
7.75M
  // *ptr = 40;
1003
7.75M
  // *ptr = 50;
1004
7.75M
  // invariant_start(ptr)
1005
7.75M
  // int val = *ptr;
1006
7.75M
  // print(val);
1007
7.75M
  //
1008
7.75M
  // This cannot be transformed to:
1009
7.75M
  //
1010
7.75M
  // *ptr = 40;
1011
7.75M
  // invariant_start(ptr)
1012
7.75M
  // *ptr = 50;
1013
7.75M
  // int val = *ptr;
1014
7.75M
  // print(val);
1015
7.75M
  //
1016
7.75M
  // The transformation will cause the second store to be ignored (based on
1017
7.75M
  // rules of invariant.start)  and print 40, while the first program always
1018
7.75M
  // prints 50.
1019
7.75M
  if (isIntrinsicCall(Call, Intrinsic::invariant_start))
1020
64
    return ModRefInfo::Ref;
1021
7.75M
1022
7.75M
  // The AAResultBase base class has some smarts, lets use them.
1023
7.75M
  return AAResultBase::getModRefInfo(Call, Loc, AAQI);
1024
7.75M
}
1025
1026
ModRefInfo BasicAAResult::getModRefInfo(const CallBase *Call1,
1027
                                        const CallBase *Call2,
1028
818k
                                        AAQueryInfo &AAQI) {
1029
818k
  // While the assume intrinsic is marked as arbitrarily writing so that
1030
818k
  // proper control dependencies will be maintained, it never aliases any
1031
818k
  // particular memory location.
1032
818k
  if (isIntrinsicCall(Call1, Intrinsic::assume) ||
1033
818k
      
isIntrinsicCall(Call2, Intrinsic::assume)818k
)
1034
2
    return ModRefInfo::NoModRef;
1035
818k
1036
818k
  // Like assumes, guard intrinsics are also marked as arbitrarily writing so
1037
818k
  // that proper control dependencies are maintained but they never mod any
1038
818k
  // particular memory location.
1039
818k
  //
1040
818k
  // *Unlike* assumes, guard intrinsics are modeled as reading memory since the
1041
818k
  // heap state at the point the guard is issued needs to be consistent in case
1042
818k
  // the guard invokes the "deopt" continuation.
1043
818k
1044
818k
  // NB! This function is *not* commutative, so we special case two
1045
818k
  // possibilities for guard intrinsics.
1046
818k
1047
818k
  if (isIntrinsicCall(Call1, Intrinsic::experimental_guard))
1048
40
    return isModSet(createModRefInfo(getModRefBehavior(Call2)))
1049
40
               ? 
ModRefInfo::Ref39
1050
40
               : 
ModRefInfo::NoModRef1
;
1051
818k
1052
818k
  if (isIntrinsicCall(Call2, Intrinsic::experimental_guard))
1053
2
    return isModSet(createModRefInfo(getModRefBehavior(Call1)))
1054
2
               ? 
ModRefInfo::Mod1
1055
2
               : 
ModRefInfo::NoModRef1
;
1056
818k
1057
818k
  // The AAResultBase base class has some smarts, lets use them.
1058
818k
  return AAResultBase::getModRefInfo(Call1, Call2, AAQI);
1059
818k
}
1060
1061
/// Provide ad-hoc rules to disambiguate accesses through two GEP operators,
1062
/// both having the exact same pointer operand.
1063
static AliasResult aliasSameBasePointerGEPs(const GEPOperator *GEP1,
1064
                                            LocationSize MaybeV1Size,
1065
                                            const GEPOperator *GEP2,
1066
                                            LocationSize MaybeV2Size,
1067
13.5M
                                            const DataLayout &DL) {
1068
13.5M
  assert(GEP1->getPointerOperand()->stripPointerCastsAndInvariantGroups() ==
1069
13.5M
             GEP2->getPointerOperand()->stripPointerCastsAndInvariantGroups() &&
1070
13.5M
         GEP1->getPointerOperandType() == GEP2->getPointerOperandType() &&
1071
13.5M
         "Expected GEPs with the same pointer operand");
1072
13.5M
1073
13.5M
  // Try to determine whether GEP1 and GEP2 index through arrays, into structs,
1074
13.5M
  // such that the struct field accesses provably cannot alias.
1075
13.5M
  // We also need at least two indices (the pointer, and the struct field).
1076
13.5M
  if (GEP1->getNumIndices() != GEP2->getNumIndices() ||
1077
13.5M
      
GEP1->getNumIndices() < 212.4M
)
1078
4.98M
    return MayAlias;
1079
8.58M
1080
8.58M
  // If we don't know the size of the accesses through both GEPs, we can't
1081
8.58M
  // determine whether the struct fields accessed can't alias.
1082
8.58M
  if (MaybeV1Size == LocationSize::unknown() ||
1083
8.58M
      
MaybeV2Size == LocationSize::unknown()8.56M
)
1084
21.9k
    return MayAlias;
1085
8.55M
1086
8.55M
  const uint64_t V1Size = MaybeV1Size.getValue();
1087
8.55M
  const uint64_t V2Size = MaybeV2Size.getValue();
1088
8.55M
1089
8.55M
  ConstantInt *C1 =
1090
8.55M
      dyn_cast<ConstantInt>(GEP1->getOperand(GEP1->getNumOperands() - 1));
1091
8.55M
  ConstantInt *C2 =
1092
8.55M
      dyn_cast<ConstantInt>(GEP2->getOperand(GEP2->getNumOperands() - 1));
1093
8.55M
1094
8.55M
  // If the last (struct) indices are constants and are equal, the other indices
1095
8.55M
  // might be also be dynamically equal, so the GEPs can alias.
1096
8.55M
  if (C1 && 
C28.36M
) {
1097
8.34M
    unsigned BitWidth = std::max(C1->getBitWidth(), C2->getBitWidth());
1098
8.34M
    if (C1->getValue().sextOrSelf(BitWidth) ==
1099
8.34M
        C2->getValue().sextOrSelf(BitWidth))
1100
471k
      return MayAlias;
1101
8.08M
  }
1102
8.08M
1103
8.08M
  // Find the last-indexed type of the GEP, i.e., the type you'd get if
1104
8.08M
  // you stripped the last index.
1105
8.08M
  // On the way, look at each indexed type.  If there's something other
1106
8.08M
  // than an array, different indices can lead to different final types.
1107
8.08M
  SmallVector<Value *, 8> IntermediateIndices;
1108
8.08M
1109
8.08M
  // Insert the first index; we don't need to check the type indexed
1110
8.08M
  // through it as it only drops the pointer indirection.
1111
8.08M
  assert(GEP1->getNumIndices() > 1 && "Not enough GEP indices to examine");
1112
8.08M
  IntermediateIndices.push_back(GEP1->getOperand(1));
1113
8.08M
1114
8.08M
  // Insert all the remaining indices but the last one.
1115
8.08M
  // Also, check that they all index through arrays.
1116
8.34M
  for (unsigned i = 1, e = GEP1->getNumIndices() - 1; i != e; 
++i260k
) {
1117
1.56M
    if (!isa<ArrayType>(GetElementPtrInst::getIndexedType(
1118
1.56M
            GEP1->getSourceElementType(), IntermediateIndices)))
1119
1.29M
      return MayAlias;
1120
260k
    IntermediateIndices.push_back(GEP1->getOperand(i + 1));
1121
260k
  }
1122
8.08M
1123
8.08M
  auto *Ty = GetElementPtrInst::getIndexedType(
1124
6.78M
    GEP1->getSourceElementType(), IntermediateIndices);
1125
6.78M
  StructType *LastIndexedStruct = dyn_cast<StructType>(Ty);
1126
6.78M
1127
6.78M
  if (isa<SequentialType>(Ty)) {
1128
5.01M
    // We know that:
1129
5.01M
    // - both GEPs begin indexing from the exact same pointer;
1130
5.01M
    // - the last indices in both GEPs are constants, indexing into a sequential
1131
5.01M
    //   type (array or pointer);
1132
5.01M
    // - both GEPs only index through arrays prior to that.
1133
5.01M
    //
1134
5.01M
    // Because array indices greater than the number of elements are valid in
1135
5.01M
    // GEPs, unless we know the intermediate indices are identical between
1136
5.01M
    // GEP1 and GEP2 we cannot guarantee that the last indexed arrays don't
1137
5.01M
    // partially overlap. We also need to check that the loaded size matches
1138
5.01M
    // the element size, otherwise we could still have overlap.
1139
5.01M
    const uint64_t ElementSize =
1140
5.01M
        DL.getTypeStoreSize(cast<SequentialType>(Ty)->getElementType());
1141
5.01M
    if (V1Size != ElementSize || 
V2Size != ElementSize232k
)
1142
4.78M
      return MayAlias;
1143
226k
1144
567k
    
for (unsigned i = 0, e = GEP1->getNumIndices() - 1; 226k
i != e;
++i341k
)
1145
402k
      if (GEP1->getOperand(i + 1) != GEP2->getOperand(i + 1))
1146
61.3k
        return MayAlias;
1147
226k
1148
226k
    // Now we know that the array/pointer that GEP1 indexes into and that
1149
226k
    // that GEP2 indexes into must either precisely overlap or be disjoint.
1150
226k
    // Because they cannot partially overlap and because fields in an array
1151
226k
    // cannot overlap, if we can prove the final indices are different between
1152
226k
    // GEP1 and GEP2, we can conclude GEP1 and GEP2 don't alias.
1153
226k
1154
226k
    // If the last indices are constants, we've already checked they don't
1155
226k
    // equal each other so we can exit early.
1156
226k
    
if (164k
C1164k
&&
C2120k
)
1157
116k
      return NoAlias;
1158
48.8k
    {
1159
48.8k
      Value *GEP1LastIdx = GEP1->getOperand(GEP1->getNumOperands() - 1);
1160
48.8k
      Value *GEP2LastIdx = GEP2->getOperand(GEP2->getNumOperands() - 1);
1161
48.8k
      if (isa<PHINode>(GEP1LastIdx) || 
isa<PHINode>(GEP2LastIdx)41.3k
) {
1162
10.8k
        // If one of the indices is a PHI node, be safe and only use
1163
10.8k
        // computeKnownBits so we don't make any assumptions about the
1164
10.8k
        // relationships between the two indices. This is important if we're
1165
10.8k
        // asking about values from different loop iterations. See PR32314.
1166
10.8k
        // TODO: We may be able to change the check so we only do this when
1167
10.8k
        // we definitely looked through a PHINode.
1168
10.8k
        if (GEP1LastIdx != GEP2LastIdx &&
1169
10.8k
            
GEP1LastIdx->getType() == GEP2LastIdx->getType()10.3k
) {
1170
10.3k
          KnownBits Known1 = computeKnownBits(GEP1LastIdx, DL);
1171
10.3k
          KnownBits Known2 = computeKnownBits(GEP2LastIdx, DL);
1172
10.3k
          if (Known1.Zero.intersects(Known2.One) ||
1173
10.3k
              
Known1.One.intersects(Known2.Zero)9.79k
)
1174
705
            return NoAlias;
1175
37.9k
        }
1176
37.9k
      } else if (isKnownNonEqual(GEP1LastIdx, GEP2LastIdx, DL))
1177
2.81k
        return NoAlias;
1178
45.3k
    }
1179
45.3k
    return MayAlias;
1180
1.77M
  } else if (!LastIndexedStruct || !C1 || !C2) {
1181
0
    return MayAlias;
1182
0
  }
1183
1.77M
1184
1.77M
  if (C1->getValue().getActiveBits() > 64 ||
1185
1.77M
      C2->getValue().getActiveBits() > 64)
1186
0
    return MayAlias;
1187
1.77M
1188
1.77M
  // We know that:
1189
1.77M
  // - both GEPs begin indexing from the exact same pointer;
1190
1.77M
  // - the last indices in both GEPs are constants, indexing into a struct;
1191
1.77M
  // - said indices are different, hence, the pointed-to fields are different;
1192
1.77M
  // - both GEPs only index through arrays prior to that.
1193
1.77M
  //
1194
1.77M
  // This lets us determine that the struct that GEP1 indexes into and the
1195
1.77M
  // struct that GEP2 indexes into must either precisely overlap or be
1196
1.77M
  // completely disjoint.  Because they cannot partially overlap, indexing into
1197
1.77M
  // different non-overlapping fields of the struct will never alias.
1198
1.77M
1199
1.77M
  // Therefore, the only remaining thing needed to show that both GEPs can't
1200
1.77M
  // alias is that the fields are not overlapping.
1201
1.77M
  const StructLayout *SL = DL.getStructLayout(LastIndexedStruct);
1202
1.77M
  const uint64_t StructSize = SL->getSizeInBytes();
1203
1.77M
  const uint64_t V1Off = SL->getElementOffset(C1->getZExtValue());
1204
1.77M
  const uint64_t V2Off = SL->getElementOffset(C2->getZExtValue());
1205
1.77M
1206
1.77M
  auto EltsDontOverlap = [StructSize](uint64_t V1Off, uint64_t V1Size,
1207
2.61M
                                      uint64_t V2Off, uint64_t V2Size) {
1208
2.61M
    return V1Off < V2Off && 
V1Off + V1Size <= V2Off1.77M
&&
1209
2.61M
           
(1.76M
(V2Off + V2Size <= StructSize)1.76M
||
1210
1.76M
            
(V2Off + V2Size - StructSize <= V1Off)36
);
1211
2.61M
  };
1212
1.77M
1213
1.77M
  if (EltsDontOverlap(V1Off, V1Size, V2Off, V2Size) ||
1214
1.77M
      
EltsDontOverlap(V2Off, V2Size, V1Off, V1Size)842k
)
1215
1.76M
    return NoAlias;
1216
10.1k
1217
10.1k
  return MayAlias;
1218
10.1k
}
1219
1220
// If a we have (a) a GEP and (b) a pointer based on an alloca, and the
1221
// beginning of the object the GEP points would have a negative offset with
1222
// repsect to the alloca, that means the GEP can not alias pointer (b).
1223
// Note that the pointer based on the alloca may not be a GEP. For
1224
// example, it may be the alloca itself.
1225
// The same applies if (b) is based on a GlobalVariable. Note that just being
1226
// based on isIdentifiedObject() is not enough - we need an identified object
1227
// that does not permit access to negative offsets. For example, a negative
1228
// offset from a noalias argument or call can be inbounds w.r.t the actual
1229
// underlying object.
1230
//
1231
// For example, consider:
1232
//
1233
//   struct { int f0, int f1, ...} foo;
1234
//   foo alloca;
1235
//   foo* random = bar(alloca);
1236
//   int *f0 = &alloca.f0
1237
//   int *f1 = &random->f1;
1238
//
1239
// Which is lowered, approximately, to:
1240
//
1241
//  %alloca = alloca %struct.foo
1242
//  %random = call %struct.foo* @random(%struct.foo* %alloca)
1243
//  %f0 = getelementptr inbounds %struct, %struct.foo* %alloca, i32 0, i32 0
1244
//  %f1 = getelementptr inbounds %struct, %struct.foo* %random, i32 0, i32 1
1245
//
1246
// Assume %f1 and %f0 alias. Then %f1 would point into the object allocated
1247
// by %alloca. Since the %f1 GEP is inbounds, that means %random must also
1248
// point into the same object. But since %f0 points to the beginning of %alloca,
1249
// the highest %f1 can be is (%alloca + 3). This means %random can not be higher
1250
// than (%alloca - 1), and so is not inbounds, a contradiction.
1251
bool BasicAAResult::isGEPBaseAtNegativeOffset(const GEPOperator *GEPOp,
1252
      const DecomposedGEP &DecompGEP, const DecomposedGEP &DecompObject,
1253
63.5M
      LocationSize MaybeObjectAccessSize) {
1254
63.5M
  // If the object access size is unknown, or the GEP isn't inbounds, bail.
1255
63.5M
  if (MaybeObjectAccessSize == LocationSize::unknown() || 
!GEPOp->isInBounds()60.8M
)
1256
10.7M
    return false;
1257
52.7M
1258
52.7M
  const uint64_t ObjectAccessSize = MaybeObjectAccessSize.getValue();
1259
52.7M
1260
52.7M
  // We need the object to be an alloca or a globalvariable, and want to know
1261
52.7M
  // the offset of the pointer from the object precisely, so no variable
1262
52.7M
  // indices are allowed.
1263
52.7M
  if (!(isa<AllocaInst>(DecompObject.Base) ||
1264
52.7M
        
isa<GlobalVariable>(DecompObject.Base)43.7M
) ||
1265
52.7M
      
!DecompObject.VarIndices.empty()21.5M
)
1266
41.1M
    return false;
1267
11.5M
1268
11.5M
  APInt ObjectBaseOffset = DecompObject.StructOffset +
1269
11.5M
                           DecompObject.OtherOffset;
1270
11.5M
1271
11.5M
  // If the GEP has no variable indices, we know the precise offset
1272
11.5M
  // from the base, then use it. If the GEP has variable indices,
1273
11.5M
  // we can't get exact GEP offset to identify pointer alias. So return
1274
11.5M
  // false in that case.
1275
11.5M
  if (!DecompGEP.VarIndices.empty())
1276
878k
    return false;
1277
10.7M
1278
10.7M
  APInt GEPBaseOffset = DecompGEP.StructOffset;
1279
10.7M
  GEPBaseOffset += DecompGEP.OtherOffset;
1280
10.7M
1281
10.7M
  return GEPBaseOffset.sge(ObjectBaseOffset + (int64_t)ObjectAccessSize);
1282
10.7M
}
1283
1284
/// Provides a bunch of ad-hoc rules to disambiguate a GEP instruction against
1285
/// another pointer.
1286
///
1287
/// We know that V1 is a GEP, but we don't know anything about V2.
1288
/// UnderlyingV1 is GetUnderlyingObject(GEP1, DL), UnderlyingV2 is the same for
1289
/// V2.
1290
AliasResult BasicAAResult::aliasGEP(
1291
    const GEPOperator *GEP1, LocationSize V1Size, const AAMDNodes &V1AAInfo,
1292
    const Value *V2, LocationSize V2Size, const AAMDNodes &V2AAInfo,
1293
36.6M
    const Value *UnderlyingV1, const Value *UnderlyingV2, AAQueryInfo &AAQI) {
1294
36.6M
  DecomposedGEP DecompGEP1, DecompGEP2;
1295
36.6M
  unsigned MaxPointerSize = getMaxPointerSize(DL);
1296
36.6M
  DecompGEP1.StructOffset = DecompGEP1.OtherOffset = APInt(MaxPointerSize, 0);
1297
36.6M
  DecompGEP2.StructOffset = DecompGEP2.OtherOffset = APInt(MaxPointerSize, 0);
1298
36.6M
1299
36.6M
  bool GEP1MaxLookupReached =
1300
36.6M
    DecomposeGEPExpression(GEP1, DecompGEP1, DL, &AC, DT);
1301
36.6M
  bool GEP2MaxLookupReached =
1302
36.6M
    DecomposeGEPExpression(V2, DecompGEP2, DL, &AC, DT);
1303
36.6M
1304
36.6M
  APInt GEP1BaseOffset = DecompGEP1.StructOffset + DecompGEP1.OtherOffset;
1305
36.6M
  APInt GEP2BaseOffset = DecompGEP2.StructOffset + DecompGEP2.OtherOffset;
1306
36.6M
1307
36.6M
  assert(DecompGEP1.Base == UnderlyingV1 && DecompGEP2.Base == UnderlyingV2 &&
1308
36.6M
         "DecomposeGEPExpression returned a result different from "
1309
36.6M
         "GetUnderlyingObject");
1310
36.6M
1311
36.6M
  // If the GEP's offset relative to its base is such that the base would
1312
36.6M
  // fall below the start of the object underlying V2, then the GEP and V2
1313
36.6M
  // cannot alias.
1314
36.6M
  if (!GEP1MaxLookupReached && 
!GEP2MaxLookupReached36.4M
&&
1315
36.6M
      
isGEPBaseAtNegativeOffset(GEP1, DecompGEP1, DecompGEP2, V2Size)36.4M
)
1316
2.06M
    return NoAlias;
1317
34.5M
  // If we have two gep instructions with must-alias or not-alias'ing base
1318
34.5M
  // pointers, figure out if the indexes to the GEP tell us anything about the
1319
34.5M
  // derived pointer.
1320
34.5M
  if (const GEPOperator *GEP2 = dyn_cast<GEPOperator>(V2)) {
1321
27.1M
    // Check for the GEP base being at a negative offset, this time in the other
1322
27.1M
    // direction.
1323
27.1M
    if (!GEP1MaxLookupReached && 
!GEP2MaxLookupReached27.1M
&&
1324
27.1M
        
isGEPBaseAtNegativeOffset(GEP2, DecompGEP2, DecompGEP1, V1Size)27.0M
)
1325
4.00M
      return NoAlias;
1326
23.1M
    // Do the base pointers alias?
1327
23.1M
    AliasResult BaseAlias =
1328
23.1M
        aliasCheck(UnderlyingV1, LocationSize::unknown(), AAMDNodes(),
1329
23.1M
                   UnderlyingV2, LocationSize::unknown(), AAMDNodes(), AAQI);
1330
23.1M
1331
23.1M
    // Check for geps of non-aliasing underlying pointers where the offsets are
1332
23.1M
    // identical.
1333
23.1M
    if ((BaseAlias == MayAlias) && 
V1Size == V2Size8.96M
) {
1334
5.01M
      // Do the base pointers alias assuming type and size.
1335
5.01M
      AliasResult PreciseBaseAlias = aliasCheck(
1336
5.01M
          UnderlyingV1, V1Size, V1AAInfo, UnderlyingV2, V2Size, V2AAInfo, AAQI);
1337
5.01M
      if (PreciseBaseAlias == NoAlias) {
1338
2.16M
        // See if the computed offset from the common pointer tells us about the
1339
2.16M
        // relation of the resulting pointer.
1340
2.16M
        // If the max search depth is reached the result is undefined
1341
2.16M
        if (GEP2MaxLookupReached || 
GEP1MaxLookupReached2.15M
)
1342
16.4k
          return MayAlias;
1343
2.14M
1344
2.14M
        // Same offsets.
1345
2.14M
        if (GEP1BaseOffset == GEP2BaseOffset &&
1346
2.14M
            
DecompGEP1.VarIndices == DecompGEP2.VarIndices337k
)
1347
188k
          return NoAlias;
1348
22.9M
      }
1349
5.01M
    }
1350
22.9M
1351
22.9M
    // If we get a No or May, then return it immediately, no amount of analysis
1352
22.9M
    // will improve this situation.
1353
22.9M
    if (BaseAlias != MustAlias) {
1354
9.07M
      assert(BaseAlias == NoAlias || BaseAlias == MayAlias);
1355
9.07M
      return BaseAlias;
1356
9.07M
    }
1357
13.9M
1358
13.9M
    // Otherwise, we have a MustAlias.  Since the base pointers alias each other
1359
13.9M
    // exactly, see if the computed offset from the common pointer tells us
1360
13.9M
    // about the relation of the resulting pointer.
1361
13.9M
    // If we know the two GEPs are based off of the exact same pointer (and not
1362
13.9M
    // just the same underlying object), see if that tells us anything about
1363
13.9M
    // the resulting pointers.
1364
13.9M
    if (GEP1->getPointerOperand()->stripPointerCastsAndInvariantGroups() ==
1365
13.9M
            GEP2->getPointerOperand()->stripPointerCastsAndInvariantGroups() &&
1366
13.9M
        
GEP1->getPointerOperandType() == GEP2->getPointerOperandType()13.6M
) {
1367
13.5M
      AliasResult R = aliasSameBasePointerGEPs(GEP1, V1Size, GEP2, V2Size, DL);
1368
13.5M
      // If we couldn't find anything interesting, don't abandon just yet.
1369
13.5M
      if (R != MayAlias)
1370
1.88M
        return R;
1371
12.0M
    }
1372
12.0M
1373
12.0M
    // If the max search depth is reached, the result is undefined
1374
12.0M
    if (GEP2MaxLookupReached || 
GEP1MaxLookupReached12.0M
)
1375
12.1k
      return MayAlias;
1376
12.0M
1377
12.0M
    // Subtract the GEP2 pointer from the GEP1 pointer to find out their
1378
12.0M
    // symbolic difference.
1379
12.0M
    GEP1BaseOffset -= GEP2BaseOffset;
1380
12.0M
    GetIndexDifference(DecompGEP1.VarIndices, DecompGEP2.VarIndices);
1381
12.0M
1382
12.0M
  } else {
1383
7.35M
    // Check to see if these two pointers are related by the getelementptr
1384
7.35M
    // instruction.  If one pointer is a GEP with a non-zero index of the other
1385
7.35M
    // pointer, we know they cannot alias.
1386
7.35M
1387
7.35M
    // If both accesses are unknown size, we can't do anything useful here.
1388
7.35M
    if (V1Size == LocationSize::unknown() && 
V2Size == LocationSize::unknown()1.33M
)
1389
1.32M
      return MayAlias;
1390
6.02M
1391
6.02M
    AliasResult R = aliasCheck(UnderlyingV1, LocationSize::unknown(),
1392
6.02M
                               AAMDNodes(), V2, LocationSize::unknown(),
1393
6.02M
                               V2AAInfo, AAQI, nullptr, UnderlyingV2);
1394
6.02M
    if (R != MustAlias) {
1395
4.86M
      // If V2 may alias GEP base pointer, conservatively returns MayAlias.
1396
4.86M
      // If V2 is known not to alias GEP base pointer, then the two values
1397
4.86M
      // cannot alias per GEP semantics: "Any memory access must be done through
1398
4.86M
      // a pointer value associated with an address range of the memory access,
1399
4.86M
      // otherwise the behavior is undefined.".
1400
4.86M
      assert(R == NoAlias || R == MayAlias);
1401
4.86M
      return R;
1402
4.86M
    }
1403
1.16M
1404
1.16M
    // If the max search depth is reached the result is undefined
1405
1.16M
    if (GEP1MaxLookupReached)
1406
659
      return MayAlias;
1407
13.1M
  }
1408
13.1M
1409
13.1M
  // In the two GEP Case, if there is no difference in the offsets of the
1410
13.1M
  // computed pointers, the resultant pointers are a must alias.  This
1411
13.1M
  // happens when we have two lexically identical GEP's (for example).
1412
13.1M
  //
1413
13.1M
  // In the other case, if we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2
1414
13.1M
  // must aliases the GEP, the end result is a must alias also.
1415
13.1M
  if (GEP1BaseOffset == 0 && 
DecompGEP1.VarIndices.empty()235k
)
1416
67.6k
    return MustAlias;
1417
13.1M
1418
13.1M
  // If there is a constant difference between the pointers, but the difference
1419
13.1M
  // is less than the size of the associated memory object, then we know
1420
13.1M
  // that the objects are partially overlapping.  If the difference is
1421
13.1M
  // greater, we know they do not overlap.
1422
13.1M
  if (GEP1BaseOffset != 0 && 
DecompGEP1.VarIndices.empty()12.9M
) {
1423
12.6M
    if (GEP1BaseOffset.sge(0)) {
1424
2.28M
      if (V2Size != LocationSize::unknown()) {
1425
2.11M
        if (GEP1BaseOffset.ult(V2Size.getValue()))
1426
71.4k
          return PartialAlias;
1427
2.03M
        return NoAlias;
1428
2.03M
      }
1429
10.3M
    } else {
1430
10.3M
      // We have the situation where:
1431
10.3M
      // +                +
1432
10.3M
      // | BaseOffset     |
1433
10.3M
      // ---------------->|
1434
10.3M
      // |-->V1Size       |-------> V2Size
1435
10.3M
      // GEP1             V2
1436
10.3M
      // We need to know that V2Size is not unknown, otherwise we might have
1437
10.3M
      // stripped a gep with negative index ('gep <ptr>, -1, ...).
1438
10.3M
      if (V1Size != LocationSize::unknown() &&
1439
10.3M
          
V2Size != LocationSize::unknown()10.2M
) {
1440
10.2M
        if ((-GEP1BaseOffset).ult(V1Size.getValue()))
1441
12.9k
          return PartialAlias;
1442
10.2M
        return NoAlias;
1443
10.2M
      }
1444
10.3M
    }
1445
12.6M
  }
1446
746k
1447
746k
  if (!DecompGEP1.VarIndices.empty()) {
1448
502k
    APInt Modulo(MaxPointerSize, 0);
1449
502k
    bool AllPositive = true;
1450
1.36M
    for (unsigned i = 0, e = DecompGEP1.VarIndices.size(); i != e; 
++i862k
) {
1451
862k
1452
862k
      // Try to distinguish something like &A[i][1] against &A[42][0].
1453
862k
      // Grab the least significant bit set in any of the scales. We
1454
862k
      // don't need std::abs here (even if the scale's negative) as we'll
1455
862k
      // be ^'ing Modulo with itself later.
1456
862k
      Modulo |= DecompGEP1.VarIndices[i].Scale;
1457
862k
1458
862k
      if (AllPositive) {
1459
605k
        // If the Value could change between cycles, then any reasoning about
1460
605k
        // the Value this cycle may not hold in the next cycle. We'll just
1461
605k
        // give up if we can't determine conditions that hold for every cycle:
1462
605k
        const Value *V = DecompGEP1.VarIndices[i].V;
1463
605k
1464
605k
        KnownBits Known = computeKnownBits(V, DL, 0, &AC, nullptr, DT);
1465
605k
        bool SignKnownZero = Known.isNonNegative();
1466
605k
        bool SignKnownOne = Known.isNegative();
1467
605k
1468
605k
        // Zero-extension widens the variable, and so forces the sign
1469
605k
        // bit to zero.
1470
605k
        bool IsZExt = DecompGEP1.VarIndices[i].ZExtBits > 0 || 
isa<ZExtInst>(V)467k
;
1471
605k
        SignKnownZero |= IsZExt;
1472
605k
        SignKnownOne &= !IsZExt;
1473
605k
1474
605k
        // If the variable begins with a zero then we know it's
1475
605k
        // positive, regardless of whether the value is signed or
1476
605k
        // unsigned.
1477
605k
        APInt Scale = DecompGEP1.VarIndices[i].Scale;
1478
605k
        AllPositive =
1479
605k
            (SignKnownZero && 
Scale.sge(0)281k
) ||
(424k
SignKnownOne424k
&&
Scale.slt(0)24
);
1480
605k
      }
1481
862k
    }
1482
502k
1483
502k
    Modulo = Modulo ^ (Modulo & (Modulo - 1));
1484
502k
1485
502k
    // We can compute the difference between the two addresses
1486
502k
    // mod Modulo. Check whether that difference guarantees that the
1487
502k
    // two locations do not alias.
1488
502k
    APInt ModOffset = GEP1BaseOffset & (Modulo - 1);
1489
502k
    if (V1Size != LocationSize::unknown() &&
1490
502k
        
V2Size != LocationSize::unknown()491k
&&
ModOffset.uge(V2Size.getValue())489k
&&
1491
502k
        
(Modulo - ModOffset).uge(V1Size.getValue())49.5k
)
1492
44.0k
      return NoAlias;
1493
458k
1494
458k
    // If we know all the variables are positive, then GEP1 >= GEP1BasePtr.
1495
458k
    // If GEP1BasePtr > V2 (GEP1BaseOffset > 0) then we know the pointers
1496
458k
    // don't alias if V2Size can fit in the gap between V2 and GEP1BasePtr.
1497
458k
    if (AllPositive && 
GEP1BaseOffset.sgt(0)67.7k
&&
1498
458k
        
V2Size != LocationSize::unknown()28.2k
&&
1499
458k
        
GEP1BaseOffset.uge(V2Size.getValue())28.0k
)
1500
27.7k
      return NoAlias;
1501
430k
1502
430k
    if (constantOffsetHeuristic(DecompGEP1.VarIndices, V1Size, V2Size,
1503
430k
                                GEP1BaseOffset, &AC, DT))
1504
5.30k
      return NoAlias;
1505
669k
  }
1506
669k
1507
669k
  // Statically, we can see that the base objects are the same, but the
1508
669k
  // pointers have dynamic offsets which we can't resolve. And none of our
1509
669k
  // little tricks above worked.
1510
669k
  return MayAlias;
1511
669k
}
1512
1513
2.72M
static AliasResult MergeAliasResults(AliasResult A, AliasResult B) {
1514
2.72M
  // If the results agree, take it.
1515
2.72M
  if (A == B)
1516
1.88M
    return A;
1517
841k
  // A mix of PartialAlias and MustAlias is PartialAlias.
1518
841k
  if ((A == PartialAlias && 
B == MustAlias65
) ||
1519
841k
      
(841k
B == PartialAlias841k
&&
A == MustAlias58
))
1520
4
    return PartialAlias;
1521
841k
  // Otherwise, we don't know anything.
1522
841k
  return MayAlias;
1523
841k
}
1524
1525
/// Provides a bunch of ad-hoc rules to disambiguate a Select instruction
1526
/// against another.
1527
AliasResult
1528
BasicAAResult::aliasSelect(const SelectInst *SI, LocationSize SISize,
1529
                           const AAMDNodes &SIAAInfo, const Value *V2,
1530
                           LocationSize V2Size, const AAMDNodes &V2AAInfo,
1531
350k
                           const Value *UnderV2, AAQueryInfo &AAQI) {
1532
350k
  // If the values are Selects with the same condition, we can do a more precise
1533
350k
  // check: just check for aliases between the values on corresponding arms.
1534
350k
  if (const SelectInst *SI2 = dyn_cast<SelectInst>(V2))
1535
8.18k
    if (SI->getCondition() == SI2->getCondition()) {
1536
5.89k
      AliasResult Alias =
1537
5.89k
          aliasCheck(SI->getTrueValue(), SISize, SIAAInfo, SI2->getTrueValue(),
1538
5.89k
                     V2Size, V2AAInfo, AAQI);
1539
5.89k
      if (Alias == MayAlias)
1540
5.08k
        return MayAlias;
1541
810
      AliasResult ThisAlias =
1542
810
          aliasCheck(SI->getFalseValue(), SISize, SIAAInfo,
1543
810
                     SI2->getFalseValue(), V2Size, V2AAInfo, AAQI);
1544
810
      return MergeAliasResults(ThisAlias, Alias);
1545
810
    }
1546
344k
1547
344k
  // If both arms of the Select node NoAlias or MustAlias V2, then returns
1548
344k
  // NoAlias / MustAlias. Otherwise, returns MayAlias.
1549
344k
  AliasResult Alias = aliasCheck(V2, V2Size, V2AAInfo, SI->getTrueValue(),
1550
344k
                                 SISize, SIAAInfo, AAQI, UnderV2);
1551
344k
  if (Alias == MayAlias)
1552
229k
    return MayAlias;
1553
115k
1554
115k
  AliasResult ThisAlias = aliasCheck(V2, V2Size, V2AAInfo, SI->getFalseValue(),
1555
115k
                                     SISize, SIAAInfo, AAQI, UnderV2);
1556
115k
  return MergeAliasResults(ThisAlias, Alias);
1557
115k
}
1558
1559
/// Provide a bunch of ad-hoc rules to disambiguate a PHI instruction against
1560
/// another.
1561
AliasResult BasicAAResult::aliasPHI(const PHINode *PN, LocationSize PNSize,
1562
                                    const AAMDNodes &PNAAInfo, const Value *V2,
1563
                                    LocationSize V2Size,
1564
                                    const AAMDNodes &V2AAInfo,
1565
7.45M
                                    const Value *UnderV2, AAQueryInfo &AAQI) {
1566
7.45M
  // Track phi nodes we have visited. We use this information when we determine
1567
7.45M
  // value equivalence.
1568
7.45M
  VisitedPhiBBs.insert(PN->getParent());
1569
7.45M
1570
7.45M
  // If the values are PHIs in the same block, we can do a more precise
1571
7.45M
  // as well as efficient check: just check for aliases between the values
1572
7.45M
  // on corresponding edges.
1573
7.45M
  if (const PHINode *PN2 = dyn_cast<PHINode>(V2))
1574
1.16M
    if (PN2->getParent() == PN->getParent()) {
1575
641k
      AAQueryInfo::LocPair Locs(MemoryLocation(PN, PNSize, PNAAInfo),
1576
641k
                                MemoryLocation(V2, V2Size, V2AAInfo));
1577
641k
      if (PN > V2)
1578
291k
        std::swap(Locs.first, Locs.second);
1579
641k
      // Analyse the PHIs' inputs under the assumption that the PHIs are
1580
641k
      // NoAlias.
1581
641k
      // If the PHIs are May/MustAlias there must be (recursively) an input
1582
641k
      // operand from outside the PHIs' cycle that is MayAlias/MustAlias or
1583
641k
      // there must be an operation on the PHIs within the PHIs' value cycle
1584
641k
      // that causes a MayAlias.
1585
641k
      // Pretend the phis do not alias.
1586
641k
      AliasResult Alias = NoAlias;
1587
641k
      AliasResult OrigAliasResult;
1588
641k
      {
1589
641k
        // Limited lifetime iterator invalidated by the aliasCheck call below.
1590
641k
        auto CacheIt = AAQI.AliasCache.find(Locs);
1591
641k
        assert((CacheIt != AAQI.AliasCache.end()) &&
1592
641k
               "There must exist an entry for the phi node");
1593
641k
        OrigAliasResult = CacheIt->second;
1594
641k
        CacheIt->second = NoAlias;
1595
641k
      }
1596
641k
1597
1.05M
      for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; 
++i418k
) {
1598
940k
        AliasResult ThisAlias =
1599
940k
            aliasCheck(PN->getIncomingValue(i), PNSize, PNAAInfo,
1600
940k
                       PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)),
1601
940k
                       V2Size, V2AAInfo, AAQI);
1602
940k
        Alias = MergeAliasResults(ThisAlias, Alias);
1603
940k
        if (Alias == MayAlias)
1604
521k
          break;
1605
940k
      }
1606
641k
1607
641k
      // Reset if speculation failed.
1608
641k
      if (Alias != NoAlias) {
1609
521k
        auto Pair =
1610
521k
            AAQI.AliasCache.insert(std::make_pair(Locs, OrigAliasResult));
1611
521k
        assert(!Pair.second && "Entry must have existed");
1612
521k
        Pair.first->second = OrigAliasResult;
1613
521k
      }
1614
641k
      return Alias;
1615
641k
    }
1616
6.81M
1617
6.81M
  SmallVector<Value *, 4> V1Srcs;
1618
6.81M
  bool isRecursive = false;
1619
6.81M
  if (PV)  {
1620
1.41M
    // If we have PhiValues then use it to get the underlying phi values.
1621
1.41M
    const PhiValues::ValueSet &PhiValueSet = PV->getValuesForPhi(PN);
1622
1.41M
    // If we have more phi values than the search depth then return MayAlias
1623
1.41M
    // conservatively to avoid compile time explosion. The worst possible case
1624
1.41M
    // is if both sides are PHI nodes. In which case, this is O(m x n) time
1625
1.41M
    // where 'm' and 'n' are the number of PHI sources.
1626
1.41M
    if (PhiValueSet.size() > MaxLookupSearchDepth)
1627
49.0k
      return MayAlias;
1628
1.36M
    // Add the values to V1Srcs
1629
3.32M
    
for (Value *PV1 : PhiValueSet)1.36M
{
1630
3.32M
      if (EnableRecPhiAnalysis) {
1631
0
        if (GEPOperator *PV1GEP = dyn_cast<GEPOperator>(PV1)) {
1632
0
          // Check whether the incoming value is a GEP that advances the pointer
1633
0
          // result of this PHI node (e.g. in a loop). If this is the case, we
1634
0
          // would recurse and always get a MayAlias. Handle this case specially
1635
0
          // below.
1636
0
          if (PV1GEP->getPointerOperand() == PN && PV1GEP->getNumIndices() == 1 &&
1637
0
              isa<ConstantInt>(PV1GEP->idx_begin())) {
1638
0
            isRecursive = true;
1639
0
            continue;
1640
0
          }
1641
3.32M
        }
1642
0
      }
1643
3.32M
      V1Srcs.push_back(PV1);
1644
3.32M
    }
1645
5.39M
  } else {
1646
5.39M
    // If we don't have PhiInfo then just look at the operands of the phi itself
1647
5.39M
    // FIXME: Remove this once we can guarantee that we have PhiInfo always
1648
5.39M
    SmallPtrSet<Value *, 4> UniqueSrc;
1649
10.3M
    for (Value *PV1 : PN->incoming_values()) {
1650
10.3M
      if (isa<PHINode>(PV1))
1651
1.12M
        // If any of the source itself is a PHI, return MayAlias conservatively
1652
1.12M
        // to avoid compile time explosion. The worst possible case is if both
1653
1.12M
        // sides are PHI nodes. In which case, this is O(m x n) time where 'm'
1654
1.12M
        // and 'n' are the number of PHI sources.
1655
1.12M
        return MayAlias;
1656
9.19M
1657
9.19M
      if (EnableRecPhiAnalysis)
1658
18
        if (GEPOperator *PV1GEP = dyn_cast<GEPOperator>(PV1)) {
1659
9
          // Check whether the incoming value is a GEP that advances the pointer
1660
9
          // result of this PHI node (e.g. in a loop). If this is the case, we
1661
9
          // would recurse and always get a MayAlias. Handle this case specially
1662
9
          // below.
1663
9
          if (PV1GEP->getPointerOperand() == PN && PV1GEP->getNumIndices() == 1 &&
1664
9
              isa<ConstantInt>(PV1GEP->idx_begin())) {
1665
9
            isRecursive = true;
1666
9
            continue;
1667
9
          }
1668
9.19M
        }
1669
9.19M
1670
9.19M
      if (UniqueSrc.insert(PV1).second)
1671
9.08M
        V1Srcs.push_back(PV1);
1672
9.19M
    }
1673
5.39M
  }
1674
6.81M
1675
6.81M
  // If V1Srcs is empty then that means that the phi has no underlying non-phi
1676
6.81M
  // value. This should only be possible in blocks unreachable from the entry
1677
6.81M
  // block, but return MayAlias just in case.
1678
6.81M
  
if (5.63M
V1Srcs.empty()5.63M
)
1679
0
    return MayAlias;
1680
5.63M
1681
5.63M
  // If this PHI node is recursive, set the size of the accessed memory to
1682
5.63M
  // unknown to represent all the possible values the GEP could advance the
1683
5.63M
  // pointer to.
1684
5.63M
  if (isRecursive)
1685
9
    PNSize = LocationSize::unknown();
1686
5.63M
1687
5.63M
  AliasResult Alias = aliasCheck(V2, V2Size, V2AAInfo, V1Srcs[0], PNSize,
1688
5.63M
                                 PNAAInfo, AAQI, UnderV2);
1689
5.63M
1690
5.63M
  // Early exit if the check of the first PHI source against V2 is MayAlias.
1691
5.63M
  // Other results are not possible.
1692
5.63M
  if (Alias == MayAlias)
1693
4.05M
    return MayAlias;
1694
1.57M
1695
1.57M
  // If all sources of the PHI node NoAlias or MustAlias V2, then returns
1696
1.57M
  // NoAlias / MustAlias. Otherwise, returns MayAlias.
1697
3.00M
  
for (unsigned i = 1, e = V1Srcs.size(); 1.57M
i != e;
++i1.42M
) {
1698
1.66M
    Value *V = V1Srcs[i];
1699
1.66M
1700
1.66M
    AliasResult ThisAlias =
1701
1.66M
        aliasCheck(V2, V2Size, V2AAInfo, V, PNSize, PNAAInfo, AAQI, UnderV2);
1702
1.66M
    Alias = MergeAliasResults(ThisAlias, Alias);
1703
1.66M
    if (Alias == MayAlias)
1704
246k
      break;
1705
1.66M
  }
1706
1.57M
1707
1.57M
  return Alias;
1708
1.57M
}
1709
1710
/// Provides a bunch of ad-hoc rules to disambiguate in common cases, such as
1711
/// array references.
1712
AliasResult BasicAAResult::aliasCheck(const Value *V1, LocationSize V1Size,
1713
                                      AAMDNodes V1AAInfo, const Value *V2,
1714
                                      LocationSize V2Size, AAMDNodes V2AAInfo,
1715
                                      AAQueryInfo &AAQI, const Value *O1,
1716
87.4M
                                      const Value *O2) {
1717
87.4M
  // If either of the memory references is empty, it doesn't matter what the
1718
87.4M
  // pointer values are.
1719
87.4M
  if (V1Size.isZero() || 
V2Size.isZero()87.4M
)
1720
369
    return NoAlias;
1721
87.4M
1722
87.4M
  // Strip off any casts if they exist.
1723
87.4M
  V1 = V1->stripPointerCastsAndInvariantGroups();
1724
87.4M
  V2 = V2->stripPointerCastsAndInvariantGroups();
1725
87.4M
1726
87.4M
  // If V1 or V2 is undef, the result is NoAlias because we can always pick a
1727
87.4M
  // value for undef that aliases nothing in the program.
1728
87.4M
  if (isa<UndefValue>(V1) || 
isa<UndefValue>(V2)87.4M
)
1729
26.1k
    return NoAlias;
1730
87.4M
1731
87.4M
  // Are we checking for alias of the same value?
1732
87.4M
  // Because we look 'through' phi nodes, we could look at "Value" pointers from
1733
87.4M
  // different iterations. We must therefore make sure that this is not the
1734
87.4M
  // case. The function isValueEqualInPotentialCycles ensures that this cannot
1735
87.4M
  // happen by looking at the visited phi nodes and making sure they cannot
1736
87.4M
  // reach the value.
1737
87.4M
  if (isValueEqualInPotentialCycles(V1, V2))
1738
15.8M
    return MustAlias;
1739
71.5M
1740
71.5M
  if (!V1->getType()->isPointerTy() || 
!V2->getType()->isPointerTy()71.5M
)
1741
73
    return NoAlias; // Scalars cannot alias each other
1742
71.5M
1743
71.5M
  // Figure out what objects these things are pointing to if we can.
1744
71.5M
  if (O1 == nullptr)
1745
63.8M
    O1 = GetUnderlyingObject(V1, DL, MaxLookupSearchDepth);
1746
71.5M
1747
71.5M
  if (O2 == nullptr)
1748
66.6M
    O2 = GetUnderlyingObject(V2, DL, MaxLookupSearchDepth);
1749
71.5M
1750
71.5M
  // Null values in the default address space don't point to any object, so they
1751
71.5M
  // don't alias any other pointer.
1752
71.5M
  if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O1))
1753
24.4k
    if (!NullPointerIsDefined(&F, CPN->getType()->getAddressSpace()))
1754
24.4k
      return NoAlias;
1755
71.5M
  if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O2))
1756
165k
    if (!NullPointerIsDefined(&F, CPN->getType()->getAddressSpace()))
1757
165k
      return NoAlias;
1758
71.3M
1759
71.3M
  if (O1 != O2) {
1760
51.3M
    // If V1/V2 point to two different objects, we know that we have no alias.
1761
51.3M
    if (isIdentifiedObject(O1) && 
isIdentifiedObject(O2)14.6M
)
1762
6.19M
      return NoAlias;
1763
45.1M
1764
45.1M
    // Constant pointers can't alias with non-const isIdentifiedObject objects.
1765
45.1M
    if ((isa<Constant>(O1) && 
isIdentifiedObject(O2)2.68M
&&
!isa<Constant>(O2)895
) ||
1766
45.1M
        
(45.1M
isa<Constant>(O2)45.1M
&&
isIdentifiedObject(O1)2.80M
&&
!isa<Constant>(O1)3.01k
))
1767
2.75k
      return NoAlias;
1768
45.1M
1769
45.1M
    // Function arguments can't alias with things that are known to be
1770
45.1M
    // unambigously identified at the function level.
1771
45.1M
    if ((isa<Argument>(O1) && 
isIdentifiedFunctionLocal(O2)8.75M
) ||
1772
45.1M
        
(44.4M
isa<Argument>(O2)44.4M
&&
isIdentifiedFunctionLocal(O1)10.3M
))
1773
2.94M
      return NoAlias;
1774
42.1M
1775
42.1M
    // If one pointer is the result of a call/invoke or load and the other is a
1776
42.1M
    // non-escaping local object within the same function, then we know the
1777
42.1M
    // object couldn't escape to a point where the call could return it.
1778
42.1M
    //
1779
42.1M
    // Note that if the pointers are in different functions, there are a
1780
42.1M
    // variety of complications. A call with a nocapture argument may still
1781
42.1M
    // temporary store the nocapture argument's value in a temporary memory
1782
42.1M
    // location if that memory location doesn't escape. Or it may pass a
1783
42.1M
    // nocapture value to other functions as long as they don't capture it.
1784
42.1M
    if (isEscapeSource(O1) &&
1785
42.1M
        
isNonEscapingLocalObject(O2, &AAQI.IsCapturedCache)28.2M
)
1786
203k
      return NoAlias;
1787
41.9M
    if (isEscapeSource(O2) &&
1788
41.9M
        
isNonEscapingLocalObject(O1, &AAQI.IsCapturedCache)28.3M
)
1789
287k
      return NoAlias;
1790
61.7M
  }
1791
61.7M
1792
61.7M
  // If the size of one access is larger than the entire object on the other
1793
61.7M
  // side, then we know such behavior is undefined and can assume no alias.
1794
61.7M
  bool NullIsValidLocation = NullPointerIsDefined(&F);
1795
61.7M
  if ((V1Size.isPrecise() && isObjectSmallerThan(O2, V1Size.getValue(), DL, TLI,
1796
42.4M
                                                 NullIsValidLocation)) ||
1797
61.7M
      
(61.6M
V2Size.isPrecise()61.6M
&& isObjectSmallerThan(O1, V2Size.getValue(), DL, TLI,
1798
42.6M
                                                 NullIsValidLocation)))
1799
218k
    return NoAlias;
1800
61.5M
1801
61.5M
  // Check the cache before climbing up use-def chains. This also terminates
1802
61.5M
  // otherwise infinitely recursive queries.
1803
61.5M
  AAQueryInfo::LocPair Locs(MemoryLocation(V1, V1Size, V1AAInfo),
1804
61.5M
                            MemoryLocation(V2, V2Size, V2AAInfo));
1805
61.5M
  if (V1 > V2)
1806
25.0M
    std::swap(Locs.first, Locs.second);
1807
61.5M
  std::pair<AAQueryInfo::AliasCacheT::iterator, bool> Pair =
1808
61.5M
      AAQI.AliasCache.try_emplace(Locs, MayAlias);
1809
61.5M
  if (!Pair.second)
1810
2.45M
    return Pair.first->second;
1811
59.0M
1812
59.0M
  // FIXME: This isn't aggressively handling alias(GEP, PHI) for example: if the
1813
59.0M
  // GEP can't simplify, we don't even look at the PHI cases.
1814
59.0M
  if (!isa<GEPOperator>(V1) && 
isa<GEPOperator>(V2)27.7M
) {
1815
5.26M
    std::swap(V1, V2);
1816
5.26M
    std::swap(V1Size, V2Size);
1817
5.26M
    std::swap(O1, O2);
1818
5.26M
    std::swap(V1AAInfo, V2AAInfo);
1819
5.26M
  }
1820
59.0M
  if (const GEPOperator *GV1 = dyn_cast<GEPOperator>(V1)) {
1821
36.6M
    AliasResult Result =
1822
36.6M
        aliasGEP(GV1, V1Size, V1AAInfo, V2, V2Size, V2AAInfo, O1, O2, AAQI);
1823
36.6M
    if (Result != MayAlias) {
1824
21.1M
      auto ItInsPair = AAQI.AliasCache.insert(std::make_pair(Locs, Result));
1825
21.1M
      assert(!ItInsPair.second && "Entry must have existed");
1826
21.1M
      ItInsPair.first->second = Result;
1827
21.1M
      return Result;
1828
21.1M
    }
1829
37.9M
  }
1830
37.9M
1831
37.9M
  if (isa<PHINode>(V2) && 
!isa<PHINode>(V1)4.64M
) {
1832
3.47M
    std::swap(V1, V2);
1833
3.47M
    std::swap(O1, O2);
1834
3.47M
    std::swap(V1Size, V2Size);
1835
3.47M
    std::swap(V1AAInfo, V2AAInfo);
1836
3.47M
  }
1837
37.9M
  if (const PHINode *PN = dyn_cast<PHINode>(V1)) {
1838
7.45M
    AliasResult Result =
1839
7.45M
        aliasPHI(PN, V1Size, V1AAInfo, V2, V2Size, V2AAInfo, O2, AAQI);
1840
7.45M
    if (Result != MayAlias) {
1841
1.45M
      Pair = AAQI.AliasCache.try_emplace(Locs, Result);
1842
1.45M
      assert(!Pair.second && "Entry must have existed");
1843
1.45M
      return Pair.first->second = Result;
1844
1.45M
    }
1845
36.4M
  }
1846
36.4M
1847
36.4M
  if (isa<SelectInst>(V2) && 
!isa<SelectInst>(V1)259k
) {
1848
251k
    std::swap(V1, V2);
1849
251k
    std::swap(O1, O2);
1850
251k
    std::swap(V1Size, V2Size);
1851
251k
    std::swap(V1AAInfo, V2AAInfo);
1852
251k
  }
1853
36.4M
  if (const SelectInst *S1 = dyn_cast<SelectInst>(V1)) {
1854
350k
    AliasResult Result =
1855
350k
        aliasSelect(S1, V1Size, V1AAInfo, V2, V2Size, V2AAInfo, O2, AAQI);
1856
350k
    if (Result != MayAlias) {
1857
43.0k
      Pair = AAQI.AliasCache.try_emplace(Locs, Result);
1858
43.0k
      assert(!Pair.second && "Entry must have existed");
1859
43.0k
      return Pair.first->second = Result;
1860
43.0k
    }
1861
36.4M
  }
1862
36.4M
1863
36.4M
  // If both pointers are pointing into the same object and one of them
1864
36.4M
  // accesses the entire object, then the accesses must overlap in some way.
1865
36.4M
  if (O1 == O2)
1866
989k
    if (V1Size.isPrecise() && 
V2Size.isPrecise()688k
&&
1867
989k
        
(519k
isObjectSize(O1, V1Size.getValue(), DL, TLI, NullIsValidLocation)519k
||
1868
519k
         
isObjectSize(O2, V2Size.getValue(), DL, TLI, NullIsValidLocation)519k
)) {
1869
988
      Pair = AAQI.AliasCache.try_emplace(Locs, PartialAlias);
1870
988
      assert(!Pair.second && "Entry must have existed");
1871
988
      return Pair.first->second = PartialAlias;
1872
988
    }
1873
36.4M
1874
36.4M
  // Recurse back into the best AA results we have, potentially with refined
1875
36.4M
  // memory locations. We have already ensured that BasicAA has a MayAlias
1876
36.4M
  // cache result for these, so any recursion back into BasicAA won't loop.
1877
36.4M
  AliasResult Result = getBestAAResults().alias(Locs.first, Locs.second, AAQI);
1878
36.4M
  Pair = AAQI.AliasCache.try_emplace(Locs, Result);
1879
36.4M
  assert(!Pair.second && "Entry must have existed");
1880
36.4M
  return Pair.first->second = Result;
1881
36.4M
}
1882
1883
/// Check whether two Values can be considered equivalent.
1884
///
1885
/// In addition to pointer equivalence of \p V1 and \p V2 this checks whether
1886
/// they can not be part of a cycle in the value graph by looking at all
1887
/// visited phi nodes an making sure that the phis cannot reach the value. We
1888
/// have to do this because we are looking through phi nodes (That is we say
1889
/// noalias(V, phi(VA, VB)) if noalias(V, VA) and noalias(V, VB).
1890
bool BasicAAResult::isValueEqualInPotentialCycles(const Value *V,
1891
93.5M
                                                  const Value *V2) {
1892
93.5M
  if (V != V2)
1893
71.8M
    return false;
1894
21.7M
1895
21.7M
  const Instruction *Inst = dyn_cast<Instruction>(V);
1896
21.7M
  if (!Inst)
1897
9.40M
    return true;
1898
12.3M
1899
12.3M
  if (VisitedPhiBBs.empty())
1900
11.9M
    return true;
1901
352k
1902
352k
  if (VisitedPhiBBs.size() > MaxNumPhiBBsValueReachabilityCheck)
1903
66
    return false;
1904
352k
1905
352k
  // Make sure that the visited phis cannot reach the Value. This ensures that
1906
352k
  // the Values cannot come from different iterations of a potential cycle the
1907
352k
  // phi nodes could be involved in.
1908
352k
  for (auto *P : VisitedPhiBBs)
1909
376k
    if (isPotentiallyReachable(&P->front(), Inst, nullptr, DT, LI))
1910
306k
      return false;
1911
352k
1912
352k
  
return true45.7k
;
1913
352k
}
1914
1915
/// Computes the symbolic difference between two de-composed GEPs.
1916
///
1917
/// Dest and Src are the variable indices from two decomposed GetElementPtr
1918
/// instructions GEP1 and GEP2 which have common base pointers.
1919
void BasicAAResult::GetIndexDifference(
1920
    SmallVectorImpl<VariableGEPIndex> &Dest,
1921
12.0M
    const SmallVectorImpl<VariableGEPIndex> &Src) {
1922
12.0M
  if (Src.empty())
1923
6.29M
    return;
1924
5.72M
1925
11.6M
  
for (unsigned i = 0, e = Src.size(); 5.72M
i != e;
++i5.92M
) {
1926
5.92M
    const Value *V = Src[i].V;
1927
5.92M
    unsigned ZExtBits = Src[i].ZExtBits, SExtBits = Src[i].SExtBits;
1928
5.92M
    APInt Scale = Src[i].Scale;
1929
5.92M
1930
5.92M
    // Find V in Dest.  This is N^2, but pointer indices almost never have more
1931
5.92M
    // than a few variable indexes.
1932
6.37M
    for (unsigned j = 0, e = Dest.size(); j != e; 
++j448k
) {
1933
5.99M
      if (!isValueEqualInPotentialCycles(Dest[j].V, V) ||
1934
5.99M
          
Dest[j].ZExtBits != ZExtBits5.55M
||
Dest[j].SExtBits != SExtBits5.55M
)
1935
448k
        continue;
1936
5.55M
1937
5.55M
      // If we found it, subtract off Scale V's from the entry in Dest.  If it
1938
5.55M
      // goes to zero, remove the entry.
1939
5.55M
      if (Dest[j].Scale != Scale)
1940
15.3k
        Dest[j].Scale -= Scale;
1941
5.53M
      else
1942
5.53M
        Dest.erase(Dest.begin() + j);
1943
5.55M
      Scale = 0;
1944
5.55M
      break;
1945
5.55M
    }
1946
5.92M
1947
5.92M
    // If we didn't consume this entry, add it to the end of the Dest list.
1948
5.92M
    if (!!Scale) {
1949
370k
      VariableGEPIndex Entry = {V, ZExtBits, SExtBits, -Scale};
1950
370k
      Dest.push_back(Entry);
1951
370k
    }
1952
5.92M
  }
1953
5.72M
}
1954
1955
bool BasicAAResult::constantOffsetHeuristic(
1956
    const SmallVectorImpl<VariableGEPIndex> &VarIndices,
1957
    LocationSize MaybeV1Size, LocationSize MaybeV2Size, APInt BaseOffset,
1958
430k
    AssumptionCache *AC, DominatorTree *DT) {
1959
430k
  if (VarIndices.size() != 2 || 
MaybeV1Size == LocationSize::unknown()208k
||
1960
430k
      
MaybeV2Size == LocationSize::unknown()201k
)
1961
229k
    return false;
1962
201k
1963
201k
  const uint64_t V1Size = MaybeV1Size.getValue();
1964
201k
  const uint64_t V2Size = MaybeV2Size.getValue();
1965
201k
1966
201k
  const VariableGEPIndex &Var0 = VarIndices[0], &Var1 = VarIndices[1];
1967
201k
1968
201k
  if (Var0.ZExtBits != Var1.ZExtBits || 
Var0.SExtBits != Var1.SExtBits189k
||
1969
201k
      
Var0.Scale != -Var1.Scale171k
)
1970
52.0k
    return false;
1971
149k
1972
149k
  unsigned Width = Var1.V->getType()->getIntegerBitWidth();
1973
149k
1974
149k
  // We'll strip off the Extensions of Var0 and Var1 and do another round
1975
149k
  // of GetLinearExpression decomposition. In the example above, if Var0
1976
149k
  // is zext(%x + 1) we should get V1 == %x and V1Offset == 1.
1977
149k
1978
149k
  APInt V0Scale(Width, 0), V0Offset(Width, 0), V1Scale(Width, 0),
1979
149k
      V1Offset(Width, 0);
1980
149k
  bool NSW = true, NUW = true;
1981
149k
  unsigned V0ZExtBits = 0, V0SExtBits = 0, V1ZExtBits = 0, V1SExtBits = 0;
1982
149k
  const Value *V0 = GetLinearExpression(Var0.V, V0Scale, V0Offset, V0ZExtBits,
1983
149k
                                        V0SExtBits, DL, 0, AC, DT, NSW, NUW);
1984
149k
  NSW = true;
1985
149k
  NUW = true;
1986
149k
  const Value *V1 = GetLinearExpression(Var1.V, V1Scale, V1Offset, V1ZExtBits,
1987
149k
                                        V1SExtBits, DL, 0, AC, DT, NSW, NUW);
1988
149k
1989
149k
  if (V0Scale != V1Scale || 
V0ZExtBits != V1ZExtBits148k
||
1990
149k
      
V0SExtBits != V1SExtBits148k
||
!isValueEqualInPotentialCycles(V0, V1)148k
)
1991
138k
    return false;
1992
11.2k
1993
11.2k
  // We have a hit - Var0 and Var1 only differ by a constant offset!
1994
11.2k
1995
11.2k
  // If we've been sext'ed then zext'd the maximum difference between Var0 and
1996
11.2k
  // Var1 is possible to calculate, but we're just interested in the absolute
1997
11.2k
  // minimum difference between the two. The minimum distance may occur due to
1998
11.2k
  // wrapping; consider "add i3 %i, 5": if %i == 7 then 7 + 5 mod 8 == 4, and so
1999
11.2k
  // the minimum distance between %i and %i + 5 is 3.
2000
11.2k
  APInt MinDiff = V0Offset - V1Offset, Wrapped = -MinDiff;
2001
11.2k
  MinDiff = APIntOps::umin(MinDiff, Wrapped);
2002
11.2k
  APInt MinDiffBytes =
2003
11.2k
    MinDiff.zextOrTrunc(Var0.Scale.getBitWidth()) * Var0.Scale.abs();
2004
11.2k
2005
11.2k
  // We can't definitely say whether GEP1 is before or after V2 due to wrapping
2006
11.2k
  // arithmetic (i.e. for some values of GEP1 and V2 GEP1 < V2, and for other
2007
11.2k
  // values GEP1 > V2). We'll therefore only declare NoAlias if both V1Size and
2008
11.2k
  // V2Size can fit in the MinDiffBytes gap.
2009
11.2k
  return MinDiffBytes.uge(V1Size + BaseOffset.abs()) &&
2010
11.2k
         
MinDiffBytes.uge(V2Size + BaseOffset.abs())5.30k
;
2011
11.2k
}
2012
2013
//===----------------------------------------------------------------------===//
2014
// BasicAliasAnalysis Pass
2015
//===----------------------------------------------------------------------===//
2016
2017
AnalysisKey BasicAA::Key;
2018
2019
4.25k
BasicAAResult BasicAA::run(Function &F, FunctionAnalysisManager &AM) {
2020
4.25k
  return BasicAAResult(F.getParent()->getDataLayout(),
2021
4.25k
                       F,
2022
4.25k
                       AM.getResult<TargetLibraryAnalysis>(F),
2023
4.25k
                       AM.getResult<AssumptionAnalysis>(F),
2024
4.25k
                       &AM.getResult<DominatorTreeAnalysis>(F),
2025
4.25k
                       AM.getCachedResult<LoopAnalysis>(F),
2026
4.25k
                       AM.getCachedResult<PhiValuesAnalysis>(F));
2027
4.25k
}
2028
2029
383k
BasicAAWrapperPass::BasicAAWrapperPass() : FunctionPass(ID) {
2030
383k
    initializeBasicAAWrapperPassPass(*PassRegistry::getPassRegistry());
2031
383k
}
2032
2033
char BasicAAWrapperPass::ID = 0;
2034
2035
0
void BasicAAWrapperPass::anchor() {}
2036
2037
102k
INITIALIZE_PASS_BEGIN(BasicAAWrapperPass, "basicaa",
2038
102k
                      "Basic Alias Analysis (stateless AA impl)", false, true)
2039
102k
INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
2040
102k
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
2041
102k
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
2042
102k
INITIALIZE_PASS_END(BasicAAWrapperPass, "basicaa",
2043
                    "Basic Alias Analysis (stateless AA impl)", false, true)
2044
2045
36.3k
FunctionPass *llvm::createBasicAAWrapperPass() {
2046
36.3k
  return new BasicAAWrapperPass();
2047
36.3k
}
2048
2049
9.61M
bool BasicAAWrapperPass::runOnFunction(Function &F) {
2050
9.61M
  auto &ACT = getAnalysis<AssumptionCacheTracker>();
2051
9.61M
  auto &TLIWP = getAnalysis<TargetLibraryInfoWrapperPass>();
2052
9.61M
  auto &DTWP = getAnalysis<DominatorTreeWrapperPass>();
2053
9.61M
  auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
2054
9.61M
  auto *PVWP = getAnalysisIfAvailable<PhiValuesWrapperPass>();
2055
9.61M
2056
9.61M
  Result.reset(new BasicAAResult(F.getParent()->getDataLayout(), F, TLIWP.getTLI(),
2057
9.61M
                                 ACT.getAssumptionCache(F), &DTWP.getDomTree(),
2058
9.61M
                                 LIWP ? 
&LIWP->getLoopInfo()3.15M
:
nullptr6.46M
,
2059
9.61M
                                 PVWP ? 
&PVWP->getResult()952k
:
nullptr8.66M
));
2060
9.61M
2061
9.61M
  return false;
2062
9.61M
}
2063
2064
381k
void BasicAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
2065
381k
  AU.setPreservesAll();
2066
381k
  AU.addRequired<AssumptionCacheTracker>();
2067
381k
  AU.addRequired<DominatorTreeWrapperPass>();
2068
381k
  AU.addRequired<TargetLibraryInfoWrapperPass>();
2069
381k
  AU.addUsedIfAvailable<PhiValuesWrapperPass>();
2070
381k
}
2071
2072
1.17M
BasicAAResult llvm::createLegacyPMBasicAAResult(Pass &P, Function &F) {
2073
1.17M
  return BasicAAResult(
2074
1.17M
      F.getParent()->getDataLayout(),
2075
1.17M
      F,
2076
1.17M
      P.getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(),
2077
1.17M
      P.getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F));
2078
1.17M
}