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/ProfDataUtils.h"
36#include "llvm/IR/Type.h"
37#include "llvm/IR/Value.h"
38#include "llvm/Support/Casting.h"
39#include "llvm/Support/CommandLine.h"
40#include "llvm/Support/Debug.h"
41#include "llvm/Support/MathExtras.h"
42#include "llvm/Support/raw_ostream.h"
43#include <cassert>
44#include <cstdint>
45#include <iterator>
46#include <numeric>
47#include <optional>
48#include <utility>
49
50using namespace llvm;
51
52#define DEBUG_TYPE "memory-builtins"
53
54namespace llvm {
55extern cl::opt<bool> ProfcheckDisableMetadataFixes;
56}
57
58static cl::opt<unsigned> ObjectSizeOffsetVisitorMaxVisitInstructions(
59 "object-size-offset-visitor-max-visit-instructions",
60 cl::desc("Maximum number of instructions for ObjectSizeOffsetVisitor to "
61 "look at"),
62 cl::init(Val: 100));
63
64// clang-format off
65enum AllocType : uint8_t {
66 OpNewLike = 1<<0, // allocates; never returns null
67 MallocLike = 1<<1, // allocates; may return null
68 StrDupLike = 1<<2,
69 MallocOrOpNewLike = MallocLike | OpNewLike,
70 AllocLike = MallocOrOpNewLike | StrDupLike,
71 AnyAlloc = AllocLike
72};
73
74enum class MallocFamily {
75 Malloc,
76 CPPNew, // new(unsigned int)
77 CPPNewAligned, // new(unsigned int, align_val_t)
78 CPPNewArray, // new[](unsigned int)
79 CPPNewArrayAligned, // new[](unsigned long, align_val_t)
80 MSVCNew, // new(unsigned int)
81 MSVCArrayNew, // new[](unsigned int)
82 VecMalloc,
83};
84// clang-format on
85
86static StringRef mangledNameForMallocFamily(const MallocFamily &Family) {
87 switch (Family) {
88 case MallocFamily::Malloc:
89 return "malloc";
90 case MallocFamily::CPPNew:
91 return "_Znwm";
92 case MallocFamily::CPPNewAligned:
93 return "_ZnwmSt11align_val_t";
94 case MallocFamily::CPPNewArray:
95 return "_Znam";
96 case MallocFamily::CPPNewArrayAligned:
97 return "_ZnamSt11align_val_t";
98 case MallocFamily::MSVCNew:
99 return "??2@YAPAXI@Z";
100 case MallocFamily::MSVCArrayNew:
101 return "??_U@YAPAXI@Z";
102 case MallocFamily::VecMalloc:
103 return "vec_malloc";
104 }
105 llvm_unreachable("missing an alloc family");
106}
107
108struct AllocFnsTy {
109 AllocType AllocTy;
110 unsigned NumParams;
111 // First and Second size parameters (or -1 if unused)
112 int FstParam, SndParam;
113 // Alignment parameter for aligned_alloc and aligned new
114 int AlignParam;
115 // Name of default allocator function to group malloc/free calls by family
116 MallocFamily Family;
117};
118
119// clang-format off
120// FIXME: certain users need more information. E.g., SimplifyLibCalls needs to
121// know which functions are nounwind, noalias, nocapture parameters, etc.
122static const std::pair<LibFunc, AllocFnsTy> AllocationFnData[] = {
123 {LibFunc_Znwj, {.AllocTy: OpNewLike, .NumParams: 1, .FstParam: 0, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::CPPNew}}, // new(unsigned int)
124 {LibFunc_ZnwjRKSt9nothrow_t, {.AllocTy: MallocLike, .NumParams: 2, .FstParam: 0, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::CPPNew}}, // new(unsigned int, nothrow)
125 {LibFunc_ZnwjSt11align_val_t, {.AllocTy: OpNewLike, .NumParams: 2, .FstParam: 0, .SndParam: -1, .AlignParam: 1, .Family: MallocFamily::CPPNewAligned}}, // new(unsigned int, align_val_t)
126 {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)
127 {LibFunc_Znwm, {.AllocTy: OpNewLike, .NumParams: 1, .FstParam: 0, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::CPPNew}}, // new(unsigned long)
128 {LibFunc_Znwm12__hot_cold_t, {.AllocTy: OpNewLike, .NumParams: 2, .FstParam: 0, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::CPPNew}}, // new(unsigned long, __hot_cold_t)
129 {LibFunc_ZnwmRKSt9nothrow_t, {.AllocTy: MallocLike, .NumParams: 2, .FstParam: 0, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::CPPNew}}, // new(unsigned long, nothrow)
130 {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)
131 {LibFunc_ZnwmSt11align_val_t, {.AllocTy: OpNewLike, .NumParams: 2, .FstParam: 0, .SndParam: -1, .AlignParam: 1, .Family: MallocFamily::CPPNewAligned}}, // new(unsigned long, align_val_t)
132 {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)
133 {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)
134 {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)
135 {LibFunc_Znaj, {.AllocTy: OpNewLike, .NumParams: 1, .FstParam: 0, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::CPPNewArray}}, // new[](unsigned int)
136 {LibFunc_ZnajRKSt9nothrow_t, {.AllocTy: MallocLike, .NumParams: 2, .FstParam: 0, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::CPPNewArray}}, // new[](unsigned int, nothrow)
137 {LibFunc_ZnajSt11align_val_t, {.AllocTy: OpNewLike, .NumParams: 2, .FstParam: 0, .SndParam: -1, .AlignParam: 1, .Family: MallocFamily::CPPNewArrayAligned}}, // new[](unsigned int, align_val_t)
138 {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)
139 {LibFunc_Znam, {.AllocTy: OpNewLike, .NumParams: 1, .FstParam: 0, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::CPPNewArray}}, // new[](unsigned long)
140 {LibFunc_Znam12__hot_cold_t, {.AllocTy: OpNewLike, .NumParams: 2, .FstParam: 0, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::CPPNew}}, // new[](unsigned long, __hot_cold_t)
141 {LibFunc_ZnamRKSt9nothrow_t, {.AllocTy: MallocLike, .NumParams: 2, .FstParam: 0, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::CPPNewArray}}, // new[](unsigned long, nothrow)
142 {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)
143 {LibFunc_ZnamSt11align_val_t, {.AllocTy: OpNewLike, .NumParams: 2, .FstParam: 0, .SndParam: -1, .AlignParam: 1, .Family: MallocFamily::CPPNewArrayAligned}}, // new[](unsigned long, align_val_t)
144 {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)
145 {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)
146 {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)
147 {LibFunc_msvc_new_int, {.AllocTy: OpNewLike, .NumParams: 1, .FstParam: 0, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::MSVCNew}}, // new(unsigned int)
148 {LibFunc_msvc_new_int_nothrow, {.AllocTy: MallocLike, .NumParams: 2, .FstParam: 0, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::MSVCNew}}, // new(unsigned int, nothrow)
149 {LibFunc_msvc_new_longlong, {.AllocTy: OpNewLike, .NumParams: 1, .FstParam: 0, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::MSVCNew}}, // new(unsigned long long)
150 {LibFunc_msvc_new_longlong_nothrow, {.AllocTy: MallocLike, .NumParams: 2, .FstParam: 0, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::MSVCNew}}, // new(unsigned long long, nothrow)
151 {LibFunc_msvc_new_array_int, {.AllocTy: OpNewLike, .NumParams: 1, .FstParam: 0, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::MSVCArrayNew}}, // new[](unsigned int)
152 {LibFunc_msvc_new_array_int_nothrow, {.AllocTy: MallocLike, .NumParams: 2, .FstParam: 0, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::MSVCArrayNew}}, // new[](unsigned int, nothrow)
153 {LibFunc_msvc_new_array_longlong, {.AllocTy: OpNewLike, .NumParams: 1, .FstParam: 0, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::MSVCArrayNew}}, // new[](unsigned long long)
154 {LibFunc_msvc_new_array_longlong_nothrow, {.AllocTy: MallocLike, .NumParams: 2, .FstParam: 0, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::MSVCArrayNew}}, // new[](unsigned long long, nothrow)
155 {LibFunc_strdup, {.AllocTy: StrDupLike, .NumParams: 1, .FstParam: -1, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::Malloc}},
156 {LibFunc_dunder_strdup, {.AllocTy: StrDupLike, .NumParams: 1, .FstParam: -1, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::Malloc}},
157 {LibFunc_strndup, {.AllocTy: StrDupLike, .NumParams: 2, .FstParam: 1, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::Malloc}},
158 {LibFunc_dunder_strndup, {.AllocTy: StrDupLike, .NumParams: 2, .FstParam: 1, .SndParam: -1, .AlignParam: -1, .Family: MallocFamily::Malloc}},
159};
160// clang-format on
161
162static const Function *getCalledFunction(const Value *V) {
163 // Don't care about intrinsics in this case.
164 if (isa<IntrinsicInst>(Val: V))
165 return nullptr;
166
167 const auto *CB = dyn_cast<CallBase>(Val: V);
168 if (!CB)
169 return nullptr;
170
171 if (CB->isNoBuiltin())
172 return nullptr;
173
174 return CB->getCalledFunction();
175}
176
177/// Returns the allocation data for the given value if it's a call to a known
178/// allocation function.
179static std::optional<AllocFnsTy>
180getAllocationDataForFunction(const Function *Callee, AllocType AllocTy,
181 const TargetLibraryInfo *TLI) {
182 // Don't perform a slow TLI lookup, if this function doesn't return a pointer
183 // and thus can't be an allocation function.
184 if (!Callee->getReturnType()->isPointerTy())
185 return std::nullopt;
186
187 // Make sure that the function is available.
188 if (!TLI)
189 return std::nullopt;
190
191 LibFunc TLIFn = TLI->getLibFunc(FDecl: *Callee);
192 if (!TLI->has(F: TLIFn))
193 return std::nullopt;
194
195 const auto *Iter = find_if(Range: AllocationFnData,
196 P: [TLIFn](const std::pair<LibFunc, AllocFnsTy> &P) {
197 return P.first == TLIFn;
198 });
199
200 if (Iter == std::end(arr: AllocationFnData))
201 return std::nullopt;
202
203 const AllocFnsTy *FnData = &Iter->second;
204 if ((FnData->AllocTy & AllocTy) != FnData->AllocTy)
205 return std::nullopt;
206
207 // Check function prototype.
208 int FstParam = FnData->FstParam;
209 int SndParam = FnData->SndParam;
210 FunctionType *FTy = Callee->getFunctionType();
211
212 if (FTy->getReturnType()->isPointerTy() &&
213 FTy->getNumParams() == FnData->NumParams &&
214 (FstParam < 0 || (FTy->getParamType(i: FstParam)->isIntegerTy(BitWidth: 32) ||
215 FTy->getParamType(i: FstParam)->isIntegerTy(BitWidth: 64))) &&
216 (SndParam < 0 || FTy->getParamType(i: SndParam)->isIntegerTy(BitWidth: 32) ||
217 FTy->getParamType(i: SndParam)->isIntegerTy(BitWidth: 64)))
218 return *FnData;
219 return std::nullopt;
220}
221
222static std::optional<AllocFnsTy>
223getAllocationData(const Value *V, AllocType AllocTy,
224 const TargetLibraryInfo *TLI) {
225 if (const Function *Callee = getCalledFunction(V))
226 return getAllocationDataForFunction(Callee, AllocTy, TLI);
227 return std::nullopt;
228}
229
230static std::optional<AllocFnsTy>
231getAllocationData(const Value *V, AllocType AllocTy,
232 function_ref<const TargetLibraryInfo &(Function &)> GetTLI) {
233 if (const Function *Callee = getCalledFunction(V))
234 return getAllocationDataForFunction(
235 Callee, AllocTy, TLI: &GetTLI(const_cast<Function &>(*Callee)));
236 return std::nullopt;
237}
238
239static std::optional<AllocFnsTy>
240getAllocationSize(const CallBase *CB, const TargetLibraryInfo *TLI) {
241 if (const Function *Callee = getCalledFunction(V: CB)) {
242 // Prefer to use existing information over allocsize. This will give us an
243 // accurate AllocTy.
244 if (std::optional<AllocFnsTy> Data =
245 getAllocationDataForFunction(Callee, AllocTy: AnyAlloc, TLI))
246 return Data;
247 }
248
249 Attribute Attr = CB->getFnAttr(Kind: Attribute::AllocSize);
250 if (Attr == Attribute())
251 return std::nullopt;
252
253 std::pair<unsigned, std::optional<unsigned>> Args = Attr.getAllocSizeArgs();
254
255 AllocFnsTy Result;
256 // Because allocsize only tells us how many bytes are allocated, we're not
257 // really allowed to assume anything, so we use MallocLike.
258 Result.AllocTy = MallocLike;
259 Result.NumParams = CB->arg_size();
260 Result.FstParam = Args.first;
261 Result.SndParam = Args.second.value_or(u: -1);
262 // Allocsize has no way to specify an alignment argument
263 Result.AlignParam = -1;
264 return Result;
265}
266
267static AllocFnKind getAllocFnKind(const Value *V) {
268 if (const auto *CB = dyn_cast<CallBase>(Val: V)) {
269 Attribute Attr = CB->getFnAttr(Kind: Attribute::AllocKind);
270 if (Attr.isValid())
271 return AllocFnKind(Attr.getValueAsInt());
272 }
273 return AllocFnKind::Unknown;
274}
275
276static AllocFnKind getAllocFnKind(const Function *F) {
277 return F->getAttributes().getAllocKind();
278}
279
280static bool checkFnAllocKind(const Value *V, AllocFnKind Wanted) {
281 return (getAllocFnKind(V) & Wanted) != AllocFnKind::Unknown;
282}
283
284static bool checkFnAllocKind(const Function *F, AllocFnKind Wanted) {
285 return (getAllocFnKind(F) & Wanted) != AllocFnKind::Unknown;
286}
287
288/// Tests if a value is a call or invoke to a library function that
289/// allocates or reallocates memory (either malloc, calloc, realloc, or strdup
290/// like).
291bool llvm::isAllocationFn(const Value *V, const TargetLibraryInfo *TLI) {
292 return getAllocationData(V, AllocTy: AnyAlloc, TLI).has_value() ||
293 checkFnAllocKind(V, Wanted: AllocFnKind::Alloc | AllocFnKind::Realloc);
294}
295bool llvm::isAllocationFn(
296 const Value *V,
297 function_ref<const TargetLibraryInfo &(Function &)> GetTLI) {
298 return getAllocationData(V, AllocTy: AnyAlloc, GetTLI).has_value() ||
299 checkFnAllocKind(V, Wanted: AllocFnKind::Alloc | AllocFnKind::Realloc);
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 = TLI ? TLI->getLibFunc(FDecl: *Callee) : NotLibFunc;
496 if (TLIFn != NotLibFunc && 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 = TLI ? TLI->getLibFunc(FDecl: *Callee) : NotLibFunc;
541 if (TLIFn != NotLibFunc && 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 ObjectSizeOffsetEvaluator Eval(*ObjectSize->getModule(), TLI, EvalOptions);
677 SizeOffsetValue SizeOffsetPair = Eval.compute(V: ObjectSize->getArgOperand(i: 0));
678
679 if (SizeOffsetPair != ObjectSizeOffsetEvaluator::unknown()) {
680 IRBuilder<TargetFolder, IRBuilderCallbackInserter> Builder(
681 ObjectSize->getIterator(), TargetFolder(DL),
682 IRBuilderCallbackInserter([&](Instruction *I) {
683 if (InsertedInstructions)
684 InsertedInstructions->push_back(Elt: I);
685 }));
686
687 Value *Size = SizeOffsetPair.Size;
688 Value *Offset = SizeOffsetPair.Offset;
689
690 // If we've outside the end of the object, then we can always access
691 // exactly 0 bytes.
692 Value *ResultSize = Builder.CreateSub(LHS: Size, RHS: Offset);
693 Value *UseZero = Builder.CreateICmpULT(LHS: Size, RHS: Offset);
694 ResultSize = Builder.CreateZExtOrTrunc(V: ResultSize, DestTy: ResultType);
695 Value *Ret = Builder.CreateSelect(
696 C: UseZero, True: ConstantInt::get(Ty: ResultType, V: 0), False: ResultSize);
697
698 // The non-constant size expression cannot evaluate to -1.
699 if (!isa<Constant>(Val: Size) || !isa<Constant>(Val: Offset))
700 Builder.CreateAssumption(Cond: Builder.CreateICmpNE(
701 LHS: Ret, RHS: ConstantInt::getAllOnesValue(Ty: ResultType)));
702
703 return Ret;
704 }
705 }
706
707 if (!MustSucceed)
708 return nullptr;
709
710 return MaxVal ? Constant::getAllOnesValue(Ty: ResultType)
711 : Constant::getNullValue(Ty: ResultType);
712}
713
714STATISTIC(ObjectVisitorArgument,
715 "Number of arguments with unsolved size and offset");
716STATISTIC(ObjectVisitorLoad,
717 "Number of load instructions with unsolved size and offset");
718
719static std::optional<APInt>
720combinePossibleConstantValues(std::optional<APInt> LHS,
721 std::optional<APInt> RHS,
722 ObjectSizeOpts::Mode EvalMode) {
723 if (!LHS || !RHS)
724 return std::nullopt;
725 if (EvalMode == ObjectSizeOpts::Mode::Max)
726 return LHS->sge(RHS: *RHS) ? *LHS : *RHS;
727 return LHS->sle(RHS: *RHS) ? *LHS : *RHS;
728}
729
730static std::optional<APInt> aggregatePossibleConstantValuesImpl(
731 const Value *V, ObjectSizeOpts::Mode EvalMode, unsigned BitWidth,
732 unsigned RecursionDepth) {
733 constexpr unsigned MaxRecursionDepth = 4;
734 if (RecursionDepth == MaxRecursionDepth)
735 return std::nullopt;
736
737 if (const auto *CI = dyn_cast<ConstantInt>(Val: V)) {
738 return CI->getValue().sextOrTrunc(width: BitWidth);
739 } else if (const auto *SI = dyn_cast<SelectInst>(Val: V)) {
740 return combinePossibleConstantValues(
741 LHS: aggregatePossibleConstantValuesImpl(V: SI->getTrueValue(), EvalMode,
742 BitWidth, RecursionDepth: RecursionDepth + 1),
743 RHS: aggregatePossibleConstantValuesImpl(V: SI->getFalseValue(), EvalMode,
744 BitWidth, RecursionDepth: RecursionDepth + 1),
745 EvalMode);
746 } else if (const auto *PN = dyn_cast<PHINode>(Val: V)) {
747 unsigned Count = PN->getNumIncomingValues();
748 if (Count == 0)
749 return std::nullopt;
750 auto Acc = aggregatePossibleConstantValuesImpl(
751 V: PN->getIncomingValue(i: 0), EvalMode, BitWidth, RecursionDepth: RecursionDepth + 1);
752 for (unsigned I = 1; Acc && I < Count; ++I) {
753 auto Tmp = aggregatePossibleConstantValuesImpl(
754 V: PN->getIncomingValue(i: I), EvalMode, BitWidth, RecursionDepth: RecursionDepth + 1);
755 Acc = combinePossibleConstantValues(LHS: Acc, RHS: Tmp, EvalMode);
756 }
757 return Acc;
758 }
759
760 return std::nullopt;
761}
762
763static std::optional<APInt>
764aggregatePossibleConstantValues(const Value *V, ObjectSizeOpts::Mode EvalMode,
765 unsigned BitWidth) {
766 if (auto *CI = dyn_cast<ConstantInt>(Val: V))
767 return CI->getValue().sextOrTrunc(width: BitWidth);
768
769 if (EvalMode != ObjectSizeOpts::Mode::Min &&
770 EvalMode != ObjectSizeOpts::Mode::Max)
771 return std::nullopt;
772
773 // Not using computeConstantRange here because we cannot guarantee it's not
774 // doing optimization based on UB which we want to avoid when expanding
775 // __builtin_object_size.
776 return aggregatePossibleConstantValuesImpl(V, EvalMode, BitWidth, RecursionDepth: 0u);
777}
778
779/// Align \p Size according to \p Alignment. If \p Size is greater than
780/// getSignedMaxValue(), set it as unknown as we can only represent signed value
781/// in OffsetSpan.
782APInt ObjectSizeOffsetVisitor::align(APInt Size, MaybeAlign Alignment) {
783 if (Options.RoundToAlign && Alignment)
784 Size = APInt(IntTyBits, alignTo(Size: Size.getZExtValue(), A: *Alignment));
785
786 return Size.isNegative() ? APInt() : Size;
787}
788
789ObjectSizeOffsetVisitor::ObjectSizeOffsetVisitor(const DataLayout &DL,
790 const TargetLibraryInfo *TLI,
791 LLVMContext &Context,
792 ObjectSizeOpts Options)
793 : DL(DL), TLI(TLI), Options(Options) {
794 // Pointer size must be rechecked for each object visited since it could have
795 // a different address space.
796}
797
798SizeOffsetAPInt ObjectSizeOffsetVisitor::compute(Value *V) {
799 InstructionsVisited = 0;
800 OffsetSpan Span = computeImpl(V);
801
802 // In ExactSizeFromOffset mode, we don't care about the Before Field, so allow
803 // us to overwrite it if needs be.
804 if (Span.knownAfter() && !Span.knownBefore() &&
805 Options.EvalMode == ObjectSizeOpts::Mode::ExactSizeFromOffset)
806 Span.Before = APInt::getZero(numBits: Span.After.getBitWidth());
807
808 if (!Span.bothKnown())
809 return {};
810
811 return {Span.Before + Span.After, Span.Before};
812}
813
814OffsetSpan ObjectSizeOffsetVisitor::computeImpl(Value *V) {
815 unsigned InitialIntTyBits = DL.getIndexTypeSizeInBits(Ty: V->getType());
816
817 // Stripping pointer casts can strip address space casts which can change the
818 // index type size. The invariant is that we use the value type to determine
819 // the index type size and if we stripped address space casts we have to
820 // readjust the APInt as we pass it upwards in order for the APInt to match
821 // the type the caller passed in.
822 APInt Offset(InitialIntTyBits, 0);
823 V = V->stripAndAccumulateConstantOffsets(
824 DL, Offset, /* AllowNonInbounds */ true, /* AllowInvariantGroup */ true);
825
826 // Give it another try with approximated analysis. We don't start with this
827 // one because stripAndAccumulateConstantOffsets behaves differently wrt.
828 // overflows if we provide an external Analysis.
829 if ((Options.EvalMode == ObjectSizeOpts::Mode::Min ||
830 Options.EvalMode == ObjectSizeOpts::Mode::Max) &&
831 isa<GEPOperator>(Val: V)) {
832 // External Analysis used to compute the Min/Max value of individual Offsets
833 // within a GEP.
834 ObjectSizeOpts::Mode EvalMode =
835 Options.EvalMode == ObjectSizeOpts::Mode::Min
836 ? ObjectSizeOpts::Mode::Max
837 : ObjectSizeOpts::Mode::Min;
838 // For a GEPOperator the indices are first converted to offsets in the
839 // pointer’s index type, so we need to provide the index type to make sure
840 // the min/max operations are performed in correct type.
841 unsigned IdxTyBits = DL.getIndexTypeSizeInBits(Ty: V->getType());
842 auto OffsetRangeAnalysis = [EvalMode, IdxTyBits](Value &VOffset,
843 APInt &Offset) {
844 if (auto PossibleOffset =
845 aggregatePossibleConstantValues(V: &VOffset, EvalMode, BitWidth: IdxTyBits)) {
846 Offset = *PossibleOffset;
847 return true;
848 }
849 return false;
850 };
851
852 V = V->stripAndAccumulateConstantOffsets(
853 DL, Offset, /* AllowNonInbounds */ true, /* AllowInvariantGroup */ true,
854 /*ExternalAnalysis=*/OffsetRangeAnalysis);
855 }
856
857 // Later we use the index type size and zero but it will match the type of the
858 // value that is passed to computeImpl.
859 IntTyBits = DL.getIndexTypeSizeInBits(Ty: V->getType());
860 Zero = APInt::getZero(numBits: IntTyBits);
861 OffsetSpan ORT = computeValue(V);
862
863 bool IndexTypeSizeChanged = InitialIntTyBits != IntTyBits;
864 if (!IndexTypeSizeChanged && Offset.isZero())
865 return ORT;
866
867 // We stripped an address space cast that changed the index type size or we
868 // accumulated some constant offset (or both). Readjust the bit width to match
869 // the argument index type size and apply the offset, as required.
870 if (IndexTypeSizeChanged) {
871 if (ORT.knownBefore() &&
872 !::checkedZextOrTrunc(I&: ORT.Before, IntTyBits: InitialIntTyBits))
873 ORT.Before = APInt();
874 if (ORT.knownAfter() && !::checkedZextOrTrunc(I&: ORT.After, IntTyBits: InitialIntTyBits))
875 ORT.After = APInt();
876 }
877 // If the computed bound is "unknown" we cannot add the stripped offset.
878 if (ORT.knownBefore()) {
879 bool Overflow;
880 ORT.Before = ORT.Before.sadd_ov(RHS: Offset, Overflow);
881 if (Overflow)
882 ORT.Before = APInt();
883 }
884 if (ORT.knownAfter()) {
885 bool Overflow;
886 ORT.After = ORT.After.ssub_ov(RHS: Offset, Overflow);
887 if (Overflow)
888 ORT.After = APInt();
889 }
890
891 // We end up pointing on a location that's outside of the original object.
892 if (ORT.knownBefore() && ORT.Before.isNegative()) {
893 // This means that we *may* be accessing memory before the allocation.
894 // Conservatively return an unknown size.
895 //
896 // TODO: working with ranges instead of value would make it possible to take
897 // a better decision.
898 if (Options.EvalMode == ObjectSizeOpts::Mode::Min ||
899 Options.EvalMode == ObjectSizeOpts::Mode::Max) {
900 return ObjectSizeOffsetVisitor::unknown();
901 }
902 // Otherwise it's fine, caller can handle negative offset.
903 }
904 return ORT;
905}
906
907OffsetSpan ObjectSizeOffsetVisitor::computeValue(Value *V) {
908 if (Instruction *I = dyn_cast<Instruction>(Val: V)) {
909 // If we have already seen this instruction, bail out. Cycles can happen in
910 // unreachable code after constant propagation.
911 auto P = SeenInsts.try_emplace(Key: I, Args: ObjectSizeOffsetVisitor::unknown());
912 if (!P.second)
913 return P.first->second;
914 ++InstructionsVisited;
915 if (InstructionsVisited > ObjectSizeOffsetVisitorMaxVisitInstructions)
916 return ObjectSizeOffsetVisitor::unknown();
917 OffsetSpan Res = visit(I&: *I);
918 // Cache the result for later visits. If we happened to visit this during
919 // the above recursion, we would consider it unknown until now.
920 SeenInsts[I] = Res;
921 return Res;
922 }
923 if (Argument *A = dyn_cast<Argument>(Val: V))
924 return visitArgument(A&: *A);
925 if (ConstantPointerNull *P = dyn_cast<ConstantPointerNull>(Val: V))
926 return visitConstantPointerNull(*P);
927 if (GlobalAlias *GA = dyn_cast<GlobalAlias>(Val: V))
928 return visitGlobalAlias(GA&: *GA);
929 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Val: V))
930 return visitGlobalVariable(GV&: *GV);
931 if (UndefValue *UV = dyn_cast<UndefValue>(Val: V))
932 return visitUndefValue(*UV);
933
934 LLVM_DEBUG(dbgs() << "ObjectSizeOffsetVisitor::compute() unhandled value: "
935 << *V << '\n');
936 return ObjectSizeOffsetVisitor::unknown();
937}
938
939bool ObjectSizeOffsetVisitor::checkedZextOrTrunc(APInt &I) {
940 return ::checkedZextOrTrunc(I, IntTyBits);
941}
942
943OffsetSpan ObjectSizeOffsetVisitor::visitAllocaInst(AllocaInst &I) {
944 TypeSize ElemSize = I.getAllocationBaseSize(DL);
945 if (ElemSize.isScalable() && Options.EvalMode != ObjectSizeOpts::Mode::Min)
946 return ObjectSizeOffsetVisitor::unknown();
947 if (!isUIntN(N: IntTyBits, x: ElemSize.getKnownMinValue()))
948 return ObjectSizeOffsetVisitor::unknown();
949 APInt Size(IntTyBits, ElemSize.getKnownMinValue());
950
951 if (!I.isArrayAllocation())
952 return OffsetSpan(Zero, align(Size, Alignment: I.getAlign()));
953
954 Value *ArraySize = I.getArraySize();
955 if (auto PossibleSize = aggregatePossibleConstantValues(
956 V: ArraySize, EvalMode: Options.EvalMode,
957 BitWidth: ArraySize->getType()->getScalarSizeInBits())) {
958 APInt NumElems = *PossibleSize;
959 if (!checkedZextOrTrunc(I&: NumElems))
960 return ObjectSizeOffsetVisitor::unknown();
961
962 bool Overflow;
963 Size = Size.umul_ov(RHS: NumElems, Overflow);
964
965 return Overflow ? ObjectSizeOffsetVisitor::unknown()
966 : OffsetSpan(Zero, align(Size, Alignment: I.getAlign()));
967 }
968 return ObjectSizeOffsetVisitor::unknown();
969}
970
971OffsetSpan ObjectSizeOffsetVisitor::visitArgument(Argument &A) {
972 Type *MemoryTy = A.getPointeeInMemoryValueType();
973 // No interprocedural analysis is done at the moment.
974 if (!MemoryTy || !MemoryTy->isSized()) {
975 ++ObjectVisitorArgument;
976 return ObjectSizeOffsetVisitor::unknown();
977 }
978
979 APInt Size(IntTyBits, DL.getTypeAllocSize(Ty: MemoryTy));
980 return OffsetSpan(Zero, align(Size, Alignment: A.getParamAlign()));
981}
982
983OffsetSpan ObjectSizeOffsetVisitor::visitCallBase(CallBase &CB) {
984 auto Mapper = [this](const Value *V) -> const Value * {
985 if (!V->getType()->isIntegerTy())
986 return V;
987
988 if (auto PossibleBound = aggregatePossibleConstantValues(
989 V, EvalMode: Options.EvalMode, BitWidth: V->getType()->getScalarSizeInBits()))
990 return ConstantInt::get(Ty: V->getType(), V: *PossibleBound);
991
992 return V;
993 };
994
995 if (std::optional<APInt> Size = getAllocSize(CB: &CB, TLI, Mapper)) {
996 // Very large unsigned value cannot be represented as OffsetSpan.
997 if (Size->isNegative())
998 return ObjectSizeOffsetVisitor::unknown();
999 return OffsetSpan(Zero, *Size);
1000 }
1001 return ObjectSizeOffsetVisitor::unknown();
1002}
1003
1004OffsetSpan
1005ObjectSizeOffsetVisitor::visitConstantPointerNull(ConstantPointerNull &CPN) {
1006 // If null is unknown, there's nothing we can do. Additionally, non-zero
1007 // address spaces can make use of null, so we don't presume to know anything
1008 // about that.
1009 //
1010 // TODO: How should this work with address space casts? We currently just drop
1011 // them on the floor, but it's unclear what we should do when a NULL from
1012 // addrspace(1) gets casted to addrspace(0) (or vice-versa).
1013 if (Options.NullIsUnknownSize || CPN.getPointerType()->getAddressSpace())
1014 return ObjectSizeOffsetVisitor::unknown();
1015 return OffsetSpan(Zero, Zero);
1016}
1017
1018OffsetSpan
1019ObjectSizeOffsetVisitor::visitExtractElementInst(ExtractElementInst &) {
1020 return ObjectSizeOffsetVisitor::unknown();
1021}
1022
1023OffsetSpan ObjectSizeOffsetVisitor::visitExtractValueInst(ExtractValueInst &) {
1024 // Easy cases were already folded by previous passes.
1025 return ObjectSizeOffsetVisitor::unknown();
1026}
1027
1028OffsetSpan ObjectSizeOffsetVisitor::visitGlobalAlias(GlobalAlias &GA) {
1029 if (GA.isInterposable())
1030 return ObjectSizeOffsetVisitor::unknown();
1031 return computeImpl(V: GA.getAliasee());
1032}
1033
1034OffsetSpan ObjectSizeOffsetVisitor::visitGlobalVariable(GlobalVariable &GV) {
1035 if (!GV.getValueType()->isSized() || GV.hasExternalWeakLinkage() ||
1036 ((!GV.hasInitializer() || GV.isInterposable()) &&
1037 Options.EvalMode != ObjectSizeOpts::Mode::Min))
1038 return ObjectSizeOffsetVisitor::unknown();
1039
1040 APInt Size(IntTyBits, GV.getGlobalSize(DL));
1041 return OffsetSpan(Zero, align(Size, Alignment: GV.getAlign()));
1042}
1043
1044OffsetSpan ObjectSizeOffsetVisitor::visitIntToPtrInst(IntToPtrInst &) {
1045 // clueless
1046 return ObjectSizeOffsetVisitor::unknown();
1047}
1048
1049OffsetSpan ObjectSizeOffsetVisitor::findLoadOffsetRange(
1050 LoadInst &Load, BasicBlock &BB, BasicBlock::iterator From,
1051 SmallDenseMap<BasicBlock *, OffsetSpan, 8> &VisitedBlocks,
1052 unsigned &ScannedInstCount) {
1053 constexpr unsigned MaxInstsToScan = 128;
1054
1055 auto Where = VisitedBlocks.find(Val: &BB);
1056 if (Where != VisitedBlocks.end())
1057 return Where->second;
1058
1059 auto Unknown = [&BB, &VisitedBlocks]() {
1060 return VisitedBlocks[&BB] = ObjectSizeOffsetVisitor::unknown();
1061 };
1062 auto Known = [&BB, &VisitedBlocks](OffsetSpan SO) {
1063 return VisitedBlocks[&BB] = SO;
1064 };
1065
1066 do {
1067 Instruction &I = *From;
1068
1069 if (I.isDebugOrPseudoInst())
1070 continue;
1071
1072 if (++ScannedInstCount > MaxInstsToScan)
1073 return Unknown();
1074
1075 if (!I.mayWriteToMemory())
1076 continue;
1077
1078 if (auto *SI = dyn_cast<StoreInst>(Val: &I)) {
1079 AliasResult AR =
1080 Options.AA->alias(V1: SI->getPointerOperand(), V2: Load.getPointerOperand());
1081 switch ((AliasResult::Kind)AR) {
1082 case AliasResult::NoAlias:
1083 continue;
1084 case AliasResult::MustAlias:
1085 if (SI->getValueOperand()->getType()->isPointerTy())
1086 return Known(computeImpl(V: SI->getValueOperand()));
1087 else
1088 return Unknown(); // No handling of non-pointer values by `compute`.
1089 default:
1090 return Unknown();
1091 }
1092 }
1093
1094 if (auto *CB = dyn_cast<CallBase>(Val: &I)) {
1095 Function *Callee = CB->getCalledFunction();
1096 // Bail out on indirect call.
1097 if (!Callee)
1098 return Unknown();
1099
1100 if (!TLI)
1101 return Unknown();
1102
1103 LibFunc TLIFn = TLI->getLibFunc(FDecl: *CB->getCalledFunction());
1104 if (!TLI->has(F: TLIFn))
1105 return Unknown();
1106
1107 // TODO: There's probably more interesting case to support here.
1108 if (TLIFn != LibFunc_posix_memalign)
1109 return Unknown();
1110
1111 AliasResult AR =
1112 Options.AA->alias(V1: CB->getOperand(i_nocapture: 0), V2: Load.getPointerOperand());
1113 switch ((AliasResult::Kind)AR) {
1114 case AliasResult::NoAlias:
1115 continue;
1116 case AliasResult::MustAlias:
1117 break;
1118 default:
1119 return Unknown();
1120 }
1121
1122 // Is the error status of posix_memalign correctly checked? If not it
1123 // would be incorrect to assume it succeeds and load doesn't see the
1124 // previous value.
1125 std::optional<bool> Checked = isImpliedByDomCondition(
1126 Pred: ICmpInst::ICMP_EQ, LHS: CB, RHS: ConstantInt::get(Ty: CB->getType(), V: 0), ContextI: &Load, DL);
1127 if (!Checked || !*Checked)
1128 return Unknown();
1129
1130 Value *Size = CB->getOperand(i_nocapture: 2);
1131 auto *C = dyn_cast<ConstantInt>(Val: Size);
1132 if (!C)
1133 return Unknown();
1134
1135 APInt CSize = C->getValue();
1136 if (CSize.isNegative())
1137 return Unknown();
1138
1139 return Known({APInt(CSize.getBitWidth(), 0), CSize});
1140 }
1141
1142 return Unknown();
1143 } while (From-- != BB.begin());
1144
1145 SmallVector<OffsetSpan> PredecessorSizeOffsets;
1146 for (auto *PredBB : predecessors(BB: &BB)) {
1147 PredecessorSizeOffsets.push_back(Elt: findLoadOffsetRange(
1148 Load, BB&: *PredBB, From: BasicBlock::iterator(PredBB->getTerminator()),
1149 VisitedBlocks, ScannedInstCount));
1150 if (!PredecessorSizeOffsets.back().bothKnown())
1151 return Unknown();
1152 }
1153
1154 if (PredecessorSizeOffsets.empty())
1155 return Unknown();
1156
1157 return Known(std::accumulate(
1158 first: PredecessorSizeOffsets.begin() + 1, last: PredecessorSizeOffsets.end(),
1159 init: PredecessorSizeOffsets.front(), binary_op: [this](OffsetSpan LHS, OffsetSpan RHS) {
1160 return combineOffsetRange(LHS, RHS);
1161 }));
1162}
1163
1164OffsetSpan ObjectSizeOffsetVisitor::visitLoadInst(LoadInst &LI) {
1165 if (!Options.AA) {
1166 ++ObjectVisitorLoad;
1167 return ObjectSizeOffsetVisitor::unknown();
1168 }
1169
1170 SmallDenseMap<BasicBlock *, OffsetSpan, 8> VisitedBlocks;
1171 unsigned ScannedInstCount = 0;
1172 OffsetSpan SO =
1173 findLoadOffsetRange(Load&: LI, BB&: *LI.getParent(), From: BasicBlock::iterator(LI),
1174 VisitedBlocks, ScannedInstCount);
1175 if (!SO.bothKnown())
1176 ++ObjectVisitorLoad;
1177 return SO;
1178}
1179
1180OffsetSpan ObjectSizeOffsetVisitor::combineOffsetRange(OffsetSpan LHS,
1181 OffsetSpan RHS) {
1182 if (!LHS.bothKnown() || !RHS.bothKnown())
1183 return ObjectSizeOffsetVisitor::unknown();
1184
1185 switch (Options.EvalMode) {
1186 case ObjectSizeOpts::Mode::Min:
1187 return {LHS.Before.slt(RHS: RHS.Before) ? LHS.Before : RHS.Before,
1188 LHS.After.slt(RHS: RHS.After) ? LHS.After : RHS.After};
1189 case ObjectSizeOpts::Mode::Max: {
1190 return {LHS.Before.sgt(RHS: RHS.Before) ? LHS.Before : RHS.Before,
1191 LHS.After.sgt(RHS: RHS.After) ? LHS.After : RHS.After};
1192 }
1193 case ObjectSizeOpts::Mode::ExactSizeFromOffset:
1194 return {LHS.Before.eq(RHS: RHS.Before) ? LHS.Before : APInt(),
1195 LHS.After.eq(RHS: RHS.After) ? LHS.After : APInt()};
1196 case ObjectSizeOpts::Mode::ExactUnderlyingSizeAndOffset:
1197 return (LHS == RHS) ? LHS : ObjectSizeOffsetVisitor::unknown();
1198 }
1199 llvm_unreachable("missing an eval mode");
1200}
1201
1202OffsetSpan ObjectSizeOffsetVisitor::visitPHINode(PHINode &PN) {
1203 if (PN.getNumIncomingValues() == 0)
1204 return ObjectSizeOffsetVisitor::unknown();
1205 auto IncomingValues = PN.incoming_values();
1206 return std::accumulate(first: IncomingValues.begin() + 1, last: IncomingValues.end(),
1207 init: computeImpl(V: *IncomingValues.begin()),
1208 binary_op: [this](OffsetSpan LHS, Value *VRHS) {
1209 return combineOffsetRange(LHS, RHS: computeImpl(V: VRHS));
1210 });
1211}
1212
1213OffsetSpan ObjectSizeOffsetVisitor::visitSelectInst(SelectInst &I) {
1214 return combineOffsetRange(LHS: computeImpl(V: I.getTrueValue()),
1215 RHS: computeImpl(V: I.getFalseValue()));
1216}
1217
1218OffsetSpan ObjectSizeOffsetVisitor::visitUndefValue(UndefValue &) {
1219 return OffsetSpan(Zero, Zero);
1220}
1221
1222OffsetSpan ObjectSizeOffsetVisitor::visitInstruction(Instruction &I) {
1223 LLVM_DEBUG(dbgs() << "ObjectSizeOffsetVisitor unknown instruction:" << I
1224 << '\n');
1225 return ObjectSizeOffsetVisitor::unknown();
1226}
1227
1228// Just set these right here...
1229SizeOffsetValue::SizeOffsetValue(const SizeOffsetWeakTrackingVH &SOT)
1230 : SizeOffsetType(SOT.Size, SOT.Offset) {}
1231
1232ObjectSizeOffsetEvaluator::ObjectSizeOffsetEvaluator(
1233 Module &M, const TargetLibraryInfo *TLI, ObjectSizeOpts EvalOpts)
1234 : DL(M.getDataLayout()), TLI(TLI), Context(M.getContext()),
1235 Builder(M, 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 // must be a VLA or vscale.
1331 assert(I.isArrayAllocation() || I.isScalable());
1332
1333 // If needed, adjust the alloca's operand size to match the pointer indexing
1334 // size. Subsequent math operations expect the types to match.
1335 Type *IndexTy = DL.getIndexType(C&: I.getContext(), AddressSpace: DL.getAllocaAddrSpace());
1336 assert(IndexTy == Zero->getType() &&
1337 "Expected zero constant to have pointer index type");
1338
1339 Value *Size = Builder.CreateAllocationSize(DestTy: IndexTy, AI: &I);
1340 return SizeOffsetValue(Size, Zero);
1341}
1342
1343SizeOffsetValue ObjectSizeOffsetEvaluator::visitCallBase(CallBase &CB) {
1344 std::optional<AllocFnsTy> FnData = getAllocationSize(CB: &CB, TLI);
1345 if (!FnData)
1346 return ObjectSizeOffsetEvaluator::unknown();
1347
1348 // Handle strdup-like functions separately.
1349 if (FnData->AllocTy == StrDupLike) {
1350 // TODO: implement evaluation of strdup/strndup
1351 return ObjectSizeOffsetEvaluator::unknown();
1352 }
1353
1354 Value *FirstArg = CB.getArgOperand(i: FnData->FstParam);
1355 FirstArg = Builder.CreateZExtOrTrunc(V: FirstArg, DestTy: IntTy);
1356 if (FnData->SndParam < 0)
1357 return SizeOffsetValue(FirstArg, Zero);
1358
1359 Value *SecondArg = CB.getArgOperand(i: FnData->SndParam);
1360 SecondArg = Builder.CreateZExtOrTrunc(V: SecondArg, DestTy: IntTy);
1361 Value *Size = Builder.CreateMul(LHS: FirstArg, RHS: SecondArg);
1362 return SizeOffsetValue(Size, Zero);
1363}
1364
1365SizeOffsetValue
1366ObjectSizeOffsetEvaluator::visitExtractElementInst(ExtractElementInst &) {
1367 return ObjectSizeOffsetEvaluator::unknown();
1368}
1369
1370SizeOffsetValue
1371ObjectSizeOffsetEvaluator::visitExtractValueInst(ExtractValueInst &) {
1372 return ObjectSizeOffsetEvaluator::unknown();
1373}
1374
1375SizeOffsetValue ObjectSizeOffsetEvaluator::visitGEPOperator(GEPOperator &GEP) {
1376 SizeOffsetValue PtrData = compute_(V: GEP.getPointerOperand());
1377 if (!PtrData.bothKnown())
1378 return ObjectSizeOffsetEvaluator::unknown();
1379
1380 Value *Offset = emitGEPOffset(Builder: &Builder, DL, GEP: &GEP, /*NoAssumptions=*/true);
1381 Offset = Builder.CreateAdd(LHS: PtrData.Offset, RHS: Offset);
1382 return SizeOffsetValue(PtrData.Size, Offset);
1383}
1384
1385SizeOffsetValue ObjectSizeOffsetEvaluator::visitIntToPtrInst(IntToPtrInst &) {
1386 // clueless
1387 return ObjectSizeOffsetEvaluator::unknown();
1388}
1389
1390SizeOffsetValue ObjectSizeOffsetEvaluator::visitLoadInst(LoadInst &LI) {
1391 return ObjectSizeOffsetEvaluator::unknown();
1392}
1393
1394SizeOffsetValue ObjectSizeOffsetEvaluator::visitPHINode(PHINode &PHI) {
1395 // Create 2 PHIs: one for size and another for offset.
1396 PHINode *SizePHI = Builder.CreatePHI(Ty: IntTy, NumReservedValues: PHI.getNumIncomingValues());
1397 PHINode *OffsetPHI = Builder.CreatePHI(Ty: IntTy, NumReservedValues: PHI.getNumIncomingValues());
1398
1399 // Insert right away in the cache to handle recursive PHIs.
1400 CacheMap[&PHI] = SizeOffsetWeakTrackingVH(SizePHI, OffsetPHI);
1401
1402 // Compute offset/size for each PHI incoming pointer.
1403 for (unsigned i = 0, e = PHI.getNumIncomingValues(); i != e; ++i) {
1404 BasicBlock *IncomingBlock = PHI.getIncomingBlock(i);
1405 Builder.SetInsertPoint(IncomingBlock->getFirstInsertionPt());
1406 SizeOffsetValue EdgeData = compute_(V: PHI.getIncomingValue(i));
1407
1408 if (!EdgeData.bothKnown()) {
1409 OffsetPHI->replaceAllUsesWith(V: PoisonValue::get(T: IntTy));
1410 OffsetPHI->eraseFromParent();
1411 InsertedInstructions.erase(Ptr: OffsetPHI);
1412 SizePHI->replaceAllUsesWith(V: PoisonValue::get(T: IntTy));
1413 SizePHI->eraseFromParent();
1414 InsertedInstructions.erase(Ptr: SizePHI);
1415 return ObjectSizeOffsetEvaluator::unknown();
1416 }
1417 SizePHI->addIncoming(V: EdgeData.Size, BB: IncomingBlock);
1418 OffsetPHI->addIncoming(V: EdgeData.Offset, BB: IncomingBlock);
1419 }
1420
1421 Value *Size = SizePHI, *Offset = OffsetPHI;
1422 if (Value *Tmp = SizePHI->hasConstantValue()) {
1423 Size = Tmp;
1424 SizePHI->replaceAllUsesWith(V: Size);
1425 SizePHI->eraseFromParent();
1426 InsertedInstructions.erase(Ptr: SizePHI);
1427 }
1428 if (Value *Tmp = OffsetPHI->hasConstantValue()) {
1429 Offset = Tmp;
1430 OffsetPHI->replaceAllUsesWith(V: Offset);
1431 OffsetPHI->eraseFromParent();
1432 InsertedInstructions.erase(Ptr: OffsetPHI);
1433 }
1434 return SizeOffsetValue(Size, Offset);
1435}
1436
1437SizeOffsetValue ObjectSizeOffsetEvaluator::visitSelectInst(SelectInst &I) {
1438 SizeOffsetValue TrueSide = compute_(V: I.getTrueValue());
1439 SizeOffsetValue FalseSide = compute_(V: I.getFalseValue());
1440
1441 if (!TrueSide.bothKnown() || !FalseSide.bothKnown())
1442 return ObjectSizeOffsetEvaluator::unknown();
1443 if (TrueSide == FalseSide)
1444 return TrueSide;
1445
1446 Value *Size =
1447 Builder.CreateSelect(C: I.getCondition(), True: TrueSide.Size, False: FalseSide.Size, Name: "",
1448 MDFrom: ProfcheckDisableMetadataFixes ? nullptr : &I);
1449 Value *Offset =
1450 Builder.CreateSelect(C: I.getCondition(), True: TrueSide.Offset, False: FalseSide.Offset,
1451 Name: "", MDFrom: ProfcheckDisableMetadataFixes ? nullptr : &I);
1452 return SizeOffsetValue(Size, Offset);
1453}
1454
1455SizeOffsetValue ObjectSizeOffsetEvaluator::visitInstruction(Instruction &I) {
1456 LLVM_DEBUG(dbgs() << "ObjectSizeOffsetEvaluator unknown instruction:" << I
1457 << '\n');
1458 return ObjectSizeOffsetEvaluator::unknown();
1459}
1460