1 //===------ MemoryBuiltins.cpp - Identify calls to memory builtins --------===//
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 #define DEBUG_TYPE "memory-builtins"
16 #include "llvm/ADT/Statistic.h"
17 #include "llvm/ADT/STLExtras.h"
18 #include "llvm/Analysis/MemoryBuiltins.h"
19 #include "llvm/GlobalVariable.h"
20 #include "llvm/Instructions.h"
21 #include "llvm/Intrinsics.h"
22 #include "llvm/Metadata.h"
23 #include "llvm/Module.h"
24 #include "llvm/Analysis/ValueTracking.h"
25 #include "llvm/Support/Debug.h"
26 #include "llvm/Support/MathExtras.h"
27 #include "llvm/Support/raw_ostream.h"
28 #include "llvm/Target/TargetData.h"
29 #include "llvm/Target/TargetLibraryInfo.h"
30 #include "llvm/Transforms/Utils/Local.h"
34 MallocLike
= 1<<0, // allocates
35 CallocLike
= 1<<1, // allocates + bzero
36 ReallocLike
= 1<<2, // reallocates
38 AllocLike
= MallocLike
| CallocLike
| StrDupLike
,
39 AnyAlloc
= MallocLike
| CallocLike
| ReallocLike
| StrDupLike
45 unsigned char NumParams
;
46 // First and Second size parameters (or -1 if unused)
47 signed char FstParam
, SndParam
;
50 // FIXME: certain users need more information. E.g., SimplifyLibCalls needs to
51 // know which functions are nounwind, noalias, nocapture parameters, etc.
52 static const AllocFnsTy AllocationFnData
[] = {
53 {LibFunc::malloc
, MallocLike
, 1, 0, -1},
54 {LibFunc::valloc
, MallocLike
, 1, 0, -1},
55 {LibFunc::Znwj
, MallocLike
, 1, 0, -1}, // new(unsigned int)
56 {LibFunc::ZnwjRKSt9nothrow_t
, MallocLike
, 2, 0, -1}, // new(unsigned int, nothrow)
57 {LibFunc::Znwm
, MallocLike
, 1, 0, -1}, // new(unsigned long)
58 {LibFunc::ZnwmRKSt9nothrow_t
, MallocLike
, 2, 0, -1}, // new(unsigned long, nothrow)
59 {LibFunc::Znaj
, MallocLike
, 1, 0, -1}, // new[](unsigned int)
60 {LibFunc::ZnajRKSt9nothrow_t
, MallocLike
, 2, 0, -1}, // new[](unsigned int, nothrow)
61 {LibFunc::Znam
, MallocLike
, 1, 0, -1}, // new[](unsigned long)
62 {LibFunc::ZnamRKSt9nothrow_t
, MallocLike
, 2, 0, -1}, // new[](unsigned long, nothrow)
63 {LibFunc::posix_memalign
, MallocLike
, 3, 2, -1},
64 {LibFunc::calloc
, CallocLike
, 2, 0, 1},
65 {LibFunc::realloc
, ReallocLike
, 2, 1, -1},
66 {LibFunc::reallocf
, ReallocLike
, 2, 1, -1},
67 {LibFunc::strdup
, StrDupLike
, 1, -1, -1},
68 {LibFunc::strndup
, StrDupLike
, 2, 1, -1}
72 static Function
*getCalledFunction(const Value
*V
, bool LookThroughBitCast
) {
73 if (LookThroughBitCast
)
74 V
= V
->stripPointerCasts();
76 CallSite
CS(const_cast<Value
*>(V
));
77 if (!CS
.getInstruction())
80 Function
*Callee
= CS
.getCalledFunction();
81 if (!Callee
|| !Callee
->isDeclaration())
86 /// \brief Returns the allocation data for the given value if it is a call to a
87 /// known allocation function, and NULL otherwise.
88 static const AllocFnsTy
*getAllocationData(const Value
*V
, AllocType AllocTy
,
89 const TargetLibraryInfo
*TLI
,
90 bool LookThroughBitCast
= false) {
91 Function
*Callee
= getCalledFunction(V
, LookThroughBitCast
);
95 // Make sure that the function is available.
96 StringRef FnName
= Callee
->getName();
98 if (!TLI
|| !TLI
->getLibFunc(FnName
, TLIFn
) || !TLI
->has(TLIFn
))
103 for ( ; i
< array_lengthof(AllocationFnData
); ++i
) {
104 if (AllocationFnData
[i
].Func
== TLIFn
) {
112 const AllocFnsTy
*FnData
= &AllocationFnData
[i
];
113 if ((FnData
->AllocTy
& AllocTy
) == 0)
116 // Check function prototype.
117 int FstParam
= FnData
->FstParam
;
118 int SndParam
= FnData
->SndParam
;
119 FunctionType
*FTy
= Callee
->getFunctionType();
121 if (FTy
->getReturnType() == Type::getInt8PtrTy(FTy
->getContext()) &&
122 FTy
->getNumParams() == FnData
->NumParams
&&
124 (FTy
->getParamType(FstParam
)->isIntegerTy(32) ||
125 FTy
->getParamType(FstParam
)->isIntegerTy(64))) &&
127 FTy
->getParamType(SndParam
)->isIntegerTy(32) ||
128 FTy
->getParamType(SndParam
)->isIntegerTy(64)))
133 static bool hasNoAliasAttr(const Value
*V
, bool LookThroughBitCast
) {
134 ImmutableCallSite
CS(LookThroughBitCast
? V
->stripPointerCasts() : V
);
135 return CS
&& CS
.hasFnAttr(Attribute::NoAlias
);
139 /// \brief Tests if a value is a call or invoke to a library function that
140 /// allocates or reallocates memory (either malloc, calloc, realloc, or strdup
142 bool llvm::isAllocationFn(const Value
*V
, const TargetLibraryInfo
*TLI
,
143 bool LookThroughBitCast
) {
144 return getAllocationData(V
, AnyAlloc
, TLI
, LookThroughBitCast
);
147 /// \brief Tests if a value is a call or invoke to a function that returns a
148 /// NoAlias pointer (including malloc/calloc/realloc/strdup-like functions).
149 bool llvm::isNoAliasFn(const Value
*V
, const TargetLibraryInfo
*TLI
,
150 bool LookThroughBitCast
) {
151 // it's safe to consider realloc as noalias since accessing the original
152 // pointer is undefined behavior
153 return isAllocationFn(V
, TLI
, LookThroughBitCast
) ||
154 hasNoAliasAttr(V
, LookThroughBitCast
);
157 /// \brief Tests if a value is a call or invoke to a library function that
158 /// allocates uninitialized memory (such as malloc).
159 bool llvm::isMallocLikeFn(const Value
*V
, const TargetLibraryInfo
*TLI
,
160 bool LookThroughBitCast
) {
161 return getAllocationData(V
, MallocLike
, TLI
, LookThroughBitCast
);
164 /// \brief Tests if a value is a call or invoke to a library function that
165 /// allocates zero-filled memory (such as calloc).
166 bool llvm::isCallocLikeFn(const Value
*V
, const TargetLibraryInfo
*TLI
,
167 bool LookThroughBitCast
) {
168 return getAllocationData(V
, CallocLike
, TLI
, LookThroughBitCast
);
171 /// \brief Tests if a value is a call or invoke to a library function that
172 /// allocates memory (either malloc, calloc, or strdup like).
173 bool llvm::isAllocLikeFn(const Value
*V
, const TargetLibraryInfo
*TLI
,
174 bool LookThroughBitCast
) {
175 return getAllocationData(V
, AllocLike
, TLI
, LookThroughBitCast
);
178 /// \brief Tests if a value is a call or invoke to a library function that
179 /// reallocates memory (such as realloc).
180 bool llvm::isReallocLikeFn(const Value
*V
, const TargetLibraryInfo
*TLI
,
181 bool LookThroughBitCast
) {
182 return getAllocationData(V
, ReallocLike
, TLI
, LookThroughBitCast
);
185 /// extractMallocCall - Returns the corresponding CallInst if the instruction
186 /// is a malloc call. Since CallInst::CreateMalloc() only creates calls, we
187 /// ignore InvokeInst here.
188 const CallInst
*llvm::extractMallocCall(const Value
*I
,
189 const TargetLibraryInfo
*TLI
) {
190 return isMallocLikeFn(I
, TLI
) ? dyn_cast
<CallInst
>(I
) : 0;
193 static Value
*computeArraySize(const CallInst
*CI
, const TargetData
*TD
,
194 const TargetLibraryInfo
*TLI
,
195 bool LookThroughSExt
= false) {
199 // The size of the malloc's result type must be known to determine array size.
200 Type
*T
= getMallocAllocatedType(CI
, TLI
);
201 if (!T
|| !T
->isSized() || !TD
)
204 unsigned ElementSize
= TD
->getTypeAllocSize(T
);
205 if (StructType
*ST
= dyn_cast
<StructType
>(T
))
206 ElementSize
= TD
->getStructLayout(ST
)->getSizeInBytes();
208 // If malloc call's arg can be determined to be a multiple of ElementSize,
209 // return the multiple. Otherwise, return NULL.
210 Value
*MallocArg
= CI
->getArgOperand(0);
211 Value
*Multiple
= NULL
;
212 if (ComputeMultiple(MallocArg
, ElementSize
, Multiple
,
219 /// isArrayMalloc - Returns the corresponding CallInst if the instruction
220 /// is a call to malloc whose array size can be determined and the array size
221 /// is not constant 1. Otherwise, return NULL.
222 const CallInst
*llvm::isArrayMalloc(const Value
*I
,
223 const TargetData
*TD
,
224 const TargetLibraryInfo
*TLI
) {
225 const CallInst
*CI
= extractMallocCall(I
, TLI
);
226 Value
*ArraySize
= computeArraySize(CI
, TD
, TLI
);
229 ArraySize
!= ConstantInt::get(CI
->getArgOperand(0)->getType(), 1))
232 // CI is a non-array malloc or we can't figure out that it is an array malloc.
236 /// getMallocType - Returns the PointerType resulting from the malloc call.
237 /// The PointerType depends on the number of bitcast uses of the malloc call:
238 /// 0: PointerType is the calls' return type.
239 /// 1: PointerType is the bitcast's result type.
240 /// >1: Unique PointerType cannot be determined, return NULL.
241 PointerType
*llvm::getMallocType(const CallInst
*CI
,
242 const TargetLibraryInfo
*TLI
) {
243 assert(isMallocLikeFn(CI
, TLI
) && "getMallocType and not malloc call");
245 PointerType
*MallocType
= NULL
;
246 unsigned NumOfBitCastUses
= 0;
248 // Determine if CallInst has a bitcast use.
249 for (Value::const_use_iterator UI
= CI
->use_begin(), E
= CI
->use_end();
251 if (const BitCastInst
*BCI
= dyn_cast
<BitCastInst
>(*UI
++)) {
252 MallocType
= cast
<PointerType
>(BCI
->getDestTy());
256 // Malloc call has 1 bitcast use, so type is the bitcast's destination type.
257 if (NumOfBitCastUses
== 1)
260 // Malloc call was not bitcast, so type is the malloc function's return type.
261 if (NumOfBitCastUses
== 0)
262 return cast
<PointerType
>(CI
->getType());
264 // Type could not be determined.
268 /// getMallocAllocatedType - Returns the Type allocated by malloc call.
269 /// The Type depends on the number of bitcast uses of the malloc call:
270 /// 0: PointerType is the malloc calls' return type.
271 /// 1: PointerType is the bitcast's result type.
272 /// >1: Unique PointerType cannot be determined, return NULL.
273 Type
*llvm::getMallocAllocatedType(const CallInst
*CI
,
274 const TargetLibraryInfo
*TLI
) {
275 PointerType
*PT
= getMallocType(CI
, TLI
);
276 return PT
? PT
->getElementType() : NULL
;
279 /// getMallocArraySize - Returns the array size of a malloc call. If the
280 /// argument passed to malloc is a multiple of the size of the malloced type,
281 /// then return that multiple. For non-array mallocs, the multiple is
282 /// constant 1. Otherwise, return NULL for mallocs whose array size cannot be
284 Value
*llvm::getMallocArraySize(CallInst
*CI
, const TargetData
*TD
,
285 const TargetLibraryInfo
*TLI
,
286 bool LookThroughSExt
) {
287 assert(isMallocLikeFn(CI
, TLI
) && "getMallocArraySize and not malloc call");
288 return computeArraySize(CI
, TD
, TLI
, LookThroughSExt
);
292 /// extractCallocCall - Returns the corresponding CallInst if the instruction
293 /// is a calloc call.
294 const CallInst
*llvm::extractCallocCall(const Value
*I
,
295 const TargetLibraryInfo
*TLI
) {
296 return isCallocLikeFn(I
, TLI
) ? cast
<CallInst
>(I
) : 0;
300 /// isFreeCall - Returns non-null if the value is a call to the builtin free()
301 const CallInst
*llvm::isFreeCall(const Value
*I
, const TargetLibraryInfo
*TLI
) {
302 const CallInst
*CI
= dyn_cast
<CallInst
>(I
);
305 Function
*Callee
= CI
->getCalledFunction();
306 if (Callee
== 0 || !Callee
->isDeclaration())
309 StringRef FnName
= Callee
->getName();
311 if (!TLI
|| !TLI
->getLibFunc(FnName
, TLIFn
) || !TLI
->has(TLIFn
))
314 if (TLIFn
!= LibFunc::free
&&
315 TLIFn
!= LibFunc::ZdlPv
&& // operator delete(void*)
316 TLIFn
!= LibFunc::ZdaPv
) // operator delete[](void*)
319 // Check free prototype.
320 // FIXME: workaround for PR5130, this will be obsolete when a nobuiltin
321 // attribute will exist.
322 FunctionType
*FTy
= Callee
->getFunctionType();
323 if (!FTy
->getReturnType()->isVoidTy())
325 if (FTy
->getNumParams() != 1)
327 if (FTy
->getParamType(0) != Type::getInt8PtrTy(Callee
->getContext()))
335 //===----------------------------------------------------------------------===//
336 // Utility functions to compute size of objects.
340 /// \brief Compute the size of the object pointed by Ptr. Returns true and the
341 /// object size in Size if successful, and false otherwise.
342 /// If RoundToAlign is true, then Size is rounded up to the aligment of allocas,
343 /// byval arguments, and global variables.
344 bool llvm::getObjectSize(const Value
*Ptr
, uint64_t &Size
, const TargetData
*TD
,
345 const TargetLibraryInfo
*TLI
, bool RoundToAlign
) {
349 ObjectSizeOffsetVisitor
Visitor(TD
, TLI
, Ptr
->getContext(), RoundToAlign
);
350 SizeOffsetType Data
= Visitor
.compute(const_cast<Value
*>(Ptr
));
351 if (!Visitor
.bothKnown(Data
))
354 APInt ObjSize
= Data
.first
, Offset
= Data
.second
;
355 // check for overflow
356 if (Offset
.slt(0) || ObjSize
.ult(Offset
))
359 Size
= (ObjSize
- Offset
).getZExtValue();
364 STATISTIC(ObjectVisitorArgument
,
365 "Number of arguments with unsolved size and offset");
366 STATISTIC(ObjectVisitorLoad
,
367 "Number of load instructions with unsolved size and offset");
370 APInt
ObjectSizeOffsetVisitor::align(APInt Size
, uint64_t Align
) {
371 if (RoundToAlign
&& Align
)
372 return APInt(IntTyBits
, RoundUpToAlignment(Size
.getZExtValue(), Align
));
376 ObjectSizeOffsetVisitor::ObjectSizeOffsetVisitor(const TargetData
*TD
,
377 const TargetLibraryInfo
*TLI
,
378 LLVMContext
&Context
,
380 : TD(TD
), TLI(TLI
), RoundToAlign(RoundToAlign
) {
381 IntegerType
*IntTy
= TD
->getIntPtrType(Context
);
382 IntTyBits
= IntTy
->getBitWidth();
383 Zero
= APInt::getNullValue(IntTyBits
);
386 SizeOffsetType
ObjectSizeOffsetVisitor::compute(Value
*V
) {
387 V
= V
->stripPointerCasts();
388 if (Instruction
*I
= dyn_cast
<Instruction
>(V
)) {
389 // If we have already seen this instruction, bail out. Cycles can happen in
390 // unreachable code after constant propagation.
391 if (!SeenInsts
.insert(I
))
394 if (GEPOperator
*GEP
= dyn_cast
<GEPOperator
>(V
))
395 return visitGEPOperator(*GEP
);
398 if (Argument
*A
= dyn_cast
<Argument
>(V
))
399 return visitArgument(*A
);
400 if (ConstantPointerNull
*P
= dyn_cast
<ConstantPointerNull
>(V
))
401 return visitConstantPointerNull(*P
);
402 if (GlobalVariable
*GV
= dyn_cast
<GlobalVariable
>(V
))
403 return visitGlobalVariable(*GV
);
404 if (UndefValue
*UV
= dyn_cast
<UndefValue
>(V
))
405 return visitUndefValue(*UV
);
406 if (ConstantExpr
*CE
= dyn_cast
<ConstantExpr
>(V
)) {
407 if (CE
->getOpcode() == Instruction::IntToPtr
)
408 return unknown(); // clueless
409 if (CE
->getOpcode() == Instruction::GetElementPtr
)
410 return visitGEPOperator(cast
<GEPOperator
>(*CE
));
413 DEBUG(dbgs() << "ObjectSizeOffsetVisitor::compute() unhandled value: " << *V
418 SizeOffsetType
ObjectSizeOffsetVisitor::visitAllocaInst(AllocaInst
&I
) {
419 if (!I
.getAllocatedType()->isSized())
422 APInt
Size(IntTyBits
, TD
->getTypeAllocSize(I
.getAllocatedType()));
423 if (!I
.isArrayAllocation())
424 return std::make_pair(align(Size
, I
.getAlignment()), Zero
);
426 Value
*ArraySize
= I
.getArraySize();
427 if (const ConstantInt
*C
= dyn_cast
<ConstantInt
>(ArraySize
)) {
428 Size
*= C
->getValue().zextOrSelf(IntTyBits
);
429 return std::make_pair(align(Size
, I
.getAlignment()), Zero
);
434 SizeOffsetType
ObjectSizeOffsetVisitor::visitArgument(Argument
&A
) {
435 // no interprocedural analysis is done at the moment
436 if (!A
.hasByValAttr()) {
437 ++ObjectVisitorArgument
;
440 PointerType
*PT
= cast
<PointerType
>(A
.getType());
441 APInt
Size(IntTyBits
, TD
->getTypeAllocSize(PT
->getElementType()));
442 return std::make_pair(align(Size
, A
.getParamAlignment()), Zero
);
445 SizeOffsetType
ObjectSizeOffsetVisitor::visitCallSite(CallSite CS
) {
446 const AllocFnsTy
*FnData
= getAllocationData(CS
.getInstruction(), AnyAlloc
,
451 // handle strdup-like functions separately
452 if (FnData
->AllocTy
== StrDupLike
) {
453 APInt
Size(IntTyBits
, GetStringLength(CS
.getArgument(0)));
457 // strndup limits strlen
458 if (FnData
->FstParam
> 0) {
459 ConstantInt
*Arg
= dyn_cast
<ConstantInt
>(CS
.getArgument(FnData
->FstParam
));
463 APInt MaxSize
= Arg
->getValue().zextOrSelf(IntTyBits
);
464 if (Size
.ugt(MaxSize
))
467 return std::make_pair(Size
, Zero
);
470 ConstantInt
*Arg
= dyn_cast
<ConstantInt
>(CS
.getArgument(FnData
->FstParam
));
474 APInt Size
= Arg
->getValue().zextOrSelf(IntTyBits
);
475 // size determined by just 1 parameter
476 if (FnData
->SndParam
< 0)
477 return std::make_pair(Size
, Zero
);
479 Arg
= dyn_cast
<ConstantInt
>(CS
.getArgument(FnData
->SndParam
));
483 Size
*= Arg
->getValue().zextOrSelf(IntTyBits
);
484 return std::make_pair(Size
, Zero
);
486 // TODO: handle more standard functions (+ wchar cousins):
487 // - strdup / strndup
488 // - strcpy / strncpy
489 // - strcat / strncat
490 // - memcpy / memmove
491 // - strcat / strncat
496 ObjectSizeOffsetVisitor::visitConstantPointerNull(ConstantPointerNull
&) {
497 return std::make_pair(Zero
, Zero
);
501 ObjectSizeOffsetVisitor::visitExtractElementInst(ExtractElementInst
&) {
506 ObjectSizeOffsetVisitor::visitExtractValueInst(ExtractValueInst
&) {
507 // Easy cases were already folded by previous passes.
511 SizeOffsetType
ObjectSizeOffsetVisitor::visitGEPOperator(GEPOperator
&GEP
) {
512 SizeOffsetType PtrData
= compute(GEP
.getPointerOperand());
513 if (!bothKnown(PtrData
) || !GEP
.hasAllConstantIndices())
516 SmallVector
<Value
*, 8> Ops(GEP
.idx_begin(), GEP
.idx_end());
517 APInt
Offset(IntTyBits
,TD
->getIndexedOffset(GEP
.getPointerOperandType(),Ops
));
518 return std::make_pair(PtrData
.first
, PtrData
.second
+ Offset
);
521 SizeOffsetType
ObjectSizeOffsetVisitor::visitGlobalVariable(GlobalVariable
&GV
){
522 if (!GV
.hasDefinitiveInitializer())
525 APInt
Size(IntTyBits
, TD
->getTypeAllocSize(GV
.getType()->getElementType()));
526 return std::make_pair(align(Size
, GV
.getAlignment()), Zero
);
529 SizeOffsetType
ObjectSizeOffsetVisitor::visitIntToPtrInst(IntToPtrInst
&) {
534 SizeOffsetType
ObjectSizeOffsetVisitor::visitLoadInst(LoadInst
&) {
539 SizeOffsetType
ObjectSizeOffsetVisitor::visitPHINode(PHINode
&) {
540 // too complex to analyze statically.
544 SizeOffsetType
ObjectSizeOffsetVisitor::visitSelectInst(SelectInst
&I
) {
545 SizeOffsetType TrueSide
= compute(I
.getTrueValue());
546 SizeOffsetType FalseSide
= compute(I
.getFalseValue());
547 if (bothKnown(TrueSide
) && bothKnown(FalseSide
) && TrueSide
== FalseSide
)
552 SizeOffsetType
ObjectSizeOffsetVisitor::visitUndefValue(UndefValue
&) {
553 return std::make_pair(Zero
, Zero
);
556 SizeOffsetType
ObjectSizeOffsetVisitor::visitInstruction(Instruction
&I
) {
557 DEBUG(dbgs() << "ObjectSizeOffsetVisitor unknown instruction:" << I
<< '\n');
562 ObjectSizeOffsetEvaluator::ObjectSizeOffsetEvaluator(const TargetData
*TD
,
563 const TargetLibraryInfo
*TLI
,
564 LLVMContext
&Context
)
565 : TD(TD
), TLI(TLI
), Context(Context
), Builder(Context
, TargetFolder(TD
)) {
566 IntTy
= TD
->getIntPtrType(Context
);
567 Zero
= ConstantInt::get(IntTy
, 0);
570 SizeOffsetEvalType
ObjectSizeOffsetEvaluator::compute(Value
*V
) {
571 SizeOffsetEvalType Result
= compute_(V
);
573 if (!bothKnown(Result
)) {
574 // erase everything that was computed in this iteration from the cache, so
575 // that no dangling references are left behind. We could be a bit smarter if
576 // we kept a dependency graph. It's probably not worth the complexity.
577 for (PtrSetTy::iterator I
=SeenVals
.begin(), E
=SeenVals
.end(); I
!= E
; ++I
) {
578 CacheMapTy::iterator CacheIt
= CacheMap
.find(*I
);
579 // non-computable results can be safely cached
580 if (CacheIt
!= CacheMap
.end() && anyKnown(CacheIt
->second
))
581 CacheMap
.erase(CacheIt
);
589 SizeOffsetEvalType
ObjectSizeOffsetEvaluator::compute_(Value
*V
) {
590 ObjectSizeOffsetVisitor
Visitor(TD
, TLI
, Context
);
591 SizeOffsetType Const
= Visitor
.compute(V
);
592 if (Visitor
.bothKnown(Const
))
593 return std::make_pair(ConstantInt::get(Context
, Const
.first
),
594 ConstantInt::get(Context
, Const
.second
));
596 V
= V
->stripPointerCasts();
599 CacheMapTy::iterator CacheIt
= CacheMap
.find(V
);
600 if (CacheIt
!= CacheMap
.end())
601 return CacheIt
->second
;
603 // always generate code immediately before the instruction being
604 // processed, so that the generated code dominates the same BBs
605 Instruction
*PrevInsertPoint
= Builder
.GetInsertPoint();
606 if (Instruction
*I
= dyn_cast
<Instruction
>(V
))
607 Builder
.SetInsertPoint(I
);
609 // record the pointers that were handled in this run, so that they can be
610 // cleaned later if something fails
613 // now compute the size and offset
614 SizeOffsetEvalType Result
;
615 if (GEPOperator
*GEP
= dyn_cast
<GEPOperator
>(V
)) {
616 Result
= visitGEPOperator(*GEP
);
617 } else if (Instruction
*I
= dyn_cast
<Instruction
>(V
)) {
619 } else if (isa
<Argument
>(V
) ||
620 (isa
<ConstantExpr
>(V
) &&
621 cast
<ConstantExpr
>(V
)->getOpcode() == Instruction::IntToPtr
) ||
622 isa
<GlobalVariable
>(V
)) {
623 // ignore values where we cannot do more than what ObjectSizeVisitor can
626 DEBUG(dbgs() << "ObjectSizeOffsetEvaluator::compute() unhandled value: "
632 Builder
.SetInsertPoint(PrevInsertPoint
);
634 // Don't reuse CacheIt since it may be invalid at this point.
635 CacheMap
[V
] = Result
;
639 SizeOffsetEvalType
ObjectSizeOffsetEvaluator::visitAllocaInst(AllocaInst
&I
) {
640 if (!I
.getAllocatedType()->isSized())
644 assert(I
.isArrayAllocation());
645 Value
*ArraySize
= I
.getArraySize();
646 Value
*Size
= ConstantInt::get(ArraySize
->getType(),
647 TD
->getTypeAllocSize(I
.getAllocatedType()));
648 Size
= Builder
.CreateMul(Size
, ArraySize
);
649 return std::make_pair(Size
, Zero
);
652 SizeOffsetEvalType
ObjectSizeOffsetEvaluator::visitCallSite(CallSite CS
) {
653 const AllocFnsTy
*FnData
= getAllocationData(CS
.getInstruction(), AnyAlloc
,
658 // handle strdup-like functions separately
659 if (FnData
->AllocTy
== StrDupLike
) {
664 Value
*FirstArg
= CS
.getArgument(FnData
->FstParam
);
665 FirstArg
= Builder
.CreateZExt(FirstArg
, IntTy
);
666 if (FnData
->SndParam
< 0)
667 return std::make_pair(FirstArg
, Zero
);
669 Value
*SecondArg
= CS
.getArgument(FnData
->SndParam
);
670 SecondArg
= Builder
.CreateZExt(SecondArg
, IntTy
);
671 Value
*Size
= Builder
.CreateMul(FirstArg
, SecondArg
);
672 return std::make_pair(Size
, Zero
);
674 // TODO: handle more standard functions (+ wchar cousins):
675 // - strdup / strndup
676 // - strcpy / strncpy
677 // - strcat / strncat
678 // - memcpy / memmove
679 // - strcat / strncat
684 ObjectSizeOffsetEvaluator::visitExtractElementInst(ExtractElementInst
&) {
689 ObjectSizeOffsetEvaluator::visitExtractValueInst(ExtractValueInst
&) {
694 ObjectSizeOffsetEvaluator::visitGEPOperator(GEPOperator
&GEP
) {
695 SizeOffsetEvalType PtrData
= compute_(GEP
.getPointerOperand());
696 if (!bothKnown(PtrData
))
699 Value
*Offset
= EmitGEPOffset(&Builder
, *TD
, &GEP
, /*NoAssumptions=*/true);
700 Offset
= Builder
.CreateAdd(PtrData
.second
, Offset
);
701 return std::make_pair(PtrData
.first
, Offset
);
704 SizeOffsetEvalType
ObjectSizeOffsetEvaluator::visitIntToPtrInst(IntToPtrInst
&) {
709 SizeOffsetEvalType
ObjectSizeOffsetEvaluator::visitLoadInst(LoadInst
&) {
713 SizeOffsetEvalType
ObjectSizeOffsetEvaluator::visitPHINode(PHINode
&PHI
) {
714 // create 2 PHIs: one for size and another for offset
715 PHINode
*SizePHI
= Builder
.CreatePHI(IntTy
, PHI
.getNumIncomingValues());
716 PHINode
*OffsetPHI
= Builder
.CreatePHI(IntTy
, PHI
.getNumIncomingValues());
718 // insert right away in the cache to handle recursive PHIs
719 CacheMap
[&PHI
] = std::make_pair(SizePHI
, OffsetPHI
);
721 // compute offset/size for each PHI incoming pointer
722 for (unsigned i
= 0, e
= PHI
.getNumIncomingValues(); i
!= e
; ++i
) {
723 Builder
.SetInsertPoint(PHI
.getIncomingBlock(i
)->getFirstInsertionPt());
724 SizeOffsetEvalType EdgeData
= compute_(PHI
.getIncomingValue(i
));
726 if (!bothKnown(EdgeData
)) {
727 OffsetPHI
->replaceAllUsesWith(UndefValue::get(IntTy
));
728 OffsetPHI
->eraseFromParent();
729 SizePHI
->replaceAllUsesWith(UndefValue::get(IntTy
));
730 SizePHI
->eraseFromParent();
733 SizePHI
->addIncoming(EdgeData
.first
, PHI
.getIncomingBlock(i
));
734 OffsetPHI
->addIncoming(EdgeData
.second
, PHI
.getIncomingBlock(i
));
737 Value
*Size
= SizePHI
, *Offset
= OffsetPHI
, *Tmp
;
738 if ((Tmp
= SizePHI
->hasConstantValue())) {
740 SizePHI
->replaceAllUsesWith(Size
);
741 SizePHI
->eraseFromParent();
743 if ((Tmp
= OffsetPHI
->hasConstantValue())) {
745 OffsetPHI
->replaceAllUsesWith(Offset
);
746 OffsetPHI
->eraseFromParent();
748 return std::make_pair(Size
, Offset
);
751 SizeOffsetEvalType
ObjectSizeOffsetEvaluator::visitSelectInst(SelectInst
&I
) {
752 SizeOffsetEvalType TrueSide
= compute_(I
.getTrueValue());
753 SizeOffsetEvalType FalseSide
= compute_(I
.getFalseValue());
755 if (!bothKnown(TrueSide
) || !bothKnown(FalseSide
))
757 if (TrueSide
== FalseSide
)
760 Value
*Size
= Builder
.CreateSelect(I
.getCondition(), TrueSide
.first
,
762 Value
*Offset
= Builder
.CreateSelect(I
.getCondition(), TrueSide
.second
,
764 return std::make_pair(Size
, Offset
);
767 SizeOffsetEvalType
ObjectSizeOffsetEvaluator::visitInstruction(Instruction
&I
) {
768 DEBUG(dbgs() << "ObjectSizeOffsetEvaluator unknown instruction:" << I
<<'\n');