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/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 else
33 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(Value: DL.getTypeStoreSize(Ty: 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(Value: DL.getTypeStoreSize(
50 Ty: 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(Value: DL.getTypeStoreSize(
64 Ty: 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(Value: DL.getTypeStoreSize(
73 Ty: 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(LI: cast<LoadInst>(Val: Inst));
82 case Instruction::Store:
83 return get(SI: cast<StoreInst>(Val: Inst));
84 case Instruction::VAArg:
85 return get(VI: cast<VAArgInst>(Val: Inst));
86 case Instruction::AtomicCmpXchg:
87 return get(CXI: cast<AtomicCmpXchgInst>(Val: Inst));
88 case Instruction::AtomicRMW:
89 return get(RMWI: cast<AtomicRMWInst>(Val: Inst));
90 default:
91 return std::nullopt;
92 }
93}
94
95MemoryLocation MemoryLocation::getForSource(const MemTransferInst *MTI) {
96 return getForSource(MTI: cast<AnyMemTransferInst>(Val: MTI));
97}
98
99MemoryLocation MemoryLocation::getForSource(const AnyMemTransferInst *MTI) {
100 assert(MTI->getRawSource() == MTI->getArgOperand(1));
101 return getForArgument(Call: MTI, ArgIdx: 1, TLI: nullptr);
102}
103
104MemoryLocation MemoryLocation::getForDest(const MemIntrinsic *MI) {
105 return getForDest(MI: cast<AnyMemIntrinsic>(Val: MI));
106}
107
108MemoryLocation MemoryLocation::getForDest(const AnyMemIntrinsic *MI) {
109 assert(MI->getRawDest() == MI->getArgOperand(0));
110 return getForArgument(Call: MI, ArgIdx: 0, TLI: 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 restriction
122 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(OpNo: i))
130 continue;
131 if (!UsedV) {
132 // First potentially writing parameter
133 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 the
141 // 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" result
146 // and thus have to be conservative and return unknown.
147 return std::nullopt;
148
149 if (UsedIdx)
150 return getForArgument(Call: CB, ArgIdx: *UsedIdx, TLI: &TLI);
151 return MemoryLocation::getBeforeOrAfter(Ptr: UsedV, AATags: CB->getAAMetadata());
152}
153
154// If the mask for a memory op is a get active lane mask intrinsic
155// we can possibly infer the size of memory written or read
156static std::optional<FixedVectorType *>
157getKnownTypeFromMaskedOp(Value *Mask, VectorType *Ty) {
158 using namespace llvm::PatternMatch;
159 ConstantInt *Op0, *Op1;
160 if (!match(V: Mask, P: m_Intrinsic<Intrinsic::get_active_lane_mask>(
161 Op0: m_ConstantInt(CI&: Op0), Op1: m_ConstantInt(CI&: Op1))))
162 return std::nullopt;
163
164 APInt LaneMaskLo = Op0->getValue();
165 APInt LaneMaskHi = Op1->getValue();
166 if (LaneMaskHi.ule(RHS: LaneMaskLo))
167 return std::nullopt;
168
169 APInt NumElts = LaneMaskHi - LaneMaskLo;
170 if (NumElts.ugt(RHS: Ty->getElementCount().getKnownMinValue())) {
171 if (isa<ScalableVectorType>(Val: Ty))
172 return std::nullopt;
173 // Unlike scalable vectors, fixed vector types are guaranteed to handle the
174 // KnownMinValue and can be clamped
175 NumElts = Ty->getElementCount().getKnownMinValue();
176 }
177
178 return FixedVectorType::get(ElementType: Ty->getElementType(), NumElts: 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(i: ArgIdx);
186
187 // We may be able to produce an exact size for known intrinsics.
188 if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Val: 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>(Val: II->getArgOperand(i: 2)))
204 return MemoryLocation(Arg, LocationSize::precise(Value: LenCI->getZExtValue()),
205 AATags);
206 return MemoryLocation::getAfter(Ptr: 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>(Val: II->getArgOperand(i: 2)))
212 return MemoryLocation(
213 Arg,
214 LocationSize::precise(
215 Value: LenCI->getZExtValue() *
216 DL.getTypeAllocSize(Ty: II->getArgOperand(i: 1)->getType())),
217 AATags);
218 return MemoryLocation::getAfter(Ptr: 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>(Val: Arg);
224 if (!AI)
225 // lifetime of poison value.
226 return MemoryLocation::getBeforeOrAfter(Ptr: Arg);
227
228 std::optional<TypeSize> AllocSize =
229 AI->getAllocationSize(DL: II->getDataLayout());
230 return MemoryLocation(Arg,
231 AllocSize ? LocationSize::precise(Value: *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 Value: cast<ConstantInt>(Val: II->getArgOperand(i: 0))->getZExtValue()),
242 AATags);
243
244 case Intrinsic::masked_load: {
245 assert(ArgIdx == 0 && "Invalid argument index");
246
247 auto *Ty = cast<VectorType>(Val: II->getType());
248 if (auto KnownType = getKnownTypeFromMaskedOp(Mask: II->getOperand(i_nocapture: 1), Ty))
249 return MemoryLocation(Arg, DL.getTypeStoreSize(Ty: *KnownType), AATags);
250
251 return MemoryLocation(
252 Arg, LocationSize::upperBound(Value: DL.getTypeStoreSize(Ty)), AATags);
253 }
254 case Intrinsic::masked_store: {
255 assert(ArgIdx == 1 && "Invalid argument index");
256
257 auto *Ty = cast<VectorType>(Val: II->getArgOperand(i: 0)->getType());
258 if (auto KnownType = getKnownTypeFromMaskedOp(Mask: II->getOperand(i_nocapture: 2), Ty))
259 return MemoryLocation(Arg, DL.getTypeStoreSize(Ty: *KnownType), AATags);
260
261 return MemoryLocation(
262 Arg, LocationSize::upperBound(Value: 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. a
267 // pointer to a empty struct) which is never actually dereferenced.
268 if (ArgIdx == 0)
269 return MemoryLocation(Arg, LocationSize::precise(Value: 0), AATags);
270 assert(ArgIdx == 2 && "Invalid argument index");
271 return MemoryLocation(
272 Arg,
273 LocationSize::precise(
274 Value: cast<ConstantInt>(Val: II->getArgOperand(i: 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 single
280 // vector register.
281 return MemoryLocation(
282 Arg, LocationSize::precise(Value: DL.getTypeStoreSize(Ty: 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(Value: DL.getTypeStoreSize(
289 Ty: II->getArgOperand(i: 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>(Val: II->getArgOperand(i: IsLoad ? 1 : 2));
297 uint64_t Rows =
298 cast<ConstantInt>(Val: II->getArgOperand(i: IsLoad ? 3 : 4))->getZExtValue();
299 uint64_t Cols =
300 cast<ConstantInt>(Val: II->getArgOperand(i: 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>(Val: IsLoad ? II->getType()
308 : II->getArgOperand(i: 0)->getType());
309 assert(Cols != 0 && "Matrix cannot have 0 columns");
310 TypeSize Size = DL.getTypeAllocSize(Ty: 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(Value: Size), AATags);
316 // otherwise we merely obtain an upper bound.
317 return MemoryLocation(Arg, LocationSize::upperBound(Value: 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 can
327 // for memcpy/memset. This is particularly important because the
328 // LoopIdiomRecognizer likes to turn loops into calls to memset_pattern16
329 // whenever possible.
330 LibFunc F;
331 if (TLI && TLI->getLibFunc(CB: *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(Ptr: 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>(Val: Call->getArgOperand(i: 2))) {
347 // memset_chk writes at most Len bytes, memcpy_chk reads/writes at most
348 // Len bytes. They may read/write less, if Len exceeds the specified max
349 // size and aborts.
350 Size = LocationSize::upperBound(Value: 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>(Val: Call->getArgOperand(i: 2))) {
359 // strncpy is guaranteed to write Len bytes, but only reads up to Len
360 // bytes.
361 Size = ArgIdx == 0 ? LocationSize::precise(Value: Len->getZExtValue())
362 : LocationSize::upperBound(Value: 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(Value: Size), AATags);
378 }
379 if (const ConstantInt *LenCI =
380 dyn_cast<ConstantInt>(Val: Call->getArgOperand(i: 2)))
381 return MemoryLocation(Arg, LocationSize::precise(Value: LenCI->getZExtValue()),
382 AATags);
383 return MemoryLocation::getAfter(Ptr: 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>(Val: Call->getArgOperand(i: 2)))
390 return MemoryLocation(Arg, LocationSize::precise(Value: LenCI->getZExtValue()),
391 AATags);
392 return MemoryLocation::getAfter(Ptr: Arg, AATags);
393 case LibFunc_memchr:
394 assert((ArgIdx == 0) && "Invalid argument index for memchr");
395 if (const ConstantInt *LenCI =
396 dyn_cast<ConstantInt>(Val: Call->getArgOperand(i: 2)))
397 return MemoryLocation(Arg, LocationSize::precise(Value: LenCI->getZExtValue()),
398 AATags);
399 return MemoryLocation::getAfter(Ptr: 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>(Val: Call->getArgOperand(i: 3)))
406 return MemoryLocation(
407 Arg, LocationSize::upperBound(Value: LenCI->getZExtValue()), AATags);
408 return MemoryLocation::getAfter(Ptr: Arg, AATags);
409 default:
410 break;
411 };
412 }
413
414 return MemoryLocation::getBeforeOrAfter(Ptr: Call->getArgOperand(i: ArgIdx), AATags);
415}
416