[DAGCombiner] try to convert opposing shifts to casts

[spatel]

Summary

This reverses a questionable IR canonicalization when a truncate is free:

sra (add (shl X, N1C), AddC), N1C -->
sext (add (trunc X to (width - N1C)), AddC')

https://rise4fun.com/Alive/slRC

More details in PR42644:
https://bugs.llvm.org/show_bug.cgi?id=42644

I limited this to pre-legalization for code simplicity because that should be enough to reverse the IR patterns. I don't have any evidence (no regression test diffs) that we need to try this later.

[lebedev.ri]

Looks good.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

7624

Don't we also need for N0 to be one-use?

[xbolva00]

Thanks for fixing this!

[spatel]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

7624

Good catch. I was assuming that the free truncate wasn't a real instruction (and lazily didn't include extra-use tests), so that case would be ok. But that's not true. If either operand has extra uses, this transform can result in an extra x86 instruction, so it's unlikely to be profitable.

[spatel]

Patch updated:

1. Added 1 more one-use restriction.
2. Added extra-use tests (not changed here - baseline rL367677).

[lebedev.ri]

LGTM

[mstorsjo]

This caused failed asserts ("Unexpected illegal type!" in LegalizeDAG) when building Qt, with https://martin.st/temp/qpainterpath-preproc.cpp, built with clang++ -target i686-w64-mingw32 -c -O3 -std=c++17 qpainterpath-preproc.cpp. Will file a full proper bug later if necessary.

[lebedev.ri]

In D65607#1613401, @mstorsjo wrote:

This caused failed asserts ("Unexpected illegal type!" in LegalizeDAG) when building Qt, with https://martin.st/temp/qpainterpath-preproc.cpp, built with clang++ -target i686-w64-mingw32 -c -O3 -std=c++17 qpainterpath-preproc.cpp. Will file a full proper bug later if necessary.

Would be good to have a reproducer, even just N->dumprFull() may shed some light.

[mstorsjo]

In D65607#1613403, @lebedev.ri wrote:

In D65607#1613401, @mstorsjo wrote:

This caused failed asserts ("Unexpected illegal type!" in LegalizeDAG) when building Qt, with https://martin.st/temp/qpainterpath-preproc.cpp, built with clang++ -target i686-w64-mingw32 -c -O3 -std=c++17 qpainterpath-preproc.cpp. Will file a full proper bug later if necessary.

Would be good to have a reproducer, even just N->dumprFull() may shed some light.

Node->dumprFull(); for the failed assert prints

t51: i32 = sign_extend t50
  t50: i29 = add t48, Constant:i29<-3>
    t48: i29 = truncate t46
      t46: i32 = <<Unknown Node #438>> t8, Constant:i32<3>
        t8: i32,ch = CopyFromReg t0, Register:i32 %13
          t7: i32 = Register %13
        t45: i32 = Constant<3>
    t49: i29 = Constant<-3>

[spatel]

In D65607#1613432, @mstorsjo wrote:

In D65607#1613403, @lebedev.ri wrote:

In D65607#1613401, @mstorsjo wrote:

This caused failed asserts ("Unexpected illegal type!" in LegalizeDAG) when building Qt, with https://martin.st/temp/qpainterpath-preproc.cpp, built with clang++ -target i686-w64-mingw32 -c -O3 -std=c++17 qpainterpath-preproc.cpp. Will file a full proper bug later if necessary.

Would be good to have a reproducer, even just N->dumprFull() may shed some light.

Node->dumprFull(); for the failed assert prints

t51: i32 = sign_extend t50
  t50: i29 = add t48, Constant:i29<-3>
    t48: i29 = truncate t46
      t46: i32 = <<Unknown Node #438>> t8, Constant:i32<3>
        t8: i32,ch = CopyFromReg t0, Register:i32 %13
          t7: i32 = Register %13
        t45: i32 = Constant<3>
    t49: i29 = Constant<-3>

I can guess how we should limit this transform, but my translation of that DAG to IR does not crash for me:

define i32 @trunc29(i32 %x) nounwind {
  %u2 = trunc i32 %x to i29
  %u3 = add i29 %u2, -3
  %r = sext i29 %u3 to i32
  ret i32 %r
}

...so I need more info.

[mstorsjo]

In D65607#1613461, @spatel wrote:

In D65607#1613432, @mstorsjo wrote:

In D65607#1613403, @lebedev.ri wrote:

In D65607#1613401, @mstorsjo wrote:

