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/APInt.h"
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/ADT/SmallPtrSet.h"
21 #include "llvm/Analysis/TargetFolder.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"
35 class ConstantPointerNull;
37 class ExtractElementInst;
38 class ExtractValueInst;
51 class TargetLibraryInfo;
56 /// \brief 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
59 bool isAllocationFn(const Value *V, const TargetLibraryInfo *TLI,
60 bool LookThroughBitCast = false);
62 /// \brief Tests if a value is a call or invoke to a function that returns a
63 /// NoAlias pointer (including malloc/calloc/realloc/strdup-like functions).
64 bool isNoAliasFn(const Value *V, const TargetLibraryInfo *TLI,
65 bool LookThroughBitCast = false);
67 /// \brief Tests if a value is a call or invoke to a library function that
68 /// allocates uninitialized memory (such as malloc).
69 bool isMallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
70 bool LookThroughBitCast = false);
72 /// \brief Tests if a value is a call or invoke to a library function that
73 /// allocates zero-filled memory (such as calloc).
74 bool isCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
75 bool LookThroughBitCast = false);
77 /// \brief Tests if a value is a call or invoke to a library function that
78 /// allocates memory similar to malloc or calloc.
79 bool isMallocOrCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
80 bool LookThroughBitCast = false);
82 /// \brief Tests if a value is a call or invoke to a library function that
83 /// allocates memory (either malloc, calloc, or strdup like).
84 bool isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
85 bool LookThroughBitCast = false);
87 //===----------------------------------------------------------------------===//
88 // malloc Call Utility Functions.
91 /// extractMallocCall - Returns the corresponding CallInst if the instruction
92 /// is a malloc call. Since CallInst::CreateMalloc() only creates calls, we
93 /// ignore InvokeInst here.
94 const CallInst *extractMallocCall(const Value *I, const TargetLibraryInfo *TLI);
95 inline CallInst *extractMallocCall(Value *I, const TargetLibraryInfo *TLI) {
96 return const_cast<CallInst*>(extractMallocCall((const Value*)I, TLI));
99 /// getMallocType - Returns the PointerType resulting from the malloc call.
100 /// The PointerType depends on the number of bitcast uses of the malloc call:
101 /// 0: PointerType is the malloc calls' return type.
102 /// 1: PointerType is the bitcast's result type.
103 /// >1: Unique PointerType cannot be determined, return NULL.
104 PointerType *getMallocType(const CallInst *CI, const TargetLibraryInfo *TLI);
106 /// getMallocAllocatedType - Returns the Type allocated by malloc call.
107 /// The Type depends on the number of bitcast uses of the malloc call:
108 /// 0: PointerType is the malloc calls' return type.
109 /// 1: PointerType is the bitcast's result type.
110 /// >1: Unique PointerType cannot be determined, return NULL.
111 Type *getMallocAllocatedType(const CallInst *CI, const TargetLibraryInfo *TLI);
113 /// getMallocArraySize - Returns the array size of a malloc call. If the
114 /// argument passed to malloc is a multiple of the size of the malloced type,
115 /// then return that multiple. For non-array mallocs, the multiple is
116 /// constant 1. Otherwise, return NULL for mallocs whose array size cannot be
118 Value *getMallocArraySize(CallInst *CI, const DataLayout &DL,
119 const TargetLibraryInfo *TLI,
120 bool LookThroughSExt = false);
122 //===----------------------------------------------------------------------===//
123 // calloc Call Utility Functions.
126 /// extractCallocCall - Returns the corresponding CallInst if the instruction
127 /// is a calloc call.
128 const CallInst *extractCallocCall(const Value *I, const TargetLibraryInfo *TLI);
129 inline CallInst *extractCallocCall(Value *I, const TargetLibraryInfo *TLI) {
130 return const_cast<CallInst*>(extractCallocCall((const Value*)I, TLI));
134 //===----------------------------------------------------------------------===//
135 // free Call Utility Functions.
138 /// isFreeCall - Returns non-null if the value is a call to the builtin free()
139 const CallInst *isFreeCall(const Value *I, const TargetLibraryInfo *TLI);
141 inline CallInst *isFreeCall(Value *I, const TargetLibraryInfo *TLI) {
142 return const_cast<CallInst*>(isFreeCall((const Value*)I, TLI));
145 //===----------------------------------------------------------------------===//
146 // Utility functions to compute size of objects.
149 /// Various options to control the behavior of getObjectSize.
150 struct ObjectSizeOpts {
151 /// Controls how we handle conditional statements with unknown conditions.
152 enum class Mode : uint8_t {
153 /// Fail to evaluate an unknown condition.
155 /// Evaluate all branches of an unknown condition. If all evaluations
156 /// succeed, pick the minimum size.
158 /// Same as Min, except we pick the maximum size of all of the branches.
162 /// How we want to evaluate this object's size.
163 Mode EvalMode = Mode::Exact;
164 /// Whether to round the result up to the alignment of allocas, byval
165 /// arguments, and global variables.
166 bool RoundToAlign = false;
167 /// If this is true, null pointers in address space 0 will be treated as
168 /// though they can't be evaluated. Otherwise, null is always considered to
169 /// point to a 0 byte region of memory.
170 bool NullIsUnknownSize = false;
173 /// \brief Compute the size of the object pointed by Ptr. Returns true and the
174 /// object size in Size if successful, and false otherwise. In this context, by
175 /// object we mean the region of memory starting at Ptr to the end of the
176 /// underlying object pointed to by Ptr.
177 bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL,
178 const TargetLibraryInfo *TLI, ObjectSizeOpts Opts = {});
180 /// Try to turn a call to @llvm.objectsize into an integer value of the given
181 /// Type. Returns null on failure.
182 /// If MustSucceed is true, this function will not return null, and may return
183 /// conservative values governed by the second argument of the call to
185 ConstantInt *lowerObjectSizeCall(IntrinsicInst *ObjectSize,
186 const DataLayout &DL,
187 const TargetLibraryInfo *TLI,
190 using SizeOffsetType = std::pair<APInt, APInt>;
192 /// \brief Evaluate the size and offset of an object pointed to by a Value*
193 /// statically. Fails if size or offset are not known at compile time.
194 class ObjectSizeOffsetVisitor
195 : public InstVisitor<ObjectSizeOffsetVisitor, SizeOffsetType> {
196 const DataLayout &DL;
197 const TargetLibraryInfo *TLI;
198 ObjectSizeOpts Options;
201 SmallPtrSet<Instruction *, 8> SeenInsts;
203 APInt align(APInt Size, uint64_t Align);
205 SizeOffsetType unknown() {
206 return std::make_pair(APInt(), APInt());
210 ObjectSizeOffsetVisitor(const DataLayout &DL, const TargetLibraryInfo *TLI,
211 LLVMContext &Context, ObjectSizeOpts Options = {});
213 SizeOffsetType compute(Value *V);
215 static bool knownSize(const SizeOffsetType &SizeOffset) {
216 return SizeOffset.first.getBitWidth() > 1;
219 static bool knownOffset(const SizeOffsetType &SizeOffset) {
220 return SizeOffset.second.getBitWidth() > 1;
223 static bool bothKnown(const SizeOffsetType &SizeOffset) {
224 return knownSize(SizeOffset) && knownOffset(SizeOffset);
227 // These are "private", except they can't actually be made private. Only
228 // compute() should be used by external users.
229 SizeOffsetType visitAllocaInst(AllocaInst &I);
230 SizeOffsetType visitArgument(Argument &A);
231 SizeOffsetType visitCallSite(CallSite CS);
232 SizeOffsetType visitConstantPointerNull(ConstantPointerNull&);
233 SizeOffsetType visitExtractElementInst(ExtractElementInst &I);
234 SizeOffsetType visitExtractValueInst(ExtractValueInst &I);
235 SizeOffsetType visitGEPOperator(GEPOperator &GEP);
236 SizeOffsetType visitGlobalAlias(GlobalAlias &GA);
237 SizeOffsetType visitGlobalVariable(GlobalVariable &GV);
238 SizeOffsetType visitIntToPtrInst(IntToPtrInst&);
239 SizeOffsetType visitLoadInst(LoadInst &I);
240 SizeOffsetType visitPHINode(PHINode&);
241 SizeOffsetType visitSelectInst(SelectInst &I);
242 SizeOffsetType visitUndefValue(UndefValue&);
243 SizeOffsetType visitInstruction(Instruction &I);
246 bool CheckedZextOrTrunc(APInt &I);
249 using SizeOffsetEvalType = std::pair<Value *, Value *>;
251 /// \brief Evaluate the size and offset of an object pointed to by a Value*.
252 /// May create code to compute the result at run-time.
253 class ObjectSizeOffsetEvaluator
254 : public InstVisitor<ObjectSizeOffsetEvaluator, SizeOffsetEvalType> {
255 using BuilderTy = IRBuilder<TargetFolder>;
256 using WeakEvalType = std::pair<WeakTrackingVH, WeakTrackingVH>;
257 using CacheMapTy = DenseMap<const Value *, WeakEvalType>;
258 using PtrSetTy = SmallPtrSet<const Value *, 8>;
260 const DataLayout &DL;
261 const TargetLibraryInfo *TLI;
262 LLVMContext &Context;
270 SizeOffsetEvalType unknown() {
271 return std::make_pair(nullptr, nullptr);
274 SizeOffsetEvalType compute_(Value *V);
277 ObjectSizeOffsetEvaluator(const DataLayout &DL, const TargetLibraryInfo *TLI,
278 LLVMContext &Context, bool RoundToAlign = false);
280 SizeOffsetEvalType compute(Value *V);
282 bool knownSize(SizeOffsetEvalType SizeOffset) {
283 return SizeOffset.first;
286 bool knownOffset(SizeOffsetEvalType SizeOffset) {
287 return SizeOffset.second;
290 bool anyKnown(SizeOffsetEvalType SizeOffset) {
291 return knownSize(SizeOffset) || knownOffset(SizeOffset);
294 bool bothKnown(SizeOffsetEvalType SizeOffset) {
295 return knownSize(SizeOffset) && knownOffset(SizeOffset);
298 // The individual instruction visitors should be treated as private.
299 SizeOffsetEvalType visitAllocaInst(AllocaInst &I);
300 SizeOffsetEvalType visitCallSite(CallSite CS);
301 SizeOffsetEvalType visitExtractElementInst(ExtractElementInst &I);
302 SizeOffsetEvalType visitExtractValueInst(ExtractValueInst &I);
303 SizeOffsetEvalType visitGEPOperator(GEPOperator &GEP);
304 SizeOffsetEvalType visitIntToPtrInst(IntToPtrInst&);
305 SizeOffsetEvalType visitLoadInst(LoadInst &I);
306 SizeOffsetEvalType visitPHINode(PHINode &PHI);
307 SizeOffsetEvalType visitSelectInst(SelectInst &I);
308 SizeOffsetEvalType visitInstruction(Instruction &I);
311 } // end namespace llvm
313 #endif // LLVM_ANALYSIS_MEMORYBUILTINS_H