[RISCV] Return false from shouldFormOverflowOp when type is i8 and i16

[liaolucy]

Summary

i8 and i16 are not using overflow.
Reduce the number of zero extension instructions.

To reduce the uncertainty of the unknown,
most of the checks of the virtual function are kept

[craig.topper]

The regression in D142071 was for i64 on rv32. Do we need to disable this completely or only for that case?

[liaolucy]

rebase and add more testcases

[liaolucy]

llvm/test/CodeGen/RISCV/overflow-intrinsics.ll

84

This can be optimized in riscv DAG combine. I'll write another patch.
to:

%add = add i64 %b, %a
%cmp = icmp ult i64 %b, 0
%Q = select i1 %cmp, i64 %b, i64 42
store i64 %add, ptr %res

[liaolucy]

In D143646#4115724, @craig.topper wrote:

The regression in D142071 was for i64 on rv32. Do we need to disable this completely or only for that case?

I added more examples and it looks like there are optimizations on some rv64

[craig.topper]

llvm/test/CodeGen/RISCV/overflow-intrinsics.ll

84

That doesn't look right.

%cmp = icmp ult i64 %b, 0

is always false. There is no value of %b that can less than 0 when treated as unsigned. 0 is the smallest value.

[liaolucy]

Solving the regression of uaddo1_math_overflow_used.

the regression testcase.

define i64 @uaddo1_math_overflow_used(i64 %a, i64 %b, ptr %res) nounwind ssp {
  %add = add i64 %b, %a
  %cmp = icmp ult i64 %add, %a ----------%a
  %Q = select i1 %cmp, i64 %b, i64 42
  store i64 %add, ptr %res
  ret i64 %Q
}

No regression, the testcase from the following of file

define i64 @uaddo2_math_overflow_used(i64 %a, i64 %b, ptr %res) nounwind ssp {
  %add = add i64 %b, %a
  %cmp = icmp ult i64 %add, %b -----------%b
  %Q = select i1 %cmp, i64 %b, i64 42
  store i64 %add, ptr %res
  ret i64 %Q
}

So I think it is good to modify it to:

define i64 @uaddo1_math_overflow_used(i64 %a, i64 %b, ptr %res) nounwind ssp {
  %add = add i64 %a, %b    --------a and b exchange positions
  %cmp = icmp ult i64 %add, %a 
  %Q = select i1 %cmp, i64 %b, i64 42
  store i64 %add, ptr %res
  ret i64 %Q
}

[craig.topper]

llvm/lib/Target/RISCV/RISCVISelLowering.cpp

8931 ↗

