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