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