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