Line data Source code
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/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"
26 : #include <cstdint>
27 : #include <utility>
28 :
29 : namespace llvm {
30 :
31 : class AllocaInst;
32 : class Argument;
33 : class CallInst;
34 : class ConstantInt;
35 : class ConstantPointerNull;
36 : class DataLayout;
37 : class ExtractElementInst;
38 : class ExtractValueInst;
39 : class GEPOperator;
40 : class GlobalAlias;
41 : class GlobalVariable;
42 : class Instruction;
43 : class IntegerType;
44 : class IntrinsicInst;
45 : class IntToPtrInst;
46 : class LLVMContext;
47 : class LoadInst;
48 : class PHINode;
49 : class PointerType;
50 : class SelectInst;
51 : class TargetLibraryInfo;
52 : class Type;
53 : class UndefValue;
54 : class Value;
55 :
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
58 : /// like).
59 : bool isAllocationFn(const Value *V, const TargetLibraryInfo *TLI,
60 : bool LookThroughBitCast = false);
61 :
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);
66 :
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);
71 :
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);
76 :
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);
81 :
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);
86 :
87 : //===----------------------------------------------------------------------===//
88 : // malloc Call Utility Functions.
89 : //
90 :
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 104 : return const_cast<CallInst*>(extractMallocCall((const Value*)I, TLI));
97 : }
98 :
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);
105 :
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);
112 :
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
117 : /// determined.
118 : Value *getMallocArraySize(CallInst *CI, const DataLayout &DL,
119 : const TargetLibraryInfo *TLI,
120 : bool LookThroughSExt = false);
121 :
122 : //===----------------------------------------------------------------------===//
123 : // calloc Call Utility Functions.
124 : //
125 :
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));
131 : }
132 :
133 :
134 : //===----------------------------------------------------------------------===//
135 : // free Call Utility Functions.
136 : //
137 :
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);
140 :
141 : inline CallInst *isFreeCall(Value *I, const TargetLibraryInfo *TLI) {
142 24319215 : return const_cast<CallInst*>(isFreeCall((const Value*)I, TLI));
143 : }
144 :
145 : //===----------------------------------------------------------------------===//
146 : // Utility functions to compute size of objects.
147 : //
148 :
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.
154 : Exact,
155 : /// Evaluate all branches of an unknown condition. If all evaluations
156 : /// succeed, pick the minimum size.
157 : Min,
158 : /// Same as Min, except we pick the maximum size of all of the branches.
159 : Max
160 : };
161 :
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;
171 : };
172 :
173 : /// 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 = {});
179 :
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
184 : /// objectsize.
185 : ConstantInt *lowerObjectSizeCall(IntrinsicInst *ObjectSize,
186 : const DataLayout &DL,
187 : const TargetLibraryInfo *TLI,
188 : bool MustSucceed);
189 :
190 : using SizeOffsetType = std::pair<APInt, APInt>;
191 :
192 : /// 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;
199 : unsigned IntTyBits;
200 : APInt Zero;
201 : SmallPtrSet<Instruction *, 8> SeenInsts;
202 :
203 : APInt align(APInt Size, uint64_t Align);
204 :
205 0 : SizeOffsetType unknown() {
206 0 : return std::make_pair(APInt(), APInt());
207 : }
208 :
209 : public:
210 : ObjectSizeOffsetVisitor(const DataLayout &DL, const TargetLibraryInfo *TLI,
211 : LLVMContext &Context, ObjectSizeOpts Options = {});
212 :
213 : SizeOffsetType compute(Value *V);
214 :
215 : static bool knownSize(const SizeOffsetType &SizeOffset) {
216 22322022 : return SizeOffset.first.getBitWidth() > 1;
217 : }
218 :
219 : static bool knownOffset(const SizeOffsetType &SizeOffset) {
220 21786602 : return SizeOffset.second.getBitWidth() > 1;
221 : }
222 :
223 : static bool bothKnown(const SizeOffsetType &SizeOffset) {
224 22322010 : return knownSize(SizeOffset) && knownOffset(SizeOffset);
225 : }
226 :
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);
244 :
245 : private:
246 : bool CheckedZextOrTrunc(APInt &I);
247 : };
248 :
249 : using SizeOffsetEvalType = std::pair<Value *, Value *>;
250 :
251 : /// 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>;
259 :
260 : const DataLayout &DL;
261 : const TargetLibraryInfo *TLI;
262 : LLVMContext &Context;
263 : BuilderTy Builder;
264 : IntegerType *IntTy;
265 : Value *Zero;
266 : CacheMapTy CacheMap;
267 : PtrSetTy SeenVals;
268 : bool RoundToAlign;
269 :
270 0 : SizeOffsetEvalType unknown() {
271 0 : return std::make_pair(nullptr, nullptr);
272 : }
273 :
274 : SizeOffsetEvalType compute_(Value *V);
275 :
276 : public:
277 : ObjectSizeOffsetEvaluator(const DataLayout &DL, const TargetLibraryInfo *TLI,
278 : LLVMContext &Context, bool RoundToAlign = false);
279 :
280 : SizeOffsetEvalType compute(Value *V);
281 :
282 0 : bool knownSize(SizeOffsetEvalType SizeOffset) {
283 0 : return SizeOffset.first;
284 : }
285 :
286 0 : bool knownOffset(SizeOffsetEvalType SizeOffset) {
287 0 : return SizeOffset.second;
288 : }
289 :
290 0 : bool anyKnown(SizeOffsetEvalType SizeOffset) {
291 20 : return knownSize(SizeOffset) || knownOffset(SizeOffset);
292 : }
293 :
294 0 : bool bothKnown(SizeOffsetEvalType SizeOffset) {
295 138 : return knownSize(SizeOffset) && knownOffset(SizeOffset);
296 : }
297 :
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);
309 : };
310 :
311 : } // end namespace llvm
312 :
313 : #endif // LLVM_ANALYSIS_MEMORYBUILTINS_H
|
