1//===- MemoryBuiltins.cpp - Identify calls to memory builtins -------------===//
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// This family of functions identifies calls to builtin functions that allocate
10// or free memory.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/Analysis/MemoryBuiltins.h"
15#include "llvm/ADT/APInt.h"
16#include "llvm/ADT/STLExtras.h"
17#include "llvm/ADT/Statistic.h"
18#include "llvm/Analysis/AliasAnalysis.h"
19#include "llvm/Analysis/TargetFolder.h"
20#include "llvm/Analysis/TargetLibraryInfo.h"
21#include "llvm/Analysis/Utils/Local.h"
22#include "llvm/Analysis/ValueTracking.h"
23#include "llvm/IR/Argument.h"
24#include "llvm/IR/Attributes.h"
25#include "llvm/IR/Constants.h"
26#include "llvm/IR/DataLayout.h"
27#include "llvm/IR/DerivedTypes.h"
28#include "llvm/IR/Function.h"
29#include "llvm/IR/GlobalAlias.h"
30#include "llvm/IR/GlobalVariable.h"
31#include "llvm/IR/Instruction.h"
32#include "llvm/IR/Instructions.h"
33#include "llvm/IR/IntrinsicInst.h"
34#include "llvm/IR/Operator.h"
35#include "llvm/IR/Type.h"
36#include "llvm/IR/Value.h"
37#include "llvm/Support/Casting.h"
38#include "llvm/Support/CommandLine.h"
39#include "llvm/Support/Debug.h"
40#include "llvm/Support/MathExtras.h"
41#include "llvm/Support/raw_ostream.h"
42#include <cassert>
43#include <cstdint>
44#include <iterator>
45#include <numeric>
46#include <optional>
47#include <type_traits>
48#include <utility>
49
50using namespace llvm;
51
52#define DEBUG_TYPE "memory-builtins"
53
54static cl::opt<unsigned> ObjectSizeOffsetVisitorMaxVisitInstructions(
55 "object-size-offset-visitor-max-visit-instructions",
56 cl::desc("Maximum number of instructions for ObjectSizeOffsetVisitor to "
57 "look at"),
58 cl::init(Val: 100));
59
60enum AllocType : uint8_t {
61 OpNewLike = 1<<0, // allocates; never returns null
62 MallocLike = 1<<1, // allocates; may return null
63 StrDupLike = 1<<2,
64 MallocOrOpNewLike = MallocLike | OpNewLike,
65 AllocLike = MallocOrOpNewLike | StrDupLike,
66 AnyAlloc = AllocLike
67};
68
69enum class MallocFamily {
70 Malloc,
71 CPPNew, // new(unsigned int)
72 CPPNewAligned, // new(unsigned int, align_val_t)
73 CPPNewArray, // new[](unsigned int)
74 CPPNewArrayAligned, // new[](unsigned long, align_val_t)
75 MSVCNew, // new(unsigned int)
76 MSVCArrayNew, // new[](unsigned int)
77 VecMalloc,
78 KmpcAllocShared,
79};
80
81StringRef mangledNameForMallocFamily(const MallocFamily &Family) {
82 switch (Family) {
83 case MallocFamily::Malloc:
84 return "malloc";
85 case MallocFamily::CPPNew:
86 return "_Znwm";
87 case MallocFamily::CPPNewAligned:
88 return "_ZnwmSt11align_val_t";
89 case MallocFamily::CPPNewArray:
90 return "_Znam";
91 case MallocFamily::CPPNewArrayAligned:
92 return "_ZnamSt11align_val_t";
93 case MallocFamily::MSVCNew:
94 return "??2@YAPAXI@Z";
95 case MallocFamily::MSVCArrayNew:
96 return "??_U@YAPAXI@Z";
97 case MallocFamily::VecMalloc:
98 return "vec_malloc";
99 case MallocFamily::KmpcAllocShared:
100 return "__kmpc_alloc_shared";
101 }
102 llvm_unreachable("missing an alloc family");
103}
104
105struct AllocFnsTy {
106 AllocType AllocTy;
107 unsigned NumParams;
108 // First and Second size parameters (or -1 if unused)
109 int FstParam, SndParam;
110 // Alignment parameter for aligned_alloc and aligned new
111 int AlignParam;
112 // Name of default allocator function to group malloc/free calls by family
113 MallocFamily Family;
114};
115
116// clang-format off
117// FIXME: certain users need more information. E.g., SimplifyLibCalls needs to
118// know which functions are nounwind, noalias, nocapture parameters, etc.
119static const std::pair<LibFunc, AllocFnsTy> AllocationFnData[] = {
120 {LibFunc_Znwj, {.AllocTy: OpNewLike, .NumParams: 1, .FstParam: 0, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::CPPNew}}, // new(unsigned int)
121 {LibFunc_ZnwjRKSt9nothrow_t, {.AllocTy: MallocLike, .NumParams: 2, .FstParam: 0, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::CPPNew}}, // new(unsigned int, nothrow)
122 {LibFunc_ZnwjSt11align_val_t, {.AllocTy: OpNewLike, .NumParams: 2, .FstParam: 0, .SndParam: -1, .AlignParam: 1, .Family: MallocFamily::CPPNewAligned}}, // new(unsigned int, align_val_t)
123 {LibFunc_ZnwjSt11align_val_tRKSt9nothrow_t, {.AllocTy: MallocLike, .NumParams: 3, .FstParam: 0, .SndParam: -1, .AlignParam: 1, .Family: MallocFamily::CPPNewAligned}}, // new(unsigned int, align_val_t, nothrow)
124 {LibFunc_Znwm, {.AllocTy: OpNewLike, .NumParams: 1, .FstParam: 0, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::CPPNew}}, // new(unsigned long)
125 {LibFunc_Znwm12__hot_cold_t, {.AllocTy: OpNewLike, .NumParams: 2, .FstParam: 0, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::CPPNew}}, // new(unsigned long, __hot_cold_t)
126 {LibFunc_ZnwmRKSt9nothrow_t, {.AllocTy: MallocLike, .NumParams: 2, .FstParam: 0, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::CPPNew}}, // new(unsigned long, nothrow)
127 {LibFunc_ZnwmRKSt9nothrow_t12__hot_cold_t, {.AllocTy: MallocLike, .NumParams: 3, .FstParam: 0, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::CPPNew}}, // new(unsigned long, nothrow, __hot_cold_t)
128 {LibFunc_ZnwmSt11align_val_t, {.AllocTy: OpNewLike, .NumParams: 2, .FstParam: 0, .SndParam: -1, .AlignParam: 1, .Family: MallocFamily::CPPNewAligned}}, // new(unsigned long, align_val_t)
129 {LibFunc_ZnwmSt11align_val_t12__hot_cold_t, {.AllocTy: OpNewLike, .NumParams: 3, .FstParam: 0, .SndParam: -1, .AlignParam: 1, .Family: MallocFamily::CPPNewAligned}}, // new(unsigned long, align_val_t, __hot_cold_t)
130 {LibFunc_ZnwmSt11align_val_tRKSt9nothrow_t, {.AllocTy: MallocLike, .NumParams: 3, .FstParam: 0, .SndParam: -1, .AlignParam: 1, .Family: MallocFamily::CPPNewAligned}}, // new(unsigned long, align_val_t, nothrow)
131 {LibFunc_ZnwmSt11align_val_tRKSt9nothrow_t12__hot_cold_t, {.AllocTy: MallocLike, .NumParams: 4, .FstParam: 0, .SndParam: -1, .AlignParam: 1, .Family: MallocFamily::CPPNewAligned}}, // new(unsigned long, align_val_t, nothrow, __hot_cold_t)
132 {LibFunc_Znaj, {.AllocTy: OpNewLike, .NumParams: 1, .FstParam: 0, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::CPPNewArray}}, // new[](unsigned int)
133 {LibFunc_ZnajRKSt9nothrow_t, {.AllocTy: MallocLike, .NumParams: 2, .FstParam: 0, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::CPPNewArray}}, // new[](unsigned int, nothrow)
134 {LibFunc_ZnajSt11align_val_t, {.AllocTy: OpNewLike, .NumParams: 2, .FstParam: 0, .SndParam: -1, .AlignParam: 1, .Family: MallocFamily::CPPNewArrayAligned}}, // new[](unsigned int, align_val_t)
135 {LibFunc_ZnajSt11align_val_tRKSt9nothrow_t, {.AllocTy: MallocLike, .NumParams: 3, .FstParam: 0, .SndParam: -1, .AlignParam: 1, .Family: MallocFamily::CPPNewArrayAligned}}, // new[](unsigned int, align_val_t, nothrow)
136 {LibFunc_Znam, {.AllocTy: OpNewLike, .NumParams: 1, .FstParam: 0, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::CPPNewArray}}, // new[](unsigned long)
137 {LibFunc_Znam12__hot_cold_t, {.AllocTy: OpNewLike, .NumParams: 2, .FstParam: 0, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::CPPNew}}, // new[](unsigned long, __hot_cold_t)
138 {LibFunc_ZnamRKSt9nothrow_t, {.AllocTy: MallocLike, .NumParams: 2, .FstParam: 0, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::CPPNewArray}}, // new[](unsigned long, nothrow)
139 {LibFunc_ZnamRKSt9nothrow_t12__hot_cold_t, {.AllocTy: MallocLike, .NumParams: 3, .FstParam: 0, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::CPPNew}}, // new[](unsigned long, nothrow, __hot_cold_t)
140 {LibFunc_ZnamSt11align_val_t, {.AllocTy: OpNewLike, .NumParams: 2, .FstParam: 0, .SndParam: -1, .AlignParam: 1, .Family: MallocFamily::CPPNewArrayAligned}}, // new[](unsigned long, align_val_t)
141 {LibFunc_ZnamSt11align_val_t12__hot_cold_t, {.AllocTy: OpNewLike, .NumParams: 3, .FstParam: 0, .SndParam: -1, .AlignParam: 1, .Family: MallocFamily::CPPNewAligned}}, // new[](unsigned long, align_val_t, __hot_cold_t)
142 {LibFunc_ZnamSt11align_val_tRKSt9nothrow_t, {.AllocTy: MallocLike, .NumParams: 3, .FstParam: 0, .SndParam: -1, .AlignParam: 1, .Family: MallocFamily::CPPNewArrayAligned}}, // new[](unsigned long, align_val_t, nothrow)
143 {LibFunc_ZnamSt11align_val_tRKSt9nothrow_t12__hot_cold_t, {.AllocTy: MallocLike, .NumParams: 4, .FstParam: 0, .SndParam: -1, .AlignParam: 1, .Family: MallocFamily::CPPNewAligned}}, // new[](unsigned long, align_val_t, nothrow, __hot_cold_t)
144 {LibFunc_msvc_new_int, {.AllocTy: OpNewLike, .NumParams: 1, .FstParam: 0, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::MSVCNew}}, // new(unsigned int)
145 {LibFunc_msvc_new_int_nothrow, {.AllocTy: MallocLike, .NumParams: 2, .FstParam: 0, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::MSVCNew}}, // new(unsigned int, nothrow)
146 {LibFunc_msvc_new_longlong, {.AllocTy: OpNewLike, .NumParams: 1, .FstParam: 0, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::MSVCNew}}, // new(unsigned long long)
147 {LibFunc_msvc_new_longlong_nothrow, {.AllocTy: MallocLike, .NumParams: 2, .FstParam: 0, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::MSVCNew}}, // new(unsigned long long, nothrow)
148 {LibFunc_msvc_new_array_int, {.AllocTy: OpNewLike, .NumParams: 1, .FstParam: 0, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::MSVCArrayNew}}, // new[](unsigned int)
149 {LibFunc_msvc_new_array_int_nothrow, {.AllocTy: MallocLike, .NumParams: 2, .FstParam: 0, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::MSVCArrayNew}}, // new[](unsigned int, nothrow)
150 {LibFunc_msvc_new_array_longlong, {.AllocTy: OpNewLike, .NumParams: 1, .FstParam: 0, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::MSVCArrayNew}}, // new[](unsigned long long)
151 {LibFunc_msvc_new_array_longlong_nothrow, {.AllocTy: MallocLike, .NumParams: 2, .FstParam: 0, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::MSVCArrayNew}}, // new[](unsigned long long, nothrow)
152 {LibFunc_strdup, {.AllocTy: StrDupLike, .NumParams: 1, .FstParam: -1, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::Malloc}},
153 {LibFunc_dunder_strdup, {.AllocTy: StrDupLike, .NumParams: 1, .FstParam: -1, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::Malloc}},
154 {LibFunc_strndup, {.AllocTy: StrDupLike, .NumParams: 2, .FstParam: 1, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::Malloc}},
155 {LibFunc_dunder_strndup, {.AllocTy: StrDupLike, .NumParams: 2, .FstParam: 1, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::Malloc}},
156 {LibFunc___kmpc_alloc_shared, {.AllocTy: MallocLike, .NumParams: 1, .FstParam: 0, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::KmpcAllocShared}},
157};
158// clang-format on
159
160static const Function *getCalledFunction(const Value *V,
161 bool &IsNoBuiltin) {
162 // Don't care about intrinsics in this case.
163 if (isa<IntrinsicInst>(Val: V))
164 return nullptr;
165
166 const auto *CB = dyn_cast<CallBase>(Val: V);
167 if (!CB)
168 return nullptr;
169
170 IsNoBuiltin = CB->isNoBuiltin();
171
172 if (const Function *Callee = CB->getCalledFunction())
173 return Callee;
174 return nullptr;
175}
176
177/// Returns the allocation data for the given value if it's a call to a known
178/// allocation function.
179static std::optional<AllocFnsTy>
180getAllocationDataForFunction(const Function *Callee, AllocType AllocTy,
181 const TargetLibraryInfo *TLI) {
182 // Don't perform a slow TLI lookup, if this function doesn't return a pointer
183 // and thus can't be an allocation function.
184 if (!Callee->getReturnType()->isPointerTy())
185 return std::nullopt;
186
187 // Make sure that the function is available.
188 LibFunc TLIFn;
189 if (!TLI || !TLI->getLibFunc(FDecl: *Callee, F&: TLIFn) || !TLI->has(F: TLIFn))
190 return std::nullopt;
191
192 const auto *Iter = find_if(
193 Range: AllocationFnData, P: [TLIFn](const std::pair<LibFunc, AllocFnsTy> &P) {
194 return P.first == TLIFn;
195 });
196
197 if (Iter == std::end(arr: AllocationFnData))
198 return std::nullopt;
199
200 const AllocFnsTy *FnData = &Iter->second;
201 if ((FnData->AllocTy & AllocTy) != FnData->AllocTy)
202 return std::nullopt;
203
204 // Check function prototype.
205 int FstParam = FnData->FstParam;
206 int SndParam = FnData->SndParam;
207 FunctionType *FTy = Callee->getFunctionType();
208
209 if (FTy->getReturnType()->isPointerTy() &&
210 FTy->getNumParams() == FnData->NumParams &&
211 (FstParam < 0 ||
212 (FTy->getParamType(i: FstParam)->isIntegerTy(Bitwidth: 32) ||
213 FTy->getParamType(i: FstParam)->isIntegerTy(Bitwidth: 64))) &&
214 (SndParam < 0 ||
215 FTy->getParamType(i: SndParam)->isIntegerTy(Bitwidth: 32) ||
216 FTy->getParamType(i: SndParam)->isIntegerTy(Bitwidth: 64)))
217 return *FnData;
218 return std::nullopt;
219}
220
221static std::optional<AllocFnsTy>
222getAllocationData(const Value *V, AllocType AllocTy,
223 const TargetLibraryInfo *TLI) {
224 bool IsNoBuiltinCall;
225 if (const Function *Callee = getCalledFunction(V, IsNoBuiltin&: IsNoBuiltinCall))
226 if (!IsNoBuiltinCall)
227 return getAllocationDataForFunction(Callee, AllocTy, TLI);
228 return std::nullopt;
229}
230
231static std::optional<AllocFnsTy>
232getAllocationData(const Value *V, AllocType AllocTy,
233 function_ref<const TargetLibraryInfo &(Function &)> GetTLI) {
234 bool IsNoBuiltinCall;
235 if (const Function *Callee = getCalledFunction(V, IsNoBuiltin&: IsNoBuiltinCall))
236 if (!IsNoBuiltinCall)
237 return getAllocationDataForFunction(
238 Callee, AllocTy, TLI: &GetTLI(const_cast<Function &>(*Callee)));
239 return std::nullopt;
240}
241
242static std::optional<AllocFnsTy>
243getAllocationSize(const Value *V, const TargetLibraryInfo *TLI) {
244 bool IsNoBuiltinCall;
245 const Function *Callee =
246 getCalledFunction(V, IsNoBuiltin&: IsNoBuiltinCall);
247 if (!Callee)
248 return std::nullopt;
249
250 // Prefer to use existing information over allocsize. This will give us an
251 // accurate AllocTy.
252 if (!IsNoBuiltinCall)
253 if (std::optional<AllocFnsTy> Data =
254 getAllocationDataForFunction(Callee, AllocTy: AnyAlloc, TLI))
255 return Data;
256
257 Attribute Attr = Callee->getFnAttribute(Kind: Attribute::AllocSize);
258 if (Attr == Attribute())
259 return std::nullopt;
260
261 std::pair<unsigned, std::optional<unsigned>> Args = Attr.getAllocSizeArgs();
262
263 AllocFnsTy Result;
264 // Because allocsize only tells us how many bytes are allocated, we're not
265 // really allowed to assume anything, so we use MallocLike.
266 Result.AllocTy = MallocLike;
267 Result.NumParams = Callee->getNumOperands();
268 Result.FstParam = Args.first;
269 Result.SndParam = Args.second.value_or(u: -1);
270 // Allocsize has no way to specify an alignment argument
271 Result.AlignParam = -1;
272 return Result;
273}
274
275static AllocFnKind getAllocFnKind(const Value *V) {
276 if (const auto *CB = dyn_cast<CallBase>(Val: V)) {
277 Attribute Attr = CB->getFnAttr(Kind: Attribute::AllocKind);
278 if (Attr.isValid())
279 return AllocFnKind(Attr.getValueAsInt());
280 }
281 return AllocFnKind::Unknown;
282}
283
284static AllocFnKind getAllocFnKind(const Function *F) {
285 return F->getAttributes().getAllocKind();
286}
287
288static bool checkFnAllocKind(const Value *V, AllocFnKind Wanted) {
289 return (getAllocFnKind(V) & Wanted) != AllocFnKind::Unknown;
290}
291
292static bool checkFnAllocKind(const Function *F, AllocFnKind Wanted) {
293 return (getAllocFnKind(F) & Wanted) != AllocFnKind::Unknown;
294}
295
296/// Tests if a value is a call or invoke to a library function that
297/// allocates or reallocates memory (either malloc, calloc, realloc, or strdup
298/// like).
299bool llvm::isAllocationFn(const Value *V, const TargetLibraryInfo *TLI) {
300 return getAllocationData(V, AllocTy: AnyAlloc, TLI).has_value() ||
301 checkFnAllocKind(V, Wanted: AllocFnKind::Alloc | AllocFnKind::Realloc);
302}
303bool llvm::isAllocationFn(
304 const Value *V,
305 function_ref<const TargetLibraryInfo &(Function &)> GetTLI) {
306 return getAllocationData(V, AllocTy: AnyAlloc, GetTLI).has_value() ||
307 checkFnAllocKind(V, Wanted: AllocFnKind::Alloc | AllocFnKind::Realloc);
308}
309
310/// Tests if a value is a call or invoke to a library function that
311/// allocates memory via new.
312bool llvm::isNewLikeFn(const Value *V, const TargetLibraryInfo *TLI) {
313 return getAllocationData(V, AllocTy: OpNewLike, TLI).has_value();
314}
315
316/// Tests if a value is a call or invoke to a library function that
317/// allocates memory similar to malloc or calloc.
318bool llvm::isMallocOrCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI) {
319 // TODO: Function behavior does not match name.
320 return getAllocationData(V, AllocTy: MallocOrOpNewLike, TLI).has_value();
321}
322
323/// Tests if a value is a call or invoke to a library function that
324/// allocates memory (either malloc, calloc, or strdup like).
325bool llvm::isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI) {
326 return getAllocationData(V, AllocTy: AllocLike, TLI).has_value() ||
327 checkFnAllocKind(V, Wanted: AllocFnKind::Alloc);
328}
329
330/// Tests if a functions is a call or invoke to a library function that
331/// reallocates memory (e.g., realloc).
332bool llvm::isReallocLikeFn(const Function *F) {
333 return checkFnAllocKind(F, Wanted: AllocFnKind::Realloc);
334}
335
336Value *llvm::getReallocatedOperand(const CallBase *CB) {
337 if (checkFnAllocKind(V: CB, Wanted: AllocFnKind::Realloc))
338 return CB->getArgOperandWithAttribute(Kind: Attribute::AllocatedPointer);
339 return nullptr;
340}
341
342bool llvm::isRemovableAlloc(const CallBase *CB, const TargetLibraryInfo *TLI) {
343 // Note: Removability is highly dependent on the source language. For
344 // example, recent C++ requires direct calls to the global allocation
345 // [basic.stc.dynamic.allocation] to be observable unless part of a new
346 // expression [expr.new paragraph 13].
347
348 // Historically we've treated the C family allocation routines and operator
349 // new as removable
350 return isAllocLikeFn(V: CB, TLI);
351}
352
353Value *llvm::getAllocAlignment(const CallBase *V,
354 const TargetLibraryInfo *TLI) {
355 const std::optional<AllocFnsTy> FnData = getAllocationData(V, AllocTy: AnyAlloc, TLI);
356 if (FnData && FnData->AlignParam >= 0) {
357 return V->getOperand(i_nocapture: FnData->AlignParam);
358 }
359 return V->getArgOperandWithAttribute(Kind: Attribute::AllocAlign);
360}
361
362/// When we're compiling N-bit code, and the user uses parameters that are
363/// greater than N bits (e.g. uint64_t on a 32-bit build), we can run into
364/// trouble with APInt size issues. This function handles resizing + overflow
365/// checks for us. Check and zext or trunc \p I depending on IntTyBits and
366/// I's value.
367static bool CheckedZextOrTrunc(APInt &I, unsigned IntTyBits) {
368 // More bits than we can handle. Checking the bit width isn't necessary, but
369 // it's faster than checking active bits, and should give `false` in the
370 // vast majority of cases.
371 if (I.getBitWidth() > IntTyBits && I.getActiveBits() > IntTyBits)
372 return false;
373 if (I.getBitWidth() != IntTyBits)
374 I = I.zextOrTrunc(width: IntTyBits);
375 return true;
376}
377
378std::optional<APInt>
379llvm::getAllocSize(const CallBase *CB, const TargetLibraryInfo *TLI,
380 function_ref<const Value *(const Value *)> Mapper) {
381 // Note: This handles both explicitly listed allocation functions and
382 // allocsize. The code structure could stand to be cleaned up a bit.
383 std::optional<AllocFnsTy> FnData = getAllocationSize(V: CB, TLI);
384 if (!FnData)
385 return std::nullopt;
386
387 // Get the index type for this address space, results and intermediate
388 // computations are performed at that width.
389 auto &DL = CB->getDataLayout();
390 const unsigned IntTyBits = DL.getIndexTypeSizeInBits(Ty: CB->getType());
391
392 // Handle strdup-like functions separately.
393 if (FnData->AllocTy == StrDupLike) {
394 APInt Size(IntTyBits, GetStringLength(V: Mapper(CB->getArgOperand(i: 0))));
395 if (!Size)
396 return std::nullopt;
397
398 // Strndup limits strlen.
399 if (FnData->FstParam > 0) {
400 const ConstantInt *Arg =
401 dyn_cast<ConstantInt>(Val: Mapper(CB->getArgOperand(i: FnData->FstParam)));
402 if (!Arg)
403 return std::nullopt;
404
405 APInt MaxSize = Arg->getValue().zext(width: IntTyBits);
406 if (Size.ugt(RHS: MaxSize))
407 Size = MaxSize + 1;
408 }
409 return Size;
410 }
411
412 const ConstantInt *Arg =
413 dyn_cast<ConstantInt>(Val: Mapper(CB->getArgOperand(i: FnData->FstParam)));
414 if (!Arg)
415 return std::nullopt;
416
417 APInt Size = Arg->getValue();
418 if (!CheckedZextOrTrunc(I&: Size, IntTyBits))
419 return std::nullopt;
420
421 // Size is determined by just 1 parameter.
422 if (FnData->SndParam < 0)
423 return Size;
424
425 Arg = dyn_cast<ConstantInt>(Val: Mapper(CB->getArgOperand(i: FnData->SndParam)));
426 if (!Arg)
427 return std::nullopt;
428
429 APInt NumElems = Arg->getValue();
430 if (!CheckedZextOrTrunc(I&: NumElems, IntTyBits))
431 return std::nullopt;
432
433 bool Overflow;
434 Size = Size.umul_ov(RHS: NumElems, Overflow);
435 if (Overflow)
436 return std::nullopt;
437 return Size;
438}
439
440Constant *llvm::getInitialValueOfAllocation(const Value *V,
441 const TargetLibraryInfo *TLI,
442 Type *Ty) {
443 auto *Alloc = dyn_cast<CallBase>(Val: V);
444 if (!Alloc)
445 return nullptr;
446
447 // malloc are uninitialized (undef)
448 if (getAllocationData(V: Alloc, AllocTy: MallocOrOpNewLike, TLI).has_value())
449 return UndefValue::get(T: Ty);
450
451 AllocFnKind AK = getAllocFnKind(V: Alloc);
452 if ((AK & AllocFnKind::Uninitialized) != AllocFnKind::Unknown)
453 return UndefValue::get(T: Ty);
454 if ((AK & AllocFnKind::Zeroed) != AllocFnKind::Unknown)
455 return Constant::getNullValue(Ty);
456
457 return nullptr;
458}
459
460struct FreeFnsTy {
461 unsigned NumParams;
462 // Name of default allocator function to group malloc/free calls by family
463 MallocFamily Family;
464};
465
466// clang-format off
467static const std::pair<LibFunc, FreeFnsTy> FreeFnData[] = {
468 {LibFunc_ZdlPv, {.NumParams: 1, .Family: MallocFamily::CPPNew}}, // operator delete(void*)
469 {LibFunc_ZdaPv, {.NumParams: 1, .Family: MallocFamily::CPPNewArray}}, // operator delete[](void*)
470 {LibFunc_msvc_delete_ptr32, {.NumParams: 1, .Family: MallocFamily::MSVCNew}}, // operator delete(void*)
471 {LibFunc_msvc_delete_ptr64, {.NumParams: 1, .Family: MallocFamily::MSVCNew}}, // operator delete(void*)
472 {LibFunc_msvc_delete_array_ptr32, {.NumParams: 1, .Family: MallocFamily::MSVCArrayNew}}, // operator delete[](void*)
473 {LibFunc_msvc_delete_array_ptr64, {.NumParams: 1, .Family: MallocFamily::MSVCArrayNew}}, // operator delete[](void*)
474 {LibFunc_ZdlPvj, {.NumParams: 2, .Family: MallocFamily::CPPNew}}, // delete(void*, uint)
475 {LibFunc_ZdlPvm, {.NumParams: 2, .Family: MallocFamily::CPPNew}}, // delete(void*, ulong)
476 {LibFunc_ZdlPvRKSt9nothrow_t, {.NumParams: 2, .Family: MallocFamily::CPPNew}}, // delete(void*, nothrow)
477 {LibFunc_ZdlPvSt11align_val_t, {.NumParams: 2, .Family: MallocFamily::CPPNewAligned}}, // delete(void*, align_val_t)
478 {LibFunc_ZdaPvj, {.NumParams: 2, .Family: MallocFamily::CPPNewArray}}, // delete[](void*, uint)
479 {LibFunc_ZdaPvm, {.NumParams: 2, .Family: MallocFamily::CPPNewArray}}, // delete[](void*, ulong)
480 {LibFunc_ZdaPvRKSt9nothrow_t, {.NumParams: 2, .Family: MallocFamily::CPPNewArray}}, // delete[](void*, nothrow)
481 {LibFunc_ZdaPvSt11align_val_t, {.NumParams: 2, .Family: MallocFamily::CPPNewArrayAligned}}, // delete[](void*, align_val_t)
482 {LibFunc_msvc_delete_ptr32_int, {.NumParams: 2, .Family: MallocFamily::MSVCNew}}, // delete(void*, uint)
483 {LibFunc_msvc_delete_ptr64_longlong, {.NumParams: 2, .Family: MallocFamily::MSVCNew}}, // delete(void*, ulonglong)
484 {LibFunc_msvc_delete_ptr32_nothrow, {.NumParams: 2, .Family: MallocFamily::MSVCNew}}, // delete(void*, nothrow)
485 {LibFunc_msvc_delete_ptr64_nothrow, {.NumParams: 2, .Family: MallocFamily::MSVCNew}}, // delete(void*, nothrow)
486 {LibFunc_msvc_delete_array_ptr32_int, {.NumParams: 2, .Family: MallocFamily::MSVCArrayNew}}, // delete[](void*, uint)
487 {LibFunc_msvc_delete_array_ptr64_longlong, {.NumParams: 2, .Family: MallocFamily::MSVCArrayNew}}, // delete[](void*, ulonglong)
488 {LibFunc_msvc_delete_array_ptr32_nothrow, {.NumParams: 2, .Family: MallocFamily::MSVCArrayNew}}, // delete[](void*, nothrow)
489 {LibFunc_msvc_delete_array_ptr64_nothrow, {.NumParams: 2, .Family: MallocFamily::MSVCArrayNew}}, // delete[](void*, nothrow)
490 {LibFunc___kmpc_free_shared, {.NumParams: 2, .Family: MallocFamily::KmpcAllocShared}}, // OpenMP Offloading RTL free
491 {LibFunc_ZdlPvSt11align_val_tRKSt9nothrow_t, {.NumParams: 3, .Family: MallocFamily::CPPNewAligned}}, // delete(void*, align_val_t, nothrow)
492 {LibFunc_ZdaPvSt11align_val_tRKSt9nothrow_t, {.NumParams: 3, .Family: MallocFamily::CPPNewArrayAligned}}, // delete[](void*, align_val_t, nothrow)
493 {LibFunc_ZdlPvjSt11align_val_t, {.NumParams: 3, .Family: MallocFamily::CPPNewAligned}}, // delete(void*, unsigned int, align_val_t)
494 {LibFunc_ZdlPvmSt11align_val_t, {.NumParams: 3, .Family: MallocFamily::CPPNewAligned}}, // delete(void*, unsigned long, align_val_t)
495 {LibFunc_ZdaPvjSt11align_val_t, {.NumParams: 3, .Family: MallocFamily::CPPNewArrayAligned}}, // delete[](void*, unsigned int, align_val_t)
496 {LibFunc_ZdaPvmSt11align_val_t, {.NumParams: 3, .Family: MallocFamily::CPPNewArrayAligned}}, // delete[](void*, unsigned long, align_val_t)
497};
498// clang-format on
499
500std::optional<FreeFnsTy> getFreeFunctionDataForFunction(const Function *Callee,
501 const LibFunc TLIFn) {
502 const auto *Iter =
503 find_if(Range: FreeFnData, P: [TLIFn](const std::pair<LibFunc, FreeFnsTy> &P) {
504 return P.first == TLIFn;
505 });
506 if (Iter == std::end(arr: FreeFnData))
507 return std::nullopt;
508 return Iter->second;
509}
510
511std::optional<StringRef>
512llvm::getAllocationFamily(const Value *I, const TargetLibraryInfo *TLI) {
513 bool IsNoBuiltin;
514 const Function *Callee = getCalledFunction(V: I, IsNoBuiltin);
515 if (Callee == nullptr || IsNoBuiltin)
516 return std::nullopt;
517 LibFunc TLIFn;
518
519 if (TLI && TLI->getLibFunc(FDecl: *Callee, F&: TLIFn) && TLI->has(F: TLIFn)) {
520 // Callee is some known library function.
521 const auto AllocData = getAllocationDataForFunction(Callee, AllocTy: AnyAlloc, TLI);
522 if (AllocData)
523 return mangledNameForMallocFamily(Family: AllocData->Family);
524 const auto FreeData = getFreeFunctionDataForFunction(Callee, TLIFn);
525 if (FreeData)
526 return mangledNameForMallocFamily(Family: FreeData->Family);
527 }
528 // Callee isn't a known library function, still check attributes.
529 if (checkFnAllocKind(V: I, Wanted: AllocFnKind::Free | AllocFnKind::Alloc |
530 AllocFnKind::Realloc)) {
531 Attribute Attr = cast<CallBase>(Val: I)->getFnAttr(Kind: "alloc-family");
532 if (Attr.isValid())
533 return Attr.getValueAsString();
534 }
535 return std::nullopt;
536}
537
538/// isLibFreeFunction - Returns true if the function is a builtin free()
539bool llvm::isLibFreeFunction(const Function *F, const LibFunc TLIFn) {
540 std::optional<FreeFnsTy> FnData = getFreeFunctionDataForFunction(Callee: F, TLIFn);
541 if (!FnData)
542 return checkFnAllocKind(F, Wanted: AllocFnKind::Free);
543
544 // Check free prototype.
545 // FIXME: workaround for PR5130, this will be obsolete when a nobuiltin
546 // attribute will exist.
547 FunctionType *FTy = F->getFunctionType();
548 if (!FTy->getReturnType()->isVoidTy())
549 return false;
550 if (FTy->getNumParams() != FnData->NumParams)
551 return false;
552 if (!FTy->getParamType(i: 0)->isPointerTy())
553 return false;
554
555 return true;
556}
557
558Value *llvm::getFreedOperand(const CallBase *CB, const TargetLibraryInfo *TLI) {
559 bool IsNoBuiltinCall;
560 const Function *Callee = getCalledFunction(V: CB, IsNoBuiltin&: IsNoBuiltinCall);
561 if (Callee == nullptr || IsNoBuiltinCall)
562 return nullptr;
563
564 LibFunc TLIFn;
565 if (TLI && TLI->getLibFunc(FDecl: *Callee, F&: TLIFn) && TLI->has(F: TLIFn) &&
566 isLibFreeFunction(F: Callee, TLIFn)) {
567 // All currently supported free functions free the first argument.
568 return CB->getArgOperand(i: 0);
569 }
570
571 if (checkFnAllocKind(V: CB, Wanted: AllocFnKind::Free))
572 return CB->getArgOperandWithAttribute(Kind: Attribute::AllocatedPointer);
573
574 return nullptr;
575}
576
577//===----------------------------------------------------------------------===//
578// Utility functions to compute size of objects.
579//
580static APInt getSizeWithOverflow(const SizeOffsetAPInt &Data) {
581 APInt Size = Data.Size;
582 APInt Offset = Data.Offset;
583 if (Offset.isNegative() || Size.ult(RHS: Offset))
584 return APInt(Size.getBitWidth(), 0);
585 return Size - Offset;
586}
587
588/// Compute the size of the object pointed by Ptr. Returns true and the
589/// object size in Size if successful, and false otherwise.
590/// If RoundToAlign is true, then Size is rounded up to the alignment of
591/// allocas, byval arguments, and global variables.
592bool llvm::getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL,
593 const TargetLibraryInfo *TLI, ObjectSizeOpts Opts) {
594 ObjectSizeOffsetVisitor Visitor(DL, TLI, Ptr->getContext(), Opts);
595 SizeOffsetAPInt Data = Visitor.compute(V: const_cast<Value *>(Ptr));
596 if (!Data.bothKnown())
597 return false;
598
599 Size = getSizeWithOverflow(Data).getZExtValue();
600 return true;
601}
602
603Value *llvm::lowerObjectSizeCall(IntrinsicInst *ObjectSize,
604 const DataLayout &DL,
605 const TargetLibraryInfo *TLI,
606 bool MustSucceed) {
607 return lowerObjectSizeCall(ObjectSize, DL, TLI, /*AAResults=*/AA: nullptr,
608 MustSucceed);
609}
610
611Value *llvm::lowerObjectSizeCall(
612 IntrinsicInst *ObjectSize, const DataLayout &DL,
613 const TargetLibraryInfo *TLI, AAResults *AA, bool MustSucceed,
614 SmallVectorImpl<Instruction *> *InsertedInstructions) {
615 assert(ObjectSize->getIntrinsicID() == Intrinsic::objectsize &&
616 "ObjectSize must be a call to llvm.objectsize!");
617
618 bool MaxVal = cast<ConstantInt>(Val: ObjectSize->getArgOperand(i: 1))->isZero();
619 ObjectSizeOpts EvalOptions;
620 EvalOptions.AA = AA;
621
622 // Unless we have to fold this to something, try to be as accurate as
623 // possible.
624 if (MustSucceed)
625 EvalOptions.EvalMode =
626 MaxVal ? ObjectSizeOpts::Mode::Max : ObjectSizeOpts::Mode::Min;
627 else
628 EvalOptions.EvalMode = ObjectSizeOpts::Mode::ExactSizeFromOffset;
629
630 EvalOptions.NullIsUnknownSize =
631 cast<ConstantInt>(Val: ObjectSize->getArgOperand(i: 2))->isOne();
632
633 auto *ResultType = cast<IntegerType>(Val: ObjectSize->getType());
634 bool StaticOnly = cast<ConstantInt>(Val: ObjectSize->getArgOperand(i: 3))->isZero();
635 if (StaticOnly) {
636 // FIXME: Does it make sense to just return a failure value if the size won't
637 // fit in the output and `!MustSucceed`?
638 uint64_t Size;
639 if (getObjectSize(Ptr: ObjectSize->getArgOperand(i: 0), Size, DL, TLI, Opts: EvalOptions) &&
640 isUIntN(N: ResultType->getBitWidth(), x: Size))
641 return ConstantInt::get(Ty: ResultType, V: Size);
642 } else {
643 LLVMContext &Ctx = ObjectSize->getFunction()->getContext();
644 ObjectSizeOffsetEvaluator Eval(DL, TLI, Ctx, EvalOptions);
645 SizeOffsetValue SizeOffsetPair = Eval.compute(V: ObjectSize->getArgOperand(i: 0));
646
647 if (SizeOffsetPair != ObjectSizeOffsetEvaluator::unknown()) {
648 IRBuilder<TargetFolder, IRBuilderCallbackInserter> Builder(
649 Ctx, TargetFolder(DL), IRBuilderCallbackInserter([&](Instruction *I) {
650 if (InsertedInstructions)
651 InsertedInstructions->push_back(Elt: I);
652 }));
653 Builder.SetInsertPoint(ObjectSize);
654
655 Value *Size = SizeOffsetPair.Size;
656 Value *Offset = SizeOffsetPair.Offset;
657
658 // If we've outside the end of the object, then we can always access
659 // exactly 0 bytes.
660 Value *ResultSize = Builder.CreateSub(LHS: Size, RHS: Offset);
661 Value *UseZero = Builder.CreateICmpULT(LHS: Size, RHS: Offset);
662 ResultSize = Builder.CreateZExtOrTrunc(V: ResultSize, DestTy: ResultType);
663 Value *Ret = Builder.CreateSelect(
664 C: UseZero, True: ConstantInt::get(Ty: ResultType, V: 0), False: ResultSize);
665
666 // The non-constant size expression cannot evaluate to -1.
667 if (!isa<Constant>(Val: Size) || !isa<Constant>(Val: Offset))
668 Builder.CreateAssumption(
669 Cond: Builder.CreateICmpNE(LHS: Ret, RHS: ConstantInt::get(Ty: ResultType, V: -1)));
670
671 return Ret;
672 }
673 }
674
675 if (!MustSucceed)
676 return nullptr;
677
678 return ConstantInt::get(Ty: ResultType, V: MaxVal ? -1ULL : 0);
679}
680
681STATISTIC(ObjectVisitorArgument,
682 "Number of arguments with unsolved size and offset");
683STATISTIC(ObjectVisitorLoad,
684 "Number of load instructions with unsolved size and offset");
685
686APInt ObjectSizeOffsetVisitor::align(APInt Size, MaybeAlign Alignment) {
687 if (Options.RoundToAlign && Alignment)
688 return APInt(IntTyBits, alignTo(Size: Size.getZExtValue(), A: *Alignment));
689 return Size;
690}
691
692ObjectSizeOffsetVisitor::ObjectSizeOffsetVisitor(const DataLayout &DL,
693 const TargetLibraryInfo *TLI,
694 LLVMContext &Context,
695 ObjectSizeOpts Options)
696 : DL(DL), TLI(TLI), Options(Options) {
697 // Pointer size must be rechecked for each object visited since it could have
698 // a different address space.
699}
700
701SizeOffsetAPInt ObjectSizeOffsetVisitor::compute(Value *V) {
702 InstructionsVisited = 0;
703 return computeImpl(V);
704}
705
706SizeOffsetAPInt ObjectSizeOffsetVisitor::computeImpl(Value *V) {
707 unsigned InitialIntTyBits = DL.getIndexTypeSizeInBits(Ty: V->getType());
708
709 // Stripping pointer casts can strip address space casts which can change the
710 // index type size. The invariant is that we use the value type to determine
711 // the index type size and if we stripped address space casts we have to
712 // readjust the APInt as we pass it upwards in order for the APInt to match
713 // the type the caller passed in.
714 APInt Offset(InitialIntTyBits, 0);
715 V = V->stripAndAccumulateConstantOffsets(
716 DL, Offset, /* AllowNonInbounds */ true, /* AllowInvariantGroup */ true);
717
718 // Later we use the index type size and zero but it will match the type of the
719 // value that is passed to computeImpl.
720 IntTyBits = DL.getIndexTypeSizeInBits(Ty: V->getType());
721 Zero = APInt::getZero(numBits: IntTyBits);
722
723 SizeOffsetAPInt SOT = computeValue(V);
724
725 bool IndexTypeSizeChanged = InitialIntTyBits != IntTyBits;
726 if (!IndexTypeSizeChanged && Offset.isZero())
727 return SOT;
728
729 // We stripped an address space cast that changed the index type size or we
730 // accumulated some constant offset (or both). Readjust the bit width to match
731 // the argument index type size and apply the offset, as required.
732 if (IndexTypeSizeChanged) {
733 if (SOT.knownSize() && !::CheckedZextOrTrunc(I&: SOT.Size, IntTyBits: InitialIntTyBits))
734 SOT.Size = APInt();
735 if (SOT.knownOffset() &&
736 !::CheckedZextOrTrunc(I&: SOT.Offset, IntTyBits: InitialIntTyBits))
737 SOT.Offset = APInt();
738 }
739 // If the computed offset is "unknown" we cannot add the stripped offset.
740 return {SOT.Size,
741 SOT.Offset.getBitWidth() > 1 ? SOT.Offset + Offset : SOT.Offset};
742}
743
744SizeOffsetAPInt ObjectSizeOffsetVisitor::computeValue(Value *V) {
745 if (Instruction *I = dyn_cast<Instruction>(Val: V)) {
746 // If we have already seen this instruction, bail out. Cycles can happen in
747 // unreachable code after constant propagation.
748 auto P = SeenInsts.try_emplace(Key: I, Args: ObjectSizeOffsetVisitor::unknown());
749 if (!P.second)
750 return P.first->second;
751 ++InstructionsVisited;
752 if (InstructionsVisited > ObjectSizeOffsetVisitorMaxVisitInstructions)
753 return ObjectSizeOffsetVisitor::unknown();
754 SizeOffsetAPInt Res = visit(I&: *I);
755 // Cache the result for later visits. If we happened to visit this during
756 // the above recursion, we would consider it unknown until now.
757 SeenInsts[I] = Res;
758 return Res;
759 }
760 if (Argument *A = dyn_cast<Argument>(Val: V))
761 return visitArgument(A&: *A);
762 if (ConstantPointerNull *P = dyn_cast<ConstantPointerNull>(Val: V))
763 return visitConstantPointerNull(*P);
764 if (GlobalAlias *GA = dyn_cast<GlobalAlias>(Val: V))
765 return visitGlobalAlias(GA&: *GA);
766 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Val: V))
767 return visitGlobalVariable(GV&: *GV);
768 if (UndefValue *UV = dyn_cast<UndefValue>(Val: V))
769 return visitUndefValue(*UV);
770
771 LLVM_DEBUG(dbgs() << "ObjectSizeOffsetVisitor::compute() unhandled value: "
772 << *V << '\n');
773 return ObjectSizeOffsetVisitor::unknown();
774}
775
776bool ObjectSizeOffsetVisitor::CheckedZextOrTrunc(APInt &I) {
777 return ::CheckedZextOrTrunc(I, IntTyBits);
778}
779
780SizeOffsetAPInt ObjectSizeOffsetVisitor::visitAllocaInst(AllocaInst &I) {
781 TypeSize ElemSize = DL.getTypeAllocSize(Ty: I.getAllocatedType());
782 if (ElemSize.isScalable() && Options.EvalMode != ObjectSizeOpts::Mode::Min)
783 return ObjectSizeOffsetVisitor::unknown();
784 APInt Size(IntTyBits, ElemSize.getKnownMinValue());
785 if (!I.isArrayAllocation())
786 return SizeOffsetAPInt(align(Size, Alignment: I.getAlign()), Zero);
787
788 Value *ArraySize = I.getArraySize();
789 if (const ConstantInt *C = dyn_cast<ConstantInt>(Val: ArraySize)) {
790 APInt NumElems = C->getValue();
791 if (!CheckedZextOrTrunc(I&: NumElems))
792 return ObjectSizeOffsetVisitor::unknown();
793
794 bool Overflow;
795 Size = Size.umul_ov(RHS: NumElems, Overflow);
796 return Overflow ? ObjectSizeOffsetVisitor::unknown()
797 : SizeOffsetAPInt(align(Size, Alignment: I.getAlign()), Zero);
798 }
799 return ObjectSizeOffsetVisitor::unknown();
800}
801
802SizeOffsetAPInt ObjectSizeOffsetVisitor::visitArgument(Argument &A) {
803 Type *MemoryTy = A.getPointeeInMemoryValueType();
804 // No interprocedural analysis is done at the moment.
805 if (!MemoryTy|| !MemoryTy->isSized()) {
806 ++ObjectVisitorArgument;
807 return ObjectSizeOffsetVisitor::unknown();
808 }
809
810 APInt Size(IntTyBits, DL.getTypeAllocSize(Ty: MemoryTy));
811 return SizeOffsetAPInt(align(Size, Alignment: A.getParamAlign()), Zero);
812}
813
814SizeOffsetAPInt ObjectSizeOffsetVisitor::visitCallBase(CallBase &CB) {
815 if (std::optional<APInt> Size = getAllocSize(CB: &CB, TLI))
816 return SizeOffsetAPInt(*Size, Zero);
817 return ObjectSizeOffsetVisitor::unknown();
818}
819
820SizeOffsetAPInt
821ObjectSizeOffsetVisitor::visitConstantPointerNull(ConstantPointerNull &CPN) {
822 // If null is unknown, there's nothing we can do. Additionally, non-zero
823 // address spaces can make use of null, so we don't presume to know anything
824 // about that.
825 //
826 // TODO: How should this work with address space casts? We currently just drop
827 // them on the floor, but it's unclear what we should do when a NULL from
828 // addrspace(1) gets casted to addrspace(0) (or vice-versa).
829 if (Options.NullIsUnknownSize || CPN.getType()->getAddressSpace())
830 return ObjectSizeOffsetVisitor::unknown();
831 return SizeOffsetAPInt(Zero, Zero);
832}
833
834SizeOffsetAPInt
835ObjectSizeOffsetVisitor::visitExtractElementInst(ExtractElementInst &) {
836 return ObjectSizeOffsetVisitor::unknown();
837}
838
839SizeOffsetAPInt
840ObjectSizeOffsetVisitor::visitExtractValueInst(ExtractValueInst &) {
841 // Easy cases were already folded by previous passes.
842 return ObjectSizeOffsetVisitor::unknown();
843}
844
845SizeOffsetAPInt ObjectSizeOffsetVisitor::visitGlobalAlias(GlobalAlias &GA) {
846 if (GA.isInterposable())
847 return ObjectSizeOffsetVisitor::unknown();
848 return computeImpl(V: GA.getAliasee());
849}
850
851SizeOffsetAPInt
852ObjectSizeOffsetVisitor::visitGlobalVariable(GlobalVariable &GV) {
853 if (!GV.getValueType()->isSized() || GV.hasExternalWeakLinkage() ||
854 ((!GV.hasInitializer() || GV.isInterposable()) &&
855 Options.EvalMode != ObjectSizeOpts::Mode::Min))
856 return ObjectSizeOffsetVisitor::unknown();
857
858 APInt Size(IntTyBits, DL.getTypeAllocSize(Ty: GV.getValueType()));
859 return SizeOffsetAPInt(align(Size, Alignment: GV.getAlign()), Zero);
860}
861
862SizeOffsetAPInt ObjectSizeOffsetVisitor::visitIntToPtrInst(IntToPtrInst &) {
863 // clueless
864 return ObjectSizeOffsetVisitor::unknown();
865}
866
867SizeOffsetAPInt ObjectSizeOffsetVisitor::findLoadSizeOffset(
868 LoadInst &Load, BasicBlock &BB, BasicBlock::iterator From,
869 SmallDenseMap<BasicBlock *, SizeOffsetAPInt, 8> &VisitedBlocks,
870 unsigned &ScannedInstCount) {
871 constexpr unsigned MaxInstsToScan = 128;
872
873 auto Where = VisitedBlocks.find(Val: &BB);
874 if (Where != VisitedBlocks.end())
875 return Where->second;
876
877 auto Unknown = [&BB, &VisitedBlocks]() {
878 return VisitedBlocks[&BB] = ObjectSizeOffsetVisitor::unknown();
879 };
880 auto Known = [&BB, &VisitedBlocks](SizeOffsetAPInt SO) {
881 return VisitedBlocks[&BB] = SO;
882 };
883
884 do {
885 Instruction &I = *From;
886
887 if (I.isDebugOrPseudoInst())
888 continue;
889
890 if (++ScannedInstCount > MaxInstsToScan)
891 return Unknown();
892
893 if (!I.mayWriteToMemory())
894 continue;
895
896 if (auto *SI = dyn_cast<StoreInst>(Val: &I)) {
897 AliasResult AR =
898 Options.AA->alias(V1: SI->getPointerOperand(), V2: Load.getPointerOperand());
899 switch ((AliasResult::Kind)AR) {
900 case AliasResult::NoAlias:
901 continue;
902 case AliasResult::MustAlias:
903 if (SI->getValueOperand()->getType()->isPointerTy())
904 return Known(computeImpl(V: SI->getValueOperand()));
905 else
906 return Unknown(); // No handling of non-pointer values by `compute`.
907 default:
908 return Unknown();
909 }
910 }
911
912 if (auto *CB = dyn_cast<CallBase>(Val: &I)) {
913 Function *Callee = CB->getCalledFunction();
914 // Bail out on indirect call.
915 if (!Callee)
916 return Unknown();
917
918 LibFunc TLIFn;
919 if (!TLI || !TLI->getLibFunc(FDecl: *CB->getCalledFunction(), F&: TLIFn) ||
920 !TLI->has(F: TLIFn))
921 return Unknown();
922
923 // TODO: There's probably more interesting case to support here.
924 if (TLIFn != LibFunc_posix_memalign)
925 return Unknown();
926
927 AliasResult AR =
928 Options.AA->alias(V1: CB->getOperand(i_nocapture: 0), V2: Load.getPointerOperand());
929 switch ((AliasResult::Kind)AR) {
930 case AliasResult::NoAlias:
931 continue;
932 case AliasResult::MustAlias:
933 break;
934 default:
935 return Unknown();
936 }
937
938 // Is the error status of posix_memalign correctly checked? If not it
939 // would be incorrect to assume it succeeds and load doesn't see the
940 // previous value.
941 std::optional<bool> Checked = isImpliedByDomCondition(
942 Pred: ICmpInst::ICMP_EQ, LHS: CB, RHS: ConstantInt::get(Ty: CB->getType(), V: 0), ContextI: &Load, DL);
943 if (!Checked || !*Checked)
944 return Unknown();
945
946 Value *Size = CB->getOperand(i_nocapture: 2);
947 auto *C = dyn_cast<ConstantInt>(Val: Size);
948 if (!C)
949 return Unknown();
950
951 return Known({C->getValue(), APInt(C->getValue().getBitWidth(), 0)});
952 }
953
954 return Unknown();
955 } while (From-- != BB.begin());
956
957 SmallVector<SizeOffsetAPInt> PredecessorSizeOffsets;
958 for (auto *PredBB : predecessors(BB: &BB)) {
959 PredecessorSizeOffsets.push_back(Elt: findLoadSizeOffset(
960 Load, BB&: *PredBB, From: BasicBlock::iterator(PredBB->getTerminator()),
961 VisitedBlocks, ScannedInstCount));
962 if (!PredecessorSizeOffsets.back().bothKnown())
963 return Unknown();
964 }
965
966 if (PredecessorSizeOffsets.empty())
967 return Unknown();
968
969 return Known(std::accumulate(
970 first: PredecessorSizeOffsets.begin() + 1, last: PredecessorSizeOffsets.end(),
971 init: PredecessorSizeOffsets.front(),
972 binary_op: [this](SizeOffsetAPInt LHS, SizeOffsetAPInt RHS) {
973 return combineSizeOffset(LHS, RHS);
974 }));
975}
976
977SizeOffsetAPInt ObjectSizeOffsetVisitor::visitLoadInst(LoadInst &LI) {
978 if (!Options.AA) {
979 ++ObjectVisitorLoad;
980 return ObjectSizeOffsetVisitor::unknown();
981 }
982
983 SmallDenseMap<BasicBlock *, SizeOffsetAPInt, 8> VisitedBlocks;
984 unsigned ScannedInstCount = 0;
985 SizeOffsetAPInt SO =
986 findLoadSizeOffset(Load&: LI, BB&: *LI.getParent(), From: BasicBlock::iterator(LI),
987 VisitedBlocks, ScannedInstCount);
988 if (!SO.bothKnown())
989 ++ObjectVisitorLoad;
990 return SO;
991}
992
993SizeOffsetAPInt
994ObjectSizeOffsetVisitor::combineSizeOffset(SizeOffsetAPInt LHS,
995 SizeOffsetAPInt RHS) {
996 if (!LHS.bothKnown() || !RHS.bothKnown())
997 return ObjectSizeOffsetVisitor::unknown();
998
999 switch (Options.EvalMode) {
1000 case ObjectSizeOpts::Mode::Min:
1001 return (getSizeWithOverflow(Data: LHS).slt(RHS: getSizeWithOverflow(Data: RHS))) ? LHS : RHS;
1002 case ObjectSizeOpts::Mode::Max:
1003 return (getSizeWithOverflow(Data: LHS).sgt(RHS: getSizeWithOverflow(Data: RHS))) ? LHS : RHS;
1004 case ObjectSizeOpts::Mode::ExactSizeFromOffset:
1005 return (getSizeWithOverflow(Data: LHS).eq(RHS: getSizeWithOverflow(Data: RHS)))
1006 ? LHS
1007 : ObjectSizeOffsetVisitor::unknown();
1008 case ObjectSizeOpts::Mode::ExactUnderlyingSizeAndOffset:
1009 return LHS == RHS ? LHS : ObjectSizeOffsetVisitor::unknown();
1010 }
1011 llvm_unreachable("missing an eval mode");
1012}
1013
1014SizeOffsetAPInt ObjectSizeOffsetVisitor::visitPHINode(PHINode &PN) {
1015 if (PN.getNumIncomingValues() == 0)
1016 return ObjectSizeOffsetVisitor::unknown();
1017 auto IncomingValues = PN.incoming_values();
1018 return std::accumulate(first: IncomingValues.begin() + 1, last: IncomingValues.end(),
1019 init: computeImpl(V: *IncomingValues.begin()),
1020 binary_op: [this](SizeOffsetAPInt LHS, Value *VRHS) {
1021 return combineSizeOffset(LHS, RHS: computeImpl(V: VRHS));
1022 });
1023}
1024
1025SizeOffsetAPInt ObjectSizeOffsetVisitor::visitSelectInst(SelectInst &I) {
1026 return combineSizeOffset(LHS: computeImpl(V: I.getTrueValue()),
1027 RHS: computeImpl(V: I.getFalseValue()));
1028}
1029
1030SizeOffsetAPInt ObjectSizeOffsetVisitor::visitUndefValue(UndefValue &) {
1031 return SizeOffsetAPInt(Zero, Zero);
1032}
1033
1034SizeOffsetAPInt ObjectSizeOffsetVisitor::visitInstruction(Instruction &I) {
1035 LLVM_DEBUG(dbgs() << "ObjectSizeOffsetVisitor unknown instruction:" << I
1036 << '\n');
1037 return ObjectSizeOffsetVisitor::unknown();
1038}
1039
1040// Just set these right here...
1041SizeOffsetValue::SizeOffsetValue(const SizeOffsetWeakTrackingVH &SOT)
1042 : SizeOffsetType(SOT.Size, SOT.Offset) {}
1043
1044ObjectSizeOffsetEvaluator::ObjectSizeOffsetEvaluator(
1045 const DataLayout &DL, const TargetLibraryInfo *TLI, LLVMContext &Context,
1046 ObjectSizeOpts EvalOpts)
1047 : DL(DL), TLI(TLI), Context(Context),
1048 Builder(Context, TargetFolder(DL),
1049 IRBuilderCallbackInserter(
1050 [&](Instruction *I) { InsertedInstructions.insert(Ptr: I); })),
1051 EvalOpts(EvalOpts) {
1052 // IntTy and Zero must be set for each compute() since the address space may
1053 // be different for later objects.
1054}
1055
1056SizeOffsetValue ObjectSizeOffsetEvaluator::compute(Value *V) {
1057 // XXX - Are vectors of pointers possible here?
1058 IntTy = cast<IntegerType>(Val: DL.getIndexType(PtrTy: V->getType()));
1059 Zero = ConstantInt::get(Ty: IntTy, V: 0);
1060
1061 SizeOffsetValue Result = compute_(V);
1062
1063 if (!Result.bothKnown()) {
1064 // Erase everything that was computed in this iteration from the cache, so
1065 // that no dangling references are left behind. We could be a bit smarter if
1066 // we kept a dependency graph. It's probably not worth the complexity.
1067 for (const Value *SeenVal : SeenVals) {
1068 CacheMapTy::iterator CacheIt = CacheMap.find(Val: SeenVal);
1069 // non-computable results can be safely cached
1070 if (CacheIt != CacheMap.end() && CacheIt->second.anyKnown())
1071 CacheMap.erase(I: CacheIt);
1072 }
1073
1074 // Erase any instructions we inserted as part of the traversal.
1075 for (Instruction *I : InsertedInstructions) {
1076 I->replaceAllUsesWith(V: PoisonValue::get(T: I->getType()));
1077 I->eraseFromParent();
1078 }
1079 }
1080
1081 SeenVals.clear();
1082 InsertedInstructions.clear();
1083 return Result;
1084}
1085
1086SizeOffsetValue ObjectSizeOffsetEvaluator::compute_(Value *V) {
1087 ObjectSizeOffsetVisitor Visitor(DL, TLI, Context, EvalOpts);
1088 SizeOffsetAPInt Const = Visitor.compute(V);
1089 if (Const.bothKnown())
1090 return SizeOffsetValue(ConstantInt::get(Context, V: Const.Size),
1091 ConstantInt::get(Context, V: Const.Offset));
1092
1093 V = V->stripPointerCasts();
1094
1095 // Check cache.
1096 CacheMapTy::iterator CacheIt = CacheMap.find(Val: V);
1097 if (CacheIt != CacheMap.end())
1098 return CacheIt->second;
1099
1100 // Always generate code immediately before the instruction being
1101 // processed, so that the generated code dominates the same BBs.
1102 BuilderTy::InsertPointGuard Guard(Builder);
1103 if (Instruction *I = dyn_cast<Instruction>(Val: V))
1104 Builder.SetInsertPoint(I);
1105
1106 // Now compute the size and offset.
1107 SizeOffsetValue Result;
1108
1109 // Record the pointers that were handled in this run, so that they can be
1110 // cleaned later if something fails. We also use this set to break cycles that
1111 // can occur in dead code.
1112 if (!SeenVals.insert(Ptr: V).second) {
1113 Result = ObjectSizeOffsetEvaluator::unknown();
1114 } else if (GEPOperator *GEP = dyn_cast<GEPOperator>(Val: V)) {
1115 Result = visitGEPOperator(GEP&: *GEP);
1116 } else if (Instruction *I = dyn_cast<Instruction>(Val: V)) {
1117 Result = visit(I&: *I);
1118 } else if (isa<Argument>(Val: V) ||
1119 (isa<ConstantExpr>(Val: V) &&
1120 cast<ConstantExpr>(Val: V)->getOpcode() == Instruction::IntToPtr) ||
1121 isa<GlobalAlias>(Val: V) ||
1122 isa<GlobalVariable>(Val: V)) {
1123 // Ignore values where we cannot do more than ObjectSizeVisitor.
1124 Result = ObjectSizeOffsetEvaluator::unknown();
1125 } else {
1126 LLVM_DEBUG(
1127 dbgs() << "ObjectSizeOffsetEvaluator::compute() unhandled value: " << *V
1128 << '\n');
1129 Result = ObjectSizeOffsetEvaluator::unknown();
1130 }
1131
1132 // Don't reuse CacheIt since it may be invalid at this point.
1133 CacheMap[V] = SizeOffsetWeakTrackingVH(Result);
1134 return Result;
1135}
1136
1137SizeOffsetValue ObjectSizeOffsetEvaluator::visitAllocaInst(AllocaInst &I) {
1138 if (!I.getAllocatedType()->isSized())
1139 return ObjectSizeOffsetEvaluator::unknown();
1140
1141 // must be a VLA or vscale.
1142 assert(I.isArrayAllocation() || I.getAllocatedType()->isScalableTy());
1143
1144 // If needed, adjust the alloca's operand size to match the pointer indexing
1145 // size. Subsequent math operations expect the types to match.
1146 Value *ArraySize = Builder.CreateZExtOrTrunc(
1147 V: I.getArraySize(),
1148 DestTy: DL.getIndexType(C&: I.getContext(), AddressSpace: DL.getAllocaAddrSpace()));
1149 assert(ArraySize->getType() == Zero->getType() &&
1150 "Expected zero constant to have pointer index type");
1151
1152 Value *Size = Builder.CreateTypeSize(
1153 DstType: ArraySize->getType(), Size: DL.getTypeAllocSize(Ty: I.getAllocatedType()));
1154 Size = Builder.CreateMul(LHS: Size, RHS: ArraySize);
1155 return SizeOffsetValue(Size, Zero);
1156}
1157
1158SizeOffsetValue ObjectSizeOffsetEvaluator::visitCallBase(CallBase &CB) {
1159 std::optional<AllocFnsTy> FnData = getAllocationSize(V: &CB, TLI);
1160 if (!FnData)
1161 return ObjectSizeOffsetEvaluator::unknown();
1162
1163 // Handle strdup-like functions separately.
1164 if (FnData->AllocTy == StrDupLike) {
1165 // TODO: implement evaluation of strdup/strndup
1166 return ObjectSizeOffsetEvaluator::unknown();
1167 }
1168
1169 Value *FirstArg = CB.getArgOperand(i: FnData->FstParam);
1170 FirstArg = Builder.CreateZExtOrTrunc(V: FirstArg, DestTy: IntTy);
1171 if (FnData->SndParam < 0)
1172 return SizeOffsetValue(FirstArg, Zero);
1173
1174 Value *SecondArg = CB.getArgOperand(i: FnData->SndParam);
1175 SecondArg = Builder.CreateZExtOrTrunc(V: SecondArg, DestTy: IntTy);
1176 Value *Size = Builder.CreateMul(LHS: FirstArg, RHS: SecondArg);
1177 return SizeOffsetValue(Size, Zero);
1178}
1179
1180SizeOffsetValue
1181ObjectSizeOffsetEvaluator::visitExtractElementInst(ExtractElementInst &) {
1182 return ObjectSizeOffsetEvaluator::unknown();
1183}
1184
1185SizeOffsetValue
1186ObjectSizeOffsetEvaluator::visitExtractValueInst(ExtractValueInst &) {
1187 return ObjectSizeOffsetEvaluator::unknown();
1188}
1189
1190SizeOffsetValue ObjectSizeOffsetEvaluator::visitGEPOperator(GEPOperator &GEP) {
1191 SizeOffsetValue PtrData = compute_(V: GEP.getPointerOperand());
1192 if (!PtrData.bothKnown())
1193 return ObjectSizeOffsetEvaluator::unknown();
1194
1195 Value *Offset = emitGEPOffset(Builder: &Builder, DL, GEP: &GEP, /*NoAssumptions=*/true);
1196 Offset = Builder.CreateAdd(LHS: PtrData.Offset, RHS: Offset);
1197 return SizeOffsetValue(PtrData.Size, Offset);
1198}
1199
1200SizeOffsetValue ObjectSizeOffsetEvaluator::visitIntToPtrInst(IntToPtrInst &) {
1201 // clueless
1202 return ObjectSizeOffsetEvaluator::unknown();
1203}
1204
1205SizeOffsetValue ObjectSizeOffsetEvaluator::visitLoadInst(LoadInst &LI) {
1206 return ObjectSizeOffsetEvaluator::unknown();
1207}
1208
1209SizeOffsetValue ObjectSizeOffsetEvaluator::visitPHINode(PHINode &PHI) {
1210 // Create 2 PHIs: one for size and another for offset.
1211 PHINode *SizePHI = Builder.CreatePHI(Ty: IntTy, NumReservedValues: PHI.getNumIncomingValues());
1212 PHINode *OffsetPHI = Builder.CreatePHI(Ty: IntTy, NumReservedValues: PHI.getNumIncomingValues());
1213
1214 // Insert right away in the cache to handle recursive PHIs.
1215 CacheMap[&PHI] = SizeOffsetWeakTrackingVH(SizePHI, OffsetPHI);
1216
1217 // Compute offset/size for each PHI incoming pointer.
1218 for (unsigned i = 0, e = PHI.getNumIncomingValues(); i != e; ++i) {
1219 BasicBlock *IncomingBlock = PHI.getIncomingBlock(i);
1220 Builder.SetInsertPoint(TheBB: IncomingBlock, IP: IncomingBlock->getFirstInsertionPt());
1221 SizeOffsetValue EdgeData = compute_(V: PHI.getIncomingValue(i));
1222
1223 if (!EdgeData.bothKnown()) {
1224 OffsetPHI->replaceAllUsesWith(V: PoisonValue::get(T: IntTy));
1225 OffsetPHI->eraseFromParent();
1226 InsertedInstructions.erase(Ptr: OffsetPHI);
1227 SizePHI->replaceAllUsesWith(V: PoisonValue::get(T: IntTy));
1228 SizePHI->eraseFromParent();
1229 InsertedInstructions.erase(Ptr: SizePHI);
1230 return ObjectSizeOffsetEvaluator::unknown();
1231 }
1232 SizePHI->addIncoming(V: EdgeData.Size, BB: IncomingBlock);
1233 OffsetPHI->addIncoming(V: EdgeData.Offset, BB: IncomingBlock);
1234 }
1235
1236 Value *Size = SizePHI, *Offset = OffsetPHI;
1237 if (Value *Tmp = SizePHI->hasConstantValue()) {
1238 Size = Tmp;
1239 SizePHI->replaceAllUsesWith(V: Size);
1240 SizePHI->eraseFromParent();
1241 InsertedInstructions.erase(Ptr: SizePHI);
1242 }
1243 if (Value *Tmp = OffsetPHI->hasConstantValue()) {
1244 Offset = Tmp;
1245 OffsetPHI->replaceAllUsesWith(V: Offset);
1246 OffsetPHI->eraseFromParent();
1247 InsertedInstructions.erase(Ptr: OffsetPHI);
1248 }
1249 return SizeOffsetValue(Size, Offset);
1250}
1251
1252SizeOffsetValue ObjectSizeOffsetEvaluator::visitSelectInst(SelectInst &I) {
1253 SizeOffsetValue TrueSide = compute_(V: I.getTrueValue());
1254 SizeOffsetValue FalseSide = compute_(V: I.getFalseValue());
1255
1256 if (!TrueSide.bothKnown() || !FalseSide.bothKnown())
1257 return ObjectSizeOffsetEvaluator::unknown();
1258 if (TrueSide == FalseSide)
1259 return TrueSide;
1260
1261 Value *Size =
1262 Builder.CreateSelect(C: I.getCondition(), True: TrueSide.Size, False: FalseSide.Size);
1263 Value *Offset =
1264 Builder.CreateSelect(C: I.getCondition(), True: TrueSide.Offset, False: FalseSide.Offset);
1265 return SizeOffsetValue(Size, Offset);
1266}
1267
1268SizeOffsetValue ObjectSizeOffsetEvaluator::visitInstruction(Instruction &I) {
1269 LLVM_DEBUG(dbgs() << "ObjectSizeOffsetEvaluator unknown instruction:" << I
1270 << '\n');
1271 return ObjectSizeOffsetEvaluator::unknown();
1272}
1273