1 //===- MemoryLocation.cpp - Memory location descriptions -------------------==// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include "llvm/Analysis/MemoryLocation.h" 10 #include "llvm/Analysis/TargetLibraryInfo.h" 11 #include "llvm/IR/DataLayout.h" 12 #include "llvm/IR/Instructions.h" 13 #include "llvm/IR/IntrinsicInst.h" 14 #include "llvm/IR/IntrinsicsARM.h" 15 #include "llvm/IR/Type.h" 16 #include <optional> 17 using namespace llvm; 18 19 void LocationSize::print(raw_ostream &OS) const { 20 OS << "LocationSize::"; 21 if (*this == beforeOrAfterPointer()) 22 OS << "beforeOrAfterPointer"; 23 else if (*this == afterPointer()) 24 OS << "afterPointer"; 25 else if (*this == mapEmpty()) 26 OS << "mapEmpty"; 27 else if (*this == mapTombstone()) 28 OS << "mapTombstone"; 29 else if (isPrecise()) 30 OS << "precise(" << getValue() << ')'; 31 else 32 OS << "upperBound(" << getValue() << ')'; 33 } 34 35 MemoryLocation MemoryLocation::get(const LoadInst *LI) { 36 const auto &DL = LI->getDataLayout(); 37 38 return MemoryLocation( 39 LI->getPointerOperand(), 40 LocationSize::precise(DL.getTypeStoreSize(LI->getType())), 41 LI->getAAMetadata()); 42 } 43 44 MemoryLocation MemoryLocation::get(const StoreInst *SI) { 45 const auto &DL = SI->getDataLayout(); 46 47 return MemoryLocation(SI->getPointerOperand(), 48 LocationSize::precise(DL.getTypeStoreSize( 49 SI->getValueOperand()->getType())), 50 SI->getAAMetadata()); 51 } 52 53 MemoryLocation MemoryLocation::get(const VAArgInst *VI) { 54 return MemoryLocation(VI->getPointerOperand(), 55 LocationSize::afterPointer(), VI->getAAMetadata()); 56 } 57 58 MemoryLocation MemoryLocation::get(const AtomicCmpXchgInst *CXI) { 59 const auto &DL = CXI->getDataLayout(); 60 61 return MemoryLocation(CXI->getPointerOperand(), 62 LocationSize::precise(DL.getTypeStoreSize( 63 CXI->getCompareOperand()->getType())), 64 CXI->getAAMetadata()); 65 } 66 67 MemoryLocation MemoryLocation::get(const AtomicRMWInst *RMWI) { 68 const auto &DL = RMWI->getDataLayout(); 69 70 return MemoryLocation(RMWI->getPointerOperand(), 71 LocationSize::precise(DL.getTypeStoreSize( 72 RMWI->getValOperand()->getType())), 73 RMWI->getAAMetadata()); 74 } 75 76 std::optional<MemoryLocation> 77 MemoryLocation::getOrNone(const Instruction *Inst) { 78 switch (Inst->getOpcode()) { 79 case Instruction::Load: 80 return get(cast<LoadInst>(Inst)); 81 case Instruction::Store: 82 return get(cast<StoreInst>(Inst)); 83 case Instruction::VAArg: 84 return get(cast<VAArgInst>(Inst)); 85 case Instruction::AtomicCmpXchg: 86 return get(cast<AtomicCmpXchgInst>(Inst)); 87 case Instruction::AtomicRMW: 88 return get(cast<AtomicRMWInst>(Inst)); 89 default: 90 return std::nullopt; 91 } 92 } 93 94 MemoryLocation MemoryLocation::getForSource(const MemTransferInst *MTI) { 95 return getForSource(cast<AnyMemTransferInst>(MTI)); 96 } 97 98 MemoryLocation MemoryLocation::getForSource(const AnyMemTransferInst *MTI) { 99 assert(MTI->getRawSource() == MTI->getArgOperand(1)); 100 return getForArgument(MTI, 1, nullptr); 101 } 102 103 MemoryLocation MemoryLocation::getForDest(const MemIntrinsic *MI) { 104 return getForDest(cast<AnyMemIntrinsic>(MI)); 105 } 106 107 MemoryLocation MemoryLocation::getForDest(const AnyMemIntrinsic *MI) { 108 assert(MI->getRawDest() == MI->getArgOperand(0)); 109 return getForArgument(MI, 0, nullptr); 110 } 111 112 std::optional<MemoryLocation> 113 MemoryLocation::getForDest(const CallBase *CB, const TargetLibraryInfo &TLI) { 114 // Check that the only possible writes are to arguments. 115 MemoryEffects WriteME = CB->getMemoryEffects() & MemoryEffects::writeOnly(); 116 if (!WriteME.onlyAccessesArgPointees()) 117 return std::nullopt; 118 119 if (CB->hasOperandBundles()) 120 // TODO: remove implementation restriction 121 return std::nullopt; 122 123 Value *UsedV = nullptr; 124 std::optional<unsigned> UsedIdx; 125 for (unsigned i = 0; i < CB->arg_size(); i++) { 126 if (!CB->getArgOperand(i)->getType()->isPointerTy()) 127 continue; 128 if (CB->onlyReadsMemory(i)) 129 continue; 130 if (!UsedV) { 131 // First potentially writing parameter 132 UsedV = CB->getArgOperand(i); 133 UsedIdx = i; 134 continue; 135 } 136 UsedIdx = std::nullopt; 137 if (UsedV != CB->getArgOperand(i)) 138 // Can't describe writing to two distinct locations. 139 // TODO: This results in an inprecision when two values derived from the 140 // same object are passed as arguments to the same function. 141 return std::nullopt; 142 } 143 if (!UsedV) 144 // We don't currently have a way to represent a "does not write" result 145 // and thus have to be conservative and return unknown. 146 return std::nullopt; 147 148 if (UsedIdx) 149 return getForArgument(CB, *UsedIdx, &TLI); 150 return MemoryLocation::getBeforeOrAfter(UsedV, CB->getAAMetadata()); 151 } 152 153 MemoryLocation MemoryLocation::getForArgument(const CallBase *Call, 154 unsigned ArgIdx, 155 const TargetLibraryInfo *TLI) { 156 AAMDNodes AATags = Call->getAAMetadata(); 157 const Value *Arg = Call->getArgOperand(ArgIdx); 158 159 // We may be able to produce an exact size for known intrinsics. 160 if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Call)) { 161 const DataLayout &DL = II->getDataLayout(); 162 163 switch (II->getIntrinsicID()) { 164 default: 165 break; 166 case Intrinsic::memset: 167 case Intrinsic::memcpy: 168 case Intrinsic::memcpy_inline: 169 case Intrinsic::memmove: 170 case Intrinsic::memcpy_element_unordered_atomic: 171 case Intrinsic::memmove_element_unordered_atomic: 172 case Intrinsic::memset_element_unordered_atomic: 173 assert((ArgIdx == 0 || ArgIdx == 1) && 174 "Invalid argument index for memory intrinsic"); 175 if (ConstantInt *LenCI = dyn_cast<ConstantInt>(II->getArgOperand(2))) 176 return MemoryLocation(Arg, LocationSize::precise(LenCI->getZExtValue()), 177 AATags); 178 return MemoryLocation::getAfter(Arg, AATags); 179 180 case Intrinsic::experimental_memset_pattern: 181 assert((ArgIdx == 0 || ArgIdx == 1) && 182 "Invalid argument index for memory intrinsic"); 183 if (ConstantInt *LenCI = dyn_cast<ConstantInt>(II->getArgOperand(2))) 184 return MemoryLocation( 185 Arg, 186 LocationSize::precise( 187 LenCI->getZExtValue() * 188 DL.getTypeAllocSize(II->getArgOperand(1)->getType())), 189 AATags); 190 return MemoryLocation::getAfter(Arg, AATags); 191 192 case Intrinsic::lifetime_start: 193 case Intrinsic::lifetime_end: 194 case Intrinsic::invariant_start: 195 assert(ArgIdx == 1 && "Invalid argument index"); 196 return MemoryLocation( 197 Arg, 198 LocationSize::precise( 199 cast<ConstantInt>(II->getArgOperand(0))->getZExtValue()), 200 AATags); 201 202 case Intrinsic::masked_load: 203 assert(ArgIdx == 0 && "Invalid argument index"); 204 return MemoryLocation( 205 Arg, 206 LocationSize::upperBound(DL.getTypeStoreSize(II->getType())), 207 AATags); 208 209 case Intrinsic::masked_store: 210 assert(ArgIdx == 1 && "Invalid argument index"); 211 return MemoryLocation( 212 Arg, 213 LocationSize::upperBound( 214 DL.getTypeStoreSize(II->getArgOperand(0)->getType())), 215 AATags); 216 217 case Intrinsic::invariant_end: 218 // The first argument to an invariant.end is a "descriptor" type (e.g. a 219 // pointer to a empty struct) which is never actually dereferenced. 220 if (ArgIdx == 0) 221 return MemoryLocation(Arg, LocationSize::precise(0), AATags); 222 assert(ArgIdx == 2 && "Invalid argument index"); 223 return MemoryLocation( 224 Arg, 225 LocationSize::precise( 226 cast<ConstantInt>(II->getArgOperand(1))->getZExtValue()), 227 AATags); 228 229 case Intrinsic::arm_neon_vld1: 230 assert(ArgIdx == 0 && "Invalid argument index"); 231 // LLVM's vld1 and vst1 intrinsics currently only support a single 232 // vector register. 233 return MemoryLocation( 234 Arg, LocationSize::precise(DL.getTypeStoreSize(II->getType())), 235 AATags); 236 237 case Intrinsic::arm_neon_vst1: 238 assert(ArgIdx == 0 && "Invalid argument index"); 239 return MemoryLocation(Arg, 240 LocationSize::precise(DL.getTypeStoreSize( 241 II->getArgOperand(1)->getType())), 242 AATags); 243 } 244 245 assert( 246 !isa<AnyMemTransferInst>(II) && 247 "all memory transfer intrinsics should be handled by the switch above"); 248 } 249 250 // We can bound the aliasing properties of memset_pattern16 just as we can 251 // for memcpy/memset. This is particularly important because the 252 // LoopIdiomRecognizer likes to turn loops into calls to memset_pattern16 253 // whenever possible. 254 LibFunc F; 255 if (TLI && TLI->getLibFunc(*Call, F) && TLI->has(F)) { 256 switch (F) { 257 case LibFunc_strcpy: 258 case LibFunc_strcat: 259 case LibFunc_strncat: 260 assert((ArgIdx == 0 || ArgIdx == 1) && "Invalid argument index for str function"); 261 return MemoryLocation::getAfter(Arg, AATags); 262 263 case LibFunc_memset_chk: 264 assert(ArgIdx == 0 && "Invalid argument index for memset_chk"); 265 [[fallthrough]]; 266 case LibFunc_memcpy_chk: { 267 assert((ArgIdx == 0 || ArgIdx == 1) && 268 "Invalid argument index for memcpy_chk"); 269 LocationSize Size = LocationSize::afterPointer(); 270 if (const auto *Len = dyn_cast<ConstantInt>(Call->getArgOperand(2))) { 271 // memset_chk writes at most Len bytes, memcpy_chk reads/writes at most 272 // Len bytes. They may read/write less, if Len exceeds the specified max 273 // size and aborts. 274 Size = LocationSize::upperBound(Len->getZExtValue()); 275 } 276 return MemoryLocation(Arg, Size, AATags); 277 } 278 case LibFunc_strncpy: { 279 assert((ArgIdx == 0 || ArgIdx == 1) && 280 "Invalid argument index for strncpy"); 281 LocationSize Size = LocationSize::afterPointer(); 282 if (const auto *Len = dyn_cast<ConstantInt>(Call->getArgOperand(2))) { 283 // strncpy is guaranteed to write Len bytes, but only reads up to Len 284 // bytes. 285 Size = ArgIdx == 0 ? LocationSize::precise(Len->getZExtValue()) 286 : LocationSize::upperBound(Len->getZExtValue()); 287 } 288 return MemoryLocation(Arg, Size, AATags); 289 } 290 case LibFunc_memset_pattern16: 291 case LibFunc_memset_pattern4: 292 case LibFunc_memset_pattern8: 293 assert((ArgIdx == 0 || ArgIdx == 1) && 294 "Invalid argument index for memset_pattern16"); 295 if (ArgIdx == 1) { 296 unsigned Size = 16; 297 if (F == LibFunc_memset_pattern4) 298 Size = 4; 299 else if (F == LibFunc_memset_pattern8) 300 Size = 8; 301 return MemoryLocation(Arg, LocationSize::precise(Size), AATags); 302 } 303 if (const ConstantInt *LenCI = 304 dyn_cast<ConstantInt>(Call->getArgOperand(2))) 305 return MemoryLocation(Arg, LocationSize::precise(LenCI->getZExtValue()), 306 AATags); 307 return MemoryLocation::getAfter(Arg, AATags); 308 case LibFunc_bcmp: 309 case LibFunc_memcmp: 310 assert((ArgIdx == 0 || ArgIdx == 1) && 311 "Invalid argument index for memcmp/bcmp"); 312 if (const ConstantInt *LenCI = 313 dyn_cast<ConstantInt>(Call->getArgOperand(2))) 314 return MemoryLocation(Arg, LocationSize::precise(LenCI->getZExtValue()), 315 AATags); 316 return MemoryLocation::getAfter(Arg, AATags); 317 case LibFunc_memchr: 318 assert((ArgIdx == 0) && "Invalid argument index for memchr"); 319 if (const ConstantInt *LenCI = 320 dyn_cast<ConstantInt>(Call->getArgOperand(2))) 321 return MemoryLocation(Arg, LocationSize::precise(LenCI->getZExtValue()), 322 AATags); 323 return MemoryLocation::getAfter(Arg, AATags); 324 case LibFunc_memccpy: 325 assert((ArgIdx == 0 || ArgIdx == 1) && 326 "Invalid argument index for memccpy"); 327 // We only know an upper bound on the number of bytes read/written. 328 if (const ConstantInt *LenCI = 329 dyn_cast<ConstantInt>(Call->getArgOperand(3))) 330 return MemoryLocation( 331 Arg, LocationSize::upperBound(LenCI->getZExtValue()), AATags); 332 return MemoryLocation::getAfter(Arg, AATags); 333 default: 334 break; 335 }; 336 } 337 338 return MemoryLocation::getBeforeOrAfter(Call->getArgOperand(ArgIdx), AATags); 339 } 340