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