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" 31 using namespace llvm; 32 33 enum 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 42 struct 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. 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} 69 }; 70 71 72 static 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. 88 static 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 137 static 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). 146 bool 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). 153 bool 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). 163 bool 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). 170 bool 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). 177 bool 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). 184 bool 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. 192 const CallInst *llvm::extractMallocCall(const Value *I, 193 const TargetLibraryInfo *TLI) { 194 return isMallocLikeFn(I, TLI) ? dyn_cast<CallInst>(I) : 0; 195 } 196 197 static 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. 226 const 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. 245 PointerType *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. 277 Type *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. 288 Value *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. 298 const 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() 305 const 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. 348 bool 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 /// \brief Compute the size of the underlying object pointed by Ptr. Returns 368 /// true and the object size in Size if successful, and false otherwise. 369 /// If RoundToAlign is true, then Size is rounded up to the aligment of allocas, 370 /// byval arguments, and global variables. 371 bool llvm::getUnderlyingObjectSize(const Value *Ptr, uint64_t &Size, 372 const DataLayout *TD, 373 const TargetLibraryInfo *TLI, 374 bool RoundToAlign) { 375 if (!TD) 376 return false; 377 378 ObjectSizeOffsetVisitor Visitor(TD, TLI, Ptr->getContext(), RoundToAlign); 379 SizeOffsetType Data = Visitor.compute(const_cast<Value*>(Ptr)); 380 if (!Visitor.knownSize(Data)) 381 return false; 382 383 Size = Data.first.getZExtValue(); 384 return true; 385 } 386 387 388 STATISTIC(ObjectVisitorArgument, 389 "Number of arguments with unsolved size and offset"); 390 STATISTIC(ObjectVisitorLoad, 391 "Number of load instructions with unsolved size and offset"); 392 393 394 APInt ObjectSizeOffsetVisitor::align(APInt Size, uint64_t Align) { 395 if (RoundToAlign && Align) 396 return APInt(IntTyBits, RoundUpToAlignment(Size.getZExtValue(), Align)); 397 return Size; 398 } 399 400 ObjectSizeOffsetVisitor::ObjectSizeOffsetVisitor(const DataLayout *TD, 401 const TargetLibraryInfo *TLI, 402 LLVMContext &Context, 403 bool RoundToAlign) 404 : TD(TD), TLI(TLI), RoundToAlign(RoundToAlign) { 405 IntegerType *IntTy = TD->getIntPtrType(Context); 406 IntTyBits = IntTy->getBitWidth(); 407 Zero = APInt::getNullValue(IntTyBits); 408 } 409 410 SizeOffsetType ObjectSizeOffsetVisitor::compute(Value *V) { 411 V = V->stripPointerCasts(); 412 413 if (isa<Instruction>(V) || isa<GEPOperator>(V)) { 414 // Return cached value or insert unknown in cache if size of V was not 415 // computed yet in order to avoid recursions in PHis. 416 std::pair<CacheMapTy::iterator, bool> CacheVal = 417 CacheMap.insert(std::make_pair(V, unknown())); 418 if (!CacheVal.second) 419 return CacheVal.first->second; 420 421 SizeOffsetType Result; 422 if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) 423 Result = visitGEPOperator(*GEP); 424 else 425 Result = visit(cast<Instruction>(*V)); 426 return CacheMap[V] = Result; 427 } 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); 433 if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) 434 return visitGlobalAlias(*GA); 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 442 } 443 444 DEBUG(dbgs() << "ObjectSizeOffsetVisitor::compute() unhandled value: " << *V 445 << '\n'); 446 return unknown(); 447 } 448 449 SizeOffsetType ObjectSizeOffsetVisitor::visitAllocaInst(AllocaInst &I) { 450 if (!I.getAllocatedType()->isSized()) 451 return unknown(); 452 453 APInt Size(IntTyBits, TD->getTypeAllocSize(I.getAllocatedType())); 454 if (!I.isArrayAllocation()) 455 return std::make_pair(align(Size, I.getAlignment()), Zero); 456 457 Value *ArraySize = I.getArraySize(); 458 if (const ConstantInt *C = dyn_cast<ConstantInt>(ArraySize)) { 459 Size *= C->getValue().zextOrSelf(IntTyBits); 460 return std::make_pair(align(Size, I.getAlignment()), Zero); 461 } 462 return unknown(); 463 } 464 465 SizeOffsetType ObjectSizeOffsetVisitor::visitArgument(Argument &A) { 466 // no interprocedural analysis is done at the moment 467 if (!A.hasByValAttr()) { 468 ++ObjectVisitorArgument; 469 return unknown(); 470 } 471 PointerType *PT = cast<PointerType>(A.getType()); 472 APInt Size(IntTyBits, TD->getTypeAllocSize(PT->getElementType())); 473 return std::make_pair(align(Size, A.getParamAlignment()), Zero); 474 } 475 476 SizeOffsetType ObjectSizeOffsetVisitor::visitCallSite(CallSite CS) { 477 const AllocFnsTy *FnData = getAllocationData(CS.getInstruction(), AnyAlloc, 478 TLI); 479 if (!FnData) 480 return unknown(); 481 482 // handle strdup-like functions separately 483 if (FnData->AllocTy == StrDupLike) { 484 APInt Size(IntTyBits, GetStringLength(CS.getArgument(0))); 485 if (!Size) 486 return unknown(); 487 488 // strndup limits strlen 489 if (FnData->FstParam > 0) { 490 ConstantInt *Arg= dyn_cast<ConstantInt>(CS.getArgument(FnData->FstParam)); 491 if (!Arg) 492 return unknown(); 493 494 APInt MaxSize = Arg->getValue().zextOrSelf(IntTyBits); 495 if (Size.ugt(MaxSize)) 496 Size = MaxSize + 1; 497 } 498 return std::make_pair(Size, Zero); 499 } 500 501 ConstantInt *Arg = dyn_cast<ConstantInt>(CS.getArgument(FnData->FstParam)); 502 if (!Arg) 503 return unknown(); 504 505 APInt Size = Arg->getValue().zextOrSelf(IntTyBits); 506 // size determined by just 1 parameter 507 if (FnData->SndParam < 0) 508 return std::make_pair(Size, Zero); 509 510 Arg = dyn_cast<ConstantInt>(CS.getArgument(FnData->SndParam)); 511 if (!Arg) 512 return unknown(); 513 514 Size *= Arg->getValue().zextOrSelf(IntTyBits); 515 return std::make_pair(Size, Zero); 516 517 // TODO: handle more standard functions (+ wchar cousins): 518 // - strdup / strndup 519 // - strcpy / strncpy 520 // - strcat / strncat 521 // - memcpy / memmove 522 // - strcat / strncat 523 // - memset 524 } 525 526 SizeOffsetType 527 ObjectSizeOffsetVisitor::visitConstantPointerNull(ConstantPointerNull&) { 528 return std::make_pair(Zero, Zero); 529 } 530 531 SizeOffsetType 532 ObjectSizeOffsetVisitor::visitExtractElementInst(ExtractElementInst&) { 533 return unknown(); 534 } 535 536 SizeOffsetType 537 ObjectSizeOffsetVisitor::visitExtractValueInst(ExtractValueInst&) { 538 // Easy cases were already folded by previous passes. 539 return unknown(); 540 } 541 542 SizeOffsetType ObjectSizeOffsetVisitor::visitGEPOperator(GEPOperator &GEP) { 543 SizeOffsetType PtrData = compute(GEP.getPointerOperand()); 544 APInt Offset(IntTyBits, 0); 545 if (!bothKnown(PtrData) || !GEP.accumulateConstantOffset(*TD, Offset)) 546 return unknown(); 547 548 return std::make_pair(PtrData.first, PtrData.second + Offset); 549 } 550 551 SizeOffsetType ObjectSizeOffsetVisitor::visitGlobalAlias(GlobalAlias &GA) { 552 if (GA.mayBeOverridden()) 553 return unknown(); 554 return compute(GA.getAliasee()); 555 } 556 557 SizeOffsetType ObjectSizeOffsetVisitor::visitGlobalVariable(GlobalVariable &GV){ 558 if (!GV.hasDefinitiveInitializer()) 559 return unknown(); 560 561 APInt Size(IntTyBits, TD->getTypeAllocSize(GV.getType()->getElementType())); 562 return std::make_pair(align(Size, GV.getAlignment()), Zero); 563 } 564 565 SizeOffsetType ObjectSizeOffsetVisitor::visitIntToPtrInst(IntToPtrInst&) { 566 // clueless 567 return unknown(); 568 } 569 570 SizeOffsetType ObjectSizeOffsetVisitor::visitLoadInst(LoadInst&) { 571 ++ObjectVisitorLoad; 572 return unknown(); 573 } 574 575 SizeOffsetType ObjectSizeOffsetVisitor::visitPHINode(PHINode &PHI) { 576 if (PHI.getNumIncomingValues() == 0) 577 return unknown(); 578 579 SizeOffsetType Ret = compute(PHI.getIncomingValue(0)); 580 if (!bothKnown(Ret)) 581 return unknown(); 582 583 // Verify that all PHI incoming pointers have the same size and offset. 584 for (unsigned i = 1, e = PHI.getNumIncomingValues(); i != e; ++i) { 585 SizeOffsetType EdgeData = compute(PHI.getIncomingValue(i)); 586 if (!bothKnown(EdgeData) || EdgeData != Ret) 587 return unknown(); 588 } 589 return Ret; 590 } 591 592 SizeOffsetType ObjectSizeOffsetVisitor::visitSelectInst(SelectInst &I) { 593 SizeOffsetType TrueSide = compute(I.getTrueValue()); 594 SizeOffsetType FalseSide = compute(I.getFalseValue()); 595 if (bothKnown(TrueSide) && bothKnown(FalseSide) && TrueSide == FalseSide) 596 return TrueSide; 597 return unknown(); 598 } 599 600 SizeOffsetType ObjectSizeOffsetVisitor::visitUndefValue(UndefValue&) { 601 return std::make_pair(Zero, Zero); 602 } 603 604 SizeOffsetType ObjectSizeOffsetVisitor::visitInstruction(Instruction &I) { 605 DEBUG(dbgs() << "ObjectSizeOffsetVisitor unknown instruction:" << I << '\n'); 606 return unknown(); 607 } 608 609 610 ObjectSizeOffsetEvaluator::ObjectSizeOffsetEvaluator(const DataLayout *TD, 611 const TargetLibraryInfo *TLI, 612 LLVMContext &Context) 613 : TD(TD), TLI(TLI), Context(Context), Builder(Context, TargetFolder(TD)) { 614 IntTy = TD->getIntPtrType(Context); 615 Zero = ConstantInt::get(IntTy, 0); 616 } 617 618 SizeOffsetEvalType ObjectSizeOffsetEvaluator::compute(Value *V) { 619 SizeOffsetEvalType Result = compute_(V); 620 621 if (!bothKnown(Result)) { 622 // erase everything that was computed in this iteration from the cache, so 623 // that no dangling references are left behind. We could be a bit smarter if 624 // we kept a dependency graph. It's probably not worth the complexity. 625 for (PtrSetTy::iterator I=SeenVals.begin(), E=SeenVals.end(); I != E; ++I) { 626 CacheMapTy::iterator CacheIt = CacheMap.find(*I); 627 // non-computable results can be safely cached 628 if (CacheIt != CacheMap.end() && anyKnown(CacheIt->second)) 629 CacheMap.erase(CacheIt); 630 } 631 } 632 633 SeenVals.clear(); 634 return Result; 635 } 636 637 SizeOffsetEvalType ObjectSizeOffsetEvaluator::compute_(Value *V) { 638 ObjectSizeOffsetVisitor Visitor(TD, TLI, Context); 639 SizeOffsetType Const = Visitor.compute(V); 640 if (Visitor.bothKnown(Const)) 641 return std::make_pair(ConstantInt::get(Context, Const.first), 642 ConstantInt::get(Context, Const.second)); 643 644 V = V->stripPointerCasts(); 645 646 // check cache 647 CacheMapTy::iterator CacheIt = CacheMap.find(V); 648 if (CacheIt != CacheMap.end()) 649 return CacheIt->second; 650 651 // always generate code immediately before the instruction being 652 // processed, so that the generated code dominates the same BBs 653 Instruction *PrevInsertPoint = Builder.GetInsertPoint(); 654 if (Instruction *I = dyn_cast<Instruction>(V)) 655 Builder.SetInsertPoint(I); 656 657 // record the pointers that were handled in this run, so that they can be 658 // cleaned later if something fails 659 SeenVals.insert(V); 660 661 // now compute the size and offset 662 SizeOffsetEvalType Result; 663 if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { 664 Result = visitGEPOperator(*GEP); 665 } else if (Instruction *I = dyn_cast<Instruction>(V)) { 666 Result = visit(*I); 667 } else if (isa<Argument>(V) || 668 (isa<ConstantExpr>(V) && 669 cast<ConstantExpr>(V)->getOpcode() == Instruction::IntToPtr) || 670 isa<GlobalAlias>(V) || 671 isa<GlobalVariable>(V)) { 672 // ignore values where we cannot do more than what ObjectSizeVisitor can 673 Result = unknown(); 674 } else { 675 DEBUG(dbgs() << "ObjectSizeOffsetEvaluator::compute() unhandled value: " 676 << *V << '\n'); 677 Result = unknown(); 678 } 679 680 if (PrevInsertPoint) 681 Builder.SetInsertPoint(PrevInsertPoint); 682 683 // Don't reuse CacheIt since it may be invalid at this point. 684 CacheMap[V] = Result; 685 return Result; 686 } 687 688 SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitAllocaInst(AllocaInst &I) { 689 if (!I.getAllocatedType()->isSized()) 690 return unknown(); 691 692 // must be a VLA 693 assert(I.isArrayAllocation()); 694 Value *ArraySize = I.getArraySize(); 695 Value *Size = ConstantInt::get(ArraySize->getType(), 696 TD->getTypeAllocSize(I.getAllocatedType())); 697 Size = Builder.CreateMul(Size, ArraySize); 698 return std::make_pair(Size, Zero); 699 } 700 701 SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitCallSite(CallSite CS) { 702 const AllocFnsTy *FnData = getAllocationData(CS.getInstruction(), AnyAlloc, 703 TLI); 704 if (!FnData) 705 return unknown(); 706 707 // handle strdup-like functions separately 708 if (FnData->AllocTy == StrDupLike) { 709 // TODO 710 return unknown(); 711 } 712 713 Value *FirstArg = CS.getArgument(FnData->FstParam); 714 FirstArg = Builder.CreateZExt(FirstArg, IntTy); 715 if (FnData->SndParam < 0) 716 return std::make_pair(FirstArg, Zero); 717 718 Value *SecondArg = CS.getArgument(FnData->SndParam); 719 SecondArg = Builder.CreateZExt(SecondArg, IntTy); 720 Value *Size = Builder.CreateMul(FirstArg, SecondArg); 721 return std::make_pair(Size, Zero); 722 723 // TODO: handle more standard functions (+ wchar cousins): 724 // - strdup / strndup 725 // - strcpy / strncpy 726 // - strcat / strncat 727 // - memcpy / memmove 728 // - strcat / strncat 729 // - memset 730 } 731 732 SizeOffsetEvalType 733 ObjectSizeOffsetEvaluator::visitExtractElementInst(ExtractElementInst&) { 734 return unknown(); 735 } 736 737 SizeOffsetEvalType 738 ObjectSizeOffsetEvaluator::visitExtractValueInst(ExtractValueInst&) { 739 return unknown(); 740 } 741 742 SizeOffsetEvalType 743 ObjectSizeOffsetEvaluator::visitGEPOperator(GEPOperator &GEP) { 744 SizeOffsetEvalType PtrData = compute_(GEP.getPointerOperand()); 745 if (!bothKnown(PtrData)) 746 return unknown(); 747 748 Value *Offset = EmitGEPOffset(&Builder, *TD, &GEP, /*NoAssumptions=*/true); 749 Offset = Builder.CreateAdd(PtrData.second, Offset); 750 return std::make_pair(PtrData.first, Offset); 751 } 752 753 SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitIntToPtrInst(IntToPtrInst&) { 754 // clueless 755 return unknown(); 756 } 757 758 SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitLoadInst(LoadInst&) { 759 return unknown(); 760 } 761 762 SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitPHINode(PHINode &PHI) { 763 // create 2 PHIs: one for size and another for offset 764 PHINode *SizePHI = Builder.CreatePHI(IntTy, PHI.getNumIncomingValues()); 765 PHINode *OffsetPHI = Builder.CreatePHI(IntTy, PHI.getNumIncomingValues()); 766 767 // insert right away in the cache to handle recursive PHIs 768 CacheMap[&PHI] = std::make_pair(SizePHI, OffsetPHI); 769 770 // compute offset/size for each PHI incoming pointer 771 for (unsigned i = 0, e = PHI.getNumIncomingValues(); i != e; ++i) { 772 Builder.SetInsertPoint(PHI.getIncomingBlock(i)->getFirstInsertionPt()); 773 SizeOffsetEvalType EdgeData = compute_(PHI.getIncomingValue(i)); 774 775 if (!bothKnown(EdgeData)) { 776 OffsetPHI->replaceAllUsesWith(UndefValue::get(IntTy)); 777 OffsetPHI->eraseFromParent(); 778 SizePHI->replaceAllUsesWith(UndefValue::get(IntTy)); 779 SizePHI->eraseFromParent(); 780 return unknown(); 781 } 782 SizePHI->addIncoming(EdgeData.first, PHI.getIncomingBlock(i)); 783 OffsetPHI->addIncoming(EdgeData.second, PHI.getIncomingBlock(i)); 784 } 785 786 Value *Size = SizePHI, *Offset = OffsetPHI, *Tmp; 787 if ((Tmp = SizePHI->hasConstantValue())) { 788 Size = Tmp; 789 SizePHI->replaceAllUsesWith(Size); 790 SizePHI->eraseFromParent(); 791 } 792 if ((Tmp = OffsetPHI->hasConstantValue())) { 793 Offset = Tmp; 794 OffsetPHI->replaceAllUsesWith(Offset); 795 OffsetPHI->eraseFromParent(); 796 } 797 return std::make_pair(Size, Offset); 798 } 799 800 SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitSelectInst(SelectInst &I) { 801 SizeOffsetEvalType TrueSide = compute_(I.getTrueValue()); 802 SizeOffsetEvalType FalseSide = compute_(I.getFalseValue()); 803 804 if (!bothKnown(TrueSide) || !bothKnown(FalseSide)) 805 return unknown(); 806 if (TrueSide == FalseSide) 807 return TrueSide; 808 809 Value *Size = Builder.CreateSelect(I.getCondition(), TrueSide.first, 810 FalseSide.first); 811 Value *Offset = Builder.CreateSelect(I.getCondition(), TrueSide.second, 812 FalseSide.second); 813 return std::make_pair(Size, Offset); 814 } 815 816 SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitInstruction(Instruction &I) { 817 DEBUG(dbgs() << "ObjectSizeOffsetEvaluator unknown instruction:" << I <<'\n'); 818 return unknown(); 819 } 820