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