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