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