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