1 //===-- Lint.cpp - Check for common errors in LLVM IR ---------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This pass statically checks for common and easily-identified constructs 10 // which produce undefined or likely unintended behavior in LLVM IR. 11 // 12 // It is not a guarantee of correctness, in two ways. First, it isn't 13 // comprehensive. There are checks which could be done statically which are 14 // not yet implemented. Some of these are indicated by TODO comments, but 15 // those aren't comprehensive either. Second, many conditions cannot be 16 // checked statically. This pass does no dynamic instrumentation, so it 17 // can't check for all possible problems. 18 // 19 // Another limitation is that it assumes all code will be executed. A store 20 // through a null pointer in a basic block which is never reached is harmless, 21 // but this pass will warn about it anyway. This is the main reason why most 22 // of these checks live here instead of in the Verifier pass. 23 // 24 // Optimization passes may make conditions that this pass checks for more or 25 // less obvious. If an optimization pass appears to be introducing a warning, 26 // it may be that the optimization pass is merely exposing an existing 27 // condition in the code. 28 // 29 // This code may be run before instcombine. In many cases, instcombine checks 30 // for the same kinds of things and turns instructions with undefined behavior 31 // into unreachable (or equivalent). Because of this, this pass makes some 32 // effort to look through bitcasts and so on. 33 // 34 //===----------------------------------------------------------------------===// 35 36 #include "llvm/Analysis/Lint.h" 37 #include "llvm/ADT/APInt.h" 38 #include "llvm/ADT/ArrayRef.h" 39 #include "llvm/ADT/SmallPtrSet.h" 40 #include "llvm/ADT/Twine.h" 41 #include "llvm/Analysis/AliasAnalysis.h" 42 #include "llvm/Analysis/AssumptionCache.h" 43 #include "llvm/Analysis/ConstantFolding.h" 44 #include "llvm/Analysis/InstructionSimplify.h" 45 #include "llvm/Analysis/Loads.h" 46 #include "llvm/Analysis/MemoryLocation.h" 47 #include "llvm/Analysis/Passes.h" 48 #include "llvm/Analysis/TargetLibraryInfo.h" 49 #include "llvm/Analysis/ValueTracking.h" 50 #include "llvm/IR/Argument.h" 51 #include "llvm/IR/BasicBlock.h" 52 #include "llvm/IR/CallSite.h" 53 #include "llvm/IR/Constant.h" 54 #include "llvm/IR/Constants.h" 55 #include "llvm/IR/DataLayout.h" 56 #include "llvm/IR/DerivedTypes.h" 57 #include "llvm/IR/Dominators.h" 58 #include "llvm/IR/Function.h" 59 #include "llvm/IR/GlobalVariable.h" 60 #include "llvm/IR/InstVisitor.h" 61 #include "llvm/IR/InstrTypes.h" 62 #include "llvm/IR/Instruction.h" 63 #include "llvm/IR/Instructions.h" 64 #include "llvm/IR/IntrinsicInst.h" 65 #include "llvm/IR/LegacyPassManager.h" 66 #include "llvm/IR/Module.h" 67 #include "llvm/IR/Type.h" 68 #include "llvm/IR/Value.h" 69 #include "llvm/InitializePasses.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(F); 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; 272 ++BI, ++ArgNo) { 273 // Skip ByVal arguments since they will be memcpy'd to the callee's 274 // stack so we're not really passing the pointer anyway. 275 if (PAL.hasParamAttribute(ArgNo, Attribute::ByVal)) 276 continue; 277 // If both arguments are readonly, they have no dependence. 278 if (Formal->onlyReadsMemory() && CS.onlyReadsMemory(ArgNo)) 279 continue; 280 if (AI != BI && (*BI)->getType()->isPointerTy()) { 281 AliasResult Result = AA->alias(*AI, *BI); 282 Assert(Result != MustAlias && Result != PartialAlias, 283 "Unusual: noalias argument aliases another argument", &I); 284 } 285 } 286 } 287 288 // Check that an sret argument points to valid memory. 289 if (Formal->hasStructRetAttr() && Actual->getType()->isPointerTy()) { 290 Type *Ty = 291 cast<PointerType>(Formal->getType())->getElementType(); 292 visitMemoryReference(I, Actual, DL->getTypeStoreSize(Ty), 293 DL->getABITypeAlignment(Ty), Ty, 294 MemRef::Read | MemRef::Write); 295 } 296 } 297 } 298 } 299 300 if (CS.isCall()) { 301 const CallInst *CI = cast<CallInst>(CS.getInstruction()); 302 if (CI->isTailCall()) { 303 const AttributeList &PAL = CI->getAttributes(); 304 unsigned ArgNo = 0; 305 for (Value *Arg : CS.args()) { 306 // Skip ByVal arguments since they will be memcpy'd to the callee's 307 // stack anyway. 308 if (PAL.hasParamAttribute(ArgNo++, Attribute::ByVal)) 309 continue; 310 Value *Obj = findValue(Arg, /*OffsetOk=*/true); 311 Assert(!isa<AllocaInst>(Obj), 312 "Undefined behavior: Call with \"tail\" keyword references " 313 "alloca", 314 &I); 315 } 316 } 317 } 318 319 320 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(&I)) 321 switch (II->getIntrinsicID()) { 322 default: break; 323 324 // TODO: Check more intrinsics 325 326 case Intrinsic::memcpy: { 327 MemCpyInst *MCI = cast<MemCpyInst>(&I); 328 // TODO: If the size is known, use it. 329 visitMemoryReference(I, MCI->getDest(), MemoryLocation::UnknownSize, 330 MCI->getDestAlignment(), nullptr, MemRef::Write); 331 visitMemoryReference(I, MCI->getSource(), MemoryLocation::UnknownSize, 332 MCI->getSourceAlignment(), nullptr, MemRef::Read); 333 334 // Check that the memcpy arguments don't overlap. The AliasAnalysis API 335 // isn't expressive enough for what we really want to do. Known partial 336 // overlap is not distinguished from the case where nothing is known. 337 auto Size = LocationSize::unknown(); 338 if (const ConstantInt *Len = 339 dyn_cast<ConstantInt>(findValue(MCI->getLength(), 340 /*OffsetOk=*/false))) 341 if (Len->getValue().isIntN(32)) 342 Size = LocationSize::precise(Len->getValue().getZExtValue()); 343 Assert(AA->alias(MCI->getSource(), Size, MCI->getDest(), Size) != 344 MustAlias, 345 "Undefined behavior: memcpy source and destination overlap", &I); 346 break; 347 } 348 case Intrinsic::memmove: { 349 MemMoveInst *MMI = cast<MemMoveInst>(&I); 350 // TODO: If the size is known, use it. 351 visitMemoryReference(I, MMI->getDest(), MemoryLocation::UnknownSize, 352 MMI->getDestAlignment(), nullptr, MemRef::Write); 353 visitMemoryReference(I, MMI->getSource(), MemoryLocation::UnknownSize, 354 MMI->getSourceAlignment(), nullptr, MemRef::Read); 355 break; 356 } 357 case Intrinsic::memset: { 358 MemSetInst *MSI = cast<MemSetInst>(&I); 359 // TODO: If the size is known, use it. 360 visitMemoryReference(I, MSI->getDest(), MemoryLocation::UnknownSize, 361 MSI->getDestAlignment(), nullptr, MemRef::Write); 362 break; 363 } 364 365 case Intrinsic::vastart: 366 Assert(I.getParent()->getParent()->isVarArg(), 367 "Undefined behavior: va_start called in a non-varargs function", 368 &I); 369 370 visitMemoryReference(I, CS.getArgument(0), MemoryLocation::UnknownSize, 0, 371 nullptr, MemRef::Read | MemRef::Write); 372 break; 373 case Intrinsic::vacopy: 374 visitMemoryReference(I, CS.getArgument(0), MemoryLocation::UnknownSize, 0, 375 nullptr, MemRef::Write); 376 visitMemoryReference(I, CS.getArgument(1), MemoryLocation::UnknownSize, 0, 377 nullptr, MemRef::Read); 378 break; 379 case Intrinsic::vaend: 380 visitMemoryReference(I, CS.getArgument(0), MemoryLocation::UnknownSize, 0, 381 nullptr, MemRef::Read | MemRef::Write); 382 break; 383 384 case Intrinsic::stackrestore: 385 // Stackrestore doesn't read or write memory, but it sets the 386 // stack pointer, which the compiler may read from or write to 387 // at any time, so check it for both readability and writeability. 388 visitMemoryReference(I, CS.getArgument(0), MemoryLocation::UnknownSize, 0, 389 nullptr, MemRef::Read | MemRef::Write); 390 break; 391 } 392 } 393 394 void Lint::visitCallInst(CallInst &I) { 395 return visitCallSite(&I); 396 } 397 398 void Lint::visitInvokeInst(InvokeInst &I) { 399 return visitCallSite(&I); 400 } 401 402 void Lint::visitReturnInst(ReturnInst &I) { 403 Function *F = I.getParent()->getParent(); 404 Assert(!F->doesNotReturn(), 405 "Unusual: Return statement in function with noreturn attribute", &I); 406 407 if (Value *V = I.getReturnValue()) { 408 Value *Obj = findValue(V, /*OffsetOk=*/true); 409 Assert(!isa<AllocaInst>(Obj), "Unusual: Returning alloca value", &I); 410 } 411 } 412 413 // TODO: Check that the reference is in bounds. 414 // TODO: Check readnone/readonly function attributes. 415 void Lint::visitMemoryReference(Instruction &I, 416 Value *Ptr, uint64_t Size, unsigned Align, 417 Type *Ty, unsigned Flags) { 418 // If no memory is being referenced, it doesn't matter if the pointer 419 // is valid. 420 if (Size == 0) 421 return; 422 423 Value *UnderlyingObject = findValue(Ptr, /*OffsetOk=*/true); 424 Assert(!isa<ConstantPointerNull>(UnderlyingObject), 425 "Undefined behavior: Null pointer dereference", &I); 426 Assert(!isa<UndefValue>(UnderlyingObject), 427 "Undefined behavior: Undef pointer dereference", &I); 428 Assert(!isa<ConstantInt>(UnderlyingObject) || 429 !cast<ConstantInt>(UnderlyingObject)->isMinusOne(), 430 "Unusual: All-ones pointer dereference", &I); 431 Assert(!isa<ConstantInt>(UnderlyingObject) || 432 !cast<ConstantInt>(UnderlyingObject)->isOne(), 433 "Unusual: Address one pointer dereference", &I); 434 435 if (Flags & MemRef::Write) { 436 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(UnderlyingObject)) 437 Assert(!GV->isConstant(), "Undefined behavior: Write to read-only memory", 438 &I); 439 Assert(!isa<Function>(UnderlyingObject) && 440 !isa<BlockAddress>(UnderlyingObject), 441 "Undefined behavior: Write to text section", &I); 442 } 443 if (Flags & MemRef::Read) { 444 Assert(!isa<Function>(UnderlyingObject), "Unusual: Load from function body", 445 &I); 446 Assert(!isa<BlockAddress>(UnderlyingObject), 447 "Undefined behavior: Load from block address", &I); 448 } 449 if (Flags & MemRef::Callee) { 450 Assert(!isa<BlockAddress>(UnderlyingObject), 451 "Undefined behavior: Call to block address", &I); 452 } 453 if (Flags & MemRef::Branchee) { 454 Assert(!isa<Constant>(UnderlyingObject) || 455 isa<BlockAddress>(UnderlyingObject), 456 "Undefined behavior: Branch to non-blockaddress", &I); 457 } 458 459 // Check for buffer overflows and misalignment. 460 // Only handles memory references that read/write something simple like an 461 // alloca instruction or a global variable. 462 int64_t Offset = 0; 463 if (Value *Base = GetPointerBaseWithConstantOffset(Ptr, Offset, *DL)) { 464 // OK, so the access is to a constant offset from Ptr. Check that Ptr is 465 // something we can handle and if so extract the size of this base object 466 // along with its alignment. 467 uint64_t BaseSize = MemoryLocation::UnknownSize; 468 unsigned BaseAlign = 0; 469 470 if (AllocaInst *AI = dyn_cast<AllocaInst>(Base)) { 471 Type *ATy = AI->getAllocatedType(); 472 if (!AI->isArrayAllocation() && ATy->isSized()) 473 BaseSize = DL->getTypeAllocSize(ATy); 474 BaseAlign = AI->getAlignment(); 475 if (BaseAlign == 0 && ATy->isSized()) 476 BaseAlign = DL->getABITypeAlignment(ATy); 477 } else if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Base)) { 478 // If the global may be defined differently in another compilation unit 479 // then don't warn about funky memory accesses. 480 if (GV->hasDefinitiveInitializer()) { 481 Type *GTy = GV->getValueType(); 482 if (GTy->isSized()) 483 BaseSize = DL->getTypeAllocSize(GTy); 484 BaseAlign = GV->getAlignment(); 485 if (BaseAlign == 0 && GTy->isSized()) 486 BaseAlign = DL->getABITypeAlignment(GTy); 487 } 488 } 489 490 // Accesses from before the start or after the end of the object are not 491 // defined. 492 Assert(Size == MemoryLocation::UnknownSize || 493 BaseSize == MemoryLocation::UnknownSize || 494 (Offset >= 0 && Offset + Size <= BaseSize), 495 "Undefined behavior: Buffer overflow", &I); 496 497 // Accesses that say that the memory is more aligned than it is are not 498 // defined. 499 if (Align == 0 && Ty && Ty->isSized()) 500 Align = DL->getABITypeAlignment(Ty); 501 Assert(!BaseAlign || Align <= MinAlign(BaseAlign, Offset), 502 "Undefined behavior: Memory reference address is misaligned", &I); 503 } 504 } 505 506 void Lint::visitLoadInst(LoadInst &I) { 507 visitMemoryReference(I, I.getPointerOperand(), 508 DL->getTypeStoreSize(I.getType()), I.getAlignment(), 509 I.getType(), MemRef::Read); 510 } 511 512 void Lint::visitStoreInst(StoreInst &I) { 513 visitMemoryReference(I, I.getPointerOperand(), 514 DL->getTypeStoreSize(I.getOperand(0)->getType()), 515 I.getAlignment(), 516 I.getOperand(0)->getType(), MemRef::Write); 517 } 518 519 void Lint::visitXor(BinaryOperator &I) { 520 Assert(!isa<UndefValue>(I.getOperand(0)) || !isa<UndefValue>(I.getOperand(1)), 521 "Undefined result: xor(undef, undef)", &I); 522 } 523 524 void Lint::visitSub(BinaryOperator &I) { 525 Assert(!isa<UndefValue>(I.getOperand(0)) || !isa<UndefValue>(I.getOperand(1)), 526 "Undefined result: sub(undef, undef)", &I); 527 } 528 529 void Lint::visitLShr(BinaryOperator &I) { 530 if (ConstantInt *CI = dyn_cast<ConstantInt>(findValue(I.getOperand(1), 531 /*OffsetOk=*/false))) 532 Assert(CI->getValue().ult(cast<IntegerType>(I.getType())->getBitWidth()), 533 "Undefined result: Shift count out of range", &I); 534 } 535 536 void Lint::visitAShr(BinaryOperator &I) { 537 if (ConstantInt *CI = 538 dyn_cast<ConstantInt>(findValue(I.getOperand(1), /*OffsetOk=*/false))) 539 Assert(CI->getValue().ult(cast<IntegerType>(I.getType())->getBitWidth()), 540 "Undefined result: Shift count out of range", &I); 541 } 542 543 void Lint::visitShl(BinaryOperator &I) { 544 if (ConstantInt *CI = 545 dyn_cast<ConstantInt>(findValue(I.getOperand(1), /*OffsetOk=*/false))) 546 Assert(CI->getValue().ult(cast<IntegerType>(I.getType())->getBitWidth()), 547 "Undefined result: Shift count out of range", &I); 548 } 549 550 static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, 551 AssumptionCache *AC) { 552 // Assume undef could be zero. 553 if (isa<UndefValue>(V)) 554 return true; 555 556 VectorType *VecTy = dyn_cast<VectorType>(V->getType()); 557 if (!VecTy) { 558 KnownBits Known = computeKnownBits(V, DL, 0, AC, dyn_cast<Instruction>(V), DT); 559 return Known.isZero(); 560 } 561 562 // Per-component check doesn't work with zeroinitializer 563 Constant *C = dyn_cast<Constant>(V); 564 if (!C) 565 return false; 566 567 if (C->isZeroValue()) 568 return true; 569 570 // For a vector, KnownZero will only be true if all values are zero, so check 571 // this per component 572 for (unsigned I = 0, N = VecTy->getNumElements(); I != N; ++I) { 573 Constant *Elem = C->getAggregateElement(I); 574 if (isa<UndefValue>(Elem)) 575 return true; 576 577 KnownBits Known = computeKnownBits(Elem, DL); 578 if (Known.isZero()) 579 return true; 580 } 581 582 return false; 583 } 584 585 void Lint::visitSDiv(BinaryOperator &I) { 586 Assert(!isZero(I.getOperand(1), I.getModule()->getDataLayout(), DT, AC), 587 "Undefined behavior: Division by zero", &I); 588 } 589 590 void Lint::visitUDiv(BinaryOperator &I) { 591 Assert(!isZero(I.getOperand(1), I.getModule()->getDataLayout(), DT, AC), 592 "Undefined behavior: Division by zero", &I); 593 } 594 595 void Lint::visitSRem(BinaryOperator &I) { 596 Assert(!isZero(I.getOperand(1), I.getModule()->getDataLayout(), DT, AC), 597 "Undefined behavior: Division by zero", &I); 598 } 599 600 void Lint::visitURem(BinaryOperator &I) { 601 Assert(!isZero(I.getOperand(1), I.getModule()->getDataLayout(), DT, AC), 602 "Undefined behavior: Division by zero", &I); 603 } 604 605 void Lint::visitAllocaInst(AllocaInst &I) { 606 if (isa<ConstantInt>(I.getArraySize())) 607 // This isn't undefined behavior, it's just an obvious pessimization. 608 Assert(&I.getParent()->getParent()->getEntryBlock() == I.getParent(), 609 "Pessimization: Static alloca outside of entry block", &I); 610 611 // TODO: Check for an unusual size (MSB set?) 612 } 613 614 void Lint::visitVAArgInst(VAArgInst &I) { 615 visitMemoryReference(I, I.getOperand(0), MemoryLocation::UnknownSize, 0, 616 nullptr, MemRef::Read | MemRef::Write); 617 } 618 619 void Lint::visitIndirectBrInst(IndirectBrInst &I) { 620 visitMemoryReference(I, I.getAddress(), MemoryLocation::UnknownSize, 0, 621 nullptr, MemRef::Branchee); 622 623 Assert(I.getNumDestinations() != 0, 624 "Undefined behavior: indirectbr with no destinations", &I); 625 } 626 627 void Lint::visitExtractElementInst(ExtractElementInst &I) { 628 if (ConstantInt *CI = dyn_cast<ConstantInt>(findValue(I.getIndexOperand(), 629 /*OffsetOk=*/false))) 630 Assert(CI->getValue().ult(I.getVectorOperandType()->getNumElements()), 631 "Undefined result: extractelement index out of range", &I); 632 } 633 634 void Lint::visitInsertElementInst(InsertElementInst &I) { 635 if (ConstantInt *CI = dyn_cast<ConstantInt>(findValue(I.getOperand(2), 636 /*OffsetOk=*/false))) 637 Assert(CI->getValue().ult(I.getType()->getNumElements()), 638 "Undefined result: insertelement index out of range", &I); 639 } 640 641 void Lint::visitUnreachableInst(UnreachableInst &I) { 642 // This isn't undefined behavior, it's merely suspicious. 643 Assert(&I == &I.getParent()->front() || 644 std::prev(I.getIterator())->mayHaveSideEffects(), 645 "Unusual: unreachable immediately preceded by instruction without " 646 "side effects", 647 &I); 648 } 649 650 /// findValue - Look through bitcasts and simple memory reference patterns 651 /// to identify an equivalent, but more informative, value. If OffsetOk 652 /// is true, look through getelementptrs with non-zero offsets too. 653 /// 654 /// Most analysis passes don't require this logic, because instcombine 655 /// will simplify most of these kinds of things away. But it's a goal of 656 /// this Lint pass to be useful even on non-optimized IR. 657 Value *Lint::findValue(Value *V, bool OffsetOk) const { 658 SmallPtrSet<Value *, 4> Visited; 659 return findValueImpl(V, OffsetOk, Visited); 660 } 661 662 /// findValueImpl - Implementation helper for findValue. 663 Value *Lint::findValueImpl(Value *V, bool OffsetOk, 664 SmallPtrSetImpl<Value *> &Visited) const { 665 // Detect self-referential values. 666 if (!Visited.insert(V).second) 667 return UndefValue::get(V->getType()); 668 669 // TODO: Look through sext or zext cast, when the result is known to 670 // be interpreted as signed or unsigned, respectively. 671 // TODO: Look through eliminable cast pairs. 672 // TODO: Look through calls with unique return values. 673 // TODO: Look through vector insert/extract/shuffle. 674 V = OffsetOk ? GetUnderlyingObject(V, *DL) : V->stripPointerCasts(); 675 if (LoadInst *L = dyn_cast<LoadInst>(V)) { 676 BasicBlock::iterator BBI = L->getIterator(); 677 BasicBlock *BB = L->getParent(); 678 SmallPtrSet<BasicBlock *, 4> VisitedBlocks; 679 for (;;) { 680 if (!VisitedBlocks.insert(BB).second) 681 break; 682 if (Value *U = 683 FindAvailableLoadedValue(L, BB, BBI, DefMaxInstsToScan, AA)) 684 return findValueImpl(U, OffsetOk, Visited); 685 if (BBI != BB->begin()) break; 686 BB = BB->getUniquePredecessor(); 687 if (!BB) break; 688 BBI = BB->end(); 689 } 690 } else if (PHINode *PN = dyn_cast<PHINode>(V)) { 691 if (Value *W = PN->hasConstantValue()) 692 if (W != V) 693 return findValueImpl(W, OffsetOk, Visited); 694 } else if (CastInst *CI = dyn_cast<CastInst>(V)) { 695 if (CI->isNoopCast(*DL)) 696 return findValueImpl(CI->getOperand(0), OffsetOk, Visited); 697 } else if (ExtractValueInst *Ex = dyn_cast<ExtractValueInst>(V)) { 698 if (Value *W = FindInsertedValue(Ex->getAggregateOperand(), 699 Ex->getIndices())) 700 if (W != V) 701 return findValueImpl(W, OffsetOk, Visited); 702 } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) { 703 // Same as above, but for ConstantExpr instead of Instruction. 704 if (Instruction::isCast(CE->getOpcode())) { 705 if (CastInst::isNoopCast(Instruction::CastOps(CE->getOpcode()), 706 CE->getOperand(0)->getType(), CE->getType(), 707 *DL)) 708 return findValueImpl(CE->getOperand(0), OffsetOk, Visited); 709 } else if (CE->getOpcode() == Instruction::ExtractValue) { 710 ArrayRef<unsigned> Indices = CE->getIndices(); 711 if (Value *W = FindInsertedValue(CE->getOperand(0), Indices)) 712 if (W != V) 713 return findValueImpl(W, OffsetOk, Visited); 714 } 715 } 716 717 // As a last resort, try SimplifyInstruction or constant folding. 718 if (Instruction *Inst = dyn_cast<Instruction>(V)) { 719 if (Value *W = SimplifyInstruction(Inst, {*DL, TLI, DT, AC})) 720 return findValueImpl(W, OffsetOk, Visited); 721 } else if (auto *C = dyn_cast<Constant>(V)) { 722 if (Value *W = ConstantFoldConstant(C, *DL, TLI)) 723 if (W && W != V) 724 return findValueImpl(W, OffsetOk, Visited); 725 } 726 727 return V; 728 } 729 730 //===----------------------------------------------------------------------===// 731 // Implement the public interfaces to this file... 732 //===----------------------------------------------------------------------===// 733 734 FunctionPass *llvm::createLintPass() { 735 return new Lint(); 736 } 737 738 /// lintFunction - Check a function for errors, printing messages on stderr. 739 /// 740 void llvm::lintFunction(const Function &f) { 741 Function &F = const_cast<Function&>(f); 742 assert(!F.isDeclaration() && "Cannot lint external functions"); 743 744 legacy::FunctionPassManager FPM(F.getParent()); 745 Lint *V = new Lint(); 746 FPM.add(V); 747 FPM.run(F); 748 } 749 750 /// lintModule - Check a module for errors, printing messages on stderr. 751 /// 752 void llvm::lintModule(const Module &M) { 753 legacy::PassManager PM; 754 Lint *V = new Lint(); 755 PM.add(V); 756 PM.run(const_cast<Module&>(M)); 757 } 758