X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FLint.cpp;h=0f5599e8204b40984b9c07502877c8752c2af1da;hb=2b5c8d67d2b20599eda9d1770f3ccce0e6417533;hp=b14f3292e90075367cb4db44d38bfbb7b2af6fca;hpb=db77b82ed5afdc87000bc3b85bfb5398f183a8b3;p=oota-llvm.git diff --git a/lib/Analysis/Lint.cpp b/lib/Analysis/Lint.cpp index b14f3292e90..0f5599e8204 100644 --- a/lib/Analysis/Lint.cpp +++ b/lib/Analysis/Lint.cpp @@ -36,31 +36,34 @@ #include "llvm/Analysis/Lint.h" #include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallSet.h" #include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/AssumptionCache.h" #include "llvm/Analysis/ConstantFolding.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/Loads.h" #include "llvm/Analysis/Passes.h" +#include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/CallSite.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/Function.h" +#include "llvm/IR/Module.h" #include "llvm/IR/InstVisitor.h" #include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/LegacyPassManager.h" #include "llvm/Pass.h" -#include "llvm/PassManager.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" -#include "llvm/Target/TargetLibraryInfo.h" using namespace llvm; namespace { namespace MemRef { - static unsigned Read = 1; - static unsigned Write = 2; - static unsigned Callee = 4; - static unsigned Branchee = 8; + static const unsigned Read = 1; + static const unsigned Write = 2; + static const unsigned Callee = 4; + static const unsigned Branchee = 8; } class Lint : public FunctionPass, public InstVisitor { @@ -72,6 +75,8 @@ namespace { void visitMemoryReference(Instruction &I, Value *Ptr, uint64_t Size, unsigned Align, Type *Ty, unsigned Flags); + void visitEHBeginCatch(IntrinsicInst *II); + void visitEHEndCatch(IntrinsicInst *II); void visitCallInst(CallInst &I); void visitInvokeInst(InvokeInst &I); @@ -96,13 +101,14 @@ namespace { Value *findValue(Value *V, bool OffsetOk) const; Value *findValueImpl(Value *V, bool OffsetOk, - SmallPtrSet &Visited) const; + SmallPtrSetImpl &Visited) const; public: Module *Mod; + const DataLayout *DL; AliasAnalysis *AA; + AssumptionCache *AC; DominatorTree *DT; - const DataLayout *DL; TargetLibraryInfo *TLI; std::string Messages; @@ -117,33 +123,40 @@ namespace { void getAnalysisUsage(AnalysisUsage &AU) const override { AU.setPreservesAll(); - AU.addRequired(); - AU.addRequired(); + AU.addRequired(); + AU.addRequired(); + AU.addRequired(); AU.addRequired(); } void print(raw_ostream &O, const Module *M) const override {} - void WriteValue(const Value *V) { - if (!V) return; - if (isa(V)) { - MessagesStr << *V << '\n'; - } else { - V->printAsOperand(MessagesStr, true, Mod); - MessagesStr << '\n'; + void WriteValues(ArrayRef Vs) { + for (const Value *V : Vs) { + if (!V) + continue; + if (isa(V)) { + MessagesStr << *V << '\n'; + } else { + V->printAsOperand(MessagesStr, true, Mod); + MessagesStr << '\n'; + } } } - // CheckFailed - A check failed, so print out the condition and the message - // that failed. This provides a nice place to put a breakpoint if you want - // to see why something is not correct. - void CheckFailed(const Twine &Message, - const Value *V1 = nullptr, const Value *V2 = nullptr, - const Value *V3 = nullptr, const Value *V4 = nullptr) { - MessagesStr << Message.str() << "\n"; - WriteValue(V1); - WriteValue(V2); - WriteValue(V3); - WriteValue(V4); + /// \brief A check failed, so printout out the condition and the message. + /// + /// This provides a nice place to put a breakpoint if you want to see why + /// something is not correct. + void CheckFailed(const Twine &Message) { MessagesStr << Message << '\n'; } + + /// \brief A check failed (with values to print). + /// + /// This calls the Message-only version so that the above is easier to set + /// a breakpoint on. + template + void CheckFailed(const Twine &Message, const T1 &V1, const Ts &...Vs) { + CheckFailed(Message); + WriteValues({V1, Vs...}); } }; } @@ -151,34 +164,27 @@ namespace { char Lint::ID = 0; INITIALIZE_PASS_BEGIN(Lint, "lint", "Statically lint-checks LLVM IR", false, true) -INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo) +INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) +INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) -INITIALIZE_AG_DEPENDENCY(AliasAnalysis) +INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) INITIALIZE_PASS_END(Lint, "lint", "Statically lint-checks LLVM IR", false, true) // Assert - We know that cond should be true, if not print an error message. -#define Assert(C, M) \ - do { if (!(C)) { CheckFailed(M); return; } } while (0) -#define Assert1(C, M, V1) \ - do { if (!(C)) { CheckFailed(M, V1); return; } } while (0) -#define Assert2(C, M, V1, V2) \ - do { if (!(C)) { CheckFailed(M, V1, V2); return; } } while (0) -#define Assert3(C, M, V1, V2, V3) \ - do { if (!(C)) { CheckFailed(M, V1, V2, V3); return; } } while (0) -#define Assert4(C, M, V1, V2, V3, V4) \ - do { if (!(C)) { CheckFailed(M, V1, V2, V3, V4); return; } } while (0) +#define Assert(C, ...) \ + do { if (!(C)) { CheckFailed(__VA_ARGS__); return; } } while (0) // Lint::run - This is the main Analysis entry point for a // function. // bool Lint::runOnFunction(Function &F) { Mod = F.getParent(); - AA = &getAnalysis(); + DL = &F.getParent()->getDataLayout(); + AA = &getAnalysis().getAAResults(); + AC = &getAnalysis().getAssumptionCache(F); DT = &getAnalysis().getDomTree(); - DataLayoutPass *DLP = getAnalysisIfAvailable(); - DL = DLP ? &DLP->getDataLayout() : nullptr; - TLI = &getAnalysis(); + TLI = &getAnalysis().getTLI(); visit(F); dbgs() << MessagesStr.str(); Messages.clear(); @@ -188,8 +194,8 @@ bool Lint::runOnFunction(Function &F) { void Lint::visitFunction(Function &F) { // This isn't undefined behavior, it's just a little unusual, and it's a // fairly common mistake to neglect to name a function. - Assert1(F.hasName() || F.hasLocalLinkage(), - "Unusual: Unnamed function with non-local linkage", &F); + Assert(F.hasName() || F.hasLocalLinkage(), + "Unusual: Unnamed function with non-local linkage", &F); // TODO: Check for irreducible control flow. } @@ -198,26 +204,28 @@ void Lint::visitCallSite(CallSite CS) { Instruction &I = *CS.getInstruction(); Value *Callee = CS.getCalledValue(); - visitMemoryReference(I, Callee, AliasAnalysis::UnknownSize, - 0, nullptr, MemRef::Callee); + visitMemoryReference(I, Callee, MemoryLocation::UnknownSize, 0, nullptr, + MemRef::Callee); - if (Function *F = dyn_cast(findValue(Callee, /*OffsetOk=*/false))) { - Assert1(CS.getCallingConv() == F->getCallingConv(), - "Undefined behavior: Caller and callee calling convention differ", - &I); + if (Function *F = dyn_cast(findValue(Callee, + /*OffsetOk=*/false))) { + Assert(CS.getCallingConv() == F->getCallingConv(), + "Undefined behavior: Caller and callee calling convention differ", + &I); FunctionType *FT = F->getFunctionType(); unsigned NumActualArgs = CS.arg_size(); - Assert1(FT->isVarArg() ? - FT->getNumParams() <= NumActualArgs : - FT->getNumParams() == NumActualArgs, - "Undefined behavior: Call argument count mismatches callee " - "argument count", &I); + Assert(FT->isVarArg() ? FT->getNumParams() <= NumActualArgs + : FT->getNumParams() == NumActualArgs, + "Undefined behavior: Call argument count mismatches callee " + "argument count", + &I); - Assert1(FT->getReturnType() == I.getType(), - "Undefined behavior: Call return type mismatches " - "callee return type", &I); + Assert(FT->getReturnType() == I.getType(), + "Undefined behavior: Call return type mismatches " + "callee return type", + &I); // Check argument types (in case the callee was casted) and attributes. // TODO: Verify that caller and callee attributes are compatible. @@ -227,9 +235,10 @@ void Lint::visitCallSite(CallSite CS) { Value *Actual = *AI; if (PI != PE) { Argument *Formal = PI++; - Assert1(Formal->getType() == Actual->getType(), - "Undefined behavior: Call argument type mismatches " - "callee parameter type", &I); + Assert(Formal->getType() == Actual->getType(), + "Undefined behavior: Call argument type mismatches " + "callee parameter type", + &I); // Check that noalias arguments don't alias other arguments. This is // not fully precise because we don't know the sizes of the dereferenced @@ -237,19 +246,18 @@ void Lint::visitCallSite(CallSite CS) { if (Formal->hasNoAliasAttr() && Actual->getType()->isPointerTy()) for (CallSite::arg_iterator BI = CS.arg_begin(); BI != AE; ++BI) if (AI != BI && (*BI)->getType()->isPointerTy()) { - AliasAnalysis::AliasResult Result = AA->alias(*AI, *BI); - Assert1(Result != AliasAnalysis::MustAlias && - Result != AliasAnalysis::PartialAlias, - "Unusual: noalias argument aliases another argument", &I); + AliasResult Result = AA->alias(*AI, *BI); + Assert(Result != MustAlias && Result != PartialAlias, + "Unusual: noalias argument aliases another argument", &I); } // Check that an sret argument points to valid memory. if (Formal->hasStructRetAttr() && Actual->getType()->isPointerTy()) { Type *Ty = cast(Formal->getType())->getElementType(); - visitMemoryReference(I, Actual, AA->getTypeStoreSize(Ty), - DL ? DL->getABITypeAlignment(Ty) : 0, - Ty, MemRef::Read | MemRef::Write); + visitMemoryReference(I, Actual, DL->getTypeStoreSize(Ty), + DL->getABITypeAlignment(Ty), Ty, + MemRef::Read | MemRef::Write); } } } @@ -259,9 +267,10 @@ void Lint::visitCallSite(CallSite CS) { for (CallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end(); AI != AE; ++AI) { Value *Obj = findValue(*AI, /*OffsetOk=*/true); - Assert1(!isa(Obj), - "Undefined behavior: Call with \"tail\" keyword references " - "alloca", &I); + Assert(!isa(Obj), + "Undefined behavior: Call with \"tail\" keyword references " + "alloca", + &I); } @@ -274,72 +283,74 @@ void Lint::visitCallSite(CallSite CS) { case Intrinsic::memcpy: { MemCpyInst *MCI = cast(&I); // TODO: If the size is known, use it. - visitMemoryReference(I, MCI->getDest(), AliasAnalysis::UnknownSize, - MCI->getAlignment(), nullptr, - MemRef::Write); - visitMemoryReference(I, MCI->getSource(), AliasAnalysis::UnknownSize, - MCI->getAlignment(), nullptr, - MemRef::Read); + visitMemoryReference(I, MCI->getDest(), MemoryLocation::UnknownSize, + MCI->getAlignment(), nullptr, MemRef::Write); + visitMemoryReference(I, MCI->getSource(), MemoryLocation::UnknownSize, + MCI->getAlignment(), nullptr, MemRef::Read); // Check that the memcpy arguments don't overlap. The AliasAnalysis API // isn't expressive enough for what we really want to do. Known partial // overlap is not distinguished from the case where nothing is known. uint64_t Size = 0; if (const ConstantInt *Len = - dyn_cast(findValue(MCI->getLength(), - /*OffsetOk=*/false))) + dyn_cast(findValue(MCI->getLength(), + /*OffsetOk=*/false))) if (Len->getValue().isIntN(32)) Size = Len->getValue().getZExtValue(); - Assert1(AA->alias(MCI->getSource(), Size, MCI->getDest(), Size) != - AliasAnalysis::MustAlias, - "Undefined behavior: memcpy source and destination overlap", &I); + Assert(AA->alias(MCI->getSource(), Size, MCI->getDest(), Size) != + MustAlias, + "Undefined behavior: memcpy source and destination overlap", &I); break; } case Intrinsic::memmove: { MemMoveInst *MMI = cast(&I); // TODO: If the size is known, use it. - visitMemoryReference(I, MMI->getDest(), AliasAnalysis::UnknownSize, - MMI->getAlignment(), nullptr, - MemRef::Write); - visitMemoryReference(I, MMI->getSource(), AliasAnalysis::UnknownSize, - MMI->getAlignment(), nullptr, - MemRef::Read); + visitMemoryReference(I, MMI->getDest(), MemoryLocation::UnknownSize, + MMI->getAlignment(), nullptr, MemRef::Write); + visitMemoryReference(I, MMI->getSource(), MemoryLocation::UnknownSize, + MMI->getAlignment(), nullptr, MemRef::Read); break; } case Intrinsic::memset: { MemSetInst *MSI = cast(&I); // TODO: If the size is known, use it. - visitMemoryReference(I, MSI->getDest(), AliasAnalysis::UnknownSize, - MSI->getAlignment(), nullptr, - MemRef::Write); + visitMemoryReference(I, MSI->getDest(), MemoryLocation::UnknownSize, + MSI->getAlignment(), nullptr, MemRef::Write); break; } case Intrinsic::vastart: - Assert1(I.getParent()->getParent()->isVarArg(), - "Undefined behavior: va_start called in a non-varargs function", - &I); + Assert(I.getParent()->getParent()->isVarArg(), + "Undefined behavior: va_start called in a non-varargs function", + &I); - visitMemoryReference(I, CS.getArgument(0), AliasAnalysis::UnknownSize, - 0, nullptr, MemRef::Read | MemRef::Write); + visitMemoryReference(I, CS.getArgument(0), MemoryLocation::UnknownSize, 0, + nullptr, MemRef::Read | MemRef::Write); break; case Intrinsic::vacopy: - visitMemoryReference(I, CS.getArgument(0), AliasAnalysis::UnknownSize, - 0, nullptr, MemRef::Write); - visitMemoryReference(I, CS.getArgument(1), AliasAnalysis::UnknownSize, - 0, nullptr, MemRef::Read); + visitMemoryReference(I, CS.getArgument(0), MemoryLocation::UnknownSize, 0, + nullptr, MemRef::Write); + visitMemoryReference(I, CS.getArgument(1), MemoryLocation::UnknownSize, 0, + nullptr, MemRef::Read); break; case Intrinsic::vaend: - visitMemoryReference(I, CS.getArgument(0), AliasAnalysis::UnknownSize, - 0, nullptr, MemRef::Read | MemRef::Write); + visitMemoryReference(I, CS.getArgument(0), MemoryLocation::UnknownSize, 0, + nullptr, MemRef::Read | MemRef::Write); break; case Intrinsic::stackrestore: // Stackrestore doesn't read or write memory, but it sets the // stack pointer, which the compiler may read from or write to // at any time, so check it for both readability and writeability. - visitMemoryReference(I, CS.getArgument(0), AliasAnalysis::UnknownSize, - 0, nullptr, MemRef::Read | MemRef::Write); + visitMemoryReference(I, CS.getArgument(0), MemoryLocation::UnknownSize, 0, + nullptr, MemRef::Read | MemRef::Write); + break; + + case Intrinsic::eh_begincatch: + visitEHBeginCatch(II); + break; + case Intrinsic::eh_endcatch: + visitEHEndCatch(II); break; } } @@ -354,14 +365,12 @@ void Lint::visitInvokeInst(InvokeInst &I) { void Lint::visitReturnInst(ReturnInst &I) { Function *F = I.getParent()->getParent(); - Assert1(!F->doesNotReturn(), - "Unusual: Return statement in function with noreturn attribute", - &I); + Assert(!F->doesNotReturn(), + "Unusual: Return statement in function with noreturn attribute", &I); if (Value *V = I.getReturnValue()) { Value *Obj = findValue(V, /*OffsetOk=*/true); - Assert1(!isa(Obj), - "Unusual: Returning alloca value", &I); + Assert(!isa(Obj), "Unusual: Returning alloca value", &I); } } @@ -376,135 +385,315 @@ void Lint::visitMemoryReference(Instruction &I, return; Value *UnderlyingObject = findValue(Ptr, /*OffsetOk=*/true); - Assert1(!isa(UnderlyingObject), - "Undefined behavior: Null pointer dereference", &I); - Assert1(!isa(UnderlyingObject), - "Undefined behavior: Undef pointer dereference", &I); - Assert1(!isa(UnderlyingObject) || - !cast(UnderlyingObject)->isAllOnesValue(), - "Unusual: All-ones pointer dereference", &I); - Assert1(!isa(UnderlyingObject) || - !cast(UnderlyingObject)->isOne(), - "Unusual: Address one pointer dereference", &I); + Assert(!isa(UnderlyingObject), + "Undefined behavior: Null pointer dereference", &I); + Assert(!isa(UnderlyingObject), + "Undefined behavior: Undef pointer dereference", &I); + Assert(!isa(UnderlyingObject) || + !cast(UnderlyingObject)->isAllOnesValue(), + "Unusual: All-ones pointer dereference", &I); + Assert(!isa(UnderlyingObject) || + !cast(UnderlyingObject)->isOne(), + "Unusual: Address one pointer dereference", &I); if (Flags & MemRef::Write) { if (const GlobalVariable *GV = dyn_cast(UnderlyingObject)) - Assert1(!GV->isConstant(), - "Undefined behavior: Write to read-only memory", &I); - Assert1(!isa(UnderlyingObject) && - !isa(UnderlyingObject), - "Undefined behavior: Write to text section", &I); + Assert(!GV->isConstant(), "Undefined behavior: Write to read-only memory", + &I); + Assert(!isa(UnderlyingObject) && + !isa(UnderlyingObject), + "Undefined behavior: Write to text section", &I); } if (Flags & MemRef::Read) { - Assert1(!isa(UnderlyingObject), - "Unusual: Load from function body", &I); - Assert1(!isa(UnderlyingObject), - "Undefined behavior: Load from block address", &I); + Assert(!isa(UnderlyingObject), "Unusual: Load from function body", + &I); + Assert(!isa(UnderlyingObject), + "Undefined behavior: Load from block address", &I); } if (Flags & MemRef::Callee) { - Assert1(!isa(UnderlyingObject), - "Undefined behavior: Call to block address", &I); + Assert(!isa(UnderlyingObject), + "Undefined behavior: Call to block address", &I); } if (Flags & MemRef::Branchee) { - Assert1(!isa(UnderlyingObject) || - isa(UnderlyingObject), - "Undefined behavior: Branch to non-blockaddress", &I); + Assert(!isa(UnderlyingObject) || + isa(UnderlyingObject), + "Undefined behavior: Branch to non-blockaddress", &I); } // Check for buffer overflows and misalignment. // Only handles memory references that read/write something simple like an // alloca instruction or a global variable. int64_t Offset = 0; - if (Value *Base = GetPointerBaseWithConstantOffset(Ptr, Offset, DL)) { + if (Value *Base = GetPointerBaseWithConstantOffset(Ptr, Offset, *DL)) { // OK, so the access is to a constant offset from Ptr. Check that Ptr is // something we can handle and if so extract the size of this base object // along with its alignment. - uint64_t BaseSize = AliasAnalysis::UnknownSize; + uint64_t BaseSize = MemoryLocation::UnknownSize; unsigned BaseAlign = 0; if (AllocaInst *AI = dyn_cast(Base)) { Type *ATy = AI->getAllocatedType(); - if (DL && !AI->isArrayAllocation() && ATy->isSized()) + if (!AI->isArrayAllocation() && ATy->isSized()) BaseSize = DL->getTypeAllocSize(ATy); BaseAlign = AI->getAlignment(); - if (DL && BaseAlign == 0 && ATy->isSized()) + if (BaseAlign == 0 && ATy->isSized()) BaseAlign = DL->getABITypeAlignment(ATy); } else if (GlobalVariable *GV = dyn_cast(Base)) { // If the global may be defined differently in another compilation unit // then don't warn about funky memory accesses. if (GV->hasDefinitiveInitializer()) { Type *GTy = GV->getType()->getElementType(); - if (DL && GTy->isSized()) + if (GTy->isSized()) BaseSize = DL->getTypeAllocSize(GTy); BaseAlign = GV->getAlignment(); - if (DL && BaseAlign == 0 && GTy->isSized()) + if (BaseAlign == 0 && GTy->isSized()) BaseAlign = DL->getABITypeAlignment(GTy); } } // Accesses from before the start or after the end of the object are not // defined. - Assert1(Size == AliasAnalysis::UnknownSize || - BaseSize == AliasAnalysis::UnknownSize || - (Offset >= 0 && Offset + Size <= BaseSize), - "Undefined behavior: Buffer overflow", &I); + Assert(Size == MemoryLocation::UnknownSize || + BaseSize == MemoryLocation::UnknownSize || + (Offset >= 0 && Offset + Size <= BaseSize), + "Undefined behavior: Buffer overflow", &I); // Accesses that say that the memory is more aligned than it is are not // defined. - if (DL && Align == 0 && Ty && Ty->isSized()) + if (Align == 0 && Ty && Ty->isSized()) Align = DL->getABITypeAlignment(Ty); - Assert1(!BaseAlign || Align <= MinAlign(BaseAlign, Offset), - "Undefined behavior: Memory reference address is misaligned", &I); + Assert(!BaseAlign || Align <= MinAlign(BaseAlign, Offset), + "Undefined behavior: Memory reference address is misaligned", &I); } } void Lint::visitLoadInst(LoadInst &I) { visitMemoryReference(I, I.getPointerOperand(), - AA->getTypeStoreSize(I.getType()), I.getAlignment(), + DL->getTypeStoreSize(I.getType()), I.getAlignment(), I.getType(), MemRef::Read); } void Lint::visitStoreInst(StoreInst &I) { visitMemoryReference(I, I.getPointerOperand(), - AA->getTypeStoreSize(I.getOperand(0)->getType()), + DL->getTypeStoreSize(I.getOperand(0)->getType()), I.getAlignment(), I.getOperand(0)->getType(), MemRef::Write); } void Lint::visitXor(BinaryOperator &I) { - Assert1(!isa(I.getOperand(0)) || - !isa(I.getOperand(1)), - "Undefined result: xor(undef, undef)", &I); + Assert(!isa(I.getOperand(0)) || !isa(I.getOperand(1)), + "Undefined result: xor(undef, undef)", &I); } void Lint::visitSub(BinaryOperator &I) { - Assert1(!isa(I.getOperand(0)) || - !isa(I.getOperand(1)), - "Undefined result: sub(undef, undef)", &I); + Assert(!isa(I.getOperand(0)) || !isa(I.getOperand(1)), + "Undefined result: sub(undef, undef)", &I); } void Lint::visitLShr(BinaryOperator &I) { - if (ConstantInt *CI = - dyn_cast(findValue(I.getOperand(1), /*OffsetOk=*/false))) - Assert1(CI->getValue().ult(cast(I.getType())->getBitWidth()), - "Undefined result: Shift count out of range", &I); + if (ConstantInt *CI = dyn_cast(findValue(I.getOperand(1), + /*OffsetOk=*/false))) + Assert(CI->getValue().ult(cast(I.getType())->getBitWidth()), + "Undefined result: Shift count out of range", &I); } void Lint::visitAShr(BinaryOperator &I) { if (ConstantInt *CI = - dyn_cast(findValue(I.getOperand(1), /*OffsetOk=*/false))) - Assert1(CI->getValue().ult(cast(I.getType())->getBitWidth()), - "Undefined result: Shift count out of range", &I); + dyn_cast(findValue(I.getOperand(1), /*OffsetOk=*/false))) + Assert(CI->getValue().ult(cast(I.getType())->getBitWidth()), + "Undefined result: Shift count out of range", &I); } void Lint::visitShl(BinaryOperator &I) { if (ConstantInt *CI = - dyn_cast(findValue(I.getOperand(1), /*OffsetOk=*/false))) - Assert1(CI->getValue().ult(cast(I.getType())->getBitWidth()), - "Undefined result: Shift count out of range", &I); + dyn_cast(findValue(I.getOperand(1), /*OffsetOk=*/false))) + Assert(CI->getValue().ult(cast(I.getType())->getBitWidth()), + "Undefined result: Shift count out of range", &I); } -static bool isZero(Value *V, const DataLayout *DL) { +static bool +allPredsCameFromLandingPad(BasicBlock *BB, + SmallSet &VisitedBlocks) { + VisitedBlocks.insert(BB); + if (BB->isLandingPad()) + return true; + // If we find a block with no predecessors, the search failed. + if (pred_empty(BB)) + return false; + for (BasicBlock *Pred : predecessors(BB)) { + if (VisitedBlocks.count(Pred)) + continue; + if (!allPredsCameFromLandingPad(Pred, VisitedBlocks)) + return false; + } + return true; +} + +static bool +allSuccessorsReachEndCatch(BasicBlock *BB, BasicBlock::iterator InstBegin, + IntrinsicInst **SecondBeginCatch, + SmallSet &VisitedBlocks) { + VisitedBlocks.insert(BB); + for (BasicBlock::iterator I = InstBegin, E = BB->end(); I != E; ++I) { + IntrinsicInst *IC = dyn_cast(I); + if (IC && IC->getIntrinsicID() == Intrinsic::eh_endcatch) + return true; + // If we find another begincatch while looking for an endcatch, + // that's also an error. + if (IC && IC->getIntrinsicID() == Intrinsic::eh_begincatch) { + *SecondBeginCatch = IC; + return false; + } + } + + // If we reach a block with no successors while searching, the + // search has failed. + if (succ_empty(BB)) + return false; + // Otherwise, search all of the successors. + for (BasicBlock *Succ : successors(BB)) { + if (VisitedBlocks.count(Succ)) + continue; + if (!allSuccessorsReachEndCatch(Succ, Succ->begin(), SecondBeginCatch, + VisitedBlocks)) + return false; + } + return true; +} + +void Lint::visitEHBeginCatch(IntrinsicInst *II) { + // The checks in this function make a potentially dubious assumption about + // the CFG, namely that any block involved in a catch is only used for the + // catch. This will very likely be true of IR generated by a front end, + // but it may cease to be true, for example, if the IR is run through a + // pass which combines similar blocks. + // + // In general, if we encounter a block the isn't dominated by the catch + // block while we are searching the catch block's successors for a call + // to end catch intrinsic, then it is possible that it will be legal for + // a path through this block to never reach a call to llvm.eh.endcatch. + // An analogous statement could be made about our search for a landing + // pad among the catch block's predecessors. + // + // What is actually required is that no path is possible at runtime that + // reaches a call to llvm.eh.begincatch without having previously visited + // a landingpad instruction and that no path is possible at runtime that + // calls llvm.eh.begincatch and does not subsequently call llvm.eh.endcatch + // (mentally adjusting for the fact that in reality these calls will be + // removed before code generation). + // + // Because this is a lint check, we take a pessimistic approach and warn if + // the control flow is potentially incorrect. + + SmallSet VisitedBlocks; + BasicBlock *CatchBB = II->getParent(); + + // The begin catch must occur in a landing pad block or all paths + // to it must have come from a landing pad. + Assert(allPredsCameFromLandingPad(CatchBB, VisitedBlocks), + "llvm.eh.begincatch may be reachable without passing a landingpad", + II); + + // Reset the visited block list. + VisitedBlocks.clear(); + + IntrinsicInst *SecondBeginCatch = nullptr; + + // This has to be called before it is asserted. Otherwise, the first assert + // below can never be hit. + bool EndCatchFound = allSuccessorsReachEndCatch( + CatchBB, std::next(static_cast(II)), + &SecondBeginCatch, VisitedBlocks); + Assert( + SecondBeginCatch == nullptr, + "llvm.eh.begincatch may be called a second time before llvm.eh.endcatch", + II, SecondBeginCatch); + Assert(EndCatchFound, + "Some paths from llvm.eh.begincatch may not reach llvm.eh.endcatch", + II); +} + +static bool allPredCameFromBeginCatch( + BasicBlock *BB, BasicBlock::reverse_iterator InstRbegin, + IntrinsicInst **SecondEndCatch, SmallSet &VisitedBlocks) { + VisitedBlocks.insert(BB); + // Look for a begincatch in this block. + for (BasicBlock::reverse_iterator RI = InstRbegin, RE = BB->rend(); RI != RE; + ++RI) { + IntrinsicInst *IC = dyn_cast(&*RI); + if (IC && IC->getIntrinsicID() == Intrinsic::eh_begincatch) + return true; + // If we find another end catch before we find a begin catch, that's + // an error. + if (IC && IC->getIntrinsicID() == Intrinsic::eh_endcatch) { + *SecondEndCatch = IC; + return false; + } + // If we encounter a landingpad instruction, the search failed. + if (isa(*RI)) + return false; + } + // If while searching we find a block with no predeccesors, + // the search failed. + if (pred_empty(BB)) + return false; + // Search any predecessors we haven't seen before. + for (BasicBlock *Pred : predecessors(BB)) { + if (VisitedBlocks.count(Pred)) + continue; + if (!allPredCameFromBeginCatch(Pred, Pred->rbegin(), SecondEndCatch, + VisitedBlocks)) + return false; + } + return true; +} + +void Lint::visitEHEndCatch(IntrinsicInst *II) { + // The check in this function makes a potentially dubious assumption about + // the CFG, namely that any block involved in a catch is only used for the + // catch. This will very likely be true of IR generated by a front end, + // but it may cease to be true, for example, if the IR is run through a + // pass which combines similar blocks. + // + // In general, if we encounter a block the isn't post-dominated by the + // end catch block while we are searching the end catch block's predecessors + // for a call to the begin catch intrinsic, then it is possible that it will + // be legal for a path to reach the end catch block without ever having + // called llvm.eh.begincatch. + // + // What is actually required is that no path is possible at runtime that + // reaches a call to llvm.eh.endcatch without having previously visited + // a call to llvm.eh.begincatch (mentally adjusting for the fact that in + // reality these calls will be removed before code generation). + // + // Because this is a lint check, we take a pessimistic approach and warn if + // the control flow is potentially incorrect. + + BasicBlock *EndCatchBB = II->getParent(); + + // Alls paths to the end catch call must pass through a begin catch call. + + // If llvm.eh.begincatch wasn't called in the current block, we'll use this + // lambda to recursively look for it in predecessors. + SmallSet VisitedBlocks; + IntrinsicInst *SecondEndCatch = nullptr; + + // This has to be called before it is asserted. Otherwise, the first assert + // below can never be hit. + bool BeginCatchFound = + allPredCameFromBeginCatch(EndCatchBB, BasicBlock::reverse_iterator(II), + &SecondEndCatch, VisitedBlocks); + Assert( + SecondEndCatch == nullptr, + "llvm.eh.endcatch may be called a second time after llvm.eh.begincatch", + II, SecondEndCatch); + Assert(BeginCatchFound, + "llvm.eh.endcatch may be reachable without passing llvm.eh.begincatch", + II); +} + +static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, + AssumptionCache *AC) { // Assume undef could be zero. if (isa(V)) return true; @@ -513,7 +702,8 @@ static bool isZero(Value *V, const DataLayout *DL) { if (!VecTy) { unsigned BitWidth = V->getType()->getIntegerBitWidth(); APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0); - computeKnownBits(V, KnownZero, KnownOne, DL); + computeKnownBits(V, KnownZero, KnownOne, DL, 0, AC, + dyn_cast(V), DT); return KnownZero.isAllOnesValue(); } @@ -543,69 +733,68 @@ static bool isZero(Value *V, const DataLayout *DL) { } void Lint::visitSDiv(BinaryOperator &I) { - Assert1(!isZero(I.getOperand(1), DL), - "Undefined behavior: Division by zero", &I); + Assert(!isZero(I.getOperand(1), I.getModule()->getDataLayout(), DT, AC), + "Undefined behavior: Division by zero", &I); } void Lint::visitUDiv(BinaryOperator &I) { - Assert1(!isZero(I.getOperand(1), DL), - "Undefined behavior: Division by zero", &I); + Assert(!isZero(I.getOperand(1), I.getModule()->getDataLayout(), DT, AC), + "Undefined behavior: Division by zero", &I); } void Lint::visitSRem(BinaryOperator &I) { - Assert1(!isZero(I.getOperand(1), DL), - "Undefined behavior: Division by zero", &I); + Assert(!isZero(I.getOperand(1), I.getModule()->getDataLayout(), DT, AC), + "Undefined behavior: Division by zero", &I); } void Lint::visitURem(BinaryOperator &I) { - Assert1(!isZero(I.getOperand(1), DL), - "Undefined behavior: Division by zero", &I); + Assert(!isZero(I.getOperand(1), I.getModule()->getDataLayout(), DT, AC), + "Undefined behavior: Division by zero", &I); } void Lint::visitAllocaInst(AllocaInst &I) { if (isa(I.getArraySize())) // This isn't undefined behavior, it's just an obvious pessimization. - Assert1(&I.getParent()->getParent()->getEntryBlock() == I.getParent(), - "Pessimization: Static alloca outside of entry block", &I); + Assert(&I.getParent()->getParent()->getEntryBlock() == I.getParent(), + "Pessimization: Static alloca outside of entry block", &I); // TODO: Check for an unusual size (MSB set?) } void Lint::visitVAArgInst(VAArgInst &I) { - visitMemoryReference(I, I.getOperand(0), AliasAnalysis::UnknownSize, 0, + visitMemoryReference(I, I.getOperand(0), MemoryLocation::UnknownSize, 0, nullptr, MemRef::Read | MemRef::Write); } void Lint::visitIndirectBrInst(IndirectBrInst &I) { - visitMemoryReference(I, I.getAddress(), AliasAnalysis::UnknownSize, 0, + visitMemoryReference(I, I.getAddress(), MemoryLocation::UnknownSize, 0, nullptr, MemRef::Branchee); - Assert1(I.getNumDestinations() != 0, - "Undefined behavior: indirectbr with no destinations", &I); + Assert(I.getNumDestinations() != 0, + "Undefined behavior: indirectbr with no destinations", &I); } void Lint::visitExtractElementInst(ExtractElementInst &I) { - if (ConstantInt *CI = - dyn_cast(findValue(I.getIndexOperand(), - /*OffsetOk=*/false))) - Assert1(CI->getValue().ult(I.getVectorOperandType()->getNumElements()), - "Undefined result: extractelement index out of range", &I); + if (ConstantInt *CI = dyn_cast(findValue(I.getIndexOperand(), + /*OffsetOk=*/false))) + Assert(CI->getValue().ult(I.getVectorOperandType()->getNumElements()), + "Undefined result: extractelement index out of range", &I); } void Lint::visitInsertElementInst(InsertElementInst &I) { - if (ConstantInt *CI = - dyn_cast(findValue(I.getOperand(2), - /*OffsetOk=*/false))) - Assert1(CI->getValue().ult(I.getType()->getNumElements()), - "Undefined result: insertelement index out of range", &I); + if (ConstantInt *CI = dyn_cast(findValue(I.getOperand(2), + /*OffsetOk=*/false))) + Assert(CI->getValue().ult(I.getType()->getNumElements()), + "Undefined result: insertelement index out of range", &I); } void Lint::visitUnreachableInst(UnreachableInst &I) { // This isn't undefined behavior, it's merely suspicious. - Assert1(&I == I.getParent()->begin() || - std::prev(BasicBlock::iterator(&I))->mayHaveSideEffects(), - "Unusual: unreachable immediately preceded by instruction without " - "side effects", &I); + Assert(&I == I.getParent()->begin() || + std::prev(BasicBlock::iterator(&I))->mayHaveSideEffects(), + "Unusual: unreachable immediately preceded by instruction without " + "side effects", + &I); } /// findValue - Look through bitcasts and simple memory reference patterns @@ -622,9 +811,9 @@ Value *Lint::findValue(Value *V, bool OffsetOk) const { /// findValueImpl - Implementation helper for findValue. Value *Lint::findValueImpl(Value *V, bool OffsetOk, - SmallPtrSet &Visited) const { + SmallPtrSetImpl &Visited) const { // Detect self-referential values. - if (!Visited.insert(V)) + if (!Visited.insert(V).second) return UndefValue::get(V->getType()); // TODO: Look through sext or zext cast, when the result is known to @@ -632,13 +821,14 @@ Value *Lint::findValueImpl(Value *V, bool OffsetOk, // TODO: Look through eliminable cast pairs. // TODO: Look through calls with unique return values. // TODO: Look through vector insert/extract/shuffle. - V = OffsetOk ? GetUnderlyingObject(V, DL) : V->stripPointerCasts(); + V = OffsetOk ? GetUnderlyingObject(V, *DL) : V->stripPointerCasts(); if (LoadInst *L = dyn_cast(V)) { BasicBlock::iterator BBI = L; BasicBlock *BB = L->getParent(); SmallPtrSet VisitedBlocks; for (;;) { - if (!VisitedBlocks.insert(BB)) break; + if (!VisitedBlocks.insert(BB).second) + break; if (Value *U = FindAvailableLoadedValue(L->getPointerOperand(), BB, BBI, 6, AA)) return findValueImpl(U, OffsetOk, Visited); @@ -652,7 +842,7 @@ Value *Lint::findValueImpl(Value *V, bool OffsetOk, if (W != V) return findValueImpl(W, OffsetOk, Visited); } else if (CastInst *CI = dyn_cast(V)) { - if (CI->isNoopCast(DL)) + if (CI->isNoopCast(*DL)) return findValueImpl(CI->getOperand(0), OffsetOk, Visited); } else if (ExtractValueInst *Ex = dyn_cast(V)) { if (Value *W = FindInsertedValue(Ex->getAggregateOperand(), @@ -663,10 +853,8 @@ Value *Lint::findValueImpl(Value *V, bool OffsetOk, // Same as above, but for ConstantExpr instead of Instruction. if (Instruction::isCast(CE->getOpcode())) { if (CastInst::isNoopCast(Instruction::CastOps(CE->getOpcode()), - CE->getOperand(0)->getType(), - CE->getType(), - DL ? DL->getIntPtrType(V->getType()) : - Type::getInt64Ty(V->getContext()))) + CE->getOperand(0)->getType(), CE->getType(), + DL->getIntPtrType(V->getType()))) return findValueImpl(CE->getOperand(0), OffsetOk, Visited); } else if (CE->getOpcode() == Instruction::ExtractValue) { ArrayRef Indices = CE->getIndices(); @@ -678,10 +866,10 @@ Value *Lint::findValueImpl(Value *V, bool OffsetOk, // As a last resort, try SimplifyInstruction or constant folding. if (Instruction *Inst = dyn_cast(V)) { - if (Value *W = SimplifyInstruction(Inst, DL, TLI, DT)) + if (Value *W = SimplifyInstruction(Inst, *DL, TLI, DT, AC)) return findValueImpl(W, OffsetOk, Visited); } else if (ConstantExpr *CE = dyn_cast(V)) { - if (Value *W = ConstantFoldConstantExpression(CE, DL, TLI)) + if (Value *W = ConstantFoldConstantExpression(CE, *DL, TLI)) if (W != V) return findValueImpl(W, OffsetOk, Visited); } @@ -703,7 +891,7 @@ void llvm::lintFunction(const Function &f) { Function &F = const_cast(f); assert(!F.isDeclaration() && "Cannot lint external functions"); - FunctionPassManager FPM(F.getParent()); + legacy::FunctionPassManager FPM(F.getParent()); Lint *V = new Lint(); FPM.add(V); FPM.run(F); @@ -712,7 +900,7 @@ void llvm::lintFunction(const Function &f) { /// lintModule - Check a module for errors, printing messages on stderr. /// void llvm::lintModule(const Module &M) { - PassManager PM; + legacy::PassManager PM; Lint *V = new Lint(); PM.add(V); PM.run(const_cast(M));