llvm/Analysis/MemoryBuiltins.h

0001 //==- llvm/Analysis/MemoryBuiltins.h - Calls to memory builtins --*- C++ -*-==//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // This family of functions identifies calls to builtin functions that allocate
0010 // or free memory.
0011 //
0012 //===----------------------------------------------------------------------===//
0013
0014 #ifndef LLVM_ANALYSIS_MEMORYBUILTINS_H
0015 #define LLVM_ANALYSIS_MEMORYBUILTINS_H
0016
0017 #include "llvm/ADT/APInt.h"
0018 #include "llvm/ADT/DenseMap.h"
0019 #include "llvm/ADT/SmallPtrSet.h"
0020 #include "llvm/Analysis/TargetFolder.h"
0021 #include "llvm/IR/IRBuilder.h"
0022 #include "llvm/IR/InstVisitor.h"
0023 #include "llvm/IR/ValueHandle.h"
0024 #include <cstdint>
0025 #include <optional>
0026 #include <utility>
0027
0028 namespace llvm {
0029
0030 class AllocaInst;
0031 class AAResults;
0032 class Argument;
0033 class ConstantPointerNull;
0034 class DataLayout;
0035 class ExtractElementInst;
0036 class ExtractValueInst;
0037 class GEPOperator;
0038 class GlobalAlias;
0039 class GlobalVariable;
0040 class Instruction;
0041 class IntegerType;
0042 class IntrinsicInst;
0043 class IntToPtrInst;
0044 class LLVMContext;
0045 class LoadInst;
0046 class PHINode;
0047 class SelectInst;
0048 class Type;
0049 class UndefValue;
0050 class Value;
0051
0052 /// Tests if a value is a call or invoke to a library function that
0053 /// allocates or reallocates memory (either malloc, calloc, realloc, or strdup
0054 /// like).
0055 bool isAllocationFn(const Value *V, const TargetLibraryInfo *TLI);
0056 bool isAllocationFn(const Value *V,
0057                     function_ref<const TargetLibraryInfo &(Function &)> GetTLI);
0058
0059 /// Tests if a value is a call or invoke to a library function that
0060 /// allocates memory via new.
0061 bool isNewLikeFn(const Value *V, const TargetLibraryInfo *TLI);
0062
0063 /// Tests if a value is a call or invoke to a library function that
0064 /// allocates memory similar to malloc or calloc.
0065 bool isMallocOrCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI);
0066
0067 /// Tests if a value is a call or invoke to a library function that
0068 /// allocates memory (either malloc, calloc, or strdup like).
0069 bool isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI);
0070
0071 /// Tests if a function is a call or invoke to a library function that
0072 /// reallocates memory (e.g., realloc).
0073 bool isReallocLikeFn(const Function *F);
0074
0075 /// If this is a call to a realloc function, return the reallocated operand.
0076 Value *getReallocatedOperand(const CallBase *CB);
0077
0078 //===----------------------------------------------------------------------===//
0079 //  free Call Utility Functions.
0080 //
0081
0082 /// isLibFreeFunction - Returns true if the function is a builtin free()
0083 bool isLibFreeFunction(const Function *F, const LibFunc TLIFn);
0084
0085 /// If this if a call to a free function, return the freed operand.
0086 Value *getFreedOperand(const CallBase *CB, const TargetLibraryInfo *TLI);
0087
0088 //===----------------------------------------------------------------------===//
0089 //  Properties of allocation functions
0090 //
0091
0092 /// Return true if this is a call to an allocation function that does not have
0093 /// side effects that we are required to preserve beyond the effect of
0094 /// allocating a new object.
0095 /// Ex: If our allocation routine has a counter for the number of objects
0096 /// allocated, and the program prints it on exit, can the value change due
0097 /// to optimization? Answer is highly language dependent.
0098 /// Note: *Removable* really does mean removable; it does not mean observable.
0099 /// A language (e.g. C++) can allow removing allocations without allowing
0100 /// insertion or speculative execution of allocation routines.
0101 bool isRemovableAlloc(const CallBase *V, const TargetLibraryInfo *TLI);
0102
0103 /// Gets the alignment argument for an aligned_alloc-like function, using either
0104 /// built-in knowledge based on fuction names/signatures or allocalign
0105 /// attributes. Note: the Value returned may not indicate a valid alignment, per
0106 /// the definition of the allocalign attribute.
0107 Value *getAllocAlignment(const CallBase *V, const TargetLibraryInfo *TLI);
0108
0109 /// Return the size of the requested allocation. With a trivial mapper, this is
0110 /// similar to calling getObjectSize(..., Exact), but without looking through
0111 /// calls that return their argument. A mapper function can be used to replace
0112 /// one Value* (operand to the allocation) with another. This is useful when
0113 /// doing abstract interpretation.
0114 std::optional<APInt> getAllocSize(
0115     const CallBase *CB, const TargetLibraryInfo *TLI,
0116     function_ref<const Value *(const Value *)> Mapper = [](const Value *V) {
0117       return V;
0118     });
0119
0120 /// If this is a call to an allocation function that initializes memory to a
0121 /// fixed value, return said value in the requested type.  Otherwise, return
0122 /// nullptr.
0123 Constant *getInitialValueOfAllocation(const Value *V,
0124                                       const TargetLibraryInfo *TLI,
0125                                       Type *Ty);
0126
0127 /// If a function is part of an allocation family (e.g.
0128 /// malloc/realloc/calloc/free), return the identifier for its family
0129 /// of functions.
0130 std::optional<StringRef> getAllocationFamily(const Value *I,
0131                                              const TargetLibraryInfo *TLI);
0132
0133 //===----------------------------------------------------------------------===//
0134 //  Utility functions to compute size of objects.
0135 //
0136
0137 /// Various options to control the behavior of getObjectSize.
0138 struct ObjectSizeOpts {
0139   /// Controls how we handle conditional statements with unknown conditions.
0140   enum class Mode : uint8_t {
0141     /// All branches must be known and have the same size, starting from the
0142     /// offset, to be merged.
0143     ExactSizeFromOffset,
0144     /// All branches must be known and have the same underlying size and offset
0145     /// to be merged.
0146     ExactUnderlyingSizeAndOffset,
0147     /// Evaluate all branches of an unknown condition. If all evaluations
0148     /// succeed, pick the minimum size.
0149     Min,
0150     /// Same as Min, except we pick the maximum size of all of the branches.
0151     Max,
0152   };
0153
0154   /// How we want to evaluate this object's size.
0155   Mode EvalMode = Mode::ExactSizeFromOffset;
0156   /// Whether to round the result up to the alignment of allocas, byval
0157   /// arguments, and global variables.
0158   bool RoundToAlign = false;
0159   /// If this is true, null pointers in address space 0 will be treated as
0160   /// though they can't be evaluated. Otherwise, null is always considered to
0161   /// point to a 0 byte region of memory.
0162   bool NullIsUnknownSize = false;
0163   /// If set, used for more accurate evaluation
0164   AAResults *AA = nullptr;
0165 };
0166
0167 /// Compute the size of the object pointed by Ptr. Returns true and the
0168 /// object size in Size if successful, and false otherwise. In this context, by
0169 /// object we mean the region of memory starting at Ptr to the end of the
0170 /// underlying object pointed to by Ptr.
0171 ///
0172 /// WARNING: The object size returned is the allocation size.  This does not
0173 /// imply dereferenceability at site of use since the object may be freeed in
0174 /// between.
0175 bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL,
0176                    const TargetLibraryInfo *TLI, ObjectSizeOpts Opts = {});
0177
0178 /// Try to turn a call to \@llvm.objectsize into an integer value of the given
0179 /// Type. Returns null on failure. If MustSucceed is true, this function will
0180 /// not return null, and may return conservative values governed by the second
0181 /// argument of the call to objectsize.
0182 Value *lowerObjectSizeCall(IntrinsicInst *ObjectSize, const DataLayout &DL,
0183                            const TargetLibraryInfo *TLI, bool MustSucceed);
0184 Value *lowerObjectSizeCall(
0185     IntrinsicInst *ObjectSize, const DataLayout &DL,
0186     const TargetLibraryInfo *TLI, AAResults *AA, bool MustSucceed,
0187     SmallVectorImpl<Instruction *> *InsertedInstructions = nullptr);
0188
0189 /// SizeOffsetType - A base template class for the object size visitors. Used
0190 /// here as a self-documenting way to handle the values rather than using a
0191 /// \p std::pair.
0192 template <typename T, class C> struct SizeOffsetType {
0193 public:
0194   T Size;
0195   T Offset;
0196
0197   SizeOffsetType() = default;
0198   SizeOffsetType(T Size, T Offset)
0199       : Size(std::move(Size)), Offset(std::move(Offset)) {}
0200
0201   bool knownSize() const { return C::known(Size); }
0202   bool knownOffset() const { return C::known(Offset); }
0203   bool anyKnown() const { return knownSize() || knownOffset(); }
0204   bool bothKnown() const { return knownSize() && knownOffset(); }
0205
0206   bool operator==(const SizeOffsetType<T, C> &RHS) const {
0207     return Size == RHS.Size && Offset == RHS.Offset;
0208   }
0209   bool operator!=(const SizeOffsetType<T, C> &RHS) const {
0210     return !(*this == RHS);
0211   }
0212 };
0213
0214 /// SizeOffsetAPInt - Used by \p ObjectSizeOffsetVisitor, which works with
0215 /// \p APInts.
0216 struct SizeOffsetAPInt : public SizeOffsetType<APInt, SizeOffsetAPInt> {
0217   SizeOffsetAPInt() = default;
0218   SizeOffsetAPInt(APInt Size, APInt Offset)
0219       : SizeOffsetType(std::move(Size), std::move(Offset)) {}
0220
0221   static bool known(const APInt &V) { return V.getBitWidth() > 1; }
0222 };
0223
0224 /// OffsetSpan - Used internally by \p ObjectSizeOffsetVisitor. Represents a
0225 /// point in memory as a pair of allocated bytes before and after it.
0226 ///
0227 /// \c Before and \c After fields are signed values. It makes it possible to
0228 /// represent out-of-bound access, e.g. as a result of a GEP, at the expense of
0229 /// not being able to represent very large allocation.
0230 struct OffsetSpan {
0231   APInt Before; /// Number of allocated bytes before this point.
0232   APInt After;  /// Number of allocated bytes after this point.
0233
0234   OffsetSpan() = default;
0235   OffsetSpan(APInt Before, APInt After) : Before(Before), After(After) {}
0236
0237   bool knownBefore() const { return known(Before); }
0238   bool knownAfter() const { return known(After); }
0239   bool anyKnown() const { return knownBefore() || knownAfter(); }
0240   bool bothKnown() const { return knownBefore() && knownAfter(); }
0241
0242   bool operator==(const OffsetSpan &RHS) const {
0243     return Before == RHS.Before && After == RHS.After;
0244   }
0245   bool operator!=(const OffsetSpan &RHS) const { return !(*this == RHS); }
0246
0247   static bool known(const APInt &V) { return V.getBitWidth() > 1; }
0248 };
0249
0250 /// Evaluate the size and offset of an object pointed to by a Value*
0251 /// statically. Fails if size or offset are not known at compile time.
0252 class ObjectSizeOffsetVisitor
0253     : public InstVisitor<ObjectSizeOffsetVisitor, OffsetSpan> {
0254   const DataLayout &DL;
0255   const TargetLibraryInfo *TLI;
0256   ObjectSizeOpts Options;
0257   unsigned IntTyBits;
0258   APInt Zero;
0259   SmallDenseMap<Instruction *, OffsetSpan, 8> SeenInsts;
0260   unsigned InstructionsVisited;
0261
0262   APInt align(APInt Size, MaybeAlign Align);
0263
0264   static OffsetSpan unknown() { return OffsetSpan(); }
0265
0266 public:
0267   ObjectSizeOffsetVisitor(const DataLayout &DL, const TargetLibraryInfo *TLI,
0268                           LLVMContext &Context, ObjectSizeOpts Options = {});
0269
0270   SizeOffsetAPInt compute(Value *V);
0271
0272   // These are "private", except they can't actually be made private. Only
0273   // compute() should be used by external users.
0274   OffsetSpan visitAllocaInst(AllocaInst &I);
0275   OffsetSpan visitArgument(Argument &A);
0276   OffsetSpan visitCallBase(CallBase &CB);
0277   OffsetSpan visitConstantPointerNull(ConstantPointerNull &);
0278   OffsetSpan visitExtractElementInst(ExtractElementInst &I);
0279   OffsetSpan visitExtractValueInst(ExtractValueInst &I);
0280   OffsetSpan visitGlobalAlias(GlobalAlias &GA);
0281   OffsetSpan visitGlobalVariable(GlobalVariable &GV);
0282   OffsetSpan visitIntToPtrInst(IntToPtrInst &);
0283   OffsetSpan visitLoadInst(LoadInst &I);
0284   OffsetSpan visitPHINode(PHINode &);
0285   OffsetSpan visitSelectInst(SelectInst &I);
0286   OffsetSpan visitUndefValue(UndefValue &);
0287   OffsetSpan visitInstruction(Instruction &I);
0288
0289 private:
0290   OffsetSpan
0291   findLoadOffsetRange(LoadInst &LoadFrom, BasicBlock &BB,
0292                       BasicBlock::iterator From,
0293                       SmallDenseMap<BasicBlock *, OffsetSpan, 8> &VisitedBlocks,
0294                       unsigned &ScannedInstCount);
0295   OffsetSpan combineOffsetRange(OffsetSpan LHS, OffsetSpan RHS);
0296   OffsetSpan computeImpl(Value *V);
0297   OffsetSpan computeValue(Value *V);
0298   bool CheckedZextOrTrunc(APInt &I);
0299 };
0300
0301 /// SizeOffsetValue - Used by \p ObjectSizeOffsetEvaluator, which works with
0302 /// \p Values.
0303 struct SizeOffsetWeakTrackingVH;
0304 struct SizeOffsetValue : public SizeOffsetType<Value *, SizeOffsetValue> {
0305   SizeOffsetValue() : SizeOffsetType(nullptr, nullptr) {}
0306   SizeOffsetValue(Value *Size, Value *Offset) : SizeOffsetType(Size, Offset) {}
0307   SizeOffsetValue(const SizeOffsetWeakTrackingVH &SOT);
0308
0309   static bool known(Value *V) { return V != nullptr; }
0310 };
0311
0312 /// SizeOffsetWeakTrackingVH - Used by \p ObjectSizeOffsetEvaluator in a
0313 /// \p DenseMap.
0314 struct SizeOffsetWeakTrackingVH
0315     : public SizeOffsetType<WeakTrackingVH, SizeOffsetWeakTrackingVH> {
0316   SizeOffsetWeakTrackingVH() : SizeOffsetType(nullptr, nullptr) {}
0317   SizeOffsetWeakTrackingVH(Value *Size, Value *Offset)
0318       : SizeOffsetType(Size, Offset) {}
0319   SizeOffsetWeakTrackingVH(const SizeOffsetValue &SOV)
0320       : SizeOffsetType(SOV.Size, SOV.Offset) {}
0321
0322   static bool known(WeakTrackingVH V) { return V.pointsToAliveValue(); }
0323 };
0324
0325 /// Evaluate the size and offset of an object pointed to by a Value*.
0326 /// May create code to compute the result at run-time.
0327 class ObjectSizeOffsetEvaluator
0328     : public InstVisitor<ObjectSizeOffsetEvaluator, SizeOffsetValue> {
0329   using BuilderTy = IRBuilder<TargetFolder, IRBuilderCallbackInserter>;
0330   using WeakEvalType = SizeOffsetWeakTrackingVH;
0331   using CacheMapTy = DenseMap<const Value *, WeakEvalType>;
0332   using PtrSetTy = SmallPtrSet<const Value *, 8>;
0333
0334   const DataLayout &DL;
0335   const TargetLibraryInfo *TLI;
0336   LLVMContext &Context;
0337   BuilderTy Builder;
0338   IntegerType *IntTy;
0339   Value *Zero;
0340   CacheMapTy CacheMap;
0341   PtrSetTy SeenVals;
0342   ObjectSizeOpts EvalOpts;
0343   SmallPtrSet<Instruction *, 8> InsertedInstructions;
0344
0345   SizeOffsetValue compute_(Value *V);
0346
0347 public:
0348   ObjectSizeOffsetEvaluator(const DataLayout &DL, const TargetLibraryInfo *TLI,
0349                             LLVMContext &Context, ObjectSizeOpts EvalOpts = {});
0350
0351   static SizeOffsetValue unknown() { return SizeOffsetValue(); }
0352
0353   SizeOffsetValue compute(Value *V);
0354
0355   // The individual instruction visitors should be treated as private.
0356   SizeOffsetValue visitAllocaInst(AllocaInst &I);
0357   SizeOffsetValue visitCallBase(CallBase &CB);
0358   SizeOffsetValue visitExtractElementInst(ExtractElementInst &I);
0359   SizeOffsetValue visitExtractValueInst(ExtractValueInst &I);
0360   SizeOffsetValue visitGEPOperator(GEPOperator &GEP);
0361   SizeOffsetValue visitIntToPtrInst(IntToPtrInst &);
0362   SizeOffsetValue visitLoadInst(LoadInst &I);
0363   SizeOffsetValue visitPHINode(PHINode &PHI);
0364   SizeOffsetValue visitSelectInst(SelectInst &I);
0365   SizeOffsetValue visitInstruction(Instruction &I);
0366 };
0367
0368 } // end namespace llvm
0369
0370 #endif // LLVM_ANALYSIS_MEMORYBUILTINS_H