[LoopSimplifyCFG] Form LCSSA when a parent loop becomes a sibling

[mkazantsev]

Summary

During the transforms in LoopSimplifyCFG, when we remove a dead exiting edge, the
parent loop may stop being reachable from the child loop, and therefore they become
siblings. If the former child loop had uses of some values from its former parent loop,
now such uses will require LCSSA Phis, even if they weren't needed before. So we must
form LCSSA for all loops that stopped being ancestors of the current loop in this case.

[uabelho]

The problem I saw goes away with this patch and I haven't seen any new failures with the limited testing I've done on the patch. Thanks!
I don't know this code though, so I don't know if this is the way the problem should be solved.

[mkazantsev]

Re-uploaded with context.

[fedor.sergeev]

LGTM.

llvm/trunk/lib/Transforms/Scalar/LoopSimplifyCFG.cpp

if (Loop *OuterLoop = LI.getLoopFor(Preheader)) {
           for (auto *BB : L.blocks())
             NotContaining->removeBlockFromLoop(BB);
         }
         OuterLoop->removeChildLoop(&L);
         if (StillReachable)
           StillReachable->addChildLoop(&L);
         else
           LI.addTopLevelLoop(&L);
+
+        // Some values from loops in [OuterLoop, StillReachable) could be used
+        // in the current loop. Now it is not their child anymore, so such uses
+        // require LCSSA Phis.
+        Loop *FixLCSSALoop = OuterLoop;
+        while (FixLCSSALoop->getParentLoop() != StillReachable)
+          FixLCSSALoop = FixLCSSALoop->getParentLoop();
+        assert(FixLCSSALoop && "Should be a loop!");
+        formLCSSARecursively(*FixLCSSALoop, DT, &LI, &SE);
       }
     }
   }
 
   /// Delete loop blocks that have become unreachable after folding. Make all
   /// relevant updates to DT and LI.
   void deleteDeadLoopBlocks() {
     DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);

llvm/trunk/test/Transforms/LoopSimplifyCFG/lcssa.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; REQUIRES: asserts
 ; RUN: opt -S -enable-loop-simplifycfg-term-folding=true -loop-simplifycfg -verify-loop-info -verify-dom-info -verify-loop-lcssa < %s | FileCheck %s
 ; RUN: opt -S -enable-loop-simplifycfg-term-folding=true -passes='require<domtree>,loop(simplify-cfg)' -verify-loop-info -verify-dom-info -verify-loop-lcssa < %s | FileCheck %s
 ; RUN: opt -S -enable-loop-simplifycfg-term-folding=true -loop-simplifycfg -enable-mssa-loop-dependency=true -verify-memoryssa -verify-loop-info -verify-dom-info -verify-loop-lcssa < %s | FileCheck %s
-; XFAIL: *
-; test_01 is currently failing because the loop is not in LCSSA form after the
-; transform.
 
 target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
 
 define void @c() {
 ; CHECK-LABEL: @c(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[D:%.*]]
 ; CHECK:       d.loopexit:

 if.end.7:                                         ; preds = %if.end
   br i1 true, label %if.end.8, label %d.loopexit
 
 if.end.8:                                         ; preds = %if.end.7
   br label %for.cond
 }
 
 define void @test_01() {
+; CHECK-LABEL: @test_01(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_COND:%.*]]
+; CHECK:       for.cond.loopexit:
+; CHECK-NEXT:    br label [[FOR_COND]]
+; CHECK:       for.cond:
+; CHECK-NEXT:    [[INC41_LCSSA3:%.*]] = phi i16 [ undef, [[FOR_COND_LOOPEXIT:%.*]] ], [ undef, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    switch i32 0, label [[FOR_COND_SPLIT:%.*]] [
+; CHECK-NEXT:    i32 1, label [[FOR_COND_LOOPEXIT]]
+; CHECK-NEXT:    ]
+; CHECK:       for.cond-split:
+; CHECK-NEXT:    [[INC41_LCSSA3_LCSSA:%.*]] = phi i16 [ [[INC41_LCSSA3]], [[FOR_COND]] ]
+; CHECK-NEXT:    br label [[WHILE_COND:%.*]]
+; CHECK:       while.cond:
+; CHECK-NEXT:    [[INC41:%.*]] = phi i16 [ [[INC4:%.*]], [[WHILE_COND]] ], [ [[INC41_LCSSA3_LCSSA]], [[FOR_COND_SPLIT]] ]
+; CHECK-NEXT:    [[INC4]] = add nsw i16 [[INC41]], 1
+; CHECK-NEXT:    br label [[WHILE_COND]]
+;
 entry:
   br label %for.cond
 
 for.cond.loopexit:                                ; preds = %while.cond
   %inc41.lcssa = phi i16 [ %inc41, %while.cond ]
   br label %for.cond
 
 for.cond:                                         ; preds = %for.cond.loopexit, %entry