Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 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" |
| 9 | |
| 10 | #define DEBUG_TYPE "vncoerce" |
| 11 | namespace llvm { |
| 12 | namespace VNCoercion { |
| 13 | |
| 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()) |
| 21 | return false; |
| 22 | |
Matthew Voss | 30648ab | 2018-06-21 21:43:20 +0000 | [diff] [blame] | 23 | 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 Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 29 | // The store has to be at least as big as the load. |
Matthew Voss | 30648ab | 2018-06-21 21:43:20 +0000 | [diff] [blame] | 30 | if (StoreSize < DL.getTypeSizeInBits(LoadTy)) |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 31 | return false; |
| 32 | |
Sanjoy Das | 5945447 | 2017-04-19 18:21:09 +0000 | [diff] [blame] | 33 | // Don't coerce non-integral pointers to integers or vice versa. |
Philip Reames | 322eb76 | 2019-02-19 23:19:51 +0000 | [diff] [blame] | 34 | if (DL.isNonIntegralPointerType(StoredVal->getType()->getScalarType()) != |
| 35 | DL.isNonIntegralPointerType(LoadTy->getScalarType())) { |
Philip Reames | 92756a8 | 2019-02-19 23:07:15 +0000 | [diff] [blame] | 36 | // 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 Reames | 79d5e16 | 2019-02-20 00:31:28 +0000 | [diff] [blame] | 39 | if (auto *CI = dyn_cast<Constant>(StoredVal)) |
| 40 | return CI->isNullValue(); |
Sanjoy Das | 5945447 | 2017-04-19 18:21:09 +0000 | [diff] [blame] | 41 | return false; |
Philip Reames | 92756a8 | 2019-02-19 23:07:15 +0000 | [diff] [blame] | 42 | } |
| 43 | |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 44 | return true; |
| 45 | } |
| 46 | |
Daniel Berlin | 12883b1 | 2017-03-20 16:08:29 +0000 | [diff] [blame] | 47 | template <class T, class HelperClass> |
| 48 | static T *coerceAvailableValueToLoadTypeHelper(T *StoredVal, Type *LoadedTy, |
| 49 | HelperClass &Helper, |
| 50 | const DataLayout &DL) { |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 51 | assert(canCoerceMustAliasedValueToLoad(StoredVal, LoadedTy, DL) && |
| 52 | "precondition violation - materialization can't fail"); |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 53 | 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 Topper | 95d2347 | 2017-07-09 07:04:00 +0000 | [diff] [blame] | 66 | if (StoredValTy->isPtrOrPtrVectorTy() && LoadedTy->isPtrOrPtrVectorTy()) { |
Daniel Berlin | 12883b1 | 2017-03-20 16:08:29 +0000 | [diff] [blame] | 67 | StoredVal = Helper.CreateBitCast(StoredVal, LoadedTy); |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 68 | } else { |
| 69 | // Convert source pointers to integers, which can be bitcast. |
Craig Topper | 95d2347 | 2017-07-09 07:04:00 +0000 | [diff] [blame] | 70 | if (StoredValTy->isPtrOrPtrVectorTy()) { |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 71 | StoredValTy = DL.getIntPtrType(StoredValTy); |
Daniel Berlin | 12883b1 | 2017-03-20 16:08:29 +0000 | [diff] [blame] | 72 | StoredVal = Helper.CreatePtrToInt(StoredVal, StoredValTy); |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 73 | } |
| 74 | |
| 75 | Type *TypeToCastTo = LoadedTy; |
Craig Topper | 95d2347 | 2017-07-09 07:04:00 +0000 | [diff] [blame] | 76 | if (TypeToCastTo->isPtrOrPtrVectorTy()) |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 77 | TypeToCastTo = DL.getIntPtrType(TypeToCastTo); |
| 78 | |
| 79 | if (StoredValTy != TypeToCastTo) |
Daniel Berlin | 12883b1 | 2017-03-20 16:08:29 +0000 | [diff] [blame] | 80 | StoredVal = Helper.CreateBitCast(StoredVal, TypeToCastTo); |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 81 | |
| 82 | // Cast to pointer if the load needs a pointer type. |
Craig Topper | 95d2347 | 2017-07-09 07:04:00 +0000 | [diff] [blame] | 83 | if (LoadedTy->isPtrOrPtrVectorTy()) |
Daniel Berlin | 12883b1 | 2017-03-20 16:08:29 +0000 | [diff] [blame] | 84 | StoredVal = Helper.CreateIntToPtr(StoredVal, LoadedTy); |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 85 | } |
| 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 Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 93 | // 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 Topper | 95d2347 | 2017-07-09 07:04:00 +0000 | [diff] [blame] | 100 | if (StoredValTy->isPtrOrPtrVectorTy()) { |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 101 | StoredValTy = DL.getIntPtrType(StoredValTy); |
Daniel Berlin | 12883b1 | 2017-03-20 16:08:29 +0000 | [diff] [blame] | 102 | StoredVal = Helper.CreatePtrToInt(StoredVal, StoredValTy); |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 103 | } |
| 104 | |
| 105 | // Convert vectors and fp to integer, which can be manipulated. |
| 106 | if (!StoredValTy->isIntegerTy()) { |
| 107 | StoredValTy = IntegerType::get(StoredValTy->getContext(), StoredValSize); |
Daniel Berlin | 12883b1 | 2017-03-20 16:08:29 +0000 | [diff] [blame] | 108 | StoredVal = Helper.CreateBitCast(StoredVal, StoredValTy); |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 109 | } |
| 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 Berlin | 12883b1 | 2017-03-20 16:08:29 +0000 | [diff] [blame] | 116 | StoredVal = Helper.CreateLShr( |
| 117 | StoredVal, ConstantInt::get(StoredVal->getType(), ShiftAmt)); |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 118 | } |
| 119 | |
| 120 | // Truncate the integer to the right size now. |
| 121 | Type *NewIntTy = IntegerType::get(StoredValTy->getContext(), LoadedValSize); |
Daniel Berlin | 12883b1 | 2017-03-20 16:08:29 +0000 | [diff] [blame] | 122 | StoredVal = Helper.CreateTruncOrBitCast(StoredVal, NewIntTy); |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 123 | |
| 124 | if (LoadedTy != NewIntTy) { |
| 125 | // If the result is a pointer, inttoptr. |
Craig Topper | 95d2347 | 2017-07-09 07:04:00 +0000 | [diff] [blame] | 126 | if (LoadedTy->isPtrOrPtrVectorTy()) |
Daniel Berlin | 12883b1 | 2017-03-20 16:08:29 +0000 | [diff] [blame] | 127 | StoredVal = Helper.CreateIntToPtr(StoredVal, LoadedTy); |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 128 | else |
| 129 | // Otherwise, bitcast. |
Daniel Berlin | 12883b1 | 2017-03-20 16:08:29 +0000 | [diff] [blame] | 130 | StoredVal = Helper.CreateBitCast(StoredVal, LoadedTy); |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 131 | } |
| 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 Berlin | 12883b1 | 2017-03-20 16:08:29 +0000 | [diff] [blame] | 140 | /// 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. |
| 146 | Value *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 Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 155 | /// |
| 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. |
| 159 | static 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. |
| 214 | int analyzeLoadFromClobberingStore(Type *LoadTy, Value *LoadPtr, |
Daniel Berlin | cd07a0f | 2017-03-11 00:51:01 +0000 | [diff] [blame] | 215 | StoreInst *DepSI, const DataLayout &DL) { |
Philip Reames | a259dc3 | 2019-02-20 00:15:54 +0000 | [diff] [blame] | 216 | auto *StoredVal = DepSI->getValueOperand(); |
| 217 | |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 218 | // Cannot handle reading from store of first-class aggregate yet. |
Philip Reames | a259dc3 | 2019-02-20 00:15:54 +0000 | [diff] [blame] | 219 | if (StoredVal->getType()->isStructTy() || |
| 220 | StoredVal->getType()->isArrayTy()) |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 221 | return -1; |
| 222 | |
Philip Reames | a259dc3 | 2019-02-20 00:15:54 +0000 | [diff] [blame] | 223 | // 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 Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 232 | 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. |
| 242 | int 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 Reames | a259dc3 | 2019-02-20 00:15:54 +0000 | [diff] [blame] | 248 | // 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 Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 253 | 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 | |
| 279 | int 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 Reames | 92756a8 | 2019-02-19 23:07:15 +0000 | [diff] [blame] | 289 | if (MI->getIntrinsicID() == Intrinsic::memset) { |
Philip Reames | 92756a8 | 2019-02-19 23:07:15 +0000 | [diff] [blame] | 290 | if (DL.isNonIntegralPointerType(LoadTy->getScalarType())) { |
Philip Reames | 79d5e16 | 2019-02-20 00:31:28 +0000 | [diff] [blame] | 291 | auto *CI = dyn_cast<ConstantInt>(cast<MemSetInst>(MI)->getValue()); |
Philip Reames | 92756a8 | 2019-02-19 23:07:15 +0000 | [diff] [blame] | 292 | if (!CI || !CI->isZero()) |
| 293 | return -1; |
| 294 | } |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 295 | return analyzeLoadFromClobberingWrite(LoadTy, LoadPtr, MI->getDest(), |
| 296 | MemSizeInBits, DL); |
Philip Reames | 92756a8 | 2019-02-19 23:07:15 +0000 | [diff] [blame] | 297 | } |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 298 | |
| 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 Reames | 79d5e16 | 2019-02-20 00:31:28 +0000 | [diff] [blame] | 318 | // Don't coerce non-integral pointers to integers or vice versa, and the |
| 319 | // memtransfer is implicitly a raw byte code |
Philip Reames | 952d234 | 2019-02-19 23:49:38 +0000 | [diff] [blame] | 320 | if (DL.isNonIntegralPointerType(LoadTy->getScalarType())) |
| 321 | // TODO: Can allow nullptrs from constant zeros |
| 322 | return -1; |
| 323 | |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 324 | 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 Berlin | 12883b1 | 2017-03-20 16:08:29 +0000 | [diff] [blame] | 339 | template <class T, class HelperClass> |
| 340 | static T *getStoreValueForLoadHelper(T *SrcVal, unsigned Offset, Type *LoadTy, |
| 341 | HelperClass &Helper, |
| 342 | const DataLayout &DL) { |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 343 | LLVMContext &Ctx = SrcVal->getType()->getContext(); |
| 344 | |
Keno Fischer | 06f962c | 2017-05-09 21:07:20 +0000 | [diff] [blame] | 345 | // 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 Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 354 | uint64_t StoreSize = (DL.getTypeSizeInBits(SrcVal->getType()) + 7) / 8; |
| 355 | uint64_t LoadSize = (DL.getTypeSizeInBits(LoadTy) + 7) / 8; |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 356 | // Compute which bits of the stored value are being used by the load. Convert |
| 357 | // to an integer type to start with. |
Craig Topper | 95d2347 | 2017-07-09 07:04:00 +0000 | [diff] [blame] | 358 | if (SrcVal->getType()->isPtrOrPtrVectorTy()) |
Daniel Berlin | 12883b1 | 2017-03-20 16:08:29 +0000 | [diff] [blame] | 359 | SrcVal = Helper.CreatePtrToInt(SrcVal, DL.getIntPtrType(SrcVal->getType())); |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 360 | if (!SrcVal->getType()->isIntegerTy()) |
Daniel Berlin | 12883b1 | 2017-03-20 16:08:29 +0000 | [diff] [blame] | 361 | SrcVal = Helper.CreateBitCast(SrcVal, IntegerType::get(Ctx, StoreSize * 8)); |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 362 | |
| 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 Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 369 | if (ShiftAmt) |
Daniel Berlin | 12883b1 | 2017-03-20 16:08:29 +0000 | [diff] [blame] | 370 | SrcVal = Helper.CreateLShr(SrcVal, |
| 371 | ConstantInt::get(SrcVal->getType(), ShiftAmt)); |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 372 | |
| 373 | if (LoadSize != StoreSize) |
Daniel Berlin | 12883b1 | 2017-03-20 16:08:29 +0000 | [diff] [blame] | 374 | SrcVal = Helper.CreateTruncOrBitCast(SrcVal, |
| 375 | IntegerType::get(Ctx, LoadSize * 8)); |
| 376 | return SrcVal; |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 377 | } |
| 378 | |
Daniel Berlin | 12883b1 | 2017-03-20 16:08:29 +0000 | [diff] [blame] | 379 | /// 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. |
| 383 | Value *getStoreValueForLoad(Value *SrcVal, unsigned Offset, Type *LoadTy, |
| 384 | Instruction *InsertPt, const DataLayout &DL) { |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 385 | |
Daniel Berlin | 12883b1 | 2017-03-20 16:08:29 +0000 | [diff] [blame] | 386 | IRBuilder<> Builder(InsertPt); |
| 387 | SrcVal = getStoreValueForLoadHelper(SrcVal, Offset, LoadTy, Builder, DL); |
| 388 | return coerceAvailableValueToLoadTypeHelper(SrcVal, LoadTy, Builder, DL); |
| 389 | } |
| 390 | |
| 391 | Constant *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. |
| 403 | Value *getLoadValueForLoad(LoadInst *SrcVal, unsigned Offset, Type *LoadTy, |
| 404 | Instruction *InsertPt, const DataLayout &DL) { |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 405 | // 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 Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 419 | // 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 Knight | 14359ef | 2019-02-01 20:44:24 +0000 | [diff] [blame] | 423 | Type *DestTy = IntegerType::get(LoadTy->getContext(), NewLoadSize * 8); |
| 424 | Type *DestPTy = |
| 425 | PointerType::get(DestTy, PtrVal->getType()->getPointerAddressSpace()); |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 426 | Builder.SetCurrentDebugLocation(SrcVal->getDebugLoc()); |
| 427 | PtrVal = Builder.CreateBitCast(PtrVal, DestPTy); |
James Y Knight | 14359ef | 2019-02-01 20:44:24 +0000 | [diff] [blame] | 428 | LoadInst *NewLoad = Builder.CreateLoad(DestTy, PtrVal); |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 429 | NewLoad->takeName(SrcVal); |
| 430 | NewLoad->setAlignment(SrcVal->getAlignment()); |
| 431 | |
Nicola Zaghen | d34e60c | 2018-05-14 12:53:11 +0000 | [diff] [blame] | 432 | LLVM_DEBUG(dbgs() << "GVN WIDENED LOAD: " << *SrcVal << "\n"); |
| 433 | LLVM_DEBUG(dbgs() << "TO: " << *NewLoad << "\n"); |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 434 | |
| 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 Berlin | 12883b1 | 2017-03-20 16:08:29 +0000 | [diff] [blame] | 449 | Constant *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 | |
| 458 | template <class T, class HelperClass> |
| 459 | T *getMemInstValueForLoadHelper(MemIntrinsic *SrcInst, unsigned Offset, |
| 460 | Type *LoadTy, HelperClass &Helper, |
| 461 | const DataLayout &DL) { |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 462 | LLVMContext &Ctx = LoadTy->getContext(); |
| 463 | uint64_t LoadSize = DL.getTypeSizeInBits(LoadTy) / 8; |
| 464 | |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 465 | // 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 Berlin | 12883b1 | 2017-03-20 16:08:29 +0000 | [diff] [blame] | 470 | T *Val = cast<T>(MSI->getValue()); |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 471 | if (LoadSize != 1) |
Daniel Berlin | 12883b1 | 2017-03-20 16:08:29 +0000 | [diff] [blame] | 472 | Val = |
| 473 | Helper.CreateZExtOrBitCast(Val, IntegerType::get(Ctx, LoadSize * 8)); |
| 474 | T *OneElt = Val; |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 475 | |
| 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 Berlin | 12883b1 | 2017-03-20 16:08:29 +0000 | [diff] [blame] | 480 | T *ShVal = Helper.CreateShl( |
| 481 | Val, ConstantInt::get(Val->getType(), NumBytesSet * 8)); |
| 482 | Val = Helper.CreateOr(Val, ShVal); |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 483 | NumBytesSet <<= 1; |
| 484 | continue; |
| 485 | } |
| 486 | |
| 487 | // Otherwise insert one byte at a time. |
Daniel Berlin | 12883b1 | 2017-03-20 16:08:29 +0000 | [diff] [blame] | 488 | T *ShVal = Helper.CreateShl(Val, ConstantInt::get(Val->getType(), 1 * 8)); |
| 489 | Val = Helper.CreateOr(OneElt, ShVal); |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 490 | ++NumBytesSet; |
| 491 | } |
| 492 | |
Daniel Berlin | 12883b1 | 2017-03-20 16:08:29 +0000 | [diff] [blame] | 493 | return coerceAvailableValueToLoadTypeHelper(Val, LoadTy, Helper, DL); |
Daniel Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 494 | } |
| 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 Berlin | 12883b1 | 2017-03-20 16:08:29 +0000 | [diff] [blame] | 512 | |
| 513 | /// This function is called when we have a |
| 514 | /// memdep query of a load that ends up being a clobbering mem intrinsic. |
| 515 | Value *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 | |
| 523 | Constant *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 Berlin | 5ac9179 | 2017-03-10 04:54:10 +0000 | [diff] [blame] | 534 | } // namespace VNCoercion |
| 535 | } // namespace llvm |