[ARM] Lower lower saturate to 0 and lower saturate to -1 using bit-operations

[thebolt]

Summary

Expressions of the form x < 0 ? 0 : x; and x < -1 ? -1 : x can be lowered using bit-operations instead of branching or conditional moves

In thumb-mode this results in a two-instruction sequence, a shift followed by a bic or or while in ARM/thumb2 mode that has flexible second operand the shift can be folded into a single bic/or instructions. In most cases this results in smaller code and possibly less branches, and in no case larger than before.

[pbarrio]

The logic & testing LGTM. Just a couple of coding standard nits.

lib/Target/ARM/ARMISelLowering.cpp

4386 ↗

(On Diff #131572)

Variable names should start with uppercase (see https://llvm.org/docs/CodingStandards.html, "Name Types, Functions, Variables, and Enumerators Properly")

4388 ↗

(On Diff #131572)

Same here: upper case + camel case, i.e. NotShiftV

[thebolt]

Updated variable names to conform with coding style as per comments

[rogfer01]

lib/Target/ARM/ARMISelLowering.cpp

4387 ↗

(On Diff #131746)

Given that you don't use the value of KVal itself except to check if it is 0 or -1, you can simplify this to isNullConstant(*K) and isAllOnesConstant(*K).

test/CodeGen/ARM/atomic-op.ll

132 ↗

(On Diff #131746)

If you don't want a cmp now you may want to consider adding a CHECK-NOT: cmp

[thebolt]

Incorporated changes based on comment from Roger Ferrer regarding unnecessary KVal variable.

Added some more negative tests to make sure no comparisons are generated when not expected.

[pbarrio]

LGTM now. In other circumstances, I would wait for someone more experienced than me, but this is a small peephole optimization. I've also tested the patch and it works correctly, so I think it has very little risk.

[thebolt]

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

[pbarrio]

I'll do it.

[pbarrio]

Committed now. Thanks for the patch @thebolt!

[eugenis]

I've reverted your commit in r323929.
It miscompiles the following program on armv7-linux-android:
#include <stdio.h>

typedef unsigned long long u64;
typedef signed long long s64;
s64 f(u64 x) {

return (x > (u64)0x7fffffffffffffffULL) ? (s64)1 : -(s64)x;

}

int main() {

volatile u64 x = 42;
s64 y = f(x);
printf("%lld\n", y);

}

Without this patch, the output is -42.
With your patch, the output is 4294967254.

It also breaks the android bot:

http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-android/builds/7279

[efriedma]

llvm/trunk/lib/Target/ARM/ARMISelLowering.cpp

4483

The use of the constant "31" here is a bit suspicious, given you don't check the type of "VT".

4485

getAllOnesConstant?

[pbarrio]

Sorry, I missed the sanitizer failure in yesterday's buildbot message and thought it wasn't related to this patch. I will leave some time for @thebolt to fix it, otherwise maybe I can take a look.

Thanks for the revert.

[thebolt]

I'm looking into it right now.

I found one direct error (which caused the armv7-linux-android misscompile) and also "pessimised" it a bit to only do the optimization on i32 variables. This still covers the majority of cases as clang for 16/8 bit variables creates signextend->select->truncate sequences, but avoids a few corner cases.

Will try to post a new patch during the day, but I don't know how to runtime test it or do any more testing than "ninja check" (I runtime-test it on our Cortex-M4 ARM based boards).

[yroux]

I can test it in the same condition as our buildbots if you want... will take a bit of time though

[thebolt]

This update hopefully solves the issues found by @eugenis

It adds a missing check for correctly formed expression, and limits the optimization to 32-bit values (which in practice is a majority of the cases you want to cover). Factored out the code that checks for the expression, in similar way to already existing isSaturatingExpression.

@yroux Can you please test and see that this indeed solves all the problems?

[yroux]

@thebolt validation is on-going

[yroux]

stage2 build is not completed yet, but there is no more issue in tblgen with this patch.

LGTM (just two small typos)

[yroux]

lib/Target/ARM/ARMISelLowering.cpp

4393 ↗

(On Diff #132542)

typo: that's up to the caller

4458 ↗

(On Diff #132542)

I'd say: "which have flexible..."

[thebolt]

I have corrected the typos in my code, I will however await further functional testing before submitting a new (hopefully final) version

[thebolt]

@yroux did the entire build and verification pass? If so I will tomorrow (when I have my work computer) upload a new version of the diff with the comment fixes, and then hope it can be approved/commited without breaking anything this time.

[yroux]

@thebolt yes 2 stage build and regression testsuite passed on armv7 builder, thanks for the fix.

[thebolt]

Updated with fixes for the misspelled comments.
Also added two test-cases to catch invalid transformations (such as the ones causing problems earlier).

[thebolt]

Ping? As this revision now has been tested to not break in the same way the first (accepted) version did, could someone please re-review? If the current subscribers are not right, who should I add as reviewer?

[rogfer01]

lib/Target/ARM/ARMISelLowering.cpp

4402–4404 ↗

(On Diff #133185)

For consistency with the rest of the file I think you want to remove the braces here.

4417 ↗

(On Diff #133185)

Ditto.

4427 ↗

(On Diff #133185)

Ditto

4463 ↗

(On Diff #133185)

I'm not convinced of the implicit dependency between the function returning false when Op.getValueType() != MVT::i32 and the 32 bit constant created here.

I wonder if it would be better (just suggesting! I'm happy to be convinced otherwise :)) if you want to do the check here (instead of inside the function).

if (VT == MVT::i32 && isLowerSaturatingConditional(Op, SatValue, LowerSatConstant)) {

This way the dependency of types is more obvious. Perhaps you foresee that we will call isLowerSaturatingConditional in other places and then the we would have to repeat the check?

4468 ↗

(On Diff #133185)

Braces.

[thebolt]

lib/Target/ARM/ARMISelLowering.cpp

4463 ↗

(On Diff #133185)

I buy your argument. Technically there is not any 32-bit constant created (the constant will as far as I can tell have same width as VT) however the transformation from select_cc->bitoperation is only done on 32-bit operations.
I have moved out the condition check on the type as you suggested (and removed it from the function that checks if it is a lower saturate, making it more general)

[thebolt]

Updated coding style as per feedback from @rogfer01

[rogfer01]

Thanks a lot Marten.

This looks good to me now.

[thebolt]

As before, I don't have any commit access so would appreciate if someone else picks it up.

[pbarrio]

If nobody does it before, I'll give it a try early next week.

[pbarrio]

lib/Target/ARM/ARMISelLowering.cpp

4398 ↗

(On Diff #134875)

VT is not used anywhere. I will remove it before committing.

[pbarrio]

Buildbot failing here: http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-bootstrap-msan/builds/2998

The errors don't look related:

FAIL: lld :: ELF/linkerscript/eh-frame-reloc-out-of-range.test (673 of 1549)
FAIL: lld :: ELF/strip-all.s (1509 of 1533)

But I haven't investigated in depth. @thebolt you may want to take a look at it.

llvm/trunk/lib/Target/ARM/ARMISelLowering.cpp

if (((Val1 > Val2 && UpperCheckOp == &Op) ||
     K = (uint64_t)PosVal; // At this point, PosVal is guaranteed to be positive
 
     return true;
   }
 
   return false;
 }
 
+// Check if a condition of the type x < k ? k : x can be converted into a
+// bit operation instead of conditional moves.
+// Currently this is allowed given:
+// - The conditions and values match up
+// - k is 0 or -1 (all ones)
+// This function will not check the last condition, thats up to the caller
+// It returns true if the transformation can be made, and in such case
+// returns x in V, and k in SatK.
+static bool isLowerSaturatingConditional(const SDValue &Op, SDValue &V,
+                                         SDValue &SatK)
+{
+  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);
+
+  SDValue *K = isa<ConstantSDNode>(LHS) ? &LHS : isa<ConstantSDNode>(RHS)
+                                               ? &RHS
+                                               : nullptr;
+
+  // No constant operation in comparison, early out
+  if (!K)
+    return false;
+
+  SDValue KTmp = isa<ConstantSDNode>(TrueVal) ? TrueVal : FalseVal;
+  V = (KTmp == TrueVal) ? FalseVal : TrueVal;
+  SDValue VTmp = (K && *K == LHS) ? RHS : LHS;
+
+  // If the constant on left and right side, or variable on left and right,
+  // does not match, early out
+  if (*K != KTmp || V != VTmp)
+    return false;
+
+  if (isLowerSaturate(LHS, RHS, TrueVal, FalseVal, CC, *K)) {
+    SatK = *K;
+    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, 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));
   }
 
+  // Try to convert expressions of the form x < k ? k : x (and similar forms)
+  // into more efficient bit operations, which is possible when k is 0 or -1
+  // On ARM and Thumb-2 which have flexible operand 2 this will result in
+  // single instructions. On Thumb the shift and the bit operation will be two
+  // instructions.
+  // Only allow this transformation on full-width (32-bit) operations
+  SDValue LowerSatConstant;
+  if (VT == MVT::i32 &&
+      isLowerSaturatingConditional(Op, SatValue, LowerSatConstant)) {
+    SDValue ShiftV = DAG.getNode(ISD::SRA, dl, VT, SatValue,
+                                 DAG.getConstant(31, dl, VT));
+    if (isNullConstant(LowerSatConstant)) {
+      SDValue NotShiftV = DAG.getNode(ISD::XOR, dl, VT, ShiftV,
+                                      DAG.getAllOnesConstant(dl, VT));
+      return DAG.getNode(ISD::AND, dl, VT, SatValue, NotShiftV);
+    } else if (isAllOnesConstant(LowerSatConstant))
+      return DAG.getNode(ISD::OR, dl, VT, SatValue, ShiftV);
+  }
+
   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) {
     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
     // sometimes need to swap the operands to the VSEL (which inverts the

llvm/trunk/test/CodeGen/ARM/atomic-op.ll

entry:
   ; CHECK-T1: bl ___sync_fetch_and_max_4
   ; CHECK-T1-M0: bl ___sync_fetch_and_max_4
   ; CHECK-BAREMETAL: cmp
   ; CHECK-BAREMETAL-NOT: __sync
   %9 = atomicrmw max i32* %val2, i32 1 monotonic
   store i32 %9, i32* %old
   call void asm sideeffect "", "~{memory},~{dirflag},~{fpsr},~{flags}"()
   ; CHECK: ldrex
-  ; CHECK: cmp
+  ; CHECK: bic
+  ; CHECK-NOT: cmp
   ; CHECK: strex
   ; CHECK-T1: bl ___sync_fetch_and_max_4
   ; CHECK-T1-M0: bl ___sync_fetch_and_max_4
-  ; CHECK-BAREMETAL: cmp
+  ; CHECK-BAREMETAL: bic
   ; CHECK-BAREMETAL-NOT: __sync
   %10 = atomicrmw max i32* %val2, i32 0 monotonic
   store i32 %10, i32* %old
   call void asm sideeffect "", "~{memory},~{dirflag},~{fpsr},~{flags}"()
   ; CHECK: ldrex
   ; CHECK: cmp
   ; CHECK: strex
   ; CHECK-T1: bl ___sync_fetch_and_umin_4

llvm/trunk/test/CodeGen/ARM/sat-to-bitop.ll

+; RUN: llc -mtriple=arm %s -o - | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-ARM --check-prefix=CHECK-CMP
+; RUN: llc -mtriple=thumb-eabi %s -o - | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-T --check-prefix=CHECK-CMP
+; RUN: llc -mtriple=thumb-eabi -mcpu=arm1156t2-s -mattr=+thumb2 %s -o - | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-T2 --check-prefix=CHECK-CMP
+
+
+; Check for clipping against 0 that should result in bic
+;
+; Base tests with different bit widths
+;
+
+; x < 0 ? 0 : x
+; 32-bit base test
+define i32 @sat0_base_32bit(i32 %x) #0 {
+; CHECK-LABEL: sat0_base_32bit:
+; CHECK-CMP-NOT: cmp
+; CHECK-ARM: bic {{r[0-9]}}, [[INPUT:r[0-9]]], [[INPUT]], asr #31
+; CHECK-T2: bic.w {{r[0-9]}}, [[INPUT:r[0-9]]], [[INPUT]], asr #31
+; CHECK-T: asrs [[IM:r[0-9]]], {{r[0-9]}}, #31
+; CHECK-T-NEXT: bics {{r[0-9]}}, [[IM]]
+entry:
+  %cmpLow = icmp slt i32 %x, 0
+  %saturateLow = select i1 %cmpLow, i32 0, i32 %x
+  ret i32 %saturateLow
+}
+
+; x < 0 ? 0 : x
+; 16-bit base test
+define i16 @sat0_base_16bit(i16 %x) #0 {
+; CHECK-LABEL: sat0_base_16bit:
+; CHECK-CMP: cmp
+; CHECK-ARM-NOT: bic
+; CHECK-T2-NOT: bic.w
+; CHECK-T-NOT: bics
+entry:
+  %cmpLow = icmp slt i16 %x, 0
+  %saturateLow = select i1 %cmpLow, i16 0, i16 %x
+  ret i16 %saturateLow
+}
+
+; x < 0 ? 0 : x
+; 8-bit base test
+define i8 @sat0_base_8bit(i8 %x) #0 {
+; CHECK-LABEL: sat0_base_8bit:
+; CHECK-CMP: cmp
+; CHECK-ARM-NOT: bic
+; CHECK-T2-NOT: bic.w
+entry:
+  %cmpLow = icmp slt i8 %x, 0
+  %saturateLow = select i1 %cmpLow, i8 0, i8 %x
+  ret i8 %saturateLow
+}
+
+; Test where the conditional is formed in a different way
+
+; x > 0 ? x : 0
+define i32 @sat0_lower_1(i32 %x) #0 {
+; CHECK-LABEL: sat0_lower_1:
+; CHECK-CMP-NOT: cmp
+; CHECK-ARM: bic {{r[0-9]}}, [[INPUT:r[0-9]]], [[INPUT]], asr #31
+; CHECK-T2: bic.w {{r[0-9]}}, [[INPUT:r[0-9]]], [[INPUT]], asr #31
+; CHECK-T: asrs [[IM:r[0-9]]], {{r[0-9]}}, #31
+; CHECK-T-NEXT: bics {{r[0-9]}}, [[IM]]
+entry:
+  %cmpGt = icmp sgt i32 %x, 0
+  %saturateLow = select i1 %cmpGt, i32 %x, i32 0
+  ret i32 %saturateLow
+}
+
+
+; Check for clipping against -1 that should result in orr
+;
+; Base tests with different bit widths
+;
+
+; x < -1 ? -1 : x
+; 32-bit base test
+define i32 @sat1_base_32bit(i32 %x) #0 {
+; CHECK-LABEL: sat1_base_32bit:
+; CHECK-CMP-NOT: cmp
+; CHECK-ARM: orr {{r[0-9]}}, [[INPUT:r[0-9]]], [[INPUT]], asr #31
+; CHECK-T2: orr.w {{r[0-9]}}, [[INPUT:r[0-9]]], [[INPUT]], asr #31
+; CHECK-T: asrs [[IM:r[0-9]]], {{r[0-9]}}, #31
+; CHECK-T-NEXT: orrs {{r[0-9]}}, [[IM]]
+entry:
+  %cmpLow = icmp slt i32 %x, -1
+  %saturateLow = select i1 %cmpLow, i32 -1, i32 %x
+  ret i32 %saturateLow
+}
+
+; x < -1 ? -1 : x
+; 16-bit base test
+define i16 @sat1_base_16bit(i16 %x) #0 {
+; CHECK-LABEL: sat1_base_16bit:
+; CHECK-ARM: cmn
+; CHECK-T2: cmp
+; CHECK-T: cmp
+entry:
+  %cmpLow = icmp slt i16 %x, -1
+  %saturateLow = select i1 %cmpLow, i16 -1, i16 %x
+  ret i16 %saturateLow
+}
+
+; x < -1 ? -1 : x
+; 8-bit base test
+define i8 @sat1_base_8bit(i8 %x) #0 {
+; CHECK-LABEL: sat1_base_8bit:
+; CHECK-ARM: cmn
+; CHECK-T2: cmp
+; CHECK-T: cmp
+entry:
+  %cmpLow = icmp slt i8 %x, -1
+  %saturateLow = select i1 %cmpLow, i8 -1, i8 %x
+  ret i8 %saturateLow
+}
+
+; Test where the conditional is formed in a different way
+
+; x > -1 ? x : -1
+define i32 @sat1_lower_1(i32 %x) #0 {
+; CHECK-LABEL: sat1_lower_1:
+; CHECK-ARM: orr {{r[0-9]}}, [[INPUT:r[0-9]]], [[INPUT]], asr #31
+; CHECK-T2: orr.w {{r[0-9]}}, [[INPUT:r[0-9]]], [[INPUT]], asr #31
+; CHECK-T: asrs [[IM:r[0-9]]], {{r[0-9]}}, #31
+; CHECK-T-NEXT: orrs {{r[0-9]}}, [[IM]]
+; CHECK-CMP-NOT: cmp
+entry:
+  %cmpGt = icmp sgt i32 %x, -1
+  %saturateLow = select i1 %cmpGt, i32 %x, i32 -1
+  ret i32 %saturateLow
+}
+
+; The following tests for patterns that should not transform into bitops
+; but that are similar enough that could confuse the selector.
+
+; x < 0 ? 0 : y where x and y does not properly match
+define i32 @no_sat0_incorrect_variable(i32 %x, i32 %y) #0 {
+; CHECK-LABEL: no_sat0_incorrect_variable:
+; CHECK-NOT: bic
+; CHECK-NOT: asrs
+; CHECK-CMP: cmp
+entry:
+  %cmpLow = icmp slt i32 %x, 0
+  %saturateLow = select i1 %cmpLow, i32 0, i32 %y
+  ret i32 %saturateLow
+}
+
+; x < 0 ? -1 : x
+define i32 @no_sat0_incorrect_constant(i32 %x) #0 {
+; CHECK-LABEL: no_sat0_incorrect_constant:
+; CHECK-NOT: bic
+; CHECK-NOT: asrs
+; CHECK-CMP: cmp
+entry:
+  %cmpLow = icmp slt i32 %x, 0
+  %saturateLow = select i1 %cmpLow, i32 -1, i32 %x
+  ret i32 %saturateLow
+}