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