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