[DAGCombiner][AArch64][VE] Teach BuildUDIV/SDIV to use 2x mul when mulh/mul_lohi are not available.

[craig.topper]

Summary

Correct the legality of i32 mul_lohi on AArch64.

Previously, AArch64 incorrectly reported i32 mul_lohi as Legal.
This allowed BuildUDIV/SDIV to use them. A later DAGCombiner would
replace them with MULHS/MULHU because only the high half was used.
This conversion does not check the legality of MULHS/MULHU under
the assumption that LegalizeDAG can turn it back into MUL_LOHI later.

After they are converted to MULHS/MULHU, DAGCombine ran and saw that
these operations aren't supported but an i64 MUL is. So they get
converted to that plus a shift. Without this, LegalizeDAG would
convert back MUL_LOHI and isel would fail to find a pattern.

This patch teaches BuildUDIV/SDIV to create the wide mul and shift
so that we can report the correct operation legality on AArch64. It
also enables div by constant folding for more cases on VE.

I don't know if VE wants this div by constant optimization or not. If they
don't want it, they can use the isIntDivCheap hook to disable it.

[RKSimon]

SGTM - probably need to wait for VE review though

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

5996

We now have a few cases where we're doing this - we already have widenIntegerVectorElementType but for some reason don't have an equivalent widenIntegerScalarType

[craig.topper]

In D150333#4337718, @RKSimon wrote:

SGTM - probably need to wait for VE review though

I might have missed something but looking at commit log, I think VE development has been inactive in 2023.

[RKSimon]

LGTM then, but please raise a bug for the missing VE isIntDivCheap handling

[glaubitz]

This change broke the test CodeGen/M68k/Arith/divide-by-constant.ll on M68k:

FAIL: LLVM :: CodeGen/M68k/Arith/divide-by-constant.ll (11158 of 65166)
******************** TEST 'LLVM :: CodeGen/M68k/Arith/divide-by-constant.ll' FAILED ********************
Script:
--
: 'RUN: at line 2';   /srv/buildbot/workers/suse-gary-m68k-cross/clang-m68k-linux-cross/stage1/bin/llc < /srv/buildbot/workers/suse-gary-m68k-cross/clang-m68k-linux-cross/llvm/llvm/test/CodeGen/M68k/Arith/divide-by-constant.ll -mtriple=m68k-linux -verify-machineinstrs | /srv/buildbot/workers/suse-gary-m68k-cross/clang-m68k-linux-cross/stage1/bin/FileCheck /srv/buildbot/workers/suse-gary-m68k-cross/clang-m68k-linux-cross/llvm/llvm/test/CodeGen/M68k/Arith/divide-by-constant.ll
--
Exit Code: 1

Command Output (stderr):
--
/srv/buildbot/workers/suse-gary-m68k-cross/clang-m68k-linux-cross/llvm/llvm/test/CodeGen/M68k/Arith/divide-by-constant.ll:42:15: error: CHECK-NEXT: expected string not found in input
; CHECK-NEXT: mulu #21846, %d0
              ^
<stdin>:42:17: note: scanning from here
 and.l #255, %d0
                ^
<stdin>:43:2: note: possible intended match here
 muls #171, %d0
 ^
/srv/buildbot/workers/suse-gary-m68k-cross/clang-m68k-linux-cross/llvm/llvm/test/CodeGen/M68k/Arith/divide-by-constant.ll:128:15: error: CHECK-NEXT: is not on the line after the previous match
; CHECK-NEXT: and.l #255, %d0
              ^
<stdin>:132:2: note: 'next' match was here
 and.l #255, %d0
 ^
<stdin>:130:21: note: previous match ended here
 move.b (7,%sp), %d0
                    ^
<stdin>:131:1: note: non-matching line after previous match is here
 lsr.b #1, %d0
^
/srv/buildbot/workers/suse-gary-m68k-cross/clang-m68k-linux-cross/llvm/llvm/test/CodeGen/M68k/Arith/divide-by-constant.ll:142:15: error: CHECK-NEXT: is not on the line after the previous match
; CHECK-NEXT: and.l #255, %d0
              ^
