[TargetLowering][X86] Teach SimplifyDemandedBits to use ShrinkDemandedOp on ISD::SHL nodes.

[craig.topper]

Summary

If the upper bits of the SHL result aren't used, we might be able to use a narrower shift. For example, on X86 this can turn a 64-bit into 32-bit enabling a smaller encoding.

[craig.topper]

Rebase

[RKSimon]

llvm/test/CodeGen/X86/zext-logicop-shift-load.ll

26

Are you looking at this as a followup?

[spatel]

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

11041–11045 ↗

(On Diff #194208)

It would be better to split this change off on its own while adding a test specifically for this pattern.

IIUC, we can modify the existing test slightly and show the missing fold:

declare void @t()
define void @tbz_zext(i32 %in) {
  %shl = shl i32 %in, 3
  %t = zext i32 %shl to i64
  %and = and i64 %t, 32
  %cond = icmp eq i64 %and, 0
  br i1 %cond, label %then, label %end

then:
  call void @t()
  br label %end

end:
  ret void
}

[craig.topper]

Remove the AArch64 code change. Show the regression instead. I'll work on the separate patch and rebase accordingly depending on what order they get committed

[spatel]

I think D60482 should go in 1st, so we avoid that known regression. There's still an open question about the x86 LEA matching. I've seen that or similar matching failures in other tests, so it would be nice to catch it first too.

I wonder if losing the wrapping flags is hurting. Although we should be able to use knownbits to restore the knowledge. Something like this?

define i64 @lea(i64 %t0, i32 %t1) {
  %t4 = add nuw nsw i32 %t1, 8
  %sh = shl nsw i32 %t4, 2
  %t5 = zext i32 %sh to i64
  %t6 = add i64 %t5, %t0
  ret i64 %t6
}

Produces:
leal 32(,%rsi,4), %eax
addq %rdi, %rax

Instead of:
leaq 32(%rdi,%rsi,4), %rax

[craig.topper]

For the LEA regression here, we need to teach foldMaskedShiftToScaledMask to look through the any_extend to find the shift and reinsert the any_extend in the new ordering.

[craig.topper]

Rebase

[spatel]

LGTM

[efriedma]

I just pushed rGd8b9ed72ee83, a testcase affected by this patch.

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

if (ConstantSDNode *SA = isConstOrConstSplat(Op1)) {
           }
         }
       }
 
       if (SimplifyDemandedBits(Op0, DemandedBits.lshr(ShAmt), DemandedElts,
                                Known, TLO, Depth + 1))
         return true;
 
