From af36d02430d66212c6bcab713199f2ab74c03a16 Mon Sep 17 00:00:00 2001 From: Davide Italiano Date: Thu, 13 Apr 2017 20:36:59 +0000 Subject: [PATCH] [LCSSA] Efficiently compute blocks dominating at least one exit. For LCSSA purposes, loop BBs not dominating any of the exits aren't interesting, as none of the values defined in these blocks can be used outside the loop. The way the code computed this information was by comparing each BB of the loop with each of the exit blocks and ask the dominator tree about their dominance relation. This is slow. A more efficient way, implemented here, is that of starting from the exit blocks and walking the dom upwards until we hit an header. By transitivity, all the blocks we encounter in our path dominate an exit. For the testcase provided in PR31851, this reduces compile time on `opt -O2` by ~25%, going from 1m47s to 1m22s. Thanks to Dan/MichaelZ for discussions/suggesting the approach/review. Differential Revision: https://reviews.llvm.org/D31843 llvm-svn: 300255 --- llvm/lib/Transforms/Utils/LCSSA.cpp | 73 +++++++++++++++++++++++++++---------- 1 file changed, 54 insertions(+), 19 deletions(-) diff --git a/llvm/lib/Transforms/Utils/LCSSA.cpp b/llvm/lib/Transforms/Utils/LCSSA.cpp index 493c7c0..49b4bd9 100644 --- a/llvm/lib/Transforms/Utils/LCSSA.cpp +++ b/llvm/lib/Transforms/Utils/LCSSA.cpp @@ -238,40 +238,75 @@ bool llvm::formLCSSAForInstructions(SmallVectorImpl &Worklist, return Changed; } -/// Return true if the specified block dominates at least -/// one of the blocks in the specified list. -static bool -blockDominatesAnExit(BasicBlock *BB, - DominatorTree &DT, - const SmallVectorImpl &ExitBlocks) { - DomTreeNode *DomNode = DT.getNode(BB); - return any_of(ExitBlocks, [&](BasicBlock *EB) { - return DT.dominates(DomNode, DT.getNode(EB)); - }); +// Compute the set of BasicBlocks in the loop `L` dominating at least one exit. +static void computeBlocksDominatingExits( + Loop &L, DominatorTree &DT, SmallVector &ExitBlocks, + SmallPtrSet &BlocksDominatingExits) { + SmallVector BBWorklist; + + // We start from the exit blocks, as every block trivially dominates itself + // (not strictly). + for (BasicBlock *BB : ExitBlocks) + BBWorklist.push_back(BB); + + while (!BBWorklist.empty()) { + BasicBlock *BB = BBWorklist.pop_back_val(); + + // Check if this is a loop header. If this is the case, we're done. + if (L.getHeader() == BB) + continue; + + // Otherwise, add its immediate predecessor in the dominator tree to the + // worklist, unless we visited it already. + BasicBlock *IDomBB = DT.getNode(BB)->getIDom()->getBlock(); + + // Exit blocks can have an immediate dominator not beloinging to the + // loop. For an exit block to be immediately dominated by another block + // outside the loop, it implies not all paths from that dominator, to the + // exit block, go through the loop. + // Example: + // + // |---- A + // | | + // | B<-- + // | | | + // |---> C -- + // | + // D + // + // C is the exit block of the loop and it's immediately dominated by A, + // which doesn't belong to the loop. + if (!L.contains(IDomBB)) + continue; + + if (BlocksDominatingExits.insert(IDomBB).second) + BBWorklist.push_back(IDomBB); + } } bool llvm::formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution *SE) { bool Changed = false; - // Get the set of exiting blocks. SmallVector ExitBlocks; L.getExitBlocks(ExitBlocks); - if (ExitBlocks.empty()) return false; + SmallPtrSet BlocksDominatingExits; + + // We want to avoid use-scanning leveraging dominance informations. + // If a block doesn't dominate any of the loop exits, the none of the values + // defined in the loop can be used outside. + // We compute the set of blocks fullfilling the conditions in advance + // walking the dominator tree upwards until we hit a loop header. + computeBlocksDominatingExits(L, DT, ExitBlocks, BlocksDominatingExits); + SmallVector Worklist; // Look at all the instructions in the loop, checking to see if they have uses // outside the loop. If so, put them into the worklist to rewrite those uses. - for (BasicBlock *BB : L.blocks()) { - // For large loops, avoid use-scanning by using dominance information: In - // particular, if a block does not dominate any of the loop exits, then none - // of the values defined in the block could be used outside the loop. - if (!blockDominatesAnExit(BB, DT, ExitBlocks)) - continue; - + for (BasicBlock *BB : BlocksDominatingExits) { for (Instruction &I : *BB) { // Reject two common cases fast: instructions with no uses (like stores) // and instructions with one use that is in the same block as this. -- 2.7.4