[DAGCombine] Canonicalize operands for visitANDLike

[hev]

Summary

During the construction of SelectionDAG, there are no explicit canonicalization rules to adjust the order of operands for AND nodes. This may prevent the optimization in DAGCombiner::visitANDLike from being triggered. This patch canonicalizes the operands before matches, which can be observed to improve optimization on the RISC-V target architecture.

Canonicalize:

and(x, add) -> and(add, x)

Signed-off-by: WANG Rui <[e-mail]>

[RKSimon]

please can you add test cases?

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

6199

Why are you having to swap all the ADD/SRL operand handling? Can't you just adjust the std::swap code above?

[hev]

Thanks.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

6199

The following has another match N0 == ISD::SRL.

6226–6227

Here

[hev]

Add a test case.

[asb]

@hev you don't seem to have used update_llc_test_checks.py to regenerate the test case, as the new function doesn't have RV32I check lines, and RV64I check lines weren't added to @main.

[jrtc27]

And when you do that, please put the new tests in their own commit so this one shows the diff to the generated code

[hev]

Rebase and update test case.

[craig.topper]

Description should say what the canonicalization is.

[hev]

1. Update test case.
2. Update description.

[RKSimon]

@hev please can you rebase after D146121?

[hev]

@RKSimon rebase done.

[RKSimon]

LGTM - cheers

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

SDValue DAGCombiner::visitANDLike(SDValue N0, SDValue N1, SDNode *N) {
 
   // fold (and x, undef) -> 0
   if (N0.isUndef() || N1.isUndef())
     return DAG.getConstant(0, DL, VT);
 
   if (SDValue V = foldLogicOfSetCCs(true, N0, N1, DL))
     return V;
 
+  // Canonicalize:
+  //   and(x, add) -> and(add, x)
+  if (N1.getOpcode() == ISD::ADD)
+    std::swap(N0, N1);
+
   // TODO: Rewrite this to return a new 'AND' instead of using CombineTo.
   if (N0.getOpcode() == ISD::ADD && N1.getOpcode() == ISD::SRL &&
       VT.getSizeInBits() <= 64 && N0->hasOneUse()) {
     if (ConstantSDNode *ADDI = dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
       if (ConstantSDNode *SRLI = dyn_cast<ConstantSDNode>(N1.getOperand(1))) {
         // Look for (and (add x, c1), (lshr y, c2)). If C1 wasn't a legal
         // immediate for an add, but it is legal if its top c2 bits are set,
         // transform the ADD so the immediate doesn't need to be materialized
         // in a register.
         APInt ADDC = ADDI->getAPIntValue();
         APInt SRLC = SRLI->getAPIntValue();
         if (ADDC.getSignificantBits() <= 64 && SRLC.ult(VT.getSizeInBits()) &&
             !TLI.isLegalAddImmediate(ADDC.getSExtValue())) {
if (ConstantSDNode *ADDI = dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
               // Return N so it doesn't get rechecked!
               return SDValue(N, 0);
             }
           }
         }
       }
     }
   }
 
   return SDValue();
 }
 
 bool DAGCombiner::isAndLoadExtLoad(ConstantSDNode *AndC, LoadSDNode *LoadN,
                                    EVT LoadResultTy, EVT &ExtVT) {
   if (!AndC->getAPIntValue().isMask())
     return false;
 
   unsigned ActiveBits = AndC->getAPIntValue().countr_one();

llvm/test/CodeGen/RISCV/and-add-lsr.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -mtriple=riscv32 -verify-machineinstrs < %s \
 ; RUN:   | FileCheck %s -check-prefix=RV32I
 ; RUN: llc -mtriple=riscv64 -verify-machineinstrs < %s \
 ; RUN:   | FileCheck %s -check-prefix=RV64I
 
 define i32 @and_add_lsr(i32 %x, i32 %y) {
 ; RV32I-LABEL: and_add_lsr:
 ; RV32I:       # %bb.0:
-; RV32I-NEXT:    lui a2, 1
-; RV32I-NEXT:    addi a2, a2, -1
-; RV32I-NEXT:    add a0, a0, a2
+; RV32I-NEXT:    addi a0, a0, -1
 ; RV32I-NEXT:    srli a1, a1, 20
 ; RV32I-NEXT:    and a0, a1, a0
 ; RV32I-NEXT:    ret
 ;
 ; RV64I-LABEL: and_add_lsr:
 ; RV64I:       # %bb.0:
-; RV64I-NEXT:    lui a2, 1
-; RV64I-NEXT:    addiw a2, a2, -1
-; RV64I-NEXT:    addw a0, a0, a2
+; RV64I-NEXT:    addiw a0, a0, -1
 ; RV64I-NEXT:    srliw a1, a1, 20
 ; RV64I-NEXT:    and a0, a1, a0
 ; RV64I-NEXT:    ret
   %1 = add i32 %x, 4095
   %2 = lshr i32 %y, 20
   %r = and i32 %2, %1
   ret i32 %r
 }