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