1 //===- llvm/Analysis/MemoryBuiltins.h- Calls to memory builtins -*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This family of functions identifies calls to builtin functions that allocate
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_ANALYSIS_MEMORYBUILTINS_H
16 #define LLVM_ANALYSIS_MEMORYBUILTINS_H
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"
31 class TargetLibraryInfo;
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
38 bool isAllocationFn(const Value *V, const TargetLibraryInfo *TLI,
39 bool LookThroughBitCast = false);
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).
43 bool isNoAliasFn(const Value *V, const TargetLibraryInfo *TLI,
44 bool LookThroughBitCast = false);
46 /// \brief Tests if a value is a call or invoke to a library function that
47 /// allocates uninitialized memory (such as malloc).
48 bool isMallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
49 bool LookThroughBitCast = false);
51 /// \brief Tests if a value is a call or invoke to a library function that
52 /// allocates zero-filled memory (such as calloc).
53 bool isCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
54 bool LookThroughBitCast = false);
56 /// \brief Tests if a value is a call or invoke to a library function that
57 /// allocates memory similar to malloc or calloc.
58 bool isMallocOrCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
59 bool LookThroughBitCast = false);
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).
63 bool isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
64 bool LookThroughBitCast = false);
66 //===----------------------------------------------------------------------===//
67 // malloc Call Utility Functions.
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.
73 const CallInst *extractMallocCall(const Value *I, const TargetLibraryInfo *TLI);
74 static inline CallInst *extractMallocCall(Value *I,
75 const TargetLibraryInfo *TLI) {
76 return const_cast<CallInst*>(extractMallocCall((const Value*)I, TLI));
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.
84 PointerType *getMallocType(const CallInst *CI, const TargetLibraryInfo *TLI);
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.
91 Type *getMallocAllocatedType(const CallInst *CI, const TargetLibraryInfo *TLI);
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
98 Value *getMallocArraySize(CallInst *CI, const DataLayout &DL,
99 const TargetLibraryInfo *TLI,
100 bool LookThroughSExt = false);
102 //===----------------------------------------------------------------------===//
103 // calloc Call Utility Functions.
106 /// extractCallocCall - Returns the corresponding CallInst if the instruction
107 /// is a calloc call.
108 const CallInst *extractCallocCall(const Value *I, const TargetLibraryInfo *TLI);
109 static inline CallInst *extractCallocCall(Value *I,
110 const TargetLibraryInfo *TLI) {
111 return const_cast<CallInst*>(extractCallocCall((const Value*)I, TLI));
115 //===----------------------------------------------------------------------===//
116 // free Call Utility Functions.
119 /// isFreeCall - Returns non-null if the value is a call to the builtin free()
120 const CallInst *isFreeCall(const Value *I, const TargetLibraryInfo *TLI);
122 static inline CallInst *isFreeCall(Value *I, const TargetLibraryInfo *TLI) {
123 return const_cast<CallInst*>(isFreeCall((const Value*)I, TLI));
127 //===----------------------------------------------------------------------===//
128 // Utility functions to compute size of objects.
131 /// Various options to control the behavior of getObjectSize.
132 struct ObjectSizeOpts {
133 /// Controls how we handle conditional statements with unknown conditions.
134 enum class Mode : uint8_t {
135 /// Fail to evaluate an unknown condition.
137 /// Evaluate all branches of an unknown condition. If all evaluations
138 /// succeed, pick the minimum size.
140 /// Same as Min, except we pick the maximum size of all of the branches.
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;
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.
159 bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL,
160 const TargetLibraryInfo *TLI, ObjectSizeOpts Opts = {});
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
167 ConstantInt *lowerObjectSizeCall(IntrinsicInst *ObjectSize,
168 const DataLayout &DL,
169 const TargetLibraryInfo *TLI,
172 typedef std::pair<APInt, APInt> SizeOffsetType;
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.
176 class ObjectSizeOffsetVisitor
177 : public InstVisitor<ObjectSizeOffsetVisitor, SizeOffsetType> {
179 const DataLayout &DL;
180 const TargetLibraryInfo *TLI;
181 ObjectSizeOpts Options;
184 SmallPtrSet<Instruction *, 8> SeenInsts;
186 APInt align(APInt Size, uint64_t Align);
188 SizeOffsetType unknown() {
189 return std::make_pair(APInt(), APInt());
193 ObjectSizeOffsetVisitor(const DataLayout &DL, const TargetLibraryInfo *TLI,
194 LLVMContext &Context, ObjectSizeOpts Options = {});
196 SizeOffsetType compute(Value *V);
198 static bool knownSize(const SizeOffsetType &SizeOffset) {
199 return SizeOffset.first.getBitWidth() > 1;
202 static bool knownOffset(const SizeOffsetType &SizeOffset) {
203 return SizeOffset.second.getBitWidth() > 1;
206 static bool bothKnown(const SizeOffsetType &SizeOffset) {
207 return knownSize(SizeOffset) && knownOffset(SizeOffset);
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);
229 bool CheckedZextOrTrunc(APInt &I);
232 typedef std::pair<Value*, Value*> SizeOffsetEvalType;
235 /// \brief Evaluate the size and offset of an object pointed to by a Value*.
236 /// May create code to compute the result at run-time.
237 class ObjectSizeOffsetEvaluator
238 : public InstVisitor<ObjectSizeOffsetEvaluator, SizeOffsetEvalType> {
240 typedef IRBuilder<TargetFolder> BuilderTy;
241 typedef std::pair<WeakTrackingVH, WeakTrackingVH> WeakEvalType;
242 typedef DenseMap<const Value*, WeakEvalType> CacheMapTy;
243 typedef SmallPtrSet<const Value*, 8> PtrSetTy;
245 const DataLayout &DL;
246 const TargetLibraryInfo *TLI;
247 LLVMContext &Context;
255 SizeOffsetEvalType unknown() {
256 return std::make_pair(nullptr, nullptr);
258 SizeOffsetEvalType compute_(Value *V);
261 ObjectSizeOffsetEvaluator(const DataLayout &DL, const TargetLibraryInfo *TLI,
262 LLVMContext &Context, bool RoundToAlign = false);
263 SizeOffsetEvalType compute(Value *V);
265 bool knownSize(SizeOffsetEvalType SizeOffset) {
266 return SizeOffset.first;
269 bool knownOffset(SizeOffsetEvalType SizeOffset) {
270 return SizeOffset.second;
273 bool anyKnown(SizeOffsetEvalType SizeOffset) {
274 return knownSize(SizeOffset) || knownOffset(SizeOffset);
277 bool bothKnown(SizeOffsetEvalType SizeOffset) {
278 return knownSize(SizeOffset) && knownOffset(SizeOffset);
281 // The individual instruction visitors should be treated as private.
282 SizeOffsetEvalType visitAllocaInst(AllocaInst &I);
283 SizeOffsetEvalType visitCallSite(CallSite CS);
284 SizeOffsetEvalType visitExtractElementInst(ExtractElementInst &I);
285 SizeOffsetEvalType visitExtractValueInst(ExtractValueInst &I);
286 SizeOffsetEvalType visitGEPOperator(GEPOperator &GEP);
287 SizeOffsetEvalType visitIntToPtrInst(IntToPtrInst&);
288 SizeOffsetEvalType visitLoadInst(LoadInst &I);
289 SizeOffsetEvalType visitPHINode(PHINode &PHI);
290 SizeOffsetEvalType visitSelectInst(SelectInst &I);
291 SizeOffsetEvalType visitInstruction(Instruction &I);
294 } // End llvm namespace