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