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