X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FIR%2FVerifier.cpp;h=1557ca0dbb78821bfecf64e093cf521ce7da1e35;hp=6dfb05d9449122dcc3705c1ac7ad5afcfbb159a7;hb=fad8ff3134d32996a6ce6beba7ee70d5e1c51d8b;hpb=397864c7122838ca2afd0ceb61efeee540c37948 diff --git a/lib/IR/Verifier.cpp b/lib/IR/Verifier.cpp index 6dfb05d9449..1557ca0dbb7 100644 --- a/lib/IR/Verifier.cpp +++ b/lib/IR/Verifier.cpp @@ -45,6 +45,7 @@ //===----------------------------------------------------------------------===// #include "llvm/IR/Verifier.h" +#include "llvm/ADT/MapVector.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallPtrSet.h" @@ -145,6 +146,11 @@ private: OS << *C; } + template void Write(ArrayRef Vs) { + for (const T &V : Vs) + Write(V); + } + template void WriteTs(const T1 &V1, const Ts &... Vs) { Write(V1); @@ -204,6 +210,10 @@ class Verifier : public InstVisitor, VerifierSupport { /// given function and the largest index passed to llvm.localrecover. DenseMap> FrameEscapeInfo; + // Maps catchswitches and cleanuppads that unwind to siblings to the + // terminators that indicate the unwind, used to detect cycles therein. + MapVector SiblingFuncletInfo; + /// Cache of constants visited in search of ConstantExprs. SmallPtrSet ConstantExprVisited; @@ -245,9 +255,11 @@ public: Broken = false; // FIXME: We strip const here because the inst visitor strips const. visit(const_cast(F)); + verifySiblingFuncletUnwinds(); InstsInThisBlock.clear(); LandingPadResultTy = nullptr; SawFrameEscape = false; + SiblingFuncletInfo.clear(); return !Broken; } @@ -403,6 +415,7 @@ private: void visitCatchPadInst(CatchPadInst &CPI); void visitCatchReturnInst(CatchReturnInst &CatchReturn); void visitCleanupPadInst(CleanupPadInst &CPI); + void visitFuncletPadInst(FuncletPadInst &FPI); void visitCatchSwitchInst(CatchSwitchInst &CatchSwitch); void visitCleanupReturnInst(CleanupReturnInst &CRI); @@ -428,12 +441,12 @@ private: void visitConstantExpr(const ConstantExpr *CE); void VerifyStatepoint(ImmutableCallSite CS); void verifyFrameRecoverIndices(); + void verifySiblingFuncletUnwinds(); // Module-level debug info verification... void verifyTypeRefs(); template - void verifyBitPieceExpression(const DbgInfoIntrinsic &I, - const MapTy &TypeRefs); + void verifyDIExpression(const DbgInfoIntrinsic &I, const MapTy &TypeRefs); void visitUnresolvedTypeRef(const MDString *S, const MDNode *N); }; } // End anonymous namespace @@ -984,6 +997,9 @@ void Verifier::visitDIMacro(const DIMacro &N) { N.getMacinfoType() == dwarf::DW_MACINFO_undef, "invalid macinfo type", &N); Assert(!N.getName().empty(), "anonymous macro", &N); + if (!N.getValue().empty()) { + assert(N.getValue().data()[0] != ' ' && "Macro value has a space prefix"); + } } void Verifier::visitDIMacroFile(const DIMacroFile &N) { @@ -1693,6 +1709,59 @@ void Verifier::verifyFrameRecoverIndices() { } } +static Instruction *getSuccPad(TerminatorInst *Terminator) { + BasicBlock *UnwindDest; + if (auto *II = dyn_cast(Terminator)) + UnwindDest = II->getUnwindDest(); + else if (auto *CSI = dyn_cast(Terminator)) + UnwindDest = CSI->getUnwindDest(); + else + UnwindDest = cast(Terminator)->getUnwindDest(); + return UnwindDest->getFirstNonPHI(); +} + +void Verifier::verifySiblingFuncletUnwinds() { + SmallPtrSet Visited; + SmallPtrSet Active; + for (const auto &Pair : SiblingFuncletInfo) { + Instruction *PredPad = Pair.first; + if (Visited.count(PredPad)) + continue; + Active.insert(PredPad); + TerminatorInst *Terminator = Pair.second; + do { + Instruction *SuccPad = getSuccPad(Terminator); + if (Active.count(SuccPad)) { + // Found a cycle; report error + Instruction *CyclePad = SuccPad; + SmallVector CycleNodes; + do { + CycleNodes.push_back(CyclePad); + TerminatorInst *CycleTerminator = SiblingFuncletInfo[CyclePad]; + if (CycleTerminator != CyclePad) + CycleNodes.push_back(CycleTerminator); + CyclePad = getSuccPad(CycleTerminator); + } while (CyclePad != SuccPad); + Assert(false, "EH pads can't handle each other's exceptions", + ArrayRef(CycleNodes)); + } + // Don't re-walk a node we've already checked + if (!Visited.insert(SuccPad).second) + break; + // Walk to this successor if it has a map entry. + PredPad = SuccPad; + auto TermI = SiblingFuncletInfo.find(PredPad); + if (TermI == SiblingFuncletInfo.end()) + break; + Terminator = TermI->second; + Active.insert(PredPad); + } while (true); + // Each node only has one successor, so we've walked all the active + // nodes' successors. + Active.clear(); + } +} + // visitFunction - Verify that a function is ok. // void Verifier::visitFunction(const Function &F) { @@ -2892,6 +2961,13 @@ void Verifier::visitInsertValueInst(InsertValueInst &IVI) { visitInstruction(IVI); } +static Value *getParentPad(Value *EHPad) { + if (auto *FPI = dyn_cast(EHPad)) + return FPI->getParentPad(); + + return cast(EHPad)->getParentPad(); +} + void Verifier::visitEHPadPredecessors(Instruction &I) { assert(I.isEHPad()); @@ -2919,16 +2995,45 @@ void Verifier::visitEHPadPredecessors(Instruction &I) { "Block containg CatchPadInst must be jumped to " "only by its catchswitch.", CPI); + Assert(BB != CPI->getCatchSwitch()->getUnwindDest(), + "Catchswitch cannot unwind to one of its catchpads", + CPI->getCatchSwitch(), CPI); return; } + // Verify that each pred has a legal terminator with a legal to/from EH + // pad relationship. + Instruction *ToPad = &I; + Value *ToPadParent = getParentPad(ToPad); for (BasicBlock *PredBB : predecessors(BB)) { TerminatorInst *TI = PredBB->getTerminator(); + Value *FromPad; if (auto *II = dyn_cast(TI)) { Assert(II->getUnwindDest() == BB && II->getNormalDest() != BB, - "EH pad must be jumped to via an unwind edge", &I, II); - } else if (!isa(TI) && !isa(TI)) { - Assert(false, "EH pad must be jumped to via an unwind edge", &I, TI); + "EH pad must be jumped to via an unwind edge", ToPad, II); + if (auto Bundle = II->getOperandBundle(LLVMContext::OB_funclet)) + FromPad = Bundle->Inputs[0]; + else + FromPad = ConstantTokenNone::get(II->getContext()); + } else if (auto *CRI = dyn_cast(TI)) { + FromPad = CRI->getCleanupPad(); + Assert(FromPad != ToPadParent, "A cleanupret must exit its cleanup", CRI); + } else if (auto *CSI = dyn_cast(TI)) { + FromPad = CSI; + } else { + Assert(false, "EH pad must be jumped to via an unwind edge", ToPad, TI); + } + + // The edge may exit from zero or more nested pads. + for (;; FromPad = getParentPad(FromPad)) { + Assert(FromPad != ToPad, + "EH pad cannot handle exceptions raised within it", FromPad, TI); + if (FromPad == ToPadParent) { + // This is a legal unwind edge. + break; + } + Assert(!isa(FromPad), + "A single unwind edge may only enter one EH pad", TI); } } } @@ -2992,7 +3097,7 @@ void Verifier::visitCatchPadInst(CatchPadInst &CPI) { Assert(BB->getFirstNonPHI() == &CPI, "CatchPadInst not the first non-PHI instruction in the block.", &CPI); - visitInstruction(CPI); + visitFuncletPadInst(CPI); } void Verifier::visitCatchReturnInst(CatchReturnInst &CatchReturn) { @@ -3022,33 +3127,160 @@ void Verifier::visitCleanupPadInst(CleanupPadInst &CPI) { Assert(isa(ParentPad) || isa(ParentPad), "CleanupPadInst has an invalid parent.", &CPI); + visitFuncletPadInst(CPI); +} + +void Verifier::visitFuncletPadInst(FuncletPadInst &FPI) { User *FirstUser = nullptr; - BasicBlock *FirstUnwindDest = nullptr; - for (User *U : CPI.users()) { - BasicBlock *UnwindDest; - if (CleanupReturnInst *CRI = dyn_cast(U)) { - UnwindDest = CRI->getUnwindDest(); - } else if (isa(U) || isa(U)) { - continue; - } else if (CallSite(U)) { - continue; - } else { - Assert(false, "bogus cleanuppad use", &CPI); + Value *FirstUnwindPad = nullptr; + SmallVector Worklist({&FPI}); + while (!Worklist.empty()) { + FuncletPadInst *CurrentPad = Worklist.pop_back_val(); + Value *UnresolvedAncestorPad = nullptr; + for (User *U : CurrentPad->users()) { + BasicBlock *UnwindDest; + if (auto *CRI = dyn_cast(U)) { + UnwindDest = CRI->getUnwindDest(); + } else if (auto *CSI = dyn_cast(U)) { + // We allow catchswitch unwind to caller to nest + // within an outer pad that unwinds somewhere else, + // because catchswitch doesn't have a nounwind variant. + // See e.g. SimplifyCFGOpt::SimplifyUnreachable. + if (CSI->unwindsToCaller()) + continue; + UnwindDest = CSI->getUnwindDest(); + } else if (auto *II = dyn_cast(U)) { + UnwindDest = II->getUnwindDest(); + } else if (isa(U)) { + // Calls which don't unwind may be found inside funclet + // pads that unwind somewhere else. We don't *require* + // such calls to be annotated nounwind. + continue; + } else if (auto *CPI = dyn_cast(U)) { + // The unwind dest for a cleanup can only be found by + // recursive search. Add it to the worklist, and we'll + // search for its first use that determines where it unwinds. + Worklist.push_back(CPI); + continue; + } else { + Assert(isa(U), "Bogus funclet pad use", U); + continue; + } + + Value *UnwindPad; + bool ExitsFPI; + if (UnwindDest) { + UnwindPad = UnwindDest->getFirstNonPHI(); + Value *UnwindParent = getParentPad(UnwindPad); + // Ignore unwind edges that don't exit CurrentPad. + if (UnwindParent == CurrentPad) + continue; + // Determine whether the original funclet pad is exited, + // and if we are scanning nested pads determine how many + // of them are exited so we can stop searching their + // children. + Value *ExitedPad = CurrentPad; + ExitsFPI = false; + do { + if (ExitedPad == &FPI) { + ExitsFPI = true; + // Now we can resolve any ancestors of CurrentPad up to + // FPI, but not including FPI since we need to make sure + // to check all direct users of FPI for consistency. + UnresolvedAncestorPad = &FPI; + break; + } + Value *ExitedParent = getParentPad(ExitedPad); + if (ExitedParent == UnwindParent) { + // ExitedPad is the ancestor-most pad which this unwind + // edge exits, so we can resolve up to it, meaning that + // ExitedParent is the first ancestor still unresolved. + UnresolvedAncestorPad = ExitedParent; + break; + } + ExitedPad = ExitedParent; + } while (!isa(ExitedPad)); + } else { + // Unwinding to caller exits all pads. + UnwindPad = ConstantTokenNone::get(FPI.getContext()); + ExitsFPI = true; + UnresolvedAncestorPad = &FPI; + } + + if (ExitsFPI) { + // This unwind edge exits FPI. Make sure it agrees with other + // such edges. + if (FirstUser) { + Assert(UnwindPad == FirstUnwindPad, "Unwind edges out of a funclet " + "pad must have the same unwind " + "dest", + &FPI, U, FirstUser); + } else { + FirstUser = U; + FirstUnwindPad = UnwindPad; + // Record cleanup sibling unwinds for verifySiblingFuncletUnwinds + if (isa(&FPI) && !isa(UnwindPad) && + getParentPad(UnwindPad) == getParentPad(&FPI)) + SiblingFuncletInfo[&FPI] = cast(U); + } + } + // Make sure we visit all uses of FPI, but for nested pads stop as + // soon as we know where they unwind to. + if (CurrentPad != &FPI) + break; + } + if (UnresolvedAncestorPad) { + if (CurrentPad == UnresolvedAncestorPad) { + // When CurrentPad is FPI itself, we don't mark it as resolved even if + // we've found an unwind edge that exits it, because we need to verify + // all direct uses of FPI. + assert(CurrentPad == &FPI); + continue; + } + // Pop off the worklist any nested pads that we've found an unwind + // destination for. The pads on the worklist are the uncles, + // great-uncles, etc. of CurrentPad. We've found an unwind destination + // for all ancestors of CurrentPad up to but not including + // UnresolvedAncestorPad. + Value *ResolvedPad = CurrentPad; + while (!Worklist.empty()) { + Value *UnclePad = Worklist.back(); + Value *AncestorPad = getParentPad(UnclePad); + // Walk ResolvedPad up the ancestor list until we either find the + // uncle's parent or the last resolved ancestor. + while (ResolvedPad != AncestorPad) { + Value *ResolvedParent = getParentPad(ResolvedPad); + if (ResolvedParent == UnresolvedAncestorPad) { + break; + } + ResolvedPad = ResolvedParent; + } + // If the resolved ancestor search didn't find the uncle's parent, + // then the uncle is not yet resolved. + if (ResolvedPad != AncestorPad) + break; + // This uncle is resolved, so pop it from the worklist. + Worklist.pop_back(); + } } + } - if (!FirstUser) { - FirstUser = U; - FirstUnwindDest = UnwindDest; - } else { - Assert( - UnwindDest == FirstUnwindDest, - "cleanupret instructions from the same cleanuppad must have the same " - "unwind destination", - FirstUser, U); + if (FirstUnwindPad) { + if (auto *CatchSwitch = dyn_cast(FPI.getParentPad())) { + BasicBlock *SwitchUnwindDest = CatchSwitch->getUnwindDest(); + Value *SwitchUnwindPad; + if (SwitchUnwindDest) + SwitchUnwindPad = SwitchUnwindDest->getFirstNonPHI(); + else + SwitchUnwindPad = ConstantTokenNone::get(FPI.getContext()); + Assert(SwitchUnwindPad == FirstUnwindPad, + "Unwind edges out of a catch must have the same unwind dest as " + "the parent catchswitch", + &FPI, FirstUser, CatchSwitch); } } - visitInstruction(CPI); + visitInstruction(FPI); } void Verifier::visitCatchSwitchInst(CatchSwitchInst &CatchSwitch) { @@ -3067,17 +3299,21 @@ void Verifier::visitCatchSwitchInst(CatchSwitchInst &CatchSwitch) { "CatchSwitchInst not the first non-PHI instruction in the block.", &CatchSwitch); + auto *ParentPad = CatchSwitch.getParentPad(); + Assert(isa(ParentPad) || isa(ParentPad), + "CatchSwitchInst has an invalid parent.", ParentPad); + if (BasicBlock *UnwindDest = CatchSwitch.getUnwindDest()) { Instruction *I = UnwindDest->getFirstNonPHI(); Assert(I->isEHPad() && !isa(I), "CatchSwitchInst must unwind to an EH block which is not a " "landingpad.", &CatchSwitch); - } - auto *ParentPad = CatchSwitch.getParentPad(); - Assert(isa(ParentPad) || isa(ParentPad), - "CatchSwitchInst has an invalid parent.", ParentPad); + // Record catchswitch sibling unwinds for verifySiblingFuncletUnwinds + if (getParentPad(I) == ParentPad) + SiblingFuncletInfo[&CatchSwitch] = &CatchSwitch; + } Assert(CatchSwitch.getNumHandlers() != 0, "CatchSwitchInst cannot have empty handler list", &CatchSwitch); @@ -3652,6 +3888,9 @@ void Verifier::visitIntrinsicCallSite(Intrinsic::ID ID, CallSite CS) { case Intrinsic::experimental_gc_relocate: { Assert(CS.getNumArgOperands() == 3, "wrong number of arguments", CS); + Assert(isa(CS.getType()->getScalarType()), + "gc.relocate must return a pointer or a vector of pointers", CS); + // Check that this relocate is correctly tied to the statepoint // This is case for relocate on the unwinding path of an invoke statepoint @@ -3734,17 +3973,20 @@ void Verifier::visitIntrinsicCallSite(Intrinsic::ID ID, CallSite CS) { "'gc parameters' section of the statepoint call", CS); - // Relocated value must be a pointer type, but gc_relocate does not need to return the - // same pointer type as the relocated pointer. It can be casted to the correct type later - // if it's desired. However, they must have the same address space. + // Relocated value must be either a pointer type or vector-of-pointer type, + // but gc_relocate does not need to return the same pointer type as the + // relocated pointer. It can be casted to the correct type later if it's + // desired. However, they must have the same address space and 'vectorness' GCRelocateInst &Relocate = cast(*CS.getInstruction()); - Assert(Relocate.getDerivedPtr()->getType()->isPointerTy(), + Assert(Relocate.getDerivedPtr()->getType()->getScalarType()->isPointerTy(), "gc.relocate: relocated value must be a gc pointer", CS); - // gc_relocate return type must be a pointer type, and is verified earlier in - // VerifyIntrinsicType(). - Assert(cast(CS.getType())->getAddressSpace() == - cast(Relocate.getDerivedPtr()->getType())->getAddressSpace(), + auto ResultType = CS.getType(); + auto DerivedType = Relocate.getDerivedPtr()->getType(); + Assert(ResultType->isVectorTy() == DerivedType->isVectorTy(), + "gc.relocate: vector relocates to vector and pointer to pointer", CS); + Assert(ResultType->getPointerAddressSpace() == + DerivedType->getPointerAddressSpace(), "gc.relocate: relocating a pointer shouldn't change its address space", CS); break; } @@ -3845,15 +4087,34 @@ static uint64_t getVariableSize(const DILocalVariable &V, const MapTy &Map) { } template -void Verifier::verifyBitPieceExpression(const DbgInfoIntrinsic &I, - const MapTy &TypeRefs) { +void Verifier::verifyDIExpression(const DbgInfoIntrinsic &I, + const MapTy &TypeRefs) { DILocalVariable *V; DIExpression *E; + const Value *Arg; + uint64_t ArgumentTypeSizeInBits = 0; if (auto *DVI = dyn_cast(&I)) { + Arg = DVI->getValue(); + if (Arg) + ArgumentTypeSizeInBits = + M->getDataLayout().getTypeAllocSizeInBits(Arg->getType()); V = dyn_cast_or_null(DVI->getRawVariable()); E = dyn_cast_or_null(DVI->getRawExpression()); } else { auto *DDI = cast(&I); + // For declare intrinsics, get the total size of the alloca, to allow + // case where the variable may span more than one element. + Arg = DDI->getAddress(); + if (Arg) + Arg = Arg->stripPointerCasts(); + const AllocaInst *AI = dyn_cast_or_null(Arg); + if (AI) { + // We can only say something about constant size allocations + if (const ConstantInt *CI = dyn_cast(AI->getArraySize())) + ArgumentTypeSizeInBits = + CI->getLimitedValue() * + M->getDataLayout().getTypeAllocSizeInBits(AI->getAllocatedType()); + } V = dyn_cast_or_null(DDI->getRawVariable()); E = dyn_cast_or_null(DDI->getRawExpression()); } @@ -3862,10 +4123,6 @@ void Verifier::verifyBitPieceExpression(const DbgInfoIntrinsic &I, if (!V || !E || !E->isValid()) return; - // Nothing to do if this isn't a bit piece expression. - if (!E->isBitPiece()) - return; - // The frontend helps out GDB by emitting the members of local anonymous // unions as artificial local variables with shared storage. When SROA splits // the storage for artificial local variables that are smaller than the entire @@ -3881,11 +4138,33 @@ void Verifier::verifyBitPieceExpression(const DbgInfoIntrinsic &I, if (!VarSize) return; - unsigned PieceSize = E->getBitPieceSize(); - unsigned PieceOffset = E->getBitPieceOffset(); - Assert(PieceSize + PieceOffset <= VarSize, - "piece is larger than or outside of variable", &I, V, E); - Assert(PieceSize != VarSize, "piece covers entire variable", &I, V, E); + if (E->isBitPiece()) { + unsigned PieceSize = E->getBitPieceSize(); + unsigned PieceOffset = E->getBitPieceOffset(); + Assert(PieceSize + PieceOffset <= VarSize, + "piece is larger than or outside of variable", &I, V, E); + Assert(PieceSize != VarSize, "piece covers entire variable", &I, V, E); + return; + } + + if (!ArgumentTypeSizeInBits) + return; // We were unable to determine the size of the argument + + if (E->getNumElements() == 0) { + // In the case where the expression is empty, verify the size of the + // argument. Doing this in the general case would require looking through + // any dereferences that may be in the expression. + Assert(ArgumentTypeSizeInBits == VarSize, + "size of passed value (" + utostr(ArgumentTypeSizeInBits) + + ") does not match size of declared variable (" + + utostr(VarSize) + ")", + &I, Arg, V, V->getType(), E); + } else if (E->getElement(0) == dwarf::DW_OP_deref) { + Assert(ArgumentTypeSizeInBits == M->getDataLayout().getPointerSizeInBits(), + "the operation of the expression is a deref, but the passed value " + "is not pointer sized", + &I, Arg, V, V->getType(), E); + } } void Verifier::visitUnresolvedTypeRef(const MDString *S, const MDNode *N) { @@ -3918,7 +4197,7 @@ void Verifier::verifyTypeRefs() { for (const BasicBlock &BB : F) for (const Instruction &I : BB) if (auto *DII = dyn_cast(&I)) - verifyBitPieceExpression(*DII, TypeRefs); + verifyDIExpression(*DII, TypeRefs); // Return early if all typerefs were resolved. if (UnresolvedTypeRefs.empty())