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 15f006b183e2d2bebcf6968d1dd7350397c95b0325Victor Hernandez#include "llvm/Analysis/MemoryBuiltins.h" 16d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/STLExtras.h" 17d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 18d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/ValueTracking.h" 190b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DataLayout.h" 200b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/GlobalVariable.h" 210b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 220b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Intrinsics.h" 230b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Metadata.h" 240b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Module.h" 259e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes#include "llvm/Support/Debug.h" 269e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes#include "llvm/Support/MathExtras.h" 279e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes#include "llvm/Support/raw_ostream.h" 288e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer#include "llvm/Target/TargetLibraryInfo.h" 299e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes#include "llvm/Transforms/Utils/Local.h" 30fabcb9127f278a77b8aae5673be1115390c55050Evan Chengusing namespace llvm; 31fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 32dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "memory-builtins" 33dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 349e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopesenum AllocType { 35d44f9f2ff88cd03e3f944ecdd6373737d5acdb90Benjamin Kramer OpNewLike = 1<<0, // allocates; never returns null 36d44f9f2ff88cd03e3f944ecdd6373737d5acdb90Benjamin Kramer MallocLike = 1<<1 | OpNewLike, // allocates; may return null 37d44f9f2ff88cd03e3f944ecdd6373737d5acdb90Benjamin Kramer CallocLike = 1<<2, // allocates + bzero 38d44f9f2ff88cd03e3f944ecdd6373737d5acdb90Benjamin Kramer ReallocLike = 1<<3, // reallocates 39d44f9f2ff88cd03e3f944ecdd6373737d5acdb90Benjamin Kramer StrDupLike = 1<<4, 40d44f9f2ff88cd03e3f944ecdd6373737d5acdb90Benjamin Kramer AllocLike = MallocLike | CallocLike | StrDupLike, 41989779ccc746eb7d7ab4774f25d7a3e1be14923eBenjamin Kramer AnyAlloc = AllocLike | ReallocLike 429e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes}; 439e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 449e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopesstruct AllocFnsTy { 458e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer LibFunc::Func Func; 469e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes AllocType AllocTy; 479e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes unsigned char NumParams; 489e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // First and Second size parameters (or -1 if unused) 49ef22f04bad6f5037fd4cc4d144e0c418f6cb2edcNuno Lopes signed char FstParam, SndParam; 509e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes}; 519e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5241a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes// FIXME: certain users need more information. E.g., SimplifyLibCalls needs to 5341a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes// know which functions are nounwind, noalias, nocapture parameters, etc. 549e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopesstatic const AllocFnsTy AllocationFnData[] = { 558e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer {LibFunc::malloc, MallocLike, 1, 0, -1}, 568e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer {LibFunc::valloc, MallocLike, 1, 0, -1}, 576629210aaf9d2e4fcbecc80b35f72108304da4b4Benjamin Kramer {LibFunc::Znwj, OpNewLike, 1, 0, -1}, // new(unsigned int) 58e43e2d8cf0a5a05a1d1ed5abbc2134834a9b06d2Nadav Rotem {LibFunc::ZnwjRKSt9nothrow_t, MallocLike, 2, 0, -1}, // new(unsigned int, nothrow) 596629210aaf9d2e4fcbecc80b35f72108304da4b4Benjamin Kramer {LibFunc::Znwm, OpNewLike, 1, 0, -1}, // new(unsigned long) 60e43e2d8cf0a5a05a1d1ed5abbc2134834a9b06d2Nadav Rotem {LibFunc::ZnwmRKSt9nothrow_t, MallocLike, 2, 0, -1}, // new(unsigned long, nothrow) 616629210aaf9d2e4fcbecc80b35f72108304da4b4Benjamin Kramer {LibFunc::Znaj, OpNewLike, 1, 0, -1}, // new[](unsigned int) 62e43e2d8cf0a5a05a1d1ed5abbc2134834a9b06d2Nadav Rotem {LibFunc::ZnajRKSt9nothrow_t, MallocLike, 2, 0, -1}, // new[](unsigned int, nothrow) 636629210aaf9d2e4fcbecc80b35f72108304da4b4Benjamin Kramer {LibFunc::Znam, OpNewLike, 1, 0, -1}, // new[](unsigned long) 64e43e2d8cf0a5a05a1d1ed5abbc2134834a9b06d2Nadav Rotem {LibFunc::ZnamRKSt9nothrow_t, MallocLike, 2, 0, -1}, // new[](unsigned long, nothrow) 658e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer {LibFunc::calloc, CallocLike, 2, 0, 1}, 668e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer {LibFunc::realloc, ReallocLike, 2, 1, -1}, 678e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer {LibFunc::reallocf, ReallocLike, 2, 1, -1}, 688e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer {LibFunc::strdup, StrDupLike, 1, -1, -1}, 698e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer {LibFunc::strndup, StrDupLike, 2, 1, -1} 7009b16f3bb5e2b4194268866e1e8c969335a7aec6Benjamin Kramer // TODO: Handle "int posix_memalign(void **, size_t, size_t)" 719e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes}; 729e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 739e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 749e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopesstatic Function *getCalledFunction(const Value *V, bool LookThroughBitCast) { 759e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (LookThroughBitCast) 769e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes V = V->stripPointerCasts(); 772b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes 78d845c34170be5ece8aee3a1097849aa8ce9259cbNuno Lopes CallSite CS(const_cast<Value*>(V)); 79d845c34170be5ece8aee3a1097849aa8ce9259cbNuno Lopes if (!CS.getInstruction()) 80dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 81fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 822253a2f52f3c46ae75cd05f5885acb987bd1d6b6Michael Gottesman if (CS.isNoBuiltin()) 83dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 84eb351eb84945c64212b5e8582c09394542a7cc69Richard Smith 852b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes Function *Callee = CS.getCalledFunction(); 869e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!Callee || !Callee->isDeclaration()) 87dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 889e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return Callee; 89fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng} 90fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 919e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes/// \brief Returns the allocation data for the given value if it is a call to a 929e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes/// known allocation function, and NULL otherwise. 939e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopesstatic const AllocFnsTy *getAllocationData(const Value *V, AllocType AllocTy, 948e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer const TargetLibraryInfo *TLI, 959e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes bool LookThroughBitCast = false) { 96cacf97107972d0c9d29d14b8d67183c998d17d94Michael Ilseman // Skip intrinsics 97cacf97107972d0c9d29d14b8d67183c998d17d94Michael Ilseman if (isa<IntrinsicInst>(V)) 98dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 99cacf97107972d0c9d29d14b8d67183c998d17d94Michael Ilseman 1009e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Function *Callee = getCalledFunction(V, LookThroughBitCast); 1019e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!Callee) 102dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 103fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 1048e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer // Make sure that the function is available. 1058e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer StringRef FnName = Callee->getName(); 1068e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer LibFunc::Func TLIFn; 1078e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer if (!TLI || !TLI->getLibFunc(FnName, TLIFn) || !TLI->has(TLIFn)) 108dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 1098e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer 1109e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes unsigned i = 0; 1119e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes bool found = false; 1129e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes for ( ; i < array_lengthof(AllocationFnData); ++i) { 1138e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer if (AllocationFnData[i].Func == TLIFn) { 1149e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes found = true; 1159e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes break; 1169e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } 1179e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } 1189e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!found) 119dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 120fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 1219e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes const AllocFnsTy *FnData = &AllocationFnData[i]; 122d44f9f2ff88cd03e3f944ecdd6373737d5acdb90Benjamin Kramer if ((FnData->AllocTy & AllocTy) != FnData->AllocTy) 123dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 1249e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 1259e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // Check function prototype. 126ef22f04bad6f5037fd4cc4d144e0c418f6cb2edcNuno Lopes int FstParam = FnData->FstParam; 127ef22f04bad6f5037fd4cc4d144e0c418f6cb2edcNuno Lopes int SndParam = FnData->SndParam; 128db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner FunctionType *FTy = Callee->getFunctionType(); 1299e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 1309e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (FTy->getReturnType() == Type::getInt8PtrTy(FTy->getContext()) && 1319e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes FTy->getNumParams() == FnData->NumParams && 132ef22f04bad6f5037fd4cc4d144e0c418f6cb2edcNuno Lopes (FstParam < 0 || 1339e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes (FTy->getParamType(FstParam)->isIntegerTy(32) || 1349e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes FTy->getParamType(FstParam)->isIntegerTy(64))) && 135ef22f04bad6f5037fd4cc4d144e0c418f6cb2edcNuno Lopes (SndParam < 0 || 1369e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes FTy->getParamType(SndParam)->isIntegerTy(32) || 1379e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes FTy->getParamType(SndParam)->isIntegerTy(64))) 1389e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return FnData; 139dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 140fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng} 141fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 1429e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopesstatic bool hasNoAliasAttr(const Value *V, bool LookThroughBitCast) { 143e8742d084c54e9cd230fa03d368f0fedac2106cbNuno Lopes ImmutableCallSite CS(LookThroughBitCast ? V->stripPointerCasts() : V); 144034b94b17006f51722886b0f2283fb6fb19aca1fBill Wendling return CS && CS.hasFnAttr(Attribute::NoAlias); 145fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng} 146fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 1479e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 1482b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes/// \brief Tests if a value is a call or invoke to a library function that 1492b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes/// allocates or reallocates memory (either malloc, calloc, realloc, or strdup 1502b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes/// like). 1518e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramerbool llvm::isAllocationFn(const Value *V, const TargetLibraryInfo *TLI, 1528e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer bool LookThroughBitCast) { 1538e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer return getAllocationData(V, AnyAlloc, TLI, LookThroughBitCast); 154fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng} 155fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 1562b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes/// \brief Tests if a value is a call or invoke to a function that returns a 15741a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes/// NoAlias pointer (including malloc/calloc/realloc/strdup-like functions). 1588e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramerbool llvm::isNoAliasFn(const Value *V, const TargetLibraryInfo *TLI, 1598e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer bool LookThroughBitCast) { 16041a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes // it's safe to consider realloc as noalias since accessing the original 16141a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes // pointer is undefined behavior 1628e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer return isAllocationFn(V, TLI, LookThroughBitCast) || 1639e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes hasNoAliasAttr(V, LookThroughBitCast); 164fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng} 165fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 1662b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes/// \brief Tests if a value is a call or invoke to a library function that 1672b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes/// allocates uninitialized memory (such as malloc). 1688e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramerbool llvm::isMallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, 1698e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer bool LookThroughBitCast) { 1708e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer return getAllocationData(V, MallocLike, TLI, LookThroughBitCast); 1719e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 1729e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 1732b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes/// \brief Tests if a value is a call or invoke to a library function that 1742b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes/// allocates zero-filled memory (such as calloc). 1758e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramerbool llvm::isCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, 1768e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer bool LookThroughBitCast) { 1778e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer return getAllocationData(V, CallocLike, TLI, LookThroughBitCast); 1789e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 1799e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 1802b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes/// \brief Tests if a value is a call or invoke to a library function that 1812b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes/// allocates memory (either malloc, calloc, or strdup like). 1828e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramerbool llvm::isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI, 1838e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer bool LookThroughBitCast) { 1848e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer return getAllocationData(V, AllocLike, TLI, LookThroughBitCast); 1859e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 1869e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 1872b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes/// \brief Tests if a value is a call or invoke to a library function that 1882b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes/// reallocates memory (such as realloc). 1898e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramerbool llvm::isReallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, 1908e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer bool LookThroughBitCast) { 1918e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer return getAllocationData(V, ReallocLike, TLI, LookThroughBitCast); 1929e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 1939e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 1946629210aaf9d2e4fcbecc80b35f72108304da4b4Benjamin Kramer/// \brief Tests if a value is a call or invoke to a library function that 1956629210aaf9d2e4fcbecc80b35f72108304da4b4Benjamin Kramer/// allocates memory and never returns null (such as operator new). 1966629210aaf9d2e4fcbecc80b35f72108304da4b4Benjamin Kramerbool llvm::isOperatorNewLikeFn(const Value *V, const TargetLibraryInfo *TLI, 1976629210aaf9d2e4fcbecc80b35f72108304da4b4Benjamin Kramer bool LookThroughBitCast) { 1986629210aaf9d2e4fcbecc80b35f72108304da4b4Benjamin Kramer return getAllocationData(V, OpNewLike, TLI, LookThroughBitCast); 1996629210aaf9d2e4fcbecc80b35f72108304da4b4Benjamin Kramer} 2006629210aaf9d2e4fcbecc80b35f72108304da4b4Benjamin Kramer 2019e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes/// extractMallocCall - Returns the corresponding CallInst if the instruction 2029e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes/// is a malloc call. Since CallInst::CreateMalloc() only creates calls, we 2039e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes/// ignore InvokeInst here. 2048e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramerconst CallInst *llvm::extractMallocCall(const Value *I, 2058e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer const TargetLibraryInfo *TLI) { 206dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return isMallocLikeFn(I, TLI) ? dyn_cast<CallInst>(I) : nullptr; 207fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng} 208fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 209cee51c48030f37133ad4004d3e5c14d8ebfc91c4Matt Arsenaultstatic Value *computeArraySize(const CallInst *CI, const DataLayout *DL, 2108e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer const TargetLibraryInfo *TLI, 2118e345a1c418608c49abb7c51a090bbb36f1273bcVictor Hernandez bool LookThroughSExt = false) { 212fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng if (!CI) 213dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 214fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 2159d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez // The size of the malloc's result type must be known to determine array size. 2168e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer Type *T = getMallocAllocatedType(CI, TLI); 217cee51c48030f37133ad4004d3e5c14d8ebfc91c4Matt Arsenault if (!T || !T->isSized() || !DL) 218dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 219fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 220cee51c48030f37133ad4004d3e5c14d8ebfc91c4Matt Arsenault unsigned ElementSize = DL->getTypeAllocSize(T); 221db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner if (StructType *ST = dyn_cast<StructType>(T)) 222cee51c48030f37133ad4004d3e5c14d8ebfc91c4Matt Arsenault ElementSize = DL->getStructLayout(ST)->getSizeInBytes(); 2239d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez 224e3401c4fae95bc69dada2a3f9080d9f15349af61Gabor Greif // If malloc call's arg can be determined to be a multiple of ElementSize, 2258e345a1c418608c49abb7c51a090bbb36f1273bcVictor Hernandez // return the multiple. Otherwise, return NULL. 226e3401c4fae95bc69dada2a3f9080d9f15349af61Gabor Greif Value *MallocArg = CI->getArgOperand(0); 227dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Value *Multiple = nullptr; 2288e345a1c418608c49abb7c51a090bbb36f1273bcVictor Hernandez if (ComputeMultiple(MallocArg, ElementSize, Multiple, 2293dbb9e64d6e9d1e8bf16f75ebe4fe59ffdf93dd3Dan Gohman LookThroughSExt)) 2308e345a1c418608c49abb7c51a090bbb36f1273bcVictor Hernandez return Multiple; 23188d9839d07a6b5a03484d664913de0f2b33d3bffVictor Hernandez 232dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 233fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng} 234fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 2359333ffb6db95e8ec2e34d2013c4fee47cecc8e91Michael Ilseman/// isArrayMalloc - Returns the corresponding CallInst if the instruction 23690f48e7c91a8faa875ba889ca66b137ffd46e34aVictor Hernandez/// is a call to malloc whose array size can be determined and the array size 23790f48e7c91a8faa875ba889ca66b137ffd46e34aVictor Hernandez/// is not constant 1. Otherwise, return NULL. 2388e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramerconst CallInst *llvm::isArrayMalloc(const Value *I, 239cee51c48030f37133ad4004d3e5c14d8ebfc91c4Matt Arsenault const DataLayout *DL, 2408e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer const TargetLibraryInfo *TLI) { 2418e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer const CallInst *CI = extractMallocCall(I, TLI); 242cee51c48030f37133ad4004d3e5c14d8ebfc91c4Matt Arsenault Value *ArraySize = computeArraySize(CI, DL, TLI); 24390f48e7c91a8faa875ba889ca66b137ffd46e34aVictor Hernandez 244b1b6c170819120e535ef706f58041bb6caebe35dJakub Staszak if (ConstantInt *ConstSize = dyn_cast_or_null<ConstantInt>(ArraySize)) 245b1b6c170819120e535ef706f58041bb6caebe35dJakub Staszak if (ConstSize->isOne()) 246b1b6c170819120e535ef706f58041bb6caebe35dJakub Staszak return CI; 24790f48e7c91a8faa875ba889ca66b137ffd46e34aVictor Hernandez 24890f48e7c91a8faa875ba889ca66b137ffd46e34aVictor Hernandez // CI is a non-array malloc or we can't figure out that it is an array malloc. 249dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 250fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng} 251fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 252fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng/// getMallocType - Returns the PointerType resulting from the malloc call. 2539d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez/// The PointerType depends on the number of bitcast uses of the malloc call: 2549d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez/// 0: PointerType is the calls' return type. 2559d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez/// 1: PointerType is the bitcast's result type. 2569d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez/// >1: Unique PointerType cannot be determined, return NULL. 2578e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin KramerPointerType *llvm::getMallocType(const CallInst *CI, 2588e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer const TargetLibraryInfo *TLI) { 2598e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer assert(isMallocLikeFn(CI, TLI) && "getMallocType and not malloc call"); 2609333ffb6db95e8ec2e34d2013c4fee47cecc8e91Michael Ilseman 261dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines PointerType *MallocType = nullptr; 2629d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez unsigned NumOfBitCastUses = 0; 2639d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez 26488d9839d07a6b5a03484d664913de0f2b33d3bffVictor Hernandez // Determine if CallInst has a bitcast use. 26536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (Value::const_user_iterator UI = CI->user_begin(), E = CI->user_end(); 26636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines UI != E;) 2679d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez if (const BitCastInst *BCI = dyn_cast<BitCastInst>(*UI++)) { 2689d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez MallocType = cast<PointerType>(BCI->getDestTy()); 2699d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez NumOfBitCastUses++; 2709d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez } 27188d9839d07a6b5a03484d664913de0f2b33d3bffVictor Hernandez 2729d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez // Malloc call has 1 bitcast use, so type is the bitcast's destination type. 2739d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez if (NumOfBitCastUses == 1) 2749d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez return MallocType; 275fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 27660cfc03379c1ec3fac3dc807f5e93842c0b95f33Victor Hernandez // Malloc call was not bitcast, so type is the malloc function's return type. 2779d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez if (NumOfBitCastUses == 0) 27888d9839d07a6b5a03484d664913de0f2b33d3bffVictor Hernandez return cast<PointerType>(CI->getType()); 279fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 28088d9839d07a6b5a03484d664913de0f2b33d3bffVictor Hernandez // Type could not be determined. 281dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 282fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng} 283fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 2849d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez/// getMallocAllocatedType - Returns the Type allocated by malloc call. 2859d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez/// The Type depends on the number of bitcast uses of the malloc call: 2869d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez/// 0: PointerType is the malloc calls' return type. 2879d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez/// 1: PointerType is the bitcast's result type. 2889d0b704e3ea418441001dac4d1a56c2c224cdbf5Victor Hernandez/// >1: Unique PointerType cannot be determined, return NULL. 2898e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin KramerType *llvm::getMallocAllocatedType(const CallInst *CI, 2908e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer const TargetLibraryInfo *TLI) { 2918e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer PointerType *PT = getMallocType(CI, TLI); 292dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return PT ? PT->getElementType() : nullptr; 293fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng} 294fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng 2959333ffb6db95e8ec2e34d2013c4fee47cecc8e91Michael Ilseman/// getMallocArraySize - Returns the array size of a malloc call. If the 29690f48e7c91a8faa875ba889ca66b137ffd46e34aVictor Hernandez/// argument passed to malloc is a multiple of the size of the malloced type, 29790f48e7c91a8faa875ba889ca66b137ffd46e34aVictor Hernandez/// then return that multiple. For non-array mallocs, the multiple is 29890f48e7c91a8faa875ba889ca66b137ffd46e34aVictor Hernandez/// constant 1. Otherwise, return NULL for mallocs whose array size cannot be 2992491ce03535cf8ec171570d2e28df63e4db3dd6bVictor Hernandez/// determined. 300cee51c48030f37133ad4004d3e5c14d8ebfc91c4Matt ArsenaultValue *llvm::getMallocArraySize(CallInst *CI, const DataLayout *DL, 3018e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer const TargetLibraryInfo *TLI, 3028e345a1c418608c49abb7c51a090bbb36f1273bcVictor Hernandez bool LookThroughSExt) { 3038e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer assert(isMallocLikeFn(CI, TLI) && "getMallocArraySize and not malloc call"); 304cee51c48030f37133ad4004d3e5c14d8ebfc91c4Matt Arsenault return computeArraySize(CI, DL, TLI, LookThroughSExt); 305fabcb9127f278a77b8aae5673be1115390c55050Evan Cheng} 30666284e063a1e46500acae48bdc0e4a00652021d1Victor Hernandez 307252ef566e8734b6bcf46434d0a7954c9eda0bd96Nuno Lopes 308252ef566e8734b6bcf46434d0a7954c9eda0bd96Nuno Lopes/// extractCallocCall - Returns the corresponding CallInst if the instruction 309252ef566e8734b6bcf46434d0a7954c9eda0bd96Nuno Lopes/// is a calloc call. 3108e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramerconst CallInst *llvm::extractCallocCall(const Value *I, 3118e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer const TargetLibraryInfo *TLI) { 312dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return isCallocLikeFn(I, TLI) ? cast<CallInst>(I) : nullptr; 313252ef566e8734b6bcf46434d0a7954c9eda0bd96Nuno Lopes} 314252ef566e8734b6bcf46434d0a7954c9eda0bd96Nuno Lopes 315046e78ce55a7c3d82b7b6758d2d77f2d99f970bfVictor Hernandez 31602680f946b8dcbeff3b8d7236030678551b15a6cGabor Greif/// isFreeCall - Returns non-null if the value is a call to the builtin free() 3178e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramerconst CallInst *llvm::isFreeCall(const Value *I, const TargetLibraryInfo *TLI) { 31866284e063a1e46500acae48bdc0e4a00652021d1Victor Hernandez const CallInst *CI = dyn_cast<CallInst>(I); 319cacf97107972d0c9d29d14b8d67183c998d17d94Michael Ilseman if (!CI || isa<IntrinsicInst>(CI)) 320dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 3213ad70d5d61f3f86fb5bc167e157680fc107a1173Victor Hernandez Function *Callee = CI->getCalledFunction(); 322dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Callee == nullptr || !Callee->isDeclaration()) 323dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 32442e72ca3d00dbe073fbb39e181caa7f0c4c171b7Nick Lewycky 3258e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer StringRef FnName = Callee->getName(); 3268e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer LibFunc::Func TLIFn; 3278e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer if (!TLI || !TLI->getLibFunc(FnName, TLIFn) || !TLI->has(TLIFn)) 328dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 3298e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer 33072c8331ec1437f8c33fff1dac1ea0ebb11009411Richard Smith unsigned ExpectedNumParams; 33172c8331ec1437f8c33fff1dac1ea0ebb11009411Richard Smith if (TLIFn == LibFunc::free || 33272c8331ec1437f8c33fff1dac1ea0ebb11009411Richard Smith TLIFn == LibFunc::ZdlPv || // operator delete(void*) 33372c8331ec1437f8c33fff1dac1ea0ebb11009411Richard Smith TLIFn == LibFunc::ZdaPv) // operator delete[](void*) 33472c8331ec1437f8c33fff1dac1ea0ebb11009411Richard Smith ExpectedNumParams = 1; 33572c8331ec1437f8c33fff1dac1ea0ebb11009411Richard Smith else if (TLIFn == LibFunc::ZdlPvRKSt9nothrow_t || // delete(void*, nothrow) 33672c8331ec1437f8c33fff1dac1ea0ebb11009411Richard Smith TLIFn == LibFunc::ZdaPvRKSt9nothrow_t) // delete[](void*, nothrow) 33772c8331ec1437f8c33fff1dac1ea0ebb11009411Richard Smith ExpectedNumParams = 2; 33872c8331ec1437f8c33fff1dac1ea0ebb11009411Richard Smith else 339dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 34066284e063a1e46500acae48bdc0e4a00652021d1Victor Hernandez 34166284e063a1e46500acae48bdc0e4a00652021d1Victor Hernandez // Check free prototype. 3429333ffb6db95e8ec2e34d2013c4fee47cecc8e91Michael Ilseman // FIXME: workaround for PR5130, this will be obsolete when a nobuiltin 34366284e063a1e46500acae48bdc0e4a00652021d1Victor Hernandez // attribute will exist. 344db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner FunctionType *FTy = Callee->getFunctionType(); 3453ad70d5d61f3f86fb5bc167e157680fc107a1173Victor Hernandez if (!FTy->getReturnType()->isVoidTy()) 346dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 34772c8331ec1437f8c33fff1dac1ea0ebb11009411Richard Smith if (FTy->getNumParams() != ExpectedNumParams) 348dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 349ebb2189904564c7c6193e7f23904f1ced7975480Chris Lattner if (FTy->getParamType(0) != Type::getInt8PtrTy(Callee->getContext())) 350dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 35166284e063a1e46500acae48bdc0e4a00652021d1Victor Hernandez 35202680f946b8dcbeff3b8d7236030678551b15a6cGabor Greif return CI; 35366284e063a1e46500acae48bdc0e4a00652021d1Victor Hernandez} 3549e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3559e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3569e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3579e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes//===----------------------------------------------------------------------===// 3589e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes// Utility functions to compute size of objects. 3599e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes// 3609e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3619e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3629e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes/// \brief Compute the size of the object pointed by Ptr. Returns true and the 3639e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes/// object size in Size if successful, and false otherwise. 3649e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes/// If RoundToAlign is true, then Size is rounded up to the aligment of allocas, 3659e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes/// byval arguments, and global variables. 366cee51c48030f37133ad4004d3e5c14d8ebfc91c4Matt Arsenaultbool llvm::getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout *DL, 3678e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer const TargetLibraryInfo *TLI, bool RoundToAlign) { 368cee51c48030f37133ad4004d3e5c14d8ebfc91c4Matt Arsenault if (!DL) 3699e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return false; 3709e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 371cee51c48030f37133ad4004d3e5c14d8ebfc91c4Matt Arsenault ObjectSizeOffsetVisitor Visitor(DL, TLI, Ptr->getContext(), RoundToAlign); 3729e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizeOffsetType Data = Visitor.compute(const_cast<Value*>(Ptr)); 3739e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!Visitor.bothKnown(Data)) 3749e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return false; 3759e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3769e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes APInt ObjSize = Data.first, Offset = Data.second; 3779e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // check for overflow 3789e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (Offset.slt(0) || ObjSize.ult(Offset)) 3799e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Size = 0; 3809e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes else 3819e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Size = (ObjSize - Offset).getZExtValue(); 3829e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return true; 3839e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 3849e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3859e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3869e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSTATISTIC(ObjectVisitorArgument, 3879e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes "Number of arguments with unsolved size and offset"); 3889e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSTATISTIC(ObjectVisitorLoad, 3899e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes "Number of load instructions with unsolved size and offset"); 3909e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3919e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 3929e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesAPInt ObjectSizeOffsetVisitor::align(APInt Size, uint64_t Align) { 3939e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (RoundToAlign && Align) 3949e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return APInt(IntTyBits, RoundUpToAlignment(Size.getZExtValue(), Align)); 3959e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return Size; 3969e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 3979e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 398cee51c48030f37133ad4004d3e5c14d8ebfc91c4Matt ArsenaultObjectSizeOffsetVisitor::ObjectSizeOffsetVisitor(const DataLayout *DL, 3998e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer const TargetLibraryInfo *TLI, 4009e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes LLVMContext &Context, 401ece6c6bb6329748b92403c06ac87f45c43485911Chandler Carruth bool RoundToAlign) 402cee51c48030f37133ad4004d3e5c14d8ebfc91c4Matt Arsenault: DL(DL), TLI(TLI), RoundToAlign(RoundToAlign) { 40336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Pointer size must be rechecked for each object visited since it could have 40436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // a different address space. 4059e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 4069e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 4079e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType ObjectSizeOffsetVisitor::compute(Value *V) { 40836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines IntTyBits = DL->getPointerTypeSizeInBits(V->getType()); 40936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Zero = APInt::getNullValue(IntTyBits); 41036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 4119e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes V = V->stripPointerCasts(); 4128e4df489d0e02e0fbdd00ed829e70e5f21998162Nadav Rotem if (Instruction *I = dyn_cast<Instruction>(V)) { 4138e4df489d0e02e0fbdd00ed829e70e5f21998162Nadav Rotem // If we have already seen this instruction, bail out. Cycles can happen in 4148e4df489d0e02e0fbdd00ed829e70e5f21998162Nadav Rotem // unreachable code after constant propagation. 4158e4df489d0e02e0fbdd00ed829e70e5f21998162Nadav Rotem if (!SeenInsts.insert(I)) 4168e4df489d0e02e0fbdd00ed829e70e5f21998162Nadav Rotem return unknown(); 4170a9ff4cab3a3fc1179c37855717a54ae44a5312eNuno Lopes 418168843c0137ad67c24a3930244a9c5f60add320dBenjamin Kramer if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) 4198e4df489d0e02e0fbdd00ed829e70e5f21998162Nadav Rotem return visitGEPOperator(*GEP); 4208e4df489d0e02e0fbdd00ed829e70e5f21998162Nadav Rotem return visit(*I); 421168843c0137ad67c24a3930244a9c5f60add320dBenjamin Kramer } 4229e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (Argument *A = dyn_cast<Argument>(V)) 4239e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return visitArgument(*A); 4249e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (ConstantPointerNull *P = dyn_cast<ConstantPointerNull>(V)) 4259e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return visitConstantPointerNull(*P); 42641be2fb1f9e9b8f796effb81c2bee6cf397136cfNuno Lopes if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) 42741be2fb1f9e9b8f796effb81c2bee6cf397136cfNuno Lopes return visitGlobalAlias(*GA); 4289e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) 4299e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return visitGlobalVariable(*GV); 4309e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (UndefValue *UV = dyn_cast<UndefValue>(V)) 4319e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return visitUndefValue(*UV); 432168843c0137ad67c24a3930244a9c5f60add320dBenjamin Kramer if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) { 4339e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (CE->getOpcode() == Instruction::IntToPtr) 4349e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); // clueless 4358e4df489d0e02e0fbdd00ed829e70e5f21998162Nadav Rotem if (CE->getOpcode() == Instruction::GetElementPtr) 4368e4df489d0e02e0fbdd00ed829e70e5f21998162Nadav Rotem return visitGEPOperator(cast<GEPOperator>(*CE)); 437168843c0137ad67c24a3930244a9c5f60add320dBenjamin Kramer } 4389e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 4399e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes DEBUG(dbgs() << "ObjectSizeOffsetVisitor::compute() unhandled value: " << *V 4409e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes << '\n'); 4419e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 4429e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 4439e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 4449e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType ObjectSizeOffsetVisitor::visitAllocaInst(AllocaInst &I) { 4459e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!I.getAllocatedType()->isSized()) 4469e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 4479e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 448cee51c48030f37133ad4004d3e5c14d8ebfc91c4Matt Arsenault APInt Size(IntTyBits, DL->getTypeAllocSize(I.getAllocatedType())); 4499e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!I.isArrayAllocation()) 4509e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(align(Size, I.getAlignment()), Zero); 4519e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 4529e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Value *ArraySize = I.getArraySize(); 4539e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (const ConstantInt *C = dyn_cast<ConstantInt>(ArraySize)) { 4549e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Size *= C->getValue().zextOrSelf(IntTyBits); 4559e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(align(Size, I.getAlignment()), Zero); 4569e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } 4579e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 4589e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 4599e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 4609e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType ObjectSizeOffsetVisitor::visitArgument(Argument &A) { 4619e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // no interprocedural analysis is done at the moment 46236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!A.hasByValOrInAllocaAttr()) { 4639e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes ++ObjectVisitorArgument; 4649e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 4659e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } 4669e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes PointerType *PT = cast<PointerType>(A.getType()); 467cee51c48030f37133ad4004d3e5c14d8ebfc91c4Matt Arsenault APInt Size(IntTyBits, DL->getTypeAllocSize(PT->getElementType())); 4689e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(align(Size, A.getParamAlignment()), Zero); 4699e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 4709e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 4719e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType ObjectSizeOffsetVisitor::visitCallSite(CallSite CS) { 4728e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer const AllocFnsTy *FnData = getAllocationData(CS.getInstruction(), AnyAlloc, 4738e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer TLI); 4749e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!FnData) 4759e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 4769e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 4779e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // handle strdup-like functions separately 4789e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (FnData->AllocTy == StrDupLike) { 4799827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes APInt Size(IntTyBits, GetStringLength(CS.getArgument(0))); 4809827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes if (!Size) 4819827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes return unknown(); 4829827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes 4839827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes // strndup limits strlen 4849827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes if (FnData->FstParam > 0) { 4859827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes ConstantInt *Arg= dyn_cast<ConstantInt>(CS.getArgument(FnData->FstParam)); 4869827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes if (!Arg) 4879827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes return unknown(); 4889827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes 4899827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes APInt MaxSize = Arg->getValue().zextOrSelf(IntTyBits); 4909827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes if (Size.ugt(MaxSize)) 4919827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes Size = MaxSize + 1; 4929827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes } 4939827c8e1c96950d17a4dbb7ef9d9036501c40c1bNuno Lopes return std::make_pair(Size, Zero); 4949e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } 4959e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 4969e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes ConstantInt *Arg = dyn_cast<ConstantInt>(CS.getArgument(FnData->FstParam)); 4979e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!Arg) 4989e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 4999e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 500034dd6c6a118cf78ebfa6bf3496cd5b0df578a9eNuno Lopes APInt Size = Arg->getValue().zextOrSelf(IntTyBits); 5019e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // size determined by just 1 parameter 502ef22f04bad6f5037fd4cc4d144e0c418f6cb2edcNuno Lopes if (FnData->SndParam < 0) 5039e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(Size, Zero); 5049e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5059e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Arg = dyn_cast<ConstantInt>(CS.getArgument(FnData->SndParam)); 5069e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!Arg) 5079e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 5089e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 509034dd6c6a118cf78ebfa6bf3496cd5b0df578a9eNuno Lopes Size *= Arg->getValue().zextOrSelf(IntTyBits); 5109e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(Size, Zero); 5119e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5129e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // TODO: handle more standard functions (+ wchar cousins): 5136e699bf38dd862331532bd6f74ec491bdfad5db9Nuno Lopes // - strdup / strndup 5149e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // - strcpy / strncpy 5159e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // - strcat / strncat 5169e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // - memcpy / memmove 5176e699bf38dd862331532bd6f74ec491bdfad5db9Nuno Lopes // - strcat / strncat 5189e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // - memset 5199e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 5209e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5219e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType 5229e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesObjectSizeOffsetVisitor::visitConstantPointerNull(ConstantPointerNull&) { 5239e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(Zero, Zero); 5249e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 5259e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5269e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType 52741a3f251346681e21171879dce409b2e6a3ba750Nuno LopesObjectSizeOffsetVisitor::visitExtractElementInst(ExtractElementInst&) { 52841a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes return unknown(); 52941a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes} 53041a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes 53141a3f251346681e21171879dce409b2e6a3ba750Nuno LopesSizeOffsetType 5329e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesObjectSizeOffsetVisitor::visitExtractValueInst(ExtractValueInst&) { 5339e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // Easy cases were already folded by previous passes. 5349e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 5359e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 5369e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5379e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType ObjectSizeOffsetVisitor::visitGEPOperator(GEPOperator &GEP) { 5389e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizeOffsetType PtrData = compute(GEP.getPointerOperand()); 53998281a20503896349bd152e2dfe87435d3a6aadaNuno Lopes APInt Offset(IntTyBits, 0); 540cee51c48030f37133ad4004d3e5c14d8ebfc91c4Matt Arsenault if (!bothKnown(PtrData) || !GEP.accumulateConstantOffset(*DL, Offset)) 5419e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 5429e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5439e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(PtrData.first, PtrData.second + Offset); 5449e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 5459e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 54641be2fb1f9e9b8f796effb81c2bee6cf397136cfNuno LopesSizeOffsetType ObjectSizeOffsetVisitor::visitGlobalAlias(GlobalAlias &GA) { 54741be2fb1f9e9b8f796effb81c2bee6cf397136cfNuno Lopes if (GA.mayBeOverridden()) 54841be2fb1f9e9b8f796effb81c2bee6cf397136cfNuno Lopes return unknown(); 54941be2fb1f9e9b8f796effb81c2bee6cf397136cfNuno Lopes return compute(GA.getAliasee()); 55041be2fb1f9e9b8f796effb81c2bee6cf397136cfNuno Lopes} 55141be2fb1f9e9b8f796effb81c2bee6cf397136cfNuno Lopes 5529e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType ObjectSizeOffsetVisitor::visitGlobalVariable(GlobalVariable &GV){ 5539e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!GV.hasDefinitiveInitializer()) 5549e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 5559e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 556cee51c48030f37133ad4004d3e5c14d8ebfc91c4Matt Arsenault APInt Size(IntTyBits, DL->getTypeAllocSize(GV.getType()->getElementType())); 5579e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(align(Size, GV.getAlignment()), Zero); 5589e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 5599e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5609e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType ObjectSizeOffsetVisitor::visitIntToPtrInst(IntToPtrInst&) { 5619e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // clueless 5629e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 5639e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 5649e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5659e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType ObjectSizeOffsetVisitor::visitLoadInst(LoadInst&) { 5669e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes ++ObjectVisitorLoad; 5679e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 5689e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 5699e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5708e4df489d0e02e0fbdd00ed829e70e5f21998162Nadav RotemSizeOffsetType ObjectSizeOffsetVisitor::visitPHINode(PHINode&) { 5718e4df489d0e02e0fbdd00ed829e70e5f21998162Nadav Rotem // too complex to analyze statically. 5728e4df489d0e02e0fbdd00ed829e70e5f21998162Nadav Rotem return unknown(); 5739e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 5749e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5759e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType ObjectSizeOffsetVisitor::visitSelectInst(SelectInst &I) { 5769e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizeOffsetType TrueSide = compute(I.getTrueValue()); 5779e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizeOffsetType FalseSide = compute(I.getFalseValue()); 5782e594fa85c809178ce598a9b4c3a3bf5e0e6a14eNuno Lopes if (bothKnown(TrueSide) && bothKnown(FalseSide) && TrueSide == FalseSide) 5799e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return TrueSide; 5809e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 5819e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 5829e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5839e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType ObjectSizeOffsetVisitor::visitUndefValue(UndefValue&) { 5849e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(Zero, Zero); 5859e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 5869e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 5879e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetType ObjectSizeOffsetVisitor::visitInstruction(Instruction &I) { 5889e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes DEBUG(dbgs() << "ObjectSizeOffsetVisitor unknown instruction:" << I << '\n'); 5899e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 5909e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 5919e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 592cee51c48030f37133ad4004d3e5c14d8ebfc91c4Matt ArsenaultObjectSizeOffsetEvaluator::ObjectSizeOffsetEvaluator(const DataLayout *DL, 593cee51c48030f37133ad4004d3e5c14d8ebfc91c4Matt Arsenault const TargetLibraryInfo *TLI, 5945e1d0d39db5fefe013f58c124a94694f96bce2f1Nuno Lopes LLVMContext &Context, 5955e1d0d39db5fefe013f58c124a94694f96bce2f1Nuno Lopes bool RoundToAlign) 5965e1d0d39db5fefe013f58c124a94694f96bce2f1Nuno Lopes: DL(DL), TLI(TLI), Context(Context), Builder(Context, TargetFolder(DL)), 5975e1d0d39db5fefe013f58c124a94694f96bce2f1Nuno Lopes RoundToAlign(RoundToAlign) { 59836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // IntTy and Zero must be set for each compute() since the address space may 59936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // be different for later objects. 6009e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 6019e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6029e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetEvalType ObjectSizeOffsetEvaluator::compute(Value *V) { 60336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // XXX - Are vectors of pointers possible here? 60436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines IntTy = cast<IntegerType>(DL->getIntPtrType(V->getType())); 60536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Zero = ConstantInt::get(IntTy, 0); 60636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 6079e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizeOffsetEvalType Result = compute_(V); 6089e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6099e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!bothKnown(Result)) { 6109e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // erase everything that was computed in this iteration from the cache, so 6119e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // that no dangling references are left behind. We could be a bit smarter if 6129e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // we kept a dependency graph. It's probably not worth the complexity. 6139e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes for (PtrSetTy::iterator I=SeenVals.begin(), E=SeenVals.end(); I != E; ++I) { 6149e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes CacheMapTy::iterator CacheIt = CacheMap.find(*I); 6159e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // non-computable results can be safely cached 6169e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (CacheIt != CacheMap.end() && anyKnown(CacheIt->second)) 6179e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes CacheMap.erase(CacheIt); 6189e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } 6199e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } 6209e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6219e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SeenVals.clear(); 6229e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return Result; 6239e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 6249e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6259e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetEvalType ObjectSizeOffsetEvaluator::compute_(Value *V) { 6265e1d0d39db5fefe013f58c124a94694f96bce2f1Nuno Lopes ObjectSizeOffsetVisitor Visitor(DL, TLI, Context, RoundToAlign); 6279e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizeOffsetType Const = Visitor.compute(V); 6289e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (Visitor.bothKnown(Const)) 6299e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(ConstantInt::get(Context, Const.first), 6309e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes ConstantInt::get(Context, Const.second)); 6319e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6329e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes V = V->stripPointerCasts(); 6339e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6349e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // check cache 6359e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes CacheMapTy::iterator CacheIt = CacheMap.find(V); 6369e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (CacheIt != CacheMap.end()) 6379e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return CacheIt->second; 6389e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6399e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // always generate code immediately before the instruction being 6409e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // processed, so that the generated code dominates the same BBs 6419e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Instruction *PrevInsertPoint = Builder.GetInsertPoint(); 6429e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (Instruction *I = dyn_cast<Instruction>(V)) 6439e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Builder.SetInsertPoint(I); 6449e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6459e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // now compute the size and offset 6469e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizeOffsetEvalType Result; 6472f0843321016091dca890c819741e06f11ceb390Benjamin Kramer 6482f0843321016091dca890c819741e06f11ceb390Benjamin Kramer // Record the pointers that were handled in this run, so that they can be 6492f0843321016091dca890c819741e06f11ceb390Benjamin Kramer // cleaned later if something fails. We also use this set to break cycles that 6502f0843321016091dca890c819741e06f11ceb390Benjamin Kramer // can occur in dead code. 6512f0843321016091dca890c819741e06f11ceb390Benjamin Kramer if (!SeenVals.insert(V)) { 6522f0843321016091dca890c819741e06f11ceb390Benjamin Kramer Result = unknown(); 6532f0843321016091dca890c819741e06f11ceb390Benjamin Kramer } else if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { 6549e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Result = visitGEPOperator(*GEP); 6559e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } else if (Instruction *I = dyn_cast<Instruction>(V)) { 6569e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Result = visit(*I); 6579e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } else if (isa<Argument>(V) || 6589e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes (isa<ConstantExpr>(V) && 6599e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes cast<ConstantExpr>(V)->getOpcode() == Instruction::IntToPtr) || 66041be2fb1f9e9b8f796effb81c2bee6cf397136cfNuno Lopes isa<GlobalAlias>(V) || 6619e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes isa<GlobalVariable>(V)) { 6629e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // ignore values where we cannot do more than what ObjectSizeVisitor can 6639e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Result = unknown(); 6649e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } else { 6659e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes DEBUG(dbgs() << "ObjectSizeOffsetEvaluator::compute() unhandled value: " 6669e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes << *V << '\n'); 6679e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Result = unknown(); 6689e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } 6699e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6709e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (PrevInsertPoint) 6719e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Builder.SetInsertPoint(PrevInsertPoint); 6729e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6739e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // Don't reuse CacheIt since it may be invalid at this point. 6749e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes CacheMap[V] = Result; 6759e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return Result; 6769e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 6779e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6789e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetEvalType ObjectSizeOffsetEvaluator::visitAllocaInst(AllocaInst &I) { 6799e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!I.getAllocatedType()->isSized()) 6809e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 6819e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6829e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // must be a VLA 6839e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes assert(I.isArrayAllocation()); 6849e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Value *ArraySize = I.getArraySize(); 6859e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Value *Size = ConstantInt::get(ArraySize->getType(), 686cee51c48030f37133ad4004d3e5c14d8ebfc91c4Matt Arsenault DL->getTypeAllocSize(I.getAllocatedType())); 6879e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Size = Builder.CreateMul(Size, ArraySize); 6889e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(Size, Zero); 6899e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 6909e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6919e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetEvalType ObjectSizeOffsetEvaluator::visitCallSite(CallSite CS) { 6928e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer const AllocFnsTy *FnData = getAllocationData(CS.getInstruction(), AnyAlloc, 6938e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer TLI); 6949e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!FnData) 6959e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 6969e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 6979e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // handle strdup-like functions separately 6989e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (FnData->AllocTy == StrDupLike) { 6996e699bf38dd862331532bd6f74ec491bdfad5db9Nuno Lopes // TODO 7006e699bf38dd862331532bd6f74ec491bdfad5db9Nuno Lopes return unknown(); 7019e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } 7029e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 703034dd6c6a118cf78ebfa6bf3496cd5b0df578a9eNuno Lopes Value *FirstArg = CS.getArgument(FnData->FstParam); 704034dd6c6a118cf78ebfa6bf3496cd5b0df578a9eNuno Lopes FirstArg = Builder.CreateZExt(FirstArg, IntTy); 705ef22f04bad6f5037fd4cc4d144e0c418f6cb2edcNuno Lopes if (FnData->SndParam < 0) 7069e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(FirstArg, Zero); 7079e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 7089e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Value *SecondArg = CS.getArgument(FnData->SndParam); 709034dd6c6a118cf78ebfa6bf3496cd5b0df578a9eNuno Lopes SecondArg = Builder.CreateZExt(SecondArg, IntTy); 7109e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Value *Size = Builder.CreateMul(FirstArg, SecondArg); 7119e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(Size, Zero); 7129e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 7139e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // TODO: handle more standard functions (+ wchar cousins): 7146e699bf38dd862331532bd6f74ec491bdfad5db9Nuno Lopes // - strdup / strndup 7159e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // - strcpy / strncpy 7169e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // - strcat / strncat 7179e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // - memcpy / memmove 7186e699bf38dd862331532bd6f74ec491bdfad5db9Nuno Lopes // - strcat / strncat 7199e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // - memset 7209e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 7219e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 7229e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetEvalType 72341a3f251346681e21171879dce409b2e6a3ba750Nuno LopesObjectSizeOffsetEvaluator::visitExtractElementInst(ExtractElementInst&) { 72441a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes return unknown(); 72541a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes} 72641a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes 72741a3f251346681e21171879dce409b2e6a3ba750Nuno LopesSizeOffsetEvalType 72841a3f251346681e21171879dce409b2e6a3ba750Nuno LopesObjectSizeOffsetEvaluator::visitExtractValueInst(ExtractValueInst&) { 72941a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes return unknown(); 73041a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes} 73141a3f251346681e21171879dce409b2e6a3ba750Nuno Lopes 73241a3f251346681e21171879dce409b2e6a3ba750Nuno LopesSizeOffsetEvalType 7339e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesObjectSizeOffsetEvaluator::visitGEPOperator(GEPOperator &GEP) { 7349e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizeOffsetEvalType PtrData = compute_(GEP.getPointerOperand()); 7359e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!bothKnown(PtrData)) 7369e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 7379e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 738cee51c48030f37133ad4004d3e5c14d8ebfc91c4Matt Arsenault Value *Offset = EmitGEPOffset(&Builder, *DL, &GEP, /*NoAssumptions=*/true); 7399e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Offset = Builder.CreateAdd(PtrData.second, Offset); 7409e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(PtrData.first, Offset); 7419e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 7429e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 7439e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetEvalType ObjectSizeOffsetEvaluator::visitIntToPtrInst(IntToPtrInst&) { 7449e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // clueless 7459e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 7469e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 7479e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 7489e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetEvalType ObjectSizeOffsetEvaluator::visitLoadInst(LoadInst&) { 7499e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 7509e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 7519e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 7529e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetEvalType ObjectSizeOffsetEvaluator::visitPHINode(PHINode &PHI) { 7539e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // create 2 PHIs: one for size and another for offset 7549e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes PHINode *SizePHI = Builder.CreatePHI(IntTy, PHI.getNumIncomingValues()); 7559e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes PHINode *OffsetPHI = Builder.CreatePHI(IntTy, PHI.getNumIncomingValues()); 7569e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 7579e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // insert right away in the cache to handle recursive PHIs 7589e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes CacheMap[&PHI] = std::make_pair(SizePHI, OffsetPHI); 7599e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 7609e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes // compute offset/size for each PHI incoming pointer 7619e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes for (unsigned i = 0, e = PHI.getNumIncomingValues(); i != e; ++i) { 7629e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Builder.SetInsertPoint(PHI.getIncomingBlock(i)->getFirstInsertionPt()); 7639e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizeOffsetEvalType EdgeData = compute_(PHI.getIncomingValue(i)); 7649e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 7659e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!bothKnown(EdgeData)) { 7669e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes OffsetPHI->replaceAllUsesWith(UndefValue::get(IntTy)); 7679e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes OffsetPHI->eraseFromParent(); 7689e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizePHI->replaceAllUsesWith(UndefValue::get(IntTy)); 7699e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizePHI->eraseFromParent(); 7709e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 7719e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } 7729e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizePHI->addIncoming(EdgeData.first, PHI.getIncomingBlock(i)); 7739e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes OffsetPHI->addIncoming(EdgeData.second, PHI.getIncomingBlock(i)); 7749e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes } 7750dff532fce434c3e9fdf9695aed8efeb5f752ed5Nuno Lopes 7760dff532fce434c3e9fdf9695aed8efeb5f752ed5Nuno Lopes Value *Size = SizePHI, *Offset = OffsetPHI, *Tmp; 7770dff532fce434c3e9fdf9695aed8efeb5f752ed5Nuno Lopes if ((Tmp = SizePHI->hasConstantValue())) { 7780dff532fce434c3e9fdf9695aed8efeb5f752ed5Nuno Lopes Size = Tmp; 7790dff532fce434c3e9fdf9695aed8efeb5f752ed5Nuno Lopes SizePHI->replaceAllUsesWith(Size); 7800dff532fce434c3e9fdf9695aed8efeb5f752ed5Nuno Lopes SizePHI->eraseFromParent(); 7810dff532fce434c3e9fdf9695aed8efeb5f752ed5Nuno Lopes } 7820dff532fce434c3e9fdf9695aed8efeb5f752ed5Nuno Lopes if ((Tmp = OffsetPHI->hasConstantValue())) { 7830dff532fce434c3e9fdf9695aed8efeb5f752ed5Nuno Lopes Offset = Tmp; 7840dff532fce434c3e9fdf9695aed8efeb5f752ed5Nuno Lopes OffsetPHI->replaceAllUsesWith(Offset); 7850dff532fce434c3e9fdf9695aed8efeb5f752ed5Nuno Lopes OffsetPHI->eraseFromParent(); 7860dff532fce434c3e9fdf9695aed8efeb5f752ed5Nuno Lopes } 7870dff532fce434c3e9fdf9695aed8efeb5f752ed5Nuno Lopes return std::make_pair(Size, Offset); 7889e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 7899e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 7909e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetEvalType ObjectSizeOffsetEvaluator::visitSelectInst(SelectInst &I) { 7919e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizeOffsetEvalType TrueSide = compute_(I.getTrueValue()); 7929e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes SizeOffsetEvalType FalseSide = compute_(I.getFalseValue()); 7939e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 7949e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (!bothKnown(TrueSide) || !bothKnown(FalseSide)) 7959e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 7969e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (TrueSide == FalseSide) 7979e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return TrueSide; 7989e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 7999e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Value *Size = Builder.CreateSelect(I.getCondition(), TrueSide.first, 8009e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes FalseSide.first); 8019e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes Value *Offset = Builder.CreateSelect(I.getCondition(), TrueSide.second, 8029e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes FalseSide.second); 8039e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return std::make_pair(Size, Offset); 8049e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 8059e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 8069e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno LopesSizeOffsetEvalType ObjectSizeOffsetEvaluator::visitInstruction(Instruction &I) { 8079e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes DEBUG(dbgs() << "ObjectSizeOffsetEvaluator unknown instruction:" << I <<'\n'); 8089e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return unknown(); 8099e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 810