MemoryBuiltins.h revision 41a3f251346681e21171879dce409b2e6a3ba750 
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/Operator.h"
21#include "llvm/Support/DataTypes.h"
22#include "llvm/Support/InstVisitor.h"
23#include "llvm/Support/IRBuilder.h"
24#include "llvm/Support/TargetFolder.h"
25
26namespace llvm {
27class CallInst;
28class PointerType;
29class TargetData;
30class Type;
31class Value;
32
33
34/// \brief Tests if a value is a call or invoke to a library function that
35/// allocates or reallocates memory (either malloc, calloc, realloc, or strdup
36/// like).
37bool isAllocationFn(const Value *V, bool LookThroughBitCast = false);
38
39/// \brief Tests if a value is a call or invoke to a function that returns a
40/// NoAlias pointer (including malloc/calloc/realloc/strdup-like functions).
41bool isNoAliasFn(const Value *V, bool LookThroughBitCast = false);
42
43/// \brief Tests if a value is a call or invoke to a library function that
44/// allocates uninitialized memory (such as malloc).
45bool isMallocLikeFn(const Value *V, bool LookThroughBitCast = false);
46
47/// \brief Tests if a value is a call or invoke to a library function that
48/// allocates zero-filled memory (such as calloc).
49bool isCallocLikeFn(const Value *V, bool LookThroughBitCast = false);
50
51/// \brief Tests if a value is a call or invoke to a library function that
52/// allocates memory (either malloc, calloc, or strdup like).
53bool isAllocLikeFn(const Value *V, bool LookThroughBitCast = false);
54
55/// \brief Tests if a value is a call or invoke to a library function that
56/// reallocates memory (such as realloc).
57bool isReallocLikeFn(const Value *V, bool LookThroughBitCast = false);
58
59
60//===----------------------------------------------------------------------===//
61//  malloc Call Utility Functions.
62//
63
64/// extractMallocCall - Returns the corresponding CallInst if the instruction
65/// is a malloc call.  Since CallInst::CreateMalloc() only creates calls, we
66/// ignore InvokeInst here.
67const CallInst *extractMallocCall(const Value *I);
68static inline CallInst *extractMallocCall(Value *I) {
69  return const_cast<CallInst*>(extractMallocCall((const Value*)I));
70}
71
72/// isArrayMalloc - Returns the corresponding CallInst if the instruction
73/// is a call to malloc whose array size can be determined and the array size
74/// is not constant 1.  Otherwise, return NULL.
75const CallInst *isArrayMalloc(const Value *I, const TargetData *TD);
76
77/// getMallocType - Returns the PointerType resulting from the malloc call.
78/// The PointerType depends on the number of bitcast uses of the malloc call:
79///   0: PointerType is the malloc calls' return type.
80///   1: PointerType is the bitcast's result type.
81///  >1: Unique PointerType cannot be determined, return NULL.
82PointerType *getMallocType(const CallInst *CI);
83
84/// getMallocAllocatedType - Returns the Type allocated by malloc call.
85/// The Type depends on the number of bitcast uses of the malloc call:
86///   0: PointerType is the malloc calls' return type.
87///   1: PointerType is the bitcast's result type.
88///  >1: Unique PointerType cannot be determined, return NULL.
89Type *getMallocAllocatedType(const CallInst *CI);
90
91/// getMallocArraySize - Returns the array size of a malloc call.  If the
92/// argument passed to malloc is a multiple of the size of the malloced type,
93/// then return that multiple.  For non-array mallocs, the multiple is
94/// constant 1.  Otherwise, return NULL for mallocs whose array size cannot be
95/// determined.
96Value *getMallocArraySize(CallInst *CI, const TargetData *TD,
97                          bool LookThroughSExt = false);
98
99
100//===----------------------------------------------------------------------===//
101//  calloc Call Utility Functions.
102//
103
104/// extractCallocCall - Returns the corresponding CallInst if the instruction
105/// is a calloc call.
106const CallInst *extractCallocCall(const Value *I);
107static inline CallInst *extractCallocCall(Value *I) {
108  return const_cast<CallInst*>(extractCallocCall((const Value*)I));
109}
110
111
112//===----------------------------------------------------------------------===//
113//  free Call Utility Functions.
114//
115
116/// isFreeCall - Returns non-null if the value is a call to the builtin free()
117const CallInst *isFreeCall(const Value *I);
118
119static inline CallInst *isFreeCall(Value *I) {
120  return const_cast<CallInst*>(isFreeCall((const Value*)I));
121}
122
123
124//===----------------------------------------------------------------------===//
125//  Utility functions to compute size of objects.
126//
127
128/// \brief Compute the size of the object pointed by Ptr. Returns true and the
129/// object size in Size if successful, and false otherwise.
130/// If RoundToAlign is true, then Size is rounded up to the aligment of allocas,
131/// byval arguments, and global variables.
132bool getObjectSize(const Value *Ptr, uint64_t &Size, const TargetData *TD,
133                   bool RoundToAlign = false);
134
135
136
137typedef std::pair<APInt, APInt> SizeOffsetType;
138
139/// \brief Evaluate the size and offset of an object ponted by a Value*
140/// statically. Fails if size or offset are not known at compile time.
141class ObjectSizeOffsetVisitor
142  : public InstVisitor<ObjectSizeOffsetVisitor, SizeOffsetType> {
143
144  const TargetData *TD;
145  bool RoundToAlign;
146  unsigned IntTyBits;
147  APInt Zero;
148
149  APInt align(APInt Size, uint64_t Align);
150
151  SizeOffsetType unknown() {
152    return std::make_pair(APInt(), APInt());
153  }
154
155public:
156  ObjectSizeOffsetVisitor(const TargetData *TD, LLVMContext &Context,
157                          bool RoundToAlign = false);
158
159  SizeOffsetType compute(Value *V);
160
161  bool knownSize(SizeOffsetType &SizeOffset) {
162    return SizeOffset.first.getBitWidth() > 1;
163  }
164
165  bool knownOffset(SizeOffsetType &SizeOffset) {
166    return SizeOffset.second.getBitWidth() > 1;
167  }
168
169  bool bothKnown(SizeOffsetType &SizeOffset) {
170    return knownSize(SizeOffset) && knownOffset(SizeOffset);
171  }
172
173  SizeOffsetType visitAllocaInst(AllocaInst &I);
174  SizeOffsetType visitArgument(Argument &A);
175  SizeOffsetType visitCallSite(CallSite CS);
176  SizeOffsetType visitConstantPointerNull(ConstantPointerNull&);
177  SizeOffsetType visitExtractElementInst(ExtractElementInst &I);
178  SizeOffsetType visitExtractValueInst(ExtractValueInst &I);
179  SizeOffsetType visitGEPOperator(GEPOperator &GEP);
180  SizeOffsetType visitGlobalVariable(GlobalVariable &GV);
181  SizeOffsetType visitIntToPtrInst(IntToPtrInst&);
182  SizeOffsetType visitLoadInst(LoadInst &I);
183  SizeOffsetType visitPHINode(PHINode&);
184  SizeOffsetType visitSelectInst(SelectInst &I);
185  SizeOffsetType visitUndefValue(UndefValue&);
186  SizeOffsetType visitInstruction(Instruction &I);
187};
188
189typedef std::pair<Value*, Value*> SizeOffsetEvalType;
190
191
192/// \brief Evaluate the size and offset of an object ponted by a Value*.
193/// May create code to compute the result at run-time.
194class ObjectSizeOffsetEvaluator
195  : public InstVisitor<ObjectSizeOffsetEvaluator, SizeOffsetEvalType> {
196
197  typedef IRBuilder<true, TargetFolder> BuilderTy;
198  typedef DenseMap<const Value*, SizeOffsetEvalType> CacheMapTy;
199  typedef SmallPtrSet<const Value*, 8> PtrSetTy;
200
201  const TargetData *TD;
202  LLVMContext &Context;
203  BuilderTy Builder;
204  ObjectSizeOffsetVisitor Visitor;
205  IntegerType *IntTy;
206  Value *Zero;
207  CacheMapTy CacheMap;
208  PtrSetTy SeenVals;
209
210  SizeOffsetEvalType unknown() {
211    return std::make_pair((Value*)0, (Value*)0);
212  }
213  SizeOffsetEvalType compute_(Value *V);
214
215public:
216  ObjectSizeOffsetEvaluator(const TargetData *TD, LLVMContext &Context);
217  SizeOffsetEvalType compute(Value *V);
218
219  bool knownSize(SizeOffsetEvalType &SizeOffset) {
220    return SizeOffset.first;
221  }
222
223  bool knownOffset(SizeOffsetEvalType &SizeOffset) {
224    return SizeOffset.second;
225  }
226
227  bool anyKnown(SizeOffsetEvalType &SizeOffset) {
228    return knownSize(SizeOffset) || knownOffset(SizeOffset);
229  }
230
231  bool bothKnown(SizeOffsetEvalType &SizeOffset) {
232    return knownSize(SizeOffset) && knownOffset(SizeOffset);
233  }
234
235  SizeOffsetEvalType visitAllocaInst(AllocaInst &I);
236  SizeOffsetEvalType visitCallSite(CallSite CS);
237  SizeOffsetEvalType visitExtractElementInst(ExtractElementInst &I);
238  SizeOffsetEvalType visitExtractValueInst(ExtractValueInst &I);
239  SizeOffsetEvalType visitGEPOperator(GEPOperator &GEP);
240  SizeOffsetEvalType visitIntToPtrInst(IntToPtrInst&);
241  SizeOffsetEvalType visitLoadInst(LoadInst &I);
242  SizeOffsetEvalType visitPHINode(PHINode &PHI);
243  SizeOffsetEvalType visitSelectInst(SelectInst &I);
244  SizeOffsetEvalType visitInstruction(Instruction &I);
245};
246
247} // End llvm namespace
248
249#endif
250