Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Analysis/MemoryBuiltins.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- MemoryBuiltins.cpp - Identify calls to memory builtins -------------===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
// This family of functions identifies calls to builtin functions that allocate
10
// or free memory.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "llvm/Analysis/MemoryBuiltins.h"
15
#include "llvm/ADT/APInt.h"
16
#include "llvm/ADT/None.h"
17
#include "llvm/ADT/Optional.h"
18
#include "llvm/ADT/STLExtras.h"
19
#include "llvm/ADT/Statistic.h"
20
#include "llvm/ADT/StringRef.h"
21
#include "llvm/Analysis/TargetFolder.h"
22
#include "llvm/Analysis/TargetLibraryInfo.h"
23
#include "llvm/Analysis/Utils/Local.h"
24
#include "llvm/Analysis/ValueTracking.h"
25
#include "llvm/IR/Argument.h"
26
#include "llvm/IR/Attributes.h"
27
#include "llvm/IR/Constants.h"
28
#include "llvm/IR/DataLayout.h"
29
#include "llvm/IR/DerivedTypes.h"
30
#include "llvm/IR/Function.h"
31
#include "llvm/IR/GlobalAlias.h"
32
#include "llvm/IR/GlobalVariable.h"
33
#include "llvm/IR/Instruction.h"
34
#include "llvm/IR/Instructions.h"
35
#include "llvm/IR/IntrinsicInst.h"
36
#include "llvm/IR/Operator.h"
37
#include "llvm/IR/Type.h"
38
#include "llvm/IR/Value.h"
39
#include "llvm/Support/Casting.h"
40
#include "llvm/Support/Debug.h"
41
#include "llvm/Support/MathExtras.h"
42
#include "llvm/Support/raw_ostream.h"
43
#include <cassert>
44
#include <cstdint>
45
#include <iterator>
46
#include <utility>
47
48
using namespace llvm;
49
50
#define DEBUG_TYPE "memory-builtins"
51
52
enum AllocType : uint8_t {
53
  OpNewLike          = 1<<0, // allocates; never returns null
54
  MallocLike         = 1<<1 | OpNewLike, // allocates; may return null
55
  CallocLike         = 1<<2, // allocates + bzero
56
  ReallocLike        = 1<<3, // reallocates
57
  StrDupLike         = 1<<4,
58
  MallocOrCallocLike = MallocLike | CallocLike,
59
  AllocLike          = MallocLike | CallocLike | StrDupLike,
60
  AnyAlloc           = AllocLike | ReallocLike
61
};
62
63
struct AllocFnsTy {
64
  AllocType AllocTy;
65
  unsigned NumParams;
66
  // First and Second size parameters (or -1 if unused)
67
  int FstParam, SndParam;
68
};
69
70
// FIXME: certain users need more information. E.g., SimplifyLibCalls needs to
71
// know which functions are nounwind, noalias, nocapture parameters, etc.
72
static const std::pair<LibFunc, AllocFnsTy> AllocationFnData[] = {
73
  {LibFunc_malloc,              {MallocLike,  1, 0,  -1}},
74
  {LibFunc_valloc,              {MallocLike,  1, 0,  -1}},
75
  {LibFunc_Znwj,                {OpNewLike,   1, 0,  -1}}, // new(unsigned int)
76
  {LibFunc_ZnwjRKSt9nothrow_t,  {MallocLike,  2, 0,  -1}}, // new(unsigned int, nothrow)
77
  {LibFunc_ZnwjSt11align_val_t, {OpNewLike,   2, 0,  -1}}, // new(unsigned int, align_val_t)
78
  {LibFunc_ZnwjSt11align_val_tRKSt9nothrow_t, // new(unsigned int, align_val_t, nothrow)
79
                                {MallocLike,  3, 0,  -1}},
80
  {LibFunc_Znwm,                {OpNewLike,   1, 0,  -1}}, // new(unsigned long)
81
  {LibFunc_ZnwmRKSt9nothrow_t,  {MallocLike,  2, 0,  -1}}, // new(unsigned long, nothrow)
82
  {LibFunc_ZnwmSt11align_val_t, {OpNewLike,   2, 0,  -1}}, // new(unsigned long, align_val_t)
83
  {LibFunc_ZnwmSt11align_val_tRKSt9nothrow_t, // new(unsigned long, align_val_t, nothrow)
84
                                {MallocLike,  3, 0,  -1}},
85
  {LibFunc_Znaj,                {OpNewLike,   1, 0,  -1}}, // new[](unsigned int)
86
  {LibFunc_ZnajRKSt9nothrow_t,  {MallocLike,  2, 0,  -1}}, // new[](unsigned int, nothrow)
87
  {LibFunc_ZnajSt11align_val_t, {OpNewLike,   2, 0,  -1}}, // new[](unsigned int, align_val_t)
88
  {LibFunc_ZnajSt11align_val_tRKSt9nothrow_t, // new[](unsigned int, align_val_t, nothrow)
89
                                {MallocLike,  3, 0,  -1}},
90
  {LibFunc_Znam,                {OpNewLike,   1, 0,  -1}}, // new[](unsigned long)
91
  {LibFunc_ZnamRKSt9nothrow_t,  {MallocLike,  2, 0,  -1}}, // new[](unsigned long, nothrow)
92
  {LibFunc_ZnamSt11align_val_t, {OpNewLike,   2, 0,  -1}}, // new[](unsigned long, align_val_t)
93
  {LibFunc_ZnamSt11align_val_tRKSt9nothrow_t, // new[](unsigned long, align_val_t, nothrow)
94
                                 {MallocLike,  3, 0,  -1}},
95
  {LibFunc_msvc_new_int,         {OpNewLike,   1, 0,  -1}}, // new(unsigned int)
96
  {LibFunc_msvc_new_int_nothrow, {MallocLike,  2, 0,  -1}}, // new(unsigned int, nothrow)
97
  {LibFunc_msvc_new_longlong,         {OpNewLike,   1, 0,  -1}}, // new(unsigned long long)
98
  {LibFunc_msvc_new_longlong_nothrow, {MallocLike,  2, 0,  -1}}, // new(unsigned long long, nothrow)
99
  {LibFunc_msvc_new_array_int,         {OpNewLike,   1, 0,  -1}}, // new[](unsigned int)
100
  {LibFunc_msvc_new_array_int_nothrow, {MallocLike,  2, 0,  -1}}, // new[](unsigned int, nothrow)
101
  {LibFunc_msvc_new_array_longlong,         {OpNewLike,   1, 0,  -1}}, // new[](unsigned long long)
102
  {LibFunc_msvc_new_array_longlong_nothrow, {MallocLike,  2, 0,  -1}}, // new[](unsigned long long, nothrow)
103
  {LibFunc_calloc,              {CallocLike,  2, 0,   1}},
104
  {LibFunc_realloc,             {ReallocLike, 2, 1,  -1}},
105
  {LibFunc_reallocf,            {ReallocLike, 2, 1,  -1}},
106
  {LibFunc_strdup,              {StrDupLike,  1, -1, -1}},
107
  {LibFunc_strndup,             {StrDupLike,  2, 1,  -1}}
108
  // TODO: Handle "int posix_memalign(void **, size_t, size_t)"
109
};
110
111
static const Function *getCalledFunction(const Value *V, bool LookThroughBitCast,
112
231M
                                         bool &IsNoBuiltin) {
113
231M
  // Don't care about intrinsics in this case.
114
231M
  if (isa<IntrinsicInst>(V))
115
12.4M
    return nullptr;
116
219M
117
219M
  if (LookThroughBitCast)
118
0
    V = V->stripPointerCasts();
119
219M
120
219M
  ImmutableCallSite CS(V);
121
219M
  if (!CS.getInstruction())
122
128M
    return nullptr;
123
90.9M
124
90.9M
  IsNoBuiltin = CS.isNoBuiltin();
125
90.9M
126
90.9M
  if (const Function *Callee = CS.getCalledFunction())
127
85.8M
    return Callee;
128
5.11M
  return nullptr;
129
5.11M
}
130
131
/// Returns the allocation data for the given value if it's either a call to a
132
/// known allocation function, or a call to a function with the allocsize
133
/// attribute.
134
static Optional<AllocFnsTy>
135
getAllocationDataForFunction(const Function *Callee, AllocType AllocTy,
136
15.3M
                             const TargetLibraryInfo *TLI) {
137
15.3M
  // Make sure that the function is available.
138
15.3M
  StringRef FnName = Callee->getName();
139
15.3M
  LibFunc TLIFn;
140
15.3M
  if (!TLI || 
!TLI->getLibFunc(FnName, TLIFn)15.1M
||
!TLI->has(TLIFn)5.93M
)
141
9.81M
    return None;
142
5.55M
143
5.55M
  const auto *Iter = find_if(
144
144M
      AllocationFnData, [TLIFn](const std::pair<LibFunc, AllocFnsTy> &P) {
145
144M
        return P.first == TLIFn;
146
144M
      });
147
5.55M
148
5.55M
  if (Iter == std::end(AllocationFnData))
149
4.35M
    return None;
150
1.19M
151
1.19M
  const AllocFnsTy *FnData = &Iter->second;
152
1.19M
  if ((FnData->AllocTy & AllocTy) != FnData->AllocTy)
153
52.3k
    return None;
154
1.14M
155
1.14M
  // Check function prototype.
156
1.14M
  int FstParam = FnData->FstParam;
157
1.14M
  int SndParam = FnData->SndParam;
158
1.14M
  FunctionType *FTy = Callee->getFunctionType();
159
1.14M
160
1.14M
  if (FTy->getReturnType() == Type::getInt8PtrTy(FTy->getContext()) &&
161
1.14M
      
FTy->getNumParams() == FnData->NumParams1.14M
&&
162
1.14M
      
(1.14M
FstParam < 01.14M
||
163
1.14M
       
(1.14M
FTy->getParamType(FstParam)->isIntegerTy(32)1.14M
||
164
1.14M
        
FTy->getParamType(FstParam)->isIntegerTy(64)1.13M
)) &&
165
1.14M
      
(1.14M
SndParam < 01.14M
||
166
1.14M
       
FTy->getParamType(SndParam)->isIntegerTy(32)57.0k
||
167
1.14M
       
FTy->getParamType(SndParam)->isIntegerTy(64)55.8k
))
168
1.14M
    return *FnData;
169
11
  return None;
170
11
}
171
172
static Optional<AllocFnsTy> getAllocationData(const Value *V, AllocType AllocTy,
173
                                              const TargetLibraryInfo *TLI,
174
138M
                                              bool LookThroughBitCast = false) {
175
138M
  bool IsNoBuiltinCall;
176
138M
  if (const Function *Callee =
177
45.6M
          getCalledFunction(V, LookThroughBitCast, IsNoBuiltinCall))
178
45.6M
    if (!IsNoBuiltinCall)
179
14.4M
      return getAllocationDataForFunction(Callee, AllocTy, TLI);
180
124M
  return None;
181
124M
}
182
183
static Optional<AllocFnsTy> getAllocationSize(const Value *V,
184
1.16M
                                              const TargetLibraryInfo *TLI) {
185
1.16M
  bool IsNoBuiltinCall;
186
1.16M
  const Function *Callee =
187
1.16M
      getCalledFunction(V, /*LookThroughBitCast=*/false, IsNoBuiltinCall);
188
1.16M
  if (!Callee)
189
5.03k
    return None;
190
1.15M
191
1.15M
  // Prefer to use existing information over allocsize. This will give us an
192
1.15M
  // accurate AllocTy.
193
1.15M
  if (!IsNoBuiltinCall)
194
777k
    if (Optional<AllocFnsTy> Data =
195
677k
            getAllocationDataForFunction(Callee, AnyAlloc, TLI))
196
677k
      return Data;
197
477k
198
477k
  Attribute Attr = Callee->getFnAttribute(Attribute::AllocSize);
199
477k
  if (Attr == Attribute())
200
477k
    return None;
201
234
202
234
  std::pair<unsigned, Optional<unsigned>> Args = Attr.getAllocSizeArgs();
203
234
204
234
  AllocFnsTy Result;
205
234
  // Because allocsize only tells us how many bytes are allocated, we're not
206
234
  // really allowed to assume anything, so we use MallocLike.
207
234
  Result.AllocTy = MallocLike;
208
234
  Result.NumParams = Callee->getNumOperands();
209
234
  Result.FstParam = Args.first;
210
234
  Result.SndParam = Args.second.getValueOr(-1);
211
234
  return Result;
212
234
}
213
214
40.2M
static bool hasNoAliasAttr(const Value *V, bool LookThroughBitCast) {
215
40.2M
  ImmutableCallSite CS(LookThroughBitCast ? 
V->stripPointerCasts()0
: V);
216
40.2M
  return CS && 
CS.hasRetAttr(Attribute::NoAlias)2.32M
;
217
40.2M
}
218
219
/// Tests if a value is a call or invoke to a library function that
220
/// allocates or reallocates memory (either malloc, calloc, realloc, or strdup
221
/// like).
222
bool llvm::isAllocationFn(const Value *V, const TargetLibraryInfo *TLI,
223
40.4M
                          bool LookThroughBitCast) {
224
40.4M
  return getAllocationData(V, AnyAlloc, TLI, LookThroughBitCast).hasValue();
225
40.4M
}
226
227
/// Tests if a value is a call or invoke to a function that returns a
228
/// NoAlias pointer (including malloc/calloc/realloc/strdup-like functions).
229
bool llvm::isNoAliasFn(const Value *V, const TargetLibraryInfo *TLI,
230
40.3M
                       bool LookThroughBitCast) {
231
40.3M
  // it's safe to consider realloc as noalias since accessing the original
232
40.3M
  // pointer is undefined behavior
233
40.3M
  return isAllocationFn(V, TLI, LookThroughBitCast) ||
234
40.3M
         
hasNoAliasAttr(V, LookThroughBitCast)40.2M
;
235
40.3M
}
236
237
/// Tests if a value is a call or invoke to a library function that
238
/// allocates uninitialized memory (such as malloc).
239
bool llvm::isMallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
240
488k
                          bool LookThroughBitCast) {
241
488k
  return getAllocationData(V, MallocLike, TLI, LookThroughBitCast).hasValue();
242
488k
}
243
244
/// Tests if a value is a call or invoke to a library function that
245
/// allocates zero-filled memory (such as calloc).
246
bool llvm::isCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
247
642k
                          bool LookThroughBitCast) {
248
642k
  return getAllocationData(V, CallocLike, TLI, LookThroughBitCast).hasValue();
249
642k
}
250
251
/// Tests if a value is a call or invoke to a library function that
252
/// allocates memory similar to malloc or calloc.
253
bool llvm::isMallocOrCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
254
8.14M
                                  bool LookThroughBitCast) {
255
8.14M
  return getAllocationData(V, MallocOrCallocLike, TLI,
256
8.14M
                           LookThroughBitCast).hasValue();
257
8.14M
}
258
259
/// Tests if a value is a call or invoke to a library function that
260
/// allocates memory (either malloc, calloc, or strdup like).
261
bool llvm::isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
262
89.2M
                         bool LookThroughBitCast) {
263
89.2M
  return getAllocationData(V, AllocLike, TLI, LookThroughBitCast).hasValue();
264
89.2M
}
265
266
/// Tests if a value is a call or invoke to a library function that
267
/// reallocates memory (e.g., realloc).
268
bool llvm::isReallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
269
0
                     bool LookThroughBitCast) {
270
0
  return getAllocationData(V, ReallocLike, TLI, LookThroughBitCast).hasValue();
271
0
}
272
273
/// Tests if a functions is a call or invoke to a library function that
274
/// reallocates memory (e.g., realloc).
275
152k
bool llvm::isReallocLikeFn(const Function *F, const TargetLibraryInfo *TLI) {
276
152k
  return getAllocationDataForFunction(F, ReallocLike, TLI).hasValue();
277
152k
}
278
279
/// extractMallocCall - Returns the corresponding CallInst if the instruction
280
/// is a malloc call.  Since CallInst::CreateMalloc() only creates calls, we
281
/// ignore InvokeInst here.
282
const CallInst *llvm::extractMallocCall(const Value *I,
283
4.03k
                                        const TargetLibraryInfo *TLI) {
284
4.03k
  return isMallocLikeFn(I, TLI) ? 
dyn_cast<CallInst>(I)215
:
nullptr3.81k
;
285
4.03k
}
286
287
static Value *computeArraySize(const CallInst *CI, const DataLayout &DL,
288
                               const TargetLibraryInfo *TLI,
289
52
                               bool LookThroughSExt = false) {
290
52
  if (!CI)
291
0
    return nullptr;
292
52
293
52
  // The size of the malloc's result type must be known to determine array size.
294
52
  Type *T = getMallocAllocatedType(CI, TLI);
295
52
  if (!T || !T->isSized())
296
0
    return nullptr;
297
52
298
52
  unsigned ElementSize = DL.getTypeAllocSize(T);
299
52
  if (StructType *ST = dyn_cast<StructType>(T))
300
14
    ElementSize = DL.getStructLayout(ST)->getSizeInBytes();
301
52
302
52
  // If malloc call's arg can be determined to be a multiple of ElementSize,
303
52
  // return the multiple.  Otherwise, return NULL.
304
52
  Value *MallocArg = CI->getArgOperand(0);
305
52
  Value *Multiple = nullptr;
306
52
  if (ComputeMultiple(MallocArg, ElementSize, Multiple, LookThroughSExt))
307
18
    return Multiple;
308
34
309
34
  return nullptr;
310
34
}
311
312
/// getMallocType - Returns the PointerType resulting from the malloc call.
313
/// The PointerType depends on the number of bitcast uses of the malloc call:
314
///   0: PointerType is the calls' return type.
315
///   1: PointerType is the bitcast's result type.
316
///  >1: Unique PointerType cannot be determined, return NULL.
317
PointerType *llvm::getMallocType(const CallInst *CI,
318
269
                                 const TargetLibraryInfo *TLI) {
319
269
  assert(isMallocLikeFn(CI, TLI) && "getMallocType and not malloc call");
320
269
321
269
  PointerType *MallocType = nullptr;
322
269
  unsigned NumOfBitCastUses = 0;
323
269
324
269
  // Determine if CallInst has a bitcast use.
325
269
  for (Value::const_user_iterator UI = CI->user_begin(), E = CI->user_end();
326
618
       UI != E;)
327
349
    if (const BitCastInst *BCI = dyn_cast<BitCastInst>(*UI++)) {
328
221
      MallocType = cast<PointerType>(BCI->getDestTy());
329
221
      NumOfBitCastUses++;
330
221
    }
331
269
332
269
  // Malloc call has 1 bitcast use, so type is the bitcast's destination type.
333
269
  if (NumOfBitCastUses == 1)
334
221
    return MallocType;
335
48
336
48
  // Malloc call was not bitcast, so type is the malloc function's return type.
337
48
  if (NumOfBitCastUses == 0)
338
48
    return cast<PointerType>(CI->getType());
339
0
340
0
  // Type could not be determined.
341
0
  return nullptr;
342
0
}
343
344
/// getMallocAllocatedType - Returns the Type allocated by malloc call.
345
/// The Type depends on the number of bitcast uses of the malloc call:
346
///   0: PointerType is the malloc calls' return type.
347
///   1: PointerType is the bitcast's result type.
348
///  >1: Unique PointerType cannot be determined, return NULL.
349
Type *llvm::getMallocAllocatedType(const CallInst *CI,
350
269
                                   const TargetLibraryInfo *TLI) {
351
269
  PointerType *PT = getMallocType(CI, TLI);
352
269
  return PT ? PT->getElementType() : 
nullptr0
;
353
269
}
354
355
/// getMallocArraySize - Returns the array size of a malloc call.  If the
356
/// argument passed to malloc is a multiple of the size of the malloced type,
357
/// then return that multiple.  For non-array mallocs, the multiple is
358
/// constant 1.  Otherwise, return NULL for mallocs whose array size cannot be
359
/// determined.
360
Value *llvm::getMallocArraySize(CallInst *CI, const DataLayout &DL,
361
                                const TargetLibraryInfo *TLI,
362
52
                                bool LookThroughSExt) {
363
52
  assert(isMallocLikeFn(CI, TLI) && "getMallocArraySize and not malloc call");
364
52
  return computeArraySize(CI, DL, TLI, LookThroughSExt);
365
52
}
366
367
/// extractCallocCall - Returns the corresponding CallInst if the instruction
368
/// is a calloc call.
369
const CallInst *llvm::extractCallocCall(const Value *I,
370
0
                                        const TargetLibraryInfo *TLI) {
371
0
  return isCallocLikeFn(I, TLI) ? cast<CallInst>(I) : nullptr;
372
0
}
373
374
/// isLibFreeFunction - Returns true if the function is a builtin free()
375
4.00M
bool llvm::isLibFreeFunction(const Function *F, const LibFunc TLIFn) {
376
4.00M
  unsigned ExpectedNumParams;
377
4.00M
  if (TLIFn == LibFunc_free ||
378
4.00M
      
TLIFn == LibFunc_ZdlPv3.71M
|| // operator delete(void*)
379
4.00M
      
TLIFn == LibFunc_ZdaPv2.86M
|| // operator delete[](void*)
380
4.00M
      
TLIFn == LibFunc_msvc_delete_ptr322.72M
|| // operator delete(void*)
381
4.00M
      
TLIFn == LibFunc_msvc_delete_ptr642.72M
|| // operator delete(void*)
382
4.00M
      
TLIFn == LibFunc_msvc_delete_array_ptr322.72M
|| // operator delete[](void*)
383
4.00M
      
TLIFn == LibFunc_msvc_delete_array_ptr642.72M
) // operator delete[](void*)
384
1.28M
    ExpectedNumParams = 1;
385
2.72M
  else if (TLIFn == LibFunc_ZdlPvj ||              // delete(void*, uint)
386
2.72M
           
TLIFn == LibFunc_ZdlPvm2.72M
|| // delete(void*, ulong)
387
2.72M
           
TLIFn == LibFunc_ZdlPvRKSt9nothrow_t2.72M
|| // delete(void*, nothrow)
388
2.72M
           
TLIFn == LibFunc_ZdlPvSt11align_val_t2.72M
|| // delete(void*, align_val_t)
389
2.72M
           
TLIFn == LibFunc_ZdaPvj2.72M
|| // delete[](void*, uint)
390
2.72M
           
TLIFn == LibFunc_ZdaPvm2.72M
|| // delete[](void*, ulong)
391
2.72M
           
TLIFn == LibFunc_ZdaPvRKSt9nothrow_t2.72M
|| // delete[](void*, nothrow)
392
2.72M
           
TLIFn == LibFunc_ZdaPvSt11align_val_t2.72M
|| // delete[](void*, align_val_t)
393
2.72M
           
TLIFn == LibFunc_msvc_delete_ptr32_int2.72M
|| // delete(void*, uint)
394
2.72M
           
TLIFn == LibFunc_msvc_delete_ptr64_longlong2.72M
|| // delete(void*, ulonglong)
395
2.72M
           
TLIFn == LibFunc_msvc_delete_ptr32_nothrow2.72M
|| // delete(void*, nothrow)
396
2.72M
           
TLIFn == LibFunc_msvc_delete_ptr64_nothrow2.72M
|| // delete(void*, nothrow)
397
2.72M
           
TLIFn == LibFunc_msvc_delete_array_ptr32_int2.72M
|| // delete[](void*, uint)
398
2.72M
           
TLIFn == LibFunc_msvc_delete_array_ptr64_longlong2.72M
|| // delete[](void*, ulonglong)
399
2.72M
           
TLIFn == LibFunc_msvc_delete_array_ptr32_nothrow2.72M
|| // delete[](void*, nothrow)
400
2.72M
           
TLIFn == LibFunc_msvc_delete_array_ptr64_nothrow2.72M
) // delete[](void*, nothrow)
401
19
    ExpectedNumParams = 2;
402
2.72M
  else if (TLIFn == LibFunc_ZdaPvSt11align_val_tRKSt9nothrow_t || // delete(void*, align_val_t, nothrow)
403
2.72M
           
TLIFn == LibFunc_ZdlPvSt11align_val_tRKSt9nothrow_t2.72M
) // delete[](void*, align_val_t, nothrow)
404
12
    ExpectedNumParams = 3;
405
2.72M
  else
406
2.72M
    return false;
407
1.28M
408
1.28M
  // Check free prototype.
409
1.28M
  // FIXME: workaround for PR5130, this will be obsolete when a nobuiltin
410
1.28M
  // attribute will exist.
411
1.28M
  FunctionType *FTy = F->getFunctionType();
412
1.28M
  if (!FTy->getReturnType()->isVoidTy())
413
0
    return false;
414
1.28M
  if (FTy->getNumParams() != ExpectedNumParams)
415
1
    return false;
416
1.28M
  if (FTy->getParamType(0) != Type::getInt8PtrTy(F->getContext()))
417
0
    return false;
418
1.28M
419
1.28M
  return true;
420
1.28M
}
421
422
/// isFreeCall - Returns non-null if the value is a call to the builtin free()
423
91.6M
const CallInst *llvm::isFreeCall(const Value *I, const TargetLibraryInfo *TLI) {
424
91.6M
  bool IsNoBuiltinCall;
425
91.6M
  const Function *Callee =
426
91.6M
      getCalledFunction(I, /*LookThroughBitCast=*/false, IsNoBuiltinCall);
427
91.6M
  if (Callee == nullptr || 
IsNoBuiltinCall39.0M
)
428
79.9M
    return nullptr;
429
11.6M
430
11.6M
  StringRef FnName = Callee->getName();
431
11.6M
  LibFunc TLIFn;
432
11.6M
  if (!TLI || 
!TLI->getLibFunc(FnName, TLIFn)11.4M
||
!TLI->has(TLIFn)4.08M
)
433
7.84M
    return nullptr;
434
3.84M
435
3.84M
  return isLibFreeFunction(Callee, TLIFn) ? 
dyn_cast<CallInst>(I)1.27M
:
nullptr2.56M
;
436
3.84M
}
437
438
439
//===----------------------------------------------------------------------===//
440
//  Utility functions to compute size of objects.
441
//
442
13.4M
static APInt getSizeWithOverflow(const SizeOffsetType &Data) {
443
13.4M
  if (Data.second.isNegative() || Data.first.ult(Data.second))
444
0
    return APInt(Data.first.getBitWidth(), 0);
445
13.4M
  return Data.first - Data.second;
446
13.4M
}
447
448
/// Compute the size of the object pointed by Ptr. Returns true and the
449
/// object size in Size if successful, and false otherwise.
450
/// If RoundToAlign is true, then Size is rounded up to the alignment of
451
/// allocas, byval arguments, and global variables.
452
bool llvm::getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL,
453
28.9M
                         const TargetLibraryInfo *TLI, ObjectSizeOpts Opts) {
454
28.9M
  ObjectSizeOffsetVisitor Visitor(DL, TLI, Ptr->getContext(), Opts);
455
28.9M
  SizeOffsetType Data = Visitor.compute(const_cast<Value*>(Ptr));
456
28.9M
  if (!Visitor.bothKnown(Data))
457
15.5M
    return false;
458
13.4M
459
13.4M
  Size = getSizeWithOverflow(Data).getZExtValue();
460
13.4M
  return true;
461
13.4M
}
462
463
Value *llvm::lowerObjectSizeCall(IntrinsicInst *ObjectSize,
464
                                 const DataLayout &DL,
465
                                 const TargetLibraryInfo *TLI,
466
47.4k
                                 bool MustSucceed) {
467
47.4k
  assert(ObjectSize->getIntrinsicID() == Intrinsic::objectsize &&
468
47.4k
         "ObjectSize must be a call to llvm.objectsize!");
469
47.4k
470
47.4k
  bool MaxVal = cast<ConstantInt>(ObjectSize->getArgOperand(1))->isZero();
471
47.4k
  ObjectSizeOpts EvalOptions;
472
47.4k
  // Unless we have to fold this to something, try to be as accurate as
473
47.4k
  // possible.
474
47.4k
  if (MustSucceed)
475
3.40k
    EvalOptions.EvalMode =
476
3.40k
        MaxVal ? 
ObjectSizeOpts::Mode::Max3.40k
:
ObjectSizeOpts::Mode::Min6
;
477
44.0k
  else
478
44.0k
    EvalOptions.EvalMode = ObjectSizeOpts::Mode::Exact;
479
47.4k
480
47.4k
  EvalOptions.NullIsUnknownSize =
481
47.4k
      cast<ConstantInt>(ObjectSize->getArgOperand(2))->isOne();
482
47.4k
483
47.4k
  auto *ResultType = cast<IntegerType>(ObjectSize->getType());
484
47.4k
  bool StaticOnly = cast<ConstantInt>(ObjectSize->getArgOperand(3))->isZero();
485
47.4k
  if (StaticOnly) {
486
47.4k
    // FIXME: Does it make sense to just return a failure value if the size won't
487
47.4k
    // fit in the output and `!MustSucceed`?
488
47.4k
    uint64_t Size;
489
47.4k
    if (getObjectSize(ObjectSize->getArgOperand(0), Size, DL, TLI, EvalOptions) &&
490
47.4k
        
isUIntN(ResultType->getBitWidth(), Size)397
)
491
392
      return ConstantInt::get(ResultType, Size);
492
7
  } else {
493
7
    LLVMContext &Ctx = ObjectSize->getFunction()->getContext();
494
7
    ObjectSizeOffsetEvaluator Eval(DL, TLI, Ctx, EvalOptions);
495
7
    SizeOffsetEvalType SizeOffsetPair =
496
7
        Eval.compute(ObjectSize->getArgOperand(0));
497
7
498
7
    if (SizeOffsetPair != ObjectSizeOffsetEvaluator::unknown()) {
499
4
      IRBuilder<TargetFolder> Builder(Ctx, TargetFolder(DL));
500
4
      Builder.SetInsertPoint(ObjectSize);
501
4
502
4
      // If we've outside the end of the object, then we can always access
503
4
      // exactly 0 bytes.
504
4
      Value *ResultSize =
505
4
          Builder.CreateSub(SizeOffsetPair.first, SizeOffsetPair.second);
506
4
      Value *UseZero =
507
4
          Builder.CreateICmpULT(SizeOffsetPair.first, SizeOffsetPair.second);
508
4
      return Builder.CreateSelect(UseZero, ConstantInt::get(ResultType, 0),
509
4
                                  ResultSize);
510
4
    }
511
47.0k
  }
512
47.0k
513
47.0k
  if (!MustSucceed)
514
43.6k
    return nullptr;
515
3.39k
516
3.39k
  return ConstantInt::get(ResultType, MaxVal ? 
-1ULL3.38k
:
05
);
517
3.39k
}
518
519
STATISTIC(ObjectVisitorArgument,
520
          "Number of arguments with unsolved size and offset");
