[InstCombine] Disable branch predicate canonicalization

[yrouban]

Summary

Introduce a flag to enable/disable the branch predicate canonicalization in InstCombine.
Fix all sensitive tests to pass with the flag set to /off.

This is the next step to move the branch predicate canonicalization transformation from InstCombine to SimplifyCFG. See the motivation in the description of the first patch D84491.

[nikic]

The main canonicalization for this nowadays lives in https://github.com/llvm/llvm-project/blob/99d03f03919498b688a8921b2ec669057772803f/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp#L5286.

[lebedev.ri]

Since out of all 3 patches this is the one with comments, i'll reply here.
I'm not a fan of this direction. You'll need to additionally cripple
canonicalizeICmpPredicate(), canFreelyInvertAllUsersOf(),
possibly their users. I'm not sure it conceptually makes sense
to do that in SimplifyCFG. But it for sure will restrict InstCombine.

Was the other proper solution of either updating PDT, or making it order-insensitive explored and turned out to be impossible?

[yrouban]

In D84493#2171571, @lebedev.ri wrote:

Thank you for pointing this out. I will try changing canonicalizeICmpPredicate(), canFreelyInvertAllUsersOf().

In D84493#2171571, @lebedev.ri wrote:

Was the other proper solution of either updating PDT, or making it order-insensitive explored and turned out to be impossible?

Nobody proposed a good solution with a PDT calculation fix to make it insensitive to the branch order. PDT could not be updated properly either.

[lebedev.ri]

So in other words, instead of paying the price of recreating domtrees after instcombine,
we'll just shift the transforms to some other pass that already causes domtrees to be recreated, correct?

In D84493#2171811, @yrouban wrote:

In D84493#2171571, @lebedev.ri wrote:

Thank you for pointing this out. I will try changing canonicalizeICmpPredicate(), canFreelyInvertAllUsersOf().

In D84493#2171571, @lebedev.ri wrote:

Was the other proper solution of either updating PDT, or making it order-insensitive explored and turned out to be impossible?

Nobody proposed a good solution with a PDT calculation fix to make it insensitive to the branch order. PDT could not be updated properly either.

In D81089#2088014, @kuhar wrote:

<..> you have to chose some arbitrary way of selecting a fake-entry node from nodes in an scc. Right now this order is whatever children or inverse_children return, but could be based on the order of blocks in a function instead.

[yrouban]

In D84493#2171849, @lebedev.ri wrote:

So in other words, instead of paying the price of recreating domtrees after instcombine,
we'll just shift the transforms to some other pass that already causes domtrees to be recreated, correct?

I have just proposed a solution alternative to D81089. The intention is clear: do CFG changes in SimplifyCFG instead of InstCombine. Strictly speaking PreserveCFG must not be reported if we change terminators in any way.

In D84493#2171849, @lebedev.ri wrote:

In D81089#2088014, @kuhar wrote:

<..> you have to chose some arbitrary way of selecting a fake-entry node from nodes in an scc. Right now this order is whatever children or inverse_children return, but could be based on the order of blocks in a function instead.

Ok. Let us try now. But why did not they do it a few years ago then?

[kuhar]

In D84493#2171946, @yrouban wrote:

In D84493#2171849, @lebedev.ri wrote:

In D81089#2088014, @kuhar wrote:

<..> you have to chose some arbitrary way of selecting a fake-entry node from nodes in an scc. Right now this order is whatever children or inverse_children return, but could be based on the order of blocks in a function instead.

Ok. Let us try now. But why did not they do it a few years ago then?

We just missed this IIRC :)

[lebedev.ri]

Abandon now that D84763 has resolved the base problem?

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

 // increases variable availability at the cost of accuracy. Variables that
 // cannot be promoted by mem2reg or SROA will be described as living in memory
 // for their entire lifetime. However, passes like DSE and instcombine can
 // delete stores to the alloca, leading to misleading and inaccurate debug
 // information. This flag can be removed when those passes are fixed.
 static cl::opt<unsigned> ShouldLowerDbgDeclare("instcombine-lower-dbg-declare",
                                                cl::Hidden, cl::init(true));
 
