[DAGCombiner] Improve shift by select of constant

[laytonio]

Summary

Clean up a TODO, to support folding a shift of a constant by a select of constants, on targets with different shift operand sizes.

[RKSimon]

llvm/test/CodeGen/PowerPC/select_const.ll

630

any ideas on these regressions?

[laytonio]

llvm/test/CodeGen/PowerPC/select_const.ll

630

any ideas on these regressions?

Forgive me, I'm not very familiar with PowerPC, but is this actually worse? It now looks just like the above unaltered test for select of constants shifted by constant. If it is worse, should we change that as well?

[RKSimon]

llvm/test/CodeGen/PowerPC/select_const.ll

630

@nemanjai how much of an issue is this?

[laytonio]

ping

[lebedev.ri]

llvm/test/CodeGen/PowerPC/select_const.ll

630

@nemanjai ping

[RKSimon]

llvm/test/CodeGen/PowerPC/select_const.ll

630

@amyk Any comments?

[steven.zhang]

llvm/test/CodeGen/PowerPC/select_const.ll

630

It looks good to me as before the change, clrlwi, subfic and slw are chained together, while the new one only chain two instructions.(andi. and iselgt) And they didn't have too much latency difference AFAIK. But please correct me if I miss something here.

[lkail]

llvm/test/CodeGen/PowerPC/select_const.ll

630

Agree, my pfm test shows that using isel here is better.

[lebedev.ri]

Looks reasonable to me then.

[RKSimon]

LGTM

[nemanjai]

I am really sorry that I've missed these notifications. The PPC changes are perfectly fine. This might lead to regressions if the shift amount is large enough to require more than a single instruction to produce each constant (i.e. the constant no longer fits in a 16-bit signed immediate). But there's work underway to improve constant materialization in the back end that will alleviate this problem.

So LGTM and sorry about the delay.

[amyk]

I'm really sorry for the delay. LGTM to me, as well.

[laytonio]

Thank you everyone for looking at this! Could one of you please commit this for me? Layton Kifer <[e-mail]>

[steven.zhang]

Done in 385e9a2a047bc0bee13a21a9016763e694a686a3

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

bool CanFoldNonConst =
       (isNullOrNullSplat(CF) || isAllOnesOrAllOnesSplat(CF));
 
   SDValue CBO = BO->getOperand(SelOpNo ^ 1);
   if (!CanFoldNonConst &&
       !isConstantOrConstantVector(CBO, true) &&
       !isConstantFPBuildVectorOrConstantFP(CBO))
     return SDValue();
 
