[ARM] Lower unsigned saturation to USAT

[thebolt]

Summary

Implement lower of unsigned saturation on an interval [0, k] where k + 1 is a power of two using USAT instruction in a similar way to how [~k, k] is lowered using SSAT on ARM models that supports it.

Patch by Marten Svanfeldt

[fhahn]

Thanks for the patch! Please upload a diff with more context: http://llvm.org/docs/Phabricator.html#id3 as this makes it easier to have a look at the code around your changes.

lib/Target/ARM/ARMISelLowering.cpp

4286

left over debug output

4312

nit: unrelated whitespace change.

12951

nit: unrelated change

12957

nit: unrelated change

[fhahn]

lib/Target/ARM/ARMISelLowering.cpp

4302

No braces needed here I think

[thebolt]

Updated based on review.
Removed extra white space changes, extra braces and left-in debug code.

[thebolt]

I've updated the diff based on the comments, also regenerated the diff with more context as per the instructions on llvm site.

[fhahn]

Thanks, this looks good to me, with the test extension. A nice extension to the SSAT case! Adding a couple of additional Arm people, to have a quick look.

test/CodeGen/ARM/usat.ll

2

This instruction should be available in ARMv6+ as well. Could you extend the test to cover that as well?

[thebolt]

Add tests for ARMv6 (non-thumb)

[fhahn]

LGTM, thanks

[thebolt]

I don't have any commit rights so would be happy if someone else picks it up

[fhahn]

Done! Thanks for the patch :)

lib/Target/ARM/ARMISelLowering.h

enum NodeType : unsigned {
       CMPZ,         // ARM compare that sets only Z flag.
       CMPFP,        // ARM VFP compare instruction, sets FPSCR.
       CMPFPw0,      // ARM VFP compare against zero instruction, sets FPSCR.
       FMSTAT,       // ARM fmstat instruction.
 
       CMOV,         // ARM conditional move instructions.
 
       SSAT,         // Signed saturation
+      USAT,         // Unsigned saturation
 
       BCC_i64,
 
       SRL_FLAG,     // V,Flag = srl_flag X -> srl X, 1 + save carry out.
       SRA_FLAG,     // V,Flag = sra_flag X -> sra X, 1 + save carry out.
       RRX,          // V = RRX X, Flag     -> srl X, 1 + shift in carry flag.
 
