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