[LoopSimplifyCFG] Check predecessors of exits before marking them dead.

[fhahn]

Summary

LoopSimplifyCFG may process loops that are not in
loop-simplify/canonical form. For loops not in canonical form, exit
blocks may be reachable from non-loop blocks and we cannot consider them
as dead if they only are not reachable from the loop itself.

Unfortunately the smallest test I could come up with requires running
multiple passes:

-passes='loop-mssa(loop-instsimplify,loop-simplifycfg,simple-loop-unswitch)'

The reason is that loops are canonicalized at the beginning of loop
pipelines, so a later transform has to break canonical form in a way
that breaks LoopSimplifyCFG's dead-exit analysis.

Alternatively we could try to require all loop passes to maintain
canonical form. That in turn would also require additional verification.

Fixes #54023.

[nikic]

LGTM

Alternatively we could try to require all loop passes to maintain canonical form. That in turn would also require additional verification.

I think that may be worthwhile to do longer term. I think we have some transforms that bail out if we're not in loop simplify form, so this would ensure that things compose as intended. Also, I suspect that preserving loop simplify form might make preservation simpler overall, for example it should be easier to preserve LCSSA form (don't need to deal with an exit also being a sibling loop header etc).

IIRC the legacy pass manager did not automatically convert to loop simplify form for loop pass managers, which is where the current behavior might be coming from.

llvm/test/Transforms/LoopSimplifyCFG/loop-not-in-simplify-form.ll

6–7

Remove fixme.

llvm/lib/Transforms/Scalar/LoopSimplifyCFG.cpp

for (auto I = DFS.beginRPO(), E = DFS.endRPO(); I != E; ++I) {
         }
     }
 
     // Amount of dead and live loop blocks should match the total number of
     // blocks in loop.
     assert(L.getNumBlocks() == LiveLoopBlocks.size() + DeadLoopBlocks.size() &&
            "Malformed block sets?");
 
-    // Now, all exit blocks that are not marked as live are dead.
+    // Now, all exit blocks that are not marked as live are dead, if all their
+    // predecessors are in the loop. This may not be the case, as the input loop
+    // may not by in loop-simplify/canonical form.
     SmallVector<BasicBlock *, 8> ExitBlocks;
     L.getExitBlocks(ExitBlocks);
     SmallPtrSet<BasicBlock *, 8> UniqueDeadExits;
     for (auto *ExitBlock : ExitBlocks)
       if (!LiveExitBlocks.count(ExitBlock) &&
-          UniqueDeadExits.insert(ExitBlock).second)
+          UniqueDeadExits.insert(ExitBlock).second &&
+          all_of(predecessors(ExitBlock),
+                 [this](BasicBlock *Pred) { return L.contains(Pred); }))
         DeadExitBlocks.push_back(ExitBlock);
 
     // Whether or not the edge From->To will still be present in graph after the
     // folding.
     auto IsEdgeLive = [&](BasicBlock *From, BasicBlock *To) {
       if (!LiveLoopBlocks.count(From))
         return false;
       BasicBlock *TheOnlySucc = getOnlyLiveSuccessor(From);

llvm/test/Transforms/LoopSimplifyCFG/loop-not-in-simplify-form.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes='loop-mssa(loop-instsimplify,loop-simplifycfg,simple-loop-unswitch)' -S %s | FileCheck %s
 
 ; Test case from PR54023. After SimpleLoopUnswitch, one of the loops processed
 ; by LoopSimplifyCFG will have exit blocks with predecessors outside the loop
 ; (i.e. it is not in loop-simplify/canonical form).
-; FIXME: currently %res gets incorrectly replaced with undef.
 define i32 @test(i32 %v, i1 %c.1, i1 %c.2) {
 ; CHECK-LABEL: @test(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    switch i32 0, label [[ENTRY_SPLIT:%.*]] [
-; CHECK-NEXT:    i32 1, label [[EXIT_SPLIT:%.*]]
-; CHECK-NEXT:    ]
-; CHECK:       entry.split:
 ; CHECK-NEXT:    br label [[OUTER_HEADER:%.*]]
 ; CHECK:       outer.header:
 ; CHECK-NEXT:    br i1 [[C_1:%.*]], label [[OUTER_LATCH:%.*]], label [[INNER_HEADER_PREHEADER:%.*]]
 ; CHECK:       inner.header.preheader:
 ; CHECK-NEXT:    br label [[INNER_HEADER:%.*]]
 ; CHECK:       inner.header:
 ; CHECK-NEXT:    [[CMP_2:%.*]] = icmp ne i32 [[V:%.*]], 0
 ; CHECK-NEXT:    br i1 [[CMP_2]], label [[EXIT:%.*]], label [[INNER_LATCH:%.*]]
 ; CHECK:       inner.latch:
 ; CHECK-NEXT:    br i1 [[C_2:%.*]], label [[OUTER_LATCH_LOOPEXIT:%.*]], label [[INNER_HEADER]]
 ; CHECK:       outer.latch.loopexit:
 ; CHECK-NEXT:    br label [[OUTER_LATCH]]
 ; CHECK:       outer.latch:
 ; CHECK-NEXT:    br label [[OUTER_HEADER]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[RES:%.*]] = phi i32 [ [[V]], [[INNER_HEADER]] ]
-; CHECK-NEXT:    br label [[EXIT_SPLIT]]
+; CHECK-NEXT:    br label [[EXIT_SPLIT:%.*]]
 ; CHECK:       exit.split:
-; CHECK-NEXT:    ret i32 undef
+; CHECK-NEXT:    [[RES_SPLIT:%.*]] = phi i32 [ [[RES]], [[EXIT]] ]
+; CHECK-NEXT:    ret i32 [[RES_SPLIT]]
 ;
 entry:
   br label %outer.header
 
 outer.header:
   %g.0 = phi i32 [ 10, %outer.latch ], [ 1, %entry ]
   %cmp.1 = icmp eq i32 %g.0, 0
   br i1 %c.1, label %outer.latch, label %inner.header