[SelectionDAG] Handle inverted conditions when splitting into multiple branches.

[gberry]

Summary

When conditional branches with complex conditions are split into
multiple branches in SelectionDAGBuilder::FindMergedConditions, also
handle inverted conditions. These may sometimes appear without having
been optimized by InstCombine when CodeGenPrepare decides to sink and
duplicate cmp instructions, causing them to have only one use. This
problem can be increased by e.g. GVNHoist hiding more cmps from
InstCombine by combining equivalent cmps from different blocks.

For example codegen X & !(Y | Z) as:

  jmp_if_X TmpBB
  jmp FBB
TmpBB:
  jmp_if_notY Tmp2BB
  jmp FBB
Tmp2BB:
  jmp_if_notZ TBB
  jmp FBB

[mcrosier]

The patch seems to be inline with and extending the current functionality of the FindMergedConditions optimization, so it LGTM. However, I'll give others an opportunity to chime in before giving a formal approval.

Did you collect any performance results for AArch64 and/or X86? I looked at the AArch64 binary diffs, but nothing jumped out at me.

[gberry]

I did some performance testing on aarch64 (kryo) and there was a slight improvement overall, though almost all of the differences look to be due to indirect I$ effects.
For x86, the static instruction count improves by .02% over all benchmarks, with no significant static instruction count regressions.

My primary motivation for getting this patch in is to address PR31382 in order to get my change (D27722) to move GVNHoist later in the optimization pipeline re-enabled

[sebpop]

The change looks good to me: I will let one of the maintainers of selectionDAG approve the patch.
Thanks for fixing this such that we can close PR31382 and commit again the gvn-hoist patch.

[gberry]

Ping? @bogner would you mind taking a look at this or suggesting someone else that could?

[gberry]

Approved by @bogner via email

[nemanjai]

This commit causes https://llvm.org/bugs/show_bug.cgi?id=31914.
I imagine this is an issue in the PPC back end so I don't mind investigating. I'm just wondering if you have any suggestions as to what the issue might be.

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h

