From d5118c8f78a05ad0b426b6032138d1d934b77c8d Mon Sep 17 00:00:00 2001 From: Rafael Espindola Date: Fri, 17 Aug 2012 18:21:28 +0000 Subject: [PATCH] Assert that dominates is not given a multiple edge. Finding out if we have multiple edges between two blocks is linear. If the caller is iterating all edges leaving a BB that would be a square time algorithm. It is more efficient to have the callers handle that case. Currently the only callers are: * GVN: already avoids the multiple edge case. * Verifier: could only hit this assert when looking at an invalid invoke. Since it already rejects the invoke, just avoid computing the dominance for it. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162113 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/VMCore/Dominators.cpp | 10 ++++++++++ lib/VMCore/Verifier.cpp | 7 +++++++ test/Verifier/invoke.ll | 1 - 3 files changed, 17 insertions(+), 1 deletion(-) diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp index 60bdeac16b3..77b2403d87d 100644 --- a/lib/VMCore/Dominators.cpp +++ b/lib/VMCore/Dominators.cpp @@ -161,6 +161,11 @@ bool DominatorTree::dominates(const Instruction *Def, bool DominatorTree::dominates(const BasicBlockEdge &BBE, const BasicBlock *UseBB) const { + // Assert that we have a single edge. We could handle them by simply + // returning false, but since isSingleEdge is linear on the number of + // edges, the callers can normally handle them more efficiently. + assert(BBE.isSingleEdge()); + // If the BB the edge ends in doesn't dominate the use BB, then the // edge also doesn't. const BasicBlock *Start = BBE.getStart(); @@ -207,6 +212,11 @@ bool DominatorTree::dominates(const BasicBlockEdge &BBE, bool DominatorTree::dominates(const BasicBlockEdge &BBE, const Use &U) const { + // Assert that we have a single edge. We could handle them by simply + // returning false, but since isSingleEdge is linear on the number of + // edges, the callers can normally handle them more efficiently. + assert(BBE.isSingleEdge()); + Instruction *UserInst = cast(U.getUser()); // A PHI in the end of the edge is dominated by it. PHINode *PN = dyn_cast(UserInst); diff --git a/lib/VMCore/Verifier.cpp b/lib/VMCore/Verifier.cpp index 38914b3fe7e..7ff97c34793 100644 --- a/lib/VMCore/Verifier.cpp +++ b/lib/VMCore/Verifier.cpp @@ -1575,6 +1575,13 @@ void Verifier::visitLandingPadInst(LandingPadInst &LPI) { void Verifier::verifyDominatesUse(Instruction &I, unsigned i) { Instruction *Op = cast(I.getOperand(i)); + // If the we have an invalid invoke, don't try to compute the dominance. + // We already reject it in the invoke specific checks and the dominance + // computation doesn't handle multiple edges. + if (InvokeInst *II = dyn_cast(Op)) { + if (II->getNormalDest() == II->getUnwindDest()) + return; + } const Use &U = I.getOperandUse(i); Assert2(InstsInThisBlock.count(Op) || DT->dominates(Op, U), diff --git a/test/Verifier/invoke.ll b/test/Verifier/invoke.ll index a48f9b60feb..c2750bb121f 100644 --- a/test/Verifier/invoke.ll +++ b/test/Verifier/invoke.ll @@ -19,7 +19,6 @@ L2: ; preds = %0 br label %L L: ; preds = %L2, %L1, %L1 ; CHECK: The unwind destination does not have a landingpad instruction -; CHECK: Instruction does not dominate all uses ret i32 %A } -- 2.34.1