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