521
STATISTIC(ObjectVisitorLoad,
522
          "Number of load instructions with unsolved size and offset");
523
524
12.9M
APInt ObjectSizeOffsetVisitor::align(APInt Size, uint64_t Align) {
525
12.9M
  if (Options.RoundToAlign && 
Align12.5M
)
526
12.5M
    return APInt(IntTyBits, alignTo(Size.getZExtValue(), Align));
527
323k
  return Size;
528
323k
}
529
530
ObjectSizeOffsetVisitor::ObjectSizeOffsetVisitor(const DataLayout &DL,
531
                                                 const TargetLibraryInfo *TLI,
532
                                                 LLVMContext &Context,
533
                                                 ObjectSizeOpts Options)
534
28.9M
    : DL(DL), TLI(TLI), Options(Options) {
535
28.9M
  // Pointer size must be rechecked for each object visited since it could have
536
28.9M
  // a different address space.
537
28.9M
}
538
539
29.0M
SizeOffsetType ObjectSizeOffsetVisitor::compute(Value *V) {
540
29.0M
  IntTyBits = DL.getPointerTypeSizeInBits(V->getType());
541
29.0M
  Zero = APInt::getNullValue(IntTyBits);
542
29.0M
543
29.0M
  V = V->stripPointerCasts();
544
29.0M
  if (Instruction *I = dyn_cast<Instruction>(V)) {
545
12.7M
    // If we have already seen this instruction, bail out. Cycles can happen in
546
12.7M
    // unreachable code after constant propagation.
547
12.7M
    if (!SeenInsts.insert(I).second)
548
475
      return unknown();
549
12.7M
550
12.7M
    if (GEPOperator *GEP = dyn_cast<GEPOperator>(V))
551
34.1k
      return visitGEPOperator(*GEP);
552
12.6M
    return visit(*I);
553
12.6M
  }
554
16.2M
  if (Argument *A = dyn_cast<Argument>(V))
555
1.95M
    return visitArgument(*A);
556
14.3M
  if (ConstantPointerNull *P = dyn_cast<ConstantPointerNull>(V))
557
232
    return visitConstantPointerNull(*P);
558
14.3M
  if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V))
