[PM/LoopUnswitch] Fix how the cloned loops are handled when updating analyses.

[chandlerc]

Summary

I noticed this issue because we didn't put the primary cloned loop into
the NonChildClonedLoops vector and so never iterated on it. Once
I fixed that, it made it clear why I had to do a really complicated and
unnecesasry dance when updating the loops to remain in canonical form --
I was unwittingly working around the fact that the primary cloned loop
wasn't in the expected list of cloned loops. Doh!

Now that we include it in this vector, we don't need to return it and we
can consolidate the update logic as we correctly have a single place
where it can be handled.

I've just added a test for the iteration order aspect as every time
I changed the update logic partially or incorrectly here, an existing
test failed and caught it so that seems well covered (which is also
evidenced by the extensive working around of this missing update).

[sanjoy]

lgtm

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

 /// backedge set may be different. However, we know that each child loop is
 /// undisturbed, we only need to find where to place each child loop within
 /// either any parent loop or within a cloned version of the original loop.
 ///
 /// Because child loops may end up cloned outside of any cloned version of the
 /// original loop, multiple cloned sibling loops may be created. All of them
 /// are returned so that the newly introduced loop nest roots can be
 /// identified.
-static Loop *buildClonedLoops(Loop &OrigL, ArrayRef<BasicBlock *> ExitBlocks,
-                              const ValueToValueMapTy &VMap, LoopInfo &LI,
-                              SmallVectorImpl<Loop *> &NonChildClonedLoops) {
+static void buildClonedLoops(Loop &OrigL, ArrayRef<BasicBlock *> ExitBlocks,
   Loop *ClonedL = nullptr;
 
   auto *OrigPH = OrigL.getLoopPreheader();
   auto *OrigHeader = OrigL.getHeader();
 
   auto *ClonedPH = cast<BasicBlock>(VMap.lookup(OrigPH));
   auto *ClonedHeader = cast<BasicBlock>(VMap.lookup(OrigHeader));
 
if (!BlocksInClonedLoop.empty()) {
 
     ClonedL = LI.AllocateLoop();
     if (ParentL) {
       ParentL->addBasicBlockToLoop(ClonedPH, LI);
       ParentL->addChildLoop(ClonedL);
     } else {
       LI.addTopLevelLoop(ClonedL);
     }
+    NonChildClonedLoops.push_back(ClonedL);
 
     ClonedL->reserveBlocks(BlocksInClonedLoop.size());
     // We don't want to just add the cloned loop blocks based on how we
     // discovered them. The original order of blocks was carefully built in
     // a way that doesn't rely on predecessor ordering. Rather than re-invent
     // that logic, we just re-walk the original blocks (and those of the child
     // loops) and filter them as we add them into the cloned loop.
     for (auto *BB : OrigL.blocks()) {
#ifndef NDEBUG
     for (auto *ChildLoopBB : ChildL->blocks())
       assert(VMap.count(ChildLoopBB) &&
              "Cloned a child loop header but not all of that loops blocks!");
 #endif
 
     NonChildClonedLoops.push_back(cloneLoopNest(
         *ChildL, ExitLoopMap.lookup(ClonedChildHeader), VMap, LI));
   }
-
-  // Return the main cloned loop if any.
-  return ClonedL;
 }
 
 static void
 deleteDeadBlocksFromLoop(Loop &L,
                          const SmallVectorImpl<BasicBlock *> &DeadBlocks,
                          SmallVectorImpl<BasicBlock *> &ExitBlocks,
                          DominatorTree &DT, LoopInfo &LI) {
   SmallPtrSet<BasicBlock *, 16> DeadBlockSet(DeadBlocks.begin(),
static bool unswitchInvariantBranch(
   DTUpdates.push_back({DominatorTree::Delete, ParentBB, UnswitchedSuccBB});
   DTUpdates.push_back({DominatorTree::Insert, SplitBB, ClonedPH});
   DT.applyUpdates(DTUpdates);
 
   // Build the cloned loop structure itself. This may be substantially
   // different from the original structure due to the simplified CFG. This also
   // handles inserting all the cloned blocks into the correct loops.
   SmallVector<Loop *, 4> NonChildClonedLoops;
-  Loop *ClonedL =
-      buildClonedLoops(L, ExitBlocks, VMap, LI, NonChildClonedLoops);
 
   // Delete anything that was made dead in the original loop due to
   // unswitching.
   if (!DeadBlocks.empty())
     deleteDeadBlocksFromLoop(L, DeadBlocks, ExitBlocks, DT, LI);
 
   SmallVector<Loop *, 4> HoistedLoops;
   bool IsStillLoop = rebuildLoopAfterUnswitch(L, ExitBlocks, LI, HoistedLoops);
static bool unswitchInvariantBranch(
   // FIXME: This could be made more efficient by tracking which exit blocks are
   // new, and focusing on them, but that isn't likely to be necessary.
   //
   // In order to reasonably rebuild LCSSA we need to walk inside-out across the
   // loop nest and update every loop that could have had its exits changed. We
   // also need to cover any intervening loops. We add all of these loops to
   // a list and sort them by loop depth to achieve this without updating
   // unnecessary loops.
-  auto UpdateLCSSA = [&](Loop &UpdateL) {
+  auto UpdateLoop = [&](Loop &UpdateL) {
 #ifndef NDEBUG
     UpdateL.verifyLoop();
     for (Loop *ChildL : UpdateL) {
       ChildL->verifyLoop();
       assert(ChildL->isRecursivelyLCSSAForm(DT, LI) &&
              "Perturbed a child loop's LCSSA form!");
     }
 #endif
+    // First build LCSSA for this loop so that we can preserve it when
+    // forming dedicated exits. We don't want to perturb some other loop's
+    // LCSSA while doing that CFG edit.
     formLCSSA(UpdateL, DT, &LI, nullptr);
+
+    // For loops reached by this loop's original exit blocks we may
+    // introduced new, non-dedicated exits. At least try to re-form dedicated
+    // exits for these loops. This may fail if they couldn't have dedicated
+    // exits to start with.
+    formDedicatedExitBlocks(&UpdateL, &DT, &LI, /*PreserveLCSSA*/ true);
   };
 
   // For non-child cloned loops and hoisted loops, we just need to update LCSSA
   // and we can do it in any order as they don't nest relative to each other.
-  for (Loop *UpdatedL : llvm::concat<Loop *>(NonChildClonedLoops, HoistedLoops))
-    UpdateLCSSA(*UpdatedL);
-
-  // If the original loop had exit blocks, walk up through the outer most loop
-  // of those exit blocks to update LCSSA and form updated dedicated exits.
-  if (OuterExitL != &L) {
-    SmallVector<Loop *, 4> OuterLoops;
-    // We start with the cloned loop and the current loop if they are loops and
-    // move toward OuterExitL. Also, if either the cloned loop or the current
-    // loop have become top level loops we need to walk all the way out.
-    if (ClonedL) {
-      OuterLoops.push_back(ClonedL);
-      if (!ClonedL->getParentLoop())
-        OuterExitL = nullptr;
-    }
-    if (IsStillLoop) {
-      OuterLoops.push_back(&L);
-      if (!L.getParentLoop())
-        OuterExitL = nullptr;
-    }
-    // Grab all of the enclosing loops now.
+  //
+  // Also check if any of the loops we have updated have become top-level loops
+  // as that will necessitate widening the outer loop scope.
+  for (Loop *UpdatedL :
+       llvm::concat<Loop *>(NonChildClonedLoops, HoistedLoops)) {
+    UpdateLoop(*UpdatedL);
+    if (!UpdatedL->getParentLoop())
+    UpdateLoop(L);
+
+  // If the original loop had exit blocks, walk up through the outer most loop
+  // of those exit blocks to update LCSSA and form updated dedicated exits.
+  if (OuterExitL != &L)
     for (Loop *OuterL = ParentL; OuterL != OuterExitL;
          OuterL = OuterL->getParentLoop())
-      OuterLoops.push_back(OuterL);
-
-    // Finally, update our list of outer loops. This is nicely ordered to work
-    // inside-out.
-    for (Loop *OuterL : OuterLoops) {
-      // First build LCSSA for this loop so that we can preserve it when
-      // forming dedicated exits. We don't want to perturb some other loop's
-      // LCSSA while doing that CFG edit.
-      UpdateLCSSA(*OuterL);
-
-      // For loops reached by this loop's original exit blocks we may
-      // introduced new, non-dedicated exits. At least try to re-form dedicated
-      // exits for these loops. This may fail if they couldn't have dedicated
-      // exits to start with.
-      formDedicatedExitBlocks(OuterL, &DT, &LI, /*PreserveLCSSA*/ true);
-    }
-  }
+      UpdateLoop(*OuterL);
 
 #ifndef NDEBUG
   // Verify the entire loop structure to catch any incorrect updates before we
   // progress in the pass pipeline.
   LI.verify(DT);
 #endif
 
   // Now that we've unswitched something, make callbacks to report the changes.

llvm/trunk/test/Transforms/SimpleLoopUnswitch/nontrivial-unswitch.ll

 
 outer.latch:
   %outer.cond = load i1, i1* %ptr
   br i1 %outer.cond, label %outer.header, label %exit
 
 exit:
   ret void
 }
+
+; Non-trivial loop unswitching where there are two invariant conditions, but the
+; second one is only in the cloned copy of the loop after unswitching.
+define i32 @test24(i1* %ptr, i1 %cond1, i1 %cond2) {
+; CHECK-LABEL: @test24(
+entry:
+  br label %loop_begin
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 %cond1, label %entry.split.us, label %entry.split
+
+loop_begin:
+  br i1 %cond1, label %loop_a, label %loop_b
+
+loop_a:
+  br i1 %cond2, label %loop_a_a, label %loop_a_c
+; The second unswitched condition.
+;
+; CHECK:       entry.split.us:
+; CHECK-NEXT:    br i1 %cond2, label %entry.split.us.split.us, label %entry.split.us.split
+
+loop_a_a:
+  call void @a()
+  br label %latch
+; The 'loop_a_a' unswitched loop.
+;
+; CHECK:       entry.split.us.split.us:
+; CHECK-NEXT:    br label %loop_begin.us.us
+;
+; CHECK:       loop_begin.us.us:
+; CHECK-NEXT:    br label %loop_a.us.us
+;
+; CHECK:       loop_a.us.us:
+; CHECK-NEXT:    br label %loop_a_a.us.us
+;
+; CHECK:       loop_a_a.us.us:
+; CHECK-NEXT:    call void @a()
+; CHECK-NEXT:    br label %latch.us.us
+;
+; CHECK:       latch.us.us:
+; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
+; CHECK-NEXT:    br i1 %[[V]], label %loop_begin.us.us, label %loop_exit.split.us.split.us
+;
+; CHECK:       loop_exit.split.us.split.us:
+; CHECK-NEXT:    br label %loop_exit.split
+
+loop_a_c:
+  call void @c()
+  br label %latch
+; The 'loop_a_c' unswitched loop.
+;
+; CHECK:       entry.split.us.split:
+; CHECK-NEXT:    br label %loop_begin.us
+;
+; CHECK:       loop_begin.us:
+; CHECK-NEXT:    br label %loop_a.us
+;
+; CHECK:       loop_a.us:
+; CHECK-NEXT:    br label %loop_a_c.us
+;
+; CHECK:       loop_a_c.us:
+; CHECK-NEXT:    call void @c()
+; CHECK-NEXT:    br label %latch
+;
+; CHECK:       latch.us:
+; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
+; CHECK-NEXT:    br i1 %[[V]], label %loop_begin.us, label %loop_exit.split.us.split
+;
+; CHECK:       loop_exit.split.us.split:
+; CHECK-NEXT:    br label %loop_exit.split
+
+loop_b:
+  call void @b()
+  br label %latch
+; The 'loop_b' unswitched loop.
+;
+; CHECK:       entry.split:
+; CHECK-NEXT:    br label %loop_begin
+;
+; CHECK:       loop_begin:
+; CHECK-NEXT:    br label %loop_b
+;
+; CHECK:       loop_b:
+; CHECK-NEXT:    call void @b()
+; CHECK-NEXT:    br label %latch
+;
+; CHECK:       latch:
+; CHECK-NEXT:    %[[V:.*]] = load i1, i1* %ptr
+; CHECK-NEXT:    br i1 %[[V]], label %loop_begin, label %loop_exit.split
+;
+; CHECK:       loop_exit.split:
+; CHECK-NEXT:    br label %loop_exit
+
+latch:
+  %v = load i1, i1* %ptr
+  br i1 %v, label %loop_begin, label %loop_exit
+
+loop_exit:
+  ret i32 0
+; CHECK:       loop_exit:
+; CHECK-NEXT:    ret
+}
 No newline at end of file