LLVM  15.0.0git
Loads.cpp
Go to the documentation of this file.
1 //===- Loads.cpp - Local load analysis ------------------------------------===//
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 simple local analyses for load instructions.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "llvm/Analysis/Loads.h"
16 #include "llvm/Analysis/LoopInfo.h"
22 #include "llvm/IR/DataLayout.h"
23 #include "llvm/IR/IntrinsicInst.h"
24 #include "llvm/IR/Module.h"
25 #include "llvm/IR/Operator.h"
26 
27 using namespace llvm;
28 
29 static bool isAligned(const Value *Base, const APInt &Offset, Align Alignment,
30  const DataLayout &DL) {
31  Align BA = Base->getPointerAlignment(DL);
32  const APInt APAlign(Offset.getBitWidth(), Alignment.value());
33  assert(APAlign.isPowerOf2() && "must be a power of 2!");
34  return BA >= Alignment && !(Offset & (APAlign - 1));
35 }
36 
37 /// Test if V is always a pointer to allocated and suitably aligned memory for
38 /// a simple load or store.
40  const Value *V, Align Alignment, const APInt &Size, const DataLayout &DL,
41  const Instruction *CtxI, const DominatorTree *DT,
43  unsigned MaxDepth) {
44  assert(V->getType()->isPointerTy() && "Base must be pointer");
45 
46  // Recursion limit.
47  if (MaxDepth-- == 0)
48  return false;
49 
50  // Already visited? Bail out, we've likely hit unreachable code.
51  if (!Visited.insert(V).second)
52  return false;
53 
54  // Note that it is not safe to speculate into a malloc'd region because
55  // malloc may return null.
56 
57  // Recurse into both hands of select.
58  if (const SelectInst *Sel = dyn_cast<SelectInst>(V)) {
59  return isDereferenceableAndAlignedPointer(Sel->getTrueValue(), Alignment,
60  Size, DL, CtxI, DT, TLI, Visited,
61  MaxDepth) &&
62  isDereferenceableAndAlignedPointer(Sel->getFalseValue(), Alignment,
63  Size, DL, CtxI, DT, TLI, Visited,
64  MaxDepth);
65  }
66 
67  // bitcast instructions are no-ops as far as dereferenceability is concerned.
68  if (const BitCastOperator *BC = dyn_cast<BitCastOperator>(V)) {
69  if (BC->getSrcTy()->isPointerTy())
71  BC->getOperand(0), Alignment, Size, DL, CtxI, DT, TLI,
72  Visited, MaxDepth);
73  }
74 
75  bool CheckForNonNull, CheckForFreed;
76  APInt KnownDerefBytes(Size.getBitWidth(),
77  V->getPointerDereferenceableBytes(DL, CheckForNonNull,
78  CheckForFreed));
79  if (KnownDerefBytes.getBoolValue() && KnownDerefBytes.uge(Size) &&
80  !CheckForFreed)
81  if (!CheckForNonNull || isKnownNonZero(V, DL, 0, nullptr, CtxI, DT)) {
82  // As we recursed through GEPs to get here, we've incrementally checked
83  // that each step advanced by a multiple of the alignment. If our base is
84  // properly aligned, then the original offset accessed must also be.
85  Type *Ty = V->getType();
86  assert(Ty->isSized() && "must be sized");
87  APInt Offset(DL.getTypeStoreSizeInBits(Ty), 0);
88  return isAligned(V, Offset, Alignment, DL);
89  }
90 
91  if (CtxI) {
92  /// Look through assumes to see if both dereferencability and alignment can
93  /// be provent by an assume
94  RetainedKnowledge AlignRK;
95  RetainedKnowledge DerefRK;
97  V, {Attribute::Dereferenceable, Attribute::Alignment}, nullptr,
98  [&](RetainedKnowledge RK, Instruction *Assume, auto) {
99  if (!isValidAssumeForContext(Assume, CtxI))
100  return false;
101  if (RK.AttrKind == Attribute::Alignment)
102  AlignRK = std::max(AlignRK, RK);
103  if (RK.AttrKind == Attribute::Dereferenceable)
104  DerefRK = std::max(DerefRK, RK);
105  if (AlignRK && DerefRK && AlignRK.ArgValue >= Alignment.value() &&
106  DerefRK.ArgValue >= Size.getZExtValue())
107  return true; // We have found what we needed so we stop looking
108  return false; // Other assumes may have better information. so
109  // keep looking
110  }))
111  return true;
112  }
113  /// TODO refactor this function to be able to search independently for
114  /// Dereferencability and Alignment requirements.
115 
116  // For GEPs, determine if the indexing lands within the allocated object.
117  if (const GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
118  const Value *Base = GEP->getPointerOperand();
119 
120  APInt Offset(DL.getIndexTypeSizeInBits(GEP->getType()), 0);
121  if (!GEP->accumulateConstantOffset(DL, Offset) || Offset.isNegative() ||
122  !Offset.urem(APInt(Offset.getBitWidth(), Alignment.value()))
123  .isMinValue())
124  return false;
125 
126  // If the base pointer is dereferenceable for Offset+Size bytes, then the
127  // GEP (== Base + Offset) is dereferenceable for Size bytes. If the base
128  // pointer is aligned to Align bytes, and the Offset is divisible by Align
129  // then the GEP (== Base + Offset == k_0 * Align + k_1 * Align) is also
130  // aligned to Align bytes.
131 
132  // Offset and Size may have different bit widths if we have visited an
133  // addrspacecast, so we can't do arithmetic directly on the APInt values.
135  Base, Alignment, Offset + Size.sextOrTrunc(Offset.getBitWidth()), DL,
136  CtxI, DT, TLI, Visited, MaxDepth);
137  }
138 
139  // For gc.relocate, look through relocations
140  if (const GCRelocateInst *RelocateInst = dyn_cast<GCRelocateInst>(V))
141  return isDereferenceableAndAlignedPointer(RelocateInst->getDerivedPtr(),
142  Alignment, Size, DL, CtxI, DT,
143  TLI, Visited, MaxDepth);
144 
145  if (const AddrSpaceCastOperator *ASC = dyn_cast<AddrSpaceCastOperator>(V))
146  return isDereferenceableAndAlignedPointer(ASC->getOperand(0), Alignment,
147  Size, DL, CtxI, DT, TLI,
148  Visited, MaxDepth);
149 
150  if (const auto *Call = dyn_cast<CallBase>(V)) {
151  if (auto *RP = getArgumentAliasingToReturnedPointer(Call, true))
152  return isDereferenceableAndAlignedPointer(RP, Alignment, Size, DL, CtxI,
153  DT, TLI, Visited, MaxDepth);
154 
155  // If we have a call we can't recurse through, check to see if this is an
156  // allocation function for which we can establish an minimum object size.
157  // Such a minimum object size is analogous to a deref_or_null attribute in
158  // that we still need to prove the result non-null at point of use.
159  // NOTE: We can only use the object size as a base fact as we a) need to
160  // prove alignment too, and b) don't want the compile time impact of a
161  // separate recursive walk.
162  ObjectSizeOpts Opts;
163  // TODO: It may be okay to round to align, but that would imply that
164  // accessing slightly out of bounds was legal, and we're currently
165  // inconsistent about that. For the moment, be conservative.
166  Opts.RoundToAlign = false;
167  Opts.NullIsUnknownSize = true;
168  uint64_t ObjSize;
169  if (getObjectSize(V, ObjSize, DL, TLI, Opts)) {
170  APInt KnownDerefBytes(Size.getBitWidth(), ObjSize);
171  if (KnownDerefBytes.getBoolValue() && KnownDerefBytes.uge(Size) &&
172  isKnownNonZero(V, DL, 0, nullptr, CtxI, DT) && !V->canBeFreed()) {
173  // As we recursed through GEPs to get here, we've incrementally
174  // checked that each step advanced by a multiple of the alignment. If
175  // our base is properly aligned, then the original offset accessed
176  // must also be.
177  Type *Ty = V->getType();
178  assert(Ty->isSized() && "must be sized");
179  APInt Offset(DL.getTypeStoreSizeInBits(Ty), 0);
180  return isAligned(V, Offset, Alignment, DL);
181  }
182  }
183  }
184 
185  // If we don't know, assume the worst.
186  return false;
187 }
188 
190  const APInt &Size,
191  const DataLayout &DL,
192  const Instruction *CtxI,
193  const DominatorTree *DT,
194  const TargetLibraryInfo *TLI) {
195  // Note: At the moment, Size can be zero. This ends up being interpreted as
196  // a query of whether [Base, V] is dereferenceable and V is aligned (since
197  // that's what the implementation happened to do). It's unclear if this is
198  // the desired semantic, but at least SelectionDAG does exercise this case.
199 
201  return ::isDereferenceableAndAlignedPointer(V, Alignment, Size, DL, CtxI, DT,
202  TLI, Visited, 16);
203 }
204 
206  Align Alignment,
207  const DataLayout &DL,
208  const Instruction *CtxI,
209  const DominatorTree *DT,
210  const TargetLibraryInfo *TLI) {
211  // For unsized types or scalable vectors we don't know exactly how many bytes
212  // are dereferenced, so bail out.
213  if (!Ty->isSized() || isa<ScalableVectorType>(Ty))
214  return false;
215 
216  // When dereferenceability information is provided by a dereferenceable
217  // attribute, we know exactly how many bytes are dereferenceable. If we can
218  // determine the exact offset to the attributed variable, we can use that
219  // information here.
220 
221  APInt AccessSize(DL.getPointerTypeSizeInBits(V->getType()),
222  DL.getTypeStoreSize(Ty));
223  return isDereferenceableAndAlignedPointer(V, Alignment, AccessSize, DL, CtxI,
224  DT, TLI);
225 }
226 
228  const DataLayout &DL,
229  const Instruction *CtxI,
230  const DominatorTree *DT,
231  const TargetLibraryInfo *TLI) {
232  return isDereferenceableAndAlignedPointer(V, Ty, Align(1), DL, CtxI, DT, TLI);
233 }
234 
235 /// Test if A and B will obviously have the same value.
236 ///
237 /// This includes recognizing that %t0 and %t1 will have the same
238 /// value in code like this:
239 /// \code
240 /// %t0 = getelementptr \@a, 0, 3
241 /// store i32 0, i32* %t0
242 /// %t1 = getelementptr \@a, 0, 3
243 /// %t2 = load i32* %t1
244 /// \endcode
245 ///
246 static bool AreEquivalentAddressValues(const Value *A, const Value *B) {
247  // Test if the values are trivially equivalent.
248  if (A == B)
249  return true;
250 
251  // Test if the values come from identical arithmetic instructions.
252  // Use isIdenticalToWhenDefined instead of isIdenticalTo because
253  // this function is only used when one address use dominates the
254  // other, which means that they'll always either have the same
255  // value or one of them will have an undefined value.
256  if (isa<BinaryOperator>(A) || isa<CastInst>(A) || isa<PHINode>(A) ||
257  isa<GetElementPtrInst>(A))
258  if (const Instruction *BI = dyn_cast<Instruction>(B))
259  if (cast<Instruction>(A)->isIdenticalToWhenDefined(BI))
260  return true;
261 
262  // Otherwise they may not be equivalent.
263  return false;
264 }
265 
267  ScalarEvolution &SE,
268  DominatorTree &DT) {
269  auto &DL = LI->getModule()->getDataLayout();
270  Value *Ptr = LI->getPointerOperand();
271 
272  APInt EltSize(DL.getIndexTypeSizeInBits(Ptr->getType()),
273  DL.getTypeStoreSize(LI->getType()).getFixedSize());
274  const Align Alignment = LI->getAlign();
275 
276  Instruction *HeaderFirstNonPHI = L->getHeader()->getFirstNonPHI();
277 
278  // If given a uniform (i.e. non-varying) address, see if we can prove the
279  // access is safe within the loop w/o needing predication.
280  if (L->isLoopInvariant(Ptr))
281  return isDereferenceableAndAlignedPointer(Ptr, Alignment, EltSize, DL,
282  HeaderFirstNonPHI, &DT);
283 
284  // Otherwise, check to see if we have a repeating access pattern where we can
285  // prove that all accesses are well aligned and dereferenceable.
286  auto *AddRec = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(Ptr));
287  if (!AddRec || AddRec->getLoop() != L || !AddRec->isAffine())
288  return false;
289  auto* Step = dyn_cast<SCEVConstant>(AddRec->getStepRecurrence(SE));
290  if (!Step)
291  return false;
292  // TODO: generalize to access patterns which have gaps
293  if (Step->getAPInt() != EltSize)
294  return false;
295 
296  auto TC = SE.getSmallConstantMaxTripCount(L);
297  if (!TC)
298  return false;
299 
300  const APInt AccessSize = TC * EltSize;
301 
302  auto *StartS = dyn_cast<SCEVUnknown>(AddRec->getStart());
303  if (!StartS)
304  return false;
305  assert(SE.isLoopInvariant(StartS, L) && "implied by addrec definition");
306  Value *Base = StartS->getValue();
307 
308  // For the moment, restrict ourselves to the case where the access size is a
309  // multiple of the requested alignment and the base is aligned.
310  // TODO: generalize if a case found which warrants
311  if (EltSize.urem(Alignment.value()) != 0)
312  return false;
313  return isDereferenceableAndAlignedPointer(Base, Alignment, AccessSize, DL,
314  HeaderFirstNonPHI, &DT);
315 }
316 
317 /// Check if executing a load of this pointer value cannot trap.
318 ///
319 /// If DT and ScanFrom are specified this method performs context-sensitive
320 /// analysis and returns true if it is safe to load immediately before ScanFrom.
321 ///
322 /// If it is not obviously safe to load from the specified pointer, we do
323 /// a quick local scan of the basic block containing \c ScanFrom, to determine
324 /// if the address is already accessed.
325 ///
326 /// This uses the pointee type to determine how many bytes need to be safe to
327 /// load from the pointer.
329  const DataLayout &DL,
330  Instruction *ScanFrom,
331  const DominatorTree *DT,
332  const TargetLibraryInfo *TLI) {
333  // If DT is not specified we can't make context-sensitive query
334  const Instruction* CtxI = DT ? ScanFrom : nullptr;
335  if (isDereferenceableAndAlignedPointer(V, Alignment, Size, DL, CtxI, DT, TLI))
336  return true;
337 
338  if (!ScanFrom)
339  return false;
340 
341  if (Size.getBitWidth() > 64)
342  return false;
343  const uint64_t LoadSize = Size.getZExtValue();
344 
345  // Otherwise, be a little bit aggressive by scanning the local block where we
346  // want to check to see if the pointer is already being loaded or stored
347  // from/to. If so, the previous load or store would have already trapped,
348  // so there is no harm doing an extra load (also, CSE will later eliminate
349  // the load entirely).
350  BasicBlock::iterator BBI = ScanFrom->getIterator(),
351  E = ScanFrom->getParent()->begin();
352 
353  // We can at least always strip pointer casts even though we can't use the
354  // base here.
355  V = V->stripPointerCasts();
356 
357  while (BBI != E) {
358  --BBI;
359 
360  // If we see a free or a call which may write to memory (i.e. which might do
361  // a free) the pointer could be marked invalid.
362  if (isa<CallInst>(BBI) && BBI->mayWriteToMemory() &&
363  !isa<DbgInfoIntrinsic>(BBI))
364  return false;
365 
366  Value *AccessedPtr;
367  Type *AccessedTy;
368  Align AccessedAlign;
369  if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) {
370  // Ignore volatile loads. The execution of a volatile load cannot
371  // be used to prove an address is backed by regular memory; it can,
372  // for example, point to an MMIO register.
373  if (LI->isVolatile())
374  continue;
375  AccessedPtr = LI->getPointerOperand();
376  AccessedTy = LI->getType();
377  AccessedAlign = LI->getAlign();
378  } else if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) {
379  // Ignore volatile stores (see comment for loads).
380  if (SI->isVolatile())
381  continue;
382  AccessedPtr = SI->getPointerOperand();
383  AccessedTy = SI->getValueOperand()->getType();
384  AccessedAlign = SI->getAlign();
385  } else
386  continue;
387 
388  if (AccessedAlign < Alignment)
389  continue;
390 
391  // Handle trivial cases.
392  if (AccessedPtr == V &&
393  LoadSize <= DL.getTypeStoreSize(AccessedTy))
394  return true;
395 
396  if (AreEquivalentAddressValues(AccessedPtr->stripPointerCasts(), V) &&
397  LoadSize <= DL.getTypeStoreSize(AccessedTy))
398  return true;
399  }
400  return false;
401 }
402 
404  const DataLayout &DL,
405  Instruction *ScanFrom,
406  const DominatorTree *DT,
407  const TargetLibraryInfo *TLI) {
408  APInt Size(DL.getIndexTypeSizeInBits(V->getType()), DL.getTypeStoreSize(Ty));
409  return isSafeToLoadUnconditionally(V, Alignment, Size, DL, ScanFrom, DT, TLI);
410 }
411 
412 /// DefMaxInstsToScan - the default number of maximum instructions
413 /// to scan in the block, used by FindAvailableLoadedValue().
414 /// FindAvailableLoadedValue() was introduced in r60148, to improve jump
415 /// threading in part by eliminating partially redundant loads.
416 /// At that point, the value of MaxInstsToScan was already set to '6'
417 /// without documented explanation.
419 llvm::DefMaxInstsToScan("available-load-scan-limit", cl::init(6), cl::Hidden,
420  cl::desc("Use this to specify the default maximum number of instructions "
421  "to scan backward from a given instruction, when searching for "
422  "available loaded value"));
423 
425  BasicBlock *ScanBB,
426  BasicBlock::iterator &ScanFrom,
427  unsigned MaxInstsToScan,
428  AAResults *AA, bool *IsLoad,
429  unsigned *NumScanedInst) {
430  // Don't CSE load that is volatile or anything stronger than unordered.
431  if (!Load->isUnordered())
432  return nullptr;
433 
435  return findAvailablePtrLoadStore(Loc, Load->getType(), Load->isAtomic(),
436  ScanBB, ScanFrom, MaxInstsToScan, AA, IsLoad,
437  NumScanedInst);
438 }
439 
440 // Check if the load and the store have the same base, constant offsets and
441 // non-overlapping access ranges.
442 static bool areNonOverlapSameBaseLoadAndStore(const Value *LoadPtr,
443  Type *LoadTy,
444  const Value *StorePtr,
445  Type *StoreTy,
446  const DataLayout &DL) {
447  APInt LoadOffset(DL.getIndexTypeSizeInBits(LoadPtr->getType()), 0);
448  APInt StoreOffset(DL.getIndexTypeSizeInBits(StorePtr->getType()), 0);
449  const Value *LoadBase = LoadPtr->stripAndAccumulateConstantOffsets(
450  DL, LoadOffset, /* AllowNonInbounds */ false);
451  const Value *StoreBase = StorePtr->stripAndAccumulateConstantOffsets(
452  DL, StoreOffset, /* AllowNonInbounds */ false);
453  if (LoadBase != StoreBase)
454  return false;
455  auto LoadAccessSize = LocationSize::precise(DL.getTypeStoreSize(LoadTy));
456  auto StoreAccessSize = LocationSize::precise(DL.getTypeStoreSize(StoreTy));
457  ConstantRange LoadRange(LoadOffset,
458  LoadOffset + LoadAccessSize.toRaw());
459  ConstantRange StoreRange(StoreOffset,
460  StoreOffset + StoreAccessSize.toRaw());
461  return LoadRange.intersectWith(StoreRange).isEmptySet();
462 }
463 
464 static Value *getAvailableLoadStore(Instruction *Inst, const Value *Ptr,
465  Type *AccessTy, bool AtLeastAtomic,
466  const DataLayout &DL, bool *IsLoadCSE) {
467  // If this is a load of Ptr, the loaded value is available.
468  // (This is true even if the load is volatile or atomic, although
469  // those cases are unlikely.)
470  if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
471  // We can value forward from an atomic to a non-atomic, but not the
472  // other way around.
473  if (LI->isAtomic() < AtLeastAtomic)
474  return nullptr;
475 
476  Value *LoadPtr = LI->getPointerOperand()->stripPointerCasts();
477  if (!AreEquivalentAddressValues(LoadPtr, Ptr))
478  return nullptr;
479 
480  if (CastInst::isBitOrNoopPointerCastable(LI->getType(), AccessTy, DL)) {
481  if (IsLoadCSE)
482  *IsLoadCSE = true;
483  return LI;
484  }
485  }
486 
487  // If this is a store through Ptr, the value is available!
488  // (This is true even if the store is volatile or atomic, although
489  // those cases are unlikely.)
490  if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
491  // We can value forward from an atomic to a non-atomic, but not the
492  // other way around.
493  if (SI->isAtomic() < AtLeastAtomic)
494  return nullptr;
495 
496  Value *StorePtr = SI->getPointerOperand()->stripPointerCasts();
497  if (!AreEquivalentAddressValues(StorePtr, Ptr))
498  return nullptr;
499 
500  if (IsLoadCSE)
501  *IsLoadCSE = false;
502 
503  Value *Val = SI->getValueOperand();
504  if (CastInst::isBitOrNoopPointerCastable(Val->getType(), AccessTy, DL))
505  return Val;
506 
507  TypeSize StoreSize = DL.getTypeSizeInBits(Val->getType());
508  TypeSize LoadSize = DL.getTypeSizeInBits(AccessTy);
509  if (TypeSize::isKnownLE(LoadSize, StoreSize))
510  if (auto *C = dyn_cast<Constant>(Val))
511  return ConstantFoldLoadFromConst(C, AccessTy, DL);
512  }
513 
514  return nullptr;
515 }
516 
518  const MemoryLocation &Loc, Type *AccessTy, bool AtLeastAtomic,
519  BasicBlock *ScanBB, BasicBlock::iterator &ScanFrom, unsigned MaxInstsToScan,
520  AAResults *AA, bool *IsLoadCSE, unsigned *NumScanedInst) {
521  if (MaxInstsToScan == 0)
522  MaxInstsToScan = ~0U;
523 
524  const DataLayout &DL = ScanBB->getModule()->getDataLayout();
525  const Value *StrippedPtr = Loc.Ptr->stripPointerCasts();
526 
527  while (ScanFrom != ScanBB->begin()) {
528  // We must ignore debug info directives when counting (otherwise they
529  // would affect codegen).
530  Instruction *Inst = &*--ScanFrom;
531  if (Inst->isDebugOrPseudoInst())
532  continue;
533 
534  // Restore ScanFrom to expected value in case next test succeeds
535  ScanFrom++;
536 
537  if (NumScanedInst)
538  ++(*NumScanedInst);
539 
540  // Don't scan huge blocks.
541  if (MaxInstsToScan-- == 0)
542  return nullptr;
543 
544  --ScanFrom;
545 
546  if (Value *Available = getAvailableLoadStore(Inst, StrippedPtr, AccessTy,
547  AtLeastAtomic, DL, IsLoadCSE))
548  return Available;
549 
550  // Try to get the store size for the type.
551  if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
552  Value *StorePtr = SI->getPointerOperand()->stripPointerCasts();
553 
554  // If both StrippedPtr and StorePtr reach all the way to an alloca or
555  // global and they are different, ignore the store. This is a trivial form
556  // of alias analysis that is important for reg2mem'd code.
557  if ((isa<AllocaInst>(StrippedPtr) || isa<GlobalVariable>(StrippedPtr)) &&
558  (isa<AllocaInst>(StorePtr) || isa<GlobalVariable>(StorePtr)) &&
559  StrippedPtr != StorePtr)
560  continue;
561 
562  if (!AA) {
563  // When AA isn't available, but if the load and the store have the same
564  // base, constant offsets and non-overlapping access ranges, ignore the
565  // store. This is a simple form of alias analysis that is used by the
566  // inliner. FIXME: use BasicAA if possible.
568  Loc.Ptr, AccessTy, SI->getPointerOperand(),
569  SI->getValueOperand()->getType(), DL))
570  continue;
571  } else {
572  // If we have alias analysis and it says the store won't modify the
573  // loaded value, ignore the store.
574  if (!isModSet(AA->getModRefInfo(SI, Loc)))
575  continue;
576  }
577 
578  // Otherwise the store that may or may not alias the pointer, bail out.
579  ++ScanFrom;
580  return nullptr;
581  }
582 
583  // If this is some other instruction that may clobber Ptr, bail out.
584  if (Inst->mayWriteToMemory()) {
585  // If alias analysis claims that it really won't modify the load,
586  // ignore it.
587  if (AA && !isModSet(AA->getModRefInfo(Inst, Loc)))
588  continue;
589 
590  // May modify the pointer, bail out.
591  ++ScanFrom;
592  return nullptr;
593  }
594  }
595 
596  // Got to the start of the block, we didn't find it, but are done for this
597  // block.
598  return nullptr;
599 }
600 
602  bool *IsLoadCSE,
603  unsigned MaxInstsToScan) {
604  const DataLayout &DL = Load->getModule()->getDataLayout();
605  Value *StrippedPtr = Load->getPointerOperand()->stripPointerCasts();
606  BasicBlock *ScanBB = Load->getParent();
607  Type *AccessTy = Load->getType();
608  bool AtLeastAtomic = Load->isAtomic();
609 
610  if (!Load->isUnordered())
611  return nullptr;
612 
613  // Try to find an available value first, and delay expensive alias analysis
614  // queries until later.
615  Value *Available = nullptr;;
616  SmallVector<Instruction *> MustNotAliasInsts;
617  for (Instruction &Inst : make_range(++Load->getReverseIterator(),
618  ScanBB->rend())) {
619  if (Inst.isDebugOrPseudoInst())
620  continue;
621 
622  if (MaxInstsToScan-- == 0)
623  return nullptr;
624 
625  Available = getAvailableLoadStore(&Inst, StrippedPtr, AccessTy,
626  AtLeastAtomic, DL, IsLoadCSE);
627  if (Available)
628  break;
629 
630  if (Inst.mayWriteToMemory())
631  MustNotAliasInsts.push_back(&Inst);
632  }
633 
634  // If we found an available value, ensure that the instructions in between
635  // did not modify the memory location.
636  if (Available) {
638  for (Instruction *Inst : MustNotAliasInsts)
639  if (isModSet(AA.getModRefInfo(Inst, Loc)))
640  return nullptr;
641  }
642 
643  return Available;
644 }
645 
647  Instruction *CtxI) {
648  Type *Ty = A->getType();
649  assert(Ty == B->getType() && Ty->isPointerTy() &&
650  "values must have matching pointer types");
651 
652  // NOTE: The checks in the function are incomplete and currently miss illegal
653  // cases! The current implementation is a starting point and the
654  // implementation should be made stricter over time.
655  if (auto *C = dyn_cast<Constant>(B)) {
656  // Do not allow replacing a pointer with a constant pointer, unless it is
657  // either null or at least one byte is dereferenceable.
658  APInt OneByte(DL.getPointerTypeSizeInBits(Ty), 1);
659  return C->isNullValue() ||
660  isDereferenceableAndAlignedPointer(B, Align(1), OneByte, DL, CtxI);
661  }
662 
663  return true;
664 }
llvm::Type::isSized
bool isSized(SmallPtrSetImpl< Type * > *Visited=nullptr) const
Return true if it makes sense to take the size of this type.
Definition: Type.h:264
llvm::Loop::isLoopInvariant
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
Definition: LoopInfo.cpp:60
llvm::isAligned
bool isAligned(Align Lhs, uint64_t SizeInBytes)
Checks that SizeInBytes is a multiple of the alignment.
Definition: Alignment.h:138
llvm::MemoryLocation::get
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
Definition: MemoryLocation.cpp:35
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::Instruction::getModule
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:65
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
IntrinsicInst.h
llvm::Type::isPointerTy
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:218
llvm::MemoryLocation::Ptr
const Value * Ptr
The address of the start of the location.
Definition: MemoryLocation.h:218
Loads.h
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
isDereferenceableAndAlignedPointer
static bool isDereferenceableAndAlignedPointer(const Value *V, Align Alignment, const APInt &Size, const DataLayout &DL, const Instruction *CtxI, const DominatorTree *DT, const TargetLibraryInfo *TLI, SmallPtrSetImpl< const Value * > &Visited, unsigned MaxDepth)
Test if V is always a pointer to allocated and suitably aligned memory for a simple load or store.
Definition: Loads.cpp:39
llvm::APInt::isPowerOf2
bool isPowerOf2() const
Check if this APInt's value is a power of two greater than zero.
Definition: APInt.h:425
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
llvm::LinearPolySize< TypeSize >::isKnownLE
static bool isKnownLE(const LinearPolySize &LHS, const LinearPolySize &RHS)
Definition: TypeSize.h:340
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:449
ValueTracking.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::canReplacePointersIfEqual
bool canReplacePointersIfEqual(Value *A, Value *B, const DataLayout &DL, Instruction *CtxI)
Returns true if a pointer value A can be replace with another pointer value \B if they are deemed equ...
Definition: Loads.cpp:646
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:139
llvm::isKnownNonZero
bool isKnownNonZero(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if the given value is known to be non-zero when defined.
Definition: ValueTracking.cpp:340
ScalarEvolution.h
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
Module.h
MemoryBuiltins.h
llvm::ObjectSizeOpts::NullIsUnknownSize
bool NullIsUnknownSize
If this is true, null pointers in address space 0 will be treated as though they can't be evaluated.
Definition: MemoryBuiltins.h:155
llvm::Value::stripAndAccumulateConstantOffsets
const Value * stripAndAccumulateConstantOffsets(const DataLayout &DL, APInt &Offset, bool AllowNonInbounds, bool AllowInvariantGroup=false, function_ref< bool(Value &Value, APInt &Offset)> ExternalAnalysis=nullptr) const
Accumulate the constant offset this value has compared to a base pointer.
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::ObjectSizeOpts::RoundToAlign
bool RoundToAlign
Whether to round the result up to the alignment of allocas, byval arguments, and global variables.
Definition: MemoryBuiltins.h:151
Operator.h
llvm::LoadInst::getPointerOperand
Value * getPointerOperand()
Definition: Instructions.h:268
llvm::LoadInst::getAlign
Align getAlign() const
Return the alignment of the access that is being performed.
Definition: Instructions.h:224
llvm::BasicBlock::rend
reverse_iterator rend()
Definition: BasicBlock.h:304
getAvailableLoadStore
static Value * getAvailableLoadStore(Instruction *Inst, const Value *Ptr, Type *AccessTy, bool AtLeastAtomic, const DataLayout &DL, bool *IsLoadCSE)
Definition: Loads.cpp:464
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
AliasAnalysis.h
llvm::APInt::uge
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
Definition: APInt.h:1171
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
llvm::isValidAssumeForContext
bool isValidAssumeForContext(const Instruction *I, const Instruction *CxtI, const DominatorTree *DT=nullptr)
Return true if it is valid to use the assumptions provided by an assume intrinsic,...
Definition: ValueTracking.cpp:566
llvm::BitCastOperator
Definition: Operator.h:541
llvm::AAResults
Definition: AliasAnalysis.h:511
llvm::AArch64::RP
@ RP
Definition: AArch64ISelLowering.h:480
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
AvailabilityState::Available
@ Available
We know the block is fully available. This is a fixpoint.
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:297
AssumeBundleQueries.h
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::Instruction
Definition: Instruction.h:42
llvm::isDereferenceablePointer
bool isDereferenceablePointer(const Value *V, Type *Ty, const DataLayout &DL, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if this is always a dereferenceable pointer.
Definition: Loads.cpp:227
llvm::getArgumentAliasingToReturnedPointer
const Value * getArgumentAliasingToReturnedPointer(const CallBase *Call, bool MustPreserveNullness)
This function returns call pointer argument that is considered the same by aliasing rules.
Definition: ValueTracking.cpp:4307
llvm::LocationSize::precise
static LocationSize precise(uint64_t Value)
Definition: MemoryLocation.h:101
llvm::BasicBlock::getModule
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
Definition: BasicBlock.cpp:147
Align
uint64_t Align
Definition: ELFObjHandler.cpp:81
llvm::BasicBlock::getFirstNonPHI
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:209
llvm::Align
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
llvm::Instruction::mayWriteToMemory
bool mayWriteToMemory() const
Return true if this instruction may modify memory.
Definition: Instruction.cpp:596
llvm::isModSet
LLVM_NODISCARD bool isModSet(const ModRefInfo MRI)
Definition: AliasAnalysis.h:196
llvm::getObjectSize
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.
Definition: MemoryBuiltins.cpp:558
LoopInfo.h
llvm::findAvailablePtrLoadStore
Value * findAvailablePtrLoadStore(const MemoryLocation &Loc, Type *AccessTy, bool AtLeastAtomic, BasicBlock *ScanBB, BasicBlock::iterator &ScanFrom, unsigned MaxInstsToScan, AAResults *AA, bool *IsLoadCSE, unsigned *NumScanedInst)
Scan backwards to see if we have the value of the given pointer available locally within a small numb...
Definition: Loads.cpp:517
llvm::ScalarEvolution::getSCEV
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
Definition: ScalarEvolution.cpp:4407
llvm::cl::opt
Definition: CommandLine.h:1392
llvm::RetainedKnowledge::AttrKind
Attribute::AttrKind AttrKind
Definition: AssumeBundleQueries.h:101
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:305
llvm::AddrSpaceCastOperator
Definition: Operator.h:556
llvm::GCRelocateInst
Represents calls to the gc.relocate intrinsic.
Definition: IntrinsicInst.h:1369
llvm::Value::getPointerDereferenceableBytes
uint64_t getPointerDereferenceableBytes(const DataLayout &DL, bool &CanBeNull, bool &CanBeFreed) const
Returns the number of bytes known to be dereferenceable for the pointer value.
Definition: Value.cpp:840
uint64_t
llvm::RetainedKnowledge::ArgValue
uint64_t ArgValue
Definition: AssumeBundleQueries.h:102
areNonOverlapSameBaseLoadAndStore
static bool areNonOverlapSameBaseLoadAndStore(const Value *LoadPtr, Type *LoadTy, const Value *StorePtr, Type *StoreTy, const DataLayout &DL)
Definition: Loads.cpp:442
MemoryLocation.h
llvm::ScalarEvolution::getSmallConstantMaxTripCount
unsigned getSmallConstantMaxTripCount(const Loop *L)
Returns the upper bound of the loop trip count as a normal unsigned value.
Definition: ScalarEvolution.cpp:7698
AreEquivalentAddressValues
static bool AreEquivalentAddressValues(const Value *A, const Value *B)
Test if A and B will obviously have the same value.
Definition: Loads.cpp:246
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
llvm::APInt::getBoolValue
bool getBoolValue() const
Convert APInt to a boolean value.
Definition: APInt.h:452
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1737
llvm::isDereferenceableAndAlignedInLoop
bool isDereferenceableAndAlignedInLoop(LoadInst *LI, Loop *L, ScalarEvolution &SE, DominatorTree &DT)
Return true if we can prove that the given load (which is assumed to be within the specified loop) wo...
Definition: Loads.cpp:266
llvm::GEPOperator
Definition: Operator.h:375
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::ConstantFoldLoadFromConst
Constant * ConstantFoldLoadFromConst(Constant *C, Type *Ty, const APInt &Offset, const DataLayout &DL)
Extract value of C at the given Offset reinterpreted as Ty.
Definition: ConstantFolding.cpp:666
DataLayout.h
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
if
if(llvm_vc STREQUAL "") set(fake_version_inc "$
Definition: CMakeLists.txt:14
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:82
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::CastInst::isBitOrNoopPointerCastable
static bool isBitOrNoopPointerCastable(Type *SrcTy, Type *DestTy, const DataLayout &DL)
Check whether a bitcast, inttoptr, or ptrtoint cast between these types is valid and a no-op.
Definition: Instructions.cpp:3440
llvm::RetainedKnowledge
Represent one information held inside an operand bundle of an llvm.assume.
Definition: AssumeBundleQueries.h:100
llvm::ObjectSizeOpts
Various options to control the behavior of getObjectSize.
Definition: MemoryBuiltins.h:135
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:176
llvm::Value::stripPointerCasts
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
Definition: Value.cpp:682
MaxDepth
static const unsigned MaxDepth
Definition: InstCombineMulDivRem.cpp:906
llvm::ScalarEvolution::isLoopInvariant
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
Definition: ScalarEvolution.cpp:13248
llvm::TypeSize
Definition: TypeSize.h:421
llvm::FindAvailableLoadedValue
Value * FindAvailableLoadedValue(LoadInst *Load, BasicBlock *ScanBB, BasicBlock::iterator &ScanFrom, unsigned MaxInstsToScan=DefMaxInstsToScan, AAResults *AA=nullptr, bool *IsLoadCSE=nullptr, unsigned *NumScanedInst=nullptr)
Scan backwards to see if we have the value of the given load available locally within a small number ...
Definition: Loads.cpp:424
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:222
llvm::Instruction::isDebugOrPseudoInst
bool isDebugOrPseudoInst() const
Return true if the instruction is a DbgInfoIntrinsic or PseudoProbeInst.
Definition: Instruction.cpp:735
llvm::ConstantRange
This class represents a range of values.
Definition: ConstantRange.h:47
AA
ScalarEvolutionExpressions.h
llvm::Value::canBeFreed
bool canBeFreed() const
Return true if the memory object referred to by V can by freed in the scope for which the SSA value d...
Definition: Value.cpp:778
llvm::ConstantRange::intersectWith
ConstantRange intersectWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the intersection of this range with another range.
Definition: ConstantRange.cpp:523
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
llvm::Module::getDataLayout
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:398
llvm::isSafeToLoadUnconditionally
bool isSafeToLoadUnconditionally(Value *V, Align Alignment, APInt &Size, const DataLayout &DL, Instruction *ScanFrom=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if we know that executing a load from this value cannot trap.
Definition: Loads.cpp:328
llvm::SmallPtrSetImpl< const Value * >
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:172
llvm::cl::desc
Definition: CommandLine.h:405
llvm::ConstantRange::isEmptySet
bool isEmptySet() const
Return true if this set contains no members.
Definition: ConstantRange.cpp:370
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::MemoryLocation
Representation for a specific memory location.
Definition: MemoryLocation.h:210
llvm::sampleprof::Base
@ Base
Definition: Discriminator.h:58
llvm::DefMaxInstsToScan
cl::opt< unsigned > DefMaxInstsToScan
The default number of maximum instructions to scan in the block, used by FindAvailableLoadedValue().
llvm::isDereferenceableAndAlignedPointer
bool isDereferenceableAndAlignedPointer(const Value *V, Type *Ty, Align Alignment, const DataLayout &DL, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Returns true if V is always a dereferenceable pointer with alignment greater or equal than requested.
Definition: Loads.cpp:205
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
llvm::getKnowledgeForValue
RetainedKnowledge getKnowledgeForValue(const Value *V, ArrayRef< Attribute::AttrKind > AttrKinds, AssumptionCache *AC=nullptr, function_ref< bool(RetainedKnowledge, Instruction *, const CallBase::BundleOpInfo *)> Filter=[](auto...) { return true;})
Return a valid Knowledge associated to the Value V if its Attribute kind is in AttrKinds and it match...
Definition: AssumeBundleQueries.cpp:154