<stdin>:148:2: note: 'next' match was here
 and.l #255, %d0
 ^
<stdin>:146:21: note: previous match ended here
 move.b (7,%sp), %d0
                    ^
<stdin>:147:1: note: non-matching line after previous match is here
 lsr.b #2, %d0
^

Input file: <stdin>
Check file: /srv/buildbot/workers/suse-gary-m68k-cross/clang-m68k-linux-cross/llvm/llvm/test/CodeGen/M68k/Arith/divide-by-constant.ll

-dump-input=help explains the following input dump.

Input was:
<<<<<<
           .
           .
           .
          37:  .type test3,@function 
          38: test3: ; @test3 
          39:  .cfi_startproc 
          40: ; %bb.0: ; %entry 
          41:  move.b (11,%sp), %d0 
          42:  and.l #255, %d0 
next:42'0                     X error: no match found
          43:  muls #171, %d0 
next:42'0     ~~~~~~~~~~~~~~~~
next:42'1      ?               possible intended match
          44:  move.w #9, %d1 
next:42'0     ~~~~~~~~~~~~~~~~
          45:  lsr.w %d1, %d0 
next:42'0     ~~~~~~~~~~~~~~~~
          46:  and.l #65535, %d0 
next:42'0     ~~~~~~~~~~~~~~~~~~~
          47:  rts 
next:42'0     ~~~~~
          48: .Lfunc_end2: 
next:42'0     ~~~~~~~~~~~~~
           .
           .
           .
         127:  .type test8,@function
         128: test8: ; @test8 
         129: ; %bb.0: 
         130:  move.b (7,%sp), %d0 
         131:  lsr.b #1, %d0 
         132:  and.l #255, %d0 
next:128       !~~~~~~~~~~~~~~  error: match on wrong line
         133:  muls #211, %d0 
         134:  move.w #13, %d1 
         135:  lsr.w %d1, %d0 
         136:  ; kill: def $bd0 killed $bd0 killed $d0 
         137:  rts 
           .
           .
           .
         143:  .type test9,@function 
         144: test9: ; @test9 
         145: ; %bb.0: 
         146:  move.b (7,%sp), %d0 
         147:  lsr.b #2, %d0 
         148:  and.l #255, %d0 
next:142       !~~~~~~~~~~~~~~  error: match on wrong line
         149:  muls #71, %d0 
         150:  move.w #11, %d1 
         151:  lsr.w %d1, %d0 
         152:  ; kill: def $bd0 killed $bd0 killed $d0 
         153:  rts 
           .
           .
           .
>>>>>>

--

********************

See: https://lab.llvm.org/buildbot/#/builders/192/builds/1874

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

 //===-- TargetLowering.cpp - Implement the TargetLowering class -----------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
auto GetMULHS = [&](SDValue X, SDValue Y) {
 
     if (isOperationLegalOrCustom(ISD::MULHS, VT, IsAfterLegalization))
       return DAG.getNode(ISD::MULHS, dl, VT, X, Y);
     if (isOperationLegalOrCustom(ISD::SMUL_LOHI, VT, IsAfterLegalization)) {
       SDValue LoHi =
           DAG.getNode(ISD::SMUL_LOHI, dl, DAG.getVTList(VT, VT), X, Y);
       return SDValue(LoHi.getNode(), 1);
     }
+    // If type twice as wide legal, widen and use a mul plus a shift.
+    if (!VT.isVector()) {
+      unsigned Size = VT.getSizeInBits();
+      EVT WideVT = EVT::getIntegerVT(*DAG.getContext(), Size * 2);
+      if (isOperationLegal(ISD::MUL, WideVT)) {
+        X = DAG.getNode(ISD::SIGN_EXTEND, dl, WideVT, X);
+        Y = DAG.getNode(ISD::SIGN_EXTEND, dl, WideVT, Y);
+        Y = DAG.getNode(ISD::MUL, dl, WideVT, X, Y);
+        Y = DAG.getNode(ISD::SRL, dl, WideVT, Y,
+                        DAG.getShiftAmountConstant(EltBits, WideVT, dl));
+        return DAG.getNode(ISD::TRUNCATE, dl, VT, Y);
+      }
+    }
     return SDValue();
   };
 
   SDValue Q = GetMULHS(N0, MagicFactor);
   if (!Q)
     return SDValue();
 
   Created.push_back(Q.getNode());
