LCOV - code coverage report
Current view: top level - lib/Analysis - Lint.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 209 245 85.3 %
Date: 2018-07-13 00:08:38 Functions: 41 46 89.1 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13