+      // Try shrinking the operation as long as the shift amount will still be
+      // in range.
+      if ((ShAmt < DemandedBits.getActiveBits()) &&
+          ShrinkDemandedOp(Op, BitWidth, DemandedBits, TLO))
+        return true;
+
       // Convert (shl (anyext x, c)) to (anyext (shl x, c)) if the high bits
       // are not demanded. This will likely allow the anyext to be folded away.
       if (Op0.getOpcode() == ISD::ANY_EXTEND) {
         SDValue InnerOp = Op0.getOperand(0);
         EVT InnerVT = InnerOp.getValueType();
         unsigned InnerBits = InnerVT.getScalarSizeInBits();
         if (ShAmt < InnerBits && DemandedBits.getActiveBits() <= InnerBits &&
             isTypeDesirableForOp(ISD::SHL, InnerVT)) {

llvm/test/CodeGen/AArch64/tbz-tbnz.ll

 
 define void @test16(i64 %in) {
 ; CHECK-LABEL: @test16
   %shl = shl i64 %in, 3
   %and = and i64 %shl, 32
   %cond = icmp eq i64 %and, 0
   br i1 %cond, label %then, label %end
 
-; CHECK-NOT: lsl
-; CHECK: tbnz w0, #2
+; FIXME: Should be no lsl
+; CHECK: lsl w8, w0, #3
+; CHECK: tbnz w8, #5
 
 then:
   call void @t()
   br label %end
 
 end:
   ret void
 }

llvm/test/CodeGen/X86/btc_bts_btr.ll

; X86-NEXT:    retl
   %4 = xor i32 %x, %3
   ret i32 %4
 }
 
 define i64 @btr_64_mask_zeros(i64 %x, i64 %n) {
 ; X64-LABEL: btr_64_mask_zeros:
 ; X64:       # %bb.0:
 ; X64-NEXT:    movq %rdi, %rax
-; X64-NEXT:    shlq $2, %rsi
+; X64-NEXT:    shll $2, %esi
 ; X64-NEXT:    btrq %rsi, %rax
 ; X64-NEXT:    retq
 ;
 ; X86-LABEL: btr_64_mask_zeros:
 ; X86:       # %bb.0:
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 ; X86-NEXT:    shll $2, %ecx
 ; X86-NEXT:    movl $1, %eax
; X86-NEXT:    retl
   %5 = and i64 %x, %4
   ret i64 %5
 }
 
 define i64 @bts_64_mask_zeros(i64 %x, i64 %n) {
 ; X64-LABEL: bts_64_mask_zeros:
 ; X64:       # %bb.0:
 ; X64-NEXT:    movq %rdi, %rax
-; X64-NEXT:    shlq $2, %rsi
+; X64-NEXT:    shll $2, %esi
 ; X64-NEXT:    btsq %rsi, %rax
 ; X64-NEXT:    retq
 ;
 ; X86-LABEL: bts_64_mask_zeros:
 ; X86:       # %bb.0:
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 ; X86-NEXT:    shll $2, %ecx
 ; X86-NEXT:    movl $1, %eax
; X86-NEXT:    retl
   %4 = or i64 %x, %3
   ret i64 %4
 }
 
 define i64 @btc_64_mask_zeros(i64 %x, i64 %n) {
 ; X64-LABEL: btc_64_mask_zeros:
 ; X64:       # %bb.0:
 ; X64-NEXT:    movq %rdi, %rax
-; X64-NEXT:    shlq $2, %rsi
+; X64-NEXT:    shll $2, %esi
 ; X64-NEXT:    btcq %rsi, %rax
 ; X64-NEXT:    retq
 ;
 ; X86-LABEL: btc_64_mask_zeros:
 ; X86:       # %bb.0:
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 ; X86-NEXT:    shll $2, %ecx
 ; X86-NEXT:    movl $1, %eax

llvm/test/CodeGen/X86/narrow-shl-cst.ll

; CHECK-NEXT:    retq
   %shl = and i32 %and, 255
   store i32 %shl, i32* %y
   ret i32 %shl
 }
 
 define i64 @test13(i64 %x, i64* %y) nounwind {
 ; CHECK-LABEL: test13:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    movq %rdi, %rax
-; CHECK-NEXT:    andl $127, %eax
-; CHECK-NEXT:    addq %rax, %rax
+; CHECK-NEXT:    addl %edi, %edi
+; CHECK-NEXT:    movzbl %dil, %eax
 ; CHECK-NEXT:    movq %rax, (%rsi)
 ; CHECK-NEXT:    retq
   %and = shl i64 %x, 1
   %shl = and i64 %and, 255
   store i64 %shl, i64* %y
   ret i64 %shl
 }
 

llvm/test/CodeGen/X86/scheduler-backtracking.ll

 
 define i256 @test1(i256 %a) nounwind {
 ; ILP-LABEL: test1:
 ; ILP:       # %bb.0:
 ; ILP-NEXT:    pushq %r14
 ; ILP-NEXT:    pushq %rbx
 ; ILP-NEXT:    movq %rdi, %rax
 ; ILP-NEXT:    xorl %r8d, %r8d
-; ILP-NEXT:    addq %rsi, %rsi
+; ILP-NEXT:    addl %esi, %esi
 ; ILP-NEXT:    addb $2, %sil
 ; ILP-NEXT:    orb $1, %sil
 ; ILP-NEXT:    movl $1, %r10d
 ; ILP-NEXT:    xorl %r14d, %r14d
 ; ILP-NEXT:    movl %esi, %ecx
 ; ILP-NEXT:    shldq %cl, %r10, %r14
 ; ILP-NEXT:    movl $1, %edx
 ; ILP-NEXT:    shlq %cl, %rdx
-; ILP-NEXT:    movb $-128, %r11b
-; ILP-NEXT:    subb %sil, %r11b
 ; ILP-NEXT:    leal -128(%rsi), %r9d
-; ILP-NEXT:    xorl %edi, %edi
+; ILP-NEXT:    movb $-128, %r11b
+; ILP-NEXT:    xorl %ebx, %ebx
 ; ILP-NEXT:    movl %r9d, %ecx
-; ILP-NEXT:    shldq %cl, %r10, %rdi
-; ILP-NEXT:    movl $1, %ebx
-; ILP-NEXT:    shlq %cl, %rbx
-; ILP-NEXT:    movl %r11d, %ecx
-; ILP-NEXT:    shrdq %cl, %r8, %r10
+; ILP-NEXT:    shldq %cl, %r10, %rbx
 ; ILP-NEXT:    testb $64, %sil
 ; ILP-NEXT:    cmovneq %rdx, %r14
 ; ILP-NEXT:    cmovneq %r8, %rdx
+; ILP-NEXT:    movl $1, %edi
+; ILP-NEXT:    shlq %cl, %rdi
+; ILP-NEXT:    subb %sil, %r11b
+; ILP-NEXT:    movl %r11d, %ecx
+; ILP-NEXT:    shrdq %cl, %r8, %r10
 ; ILP-NEXT:    testb $64, %r11b
 ; ILP-NEXT:    cmovneq %r8, %r10
 ; ILP-NEXT:    testb $64, %r9b
-; ILP-NEXT:    cmovneq %rbx, %rdi
-; ILP-NEXT:    cmovneq %r8, %rbx
+; ILP-NEXT:    cmovneq %rdi, %rbx
+; ILP-NEXT:    cmovneq %r8, %rdi
 ; ILP-NEXT:    testb %sil, %sil
 ; ILP-NEXT:    cmovsq %r8, %r14
 ; ILP-NEXT:    cmovsq %r8, %rdx
 ; ILP-NEXT:    movq %r14, 8(%rax)
 ; ILP-NEXT:    movq %rdx, (%rax)
-; ILP-NEXT:    cmovnsq %r8, %rdi
-; ILP-NEXT:    cmoveq %r8, %rdi
-; ILP-NEXT:    movq %rdi, 24(%rax)
-; ILP-NEXT:    cmovnsq %r10, %rbx
+; ILP-NEXT:    cmovnsq %r8, %rbx
 ; ILP-NEXT:    cmoveq %r8, %rbx
-; ILP-NEXT:    movq %rbx, 16(%rax)
+; ILP-NEXT:    movq %rbx, 24(%rax)
+; ILP-NEXT:    cmovnsq %r10, %rdi
+; ILP-NEXT:    cmoveq %r8, %rdi
+; ILP-NEXT:    movq %rdi, 16(%rax)
 ; ILP-NEXT:    popq %rbx
 ; ILP-NEXT:    popq %r14
 ; ILP-NEXT:    retq
 ;
 ; HYBRID-LABEL: test1:
 ; HYBRID:       # %bb.0:
 ; HYBRID-NEXT:    movq %rdi, %rax
-; HYBRID-NEXT:    addq %rsi, %rsi
+; HYBRID-NEXT:    addl %esi, %esi
 ; HYBRID-NEXT:    addb $2, %sil
 ; HYBRID-NEXT:    orb $1, %sil
 ; HYBRID-NEXT:    movb $-128, %cl
 ; HYBRID-NEXT:    subb %sil, %cl
 ; HYBRID-NEXT:    xorl %r8d, %r8d
 ; HYBRID-NEXT:    movl $1, %r11d
 ; HYBRID-NEXT:    movl $1, %r9d
 ; HYBRID-NEXT:    shrdq %cl, %r8, %r9

 ; HYBRID-NEXT:    cmovnsq %r9, %rdx
 ; HYBRID-NEXT:    cmoveq %r8, %rdx
 ; HYBRID-NEXT:    movq %rdx, 16(%rax)
 ; HYBRID-NEXT:    retq
 ;
 ; BURR-LABEL: test1:
 ; BURR:       # %bb.0:
 ; BURR-NEXT:    movq %rdi, %rax
-; BURR-NEXT:    addq %rsi, %rsi
+; BURR-NEXT:    addl %esi, %esi
 ; BURR-NEXT:    addb $2, %sil
 ; BURR-NEXT:    orb $1, %sil
 ; BURR-NEXT:    movb $-128, %cl
 ; BURR-NEXT:    subb %sil, %cl
 ; BURR-NEXT:    xorl %r8d, %r8d
 ; BURR-NEXT:    movl $1, %r11d
 ; BURR-NEXT:    movl $1, %r9d
 ; BURR-NEXT:    shrdq %cl, %r8, %r9

 ; BURR-NEXT:    cmoveq %r8, %rdx
 ; BURR-NEXT:    movq %rdx, 16(%rax)
 ; BURR-NEXT:    retq
 ;
 ; SRC-LABEL: test1:
 ; SRC:       # %bb.0:
 ; SRC-NEXT:    pushq %rbx
 ; SRC-NEXT:    movq %rdi, %rax
-; SRC-NEXT:    addq %rsi, %rsi
+; SRC-NEXT:    addl %esi, %esi
 ; SRC-NEXT:    addb $2, %sil
 ; SRC-NEXT:    orb $1, %sil
 ; SRC-NEXT:    movb $-128, %cl
 ; SRC-NEXT:    subb %sil, %cl
 ; SRC-NEXT:    xorl %r8d, %r8d
 ; SRC-NEXT:    movl $1, %edi
 ; SRC-NEXT:    movl $1, %r10d
 ; SRC-NEXT:    shrdq %cl, %r8, %r10

 ; SRC-NEXT:    popq %rbx
 ; SRC-NEXT:    retq
 ;
 ; LIN-LABEL: test1:
 ; LIN:       # %bb.0:
 ; LIN-NEXT:    movq %rdi, %rax
 ; LIN-NEXT:    xorl %r9d, %r9d
 ; LIN-NEXT:    movl $1, %r8d
-; LIN-NEXT:    addq %rsi, %rsi
+; LIN-NEXT:    addl %esi, %esi
 ; LIN-NEXT:    addb $2, %sil
 ; LIN-NEXT:    orb $1, %sil
 ; LIN-NEXT:    movl $1, %edx
 ; LIN-NEXT:    movl %esi, %ecx
 ; LIN-NEXT:    shlq %cl, %rdx
 ; LIN-NEXT:    testb $64, %sil
 ; LIN-NEXT:    movq %rdx, %rcx
 ; LIN-NEXT:    cmovneq %r9, %rcx

llvm/test/CodeGen/X86/zext-logicop-shift-load.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=x86_64-unknown-unknown | FileCheck %s
 
 
 define i64 @test1(i8* %data) {
 ; CHECK-LABEL: test1:
 ; CHECK:       # %bb.0: # %entry
 ; CHECK-NEXT:    movl (%rdi), %eax
-; CHECK-NEXT:    shlq $2, %rax
+; CHECK-NEXT:    shll $2, %eax
 ; CHECK-NEXT:    andl $60, %eax
 ; CHECK-NEXT:    retq
 entry:
   %bf.load = load i8, i8* %data, align 4
   %bf.clear = shl i8 %bf.load, 2
   %0 = and i8 %bf.clear, 60
   %mul = zext i8 %0 to i64
   ret i64 %mul
 }
 
 define i8* @test2(i8* %data) {
 ; CHECK-LABEL: test2:
 ; CHECK:       # %bb.0: # %entry
 ; CHECK-NEXT:    movl (%rdi), %eax
-; CHECK-NEXT:    andl $15, %eax
-; CHECK-NEXT:    leaq (%rdi,%rax,4), %rax
+; CHECK-NEXT:    shll $2, %eax
+; CHECK-NEXT:    andl $60, %eax
+; CHECK-NEXT:    addq %rdi, %rax
 ; CHECK-NEXT:    retq
 entry:
   %bf.load = load i8, i8* %data, align 4
   %bf.clear = shl i8 %bf.load, 2
   %0 = and i8 %bf.clear, 60
   %mul = zext i8 %0 to i64
   %add.ptr = getelementptr inbounds i8, i8* %data, i64 %mul
   ret i8* %add.ptr