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