(On Diff #498742)

This replaces N0, but the variable N0 still escapes into the following code pointing at the original ADD.

[craig.topper]

llvm/lib/Target/RISCV/RISCVISelLowering.cpp

8923 ↗

(On Diff #498742)

I don't understand this criteria. Just looking at the operands of the add is arbitrary. In your example, it seems like the select is important, but you don't check for that.

[liaolucy]

llvm/lib/Target/RISCV/RISCVISelLowering.cpp

8923 ↗

(On Diff #498742)

It should have nothing to do with the select instruction.
In fact selectDAG is just one more instruction than before: %10:gpr = SLTU %6:gpr, %0:gpr
IR Dump After Machine code sinking (machine-sink) : generating redundant branch instruction + copy SLTU

when add 64 is expanded, it is compared with the left side by default.
https://github.com/llvm/llvm-project/blob/main/llvm/lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp#L3017

Optimized lowered selection DAG: %bb.0 
'uaddo1_math_overflow_used:'
SelectionDAG has 29 nodes:
  t0: ch,glue = EntryToken
    t2: i32,ch = CopyFromReg t0, Register:i32 %0
    t4: i32,ch = CopyFromReg t0, Register:i32 %1
  t11: i64 = build_pair t2, t4
    t6: i32,ch = CopyFromReg t0, Register:i32 %2
    t8: i32,ch = CopyFromReg t0, Register:i32 %3
  t12: i64 = build_pair t6, t8
  t13: i64 = add t12, t11
    t15: i1 = setcc t13, t11, setult:ch
  t17: i64 = select t15, t12, Constant:i64<42>
      t10: i32,ch = CopyFromReg t0, Register:i32 %4
    t20: ch = store<(store (s64) into %ir.res)> t0, t13, t10, undef:i32
    t23: i32 = extract_element t17, Constant:i32<0>
  t25: ch,glue = CopyToReg t20, Register:i32 $x10, t23
    t22: i32 = extract_element t17, Constant:i32<1>
  t27: ch,glue = CopyToReg t25, Register:i32 $x11, t22, t25:1
  t28: ch = RISCVISD::RET_FLAG t27, Register:i32 $x10, Register:i32 $x11, t27:1


Type-legalized selection DAG: %bb.0 'uaddo1_math_overflow_used:'
SelectionDAG has 38 nodes:
  t0: ch,glue = EntryToken
  t2: i32,ch = CopyFromReg t0, Register:i32 %0
  t4: i32,ch = CopyFromReg t0, Register:i32 %1
  t6: i32,ch = CopyFromReg t0, Register:i32 %2
  t8: i32,ch = CopyFromReg t0, Register:i32 %3
  t10: i32,ch = CopyFromReg t0, Register:i32 %4
      t44: ch = store<(store (s32) into %ir.res, align 8)> t0, t30, t10, undef:i32
        t46: i32 = add nuw t10, Constant:i32<4>
      t47: ch = store<(store (s32) into %ir.res + 4, basealign 8)> t0, t33, t46, undef:i32
    t48: ch = TokenFactor t44, t47
    t35: i32 = select t38, t6, Constant:i32<42>
  t25: ch,glue = CopyToReg t48, Register:i32 $x10, t35
    t36: i32 = select t38, t8, Constant:i32<0>
  t27: ch,glue = CopyToReg t25, Register:i32 $x11, t36, t25:1
  t30: i32 = add t6, t2
    t31: i32 = add t8, t4
    t32: i32 = setcc t30, t6, setult:ch -------- if change to :  t32: i32 = setcc t30, t2, setult:ch
  t33: i32 = add t31, t32
      t42: i32 = setcc t33, t4, seteq:ch
      t39: i32 = setcc t30, t2, setult:ch. -------  t32 and t42 are the same， t32/t42 can be delete.
      t40: i32 = setcc t33, t4, setult:ch
    t43: i32 = select t42, t39, t40
  t38: i32 = and t43, Constant:i32<1>
  t28: ch = RISCVISD::RET_FLAG t27, Register:i32 $x10, Register:i32 $x11, t27:1

[craig.topper]

llvm/lib/Target/RISCV/RISCVISelLowering.cpp

8923 ↗

(On Diff #498742)

Ok I understand now. I'm concerned there aren't enough checks here to prevent infinite loops. If there are two setccs that both use the add but compare to a different operand, we'll infinite loop commuting the add.

[liaolucy]

llvm/lib/Target/RISCV/RISCVISelLowering.cpp

8923 ↗

(On Diff #498742)

Thanks Craig.
I didn't think of a good way to solve this problem and I will remove this code. Probably need to test benchmark to prove if this patch is really needed.

[liaolucy]

A+B u< A is the same result as A+B u< B.
There is no regression now, and there should be no logical problem.

[craig.topper]

I have a completely different proposal I will post shortly.

[liaolucy]

I found that i8 and i16 are better without overflow, so I kept it here and returned false when the data type is i8 and i16

overflow promote, LHS and RHS use ZExtPromotedInteger in PromoteIntRes_UADDSUBO.
add promote, LHS and RHS GetPromotedInteger int PromoteIntRes_SimpleIntBinOp.
Therefore the overflow has an extra zero extension instruction.
If there is another better way, I am willing to learn

[craig.topper]

I'm not sure the tests are here are sufficient to motivate this change. They "noncanonical" having the 1 on the LHS of an add instead of the RHS. And they only test the +1 case. Does shouldFormOverflowOp only apply to +1?

[liaolucy]

Add a testcase where both the LHS and RHS are not immediate, and it reduces one 'and' instruction.

[craig.topper]

llvm/lib/Target/RISCV/RISCVISelLowering.h

492

What if we did

if (VT == MVT::i8 || VT == MVT::i16)
  return false;

return TargetLowering::shouldFormOverflowOp(Opcode, VT, MathUsed);

That would match how you've described this patch.

[liaolucy]

Address craig.topper's comments.
Address jrtc27's comments. https://reviews.llvm.org/rG42a5dda553e8

[craig.topper]

LGTM

llvm/lib/Target/RISCV/RISCVISelLowering.h

EmitInstrWithCustomInserter(MachineInstr &MI,
                               MachineBasicBlock *BB) const override;
 
   void AdjustInstrPostInstrSelection(MachineInstr &MI,
                                      SDNode *Node) const override;
 
   EVT getSetCCResultType(const DataLayout &DL, LLVMContext &Context,
                          EVT VT) const override;
 
+  bool shouldFormOverflowOp(unsigned Opcode, EVT VT,
+                            bool MathUsed) const override {
+    if (VT == MVT::i8 || VT == MVT::i16)
+      return false;
+
+    return TargetLowering::shouldFormOverflowOp(Opcode, VT, MathUsed);
+  }
+
   bool convertSetCCLogicToBitwiseLogic(EVT VT) const override {
     return VT.isScalarInteger();
   }
   bool convertSelectOfConstantsToMath(EVT VT) const override { return true; }
 
   bool preferZeroCompareBranch() const override { return true; }
 
   bool shouldInsertFencesForAtomic(const Instruction *I) const override {

llvm/test/CodeGen/RISCV/overflow-intrinsics.ll

 ; RV64-NEXT:  .LBB1_2:
 ; RV64-NEXT:    sd a0, 0(a2)
 ; RV64-NEXT:    mv a0, a1
 ; RV64-NEXT:    ret
   %add = add i64 %b, %a
   %cmp = icmp ult i64 %add, %a
   %Q = select i1 %cmp, i64 %b, i64 42
   store i64 %add, ptr %res
   ret i64 %Q
 }
 
 define i64 @uaddo2_overflow_used(i64 %a, i64 %b) nounwind ssp {
 ; RV32-LABEL: uaddo2_overflow_used:
 ; RV32:       # %bb.0:
 ; RV32-NEXT:    add a1, a3, a1
 ; RV32-NEXT:    add a0, a2, a0
 ; RV32-NEXT:    sltu a0, a0, a2
; RV64-NEXT:    ret
   %ov = icmp eq i64 %a, 0
   store i64 %a, ptr %p
   ret i1 %ov
 }
 
 define i1 @uaddo_i8_increment_noncanonical_1(i8 %x, ptr %p) {
 ; RV32-LABEL: uaddo_i8_increment_noncanonical_1:
 ; RV32:       # %bb.0:
-; RV32-NEXT:    andi a0, a0, 255
 ; RV32-NEXT:    addi a2, a0, 1
 ; RV32-NEXT:    andi a0, a2, 255
-; RV32-NEXT:    xor a0, a0, a2
-; RV32-NEXT:    snez a0, a0
+; RV32-NEXT:    seqz a0, a0
 ; RV32-NEXT:    sb a2, 0(a1)
 ; RV32-NEXT:    ret
 ;
 ; RV64-LABEL: uaddo_i8_increment_noncanonical_1:
 ; RV64:       # %bb.0:
-; RV64-NEXT:    andi a0, a0, 255
-; RV64-NEXT:    addi a2, a0, 1
+; RV64-NEXT:    addiw a2, a0, 1
 ; RV64-NEXT:    andi a0, a2, 255
-; RV64-NEXT:    xor a0, a0, a2
-; RV64-NEXT:    snez a0, a0
+; RV64-NEXT:    seqz a0, a0
 ; RV64-NEXT:    sb a2, 0(a1)
 ; RV64-NEXT:    ret
   %a = add i8 1, %x        ; commute
   %ov = icmp eq i8 %a, 0
   store i8 %a, ptr %p
   ret i1 %ov
 }
 
; RV64-NEXT:    ret
   %ov = icmp eq i32 0, %a   ; commute
   store i32 %a, ptr %p
   ret i1 %ov
 }
 
 define i1 @uaddo_i16_increment_noncanonical_3(i16 %x, ptr %p) {
 ; RV32-LABEL: uaddo_i16_increment_noncanonical_3:
 ; RV32:       # %bb.0:
-; RV32-NEXT:    lui a2, 16
-; RV32-NEXT:    addi a2, a2, -1
-; RV32-NEXT:    and a0, a0, a2
-; RV32-NEXT:    addi a3, a0, 1
-; RV32-NEXT:    and a2, a3, a2
-; RV32-NEXT:    xor a2, a2, a3
-; RV32-NEXT:    snez a0, a2
-; RV32-NEXT:    sh a3, 0(a1)
+; RV32-NEXT:    addi a2, a0, 1
+; RV32-NEXT:    slli a0, a2, 16
+; RV32-NEXT:    srli a0, a0, 16
+; RV32-NEXT:    seqz a0, a0
+; RV32-NEXT:    sh a2, 0(a1)
 ; RV32-NEXT:    ret
 ;
 ; RV64-LABEL: uaddo_i16_increment_noncanonical_3:
 ; RV64:       # %bb.0:
-; RV64-NEXT:    lui a2, 16
-; RV64-NEXT:    addiw a2, a2, -1
-; RV64-NEXT:    and a0, a0, a2
-; RV64-NEXT:    addi a3, a0, 1
-; RV64-NEXT:    and a2, a3, a2
-; RV64-NEXT:    xor a2, a2, a3
-; RV64-NEXT:    snez a0, a2
-; RV64-NEXT:    sh a3, 0(a1)
+; RV64-NEXT:    addiw a2, a0, 1
+; RV64-NEXT:    slli a0, a2, 48
+; RV64-NEXT:    srli a0, a0, 48
+; RV64-NEXT:    seqz a0, a0
+; RV64-NEXT:    sh a2, 0(a1)
 ; RV64-NEXT:    ret
   %a = add i16 1, %x        ; commute
   %ov = icmp eq i16 0, %a   ; commute
   store i16 %a, ptr %p
   ret i1 %ov
 }
 
 ; The overflow check may be against the input rather than the sum.
true:
   %svalue = add i64 %key, -1
   store i64 %svalue, ptr %p64
   br label %exit
 
 exit:
   ret void
 }
 
-define i16 @overflow_not_used(i16 %a, i16 %b, ptr %res) nounwind ssp {
+define i16 @overflow_not_used(i16 %a, i16 %b, ptr %res) {
 ; RV32-LABEL: overflow_not_used:
 ; RV32:       # %bb.0:
 ; RV32-NEXT:    lui a3, 16
 ; RV32-NEXT:    addi a3, a3, -1
-; RV32-NEXT:    and a0, a0, a3
 ; RV32-NEXT:    and a4, a1, a3
-; RV32-NEXT:    add a0, a4, a0
+; RV32-NEXT:    add a0, a1, a0
 ; RV32-NEXT:    and a3, a0, a3
-; RV32-NEXT:    bne a3, a0, .LBB37_2
+; RV32-NEXT:    bltu a3, a4, .LBB37_2
 ; RV32-NEXT:  # %bb.1:
 ; RV32-NEXT:    li a1, 42
 ; RV32-NEXT:  .LBB37_2:
 ; RV32-NEXT:    sh a0, 0(a2)
 ; RV32-NEXT:    mv a0, a1
 ; RV32-NEXT:    ret
 ;
 ; RV64-LABEL: overflow_not_used:
 ; RV64:       # %bb.0:
 ; RV64-NEXT:    lui a3, 16
 ; RV64-NEXT:    addiw a3, a3, -1
-; RV64-NEXT:    and a0, a0, a3
 ; RV64-NEXT:    and a4, a1, a3
-; RV64-NEXT:    add a0, a4, a0
+; RV64-NEXT:    add a0, a1, a0
 ; RV64-NEXT:    and a3, a0, a3
-; RV64-NEXT:    bne a3, a0, .LBB37_2
+; RV64-NEXT:    bltu a3, a4, .LBB37_2
 ; RV64-NEXT:  # %bb.1:
 ; RV64-NEXT:    li a1, 42
 ; RV64-NEXT:  .LBB37_2:
 ; RV64-NEXT:    sh a0, 0(a2)
 ; RV64-NEXT:    mv a0, a1
 ; RV64-NEXT:    ret
   %add = add i16 %b, %a
   %cmp = icmp ult i16 %add, %b
   %Q = select i1 %cmp, i16 %b, i16 42
   store i16 %add, ptr %res
   ret i16 %Q
 }