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