LCOV - code coverage report
Current view: top level - lib/Analysis - Loads.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 155 159 97.5 %
Date: 2017-09-14 15:23:50 Functions: 12 12 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- Loads.cpp - Local load analysis ------------------------------------===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // This file defines simple local analyses for load instructions.
      11             : //
      12             : //===----------------------------------------------------------------------===//
      13             : 
      14             : #include "llvm/Analysis/Loads.h"
      15             : #include "llvm/Analysis/AliasAnalysis.h"
      16             : #include "llvm/Analysis/ValueTracking.h"
      17             : #include "llvm/IR/DataLayout.h"
      18             : #include "llvm/IR/GlobalAlias.h"
      19             : #include "llvm/IR/GlobalVariable.h"
      20             : #include "llvm/IR/IntrinsicInst.h"
      21             : #include "llvm/IR/LLVMContext.h"
      22             : #include "llvm/IR/Module.h"
      23             : #include "llvm/IR/Operator.h"
      24             : #include "llvm/IR/Statepoint.h"
      25             : 
      26             : using namespace llvm;
      27             : 
      28      249555 : static bool isAligned(const Value *Base, const APInt &Offset, unsigned Align,
      29             :                       const DataLayout &DL) {
      30      748665 :   APInt BaseAlign(Offset.getBitWidth(), Base->getPointerAlignment(DL));
      31             : 
      32      249555 :   if (!BaseAlign) {
      33        5318 :     Type *Ty = Base->getType()->getPointerElementType();
      34        2659 :     if (!Ty->isSized())
      35             :       return false;
      36        2657 :     BaseAlign = DL.getABITypeAlignment(Ty);
      37             :   }
      38             : 
      39      499106 :   APInt Alignment(Offset.getBitWidth(), Align);
      40             : 
      41             :   assert(Alignment.isPowerOf2() && "must be a power of 2!");
      42     2245789 :   return BaseAlign.uge(Alignment) && !(Offset & (Alignment-1));
      43             : }
      44             : 
      45      249555 : static bool isAligned(const Value *Base, unsigned Align, const DataLayout &DL) {
      46      249555 :   Type *Ty = Base->getType();
      47             :   assert(Ty->isSized() && "must be sized");
      48      748665 :   APInt Offset(DL.getTypeStoreSizeInBits(Ty), 0);
      49      499110 :   return isAligned(Base, Offset, Align, DL);
      50             : }
      51             : 
      52             : /// Test if V is always a pointer to allocated and suitably aligned memory for
      53             : /// a simple load or store.
      54      649792 : static bool isDereferenceableAndAlignedPointer(
      55             :     const Value *V, unsigned Align, const APInt &Size, const DataLayout &DL,
      56             :     const Instruction *CtxI, const DominatorTree *DT,
      57             :     SmallPtrSetImpl<const Value *> &Visited) {
      58             :   // Already visited?  Bail out, we've likely hit unreachable code.
      59      649792 :   if (!Visited.insert(V).second)
      60             :     return false;
      61             : 
      62             :   // Note that it is not safe to speculate into a malloc'd region because
      63             :   // malloc may return null.
      64             : 
      65             :   // bitcast instructions are no-ops as far as dereferenceability is concerned.
      66      102709 :   if (const BitCastOperator *BC = dyn_cast<BitCastOperator>(V))
      67      205418 :     return isDereferenceableAndAlignedPointer(BC->getOperand(0), Align, Size,
      68      102709 :                                               DL, CtxI, DT, Visited);
      69             : 
      70      547081 :   bool CheckForNonNull = false;
      71             :   APInt KnownDerefBytes(Size.getBitWidth(),
      72     1094162 :                         V->getPointerDereferenceableBytes(DL, CheckForNonNull));
      73      547081 :   if (KnownDerefBytes.getBoolValue()) {
      74      249981 :     if (KnownDerefBytes.uge(Size))
      75      249563 :       if (!CheckForNonNull || isKnownNonZero(V, DL, 0, nullptr, CtxI, DT))
      76      249555 :         return isAligned(V, Align, DL);
      77             :   }
      78             : 
      79             :   // For GEPs, determine if the indexing lands within the allocated object.
      80      222922 :   if (const GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
      81      222922 :     const Value *Base = GEP->getPointerOperand();
      82             : 
      83      668766 :     APInt Offset(DL.getPointerTypeSizeInBits(GEP->getType()), 0);
      84     1002072 :     if (!GEP->accumulateConstantOffset(DL, Offset) || Offset.isNegative() ||
      85     1223637 :         !Offset.urem(APInt(Offset.getBitWidth(), Align)).isMinValue())
      86             :       return false;
      87             : 
      88             :     // If the base pointer is dereferenceable for Offset+Size bytes, then the
      89             :     // GEP (== Base + Offset) is dereferenceable for Size bytes.  If the base
      90             :     // pointer is aligned to Align bytes, and the Offset is divisible by Align
      91             :     // then the GEP (== Base + Offset == k_0 * Align + k_1 * Align) is also
      92             :     // aligned to Align bytes.
      93             : 
      94             :     // Offset and Size may have different bit widths if we have visited an
      95             :     // addrspacecast, so we can't do arithmetic directly on the APInt values.
      96             :     return isDereferenceableAndAlignedPointer(
      97      739752 :         Base, Align, Offset + Size.sextOrTrunc(Offset.getBitWidth()),
      98      184938 :         DL, CtxI, DT, Visited);
      99             :   }
     100             : 
     101             :   // For gc.relocate, look through relocations
     102           5 :   if (const GCRelocateInst *RelocateInst = dyn_cast<GCRelocateInst>(V))
     103             :     return isDereferenceableAndAlignedPointer(
     104           5 :         RelocateInst->getDerivedPtr(), Align, Size, DL, CtxI, DT, Visited);
     105             : 
     106         140 :   if (const AddrSpaceCastInst *ASC = dyn_cast<AddrSpaceCastInst>(V))
     107         280 :     return isDereferenceableAndAlignedPointer(ASC->getOperand(0), Align, Size,
     108         140 :                                               DL, CtxI, DT, Visited);
     109             : 
     110      148918 :   if (auto CS = ImmutableCallSite(V))
     111         647 :     if (const Value *RV = CS.getReturnedArgOperand())
     112             :       return isDereferenceableAndAlignedPointer(RV, Align, Size, DL, CtxI, DT,
     113           4 :                                                 Visited);
     114             : 
     115             :   // If we don't know, assume the worst.
     116       74455 :   return false;
     117             : }
     118             : 
     119        1330 : bool llvm::isDereferenceableAndAlignedPointer(const Value *V, unsigned Align,
     120             :                                               const APInt &Size,
     121             :                                               const DataLayout &DL,
     122             :                                               const Instruction *CtxI,
     123             :                                               const DominatorTree *DT) {
     124        2660 :   SmallPtrSet<const Value *, 32> Visited;
     125             :   return ::isDereferenceableAndAlignedPointer(V, Align, Size, DL, CtxI, DT,
     126        2660 :                                               Visited);
     127             : }
     128             : 
     129      360669 : bool llvm::isDereferenceableAndAlignedPointer(const Value *V, unsigned Align,
     130             :                                               const DataLayout &DL,
     131             :                                               const Instruction *CtxI,
     132             :                                               const DominatorTree *DT) {
     133             :   // When dereferenceability information is provided by a dereferenceable
     134             :   // attribute, we know exactly how many bytes are dereferenceable. If we can
     135             :   // determine the exact offset to the attributed variable, we can use that
     136             :   // information here.
     137      360669 :   Type *VTy = V->getType();
     138      360669 :   Type *Ty = VTy->getPointerElementType();
     139             : 
     140             :   // Require ABI alignment for loads without alignment specification
     141      360669 :   if (Align == 0)
     142         396 :     Align = DL.getABITypeAlignment(Ty);
     143             : 
     144      360669 :   if (!Ty->isSized())
     145             :     return false;
     146             : 
     147      360666 :   SmallPtrSet<const Value *, 32> Visited;
     148             :   return ::isDereferenceableAndAlignedPointer(
     149     1081998 :       V, Align, APInt(DL.getTypeSizeInBits(VTy), DL.getTypeStoreSize(Ty)), DL,
     150      360666 :       CtxI, DT, Visited);
     151             : }
     152             : 
     153      276405 : bool llvm::isDereferenceablePointer(const Value *V, const DataLayout &DL,
     154             :                                     const Instruction *CtxI,
     155             :                                     const DominatorTree *DT) {
     156      276405 :   return isDereferenceableAndAlignedPointer(V, 1, DL, CtxI, DT);
     157             : }
     158             : 
     159             : /// \brief Test if A and B will obviously have the same value.
     160             : ///
     161             : /// This includes recognizing that %t0 and %t1 will have the same
     162             : /// value in code like this:
     163             : /// \code
     164             : ///   %t0 = getelementptr \@a, 0, 3
     165             : ///   store i32 0, i32* %t0
     166             : ///   %t1 = getelementptr \@a, 0, 3
     167             : ///   %t2 = load i32* %t1
     168             : /// \endcode
     169             : ///
     170     6091436 : static bool AreEquivalentAddressValues(const Value *A, const Value *B) {
     171             :   // Test if the values are trivially equivalent.
     172     6091436 :   if (A == B)
     173             :     return true;
     174             : 
     175             :   // Test if the values come from identical arithmetic instructions.
     176             :   // Use isIdenticalToWhenDefined instead of isIdenticalTo because
     177             :   // this function is only used when one address use dominates the
     178             :   // other, which means that they'll always either have the same
     179             :   // value or one of them will have an undefined value.
     180    18266085 :   if (isa<BinaryOperator>(A) || isa<CastInst>(A) || isa<PHINode>(A) ||
     181     6046569 :       isa<GetElementPtrInst>(A))
     182      175095 :     if (const Instruction *BI = dyn_cast<Instruction>(B))
     183      350190 :       if (cast<Instruction>(A)->isIdenticalToWhenDefined(BI))
     184             :         return true;
     185             : 
     186             :   // Otherwise they may not be equivalent.
     187             :   return false;
     188             : }
     189             : 
     190             : /// \brief Check if executing a load of this pointer value cannot trap.
     191             : ///
     192             : /// If DT and ScanFrom are specified this method performs context-sensitive
     193             : /// analysis and returns true if it is safe to load immediately before ScanFrom.
     194             : ///
     195             : /// If it is not obviously safe to load from the specified pointer, we do
     196             : /// a quick local scan of the basic block containing \c ScanFrom, to determine
     197             : /// if the address is already accessed.
     198             : ///
     199             : /// This uses the pointee type to determine how many bytes need to be safe to
     200             : /// load from the pointer.
     201        1660 : bool llvm::isSafeToLoadUnconditionally(Value *V, unsigned Align,
     202             :                                        const DataLayout &DL,
     203             :                                        Instruction *ScanFrom,
     204             :                                        const DominatorTree *DT) {
     205             :   // Zero alignment means that the load has the ABI alignment for the target
     206        1660 :   if (Align == 0)
     207         326 :     Align = DL.getABITypeAlignment(V->getType()->getPointerElementType());
     208             :   assert(isPowerOf2_32(Align));
     209             : 
     210             :   // If DT is not specified we can't make context-sensitive query
     211        1660 :   const Instruction* CtxI = DT ? ScanFrom : nullptr;
     212        1660 :   if (isDereferenceableAndAlignedPointer(V, Align, DL, CtxI, DT))
     213             :     return true;
     214             : 
     215        1316 :   int64_t ByteOffset = 0;
     216        1316 :   Value *Base = V;
     217        1316 :   Base = GetPointerBaseWithConstantOffset(V, ByteOffset, DL);
     218             : 
     219        1316 :   if (ByteOffset < 0) // out of bounds
     220             :     return false;
     221             : 
     222        1316 :   Type *BaseType = nullptr;
     223        1316 :   unsigned BaseAlign = 0;
     224           2 :   if (const AllocaInst *AI = dyn_cast<AllocaInst>(Base)) {
     225             :     // An alloca is safe to load from as load as it is suitably aligned.
     226           2 :     BaseType = AI->getAllocatedType();
     227           2 :     BaseAlign = AI->getAlignment();
     228           2 :   } else if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(Base)) {
     229             :     // Global variables are not necessarily safe to load from if they are
     230             :     // interposed arbitrarily. Their size may change or they may be weak and
     231             :     // require a test to determine if they were in fact provided.
     232           3 :     if (!GV->isInterposable()) {
     233           2 :       BaseType = GV->getType()->getElementType();
     234           2 :       BaseAlign = GV->getAlignment();
     235             :     }
     236             :   }
     237             : 
     238        2632 :   PointerType *AddrTy = cast<PointerType>(V->getType());
     239        2632 :   uint64_t LoadSize = DL.getTypeStoreSize(AddrTy->getElementType());
     240             : 
     241             :   // If we found a base allocated type from either an alloca or global variable,
     242             :   // try to see if we are definitively within the allocated region. We need to
     243             :   // know the size of the base type and the loaded type to do anything in this
     244             :   // case.
     245        1316 :   if (BaseType && BaseType->isSized()) {
     246           3 :     if (BaseAlign == 0)
     247           0 :       BaseAlign = DL.getPrefTypeAlignment(BaseType);
     248             : 
     249           3 :     if (Align <= BaseAlign) {
     250             :       // Check if the load is within the bounds of the underlying object.
     251           0 :       if (ByteOffset + LoadSize <= DL.getTypeAllocSize(BaseType) &&
     252           0 :           ((ByteOffset % Align) == 0))
     253             :         return true;
     254             :     }
     255             :   }
     256             : 
     257        1316 :   if (!ScanFrom)
     258             :     return false;
     259             : 
     260             :   // Otherwise, be a little bit aggressive by scanning the local block where we
     261             :   // want to check to see if the pointer is already being loaded or stored
     262             :   // from/to.  If so, the previous load or store would have already trapped,
     263             :   // so there is no harm doing an extra load (also, CSE will later eliminate
     264             :   // the load entirely).
     265          56 :   BasicBlock::iterator BBI = ScanFrom->getIterator(),
     266          56 :                        E = ScanFrom->getParent()->begin();
     267             : 
     268             :   // We can at least always strip pointer casts even though we can't use the
     269             :   // base here.
     270          28 :   V = V->stripPointerCasts();
     271             : 
     272          93 :   while (BBI != E) {
     273          81 :     --BBI;
     274             : 
     275             :     // If we see a free or a call which may write to memory (i.e. which might do
     276             :     // a free) the pointer could be marked invalid.
     277          93 :     if (isa<CallInst>(BBI) && BBI->mayWriteToMemory() &&
     278           4 :         !isa<DbgInfoIntrinsic>(BBI))
     279             :       return false;
     280             : 
     281             :     Value *AccessedPtr;
     282             :     unsigned AccessedAlign;
     283           6 :     if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) {
     284           6 :       AccessedPtr = LI->getPointerOperand();
     285           6 :       AccessedAlign = LI->getAlignment();
     286          71 :     } else if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) {
     287          28 :       AccessedPtr = SI->getPointerOperand();
     288          28 :       AccessedAlign = SI->getAlignment();
     289             :     } else
     290          43 :       continue;
     291             : 
     292          68 :     Type *AccessedTy = AccessedPtr->getType()->getPointerElementType();
     293          34 :     if (AccessedAlign == 0)
     294           9 :       AccessedAlign = DL.getABITypeAlignment(AccessedTy);
     295          34 :     if (AccessedAlign < Align)
     296           3 :       continue;
     297             : 
     298             :     // Handle trivial cases.
     299          31 :     if (AccessedPtr == V)
     300             :       return true;
     301             : 
     302          21 :     if (AreEquivalentAddressValues(AccessedPtr->stripPointerCasts(), V) &&
     303           1 :         LoadSize <= DL.getTypeStoreSize(AccessedTy))
     304             :       return true;
     305             :   }
     306             :   return false;
     307             : }
     308             : 
     309             : /// DefMaxInstsToScan - the default number of maximum instructions
     310             : /// to scan in the block, used by FindAvailableLoadedValue().
     311             : /// FindAvailableLoadedValue() was introduced in r60148, to improve jump
     312             : /// threading in part by eliminating partially redundant loads.
     313             : /// At that point, the value of MaxInstsToScan was already set to '6'
     314             : /// without documented explanation.
     315             : cl::opt<unsigned>
     316      289224 : llvm::DefMaxInstsToScan("available-load-scan-limit", cl::init(6), cl::Hidden,
     317      216918 :   cl::desc("Use this to specify the default maximum number of instructions "
     318             :            "to scan backward from a given instruction, when searching for "
     319      216918 :            "available loaded value"));
     320             : 
     321     3474438 : Value *llvm::FindAvailableLoadedValue(LoadInst *Load,
     322             :                                       BasicBlock *ScanBB,
     323             :                                       BasicBlock::iterator &ScanFrom,
     324             :                                       unsigned MaxInstsToScan,
     325             :                                       AliasAnalysis *AA, bool *IsLoad,
     326             :                                       unsigned *NumScanedInst) {
     327             :   // Don't CSE load that is volatile or anything stronger than unordered.
     328     3435966 :   if (!Load->isUnordered())
     329             :     return nullptr;
     330             : 
     331     6871932 :   return FindAvailablePtrLoadStore(
     332     3435966 :       Load->getPointerOperand(), Load->getType(), Load->isAtomic(), ScanBB,
     333     3435966 :       ScanFrom, MaxInstsToScan, AA, IsLoad, NumScanedInst);
     334             : }
     335             : 
     336     3438283 : Value *llvm::FindAvailablePtrLoadStore(Value *Ptr, Type *AccessTy,
     337             :                                        bool AtLeastAtomic, BasicBlock *ScanBB,
     338             :                                        BasicBlock::iterator &ScanFrom,
     339             :                                        unsigned MaxInstsToScan,
     340             :                                        AliasAnalysis *AA, bool *IsLoadCSE,
     341             :                                        unsigned *NumScanedInst) {
     342     3438283 :   if (MaxInstsToScan == 0)
     343           0 :     MaxInstsToScan = ~0U;
     344             : 
     345     3438283 :   const DataLayout &DL = ScanBB->getModule()->getDataLayout();
     346             : 
     347             :   // Try to get the store size for the type.
     348     3438283 :   uint64_t AccessSize = DL.getTypeStoreSize(AccessTy);
     349             : 
     350     3438283 :   Value *StrippedPtr = Ptr->stripPointerCasts();
     351             : 
     352    29569838 :   while (ScanFrom != ScanBB->begin()) {
     353             :     // We must ignore debug info directives when counting (otherwise they
     354             :     // would affect codegen).
     355    26964284 :     Instruction *Inst = &*--ScanFrom;
     356    13714473 :     if (isa<DbgInfoIntrinsic>(Inst))
     357      232331 :       continue;
     358             : 
     359             :     // Restore ScanFrom to expected value in case next test succeeds
     360    26499622 :     ScanFrom++;
     361             : 
     362    13249811 :     if (NumScanedInst)
     363        8173 :       ++(*NumScanedInst);
     364             : 
     365             :     // Don't scan huge blocks.
     366    13249811 :     if (MaxInstsToScan-- == 0)
     367             :       return nullptr;
     368             : 
     369    12025262 :     --ScanFrom;
     370             :     // If this is a load of Ptr, the loaded value is available.
     371             :     // (This is true even if the load is volatile or atomic, although
     372             :     // those cases are unlikely.)
     373    14726190 :     if (LoadInst *LI = dyn_cast<LoadInst>(Inst))
     374     5401856 :       if (AreEquivalentAddressValues(
     375     8104333 :               LI->getPointerOperand()->stripPointerCasts(), StrippedPtr) &&
     376        1549 :           CastInst::isBitOrNoopPointerCastable(LI->getType(), AccessTy, DL)) {
     377             : 
     378             :         // We can value forward from an atomic to a non-atomic, but not the
     379             :         // other way around.
     380        1545 :         if (LI->isAtomic() < AtLeastAtomic)
     381             :           return nullptr;
     382             : 
     383        1545 :         if (IsLoadCSE)
     384        1545 :             *IsLoadCSE = true;
     385             :         return LI;
     386             :       }
     387             : 
     388    15414205 :     if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
     389     6780976 :       Value *StorePtr = SI->getPointerOperand()->stripPointerCasts();
     390             :       // If this is a store through Ptr, the value is available!
     391             :       // (This is true even if the store is volatile or atomic, although
     392             :       // those cases are unlikely.)
     393     3391557 :       if (AreEquivalentAddressValues(StorePtr, StrippedPtr) &&
     394        1069 :           CastInst::isBitOrNoopPointerCastable(SI->getValueOperand()->getType(),
     395             :                                                AccessTy, DL)) {
     396             : 
     397             :         // We can value forward from an atomic to a non-atomic, but not the
     398             :         // other way around.
     399        1030 :         if (SI->isAtomic() < AtLeastAtomic)
     400             :           return nullptr;
     401             : 
     402        1030 :         if (IsLoadCSE)
     403        1029 :           *IsLoadCSE = false;
     404             :         return SI->getOperand(0);
     405             :       }
     406             : 
     407             :       // If both StrippedPtr and StorePtr reach all the way to an alloca or
     408             :       // global and they are different, ignore the store. This is a trivial form
     409             :       // of alias analysis that is important for reg2mem'd code.
     410    10769486 :       if ((isa<AllocaInst>(StrippedPtr) || isa<GlobalVariable>(StrippedPtr)) &&
     411     4591040 :           (isa<AllocaInst>(StorePtr) || isa<GlobalVariable>(StorePtr)) &&
     412             :           StrippedPtr != StorePtr)
     413      876984 :         continue;
     414             : 
     415             :       // If we have alias analysis and it says the store won't modify the loaded
     416             :       // value, ignore the store.
     417     9808262 :       if (AA && (AA->getModRefInfo(SI, StrippedPtr, AccessSize) & MRI_Mod) == 0)
     418     2270864 :         continue;
     419             : 
     420             :       // Otherwise the store that may or may not alias the pointer, bail out.
     421      241610 :       ++ScanFrom;
     422      241610 :       return nullptr;
     423             :     }
     424             : 
     425             :     // If this is some other instruction that may clobber Ptr, bail out.
     426     8633229 :     if (Inst->mayWriteToMemory()) {
     427             :       // If alias analysis claims that it really won't modify the load,
     428             :       // ignore it.
     429     2304523 :       if (AA &&
     430     1980762 :           (AA->getModRefInfo(Inst, StrippedPtr, AccessSize) & MRI_Mod) == 0)
     431      323685 :         continue;
     432             : 
     433             :       // May modify the pointer, bail out.
     434      666772 :       ++ScanFrom;
     435      666772 :       return nullptr;
     436             :     }
     437             :   }
     438             : 
     439             :   // Got to the start of the block, we didn't find it, but are done for this
     440             :   // block.
     441             :   return nullptr;
     442      216918 : }

Generated by: LCOV version 1.13