auto GetMULHU = [&](SDValue X, SDValue Y) {
 
     if (isOperationLegalOrCustom(ISD::MULHU, VT, IsAfterLegalization))
       return DAG.getNode(ISD::MULHU, dl, VT, X, Y);
     if (isOperationLegalOrCustom(ISD::UMUL_LOHI, VT, IsAfterLegalization)) {
       SDValue LoHi =
           DAG.getNode(ISD::UMUL_LOHI, dl, DAG.getVTList(VT, VT), X, Y);
       return SDValue(LoHi.getNode(), 1);
     }
+    // If type twice as wide legal, widen and use a mul plus a shift.
+    if (!VT.isVector()) {
+      unsigned Size = VT.getSizeInBits();
+      EVT WideVT = EVT::getIntegerVT(*DAG.getContext(), Size * 2);
+      if (isOperationLegal(ISD::MUL, WideVT)) {
+        X = DAG.getNode(ISD::ZERO_EXTEND, dl, WideVT, X);
+        Y = DAG.getNode(ISD::ZERO_EXTEND, dl, WideVT, Y);
+        Y = DAG.getNode(ISD::MUL, dl, WideVT, X, Y);
+        Y = DAG.getNode(ISD::SRL, dl, WideVT, Y,
+                        DAG.getShiftAmountConstant(EltBits, WideVT, dl));
+        return DAG.getNode(ISD::TRUNCATE, dl, VT, Y);
+      }
+    }
     return SDValue(); // No mulhu or equivalent
   };
 
   // Multiply the numerator (operand 0) by the magic value.
   Q = GetMULHU(Q, MagicFactor);
   if (!Q)
     return SDValue();
 

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

 //===-- AArch64ISelLowering.cpp - AArch64 DAG Lowering Implementation  ----===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
for (MVT VT : MVT::fixedlen_vector_valuetypes()) {
     setOperationAction(ISD::ROTR, VT, Expand);
   }
 
   // AArch64 doesn't have i32 MULH{S|U}.
   setOperationAction(ISD::MULHU, MVT::i32, Expand);
   setOperationAction(ISD::MULHS, MVT::i32, Expand);
 
   // AArch64 doesn't have {U|S}MUL_LOHI.
