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