Don't attempt to split subloops out of a loop with a huge number of backedges.

Not only will this take huge amounts of compile time, the resultant loop nests
won't be useful for optimization.  This reduces loopsimplify time on
Transforms/LoopSimplify/2006-08-11-LoopSimplifyLongTime.ll from ~32s to ~0.4s
with a debug build of llvm on a 2.7Ghz G5.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@29647 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 19 insertions, 8 deletions

diff --git a/lib/Transforms/Utils/LoopSimplify.cpp b/lib/Transforms/Utils/LoopSimplify.cpp
index 7289f22..a4526e2 100644
--- a/lib/Transforms/Utils/LoopSimplify.cpp
+++ b/lib/Transforms/Utils/LoopSimplify.cpp
@@ -168,6 +168,8 @@ bool LoopSimplify::runOnFunction(Function &F) {
 ///
 bool LoopSimplify::ProcessLoop(Loop *L) {
   bool Changed = false;
+ReprocessLoop:
+  
   // Canonicalize inner loops before outer loops.  Inner loop canonicalization
   // can provide work for the outer loop to canonicalize.
   for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
@@ -208,16 +210,25 @@ bool LoopSimplify::ProcessLoop(Loop *L) {
 
   // If the header has more than two predecessors at this point (from the
   // preheader and from multiple backedges), we must adjust the loop.
-  if (L->getNumBackEdges() != 1) {
-    
-    // If this is really a nested loop, rip it out into a child loop.
-    if (Loop *NL = SeparateNestedLoop(L)) {
-      ++NumNested;
-      // This is a big restructuring change, reprocess the whole loop.
-      ProcessLoop(NL);
-      return true;
+  unsigned NumBackedges = L->getNumBackEdges();
+  if (NumBackedges != 1) {
+    // If this is really a nested loop, rip it out into a child loop.  Don't do
+    // this for loops with a giant number of backedges, just factor them into a
+    // common backedge instead.
+    if (NumBackedges < 8) {
+      if (Loop *NL = SeparateNestedLoop(L)) {
+        ++NumNested;
+        // This is a big restructuring change, reprocess the whole loop.
+        ProcessLoop(NL);
+        Changed = true;
+        // GCC doesn't tail recursion eliminate this.
+        goto ReprocessLoop;
+      }
     }
 
+    // If we either couldn't, or didn't want to, identify nesting of the loops,
+    // insert a new block that all backedges target, then make it jump to the
+    // loop header.
     InsertUniqueBackedgeBlock(L);
     NumInserted++;
     Changed = true;