+  setOperationAction(ISD::UMUL_LOHI, MVT::i32, Expand);
+  setOperationAction(ISD::SMUL_LOHI, MVT::i32, Expand);
   setOperationAction(ISD::UMUL_LOHI, MVT::i64, Expand);
   setOperationAction(ISD::SMUL_LOHI, MVT::i64, Expand);
 
   if (Subtarget->hasCSSC()) {
     setOperationAction(ISD::CTPOP, MVT::i32, Legal);
     setOperationAction(ISD::CTPOP, MVT::i64, Legal);
     setOperationAction(ISD::CTPOP, MVT::i128, Expand);
 

llvm/test/CodeGen/VE/Scalar/div.ll

; CHECK-NEXT:    b.l.t (, %s10)
   %r = sdiv i64 %a, 3
   ret i64 %r
 }
 
 ; Function Attrs: norecurse nounwind readnone
 define signext i32 @divi32ri(i32 signext %a, i32 signext %b) {
 ; CHECK-LABEL: divi32ri:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    divs.w.sx %s0, %s0, (62)0
+; CHECK-NEXT:    lea %s1, 1431655766
+; CHECK-NEXT:    muls.l %s0, %s0, %s1
+; CHECK-NEXT:    srl %s1, %s0, 63
+; CHECK-NEXT:    srl %s0, %s0, 32
+; CHECK-NEXT:    adds.w.sx %s0, %s0, %s1
 ; CHECK-NEXT:    adds.w.sx %s0, %s0, (0)1
 ; CHECK-NEXT:    b.l.t (, %s10)
   %r = sdiv i32 %a, 3
   ret i32 %r
 }
 
 ; Function Attrs: norecurse nounwind readnone
 define i128 @divu128ri(i128) {
; CHECK-NEXT:    b.l.t (, %s10)
   %r = udiv i64 %a, 3
   ret i64 %r
 }
 
 ; Function Attrs: norecurse nounwind readnone
 define zeroext i32 @divu32ri(i32 zeroext %a, i32 zeroext %b) {
 ; CHECK-LABEL: divu32ri:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    divu.w %s0, %s0, (62)0
-; CHECK-NEXT:    adds.w.zx %s0, %s0, (0)1
+; CHECK-NEXT:    lea %s1, -1431655765
+; CHECK-NEXT:    and %s1, %s1, (32)0
+; CHECK-NEXT:    muls.l %s0, %s0, %s1
+; CHECK-NEXT:    srl %s0, %s0, 33
 ; CHECK-NEXT:    b.l.t (, %s10)
   %r = udiv i32 %a, 3
   ret i32 %r
 }
 
 ; Function Attrs: norecurse nounwind readnone
 define i128 @divi128li(i128) {
 ; CHECK-LABEL: divi128li:

llvm/test/CodeGen/VE/Scalar/rem.ll

; CHECK-NEXT:    b.l.t (, %s10)
   %r = srem i64 %a, 3
   ret i64 %r
 }
 
 ; Function Attrs: norecurse nounwind readnone
 define signext i32 @remi32ri(i32 signext %a) {
 ; CHECK-LABEL: remi32ri:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    divs.w.sx %s1, %s0, (62)0
+; CHECK-NEXT:    lea %s1, 1431655766
+; CHECK-NEXT:    muls.l %s1, %s0, %s1
+; CHECK-NEXT:    srl %s2, %s1, 63
+; CHECK-NEXT:    srl %s1, %s1, 32
+; CHECK-NEXT:    adds.w.sx %s1, %s1, %s2
 ; CHECK-NEXT:    muls.w.sx %s1, 3, %s1
 ; CHECK-NEXT:    subs.w.sx %s0, %s0, %s1
 ; CHECK-NEXT:    adds.w.sx %s0, %s0, (0)1
 ; CHECK-NEXT:    b.l.t (, %s10)
   %r = srem i32 %a, 3
   ret i32 %r
 }
 
; CHECK-NEXT:    b.l.t (, %s10)
   %r = urem i64 %a, 3
   ret i64 %r
 }
 
 ; Function Attrs: norecurse nounwind readnone
 define zeroext i32 @remu32ri(i32 zeroext %a) {
 ; CHECK-LABEL: remu32ri:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    divu.w %s1, %s0, (62)0
+; CHECK-NEXT:    lea %s1, -1431655765
+; CHECK-NEXT:    and %s1, %s1, (32)0
+; CHECK-NEXT:    muls.l %s1, %s0, %s1
+; CHECK-NEXT:    srl %s1, %s1, 33
 ; CHECK-NEXT:    muls.w.sx %s1, 3, %s1
 ; CHECK-NEXT:    subs.w.sx %s0, %s0, %s1
 ; CHECK-NEXT:    adds.w.zx %s0, %s0, (0)1
 ; CHECK-NEXT:    b.l.t (, %s10)
   %r = urem i32 %a, 3
   ret i32 %r
 }
 

