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