[SelectionDAGBuilder][WIP] Teach visitBr to sink AND along with compares.

[craig.topper]

Summary

visitBr expands i1 And/Or of compares into multiple branches and
basic blocks.

We should also sink any Ands on the compare input if it would allow
the target to use an instruction like x86's TEST.

Need to cleanup some comments and add more tests. But wanted to
get early feedback on the direction.

Another option might be to use CodeGenPrepare to do the expansion.
I think it already does for fast isel. CodeGenPrepare already has
code for sinking Ands to compares.

[arsenm]

LGTM with nit

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

2219–2220

also use match for the zero case?

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

 //===- SelectionDAGBuilder.cpp - Selection-DAG building -------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
SelectionDAGBuilder::EmitBranchForMergedCondition(const Value *Cond,
                                                   BranchProbability TProb,
                                                   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)) {
+    Value *CmpLHS = BOp->getOperand(0);
+    Value *CmpRHS = BOp->getOperand(1);
     // 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))) {
+        (isExportableFromCurrentBlock(CmpLHS, BB) &&
+         isExportableFromCurrentBlock(CmpRHS, BB))) {
+      Value *CmpMHS = nullptr;
+
       ISD::CondCode Condition;
       if (const ICmpInst *IC = dyn_cast<ICmpInst>(Cond)) {
         ICmpInst::Predicate Pred =
             InvertCond ? IC->getInversePredicate() : IC->getPredicate();
         Condition = getICmpCondCode(Pred);
+
+        auto &TLI = DAG.getTargetLoweringInfo();
+        Value *AndLHS;
+        ConstantInt *AndRHS;
+        if (IC->isEquality() && isa<ConstantInt>(CmpRHS) &&
+            cast<ConstantInt>(CmpRHS)->isZero() &&
+            match(CmpLHS, m_OneUse(m_And(m_Value(AndLHS), m_ConstantInt(AndRHS)))) &&
+            TLI.isMaskAndCmp0FoldingBeneficial(*cast<Instruction>(CmpLHS)) &&
+            isExportableFromCurrentBlock(AndLHS, BB) &&
+            isExportableFromCurrentBlock(AndRHS, BB)) {
+          CmpLHS = AndLHS;
+          CmpMHS = AndRHS;
+        }
       } else {
         const FCmpInst *FC = cast<FCmpInst>(Cond);
         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,
+      CaseBlock CB(Condition, CmpLHS, CmpRHS, CmpMHS,
                    TBB, FBB, CurBB, getCurSDLoc(), TProb, FProb);
       SL->SwitchCases.push_back(CB);
       return;
     }
   }
 
   // Create a CaseBlock record representing this branch.
   ISD::CondCode Opc = InvertCond ? ISD::SETNE : ISD::SETEQ;
