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