This caused failed asserts ("Unexpected illegal type!" in LegalizeDAG) when building Qt, with https://martin.st/temp/qpainterpath-preproc.cpp, built with clang++ -target i686-w64-mingw32 -c -O3 -std=c++17 qpainterpath-preproc.cpp. Will file a full proper bug later if necessary.

Would be good to have a reproducer, even just N->dumprFull() may shed some light.

Node->dumprFull(); for the failed assert prints

t51: i32 = sign_extend t50
  t50: i29 = add t48, Constant:i29<-3>
    t48: i29 = truncate t46
      t46: i32 = <<Unknown Node #438>> t8, Constant:i32<3>
        t8: i32,ch = CopyFromReg t0, Register:i32 %13
          t7: i32 = Register %13
        t45: i32 = Constant<3>
    t49: i29 = Constant<-3>

I can guess how we should limit this transform, but my translation of that DAG to IR does not crash for me:

define i32 @trunc29(i32 %x) nounwind {
  %u2 = trunc i32 %x to i29
  %u3 = add i29 %u2, -3
  %r = sext i29 %u3 to i32
  ret i32 %r
}

...so I need more info.

The original standalone preprocessed C++ code I linked before was reproducible on its own already, but I went ahead and made a reduced IR reproducer out of it, and filed a bug for it at https://bugs.llvm.org/show_bug.cgi?id=42880.

[spatel]

In D65607#1613601, @mstorsjo wrote:

In D65607#1613461, @spatel wrote:

In D65607#1613432, @mstorsjo wrote:

In D65607#1613403, @lebedev.ri wrote:

In D65607#1613401, @mstorsjo wrote:

This caused failed asserts ("Unexpected illegal type!" in LegalizeDAG) when building Qt, with https://martin.st/temp/qpainterpath-preproc.cpp, built with clang++ -target i686-w64-mingw32 -c -O3 -std=c++17 qpainterpath-preproc.cpp. Will file a full proper bug later if necessary.

Would be good to have a reproducer, even just N->dumprFull() may shed some light.

Node->dumprFull(); for the failed assert prints

t51: i32 = sign_extend t50
  t50: i29 = add t48, Constant:i29<-3>
    t48: i29 = truncate t46
      t46: i32 = <<Unknown Node #438>> t8, Constant:i32<3>
        t8: i32,ch = CopyFromReg t0, Register:i32 %13
          t7: i32 = Register %13
        t45: i32 = Constant<3>
    t49: i29 = Constant<-3>

I can guess how we should limit this transform, but my translation of that DAG to IR does not crash for me:

define i32 @trunc29(i32 %x) nounwind {
  %u2 = trunc i32 %x to i29
  %u3 = add i29 %u2, -3
  %r = sext i29 %u3 to i32
  ret i32 %r
}

...so I need more info.

The original standalone preprocessed C++ code I linked before was reproducible on its own already, but I went ahead and made a reduced IR reproducer out of it, and filed a bug for it at https://bugs.llvm.org/show_bug.cgi?id=42880.

Thank you for reducing that! I submitted:
rL367766
...as an immediate fix, but I'm still not sure what happens later to cause the assert.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

if (N01C) {
         SDValue Trunc = DAG.getNode(ISD::TRUNCATE, DL, TruncVT,
                                     Shift);
         return DAG.getNode(ISD::SIGN_EXTEND, DL,
                            N->getValueType(0), Trunc);
       }
     }
   }
 
