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