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 AtomicMemTransferInst *MTI) { 99 return getForSource(cast<AnyMemTransferInst>(MTI)); 100 } 101 102 MemoryLocation MemoryLocation::getForSource(const AnyMemTransferInst *MTI) { 103 assert(MTI->getRawSource() == MTI->getArgOperand(1)); 104 return getForArgument(MTI, 1, nullptr); 105 } 106 107 MemoryLocation MemoryLocation::getForDest(const MemIntrinsic *MI) { 108 return getForDest(cast<AnyMemIntrinsic>(MI)); 109 } 110 111 MemoryLocation MemoryLocation::getForDest(const AtomicMemIntrinsic *MI) { 112 return getForDest(cast<AnyMemIntrinsic>(MI)); 113 } 114 115 MemoryLocation MemoryLocation::getForDest(const AnyMemIntrinsic *MI) { 116 assert(MI->getRawDest() == MI->getArgOperand(0)); 117 return getForArgument(MI, 0, nullptr); 118 } 119 120 std::optional<MemoryLocation> 121 MemoryLocation::getForDest(const CallBase *CB, const TargetLibraryInfo &TLI) { 122 if (!CB->onlyAccessesArgMemory()) 123 return std::nullopt; 124 125 if (CB->hasOperandBundles()) 126 // TODO: remove implementation restriction 127 return std::nullopt; 128 129 Value *UsedV = nullptr; 130 std::optional<unsigned> UsedIdx; 131 for (unsigned i = 0; i < CB->arg_size(); i++) { 132 if (!CB->getArgOperand(i)->getType()->isPointerTy()) 133 continue; 134 if (CB->onlyReadsMemory(i)) 135 continue; 136 if (!UsedV) { 137 // First potentially writing parameter 138 UsedV = CB->getArgOperand(i); 139 UsedIdx = i; 140 continue; 141 } 142 UsedIdx = std::nullopt; 143 if (UsedV != CB->getArgOperand(i)) 144 // Can't describe writing to two distinct locations. 145 // TODO: This results in an inprecision when two values derived from the 146 // same object are passed as arguments to the same function. 147 return std::nullopt; 148 } 149 if (!UsedV) 150 // We don't currently have a way to represent a "does not write" result 151 // and thus have to be conservative and return unknown. 152 return std::nullopt; 153 154 if (UsedIdx) 155 return getForArgument(CB, *UsedIdx, &TLI); 156 return MemoryLocation::getBeforeOrAfter(UsedV, CB->getAAMetadata()); 157 } 158 159 MemoryLocation MemoryLocation::getForArgument(const CallBase *Call, 160 unsigned ArgIdx, 161 const TargetLibraryInfo *TLI) { 162 AAMDNodes AATags = Call->getAAMetadata(); 163 const Value *Arg = Call->getArgOperand(ArgIdx); 164 165 // We may be able to produce an exact size for known intrinsics. 166 if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Call)) { 167 const DataLayout &DL = II->getDataLayout(); 168 169 switch (II->getIntrinsicID()) { 170 default: 171 break; 172 case Intrinsic::memset: 173 case Intrinsic::memcpy: 174 case Intrinsic::memcpy_inline: 175 case Intrinsic::memmove: 176 case Intrinsic::memcpy_element_unordered_atomic: 177 case Intrinsic::memmove_element_unordered_atomic: 178 case Intrinsic::memset_element_unordered_atomic: 179 assert((ArgIdx == 0 || ArgIdx == 1) && 180 "Invalid argument index for memory intrinsic"); 181 if (ConstantInt *LenCI = dyn_cast<ConstantInt>(II->getArgOperand(2))) 182 return MemoryLocation(Arg, LocationSize::precise(LenCI->getZExtValue()), 183 AATags); 184 return MemoryLocation::getAfter(Arg, AATags); 185 186 case Intrinsic::experimental_memset_pattern: 187 assert((ArgIdx == 0 || ArgIdx == 1) && 188 "Invalid argument index for memory intrinsic"); 189 if (ConstantInt *LenCI = dyn_cast<ConstantInt>(II->getArgOperand(2))) 190 return MemoryLocation( 191 Arg, 192 LocationSize::precise( 193 LenCI->getZExtValue() * 194 DL.getTypeAllocSize(II->getArgOperand(1)->getType())), 195 AATags); 196 return MemoryLocation::getAfter(Arg, AATags); 197 198 case Intrinsic::lifetime_start: 199 case Intrinsic::lifetime_end: 200 case Intrinsic::invariant_start: 201 assert(ArgIdx == 1 && "Invalid argument index"); 202 return MemoryLocation( 203 Arg, 204 LocationSize::precise( 205 cast<ConstantInt>(II->getArgOperand(0))->getZExtValue()), 206 AATags); 207 208 case Intrinsic::masked_load: 209 assert(ArgIdx == 0 && "Invalid argument index"); 210 return MemoryLocation( 211 Arg, 212 LocationSize::upperBound(DL.getTypeStoreSize(II->getType())), 213 AATags); 214 215 case Intrinsic::masked_store: 216 assert(ArgIdx == 1 && "Invalid argument index"); 217 return MemoryLocation( 218 Arg, 219 LocationSize::upperBound( 220 DL.getTypeStoreSize(II->getArgOperand(0)->getType())), 221 AATags); 222 223 case Intrinsic::invariant_end: 224 // The first argument to an invariant.end is a "descriptor" type (e.g. a 225 // pointer to a empty struct) which is never actually dereferenced. 226 if (ArgIdx == 0) 227 return MemoryLocation(Arg, LocationSize::precise(0), AATags); 228 assert(ArgIdx == 2 && "Invalid argument index"); 229 return MemoryLocation( 230 Arg, 231 LocationSize::precise( 232 cast<ConstantInt>(II->getArgOperand(1))->getZExtValue()), 233 AATags); 234 235 case Intrinsic::arm_neon_vld1: 236 assert(ArgIdx == 0 && "Invalid argument index"); 237 // LLVM's vld1 and vst1 intrinsics currently only support a single 238 // vector register. 239 return MemoryLocation( 240 Arg, LocationSize::precise(DL.getTypeStoreSize(II->getType())), 241 AATags); 242 243 case Intrinsic::arm_neon_vst1: 244 assert(ArgIdx == 0 && "Invalid argument index"); 245 return MemoryLocation(Arg, 246 LocationSize::precise(DL.getTypeStoreSize( 247 II->getArgOperand(1)->getType())), 248 AATags); 249 } 250 251 assert( 252 !isa<AnyMemTransferInst>(II) && 253 "all memory transfer intrinsics should be handled by the switch above"); 254 } 255 256 // We can bound the aliasing properties of memset_pattern16 just as we can 257 // for memcpy/memset. This is particularly important because the 258 // LoopIdiomRecognizer likes to turn loops into calls to memset_pattern16 259 // whenever possible. 260 LibFunc F; 261 if (TLI && TLI->getLibFunc(*Call, F) && TLI->has(F)) { 262 switch (F) { 263 case LibFunc_strcpy: 264 case LibFunc_strcat: 265 case LibFunc_strncat: 266 assert((ArgIdx == 0 || ArgIdx == 1) && "Invalid argument index for str function"); 267 return MemoryLocation::getAfter(Arg, AATags); 268 269 case LibFunc_memset_chk: 270 assert(ArgIdx == 0 && "Invalid argument index for memset_chk"); 271 [[fallthrough]]; 272 case LibFunc_memcpy_chk: { 273 assert((ArgIdx == 0 || ArgIdx == 1) && 274 "Invalid argument index for memcpy_chk"); 275 LocationSize Size = LocationSize::afterPointer(); 276 if (const auto *Len = dyn_cast<ConstantInt>(Call->getArgOperand(2))) { 277 // memset_chk writes at most Len bytes, memcpy_chk reads/writes at most 278 // Len bytes. They may read/write less, if Len exceeds the specified max 279 // size and aborts. 280 Size = LocationSize::upperBound(Len->getZExtValue()); 281 } 282 return MemoryLocation(Arg, Size, AATags); 283 } 284 case LibFunc_strncpy: { 285 assert((ArgIdx == 0 || ArgIdx == 1) && 286 "Invalid argument index for strncpy"); 287 LocationSize Size = LocationSize::afterPointer(); 288 if (const auto *Len = dyn_cast<ConstantInt>(Call->getArgOperand(2))) { 289 // strncpy is guaranteed to write Len bytes, but only reads up to Len 290 // bytes. 291 Size = ArgIdx == 0 ? LocationSize::precise(Len->getZExtValue()) 292 : LocationSize::upperBound(Len->getZExtValue()); 293 } 294 return MemoryLocation(Arg, Size, AATags); 295 } 296 case LibFunc_memset_pattern16: 297 case LibFunc_memset_pattern4: 298 case LibFunc_memset_pattern8: 299 assert((ArgIdx == 0 || ArgIdx == 1) && 300 "Invalid argument index for memset_pattern16"); 301 if (ArgIdx == 1) { 302 unsigned Size = 16; 303 if (F == LibFunc_memset_pattern4) 304 Size = 4; 305 else if (F == LibFunc_memset_pattern8) 306 Size = 8; 307 return MemoryLocation(Arg, LocationSize::precise(Size), AATags); 308 } 309 if (const ConstantInt *LenCI = 310 dyn_cast<ConstantInt>(Call->getArgOperand(2))) 311 return MemoryLocation(Arg, LocationSize::precise(LenCI->getZExtValue()), 312 AATags); 313 return MemoryLocation::getAfter(Arg, AATags); 314 case LibFunc_bcmp: 315 case LibFunc_memcmp: 316 assert((ArgIdx == 0 || ArgIdx == 1) && 317 "Invalid argument index for memcmp/bcmp"); 318 if (const ConstantInt *LenCI = 319 dyn_cast<ConstantInt>(Call->getArgOperand(2))) 320 return MemoryLocation(Arg, LocationSize::precise(LenCI->getZExtValue()), 321 AATags); 322 return MemoryLocation::getAfter(Arg, AATags); 323 case LibFunc_memchr: 324 assert((ArgIdx == 0) && "Invalid argument index for memchr"); 325 if (const ConstantInt *LenCI = 326 dyn_cast<ConstantInt>(Call->getArgOperand(2))) 327 return MemoryLocation(Arg, LocationSize::precise(LenCI->getZExtValue()), 328 AATags); 329 return MemoryLocation::getAfter(Arg, AATags); 330 case LibFunc_memccpy: 331 assert((ArgIdx == 0 || ArgIdx == 1) && 332 "Invalid argument index for memccpy"); 333 // We only know an upper bound on the number of bytes read/written. 334 if (const ConstantInt *LenCI = 335 dyn_cast<ConstantInt>(Call->getArgOperand(3))) 336 return MemoryLocation( 337 Arg, LocationSize::upperBound(LenCI->getZExtValue()), AATags); 338 return MemoryLocation::getAfter(Arg, AATags); 339 default: 340 break; 341 }; 342 } 343 344 return MemoryLocation::getBeforeOrAfter(Call->getArgOperand(ArgIdx), AATags); 345 } 346