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