559
2
    return visitGlobalAlias(*GA);
560
14.3M
  if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
561
14.3M
    return visitGlobalVariable(*GV);
562
665
  if (UndefValue *UV = dyn_cast<UndefValue>(V))
563
13
    return visitUndefValue(*UV);
564
652
  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
565
615
    if (CE->getOpcode() == Instruction::IntToPtr)
566
0
      return unknown(); // clueless
567
615
    if (CE->getOpcode() == Instruction::GetElementPtr)
568
615
      return visitGEPOperator(cast<GEPOperator>(*CE));
569
37
  }
570
37
571
37
  LLVM_DEBUG(dbgs() << "ObjectSizeOffsetVisitor::compute() unhandled value: "
572
37
                    << *V << '\n');
573
37
  return unknown();
574
37
}
575
576
/// When we're compiling N-bit code, and the user uses parameters that are
577
/// greater than N bits (e.g. uint64_t on a 32-bit build), we can run into
578
/// trouble with APInt size issues. This function handles resizing + overflow
579
/// checks for us. Check and zext or trunc \p I depending on IntTyBits and
580
/// I's value.
581
564k
bool ObjectSizeOffsetVisitor::CheckedZextOrTrunc(APInt &I) {
582
564k
  // More bits than we can handle. Checking the bit width isn't necessary, but
583
564k
  // it's faster than checking active bits, and should give `false` in the
584
564k
  // vast majority of cases.
585
564k
  if (I.getBitWidth() > IntTyBits && 
I.getActiveBits() > IntTyBits5
)
586
3
    return false;
587
564k
  if (I.getBitWidth() != IntTyBits)
588
571
    I = I.zextOrTrunc(IntTyBits);
589
564k
  return true;
590
564k
}
591
592
11.1M
SizeOffsetType ObjectSizeOffsetVisitor::visitAllocaInst(AllocaInst &I) {
593
11.1M
  if (!I.getAllocatedType()->isSized())
594
0
    return unknown();
595
11.1M
596
11.1M
  APInt Size(IntTyBits, DL.getTypeAllocSize(I.getAllocatedType()));
597
11.1M
  if (!I.isArrayAllocation())
598
11.0M
    return std::make_pair(align(Size, I.getAlignment()), Zero);
599
9.34k
600
9.34k
  Value *ArraySize = I.getArraySize();
601
9.34k
  if (const ConstantInt *C = dyn_cast<ConstantInt>(ArraySize)) {
602
58
    APInt NumElems = C->getValue();
603
58
    if (!CheckedZextOrTrunc(NumElems))
604
1
      return unknown();
605
57
606
57
    bool Overflow;
607
57
    Size = Size.umul_ov(NumElems, Overflow);
608
57
    return Overflow ? 
unknown()0
: std::make_pair(align(Size, I.getAlignment()),
609
57
                                                 Zero);
610
57
  }
611
9.28k
  return unknown();
612
9.28k
}
613
614
1.95M
SizeOffsetType ObjectSizeOffsetVisitor::visitArgument(Argument &A) {
615
1.95M
  // No interprocedural analysis is done at the moment.
616
1.95M
  if (!A.hasByValOrInAllocaAttr()) {
617
1.95M
    ++ObjectVisitorArgument;
618
1.95M
    return unknown();
619
1.95M
  }
620
5.10k
  PointerType *PT = cast<PointerType>(A.getType());
621
5.10k
  APInt Size(IntTyBits, DL.getTypeAllocSize(PT->getElementType()));
622
5.10k
  return std::make_pair(align(Size, A.getParamAlignment()), Zero);
623
5.10k
}
624
625
1.16M
SizeOffsetType ObjectSizeOffsetVisitor::visitCallSite(CallSite CS) {
626
1.16M
  Optional<AllocFnsTy> FnData = getAllocationSize(CS.getInstruction(), TLI);
627
1.16M
  if (!FnData)
628
482k
    return unknown();
629
678k
630
678k
  // Handle strdup-like functions separately.
631
678k
  if (FnData->AllocTy == StrDupLike) {
632
82
    APInt Size(IntTyBits, GetStringLength(CS.getArgument(0)));
633
82
    if (!Size)
634
77
      return unknown();
635
5
636
5
    // Strndup limits strlen.
637
5
    if (FnData->FstParam > 0) {
638
4
      ConstantInt *Arg =
639
4
          dyn_cast<ConstantInt>(CS.getArgument(FnData->FstParam));
640
4
      if (!Arg)
641
0
        return unknown();
642
4
643
4
      APInt MaxSize = Arg->getValue().zextOrSelf(IntTyBits);
644
4
      if (Size.ugt(MaxSize))
645
2
        Size = MaxSize + 1;
646
4
    }
647
5
    return std::make_pair(Size, Zero);
648
677k
  }
649
677k
650
677k
  ConstantInt *Arg = dyn_cast<ConstantInt>(CS.getArgument(FnData->FstParam));
651
677k
  if (!Arg)
652
129k
    return unknown();
653
548k
654
548k
  APInt Size = Arg->getValue();
655
548k
  if (!CheckedZextOrTrunc(Size))
656
2
    return unknown();
657
548k
658
548k
  // Size is determined by just 1 parameter.
659
548k
  if (FnData->SndParam < 0)
660
531k
    return std::make_pair(Size, Zero);
661
16.8k
662
16.8k
  Arg = dyn_cast<ConstantInt>(CS.getArgument(FnData->SndParam));
663
16.8k
  if (!Arg)
664
1.34k
    return unknown();
665
15.4k
666
15.4k
  APInt NumElems = Arg->getValue();
667
15.4k
  if (!CheckedZextOrTrunc(NumElems))
668
0
    return unknown();
669
15.4k
670
15.4k
  bool Overflow;
671
15.4k
  Size = Size.umul_ov(NumElems, Overflow);
672
15.4k
  return Overflow ? 
unknown()0
: std::make_pair(Size, Zero);
673
15.4k
674
15.4k
  // TODO: handle more standard functions (+ wchar cousins):
675
15.4k
  // - strdup / strndup
676
15.4k
  // - strcpy / strncpy
677
15.4k
  // - strcat / strncat
678
15.4k
  // - memcpy / memmove
679
15.4k
  // - strcat / strncat
680
15.4k
  // - memset
681
15.4k
}
682
683
SizeOffsetType
684
232
ObjectSizeOffsetVisitor::visitConstantPointerNull(ConstantPointerNull& CPN) {
685
232
  // If null is unknown, there's nothing we can do. Additionally, non-zero
686
232
  // address spaces can make use of null, so we don't presume to know anything
687
232
  // about that.
688
232
  //
689
232
  // TODO: How should this work with address space casts? We currently just drop
690
232
  // them on the floor, but it's unclear what we should do when a NULL from
691
232
  // addrspace(1) gets casted to addrspace(0) (or vice-versa).
692
232
  if (Options.NullIsUnknownSize || 
CPN.getType()->getAddressSpace()223
)
693
69
    return unknown();
694
163
  return std::make_pair(Zero, Zero);
695
163
}
696
697
SizeOffsetType
698
0
ObjectSizeOffsetVisitor::visitExtractElementInst(ExtractElementInst&) {
699
0
  return unknown();
700
0
}
701
702
SizeOffsetType
703
52
ObjectSizeOffsetVisitor::visitExtractValueInst(ExtractValueInst&) {
704
52
  // Easy cases were already folded by previous passes.
705
52
  return unknown();
706
52
}
707
708
34.7k
SizeOffsetType ObjectSizeOffsetVisitor::visitGEPOperator(GEPOperator &GEP) {
709
34.7k
  SizeOffsetType PtrData = compute(GEP.getPointerOperand());
710
34.7k
  APInt Offset(IntTyBits, 0);
711
34.7k
  if (!bothKnown(PtrData) || 
!GEP.accumulateConstantOffset(DL, Offset)9.33k
)
712
26.6k
    return unknown();
713
8.14k
714
8.14k
  return std::make_pair(PtrData.first, PtrData.second + Offset);
715
8.14k
}
716
717
2
SizeOffsetType ObjectSizeOffsetVisitor::visitGlobalAlias(GlobalAlias &GA) {
718
2
  if (GA.isInterposable())
719
2
    return unknown();
720
0
  return compute(GA.getAliasee());
721
0
}
722
723
14.3M
SizeOffsetType ObjectSizeOffsetVisitor::visitGlobalVariable(GlobalVariable &GV){
724
14.3M
  if (!GV.hasDefinitiveInitializer())
725
12.5M
    return unknown();
726
1.80M
727
1.80M
  APInt Size(IntTyBits, DL.getTypeAllocSize(GV.getValueType()));
728
1.80M
  return std::make_pair(align(Size, GV.getAlignment()), Zero);
729
1.80M
}
730
731
5.19k
SizeOffsetType ObjectSizeOffsetVisitor::visitIntToPtrInst(IntToPtrInst&) {
732
5.19k
  // clueless
733
5.19k
  return unknown();
734
5.19k
}
735
736
305k
SizeOffsetType ObjectSizeOffsetVisitor::visitLoadInst(LoadInst&) {
737
305k
  ++ObjectVisitorLoad;
738
305k
  return unknown();
739
305k
}
740
741
98.8k
SizeOffsetType ObjectSizeOffsetVisitor::visitPHINode(PHINode&) {
742
98.8k
  // too complex to analyze statically.
743
98.8k
  return unknown();
744
98.8k
}
745
746
1.15k
SizeOffsetType ObjectSizeOffsetVisitor::visitSelectInst(SelectInst &I) {
747
1.15k
  SizeOffsetType TrueSide  = compute(I.getTrueValue());
748
1.15k
  SizeOffsetType FalseSide = compute(I.getFalseValue());
749
1.15k
  if (bothKnown(TrueSide) && 
bothKnown(FalseSide)315
) {
750
155
    if (TrueSide == FalseSide) {
751
149
        return TrueSide;
752
149
    }
753
6
754
6
    APInt TrueResult = getSizeWithOverflow(TrueSide);
755
6
    APInt FalseResult = getSizeWithOverflow(FalseSide);
756
6
757
6
    if (TrueResult == FalseResult) {
758
1
      return TrueSide;
759
1
    }
760
5
    if (Options.EvalMode == ObjectSizeOpts::Mode::Min) {
761
1
      if (TrueResult.slt(FalseResult))
762
0
        return TrueSide;
763
1
      return FalseSide;
764
1
    }
765
4
    if (Options.EvalMode == ObjectSizeOpts::Mode::Max) {
766
2
      if (TrueResult.sgt(FalseResult))
767
1
        return TrueSide;
768
1
      return FalseSide;
769
1
    }
770
4
  }
771
1.00k
  return unknown();
772
1.00k
}
773
774
13
SizeOffsetType ObjectSizeOffsetVisitor::visitUndefValue(UndefValue&) {
775
13
  return std::make_pair(Zero, Zero);
776
13
}
777
778
2
SizeOffsetType ObjectSizeOffsetVisitor::visitInstruction(Instruction &I) {
779
2
  LLVM_DEBUG(dbgs() << "ObjectSizeOffsetVisitor unknown instruction:" << I
780
2
                    << '\n');
781
2
  return unknown();
782
2
}
783
784
ObjectSizeOffsetEvaluator::ObjectSizeOffsetEvaluator(
785
    const DataLayout &DL, const TargetLibraryInfo *TLI, LLVMContext &Context,
786
    ObjectSizeOpts EvalOpts)
