From 507e3d6dc3face0d68eaf30e30dac07dc948ea2f Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Thu, 15 Jul 2004 04:27:04 +0000 Subject: [PATCH] Fix PR404: Loop simplify is really slow on 252.eon This eliminates an N*N*logN algorithm from the loop simplify pass, replacing it with a much simpler and faster alternative. In a debug build, this reduces gccas time on eon from 85s to 42s. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@14851 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Utils/LoopSimplify.cpp | 24 ++++++++++++------------ 1 file changed, 12 insertions(+), 12 deletions(-) diff --git a/lib/Transforms/Utils/LoopSimplify.cpp b/lib/Transforms/Utils/LoopSimplify.cpp index b2752089d44..9f8373e5450 100644 --- a/lib/Transforms/Utils/LoopSimplify.cpp +++ b/lib/Transforms/Utils/LoopSimplify.cpp @@ -147,6 +147,9 @@ bool LoopSimplify::ProcessLoop(Loop *L) { Changed = true; } + + DominatorSet &DS = getAnalysis(); // Update dominator info + // Next, check to make sure that all exit nodes of the loop only have // predecessors that are inside of the loop. This check guarantees that the // loop preheader/header will dominate the exit blocks. If the exit block has @@ -155,19 +158,16 @@ bool LoopSimplify::ProcessLoop(Loop *L) { L->getExitBlocks(ExitBlocks); for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { BasicBlock *ExitBlock = ExitBlocks[i]; - for (pred_iterator PI = pred_begin(ExitBlock), PE = pred_end(ExitBlock); - PI != PE; ++PI) - if (!L->contains(*PI)) { - BasicBlock *NewBB = RewriteLoopExitBlock(L, ExitBlock); - for (unsigned j = i; j != ExitBlocks.size(); ++j) - if (ExitBlocks[j] == ExitBlock) - ExitBlocks[j] = NewBB; - - NumInserted++; - Changed = true; - break; - } + if (!DS.dominates(L->getHeader(), ExitBlock)) { + BasicBlock *NewBB = RewriteLoopExitBlock(L, ExitBlock); + for (unsigned j = i; j != ExitBlocks.size(); ++j) + if (ExitBlocks[j] == ExitBlock) + ExitBlocks[j] = NewBB; + + NumInserted++; + Changed = true; } + } // If the header has more than two predecessors at this point (from the // preheader and from multiple backedges), we must adjust the loop. -- 2.34.1