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