MemoryBuiltins.cpp revision 9827c8e1c96950d17a4dbb7ef9d9036501c40c1b
1f006b183e2d2bebcf6968d1dd7350397c95b0325Victor Hernandez//===------ MemoryBuiltins.cpp - Identify calls to memory builtins --------===// 2fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng// 3fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng// The LLVM Compiler Infrastructure 4fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng// 5fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng// This file is distributed under the University of Illinois Open Source 6fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng// License. See LICENSE.TXT for details. 7fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng// 8fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng//===----------------------------------------------------------------------===// 9fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng// 10f006b183e2d2bebcf6968d1dd7350397c95b0325Victor Hernandez// This family of functions identifies calls to builtin functions that allocate 11f006b183e2d2bebcf6968d1dd7350397c95b0325Victor Hernandez// or free memory. 12fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng// 13fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng//===----------------------------------------------------------------------===// 14fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 159e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes#define DEBUG_TYPE "memory-builtins" 169e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes#include "llvm/ADT/Statistic.h" 179e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes#include "llvm/ADT/STLExtras.h" 18f006b183e2d2bebcf6968d1dd7350397c95b0325Victor Hernandez#include "llvm/Analysis/MemoryBuiltins.h" 199e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes#include "llvm/GlobalVariable.h" 20fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng#include "llvm/Instructions.h" 219e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes#include "llvm/Intrinsics.h" 229e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes#include "llvm/Metadata.h" 23fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng#include "llvm/Module.h" 248e345a1c418608c49abb7c51a090bbb36f1273bcVictor Hernandez#include "llvm/Analysis/ValueTracking.h" 259e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes#include "llvm/Support/Debug.h" 269e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes#include "llvm/Support/MathExtras.h" 279e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes#include "llvm/Support/raw_ostream.h" 289d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez#include "llvm/Target/TargetData.h" 299e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes#include "llvm/Transforms/Utils/Local.h" 30fabcb9127f278a77b8aae5673be1115390c55050Evan Chengusing namespace llvm; 31fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 329e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopesenum AllocType { 339e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes MallocLike = 1<<0, // allocates 349e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes CallocLike = 1<<1, // allocates + bzero 359e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes ReallocLike = 1<<2, // reallocates 369e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes StrDupLike = 1<<3, 379e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes AllocLike = MallocLike | CallocLike | StrDupLike, 389e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes AnyAlloc = MallocLike | CallocLike | ReallocLike | StrDupLike 399e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes}; 409e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 419e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopesstruct AllocFnsTy { 429e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes const char *Name; 439e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes AllocType AllocTy; 449e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes unsigned char NumParams; 459e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // First and Second size parameters (or -1 if unused) 46ef22f04bad6f5037fd4cc4d144e0c418f6cb2edcNuno Lopes signed char FstParam, SndParam; 479e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes}; 489e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 4941a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes// FIXME: certain users need more information. E.g., SimplifyLibCalls needs to 5041a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes// know which functions are nounwind, noalias, nocapture parameters, etc. 519e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopesstatic const AllocFnsTy AllocationFnData[] = { 5241a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes {"malloc", MallocLike, 1, 0, -1}, 5341a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes {"valloc", MallocLike, 1, 0, -1}, 5441a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes {"_Znwj", MallocLike, 1, 0, -1}, // new(unsigned int) 5541a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes {"_ZnwjRKSt9nothrow_t", MallocLike, 2, 0, -1}, // new(unsigned int, nothrow) 5641a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes {"_Znwm", MallocLike, 1, 0, -1}, // new(unsigned long) 5741a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes {"_ZnwmRKSt9nothrow_t", MallocLike, 2, 0, -1}, // new(unsigned long, nothrow) 5841a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes {"_Znaj", MallocLike, 1, 0, -1}, // new[](unsigned int) 5941a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes {"_ZnajRKSt9nothrow_t", MallocLike, 2, 0, -1}, // new[](unsigned int, nothrow) 6041a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes {"_Znam", MallocLike, 1, 0, -1}, // new[](unsigned long) 6141a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes {"_ZnamRKSt9nothrow_t", MallocLike, 2, 0, -1}, // new[](unsigned long, nothrow) 6241a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes {"posix_memalign", MallocLike, 3, 2, -1}, 6341a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes {"calloc", CallocLike, 2, 0, 1}, 6441a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes {"realloc", ReallocLike, 2, 1, -1}, 6541a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes {"reallocf", ReallocLike, 2, 1, -1}, 6641a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes {"strdup", StrDupLike, 1, -1, -1}, 679827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes {"strndup", StrDupLike, 2, 1, -1} 689e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes}; 699e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 709e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 719e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopesstatic Function *getCalledFunction(const Value *V, bool LookThroughBitCast) { 729e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (LookThroughBitCast) 739e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes V = V->stripPointerCasts(); 742b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes 75d845c34170be5ece8aee3a1097849aa8ce9259cbNuno Lopes CallSite CS(const_cast<Value*>(V)); 76d845c34170be5ece8aee3a1097849aa8ce9259cbNuno Lopes if (!CS.getInstruction()) 779e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return 0; 78fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 792b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes Function *Callee = CS.getCalledFunction(); 809e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!Callee || !Callee->isDeclaration()) 819e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return 0; 829e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return Callee; 83fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng} 84fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 859e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes/// \brief Returns the allocation data for the given value if it is a call to a 869e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes/// known allocation function, and NULL otherwise. 879e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopesstatic const AllocFnsTy *getAllocationData(const Value *V, AllocType AllocTy, 889e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes bool LookThroughBitCast = false) { 899e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Function *Callee = getCalledFunction(V, LookThroughBitCast); 909e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!Callee) 919e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return 0; 92fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 939e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes unsigned i = 0; 949e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes bool found = false; 959e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes for ( ; i < array_lengthof(AllocationFnData); ++i) { 969e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (Callee->getName() == AllocationFnData[i].Name) { 979e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes found = true; 989e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes break; 999e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } 1009e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } 1019e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!found) 1029e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return 0; 103fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 1049e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes const AllocFnsTy *FnData = &AllocationFnData[i]; 1059e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if ((FnData->AllocTy & AllocTy) == 0) 1069e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return 0; 1079e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 1089e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // Check function prototype. 1099e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // FIXME: Check the nobuiltin metadata?? (PR5130) 110ef22f04bad6f5037fd4cc4d144e0c418f6cb2edcNuno Lopes int FstParam = FnData->FstParam; 111ef22f04bad6f5037fd4cc4d144e0c418f6cb2edcNuno Lopes int SndParam = FnData->SndParam; 112db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner FunctionType *FTy = Callee->getFunctionType(); 1139e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 1149e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (FTy->getReturnType() == Type::getInt8PtrTy(FTy->getContext()) && 1159e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes FTy->getNumParams() == FnData->NumParams && 116ef22f04bad6f5037fd4cc4d144e0c418f6cb2edcNuno Lopes (FstParam < 0 || 1179e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes (FTy->getParamType(FstParam)->isIntegerTy(32) || 1189e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes FTy->getParamType(FstParam)->isIntegerTy(64))) && 119ef22f04bad6f5037fd4cc4d144e0c418f6cb2edcNuno Lopes (SndParam < 0 || 1209e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes FTy->getParamType(SndParam)->isIntegerTy(32) || 1219e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes FTy->getParamType(SndParam)->isIntegerTy(64))) 1229e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return FnData; 1239e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return 0; 124fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng} 125fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 1269e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopesstatic bool hasNoAliasAttr(const Value *V, bool LookThroughBitCast) { 127e8742d084c54e9cd230fa03d368f0fedac2106cbNuno Lopes ImmutableCallSite CS(LookThroughBitCast ? V->stripPointerCasts() : V); 128e8742d084c54e9cd230fa03d368f0fedac2106cbNuno Lopes return CS && CS.hasFnAttr(Attribute::NoAlias); 129fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng} 130fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 1319e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 1322b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes/// \brief Tests if a value is a call or invoke to a library function that 1332b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes/// allocates or reallocates memory (either malloc, calloc, realloc, or strdup 1342b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes/// like). 1359e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopesbool llvm::isAllocationFn(const Value *V, bool LookThroughBitCast) { 1369e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return getAllocationData(V, AnyAlloc, LookThroughBitCast); 137fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng} 138fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 1392b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes/// \brief Tests if a value is a call or invoke to a function that returns a 14041a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes/// NoAlias pointer (including malloc/calloc/realloc/strdup-like functions). 1419e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopesbool llvm::isNoAliasFn(const Value *V, bool LookThroughBitCast) { 14241a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes // it's safe to consider realloc as noalias since accessing the original 14341a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes // pointer is undefined behavior 14441a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes return isAllocationFn(V, LookThroughBitCast) || 1459e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes hasNoAliasAttr(V, LookThroughBitCast); 146fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng} 147fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 1482b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes/// \brief Tests if a value is a call or invoke to a library function that 1492b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes/// allocates uninitialized memory (such as malloc). 1509e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopesbool llvm::isMallocLikeFn(const Value *V, bool LookThroughBitCast) { 1519e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return getAllocationData(V, MallocLike, LookThroughBitCast); 1529e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 1539e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 1542b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes/// \brief Tests if a value is a call or invoke to a library function that 1552b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes/// allocates zero-filled memory (such as calloc). 1569e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopesbool llvm::isCallocLikeFn(const Value *V, bool LookThroughBitCast) { 1579e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return getAllocationData(V, CallocLike, LookThroughBitCast); 1589e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 1599e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 1602b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes/// \brief Tests if a value is a call or invoke to a library function that 1612b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes/// allocates memory (either malloc, calloc, or strdup like). 1629e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopesbool llvm::isAllocLikeFn(const Value *V, bool LookThroughBitCast) { 1639e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return getAllocationData(V, AllocLike, LookThroughBitCast); 1649e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 1659e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 1662b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes/// \brief Tests if a value is a call or invoke to a library function that 1672b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes/// reallocates memory (such as realloc). 1689e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopesbool llvm::isReallocLikeFn(const Value *V, bool LookThroughBitCast) { 1699e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return getAllocationData(V, ReallocLike, LookThroughBitCast); 1709e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 1719e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 1729e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes/// extractMallocCall - Returns the corresponding CallInst if the instruction 1739e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes/// is a malloc call. Since CallInst::CreateMalloc() only creates calls, we 1749e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes/// ignore InvokeInst here. 1759e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopesconst CallInst *llvm::extractMallocCall(const Value *I) { 176eb7c6865cd8d44a882aa7c3e10e1d976f333344fNuno Lopes return isMallocLikeFn(I) ? dyn_cast<CallInst>(I) : 0; 177fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng} 178fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 1798e345a1c418608c49abb7c51a090bbb36f1273bcVictor Hernandezstatic Value *computeArraySize(const CallInst *CI, const TargetData *TD, 1808e345a1c418608c49abb7c51a090bbb36f1273bcVictor Hernandez bool LookThroughSExt = false) { 181fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng if (!CI) 18290f48e7c91a8faa875ba889ca66b137ffd46e34aVictor Hernandez return NULL; 183fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 1849d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez // The size of the malloc's result type must be known to determine array size. 185db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *T = getMallocAllocatedType(CI); 1869d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez if (!T || !T->isSized() || !TD) 18790f48e7c91a8faa875ba889ca66b137ffd46e34aVictor Hernandez return NULL; 188fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 1898e345a1c418608c49abb7c51a090bbb36f1273bcVictor Hernandez unsigned ElementSize = TD->getTypeAllocSize(T); 190db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner if (StructType *ST = dyn_cast<StructType>(T)) 1918e345a1c418608c49abb7c51a090bbb36f1273bcVictor Hernandez ElementSize = TD->getStructLayout(ST)->getSizeInBytes(); 1929d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez 193e3401c4fae95bc69dada2a3f9080d9f15349af61Gabor Greif // If malloc call's arg can be determined to be a multiple of ElementSize, 1948e345a1c418608c49abb7c51a090bbb36f1273bcVictor Hernandez // return the multiple. Otherwise, return NULL. 195e3401c4fae95bc69dada2a3f9080d9f15349af61Gabor Greif Value *MallocArg = CI->getArgOperand(0); 1968e345a1c418608c49abb7c51a090bbb36f1273bcVictor Hernandez Value *Multiple = NULL; 1978e345a1c418608c49abb7c51a090bbb36f1273bcVictor Hernandez if (ComputeMultiple(MallocArg, ElementSize, Multiple, 1983dbb9e64d6e9d1e8bf16f75ebe4fe59ffdf93dd3Dan Gohman LookThroughSExt)) 1998e345a1c418608c49abb7c51a090bbb36f1273bcVictor Hernandez return Multiple; 20088d9839d07a6b5a03484d664913de0f2b33d3bffVictor Hernandez 20190f48e7c91a8faa875ba889ca66b137ffd46e34aVictor Hernandez return NULL; 202fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng} 203fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 204fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng/// isArrayMalloc - Returns the corresponding CallInst if the instruction 20590f48e7c91a8faa875ba889ca66b137ffd46e34aVictor Hernandez/// is a call to malloc whose array size can be determined and the array size 20690f48e7c91a8faa875ba889ca66b137ffd46e34aVictor Hernandez/// is not constant 1. Otherwise, return NULL. 2077b550ccfc5a3346c17e0390a59e2d6d19bc52705Chris Lattnerconst CallInst *llvm::isArrayMalloc(const Value *I, const TargetData *TD) { 208fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng const CallInst *CI = extractMallocCall(I); 2098e345a1c418608c49abb7c51a090bbb36f1273bcVictor Hernandez Value *ArraySize = computeArraySize(CI, TD); 21090f48e7c91a8faa875ba889ca66b137ffd46e34aVictor Hernandez 21190f48e7c91a8faa875ba889ca66b137ffd46e34aVictor Hernandez if (ArraySize && 212e3401c4fae95bc69dada2a3f9080d9f15349af61Gabor Greif ArraySize != ConstantInt::get(CI->getArgOperand(0)->getType(), 1)) 21390f48e7c91a8faa875ba889ca66b137ffd46e34aVictor Hernandez return CI; 21490f48e7c91a8faa875ba889ca66b137ffd46e34aVictor Hernandez 21590f48e7c91a8faa875ba889ca66b137ffd46e34aVictor Hernandez // CI is a non-array malloc or we can't figure out that it is an array malloc. 21690f48e7c91a8faa875ba889ca66b137ffd46e34aVictor Hernandez return NULL; 217fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng} 218fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 219fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng/// getMallocType - Returns the PointerType resulting from the malloc call. 2209d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez/// The PointerType depends on the number of bitcast uses of the malloc call: 2219d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez/// 0: PointerType is the calls' return type. 2229d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez/// 1: PointerType is the bitcast's result type. 2239d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez/// >1: Unique PointerType cannot be determined, return NULL. 224db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris LattnerPointerType *llvm::getMallocType(const CallInst *CI) { 2259e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes assert(isMallocLikeFn(CI) && "getMallocType and not malloc call"); 226fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 227db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner PointerType *MallocType = NULL; 2289d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez unsigned NumOfBitCastUses = 0; 2299d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez 23088d9839d07a6b5a03484d664913de0f2b33d3bffVictor Hernandez // Determine if CallInst has a bitcast use. 23160ad781c61815ca5b8dc2a45a102e1c8af65992fGabor Greif for (Value::const_use_iterator UI = CI->use_begin(), E = CI->use_end(); 23288d9839d07a6b5a03484d664913de0f2b33d3bffVictor Hernandez UI != E; ) 2339d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez if (const BitCastInst *BCI = dyn_cast<BitCastInst>(*UI++)) { 2349d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez MallocType = cast<PointerType>(BCI->getDestTy()); 2359d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez NumOfBitCastUses++; 2369d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez } 23788d9839d07a6b5a03484d664913de0f2b33d3bffVictor Hernandez 2389d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez // Malloc call has 1 bitcast use, so type is the bitcast's destination type. 2399d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez if (NumOfBitCastUses == 1) 2409d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez return MallocType; 241fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 24260cfc03379c1ec3fac3dc807f5e93842c0b95f33Victor Hernandez // Malloc call was not bitcast, so type is the malloc function's return type. 2439d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez if (NumOfBitCastUses == 0) 24488d9839d07a6b5a03484d664913de0f2b33d3bffVictor Hernandez return cast<PointerType>(CI->getType()); 245fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 24688d9839d07a6b5a03484d664913de0f2b33d3bffVictor Hernandez // Type could not be determined. 24788d9839d07a6b5a03484d664913de0f2b33d3bffVictor Hernandez return NULL; 248fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng} 249fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 2509d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez/// getMallocAllocatedType - Returns the Type allocated by malloc call. 2519d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez/// The Type depends on the number of bitcast uses of the malloc call: 2529d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez/// 0: PointerType is the malloc calls' return type. 2539d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez/// 1: PointerType is the bitcast's result type. 2549d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez/// >1: Unique PointerType cannot be determined, return NULL. 255db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris LattnerType *llvm::getMallocAllocatedType(const CallInst *CI) { 256db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner PointerType *PT = getMallocType(CI); 257fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng return PT ? PT->getElementType() : NULL; 258fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng} 259fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 26090f48e7c91a8faa875ba889ca66b137ffd46e34aVictor Hernandez/// getMallocArraySize - Returns the array size of a malloc call. If the 26190f48e7c91a8faa875ba889ca66b137ffd46e34aVictor Hernandez/// argument passed to malloc is a multiple of the size of the malloced type, 26290f48e7c91a8faa875ba889ca66b137ffd46e34aVictor Hernandez/// then return that multiple. For non-array mallocs, the multiple is 26390f48e7c91a8faa875ba889ca66b137ffd46e34aVictor Hernandez/// constant 1. Otherwise, return NULL for mallocs whose array size cannot be 2642491ce03535cf8ec171570d2e28df63e4db3dd6bVictor Hernandez/// determined. 2658e345a1c418608c49abb7c51a090bbb36f1273bcVictor HernandezValue *llvm::getMallocArraySize(CallInst *CI, const TargetData *TD, 2668e345a1c418608c49abb7c51a090bbb36f1273bcVictor Hernandez bool LookThroughSExt) { 2679e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes assert(isMallocLikeFn(CI) && "getMallocArraySize and not malloc call"); 2688e345a1c418608c49abb7c51a090bbb36f1273bcVictor Hernandez return computeArraySize(CI, TD, LookThroughSExt); 269fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng} 27066284e063a1e46500acae48bdc0e4a00652021d1Victor Hernandez 271252ef566e8734b6bcf46434d0a7954c9eda0bd96Nuno Lopes 272252ef566e8734b6bcf46434d0a7954c9eda0bd96Nuno Lopes/// extractCallocCall - Returns the corresponding CallInst if the instruction 273252ef566e8734b6bcf46434d0a7954c9eda0bd96Nuno Lopes/// is a calloc call. 274252ef566e8734b6bcf46434d0a7954c9eda0bd96Nuno Lopesconst CallInst *llvm::extractCallocCall(const Value *I) { 2759e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return isCallocLikeFn(I) ? cast<CallInst>(I) : 0; 276252ef566e8734b6bcf46434d0a7954c9eda0bd96Nuno Lopes} 277252ef566e8734b6bcf46434d0a7954c9eda0bd96Nuno Lopes 278046e78ce55a7c3d82b7b6758d2d77f2d99f970bfVictor Hernandez 27902680f946b8dcbeff3b8d7236030678551b15a6cGabor Greif/// isFreeCall - Returns non-null if the value is a call to the builtin free() 28002680f946b8dcbeff3b8d7236030678551b15a6cGabor Greifconst CallInst *llvm::isFreeCall(const Value *I) { 28166284e063a1e46500acae48bdc0e4a00652021d1Victor Hernandez const CallInst *CI = dyn_cast<CallInst>(I); 28266284e063a1e46500acae48bdc0e4a00652021d1Victor Hernandez if (!CI) 28302680f946b8dcbeff3b8d7236030678551b15a6cGabor Greif return 0; 2843ad70d5d61f3f86fb5bc167e157680fc107a1173Victor Hernandez Function *Callee = CI->getCalledFunction(); 28542e72ca3d00dbe073fbb39e181caa7f0c4c171b7Nick Lewycky if (Callee == 0 || !Callee->isDeclaration()) 28642e72ca3d00dbe073fbb39e181caa7f0c4c171b7Nick Lewycky return 0; 28742e72ca3d00dbe073fbb39e181caa7f0c4c171b7Nick Lewycky 28842e72ca3d00dbe073fbb39e181caa7f0c4c171b7Nick Lewycky if (Callee->getName() != "free" && 2891ace169c3d2ffd6596e0533c37df206430e8b707Nick Lewycky Callee->getName() != "_ZdlPv" && // operator delete(void*) 2901ace169c3d2ffd6596e0533c37df206430e8b707Nick Lewycky Callee->getName() != "_ZdaPv") // operator delete[](void*) 29102680f946b8dcbeff3b8d7236030678551b15a6cGabor Greif return 0; 29266284e063a1e46500acae48bdc0e4a00652021d1Victor Hernandez 29366284e063a1e46500acae48bdc0e4a00652021d1Victor Hernandez // Check free prototype. 29466284e063a1e46500acae48bdc0e4a00652021d1Victor Hernandez // FIXME: workaround for PR5130, this will be obsolete when a nobuiltin 29566284e063a1e46500acae48bdc0e4a00652021d1Victor Hernandez // attribute will exist. 296db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner FunctionType *FTy = Callee->getFunctionType(); 2973ad70d5d61f3f86fb5bc167e157680fc107a1173Victor Hernandez if (!FTy->getReturnType()->isVoidTy()) 29802680f946b8dcbeff3b8d7236030678551b15a6cGabor Greif return 0; 29966284e063a1e46500acae48bdc0e4a00652021d1Victor Hernandez if (FTy->getNumParams() != 1) 30002680f946b8dcbeff3b8d7236030678551b15a6cGabor Greif return 0; 301ebb2189904564c7c6193e7f23904f1ced7975480Chris Lattner if (FTy->getParamType(0) != Type::getInt8PtrTy(Callee->getContext())) 30202680f946b8dcbeff3b8d7236030678551b15a6cGabor Greif return 0; 30366284e063a1e46500acae48bdc0e4a00652021d1Victor Hernandez 30402680f946b8dcbeff3b8d7236030678551b15a6cGabor Greif return CI; 30566284e063a1e46500acae48bdc0e4a00652021d1Victor Hernandez} 3069e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3079e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3089e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3099e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes//===----------------------------------------------------------------------===// 3109e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes// Utility functions to compute size of objects. 3119e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes// 3129e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3139e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3149e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes/// \brief Compute the size of the object pointed by Ptr. Returns true and the 3159e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes/// object size in Size if successful, and false otherwise. 3169e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes/// If RoundToAlign is true, then Size is rounded up to the aligment of allocas, 3179e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes/// byval arguments, and global variables. 3189e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopesbool llvm::getObjectSize(const Value *Ptr, uint64_t &Size, const TargetData *TD, 3199e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes bool RoundToAlign) { 3209e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!TD) 3219e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return false; 3229e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3239e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes ObjectSizeOffsetVisitor Visitor(TD, Ptr->getContext(), RoundToAlign); 3249e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizeOffsetType Data = Visitor.compute(const_cast<Value*>(Ptr)); 3259e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!Visitor.bothKnown(Data)) 3269e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return false; 3279e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3289e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes APInt ObjSize = Data.first, Offset = Data.second; 3299e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // check for overflow 3309e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (Offset.slt(0) || ObjSize.ult(Offset)) 3319e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Size = 0; 3329e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes else 3339e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Size = (ObjSize - Offset).getZExtValue(); 3349e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return true; 3359e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 3369e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3379e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3389e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSTATISTIC(ObjectVisitorArgument, 3399e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes "Number of arguments with unsolved size and offset"); 3409e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSTATISTIC(ObjectVisitorLoad, 3419e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes "Number of load instructions with unsolved size and offset"); 3429e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3439e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3449e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesAPInt ObjectSizeOffsetVisitor::align(APInt Size, uint64_t Align) { 3459e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (RoundToAlign && Align) 3469e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return APInt(IntTyBits, RoundUpToAlignment(Size.getZExtValue(), Align)); 3479e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return Size; 3489e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 3499e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3509e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesObjectSizeOffsetVisitor::ObjectSizeOffsetVisitor(const TargetData *TD, 3519e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes LLVMContext &Context, 3529e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes bool RoundToAlign) 3539e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes: TD(TD), RoundToAlign(RoundToAlign) { 3549e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes IntegerType *IntTy = TD->getIntPtrType(Context); 3559e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes IntTyBits = IntTy->getBitWidth(); 3569e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Zero = APInt::getNullValue(IntTyBits); 3579e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 3589e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3599e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType ObjectSizeOffsetVisitor::compute(Value *V) { 3609e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes V = V->stripPointerCasts(); 3619e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3629e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) 3639e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return visitGEPOperator(*GEP); 3649e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (Instruction *I = dyn_cast<Instruction>(V)) 3659e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return visit(*I); 3669e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (Argument *A = dyn_cast<Argument>(V)) 3679e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return visitArgument(*A); 3689e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (ConstantPointerNull *P = dyn_cast<ConstantPointerNull>(V)) 3699e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return visitConstantPointerNull(*P); 3709e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) 3719e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return visitGlobalVariable(*GV); 3729e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (UndefValue *UV = dyn_cast<UndefValue>(V)) 3739e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return visitUndefValue(*UV); 3749e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 3759e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (CE->getOpcode() == Instruction::IntToPtr) 3769e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); // clueless 3779e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3789e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes DEBUG(dbgs() << "ObjectSizeOffsetVisitor::compute() unhandled value: " << *V 3799e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes << '\n'); 3809e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 3819e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 3829e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3839e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType ObjectSizeOffsetVisitor::visitAllocaInst(AllocaInst &I) { 3849e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!I.getAllocatedType()->isSized()) 3859e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 3869e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3879e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes APInt Size(IntTyBits, TD->getTypeAllocSize(I.getAllocatedType())); 3889e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!I.isArrayAllocation()) 3899e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(align(Size, I.getAlignment()), Zero); 3909e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3919e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Value *ArraySize = I.getArraySize(); 3929e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (const ConstantInt *C = dyn_cast<ConstantInt>(ArraySize)) { 3939e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Size *= C->getValue().zextOrSelf(IntTyBits); 3949e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(align(Size, I.getAlignment()), Zero); 3959e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } 3969e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 3979e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 3989e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3999e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType ObjectSizeOffsetVisitor::visitArgument(Argument &A) { 4009e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // no interprocedural analysis is done at the moment 4019e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!A.hasByValAttr()) { 4029e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes ++ObjectVisitorArgument; 4039e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 4049e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } 4059e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes PointerType *PT = cast<PointerType>(A.getType()); 4069e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes APInt Size(IntTyBits, TD->getTypeAllocSize(PT->getElementType())); 4079e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(align(Size, A.getParamAlignment()), Zero); 4089e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 4099e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 4109e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType ObjectSizeOffsetVisitor::visitCallSite(CallSite CS) { 4119e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes const AllocFnsTy *FnData = getAllocationData(CS.getInstruction(), AnyAlloc); 4129e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!FnData) 4139e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 4149e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 4159e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // handle strdup-like functions separately 4169e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (FnData->AllocTy == StrDupLike) { 4179827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes APInt Size(IntTyBits, GetStringLength(CS.getArgument(0))); 4189827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes if (!Size) 4199827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes return unknown(); 4209827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes 4219827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes // strndup limits strlen 4229827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes if (FnData->FstParam > 0) { 4239827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes ConstantInt *Arg= dyn_cast<ConstantInt>(CS.getArgument(FnData->FstParam)); 4249827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes if (!Arg) 4259827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes return unknown(); 4269827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes 4279827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes APInt MaxSize = Arg->getValue().zextOrSelf(IntTyBits); 4289827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes if (Size.ugt(MaxSize)) 4299827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes Size = MaxSize + 1; 4309827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes } 4319827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes return std::make_pair(Size, Zero); 4329e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } 4339e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 4349e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes ConstantInt *Arg = dyn_cast<ConstantInt>(CS.getArgument(FnData->FstParam)); 4359e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!Arg) 4369e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 4379e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 438034dd6c6a118cf78ebfa6bf3496cd5b0df578a9eNuno Lopes APInt Size = Arg->getValue().zextOrSelf(IntTyBits); 4399e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // size determined by just 1 parameter 440ef22f04bad6f5037fd4cc4d144e0c418f6cb2edcNuno Lopes if (FnData->SndParam < 0) 4419e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(Size, Zero); 4429e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 4439e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Arg = dyn_cast<ConstantInt>(CS.getArgument(FnData->SndParam)); 4449e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!Arg) 4459e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 4469e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 447034dd6c6a118cf78ebfa6bf3496cd5b0df578a9eNuno Lopes Size *= Arg->getValue().zextOrSelf(IntTyBits); 4489e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(Size, Zero); 4499e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 4509e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // TODO: handle more standard functions (+ wchar cousins): 4519e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // - strdup / strndup 4529e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // - strcpy / strncpy 4539e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // - strcat / strncat 4549e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // - memcpy / memmove 4559e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // - strcat / strncat 4569e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // - memset 4579e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 4589e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 4599e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType 4609e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesObjectSizeOffsetVisitor::visitConstantPointerNull(ConstantPointerNull&) { 4619e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(Zero, Zero); 4629e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 4639e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 4649e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType 46541a3f251346681e21171879dce409b2e6a3ba750Nuno LopesObjectSizeOffsetVisitor::visitExtractElementInst(ExtractElementInst&) { 46641a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes return unknown(); 46741a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes} 46841a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes 46941a3f251346681e21171879dce409b2e6a3ba750Nuno LopesSizeOffsetType 4709e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesObjectSizeOffsetVisitor::visitExtractValueInst(ExtractValueInst&) { 4719e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // Easy cases were already folded by previous passes. 4729e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 4739e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 4749e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 4759e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType ObjectSizeOffsetVisitor::visitGEPOperator(GEPOperator &GEP) { 4769e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizeOffsetType PtrData = compute(GEP.getPointerOperand()); 4779e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!bothKnown(PtrData) || !GEP.hasAllConstantIndices()) 4789e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 4799e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 4809e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SmallVector<Value*, 8> Ops(GEP.idx_begin(), GEP.idx_end()); 4819e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes APInt Offset(IntTyBits,TD->getIndexedOffset(GEP.getPointerOperandType(),Ops)); 4829e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(PtrData.first, PtrData.second + Offset); 4839e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 4849e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 4859e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType ObjectSizeOffsetVisitor::visitGlobalVariable(GlobalVariable &GV){ 4869e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!GV.hasDefinitiveInitializer()) 4879e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 4889e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 4899e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes APInt Size(IntTyBits, TD->getTypeAllocSize(GV.getType()->getElementType())); 4909e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(align(Size, GV.getAlignment()), Zero); 4919e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 4929e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 4939e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType ObjectSizeOffsetVisitor::visitIntToPtrInst(IntToPtrInst&) { 4949e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // clueless 4959e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 4969e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 4979e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 4989e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType ObjectSizeOffsetVisitor::visitLoadInst(LoadInst&) { 4999e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes ++ObjectVisitorLoad; 5009e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 5019e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 5029e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5039e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType ObjectSizeOffsetVisitor::visitPHINode(PHINode&) { 5049e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // too complex to analyze statically. 5059e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 5069e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 5079e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5089e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType ObjectSizeOffsetVisitor::visitSelectInst(SelectInst &I) { 5099e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizeOffsetType TrueSide = compute(I.getTrueValue()); 5109e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizeOffsetType FalseSide = compute(I.getFalseValue()); 5119e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (bothKnown(TrueSide) && bothKnown(FalseSide) && TrueSide == FalseSide) 5129e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return TrueSide; 5139e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 5149e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 5159e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5169e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType ObjectSizeOffsetVisitor::visitUndefValue(UndefValue&) { 5179e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(Zero, Zero); 5189e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 5199e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5209e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType ObjectSizeOffsetVisitor::visitInstruction(Instruction &I) { 5219e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes DEBUG(dbgs() << "ObjectSizeOffsetVisitor unknown instruction:" << I << '\n'); 5229e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 5239e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 5249e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5259e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5269e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesObjectSizeOffsetEvaluator::ObjectSizeOffsetEvaluator(const TargetData *TD, 5279e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes LLVMContext &Context) 5289e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes: TD(TD), Context(Context), Builder(Context, TargetFolder(TD)), 5299e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesVisitor(TD, Context) { 5309e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes IntTy = TD->getIntPtrType(Context); 5319e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Zero = ConstantInt::get(IntTy, 0); 5329e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 5339e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5349e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetEvalType ObjectSizeOffsetEvaluator::compute(Value *V) { 5359e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizeOffsetEvalType Result = compute_(V); 5369e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5379e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!bothKnown(Result)) { 5389e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // erase everything that was computed in this iteration from the cache, so 5399e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // that no dangling references are left behind. We could be a bit smarter if 5409e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // we kept a dependency graph. It's probably not worth the complexity. 5419e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes for (PtrSetTy::iterator I=SeenVals.begin(), E=SeenVals.end(); I != E; ++I) { 5429e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes CacheMapTy::iterator CacheIt = CacheMap.find(*I); 5439e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // non-computable results can be safely cached 5449e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (CacheIt != CacheMap.end() && anyKnown(CacheIt->second)) 5459e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes CacheMap.erase(CacheIt); 5469e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } 5479e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } 5489e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5499e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SeenVals.clear(); 5509e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return Result; 5519e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 5529e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5539e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetEvalType ObjectSizeOffsetEvaluator::compute_(Value *V) { 5549e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizeOffsetType Const = Visitor.compute(V); 5559e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (Visitor.bothKnown(Const)) 5569e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(ConstantInt::get(Context, Const.first), 5579e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes ConstantInt::get(Context, Const.second)); 5589e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5599e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes V = V->stripPointerCasts(); 5609e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5619e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // check cache 5629e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes CacheMapTy::iterator CacheIt = CacheMap.find(V); 5639e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (CacheIt != CacheMap.end()) 5649e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return CacheIt->second; 5659e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5669e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // always generate code immediately before the instruction being 5679e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // processed, so that the generated code dominates the same BBs 5689e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Instruction *PrevInsertPoint = Builder.GetInsertPoint(); 5699e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (Instruction *I = dyn_cast<Instruction>(V)) 5709e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Builder.SetInsertPoint(I); 5719e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5729e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // record the pointers that were handled in this run, so that they can be 5739e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // cleaned later if something fails 5749e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SeenVals.insert(V); 5759e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5769e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // now compute the size and offset 5779e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizeOffsetEvalType Result; 5789e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { 5799e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Result = visitGEPOperator(*GEP); 5809e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } else if (Instruction *I = dyn_cast<Instruction>(V)) { 5819e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Result = visit(*I); 5829e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } else if (isa<Argument>(V) || 5839e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes (isa<ConstantExpr>(V) && 5849e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes cast<ConstantExpr>(V)->getOpcode() == Instruction::IntToPtr) || 5859e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes isa<GlobalVariable>(V)) { 5869e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // ignore values where we cannot do more than what ObjectSizeVisitor can 5879e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Result = unknown(); 5889e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } else { 5899e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes DEBUG(dbgs() << "ObjectSizeOffsetEvaluator::compute() unhandled value: " 5909e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes << *V << '\n'); 5919e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Result = unknown(); 5929e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } 5939e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5949e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (PrevInsertPoint) 5959e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Builder.SetInsertPoint(PrevInsertPoint); 5969e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5979e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // Don't reuse CacheIt since it may be invalid at this point. 5989e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes CacheMap[V] = Result; 5999e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return Result; 6009e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 6019e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6029e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetEvalType ObjectSizeOffsetEvaluator::visitAllocaInst(AllocaInst &I) { 6039e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!I.getAllocatedType()->isSized()) 6049e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 6059e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6069e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // must be a VLA 6079e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes assert(I.isArrayAllocation()); 6089e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Value *ArraySize = I.getArraySize(); 6099e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Value *Size = ConstantInt::get(ArraySize->getType(), 6109e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes TD->getTypeAllocSize(I.getAllocatedType())); 6119e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Size = Builder.CreateMul(Size, ArraySize); 6129e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(Size, Zero); 6139e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 6149e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6159e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetEvalType ObjectSizeOffsetEvaluator::visitCallSite(CallSite CS) { 6169e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes const AllocFnsTy *FnData = getAllocationData(CS.getInstruction(), AnyAlloc); 6179e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!FnData) 6189e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 6199e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6209e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // handle strdup-like functions separately 6219e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (FnData->AllocTy == StrDupLike) { 6229e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // TODO 6239e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 6249e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } 6259e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 626034dd6c6a118cf78ebfa6bf3496cd5b0df578a9eNuno Lopes Value *FirstArg = CS.getArgument(FnData->FstParam); 627034dd6c6a118cf78ebfa6bf3496cd5b0df578a9eNuno Lopes FirstArg = Builder.CreateZExt(FirstArg, IntTy); 628ef22f04bad6f5037fd4cc4d144e0c418f6cb2edcNuno Lopes if (FnData->SndParam < 0) 6299e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(FirstArg, Zero); 6309e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6319e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Value *SecondArg = CS.getArgument(FnData->SndParam); 632034dd6c6a118cf78ebfa6bf3496cd5b0df578a9eNuno Lopes SecondArg = Builder.CreateZExt(SecondArg, IntTy); 6339e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Value *Size = Builder.CreateMul(FirstArg, SecondArg); 6349e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(Size, Zero); 6359e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6369e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // TODO: handle more standard functions (+ wchar cousins): 6379e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // - strdup / strndup 6389e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // - strcpy / strncpy 6399e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // - strcat / strncat 6409e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // - memcpy / memmove 6419e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // - strcat / strncat 6429e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // - memset 6439e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 6449e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6459e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetEvalType 64641a3f251346681e21171879dce409b2e6a3ba750Nuno LopesObjectSizeOffsetEvaluator::visitExtractElementInst(ExtractElementInst&) { 64741a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes return unknown(); 64841a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes} 64941a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes 65041a3f251346681e21171879dce409b2e6a3ba750Nuno LopesSizeOffsetEvalType 65141a3f251346681e21171879dce409b2e6a3ba750Nuno LopesObjectSizeOffsetEvaluator::visitExtractValueInst(ExtractValueInst&) { 65241a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes return unknown(); 65341a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes} 65441a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes 65541a3f251346681e21171879dce409b2e6a3ba750Nuno LopesSizeOffsetEvalType 6569e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesObjectSizeOffsetEvaluator::visitGEPOperator(GEPOperator &GEP) { 6579e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizeOffsetEvalType PtrData = compute_(GEP.getPointerOperand()); 6589e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!bothKnown(PtrData)) 6599e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 6609e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 661c606c3ff911eddcbf8bab95e67c7d8c1f69a493eNuno Lopes Value *Offset = EmitGEPOffset(&Builder, *TD, &GEP, /*NoAssumptions=*/true); 6629e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Offset = Builder.CreateAdd(PtrData.second, Offset); 6639e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(PtrData.first, Offset); 6649e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 6659e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6669e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetEvalType ObjectSizeOffsetEvaluator::visitIntToPtrInst(IntToPtrInst&) { 6679e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // clueless 6689e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 6699e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 6709e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6719e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetEvalType ObjectSizeOffsetEvaluator::visitLoadInst(LoadInst&) { 6729e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 6739e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 6749e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6759e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetEvalType ObjectSizeOffsetEvaluator::visitPHINode(PHINode &PHI) { 6769e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // create 2 PHIs: one for size and another for offset 6779e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes PHINode *SizePHI = Builder.CreatePHI(IntTy, PHI.getNumIncomingValues()); 6789e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes PHINode *OffsetPHI = Builder.CreatePHI(IntTy, PHI.getNumIncomingValues()); 6799e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6809e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // insert right away in the cache to handle recursive PHIs 6819e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes CacheMap[&PHI] = std::make_pair(SizePHI, OffsetPHI); 6829e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6839e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // compute offset/size for each PHI incoming pointer 6849e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes for (unsigned i = 0, e = PHI.getNumIncomingValues(); i != e; ++i) { 6859e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Builder.SetInsertPoint(PHI.getIncomingBlock(i)->getFirstInsertionPt()); 6869e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizeOffsetEvalType EdgeData = compute_(PHI.getIncomingValue(i)); 6879e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6889e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!bothKnown(EdgeData)) { 6899e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes OffsetPHI->replaceAllUsesWith(UndefValue::get(IntTy)); 6909e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes OffsetPHI->eraseFromParent(); 6919e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizePHI->replaceAllUsesWith(UndefValue::get(IntTy)); 6929e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizePHI->eraseFromParent(); 6939e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 6949e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } 6959e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizePHI->addIncoming(EdgeData.first, PHI.getIncomingBlock(i)); 6969e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes OffsetPHI->addIncoming(EdgeData.second, PHI.getIncomingBlock(i)); 6979e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } 6980dff532fce434c3e9fdf9695aed8efeb5f752ed5Nuno Lopes 6990dff532fce434c3e9fdf9695aed8efeb5f752ed5Nuno Lopes Value *Size = SizePHI, *Offset = OffsetPHI, *Tmp; 7000dff532fce434c3e9fdf9695aed8efeb5f752ed5Nuno Lopes if ((Tmp = SizePHI->hasConstantValue())) { 7010dff532fce434c3e9fdf9695aed8efeb5f752ed5Nuno Lopes Size = Tmp; 7020dff532fce434c3e9fdf9695aed8efeb5f752ed5Nuno Lopes SizePHI->replaceAllUsesWith(Size); 7030dff532fce434c3e9fdf9695aed8efeb5f752ed5Nuno Lopes SizePHI->eraseFromParent(); 7040dff532fce434c3e9fdf9695aed8efeb5f752ed5Nuno Lopes } 7050dff532fce434c3e9fdf9695aed8efeb5f752ed5Nuno Lopes if ((Tmp = OffsetPHI->hasConstantValue())) { 7060dff532fce434c3e9fdf9695aed8efeb5f752ed5Nuno Lopes Offset = Tmp; 7070dff532fce434c3e9fdf9695aed8efeb5f752ed5Nuno Lopes OffsetPHI->replaceAllUsesWith(Offset); 7080dff532fce434c3e9fdf9695aed8efeb5f752ed5Nuno Lopes OffsetPHI->eraseFromParent(); 7090dff532fce434c3e9fdf9695aed8efeb5f752ed5Nuno Lopes } 7100dff532fce434c3e9fdf9695aed8efeb5f752ed5Nuno Lopes return std::make_pair(Size, Offset); 7119e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 7129e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 7139e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetEvalType ObjectSizeOffsetEvaluator::visitSelectInst(SelectInst &I) { 7149e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizeOffsetEvalType TrueSide = compute_(I.getTrueValue()); 7159e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizeOffsetEvalType FalseSide = compute_(I.getFalseValue()); 7169e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 7179e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!bothKnown(TrueSide) || !bothKnown(FalseSide)) 7189e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 7199e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (TrueSide == FalseSide) 7209e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return TrueSide; 7219e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 7229e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Value *Size = Builder.CreateSelect(I.getCondition(), TrueSide.first, 7239e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes FalseSide.first); 7249e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Value *Offset = Builder.CreateSelect(I.getCondition(), TrueSide.second, 7259e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes FalseSide.second); 7269e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(Size, Offset); 7279e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 7289e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 7299e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetEvalType ObjectSizeOffsetEvaluator::visitInstruction(Instruction &I) { 7309e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes DEBUG(dbgs() << "ObjectSizeOffsetEvaluator unknown instruction:" << I <<'\n'); 7319e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 7329e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 733