[X86][MCU] replace select with bit manipulation instead of branches

[AsafBadouh]

Summary

In case of the following select pattern, where :

1. the condition is a result of "x & 0x1"
2. the select operand are (z ^ y) , y or (z | y) , y

we can eliminate the branch (there is no "cmov" in MCU) by generate bitwise sequence.

select (and (x & 0x1) == 0) , y,  (z ^ y) )

to:

(-(and (x & 0x1)) & z ) ^ y

[igorb]

../tunkClang/lib/Target/X86/X86ISelLowering.cpp

16846 ↗

(On Diff #83233)

Could you please add comments.
I think the function name is misleading.

16992 ↗

(On Diff #83233)

what do you mean "(and (x & 0x1)" ?

17043 ↗

(On Diff #83233)

Could you implement isOrXorPattern as lambda function?

[AsafBadouh]

changes according to Igor review.

[igorb]

please recheck the algorithm, it looks like it incorrect.

[AsafBadouh]

Great catch Igor,
the transformation is not valid to select (and (x & 0x1) == 0) , (z ^ y), y ),
for that we will need an extra instruction to create the mask.
I change the algorithm to catch only: select (and (x & 0x1) == 0) , y, (z ^ y) )

llvm/trunk/lib/Target/X86/X86ISelLowering.cpp

if (SDValue NewCond = LowerSETCC(Cond, DAG)) {
       Op2 = Op.getOperand(2);
     }
   }
 
   // (select (x == 0), -1, y) -> (sign_bit (x - 1)) | y
   // (select (x == 0), y, -1) -> ~(sign_bit (x - 1)) | y
   // (select (x != 0), y, -1) -> (sign_bit (x - 1)) | y
   // (select (x != 0), -1, y) -> ~(sign_bit (x - 1)) | y
+  // (select (and (x , 0x1) == 0), y, (z ^ y) ) -> (-(and (x , 0x1)) & z ) ^ y
+  // (select (and (x , 0x1) == 0), y, (z | y) ) -> (-(and (x , 0x1)) & z ) | y
   if (Cond.getOpcode() == X86ISD::SETCC &&
       Cond.getOperand(1).getOpcode() == X86ISD::CMP &&
       isNullConstant(Cond.getOperand(1).getOperand(1))) {
     SDValue Cmp = Cond.getOperand(1);
-
-    unsigned CondCode =cast<ConstantSDNode>(Cond.getOperand(0))->getZExtValue();
+    unsigned CondCode =
+        cast<ConstantSDNode>(Cond.getOperand(0))->getZExtValue();
 
     if ((isAllOnesConstant(Op1) || isAllOnesConstant(Op2)) &&
         (CondCode == X86::COND_E || CondCode == X86::COND_NE)) {
       SDValue Y = isAllOnesConstant(Op2) ? Op1 : Op2;
 
       SDValue CmpOp0 = Cmp.getOperand(0);
       // Apply further optimizations for special cases
       // (select (x != 0), -1, 0) -> neg & sbb
if ((isAllOnesConstant(Op1) || isAllOnesConstant(Op2)) &&
                     DAG.getConstant(X86::COND_B, DL, MVT::i8), Cmp);
 
       if (isAllOnesConstant(Op1) != (CondCode == X86::COND_E))
         Res = DAG.getNOT(DL, Res, Res.getValueType());
 
       if (!isNullConstant(Op2))
         Res = DAG.getNode(ISD::OR, DL, Res.getValueType(), Res, Y);
       return Res;
+    } else if (!Subtarget.hasCMov() && CondCode == X86::COND_E &&
+               Cmp.getOperand(0).getOpcode() == ISD::AND &&
+               isOneConstant(Cmp.getOperand(0).getOperand(1))) {
+      SDValue CmpOp0 = Cmp.getOperand(0);
+      SDValue Src1, Src2;
+      // true if Op2 is XOR or OR operator and one of its operands
+      // is equal to Op1
+      // ( a , a op b) || ( b , a op b)
+      auto isOrXorPattern = [&]() {
+        if ((Op2.getOpcode() == ISD::XOR || Op2.getOpcode() == ISD::OR) &&
+            (Op2.getOperand(0) == Op1 || Op2.getOperand(1) == Op1)) {
+          Src1 =
+              Op2.getOperand(0) == Op1 ? Op2.getOperand(1) : Op2.getOperand(0);
+          Src2 = Op1;
+          return true;
+        }
+        return false;
+      };
+
+      if (isOrXorPattern()) {
+        SDValue Neg;
+        unsigned int CmpSz = CmpOp0.getSimpleValueType().getSizeInBits();
+        // we need mask of all zeros or ones with same size of the other
+        // operands.
+        if (CmpSz > VT.getSizeInBits())
+          Neg = DAG.getNode(ISD::TRUNCATE, DL, VT, CmpOp0);
+        else if (CmpSz < VT.getSizeInBits())
+          Neg = DAG.getNode(ISD::AND, DL, VT,
+              DAG.getNode(ISD::ANY_EXTEND, DL, VT, CmpOp0.getOperand(0)),
+              DAG.getConstant(1, DL, VT));
+        else
+          Neg = Cmp;
+        SDValue Mask = DAG.getNode(ISD::SUB, DL, VT, DAG.getConstant(0, DL, VT),
+                                   Neg); // -(and (x, 0x1))
+        SDValue And = DAG.getNode(ISD::AND, DL, VT, Mask, Src1); // Mask & z
+        return DAG.getNode(Op2.getOpcode(), DL, VT, And, Src2);  // And Op y
+      }
     }
   }
 
   // Look past (and (setcc_carry (cmp ...)), 1).
   if (Cond.getOpcode() == ISD::AND &&
       Cond.getOperand(0).getOpcode() == X86ISD::SETCC_CARRY &&
       isOneConstant(Cond.getOperand(1)))
     Cond = Cond.getOperand(0);

