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>
18 using namespace llvm;
19
print(raw_ostream & OS) const20 void 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
get(const LoadInst * LI)36 MemoryLocation 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
get(const StoreInst * SI)45 MemoryLocation 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
get(const VAArgInst * VI)54 MemoryLocation MemoryLocation::get(const VAArgInst *VI) {
55 return MemoryLocation(VI->getPointerOperand(),
56 LocationSize::afterPointer(), VI->getAAMetadata());
57 }
58
get(const AtomicCmpXchgInst * CXI)59 MemoryLocation 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
get(const AtomicRMWInst * RMWI)68 MemoryLocation 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
77 std::optional<MemoryLocation>
getOrNone(const Instruction * Inst)78 MemoryLocation::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
getForSource(const MemTransferInst * MTI)95 MemoryLocation MemoryLocation::getForSource(const MemTransferInst *MTI) {
96 return getForSource(cast<AnyMemTransferInst>(MTI));
97 }
98
getForSource(const AtomicMemTransferInst * MTI)99 MemoryLocation MemoryLocation::getForSource(const AtomicMemTransferInst *MTI) {
100 return getForSource(cast<AnyMemTransferInst>(MTI));
101 }
102
getForSource(const AnyMemTransferInst * MTI)103 MemoryLocation MemoryLocation::getForSource(const AnyMemTransferInst *MTI) {
104 assert(MTI->getRawSource() == MTI->getArgOperand(1));
105 return getForArgument(MTI, 1, nullptr);
106 }
107
getForDest(const MemIntrinsic * MI)108 MemoryLocation MemoryLocation::getForDest(const MemIntrinsic *MI) {
109 return getForDest(cast<AnyMemIntrinsic>(MI));
110 }
111
getForDest(const AtomicMemIntrinsic * MI)112 MemoryLocation MemoryLocation::getForDest(const AtomicMemIntrinsic *MI) {
113 return getForDest(cast<AnyMemIntrinsic>(MI));
114 }
115
getForDest(const AnyMemIntrinsic * MI)116 MemoryLocation MemoryLocation::getForDest(const AnyMemIntrinsic *MI) {
117 assert(MI->getRawDest() == MI->getArgOperand(0));
118 return getForArgument(MI, 0, nullptr);
119 }
120
121 std::optional<MemoryLocation>
getForDest(const CallBase * CB,const TargetLibraryInfo & TLI)122 MemoryLocation::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(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(CB, *UsedIdx, &TLI);
157 return MemoryLocation::getBeforeOrAfter(UsedV, CB->getAAMetadata());
158 }
159
getForArgument(const CallBase * Call,unsigned ArgIdx,const TargetLibraryInfo * TLI)160 MemoryLocation MemoryLocation::getForArgument(const CallBase *Call,
161 unsigned ArgIdx,
162 const TargetLibraryInfo *TLI) {
163 AAMDNodes AATags = Call->getAAMetadata();
164 const Value *Arg = Call->getArgOperand(ArgIdx);
165
166 // We may be able to produce an exact size for known intrinsics.
167 if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(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>(II->getArgOperand(2)))
183 return MemoryLocation(Arg, LocationSize::precise(LenCI->getZExtValue()),
184 AATags);
185 return MemoryLocation::getAfter(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 cast<ConstantInt>(II->getArgOperand(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(DL.getTypeStoreSize(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 DL.getTypeStoreSize(II->getArgOperand(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(0), AATags);
217 assert(ArgIdx == 2 && "Invalid argument index");
218 return MemoryLocation(
219 Arg,
220 LocationSize::precise(
221 cast<ConstantInt>(II->getArgOperand(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(DL.getTypeStoreSize(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(DL.getTypeStoreSize(
236 II->getArgOperand(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(*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(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>(Call->getArgOperand(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(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>(Call->getArgOperand(2))) {
278 // strncpy is guaranteed to write Len bytes, but only reads up to Len
279 // bytes.
280 Size = ArgIdx == 0 ? LocationSize::precise(Len->getZExtValue())
281 : LocationSize::upperBound(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(Size), AATags);
297 }
298 if (const ConstantInt *LenCI =
299 dyn_cast<ConstantInt>(Call->getArgOperand(2)))
300 return MemoryLocation(Arg, LocationSize::precise(LenCI->getZExtValue()),
301 AATags);
302 return MemoryLocation::getAfter(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>(Call->getArgOperand(2)))
309 return MemoryLocation(Arg, LocationSize::precise(LenCI->getZExtValue()),
310 AATags);
311 return MemoryLocation::getAfter(Arg, AATags);
312 case LibFunc_memchr:
313 assert((ArgIdx == 0) && "Invalid argument index for memchr");
314 if (const ConstantInt *LenCI =
315 dyn_cast<ConstantInt>(Call->getArgOperand(2)))
316 return MemoryLocation(Arg, LocationSize::precise(LenCI->getZExtValue()),
317 AATags);
318 return MemoryLocation::getAfter(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>(Call->getArgOperand(3)))
325 return MemoryLocation(
326 Arg, LocationSize::upperBound(LenCI->getZExtValue()), AATags);
327 return MemoryLocation::getAfter(Arg, AATags);
328 default:
329 break;
330 };
331 }
332
333 return MemoryLocation::getBeforeOrAfter(Call->getArgOperand(ArgIdx), AATags);
334 }
335