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/Lint.h" 38 #include "llvm/ADT/STLExtras.h" 39 #include "llvm/Analysis/AliasAnalysis.h" 40 #include "llvm/Analysis/ConstantFolding.h" 41 #include "llvm/Analysis/Dominators.h" 42 #include "llvm/Analysis/InstructionSimplify.h" 43 #include "llvm/Analysis/Loads.h" 44 #include "llvm/Analysis/Passes.h" 45 #include "llvm/Analysis/ValueTracking.h" 46 #include "llvm/Assembly/Writer.h" 47 #include "llvm/IR/DataLayout.h" 48 #include "llvm/IR/Function.h" 49 #include "llvm/IR/IntrinsicInst.h" 50 #include "llvm/InstVisitor.h" 51 #include "llvm/Pass.h" 52 #include "llvm/PassManager.h" 53 #include "llvm/Support/CallSite.h" 54 #include "llvm/Support/Debug.h" 55 #include "llvm/Support/raw_ostream.h" 56 #include "llvm/Target/TargetLibraryInfo.h" 57 using namespace llvm; 58 59 namespace { 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 152 char Lint::ID = 0; 153 INITIALIZE_PASS_BEGIN(Lint, "lint", "Statically lint-checks LLVM IR", 154 false, true) 155 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo) 156 INITIALIZE_PASS_DEPENDENCY(DominatorTree) 157 INITIALIZE_AG_DEPENDENCY(AliasAnalysis) 158 INITIALIZE_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 // 176 bool 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 188 void 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 197 void 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 347 void Lint::visitCallInst(CallInst &I) { 348 return visitCallSite(&I); 349 } 350 351 void Lint::visitInvokeInst(InvokeInst &I) { 352 return visitCallSite(&I); 353 } 354 355 void 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. 370 void 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 // Only handles memory references that read/write something simple like an 416 // alloca instruction or a global variable. 417 int64_t Offset = 0; 418 if (Value *Base = GetPointerBaseWithConstantOffset(Ptr, Offset, TD)) { 419 // OK, so the access is to a constant offset from Ptr. Check that Ptr is 420 // something we can handle and if so extract the size of this base object 421 // along with its alignment. 422 uint64_t BaseSize = AliasAnalysis::UnknownSize; 423 unsigned BaseAlign = 0; 424 425 if (AllocaInst *AI = dyn_cast<AllocaInst>(Base)) { 426 Type *ATy = AI->getAllocatedType(); 427 if (TD && !AI->isArrayAllocation() && ATy->isSized()) 428 BaseSize = TD->getTypeAllocSize(ATy); 429 BaseAlign = AI->getAlignment(); 430 if (TD && BaseAlign == 0 && ATy->isSized()) 431 BaseAlign = TD->getABITypeAlignment(ATy); 432 } else if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Base)) { 433 // If the global may be defined differently in another compilation unit 434 // then don't warn about funky memory accesses. 435 if (GV->hasDefinitiveInitializer()) { 436 Type *GTy = GV->getType()->getElementType(); 437 if (TD && GTy->isSized()) 438 BaseSize = TD->getTypeAllocSize(GTy); 439 BaseAlign = GV->getAlignment(); 440 if (TD && BaseAlign == 0 && GTy->isSized()) 441 BaseAlign = TD->getABITypeAlignment(GTy); 442 } 443 } 444 445 // Accesses from before the start or after the end of the object are not 446 // defined. 447 Assert1(Size == AliasAnalysis::UnknownSize || 448 BaseSize == AliasAnalysis::UnknownSize || 449 (Offset >= 0 && Offset + Size <= BaseSize), 450 "Undefined behavior: Buffer overflow", &I); 451 452 // Accesses that say that the memory is more aligned than it is are not 453 // defined. 454 if (TD && Align == 0 && Ty && Ty->isSized()) 455 Align = TD->getABITypeAlignment(Ty); 456 Assert1(!BaseAlign || Align <= MinAlign(BaseAlign, Offset), 457 "Undefined behavior: Memory reference address is misaligned", &I); 458 } 459 } 460 461 void Lint::visitLoadInst(LoadInst &I) { 462 visitMemoryReference(I, I.getPointerOperand(), 463 AA->getTypeStoreSize(I.getType()), I.getAlignment(), 464 I.getType(), MemRef::Read); 465 } 466 467 void Lint::visitStoreInst(StoreInst &I) { 468 visitMemoryReference(I, I.getPointerOperand(), 469 AA->getTypeStoreSize(I.getOperand(0)->getType()), 470 I.getAlignment(), 471 I.getOperand(0)->getType(), MemRef::Write); 472 } 473 474 void Lint::visitXor(BinaryOperator &I) { 475 Assert1(!isa<UndefValue>(I.getOperand(0)) || 476 !isa<UndefValue>(I.getOperand(1)), 477 "Undefined result: xor(undef, undef)", &I); 478 } 479 480 void Lint::visitSub(BinaryOperator &I) { 481 Assert1(!isa<UndefValue>(I.getOperand(0)) || 482 !isa<UndefValue>(I.getOperand(1)), 483 "Undefined result: sub(undef, undef)", &I); 484 } 485 486 void Lint::visitLShr(BinaryOperator &I) { 487 if (ConstantInt *CI = 488 dyn_cast<ConstantInt>(findValue(I.getOperand(1), /*OffsetOk=*/false))) 489 Assert1(CI->getValue().ult(cast<IntegerType>(I.getType())->getBitWidth()), 490 "Undefined result: Shift count out of range", &I); 491 } 492 493 void Lint::visitAShr(BinaryOperator &I) { 494 if (ConstantInt *CI = 495 dyn_cast<ConstantInt>(findValue(I.getOperand(1), /*OffsetOk=*/false))) 496 Assert1(CI->getValue().ult(cast<IntegerType>(I.getType())->getBitWidth()), 497 "Undefined result: Shift count out of range", &I); 498 } 499 500 void Lint::visitShl(BinaryOperator &I) { 501 if (ConstantInt *CI = 502 dyn_cast<ConstantInt>(findValue(I.getOperand(1), /*OffsetOk=*/false))) 503 Assert1(CI->getValue().ult(cast<IntegerType>(I.getType())->getBitWidth()), 504 "Undefined result: Shift count out of range", &I); 505 } 506 507 static bool isZero(Value *V, DataLayout *TD) { 508 // Assume undef could be zero. 509 if (isa<UndefValue>(V)) return true; 510 511 unsigned BitWidth = cast<IntegerType>(V->getType())->getBitWidth(); 512 APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0); 513 ComputeMaskedBits(V, KnownZero, KnownOne, TD); 514 return KnownZero.isAllOnesValue(); 515 } 516 517 void Lint::visitSDiv(BinaryOperator &I) { 518 Assert1(!isZero(I.getOperand(1), TD), 519 "Undefined behavior: Division by zero", &I); 520 } 521 522 void Lint::visitUDiv(BinaryOperator &I) { 523 Assert1(!isZero(I.getOperand(1), TD), 524 "Undefined behavior: Division by zero", &I); 525 } 526 527 void Lint::visitSRem(BinaryOperator &I) { 528 Assert1(!isZero(I.getOperand(1), TD), 529 "Undefined behavior: Division by zero", &I); 530 } 531 532 void Lint::visitURem(BinaryOperator &I) { 533 Assert1(!isZero(I.getOperand(1), TD), 534 "Undefined behavior: Division by zero", &I); 535 } 536 537 void Lint::visitAllocaInst(AllocaInst &I) { 538 if (isa<ConstantInt>(I.getArraySize())) 539 // This isn't undefined behavior, it's just an obvious pessimization. 540 Assert1(&I.getParent()->getParent()->getEntryBlock() == I.getParent(), 541 "Pessimization: Static alloca outside of entry block", &I); 542 543 // TODO: Check for an unusual size (MSB set?) 544 } 545 546 void Lint::visitVAArgInst(VAArgInst &I) { 547 visitMemoryReference(I, I.getOperand(0), AliasAnalysis::UnknownSize, 0, 0, 548 MemRef::Read | MemRef::Write); 549 } 550 551 void Lint::visitIndirectBrInst(IndirectBrInst &I) { 552 visitMemoryReference(I, I.getAddress(), AliasAnalysis::UnknownSize, 0, 0, 553 MemRef::Branchee); 554 555 Assert1(I.getNumDestinations() != 0, 556 "Undefined behavior: indirectbr with no destinations", &I); 557 } 558 559 void Lint::visitExtractElementInst(ExtractElementInst &I) { 560 if (ConstantInt *CI = 561 dyn_cast<ConstantInt>(findValue(I.getIndexOperand(), 562 /*OffsetOk=*/false))) 563 Assert1(CI->getValue().ult(I.getVectorOperandType()->getNumElements()), 564 "Undefined result: extractelement index out of range", &I); 565 } 566 567 void Lint::visitInsertElementInst(InsertElementInst &I) { 568 if (ConstantInt *CI = 569 dyn_cast<ConstantInt>(findValue(I.getOperand(2), 570 /*OffsetOk=*/false))) 571 Assert1(CI->getValue().ult(I.getType()->getNumElements()), 572 "Undefined result: insertelement index out of range", &I); 573 } 574 575 void Lint::visitUnreachableInst(UnreachableInst &I) { 576 // This isn't undefined behavior, it's merely suspicious. 577 Assert1(&I == I.getParent()->begin() || 578 prior(BasicBlock::iterator(&I))->mayHaveSideEffects(), 579 "Unusual: unreachable immediately preceded by instruction without " 580 "side effects", &I); 581 } 582 583 /// findValue - Look through bitcasts and simple memory reference patterns 584 /// to identify an equivalent, but more informative, value. If OffsetOk 585 /// is true, look through getelementptrs with non-zero offsets too. 586 /// 587 /// Most analysis passes don't require this logic, because instcombine 588 /// will simplify most of these kinds of things away. But it's a goal of 589 /// this Lint pass to be useful even on non-optimized IR. 590 Value *Lint::findValue(Value *V, bool OffsetOk) const { 591 SmallPtrSet<Value *, 4> Visited; 592 return findValueImpl(V, OffsetOk, Visited); 593 } 594 595 /// findValueImpl - Implementation helper for findValue. 596 Value *Lint::findValueImpl(Value *V, bool OffsetOk, 597 SmallPtrSet<Value *, 4> &Visited) const { 598 // Detect self-referential values. 599 if (!Visited.insert(V)) 600 return UndefValue::get(V->getType()); 601 602 // TODO: Look through sext or zext cast, when the result is known to 603 // be interpreted as signed or unsigned, respectively. 604 // TODO: Look through eliminable cast pairs. 605 // TODO: Look through calls with unique return values. 606 // TODO: Look through vector insert/extract/shuffle. 607 V = OffsetOk ? GetUnderlyingObject(V, TD) : V->stripPointerCasts(); 608 if (LoadInst *L = dyn_cast<LoadInst>(V)) { 609 BasicBlock::iterator BBI = L; 610 BasicBlock *BB = L->getParent(); 611 SmallPtrSet<BasicBlock *, 4> VisitedBlocks; 612 for (;;) { 613 if (!VisitedBlocks.insert(BB)) break; 614 if (Value *U = FindAvailableLoadedValue(L->getPointerOperand(), 615 BB, BBI, 6, AA)) 616 return findValueImpl(U, OffsetOk, Visited); 617 if (BBI != BB->begin()) break; 618 BB = BB->getUniquePredecessor(); 619 if (!BB) break; 620 BBI = BB->end(); 621 } 622 } else if (PHINode *PN = dyn_cast<PHINode>(V)) { 623 if (Value *W = PN->hasConstantValue()) 624 if (W != V) 625 return findValueImpl(W, OffsetOk, Visited); 626 } else if (CastInst *CI = dyn_cast<CastInst>(V)) { 627 if (CI->isNoopCast(TD ? TD->getIntPtrType(V->getContext()) : 628 Type::getInt64Ty(V->getContext()))) 629 return findValueImpl(CI->getOperand(0), OffsetOk, Visited); 630 } else if (ExtractValueInst *Ex = dyn_cast<ExtractValueInst>(V)) { 631 if (Value *W = FindInsertedValue(Ex->getAggregateOperand(), 632 Ex->getIndices())) 633 if (W != V) 634 return findValueImpl(W, OffsetOk, Visited); 635 } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) { 636 // Same as above, but for ConstantExpr instead of Instruction. 637 if (Instruction::isCast(CE->getOpcode())) { 638 if (CastInst::isNoopCast(Instruction::CastOps(CE->getOpcode()), 639 CE->getOperand(0)->getType(), 640 CE->getType(), 641 TD ? TD->getIntPtrType(V->getContext()) : 642 Type::getInt64Ty(V->getContext()))) 643 return findValueImpl(CE->getOperand(0), OffsetOk, Visited); 644 } else if (CE->getOpcode() == Instruction::ExtractValue) { 645 ArrayRef<unsigned> Indices = CE->getIndices(); 646 if (Value *W = FindInsertedValue(CE->getOperand(0), Indices)) 647 if (W != V) 648 return findValueImpl(W, OffsetOk, Visited); 649 } 650 } 651 652 // As a last resort, try SimplifyInstruction or constant folding. 653 if (Instruction *Inst = dyn_cast<Instruction>(V)) { 654 if (Value *W = SimplifyInstruction(Inst, TD, TLI, DT)) 655 return findValueImpl(W, OffsetOk, Visited); 656 } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) { 657 if (Value *W = ConstantFoldConstantExpression(CE, TD, TLI)) 658 if (W != V) 659 return findValueImpl(W, OffsetOk, Visited); 660 } 661 662 return V; 663 } 664 665 //===----------------------------------------------------------------------===// 666 // Implement the public interfaces to this file... 667 //===----------------------------------------------------------------------===// 668 669 FunctionPass *llvm::createLintPass() { 670 return new Lint(); 671 } 672 673 /// lintFunction - Check a function for errors, printing messages on stderr. 674 /// 675 void llvm::lintFunction(const Function &f) { 676 Function &F = const_cast<Function&>(f); 677 assert(!F.isDeclaration() && "Cannot lint external functions"); 678 679 FunctionPassManager FPM(F.getParent()); 680 Lint *V = new Lint(); 681 FPM.add(V); 682 FPM.run(F); 683 } 684 685 /// lintModule - Check a module for errors, printing messages on stderr. 686 /// 687 void llvm::lintModule(const Module &M) { 688 PassManager PM; 689 Lint *V = new Lint(); 690 PM.add(V); 691 PM.run(const_cast<Module&>(M)); 692 } 693
