[LPM] Fix PR18616 where the shifts to the loop pass manager to extract

LCSSA from it caused a crasher with the LoopUnroll pass.

This crasher is really nasty. We destroy LCSSA form in a suprising way.
When unrolling a loop into an outer loop, we not only need to restore
LCSSA form for the outer loop, but for all children of the outer loop.
This is somewhat obvious in retrospect, but hey!

While this seems pretty heavy-handed, it's not that bad. Fundamentally,
we only do this when we unroll a loop, which is already a heavyweight
operation. We're unrolling all of these hypothetical inner loops as
well, so their size and complexity is already on the critical path. This
is just adding another pass over them to re-canonicalize.

I have a test case from PR18616 that is great for reproducing this, but
pretty useless to check in as it relies on many 10s of nested empty
loops that get unrolled and deleted in just the right order. =/ What's
worse is that investigating this has exposed another source of failure
that is likely to be even harder to test. I'll try to come up with test
cases for these fixes, but I want to get the fixes into the tree first
as they're causing crashes in the wild.

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

diff --git a/include/llvm/Transforms/Utils/LoopUtils.h b/include/llvm/Transforms/Utils/LoopUtils.h
index 5864e22e135d92e9b953967ed9a7ccad845b2cb0..64e18ca1b6d7a48b6b614ddf9792048c15a2b93c 100644 (file)
--- a/include/llvm/Transforms/Utils/LoopUtils.h
+++ b/include/llvm/Transforms/Utils/LoopUtils.h
@@ -47,6 +47,17 @@ bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, Pass *PP,
 /// Returns true if any modifications are made to the loop.
 bool formLCSSA(Loop &L, DominatorTree &DT, ScalarEvolution *SE = 0);
 
+/// \brief Put a loop nest into LCSSA form.
+///
+/// This recursively forms LCSSA for a loop nest.
+///
+/// LoopInfo and DominatorTree are required and preserved.
+///
+/// If ScalarEvolution is passed in, it will be preserved.
+///
+/// Returns true if any modifications are made to the loop.
+bool formLCSSARecursively(Loop &L, DominatorTree &DT, ScalarEvolution *SE = 0);
+
 }
 
 #endif

diff --git a/lib/Transforms/Utils/LCSSA.cpp b/lib/Transforms/Utils/LCSSA.cpp
index 546f4b160a5ee22a7362587118ee6a7a8d482d9f..5959324da6c574aea950dca1d6be99a810d65711 100644 (file)
--- a/lib/Transforms/Utils/LCSSA.cpp
+++ b/lib/Transforms/Utils/LCSSA.cpp
@@ -226,6 +226,19 @@ bool llvm::formLCSSA(Loop &L, DominatorTree &DT, ScalarEvolution *SE) {
   return Changed;
 }
 
+/// Process a loop nest depth first.
+bool llvm::formLCSSARecursively(Loop &L, DominatorTree &DT,
+                                ScalarEvolution *SE) {
+  bool Changed = false;
+
+  // Recurse depth-first through inner loops.
+  for (Loop::iterator LI = L.begin(), LE = L.end(); LI != LE; ++LI)
+    Changed |= formLCSSARecursively(**LI, DT, SE);
+
+  Changed |= formLCSSA(L, DT, SE);
+  return Changed;
+}
+
 namespace {
 struct LCSSA : public FunctionPass {
   static char ID; // Pass identification, replacement for typeid
@@ -278,20 +291,8 @@ bool LCSSA::runOnFunction(Function &F) {
 
   // Simplify each loop nest in the function.
   for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
-    Changed |= processLoop(**I);
-
-  return Changed;
-}
-
-/// Process a loop nest depth first.
-bool LCSSA::processLoop(Loop &L) {
-  bool Changed = false;
-
-  // Recurse depth-first through inner loops.
-  for (Loop::iterator LI = L.begin(), LE = L.end(); LI != LE; ++LI)
-    Changed |= processLoop(**LI);
+    Changed |= formLCSSARecursively(**I, *DT, SE);
 
-  Changed |= formLCSSA(L, *DT, SE);
   return Changed;
 }
 

diff --git a/lib/Transforms/Utils/LoopUnroll.cpp b/lib/Transforms/Utils/LoopUnroll.cpp
index 3c43fbbe828cb2c9ab8c57deb011db7e56127651..d2dfc20e4d8e9f681e7127d05137f6ca5fe32fcb 100644 (file)
--- a/lib/Transforms/Utils/LoopUnroll.cpp
+++ b/lib/Transforms/Utils/LoopUnroll.cpp
@@ -468,9 +468,11 @@ bool llvm::UnrollLoop(Loop *L, unsigned Count, unsigned TripCount,
   if (PP && DT) {
     if (!OuterL && !CompletelyUnroll)
       OuterL = L;
-    if (OuterL)
-      simplifyLoop(OuterL, DT, LI, PP, /*AliasAnalysis*/ 0,
-                   PP->getAnalysisIfAvailable<ScalarEvolution>());
+    if (OuterL) {
+      ScalarEvolution *SE = PP->getAnalysisIfAvailable<ScalarEvolution>();
+      simplifyLoop(OuterL, DT, LI, PP, /*AliasAnalysis*/ 0, SE);
+      formLCSSARecursively(*OuterL, *DT, SE);
+    }
   }
 
   return true;