       ADDC,         // Add with carry

lib/Target/ARM/ARMISelLowering.cpp

const char *ARMTargetLowering::getTargetNodeName(unsigned Opcode) const {
   case ARMISD::CMPFP:         return "ARMISD::CMPFP";
   case ARMISD::CMPFPw0:       return "ARMISD::CMPFPw0";
   case ARMISD::BCC_i64:       return "ARMISD::BCC_i64";
   case ARMISD::FMSTAT:        return "ARMISD::FMSTAT";
 
   case ARMISD::CMOV:          return "ARMISD::CMOV";
 
   case ARMISD::SSAT:          return "ARMISD::SSAT";
+  case ARMISD::USAT:          return "ARMISD::USAT";
 
   case ARMISD::SRL_FLAG:      return "ARMISD::SRL_FLAG";
   case ARMISD::SRA_FLAG:      return "ARMISD::SRA_FLAG";
   case ARMISD::RRX:           return "ARMISD::RRX";
 
   case ARMISD::ADDC:          return "ARMISD::ADDC";
   case ARMISD::ADDE:          return "ARMISD::ADDE";
   case ARMISD::SUBC:          return "ARMISD::SUBC";
static bool isUpperSaturate(const SDValue LHS, const SDValue RHS,
                             const SDValue TrueVal, const SDValue FalseVal,
                             const ISD::CondCode CC, const SDValue K) {
   return (isGTorGE(CC) &&
           ((K == RHS && K == TrueVal) || (K == LHS && K == FalseVal))) ||
          (isLTorLE(CC) &&
           ((K == LHS && K == TrueVal) || (K == RHS && K == FalseVal)));
 }
 
-// Check if two chained conditionals could be converted into SSAT.
+// Check if two chained conditionals could be converted into SSAT or USAT.
 //
 // SSAT can replace a set of two conditional selectors that bound a number to an
 // interval of type [k, ~k] when k + 1 is a power of 2. Here are some examples:
 //
 //     x < -k ? -k : (x > k ? k : x)
 //     x < -k ? -k : (x < k ? x : k)
 //     x > -k ? (x > k ? k : x) : -k
 //     x < k ? (x < -k ? -k : x) : k
 //     etc.
 //
+// USAT works similarily to SSAT but bounds on the interval [0, k] where k + 1 is
+// a power of 2.
+//
 // It returns true if the conversion can be done, false otherwise.
-// Additionally, the variable is returned in parameter V and the constant in K.
+// Additionally, the variable is returned in parameter V, the constant in K and
+// usat is set to true if the conditional represents an unsigned saturation
 static bool isSaturatingConditional(const SDValue &Op, SDValue &V,
-                                    uint64_t &K) {
+                                    uint64_t &K, bool &usat) {
   SDValue LHS1 = Op.getOperand(0);
   SDValue RHS1 = Op.getOperand(1);
   SDValue TrueVal1 = Op.getOperand(2);
   SDValue FalseVal1 = Op.getOperand(3);
   ISD::CondCode CC1 = cast<CondCodeSDNode>(Op.getOperand(4))->get();
 
   const SDValue Op2 = isa<ConstantSDNode>(TrueVal1) ? FalseVal1 : TrueVal1;
   if (Op2.getOpcode() != ISD::SELECT_CC)
static bool isSaturatingConditional(const SDValue &Op, SDValue &V,
   const SDValue *UpperCheckOp =
       isUpperSaturate(LHS1, RHS1, TrueVal1, FalseVal1, CC1, *K1)
           ? &Op
           : isUpperSaturate(LHS2, RHS2, TrueVal2, FalseVal2, CC2, *K2)
                 ? &Op2
                 : nullptr;
 
   if (!UpperCheckOp || !LowerCheckOp || LowerCheckOp == UpperCheckOp)
     return false;
 
   // Check that the constant in the lower-bound check is
   // the opposite of the constant in the upper-bound check
   // in 1's complement.
   int64_t Val1 = cast<ConstantSDNode>(*K1)->getSExtValue();
   int64_t Val2 = cast<ConstantSDNode>(*K2)->getSExtValue();
   int64_t PosVal = std::max(Val1, Val2);
+  int64_t NegVal = std::min(Val1, Val2);
 
   if (((Val1 > Val2 && UpperCheckOp == &Op) ||
        (Val1 < Val2 && UpperCheckOp == &Op2)) &&
-      Val1 == ~Val2 && isPowerOf2_64(PosVal + 1)) {
+      isPowerOf2_64(PosVal + 1)) {
+
+    // Handle the difference between USAT (unsigned) and SSAT (signed) saturation
+    if (Val1 == ~Val2)
+      usat = false;
+    else if (NegVal == 0)
+      usat = true;
+    else
+      return false;
 
     V = V2;
     K = (uint64_t)PosVal; // At this point, PosVal is guaranteed to be positive
+
     return true;
   }
 
   return false;
 }
 
 SDValue ARMTargetLowering::LowerSELECT_CC(SDValue Op, SelectionDAG &DAG) const {
   EVT VT = Op.getValueType();
   SDLoc dl(Op);
 
   // Try to convert two saturating conditional selects into a single SSAT
   SDValue SatValue;
   uint64_t SatConstant;
+  bool SatUSat;
   if (((!Subtarget->isThumb() && Subtarget->hasV6Ops()) || Subtarget->isThumb2()) &&
-      isSaturatingConditional(Op, SatValue, SatConstant))
+      isSaturatingConditional(Op, SatValue, SatConstant, SatUSat)) {
+    if (SatUSat)
+      return DAG.getNode(ARMISD::USAT, dl, VT, SatValue,
+                         DAG.getConstant(countTrailingOnes(SatConstant), dl, VT));
+    else
       return DAG.getNode(ARMISD::SSAT, dl, VT, SatValue,
                          DAG.getConstant(countTrailingOnes(SatConstant), dl, VT));
+  }
 
   SDValue LHS = Op.getOperand(0);
   SDValue RHS = Op.getOperand(1);
   ISD::CondCode CC = cast<CondCodeSDNode>(Op.getOperand(4))->get();
   SDValue TrueVal = Op.getOperand(2);
   SDValue FalseVal = Op.getOperand(3);
 
   if (Subtarget->isFPOnlySP() && LHS.getValueType() == MVT::f64) {
if (Subtarget->isThumb1Only()) {
     assert(Op->getValueType(0) == MVT::i32 && "Non-i32 post-inc op?!");
     if (Op->getOpcode() != ISD::ADD || !isNonExt)
       return false;
     auto *RHS = dyn_cast<ConstantSDNode>(Op->getOperand(1));
     if (!RHS || RHS->getZExtValue() != 4)
       return false;
     
     Offset = Op->getOperand(1);
     Base = Op->getOperand(0);
     AM = ISD::POST_INC;
     return true;
   }
   
   bool isInc;
   bool isLegal = false;
   if (Subtarget->isThumb2())
     isLegal = getT2IndexedAddressParts(Op, VT, isSEXTLoad, Base, Offset,
                                        isInc, DAG);
   else
     isLegal = getARMIndexedAddressParts(Op, VT, isSEXTLoad, Base, Offset,
                                         isInc, DAG);
   if (!isLegal)
     return false;

lib/Target/ARM/ARMInstrInfo.td

def ARMretflag       : SDNode<"ARMISD::RET_FLAG", SDTNone,
                               [SDNPHasChain, SDNPOptInGlue, SDNPVariadic]>;
 def ARMintretflag    : SDNode<"ARMISD::INTRET_FLAG", SDT_ARMcall,
                               [SDNPHasChain, SDNPOptInGlue, SDNPVariadic]>;
 def ARMcmov          : SDNode<"ARMISD::CMOV", SDT_ARMCMov,
                               [SDNPInGlue]>;
 
 def ARMssatnoshift   : SDNode<"ARMISD::SSAT", SDTIntSatNoShOp, []>;
 
+def ARMusatnoshift   : SDNode<"ARMISD::USAT", SDTIntSatNoShOp, []>;
+
 def ARMbrcond        : SDNode<"ARMISD::BRCOND", SDT_ARMBrcond,
                               [SDNPHasChain, SDNPInGlue, SDNPOutGlue]>;
 
 def ARMbrjt          : SDNode<"ARMISD::BR_JT", SDT_ARMBrJT,
                               [SDNPHasChain]>;
 def ARMbr2jt         : SDNode<"ARMISD::BR2_JT", SDT_ARMBr2JT,
                               [SDNPHasChain]>;
 

 }
 
 def : ARMV6Pat<(int_arm_ssat GPRnopc:$a, imm1_32:$pos),
                (SSAT imm1_32:$pos, GPRnopc:$a, 0)>;
 def : ARMV6Pat<(int_arm_usat GPRnopc:$a, imm0_31:$pos),
                (USAT imm0_31:$pos, GPRnopc:$a, 0)>;
 def : ARMPat<(ARMssatnoshift GPRnopc:$Rn, imm0_31:$imm),
              (SSAT imm0_31:$imm, GPRnopc:$Rn, 0)>;
+def : ARMPat<(ARMusatnoshift GPRnopc:$Rn, imm0_31:$imm),
+             (USAT imm0_31:$imm, GPRnopc:$Rn, 0)>;
 def : ARMV6Pat<(int_arm_ssat16 GPRnopc:$a, imm1_16:$pos),
                (SSAT16 imm1_16:$pos, GPRnopc:$a)>;
 def : ARMV6Pat<(int_arm_usat16 GPRnopc:$a, imm0_15:$pos),
                (USAT16 imm0_15:$pos, GPRnopc:$a)>;
 
 //===----------------------------------------------------------------------===//
 //  Bitwise Instructions.
 //

lib/Target/ARM/ARMInstrThumb2.td

def t2USAT16: T2SatI<(ins imm0_15:$sat_imm, rGPR:$Rn),
                      Requires<[IsThumb2, HasDSP]> {
   let Inst{23-22} = 0b10;
   let sh = 0b100000;
   let Inst{4} = 0;
 }
 
 def : T2Pat<(ARMssatnoshift GPRnopc:$Rn, imm0_31:$imm),
              (t2SSAT imm0_31:$imm, GPRnopc:$Rn, 0)>;
+def : T2Pat<(ARMusatnoshift GPRnopc:$Rn, imm0_31:$imm),
+             (t2USAT imm0_31:$imm, GPRnopc:$Rn, 0)>;
 def : T2Pat<(int_arm_ssat GPR:$a, imm1_32:$pos),
             (t2SSAT imm1_32:$pos, GPR:$a, 0)>;
 def : T2Pat<(int_arm_usat GPR:$a, imm0_31:$pos),
             (t2USAT imm0_31:$pos, GPR:$a, 0)>;
 def : T2Pat<(int_arm_ssat16 GPR:$a, imm1_16:$pos),
             (t2SSAT16 imm1_16:$pos, GPR:$a)>;
 def : T2Pat<(int_arm_usat16 GPR:$a, imm0_15:$pos),
             (t2USAT16 imm0_15:$pos, GPR:$a)>;

test/CodeGen/ARM/usat.ll

+; RUN: llc -mtriple=armv4t-eabi %s -o -  | FileCheck %s --check-prefix=CHECK --check-prefix=V4T
+; RUN: llc -mtriple=armv6-eabi %s -o -   | FileCheck %s --check-prefix=CHECK --check-prefix=V6
+; RUN: llc -mtriple=armv6t2-eabi %s -o - | FileCheck %s --check-prefix=CHECK --check-prefix=V6T2
+
+; Check for several conditions that should result in USAT.
+; For example, the base test is equivalent to
+; x < 0 ? 0 : (x > k ? k : x) in C. All patterns that bound x
+; to the interval [0, k] where k + 1 is a power of 2 can be
+; transformed into USAT. At the end there are some tests
+; checking that conditionals are not transformed if they don't
+; match the right pattern.
+
+;
+; Base tests with different bit widths
+;
+
+; x < 0 ? 0 : (x > k ? k : x)
+; 32-bit base test
+define i32 @unsigned_sat_base_32bit(i32 %x) #0 {
+; CHECK-LABEL: unsigned_sat_base_32bit:
+; V6: usat r0, #23, r0
+; V6T2: usat r0, #23, r0
+; V4T-NOT: usat
+entry:
+  %cmpLow = icmp slt i32 %x, 0
+  %cmpUp = icmp sgt i32 %x, 8388607
+  %saturateUp = select i1 %cmpUp, i32 8388607, i32 %x
+  %saturateLow = select i1 %cmpLow, i32 0, i32 %saturateUp
+  ret i32 %saturateLow
+}
+
+; x < 0 ? 0 : (x > k ? k : x)
+; 16-bit base test
+define i16 @unsigned_sat_base_16bit(i16 %x) #0 {
+; CHECK-LABEL: unsigned_sat_base_16bit:
+; V6: usat r0, #11, r0
+; V6T2: usat r0, #11, r0
+; V4T-NOT: usat
+entry:
+  %cmpLow = icmp slt i16 %x, 0
+  %cmpUp = icmp sgt i16 %x, 2047
+  %saturateUp = select i1 %cmpUp, i16 2047, i16 %x
+  %saturateLow = select i1 %cmpLow, i16 0, i16 %saturateUp
+  ret i16 %saturateLow
+}
+
+; x < 0 ? 0 : (x > k ? k : x)
+; 8-bit base test
+define i8 @unsigned_sat_base_8bit(i8 %x) #0 {
+; CHECK-LABEL: unsigned_sat_base_8bit:
+; V6: usat r0, #5, r0
+; V6T2: usat r0, #5, r0
+; V4T-NOT: usat
+entry:
+  %cmpLow = icmp slt i8 %x, 0
+  %cmpUp = icmp sgt i8 %x, 31
+  %saturateUp = select i1 %cmpUp, i8 31, i8 %x
+  %saturateLow = select i1 %cmpLow, i8 0, i8 %saturateUp
+  ret i8 %saturateLow
+}
+
+;
+; Tests where the conditionals that check for upper and lower bounds,
+; or the < and > operators, are arranged in different ways. Only some
+; of the possible combinations that lead to USAT are tested.
+;
+; x < 0 ? 0 : (x < k ? x : k)
+define i32 @unsigned_sat_lower_upper_1(i32 %x) #0 {
+; CHECK-LABEL: unsigned_sat_lower_upper_1:
+; V6: usat r0, #23, r0
+; V6T2: usat r0, #23, r0
+; V4T-NOT: usat
+entry:
+  %cmpLow = icmp slt i32 %x, 0
+  %cmpUp = icmp slt i32 %x, 8388607
+  %saturateUp = select i1 %cmpUp, i32 %x, i32 8388607
+  %saturateLow = select i1 %cmpLow, i32 0, i32 %saturateUp
+  ret i32 %saturateLow
+}
+
+; x > 0 ? (x > k ? k : x) : 0
+define i32 @unsigned_sat_lower_upper_2(i32 %x) #0 {
+; CHECK-LABEL: unsigned_sat_lower_upper_2:
+; V6: usat    r0, #23, r0
+; V6T2: usat    r0, #23, r0
+; V4T-NOT: usat
+entry:
+  %cmpLow = icmp sgt i32 %x, 0
+  %cmpUp = icmp sgt i32 %x, 8388607
+  %saturateUp = select i1 %cmpUp, i32 8388607, i32 %x
+  %saturateLow = select i1 %cmpLow, i32 %saturateUp, i32 0
+  ret i32 %saturateLow
+}
+
+; x < k ? (x < 0 ? 0 : x) : k
+define i32 @unsigned_sat_upper_lower_1(i32 %x) #0 {
+; CHECK-LABEL: unsigned_sat_upper_lower_1:
+; V6: usat    r0, #23, r0
+; V6T2: usat    r0, #23, r0
+; V4T-NOT: usat
+entry:
+  %cmpUp = icmp slt i32 %x, 8388607
+  %cmpLow = icmp slt i32 %x, 0
+  %saturateLow = select i1 %cmpLow, i32 0, i32 %x
+  %saturateUp = select i1 %cmpUp, i32 %saturateLow, i32 8388607
+  ret i32 %saturateUp
+}
+
+; x > k ? k : (x < 0 ? 0 : x)
+define i32 @unsigned_sat_upper_lower_2(i32 %x) #0 {
+; CHECK-LABEL: unsigned_sat_upper_lower_2:
+; V6: usat    r0, #23, r0
+; V6T2: usat    r0, #23, r0
+; V4T-NOT: usat
+entry:
+  %cmpUp = icmp sgt i32 %x, 8388607
+  %cmpLow = icmp slt i32 %x, 0
+  %saturateLow = select i1 %cmpLow, i32 0, i32 %x
+  %saturateUp = select i1 %cmpUp, i32 8388607, i32 %saturateLow
+  ret i32 %saturateUp
+}
+
+; k < x ? k : (x > 0 ? x : 0)
+define i32 @unsigned_sat_upper_lower_3(i32 %x) #0 {
+; CHECK-LABEL: unsigned_sat_upper_lower_3:
+; V6: usat    r0, #23, r0
+; V6T2: usat    r0, #23, r0
+; V4T-NOT: usat
+entry:
+  %cmpUp = icmp slt i32 8388607, %x
+  %cmpLow = icmp sgt i32 %x, 0
+  %saturateLow = select i1 %cmpLow, i32 %x, i32 0
+  %saturateUp = select i1 %cmpUp, i32 8388607, i32 %saturateLow
+  ret i32 %saturateUp
+}
+
+;
+; The following tests check for patterns that should not transform
+; into USAT but are similar enough that could confuse the selector.
+;
+; x > k ? k : (x > 0 ? 0 : x)
+; First condition upper-saturates, second doesn't lower-saturate.
+define i32 @no_unsigned_sat_missing_lower(i32 %x) #0 {
+; CHECK-LABEL: no_unsigned_sat_missing_lower
+; CHECK-NOT: usat
+entry:
+  %cmpUp = icmp sgt i32 %x, 8388607
+  %cmpLow = icmp sgt i32 %x, 0
+  %saturateLow = select i1 %cmpLow, i32 0, i32 %x
+  %saturateUp = select i1 %cmpUp, i32 8388607, i32 %saturateLow
+  ret i32 %saturateUp
+}
+
+; x < k ? k : (x < 0 ? 0 : x)
+; Second condition lower-saturates, first doesn't upper-saturate.
+define i32 @no_unsigned_sat_missing_upper(i32 %x) #0 {
+; CHECK-LABEL: no_unsigned_sat_missing_upper:
+; CHECK-NOT: usat
+entry:
+  %cmpUp = icmp slt i32 %x, 8388607
+  %cmpLow = icmp slt i32 %x, 0
+  %saturateLow = select i1 %cmpLow, i32 0, i32 %x
+  %saturateUp = select i1 %cmpUp, i32 8388607, i32 %saturateLow
+  ret i32 %saturateUp
+}
+
+; Lower constant is different in the select and in the compare
+define i32 @no_unsigned_sat_incorrect_constant(i32 %x) #0 {
+; CHECK-LABEL: no_unsigned_sat_incorrect_constant:
+; CHECK-NOT: usat
+entry:
+  %cmpUp = icmp sgt i32 %x, 8388607
+  %cmpLow = icmp slt i32 %x, 0
+  %saturateLow = select i1 %cmpLow, i32 -1, i32 %x
+  %saturateUp = select i1 %cmpUp, i32 8388607, i32 %saturateLow
+  ret i32 %saturateUp
+}
+
+; The interval is not [0, k]
+define i32 @no_unsigned_sat_incorrect_interval(i32 %x) #0 {
+; CHECK-LABEL: no_unsigned_sat_incorrect_interval:
+; CHECK-NOT: usat
+entry:
+  %cmpUp = icmp sgt i32 %x, 8388607
+  %cmpLow = icmp slt i32 %x, -4
+  %saturateLow = select i1 %cmpLow, i32 -4, i32 %x
+  %saturateUp = select i1 %cmpUp, i32 8388607, i32 %saturateLow
+  ret i32 %saturateUp
+}
+
+; The returned value (y) is not the same as the tested value (x).
+define i32 @no_unsigned_sat_incorrect_return(i32 %x, i32 %y) #0 {
+; CHECK-LABEL: no_unsigned_sat_incorrect_return:
+; CHECK-NOT: usat
+entry:
+  %cmpUp = icmp sgt i32 %x, 8388607
+  %cmpLow = icmp slt i32 %x, 0
+  %saturateLow = select i1 %cmpLow, i32 0, i32 %y
+  %saturateUp = select i1 %cmpUp, i32 8388607, i32 %saturateLow
+  ret i32 %saturateUp
+}
+
+; One of the values in a compare (y) is not the same as the rest
+; of the compare and select values (x).
+define i32 @no_unsigned_sat_incorrect_compare(i32 %x, i32 %y) #0 {
+; CHECK-LABEL: no_unsigned_sat_incorrect_compare:
+; CHECK-NOT: usat
+entry:
+  %cmpUp = icmp sgt i32 %x, 8388607
+  %cmpLow = icmp slt i32 %y, 0
+  %saturateLow = select i1 %cmpLow, i32 0, i32 %x
+  %saturateUp = select i1 %cmpUp, i32 8388607, i32 %saturateLow
+  ret i32 %saturateUp
+}