+static cl::opt<bool>
+    CanonicalizeBranchPredicates("instcombine-canonicalize-branch-predicates",
+                                 cl::Hidden, cl::init(true),
+                                 cl::desc("Canonicalize branch predicates"));
+
 Optional<Instruction *>
 InstCombiner::targetInstCombineIntrinsic(IntrinsicInst &II) {
   // Handle target specific intrinsics
   if (II.getCalledFunction()->isTargetIntrinsic()) {
     return TTI.instCombineIntrinsic(*this, II);
   }
   return None;
 }

 }
 
 Instruction *InstCombinerImpl::visitBranchInst(BranchInst &BI) {
   if (BI.isUnconditional())
     return visitUnconditionalBranchInst(BI);
 
   // Change br (not X), label True, label False to: br X, label False, True
   Value *X = nullptr;
-  if (match(&BI, m_Br(m_Not(m_Value(X)), m_BasicBlock(), m_BasicBlock())) &&
+  if (CanonicalizeBranchPredicates &&
+      match(&BI, m_Br(m_Not(m_Value(X)), m_BasicBlock(), m_BasicBlock())) &&
       !isa<Constant>(X)) {
     // Swap Destinations and condition...
     BI.swapSuccessors();
     return replaceOperand(BI, 0, X);
   }
 
   // If the condition is irrelevant, remove the use so that other
   // transforms on the condition become more effective.
   if (!isa<ConstantInt>(BI.getCondition()) &&
       BI.getSuccessor(0) == BI.getSuccessor(1))
     return replaceOperand(
         BI, 0, ConstantInt::getFalse(BI.getCondition()->getType()));
 
   // Canonicalize, for example, fcmp_one -> fcmp_oeq.
   CmpInst::Predicate Pred;
-  if (match(&BI, m_Br(m_OneUse(m_FCmp(Pred, m_Value(), m_Value())),
+  if (CanonicalizeBranchPredicates &&
+      match(&BI, m_Br(m_OneUse(m_FCmp(Pred, m_Value(), m_Value())),
                       m_BasicBlock(), m_BasicBlock())) &&
       !isCanonicalPredicate(Pred)) {
     // Swap destinations and condition.
     CmpInst *Cond = cast<CmpInst>(BI.getCondition());
     Cond->setPredicate(CmpInst::getInversePredicate(Pred));
     BI.swapSuccessors();
     Worklist.push(Cond);
     return &BI;

llvm/test/Transforms/InstCombine/branch.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -instcombine -S < %s | FileCheck %s
-; RUN: opt -passes=instcombine -S < %s | FileCheck %s
+; RUN: opt -instcombine -instcombine-canonicalize-branch-predicates=0 -S < %s | FileCheck %s
+; RUN: opt -passes=instcombine -instcombine-canonicalize-branch-predicates=0 -S < %s | FileCheck %s
 
 ; Check that we fold the condition of branches of the
 ; form: br <condition> dest1, dest2, where dest1 == dest2.
 define i32 @test(i32 %x) {
 ; CHECK-LABEL: @test(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 false, label [[MERGE:%.*]], label [[MERGE]]
 ; CHECK:       merge:

 ; CHECK-LABEL: @test02(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_TRUE_1:%.*]], label [[IF_FALSE_1:%.*]]
 ; CHECK:       if.true.1:
 ; CHECK-NEXT:    br label [[MERGE_1:%.*]]
 ; CHECK:       if.false.1:
 ; CHECK-NEXT:    br label [[MERGE_1]]
 ; CHECK:       merge.1:
-; CHECK-NEXT:    br i1 [[COND]], label [[IF_FALSE_2:%.*]], label [[IF_TRUE_2:%.*]]
+; CHECK:         [[TMP0:%.*]] = xor i1 [[COND]], true
+; CHECK-NEXT:    br i1 [[TMP0]], label [[IF_TRUE_2:%.*]], label [[IF_FALSE_2:%.*]]
 ; CHECK:       if.true.2:
 ; CHECK-NEXT:    br label [[MERGE_2:%.*]]
 ; CHECK:       if.false.2:
 ; CHECK-NEXT:    br label [[MERGE_2]]
 ; CHECK:       merge.2:
 ; CHECK-NEXT:    ret i1 [[COND]]
 ;
 entry:

llvm/test/Transforms/InstCombine/canonicalize_branch.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt < %s -instcombine -S | FileCheck %s
+; RUN: opt < %s -instcombine -instcombine-canonicalize-branch-predicates=0 -S | FileCheck %s
 
 ; Test an already canonical branch to make sure we don't flip those.
 define i32 @eq(i32 %X, i32 %Y) {
 ; CHECK-LABEL: @eq(
 ; CHECK-NEXT:    [[C:%.*]] = icmp eq i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br i1 [[C]], label [[T:%.*]], label [[F:%.*]], !prof !0
 ; CHECK:       T:
 ; CHECK-NEXT:    ret i32 12

 T:
   ret i32 12
 F:
   ret i32 123
 }
 
 define i32 @f_oge(float %X, float %Y) {
 ; CHECK-LABEL: @f_oge(
-; CHECK-NEXT:    [[C:%.*]] = fcmp ult float [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    br i1 [[C]], label [[F:%.*]], label [[T:%.*]], !prof !13
+; CHECK-NEXT:    [[C:%.*]] = fcmp oge float [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    br i1 [[C]], label [[T:%.*]], label [[F:%.*]], !prof !13
 ; CHECK:       T:
 ; CHECK-NEXT:    ret i32 12
 ; CHECK:       F:
 ; CHECK-NEXT:    ret i32 123
 ;
   %C = fcmp oge float %X, %Y
   br i1 %C, label %T, label %F, !prof !13
 T:

 T:
   ret i32 12
 F:
   ret i32 123
 }
 
 define i32 @f_ole(float %X, float %Y) {
 ; CHECK-LABEL: @f_ole(
-; CHECK-NEXT:    [[C:%.*]] = fcmp ugt float [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    br i1 [[C]], label [[F:%.*]], label [[T:%.*]], !prof !15
+; CHECK-NEXT:    [[C:%.*]] = fcmp ole float [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    br i1 [[C]], label [[T:%.*]], label [[F:%.*]], !prof !15
 ; CHECK:       T:
 ; CHECK-NEXT:    ret i32 12
 ; CHECK:       F:
 ; CHECK-NEXT:    ret i32 123
 ;
   %C = fcmp ole float %X, %Y
   br i1 %C, label %T, label %F, !prof !15
 T:
   ret i32 12
 F:
   ret i32 123
 }
 
 define i32 @f_one(float %X, float %Y) {
 ; CHECK-LABEL: @f_one(
-; CHECK-NEXT:    [[C:%.*]] = fcmp ueq float [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    br i1 [[C]], label [[F:%.*]], label [[T:%.*]], !prof !16
+; CHECK-NEXT:    [[C:%.*]] = fcmp one float [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    br i1 [[C]], label [[T:%.*]], label [[F:%.*]], !prof !16
 ; CHECK:       T:
 ; CHECK-NEXT:    ret i32 12
 ; CHECK:       F:
 ; CHECK-NEXT:    ret i32 123
 ;
   %C = fcmp one float %X, %Y
   br i1 %C, label %T, label %F, !prof !16
 T:

 ; CHECK: !5 = {{.*}} i32 99, i32 5}
 ; CHECK: !6 = {{.*}} i32 6, i32 99}
 ; CHECK: !7 = {{.*}} i32 99, i32 7}
 ; CHECK: !8 = {{.*}} i32 8, i32 99}
 ; CHECK: !9 = {{.*}} i32 99, i32 9}
 ; CHECK: !10 = {{.*}} i32 10, i32 99}
 ; CHECK: !11 = {{.*}} i32 11, i32 99}
 ; CHECK: !12 = {{.*}} i32 12, i32 99}
-; CHECK: !13 = {{.*}} i32 99, i32 13}
+; CHECK: !13 = {{.*}} i32 13, i32 99}
 ; CHECK: !14 = {{.*}} i32 14, i32 99}
-; CHECK: !15 = {{.*}} i32 99, i32 15}
-; CHECK: !16 = {{.*}} i32 99, i32 16}
+; CHECK: !15 = {{.*}} i32 15, i32 99}
+; CHECK: !16 = {{.*}} i32 16, i32 99}
 ; CHECK: !17 = {{.*}} i32 17, i32 99}
 ; CHECK: !18 = {{.*}} i32 18, i32 99}
 ; CHECK: !19 = {{.*}} i32 19, i32 99}
 ; CHECK: !20 = {{.*}} i32 20, i32 99}
 ; CHECK: !21 = {{.*}} i32 21, i32 99}
 ; CHECK: !22 = {{.*}} i32 22, i32 99}
 ; CHECK: !23 = {{.*}} i32 23, i32 99}
 ; CHECK: !24 = {{.*}} i32 24, i32 99}
 ; CHECK: !25 = {{.*}} i32 25, i32 99}
 

llvm/test/Transforms/InstCombine/select.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt < %s -instcombine -S | FileCheck %s
+; RUN: opt < %s -instcombine -instcombine-canonicalize-branch-predicates=0 -S | FileCheck %s
 
 ; PR1822
 
 target datalayout = "e-p:64:64-p1:16:16-p2:32:32:32-p3:64:64:64"
 
 define i1 @test5(i1 %C) {
 ; CHECK-LABEL: @test5(
 ; CHECK-NEXT:    [[NOT_C:%.*]] = xor i1 [[C:%.*]], true

 merge:
   %s = select i1 %cond, i32 %x, i32 %y
   ret i32 %s
 }
 
 define i32 @select_dominating_inverted(i1 %cond, i32 %x, i32 %y) {
 ; CHECK-LABEL: @select_dominating_inverted(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_FALSE:%.*]], label [[IF_TRUE:%.*]]
+; CHECK-NEXT:    [[INVERTED:%.*]] = xor i1 [[COND:%.*]], true
+; CHECK-NEXT:    br i1 [[INVERTED]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
 ; CHECK:       if.true:
 ; CHECK-NEXT:    br label [[MERGE:%.*]]
 ; CHECK:       if.false:
 ; CHECK-NEXT:    br label [[MERGE]]
 ; CHECK:       merge:
 ; CHECK-NEXT:    [[S:%.*]] = phi i32 [ [[X:%.*]], [[IF_FALSE]] ], [ [[Y:%.*]], [[IF_TRUE]] ]
 ; CHECK-NEXT:    ret i32 [[S]]
 ;

 exit:
   ret i32 0
 }
 
 ; More complex CFG for inverted case: the block with select has multiple predecessors.
 define i32 @select_dominating_cond_inverted_multiple_preds(i1 %cond, i1 %cond2, i1 %cond3, i32 %x, i32 %y) {
 ; CHECK-LABEL: @select_dominating_cond_inverted_multiple_preds(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_FALSE:%.*]], label [[IF_TRUE:%.*]]
+; CHECK-NEXT:    [[INVERTED:%.*]] = xor i1 [[COND:%.*]], true
+; CHECK-NEXT:    br i1 [[INVERTED]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
 ; CHECK:       if.true:
 ; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[IF_TRUE_1:%.*]], label [[IF_TRUE_2:%.*]]
 ; CHECK:       if.true.1:
 ; CHECK-NEXT:    br label [[MERGE:%.*]]
 ; CHECK:       if.true.2:
 ; CHECK-NEXT:    br label [[MERGE]]
 ; CHECK:       if.false:
 ; CHECK-NEXT:    br i1 [[COND3:%.*]], label [[IF_FALSE_1:%.*]], label [[EXIT:%.*]]

 exit:
   ret i32 0
 }
 
 ; More complex CFG for inverted case: the block with select has multiple predecessors that can duplicate.
 define i32 @select_dominating_cond_inverted_multiple_duplicating_preds(i1 %cond, i32 %cond2, i1 %cond3, i32 %x, i32 %y) {
 ; CHECK-LABEL: @select_dominating_cond_inverted_multiple_duplicating_preds(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_FALSE:%.*]], label [[IF_TRUE:%.*]]
