1 //==- llvm/Analysis/MemoryBuiltins.h - Calls to memory builtins --*- C++ -*-==//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 // This family of functions identifies calls to builtin functions that allocate
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_ANALYSIS_MEMORYBUILTINS_H
15 #define LLVM_ANALYSIS_MEMORYBUILTINS_H
17 #include "llvm/ADT/APInt.h"
18 #include "llvm/ADT/DenseMap.h"
19 #include "llvm/ADT/SmallPtrSet.h"
20 #include "llvm/Analysis/TargetFolder.h"
21 #include "llvm/Analysis/TargetLibraryInfo.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 /// 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 /// 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 /// 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 /// 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 /// 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 /// 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 /// Tests if a value is a call or invoke to a library function that
88 /// reallocates memory (e.g., realloc).
89 bool isReallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
90 bool LookThroughBitCast = false);
92 /// Tests if a function is a call or invoke to a library function that
93 /// reallocates memory (e.g., realloc).
94 bool isReallocLikeFn(const Function *F, const TargetLibraryInfo *TLI);
96 //===----------------------------------------------------------------------===//
97 // malloc Call Utility Functions.
100 /// extractMallocCall - Returns the corresponding CallInst if the instruction
101 /// is a malloc call. Since CallInst::CreateMalloc() only creates calls, we
102 /// ignore InvokeInst here.
103 const CallInst *extractMallocCall(const Value *I, const TargetLibraryInfo *TLI);
104 inline CallInst *extractMallocCall(Value *I, const TargetLibraryInfo *TLI) {
105 return const_cast<CallInst*>(extractMallocCall((const Value*)I, TLI));
108 /// getMallocType - Returns the PointerType resulting from the malloc call.
109 /// The PointerType depends on the number of bitcast uses of the malloc call:
110 /// 0: PointerType is the malloc calls' return type.
111 /// 1: PointerType is the bitcast's result type.
112 /// >1: Unique PointerType cannot be determined, return NULL.
113 PointerType *getMallocType(const CallInst *CI, const TargetLibraryInfo *TLI);
115 /// getMallocAllocatedType - Returns the Type allocated by malloc call.
116 /// The Type depends on the number of bitcast uses of the malloc call:
117 /// 0: PointerType is the malloc calls' return type.
118 /// 1: PointerType is the bitcast's result type.
119 /// >1: Unique PointerType cannot be determined, return NULL.
120 Type *getMallocAllocatedType(const CallInst *CI, const TargetLibraryInfo *TLI);
122 /// getMallocArraySize - Returns the array size of a malloc call. If the
123 /// argument passed to malloc is a multiple of the size of the malloced type,
124 /// then return that multiple. For non-array mallocs, the multiple is
125 /// constant 1. Otherwise, return NULL for mallocs whose array size cannot be
127 Value *getMallocArraySize(CallInst *CI, const DataLayout &DL,
128 const TargetLibraryInfo *TLI,
129 bool LookThroughSExt = false);
131 //===----------------------------------------------------------------------===//
132 // calloc Call Utility Functions.
135 /// extractCallocCall - Returns the corresponding CallInst if the instruction
136 /// is a calloc call.
137 const CallInst *extractCallocCall(const Value *I, const TargetLibraryInfo *TLI);
138 inline CallInst *extractCallocCall(Value *I, const TargetLibraryInfo *TLI) {
139 return const_cast<CallInst*>(extractCallocCall((const Value*)I, TLI));
143 //===----------------------------------------------------------------------===//
144 // free Call Utility Functions.
147 /// isLibFreeFunction - Returns true if the function is a builtin free()
148 bool isLibFreeFunction(const Function *F, const LibFunc TLIFn);
150 /// isFreeCall - Returns non-null if the value is a call to the builtin free()
151 const CallInst *isFreeCall(const Value *I, const TargetLibraryInfo *TLI);
153 inline CallInst *isFreeCall(Value *I, const TargetLibraryInfo *TLI) {
154 return const_cast<CallInst*>(isFreeCall((const Value*)I, TLI));
157 //===----------------------------------------------------------------------===//
158 // Utility functions to compute size of objects.
161 /// Various options to control the behavior of getObjectSize.
162 struct ObjectSizeOpts {
163 /// Controls how we handle conditional statements with unknown conditions.
164 enum class Mode : uint8_t {
165 /// Fail to evaluate an unknown condition.
167 /// Evaluate all branches of an unknown condition. If all evaluations
168 /// succeed, pick the minimum size.
170 /// Same as Min, except we pick the maximum size of all of the branches.
174 /// How we want to evaluate this object's size.
175 Mode EvalMode = Mode::Exact;
176 /// Whether to round the result up to the alignment of allocas, byval
177 /// arguments, and global variables.
178 bool RoundToAlign = false;
179 /// If this is true, null pointers in address space 0 will be treated as
180 /// though they can't be evaluated. Otherwise, null is always considered to
181 /// point to a 0 byte region of memory.
182 bool NullIsUnknownSize = false;
185 /// Compute the size of the object pointed by Ptr. Returns true and the
186 /// object size in Size if successful, and false otherwise. In this context, by
187 /// object we mean the region of memory starting at Ptr to the end of the
188 /// underlying object pointed to by Ptr.
189 bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL,
190 const TargetLibraryInfo *TLI, ObjectSizeOpts Opts = {});
192 /// Try to turn a call to \@llvm.objectsize into an integer value of the given
193 /// Type. Returns null on failure. If MustSucceed is true, this function will
194 /// not return null, and may return conservative values governed by the second
195 /// argument of the call to objectsize.
196 Value *lowerObjectSizeCall(IntrinsicInst *ObjectSize, const DataLayout &DL,
197 const TargetLibraryInfo *TLI, bool MustSucceed);
201 using SizeOffsetType = std::pair<APInt, APInt>;
203 /// Evaluate the size and offset of an object pointed to by a Value*
204 /// statically. Fails if size or offset are not known at compile time.
205 class ObjectSizeOffsetVisitor
206 : public InstVisitor<ObjectSizeOffsetVisitor, SizeOffsetType> {
207 const DataLayout &DL;
208 const TargetLibraryInfo *TLI;
209 ObjectSizeOpts Options;
212 SmallPtrSet<Instruction *, 8> SeenInsts;
214 APInt align(APInt Size, uint64_t Align);
216 SizeOffsetType unknown() {
217 return std::make_pair(APInt(), APInt());
221 ObjectSizeOffsetVisitor(const DataLayout &DL, const TargetLibraryInfo *TLI,
222 LLVMContext &Context, ObjectSizeOpts Options = {});
224 SizeOffsetType compute(Value *V);
226 static bool knownSize(const SizeOffsetType &SizeOffset) {
227 return SizeOffset.first.getBitWidth() > 1;
230 static bool knownOffset(const SizeOffsetType &SizeOffset) {
231 return SizeOffset.second.getBitWidth() > 1;
234 static bool bothKnown(const SizeOffsetType &SizeOffset) {
235 return knownSize(SizeOffset) && knownOffset(SizeOffset);
238 // These are "private", except they can't actually be made private. Only
239 // compute() should be used by external users.
240 SizeOffsetType visitAllocaInst(AllocaInst &I);
241 SizeOffsetType visitArgument(Argument &A);
242 SizeOffsetType visitCallSite(CallSite CS);
243 SizeOffsetType visitConstantPointerNull(ConstantPointerNull&);
244 SizeOffsetType visitExtractElementInst(ExtractElementInst &I);
245 SizeOffsetType visitExtractValueInst(ExtractValueInst &I);
246 SizeOffsetType visitGEPOperator(GEPOperator &GEP);
247 SizeOffsetType visitGlobalAlias(GlobalAlias &GA);
248 SizeOffsetType visitGlobalVariable(GlobalVariable &GV);
249 SizeOffsetType visitIntToPtrInst(IntToPtrInst&);
250 SizeOffsetType visitLoadInst(LoadInst &I);
251 SizeOffsetType visitPHINode(PHINode&);
252 SizeOffsetType visitSelectInst(SelectInst &I);
253 SizeOffsetType visitUndefValue(UndefValue&);
254 SizeOffsetType visitInstruction(Instruction &I);
257 bool CheckedZextOrTrunc(APInt &I);
260 using SizeOffsetEvalType = std::pair<Value *, Value *>;
262 /// Evaluate the size and offset of an object pointed to by a Value*.
263 /// May create code to compute the result at run-time.
264 class ObjectSizeOffsetEvaluator
265 : public InstVisitor<ObjectSizeOffsetEvaluator, SizeOffsetEvalType> {
266 using BuilderTy = IRBuilder<TargetFolder, IRBuilderCallbackInserter>;
267 using WeakEvalType = std::pair<WeakTrackingVH, WeakTrackingVH>;
268 using CacheMapTy = DenseMap<const Value *, WeakEvalType>;
269 using PtrSetTy = SmallPtrSet<const Value *, 8>;
271 const DataLayout &DL;
272 const TargetLibraryInfo *TLI;
273 LLVMContext &Context;
279 ObjectSizeOpts EvalOpts;
280 SmallPtrSet<Instruction *, 8> InsertedInstructions;
282 SizeOffsetEvalType compute_(Value *V);
285 static SizeOffsetEvalType unknown() {
286 return std::make_pair(nullptr, nullptr);
289 ObjectSizeOffsetEvaluator(const DataLayout &DL, const TargetLibraryInfo *TLI,
290 LLVMContext &Context, ObjectSizeOpts EvalOpts = {});
292 SizeOffsetEvalType compute(Value *V);
294 bool knownSize(SizeOffsetEvalType SizeOffset) {
295 return SizeOffset.first;
298 bool knownOffset(SizeOffsetEvalType SizeOffset) {
299 return SizeOffset.second;
302 bool anyKnown(SizeOffsetEvalType SizeOffset) {
303 return knownSize(SizeOffset) || knownOffset(SizeOffset);
306 bool bothKnown(SizeOffsetEvalType SizeOffset) {
307 return knownSize(SizeOffset) && knownOffset(SizeOffset);
310 // The individual instruction visitors should be treated as private.
311 SizeOffsetEvalType visitAllocaInst(AllocaInst &I);
312 SizeOffsetEvalType visitCallSite(CallSite CS);
313 SizeOffsetEvalType visitExtractElementInst(ExtractElementInst &I);
314 SizeOffsetEvalType visitExtractValueInst(ExtractValueInst &I);
315 SizeOffsetEvalType visitGEPOperator(GEPOperator &GEP);
316 SizeOffsetEvalType visitIntToPtrInst(IntToPtrInst&);
317 SizeOffsetEvalType visitLoadInst(LoadInst &I);
318 SizeOffsetEvalType visitPHINode(PHINode &PHI);
319 SizeOffsetEvalType visitSelectInst(SelectInst &I);
320 SizeOffsetEvalType visitInstruction(Instruction &I);
323 } // end namespace llvm
325 #endif // LLVM_ANALYSIS_MEMORYBUILTINS_H