+  // We convert trunc/ext to opposing shifts in IR, but casts may be cheaper.
+  //   sra (add (shl X, N1C), AddC), N1C -->
+  //   sext (add (trunc X to (width - N1C)), AddC')
+  if (!LegalOperations && N0.getOpcode() == ISD::ADD && N1C &&
+      N0.getOperand(0).getOpcode() == ISD::SHL &&
+      N0.getOperand(0).getOperand(1) == N1 && N0.getOperand(0).hasOneUse()) {
+    if (ConstantSDNode *AddC = isConstOrConstSplat(N0.getOperand(1))) {
+      SDValue Shl = N0.getOperand(0);
+      // Determine what the truncate's type would be and ask the target if that
+      // is a free operation.
+      LLVMContext &Ctx = *DAG.getContext();
+      unsigned ShiftAmt = N1C->getZExtValue();
+      EVT TruncVT = EVT::getIntegerVT(Ctx, OpSizeInBits - ShiftAmt);
+      if (VT.isVector())
+        TruncVT = EVT::getVectorVT(Ctx, TruncVT, VT.getVectorNumElements());
+      if (TLI.isTruncateFree(VT, TruncVT)) {
+        SDLoc DL(N);
+        SDValue Trunc = DAG.getZExtOrTrunc(Shl.getOperand(0), DL, TruncVT);
+        SDValue ShiftC = DAG.getConstant(AddC->getAPIntValue().lshr(ShiftAmt).
+                             trunc(TruncVT.getScalarSizeInBits()), DL, TruncVT);
+        SDValue Add = DAG.getNode(ISD::ADD, DL, TruncVT, Trunc, ShiftC);
+        return DAG.getSExtOrTrunc(Add, DL, VT);
+      }
+    }
+  }
+
   // fold (sra x, (trunc (and y, c))) -> (sra x, (and (trunc y), (trunc c))).
   if (N1.getOpcode() == ISD::TRUNCATE &&
       N1.getOperand(0).getOpcode() == ISD::AND) {
     if (SDValue NewOp1 = distributeTruncateThroughAnd(N1.getNode()))
       return DAG.getNode(ISD::SRA, SDLoc(N), VT, N0, NewOp1);
   }
 
   // fold (sra (trunc (sra x, c1)), c2) -> (trunc (sra x, c1 + c2))

llvm/test/CodeGen/AArch64/shift-mod.ll

