From 4ef096b0c235b7dade47d6b43951697098b30e9d Mon Sep 17 00:00:00 2001 From: Adam Nemet Date: Mon, 5 Jun 2017 16:27:09 +0000 Subject: Handle non-unique edges in edge-dominance This removes a quadratic behavior in assert-enabled builds. GVN propagates the equivalence from a condition into the blocks guarded by the condition. E.g. for 'if (a == 7) { ... }', 'a' will be replaced in the block with 7. It does this by replacing all the uses of 'a' that are dominated by the true edge. For a switch with N cases and U uses of the value, this will mean N * U calls to 'dominates'. Asserting isSingleEdge in 'dominates' make this N^2 * U because this function checks for the uniqueness of the edge. I.e. traverses each edge between the SwitchInst's block and the cases. The change removes the assert and makes 'dominates' works correctly in the presence of non-unique edges. This brings build time down by an order of magnitude for an input that has ~10k cases in a switch statement. Differential Revision: https://reviews.llvm.org/D33584 llvm-svn: 304721 --- llvm/lib/IR/Dominators.cpp | 20 +++++++------------- 1 file changed, 7 insertions(+), 13 deletions(-) (limited to 'llvm/lib/IR/Dominators.cpp') diff --git a/llvm/lib/IR/Dominators.cpp b/llvm/lib/IR/Dominators.cpp index 44948cc5831..37e735251fd 100644 --- a/llvm/lib/IR/Dominators.cpp +++ b/llvm/lib/IR/Dominators.cpp @@ -150,12 +150,6 @@ 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() && - "This function is not efficient in handling multiple edges"); - // If the BB the edge ends in doesn't dominate the use BB, then the // edge also doesn't. const BasicBlock *Start = BBE.getStart(); @@ -188,11 +182,17 @@ bool DominatorTree::dominates(const BasicBlockEdge &BBE, // trivially dominates itself, so we only have to find if it dominates the // other predecessors. Since the only way out of X is via NormalDest, X can // only properly dominate a node if NormalDest dominates that node too. + int IsDuplicateEdge = 0; for (const_pred_iterator PI = pred_begin(End), E = pred_end(End); PI != E; ++PI) { const BasicBlock *BB = *PI; - if (BB == Start) + if (BB == Start) { + // If there are multiple edges between Start and End, by definition they + // can't dominate anything. + if (IsDuplicateEdge++) + return false; continue; + } if (!dominates(End, BB)) return false; @@ -201,12 +201,6 @@ 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() && - "This function is not efficient in handling multiple edges"); - Instruction *UserInst = cast(U.getUser()); // A PHI in the end of the edge is dominated by it. PHINode *PN = dyn_cast(UserInst); -- cgit v1.2.3