include/llvm/Analysis/MemoryBuiltins.h

   1 //===- llvm/Analysis/MemoryBuiltins.h- Calls to memory builtins -*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This family of functions identifies calls to builtin functions that allocate
  11 // or free memory.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_ANALYSIS_MEMORYBUILTINS_H
  16 #define LLVM_ANALYSIS_MEMORYBUILTINS_H
  17
  18 #include "llvm/ADT/DenseMap.h"
  19 #include "llvm/ADT/SmallPtrSet.h"
  20 #include "llvm/Analysis/TargetFolder.h"
  21 #include "llvm/IR/IRBuilder.h"
  22 #include "llvm/IR/InstVisitor.h"
  23 #include "llvm/IR/Operator.h"
  24 #include "llvm/IR/ValueHandle.h"
  25 #include "llvm/Support/DataTypes.h"
  26
  27 namespace llvm {
  28 class CallInst;
  29 class PointerType;
  30 class DataLayout;
  31 class TargetLibraryInfo;
  32 class Type;
  33 class Value;
  34
  35
  36 /// \brief Tests if a value is a call or invoke to a library function that
  37 /// allocates or reallocates memory (either malloc, calloc, realloc, or strdup
  38 /// like).
  39 bool isAllocationFn(const Value *V, const TargetLibraryInfo *TLI,
  40                     bool LookThroughBitCast = false);
  41
  42 /// \brief Tests if a value is a call or invoke to a function that returns a
  43 /// NoAlias pointer (including malloc/calloc/realloc/strdup-like functions).
  44 bool isNoAliasFn(const Value *V, const TargetLibraryInfo *TLI,
  45                  bool LookThroughBitCast = false);
  46
  47 /// \brief Tests if a value is a call or invoke to a library function that
  48 /// allocates uninitialized memory (such as malloc).
  49 bool isMallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
  50                     bool LookThroughBitCast = false);
  51
  52 /// \brief Tests if a value is a call or invoke to a library function that
  53 /// allocates zero-filled memory (such as calloc).
  54 bool isCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
  55                     bool LookThroughBitCast = false);
  56
  57 /// \brief Tests if a value is a call or invoke to a library function that
  58 /// allocates memory (either malloc, calloc, or strdup like).
  59 bool isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
  60                    bool LookThroughBitCast = false);
  61
  62 /// \brief Tests if a value is a call or invoke to a library function that
  63 /// reallocates memory (such as realloc).
  64 bool isReallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
  65                      bool LookThroughBitCast = false);
  66
  67 /// \brief Tests if a value is a call or invoke to a library function that
  68 /// allocates memory and never returns null (such as operator new).
  69 bool isOperatorNewLikeFn(const Value *V, const TargetLibraryInfo *TLI,
  70                          bool LookThroughBitCast = false);
  71
  72 //===----------------------------------------------------------------------===//
  73 //  malloc Call Utility Functions.
  74 //
  75
  76 /// extractMallocCall - Returns the corresponding CallInst if the instruction
  77 /// is a malloc call.  Since CallInst::CreateMalloc() only creates calls, we
  78 /// ignore InvokeInst here.
  79 const CallInst *extractMallocCall(const Value *I, const TargetLibraryInfo *TLI);
  80 static inline CallInst *extractMallocCall(Value *I,
  81                                           const TargetLibraryInfo *TLI) {
  82   return const_cast<CallInst*>(extractMallocCall((const Value*)I, TLI));
  83 }
  84
  85 /// getMallocType - Returns the PointerType resulting from the malloc call.
  86 /// The PointerType depends on the number of bitcast uses of the malloc call:
  87 ///   0: PointerType is the malloc calls' return type.
  88 ///   1: PointerType is the bitcast's result type.
  89 ///  >1: Unique PointerType cannot be determined, return NULL.
  90 PointerType *getMallocType(const CallInst *CI, const TargetLibraryInfo *TLI);
  91
  92 /// getMallocAllocatedType - Returns the Type allocated by malloc call.
  93 /// The Type depends on the number of bitcast uses of the malloc call:
  94 ///   0: PointerType is the malloc calls' return type.
  95 ///   1: PointerType is the bitcast's result type.
  96 ///  >1: Unique PointerType cannot be determined, return NULL.
  97 Type *getMallocAllocatedType(const CallInst *CI, const TargetLibraryInfo *TLI);
  98
  99 /// getMallocArraySize - Returns the array size of a malloc call.  If the
 100 /// argument passed to malloc is a multiple of the size of the malloced type,
 101 /// then return that multiple.  For non-array mallocs, the multiple is
 102 /// constant 1.  Otherwise, return NULL for mallocs whose array size cannot be
 103 /// determined.
 104 Value *getMallocArraySize(CallInst *CI, const DataLayout *DL,
 105                           const TargetLibraryInfo *TLI,
 106                           bool LookThroughSExt = false);
 107
 108
 109 //===----------------------------------------------------------------------===//
 110 //  calloc Call Utility Functions.
 111 //
 112
 113 /// extractCallocCall - Returns the corresponding CallInst if the instruction
 114 /// is a calloc call.
 115 const CallInst *extractCallocCall(const Value *I, const TargetLibraryInfo *TLI);
 116 static inline CallInst *extractCallocCall(Value *I,
 117                                           const TargetLibraryInfo *TLI) {
 118   return const_cast<CallInst*>(extractCallocCall((const Value*)I, TLI));
 119 }
 120
 121
 122 //===----------------------------------------------------------------------===//
 123 //  free Call Utility Functions.
 124 //
 125
 126 /// isFreeCall - Returns non-null if the value is a call to the builtin free()
 127 const CallInst *isFreeCall(const Value *I, const TargetLibraryInfo *TLI);
 128
 129 static inline CallInst *isFreeCall(Value *I, const TargetLibraryInfo *TLI) {
 130   return const_cast<CallInst*>(isFreeCall((const Value*)I, TLI));
 131 }
 132
 133
 134 //===----------------------------------------------------------------------===//
 135 //  Utility functions to compute size of objects.
 136 //
 137
 138 /// \brief Compute the size of the object pointed by Ptr. Returns true and the
 139 /// object size in Size if successful, and false otherwise. In this context, by
 140 /// object we mean the region of memory starting at Ptr to the end of the
 141 /// underlying object pointed to by Ptr.
 142 /// If RoundToAlign is true, then Size is rounded up to the aligment of allocas,
 143 /// byval arguments, and global variables.
 144 bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout *DL,
 145                    const TargetLibraryInfo *TLI, bool RoundToAlign = false);
 146
 147
 148
 149 typedef std::pair<APInt, APInt> SizeOffsetType;
 150
 151 /// \brief Evaluate the size and offset of an object pointed to by a Value*
 152 /// statically. Fails if size or offset are not known at compile time.
 153 class ObjectSizeOffsetVisitor
 154   : public InstVisitor<ObjectSizeOffsetVisitor, SizeOffsetType> {
 155
 156   const DataLayout *DL;
 157   const TargetLibraryInfo *TLI;
 158   bool RoundToAlign;
 159   unsigned IntTyBits;
 160   APInt Zero;
 161   SmallPtrSet<Instruction *, 8> SeenInsts;
 162
 163   APInt align(APInt Size, uint64_t Align);
 164
 165   SizeOffsetType unknown() {
 166     return std::make_pair(APInt(), APInt());
 167   }
 168
 169 public:
 170   ObjectSizeOffsetVisitor(const DataLayout *DL, const TargetLibraryInfo *TLI,
 171                           LLVMContext &Context, bool RoundToAlign = false);
 172
 173   SizeOffsetType compute(Value *V);
 174
 175   bool knownSize(SizeOffsetType &SizeOffset) {
 176     return SizeOffset.first.getBitWidth() > 1;
 177   }
 178
 179   bool knownOffset(SizeOffsetType &SizeOffset) {
 180     return SizeOffset.second.getBitWidth() > 1;
 181   }
 182
 183   bool bothKnown(SizeOffsetType &SizeOffset) {
 184     return knownSize(SizeOffset) && knownOffset(SizeOffset);
 185   }
 186
 187   // These are "private", except they can't actually be made private. Only
 188   // compute() should be used by external users.
 189   SizeOffsetType visitAllocaInst(AllocaInst &I);
 190   SizeOffsetType visitArgument(Argument &A);
 191   SizeOffsetType visitCallSite(CallSite CS);
 192   SizeOffsetType visitConstantPointerNull(ConstantPointerNull&);
 193   SizeOffsetType visitExtractElementInst(ExtractElementInst &I);
 194   SizeOffsetType visitExtractValueInst(ExtractValueInst &I);
 195   SizeOffsetType visitGEPOperator(GEPOperator &GEP);
 196   SizeOffsetType visitGlobalAlias(GlobalAlias &GA);
 197   SizeOffsetType visitGlobalVariable(GlobalVariable &GV);
 198   SizeOffsetType visitIntToPtrInst(IntToPtrInst&);
 199   SizeOffsetType visitLoadInst(LoadInst &I);
 200   SizeOffsetType visitPHINode(PHINode&);
 201   SizeOffsetType visitSelectInst(SelectInst &I);
 202   SizeOffsetType visitUndefValue(UndefValue&);
 203   SizeOffsetType visitInstruction(Instruction &I);
 204 };
 205
 206 typedef std::pair<Value*, Value*> SizeOffsetEvalType;
 207
 208
 209 /// \brief Evaluate the size and offset of an object pointed to by a Value*.
 210 /// May create code to compute the result at run-time.
 211 class ObjectSizeOffsetEvaluator
 212   : public InstVisitor<ObjectSizeOffsetEvaluator, SizeOffsetEvalType> {
 213
 214   typedef IRBuilder<true, TargetFolder> BuilderTy;
 215   typedef std::pair<WeakVH, WeakVH> WeakEvalType;
 216   typedef DenseMap<const Value*, WeakEvalType> CacheMapTy;
 217   typedef SmallPtrSet<const Value*, 8> PtrSetTy;
 218
 219   const DataLayout *DL;
 220   const TargetLibraryInfo *TLI;
 221   LLVMContext &Context;
 222   BuilderTy Builder;
 223   IntegerType *IntTy;
 224   Value *Zero;
 225   CacheMapTy CacheMap;
 226   PtrSetTy SeenVals;
 227   bool RoundToAlign;
 228
 229   SizeOffsetEvalType unknown() {
 230     return std::make_pair(nullptr, nullptr);
 231   }
 232   SizeOffsetEvalType compute_(Value *V);
 233
 234 public:
 235   ObjectSizeOffsetEvaluator(const DataLayout *DL, const TargetLibraryInfo *TLI,
 236                             LLVMContext &Context, bool RoundToAlign = false);
 237   SizeOffsetEvalType compute(Value *V);
 238
 239   bool knownSize(SizeOffsetEvalType SizeOffset) {
 240     return SizeOffset.first;
 241   }
 242
 243   bool knownOffset(SizeOffsetEvalType SizeOffset) {
 244     return SizeOffset.second;
 245   }
 246
 247   bool anyKnown(SizeOffsetEvalType SizeOffset) {
 248     return knownSize(SizeOffset) || knownOffset(SizeOffset);
 249   }
 250
 251   bool bothKnown(SizeOffsetEvalType SizeOffset) {
 252     return knownSize(SizeOffset) && knownOffset(SizeOffset);
 253   }
 254
 255   // The individual instruction visitors should be treated as private.
 256   SizeOffsetEvalType visitAllocaInst(AllocaInst &I);
 257   SizeOffsetEvalType visitCallSite(CallSite CS);
 258   SizeOffsetEvalType visitExtractElementInst(ExtractElementInst &I);
 259   SizeOffsetEvalType visitExtractValueInst(ExtractValueInst &I);
 260   SizeOffsetEvalType visitGEPOperator(GEPOperator &GEP);
 261   SizeOffsetEvalType visitIntToPtrInst(IntToPtrInst&);
 262   SizeOffsetEvalType visitLoadInst(LoadInst &I);
 263   SizeOffsetEvalType visitPHINode(PHINode &PHI);
 264   SizeOffsetEvalType visitSelectInst(SelectInst &I);
 265   SizeOffsetEvalType visitInstruction(Instruction &I);
 266 };
 267
 268 } // End llvm namespace
 269
 270 #endif