entry:
   ret i64 %shr
 }
 
 ; PR42644 - https://bugs.llvm.org/show_bug.cgi?id=42644
 
 define i64 @ashr_add_shl_i32(i64 %r) {
 ; CHECK-LABEL: ashr_add_shl_i32:
 ; CHECK:       // %bb.0:
-; CHECK-NEXT:    mov x8, #4294967296
-; CHECK-NEXT:    add x8, x8, x0, lsl #32
-; CHECK-NEXT:    asr x0, x8, #32
+; CHECK-NEXT:    add w8, w0, #1 // =1
+; CHECK-NEXT:    sxtw x0, w8
 ; CHECK-NEXT:    ret
   %conv = shl i64 %r, 32
   %sext = add i64 %conv, 4294967296
   %conv1 = ashr i64 %sext, 32
   ret i64 %conv1
 }
 
 define i64 @ashr_add_shl_i8(i64 %r) {
 ; CHECK-LABEL: ashr_add_shl_i8:
 ; CHECK:       // %bb.0:
-; CHECK-NEXT:    mov x8, #72057594037927936
-; CHECK-NEXT:    add x8, x8, x0, lsl #56
-; CHECK-NEXT:    asr x0, x8, #56
+; CHECK-NEXT:    add w8, w0, #1 // =1
+; CHECK-NEXT:    sxtb x0, w8
 ; CHECK-NEXT:    ret
   %conv = shl i64 %r, 56
   %sext = add i64 %conv, 72057594037927936
   %conv1 = ashr i64 %sext, 56
   ret i64 %conv1
 }
 
 define <4 x i32> @ashr_add_shl_v4i8(<4 x i32> %r) {

llvm/test/CodeGen/X86/shift-combine.ll

 ; X32-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X32-NEXT:    incl %eax
 ; X32-NEXT:    movl %eax, %edx
 ; X32-NEXT:    sarl $31, %edx
 ; X32-NEXT:    retl
 ;
 ; X64-LABEL: ashr_add_shl_i32:
 ; X64:       # %bb.0:
-; X64-NEXT:    shlq $32, %rdi
-; X64-NEXT:    movabsq $4294967296, %rax # imm = 0x100000000
-; X64-NEXT:    addq %rdi, %rax
-; X64-NEXT:    sarq $32, %rax
+; X64-NEXT:    incl %edi
+; X64-NEXT:    movslq %edi, %rax
 ; X64-NEXT:    retq
   %conv = shl i64 %r, 32
   %sext = add i64 %conv, 4294967296
   %conv1 = ashr i64 %sext, 32
   ret i64 %conv1
 }
 
 define i64 @ashr_add_shl_i8(i64 %r) nounwind {
 ; X32-LABEL: ashr_add_shl_i8:
 ; X32:       # %bb.0:
-; X32-NEXT:    movl {{[0-9]+}}(%esp), %edx
-; X32-NEXT:    shll $24, %edx
-; X32-NEXT:    addl $16777216, %edx # imm = 0x1000000
-; X32-NEXT:    movl %edx, %eax
-; X32-NEXT:    sarl $24, %eax
+; X32-NEXT:    movb {{[0-9]+}}(%esp), %al
+; X32-NEXT:    incb %al
+; X32-NEXT:    movsbl %al, %eax
+; X32-NEXT:    movl %eax, %edx
 ; X32-NEXT:    sarl $31, %edx
 ; X32-NEXT:    retl
 ;
 ; X64-LABEL: ashr_add_shl_i8:
 ; X64:       # %bb.0:
-; X64-NEXT:    shlq $56, %rdi
-; X64-NEXT:    movabsq $72057594037927936, %rax # imm = 0x100000000000000
-; X64-NEXT:    addq %rdi, %rax
-; X64-NEXT:    sarq $56, %rax
+; X64-NEXT:    incb %dil
+; X64-NEXT:    movsbq %dil, %rax
 ; X64-NEXT:    retq
   %conv = shl i64 %r, 56
   %sext = add i64 %conv, 72057594037927936
   %conv1 = ashr i64 %sext, 56
   ret i64 %conv1
 }
 
 define <4 x i32> @ashr_add_shl_v4i8(<4 x i32> %r) nounwind {
 ; X32-LABEL: ashr_add_shl_v4i8:
 ; X32:       # %bb.0:
 ; X32-NEXT:    pushl %edi
 ; X32-NEXT:    pushl %esi
 ; X32-NEXT:    movl {{[0-9]+}}(%esp), %eax
-; X32-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X32-NEXT:    movl {{[0-9]+}}(%esp), %edx
-; X32-NEXT:    movl {{[0-9]+}}(%esp), %esi
-; X32-NEXT:    movl {{[0-9]+}}(%esp), %edi
-; X32-NEXT:    shll $24, %edi
-; X32-NEXT:    shll $24, %esi
-; X32-NEXT:    shll $24, %edx
-; X32-NEXT:    shll $24, %ecx
-; X32-NEXT:    addl $16777216, %ecx # imm = 0x1000000
-; X32-NEXT:    addl $16777216, %edx # imm = 0x1000000
-; X32-NEXT:    addl $16777216, %esi # imm = 0x1000000
-; X32-NEXT:    addl $16777216, %edi # imm = 0x1000000
-; X32-NEXT:    sarl $24, %edi
-; X32-NEXT:    sarl $24, %esi
-; X32-NEXT:    sarl $24, %edx
-; X32-NEXT:    sarl $24, %ecx
+; X32-NEXT:    movb {{[0-9]+}}(%esp), %cl
+; X32-NEXT:    movb {{[0-9]+}}(%esp), %dl
+; X32-NEXT:    movb {{[0-9]+}}(%esp), %ch
+; X32-NEXT:    movb {{[0-9]+}}(%esp), %dh
+; X32-NEXT:    incb %dh
+; X32-NEXT:    movsbl %dh, %esi
+; X32-NEXT:    incb %ch
+; X32-NEXT:    movsbl %ch, %edi
+; X32-NEXT:    incb %dl
+; X32-NEXT:    movsbl %dl, %edx
+; X32-NEXT:    incb %cl
+; X32-NEXT:    movsbl %cl, %ecx
 ; X32-NEXT:    movl %ecx, 12(%eax)
 ; X32-NEXT:    movl %edx, 8(%eax)
-; X32-NEXT:    movl %esi, 4(%eax)
-; X32-NEXT:    movl %edi, (%eax)
+; X32-NEXT:    movl %edi, 4(%eax)
+; X32-NEXT:    movl %esi, (%eax)
 ; X32-NEXT:    popl %esi
 ; X32-NEXT:    popl %edi
 ; X32-NEXT:    retl $4
 ;
 ; X64-LABEL: ashr_add_shl_v4i8:
 ; X64:       # %bb.0:
+; X64-NEXT:    pcmpeqd %xmm1, %xmm1
+; X64-NEXT:    psubd %xmm1, %xmm0
 ; X64-NEXT:    pslld $24, %xmm0
-; X64-NEXT:    paddd {{.*}}(%rip), %xmm0
 ; X64-NEXT:    psrad $24, %xmm0
 ; X64-NEXT:    retq
   %conv = shl <4 x i32> %r, <i32 24, i32 24, i32 24, i32 24>
   %sext = add <4 x i32> %conv, <i32 16777216, i32 16777216, i32 16777216, i32 16777216>
   %conv1 = ashr <4 x i32> %sext, <i32 24, i32 24, i32 24, i32 24>
   ret <4 x i32> %conv1
 }