-  EVT VT = Sel.getValueType();
-
-  // In case of shift value and shift amount may have different VT. For instance
-  // on x86 shift amount is i8 regardles of LHS type. Bail out if we have
-  // swapped operands and value types do not match. NB: x86 is fine if operands
-  // are not swapped with shift amount VT being not bigger than shifted value.
-  // TODO: that is possible to check for a shift operation, correct VTs and
-  // still perform optimization on x86 if needed.
-  if (SelOpNo && VT != CBO.getValueType())
-    return SDValue();
+  EVT VT = BO->getValueType(0);
 
   // We have a select-of-constants followed by a binary operator with a
   // constant. Eliminate the binop by pulling the constant math into the select.
   // Example: add (select Cond, CT, CF), CBO --> select Cond, CT + CBO, CF + CBO
   SDLoc DL(Sel);
   SDValue NewCT = SelOpNo ? DAG.getNode(BinOpcode, DL, VT, CBO, CT)
                           : DAG.getNode(BinOpcode, DL, VT, CT, CBO);
   if (!CanFoldNonConst && !NewCT.isUndef() &&

llvm/test/CodeGen/AArch64/select_const.ll

; CHECK-NEXT:    ret
   %bo = shl i8 %sel, 5
   ret i8 %bo
 }
 
 define i8 @shl_constant_sel_constants(i1 %cond) {
 ; CHECK-LABEL: shl_constant_sel_constants:
 ; CHECK:       // %bb.0:
 ; CHECK-NEXT:    tst w0, #0x1
-; CHECK-NEXT:    mov w8, #2
-; CHECK-NEXT:    cinc x8, x8, eq
-; CHECK-NEXT:    mov w9, #1
-; CHECK-NEXT:    lsl w0, w9, w8
+; CHECK-NEXT:    mov w8, #8
+; CHECK-NEXT:    mov w9, #4
+; CHECK-NEXT:    csel w0, w9, w8, ne
 ; CHECK-NEXT:    ret
   %sel = select i1 %cond, i8 2, i8 3
   %bo = shl i8 1, %sel
   ret i8 %bo
 }
 
 define i8 @sel_constants_lshr_constant(i1 %cond) {
 ; CHECK-LABEL: sel_constants_lshr_constant:
 ; CHECK:       // %bb.0:
 ; CHECK-NEXT:    tst w0, #0x1
 ; CHECK-NEXT:    mov w8, #7
 ; CHECK-NEXT:    csel w0, w8, wzr, ne
 ; CHECK-NEXT:    ret
   %sel = select i1 %cond, i8 -4, i8 23
   %bo = lshr i8 %sel, 5
   ret i8 %bo
 }
 
 define i8 @lshr_constant_sel_constants(i1 %cond) {
 ; CHECK-LABEL: lshr_constant_sel_constants:
 ; CHECK:       // %bb.0:
 ; CHECK-NEXT:    tst w0, #0x1
-; CHECK-NEXT:    mov w8, #2
-; CHECK-NEXT:    cinc x8, x8, eq
-; CHECK-NEXT:    mov w9, #64
-; CHECK-NEXT:    lsr w0, w9, w8
+; CHECK-NEXT:    mov w8, #8
+; CHECK-NEXT:    mov w9, #16
+; CHECK-NEXT:    csel w0, w9, w8, ne
 ; CHECK-NEXT:    ret
   %sel = select i1 %cond, i8 2, i8 3
   %bo = lshr i8 64, %sel
   ret i8 %bo
 }
 
 
 define i8 @sel_constants_ashr_constant(i1 %cond) {
 ; CHECK-LABEL: sel_constants_ashr_constant:
 ; CHECK:       // %bb.0:
 ; CHECK-NEXT:    sbfx w0, w0, #0, #1
 ; CHECK-NEXT:    ret
   %sel = select i1 %cond, i8 -4, i8 23
   %bo = ashr i8 %sel, 5
   ret i8 %bo
 }
 
 define i8 @ashr_constant_sel_constants(i1 %cond) {
 ; CHECK-LABEL: ashr_constant_sel_constants:
 ; CHECK:       // %bb.0:
 ; CHECK-NEXT:    tst w0, #0x1
-; CHECK-NEXT:    mov w8, #2
-; CHECK-NEXT:    cinc x8, x8, eq
-; CHECK-NEXT:    mov w9, #-128
-; CHECK-NEXT:    asr w0, w9, w8
+; CHECK-NEXT:    mov w8, #-16
+; CHECK-NEXT:    mov w9, #-32
+; CHECK-NEXT:    csel w0, w9, w8, ne
 ; CHECK-NEXT:    ret
   %sel = select i1 %cond, i8 2, i8 3
   %bo = ashr i8 128, %sel
   ret i8 %bo
 }
 
 define double @sel_constants_fadd_constant(i1 %cond) {
 ; CHECK-LABEL: sel_constants_fadd_constant:

llvm/test/CodeGen/PowerPC/select_const.ll

 ; NO_ISEL-NEXT:    addi 3, 4, 0
 ; NO_ISEL-NEXT:    blr
   %sel = select i1 %cond, i8 -4, i8 23
   %bo = shl i8 %sel, 5
   ret i8 %bo
 }
 
 define i8 @shl_constant_sel_constants(i1 %cond) {
-; ALL-LABEL: shl_constant_sel_constants:
-; ALL:       # %bb.0:
-; ALL-NEXT:    clrlwi 3, 3, 31
-; ALL-NEXT:    li 4, 1
-; ALL-NEXT:    subfic 3, 3, 3
-; ALL-NEXT:    slw 3, 4, 3
-; ALL-NEXT:    blr
+; ISEL-LABEL: shl_constant_sel_constants:
+; ISEL:       # %bb.0:
+; ISEL-NEXT:    andi. 3, 3, 1
+; ISEL-NEXT:    li 4, 4
+; ISEL-NEXT:    li 3, 8
+; ISEL-NEXT:    iselgt 3, 4, 3
+; ISEL-NEXT:    blr
+;
+; NO_ISEL-LABEL: shl_constant_sel_constants:
+; NO_ISEL:       # %bb.0:
+; NO_ISEL-NEXT:    andi. 3, 3, 1
+; NO_ISEL-NEXT:    li 4, 4
+; NO_ISEL-NEXT:    li 3, 8
+; NO_ISEL-NEXT:    bc 12, 1, .LBB37_1
+; NO_ISEL-NEXT:    blr
+; NO_ISEL-NEXT:  .LBB37_1:
+; NO_ISEL-NEXT:    addi 3, 4, 0
+; NO_ISEL-NEXT:    blr
   %sel = select i1 %cond, i8 2, i8 3
   %bo = shl i8 1, %sel
   ret i8 %bo
 }
 
 define i8 @sel_constants_lshr_constant(i1 %cond) {
 ; ISEL-LABEL: sel_constants_lshr_constant:
 ; ISEL:       # %bb.0:

 ; NO_ISEL-NEXT:    addi 3, 4, 0
 ; NO_ISEL-NEXT:    blr
   %sel = select i1 %cond, i8 -4, i8 23
   %bo = lshr i8 %sel, 5
   ret i8 %bo
 }
 
 define i8 @lshr_constant_sel_constants(i1 %cond) {
-; ALL-LABEL: lshr_constant_sel_constants:
-; ALL:       # %bb.0:
-; ALL-NEXT:    clrlwi 3, 3, 31
-; ALL-NEXT:    li 4, 64
-; ALL-NEXT:    subfic 3, 3, 3
-; ALL-NEXT:    srw 3, 4, 3
-; ALL-NEXT:    blr
+; ISEL-LABEL: lshr_constant_sel_constants:
+; ISEL:       # %bb.0:
+; ISEL-NEXT:    andi. 3, 3, 1
+; ISEL-NEXT:    li 4, 16
+; ISEL-NEXT:    li 3, 8
+; ISEL-NEXT:    iselgt 3, 4, 3
+; ISEL-NEXT:    blr
+;
+; NO_ISEL-LABEL: lshr_constant_sel_constants:
+; NO_ISEL:       # %bb.0:
+; NO_ISEL-NEXT:    andi. 3, 3, 1
+; NO_ISEL-NEXT:    li 4, 16
+; NO_ISEL-NEXT:    li 3, 8
+; NO_ISEL-NEXT:    bc 12, 1, .LBB39_1
+; NO_ISEL-NEXT:    blr
+; NO_ISEL-NEXT:  .LBB39_1:
+; NO_ISEL-NEXT:    addi 3, 4, 0
+; NO_ISEL-NEXT:    blr
   %sel = select i1 %cond, i8 2, i8 3
   %bo = lshr i8 64, %sel
   ret i8 %bo
 }
 
 
 define i8 @sel_constants_ashr_constant(i1 %cond) {
 ; ALL-LABEL: sel_constants_ashr_constant:
 ; ALL:       # %bb.0:
 ; ALL-NEXT:    clrldi 3, 3, 63
 ; ALL-NEXT:    neg 3, 3
 ; ALL-NEXT:    blr
   %sel = select i1 %cond, i8 -4, i8 23
   %bo = ashr i8 %sel, 5
   ret i8 %bo
 }
 
 define i8 @ashr_constant_sel_constants(i1 %cond) {
-; ALL-LABEL: ashr_constant_sel_constants:
-; ALL:       # %bb.0:
-; ALL-NEXT:    clrlwi 3, 3, 31
-; ALL-NEXT:    li 4, -128
-; ALL-NEXT:    subfic 3, 3, 3
-; ALL-NEXT:    sraw 3, 4, 3
-; ALL-NEXT:    blr
+; ISEL-LABEL: ashr_constant_sel_constants:
+; ISEL:       # %bb.0:
+; ISEL-NEXT:    andi. 3, 3, 1
+; ISEL-NEXT:    li 4, -32
+; ISEL-NEXT:    li 3, -16
+; ISEL-NEXT:    iselgt 3, 4, 3
+; ISEL-NEXT:    blr
+;
+; NO_ISEL-LABEL: ashr_constant_sel_constants:
+; NO_ISEL:       # %bb.0:
+; NO_ISEL-NEXT:    andi. 3, 3, 1
+; NO_ISEL-NEXT:    li 4, -32
+; NO_ISEL-NEXT:    li 3, -16
+; NO_ISEL-NEXT:    bc 12, 1, .LBB41_1
+; NO_ISEL-NEXT:    blr
+; NO_ISEL-NEXT:  .LBB41_1:
+; NO_ISEL-NEXT:    addi 3, 4, 0
+; NO_ISEL-NEXT:    blr
   %sel = select i1 %cond, i8 2, i8 3
   %bo = ashr i8 128, %sel
   ret i8 %bo
 }
 
 define double @sel_constants_fadd_constant(i1 %cond) {
 ; ISEL-LABEL: sel_constants_fadd_constant:
 ; ISEL:       # %bb.0:

llvm/test/CodeGen/X86/dagcombine-select.ll

; CHECK-NEXT:    retq
   %sel = select i1 %cond, i32 2, i32 3
   %bo = shl i32 %sel, 8
   ret i32 %bo
 }
 
 define i32 @shl_constant_sel_constants(i1 %cond) {
 ; CHECK-LABEL: shl_constant_sel_constants:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    movl %edi, %ecx
-; CHECK-NEXT:    andb $1, %cl
-; CHECK-NEXT:    xorb $3, %cl
-; CHECK-NEXT:    movl $1, %eax
-; CHECK-NEXT:    # kill: def $cl killed $cl killed $ecx
-; CHECK-NEXT:    shll %cl, %eax
+; CHECK-NEXT:    notb %dil
+; CHECK-NEXT:    movzbl %dil, %eax
+; CHECK-NEXT:    andl $1, %eax
+; CHECK-NEXT:    leal 4(,%rax,4), %eax
 ; CHECK-NEXT:    retq
   %sel = select i1 %cond, i32 2, i32 3
   %bo = shl i32 1, %sel
   ret i32 %bo
 }
 
 define i32 @lshr_constant_sel_constants(i1 %cond) {
 ; CHECK-LABEL: lshr_constant_sel_constants:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    movl %edi, %ecx
-; CHECK-NEXT:    andb $1, %cl
-; CHECK-NEXT:    xorb $3, %cl
-; CHECK-NEXT:    movl $64, %eax
-; CHECK-NEXT:    # kill: def $cl killed $cl killed $ecx
-; CHECK-NEXT:    shrl %cl, %eax
+; CHECK-NEXT:    # kill: def $edi killed $edi def $rdi
+; CHECK-NEXT:    andl $1, %edi
+; CHECK-NEXT:    leal 8(,%rdi,8), %eax
 ; CHECK-NEXT:    retq
   %sel = select i1 %cond, i32 2, i32 3
   %bo = lshr i32 64, %sel
   ret i32 %bo
 }
 
 define i32 @ashr_constant_sel_constants(i1 %cond) {
 ; CHECK-LABEL: ashr_constant_sel_constants:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    movl %edi, %ecx
-; CHECK-NEXT:    andb $1, %cl
-; CHECK-NEXT:    xorb $3, %cl
-; CHECK-NEXT:    movl $128, %eax
-; CHECK-NEXT:    # kill: def $cl killed $cl killed $ecx
-; CHECK-NEXT:    shrl %cl, %eax
+; CHECK-NEXT:    # kill: def $edi killed $edi def $rdi
+; CHECK-NEXT:    andl $1, %edi
+; CHECK-NEXT:    shll $4, %edi
+; CHECK-NEXT:    leal 16(%rdi), %eax
 ; CHECK-NEXT:    retq
   %sel = select i1 %cond, i32 2, i32 3
   %bo = ashr i32 128, %sel
   ret i32 %bo
 }
 
 define double @fsub_constant_sel_constants(i1 %cond) {
 ; CHECK-LABEL: fsub_constant_sel_constants: