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>
17using namespace llvm;
18
19void 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
35MemoryLocation MemoryLocation::get(const LoadInst *LI) {
36 const auto &DL = LI->getDataLayout();
37
38 return MemoryLocation(
39 LI->getPointerOperand(),
40 LocationSize::precise(Value: DL.getTypeStoreSize(Ty: LI->getType())),
41 LI->getAAMetadata());
42}
43
44MemoryLocation MemoryLocation::get(const StoreInst *SI) {
45 const auto &DL = SI->getDataLayout();
46
47 return MemoryLocation(SI->getPointerOperand(),
48 LocationSize::precise(Value: DL.getTypeStoreSize(
49 Ty: SI->getValueOperand()->getType())),
50 SI->getAAMetadata());
51}
52
53MemoryLocation MemoryLocation::get(const VAArgInst *VI) {
54 return MemoryLocation(VI->getPointerOperand(),
55 LocationSize::afterPointer(), VI->getAAMetadata());
56}
57
58MemoryLocation MemoryLocation::get(const AtomicCmpXchgInst *CXI) {
59 const auto &DL = CXI->getDataLayout();
60
61 return MemoryLocation(CXI->getPointerOperand(),
62 LocationSize::precise(Value: DL.getTypeStoreSize(
63 Ty: CXI->getCompareOperand()->getType())),
64 CXI->getAAMetadata());
65}
66
67MemoryLocation MemoryLocation::get(const AtomicRMWInst *RMWI) {
68 const auto &DL = RMWI->getDataLayout();
69
70 return MemoryLocation(RMWI->getPointerOperand(),
71 LocationSize::precise(Value: DL.getTypeStoreSize(
72 Ty: RMWI->getValOperand()->getType())),
73 RMWI->getAAMetadata());
74}
75
76std::optional<MemoryLocation>
77MemoryLocation::getOrNone(const Instruction *Inst) {
78 switch (Inst->getOpcode()) {
79 case Instruction::Load:
80 return get(LI: cast<LoadInst>(Val: Inst));
81 case Instruction::Store:
82 return get(SI: cast<StoreInst>(Val: Inst));
83 case Instruction::VAArg:
84 return get(VI: cast<VAArgInst>(Val: Inst));
85 case Instruction::AtomicCmpXchg:
86 return get(CXI: cast<AtomicCmpXchgInst>(Val: Inst));
87 case Instruction::AtomicRMW:
88 return get(RMWI: cast<AtomicRMWInst>(Val: Inst));
89 default:
90 return std::nullopt;
91 }
92}
93
94MemoryLocation MemoryLocation::getForSource(const MemTransferInst *MTI) {
95 return getForSource(MTI: cast<AnyMemTransferInst>(Val: MTI));
96}
97
98MemoryLocation MemoryLocation::getForSource(const AnyMemTransferInst *MTI) {
99 assert(MTI->getRawSource() == MTI->getArgOperand(1));
100 return getForArgument(Call: MTI, ArgIdx: 1, TLI: nullptr);
101}
102
103MemoryLocation MemoryLocation::getForDest(const MemIntrinsic *MI) {
104 return getForDest(MI: cast<AnyMemIntrinsic>(Val: MI));
105}
106
107MemoryLocation MemoryLocation::getForDest(const AnyMemIntrinsic *MI) {
108 assert(MI->getRawDest() == MI->getArgOperand(0));
109 return getForArgument(Call: MI, ArgIdx: 0, TLI: nullptr);
110}
111
112std::optional<MemoryLocation>
113MemoryLocation::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(OpNo: 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(Call: CB, ArgIdx: *UsedIdx, TLI: &TLI);
150 return MemoryLocation::getBeforeOrAfter(Ptr: UsedV, AATags: CB->getAAMetadata());
151}
152
153MemoryLocation MemoryLocation::getForArgument(const CallBase *Call,
154 unsigned ArgIdx,
155 const TargetLibraryInfo *TLI) {
156 AAMDNodes AATags = Call->getAAMetadata();
157 const Value *Arg = Call->getArgOperand(i: ArgIdx);
158
159 // We may be able to produce an exact size for known intrinsics.
160 if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Val: 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>(Val: II->getArgOperand(i: 2)))
176 return MemoryLocation(Arg, LocationSize::precise(Value: LenCI->getZExtValue()),
177 AATags);
178 return MemoryLocation::getAfter(Ptr: 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>(Val: II->getArgOperand(i: 2)))
184 return MemoryLocation(
185 Arg,
186 LocationSize::precise(
187 Value: LenCI->getZExtValue() *
188 DL.getTypeAllocSize(Ty: II->getArgOperand(i: 1)->getType())),
189 AATags);
190 return MemoryLocation::getAfter(Ptr: 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 Value: cast<ConstantInt>(Val: II->getArgOperand(i: 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(Value: DL.getTypeStoreSize(Ty: 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 Value: DL.getTypeStoreSize(Ty: II->getArgOperand(i: 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(Value: 0), AATags);
222 assert(ArgIdx == 2 && "Invalid argument index");
223 return MemoryLocation(
224 Arg,
225 LocationSize::precise(
226 Value: cast<ConstantInt>(Val: II->getArgOperand(i: 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(Value: DL.getTypeStoreSize(Ty: 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(Value: DL.getTypeStoreSize(
241 Ty: II->getArgOperand(i: 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(CB: *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(Ptr: 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>(Val: Call->getArgOperand(i: 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(Value: 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>(Val: Call->getArgOperand(i: 2))) {
283 // strncpy is guaranteed to write Len bytes, but only reads up to Len
284 // bytes.
285 Size = ArgIdx == 0 ? LocationSize::precise(Value: Len->getZExtValue())
286 : LocationSize::upperBound(Value: 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(Value: Size), AATags);
302 }
303 if (const ConstantInt *LenCI =
304 dyn_cast<ConstantInt>(Val: Call->getArgOperand(i: 2)))
305 return MemoryLocation(Arg, LocationSize::precise(Value: LenCI->getZExtValue()),
306 AATags);
307 return MemoryLocation::getAfter(Ptr: 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>(Val: Call->getArgOperand(i: 2)))
314 return MemoryLocation(Arg, LocationSize::precise(Value: LenCI->getZExtValue()),
315 AATags);
316 return MemoryLocation::getAfter(Ptr: Arg, AATags);
317 case LibFunc_memchr:
318 assert((ArgIdx == 0) && "Invalid argument index for memchr");
319 if (const ConstantInt *LenCI =
320 dyn_cast<ConstantInt>(Val: Call->getArgOperand(i: 2)))
321 return MemoryLocation(Arg, LocationSize::precise(Value: LenCI->getZExtValue()),
322 AATags);
323 return MemoryLocation::getAfter(Ptr: 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>(Val: Call->getArgOperand(i: 3)))
330 return MemoryLocation(
331 Arg, LocationSize::upperBound(Value: LenCI->getZExtValue()), AATags);
332 return MemoryLocation::getAfter(Ptr: Arg, AATags);
333 default:
334 break;
335 };
336 }
337
338 return MemoryLocation::getBeforeOrAfter(Ptr: Call->getArgOperand(i: ArgIdx), AATags);
339}
340