LLVM API Documentation

Lint.cpp
Go to the documentation of this file.
00001 //===-- Lint.cpp - Check for common errors in LLVM IR ---------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This pass statically checks for common and easily-identified constructs
00011 // which produce undefined or likely unintended behavior in LLVM IR.
00012 //
00013 // It is not a guarantee of correctness, in two ways. First, it isn't
00014 // comprehensive. There are checks which could be done statically which are
00015 // not yet implemented. Some of these are indicated by TODO comments, but
00016 // those aren't comprehensive either. Second, many conditions cannot be
00017 // checked statically. This pass does no dynamic instrumentation, so it
00018 // can't check for all possible problems.
00019 //
00020 // Another limitation is that it assumes all code will be executed. A store
00021 // through a null pointer in a basic block which is never reached is harmless,
00022 // but this pass will warn about it anyway. This is the main reason why most
00023 // of these checks live here instead of in the Verifier pass.
00024 //
00025 // Optimization passes may make conditions that this pass checks for more or
00026 // less obvious. If an optimization pass appears to be introducing a warning,
00027 // it may be that the optimization pass is merely exposing an existing
00028 // condition in the code.
00029 //
00030 // This code may be run before instcombine. In many cases, instcombine checks
00031 // for the same kinds of things and turns instructions with undefined behavior
00032 // into unreachable (or equivalent). Because of this, this pass makes some
00033 // effort to look through bitcasts and so on.
00034 //
00035 //===----------------------------------------------------------------------===//
00036 
00037 #include "llvm/Analysis/Lint.h"
00038 #include "llvm/ADT/STLExtras.h"
00039 #include "llvm/Analysis/AliasAnalysis.h"
00040 #include "llvm/Analysis/ConstantFolding.h"
00041 #include "llvm/Analysis/InstructionSimplify.h"
00042 #include "llvm/Analysis/Loads.h"
00043 #include "llvm/Analysis/Passes.h"
00044 #include "llvm/Analysis/ValueTracking.h"
00045 #include "llvm/IR/CallSite.h"
00046 #include "llvm/IR/DataLayout.h"
00047 #include "llvm/IR/Dominators.h"
00048 #include "llvm/IR/Function.h"
00049 #include "llvm/IR/InstVisitor.h"
00050 #include "llvm/IR/IntrinsicInst.h"
00051 #include "llvm/Pass.h"
00052 #include "llvm/PassManager.h"
00053 #include "llvm/Support/Debug.h"
00054 #include "llvm/Support/raw_ostream.h"
00055 #include "llvm/Target/TargetLibraryInfo.h"
00056 using namespace llvm;
00057 
00058 namespace {
00059   namespace MemRef {
00060     static unsigned Read     = 1;
00061     static unsigned Write    = 2;
00062     static unsigned Callee   = 4;
00063     static unsigned Branchee = 8;
00064   }
00065 
00066   class Lint : public FunctionPass, public InstVisitor<Lint> {
00067     friend class InstVisitor<Lint>;
00068 
00069     void visitFunction(Function &F);
00070 
00071     void visitCallSite(CallSite CS);
00072     void visitMemoryReference(Instruction &I, Value *Ptr,
00073                               uint64_t Size, unsigned Align,
00074                               Type *Ty, unsigned Flags);
00075 
00076     void visitCallInst(CallInst &I);
00077     void visitInvokeInst(InvokeInst &I);
00078     void visitReturnInst(ReturnInst &I);
00079     void visitLoadInst(LoadInst &I);
00080     void visitStoreInst(StoreInst &I);
00081     void visitXor(BinaryOperator &I);
00082     void visitSub(BinaryOperator &I);
00083     void visitLShr(BinaryOperator &I);
00084     void visitAShr(BinaryOperator &I);
00085     void visitShl(BinaryOperator &I);
00086     void visitSDiv(BinaryOperator &I);
00087     void visitUDiv(BinaryOperator &I);
00088     void visitSRem(BinaryOperator &I);
00089     void visitURem(BinaryOperator &I);
00090     void visitAllocaInst(AllocaInst &I);
00091     void visitVAArgInst(VAArgInst &I);
00092     void visitIndirectBrInst(IndirectBrInst &I);
00093     void visitExtractElementInst(ExtractElementInst &I);
00094     void visitInsertElementInst(InsertElementInst &I);
00095     void visitUnreachableInst(UnreachableInst &I);
00096 
00097     Value *findValue(Value *V, bool OffsetOk) const;
00098     Value *findValueImpl(Value *V, bool OffsetOk,
00099                          SmallPtrSet<Value *, 4> &Visited) const;
00100 
00101   public:
00102     Module *Mod;
00103     AliasAnalysis *AA;
00104     DominatorTree *DT;
00105     const DataLayout *DL;
00106     TargetLibraryInfo *TLI;
00107 
00108     std::string Messages;
00109     raw_string_ostream MessagesStr;
00110 
00111     static char ID; // Pass identification, replacement for typeid
00112     Lint() : FunctionPass(ID), MessagesStr(Messages) {
00113       initializeLintPass(*PassRegistry::getPassRegistry());
00114     }
00115 
00116     bool runOnFunction(Function &F) override;
00117 
00118     void getAnalysisUsage(AnalysisUsage &AU) const override {
00119       AU.setPreservesAll();
00120       AU.addRequired<AliasAnalysis>();
00121       AU.addRequired<TargetLibraryInfo>();
00122       AU.addRequired<DominatorTreeWrapperPass>();
00123     }
00124     void print(raw_ostream &O, const Module *M) const override {}
00125 
00126     void WriteValue(const Value *V) {
00127       if (!V) return;
00128       if (isa<Instruction>(V)) {
00129         MessagesStr << *V << '\n';
00130       } else {
00131         V->printAsOperand(MessagesStr, true, Mod);
00132         MessagesStr << '\n';
00133       }
00134     }
00135 
00136     // CheckFailed - A check failed, so print out the condition and the message
00137     // that failed.  This provides a nice place to put a breakpoint if you want
00138     // to see why something is not correct.
00139     void CheckFailed(const Twine &Message,
00140                      const Value *V1 = nullptr, const Value *V2 = nullptr,
00141                      const Value *V3 = nullptr, const Value *V4 = nullptr) {
00142       MessagesStr << Message.str() << "\n";
00143       WriteValue(V1);
00144       WriteValue(V2);
00145       WriteValue(V3);
00146       WriteValue(V4);
00147     }
00148   };
00149 }
00150 
00151 char Lint::ID = 0;
00152 INITIALIZE_PASS_BEGIN(Lint, "lint", "Statically lint-checks LLVM IR",
00153                       false, true)
00154 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
00155 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
00156 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
00157 INITIALIZE_PASS_END(Lint, "lint", "Statically lint-checks LLVM IR",
00158                     false, true)
00159 
00160 // Assert - We know that cond should be true, if not print an error message.
00161 #define Assert(C, M) \
00162     do { if (!(C)) { CheckFailed(M); return; } } while (0)
00163 #define Assert1(C, M, V1) \
00164     do { if (!(C)) { CheckFailed(M, V1); return; } } while (0)
00165 #define Assert2(C, M, V1, V2) \
00166     do { if (!(C)) { CheckFailed(M, V1, V2); return; } } while (0)
00167 #define Assert3(C, M, V1, V2, V3) \
00168     do { if (!(C)) { CheckFailed(M, V1, V2, V3); return; } } while (0)
00169 #define Assert4(C, M, V1, V2, V3, V4) \
00170     do { if (!(C)) { CheckFailed(M, V1, V2, V3, V4); return; } } while (0)
00171 
00172 // Lint::run - This is the main Analysis entry point for a
00173 // function.
00174 //
00175 bool Lint::runOnFunction(Function &F) {
00176   Mod = F.getParent();
00177   AA = &getAnalysis<AliasAnalysis>();
00178   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
00179   DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
00180   DL = DLP ? &DLP->getDataLayout() : nullptr;
00181   TLI = &getAnalysis<TargetLibraryInfo>();
00182   visit(F);
00183   dbgs() << MessagesStr.str();
00184   Messages.clear();
00185   return false;
00186 }
00187 
00188 void Lint::visitFunction(Function &F) {
00189   // This isn't undefined behavior, it's just a little unusual, and it's a
00190   // fairly common mistake to neglect to name a function.
00191   Assert1(F.hasName() || F.hasLocalLinkage(),
00192           "Unusual: Unnamed function with non-local linkage", &F);
00193 
00194   // TODO: Check for irreducible control flow.
00195 }
00196 
00197 void Lint::visitCallSite(CallSite CS) {
00198   Instruction &I = *CS.getInstruction();
00199   Value *Callee = CS.getCalledValue();
00200 
00201   visitMemoryReference(I, Callee, AliasAnalysis::UnknownSize,
00202                        0, nullptr, MemRef::Callee);
00203 
00204   if (Function *F = dyn_cast<Function>(findValue(Callee, /*OffsetOk=*/false))) {
00205     Assert1(CS.getCallingConv() == F->getCallingConv(),
00206             "Undefined behavior: Caller and callee calling convention differ",
00207             &I);
00208 
00209     FunctionType *FT = F->getFunctionType();
00210     unsigned NumActualArgs = CS.arg_size();
00211 
00212     Assert1(FT->isVarArg() ?
00213               FT->getNumParams() <= NumActualArgs :
00214               FT->getNumParams() == NumActualArgs,
00215             "Undefined behavior: Call argument count mismatches callee "
00216             "argument count", &I);
00217 
00218     Assert1(FT->getReturnType() == I.getType(),
00219             "Undefined behavior: Call return type mismatches "
00220             "callee return type", &I);
00221 
00222     // Check argument types (in case the callee was casted) and attributes.
00223     // TODO: Verify that caller and callee attributes are compatible.
00224     Function::arg_iterator PI = F->arg_begin(), PE = F->arg_end();
00225     CallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end();
00226     for (; AI != AE; ++AI) {
00227       Value *Actual = *AI;
00228       if (PI != PE) {
00229         Argument *Formal = PI++;
00230         Assert1(Formal->getType() == Actual->getType(),
00231                 "Undefined behavior: Call argument type mismatches "
00232                 "callee parameter type", &I);
00233 
00234         // Check that noalias arguments don't alias other arguments. This is
00235         // not fully precise because we don't know the sizes of the dereferenced
00236         // memory regions.
00237         if (Formal->hasNoAliasAttr() && Actual->getType()->isPointerTy())
00238           for (CallSite::arg_iterator BI = CS.arg_begin(); BI != AE; ++BI)
00239             if (AI != BI && (*BI)->getType()->isPointerTy()) {
00240               AliasAnalysis::AliasResult Result = AA->alias(*AI, *BI);
00241               Assert1(Result != AliasAnalysis::MustAlias &&
00242                       Result != AliasAnalysis::PartialAlias,
00243                       "Unusual: noalias argument aliases another argument", &I);
00244             }
00245 
00246         // Check that an sret argument points to valid memory.
00247         if (Formal->hasStructRetAttr() && Actual->getType()->isPointerTy()) {
00248           Type *Ty =
00249             cast<PointerType>(Formal->getType())->getElementType();
00250           visitMemoryReference(I, Actual, AA->getTypeStoreSize(Ty),
00251                                DL ? DL->getABITypeAlignment(Ty) : 0,
00252                                Ty, MemRef::Read | MemRef::Write);
00253         }
00254       }
00255     }
00256   }
00257 
00258   if (CS.isCall() && cast<CallInst>(CS.getInstruction())->isTailCall())
00259     for (CallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end();
00260          AI != AE; ++AI) {
00261       Value *Obj = findValue(*AI, /*OffsetOk=*/true);
00262       Assert1(!isa<AllocaInst>(Obj),
00263               "Undefined behavior: Call with \"tail\" keyword references "
00264               "alloca", &I);
00265     }
00266 
00267 
00268   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(&I))
00269     switch (II->getIntrinsicID()) {
00270     default: break;
00271 
00272     // TODO: Check more intrinsics
00273 
00274     case Intrinsic::memcpy: {
00275       MemCpyInst *MCI = cast<MemCpyInst>(&I);
00276       // TODO: If the size is known, use it.
00277       visitMemoryReference(I, MCI->getDest(), AliasAnalysis::UnknownSize,
00278                            MCI->getAlignment(), nullptr,
00279                            MemRef::Write);
00280       visitMemoryReference(I, MCI->getSource(), AliasAnalysis::UnknownSize,
00281                            MCI->getAlignment(), nullptr,
00282                            MemRef::Read);
00283 
00284       // Check that the memcpy arguments don't overlap. The AliasAnalysis API
00285       // isn't expressive enough for what we really want to do. Known partial
00286       // overlap is not distinguished from the case where nothing is known.
00287       uint64_t Size = 0;
00288       if (const ConstantInt *Len =
00289             dyn_cast<ConstantInt>(findValue(MCI->getLength(),
00290                                             /*OffsetOk=*/false)))
00291         if (Len->getValue().isIntN(32))
00292           Size = Len->getValue().getZExtValue();
00293       Assert1(AA->alias(MCI->getSource(), Size, MCI->getDest(), Size) !=
00294               AliasAnalysis::MustAlias,
00295               "Undefined behavior: memcpy source and destination overlap", &I);
00296       break;
00297     }
00298     case Intrinsic::memmove: {
00299       MemMoveInst *MMI = cast<MemMoveInst>(&I);
00300       // TODO: If the size is known, use it.
00301       visitMemoryReference(I, MMI->getDest(), AliasAnalysis::UnknownSize,
00302                            MMI->getAlignment(), nullptr,
00303                            MemRef::Write);
00304       visitMemoryReference(I, MMI->getSource(), AliasAnalysis::UnknownSize,
00305                            MMI->getAlignment(), nullptr,
00306                            MemRef::Read);
00307       break;
00308     }
00309     case Intrinsic::memset: {
00310       MemSetInst *MSI = cast<MemSetInst>(&I);
00311       // TODO: If the size is known, use it.
00312       visitMemoryReference(I, MSI->getDest(), AliasAnalysis::UnknownSize,
00313                            MSI->getAlignment(), nullptr,
00314                            MemRef::Write);
00315       break;
00316     }
00317 
00318     case Intrinsic::vastart:
00319       Assert1(I.getParent()->getParent()->isVarArg(),
00320               "Undefined behavior: va_start called in a non-varargs function",
00321               &I);
00322 
00323       visitMemoryReference(I, CS.getArgument(0), AliasAnalysis::UnknownSize,
00324                            0, nullptr, MemRef::Read | MemRef::Write);
00325       break;
00326     case Intrinsic::vacopy:
00327       visitMemoryReference(I, CS.getArgument(0), AliasAnalysis::UnknownSize,
00328                            0, nullptr, MemRef::Write);
00329       visitMemoryReference(I, CS.getArgument(1), AliasAnalysis::UnknownSize,
00330                            0, nullptr, MemRef::Read);
00331       break;
00332     case Intrinsic::vaend:
00333       visitMemoryReference(I, CS.getArgument(0), AliasAnalysis::UnknownSize,
00334                            0, nullptr, MemRef::Read | MemRef::Write);
00335       break;
00336 
00337     case Intrinsic::stackrestore:
00338       // Stackrestore doesn't read or write memory, but it sets the
00339       // stack pointer, which the compiler may read from or write to
00340       // at any time, so check it for both readability and writeability.
00341       visitMemoryReference(I, CS.getArgument(0), AliasAnalysis::UnknownSize,
00342                            0, nullptr, MemRef::Read | MemRef::Write);
00343       break;
00344     }
00345 }
00346 
00347 void Lint::visitCallInst(CallInst &I) {
00348   return visitCallSite(&I);
00349 }
00350 
00351 void Lint::visitInvokeInst(InvokeInst &I) {
00352   return visitCallSite(&I);
00353 }
00354 
00355 void Lint::visitReturnInst(ReturnInst &I) {
00356   Function *F = I.getParent()->getParent();
00357   Assert1(!F->doesNotReturn(),
00358           "Unusual: Return statement in function with noreturn attribute",
00359           &I);
00360 
00361   if (Value *V = I.getReturnValue()) {
00362     Value *Obj = findValue(V, /*OffsetOk=*/true);
00363     Assert1(!isa<AllocaInst>(Obj),
00364             "Unusual: Returning alloca value", &I);
00365   }
00366 }
00367 
00368 // TODO: Check that the reference is in bounds.
00369 // TODO: Check readnone/readonly function attributes.
00370 void Lint::visitMemoryReference(Instruction &I,
00371                                 Value *Ptr, uint64_t Size, unsigned Align,
00372                                 Type *Ty, unsigned Flags) {
00373   // If no memory is being referenced, it doesn't matter if the pointer
00374   // is valid.
00375   if (Size == 0)
00376     return;
00377 
00378   Value *UnderlyingObject = findValue(Ptr, /*OffsetOk=*/true);
00379   Assert1(!isa<ConstantPointerNull>(UnderlyingObject),
00380           "Undefined behavior: Null pointer dereference", &I);
00381   Assert1(!isa<UndefValue>(UnderlyingObject),
00382           "Undefined behavior: Undef pointer dereference", &I);
00383   Assert1(!isa<ConstantInt>(UnderlyingObject) ||
00384           !cast<ConstantInt>(UnderlyingObject)->isAllOnesValue(),
00385           "Unusual: All-ones pointer dereference", &I);
00386   Assert1(!isa<ConstantInt>(UnderlyingObject) ||
00387           !cast<ConstantInt>(UnderlyingObject)->isOne(),
00388           "Unusual: Address one pointer dereference", &I);
00389 
00390   if (Flags & MemRef::Write) {
00391     if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(UnderlyingObject))
00392       Assert1(!GV->isConstant(),
00393               "Undefined behavior: Write to read-only memory", &I);
00394     Assert1(!isa<Function>(UnderlyingObject) &&
00395             !isa<BlockAddress>(UnderlyingObject),
00396             "Undefined behavior: Write to text section", &I);
00397   }
00398   if (Flags & MemRef::Read) {
00399     Assert1(!isa<Function>(UnderlyingObject),
00400             "Unusual: Load from function body", &I);
00401     Assert1(!isa<BlockAddress>(UnderlyingObject),
00402             "Undefined behavior: Load from block address", &I);
00403   }
00404   if (Flags & MemRef::Callee) {
00405     Assert1(!isa<BlockAddress>(UnderlyingObject),
00406             "Undefined behavior: Call to block address", &I);
00407   }
00408   if (Flags & MemRef::Branchee) {
00409     Assert1(!isa<Constant>(UnderlyingObject) ||
00410             isa<BlockAddress>(UnderlyingObject),
00411             "Undefined behavior: Branch to non-blockaddress", &I);
00412   }
00413 
00414   // Check for buffer overflows and misalignment.
00415   // Only handles memory references that read/write something simple like an
00416   // alloca instruction or a global variable.
00417   int64_t Offset = 0;
00418   if (Value *Base = GetPointerBaseWithConstantOffset(Ptr, Offset, DL)) {
00419     // OK, so the access is to a constant offset from Ptr.  Check that Ptr is
00420     // something we can handle and if so extract the size of this base object
00421     // along with its alignment.
00422     uint64_t BaseSize = AliasAnalysis::UnknownSize;
00423     unsigned BaseAlign = 0;
00424 
00425     if (AllocaInst *AI = dyn_cast<AllocaInst>(Base)) {
00426       Type *ATy = AI->getAllocatedType();
00427       if (DL && !AI->isArrayAllocation() && ATy->isSized())
00428         BaseSize = DL->getTypeAllocSize(ATy);
00429       BaseAlign = AI->getAlignment();
00430       if (DL && BaseAlign == 0 && ATy->isSized())
00431         BaseAlign = DL->getABITypeAlignment(ATy);
00432     } else if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Base)) {
00433       // If the global may be defined differently in another compilation unit
00434       // then don't warn about funky memory accesses.
00435       if (GV->hasDefinitiveInitializer()) {
00436         Type *GTy = GV->getType()->getElementType();
00437         if (DL && GTy->isSized())
00438           BaseSize = DL->getTypeAllocSize(GTy);
00439         BaseAlign = GV->getAlignment();
00440         if (DL && BaseAlign == 0 && GTy->isSized())
00441           BaseAlign = DL->getABITypeAlignment(GTy);
00442       }
00443     }
00444 
00445     // Accesses from before the start or after the end of the object are not
00446     // defined.
00447     Assert1(Size == AliasAnalysis::UnknownSize ||
00448             BaseSize == AliasAnalysis::UnknownSize ||
00449             (Offset >= 0 && Offset + Size <= BaseSize),
00450             "Undefined behavior: Buffer overflow", &I);
00451 
00452     // Accesses that say that the memory is more aligned than it is are not
00453     // defined.
00454     if (DL && Align == 0 && Ty && Ty->isSized())
00455       Align = DL->getABITypeAlignment(Ty);
00456     Assert1(!BaseAlign || Align <= MinAlign(BaseAlign, Offset),
00457             "Undefined behavior: Memory reference address is misaligned", &I);
00458   }
00459 }
00460 
00461 void Lint::visitLoadInst(LoadInst &I) {
00462   visitMemoryReference(I, I.getPointerOperand(),
00463                        AA->getTypeStoreSize(I.getType()), I.getAlignment(),
00464                        I.getType(), MemRef::Read);
00465 }
00466 
00467 void Lint::visitStoreInst(StoreInst &I) {
00468   visitMemoryReference(I, I.getPointerOperand(),
00469                        AA->getTypeStoreSize(I.getOperand(0)->getType()),
00470                        I.getAlignment(),
00471                        I.getOperand(0)->getType(), MemRef::Write);
00472 }
00473 
00474 void Lint::visitXor(BinaryOperator &I) {
00475   Assert1(!isa<UndefValue>(I.getOperand(0)) ||
00476           !isa<UndefValue>(I.getOperand(1)),
00477           "Undefined result: xor(undef, undef)", &I);
00478 }
00479 
00480 void Lint::visitSub(BinaryOperator &I) {
00481   Assert1(!isa<UndefValue>(I.getOperand(0)) ||
00482           !isa<UndefValue>(I.getOperand(1)),
00483           "Undefined result: sub(undef, undef)", &I);
00484 }
00485 
00486 void Lint::visitLShr(BinaryOperator &I) {
00487   if (ConstantInt *CI =
00488         dyn_cast<ConstantInt>(findValue(I.getOperand(1), /*OffsetOk=*/false)))
00489     Assert1(CI->getValue().ult(cast<IntegerType>(I.getType())->getBitWidth()),
00490             "Undefined result: Shift count out of range", &I);
00491 }
00492 
00493 void Lint::visitAShr(BinaryOperator &I) {
00494   if (ConstantInt *CI =
00495         dyn_cast<ConstantInt>(findValue(I.getOperand(1), /*OffsetOk=*/false)))
00496     Assert1(CI->getValue().ult(cast<IntegerType>(I.getType())->getBitWidth()),
00497             "Undefined result: Shift count out of range", &I);
00498 }
00499 
00500 void Lint::visitShl(BinaryOperator &I) {
00501   if (ConstantInt *CI =
00502         dyn_cast<ConstantInt>(findValue(I.getOperand(1), /*OffsetOk=*/false)))
00503     Assert1(CI->getValue().ult(cast<IntegerType>(I.getType())->getBitWidth()),
00504             "Undefined result: Shift count out of range", &I);
00505 }
00506 
00507 static bool isZero(Value *V, const DataLayout *DL) {
00508   // Assume undef could be zero.
00509   if (isa<UndefValue>(V))
00510     return true;
00511 
00512   VectorType *VecTy = dyn_cast<VectorType>(V->getType());
00513   if (!VecTy) {
00514     unsigned BitWidth = V->getType()->getIntegerBitWidth();
00515     APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0);
00516     ComputeMaskedBits(V, KnownZero, KnownOne, DL);
00517     return KnownZero.isAllOnesValue();
00518   }
00519 
00520   // Per-component check doesn't work with zeroinitializer
00521   Constant *C = dyn_cast<Constant>(V);
00522   if (!C)
00523     return false;
00524 
00525   if (C->isZeroValue())
00526     return true;
00527 
00528   // For a vector, KnownZero will only be true if all values are zero, so check
00529   // this per component
00530   unsigned BitWidth = VecTy->getElementType()->getIntegerBitWidth();
00531   for (unsigned I = 0, N = VecTy->getNumElements(); I != N; ++I) {
00532     Constant *Elem = C->getAggregateElement(I);
00533     if (isa<UndefValue>(Elem))
00534       return true;
00535 
00536     APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0);
00537     ComputeMaskedBits(Elem, KnownZero, KnownOne, DL);
00538     if (KnownZero.isAllOnesValue())
00539       return true;
00540   }
00541 
00542   return false;
00543 }
00544 
00545 void Lint::visitSDiv(BinaryOperator &I) {
00546   Assert1(!isZero(I.getOperand(1), DL),
00547           "Undefined behavior: Division by zero", &I);
00548 }
00549 
00550 void Lint::visitUDiv(BinaryOperator &I) {
00551   Assert1(!isZero(I.getOperand(1), DL),
00552           "Undefined behavior: Division by zero", &I);
00553 }
00554 
00555 void Lint::visitSRem(BinaryOperator &I) {
00556   Assert1(!isZero(I.getOperand(1), DL),
00557           "Undefined behavior: Division by zero", &I);
00558 }
00559 
00560 void Lint::visitURem(BinaryOperator &I) {
00561   Assert1(!isZero(I.getOperand(1), DL),
00562           "Undefined behavior: Division by zero", &I);
00563 }
00564 
00565 void Lint::visitAllocaInst(AllocaInst &I) {
00566   if (isa<ConstantInt>(I.getArraySize()))
00567     // This isn't undefined behavior, it's just an obvious pessimization.
00568     Assert1(&I.getParent()->getParent()->getEntryBlock() == I.getParent(),
00569             "Pessimization: Static alloca outside of entry block", &I);
00570 
00571   // TODO: Check for an unusual size (MSB set?)
00572 }
00573 
00574 void Lint::visitVAArgInst(VAArgInst &I) {
00575   visitMemoryReference(I, I.getOperand(0), AliasAnalysis::UnknownSize, 0,
00576                        nullptr, MemRef::Read | MemRef::Write);
00577 }
00578 
00579 void Lint::visitIndirectBrInst(IndirectBrInst &I) {
00580   visitMemoryReference(I, I.getAddress(), AliasAnalysis::UnknownSize, 0,
00581                        nullptr, MemRef::Branchee);
00582 
00583   Assert1(I.getNumDestinations() != 0,
00584           "Undefined behavior: indirectbr with no destinations", &I);
00585 }
00586 
00587 void Lint::visitExtractElementInst(ExtractElementInst &I) {
00588   if (ConstantInt *CI =
00589         dyn_cast<ConstantInt>(findValue(I.getIndexOperand(),
00590                                         /*OffsetOk=*/false)))
00591     Assert1(CI->getValue().ult(I.getVectorOperandType()->getNumElements()),
00592             "Undefined result: extractelement index out of range", &I);
00593 }
00594 
00595 void Lint::visitInsertElementInst(InsertElementInst &I) {
00596   if (ConstantInt *CI =
00597         dyn_cast<ConstantInt>(findValue(I.getOperand(2),
00598                                         /*OffsetOk=*/false)))
00599     Assert1(CI->getValue().ult(I.getType()->getNumElements()),
00600             "Undefined result: insertelement index out of range", &I);
00601 }
00602 
00603 void Lint::visitUnreachableInst(UnreachableInst &I) {
00604   // This isn't undefined behavior, it's merely suspicious.
00605   Assert1(&I == I.getParent()->begin() ||
00606           std::prev(BasicBlock::iterator(&I))->mayHaveSideEffects(),
00607           "Unusual: unreachable immediately preceded by instruction without "
00608           "side effects", &I);
00609 }
00610 
00611 /// findValue - Look through bitcasts and simple memory reference patterns
00612 /// to identify an equivalent, but more informative, value.  If OffsetOk
00613 /// is true, look through getelementptrs with non-zero offsets too.
00614 ///
00615 /// Most analysis passes don't require this logic, because instcombine
00616 /// will simplify most of these kinds of things away. But it's a goal of
00617 /// this Lint pass to be useful even on non-optimized IR.
00618 Value *Lint::findValue(Value *V, bool OffsetOk) const {
00619   SmallPtrSet<Value *, 4> Visited;
00620   return findValueImpl(V, OffsetOk, Visited);
00621 }
00622 
00623 /// findValueImpl - Implementation helper for findValue.
00624 Value *Lint::findValueImpl(Value *V, bool OffsetOk,
00625                            SmallPtrSet<Value *, 4> &Visited) const {
00626   // Detect self-referential values.
00627   if (!Visited.insert(V))
00628     return UndefValue::get(V->getType());
00629 
00630   // TODO: Look through sext or zext cast, when the result is known to
00631   // be interpreted as signed or unsigned, respectively.
00632   // TODO: Look through eliminable cast pairs.
00633   // TODO: Look through calls with unique return values.
00634   // TODO: Look through vector insert/extract/shuffle.
00635   V = OffsetOk ? GetUnderlyingObject(V, DL) : V->stripPointerCasts();
00636   if (LoadInst *L = dyn_cast<LoadInst>(V)) {
00637     BasicBlock::iterator BBI = L;
00638     BasicBlock *BB = L->getParent();
00639     SmallPtrSet<BasicBlock *, 4> VisitedBlocks;
00640     for (;;) {
00641       if (!VisitedBlocks.insert(BB)) break;
00642       if (Value *U = FindAvailableLoadedValue(L->getPointerOperand(),
00643                                               BB, BBI, 6, AA))
00644         return findValueImpl(U, OffsetOk, Visited);
00645       if (BBI != BB->begin()) break;
00646       BB = BB->getUniquePredecessor();
00647       if (!BB) break;
00648       BBI = BB->end();
00649     }
00650   } else if (PHINode *PN = dyn_cast<PHINode>(V)) {
00651     if (Value *W = PN->hasConstantValue())
00652       if (W != V)
00653         return findValueImpl(W, OffsetOk, Visited);
00654   } else if (CastInst *CI = dyn_cast<CastInst>(V)) {
00655     if (CI->isNoopCast(DL))
00656       return findValueImpl(CI->getOperand(0), OffsetOk, Visited);
00657   } else if (ExtractValueInst *Ex = dyn_cast<ExtractValueInst>(V)) {
00658     if (Value *W = FindInsertedValue(Ex->getAggregateOperand(),
00659                                      Ex->getIndices()))
00660       if (W != V)
00661         return findValueImpl(W, OffsetOk, Visited);
00662   } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
00663     // Same as above, but for ConstantExpr instead of Instruction.
00664     if (Instruction::isCast(CE->getOpcode())) {
00665       if (CastInst::isNoopCast(Instruction::CastOps(CE->getOpcode()),
00666                                CE->getOperand(0)->getType(),
00667                                CE->getType(),
00668                                DL ? DL->getIntPtrType(V->getType()) :
00669                                     Type::getInt64Ty(V->getContext())))
00670         return findValueImpl(CE->getOperand(0), OffsetOk, Visited);
00671     } else if (CE->getOpcode() == Instruction::ExtractValue) {
00672       ArrayRef<unsigned> Indices = CE->getIndices();
00673       if (Value *W = FindInsertedValue(CE->getOperand(0), Indices))
00674         if (W != V)
00675           return findValueImpl(W, OffsetOk, Visited);
00676     }
00677   }
00678 
00679   // As a last resort, try SimplifyInstruction or constant folding.
00680   if (Instruction *Inst = dyn_cast<Instruction>(V)) {
00681     if (Value *W = SimplifyInstruction(Inst, DL, TLI, DT))
00682       return findValueImpl(W, OffsetOk, Visited);
00683   } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
00684     if (Value *W = ConstantFoldConstantExpression(CE, DL, TLI))
00685       if (W != V)
00686         return findValueImpl(W, OffsetOk, Visited);
00687   }
00688 
00689   return V;
00690 }
00691 
00692 //===----------------------------------------------------------------------===//
00693 //  Implement the public interfaces to this file...
00694 //===----------------------------------------------------------------------===//
00695 
00696 FunctionPass *llvm::createLintPass() {
00697   return new Lint();
00698 }
00699 
00700 /// lintFunction - Check a function for errors, printing messages on stderr.
00701 ///
00702 void llvm::lintFunction(const Function &f) {
00703   Function &F = const_cast<Function&>(f);
00704   assert(!F.isDeclaration() && "Cannot lint external functions");
00705 
00706   FunctionPassManager FPM(F.getParent());
00707   Lint *V = new Lint();
00708   FPM.add(V);
00709   FPM.run(F);
00710 }
00711 
00712 /// lintModule - Check a module for errors, printing messages on stderr.
00713 ///
00714 void llvm::lintModule(const Module &M) {
00715   PassManager PM;
00716   Lint *V = new Lint();
00717   PM.add(V);
00718   PM.run(const_cast<Module&>(M));
00719 }