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