LLVM  15.0.0git
MemoryBuiltins.cpp
Go to the documentation of this file.
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 
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"
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"
43 #include <cassert>
44 #include <cstdint>
45 #include <iterator>
46 #include <numeric>
47 #include <type_traits>
48 #include <utility>
49 
50 using namespace llvm;
51 
52 #define DEBUG_TYPE "memory-builtins"
53 
54 enum AllocType : uint8_t {
55  OpNewLike = 1<<0, // allocates; never returns null
56  MallocLike = 1<<1, // allocates; may return null
57  AlignedAllocLike = 1<<2, // allocates with alignment; may return null
58  CallocLike = 1<<3, // allocates + bzero
59  ReallocLike = 1<<4, // reallocates
60  StrDupLike = 1<<5,
65 };
66 
67 enum class MallocFamily {
68  Malloc,
69  CPPNew, // new(unsigned int)
70  CPPNewAligned, // new(unsigned int, align_val_t)
71  CPPNewArray, // new[](unsigned int)
72  CPPNewArrayAligned, // new[](unsigned long, align_val_t)
73  MSVCNew, // new(unsigned int)
74  MSVCArrayNew, // new[](unsigned int)
75  VecMalloc,
77 };
78 
80  switch (Family) {
82  return "malloc";
84  return "_Znwm";
86  return "_ZnwmSt11align_val_t";
88  return "_Znam";
90  return "_ZnamSt11align_val_t";
92  return "??2@YAPAXI@Z";
94  return "??_U@YAPAXI@Z";
96  return "vec_malloc";
98  return "__kmpc_alloc_shared";
99  }
100  llvm_unreachable("missing an alloc family");
101 }
102 
103 struct AllocFnsTy {
105  unsigned NumParams;
106  // First and Second size parameters (or -1 if unused)
107  int FstParam, SndParam;
108  // Alignment parameter for aligned_alloc and aligned new
110  // Name of default allocator function to group malloc/free calls by family
112 };
113 
114 // clang-format off
115 // FIXME: certain users need more information. E.g., SimplifyLibCalls needs to
116 // know which functions are nounwind, noalias, nocapture parameters, etc.
117 static const std::pair<LibFunc, AllocFnsTy> AllocationFnData[] = {
118  {LibFunc_malloc, {MallocLike, 1, 0, -1, -1, MallocFamily::Malloc}},
119  {LibFunc_vec_malloc, {MallocLike, 1, 0, -1, -1, MallocFamily::VecMalloc}},
120  {LibFunc_valloc, {MallocLike, 1, 0, -1, -1, MallocFamily::Malloc}},
121  {LibFunc_Znwj, {OpNewLike, 1, 0, -1, -1, MallocFamily::CPPNew}}, // new(unsigned int)
122  {LibFunc_ZnwjRKSt9nothrow_t, {MallocLike, 2, 0, -1, -1, MallocFamily::CPPNew}}, // new(unsigned int, nothrow)
123  {LibFunc_ZnwjSt11align_val_t, {OpNewLike, 2, 0, -1, 1, MallocFamily::CPPNewAligned}}, // new(unsigned int, align_val_t)
124  {LibFunc_ZnwjSt11align_val_tRKSt9nothrow_t, {MallocLike, 3, 0, -1, 1, MallocFamily::CPPNewAligned}}, // new(unsigned int, align_val_t, nothrow)
125  {LibFunc_Znwm, {OpNewLike, 1, 0, -1, -1, MallocFamily::CPPNew}}, // new(unsigned long)
126  {LibFunc_ZnwmRKSt9nothrow_t, {MallocLike, 2, 0, -1, -1, MallocFamily::CPPNew}}, // new(unsigned long, nothrow)
127  {LibFunc_ZnwmSt11align_val_t, {OpNewLike, 2, 0, -1, 1, MallocFamily::CPPNewAligned}}, // new(unsigned long, align_val_t)
128  {LibFunc_ZnwmSt11align_val_tRKSt9nothrow_t, {MallocLike, 3, 0, -1, 1, MallocFamily::CPPNewAligned}}, // new(unsigned long, align_val_t, nothrow)
129  {LibFunc_Znaj, {OpNewLike, 1, 0, -1, -1, MallocFamily::CPPNewArray}}, // new[](unsigned int)
130  {LibFunc_ZnajRKSt9nothrow_t, {MallocLike, 2, 0, -1, -1, MallocFamily::CPPNewArray}}, // new[](unsigned int, nothrow)
131  {LibFunc_ZnajSt11align_val_t, {OpNewLike, 2, 0, -1, 1, MallocFamily::CPPNewArrayAligned}}, // new[](unsigned int, align_val_t)
132  {LibFunc_ZnajSt11align_val_tRKSt9nothrow_t, {MallocLike, 3, 0, -1, 1, MallocFamily::CPPNewArrayAligned}}, // new[](unsigned int, align_val_t, nothrow)
133  {LibFunc_Znam, {OpNewLike, 1, 0, -1, -1, MallocFamily::CPPNewArray}}, // new[](unsigned long)
134  {LibFunc_ZnamRKSt9nothrow_t, {MallocLike, 2, 0, -1, -1, MallocFamily::CPPNewArray}}, // new[](unsigned long, nothrow)
135  {LibFunc_ZnamSt11align_val_t, {OpNewLike, 2, 0, -1, 1, MallocFamily::CPPNewArrayAligned}}, // new[](unsigned long, align_val_t)
136  {LibFunc_ZnamSt11align_val_tRKSt9nothrow_t, {MallocLike, 3, 0, -1, 1, MallocFamily::CPPNewArrayAligned}}, // new[](unsigned long, align_val_t, nothrow)
137  {LibFunc_msvc_new_int, {OpNewLike, 1, 0, -1, -1, MallocFamily::MSVCNew}}, // new(unsigned int)
138  {LibFunc_msvc_new_int_nothrow, {MallocLike, 2, 0, -1, -1, MallocFamily::MSVCNew}}, // new(unsigned int, nothrow)
139  {LibFunc_msvc_new_longlong, {OpNewLike, 1, 0, -1, -1, MallocFamily::MSVCNew}}, // new(unsigned long long)
140  {LibFunc_msvc_new_longlong_nothrow, {MallocLike, 2, 0, -1, -1, MallocFamily::MSVCNew}}, // new(unsigned long long, nothrow)
141  {LibFunc_msvc_new_array_int, {OpNewLike, 1, 0, -1, -1, MallocFamily::MSVCArrayNew}}, // new[](unsigned int)
142  {LibFunc_msvc_new_array_int_nothrow, {MallocLike, 2, 0, -1, -1, MallocFamily::MSVCArrayNew}}, // new[](unsigned int, nothrow)
143  {LibFunc_msvc_new_array_longlong, {OpNewLike, 1, 0, -1, -1, MallocFamily::MSVCArrayNew}}, // new[](unsigned long long)
144  {LibFunc_msvc_new_array_longlong_nothrow, {MallocLike, 2, 0, -1, -1, MallocFamily::MSVCArrayNew}}, // new[](unsigned long long, nothrow)
145  {LibFunc_aligned_alloc, {AlignedAllocLike, 2, 1, -1, 0, MallocFamily::Malloc}},
146  {LibFunc_memalign, {AlignedAllocLike, 2, 1, -1, 0, MallocFamily::Malloc}},
147  {LibFunc_calloc, {CallocLike, 2, 0, 1, -1, MallocFamily::Malloc}},
148  {LibFunc_vec_calloc, {CallocLike, 2, 0, 1, -1, MallocFamily::VecMalloc}},
149  {LibFunc_realloc, {ReallocLike, 2, 1, -1, -1, MallocFamily::Malloc}},
150  {LibFunc_vec_realloc, {ReallocLike, 2, 1, -1, -1, MallocFamily::VecMalloc}},
151  {LibFunc_reallocf, {ReallocLike, 2, 1, -1, -1, MallocFamily::Malloc}},
152  {LibFunc_strdup, {StrDupLike, 1, -1, -1, -1, MallocFamily::Malloc}},
153  {LibFunc_dunder_strdup, {StrDupLike, 1, -1, -1, -1, MallocFamily::Malloc}},
154  {LibFunc_strndup, {StrDupLike, 2, 1, -1, -1, MallocFamily::Malloc}},
155  {LibFunc_dunder_strndup, {StrDupLike, 2, 1, -1, -1, MallocFamily::Malloc}},
156  {LibFunc___kmpc_alloc_shared, {MallocLike, 1, 0, -1, -1, MallocFamily::KmpcAllocShared}},
157 };
158 // clang-format on
159 
160 static const Function *getCalledFunction(const Value *V,
161  bool &IsNoBuiltin) {
162  // Don't care about intrinsics in this case.
163  if (isa<IntrinsicInst>(V))
164  return nullptr;
165 
166  const auto *CB = dyn_cast<CallBase>(V);
167  if (!CB)
168  return nullptr;
169 
170  IsNoBuiltin = CB->isNoBuiltin();
171 
172  if (const Function *Callee = CB->getCalledFunction())
173  return Callee;
174  return nullptr;
175 }
176 
177 /// Returns the allocation data for the given value if it's a call to a known
178 /// allocation function.
181  const TargetLibraryInfo *TLI) {
182  // Make sure that the function is available.
183  LibFunc TLIFn;
184  if (!TLI || !TLI->getLibFunc(*Callee, TLIFn) || !TLI->has(TLIFn))
185  return None;
186 
187  const auto *Iter = find_if(
188  AllocationFnData, [TLIFn](const std::pair<LibFunc, AllocFnsTy> &P) {
189  return P.first == TLIFn;
190  });
191 
192  if (Iter == std::end(AllocationFnData))
193  return None;
194 
195  const AllocFnsTy *FnData = &Iter->second;
196  if ((FnData->AllocTy & AllocTy) != FnData->AllocTy)
197  return None;
198 
199  // Check function prototype.
200  int FstParam = FnData->FstParam;
201  int SndParam = FnData->SndParam;
203 
204  if (FTy->getReturnType() == Type::getInt8PtrTy(FTy->getContext()) &&
205  FTy->getNumParams() == FnData->NumParams &&
206  (FstParam < 0 ||
207  (FTy->getParamType(FstParam)->isIntegerTy(32) ||
208  FTy->getParamType(FstParam)->isIntegerTy(64))) &&
209  (SndParam < 0 ||
210  FTy->getParamType(SndParam)->isIntegerTy(32) ||
211  FTy->getParamType(SndParam)->isIntegerTy(64)))
212  return *FnData;
213  return None;
214 }
215 
217  const TargetLibraryInfo *TLI) {
218  bool IsNoBuiltinCall;
219  if (const Function *Callee = getCalledFunction(V, IsNoBuiltinCall))
220  if (!IsNoBuiltinCall)
221  return getAllocationDataForFunction(Callee, AllocTy, TLI);
222  return None;
223 }
224 
227  function_ref<const TargetLibraryInfo &(Function &)> GetTLI) {
228  bool IsNoBuiltinCall;
229  if (const Function *Callee = getCalledFunction(V, IsNoBuiltinCall))
230  if (!IsNoBuiltinCall)
232  Callee, AllocTy, &GetTLI(const_cast<Function &>(*Callee)));
233  return None;
234 }
235 
237  const TargetLibraryInfo *TLI) {
238  bool IsNoBuiltinCall;
239  const Function *Callee =
240  getCalledFunction(V, IsNoBuiltinCall);
241  if (!Callee)
242  return None;
243 
244  // Prefer to use existing information over allocsize. This will give us an
245  // accurate AllocTy.
246  if (!IsNoBuiltinCall)
249  return Data;
250 
251  Attribute Attr = Callee->getFnAttribute(Attribute::AllocSize);
252  if (Attr == Attribute())
253  return None;
254 
255  std::pair<unsigned, Optional<unsigned>> Args = Attr.getAllocSizeArgs();
256 
257  AllocFnsTy Result;
258  // Because allocsize only tells us how many bytes are allocated, we're not
259  // really allowed to assume anything, so we use MallocLike.
260  Result.AllocTy = MallocLike;
261  Result.NumParams = Callee->getNumOperands();
262  Result.FstParam = Args.first;
263  Result.SndParam = Args.second.getValueOr(-1);
264  // Allocsize has no way to specify an alignment argument
265  Result.AlignParam = -1;
266  return Result;
267 }
268 
269 /// Tests if a value is a call or invoke to a library function that
270 /// allocates or reallocates memory (either malloc, calloc, realloc, or strdup
271 /// like).
272 bool llvm::isAllocationFn(const Value *V, const TargetLibraryInfo *TLI) {
273  return getAllocationData(V, AnyAlloc, TLI).hasValue();
274 }
276  const Value *V, function_ref<const TargetLibraryInfo &(Function &)> GetTLI) {
277  return getAllocationData(V, AnyAlloc, GetTLI).hasValue();
278 }
279 
280 /// Tests if a value is a call or invoke to a library function that
281 /// allocates uninitialized memory (such as malloc).
282 static bool isMallocLikeFn(const Value *V, const TargetLibraryInfo *TLI) {
283  return getAllocationData(V, MallocOrOpNewLike, TLI).hasValue();
284 }
285 
286 /// Tests if a value is a call or invoke to a library function that
287 /// allocates uninitialized memory with alignment (such as aligned_alloc).
288 static bool isAlignedAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI) {
289  return getAllocationData(V, AlignedAllocLike, TLI)
290  .hasValue();
291 }
292 
293 /// Tests if a value is a call or invoke to a library function that
294 /// allocates zero-filled memory (such as calloc).
295 static bool isCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI) {
296  return getAllocationData(V, CallocLike, TLI).hasValue();
297 }
298 
299 /// Tests if a value is a call or invoke to a library function that
300 /// allocates memory similar to malloc or calloc.
302  return getAllocationData(V, MallocOrCallocLike, TLI).hasValue();
303 }
304 
305 /// Tests if a value is a call or invoke to a library function that
306 /// allocates memory (either malloc, calloc, or strdup like).
307 bool llvm::isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI) {
308  return getAllocationData(V, AllocLike, TLI).hasValue();
309 }
310 
311 /// Tests if a value is a call or invoke to a library function that
312 /// reallocates memory (e.g., realloc).
313 bool llvm::isReallocLikeFn(const Value *V, const TargetLibraryInfo *TLI) {
314  return getAllocationData(V, ReallocLike, TLI).hasValue();
315 }
316 
317 /// Tests if a functions is a call or invoke to a library function that
318 /// reallocates memory (e.g., realloc).
320  return getAllocationDataForFunction(F, ReallocLike, TLI).hasValue();
321 }
322 
323 bool llvm::isAllocRemovable(const CallBase *CB, const TargetLibraryInfo *TLI) {
324  assert(isAllocationFn(CB, TLI));
325 
326  // Note: Removability is highly dependent on the source language. For
327  // example, recent C++ requires direct calls to the global allocation
328  // [basic.stc.dynamic.allocation] to be observable unless part of a new
329  // expression [expr.new paragraph 13].
330 
331  // Historically we've treated the C family allocation routines as removable
332  return isAllocLikeFn(CB, TLI);
333 }
334 
336  const TargetLibraryInfo *TLI) {
337  const Optional<AllocFnsTy> FnData = getAllocationData(V, AnyAlloc, TLI);
338  if (FnData.hasValue() && FnData->AlignParam >= 0) {
339  return V->getOperand(FnData->AlignParam);
340  }
341  return V->getArgOperandWithAttribute(Attribute::AllocAlign);
342 }
343 
344 /// When we're compiling N-bit code, and the user uses parameters that are
345 /// greater than N bits (e.g. uint64_t on a 32-bit build), we can run into
346 /// trouble with APInt size issues. This function handles resizing + overflow
347 /// checks for us. Check and zext or trunc \p I depending on IntTyBits and
348 /// I's value.
349 static bool CheckedZextOrTrunc(APInt &I, unsigned IntTyBits) {
350  // More bits than we can handle. Checking the bit width isn't necessary, but
351  // it's faster than checking active bits, and should give `false` in the
352  // vast majority of cases.
353  if (I.getBitWidth() > IntTyBits && I.getActiveBits() > IntTyBits)
354  return false;
355  if (I.getBitWidth() != IntTyBits)
356  I = I.zextOrTrunc(IntTyBits);
357  return true;
358 }
359 
362  const TargetLibraryInfo *TLI,
363  std::function<const Value*(const Value*)> Mapper) {
364  // Note: This handles both explicitly listed allocation functions and
365  // allocsize. The code structure could stand to be cleaned up a bit.
366  Optional<AllocFnsTy> FnData = getAllocationSize(CB, TLI);
367  if (!FnData)
368  return None;
369 
370  // Get the index type for this address space, results and intermediate
371  // computations are performed at that width.
372  auto &DL = CB->getModule()->getDataLayout();
373  const unsigned IntTyBits = DL.getIndexTypeSizeInBits(CB->getType());
374 
375  // Handle strdup-like functions separately.
376  if (FnData->AllocTy == StrDupLike) {
377  APInt Size(IntTyBits, GetStringLength(Mapper(CB->getArgOperand(0))));
378  if (!Size)
379  return None;
380 
381  // Strndup limits strlen.
382  if (FnData->FstParam > 0) {
383  const ConstantInt *Arg =
384  dyn_cast<ConstantInt>(Mapper(CB->getArgOperand(FnData->FstParam)));
385  if (!Arg)
386  return None;
387 
388  APInt MaxSize = Arg->getValue().zext(IntTyBits);
389  if (Size.ugt(MaxSize))
390  Size = MaxSize + 1;
391  }
392  return Size;
393  }
394 
395  const ConstantInt *Arg =
396  dyn_cast<ConstantInt>(Mapper(CB->getArgOperand(FnData->FstParam)));
397  if (!Arg)
398  return None;
399 
400  APInt Size = Arg->getValue();
401  if (!CheckedZextOrTrunc(Size, IntTyBits))
402  return None;
403 
404  // Size is determined by just 1 parameter.
405  if (FnData->SndParam < 0)
406  return Size;
407 
408  Arg = dyn_cast<ConstantInt>(Mapper(CB->getArgOperand(FnData->SndParam)));
409  if (!Arg)
410  return None;
411 
412  APInt NumElems = Arg->getValue();
413  if (!CheckedZextOrTrunc(NumElems, IntTyBits))
414  return None;
415 
416  bool Overflow;
417  Size = Size.umul_ov(NumElems, Overflow);
418  if (Overflow)
419  return None;
420  return Size;
421 }
422 
424  const TargetLibraryInfo *TLI,
425  Type *Ty) {
426  assert(isAllocationFn(Alloc, TLI));
427 
428  // malloc and aligned_alloc are uninitialized (undef)
429  if (isMallocLikeFn(Alloc, TLI) || isAlignedAllocLikeFn(Alloc, TLI))
430  return UndefValue::get(Ty);
431 
432  // calloc zero initializes
433  if (isCallocLikeFn(Alloc, TLI))
434  return Constant::getNullValue(Ty);
435 
436  return nullptr;
437 }
438 
439 struct FreeFnsTy {
440  unsigned NumParams;
441  // Name of default allocator function to group malloc/free calls by family
443 };
444 
445 // clang-format off
446 static const std::pair<LibFunc, FreeFnsTy> FreeFnData[] = {
447  {LibFunc_free, {1, MallocFamily::Malloc}},
448  {LibFunc_vec_free, {1, MallocFamily::VecMalloc}},
449  {LibFunc_ZdlPv, {1, MallocFamily::CPPNew}}, // operator delete(void*)
450  {LibFunc_ZdaPv, {1, MallocFamily::CPPNewArray}}, // operator delete[](void*)
451  {LibFunc_msvc_delete_ptr32, {1, MallocFamily::MSVCNew}}, // operator delete(void*)
452  {LibFunc_msvc_delete_ptr64, {1, MallocFamily::MSVCNew}}, // operator delete(void*)
453  {LibFunc_msvc_delete_array_ptr32, {1, MallocFamily::MSVCArrayNew}}, // operator delete[](void*)
454  {LibFunc_msvc_delete_array_ptr64, {1, MallocFamily::MSVCArrayNew}}, // operator delete[](void*)
455  {LibFunc_ZdlPvj, {2, MallocFamily::CPPNew}}, // delete(void*, uint)
456  {LibFunc_ZdlPvm, {2, MallocFamily::CPPNew}}, // delete(void*, ulong)
457  {LibFunc_ZdlPvRKSt9nothrow_t, {2, MallocFamily::CPPNew}}, // delete(void*, nothrow)
458  {LibFunc_ZdlPvSt11align_val_t, {2, MallocFamily::CPPNewAligned}}, // delete(void*, align_val_t)
459  {LibFunc_ZdaPvj, {2, MallocFamily::CPPNewArray}}, // delete[](void*, uint)
460  {LibFunc_ZdaPvm, {2, MallocFamily::CPPNewArray}}, // delete[](void*, ulong)
461  {LibFunc_ZdaPvRKSt9nothrow_t, {2, MallocFamily::CPPNewArray}}, // delete[](void*, nothrow)
462  {LibFunc_ZdaPvSt11align_val_t, {2, MallocFamily::CPPNewArrayAligned}}, // delete[](void*, align_val_t)
463  {LibFunc_msvc_delete_ptr32_int, {2, MallocFamily::MSVCNew}}, // delete(void*, uint)
464  {LibFunc_msvc_delete_ptr64_longlong, {2, MallocFamily::MSVCNew}}, // delete(void*, ulonglong)
465  {LibFunc_msvc_delete_ptr32_nothrow, {2, MallocFamily::MSVCNew}}, // delete(void*, nothrow)
466  {LibFunc_msvc_delete_ptr64_nothrow, {2, MallocFamily::MSVCNew}}, // delete(void*, nothrow)
467  {LibFunc_msvc_delete_array_ptr32_int, {2, MallocFamily::MSVCArrayNew}}, // delete[](void*, uint)
468  {LibFunc_msvc_delete_array_ptr64_longlong, {2, MallocFamily::MSVCArrayNew}}, // delete[](void*, ulonglong)
469  {LibFunc_msvc_delete_array_ptr32_nothrow, {2, MallocFamily::MSVCArrayNew}}, // delete[](void*, nothrow)
470  {LibFunc_msvc_delete_array_ptr64_nothrow, {2, MallocFamily::MSVCArrayNew}}, // delete[](void*, nothrow)
471  {LibFunc___kmpc_free_shared, {2, MallocFamily::KmpcAllocShared}}, // OpenMP Offloading RTL free
472  {LibFunc_ZdlPvSt11align_val_tRKSt9nothrow_t, {3, MallocFamily::CPPNewAligned}}, // delete(void*, align_val_t, nothrow)
473  {LibFunc_ZdaPvSt11align_val_tRKSt9nothrow_t, {3, MallocFamily::CPPNewArrayAligned}}, // delete[](void*, align_val_t, nothrow)
474  {LibFunc_ZdlPvjSt11align_val_t, {3, MallocFamily::CPPNewAligned}}, // delete(void*, unsigned int, align_val_t)
475  {LibFunc_ZdlPvmSt11align_val_t, {3, MallocFamily::CPPNewAligned}}, // delete(void*, unsigned long, align_val_t)
476  {LibFunc_ZdaPvjSt11align_val_t, {3, MallocFamily::CPPNewArrayAligned}}, // delete[](void*, unsigned int, align_val_t)
477  {LibFunc_ZdaPvmSt11align_val_t, {3, MallocFamily::CPPNewArrayAligned}}, // delete[](void*, unsigned long, align_val_t)
478 };
479 // clang-format on
480 
482  const LibFunc TLIFn) {
483  const auto *Iter =
484  find_if(FreeFnData, [TLIFn](const std::pair<LibFunc, FreeFnsTy> &P) {
485  return P.first == TLIFn;
486  });
487  if (Iter == std::end(FreeFnData))
488  return None;
489  return Iter->second;
490 }
491 
493  const TargetLibraryInfo *TLI) {
494  bool IsNoBuiltin;
495  const Function *Callee = getCalledFunction(I, IsNoBuiltin);
496  if (Callee == nullptr || IsNoBuiltin)
497  return None;
498  LibFunc TLIFn;
499  if (!TLI || !TLI->getLibFunc(*Callee, TLIFn) || !TLI->has(TLIFn))
500  return None;
501  const auto AllocData = getAllocationDataForFunction(Callee, AnyAlloc, TLI);
502  if (AllocData.hasValue())
503  return mangledNameForMallocFamily(AllocData.getValue().Family);
504  const auto FreeData = getFreeFunctionDataForFunction(Callee, TLIFn);
505  if (FreeData.hasValue())
506  return mangledNameForMallocFamily(FreeData.getValue().Family);
507  return None;
508 }
509 
510 /// isLibFreeFunction - Returns true if the function is a builtin free()
511 bool llvm::isLibFreeFunction(const Function *F, const LibFunc TLIFn) {
513  if (!FnData.hasValue())
514  return false;
515 
516  // Check free prototype.
517  // FIXME: workaround for PR5130, this will be obsolete when a nobuiltin
518  // attribute will exist.
519  FunctionType *FTy = F->getFunctionType();
520  if (!FTy->getReturnType()->isVoidTy())
521  return false;
522  if (FTy->getNumParams() != FnData->NumParams)
523  return false;
524  if (FTy->getParamType(0) != Type::getInt8PtrTy(F->getContext()))
525  return false;
526 
527  return true;
528 }
529 
530 /// isFreeCall - Returns non-null if the value is a call to the builtin free()
531 const CallInst *llvm::isFreeCall(const Value *I, const TargetLibraryInfo *TLI) {
532  bool IsNoBuiltinCall;
533  const Function *Callee = getCalledFunction(I, IsNoBuiltinCall);
534  if (Callee == nullptr || IsNoBuiltinCall)
535  return nullptr;
536 
537  LibFunc TLIFn;
538  if (!TLI || !TLI->getLibFunc(*Callee, TLIFn) || !TLI->has(TLIFn))
539  return nullptr;
540 
541  return isLibFreeFunction(Callee, TLIFn) ? dyn_cast<CallInst>(I) : nullptr;
542 }
543 
544 
545 //===----------------------------------------------------------------------===//
546 // Utility functions to compute size of objects.
547 //
549  if (Data.second.isNegative() || Data.first.ult(Data.second))
550  return APInt(Data.first.getBitWidth(), 0);
551  return Data.first - Data.second;
552 }
553 
554 /// Compute the size of the object pointed by Ptr. Returns true and the
555 /// object size in Size if successful, and false otherwise.
556 /// If RoundToAlign is true, then Size is rounded up to the alignment of
557 /// allocas, byval arguments, and global variables.
558 bool llvm::getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL,
559  const TargetLibraryInfo *TLI, ObjectSizeOpts Opts) {
560  ObjectSizeOffsetVisitor Visitor(DL, TLI, Ptr->getContext(), Opts);
561  SizeOffsetType Data = Visitor.compute(const_cast<Value*>(Ptr));
562  if (!Visitor.bothKnown(Data))
563  return false;
564 
566  return true;
567 }
568 
570  const DataLayout &DL,
571  const TargetLibraryInfo *TLI,
572  bool MustSucceed) {
573  return lowerObjectSizeCall(ObjectSize, DL, TLI, /*AAResults=*/nullptr,
574  MustSucceed);
575 }
576 
578  const DataLayout &DL,
579  const TargetLibraryInfo *TLI, AAResults *AA,
580  bool MustSucceed) {
581  assert(ObjectSize->getIntrinsicID() == Intrinsic::objectsize &&
582  "ObjectSize must be a call to llvm.objectsize!");
583 
584  bool MaxVal = cast<ConstantInt>(ObjectSize->getArgOperand(1))->isZero();
585  ObjectSizeOpts EvalOptions;
586  EvalOptions.AA = AA;
587 
588  // Unless we have to fold this to something, try to be as accurate as
589  // possible.
590  if (MustSucceed)
591  EvalOptions.EvalMode =
593  else
595 
596  EvalOptions.NullIsUnknownSize =
597  cast<ConstantInt>(ObjectSize->getArgOperand(2))->isOne();
598 
599  auto *ResultType = cast<IntegerType>(ObjectSize->getType());
600  bool StaticOnly = cast<ConstantInt>(ObjectSize->getArgOperand(3))->isZero();
601  if (StaticOnly) {
602  // FIXME: Does it make sense to just return a failure value if the size won't
603  // fit in the output and `!MustSucceed`?
604  uint64_t Size;
605  if (getObjectSize(ObjectSize->getArgOperand(0), Size, DL, TLI, EvalOptions) &&
606  isUIntN(ResultType->getBitWidth(), Size))
607  return ConstantInt::get(ResultType, Size);
608  } else {
609  LLVMContext &Ctx = ObjectSize->getFunction()->getContext();
610  ObjectSizeOffsetEvaluator Eval(DL, TLI, Ctx, EvalOptions);
611  SizeOffsetEvalType SizeOffsetPair =
612  Eval.compute(ObjectSize->getArgOperand(0));
613 
614  if (SizeOffsetPair != ObjectSizeOffsetEvaluator::unknown()) {
616  Builder.SetInsertPoint(ObjectSize);
617 
618  // If we've outside the end of the object, then we can always access
619  // exactly 0 bytes.
620  Value *ResultSize =
621  Builder.CreateSub(SizeOffsetPair.first, SizeOffsetPair.second);
622  Value *UseZero =
623  Builder.CreateICmpULT(SizeOffsetPair.first, SizeOffsetPair.second);
624  ResultSize = Builder.CreateZExtOrTrunc(ResultSize, ResultType);
625  Value *Ret = Builder.CreateSelect(
626  UseZero, ConstantInt::get(ResultType, 0), ResultSize);
627 
628  // The non-constant size expression cannot evaluate to -1.
629  if (!isa<Constant>(SizeOffsetPair.first) ||
630  !isa<Constant>(SizeOffsetPair.second))
631  Builder.CreateAssumption(
632  Builder.CreateICmpNE(Ret, ConstantInt::get(ResultType, -1)));
633 
634  return Ret;
635  }
636  }
637 
638  if (!MustSucceed)
639  return nullptr;
640 
641  return ConstantInt::get(ResultType, MaxVal ? -1ULL : 0);
642 }
643 
644 STATISTIC(ObjectVisitorArgument,
645  "Number of arguments with unsolved size and offset");
646 STATISTIC(ObjectVisitorLoad,
647  "Number of load instructions with unsolved size and offset");
648 
649 APInt ObjectSizeOffsetVisitor::align(APInt Size, MaybeAlign Alignment) {
650  if (Options.RoundToAlign && Alignment)
651  return APInt(IntTyBits, alignTo(Size.getZExtValue(), Alignment));
652  return Size;
653 }
654 
656  const TargetLibraryInfo *TLI,
659  : DL(DL), TLI(TLI), Options(Options) {
660  // Pointer size must be rechecked for each object visited since it could have
661  // a different address space.
662 }
663 
665  unsigned InitialIntTyBits = DL.getIndexTypeSizeInBits(V->getType());
666 
667  // Stripping pointer casts can strip address space casts which can change the
668  // index type size. The invariant is that we use the value type to determine
669  // the index type size and if we stripped address space casts we have to
670  // readjust the APInt as we pass it upwards in order for the APInt to match
671  // the type the caller passed in.
672  APInt Offset(InitialIntTyBits, 0);
674  DL, Offset, /* AllowNonInbounds */ true, /* AllowInvariantGroup */ true);
675 
676  // Later we use the index type size and zero but it will match the type of the
677  // value that is passed to computeImpl.
678  IntTyBits = DL.getIndexTypeSizeInBits(V->getType());
679  Zero = APInt::getZero(IntTyBits);
680 
681  bool IndexTypeSizeChanged = InitialIntTyBits != IntTyBits;
682  if (!IndexTypeSizeChanged && Offset.isZero())
683  return computeImpl(V);
684 
685  // We stripped an address space cast that changed the index type size or we
686  // accumulated some constant offset (or both). Readjust the bit width to match
687  // the argument index type size and apply the offset, as required.
688  SizeOffsetType SOT = computeImpl(V);
689  if (IndexTypeSizeChanged) {
690  if (knownSize(SOT) && !::CheckedZextOrTrunc(SOT.first, InitialIntTyBits))
691  SOT.first = APInt();
692  if (knownOffset(SOT) && !::CheckedZextOrTrunc(SOT.second, InitialIntTyBits))
693  SOT.second = APInt();
694  }
695  // If the computed offset is "unknown" we cannot add the stripped offset.
696  return {SOT.first,
697  SOT.second.getBitWidth() > 1 ? SOT.second + Offset : SOT.second};
698 }
699 
700 SizeOffsetType ObjectSizeOffsetVisitor::computeImpl(Value *V) {
701  if (Instruction *I = dyn_cast<Instruction>(V)) {
702  // If we have already seen this instruction, bail out. Cycles can happen in
703  // unreachable code after constant propagation.
704  if (!SeenInsts.insert(I).second)
705  return unknown();
706 
707  return visit(*I);
708  }
709  if (Argument *A = dyn_cast<Argument>(V))
710  return visitArgument(*A);
711  if (ConstantPointerNull *P = dyn_cast<ConstantPointerNull>(V))
712  return visitConstantPointerNull(*P);
713  if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V))
714  return visitGlobalAlias(*GA);
715  if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
716  return visitGlobalVariable(*GV);
717  if (UndefValue *UV = dyn_cast<UndefValue>(V))
718  return visitUndefValue(*UV);
719 
720  LLVM_DEBUG(dbgs() << "ObjectSizeOffsetVisitor::compute() unhandled value: "
721  << *V << '\n');
722  return unknown();
723 }
724 
725 bool ObjectSizeOffsetVisitor::CheckedZextOrTrunc(APInt &I) {
726  return ::CheckedZextOrTrunc(I, IntTyBits);
727 }
728 
730  if (!I.getAllocatedType()->isSized())
731  return unknown();
732 
733  TypeSize ElemSize = DL.getTypeAllocSize(I.getAllocatedType());
734  if (ElemSize.isScalable() && Options.EvalMode != ObjectSizeOpts::Mode::Min)
735  return unknown();
736  APInt Size(IntTyBits, ElemSize.getKnownMinSize());
737  if (!I.isArrayAllocation())
738  return std::make_pair(align(Size, I.getAlign()), Zero);
739 
740  Value *ArraySize = I.getArraySize();
741  if (const ConstantInt *C = dyn_cast<ConstantInt>(ArraySize)) {
742  APInt NumElems = C->getValue();
743  if (!CheckedZextOrTrunc(NumElems))
744  return unknown();
745 
746  bool Overflow;
747  Size = Size.umul_ov(NumElems, Overflow);
748  return Overflow ? unknown()
749  : std::make_pair(align(Size, I.getAlign()), Zero);
750  }
751  return unknown();
752 }
753 
755  Type *MemoryTy = A.getPointeeInMemoryValueType();
756  // No interprocedural analysis is done at the moment.
757  if (!MemoryTy|| !MemoryTy->isSized()) {
758  ++ObjectVisitorArgument;
759  return unknown();
760  }
761 
762  APInt Size(IntTyBits, DL.getTypeAllocSize(MemoryTy));
763  return std::make_pair(align(Size, A.getParamAlign()), Zero);
764 }
765 
767  auto Mapper = [](const Value *V) { return V; };
768  if (Optional<APInt> Size = getAllocSize(&CB, TLI, Mapper))
769  return std::make_pair(*Size, Zero);
770  return unknown();
771 }
772 
775  // If null is unknown, there's nothing we can do. Additionally, non-zero
776  // address spaces can make use of null, so we don't presume to know anything
777  // about that.
778  //
779  // TODO: How should this work with address space casts? We currently just drop
780  // them on the floor, but it's unclear what we should do when a NULL from
781  // addrspace(1) gets casted to addrspace(0) (or vice-versa).
782  if (Options.NullIsUnknownSize || CPN.getType()->getAddressSpace())
783  return unknown();
784  return std::make_pair(Zero, Zero);
785 }
786 
789  return unknown();
790 }
791 
794  // Easy cases were already folded by previous passes.
795  return unknown();
796 }
797 
799  if (GA.isInterposable())
800  return unknown();
801  return compute(GA.getAliasee());
802 }
803 
805  if (!GV.hasDefinitiveInitializer())
806  return unknown();
807 
808  APInt Size(IntTyBits, DL.getTypeAllocSize(GV.getValueType()));
809  return std::make_pair(align(Size, GV.getAlign()), Zero);
810 }
811 
813  // clueless
814  return unknown();
815 }
816 
817 SizeOffsetType ObjectSizeOffsetVisitor::findLoadSizeOffset(
820  unsigned &ScannedInstCount) {
821  constexpr unsigned MaxInstsToScan = 128;
822 
823  auto Where = VisitedBlocks.find(&BB);
824  if (Where != VisitedBlocks.end())
825  return Where->second;
826 
827  auto Unknown = [this, &BB, &VisitedBlocks]() {
828  return VisitedBlocks[&BB] = unknown();
829  };
830  auto Known = [&BB, &VisitedBlocks](SizeOffsetType SO) {
831  return VisitedBlocks[&BB] = SO;
832  };
833 
834  do {
835  Instruction &I = *From;
836 
837  if (I.isDebugOrPseudoInst())
838  continue;
839 
840  if (++ScannedInstCount > MaxInstsToScan)
841  return Unknown();
842 
843  if (!I.mayWriteToMemory())
844  continue;
845 
846  if (auto *SI = dyn_cast<StoreInst>(&I)) {
847  AliasResult AR =
848  Options.AA->alias(SI->getPointerOperand(), Load.getPointerOperand());
849  switch ((AliasResult::Kind)AR) {
851  continue;
853  if (SI->getValueOperand()->getType()->isPointerTy())
854  return Known(compute(SI->getValueOperand()));
855  else
856  return Unknown(); // No handling of non-pointer values by `compute`.
857  default:
858  return Unknown();
859  }
860  }
861 
862  if (auto *CB = dyn_cast<CallBase>(&I)) {
864  // Bail out on indirect call.
865  if (!Callee)
866  return Unknown();
867 
868  LibFunc TLIFn;
869  if (!TLI || !TLI->getLibFunc(*CB->getCalledFunction(), TLIFn) ||
870  !TLI->has(TLIFn))
871  return Unknown();
872 
873  // TODO: There's probably more interesting case to support here.
874  if (TLIFn != LibFunc_posix_memalign)
875  return Unknown();
876 
877  AliasResult AR =
878  Options.AA->alias(CB->getOperand(0), Load.getPointerOperand());
879  switch ((AliasResult::Kind)AR) {
881  continue;
883  break;
884  default:
885  return Unknown();
886  }
887 
888  // Is the error status of posix_memalign correctly checked? If not it
889  // would be incorrect to assume it succeeds and load doesn't see the
890  // previous value.
892  ICmpInst::ICMP_EQ, CB, ConstantInt::get(CB->getType(), 0), &Load, DL);
893  if (!Checked || !*Checked)
894  return Unknown();
895 
896  Value *Size = CB->getOperand(2);
897  auto *C = dyn_cast<ConstantInt>(Size);
898  if (!C)
899  return Unknown();
900 
901  return Known({C->getValue(), APInt(C->getValue().getBitWidth(), 0)});
902  }
903 
904  return Unknown();
905  } while (From-- != BB.begin());
906 
907  SmallVector<SizeOffsetType> PredecessorSizeOffsets;
908  for (auto *PredBB : predecessors(&BB)) {
909  PredecessorSizeOffsets.push_back(findLoadSizeOffset(
910  Load, *PredBB, BasicBlock::iterator(PredBB->getTerminator()),
911  VisitedBlocks, ScannedInstCount));
912  if (!bothKnown(PredecessorSizeOffsets.back()))
913  return Unknown();
914  }
915 
916  if (PredecessorSizeOffsets.empty())
917  return Unknown();
918 
919  return Known(std::accumulate(PredecessorSizeOffsets.begin() + 1,
920  PredecessorSizeOffsets.end(),
921  PredecessorSizeOffsets.front(),
923  return combineSizeOffset(LHS, RHS);
924  }));
925 }
926 
928  if (!Options.AA) {
929  ++ObjectVisitorLoad;
930  return unknown();
931  }
932 
934  unsigned ScannedInstCount = 0;
935  SizeOffsetType SO =
936  findLoadSizeOffset(LI, *LI.getParent(), BasicBlock::iterator(LI),
937  VisitedBlocks, ScannedInstCount);
938  if (!bothKnown(SO))
939  ++ObjectVisitorLoad;
940  return SO;
941 }
942 
943 SizeOffsetType ObjectSizeOffsetVisitor::combineSizeOffset(SizeOffsetType LHS,
945  if (!bothKnown(LHS) || !bothKnown(RHS))
946  return unknown();
947 
948  switch (Options.EvalMode) {
955  : unknown();
956  }
957  llvm_unreachable("missing an eval mode");
958 }
959 
961  auto IncomingValues = PN.incoming_values();
962  return std::accumulate(IncomingValues.begin() + 1, IncomingValues.end(),
963  compute(*IncomingValues.begin()),
964  [this](SizeOffsetType LHS, Value *VRHS) {
965  return combineSizeOffset(LHS, compute(VRHS));
966  });
967 }
968 
970  return combineSizeOffset(compute(I.getTrueValue()),
971  compute(I.getFalseValue()));
972 }
973 
975  return std::make_pair(Zero, Zero);
976 }
977 
979  LLVM_DEBUG(dbgs() << "ObjectSizeOffsetVisitor unknown instruction:" << I
980  << '\n');
981  return unknown();
982 }
983 
985  const DataLayout &DL, const TargetLibraryInfo *TLI, LLVMContext &Context,
986  ObjectSizeOpts EvalOpts)
987  : DL(DL), TLI(TLI), Context(Context),
990  [&](Instruction *I) { InsertedInstructions.insert(I); })),
991  EvalOpts(EvalOpts) {
992  // IntTy and Zero must be set for each compute() since the address space may
993  // be different for later objects.
994 }
995 
997  // XXX - Are vectors of pointers possible here?
998  IntTy = cast<IntegerType>(DL.getIndexType(V->getType()));
999  Zero = ConstantInt::get(IntTy, 0);
1000 
1001  SizeOffsetEvalType Result = compute_(V);
1002 
1003  if (!bothKnown(Result)) {
1004  // Erase everything that was computed in this iteration from the cache, so
1005  // that no dangling references are left behind. We could be a bit smarter if
1006  // we kept a dependency graph. It's probably not worth the complexity.
1007  for (const Value *SeenVal : SeenVals) {
1008  CacheMapTy::iterator CacheIt = CacheMap.find(SeenVal);
1009  // non-computable results can be safely cached
1010  if (CacheIt != CacheMap.end() && anyKnown(CacheIt->second))
1011  CacheMap.erase(CacheIt);
1012  }
1013 
1014  // Erase any instructions we inserted as part of the traversal.
1015  for (Instruction *I : InsertedInstructions) {
1016  I->replaceAllUsesWith(UndefValue::get(I->getType()));
1017  I->eraseFromParent();
1018  }
1019  }
1020 
1021  SeenVals.clear();
1022  InsertedInstructions.clear();
1023  return Result;
1024 }
1025 
1026 SizeOffsetEvalType ObjectSizeOffsetEvaluator::compute_(Value *V) {
1027  ObjectSizeOffsetVisitor Visitor(DL, TLI, Context, EvalOpts);
1028  SizeOffsetType Const = Visitor.compute(V);
1029  if (Visitor.bothKnown(Const))
1030  return std::make_pair(ConstantInt::get(Context, Const.first),
1031  ConstantInt::get(Context, Const.second));
1032 
1033  V = V->stripPointerCasts();
1034 
1035  // Check cache.
1036  CacheMapTy::iterator CacheIt = CacheMap.find(V);
1037  if (CacheIt != CacheMap.end())
1038  return CacheIt->second;
1039 
1040  // Always generate code immediately before the instruction being
1041  // processed, so that the generated code dominates the same BBs.
1042  BuilderTy::InsertPointGuard Guard(Builder);
1043  if (Instruction *I = dyn_cast<Instruction>(V))
1044  Builder.SetInsertPoint(I);
1045 
1046  // Now compute the size and offset.
1047  SizeOffsetEvalType Result;
1048 
1049  // Record the pointers that were handled in this run, so that they can be
1050  // cleaned later if something fails. We also use this set to break cycles that
1051  // can occur in dead code.
1052  if (!SeenVals.insert(V).second) {
1053  Result = unknown();
1054  } else if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
1055  Result = visitGEPOperator(*GEP);
1056  } else if (Instruction *I = dyn_cast<Instruction>(V)) {
1057  Result = visit(*I);
1058  } else if (isa<Argument>(V) ||
1059  (isa<ConstantExpr>(V) &&
1060  cast<ConstantExpr>(V)->getOpcode() == Instruction::IntToPtr) ||
1061  isa<GlobalAlias>(V) ||
1062  isa<GlobalVariable>(V)) {
1063  // Ignore values where we cannot do more than ObjectSizeVisitor.
1064  Result = unknown();
1065  } else {
1066  LLVM_DEBUG(
1067  dbgs() << "ObjectSizeOffsetEvaluator::compute() unhandled value: " << *V
1068  << '\n');
1069  Result = unknown();
1070  }
1071 
1072  // Don't reuse CacheIt since it may be invalid at this point.
1073  CacheMap[V] = Result;
1074  return Result;
1075 }
1076 
1078  if (!I.getAllocatedType()->isSized())
1079  return unknown();
1080 
1081  // must be a VLA
1082  assert(I.isArrayAllocation());
1083 
1084  // If needed, adjust the alloca's operand size to match the pointer size.
1085  // Subsequent math operations expect the types to match.
1086  Value *ArraySize = Builder.CreateZExtOrTrunc(
1087  I.getArraySize(), DL.getIntPtrType(I.getContext()));
1088  assert(ArraySize->getType() == Zero->getType() &&
1089  "Expected zero constant to have pointer type");
1090 
1091  Value *Size = ConstantInt::get(ArraySize->getType(),
1092  DL.getTypeAllocSize(I.getAllocatedType()));
1093  Size = Builder.CreateMul(Size, ArraySize);
1094  return std::make_pair(Size, Zero);
1095 }
1096 
1098  Optional<AllocFnsTy> FnData = getAllocationSize(&CB, TLI);
1099  if (!FnData)
1100  return unknown();
1101 
1102  // Handle strdup-like functions separately.
1103  if (FnData->AllocTy == StrDupLike) {
1104  // TODO: implement evaluation of strdup/strndup
1105  return unknown();
1106  }
1107 
1108  Value *FirstArg = CB.getArgOperand(FnData->FstParam);
1109  FirstArg = Builder.CreateZExtOrTrunc(FirstArg, IntTy);
1110  if (FnData->SndParam < 0)
1111  return std::make_pair(FirstArg, Zero);
1112 
1113  Value *SecondArg = CB.getArgOperand(FnData->SndParam);
1114  SecondArg = Builder.CreateZExtOrTrunc(SecondArg, IntTy);
1115  Value *Size = Builder.CreateMul(FirstArg, SecondArg);
1116  return std::make_pair(Size, Zero);
1117 }
1118 
1121  return unknown();
1122 }
1123 
1126  return unknown();
1127 }
1128 
1131  SizeOffsetEvalType PtrData = compute_(GEP.getPointerOperand());
1132  if (!bothKnown(PtrData))
1133  return unknown();
1134 
1135  Value *Offset = EmitGEPOffset(&Builder, DL, &GEP, /*NoAssumptions=*/true);
1136  Offset = Builder.CreateAdd(PtrData.second, Offset);
1137  return std::make_pair(PtrData.first, Offset);
1138 }
1139 
1141  // clueless
1142  return unknown();
1143 }
1144 
1146  return unknown();
1147 }
1148 
1150  // Create 2 PHIs: one for size and another for offset.
1151  PHINode *SizePHI = Builder.CreatePHI(IntTy, PHI.getNumIncomingValues());
1152  PHINode *OffsetPHI = Builder.CreatePHI(IntTy, PHI.getNumIncomingValues());
1153 
1154  // Insert right away in the cache to handle recursive PHIs.
1155  CacheMap[&PHI] = std::make_pair(SizePHI, OffsetPHI);
1156 
1157  // Compute offset/size for each PHI incoming pointer.
1158  for (unsigned i = 0, e = PHI.getNumIncomingValues(); i != e; ++i) {
1160  SizeOffsetEvalType EdgeData = compute_(PHI.getIncomingValue(i));
1161 
1162  if (!bothKnown(EdgeData)) {
1163  OffsetPHI->replaceAllUsesWith(UndefValue::get(IntTy));
1164  OffsetPHI->eraseFromParent();
1165  InsertedInstructions.erase(OffsetPHI);
1166  SizePHI->replaceAllUsesWith(UndefValue::get(IntTy));
1167  SizePHI->eraseFromParent();
1168  InsertedInstructions.erase(SizePHI);
1169  return unknown();
1170  }
1171  SizePHI->addIncoming(EdgeData.first, PHI.getIncomingBlock(i));
1172  OffsetPHI->addIncoming(EdgeData.second, PHI.getIncomingBlock(i));
1173  }
1174 
1175  Value *Size = SizePHI, *Offset = OffsetPHI;
1176  if (Value *Tmp = SizePHI->hasConstantValue()) {
1177  Size = Tmp;
1178  SizePHI->replaceAllUsesWith(Size);
1179  SizePHI->eraseFromParent();
1180  InsertedInstructions.erase(SizePHI);
1181  }
1182  if (Value *Tmp = OffsetPHI->hasConstantValue()) {
1183  Offset = Tmp;
1184  OffsetPHI->replaceAllUsesWith(Offset);
1185  OffsetPHI->eraseFromParent();
1186  InsertedInstructions.erase(OffsetPHI);
1187  }
1188  return std::make_pair(Size, Offset);
1189 }
1190 
1192  SizeOffsetEvalType TrueSide = compute_(I.getTrueValue());
1193  SizeOffsetEvalType FalseSide = compute_(I.getFalseValue());
1194 
1195  if (!bothKnown(TrueSide) || !bothKnown(FalseSide))
1196  return unknown();
1197  if (TrueSide == FalseSide)
1198  return TrueSide;
1199 
1200  Value *Size = Builder.CreateSelect(I.getCondition(), TrueSide.first,
1201  FalseSide.first);
1202  Value *Offset = Builder.CreateSelect(I.getCondition(), TrueSide.second,
1203  FalseSide.second);
1204  return std::make_pair(Size, Offset);
1205 }
1206 
1208  LLVM_DEBUG(dbgs() << "ObjectSizeOffsetEvaluator unknown instruction:" << I
1209  << '\n');
1210  return unknown();
1211 }
llvm::Check::Size
@ Size
Definition: FileCheck.h:76
llvm::CallBase::getArgOperandWithAttribute
Value * getArgOperandWithAttribute(Attribute::AttrKind Kind) const
If one of the arguments has the specified attribute, returns its operand value.
Definition: Instructions.cpp:328
i
i
Definition: README.txt:29
llvm::ObjectSizeOffsetEvaluator::unknown
static SizeOffsetEvalType unknown()
Definition: MemoryBuiltins.h:270
llvm::alignTo
uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
Definition: Alignment.h:148
llvm::SizeOffsetType
std::pair< APInt, APInt > SizeOffsetType
Definition: MemoryBuiltins.h:181
llvm::Argument
This class represents an incoming formal argument to a Function.
Definition: Argument.h:28
llvm::Type::isSized
bool isSized(SmallPtrSetImpl< Type * > *Visited=nullptr) const
Return true if it makes sense to take the size of this type.
Definition: Type.h:264
getAllocationSize
static Optional< AllocFnsTy > getAllocationSize(const Value *V, const TargetLibraryInfo *TLI)
Definition: MemoryBuiltins.cpp:236
llvm::ObjectSizeOffsetVisitor::visitGlobalAlias
SizeOffsetType visitGlobalAlias(GlobalAlias &GA)
Definition: MemoryBuiltins.cpp:798
MathExtras.h
llvm::IRBuilderBase::SetInsertPoint
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Definition: IRBuilder.h:179
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
AllocFnsTy::NumParams
unsigned NumParams
Definition: MemoryBuiltins.cpp:105
FreeFnData
static const std::pair< LibFunc, FreeFnsTy > FreeFnData[]
Definition: MemoryBuiltins.cpp:446
llvm::Instruction::getModule
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:65
llvm::CmpInst::ICMP_EQ
@ ICMP_EQ
equal
Definition: InstrTypes.h:740
llvm::DataLayout::getIndexTypeSizeInBits
unsigned getIndexTypeSizeInBits(Type *Ty) const
Layout size of the index used in GEP calculation.
Definition: DataLayout.cpp:732
Optional.h
llvm::PHINode::incoming_values
op_range incoming_values()
Definition: Instructions.h:2750
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::Type::getInt8PtrTy
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
Definition: Type.cpp:291
MallocFamily::CPPNewArray
@ CPPNewArray
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
IntrinsicInst.h
getFreeFunctionDataForFunction
Optional< FreeFnsTy > getFreeFunctionDataForFunction(const Function *Callee, const LibFunc TLIFn)
Definition: MemoryBuiltins.cpp:481
MallocFamily::Malloc
@ Malloc
llvm::ExtractElementInst
This instruction extracts a single (scalar) element from a VectorType value.
Definition: Instructions.h:1872
llvm::Function
Definition: Function.h:60
llvm::Attribute
Definition: Attributes.h:52
AllocFnsTy::AlignParam
int AlignParam
Definition: MemoryBuiltins.cpp:109
TargetFolder.h
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::IntrinsicInst::getIntrinsicID
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
Definition: IntrinsicInst.h:53
AllocFnsTy::Family
MallocFamily Family
Definition: MemoryBuiltins.cpp:111
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
Statistic.h
llvm::ObjectSizeOffsetEvaluator::compute
SizeOffsetEvalType compute(Value *V)
Definition: MemoryBuiltins.cpp:996
llvm::GlobalObject::getAlign
MaybeAlign getAlign() const
Returns the alignment of the given variable or function.
Definition: GlobalObject.h:79
llvm::ObjectSizeOffsetVisitor::visitExtractValueInst
SizeOffsetType visitExtractValueInst(ExtractValueInst &I)
Definition: MemoryBuiltins.cpp:793
llvm::IRBuilder
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2489
llvm::GlobalVariable
Definition: GlobalVariable.h:39
llvm::PointerType::getAddressSpace
unsigned getAddressSpace() const
Return the address space of the Pointer type.
Definition: DerivedTypes.h:682
llvm::ObjectSizeOffsetEvaluator::visitSelectInst
SizeOffsetEvalType visitSelectInst(SelectInst &I)
Definition: MemoryBuiltins.cpp:1191
llvm::ObjectSizeOffsetEvaluator::visitGEPOperator
SizeOffsetEvalType visitGEPOperator(GEPOperator &GEP)
Definition: MemoryBuiltins.cpp:1130
llvm::SmallDenseMap
Definition: DenseMap.h:882
llvm::GlobalAlias
Definition: GlobalAlias.h:28
ValueTracking.h
llvm::getInitialValueOfAllocation
Constant * getInitialValueOfAllocation(const CallBase *Alloc, const TargetLibraryInfo *TLI, Type *Ty)
If this allocation function initializes memory to a fixed value, return said value in the requested t...
Definition: MemoryBuiltins.cpp:423
isMallocLikeFn
static bool isMallocLikeFn(const Value *V, const TargetLibraryInfo *TLI)
Tests if a value is a call or invoke to a library function that allocates uninitialized memory (such ...
Definition: MemoryBuiltins.cpp:282
llvm::DenseMapBase::erase
bool erase(const KeyT &Val)
Definition: DenseMap.h:304
APInt.h
llvm::Function::getContext
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function.
Definition: Function.cpp:319
CallocLike
@ CallocLike
Definition: MemoryBuiltins.cpp:58
llvm::DataLayout::getIndexType
Type * getIndexType(Type *PtrTy) const
Returns the type of a GEP index.
Definition: DataLayout.cpp:869
llvm::DenseMapIterator
Definition: DenseMap.h:57
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
MemoryBuiltins.h
llvm::ObjectSizeOpts::NullIsUnknownSize
bool NullIsUnknownSize
If this is true, null pointers in address space 0 will be treated as though they can't be evaluated.
Definition: MemoryBuiltins.h:155
AllocFnsTy
Definition: MemoryBuiltins.cpp:103
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:235
FreeFnsTy::Family
MallocFamily Family
Definition: MemoryBuiltins.cpp:442
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
llvm::Optional
Definition: APInt.h:33
llvm::ObjectSizeOffsetEvaluator::visitCallBase
SizeOffsetEvalType visitCallBase(CallBase &CB)
Definition: MemoryBuiltins.cpp:1097
llvm::Value::stripAndAccumulateConstantOffsets
const Value * stripAndAccumulateConstantOffsets(const DataLayout &DL, APInt &Offset, bool AllowNonInbounds, bool AllowInvariantGroup=false, function_ref< bool(Value &Value, APInt &Offset)> ExternalAnalysis=nullptr) const
Accumulate the constant offset this value has compared to a base pointer.
llvm::AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:81
llvm::ObjectSizeOpts::RoundToAlign
bool RoundToAlign
Whether to round the result up to the alignment of allocas, byval arguments, and global variables.
Definition: MemoryBuiltins.h:151
Operator.h
llvm::FunctionType::getNumParams
unsigned getNumParams() const
Return the number of fixed parameters this function type requires.
Definition: DerivedTypes.h:139
llvm::MipsISD::Ret
@ Ret
Definition: MipsISelLowering.h:119
STLExtras.h
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
getAllocationData
static Optional< AllocFnsTy > getAllocationData(const Value *V, AllocType AllocTy, const TargetLibraryInfo *TLI)
Definition: MemoryBuiltins.cpp:216
llvm::ObjectSizeOffsetEvaluator::visitLoadInst
SizeOffsetEvalType visitLoadInst(LoadInst &I)
Definition: MemoryBuiltins.cpp:1145
llvm::EmitGEPOffset
Value * EmitGEPOffset(IRBuilderTy *Builder, const DataLayout &DL, User *GEP, bool NoAssumptions=false)
Given a getelementptr instruction/constantexpr, emit the code necessary to compute the offset from th...
Definition: Local.h:29
llvm::LinearPolySize::isScalable
bool isScalable() const
Returns whether the size is scaled by a runtime quantity (vscale).
Definition: TypeSize.h:298
llvm::Data
@ Data
Definition: SIMachineScheduler.h:55
llvm::APInt::getZero
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
Definition: APInt.h:177
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
AliasAnalysis.h
llvm::Optional::hasValue
constexpr bool hasValue() const
Definition: Optional.h:283
Context
LLVMContext & Context
Definition: NVVMIntrRange.cpp:66
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::ObjectSizeOffsetEvaluator::visitIntToPtrInst
SizeOffsetEvalType visitIntToPtrInst(IntToPtrInst &)
Definition: MemoryBuiltins.cpp:1140
llvm::isAllocationFn
bool isAllocationFn(const Value *V, const TargetLibraryInfo *TLI)
Tests if a value is a call or invoke to a library function that allocates or reallocates memory (eith...
Definition: MemoryBuiltins.cpp:272
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:186
llvm::ConstantPointerNull
A constant pointer value that points to null.
Definition: Constants.h:534
Instruction.h
MallocOrCallocLike
@ MallocOrCallocLike
Definition: MemoryBuiltins.cpp:62
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::ObjectSizeOffsetVisitor::bothKnown
static bool bothKnown(const SizeOffsetType &SizeOffset)
Definition: MemoryBuiltins.h:214
llvm::IRBuilderBase::CreateMul
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1234
Constants.h
llvm::PHINode::getIncomingValue
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
Definition: Instructions.h:2760
llvm::AAResults
Definition: AliasAnalysis.h:511
llvm::LibFunc
LibFunc
Definition: TargetLibraryInfo.h:35
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::ObjectSizeOffsetVisitor::visitIntToPtrInst
SizeOffsetType visitIntToPtrInst(IntToPtrInst &)
Definition: MemoryBuiltins.cpp:812
llvm::ObjectSizeOffsetEvaluator::ObjectSizeOffsetEvaluator
ObjectSizeOffsetEvaluator(const DataLayout &DL, const TargetLibraryInfo *TLI, LLVMContext &Context, ObjectSizeOpts EvalOpts={})
Definition: MemoryBuiltins.cpp:984
llvm::CallBase::getCalledFunction
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
Definition: InstrTypes.h:1396
llvm::ObjectSizeOpts::Mode::Exact
@ Exact
Fail to evaluate an unknown condition.
MallocFamily::CPPNewAligned
@ CPPNewAligned
getOpcode
static Optional< unsigned > getOpcode(ArrayRef< VPValue * > Values)
Returns the opcode of Values or ~0 if they do not all agree.
Definition: VPlanSLP.cpp:190
llvm::ms_demangle::QualifierMangleMode::Result
@ Result
TargetLibraryInfo.h
llvm::BasicBlock::getFirstInsertionPt
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
Definition: BasicBlock.cpp:246
FreeFnsTy::NumParams
unsigned NumParams
Definition: MemoryBuiltins.cpp:440
llvm::MaybeAlign
This struct is a compact representation of a valid (power of two) or undefined (0) alignment.
Definition: Alignment.h:109
llvm::isUIntN
bool isUIntN(unsigned N, uint64_t x)
Checks if an unsigned integer fits into the given (dynamic) bit width.
Definition: MathExtras.h:455
llvm::TargetLibraryInfo::getLibFunc
bool getLibFunc(StringRef funcName, LibFunc &F) const
Searches for a particular function name.
Definition: TargetLibraryInfo.h:294
llvm::ObjectSizeOffsetVisitor::visitGlobalVariable
SizeOffsetType visitGlobalVariable(GlobalVariable &GV)
Definition: MemoryBuiltins.cpp:804
llvm::Instruction
Definition: Instruction.h:42
llvm::ObjectSizeOffsetVisitor::visitAllocaInst
SizeOffsetType visitAllocaInst(AllocaInst &I)
Definition: MemoryBuiltins.cpp:729
llvm::ObjectSizeOffsetEvaluator::visitExtractElementInst
SizeOffsetEvalType visitExtractElementInst(ExtractElementInst &I)
Definition: MemoryBuiltins.cpp:1120
AnyAlloc
@ AnyAlloc
Definition: MemoryBuiltins.cpp:64
llvm::APInt::getZExtValue
uint64_t getZExtValue() const
Get zero extended value.
Definition: APInt.h:1478
Options
const char LLVMTargetMachineRef LLVMPassBuilderOptionsRef Options
Definition: PassBuilderBindings.cpp:48
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::predecessors
auto predecessors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:30
ReallocLike
@ ReallocLike
Definition: MemoryBuiltins.cpp:59
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1769
llvm::ConstantInt::get
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:919
llvm::ObjectSizeOffsetEvaluator
Evaluate the size and offset of an object pointed to by a Value*.
Definition: MemoryBuiltins.h:249
llvm::FunctionCallee::getFunctionType
FunctionType * getFunctionType()
Definition: DerivedTypes.h:182
llvm::ObjectSizeOffsetEvaluator::visitPHINode
SizeOffsetEvalType visitPHINode(PHINode &PHI)
Definition: MemoryBuiltins.cpp:1149
llvm::getObjectSize
bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL, const TargetLibraryInfo *TLI, ObjectSizeOpts Opts={})
Compute the size of the object pointed by Ptr.
Definition: MemoryBuiltins.cpp:558
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2756
llvm::None
const NoneType None
Definition: None.h:24
Type.h
llvm::Type::isIntegerTy
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:191
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLFunctionalExtras.h:36
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:77
llvm::PHINode::hasConstantValue
Value * hasConstantValue() const
If the specified PHI node always merges together the same value, return the value,...
Definition: Instructions.cpp:152
AlignedAllocLike
@ AlignedAllocLike
Definition: MemoryBuiltins.cpp:57
uint64_t
llvm::pdb::Unknown
@ Unknown
Definition: PDBTypes.h:396
MallocFamily::CPPNewArrayAligned
@ CPPNewArrayAligned
llvm::GlobalVariable::hasDefinitiveInitializer
bool hasDefinitiveInitializer() const
hasDefinitiveInitializer - Whether the global variable has an initializer, and any other instances of...
Definition: GlobalVariable.h:109
AllocFnsTy::SndParam
int SndParam
Definition: MemoryBuiltins.cpp:107
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2814
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
MallocFamily
MallocFamily
Definition: MemoryBuiltins.cpp:67
llvm::ObjectSizeOffsetVisitor::visitUndefValue
SizeOffsetType visitUndefValue(UndefValue &)
Definition: MemoryBuiltins.cpp:974
I
#define I(x, y, z)
Definition: MD5.cpp:58
getCalledFunction
static const Function * getCalledFunction(const Value *V, bool &IsNoBuiltin)
Definition: MemoryBuiltins.cpp:160
llvm::FunctionType::getParamType
Type * getParamType(unsigned i) const
Parameter type accessors.
Definition: DerivedTypes.h:135
OpNewLike
@ OpNewLike
Definition: MemoryBuiltins.cpp:55
llvm::UndefValue
'undef' values are things that do not have specified contents.
Definition: Constants.h:1382
llvm::ObjectSizeOffsetVisitor
Evaluate the size and offset of an object pointed to by a Value* statically.
Definition: MemoryBuiltins.h:185
llvm::lowerObjectSizeCall
Value * lowerObjectSizeCall(IntrinsicInst *ObjectSize, const DataLayout &DL, const TargetLibraryInfo *TLI, bool MustSucceed)
Try to turn a call to @llvm.objectsize into an integer value of the given Type.
Definition: MemoryBuiltins.cpp:569
llvm::IRBuilderBase::CreateSelect
Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
Definition: IRBuilder.cpp:991
MallocOrOpNewLike
@ MallocOrOpNewLike
Definition: MemoryBuiltins.cpp:61
llvm::ObjectSizeOffsetVisitor::visitSelectInst
SizeOffsetType visitSelectInst(SelectInst &I)
Definition: MemoryBuiltins.cpp:969
MallocFamily::CPPNew
@ CPPNew
llvm::InstVisitor< ObjectSizeOffsetVisitor, SizeOffsetType >::visit
void visit(Iterator Start, Iterator End)
Definition: InstVisitor.h:87
llvm::IRBuilderBase::CreateAdd
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1201
llvm::isAllocLikeFn
bool isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI)
Tests if a value is a call or invoke to a library function that allocates memory (either malloc,...
Definition: MemoryBuiltins.cpp:307
MallocLike
@ MallocLike
Definition: MemoryBuiltins.cpp:56
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:152
FreeFnsTy
Definition: MemoryBuiltins.cpp:439
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::ObjectSizeOpts::Mode::Min
@ Min
Evaluate all branches of an unknown condition.
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1737
llvm::TargetLibraryInfo::has
bool has(LibFunc F) const
Tests whether a library function is available.
Definition: TargetLibraryInfo.h:328
function
print Print MemDeps of function
Definition: MemDepPrinter.cpp:82
llvm::Type::isVoidTy
bool isVoidTy() const
Return true if this is 'void'.
Definition: Type.h:139
llvm::IRBuilderCallbackInserter
Provides an 'InsertHelper' that calls a user-provided callback after performing the default insertion...
Definition: IRBuilder.h:75
llvm::GEPOperator
Definition: Operator.h:375
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:651
MallocFamily::VecMalloc
@ VecMalloc
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
MallocFamily::KmpcAllocShared
@ KmpcAllocShared
llvm::IRBuilderBase::CreatePHI
PHINode * CreatePHI(Type *Ty, unsigned NumReservedValues, const Twine &Name="")
Definition: IRBuilder.h:2221
llvm::SmallPtrSetImplBase::clear
void clear()
Definition: SmallPtrSet.h:95
llvm::ObjectSizeOffsetEvaluator::visitAllocaInst
SizeOffsetEvalType visitAllocaInst(AllocaInst &I)
Definition: MemoryBuiltins.cpp:1077
llvm::ObjectSizeOpts::AA
AAResults * AA
If set, used for more accurate evaluation.
Definition: MemoryBuiltins.h:157
None.h
DataLayout.h
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::Instruction::getFunction
const Function * getFunction() const
Return the function this instruction belongs to.
Definition: Instruction.cpp:69
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:529
llvm::AliasResult::NoAlias
@ NoAlias
The two locations do not alias at all.
Definition: AliasAnalysis.h:99
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:991
llvm::IRBuilderBase::InsertPointGuard
Definition: IRBuilder.h:350
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::AliasResult::MustAlias
@ MustAlias
The two locations precisely alias each other.
Definition: AliasAnalysis.h:106
Local.h
llvm::ObjectSizeOpts
Various options to control the behavior of getObjectSize.
Definition: MemoryBuiltins.h:135
llvm::GlobalAlias::getAliasee
const Constant * getAliasee() const
Definition: GlobalAlias.h:84
AllocationFnData
static const std::pair< LibFunc, AllocFnsTy > AllocationFnData[]
Definition: MemoryBuiltins.cpp:117
llvm::Type::getContext
LLVMContext & getContext() const
Return the LLVMContext in which this type was uniqued.
Definition: Type.h:128
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:176
llvm::ObjectSizeOpts::Mode::Max
@ Max
Same as Min, except we pick the maximum size of all of the branches.
llvm::ObjectSizeOffsetVisitor::visitLoadInst
SizeOffsetType visitLoadInst(LoadInst &I)
Definition: MemoryBuiltins.cpp:927
llvm::Value::stripPointerCasts
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
Definition: Value.cpp:682
Argument.h
llvm::find_if
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1632
llvm::ObjectSizeOffsetVisitor::visitInstruction
SizeOffsetType visitInstruction(Instruction &I)
Definition: MemoryBuiltins.cpp:978
Callee
amdgpu Simplify well known AMD library false FunctionCallee Callee
Definition: AMDGPULibCalls.cpp:186
CheckedZextOrTrunc
static bool CheckedZextOrTrunc(APInt &I, unsigned IntTyBits)
When we're compiling N-bit code, and the user uses parameters that are greater than N bits (e....
Definition: MemoryBuiltins.cpp:349
llvm::GlobalValue::isInterposable
bool isInterposable() const
Return true if this global's definition can be substituted with an arbitrary definition at link time ...
Definition: Globals.cpp:98
llvm::GetStringLength
uint64_t GetStringLength(const Value *V, unsigned CharSize=8)
If we can compute the length of the string pointed to by the specified pointer, return 'len+1'.
Definition: ValueTracking.cpp:4276
mangledNameForMallocFamily
StringRef mangledNameForMallocFamily(const MallocFamily &Family)
Definition: MemoryBuiltins.cpp:79
Attributes.h
llvm::DataLayout::getIntPtrType
IntegerType * getIntPtrType(LLVMContext &C, unsigned AddressSpace=0) const
Returns an integer type with size at least as big as that of a pointer in the given address space.
Definition: DataLayout.cpp:842
llvm::TargetFolder
TargetFolder - Create constants with target dependent folding.
Definition: TargetFolder.h:33
llvm::Constant::getNullValue
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:350
llvm::ObjectSizeOffsetVisitor::visitCallBase
SizeOffsetType visitCallBase(CallBase &CB)
Definition: MemoryBuiltins.cpp:766
llvm::ObjectSizeOffsetVisitor::visitArgument
SizeOffsetType visitArgument(Argument &A)
Definition: MemoryBuiltins.cpp:754
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end
iterator end()
Definition: DenseMap.h:84
llvm::getAllocationFamily
Optional< StringRef > getAllocationFamily(const Value *I, const TargetLibraryInfo *TLI)
If a function is part of an allocation family (e.g.
Definition: MemoryBuiltins.cpp:492
GlobalVariable.h
llvm::ObjectSizeOpts::EvalMode
Mode EvalMode
How we want to evaluate this object's size.
Definition: MemoryBuiltins.h:148
llvm::ExtractValueInst
This instruction extracts a struct member or array element value from an aggregate value.
Definition: Instructions.h:2411
llvm::TypeSize
Definition: TypeSize.h:421
llvm::getAllocAlignment
Value * getAllocAlignment(const CallBase *V, const TargetLibraryInfo *TLI)
Gets the alignment argument for an aligned_alloc-like function, using either built-in knowledge based...
Definition: MemoryBuiltins.cpp:335
llvm::SizeOffsetEvalType
std::pair< Value *, Value * > SizeOffsetEvalType
Definition: MemoryBuiltins.h:245
Casting.h
Function.h
llvm::ObjectSizeOffsetVisitor::knownOffset
static bool knownOffset(const SizeOffsetType &SizeOffset)
Definition: MemoryBuiltins.h:210
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:222
llvm::AAResults::alias
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
The main low level interface to the alias analysis implementation.
Definition: AliasAnalysis.cpp:119
isCallocLikeFn
static bool isCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI)
Tests if a value is a call or invoke to a library function that allocates zero-filled memory (such as...
Definition: MemoryBuiltins.cpp:295
llvm::IntToPtrInst
This class represents a cast from an integer to a pointer.
Definition: Instructions.h:5131
GlobalAlias.h
AllocType
AllocType
Definition: MemoryBuiltins.cpp:54
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:46
llvm::AliasResult::Kind
Kind
Definition: AliasAnalysis.h:93
AA
llvm::ObjectSizeOffsetVisitor::compute
SizeOffsetType compute(Value *V)
Definition: MemoryBuiltins.cpp:664
llvm::ObjectSizeOffsetVisitor::visitConstantPointerNull
SizeOffsetType visitConstantPointerNull(ConstantPointerNull &)
Definition: MemoryBuiltins.cpp:774
Instructions.h
getSizeWithOverflow
static APInt getSizeWithOverflow(const SizeOffsetType &Data)
Definition: MemoryBuiltins.cpp:548
llvm::getAllocSize
Optional< APInt > getAllocSize(const CallBase *CB, const TargetLibraryInfo *TLI, std::function< const Value *(const Value *)> Mapper)
Return the size of the requested allocation.
Definition: MemoryBuiltins.cpp:361
llvm::DenseMapBase< DenseMap< const Value *, WeakEvalType, DenseMapInfo< const Value * >, llvm::detail::DenseMapPair< const Value *, WeakEvalType > >, const Value *, WeakEvalType, DenseMapInfo< const Value * >, llvm::detail::DenseMapPair< const Value *, WeakEvalType > >::iterator
DenseMapIterator< const Value *, WeakEvalType, DenseMapInfo< const Value * >, llvm::detail::DenseMapPair< const Value *, WeakEvalType > > iterator
Definition: DenseMap.h:71
llvm::isImpliedByDomCondition
Optional< bool > isImpliedByDomCondition(const Value *Cond, const Instruction *ContextI, const DataLayout &DL)
Return the boolean condition value in the context of the given instruction if it is known based on do...
Definition: ValueTracking.cpp:6722
llvm::ObjectSizeOffsetEvaluator::visitExtractValueInst
SizeOffsetEvalType visitExtractValueInst(ExtractValueInst &I)
Definition: MemoryBuiltins.cpp:1125
StrDupLike
@ StrDupLike
Definition: MemoryBuiltins.cpp:60
llvm::isReallocLikeFn
bool isReallocLikeFn(const Value *V, const TargetLibraryInfo *TLI)
Tests if a value is a call or invoke to a library function that reallocates memory (e....
Definition: MemoryBuiltins.cpp:313
llvm::CallBase::getArgOperand
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1341
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
llvm::ObjectSizeOffsetEvaluator::visitInstruction
SizeOffsetEvalType visitInstruction(Instruction &I)
Definition: MemoryBuiltins.cpp:1207
llvm::ObjectSizeOffsetVisitor::knownSize
static bool knownSize(const SizeOffsetType &SizeOffset)
Definition: MemoryBuiltins.h:206
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2780
llvm::PHINode
Definition: Instructions.h:2664
llvm::TypeSize::getKnownMinSize
ScalarTy getKnownMinSize() const
Definition: TypeSize.h:431
getAllocationDataForFunction
static Optional< AllocFnsTy > getAllocationDataForFunction(const Function *Callee, AllocType AllocTy, const TargetLibraryInfo *TLI)
Returns the allocation data for the given value if it's a call to a known allocation function.
Definition: MemoryBuiltins.cpp:180
llvm::IRBuilderBase::CreateZExtOrTrunc
Value * CreateZExtOrTrunc(Value *V, Type *DestTy, const Twine &Name="")
Create a ZExt or Trunc from the integer value V to DestTy.
Definition: IRBuilder.h:1870
llvm::ObjectSizeOffsetEvaluator::bothKnown
bool bothKnown(SizeOffsetEvalType SizeOffset)
Definition: MemoryBuiltins.h:291
MallocFamily::MSVCArrayNew
@ MSVCArrayNew
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1174
llvm::Module::getDataLayout
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:398
DerivedTypes.h
llvm::GlobalValue::getValueType
Type * getValueType() const
Definition: GlobalValue.h:272
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1474
AllocLike
@ AllocLike
Definition: MemoryBuiltins.cpp:63
llvm::ObjectSizeOffsetVisitor::ObjectSizeOffsetVisitor
ObjectSizeOffsetVisitor(const DataLayout &DL, const TargetLibraryInfo *TLI, LLVMContext &Context, ObjectSizeOpts Options={})
Definition: MemoryBuiltins.cpp:655
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:172
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::ConstantPointerNull::getType
PointerType * getType() const
Specialize the getType() method to always return an PointerType, which reduces the amount of casting ...
Definition: Constants.h:550
llvm::isAllocRemovable
bool isAllocRemovable(const CallBase *V, const TargetLibraryInfo *TLI)
Return false if the allocation can have side effects on the program state we are required to preserve...
Definition: MemoryBuiltins.cpp:323
llvm::AMDGPU::HSAMD::Kernel::Key::Args
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
Definition: AMDGPUMetadata.h:394
llvm::AllocaInst
an instruction to allocate memory on the stack
Definition: Instructions.h:58
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::isLibFreeFunction
bool isLibFreeFunction(const Function *F, const LibFunc TLIFn)
isLibFreeFunction - Returns true if the function is a builtin free()
Definition: MemoryBuiltins.cpp:511
raw_ostream.h
llvm::ObjectSizeOffsetVisitor::visitExtractElementInst
SizeOffsetType visitExtractElementInst(ExtractElementInst &I)
Definition: MemoryBuiltins.cpp:788
AllocFnsTy::FstParam
int FstParam
Definition: MemoryBuiltins.cpp:107
Value.h
llvm::FunctionType::getReturnType
Type * getReturnType() const
Definition: DerivedTypes.h:124
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::ObjectSizeOffsetEvaluator::anyKnown
bool anyKnown(SizeOffsetEvalType SizeOffset)
Definition: MemoryBuiltins.h:287
Debug.h
AllocFnsTy::AllocTy
AllocType AllocTy
Definition: MemoryBuiltins.cpp:104
MallocFamily::MSVCNew
@ MSVCNew
llvm::isMallocOrCallocLikeFn
bool isMallocOrCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI)
Tests if a value is a call or invoke to a library function that allocates memory similar to malloc or...
Definition: MemoryBuiltins.cpp:301
llvm::isFreeCall
const CallInst * isFreeCall(const Value *I, const TargetLibraryInfo *TLI)
isFreeCall - Returns non-null if the value is a call to the builtin free()
Definition: MemoryBuiltins.cpp:531
llvm::ObjectSizeOffsetVisitor::visitPHINode
SizeOffsetType visitPHINode(PHINode &)
Definition: MemoryBuiltins.cpp:960
llvm::Attribute::getAllocSizeArgs
std::pair< unsigned, Optional< unsigned > > getAllocSizeArgs() const
Returns the argument numbers for the allocsize attribute (or pair(0, 0) if not known).
Definition: Attributes.cpp:355
llvm::FunctionType
Class to represent function types.
Definition: DerivedTypes.h:103
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
isAlignedAllocLikeFn
static bool isAlignedAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI)
Tests if a value is a call or invoke to a library function that allocates uninitialized memory with a...
Definition: MemoryBuiltins.cpp:288
llvm::DataLayout::getTypeAllocSize
TypeSize getTypeAllocSize(Type *Ty) const
Returns the offset in bytes between successive objects of the specified type, including alignment pad...
Definition: DataLayout.h:506