if (Opcode && !(match(BOp0, m_ExtractElt(m_Value(Vec), m_Value())) &&
       // be the first entry.
       assert(SL->SwitchCases[0].ThisBB == BrMBB && "Unexpected lowering!");
 
       // Allow some cases to be rejected.
       if (ShouldEmitAsBranches(SL->SwitchCases)) {
         for (unsigned i = 1, e = SL->SwitchCases.size(); i != e; ++i) {
           ExportFromCurrentBlock(SL->SwitchCases[i].CmpLHS);
           ExportFromCurrentBlock(SL->SwitchCases[i].CmpRHS);
+          if (SL->SwitchCases[i].CmpMHS)
+            ExportFromCurrentBlock(SL->SwitchCases[i].CmpMHS);
         }
 
         // Emit the branch for this block.
         visitSwitchCase(SL->SwitchCases[0], BrMBB);
         SL->SwitchCases.erase(SL->SwitchCases.begin());
         return;
       }
 
else if (CB.CmpRHS == ConstantInt::getFalse(*DAG.getContext()) &&
       // values are zero-extended. This breaks signed comparisons so truncate
       // back to the underlying type before doing the compare.
       if (CondLHS.getValueType() != MemVT) {
         CondLHS = DAG.getPtrExtOrTrunc(CondLHS, getCurSDLoc(), MemVT);
         CondRHS = DAG.getPtrExtOrTrunc(CondRHS, getCurSDLoc(), MemVT);
       }
       Cond = DAG.getSetCC(dl, MVT::i1, CondLHS, CondRHS, CB.CC);
     }
-  } else {
-    assert(CB.CC == ISD::SETLE && "Can handle only LE ranges now");
-
+  } else if (CB.CC == ISD::SETLE) {
     const APInt& Low = cast<ConstantInt>(CB.CmpLHS)->getValue();
     const APInt& High = cast<ConstantInt>(CB.CmpRHS)->getValue();
 
     SDValue CmpOp = getValue(CB.CmpMHS);
     EVT VT = CmpOp.getValueType();
 
     if (cast<ConstantInt>(CB.CmpLHS)->isMinValue(true)) {
       Cond = DAG.getSetCC(dl, MVT::i1, CmpOp, DAG.getConstant(High, dl, VT),
                           ISD::SETLE);
     } else {
       SDValue SUB = DAG.getNode(ISD::SUB, dl,
                                 VT, CmpOp, DAG.getConstant(Low, dl, VT));
       Cond = DAG.getSetCC(dl, MVT::i1, SUB,
                           DAG.getConstant(High-Low, dl, VT), ISD::SETULE);
     }
+  } else {
+    assert(ISD::isIntEqualitySetCC(CB.CC) && "Expected equality compare");
+    SDValue AndLHS = getValue(CB.CmpLHS);
+    SDValue AndRHS = getValue(CB.CmpMHS);
+    SDValue CmpRHS = getValue(CB.CmpRHS);
+    EVT VT = AndLHS.getValueType();
+
+    SDValue AND = DAG.getNode(ISD::AND, dl, VT, AndLHS, AndRHS);
+    Cond = DAG.getSetCC(dl, MVT::i1, AND, CmpRHS, CB.CC);
   }
 
   // Update successor info
   addSuccessorWithProb(SwitchBB, CB.TrueBB, CB.TrueProb);
   // TrueBB and FalseBB are always different unless the incoming IR is
   // degenerate. This only happens when running llc on weird IR.
   if (CB.TrueBB != CB.FalseBB)
     addSuccessorWithProb(SwitchBB, CB.FalseBB, CB.FalseProb);

llvm/test/CodeGen/X86/peephole-na-phys-copy-folding.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -mtriple=i386-linux-gnu -verify-machineinstrs %s -o - | FileCheck %s --check-prefix=CHECK32
 ; RUN: llc -mtriple=x86_64-linux-gnu -verify-machineinstrs %s -o - | FileCheck %s --check-prefix=CHECK64
 
 ; The peephole optimizer can elide some physical register copies such as
 ; EFLAGS. Make sure the flags are used directly, instead of needlessly using
 ; saving and restoring specific conditions.
 
 @L = external dso_local global i32
 @M = external dso_local global i8
 
 declare i32 @bar(i64)
 
 define i1 @plus_one() nounwind {
 ; CHECK32-LABEL: plus_one:
 ; CHECK32:       # %bb.0: # %entry
-; CHECK32-NEXT:    movzbl M, %eax
 ; CHECK32-NEXT:    incl L
 ; CHECK32-NEXT:    jne .LBB0_2
 ; CHECK32-NEXT:  # %bb.1: # %entry
-; CHECK32-NEXT:    andb $8, %al
+; CHECK32-NEXT:    testb $8, M
 ; CHECK32-NEXT:    je .LBB0_2
 ; CHECK32-NEXT:  # %bb.3: # %exit2
 ; CHECK32-NEXT:    xorl %eax, %eax
 ; CHECK32-NEXT:    retl
 ; CHECK32-NEXT:  .LBB0_2: # %exit
 ; CHECK32-NEXT:    movb $1, %al
 ; CHECK32-NEXT:    retl
 ;
 ; CHECK64-LABEL: plus_one:
 ; CHECK64:       # %bb.0: # %entry
-; CHECK64-NEXT:    movzbl M(%rip), %eax
 ; CHECK64-NEXT:    incl L(%rip)
 ; CHECK64-NEXT:    jne .LBB0_2
 ; CHECK64-NEXT:  # %bb.1: # %entry
-; CHECK64-NEXT:    andb $8, %al
+; CHECK64-NEXT:    testb $8, M(%rip)
 ; CHECK64-NEXT:    je .LBB0_2
 ; CHECK64-NEXT:  # %bb.3: # %exit2
 ; CHECK64-NEXT:    xorl %eax, %eax
 ; CHECK64-NEXT:    retq
 ; CHECK64-NEXT:  .LBB0_2: # %exit
 ; CHECK64-NEXT:    movb $1, %al
 ; CHECK64-NEXT:    retq
 entry:

 
 exit2:
   ret i1 false
 }
 
 define i1 @plus_forty_two() nounwind {
 ; CHECK32-LABEL: plus_forty_two:
 ; CHECK32:       # %bb.0: # %entry
-; CHECK32-NEXT:    movzbl M, %eax
 ; CHECK32-NEXT:    addl $42, L
 ; CHECK32-NEXT:    jne .LBB1_2
 ; CHECK32-NEXT:  # %bb.1: # %entry
-; CHECK32-NEXT:    andb $8, %al
+; CHECK32-NEXT:    testb $8, M
 ; CHECK32-NEXT:    je .LBB1_2
 ; CHECK32-NEXT:  # %bb.3: # %exit2
 ; CHECK32-NEXT:    xorl %eax, %eax
 ; CHECK32-NEXT:    retl
 ; CHECK32-NEXT:  .LBB1_2: # %exit
 ; CHECK32-NEXT:    movb $1, %al
 ; CHECK32-NEXT:    retl
 ;
 ; CHECK64-LABEL: plus_forty_two:
 ; CHECK64:       # %bb.0: # %entry
-; CHECK64-NEXT:    movzbl M(%rip), %eax
 ; CHECK64-NEXT:    addl $42, L(%rip)
 ; CHECK64-NEXT:    jne .LBB1_2
 ; CHECK64-NEXT:  # %bb.1: # %entry
-; CHECK64-NEXT:    andb $8, %al
+; CHECK64-NEXT:    testb $8, M(%rip)
 ; CHECK64-NEXT:    je .LBB1_2
 ; CHECK64-NEXT:  # %bb.3: # %exit2
 ; CHECK64-NEXT:    xorl %eax, %eax
 ; CHECK64-NEXT:    retq
 ; CHECK64-NEXT:  .LBB1_2: # %exit
 ; CHECK64-NEXT:    movb $1, %al
 ; CHECK64-NEXT:    retq
 entry:

 
 exit2:
   ret i1 false
 }
 
 define i1 @minus_one() nounwind {
 ; CHECK32-LABEL: minus_one:
 ; CHECK32:       # %bb.0: # %entry
-; CHECK32-NEXT:    movzbl M, %eax
 ; CHECK32-NEXT:    decl L
 ; CHECK32-NEXT:    jne .LBB2_2
 ; CHECK32-NEXT:  # %bb.1: # %entry
-; CHECK32-NEXT:    andb $8, %al
+; CHECK32-NEXT:    testb $8, M
 ; CHECK32-NEXT:    je .LBB2_2
 ; CHECK32-NEXT:  # %bb.3: # %exit2
 ; CHECK32-NEXT:    xorl %eax, %eax
 ; CHECK32-NEXT:    retl
 ; CHECK32-NEXT:  .LBB2_2: # %exit
 ; CHECK32-NEXT:    movb $1, %al
 ; CHECK32-NEXT:    retl
 ;
 ; CHECK64-LABEL: minus_one:
 ; CHECK64:       # %bb.0: # %entry
-; CHECK64-NEXT:    movzbl M(%rip), %eax
 ; CHECK64-NEXT:    decl L(%rip)
 ; CHECK64-NEXT:    jne .LBB2_2
 ; CHECK64-NEXT:  # %bb.1: # %entry
-; CHECK64-NEXT:    andb $8, %al
+; CHECK64-NEXT:    testb $8, M(%rip)
 ; CHECK64-NEXT:    je .LBB2_2
 ; CHECK64-NEXT:  # %bb.3: # %exit2
 ; CHECK64-NEXT:    xorl %eax, %eax
 ; CHECK64-NEXT:    retq
 ; CHECK64-NEXT:  .LBB2_2: # %exit
 ; CHECK64-NEXT:    movb $1, %al
 ; CHECK64-NEXT:    retq
 entry:

 
 exit2:
   ret i1 false
 }
 
 define i1 @minus_forty_two() nounwind {
 ; CHECK32-LABEL: minus_forty_two:
 ; CHECK32:       # %bb.0: # %entry
-; CHECK32-NEXT:    movzbl M, %eax
 ; CHECK32-NEXT:    addl $-42, L
 ; CHECK32-NEXT:    jne .LBB3_2
 ; CHECK32-NEXT:  # %bb.1: # %entry
-; CHECK32-NEXT:    andb $8, %al
+; CHECK32-NEXT:    testb $8, M
 ; CHECK32-NEXT:    je .LBB3_2
 ; CHECK32-NEXT:  # %bb.3: # %exit2
 ; CHECK32-NEXT:    xorl %eax, %eax
 ; CHECK32-NEXT:    retl
 ; CHECK32-NEXT:  .LBB3_2: # %exit
 ; CHECK32-NEXT:    movb $1, %al
 ; CHECK32-NEXT:    retl
 ;
 ; CHECK64-LABEL: minus_forty_two:
 ; CHECK64:       # %bb.0: # %entry
-; CHECK64-NEXT:    movzbl M(%rip), %eax
 ; CHECK64-NEXT:    addl $-42, L(%rip)
 ; CHECK64-NEXT:    jne .LBB3_2
 ; CHECK64-NEXT:  # %bb.1: # %entry
-; CHECK64-NEXT:    andb $8, %al
+; CHECK64-NEXT:    testb $8, M(%rip)
 ; CHECK64-NEXT:    je .LBB3_2
 ; CHECK64-NEXT:  # %bb.3: # %exit2
 ; CHECK64-NEXT:    xorl %eax, %eax
 ; CHECK64-NEXT:    retq
 ; CHECK64-NEXT:  .LBB3_2: # %exit
 ; CHECK64-NEXT:    movb $1, %al
 ; CHECK64-NEXT:    retq
 entry:

llvm/test/CodeGen/X86/pr57402.ll

 ; CHECK-NEXT:  # %bb.1: # %entry
 ; CHECK-NEXT:    xorl %eax, %eax
 ; CHECK-NEXT:    testb %al, %al
 ; CHECK-NEXT:    jne .LBB0_4
 ; CHECK-NEXT:  # %bb.2: # %entry
 ; CHECK-NEXT:    movswl %dx, %eax
 ; CHECK-NEXT:    movswl %cx, %ecx
 ; CHECK-NEXT:    andl %eax, %ecx
-; CHECK-NEXT:    imull %ecx, %eax
-; CHECK-NEXT:    testq %rax, %rax
+; CHECK-NEXT:    movslq %ecx, %rax
+; CHECK-NEXT:    imulq %rax, %rax
+; CHECK-NEXT:    testl %eax, %eax
 ; CHECK-NEXT:    jne .LBB0_3
 ; CHECK-NEXT:  .LBB0_4: # %if.end
 ; CHECK-NEXT:    retq
 ; CHECK-NEXT:  .LBB0_3: # %if.then
 entry:
   %.fr = freeze i64 undef
   %0 = trunc i64 %.fr to i16
   %1 = and i16 %0, -2