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 119333ffb6db95e8ec2e34d2013c4fee47cecc8e91Michael Ilseman// or free memory. 12fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng// 13fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng//===----------------------------------------------------------------------===// 14fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 159e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes#define DEBUG_TYPE "memory-builtins" 16f006b183e2d2bebcf6968d1dd7350397c95b0325Victor Hernandez#include "llvm/Analysis/MemoryBuiltins.h" 17d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/STLExtras.h" 18d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 19d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/ValueTracking.h" 200b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DataLayout.h" 210b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/GlobalVariable.h" 220b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 230b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Intrinsics.h" 240b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Metadata.h" 250b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Module.h" 269e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes#include "llvm/Support/Debug.h" 279e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes#include "llvm/Support/MathExtras.h" 289e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes#include "llvm/Support/raw_ostream.h" 298e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer#include "llvm/Target/TargetLibraryInfo.h" 309e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes#include "llvm/Transforms/Utils/Local.h" 31fabcb9127f278a77b8aae5673be1115390c55050Evan Chengusing namespace llvm; 32fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 339e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopesenum AllocType { 349e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes MallocLike = 1<<0, // allocates 359e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes CallocLike = 1<<1, // allocates + bzero 369e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes ReallocLike = 1<<2, // reallocates 379e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes StrDupLike = 1<<3, 389e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes AllocLike = MallocLike | CallocLike | StrDupLike, 399e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes AnyAlloc = MallocLike | CallocLike | ReallocLike | StrDupLike 409e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes}; 419e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 429e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopesstruct AllocFnsTy { 438e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer LibFunc::Func Func; 449e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes AllocType AllocTy; 459e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes unsigned char NumParams; 469e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // First and Second size parameters (or -1 if unused) 47ef22f04bad6f5037fd4cc4d144e0c418f6cb2edcNuno Lopes signed char FstParam, SndParam; 489e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes}; 499e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5041a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes// FIXME: certain users need more information. E.g., SimplifyLibCalls needs to 5141a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes// know which functions are nounwind, noalias, nocapture parameters, etc. 529e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopesstatic const AllocFnsTy AllocationFnData[] = { 538e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer {LibFunc::malloc, MallocLike, 1, 0, -1}, 548e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer {LibFunc::valloc, MallocLike, 1, 0, -1}, 558e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer {LibFunc::Znwj, MallocLike, 1, 0, -1}, // new(unsigned int) 568e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer {LibFunc::ZnwjRKSt9nothrow_t, MallocLike, 2, 0, -1}, // new(unsigned int, nothrow) 578e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer {LibFunc::Znwm, MallocLike, 1, 0, -1}, // new(unsigned long) 588e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer {LibFunc::ZnwmRKSt9nothrow_t, MallocLike, 2, 0, -1}, // new(unsigned long, nothrow) 598e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer {LibFunc::Znaj, MallocLike, 1, 0, -1}, // new[](unsigned int) 608e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer {LibFunc::ZnajRKSt9nothrow_t, MallocLike, 2, 0, -1}, // new[](unsigned int, nothrow) 618e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer {LibFunc::Znam, MallocLike, 1, 0, -1}, // new[](unsigned long) 628e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer {LibFunc::ZnamRKSt9nothrow_t, MallocLike, 2, 0, -1}, // new[](unsigned long, nothrow) 638e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer {LibFunc::posix_memalign, MallocLike, 3, 2, -1}, 648e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer {LibFunc::calloc, CallocLike, 2, 0, 1}, 658e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer {LibFunc::realloc, ReallocLike, 2, 1, -1}, 668e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer {LibFunc::reallocf, ReallocLike, 2, 1, -1}, 678e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer {LibFunc::strdup, StrDupLike, 1, -1, -1}, 688e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer {LibFunc::strndup, StrDupLike, 2, 1, -1} 699e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes}; 709e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 719e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 729e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopesstatic Function *getCalledFunction(const Value *V, bool LookThroughBitCast) { 739e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (LookThroughBitCast) 749e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes V = V->stripPointerCasts(); 752b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes 76d845c34170be5ece8aee3a1097849aa8ce9259cbNuno Lopes CallSite CS(const_cast<Value*>(V)); 77d845c34170be5ece8aee3a1097849aa8ce9259cbNuno Lopes if (!CS.getInstruction()) 789e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return 0; 79fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 802b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes Function *Callee = CS.getCalledFunction(); 819e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!Callee || !Callee->isDeclaration()) 829e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return 0; 839e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return Callee; 84fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng} 85fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 869e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes/// \brief Returns the allocation data for the given value if it is a call to a 879e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes/// known allocation function, and NULL otherwise. 889e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopesstatic const AllocFnsTy *getAllocationData(const Value *V, AllocType AllocTy, 898e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer const TargetLibraryInfo *TLI, 909e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes bool LookThroughBitCast = false) { 91cacf97107972d0c9d29d14b8d67183c998d17d94Michael Ilseman // Skip intrinsics 92cacf97107972d0c9d29d14b8d67183c998d17d94Michael Ilseman if (isa<IntrinsicInst>(V)) 93cacf97107972d0c9d29d14b8d67183c998d17d94Michael Ilseman return 0; 94cacf97107972d0c9d29d14b8d67183c998d17d94Michael Ilseman 959e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Function *Callee = getCalledFunction(V, LookThroughBitCast); 969e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!Callee) 979e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return 0; 98fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 998e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer // Make sure that the function is available. 1008e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer StringRef FnName = Callee->getName(); 1018e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer LibFunc::Func TLIFn; 1028e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer if (!TLI || !TLI->getLibFunc(FnName, TLIFn) || !TLI->has(TLIFn)) 1038e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer return 0; 1048e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer 1059e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes unsigned i = 0; 1069e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes bool found = false; 1079e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes for ( ; i < array_lengthof(AllocationFnData); ++i) { 1088e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer if (AllocationFnData[i].Func == TLIFn) { 1099e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes found = true; 1109e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes break; 1119e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } 1129e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } 1139e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!found) 1149e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return 0; 115fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 1169e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes const AllocFnsTy *FnData = &AllocationFnData[i]; 1179e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if ((FnData->AllocTy & AllocTy) == 0) 1189e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return 0; 1199e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 1209e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // Check function prototype. 121ef22f04bad6f5037fd4cc4d144e0c418f6cb2edcNuno Lopes int FstParam = FnData->FstParam; 122ef22f04bad6f5037fd4cc4d144e0c418f6cb2edcNuno Lopes int SndParam = FnData->SndParam; 123db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner FunctionType *FTy = Callee->getFunctionType(); 1249e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 1259e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (FTy->getReturnType() == Type::getInt8PtrTy(FTy->getContext()) && 1269e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes FTy->getNumParams() == FnData->NumParams && 127ef22f04bad6f5037fd4cc4d144e0c418f6cb2edcNuno Lopes (FstParam < 0 || 1289e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes (FTy->getParamType(FstParam)->isIntegerTy(32) || 1299e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes FTy->getParamType(FstParam)->isIntegerTy(64))) && 130ef22f04bad6f5037fd4cc4d144e0c418f6cb2edcNuno Lopes (SndParam < 0 || 1319e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes FTy->getParamType(SndParam)->isIntegerTy(32) || 1329e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes FTy->getParamType(SndParam)->isIntegerTy(64))) 1339e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return FnData; 1349e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return 0; 135fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng} 136fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 1379e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopesstatic bool hasNoAliasAttr(const Value *V, bool LookThroughBitCast) { 138e8742d084c54e9cd230fa03d368f0fedac2106cbNuno Lopes ImmutableCallSite CS(LookThroughBitCast ? V->stripPointerCasts() : V); 139034b94b17006f51722886b0f2283fb6fb19aca1fBill Wendling return CS && CS.hasFnAttr(Attribute::NoAlias); 140fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng} 141fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 1429e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 1432b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes/// \brief Tests if a value is a call or invoke to a library function that 1442b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes/// allocates or reallocates memory (either malloc, calloc, realloc, or strdup 1452b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes/// like). 1468e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramerbool llvm::isAllocationFn(const Value *V, const TargetLibraryInfo *TLI, 1478e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer bool LookThroughBitCast) { 1488e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer return getAllocationData(V, AnyAlloc, TLI, LookThroughBitCast); 149fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng} 150fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 1512b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes/// \brief Tests if a value is a call or invoke to a function that returns a 15241a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes/// NoAlias pointer (including malloc/calloc/realloc/strdup-like functions). 1538e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramerbool llvm::isNoAliasFn(const Value *V, const TargetLibraryInfo *TLI, 1548e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer bool LookThroughBitCast) { 15541a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes // it's safe to consider realloc as noalias since accessing the original 15641a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes // pointer is undefined behavior 1578e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer return isAllocationFn(V, TLI, LookThroughBitCast) || 1589e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes hasNoAliasAttr(V, LookThroughBitCast); 159fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng} 160fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 1612b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes/// \brief Tests if a value is a call or invoke to a library function that 1622b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes/// allocates uninitialized memory (such as malloc). 1638e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramerbool llvm::isMallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, 1648e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer bool LookThroughBitCast) { 1658e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer return getAllocationData(V, MallocLike, TLI, LookThroughBitCast); 1669e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 1679e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 1682b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes/// \brief Tests if a value is a call or invoke to a library function that 1692b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes/// allocates zero-filled memory (such as calloc). 1708e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramerbool llvm::isCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, 1718e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer bool LookThroughBitCast) { 1728e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer return getAllocationData(V, CallocLike, TLI, LookThroughBitCast); 1739e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 1749e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 1752b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes/// \brief Tests if a value is a call or invoke to a library function that 1762b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes/// allocates memory (either malloc, calloc, or strdup like). 1778e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramerbool llvm::isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI, 1788e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer bool LookThroughBitCast) { 1798e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer return getAllocationData(V, AllocLike, TLI, LookThroughBitCast); 1809e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 1819e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 1822b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes/// \brief Tests if a value is a call or invoke to a library function that 1832b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes/// reallocates memory (such as realloc). 1848e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramerbool llvm::isReallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, 1858e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer bool LookThroughBitCast) { 1868e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer return getAllocationData(V, ReallocLike, TLI, LookThroughBitCast); 1879e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 1889e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 1899e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes/// extractMallocCall - Returns the corresponding CallInst if the instruction 1909e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes/// is a malloc call. Since CallInst::CreateMalloc() only creates calls, we 1919e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes/// ignore InvokeInst here. 1928e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramerconst CallInst *llvm::extractMallocCall(const Value *I, 1938e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer const TargetLibraryInfo *TLI) { 1948e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer return isMallocLikeFn(I, TLI) ? dyn_cast<CallInst>(I) : 0; 195fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng} 196fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 1973574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmowstatic Value *computeArraySize(const CallInst *CI, const DataLayout *TD, 1988e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer const TargetLibraryInfo *TLI, 1998e345a1c418608c49abb7c51a090bbb36f1273bcVictor Hernandez bool LookThroughSExt = false) { 200fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng if (!CI) 201a9cd5164c404905a8109da5bfedea9d68960990dJakub Staszak return 0; 202fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 2039d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez // The size of the malloc's result type must be known to determine array size. 2048e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer Type *T = getMallocAllocatedType(CI, TLI); 2059d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez if (!T || !T->isSized() || !TD) 206a9cd5164c404905a8109da5bfedea9d68960990dJakub Staszak return 0; 207fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 2088e345a1c418608c49abb7c51a090bbb36f1273bcVictor Hernandez unsigned ElementSize = TD->getTypeAllocSize(T); 209db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner if (StructType *ST = dyn_cast<StructType>(T)) 2108e345a1c418608c49abb7c51a090bbb36f1273bcVictor Hernandez ElementSize = TD->getStructLayout(ST)->getSizeInBytes(); 2119d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez 212e3401c4fae95bc69dada2a3f9080d9f15349af61Gabor Greif // If malloc call's arg can be determined to be a multiple of ElementSize, 2138e345a1c418608c49abb7c51a090bbb36f1273bcVictor Hernandez // return the multiple. Otherwise, return NULL. 214e3401c4fae95bc69dada2a3f9080d9f15349af61Gabor Greif Value *MallocArg = CI->getArgOperand(0); 215a9cd5164c404905a8109da5bfedea9d68960990dJakub Staszak Value *Multiple = 0; 2168e345a1c418608c49abb7c51a090bbb36f1273bcVictor Hernandez if (ComputeMultiple(MallocArg, ElementSize, Multiple, 2173dbb9e64d6e9d1e8bf16f75ebe4fe59ffdf93dd3Dan Gohman LookThroughSExt)) 2188e345a1c418608c49abb7c51a090bbb36f1273bcVictor Hernandez return Multiple; 21988d9839d07a6b5a03484d664913de0f2b33d3bffVictor Hernandez 220a9cd5164c404905a8109da5bfedea9d68960990dJakub Staszak return 0; 221fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng} 222fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 2239333ffb6db95e8ec2e34d2013c4fee47cecc8e91Michael Ilseman/// isArrayMalloc - Returns the corresponding CallInst if the instruction 22490f48e7c91a8faa875ba889ca66b137ffd46e34aVictor Hernandez/// is a call to malloc whose array size can be determined and the array size 22590f48e7c91a8faa875ba889ca66b137ffd46e34aVictor Hernandez/// is not constant 1. Otherwise, return NULL. 2268e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramerconst CallInst *llvm::isArrayMalloc(const Value *I, 2273574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow const DataLayout *TD, 2288e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer const TargetLibraryInfo *TLI) { 2298e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer const CallInst *CI = extractMallocCall(I, TLI); 2308e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer Value *ArraySize = computeArraySize(CI, TD, TLI); 23190f48e7c91a8faa875ba889ca66b137ffd46e34aVictor Hernandez 232b1b6c170819120e535ef706f58041bb6caebe35dJakub Staszak if (ConstantInt *ConstSize = dyn_cast_or_null<ConstantInt>(ArraySize)) 233b1b6c170819120e535ef706f58041bb6caebe35dJakub Staszak if (ConstSize->isOne()) 234b1b6c170819120e535ef706f58041bb6caebe35dJakub Staszak return CI; 23590f48e7c91a8faa875ba889ca66b137ffd46e34aVictor Hernandez 23690f48e7c91a8faa875ba889ca66b137ffd46e34aVictor Hernandez // CI is a non-array malloc or we can't figure out that it is an array malloc. 237a9cd5164c404905a8109da5bfedea9d68960990dJakub Staszak return 0; 238fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng} 239fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 240fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng/// getMallocType - Returns the PointerType resulting from the malloc call. 2419d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez/// The PointerType depends on the number of bitcast uses of the malloc call: 2429d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez/// 0: PointerType is the calls' return type. 2439d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez/// 1: PointerType is the bitcast's result type. 2449d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez/// >1: Unique PointerType cannot be determined, return NULL. 2458e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin KramerPointerType *llvm::getMallocType(const CallInst *CI, 2468e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer const TargetLibraryInfo *TLI) { 2478e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer assert(isMallocLikeFn(CI, TLI) && "getMallocType and not malloc call"); 2489333ffb6db95e8ec2e34d2013c4fee47cecc8e91Michael Ilseman 249a9cd5164c404905a8109da5bfedea9d68960990dJakub Staszak PointerType *MallocType = 0; 2509d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez unsigned NumOfBitCastUses = 0; 2519d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez 25288d9839d07a6b5a03484d664913de0f2b33d3bffVictor Hernandez // Determine if CallInst has a bitcast use. 25360ad781c61815ca5b8dc2a45a102e1c8af65992fGabor Greif for (Value::const_use_iterator UI = CI->use_begin(), E = CI->use_end(); 25488d9839d07a6b5a03484d664913de0f2b33d3bffVictor Hernandez UI != E; ) 2559d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez if (const BitCastInst *BCI = dyn_cast<BitCastInst>(*UI++)) { 2569d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez MallocType = cast<PointerType>(BCI->getDestTy()); 2579d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez NumOfBitCastUses++; 2589d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez } 25988d9839d07a6b5a03484d664913de0f2b33d3bffVictor Hernandez 2609d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez // Malloc call has 1 bitcast use, so type is the bitcast's destination type. 2619d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez if (NumOfBitCastUses == 1) 2629d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez return MallocType; 263fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 26460cfc03379c1ec3fac3dc807f5e93842c0b95f33Victor Hernandez // Malloc call was not bitcast, so type is the malloc function's return type. 2659d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez if (NumOfBitCastUses == 0) 26688d9839d07a6b5a03484d664913de0f2b33d3bffVictor Hernandez return cast<PointerType>(CI->getType()); 267fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 26888d9839d07a6b5a03484d664913de0f2b33d3bffVictor Hernandez // Type could not be determined. 269a9cd5164c404905a8109da5bfedea9d68960990dJakub Staszak return 0; 270fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng} 271fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 2729d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez/// getMallocAllocatedType - Returns the Type allocated by malloc call. 2739d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez/// The Type depends on the number of bitcast uses of the malloc call: 2749d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez/// 0: PointerType is the malloc calls' return type. 2759d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez/// 1: PointerType is the bitcast's result type. 2769d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez/// >1: Unique PointerType cannot be determined, return NULL. 2778e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin KramerType *llvm::getMallocAllocatedType(const CallInst *CI, 2788e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer const TargetLibraryInfo *TLI) { 2798e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer PointerType *PT = getMallocType(CI, TLI); 280a9cd5164c404905a8109da5bfedea9d68960990dJakub Staszak return PT ? PT->getElementType() : 0; 281fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng} 282fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 2839333ffb6db95e8ec2e34d2013c4fee47cecc8e91Michael Ilseman/// getMallocArraySize - Returns the array size of a malloc call. If the 28490f48e7c91a8faa875ba889ca66b137ffd46e34aVictor Hernandez/// argument passed to malloc is a multiple of the size of the malloced type, 28590f48e7c91a8faa875ba889ca66b137ffd46e34aVictor Hernandez/// then return that multiple. For non-array mallocs, the multiple is 28690f48e7c91a8faa875ba889ca66b137ffd46e34aVictor Hernandez/// constant 1. Otherwise, return NULL for mallocs whose array size cannot be 2872491ce03535cf8ec171570d2e28df63e4db3dd6bVictor Hernandez/// determined. 2883574eca1b02600bac4e625297f4ecf745f4c4f32Micah VillmowValue *llvm::getMallocArraySize(CallInst *CI, const DataLayout *TD, 2898e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer const TargetLibraryInfo *TLI, 2908e345a1c418608c49abb7c51a090bbb36f1273bcVictor Hernandez bool LookThroughSExt) { 2918e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer assert(isMallocLikeFn(CI, TLI) && "getMallocArraySize and not malloc call"); 2928e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer return computeArraySize(CI, TD, TLI, LookThroughSExt); 293fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng} 29466284e063a1e46500acae48bdc0e4a00652021d1Victor Hernandez 295252ef566e8734b6bcf46434d0a7954c9eda0bd96Nuno Lopes 296252ef566e8734b6bcf46434d0a7954c9eda0bd96Nuno Lopes/// extractCallocCall - Returns the corresponding CallInst if the instruction 297252ef566e8734b6bcf46434d0a7954c9eda0bd96Nuno Lopes/// is a calloc call. 2988e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramerconst CallInst *llvm::extractCallocCall(const Value *I, 2998e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer const TargetLibraryInfo *TLI) { 3008e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer return isCallocLikeFn(I, TLI) ? cast<CallInst>(I) : 0; 301252ef566e8734b6bcf46434d0a7954c9eda0bd96Nuno Lopes} 302252ef566e8734b6bcf46434d0a7954c9eda0bd96Nuno Lopes 303046e78ce55a7c3d82b7b6758d2d77f2d99f970bfVictor Hernandez 30402680f946b8dcbeff3b8d7236030678551b15a6cGabor Greif/// isFreeCall - Returns non-null if the value is a call to the builtin free() 3058e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramerconst CallInst *llvm::isFreeCall(const Value *I, const TargetLibraryInfo *TLI) { 30666284e063a1e46500acae48bdc0e4a00652021d1Victor Hernandez const CallInst *CI = dyn_cast<CallInst>(I); 307cacf97107972d0c9d29d14b8d67183c998d17d94Michael Ilseman if (!CI || isa<IntrinsicInst>(CI)) 30802680f946b8dcbeff3b8d7236030678551b15a6cGabor Greif return 0; 3093ad70d5d61f3f86fb5bc167e157680fc107a1173Victor Hernandez Function *Callee = CI->getCalledFunction(); 31042e72ca3d00dbe073fbb39e181caa7f0c4c171b7Nick Lewycky if (Callee == 0 || !Callee->isDeclaration()) 31142e72ca3d00dbe073fbb39e181caa7f0c4c171b7Nick Lewycky return 0; 31242e72ca3d00dbe073fbb39e181caa7f0c4c171b7Nick Lewycky 3138e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer StringRef FnName = Callee->getName(); 3148e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer LibFunc::Func TLIFn; 3158e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer if (!TLI || !TLI->getLibFunc(FnName, TLIFn) || !TLI->has(TLIFn)) 3168e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer return 0; 3178e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer 3188e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer if (TLIFn != LibFunc::free && 3198e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer TLIFn != LibFunc::ZdlPv && // operator delete(void*) 3208e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer TLIFn != LibFunc::ZdaPv) // operator delete[](void*) 32102680f946b8dcbeff3b8d7236030678551b15a6cGabor Greif return 0; 32266284e063a1e46500acae48bdc0e4a00652021d1Victor Hernandez 32366284e063a1e46500acae48bdc0e4a00652021d1Victor Hernandez // Check free prototype. 3249333ffb6db95e8ec2e34d2013c4fee47cecc8e91Michael Ilseman // FIXME: workaround for PR5130, this will be obsolete when a nobuiltin 32566284e063a1e46500acae48bdc0e4a00652021d1Victor Hernandez // attribute will exist. 326db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner FunctionType *FTy = Callee->getFunctionType(); 3273ad70d5d61f3f86fb5bc167e157680fc107a1173Victor Hernandez if (!FTy->getReturnType()->isVoidTy()) 32802680f946b8dcbeff3b8d7236030678551b15a6cGabor Greif return 0; 32966284e063a1e46500acae48bdc0e4a00652021d1Victor Hernandez if (FTy->getNumParams() != 1) 33002680f946b8dcbeff3b8d7236030678551b15a6cGabor Greif return 0; 331ebb2189904564c7c6193e7f23904f1ced7975480Chris Lattner if (FTy->getParamType(0) != Type::getInt8PtrTy(Callee->getContext())) 33202680f946b8dcbeff3b8d7236030678551b15a6cGabor Greif return 0; 33366284e063a1e46500acae48bdc0e4a00652021d1Victor Hernandez 33402680f946b8dcbeff3b8d7236030678551b15a6cGabor Greif return CI; 33566284e063a1e46500acae48bdc0e4a00652021d1Victor Hernandez} 3369e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3379e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3389e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3399e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes//===----------------------------------------------------------------------===// 3409e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes// Utility functions to compute size of objects. 3419e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes// 3429e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3439e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3449e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes/// \brief Compute the size of the object pointed by Ptr. Returns true and the 3459e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes/// object size in Size if successful, and false otherwise. 3469e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes/// If RoundToAlign is true, then Size is rounded up to the aligment of allocas, 3479e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes/// byval arguments, and global variables. 3483574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmowbool llvm::getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout *TD, 3498e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer const TargetLibraryInfo *TLI, bool RoundToAlign) { 3509e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!TD) 3519e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return false; 3529e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3538e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer ObjectSizeOffsetVisitor Visitor(TD, TLI, Ptr->getContext(), RoundToAlign); 3549e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizeOffsetType Data = Visitor.compute(const_cast<Value*>(Ptr)); 3559e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!Visitor.bothKnown(Data)) 3569e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return false; 3579e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3589e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes APInt ObjSize = Data.first, Offset = Data.second; 3599e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // check for overflow 3609e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (Offset.slt(0) || ObjSize.ult(Offset)) 3619e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Size = 0; 3629e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes else 3639e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Size = (ObjSize - Offset).getZExtValue(); 3649e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return true; 3659e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 3669e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3672bc689c8461dfbaa4ca9a9cc4ae5bc59cb007329Nuno Lopes/// \brief Compute the size of the underlying object pointed by Ptr. Returns 3682bc689c8461dfbaa4ca9a9cc4ae5bc59cb007329Nuno Lopes/// true and the object size in Size if successful, and false otherwise. 3692bc689c8461dfbaa4ca9a9cc4ae5bc59cb007329Nuno Lopes/// If RoundToAlign is true, then Size is rounded up to the aligment of allocas, 3702bc689c8461dfbaa4ca9a9cc4ae5bc59cb007329Nuno Lopes/// byval arguments, and global variables. 3712bc689c8461dfbaa4ca9a9cc4ae5bc59cb007329Nuno Lopesbool llvm::getUnderlyingObjectSize(const Value *Ptr, uint64_t &Size, 3722bc689c8461dfbaa4ca9a9cc4ae5bc59cb007329Nuno Lopes const DataLayout *TD, 3732bc689c8461dfbaa4ca9a9cc4ae5bc59cb007329Nuno Lopes const TargetLibraryInfo *TLI, 3742bc689c8461dfbaa4ca9a9cc4ae5bc59cb007329Nuno Lopes bool RoundToAlign) { 3752bc689c8461dfbaa4ca9a9cc4ae5bc59cb007329Nuno Lopes if (!TD) 3762bc689c8461dfbaa4ca9a9cc4ae5bc59cb007329Nuno Lopes return false; 3772bc689c8461dfbaa4ca9a9cc4ae5bc59cb007329Nuno Lopes 3782bc689c8461dfbaa4ca9a9cc4ae5bc59cb007329Nuno Lopes ObjectSizeOffsetVisitor Visitor(TD, TLI, Ptr->getContext(), RoundToAlign); 3792bc689c8461dfbaa4ca9a9cc4ae5bc59cb007329Nuno Lopes SizeOffsetType Data = Visitor.compute(const_cast<Value*>(Ptr)); 3802bc689c8461dfbaa4ca9a9cc4ae5bc59cb007329Nuno Lopes if (!Visitor.knownSize(Data)) 3812bc689c8461dfbaa4ca9a9cc4ae5bc59cb007329Nuno Lopes return false; 3822bc689c8461dfbaa4ca9a9cc4ae5bc59cb007329Nuno Lopes 3832bc689c8461dfbaa4ca9a9cc4ae5bc59cb007329Nuno Lopes Size = Data.first.getZExtValue(); 3842bc689c8461dfbaa4ca9a9cc4ae5bc59cb007329Nuno Lopes return true; 3852bc689c8461dfbaa4ca9a9cc4ae5bc59cb007329Nuno Lopes} 3862bc689c8461dfbaa4ca9a9cc4ae5bc59cb007329Nuno Lopes 3879e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3889e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSTATISTIC(ObjectVisitorArgument, 3899e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes "Number of arguments with unsolved size and offset"); 3909e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSTATISTIC(ObjectVisitorLoad, 3919e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes "Number of load instructions with unsolved size and offset"); 3929e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3939e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3949e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesAPInt ObjectSizeOffsetVisitor::align(APInt Size, uint64_t Align) { 3959e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (RoundToAlign && Align) 3969e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return APInt(IntTyBits, RoundUpToAlignment(Size.getZExtValue(), Align)); 3979e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return Size; 3989e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 3999e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 4003574eca1b02600bac4e625297f4ecf745f4c4f32Micah VillmowObjectSizeOffsetVisitor::ObjectSizeOffsetVisitor(const DataLayout *TD, 4018e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer const TargetLibraryInfo *TLI, 4029e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes LLVMContext &Context, 403ece6c6bb6329748b92403c06ac87f45c43485911Chandler Carruth bool RoundToAlign) 4048e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer: TD(TD), TLI(TLI), RoundToAlign(RoundToAlign) { 405ece6c6bb6329748b92403c06ac87f45c43485911Chandler Carruth IntegerType *IntTy = TD->getIntPtrType(Context); 4069e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes IntTyBits = IntTy->getBitWidth(); 4079e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Zero = APInt::getNullValue(IntTyBits); 4089e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 4099e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 4109e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType ObjectSizeOffsetVisitor::compute(Value *V) { 4119e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes V = V->stripPointerCasts(); 4120a9ff4cab3a3fc1179c37855717a54ae44a5312eNuno Lopes 413b443a0aeac38e6fdce063224dfc746c269b0779dNuno Lopes if (isa<Instruction>(V) || isa<GEPOperator>(V)) { 414b443a0aeac38e6fdce063224dfc746c269b0779dNuno Lopes // Return cached value or insert unknown in cache if size of V was not 415b443a0aeac38e6fdce063224dfc746c269b0779dNuno Lopes // computed yet in order to avoid recursions in PHis. 416b443a0aeac38e6fdce063224dfc746c269b0779dNuno Lopes std::pair<CacheMapTy::iterator, bool> CacheVal = 417b443a0aeac38e6fdce063224dfc746c269b0779dNuno Lopes CacheMap.insert(std::make_pair(V, unknown())); 418b443a0aeac38e6fdce063224dfc746c269b0779dNuno Lopes if (!CacheVal.second) 419b443a0aeac38e6fdce063224dfc746c269b0779dNuno Lopes return CacheVal.first->second; 420b443a0aeac38e6fdce063224dfc746c269b0779dNuno Lopes 421b443a0aeac38e6fdce063224dfc746c269b0779dNuno Lopes SizeOffsetType Result; 422168843c0137ad67c24a3930244a9c5f60add320dBenjamin Kramer if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) 423b443a0aeac38e6fdce063224dfc746c269b0779dNuno Lopes Result = visitGEPOperator(*GEP); 424b443a0aeac38e6fdce063224dfc746c269b0779dNuno Lopes else 425b443a0aeac38e6fdce063224dfc746c269b0779dNuno Lopes Result = visit(cast<Instruction>(*V)); 426b443a0aeac38e6fdce063224dfc746c269b0779dNuno Lopes return CacheMap[V] = Result; 427168843c0137ad67c24a3930244a9c5f60add320dBenjamin Kramer } 428b443a0aeac38e6fdce063224dfc746c269b0779dNuno Lopes 4299e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (Argument *A = dyn_cast<Argument>(V)) 4309e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return visitArgument(*A); 4319e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (ConstantPointerNull *P = dyn_cast<ConstantPointerNull>(V)) 4329e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return visitConstantPointerNull(*P); 43341be2fb1f9e9b8f796effb81c2bee6cf397136cfNuno Lopes if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) 43441be2fb1f9e9b8f796effb81c2bee6cf397136cfNuno Lopes return visitGlobalAlias(*GA); 4359e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) 4369e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return visitGlobalVariable(*GV); 4379e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (UndefValue *UV = dyn_cast<UndefValue>(V)) 4389e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return visitUndefValue(*UV); 439168843c0137ad67c24a3930244a9c5f60add320dBenjamin Kramer if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) { 4409e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (CE->getOpcode() == Instruction::IntToPtr) 4419e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); // clueless 442168843c0137ad67c24a3930244a9c5f60add320dBenjamin Kramer } 4439e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 4449e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes DEBUG(dbgs() << "ObjectSizeOffsetVisitor::compute() unhandled value: " << *V 4459e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes << '\n'); 4469e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 4479e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 4489e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 4499e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType ObjectSizeOffsetVisitor::visitAllocaInst(AllocaInst &I) { 4509e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!I.getAllocatedType()->isSized()) 4519e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 4529e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 4539e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes APInt Size(IntTyBits, TD->getTypeAllocSize(I.getAllocatedType())); 4549e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!I.isArrayAllocation()) 4559e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(align(Size, I.getAlignment()), Zero); 4569e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 4579e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Value *ArraySize = I.getArraySize(); 4589e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (const ConstantInt *C = dyn_cast<ConstantInt>(ArraySize)) { 4599e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Size *= C->getValue().zextOrSelf(IntTyBits); 4609e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(align(Size, I.getAlignment()), Zero); 4619e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } 4629e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 4639e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 4649e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 4659e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType ObjectSizeOffsetVisitor::visitArgument(Argument &A) { 4669e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // no interprocedural analysis is done at the moment 4679e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!A.hasByValAttr()) { 4689e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes ++ObjectVisitorArgument; 4699e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 4709e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } 4719e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes PointerType *PT = cast<PointerType>(A.getType()); 4729e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes APInt Size(IntTyBits, TD->getTypeAllocSize(PT->getElementType())); 4739e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(align(Size, A.getParamAlignment()), Zero); 4749e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 4759e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 4769e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType ObjectSizeOffsetVisitor::visitCallSite(CallSite CS) { 4778e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer const AllocFnsTy *FnData = getAllocationData(CS.getInstruction(), AnyAlloc, 4788e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer TLI); 4799e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!FnData) 4809e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 4819e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 4829e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // handle strdup-like functions separately 4839e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (FnData->AllocTy == StrDupLike) { 4849827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes APInt Size(IntTyBits, GetStringLength(CS.getArgument(0))); 4859827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes if (!Size) 4869827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes return unknown(); 4879827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes 4889827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes // strndup limits strlen 4899827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes if (FnData->FstParam > 0) { 4909827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes ConstantInt *Arg= dyn_cast<ConstantInt>(CS.getArgument(FnData->FstParam)); 4919827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes if (!Arg) 4929827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes return unknown(); 4939827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes 4949827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes APInt MaxSize = Arg->getValue().zextOrSelf(IntTyBits); 4959827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes if (Size.ugt(MaxSize)) 4969827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes Size = MaxSize + 1; 4979827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes } 4989827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes return std::make_pair(Size, Zero); 4999e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } 5009e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5019e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes ConstantInt *Arg = dyn_cast<ConstantInt>(CS.getArgument(FnData->FstParam)); 5029e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!Arg) 5039e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 5049e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 505034dd6c6a118cf78ebfa6bf3496cd5b0df578a9eNuno Lopes APInt Size = Arg->getValue().zextOrSelf(IntTyBits); 5069e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // size determined by just 1 parameter 507ef22f04bad6f5037fd4cc4d144e0c418f6cb2edcNuno Lopes if (FnData->SndParam < 0) 5089e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(Size, Zero); 5099e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5109e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Arg = dyn_cast<ConstantInt>(CS.getArgument(FnData->SndParam)); 5119e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!Arg) 5129e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 5139e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 514034dd6c6a118cf78ebfa6bf3496cd5b0df578a9eNuno Lopes Size *= Arg->getValue().zextOrSelf(IntTyBits); 5159e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(Size, Zero); 5169e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5179e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // TODO: handle more standard functions (+ wchar cousins): 5186e699bf38dd862331532bd6f74ec491bdfad5db9Nuno Lopes // - strdup / strndup 5199e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // - strcpy / strncpy 5209e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // - strcat / strncat 5219e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // - memcpy / memmove 5226e699bf38dd862331532bd6f74ec491bdfad5db9Nuno Lopes // - strcat / strncat 5239e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // - memset 5249e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 5259e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5269e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType 5279e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesObjectSizeOffsetVisitor::visitConstantPointerNull(ConstantPointerNull&) { 5289e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(Zero, Zero); 5299e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 5309e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5319e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType 53241a3f251346681e21171879dce409b2e6a3ba750Nuno LopesObjectSizeOffsetVisitor::visitExtractElementInst(ExtractElementInst&) { 53341a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes return unknown(); 53441a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes} 53541a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes 53641a3f251346681e21171879dce409b2e6a3ba750Nuno LopesSizeOffsetType 5379e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesObjectSizeOffsetVisitor::visitExtractValueInst(ExtractValueInst&) { 5389e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // Easy cases were already folded by previous passes. 5399e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 5409e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 5419e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5429e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType ObjectSizeOffsetVisitor::visitGEPOperator(GEPOperator &GEP) { 5439e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizeOffsetType PtrData = compute(GEP.getPointerOperand()); 54498281a20503896349bd152e2dfe87435d3a6aadaNuno Lopes APInt Offset(IntTyBits, 0); 54598281a20503896349bd152e2dfe87435d3a6aadaNuno Lopes if (!bothKnown(PtrData) || !GEP.accumulateConstantOffset(*TD, Offset)) 5469e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 5479e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5489e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(PtrData.first, PtrData.second + Offset); 5499e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 5509e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 55141be2fb1f9e9b8f796effb81c2bee6cf397136cfNuno LopesSizeOffsetType ObjectSizeOffsetVisitor::visitGlobalAlias(GlobalAlias &GA) { 55241be2fb1f9e9b8f796effb81c2bee6cf397136cfNuno Lopes if (GA.mayBeOverridden()) 55341be2fb1f9e9b8f796effb81c2bee6cf397136cfNuno Lopes return unknown(); 55441be2fb1f9e9b8f796effb81c2bee6cf397136cfNuno Lopes return compute(GA.getAliasee()); 55541be2fb1f9e9b8f796effb81c2bee6cf397136cfNuno Lopes} 55641be2fb1f9e9b8f796effb81c2bee6cf397136cfNuno Lopes 5579e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType ObjectSizeOffsetVisitor::visitGlobalVariable(GlobalVariable &GV){ 5589e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!GV.hasDefinitiveInitializer()) 5599e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 5609e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5619e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes APInt Size(IntTyBits, TD->getTypeAllocSize(GV.getType()->getElementType())); 5629e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(align(Size, GV.getAlignment()), Zero); 5639e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 5649e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5659e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType ObjectSizeOffsetVisitor::visitIntToPtrInst(IntToPtrInst&) { 5669e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // clueless 5679e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 5689e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 5699e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5709e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType ObjectSizeOffsetVisitor::visitLoadInst(LoadInst&) { 5719e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes ++ObjectVisitorLoad; 5729e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 5739e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 5749e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 575b443a0aeac38e6fdce063224dfc746c269b0779dNuno LopesSizeOffsetType ObjectSizeOffsetVisitor::visitPHINode(PHINode &PHI) { 576b443a0aeac38e6fdce063224dfc746c269b0779dNuno Lopes if (PHI.getNumIncomingValues() == 0) 577b443a0aeac38e6fdce063224dfc746c269b0779dNuno Lopes return unknown(); 578b443a0aeac38e6fdce063224dfc746c269b0779dNuno Lopes 579b443a0aeac38e6fdce063224dfc746c269b0779dNuno Lopes SizeOffsetType Ret = compute(PHI.getIncomingValue(0)); 580b443a0aeac38e6fdce063224dfc746c269b0779dNuno Lopes if (!bothKnown(Ret)) 581b443a0aeac38e6fdce063224dfc746c269b0779dNuno Lopes return unknown(); 582b443a0aeac38e6fdce063224dfc746c269b0779dNuno Lopes 583b443a0aeac38e6fdce063224dfc746c269b0779dNuno Lopes // Verify that all PHI incoming pointers have the same size and offset. 584b443a0aeac38e6fdce063224dfc746c269b0779dNuno Lopes for (unsigned i = 1, e = PHI.getNumIncomingValues(); i != e; ++i) { 585b443a0aeac38e6fdce063224dfc746c269b0779dNuno Lopes SizeOffsetType EdgeData = compute(PHI.getIncomingValue(i)); 586b443a0aeac38e6fdce063224dfc746c269b0779dNuno Lopes if (!bothKnown(EdgeData) || EdgeData != Ret) 587b443a0aeac38e6fdce063224dfc746c269b0779dNuno Lopes return unknown(); 588b443a0aeac38e6fdce063224dfc746c269b0779dNuno Lopes } 589b443a0aeac38e6fdce063224dfc746c269b0779dNuno Lopes return Ret; 5909e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 5919e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5929e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType ObjectSizeOffsetVisitor::visitSelectInst(SelectInst &I) { 5939e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizeOffsetType TrueSide = compute(I.getTrueValue()); 5949e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizeOffsetType FalseSide = compute(I.getFalseValue()); 5952e594fa85c809178ce598a9b4c3a3bf5e0e6a14eNuno Lopes if (bothKnown(TrueSide) && bothKnown(FalseSide) && TrueSide == FalseSide) 5969e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return TrueSide; 5979e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 5989e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 5999e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6009e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType ObjectSizeOffsetVisitor::visitUndefValue(UndefValue&) { 6019e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(Zero, Zero); 6029e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 6039e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6049e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType ObjectSizeOffsetVisitor::visitInstruction(Instruction &I) { 6059e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes DEBUG(dbgs() << "ObjectSizeOffsetVisitor unknown instruction:" << I << '\n'); 6069e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 6079e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 6089e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6099e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6103574eca1b02600bac4e625297f4ecf745f4c4f32Micah VillmowObjectSizeOffsetEvaluator::ObjectSizeOffsetEvaluator(const DataLayout *TD, 6118e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer const TargetLibraryInfo *TLI, 612ece6c6bb6329748b92403c06ac87f45c43485911Chandler Carruth LLVMContext &Context) 6138e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer: TD(TD), TLI(TLI), Context(Context), Builder(Context, TargetFolder(TD)) { 614ece6c6bb6329748b92403c06ac87f45c43485911Chandler Carruth IntTy = TD->getIntPtrType(Context); 6159e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Zero = ConstantInt::get(IntTy, 0); 6169e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 6179e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6189e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetEvalType ObjectSizeOffsetEvaluator::compute(Value *V) { 6199e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizeOffsetEvalType Result = compute_(V); 6209e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6219e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!bothKnown(Result)) { 6229e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // erase everything that was computed in this iteration from the cache, so 6239e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // that no dangling references are left behind. We could be a bit smarter if 6249e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // we kept a dependency graph. It's probably not worth the complexity. 6259e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes for (PtrSetTy::iterator I=SeenVals.begin(), E=SeenVals.end(); I != E; ++I) { 6269e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes CacheMapTy::iterator CacheIt = CacheMap.find(*I); 6279e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // non-computable results can be safely cached 6289e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (CacheIt != CacheMap.end() && anyKnown(CacheIt->second)) 6299e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes CacheMap.erase(CacheIt); 6309e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } 6319e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } 6329e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6339e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SeenVals.clear(); 6349e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return Result; 6359e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 6369e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6379e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetEvalType ObjectSizeOffsetEvaluator::compute_(Value *V) { 6388e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer ObjectSizeOffsetVisitor Visitor(TD, TLI, Context); 6399e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizeOffsetType Const = Visitor.compute(V); 6409e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (Visitor.bothKnown(Const)) 6419e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(ConstantInt::get(Context, Const.first), 6429e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes ConstantInt::get(Context, Const.second)); 6439e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6449e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes V = V->stripPointerCasts(); 6459e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6469e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // check cache 6479e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes CacheMapTy::iterator CacheIt = CacheMap.find(V); 6489e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (CacheIt != CacheMap.end()) 6499e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return CacheIt->second; 6509e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6519e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // always generate code immediately before the instruction being 6529e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // processed, so that the generated code dominates the same BBs 6539e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Instruction *PrevInsertPoint = Builder.GetInsertPoint(); 6549e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (Instruction *I = dyn_cast<Instruction>(V)) 6559e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Builder.SetInsertPoint(I); 6569e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6579e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // record the pointers that were handled in this run, so that they can be 6589e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // cleaned later if something fails 6599e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SeenVals.insert(V); 6609e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6619e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // now compute the size and offset 6629e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizeOffsetEvalType Result; 6639e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { 6649e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Result = visitGEPOperator(*GEP); 6659e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } else if (Instruction *I = dyn_cast<Instruction>(V)) { 6669e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Result = visit(*I); 6679e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } else if (isa<Argument>(V) || 6689e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes (isa<ConstantExpr>(V) && 6699e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes cast<ConstantExpr>(V)->getOpcode() == Instruction::IntToPtr) || 67041be2fb1f9e9b8f796effb81c2bee6cf397136cfNuno Lopes isa<GlobalAlias>(V) || 6719e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes isa<GlobalVariable>(V)) { 6729e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // ignore values where we cannot do more than what ObjectSizeVisitor can 6739e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Result = unknown(); 6749e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } else { 6759e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes DEBUG(dbgs() << "ObjectSizeOffsetEvaluator::compute() unhandled value: " 6769e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes << *V << '\n'); 6779e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Result = unknown(); 6789e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } 6799e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6809e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (PrevInsertPoint) 6819e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Builder.SetInsertPoint(PrevInsertPoint); 6829e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6839e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // Don't reuse CacheIt since it may be invalid at this point. 6849e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes CacheMap[V] = Result; 6859e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return Result; 6869e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 6879e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6889e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetEvalType ObjectSizeOffsetEvaluator::visitAllocaInst(AllocaInst &I) { 6899e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!I.getAllocatedType()->isSized()) 6909e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 6919e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6929e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // must be a VLA 6939e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes assert(I.isArrayAllocation()); 6949e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Value *ArraySize = I.getArraySize(); 6959e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Value *Size = ConstantInt::get(ArraySize->getType(), 6969e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes TD->getTypeAllocSize(I.getAllocatedType())); 6979e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Size = Builder.CreateMul(Size, ArraySize); 6989e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(Size, Zero); 6999e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 7009e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 7019e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetEvalType ObjectSizeOffsetEvaluator::visitCallSite(CallSite CS) { 7028e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer const AllocFnsTy *FnData = getAllocationData(CS.getInstruction(), AnyAlloc, 7038e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer TLI); 7049e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!FnData) 7059e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 7069e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 7079e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // handle strdup-like functions separately 7089e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (FnData->AllocTy == StrDupLike) { 7096e699bf38dd862331532bd6f74ec491bdfad5db9Nuno Lopes // TODO 7106e699bf38dd862331532bd6f74ec491bdfad5db9Nuno Lopes return unknown(); 7119e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } 7129e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 713034dd6c6a118cf78ebfa6bf3496cd5b0df578a9eNuno Lopes Value *FirstArg = CS.getArgument(FnData->FstParam); 714034dd6c6a118cf78ebfa6bf3496cd5b0df578a9eNuno Lopes FirstArg = Builder.CreateZExt(FirstArg, IntTy); 715ef22f04bad6f5037fd4cc4d144e0c418f6cb2edcNuno Lopes if (FnData->SndParam < 0) 7169e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(FirstArg, Zero); 7179e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 7189e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Value *SecondArg = CS.getArgument(FnData->SndParam); 719034dd6c6a118cf78ebfa6bf3496cd5b0df578a9eNuno Lopes SecondArg = Builder.CreateZExt(SecondArg, IntTy); 7209e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Value *Size = Builder.CreateMul(FirstArg, SecondArg); 7219e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(Size, Zero); 7229e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 7239e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // TODO: handle more standard functions (+ wchar cousins): 7246e699bf38dd862331532bd6f74ec491bdfad5db9Nuno Lopes // - strdup / strndup 7259e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // - strcpy / strncpy 7269e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // - strcat / strncat 7279e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // - memcpy / memmove 7286e699bf38dd862331532bd6f74ec491bdfad5db9Nuno Lopes // - strcat / strncat 7299e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // - memset 7309e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 7319e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 7329e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetEvalType 73341a3f251346681e21171879dce409b2e6a3ba750Nuno LopesObjectSizeOffsetEvaluator::visitExtractElementInst(ExtractElementInst&) { 73441a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes return unknown(); 73541a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes} 73641a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes 73741a3f251346681e21171879dce409b2e6a3ba750Nuno LopesSizeOffsetEvalType 73841a3f251346681e21171879dce409b2e6a3ba750Nuno LopesObjectSizeOffsetEvaluator::visitExtractValueInst(ExtractValueInst&) { 73941a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes return unknown(); 74041a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes} 74141a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes 74241a3f251346681e21171879dce409b2e6a3ba750Nuno LopesSizeOffsetEvalType 7439e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesObjectSizeOffsetEvaluator::visitGEPOperator(GEPOperator &GEP) { 7449e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizeOffsetEvalType PtrData = compute_(GEP.getPointerOperand()); 7459e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!bothKnown(PtrData)) 7469e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 7479e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 748c606c3ff911eddcbf8bab95e67c7d8c1f69a493eNuno Lopes Value *Offset = EmitGEPOffset(&Builder, *TD, &GEP, /*NoAssumptions=*/true); 7499e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Offset = Builder.CreateAdd(PtrData.second, Offset); 7509e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(PtrData.first, Offset); 7519e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 7529e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 7539e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetEvalType ObjectSizeOffsetEvaluator::visitIntToPtrInst(IntToPtrInst&) { 7549e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // clueless 7559e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 7569e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 7579e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 7589e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetEvalType ObjectSizeOffsetEvaluator::visitLoadInst(LoadInst&) { 7599e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 7609e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 7619e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 7629e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetEvalType ObjectSizeOffsetEvaluator::visitPHINode(PHINode &PHI) { 7639e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // create 2 PHIs: one for size and another for offset 7649e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes PHINode *SizePHI = Builder.CreatePHI(IntTy, PHI.getNumIncomingValues()); 7659e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes PHINode *OffsetPHI = Builder.CreatePHI(IntTy, PHI.getNumIncomingValues()); 7669e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 7679e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // insert right away in the cache to handle recursive PHIs 7689e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes CacheMap[&PHI] = std::make_pair(SizePHI, OffsetPHI); 7699e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 7709e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // compute offset/size for each PHI incoming pointer 7719e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes for (unsigned i = 0, e = PHI.getNumIncomingValues(); i != e; ++i) { 7729e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Builder.SetInsertPoint(PHI.getIncomingBlock(i)->getFirstInsertionPt()); 7739e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizeOffsetEvalType EdgeData = compute_(PHI.getIncomingValue(i)); 7749e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 7759e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!bothKnown(EdgeData)) { 7769e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes OffsetPHI->replaceAllUsesWith(UndefValue::get(IntTy)); 7779e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes OffsetPHI->eraseFromParent(); 7789e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizePHI->replaceAllUsesWith(UndefValue::get(IntTy)); 7799e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizePHI->eraseFromParent(); 7809e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 7819e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } 7829e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizePHI->addIncoming(EdgeData.first, PHI.getIncomingBlock(i)); 7839e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes OffsetPHI->addIncoming(EdgeData.second, PHI.getIncomingBlock(i)); 7849e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } 7850dff532fce434c3e9fdf9695aed8efeb5f752ed5Nuno Lopes 7860dff532fce434c3e9fdf9695aed8efeb5f752ed5Nuno Lopes Value *Size = SizePHI, *Offset = OffsetPHI, *Tmp; 7870dff532fce434c3e9fdf9695aed8efeb5f752ed5Nuno Lopes if ((Tmp = SizePHI->hasConstantValue())) { 7880dff532fce434c3e9fdf9695aed8efeb5f752ed5Nuno Lopes Size = Tmp; 7890dff532fce434c3e9fdf9695aed8efeb5f752ed5Nuno Lopes SizePHI->replaceAllUsesWith(Size); 7900dff532fce434c3e9fdf9695aed8efeb5f752ed5Nuno Lopes SizePHI->eraseFromParent(); 7910dff532fce434c3e9fdf9695aed8efeb5f752ed5Nuno Lopes } 7920dff532fce434c3e9fdf9695aed8efeb5f752ed5Nuno Lopes if ((Tmp = OffsetPHI->hasConstantValue())) { 7930dff532fce434c3e9fdf9695aed8efeb5f752ed5Nuno Lopes Offset = Tmp; 7940dff532fce434c3e9fdf9695aed8efeb5f752ed5Nuno Lopes OffsetPHI->replaceAllUsesWith(Offset); 7950dff532fce434c3e9fdf9695aed8efeb5f752ed5Nuno Lopes OffsetPHI->eraseFromParent(); 7960dff532fce434c3e9fdf9695aed8efeb5f752ed5Nuno Lopes } 7970dff532fce434c3e9fdf9695aed8efeb5f752ed5Nuno Lopes return std::make_pair(Size, Offset); 7989e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 7999e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 8009e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetEvalType ObjectSizeOffsetEvaluator::visitSelectInst(SelectInst &I) { 8019e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizeOffsetEvalType TrueSide = compute_(I.getTrueValue()); 8029e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizeOffsetEvalType FalseSide = compute_(I.getFalseValue()); 8039e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 8049e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!bothKnown(TrueSide) || !bothKnown(FalseSide)) 8059e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 8069e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (TrueSide == FalseSide) 8079e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return TrueSide; 8089e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 8099e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Value *Size = Builder.CreateSelect(I.getCondition(), TrueSide.first, 8109e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes FalseSide.first); 8119e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Value *Offset = Builder.CreateSelect(I.getCondition(), TrueSide.second, 8129e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes FalseSide.second); 8139e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(Size, Offset); 8149e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 8159e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 8169e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetEvalType ObjectSizeOffsetEvaluator::visitInstruction(Instruction &I) { 8179e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes DEBUG(dbgs() << "ObjectSizeOffsetEvaluator unknown instruction:" << I <<'\n'); 8189e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 8199e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 820