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/InstructionSimplify.h" 42 #include "llvm/Analysis/Loads.h" 43 #include "llvm/Analysis/Passes.h" 44 #include "llvm/Analysis/ValueTracking.h" 45 #include "llvm/IR/CallSite.h" 46 #include "llvm/IR/DataLayout.h" 47 #include "llvm/IR/Dominators.h" 48 #include "llvm/IR/Function.h" 49 #include "llvm/IR/InstVisitor.h" 50 #include "llvm/IR/IntrinsicInst.h" 51 #include "llvm/Pass.h" 52 #include "llvm/PassManager.h" 53 #include "llvm/Support/Debug.h" 54 #include "llvm/Support/raw_ostream.h" 55 #include "llvm/Target/TargetLibraryInfo.h" 56 using namespace llvm; 57 58 namespace { 59 namespace MemRef { 60 static unsigned Read = 1; 61 static unsigned Write = 2; 62 static unsigned Callee = 4; 63 static unsigned Branchee = 8; 64 } 65 66 class Lint : public FunctionPass, public InstVisitor<Lint> { 67 friend class InstVisitor<Lint>; 68 69 void visitFunction(Function &F); 70 71 void visitCallSite(CallSite CS); 72 void visitMemoryReference(Instruction &I, Value *Ptr, 73 uint64_t Size, unsigned Align, 74 Type *Ty, unsigned Flags); 75 76 void visitCallInst(CallInst &I); 77 void visitInvokeInst(InvokeInst &I); 78 void visitReturnInst(ReturnInst &I); 79 void visitLoadInst(LoadInst &I); 80 void visitStoreInst(StoreInst &I); 81 void visitXor(BinaryOperator &I); 82 void visitSub(BinaryOperator &I); 83 void visitLShr(BinaryOperator &I); 84 void visitAShr(BinaryOperator &I); 85 void visitShl(BinaryOperator &I); 86 void visitSDiv(BinaryOperator &I); 87 void visitUDiv(BinaryOperator &I); 88 void visitSRem(BinaryOperator &I); 89 void visitURem(BinaryOperator &I); 90 void visitAllocaInst(AllocaInst &I); 91 void visitVAArgInst(VAArgInst &I); 92 void visitIndirectBrInst(IndirectBrInst &I); 93 void visitExtractElementInst(ExtractElementInst &I); 94 void visitInsertElementInst(InsertElementInst &I); 95 void visitUnreachableInst(UnreachableInst &I); 96 97 Value *findValue(Value *V, bool OffsetOk) const; 98 Value *findValueImpl(Value *V, bool OffsetOk, 99 SmallPtrSet<Value *, 4> &Visited) const; 100 101 public: 102 Module *Mod; 103 AliasAnalysis *AA; 104 DominatorTree *DT; 105 const DataLayout *DL; 106 TargetLibraryInfo *TLI; 107 108 std::string Messages; 109 raw_string_ostream MessagesStr; 110 111 static char ID; // Pass identification, replacement for typeid 112 Lint() : FunctionPass(ID), MessagesStr(Messages) { 113 initializeLintPass(*PassRegistry::getPassRegistry()); 114 } 115 116 bool runOnFunction(Function &F) override; 117 118 void getAnalysisUsage(AnalysisUsage &AU) const override { 119 AU.setPreservesAll(); 120 AU.addRequired<AliasAnalysis>(); 121 AU.addRequired<TargetLibraryInfo>(); 122 AU.addRequired<DominatorTreeWrapperPass>(); 123 } 124 void print(raw_ostream &O, const Module *M) const override {} 125 126 void WriteValue(const Value *V) { 127 if (!V) return; 128 if (isa<Instruction>(V)) { 129 MessagesStr << *V << '\n'; 130 } else { 131 V->printAsOperand(MessagesStr, true, Mod); 132 MessagesStr << '\n'; 133 } 134 } 135 136 // CheckFailed - A check failed, so print out the condition and the message 137 // that failed. This provides a nice place to put a breakpoint if you want 138 // to see why something is not correct. 139 void CheckFailed(const Twine &Message, 140 const Value *V1 = nullptr, const Value *V2 = nullptr, 141 const Value *V3 = nullptr, const Value *V4 = nullptr) { 142 MessagesStr << Message.str() << "\n"; 143 WriteValue(V1); 144 WriteValue(V2); 145 WriteValue(V3); 146 WriteValue(V4); 147 } 148 }; 149 } 150 151 char Lint::ID = 0; 152 INITIALIZE_PASS_BEGIN(Lint, "lint", "Statically lint-checks LLVM IR", 153 false, true) 154 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo) 155 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 156 INITIALIZE_AG_DEPENDENCY(AliasAnalysis) 157 INITIALIZE_PASS_END(Lint, "lint", "Statically lint-checks LLVM IR", 158 false, true) 159 160 // Assert - We know that cond should be true, if not print an error message. 161 #define Assert(C, M) \ 162 do { if (!(C)) { CheckFailed(M); return; } } while (0) 163 #define Assert1(C, M, V1) \ 164 do { if (!(C)) { CheckFailed(M, V1); return; } } while (0) 165 #define Assert2(C, M, V1, V2) \ 166 do { if (!(C)) { CheckFailed(M, V1, V2); return; } } while (0) 167 #define Assert3(C, M, V1, V2, V3) \ 168 do { if (!(C)) { CheckFailed(M, V1, V2, V3); return; } } while (0) 169 #define Assert4(C, M, V1, V2, V3, V4) \ 170 do { if (!(C)) { CheckFailed(M, V1, V2, V3, V4); return; } } while (0) 171 172 // Lint::run - This is the main Analysis entry point for a 173 // function. 174 // 175 bool Lint::runOnFunction(Function &F) { 176 Mod = F.getParent(); 177 AA = &getAnalysis<AliasAnalysis>(); 178 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 179 DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>(); 180 DL = DLP ? &DLP->getDataLayout() : nullptr; 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, nullptr, 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 = CS.arg_size(); 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 DL ? DL->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(), nullptr, 279 MemRef::Write); 280 visitMemoryReference(I, MCI->getSource(), AliasAnalysis::UnknownSize, 281 MCI->getAlignment(), nullptr, 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(), nullptr, 303 MemRef::Write); 304 visitMemoryReference(I, MMI->getSource(), AliasAnalysis::UnknownSize, 305 MMI->getAlignment(), nullptr, 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(), nullptr, 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, nullptr, MemRef::Read | MemRef::Write); 325 break; 326 case Intrinsic::vacopy: 327 visitMemoryReference(I, CS.getArgument(0), AliasAnalysis::UnknownSize, 328 0, nullptr, MemRef::Write); 329 visitMemoryReference(I, CS.getArgument(1), AliasAnalysis::UnknownSize, 330 0, nullptr, MemRef::Read); 331 break; 332 case Intrinsic::vaend: 333 visitMemoryReference(I, CS.getArgument(0), AliasAnalysis::UnknownSize, 334 0, nullptr, 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, nullptr, 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, DL)) { 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 (DL && !AI->isArrayAllocation() && ATy->isSized()) 428 BaseSize = DL->getTypeAllocSize(ATy); 429 BaseAlign = AI->getAlignment(); 430 if (DL && BaseAlign == 0 && ATy->isSized()) 431 BaseAlign = DL->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 (DL && GTy->isSized()) 438 BaseSize = DL->getTypeAllocSize(GTy); 439 BaseAlign = GV->getAlignment(); 440 if (DL && BaseAlign == 0 && GTy->isSized()) 441 BaseAlign = DL->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 (DL && Align == 0 && Ty && Ty->isSized()) 455 Align = DL->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, const DataLayout *DL) { 508 // Assume undef could be zero. 509 if (isa<UndefValue>(V)) 510 return true; 511 512 VectorType *VecTy = dyn_cast<VectorType>(V->getType()); 513 if (!VecTy) { 514 unsigned BitWidth = V->getType()->getIntegerBitWidth(); 515 APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0); 516 computeKnownBits(V, KnownZero, KnownOne, DL); 517 return KnownZero.isAllOnesValue(); 518 } 519 520 // Per-component check doesn't work with zeroinitializer 521 Constant *C = dyn_cast<Constant>(V); 522 if (!C) 523 return false; 524 525 if (C->isZeroValue()) 526 return true; 527 528 // For a vector, KnownZero will only be true if all values are zero, so check 529 // this per component 530 unsigned BitWidth = VecTy->getElementType()->getIntegerBitWidth(); 531 for (unsigned I = 0, N = VecTy->getNumElements(); I != N; ++I) { 532 Constant *Elem = C->getAggregateElement(I); 533 if (isa<UndefValue>(Elem)) 534 return true; 535 536 APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0); 537 computeKnownBits(Elem, KnownZero, KnownOne, DL); 538 if (KnownZero.isAllOnesValue()) 539 return true; 540 } 541 542 return false; 543 } 544 545 void Lint::visitSDiv(BinaryOperator &I) { 546 Assert1(!isZero(I.getOperand(1), DL), 547 "Undefined behavior: Division by zero", &I); 548 } 549 550 void Lint::visitUDiv(BinaryOperator &I) { 551 Assert1(!isZero(I.getOperand(1), DL), 552 "Undefined behavior: Division by zero", &I); 553 } 554 555 void Lint::visitSRem(BinaryOperator &I) { 556 Assert1(!isZero(I.getOperand(1), DL), 557 "Undefined behavior: Division by zero", &I); 558 } 559 560 void Lint::visitURem(BinaryOperator &I) { 561 Assert1(!isZero(I.getOperand(1), DL), 562 "Undefined behavior: Division by zero", &I); 563 } 564 565 void Lint::visitAllocaInst(AllocaInst &I) { 566 if (isa<ConstantInt>(I.getArraySize())) 567 // This isn't undefined behavior, it's just an obvious pessimization. 568 Assert1(&I.getParent()->getParent()->getEntryBlock() == I.getParent(), 569 "Pessimization: Static alloca outside of entry block", &I); 570 571 // TODO: Check for an unusual size (MSB set?) 572 } 573 574 void Lint::visitVAArgInst(VAArgInst &I) { 575 visitMemoryReference(I, I.getOperand(0), AliasAnalysis::UnknownSize, 0, 576 nullptr, MemRef::Read | MemRef::Write); 577 } 578 579 void Lint::visitIndirectBrInst(IndirectBrInst &I) { 580 visitMemoryReference(I, I.getAddress(), AliasAnalysis::UnknownSize, 0, 581 nullptr, MemRef::Branchee); 582 583 Assert1(I.getNumDestinations() != 0, 584 "Undefined behavior: indirectbr with no destinations", &I); 585 } 586 587 void Lint::visitExtractElementInst(ExtractElementInst &I) { 588 if (ConstantInt *CI = 589 dyn_cast<ConstantInt>(findValue(I.getIndexOperand(), 590 /*OffsetOk=*/false))) 591 Assert1(CI->getValue().ult(I.getVectorOperandType()->getNumElements()), 592 "Undefined result: extractelement index out of range", &I); 593 } 594 595 void Lint::visitInsertElementInst(InsertElementInst &I) { 596 if (ConstantInt *CI = 597 dyn_cast<ConstantInt>(findValue(I.getOperand(2), 598 /*OffsetOk=*/false))) 599 Assert1(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 Assert1(&I == I.getParent()->begin() || 606 std::prev(BasicBlock::iterator(&I))->mayHaveSideEffects(), 607 "Unusual: unreachable immediately preceded by instruction without " 608 "side effects", &I); 609 } 610 611 /// findValue - Look through bitcasts and simple memory reference patterns 612 /// to identify an equivalent, but more informative, value. If OffsetOk 613 /// is true, look through getelementptrs with non-zero offsets too. 614 /// 615 /// Most analysis passes don't require this logic, because instcombine 616 /// will simplify most of these kinds of things away. But it's a goal of 617 /// this Lint pass to be useful even on non-optimized IR. 618 Value *Lint::findValue(Value *V, bool OffsetOk) const { 619 SmallPtrSet<Value *, 4> Visited; 620 return findValueImpl(V, OffsetOk, Visited); 621 } 622 623 /// findValueImpl - Implementation helper for findValue. 624 Value *Lint::findValueImpl(Value *V, bool OffsetOk, 625 SmallPtrSet<Value *, 4> &Visited) const { 626 // Detect self-referential values. 627 if (!Visited.insert(V)) 628 return UndefValue::get(V->getType()); 629 630 // TODO: Look through sext or zext cast, when the result is known to 631 // be interpreted as signed or unsigned, respectively. 632 // TODO: Look through eliminable cast pairs. 633 // TODO: Look through calls with unique return values. 634 // TODO: Look through vector insert/extract/shuffle. 635 V = OffsetOk ? GetUnderlyingObject(V, DL) : V->stripPointerCasts(); 636 if (LoadInst *L = dyn_cast<LoadInst>(V)) { 637 BasicBlock::iterator BBI = L; 638 BasicBlock *BB = L->getParent(); 639 SmallPtrSet<BasicBlock *, 4> VisitedBlocks; 640 for (;;) { 641 if (!VisitedBlocks.insert(BB)) break; 642 if (Value *U = FindAvailableLoadedValue(L->getPointerOperand(), 643 BB, BBI, 6, AA)) 644 return findValueImpl(U, OffsetOk, Visited); 645 if (BBI != BB->begin()) break; 646 BB = BB->getUniquePredecessor(); 647 if (!BB) break; 648 BBI = BB->end(); 649 } 650 } else if (PHINode *PN = dyn_cast<PHINode>(V)) { 651 if (Value *W = PN->hasConstantValue()) 652 if (W != V) 653 return findValueImpl(W, OffsetOk, Visited); 654 } else if (CastInst *CI = dyn_cast<CastInst>(V)) { 655 if (CI->isNoopCast(DL)) 656 return findValueImpl(CI->getOperand(0), OffsetOk, Visited); 657 } else if (ExtractValueInst *Ex = dyn_cast<ExtractValueInst>(V)) { 658 if (Value *W = FindInsertedValue(Ex->getAggregateOperand(), 659 Ex->getIndices())) 660 if (W != V) 661 return findValueImpl(W, OffsetOk, Visited); 662 } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) { 663 // Same as above, but for ConstantExpr instead of Instruction. 664 if (Instruction::isCast(CE->getOpcode())) { 665 if (CastInst::isNoopCast(Instruction::CastOps(CE->getOpcode()), 666 CE->getOperand(0)->getType(), 667 CE->getType(), 668 DL ? DL->getIntPtrType(V->getType()) : 669 Type::getInt64Ty(V->getContext()))) 670 return findValueImpl(CE->getOperand(0), OffsetOk, Visited); 671 } else if (CE->getOpcode() == Instruction::ExtractValue) { 672 ArrayRef<unsigned> Indices = CE->getIndices(); 673 if (Value *W = FindInsertedValue(CE->getOperand(0), Indices)) 674 if (W != V) 675 return findValueImpl(W, OffsetOk, Visited); 676 } 677 } 678 679 // As a last resort, try SimplifyInstruction or constant folding. 680 if (Instruction *Inst = dyn_cast<Instruction>(V)) { 681 if (Value *W = SimplifyInstruction(Inst, DL, TLI, DT)) 682 return findValueImpl(W, OffsetOk, Visited); 683 } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) { 684 if (Value *W = ConstantFoldConstantExpression(CE, DL, TLI)) 685 if (W != V) 686 return findValueImpl(W, OffsetOk, Visited); 687 } 688 689 return V; 690 } 691 692 //===----------------------------------------------------------------------===// 693 // Implement the public interfaces to this file... 694 //===----------------------------------------------------------------------===// 695 696 FunctionPass *llvm::createLintPass() { 697 return new Lint(); 698 } 699 700 /// lintFunction - Check a function for errors, printing messages on stderr. 701 /// 702 void llvm::lintFunction(const Function &f) { 703 Function &F = const_cast<Function&>(f); 704 assert(!F.isDeclaration() && "Cannot lint external functions"); 705 706 FunctionPassManager FPM(F.getParent()); 707 Lint *V = new Lint(); 708 FPM.add(V); 709 FPM.run(F); 710 } 711 712 /// lintModule - Check a module for errors, printing messages on stderr. 713 /// 714 void llvm::lintModule(const Module &M) { 715 PassManager PM; 716 Lint *V = new Lint(); 717 PM.add(V); 718 PM.run(const_cast<Module&>(M)); 719 } 720
