1 #include "llvm/Transforms/Utils/VNCoercion.h"
2 #include "llvm/Analysis/AliasAnalysis.h"
3 #include "llvm/Analysis/ConstantFolding.h"
4 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
5 #include "llvm/Analysis/ValueTracking.h"
6 #include "llvm/IR/IRBuilder.h"
7 #include "llvm/IR/IntrinsicInst.h"
8 #include "llvm/Support/Debug.h"
10 #define DEBUG_TYPE "vncoerce"
12 namespace VNCoercion {
14 /// Return true if coerceAvailableValueToLoadType will succeed.
15 bool canCoerceMustAliasedValueToLoad(Value *StoredVal, Type *LoadTy,
16 const DataLayout &DL) {
17 // If the loaded or stored value is an first class array or struct, don't try
18 // to transform them. We need to be able to bitcast to integer.
19 if (LoadTy->isStructTy() || LoadTy->isArrayTy() ||
20 StoredVal->getType()->isStructTy() || StoredVal->getType()->isArrayTy())
23 // The store has to be at least as big as the load.
24 if (DL.getTypeSizeInBits(StoredVal->getType()) < DL.getTypeSizeInBits(LoadTy))
27 // Don't coerce non-integral pointers to integers or vice versa.
28 if (DL.isNonIntegralPointerType(StoredVal->getType()) !=
29 DL.isNonIntegralPointerType(LoadTy))
35 template <class T, class HelperClass>
36 static T *coerceAvailableValueToLoadTypeHelper(T *StoredVal, Type *LoadedTy,
38 const DataLayout &DL) {
39 assert(canCoerceMustAliasedValueToLoad(StoredVal, LoadedTy, DL) &&
40 "precondition violation - materialization can't fail");
41 if (auto *C = dyn_cast<Constant>(StoredVal))
42 if (auto *FoldedStoredVal = ConstantFoldConstant(C, DL))
43 StoredVal = FoldedStoredVal;
45 // If this is already the right type, just return it.
46 Type *StoredValTy = StoredVal->getType();
48 uint64_t StoredValSize = DL.getTypeSizeInBits(StoredValTy);
49 uint64_t LoadedValSize = DL.getTypeSizeInBits(LoadedTy);
51 // If the store and reload are the same size, we can always reuse it.
52 if (StoredValSize == LoadedValSize) {
53 // Pointer to Pointer -> use bitcast.
54 if (StoredValTy->isPtrOrPtrVectorTy() && LoadedTy->isPtrOrPtrVectorTy()) {
55 StoredVal = Helper.CreateBitCast(StoredVal, LoadedTy);
57 // Convert source pointers to integers, which can be bitcast.
58 if (StoredValTy->isPtrOrPtrVectorTy()) {
59 StoredValTy = DL.getIntPtrType(StoredValTy);
60 StoredVal = Helper.CreatePtrToInt(StoredVal, StoredValTy);
63 Type *TypeToCastTo = LoadedTy;
64 if (TypeToCastTo->isPtrOrPtrVectorTy())
65 TypeToCastTo = DL.getIntPtrType(TypeToCastTo);
67 if (StoredValTy != TypeToCastTo)
68 StoredVal = Helper.CreateBitCast(StoredVal, TypeToCastTo);
70 // Cast to pointer if the load needs a pointer type.
71 if (LoadedTy->isPtrOrPtrVectorTy())
72 StoredVal = Helper.CreateIntToPtr(StoredVal, LoadedTy);
75 if (auto *C = dyn_cast<ConstantExpr>(StoredVal))
76 if (auto *FoldedStoredVal = ConstantFoldConstant(C, DL))
77 StoredVal = FoldedStoredVal;
81 // If the loaded value is smaller than the available value, then we can
82 // extract out a piece from it. If the available value is too small, then we
84 assert(StoredValSize >= LoadedValSize &&
85 "canCoerceMustAliasedValueToLoad fail");
87 // Convert source pointers to integers, which can be manipulated.
88 if (StoredValTy->isPtrOrPtrVectorTy()) {
89 StoredValTy = DL.getIntPtrType(StoredValTy);
90 StoredVal = Helper.CreatePtrToInt(StoredVal, StoredValTy);
93 // Convert vectors and fp to integer, which can be manipulated.
94 if (!StoredValTy->isIntegerTy()) {
95 StoredValTy = IntegerType::get(StoredValTy->getContext(), StoredValSize);
96 StoredVal = Helper.CreateBitCast(StoredVal, StoredValTy);
99 // If this is a big-endian system, we need to shift the value down to the low
100 // bits so that a truncate will work.
101 if (DL.isBigEndian()) {
102 uint64_t ShiftAmt = DL.getTypeStoreSizeInBits(StoredValTy) -
103 DL.getTypeStoreSizeInBits(LoadedTy);
104 StoredVal = Helper.CreateLShr(
105 StoredVal, ConstantInt::get(StoredVal->getType(), ShiftAmt));
108 // Truncate the integer to the right size now.
109 Type *NewIntTy = IntegerType::get(StoredValTy->getContext(), LoadedValSize);
110 StoredVal = Helper.CreateTruncOrBitCast(StoredVal, NewIntTy);
112 if (LoadedTy != NewIntTy) {
113 // If the result is a pointer, inttoptr.
114 if (LoadedTy->isPtrOrPtrVectorTy())
115 StoredVal = Helper.CreateIntToPtr(StoredVal, LoadedTy);
117 // Otherwise, bitcast.
118 StoredVal = Helper.CreateBitCast(StoredVal, LoadedTy);
121 if (auto *C = dyn_cast<Constant>(StoredVal))
122 if (auto *FoldedStoredVal = ConstantFoldConstant(C, DL))
123 StoredVal = FoldedStoredVal;
128 /// If we saw a store of a value to memory, and
129 /// then a load from a must-aliased pointer of a different type, try to coerce
130 /// the stored value. LoadedTy is the type of the load we want to replace.
131 /// IRB is IRBuilder used to insert new instructions.
133 /// If we can't do it, return null.
134 Value *coerceAvailableValueToLoadType(Value *StoredVal, Type *LoadedTy,
135 IRBuilder<> &IRB, const DataLayout &DL) {
136 return coerceAvailableValueToLoadTypeHelper(StoredVal, LoadedTy, IRB, DL);
139 /// This function is called when we have a memdep query of a load that ends up
140 /// being a clobbering memory write (store, memset, memcpy, memmove). This
141 /// means that the write *may* provide bits used by the load but we can't be
142 /// sure because the pointers don't must-alias.
144 /// Check this case to see if there is anything more we can do before we give
145 /// up. This returns -1 if we have to give up, or a byte number in the stored
146 /// value of the piece that feeds the load.
147 static int analyzeLoadFromClobberingWrite(Type *LoadTy, Value *LoadPtr,
149 uint64_t WriteSizeInBits,
150 const DataLayout &DL) {
151 // If the loaded or stored value is a first class array or struct, don't try
152 // to transform them. We need to be able to bitcast to integer.
153 if (LoadTy->isStructTy() || LoadTy->isArrayTy())
156 int64_t StoreOffset = 0, LoadOffset = 0;
158 GetPointerBaseWithConstantOffset(WritePtr, StoreOffset, DL);
159 Value *LoadBase = GetPointerBaseWithConstantOffset(LoadPtr, LoadOffset, DL);
160 if (StoreBase != LoadBase)
163 // If the load and store are to the exact same address, they should have been
164 // a must alias. AA must have gotten confused.
165 // FIXME: Study to see if/when this happens. One case is forwarding a memset
166 // to a load from the base of the memset.
168 // If the load and store don't overlap at all, the store doesn't provide
169 // anything to the load. In this case, they really don't alias at all, AA
170 // must have gotten confused.
171 uint64_t LoadSize = DL.getTypeSizeInBits(LoadTy);
173 if ((WriteSizeInBits & 7) | (LoadSize & 7))
175 uint64_t StoreSize = WriteSizeInBits / 8; // Convert to bytes.
178 bool isAAFailure = false;
179 if (StoreOffset < LoadOffset)
180 isAAFailure = StoreOffset + int64_t(StoreSize) <= LoadOffset;
182 isAAFailure = LoadOffset + int64_t(LoadSize) <= StoreOffset;
187 // If the Load isn't completely contained within the stored bits, we don't
188 // have all the bits to feed it. We could do something crazy in the future
189 // (issue a smaller load then merge the bits in) but this seems unlikely to be
191 if (StoreOffset > LoadOffset ||
192 StoreOffset + StoreSize < LoadOffset + LoadSize)
195 // Okay, we can do this transformation. Return the number of bytes into the
196 // store that the load is.
197 return LoadOffset - StoreOffset;
200 /// This function is called when we have a
201 /// memdep query of a load that ends up being a clobbering store.
202 int analyzeLoadFromClobberingStore(Type *LoadTy, Value *LoadPtr,
203 StoreInst *DepSI, const DataLayout &DL) {
204 // Cannot handle reading from store of first-class aggregate yet.
205 if (DepSI->getValueOperand()->getType()->isStructTy() ||
206 DepSI->getValueOperand()->getType()->isArrayTy())
209 Value *StorePtr = DepSI->getPointerOperand();
211 DL.getTypeSizeInBits(DepSI->getValueOperand()->getType());
212 return analyzeLoadFromClobberingWrite(LoadTy, LoadPtr, StorePtr, StoreSize,
216 /// This function is called when we have a
217 /// memdep query of a load that ends up being clobbered by another load. See if
218 /// the other load can feed into the second load.
219 int analyzeLoadFromClobberingLoad(Type *LoadTy, Value *LoadPtr, LoadInst *DepLI,
220 const DataLayout &DL) {
221 // Cannot handle reading from store of first-class aggregate yet.
222 if (DepLI->getType()->isStructTy() || DepLI->getType()->isArrayTy())
225 Value *DepPtr = DepLI->getPointerOperand();
226 uint64_t DepSize = DL.getTypeSizeInBits(DepLI->getType());
227 int R = analyzeLoadFromClobberingWrite(LoadTy, LoadPtr, DepPtr, DepSize, DL);
231 // If we have a load/load clobber an DepLI can be widened to cover this load,
232 // then we should widen it!
233 int64_t LoadOffs = 0;
234 const Value *LoadBase =
235 GetPointerBaseWithConstantOffset(LoadPtr, LoadOffs, DL);
236 unsigned LoadSize = DL.getTypeStoreSize(LoadTy);
238 unsigned Size = MemoryDependenceResults::getLoadLoadClobberFullWidthSize(
239 LoadBase, LoadOffs, LoadSize, DepLI);
243 // Check non-obvious conditions enforced by MDA which we rely on for being
244 // able to materialize this potentially available value
245 assert(DepLI->isSimple() && "Cannot widen volatile/atomic load!");
246 assert(DepLI->getType()->isIntegerTy() && "Can't widen non-integer load");
248 return analyzeLoadFromClobberingWrite(LoadTy, LoadPtr, DepPtr, Size * 8, DL);
251 int analyzeLoadFromClobberingMemInst(Type *LoadTy, Value *LoadPtr,
252 MemIntrinsic *MI, const DataLayout &DL) {
253 // If the mem operation is a non-constant size, we can't handle it.
254 ConstantInt *SizeCst = dyn_cast<ConstantInt>(MI->getLength());
257 uint64_t MemSizeInBits = SizeCst->getZExtValue() * 8;
259 // If this is memset, we just need to see if the offset is valid in the size
261 if (MI->getIntrinsicID() == Intrinsic::memset)
262 return analyzeLoadFromClobberingWrite(LoadTy, LoadPtr, MI->getDest(),
265 // If we have a memcpy/memmove, the only case we can handle is if this is a
266 // copy from constant memory. In that case, we can read directly from the
268 MemTransferInst *MTI = cast<MemTransferInst>(MI);
270 Constant *Src = dyn_cast<Constant>(MTI->getSource());
274 GlobalVariable *GV = dyn_cast<GlobalVariable>(GetUnderlyingObject(Src, DL));
275 if (!GV || !GV->isConstant())
278 // See if the access is within the bounds of the transfer.
279 int Offset = analyzeLoadFromClobberingWrite(LoadTy, LoadPtr, MI->getDest(),
284 unsigned AS = Src->getType()->getPointerAddressSpace();
285 // Otherwise, see if we can constant fold a load from the constant with the
286 // offset applied as appropriate.
288 ConstantExpr::getBitCast(Src, Type::getInt8PtrTy(Src->getContext(), AS));
289 Constant *OffsetCst =
290 ConstantInt::get(Type::getInt64Ty(Src->getContext()), (unsigned)Offset);
291 Src = ConstantExpr::getGetElementPtr(Type::getInt8Ty(Src->getContext()), Src,
293 Src = ConstantExpr::getBitCast(Src, PointerType::get(LoadTy, AS));
294 if (ConstantFoldLoadFromConstPtr(Src, LoadTy, DL))
299 template <class T, class HelperClass>
300 static T *getStoreValueForLoadHelper(T *SrcVal, unsigned Offset, Type *LoadTy,
302 const DataLayout &DL) {
303 LLVMContext &Ctx = SrcVal->getType()->getContext();
305 // If two pointers are in the same address space, they have the same size,
306 // so we don't need to do any truncation, etc. This avoids introducing
307 // ptrtoint instructions for pointers that may be non-integral.
308 if (SrcVal->getType()->isPointerTy() && LoadTy->isPointerTy() &&
309 cast<PointerType>(SrcVal->getType())->getAddressSpace() ==
310 cast<PointerType>(LoadTy)->getAddressSpace()) {
314 uint64_t StoreSize = (DL.getTypeSizeInBits(SrcVal->getType()) + 7) / 8;
315 uint64_t LoadSize = (DL.getTypeSizeInBits(LoadTy) + 7) / 8;
316 // Compute which bits of the stored value are being used by the load. Convert
317 // to an integer type to start with.
318 if (SrcVal->getType()->isPtrOrPtrVectorTy())
319 SrcVal = Helper.CreatePtrToInt(SrcVal, DL.getIntPtrType(SrcVal->getType()));
320 if (!SrcVal->getType()->isIntegerTy())
321 SrcVal = Helper.CreateBitCast(SrcVal, IntegerType::get(Ctx, StoreSize * 8));
323 // Shift the bits to the least significant depending on endianness.
325 if (DL.isLittleEndian())
326 ShiftAmt = Offset * 8;
328 ShiftAmt = (StoreSize - LoadSize - Offset) * 8;
330 SrcVal = Helper.CreateLShr(SrcVal,
331 ConstantInt::get(SrcVal->getType(), ShiftAmt));
333 if (LoadSize != StoreSize)
334 SrcVal = Helper.CreateTruncOrBitCast(SrcVal,
335 IntegerType::get(Ctx, LoadSize * 8));
339 /// This function is called when we have a memdep query of a load that ends up
340 /// being a clobbering store. This means that the store provides bits used by
341 /// the load but the pointers don't must-alias. Check this case to see if
342 /// there is anything more we can do before we give up.
343 Value *getStoreValueForLoad(Value *SrcVal, unsigned Offset, Type *LoadTy,
344 Instruction *InsertPt, const DataLayout &DL) {
346 IRBuilder<> Builder(InsertPt);
347 SrcVal = getStoreValueForLoadHelper(SrcVal, Offset, LoadTy, Builder, DL);
348 return coerceAvailableValueToLoadTypeHelper(SrcVal, LoadTy, Builder, DL);
351 Constant *getConstantStoreValueForLoad(Constant *SrcVal, unsigned Offset,
352 Type *LoadTy, const DataLayout &DL) {
354 SrcVal = getStoreValueForLoadHelper(SrcVal, Offset, LoadTy, F, DL);
355 return coerceAvailableValueToLoadTypeHelper(SrcVal, LoadTy, F, DL);
358 /// This function is called when we have a memdep query of a load that ends up
359 /// being a clobbering load. This means that the load *may* provide bits used
360 /// by the load but we can't be sure because the pointers don't must-alias.
361 /// Check this case to see if there is anything more we can do before we give
363 Value *getLoadValueForLoad(LoadInst *SrcVal, unsigned Offset, Type *LoadTy,
364 Instruction *InsertPt, const DataLayout &DL) {
365 // If Offset+LoadTy exceeds the size of SrcVal, then we must be wanting to
366 // widen SrcVal out to a larger load.
367 unsigned SrcValStoreSize = DL.getTypeStoreSize(SrcVal->getType());
368 unsigned LoadSize = DL.getTypeStoreSize(LoadTy);
369 if (Offset + LoadSize > SrcValStoreSize) {
370 assert(SrcVal->isSimple() && "Cannot widen volatile/atomic load!");
371 assert(SrcVal->getType()->isIntegerTy() && "Can't widen non-integer load");
372 // If we have a load/load clobber an DepLI can be widened to cover this
373 // load, then we should widen it to the next power of 2 size big enough!
374 unsigned NewLoadSize = Offset + LoadSize;
375 if (!isPowerOf2_32(NewLoadSize))
376 NewLoadSize = NextPowerOf2(NewLoadSize);
378 Value *PtrVal = SrcVal->getPointerOperand();
379 // Insert the new load after the old load. This ensures that subsequent
380 // memdep queries will find the new load. We can't easily remove the old
381 // load completely because it is already in the value numbering table.
382 IRBuilder<> Builder(SrcVal->getParent(), ++BasicBlock::iterator(SrcVal));
383 Type *DestPTy = IntegerType::get(LoadTy->getContext(), NewLoadSize * 8);
385 PointerType::get(DestPTy, PtrVal->getType()->getPointerAddressSpace());
386 Builder.SetCurrentDebugLocation(SrcVal->getDebugLoc());
387 PtrVal = Builder.CreateBitCast(PtrVal, DestPTy);
388 LoadInst *NewLoad = Builder.CreateLoad(PtrVal);
389 NewLoad->takeName(SrcVal);
390 NewLoad->setAlignment(SrcVal->getAlignment());
392 DEBUG(dbgs() << "GVN WIDENED LOAD: " << *SrcVal << "\n");
393 DEBUG(dbgs() << "TO: " << *NewLoad << "\n");
395 // Replace uses of the original load with the wider load. On a big endian
396 // system, we need to shift down to get the relevant bits.
398 if (DL.isBigEndian())
399 RV = Builder.CreateLShr(RV, (NewLoadSize - SrcValStoreSize) * 8);
400 RV = Builder.CreateTrunc(RV, SrcVal->getType());
401 SrcVal->replaceAllUsesWith(RV);
406 return getStoreValueForLoad(SrcVal, Offset, LoadTy, InsertPt, DL);
409 Constant *getConstantLoadValueForLoad(Constant *SrcVal, unsigned Offset,
410 Type *LoadTy, const DataLayout &DL) {
411 unsigned SrcValStoreSize = DL.getTypeStoreSize(SrcVal->getType());
412 unsigned LoadSize = DL.getTypeStoreSize(LoadTy);
413 if (Offset + LoadSize > SrcValStoreSize)
415 return getConstantStoreValueForLoad(SrcVal, Offset, LoadTy, DL);
418 template <class T, class HelperClass>
419 T *getMemInstValueForLoadHelper(MemIntrinsic *SrcInst, unsigned Offset,
420 Type *LoadTy, HelperClass &Helper,
421 const DataLayout &DL) {
422 LLVMContext &Ctx = LoadTy->getContext();
423 uint64_t LoadSize = DL.getTypeSizeInBits(LoadTy) / 8;
425 // We know that this method is only called when the mem transfer fully
426 // provides the bits for the load.
427 if (MemSetInst *MSI = dyn_cast<MemSetInst>(SrcInst)) {
428 // memset(P, 'x', 1234) -> splat('x'), even if x is a variable, and
429 // independently of what the offset is.
430 T *Val = cast<T>(MSI->getValue());
433 Helper.CreateZExtOrBitCast(Val, IntegerType::get(Ctx, LoadSize * 8));
436 // Splat the value out to the right number of bits.
437 for (unsigned NumBytesSet = 1; NumBytesSet != LoadSize;) {
438 // If we can double the number of bytes set, do it.
439 if (NumBytesSet * 2 <= LoadSize) {
440 T *ShVal = Helper.CreateShl(
441 Val, ConstantInt::get(Val->getType(), NumBytesSet * 8));
442 Val = Helper.CreateOr(Val, ShVal);
447 // Otherwise insert one byte at a time.
448 T *ShVal = Helper.CreateShl(Val, ConstantInt::get(Val->getType(), 1 * 8));
449 Val = Helper.CreateOr(OneElt, ShVal);
453 return coerceAvailableValueToLoadTypeHelper(Val, LoadTy, Helper, DL);
456 // Otherwise, this is a memcpy/memmove from a constant global.
457 MemTransferInst *MTI = cast<MemTransferInst>(SrcInst);
458 Constant *Src = cast<Constant>(MTI->getSource());
459 unsigned AS = Src->getType()->getPointerAddressSpace();
461 // Otherwise, see if we can constant fold a load from the constant with the
462 // offset applied as appropriate.
464 ConstantExpr::getBitCast(Src, Type::getInt8PtrTy(Src->getContext(), AS));
465 Constant *OffsetCst =
466 ConstantInt::get(Type::getInt64Ty(Src->getContext()), (unsigned)Offset);
467 Src = ConstantExpr::getGetElementPtr(Type::getInt8Ty(Src->getContext()), Src,
469 Src = ConstantExpr::getBitCast(Src, PointerType::get(LoadTy, AS));
470 return ConstantFoldLoadFromConstPtr(Src, LoadTy, DL);
473 /// This function is called when we have a
474 /// memdep query of a load that ends up being a clobbering mem intrinsic.
475 Value *getMemInstValueForLoad(MemIntrinsic *SrcInst, unsigned Offset,
476 Type *LoadTy, Instruction *InsertPt,
477 const DataLayout &DL) {
478 IRBuilder<> Builder(InsertPt);
479 return getMemInstValueForLoadHelper<Value, IRBuilder<>>(SrcInst, Offset,
480 LoadTy, Builder, DL);
483 Constant *getConstantMemInstValueForLoad(MemIntrinsic *SrcInst, unsigned Offset,
484 Type *LoadTy, const DataLayout &DL) {
485 // The only case analyzeLoadFromClobberingMemInst cannot be converted to a
486 // constant is when it's a memset of a non-constant.
487 if (auto *MSI = dyn_cast<MemSetInst>(SrcInst))
488 if (!isa<Constant>(MSI->getValue()))
491 return getMemInstValueForLoadHelper<Constant, ConstantFolder>(SrcInst, Offset,
494 } // namespace VNCoercion