[SimpleLoopUnswitch] Freeze individual OR/AND operands.

[fhahn]

Summary

In some cases, it is not enough to freeze the final AND/OR operation
when chaining a number of invariant conditions together.

After creating a chain of ANDs/ORs, we assume all unswitched operands to
be either true or false. But if any of the operands is poison, the rest
of the operands could have any value after branching on the frozen
condition.

To avoid that, freeze individual operands, if needed. In some cases this
may lead to unnecessary freezes, but it seems required at least for some
cases (see trivial-unswitch-freeze-individual-conditions.ll)

[nikic]

LGTM

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

215

nit: unnecessary braces

[fhahn]

Rebased so it can be applied before D124526.

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

static bool areLoopExitPHIsLoopInvariant(Loop &L, BasicBlock &ExitingBB,
   llvm_unreachable("Basic blocks should never be empty!");
 }
 
 /// Copy a set of loop invariant values \p ToDuplicate and insert them at the
 /// end of \p BB and conditionally branch on the copied condition. We only
 /// branch on a single value.
 static void buildPartialUnswitchConditionalBranch(
     BasicBlock &BB, ArrayRef<Value *> Invariants, bool Direction,
-    BasicBlock &UnswitchedSucc, BasicBlock &NormalSucc, bool InsertFreeze) {
+    BasicBlock &UnswitchedSucc, BasicBlock &NormalSucc, bool InsertFreeze,
+    Instruction *I, AssumptionCache *AC, DominatorTree &DT) {
   IRBuilder<> IRB(&BB);
 
-  Value *Cond = Direction ? IRB.CreateOr(Invariants) :
-    IRB.CreateAnd(Invariants);
-  if (InsertFreeze)
-    Cond = IRB.CreateFreeze(Cond, Cond->getName() + ".fr");
+  SmallVector<Value *> FrozenInvariants;
+  for (Value *Inv : Invariants) {
+    if (InsertFreeze && !isGuaranteedNotToBeUndefOrPoison(Inv, AC, I, &DT))
+      Inv = IRB.CreateFreeze(Inv, Inv->getName() + ".fr");
+    FrozenInvariants.push_back(Inv);
+  }
+
+  Value *Cond = Direction ? IRB.CreateOr(FrozenInvariants)
+                          : IRB.CreateAnd(FrozenInvariants);
   IRB.CreateCondBr(Cond, Direction ? &UnswitchedSucc : &NormalSucc,
                    Direction ? &NormalSucc : &UnswitchedSucc);
 }
 
 /// Copy a set of loop invariant values, and conditionally branch on them.
 static void buildPartialInvariantUnswitchConditionalBranch(
     BasicBlock &BB, ArrayRef<Value *> ToDuplicate, bool Direction,
     BasicBlock &UnswitchedSucc, BasicBlock &NormalSucc, Loop &L,
if (ExitDirection)
              "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,
-        FreezeLoopUnswitchCond && any_of(Invariants, [&](Value *C) {
-          return !isGuaranteedNotToBeUndefOrPoison(C, nullptr,
-                                                   OldPH->getTerminator(), &DT);
-        }));
+        FreezeLoopUnswitchCond, OldPH->getTerminator(), nullptr, 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) {
assert(UnswitchedSuccBBs.size() == 1 &&
            "Only one possible unswitched block for a branch!");
     BasicBlock *ClonedPH = ClonedPHs.begin()->second;
     // When doing a partial unswitch, we have to do a bit more work to build up
     // the branch in the split block.
     if (PartiallyInvariant)
       buildPartialInvariantUnswitchConditionalBranch(
           *SplitBB, Invariants, Direction, *ClonedPH, *LoopPH, L, MSSAU);
     else {
-      buildPartialUnswitchConditionalBranch(
-          *SplitBB, Invariants, Direction, *ClonedPH, *LoopPH,
-          InsertFreeze && any_of(Invariants, [&](Value *C) {
-            return !isGuaranteedNotToBeUndefOrPoison(C, &AC, BI, &DT);
-          }));
+      buildPartialUnswitchConditionalBranch(*SplitBB, Invariants, Direction,
+                                            *ClonedPH, *LoopPH, InsertFreeze,
+                                            BI, &AC, DT);
     }
     DTUpdates.push_back({DominatorTree::Insert, SplitBB, ClonedPH});
 
     if (MSSAU) {
       DT.applyUpdates(DTUpdates);
       DTUpdates.clear();
 
       // Perform MSSA cloning updates.

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:    [[DOTFR:%.*]] = freeze i1 [[TMP0]]
-; CHECK-NEXT:    br i1 [[DOTFR]], label [[ENTRY_SPLIT:%.*]], label [[EXIT_SPLIT:%.*]]
+; CHECK-NEXT:    [[COND4_FR:%.*]] = freeze i1 [[COND4:%.*]]
+; CHECK-NEXT:    [[COND1_FR:%.*]] = freeze i1 [[COND1:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = and i1 [[COND4_FR]], [[COND1_FR]]
+; CHECK-NEXT:    br i1 [[TMP0]], label [[ENTRY_SPLIT:%.*]], label [[EXIT_SPLIT:%.*]]
 ; CHECK:       entry.split:
-; CHECK-NEXT:    [[TMP1:%.*]] = and i1 [[COND2:%.*]], [[COND3:%.*]]
-; CHECK-NEXT:    [[DOTFR2:%.*]] = freeze i1 [[TMP1]]
-; CHECK-NEXT:    br i1 [[DOTFR2]], label [[ENTRY_SPLIT_SPLIT:%.*]], label [[EXIT_SPLIT1:%.*]]
+; CHECK-NEXT:    [[COND2_FR:%.*]] = freeze i1 [[COND2:%.*]]
+; CHECK-NEXT:    [[COND3_FR:%.*]] = freeze i1 [[COND3:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i1 [[COND2_FR]], [[COND3_FR]]
+; CHECK-NEXT:    br i1 [[TMP1]], 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:    [[DOTFR:%.*]] = freeze i1 [[TMP0]]
-; CHECK-NEXT:    br i1 [[DOTFR]], label [[ENTRY_SPLIT:%.*]], label [[EXIT_SPLIT:%.*]]
+; CHECK-NEXT:    [[COND4_FR:%.*]] = freeze i1 [[COND4:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = and i1 [[COND4_FR]], [[COND1:%.*]]
+; CHECK-NEXT:    br i1 [[TMP0]], label [[ENTRY_SPLIT:%.*]], label [[EXIT_SPLIT:%.*]]
 ; CHECK:       entry.split:
-; CHECK-NEXT:    [[TMP1:%.*]] = and i1 [[COND2:%.*]], [[COND3:%.*]]
-; CHECK-NEXT:    [[DOTFR2:%.*]] = freeze i1 [[TMP1]]
-; CHECK-NEXT:    br i1 [[DOTFR2]], label [[ENTRY_SPLIT_SPLIT:%.*]], label [[EXIT_SPLIT1:%.*]]
+; CHECK-NEXT:    [[COND2_FR:%.*]] = freeze i1 [[COND2:%.*]]
+; CHECK-NEXT:    [[COND3_FR:%.*]] = freeze i1 [[COND3:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i1 [[COND2_FR]], [[COND3_FR]]
+; CHECK-NEXT:    br i1 [[TMP1]], 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:    [[DOTFR:%.*]] = freeze i1 [[TMP0]]
-; CHECK-NEXT:    br i1 [[DOTFR]], label [[ENTRY_SPLIT:%.*]], label [[EXIT_SPLIT:%.*]]
+; CHECK-NEXT:    [[COND1_FR:%.*]] = freeze i1 [[COND1:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = and i1 [[COND4:%.*]], [[COND1_FR]]
+; CHECK-NEXT:    br i1 [[TMP0]], label [[ENTRY_SPLIT:%.*]], label [[EXIT_SPLIT:%.*]]
 ; CHECK:       entry.split:
-; CHECK-NEXT:    [[TMP1:%.*]] = and i1 [[COND2:%.*]], [[COND3:%.*]]
-; CHECK-NEXT:    [[DOTFR2:%.*]] = freeze i1 [[TMP1]]
-; CHECK-NEXT:    br i1 [[DOTFR2]], label [[ENTRY_SPLIT_SPLIT:%.*]], label [[EXIT_SPLIT1:%.*]]
+; CHECK-NEXT:    [[COND2_FR:%.*]] = freeze i1 [[COND2:%.*]]
+; CHECK-NEXT:    [[COND3_FR:%.*]] = freeze i1 [[COND3:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i1 [[COND2_FR]], [[COND3_FR]]
+; CHECK-NEXT:    br i1 [[TMP1]], 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:    [[DOTFR:%.*]] = freeze i1 [[TMP0]]
-; CHECK-NEXT:    br i1 [[DOTFR]], label [[EXIT_SPLIT:%.*]], label [[ENTRY_SPLIT:%.*]]
+; CHECK-NEXT:    [[COND4_FR:%.*]] = freeze i1 [[COND4:%.*]]
+; CHECK-NEXT:    [[COND1_FR:%.*]] = freeze i1 [[COND1:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = or i1 [[COND4_FR]], [[COND1_FR]]
+; CHECK-NEXT:    br i1 [[TMP0]], 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:    [[DOTFR:%.*]] = freeze i1 [[TMP0]]
-; CHECK-NEXT:    br i1 [[DOTFR]], label [[EXIT_SPLIT:%.*]], label [[ENTRY_SPLIT:%.*]]
+; CHECK-NEXT:    [[COND4_FR:%.*]] = freeze i1 [[COND4:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = or i1 [[COND4_FR]], [[COND1:%.*]]
+; CHECK-NEXT:    br i1 [[TMP0]], 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:    [[DOTFR:%.*]] = freeze i1 [[TMP0]]
-; CHECK-NEXT:    br i1 [[DOTFR]], label [[EXIT_SPLIT:%.*]], label [[ENTRY_SPLIT:%.*]]
+; CHECK-NEXT:    [[COND1_FR:%.*]] = freeze i1 [[COND1:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = or i1 [[COND4:%.*]], [[COND1_FR]]
+; CHECK-NEXT:    br i1 [[TMP0]], 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

 }
 
 ; Check that loop unswitch looks through a combination of or and select instructions.
 ; 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:    [[DOTFR:%.*]] = freeze i1 [[TMP2]]
-; CHECK-NEXT:    br i1 [[DOTFR]], label [[LOOP_EXIT_SPLIT:%.*]], label [[ENTRY_SPLIT:%.*]]
+; CHECK-NEXT:    [[COND4_FR:%.*]] = freeze i1 [[COND4:%.*]]
+; CHECK-NEXT:    [[COND2_FR:%.*]] = freeze i1 [[COND2:%.*]]
+; CHECK-NEXT:    [[COND3_FR:%.*]] = freeze i1 [[COND3:%.*]]
+; CHECK-NEXT:    [[COND1_FR:%.*]] = freeze i1 [[COND1:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = or i1 [[COND4_FR]], [[COND2_FR]]
+; CHECK-NEXT:    [[TMP1:%.*]] = or i1 [[TMP0]], [[COND3_FR]]
+; CHECK-NEXT:    [[TMP2:%.*]] = or i1 [[TMP1]], [[COND1_FR]]
+; CHECK-NEXT:    br i1 [[TMP2]], label [[LOOP_EXIT_SPLIT:%.*]], label [[ENTRY_SPLIT:%.*]]
 ; CHECK:       entry.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

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

 ; CHECK-NEXT:    ret
 }
 
 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:    [[FROZEN:%.+]] = freeze i1 %[[INV_OR3]]
-; CHECK-NEXT:    br i1 [[FROZEN]], label %loop_exit.split, label %entry.split
+; CHECK-NEXT:    %[[C4_FR:.+]] = freeze i1 %cond4
+; CHECK-NEXT:    %[[C2_FR:.+]] = freeze i1 %cond2
+; CHECK-NEXT:    %[[C3_FR:.+]] = freeze i1 %cond3
+; CHECK-NEXT:    %[[C1_FR:.+]] = freeze i1 %cond1
+; CHECK-NEXT:    %[[INV_OR1:.*]] = or i1 %[[C4_FR]], %[[C2_FR]]
+; CHECK-NEXT:    %[[INV_OR2:.*]] = or i1 %[[INV_OR1]], %[[C3_FR]]
+; CHECK-NEXT:    %[[INV_OR3:.*]] = or i1 %[[INV_OR2]], %[[C1_FR]]
+; CHECK-NEXT:    br i1 %[[INV_OR3]], 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