LLVM 24.0.0git
MemoryBuiltins.cpp
Go to the documentation of this file.
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
15#include "llvm/ADT/APInt.h"
16#include "llvm/ADT/STLExtras.h"
17#include "llvm/ADT/Statistic.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"
28#include "llvm/IR/Function.h"
29#include "llvm/IR/GlobalAlias.h"
31#include "llvm/IR/Instruction.h"
34#include "llvm/IR/Operator.h"
36#include "llvm/IR/Type.h"
37#include "llvm/IR/Value.h"
40#include "llvm/Support/Debug.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 {
56}
57
59 "object-size-offset-visitor-max-visit-instructions",
60 cl::desc("Maximum number of instructions for ObjectSizeOffsetVisitor to "
61 "look at"),
62 cl::init(100));
63
64// clang-format off
66 OpNewLike = 1<<0, // allocates; never returns null
67 MallocLike = 1<<1, // allocates; may return null
68 StrDupLike = 1<<2,
72};
73
78// clang-format on
79
81 switch (Family) {
83 return "malloc";
85 return "vec_malloc";
86 }
87 llvm_unreachable("missing an alloc family");
88}
89
90struct AllocFnsTy {
92 unsigned NumParams;
93 // First and Second size parameters (or -1 if unused)
95 // Alignment parameter for aligned_alloc and aligned new
97 // Name of default allocator function to group malloc/free calls by 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, {StrDupLike, 1, -1, -1, -1, MallocFamily::Malloc}},
106 {LibFunc_dunder_strdup, {StrDupLike, 1, -1, -1, -1, MallocFamily::Malloc}},
107 {LibFunc_strndup, {StrDupLike, 2, 1, -1, -1, MallocFamily::Malloc}},
108 {LibFunc_dunder_strndup, {StrDupLike, 2, 1, -1, -1, MallocFamily::Malloc}},
109};
110// clang-format on
111
112static const Function *getCalledFunction(const Value *V) {
113 // Don't care about intrinsics in this case.
115 return nullptr;
116
117 const auto *CB = dyn_cast<CallBase>(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>
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(*Callee);
142 if (!TLI->has(TLIFn))
143 return std::nullopt;
144
145 const auto *Iter = find_if(AllocationFnData,
146 [TLIFn](const std::pair<LibFunc, AllocFnsTy> &P) {
147 return P.first == TLIFn;
148 });
149
150 if (Iter == std::end(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(FstParam)->isIntegerTy(32) ||
165 FTy->getParamType(FstParam)->isIntegerTy(64))) &&
166 (SndParam < 0 || FTy->getParamType(SndParam)->isIntegerTy(32) ||
167 FTy->getParamType(SndParam)->isIntegerTy(64)))
168 return *FnData;
169 return std::nullopt;
170}
171
172static std::optional<AllocFnsTy>
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>
182 function_ref<const TargetLibraryInfo &(Function &)> GetTLI) {
183 if (const Function *Callee = getCalledFunction(V))
185 Callee, AllocTy, &GetTLI(const_cast<Function &>(*Callee)));
186 return std::nullopt;
187}
188
189static std::optional<AllocFnsTy>
191 if (const Function *Callee = getCalledFunction(CB)) {
192 // Prefer to use existing information over allocsize. This will give us an
193 // accurate AllocTy.
194 if (std::optional<AllocFnsTy> Data =
196 return Data;
197 }
198
199 Attribute Attr = CB->getFnAttr(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(-1);
212 // Allocsize has no way to specify an alignment argument
213 Result.AlignParam = -1;
214 return Result;
215}
216
218 if (const auto *CB = dyn_cast<CallBase>(V)) {
219 Attribute Attr = CB->getFnAttr(Attribute::AllocKind);
220 if (Attr.isValid())
221 return AllocFnKind(Attr.getValueAsInt());
222 }
224}
225
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).
242 // Allocation calls must return ptr. Exit early if this doesn't.
243 if (!V->getType()->isPointerTy())
244 return false;
245 return getAllocationData(V, AnyAlloc, TLI).has_value() ||
247}
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, AnyAlloc, GetTLI).has_value() ||
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).
261 // Allocation calls must return ptr. Exit early if this doesn't.
262 if (!V->getType()->isPointerTy())
263 return false;
264 return getAllocationData(V, AllocLike, TLI).has_value() ||
266}
267
268/// Tests if a functions is a call or invoke to a library function that
269/// reallocates memory (e.g., realloc).
273
276 return CB->getArgOperandWithAttribute(Attribute::AllocatedPointer);
277 return nullptr;
278}
279
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(CB, TLI);
289}
290
292 const TargetLibraryInfo *TLI) {
293 const std::optional<AllocFnsTy> FnData = getAllocationData(V, AnyAlloc, TLI);
294 if (FnData && FnData->AlignParam >= 0) {
295 return V->getOperand(FnData->AlignParam);
296 }
297 return V->getArgOperandWithAttribute(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(IntTyBits);
313 return true;
314}
315
316std::optional<APInt>
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(CB->getType());
329
330 // Handle strdup-like functions separately.
331 if (FnData->AllocTy == StrDupLike) {
332 APInt Size(IntTyBits, GetStringLength(Mapper(CB->getArgOperand(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>(Mapper(CB->getArgOperand(FnData->FstParam)));
340 if (!Arg)
341 return std::nullopt;
342
343 APInt MaxSize = Arg->getValue().zext(IntTyBits);
344 if (Size.ugt(MaxSize))
345 Size = MaxSize + 1;
346 }
347 return Size;
348 }
349
350 const ConstantInt *Arg =
351 dyn_cast<ConstantInt>(Mapper(CB->getArgOperand(FnData->FstParam)));
352 if (!Arg)
353 return std::nullopt;
354
355 APInt Size = Arg->getValue();
356 if (!checkedZextOrTrunc(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>(Mapper(CB->getArgOperand(FnData->SndParam)));
364 if (!Arg)
365 return std::nullopt;
366
367 APInt NumElems = Arg->getValue();
368 if (!checkedZextOrTrunc(NumElems, IntTyBits))
369 return std::nullopt;
370
371 bool Overflow;
372 Size = Size.umul_ov(NumElems, Overflow);
373 if (Overflow)
374 return std::nullopt;
375 return Size;
376}
377
379 const TargetLibraryInfo *TLI,
380 Type *Ty) {
381 if (isa<AllocaInst>(V))
382 return UndefValue::get(Ty);
383
384 auto *Alloc = dyn_cast<CallBase>(V);
385 if (!Alloc)
386 return nullptr;
387
388 // malloc are uninitialized (undef)
389 if (getAllocationData(Alloc, MallocOrOpNewLike, TLI).has_value())
390 return UndefValue::get(Ty);
391
394 return UndefValue::get(Ty);
396 return Constant::getNullValue(Ty);
397
398 return nullptr;
399}
400
401std::optional<StringRef>
403 if (const Function *Callee = getCalledFunction(I)) {
404 LibFunc TLIFn = TLI ? TLI->getLibFunc(*Callee) : NotLibFunc;
405 if (TLIFn != NotLibFunc && TLI->has(TLIFn)) {
406 // Callee is some known library function.
407 const auto AllocData =
409 if (AllocData)
410 return mangledNameForMallocFamily(AllocData->Family);
411 }
412 }
413
414 // Callee isn't a known library function, still check attributes.
417 Attribute Attr = cast<CallBase>(I)->getFnAttr("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*/) {
427}
428
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(CB)) {
436 LibFunc TLIFn = TLI ? TLI->getLibFunc(*Callee) : NotLibFunc;
437 if (TLIFn != NotLibFunc && TLI->has(TLIFn) &&
438 isLibFreeFunction(Callee, TLIFn)) {
439 // All currently supported free functions free the first argument.
440 return CB->getArgOperand(0);
441 }
442 }
443
445 return CB->getArgOperandWithAttribute(Attribute::AllocatedPointer);
446
447 return nullptr;
448}
449
450//===----------------------------------------------------------------------===//
451// Utility functions to compute size of objects.
452//
454 APInt Size = Data.Size;
455 APInt Offset = Data.Offset;
456
457 if (Offset.isNegative() || Size.ult(Offset))
458 return APInt::getZero(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(const_cast<Value *>(Ptr));
471 if (!Data.bothKnown())
472 return false;
473
475 return true;
476}
477
478std::optional<TypeSize> llvm::getBaseObjectSize(const Value *Ptr,
479 const DataLayout &DL,
480 const TargetLibraryInfo *TLI,
481 ObjectSizeOpts Opts) {
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(alignTo(Size.getFixedValue(), *Alignment));
488 return Size;
489 };
490
491 if (isa<UndefValue>(Ptr))
492 return TypeSize::getZero();
493
494 if (isa<ConstantPointerNull>(Ptr)) {
496 return std::nullopt;
497 return TypeSize::getZero();
498 }
499
500 if (auto *GV = dyn_cast<GlobalVariable>(Ptr)) {
501 if (!GV->getValueType()->isSized() || GV->hasExternalWeakLinkage() ||
502 !GV->hasInitializer() || GV->isInterposable())
503 return std::nullopt;
504 return Align(TypeSize::getFixed(GV->getGlobalSize(DL)), GV->getAlign());
505 }
506
507 if (auto *A = dyn_cast<Argument>(Ptr)) {
508 Type *MemoryTy = A->getPointeeInMemoryValueType();
509 if (!MemoryTy || !MemoryTy->isSized())
510 return std::nullopt;
511 return Align(DL.getTypeAllocSize(MemoryTy), A->getParamAlign());
512 }
513
514 if (auto *AI = dyn_cast<AllocaInst>(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>(Ptr)) {
521 if (std::optional<APInt> Size = getAllocSize(CB, TLI)) {
522 if (std::optional<uint64_t> ZExtSize = Size->tryZExtValue())
523 return TypeSize::getFixed(*ZExtSize);
524 }
525 return std::nullopt;
526 }
527
528 return std::nullopt;
529}
530
532 const DataLayout &DL,
533 const TargetLibraryInfo *TLI,
534 bool MustSucceed) {
535 return lowerObjectSizeCall(ObjectSize, DL, TLI, /*AAResults=*/nullptr,
536 MustSucceed);
537}
538
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>(ObjectSize->getArgOperand(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 =
555 else
557
558 EvalOptions.NullIsUnknownSize =
559 cast<ConstantInt>(ObjectSize->getArgOperand(2))->isOne();
560
561 auto *ResultType = cast<IntegerType>(ObjectSize->getType());
562 bool StaticOnly = cast<ConstantInt>(ObjectSize->getArgOperand(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(ObjectSize->getArgOperand(0), Size, DL, TLI,
568 EvalOptions) &&
569 isUIntN(ResultType->getBitWidth(), Size))
570 return ConstantInt::get(ResultType, Size);
571 } else {
572 ObjectSizeOffsetEvaluator Eval(*ObjectSize->getModule(), TLI, EvalOptions);
573 SizeOffsetValue SizeOffsetPair = Eval.compute(ObjectSize->getArgOperand(0));
574
575 if (SizeOffsetPair != ObjectSizeOffsetEvaluator::unknown()) {
577 ObjectSize->getIterator(), TargetFolder(DL),
579 if (InsertedInstructions)
580 InsertedInstructions->push_back(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(Size, Offset);
589 Value *UseZero = Builder.CreateICmpULT(Size, Offset);
590 ResultSize = Builder.CreateZExtOrTrunc(ResultSize, ResultType);
591 Value *Ret = Builder.CreateSelect(
592 UseZero, ConstantInt::get(ResultType, 0), ResultSize);
593
594 // The non-constant size expression cannot evaluate to -1.
596 Builder.CreateAssumption(Builder.CreateICmpNE(
597 Ret, ConstantInt::getAllOnesValue(ResultType)));
598
599 return Ret;
600 }
601 }
602
603 if (!MustSucceed)
604 return nullptr;
605
606 return MaxVal ? Constant::getAllOnesValue(ResultType)
607 : Constant::getNullValue(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>
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) ? *LHS : *RHS;
623 return LHS->sle(*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>(V)) {
634 return CI->getValue().sextOrTrunc(BitWidth);
635 } else if (const auto *SI = dyn_cast<SelectInst>(V)) {
637 aggregatePossibleConstantValuesImpl(SI->getTrueValue(), EvalMode,
638 BitWidth, RecursionDepth + 1),
639 aggregatePossibleConstantValuesImpl(SI->getFalseValue(), EvalMode,
640 BitWidth, RecursionDepth + 1),
641 EvalMode);
642 } else if (const auto *PN = dyn_cast<PHINode>(V)) {
643 unsigned Count = PN->getNumIncomingValues();
644 if (Count == 0)
645 return std::nullopt;
647 PN->getIncomingValue(0), EvalMode, BitWidth, RecursionDepth + 1);
648 for (unsigned I = 1; Acc && I < Count; ++I) {
650 PN->getIncomingValue(I), EvalMode, BitWidth, RecursionDepth + 1);
651 Acc = combinePossibleConstantValues(Acc, Tmp, EvalMode);
652 }
653 return Acc;
654 }
655
656 return std::nullopt;
657}
658
659static std::optional<APInt>
661 unsigned BitWidth) {
662 if (auto *CI = dyn_cast<ConstantInt>(V))
663 return CI->getValue().sextOrTrunc(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, 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.getZExtValue(), *Alignment));
681
682 return Size.isNegative() ? APInt() : Size;
683}
684
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
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() &&
702 Span.Before = APInt::getZero(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(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>(V)) {
728 // External Analysis used to compute the Min/Max value of individual Offsets
729 // within a GEP.
730 ObjectSizeOpts::Mode EvalMode =
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(V->getType());
738 auto OffsetRangeAnalysis = [EvalMode, IdxTyBits](Value &VOffset,
739 APInt &Offset) {
740 if (auto PossibleOffset =
741 aggregatePossibleConstantValues(&VOffset, EvalMode, 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(V->getType());
756 Zero = APInt::getZero(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(ORT.Before, InitialIntTyBits))
769 ORT.Before = APInt();
770 if (ORT.knownAfter() && !::checkedZextOrTrunc(ORT.After, 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(Offset, Overflow);
777 if (Overflow)
778 ORT.Before = APInt();
779 }
780 if (ORT.knownAfter()) {
781 bool Overflow;
782 ORT.After = ORT.After.ssub_ov(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>(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(I, 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);
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>(V))
820 return visitArgument(*A);
821 if (ConstantPointerNull *P = dyn_cast<ConstantPointerNull>(V))
823 if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V))
824 return visitGlobalAlias(*GA);
825 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
826 return visitGlobalVariable(*GV);
827 if (UndefValue *UV = dyn_cast<UndefValue>(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
840 TypeSize ElemSize = I.getAllocationBaseSize(DL);
841 if (ElemSize.isScalable() && Options.EvalMode != ObjectSizeOpts::Mode::Min)
842 return ObjectSizeOffsetVisitor::unknown();
843 if (!isUIntN(IntTyBits, ElemSize.getKnownMinValue()))
844 return ObjectSizeOffsetVisitor::unknown();
845 APInt Size(IntTyBits, ElemSize.getKnownMinValue());
846
847 if (!I.isArrayAllocation())
848 return OffsetSpan(Zero, align(Size, I.getAlign()));
849
850 Value *ArraySize = I.getArraySize();
851 if (auto PossibleSize = aggregatePossibleConstantValues(
852 ArraySize, Options.EvalMode,
853 ArraySize->getType()->getScalarSizeInBits())) {
854 APInt NumElems = *PossibleSize;
855 if (!checkedZextOrTrunc(NumElems))
856 return ObjectSizeOffsetVisitor::unknown();
857
858 bool Overflow;
859 Size = Size.umul_ov(NumElems, Overflow);
860
861 return Overflow ? ObjectSizeOffsetVisitor::unknown()
862 : OffsetSpan(Zero, align(Size, I.getAlign()));
863 }
864 return ObjectSizeOffsetVisitor::unknown();
865}
866
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(MemoryTy));
876 return OffsetSpan(Zero, align(Size, A.getParamAlign()));
877}
878
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, Options.EvalMode, V->getType()->getScalarSizeInBits()))
886 return ConstantInt::get(V->getType(), *PossibleBound);
887
888 return V;
889 };
890
891 if (std::optional<APInt> Size = getAllocSize(&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
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
916 return ObjectSizeOffsetVisitor::unknown();
917}
918
920 // Easy cases were already folded by previous passes.
921 return ObjectSizeOffsetVisitor::unknown();
922}
923
925 if (GA.isInterposable())
926 return ObjectSizeOffsetVisitor::unknown();
927 return computeImpl(GA.getAliasee());
928}
929
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, GV.getAlign()));
938}
939
941 // clueless
942 return ObjectSizeOffsetVisitor::unknown();
943}
944
945OffsetSpan ObjectSizeOffsetVisitor::findLoadOffsetRange(
948 unsigned &ScannedInstCount) {
949 constexpr unsigned MaxInstsToScan = 128;
950
951 auto Where = VisitedBlocks.find(&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
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>(&I)) {
975 AliasResult AR =
976 Options.AA->alias(SI->getPointerOperand(), Load.getPointerOperand());
977 switch ((AliasResult::Kind)AR) {
979 continue;
981 if (SI->getValueOperand()->getType()->isPointerTy())
982 return Known(computeImpl(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>(&I)) {
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(*CB->getCalledFunction());
1000 if (!TLI->has(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(CB->getOperand(0), Load.getPointerOperand());
1009 switch ((AliasResult::Kind)AR) {
1011 continue;
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 ICmpInst::ICMP_EQ, CB, ConstantInt::get(CB->getType(), 0), &Load, DL);
1023 if (!Checked || !*Checked)
1024 return Unknown();
1025
1026 Value *Size = CB->getOperand(2);
1027 auto *C = dyn_cast<ConstantInt>(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)) {
1043 PredecessorSizeOffsets.push_back(findLoadOffsetRange(
1044 Load, *PredBB, 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 PredecessorSizeOffsets.begin() + 1, PredecessorSizeOffsets.end(),
1055 PredecessorSizeOffsets.front(), [this](OffsetSpan LHS, OffsetSpan RHS) {
1056 return combineOffsetRange(LHS, RHS);
1057 }));
1058}
1059
1061 if (!Options.AA) {
1062 ++ObjectVisitorLoad;
1063 return ObjectSizeOffsetVisitor::unknown();
1064 }
1065
1067 unsigned ScannedInstCount = 0;
1068 OffsetSpan SO =
1069 findLoadOffsetRange(LI, *LI.getParent(), 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) {
1083 return {LHS.Before.slt(RHS.Before) ? LHS.Before : RHS.Before,
1084 LHS.After.slt(RHS.After) ? LHS.After : RHS.After};
1086 return {LHS.Before.sgt(RHS.Before) ? LHS.Before : RHS.Before,
1087 LHS.After.sgt(RHS.After) ? LHS.After : RHS.After};
1088 }
1090 return {LHS.Before.eq(RHS.Before) ? LHS.Before : APInt(),
1091 LHS.After.eq(RHS.After) ? LHS.After : APInt()};
1093 return (LHS == RHS) ? LHS : ObjectSizeOffsetVisitor::unknown();
1094 }
1095 llvm_unreachable("missing an eval mode");
1096}
1097
1099 if (PN.getNumIncomingValues() == 0)
1100 return ObjectSizeOffsetVisitor::unknown();
1101 auto IncomingValues = PN.incoming_values();
1102 return std::accumulate(IncomingValues.begin() + 1, IncomingValues.end(),
1103 computeImpl(*IncomingValues.begin()),
1104 [this](OffsetSpan LHS, Value *VRHS) {
1105 return combineOffsetRange(LHS, computeImpl(VRHS));
1106 });
1107}
1108
1110 return combineOffsetRange(computeImpl(I.getTrueValue()),
1111 computeImpl(I.getFalseValue()));
1112}
1113
1117
1119 LLVM_DEBUG(dbgs() << "ObjectSizeOffsetVisitor unknown instruction:" << I
1120 << '\n');
1121 return ObjectSizeOffsetVisitor::unknown();
1122}
1123
1124// Just set these right here...
1127
1129 Module &M, const TargetLibraryInfo *TLI, ObjectSizeOpts EvalOpts)
1130 : DL(M.getDataLayout()), TLI(TLI), Context(M.getContext()),
1131 Builder(M, TargetFolder(DL),
1133 [&](Instruction *I) { InsertedInstructions.insert(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
1140 // XXX - Are vectors of pointers possible here?
1141 IntTy = cast<IntegerType>(DL.getIndexType(V->getType()));
1142 Zero = ConstantInt::get(IntTy, 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(SeenVal);
1152 // non-computable results can be safely cached
1153 if (CacheIt != CacheMap.end() && CacheIt->second.anyKnown())
1154 CacheMap.erase(CacheIt);
1155 }
1156
1157 // Erase any instructions we inserted as part of the traversal.
1158 for (Instruction *I : InsertedInstructions) {
1159 I->replaceAllUsesWith(PoisonValue::get(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, Const.Size),
1180 ConstantInt::get(Context, Const.Offset));
1181
1182 V = V->stripPointerCasts();
1183
1184 // Check cache.
1185 CacheMapTy::iterator CacheIt = CacheMap.find(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);
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(V).second) {
1203 } else if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
1204 Result = visitGEPOperator(*GEP);
1205 } else if (Instruction *I = dyn_cast<Instruction>(V)) {
1206 Result = visit(*I);
1207 } else if (isa<Argument>(V) ||
1208 (isa<ConstantExpr>(V) &&
1209 cast<ConstantExpr>(V)->getOpcode() == Instruction::IntToPtr) ||
1211 // Ignore values where we cannot do more than ObjectSizeVisitor.
1213 } else {
1214 LLVM_DEBUG(
1215 dbgs() << "ObjectSizeOffsetEvaluator::compute() unhandled value: " << *V
1216 << '\n');
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
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(I.getContext(), DL.getAllocaAddrSpace());
1232 assert(IndexTy == Zero->getType() &&
1233 "Expected zero constant to have pointer index type");
1234
1235 Value *Size = Builder.CreateAllocationSize(IndexTy, &I);
1236 return SizeOffsetValue(Size, Zero);
1237}
1238
1240 std::optional<AllocFnsTy> FnData = getAllocationSize(&CB, TLI);
1241 if (!FnData)
1243
1244 // Handle strdup-like functions separately.
1245 if (FnData->AllocTy == StrDupLike) {
1246 // TODO: implement evaluation of strdup/strndup
1248 }
1249
1250 Value *FirstArg = CB.getArgOperand(FnData->FstParam);
1251 FirstArg = Builder.CreateZExtOrTrunc(FirstArg, IntTy);
1252 if (FnData->SndParam < 0)
1253 return SizeOffsetValue(FirstArg, Zero);
1254
1255 Value *SecondArg = CB.getArgOperand(FnData->SndParam);
1256 SecondArg = Builder.CreateZExtOrTrunc(SecondArg, IntTy);
1257 Value *Size = Builder.CreateMul(FirstArg, SecondArg);
1258 return SizeOffsetValue(Size, Zero);
1259}
1260
1265
1270
1272 SizeOffsetValue PtrData = compute_(GEP.getPointerOperand());
1273 if (!PtrData.bothKnown())
1275
1276 Value *Offset = emitGEPOffset(&Builder, DL, &GEP, /*NoAssumptions=*/true);
1277 Offset = Builder.CreateAdd(PtrData.Offset, Offset);
1278 return SizeOffsetValue(PtrData.Size, Offset);
1279}
1280
1285
1289
1291 // Create 2 PHIs: one for size and another for offset.
1292 PHINode *SizePHI = Builder.CreatePHI(IntTy, PHI.getNumIncomingValues());
1293 PHINode *OffsetPHI = Builder.CreatePHI(IntTy, 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_(PHI.getIncomingValue(i));
1303
1304 if (!EdgeData.bothKnown()) {
1305 OffsetPHI->replaceAllUsesWith(PoisonValue::get(IntTy));
1306 OffsetPHI->eraseFromParent();
1307 InsertedInstructions.erase(OffsetPHI);
1308 SizePHI->replaceAllUsesWith(PoisonValue::get(IntTy));
1309 SizePHI->eraseFromParent();
1310 InsertedInstructions.erase(SizePHI);
1312 }
1313 SizePHI->addIncoming(EdgeData.Size, IncomingBlock);
1314 OffsetPHI->addIncoming(EdgeData.Offset, IncomingBlock);
1315 }
1316
1317 Value *Size = SizePHI, *Offset = OffsetPHI;
1318 if (Value *Tmp = SizePHI->hasConstantValue()) {
1319 Size = Tmp;
1320 SizePHI->replaceAllUsesWith(Size);
1321 SizePHI->eraseFromParent();
1322 InsertedInstructions.erase(SizePHI);
1323 }
1324 if (Value *Tmp = OffsetPHI->hasConstantValue()) {
1325 Offset = Tmp;
1326 OffsetPHI->replaceAllUsesWith(Offset);
1327 OffsetPHI->eraseFromParent();
1328 InsertedInstructions.erase(OffsetPHI);
1329 }
1330 return SizeOffsetValue(Size, Offset);
1331}
1332
1334 SizeOffsetValue TrueSide = compute_(I.getTrueValue());
1335 SizeOffsetValue FalseSide = compute_(I.getFalseValue());
1336
1337 if (!TrueSide.bothKnown() || !FalseSide.bothKnown())
1339 if (TrueSide == FalseSide)
1340 return TrueSide;
1341
1342 Value *Size =
1343 Builder.CreateSelect(I.getCondition(), TrueSide.Size, FalseSide.Size, "",
1344 ProfcheckDisableMetadataFixes ? nullptr : &I);
1345 Value *Offset =
1346 Builder.CreateSelect(I.getCondition(), TrueSide.Offset, FalseSide.Offset,
1347 "", ProfcheckDisableMetadataFixes ? nullptr : &I);
1348 return SizeOffsetValue(Size, Offset);
1349}
1350
1352 LLVM_DEBUG(dbgs() << "ObjectSizeOffsetEvaluator unknown instruction:" << I
1353 << '\n');
1355}
const TargetLowering & TLI
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
Rewrite undef for PHI
This file implements a class to represent arbitrary precision integral constant values and operations...
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file contains the simple types necessary to represent the attributes associated with functions a...
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
SmallPtrSet< const BasicBlock *, 8 > VisitedBlocks
Hexagon Common GEP
static LVOptions Options
Definition LVOptions.cpp:25
#define F(x, y, z)
Definition MD5.cpp:54
#define I(x, y, z)
Definition MD5.cpp:57
MallocFamily
static std::optional< APInt > combinePossibleConstantValues(std::optional< APInt > LHS, std::optional< APInt > RHS, ObjectSizeOpts::Mode EvalMode)
static AllocFnKind getAllocFnKind(const Value *V)
static std::optional< APInt > aggregatePossibleConstantValuesImpl(const Value *V, ObjectSizeOpts::Mode EvalMode, unsigned BitWidth, unsigned RecursionDepth)
static bool checkedZextOrTrunc(APInt &I, unsigned IntTyBits)
When we're compiling N-bit code, and the user uses parameters that are greater than N bits (e....
static std::optional< AllocFnsTy > getAllocationDataForFunction(const Function *Callee, AllocType AllocTy, const TargetLibraryInfo *TLI)
Returns the allocation data for the given value if it's a call to a known allocation function.
static std::optional< AllocFnsTy > getAllocationData(const Value *V, AllocType AllocTy, const TargetLibraryInfo *TLI)
static bool checkFnAllocKind(const Value *V, AllocFnKind Wanted)
static std::optional< AllocFnsTy > getAllocationSize(const CallBase *CB, const TargetLibraryInfo *TLI)
static const Function * getCalledFunction(const Value *V)
static cl::opt< unsigned > ObjectSizeOffsetVisitorMaxVisitInstructions("object-size-offset-visitor-max-visit-instructions", cl::desc("Maximum number of instructions for ObjectSizeOffsetVisitor to " "look at"), cl::init(100))
static StringRef mangledNameForMallocFamily(const MallocFamily &Family)
static const std::pair< LibFunc, AllocFnsTy > AllocationFnData[]
AllocType
@ MallocLike
@ AnyAlloc
@ AllocLike
@ StrDupLike
@ OpNewLike
@ MallocOrOpNewLike
static APInt getSizeWithOverflow(const SizeOffsetAPInt &Data)
static std::optional< APInt > aggregatePossibleConstantValues(const Value *V, ObjectSizeOpts::Mode EvalMode, unsigned BitWidth)
#define P(N)
This file contains the declarations for profiling metadata utility functions.
Func getContext().diagnose(DiagnosticInfoUnsupported(Func
This file contains some templates that are useful if you are working with the STL at all.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition Statistic.h:171
#define LLVM_DEBUG(...)
Definition Debug.h:119
Value * RHS
Value * LHS
Class for arbitrary precision integers.
Definition APInt.h:78
LLVM_ABI APInt zext(unsigned width) const
Zero extend to a new width.
Definition APInt.cpp:1057
uint64_t getZExtValue() const
Get zero extended value.
Definition APInt.h:1560
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition APInt.h:1508
bool isNegative() const
Determine sign of this APInt.
Definition APInt.h:325
LLVM_ABI APInt sadd_ov(const APInt &RHS, bool &Overflow) const
Definition APInt.cpp:1966
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
Definition APInt.h:196
LLVM_ABI APInt ssub_ov(const APInt &RHS, bool &Overflow) const
Definition APInt.cpp:1979
@ NoAlias
The two locations do not alias at all.
@ MustAlias
The two locations precisely alias each other.
an instruction to allocate memory on the stack
This class represents an incoming formal argument to a Function.
Definition Argument.h:32
Functions, function parameters, and return types can have attributes to indicate how they should be t...
Definition Attributes.h:107
LLVM_ABI uint64_t getValueAsInt() const
Return the attribute's value as an integer.
LLVM_ABI std::pair< unsigned, std::optional< unsigned > > getAllocSizeArgs() const
Returns the argument numbers for the allocsize attribute.
LLVM_ABI StringRef getValueAsString() const
Return the attribute's value as a string.
bool isValid() const
Return true if the attribute is any kind of attribute.
Definition Attributes.h:263
LLVM Basic Block Representation.
Definition BasicBlock.h:62
iterator begin()
Instruction iterator methods.
Definition BasicBlock.h:440
LLVM_ABI const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
InstListType::iterator iterator
Instruction iterators...
Definition BasicBlock.h:170
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
Attribute getFnAttr(StringRef Kind) const
Get the attribute of a given kind for the function.
Value * getArgOperand(unsigned i) const
LLVM_ABI Value * getArgOperandWithAttribute(Attribute::AttrKind Kind) const
If one of the arguments has the specified attribute, returns its operand value.
unsigned arg_size() const
This is the shared class of boolean and integer constants.
Definition Constants.h:87
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition Constants.h:159
A constant pointer value that points to null.
Definition Constants.h:716
PointerType * getPointerType() const
Return the scalar pointer type for this null value.
Definition Constants.h:736
This is an important base class in LLVM.
Definition Constant.h:44
static LLVM_ABI Constant * getAllOnesValue(Type *Ty)
static LLVM_ABI Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
A parsed version of the target data layout string in and methods for querying it.
Definition DataLayout.h:64
iterator find(const_arg_type_t< KeyT > Val)
Definition DenseMap.h:766
iterator end()
Definition DenseMap.h:686
DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT > iterator
Definition DenseMap.h:678
This instruction extracts a single (scalar) element from a VectorType value.
This instruction extracts a struct member or array element value from an aggregate value.
const Constant * getAliasee() const
Definition GlobalAlias.h:87
bool hasExternalWeakLinkage() const
Type * getValueType() const
LLVM_ABI bool isInterposable(bool CheckNoIPA=true) const
Return true if this global's definition can be substituted with an arbitrary definition at link time ...
Definition Globals.cpp:178
bool hasInitializer() const
Definitions have initializers, declarations don't.
MaybeAlign getAlign() const
Returns the alignment of the given variable.
LLVM_ABI uint64_t getGlobalSize(const DataLayout &DL) const
Get the size of this global variable in bytes.
Definition Globals.cpp:640
Provides an 'InsertHelper' that calls a user-provided callback after performing the default insertion...
Definition IRBuilder.h:74
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition IRBuilder.h:2990
LLVM_ABI const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
LLVM_ABI InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
LLVM_ABI const DataLayout & getDataLayout() const
Get the data layout of the module this instruction belongs to.
This class represents a cast from an integer to a pointer.
A wrapper class for inspecting calls to intrinsic functions.
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
This is an important class for using LLVM in a threaded context.
Definition LLVMContext.h:76
An instruction for reading from memory.
A Module instance is used to store all the information related to an LLVM module.
Definition Module.h:68
Evaluate the size and offset of an object pointed to by a Value*.
LLVM_ABI SizeOffsetValue visitExtractValueInst(ExtractValueInst &I)
LLVM_ABI SizeOffsetValue visitExtractElementInst(ExtractElementInst &I)
LLVM_ABI SizeOffsetValue compute(Value *V)
LLVM_ABI SizeOffsetValue visitInstruction(Instruction &I)
LLVM_ABI SizeOffsetValue visitLoadInst(LoadInst &I)
LLVM_ABI SizeOffsetValue visitGEPOperator(GEPOperator &GEP)
LLVM_ABI SizeOffsetValue visitIntToPtrInst(IntToPtrInst &)
LLVM_ABI SizeOffsetValue visitPHINode(PHINode &PHI)
LLVM_ABI SizeOffsetValue visitCallBase(CallBase &CB)
LLVM_ABI ObjectSizeOffsetEvaluator(Module &M, const TargetLibraryInfo *TLI, ObjectSizeOpts EvalOpts={})
LLVM_ABI SizeOffsetValue visitSelectInst(SelectInst &I)
LLVM_ABI SizeOffsetValue visitAllocaInst(AllocaInst &I)
static SizeOffsetValue unknown()
Evaluate the size and offset of an object pointed to by a Value* statically.
LLVM_ABI OffsetSpan visitSelectInst(SelectInst &I)
LLVM_ABI OffsetSpan visitExtractValueInst(ExtractValueInst &I)
LLVM_ABI OffsetSpan visitConstantPointerNull(ConstantPointerNull &)
LLVM_ABI OffsetSpan visitExtractElementInst(ExtractElementInst &I)
LLVM_ABI OffsetSpan visitGlobalVariable(GlobalVariable &GV)
LLVM_ABI OffsetSpan visitCallBase(CallBase &CB)
LLVM_ABI OffsetSpan visitIntToPtrInst(IntToPtrInst &)
LLVM_ABI OffsetSpan visitAllocaInst(AllocaInst &I)
LLVM_ABI ObjectSizeOffsetVisitor(const DataLayout &DL, const TargetLibraryInfo *TLI, LLVMContext &Context, ObjectSizeOpts Options={})
LLVM_ABI OffsetSpan visitLoadInst(LoadInst &I)
LLVM_ABI OffsetSpan visitPHINode(PHINode &)
LLVM_ABI OffsetSpan visitGlobalAlias(GlobalAlias &GA)
LLVM_ABI OffsetSpan visitInstruction(Instruction &I)
LLVM_ABI SizeOffsetAPInt compute(Value *V)
LLVM_ABI OffsetSpan visitUndefValue(UndefValue &)
LLVM_ABI OffsetSpan visitArgument(Argument &A)
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
op_range incoming_values()
LLVM_ABI Value * hasConstantValue() const
If the specified PHI node always merges together the same value, return the value,...
unsigned getNumIncomingValues() const
Return the number of incoming edges.
unsigned getAddressSpace() const
Return the address space of the Pointer type.
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
This class represents the LLVM 'select' instruction.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void push_back(const T &Elt)
LLVM_NO_SANITIZE_CFI_UNRELATED_CAST iterator begin()
Represent a constant reference to a string, i.e.
Definition StringRef.h:56
TargetFolder - Create constants with target dependent folding.
Provides information about what library functions are available for the current target.
static constexpr TypeSize getFixed(ScalarTy ExactSize)
Definition TypeSize.h:352
static constexpr TypeSize getZero()
Definition TypeSize.h:358
The instances of the Type class are immutable: once they are created, they are never changed.
Definition Type.h:46
LLVM_ABI unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
bool isSized() const
Return true if it makes sense to take the size of this type.
Definition Type.h:321
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
Definition Type.h:354
bool isVoidTy() const
Return true if this is 'void'.
Definition Type.h:141
'undef' values are things that do not have specified contents.
Definition Constants.h:1657
static LLVM_ABI UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Value * getOperand(unsigned i) const
Definition User.h:207
LLVM Value Representation.
Definition Value.h:75
Type * getType() const
All values are typed, get the type of this value.
Definition Value.h:257
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition Value.cpp:548
LLVMContext & getContext() const
All values hold a context through their type.
Definition Value.h:260
constexpr bool isScalable() const
Returns whether the quantity is scaled by a runtime quantity (vscale).
Definition TypeSize.h:169
constexpr ScalarTy getKnownMinValue() const
Returns the minimum value this quantity can represent.
Definition TypeSize.h:166
An efficient, type-erasing, non-owning reference to a callable.
const ParentTy * getParent() const
Definition ilist_node.h:34
self_iterator getIterator()
Definition ilist_node.h:123
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Abstract Attribute helper functions.
Definition Attributor.h:166
initializer< Ty > init(const Ty &Val)
friend class Instruction
Iterator for Instructions in a `BasicBlock.
Definition BasicBlock.h:73
unsigned getOpcode(const VPValue *V)
Return the instruction opcode for the recipe defining V or 0 for unsupported recipes and VPValues not...
This is an optimization pass for GlobalISel generic memory operations.
@ Offset
Definition DWP.cpp:577
LLVM_ABI cl::opt< bool > ProfcheckDisableMetadataFixes
LLVM_ABI Constant * getInitialValueOfAllocation(const Value *V, const TargetLibraryInfo *TLI, Type *Ty)
If this is a call to an allocation function that initializes memory to a fixed value,...
@ Known
Known to have no common set bits.
@ Unknown
Not known to have no common set bits.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:643
AllocFnKind
Definition Attributes.h:55
LLVM_ABI bool isRemovableAlloc(const CallBase *V, const TargetLibraryInfo *TLI)
Return true if this is a call to an allocation function that does not have side effects that we are r...
LLVM_ABI std::optional< StringRef > getAllocationFamily(const Value *I, const TargetLibraryInfo *TLI)
If a function is part of an allocation family (e.g.
@ Load
The value being inserted comes from a load (InsertElement only).
LLVM_ABI Value * lowerObjectSizeCall(IntrinsicInst *ObjectSize, const DataLayout &DL, const TargetLibraryInfo *TLI, bool MustSucceed)
Try to turn a call to @llvm.objectsize into an integer value of the given Type.
LLVM_ABI Value * getAllocAlignment(const CallBase *V, const TargetLibraryInfo *TLI)
Gets the alignment argument for an aligned_alloc-like function, using either built-in knowledge based...
constexpr bool isUIntN(unsigned N, uint64_t x)
Checks if an unsigned integer fits into the given (dynamic) bit width.
Definition MathExtras.h:244
LLVM_ABI bool isLibFreeFunction(const Function *F, const LibFunc TLIFn)
isLibFreeFunction - Returns true if the function is a builtin free()
LLVM_ABI Value * getReallocatedOperand(const CallBase *CB)
If this is a call to a realloc function, return the reallocated operand.
LLVM_ABI std::optional< TypeSize > getBaseObjectSize(const Value *Ptr, const DataLayout &DL, const TargetLibraryInfo *TLI, ObjectSizeOpts Opts={})
Like getObjectSize(), but only returns the size of base objects (like allocas, global variables and a...
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
Definition InstrProf.h:143
LLVM_ABI bool isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI)
Tests if a value is a call or invoke to a library function that allocates memory (either malloc,...
LLVM_ABI bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL, const TargetLibraryInfo *TLI, ObjectSizeOpts Opts={})
Compute the size of the object pointed by Ptr.
LLVM_ABI Value * emitGEPOffset(IRBuilderBase *Builder, const DataLayout &DL, User *GEP, bool NoAssumptions=false)
Given a getelementptr instruction/constantexpr, emit the code necessary to compute the offset from th...
Definition Local.cpp:22
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:209
constexpr uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
Definition Alignment.h:149
LLVM_ABI uint64_t GetStringLength(const Value *V, unsigned CharSize=8)
If we can compute the length of the string pointed to by the specified pointer, return 'len+1'.
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
Definition Casting.h:547
LLVM_ABI bool isReallocLikeFn(const Function *F)
Tests if a function is a call or invoke to a library function that reallocates memory (e....
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Count
Definition InstrProf.h:145
LLVM_ABI Value * getFreedOperand(const CallBase *CB, const TargetLibraryInfo *TLI)
If this if a call to a free function, return the freed operand.
constexpr unsigned BitWidth
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:559
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1788
auto predecessors(const MachineBasicBlock *BB)
LLVM_ABI bool isAllocationFn(const Value *V, const TargetLibraryInfo *TLI)
Tests if a value is a call or invoke to a library function that allocates or reallocates memory (eith...
LLVM_ABI std::optional< APInt > getAllocSize(const CallBase *CB, const TargetLibraryInfo *TLI, function_ref< const Value *(const Value *)> Mapper=[](const Value *V) { return V;})
Return the size of the requested allocation.
LLVM_ABI std::optional< bool > isImpliedByDomCondition(const Value *Cond, const Instruction *ContextI, const DataLayout &DL)
Return the boolean condition value in the context of the given instruction if it is known based on do...
MallocFamily Family
unsigned NumParams
AllocType AllocTy
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition Alignment.h:39
This struct is a compact representation of a valid (power of two) or undefined (0) alignment.
Definition Alignment.h:111
Various options to control the behavior of getObjectSize.
bool NullIsUnknownSize
If this is true, null pointers in address space 0 will be treated as though they can't be evaluated.
Mode EvalMode
How we want to evaluate this object's size.
AAResults * AA
If set, used for more accurate evaluation.
bool RoundToAlign
Whether to round the result up to the alignment of allocas, byval arguments, and global variables.
Mode
Controls how we handle conditional statements with unknown conditions.
@ ExactUnderlyingSizeAndOffset
All branches must be known and have the same underlying size and offset to be merged.
@ Max
Same as Min, except we pick the maximum size of all of the branches.
@ Min
Evaluate all branches of an unknown condition.
@ ExactSizeFromOffset
All branches must be known and have the same size, starting from the offset, to be merged.
OffsetSpan - Used internally by ObjectSizeOffsetVisitor.
bool knownBefore() const
APInt After
Number of allocated bytes before this point.
bool knownAfter() const
bool bothKnown() const
SizeOffsetAPInt - Used by ObjectSizeOffsetVisitor, which works with APInts.
SizeOffsetWeakTrackingVH - Used by ObjectSizeOffsetEvaluator in a DenseMap.