787
    : DL(DL), TLI(TLI), Context(Context),
788
      Builder(Context, TargetFolder(DL),
789
              IRBuilderCallbackInserter(
790
105
                  [&](Instruction *I) { InsertedInstructions.insert(I); })),
791
63
      EvalOpts(EvalOpts) {
792
63
  // IntTy and Zero must be set for each compute() since the address space may
793
63
  // be different for later objects.
794
63
}
795
796
98
SizeOffsetEvalType ObjectSizeOffsetEvaluator::compute(Value *V) {
797
98
  // XXX - Are vectors of pointers possible here?
798
98
  IntTy = cast<IntegerType>(DL.getIntPtrType(V->getType()));
799
98
  Zero = ConstantInt::get(IntTy, 0);
800
98
801
98
  SizeOffsetEvalType Result = compute_(V);
802
98
803
98
  if (!bothKnown(Result)) {
804
16
    // Erase everything that was computed in this iteration from the cache, so
805
16
    // that no dangling references are left behind. We could be a bit smarter if
806
16
    // we kept a dependency graph. It's probably not worth the complexity.
807
27
    for (const Value *SeenVal : SeenVals) {
808
27
      CacheMapTy::iterator CacheIt = CacheMap.find(SeenVal);
809
27
      // non-computable results can be safely cached
810
27
      if (CacheIt != CacheMap.end() && anyKnown(CacheIt->second))
811
4
        CacheMap.erase(CacheIt);
812
27
    }
813
16
814
16
    // Erase any instructions we inserted as part of the traversal.
815
16
    for (Instruction *I : InsertedInstructions) {
816
6
      I->replaceAllUsesWith(UndefValue::get(I->getType()));
817
6
      I->eraseFromParent();
818
6
    }
819
16
  }
820
98
821
98
  SeenVals.clear();
822
98
  InsertedInstructions.clear();
823
98
  return Result;
824
98
}
825
826
158
SizeOffsetEvalType ObjectSizeOffsetEvaluator::compute_(Value *V) {
827
158
  ObjectSizeOffsetVisitor Visitor(DL, TLI, Context, EvalOpts);
828
158
  SizeOffsetType Const = Visitor.compute(V);
829
158
  if (Visitor.bothKnown(Const))
830
65
    return std::make_pair(ConstantInt::get(Context, Const.first),
831
65
                          ConstantInt::get(Context, Const.second));
832
93
833
93
  V = V->stripPointerCasts();
834
93
835
93
  // Check cache.
836
93
  CacheMapTy::iterator CacheIt = CacheMap.find(V);
837
93
  if (CacheIt != CacheMap.end())
838
14
    return CacheIt->second;
839
79
840
79
  // Always generate code immediately before the instruction being
841
79
  // processed, so that the generated code dominates the same BBs.
842
79
  BuilderTy::InsertPointGuard Guard(Builder);
843
79
  if (Instruction *I = dyn_cast<Instruction>(V))
844
71
    Builder.SetInsertPoint(I);
845
79
846
79
  // Now compute the size and offset.
847
79
  SizeOffsetEvalType Result;
848
79
849
79
  // Record the pointers that were handled in this run, so that they can be
850
79
  // cleaned later if something fails. We also use this set to break cycles that
851
79
  // can occur in dead code.
852
79
  if (!SeenVals.insert(V).second) {
853
2
    Result = unknown();
854
77
  } else if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
855
38
    Result = visitGEPOperator(*GEP);
856
39
  } else if (Instruction *I = dyn_cast<Instruction>(V)) {
857
31
    Result = visit(*I);
858
31
  } else 
