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