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" 24using namespace llvm; 25 26/// \brief Test if A and B will obviously have the same value. 27/// 28/// This includes recognizing that %t0 and %t1 will have the same 29/// value in code like this: 30/// \code 31/// %t0 = getelementptr \@a, 0, 3 32/// store i32 0, i32* %t0 33/// %t1 = getelementptr \@a, 0, 3 34/// %t2 = load i32* %t1 35/// \endcode 36/// 37static bool AreEquivalentAddressValues(const Value *A, const Value *B) { 38 // Test if the values are trivially equivalent. 39 if (A == B) 40 return true; 41 42 // Test if the values come from identical arithmetic instructions. 43 // Use isIdenticalToWhenDefined instead of isIdenticalTo because 44 // this function is only used when one address use dominates the 45 // other, which means that they'll always either have the same 46 // value or one of them will have an undefined value. 47 if (isa<BinaryOperator>(A) || isa<CastInst>(A) || isa<PHINode>(A) || 48 isa<GetElementPtrInst>(A)) 49 if (const Instruction *BI = dyn_cast<Instruction>(B)) 50 if (cast<Instruction>(A)->isIdenticalToWhenDefined(BI)) 51 return true; 52 53 // Otherwise they may not be equivalent. 54 return false; 55} 56 57/// \brief Check if executing a load of this pointer value cannot trap. 58/// 59/// If it is not obviously safe to load from the specified pointer, we do 60/// a quick local scan of the basic block containing \c ScanFrom, to determine 61/// if the address is already accessed. 62/// 63/// This uses the pointee type to determine how many bytes need to be safe to 64/// load from the pointer. 65bool llvm::isSafeToLoadUnconditionally(Value *V, Instruction *ScanFrom, 66 unsigned Align) { 67 const DataLayout &DL = ScanFrom->getModule()->getDataLayout(); 68 int64_t ByteOffset = 0; 69 Value *Base = V; 70 Base = GetPointerBaseWithConstantOffset(V, ByteOffset, DL); 71 72 if (ByteOffset < 0) // out of bounds 73 return false; 74 75 Type *BaseType = nullptr; 76 unsigned BaseAlign = 0; 77 if (const AllocaInst *AI = dyn_cast<AllocaInst>(Base)) { 78 // An alloca is safe to load from as load as it is suitably aligned. 79 BaseType = AI->getAllocatedType(); 80 BaseAlign = AI->getAlignment(); 81 } else if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(Base)) { 82 // Global variables are not necessarily safe to load from if they are 83 // overridden. Their size may change or they may be weak and require a test 84 // to determine if they were in fact provided. 85 if (!GV->mayBeOverridden()) { 86 BaseType = GV->getType()->getElementType(); 87 BaseAlign = GV->getAlignment(); 88 } 89 } 90 91 PointerType *AddrTy = cast<PointerType>(V->getType()); 92 uint64_t LoadSize = DL.getTypeStoreSize(AddrTy->getElementType()); 93 94 // If we found a base allocated type from either an alloca or global variable, 95 // try to see if we are definitively within the allocated region. We need to 96 // know the size of the base type and the loaded type to do anything in this 97 // case. 98 if (BaseType && BaseType->isSized()) { 99 if (BaseAlign == 0) 100 BaseAlign = DL.getPrefTypeAlignment(BaseType); 101 102 if (Align <= BaseAlign) { 103 // Check if the load is within the bounds of the underlying object. 104 if (ByteOffset + LoadSize <= DL.getTypeAllocSize(BaseType) && 105 (Align == 0 || (ByteOffset % Align) == 0)) 106 return true; 107 } 108 } 109 110 // Otherwise, be a little bit aggressive by scanning the local block where we 111 // want to check to see if the pointer is already being loaded or stored 112 // from/to. If so, the previous load or store would have already trapped, 113 // so there is no harm doing an extra load (also, CSE will later eliminate 114 // the load entirely). 115 BasicBlock::iterator BBI = ScanFrom, E = ScanFrom->getParent()->begin(); 116 117 // We can at least always strip pointer casts even though we can't use the 118 // base here. 119 V = V->stripPointerCasts(); 120 121 while (BBI != E) { 122 --BBI; 123 124 // If we see a free or a call which may write to memory (i.e. which might do 125 // a free) the pointer could be marked invalid. 126 if (isa<CallInst>(BBI) && BBI->mayWriteToMemory() && 127 !isa<DbgInfoIntrinsic>(BBI)) 128 return false; 129 130 Value *AccessedPtr; 131 if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) 132 AccessedPtr = LI->getPointerOperand(); 133 else if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) 134 AccessedPtr = SI->getPointerOperand(); 135 else 136 continue; 137 138 // Handle trivial cases. 139 if (AccessedPtr == V) 140 return true; 141 142 auto *AccessedTy = cast<PointerType>(AccessedPtr->getType()); 143 if (AreEquivalentAddressValues(AccessedPtr->stripPointerCasts(), V) && 144 LoadSize <= DL.getTypeStoreSize(AccessedTy->getElementType())) 145 return true; 146 } 147 return false; 148} 149 150/// \brief Scan the ScanBB block backwards to see if we have the value at the 151/// memory address *Ptr locally available within a small number of instructions. 152/// 153/// The scan starts from \c ScanFrom. \c MaxInstsToScan specifies the maximum 154/// instructions to scan in the block. If it is set to \c 0, it will scan the whole 155/// block. 156/// 157/// If the value is available, this function returns it. If not, it returns the 158/// iterator for the last validated instruction that the value would be live 159/// through. If we scanned the entire block and didn't find something that 160/// invalidates \c *Ptr or provides it, \c ScanFrom is left at the last 161/// instruction processed and this returns null. 162/// 163/// You can also optionally specify an alias analysis implementation, which 164/// makes this more precise. 165/// 166/// If \c AATags is non-null and a load or store is found, the AA tags from the 167/// load or store are recorded there. If there are no AA tags or if no access is 168/// found, it is left unmodified. 169Value *llvm::FindAvailableLoadedValue(Value *Ptr, BasicBlock *ScanBB, 170 BasicBlock::iterator &ScanFrom, 171 unsigned MaxInstsToScan, 172 AliasAnalysis *AA, AAMDNodes *AATags) { 173 if (MaxInstsToScan == 0) 174 MaxInstsToScan = ~0U; 175 176 Type *AccessTy = cast<PointerType>(Ptr->getType())->getElementType(); 177 178 const DataLayout &DL = ScanBB->getModule()->getDataLayout(); 179 180 // Try to get the store size for the type. 181 uint64_t AccessSize = DL.getTypeStoreSize(AccessTy); 182 183 Value *StrippedPtr = Ptr->stripPointerCasts(); 184 185 while (ScanFrom != ScanBB->begin()) { 186 // We must ignore debug info directives when counting (otherwise they 187 // would affect codegen). 188 Instruction *Inst = --ScanFrom; 189 if (isa<DbgInfoIntrinsic>(Inst)) 190 continue; 191 192 // Restore ScanFrom to expected value in case next test succeeds 193 ScanFrom++; 194 195 // Don't scan huge blocks. 196 if (MaxInstsToScan-- == 0) 197 return nullptr; 198 199 --ScanFrom; 200 // If this is a load of Ptr, the loaded value is available. 201 // (This is true even if the load is volatile or atomic, although 202 // those cases are unlikely.) 203 if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) 204 if (AreEquivalentAddressValues( 205 LI->getPointerOperand()->stripPointerCasts(), StrippedPtr) && 206 CastInst::isBitOrNoopPointerCastable(LI->getType(), AccessTy, DL)) { 207 if (AATags) 208 LI->getAAMetadata(*AATags); 209 return LI; 210 } 211 212 if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 213 Value *StorePtr = SI->getPointerOperand()->stripPointerCasts(); 214 // If this is a store through Ptr, the value is available! 215 // (This is true even if the store is volatile or atomic, although 216 // those cases are unlikely.) 217 if (AreEquivalentAddressValues(StorePtr, StrippedPtr) && 218 CastInst::isBitOrNoopPointerCastable(SI->getValueOperand()->getType(), 219 AccessTy, DL)) { 220 if (AATags) 221 SI->getAAMetadata(*AATags); 222 return SI->getOperand(0); 223 } 224 225 // If both StrippedPtr and StorePtr reach all the way to an alloca or 226 // global and they are different, ignore the store. This is a trivial form 227 // of alias analysis that is important for reg2mem'd code. 228 if ((isa<AllocaInst>(StrippedPtr) || isa<GlobalVariable>(StrippedPtr)) && 229 (isa<AllocaInst>(StorePtr) || isa<GlobalVariable>(StorePtr)) && 230 StrippedPtr != StorePtr) 231 continue; 232 233 // If we have alias analysis and it says the store won't modify the loaded 234 // value, ignore the store. 235 if (AA && 236 (AA->getModRefInfo(SI, StrippedPtr, AccessSize) & 237 AliasAnalysis::Mod) == 0) 238 continue; 239 240 // Otherwise the store that may or may not alias the pointer, bail out. 241 ++ScanFrom; 242 return nullptr; 243 } 244 245 // If this is some other instruction that may clobber Ptr, bail out. 246 if (Inst->mayWriteToMemory()) { 247 // If alias analysis claims that it really won't modify the load, 248 // ignore it. 249 if (AA && 250 (AA->getModRefInfo(Inst, StrippedPtr, AccessSize) & 251 AliasAnalysis::Mod) == 0) 252 continue; 253 254 // May modify the pointer, bail out. 255 ++ScanFrom; 256 return nullptr; 257 } 258 } 259 260 // Got to the start of the block, we didn't find it, but are done for this 261 // block. 262 return nullptr; 263} 264