[RISCV] Added optimization patterns with Zbb extension

[iabg-sc]

Summary

Patterns were added to substitute comparison and logic operations with min and logic operations.
Pattern.1
i = a < c
j = b < c
res = i or j
changes to:
m = min(a, b)
res = m < c

Pattern.2
i = a >= c
j = b >= c
res = i and j // negation of the result from Pattern.1
changes to:
m = min(a, b)
tmp = m < c
res = tmp xor 1

Pattern.2 is similar to Pattern.1 except there is no sgeu instruction and result has to be inverted with xor 1.

This patch can resolve this issue: https://github.com/llvm/llvm-project/issues/56518

[craig.topper]

This seems more suited to a DAGCombine. We need to check the use count of the setccs to make sure we aren't increasing the number of instructions.

It can also allow the xori to be optimized away in some cases.

[iabg-sc]

This patch specific for RISCV. There is no guarantee that min/max will work faster than two comparisons on other archs.
I am not sure how count of the instructions can be increased as pattern explicitly specifies changes from three instructions to two (or three) instructions. Could you please give an example?
xori can be optimized later, but it requires more complex analysis than I suggest in this patch.
Right now I am trying to write self-expanding patterns in TableGen to support most cases.

[craig.topper]

In D133417#3776651, @iabg-sc wrote:

This patch specific for RISCV. There is no guarantee that min/max will work faster than two comparisons on other archs.

I meant RISC-V DAGCombine in RISCVISelLowering not the generic DAGCombiner.

I am not sure how count of the instructions can be increased as pattern explicitly specifies changes from three instructions to two (or three) instructions. Could you please give an example?

If the setccs have users other than the or/and, then they'll get selected by your pattern as well as the setcc only patterns to satisify the other users. Overall this would result in 4(2 from your pattern and 1 for each setcc) instructions being created instead of 3 if we had selected the OR and setcc separately.

xori can be optimized later, but it requires more complex analysis than I suggest in this patch.

We already have a combine to fold the xori into a beqz or bnez by inverting the branch condition. We also have several combines that can pull the xori through a later or/and using deMorgan's law to move it closer to a branch.

Right now I am trying to write self-expanding patterns in TableGen to support most cases.

[craig.topper]

llvm/test/CodeGen/RISCV/minu_xori.ll

5

The DAG for this before isel looks like

SelectionDAG has 16 nodes:                                                       
  t0: ch = EntryToken                                                            
  t2: i64,ch = CopyFromReg t0, Register:i64 %0                                   
          t4: i64,ch = CopyFromReg t0, Register:i64 %1                           
        t22: i64 = setcc t4, t2, setult:ch                                       
          t6: i64,ch = CopyFromReg t0, Register:i64 %2                           
        t19: i64 = setcc t6, t2, setult:ch                                       
      t26: i64 = or t22, t19                                                     
    t27: i64 = xor t26, Constant:i64<1>                                          
  t13: ch,glue = CopyToReg t0, Register:i64 $x10, t27                            
  t14: ch = RISCVISD::RET_FLAG t13, Register:i64 $x10, t13:1

There is no AND, the XOR with 1 was already created.

llvm/lib/Target/RISCV/RISCVInstrInfoZb.td

 //===----------------------------------------------------------------------===//
 
 let Predicates = [HasStdExtZbbOrZbpOrZbkb] in {
 def : Pat<(and GPR:$rs1, (not GPR:$rs2)), (ANDN GPR:$rs1, GPR:$rs2)>;
 def : Pat<(or  GPR:$rs1, (not GPR:$rs2)), (ORN  GPR:$rs1, GPR:$rs2)>;
 def : Pat<(xor GPR:$rs1, (not GPR:$rs2)), (XNOR GPR:$rs1, GPR:$rs2)>;
 } // Predicates = [HasStdExtZbbOrZbpOrZbkb]
 
+let Predicates = [HasStdExtZbb] in {
+def : Pat<(or  (setult GPR:$rs1, GPR:$rs3), (setult GPR:$rs2, GPR:$rs3)),
+          (SLTU (MINU GPR:$rs1, GPR:$rs2), GPR:$rs3)>;
+def : Pat<(and  (setuge GPR:$rs1, GPR:$rs3), (setuge GPR:$rs2, GPR:$rs3)),
+          (XORI (SLTU (MINU GPR:$rs1, GPR:$rs2), GPR:$rs3), 1)>;
+} // Predicates = [HasStdExtZbb]
+
 let Predicates = [HasStdExtZbbOrZbpOrZbkb] in {
 def : PatGprGpr<shiftop<rotl>, ROL>;
 def : PatGprGpr<shiftop<rotr>, ROR>;
 
 def : PatGprImm<rotr, RORI, uimmlog2xlen>;
 // There's no encoding for roli in the the 'B' extension as it can be
 // implemented with rori by negating the immediate.
 def : Pat<(rotl GPR:$rs1, uimmlog2xlen:$shamt),

llvm/test/CodeGen/RISCV/minu.ll

+; RUN: llc  -march=riscv64 -mattr=+v,+zbb -O3 < %s \
+; RUN:  | FileCheck %s
+
+
+define i1 @test(i64 %c, i64 %a, i64 %b) {
+entry:
+  %cmp0 = icmp ult i64 %a, %c
+  %cmp1 = icmp ult i64 %b, %c
+  %res = or i1 %cmp0, %cmp1
+; CHECK: minu [[REG1:a[0-9]+]], [[REG1]], [[REG2:a[0-9]+]]
+; CHECK: sltu [[REG0:a[0-9]+]], [[REG1]], [[REG0]]
+  ret i1 %res
+}
+

llvm/test/CodeGen/RISCV/minu_xori.ll

+; RUN: llc  -march=riscv64 -mattr=+v,+zbb -O3 < %s \
+; RUN:  | FileCheck %s
+
+
+define i1 @test(i64 %c, i64 %a, i64 %b) {
+entry:
+  %cmp0 = icmp uge i64 %a, %c
+  %cmp1 = icmp uge i64 %b, %c
+  %res = and i1 %cmp0, %cmp1
+; CHECK: minu [[REG1:a[0-9]+]], [[REG1]], [[REG2:a[0-9]+]]
+; CHECK: sltu [[REG0:a[0-9]+]], [[REG1]], [[REG0]]
+; CHECK: xori [[REG0]], [[REG0]], 1
+  ret i1 %res
+}
+