llvm/test/CodeGen/VE/Vector/vec_divrem.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=ve -mattr=+vpu | FileCheck %s
 
 ; This would assert because VE specified that all setcc
 ; nodes (even with vector operands) return a scalar value.
 
 define <4 x i8> @udiv_by_minus_one(<4 x i8> %x) {
 ; CHECK-LABEL: udiv_by_minus_one:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    and %s0, %s0, (56)0
+; CHECK-NEXT:    lea %s4, 16843010
+; CHECK-NEXT:    muls.l %s0, %s0, %s4
+; CHECK-NEXT:    srl %s0, %s0, 32
 ; CHECK-NEXT:    and %s1, %s1, (56)0
+; CHECK-NEXT:    muls.l %s1, %s1, %s4
+; CHECK-NEXT:    srl %s1, %s1, 32
 ; CHECK-NEXT:    and %s2, %s2, (56)0
+; CHECK-NEXT:    muls.l %s2, %s2, %s4
+; CHECK-NEXT:    srl %s2, %s2, 32
 ; CHECK-NEXT:    and %s3, %s3, (56)0
-; CHECK-NEXT:    divu.w %s3, %s3, (56)0
-; CHECK-NEXT:    divu.w %s2, %s2, (56)0
-; CHECK-NEXT:    divu.w %s1, %s1, (56)0
-; CHECK-NEXT:    divu.w %s0, %s0, (56)0
+; CHECK-NEXT:    muls.l %s3, %s3, %s4
+; CHECK-NEXT:    srl %s3, %s3, 32
 ; CHECK-NEXT:    b.l.t (, %s10)
   %r = udiv <4 x i8> %x, <i8 255, i8 255, i8 255, i8 255>
   ret <4 x i8> %r
 }
 
 define <4 x i8> @urem_by_minus_one(<4 x i8> %x) {
 ; CHECK-LABEL: urem_by_minus_one:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    and %s0, %s0, (56)0
 ; CHECK-NEXT:    and %s1, %s1, (56)0
 ; CHECK-NEXT:    and %s2, %s2, (56)0
 ; CHECK-NEXT:    and %s3, %s3, (56)0
-; CHECK-NEXT:    divu.w %s4, %s3, (56)0
-; CHECK-NEXT:    muls.w.sx %s4, %s4, (56)0
-; CHECK-NEXT:    subs.w.sx %s3, %s3, %s4
-; CHECK-NEXT:    divu.w %s4, %s2, (56)0
-; CHECK-NEXT:    muls.w.sx %s4, %s4, (56)0
-; CHECK-NEXT:    subs.w.sx %s2, %s2, %s4
-; CHECK-NEXT:    divu.w %s4, %s1, (56)0
-; CHECK-NEXT:    muls.w.sx %s4, %s4, (56)0
-; CHECK-NEXT:    subs.w.sx %s1, %s1, %s4
-; CHECK-NEXT:    divu.w %s4, %s0, (56)0
+; CHECK-NEXT:    lea %s4, 16843010
+; CHECK-NEXT:    muls.l %s5, %s3, %s4
+; CHECK-NEXT:    srl %s5, %s5, 32
+; CHECK-NEXT:    muls.w.sx %s5, %s5, (56)0
+; CHECK-NEXT:    subs.w.sx %s3, %s3, %s5
+; CHECK-NEXT:    muls.l %s5, %s2, %s4
+; CHECK-NEXT:    srl %s5, %s5, 32
+; CHECK-NEXT:    muls.w.sx %s5, %s5, (56)0
+; CHECK-NEXT:    subs.w.sx %s2, %s2, %s5
+; CHECK-NEXT:    muls.l %s5, %s1, %s4
+; CHECK-NEXT:    srl %s5, %s5, 32
+; CHECK-NEXT:    muls.w.sx %s5, %s5, (56)0
+; CHECK-NEXT:    subs.w.sx %s1, %s1, %s5
+; CHECK-NEXT:    muls.l %s4, %s0, %s4
+; CHECK-NEXT:    srl %s4, %s4, 32
 ; CHECK-NEXT:    muls.w.sx %s4, %s4, (56)0
 ; CHECK-NEXT:    subs.w.sx %s0, %s0, %s4
 ; CHECK-NEXT:    b.l.t (, %s10)
   %r = urem <4 x i8> %x, <i8 255, i8 255, i8 255, i8 255>
   ret <4 x i8> %r
 }