contrib/llvm/lib/Analysis/MemoryBuiltins.cpp

   1 //===------ MemoryBuiltins.cpp - Identify calls to memory builtins --------===//
   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 #include "llvm/Analysis/MemoryBuiltins.h"
  16 #include "llvm/ADT/STLExtras.h"
  17 #include "llvm/ADT/Statistic.h"
  18 #include "llvm/Analysis/TargetLibraryInfo.h"
  19 #include "llvm/Analysis/ValueTracking.h"
  20 #include "llvm/IR/DataLayout.h"
  21 #include "llvm/IR/GlobalVariable.h"
  22 #include "llvm/IR/Instructions.h"
  23 #include "llvm/IR/Intrinsics.h"
  24 #include "llvm/IR/Metadata.h"
  25 #include "llvm/IR/Module.h"
  26 #include "llvm/Support/Debug.h"
  27 #include "llvm/Support/MathExtras.h"
  28 #include "llvm/Support/raw_ostream.h"
  29 #include "llvm/Transforms/Utils/Local.h"
  30 using namespace llvm;
  31
  32 #define DEBUG_TYPE "memory-builtins"
  33
  34 enum AllocType : uint8_t {
  35   OpNewLike          = 1<<0, // allocates; never returns null
  36   MallocLike         = 1<<1 | OpNewLike, // allocates; may return null
  37   CallocLike         = 1<<2, // allocates + bzero
  38   ReallocLike        = 1<<3, // reallocates
  39   StrDupLike         = 1<<4,
  40   MallocOrCallocLike = MallocLike | CallocLike,
  41   AllocLike          = MallocLike | CallocLike | StrDupLike,
  42   AnyAlloc           = AllocLike | ReallocLike
  43 };
  44
  45 struct AllocFnsTy {
  46   AllocType AllocTy;
  47   unsigned NumParams;
  48   // First and Second size parameters (or -1 if unused)
  49   int FstParam, SndParam;
  50 };
  51
  52 // FIXME: certain users need more information. E.g., SimplifyLibCalls needs to
  53 // know which functions are nounwind, noalias, nocapture parameters, etc.
  54 static const std::pair<LibFunc, AllocFnsTy> AllocationFnData[] = {
  55   {LibFunc_malloc,              {MallocLike,  1, 0,  -1}},
  56   {LibFunc_valloc,              {MallocLike,  1, 0,  -1}},
  57   {LibFunc_Znwj,                {OpNewLike,   1, 0,  -1}}, // new(unsigned int)
  58   {LibFunc_ZnwjRKSt9nothrow_t,  {MallocLike,  2, 0,  -1}}, // new(unsigned int, nothrow)
  59   {LibFunc_Znwm,                {OpNewLike,   1, 0,  -1}}, // new(unsigned long)
  60   {LibFunc_ZnwmRKSt9nothrow_t,  {MallocLike,  2, 0,  -1}}, // new(unsigned long, nothrow)
  61   {LibFunc_Znaj,                {OpNewLike,   1, 0,  -1}}, // new[](unsigned int)
  62   {LibFunc_ZnajRKSt9nothrow_t,  {MallocLike,  2, 0,  -1}}, // new[](unsigned int, nothrow)
  63   {LibFunc_Znam,                {OpNewLike,   1, 0,  -1}}, // new[](unsigned long)
  64   {LibFunc_ZnamRKSt9nothrow_t,  {MallocLike,  2, 0,  -1}}, // new[](unsigned long, nothrow)
  65   {LibFunc_msvc_new_int,         {OpNewLike,   1, 0,  -1}}, // new(unsigned int)
  66   {LibFunc_msvc_new_int_nothrow, {MallocLike,  2, 0,  -1}}, // new(unsigned int, nothrow)
  67   {LibFunc_msvc_new_longlong,         {OpNewLike,   1, 0,  -1}}, // new(unsigned long long)
  68   {LibFunc_msvc_new_longlong_nothrow, {MallocLike,  2, 0,  -1}}, // new(unsigned long long, nothrow)
  69   {LibFunc_msvc_new_array_int,         {OpNewLike,   1, 0,  -1}}, // new[](unsigned int)
  70   {LibFunc_msvc_new_array_int_nothrow, {MallocLike,  2, 0,  -1}}, // new[](unsigned int, nothrow)
  71   {LibFunc_msvc_new_array_longlong,         {OpNewLike,   1, 0,  -1}}, // new[](unsigned long long)
  72   {LibFunc_msvc_new_array_longlong_nothrow, {MallocLike,  2, 0,  -1}}, // new[](unsigned long long, nothrow)
  73   {LibFunc_calloc,              {CallocLike,  2, 0,   1}},
  74   {LibFunc_realloc,             {ReallocLike, 2, 1,  -1}},
  75   {LibFunc_reallocf,            {ReallocLike, 2, 1,  -1}},
  76   {LibFunc_strdup,              {StrDupLike,  1, -1, -1}},
  77   {LibFunc_strndup,             {StrDupLike,  2, 1,  -1}}
  78   // TODO: Handle "int posix_memalign(void **, size_t, size_t)"
  79 };
  80
  81 static const Function *getCalledFunction(const Value *V, bool LookThroughBitCast,
  82                                          bool &IsNoBuiltin) {
  83   // Don't care about intrinsics in this case.
  84   if (isa<IntrinsicInst>(V))
  85     return nullptr;
  86
  87   if (LookThroughBitCast)
  88     V = V->stripPointerCasts();
  89
  90   ImmutableCallSite CS(V);
  91   if (!CS.getInstruction())
  92     return nullptr;
  93
  94   IsNoBuiltin = CS.isNoBuiltin();
  95
  96   const Function *Callee = CS.getCalledFunction();
  97   if (!Callee || !Callee->isDeclaration())
  98     return nullptr;
  99   return Callee;
 100 }
 101
 102 /// Returns the allocation data for the given value if it's either a call to a
 103 /// known allocation function, or a call to a function with the allocsize
 104 /// attribute.
 105 static Optional<AllocFnsTy>
 106 getAllocationDataForFunction(const Function *Callee, AllocType AllocTy,
 107                              const TargetLibraryInfo *TLI) {
 108   // Make sure that the function is available.
 109   StringRef FnName = Callee->getName();
 110   LibFunc TLIFn;
 111   if (!TLI || !TLI->getLibFunc(FnName, TLIFn) || !TLI->has(TLIFn))
 112     return None;
 113
 114   const auto *Iter = find_if(
 115       AllocationFnData, [TLIFn](const std::pair<LibFunc, AllocFnsTy> &P) {
 116         return P.first == TLIFn;
 117       });
 118
 119   if (Iter == std::end(AllocationFnData))
 120     return None;
 121
 122   const AllocFnsTy *FnData = &Iter->second;
 123   if ((FnData->AllocTy & AllocTy) != FnData->AllocTy)
 124     return None;
 125
 126   // Check function prototype.
 127   int FstParam = FnData->FstParam;
 128   int SndParam = FnData->SndParam;
 129   FunctionType *FTy = Callee->getFunctionType();
 130
 131   if (FTy->getReturnType() == Type::getInt8PtrTy(FTy->getContext()) &&
 132       FTy->getNumParams() == FnData->NumParams &&
 133       (FstParam < 0 ||
 134        (FTy->getParamType(FstParam)->isIntegerTy(32) ||
 135         FTy->getParamType(FstParam)->isIntegerTy(64))) &&
 136       (SndParam < 0 ||
 137        FTy->getParamType(SndParam)->isIntegerTy(32) ||
 138        FTy->getParamType(SndParam)->isIntegerTy(64)))
 139     return *FnData;
 140   return None;
 141 }
 142
 143 static Optional<AllocFnsTy> getAllocationData(const Value *V, AllocType AllocTy,
 144                                               const TargetLibraryInfo *TLI,
 145                                               bool LookThroughBitCast = false) {
 146   bool IsNoBuiltinCall;
 147   if (const Function *Callee =
 148           getCalledFunction(V, LookThroughBitCast, IsNoBuiltinCall))
 149     if (!IsNoBuiltinCall)
 150       return getAllocationDataForFunction(Callee, AllocTy, TLI);
 151   return None;
 152 }
 153
 154 static Optional<AllocFnsTy> getAllocationSize(const Value *V,
 155                                               const TargetLibraryInfo *TLI) {
 156   bool IsNoBuiltinCall;
 157   const Function *Callee =
 158       getCalledFunction(V, /*LookThroughBitCast=*/false, IsNoBuiltinCall);
 159   if (!Callee)
 160     return None;
 161
 162   // Prefer to use existing information over allocsize. This will give us an
 163   // accurate AllocTy.
 164   if (!IsNoBuiltinCall)
 165     if (Optional<AllocFnsTy> Data =
 166             getAllocationDataForFunction(Callee, AnyAlloc, TLI))
 167       return Data;
 168
 169   Attribute Attr = Callee->getFnAttribute(Attribute::AllocSize);
 170   if (Attr == Attribute())
 171     return None;
 172
 173   std::pair<unsigned, Optional<unsigned>> Args = Attr.getAllocSizeArgs();
 174
 175   AllocFnsTy Result;
 176   // Because allocsize only tells us how many bytes are allocated, we're not
 177   // really allowed to assume anything, so we use MallocLike.
 178   Result.AllocTy = MallocLike;
 179   Result.NumParams = Callee->getNumOperands();
 180   Result.FstParam = Args.first;
 181   Result.SndParam = Args.second.getValueOr(-1);
 182   return Result;
 183 }
 184
 185 static bool hasNoAliasAttr(const Value *V, bool LookThroughBitCast) {
 186   ImmutableCallSite CS(LookThroughBitCast ? V->stripPointerCasts() : V);
 187   return CS && CS.hasRetAttr(Attribute::NoAlias);
 188 }
 189
 190
 191 /// \brief Tests if a value is a call or invoke to a library function that
 192 /// allocates or reallocates memory (either malloc, calloc, realloc, or strdup
 193 /// like).
 194 bool llvm::isAllocationFn(const Value *V, const TargetLibraryInfo *TLI,
 195                           bool LookThroughBitCast) {
 196   return getAllocationData(V, AnyAlloc, TLI, LookThroughBitCast).hasValue();
 197 }
 198
 199 /// \brief Tests if a value is a call or invoke to a function that returns a
 200 /// NoAlias pointer (including malloc/calloc/realloc/strdup-like functions).
 201 bool llvm::isNoAliasFn(const Value *V, const TargetLibraryInfo *TLI,
 202                        bool LookThroughBitCast) {
 203   // it's safe to consider realloc as noalias since accessing the original
 204   // pointer is undefined behavior
 205   return isAllocationFn(V, TLI, LookThroughBitCast) ||
 206          hasNoAliasAttr(V, LookThroughBitCast);
 207 }
 208
 209 /// \brief Tests if a value is a call or invoke to a library function that
 210 /// allocates uninitialized memory (such as malloc).
 211 bool llvm::isMallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
 212                           bool LookThroughBitCast) {
 213   return getAllocationData(V, MallocLike, TLI, LookThroughBitCast).hasValue();
 214 }
 215
 216 /// \brief Tests if a value is a call or invoke to a library function that
 217 /// allocates zero-filled memory (such as calloc).
 218 bool llvm::isCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
 219                           bool LookThroughBitCast) {
 220   return getAllocationData(V, CallocLike, TLI, LookThroughBitCast).hasValue();
 221 }
 222
 223 /// \brief Tests if a value is a call or invoke to a library function that
 224 /// allocates memory similiar to malloc or calloc.
 225 bool llvm::isMallocOrCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
 226                                   bool LookThroughBitCast) {
 227   return getAllocationData(V, MallocOrCallocLike, TLI,
 228                            LookThroughBitCast).hasValue();
 229 }
 230
 231 /// \brief Tests if a value is a call or invoke to a library function that
 232 /// allocates memory (either malloc, calloc, or strdup like).
 233 bool llvm::isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
 234                          bool LookThroughBitCast) {
 235   return getAllocationData(V, AllocLike, TLI, LookThroughBitCast).hasValue();
 236 }
 237
 238 /// extractMallocCall - Returns the corresponding CallInst if the instruction
 239 /// is a malloc call.  Since CallInst::CreateMalloc() only creates calls, we
 240 /// ignore InvokeInst here.
 241 const CallInst *llvm::extractMallocCall(const Value *I,
 242                                         const TargetLibraryInfo *TLI) {
 243   return isMallocLikeFn(I, TLI) ? dyn_cast<CallInst>(I) : nullptr;
 244 }
 245
 246 static Value *computeArraySize(const CallInst *CI, const DataLayout &DL,
 247                                const TargetLibraryInfo *TLI,
 248                                bool LookThroughSExt = false) {
 249   if (!CI)
 250     return nullptr;
 251
 252   // The size of the malloc's result type must be known to determine array size.
 253   Type *T = getMallocAllocatedType(CI, TLI);
 254   if (!T || !T->isSized())
 255     return nullptr;
 256
 257   unsigned ElementSize = DL.getTypeAllocSize(T);
 258   if (StructType *ST = dyn_cast<StructType>(T))
 259     ElementSize = DL.getStructLayout(ST)->getSizeInBytes();
 260
 261   // If malloc call's arg can be determined to be a multiple of ElementSize,
 262   // return the multiple.  Otherwise, return NULL.
 263   Value *MallocArg = CI->getArgOperand(0);
 264   Value *Multiple = nullptr;
 265   if (ComputeMultiple(MallocArg, ElementSize, Multiple, LookThroughSExt))
 266     return Multiple;
 267
 268   return nullptr;
 269 }
 270
 271 /// getMallocType - Returns the PointerType resulting from the malloc call.
 272 /// The PointerType depends on the number of bitcast uses of the malloc call:
 273 ///   0: PointerType is the calls' return type.
 274 ///   1: PointerType is the bitcast's result type.
 275 ///  >1: Unique PointerType cannot be determined, return NULL.
 276 PointerType *llvm::getMallocType(const CallInst *CI,
 277                                  const TargetLibraryInfo *TLI) {
 278   assert(isMallocLikeFn(CI, TLI) && "getMallocType and not malloc call");
 279
 280   PointerType *MallocType = nullptr;
 281   unsigned NumOfBitCastUses = 0;
 282
 283   // Determine if CallInst has a bitcast use.
 284   for (Value::const_user_iterator UI = CI->user_begin(), E = CI->user_end();
 285        UI != E;)
 286     if (const BitCastInst *BCI = dyn_cast<BitCastInst>(*UI++)) {
 287       MallocType = cast<PointerType>(BCI->getDestTy());
 288       NumOfBitCastUses++;
 289     }
 290
 291   // Malloc call has 1 bitcast use, so type is the bitcast's destination type.
 292   if (NumOfBitCastUses == 1)
 293     return MallocType;
 294
 295   // Malloc call was not bitcast, so type is the malloc function's return type.
 296   if (NumOfBitCastUses == 0)
 297     return cast<PointerType>(CI->getType());
 298
 299   // Type could not be determined.
 300   return nullptr;
 301 }
 302
 303 /// getMallocAllocatedType - Returns the Type allocated by malloc call.
 304 /// The Type depends on the number of bitcast uses of the malloc call:
 305 ///   0: PointerType is the malloc calls' return type.
 306 ///   1: PointerType is the bitcast's result type.
 307 ///  >1: Unique PointerType cannot be determined, return NULL.
 308 Type *llvm::getMallocAllocatedType(const CallInst *CI,
 309                                    const TargetLibraryInfo *TLI) {
 310   PointerType *PT = getMallocType(CI, TLI);
 311   return PT ? PT->getElementType() : nullptr;
 312 }
 313
 314 /// getMallocArraySize - Returns the array size of a malloc call.  If the
 315 /// argument passed to malloc is a multiple of the size of the malloced type,
 316 /// then return that multiple.  For non-array mallocs, the multiple is
 317 /// constant 1.  Otherwise, return NULL for mallocs whose array size cannot be
 318 /// determined.
 319 Value *llvm::getMallocArraySize(CallInst *CI, const DataLayout &DL,
 320                                 const TargetLibraryInfo *TLI,
 321                                 bool LookThroughSExt) {
 322   assert(isMallocLikeFn(CI, TLI) && "getMallocArraySize and not malloc call");
 323   return computeArraySize(CI, DL, TLI, LookThroughSExt);
 324 }
 325
 326
 327 /// extractCallocCall - Returns the corresponding CallInst if the instruction
 328 /// is a calloc call.
 329 const CallInst *llvm::extractCallocCall(const Value *I,
 330                                         const TargetLibraryInfo *TLI) {
 331   return isCallocLikeFn(I, TLI) ? cast<CallInst>(I) : nullptr;
 332 }
 333
 334
 335 /// isFreeCall - Returns non-null if the value is a call to the builtin free()
 336 const CallInst *llvm::isFreeCall(const Value *I, const TargetLibraryInfo *TLI) {
 337   const CallInst *CI = dyn_cast<CallInst>(I);
 338   if (!CI || isa<IntrinsicInst>(CI))
 339     return nullptr;
 340   Function *Callee = CI->getCalledFunction();
 341   if (Callee == nullptr)
 342     return nullptr;
 343
 344   StringRef FnName = Callee->getName();
 345   LibFunc TLIFn;
 346   if (!TLI || !TLI->getLibFunc(FnName, TLIFn) || !TLI->has(TLIFn))
 347     return nullptr;
 348
 349   unsigned ExpectedNumParams;
 350   if (TLIFn == LibFunc_free ||
 351       TLIFn == LibFunc_ZdlPv || // operator delete(void*)
 352       TLIFn == LibFunc_ZdaPv || // operator delete[](void*)
 353       TLIFn == LibFunc_msvc_delete_ptr32 || // operator delete(void*)
 354       TLIFn == LibFunc_msvc_delete_ptr64 || // operator delete(void*)
 355       TLIFn == LibFunc_msvc_delete_array_ptr32 || // operator delete[](void*)
 356       TLIFn == LibFunc_msvc_delete_array_ptr64)   // operator delete[](void*)
 357     ExpectedNumParams = 1;
 358   else if (TLIFn == LibFunc_ZdlPvj ||              // delete(void*, uint)
 359            TLIFn == LibFunc_ZdlPvm ||              // delete(void*, ulong)
 360            TLIFn == LibFunc_ZdlPvRKSt9nothrow_t || // delete(void*, nothrow)
 361            TLIFn == LibFunc_ZdaPvj ||              // delete[](void*, uint)
 362            TLIFn == LibFunc_ZdaPvm ||              // delete[](void*, ulong)
 363            TLIFn == LibFunc_ZdaPvRKSt9nothrow_t || // delete[](void*, nothrow)
 364            TLIFn == LibFunc_msvc_delete_ptr32_int ||      // delete(void*, uint)
 365            TLIFn == LibFunc_msvc_delete_ptr64_longlong || // delete(void*, ulonglong)
 366            TLIFn == LibFunc_msvc_delete_ptr32_nothrow || // delete(void*, nothrow)
 367            TLIFn == LibFunc_msvc_delete_ptr64_nothrow || // delete(void*, nothrow)
 368            TLIFn == LibFunc_msvc_delete_array_ptr32_int ||      // delete[](void*, uint)
 369            TLIFn == LibFunc_msvc_delete_array_ptr64_longlong || // delete[](void*, ulonglong)
 370            TLIFn == LibFunc_msvc_delete_array_ptr32_nothrow || // delete[](void*, nothrow)
 371            TLIFn == LibFunc_msvc_delete_array_ptr64_nothrow)   // delete[](void*, nothrow)
 372     ExpectedNumParams = 2;
 373   else
 374     return nullptr;
 375
 376   // Check free prototype.
 377   // FIXME: workaround for PR5130, this will be obsolete when a nobuiltin
 378   // attribute will exist.
 379   FunctionType *FTy = Callee->getFunctionType();
 380   if (!FTy->getReturnType()->isVoidTy())
 381     return nullptr;
 382   if (FTy->getNumParams() != ExpectedNumParams)
 383     return nullptr;
 384   if (FTy->getParamType(0) != Type::getInt8PtrTy(Callee->getContext()))
 385     return nullptr;
 386
 387   return CI;
 388 }
 389
 390
 391
 392 //===----------------------------------------------------------------------===//
 393 //  Utility functions to compute size of objects.
 394 //
 395 static APInt getSizeWithOverflow(const SizeOffsetType &Data) {
 396   if (Data.second.isNegative() || Data.first.ult(Data.second))
 397     return APInt(Data.first.getBitWidth(), 0);
 398   return Data.first - Data.second;
 399 }
 400
 401 /// \brief Compute the size of the object pointed by Ptr. Returns true and the
 402 /// object size in Size if successful, and false otherwise.
 403 /// If RoundToAlign is true, then Size is rounded up to the aligment of allocas,
 404 /// byval arguments, and global variables.
 405 bool llvm::getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL,
 406                          const TargetLibraryInfo *TLI, ObjectSizeOpts Opts) {
 407   ObjectSizeOffsetVisitor Visitor(DL, TLI, Ptr->getContext(), Opts);
 408   SizeOffsetType Data = Visitor.compute(const_cast<Value*>(Ptr));
 409   if (!Visitor.bothKnown(Data))
 410     return false;
 411
 412   Size = getSizeWithOverflow(Data).getZExtValue();
 413   return true;
 414 }
 415
 416 ConstantInt *llvm::lowerObjectSizeCall(IntrinsicInst *ObjectSize,
 417                                        const DataLayout &DL,
 418                                        const TargetLibraryInfo *TLI,
 419                                        bool MustSucceed) {
 420   assert(ObjectSize->getIntrinsicID() == Intrinsic::objectsize &&
 421          "ObjectSize must be a call to llvm.objectsize!");
 422
 423   bool MaxVal = cast<ConstantInt>(ObjectSize->getArgOperand(1))->isZero();
 424   ObjectSizeOpts EvalOptions;
 425   // Unless we have to fold this to something, try to be as accurate as
 426   // possible.
 427   if (MustSucceed)
 428     EvalOptions.EvalMode =
 429         MaxVal ? ObjectSizeOpts::Mode::Max : ObjectSizeOpts::Mode::Min;
 430   else
 431     EvalOptions.EvalMode = ObjectSizeOpts::Mode::Exact;
 432
 433   EvalOptions.NullIsUnknownSize =
 434       cast<ConstantInt>(ObjectSize->getArgOperand(2))->isOne();
 435
 436   // FIXME: Does it make sense to just return a failure value if the size won't
 437   // fit in the output and `!MustSucceed`?
 438   uint64_t Size;
 439   auto *ResultType = cast<IntegerType>(ObjectSize->getType());
 440   if (getObjectSize(ObjectSize->getArgOperand(0), Size, DL, TLI, EvalOptions) &&
 441       isUIntN(ResultType->getBitWidth(), Size))
 442     return ConstantInt::get(ResultType, Size);
 443
 444   if (!MustSucceed)
 445     return nullptr;
 446
 447   return ConstantInt::get(ResultType, MaxVal ? -1ULL : 0);
 448 }
 449
 450 STATISTIC(ObjectVisitorArgument,
 451           "Number of arguments with unsolved size and offset");
 452 STATISTIC(ObjectVisitorLoad,
 453           "Number of load instructions with unsolved size and offset");
 454
 455
 456 APInt ObjectSizeOffsetVisitor::align(APInt Size, uint64_t Align) {
 457   if (Options.RoundToAlign && Align)
 458     return APInt(IntTyBits, alignTo(Size.getZExtValue(), Align));
 459   return Size;
 460 }
 461
 462 ObjectSizeOffsetVisitor::ObjectSizeOffsetVisitor(const DataLayout &DL,
 463                                                  const TargetLibraryInfo *TLI,
 464                                                  LLVMContext &Context,
 465                                                  ObjectSizeOpts Options)
 466     : DL(DL), TLI(TLI), Options(Options) {
 467   // Pointer size must be rechecked for each object visited since it could have
 468   // a different address space.
 469 }
 470
 471 SizeOffsetType ObjectSizeOffsetVisitor::compute(Value *V) {
 472   IntTyBits = DL.getPointerTypeSizeInBits(V->getType());
 473   Zero = APInt::getNullValue(IntTyBits);
 474
 475   V = V->stripPointerCasts();
 476   if (Instruction *I = dyn_cast<Instruction>(V)) {
 477     // If we have already seen this instruction, bail out. Cycles can happen in
 478     // unreachable code after constant propagation.
 479     if (!SeenInsts.insert(I).second)
 480       return unknown();
 481
 482     if (GEPOperator *GEP = dyn_cast<GEPOperator>(V))
 483       return visitGEPOperator(*GEP);
 484     return visit(*I);
 485   }
 486   if (Argument *A = dyn_cast<Argument>(V))
 487     return visitArgument(*A);
 488   if (ConstantPointerNull *P = dyn_cast<ConstantPointerNull>(V))
 489     return visitConstantPointerNull(*P);
 490   if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V))
 491     return visitGlobalAlias(*GA);
 492   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
 493     return visitGlobalVariable(*GV);
 494   if (UndefValue *UV = dyn_cast<UndefValue>(V))
 495     return visitUndefValue(*UV);
 496   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
 497     if (CE->getOpcode() == Instruction::IntToPtr)
 498       return unknown(); // clueless
 499     if (CE->getOpcode() == Instruction::GetElementPtr)
 500       return visitGEPOperator(cast<GEPOperator>(*CE));
 501   }
 502
 503   DEBUG(dbgs() << "ObjectSizeOffsetVisitor::compute() unhandled value: " << *V
 504         << '\n');
 505   return unknown();
 506 }
 507
 508 SizeOffsetType ObjectSizeOffsetVisitor::visitAllocaInst(AllocaInst &I) {
 509   if (!I.getAllocatedType()->isSized())
 510     return unknown();
 511
 512   APInt Size(IntTyBits, DL.getTypeAllocSize(I.getAllocatedType()));
 513   if (!I.isArrayAllocation())
 514     return std::make_pair(align(Size, I.getAlignment()), Zero);
 515
 516   Value *ArraySize = I.getArraySize();
 517   if (const ConstantInt *C = dyn_cast<ConstantInt>(ArraySize)) {
 518     Size *= C->getValue().zextOrSelf(IntTyBits);
 519     return std::make_pair(align(Size, I.getAlignment()), Zero);
 520   }
 521   return unknown();
 522 }
 523
 524 SizeOffsetType ObjectSizeOffsetVisitor::visitArgument(Argument &A) {
 525   // No interprocedural analysis is done at the moment.
 526   if (!A.hasByValOrInAllocaAttr()) {
 527     ++ObjectVisitorArgument;
 528     return unknown();
 529   }
 530   PointerType *PT = cast<PointerType>(A.getType());
 531   APInt Size(IntTyBits, DL.getTypeAllocSize(PT->getElementType()));
 532   return std::make_pair(align(Size, A.getParamAlignment()), Zero);
 533 }
 534
 535 SizeOffsetType ObjectSizeOffsetVisitor::visitCallSite(CallSite CS) {
 536   Optional<AllocFnsTy> FnData = getAllocationSize(CS.getInstruction(), TLI);
 537   if (!FnData)
 538     return unknown();
 539
 540   // Handle strdup-like functions separately.
 541   if (FnData->AllocTy == StrDupLike) {
 542     APInt Size(IntTyBits, GetStringLength(CS.getArgument(0)));
 543     if (!Size)
 544       return unknown();
 545
 546     // Strndup limits strlen.
 547     if (FnData->FstParam > 0) {
 548       ConstantInt *Arg =
 549           dyn_cast<ConstantInt>(CS.getArgument(FnData->FstParam));
 550       if (!Arg)
 551         return unknown();
 552
 553       APInt MaxSize = Arg->getValue().zextOrSelf(IntTyBits);
 554       if (Size.ugt(MaxSize))
 555         Size = MaxSize + 1;
 556     }
 557     return std::make_pair(Size, Zero);
 558   }
 559
 560   ConstantInt *Arg = dyn_cast<ConstantInt>(CS.getArgument(FnData->FstParam));
 561   if (!Arg)
 562     return unknown();
 563
 564   // When we're compiling N-bit code, and the user uses parameters that are
 565   // greater than N bits (e.g. uint64_t on a 32-bit build), we can run into
 566   // trouble with APInt size issues. This function handles resizing + overflow
 567   // checks for us.
 568   auto CheckedZextOrTrunc = [&](APInt &I) {
 569     // More bits than we can handle. Checking the bit width isn't necessary, but
 570     // it's faster than checking active bits, and should give `false` in the
 571     // vast majority of cases.
 572     if (I.getBitWidth() > IntTyBits && I.getActiveBits() > IntTyBits)
 573       return false;
 574     if (I.getBitWidth() != IntTyBits)
 575       I = I.zextOrTrunc(IntTyBits);
 576     return true;
 577   };
 578
 579   APInt Size = Arg->getValue();
 580   if (!CheckedZextOrTrunc(Size))
 581     return unknown();
 582
 583   // Size is determined by just 1 parameter.
 584   if (FnData->SndParam < 0)
 585     return std::make_pair(Size, Zero);
 586
 587   Arg = dyn_cast<ConstantInt>(CS.getArgument(FnData->SndParam));
 588   if (!Arg)
 589     return unknown();
 590
 591   APInt NumElems = Arg->getValue();
 592   if (!CheckedZextOrTrunc(NumElems))
 593     return unknown();
 594
 595   bool Overflow;
 596   Size = Size.umul_ov(NumElems, Overflow);
 597   return Overflow ? unknown() : std::make_pair(Size, Zero);
 598
 599   // TODO: handle more standard functions (+ wchar cousins):
 600   // - strdup / strndup
 601   // - strcpy / strncpy
 602   // - strcat / strncat
 603   // - memcpy / memmove
 604   // - strcat / strncat
 605   // - memset
 606 }
 607
 608 SizeOffsetType
 609 ObjectSizeOffsetVisitor::visitConstantPointerNull(ConstantPointerNull& CPN) {
 610   if (Options.NullIsUnknownSize && CPN.getType()->getAddressSpace() == 0)
 611     return unknown();
 612   return std::make_pair(Zero, Zero);
 613 }
 614
 615 SizeOffsetType
 616 ObjectSizeOffsetVisitor::visitExtractElementInst(ExtractElementInst&) {
 617   return unknown();
 618 }
 619
 620 SizeOffsetType
 621 ObjectSizeOffsetVisitor::visitExtractValueInst(ExtractValueInst&) {
 622   // Easy cases were already folded by previous passes.
 623   return unknown();
 624 }
 625
 626 SizeOffsetType ObjectSizeOffsetVisitor::visitGEPOperator(GEPOperator &GEP) {
 627   SizeOffsetType PtrData = compute(GEP.getPointerOperand());
 628   APInt Offset(IntTyBits, 0);
 629   if (!bothKnown(PtrData) || !GEP.accumulateConstantOffset(DL, Offset))
 630     return unknown();
 631
 632   return std::make_pair(PtrData.first, PtrData.second + Offset);
 633 }
 634
 635 SizeOffsetType ObjectSizeOffsetVisitor::visitGlobalAlias(GlobalAlias &GA) {
 636   if (GA.isInterposable())
 637     return unknown();
 638   return compute(GA.getAliasee());
 639 }
 640
 641 SizeOffsetType ObjectSizeOffsetVisitor::visitGlobalVariable(GlobalVariable &GV){
 642   if (!GV.hasDefinitiveInitializer())
 643     return unknown();
 644
 645   APInt Size(IntTyBits, DL.getTypeAllocSize(GV.getType()->getElementType()));
 646   return std::make_pair(align(Size, GV.getAlignment()), Zero);
 647 }
 648
 649 SizeOffsetType ObjectSizeOffsetVisitor::visitIntToPtrInst(IntToPtrInst&) {
 650   // clueless
 651   return unknown();
 652 }
 653
 654 SizeOffsetType ObjectSizeOffsetVisitor::visitLoadInst(LoadInst&) {
 655   ++ObjectVisitorLoad;
 656   return unknown();
 657 }
 658
 659 SizeOffsetType ObjectSizeOffsetVisitor::visitPHINode(PHINode&) {
 660   // too complex to analyze statically.
 661   return unknown();
 662 }
 663
 664 SizeOffsetType ObjectSizeOffsetVisitor::visitSelectInst(SelectInst &I) {
 665   SizeOffsetType TrueSide  = compute(I.getTrueValue());
 666   SizeOffsetType FalseSide = compute(I.getFalseValue());
 667   if (bothKnown(TrueSide) && bothKnown(FalseSide)) {
 668     if (TrueSide == FalseSide) {
 669         return TrueSide;
 670     }
 671
 672     APInt TrueResult = getSizeWithOverflow(TrueSide);
 673     APInt FalseResult = getSizeWithOverflow(FalseSide);
 674
 675     if (TrueResult == FalseResult) {
 676       return TrueSide;
 677     }
 678     if (Options.EvalMode == ObjectSizeOpts::Mode::Min) {
 679       if (TrueResult.slt(FalseResult))
 680         return TrueSide;
 681       return FalseSide;
 682     }
 683     if (Options.EvalMode == ObjectSizeOpts::Mode::Max) {
 684       if (TrueResult.sgt(FalseResult))
 685         return TrueSide;
 686       return FalseSide;
 687     }
 688   }
 689   return unknown();
 690 }
 691
 692 SizeOffsetType ObjectSizeOffsetVisitor::visitUndefValue(UndefValue&) {
 693   return std::make_pair(Zero, Zero);
 694 }
 695
 696 SizeOffsetType ObjectSizeOffsetVisitor::visitInstruction(Instruction &I) {
 697   DEBUG(dbgs() << "ObjectSizeOffsetVisitor unknown instruction:" << I << '\n');
 698   return unknown();
 699 }
 700
 701 ObjectSizeOffsetEvaluator::ObjectSizeOffsetEvaluator(
 702     const DataLayout &DL, const TargetLibraryInfo *TLI, LLVMContext &Context,
 703     bool RoundToAlign)
 704     : DL(DL), TLI(TLI), Context(Context), Builder(Context, TargetFolder(DL)),
 705       RoundToAlign(RoundToAlign) {
 706   // IntTy and Zero must be set for each compute() since the address space may
 707   // be different for later objects.
 708 }
 709
 710 SizeOffsetEvalType ObjectSizeOffsetEvaluator::compute(Value *V) {
 711   // XXX - Are vectors of pointers possible here?
 712   IntTy = cast<IntegerType>(DL.getIntPtrType(V->getType()));
 713   Zero = ConstantInt::get(IntTy, 0);
 714
 715   SizeOffsetEvalType Result = compute_(V);
 716
 717   if (!bothKnown(Result)) {
 718     // Erase everything that was computed in this iteration from the cache, so
 719     // that no dangling references are left behind. We could be a bit smarter if
 720     // we kept a dependency graph. It's probably not worth the complexity.
 721     for (const Value *SeenVal : SeenVals) {
 722       CacheMapTy::iterator CacheIt = CacheMap.find(SeenVal);
 723       // non-computable results can be safely cached
 724       if (CacheIt != CacheMap.end() && anyKnown(CacheIt->second))
 725         CacheMap.erase(CacheIt);
 726     }
 727   }
 728
 729   SeenVals.clear();
 730   return Result;
 731 }
 732
 733 SizeOffsetEvalType ObjectSizeOffsetEvaluator::compute_(Value *V) {
 734   ObjectSizeOpts ObjSizeOptions;
 735   ObjSizeOptions.RoundToAlign = RoundToAlign;
 736
 737   ObjectSizeOffsetVisitor Visitor(DL, TLI, Context, ObjSizeOptions);
 738   SizeOffsetType Const = Visitor.compute(V);
 739   if (Visitor.bothKnown(Const))
 740     return std::make_pair(ConstantInt::get(Context, Const.first),
 741                           ConstantInt::get(Context, Const.second));
 742
 743   V = V->stripPointerCasts();
 744
 745   // Check cache.
 746   CacheMapTy::iterator CacheIt = CacheMap.find(V);
 747   if (CacheIt != CacheMap.end())
 748     return CacheIt->second;
 749
 750   // Always generate code immediately before the instruction being
 751   // processed, so that the generated code dominates the same BBs.
 752   BuilderTy::InsertPointGuard Guard(Builder);
 753   if (Instruction *I = dyn_cast<Instruction>(V))
 754     Builder.SetInsertPoint(I);
 755
 756   // Now compute the size and offset.
 757   SizeOffsetEvalType Result;
 758
 759   // Record the pointers that were handled in this run, so that they can be
 760   // cleaned later if something fails. We also use this set to break cycles that
 761   // can occur in dead code.
 762   if (!SeenVals.insert(V).second) {
 763     Result = unknown();
 764   } else if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
 765     Result = visitGEPOperator(*GEP);
 766   } else if (Instruction *I = dyn_cast<Instruction>(V)) {
 767     Result = visit(*I);
 768   } else if (isa<Argument>(V) ||
 769              (isa<ConstantExpr>(V) &&
 770               cast<ConstantExpr>(V)->getOpcode() == Instruction::IntToPtr) ||
 771              isa<GlobalAlias>(V) ||
 772              isa<GlobalVariable>(V)) {
 773     // Ignore values where we cannot do more than ObjectSizeVisitor.
 774     Result = unknown();
 775   } else {
 776     DEBUG(dbgs() << "ObjectSizeOffsetEvaluator::compute() unhandled value: "
 777           << *V << '\n');
 778     Result = unknown();
 779   }
 780
 781   // Don't reuse CacheIt since it may be invalid at this point.
 782   CacheMap[V] = Result;
 783   return Result;
 784 }
 785
 786 SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitAllocaInst(AllocaInst &I) {
 787   if (!I.getAllocatedType()->isSized())
 788     return unknown();
 789
 790   // must be a VLA
 791   assert(I.isArrayAllocation());
 792   Value *ArraySize = I.getArraySize();
 793   Value *Size = ConstantInt::get(ArraySize->getType(),
 794                                  DL.getTypeAllocSize(I.getAllocatedType()));
 795   Size = Builder.CreateMul(Size, ArraySize);
 796   return std::make_pair(Size, Zero);
 797 }
 798
 799 SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitCallSite(CallSite CS) {
 800   Optional<AllocFnsTy> FnData = getAllocationSize(CS.getInstruction(), TLI);
 801   if (!FnData)
 802     return unknown();
 803
 804   // Handle strdup-like functions separately.
 805   if (FnData->AllocTy == StrDupLike) {
 806     // TODO
 807     return unknown();
 808   }
 809
 810   Value *FirstArg = CS.getArgument(FnData->FstParam);
 811   FirstArg = Builder.CreateZExt(FirstArg, IntTy);
 812   if (FnData->SndParam < 0)
 813     return std::make_pair(FirstArg, Zero);
 814
 815   Value *SecondArg = CS.getArgument(FnData->SndParam);
 816   SecondArg = Builder.CreateZExt(SecondArg, IntTy);
 817   Value *Size = Builder.CreateMul(FirstArg, SecondArg);
 818   return std::make_pair(Size, Zero);
 819
 820   // TODO: handle more standard functions (+ wchar cousins):
 821   // - strdup / strndup
 822   // - strcpy / strncpy
 823   // - strcat / strncat
 824   // - memcpy / memmove
 825   // - strcat / strncat
 826   // - memset
 827 }
 828
 829 SizeOffsetEvalType
 830 ObjectSizeOffsetEvaluator::visitExtractElementInst(ExtractElementInst&) {
 831   return unknown();
 832 }
 833
 834 SizeOffsetEvalType
 835 ObjectSizeOffsetEvaluator::visitExtractValueInst(ExtractValueInst&) {
 836   return unknown();
 837 }
 838
 839 SizeOffsetEvalType
 840 ObjectSizeOffsetEvaluator::visitGEPOperator(GEPOperator &GEP) {
 841   SizeOffsetEvalType PtrData = compute_(GEP.getPointerOperand());
 842   if (!bothKnown(PtrData))
 843     return unknown();
 844
 845   Value *Offset = EmitGEPOffset(&Builder, DL, &GEP, /*NoAssumptions=*/true);
 846   Offset = Builder.CreateAdd(PtrData.second, Offset);
 847   return std::make_pair(PtrData.first, Offset);
 848 }
 849
 850 SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitIntToPtrInst(IntToPtrInst&) {
 851   // clueless
 852   return unknown();
 853 }
 854
 855 SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitLoadInst(LoadInst&) {
 856   return unknown();
 857 }
 858
 859 SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitPHINode(PHINode &PHI) {
 860   // Create 2 PHIs: one for size and another for offset.
 861   PHINode *SizePHI   = Builder.CreatePHI(IntTy, PHI.getNumIncomingValues());
 862   PHINode *OffsetPHI = Builder.CreatePHI(IntTy, PHI.getNumIncomingValues());
 863
 864   // Insert right away in the cache to handle recursive PHIs.
 865   CacheMap[&PHI] = std::make_pair(SizePHI, OffsetPHI);
 866
 867   // Compute offset/size for each PHI incoming pointer.
 868   for (unsigned i = 0, e = PHI.getNumIncomingValues(); i != e; ++i) {
 869     Builder.SetInsertPoint(&*PHI.getIncomingBlock(i)->getFirstInsertionPt());
 870     SizeOffsetEvalType EdgeData = compute_(PHI.getIncomingValue(i));
 871
 872     if (!bothKnown(EdgeData)) {
 873       OffsetPHI->replaceAllUsesWith(UndefValue::get(IntTy));
 874       OffsetPHI->eraseFromParent();
 875       SizePHI->replaceAllUsesWith(UndefValue::get(IntTy));
 876       SizePHI->eraseFromParent();
 877       return unknown();
 878     }
 879     SizePHI->addIncoming(EdgeData.first, PHI.getIncomingBlock(i));
 880     OffsetPHI->addIncoming(EdgeData.second, PHI.getIncomingBlock(i));
 881   }
 882
 883   Value *Size = SizePHI, *Offset = OffsetPHI, *Tmp;
 884   if ((Tmp = SizePHI->hasConstantValue())) {
 885     Size = Tmp;
 886     SizePHI->replaceAllUsesWith(Size);
 887     SizePHI->eraseFromParent();
 888   }
 889   if ((Tmp = OffsetPHI->hasConstantValue())) {
 890     Offset = Tmp;
 891     OffsetPHI->replaceAllUsesWith(Offset);
 892     OffsetPHI->eraseFromParent();
 893   }
 894   return std::make_pair(Size, Offset);
 895 }
 896
 897 SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitSelectInst(SelectInst &I) {
 898   SizeOffsetEvalType TrueSide  = compute_(I.getTrueValue());
 899   SizeOffsetEvalType FalseSide = compute_(I.getFalseValue());
 900
 901   if (!bothKnown(TrueSide) || !bothKnown(FalseSide))
 902     return unknown();
 903   if (TrueSide == FalseSide)
 904     return TrueSide;
 905
 906   Value *Size = Builder.CreateSelect(I.getCondition(), TrueSide.first,
 907                                      FalseSide.first);
 908   Value *Offset = Builder.CreateSelect(I.getCondition(), TrueSide.second,
 909                                        FalseSide.second);
 910   return std::make_pair(Size, Offset);
 911 }
 912
 913 SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitInstruction(Instruction &I) {
 914   DEBUG(dbgs() << "ObjectSizeOffsetEvaluator unknown instruction:" << I <<'\n');
 915   return unknown();
 916 }