if (8
isa<Argument>(V)8
||
859
8
             
(4
isa<ConstantExpr>(V)4
&&
860
4
              
cast<ConstantExpr>(V)->getOpcode() == Instruction::IntToPtr0
) ||
861
8
             
isa<GlobalAlias>(V)4
||
862
8
             
isa<GlobalVariable>(V)4
) {
863
7
    // Ignore values where we cannot do more than ObjectSizeVisitor.
864
7
    Result = unknown();
865
7
  } else {
866
1
    LLVM_DEBUG(
867
1
        dbgs() << "ObjectSizeOffsetEvaluator::compute() unhandled value: " << *V
868
1
               << '\n');
869
1
    Result = unknown();
870
1
  }
871
79
872
79
  // Don't reuse CacheIt since it may be invalid at this point.
873
79
  CacheMap[V] = Result;
874
79
  return Result;
875
79
}
876
877
10
SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitAllocaInst(AllocaInst &I) {
878
10
  if (!I.getAllocatedType()->isSized())
879
0
    return unknown();
880
10
881
10
  // must be a VLA
882
10
  assert(I.isArrayAllocation());
883
10
  Value *ArraySize = I.getArraySize();
884
10
  Value *Size = ConstantInt::get(ArraySize->getType(),
885
10
                                 DL.getTypeAllocSize(I.getAllocatedType()));
886
10
  Size = Builder.CreateMul(Size, ArraySize);
887
10
  return std::make_pair(Size, Zero);
888
10
}
889
890
8
SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitCallSite(CallSite CS) {
891
8
  Optional<AllocFnsTy> FnData = getAllocationSize(CS.getInstruction(), TLI);
892
8
  if (!FnData)
893
0
    return unknown();
894
8
895
8
  // Handle strdup-like functions separately.
896
8
  if (FnData->AllocTy == StrDupLike) {
897
0
    // TODO
898
0
    return unknown();
899
0
  }
900
8
901
8
  Value *FirstArg = CS.getArgument(FnData->FstParam);
902
8
  FirstArg = Builder.CreateZExt(FirstArg, IntTy);
903
8
  if (FnData->SndParam < 0)
904
4
    return std::make_pair(FirstArg, Zero);
905
4
906
4
  Value *SecondArg = CS.getArgument(FnData->SndParam);
907
4
  SecondArg = Builder.CreateZExt(SecondArg, IntTy);
908
4
  Value *Size = Builder.CreateMul(FirstArg, SecondArg);
909
4
  return std::make_pair(Size, Zero);
910
4
911
4
  // TODO: handle more standard functions (+ wchar cousins):
912
4
  // - strdup / strndup
913
4
  // - strcpy / strncpy
914
4
  // - strcat / strncat
915
4
  // - memcpy / memmove
916
4
  // - strcat / strncat
917
4
  // - memset
918
4
}
919
920
SizeOffsetEvalType
921
0
ObjectSizeOffsetEvaluator::visitExtractElementInst(ExtractElementInst&) {
922
0
  return unknown();
923
0
}
924
925
SizeOffsetEvalType
926
0
ObjectSizeOffsetEvaluator::visitExtractValueInst(ExtractValueInst&) {
927
0
  return unknown();
928
0
}
929
930
SizeOffsetEvalType
931
38
ObjectSizeOffsetEvaluator::visitGEPOperator(GEPOperator &GEP) {
932
38
  SizeOffsetEvalType PtrData = compute_(GEP.getPointerOperand());
933
38
  if (!bothKnown(PtrData))
934
7
    return unknown();
935
31
936
31
  Value *Offset = EmitGEPOffset(&Builder, DL, &GEP, /*NoAssumptions=*/true);
937
31
  Offset = Builder.CreateAdd(PtrData.second, Offset);
938
31
  return std::make_pair(PtrData.first, Offset);
939
31
}
940
941
0
SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitIntToPtrInst(IntToPtrInst&) {
942
0
  // clueless
943
0
  return unknown();
944
0
}
945
946
2
SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitLoadInst(LoadInst&) {
947
2
  return unknown();
948
2
}
949
950
7
SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitPHINode(PHINode &PHI) {
951
7
  // Create 2 PHIs: one for size and another for offset.
952
7
  PHINode *SizePHI   = Builder.CreatePHI(IntTy, PHI.getNumIncomingValues());
953
7
  PHINode *OffsetPHI = Builder.CreatePHI(IntTy, PHI.getNumIncomingValues());
954
7
955
7
  // Insert right away in the cache to handle recursive PHIs.
956
7
  CacheMap[&PHI] = std::make_pair(SizePHI, OffsetPHI);
957
7
958
7
  // Compute offset/size for each PHI incoming pointer.
959
17
  for (unsigned i = 0, e = PHI.getNumIncomingValues(); i != e; 
++i10
) {
960
14
    Builder.SetInsertPoint(&*PHI.getIncomingBlock(i)->getFirstInsertionPt());
961
14
    SizeOffsetEvalType EdgeData = compute_(PHI.getIncomingValue(i));
962
14
963
14
    if (!bothKnown(EdgeData)) {
964
4
      OffsetPHI->replaceAllUsesWith(UndefValue::get(IntTy));
965
4
      OffsetPHI->eraseFromParent();
966
4
      InsertedInstructions.erase(OffsetPHI);
967
4
      SizePHI->replaceAllUsesWith(UndefValue::get(IntTy));
968
4
      SizePHI->eraseFromParent();
969
4
      InsertedInstructions.erase(SizePHI);
970
4
      return unknown();
971
4
    }
972
10
    SizePHI->addIncoming(EdgeData.first, PHI.getIncomingBlock(i));
973
10
    OffsetPHI->addIncoming(EdgeData.second, PHI.getIncomingBlock(i));
974
10
  }
975
7
976
7
  Value *Size = SizePHI, *Offset = OffsetPHI;
977
3
  if (Value *Tmp = SizePHI->hasConstantValue()) {
978
2
    Size = Tmp;
979
2
    SizePHI->replaceAllUsesWith(Size);
980
2
    SizePHI->eraseFromParent();
981
2
    InsertedInstructions.erase(SizePHI);
982
2
  }
983
3
  if (Value *Tmp = OffsetPHI->hasConstantValue()) {
984
1
    Offset = Tmp;
985
1
    OffsetPHI->replaceAllUsesWith(Offset);
986
1
    OffsetPHI->eraseFromParent();
987
1
    InsertedInstructions.erase(OffsetPHI);
988
1
  }
989
3
  return std::make_pair(Size, Offset);
990
7
}
991
992
4
SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitSelectInst(SelectInst &I) {
993
4
  SizeOffsetEvalType TrueSide  = compute_(I.getTrueValue());
994
4
  SizeOffsetEvalType FalseSide = compute_(I.getFalseValue());
995
4
996
4
  if (!bothKnown(TrueSide) || 
!bothKnown(FalseSide)2
)
997
2
    return unknown();
998
2
  if (TrueSide == FalseSide)
999
0
    return TrueSide;
1000
2
1001
2
  Value *Size = Builder.CreateSelect(I.getCondition(), TrueSide.first,
1002
2
                                     FalseSide.first);
1003
2
  Value *Offset = Builder.CreateSelect(I.getCondition(), TrueSide.second,
1004
2
                                       FalseSide.second);
1005
2
  return std::make_pair(Size, Offset);
1006
2
}
1007
1008
0
SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitInstruction(Instruction &I) {
1009
0
  LLVM_DEBUG(dbgs() << "ObjectSizeOffsetEvaluator unknown instruction:" << I
1010
0
                    << '\n');
1011
0
  return unknown();
1012
0
}