1//==- llvm/Analysis/MemoryBuiltins.h - Calls to memory builtins --*- C++ -*-==//
2//
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
6//
7//===----------------------------------------------------------------------===//
8//
9// This family of functions identifies calls to builtin functions that allocate
10// or free memory.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_ANALYSIS_MEMORYBUILTINS_H
15#define LLVM_ANALYSIS_MEMORYBUILTINS_H
16
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/IRBuilder.h"
23#include "llvm/IR/InstVisitor.h"
24#include "llvm/IR/ValueHandle.h"
25#include <cstdint>
26#include <utility>
27
28namespace llvm {
29
30class AllocaInst;
31class Argument;
32class CallInst;
33class ConstantInt;
34class ConstantPointerNull;
35class DataLayout;
36class ExtractElementInst;
37class ExtractValueInst;
38class GEPOperator;
39class GlobalAlias;
40class GlobalVariable;
41class Instruction;
42class IntegerType;
43class IntrinsicInst;
44class IntToPtrInst;
45class LLVMContext;
46class LoadInst;
47class PHINode;
48class PointerType;
49class SelectInst;
50class Type;
51class UndefValue;
52class Value;
53
54/// Tests if a value is a call or invoke to a library function that
55/// allocates or reallocates memory (either malloc, calloc, realloc, or strdup
56/// like).
57bool isAllocationFn(const Value *V, const TargetLibraryInfo *TLI,
58 bool LookThroughBitCast = false);
59bool isAllocationFn(const Value *V,
60 function_ref<const TargetLibraryInfo &(Function &)> GetTLI,
61 bool LookThroughBitCast = false);
62
63/// Tests if a value is a call or invoke to a function that returns a
64/// NoAlias pointer (including malloc/calloc/realloc/strdup-like functions).
65bool isNoAliasFn(const Value *V, const TargetLibraryInfo *TLI,
66 bool LookThroughBitCast = false);
67
68/// Tests if a value is a call or invoke to a library function that
69/// allocates uninitialized memory (such as malloc).
70bool isMallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
71 bool LookThroughBitCast = false);
72bool isMallocLikeFn(const Value *V,
73 function_ref<const TargetLibraryInfo &(Function &)> GetTLI,
74 bool LookThroughBitCast = false);
75
76/// Tests if a value is a call or invoke to a library function that
77/// allocates uninitialized memory with alignment (such as aligned_alloc).
78bool isAlignedAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
79 bool LookThroughBitCast = false);
80bool isAlignedAllocLikeFn(
81 const Value *V, function_ref<const TargetLibraryInfo &(Function &)> GetTLI,
82 bool LookThroughBitCast = false);
83
84/// Tests if a value is a call or invoke to a library function that
85/// allocates zero-filled memory (such as calloc).
86bool isCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
87 bool LookThroughBitCast = false);
88
89/// Tests if a value is a call or invoke to a library function that
90/// allocates memory similar to malloc or calloc.
91bool isMallocOrCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
92 bool LookThroughBitCast = false);
93
94/// Tests if a value is a call or invoke to a library function that
95/// allocates memory (either malloc, calloc, or strdup like).
96bool isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
97 bool LookThroughBitCast = false);
98
99/// Tests if a value is a call or invoke to a library function that
100/// reallocates memory (e.g., realloc).
101bool isReallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
102 bool LookThroughBitCast = false);
103
104/// Tests if a function is a call or invoke to a library function that
105/// reallocates memory (e.g., realloc).
106bool isReallocLikeFn(const Function *F, const TargetLibraryInfo *TLI);
107
108/// Tests if a value is a call or invoke to a library function that
109/// allocates memory and throws if an allocation failed (e.g., new).
110bool isOpNewLikeFn(const Value *V, const TargetLibraryInfo *TLI,
111 bool LookThroughBitCast = false);
112
113/// Tests if a value is a call or invoke to a library function that
114/// allocates memory (strdup, strndup).
115bool isStrdupLikeFn(const Value *V, const TargetLibraryInfo *TLI,
116 bool LookThroughBitCast = false);
117
118//===----------------------------------------------------------------------===//
119// malloc Call Utility Functions.
120//
121
122/// extractMallocCall - Returns the corresponding CallInst if the instruction
123/// is a malloc call. Since CallInst::CreateMalloc() only creates calls, we
124/// ignore InvokeInst here.
125const CallInst *
126extractMallocCall(const Value *I,
127 function_ref<const TargetLibraryInfo &(Function &)> GetTLI);
128inline CallInst *
129extractMallocCall(Value *I,
130 function_ref<const TargetLibraryInfo &(Function &)> GetTLI) {
131 return const_cast<CallInst *>(extractMallocCall((const Value *)I, GetTLI));
132}
133
134/// getMallocType - Returns the PointerType resulting from the malloc call.
135/// The PointerType depends on the number of bitcast uses of the malloc call:
136/// 0: PointerType is the malloc calls' return type.
137/// 1: PointerType is the bitcast's result type.
138/// >1: Unique PointerType cannot be determined, return NULL.
139PointerType *getMallocType(const CallInst *CI, const TargetLibraryInfo *TLI);
140
141/// getMallocAllocatedType - Returns the Type allocated by malloc call.
142/// The Type depends on the number of bitcast uses of the malloc call:
143/// 0: PointerType is the malloc calls' return type.
144/// 1: PointerType is the bitcast's result type.
145/// >1: Unique PointerType cannot be determined, return NULL.
146Type *getMallocAllocatedType(const CallInst *CI, const TargetLibraryInfo *TLI);
147
148/// getMallocArraySize - Returns the array size of a malloc call. If the
149/// argument passed to malloc is a multiple of the size of the malloced type,
150/// then return that multiple. For non-array mallocs, the multiple is
151/// constant 1. Otherwise, return NULL for mallocs whose array size cannot be
152/// determined.
153Value *getMallocArraySize(CallInst *CI, const DataLayout &DL,
154 const TargetLibraryInfo *TLI,
155 bool LookThroughSExt = false);
156
157//===----------------------------------------------------------------------===//
158// calloc Call Utility Functions.
159//
160
161/// extractCallocCall - Returns the corresponding CallInst if the instruction
162/// is a calloc call.
163const CallInst *extractCallocCall(const Value *I, const TargetLibraryInfo *TLI);
164inline CallInst *extractCallocCall(Value *I, const TargetLibraryInfo *TLI) {
165 return const_cast<CallInst*>(extractCallocCall((const Value*)I, TLI));
166}
167
168
169//===----------------------------------------------------------------------===//
170// free Call Utility Functions.
171//
172
173/// isLibFreeFunction - Returns true if the function is a builtin free()
174bool isLibFreeFunction(const Function *F, const LibFunc TLIFn);
175
176/// isFreeCall - Returns non-null if the value is a call to the builtin free()
177const CallInst *isFreeCall(const Value *I, const TargetLibraryInfo *TLI);
178
179inline CallInst *isFreeCall(Value *I, const TargetLibraryInfo *TLI) {
180 return const_cast<CallInst*>(isFreeCall((const Value*)I, TLI));
181}
182
183//===----------------------------------------------------------------------===//
184// Utility functions to compute size of objects.
185//
186
187/// Various options to control the behavior of getObjectSize.
188struct ObjectSizeOpts {
189 /// Controls how we handle conditional statements with unknown conditions.
190 enum class Mode : uint8_t {
191 /// Fail to evaluate an unknown condition.
192 Exact,
193 /// Evaluate all branches of an unknown condition. If all evaluations
194 /// succeed, pick the minimum size.
195 Min,
196 /// Same as Min, except we pick the maximum size of all of the branches.
197 Max
198 };
199
200 /// How we want to evaluate this object's size.
201 Mode EvalMode = Mode::Exact;
202 /// Whether to round the result up to the alignment of allocas, byval
203 /// arguments, and global variables.
204 bool RoundToAlign = false;
205 /// If this is true, null pointers in address space 0 will be treated as
206 /// though they can't be evaluated. Otherwise, null is always considered to
207 /// point to a 0 byte region of memory.
208 bool NullIsUnknownSize = false;
209};
210
211/// Compute the size of the object pointed by Ptr. Returns true and the
212/// object size in Size if successful, and false otherwise. In this context, by
213/// object we mean the region of memory starting at Ptr to the end of the
214/// underlying object pointed to by Ptr.
215///
216/// WARNING: The object size returned is the allocation size. This does not
217/// imply dereferenceability at site of use since the object may be freeed in
218/// between.
219bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL,
220 const TargetLibraryInfo *TLI, ObjectSizeOpts Opts = {});
221
222/// Try to turn a call to \@llvm.objectsize into an integer value of the given
223/// Type. Returns null on failure. If MustSucceed is true, this function will
224/// not return null, and may return conservative values governed by the second
225/// argument of the call to objectsize.
226Value *lowerObjectSizeCall(IntrinsicInst *ObjectSize, const DataLayout &DL,
227 const TargetLibraryInfo *TLI, bool MustSucceed);
228
229
230
231using SizeOffsetType = std::pair<APInt, APInt>;
232
233/// Evaluate the size and offset of an object pointed to by a Value*
234/// statically. Fails if size or offset are not known at compile time.
235class ObjectSizeOffsetVisitor
236 : public InstVisitor<ObjectSizeOffsetVisitor, SizeOffsetType> {
237 const DataLayout &DL;
238 const TargetLibraryInfo *TLI;
239 ObjectSizeOpts Options;
240 unsigned IntTyBits;
241 APInt Zero;
242 SmallPtrSet<Instruction *, 8> SeenInsts;
243
244 APInt align(APInt Size, uint64_t Align);
245
246 SizeOffsetType unknown() {
247 return std::make_pair(APInt(), APInt());
248 }
249
250public:
251 ObjectSizeOffsetVisitor(const DataLayout &DL, const TargetLibraryInfo *TLI,
252 LLVMContext &Context, ObjectSizeOpts Options = {});
253
254 SizeOffsetType compute(Value *V);
255
256 static bool knownSize(const SizeOffsetType &SizeOffset) {
257 return SizeOffset.first.getBitWidth() > 1;
258 }
259
260 static bool knownOffset(const SizeOffsetType &SizeOffset) {
261 return SizeOffset.second.getBitWidth() > 1;
262 }
263
264 static bool bothKnown(const SizeOffsetType &SizeOffset) {
265 return knownSize(SizeOffset) && knownOffset(SizeOffset);
266 }
267
268 // These are "private", except they can't actually be made private. Only
269 // compute() should be used by external users.
270 SizeOffsetType visitAllocaInst(AllocaInst &I);
271 SizeOffsetType visitArgument(Argument &A);
272 SizeOffsetType visitCallBase(CallBase &CB);
273 SizeOffsetType visitConstantPointerNull(ConstantPointerNull&);
274 SizeOffsetType visitExtractElementInst(ExtractElementInst &I);
275 SizeOffsetType visitExtractValueInst(ExtractValueInst &I);
276 SizeOffsetType visitGEPOperator(GEPOperator &GEP);
277 SizeOffsetType visitGlobalAlias(GlobalAlias &GA);
278 SizeOffsetType visitGlobalVariable(GlobalVariable &GV);
279 SizeOffsetType visitIntToPtrInst(IntToPtrInst&);
280 SizeOffsetType visitLoadInst(LoadInst &I);
281 SizeOffsetType visitPHINode(PHINode&);
282 SizeOffsetType visitSelectInst(SelectInst &I);
283 SizeOffsetType visitUndefValue(UndefValue&);
284 SizeOffsetType visitInstruction(Instruction &I);
285
286private:
287 bool CheckedZextOrTrunc(APInt &I);
288};
289
290using SizeOffsetEvalType = std::pair<Value *, Value *>;
291
292/// Evaluate the size and offset of an object pointed to by a Value*.
293/// May create code to compute the result at run-time.
294class ObjectSizeOffsetEvaluator
295 : public InstVisitor<ObjectSizeOffsetEvaluator, SizeOffsetEvalType> {
296 using BuilderTy = IRBuilder<TargetFolder, IRBuilderCallbackInserter>;
297 using WeakEvalType = std::pair<WeakTrackingVH, WeakTrackingVH>;
298 using CacheMapTy = DenseMap<const Value *, WeakEvalType>;
299 using PtrSetTy = SmallPtrSet<const Value *, 8>;
300
301 const DataLayout &DL;
302 const TargetLibraryInfo *TLI;
303 LLVMContext &Context;
304 BuilderTy Builder;
305 IntegerType *IntTy;
306 Value *Zero;
307 CacheMapTy CacheMap;
308 PtrSetTy SeenVals;
309 ObjectSizeOpts EvalOpts;
310 SmallPtrSet<Instruction *, 8> InsertedInstructions;
311
312 SizeOffsetEvalType compute_(Value *V);
313
314public:
315 static SizeOffsetEvalType unknown() {
316 return std::make_pair(nullptr, nullptr);
317 }
318
319 ObjectSizeOffsetEvaluator(const DataLayout &DL, const TargetLibraryInfo *TLI,
320 LLVMContext &Context, ObjectSizeOpts EvalOpts = {});
321
322 SizeOffsetEvalType compute(Value *V);
323
324 bool knownSize(SizeOffsetEvalType SizeOffset) {
325 return SizeOffset.first;
326 }
327
328 bool knownOffset(SizeOffsetEvalType SizeOffset) {
329 return SizeOffset.second;
330 }
331
332 bool anyKnown(SizeOffsetEvalType SizeOffset) {
333 return knownSize(SizeOffset) || knownOffset(SizeOffset);
334 }
335
336 bool bothKnown(SizeOffsetEvalType SizeOffset) {
337 return knownSize(SizeOffset) && knownOffset(SizeOffset);
338 }
339
340 // The individual instruction visitors should be treated as private.
341 SizeOffsetEvalType visitAllocaInst(AllocaInst &I);
342 SizeOffsetEvalType visitCallBase(CallBase &CB);
343 SizeOffsetEvalType visitExtractElementInst(ExtractElementInst &I);
344 SizeOffsetEvalType visitExtractValueInst(ExtractValueInst &I);
345 SizeOffsetEvalType visitGEPOperator(GEPOperator &GEP);
346 SizeOffsetEvalType visitIntToPtrInst(IntToPtrInst&);
347 SizeOffsetEvalType visitLoadInst(LoadInst &I);
348 SizeOffsetEvalType visitPHINode(PHINode &PHI);
349 SizeOffsetEvalType visitSelectInst(SelectInst &I);
350 SizeOffsetEvalType visitInstruction(Instruction &I);
351};
352
353} // end namespace llvm
354
355#endif // LLVM_ANALYSIS_MEMORYBUILTINS_H
356