481 lines · cpp
1#include "llvm/Transforms/Utils/VNCoercion.h"2#include "llvm/Analysis/ConstantFolding.h"3#include "llvm/Analysis/ValueTracking.h"4#include "llvm/IR/IRBuilder.h"5#include "llvm/IR/IntrinsicInst.h"6 7#define DEBUG_TYPE "vncoerce"8 9namespace llvm {10namespace VNCoercion {11 12static bool isFirstClassAggregateOrScalableType(Type *Ty) {13 return Ty->isStructTy() || Ty->isArrayTy() || isa<ScalableVectorType>(Ty);14}15 16/// Return true if coerceAvailableValueToLoadType will succeed.17bool canCoerceMustAliasedValueToLoad(Value *StoredVal, Type *LoadTy,18 Function *F) {19 Type *StoredTy = StoredVal->getType();20 if (StoredTy == LoadTy)21 return true;22 23 const DataLayout &DL = F->getDataLayout();24 TypeSize MinStoreSize = DL.getTypeSizeInBits(StoredTy);25 TypeSize LoadSize = DL.getTypeSizeInBits(LoadTy);26 if (isa<ScalableVectorType>(StoredTy) && isa<ScalableVectorType>(LoadTy) &&27 MinStoreSize == LoadSize)28 return true;29 30 // If the loaded/stored value is a first class array/struct, don't try to31 // transform them. We need to be able to bitcast to integer. For scalable32 // vectors forwarded to fixed-sized vectors @llvm.vector.extract is used.33 if (isa<ScalableVectorType>(StoredTy) && isa<FixedVectorType>(LoadTy)) {34 if (StoredTy->getScalarType() != LoadTy->getScalarType())35 return false;36 37 // If it is known at compile-time that the VScale is larger than one,38 // use that information to allow for wider loads.39 const auto &Attrs = F->getAttributes().getFnAttrs();40 unsigned MinVScale = Attrs.getVScaleRangeMin();41 MinStoreSize =42 TypeSize::getFixed(MinStoreSize.getKnownMinValue() * MinVScale);43 } else if (isFirstClassAggregateOrScalableType(LoadTy) ||44 isFirstClassAggregateOrScalableType(StoredTy)) {45 return false;46 }47 48 // The store size must be byte-aligned to support future type casts.49 if (llvm::alignTo(MinStoreSize, 8) != MinStoreSize)50 return false;51 52 // The store has to be at least as big as the load.53 if (!TypeSize::isKnownGE(MinStoreSize, LoadSize))54 return false;55 56 bool StoredNI = DL.isNonIntegralPointerType(StoredTy->getScalarType());57 bool LoadNI = DL.isNonIntegralPointerType(LoadTy->getScalarType());58 // Don't coerce non-integral pointers to integers or vice versa.59 if (StoredNI != LoadNI) {60 // As a special case, allow coercion of memset used to initialize61 // an array w/null. Despite non-integral pointers not generally having a62 // specific bit pattern, we do assume null is zero.63 if (auto *CI = dyn_cast<Constant>(StoredVal))64 return CI->isNullValue();65 return false;66 } else if (StoredNI && LoadNI &&67 StoredTy->getPointerAddressSpace() !=68 LoadTy->getPointerAddressSpace()) {69 return false;70 }71 72 // The implementation below uses inttoptr for vectors of unequal size; we73 // can't allow this for non integral pointers. We could teach it to extract74 // exact subvectors if desired.75 if (StoredNI && (StoredTy->isScalableTy() || MinStoreSize != LoadSize))76 return false;77 78 if (StoredTy->isTargetExtTy() || LoadTy->isTargetExtTy())79 return false;80 81 return true;82}83 84/// If we saw a store of a value to memory, and85/// then a load from a must-aliased pointer of a different type, try to coerce86/// the stored value. LoadedTy is the type of the load we want to replace.87/// IRB is IRBuilder used to insert new instructions.88///89/// If we can't do it, return null.90Value *coerceAvailableValueToLoadType(Value *StoredVal, Type *LoadedTy,91 IRBuilderBase &Helper, Function *F) {92 assert(canCoerceMustAliasedValueToLoad(StoredVal, LoadedTy, F) &&93 "precondition violation - materialization can't fail");94 const DataLayout &DL = F->getDataLayout();95 if (auto *C = dyn_cast<Constant>(StoredVal))96 StoredVal = ConstantFoldConstant(C, DL);97 98 // If this is already the right type, just return it.99 Type *StoredValTy = StoredVal->getType();100 101 // If this is a scalable vector forwarded to a fixed vector load, create102 // a @llvm.vector.extract instead of bitcasts.103 if (isa<ScalableVectorType>(StoredVal->getType()) &&104 isa<FixedVectorType>(LoadedTy)) {105 return Helper.CreateIntrinsic(LoadedTy, Intrinsic::vector_extract,106 {StoredVal, Helper.getInt64(0)});107 }108 109 TypeSize StoredValSize = DL.getTypeSizeInBits(StoredValTy);110 TypeSize LoadedValSize = DL.getTypeSizeInBits(LoadedTy);111 112 // If the store and reload are the same size, we can always reuse it.113 if (StoredValSize == LoadedValSize) {114 // Pointer to Pointer -> use bitcast.115 if (StoredValTy->isPtrOrPtrVectorTy() && LoadedTy->isPtrOrPtrVectorTy()) {116 StoredVal = Helper.CreateBitCast(StoredVal, LoadedTy);117 } else {118 // Convert source pointers to integers, which can be bitcast.119 if (StoredValTy->isPtrOrPtrVectorTy()) {120 StoredValTy = DL.getIntPtrType(StoredValTy);121 StoredVal = Helper.CreatePtrToInt(StoredVal, StoredValTy);122 }123 124 Type *TypeToCastTo = LoadedTy;125 if (TypeToCastTo->isPtrOrPtrVectorTy())126 TypeToCastTo = DL.getIntPtrType(TypeToCastTo);127 128 if (StoredValTy != TypeToCastTo)129 StoredVal = Helper.CreateBitCast(StoredVal, TypeToCastTo);130 131 // Cast to pointer if the load needs a pointer type.132 if (LoadedTy->isPtrOrPtrVectorTy())133 StoredVal = Helper.CreateIntToPtr(StoredVal, LoadedTy);134 }135 136 if (auto *C = dyn_cast<ConstantExpr>(StoredVal))137 StoredVal = ConstantFoldConstant(C, DL);138 139 return StoredVal;140 }141 // If the loaded value is smaller than the available value, then we can142 // extract out a piece from it. If the available value is too small, then we143 // can't do anything.144 assert(!StoredValSize.isScalable() &&145 TypeSize::isKnownGE(StoredValSize, LoadedValSize) &&146 "canCoerceMustAliasedValueToLoad fail");147 148 // Convert source pointers to integers, which can be manipulated.149 if (StoredValTy->isPtrOrPtrVectorTy()) {150 StoredValTy = DL.getIntPtrType(StoredValTy);151 StoredVal = Helper.CreatePtrToInt(StoredVal, StoredValTy);152 }153 154 // Convert vectors and fp to integer, which can be manipulated.155 if (!StoredValTy->isIntegerTy()) {156 StoredValTy = IntegerType::get(StoredValTy->getContext(), StoredValSize);157 StoredVal = Helper.CreateBitCast(StoredVal, StoredValTy);158 }159 160 // If this is a big-endian system, we need to shift the value down to the low161 // bits so that a truncate will work.162 if (DL.isBigEndian()) {163 uint64_t ShiftAmt = DL.getTypeStoreSizeInBits(StoredValTy).getFixedValue() -164 DL.getTypeStoreSizeInBits(LoadedTy).getFixedValue();165 StoredVal = Helper.CreateLShr(166 StoredVal, ConstantInt::get(StoredVal->getType(), ShiftAmt));167 }168 169 // Truncate the integer to the right size now.170 Type *NewIntTy = IntegerType::get(StoredValTy->getContext(), LoadedValSize);171 StoredVal = Helper.CreateTruncOrBitCast(StoredVal, NewIntTy);172 173 if (LoadedTy != NewIntTy) {174 // If the result is a pointer, inttoptr.175 if (LoadedTy->isPtrOrPtrVectorTy())176 StoredVal = Helper.CreateIntToPtr(StoredVal, LoadedTy);177 else178 // Otherwise, bitcast.179 StoredVal = Helper.CreateBitCast(StoredVal, LoadedTy);180 }181 182 if (auto *C = dyn_cast<Constant>(StoredVal))183 StoredVal = ConstantFoldConstant(C, DL);184 185 return StoredVal;186}187 188/// This function is called when we have a memdep query of a load that ends up189/// being a clobbering memory write (store, memset, memcpy, memmove). This190/// means that the write *may* provide bits used by the load but we can't be191/// sure because the pointers don't must-alias.192///193/// Check this case to see if there is anything more we can do before we give194/// up. This returns -1 if we have to give up, or a byte number in the stored195/// value of the piece that feeds the load.196static int analyzeLoadFromClobberingWrite(Type *LoadTy, Value *LoadPtr,197 Value *WritePtr,198 uint64_t WriteSizeInBits,199 const DataLayout &DL) {200 // If the loaded/stored value is a first class array/struct, or scalable type,201 // don't try to transform them. We need to be able to bitcast to integer.202 if (isFirstClassAggregateOrScalableType(LoadTy))203 return -1;204 205 int64_t StoreOffset = 0, LoadOffset = 0;206 Value *StoreBase =207 GetPointerBaseWithConstantOffset(WritePtr, StoreOffset, DL);208 Value *LoadBase = GetPointerBaseWithConstantOffset(LoadPtr, LoadOffset, DL);209 if (StoreBase != LoadBase)210 return -1;211 212 uint64_t LoadSize = DL.getTypeSizeInBits(LoadTy).getFixedValue();213 214 if ((WriteSizeInBits & 7) | (LoadSize & 7))215 return -1;216 uint64_t StoreSize = WriteSizeInBits / 8; // Convert to bytes.217 LoadSize /= 8;218 219 // If the Load isn't completely contained within the stored bits, we don't220 // have all the bits to feed it. We could do something crazy in the future221 // (issue a smaller load then merge the bits in) but this seems unlikely to be222 // valuable.223 if (StoreOffset > LoadOffset ||224 StoreOffset + int64_t(StoreSize) < LoadOffset + int64_t(LoadSize))225 return -1;226 227 // Okay, we can do this transformation. Return the number of bytes into the228 // store that the load is.229 return LoadOffset - StoreOffset;230}231 232/// This function is called when we have a233/// memdep query of a load that ends up being a clobbering store.234int analyzeLoadFromClobberingStore(Type *LoadTy, Value *LoadPtr,235 StoreInst *DepSI, const DataLayout &DL) {236 auto *StoredVal = DepSI->getValueOperand();237 238 // Cannot handle reading from store of first-class aggregate or scalable type.239 if (isFirstClassAggregateOrScalableType(StoredVal->getType()))240 return -1;241 242 if (!canCoerceMustAliasedValueToLoad(StoredVal, LoadTy, DepSI->getFunction()))243 return -1;244 245 Value *StorePtr = DepSI->getPointerOperand();246 uint64_t StoreSize =247 DL.getTypeSizeInBits(DepSI->getValueOperand()->getType()).getFixedValue();248 return analyzeLoadFromClobberingWrite(LoadTy, LoadPtr, StorePtr, StoreSize,249 DL);250}251 252/// This function is called when we have a253/// memdep query of a load that ends up being clobbered by another load. See if254/// the other load can feed into the second load.255int analyzeLoadFromClobberingLoad(Type *LoadTy, Value *LoadPtr, LoadInst *DepLI,256 const DataLayout &DL) {257 // Cannot handle reading from store of first-class aggregate or scalable type.258 if (isFirstClassAggregateOrScalableType(DepLI->getType()))259 return -1;260 261 if (!canCoerceMustAliasedValueToLoad(DepLI, LoadTy, DepLI->getFunction()))262 return -1;263 264 Value *DepPtr = DepLI->getPointerOperand();265 uint64_t DepSize = DL.getTypeSizeInBits(DepLI->getType()).getFixedValue();266 return analyzeLoadFromClobberingWrite(LoadTy, LoadPtr, DepPtr, DepSize, DL);267}268 269int analyzeLoadFromClobberingMemInst(Type *LoadTy, Value *LoadPtr,270 MemIntrinsic *MI, const DataLayout &DL) {271 // If the mem operation is a non-constant size, we can't handle it.272 ConstantInt *SizeCst = dyn_cast<ConstantInt>(MI->getLength());273 if (!SizeCst)274 return -1;275 uint64_t MemSizeInBits = SizeCst->getZExtValue() * 8;276 277 // If this is memset, we just need to see if the offset is valid in the size278 // of the memset..279 if (const auto *memset_inst = dyn_cast<MemSetInst>(MI)) {280 if (DL.isNonIntegralPointerType(LoadTy->getScalarType())) {281 auto *CI = dyn_cast<ConstantInt>(memset_inst->getValue());282 if (!CI || !CI->isZero())283 return -1;284 }285 return analyzeLoadFromClobberingWrite(LoadTy, LoadPtr, MI->getDest(),286 MemSizeInBits, DL);287 }288 289 // If we have a memcpy/memmove, the only case we can handle is if this is a290 // copy from constant memory. In that case, we can read directly from the291 // constant memory.292 MemTransferInst *MTI = cast<MemTransferInst>(MI);293 294 Constant *Src = dyn_cast<Constant>(MTI->getSource());295 if (!Src)296 return -1;297 298 GlobalVariable *GV = dyn_cast<GlobalVariable>(getUnderlyingObject(Src));299 if (!GV || !GV->isConstant() || !GV->hasDefinitiveInitializer())300 return -1;301 302 // See if the access is within the bounds of the transfer.303 int Offset = analyzeLoadFromClobberingWrite(LoadTy, LoadPtr, MI->getDest(),304 MemSizeInBits, DL);305 if (Offset == -1)306 return Offset;307 308 // Otherwise, see if we can constant fold a load from the constant with the309 // offset applied as appropriate.310 unsigned IndexSize = DL.getIndexTypeSizeInBits(Src->getType());311 if (ConstantFoldLoadFromConstPtr(Src, LoadTy, APInt(IndexSize, Offset), DL))312 return Offset;313 return -1;314}315 316static Value *getStoreValueForLoadHelper(Value *SrcVal, unsigned Offset,317 Type *LoadTy, IRBuilderBase &Builder,318 const DataLayout &DL) {319 LLVMContext &Ctx = SrcVal->getType()->getContext();320 321 // If two pointers are in the same address space, they have the same size,322 // so we don't need to do any truncation, etc. This avoids introducing323 // ptrtoint instructions for pointers that may be non-integral.324 if (SrcVal->getType()->isPointerTy() && LoadTy->isPointerTy() &&325 cast<PointerType>(SrcVal->getType())->getAddressSpace() ==326 cast<PointerType>(LoadTy)->getAddressSpace()) {327 return SrcVal;328 }329 330 // Return scalable values directly to avoid needing to bitcast to integer331 // types, as we do not support non-zero Offsets.332 if (isa<ScalableVectorType>(LoadTy)) {333 assert(Offset == 0 && "Expected a zero offset for scalable types");334 return SrcVal;335 }336 337 // For the case of a scalable vector being forwarded to a fixed-sized load,338 // only equal element types are allowed and a @llvm.vector.extract will be339 // used instead of bitcasts.340 if (isa<ScalableVectorType>(SrcVal->getType()) &&341 isa<FixedVectorType>(LoadTy)) {342 assert(Offset == 0 &&343 SrcVal->getType()->getScalarType() == LoadTy->getScalarType());344 return SrcVal;345 }346 347 uint64_t StoreSize =348 (DL.getTypeSizeInBits(SrcVal->getType()).getFixedValue() + 7) / 8;349 uint64_t LoadSize = (DL.getTypeSizeInBits(LoadTy).getFixedValue() + 7) / 8;350 // Compute which bits of the stored value are being used by the load. Convert351 // to an integer type to start with.352 if (SrcVal->getType()->isPtrOrPtrVectorTy())353 SrcVal =354 Builder.CreatePtrToInt(SrcVal, DL.getIntPtrType(SrcVal->getType()));355 if (!SrcVal->getType()->isIntegerTy())356 SrcVal =357 Builder.CreateBitCast(SrcVal, IntegerType::get(Ctx, StoreSize * 8));358 359 // Shift the bits to the least significant depending on endianness.360 unsigned ShiftAmt;361 if (DL.isLittleEndian())362 ShiftAmt = Offset * 8;363 else364 ShiftAmt = (StoreSize - LoadSize - Offset) * 8;365 if (ShiftAmt)366 SrcVal = Builder.CreateLShr(SrcVal,367 ConstantInt::get(SrcVal->getType(), ShiftAmt));368 369 if (LoadSize != StoreSize)370 SrcVal = Builder.CreateTruncOrBitCast(SrcVal,371 IntegerType::get(Ctx, LoadSize * 8));372 return SrcVal;373}374 375Value *getValueForLoad(Value *SrcVal, unsigned Offset, Type *LoadTy,376 Instruction *InsertPt, Function *F) {377 const DataLayout &DL = F->getDataLayout();378#ifndef NDEBUG379 TypeSize MinSrcValSize = DL.getTypeStoreSize(SrcVal->getType());380 TypeSize LoadSize = DL.getTypeStoreSize(LoadTy);381 if (MinSrcValSize.isScalable() && !LoadSize.isScalable())382 MinSrcValSize =383 TypeSize::getFixed(MinSrcValSize.getKnownMinValue() *384 F->getAttributes().getFnAttrs().getVScaleRangeMin());385 assert((MinSrcValSize.isScalable() || Offset + LoadSize <= MinSrcValSize) &&386 "Expected Offset + LoadSize <= SrcValSize");387 assert((!MinSrcValSize.isScalable() ||388 (Offset == 0 && TypeSize::isKnownLE(LoadSize, MinSrcValSize))) &&389 "Expected offset of zero and LoadSize <= SrcValSize");390#endif391 IRBuilder<> Builder(InsertPt);392 SrcVal = getStoreValueForLoadHelper(SrcVal, Offset, LoadTy, Builder, DL);393 return coerceAvailableValueToLoadType(SrcVal, LoadTy, Builder, F);394}395 396Constant *getConstantValueForLoad(Constant *SrcVal, unsigned Offset,397 Type *LoadTy, const DataLayout &DL) {398#ifndef NDEBUG399 unsigned SrcValSize = DL.getTypeStoreSize(SrcVal->getType()).getFixedValue();400 unsigned LoadSize = DL.getTypeStoreSize(LoadTy).getFixedValue();401 assert(Offset + LoadSize <= SrcValSize);402#endif403 return ConstantFoldLoadFromConst(SrcVal, LoadTy, APInt(32, Offset), DL);404}405 406/// This function is called when we have a407/// memdep query of a load that ends up being a clobbering mem intrinsic.408Value *getMemInstValueForLoad(MemIntrinsic *SrcInst, unsigned Offset,409 Type *LoadTy, Instruction *InsertPt,410 const DataLayout &DL) {411 LLVMContext &Ctx = LoadTy->getContext();412 uint64_t LoadSize = DL.getTypeSizeInBits(LoadTy).getFixedValue() / 8;413 IRBuilder<> Builder(InsertPt);414 415 // We know that this method is only called when the mem transfer fully416 // provides the bits for the load.417 if (MemSetInst *MSI = dyn_cast<MemSetInst>(SrcInst)) {418 // memset(P, 'x', 1234) -> splat('x'), even if x is a variable, and419 // independently of what the offset is.420 Value *Val = MSI->getValue();421 if (LoadSize != 1)422 Val =423 Builder.CreateZExtOrBitCast(Val, IntegerType::get(Ctx, LoadSize * 8));424 Value *OneElt = Val;425 426 // Splat the value out to the right number of bits.427 for (unsigned NumBytesSet = 1; NumBytesSet != LoadSize;) {428 // If we can double the number of bytes set, do it.429 if (NumBytesSet * 2 <= LoadSize) {430 Value *ShVal = Builder.CreateShl(431 Val, ConstantInt::get(Val->getType(), NumBytesSet * 8));432 Val = Builder.CreateOr(Val, ShVal);433 NumBytesSet <<= 1;434 continue;435 }436 437 // Otherwise insert one byte at a time.438 Value *ShVal =439 Builder.CreateShl(Val, ConstantInt::get(Val->getType(), 1 * 8));440 Val = Builder.CreateOr(OneElt, ShVal);441 ++NumBytesSet;442 }443 444 return coerceAvailableValueToLoadType(Val, LoadTy, Builder,445 InsertPt->getFunction());446 }447 448 // Otherwise, this is a memcpy/memmove from a constant global.449 MemTransferInst *MTI = cast<MemTransferInst>(SrcInst);450 Constant *Src = cast<Constant>(MTI->getSource());451 unsigned IndexSize = DL.getIndexTypeSizeInBits(Src->getType());452 return ConstantFoldLoadFromConstPtr(Src, LoadTy, APInt(IndexSize, Offset),453 DL);454}455 456Constant *getConstantMemInstValueForLoad(MemIntrinsic *SrcInst, unsigned Offset,457 Type *LoadTy, const DataLayout &DL) {458 LLVMContext &Ctx = LoadTy->getContext();459 uint64_t LoadSize = DL.getTypeSizeInBits(LoadTy).getFixedValue() / 8;460 461 // We know that this method is only called when the mem transfer fully462 // provides the bits for the load.463 if (MemSetInst *MSI = dyn_cast<MemSetInst>(SrcInst)) {464 auto *Val = dyn_cast<ConstantInt>(MSI->getValue());465 if (!Val)466 return nullptr;467 468 Val = ConstantInt::get(Ctx, APInt::getSplat(LoadSize * 8, Val->getValue()));469 return ConstantFoldLoadFromConst(Val, LoadTy, DL);470 }471 472 // Otherwise, this is a memcpy/memmove from a constant global.473 MemTransferInst *MTI = cast<MemTransferInst>(SrcInst);474 Constant *Src = cast<Constant>(MTI->getSource());475 unsigned IndexSize = DL.getIndexTypeSizeInBits(Src->getType());476 return ConstantFoldLoadFromConstPtr(Src, LoadTy, APInt(IndexSize, Offset),477 DL);478}479} // namespace VNCoercion480} // namespace llvm481