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