LCOV - code coverage report
Current view: top level - lib/Analysis - Loads.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 115 118 97.5 %
Date: 2018-05-20 00:06:23 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      296702 : static bool isAligned(const Value *Base, const APInt &Offset, unsigned Align,
      29             :                       const DataLayout &DL) {
      30      296702 :   APInt BaseAlign(Offset.getBitWidth(), Base->getPointerAlignment(DL));
      31             : 
      32      296702 :   if (!BaseAlign) {
      33        3934 :     Type *Ty = Base->getType()->getPointerElementType();
      34        3934 :     if (!Ty->isSized())
      35             :       return false;
      36        3932 :     BaseAlign = DL.getABITypeAlignment(Ty);
      37             :   }
      38             : 
      39      296700 :   APInt Alignment(Offset.getBitWidth(), Align);
      40             : 
      41             :   assert(Alignment.isPowerOf2() && "must be a power of 2!");
      42     1483436 :   return BaseAlign.uge(Alignment) && !(Offset & (Alignment-1));
      43             : }
      44             : 
      45      296702 : static bool isAligned(const Value *Base, unsigned Align, const DataLayout &DL) {
      46      296702 :   Type *Ty = Base->getType();
      47             :   assert(Ty->isSized() && "must be sized");
      48      296702 :   APInt Offset(DL.getTypeStoreSizeInBits(Ty), 0);
      49      593404 :   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      758283 : 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      758283 :   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             :   if (const BitCastOperator *BC = dyn_cast<BitCastOperator>(V))
      67      114512 :     return isDereferenceableAndAlignedPointer(BC->getOperand(0), Align, Size,
      68      114512 :                                               DL, CtxI, DT, Visited);
      69             : 
      70      643769 :   bool CheckForNonNull = false;
      71             :   APInt KnownDerefBytes(Size.getBitWidth(),
      72      643769 :                         V->getPointerDereferenceableBytes(DL, CheckForNonNull));
      73      643769 :   if (KnownDerefBytes.getBoolValue()) {
      74      296837 :     if (KnownDerefBytes.uge(Size))
      75      296710 :       if (!CheckForNonNull || isKnownNonZero(V, DL, 0, nullptr, CtxI, DT))
      76      296702 :         return isAligned(V, Align, DL);
      77             :   }
      78             : 
      79             :   // For GEPs, determine if the indexing lands within the allocated object.
      80             :   if (const GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
      81             :     const Value *Base = GEP->getPointerOperand();
      82             : 
      83      255845 :     APInt Offset(DL.getIndexTypeSizeInBits(GEP->getType()), 0);
      84      937923 :     if (!GEP->accumulateConstantOffset(DL, Offset) || Offset.isNegative() ||
      85     1191289 :         !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      635574 :         Base, Align, Offset + Size.sextOrTrunc(Offset.getBitWidth()),
      98      211858 :         DL, CtxI, DT, Visited);
      99             :   }
     100             : 
     101             :   // For gc.relocate, look through relocations
     102             :   if (const GCRelocateInst *RelocateInst = dyn_cast<GCRelocateInst>(V))
     103             :     return isDereferenceableAndAlignedPointer(
     104           5 :         RelocateInst->getDerivedPtr(), Align, Size, DL, CtxI, DT, Visited);
     105             : 
     106             :   if (const AddrSpaceCastInst *ASC = dyn_cast<AddrSpaceCastInst>(V))
     107             :     return isDereferenceableAndAlignedPointer(ASC->getOperand(0), Align, Size,
     108         146 :                                               DL, CtxI, DT, Visited);
     109             : 
     110       91071 :   if (auto CS = ImmutableCallSite(V))
     111         877 :     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       91067 :   return false;
     117             : }
     118             : 
     119        2648 : 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             :   SmallPtrSet<const Value *, 32> Visited;
     125             :   return ::isDereferenceableAndAlignedPointer(V, Align, Size, DL, CtxI, DT,
     126        5296 :                                               Visited);
     127             : }
     128             : 
     129      429113 : 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      429113 :   Type *VTy = V->getType();
     138      429113 :   Type *Ty = VTy->getPointerElementType();
     139             : 
     140             :   // Require ABI alignment for loads without alignment specification
     141      429113 :   if (Align == 0)
     142         427 :     Align = DL.getABITypeAlignment(Ty);
     143             : 
     144      429113 :   if (!Ty->isSized())
     145             :     return false;
     146             : 
     147             :   SmallPtrSet<const Value *, 32> Visited;
     148             :   return ::isDereferenceableAndAlignedPointer(
     149      858220 :       V, Align, APInt(DL.getIndexTypeSizeInBits(VTy), DL.getTypeStoreSize(Ty)), DL,
     150      429110 :       CtxI, DT, Visited);
     151             : }
     152             : 
     153      328221 : bool llvm::isDereferenceablePointer(const Value *V, const DataLayout &DL,
     154             :                                     const Instruction *CtxI,
     155             :                                     const DominatorTree *DT) {
     156      328221 :   return isDereferenceableAndAlignedPointer(V, 1, DL, CtxI, DT);
     157             : }
     158             : 
     159             : /// 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     6500408 : static bool AreEquivalentAddressValues(const Value *A, const Value *B) {
     171             :   // Test if the values are trivially equivalent.
     172     6500408 :   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             :   if (isa<BinaryOperator>(A) || isa<CastInst>(A) || isa<PHINode>(A) ||
     181             :       isa<GetElementPtrInst>(A))
     182             :     if (const Instruction *BI = dyn_cast<Instruction>(B))
     183      190426 :       if (cast<Instruction>(A)->isIdenticalToWhenDefined(BI))
     184             :         return true;
     185             : 
     186             :   // Otherwise they may not be equivalent.
     187             :   return false;
     188             : }
     189             : 
     190             : /// 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        1666 : 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        1666 :   if (Align == 0)
     207         342 :     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        1666 :   const Instruction* CtxI = DT ? ScanFrom : nullptr;
     212        1666 :   if (isDereferenceableAndAlignedPointer(V, Align, DL, CtxI, DT))
     213             :     return true;
     214             : 
     215        1320 :   int64_t ByteOffset = 0;
     216             :   Value *Base = V;
     217        1320 :   Base = GetPointerBaseWithConstantOffset(V, ByteOffset, DL);
     218             : 
     219        1320 :   if (ByteOffset < 0) // out of bounds
     220             :     return false;
     221             : 
     222             :   Type *BaseType = nullptr;
     223             :   unsigned BaseAlign = 0;
     224             :   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             :     BaseAlign = AI->getAlignment();
     228             :   } 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             :     if (!GV->isInterposable()) {
     233           1 :       BaseType = GV->getType()->getElementType();
     234             :       BaseAlign = GV->getAlignment();
     235             :     }
     236             :   }
     237             : 
     238        1320 :   PointerType *AddrTy = cast<PointerType>(V->getType());
     239        1320 :   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        1320 :   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        1320 :   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          32 :   BasicBlock::iterator BBI = ScanFrom->getIterator(),
     266          32 :                        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             :   V = V->stripPointerCasts();
     271             : 
     272         103 :   while (BBI != E) {
     273             :     --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          95 :     if (isa<CallInst>(BBI) && BBI->mayWriteToMemory() &&
     278             :         !isa<DbgInfoIntrinsic>(BBI))
     279             :       return false;
     280             : 
     281             :     Value *AccessedPtr;
     282             :     unsigned AccessedAlign;
     283             :     if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) {
     284             :       AccessedPtr = LI->getPointerOperand();
     285             :       AccessedAlign = LI->getAlignment();
     286          47 :     } else if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) {
     287             :       AccessedPtr = SI->getPointerOperand();
     288             :       AccessedAlign = SI->getAlignment();
     289             :     } else
     290          47 :       continue;
     291             : 
     292          40 :     Type *AccessedTy = AccessedPtr->getType()->getPointerElementType();
     293          40 :     if (AccessedAlign == 0)
     294           9 :       AccessedAlign = DL.getABITypeAlignment(AccessedTy);
     295          40 :     if (AccessedAlign < Align)
     296           3 :       continue;
     297             : 
     298             :     // Handle trivial cases.
     299          37 :     if (AccessedPtr == V)
     300             :       return true;
     301             : 
     302          23 :     if (AreEquivalentAddressValues(AccessedPtr->stripPointerCasts(), V) &&
     303             :         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      297711 : llvm::DefMaxInstsToScan("available-load-scan-limit", cl::init(6), cl::Hidden,
     317       99237 :   cl::desc("Use this to specify the default maximum number of instructions "
     318             :            "to scan backward from a given instruction, when searching for "
     319      297711 :            "available loaded value"));
     320             : 
     321     3669992 : 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             :   if (!Load->isUnordered())
     329             :     return nullptr;
     330             : 
     331     3631642 :   return FindAvailablePtrLoadStore(
     332     3631642 :       Load->getPointerOperand(), Load->getType(), Load->isAtomic(), ScanBB,
     333     3631642 :       ScanFrom, MaxInstsToScan, AA, IsLoad, NumScanedInst);
     334             : }
     335             : 
     336     3634219 : 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     3634219 :   if (MaxInstsToScan == 0)
     343             :     MaxInstsToScan = ~0U;
     344             : 
     345     3634219 :   const DataLayout &DL = ScanBB->getModule()->getDataLayout();
     346             : 
     347             :   // Try to get the store size for the type.
     348             :   uint64_t AccessSize = DL.getTypeStoreSize(AccessTy);
     349             : 
     350             :   Value *StrippedPtr = Ptr->stripPointerCasts();
     351             : 
     352    15751532 :   while (ScanFrom != ScanBB->begin()) {
     353             :     // We must ignore debug info directives when counting (otherwise they
     354             :     // would affect codegen).
     355             :     Instruction *Inst = &*--ScanFrom;
     356      292916 :     if (isa<DbgInfoIntrinsic>(Inst))
     357      292916 :       continue;
     358             : 
     359             :     // Restore ScanFrom to expected value in case next test succeeds
     360             :     ScanFrom++;
     361             : 
     362    14080671 :     if (NumScanedInst)
     363        9715 :       ++(*NumScanedInst);
     364             : 
     365             :     // Don't scan huge blocks.
     366    14080671 :     if (MaxInstsToScan-- == 0)
     367             :       return nullptr;
     368             : 
     369             :     --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             :     if (LoadInst *LI = dyn_cast<LoadInst>(Inst))
     374     2895986 :       if (AreEquivalentAddressValues(
     375     2897533 :               LI->getPointerOperand()->stripPointerCasts(), StrippedPtr) &&
     376        1547 :           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        1543 :         if (LI->isAtomic() < AtLeastAtomic)
     381             :           return nullptr;
     382             : 
     383        1543 :         if (IsLoadCSE)
     384        1543 :             *IsLoadCSE = true;
     385             :         return LI;
     386             :       }
     387             : 
     388             :     if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
     389             :       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     3605825 :       if (AreEquivalentAddressValues(StorePtr, StrippedPtr) &&
     394        1425 :           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        1366 :         if (SI->isAtomic() < AtLeastAtomic)
     400             :           return nullptr;
     401             : 
     402        1366 :         if (IsLoadCSE)
     403        1365 :           *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     4391762 :       if ((isa<AllocaInst>(StrippedPtr) || isa<GlobalVariable>(StrippedPtr)) &&
     411     1609224 :           (isa<AllocaInst>(StorePtr) || isa<GlobalVariable>(StorePtr)) &&
     412             :           StrippedPtr != StorePtr)
     413      931272 :         continue;
     414             : 
     415             :       // If we have alias analysis and it says the store won't modify the loaded
     416             :       // value, ignore the store.
     417     7761990 :       if (AA && !isModSet(AA->getModRefInfo(SI, StrippedPtr, AccessSize)))
     418     2418466 :         continue;
     419             : 
     420             :       // Otherwise the store that may or may not alias the pointer, bail out.
     421             :       ++ScanFrom;
     422      253296 :       return nullptr;
     423             :     }
     424             : 
     425             :     // If this is some other instruction that may clobber Ptr, bail out.
     426     9160866 :     if (Inst->mayWriteToMemory()) {
     427             :       // If alias analysis claims that it really won't modify the load,
     428             :       // ignore it.
     429     2383651 :       if (AA && !isModSet(AA->getModRefInfo(Inst, StrippedPtr, AccessSize)))
     430      337079 :         continue;
     431             : 
     432             :       // May modify the pointer, bail out.
     433             :       ++ScanFrom;
     434      686207 :       return nullptr;
     435             :     }
     436             :   }
     437             : 
     438             :   // Got to the start of the block, we didn't find it, but are done for this
     439             :   // block.
     440             :   return nullptr;
     441      297711 : }

Generated by: LCOV version 1.13