[LoopSimplifyCFG] Prevent use-def dominance breach by handling dead exits. PR56243

[mkazantsev]

Summary

One of the transforms in LoopSimplifyCFG demands that the LCSSA form is
truly maintained for all values, tokens included, otherwise it may end up creating
a use that is not dominated by def (and Phi creation for tokens is impossible).
Detect this situation and prevent transform for it early.

[efriedma]

LGTM

I'm a little worried about the performance cost of the scan, but I guess this should be rare enough that it's unlikely to matter.

llvm/lib/Transforms/Scalar/LoopSimplifyCFG.cpp

if (BlocksInLoopAfterFolding.size() + DeadLoopBlocks.size() !=
       LLVM_DEBUG(
           dbgs() << "Give up constant terminator folding in loop "
                  << Header->getName() << ": we don't currently"
                     " support blocks that are not dead, but will stop "
                     "being a part of the loop after constant-folding.\n");
       return false;
     }
 
+    // TODO: Tokens may breach LCSSA form by default. However, the transform for
+    // dead exit blocks requires LCSSA form to be maintained for all values,
+    // tokens included, otherwise it may break use-def dominance (see PR56243).
+    if (!DeadExitBlocks.empty() && !L.isLCSSAForm(DT, /*IgnoreTokens*/ false)) {
+      assert(L.isLCSSAForm(DT, /*IgnoreTokens*/ true) &&
+             "LCSSA broken not by tokens?");
+      LLVM_DEBUG(dbgs() << "Give up constant terminator folding in loop "
+                        << Header->getName()
+                        << ": tokens uses potentially break LCSSA form.\n");
+      return false;
+    }
+
     SE.forgetTopmostLoop(&L);
     // Dump analysis results.
     LLVM_DEBUG(dump());
 
     LLVM_DEBUG(dbgs() << "Constant-folding " << FoldCandidates.size()
                       << " terminators in loop " << Header->getName() << "\n");
 
     // Make the actual transforms.

llvm/test/Transforms/LoopSimplifyCFG/pr56243.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -passes='loop-mssa(licm,loop-simplifycfg)' < %s | FileCheck %s
 
-; REQUIRES: asserts
-; XFAIL: *
-
 ; Here we end un sinking a user of token down from the loop, therefore breaching LCSSA form.
 ; Then, LoopSimplifyCFG expcets that LCSSA form is maintained, and remains unaware that
 ; it may be penetrated by tokens. As result, it may end up breaking dominance between def and
 ; use by introducing fake temporary edges.
 
 define i8 addrspace(1)* @test_gc_relocate() gc "statepoint-example" {
-; CHECK-LABEL: @test_gc_relocate
+; CHECK-LABEL: @test_gc_relocate(
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    switch i32 undef, label [[BB43:%.*]] [
+; CHECK-NEXT:    i32 1, label [[BB18:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       bb18:
+; CHECK-NEXT:    switch i32 undef, label [[BB43]] [
+; CHECK-NEXT:    i32 0, label [[BB28:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       bb28:
+; CHECK-NEXT:    [[TMP34:%.*]] = call token (i64, i32, i8 addrspace(1)* (i64, i32, i32, i32)*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_p1i8i64i32i32i32f(i64 2882400000, i32 0, i8 addrspace(1)* (i64, i32, i32, i32)* nonnull elementtype(i8 addrspace(1)* (i64, i32, i32, i32)) @barney.4, i32 4, i32 0, i64 undef, i32 5, i32 5, i32 undef, i32 0, i32 0) [ "deopt"(), "gc-live"(i8 addrspace(1)* undef) ]
+; CHECK-NEXT:    br i1 false, label [[BB57:%.*]], label [[BB36:%.*]]
+; CHECK:       bb36:
+; CHECK-NEXT:    switch i32 undef, label [[BB43]] [
+; CHECK-NEXT:    i32 1, label [[BB39:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       bb39:
+; CHECK-NEXT:    switch i32 undef, label [[BB43]] [
+; CHECK-NEXT:    i32 1, label [[BB45:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       bb43:
+; CHECK-NEXT:    unreachable
+; CHECK:       bb45:
+; CHECK-NEXT:    br label [[BB1]]
+; CHECK:       bb57:
+; CHECK-NEXT:    [[TMP35_LE:%.*]] = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token [[TMP34]], i32 0, i32 0)
+; CHECK-NEXT:    ret i8 addrspace(1)* [[TMP35_LE]]
+;
   br label %bb1
 
 bb1:                                              ; preds = %bb45, %0
   switch i32 undef, label %bb43 [
-    i32 1, label %bb18
   ]
 
 bb18:                                             ; preds = %bb1
   switch i32 undef, label %bb43 [
-    i32 0, label %bb28
   ]
 
 bb28:                                             ; preds = %bb18
   %tmp34 = call token (i64, i32, i8 addrspace(1)* (i64, i32, i32, i32)*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_p1i8i64i32i32i32f(i64 2882400000, i32 0, i8 addrspace(1)* (i64, i32, i32, i32)* nonnull elementtype(i8 addrspace(1)* (i64, i32, i32, i32)) @barney.4, i32 4, i32 0, i64 undef, i32 5, i32 5, i32 undef, i32 0, i32 0) [ "deopt"(), "gc-live"(i8 addrspace(1)* undef) ]
   %tmp35 = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %tmp34, i32 0, i32 0) ; (undef, undef)
   br i1 false, label %bb57, label %bb36
 
 bb36:                                             ; preds = %bb28
   switch i32 undef, label %bb43 [
-    i32 1, label %bb39
   ]
 
 bb39:                                             ; preds = %bb36
   switch i32 undef, label %bb43 [
-    i32 1, label %bb45
   ]
 
 bb43:                                             ; preds = %bb39, %bb36, %bb18, %bb1
   unreachable
 
 bb45:                                             ; preds = %bb39
   br label %bb1