llvm/trunk/test/CodeGen/X86/select.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=x86_64-apple-darwin10 -mcpu=generic | FileCheck %s --check-prefix=CHECK --check-prefix=GENERIC
 ; RUN: llc < %s -mtriple=x86_64-apple-darwin10 -mcpu=atom    | FileCheck %s --check-prefix=CHECK --check-prefix=ATOM
+; RUN: llc < %s -mtriple=i386-intel-elfiamcu                 | FileCheck %s --check-prefix=MCU
 
 ; PR5757
 %0 = type { i64, i32 }
 
 define i32 @test1(%0* %p, %0* %q, i1 %r) nounwind {
 ; CHECK-LABEL: test1:
 ; CHECK:       ## BB#0:
 ; CHECK-NEXT:    addq $8, %rdi
CF242:
   %Sl59 = select i1 %Cmp32, float %FC, float undef
   %Cmp60 = fcmp ugt float undef, undef
   br i1 %Cmp60, label %CF242, label %CF244
 
 CF244:
   %B122 = fadd float %Sl59, undef
   ret void
 }
+
+define i16 @select_xor_1(i16 %A, i8 %cond) {
+; CHECK-LABEL: select_xor_1:
+; MCU:    andl    $1, %edx
+; MCU-NEXT:    negl    %edx
+; MCU-NEXT:    andl    $43, %edx
+; MCU-NEXT:    xorl    %edx, %eax
+entry:
+ %and = and i8 %cond, 1
+ %cmp10 = icmp eq i8 %and, 0
+ %0 = xor i16 %A, 43
+ %1 = select i1 %cmp10, i16 %A, i16 %0
+ ret i16 %1
+}
+
+define i32 @select_xor_2(i32 %A, i32 %B, i8 %cond) {
+; CHECK-LABEL: select_xor_2:
+; MCU:    andl $1, %ecx
+; MCU-NEXT:    negl %ecx
+; MCU-NEXT:    andl %edx, %ecx
+; MCU-NEXT:    xorl %ecx, %eax
+entry:
+ %and = and i8 %cond, 1
+ %cmp10 = icmp eq i8 %and, 0
+ %0 = xor i32 %B, %A
+ %1 = select i1 %cmp10, i32 %A, i32 %0
+ ret i32 %1
+}
+
+define i32 @select_or(i32 %A, i32 %B, i8 %cond) {
+; CHECK-LABEL: select_or:
+; MCU:    andl $1, %ecx
+; MCU-NEXT:    negl %ecx
+; MCU-NEXT:    andl %edx, %ecx
+; MCU-NEXT:    orl %ecx, %eax
+entry:
+ %and = and i8 %cond, 1
+ %cmp10 = icmp eq i8 %and, 0
+ %0 = or i32 %B, %A
+ %1 = select i1 %cmp10, i32 %A, i32 %0
+ ret i32 %1
+}