[RISCV] Branchless lowering for (select (x < 0), TrueConstant, FalseConstant) and (select (x >= 0), TrueConstant, FalseConstant)

[liaolucy]

Summary

This patch reduces the number of unpredictable branches

(select (x < 0), y, z) -> x >> (XLEN - 1) & (y - z) + z
(select (x >= 0), y, z) -> x >> (XLEN - 1) & (z - y) + y

[reames]

llvm/lib/Target/RISCV/RISCVISelLowering.cpp

9630

It looks like we can avoid the not here by swapping the operands.

select (x < 0), y, z -> (x >> (XLEN - 1) & (y - z) + z

9633

The code appears out of sync with the comment, not sure which is correct.

The MaskedValueIsZero check here allows rhs to be 0 or 1.

9639

You shouldn't need these casts.

[liaolucy]

llvm/lib/Target/RISCV/RISCVISelLowering.cpp

9639

Is it open to all constants? There will be some code size increase

[craig.topper]

llvm/lib/Target/RISCV/RISCVISelLowering.cpp

9639

I think he was referring to the casts to uint64_t inside the isInt calls.. isInt takes a int64_t.

[liaolucy]

Address Philip Reames's comments

[craig.topper]

llvm/lib/Target/RISCV/RISCVISelLowering.cpp

9630

What about (x > -1), z, y?

[liaolucy]

Address Craig.topper's comments

Add (select (x >= 0), y, z) -> x >> (XLEN - 1) & (z - y) + y

Add (select (x > -1), y, z) to the testcase

[liaolucy]

Refactor, it feels clearer

[craig.topper]

llvm/lib/Target/RISCV/RISCVISelLowering.cpp

9637

Can you share most of the code by adding

if (CCVal == ISD::CondCode::SETGE)
  std::swap(TrueImm, FalseImm)

And another std::swap for TrueV and FalseV if the match succeeds?

[liaolucy]

Address craig.topper's comments, thanks

[reames]

LGTM

[craig.topper]

llvm/lib/Target/RISCV/RISCVISelLowering.cpp

9636

If you swap TrueV and FalseV here you need to swap them back at the end.

9652

Was this supposed to be TrueV and FalseV?

[reames]

llvm/lib/Target/RISCV/RISCVISelLowering.cpp

9652

That's what I read it as... good catch!

[liaolucy]

Update std::swap(TrueSImm, FalseSImm) to std::swap(TrueV, FalseV), thanks.

llvm/lib/Target/RISCV/RISCVISelLowering.cpp

9652

Sorry, I've been a bit confused lately.

[craig.topper]

llvm/lib/Target/RISCV/RISCVISelLowering.cpp

9652

I think this swap needs to only happen if you did the first swap. So you need to check CCVal is SETGE again

[liaolucy]

Check if CCVal is SETGE at the end

[craig.topper]

LGTM

llvm/lib/Target/RISCV/RISCVISelLowering.cpp

if (!Subtarget.hasShortForwardBranchOpt() && isNullConstant(RHS) &&
         else
           Neg = LHS;
         SDValue Mask = DAG.getNegative(Neg, DL, VT);               // -x
         SDValue And = DAG.getNode(ISD::AND, DL, VT, Mask, Src1); // Mask & z
         return DAG.getNode(Opcode, DL, VT, And, Src2);           // And Op y
       }
     }
 
