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
589/// If V is a symbolic pointer expression, decompose it into a base pointer
590/// with a constant offset and a number of scaled symbolic offsets.
591///
592/// The scaled symbolic offsets (represented by pairs of a Value* and a scale
593/// in the VarIndices vector) are Value*'s that are known to be scaled by the
594/// specified amount, but which may have other unrepresented high bits. As
595/// such, the gep cannot necessarily be reconstructed from its decomposed form.
596BasicAAResult::DecomposedGEP
597BasicAAResult::DecomposeGEPExpression(const Value *V, const DataLayout &DL,
598 AssumptionCache *AC, DominatorTree *DT) {
599 // Limit recursion depth to limit compile time in crazy cases.
600 unsigned MaxLookup = MaxLookupSearchDepth;
601 SearchTimes++;
602 const Instruction *CxtI = dyn_cast<Instruction>(Val: V);
603
604 unsigned IndexSize = DL.getIndexTypeSizeInBits(Ty: V->getType());
605 DecomposedGEP Decomposed;
606 Decomposed.Offset = APInt(IndexSize, 0);
607 do {
608 // See if this is a bitcast or GEP.
609 const Operator *Op = dyn_cast<Operator>(Val: V);
610 if (!Op) {
611 // The only non-operator case we can handle are GlobalAliases.
612 if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(Val: V)) {
613 if (!GA->isInterposable()) {
614 V = GA->getAliasee();
615 continue;
616 }
617 }
618 Decomposed.Base = V;
619 return Decomposed;
620 }
621
622 if (Op->getOpcode() == Instruction::BitCast ||
623 Op->getOpcode() == Instruction::AddrSpaceCast) {
624 Value *NewV = Op->getOperand(i: 0);
625 auto *NewVTy = NewV->getType();
626 // Don't look through casts to non-scalar-pointer types or address spaces
627 // with differing index widths.
628 if (!isa<PointerType>(Val: NewVTy) ||
629 DL.getIndexTypeSizeInBits(Ty: NewVTy) != IndexSize) {
630 Decomposed.Base = V;
631 return Decomposed;
632 }
633 V = NewV;
634 continue;
635 }
636
637 const GEPOperator *GEPOp = dyn_cast<GEPOperator>(Val: Op);
638 if (!GEPOp) {
639 if (const auto *PHI = dyn_cast<PHINode>(Val: V)) {
640 // Look through single-arg phi nodes created by LCSSA.
641 if (PHI->getNumIncomingValues() == 1) {
642 V = PHI->getIncomingValue(i: 0);
643 continue;
644 }
645 } else if (const auto *Call = dyn_cast<CallBase>(Val: V)) {
646 // CaptureTracking can know about special capturing properties of some
647 // intrinsics like launder.invariant.group, that can't be expressed with
648 // the attributes, but have properties like returning aliasing pointer.
649 // Because some analysis may assume that nocaptured pointer is not
650 // returned from some special intrinsic (because function would have to
651 // be marked with returns attribute), it is crucial to use this function
652 // because it should be in sync with CaptureTracking. Not using it may
653 // cause weird miscompilations where 2 aliasing pointers are assumed to
654 // noalias.
655 // Pass MustPreserveOffset=true so we exclude llvm.ptrmask, which can
656 // change the byte offset by clearing low bits and would otherwise
657 // corrupt the symbolic offset we are accumulating in `Decomposed`.
658 if (auto *RP = getArgumentAliasingToReturnedPointer(
659 Call, /*MustPreserveOffset=*/true)) {
660 V = RP;
661 continue;
662 }
663 }
664
665 Decomposed.Base = V;
666 return Decomposed;
667 }
668
669 // Track the common nowrap flags for all GEPs we see.
670 Decomposed.NWFlags &= GEPOp->getNoWrapFlags();
671
672 assert(GEPOp->getSourceElementType()->isSized() && "GEP must be sized");
673
674 // Walk the indices of the GEP, accumulating them into BaseOff/VarIndices.
675 gep_type_iterator GTI = gep_type_begin(GEP: GEPOp);
676 for (User::const_op_iterator I = GEPOp->op_begin() + 1, E = GEPOp->op_end();
677 I != E; ++I, ++GTI) {
678 const Value *Index = *I;
679 // Compute the (potentially symbolic) offset in bytes for this index.
680 if (StructType *STy = GTI.getStructTypeOrNull()) {
681 // For a struct, add the member offset.
682 unsigned FieldNo = cast<ConstantInt>(Val: Index)->getZExtValue();
683 if (FieldNo == 0)
684 continue;
685
686 Decomposed.Offset += DL.getStructLayout(Ty: STy)->getElementOffset(Idx: FieldNo);
687 continue;
688 }
689
690 // For an array/pointer, add the element offset, explicitly scaled.
691 if (const ConstantInt *CIdx = dyn_cast<ConstantInt>(Val: Index)) {
692 if (CIdx->isZero())
693 continue;
694
695 // Don't attempt to analyze GEPs if the scalable index is not zero.
696 TypeSize AllocTypeSize = GTI.getSequentialElementStride(DL);
697 if (AllocTypeSize.isScalable()) {
698 Decomposed.Base = V;
699 return Decomposed;
700 }
701
702 Decomposed.Offset += AllocTypeSize.getFixedValue() *
703 CIdx->getValue().sextOrTrunc(width: IndexSize);
704 continue;
705 }
706
707 TypeSize AllocTypeSize = GTI.getSequentialElementStride(DL);
708 if (AllocTypeSize.isScalable()) {
709 Decomposed.Base = V;
710 return Decomposed;
711 }
712
713 // If the integer type is smaller than the index size, it is implicitly
714 // sign extended or truncated to index size.
715 bool NUSW = GEPOp->hasNoUnsignedSignedWrap();
716 bool NUW = GEPOp->hasNoUnsignedWrap();
717 bool NonNeg = NUSW && NUW;
718 unsigned Width = Index->getType()->getIntegerBitWidth();
719 unsigned SExtBits = IndexSize > Width ? IndexSize - Width : 0;
720 unsigned TruncBits = IndexSize < Width ? Width - IndexSize : 0;
721 LinearExpression LE = GetLinearExpression(
722 Val: CastedValue(Index, 0, SExtBits, TruncBits, NonNeg), DL, Depth: 0, AC, DT);
723
724 // Scale by the type size.
725 unsigned TypeSize = AllocTypeSize.getFixedValue();
726 LE = LE.mul(Other: APInt(IndexSize, TypeSize), MulIsNUW: NUW, MulIsNSW: NUSW);
727 Decomposed.Offset += LE.Offset;
728 APInt Scale = LE.Scale;
729 if (!LE.IsNUW)
730 Decomposed.NWFlags = Decomposed.NWFlags.withoutNoUnsignedWrap();
731
732 // If we already had an occurrence of this index variable, merge this
733 // scale into it. For example, we want to handle:
734 // A[x][x] -> x*16 + x*4 -> x*20
735 // This also ensures that 'x' only appears in the index list once.
736 for (unsigned i = 0, e = Decomposed.VarIndices.size(); i != e; ++i) {
737 if ((Decomposed.VarIndices[i].Val.V == LE.Val.V ||
738 areBothVScale(V1: Decomposed.VarIndices[i].Val.V, V2: LE.Val.V)) &&
739 Decomposed.VarIndices[i].Val.hasSameCastsAs(Other: LE.Val)) {
740 Scale += Decomposed.VarIndices[i].Scale;
741 // We cannot guarantee no-wrap for the merge.
742 LE.IsNSW = LE.IsNUW = false;
743 Decomposed.VarIndices.erase(CI: Decomposed.VarIndices.begin() + i);
744 break;
745 }
746 }
747
748 if (!!Scale) {
749 VariableGEPIndex Entry = {.Val: LE.Val, .Scale: Scale, .CxtI: CxtI, .IsNSW: LE.IsNSW,
750 /* IsNegated */ false};
751 Decomposed.VarIndices.push_back(Elt: Entry);
752 }
753 }
754
755 // Analyze the base pointer next.
756 V = GEPOp->getOperand(i_nocapture: 0);
757 } while (--MaxLookup);
758
759 // If the chain of expressions is too deep, just return early.
760 Decomposed.Base = V;
761 SearchLimitReached++;
762 return Decomposed;
763}
764
765ModRefInfo BasicAAResult::getModRefInfoMask(const MemoryLocation &Loc,
766 AAQueryInfo &AAQI,
767 bool IgnoreLocals) {
768 assert(Visited.empty() && "Visited must be cleared after use!");
769 llvm::scope_exit _([&] { Visited.clear(); });
770
771 unsigned MaxLookup = 8;
772 SmallVector<const Value *, 16> Worklist;
773 Worklist.push_back(Elt: Loc.Ptr);
774 ModRefInfo Result = ModRefInfo::NoModRef;
775
776 do {
777 const Value *V = getUnderlyingObject(V: Worklist.pop_back_val());
778 if (!Visited.insert(Ptr: V).second)
779 continue;
780
781 // Ignore allocas if we were instructed to do so.
782 if (IgnoreLocals && isa<AllocaInst>(Val: V))
783 continue;
784
785 // If the location points to memory that is known to be invariant for
786 // the life of the underlying SSA value, then we can exclude Mod from
787 // the set of valid memory effects.
788 //
789 // An argument that is marked readonly and noalias is known to be
790 // invariant while that function is executing.
791 if (const Argument *Arg = dyn_cast<Argument>(Val: V)) {
792 if (Arg->hasNoAliasAttr() && Arg->onlyReadsMemory()) {
793 Result |= ModRefInfo::Ref;
794 continue;
795 }
796 }
797
798 // A global constant can't be mutated.
799 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(Val: V)) {
800 // Note: this doesn't require GV to be "ODR" because it isn't legal for a
801 // global to be marked constant in some modules and non-constant in
802 // others. GV may even be a declaration, not a definition.
803 if (!GV->isConstant())
804 return ModRefInfo::ModRef;
805 continue;
806 }
807
808 // If both select values point to local memory, then so does the select.
809 if (const SelectInst *SI = dyn_cast<SelectInst>(Val: V)) {
810 Worklist.push_back(Elt: SI->getTrueValue());
811 Worklist.push_back(Elt: SI->getFalseValue());
812 continue;
813 }
814
815 // If all values incoming to a phi node point to local memory, then so does
816 // the phi.
817 if (const PHINode *PN = dyn_cast<PHINode>(Val: V)) {
818 // Don't bother inspecting phi nodes with many operands.
819 if (PN->getNumIncomingValues() > MaxLookup)
820 return ModRefInfo::ModRef;
821 append_range(C&: Worklist, R: PN->incoming_values());
822 continue;
823 }
824
825 // Otherwise be conservative.
826 return ModRefInfo::ModRef;
827 } while (!Worklist.empty() && --MaxLookup);
828
829 // If we hit the maximum number of instructions to examine, be conservative.
830 if (!Worklist.empty())
831 return ModRefInfo::ModRef;
832
833 return Result;
834}
835
836static bool isIntrinsicCall(const CallBase *Call, Intrinsic::ID IID) {
837 const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Val: Call);
838 return II && II->getIntrinsicID() == IID;
839}
840
841/// Returns the behavior when calling the given call site.
842MemoryEffects BasicAAResult::getMemoryEffects(const CallBase *Call,
843 AAQueryInfo &AAQI) {
844 MemoryEffects Min = Call->getAttributes().getMemoryEffects();
845
846 if (const Function *F = dyn_cast<Function>(Val: Call->getCalledOperand())) {
847 MemoryEffects FuncME = AAQI.AAR.getMemoryEffects(F);
848 // Operand bundles on the call may also read or write memory, in addition
849 // to the behavior of the called function.
850 if (Call->hasReadingOperandBundles())
851 FuncME |= MemoryEffects::readOnly();
852 if (Call->hasClobberingOperandBundles())
853 FuncME |= MemoryEffects::writeOnly();
854 if (Call->isVolatile()) {
855 // Volatile operations also access inaccessible memory.
856 FuncME |= MemoryEffects::inaccessibleMemOnly();
857 }
858 Min &= FuncME;
859 }
860
861 return Min;
862}
863
864/// Returns the behavior when calling the given function. For use when the call
865/// site is not known.
866MemoryEffects BasicAAResult::getMemoryEffects(const Function *F) {
867 switch (F->getIntrinsicID()) {
868 case Intrinsic::experimental_guard:
869 case Intrinsic::experimental_deoptimize:
870 // These intrinsics can read arbitrary memory, and additionally modref
871 // inaccessible memory to model control dependence.
872 return MemoryEffects::readOnly() |
873 MemoryEffects::inaccessibleMemOnly(MR: ModRefInfo::ModRef);
874 }
875
876 return F->getMemoryEffects();
877}
878
879ModRefInfo BasicAAResult::getArgModRefInfo(const CallBase *Call,
880 unsigned ArgIdx) {
881 if (Call->doesNotAccessMemory(OpNo: ArgIdx))
882 return ModRefInfo::NoModRef;
883
884 if (Call->onlyWritesMemory(OpNo: ArgIdx))
885 return ModRefInfo::Mod;
886
887 if (Call->onlyReadsMemory(OpNo: ArgIdx))
888 return ModRefInfo::Ref;
889
890 return ModRefInfo::ModRef;
891}
892
893#ifndef NDEBUG
894static const Function *getParent(const Value *V) {
895 if (const Instruction *inst = dyn_cast<Instruction>(V)) {
896 if (!inst->getParent())
897 return nullptr;
898 return inst->getParent()->getParent();
899 }
900
901 if (const Argument *arg = dyn_cast<Argument>(V))
902 return arg->getParent();
903
904 return nullptr;
905}
906
907static bool notDifferentParent(const Value *O1, const Value *O2) {
908
909 const Function *F1 = getParent(O1);
910 const Function *F2 = getParent(O2);
911
912 return !F1 || !F2 || F1 == F2;
913}
914#endif
915
916AliasResult BasicAAResult::alias(const MemoryLocation &LocA,
917 const MemoryLocation &LocB, AAQueryInfo &AAQI,
918 const Instruction *CtxI) {
919 assert(notDifferentParent(LocA.Ptr, LocB.Ptr) &&
920 "BasicAliasAnalysis doesn't support interprocedural queries.");
921 return aliasCheck(V1: LocA.Ptr, V1Size: LocA.Size, V2: LocB.Ptr, V2Size: LocB.Size, AAQI, CtxI);
922}
923
924/// Checks to see if the specified callsite can clobber the specified memory
925/// object.
926///
927/// Since we only look at local properties of this function, we really can't
928/// say much about this query. We do, however, use simple "address taken"
929/// analysis on local objects.
930ModRefInfo BasicAAResult::getModRefInfo(const CallBase *Call,
931 const MemoryLocation &Loc,
932 AAQueryInfo &AAQI) {
933 assert(notDifferentParent(Call, Loc.Ptr) &&
934 "AliasAnalysis query involving multiple functions!");
935
936 const Value *Object = getUnderlyingObject(V: Loc.Ptr);
937
938 // Calls marked 'tail' cannot read or write allocas from the current frame
939 // because the current frame might be destroyed by the time they run. However,
940 // a tail call may use an alloca with byval. Calling with byval copies the
941 // contents of the alloca into argument registers or stack slots, so there is
942 // no lifetime issue.
943 if (isa<AllocaInst>(Val: Object))
944 if (const CallInst *CI = dyn_cast<CallInst>(Val: Call))
945 if (CI->isTailCall() &&
946 !CI->getAttributes().hasAttrSomewhere(Kind: Attribute::ByVal))
947 return ModRefInfo::NoModRef;
948
949 // Stack restore is able to modify unescaped dynamic allocas. Assume it may
950 // modify them even though the alloca is not escaped.
951 if (auto *AI = dyn_cast<AllocaInst>(Val: Object))
952 if (!AI->isStaticAlloca() && isIntrinsicCall(Call, IID: Intrinsic::stackrestore))
953 return ModRefInfo::Mod;
954
955 // We can completely ignore inaccessible memory here, because MemoryLocations
956 // can only reference accessible memory.
957 auto ME = AAQI.AAR.getMemoryEffects(Call, AAQI)
958 .getWithoutLoc(Loc: IRMemLocation::InaccessibleMem);
959 if (ME.doesNotAccessMemory())
960 return ModRefInfo::NoModRef;
961
962 ModRefInfo ArgMR = ME.getModRef(Loc: IRMemLocation::ArgMem);
963 ModRefInfo ErrnoMR = ME.getModRef(Loc: IRMemLocation::ErrnoMem);
964 ModRefInfo OtherMR = ME.getModRef(Loc: IRMemLocation::Other);
965
966 // Take into account potential synchronization effects of the call.
967 // We assume synchronization can not occur if the call does not read/write
968 // other memory (this in particular ensures that readonly/argmemonly continue
969 // to work as expected for frontends that do not emit nosync).
970 // FIXME: This should apply to all calls, but is limited to inline asm to
971 // limit impact. This ensures that inline asm memory barriers work correctly.
972 ModRefInfo SyncMR = ModRefInfo::NoModRef;
973 if (isModAndRefSet(MRI: OtherMR) && Call->maySynchronize() &&
974 Call->isInlineAsm()) {
975 SyncMR = getSyncEffects(AA: &AAQI.AAR, Loc, AAQI);
976 if (isModAndRefSet(MRI: SyncMR))
977 return SyncMR;
978 }
979
980 // An identified function-local object that does not escape can only be
981 // accessed via call arguments. Reduce OtherMR (which includes accesses to
982 // escaped memory) based on that.
983 //
984 // We model calls that can return twice (setjmp) as clobbering non-escaping
985 // objects, to model any accesses that may occur prior to the second return.
986 // As an exception, ignore allocas, as setjmp is not required to preserve
987 // non-volatile stores for them.
988 if (isModOrRefSet(MRI: OtherMR) && !isa<Constant>(Val: Object) && Call != Object &&
989 (isa<AllocaInst>(Val: Object) || !Call->hasFnAttr(Kind: Attribute::ReturnsTwice))) {
990 CaptureComponents CC = AAQI.CA->getCapturesBefore(
991 Object, I: Call, /*OrAt=*/false, /*ReturnCaptures=*/false);
992 if (capturesNothing(CC))
993 OtherMR = ModRefInfo::NoModRef;
994 else if (capturesReadProvenanceOnly(CC))
995 OtherMR = ModRefInfo::Ref;
996 }
997
998 // Refine the modref info for argument memory. We only bother to do this
999 // if ArgMR is not a subset of OtherMR, otherwise this won't have an impact
1000 // on the final result.
1001 if ((ArgMR | OtherMR) != OtherMR) {
1002 ModRefInfo NewArgMR = ModRefInfo::NoModRef;
1003 for (const Use &U : Call->data_ops()) {
1004 const Value *Arg = U;
1005 if (!Arg->getType()->isPointerTy())
1006 continue;
1007 unsigned ArgIdx = Call->getDataOperandNo(U: &U);
1008 MemoryLocation ArgLoc =
1009 Call->isArgOperand(U: &U)
1010 ? MemoryLocation::getForArgument(Call, ArgIdx, TLI)
1011 : MemoryLocation::getBeforeOrAfter(Ptr: Arg);
1012 AliasResult ArgAlias = AAQI.AAR.alias(LocA: ArgLoc, LocB: Loc, AAQI, CtxI: Call);
1013 if (ArgAlias != AliasResult::NoAlias)
1014 NewArgMR |= ArgMR & AAQI.AAR.getArgModRefInfo(Call, ArgIdx);
1015
1016 // Exit early if we cannot improve over the original ArgMR.
1017 if (NewArgMR == ArgMR)
1018 break;
1019 }
1020 ArgMR = NewArgMR;
1021 }
1022
1023 ModRefInfo Result = ArgMR | OtherMR | SyncMR;
1024
1025 // Refine accesses to errno memory.
1026 if ((ErrnoMR | Result) != Result) {
1027 if (AAQI.AAR.aliasErrno(Loc, M: Call->getModule()) != AliasResult::NoAlias) {
1028 // Exclusion conditions do not hold, this memory location may alias errno.
1029 Result |= ErrnoMR;
1030 }
1031 }
1032
1033 if (!isModAndRefSet(MRI: Result))
1034 return Result;
1035
1036 // If the call is malloc/calloc like, we can assume that it doesn't
1037 // modify any IR visible value. This is only valid because we assume these
1038 // routines do not read values visible in the IR. TODO: Consider special
1039 // casing realloc and strdup routines which access only their arguments as
1040 // well. Or alternatively, replace all of this with inaccessiblememonly once
1041 // that's implemented fully.
1042 if (isMallocOrCallocLikeFn(V: Call, TLI: &TLI)) {
1043 // Be conservative if the accessed pointer may alias the allocation -
1044 // fallback to the generic handling below.
1045 if (AAQI.AAR.alias(LocA: MemoryLocation::getBeforeOrAfter(Ptr: Call), LocB: Loc, AAQI) ==
1046 AliasResult::NoAlias)
1047 return ModRefInfo::NoModRef;
1048 }
1049
1050 // Like assumes, invariant.start intrinsics were also marked as arbitrarily
1051 // writing so that proper control dependencies are maintained but they never
1052 // mod any particular memory location visible to the IR.
1053 // *Unlike* assumes (which are now modeled as NoModRef), invariant.start
1054 // intrinsic is now modeled as reading memory. This prevents hoisting the
1055 // invariant.start intrinsic over stores. Consider:
1056 // *ptr = 40;
1057 // *ptr = 50;
1058 // invariant_start(ptr)
1059 // int val = *ptr;
1060 // print(val);
1061 //
1062 // This cannot be transformed to:
1063 //
1064 // *ptr = 40;
1065 // invariant_start(ptr)
1066 // *ptr = 50;
1067 // int val = *ptr;
1068 // print(val);
1069 //
1070 // The transformation will cause the second store to be ignored (based on
1071 // rules of invariant.start) and print 40, while the first program always
1072 // prints 50.
1073 if (isIntrinsicCall(Call, IID: Intrinsic::invariant_start))
1074 return ModRefInfo::Ref;
1075
1076 // Be conservative.
1077 return ModRefInfo::ModRef;
1078}
1079
1080ModRefInfo BasicAAResult::getModRefInfo(const CallBase *Call1,
1081 const CallBase *Call2,
1082 AAQueryInfo &AAQI) {
1083 // Guard intrinsics are marked as arbitrarily writing so that proper control
1084 // dependencies are maintained but they never mods any particular memory
1085 // location.
1086 //
1087 // *Unlike* assumes, guard intrinsics are modeled as reading memory since the
1088 // heap state at the point the guard is issued needs to be consistent in case
1089 // the guard invokes the "deopt" continuation.
1090
1091 // NB! This function is *not* commutative, so we special case two
1092 // possibilities for guard intrinsics.
1093
1094 if (isIntrinsicCall(Call: Call1, IID: Intrinsic::experimental_guard))
1095 return isModSet(MRI: getMemoryEffects(Call: Call2, AAQI).getModRef())
1096 ? ModRefInfo::Ref
1097 : ModRefInfo::NoModRef;
1098
1099 if (isIntrinsicCall(Call: Call2, IID: Intrinsic::experimental_guard))
1100 return isModSet(MRI: getMemoryEffects(Call: Call1, AAQI).getModRef())
1101 ? ModRefInfo::Mod
1102 : ModRefInfo::NoModRef;
1103
1104 // Be conservative.
1105 return ModRefInfo::ModRef;
1106}
1107
1108/// Provides a bunch of ad-hoc rules to disambiguate a GEP instruction against
1109/// another pointer.
1110///
1111/// We know that V1 is a GEP, but we don't know anything about V2.
1112/// UnderlyingV1 is getUnderlyingObject(GEP1), UnderlyingV2 is the same for
1113/// V2.
1114AliasResult BasicAAResult::aliasGEP(
1115 const GEPOperator *GEP1, LocationSize V1Size,
1116 const Value *V2, LocationSize V2Size,
1117 const Value *UnderlyingV1, const Value *UnderlyingV2, AAQueryInfo &AAQI) {
1118 auto BaseObjectsAlias = [&]() {
1119 AliasResult BaseAlias =
1120 AAQI.AAR.alias(LocA: MemoryLocation::getBeforeOrAfter(Ptr: UnderlyingV1),
1121 LocB: MemoryLocation::getBeforeOrAfter(Ptr: UnderlyingV2), AAQI);
1122 return BaseAlias == AliasResult::NoAlias ? AliasResult::NoAlias
1123 : AliasResult::MayAlias;
1124 };
1125
1126 if (!V1Size.hasValue() && !V2Size.hasValue()) {
1127 // Skip if V2 is itself a phi or select, leave the recursive walk to
1128 // aliasPHI/aliasSelect.
1129 if (isa<PHINode, SelectInst>(Val: V2))
1130 return AliasResult::MayAlias;
1131
1132 // Otherwise check whether the base objects don't alias. Only do so if V2
1133 // is a GEP or an underlying object is a GEP/phi/select, which can be
1134 // analyzed further.
1135 if (isa<GEPOperator>(Val: V2) ||
1136 isa<GEPOperator, PHINode, SelectInst>(Val: UnderlyingV1) ||
1137 isa<GEPOperator, PHINode, SelectInst>(Val: UnderlyingV2))
1138 return BaseObjectsAlias();
1139
1140 return AliasResult::MayAlias;
1141 }
1142
1143 DominatorTree *DT = getDT(AAQI);
1144 DecomposedGEP DecompGEP1 = DecomposeGEPExpression(V: GEP1, DL, AC: &AC, DT);
1145 DecomposedGEP DecompGEP2 = DecomposeGEPExpression(V: V2, DL, AC: &AC, DT);
1146
1147 // Bail if we were not able to decompose anything.
1148 if (DecompGEP1.Base == GEP1 && DecompGEP2.Base == V2)
1149 return AliasResult::MayAlias;
1150
1151 // Fall back to base objects if pointers have different index widths.
1152 if (DecompGEP1.Offset.getBitWidth() != DecompGEP2.Offset.getBitWidth())
1153 return BaseObjectsAlias();
1154
1155 // Swap GEP1 and GEP2 if GEP2 has more variable indices.
1156 if (DecompGEP1.VarIndices.size() < DecompGEP2.VarIndices.size()) {
1157 std::swap(a&: DecompGEP1, b&: DecompGEP2);
1158 std::swap(a&: V1Size, b&: V2Size);
1159 std::swap(a&: UnderlyingV1, b&: UnderlyingV2);
1160 }
1161
1162 // Subtract the GEP2 pointer from the GEP1 pointer to find out their
1163 // symbolic difference.
1164 subtractDecomposedGEPs(DestGEP&: DecompGEP1, SrcGEP: DecompGEP2, AAQI);
1165
1166 // If an inbounds GEP would have to start from an out of bounds address
1167 // for the two to alias, then we can assume noalias.
1168 // TODO: Remove !isScalable() once BasicAA fully support scalable location
1169 // size
1170
1171 if (DecompGEP1.NWFlags.isInBounds() && DecompGEP1.VarIndices.empty() &&
1172 V2Size.hasValue() && !V2Size.isScalable() &&
1173 DecompGEP1.Offset.sge(RHS: V2Size.getValue()) &&
1174 isBaseOfObject(V: DecompGEP2.Base))
1175 return AliasResult::NoAlias;
1176
1177 // Symmetric case to above.
1178 if (DecompGEP2.NWFlags.isInBounds() && DecompGEP1.VarIndices.empty() &&
1179 V1Size.hasValue() && !V1Size.isScalable() &&
1180 DecompGEP1.Offset.sle(RHS: -V1Size.getValue()) &&
1181 isBaseOfObject(V: DecompGEP1.Base))
1182 return AliasResult::NoAlias;
1183
1184 // For GEPs with identical offsets, we can preserve the size and AAInfo
1185 // when performing the alias check on the underlying objects.
1186 if (DecompGEP1.Offset == 0 && DecompGEP1.VarIndices.empty())
1187 return AAQI.AAR.alias(LocA: MemoryLocation(DecompGEP1.Base, V1Size),
1188 LocB: MemoryLocation(DecompGEP2.Base, V2Size), AAQI);
1189
1190 // Do the base pointers alias?
1191 AliasResult BaseAlias =
1192 AAQI.AAR.alias(LocA: MemoryLocation::getBeforeOrAfter(Ptr: DecompGEP1.Base),
1193 LocB: MemoryLocation::getBeforeOrAfter(Ptr: DecompGEP2.Base), AAQI);
1194
1195 // If we get a No or May, then return it immediately, no amount of analysis
1196 // will improve this situation.
1197 if (BaseAlias != AliasResult::MustAlias) {
1198 assert(BaseAlias == AliasResult::NoAlias ||
1199 BaseAlias == AliasResult::MayAlias);
1200 return BaseAlias;
1201 }
1202
1203 // If there is a constant difference between the pointers, but the difference
1204 // is less than the size of the associated memory object, then we know
1205 // that the objects are partially overlapping. If the difference is
1206 // greater, we know they do not overlap.
1207 if (DecompGEP1.VarIndices.empty()) {
1208 APInt &Off = DecompGEP1.Offset;
1209
1210 // Initialize for Off >= 0 (V2 <= GEP1) case.
1211 LocationSize VLeftSize = V2Size;
1212 LocationSize VRightSize = V1Size;
1213 const bool Swapped = Off.isNegative();
1214
1215 if (Swapped) {
1216 // Swap if we have the situation where:
1217 // + +
1218 // | BaseOffset |
1219 // ---------------->|
1220 // |-->V1Size |-------> V2Size
1221 // GEP1 V2
1222 std::swap(a&: VLeftSize, b&: VRightSize);
1223 Off = -Off;
1224 }
1225
1226 if (!VLeftSize.hasValue())
1227 return AliasResult::MayAlias;
1228
1229 const TypeSize LSize = VLeftSize.getValue();
1230 if (!LSize.isScalable()) {
1231 if (Off.ult(RHS: LSize)) {
1232 // Conservatively drop processing if a phi was visited and/or offset is
1233 // too big.
1234 AliasResult AR = AliasResult::PartialAlias;
1235 if (VRightSize.hasValue() && !VRightSize.isScalable() &&
1236 Off.ule(INT32_MAX) && (Off + VRightSize.getValue()).ule(RHS: LSize)) {
1237 // Memory referenced by right pointer is nested. Save the offset in
1238 // cache. Note that originally offset estimated as GEP1-V2, but
1239 // AliasResult contains the shift that represents GEP1+Offset=V2.
1240 AR.setOffset(-Off.getSExtValue());
1241 AR.swap(DoSwap: Swapped);
1242 }
1243 return AR;
1244 }
1245 return AliasResult::NoAlias;
1246 } else {
1247 // We can use the getVScaleRange to prove that Off >= (CR.upper * LSize).
1248 ConstantRange CR = getVScaleRange(F: &F, BitWidth: Off.getBitWidth());
1249 bool Overflow;
1250 APInt UpperRange = CR.getUnsignedMax().umul_ov(
1251 RHS: APInt(Off.getBitWidth(), LSize.getKnownMinValue()), Overflow);
1252 if (!Overflow && Off.uge(RHS: UpperRange))
1253 return AliasResult::NoAlias;
1254 }
1255 }
1256
1257 // VScale Alias Analysis - Given one scalable offset between accesses and a
1258 // scalable typesize, we can divide each side by vscale, treating both values
1259 // as a constant. We prove that Offset/vscale >= TypeSize/vscale.
1260 if (DecompGEP1.VarIndices.size() == 1 &&
1261 DecompGEP1.VarIndices[0].Val.TruncBits == 0 &&
1262 DecompGEP1.Offset.isZero() &&
1263 PatternMatch::match(V: DecompGEP1.VarIndices[0].Val.V,
1264 P: PatternMatch::m_VScale())) {
1265 const VariableGEPIndex &ScalableVar = DecompGEP1.VarIndices[0];
1266 APInt Scale =
1267 ScalableVar.IsNegated ? -ScalableVar.Scale : ScalableVar.Scale;
1268 LocationSize VLeftSize = Scale.isNegative() ? V1Size : V2Size;
1269
1270 // Check if the offset is known to not overflow, if it does then attempt to
1271 // prove it with the known values of vscale_range.
1272 bool Overflows = !DecompGEP1.VarIndices[0].IsNSW;
1273 if (Overflows) {
1274 ConstantRange CR = getVScaleRange(F: &F, BitWidth: Scale.getBitWidth());
1275 (void)CR.getSignedMax().smul_ov(RHS: Scale, Overflow&: Overflows);
1276 }
1277
1278 if (!Overflows) {
1279 // Note that we do not check that the typesize is scalable, as vscale >= 1
1280 // so noalias still holds so long as the dependency distance is at least
1281 // as big as the typesize.
1282 if (VLeftSize.hasValue() &&
1283 Scale.abs().uge(RHS: VLeftSize.getValue().getKnownMinValue()))
1284 return AliasResult::NoAlias;
1285 }
1286 }
1287
1288 // If the difference between pointers is Offset +<nuw> Indices then we know
1289 // that the addition does not wrap the pointer index type (add nuw) and the
1290 // constant Offset is a lower bound on the distance between the pointers. We
1291 // can then prove NoAlias via Offset u>= VLeftSize.
1292 // + + +
1293 // | BaseOffset | +<nuw> Indices |
1294 // ---------------->|-------------------->|
1295 // |-->V2Size | |-------> V1Size
1296 // LHS RHS
1297 if (!DecompGEP1.VarIndices.empty() &&
1298 DecompGEP1.NWFlags.hasNoUnsignedWrap() && V2Size.hasValue() &&
1299 !V2Size.isScalable() && DecompGEP1.Offset.uge(RHS: V2Size.getValue()))
1300 return AliasResult::NoAlias;
1301
1302 // Bail on analysing scalable LocationSize
1303 if (V1Size.isScalable() || V2Size.isScalable())
1304 return AliasResult::MayAlias;
1305
1306 // We need to know both access sizes for all the following heuristics. Don't
1307 // try to reason about sizes larger than the index space.
1308 unsigned BW = DecompGEP1.Offset.getBitWidth();
1309 if (!V1Size.hasValue() || !V2Size.hasValue() ||
1310 !isUIntN(N: BW, x: V1Size.getValue()) || !isUIntN(N: BW, x: V2Size.getValue()))
1311 return AliasResult::MayAlias;
1312
1313 APInt GCD;
1314 ConstantRange OffsetRange = ConstantRange(DecompGEP1.Offset);
1315 for (unsigned i = 0, e = DecompGEP1.VarIndices.size(); i != e; ++i) {
1316 const VariableGEPIndex &Index = DecompGEP1.VarIndices[i];
1317 const APInt &Scale = Index.Scale;
1318
1319 SimplifyQuery SQ(DL, DT, &AC, Index.CxtI, /*UseInstrInfo=*/true);
1320 KnownBits Known = computeKnownBits(V: Index.Val.V, Q: SQ);
1321
1322 APInt ScaleForGCD = Scale;
1323 if (!Index.IsNSW)
1324 ScaleForGCD =
1325 APInt::getOneBitSet(numBits: Scale.getBitWidth(), BitNo: Scale.countr_zero());
1326
1327 // If V has known trailing zeros, V is a multiple of 2^VarTZ, so
1328 // V*Scale is a multiple of ScaleForGCD * 2^VarTZ. Shift ScaleForGCD
1329 // left to account for this (trailing zeros compose additively through
1330 // multiplication, even in Z/2^n).
1331 unsigned VarTZ = Known.countMinTrailingZeros();
1332 if (VarTZ > 0) {
1333 unsigned MaxShift =
1334 Scale.getBitWidth() - ScaleForGCD.getSignificantBits();
1335 ScaleForGCD <<= std::min(a: VarTZ, b: MaxShift);
1336 }
1337
1338 if (i == 0)
1339 GCD = ScaleForGCD.abs();
1340 else
1341 GCD = APIntOps::GreatestCommonDivisor(A: GCD, B: ScaleForGCD.abs());
1342
1343 ConstantRange CR =
1344 computeConstantRange(V: Index.Val.V, /*ForSigned=*/false, SQ);
1345 CR = CR.intersectWith(
1346 CR: ConstantRange::fromKnownBits(Known, /* Signed */ IsSigned: true),
1347 Type: ConstantRange::Signed);
1348 CR = Index.Val.evaluateWith(N: CR).sextOrTrunc(BitWidth: OffsetRange.getBitWidth());
1349
1350 assert(OffsetRange.getBitWidth() == Scale.getBitWidth() &&
1351 "Bit widths are normalized to MaxIndexSize");
1352 if (Index.IsNSW)
1353 CR = CR.smul_sat(Other: ConstantRange(Scale));
1354 else
1355 CR = CR.smul_fast(Other: ConstantRange(Scale));
1356
1357 if (Index.IsNegated)
1358 OffsetRange = OffsetRange.sub(Other: CR);
1359 else
1360 OffsetRange = OffsetRange.add(Other: CR);
1361 }
1362
1363 // We now have accesses at two offsets from the same base:
1364 // 1. (...)*GCD + DecompGEP1.Offset with size V1Size
1365 // 2. 0 with size V2Size
1366 // Using arithmetic modulo GCD, the accesses are at
1367 // [ModOffset..ModOffset+V1Size) and [0..V2Size). If the first access fits
1368 // into the range [V2Size..GCD), then we know they cannot overlap.
1369 APInt ModOffset = DecompGEP1.Offset.srem(RHS: GCD);
1370 if (ModOffset.isNegative())
1371 ModOffset += GCD; // We want mod, not rem.
1372 if (ModOffset.uge(RHS: V2Size.getValue()) &&
1373 (GCD - ModOffset).uge(RHS: V1Size.getValue()))
1374 return AliasResult::NoAlias;
1375
1376 // Compute ranges of potentially accessed bytes for both accesses. If the
1377 // interseciton is empty, there can be no overlap.
1378 ConstantRange Range1 = OffsetRange.add(
1379 Other: ConstantRange(APInt(BW, 0), APInt(BW, V1Size.getValue())));
1380 ConstantRange Range2 =
1381 ConstantRange(APInt(BW, 0), APInt(BW, V2Size.getValue()));
1382 if (Range1.intersectWith(CR: Range2).isEmptySet())
1383 return AliasResult::NoAlias;
1384
1385 // Check if abs(V*Scale) >= abs(Scale) holds in the presence of
1386 // potentially wrapping math.
1387 auto MultiplyByScaleNoWrap = [](const VariableGEPIndex &Var) {
1388 if (Var.IsNSW)
1389 return true;
1390
1391 int ValOrigBW = Var.Val.V->getType()->getPrimitiveSizeInBits();
1392 // If Scale is small enough so that abs(V*Scale) >= abs(Scale) holds.
1393 // The max value of abs(V) is 2^ValOrigBW - 1. Multiplying with a
1394 // constant smaller than 2^(bitwidth(Val) - ValOrigBW) won't wrap.
1395 int MaxScaleValueBW = Var.Val.getBitWidth() - ValOrigBW;
1396 if (MaxScaleValueBW <= 0)
1397 return false;
1398 return Var.Scale.ule(
1399 RHS: APInt::getMaxValue(numBits: MaxScaleValueBW).zext(width: Var.Scale.getBitWidth()));
1400 };
1401
1402 // Try to determine the range of values for VarIndex such that
1403 // VarIndex <= -MinAbsVarIndex || MinAbsVarIndex <= VarIndex.
1404 std::optional<APInt> MinAbsVarIndex;
1405 if (DecompGEP1.VarIndices.size() == 1) {
1406 // VarIndex = Scale*V.
1407 const VariableGEPIndex &Var = DecompGEP1.VarIndices[0];
1408 if (Var.Val.TruncBits == 0 &&
1409 isKnownNonZero(V: Var.Val.V, Q: SimplifyQuery(DL, DT, &AC, Var.CxtI))) {
1410 // Refine MinAbsVarIndex, if abs(Scale*V) >= abs(Scale) holds in the
1411 // presence of potentially wrapping math.
1412 if (MultiplyByScaleNoWrap(Var)) {
1413 // If V != 0 then abs(VarIndex) >= abs(Scale).
1414 MinAbsVarIndex = Var.Scale.abs();
1415 }
1416 }
1417 } else if (DecompGEP1.VarIndices.size() == 2) {
1418 // VarIndex = Scale*V0 + (-Scale)*V1.
1419 // If V0 != V1 then abs(VarIndex) >= abs(Scale).
1420 // Check that MayBeCrossIteration is false, to avoid reasoning about
1421 // inequality of values across loop iterations.
1422 const VariableGEPIndex &Var0 = DecompGEP1.VarIndices[0];
1423 const VariableGEPIndex &Var1 = DecompGEP1.VarIndices[1];
1424 if (Var0.hasNegatedScaleOf(Other: Var1) && Var0.Val.TruncBits == 0 &&
1425 Var0.Val.hasSameCastsAs(Other: Var1.Val) && !AAQI.MayBeCrossIteration &&
1426 MultiplyByScaleNoWrap(Var0) && MultiplyByScaleNoWrap(Var1) &&
1427 isKnownNonEqual(V1: Var0.Val.V, V2: Var1.Val.V,
1428 SQ: SimplifyQuery(DL, DT, &AC, /*CxtI=*/Var0.CxtI
1429 ? Var0.CxtI
1430 : Var1.CxtI)))
1431 MinAbsVarIndex = Var0.Scale.abs();
1432 }
1433
1434 if (MinAbsVarIndex) {
1435 // The constant offset will have added at least +/-MinAbsVarIndex to it.
1436 APInt OffsetLo = DecompGEP1.Offset - *MinAbsVarIndex;
1437 APInt OffsetHi = DecompGEP1.Offset + *MinAbsVarIndex;
1438 // We know that Offset <= OffsetLo || Offset >= OffsetHi
1439 if (OffsetLo.isNegative() && (-OffsetLo).uge(RHS: V1Size.getValue()) &&
1440 OffsetHi.isNonNegative() && OffsetHi.uge(RHS: V2Size.getValue()))
1441 return AliasResult::NoAlias;
1442 }
1443
1444 if (constantOffsetHeuristic(GEP: DecompGEP1, V1Size, V2Size, AC: &AC, DT, AAQI))
1445 return AliasResult::NoAlias;
1446
1447 // Statically, we can see that the base objects are the same, but the
1448 // pointers have dynamic offsets which we can't resolve. And none of our
1449 // little tricks above worked.
1450 return AliasResult::MayAlias;
1451}
1452
1453static AliasResult MergeAliasResults(AliasResult A, AliasResult B) {
1454 // If the results agree, take it.
1455 if (A == B)
1456 return A;
1457 // A mix of PartialAlias and MustAlias is PartialAlias.
1458 if ((A == AliasResult::PartialAlias && B == AliasResult::MustAlias) ||
1459 (B == AliasResult::PartialAlias && A == AliasResult::MustAlias))
1460 return AliasResult::PartialAlias;
1461 // Otherwise, we don't know anything.
1462 return AliasResult::MayAlias;
1463}
1464
1465/// Provides a bunch of ad-hoc rules to disambiguate a Select instruction
1466/// against another.
1467AliasResult
1468BasicAAResult::aliasSelect(const SelectInst *SI, LocationSize SISize,
1469 const Value *V2, LocationSize V2Size,
1470 AAQueryInfo &AAQI) {
1471 // If the values are Selects with the same condition, we can do a more precise
1472 // check: just check for aliases between the values on corresponding arms.
1473 if (const SelectInst *SI2 = dyn_cast<SelectInst>(Val: V2))
1474 if (isValueEqualInPotentialCycles(V1: SI->getCondition(), V2: SI2->getCondition(),
1475 AAQI)) {
1476 AliasResult Alias =
1477 AAQI.AAR.alias(LocA: MemoryLocation(SI->getTrueValue(), SISize),
1478 LocB: MemoryLocation(SI2->getTrueValue(), V2Size), AAQI);
1479 if (Alias == AliasResult::MayAlias)
1480 return AliasResult::MayAlias;
1481 AliasResult ThisAlias =
1482 AAQI.AAR.alias(LocA: MemoryLocation(SI->getFalseValue(), SISize),
1483 LocB: MemoryLocation(SI2->getFalseValue(), V2Size), AAQI);
1484 return MergeAliasResults(A: ThisAlias, B: Alias);
1485 }
1486
1487 // If both arms of the Select node NoAlias or MustAlias V2, then returns
1488 // NoAlias / MustAlias. Otherwise, returns MayAlias.
1489 AliasResult Alias = AAQI.AAR.alias(LocA: MemoryLocation(SI->getTrueValue(), SISize),
1490 LocB: MemoryLocation(V2, V2Size), AAQI);
1491 if (Alias == AliasResult::MayAlias)
1492 return AliasResult::MayAlias;
1493
1494 AliasResult ThisAlias =
1495 AAQI.AAR.alias(LocA: MemoryLocation(SI->getFalseValue(), SISize),
1496 LocB: MemoryLocation(V2, V2Size), AAQI);
1497 return MergeAliasResults(A: ThisAlias, B: Alias);
1498}
1499
1500/// Provide a bunch of ad-hoc rules to disambiguate a PHI instruction against
1501/// another.
1502AliasResult BasicAAResult::aliasPHI(const PHINode *PN, LocationSize PNSize,
1503 const Value *V2, LocationSize V2Size,
1504 AAQueryInfo &AAQI) {
1505 if (!PN->getNumIncomingValues())
1506 return AliasResult::NoAlias;
1507 // If the values are PHIs in the same block, we can do a more precise
1508 // as well as efficient check: just check for aliases between the values
1509 // on corresponding edges. Don't do this if we are analyzing across
1510 // iterations, as we may pick a different phi entry in different iterations.
1511 if (const PHINode *PN2 = dyn_cast<PHINode>(Val: V2))
1512 if (PN2->getParent() == PN->getParent() && !AAQI.MayBeCrossIteration) {
1513 std::optional<AliasResult> Alias;
1514 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1515 AliasResult ThisAlias = AAQI.AAR.alias(
1516 LocA: MemoryLocation(PN->getIncomingValue(i), PNSize),
1517 LocB: MemoryLocation(
1518 PN2->getIncomingValueForBlock(BB: PN->getIncomingBlock(i)), V2Size),
1519 AAQI);
1520 if (Alias)
1521 *Alias = MergeAliasResults(A: *Alias, B: ThisAlias);
1522 else
1523 Alias = ThisAlias;
1524 if (*Alias == AliasResult::MayAlias)
1525 break;
1526 }
1527 return *Alias;
1528 }
1529
1530 SmallVector<Value *, 4> V1Srcs;
1531 // If a phi operand recurses back to the phi, we can still determine NoAlias
1532 // if we don't alias the underlying objects of the other phi operands, as we
1533 // know that the recursive phi needs to be based on them in some way.
1534 bool isRecursive = false;
1535 auto CheckForRecPhi = [&](Value *PV) {
1536 if (!EnableRecPhiAnalysis)
1537 return false;
1538 if (getUnderlyingObject(V: PV) == PN) {
1539 isRecursive = true;
1540 return true;
1541 }
1542 return false;
1543 };
1544
1545 SmallPtrSet<Value *, 4> UniqueSrc;
1546 Value *OnePhi = nullptr;
1547 for (Value *PV1 : PN->incoming_values()) {
1548 // Skip the phi itself being the incoming value.
1549 if (PV1 == PN)
1550 continue;
1551
1552 if (isa<PHINode>(Val: PV1)) {
1553 if (OnePhi && OnePhi != PV1) {
1554 // To control potential compile time explosion, we choose to be
1555 // conserviate when we have more than one Phi input. It is important
1556 // that we handle the single phi case as that lets us handle LCSSA
1557 // phi nodes and (combined with the recursive phi handling) simple
1558 // pointer induction variable patterns.
1559 return AliasResult::MayAlias;
1560 }
1561 OnePhi = PV1;
1562 }
1563
1564 if (CheckForRecPhi(PV1))
1565 continue;
1566
1567 if (UniqueSrc.insert(Ptr: PV1).second)
1568 V1Srcs.push_back(Elt: PV1);
1569 }
1570
1571 if (OnePhi && UniqueSrc.size() > 1)
1572 // Out of an abundance of caution, allow only the trivial lcssa and
1573 // recursive phi cases.
1574 return AliasResult::MayAlias;
1575
1576 // If V1Srcs is empty then that means that the phi has no underlying non-phi
1577 // value. This should only be possible in blocks unreachable from the entry
1578 // block, but return MayAlias just in case.
1579 if (V1Srcs.empty())
1580 return AliasResult::MayAlias;
1581
1582 // If this PHI node is recursive, indicate that the pointer may be moved
1583 // across iterations. We can only prove NoAlias if different underlying
1584 // objects are involved.
1585 if (isRecursive)
1586 PNSize = LocationSize::beforeOrAfterPointer();
1587
1588 // In the recursive alias queries below, we may compare values from two
1589 // different loop iterations.
1590 SaveAndRestore SavedMayBeCrossIteration(AAQI.MayBeCrossIteration, true);
1591
1592 AliasResult Alias = AAQI.AAR.alias(LocA: MemoryLocation(V1Srcs[0], PNSize),
1593 LocB: MemoryLocation(V2, V2Size), AAQI);
1594
1595 // Early exit if the check of the first PHI source against V2 is MayAlias.
1596 // Other results are not possible.
1597 if (Alias == AliasResult::MayAlias)
1598 return AliasResult::MayAlias;
1599 // With recursive phis we cannot guarantee that MustAlias/PartialAlias will
1600 // remain valid to all elements and needs to conservatively return MayAlias.
1601 if (isRecursive && Alias != AliasResult::NoAlias)
1602 return AliasResult::MayAlias;
1603
1604 // If all sources of the PHI node NoAlias or MustAlias V2, then returns
1605 // NoAlias / MustAlias. Otherwise, returns MayAlias.
1606 for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) {
1607 Value *V = V1Srcs[i];
1608
1609 AliasResult ThisAlias = AAQI.AAR.alias(
1610 LocA: MemoryLocation(V, PNSize), LocB: MemoryLocation(V2, V2Size), AAQI);
1611 Alias = MergeAliasResults(A: ThisAlias, B: Alias);
1612 if (Alias == AliasResult::MayAlias)
1613 break;
1614 }
1615
1616 return Alias;
1617}
1618
1619// Return true for an Argument or extractvalue(Argument). These are all known
1620// to not alias with FunctionLocal objects and can come up from coerced function
1621// arguments.
1622static bool isArgumentOrArgumentLike(const Value *V) {
1623 if (isa<Argument>(Val: V))
1624 return true;
1625 auto *E = dyn_cast<ExtractValueInst>(Val: V);
1626 return E && isa<Argument>(Val: E->getOperand(i_nocapture: 0));
1627}
1628
1629/// Provides a bunch of ad-hoc rules to disambiguate in common cases, such as
1630/// array references.
1631AliasResult BasicAAResult::aliasCheck(const Value *V1, LocationSize V1Size,
1632 const Value *V2, LocationSize V2Size,
1633 AAQueryInfo &AAQI,
1634 const Instruction *CtxI) {
1635 // If either of the memory references is empty, it doesn't matter what the
1636 // pointer values are.
1637 if (V1Size.isZero() || V2Size.isZero())
1638 return AliasResult::NoAlias;
1639
1640 // Strip off any casts if they exist.
1641 V1 = V1->stripPointerCastsForAliasAnalysis();
1642 V2 = V2->stripPointerCastsForAliasAnalysis();
1643
1644 // If V1 or V2 is undef, the result is NoAlias because we can always pick a
1645 // value for undef that aliases nothing in the program.
1646 if (isa<UndefValue>(Val: V1) || isa<UndefValue>(Val: V2))
1647 return AliasResult::NoAlias;
1648
1649 // Are we checking for alias of the same value?
1650 // Because we look 'through' phi nodes, we could look at "Value" pointers from
1651 // different iterations. We must therefore make sure that this is not the
1652 // case. The function isValueEqualInPotentialCycles ensures that this cannot
1653 // happen by looking at the visited phi nodes and making sure they cannot
1654 // reach the value.
1655 if (isValueEqualInPotentialCycles(V1, V2, AAQI))
1656 return AliasResult::MustAlias;
1657
1658 // Figure out what objects these things are pointing to if we can.
1659 const Value *O1 = getUnderlyingObject(V: V1, MaxLookup: MaxLookupSearchDepth);
1660 const Value *O2 = getUnderlyingObject(V: V2, MaxLookup: MaxLookupSearchDepth);
1661
1662 // Null values in the default address space don't point to any object, so they
1663 // don't alias any other pointer.
1664 if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(Val: O1))
1665 if (!NullPointerIsDefined(F: &F, AS: CPN->getPointerType()->getAddressSpace()))
1666 return AliasResult::NoAlias;
1667 if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(Val: O2))
1668 if (!NullPointerIsDefined(F: &F, AS: CPN->getPointerType()->getAddressSpace()))
1669 return AliasResult::NoAlias;
1670
1671 if (O1 != O2) {
1672 // If V1/V2 point to two different objects, we know that we have no alias.
1673 if (isIdentifiedObject(V: O1) && isIdentifiedObject(V: O2))
1674 return AliasResult::NoAlias;
1675
1676 // Function arguments can't alias with things that are known to be
1677 // unambigously identified at the function level.
1678 if ((isArgumentOrArgumentLike(V: O1) && isIdentifiedFunctionLocal(V: O2)) ||
1679 (isArgumentOrArgumentLike(V: O2) && isIdentifiedFunctionLocal(V: O1)))
1680 return AliasResult::NoAlias;
1681
1682 // If one pointer is the result of a call/invoke or load and the other is a
1683 // non-escaping local object within the same function, then we know the
1684 // object couldn't escape to a point where the call could return it.
1685 //
1686 // Note that if the pointers are in different functions, there are a
1687 // variety of complications. A call with a nocapture argument may still
1688 // temporary store the nocapture argument's value in a temporary memory
1689 // location if that memory location doesn't escape. Or it may pass a
1690 // nocapture value to other functions as long as they don't capture it.
1691 if (isEscapeSource(V: O1) && capturesNothing(CC: AAQI.CA->getCapturesBefore(
1692 Object: O2, I: dyn_cast<Instruction>(Val: O1), /*OrAt=*/true,
1693 /*ReturnCaptures=*/false)))
1694 return AliasResult::NoAlias;
1695 if (isEscapeSource(V: O2) && capturesNothing(CC: AAQI.CA->getCapturesBefore(
1696 Object: O1, I: dyn_cast<Instruction>(Val: O2), /*OrAt=*/true,
1697 /*ReturnCaptures=*/false)))
1698 return AliasResult::NoAlias;
1699 }
1700
1701 // If the size of one access is larger than the entire object on the other
1702 // side, then we know such behavior is undefined and can assume no alias.
1703 bool NullIsValidLocation = NullPointerIsDefined(F: &F);
1704 if ((isObjectSmallerThan(
1705 V: O2, Size: getMinimalExtentFrom(V: *V1, LocSize: V1Size, DL, NullIsValidLoc: NullIsValidLocation), DL,
1706 TLI, NullIsValidLoc: NullIsValidLocation)) ||
1707 (isObjectSmallerThan(
1708 V: O1, Size: getMinimalExtentFrom(V: *V2, LocSize: V2Size, DL, NullIsValidLoc: NullIsValidLocation), DL,
1709 TLI, NullIsValidLoc: NullIsValidLocation)))
1710 return AliasResult::NoAlias;
1711
1712 if (EnableSeparateStorageAnalysis) {
1713 for (AssumptionCache::ResultElem &Elem : AC.assumptionsFor(V: O1)) {
1714 if (!Elem || Elem.Index == AssumptionCache::ExprResultIdx)
1715 continue;
1716
1717 AssumeInst *Assume = cast<AssumeInst>(Val&: Elem);
1718 OperandBundleUse OBU = Assume->getOperandBundleAt(Index: Elem.Index);
1719 if (OBU.getTagName() == "separate_storage") {
1720 assert(OBU.Inputs.size() == 2);
1721 const Value *Hint1 = OBU.Inputs[0].get();
1722 const Value *Hint2 = OBU.Inputs[1].get();
1723 // This is often a no-op; instcombine rewrites this for us. No-op
1724 // getUnderlyingObject calls are fast, though.
1725 const Value *HintO1 = getUnderlyingObject(V: Hint1);
1726 const Value *HintO2 = getUnderlyingObject(V: Hint2);
1727
1728 DominatorTree *DT = getDT(AAQI);
1729 auto ValidAssumeForPtrContext = [&](const Value *Ptr) {
1730 if (const Instruction *PtrI = dyn_cast<Instruction>(Val: Ptr)) {
1731 return isValidAssumeForContext(I: Assume, CxtI: PtrI, DT,
1732 /* AllowEphemerals */ true);
1733 }
1734 if (const Argument *PtrA = dyn_cast<Argument>(Val: Ptr)) {
1735 const Instruction *FirstI =
1736 &*PtrA->getParent()->getEntryBlock().begin();
1737 return isValidAssumeForContext(I: Assume, CxtI: FirstI, DT,
1738 /* AllowEphemerals */ true);
1739 }
1740 return false;
1741 };
1742
1743 if ((O1 == HintO1 && O2 == HintO2) || (O1 == HintO2 && O2 == HintO1)) {
1744 // Note that we go back to V1 and V2 for the
1745 // ValidAssumeForPtrContext checks; they're dominated by O1 and O2,
1746 // so strictly more assumptions are valid for them.
1747 if ((CtxI && isValidAssumeForContext(I: Assume, CxtI: CtxI, DT,
1748 /* AllowEphemerals */ true)) ||
1749 ValidAssumeForPtrContext(V1) || ValidAssumeForPtrContext(V2)) {
1750 return AliasResult::NoAlias;
1751 }
1752 }
1753 }
1754 }
1755 }
1756
1757 // If one the accesses may be before the accessed pointer, canonicalize this
1758 // by using unknown after-pointer sizes for both accesses. This is
1759 // equivalent, because regardless of which pointer is lower, one of them
1760 // will always came after the other, as long as the underlying objects aren't
1761 // disjoint. We do this so that the rest of BasicAA does not have to deal
1762 // with accesses before the base pointer, and to improve cache utilization by
1763 // merging equivalent states.
1764 if (V1Size.mayBeBeforePointer() || V2Size.mayBeBeforePointer()) {
1765 V1Size = LocationSize::afterPointer();
1766 V2Size = LocationSize::afterPointer();
1767 }
1768
1769 // FIXME: If this depth limit is hit, then we may cache sub-optimal results
1770 // for recursive queries. For this reason, this limit is chosen to be large
1771 // enough to be very rarely hit, while still being small enough to avoid
1772 // stack overflows.
1773 if (AAQI.Depth >= 512)
1774 return AliasResult::MayAlias;
1775
1776 // Check the cache before climbing up use-def chains. This also terminates
1777 // otherwise infinitely recursive queries. Include MayBeCrossIteration in the
1778 // cache key, because some cases where MayBeCrossIteration==false returns
1779 // MustAlias or NoAlias may become MayAlias under MayBeCrossIteration==true.
1780 AAQueryInfo::LocPair Locs({V1, V1Size, AAQI.MayBeCrossIteration},
1781 {V2, V2Size, AAQI.MayBeCrossIteration});
1782 const bool Swapped = V1 > V2;
1783 if (Swapped)
1784 std::swap(a&: Locs.first, b&: Locs.second);
1785 const auto &Pair = AAQI.AliasCache.try_emplace(
1786 Key: Locs, Args: AAQueryInfo::CacheEntry{.Result: AliasResult::NoAlias, .NumAssumptionUses: 0});
1787 if (!Pair.second) {
1788 auto &Entry = Pair.first->second;
1789 if (!Entry.isDefinitive()) {
1790 // Remember that we used an assumption. This may either be a direct use
1791 // of an assumption, or a use of an entry that may itself be based on an
1792 // assumption.
1793 ++AAQI.NumAssumptionUses;
1794 if (Entry.isAssumption())
1795 ++Entry.NumAssumptionUses;
1796 }
1797 // Cache contains sorted {V1,V2} pairs but we should return original order.
1798 auto Result = Entry.Result;
1799 Result.swap(DoSwap: Swapped);
1800 return Result;
1801 }
1802
1803 int OrigNumAssumptionUses = AAQI.NumAssumptionUses;
1804 unsigned OrigNumAssumptionBasedResults = AAQI.AssumptionBasedResults.size();
1805 AliasResult Result =
1806 aliasCheckRecursive(V1, V1Size, V2, V2Size, AAQI, O1, O2);
1807
1808 auto It = AAQI.AliasCache.find(Val: Locs);
1809 assert(It != AAQI.AliasCache.end() && "Must be in cache");
1810 auto &Entry = It->second;
1811
1812 // Check whether a NoAlias assumption has been used, but disproven.
1813 bool AssumptionDisproven =
1814 Entry.NumAssumptionUses > 0 && Result != AliasResult::NoAlias;
1815 if (AssumptionDisproven)
1816 Result = AliasResult::MayAlias;
1817
1818 // This is a definitive result now, when considered as a root query.
1819 AAQI.NumAssumptionUses -= Entry.NumAssumptionUses;
1820 Entry.Result = Result;
1821 // Cache contains sorted {V1,V2} pairs.
1822 Entry.Result.swap(DoSwap: Swapped);
1823
1824 // If the assumption has been disproven, remove any results that may have
1825 // been based on this assumption. Do this after the Entry updates above to
1826 // avoid iterator invalidation.
1827 if (AssumptionDisproven)
1828 while (AAQI.AssumptionBasedResults.size() > OrigNumAssumptionBasedResults)
1829 AAQI.AliasCache.erase(Val: AAQI.AssumptionBasedResults.pop_back_val());
1830
1831 // The result may still be based on assumptions higher up in the chain.
1832 // Remember it, so it can be purged from the cache later.
1833 if (OrigNumAssumptionUses != AAQI.NumAssumptionUses &&
1834 Result != AliasResult::MayAlias) {
1835 AAQI.AssumptionBasedResults.push_back(Elt: Locs);
1836 Entry.NumAssumptionUses = AAQueryInfo::CacheEntry::AssumptionBased;
1837 } else {
1838 Entry.NumAssumptionUses = AAQueryInfo::CacheEntry::Definitive;
1839 }
1840
1841 // Depth is incremented before this function is called, so Depth==1 indicates
1842 // a root query.
1843 if (AAQI.Depth == 1) {
1844 // Any remaining assumption based results must be based on proven
1845 // assumptions, so convert them to definitive results.
1846 for (const auto &Loc : AAQI.AssumptionBasedResults) {
1847 auto It = AAQI.AliasCache.find(Val: Loc);
1848 if (It != AAQI.AliasCache.end())
1849 It->second.NumAssumptionUses = AAQueryInfo::CacheEntry::Definitive;
1850 }
1851 AAQI.AssumptionBasedResults.clear();
1852 AAQI.NumAssumptionUses = 0;
1853 }
1854 return Result;
1855}
1856
1857AliasResult BasicAAResult::aliasCheckRecursive(
1858 const Value *V1, LocationSize V1Size,
1859 const Value *V2, LocationSize V2Size,
1860 AAQueryInfo &AAQI, const Value *O1, const Value *O2) {
1861 if (const GEPOperator *GV1 = dyn_cast<GEPOperator>(Val: V1)) {
1862 AliasResult Result = aliasGEP(GEP1: GV1, V1Size, V2, V2Size, UnderlyingV1: O1, UnderlyingV2: O2, AAQI);
1863 if (Result != AliasResult::MayAlias)
1864 return Result;
1865 } else if (const GEPOperator *GV2 = dyn_cast<GEPOperator>(Val: V2)) {
1866 AliasResult Result = aliasGEP(GEP1: GV2, V1Size: V2Size, V2: V1, V2Size: V1Size, UnderlyingV1: O2, UnderlyingV2: O1, AAQI);
1867 Result.swap();
1868 if (Result != AliasResult::MayAlias)
1869 return Result;
1870 }
1871
1872 if (const PHINode *PN = dyn_cast<PHINode>(Val: V1)) {
1873 AliasResult Result = aliasPHI(PN, PNSize: V1Size, V2, V2Size, AAQI);
1874 if (Result != AliasResult::MayAlias)
1875 return Result;
1876 } else if (const PHINode *PN = dyn_cast<PHINode>(Val: V2)) {
1877 AliasResult Result = aliasPHI(PN, PNSize: V2Size, V2: V1, V2Size: V1Size, AAQI);
1878 Result.swap();
1879 if (Result != AliasResult::MayAlias)
1880 return Result;
1881 }
1882
1883 if (const SelectInst *S1 = dyn_cast<SelectInst>(Val: V1)) {
1884 AliasResult Result = aliasSelect(SI: S1, SISize: V1Size, V2, V2Size, AAQI);
1885 if (Result != AliasResult::MayAlias)
1886 return Result;
1887 } else if (const SelectInst *S2 = dyn_cast<SelectInst>(Val: V2)) {
1888 AliasResult Result = aliasSelect(SI: S2, SISize: V2Size, V2: V1, V2Size: V1Size, AAQI);
1889 Result.swap();
1890 if (Result != AliasResult::MayAlias)
1891 return Result;
1892 }
1893
1894 // If both pointers are pointing into the same object and one of them
1895 // accesses the entire object, then the accesses must overlap in some way.
1896 if (O1 == O2) {
1897 bool NullIsValidLocation = NullPointerIsDefined(F: &F);
1898 if (V1Size.isPrecise() && V2Size.isPrecise() &&
1899 (isObjectSize(V: O1, Size: V1Size.getValue(), DL, TLI, NullIsValidLoc: NullIsValidLocation) ||
1900 isObjectSize(V: O2, Size: V2Size.getValue(), DL, TLI, NullIsValidLoc: NullIsValidLocation)))
1901 return AliasResult::PartialAlias;
1902 }
1903
1904 return AliasResult::MayAlias;
1905}
1906
1907AliasResult BasicAAResult::aliasErrno(const MemoryLocation &Loc,
1908 const Module *M) {
1909 // There cannot be any alias with errno if the given memory location is an
1910 // identified function-local object, or the size of the memory access is
1911 // larger than the integer size.
1912 if (Loc.Size.hasValue() &&
1913 Loc.Size.getValue().getKnownMinValue() * 8 > TLI.getIntSize())
1914 return AliasResult::NoAlias;
1915
1916 if (isIdentifiedFunctionLocal(V: getUnderlyingObject(V: Loc.Ptr)))
1917 return AliasResult::NoAlias;
1918 return AliasResult::MayAlias;
1919}
1920
1921/// Check whether two Values can be considered equivalent.
1922///
1923/// If the values may come from different cycle iterations, this will also
1924/// check that the values are not part of cycle. We have to do this because we
1925/// are looking through phi nodes, that is we say
1926/// noalias(V, phi(VA, VB)) if noalias(V, VA) and noalias(V, VB).
1927bool BasicAAResult::isValueEqualInPotentialCycles(const Value *V,
1928 const Value *V2,
1929 const AAQueryInfo &AAQI) {
1930 if (V != V2)
1931 return false;
1932
1933 if (!AAQI.MayBeCrossIteration)
1934 return true;
1935
1936 // Non-instructions and instructions in the entry block cannot be part of
1937 // a loop.
1938 const Instruction *Inst = dyn_cast<Instruction>(Val: V);
1939 if (!Inst || Inst->getParent()->isEntryBlock())
1940 return true;
1941
1942 return isNotInCycle(I: Inst, DT: getDT(AAQI), /*LI=*/nullptr, /*CI=*/nullptr);
1943}
1944
1945/// Computes the symbolic difference between two de-composed GEPs.
1946void BasicAAResult::subtractDecomposedGEPs(DecomposedGEP &DestGEP,
1947 const DecomposedGEP &SrcGEP,
1948 const AAQueryInfo &AAQI) {
1949 // Drop nuw flag from GEP if subtraction of constant offsets overflows in an
1950 // unsigned sense.
1951 if (DestGEP.Offset.ult(RHS: SrcGEP.Offset))
1952 DestGEP.NWFlags = DestGEP.NWFlags.withoutNoUnsignedWrap();
1953
1954 DestGEP.Offset -= SrcGEP.Offset;
1955 for (const VariableGEPIndex &Src : SrcGEP.VarIndices) {
1956 // Find V in Dest. This is N^2, but pointer indices almost never have more
1957 // than a few variable indexes.
1958 bool Found = false;
1959 for (auto I : enumerate(First&: DestGEP.VarIndices)) {
1960 VariableGEPIndex &Dest = I.value();
1961 if ((!isValueEqualInPotentialCycles(V: Dest.Val.V, V2: Src.Val.V, AAQI) &&
1962 !areBothVScale(V1: Dest.Val.V, V2: Src.Val.V)) ||
1963 !Dest.Val.hasSameCastsAs(Other: Src.Val))
1964 continue;
1965
1966 // Normalize IsNegated if we're going to lose the NSW flag anyway.
1967 if (Dest.IsNegated) {
1968 Dest.Scale = -Dest.Scale;
1969 Dest.IsNegated = false;
1970 Dest.IsNSW = false;
1971 }
1972
1973 // If we found it, subtract off Scale V's from the entry in Dest. If it
1974 // goes to zero, remove the entry.
1975 if (Dest.Scale != Src.Scale) {
1976 // Drop nuw flag from GEP if subtraction of V's Scale overflows in an
1977 // unsigned sense.
1978 if (Dest.Scale.ult(RHS: Src.Scale))
1979 DestGEP.NWFlags = DestGEP.NWFlags.withoutNoUnsignedWrap();
1980
1981 Dest.Scale -= Src.Scale;
1982 Dest.IsNSW = false;
1983 } else {
1984 DestGEP.VarIndices.erase(CI: DestGEP.VarIndices.begin() + I.index());
1985 }
1986 Found = true;
1987 break;
1988 }
1989
1990 // If we didn't consume this entry, add it to the end of the Dest list.
1991 if (!Found) {
1992 VariableGEPIndex Entry = {.Val: Src.Val, .Scale: Src.Scale, .CxtI: Src.CxtI, .IsNSW: Src.IsNSW,
1993 /* IsNegated */ true};
1994 DestGEP.VarIndices.push_back(Elt: Entry);
1995
1996 // Drop nuw flag when we have unconsumed variable indices from SrcGEP.
1997 DestGEP.NWFlags = DestGEP.NWFlags.withoutNoUnsignedWrap();
1998 }
1999 }
2000}
2001
2002bool BasicAAResult::constantOffsetHeuristic(const DecomposedGEP &GEP,
2003 LocationSize MaybeV1Size,
2004 LocationSize MaybeV2Size,
2005 AssumptionCache *AC,
2006 DominatorTree *DT,
2007 const AAQueryInfo &AAQI) {
2008 if (GEP.VarIndices.size() != 2 || !MaybeV1Size.hasValue() ||
2009 !MaybeV2Size.hasValue())
2010 return false;
2011
2012 const uint64_t V1Size = MaybeV1Size.getValue();
2013 const uint64_t V2Size = MaybeV2Size.getValue();
2014
2015 const VariableGEPIndex &Var0 = GEP.VarIndices[0], &Var1 = GEP.VarIndices[1];
2016
2017 if (Var0.Val.TruncBits != 0 || !Var0.Val.hasSameCastsAs(Other: Var1.Val) ||
2018 !Var0.hasNegatedScaleOf(Other: Var1) ||
2019 Var0.Val.V->getType() != Var1.Val.V->getType())
2020 return false;
2021
2022 // We'll strip off the Extensions of Var0 and Var1 and do another round
2023 // of GetLinearExpression decomposition. In the example above, if Var0
2024 // is zext(%x + 1) we should get V1 == %x and V1Offset == 1.
2025
2026 LinearExpression E0 =
2027 GetLinearExpression(Val: CastedValue(Var0.Val.V), DL, Depth: 0, AC, DT);
2028 LinearExpression E1 =
2029 GetLinearExpression(Val: CastedValue(Var1.Val.V), DL, Depth: 0, AC, DT);
2030 if (E0.Scale != E1.Scale || !E0.Val.hasSameCastsAs(Other: E1.Val) ||
2031 !isValueEqualInPotentialCycles(V: E0.Val.V, V2: E1.Val.V, AAQI))
2032 return false;
2033
2034 // We have a hit - Var0 and Var1 only differ by a constant offset!
2035
2036 // If we've been sext'ed then zext'd the maximum difference between Var0 and
2037 // Var1 is possible to calculate, but we're just interested in the absolute
2038 // minimum difference between the two. The minimum distance may occur due to
2039 // wrapping; consider "add i3 %i, 5": if %i == 7 then 7 + 5 mod 8 == 4, and so
2040 // the minimum distance between %i and %i + 5 is 3.
2041 APInt MinDiff = E0.Offset - E1.Offset, Wrapped = -MinDiff;
2042 MinDiff = APIntOps::umin(A: MinDiff, B: Wrapped);
2043 APInt MinDiffBytes =
2044 MinDiff.zextOrTrunc(width: Var0.Scale.getBitWidth()) * Var0.Scale.abs();
2045
2046 // We can't definitely say whether GEP1 is before or after V2 due to wrapping
2047 // arithmetic (i.e. for some values of GEP1 and V2 GEP1 < V2, and for other
2048 // values GEP1 > V2). We'll therefore only declare NoAlias if both V1Size and
2049 // V2Size can fit in the MinDiffBytes gap.
2050 return MinDiffBytes.uge(RHS: V1Size + GEP.Offset.abs()) &&
2051 MinDiffBytes.uge(RHS: V2Size + GEP.Offset.abs());
2052}
2053
2054//===----------------------------------------------------------------------===//
2055// BasicAliasAnalysis Pass
2056//===----------------------------------------------------------------------===//
2057
2058AnalysisKey BasicAA::Key;
2059
2060BasicAAResult BasicAA::run(Function &F, FunctionAnalysisManager &AM) {
2061 auto &TLI = AM.getResult<TargetLibraryAnalysis>(IR&: F);
2062 auto &AC = AM.getResult<AssumptionAnalysis>(IR&: F);
2063 auto *DT = &AM.getResult<DominatorTreeAnalysis>(IR&: F);
2064 return BasicAAResult(F.getDataLayout(), F, TLI, AC, DT);
2065}
2066
2067BasicAAWrapperPass::BasicAAWrapperPass() : FunctionPass(ID) {}
2068
2069char BasicAAWrapperPass::ID = 0;
2070
2071void BasicAAWrapperPass::anchor() {}
2072
2073INITIALIZE_PASS_BEGIN(BasicAAWrapperPass, "basic-aa",
2074 "Basic Alias Analysis (stateless AA impl)", true, true)
2075INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
2076INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
2077INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
2078INITIALIZE_PASS_END(BasicAAWrapperPass, "basic-aa",
2079 "Basic Alias Analysis (stateless AA impl)", true, true)
2080
2081FunctionPass *llvm::createBasicAAWrapperPass() {
2082 return new BasicAAWrapperPass();
2083}
2084
2085bool BasicAAWrapperPass::runOnFunction(Function &F) {
2086 auto &ACT = getAnalysis<AssumptionCacheTracker>();
2087 auto &TLIWP = getAnalysis<TargetLibraryInfoWrapperPass>();
2088 auto &DTWP = getAnalysis<DominatorTreeWrapperPass>();
2089
2090 Result.reset(p: new BasicAAResult(F.getDataLayout(), F,
2091 TLIWP.getTLI(F), ACT.getAssumptionCache(F),
2092 &DTWP.getDomTree()));
2093
2094 return false;
2095}
2096
2097void BasicAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
2098 AU.setPreservesAll();
2099 AU.addRequiredTransitive<AssumptionCacheTracker>();
2100 AU.addRequiredTransitive<DominatorTreeWrapperPass>();
2101 AU.addRequiredTransitive<TargetLibraryInfoWrapperPass>();
2102}
2103