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