+; CHECK-NEXT:    [[INVERTED:%.*]] = xor i1 [[COND:%.*]], true
+; CHECK-NEXT:    br i1 [[INVERTED]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
 ; CHECK:       if.true:
 ; CHECK-NEXT:    switch i32 [[COND2:%.*]], label [[SWITCH_CASE_1:%.*]] [
 ; CHECK-NEXT:    i32 1, label [[MERGE:%.*]]
 ; CHECK-NEXT:    i32 2, label [[MERGE]]
 ; CHECK-NEXT:    i32 3, label [[MERGE]]
 ; CHECK-NEXT:    ]
 ; CHECK:       switch.case.1:
 ; CHECK-NEXT:    br label [[MERGE]]

 exit:
   %sel = select i1 %cond, i32 %B, i32 %phi
   ret i32 %sel
 }
 
 define i32 @test_select_into_phi_not_idom_inverted(i1 %cond, i32 %A, i32 %B)  {
 ; CHECK-LABEL: @test_select_into_phi_not_idom_inverted(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_FALSE:%.*]], label [[IF_TRUE:%.*]]
+; CHECK-NEXT:    [[INVERTED:%.*]] = xor i1 [[COND:%.*]], true
+; CHECK-NEXT:    br i1 [[INVERTED]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
 ; CHECK:       if.true:
 ; CHECK-NEXT:    br label [[MERGE:%.*]]
 ; CHECK:       if.false:
 ; CHECK-NEXT:    br label [[MERGE]]
 ; CHECK:       merge:
 ; CHECK-NEXT:    [[SEL:%.*]] = phi i32 [ [[B:%.*]], [[IF_FALSE]] ], [ [[A:%.*]], [[IF_TRUE]] ]
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:

 exit:
   %sel = select i1 %cond, i32 %phi, i32 %A
   ret i32 %sel
 }
 
 define i32 @test_select_into_phi_not_idom_inverted_2(i1 %cond, i32 %A, i32 %B)  {
 ; CHECK-LABEL: @test_select_into_phi_not_idom_inverted_2(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_FALSE:%.*]], label [[IF_TRUE:%.*]]
