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/ScopeExit.h"
18#include "llvm/ADT/SmallPtrSet.h"
19#include "llvm/ADT/SmallVector.h"
20#include "llvm/ADT/Statistic.h"
21#include "llvm/Analysis/AliasAnalysis.h"
22#include "llvm/Analysis/AssumptionCache.h"
23#include "llvm/Analysis/CFG.h"
24#include "llvm/Analysis/CaptureTracking.h"
25#include "llvm/Analysis/MemoryBuiltins.h"
26#include "llvm/Analysis/MemoryLocation.h"
27#include "llvm/Analysis/TargetLibraryInfo.h"
28#include "llvm/Analysis/ValueTracking.h"
29#include "llvm/IR/Argument.h"
30#include "llvm/IR/Attributes.h"
31#include "llvm/IR/Constant.h"
32#include "llvm/IR/ConstantRange.h"
33#include "llvm/IR/Constants.h"
34#include "llvm/IR/CycleInfo.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/Operator.h"
48#include "llvm/IR/PatternMatch.h"
49#include "llvm/IR/Type.h"
50#include "llvm/IR/User.h"
51#include "llvm/IR/Value.h"
52#include "llvm/InitializePasses.h"
53#include "llvm/Pass.h"
54#include "llvm/Support/Casting.h"
55#include "llvm/Support/CommandLine.h"
56#include "llvm/Support/Compiler.h"
57#include "llvm/Support/KnownBits.h"
58#include "llvm/Support/SaveAndRestore.h"
59#include <cassert>
60#include <cstdint>
61#include <cstdlib>
62#include <optional>
63#include <utility>
64
65#define DEBUG_TYPE "basicaa"
66
67using namespace llvm;
68
69/// Enable analysis of recursive PHI nodes.
70static cl::opt<bool> EnableRecPhiAnalysis("basic-aa-recphi", cl::Hidden,
71 cl::init(Val: true));
72
73static cl::opt<bool> EnableSeparateStorageAnalysis("basic-aa-separate-storage",
74 cl::Hidden, cl::init(Val: true));
75
76/// SearchLimitReached / SearchTimes shows how often the limit of
77/// to decompose GEPs is reached. It will affect the precision
78/// of basic alias analysis.
79STATISTIC(SearchLimitReached, "Number of times the limit to "
80 "decompose GEPs is reached");
81STATISTIC(SearchTimes, "Number of times a GEP is decomposed");
82
83bool BasicAAResult::invalidate(Function &Fn, const PreservedAnalyses &PA,
84 FunctionAnalysisManager::Invalidator &Inv) {
85 // We don't care if this analysis itself is preserved, it has no state. But
86 // we need to check that the analyses it depends on have been. Note that we
87 // may be created without handles to some analyses and in that case don't
88 // depend on them.
89 if (Inv.invalidate<AssumptionAnalysis>(IR&: Fn, PA) ||
90 (DT_ && Inv.invalidate<DominatorTreeAnalysis>(IR&: Fn, PA)) ||
91 Inv.invalidate<TargetLibraryAnalysis>(IR&: Fn, PA))
92 return true;
93
94 // Otherwise this analysis result remains valid.
95 return false;
96}
97
98//===----------------------------------------------------------------------===//
99// Useful predicates
100//===----------------------------------------------------------------------===//
101
102/// Returns the size of the object specified by V or UnknownSize if unknown.
103static std::optional<TypeSize> getObjectSize(const Value *V,
104 const DataLayout &DL,
105 const TargetLibraryInfo &TLI,
106 bool NullIsValidLoc,
107 bool RoundToAlign = false) {
108 ObjectSizeOpts Opts;
109 Opts.RoundToAlign = RoundToAlign;
110 Opts.NullIsUnknownSize = NullIsValidLoc;
111 if (std::optional<TypeSize> Size = getBaseObjectSize(Ptr: V, DL, TLI: &TLI, Opts)) {
112 // FIXME: Remove this check, only exists to preserve previous behavior.
113 if (Size->isScalable())
114 return std::nullopt;
115 return Size;
116 }
117 return std::nullopt;
118}
119
120/// Returns true if we can prove that the object specified by V is smaller than
121/// Size. Bails out early unless the root object is passed as the first
122/// parameter.
123static bool isObjectSmallerThan(const Value *V, TypeSize Size,
124 const DataLayout &DL,
125 const TargetLibraryInfo &TLI,
126 bool NullIsValidLoc) {
127 // Note that the meanings of the "object" are slightly different in the
128 // following contexts:
129 // c1: llvm::getObjectSize()
130 // c2: llvm.objectsize() intrinsic
131 // c3: isObjectSmallerThan()
132 // c1 and c2 share the same meaning; however, the meaning of "object" in c3
133 // refers to the "entire object".
134 //
135 // Consider this example:
136 // char *p = (char*)malloc(100)
137 // char *q = p+80;
138 //
139 // In the context of c1 and c2, the "object" pointed by q refers to the
140 // stretch of memory of q[0:19]. So, getObjectSize(q) should return 20.
141 //
142 // In the context of c3, the "object" refers to the chunk of memory being
143 // allocated. So, the "object" has 100 bytes, and q points to the middle the
144 // "object". However, unless p, the root object, is passed as the first
145 // parameter, the call to isIdentifiedObject() makes isObjectSmallerThan()
146 // bail out early.
147 if (!isIdentifiedObject(V))
148 return false;
149
150 // This function needs to use the aligned object size because we allow
151 // reads a bit past the end given sufficient alignment.
152 std::optional<TypeSize> ObjectSize = getObjectSize(V, DL, TLI, NullIsValidLoc,
153 /*RoundToAlign*/ true);
154
155 return ObjectSize && TypeSize::isKnownLT(LHS: *ObjectSize, RHS: Size);
156}
157
158/// Return the minimal extent from \p V to the end of the underlying object,
159/// assuming the result is used in an aliasing query. E.g., we do use the query
160/// location size and the fact that null pointers cannot alias here.
161static TypeSize getMinimalExtentFrom(const Value &V,
162 const LocationSize &LocSize,
163 const DataLayout &DL,
164 bool NullIsValidLoc) {
165 // If we have dereferenceability information we know a lower bound for the
166 // extent as accesses for a lower offset would be valid. We need to exclude
167 // the "or null" part if null is a valid pointer. We can ignore frees, as an
168 // access after free would be undefined behavior.
169 bool CanBeNull;
170 uint64_t DerefBytes =
171 V.getPointerDereferenceableBytes(DL, CanBeNull, /*CanBeFreed=*/nullptr);
172 DerefBytes = (CanBeNull && NullIsValidLoc) ? 0 : DerefBytes;
173 // If queried with a precise location size, we assume that location size to be
174 // accessed, thus valid.
175 if (LocSize.isPrecise())
176 DerefBytes = std::max(a: DerefBytes, b: LocSize.getValue().getKnownMinValue());
177 return TypeSize::getFixed(ExactSize: DerefBytes);
178}
179
180/// Returns true if we can prove that the object specified by V has size Size.
181static bool isObjectSize(const Value *V, TypeSize Size, const DataLayout &DL,
182 const TargetLibraryInfo &TLI, bool NullIsValidLoc) {
183 std::optional<TypeSize> ObjectSize =
184 getObjectSize(V, DL, TLI, NullIsValidLoc);
185 return ObjectSize && *ObjectSize == Size;
186}
187
188/// Return true if both V1 and V2 are VScale
189static bool areBothVScale(const Value *V1, const Value *V2) {
190 return PatternMatch::match(V: V1, P: PatternMatch::m_VScale()) &&
191 PatternMatch::match(V: V2, P: PatternMatch::m_VScale());
192}
193
194//===----------------------------------------------------------------------===//
195// CaptureAnalysis implementations
196//===----------------------------------------------------------------------===//
197
198CaptureAnalysis::~CaptureAnalysis() = default;
199
200CaptureComponents SimpleCaptureAnalysis::getCapturesBefore(
201 const Value *Object, const Instruction *I, bool OrAt, bool ReturnCaptures) {
202 if (!isIdentifiedFunctionLocal(V: Object))
203 return CaptureComponents::Provenance;
204
205 auto [CacheIt, Inserted] = IsCapturedCache.try_emplace(Key: Object);
206 if (Inserted)
207 CacheIt->second = PointerMayBeCaptured(
208 V: Object, Mask: CaptureComponents::Provenance,
209 StopFn: [](CaptureComponents CC) { return capturesFullProvenance(CC); });
210
211 return ReturnCaptures ? CacheIt->second.WithRet : CacheIt->second.WithoutRet;
212}
213
214static bool isNotInCycle(const Instruction *I, const DominatorTree *DT,
215 const LoopInfo *LI, const CycleInfo *CI) {
216 if (CI)
217 return !CI->getCycle(Block: I->getParent());
218
219 BasicBlock *BB = const_cast<BasicBlock *>(I->getParent());
220 SmallVector<BasicBlock *> Succs(successors(BB));
221 return Succs.empty() ||
222 !isPotentiallyReachableFromMany(Worklist&: Succs, StopBB: BB, ExclusionSet: nullptr, DT, LI);
223}
224
225CaptureComponents EarliestEscapeAnalysis::getCapturesBefore(
226 const Value *Object, const Instruction *I, bool OrAt, bool ReturnCaptures) {
227 if (!isIdentifiedFunctionLocal(V: Object))
228 return CaptureComponents::Provenance;
229
230 auto Iter = EarliestEscapes.try_emplace(Key: Object);
231 if (Iter.second) {
232 auto [EarliestInst, Res] = FindEarliestCapture(
233 V: Object, F&: *DT.getRoot()->getParent(), DT, Mask: CaptureComponents::Provenance);
234 if (EarliestInst)
235 Inst2Obj[EarliestInst].push_back(NewVal: Object);
236 Iter.first->second = {EarliestInst, Res};
237 }
238
239 if (ReturnCaptures) {
240 assert(!I && "Context instruction not supported if ReturnCaptures");
241 return Iter.first->second.second.WithRet;
242 }
243
244 auto IsNotCapturedBefore = [&]() {
245 // No capturing instruction.
246 Instruction *CaptureInst = Iter.first->second.first;
247 if (!CaptureInst)
248 return true;
249
250 // No context instruction means any use is capturing.
251 if (!I)
252 return false;
253
254 if (I == CaptureInst) {
255 if (OrAt)
256 return false;
257 return isNotInCycle(I, DT: &DT, LI, CI);
258 }
259
260 return !isPotentiallyReachable(From: CaptureInst, To: I, ExclusionSet: nullptr, DT: &DT, LI, CI);
261 };
262 if (IsNotCapturedBefore())
263 return CaptureComponents::None;
264 return Iter.first->second.second.WithoutRet;
265}
266
267void EarliestEscapeAnalysis::removeInstruction(Instruction *I) {
268 auto Iter = Inst2Obj.find(Val: I);
269 if (Iter != Inst2Obj.end()) {
270 for (const Value *Obj : Iter->second)
271 EarliestEscapes.erase(Val: Obj);
272 Inst2Obj.erase(Val: I);
273 }
274}
275
276//===----------------------------------------------------------------------===//
277// GetElementPtr Instruction Decomposition and Analysis
278//===----------------------------------------------------------------------===//
279
280namespace {
281/// Represents zext(sext(trunc(V))).
282struct CastedValue {
283 const Value *V;
284 unsigned ZExtBits = 0;
285 unsigned SExtBits = 0;
286 unsigned TruncBits = 0;
287 /// Whether trunc(V) is non-negative.
288 bool IsNonNegative = false;
289
290 explicit CastedValue(const Value *V) : V(V) {}
291 explicit CastedValue(const Value *V, unsigned ZExtBits, unsigned SExtBits,
292 unsigned TruncBits, bool IsNonNegative)
293 : V(V), ZExtBits(ZExtBits), SExtBits(SExtBits), TruncBits(TruncBits),
294 IsNonNegative(IsNonNegative) {}
295
296 unsigned getBitWidth() const {
297 return V->getType()->getPrimitiveSizeInBits() - TruncBits + ZExtBits +
298 SExtBits;
299 }
300
301 CastedValue withValue(const Value *NewV, bool PreserveNonNeg) const {
302 return CastedValue(NewV, ZExtBits, SExtBits, TruncBits,
303 IsNonNegative && PreserveNonNeg);
304 }
305
306 /// Replace V with zext(NewV)
307 CastedValue withZExtOfValue(const Value *NewV, bool ZExtNonNegative) const {
308 unsigned ExtendBy = V->getType()->getPrimitiveSizeInBits() -
309 NewV->getType()->getPrimitiveSizeInBits();
310 if (ExtendBy <= TruncBits)
311 // zext<nneg>(trunc(zext(NewV))) == zext<nneg>(trunc(NewV))
312 // The nneg can be preserved on the outer zext here.
313 return CastedValue(NewV, ZExtBits, SExtBits, TruncBits - ExtendBy,
314 IsNonNegative);
315
316 // zext(sext(zext(NewV))) == zext(zext(zext(NewV)))
317 ExtendBy -= TruncBits;
318 // zext<nneg>(zext(NewV)) == zext(NewV)
319 // zext(zext<nneg>(NewV)) == zext<nneg>(NewV)
320 // The nneg can be preserved from the inner zext here but must be dropped
321 // from the outer.
322 return CastedValue(NewV, ZExtBits + SExtBits + ExtendBy, 0, 0,
323 ZExtNonNegative);
324 }
325
326 /// Replace V with sext(NewV)
327 CastedValue withSExtOfValue(const Value *NewV) const {
328 unsigned ExtendBy = V->getType()->getPrimitiveSizeInBits() -
329 NewV->getType()->getPrimitiveSizeInBits();
330 if (ExtendBy <= TruncBits)
331 // zext<nneg>(trunc(sext(NewV))) == zext<nneg>(trunc(NewV))
332 // The nneg can be preserved on the outer zext here
333 return CastedValue(NewV, ZExtBits, SExtBits, TruncBits - ExtendBy,
334 IsNonNegative);
335
336 // zext(sext(sext(NewV)))
337 ExtendBy -= TruncBits;
338 // zext<nneg>(sext(sext(NewV))) = zext<nneg>(sext(NewV))
339 // The nneg can be preserved on the outer zext here
340 return CastedValue(NewV, ZExtBits, SExtBits + ExtendBy, 0, IsNonNegative);
341 }
342
343 APInt evaluateWith(APInt N) const {
344 assert(N.getBitWidth() == V->getType()->getPrimitiveSizeInBits() &&
345 "Incompatible bit width");
346 if (TruncBits) N = N.trunc(width: N.getBitWidth() - TruncBits);
347 if (SExtBits) N = N.sext(width: N.getBitWidth() + SExtBits);
348 if (ZExtBits) N = N.zext(width: N.getBitWidth() + ZExtBits);
349 return N;
350 }
351
352 ConstantRange evaluateWith(ConstantRange N) const {
353 assert(N.getBitWidth() == V->getType()->getPrimitiveSizeInBits() &&
354 "Incompatible bit width");
355 if (TruncBits) N = N.truncate(BitWidth: N.getBitWidth() - TruncBits);
356 if (IsNonNegative && !N.isAllNonNegative())
357 N = N.intersectWith(
358 CR: ConstantRange(APInt::getZero(numBits: N.getBitWidth()),
359 APInt::getSignedMinValue(numBits: N.getBitWidth())));
360 if (SExtBits) N = N.signExtend(BitWidth: N.getBitWidth() + SExtBits);
361 if (ZExtBits) N = N.zeroExtend(BitWidth: N.getBitWidth() + ZExtBits);
362 return N;
363 }
364
365 bool canDistributeOver(bool NUW, bool NSW) const {
366 // zext(x op<nuw> y) == zext(x) op<nuw> zext(y)
367 // sext(x op<nsw> y) == sext(x) op<nsw> sext(y)
368 // trunc(x op y) == trunc(x) op trunc(y)
369 return (!ZExtBits || NUW) && (!SExtBits || NSW);
370 }
371
372 bool hasSameCastsAs(const CastedValue &Other) const {
373 if (V->getType() != Other.V->getType())
374 return false;
375
376 if (ZExtBits == Other.ZExtBits && SExtBits == Other.SExtBits &&
377 TruncBits == Other.TruncBits)
378 return true;
379 // If either CastedValue has a nneg zext then the sext/zext bits are
380 // interchangable for that value.
381 if (IsNonNegative || Other.IsNonNegative)
382 return (ZExtBits + SExtBits == Other.ZExtBits + Other.SExtBits &&
383 TruncBits == Other.TruncBits);
384 return false;
385 }
386};
387
388/// Represents zext(sext(trunc(V))) * Scale + Offset.
389struct LinearExpression {
390 CastedValue Val;
391 APInt Scale;
392 APInt Offset;
393
394 /// True if all operations in this expression are NUW.
395 bool IsNUW;
396 /// True if all operations in this expression are NSW.
397 bool IsNSW;
398
399 LinearExpression(const CastedValue &Val, const APInt &Scale,
400 const APInt &Offset, bool IsNUW, bool IsNSW)
401 : Val(Val), Scale(Scale), Offset(Offset), IsNUW(IsNUW), IsNSW(IsNSW) {}
402
403 LinearExpression(const CastedValue &Val)
404 : Val(Val), IsNUW(true), IsNSW(true) {
405 unsigned BitWidth = Val.getBitWidth();
406 Scale = APInt(BitWidth, 1);
407 Offset = APInt(BitWidth, 0);
408 }
409
410 LinearExpression mul(const APInt &Other, bool MulIsNUW, bool MulIsNSW) const {
411 // The check for zero offset is necessary, because generally
412 // (X +nsw Y) *nsw Z does not imply (X *nsw Z) +nsw (Y *nsw Z).
413 bool NSW = IsNSW && (Other.isOne() || (MulIsNSW && Offset.isZero()));
414 bool NUW = IsNUW && (Other.isOne() || MulIsNUW);
415 return LinearExpression(Val, Scale * Other, Offset * Other, NUW, NSW);
416 }
417};
418}
419
420/// Analyzes the specified value as a linear expression: "A*V + B", where A and
421/// B are constant integers.
422static LinearExpression GetLinearExpression(
423 const CastedValue &Val, const DataLayout &DL, unsigned Depth,
424 AssumptionCache *AC, DominatorTree *DT) {
425 // Limit our recursion depth.
426 if (Depth == 6)
427 return Val;
428
429 if (const ConstantInt *Const = dyn_cast<ConstantInt>(Val: Val.V))
430 return LinearExpression(Val, APInt(Val.getBitWidth(), 0),
431 Val.evaluateWith(N: Const->getValue()), true, true);
432
433 if (const BinaryOperator *BOp = dyn_cast<BinaryOperator>(Val: Val.V)) {
434 if (ConstantInt *RHSC = dyn_cast<ConstantInt>(Val: BOp->getOperand(i_nocapture: 1))) {
435 APInt RHS = Val.evaluateWith(N: RHSC->getValue());
436 // The only non-OBO case we deal with is or, and only limited to the
437 // case where it is both nuw and nsw.
438 bool NUW = true, NSW = true;
439 if (isa<OverflowingBinaryOperator>(Val: BOp)) {
440 NUW &= BOp->hasNoUnsignedWrap();
441 NSW &= BOp->hasNoSignedWrap();
442 }
443 if (!Val.canDistributeOver(NUW, NSW))
444 return Val;
445
446 // While we can distribute over trunc, we cannot preserve nowrap flags
447 // in that case.
448 if (Val.TruncBits)
449 NUW = NSW = false;
450
451 LinearExpression E(Val);
452 switch (BOp->getOpcode()) {
453 default:
454 // We don't understand this instruction, so we can't decompose it any
455 // further.
456 return Val;
457 case Instruction::Or:
458 // X|C == X+C if it is disjoint. Otherwise we can't analyze it.
459 if (!cast<PossiblyDisjointInst>(Val: BOp)->isDisjoint())
460 return Val;
461
462 [[fallthrough]];
463 case Instruction::Add: {
464 E = GetLinearExpression(Val: Val.withValue(NewV: BOp->getOperand(i_nocapture: 0), PreserveNonNeg: false), DL,
465 Depth: Depth + 1, AC, DT);
466 E.Offset += RHS;
467 E.IsNUW &= NUW;
468 E.IsNSW &= NSW;
469 break;
470 }
471 case Instruction::Sub: {
472 E = GetLinearExpression(Val: Val.withValue(NewV: BOp->getOperand(i_nocapture: 0), PreserveNonNeg: false), DL,
473 Depth: Depth + 1, AC, DT);
474 E.Offset -= RHS;
475 E.IsNUW = false; // sub nuw x, y is not add nuw x, -y.
476 E.IsNSW &= NSW;
477 break;
478 }
479 case Instruction::Mul:
480 E = GetLinearExpression(Val: Val.withValue(NewV: BOp->getOperand(i_nocapture: 0), PreserveNonNeg: false), DL,
481 Depth: Depth + 1, AC, DT)
482 .mul(Other: RHS, MulIsNUW: NUW, MulIsNSW: NSW);
483 break;
484 case Instruction::Shl:
485 // We're trying to linearize an expression of the kind:
486 // shl i8 -128, 36
487 // where the shift count exceeds the bitwidth of the type.
488 // We can't decompose this further (the expression would return
489 // a poison value).
490 if (RHS.getLimitedValue() > Val.getBitWidth())
491 return Val;
492
493 E = GetLinearExpression(Val: Val.withValue(NewV: BOp->getOperand(i_nocapture: 0), PreserveNonNeg: NSW), DL,
494 Depth: Depth + 1, AC, DT);
495 E.Offset <<= RHS.getLimitedValue();
496 E.Scale <<= RHS.getLimitedValue();
497 E.IsNUW &= NUW;
498 E.IsNSW &= NSW;
499 break;
500 }
501 return E;
502 }
503 }
504
505 if (const auto *ZExt = dyn_cast<ZExtInst>(Val: Val.V))
506 return GetLinearExpression(
507 Val: Val.withZExtOfValue(NewV: ZExt->getOperand(i_nocapture: 0), ZExtNonNegative: ZExt->hasNonNeg()), DL,
508 Depth: Depth + 1, AC, DT);
509
510 if (isa<SExtInst>(Val: Val.V))
511 return GetLinearExpression(
512 Val: Val.withSExtOfValue(NewV: cast<CastInst>(Val: Val.V)->getOperand(i_nocapture: 0)),
513 DL, Depth: Depth + 1, AC, DT);
514
515 return Val;
516}
517
518namespace {
519// A linear transformation of a Value; this class represents
520// ZExt(SExt(Trunc(V, TruncBits), SExtBits), ZExtBits) * Scale.
521struct VariableGEPIndex {
522 CastedValue Val;
523 APInt Scale;
524
525 // Context instruction to use when querying information about this index.
526 const Instruction *CxtI;
527
528 /// True if all operations in this expression are NSW.
529 bool IsNSW;
530
531 /// True if the index should be subtracted rather than added. We don't simply
532 /// negate the Scale, to avoid losing the NSW flag: X - INT_MIN*1 may be
533 /// non-wrapping, while X + INT_MIN*(-1) wraps.
534 bool IsNegated;
535
536 bool hasNegatedScaleOf(const VariableGEPIndex &Other) const {
537 if (IsNegated == Other.IsNegated)
538 return Scale == -Other.Scale;
539 return Scale == Other.Scale;
540 }
541
542 void dump() const {
543 print(OS&: dbgs());
544 dbgs() << "\n";
545 }
546 void print(raw_ostream &OS) const {
547 OS << "(V=" << Val.V->getName()
548 << ", zextbits=" << Val.ZExtBits
549 << ", sextbits=" << Val.SExtBits
550 << ", truncbits=" << Val.TruncBits
551 << ", scale=" << Scale
552 << ", nsw=" << IsNSW
553 << ", negated=" << IsNegated << ")";
554 }
555};
556}
557
558// Represents the internal structure of a GEP, decomposed into a base pointer,
559// constant offsets, and variable scaled indices.
560struct BasicAAResult::DecomposedGEP {
561 // Base pointer of the GEP
562 const Value *Base;
563 // Total constant offset from base.
564 APInt Offset;
565 // Scaled variable (non-constant) indices.
566 SmallVector<VariableGEPIndex, 4> VarIndices;
567 // Nowrap flags common to all GEP operations involved in expression.
568 GEPNoWrapFlags NWFlags = GEPNoWrapFlags::all();
569
570 void dump() const {
571 print(OS&: dbgs());
572 dbgs() << "\n";
573 }
574 void print(raw_ostream &OS) const {
575 OS << ", inbounds=" << (NWFlags.isInBounds() ? "1" : "0")
576 << ", nuw=" << (NWFlags.hasNoUnsignedWrap() ? "1" : "0")
577 << "(DecomposedGEP Base=" << Base->getName() << ", Offset=" << Offset
578 << ", VarIndices=[";
579 for (size_t i = 0; i < VarIndices.size(); i++) {
580 if (i != 0)
581 OS << ", ";
582 VarIndices[i].print(OS);
583 }
584 OS << "])";
585 }
586};
587
588// Results of analyzing variable GEP indices for offset-based disambiguation.
589struct BasicAAResult::VariableGEPOffsetInfo {
590 APInt GCD;
591 ConstantRange OffsetRange;
592};
593
594/// If V is a symbolic pointer expression, decompose it into a base pointer
595/// with a constant offset and a number of scaled symbolic offsets.
596///
597/// The scaled symbolic offsets (represented by pairs of a Value* and a scale
598/// in the VarIndices vector) are Value*'s that are known to be scaled by the
599/// specified amount, but which may have other unrepresented high bits. As
600/// such, the gep cannot necessarily be reconstructed from its decomposed form.
601BasicAAResult::DecomposedGEP
602BasicAAResult::DecomposeGEPExpression(const Value *V, const DataLayout &DL,
603 AssumptionCache *AC, DominatorTree *DT) {
604 // Limit recursion depth to limit compile time in crazy cases.
605 unsigned MaxLookup = MaxLookupSearchDepth;
606 SearchTimes++;
607 const Instruction *CxtI = dyn_cast<Instruction>(Val: V);
608
609 unsigned IndexSize = DL.getIndexTypeSizeInBits(Ty: V->getType());
610 DecomposedGEP Decomposed;
611 Decomposed.Offset = APInt(IndexSize, 0);
612 do {
613 // See if this is a bitcast or GEP.
614 const Operator *Op = dyn_cast<Operator>(Val: V);
615 if (!Op) {
616 // The only non-operator case we can handle are GlobalAliases.
617 if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(Val: V)) {
618 if (!GA->isInterposable()) {
619 V = GA->getAliasee();
620 continue;
621 }
622 }
623 Decomposed.Base = V;
624 return Decomposed;
625 }
626
627 if (Op->getOpcode() == Instruction::BitCast ||
628 Op->getOpcode() == Instruction::AddrSpaceCast) {
629 Value *NewV = Op->getOperand(i: 0);
630 auto *NewVTy = NewV->getType();
631 // Don't look through casts to non-scalar-pointer types or address spaces
632 // with differing index widths.
633 if (!isa<PointerType>(Val: NewVTy) ||
634 DL.getIndexTypeSizeInBits(Ty: NewVTy) != IndexSize) {
635 Decomposed.Base = V;
636 return Decomposed;
637 }
638 V = NewV;
639 continue;
640 }
641
642 const GEPOperator *GEPOp = dyn_cast<GEPOperator>(Val: Op);
643 if (!GEPOp) {
644 if (const auto *PHI = dyn_cast<PHINode>(Val: V)) {
645 // Look through single-arg phi nodes created by LCSSA.
646 if (PHI->getNumIncomingValues() == 1) {
647 V = PHI->getIncomingValue(i: 0);
648 continue;
649 }
650 } else if (const auto *Call = dyn_cast<CallBase>(Val: V)) {
651 // CaptureTracking can know about special capturing properties of some
652 // intrinsics like launder.invariant.group, that can't be expressed with
653 // the attributes, but have properties like returning aliasing pointer.
654 // Because some analysis may assume that nocaptured pointer is not
655 // returned from some special intrinsic (because function would have to
656 // be marked with returns attribute), it is crucial to use this function
657 // because it should be in sync with CaptureTracking. Not using it may
658 // cause weird miscompilations where 2 aliasing pointers are assumed to
659 // noalias.
660 // Pass MustPreserveOffset=true so we exclude llvm.ptrmask, which can
661 // change the byte offset by clearing low bits and would otherwise
662 // corrupt the symbolic offset we are accumulating in `Decomposed`.
663 if (auto *RP = getArgumentAliasingToReturnedPointer(
664 Call, /*MustPreserveOffset=*/true)) {
665 V = RP;
666 continue;
667 }
668 }
669
670 Decomposed.Base = V;
671 return Decomposed;
672 }
673
674 // Track the common nowrap flags for all GEPs we see.
675 Decomposed.NWFlags &= GEPOp->getNoWrapFlags();
676
677 assert(GEPOp->getSourceElementType()->isSized() && "GEP must be sized");
678
679 // Walk the indices of the GEP, accumulating them into BaseOff/VarIndices.
680 gep_type_iterator GTI = gep_type_begin(GEP: GEPOp);
681 for (User::const_op_iterator I = GEPOp->op_begin() + 1, E = GEPOp->op_end();
682 I != E; ++I, ++GTI) {
683 const Value *Index = *I;
684 // Compute the (potentially symbolic) offset in bytes for this index.
685 if (StructType *STy = GTI.getStructTypeOrNull()) {
686 // For a struct, add the member offset.
687 unsigned FieldNo = cast<ConstantInt>(Val: Index)->getZExtValue();
688 if (FieldNo == 0)
689 continue;
690
691 Decomposed.Offset += DL.getStructLayout(Ty: STy)->getElementOffset(Idx: FieldNo);
692 continue;
693 }
694
695 // For an array/pointer, add the element offset, explicitly scaled.
696 if (const ConstantInt *CIdx = dyn_cast<ConstantInt>(Val: Index)) {
697 if (CIdx->isZero())
698 continue;
699
700 // Don't attempt to analyze GEPs if the scalable index is not zero.
701 TypeSize AllocTypeSize = GTI.getSequentialElementStride(DL);
702 if (AllocTypeSize.isScalable()) {
703 Decomposed.Base = V;
704 return Decomposed;
705 }
706
707 Decomposed.Offset += AllocTypeSize.getFixedValue() *
708 CIdx->getValue().sextOrTrunc(width: IndexSize);
709 continue;
710 }
711
712 TypeSize AllocTypeSize = GTI.getSequentialElementStride(DL);
713 if (AllocTypeSize.isScalable()) {
714 Decomposed.Base = V;
715 return Decomposed;
716 }
717
718 // If the integer type is smaller than the index size, it is implicitly
719 // sign extended or truncated to index size.
720 bool NUSW = GEPOp->hasNoUnsignedSignedWrap();
721 bool NUW = GEPOp->hasNoUnsignedWrap();
722 bool NonNeg = NUSW && NUW;
723 unsigned Width = Index->getType()->getIntegerBitWidth();
724 unsigned SExtBits = IndexSize > Width ? IndexSize - Width : 0;
725 unsigned TruncBits = IndexSize < Width ? Width - IndexSize : 0;
726 LinearExpression LE = GetLinearExpression(
727 Val: CastedValue(Index, 0, SExtBits, TruncBits, NonNeg), DL, Depth: 0, AC, DT);
728
729 // Scale by the type size.
730 unsigned TypeSize = AllocTypeSize.getFixedValue();
731 LE = LE.mul(Other: APInt(IndexSize, TypeSize), MulIsNUW: NUW, MulIsNSW: NUSW);
732 Decomposed.Offset += LE.Offset;
733 APInt Scale = LE.Scale;
734 if (!LE.IsNUW)
735 Decomposed.NWFlags = Decomposed.NWFlags.withoutNoUnsignedWrap();
736
737 // If we already had an occurrence of this index variable, merge this
738 // scale into it. For example, we want to handle:
739 // A[x][x] -> x*16 + x*4 -> x*20
740 // This also ensures that 'x' only appears in the index list once.
741 for (unsigned i = 0, e = Decomposed.VarIndices.size(); i != e; ++i) {
742 if ((Decomposed.VarIndices[i].Val.V == LE.Val.V ||
743 areBothVScale(V1: Decomposed.VarIndices[i].Val.V, V2: LE.Val.V)) &&
744 Decomposed.VarIndices[i].Val.hasSameCastsAs(Other: LE.Val)) {
745 Scale += Decomposed.VarIndices[i].Scale;
746 // We cannot guarantee no-wrap for the merge.
747 LE.IsNSW = LE.IsNUW = false;
748 Decomposed.VarIndices.erase(CI: Decomposed.VarIndices.begin() + i);
749 break;
750 }
751 }
752
753 if (!!Scale) {
754 VariableGEPIndex Entry = {.Val: LE.Val, .Scale: Scale, .CxtI: CxtI, .IsNSW: LE.IsNSW,
755 /* IsNegated */ false};
756 Decomposed.VarIndices.push_back(Elt: Entry);
757 }
758 }
759
760 // Analyze the base pointer next.
761 V = GEPOp->getOperand(i_nocapture: 0);
762 } while (--MaxLookup);
763
764 // If the chain of expressions is too deep, just return early.
765 Decomposed.Base = V;
766 SearchLimitReached++;
767 return Decomposed;
768}
769
770ModRefInfo BasicAAResult::getModRefInfoMask(const MemoryLocation &Loc,
771 AAQueryInfo &AAQI,
772 bool IgnoreLocals) {
773 assert(Visited.empty() && "Visited must be cleared after use!");
774 llvm::scope_exit _([&] { Visited.clear(); });
775
776 unsigned MaxLookup = 8;
777 SmallVector<const Value *, 16> Worklist;
778 Worklist.push_back(Elt: Loc.Ptr);
779 ModRefInfo Result = ModRefInfo::NoModRef;
780
781 do {
782 const Value *V = getUnderlyingObject(V: Worklist.pop_back_val());
783 if (!Visited.insert(Ptr: V).second)
784 continue;
785
786 // Ignore allocas if we were instructed to do so.
787 if (IgnoreLocals && isa<AllocaInst>(Val: V))
788 continue;
789
790 // If the location points to memory that is known to be invariant for
791 // the life of the underlying SSA value, then we can exclude Mod from
792 // the set of valid memory effects.
793 //
794 // An argument that is marked readonly and noalias is known to be
795 // invariant while that function is executing.
796 if (const Argument *Arg = dyn_cast<Argument>(Val: V)) {
797 if (Arg->hasNoAliasAttr() && Arg->onlyReadsMemory()) {
798 Result |= ModRefInfo::Ref;
799 continue;
800 }
801 }
802
803 // A global constant can't be mutated.
804 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(Val: V)) {
805 // Note: this doesn't require GV to be "ODR" because it isn't legal for a
806 // global to be marked constant in some modules and non-constant in
807 // others. GV may even be a declaration, not a definition.
808 if (!GV->isConstant())
809 return ModRefInfo::ModRef;
810 continue;
811 }
812
813 // If both select values point to local memory, then so does the select.
814 if (const SelectInst *SI = dyn_cast<SelectInst>(Val: V)) {
815 Worklist.push_back(Elt: SI->getTrueValue());
816 Worklist.push_back(Elt: SI->getFalseValue());
817 continue;
818 }
819
820 // If all values incoming to a phi node point to local memory, then so does
821 // the phi.
822 if (const PHINode *PN = dyn_cast<PHINode>(Val: V)) {
823 // Don't bother inspecting phi nodes with many operands.
824 if (PN->getNumIncomingValues() > MaxLookup)
825 return ModRefInfo::ModRef;
826 append_range(C&: Worklist, R: PN->incoming_values());
827 continue;
828 }
829
830 // Otherwise be conservative.
831 return ModRefInfo::ModRef;
832 } while (!Worklist.empty() && --MaxLookup);
833
834 // If we hit the maximum number of instructions to examine, be conservative.
835 if (!Worklist.empty())
836 return ModRefInfo::ModRef;
837
838 return Result;
839}
840
841static bool isIntrinsicCall(const CallBase *Call, Intrinsic::ID IID) {
842 const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Val: Call);
843 return II && II->getIntrinsicID() == IID;
844}
845
846/// Returns the behavior when calling the given call site.
847MemoryEffects BasicAAResult::getMemoryEffects(const CallBase *Call,
848 AAQueryInfo &AAQI) {
849 MemoryEffects Min = Call->getAttributes().getMemoryEffects();
850
851 if (const Function *F = dyn_cast<Function>(Val: Call->getCalledOperand())) {
852 MemoryEffects FuncME = AAQI.AAR.getMemoryEffects(F);
853 // Operand bundles on the call may also read or write memory, in addition
854 // to the behavior of the called function.
855 if (Call->hasReadingOperandBundles())
856 FuncME |= MemoryEffects::readOnly();
857 if (Call->hasClobberingOperandBundles())
858 FuncME |= MemoryEffects::writeOnly();
859 if (Call->isVolatile()) {
860 // Volatile operations also access inaccessible memory.
861 FuncME |= MemoryEffects::inaccessibleMemOnly();
862 }
863 Min &= FuncME;
864 }
865
866 return Min;
867}
868
869/// Returns the behavior when calling the given function. For use when the call
870/// site is not known.
871MemoryEffects BasicAAResult::getMemoryEffects(const Function *F) {
872 switch (F->getIntrinsicID()) {
873 case Intrinsic::experimental_guard:
874 case Intrinsic::experimental_deoptimize:
875 // These intrinsics can read arbitrary memory, and additionally modref
876 // inaccessible memory to model control dependence.
877 return MemoryEffects::readOnly() |
878 MemoryEffects::inaccessibleMemOnly(MR: ModRefInfo::ModRef);
879 }
880
881 return F->getMemoryEffects();
882}
883
884ModRefInfo BasicAAResult::getArgModRefInfo(const CallBase *Call,
885 unsigned ArgIdx) {
886 if (Call->doesNotAccessMemory(OpNo: ArgIdx))
887 return ModRefInfo::NoModRef;
888
889 if (Call->onlyWritesMemory(OpNo: ArgIdx))
890 return ModRefInfo::Mod;
891
892 if (Call->onlyReadsMemory(OpNo: ArgIdx))
893 return ModRefInfo::Ref;
894
895 return ModRefInfo::ModRef;
896}
897
898#ifndef NDEBUG
899static const Function *getParent(const Value *V) {
900 if (const Instruction *inst = dyn_cast<Instruction>(V)) {
901 if (!inst->getParent())
902 return nullptr;
903 return inst->getParent()->getParent();
904 }
905
906 if (const Argument *arg = dyn_cast<Argument>(V))
907 return arg->getParent();
908
909 return nullptr;
910}
911
912static bool notDifferentParent(const Value *O1, const Value *O2) {
913
914 const Function *F1 = getParent(O1);
915 const Function *F2 = getParent(O2);
916
917 return !F1 || !F2 || F1 == F2;
918}
919#endif
920
921AliasResult BasicAAResult::alias(const MemoryLocation &LocA,
922 const MemoryLocation &LocB, AAQueryInfo &AAQI,
923 const Instruction *CtxI) {
924 assert(notDifferentParent(LocA.Ptr, LocB.Ptr) &&
925 "BasicAliasAnalysis doesn't support interprocedural queries.");
926 return aliasCheck(V1: LocA.Ptr, V1Size: LocA.Size, V2: LocB.Ptr, V2Size: LocB.Size, AAQI, CtxI);
927}
928
929/// Checks to see if the specified callsite can clobber the specified memory
930/// object.
931///
932/// Since we only look at local properties of this function, we really can't
933/// say much about this query. We do, however, use simple "address taken"
934/// analysis on local objects.
935ModRefInfo BasicAAResult::getModRefInfo(const CallBase *Call,
936 const MemoryLocation &Loc,
937 AAQueryInfo &AAQI) {
938 assert(notDifferentParent(Call, Loc.Ptr) &&
939 "AliasAnalysis query involving multiple functions!");
940
941 const Value *Object = getUnderlyingObject(V: Loc.Ptr);
942
943 // Calls marked 'tail' cannot read or write allocas from the current frame
944 // because the current frame might be destroyed by the time they run. However,
945 // a tail call may use an alloca with byval. Calling with byval copies the
946 // contents of the alloca into argument registers or stack slots, so there is
947 // no lifetime issue.
948 if (isa<AllocaInst>(Val: Object))
949 if (const CallInst *CI = dyn_cast<CallInst>(Val: Call))
950 if (CI->isTailCall() &&
951 !CI->getAttributes().hasAttrSomewhere(Kind: Attribute::ByVal))
952 return ModRefInfo::NoModRef;
953
954 // Stack restore is able to modify unescaped dynamic allocas. Assume it may
955 // modify them even though the alloca is not escaped.
956 if (auto *AI = dyn_cast<AllocaInst>(Val: Object))
957 if (!AI->isStaticAlloca() && isIntrinsicCall(Call, IID: Intrinsic::stackrestore))
958 return ModRefInfo::Mod;
959
960 // We can completely ignore inaccessible memory here, because MemoryLocations
961 // can only reference accessible memory.
962 auto ME = AAQI.AAR.getMemoryEffects(Call, AAQI)
963 .getWithoutLoc(Loc: IRMemLocation::InaccessibleMem);
964 if (ME.doesNotAccessMemory())
965 return ModRefInfo::NoModRef;
966
967 ModRefInfo ArgMR = ME.getModRef(Loc: IRMemLocation::ArgMem);
968 ModRefInfo ErrnoMR = ME.getModRef(Loc: IRMemLocation::ErrnoMem);
969 ModRefInfo OtherMR = ME.getModRef(Loc: IRMemLocation::Other);
970
971 // Take into account potential synchronization effects of the call.
972 // We assume synchronization can not occur if the call does not read/write
973 // other memory (this in particular ensures that readonly/argmemonly continue
974 // to work as expected for frontends that do not emit nosync).
975 // FIXME: This should apply to all calls, but is limited to inline asm to
976 // limit impact. This ensures that inline asm memory barriers work correctly.
977 ModRefInfo SyncMR = ModRefInfo::NoModRef;
978 if (isModAndRefSet(MRI: OtherMR) && Call->maySynchronize() &&
979 Call->isInlineAsm()) {
980 SyncMR = getSyncEffects(AA: &AAQI.AAR, Loc, AAQI);
981 if (isModAndRefSet(MRI: SyncMR))
982 return SyncMR;
983 }
984
985 // An identified function-local object that does not escape can only be
986 // accessed via call arguments. Reduce OtherMR (which includes accesses to
987 // escaped memory) based on that.
988 //
989 // We model calls that can return twice (setjmp) as clobbering non-escaping
990 // objects, to model any accesses that may occur prior to the second return.
991 // As an exception, ignore allocas, as setjmp is not required to preserve
992 // non-volatile stores for them.
993 if (isModOrRefSet(MRI: OtherMR) && !isa<Constant>(Val: Object) && Call != Object &&
994 (isa<AllocaInst>(Val: Object) || !Call->hasFnAttr(Kind: Attribute::ReturnsTwice))) {
995 CaptureComponents CC = AAQI.CA->getCapturesBefore(
996 Object, I: Call, /*OrAt=*/false, /*ReturnCaptures=*/false);
997 if (capturesNothing(CC))
998 OtherMR = ModRefInfo::NoModRef;
999 else if (capturesReadProvenanceOnly(CC))
1000 OtherMR = ModRefInfo::Ref;
1001 }
1002
1003 // Refine the modref info for argument memory. We only bother to do this
1004 // if ArgMR is not a subset of OtherMR, otherwise this won't have an impact
1005 // on the final result.
1006 if ((ArgMR | OtherMR) != OtherMR) {
1007 ModRefInfo NewArgMR = ModRefInfo::NoModRef;
1008 for (const Use &U : Call->data_ops()) {
1009 const Value *Arg = U;
1010 if (!Arg->getType()->isPointerTy())
1011 continue;
1012 unsigned ArgIdx = Call->getDataOperandNo(U: &U);
1013 MemoryLocation ArgLoc =
1014 Call->isArgOperand(U: &U)
1015 ? MemoryLocation::getForArgument(Call, ArgIdx, TLI)
1016 : MemoryLocation::getBeforeOrAfter(Ptr: Arg);
1017 AliasResult ArgAlias = AAQI.AAR.alias(LocA: ArgLoc, LocB: Loc, AAQI, CtxI: Call);
1018 if (ArgAlias != AliasResult::NoAlias)
1019 NewArgMR |= ArgMR & AAQI.AAR.getArgModRefInfo(Call, ArgIdx);
1020
1021 // Exit early if we cannot improve over the original ArgMR.
1022 if (NewArgMR == ArgMR)
1023 break;
1024 }
1025 ArgMR = NewArgMR;
1026 }
1027
1028 ModRefInfo Result = ArgMR | OtherMR | SyncMR;
1029
1030 // Refine accesses to errno memory.
1031 if ((ErrnoMR | Result) != Result) {
1032 if (AAQI.AAR.aliasErrno(Loc, CtxI: Call) != AliasResult::NoAlias) {
1033 // Exclusion conditions do not hold, this memory location may alias errno.
1034 Result |= ErrnoMR;
1035 }
1036 }
1037
1038 if (!isModAndRefSet(MRI: Result))
1039 return Result;
1040
1041 // Like assumes, invariant.start intrinsics were also marked as arbitrarily
1042 // writing so that proper control dependencies are maintained but they never
1043 // mod any particular memory location visible to the IR.
1044 // *Unlike* assumes (which are now modeled as NoModRef), invariant.start
1045 // intrinsic is now modeled as reading memory. This prevents hoisting the
1046 // invariant.start intrinsic over stores. Consider:
1047 // *ptr = 40;
1048 // *ptr = 50;
1049 // invariant_start(ptr)
1050 // int val = *ptr;
1051 // print(val);
1052 //
1053 // This cannot be transformed to:
1054 //
1055 // *ptr = 40;
1056 // invariant_start(ptr)
1057 // *ptr = 50;
1058 // int val = *ptr;
1059 // print(val);
1060 //
1061 // The transformation will cause the second store to be ignored (based on
1062 // rules of invariant.start) and print 40, while the first program always
1063 // prints 50.
1064 if (isIntrinsicCall(Call, IID: Intrinsic::invariant_start))
1065 return ModRefInfo::Ref;
1066
1067 // Be conservative.
1068 return ModRefInfo::ModRef;
1069}
1070
1071ModRefInfo BasicAAResult::getModRefInfo(const CallBase *Call1,
1072 const CallBase *Call2,
1073 AAQueryInfo &AAQI) {
1074 // Guard intrinsics are marked as arbitrarily writing so that proper control
1075 // dependencies are maintained but they never mods any particular memory
1076 // location.
1077 //
1078 // *Unlike* assumes, guard intrinsics are modeled as reading memory since the
1079 // heap state at the point the guard is issued needs to be consistent in case
1080 // the guard invokes the "deopt" continuation.
1081
1082 // NB! This function is *not* commutative, so we special case two
1083 // possibilities for guard intrinsics.
1084
1085 if (isIntrinsicCall(Call: Call1, IID: Intrinsic::experimental_guard))
1086 return isModSet(MRI: getMemoryEffects(Call: Call2, AAQI).getModRef())
1087 ? ModRefInfo::Ref
1088 : ModRefInfo::NoModRef;
1089
1090 if (isIntrinsicCall(Call: Call2, IID: Intrinsic::experimental_guard))
1091 return isModSet(MRI: getMemoryEffects(Call: Call1, AAQI).getModRef())
1092 ? ModRefInfo::Mod
1093 : ModRefInfo::NoModRef;
1094
1095 // Be conservative.
1096 return ModRefInfo::ModRef;
1097}
1098
1099/// Provides a bunch of ad-hoc rules to disambiguate a GEP instruction against
1100/// another pointer.
1101///
1102/// We know that V1 is a GEP, but we don't know anything about V2.
1103/// UnderlyingV1 is getUnderlyingObject(GEP1), UnderlyingV2 is the same for
1104/// V2.
1105AliasResult BasicAAResult::aliasGEP(
1106 const GEPOperator *GEP1, LocationSize V1Size,
1107 const Value *V2, LocationSize V2Size,
1108 const Value *UnderlyingV1, const Value *UnderlyingV2, AAQueryInfo &AAQI) {
1109 auto BaseObjectsAlias = [&]() {
1110 AliasResult BaseAlias =
1111 AAQI.AAR.alias(LocA: MemoryLocation::getBeforeOrAfter(Ptr: UnderlyingV1),
1112 LocB: MemoryLocation::getBeforeOrAfter(Ptr: UnderlyingV2), AAQI);
1113 return BaseAlias == AliasResult::NoAlias ? AliasResult::NoAlias
1114 : AliasResult::MayAlias;
1115 };
1116
1117 if (!V1Size.hasValue() && !V2Size.hasValue()) {
1118 // Skip if V2 is itself a phi or select, leave the recursive walk to
1119 // aliasPHI/aliasSelect.
1120 if (isa<PHINode, SelectInst>(Val: V2))
1121 return AliasResult::MayAlias;
1122
1123 // Otherwise check whether the base objects don't alias. Only do so if V2
1124 // is a GEP or an underlying object is a GEP/phi/select, which can be
1125 // analyzed further.
1126 if (isa<GEPOperator>(Val: V2) ||
1127 isa<GEPOperator, PHINode, SelectInst>(Val: UnderlyingV1) ||
1128 isa<GEPOperator, PHINode, SelectInst>(Val: UnderlyingV2))
1129 return BaseObjectsAlias();
1130
1131 return AliasResult::MayAlias;
1132 }
1133
1134 DominatorTree *DT = getDT(AAQI);
1135 DecomposedGEP DecompGEP1 = DecomposeGEPExpression(V: GEP1, DL, AC: &AC, DT);
1136 DecomposedGEP DecompGEP2 = DecomposeGEPExpression(V: V2, DL, AC: &AC, DT);
1137
1138 // Bail if we were not able to decompose anything.
1139 if (DecompGEP1.Base == GEP1 && DecompGEP2.Base == V2)
1140 return AliasResult::MayAlias;
1141
1142 // Fall back to base objects if pointers have different index widths.
1143 if (DecompGEP1.Offset.getBitWidth() != DecompGEP2.Offset.getBitWidth())
1144 return BaseObjectsAlias();
1145
1146 // Swap GEP1 and GEP2 if GEP2 has more variable indices.
1147 if (DecompGEP1.VarIndices.size() < DecompGEP2.VarIndices.size()) {
1148 std::swap(a&: DecompGEP1, b&: DecompGEP2);
1149 std::swap(a&: V1Size, b&: V2Size);
1150 std::swap(a&: UnderlyingV1, b&: UnderlyingV2);
1151 }
1152
1153 // Subtract the GEP2 pointer from the GEP1 pointer to find out their
1154 // symbolic difference.
1155 subtractDecomposedGEPs(DestGEP&: DecompGEP1, SrcGEP: DecompGEP2, AAQI);
1156
1157 // If an inbounds GEP would have to start from an out of bounds address
1158 // for the two to alias, then we can assume noalias.
1159 // TODO: Remove !isScalable() once BasicAA fully support scalable location
1160 // size.
1161 if (DecompGEP1.NWFlags.isInBounds() && DecompGEP1.VarIndices.empty() &&
1162 V2Size.hasValue() && !V2Size.isScalable() &&
1163 DecompGEP1.Offset.sge(RHS: V2Size.getValue()) &&
1164 isBaseOfObject(V: DecompGEP2.Base))
1165 return AliasResult::NoAlias;
1166
1167 // Symmetric case to above.
1168 if (DecompGEP2.NWFlags.isInBounds() && DecompGEP1.VarIndices.empty() &&
1169 V1Size.hasValue() && !V1Size.isScalable() &&
1170 DecompGEP1.Offset.sle(RHS: -V1Size.getValue()) &&
1171 isBaseOfObject(V: DecompGEP1.Base))
1172 return AliasResult::NoAlias;
1173
1174 // For GEPs with identical offsets, we can preserve the size and AAInfo
1175 // when performing the alias check on the underlying objects.
1176 if (DecompGEP1.Offset == 0 && DecompGEP1.VarIndices.empty())
1177 return AAQI.AAR.alias(LocA: MemoryLocation(DecompGEP1.Base, V1Size),
1178 LocB: MemoryLocation(DecompGEP2.Base, V2Size), AAQI);
1179
1180 // Do the base pointers alias?
1181 AliasResult BaseAlias =
1182 AAQI.AAR.alias(LocA: MemoryLocation::getBeforeOrAfter(Ptr: DecompGEP1.Base),
1183 LocB: MemoryLocation::getBeforeOrAfter(Ptr: DecompGEP2.Base), AAQI);
1184
1185 // If we get a No or May, then return it immediately, no amount of analysis
1186 // will improve this situation.
1187 if (BaseAlias != AliasResult::MustAlias) {
1188 assert(BaseAlias == AliasResult::NoAlias ||
1189 BaseAlias == AliasResult::MayAlias);
1190 return BaseAlias;
1191 }
1192
1193 // If there is a constant difference between the pointers, but the difference
1194 // is less than the size of the associated memory object, then we know
1195 // that the objects are partially overlapping. If the difference is
1196 // greater, we know they do not overlap.
1197 if (DecompGEP1.VarIndices.empty()) {
1198 APInt &Off = DecompGEP1.Offset;
1199
1200 // Initialize for Off >= 0 (V2 <= GEP1) case.
1201 LocationSize VLeftSize = V2Size;
1202 LocationSize VRightSize = V1Size;
1203 const bool Swapped = Off.isNegative();
1204
1205 if (Swapped) {
1206 // Swap if we have the situation where:
1207 // + +
1208 // | BaseOffset |
1209 // ---------------->|
1210 // |-->V1Size |-------> V2Size
1211 // GEP1 V2
1212 std::swap(a&: VLeftSize, b&: VRightSize);
1213 Off = -Off;
1214 }
1215
1216 if (!VLeftSize.hasValue())
1217 return AliasResult::MayAlias;
1218
1219 const TypeSize LSize = VLeftSize.getValue();
1220 if (!LSize.isScalable()) {
1221 if (Off.ult(RHS: LSize)) {
1222 // Conservatively drop processing if a phi was visited and/or offset is
1223 // too big.
1224 AliasResult AR = AliasResult::PartialAlias;
1225 if (VRightSize.hasValue() && !VRightSize.isScalable() &&
1226 Off.ule(INT32_MAX) && (Off + VRightSize.getValue()).ule(RHS: LSize)) {
1227 // Memory referenced by right pointer is nested. Save the offset in
1228 // cache. Note that originally offset estimated as GEP1-V2, but
1229 // AliasResult contains the shift that represents GEP1+Offset=V2.
1230 AR.setOffset(-Off.getSExtValue());
1231 AR.swap(DoSwap: Swapped);
1232 }
1233 return AR;
1234 }
1235 return AliasResult::NoAlias;
1236 }
1237
1238 // We can use the getVScaleRange to prove that Off >= (CR.upper * LSize).
1239 ConstantRange CR = getVScaleRange(F: &F, BitWidth: Off.getBitWidth());
1240 bool Overflow;
1241 APInt UpperRange = CR.getUnsignedMax().umul_ov(
1242 RHS: APInt(Off.getBitWidth(), LSize.getKnownMinValue()), Overflow);
1243 if (!Overflow && Off.uge(RHS: UpperRange))
1244 return AliasResult::NoAlias;
1245 }
1246
1247 // VScale Alias Analysis - Given one scalable offset between accesses and a
1248 // scalable typesize, we can divide each side by vscale, treating both values
1249 // as a constant. We prove that Offset/vscale >= TypeSize/vscale.
1250 if (DecompGEP1.VarIndices.size() == 1 &&
1251 DecompGEP1.VarIndices[0].Val.TruncBits == 0 &&
1252 DecompGEP1.Offset.isZero() &&
1253 PatternMatch::match(V: DecompGEP1.VarIndices[0].Val.V,
1254 P: PatternMatch::m_VScale())) {
1255 const VariableGEPIndex &ScalableVar = DecompGEP1.VarIndices[0];
1256 APInt Scale =
1257 ScalableVar.IsNegated ? -ScalableVar.Scale : ScalableVar.Scale;
1258 LocationSize VLeftSize = Scale.isNegative() ? V1Size : V2Size;
1259
1260 // Check if the offset is known to not overflow, if it does then attempt to
1261 // prove it with the known values of vscale_range.
1262 bool Overflows = !DecompGEP1.VarIndices[0].IsNSW;
1263 if (Overflows) {
1264 ConstantRange CR = getVScaleRange(F: &F, BitWidth: Scale.getBitWidth());
1265 (void)CR.getSignedMax().smul_ov(RHS: Scale, Overflow&: Overflows);
1266 }
1267
1268 if (!Overflows) {
1269 // Note that we do not check that the typesize is scalable, as vscale >= 1
1270 // so noalias still holds so long as the dependency distance is at least
1271 // as big as the typesize.
1272 if (VLeftSize.hasValue() &&
1273 Scale.abs().uge(RHS: VLeftSize.getValue().getKnownMinValue()))
1274 return AliasResult::NoAlias;
1275 }
1276 }
1277
1278 // If the difference between pointers is Offset +<nuw> Indices then we know
1279 // that the addition does not wrap the pointer index type (add nuw) and the
1280 // constant Offset is a lower bound on the distance between the pointers. We
1281 // can then prove NoAlias via Offset u>= VLeftSize.
1282 // + + +
1283 // | BaseOffset | +<nuw> Indices |
1284 // ---------------->|-------------------->|
1285 // |-->V2Size | |-------> V1Size
1286 // LHS RHS
1287 if (!DecompGEP1.VarIndices.empty() &&
1288 DecompGEP1.NWFlags.hasNoUnsignedWrap() && V2Size.hasValue() &&
1289 !V2Size.isScalable() && DecompGEP1.Offset.uge(RHS: V2Size.getValue()))
1290 return AliasResult::NoAlias;
1291
1292 // Bail on analyzing scalable LocationSize.
1293 if (V1Size.isScalable() || V2Size.isScalable())
1294 return AliasResult::MayAlias;
1295
1296 // We need to know both access sizes for all the following heuristics. Don't
1297 // try to reason about sizes larger than the index space.
1298 unsigned BW = DecompGEP1.Offset.getBitWidth();
1299 if (!V1Size.hasValue() || !V2Size.hasValue() ||
1300 !isUIntN(N: BW, x: V1Size.getValue()) || !isUIntN(N: BW, x: V2Size.getValue()))
1301 return AliasResult::MayAlias;
1302
1303 // Analyze the variable indices, and compute the GCD that the total
1304 // variable offset is guaranteed to be a multiple of, and its approximate
1305 // range.
1306 auto [GCD, OffsetRange] = analyzeVariableOffsets(GEP: DecompGEP1, DT);
1307
1308 // We now have accesses at two offsets from the same base:
1309 // 1. (...)*GCD + DecompGEP1.Offset with size V1Size
1310 // 2. 0 with size V2Size
1311 // Using arithmetic modulo GCD, the accesses are at
1312 // [ModOffset..ModOffset+V1Size) and [0..V2Size). If the first access fits
1313 // into the range [V2Size..GCD), then we know they cannot overlap.
1314 APInt ModOffset = DecompGEP1.Offset.srem(RHS: GCD);
1315 if (ModOffset.isNegative())
1316 ModOffset += GCD; // We want mod, not rem.
1317 if (ModOffset.uge(RHS: V2Size.getValue()) &&
1318 (GCD - ModOffset).uge(RHS: V1Size.getValue()))
1319 return AliasResult::NoAlias;
1320
1321 // If the ranges of potentially accessed bytes are disjoint, there cannot be
1322 // any overlap.
1323 ConstantRange Range1 = OffsetRange.add(
1324 Other: ConstantRange(APInt(BW, 0), APInt(BW, V1Size.getValue())));
1325 ConstantRange Range2 =
1326 ConstantRange(APInt(BW, 0), APInt(BW, V2Size.getValue()));
1327 if (Range1.intersectWith(CR: Range2).isEmptySet())
1328 return AliasResult::NoAlias;
1329
1330 // If a minimum absolute variable offset can be established, employ it to
1331 // prove that the two accesses are far enough apart.
1332 if (auto MinAbsVarIndex = computeMinAbsVarOffset(GEP: DecompGEP1, DT, AAQI)) {
1333 // The constant offset will have added at least +/-MinAbsVarIndex to it.
1334 APInt OffsetLo = DecompGEP1.Offset - *MinAbsVarIndex;
1335 APInt OffsetHi = DecompGEP1.Offset + *MinAbsVarIndex;
1336 // We know that Offset <= OffsetLo || Offset >= OffsetHi
1337 if (OffsetLo.isNegative() && (-OffsetLo).uge(RHS: V1Size.getValue()) &&
1338 OffsetHi.isNonNegative() && OffsetHi.uge(RHS: V2Size.getValue()))
1339 return AliasResult::NoAlias;
1340 }
1341
1342 // As a last attempt, search for a constant offset between the variable
1343 // indices that GetLinearExpression could not extract through casts.
1344 if (computeConstantOffsetHeuristic(GEP: DecompGEP1, V1Size, V2Size, AC: &AC, DT, AAQI))
1345 return AliasResult::NoAlias;
1346
1347 // Statically, we can see that the base objects are the same, but the
1348 // pointers have dynamic offsets which we can't resolve. And none of our
1349 // little tricks above worked.
1350 return AliasResult::MayAlias;
1351}
1352
1353static AliasResult MergeAliasResults(AliasResult A, AliasResult B) {
1354 // If the results agree, take it.
1355 if (A == B)
1356 return A;
1357 // A mix of PartialAlias and MustAlias is PartialAlias.
1358 if ((A == AliasResult::PartialAlias && B == AliasResult::MustAlias) ||
1359 (B == AliasResult::PartialAlias && A == AliasResult::MustAlias))
1360 return AliasResult::PartialAlias;
1361 // Otherwise, we don't know anything.
1362 return AliasResult::MayAlias;
1363}
1364
1365/// Provides a bunch of ad-hoc rules to disambiguate a Select instruction
1366/// against another.
1367AliasResult
1368BasicAAResult::aliasSelect(const SelectInst *SI, LocationSize SISize,
1369 const Value *V2, LocationSize V2Size,
1370 AAQueryInfo &AAQI) {
1371 // If the values are Selects with the same condition, we can do a more precise
1372 // check: just check for aliases between the values on corresponding arms.
1373 if (const SelectInst *SI2 = dyn_cast<SelectInst>(Val: V2))
1374 if (isValueEqualInPotentialCycles(V1: SI->getCondition(), V2: SI2->getCondition(),
1375 AAQI)) {
1376 AliasResult Alias =
1377 AAQI.AAR.alias(LocA: MemoryLocation(SI->getTrueValue(), SISize),
1378 LocB: MemoryLocation(SI2->getTrueValue(), V2Size), AAQI);
1379 if (Alias == AliasResult::MayAlias)
1380 return AliasResult::MayAlias;
1381 AliasResult ThisAlias =
1382 AAQI.AAR.alias(LocA: MemoryLocation(SI->getFalseValue(), SISize),
1383 LocB: MemoryLocation(SI2->getFalseValue(), V2Size), AAQI);
1384 return MergeAliasResults(A: ThisAlias, B: Alias);
1385 }
1386
1387 // If both arms of the Select node NoAlias or MustAlias V2, then returns
1388 // NoAlias / MustAlias. Otherwise, returns MayAlias.
1389 AliasResult Alias = AAQI.AAR.alias(LocA: MemoryLocation(SI->getTrueValue(), SISize),
1390 LocB: MemoryLocation(V2, V2Size), AAQI);
1391 if (Alias == AliasResult::MayAlias)
1392 return AliasResult::MayAlias;
1393
1394 AliasResult ThisAlias =
1395 AAQI.AAR.alias(LocA: MemoryLocation(SI->getFalseValue(), SISize),
1396 LocB: MemoryLocation(V2, V2Size), AAQI);
1397 return MergeAliasResults(A: ThisAlias, B: Alias);
1398}
1399
1400/// Provide a bunch of ad-hoc rules to disambiguate a PHI instruction against
1401/// another.
1402AliasResult BasicAAResult::aliasPHI(const PHINode *PN, LocationSize PNSize,
1403 const Value *V2, LocationSize V2Size,
1404 AAQueryInfo &AAQI) {
1405 if (!PN->getNumIncomingValues())
1406 return AliasResult::NoAlias;
1407 // If the values are PHIs in the same block, we can do a more precise
1408 // as well as efficient check: just check for aliases between the values
1409 // on corresponding edges. Don't do this if we are analyzing across
1410 // iterations, as we may pick a different phi entry in different iterations.
1411 if (const PHINode *PN2 = dyn_cast<PHINode>(Val: V2))
1412 if (PN2->getParent() == PN->getParent() && !AAQI.MayBeCrossIteration) {
1413 std::optional<AliasResult> Alias;
1414 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1415 AliasResult ThisAlias = AAQI.AAR.alias(
1416 LocA: MemoryLocation(PN->getIncomingValue(i), PNSize),
1417 LocB: MemoryLocation(
1418 PN2->getIncomingValueForBlock(BB: PN->getIncomingBlock(i)), V2Size),
1419 AAQI);
1420 if (Alias)
1421 *Alias = MergeAliasResults(A: *Alias, B: ThisAlias);
1422 else
1423 Alias = ThisAlias;
1424 if (*Alias == AliasResult::MayAlias)
1425 break;
1426 }
1427 return *Alias;
1428 }
1429
1430 SmallVector<Value *, 4> V1Srcs;
1431 // If a phi operand recurses back to the phi, we can still determine NoAlias
1432 // if we don't alias the underlying objects of the other phi operands, as we
1433 // know that the recursive phi needs to be based on them in some way.
1434 bool isRecursive = false;
1435 auto CheckForRecPhi = [&](Value *PV) {
1436 if (!EnableRecPhiAnalysis)
1437 return false;
1438 if (getUnderlyingObject(V: PV) == PN) {
1439 isRecursive = true;
1440 return true;
1441 }
1442 return false;
1443 };
1444
1445 SmallPtrSet<Value *, 4> UniqueSrc;
1446 Value *OnePhi = nullptr;
1447 for (Value *PV1 : PN->incoming_values()) {
1448 // Skip the phi itself being the incoming value.
1449 if (PV1 == PN)
1450 continue;
1451
1452 if (isa<PHINode>(Val: PV1)) {
1453 if (OnePhi && OnePhi != PV1) {
1454 // To control potential compile time explosion, we choose to be
1455 // conserviate when we have more than one Phi input. It is important
1456 // that we handle the single phi case as that lets us handle LCSSA
1457 // phi nodes and (combined with the recursive phi handling) simple
1458 // pointer induction variable patterns.
1459 return AliasResult::MayAlias;
1460 }
1461 OnePhi = PV1;
1462 }
1463
1464 if (CheckForRecPhi(PV1))
1465 continue;
1466
1467 if (UniqueSrc.insert(Ptr: PV1).second)
1468 V1Srcs.push_back(Elt: PV1);
1469 }
1470
1471 if (OnePhi && UniqueSrc.size() > 1)
1472 // Out of an abundance of caution, allow only the trivial lcssa and
1473 // recursive phi cases.
1474 return AliasResult::MayAlias;
1475
1476 // If V1Srcs is empty then that means that the phi has no underlying non-phi
1477 // value. This should only be possible in blocks unreachable from the entry
1478 // block, but return MayAlias just in case.
1479 if (V1Srcs.empty())
1480 return AliasResult::MayAlias;
1481
1482 // If this PHI node is recursive, indicate that the pointer may be moved
1483 // across iterations. We can only prove NoAlias if different underlying
1484 // objects are involved.
1485 if (isRecursive)
1486 PNSize = LocationSize::beforeOrAfterPointer();
1487
1488 // In the recursive alias queries below, we may compare values from two
1489 // different loop iterations.
1490 SaveAndRestore SavedMayBeCrossIteration(AAQI.MayBeCrossIteration, true);
1491
1492 AliasResult Alias = AAQI.AAR.alias(LocA: MemoryLocation(V1Srcs[0], PNSize),
1493 LocB: MemoryLocation(V2, V2Size), AAQI);
1494
1495 // Early exit if the check of the first PHI source against V2 is MayAlias.
1496 // Other results are not possible.
1497 if (Alias == AliasResult::MayAlias)
1498 return AliasResult::MayAlias;
1499 // With recursive phis we cannot guarantee that MustAlias/PartialAlias will
1500 // remain valid to all elements and needs to conservatively return MayAlias.
1501 if (isRecursive && Alias != AliasResult::NoAlias)
1502 return AliasResult::MayAlias;
1503
1504 // If all sources of the PHI node NoAlias or MustAlias V2, then returns
1505 // NoAlias / MustAlias. Otherwise, returns MayAlias.
1506 for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) {
1507 Value *V = V1Srcs[i];
1508
1509 AliasResult ThisAlias = AAQI.AAR.alias(
1510 LocA: MemoryLocation(V, PNSize), LocB: MemoryLocation(V2, V2Size), AAQI);
1511 Alias = MergeAliasResults(A: ThisAlias, B: Alias);
1512 if (Alias == AliasResult::MayAlias)
1513 break;
1514 }
1515
1516 return Alias;
1517}
1518
1519// Return true for an Argument or extractvalue(Argument). These are all known
1520// to not alias with FunctionLocal objects and can come up from coerced function
1521// arguments.
1522static bool isArgumentOrArgumentLike(const Value *V) {
1523 if (isa<Argument>(Val: V))
1524 return true;
1525 auto *E = dyn_cast<ExtractValueInst>(Val: V);
1526 return E && isa<Argument>(Val: E->getOperand(i_nocapture: 0));
1527}
1528
1529/// Provides a bunch of ad-hoc rules to disambiguate in common cases, such as
1530/// array references.
1531AliasResult BasicAAResult::aliasCheck(const Value *V1, LocationSize V1Size,
1532 const Value *V2, LocationSize V2Size,
1533 AAQueryInfo &AAQI,
1534 const Instruction *CtxI) {
1535 // If either of the memory references is empty, it doesn't matter what the
1536 // pointer values are.
1537 if (V1Size.isZero() || V2Size.isZero())
1538 return AliasResult::NoAlias;
1539
1540 // Strip off any casts if they exist.
1541 V1 = V1->stripPointerCastsForAliasAnalysis();
1542 V2 = V2->stripPointerCastsForAliasAnalysis();
1543
1544 // If V1 or V2 is undef, the result is NoAlias because we can always pick a
1545 // value for undef that aliases nothing in the program.
1546 if (isa<UndefValue>(Val: V1) || isa<UndefValue>(Val: V2))
1547 return AliasResult::NoAlias;
1548
1549 // Are we checking for alias of the same value?
1550 // Because we look 'through' phi nodes, we could look at "Value" pointers from
1551 // different iterations. We must therefore make sure that this is not the
1552 // case. The function isValueEqualInPotentialCycles ensures that this cannot
1553 // happen by looking at the visited phi nodes and making sure they cannot
1554 // reach the value.
1555 if (isValueEqualInPotentialCycles(V1, V2, AAQI))
1556 return AliasResult::MustAlias;
1557
1558 // Figure out what objects these things are pointing to if we can.
1559 const Value *O1 = getUnderlyingObject(V: V1, MaxLookup: MaxLookupSearchDepth);
1560 const Value *O2 = getUnderlyingObject(V: V2, MaxLookup: MaxLookupSearchDepth);
1561
1562 // Null values in the default address space don't point to any object, so they
1563 // don't alias any other pointer.
1564 if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(Val: O1))
1565 if (!NullPointerIsDefined(F: &F, AS: CPN->getPointerType()->getAddressSpace()))
1566 return AliasResult::NoAlias;
1567 if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(Val: O2))
1568 if (!NullPointerIsDefined(F: &F, AS: CPN->getPointerType()->getAddressSpace()))
1569 return AliasResult::NoAlias;
1570
1571 if (O1 != O2) {
1572 // If V1/V2 point to two different objects, we know that we have no alias.
1573 if (isIdentifiedObject(V: O1) && isIdentifiedObject(V: O2))
1574 return AliasResult::NoAlias;
1575
1576 // Function arguments can't alias with things that are known to be
1577 // unambigously identified at the function level.
1578 if ((isArgumentOrArgumentLike(V: O1) && isIdentifiedFunctionLocal(V: O2)) ||
1579 (isArgumentOrArgumentLike(V: O2) && isIdentifiedFunctionLocal(V: O1)))
1580 return AliasResult::NoAlias;
1581
1582 // If one pointer is the result of a call/invoke or load and the other is a
1583 // non-escaping local object within the same function, then we know the
1584 // object couldn't escape to a point where the call could return it.
1585 //
1586 // Note that if the pointers are in different functions, there are a
1587 // variety of complications. A call with a nocapture argument may still
1588 // temporary store the nocapture argument's value in a temporary memory
1589 // location if that memory location doesn't escape. Or it may pass a
1590 // nocapture value to other functions as long as they don't capture it.
1591 if (isEscapeSource(V: O1) && capturesNothing(CC: AAQI.CA->getCapturesBefore(
1592 Object: O2, I: dyn_cast<Instruction>(Val: O1), /*OrAt=*/true,
1593 /*ReturnCaptures=*/false)))
1594 return AliasResult::NoAlias;
1595 if (isEscapeSource(V: O2) && capturesNothing(CC: AAQI.CA->getCapturesBefore(
1596 Object: O1, I: dyn_cast<Instruction>(Val: O2), /*OrAt=*/true,
1597 /*ReturnCaptures=*/false)))
1598 return AliasResult::NoAlias;
1599 }
1600
1601 // If the size of one access is larger than the entire object on the other
1602 // side, then we know such behavior is undefined and can assume no alias.
1603 bool NullIsValidLocation = NullPointerIsDefined(F: &F);
1604 if ((isObjectSmallerThan(
1605 V: O2, Size: getMinimalExtentFrom(V: *V1, LocSize: V1Size, DL, NullIsValidLoc: NullIsValidLocation), DL,
1606 TLI, NullIsValidLoc: NullIsValidLocation)) ||
1607 (isObjectSmallerThan(
1608 V: O1, Size: getMinimalExtentFrom(V: *V2, LocSize: V2Size, DL, NullIsValidLoc: NullIsValidLocation), DL,
1609 TLI, NullIsValidLoc: NullIsValidLocation)))
1610 return AliasResult::NoAlias;
1611
1612 if (EnableSeparateStorageAnalysis) {
1613 for (AssumptionCache::ResultElem &Elem : AC.assumptionsFor(V: O1)) {
1614 if (!Elem || Elem.Index == AssumptionCache::ExprResultIdx)
1615 continue;
1616
1617 AssumeInst *Assume = cast<AssumeInst>(Val&: Elem);
1618 OperandBundleUse OBU = Assume->getOperandBundleAt(Index: Elem.Index);
1619 if (OBU.getTagName() == "separate_storage") {
1620 assert(OBU.Inputs.size() == 2);
1621 const Value *Hint1 = OBU.Inputs[0].get();
1622 const Value *Hint2 = OBU.Inputs[1].get();
1623 // This is often a no-op; instcombine rewrites this for us. No-op
1624 // getUnderlyingObject calls are fast, though.
1625 const Value *HintO1 = getUnderlyingObject(V: Hint1);
1626 const Value *HintO2 = getUnderlyingObject(V: Hint2);
1627
1628 DominatorTree *DT = getDT(AAQI);
1629 auto ValidAssumeForPtrContext = [&](const Value *Ptr) {
1630 if (const Instruction *PtrI = dyn_cast<Instruction>(Val: Ptr)) {
1631 return isValidAssumeForContext(I: Assume, CxtI: PtrI, DT,
1632 /* AllowEphemerals */ true);
1633 }
1634 if (const Argument *PtrA = dyn_cast<Argument>(Val: Ptr)) {
1635 const Instruction *FirstI =
1636 &*PtrA->getParent()->getEntryBlock().begin();
1637 return isValidAssumeForContext(I: Assume, CxtI: FirstI, DT,
1638 /* AllowEphemerals */ true);
1639 }
1640 return false;
1641 };
1642
1643 if ((O1 == HintO1 && O2 == HintO2) || (O1 == HintO2 && O2 == HintO1)) {
1644 // Note that we go back to V1 and V2 for the
1645 // ValidAssumeForPtrContext checks; they're dominated by O1 and O2,
1646 // so strictly more assumptions are valid for them.
1647 if ((CtxI && isValidAssumeForContext(I: Assume, CxtI: CtxI, DT,
1648 /* AllowEphemerals */ true)) ||
1649 ValidAssumeForPtrContext(V1) || ValidAssumeForPtrContext(V2)) {
1650 return AliasResult::NoAlias;
1651 }
1652 }
1653 }
1654 }
1655 }
1656
1657 // If one the accesses may be before the accessed pointer, canonicalize this
1658 // by using unknown after-pointer sizes for both accesses. This is
1659 // equivalent, because regardless of which pointer is lower, one of them
1660 // will always came after the other, as long as the underlying objects aren't
1661 // disjoint. We do this so that the rest of BasicAA does not have to deal
1662 // with accesses before the base pointer, and to improve cache utilization by
1663 // merging equivalent states.
1664 if (V1Size.mayBeBeforePointer() || V2Size.mayBeBeforePointer()) {
1665 V1Size = LocationSize::afterPointer();
1666 V2Size = LocationSize::afterPointer();
1667 }
1668
1669 // FIXME: If this depth limit is hit, then we may cache sub-optimal results
1670 // for recursive queries. For this reason, this limit is chosen to be large
1671 // enough to be very rarely hit, while still being small enough to avoid
1672 // stack overflows.
1673 if (AAQI.Depth >= 512)
1674 return AliasResult::MayAlias;
1675
1676 // Check the cache before climbing up use-def chains. This also terminates
1677 // otherwise infinitely recursive queries. Include MayBeCrossIteration in the
1678 // cache key, because some cases where MayBeCrossIteration==false returns
1679 // MustAlias or NoAlias may become MayAlias under MayBeCrossIteration==true.
1680 AAQueryInfo::LocPair Locs({V1, V1Size, AAQI.MayBeCrossIteration},
1681 {V2, V2Size, AAQI.MayBeCrossIteration});
1682 const bool Swapped = V1 > V2;
1683 if (Swapped)
1684 std::swap(a&: Locs.first, b&: Locs.second);
1685 const auto &Pair = AAQI.AliasCache.try_emplace(
1686 Key: Locs, Args: AAQueryInfo::CacheEntry{.Result: AliasResult::NoAlias, .NumAssumptionUses: 0});
1687 if (!Pair.second) {
1688 auto &Entry = Pair.first->second;
1689 if (!Entry.isDefinitive()) {
1690 // Remember that we used an assumption. This may either be a direct use
1691 // of an assumption, or a use of an entry that may itself be based on an
1692 // assumption.
1693 ++AAQI.NumAssumptionUses;
1694 if (Entry.isAssumption())
1695 ++Entry.NumAssumptionUses;
1696 }
1697 // Cache contains sorted {V1,V2} pairs but we should return original order.
1698 auto Result = Entry.Result;
1699 Result.swap(DoSwap: Swapped);
1700 return Result;
1701 }
1702
1703 int OrigNumAssumptionUses = AAQI.NumAssumptionUses;
1704 unsigned OrigNumAssumptionBasedResults = AAQI.AssumptionBasedResults.size();
1705 AliasResult Result =
1706 aliasCheckRecursive(V1, V1Size, V2, V2Size, AAQI, O1, O2);
1707
1708 auto It = AAQI.AliasCache.find(Val: Locs);
1709 assert(It != AAQI.AliasCache.end() && "Must be in cache");
1710 auto &Entry = It->second;
1711
1712 // Check whether a NoAlias assumption has been used, but disproven.
1713 bool AssumptionDisproven =
1714 Entry.NumAssumptionUses > 0 && Result != AliasResult::NoAlias;
1715 if (AssumptionDisproven)
1716 Result = AliasResult::MayAlias;
1717
1718 // This is a definitive result now, when considered as a root query.
1719 AAQI.NumAssumptionUses -= Entry.NumAssumptionUses;
1720 Entry.Result = Result;
1721 // Cache contains sorted {V1,V2} pairs.
1722 Entry.Result.swap(DoSwap: Swapped);
1723
1724 // If the assumption has been disproven, remove any results that may have
1725 // been based on this assumption. Do this after the Entry updates above to
1726 // avoid iterator invalidation.
1727 if (AssumptionDisproven)
1728 while (AAQI.AssumptionBasedResults.size() > OrigNumAssumptionBasedResults)
1729 AAQI.AliasCache.erase(Val: AAQI.AssumptionBasedResults.pop_back_val());
1730
1731 // The result may still be based on assumptions higher up in the chain.
1732 // Remember it, so it can be purged from the cache later.
1733 if (OrigNumAssumptionUses != AAQI.NumAssumptionUses &&
1734 Result != AliasResult::MayAlias) {
1735 AAQI.AssumptionBasedResults.push_back(Elt: Locs);
1736 Entry.NumAssumptionUses = AAQueryInfo::CacheEntry::AssumptionBased;
1737 } else {
1738 Entry.NumAssumptionUses = AAQueryInfo::CacheEntry::Definitive;
1739 }
1740
1741 // Depth is incremented before this function is called, so Depth==1 indicates
1742 // a root query.
1743 if (AAQI.Depth == 1) {
1744 // Any remaining assumption based results must be based on proven
1745 // assumptions, so convert them to definitive results.
1746 for (const auto &Loc : AAQI.AssumptionBasedResults) {
1747 auto It = AAQI.AliasCache.find(Val: Loc);
1748 if (It != AAQI.AliasCache.end())
1749 It->second.NumAssumptionUses = AAQueryInfo::CacheEntry::Definitive;
1750 }
1751 AAQI.AssumptionBasedResults.clear();
1752 AAQI.NumAssumptionUses = 0;
1753 }
1754 return Result;
1755}
1756
1757AliasResult BasicAAResult::aliasCheckRecursive(
1758 const Value *V1, LocationSize V1Size,
1759 const Value *V2, LocationSize V2Size,
1760 AAQueryInfo &AAQI, const Value *O1, const Value *O2) {
1761 if (const GEPOperator *GV1 = dyn_cast<GEPOperator>(Val: V1)) {
1762 AliasResult Result = aliasGEP(GEP1: GV1, V1Size, V2, V2Size, UnderlyingV1: O1, UnderlyingV2: O2, AAQI);
1763 if (Result != AliasResult::MayAlias)
1764 return Result;
1765 } else if (const GEPOperator *GV2 = dyn_cast<GEPOperator>(Val: V2)) {
1766 AliasResult Result = aliasGEP(GEP1: GV2, V1Size: V2Size, V2: V1, V2Size: V1Size, UnderlyingV1: O2, UnderlyingV2: O1, AAQI);
1767 Result.swap();
1768 if (Result != AliasResult::MayAlias)
1769 return Result;
1770 }
1771
1772 if (const PHINode *PN = dyn_cast<PHINode>(Val: V1)) {
1773 AliasResult Result = aliasPHI(PN, PNSize: V1Size, V2, V2Size, AAQI);
1774 if (Result != AliasResult::MayAlias)
1775 return Result;
1776 } else if (const PHINode *PN = dyn_cast<PHINode>(Val: V2)) {
1777 AliasResult Result = aliasPHI(PN, PNSize: V2Size, V2: V1, V2Size: V1Size, AAQI);
1778 Result.swap();
1779 if (Result != AliasResult::MayAlias)
1780 return Result;
1781 }
1782
1783 if (const SelectInst *S1 = dyn_cast<SelectInst>(Val: V1)) {
1784 AliasResult Result = aliasSelect(SI: S1, SISize: V1Size, V2, V2Size, AAQI);
1785 if (Result != AliasResult::MayAlias)
1786 return Result;
1787 } else if (const SelectInst *S2 = dyn_cast<SelectInst>(Val: V2)) {
1788 AliasResult Result = aliasSelect(SI: S2, SISize: V2Size, V2: V1, V2Size: V1Size, AAQI);
1789 Result.swap();
1790 if (Result != AliasResult::MayAlias)
1791 return Result;
1792 }
1793
1794 // If both pointers are pointing into the same object and one of them
1795 // accesses the entire object, then the accesses must overlap in some way.
1796 if (O1 == O2) {
1797 bool NullIsValidLocation = NullPointerIsDefined(F: &F);
1798 if (V1Size.isPrecise() && V2Size.isPrecise() &&
1799 (isObjectSize(V: O1, Size: V1Size.getValue(), DL, TLI, NullIsValidLoc: NullIsValidLocation) ||
1800 isObjectSize(V: O2, Size: V2Size.getValue(), DL, TLI, NullIsValidLoc: NullIsValidLocation)))
1801 return AliasResult::PartialAlias;
1802 }
1803
1804 return AliasResult::MayAlias;
1805}
1806
1807AliasResult BasicAAResult::aliasErrno(const MemoryLocation &Loc,
1808 const Instruction *CtxI) {
1809 // Do not make any assumptions when targeting freestanding environments (e.g.,
1810 // in the context of baremetal LTO, errno may have been internalized or
1811 // otherwise promoted to a local variable).
1812 bool IsFreestanding = CtxI->getFunction()->hasFnAttribute(Kind: "no-builtins");
1813 if (IsFreestanding)
1814 return AliasResult::MayAlias;
1815
1816 // There cannot be any alias with errno if the given memory location is an
1817 // identified function-local object, or the size of the memory access is
1818 // larger than the integer size.
1819 if (Loc.Size.hasValue() &&
1820 Loc.Size.getValue().getKnownMinValue() * 8 > TLI.getIntSize())
1821 return AliasResult::NoAlias;
1822
1823 const Value *Object = getUnderlyingObject(V: Loc.Ptr);
1824 if (isIdentifiedFunctionLocal(V: Object))
1825 return AliasResult::NoAlias;
1826
1827 if (auto *GV = dyn_cast<GlobalVariable>(Val: Object)) {
1828 // Errno cannot alias internal/private globals.
1829 if (GV->hasLocalLinkage())
1830 return AliasResult::NoAlias;
1831
1832 // Neither can errno alias globals where environments define it as a
1833 // function call.
1834 if (TLI.isErrnoFunctionCall())
1835 return AliasResult::NoAlias;
1836 }
1837
1838 return AliasResult::MayAlias;
1839}
1840
1841/// Check whether two Values can be considered equivalent.
1842///
1843/// If the values may come from different cycle iterations, this will also
1844/// check that the values are not part of cycle. We have to do this because we
1845/// are looking through phi nodes, that is we say
1846/// noalias(V, phi(VA, VB)) if noalias(V, VA) and noalias(V, VB).
1847bool BasicAAResult::isValueEqualInPotentialCycles(const Value *V,
1848 const Value *V2,
1849 const AAQueryInfo &AAQI) {
1850 if (V != V2)
1851 return false;
1852
1853 if (!AAQI.MayBeCrossIteration)
1854 return true;
1855
1856 // Non-instructions and instructions in the entry block cannot be part of
1857 // a loop.
1858 const Instruction *Inst = dyn_cast<Instruction>(Val: V);
1859 if (!Inst || Inst->getParent()->isEntryBlock())
1860 return true;
1861
1862 return isNotInCycle(I: Inst, DT: getDT(AAQI), /*LI=*/nullptr, /*CI=*/nullptr);
1863}
1864
1865/// Computes the symbolic difference between two de-composed GEPs.
1866void BasicAAResult::subtractDecomposedGEPs(DecomposedGEP &DestGEP,
1867 const DecomposedGEP &SrcGEP,
1868 const AAQueryInfo &AAQI) {
1869 // Drop nuw flag from GEP if subtraction of constant offsets overflows in an
1870 // unsigned sense.
1871 if (DestGEP.Offset.ult(RHS: SrcGEP.Offset))
1872 DestGEP.NWFlags = DestGEP.NWFlags.withoutNoUnsignedWrap();
1873
1874 DestGEP.Offset -= SrcGEP.Offset;
1875 for (const VariableGEPIndex &Src : SrcGEP.VarIndices) {
1876 // Find V in Dest. This is N^2, but pointer indices almost never have more
1877 // than a few variable indexes.
1878 bool Found = false;
1879 for (auto I : enumerate(First&: DestGEP.VarIndices)) {
1880 VariableGEPIndex &Dest = I.value();
1881 if ((!isValueEqualInPotentialCycles(V: Dest.Val.V, V2: Src.Val.V, AAQI) &&
1882 !areBothVScale(V1: Dest.Val.V, V2: Src.Val.V)) ||
1883 !Dest.Val.hasSameCastsAs(Other: Src.Val))
1884 continue;
1885
1886 // Normalize IsNegated if we're going to lose the NSW flag anyway.
1887 if (Dest.IsNegated) {
1888 Dest.Scale = -Dest.Scale;
1889 Dest.IsNegated = false;
1890 Dest.IsNSW = false;
1891 }
1892
1893 // If we found it, subtract off Scale V's from the entry in Dest. If it
1894 // goes to zero, remove the entry.
1895 if (Dest.Scale != Src.Scale) {
1896 // Drop nuw flag from GEP if subtraction of V's Scale overflows in an
1897 // unsigned sense.
1898 if (Dest.Scale.ult(RHS: Src.Scale))
1899 DestGEP.NWFlags = DestGEP.NWFlags.withoutNoUnsignedWrap();
1900
1901 Dest.Scale -= Src.Scale;
1902 Dest.IsNSW = false;
1903 } else {
1904 DestGEP.VarIndices.erase(CI: DestGEP.VarIndices.begin() + I.index());
1905 }
1906 Found = true;
1907 break;
1908 }
1909
1910 // If we didn't consume this entry, add it to the end of the Dest list.
1911 if (!Found) {
1912 VariableGEPIndex Entry = {.Val: Src.Val, .Scale: Src.Scale, .CxtI: Src.CxtI, .IsNSW: Src.IsNSW,
1913 /* IsNegated */ true};
1914 DestGEP.VarIndices.push_back(Elt: Entry);
1915
1916 // Drop nuw flag when we have unconsumed variable indices from SrcGEP.
1917 DestGEP.NWFlags = DestGEP.NWFlags.withoutNoUnsignedWrap();
1918 }
1919 }
1920}
1921
1922BasicAAResult::VariableGEPOffsetInfo
1923BasicAAResult::analyzeVariableOffsets(const DecomposedGEP &GEP,
1924 DominatorTree *DT) {
1925 APInt GCD;
1926 ConstantRange OffsetRange(GEP.Offset);
1927
1928 for (unsigned I = 0, E = GEP.VarIndices.size(); I != E; ++I) {
1929 const VariableGEPIndex &Index = GEP.VarIndices[I];
1930 const APInt &Scale = Index.Scale;
1931
1932 SimplifyQuery SQ(DL, DT, &AC, Index.CxtI, /*UseInstrInfo=*/true);
1933 KnownBits Known = computeKnownBits(V: Index.Val.V, Q: SQ);
1934
1935 APInt ScaleForGCD = Scale;
1936 if (!Index.IsNSW)
1937 ScaleForGCD =
1938 APInt::getOneBitSet(numBits: Scale.getBitWidth(), BitNo: Scale.countr_zero());
1939
1940 // If V has known trailing zeros, V is a multiple of 2^VarTZ, so
1941 // V*Scale is a multiple of ScaleForGCD * 2^VarTZ. Shift ScaleForGCD
1942 // left to account for this (trailing zeros compose additively through
1943 // multiplication, even in Z/2^n).
1944 unsigned VarTZ = Known.countMinTrailingZeros();
1945 if (VarTZ > 0) {
1946 unsigned MaxShift =
1947 Scale.getBitWidth() - ScaleForGCD.getSignificantBits();
1948 ScaleForGCD <<= std::min(a: VarTZ, b: MaxShift);
1949 }
1950
1951 if (I == 0)
1952 GCD = ScaleForGCD.abs();
1953 else
1954 GCD = APIntOps::GreatestCommonDivisor(A: GCD, B: ScaleForGCD.abs());
1955
1956 ConstantRange CR =
1957 computeConstantRange(V: Index.Val.V, /*ForSigned=*/false, SQ);
1958 CR =
1959 CR.intersectWith(CR: ConstantRange::fromKnownBits(Known, /*IsSigned=*/true),
1960 Type: ConstantRange::Signed);
1961 CR = Index.Val.evaluateWith(N: CR).sextOrTrunc(BitWidth: OffsetRange.getBitWidth());
1962
1963 assert(OffsetRange.getBitWidth() == Scale.getBitWidth() &&
1964 "Bit widths are normalized to MaxIndexSize");
1965 if (Index.IsNSW)
1966 CR = CR.smul_sat(Other: ConstantRange(Scale));
1967 else
1968 CR = CR.smul_fast(Other: ConstantRange(Scale));
1969
1970 if (Index.IsNegated)
1971 OffsetRange = OffsetRange.sub(Other: CR);
1972 else
1973 OffsetRange = OffsetRange.add(Other: CR);
1974 }
1975
1976 return {.GCD: GCD, .OffsetRange: OffsetRange};
1977}
1978
1979std::optional<APInt> BasicAAResult::computeMinAbsVarOffset(
1980 const DecomposedGEP &GEP, DominatorTree *DT, const AAQueryInfo &AAQI) {
1981 // Check if abs(V*Scale) >= abs(Scale) holds in the presence of
1982 // potentially wrapping math.
1983 auto MultiplyByScaleNoWrap = [](const VariableGEPIndex &Var) {
1984 if (Var.IsNSW)
1985 return true;
1986
1987 int ValOrigBW = Var.Val.V->getType()->getPrimitiveSizeInBits();
1988 // If Scale is small enough so that abs(V*Scale) >= abs(Scale) holds.
1989 // The max value of abs(V) is 2^ValOrigBW - 1. Multiplying with a
1990 // constant smaller than 2^(bitwidth(Val) - ValOrigBW) won't wrap.
1991 int MaxScaleValueBW = Var.Val.getBitWidth() - ValOrigBW;
1992 if (MaxScaleValueBW <= 0)
1993 return false;
1994 return Var.Scale.ule(
1995 RHS: APInt::getMaxValue(numBits: MaxScaleValueBW).zext(width: Var.Scale.getBitWidth()));
1996 };
1997
1998 const auto &VarIndices = GEP.VarIndices;
1999 if (VarIndices.size() == 1) {
2000 // VarIndex = Scale*V.
2001 const VariableGEPIndex &Var = VarIndices[0];
2002 if (Var.Val.TruncBits == 0 &&
2003 isKnownNonZero(V: Var.Val.V, Q: SimplifyQuery(DL, DT, &AC, Var.CxtI))) {
2004 // Refine MinAbsVarIndex, if abs(Scale*V) >= abs(Scale) holds in the
2005 // presence of potentially wrapping math.
2006 if (MultiplyByScaleNoWrap(Var)) {
2007 // If V != 0 then abs(VarIndex) >= abs(Scale).
2008 return Var.Scale.abs();
2009 }
2010 }
2011 return std::nullopt;
2012 }
2013
2014 if (VarIndices.size() == 2) {
2015 // VarIndex = Scale*V0 + (-Scale)*V1.
2016 // If V0 != V1 then abs(VarIndex) >= abs(Scale).
2017 // Check that MayBeCrossIteration is false, to avoid reasoning about
2018 // inequality of values across loop iterations.
2019 const VariableGEPIndex &Var0 = VarIndices[0];
2020 const VariableGEPIndex &Var1 = VarIndices[1];
2021 if (Var0.hasNegatedScaleOf(Other: Var1) && Var0.Val.TruncBits == 0 &&
2022 Var0.Val.hasSameCastsAs(Other: Var1.Val) && !AAQI.MayBeCrossIteration &&
2023 MultiplyByScaleNoWrap(Var0) && MultiplyByScaleNoWrap(Var1) &&
2024 isKnownNonEqual(V1: Var0.Val.V, V2: Var1.Val.V,
2025 SQ: SimplifyQuery(DL, DT, &AC, /*CxtI=*/Var0.CxtI
2026 ? Var0.CxtI
2027 : Var1.CxtI)))
2028 return Var0.Scale.abs();
2029 }
2030
2031 return std::nullopt;
2032}
2033
2034bool BasicAAResult::computeConstantOffsetHeuristic(const DecomposedGEP &GEP,
2035 LocationSize MaybeV1Size,
2036 LocationSize MaybeV2Size,
2037 AssumptionCache *AC,
2038 DominatorTree *DT,
2039 const AAQueryInfo &AAQI) {
2040 if (GEP.VarIndices.size() != 2 || !MaybeV1Size.hasValue() ||
2041 !MaybeV2Size.hasValue())
2042 return false;
2043
2044 const uint64_t V1Size = MaybeV1Size.getValue();
2045 const uint64_t V2Size = MaybeV2Size.getValue();
2046
2047 const VariableGEPIndex &Var0 = GEP.VarIndices[0], &Var1 = GEP.VarIndices[1];
2048
2049 if (Var0.Val.TruncBits != 0 || !Var0.Val.hasSameCastsAs(Other: Var1.Val) ||
2050 !Var0.hasNegatedScaleOf(Other: Var1) ||
2051 Var0.Val.V->getType() != Var1.Val.V->getType())
2052 return false;
2053
2054 // We'll strip off the Extensions of Var0 and Var1 and do another round
2055 // of GetLinearExpression decomposition. In the example above, if Var0
2056 // is zext(%x + 1) we should get V1 == %x and V1Offset == 1.
2057
2058 LinearExpression E0 =
2059 GetLinearExpression(Val: CastedValue(Var0.Val.V), DL, Depth: 0, AC, DT);
2060 LinearExpression E1 =
2061 GetLinearExpression(Val: CastedValue(Var1.Val.V), DL, Depth: 0, AC, DT);
2062 if (E0.Scale != E1.Scale || !E0.Val.hasSameCastsAs(Other: E1.Val) ||
2063 !isValueEqualInPotentialCycles(V: E0.Val.V, V2: E1.Val.V, AAQI))
2064 return false;
2065
2066 // We have a hit - Var0 and Var1 only differ by a constant offset!
2067
2068 // If we've been sext'ed then zext'd the maximum difference between Var0 and
2069 // Var1 is possible to calculate, but we're just interested in the absolute
2070 // minimum difference between the two. The minimum distance may occur due to
2071 // wrapping; consider "add i3 %i, 5": if %i == 7 then 7 + 5 mod 8 == 4, and so
2072 // the minimum distance between %i and %i + 5 is 3.
2073 APInt MinDiff = E0.Offset - E1.Offset, Wrapped = -MinDiff;
2074 MinDiff = APIntOps::umin(A: MinDiff, B: Wrapped);
2075 APInt MinDiffBytes =
2076 MinDiff.zextOrTrunc(width: Var0.Scale.getBitWidth()) * Var0.Scale.abs();
2077
2078 // We can't definitely say whether GEP1 is before or after V2 due to wrapping
2079 // arithmetic (i.e. for some values of GEP1 and V2 GEP1 < V2, and for other
2080 // values GEP1 > V2). We'll therefore only declare NoAlias if both V1Size and
2081 // V2Size can fit in the MinDiffBytes gap.
2082 return MinDiffBytes.uge(RHS: V1Size + GEP.Offset.abs()) &&
2083 MinDiffBytes.uge(RHS: V2Size + GEP.Offset.abs());
2084}
2085
2086//===----------------------------------------------------------------------===//
2087// BasicAliasAnalysis Pass
2088//===----------------------------------------------------------------------===//
2089
2090AnalysisKey BasicAA::Key;
2091
2092BasicAAResult BasicAA::run(Function &F, FunctionAnalysisManager &AM) {
2093 auto &TLI = AM.getResult<TargetLibraryAnalysis>(IR&: F);
2094 auto &AC = AM.getResult<AssumptionAnalysis>(IR&: F);
2095 auto *DT = &AM.getResult<DominatorTreeAnalysis>(IR&: F);
2096 return BasicAAResult(F.getDataLayout(), F, TLI, AC, DT);
2097}
2098
2099BasicAAWrapperPass::BasicAAWrapperPass() : FunctionPass(ID) {}
2100
2101char BasicAAWrapperPass::ID = 0;
2102
2103void BasicAAWrapperPass::anchor() {}
2104
2105INITIALIZE_PASS_BEGIN(BasicAAWrapperPass, "basic-aa",
2106 "Basic Alias Analysis (stateless AA impl)", true, true)
2107INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
2108INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
2109INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
2110INITIALIZE_PASS_END(BasicAAWrapperPass, "basic-aa",
2111 "Basic Alias Analysis (stateless AA impl)", true, true)
2112
2113FunctionPass *llvm::createBasicAAWrapperPass() {
2114 return new BasicAAWrapperPass();
2115}
2116
2117bool BasicAAWrapperPass::runOnFunction(Function &F) {
2118 auto &ACT = getAnalysis<AssumptionCacheTracker>();
2119 auto &TLIWP = getAnalysis<TargetLibraryInfoWrapperPass>();
2120 auto &DTWP = getAnalysis<DominatorTreeWrapperPass>();
2121
2122 Result.reset(p: new BasicAAResult(F.getDataLayout(), F,
2123 TLIWP.getTLI(F), ACT.getAssumptionCache(F),
2124 &DTWP.getDomTree()));
2125
2126 return false;
2127}
2128
2129void BasicAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
2130 AU.setPreservesAll();
2131 AU.addRequiredTransitive<AssumptionCacheTracker>();
2132 AU.addRequiredTransitive<DominatorTreeWrapperPass>();
2133 AU.addRequiredTransitive<TargetLibraryInfoWrapperPass>();
2134}
2135