416 lines · cpp
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-exception6//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/PatternMatch.h"16#include "llvm/IR/Type.h"17#include <optional>18using namespace llvm;19 20void LocationSize::print(raw_ostream &OS) const {21 OS << "LocationSize::";22 if (*this == beforeOrAfterPointer())23 OS << "beforeOrAfterPointer";24 else if (*this == afterPointer())25 OS << "afterPointer";26 else if (*this == mapEmpty())27 OS << "mapEmpty";28 else if (*this == mapTombstone())29 OS << "mapTombstone";30 else if (isPrecise())31 OS << "precise(" << getValue() << ')';32 else33 OS << "upperBound(" << getValue() << ')';34}35 36MemoryLocation MemoryLocation::get(const LoadInst *LI) {37 const auto &DL = LI->getDataLayout();38 39 return MemoryLocation(40 LI->getPointerOperand(),41 LocationSize::precise(DL.getTypeStoreSize(LI->getType())),42 LI->getAAMetadata());43}44 45MemoryLocation MemoryLocation::get(const StoreInst *SI) {46 const auto &DL = SI->getDataLayout();47 48 return MemoryLocation(SI->getPointerOperand(),49 LocationSize::precise(DL.getTypeStoreSize(50 SI->getValueOperand()->getType())),51 SI->getAAMetadata());52}53 54MemoryLocation MemoryLocation::get(const VAArgInst *VI) {55 return MemoryLocation(VI->getPointerOperand(),56 LocationSize::afterPointer(), VI->getAAMetadata());57}58 59MemoryLocation MemoryLocation::get(const AtomicCmpXchgInst *CXI) {60 const auto &DL = CXI->getDataLayout();61 62 return MemoryLocation(CXI->getPointerOperand(),63 LocationSize::precise(DL.getTypeStoreSize(64 CXI->getCompareOperand()->getType())),65 CXI->getAAMetadata());66}67 68MemoryLocation MemoryLocation::get(const AtomicRMWInst *RMWI) {69 const auto &DL = RMWI->getDataLayout();70 71 return MemoryLocation(RMWI->getPointerOperand(),72 LocationSize::precise(DL.getTypeStoreSize(73 RMWI->getValOperand()->getType())),74 RMWI->getAAMetadata());75}76 77std::optional<MemoryLocation>78MemoryLocation::getOrNone(const Instruction *Inst) {79 switch (Inst->getOpcode()) {80 case Instruction::Load:81 return get(cast<LoadInst>(Inst));82 case Instruction::Store:83 return get(cast<StoreInst>(Inst));84 case Instruction::VAArg:85 return get(cast<VAArgInst>(Inst));86 case Instruction::AtomicCmpXchg:87 return get(cast<AtomicCmpXchgInst>(Inst));88 case Instruction::AtomicRMW:89 return get(cast<AtomicRMWInst>(Inst));90 default:91 return std::nullopt;92 }93}94 95MemoryLocation MemoryLocation::getForSource(const MemTransferInst *MTI) {96 return getForSource(cast<AnyMemTransferInst>(MTI));97}98 99MemoryLocation MemoryLocation::getForSource(const AnyMemTransferInst *MTI) {100 assert(MTI->getRawSource() == MTI->getArgOperand(1));101 return getForArgument(MTI, 1, nullptr);102}103 104MemoryLocation MemoryLocation::getForDest(const MemIntrinsic *MI) {105 return getForDest(cast<AnyMemIntrinsic>(MI));106}107 108MemoryLocation MemoryLocation::getForDest(const AnyMemIntrinsic *MI) {109 assert(MI->getRawDest() == MI->getArgOperand(0));110 return getForArgument(MI, 0, nullptr);111}112 113std::optional<MemoryLocation>114MemoryLocation::getForDest(const CallBase *CB, const TargetLibraryInfo &TLI) {115 // Check that the only possible writes are to arguments.116 MemoryEffects WriteME = CB->getMemoryEffects() & MemoryEffects::writeOnly();117 if (!WriteME.onlyAccessesArgPointees())118 return std::nullopt;119 120 if (CB->hasOperandBundles())121 // TODO: remove implementation restriction122 return std::nullopt;123 124 Value *UsedV = nullptr;125 std::optional<unsigned> UsedIdx;126 for (unsigned i = 0; i < CB->arg_size(); i++) {127 if (!CB->getArgOperand(i)->getType()->isPointerTy())128 continue;129 if (CB->onlyReadsMemory(i))130 continue;131 if (!UsedV) {132 // First potentially writing parameter133 UsedV = CB->getArgOperand(i);134 UsedIdx = i;135 continue;136 }137 UsedIdx = std::nullopt;138 if (UsedV != CB->getArgOperand(i))139 // Can't describe writing to two distinct locations.140 // TODO: This results in an inprecision when two values derived from the141 // same object are passed as arguments to the same function.142 return std::nullopt;143 }144 if (!UsedV)145 // We don't currently have a way to represent a "does not write" result146 // and thus have to be conservative and return unknown.147 return std::nullopt;148 149 if (UsedIdx)150 return getForArgument(CB, *UsedIdx, &TLI);151 return MemoryLocation::getBeforeOrAfter(UsedV, CB->getAAMetadata());152}153 154// If the mask for a memory op is a get active lane mask intrinsic155// we can possibly infer the size of memory written or read156static std::optional<FixedVectorType *>157getKnownTypeFromMaskedOp(Value *Mask, VectorType *Ty) {158 using namespace llvm::PatternMatch;159 ConstantInt *Op0, *Op1;160 if (!match(Mask, m_Intrinsic<Intrinsic::get_active_lane_mask>(161 m_ConstantInt(Op0), m_ConstantInt(Op1))))162 return std::nullopt;163 164 APInt LaneMaskLo = Op0->getValue();165 APInt LaneMaskHi = Op1->getValue();166 if (LaneMaskHi.ule(LaneMaskLo))167 return std::nullopt;168 169 APInt NumElts = LaneMaskHi - LaneMaskLo;170 if (NumElts.ugt(Ty->getElementCount().getKnownMinValue())) {171 if (isa<ScalableVectorType>(Ty))172 return std::nullopt;173 // Unlike scalable vectors, fixed vector types are guaranteed to handle the174 // KnownMinValue and can be clamped175 NumElts = Ty->getElementCount().getKnownMinValue();176 }177 178 return FixedVectorType::get(Ty->getElementType(), NumElts.getZExtValue());179}180 181MemoryLocation MemoryLocation::getForArgument(const CallBase *Call,182 unsigned ArgIdx,183 const TargetLibraryInfo *TLI) {184 AAMDNodes AATags = Call->getAAMetadata();185 const Value *Arg = Call->getArgOperand(ArgIdx);186 187 // We may be able to produce an exact size for known intrinsics.188 if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Call)) {189 const DataLayout &DL = II->getDataLayout();190 191 switch (II->getIntrinsicID()) {192 default:193 break;194 case Intrinsic::memset:195 case Intrinsic::memcpy:196 case Intrinsic::memcpy_inline:197 case Intrinsic::memmove:198 case Intrinsic::memcpy_element_unordered_atomic:199 case Intrinsic::memmove_element_unordered_atomic:200 case Intrinsic::memset_element_unordered_atomic:201 assert((ArgIdx == 0 || ArgIdx == 1) &&202 "Invalid argument index for memory intrinsic");203 if (ConstantInt *LenCI = dyn_cast<ConstantInt>(II->getArgOperand(2)))204 return MemoryLocation(Arg, LocationSize::precise(LenCI->getZExtValue()),205 AATags);206 return MemoryLocation::getAfter(Arg, AATags);207 208 case Intrinsic::experimental_memset_pattern:209 assert((ArgIdx == 0 || ArgIdx == 1) &&210 "Invalid argument index for memory intrinsic");211 if (ConstantInt *LenCI = dyn_cast<ConstantInt>(II->getArgOperand(2)))212 return MemoryLocation(213 Arg,214 LocationSize::precise(215 LenCI->getZExtValue() *216 DL.getTypeAllocSize(II->getArgOperand(1)->getType())),217 AATags);218 return MemoryLocation::getAfter(Arg, AATags);219 220 case Intrinsic::lifetime_start:221 case Intrinsic::lifetime_end: {222 assert(ArgIdx == 0 && "Invalid argument index");223 auto *AI = dyn_cast<AllocaInst>(Arg);224 if (!AI)225 // lifetime of poison value.226 return MemoryLocation::getBeforeOrAfter(Arg);227 228 std::optional<TypeSize> AllocSize =229 AI->getAllocationSize(II->getDataLayout());230 return MemoryLocation(Arg,231 AllocSize ? LocationSize::precise(*AllocSize)232 : LocationSize::afterPointer(),233 AATags);234 }235 236 case Intrinsic::invariant_start:237 assert(ArgIdx == 1 && "Invalid argument index");238 return MemoryLocation(239 Arg,240 LocationSize::precise(241 cast<ConstantInt>(II->getArgOperand(0))->getZExtValue()),242 AATags);243 244 case Intrinsic::masked_load: {245 assert(ArgIdx == 0 && "Invalid argument index");246 247 auto *Ty = cast<VectorType>(II->getType());248 if (auto KnownType = getKnownTypeFromMaskedOp(II->getOperand(1), Ty))249 return MemoryLocation(Arg, DL.getTypeStoreSize(*KnownType), AATags);250 251 return MemoryLocation(252 Arg, LocationSize::upperBound(DL.getTypeStoreSize(Ty)), AATags);253 }254 case Intrinsic::masked_store: {255 assert(ArgIdx == 1 && "Invalid argument index");256 257 auto *Ty = cast<VectorType>(II->getArgOperand(0)->getType());258 if (auto KnownType = getKnownTypeFromMaskedOp(II->getOperand(2), Ty))259 return MemoryLocation(Arg, DL.getTypeStoreSize(*KnownType), AATags);260 261 return MemoryLocation(262 Arg, LocationSize::upperBound(DL.getTypeStoreSize(Ty)), AATags);263 }264 265 case Intrinsic::invariant_end:266 // The first argument to an invariant.end is a "descriptor" type (e.g. a267 // pointer to a empty struct) which is never actually dereferenced.268 if (ArgIdx == 0)269 return MemoryLocation(Arg, LocationSize::precise(0), AATags);270 assert(ArgIdx == 2 && "Invalid argument index");271 return MemoryLocation(272 Arg,273 LocationSize::precise(274 cast<ConstantInt>(II->getArgOperand(1))->getZExtValue()),275 AATags);276 277 case Intrinsic::arm_neon_vld1:278 assert(ArgIdx == 0 && "Invalid argument index");279 // LLVM's vld1 and vst1 intrinsics currently only support a single280 // vector register.281 return MemoryLocation(282 Arg, LocationSize::precise(DL.getTypeStoreSize(II->getType())),283 AATags);284 285 case Intrinsic::arm_neon_vst1:286 assert(ArgIdx == 0 && "Invalid argument index");287 return MemoryLocation(Arg,288 LocationSize::precise(DL.getTypeStoreSize(289 II->getArgOperand(1)->getType())),290 AATags);291 case Intrinsic::matrix_column_major_load:292 case Intrinsic::matrix_column_major_store: {293 bool IsLoad = II->getIntrinsicID() == Intrinsic::matrix_column_major_load;294 assert(ArgIdx == (IsLoad ? 0 : 1) && "Invalid argument index");295 296 auto *Stride = dyn_cast<ConstantInt>(II->getArgOperand(IsLoad ? 1 : 2));297 uint64_t Rows =298 cast<ConstantInt>(II->getArgOperand(IsLoad ? 3 : 4))->getZExtValue();299 uint64_t Cols =300 cast<ConstantInt>(II->getArgOperand(IsLoad ? 4 : 5))->getZExtValue();301 302 // The stride is dynamic, so there's nothing we can say.303 if (!Stride)304 return MemoryLocation(Arg, LocationSize::afterPointer(), AATags);305 306 uint64_t ConstStride = Stride->getZExtValue();307 auto *VT = cast<VectorType>(IsLoad ? II->getType()308 : II->getArgOperand(0)->getType());309 assert(Cols != 0 && "Matrix cannot have 0 columns");310 TypeSize Size = DL.getTypeAllocSize(VT->getScalarType()) *311 (ConstStride * (Cols - 1) + Rows);312 313 // In the unstrided case, we have a precise size, ...314 if (ConstStride == Rows)315 return MemoryLocation(Arg, LocationSize::precise(Size), AATags);316 // otherwise we merely obtain an upper bound.317 return MemoryLocation(Arg, LocationSize::upperBound(Size), AATags);318 }319 }320 321 assert(322 !isa<AnyMemTransferInst>(II) &&323 "all memory transfer intrinsics should be handled by the switch above");324 }325 326 // We can bound the aliasing properties of memset_pattern16 just as we can327 // for memcpy/memset. This is particularly important because the328 // LoopIdiomRecognizer likes to turn loops into calls to memset_pattern16329 // whenever possible.330 LibFunc F;331 if (TLI && TLI->getLibFunc(*Call, F) && TLI->has(F)) {332 switch (F) {333 case LibFunc_strcpy:334 case LibFunc_strcat:335 case LibFunc_strncat:336 assert((ArgIdx == 0 || ArgIdx == 1) && "Invalid argument index for str function");337 return MemoryLocation::getAfter(Arg, AATags);338 339 case LibFunc_memset_chk:340 assert(ArgIdx == 0 && "Invalid argument index for memset_chk");341 [[fallthrough]];342 case LibFunc_memcpy_chk: {343 assert((ArgIdx == 0 || ArgIdx == 1) &&344 "Invalid argument index for memcpy_chk");345 LocationSize Size = LocationSize::afterPointer();346 if (const auto *Len = dyn_cast<ConstantInt>(Call->getArgOperand(2))) {347 // memset_chk writes at most Len bytes, memcpy_chk reads/writes at most348 // Len bytes. They may read/write less, if Len exceeds the specified max349 // size and aborts.350 Size = LocationSize::upperBound(Len->getZExtValue());351 }352 return MemoryLocation(Arg, Size, AATags);353 }354 case LibFunc_strncpy: {355 assert((ArgIdx == 0 || ArgIdx == 1) &&356 "Invalid argument index for strncpy");357 LocationSize Size = LocationSize::afterPointer();358 if (const auto *Len = dyn_cast<ConstantInt>(Call->getArgOperand(2))) {359 // strncpy is guaranteed to write Len bytes, but only reads up to Len360 // bytes.361 Size = ArgIdx == 0 ? LocationSize::precise(Len->getZExtValue())362 : LocationSize::upperBound(Len->getZExtValue());363 }364 return MemoryLocation(Arg, Size, AATags);365 }366 case LibFunc_memset_pattern16:367 case LibFunc_memset_pattern4:368 case LibFunc_memset_pattern8:369 assert((ArgIdx == 0 || ArgIdx == 1) &&370 "Invalid argument index for memset_pattern16");371 if (ArgIdx == 1) {372 unsigned Size = 16;373 if (F == LibFunc_memset_pattern4)374 Size = 4;375 else if (F == LibFunc_memset_pattern8)376 Size = 8;377 return MemoryLocation(Arg, LocationSize::precise(Size), AATags);378 }379 if (const ConstantInt *LenCI =380 dyn_cast<ConstantInt>(Call->getArgOperand(2)))381 return MemoryLocation(Arg, LocationSize::precise(LenCI->getZExtValue()),382 AATags);383 return MemoryLocation::getAfter(Arg, AATags);384 case LibFunc_bcmp:385 case LibFunc_memcmp:386 assert((ArgIdx == 0 || ArgIdx == 1) &&387 "Invalid argument index for memcmp/bcmp");388 if (const ConstantInt *LenCI =389 dyn_cast<ConstantInt>(Call->getArgOperand(2)))390 return MemoryLocation(Arg, LocationSize::precise(LenCI->getZExtValue()),391 AATags);392 return MemoryLocation::getAfter(Arg, AATags);393 case LibFunc_memchr:394 assert((ArgIdx == 0) && "Invalid argument index for memchr");395 if (const ConstantInt *LenCI =396 dyn_cast<ConstantInt>(Call->getArgOperand(2)))397 return MemoryLocation(Arg, LocationSize::precise(LenCI->getZExtValue()),398 AATags);399 return MemoryLocation::getAfter(Arg, AATags);400 case LibFunc_memccpy:401 assert((ArgIdx == 0 || ArgIdx == 1) &&402 "Invalid argument index for memccpy");403 // We only know an upper bound on the number of bytes read/written.404 if (const ConstantInt *LenCI =405 dyn_cast<ConstantInt>(Call->getArgOperand(3)))406 return MemoryLocation(407 Arg, LocationSize::upperBound(LenCI->getZExtValue()), AATags);408 return MemoryLocation::getAfter(Arg, AATags);409 default:410 break;411 };412 }413 414 return MemoryLocation::getBeforeOrAfter(Call->getArgOperand(ArgIdx), AATags);415}416