Lint.cpp revision 243830
1//===-- Lint.cpp - Check for common errors in LLVM IR ---------------------===// 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 pass statically checks for common and easily-identified constructs 11// which produce undefined or likely unintended behavior in LLVM IR. 12// 13// It is not a guarantee of correctness, in two ways. First, it isn't 14// comprehensive. There are checks which could be done statically which are 15// not yet implemented. Some of these are indicated by TODO comments, but 16// those aren't comprehensive either. Second, many conditions cannot be 17// checked statically. This pass does no dynamic instrumentation, so it 18// can't check for all possible problems. 19// 20// Another limitation is that it assumes all code will be executed. A store 21// through a null pointer in a basic block which is never reached is harmless, 22// but this pass will warn about it anyway. This is the main reason why most 23// of these checks live here instead of in the Verifier pass. 24// 25// Optimization passes may make conditions that this pass checks for more or 26// less obvious. If an optimization pass appears to be introducing a warning, 27// it may be that the optimization pass is merely exposing an existing 28// condition in the code. 29// 30// This code may be run before instcombine. In many cases, instcombine checks 31// for the same kinds of things and turns instructions with undefined behavior 32// into unreachable (or equivalent). Because of this, this pass makes some 33// effort to look through bitcasts and so on. 34// 35//===----------------------------------------------------------------------===// 36 37#include "llvm/Analysis/Passes.h" 38#include "llvm/Analysis/AliasAnalysis.h" 39#include "llvm/Analysis/InstructionSimplify.h" 40#include "llvm/Analysis/ConstantFolding.h" 41#include "llvm/Analysis/Dominators.h" 42#include "llvm/Analysis/Lint.h" 43#include "llvm/Analysis/Loads.h" 44#include "llvm/Analysis/ValueTracking.h" 45#include "llvm/Assembly/Writer.h" 46#include "llvm/DataLayout.h" 47#include "llvm/Target/TargetLibraryInfo.h" 48#include "llvm/Pass.h" 49#include "llvm/PassManager.h" 50#include "llvm/IntrinsicInst.h" 51#include "llvm/Function.h" 52#include "llvm/Support/CallSite.h" 53#include "llvm/Support/Debug.h" 54#include "llvm/Support/InstVisitor.h" 55#include "llvm/Support/raw_ostream.h" 56#include "llvm/ADT/STLExtras.h" 57using namespace llvm; 58 59namespace { 60 namespace MemRef { 61 static unsigned Read = 1; 62 static unsigned Write = 2; 63 static unsigned Callee = 4; 64 static unsigned Branchee = 8; 65 } 66 67 class Lint : public FunctionPass, public InstVisitor<Lint> { 68 friend class InstVisitor<Lint>; 69 70 void visitFunction(Function &F); 71 72 void visitCallSite(CallSite CS); 73 void visitMemoryReference(Instruction &I, Value *Ptr, 74 uint64_t Size, unsigned Align, 75 Type *Ty, unsigned Flags); 76 77 void visitCallInst(CallInst &I); 78 void visitInvokeInst(InvokeInst &I); 79 void visitReturnInst(ReturnInst &I); 80 void visitLoadInst(LoadInst &I); 81 void visitStoreInst(StoreInst &I); 82 void visitXor(BinaryOperator &I); 83 void visitSub(BinaryOperator &I); 84 void visitLShr(BinaryOperator &I); 85 void visitAShr(BinaryOperator &I); 86 void visitShl(BinaryOperator &I); 87 void visitSDiv(BinaryOperator &I); 88 void visitUDiv(BinaryOperator &I); 89 void visitSRem(BinaryOperator &I); 90 void visitURem(BinaryOperator &I); 91 void visitAllocaInst(AllocaInst &I); 92 void visitVAArgInst(VAArgInst &I); 93 void visitIndirectBrInst(IndirectBrInst &I); 94 void visitExtractElementInst(ExtractElementInst &I); 95 void visitInsertElementInst(InsertElementInst &I); 96 void visitUnreachableInst(UnreachableInst &I); 97 98 Value *findValue(Value *V, bool OffsetOk) const; 99 Value *findValueImpl(Value *V, bool OffsetOk, 100 SmallPtrSet<Value *, 4> &Visited) const; 101 102 public: 103 Module *Mod; 104 AliasAnalysis *AA; 105 DominatorTree *DT; 106 DataLayout *TD; 107 TargetLibraryInfo *TLI; 108 109 std::string Messages; 110 raw_string_ostream MessagesStr; 111 112 static char ID; // Pass identification, replacement for typeid 113 Lint() : FunctionPass(ID), MessagesStr(Messages) { 114 initializeLintPass(*PassRegistry::getPassRegistry()); 115 } 116 117 virtual bool runOnFunction(Function &F); 118 119 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 120 AU.setPreservesAll(); 121 AU.addRequired<AliasAnalysis>(); 122 AU.addRequired<TargetLibraryInfo>(); 123 AU.addRequired<DominatorTree>(); 124 } 125 virtual void print(raw_ostream &O, const Module *M) const {} 126 127 void WriteValue(const Value *V) { 128 if (!V) return; 129 if (isa<Instruction>(V)) { 130 MessagesStr << *V << '\n'; 131 } else { 132 WriteAsOperand(MessagesStr, V, true, Mod); 133 MessagesStr << '\n'; 134 } 135 } 136 137 // CheckFailed - A check failed, so print out the condition and the message 138 // that failed. This provides a nice place to put a breakpoint if you want 139 // to see why something is not correct. 140 void CheckFailed(const Twine &Message, 141 const Value *V1 = 0, const Value *V2 = 0, 142 const Value *V3 = 0, const Value *V4 = 0) { 143 MessagesStr << Message.str() << "\n"; 144 WriteValue(V1); 145 WriteValue(V2); 146 WriteValue(V3); 147 WriteValue(V4); 148 } 149 }; 150} 151 152char Lint::ID = 0; 153INITIALIZE_PASS_BEGIN(Lint, "lint", "Statically lint-checks LLVM IR", 154 false, true) 155INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo) 156INITIALIZE_PASS_DEPENDENCY(DominatorTree) 157INITIALIZE_AG_DEPENDENCY(AliasAnalysis) 158INITIALIZE_PASS_END(Lint, "lint", "Statically lint-checks LLVM IR", 159 false, true) 160 161// Assert - We know that cond should be true, if not print an error message. 162#define Assert(C, M) \ 163 do { if (!(C)) { CheckFailed(M); return; } } while (0) 164#define Assert1(C, M, V1) \ 165 do { if (!(C)) { CheckFailed(M, V1); return; } } while (0) 166#define Assert2(C, M, V1, V2) \ 167 do { if (!(C)) { CheckFailed(M, V1, V2); return; } } while (0) 168#define Assert3(C, M, V1, V2, V3) \ 169 do { if (!(C)) { CheckFailed(M, V1, V2, V3); return; } } while (0) 170#define Assert4(C, M, V1, V2, V3, V4) \ 171 do { if (!(C)) { CheckFailed(M, V1, V2, V3, V4); return; } } while (0) 172 173// Lint::run - This is the main Analysis entry point for a 174// function. 175// 176bool Lint::runOnFunction(Function &F) { 177 Mod = F.getParent(); 178 AA = &getAnalysis<AliasAnalysis>(); 179 DT = &getAnalysis<DominatorTree>(); 180 TD = getAnalysisIfAvailable<DataLayout>(); 181 TLI = &getAnalysis<TargetLibraryInfo>(); 182 visit(F); 183 dbgs() << MessagesStr.str(); 184 Messages.clear(); 185 return false; 186} 187 188void Lint::visitFunction(Function &F) { 189 // This isn't undefined behavior, it's just a little unusual, and it's a 190 // fairly common mistake to neglect to name a function. 191 Assert1(F.hasName() || F.hasLocalLinkage(), 192 "Unusual: Unnamed function with non-local linkage", &F); 193 194 // TODO: Check for irreducible control flow. 195} 196 197void Lint::visitCallSite(CallSite CS) { 198 Instruction &I = *CS.getInstruction(); 199 Value *Callee = CS.getCalledValue(); 200 201 visitMemoryReference(I, Callee, AliasAnalysis::UnknownSize, 202 0, 0, MemRef::Callee); 203 204 if (Function *F = dyn_cast<Function>(findValue(Callee, /*OffsetOk=*/false))) { 205 Assert1(CS.getCallingConv() == F->getCallingConv(), 206 "Undefined behavior: Caller and callee calling convention differ", 207 &I); 208 209 FunctionType *FT = F->getFunctionType(); 210 unsigned NumActualArgs = unsigned(CS.arg_end()-CS.arg_begin()); 211 212 Assert1(FT->isVarArg() ? 213 FT->getNumParams() <= NumActualArgs : 214 FT->getNumParams() == NumActualArgs, 215 "Undefined behavior: Call argument count mismatches callee " 216 "argument count", &I); 217 218 Assert1(FT->getReturnType() == I.getType(), 219 "Undefined behavior: Call return type mismatches " 220 "callee return type", &I); 221 222 // Check argument types (in case the callee was casted) and attributes. 223 // TODO: Verify that caller and callee attributes are compatible. 224 Function::arg_iterator PI = F->arg_begin(), PE = F->arg_end(); 225 CallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end(); 226 for (; AI != AE; ++AI) { 227 Value *Actual = *AI; 228 if (PI != PE) { 229 Argument *Formal = PI++; 230 Assert1(Formal->getType() == Actual->getType(), 231 "Undefined behavior: Call argument type mismatches " 232 "callee parameter type", &I); 233 234 // Check that noalias arguments don't alias other arguments. This is 235 // not fully precise because we don't know the sizes of the dereferenced 236 // memory regions. 237 if (Formal->hasNoAliasAttr() && Actual->getType()->isPointerTy()) 238 for (CallSite::arg_iterator BI = CS.arg_begin(); BI != AE; ++BI) 239 if (AI != BI && (*BI)->getType()->isPointerTy()) { 240 AliasAnalysis::AliasResult Result = AA->alias(*AI, *BI); 241 Assert1(Result != AliasAnalysis::MustAlias && 242 Result != AliasAnalysis::PartialAlias, 243 "Unusual: noalias argument aliases another argument", &I); 244 } 245 246 // Check that an sret argument points to valid memory. 247 if (Formal->hasStructRetAttr() && Actual->getType()->isPointerTy()) { 248 Type *Ty = 249 cast<PointerType>(Formal->getType())->getElementType(); 250 visitMemoryReference(I, Actual, AA->getTypeStoreSize(Ty), 251 TD ? TD->getABITypeAlignment(Ty) : 0, 252 Ty, MemRef::Read | MemRef::Write); 253 } 254 } 255 } 256 } 257 258 if (CS.isCall() && cast<CallInst>(CS.getInstruction())->isTailCall()) 259 for (CallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end(); 260 AI != AE; ++AI) { 261 Value *Obj = findValue(*AI, /*OffsetOk=*/true); 262 Assert1(!isa<AllocaInst>(Obj), 263 "Undefined behavior: Call with \"tail\" keyword references " 264 "alloca", &I); 265 } 266 267 268 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(&I)) 269 switch (II->getIntrinsicID()) { 270 default: break; 271 272 // TODO: Check more intrinsics 273 274 case Intrinsic::memcpy: { 275 MemCpyInst *MCI = cast<MemCpyInst>(&I); 276 // TODO: If the size is known, use it. 277 visitMemoryReference(I, MCI->getDest(), AliasAnalysis::UnknownSize, 278 MCI->getAlignment(), 0, 279 MemRef::Write); 280 visitMemoryReference(I, MCI->getSource(), AliasAnalysis::UnknownSize, 281 MCI->getAlignment(), 0, 282 MemRef::Read); 283 284 // Check that the memcpy arguments don't overlap. The AliasAnalysis API 285 // isn't expressive enough for what we really want to do. Known partial 286 // overlap is not distinguished from the case where nothing is known. 287 uint64_t Size = 0; 288 if (const ConstantInt *Len = 289 dyn_cast<ConstantInt>(findValue(MCI->getLength(), 290 /*OffsetOk=*/false))) 291 if (Len->getValue().isIntN(32)) 292 Size = Len->getValue().getZExtValue(); 293 Assert1(AA->alias(MCI->getSource(), Size, MCI->getDest(), Size) != 294 AliasAnalysis::MustAlias, 295 "Undefined behavior: memcpy source and destination overlap", &I); 296 break; 297 } 298 case Intrinsic::memmove: { 299 MemMoveInst *MMI = cast<MemMoveInst>(&I); 300 // TODO: If the size is known, use it. 301 visitMemoryReference(I, MMI->getDest(), AliasAnalysis::UnknownSize, 302 MMI->getAlignment(), 0, 303 MemRef::Write); 304 visitMemoryReference(I, MMI->getSource(), AliasAnalysis::UnknownSize, 305 MMI->getAlignment(), 0, 306 MemRef::Read); 307 break; 308 } 309 case Intrinsic::memset: { 310 MemSetInst *MSI = cast<MemSetInst>(&I); 311 // TODO: If the size is known, use it. 312 visitMemoryReference(I, MSI->getDest(), AliasAnalysis::UnknownSize, 313 MSI->getAlignment(), 0, 314 MemRef::Write); 315 break; 316 } 317 318 case Intrinsic::vastart: 319 Assert1(I.getParent()->getParent()->isVarArg(), 320 "Undefined behavior: va_start called in a non-varargs function", 321 &I); 322 323 visitMemoryReference(I, CS.getArgument(0), AliasAnalysis::UnknownSize, 324 0, 0, MemRef::Read | MemRef::Write); 325 break; 326 case Intrinsic::vacopy: 327 visitMemoryReference(I, CS.getArgument(0), AliasAnalysis::UnknownSize, 328 0, 0, MemRef::Write); 329 visitMemoryReference(I, CS.getArgument(1), AliasAnalysis::UnknownSize, 330 0, 0, MemRef::Read); 331 break; 332 case Intrinsic::vaend: 333 visitMemoryReference(I, CS.getArgument(0), AliasAnalysis::UnknownSize, 334 0, 0, MemRef::Read | MemRef::Write); 335 break; 336 337 case Intrinsic::stackrestore: 338 // Stackrestore doesn't read or write memory, but it sets the 339 // stack pointer, which the compiler may read from or write to 340 // at any time, so check it for both readability and writeability. 341 visitMemoryReference(I, CS.getArgument(0), AliasAnalysis::UnknownSize, 342 0, 0, MemRef::Read | MemRef::Write); 343 break; 344 } 345} 346 347void Lint::visitCallInst(CallInst &I) { 348 return visitCallSite(&I); 349} 350 351void Lint::visitInvokeInst(InvokeInst &I) { 352 return visitCallSite(&I); 353} 354 355void Lint::visitReturnInst(ReturnInst &I) { 356 Function *F = I.getParent()->getParent(); 357 Assert1(!F->doesNotReturn(), 358 "Unusual: Return statement in function with noreturn attribute", 359 &I); 360 361 if (Value *V = I.getReturnValue()) { 362 Value *Obj = findValue(V, /*OffsetOk=*/true); 363 Assert1(!isa<AllocaInst>(Obj), 364 "Unusual: Returning alloca value", &I); 365 } 366} 367 368// TODO: Check that the reference is in bounds. 369// TODO: Check readnone/readonly function attributes. 370void Lint::visitMemoryReference(Instruction &I, 371 Value *Ptr, uint64_t Size, unsigned Align, 372 Type *Ty, unsigned Flags) { 373 // If no memory is being referenced, it doesn't matter if the pointer 374 // is valid. 375 if (Size == 0) 376 return; 377 378 Value *UnderlyingObject = findValue(Ptr, /*OffsetOk=*/true); 379 Assert1(!isa<ConstantPointerNull>(UnderlyingObject), 380 "Undefined behavior: Null pointer dereference", &I); 381 Assert1(!isa<UndefValue>(UnderlyingObject), 382 "Undefined behavior: Undef pointer dereference", &I); 383 Assert1(!isa<ConstantInt>(UnderlyingObject) || 384 !cast<ConstantInt>(UnderlyingObject)->isAllOnesValue(), 385 "Unusual: All-ones pointer dereference", &I); 386 Assert1(!isa<ConstantInt>(UnderlyingObject) || 387 !cast<ConstantInt>(UnderlyingObject)->isOne(), 388 "Unusual: Address one pointer dereference", &I); 389 390 if (Flags & MemRef::Write) { 391 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(UnderlyingObject)) 392 Assert1(!GV->isConstant(), 393 "Undefined behavior: Write to read-only memory", &I); 394 Assert1(!isa<Function>(UnderlyingObject) && 395 !isa<BlockAddress>(UnderlyingObject), 396 "Undefined behavior: Write to text section", &I); 397 } 398 if (Flags & MemRef::Read) { 399 Assert1(!isa<Function>(UnderlyingObject), 400 "Unusual: Load from function body", &I); 401 Assert1(!isa<BlockAddress>(UnderlyingObject), 402 "Undefined behavior: Load from block address", &I); 403 } 404 if (Flags & MemRef::Callee) { 405 Assert1(!isa<BlockAddress>(UnderlyingObject), 406 "Undefined behavior: Call to block address", &I); 407 } 408 if (Flags & MemRef::Branchee) { 409 Assert1(!isa<Constant>(UnderlyingObject) || 410 isa<BlockAddress>(UnderlyingObject), 411 "Undefined behavior: Branch to non-blockaddress", &I); 412 } 413 414 // Check for buffer overflows and misalignment. 415 if (TD) { 416 // Only handles memory references that read/write something simple like an 417 // alloca instruction or a global variable. 418 int64_t Offset = 0; 419 if (Value *Base = GetPointerBaseWithConstantOffset(Ptr, Offset, *TD)) { 420 // OK, so the access is to a constant offset from Ptr. Check that Ptr is 421 // something we can handle and if so extract the size of this base object 422 // along with its alignment. 423 uint64_t BaseSize = AliasAnalysis::UnknownSize; 424 unsigned BaseAlign = 0; 425 426 if (AllocaInst *AI = dyn_cast<AllocaInst>(Base)) { 427 Type *ATy = AI->getAllocatedType(); 428 if (!AI->isArrayAllocation() && ATy->isSized()) 429 BaseSize = TD->getTypeAllocSize(ATy); 430 BaseAlign = AI->getAlignment(); 431 if (BaseAlign == 0 && ATy->isSized()) 432 BaseAlign = TD->getABITypeAlignment(ATy); 433 } else if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Base)) { 434 // If the global may be defined differently in another compilation unit 435 // then don't warn about funky memory accesses. 436 if (GV->hasDefinitiveInitializer()) { 437 Type *GTy = GV->getType()->getElementType(); 438 if (GTy->isSized()) 439 BaseSize = TD->getTypeAllocSize(GTy); 440 BaseAlign = GV->getAlignment(); 441 if (BaseAlign == 0 && GTy->isSized()) 442 BaseAlign = TD->getABITypeAlignment(GTy); 443 } 444 } 445 446 // Accesses from before the start or after the end of the object are not 447 // defined. 448 Assert1(Size == AliasAnalysis::UnknownSize || 449 BaseSize == AliasAnalysis::UnknownSize || 450 (Offset >= 0 && Offset + Size <= BaseSize), 451 "Undefined behavior: Buffer overflow", &I); 452 453 // Accesses that say that the memory is more aligned than it is are not 454 // defined. 455 if (Align == 0 && Ty && Ty->isSized()) 456 Align = TD->getABITypeAlignment(Ty); 457 Assert1(!BaseAlign || Align <= MinAlign(BaseAlign, Offset), 458 "Undefined behavior: Memory reference address is misaligned", &I); 459 } 460 } 461} 462 463void Lint::visitLoadInst(LoadInst &I) { 464 visitMemoryReference(I, I.getPointerOperand(), 465 AA->getTypeStoreSize(I.getType()), I.getAlignment(), 466 I.getType(), MemRef::Read); 467} 468 469void Lint::visitStoreInst(StoreInst &I) { 470 visitMemoryReference(I, I.getPointerOperand(), 471 AA->getTypeStoreSize(I.getOperand(0)->getType()), 472 I.getAlignment(), 473 I.getOperand(0)->getType(), MemRef::Write); 474} 475 476void Lint::visitXor(BinaryOperator &I) { 477 Assert1(!isa<UndefValue>(I.getOperand(0)) || 478 !isa<UndefValue>(I.getOperand(1)), 479 "Undefined result: xor(undef, undef)", &I); 480} 481 482void Lint::visitSub(BinaryOperator &I) { 483 Assert1(!isa<UndefValue>(I.getOperand(0)) || 484 !isa<UndefValue>(I.getOperand(1)), 485 "Undefined result: sub(undef, undef)", &I); 486} 487 488void Lint::visitLShr(BinaryOperator &I) { 489 if (ConstantInt *CI = 490 dyn_cast<ConstantInt>(findValue(I.getOperand(1), /*OffsetOk=*/false))) 491 Assert1(CI->getValue().ult(cast<IntegerType>(I.getType())->getBitWidth()), 492 "Undefined result: Shift count out of range", &I); 493} 494 495void Lint::visitAShr(BinaryOperator &I) { 496 if (ConstantInt *CI = 497 dyn_cast<ConstantInt>(findValue(I.getOperand(1), /*OffsetOk=*/false))) 498 Assert1(CI->getValue().ult(cast<IntegerType>(I.getType())->getBitWidth()), 499 "Undefined result: Shift count out of range", &I); 500} 501 502void Lint::visitShl(BinaryOperator &I) { 503 if (ConstantInt *CI = 504 dyn_cast<ConstantInt>(findValue(I.getOperand(1), /*OffsetOk=*/false))) 505 Assert1(CI->getValue().ult(cast<IntegerType>(I.getType())->getBitWidth()), 506 "Undefined result: Shift count out of range", &I); 507} 508 509static bool isZero(Value *V, DataLayout *TD) { 510 // Assume undef could be zero. 511 if (isa<UndefValue>(V)) return true; 512 513 unsigned BitWidth = cast<IntegerType>(V->getType())->getBitWidth(); 514 APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0); 515 ComputeMaskedBits(V, KnownZero, KnownOne, TD); 516 return KnownZero.isAllOnesValue(); 517} 518 519void Lint::visitSDiv(BinaryOperator &I) { 520 Assert1(!isZero(I.getOperand(1), TD), 521 "Undefined behavior: Division by zero", &I); 522} 523 524void Lint::visitUDiv(BinaryOperator &I) { 525 Assert1(!isZero(I.getOperand(1), TD), 526 "Undefined behavior: Division by zero", &I); 527} 528 529void Lint::visitSRem(BinaryOperator &I) { 530 Assert1(!isZero(I.getOperand(1), TD), 531 "Undefined behavior: Division by zero", &I); 532} 533 534void Lint::visitURem(BinaryOperator &I) { 535 Assert1(!isZero(I.getOperand(1), TD), 536 "Undefined behavior: Division by zero", &I); 537} 538 539void Lint::visitAllocaInst(AllocaInst &I) { 540 if (isa<ConstantInt>(I.getArraySize())) 541 // This isn't undefined behavior, it's just an obvious pessimization. 542 Assert1(&I.getParent()->getParent()->getEntryBlock() == I.getParent(), 543 "Pessimization: Static alloca outside of entry block", &I); 544 545 // TODO: Check for an unusual size (MSB set?) 546} 547 548void Lint::visitVAArgInst(VAArgInst &I) { 549 visitMemoryReference(I, I.getOperand(0), AliasAnalysis::UnknownSize, 0, 0, 550 MemRef::Read | MemRef::Write); 551} 552 553void Lint::visitIndirectBrInst(IndirectBrInst &I) { 554 visitMemoryReference(I, I.getAddress(), AliasAnalysis::UnknownSize, 0, 0, 555 MemRef::Branchee); 556 557 Assert1(I.getNumDestinations() != 0, 558 "Undefined behavior: indirectbr with no destinations", &I); 559} 560 561void Lint::visitExtractElementInst(ExtractElementInst &I) { 562 if (ConstantInt *CI = 563 dyn_cast<ConstantInt>(findValue(I.getIndexOperand(), 564 /*OffsetOk=*/false))) 565 Assert1(CI->getValue().ult(I.getVectorOperandType()->getNumElements()), 566 "Undefined result: extractelement index out of range", &I); 567} 568 569void Lint::visitInsertElementInst(InsertElementInst &I) { 570 if (ConstantInt *CI = 571 dyn_cast<ConstantInt>(findValue(I.getOperand(2), 572 /*OffsetOk=*/false))) 573 Assert1(CI->getValue().ult(I.getType()->getNumElements()), 574 "Undefined result: insertelement index out of range", &I); 575} 576 577void Lint::visitUnreachableInst(UnreachableInst &I) { 578 // This isn't undefined behavior, it's merely suspicious. 579 Assert1(&I == I.getParent()->begin() || 580 prior(BasicBlock::iterator(&I))->mayHaveSideEffects(), 581 "Unusual: unreachable immediately preceded by instruction without " 582 "side effects", &I); 583} 584 585/// findValue - Look through bitcasts and simple memory reference patterns 586/// to identify an equivalent, but more informative, value. If OffsetOk 587/// is true, look through getelementptrs with non-zero offsets too. 588/// 589/// Most analysis passes don't require this logic, because instcombine 590/// will simplify most of these kinds of things away. But it's a goal of 591/// this Lint pass to be useful even on non-optimized IR. 592Value *Lint::findValue(Value *V, bool OffsetOk) const { 593 SmallPtrSet<Value *, 4> Visited; 594 return findValueImpl(V, OffsetOk, Visited); 595} 596 597/// findValueImpl - Implementation helper for findValue. 598Value *Lint::findValueImpl(Value *V, bool OffsetOk, 599 SmallPtrSet<Value *, 4> &Visited) const { 600 // Detect self-referential values. 601 if (!Visited.insert(V)) 602 return UndefValue::get(V->getType()); 603 604 // TODO: Look through sext or zext cast, when the result is known to 605 // be interpreted as signed or unsigned, respectively. 606 // TODO: Look through eliminable cast pairs. 607 // TODO: Look through calls with unique return values. 608 // TODO: Look through vector insert/extract/shuffle. 609 V = OffsetOk ? GetUnderlyingObject(V, TD) : V->stripPointerCasts(); 610 if (LoadInst *L = dyn_cast<LoadInst>(V)) { 611 BasicBlock::iterator BBI = L; 612 BasicBlock *BB = L->getParent(); 613 SmallPtrSet<BasicBlock *, 4> VisitedBlocks; 614 for (;;) { 615 if (!VisitedBlocks.insert(BB)) break; 616 if (Value *U = FindAvailableLoadedValue(L->getPointerOperand(), 617 BB, BBI, 6, AA)) 618 return findValueImpl(U, OffsetOk, Visited); 619 if (BBI != BB->begin()) break; 620 BB = BB->getUniquePredecessor(); 621 if (!BB) break; 622 BBI = BB->end(); 623 } 624 } else if (PHINode *PN = dyn_cast<PHINode>(V)) { 625 if (Value *W = PN->hasConstantValue()) 626 if (W != V) 627 return findValueImpl(W, OffsetOk, Visited); 628 } else if (CastInst *CI = dyn_cast<CastInst>(V)) { 629 if (CI->isNoopCast(TD ? TD->getIntPtrType(V->getContext()) : 630 Type::getInt64Ty(V->getContext()))) 631 return findValueImpl(CI->getOperand(0), OffsetOk, Visited); 632 } else if (ExtractValueInst *Ex = dyn_cast<ExtractValueInst>(V)) { 633 if (Value *W = FindInsertedValue(Ex->getAggregateOperand(), 634 Ex->getIndices())) 635 if (W != V) 636 return findValueImpl(W, OffsetOk, Visited); 637 } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) { 638 // Same as above, but for ConstantExpr instead of Instruction. 639 if (Instruction::isCast(CE->getOpcode())) { 640 if (CastInst::isNoopCast(Instruction::CastOps(CE->getOpcode()), 641 CE->getOperand(0)->getType(), 642 CE->getType(), 643 TD ? TD->getIntPtrType(V->getContext()) : 644 Type::getInt64Ty(V->getContext()))) 645 return findValueImpl(CE->getOperand(0), OffsetOk, Visited); 646 } else if (CE->getOpcode() == Instruction::ExtractValue) { 647 ArrayRef<unsigned> Indices = CE->getIndices(); 648 if (Value *W = FindInsertedValue(CE->getOperand(0), Indices)) 649 if (W != V) 650 return findValueImpl(W, OffsetOk, Visited); 651 } 652 } 653 654 // As a last resort, try SimplifyInstruction or constant folding. 655 if (Instruction *Inst = dyn_cast<Instruction>(V)) { 656 if (Value *W = SimplifyInstruction(Inst, TD, TLI, DT)) 657 return findValueImpl(W, OffsetOk, Visited); 658 } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) { 659 if (Value *W = ConstantFoldConstantExpression(CE, TD, TLI)) 660 if (W != V) 661 return findValueImpl(W, OffsetOk, Visited); 662 } 663 664 return V; 665} 666 667//===----------------------------------------------------------------------===// 668// Implement the public interfaces to this file... 669//===----------------------------------------------------------------------===// 670 671FunctionPass *llvm::createLintPass() { 672 return new Lint(); 673} 674 675/// lintFunction - Check a function for errors, printing messages on stderr. 676/// 677void llvm::lintFunction(const Function &f) { 678 Function &F = const_cast<Function&>(f); 679 assert(!F.isDeclaration() && "Cannot lint external functions"); 680 681 FunctionPassManager FPM(F.getParent()); 682 Lint *V = new Lint(); 683 FPM.add(V); 684 FPM.run(F); 685} 686 687/// lintModule - Check a module for errors, printing messages on stderr. 688/// 689void llvm::lintModule(const Module &M) { 690 PassManager PM; 691 Lint *V = new Lint(); 692 PM.add(V); 693 PM.run(const_cast<Module&>(M)); 694} 695