[ARM] Lower (select_cc k k (select_cc ~k ~k x)) into (SSAT l_k x)

[pbarrio]

Summary

SSAT saturates an integer, making sure that its value lies within
an interval [-k, k]. Since the constant is given to SSAT as the
number of bytes set to one, k + 1 must be a power of 2, otherwise
the optimization is not possible. Also, the select_cc must use <
and > respectively so that they define an interval.

[pbarrio]

Hello mcrosier, jmolloy, rengolin, would you have a few minutes to review this patch?

Thanks

[rengolin]

Sorry it took so long, I was put of by some of the comments and tests and kept getting distracted.

Some comments to start... :)

cheers,
--renato

lib/Target/ARM/ARMISelLowering.cpp

3881

This comment is misleading (and it took me a while to figure out :).

This is not lowering (select o select), but (select o (lower o (select o upper), which is a completely different case. I think the comment above on the possibilities should actually be here.

3939

This is a slightly deeper nesting that we normally like. Can you refactor this into a new function and use early returns?

test/CodeGen/ARM/ssat.ll

13

I'd add the base test for i8 and i16, just to make sure we're getting it right with all the trivially extensible types.

30

cond is a bad name and also gave me some time to think about... Maybe max and min would be better names for those.

It might sound picky to comment on those names, but reading tests is the best way to understand what the intention of the code is, and so act much more as documentation than comment lines or commit messages. :)

200

Try to give more meaningful names of why not. Is the range wrong? Are they not powers of two? Are the conditions reversed? etc. At the very least, add a comment to that effect.

202

The NOT tests are better with just "ssat" not with the #24, since you could still emit another sized SSAT and it will still be wrong.

[pbarrio]

Addressed concerns about refactoring, comments and testing

Renato, thank you for the review. I have refactored the logic into a separate
function and used early returns as suggested. I have also modified the comments
so that they are clearer.

I have extensively cleaned up the tests and added some more. This time, the naming
is much better because it's done by me :) The previous tests were directly taken
from compiling a C file with use cases into IR, hence the cryptic names. Some of the
tests were also redundant because LLVM normalizes some constructs, so different C
code was transformed into the same IR. I have removed these - lesson learned.

I hope you find this version more readable, but let me know if you find room for
improvement. Thanks again!

[pbarrio]

Small fix for one of the tests

[pbarrio]

Same fix for another test.

[rengolin]

Thanks Pablo, it's looking much better!

A few remaining comments...

--renato

lib/Target/ARM/ARMISelLowering.cpp

3786

Minor nit, maybe move this line down like the other above?

3837

Wait, this looks backwards...

Shouldn't the positive value be something like:

std::max(Val1, Val2);

but you seem to be getting the lowest of both sign extended values.

test/CodeGen/ARM/ssat.ll

183

change all CHECK-NOT lines to:

; CHECK-NOT: ssat

as we don't want *an* ssat being generated, no matter how the test changes in the future.

[pbarrio]

lib/Target/ARM/ARMISelLowering.cpp

3837

I'm comparing two unsigned integers, so effectively the "negative" numbers are bigger than the positive ones because the most significant bit is always 1.

I'm doing this because getSExtValue() returns a uint64_t. I could cast Val1 and Val2 to signed and therefore do a signed integer compare. Let me know if you prefer that.

[pbarrio]

lib/Target/ARM/ARMISelLowering.cpp

3837

I will shut up. getSExtValue returns an int64_t so there is no reason to do this the convoluted way. I will change it in the next version.

[rengolin]

lib/Target/ARM/ARMISelLowering.cpp

3837

:D

[pbarrio]

Second round of changes addressed. Thanks!

Also a side-question. Would it be better to use std::max(V1, V2) instead of
V1 > V2 ? V1 : V2? If so, why?

[rengolin]

In D21372#464862, @pbarrio wrote:

Second round of changes addressed. Thanks!

Thanks! Looks good to me now, + using std::max.

Also a side-question. Would it be better to use std::max(V1, V2) instead of
V1 > V2 ? V1 : V2? If so, why?

Yes, because I first assumed it was it, so didn't bothered. It was only when I looked again that it didn't make sense because the condition was reversed but the values were unsigned. While it could potentially work on all cases, it was an obtuse construct, and prone to confusion.

If you had used std::min from the beginning, I'd have caught it early on, while I could have missed it with the ternary.

From a code generation point of view, std::max/min generates the exact same code as the ternary, so there's no reason to not use it.

cheers,
--renato

[pbarrio]

Using std::max() now. Near that, I also made an implicit cast explicit, just for readability.

[rengolin]

LGTM, thanks!

include/llvm/Target/TargetSelectionDAG.td

 def SDTUnaryOp  : SDTypeProfile<1, 1, []>;                   // for bitconvert.
 
 def SDTIntBinOp : SDTypeProfile<1, 2, [     // add, and, or, xor, udiv, etc.
   SDTCisSameAs<0, 1>, SDTCisSameAs<0, 2>, SDTCisInt<0>
 ]>;
 def SDTIntShiftOp : SDTypeProfile<1, 2, [   // shl, sra, srl
   SDTCisSameAs<0, 1>, SDTCisInt<0>, SDTCisInt<2>
 ]>;
+def SDTIntSatNoShOp : SDTypeProfile<1, 2, [   // ssat with no shift
+  SDTCisSameAs<0, 1>, SDTCisInt<2>
+]>;
 def SDTIntBinHiLoOp : SDTypeProfile<2, 2, [ // mulhi, mullo, sdivrem, udivrem
   SDTCisSameAs<0, 1>, SDTCisSameAs<0, 2>, SDTCisSameAs<0, 3>,SDTCisInt<0>
 ]>;
 
 def SDTFPBinOp : SDTypeProfile<1, 2, [      // fadd, fmul, etc.
   SDTCisSameAs<0, 1>, SDTCisSameAs<0, 2>, SDTCisFP<0>
 ]>;
 def SDTFPSignOp : SDTypeProfile<1, 2, [     // fcopysign.

lib/Target/ARM/ARMISelLowering.h

enum NodeType : unsigned {
       CMN,          // ARM CMN instructions.
       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
+
       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
       ADDE,         // Add using carry

lib/Target/ARM/ARMISelLowering.cpp

const char *ARMTargetLowering::getTargetNodeName(unsigned Opcode) const {
   case ARMISD::CMPZ:          return "ARMISD::CMPZ";
   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::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";
   case ARMISD::SUBE:          return "ARMISD::SUBE";
if (Subtarget->isFPOnlySP() && VT == MVT::f64) {
 
     return DAG.getNode(ARMISD::VMOVDRR, dl, MVT::f64, Low, High);
   } else {
     return DAG.getNode(ARMISD::CMOV, dl, VT, FalseVal, TrueVal, ARMcc, CCR,
                        Cmp);
   }
 }
 
+bool isGTorGE(ISD::CondCode CC) { return CC == ISD::SETGT || CC == ISD::SETGE; }
+
+bool isLTorLE(ISD::CondCode CC) { return CC == ISD::SETLT || CC == ISD::SETLE; }
+
+// See if a conditional (LHS CC RHS ? TrueVal : FalseVal) is lower-saturating.
+// All of these conditions (and their <= and >= counterparts) will do:
+//          x < k ? k : x
+//          x > k ? x : k
+//          k < x ? x : k
+//          k > x ? k : x
+bool isLowerSaturate(const SDValue LHS, const SDValue RHS,
+                     const SDValue TrueVal, const SDValue FalseVal,
+                     const ISD::CondCode CC, const SDValue K) {
+  return (isGTorGE(CC) &&
+          ((K == LHS && K == TrueVal) || (K == RHS && K == FalseVal))) ||
+         (isLTorLE(CC) &&
+          ((K == RHS && K == TrueVal) || (K == LHS && K == FalseVal)));
+}
+
+// Similar to isLowerSaturate(), but checks for upper-saturating conditions.
+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.
+//
+// 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.
+//
+// It returns true if the conversion can be done, false otherwise.
+// Additionally, the variable is returned in parameter V and the constant in K.
+bool isSaturatingConditional(const SDValue &Op, SDValue &V, uint64_t &K) {
+
+  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)
+    return false;
+
+  SDValue LHS2 = Op2.getOperand(0);
+  SDValue RHS2 = Op2.getOperand(1);
+  ISD::CondCode CC2 = cast<CondCodeSDNode>(Op2.getOperand(4))->get();
+  SDValue TrueVal2 = Op2.getOperand(2);
+  SDValue FalseVal2 = Op2.getOperand(3);
+
+  // Find out which are the constants and which are the variables
+  // in each conditional
+  SDValue *K1 = isa<ConstantSDNode>(LHS1) ? &LHS1 : isa<ConstantSDNode>(RHS1)
+                                                        ? &RHS1
+                                                        : NULL;
+  SDValue *K2 = isa<ConstantSDNode>(LHS2) ? &LHS2 : isa<ConstantSDNode>(RHS2)
+                                                        ? &RHS2
+                                                        : NULL;
+  SDValue K2Tmp = isa<ConstantSDNode>(TrueVal2) ? TrueVal2 : FalseVal2;
+  SDValue V1Tmp = (K1 && *K1 == LHS1) ? RHS1 : LHS1;
+  SDValue V2Tmp = (K2 && *K2 == LHS2) ? RHS2 : LHS2;
+  SDValue V2 = (K2Tmp == TrueVal2) ? FalseVal2 : TrueVal2;
+
+  // We must detect cases where the original operations worked with 16- or
+  // 8-bit values. In such case, V2Tmp != V2 because the comparison operations
+  // must work with sign-extended values but the select operations return
+  // the original non-extended value.
+  SDValue V2TmpReg = V2Tmp;
+  if (V2Tmp->getOpcode() == ISD::SIGN_EXTEND_INREG)
+    V2TmpReg = V2Tmp->getOperand(0);
+
+  // Check that the registers and the constants have the correct values
+  // in both conditionals
+  if (!K1 || !K2 || *K1 == Op2 || *K2 != K2Tmp || V1Tmp != V2Tmp ||
+      V2TmpReg != V2)
+    return false;
+
+  // Figure out which conditional is saturating the lower/upper bound.
+  const SDValue *LowerCheckOp =
+      isLowerSaturate(LHS1, RHS1, TrueVal1, FalseVal1, CC1, *K1)
+          ? &Op
+          : isLowerSaturate(LHS2, RHS2, TrueVal2, FalseVal2, CC2, *K2) ? &Op2
+                                                                       : NULL;
+  const SDValue *UpperCheckOp =
+      isUpperSaturate(LHS1, RHS1, TrueVal1, FalseVal1, CC1, *K1)
+          ? &Op
+          : isUpperSaturate(LHS2, RHS2, TrueVal2, FalseVal2, CC2, *K2) ? &Op2
+                                                                       : NULL;
+
+  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.
+  uint64_t Val1 = cast<ConstantSDNode>(*K1)->getSExtValue();
+  uint64_t Val2 = cast<ConstantSDNode>(*K2)->getSExtValue();
+  uint64_t PosVal = Val1 < Val2 ? Val1 : Val2;
+
+  if (((Val1 < Val2 && UpperCheckOp == &Op) ||
+       (Val1 > Val2 && (UpperCheckOp == &Op2))) &&
+      Val1 == ~Val2 && isPowerOf2_64(PosVal + 1)) {
+
+    V = V2;
+    K = PosVal;
+    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;
+  if (isSaturatingConditional(Op, SatValue, SatConstant))
+    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);
-  SDLoc dl(Op);
 
   if (Subtarget->isFPOnlySP() && LHS.getValueType() == MVT::f64) {
     DAG.getTargetLoweringInfo().softenSetCCOperands(DAG, MVT::f64, LHS, RHS, CC,
                                                     dl);
 
     // If softenSetCCOperands only returned one value, we should compare it to
     // zero.
     if (!RHS.getNode()) {
       RHS = DAG.getConstant(0, dl, LHS.getValueType());
       CC = ISD::SETNE;
     }
   }
 
   if (LHS.getValueType() == MVT::i32) {
     // Try to generate VSEL on ARMv8.
     // The VSEL instruction can't use all the usual ARM condition
     // codes: it only has two bits to select the condition code, so it's
     // constrained to use only GE, GT, VS and EQ.
     //
     // To implement all the various ISD::SETXXX opcodes, we sometimes need to
     // swap the operands of the previous compare instruction (effectively
     // inverting the compare condition, swapping 'less' and 'greater') and
SDValue ARMTargetLowering::LowerSELECT_CC(SDValue Op, SelectionDAG &DAG) const {
   if (CondCode2 != ARMCC::AL) {
     SDValue ARMcc2 = DAG.getConstant(CondCode2, dl, MVT::i32);
     // FIXME: Needs another CMP because flag can have but one use.
     SDValue Cmp2 = getVFPCmp(LHS, RHS, DAG, dl);
     Result = getCMOV(dl, VT, Result, TrueVal, ARMcc2, CCR, Cmp2, DAG);
   }
   return Result;
 }
 
 /// canChangeToInt - Given the fp compare operand, return true if it is suitable
 /// to morph to an integer compare sequence.
 static bool canChangeToInt(SDValue Op, bool &SeenZero,
                            const ARMSubtarget *Subtarget) {
   SDNode *N = Op.getNode();
   if (!N->hasOneUse())
     // Otherwise it requires moving the value from fp to integer registers.
     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 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 USAT16 : AI<(outs GPRnopc:$Rd),
   let Inst{19-16} = sat_imm;
   let Inst{3-0} = Rn;
 }
 
 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)>;
 
 //===----------------------------------------------------------------------===//
 //  Bitwise Instructions.
 //
 
 defm AND   : AsI1_bin_irs<0b0000, "and",
                           IIC_iBITi, IIC_iBITr, IIC_iBITsr, and, 1>;
 defm ORR   : AsI1_bin_irs<0b1100, "orr",

lib/Target/ARM/ARMInstrThumb2.td

def t2USAT16: T2SatI<(outs rGPR:$Rd), (ins imm0_15:$sat_imm, rGPR:$Rn),
   let Inst{21} = 1;        // sh = '1'
   let Inst{14-12} = 0b000; // imm3 = '000'
   let Inst{7-6} = 0b00;    // imm2 = '00'
   let Inst{5-4} = 0b00;
 }
 
 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<(ARMssatnoshift GPRnopc:$Rn, imm0_31:$imm),
+             (t2SSAT imm0_31:$imm, GPRnopc:$Rn, 0)>;
 
 //===----------------------------------------------------------------------===//
 //  Shift and rotate Instructions.
 //
 
 defm t2LSL  : T2I_sh_ir<0b00, "lsl", imm0_31, shl>;
 defm t2LSR  : T2I_sh_ir<0b01, "lsr", imm_sr,  srl>;
 defm t2ASR  : T2I_sh_ir<0b10, "asr", imm_sr,  sra>;

test/CodeGen/ARM/ssat.ll

+; RUN: llc -mtriple=arm-eabi %s -o - | FileCheck %s
+
+; Check for several conditions that should result in SSAT.
+; For example, the base test is equivalent to
+; x < -k ? -k : (x > k ? k : x) in C. All patterns that bound x
+; to the interval [-k, k] where k is a power of 2 can be
+; transformed into SSAT. 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 < -k ? -k : (x > k ? k : x)
+; 32-bit base test
+define i32 @sat_base_32bit(i32 %x) #0 {
+; CHECK-LABEL: sat_base_32bit:
+; CHECK: ssat r0, #24, r0
+entry:
+  %cmpLow = icmp slt i32 %x, -8388608
+  %cmpUp = icmp sgt i32 %x, 8388607
+  %saturateUp = select i1 %cmpUp, i32 8388607, i32 %x
+  %saturateLow = select i1 %cmpLow, i32 -8388608, i32 %saturateUp
+  ret i32 %saturateLow
+}
+
+; x < -k ? -k : (x > k ? k : x)
+; 16-bit base test
+define i16 @sat_base_16bit(i16 %x) #0 {
+; CHECK-LABEL: sat_base_16bit:
+; CHECK: ssat r0, #12, r0
+entry:
+  %cmpLow = icmp slt i16 %x, -2048
+  %cmpUp = icmp sgt i16 %x, 2047
+  %saturateUp = select i1 %cmpUp, i16 2047, i16 %x
+  %saturateLow = select i1 %cmpLow, i16 -2048, i16 %saturateUp
+  ret i16 %saturateLow
+}
+
+; x < -k ? -k : (x > k ? k : x)
+; 8-bit base test
+define i8 @sat_base_8bit(i8 %x) #0 {
+; CHECK-LABEL: sat_base_8bit:
+; CHECK: ssat r0, #6, r0
+entry:
+  %cmpLow = icmp slt i8 %x, -32
+  %cmpUp = icmp sgt i8 %x, 31
+  %saturateUp = select i1 %cmpUp, i8 31, i8 %x
+  %saturateLow = select i1 %cmpLow, i8 -32, 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 SSAT are tested.
+;
+
+; x < -k ? -k : (x < k ? x : k)
+define i32 @sat_lower_upper_1(i32 %x) #0 {
+; CHECK-LABEL: sat_lower_upper_1:
+; CHECK: ssat r0, #24, r0
+entry:
+  %cmpLow = icmp slt i32 %x, -8388608
+  %cmpUp = icmp slt i32 %x, 8388607
+  %saturateUp = select i1 %cmpUp, i32 %x, i32 8388607
+  %saturateLow = select i1 %cmpLow, i32 -8388608, i32 %saturateUp
+  ret i32 %saturateLow
+}
+
+; x > -k ? (x > k ? k : x) : -k
+define i32 @sat_lower_upper_2(i32 %x) #0 {
+; CHECK-LABEL: sat_lower_upper_2:
+; CHECK: ssat    r0, #24, r0
+entry:
+  %cmpLow = icmp sgt i32 %x, -8388608
+  %cmpUp = icmp sgt i32 %x, 8388607
+  %saturateUp = select i1 %cmpUp, i32 8388607, i32 %x
+  %saturateLow = select i1 %cmpLow, i32 %saturateUp, i32 -8388608
+  ret i32 %saturateLow
+}
+
+; x < k ? (x < -k ? -k : x) : k
+define i32 @sat_upper_lower_1(i32 %x) #0 {
+; CHECK-LABEL: sat_upper_lower_1:
+; CHECK: ssat    r0, #24, r0
+entry:
+  %cmpUp = icmp slt i32 %x, 8388607
+  %cmpLow = icmp slt i32 %x, -8388608
+  %saturateLow = select i1 %cmpLow, i32 -8388608, i32 %x
+  %saturateUp = select i1 %cmpUp, i32 %saturateLow, i32 8388607
+  ret i32 %saturateUp
+}
+
+; x > k ? k : (x < -k ? -k : x)
+define i32 @sat_upper_lower_2(i32 %x) #0 {
+; CHECK-LABEL: sat_upper_lower_2:
+; CHECK: ssat    r0, #24, r0
+entry:
+  %cmpUp = icmp sgt i32 %x, 8388607
+  %cmpLow = icmp slt i32 %x, -8388608
+  %saturateLow = select i1 %cmpLow, i32 -8388608, i32 %x
+  %saturateUp = select i1 %cmpUp, i32 8388607, i32 %saturateLow
+  ret i32 %saturateUp
+}
+
+; k < x ? k : (x > -k ? x : -k)
+define i32 @sat_upper_lower_3(i32 %x) #0 {
+; CHECK-LABEL: sat_upper_lower_3:
+; CHECK: ssat    r0, #24, r0
+entry:
+  %cmpUp = icmp slt i32 8388607, %x
+  %cmpLow = icmp sgt i32 %x, -8388608
+  %saturateLow = select i1 %cmpLow, i32 %x, i32 -8388608
+  %saturateUp = select i1 %cmpUp, i32 8388607, i32 %saturateLow
+  ret i32 %saturateUp
+}
+
+;
+; Miscellanea
+;
+
+; Check that >= and <= work the same as > and <
+; k <= x ? k : (x >= -k ? x : -k)
+define i32 @sat_le_ge(i32 %x) #0 {
+; CHECK-LABEL: sat_le_ge:
+; CHECK: ssat    r0, #24, r0
+entry:
+  %cmpUp = icmp sle i32 8388607, %x
+  %cmpLow = icmp sge i32 %x, -8388608
+  %saturateLow = select i1 %cmpLow, i32 %x, i32 -8388608
+  %saturateUp = select i1 %cmpUp, i32 8388607, i32 %saturateLow
+  ret i32 %saturateUp
+}
+
+;
+; The following tests check for patterns that should not transform
+; into SSAT but are similar enough that could confuse the selector.
+;
+
+; x > k ? k : (x > -k ? -k : x)
+; First condition upper-saturates, second doesn't lower-saturate.
+define i32 @no_sat_missing_lower(i32 %x) #0 {
+; CHECK-LABEL: no_sat_missing_lower
+; CHECK-NOT: ssat    r0, #24, r0
+entry:
+  %cmpUp = icmp sgt i32 %x, 8388607
+  %cmpLow = icmp sgt i32 %x, -8388608
+  %saturateLow = select i1 %cmpLow, i32 -8388608, i32 %x
+  %saturateUp = select i1 %cmpUp, i32 8388607, i32 %saturateLow
+  ret i32 %saturateUp
+}
+
+; x < k ? k : (x < -k ? -k : x)
+; Second condition lower-saturates, first doesn't upper-saturate.
+define i32 @no_sat_missing_upper(i32 %x) #0 {
+; CHECK-LABEL: no_sat_missing_upper:
+; CHECK-NOT: ssat    r0, #24, r0
+entry:
+  %cmpUp = icmp slt i32 %x, 8388607
+  %cmpLow = icmp slt i32 %x, -8388608
+  %saturateLow = select i1 %cmpLow, i32 -8388608, 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_sat_incorrect_constant(i32 %x) #0 {
+; CHECK-LABEL: no_sat_incorrect_constant:
+; CHECK-NOT: ssat    r0, #24, r0
+entry:
+  %cmpUp = icmp sgt i32 %x, 8388607
+  %cmpLow = icmp slt i32 %x, -8388608
+  %saturateLow = select i1 %cmpLow, i32 -8388607, i32 %x
+  %saturateUp = select i1 %cmpUp, i32 8388607, i32 %saturateLow
+  ret i32 %saturateUp
+}
+
+; The interval is not [k, ~k]
+define i32 @no_sat_incorrect_interval(i32 %x) #0 {
+; CHECK-LABEL: no_sat_incorrect_interval:
+; CHECK-NOT: ssat    r0, #24, r0
+entry:
+  %cmpUp = icmp sgt i32 %x, 8388607
+  %cmpLow = icmp slt i32 %x, -19088744
+  %saturateLow = select i1 %cmpLow, i32 -19088744, 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_sat_incorrect_return(i32 %x, i32 %y) #0 {
+; CHECK-LABEL: no_sat_incorrect_return:
+; CHECK-NOT: ssat    r0, #24, r0
+entry:
+  %cmpUp = icmp sgt i32 %x, 8388607
+  %cmpLow = icmp slt i32 %x, -8388608
+  %saturateLow = select i1 %cmpLow, i32 -8388608, 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_sat_incorrect_compare(i32 %x, i32 %y) #0 {
+; CHECK-LABEL: no_sat_incorrect_compare:
+; CHECK-NOT: ssat    r0, #24, r0
+entry:
+  %cmpUp = icmp sgt i32 %x, 8388607
+  %cmpLow = icmp slt i32 %y, -8388608
+  %saturateLow = select i1 %cmpLow, i32 -8388608, i32 %x
+  %saturateUp = select i1 %cmpUp, i32 8388607, i32 %saturateLow
+  ret i32 %saturateUp
+}