Lint.cpp revision f3b8c7659979ff481e7a15fa3406b280e425cf0d
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/Passes.h" 38#include "llvm/Analysis/AliasAnalysis.h" 39#include "llvm/Analysis/InstructionSimplify.h" 40#include "llvm/Analysis/ConstantFolding.h" 41#include "llvm/Analysis/Dominators.h" 42#include "llvm/Analysis/Lint.h" 43#include "llvm/Analysis/Loads.h" 44#include "llvm/Analysis/ValueTracking.h" 45#include "llvm/Assembly/Writer.h" 46#include "llvm/Target/TargetData.h" 47#include "llvm/Pass.h" 48#include "llvm/PassManager.h" 49#include "llvm/IntrinsicInst.h" 50#include "llvm/Function.h" 51#include "llvm/Support/CallSite.h" 52#include "llvm/Support/Debug.h" 53#include "llvm/Support/InstVisitor.h" 54#include "llvm/Support/raw_ostream.h" 55#include "llvm/ADT/STLExtras.h" 56using namespace llvm; 57 58namespace { 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 const 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 TargetData *TD; 106 107 std::string Messages; 108 raw_string_ostream MessagesStr; 109 110 static char ID; // Pass identification, replacement for typeid 111 Lint() : FunctionPass(ID), MessagesStr(Messages) { 112 initializeLintPass(*PassRegistry::getPassRegistry()); 113 } 114 115 virtual bool runOnFunction(Function &F); 116 117 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 118 AU.setPreservesAll(); 119 AU.addRequired<AliasAnalysis>(); 120 AU.addRequired<DominatorTree>(); 121 } 122 virtual void print(raw_ostream &O, const Module *M) const {} 123 124 void WriteValue(const Value *V) { 125 if (!V) return; 126 if (isa<Instruction>(V)) { 127 MessagesStr << *V << '\n'; 128 } else { 129 WriteAsOperand(MessagesStr, V, true, Mod); 130 MessagesStr << '\n'; 131 } 132 } 133 134 // CheckFailed - A check failed, so print out the condition and the message 135 // that failed. This provides a nice place to put a breakpoint if you want 136 // to see why something is not correct. 137 void CheckFailed(const Twine &Message, 138 const Value *V1 = 0, const Value *V2 = 0, 139 const Value *V3 = 0, const Value *V4 = 0) { 140 MessagesStr << Message.str() << "\n"; 141 WriteValue(V1); 142 WriteValue(V2); 143 WriteValue(V3); 144 WriteValue(V4); 145 } 146 }; 147} 148 149char Lint::ID = 0; 150INITIALIZE_PASS_BEGIN(Lint, "lint", "Statically lint-checks LLVM IR", 151 false, true) 152INITIALIZE_PASS_DEPENDENCY(DominatorTree) 153INITIALIZE_AG_DEPENDENCY(AliasAnalysis) 154INITIALIZE_PASS_END(Lint, "lint", "Statically lint-checks LLVM IR", 155 false, true) 156 157// Assert - We know that cond should be true, if not print an error message. 158#define Assert(C, M) \ 159 do { if (!(C)) { CheckFailed(M); return; } } while (0) 160#define Assert1(C, M, V1) \ 161 do { if (!(C)) { CheckFailed(M, V1); return; } } while (0) 162#define Assert2(C, M, V1, V2) \ 163 do { if (!(C)) { CheckFailed(M, V1, V2); return; } } while (0) 164#define Assert3(C, M, V1, V2, V3) \ 165 do { if (!(C)) { CheckFailed(M, V1, V2, V3); return; } } while (0) 166#define Assert4(C, M, V1, V2, V3, V4) \ 167 do { if (!(C)) { CheckFailed(M, V1, V2, V3, V4); return; } } while (0) 168 169// Lint::run - This is the main Analysis entry point for a 170// function. 171// 172bool Lint::runOnFunction(Function &F) { 173 Mod = F.getParent(); 174 AA = &getAnalysis<AliasAnalysis>(); 175 DT = &getAnalysis<DominatorTree>(); 176 TD = getAnalysisIfAvailable<TargetData>(); 177 visit(F); 178 dbgs() << MessagesStr.str(); 179 Messages.clear(); 180 return false; 181} 182 183void Lint::visitFunction(Function &F) { 184 // This isn't undefined behavior, it's just a little unusual, and it's a 185 // fairly common mistake to neglect to name a function. 186 Assert1(F.hasName() || F.hasLocalLinkage(), 187 "Unusual: Unnamed function with non-local linkage", &F); 188 189 // TODO: Check for irreducible control flow. 190} 191 192void Lint::visitCallSite(CallSite CS) { 193 Instruction &I = *CS.getInstruction(); 194 Value *Callee = CS.getCalledValue(); 195 196 visitMemoryReference(I, Callee, AliasAnalysis::UnknownSize, 197 0, 0, MemRef::Callee); 198 199 if (Function *F = dyn_cast<Function>(findValue(Callee, /*OffsetOk=*/false))) { 200 Assert1(CS.getCallingConv() == F->getCallingConv(), 201 "Undefined behavior: Caller and callee calling convention differ", 202 &I); 203 204 const FunctionType *FT = F->getFunctionType(); 205 unsigned NumActualArgs = unsigned(CS.arg_end()-CS.arg_begin()); 206 207 Assert1(FT->isVarArg() ? 208 FT->getNumParams() <= NumActualArgs : 209 FT->getNumParams() == NumActualArgs, 210 "Undefined behavior: Call argument count mismatches callee " 211 "argument count", &I); 212 213 Assert1(FT->getReturnType() == I.getType(), 214 "Undefined behavior: Call return type mismatches " 215 "callee return type", &I); 216 217 // Check argument types (in case the callee was casted) and attributes. 218 // TODO: Verify that caller and callee attributes are compatible. 219 Function::arg_iterator PI = F->arg_begin(), PE = F->arg_end(); 220 CallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end(); 221 for (; AI != AE; ++AI) { 222 Value *Actual = *AI; 223 if (PI != PE) { 224 Argument *Formal = PI++; 225 Assert1(Formal->getType() == Actual->getType(), 226 "Undefined behavior: Call argument type mismatches " 227 "callee parameter type", &I); 228 229 // Check that noalias arguments don't alias other arguments. The 230 // AliasAnalysis API isn't expressive enough for what we really want 231 // to do. Known partial overlap is not distinguished from the case 232 // where nothing is known. 233 if (Formal->hasNoAliasAttr() && Actual->getType()->isPointerTy()) 234 for (CallSite::arg_iterator BI = CS.arg_begin(); BI != AE; ++BI) 235 Assert1(AI == BI || 236 !(*BI)->getType()->isPointerTy() || 237 AA->alias(*AI, *BI) != AliasAnalysis::MustAlias, 238 "Unusual: noalias argument aliases another argument", &I); 239 240 // Check that an sret argument points to valid memory. 241 if (Formal->hasStructRetAttr() && Actual->getType()->isPointerTy()) { 242 const Type *Ty = 243 cast<PointerType>(Formal->getType())->getElementType(); 244 visitMemoryReference(I, Actual, AA->getTypeStoreSize(Ty), 245 TD ? TD->getABITypeAlignment(Ty) : 0, 246 Ty, MemRef::Read | MemRef::Write); 247 } 248 } 249 } 250 } 251 252 if (CS.isCall() && cast<CallInst>(CS.getInstruction())->isTailCall()) 253 for (CallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end(); 254 AI != AE; ++AI) { 255 Value *Obj = findValue(*AI, /*OffsetOk=*/true); 256 Assert1(!isa<AllocaInst>(Obj), 257 "Undefined behavior: Call with \"tail\" keyword references " 258 "alloca", &I); 259 } 260 261 262 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(&I)) 263 switch (II->getIntrinsicID()) { 264 default: break; 265 266 // TODO: Check more intrinsics 267 268 case Intrinsic::memcpy: { 269 MemCpyInst *MCI = cast<MemCpyInst>(&I); 270 // TODO: If the size is known, use it. 271 visitMemoryReference(I, MCI->getDest(), AliasAnalysis::UnknownSize, 272 MCI->getAlignment(), 0, 273 MemRef::Write); 274 visitMemoryReference(I, MCI->getSource(), AliasAnalysis::UnknownSize, 275 MCI->getAlignment(), 0, 276 MemRef::Read); 277 278 // Check that the memcpy arguments don't overlap. The AliasAnalysis API 279 // isn't expressive enough for what we really want to do. Known partial 280 // overlap is not distinguished from the case where nothing is known. 281 uint64_t Size = 0; 282 if (const ConstantInt *Len = 283 dyn_cast<ConstantInt>(findValue(MCI->getLength(), 284 /*OffsetOk=*/false))) 285 if (Len->getValue().isIntN(32)) 286 Size = Len->getValue().getZExtValue(); 287 Assert1(AA->alias(MCI->getSource(), Size, MCI->getDest(), Size) != 288 AliasAnalysis::MustAlias, 289 "Undefined behavior: memcpy source and destination overlap", &I); 290 break; 291 } 292 case Intrinsic::memmove: { 293 MemMoveInst *MMI = cast<MemMoveInst>(&I); 294 // TODO: If the size is known, use it. 295 visitMemoryReference(I, MMI->getDest(), AliasAnalysis::UnknownSize, 296 MMI->getAlignment(), 0, 297 MemRef::Write); 298 visitMemoryReference(I, MMI->getSource(), AliasAnalysis::UnknownSize, 299 MMI->getAlignment(), 0, 300 MemRef::Read); 301 break; 302 } 303 case Intrinsic::memset: { 304 MemSetInst *MSI = cast<MemSetInst>(&I); 305 // TODO: If the size is known, use it. 306 visitMemoryReference(I, MSI->getDest(), AliasAnalysis::UnknownSize, 307 MSI->getAlignment(), 0, 308 MemRef::Write); 309 break; 310 } 311 312 case Intrinsic::vastart: 313 Assert1(I.getParent()->getParent()->isVarArg(), 314 "Undefined behavior: va_start called in a non-varargs function", 315 &I); 316 317 visitMemoryReference(I, CS.getArgument(0), AliasAnalysis::UnknownSize, 318 0, 0, MemRef::Read | MemRef::Write); 319 break; 320 case Intrinsic::vacopy: 321 visitMemoryReference(I, CS.getArgument(0), AliasAnalysis::UnknownSize, 322 0, 0, MemRef::Write); 323 visitMemoryReference(I, CS.getArgument(1), AliasAnalysis::UnknownSize, 324 0, 0, MemRef::Read); 325 break; 326 case Intrinsic::vaend: 327 visitMemoryReference(I, CS.getArgument(0), AliasAnalysis::UnknownSize, 328 0, 0, MemRef::Read | MemRef::Write); 329 break; 330 331 case Intrinsic::stackrestore: 332 // Stackrestore doesn't read or write memory, but it sets the 333 // stack pointer, which the compiler may read from or write to 334 // at any time, so check it for both readability and writeability. 335 visitMemoryReference(I, CS.getArgument(0), AliasAnalysis::UnknownSize, 336 0, 0, MemRef::Read | MemRef::Write); 337 break; 338 } 339} 340 341void Lint::visitCallInst(CallInst &I) { 342 return visitCallSite(&I); 343} 344 345void Lint::visitInvokeInst(InvokeInst &I) { 346 return visitCallSite(&I); 347} 348 349void Lint::visitReturnInst(ReturnInst &I) { 350 Function *F = I.getParent()->getParent(); 351 Assert1(!F->doesNotReturn(), 352 "Unusual: Return statement in function with noreturn attribute", 353 &I); 354 355 if (Value *V = I.getReturnValue()) { 356 Value *Obj = findValue(V, /*OffsetOk=*/true); 357 Assert1(!isa<AllocaInst>(Obj), 358 "Unusual: Returning alloca value", &I); 359 } 360} 361 362// TODO: Check that the reference is in bounds. 363// TODO: Check readnone/readonly function attributes. 364void Lint::visitMemoryReference(Instruction &I, 365 Value *Ptr, uint64_t Size, unsigned Align, 366 const Type *Ty, unsigned Flags) { 367 // If no memory is being referenced, it doesn't matter if the pointer 368 // is valid. 369 if (Size == 0) 370 return; 371 372 Value *UnderlyingObject = findValue(Ptr, /*OffsetOk=*/true); 373 Assert1(!isa<ConstantPointerNull>(UnderlyingObject), 374 "Undefined behavior: Null pointer dereference", &I); 375 Assert1(!isa<UndefValue>(UnderlyingObject), 376 "Undefined behavior: Undef pointer dereference", &I); 377 Assert1(!isa<ConstantInt>(UnderlyingObject) || 378 !cast<ConstantInt>(UnderlyingObject)->isAllOnesValue(), 379 "Unusual: All-ones pointer dereference", &I); 380 Assert1(!isa<ConstantInt>(UnderlyingObject) || 381 !cast<ConstantInt>(UnderlyingObject)->isOne(), 382 "Unusual: Address one pointer dereference", &I); 383 384 if (Flags & MemRef::Write) { 385 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(UnderlyingObject)) 386 Assert1(!GV->isConstant(), 387 "Undefined behavior: Write to read-only memory", &I); 388 Assert1(!isa<Function>(UnderlyingObject) && 389 !isa<BlockAddress>(UnderlyingObject), 390 "Undefined behavior: Write to text section", &I); 391 } 392 if (Flags & MemRef::Read) { 393 Assert1(!isa<Function>(UnderlyingObject), 394 "Unusual: Load from function body", &I); 395 Assert1(!isa<BlockAddress>(UnderlyingObject), 396 "Undefined behavior: Load from block address", &I); 397 } 398 if (Flags & MemRef::Callee) { 399 Assert1(!isa<BlockAddress>(UnderlyingObject), 400 "Undefined behavior: Call to block address", &I); 401 } 402 if (Flags & MemRef::Branchee) { 403 Assert1(!isa<Constant>(UnderlyingObject) || 404 isa<BlockAddress>(UnderlyingObject), 405 "Undefined behavior: Branch to non-blockaddress", &I); 406 } 407 408 if (TD) { 409 if (Align == 0 && Ty) Align = TD->getABITypeAlignment(Ty); 410 411 if (Align != 0) { 412 unsigned BitWidth = TD->getTypeSizeInBits(Ptr->getType()); 413 APInt Mask = APInt::getAllOnesValue(BitWidth), 414 KnownZero(BitWidth, 0), KnownOne(BitWidth, 0); 415 ComputeMaskedBits(Ptr, Mask, KnownZero, KnownOne, TD); 416 Assert1(!(KnownOne & APInt::getLowBitsSet(BitWidth, Log2_32(Align))), 417 "Undefined behavior: Memory reference address is misaligned", &I); 418 } 419 } 420} 421 422void Lint::visitLoadInst(LoadInst &I) { 423 visitMemoryReference(I, I.getPointerOperand(), 424 AA->getTypeStoreSize(I.getType()), I.getAlignment(), 425 I.getType(), MemRef::Read); 426} 427 428void Lint::visitStoreInst(StoreInst &I) { 429 visitMemoryReference(I, I.getPointerOperand(), 430 AA->getTypeStoreSize(I.getOperand(0)->getType()), 431 I.getAlignment(), 432 I.getOperand(0)->getType(), MemRef::Write); 433} 434 435void Lint::visitXor(BinaryOperator &I) { 436 Assert1(!isa<UndefValue>(I.getOperand(0)) || 437 !isa<UndefValue>(I.getOperand(1)), 438 "Undefined result: xor(undef, undef)", &I); 439} 440 441void Lint::visitSub(BinaryOperator &I) { 442 Assert1(!isa<UndefValue>(I.getOperand(0)) || 443 !isa<UndefValue>(I.getOperand(1)), 444 "Undefined result: sub(undef, undef)", &I); 445} 446 447void Lint::visitLShr(BinaryOperator &I) { 448 if (ConstantInt *CI = 449 dyn_cast<ConstantInt>(findValue(I.getOperand(1), /*OffsetOk=*/false))) 450 Assert1(CI->getValue().ult(cast<IntegerType>(I.getType())->getBitWidth()), 451 "Undefined result: Shift count out of range", &I); 452} 453 454void Lint::visitAShr(BinaryOperator &I) { 455 if (ConstantInt *CI = 456 dyn_cast<ConstantInt>(findValue(I.getOperand(1), /*OffsetOk=*/false))) 457 Assert1(CI->getValue().ult(cast<IntegerType>(I.getType())->getBitWidth()), 458 "Undefined result: Shift count out of range", &I); 459} 460 461void Lint::visitShl(BinaryOperator &I) { 462 if (ConstantInt *CI = 463 dyn_cast<ConstantInt>(findValue(I.getOperand(1), /*OffsetOk=*/false))) 464 Assert1(CI->getValue().ult(cast<IntegerType>(I.getType())->getBitWidth()), 465 "Undefined result: Shift count out of range", &I); 466} 467 468static bool isZero(Value *V, TargetData *TD) { 469 // Assume undef could be zero. 470 if (isa<UndefValue>(V)) return true; 471 472 unsigned BitWidth = cast<IntegerType>(V->getType())->getBitWidth(); 473 APInt Mask = APInt::getAllOnesValue(BitWidth), 474 KnownZero(BitWidth, 0), KnownOne(BitWidth, 0); 475 ComputeMaskedBits(V, Mask, KnownZero, KnownOne, TD); 476 return KnownZero.isAllOnesValue(); 477} 478 479void Lint::visitSDiv(BinaryOperator &I) { 480 Assert1(!isZero(I.getOperand(1), TD), 481 "Undefined behavior: Division by zero", &I); 482} 483 484void Lint::visitUDiv(BinaryOperator &I) { 485 Assert1(!isZero(I.getOperand(1), TD), 486 "Undefined behavior: Division by zero", &I); 487} 488 489void Lint::visitSRem(BinaryOperator &I) { 490 Assert1(!isZero(I.getOperand(1), TD), 491 "Undefined behavior: Division by zero", &I); 492} 493 494void Lint::visitURem(BinaryOperator &I) { 495 Assert1(!isZero(I.getOperand(1), TD), 496 "Undefined behavior: Division by zero", &I); 497} 498 499void Lint::visitAllocaInst(AllocaInst &I) { 500 if (isa<ConstantInt>(I.getArraySize())) 501 // This isn't undefined behavior, it's just an obvious pessimization. 502 Assert1(&I.getParent()->getParent()->getEntryBlock() == I.getParent(), 503 "Pessimization: Static alloca outside of entry block", &I); 504 505 // TODO: Check for an unusual size (MSB set?) 506} 507 508void Lint::visitVAArgInst(VAArgInst &I) { 509 visitMemoryReference(I, I.getOperand(0), AliasAnalysis::UnknownSize, 0, 0, 510 MemRef::Read | MemRef::Write); 511} 512 513void Lint::visitIndirectBrInst(IndirectBrInst &I) { 514 visitMemoryReference(I, I.getAddress(), AliasAnalysis::UnknownSize, 0, 0, 515 MemRef::Branchee); 516 517 Assert1(I.getNumDestinations() != 0, 518 "Undefined behavior: indirectbr with no destinations", &I); 519} 520 521void Lint::visitExtractElementInst(ExtractElementInst &I) { 522 if (ConstantInt *CI = 523 dyn_cast<ConstantInt>(findValue(I.getIndexOperand(), 524 /*OffsetOk=*/false))) 525 Assert1(CI->getValue().ult(I.getVectorOperandType()->getNumElements()), 526 "Undefined result: extractelement index out of range", &I); 527} 528 529void Lint::visitInsertElementInst(InsertElementInst &I) { 530 if (ConstantInt *CI = 531 dyn_cast<ConstantInt>(findValue(I.getOperand(2), 532 /*OffsetOk=*/false))) 533 Assert1(CI->getValue().ult(I.getType()->getNumElements()), 534 "Undefined result: insertelement index out of range", &I); 535} 536 537void Lint::visitUnreachableInst(UnreachableInst &I) { 538 // This isn't undefined behavior, it's merely suspicious. 539 Assert1(&I == I.getParent()->begin() || 540 prior(BasicBlock::iterator(&I))->mayHaveSideEffects(), 541 "Unusual: unreachable immediately preceded by instruction without " 542 "side effects", &I); 543} 544 545/// findValue - Look through bitcasts and simple memory reference patterns 546/// to identify an equivalent, but more informative, value. If OffsetOk 547/// is true, look through getelementptrs with non-zero offsets too. 548/// 549/// Most analysis passes don't require this logic, because instcombine 550/// will simplify most of these kinds of things away. But it's a goal of 551/// this Lint pass to be useful even on non-optimized IR. 552Value *Lint::findValue(Value *V, bool OffsetOk) const { 553 SmallPtrSet<Value *, 4> Visited; 554 return findValueImpl(V, OffsetOk, Visited); 555} 556 557/// findValueImpl - Implementation helper for findValue. 558Value *Lint::findValueImpl(Value *V, bool OffsetOk, 559 SmallPtrSet<Value *, 4> &Visited) const { 560 // Detect self-referential values. 561 if (!Visited.insert(V)) 562 return UndefValue::get(V->getType()); 563 564 // TODO: Look through sext or zext cast, when the result is known to 565 // be interpreted as signed or unsigned, respectively. 566 // TODO: Look through eliminable cast pairs. 567 // TODO: Look through calls with unique return values. 568 // TODO: Look through vector insert/extract/shuffle. 569 V = OffsetOk ? V->getUnderlyingObject() : V->stripPointerCasts(); 570 if (LoadInst *L = dyn_cast<LoadInst>(V)) { 571 BasicBlock::iterator BBI = L; 572 BasicBlock *BB = L->getParent(); 573 SmallPtrSet<BasicBlock *, 4> VisitedBlocks; 574 for (;;) { 575 if (!VisitedBlocks.insert(BB)) break; 576 if (Value *U = FindAvailableLoadedValue(L->getPointerOperand(), 577 BB, BBI, 6, AA)) 578 return findValueImpl(U, OffsetOk, Visited); 579 if (BBI != BB->begin()) break; 580 BB = BB->getUniquePredecessor(); 581 if (!BB) break; 582 BBI = BB->end(); 583 } 584 } else if (PHINode *PN = dyn_cast<PHINode>(V)) { 585 if (Value *W = PN->hasConstantValue(DT)) 586 return findValueImpl(W, OffsetOk, Visited); 587 } else if (CastInst *CI = dyn_cast<CastInst>(V)) { 588 if (CI->isNoopCast(TD ? TD->getIntPtrType(V->getContext()) : 589 Type::getInt64Ty(V->getContext()))) 590 return findValueImpl(CI->getOperand(0), OffsetOk, Visited); 591 } else if (ExtractValueInst *Ex = dyn_cast<ExtractValueInst>(V)) { 592 if (Value *W = FindInsertedValue(Ex->getAggregateOperand(), 593 Ex->idx_begin(), 594 Ex->idx_end())) 595 if (W != V) 596 return findValueImpl(W, OffsetOk, Visited); 597 } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) { 598 // Same as above, but for ConstantExpr instead of Instruction. 599 if (Instruction::isCast(CE->getOpcode())) { 600 if (CastInst::isNoopCast(Instruction::CastOps(CE->getOpcode()), 601 CE->getOperand(0)->getType(), 602 CE->getType(), 603 TD ? TD->getIntPtrType(V->getContext()) : 604 Type::getInt64Ty(V->getContext()))) 605 return findValueImpl(CE->getOperand(0), OffsetOk, Visited); 606 } else if (CE->getOpcode() == Instruction::ExtractValue) { 607 const SmallVector<unsigned, 4> &Indices = CE->getIndices(); 608 if (Value *W = FindInsertedValue(CE->getOperand(0), 609 Indices.begin(), 610 Indices.end())) 611 if (W != V) 612 return findValueImpl(W, OffsetOk, Visited); 613 } 614 } 615 616 // As a last resort, try SimplifyInstruction or constant folding. 617 if (Instruction *Inst = dyn_cast<Instruction>(V)) { 618 if (Value *W = SimplifyInstruction(Inst, TD)) 619 if (W != Inst) 620 return findValueImpl(W, OffsetOk, Visited); 621 } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) { 622 if (Value *W = ConstantFoldConstantExpression(CE, TD)) 623 if (W != V) 624 return findValueImpl(W, OffsetOk, Visited); 625 } 626 627 return V; 628} 629 630//===----------------------------------------------------------------------===// 631// Implement the public interfaces to this file... 632//===----------------------------------------------------------------------===// 633 634FunctionPass *llvm::createLintPass() { 635 return new Lint(); 636} 637 638/// lintFunction - Check a function for errors, printing messages on stderr. 639/// 640void llvm::lintFunction(const Function &f) { 641 Function &F = const_cast<Function&>(f); 642 assert(!F.isDeclaration() && "Cannot lint external functions"); 643 644 FunctionPassManager FPM(F.getParent()); 645 Lint *V = new Lint(); 646 FPM.add(V); 647 FPM.run(F); 648} 649 650/// lintModule - Check a module for errors, printing messages on stderr. 651/// 652void llvm::lintModule(const Module &M) { 653 PassManager PM; 654 Lint *V = new Lint(); 655 PM.add(V); 656 PM.run(const_cast<Module&>(M)); 657} 658