[SimpleLoopUnswitch] Form dedicated exits after trivial unswitches.

[asbirlea]

Summary

Form dedicated exits after trivial unswitches.
Fixes PR38737, PR38283.

[xbolva00]

test/Transforms/SimpleLoopUnswitch/formDedicatedAfterTrivial3.ll

1 ↗

(On Diff #162931)

opt < %s

1 ↗

(On Diff #162931)

avoid -O3

FileCheck?

[fedor.sergeev]

test/Transforms/SimpleLoopUnswitch/formDedicatedAfterTrivial3.ll

1 ↗

(On Diff #162931)

I would rather use a somewhat reduced version of it (getting IR dump just before the failing simple-loop-unswitch) - https://pastebin.com/5qYNZvxa

fails with just:

opt < %s -simple-loop-unswitch

[fedor.sergeev]

source changes LGTM.
comments and suggested test change - up to your discretion.

lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

308 ↗

(On Diff #162931)

instead of "trivial switches" I would say something like:

"after trivial unswitching it is possible to get new non-dedicated exits out of parent loop"

[asbirlea]

Updated test, thank you for the comments!

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

for (BasicBlock *BB : L.blocks())
       OldContainingL->getBlocksSet().erase(BB);
 
     // Because we just hoisted a loop out of this one, we have essentially
     // created new exit paths from it. That means we need to form LCSSA PHI
     // nodes for values used in the no-longer-nested loop.
     formLCSSA(*OldContainingL, DT, &LI, nullptr);
 
     // We shouldn't need to form dedicated exits because the exit introduced
-    // here is the (just split by unswitching) preheader. As such, it is
-    // necessarily dedicated.
-    assert(OldContainingL->hasDedicatedExits() &&
-           "Unexpected predecessor of hoisted loop preheader!");
+    // here is the (just split by unswitching) preheader. However, after trivial
+    // unswitching it is possible to get new non-dedicated exits out of parent
+    // loop so let's conservatively form dedicated exit blocks and figure out
+    // if we can optimize later.
+    formDedicatedExitBlocks(OldContainingL, &DT, &LI, /*PreserveLCSSA*/ true);
   }
 }
 
 /// Unswitch a trivial branch if the condition is loop invariant.
 ///
 /// This routine should only be called when loop code leading to the branch has
 /// been validated as trivial (no side effects). This routine checks if the
 /// condition is invariant and one of the successors is a loop exit. This
static bool unswitchTrivialBranch(Loop &L, BranchInst &BI, DominatorTree &DT,
   for (Value *Invariant : Invariants)
     replaceLoopInvariantUses(L, Invariant, *Replacement);
 
   // If this was full unswitching, we may have changed the nesting relationship
   // for this loop so hoist it to its correct parent if needed.
   if (FullUnswitch)
     hoistLoopToNewParent(L, *NewPH, DT, LI);
 
+  LLVM_DEBUG(dbgs() << "    done: unswitching trivial branch...\n");
   ++NumTrivial;
   ++NumBranches;
   return true;
 }
 
 /// Unswitch a trivial switch if the condition is loop invariant.
 ///
 /// This routine should only be called when loop code leading to the switch has
static bool unswitchTrivialSwitch(Loop &L, SwitchInst &SI, DominatorTree &DT,
   BasicBlock *DefaultExitBB = nullptr;
   if (!L.contains(SI.getDefaultDest()) &&
       areLoopExitPHIsLoopInvariant(L, *ParentBB, *SI.getDefaultDest()) &&
       !isa<UnreachableInst>(SI.getDefaultDest()->getTerminator()))
     DefaultExitBB = SI.getDefaultDest();
   else if (ExitCaseIndices.empty())
     return false;
 
-  LLVM_DEBUG(dbgs() << "    unswitching trivial cases...\n");
+  LLVM_DEBUG(dbgs() << "    unswitching trivial switch...\n");
 
   // We may need to invalidate SCEVs for the outermost loop reached by any of
   // the exits.
   Loop *OuterL = &L;
 
   if (DefaultExitBB) {
     // Clear out the default destination temporarily to allow accurate
     // predecessor lists to be examined below.
static bool unswitchTrivialSwitch(Loop &L, SwitchInst &SI, DominatorTree &DT,
   assert(DT.verify(DominatorTree::VerificationLevel::Fast));
 
   // We may have changed the nesting relationship for this loop so hoist it to
   // its correct parent if needed.
   hoistLoopToNewParent(L, *NewPH, DT, LI);
 
   ++NumTrivial;
   ++NumSwitches;
+  LLVM_DEBUG(dbgs() << "    done: unswitching trivial switch...\n");
   return true;
 }
 
 /// This routine scans the loop to find a branch or switch which occurs before
 /// any side effects occur. These can potentially be unswitched without
 /// duplicating the loop. If a branch or switch is successfully unswitched the
 /// scanning continues to see if subsequent branches or switches have become
 /// trivial. Once all trivial candidates have been unswitched, this routine

llvm/trunk/test/Transforms/SimpleLoopUnswitch/formDedicatedAfterTrivial1.ll

+; RUN: opt < %s -simple-loop-unswitch -disable-output
+
+; PR38283
+; PR38737
+define void @f1() {
+for.cond1thread-pre-split.lr.ph.lr.ph:
+  %tobool4 = icmp eq i16 undef, 0
+  br label %for.cond1thread-pre-split
+
+for.cond1thread-pre-split:                        ; preds = %if.end, %for.cond1thread-pre-split.lr.ph.lr.ph
+  %tobool3 = icmp eq i16 undef, 0
+  br label %for.body2
+
+for.body2:                                        ; preds = %if.end6, %for.cond1thread-pre-split
+  br i1 %tobool3, label %if.end, label %for.end
+
+if.end:                                           ; preds = %for.body2
+  br i1 %tobool4, label %if.end6, label %for.cond1thread-pre-split
+
+if.end6:                                          ; preds = %if.end
+  br i1 undef, label %for.body2, label %for.end
+
+for.end:                                          ; preds = %if.end6, %for.body2
+  ret void
+}

llvm/trunk/test/Transforms/SimpleLoopUnswitch/formDedicatedAfterTrivial2.ll

+; RUN: opt < %s -simple-loop-unswitch -disable-output
+
+; PR38283
+; PR38737
+define void @Test(i32) {
+entry:
+  %trunc = trunc i32 %0 to i3
+  br label %outer
+outer:
+  br label %inner
+inner:
+  switch i3 %trunc, label %crit_edge [
+    i3 2, label %break
+    i3 1, label %loopexit
+  ]
+crit_edge:
+  br i1 true, label %loopexit, label %inner
+loopexit:
+  ret void
+break:
+  br label %outer
+}

llvm/trunk/test/Transforms/SimpleLoopUnswitch/formDedicatedAfterTrivial3.ll

+; RUN: opt < %s -simple-loop-unswitch -disable-output
+
+; PR38283
+; PR38737
+declare void @func_1()
+
+define void @func_9(i32 signext %arg) {
+bb:
+  br label %bb5
+bb5:                                              ; preds = %bb24, %bb
+  %tmp3.0 = phi i32 [ undef, %bb ], [ %tmp29, %bb24 ]
+  %tmp11 = icmp eq i32 %arg, 0
+  %tmp15 = icmp eq i32 %tmp3.0, 0
+  %spec.select = select i1 %tmp15, i32 0, i32 49
+  %tmp1.2 = select i1 %tmp11, i32 %spec.select, i32 9
+  %trunc = trunc i32 %tmp1.2 to i6
+  br label %bb9
+
+bb9:                                              ; preds = %bb5, %bb19
+  %tmp2.03 = phi i32 [ 0, %bb5 ], [ %tmp21, %bb19 ]
+  switch i6 %trunc, label %bb24 [
+    i6 0, label %bb19
+    i6 -15, label %bb22
+  ]
+
+bb19:                                             ; preds = %bb9
+  %tmp21 = add nuw nsw i32 %tmp2.03, 1
+  %tmp8 = icmp eq i32 %tmp21, 25
+  br i1 %tmp8, label %bb22, label %bb9
+
+bb22:                                             ; preds = %bb19, %bb9
+  unreachable
+
+bb24:                                             ; preds = %bb9
+  %tmp29 = or i32 %tmp3.0, 1
+  br label %bb5
+}