]>
Commit | Line | Data |
---|---|---|
223e47cc LB |
1 | //===------ MemoryBuiltins.cpp - Identify calls to memory builtins --------===// |
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 | |
970d7e83 | 11 | // or free memory. |
223e47cc LB |
12 | // |
13 | //===----------------------------------------------------------------------===// | |
14 | ||
223e47cc | 15 | #include "llvm/Analysis/MemoryBuiltins.h" |
970d7e83 LB |
16 | #include "llvm/ADT/STLExtras.h" |
17 | #include "llvm/ADT/Statistic.h" | |
223e47cc | 18 | #include "llvm/Analysis/ValueTracking.h" |
970d7e83 LB |
19 | #include "llvm/IR/DataLayout.h" |
20 | #include "llvm/IR/GlobalVariable.h" | |
21 | #include "llvm/IR/Instructions.h" | |
22 | #include "llvm/IR/Intrinsics.h" | |
23 | #include "llvm/IR/Metadata.h" | |
24 | #include "llvm/IR/Module.h" | |
223e47cc LB |
25 | #include "llvm/Support/Debug.h" |
26 | #include "llvm/Support/MathExtras.h" | |
27 | #include "llvm/Support/raw_ostream.h" | |
223e47cc LB |
28 | #include "llvm/Target/TargetLibraryInfo.h" |
29 | #include "llvm/Transforms/Utils/Local.h" | |
30 | using namespace llvm; | |
31 | ||
1a4d82fc JJ |
32 | #define DEBUG_TYPE "memory-builtins" |
33 | ||
223e47cc | 34 | enum AllocType { |
1a4d82fc JJ |
35 | OpNewLike = 1<<0, // allocates; never returns null |
36 | MallocLike = 1<<1 | OpNewLike, // allocates; may return null | |
37 | CallocLike = 1<<2, // allocates + bzero | |
38 | ReallocLike = 1<<3, // reallocates | |
39 | StrDupLike = 1<<4, | |
223e47cc | 40 | AllocLike = MallocLike | CallocLike | StrDupLike, |
1a4d82fc | 41 | AnyAlloc = AllocLike | ReallocLike |
223e47cc LB |
42 | }; |
43 | ||
44 | struct AllocFnsTy { | |
45 | LibFunc::Func Func; | |
46 | AllocType AllocTy; | |
47 | unsigned char NumParams; | |
48 | // First and Second size parameters (or -1 if unused) | |
49 | signed char FstParam, SndParam; | |
50 | }; | |
51 | ||
52 | // FIXME: certain users need more information. E.g., SimplifyLibCalls needs to | |
53 | // know which functions are nounwind, noalias, nocapture parameters, etc. | |
54 | static const AllocFnsTy AllocationFnData[] = { | |
55 | {LibFunc::malloc, MallocLike, 1, 0, -1}, | |
56 | {LibFunc::valloc, MallocLike, 1, 0, -1}, | |
1a4d82fc | 57 | {LibFunc::Znwj, OpNewLike, 1, 0, -1}, // new(unsigned int) |
223e47cc | 58 | {LibFunc::ZnwjRKSt9nothrow_t, MallocLike, 2, 0, -1}, // new(unsigned int, nothrow) |
1a4d82fc | 59 | {LibFunc::Znwm, OpNewLike, 1, 0, -1}, // new(unsigned long) |
223e47cc | 60 | {LibFunc::ZnwmRKSt9nothrow_t, MallocLike, 2, 0, -1}, // new(unsigned long, nothrow) |
1a4d82fc | 61 | {LibFunc::Znaj, OpNewLike, 1, 0, -1}, // new[](unsigned int) |
223e47cc | 62 | {LibFunc::ZnajRKSt9nothrow_t, MallocLike, 2, 0, -1}, // new[](unsigned int, nothrow) |
1a4d82fc | 63 | {LibFunc::Znam, OpNewLike, 1, 0, -1}, // new[](unsigned long) |
223e47cc | 64 | {LibFunc::ZnamRKSt9nothrow_t, MallocLike, 2, 0, -1}, // new[](unsigned long, nothrow) |
223e47cc LB |
65 | {LibFunc::calloc, CallocLike, 2, 0, 1}, |
66 | {LibFunc::realloc, ReallocLike, 2, 1, -1}, | |
67 | {LibFunc::reallocf, ReallocLike, 2, 1, -1}, | |
68 | {LibFunc::strdup, StrDupLike, 1, -1, -1}, | |
c34b1796 AL |
69 | {LibFunc::strndup, StrDupLike, 2, 1, -1}, |
70 | {LibFunc::je_mallocx, MallocLike, 2, 0, -1} | |
1a4d82fc | 71 | // TODO: Handle "int posix_memalign(void **, size_t, size_t)" |
223e47cc LB |
72 | }; |
73 | ||
74 | ||
75 | static Function *getCalledFunction(const Value *V, bool LookThroughBitCast) { | |
76 | if (LookThroughBitCast) | |
77 | V = V->stripPointerCasts(); | |
78 | ||
79 | CallSite CS(const_cast<Value*>(V)); | |
80 | if (!CS.getInstruction()) | |
1a4d82fc JJ |
81 | return nullptr; |
82 | ||
83 | if (CS.isNoBuiltin()) | |
84 | return nullptr; | |
223e47cc LB |
85 | |
86 | Function *Callee = CS.getCalledFunction(); | |
87 | if (!Callee || !Callee->isDeclaration()) | |
1a4d82fc | 88 | return nullptr; |
223e47cc LB |
89 | return Callee; |
90 | } | |
91 | ||
92 | /// \brief Returns the allocation data for the given value if it is a call to a | |
93 | /// known allocation function, and NULL otherwise. | |
94 | static const AllocFnsTy *getAllocationData(const Value *V, AllocType AllocTy, | |
95 | const TargetLibraryInfo *TLI, | |
96 | bool LookThroughBitCast = false) { | |
970d7e83 LB |
97 | // Skip intrinsics |
98 | if (isa<IntrinsicInst>(V)) | |
1a4d82fc | 99 | return nullptr; |
970d7e83 | 100 | |
223e47cc LB |
101 | Function *Callee = getCalledFunction(V, LookThroughBitCast); |
102 | if (!Callee) | |
1a4d82fc | 103 | return nullptr; |
223e47cc LB |
104 | |
105 | // Make sure that the function is available. | |
106 | StringRef FnName = Callee->getName(); | |
107 | LibFunc::Func TLIFn; | |
108 | if (!TLI || !TLI->getLibFunc(FnName, TLIFn) || !TLI->has(TLIFn)) | |
1a4d82fc | 109 | return nullptr; |
223e47cc LB |
110 | |
111 | unsigned i = 0; | |
112 | bool found = false; | |
113 | for ( ; i < array_lengthof(AllocationFnData); ++i) { | |
114 | if (AllocationFnData[i].Func == TLIFn) { | |
115 | found = true; | |
116 | break; | |
117 | } | |
118 | } | |
119 | if (!found) | |
1a4d82fc | 120 | return nullptr; |
223e47cc LB |
121 | |
122 | const AllocFnsTy *FnData = &AllocationFnData[i]; | |
1a4d82fc JJ |
123 | if ((FnData->AllocTy & AllocTy) != FnData->AllocTy) |
124 | return nullptr; | |
223e47cc LB |
125 | |
126 | // Check function prototype. | |
127 | int FstParam = FnData->FstParam; | |
128 | int SndParam = FnData->SndParam; | |
129 | FunctionType *FTy = Callee->getFunctionType(); | |
130 | ||
131 | if (FTy->getReturnType() == Type::getInt8PtrTy(FTy->getContext()) && | |
132 | FTy->getNumParams() == FnData->NumParams && | |
133 | (FstParam < 0 || | |
134 | (FTy->getParamType(FstParam)->isIntegerTy(32) || | |
135 | FTy->getParamType(FstParam)->isIntegerTy(64))) && | |
136 | (SndParam < 0 || | |
137 | FTy->getParamType(SndParam)->isIntegerTy(32) || | |
138 | FTy->getParamType(SndParam)->isIntegerTy(64))) | |
139 | return FnData; | |
1a4d82fc | 140 | return nullptr; |
223e47cc LB |
141 | } |
142 | ||
143 | static bool hasNoAliasAttr(const Value *V, bool LookThroughBitCast) { | |
144 | ImmutableCallSite CS(LookThroughBitCast ? V->stripPointerCasts() : V); | |
145 | return CS && CS.hasFnAttr(Attribute::NoAlias); | |
146 | } | |
147 | ||
148 | ||
149 | /// \brief Tests if a value is a call or invoke to a library function that | |
150 | /// allocates or reallocates memory (either malloc, calloc, realloc, or strdup | |
151 | /// like). | |
152 | bool llvm::isAllocationFn(const Value *V, const TargetLibraryInfo *TLI, | |
153 | bool LookThroughBitCast) { | |
154 | return getAllocationData(V, AnyAlloc, TLI, LookThroughBitCast); | |
155 | } | |
156 | ||
157 | /// \brief Tests if a value is a call or invoke to a function that returns a | |
158 | /// NoAlias pointer (including malloc/calloc/realloc/strdup-like functions). | |
159 | bool llvm::isNoAliasFn(const Value *V, const TargetLibraryInfo *TLI, | |
160 | bool LookThroughBitCast) { | |
161 | // it's safe to consider realloc as noalias since accessing the original | |
162 | // pointer is undefined behavior | |
163 | return isAllocationFn(V, TLI, LookThroughBitCast) || | |
164 | hasNoAliasAttr(V, LookThroughBitCast); | |
165 | } | |
166 | ||
167 | /// \brief Tests if a value is a call or invoke to a library function that | |
168 | /// allocates uninitialized memory (such as malloc). | |
169 | bool llvm::isMallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, | |
170 | bool LookThroughBitCast) { | |
171 | return getAllocationData(V, MallocLike, TLI, LookThroughBitCast); | |
172 | } | |
173 | ||
174 | /// \brief Tests if a value is a call or invoke to a library function that | |
175 | /// allocates zero-filled memory (such as calloc). | |
176 | bool llvm::isCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, | |
177 | bool LookThroughBitCast) { | |
178 | return getAllocationData(V, CallocLike, TLI, LookThroughBitCast); | |
179 | } | |
180 | ||
181 | /// \brief Tests if a value is a call or invoke to a library function that | |
182 | /// allocates memory (either malloc, calloc, or strdup like). | |
183 | bool llvm::isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI, | |
184 | bool LookThroughBitCast) { | |
185 | return getAllocationData(V, AllocLike, TLI, LookThroughBitCast); | |
186 | } | |
187 | ||
188 | /// \brief Tests if a value is a call or invoke to a library function that | |
189 | /// reallocates memory (such as realloc). | |
190 | bool llvm::isReallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, | |
191 | bool LookThroughBitCast) { | |
192 | return getAllocationData(V, ReallocLike, TLI, LookThroughBitCast); | |
193 | } | |
194 | ||
1a4d82fc JJ |
195 | /// \brief Tests if a value is a call or invoke to a library function that |
196 | /// allocates memory and never returns null (such as operator new). | |
197 | bool llvm::isOperatorNewLikeFn(const Value *V, const TargetLibraryInfo *TLI, | |
198 | bool LookThroughBitCast) { | |
199 | return getAllocationData(V, OpNewLike, TLI, LookThroughBitCast); | |
200 | } | |
201 | ||
223e47cc LB |
202 | /// extractMallocCall - Returns the corresponding CallInst if the instruction |
203 | /// is a malloc call. Since CallInst::CreateMalloc() only creates calls, we | |
204 | /// ignore InvokeInst here. | |
205 | const CallInst *llvm::extractMallocCall(const Value *I, | |
206 | const TargetLibraryInfo *TLI) { | |
1a4d82fc | 207 | return isMallocLikeFn(I, TLI) ? dyn_cast<CallInst>(I) : nullptr; |
223e47cc LB |
208 | } |
209 | ||
1a4d82fc | 210 | static Value *computeArraySize(const CallInst *CI, const DataLayout *DL, |
223e47cc LB |
211 | const TargetLibraryInfo *TLI, |
212 | bool LookThroughSExt = false) { | |
213 | if (!CI) | |
1a4d82fc | 214 | return nullptr; |
223e47cc LB |
215 | |
216 | // The size of the malloc's result type must be known to determine array size. | |
217 | Type *T = getMallocAllocatedType(CI, TLI); | |
1a4d82fc JJ |
218 | if (!T || !T->isSized() || !DL) |
219 | return nullptr; | |
223e47cc | 220 | |
1a4d82fc | 221 | unsigned ElementSize = DL->getTypeAllocSize(T); |
223e47cc | 222 | if (StructType *ST = dyn_cast<StructType>(T)) |
1a4d82fc | 223 | ElementSize = DL->getStructLayout(ST)->getSizeInBytes(); |
223e47cc LB |
224 | |
225 | // If malloc call's arg can be determined to be a multiple of ElementSize, | |
226 | // return the multiple. Otherwise, return NULL. | |
227 | Value *MallocArg = CI->getArgOperand(0); | |
1a4d82fc | 228 | Value *Multiple = nullptr; |
223e47cc LB |
229 | if (ComputeMultiple(MallocArg, ElementSize, Multiple, |
230 | LookThroughSExt)) | |
231 | return Multiple; | |
232 | ||
1a4d82fc | 233 | return nullptr; |
223e47cc LB |
234 | } |
235 | ||
970d7e83 | 236 | /// isArrayMalloc - Returns the corresponding CallInst if the instruction |
223e47cc LB |
237 | /// is a call to malloc whose array size can be determined and the array size |
238 | /// is not constant 1. Otherwise, return NULL. | |
239 | const CallInst *llvm::isArrayMalloc(const Value *I, | |
1a4d82fc | 240 | const DataLayout *DL, |
223e47cc LB |
241 | const TargetLibraryInfo *TLI) { |
242 | const CallInst *CI = extractMallocCall(I, TLI); | |
1a4d82fc | 243 | Value *ArraySize = computeArraySize(CI, DL, TLI); |
223e47cc | 244 | |
970d7e83 LB |
245 | if (ConstantInt *ConstSize = dyn_cast_or_null<ConstantInt>(ArraySize)) |
246 | if (ConstSize->isOne()) | |
247 | return CI; | |
223e47cc LB |
248 | |
249 | // CI is a non-array malloc or we can't figure out that it is an array malloc. | |
1a4d82fc | 250 | return nullptr; |
223e47cc LB |
251 | } |
252 | ||
253 | /// getMallocType - Returns the PointerType resulting from the malloc call. | |
254 | /// The PointerType depends on the number of bitcast uses of the malloc call: | |
255 | /// 0: PointerType is the calls' return type. | |
256 | /// 1: PointerType is the bitcast's result type. | |
257 | /// >1: Unique PointerType cannot be determined, return NULL. | |
258 | PointerType *llvm::getMallocType(const CallInst *CI, | |
259 | const TargetLibraryInfo *TLI) { | |
260 | assert(isMallocLikeFn(CI, TLI) && "getMallocType and not malloc call"); | |
970d7e83 | 261 | |
1a4d82fc | 262 | PointerType *MallocType = nullptr; |
223e47cc LB |
263 | unsigned NumOfBitCastUses = 0; |
264 | ||
265 | // Determine if CallInst has a bitcast use. | |
1a4d82fc JJ |
266 | for (Value::const_user_iterator UI = CI->user_begin(), E = CI->user_end(); |
267 | UI != E;) | |
223e47cc LB |
268 | if (const BitCastInst *BCI = dyn_cast<BitCastInst>(*UI++)) { |
269 | MallocType = cast<PointerType>(BCI->getDestTy()); | |
270 | NumOfBitCastUses++; | |
271 | } | |
272 | ||
273 | // Malloc call has 1 bitcast use, so type is the bitcast's destination type. | |
274 | if (NumOfBitCastUses == 1) | |
275 | return MallocType; | |
276 | ||
277 | // Malloc call was not bitcast, so type is the malloc function's return type. | |
278 | if (NumOfBitCastUses == 0) | |
279 | return cast<PointerType>(CI->getType()); | |
280 | ||
281 | // Type could not be determined. | |
1a4d82fc | 282 | return nullptr; |
223e47cc LB |
283 | } |
284 | ||
285 | /// getMallocAllocatedType - Returns the Type allocated by malloc call. | |
286 | /// The Type depends on the number of bitcast uses of the malloc call: | |
287 | /// 0: PointerType is the malloc calls' return type. | |
288 | /// 1: PointerType is the bitcast's result type. | |
289 | /// >1: Unique PointerType cannot be determined, return NULL. | |
290 | Type *llvm::getMallocAllocatedType(const CallInst *CI, | |
291 | const TargetLibraryInfo *TLI) { | |
292 | PointerType *PT = getMallocType(CI, TLI); | |
1a4d82fc | 293 | return PT ? PT->getElementType() : nullptr; |
223e47cc LB |
294 | } |
295 | ||
970d7e83 | 296 | /// getMallocArraySize - Returns the array size of a malloc call. If the |
223e47cc LB |
297 | /// argument passed to malloc is a multiple of the size of the malloced type, |
298 | /// then return that multiple. For non-array mallocs, the multiple is | |
299 | /// constant 1. Otherwise, return NULL for mallocs whose array size cannot be | |
300 | /// determined. | |
1a4d82fc | 301 | Value *llvm::getMallocArraySize(CallInst *CI, const DataLayout *DL, |
223e47cc LB |
302 | const TargetLibraryInfo *TLI, |
303 | bool LookThroughSExt) { | |
304 | assert(isMallocLikeFn(CI, TLI) && "getMallocArraySize and not malloc call"); | |
1a4d82fc | 305 | return computeArraySize(CI, DL, TLI, LookThroughSExt); |
223e47cc LB |
306 | } |
307 | ||
308 | ||
309 | /// extractCallocCall - Returns the corresponding CallInst if the instruction | |
310 | /// is a calloc call. | |
311 | const CallInst *llvm::extractCallocCall(const Value *I, | |
312 | const TargetLibraryInfo *TLI) { | |
1a4d82fc | 313 | return isCallocLikeFn(I, TLI) ? cast<CallInst>(I) : nullptr; |
223e47cc LB |
314 | } |
315 | ||
316 | ||
317 | /// isFreeCall - Returns non-null if the value is a call to the builtin free() | |
318 | const CallInst *llvm::isFreeCall(const Value *I, const TargetLibraryInfo *TLI) { | |
319 | const CallInst *CI = dyn_cast<CallInst>(I); | |
970d7e83 | 320 | if (!CI || isa<IntrinsicInst>(CI)) |
1a4d82fc | 321 | return nullptr; |
223e47cc | 322 | Function *Callee = CI->getCalledFunction(); |
1a4d82fc JJ |
323 | if (Callee == nullptr || !Callee->isDeclaration()) |
324 | return nullptr; | |
223e47cc LB |
325 | |
326 | StringRef FnName = Callee->getName(); | |
327 | LibFunc::Func TLIFn; | |
328 | if (!TLI || !TLI->getLibFunc(FnName, TLIFn) || !TLI->has(TLIFn)) | |
1a4d82fc JJ |
329 | return nullptr; |
330 | ||
331 | unsigned ExpectedNumParams; | |
332 | if (TLIFn == LibFunc::free || | |
333 | TLIFn == LibFunc::ZdlPv || // operator delete(void*) | |
334 | TLIFn == LibFunc::ZdaPv) // operator delete[](void*) | |
335 | ExpectedNumParams = 1; | |
85aaf69f SL |
336 | else if (TLIFn == LibFunc::ZdlPvj || // delete(void*, uint) |
337 | TLIFn == LibFunc::ZdlPvm || // delete(void*, ulong) | |
338 | TLIFn == LibFunc::ZdlPvRKSt9nothrow_t || // delete(void*, nothrow) | |
339 | TLIFn == LibFunc::ZdaPvj || // delete[](void*, uint) | |
340 | TLIFn == LibFunc::ZdaPvm || // delete[](void*, ulong) | |
1a4d82fc JJ |
341 | TLIFn == LibFunc::ZdaPvRKSt9nothrow_t) // delete[](void*, nothrow) |
342 | ExpectedNumParams = 2; | |
c34b1796 AL |
343 | else if (TLIFn == LibFunc::je_sdallocx) |
344 | ExpectedNumParams = 3; | |
1a4d82fc JJ |
345 | else |
346 | return nullptr; | |
223e47cc LB |
347 | |
348 | // Check free prototype. | |
970d7e83 | 349 | // FIXME: workaround for PR5130, this will be obsolete when a nobuiltin |
223e47cc LB |
350 | // attribute will exist. |
351 | FunctionType *FTy = Callee->getFunctionType(); | |
352 | if (!FTy->getReturnType()->isVoidTy()) | |
1a4d82fc JJ |
353 | return nullptr; |
354 | if (FTy->getNumParams() != ExpectedNumParams) | |
355 | return nullptr; | |
223e47cc | 356 | if (FTy->getParamType(0) != Type::getInt8PtrTy(Callee->getContext())) |
1a4d82fc | 357 | return nullptr; |
223e47cc LB |
358 | |
359 | return CI; | |
360 | } | |
361 | ||
362 | ||
363 | ||
364 | //===----------------------------------------------------------------------===// | |
365 | // Utility functions to compute size of objects. | |
366 | // | |
367 | ||
368 | ||
369 | /// \brief Compute the size of the object pointed by Ptr. Returns true and the | |
370 | /// object size in Size if successful, and false otherwise. | |
371 | /// If RoundToAlign is true, then Size is rounded up to the aligment of allocas, | |
372 | /// byval arguments, and global variables. | |
1a4d82fc | 373 | bool llvm::getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout *DL, |
223e47cc | 374 | const TargetLibraryInfo *TLI, bool RoundToAlign) { |
1a4d82fc | 375 | if (!DL) |
223e47cc LB |
376 | return false; |
377 | ||
1a4d82fc | 378 | ObjectSizeOffsetVisitor Visitor(DL, TLI, Ptr->getContext(), RoundToAlign); |
223e47cc LB |
379 | SizeOffsetType Data = Visitor.compute(const_cast<Value*>(Ptr)); |
380 | if (!Visitor.bothKnown(Data)) | |
381 | return false; | |
382 | ||
383 | APInt ObjSize = Data.first, Offset = Data.second; | |
384 | // check for overflow | |
385 | if (Offset.slt(0) || ObjSize.ult(Offset)) | |
386 | Size = 0; | |
387 | else | |
388 | Size = (ObjSize - Offset).getZExtValue(); | |
389 | return true; | |
390 | } | |
391 | ||
392 | ||
393 | STATISTIC(ObjectVisitorArgument, | |
394 | "Number of arguments with unsolved size and offset"); | |
395 | STATISTIC(ObjectVisitorLoad, | |
396 | "Number of load instructions with unsolved size and offset"); | |
397 | ||
398 | ||
399 | APInt ObjectSizeOffsetVisitor::align(APInt Size, uint64_t Align) { | |
400 | if (RoundToAlign && Align) | |
401 | return APInt(IntTyBits, RoundUpToAlignment(Size.getZExtValue(), Align)); | |
402 | return Size; | |
403 | } | |
404 | ||
1a4d82fc | 405 | ObjectSizeOffsetVisitor::ObjectSizeOffsetVisitor(const DataLayout *DL, |
223e47cc LB |
406 | const TargetLibraryInfo *TLI, |
407 | LLVMContext &Context, | |
408 | bool RoundToAlign) | |
1a4d82fc JJ |
409 | : DL(DL), TLI(TLI), RoundToAlign(RoundToAlign) { |
410 | // Pointer size must be rechecked for each object visited since it could have | |
411 | // a different address space. | |
223e47cc LB |
412 | } |
413 | ||
414 | SizeOffsetType ObjectSizeOffsetVisitor::compute(Value *V) { | |
1a4d82fc JJ |
415 | IntTyBits = DL->getPointerTypeSizeInBits(V->getType()); |
416 | Zero = APInt::getNullValue(IntTyBits); | |
223e47cc | 417 | |
1a4d82fc JJ |
418 | V = V->stripPointerCasts(); |
419 | if (Instruction *I = dyn_cast<Instruction>(V)) { | |
420 | // If we have already seen this instruction, bail out. Cycles can happen in | |
421 | // unreachable code after constant propagation. | |
85aaf69f | 422 | if (!SeenInsts.insert(I).second) |
1a4d82fc | 423 | return unknown(); |
970d7e83 | 424 | |
223e47cc | 425 | if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) |
1a4d82fc JJ |
426 | return visitGEPOperator(*GEP); |
427 | return visit(*I); | |
223e47cc LB |
428 | } |
429 | if (Argument *A = dyn_cast<Argument>(V)) | |
430 | return visitArgument(*A); | |
431 | if (ConstantPointerNull *P = dyn_cast<ConstantPointerNull>(V)) | |
432 | return visitConstantPointerNull(*P); | |
970d7e83 LB |
433 | if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) |
434 | return visitGlobalAlias(*GA); | |
223e47cc LB |
435 | if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) |
436 | return visitGlobalVariable(*GV); | |
437 | if (UndefValue *UV = dyn_cast<UndefValue>(V)) | |
438 | return visitUndefValue(*UV); | |
439 | if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) { | |
440 | if (CE->getOpcode() == Instruction::IntToPtr) | |
441 | return unknown(); // clueless | |
1a4d82fc JJ |
442 | if (CE->getOpcode() == Instruction::GetElementPtr) |
443 | return visitGEPOperator(cast<GEPOperator>(*CE)); | |
223e47cc LB |
444 | } |
445 | ||
446 | DEBUG(dbgs() << "ObjectSizeOffsetVisitor::compute() unhandled value: " << *V | |
447 | << '\n'); | |
448 | return unknown(); | |
449 | } | |
450 | ||
451 | SizeOffsetType ObjectSizeOffsetVisitor::visitAllocaInst(AllocaInst &I) { | |
452 | if (!I.getAllocatedType()->isSized()) | |
453 | return unknown(); | |
454 | ||
1a4d82fc | 455 | APInt Size(IntTyBits, DL->getTypeAllocSize(I.getAllocatedType())); |
223e47cc LB |
456 | if (!I.isArrayAllocation()) |
457 | return std::make_pair(align(Size, I.getAlignment()), Zero); | |
458 | ||
459 | Value *ArraySize = I.getArraySize(); | |
460 | if (const ConstantInt *C = dyn_cast<ConstantInt>(ArraySize)) { | |
461 | Size *= C->getValue().zextOrSelf(IntTyBits); | |
462 | return std::make_pair(align(Size, I.getAlignment()), Zero); | |
463 | } | |
464 | return unknown(); | |
465 | } | |
466 | ||
467 | SizeOffsetType ObjectSizeOffsetVisitor::visitArgument(Argument &A) { | |
468 | // no interprocedural analysis is done at the moment | |
1a4d82fc | 469 | if (!A.hasByValOrInAllocaAttr()) { |
223e47cc LB |
470 | ++ObjectVisitorArgument; |
471 | return unknown(); | |
472 | } | |
473 | PointerType *PT = cast<PointerType>(A.getType()); | |
1a4d82fc | 474 | APInt Size(IntTyBits, DL->getTypeAllocSize(PT->getElementType())); |
223e47cc LB |
475 | return std::make_pair(align(Size, A.getParamAlignment()), Zero); |
476 | } | |
477 | ||
478 | SizeOffsetType ObjectSizeOffsetVisitor::visitCallSite(CallSite CS) { | |
479 | const AllocFnsTy *FnData = getAllocationData(CS.getInstruction(), AnyAlloc, | |
480 | TLI); | |
481 | if (!FnData) | |
482 | return unknown(); | |
483 | ||
484 | // handle strdup-like functions separately | |
485 | if (FnData->AllocTy == StrDupLike) { | |
486 | APInt Size(IntTyBits, GetStringLength(CS.getArgument(0))); | |
487 | if (!Size) | |
488 | return unknown(); | |
489 | ||
490 | // strndup limits strlen | |
491 | if (FnData->FstParam > 0) { | |
492 | ConstantInt *Arg= dyn_cast<ConstantInt>(CS.getArgument(FnData->FstParam)); | |
493 | if (!Arg) | |
494 | return unknown(); | |
495 | ||
496 | APInt MaxSize = Arg->getValue().zextOrSelf(IntTyBits); | |
497 | if (Size.ugt(MaxSize)) | |
498 | Size = MaxSize + 1; | |
499 | } | |
500 | return std::make_pair(Size, Zero); | |
501 | } | |
502 | ||
503 | ConstantInt *Arg = dyn_cast<ConstantInt>(CS.getArgument(FnData->FstParam)); | |
504 | if (!Arg) | |
505 | return unknown(); | |
506 | ||
507 | APInt Size = Arg->getValue().zextOrSelf(IntTyBits); | |
508 | // size determined by just 1 parameter | |
509 | if (FnData->SndParam < 0) | |
510 | return std::make_pair(Size, Zero); | |
511 | ||
512 | Arg = dyn_cast<ConstantInt>(CS.getArgument(FnData->SndParam)); | |
513 | if (!Arg) | |
514 | return unknown(); | |
515 | ||
516 | Size *= Arg->getValue().zextOrSelf(IntTyBits); | |
517 | return std::make_pair(Size, Zero); | |
518 | ||
519 | // TODO: handle more standard functions (+ wchar cousins): | |
520 | // - strdup / strndup | |
521 | // - strcpy / strncpy | |
522 | // - strcat / strncat | |
523 | // - memcpy / memmove | |
524 | // - strcat / strncat | |
525 | // - memset | |
526 | } | |
527 | ||
528 | SizeOffsetType | |
529 | ObjectSizeOffsetVisitor::visitConstantPointerNull(ConstantPointerNull&) { | |
530 | return std::make_pair(Zero, Zero); | |
531 | } | |
532 | ||
533 | SizeOffsetType | |
534 | ObjectSizeOffsetVisitor::visitExtractElementInst(ExtractElementInst&) { | |
535 | return unknown(); | |
536 | } | |
537 | ||
538 | SizeOffsetType | |
539 | ObjectSizeOffsetVisitor::visitExtractValueInst(ExtractValueInst&) { | |
540 | // Easy cases were already folded by previous passes. | |
541 | return unknown(); | |
542 | } | |
543 | ||
544 | SizeOffsetType ObjectSizeOffsetVisitor::visitGEPOperator(GEPOperator &GEP) { | |
545 | SizeOffsetType PtrData = compute(GEP.getPointerOperand()); | |
970d7e83 | 546 | APInt Offset(IntTyBits, 0); |
1a4d82fc | 547 | if (!bothKnown(PtrData) || !GEP.accumulateConstantOffset(*DL, Offset)) |
223e47cc LB |
548 | return unknown(); |
549 | ||
223e47cc LB |
550 | return std::make_pair(PtrData.first, PtrData.second + Offset); |
551 | } | |
552 | ||
970d7e83 LB |
553 | SizeOffsetType ObjectSizeOffsetVisitor::visitGlobalAlias(GlobalAlias &GA) { |
554 | if (GA.mayBeOverridden()) | |
555 | return unknown(); | |
556 | return compute(GA.getAliasee()); | |
557 | } | |
558 | ||
223e47cc LB |
559 | SizeOffsetType ObjectSizeOffsetVisitor::visitGlobalVariable(GlobalVariable &GV){ |
560 | if (!GV.hasDefinitiveInitializer()) | |
561 | return unknown(); | |
562 | ||
1a4d82fc | 563 | APInt Size(IntTyBits, DL->getTypeAllocSize(GV.getType()->getElementType())); |
223e47cc LB |
564 | return std::make_pair(align(Size, GV.getAlignment()), Zero); |
565 | } | |
566 | ||
567 | SizeOffsetType ObjectSizeOffsetVisitor::visitIntToPtrInst(IntToPtrInst&) { | |
568 | // clueless | |
569 | return unknown(); | |
570 | } | |
571 | ||
572 | SizeOffsetType ObjectSizeOffsetVisitor::visitLoadInst(LoadInst&) { | |
573 | ++ObjectVisitorLoad; | |
574 | return unknown(); | |
575 | } | |
576 | ||
1a4d82fc JJ |
577 | SizeOffsetType ObjectSizeOffsetVisitor::visitPHINode(PHINode&) { |
578 | // too complex to analyze statically. | |
579 | return unknown(); | |
223e47cc LB |
580 | } |
581 | ||
582 | SizeOffsetType ObjectSizeOffsetVisitor::visitSelectInst(SelectInst &I) { | |
583 | SizeOffsetType TrueSide = compute(I.getTrueValue()); | |
584 | SizeOffsetType FalseSide = compute(I.getFalseValue()); | |
585 | if (bothKnown(TrueSide) && bothKnown(FalseSide) && TrueSide == FalseSide) | |
586 | return TrueSide; | |
587 | return unknown(); | |
588 | } | |
589 | ||
590 | SizeOffsetType ObjectSizeOffsetVisitor::visitUndefValue(UndefValue&) { | |
591 | return std::make_pair(Zero, Zero); | |
592 | } | |
593 | ||
594 | SizeOffsetType ObjectSizeOffsetVisitor::visitInstruction(Instruction &I) { | |
595 | DEBUG(dbgs() << "ObjectSizeOffsetVisitor unknown instruction:" << I << '\n'); | |
596 | return unknown(); | |
597 | } | |
598 | ||
1a4d82fc JJ |
599 | ObjectSizeOffsetEvaluator::ObjectSizeOffsetEvaluator(const DataLayout *DL, |
600 | const TargetLibraryInfo *TLI, | |
601 | LLVMContext &Context, | |
602 | bool RoundToAlign) | |
603 | : DL(DL), TLI(TLI), Context(Context), Builder(Context, TargetFolder(DL)), | |
604 | RoundToAlign(RoundToAlign) { | |
605 | // IntTy and Zero must be set for each compute() since the address space may | |
606 | // be different for later objects. | |
223e47cc LB |
607 | } |
608 | ||
609 | SizeOffsetEvalType ObjectSizeOffsetEvaluator::compute(Value *V) { | |
1a4d82fc JJ |
610 | // XXX - Are vectors of pointers possible here? |
611 | IntTy = cast<IntegerType>(DL->getIntPtrType(V->getType())); | |
612 | Zero = ConstantInt::get(IntTy, 0); | |
613 | ||
223e47cc LB |
614 | SizeOffsetEvalType Result = compute_(V); |
615 | ||
616 | if (!bothKnown(Result)) { | |
617 | // erase everything that was computed in this iteration from the cache, so | |
618 | // that no dangling references are left behind. We could be a bit smarter if | |
619 | // we kept a dependency graph. It's probably not worth the complexity. | |
620 | for (PtrSetTy::iterator I=SeenVals.begin(), E=SeenVals.end(); I != E; ++I) { | |
621 | CacheMapTy::iterator CacheIt = CacheMap.find(*I); | |
622 | // non-computable results can be safely cached | |
623 | if (CacheIt != CacheMap.end() && anyKnown(CacheIt->second)) | |
624 | CacheMap.erase(CacheIt); | |
625 | } | |
626 | } | |
627 | ||
628 | SeenVals.clear(); | |
629 | return Result; | |
630 | } | |
631 | ||
632 | SizeOffsetEvalType ObjectSizeOffsetEvaluator::compute_(Value *V) { | |
1a4d82fc | 633 | ObjectSizeOffsetVisitor Visitor(DL, TLI, Context, RoundToAlign); |
223e47cc LB |
634 | SizeOffsetType Const = Visitor.compute(V); |
635 | if (Visitor.bothKnown(Const)) | |
636 | return std::make_pair(ConstantInt::get(Context, Const.first), | |
637 | ConstantInt::get(Context, Const.second)); | |
638 | ||
639 | V = V->stripPointerCasts(); | |
640 | ||
641 | // check cache | |
642 | CacheMapTy::iterator CacheIt = CacheMap.find(V); | |
643 | if (CacheIt != CacheMap.end()) | |
644 | return CacheIt->second; | |
645 | ||
646 | // always generate code immediately before the instruction being | |
647 | // processed, so that the generated code dominates the same BBs | |
648 | Instruction *PrevInsertPoint = Builder.GetInsertPoint(); | |
649 | if (Instruction *I = dyn_cast<Instruction>(V)) | |
650 | Builder.SetInsertPoint(I); | |
651 | ||
223e47cc LB |
652 | // now compute the size and offset |
653 | SizeOffsetEvalType Result; | |
1a4d82fc JJ |
654 | |
655 | // Record the pointers that were handled in this run, so that they can be | |
656 | // cleaned later if something fails. We also use this set to break cycles that | |
657 | // can occur in dead code. | |
85aaf69f | 658 | if (!SeenVals.insert(V).second) { |
1a4d82fc JJ |
659 | Result = unknown(); |
660 | } else if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { | |
223e47cc LB |
661 | Result = visitGEPOperator(*GEP); |
662 | } else if (Instruction *I = dyn_cast<Instruction>(V)) { | |
663 | Result = visit(*I); | |
664 | } else if (isa<Argument>(V) || | |
665 | (isa<ConstantExpr>(V) && | |
666 | cast<ConstantExpr>(V)->getOpcode() == Instruction::IntToPtr) || | |
970d7e83 | 667 | isa<GlobalAlias>(V) || |
223e47cc LB |
668 | isa<GlobalVariable>(V)) { |
669 | // ignore values where we cannot do more than what ObjectSizeVisitor can | |
670 | Result = unknown(); | |
671 | } else { | |
672 | DEBUG(dbgs() << "ObjectSizeOffsetEvaluator::compute() unhandled value: " | |
673 | << *V << '\n'); | |
674 | Result = unknown(); | |
675 | } | |
676 | ||
677 | if (PrevInsertPoint) | |
678 | Builder.SetInsertPoint(PrevInsertPoint); | |
679 | ||
680 | // Don't reuse CacheIt since it may be invalid at this point. | |
681 | CacheMap[V] = Result; | |
682 | return Result; | |
683 | } | |
684 | ||
685 | SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitAllocaInst(AllocaInst &I) { | |
686 | if (!I.getAllocatedType()->isSized()) | |
687 | return unknown(); | |
688 | ||
689 | // must be a VLA | |
690 | assert(I.isArrayAllocation()); | |
691 | Value *ArraySize = I.getArraySize(); | |
692 | Value *Size = ConstantInt::get(ArraySize->getType(), | |
1a4d82fc | 693 | DL->getTypeAllocSize(I.getAllocatedType())); |
223e47cc LB |
694 | Size = Builder.CreateMul(Size, ArraySize); |
695 | return std::make_pair(Size, Zero); | |
696 | } | |
697 | ||
698 | SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitCallSite(CallSite CS) { | |
699 | const AllocFnsTy *FnData = getAllocationData(CS.getInstruction(), AnyAlloc, | |
700 | TLI); | |
701 | if (!FnData) | |
702 | return unknown(); | |
703 | ||
704 | // handle strdup-like functions separately | |
705 | if (FnData->AllocTy == StrDupLike) { | |
706 | // TODO | |
707 | return unknown(); | |
708 | } | |
709 | ||
710 | Value *FirstArg = CS.getArgument(FnData->FstParam); | |
711 | FirstArg = Builder.CreateZExt(FirstArg, IntTy); | |
712 | if (FnData->SndParam < 0) | |
713 | return std::make_pair(FirstArg, Zero); | |
714 | ||
715 | Value *SecondArg = CS.getArgument(FnData->SndParam); | |
716 | SecondArg = Builder.CreateZExt(SecondArg, IntTy); | |
717 | Value *Size = Builder.CreateMul(FirstArg, SecondArg); | |
718 | return std::make_pair(Size, Zero); | |
719 | ||
720 | // TODO: handle more standard functions (+ wchar cousins): | |
721 | // - strdup / strndup | |
722 | // - strcpy / strncpy | |
723 | // - strcat / strncat | |
724 | // - memcpy / memmove | |
725 | // - strcat / strncat | |
726 | // - memset | |
727 | } | |
728 | ||
729 | SizeOffsetEvalType | |
730 | ObjectSizeOffsetEvaluator::visitExtractElementInst(ExtractElementInst&) { | |
731 | return unknown(); | |
732 | } | |
733 | ||
734 | SizeOffsetEvalType | |
735 | ObjectSizeOffsetEvaluator::visitExtractValueInst(ExtractValueInst&) { | |
736 | return unknown(); | |
737 | } | |
738 | ||
739 | SizeOffsetEvalType | |
740 | ObjectSizeOffsetEvaluator::visitGEPOperator(GEPOperator &GEP) { | |
741 | SizeOffsetEvalType PtrData = compute_(GEP.getPointerOperand()); | |
742 | if (!bothKnown(PtrData)) | |
743 | return unknown(); | |
744 | ||
1a4d82fc | 745 | Value *Offset = EmitGEPOffset(&Builder, *DL, &GEP, /*NoAssumptions=*/true); |
223e47cc LB |
746 | Offset = Builder.CreateAdd(PtrData.second, Offset); |
747 | return std::make_pair(PtrData.first, Offset); | |
748 | } | |
749 | ||
750 | SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitIntToPtrInst(IntToPtrInst&) { | |
751 | // clueless | |
752 | return unknown(); | |
753 | } | |
754 | ||
755 | SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitLoadInst(LoadInst&) { | |
756 | return unknown(); | |
757 | } | |
758 | ||
759 | SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitPHINode(PHINode &PHI) { | |
760 | // create 2 PHIs: one for size and another for offset | |
761 | PHINode *SizePHI = Builder.CreatePHI(IntTy, PHI.getNumIncomingValues()); | |
762 | PHINode *OffsetPHI = Builder.CreatePHI(IntTy, PHI.getNumIncomingValues()); | |
763 | ||
764 | // insert right away in the cache to handle recursive PHIs | |
765 | CacheMap[&PHI] = std::make_pair(SizePHI, OffsetPHI); | |
766 | ||
767 | // compute offset/size for each PHI incoming pointer | |
768 | for (unsigned i = 0, e = PHI.getNumIncomingValues(); i != e; ++i) { | |
769 | Builder.SetInsertPoint(PHI.getIncomingBlock(i)->getFirstInsertionPt()); | |
770 | SizeOffsetEvalType EdgeData = compute_(PHI.getIncomingValue(i)); | |
771 | ||
772 | if (!bothKnown(EdgeData)) { | |
773 | OffsetPHI->replaceAllUsesWith(UndefValue::get(IntTy)); | |
774 | OffsetPHI->eraseFromParent(); | |
775 | SizePHI->replaceAllUsesWith(UndefValue::get(IntTy)); | |
776 | SizePHI->eraseFromParent(); | |
777 | return unknown(); | |
778 | } | |
779 | SizePHI->addIncoming(EdgeData.first, PHI.getIncomingBlock(i)); | |
780 | OffsetPHI->addIncoming(EdgeData.second, PHI.getIncomingBlock(i)); | |
781 | } | |
782 | ||
783 | Value *Size = SizePHI, *Offset = OffsetPHI, *Tmp; | |
784 | if ((Tmp = SizePHI->hasConstantValue())) { | |
785 | Size = Tmp; | |
786 | SizePHI->replaceAllUsesWith(Size); | |
787 | SizePHI->eraseFromParent(); | |
788 | } | |
789 | if ((Tmp = OffsetPHI->hasConstantValue())) { | |
790 | Offset = Tmp; | |
791 | OffsetPHI->replaceAllUsesWith(Offset); | |
792 | OffsetPHI->eraseFromParent(); | |
793 | } | |
794 | return std::make_pair(Size, Offset); | |
795 | } | |
796 | ||
797 | SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitSelectInst(SelectInst &I) { | |
798 | SizeOffsetEvalType TrueSide = compute_(I.getTrueValue()); | |
799 | SizeOffsetEvalType FalseSide = compute_(I.getFalseValue()); | |
800 | ||
801 | if (!bothKnown(TrueSide) || !bothKnown(FalseSide)) | |
802 | return unknown(); | |
803 | if (TrueSide == FalseSide) | |
804 | return TrueSide; | |
805 | ||
806 | Value *Size = Builder.CreateSelect(I.getCondition(), TrueSide.first, | |
807 | FalseSide.first); | |
808 | Value *Offset = Builder.CreateSelect(I.getCondition(), TrueSide.second, | |
809 | FalseSide.second); | |
810 | return std::make_pair(Size, Offset); | |
811 | } | |
812 | ||
813 | SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitInstruction(Instruction &I) { | |
814 | DEBUG(dbgs() << "ObjectSizeOffsetEvaluator unknown instruction:" << I <<'\n'); | |
815 | return unknown(); | |
816 | } |