blob: 64d339f564d75766862761a50941e5a1099c8d2b [file] [log] [blame]
Victor Hernandezf390e042009-10-27 20:05:49 +00001//===------ MemoryBuiltins.cpp - Identify calls to memory builtins --------===//
Evan Cheng1d9d4bd2009-09-10 04:36:43 +00002//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
Victor Hernandezf390e042009-10-27 20:05:49 +000010// This family of functions identifies calls to builtin functions that allocate
Michael Ilsemand9745242013-03-08 21:03:09 +000011// or free memory.
Evan Cheng1d9d4bd2009-09-10 04:36:43 +000012//
13//===----------------------------------------------------------------------===//
14
Victor Hernandezf390e042009-10-27 20:05:49 +000015#include "llvm/Analysis/MemoryBuiltins.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000016#include "llvm/ADT/STLExtras.h"
17#include "llvm/ADT/Statistic.h"
18#include "llvm/Analysis/ValueTracking.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000019#include "llvm/IR/DataLayout.h"
20#include "llvm/IR/GlobalVariable.h"
21#include "llvm/IR/Instructions.h"
22#include "llvm/IR/Intrinsics.h"
23#include "llvm/IR/Metadata.h"
24#include "llvm/IR/Module.h"
Nuno Lopes55fff832012-06-21 15:45:28 +000025#include "llvm/Support/Debug.h"
26#include "llvm/Support/MathExtras.h"
27#include "llvm/Support/raw_ostream.h"
Benjamin Kramer8bcc9712012-08-29 15:32:21 +000028#include "llvm/Target/TargetLibraryInfo.h"
Nuno Lopes55fff832012-06-21 15:45:28 +000029#include "llvm/Transforms/Utils/Local.h"
Evan Cheng1d9d4bd2009-09-10 04:36:43 +000030using namespace llvm;
31
Chandler Carruthf1221bd2014-04-22 02:48:03 +000032#define DEBUG_TYPE "memory-builtins"
33
Nuno Lopes55fff832012-06-21 15:45:28 +000034enum AllocType {
Benjamin Kramer2939dd32013-09-24 17:34:29 +000035 OpNewLike = 1<<0, // allocates; never returns null
36 MallocLike = 1<<1 | OpNewLike, // allocates; may return null
37 CallocLike = 1<<2, // allocates + bzero
38 ReallocLike = 1<<3, // reallocates
39 StrDupLike = 1<<4,
40 AllocLike = MallocLike | CallocLike | StrDupLike,
Benjamin Kramer4d4df042013-09-24 17:15:14 +000041 AnyAlloc = AllocLike | ReallocLike
Nuno Lopes55fff832012-06-21 15:45:28 +000042};
Evan Cheng1d9d4bd2009-09-10 04:36:43 +000043
Nuno Lopes55fff832012-06-21 15:45:28 +000044struct AllocFnsTy {
Benjamin Kramer8bcc9712012-08-29 15:32:21 +000045 LibFunc::Func Func;
Nuno Lopes55fff832012-06-21 15:45:28 +000046 AllocType AllocTy;
47 unsigned char NumParams;
48 // First and Second size parameters (or -1 if unused)
Nuno Lopesf06b7312012-06-21 18:38:26 +000049 signed char FstParam, SndParam;
Nuno Lopes55fff832012-06-21 15:45:28 +000050};
Evan Cheng1d9d4bd2009-09-10 04:36:43 +000051
Nuno Lopes181d67e2012-06-28 16:34:03 +000052// FIXME: certain users need more information. E.g., SimplifyLibCalls needs to
53// know which functions are nounwind, noalias, nocapture parameters, etc.
Nuno Lopes55fff832012-06-21 15:45:28 +000054static const AllocFnsTy AllocationFnData[] = {
Benjamin Kramer8bcc9712012-08-29 15:32:21 +000055 {LibFunc::malloc, MallocLike, 1, 0, -1},
56 {LibFunc::valloc, MallocLike, 1, 0, -1},
Benjamin Kramerfd4777c2013-09-24 16:37:51 +000057 {LibFunc::Znwj, OpNewLike, 1, 0, -1}, // new(unsigned int)
Nadav Rotem7b7585d2013-04-09 04:43:46 +000058 {LibFunc::ZnwjRKSt9nothrow_t, MallocLike, 2, 0, -1}, // new(unsigned int, nothrow)
Benjamin Kramerfd4777c2013-09-24 16:37:51 +000059 {LibFunc::Znwm, OpNewLike, 1, 0, -1}, // new(unsigned long)
Nadav Rotem7b7585d2013-04-09 04:43:46 +000060 {LibFunc::ZnwmRKSt9nothrow_t, MallocLike, 2, 0, -1}, // new(unsigned long, nothrow)
Benjamin Kramerfd4777c2013-09-24 16:37:51 +000061 {LibFunc::Znaj, OpNewLike, 1, 0, -1}, // new[](unsigned int)
Nadav Rotem7b7585d2013-04-09 04:43:46 +000062 {LibFunc::ZnajRKSt9nothrow_t, MallocLike, 2, 0, -1}, // new[](unsigned int, nothrow)
Benjamin Kramerfd4777c2013-09-24 16:37:51 +000063 {LibFunc::Znam, OpNewLike, 1, 0, -1}, // new[](unsigned long)
Nadav Rotem7b7585d2013-04-09 04:43:46 +000064 {LibFunc::ZnamRKSt9nothrow_t, MallocLike, 2, 0, -1}, // new[](unsigned long, nothrow)
Benjamin Kramer8bcc9712012-08-29 15:32:21 +000065 {LibFunc::calloc, CallocLike, 2, 0, 1},
66 {LibFunc::realloc, ReallocLike, 2, 1, -1},
67 {LibFunc::reallocf, ReallocLike, 2, 1, -1},
68 {LibFunc::strdup, StrDupLike, 1, -1, -1},
69 {LibFunc::strndup, StrDupLike, 2, 1, -1}
Benjamin Kramer01df8172013-09-24 17:49:08 +000070 // TODO: Handle "int posix_memalign(void **, size_t, size_t)"
Nuno Lopes55fff832012-06-21 15:45:28 +000071};
72
73
74static Function *getCalledFunction(const Value *V, bool LookThroughBitCast) {
75 if (LookThroughBitCast)
76 V = V->stripPointerCasts();
Nuno Lopesdc6085e2012-06-21 21:25:05 +000077
Nuno Lopes15dbcb42012-06-22 15:50:53 +000078 CallSite CS(const_cast<Value*>(V));
79 if (!CS.getInstruction())
Craig Topper9f008862014-04-15 04:59:12 +000080 return nullptr;
Evan Cheng1d9d4bd2009-09-10 04:36:43 +000081
Michael Gottesman41748d72013-06-27 00:25:01 +000082 if (CS.isNoBuiltin())
Craig Topper9f008862014-04-15 04:59:12 +000083 return nullptr;
Richard Smithe04f0d32013-05-16 04:12:04 +000084
Nuno Lopesdc6085e2012-06-21 21:25:05 +000085 Function *Callee = CS.getCalledFunction();
Nuno Lopes55fff832012-06-21 15:45:28 +000086 if (!Callee || !Callee->isDeclaration())
Craig Topper9f008862014-04-15 04:59:12 +000087 return nullptr;
Nuno Lopes55fff832012-06-21 15:45:28 +000088 return Callee;
89}
Evan Cheng1d9d4bd2009-09-10 04:36:43 +000090
Nuno Lopes55fff832012-06-21 15:45:28 +000091/// \brief Returns the allocation data for the given value if it is a call to a
92/// known allocation function, and NULL otherwise.
93static const AllocFnsTy *getAllocationData(const Value *V, AllocType AllocTy,
Benjamin Kramer8bcc9712012-08-29 15:32:21 +000094 const TargetLibraryInfo *TLI,
Nuno Lopes55fff832012-06-21 15:45:28 +000095 bool LookThroughBitCast = false) {
Michael Ilseman74ffc272013-03-08 21:15:00 +000096 // Skip intrinsics
97 if (isa<IntrinsicInst>(V))
Craig Topper9f008862014-04-15 04:59:12 +000098 return nullptr;
Michael Ilseman74ffc272013-03-08 21:15:00 +000099
Nuno Lopes55fff832012-06-21 15:45:28 +0000100 Function *Callee = getCalledFunction(V, LookThroughBitCast);
101 if (!Callee)
Craig Topper9f008862014-04-15 04:59:12 +0000102 return nullptr;
Nuno Lopes55fff832012-06-21 15:45:28 +0000103
Benjamin Kramer8bcc9712012-08-29 15:32:21 +0000104 // Make sure that the function is available.
105 StringRef FnName = Callee->getName();
106 LibFunc::Func TLIFn;
107 if (!TLI || !TLI->getLibFunc(FnName, TLIFn) || !TLI->has(TLIFn))
Craig Topper9f008862014-04-15 04:59:12 +0000108 return nullptr;
Benjamin Kramer8bcc9712012-08-29 15:32:21 +0000109
Nuno Lopes55fff832012-06-21 15:45:28 +0000110 unsigned i = 0;
111 bool found = false;
112 for ( ; i < array_lengthof(AllocationFnData); ++i) {
Benjamin Kramer8bcc9712012-08-29 15:32:21 +0000113 if (AllocationFnData[i].Func == TLIFn) {
Nuno Lopes55fff832012-06-21 15:45:28 +0000114 found = true;
115 break;
116 }
117 }
118 if (!found)
Craig Topper9f008862014-04-15 04:59:12 +0000119 return nullptr;
Nuno Lopes55fff832012-06-21 15:45:28 +0000120
121 const AllocFnsTy *FnData = &AllocationFnData[i];
Benjamin Kramer2939dd32013-09-24 17:34:29 +0000122 if ((FnData->AllocTy & AllocTy) != FnData->AllocTy)
Craig Topper9f008862014-04-15 04:59:12 +0000123 return nullptr;
Nuno Lopes55fff832012-06-21 15:45:28 +0000124
125 // Check function prototype.
Nuno Lopesf06b7312012-06-21 18:38:26 +0000126 int FstParam = FnData->FstParam;
127 int SndParam = FnData->SndParam;
Chris Lattner229907c2011-07-18 04:54:35 +0000128 FunctionType *FTy = Callee->getFunctionType();
Nuno Lopes55fff832012-06-21 15:45:28 +0000129
130 if (FTy->getReturnType() == Type::getInt8PtrTy(FTy->getContext()) &&
131 FTy->getNumParams() == FnData->NumParams &&
Nuno Lopesf06b7312012-06-21 18:38:26 +0000132 (FstParam < 0 ||
Nuno Lopes55fff832012-06-21 15:45:28 +0000133 (FTy->getParamType(FstParam)->isIntegerTy(32) ||
134 FTy->getParamType(FstParam)->isIntegerTy(64))) &&
Nuno Lopesf06b7312012-06-21 18:38:26 +0000135 (SndParam < 0 ||
Nuno Lopes55fff832012-06-21 15:45:28 +0000136 FTy->getParamType(SndParam)->isIntegerTy(32) ||
137 FTy->getParamType(SndParam)->isIntegerTy(64)))
138 return FnData;
Craig Topper9f008862014-04-15 04:59:12 +0000139 return nullptr;
Nuno Lopes55fff832012-06-21 15:45:28 +0000140}
141
142static bool hasNoAliasAttr(const Value *V, bool LookThroughBitCast) {
Nuno Lopes9ecc8762012-06-25 16:17:54 +0000143 ImmutableCallSite CS(LookThroughBitCast ? V->stripPointerCasts() : V);
Bill Wendling3d7b0b82012-12-19 07:18:57 +0000144 return CS && CS.hasFnAttr(Attribute::NoAlias);
Nuno Lopes55fff832012-06-21 15:45:28 +0000145}
146
147
Nuno Lopesdc6085e2012-06-21 21:25:05 +0000148/// \brief Tests if a value is a call or invoke to a library function that
149/// allocates or reallocates memory (either malloc, calloc, realloc, or strdup
150/// like).
Benjamin Kramer8bcc9712012-08-29 15:32:21 +0000151bool llvm::isAllocationFn(const Value *V, const TargetLibraryInfo *TLI,
152 bool LookThroughBitCast) {
153 return getAllocationData(V, AnyAlloc, TLI, LookThroughBitCast);
Nuno Lopes55fff832012-06-21 15:45:28 +0000154}
155
Nuno Lopesdc6085e2012-06-21 21:25:05 +0000156/// \brief Tests if a value is a call or invoke to a function that returns a
Nuno Lopes181d67e2012-06-28 16:34:03 +0000157/// NoAlias pointer (including malloc/calloc/realloc/strdup-like functions).
Benjamin Kramer8bcc9712012-08-29 15:32:21 +0000158bool llvm::isNoAliasFn(const Value *V, const TargetLibraryInfo *TLI,
159 bool LookThroughBitCast) {
Nuno Lopes181d67e2012-06-28 16:34:03 +0000160 // it's safe to consider realloc as noalias since accessing the original
161 // pointer is undefined behavior
Benjamin Kramer8bcc9712012-08-29 15:32:21 +0000162 return isAllocationFn(V, TLI, LookThroughBitCast) ||
Nuno Lopes55fff832012-06-21 15:45:28 +0000163 hasNoAliasAttr(V, LookThroughBitCast);
164}
165
Nuno Lopesdc6085e2012-06-21 21:25:05 +0000166/// \brief Tests if a value is a call or invoke to a library function that
167/// allocates uninitialized memory (such as malloc).
Benjamin Kramer8bcc9712012-08-29 15:32:21 +0000168bool llvm::isMallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
169 bool LookThroughBitCast) {
170 return getAllocationData(V, MallocLike, TLI, LookThroughBitCast);
Nuno Lopes55fff832012-06-21 15:45:28 +0000171}
172
Nuno Lopesdc6085e2012-06-21 21:25:05 +0000173/// \brief Tests if a value is a call or invoke to a library function that
174/// allocates zero-filled memory (such as calloc).
Benjamin Kramer8bcc9712012-08-29 15:32:21 +0000175bool llvm::isCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
176 bool LookThroughBitCast) {
177 return getAllocationData(V, CallocLike, TLI, LookThroughBitCast);
Nuno Lopes55fff832012-06-21 15:45:28 +0000178}
179
Nuno Lopesdc6085e2012-06-21 21:25:05 +0000180/// \brief Tests if a value is a call or invoke to a library function that
181/// allocates memory (either malloc, calloc, or strdup like).
Benjamin Kramer8bcc9712012-08-29 15:32:21 +0000182bool llvm::isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
183 bool LookThroughBitCast) {
184 return getAllocationData(V, AllocLike, TLI, LookThroughBitCast);
Nuno Lopes55fff832012-06-21 15:45:28 +0000185}
186
Nuno Lopesdc6085e2012-06-21 21:25:05 +0000187/// \brief Tests if a value is a call or invoke to a library function that
188/// reallocates memory (such as realloc).
Benjamin Kramer8bcc9712012-08-29 15:32:21 +0000189bool llvm::isReallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
190 bool LookThroughBitCast) {
191 return getAllocationData(V, ReallocLike, TLI, LookThroughBitCast);
Evan Cheng1d9d4bd2009-09-10 04:36:43 +0000192}
193
Benjamin Kramerfd4777c2013-09-24 16:37:51 +0000194/// \brief Tests if a value is a call or invoke to a library function that
195/// allocates memory and never returns null (such as operator new).
196bool llvm::isOperatorNewLikeFn(const Value *V, const TargetLibraryInfo *TLI,
197 bool LookThroughBitCast) {
198 return getAllocationData(V, OpNewLike, TLI, LookThroughBitCast);
199}
200
Evan Cheng1d9d4bd2009-09-10 04:36:43 +0000201/// extractMallocCall - Returns the corresponding CallInst if the instruction
202/// is a malloc call. Since CallInst::CreateMalloc() only creates calls, we
203/// ignore InvokeInst here.
Benjamin Kramer8bcc9712012-08-29 15:32:21 +0000204const CallInst *llvm::extractMallocCall(const Value *I,
205 const TargetLibraryInfo *TLI) {
Craig Topper9f008862014-04-15 04:59:12 +0000206 return isMallocLikeFn(I, TLI) ? dyn_cast<CallInst>(I) : nullptr;
Evan Cheng1d9d4bd2009-09-10 04:36:43 +0000207}
208
Matt Arsenault40dddd72013-10-03 19:50:01 +0000209static Value *computeArraySize(const CallInst *CI, const DataLayout *DL,
Benjamin Kramer8bcc9712012-08-29 15:32:21 +0000210 const TargetLibraryInfo *TLI,
Victor Hernandezfcc77b12009-11-10 08:32:25 +0000211 bool LookThroughSExt = false) {
Evan Cheng1d9d4bd2009-09-10 04:36:43 +0000212 if (!CI)
Craig Topper9f008862014-04-15 04:59:12 +0000213 return nullptr;
Evan Cheng1d9d4bd2009-09-10 04:36:43 +0000214
Victor Hernandezf3db9152009-11-07 00:16:28 +0000215 // The size of the malloc's result type must be known to determine array size.
Benjamin Kramer8bcc9712012-08-29 15:32:21 +0000216 Type *T = getMallocAllocatedType(CI, TLI);
Matt Arsenault40dddd72013-10-03 19:50:01 +0000217 if (!T || !T->isSized() || !DL)
Craig Topper9f008862014-04-15 04:59:12 +0000218 return nullptr;
Victor Hernandez788eaab2009-09-18 19:20:02 +0000219
Matt Arsenault40dddd72013-10-03 19:50:01 +0000220 unsigned ElementSize = DL->getTypeAllocSize(T);
Chris Lattner229907c2011-07-18 04:54:35 +0000221 if (StructType *ST = dyn_cast<StructType>(T))
Matt Arsenault40dddd72013-10-03 19:50:01 +0000222 ElementSize = DL->getStructLayout(ST)->getSizeInBytes();
Victor Hernandez788eaab2009-09-18 19:20:02 +0000223
Gabor Greifad7884a2010-06-23 21:41:47 +0000224 // If malloc call's arg can be determined to be a multiple of ElementSize,
Victor Hernandezfcc77b12009-11-10 08:32:25 +0000225 // return the multiple. Otherwise, return NULL.
Gabor Greifad7884a2010-06-23 21:41:47 +0000226 Value *MallocArg = CI->getArgOperand(0);
Craig Topper9f008862014-04-15 04:59:12 +0000227 Value *Multiple = nullptr;
Victor Hernandezfcc77b12009-11-10 08:32:25 +0000228 if (ComputeMultiple(MallocArg, ElementSize, Multiple,
Dan Gohman6a976bb2009-11-18 00:58:27 +0000229 LookThroughSExt))
Victor Hernandezfcc77b12009-11-10 08:32:25 +0000230 return Multiple;
Victor Hernandez788eaab2009-09-18 19:20:02 +0000231
Craig Topper9f008862014-04-15 04:59:12 +0000232 return nullptr;
Evan Cheng1d9d4bd2009-09-10 04:36:43 +0000233}
234
Michael Ilsemand9745242013-03-08 21:03:09 +0000235/// isArrayMalloc - Returns the corresponding CallInst if the instruction
Victor Hernandez0d025422009-10-28 20:18:55 +0000236/// is a call to malloc whose array size can be determined and the array size
237/// is not constant 1. Otherwise, return NULL.
Benjamin Kramer8bcc9712012-08-29 15:32:21 +0000238const CallInst *llvm::isArrayMalloc(const Value *I,
Matt Arsenault40dddd72013-10-03 19:50:01 +0000239 const DataLayout *DL,
Benjamin Kramer8bcc9712012-08-29 15:32:21 +0000240 const TargetLibraryInfo *TLI) {
241 const CallInst *CI = extractMallocCall(I, TLI);
Matt Arsenault40dddd72013-10-03 19:50:01 +0000242 Value *ArraySize = computeArraySize(CI, DL, TLI);
Victor Hernandez0d025422009-10-28 20:18:55 +0000243
Jakub Staszakafe60c12013-03-07 20:22:39 +0000244 if (ConstantInt *ConstSize = dyn_cast_or_null<ConstantInt>(ArraySize))
245 if (ConstSize->isOne())
246 return CI;
Victor Hernandez0d025422009-10-28 20:18:55 +0000247
248 // CI is a non-array malloc or we can't figure out that it is an array malloc.
Craig Topper9f008862014-04-15 04:59:12 +0000249 return nullptr;
Evan Cheng1d9d4bd2009-09-10 04:36:43 +0000250}
251
252/// getMallocType - Returns the PointerType resulting from the malloc call.
Victor Hernandezf3db9152009-11-07 00:16:28 +0000253/// The PointerType depends on the number of bitcast uses of the malloc call:
254/// 0: PointerType is the calls' return type.
255/// 1: PointerType is the bitcast's result type.
256/// >1: Unique PointerType cannot be determined, return NULL.
Benjamin Kramer8bcc9712012-08-29 15:32:21 +0000257PointerType *llvm::getMallocType(const CallInst *CI,
258 const TargetLibraryInfo *TLI) {
259 assert(isMallocLikeFn(CI, TLI) && "getMallocType and not malloc call");
Michael Ilsemand9745242013-03-08 21:03:09 +0000260
Craig Topper9f008862014-04-15 04:59:12 +0000261 PointerType *MallocType = nullptr;
Victor Hernandezf3db9152009-11-07 00:16:28 +0000262 unsigned NumOfBitCastUses = 0;
263
Victor Hernandez788eaab2009-09-18 19:20:02 +0000264 // Determine if CallInst has a bitcast use.
Chandler Carruthcdf47882014-03-09 03:16:01 +0000265 for (Value::const_user_iterator UI = CI->user_begin(), E = CI->user_end();
266 UI != E;)
Victor Hernandezf3db9152009-11-07 00:16:28 +0000267 if (const BitCastInst *BCI = dyn_cast<BitCastInst>(*UI++)) {
268 MallocType = cast<PointerType>(BCI->getDestTy());
269 NumOfBitCastUses++;
270 }
Evan Cheng1d9d4bd2009-09-10 04:36:43 +0000271
Victor Hernandezf3db9152009-11-07 00:16:28 +0000272 // Malloc call has 1 bitcast use, so type is the bitcast's destination type.
273 if (NumOfBitCastUses == 1)
274 return MallocType;
Evan Cheng1d9d4bd2009-09-10 04:36:43 +0000275
Victor Hernandezddc2ce42009-09-22 18:50:03 +0000276 // Malloc call was not bitcast, so type is the malloc function's return type.
Victor Hernandezf3db9152009-11-07 00:16:28 +0000277 if (NumOfBitCastUses == 0)
Victor Hernandez788eaab2009-09-18 19:20:02 +0000278 return cast<PointerType>(CI->getType());
279
280 // Type could not be determined.
Craig Topper9f008862014-04-15 04:59:12 +0000281 return nullptr;
Evan Cheng1d9d4bd2009-09-10 04:36:43 +0000282}
283
Victor Hernandezf3db9152009-11-07 00:16:28 +0000284/// getMallocAllocatedType - Returns the Type allocated by malloc call.
285/// The Type depends on the number of bitcast uses of the malloc call:
286/// 0: PointerType is the malloc calls' return type.
287/// 1: PointerType is the bitcast's result type.
288/// >1: Unique PointerType cannot be determined, return NULL.
Benjamin Kramer8bcc9712012-08-29 15:32:21 +0000289Type *llvm::getMallocAllocatedType(const CallInst *CI,
290 const TargetLibraryInfo *TLI) {
291 PointerType *PT = getMallocType(CI, TLI);
Craig Topper9f008862014-04-15 04:59:12 +0000292 return PT ? PT->getElementType() : nullptr;
Evan Cheng1d9d4bd2009-09-10 04:36:43 +0000293}
294
Michael Ilsemand9745242013-03-08 21:03:09 +0000295/// getMallocArraySize - Returns the array size of a malloc call. If the
Victor Hernandez0d025422009-10-28 20:18:55 +0000296/// argument passed to malloc is a multiple of the size of the malloced type,
297/// then return that multiple. For non-array mallocs, the multiple is
298/// constant 1. Otherwise, return NULL for mallocs whose array size cannot be
Victor Hernandez13020b12009-10-15 20:14:52 +0000299/// determined.
Matt Arsenault40dddd72013-10-03 19:50:01 +0000300Value *llvm::getMallocArraySize(CallInst *CI, const DataLayout *DL,
Benjamin Kramer8bcc9712012-08-29 15:32:21 +0000301 const TargetLibraryInfo *TLI,
Victor Hernandezfcc77b12009-11-10 08:32:25 +0000302 bool LookThroughSExt) {
Benjamin Kramer8bcc9712012-08-29 15:32:21 +0000303 assert(isMallocLikeFn(CI, TLI) && "getMallocArraySize and not malloc call");
Matt Arsenault40dddd72013-10-03 19:50:01 +0000304 return computeArraySize(CI, DL, TLI, LookThroughSExt);
Evan Cheng1d9d4bd2009-09-10 04:36:43 +0000305}
Victor Hernandeze2971492009-10-24 04:23:03 +0000306
Nuno Lopesd2b71e72012-05-03 21:19:58 +0000307
Nuno Lopesd2b71e72012-05-03 21:19:58 +0000308/// extractCallocCall - Returns the corresponding CallInst if the instruction
309/// is a calloc call.
Benjamin Kramer8bcc9712012-08-29 15:32:21 +0000310const CallInst *llvm::extractCallocCall(const Value *I,
311 const TargetLibraryInfo *TLI) {
Craig Topper9f008862014-04-15 04:59:12 +0000312 return isCallocLikeFn(I, TLI) ? cast<CallInst>(I) : nullptr;
Nuno Lopesd2b71e72012-05-03 21:19:58 +0000313}
314
Victor Hernandezde5ad422009-10-26 23:43:48 +0000315
Gabor Greif5f5a8642010-06-23 21:51:12 +0000316/// isFreeCall - Returns non-null if the value is a call to the builtin free()
Benjamin Kramer8bcc9712012-08-29 15:32:21 +0000317const CallInst *llvm::isFreeCall(const Value *I, const TargetLibraryInfo *TLI) {
Victor Hernandeze2971492009-10-24 04:23:03 +0000318 const CallInst *CI = dyn_cast<CallInst>(I);
Michael Ilseman74ffc272013-03-08 21:15:00 +0000319 if (!CI || isa<IntrinsicInst>(CI))
Craig Topper9f008862014-04-15 04:59:12 +0000320 return nullptr;
Victor Hernandez33188582009-11-03 20:39:35 +0000321 Function *Callee = CI->getCalledFunction();
Craig Topper9f008862014-04-15 04:59:12 +0000322 if (Callee == nullptr || !Callee->isDeclaration())
323 return nullptr;
Nick Lewyckyc1f86582011-03-15 07:31:32 +0000324
Benjamin Kramer8bcc9712012-08-29 15:32:21 +0000325 StringRef FnName = Callee->getName();
326 LibFunc::Func TLIFn;
327 if (!TLI || !TLI->getLibFunc(FnName, TLIFn) || !TLI->has(TLIFn))
Craig Topper9f008862014-04-15 04:59:12 +0000328 return nullptr;
Benjamin Kramer8bcc9712012-08-29 15:32:21 +0000329
Richard Smith70523c72013-07-21 23:11:42 +0000330 unsigned ExpectedNumParams;
331 if (TLIFn == LibFunc::free ||
332 TLIFn == LibFunc::ZdlPv || // operator delete(void*)
333 TLIFn == LibFunc::ZdaPv) // operator delete[](void*)
334 ExpectedNumParams = 1;
335 else if (TLIFn == LibFunc::ZdlPvRKSt9nothrow_t || // delete(void*, nothrow)
336 TLIFn == LibFunc::ZdaPvRKSt9nothrow_t) // delete[](void*, nothrow)
337 ExpectedNumParams = 2;
338 else
Craig Topper9f008862014-04-15 04:59:12 +0000339 return nullptr;
Victor Hernandeze2971492009-10-24 04:23:03 +0000340
341 // Check free prototype.
Michael Ilsemand9745242013-03-08 21:03:09 +0000342 // FIXME: workaround for PR5130, this will be obsolete when a nobuiltin
Victor Hernandeze2971492009-10-24 04:23:03 +0000343 // attribute will exist.
Chris Lattner229907c2011-07-18 04:54:35 +0000344 FunctionType *FTy = Callee->getFunctionType();
Victor Hernandez33188582009-11-03 20:39:35 +0000345 if (!FTy->getReturnType()->isVoidTy())
Craig Topper9f008862014-04-15 04:59:12 +0000346 return nullptr;
Richard Smith70523c72013-07-21 23:11:42 +0000347 if (FTy->getNumParams() != ExpectedNumParams)
Craig Topper9f008862014-04-15 04:59:12 +0000348 return nullptr;
Chris Lattner67733f62011-06-18 21:46:23 +0000349 if (FTy->getParamType(0) != Type::getInt8PtrTy(Callee->getContext()))
Craig Topper9f008862014-04-15 04:59:12 +0000350 return nullptr;
Victor Hernandeze2971492009-10-24 04:23:03 +0000351
Gabor Greif5f5a8642010-06-23 21:51:12 +0000352 return CI;
Victor Hernandeze2971492009-10-24 04:23:03 +0000353}
Nuno Lopes55fff832012-06-21 15:45:28 +0000354
355
356
357//===----------------------------------------------------------------------===//
358// Utility functions to compute size of objects.
359//
360
361
362/// \brief Compute the size of the object pointed by Ptr. Returns true and the
363/// object size in Size if successful, and false otherwise.
364/// If RoundToAlign is true, then Size is rounded up to the aligment of allocas,
365/// byval arguments, and global variables.
Matt Arsenault40dddd72013-10-03 19:50:01 +0000366bool llvm::getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout *DL,
Benjamin Kramer8bcc9712012-08-29 15:32:21 +0000367 const TargetLibraryInfo *TLI, bool RoundToAlign) {
Matt Arsenault40dddd72013-10-03 19:50:01 +0000368 if (!DL)
Nuno Lopes55fff832012-06-21 15:45:28 +0000369 return false;
370
Matt Arsenault40dddd72013-10-03 19:50:01 +0000371 ObjectSizeOffsetVisitor Visitor(DL, TLI, Ptr->getContext(), RoundToAlign);
Nuno Lopes55fff832012-06-21 15:45:28 +0000372 SizeOffsetType Data = Visitor.compute(const_cast<Value*>(Ptr));
373 if (!Visitor.bothKnown(Data))
374 return false;
375
376 APInt ObjSize = Data.first, Offset = Data.second;
377 // check for overflow
378 if (Offset.slt(0) || ObjSize.ult(Offset))
379 Size = 0;
380 else
381 Size = (ObjSize - Offset).getZExtValue();
382 return true;
383}
384
385
386STATISTIC(ObjectVisitorArgument,
387 "Number of arguments with unsolved size and offset");
388STATISTIC(ObjectVisitorLoad,
389 "Number of load instructions with unsolved size and offset");
390
391
392APInt ObjectSizeOffsetVisitor::align(APInt Size, uint64_t Align) {
393 if (RoundToAlign && Align)
394 return APInt(IntTyBits, RoundUpToAlignment(Size.getZExtValue(), Align));
395 return Size;
396}
397
Matt Arsenault40dddd72013-10-03 19:50:01 +0000398ObjectSizeOffsetVisitor::ObjectSizeOffsetVisitor(const DataLayout *DL,
Benjamin Kramer8bcc9712012-08-29 15:32:21 +0000399 const TargetLibraryInfo *TLI,
Nuno Lopes55fff832012-06-21 15:45:28 +0000400 LLVMContext &Context,
Chandler Carruth7ec50852012-11-01 08:07:29 +0000401 bool RoundToAlign)
Matt Arsenault40dddd72013-10-03 19:50:01 +0000402: DL(DL), TLI(TLI), RoundToAlign(RoundToAlign) {
Matt Arsenaultd3ee7af2013-12-14 00:27:48 +0000403 // Pointer size must be rechecked for each object visited since it could have
404 // a different address space.
Nuno Lopes55fff832012-06-21 15:45:28 +0000405}
406
407SizeOffsetType ObjectSizeOffsetVisitor::compute(Value *V) {
Matt Arsenaultd3ee7af2013-12-14 00:27:48 +0000408 IntTyBits = DL->getPointerTypeSizeInBits(V->getType());
409 Zero = APInt::getNullValue(IntTyBits);
410
Nuno Lopes55fff832012-06-21 15:45:28 +0000411 V = V->stripPointerCasts();
Nadav Rotemabcc64f2013-04-09 18:16:05 +0000412 if (Instruction *I = dyn_cast<Instruction>(V)) {
413 // If we have already seen this instruction, bail out. Cycles can happen in
414 // unreachable code after constant propagation.
415 if (!SeenInsts.insert(I))
416 return unknown();
Nuno Lopesd896a402012-12-31 20:45:10 +0000417
Benjamin Kramer34764fe2012-08-17 19:26:41 +0000418 if (GEPOperator *GEP = dyn_cast<GEPOperator>(V))
Nadav Rotemabcc64f2013-04-09 18:16:05 +0000419 return visitGEPOperator(*GEP);
420 return visit(*I);
Benjamin Kramer34764fe2012-08-17 19:26:41 +0000421 }
Nuno Lopes55fff832012-06-21 15:45:28 +0000422 if (Argument *A = dyn_cast<Argument>(V))
423 return visitArgument(*A);
424 if (ConstantPointerNull *P = dyn_cast<ConstantPointerNull>(V))
425 return visitConstantPointerNull(*P);
Nuno Lopese9d6dbf2012-12-31 16:23:48 +0000426 if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V))
427 return visitGlobalAlias(*GA);
Nuno Lopes55fff832012-06-21 15:45:28 +0000428 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
429 return visitGlobalVariable(*GV);
430 if (UndefValue *UV = dyn_cast<UndefValue>(V))
431 return visitUndefValue(*UV);
Benjamin Kramer34764fe2012-08-17 19:26:41 +0000432 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
Nuno Lopes55fff832012-06-21 15:45:28 +0000433 if (CE->getOpcode() == Instruction::IntToPtr)
434 return unknown(); // clueless
Nadav Rotemabcc64f2013-04-09 18:16:05 +0000435 if (CE->getOpcode() == Instruction::GetElementPtr)
436 return visitGEPOperator(cast<GEPOperator>(*CE));
Benjamin Kramer34764fe2012-08-17 19:26:41 +0000437 }
Nuno Lopes55fff832012-06-21 15:45:28 +0000438
439 DEBUG(dbgs() << "ObjectSizeOffsetVisitor::compute() unhandled value: " << *V
440 << '\n');
441 return unknown();
442}
443
444SizeOffsetType ObjectSizeOffsetVisitor::visitAllocaInst(AllocaInst &I) {
445 if (!I.getAllocatedType()->isSized())
446 return unknown();
447
Matt Arsenault40dddd72013-10-03 19:50:01 +0000448 APInt Size(IntTyBits, DL->getTypeAllocSize(I.getAllocatedType()));
Nuno Lopes55fff832012-06-21 15:45:28 +0000449 if (!I.isArrayAllocation())
450 return std::make_pair(align(Size, I.getAlignment()), Zero);
451
452 Value *ArraySize = I.getArraySize();
453 if (const ConstantInt *C = dyn_cast<ConstantInt>(ArraySize)) {
454 Size *= C->getValue().zextOrSelf(IntTyBits);
455 return std::make_pair(align(Size, I.getAlignment()), Zero);
456 }
457 return unknown();
458}
459
460SizeOffsetType ObjectSizeOffsetVisitor::visitArgument(Argument &A) {
461 // no interprocedural analysis is done at the moment
Reid Kleckner26af2ca2014-01-28 02:38:36 +0000462 if (!A.hasByValOrInAllocaAttr()) {
Nuno Lopes55fff832012-06-21 15:45:28 +0000463 ++ObjectVisitorArgument;
464 return unknown();
465 }
466 PointerType *PT = cast<PointerType>(A.getType());
Matt Arsenault40dddd72013-10-03 19:50:01 +0000467 APInt Size(IntTyBits, DL->getTypeAllocSize(PT->getElementType()));
Nuno Lopes55fff832012-06-21 15:45:28 +0000468 return std::make_pair(align(Size, A.getParamAlignment()), Zero);
469}
470
471SizeOffsetType ObjectSizeOffsetVisitor::visitCallSite(CallSite CS) {
Benjamin Kramer8bcc9712012-08-29 15:32:21 +0000472 const AllocFnsTy *FnData = getAllocationData(CS.getInstruction(), AnyAlloc,
473 TLI);
Nuno Lopes55fff832012-06-21 15:45:28 +0000474 if (!FnData)
475 return unknown();
476
477 // handle strdup-like functions separately
478 if (FnData->AllocTy == StrDupLike) {
Nuno Lopes2a4b09c2012-07-24 16:28:13 +0000479 APInt Size(IntTyBits, GetStringLength(CS.getArgument(0)));
480 if (!Size)
481 return unknown();
482
483 // strndup limits strlen
484 if (FnData->FstParam > 0) {
485 ConstantInt *Arg= dyn_cast<ConstantInt>(CS.getArgument(FnData->FstParam));
486 if (!Arg)
487 return unknown();
488
489 APInt MaxSize = Arg->getValue().zextOrSelf(IntTyBits);
490 if (Size.ugt(MaxSize))
491 Size = MaxSize + 1;
492 }
493 return std::make_pair(Size, Zero);
Nuno Lopes55fff832012-06-21 15:45:28 +0000494 }
495
496 ConstantInt *Arg = dyn_cast<ConstantInt>(CS.getArgument(FnData->FstParam));
497 if (!Arg)
498 return unknown();
499
Nuno Lopesa6aa3d32012-06-21 16:47:58 +0000500 APInt Size = Arg->getValue().zextOrSelf(IntTyBits);
Nuno Lopes55fff832012-06-21 15:45:28 +0000501 // size determined by just 1 parameter
Nuno Lopesf06b7312012-06-21 18:38:26 +0000502 if (FnData->SndParam < 0)
Nuno Lopes55fff832012-06-21 15:45:28 +0000503 return std::make_pair(Size, Zero);
504
505 Arg = dyn_cast<ConstantInt>(CS.getArgument(FnData->SndParam));
506 if (!Arg)
507 return unknown();
508
Nuno Lopesa6aa3d32012-06-21 16:47:58 +0000509 Size *= Arg->getValue().zextOrSelf(IntTyBits);
Nuno Lopes55fff832012-06-21 15:45:28 +0000510 return std::make_pair(Size, Zero);
511
512 // TODO: handle more standard functions (+ wchar cousins):
Nuno Lopesf0626f22012-07-25 18:49:28 +0000513 // - strdup / strndup
Nuno Lopes55fff832012-06-21 15:45:28 +0000514 // - strcpy / strncpy
515 // - strcat / strncat
516 // - memcpy / memmove
Nuno Lopesf0626f22012-07-25 18:49:28 +0000517 // - strcat / strncat
Nuno Lopes55fff832012-06-21 15:45:28 +0000518 // - memset
519}
520
521SizeOffsetType
522ObjectSizeOffsetVisitor::visitConstantPointerNull(ConstantPointerNull&) {
523 return std::make_pair(Zero, Zero);
524}
525
526SizeOffsetType
Nuno Lopes181d67e2012-06-28 16:34:03 +0000527ObjectSizeOffsetVisitor::visitExtractElementInst(ExtractElementInst&) {
528 return unknown();
529}
530
531SizeOffsetType
Nuno Lopes55fff832012-06-21 15:45:28 +0000532ObjectSizeOffsetVisitor::visitExtractValueInst(ExtractValueInst&) {
533 // Easy cases were already folded by previous passes.
534 return unknown();
535}
536
537SizeOffsetType ObjectSizeOffsetVisitor::visitGEPOperator(GEPOperator &GEP) {
538 SizeOffsetType PtrData = compute(GEP.getPointerOperand());
Nuno Lopesb6ad9822012-12-30 16:25:48 +0000539 APInt Offset(IntTyBits, 0);
Matt Arsenault40dddd72013-10-03 19:50:01 +0000540 if (!bothKnown(PtrData) || !GEP.accumulateConstantOffset(*DL, Offset))
Nuno Lopes55fff832012-06-21 15:45:28 +0000541 return unknown();
542
Nuno Lopes55fff832012-06-21 15:45:28 +0000543 return std::make_pair(PtrData.first, PtrData.second + Offset);
544}
545
Nuno Lopese9d6dbf2012-12-31 16:23:48 +0000546SizeOffsetType ObjectSizeOffsetVisitor::visitGlobalAlias(GlobalAlias &GA) {
547 if (GA.mayBeOverridden())
548 return unknown();
549 return compute(GA.getAliasee());
550}
551
Nuno Lopes55fff832012-06-21 15:45:28 +0000552SizeOffsetType ObjectSizeOffsetVisitor::visitGlobalVariable(GlobalVariable &GV){
553 if (!GV.hasDefinitiveInitializer())
554 return unknown();
555
Matt Arsenault40dddd72013-10-03 19:50:01 +0000556 APInt Size(IntTyBits, DL->getTypeAllocSize(GV.getType()->getElementType()));
Nuno Lopes55fff832012-06-21 15:45:28 +0000557 return std::make_pair(align(Size, GV.getAlignment()), Zero);
558}
559
560SizeOffsetType ObjectSizeOffsetVisitor::visitIntToPtrInst(IntToPtrInst&) {
561 // clueless
562 return unknown();
563}
564
565SizeOffsetType ObjectSizeOffsetVisitor::visitLoadInst(LoadInst&) {
566 ++ObjectVisitorLoad;
567 return unknown();
568}
569
Nadav Rotemabcc64f2013-04-09 18:16:05 +0000570SizeOffsetType ObjectSizeOffsetVisitor::visitPHINode(PHINode&) {
571 // too complex to analyze statically.
572 return unknown();
Nuno Lopes55fff832012-06-21 15:45:28 +0000573}
574
575SizeOffsetType ObjectSizeOffsetVisitor::visitSelectInst(SelectInst &I) {
576 SizeOffsetType TrueSide = compute(I.getTrueValue());
577 SizeOffsetType FalseSide = compute(I.getFalseValue());
Nuno Lopes4b47f822012-12-31 18:01:36 +0000578 if (bothKnown(TrueSide) && bothKnown(FalseSide) && TrueSide == FalseSide)
Nuno Lopes55fff832012-06-21 15:45:28 +0000579 return TrueSide;
580 return unknown();
581}
582
583SizeOffsetType ObjectSizeOffsetVisitor::visitUndefValue(UndefValue&) {
584 return std::make_pair(Zero, Zero);
585}
586
587SizeOffsetType ObjectSizeOffsetVisitor::visitInstruction(Instruction &I) {
588 DEBUG(dbgs() << "ObjectSizeOffsetVisitor unknown instruction:" << I << '\n');
589 return unknown();
590}
591
Matt Arsenault40dddd72013-10-03 19:50:01 +0000592ObjectSizeOffsetEvaluator::ObjectSizeOffsetEvaluator(const DataLayout *DL,
593 const TargetLibraryInfo *TLI,
Nuno Lopes340b0462013-10-24 09:17:24 +0000594 LLVMContext &Context,
595 bool RoundToAlign)
596: DL(DL), TLI(TLI), Context(Context), Builder(Context, TargetFolder(DL)),
597 RoundToAlign(RoundToAlign) {
Matt Arsenaultd3ee7af2013-12-14 00:27:48 +0000598 // IntTy and Zero must be set for each compute() since the address space may
599 // be different for later objects.
Nuno Lopes55fff832012-06-21 15:45:28 +0000600}
601
602SizeOffsetEvalType ObjectSizeOffsetEvaluator::compute(Value *V) {
Matt Arsenaultd3ee7af2013-12-14 00:27:48 +0000603 // XXX - Are vectors of pointers possible here?
604 IntTy = cast<IntegerType>(DL->getIntPtrType(V->getType()));
605 Zero = ConstantInt::get(IntTy, 0);
606
Nuno Lopes55fff832012-06-21 15:45:28 +0000607 SizeOffsetEvalType Result = compute_(V);
608
609 if (!bothKnown(Result)) {
610 // erase everything that was computed in this iteration from the cache, so
611 // that no dangling references are left behind. We could be a bit smarter if
612 // we kept a dependency graph. It's probably not worth the complexity.
613 for (PtrSetTy::iterator I=SeenVals.begin(), E=SeenVals.end(); I != E; ++I) {
614 CacheMapTy::iterator CacheIt = CacheMap.find(*I);
615 // non-computable results can be safely cached
616 if (CacheIt != CacheMap.end() && anyKnown(CacheIt->second))
617 CacheMap.erase(CacheIt);
618 }
619 }
620
621 SeenVals.clear();
622 return Result;
623}
624
625SizeOffsetEvalType ObjectSizeOffsetEvaluator::compute_(Value *V) {
Nuno Lopes340b0462013-10-24 09:17:24 +0000626 ObjectSizeOffsetVisitor Visitor(DL, TLI, Context, RoundToAlign);
Nuno Lopes55fff832012-06-21 15:45:28 +0000627 SizeOffsetType Const = Visitor.compute(V);
628 if (Visitor.bothKnown(Const))
629 return std::make_pair(ConstantInt::get(Context, Const.first),
630 ConstantInt::get(Context, Const.second));
631
632 V = V->stripPointerCasts();
633
634 // check cache
635 CacheMapTy::iterator CacheIt = CacheMap.find(V);
636 if (CacheIt != CacheMap.end())
637 return CacheIt->second;
638
639 // always generate code immediately before the instruction being
640 // processed, so that the generated code dominates the same BBs
641 Instruction *PrevInsertPoint = Builder.GetInsertPoint();
642 if (Instruction *I = dyn_cast<Instruction>(V))
643 Builder.SetInsertPoint(I);
644
Nuno Lopes55fff832012-06-21 15:45:28 +0000645 // now compute the size and offset
646 SizeOffsetEvalType Result;
Benjamin Kramer155c9d52013-09-29 19:39:13 +0000647
648 // Record the pointers that were handled in this run, so that they can be
649 // cleaned later if something fails. We also use this set to break cycles that
650 // can occur in dead code.
651 if (!SeenVals.insert(V)) {
652 Result = unknown();
653 } else if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
Nuno Lopes55fff832012-06-21 15:45:28 +0000654 Result = visitGEPOperator(*GEP);
655 } else if (Instruction *I = dyn_cast<Instruction>(V)) {
656 Result = visit(*I);
657 } else if (isa<Argument>(V) ||
658 (isa<ConstantExpr>(V) &&
659 cast<ConstantExpr>(V)->getOpcode() == Instruction::IntToPtr) ||
Nuno Lopese9d6dbf2012-12-31 16:23:48 +0000660 isa<GlobalAlias>(V) ||
Nuno Lopes55fff832012-06-21 15:45:28 +0000661 isa<GlobalVariable>(V)) {
662 // ignore values where we cannot do more than what ObjectSizeVisitor can
663 Result = unknown();
664 } else {
665 DEBUG(dbgs() << "ObjectSizeOffsetEvaluator::compute() unhandled value: "
666 << *V << '\n');
667 Result = unknown();
668 }
669
670 if (PrevInsertPoint)
671 Builder.SetInsertPoint(PrevInsertPoint);
672
673 // Don't reuse CacheIt since it may be invalid at this point.
674 CacheMap[V] = Result;
675 return Result;
676}
677
678SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitAllocaInst(AllocaInst &I) {
679 if (!I.getAllocatedType()->isSized())
680 return unknown();
681
682 // must be a VLA
683 assert(I.isArrayAllocation());
684 Value *ArraySize = I.getArraySize();
685 Value *Size = ConstantInt::get(ArraySize->getType(),
Matt Arsenault40dddd72013-10-03 19:50:01 +0000686 DL->getTypeAllocSize(I.getAllocatedType()));
Nuno Lopes55fff832012-06-21 15:45:28 +0000687 Size = Builder.CreateMul(Size, ArraySize);
688 return std::make_pair(Size, Zero);
689}
690
691SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitCallSite(CallSite CS) {
Benjamin Kramer8bcc9712012-08-29 15:32:21 +0000692 const AllocFnsTy *FnData = getAllocationData(CS.getInstruction(), AnyAlloc,
693 TLI);
Nuno Lopes55fff832012-06-21 15:45:28 +0000694 if (!FnData)
695 return unknown();
696
697 // handle strdup-like functions separately
698 if (FnData->AllocTy == StrDupLike) {
Nuno Lopesf0626f22012-07-25 18:49:28 +0000699 // TODO
700 return unknown();
Nuno Lopes55fff832012-06-21 15:45:28 +0000701 }
702
Nuno Lopesa6aa3d32012-06-21 16:47:58 +0000703 Value *FirstArg = CS.getArgument(FnData->FstParam);
704 FirstArg = Builder.CreateZExt(FirstArg, IntTy);
Nuno Lopesf06b7312012-06-21 18:38:26 +0000705 if (FnData->SndParam < 0)
Nuno Lopes55fff832012-06-21 15:45:28 +0000706 return std::make_pair(FirstArg, Zero);
707
708 Value *SecondArg = CS.getArgument(FnData->SndParam);
Nuno Lopesa6aa3d32012-06-21 16:47:58 +0000709 SecondArg = Builder.CreateZExt(SecondArg, IntTy);
Nuno Lopes55fff832012-06-21 15:45:28 +0000710 Value *Size = Builder.CreateMul(FirstArg, SecondArg);
711 return std::make_pair(Size, Zero);
712
713 // TODO: handle more standard functions (+ wchar cousins):
Nuno Lopesf0626f22012-07-25 18:49:28 +0000714 // - strdup / strndup
Nuno Lopes55fff832012-06-21 15:45:28 +0000715 // - strcpy / strncpy
716 // - strcat / strncat
717 // - memcpy / memmove
Nuno Lopesf0626f22012-07-25 18:49:28 +0000718 // - strcat / strncat
Nuno Lopes55fff832012-06-21 15:45:28 +0000719 // - memset
720}
721
722SizeOffsetEvalType
Nuno Lopes181d67e2012-06-28 16:34:03 +0000723ObjectSizeOffsetEvaluator::visitExtractElementInst(ExtractElementInst&) {
724 return unknown();
725}
726
727SizeOffsetEvalType
728ObjectSizeOffsetEvaluator::visitExtractValueInst(ExtractValueInst&) {
729 return unknown();
730}
731
732SizeOffsetEvalType
Nuno Lopes55fff832012-06-21 15:45:28 +0000733ObjectSizeOffsetEvaluator::visitGEPOperator(GEPOperator &GEP) {
734 SizeOffsetEvalType PtrData = compute_(GEP.getPointerOperand());
735 if (!bothKnown(PtrData))
736 return unknown();
737
Matt Arsenault40dddd72013-10-03 19:50:01 +0000738 Value *Offset = EmitGEPOffset(&Builder, *DL, &GEP, /*NoAssumptions=*/true);
Nuno Lopes55fff832012-06-21 15:45:28 +0000739 Offset = Builder.CreateAdd(PtrData.second, Offset);
740 return std::make_pair(PtrData.first, Offset);
741}
742
743SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitIntToPtrInst(IntToPtrInst&) {
744 // clueless
745 return unknown();
746}
747
748SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitLoadInst(LoadInst&) {
749 return unknown();
750}
751
752SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitPHINode(PHINode &PHI) {
753 // create 2 PHIs: one for size and another for offset
754 PHINode *SizePHI = Builder.CreatePHI(IntTy, PHI.getNumIncomingValues());
755 PHINode *OffsetPHI = Builder.CreatePHI(IntTy, PHI.getNumIncomingValues());
756
757 // insert right away in the cache to handle recursive PHIs
758 CacheMap[&PHI] = std::make_pair(SizePHI, OffsetPHI);
759
760 // compute offset/size for each PHI incoming pointer
761 for (unsigned i = 0, e = PHI.getNumIncomingValues(); i != e; ++i) {
762 Builder.SetInsertPoint(PHI.getIncomingBlock(i)->getFirstInsertionPt());
763 SizeOffsetEvalType EdgeData = compute_(PHI.getIncomingValue(i));
764
765 if (!bothKnown(EdgeData)) {
766 OffsetPHI->replaceAllUsesWith(UndefValue::get(IntTy));
767 OffsetPHI->eraseFromParent();
768 SizePHI->replaceAllUsesWith(UndefValue::get(IntTy));
769 SizePHI->eraseFromParent();
770 return unknown();
771 }
772 SizePHI->addIncoming(EdgeData.first, PHI.getIncomingBlock(i));
773 OffsetPHI->addIncoming(EdgeData.second, PHI.getIncomingBlock(i));
774 }
Nuno Lopes9291ff42012-07-03 17:13:25 +0000775
776 Value *Size = SizePHI, *Offset = OffsetPHI, *Tmp;
777 if ((Tmp = SizePHI->hasConstantValue())) {
778 Size = Tmp;
779 SizePHI->replaceAllUsesWith(Size);
780 SizePHI->eraseFromParent();
781 }
782 if ((Tmp = OffsetPHI->hasConstantValue())) {
783 Offset = Tmp;
784 OffsetPHI->replaceAllUsesWith(Offset);
785 OffsetPHI->eraseFromParent();
786 }
787 return std::make_pair(Size, Offset);
Nuno Lopes55fff832012-06-21 15:45:28 +0000788}
789
790SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitSelectInst(SelectInst &I) {
791 SizeOffsetEvalType TrueSide = compute_(I.getTrueValue());
792 SizeOffsetEvalType FalseSide = compute_(I.getFalseValue());
793
794 if (!bothKnown(TrueSide) || !bothKnown(FalseSide))
795 return unknown();
796 if (TrueSide == FalseSide)
797 return TrueSide;
798
799 Value *Size = Builder.CreateSelect(I.getCondition(), TrueSide.first,
800 FalseSide.first);
801 Value *Offset = Builder.CreateSelect(I.getCondition(), TrueSide.second,
802 FalseSide.second);
803 return std::make_pair(Size, Offset);
804}
805
806SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitInstruction(Instruction &I) {
807 DEBUG(dbgs() << "ObjectSizeOffsetEvaluator unknown instruction:" << I <<'\n');
808 return unknown();
809}