include/llvm/Analysis/MemoryBuiltins.h

   1 //==- llvm/Analysis/MemoryBuiltins.h - Calls to memory builtins --*- C++ -*-==//
   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 #ifndef LLVM_ANALYSIS_MEMORYBUILTINS_H
  15 #define LLVM_ANALYSIS_MEMORYBUILTINS_H
  16
  17 #include "llvm/ADT/APInt.h"
  18 #include "llvm/ADT/DenseMap.h"
  19 #include "llvm/ADT/SmallPtrSet.h"
  20 #include "llvm/Analysis/TargetFolder.h"
  21 #include "llvm/IR/CallSite.h"
  22 #include "llvm/IR/IRBuilder.h"
  23 #include "llvm/IR/InstVisitor.h"
  24 #include "llvm/IR/ValueHandle.h"
  25 #include <cstdint>
  26 #include <utility>
  27
  28 namespace llvm {
  29
  30 class AllocaInst;
  31 class Argument;
  32 class CallInst;
  33 class ConstantInt;
  34 class ConstantPointerNull;
  35 class DataLayout;
  36 class ExtractElementInst;
  37 class ExtractValueInst;
  38 class GEPOperator;
  39 class GlobalAlias;
  40 class GlobalVariable;
  41 class Instruction;
  42 class IntegerType;
  43 class IntrinsicInst;
  44 class IntToPtrInst;
  45 class LLVMContext;
  46 class LoadInst;
  47 class PHINode;
  48 class PointerType;
  49 class SelectInst;
  50 class TargetLibraryInfo;
  51 class Type;
  52 class UndefValue;
  53 class Value;
  54
  55 /// Tests if a value is a call or invoke to a library function that
  56 /// allocates or reallocates memory (either malloc, calloc, realloc, or strdup
  57 /// like).
  58 bool isAllocationFn(const Value *V, const TargetLibraryInfo *TLI,
  59                     bool LookThroughBitCast = false);
  60
  61 /// Tests if a value is a call or invoke to a function that returns a
  62 /// NoAlias pointer (including malloc/calloc/realloc/strdup-like functions).
  63 bool isNoAliasFn(const Value *V, const TargetLibraryInfo *TLI,
  64                  bool LookThroughBitCast = false);
  65
  66 /// Tests if a value is a call or invoke to a library function that
  67 /// allocates uninitialized memory (such as malloc).
  68 bool isMallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
  69                     bool LookThroughBitCast = false);
  70
  71 /// Tests if a value is a call or invoke to a library function that
  72 /// allocates zero-filled memory (such as calloc).
  73 bool isCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
  74                     bool LookThroughBitCast = false);
  75
  76 /// Tests if a value is a call or invoke to a library function that
  77 /// allocates memory similar to malloc or calloc.
  78 bool isMallocOrCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
  79                             bool LookThroughBitCast = false);
  80
  81 /// Tests if a value is a call or invoke to a library function that
  82 /// allocates memory (either malloc, calloc, or strdup like).
  83 bool isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
  84                    bool LookThroughBitCast = false);
  85
  86 //===----------------------------------------------------------------------===//
  87 //  malloc Call Utility Functions.
  88 //
  89
  90 /// extractMallocCall - Returns the corresponding CallInst if the instruction
  91 /// is a malloc call.  Since CallInst::CreateMalloc() only creates calls, we
  92 /// ignore InvokeInst here.
  93 const CallInst *extractMallocCall(const Value *I, const TargetLibraryInfo *TLI);
  94 inline CallInst *extractMallocCall(Value *I, const TargetLibraryInfo *TLI) {
  95   return const_cast<CallInst*>(extractMallocCall((const Value*)I, TLI));
  96 }
  97
  98 /// getMallocType - Returns the PointerType resulting from the malloc call.
  99 /// The PointerType depends on the number of bitcast uses of the malloc call:
 100 ///   0: PointerType is the malloc calls' return type.
 101 ///   1: PointerType is the bitcast's result type.
 102 ///  >1: Unique PointerType cannot be determined, return NULL.
 103 PointerType *getMallocType(const CallInst *CI, const TargetLibraryInfo *TLI);
 104
 105 /// getMallocAllocatedType - Returns the Type allocated by malloc call.
 106 /// The Type depends on the number of bitcast uses of the malloc call:
 107 ///   0: PointerType is the malloc calls' return type.
 108 ///   1: PointerType is the bitcast's result type.
 109 ///  >1: Unique PointerType cannot be determined, return NULL.
 110 Type *getMallocAllocatedType(const CallInst *CI, const TargetLibraryInfo *TLI);
 111
 112 /// getMallocArraySize - Returns the array size of a malloc call.  If the
 113 /// argument passed to malloc is a multiple of the size of the malloced type,
 114 /// then return that multiple.  For non-array mallocs, the multiple is
 115 /// constant 1.  Otherwise, return NULL for mallocs whose array size cannot be
 116 /// determined.
 117 Value *getMallocArraySize(CallInst *CI, const DataLayout &DL,
 118                           const TargetLibraryInfo *TLI,
 119                           bool LookThroughSExt = false);
 120
 121 //===----------------------------------------------------------------------===//
 122 //  calloc Call Utility Functions.
 123 //
 124
 125 /// extractCallocCall - Returns the corresponding CallInst if the instruction
 126 /// is a calloc call.
 127 const CallInst *extractCallocCall(const Value *I, const TargetLibraryInfo *TLI);
 128 inline CallInst *extractCallocCall(Value *I, const TargetLibraryInfo *TLI) {
 129   return const_cast<CallInst*>(extractCallocCall((const Value*)I, TLI));
 130 }
 131
 132
 133 //===----------------------------------------------------------------------===//
 134 //  free Call Utility Functions.
 135 //
 136
 137 /// isFreeCall - Returns non-null if the value is a call to the builtin free()
 138 const CallInst *isFreeCall(const Value *I, const TargetLibraryInfo *TLI);
 139
 140 inline CallInst *isFreeCall(Value *I, const TargetLibraryInfo *TLI) {
 141   return const_cast<CallInst*>(isFreeCall((const Value*)I, TLI));
 142 }
 143
 144 //===----------------------------------------------------------------------===//
 145 //  Utility functions to compute size of objects.
 146 //
 147
 148 /// Various options to control the behavior of getObjectSize.
 149 struct ObjectSizeOpts {
 150   /// Controls how we handle conditional statements with unknown conditions.
 151   enum class Mode : uint8_t {
 152     /// Fail to evaluate an unknown condition.
 153     Exact,
 154     /// Evaluate all branches of an unknown condition. If all evaluations
 155     /// succeed, pick the minimum size.
 156     Min,
 157     /// Same as Min, except we pick the maximum size of all of the branches.
 158     Max
 159   };
 160
 161   /// How we want to evaluate this object's size.
 162   Mode EvalMode = Mode::Exact;
 163   /// Whether to round the result up to the alignment of allocas, byval
 164   /// arguments, and global variables.
 165   bool RoundToAlign = false;
 166   /// If this is true, null pointers in address space 0 will be treated as
 167   /// though they can't be evaluated. Otherwise, null is always considered to
 168   /// point to a 0 byte region of memory.
 169   bool NullIsUnknownSize = false;
 170 };
 171
 172 /// Compute the size of the object pointed by Ptr. Returns true and the
 173 /// object size in Size if successful, and false otherwise. In this context, by
 174 /// object we mean the region of memory starting at Ptr to the end of the
 175 /// underlying object pointed to by Ptr.
 176 bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL,
 177                    const TargetLibraryInfo *TLI, ObjectSizeOpts Opts = {});
 178
 179 /// Try to turn a call to \@llvm.objectsize into an integer value of the given
 180 /// Type. Returns null on failure. If MustSucceed is true, this function will
 181 /// not return null, and may return conservative values governed by the second
 182 /// argument of the call to objectsize.
 183 Value *lowerObjectSizeCall(IntrinsicInst *ObjectSize, const DataLayout &DL,
 184                            const TargetLibraryInfo *TLI, bool MustSucceed);
 185
 186
 187
 188 using SizeOffsetType = std::pair<APInt, APInt>;
 189
 190 /// Evaluate the size and offset of an object pointed to by a Value*
 191 /// statically. Fails if size or offset are not known at compile time.
 192 class ObjectSizeOffsetVisitor
 193   : public InstVisitor<ObjectSizeOffsetVisitor, SizeOffsetType> {
 194   const DataLayout &DL;
 195   const TargetLibraryInfo *TLI;
 196   ObjectSizeOpts Options;
 197   unsigned IntTyBits;
 198   APInt Zero;
 199   SmallPtrSet<Instruction *, 8> SeenInsts;
 200
 201   APInt align(APInt Size, uint64_t Align);
 202
 203   SizeOffsetType unknown() {
 204     return std::make_pair(APInt(), APInt());
 205   }
 206
 207 public:
 208   ObjectSizeOffsetVisitor(const DataLayout &DL, const TargetLibraryInfo *TLI,
 209                           LLVMContext &Context, ObjectSizeOpts Options = {});
 210
 211   SizeOffsetType compute(Value *V);
 212
 213   static bool knownSize(const SizeOffsetType &SizeOffset) {
 214     return SizeOffset.first.getBitWidth() > 1;
 215   }
 216
 217   static bool knownOffset(const SizeOffsetType &SizeOffset) {
 218     return SizeOffset.second.getBitWidth() > 1;
 219   }
 220
 221   static bool bothKnown(const SizeOffsetType &SizeOffset) {
 222     return knownSize(SizeOffset) && knownOffset(SizeOffset);
 223   }
 224
 225   // These are "private", except they can't actually be made private. Only
 226   // compute() should be used by external users.
 227   SizeOffsetType visitAllocaInst(AllocaInst &I);
 228   SizeOffsetType visitArgument(Argument &A);
 229   SizeOffsetType visitCallSite(CallSite CS);
 230   SizeOffsetType visitConstantPointerNull(ConstantPointerNull&);
 231   SizeOffsetType visitExtractElementInst(ExtractElementInst &I);
 232   SizeOffsetType visitExtractValueInst(ExtractValueInst &I);
 233   SizeOffsetType visitGEPOperator(GEPOperator &GEP);
 234   SizeOffsetType visitGlobalAlias(GlobalAlias &GA);
 235   SizeOffsetType visitGlobalVariable(GlobalVariable &GV);
 236   SizeOffsetType visitIntToPtrInst(IntToPtrInst&);
 237   SizeOffsetType visitLoadInst(LoadInst &I);
 238   SizeOffsetType visitPHINode(PHINode&);
 239   SizeOffsetType visitSelectInst(SelectInst &I);
 240   SizeOffsetType visitUndefValue(UndefValue&);
 241   SizeOffsetType visitInstruction(Instruction &I);
 242
 243 private:
 244   bool CheckedZextOrTrunc(APInt &I);
 245 };
 246
 247 using SizeOffsetEvalType = std::pair<Value *, Value *>;
 248
 249 /// Evaluate the size and offset of an object pointed to by a Value*.
 250 /// May create code to compute the result at run-time.
 251 class ObjectSizeOffsetEvaluator
 252   : public InstVisitor<ObjectSizeOffsetEvaluator, SizeOffsetEvalType> {
 253   using BuilderTy = IRBuilder<TargetFolder>;
 254   using WeakEvalType = std::pair<WeakTrackingVH, WeakTrackingVH>;
 255   using CacheMapTy = DenseMap<const Value *, WeakEvalType>;
 256   using PtrSetTy = SmallPtrSet<const Value *, 8>;
 257
 258   const DataLayout &DL;
 259   const TargetLibraryInfo *TLI;
 260   LLVMContext &Context;
 261   BuilderTy Builder;
 262   IntegerType *IntTy;
 263   Value *Zero;
 264   CacheMapTy CacheMap;
 265   PtrSetTy SeenVals;
 266   ObjectSizeOpts EvalOpts;
 267
 268   SizeOffsetEvalType compute_(Value *V);
 269
 270 public:
 271   static SizeOffsetEvalType unknown() {
 272     return std::make_pair(nullptr, nullptr);
 273   }
 274
 275   ObjectSizeOffsetEvaluator(const DataLayout &DL, const TargetLibraryInfo *TLI,
 276                             LLVMContext &Context, ObjectSizeOpts EvalOpts = {});
 277
 278   SizeOffsetEvalType compute(Value *V);
 279
 280   bool knownSize(SizeOffsetEvalType SizeOffset) {
 281     return SizeOffset.first;
 282   }
 283
 284   bool knownOffset(SizeOffsetEvalType SizeOffset) {
 285     return SizeOffset.second;
 286   }
 287
 288   bool anyKnown(SizeOffsetEvalType SizeOffset) {
 289     return knownSize(SizeOffset) || knownOffset(SizeOffset);
 290   }
 291
 292   bool bothKnown(SizeOffsetEvalType SizeOffset) {
 293     return knownSize(SizeOffset) && knownOffset(SizeOffset);
 294   }
 295
 296   // The individual instruction visitors should be treated as private.
 297   SizeOffsetEvalType visitAllocaInst(AllocaInst &I);
 298   SizeOffsetEvalType visitCallSite(CallSite CS);
 299   SizeOffsetEvalType visitExtractElementInst(ExtractElementInst &I);
 300   SizeOffsetEvalType visitExtractValueInst(ExtractValueInst &I);
 301   SizeOffsetEvalType visitGEPOperator(GEPOperator &GEP);
 302   SizeOffsetEvalType visitIntToPtrInst(IntToPtrInst&);
 303   SizeOffsetEvalType visitLoadInst(LoadInst &I);
 304   SizeOffsetEvalType visitPHINode(PHINode &PHI);
 305   SizeOffsetEvalType visitSelectInst(SelectInst &I);
 306   SizeOffsetEvalType visitInstruction(Instruction &I);
 307 };
 308
 309 } // end namespace llvm
 310
 311 #endif // LLVM_ANALYSIS_MEMORYBUILTINS_H