//==- llvm/Analysis/MemoryBuiltins.h - Calls to memory builtins --*- C++ -*-==//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This family of functions identifies calls to builtin functions that allocate
// or free memory.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_ANALYSIS_MEMORYBUILTINS_H
#define LLVM_ANALYSIS_MEMORYBUILTINS_H
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/Analysis/TargetFolder.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InstVisitor.h"
#include "llvm/IR/ValueHandle.h"
#include <cstdint>
#include <optional>
#include <utility>
namespace llvm {
class AllocaInst;
class AAResults;
class Argument;
class ConstantPointerNull;
class DataLayout;
class ExtractElementInst;
class ExtractValueInst;
class GEPOperator;
class GlobalAlias;
class GlobalVariable;
class Instruction;
class IntegerType;
class IntrinsicInst;
class IntToPtrInst;
class LLVMContext;
class LoadInst;
class PHINode;
class SelectInst;
class Type;
class UndefValue;
class Value;
/// Tests if a value is a call or invoke to a library function that
/// allocates or reallocates memory (either malloc, calloc, realloc, or strdup
/// like).
bool isAllocationFn(const Value *V, const TargetLibraryInfo *TLI);
bool isAllocationFn(const Value *V,
function_ref<const TargetLibraryInfo &(Function &)> GetTLI);
/// Tests if a value is a call or invoke to a library function that
/// allocates memory via new.
bool isNewLikeFn(const Value *V, const TargetLibraryInfo *TLI);
/// Tests if a value is a call or invoke to a library function that
/// allocates memory similar to malloc or calloc.
bool isMallocOrCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI);
/// Tests if a value is a call or invoke to a library function that
/// allocates memory (either malloc, calloc, or strdup like).
bool isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI);
/// Tests if a function is a call or invoke to a library function that
/// reallocates memory (e.g., realloc).
bool isReallocLikeFn(const Function *F);
/// If this is a call to a realloc function, return the reallocated operand.
Value *getReallocatedOperand(const CallBase *CB);
//===----------------------------------------------------------------------===//
// free Call Utility Functions.
//
/// isLibFreeFunction - Returns true if the function is a builtin free()
bool isLibFreeFunction(const Function *F, const LibFunc TLIFn);
/// If this if a call to a free function, return the freed operand.
Value *getFreedOperand(const CallBase *CB, const TargetLibraryInfo *TLI);
//===----------------------------------------------------------------------===//
// Properties of allocation functions
//
/// Return true if this is a call to an allocation function that does not have
/// side effects that we are required to preserve beyond the effect of
/// allocating a new object.
/// Ex: If our allocation routine has a counter for the number of objects
/// allocated, and the program prints it on exit, can the value change due
/// to optimization? Answer is highly language dependent.
/// Note: *Removable* really does mean removable; it does not mean observable.
/// A language (e.g. C++) can allow removing allocations without allowing
/// insertion or speculative execution of allocation routines.
bool isRemovableAlloc(const CallBase *V, const TargetLibraryInfo *TLI);
/// Gets the alignment argument for an aligned_alloc-like function, using either
/// built-in knowledge based on fuction names/signatures or allocalign
/// attributes. Note: the Value returned may not indicate a valid alignment, per
/// the definition of the allocalign attribute.
Value *getAllocAlignment(const CallBase *V, const TargetLibraryInfo *TLI);
/// Return the size of the requested allocation. With a trivial mapper, this is
/// similar to calling getObjectSize(..., Exact), but without looking through
/// calls that return their argument. A mapper function can be used to replace
/// one Value* (operand to the allocation) with another. This is useful when
/// doing abstract interpretation.
std::optional<APInt> getAllocSize(
const CallBase *CB, const TargetLibraryInfo *TLI,
function_ref<const Value *(const Value *)> Mapper = [](const Value *V) {
return V;
});
/// If this is a call to an allocation function that initializes memory to a
/// fixed value, return said value in the requested type. Otherwise, return
/// nullptr.
Constant *getInitialValueOfAllocation(const Value *V,
const TargetLibraryInfo *TLI,
Type *Ty);
/// If a function is part of an allocation family (e.g.
/// malloc/realloc/calloc/free), return the identifier for its family
/// of functions.
std::optional<StringRef> getAllocationFamily(const Value *I,
const TargetLibraryInfo *TLI);
//===----------------------------------------------------------------------===//
// Utility functions to compute size of objects.
//
/// Various options to control the behavior of getObjectSize.
struct ObjectSizeOpts {
/// Controls how we handle conditional statements with unknown conditions.
enum class Mode : uint8_t {
/// All branches must be known and have the same size, starting from the
/// offset, to be merged.
ExactSizeFromOffset,
/// All branches must be known and have the same underlying size and offset
/// to be merged.
ExactUnderlyingSizeAndOffset,
/// Evaluate all branches of an unknown condition. If all evaluations
/// succeed, pick the minimum size.
Min,
/// Same as Min, except we pick the maximum size of all of the branches.
Max,
};
/// How we want to evaluate this object's size.
Mode EvalMode = Mode::ExactSizeFromOffset;
/// Whether to round the result up to the alignment of allocas, byval
/// arguments, and global variables.
bool RoundToAlign = false;
/// If this is true, null pointers in address space 0 will be treated as
/// though they can't be evaluated. Otherwise, null is always considered to
/// point to a 0 byte region of memory.
bool NullIsUnknownSize = false;
/// If set, used for more accurate evaluation
AAResults *AA = nullptr;
};
/// Compute the size of the object pointed by Ptr. Returns true and the
/// object size in Size if successful, and false otherwise. In this context, by
/// object we mean the region of memory starting at Ptr to the end of the
/// underlying object pointed to by Ptr.
///
/// WARNING: The object size returned is the allocation size. This does not
/// imply dereferenceability at site of use since the object may be freeed in
/// between.
bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL,
const TargetLibraryInfo *TLI, ObjectSizeOpts Opts = {});
/// Try to turn a call to \@llvm.objectsize into an integer value of the given
/// Type. Returns null on failure. If MustSucceed is true, this function will
/// not return null, and may return conservative values governed by the second
/// argument of the call to objectsize.
Value *lowerObjectSizeCall(IntrinsicInst *ObjectSize, const DataLayout &DL,
const TargetLibraryInfo *TLI, bool MustSucceed);
Value *lowerObjectSizeCall(IntrinsicInst *ObjectSize, const DataLayout &DL,
const TargetLibraryInfo *TLI, AAResults *AA,
bool MustSucceed);
using SizeOffsetType = std::pair<APInt, APInt>;
/// Evaluate the size and offset of an object pointed to by a Value*
/// statically. Fails if size or offset are not known at compile time.
class ObjectSizeOffsetVisitor
: public InstVisitor<ObjectSizeOffsetVisitor, SizeOffsetType> {
const DataLayout &DL;
const TargetLibraryInfo *TLI;
ObjectSizeOpts Options;
unsigned IntTyBits;
APInt Zero;
SmallPtrSet<Instruction *, 8> SeenInsts;
APInt align(APInt Size, MaybeAlign Align);
SizeOffsetType unknown() {
return std::make_pair(APInt(), APInt());
}
public:
ObjectSizeOffsetVisitor(const DataLayout &DL, const TargetLibraryInfo *TLI,
LLVMContext &Context, ObjectSizeOpts Options = {});
SizeOffsetType compute(Value *V);
static bool knownSize(const SizeOffsetType &SizeOffset) {
return SizeOffset.first.getBitWidth() > 1;
}
static bool knownOffset(const SizeOffsetType &SizeOffset) {
return SizeOffset.second.getBitWidth() > 1;
}
static bool bothKnown(const SizeOffsetType &SizeOffset) {
return knownSize(SizeOffset) && knownOffset(SizeOffset);
}
// These are "private", except they can't actually be made private. Only
// compute() should be used by external users.
SizeOffsetType visitAllocaInst(AllocaInst &I);
SizeOffsetType visitArgument(Argument &A);
SizeOffsetType visitCallBase(CallBase &CB);
SizeOffsetType visitConstantPointerNull(ConstantPointerNull&);
SizeOffsetType visitExtractElementInst(ExtractElementInst &I);
SizeOffsetType visitExtractValueInst(ExtractValueInst &I);
SizeOffsetType visitGlobalAlias(GlobalAlias &GA);
SizeOffsetType visitGlobalVariable(GlobalVariable &GV);
SizeOffsetType visitIntToPtrInst(IntToPtrInst&);
SizeOffsetType visitLoadInst(LoadInst &I);
SizeOffsetType visitPHINode(PHINode&);
SizeOffsetType visitSelectInst(SelectInst &I);
SizeOffsetType visitUndefValue(UndefValue&);
SizeOffsetType visitInstruction(Instruction &I);
private:
SizeOffsetType findLoadSizeOffset(
LoadInst &LoadFrom, BasicBlock &BB, BasicBlock::iterator From,
SmallDenseMap<BasicBlock *, SizeOffsetType, 8> &VisitedBlocks,
unsigned &ScannedInstCount);
SizeOffsetType combineSizeOffset(SizeOffsetType LHS, SizeOffsetType RHS);
SizeOffsetType computeImpl(Value *V);
bool CheckedZextOrTrunc(APInt &I);
};
using SizeOffsetEvalType = std::pair<Value *, Value *>;
/// Evaluate the size and offset of an object pointed to by a Value*.
/// May create code to compute the result at run-time.
class ObjectSizeOffsetEvaluator
: public InstVisitor<ObjectSizeOffsetEvaluator, SizeOffsetEvalType> {
using BuilderTy = IRBuilder<TargetFolder, IRBuilderCallbackInserter>;
using WeakEvalType = std::pair<WeakTrackingVH, WeakTrackingVH>;
using CacheMapTy = DenseMap<const Value *, WeakEvalType>;
using PtrSetTy = SmallPtrSet<const Value *, 8>;
const DataLayout &DL;
const TargetLibraryInfo *TLI;
LLVMContext &Context;
BuilderTy Builder;
IntegerType *IntTy;
Value *Zero;
CacheMapTy CacheMap;
PtrSetTy SeenVals;
ObjectSizeOpts EvalOpts;
SmallPtrSet<Instruction *, 8> InsertedInstructions;
SizeOffsetEvalType compute_(Value *V);
public:
static SizeOffsetEvalType unknown() {
return std::make_pair(nullptr, nullptr);
}
ObjectSizeOffsetEvaluator(const DataLayout &DL, const TargetLibraryInfo *TLI,
LLVMContext &Context, ObjectSizeOpts EvalOpts = {});
SizeOffsetEvalType compute(Value *V);
bool knownSize(SizeOffsetEvalType SizeOffset) {
return SizeOffset.first;
}
bool knownOffset(SizeOffsetEvalType SizeOffset) {
return SizeOffset.second;
}
bool anyKnown(SizeOffsetEvalType SizeOffset) {
return knownSize(SizeOffset) || knownOffset(SizeOffset);
}
bool bothKnown(SizeOffsetEvalType SizeOffset) {
return knownSize(SizeOffset) && knownOffset(SizeOffset);
}
// The individual instruction visitors should be treated as private.
SizeOffsetEvalType visitAllocaInst(AllocaInst &I);
SizeOffsetEvalType visitCallBase(CallBase &CB);
SizeOffsetEvalType visitExtractElementInst(ExtractElementInst &I);
SizeOffsetEvalType visitExtractValueInst(ExtractValueInst &I);
SizeOffsetEvalType visitGEPOperator(GEPOperator &GEP);
SizeOffsetEvalType visitIntToPtrInst(IntToPtrInst&);
SizeOffsetEvalType visitLoadInst(LoadInst &I);
SizeOffsetEvalType visitPHINode(PHINode &PHI);
SizeOffsetEvalType visitSelectInst(SelectInst &I);
SizeOffsetEvalType visitInstruction(Instruction &I);
};
} // end namespace llvm
#endif // LLVM_ANALYSIS_MEMORYBUILTINS_H