blob: 19593054c23a2881be5778748c67caa6f48eeee7 [file] [log] [blame]
Daniel Berlin5ac91792017-03-10 04:54:10 +00001#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"
9
10#define DEBUG_TYPE "vncoerce"
11namespace llvm {
12namespace VNCoercion {
13
14/// Return true if coerceAvailableValueToLoadType will succeed.
15bool 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())
21 return false;
22
Matthew Voss30648ab2018-06-21 21:43:20 +000023 uint64_t StoreSize = DL.getTypeSizeInBits(StoredVal->getType());
24
25 // The store size must be byte-aligned to support future type casts.
26 if (llvm::alignTo(StoreSize, 8) != StoreSize)
27 return false;
28
Daniel Berlin5ac91792017-03-10 04:54:10 +000029 // The store has to be at least as big as the load.
Matthew Voss30648ab2018-06-21 21:43:20 +000030 if (StoreSize < DL.getTypeSizeInBits(LoadTy))
Daniel Berlin5ac91792017-03-10 04:54:10 +000031 return false;
32
Sanjoy Das59454472017-04-19 18:21:09 +000033 // Don't coerce non-integral pointers to integers or vice versa.
Philip Reames322eb762019-02-19 23:19:51 +000034 if (DL.isNonIntegralPointerType(StoredVal->getType()->getScalarType()) !=
35 DL.isNonIntegralPointerType(LoadTy->getScalarType())) {
Philip Reames92756a82019-02-19 23:07:15 +000036 // As a special case, allow coercion of memset used to initialize
37 // an array w/null. Despite non-integral pointers not generally having a
38 // specific bit pattern, we do assume null is zero.
Philip Reames79d5e162019-02-20 00:31:28 +000039 if (auto *CI = dyn_cast<Constant>(StoredVal))
40 return CI->isNullValue();
Sanjoy Das59454472017-04-19 18:21:09 +000041 return false;
Philip Reames92756a82019-02-19 23:07:15 +000042 }
43
Daniel Berlin5ac91792017-03-10 04:54:10 +000044 return true;
45}
46
Daniel Berlin12883b12017-03-20 16:08:29 +000047template <class T, class HelperClass>
48static T *coerceAvailableValueToLoadTypeHelper(T *StoredVal, Type *LoadedTy,
49 HelperClass &Helper,
50 const DataLayout &DL) {
Daniel Berlin5ac91792017-03-10 04:54:10 +000051 assert(canCoerceMustAliasedValueToLoad(StoredVal, LoadedTy, DL) &&
52 "precondition violation - materialization can't fail");
Daniel Berlin5ac91792017-03-10 04:54:10 +000053 if (auto *C = dyn_cast<Constant>(StoredVal))
54 if (auto *FoldedStoredVal = ConstantFoldConstant(C, DL))
55 StoredVal = FoldedStoredVal;
56
57 // If this is already the right type, just return it.
58 Type *StoredValTy = StoredVal->getType();
59
60 uint64_t StoredValSize = DL.getTypeSizeInBits(StoredValTy);
61 uint64_t LoadedValSize = DL.getTypeSizeInBits(LoadedTy);
62
63 // If the store and reload are the same size, we can always reuse it.
64 if (StoredValSize == LoadedValSize) {
65 // Pointer to Pointer -> use bitcast.
Craig Topper95d23472017-07-09 07:04:00 +000066 if (StoredValTy->isPtrOrPtrVectorTy() && LoadedTy->isPtrOrPtrVectorTy()) {
Daniel Berlin12883b12017-03-20 16:08:29 +000067 StoredVal = Helper.CreateBitCast(StoredVal, LoadedTy);
Daniel Berlin5ac91792017-03-10 04:54:10 +000068 } else {
69 // Convert source pointers to integers, which can be bitcast.
Craig Topper95d23472017-07-09 07:04:00 +000070 if (StoredValTy->isPtrOrPtrVectorTy()) {
Daniel Berlin5ac91792017-03-10 04:54:10 +000071 StoredValTy = DL.getIntPtrType(StoredValTy);
Daniel Berlin12883b12017-03-20 16:08:29 +000072 StoredVal = Helper.CreatePtrToInt(StoredVal, StoredValTy);
Daniel Berlin5ac91792017-03-10 04:54:10 +000073 }
74
75 Type *TypeToCastTo = LoadedTy;
Craig Topper95d23472017-07-09 07:04:00 +000076 if (TypeToCastTo->isPtrOrPtrVectorTy())
Daniel Berlin5ac91792017-03-10 04:54:10 +000077 TypeToCastTo = DL.getIntPtrType(TypeToCastTo);
78
79 if (StoredValTy != TypeToCastTo)
Daniel Berlin12883b12017-03-20 16:08:29 +000080 StoredVal = Helper.CreateBitCast(StoredVal, TypeToCastTo);
Daniel Berlin5ac91792017-03-10 04:54:10 +000081
82 // Cast to pointer if the load needs a pointer type.
Craig Topper95d23472017-07-09 07:04:00 +000083 if (LoadedTy->isPtrOrPtrVectorTy())
Daniel Berlin12883b12017-03-20 16:08:29 +000084 StoredVal = Helper.CreateIntToPtr(StoredVal, LoadedTy);
Daniel Berlin5ac91792017-03-10 04:54:10 +000085 }
86
87 if (auto *C = dyn_cast<ConstantExpr>(StoredVal))
88 if (auto *FoldedStoredVal = ConstantFoldConstant(C, DL))
89 StoredVal = FoldedStoredVal;
90
91 return StoredVal;
92 }
Daniel Berlin5ac91792017-03-10 04:54:10 +000093 // If the loaded value is smaller than the available value, then we can
94 // extract out a piece from it. If the available value is too small, then we
95 // can't do anything.
96 assert(StoredValSize >= LoadedValSize &&
97 "canCoerceMustAliasedValueToLoad fail");
98
99 // Convert source pointers to integers, which can be manipulated.
Craig Topper95d23472017-07-09 07:04:00 +0000100 if (StoredValTy->isPtrOrPtrVectorTy()) {
Daniel Berlin5ac91792017-03-10 04:54:10 +0000101 StoredValTy = DL.getIntPtrType(StoredValTy);
Daniel Berlin12883b12017-03-20 16:08:29 +0000102 StoredVal = Helper.CreatePtrToInt(StoredVal, StoredValTy);
Daniel Berlin5ac91792017-03-10 04:54:10 +0000103 }
104
105 // Convert vectors and fp to integer, which can be manipulated.
106 if (!StoredValTy->isIntegerTy()) {
107 StoredValTy = IntegerType::get(StoredValTy->getContext(), StoredValSize);
Daniel Berlin12883b12017-03-20 16:08:29 +0000108 StoredVal = Helper.CreateBitCast(StoredVal, StoredValTy);
Daniel Berlin5ac91792017-03-10 04:54:10 +0000109 }
110
111 // If this is a big-endian system, we need to shift the value down to the low
112 // bits so that a truncate will work.
113 if (DL.isBigEndian()) {
114 uint64_t ShiftAmt = DL.getTypeStoreSizeInBits(StoredValTy) -
115 DL.getTypeStoreSizeInBits(LoadedTy);
Daniel Berlin12883b12017-03-20 16:08:29 +0000116 StoredVal = Helper.CreateLShr(
117 StoredVal, ConstantInt::get(StoredVal->getType(), ShiftAmt));
Daniel Berlin5ac91792017-03-10 04:54:10 +0000118 }
119
120 // Truncate the integer to the right size now.
121 Type *NewIntTy = IntegerType::get(StoredValTy->getContext(), LoadedValSize);
Daniel Berlin12883b12017-03-20 16:08:29 +0000122 StoredVal = Helper.CreateTruncOrBitCast(StoredVal, NewIntTy);
Daniel Berlin5ac91792017-03-10 04:54:10 +0000123
124 if (LoadedTy != NewIntTy) {
125 // If the result is a pointer, inttoptr.
Craig Topper95d23472017-07-09 07:04:00 +0000126 if (LoadedTy->isPtrOrPtrVectorTy())
Daniel Berlin12883b12017-03-20 16:08:29 +0000127 StoredVal = Helper.CreateIntToPtr(StoredVal, LoadedTy);
Daniel Berlin5ac91792017-03-10 04:54:10 +0000128 else
129 // Otherwise, bitcast.
Daniel Berlin12883b12017-03-20 16:08:29 +0000130 StoredVal = Helper.CreateBitCast(StoredVal, LoadedTy);
Daniel Berlin5ac91792017-03-10 04:54:10 +0000131 }
132
133 if (auto *C = dyn_cast<Constant>(StoredVal))
134 if (auto *FoldedStoredVal = ConstantFoldConstant(C, DL))
135 StoredVal = FoldedStoredVal;
136
137 return StoredVal;
138}
139
Daniel Berlin12883b12017-03-20 16:08:29 +0000140/// If we saw a store of a value to memory, and
141/// then a load from a must-aliased pointer of a different type, try to coerce
142/// the stored value. LoadedTy is the type of the load we want to replace.
143/// IRB is IRBuilder used to insert new instructions.
144///
145/// If we can't do it, return null.
146Value *coerceAvailableValueToLoadType(Value *StoredVal, Type *LoadedTy,
147 IRBuilder<> &IRB, const DataLayout &DL) {
148 return coerceAvailableValueToLoadTypeHelper(StoredVal, LoadedTy, IRB, DL);
149}
150
151/// This function is called when we have a memdep query of a load that ends up
152/// being a clobbering memory write (store, memset, memcpy, memmove). This
153/// means that the write *may* provide bits used by the load but we can't be
154/// sure because the pointers don't must-alias.
Daniel Berlin5ac91792017-03-10 04:54:10 +0000155///
156/// Check this case to see if there is anything more we can do before we give
157/// up. This returns -1 if we have to give up, or a byte number in the stored
158/// value of the piece that feeds the load.
159static int analyzeLoadFromClobberingWrite(Type *LoadTy, Value *LoadPtr,
160 Value *WritePtr,
161 uint64_t WriteSizeInBits,
162 const DataLayout &DL) {
163 // If the loaded or stored value is a first class array or struct, don't try
164 // to transform them. We need to be able to bitcast to integer.
165 if (LoadTy->isStructTy() || LoadTy->isArrayTy())
166 return -1;
167
168 int64_t StoreOffset = 0, LoadOffset = 0;
169 Value *StoreBase =
170 GetPointerBaseWithConstantOffset(WritePtr, StoreOffset, DL);
171 Value *LoadBase = GetPointerBaseWithConstantOffset(LoadPtr, LoadOffset, DL);
172 if (StoreBase != LoadBase)
173 return -1;
174
175 // If the load and store are to the exact same address, they should have been
176 // a must alias. AA must have gotten confused.
177 // FIXME: Study to see if/when this happens. One case is forwarding a memset
178 // to a load from the base of the memset.
179
180 // If the load and store don't overlap at all, the store doesn't provide
181 // anything to the load. In this case, they really don't alias at all, AA
182 // must have gotten confused.
183 uint64_t LoadSize = DL.getTypeSizeInBits(LoadTy);
184
185 if ((WriteSizeInBits & 7) | (LoadSize & 7))
186 return -1;
187 uint64_t StoreSize = WriteSizeInBits / 8; // Convert to bytes.
188 LoadSize /= 8;
189
190 bool isAAFailure = false;
191 if (StoreOffset < LoadOffset)
192 isAAFailure = StoreOffset + int64_t(StoreSize) <= LoadOffset;
193 else
194 isAAFailure = LoadOffset + int64_t(LoadSize) <= StoreOffset;
195
196 if (isAAFailure)
197 return -1;
198
199 // If the Load isn't completely contained within the stored bits, we don't
200 // have all the bits to feed it. We could do something crazy in the future
201 // (issue a smaller load then merge the bits in) but this seems unlikely to be
202 // valuable.
203 if (StoreOffset > LoadOffset ||
204 StoreOffset + StoreSize < LoadOffset + LoadSize)
205 return -1;
206
207 // Okay, we can do this transformation. Return the number of bytes into the
208 // store that the load is.
209 return LoadOffset - StoreOffset;
210}
211
212/// This function is called when we have a
213/// memdep query of a load that ends up being a clobbering store.
214int analyzeLoadFromClobberingStore(Type *LoadTy, Value *LoadPtr,
Daniel Berlincd07a0f2017-03-11 00:51:01 +0000215 StoreInst *DepSI, const DataLayout &DL) {
Philip Reamesa259dc32019-02-20 00:15:54 +0000216 auto *StoredVal = DepSI->getValueOperand();
217
Daniel Berlin5ac91792017-03-10 04:54:10 +0000218 // Cannot handle reading from store of first-class aggregate yet.
Philip Reamesa259dc32019-02-20 00:15:54 +0000219 if (StoredVal->getType()->isStructTy() ||
220 StoredVal->getType()->isArrayTy())
Daniel Berlin5ac91792017-03-10 04:54:10 +0000221 return -1;
222
Philip Reamesa259dc32019-02-20 00:15:54 +0000223 // Don't coerce non-integral pointers to integers or vice versa.
224 if (DL.isNonIntegralPointerType(StoredVal->getType()->getScalarType()) !=
225 DL.isNonIntegralPointerType(LoadTy->getScalarType())) {
226 // Allow casts of zero values to null as a special case
227 auto *CI = dyn_cast<Constant>(StoredVal);
228 if (!CI || !CI->isNullValue())
229 return -1;
230 }
231
Daniel Berlin5ac91792017-03-10 04:54:10 +0000232 Value *StorePtr = DepSI->getPointerOperand();
233 uint64_t StoreSize =
234 DL.getTypeSizeInBits(DepSI->getValueOperand()->getType());
235 return analyzeLoadFromClobberingWrite(LoadTy, LoadPtr, StorePtr, StoreSize,
236 DL);
237}
238
239/// This function is called when we have a
240/// memdep query of a load that ends up being clobbered by another load. See if
241/// the other load can feed into the second load.
242int analyzeLoadFromClobberingLoad(Type *LoadTy, Value *LoadPtr, LoadInst *DepLI,
243 const DataLayout &DL) {
244 // Cannot handle reading from store of first-class aggregate yet.
245 if (DepLI->getType()->isStructTy() || DepLI->getType()->isArrayTy())
246 return -1;
247
Philip Reamesa259dc32019-02-20 00:15:54 +0000248 // Don't coerce non-integral pointers to integers or vice versa.
249 if (DL.isNonIntegralPointerType(DepLI->getType()->getScalarType()) !=
250 DL.isNonIntegralPointerType(LoadTy->getScalarType()))
251 return -1;
252
Daniel Berlin5ac91792017-03-10 04:54:10 +0000253 Value *DepPtr = DepLI->getPointerOperand();
254 uint64_t DepSize = DL.getTypeSizeInBits(DepLI->getType());
255 int R = analyzeLoadFromClobberingWrite(LoadTy, LoadPtr, DepPtr, DepSize, DL);
256 if (R != -1)
257 return R;
258
259 // If we have a load/load clobber an DepLI can be widened to cover this load,
260 // then we should widen it!
261 int64_t LoadOffs = 0;
262 const Value *LoadBase =
263 GetPointerBaseWithConstantOffset(LoadPtr, LoadOffs, DL);
264 unsigned LoadSize = DL.getTypeStoreSize(LoadTy);
265
266 unsigned Size = MemoryDependenceResults::getLoadLoadClobberFullWidthSize(
267 LoadBase, LoadOffs, LoadSize, DepLI);
268 if (Size == 0)
269 return -1;
270
271 // Check non-obvious conditions enforced by MDA which we rely on for being
272 // able to materialize this potentially available value
273 assert(DepLI->isSimple() && "Cannot widen volatile/atomic load!");
274 assert(DepLI->getType()->isIntegerTy() && "Can't widen non-integer load");
275
276 return analyzeLoadFromClobberingWrite(LoadTy, LoadPtr, DepPtr, Size * 8, DL);
277}
278
279int analyzeLoadFromClobberingMemInst(Type *LoadTy, Value *LoadPtr,
280 MemIntrinsic *MI, const DataLayout &DL) {
281 // If the mem operation is a non-constant size, we can't handle it.
282 ConstantInt *SizeCst = dyn_cast<ConstantInt>(MI->getLength());
283 if (!SizeCst)
284 return -1;
285 uint64_t MemSizeInBits = SizeCst->getZExtValue() * 8;
286
287 // If this is memset, we just need to see if the offset is valid in the size
288 // of the memset..
Philip Reames92756a82019-02-19 23:07:15 +0000289 if (MI->getIntrinsicID() == Intrinsic::memset) {
Philip Reames92756a82019-02-19 23:07:15 +0000290 if (DL.isNonIntegralPointerType(LoadTy->getScalarType())) {
Philip Reames79d5e162019-02-20 00:31:28 +0000291 auto *CI = dyn_cast<ConstantInt>(cast<MemSetInst>(MI)->getValue());
Philip Reames92756a82019-02-19 23:07:15 +0000292 if (!CI || !CI->isZero())
293 return -1;
294 }
Daniel Berlin5ac91792017-03-10 04:54:10 +0000295 return analyzeLoadFromClobberingWrite(LoadTy, LoadPtr, MI->getDest(),
296 MemSizeInBits, DL);
Philip Reames92756a82019-02-19 23:07:15 +0000297 }
Daniel Berlin5ac91792017-03-10 04:54:10 +0000298
299 // If we have a memcpy/memmove, the only case we can handle is if this is a
300 // copy from constant memory. In that case, we can read directly from the
301 // constant memory.
302 MemTransferInst *MTI = cast<MemTransferInst>(MI);
303
304 Constant *Src = dyn_cast<Constant>(MTI->getSource());
305 if (!Src)
306 return -1;
307
308 GlobalVariable *GV = dyn_cast<GlobalVariable>(GetUnderlyingObject(Src, DL));
309 if (!GV || !GV->isConstant())
310 return -1;
311
312 // See if the access is within the bounds of the transfer.
313 int Offset = analyzeLoadFromClobberingWrite(LoadTy, LoadPtr, MI->getDest(),
314 MemSizeInBits, DL);
315 if (Offset == -1)
316 return Offset;
317
Philip Reames79d5e162019-02-20 00:31:28 +0000318 // Don't coerce non-integral pointers to integers or vice versa, and the
319 // memtransfer is implicitly a raw byte code
Philip Reames952d2342019-02-19 23:49:38 +0000320 if (DL.isNonIntegralPointerType(LoadTy->getScalarType()))
321 // TODO: Can allow nullptrs from constant zeros
322 return -1;
323
Daniel Berlin5ac91792017-03-10 04:54:10 +0000324 unsigned AS = Src->getType()->getPointerAddressSpace();
325 // Otherwise, see if we can constant fold a load from the constant with the
326 // offset applied as appropriate.
327 Src =
328 ConstantExpr::getBitCast(Src, Type::getInt8PtrTy(Src->getContext(), AS));
329 Constant *OffsetCst =
330 ConstantInt::get(Type::getInt64Ty(Src->getContext()), (unsigned)Offset);
331 Src = ConstantExpr::getGetElementPtr(Type::getInt8Ty(Src->getContext()), Src,
332 OffsetCst);
333 Src = ConstantExpr::getBitCast(Src, PointerType::get(LoadTy, AS));
334 if (ConstantFoldLoadFromConstPtr(Src, LoadTy, DL))
335 return Offset;
336 return -1;
337}
338
Daniel Berlin12883b12017-03-20 16:08:29 +0000339template <class T, class HelperClass>
340static T *getStoreValueForLoadHelper(T *SrcVal, unsigned Offset, Type *LoadTy,
341 HelperClass &Helper,
342 const DataLayout &DL) {
Daniel Berlin5ac91792017-03-10 04:54:10 +0000343 LLVMContext &Ctx = SrcVal->getType()->getContext();
344
Keno Fischer06f962c2017-05-09 21:07:20 +0000345 // If two pointers are in the same address space, they have the same size,
346 // so we don't need to do any truncation, etc. This avoids introducing
347 // ptrtoint instructions for pointers that may be non-integral.
348 if (SrcVal->getType()->isPointerTy() && LoadTy->isPointerTy() &&
349 cast<PointerType>(SrcVal->getType())->getAddressSpace() ==
350 cast<PointerType>(LoadTy)->getAddressSpace()) {
351 return SrcVal;
352 }
353
Daniel Berlin5ac91792017-03-10 04:54:10 +0000354 uint64_t StoreSize = (DL.getTypeSizeInBits(SrcVal->getType()) + 7) / 8;
355 uint64_t LoadSize = (DL.getTypeSizeInBits(LoadTy) + 7) / 8;
Daniel Berlin5ac91792017-03-10 04:54:10 +0000356 // Compute which bits of the stored value are being used by the load. Convert
357 // to an integer type to start with.
Craig Topper95d23472017-07-09 07:04:00 +0000358 if (SrcVal->getType()->isPtrOrPtrVectorTy())
Daniel Berlin12883b12017-03-20 16:08:29 +0000359 SrcVal = Helper.CreatePtrToInt(SrcVal, DL.getIntPtrType(SrcVal->getType()));
Daniel Berlin5ac91792017-03-10 04:54:10 +0000360 if (!SrcVal->getType()->isIntegerTy())
Daniel Berlin12883b12017-03-20 16:08:29 +0000361 SrcVal = Helper.CreateBitCast(SrcVal, IntegerType::get(Ctx, StoreSize * 8));
Daniel Berlin5ac91792017-03-10 04:54:10 +0000362
363 // Shift the bits to the least significant depending on endianness.
364 unsigned ShiftAmt;
365 if (DL.isLittleEndian())
366 ShiftAmt = Offset * 8;
367 else
368 ShiftAmt = (StoreSize - LoadSize - Offset) * 8;
Daniel Berlin5ac91792017-03-10 04:54:10 +0000369 if (ShiftAmt)
Daniel Berlin12883b12017-03-20 16:08:29 +0000370 SrcVal = Helper.CreateLShr(SrcVal,
371 ConstantInt::get(SrcVal->getType(), ShiftAmt));
Daniel Berlin5ac91792017-03-10 04:54:10 +0000372
373 if (LoadSize != StoreSize)
Daniel Berlin12883b12017-03-20 16:08:29 +0000374 SrcVal = Helper.CreateTruncOrBitCast(SrcVal,
375 IntegerType::get(Ctx, LoadSize * 8));
376 return SrcVal;
Daniel Berlin5ac91792017-03-10 04:54:10 +0000377}
378
Daniel Berlin12883b12017-03-20 16:08:29 +0000379/// This function is called when we have a memdep query of a load that ends up
380/// being a clobbering store. This means that the store provides bits used by
381/// the load but the pointers don't must-alias. Check this case to see if
382/// there is anything more we can do before we give up.
383Value *getStoreValueForLoad(Value *SrcVal, unsigned Offset, Type *LoadTy,
384 Instruction *InsertPt, const DataLayout &DL) {
Daniel Berlin5ac91792017-03-10 04:54:10 +0000385
Daniel Berlin12883b12017-03-20 16:08:29 +0000386 IRBuilder<> Builder(InsertPt);
387 SrcVal = getStoreValueForLoadHelper(SrcVal, Offset, LoadTy, Builder, DL);
388 return coerceAvailableValueToLoadTypeHelper(SrcVal, LoadTy, Builder, DL);
389}
390
391Constant *getConstantStoreValueForLoad(Constant *SrcVal, unsigned Offset,
392 Type *LoadTy, const DataLayout &DL) {
393 ConstantFolder F;
394 SrcVal = getStoreValueForLoadHelper(SrcVal, Offset, LoadTy, F, DL);
395 return coerceAvailableValueToLoadTypeHelper(SrcVal, LoadTy, F, DL);
396}
397
398/// This function is called when we have a memdep query of a load that ends up
399/// being a clobbering load. This means that the load *may* provide bits used
400/// by the load but we can't be sure because the pointers don't must-alias.
401/// Check this case to see if there is anything more we can do before we give
402/// up.
403Value *getLoadValueForLoad(LoadInst *SrcVal, unsigned Offset, Type *LoadTy,
404 Instruction *InsertPt, const DataLayout &DL) {
Daniel Berlin5ac91792017-03-10 04:54:10 +0000405 // If Offset+LoadTy exceeds the size of SrcVal, then we must be wanting to
406 // widen SrcVal out to a larger load.
407 unsigned SrcValStoreSize = DL.getTypeStoreSize(SrcVal->getType());
408 unsigned LoadSize = DL.getTypeStoreSize(LoadTy);
409 if (Offset + LoadSize > SrcValStoreSize) {
410 assert(SrcVal->isSimple() && "Cannot widen volatile/atomic load!");
411 assert(SrcVal->getType()->isIntegerTy() && "Can't widen non-integer load");
412 // If we have a load/load clobber an DepLI can be widened to cover this
413 // load, then we should widen it to the next power of 2 size big enough!
414 unsigned NewLoadSize = Offset + LoadSize;
415 if (!isPowerOf2_32(NewLoadSize))
416 NewLoadSize = NextPowerOf2(NewLoadSize);
417
418 Value *PtrVal = SrcVal->getPointerOperand();
Daniel Berlin5ac91792017-03-10 04:54:10 +0000419 // Insert the new load after the old load. This ensures that subsequent
420 // memdep queries will find the new load. We can't easily remove the old
421 // load completely because it is already in the value numbering table.
422 IRBuilder<> Builder(SrcVal->getParent(), ++BasicBlock::iterator(SrcVal));
James Y Knight14359ef2019-02-01 20:44:24 +0000423 Type *DestTy = IntegerType::get(LoadTy->getContext(), NewLoadSize * 8);
424 Type *DestPTy =
425 PointerType::get(DestTy, PtrVal->getType()->getPointerAddressSpace());
Daniel Berlin5ac91792017-03-10 04:54:10 +0000426 Builder.SetCurrentDebugLocation(SrcVal->getDebugLoc());
427 PtrVal = Builder.CreateBitCast(PtrVal, DestPTy);
James Y Knight14359ef2019-02-01 20:44:24 +0000428 LoadInst *NewLoad = Builder.CreateLoad(DestTy, PtrVal);
Daniel Berlin5ac91792017-03-10 04:54:10 +0000429 NewLoad->takeName(SrcVal);
430 NewLoad->setAlignment(SrcVal->getAlignment());
431
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000432 LLVM_DEBUG(dbgs() << "GVN WIDENED LOAD: " << *SrcVal << "\n");
433 LLVM_DEBUG(dbgs() << "TO: " << *NewLoad << "\n");
Daniel Berlin5ac91792017-03-10 04:54:10 +0000434
435 // Replace uses of the original load with the wider load. On a big endian
436 // system, we need to shift down to get the relevant bits.
437 Value *RV = NewLoad;
438 if (DL.isBigEndian())
439 RV = Builder.CreateLShr(RV, (NewLoadSize - SrcValStoreSize) * 8);
440 RV = Builder.CreateTrunc(RV, SrcVal->getType());
441 SrcVal->replaceAllUsesWith(RV);
442
443 SrcVal = NewLoad;
444 }
445
446 return getStoreValueForLoad(SrcVal, Offset, LoadTy, InsertPt, DL);
447}
448
Daniel Berlin12883b12017-03-20 16:08:29 +0000449Constant *getConstantLoadValueForLoad(Constant *SrcVal, unsigned Offset,
450 Type *LoadTy, const DataLayout &DL) {
451 unsigned SrcValStoreSize = DL.getTypeStoreSize(SrcVal->getType());
452 unsigned LoadSize = DL.getTypeStoreSize(LoadTy);
453 if (Offset + LoadSize > SrcValStoreSize)
454 return nullptr;
455 return getConstantStoreValueForLoad(SrcVal, Offset, LoadTy, DL);
456}
457
458template <class T, class HelperClass>
459T *getMemInstValueForLoadHelper(MemIntrinsic *SrcInst, unsigned Offset,
460 Type *LoadTy, HelperClass &Helper,
461 const DataLayout &DL) {
Daniel Berlin5ac91792017-03-10 04:54:10 +0000462 LLVMContext &Ctx = LoadTy->getContext();
463 uint64_t LoadSize = DL.getTypeSizeInBits(LoadTy) / 8;
464
Daniel Berlin5ac91792017-03-10 04:54:10 +0000465 // We know that this method is only called when the mem transfer fully
466 // provides the bits for the load.
467 if (MemSetInst *MSI = dyn_cast<MemSetInst>(SrcInst)) {
468 // memset(P, 'x', 1234) -> splat('x'), even if x is a variable, and
469 // independently of what the offset is.
Daniel Berlin12883b12017-03-20 16:08:29 +0000470 T *Val = cast<T>(MSI->getValue());
Daniel Berlin5ac91792017-03-10 04:54:10 +0000471 if (LoadSize != 1)
Daniel Berlin12883b12017-03-20 16:08:29 +0000472 Val =
473 Helper.CreateZExtOrBitCast(Val, IntegerType::get(Ctx, LoadSize * 8));
474 T *OneElt = Val;
Daniel Berlin5ac91792017-03-10 04:54:10 +0000475
476 // Splat the value out to the right number of bits.
477 for (unsigned NumBytesSet = 1; NumBytesSet != LoadSize;) {
478 // If we can double the number of bytes set, do it.
479 if (NumBytesSet * 2 <= LoadSize) {
Daniel Berlin12883b12017-03-20 16:08:29 +0000480 T *ShVal = Helper.CreateShl(
481 Val, ConstantInt::get(Val->getType(), NumBytesSet * 8));
482 Val = Helper.CreateOr(Val, ShVal);
Daniel Berlin5ac91792017-03-10 04:54:10 +0000483 NumBytesSet <<= 1;
484 continue;
485 }
486
487 // Otherwise insert one byte at a time.
Daniel Berlin12883b12017-03-20 16:08:29 +0000488 T *ShVal = Helper.CreateShl(Val, ConstantInt::get(Val->getType(), 1 * 8));
489 Val = Helper.CreateOr(OneElt, ShVal);
Daniel Berlin5ac91792017-03-10 04:54:10 +0000490 ++NumBytesSet;
491 }
492
Daniel Berlin12883b12017-03-20 16:08:29 +0000493 return coerceAvailableValueToLoadTypeHelper(Val, LoadTy, Helper, DL);
Daniel Berlin5ac91792017-03-10 04:54:10 +0000494 }
495
496 // Otherwise, this is a memcpy/memmove from a constant global.
497 MemTransferInst *MTI = cast<MemTransferInst>(SrcInst);
498 Constant *Src = cast<Constant>(MTI->getSource());
499 unsigned AS = Src->getType()->getPointerAddressSpace();
500
501 // Otherwise, see if we can constant fold a load from the constant with the
502 // offset applied as appropriate.
503 Src =
504 ConstantExpr::getBitCast(Src, Type::getInt8PtrTy(Src->getContext(), AS));
505 Constant *OffsetCst =
506 ConstantInt::get(Type::getInt64Ty(Src->getContext()), (unsigned)Offset);
507 Src = ConstantExpr::getGetElementPtr(Type::getInt8Ty(Src->getContext()), Src,
508 OffsetCst);
509 Src = ConstantExpr::getBitCast(Src, PointerType::get(LoadTy, AS));
510 return ConstantFoldLoadFromConstPtr(Src, LoadTy, DL);
511}
Daniel Berlin12883b12017-03-20 16:08:29 +0000512
513/// This function is called when we have a
514/// memdep query of a load that ends up being a clobbering mem intrinsic.
515Value *getMemInstValueForLoad(MemIntrinsic *SrcInst, unsigned Offset,
516 Type *LoadTy, Instruction *InsertPt,
517 const DataLayout &DL) {
518 IRBuilder<> Builder(InsertPt);
519 return getMemInstValueForLoadHelper<Value, IRBuilder<>>(SrcInst, Offset,
520 LoadTy, Builder, DL);
521}
522
523Constant *getConstantMemInstValueForLoad(MemIntrinsic *SrcInst, unsigned Offset,
524 Type *LoadTy, const DataLayout &DL) {
525 // The only case analyzeLoadFromClobberingMemInst cannot be converted to a
526 // constant is when it's a memset of a non-constant.
527 if (auto *MSI = dyn_cast<MemSetInst>(SrcInst))
528 if (!isa<Constant>(MSI->getValue()))
529 return nullptr;
530 ConstantFolder F;
531 return getMemInstValueForLoadHelper<Constant, ConstantFolder>(SrcInst, Offset,
532 LoadTy, F, DL);
533}
Daniel Berlin5ac91792017-03-10 04:54:10 +0000534} // namespace VNCoercion
535} // namespace llvm