[SimpleLoopUnswitch] Freeze trivial conditions if needed.

[fhahn]

Summary

Trivial unswitching can also introduce new branches on undef/poison.
Freeze the conditions if needed.

[nikic]

llvm/test/Transforms/SimpleLoopUnswitch/LIV-loop-condtion.ll

11–12

This freeze doesn't look necessary -- shouldn't there be a "not guaranteed to execute" check involved?

[fhahn]

llvm/test/Transforms/SimpleLoopUnswitch/LIV-loop-condtion.ll

11–12

Unfortunately I think the freeze here is needed due to the branch in the loop using %cond.and = and i1 %cond1, %cond2 as branch condition.

%cond1 could be undef and cond2 could always be 0. Then branching on cond1 unconditionally introduces a new branch on undef. (That's not an issue for poison though).

I'd need to check if isGuaranteedNotToBeUndefOrPoison does the right thing if the branch condition isn't an AND/OR but just an invariant value.

[fhahn]

llvm/test/Transforms/SimpleLoopUnswitch/LIV-loop-condtion.ll

11–12

Forgot to include: https://alive2.llvm.org/ce/z/58vj2Z

[nikic]

llvm/test/Transforms/SimpleLoopUnswitch/LIV-loop-condtion.ll

11–12

Oh right, forgot about the undef case. That's annoying.

[nikic]

LGTM

[fhahn]

Rebase so it can be applied before D124526.

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

if (FullUnswitch) {
     if (ExitDirection)
       assert(match(BI.getCondition(), m_LogicalOr()) &&
              "Must have an `or` of `i1`s or `select i1 X, true, Y`s for the "
              "condition!");
     else
       assert(match(BI.getCondition(), m_LogicalAnd()) &&
              "Must have an `and` of `i1`s or `select i1 X, Y, false`s for the"
              " condition!");
-    buildPartialUnswitchConditionalBranch(*OldPH, Invariants, ExitDirection,
-                                          *UnswitchedBB, *NewPH, false);
+    buildPartialUnswitchConditionalBranch(
+        *OldPH, Invariants, ExitDirection, *UnswitchedBB, *NewPH,
+        FreezeLoopUnswitchCond && any_of(Invariants, [&](Value *C) {
+          return !isGuaranteedNotToBeUndefOrPoison(C, nullptr,
+                                                   OldPH->getTerminator(), &DT);
+        }));
   }
 
   // Update the dominator tree with the added edge.
   DT.insertEdge(OldPH, UnswitchedBB);
 
   // After the dominator tree was updated with the added edge, update MemorySSA
   // if available.
   if (MSSAU) {

llvm/test/Transforms/SimpleLoopUnswitch/LIV-loop-condtion.ll

 ; RUN: opt < %s -simple-loop-unswitch -verify-memoryssa -S 2>&1 | FileCheck %s
 
 ; This is to test trivial loop unswitch only happens when trivial condition
 ; itself is an LIV loop condition (not partial LIV which could occur in and/or).
 
 define i32 @test(i1 %cond1, i32 %var1) {
 ; CHECK-LABEL: define i32 @test(
 entry:
   br label %loop_begin
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br i1 %cond1, label %entry.split, label %loop_exit.split
+; CHECK-NEXT:    [[FROZEN:%.+]] = freeze i1 %cond1
+; CHECK-NEXT:    br i1 [[FROZEN]], label %entry.split, label %loop_exit.split
 ;
 ; CHECK:       entry.split:
 ; CHECK-NEXT:    br label %loop_begin
 
 loop_begin:
   %var3 = phi i32 [%var1, %entry], [%var2, %do_something]
   %cond2 = icmp eq i32 %var3, 10
   %cond.and = and i1 %cond1, %cond2

llvm/test/Transforms/SimpleLoopUnswitch/trivial-unswitch-freeze-individual-conditions.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes='loop(simple-loop-unswitch)' -S %s | FileCheck %s
 
 declare void @some_func()
 
 define i32 @need_freeze_of_individual_or_conditions1(i1 %cond1, i1 %cond2, i1 %cond3, i1 %cond4) {
 ; CHECK-LABEL: @need_freeze_of_individual_or_conditions1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = and i1 [[COND4:%.*]], [[COND1:%.*]]
-; CHECK-NEXT:    br i1 [[TMP0]], label [[ENTRY_SPLIT:%.*]], label [[EXIT_SPLIT:%.*]]
+; CHECK-NEXT:    [[DOTFR:%.*]] = freeze i1 [[TMP0]]
+; CHECK-NEXT:    br i1 [[DOTFR]], label [[ENTRY_SPLIT:%.*]], label [[EXIT_SPLIT:%.*]]
 ; CHECK:       entry.split:
 ; CHECK-NEXT:    [[TMP1:%.*]] = and i1 [[COND2:%.*]], [[COND3:%.*]]
-; CHECK-NEXT:    br i1 [[TMP1]], label [[ENTRY_SPLIT_SPLIT:%.*]], label [[EXIT_SPLIT1:%.*]]
+; CHECK-NEXT:    [[DOTFR2:%.*]] = freeze i1 [[TMP1]]
+; CHECK-NEXT:    br i1 [[DOTFR2]], label [[ENTRY_SPLIT_SPLIT:%.*]], label [[EXIT_SPLIT1:%.*]]
 ; CHECK:       entry.split.split:
 ; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
 ; CHECK:       loop.header:
 ; CHECK-NEXT:    [[OR:%.*]] = or i1 true, true
 ; CHECK-NEXT:    [[AND1:%.*]] = and i1 [[OR]], true
 ; CHECK-NEXT:    [[AND2:%.*]] = select i1 [[AND1]], i1 true, i1 false
 ; CHECK-NEXT:    br i1 [[AND2]], label [[LOOP_LATCH:%.*]], label [[EXIT:%.*]]
 ; CHECK:       loop.latch:

 exit:
   ret i32 0
 }
 
 define i32 @need_freeze_of_individual_or_conditions2(i1 noundef %cond1, i1 %cond2, i1 %cond3, i1 %cond4) {
 ; CHECK-LABEL: @need_freeze_of_individual_or_conditions2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = and i1 [[COND4:%.*]], [[COND1:%.*]]
-; CHECK-NEXT:    br i1 [[TMP0]], label [[ENTRY_SPLIT:%.*]], label [[EXIT_SPLIT:%.*]]
+; CHECK-NEXT:    [[DOTFR:%.*]] = freeze i1 [[TMP0]]
+; CHECK-NEXT:    br i1 [[DOTFR]], label [[ENTRY_SPLIT:%.*]], label [[EXIT_SPLIT:%.*]]
 ; CHECK:       entry.split:
 ; CHECK-NEXT:    [[TMP1:%.*]] = and i1 [[COND2:%.*]], [[COND3:%.*]]
-; CHECK-NEXT:    br i1 [[TMP1]], label [[ENTRY_SPLIT_SPLIT:%.*]], label [[EXIT_SPLIT1:%.*]]
+; CHECK-NEXT:    [[DOTFR2:%.*]] = freeze i1 [[TMP1]]
+; CHECK-NEXT:    br i1 [[DOTFR2]], label [[ENTRY_SPLIT_SPLIT:%.*]], label [[EXIT_SPLIT1:%.*]]
 ; CHECK:       entry.split.split:
 ; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
 ; CHECK:       loop.header:
 ; CHECK-NEXT:    [[OR:%.*]] = or i1 true, true
 ; CHECK-NEXT:    [[AND1:%.*]] = and i1 [[OR]], true
 ; CHECK-NEXT:    [[AND2:%.*]] = select i1 [[AND1]], i1 true, i1 false
 ; CHECK-NEXT:    br i1 [[AND2]], label [[LOOP_LATCH:%.*]], label [[EXIT:%.*]]
 ; CHECK:       loop.latch:

 exit:
   ret i32 0
 }
 
 define i32 @need_freeze_of_individual_or_conditions3(i1 %cond1, i1 %cond2, i1 %cond3, i1 noundef %cond4) {
 ; CHECK-LABEL: @need_freeze_of_individual_or_conditions3(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = and i1 [[COND4:%.*]], [[COND1:%.*]]
-; CHECK-NEXT:    br i1 [[TMP0]], label [[ENTRY_SPLIT:%.*]], label [[EXIT_SPLIT:%.*]]
+; CHECK-NEXT:    [[DOTFR:%.*]] = freeze i1 [[TMP0]]
+; CHECK-NEXT:    br i1 [[DOTFR]], label [[ENTRY_SPLIT:%.*]], label [[EXIT_SPLIT:%.*]]
 ; CHECK:       entry.split:
 ; CHECK-NEXT:    [[TMP1:%.*]] = and i1 [[COND2:%.*]], [[COND3:%.*]]
-; CHECK-NEXT:    br i1 [[TMP1]], label [[ENTRY_SPLIT_SPLIT:%.*]], label [[EXIT_SPLIT1:%.*]]
+; CHECK-NEXT:    [[DOTFR2:%.*]] = freeze i1 [[TMP1]]
+; CHECK-NEXT:    br i1 [[DOTFR2]], label [[ENTRY_SPLIT_SPLIT:%.*]], label [[EXIT_SPLIT1:%.*]]
 ; CHECK:       entry.split.split:
 ; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
 ; CHECK:       loop.header:
 ; CHECK-NEXT:    [[OR:%.*]] = or i1 true, true
 ; CHECK-NEXT:    [[AND1:%.*]] = and i1 [[OR]], true
 ; CHECK-NEXT:    [[AND2:%.*]] = select i1 [[AND1]], i1 true, i1 false
 ; CHECK-NEXT:    br i1 [[AND2]], label [[LOOP_LATCH:%.*]], label [[EXIT:%.*]]
 ; CHECK:       loop.latch:

 exit:
   ret i32 0
 }
 
 define i32 @need_freeze_of_individual_and_conditions1(i1 %cond1, i1 %cond4) {
 ; CHECK-LABEL: @need_freeze_of_individual_and_conditions1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = or i1 [[COND4:%.*]], [[COND1:%.*]]
-; CHECK-NEXT:    br i1 [[TMP0]], label [[EXIT_SPLIT:%.*]], label [[ENTRY_SPLIT:%.*]]
+; CHECK-NEXT:    [[DOTFR:%.*]] = freeze i1 [[TMP0]]
+; CHECK-NEXT:    br i1 [[DOTFR]], label [[EXIT_SPLIT:%.*]], label [[ENTRY_SPLIT:%.*]]
 ; CHECK:       entry.split:
 ; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
 ; CHECK:       loop.header:
 ; CHECK-NEXT:    [[COND_OR1:%.*]] = or i1 undef, false
 ; CHECK-NEXT:    [[COND_OR6:%.*]] = select i1 [[COND_OR1]], i1 true, i1 false
 ; CHECK-NEXT:    br i1 [[COND_OR6]], label [[EXIT:%.*]], label [[LOOP_LATCH:%.*]]
 ; CHECK:       loop.latch:
 ; CHECK-NEXT:    br label [[LOOP_HEADER]]

 exit:
   ret i32 0
 }
 
 define i32 @need_freeze_of_individual_and_conditions2(i1 noundef %cond1, i1 %cond4) {
 ; CHECK-LABEL: @need_freeze_of_individual_and_conditions2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = or i1 [[COND4:%.*]], [[COND1:%.*]]
-; CHECK-NEXT:    br i1 [[TMP0]], label [[EXIT_SPLIT:%.*]], label [[ENTRY_SPLIT:%.*]]
+; CHECK-NEXT:    [[DOTFR:%.*]] = freeze i1 [[TMP0]]
+; CHECK-NEXT:    br i1 [[DOTFR]], label [[EXIT_SPLIT:%.*]], label [[ENTRY_SPLIT:%.*]]
 ; CHECK:       entry.split:
 ; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
 ; CHECK:       loop.header:
 ; CHECK-NEXT:    [[COND_OR1:%.*]] = or i1 undef, false
 ; CHECK-NEXT:    [[COND_OR6:%.*]] = select i1 [[COND_OR1]], i1 true, i1 false
 ; CHECK-NEXT:    br i1 [[COND_OR6]], label [[EXIT:%.*]], label [[LOOP_LATCH:%.*]]
 ; CHECK:       loop.latch:
 ; CHECK-NEXT:    br label [[LOOP_HEADER]]

 exit:
   ret i32 0
 }
 
 define i32 @need_freeze_of_individual_and_conditions3(i1 %cond1, i1 noundef %cond4) {
 ; CHECK-LABEL: @need_freeze_of_individual_and_conditions3(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = or i1 [[COND4:%.*]], [[COND1:%.*]]
-; CHECK-NEXT:    br i1 [[TMP0]], label [[EXIT_SPLIT:%.*]], label [[ENTRY_SPLIT:%.*]]
+; CHECK-NEXT:    [[DOTFR:%.*]] = freeze i1 [[TMP0]]
+; CHECK-NEXT:    br i1 [[DOTFR]], label [[EXIT_SPLIT:%.*]], label [[ENTRY_SPLIT:%.*]]
 ; CHECK:       entry.split:
 ; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
 ; CHECK:       loop.header:
 ; CHECK-NEXT:    [[COND_OR1:%.*]] = or i1 undef, false
 ; CHECK-NEXT:    [[COND_OR6:%.*]] = select i1 [[COND_OR1]], i1 true, i1 false
 ; CHECK-NEXT:    br i1 [[COND_OR6]], label [[EXIT:%.*]], label [[LOOP_LATCH:%.*]]
 ; CHECK:       loop.latch:
 ; CHECK-NEXT:    br label [[LOOP_HEADER]]

llvm/test/Transforms/SimpleLoopUnswitch/trivial-unswitch-logical-and-or.ll

 ; Note that cond6 can be unswitched because `select i1 %cond_or5, i1 true, i1 false` is
 ; both logical-or and logical-and.
 define i32 @test_partial_condition_unswitch_or_select(i32* %var, i1 %cond1, i1 %cond2, i1 %cond3, i1 %cond4, i1 %cond5, i1 %cond6) {
 ; CHECK-LABEL: @test_partial_condition_unswitch_or_select(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = or i1 [[COND4:%.*]], [[COND2:%.*]]
 ; CHECK-NEXT:    [[TMP1:%.*]] = or i1 [[TMP0]], [[COND3:%.*]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = or i1 [[TMP1]], [[COND1:%.*]]
-; CHECK-NEXT:    br i1 [[TMP2]], label [[LOOP_EXIT_SPLIT:%.*]], label [[ENTRY_SPLIT:%.*]]
+; CHECK-NEXT:    [[DOTFR:%.*]] = freeze i1 [[TMP2]]
+; CHECK-NEXT:    br i1 [[DOTFR]], label [[LOOP_EXIT_SPLIT:%.*]], label [[ENTRY_SPLIT:%.*]]
 ; CHECK:       entry.split:
-; CHECK-NEXT:    br i1 [[COND6:%.*]], label [[LOOP_EXIT_SPLIT1:%.*]], label [[ENTRY_SPLIT_SPLIT:%.*]]
+; CHECK-NEXT:    [[COND6_FR:%.*]] = freeze i1 [[COND6:%.*]]
+; CHECK-NEXT:    br i1 [[COND6_FR]], label [[LOOP_EXIT_SPLIT1:%.*]], label [[ENTRY_SPLIT_SPLIT:%.*]]
 ; CHECK:       entry.split.split:
 ; CHECK-NEXT:    br label [[LOOP_BEGIN:%.*]]
 ; CHECK:       loop_begin:
 ; CHECK-NEXT:    [[VAR_VAL:%.*]] = load i32, i32* [[VAR:%.*]], align 4
 ; CHECK-NEXT:    [[VAR_COND:%.*]] = trunc i32 [[VAR_VAL]] to i1
 ; CHECK-NEXT:    [[COND_OR1:%.*]] = or i1 [[VAR_COND]], false
 ; CHECK-NEXT:    [[COND_OR2:%.*]] = or i1 false, false
 ; CHECK-NEXT:    [[COND_OR3:%.*]] = or i1 [[COND_OR1]], [[COND_OR2]]

llvm/test/Transforms/SimpleLoopUnswitch/trivial-unswitch.ll

 define i32 @test_partial_condition_unswitch_and(i32* %var, i1 %cond1, i1 %cond2) {
 ; CHECK-LABEL: @test_partial_condition_unswitch_and(
 entry:
   br label %loop_begin
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 %cond1, label %entry.split, label %loop_exit.split
 ;
 ; CHECK:       entry.split:
-; CHECK-NEXT:    br i1 %cond2, label %entry.split.split, label %loop_exit
+; CHECK-NEXT:    [[FROZEN:%.+]] = freeze i1 %cond2
+; CHECK-NEXT:    br i1 [[FROZEN]], label %entry.split.split, label %loop_exit
 ;
 ; CHECK:       entry.split.split:
 ; CHECK-NEXT:    br label %loop_begin
 
 loop_begin:
   br i1 %cond1, label %continue, label %loop_exit
 ; CHECK:       loop_begin:
 ; CHECK-NEXT:    br label %continue

 define i32 @test_partial_condition_unswitch_and_select(i32* %var, i1 %cond1, i1 %cond2) {
 ; CHECK-LABEL: @test_partial_condition_unswitch_and_select(
 entry:
   br label %loop_begin
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 %cond1, label %entry.split, label %loop_exit.split
 ;
 ; CHECK:       entry.split:
-; CHECK-NEXT:    br i1 %cond2, label %entry.split.split, label %loop_exit
+; CHECK-NEXT:    [[FROZEN:%.+]] = freeze i1 %cond2
+; CHECK-NEXT:    br i1 [[FROZEN]], label %entry.split.split, label %loop_exit
 ;
 ; CHECK:       entry.split.split:
 ; CHECK-NEXT:    br label %loop_begin
 
 loop_begin:
   br i1 %cond1, label %continue, label %loop_exit
 ; CHECK:       loop_begin:
 ; CHECK-NEXT:    br label %continue

 define i32 @test_partial_condition_unswitch_or_simple_select(i32* %var, i1 %cond1, i1 %cond2) {
 ; CHECK-LABEL: @test_partial_condition_unswitch_or_simple_select(
 entry:
   br label %loop_begin
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 %cond1, label %entry.split, label %loop_exit.split
 ;
 ; CHECK:       entry.split:
-; CHECK-NEXT:    br i1 %cond2, label %loop_exit.split1, label %entry.split.split
+; CHECK-NEXT:    [[FROZEN:%.+]] = freeze i1 %cond2
+; CHECK-NEXT:    br i1 [[FROZEN]], label %loop_exit.split1, label %entry.split.split
 ;
 ; CHECK:       entry.split.split:
 ; CHECK-NEXT:    br label %loop_begin
 
 loop_begin:
   br i1 %cond1, label %continue, label %loop_exit
 ; CHECK:       loop_begin:
 ; CHECK-NEXT:    br label %continue

 define i32 @test_partial_condition_unswitch_or(i32* %var, i1 %cond1, i1 %cond2, i1 %cond3, i1 %cond4, i1 %cond5, i1 %cond6) {
 ; CHECK-LABEL: @test_partial_condition_unswitch_or(
 entry:
   br label %loop_begin
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    %[[INV_OR1:.*]] = or i1 %cond4, %cond2
 ; CHECK-NEXT:    %[[INV_OR2:.*]] = or i1 %[[INV_OR1]], %cond3
 ; CHECK-NEXT:    %[[INV_OR3:.*]] = or i1 %[[INV_OR2]], %cond1
-; CHECK-NEXT:    br i1 %[[INV_OR3]], label %loop_exit.split, label %entry.split
+; CHECK-NEXT:    [[FROZEN:%.+]] = freeze i1 %[[INV_OR3]]
+; CHECK-NEXT:    br i1 [[FROZEN]], label %loop_exit.split, label %entry.split
 ;
 ; CHECK:       entry.split:
 ; CHECK-NEXT:    br label %loop_begin
 
 loop_begin:
   %var_val = load i32, i32* %var
   %var_cond = trunc i32 %var_val to i1
   %cond_or1 = or i1 %var_cond, %cond1

 ; CHECK-NEXT:    ret
 }
 
 define i32 @test_partial_condition_unswitch_with_lcssa_phi1(i32* %var, i1 %cond, i32 %x) {
 ; CHECK-LABEL: @test_partial_condition_unswitch_with_lcssa_phi1(
 entry:
   br label %loop_begin
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br i1 %cond, label %entry.split, label %loop_exit.split
+; CHECK-NEXT:    [[FROZEN:%.+]] = freeze i1 %cond
+; CHECK-NEXT:    br i1 [[FROZEN]], label %entry.split, label %loop_exit.split
 ;
 ; CHECK:       entry.split:
 ; CHECK-NEXT:    br label %loop_begin
 
 loop_begin:
   %var_val = load i32, i32* %var
   %var_cond = trunc i32 %var_val to i1
   %cond_and = and i1 %var_cond, %cond

 ; CHECK-NEXT:    ret i32 %[[LCSSA_SPLIT]]
 }
 
 define i32 @test_partial_condition_unswitch_with_lcssa_phi2(i32* %var, i1 %cond, i32 %x, i32 %y) {
 ; CHECK-LABEL: @test_partial_condition_unswitch_with_lcssa_phi2(
 entry:
   br label %loop_begin
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br i1 %cond, label %entry.split, label %loop_exit.split
+; CHECK-NEXT:    [[FROZEN:%.+]] = freeze i1 %cond
+; CHECK-NEXT:    br i1 [[FROZEN]], label %entry.split, label %loop_exit.split
 ;
 ; CHECK:       entry.split:
 ; CHECK-NEXT:    br label %loop_begin
 
 loop_begin:
   %var_val = load i32, i32* %var
   %var_cond = trunc i32 %var_val to i1
   %cond_and = and i1 %var_cond, %cond