void setUnusedArgValue(const Value *V, SDValue NewN) {
     assert(!N.getNode() && "Already set a value for this node!");
     N = NewN;
   }
 
   void FindMergedConditions(const Value *Cond, MachineBasicBlock *TBB,
                             MachineBasicBlock *FBB, MachineBasicBlock *CurBB,
                             MachineBasicBlock *SwitchBB,
                             Instruction::BinaryOps Opc, BranchProbability TW,
-                            BranchProbability FW);
+                            BranchProbability FW, bool InvertCond);
   void EmitBranchForMergedCondition(const Value *Cond, MachineBasicBlock *TBB,
                                     MachineBasicBlock *FBB,
                                     MachineBasicBlock *CurBB,
                                     MachineBasicBlock *SwitchBB,
-                                    BranchProbability TW, BranchProbability FW);
+                                    BranchProbability TW, BranchProbability FW,
+                                    bool InvertCond);
   bool ShouldEmitAsBranches(const std::vector<CaseBlock> &Cases);
   bool isExportableFromCurrentBlock(const Value *V, const BasicBlock *FromBB);
   void CopyToExportRegsIfNeeded(const Value *V);
   void ExportFromCurrentBlock(const Value *V);
   void LowerCallTo(ImmutableCallSite CS, SDValue Callee, bool IsTailCall,
                    const BasicBlock *EHPadBB = nullptr);
 
   // Lower range metadata from 0 to N to assert zext to an integer of nearest

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

 ///
 void
 SelectionDAGBuilder::EmitBranchForMergedCondition(const Value *Cond,
                                                   MachineBasicBlock *TBB,
                                                   MachineBasicBlock *FBB,
                                                   MachineBasicBlock *CurBB,
                                                   MachineBasicBlock *SwitchBB,
                                                   BranchProbability TProb,
-                                                  BranchProbability FProb) {
+                                                  BranchProbability FProb,
+                                                  bool InvertCond) {
   const BasicBlock *BB = CurBB->getBasicBlock();
 
   // If the leaf of the tree is a comparison, merge the condition into
   // the caseblock.
   if (const CmpInst *BOp = dyn_cast<CmpInst>(Cond)) {
     // The operands of the cmp have to be in this block.  We don't know
     // how to export them from some other block.  If this is the first block
     // of the sequence, no exporting is needed.
     if (CurBB == SwitchBB ||
         (isExportableFromCurrentBlock(BOp->getOperand(0), BB) &&
          isExportableFromCurrentBlock(BOp->getOperand(1), BB))) {
       ISD::CondCode Condition;
       if (const ICmpInst *IC = dyn_cast<ICmpInst>(Cond)) {
-        Condition = getICmpCondCode(IC->getPredicate());
+        ICmpInst::Predicate Pred =
+            InvertCond ? IC->getInversePredicate() : IC->getPredicate();
+        Condition = getICmpCondCode(Pred);
       } else {
         const FCmpInst *FC = cast<FCmpInst>(Cond);
-        Condition = getFCmpCondCode(FC->getPredicate());
+        FCmpInst::Predicate Pred =
+            InvertCond ? FC->getInversePredicate() : FC->getPredicate();
+        Condition = getFCmpCondCode(Pred);
         if (TM.Options.NoNaNsFPMath)
           Condition = getFCmpCodeWithoutNaN(Condition);
       }
 
       CaseBlock CB(Condition, BOp->getOperand(0), BOp->getOperand(1), nullptr,
                    TBB, FBB, CurBB, TProb, FProb);
       SwitchCases.push_back(CB);
       return;
     }
   }
 
   // Create a CaseBlock record representing this branch.
-  CaseBlock CB(ISD::SETEQ, Cond, ConstantInt::getTrue(*DAG.getContext()),
+  ISD::CondCode Opc = InvertCond ? ISD::SETNE : ISD::SETEQ;
+  CaseBlock CB(Opc, Cond, ConstantInt::getTrue(*DAG.getContext()),
                nullptr, TBB, FBB, CurBB, TProb, FProb);
   SwitchCases.push_back(CB);
 }
 
 /// FindMergedConditions - If Cond is an expression like
 void SelectionDAGBuilder::FindMergedConditions(const Value *Cond,
                                                MachineBasicBlock *TBB,
                                                MachineBasicBlock *FBB,
                                                MachineBasicBlock *CurBB,
                                                MachineBasicBlock *SwitchBB,
                                                Instruction::BinaryOps Opc,
                                                BranchProbability TProb,
-                                               BranchProbability FProb) {
-  // If this node is not part of the or/and tree, emit it as a branch.
+                                               BranchProbability FProb,
+                                               bool InvertCond) {
+  // Skip over not part of the tree and remember to invert op and operands at
+  // next level.
+  if (BinaryOperator::isNot(Cond) && Cond->hasOneUse()) {
+    Cond = cast<Instruction>(Cond)->getOperand(0);
+    FindMergedConditions(Cond, TBB, FBB, CurBB, SwitchBB, Opc, TProb, FProb,
+                         !InvertCond);
+    return;
+  }
+
   const Instruction *BOp = dyn_cast<Instruction>(Cond);
+  // Compute the effective opcode for Cond, taking into account whether it needs
+  // to be inverted, e.g.
+  //   and (not (or A, B)), C
+  // gets lowered as
+  //   and (and (not A, not B), C)
+  unsigned BOpc = 0;
+  if (BOp) {
+    BOpc = BOp->getOpcode();
+    if (InvertCond) {
+      if (BOpc == Instruction::And)
+        BOpc = Instruction::Or;
+      else if (BOpc == Instruction::Or)
+        BOpc = Instruction::And;
+    }
+  }
+
+  // If this node is not part of the or/and tree, emit it as a branch.
   if (!BOp || !(isa<BinaryOperator>(BOp) || isa<CmpInst>(BOp)) ||
-      (unsigned)BOp->getOpcode() != Opc || !BOp->hasOneUse() ||
+      BOpc != Opc || !BOp->hasOneUse() ||
       BOp->getParent() != CurBB->getBasicBlock() ||
       !InBlock(BOp->getOperand(0), CurBB->getBasicBlock()) ||
       !InBlock(BOp->getOperand(1), CurBB->getBasicBlock())) {
     EmitBranchForMergedCondition(Cond, TBB, FBB, CurBB, SwitchBB,
-                                 TProb, FProb);
+                                 TProb, FProb, InvertCond);
     return;
   }
 
   //  Create TmpBB after CurBB.
   MachineFunction::iterator BBI(CurBB);
   MachineFunction &MF = DAG.getMachineFunction();
   MachineBasicBlock *TmpBB = MF.CreateMachineBasicBlock(CurBB->getBasicBlock());
   CurBB->getParent()->insert(++BBI, TmpBB);
if (Opc == Instruction::Or) {
     //   TrueProb for BB1 == FalseProb for BB1 * TrueProb for TmpBB.
     // Another choice is to assume TrueProb for BB1 equals to TrueProb for
     // TmpBB, but the math is more complicated.
 
     auto NewTrueProb = TProb / 2;
     auto NewFalseProb = TProb / 2 + FProb;
     // Emit the LHS condition.
     FindMergedConditions(BOp->getOperand(0), TBB, TmpBB, CurBB, SwitchBB, Opc,
-                         NewTrueProb, NewFalseProb);
+                         NewTrueProb, NewFalseProb, InvertCond);
 
     // Normalize A/2 and B to get A/(1+B) and 2B/(1+B).
     SmallVector<BranchProbability, 2> Probs{TProb / 2, FProb};
     BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end());
     // Emit the RHS condition into TmpBB.
     FindMergedConditions(BOp->getOperand(1), TBB, FBB, TmpBB, SwitchBB, Opc,
-                         Probs[0], Probs[1]);
+                         Probs[0], Probs[1], InvertCond);
   } else {
     assert(Opc == Instruction::And && "Unknown merge op!");
     // Codegen X & Y as:
     // BB1:
     //   jmp_if_X TmpBB
     //   jmp FBB
     // TmpBB:
     //   jmp_if_Y TBB
if (Opc == Instruction::Or) {
     // BB1's probabilities to A+B/2 and B/2, and set TmpBB's probabilities to
     // 2A/(1+A) and B/(1+A). This choice assumes that FalseProb for BB1 ==
     // TrueProb for BB1 * FalseProb for TmpBB.
 
     auto NewTrueProb = TProb + FProb / 2;
     auto NewFalseProb = FProb / 2;
     // Emit the LHS condition.
     FindMergedConditions(BOp->getOperand(0), TmpBB, FBB, CurBB, SwitchBB, Opc,
-                         NewTrueProb, NewFalseProb);
+                         NewTrueProb, NewFalseProb, InvertCond);
 
     // Normalize A and B/2 to get 2A/(1+A) and B/(1+A).
     SmallVector<BranchProbability, 2> Probs{TProb, FProb / 2};
     BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end());
     // Emit the RHS condition into TmpBB.
     FindMergedConditions(BOp->getOperand(1), TBB, FBB, TmpBB, SwitchBB, Opc,
-                         Probs[0], Probs[1]);
+                         Probs[0], Probs[1], InvertCond);
   }
 }
 
 /// If the set of cases should be emitted as a series of branches, return true.
 /// If we should emit this as a bunch of and/or'd together conditions, return
 /// false.
 bool
 SelectionDAGBuilder::ShouldEmitAsBranches(const std::vector<CaseBlock> &Cases) {
void SelectionDAGBuilder::visitBr(const BranchInst &I) {
   if (const BinaryOperator *BOp = dyn_cast<BinaryOperator>(CondVal)) {
     Instruction::BinaryOps Opcode = BOp->getOpcode();
     if (!DAG.getTargetLoweringInfo().isJumpExpensive() && BOp->hasOneUse() &&
         !I.getMetadata(LLVMContext::MD_unpredictable) &&
         (Opcode == Instruction::And || Opcode == Instruction::Or)) {
       FindMergedConditions(BOp, Succ0MBB, Succ1MBB, BrMBB, BrMBB,
                            Opcode,
                            getEdgeProbability(BrMBB, Succ0MBB),
-                           getEdgeProbability(BrMBB, Succ1MBB));
+                           getEdgeProbability(BrMBB, Succ1MBB),
+                           /*InvertCond=*/false);
       // If the compares in later blocks need to use values not currently
       // exported from this block, export them now.  This block should always
       // be the first entry.
       assert(SwitchCases[0].ThisBB == BrMBB && "Unexpected lowering!");
 
       // Allow some cases to be rejected.
       if (ShouldEmitAsBranches(SwitchCases)) {
         for (unsigned i = 1, e = SwitchCases.size(); i != e; ++i) {

test/CodeGen/AArch64/br-cond-not-merge.ll

+; RUN: llc -mtriple=aarch64 -verify-machineinstrs < %s | FileCheck %s
+
+declare void @foo()
+
+; Check that the inverted or doesn't inhibit the splitting of the
+; complex conditional into three branch instructions.
+; CHECK-LABEL: test_and_not
+; CHECK:       cbz w0, [[L:\.LBB[0-9_]+]]
+; CHECK:       cmp w1, #2
+; CHECK:       b.lo [[L]]
+; CHECK:       cmp w2, #2
+; CHECK:       b.hi [[L]]
+define void @test_and_not(i32 %a, i32 %b, i32 %c) {
+bb1:
+  %cmp1 = icmp ult i32 %a, 1
+  %cmp2 = icmp ult i32 %b, 2
+  %cmp3 = icmp ult i32 %c, 3
+  %or = or i1 %cmp1, %cmp2
+  %not.or = xor i1 %or, -1
+  %and = and i1 %not.or, %cmp3
+  br i1 %and, label %bb2, label %bb3
+
+bb2:
+  ret void
+
+bb3:
+  call void @foo()
+  ret void
+}
+
+
+

test/CodeGen/X86/cmov.ll

 ; PR4814
 
 
 @g_3 = external global i8                         ; <i8*> [#uses=1]
 @g_96 = external global i8                        ; <i8*> [#uses=2]
 @g_100 = external global i8                       ; <i8*> [#uses=2]
 @_2E_str = external constant [15 x i8], align 1   ; <[15 x i8]*> [#uses=1]
 
-define i32 @test4() nounwind {
+define i1 @test4() nounwind {
 entry:
   %0 = load i8, i8* @g_3, align 1                     ; <i8> [#uses=2]
   %1 = sext i8 %0 to i32                          ; <i32> [#uses=1]
   %.lobit.i = lshr i8 %0, 7                       ; <i8> [#uses=1]
   %tmp.i = zext i8 %.lobit.i to i32               ; <i32> [#uses=1]
   %tmp.not.i = xor i32 %tmp.i, 1                  ; <i32> [#uses=1]
   %iftmp.17.0.i.i = ashr i32 %1, %tmp.not.i       ; <i32> [#uses=1]
   %retval56.i.i = trunc i32 %iftmp.17.0.i.i to i8 ; <i8> [#uses=1]
func_4.exit.i:                                    ; preds = %bb.i.i.i, %entry
   br i1 %brmerge.i, label %func_1.exit, label %bb.i.i
 
 bb.i.i:                                           ; preds = %func_4.exit.i
   %5 = load volatile i8, i8* @g_100, align 1          ; <i8> [#uses=0]
   br label %func_1.exit
 
 func_1.exit:                                      ; preds = %bb.i.i, %func_4.exit.i
   %g_96.tmp.0.i = phi i8 [ %g_96.promoted.i, %bb.i.i ], [ %.mux.i, %func_4.exit.i ] ; <i8> [#uses=2]
+  %ret = phi i1 [ 0, %bb.i.i ], [ %.not.i, %func_4.exit.i ]
   store i8 %g_96.tmp.0.i, i8* @g_96
   %6 = zext i8 %g_96.tmp.0.i to i32               ; <i32> [#uses=1]
   %7 = tail call i32 (i8*, ...) @printf(i8* noalias getelementptr ([15 x i8], [15 x i8]* @_2E_str, i64 0, i64 0), i32 %6) nounwind ; <i32> [#uses=0]
-  ret i32 0
+  ret i1 %ret
 }
 
 declare i32 @printf(i8* nocapture, ...) nounwind
 
 
 ; Should compile to setcc | -2.
 ; rdar://6668608
 define i32 @test5(i32* nocapture %P) nounwind readonly {

test/CodeGen/X86/dagcombine-and-setcc.ll

 ; RUN: llc < %s | FileCheck %s
 
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx10.10.0"
 
 ; Function Attrs: nounwind
 declare i32 @printf(i8* nocapture readonly, ...)
 
 ; On X86 1 is true and 0 is false, so we can't perform the combine:
 ; (and (setgt X,  true), (setgt Y,  true)) -> (setgt (or X, Y), true)
 ; This combine only works if the true value is -1.
 
 
 ;CHECK: cmpl
-;CHECK: setg
+;CHECK: setl
 ;CHECK: cmpl
-;CHECK: setg
-;CHECK: andb
+;CHECK: setl
+;CHECK: orb
+;CHECK: je
 
 @.str = private unnamed_addr constant [4 x i8] c"%d\0A\00", align 1
 ; Function Attrs: optsize ssp uwtable
 define i32 @foo(i32 %a, i32 %b, i32 * %c) {
 if.else429:
   %cmp.i1144 = icmp eq i32* %c, null
   %cmp430 = icmp slt i32 %a, 2
   %cmp432 = icmp slt i32 %b, 2