+    // (select (x < 0), y, z)  -> x >> (XLEN - 1) & (y - z) + z
+    // (select (x >= 0), y, z) -> x >> (XLEN - 1) & (z - y) + y
+    if (!Subtarget.hasShortForwardBranchOpt() && isa<ConstantSDNode>(TrueV) &&
+        isa<ConstantSDNode>(FalseV) && isNullConstant(RHS) &&
+        (CCVal == ISD::CondCode::SETLT || CCVal == ISD::CondCode::SETGE)) {
+      int64_t TrueSImm = cast<ConstantSDNode>(TrueV)->getSExtValue();
+      int64_t FalseSImm = cast<ConstantSDNode>(FalseV)->getSExtValue();
+      // Only handle simm12, if it is not in this range, it can be considered as
+      // register.
+      if (isInt<12>(TrueSImm) && isInt<12>(FalseSImm) &&
+          isInt<12>(TrueSImm - FalseSImm)) {
+        SDValue SRA;
+        if (Subtarget.is64Bit())
+          SRA = DAG.getNode(ISD::SRA, DL, VT, LHS, DAG.getConstant(63, DL, VT));
+        else
+          SRA = DAG.getNode(ISD::SRA, DL, VT, LHS, DAG.getConstant(31, DL, VT));
+
+        if (CCVal == ISD::CondCode::SETLT) {
+          SDValue AND =
+              DAG.getNode(ISD::AND, DL, VT, SRA,
+                          DAG.getConstant(TrueSImm - FalseSImm, DL, VT));
+          return DAG.getNode(ISD::ADD, DL, VT, AND, FalseV);
+        }
+
+        SDValue AND =
+            DAG.getNode(ISD::AND, DL, VT, SRA,
+                        DAG.getConstant(FalseSImm - TrueSImm, DL, VT));
+        return DAG.getNode(ISD::ADD, DL, VT, AND, TrueV);
+      }
+    }
+
     if (combine_CC(LHS, RHS, CC, DL, DAG, Subtarget))
       return DAG.getNode(RISCVISD::SELECT_CC, DL, N->getValueType(0),
                          {LHS, RHS, CC, TrueV, FalseV});
 
     if (!Subtarget.hasShortForwardBranchOpt()) {
       // (select c, -1, y) -> -c | y
       if (isAllOnesConstant(TrueV)) {
         SDValue C = DAG.getSetCC(DL, VT, LHS, RHS, CCVal);

llvm/test/CodeGen/RISCV/select-const.ll

 ; RV64-NEXT:    lui a1, 2
 ; RV64-NEXT:    addiw a1, a1, 1810
 ; RV64-NEXT:    sub a0, a1, a0
 ; RV64-NEXT:    ret
   %1 = icmp ne i32 %a, %b
   %2 = select i1 %1, i32 10001, i32 10002
   ret i32 %2
 }
+
+define i32 @select_slt_zero_constant1_constant2(i32 signext %x) {
+; RV32-LABEL: select_slt_zero_constant1_constant2:
+; RV32:       # %bb.0:
+; RV32-NEXT:    srai a0, a0, 31
+; RV32-NEXT:    andi a0, a0, 10
+; RV32-NEXT:    addi a0, a0, -3
+; RV32-NEXT:    ret
+;
+; RV64-LABEL: select_slt_zero_constant1_constant2:
+; RV64:       # %bb.0:
+; RV64-NEXT:    srai a0, a0, 63
+; RV64-NEXT:    andi a0, a0, 10
+; RV64-NEXT:    addi a0, a0, -3
+; RV64-NEXT:    ret
+  %cmp = icmp slt i32 %x, 0
+  %cond = select i1 %cmp, i32 7, i32 -3
+  ret i32 %cond
+}
+
+define i32 @select_sgt_negative_one_constant1_constant2(i32 signext %x) {
+; RV32-LABEL: select_sgt_negative_one_constant1_constant2:
+; RV32:       # %bb.0:
+; RV32-NEXT:    srai a0, a0, 31
+; RV32-NEXT:    andi a0, a0, -10
+; RV32-NEXT:    addi a0, a0, 7
+; RV32-NEXT:    ret
+;
+; RV64-LABEL: select_sgt_negative_one_constant1_constant2:
+; RV64:       # %bb.0:
+; RV64-NEXT:    srai a0, a0, 63
+; RV64-NEXT:    andi a0, a0, -10
+; RV64-NEXT:    addi a0, a0, 7
+; RV64-NEXT:    ret
+  %cmp = icmp sgt i32 %x, -1
+  %cond = select i1 %cmp, i32 7, i32 -3
+  ret i32 %cond
+}