Mercurial > hg > CbC > CbC_llvm

comparison lib/Analysis/MemoryBuiltins.cpp @ 120:1172e4bd9c6f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
update 4.0.0
author mir3636
date Fri, 25 Nov 2016 19:14:25 +0900
parents 7d135dc70f03
children 803732b1fca8
comparison
equal deleted inserted replaced
101:34baf5011add 120:1172e4bd9c6f
40 AllocLike = MallocLike | CallocLike | StrDupLike, 40 AllocLike = MallocLike | CallocLike | StrDupLike,
41 AnyAlloc = AllocLike | ReallocLike 41 AnyAlloc = AllocLike | ReallocLike
42 }; 42 };
43 43
44 struct AllocFnsTy { 44 struct AllocFnsTy {
45 LibFunc::Func Func;
46 AllocType AllocTy; 45 AllocType AllocTy;
47 unsigned char NumParams; 46 unsigned NumParams;
48 // First and Second size parameters (or -1 if unused) 47 // First and Second size parameters (or -1 if unused)
49 signed char FstParam, SndParam; 48 int FstParam, SndParam;
50 }; 49 };
51 50
52 // FIXME: certain users need more information. E.g., SimplifyLibCalls needs to 51 // FIXME: certain users need more information. E.g., SimplifyLibCalls needs to
53 // know which functions are nounwind, noalias, nocapture parameters, etc. 52 // know which functions are nounwind, noalias, nocapture parameters, etc.
54 static const AllocFnsTy AllocationFnData[] = { 53 static const std::pair<LibFunc::Func, AllocFnsTy> AllocationFnData[] = {
55 {LibFunc::malloc, MallocLike, 1, 0, -1}, 54 {LibFunc::malloc, {MallocLike, 1, 0, -1}},
56 {LibFunc::valloc, MallocLike, 1, 0, -1}, 55 {LibFunc::valloc, {MallocLike, 1, 0, -1}},
57 {LibFunc::Znwj, OpNewLike, 1, 0, -1}, // new(unsigned int) 56 {LibFunc::Znwj, {OpNewLike, 1, 0, -1}}, // new(unsigned int)
58 {LibFunc::ZnwjRKSt9nothrow_t, MallocLike, 2, 0, -1}, // new(unsigned int, nothrow) 57 {LibFunc::ZnwjRKSt9nothrow_t, {MallocLike, 2, 0, -1}}, // new(unsigned int, nothrow)
59 {LibFunc::Znwm, OpNewLike, 1, 0, -1}, // new(unsigned long) 58 {LibFunc::Znwm, {OpNewLike, 1, 0, -1}}, // new(unsigned long)
60 {LibFunc::ZnwmRKSt9nothrow_t, MallocLike, 2, 0, -1}, // new(unsigned long, nothrow) 59 {LibFunc::ZnwmRKSt9nothrow_t, {MallocLike, 2, 0, -1}}, // new(unsigned long, nothrow)
61 {LibFunc::Znaj, OpNewLike, 1, 0, -1}, // new[](unsigned int) 60 {LibFunc::Znaj, {OpNewLike, 1, 0, -1}}, // new[](unsigned int)
62 {LibFunc::ZnajRKSt9nothrow_t, MallocLike, 2, 0, -1}, // new[](unsigned int, nothrow) 61 {LibFunc::ZnajRKSt9nothrow_t, {MallocLike, 2, 0, -1}}, // new[](unsigned int, nothrow)
63 {LibFunc::Znam, OpNewLike, 1, 0, -1}, // new[](unsigned long) 62 {LibFunc::Znam, {OpNewLike, 1, 0, -1}}, // new[](unsigned long)
64 {LibFunc::ZnamRKSt9nothrow_t, MallocLike, 2, 0, -1}, // new[](unsigned long, nothrow) 63 {LibFunc::ZnamRKSt9nothrow_t, {MallocLike, 2, 0, -1}}, // new[](unsigned long, nothrow)
65 {LibFunc::msvc_new_int, OpNewLike, 1, 0, -1}, // new(unsigned int) 64 {LibFunc::msvc_new_int, {OpNewLike, 1, 0, -1}}, // new(unsigned int)
66 {LibFunc::msvc_new_int_nothrow, MallocLike, 2, 0, -1}, // new(unsigned int, nothrow) 65 {LibFunc::msvc_new_int_nothrow, {MallocLike, 2, 0, -1}}, // new(unsigned int, nothrow)
67 {LibFunc::msvc_new_longlong, OpNewLike, 1, 0, -1}, // new(unsigned long long) 66 {LibFunc::msvc_new_longlong, {OpNewLike, 1, 0, -1}}, // new(unsigned long long)
68 {LibFunc::msvc_new_longlong_nothrow, MallocLike, 2, 0, -1}, // new(unsigned long long, nothrow) 67 {LibFunc::msvc_new_longlong_nothrow, {MallocLike, 2, 0, -1}}, // new(unsigned long long, nothrow)
69 {LibFunc::msvc_new_array_int, OpNewLike, 1, 0, -1}, // new[](unsigned int) 68 {LibFunc::msvc_new_array_int, {OpNewLike, 1, 0, -1}}, // new[](unsigned int)
70 {LibFunc::msvc_new_array_int_nothrow, MallocLike, 2, 0, -1}, // new[](unsigned int, nothrow) 69 {LibFunc::msvc_new_array_int_nothrow, {MallocLike, 2, 0, -1}}, // new[](unsigned int, nothrow)
71 {LibFunc::msvc_new_array_longlong, OpNewLike, 1, 0, -1}, // new[](unsigned long long) 70 {LibFunc::msvc_new_array_longlong, {OpNewLike, 1, 0, -1}}, // new[](unsigned long long)
72 {LibFunc::msvc_new_array_longlong_nothrow, MallocLike, 2, 0, -1}, // new[](unsigned long long, nothrow) 71 {LibFunc::msvc_new_array_longlong_nothrow, {MallocLike, 2, 0, -1}}, // new[](unsigned long long, nothrow)
73 {LibFunc::calloc, CallocLike, 2, 0, 1}, 72 {LibFunc::calloc, {CallocLike, 2, 0, 1}},
74 {LibFunc::realloc, ReallocLike, 2, 1, -1}, 73 {LibFunc::realloc, {ReallocLike, 2, 1, -1}},
75 {LibFunc::reallocf, ReallocLike, 2, 1, -1}, 74 {LibFunc::reallocf, {ReallocLike, 2, 1, -1}},
76 {LibFunc::strdup, StrDupLike, 1, -1, -1}, 75 {LibFunc::strdup, {StrDupLike, 1, -1, -1}},
77 {LibFunc::strndup, StrDupLike, 2, 1, -1} 76 {LibFunc::strndup, {StrDupLike, 2, 1, -1}}
78 // TODO: Handle "int posix_memalign(void **, size_t, size_t)" 77 // TODO: Handle "int posix_memalign(void **, size_t, size_t)"
79 }; 78 };
80 79
81 80
82 static Function *getCalledFunction(const Value *V, bool LookThroughBitCast) { 81 static Function *getCalledFunction(const Value *V, bool LookThroughBitCast) {
94 if (!Callee || !Callee->isDeclaration()) 93 if (!Callee || !Callee->isDeclaration())
95 return nullptr; 94 return nullptr;
96 return Callee; 95 return Callee;
97 } 96 }
98 97
99 /// \brief Returns the allocation data for the given value if it is a call to a 98 /// Returns the allocation data for the given value if it's either a call to a
100 /// known allocation function, and NULL otherwise. 99 /// known allocation function, or a call to a function with the allocsize
101 static const AllocFnsTy *getAllocationData(const Value *V, AllocType AllocTy, 100 /// attribute.
102 const TargetLibraryInfo *TLI, 101 static Optional<AllocFnsTy> getAllocationData(const Value *V, AllocType AllocTy,
103 bool LookThroughBitCast = false) { 102 const TargetLibraryInfo *TLI,
103 bool LookThroughBitCast = false) {
104 // Skip intrinsics 104 // Skip intrinsics
105 if (isa<IntrinsicInst>(V)) 105 if (isa<IntrinsicInst>(V))
106 return nullptr; 106 return None;
107 107
108 Function *Callee = getCalledFunction(V, LookThroughBitCast); 108 const Function *Callee = getCalledFunction(V, LookThroughBitCast);
109 if (!Callee) 109 if (!Callee)
110 return nullptr; 110 return None;
111
112 // If it has allocsize, we can skip checking if it's a known function.
113 //
114 // MallocLike is chosen here because allocsize makes no guarantees about the
115 // nullness of the result of the function, nor does it deal with strings, nor
116 // does it require that the memory returned is zeroed out.
117 const AllocType AllocSizeAllocTy = MallocLike;
118 if ((AllocTy & AllocSizeAllocTy) == AllocSizeAllocTy &&
119 Callee->hasFnAttribute(Attribute::AllocSize)) {
120 Attribute Attr = Callee->getFnAttribute(Attribute::AllocSize);
121 std::pair<unsigned, Optional<unsigned>> Args = Attr.getAllocSizeArgs();
122
123 AllocFnsTy Result;
124 Result.AllocTy = AllocSizeAllocTy;
125 Result.NumParams = Callee->getNumOperands();
126 Result.FstParam = Args.first;
127 Result.SndParam = Args.second.getValueOr(-1);
128 return Result;
129 }
111 130
112 // Make sure that the function is available. 131 // Make sure that the function is available.
113 StringRef FnName = Callee->getName(); 132 StringRef FnName = Callee->getName();
114 LibFunc::Func TLIFn; 133 LibFunc::Func TLIFn;
115 if (!TLI || !TLI->getLibFunc(FnName, TLIFn) || !TLI->has(TLIFn)) 134 if (!TLI || !TLI->getLibFunc(FnName, TLIFn) || !TLI->has(TLIFn))
116 return nullptr; 135 return None;
117 136
118 const AllocFnsTy *FnData = 137 const auto *Iter =
119 std::find_if(std::begin(AllocationFnData), std::end(AllocationFnData), 138 std::find_if(std::begin(AllocationFnData), std::end(AllocationFnData),
120 [TLIFn](const AllocFnsTy &Fn) { return Fn.Func == TLIFn; }); 139 [TLIFn](const std::pair<LibFunc::Func, AllocFnsTy> &P) {
121 140 return P.first == TLIFn;
122 if (FnData == std::end(AllocationFnData)) 141 });
123 return nullptr; 142
124 143 if (Iter == std::end(AllocationFnData))
144 return None;
145
146 const AllocFnsTy *FnData = &Iter->second;
125 if ((FnData->AllocTy & AllocTy) != FnData->AllocTy) 147 if ((FnData->AllocTy & AllocTy) != FnData->AllocTy)
126 return nullptr; 148 return None;
127 149
128 // Check function prototype. 150 // Check function prototype.
129 int FstParam = FnData->FstParam; 151 int FstParam = FnData->FstParam;
130 int SndParam = FnData->SndParam; 152 int SndParam = FnData->SndParam;
131 FunctionType *FTy = Callee->getFunctionType(); 153 FunctionType *FTy = Callee->getFunctionType();
136 (FTy->getParamType(FstParam)->isIntegerTy(32) || 158 (FTy->getParamType(FstParam)->isIntegerTy(32) ||
137 FTy->getParamType(FstParam)->isIntegerTy(64))) && 159 FTy->getParamType(FstParam)->isIntegerTy(64))) &&
138 (SndParam < 0 || 160 (SndParam < 0 ||
139 FTy->getParamType(SndParam)->isIntegerTy(32) || 161 FTy->getParamType(SndParam)->isIntegerTy(32) ||
140 FTy->getParamType(SndParam)->isIntegerTy(64))) 162 FTy->getParamType(SndParam)->isIntegerTy(64)))
141 return FnData; 163 return *FnData;
142 return nullptr; 164 return None;
143 } 165 }
144 166
145 static bool hasNoAliasAttr(const Value *V, bool LookThroughBitCast) { 167 static bool hasNoAliasAttr(const Value *V, bool LookThroughBitCast) {
146 ImmutableCallSite CS(LookThroughBitCast ? V->stripPointerCasts() : V); 168 ImmutableCallSite CS(LookThroughBitCast ? V->stripPointerCasts() : V);
147 return CS && CS.hasFnAttr(Attribute::NoAlias); 169 return CS && CS.paramHasAttr(AttributeSet::ReturnIndex, Attribute::NoAlias);
148 } 170 }
149 171
150 172
151 /// \brief Tests if a value is a call or invoke to a library function that 173 /// \brief Tests if a value is a call or invoke to a library function that
152 /// allocates or reallocates memory (either malloc, calloc, realloc, or strdup 174 /// allocates or reallocates memory (either malloc, calloc, realloc, or strdup
153 /// like). 175 /// like).
154 bool llvm::isAllocationFn(const Value *V, const TargetLibraryInfo *TLI, 176 bool llvm::isAllocationFn(const Value *V, const TargetLibraryInfo *TLI,
155 bool LookThroughBitCast) { 177 bool LookThroughBitCast) {
156 return getAllocationData(V, AnyAlloc, TLI, LookThroughBitCast); 178 return getAllocationData(V, AnyAlloc, TLI, LookThroughBitCast).hasValue();
157 } 179 }
158 180
159 /// \brief Tests if a value is a call or invoke to a function that returns a 181 /// \brief Tests if a value is a call or invoke to a function that returns a
160 /// NoAlias pointer (including malloc/calloc/realloc/strdup-like functions). 182 /// NoAlias pointer (including malloc/calloc/realloc/strdup-like functions).
161 bool llvm::isNoAliasFn(const Value *V, const TargetLibraryInfo *TLI, 183 bool llvm::isNoAliasFn(const Value *V, const TargetLibraryInfo *TLI,
168 190
169 /// \brief Tests if a value is a call or invoke to a library function that 191 /// \brief Tests if a value is a call or invoke to a library function that
170 /// allocates uninitialized memory (such as malloc). 192 /// allocates uninitialized memory (such as malloc).
171 bool llvm::isMallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, 193 bool llvm::isMallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
172 bool LookThroughBitCast) { 194 bool LookThroughBitCast) {
173 return getAllocationData(V, MallocLike, TLI, LookThroughBitCast); 195 return getAllocationData(V, MallocLike, TLI, LookThroughBitCast).hasValue();
174 } 196 }
175 197
176 /// \brief Tests if a value is a call or invoke to a library function that 198 /// \brief Tests if a value is a call or invoke to a library function that
177 /// allocates zero-filled memory (such as calloc). 199 /// allocates zero-filled memory (such as calloc).
178 bool llvm::isCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, 200 bool llvm::isCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
179 bool LookThroughBitCast) { 201 bool LookThroughBitCast) {
180 return getAllocationData(V, CallocLike, TLI, LookThroughBitCast); 202 return getAllocationData(V, CallocLike, TLI, LookThroughBitCast).hasValue();
181 } 203 }
182 204
183 /// \brief Tests if a value is a call or invoke to a library function that 205 /// \brief Tests if a value is a call or invoke to a library function that
184 /// allocates memory (either malloc, calloc, or strdup like). 206 /// allocates memory (either malloc, calloc, or strdup like).
185 bool llvm::isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI, 207 bool llvm::isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
186 bool LookThroughBitCast) { 208 bool LookThroughBitCast) {
187 return getAllocationData(V, AllocLike, TLI, LookThroughBitCast); 209 return getAllocationData(V, AllocLike, TLI, LookThroughBitCast).hasValue();
188 } 210 }
189 211
190 /// extractMallocCall - Returns the corresponding CallInst if the instruction 212 /// extractMallocCall - Returns the corresponding CallInst if the instruction
191 /// is a malloc call. Since CallInst::CreateMalloc() only creates calls, we 213 /// is a malloc call. Since CallInst::CreateMalloc() only creates calls, we
192 /// ignore InvokeInst here. 214 /// ignore InvokeInst here.
212 234
213 // If malloc call's arg can be determined to be a multiple of ElementSize, 235 // If malloc call's arg can be determined to be a multiple of ElementSize,
214 // return the multiple. Otherwise, return NULL. 236 // return the multiple. Otherwise, return NULL.
215 Value *MallocArg = CI->getArgOperand(0); 237 Value *MallocArg = CI->getArgOperand(0);
216 Value *Multiple = nullptr; 238 Value *Multiple = nullptr;
217 if (ComputeMultiple(MallocArg, ElementSize, Multiple, 239 if (ComputeMultiple(MallocArg, ElementSize, Multiple, LookThroughSExt))
218 LookThroughSExt))
219 return Multiple; 240 return Multiple;
220 241
221 return nullptr; 242 return nullptr;
222 } 243 }
223 244
343 364
344 365
345 //===----------------------------------------------------------------------===// 366 //===----------------------------------------------------------------------===//
346 // Utility functions to compute size of objects. 367 // Utility functions to compute size of objects.
347 // 368 //
348 369 static APInt getSizeWithOverflow(const SizeOffsetType &Data) {
370 if (Data.second.isNegative() || Data.first.ult(Data.second))
371 return APInt(Data.first.getBitWidth(), 0);
372 return Data.first - Data.second;
373 }
349 374
350 /// \brief Compute the size of the object pointed by Ptr. Returns true and the 375 /// \brief Compute the size of the object pointed by Ptr. Returns true and the
351 /// object size in Size if successful, and false otherwise. 376 /// object size in Size if successful, and false otherwise.
352 /// If RoundToAlign is true, then Size is rounded up to the aligment of allocas, 377 /// If RoundToAlign is true, then Size is rounded up to the aligment of allocas,
353 /// byval arguments, and global variables. 378 /// byval arguments, and global variables.
354 bool llvm::getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL, 379 bool llvm::getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL,
355 const TargetLibraryInfo *TLI, bool RoundToAlign) { 380 const TargetLibraryInfo *TLI, bool RoundToAlign,
356 ObjectSizeOffsetVisitor Visitor(DL, TLI, Ptr->getContext(), RoundToAlign); 381 llvm::ObjSizeMode Mode) {
382 ObjectSizeOffsetVisitor Visitor(DL, TLI, Ptr->getContext(),
383 RoundToAlign, Mode);
357 SizeOffsetType Data = Visitor.compute(const_cast<Value*>(Ptr)); 384 SizeOffsetType Data = Visitor.compute(const_cast<Value*>(Ptr));
358 if (!Visitor.bothKnown(Data)) 385 if (!Visitor.bothKnown(Data))
359 return false; 386 return false;
360 387
361 APInt ObjSize = Data.first, Offset = Data.second; 388 Size = getSizeWithOverflow(Data).getZExtValue();
362 // check for overflow
363 if (Offset.slt(0) || ObjSize.ult(Offset))
364 Size = 0;
365 else
366 Size = (ObjSize - Offset).getZExtValue();
367 return true; 389 return true;
368 } 390 }
369
370 391
371 STATISTIC(ObjectVisitorArgument, 392 STATISTIC(ObjectVisitorArgument,
372 "Number of arguments with unsolved size and offset"); 393 "Number of arguments with unsolved size and offset");
373 STATISTIC(ObjectVisitorLoad, 394 STATISTIC(ObjectVisitorLoad,
374 "Number of load instructions with unsolved size and offset"); 395 "Number of load instructions with unsolved size and offset");
381 } 402 }
382 403
383 ObjectSizeOffsetVisitor::ObjectSizeOffsetVisitor(const DataLayout &DL, 404 ObjectSizeOffsetVisitor::ObjectSizeOffsetVisitor(const DataLayout &DL,
384 const TargetLibraryInfo *TLI, 405 const TargetLibraryInfo *TLI,
385 LLVMContext &Context, 406 LLVMContext &Context,
386 bool RoundToAlign) 407 bool RoundToAlign,
387 : DL(DL), TLI(TLI), RoundToAlign(RoundToAlign) { 408 ObjSizeMode Mode)
409 : DL(DL), TLI(TLI), RoundToAlign(RoundToAlign), Mode(Mode) {
388 // Pointer size must be rechecked for each object visited since it could have 410 // Pointer size must be rechecked for each object visited since it could have
389 // a different address space. 411 // a different address space.
390 } 412 }
391 413
392 SizeOffsetType ObjectSizeOffsetVisitor::compute(Value *V) { 414 SizeOffsetType ObjectSizeOffsetVisitor::compute(Value *V) {
441 } 463 }
442 return unknown(); 464 return unknown();
443 } 465 }
444 466
445 SizeOffsetType ObjectSizeOffsetVisitor::visitArgument(Argument &A) { 467 SizeOffsetType ObjectSizeOffsetVisitor::visitArgument(Argument &A) {
446 // no interprocedural analysis is done at the moment 468 // No interprocedural analysis is done at the moment.
447 if (!A.hasByValOrInAllocaAttr()) { 469 if (!A.hasByValOrInAllocaAttr()) {
448 ++ObjectVisitorArgument; 470 ++ObjectVisitorArgument;
449 return unknown(); 471 return unknown();
450 } 472 }
451 PointerType *PT = cast<PointerType>(A.getType()); 473 PointerType *PT = cast<PointerType>(A.getType());
452 APInt Size(IntTyBits, DL.getTypeAllocSize(PT->getElementType())); 474 APInt Size(IntTyBits, DL.getTypeAllocSize(PT->getElementType()));
453 return std::make_pair(align(Size, A.getParamAlignment()), Zero); 475 return std::make_pair(align(Size, A.getParamAlignment()), Zero);
454 } 476 }
455 477
456 SizeOffsetType ObjectSizeOffsetVisitor::visitCallSite(CallSite CS) { 478 SizeOffsetType ObjectSizeOffsetVisitor::visitCallSite(CallSite CS) {
457 const AllocFnsTy *FnData = getAllocationData(CS.getInstruction(), AnyAlloc, 479 Optional<AllocFnsTy> FnData =
458 TLI); 480 getAllocationData(CS.getInstruction(), AnyAlloc, TLI);
459 if (!FnData) 481 if (!FnData)
460 return unknown(); 482 return unknown();
461 483
462 // handle strdup-like functions separately 484 // Handle strdup-like functions separately.
463 if (FnData->AllocTy == StrDupLike) { 485 if (FnData->AllocTy == StrDupLike) {
464 APInt Size(IntTyBits, GetStringLength(CS.getArgument(0))); 486 APInt Size(IntTyBits, GetStringLength(CS.getArgument(0)));
465 if (!Size) 487 if (!Size)
466 return unknown(); 488 return unknown();
467 489
468 // strndup limits strlen 490 // Strndup limits strlen.
469 if (FnData->FstParam > 0) { 491 if (FnData->FstParam > 0) {
470 ConstantInt *Arg= dyn_cast<ConstantInt>(CS.getArgument(FnData->FstParam)); 492 ConstantInt *Arg =
493 dyn_cast<ConstantInt>(CS.getArgument(FnData->FstParam));
471 if (!Arg) 494 if (!Arg)
472 return unknown(); 495 return unknown();
473 496
474 APInt MaxSize = Arg->getValue().zextOrSelf(IntTyBits); 497 APInt MaxSize = Arg->getValue().zextOrSelf(IntTyBits);
475 if (Size.ugt(MaxSize)) 498 if (Size.ugt(MaxSize))
480 503
481 ConstantInt *Arg = dyn_cast<ConstantInt>(CS.getArgument(FnData->FstParam)); 504 ConstantInt *Arg = dyn_cast<ConstantInt>(CS.getArgument(FnData->FstParam));
482 if (!Arg) 505 if (!Arg)
483 return unknown(); 506 return unknown();
484 507
485 APInt Size = Arg->getValue().zextOrSelf(IntTyBits); 508 // When we're compiling N-bit code, and the user uses parameters that are
486 // size determined by just 1 parameter 509 // greater than N bits (e.g. uint64_t on a 32-bit build), we can run into
510 // trouble with APInt size issues. This function handles resizing + overflow
511 // checks for us.
512 auto CheckedZextOrTrunc = [&](APInt &I) {
513 // More bits than we can handle. Checking the bit width isn't necessary, but
514 // it's faster than checking active bits, and should give `false` in the
515 // vast majority of cases.
516 if (I.getBitWidth() > IntTyBits && I.getActiveBits() > IntTyBits)
517 return false;
518 if (I.getBitWidth() != IntTyBits)
519 I = I.zextOrTrunc(IntTyBits);
520 return true;
521 };
522
523 APInt Size = Arg->getValue();
524 if (!CheckedZextOrTrunc(Size))
525 return unknown();
526
527 // Size is determined by just 1 parameter.
487 if (FnData->SndParam < 0) 528 if (FnData->SndParam < 0)
488 return std::make_pair(Size, Zero); 529 return std::make_pair(Size, Zero);
489 530
490 Arg = dyn_cast<ConstantInt>(CS.getArgument(FnData->SndParam)); 531 Arg = dyn_cast<ConstantInt>(CS.getArgument(FnData->SndParam));
491 if (!Arg) 532 if (!Arg)
492 return unknown(); 533 return unknown();
493 534
494 Size *= Arg->getValue().zextOrSelf(IntTyBits); 535 APInt NumElems = Arg->getValue();
495 return std::make_pair(Size, Zero); 536 if (!CheckedZextOrTrunc(NumElems))
537 return unknown();
538
539 bool Overflow;
540 Size = Size.umul_ov(NumElems, Overflow);
541 return Overflow ? unknown() : std::make_pair(Size, Zero);
496 542
497 // TODO: handle more standard functions (+ wchar cousins): 543 // TODO: handle more standard functions (+ wchar cousins):
498 // - strdup / strndup 544 // - strdup / strndup
499 // - strcpy / strncpy 545 // - strcpy / strncpy
500 // - strcat / strncat 546 // - strcat / strncat
527 573
528 return std::make_pair(PtrData.first, PtrData.second + Offset); 574 return std::make_pair(PtrData.first, PtrData.second + Offset);
529 } 575 }
530 576
531 SizeOffsetType ObjectSizeOffsetVisitor::visitGlobalAlias(GlobalAlias &GA) { 577 SizeOffsetType ObjectSizeOffsetVisitor::visitGlobalAlias(GlobalAlias &GA) {
532 if (GA.mayBeOverridden()) 578 if (GA.isInterposable())
533 return unknown(); 579 return unknown();
534 return compute(GA.getAliasee()); 580 return compute(GA.getAliasee());
535 } 581 }
536 582
537 SizeOffsetType ObjectSizeOffsetVisitor::visitGlobalVariable(GlobalVariable &GV){ 583 SizeOffsetType ObjectSizeOffsetVisitor::visitGlobalVariable(GlobalVariable &GV){
558 } 604 }
559 605
560 SizeOffsetType ObjectSizeOffsetVisitor::visitSelectInst(SelectInst &I) { 606 SizeOffsetType ObjectSizeOffsetVisitor::visitSelectInst(SelectInst &I) {
561 SizeOffsetType TrueSide = compute(I.getTrueValue()); 607 SizeOffsetType TrueSide = compute(I.getTrueValue());
562 SizeOffsetType FalseSide = compute(I.getFalseValue()); 608 SizeOffsetType FalseSide = compute(I.getFalseValue());
563 if (bothKnown(TrueSide) && bothKnown(FalseSide) && TrueSide == FalseSide) 609 if (bothKnown(TrueSide) && bothKnown(FalseSide)) {
564 return TrueSide; 610 if (TrueSide == FalseSide) {
611 return TrueSide;
612 }
613
614 APInt TrueResult = getSizeWithOverflow(TrueSide);
615 APInt FalseResult = getSizeWithOverflow(FalseSide);
616
617 if (TrueResult == FalseResult) {
618 return TrueSide;
619 }
620 if (Mode == ObjSizeMode::Min) {
621 if (TrueResult.slt(FalseResult))
622 return TrueSide;
623 return FalseSide;
624 }
625 if (Mode == ObjSizeMode::Max) {
626 if (TrueResult.sgt(FalseResult))
627 return TrueSide;
628 return FalseSide;
629 }
630 }
565 return unknown(); 631 return unknown();
566 } 632 }
567 633
568 SizeOffsetType ObjectSizeOffsetVisitor::visitUndefValue(UndefValue&) { 634 SizeOffsetType ObjectSizeOffsetVisitor::visitUndefValue(UndefValue&) {
569 return std::make_pair(Zero, Zero); 635 return std::make_pair(Zero, Zero);
589 Zero = ConstantInt::get(IntTy, 0); 655 Zero = ConstantInt::get(IntTy, 0);
590 656
591 SizeOffsetEvalType Result = compute_(V); 657 SizeOffsetEvalType Result = compute_(V);
592 658
593 if (!bothKnown(Result)) { 659 if (!bothKnown(Result)) {
594 // erase everything that was computed in this iteration from the cache, so 660 // Erase everything that was computed in this iteration from the cache, so
595 // that no dangling references are left behind. We could be a bit smarter if 661 // that no dangling references are left behind. We could be a bit smarter if
596 // we kept a dependency graph. It's probably not worth the complexity. 662 // we kept a dependency graph. It's probably not worth the complexity.
597 for (PtrSetTy::iterator I=SeenVals.begin(), E=SeenVals.end(); I != E; ++I) { 663 for (const Value *SeenVal : SeenVals) {
598 CacheMapTy::iterator CacheIt = CacheMap.find(*I); 664 CacheMapTy::iterator CacheIt = CacheMap.find(SeenVal);
599 // non-computable results can be safely cached 665 // non-computable results can be safely cached
600 if (CacheIt != CacheMap.end() && anyKnown(CacheIt->second)) 666 if (CacheIt != CacheMap.end() && anyKnown(CacheIt->second))
601 CacheMap.erase(CacheIt); 667 CacheMap.erase(CacheIt);
602 } 668 }
603 } 669 }
613 return std::make_pair(ConstantInt::get(Context, Const.first), 679 return std::make_pair(ConstantInt::get(Context, Const.first),
614 ConstantInt::get(Context, Const.second)); 680 ConstantInt::get(Context, Const.second));
615 681
616 V = V->stripPointerCasts(); 682 V = V->stripPointerCasts();
617 683
618 // check cache 684 // Check cache.
619 CacheMapTy::iterator CacheIt = CacheMap.find(V); 685 CacheMapTy::iterator CacheIt = CacheMap.find(V);
620 if (CacheIt != CacheMap.end()) 686 if (CacheIt != CacheMap.end())
621 return CacheIt->second; 687 return CacheIt->second;
622 688
623 // always generate code immediately before the instruction being 689 // Always generate code immediately before the instruction being
624 // processed, so that the generated code dominates the same BBs 690 // processed, so that the generated code dominates the same BBs.
625 BuilderTy::InsertPointGuard Guard(Builder); 691 BuilderTy::InsertPointGuard Guard(Builder);
626 if (Instruction *I = dyn_cast<Instruction>(V)) 692 if (Instruction *I = dyn_cast<Instruction>(V))
627 Builder.SetInsertPoint(I); 693 Builder.SetInsertPoint(I);
628 694
629 // now compute the size and offset 695 // Now compute the size and offset.
630 SizeOffsetEvalType Result; 696 SizeOffsetEvalType Result;
631 697
632 // Record the pointers that were handled in this run, so that they can be 698 // Record the pointers that were handled in this run, so that they can be
633 // cleaned later if something fails. We also use this set to break cycles that 699 // cleaned later if something fails. We also use this set to break cycles that
634 // can occur in dead code. 700 // can occur in dead code.
641 } else if (isa<Argument>(V) || 707 } else if (isa<Argument>(V) ||
642 (isa<ConstantExpr>(V) && 708 (isa<ConstantExpr>(V) &&
643 cast<ConstantExpr>(V)->getOpcode() == Instruction::IntToPtr) || 709 cast<ConstantExpr>(V)->getOpcode() == Instruction::IntToPtr) ||
644 isa<GlobalAlias>(V) || 710 isa<GlobalAlias>(V) ||
645 isa<GlobalVariable>(V)) { 711 isa<GlobalVariable>(V)) {
646 // ignore values where we cannot do more than what ObjectSizeVisitor can 712 // Ignore values where we cannot do more than ObjectSizeVisitor.
647 Result = unknown(); 713 Result = unknown();
648 } else { 714 } else {
649 DEBUG(dbgs() << "ObjectSizeOffsetEvaluator::compute() unhandled value: " 715 DEBUG(dbgs() << "ObjectSizeOffsetEvaluator::compute() unhandled value: "
650 << *V << '\n'); 716 << *V << '\n');
651 Result = unknown(); 717 Result = unknown();
668 Size = Builder.CreateMul(Size, ArraySize); 734 Size = Builder.CreateMul(Size, ArraySize);
669 return std::make_pair(Size, Zero); 735 return std::make_pair(Size, Zero);
670 } 736 }
671 737
672 SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitCallSite(CallSite CS) { 738 SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitCallSite(CallSite CS) {
673 const AllocFnsTy *FnData = getAllocationData(CS.getInstruction(), AnyAlloc, 739 Optional<AllocFnsTy> FnData =
674 TLI); 740 getAllocationData(CS.getInstruction(), AnyAlloc, TLI);
675 if (!FnData) 741 if (!FnData)
676 return unknown(); 742 return unknown();
677 743
678 // handle strdup-like functions separately 744 // Handle strdup-like functions separately.
679 if (FnData->AllocTy == StrDupLike) { 745 if (FnData->AllocTy == StrDupLike) {
680 // TODO 746 // TODO
681 return unknown(); 747 return unknown();
682 } 748 }
683 749
729 SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitLoadInst(LoadInst&) { 795 SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitLoadInst(LoadInst&) {
730 return unknown(); 796 return unknown();
731 } 797 }
732 798
733 SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitPHINode(PHINode &PHI) { 799 SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitPHINode(PHINode &PHI) {
734 // create 2 PHIs: one for size and another for offset 800 // Create 2 PHIs: one for size and another for offset.
735 PHINode *SizePHI = Builder.CreatePHI(IntTy, PHI.getNumIncomingValues()); 801 PHINode *SizePHI = Builder.CreatePHI(IntTy, PHI.getNumIncomingValues());
736 PHINode *OffsetPHI = Builder.CreatePHI(IntTy, PHI.getNumIncomingValues()); 802 PHINode *OffsetPHI = Builder.CreatePHI(IntTy, PHI.getNumIncomingValues());
737 803
738 // insert right away in the cache to handle recursive PHIs 804 // Insert right away in the cache to handle recursive PHIs.
739 CacheMap[&PHI] = std::make_pair(SizePHI, OffsetPHI); 805 CacheMap[&PHI] = std::make_pair(SizePHI, OffsetPHI);
740 806
741 // compute offset/size for each PHI incoming pointer 807 // Compute offset/size for each PHI incoming pointer.
742 for (unsigned i = 0, e = PHI.getNumIncomingValues(); i != e; ++i) { 808 for (unsigned i = 0, e = PHI.getNumIncomingValues(); i != e; ++i) {
743 Builder.SetInsertPoint(&*PHI.getIncomingBlock(i)->getFirstInsertionPt()); 809 Builder.SetInsertPoint(&*PHI.getIncomingBlock(i)->getFirstInsertionPt());
744 SizeOffsetEvalType EdgeData = compute_(PHI.getIncomingValue(i)); 810 SizeOffsetEvalType EdgeData = compute_(PHI.getIncomingValue(i));
745 811
746 if (!bothKnown(EdgeData)) { 812 if (!bothKnown(EdgeData)) {