1//==- llvm/Analysis/MemoryBuiltins.h - Calls to memory builtins --*- C++ -*-==//
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#ifndef LLVM_ANALYSIS_MEMORYBUILTINS_H
15#define LLVM_ANALYSIS_MEMORYBUILTINS_H
16
17#include "llvm/ADT/APInt.h"
18#include "llvm/ADT/DenseMap.h"
19#include "llvm/ADT/SmallPtrSet.h"
20#include "llvm/Analysis/TargetFolder.h"
21#include "llvm/Analysis/TargetLibraryInfo.h"
22#include "llvm/IR/CallSite.h"
23#include "llvm/IR/IRBuilder.h"
24#include "llvm/IR/InstVisitor.h"
25#include "llvm/IR/ValueHandle.h"
26#include <cstdint>
27#include <utility>
28
29namespace llvm {
30
31class AllocaInst;
32class Argument;
33class CallInst;
34class ConstantInt;
35class ConstantPointerNull;
36class DataLayout;
37class ExtractElementInst;
38class ExtractValueInst;
39class GEPOperator;
40class GlobalAlias;
41class GlobalVariable;
42class Instruction;
43class IntegerType;
44class IntrinsicInst;
45class IntToPtrInst;
46class LLVMContext;
47class LoadInst;
48class PHINode;
49class PointerType;
50class SelectInst;
51class TargetLibraryInfo;
52class Type;
53class UndefValue;
54class Value;
55
56/// Tests if a value is a call or invoke to a library function that
57/// allocates or reallocates memory (either malloc, calloc, realloc, or strdup
58/// like).
59bool isAllocationFn(const Value *V, const TargetLibraryInfo *TLI,
60                    bool LookThroughBitCast = false);
61bool isAllocationFn(const Value *V,
62                    function_ref<const TargetLibraryInfo &(Function &)> GetTLI,
63                    bool LookThroughBitCast = false);
64
65/// Tests if a value is a call or invoke to a function that returns a
66/// NoAlias pointer (including malloc/calloc/realloc/strdup-like functions).
67bool isNoAliasFn(const Value *V, const TargetLibraryInfo *TLI,
68                 bool LookThroughBitCast = false);
69
70/// Tests if a value is a call or invoke to a library function that
71/// allocates uninitialized memory (such as malloc).
72bool isMallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
73                    bool LookThroughBitCast = false);
74bool isMallocLikeFn(const Value *V,
75                    function_ref<const TargetLibraryInfo &(Function &)> GetTLI,
76                    bool LookThroughBitCast = false);
77
78/// Tests if a value is a call or invoke to a library function that
79/// allocates zero-filled memory (such as calloc).
80bool isCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
81                    bool LookThroughBitCast = false);
82
83/// Tests if a value is a call or invoke to a library function that
84/// allocates memory similar to malloc or calloc.
85bool isMallocOrCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
86                            bool LookThroughBitCast = false);
87
88/// Tests if a value is a call or invoke to a library function that
89/// allocates memory (either malloc, calloc, or strdup like).
90bool isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
91                   bool LookThroughBitCast = false);
92
93/// Tests if a value is a call or invoke to a library function that
94/// reallocates memory (e.g., realloc).
95bool isReallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
96                     bool LookThroughBitCast = false);
97
98/// Tests if a function is a call or invoke to a library function that
99/// reallocates memory (e.g., realloc).
100bool isReallocLikeFn(const Function *F, const TargetLibraryInfo *TLI);
101
102/// Tests if a value is a call or invoke to a library function that
103/// allocates memory and throws if an allocation failed (e.g., new).
104bool isOpNewLikeFn(const Value *V, const TargetLibraryInfo *TLI,
105                     bool LookThroughBitCast = false);
106
107/// Tests if a value is a call or invoke to a library function that
108/// allocates memory (strdup, strndup).
109bool isStrdupLikeFn(const Value *V, const TargetLibraryInfo *TLI,
110                     bool LookThroughBitCast = false);
111
112//===----------------------------------------------------------------------===//
113//  malloc Call Utility Functions.
114//
115
116/// extractMallocCall - Returns the corresponding CallInst if the instruction
117/// is a malloc call.  Since CallInst::CreateMalloc() only creates calls, we
118/// ignore InvokeInst here.
119const CallInst *
120extractMallocCall(const Value *I,
121                  function_ref<const TargetLibraryInfo &(Function &)> GetTLI);
122inline CallInst *
123extractMallocCall(Value *I,
124                  function_ref<const TargetLibraryInfo &(Function &)> GetTLI) {
125  return const_cast<CallInst *>(extractMallocCall((const Value *)I, GetTLI));
126}
127
128/// getMallocType - Returns the PointerType resulting from the malloc call.
129/// The PointerType depends on the number of bitcast uses of the malloc call:
130///   0: PointerType is the malloc calls' return type.
131///   1: PointerType is the bitcast's result type.
132///  >1: Unique PointerType cannot be determined, return NULL.
133PointerType *getMallocType(const CallInst *CI, const TargetLibraryInfo *TLI);
134
135/// getMallocAllocatedType - Returns the Type allocated by malloc call.
136/// The Type depends on the number of bitcast uses of the malloc call:
137///   0: PointerType is the malloc calls' return type.
138///   1: PointerType is the bitcast's result type.
139///  >1: Unique PointerType cannot be determined, return NULL.
140Type *getMallocAllocatedType(const CallInst *CI, const TargetLibraryInfo *TLI);
141
142/// getMallocArraySize - Returns the array size of a malloc call.  If the
143/// argument passed to malloc is a multiple of the size of the malloced type,
144/// then return that multiple.  For non-array mallocs, the multiple is
145/// constant 1.  Otherwise, return NULL for mallocs whose array size cannot be
146/// determined.
147Value *getMallocArraySize(CallInst *CI, const DataLayout &DL,
148                          const TargetLibraryInfo *TLI,
149                          bool LookThroughSExt = false);
150
151//===----------------------------------------------------------------------===//
152//  calloc Call Utility Functions.
153//
154
155/// extractCallocCall - Returns the corresponding CallInst if the instruction
156/// is a calloc call.
157const CallInst *extractCallocCall(const Value *I, const TargetLibraryInfo *TLI);
158inline CallInst *extractCallocCall(Value *I, const TargetLibraryInfo *TLI) {
159  return const_cast<CallInst*>(extractCallocCall((const Value*)I, TLI));
160}
161
162
163//===----------------------------------------------------------------------===//
164//  free Call Utility Functions.
165//
166
167/// isLibFreeFunction - Returns true if the function is a builtin free()
168bool isLibFreeFunction(const Function *F, const LibFunc TLIFn);
169
170/// isFreeCall - Returns non-null if the value is a call to the builtin free()
171const CallInst *isFreeCall(const Value *I, const TargetLibraryInfo *TLI);
172
173inline CallInst *isFreeCall(Value *I, const TargetLibraryInfo *TLI) {
174  return const_cast<CallInst*>(isFreeCall((const Value*)I, TLI));
175}
176
177//===----------------------------------------------------------------------===//
178//  Utility functions to compute size of objects.
179//
180
181/// Various options to control the behavior of getObjectSize.
182struct ObjectSizeOpts {
183  /// Controls how we handle conditional statements with unknown conditions.
184  enum class Mode : uint8_t {
185    /// Fail to evaluate an unknown condition.
186    Exact,
187    /// Evaluate all branches of an unknown condition. If all evaluations
188    /// succeed, pick the minimum size.
189    Min,
190    /// Same as Min, except we pick the maximum size of all of the branches.
191    Max
192  };
193
194  /// How we want to evaluate this object's size.
195  Mode EvalMode = Mode::Exact;
196  /// Whether to round the result up to the alignment of allocas, byval
197  /// arguments, and global variables.
198  bool RoundToAlign = false;
199  /// If this is true, null pointers in address space 0 will be treated as
200  /// though they can't be evaluated. Otherwise, null is always considered to
201  /// point to a 0 byte region of memory.
202  bool NullIsUnknownSize = false;
203};
204
205/// Compute the size of the object pointed by Ptr. Returns true and the
206/// object size in Size if successful, and false otherwise. In this context, by
207/// object we mean the region of memory starting at Ptr to the end of the
208/// underlying object pointed to by Ptr.
209bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL,
210                   const TargetLibraryInfo *TLI, ObjectSizeOpts Opts = {});
211
212/// Try to turn a call to \@llvm.objectsize into an integer value of the given
213/// Type. Returns null on failure. If MustSucceed is true, this function will
214/// not return null, and may return conservative values governed by the second
215/// argument of the call to objectsize.
216Value *lowerObjectSizeCall(IntrinsicInst *ObjectSize, const DataLayout &DL,
217                           const TargetLibraryInfo *TLI, bool MustSucceed);
218
219
220
221using SizeOffsetType = std::pair<APInt, APInt>;
222
223/// Evaluate the size and offset of an object pointed to by a Value*
224/// statically. Fails if size or offset are not known at compile time.
225class ObjectSizeOffsetVisitor
226  : public InstVisitor<ObjectSizeOffsetVisitor, SizeOffsetType> {
227  const DataLayout &DL;
228  const TargetLibraryInfo *TLI;
229  ObjectSizeOpts Options;
230  unsigned IntTyBits;
231  APInt Zero;
232  SmallPtrSet<Instruction *, 8> SeenInsts;
233
234  APInt align(APInt Size, uint64_t Align);
235
236  SizeOffsetType unknown() {
237    return std::make_pair(APInt(), APInt());
238  }
239
240public:
241  ObjectSizeOffsetVisitor(const DataLayout &DL, const TargetLibraryInfo *TLI,
242                          LLVMContext &Context, ObjectSizeOpts Options = {});
243
244  SizeOffsetType compute(Value *V);
245
246  static bool knownSize(const SizeOffsetType &SizeOffset) {
247    return SizeOffset.first.getBitWidth() > 1;
248  }
249
250  static bool knownOffset(const SizeOffsetType &SizeOffset) {
251    return SizeOffset.second.getBitWidth() > 1;
252  }
253
254  static bool bothKnown(const SizeOffsetType &SizeOffset) {
255    return knownSize(SizeOffset) && knownOffset(SizeOffset);
256  }
257
258  // These are "private", except they can't actually be made private. Only
259  // compute() should be used by external users.
260  SizeOffsetType visitAllocaInst(AllocaInst &I);
261  SizeOffsetType visitArgument(Argument &A);
262  SizeOffsetType visitCallSite(CallSite CS);
263  SizeOffsetType visitConstantPointerNull(ConstantPointerNull&);
264  SizeOffsetType visitExtractElementInst(ExtractElementInst &I);
265  SizeOffsetType visitExtractValueInst(ExtractValueInst &I);
266  SizeOffsetType visitGEPOperator(GEPOperator &GEP);
267  SizeOffsetType visitGlobalAlias(GlobalAlias &GA);
268  SizeOffsetType visitGlobalVariable(GlobalVariable &GV);
269  SizeOffsetType visitIntToPtrInst(IntToPtrInst&);
270  SizeOffsetType visitLoadInst(LoadInst &I);
271  SizeOffsetType visitPHINode(PHINode&);
272  SizeOffsetType visitSelectInst(SelectInst &I);
273  SizeOffsetType visitUndefValue(UndefValue&);
274  SizeOffsetType visitInstruction(Instruction &I);
275
276private:
277  bool CheckedZextOrTrunc(APInt &I);
278};
279
280using SizeOffsetEvalType = std::pair<Value *, Value *>;
281
282/// Evaluate the size and offset of an object pointed to by a Value*.
283/// May create code to compute the result at run-time.
284class ObjectSizeOffsetEvaluator
285  : public InstVisitor<ObjectSizeOffsetEvaluator, SizeOffsetEvalType> {
286  using BuilderTy = IRBuilder<TargetFolder, IRBuilderCallbackInserter>;
287  using WeakEvalType = std::pair<WeakTrackingVH, WeakTrackingVH>;
288  using CacheMapTy = DenseMap<const Value *, WeakEvalType>;
289  using PtrSetTy = SmallPtrSet<const Value *, 8>;
290
291  const DataLayout &DL;
292  const TargetLibraryInfo *TLI;
293  LLVMContext &Context;
294  BuilderTy Builder;
295  IntegerType *IntTy;
296  Value *Zero;
297  CacheMapTy CacheMap;
298  PtrSetTy SeenVals;
299  ObjectSizeOpts EvalOpts;
300  SmallPtrSet<Instruction *, 8> InsertedInstructions;
301
302  SizeOffsetEvalType compute_(Value *V);
303
304public:
305  static SizeOffsetEvalType unknown() {
306    return std::make_pair(nullptr, nullptr);
307  }
308
309  ObjectSizeOffsetEvaluator(const DataLayout &DL, const TargetLibraryInfo *TLI,
310                            LLVMContext &Context, ObjectSizeOpts EvalOpts = {});
311
312  SizeOffsetEvalType compute(Value *V);
313
314  bool knownSize(SizeOffsetEvalType SizeOffset) {
315    return SizeOffset.first;
316  }
317
318  bool knownOffset(SizeOffsetEvalType SizeOffset) {
319    return SizeOffset.second;
320  }
321
322  bool anyKnown(SizeOffsetEvalType SizeOffset) {
323    return knownSize(SizeOffset) || knownOffset(SizeOffset);
324  }
325
326  bool bothKnown(SizeOffsetEvalType SizeOffset) {
327    return knownSize(SizeOffset) && knownOffset(SizeOffset);
328  }
329
330  // The individual instruction visitors should be treated as private.
331  SizeOffsetEvalType visitAllocaInst(AllocaInst &I);
332  SizeOffsetEvalType visitCallSite(CallSite CS);
333  SizeOffsetEvalType visitExtractElementInst(ExtractElementInst &I);
334  SizeOffsetEvalType visitExtractValueInst(ExtractValueInst &I);
335  SizeOffsetEvalType visitGEPOperator(GEPOperator &GEP);
336  SizeOffsetEvalType visitIntToPtrInst(IntToPtrInst&);
337  SizeOffsetEvalType visitLoadInst(LoadInst &I);
338  SizeOffsetEvalType visitPHINode(PHINode &PHI);
339  SizeOffsetEvalType visitSelectInst(SelectInst &I);
340  SizeOffsetEvalType visitInstruction(Instruction &I);
341};
342
343} // end namespace llvm
344
345#endif // LLVM_ANALYSIS_MEMORYBUILTINS_H
346