+; CHECK-NEXT:    [[INVERTED:%.*]] = xor i1 [[COND:%.*]], true
+; CHECK-NEXT:    br i1 [[INVERTED]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
 ; CHECK:       if.true:
 ; CHECK-NEXT:    br label [[MERGE:%.*]]
 ; CHECK:       if.false:
 ; CHECK-NEXT:    br label [[MERGE]]
 ; CHECK:       merge:
 ; CHECK-NEXT:    [[SEL:%.*]] = phi i32 [ [[B:%.*]], [[IF_FALSE]] ], [ [[A:%.*]], [[IF_TRUE]] ]
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:

llvm/test/Transforms/InstCombine/xor-of-icmps-with-extra-uses.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt < %s -instcombine -instcombine-infinite-loop-threshold=2 -S | FileCheck %s
+; RUN: opt < %s -instcombine -instcombine-infinite-loop-threshold=4 -instcombine-canonicalize-branch-predicates=0 -S | FileCheck %s
 
 ; These xor-of-icmps could be replaced with and-of-icmps, but %cond0 has extra
 ; uses, so we don't consider it, even though some cases are freely invertible.
 
 ; %cond0 is extra-used in select, which is freely invertible.
 define i1 @v0_select_of_consts(i32 %X, i32* %selected) {
 ; CHECK-LABEL: @v0_select_of_consts(
 ; CHECK-NEXT:    [[COND0_INV:%.*]] = icmp sgt i32 [[X:%.*]], 32767
;
   %cond0 = icmp sgt i32 %X, 32767
   %cond1 = icmp sgt i32 %X, -32768
   %select = select i1 %cond0, i32 32767, i32 %Y
   store i32 %select, i32* %selected
   %res = xor i1 %cond0, %cond1
   ret i1 %res
 }
 
-; Branch is also freely invertible
+; Branch is not freely invertible because it changes CFG.
 define i1 @v3_branch(i32 %X, i32* %dst0, i32* %dst1) {
 ; CHECK-LABEL: @v3_branch(
 ; CHECK-NEXT:  begin:
-; CHECK-NEXT:    [[COND0:%.*]] = icmp slt i32 [[X:%.*]], 32768
-; CHECK-NEXT:    br i1 [[COND0]], label [[BB1:%.*]], label [[BB0:%.*]]
+; CHECK-NEXT:    [[COND0:%.*]] = icmp sgt i32 [[X:%.*]], 32767
+; CHECK-NEXT:    br i1 [[COND0]], label %bb0, label %bb1
 ; CHECK:       bb0:
 ; CHECK-NEXT:    store i32 0, i32* [[DST0:%.*]], align 4
 ; CHECK-NEXT:    br label [[END:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    store i32 0, i32* [[DST1:%.*]], align 4
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
 ; CHECK-NEXT:    [[X_OFF:%.*]] = add i32 [[X]], 32767

llvm/test/Transforms/InstCombine/xor.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt < %s -instcombine -S | FileCheck %s
+; RUN: opt < %s -instcombine -instcombine-canonicalize-branch-predicates=0 -S | FileCheck %s
 
 @G1 = global i32 0
 @G2 = global i32 0
 
 define i1 @test0(i1 %A) {
 ; CHECK-LABEL: @test0(
 ; CHECK-NEXT:    ret i1 [[A:%.*]]
 ;
;
   %A1 = and i32 %A, 7
   %B1 = and i32 %B, 128
   %C1 = xor i32 %A1, %B1
   ret i32 %C1
 }
 
 define i8 @test8(i1 %c) {
 ; CHECK-LABEL: @test8(
-; CHECK-NEXT:    br i1 [[C:%.*]], label [[FALSE:%.*]], label [[TRUE:%.*]]
+; CHECK-NEXT:    [[D:%.*]] = xor i1 %c, true
+; CHECK-NEXT:    br i1 [[D]], label %True, label %False
 ; CHECK:       True:
 ; CHECK-NEXT:    ret i8 1
 ; CHECK:       False:
 ; CHECK-NEXT:    ret i8 3
 ;
   %d = xor i1 %c, true
   br i1 %d, label %True, label %False