[GlobalISel] support narrow G_IMPLICIT_DEF for DstSize % NarrowSize != 0

[gargaroff]

Summary

When narrowing G_IMPLICIT_DEF where the original size is not a multiple
of the narrow size, emit a smaller G_IMPLICIT_DEF and use G_ANYEXT.

To prevent a potential endless loop in the legalizer, the condition
to combine G_ANYEXT(G_IMPLICIT_DEF) is changed from isInstUnsupported
to !isInstLegal, since in this case the combine is only valid if
consequent legalization of the newly combined G_IMPLICIT_DEF does not
introduce G_ANYEXT due to narrowing.

Although this legalization for G_IMPLICIT_DEF would also be valid for
the general case, it actually caused a lot of code regressions when
tried due to superfluous COPYs and combines not getting hit anymore.

[arsenm]

I added some test cases in db3f3f0240bb3a6c6e75a547ab7c6efeca4a81ee that this should impact, can you rebase on top of that?

llvm/lib/CodeGen/GlobalISel/LegalizerHelper.cpp

754–755

I don't think casting the vector type to a scalar makes sense, and this should introduce a vector anyext

[gargaroff]

Address review comments. Rebase.

@arsenm One of the tests that you added (G_IMPLICIT_DEF s1025) produces more than 9000 lines of code before it eventually fails due to a s65600 G_MERGE_VALUES (nope, not a typo). Since I didn't think it would be feasible to have more than 18000 CHECK-lines for just one test (output slightly differs between both RUN lines), I extracted this test to an extra file and only check for the error message. I hope that is alright with you.

[gargaroff]

llvm/lib/CodeGen/GlobalISel/LegalizerHelper.cpp

754–755

Yeah that is a good point. Fixed it.

[gargaroff]

Ping

[arsenm]

llvm/lib/CodeGen/GlobalISel/LegalizerHelper.cpp

759

There's no bundle here? Why isn't this just an erase from parent?

llvm/test/CodeGen/AMDGPU/GlobalISel/legalize-implicit-def-s1025.mir

11

We should probably think about how to handle such degenerate cases, but I guess it's not critical

[gargaroff]

fix review comments

[gargaroff]

fix review comments

[gargaroff]

llvm/lib/CodeGen/GlobalISel/LegalizerHelper.cpp

759

Thanks for spotting! That was just a typo.

llvm/test/CodeGen/AMDGPU/GlobalISel/legalize-implicit-def-s1025.mir

11

If you want to I could also try and see if another legalization strategy (using G_INSERT instead of G_ANYEXT) would be preferable for this case. But the legalizer cannot possibly know which one works best for a target. Unless you let targets decide for itself (similar to how targets can override s1 constant extensions).

[gargaroff]

fix unit test after rebase

[arsenm]

llvm/lib/CodeGen/GlobalISel/LegalizerHelper.cpp

759

Should also be eraseFromParent, not merely remove

[gargaroff]

use eraseFromParent

[gargaroff]

@arsenm I know this one has been a bit messy, but is this good to go now or is there something else?

llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h

 //===-- llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h -----*- C++ -*-//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 // This file contains some helper functions which try to cleanup artifacts
bool tryFoldImplicitDef(MachineInstr &MI,
     if (MachineInstr *DefMI = getOpcodeDef(TargetOpcode::G_IMPLICIT_DEF,
                                            MI.getOperand(1).getReg(), MRI)) {
       Builder.setInstr(MI);
       Register DstReg = MI.getOperand(0).getReg();
       LLT DstTy = MRI.getType(DstReg);
 
       if (Opcode == TargetOpcode::G_ANYEXT) {
         // G_ANYEXT (G_IMPLICIT_DEF) -> G_IMPLICIT_DEF
-        if (isInstUnsupported({TargetOpcode::G_IMPLICIT_DEF, {DstTy}}))
+        if (!isInstLegal({TargetOpcode::G_IMPLICIT_DEF, {DstTy}}))
           return false;
         LLVM_DEBUG(dbgs() << ".. Combine G_ANYEXT(G_IMPLICIT_DEF): " << MI;);
         Builder.buildInstr(TargetOpcode::G_IMPLICIT_DEF, {DstReg}, {});
         UpdatedDefs.push_back(DstReg);
       } else {
         // G_[SZ]EXT (G_IMPLICIT_DEF) -> G_CONSTANT 0 because the top
         // bits will be 0 for G_ZEXT and 0/1 for the G_SEXT.
         if (isConstantUnsupported(DstTy))

llvm/lib/CodeGen/GlobalISel/LegalizerHelper.cpp

 //===-- llvm/CodeGen/GlobalISel/LegalizerHelper.cpp -----------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
LegalizerHelper::LegalizeResult LegalizerHelper::narrowScalar(MachineInstr &MI,
 
   uint64_t SizeOp0 = MRI.getType(MI.getOperand(0).getReg()).getSizeInBits();
   uint64_t NarrowSize = NarrowTy.getSizeInBits();
 
   switch (MI.getOpcode()) {
   default:
     return UnableToLegalize;
   case TargetOpcode::G_IMPLICIT_DEF: {
-    // FIXME: add support for when SizeOp0 isn't an exact multiple of
-    // NarrowSize.
-    if (SizeOp0 % NarrowSize != 0)
-      return UnableToLegalize;
+    Register DstReg = MI.getOperand(0).getReg();
+    LLT DstTy = MRI.getType(DstReg);
+
+    // If SizeOp0 is not an exact multiple of NarrowSize, emit
+    // G_ANYEXT(G_IMPLICIT_DEF). Cast result to vector if needed.
+    // FIXME: Although this would also be legal for the general case, it causes
+    //  a lot of regressions in the emitted code (superfluous COPYs, artifact
+    //  combines not being hit). This seems to be a problem related to the
+    //  artifact combiner.
+    if (SizeOp0 % NarrowSize != 0) {
+      LLT ImplicitTy = NarrowTy;
+      if (DstTy.isVector())
+        ImplicitTy = LLT::vector(DstTy.getNumElements(), ImplicitTy);
+
+      Register ImplicitReg = MIRBuilder.buildUndef(ImplicitTy).getReg(0);
+      MIRBuilder.buildAnyExt(DstReg, ImplicitReg);
+
+      MI.removeFromParent();
+      return Legalized;
+    }
+
     int NumParts = SizeOp0 / NarrowSize;
 
     SmallVector<Register, 2> DstRegs;
     for (int i = 0; i < NumParts; ++i)
-      DstRegs.push_back(
-          MIRBuilder.buildUndef(NarrowTy).getReg(0));
+      DstRegs.push_back(MIRBuilder.buildUndef(NarrowTy).getReg(0));
 
-    Register DstReg = MI.getOperand(0).getReg();
-    if(MRI.getType(DstReg).isVector())
+    if (DstTy.isVector())
       MIRBuilder.buildBuildVector(DstReg, DstRegs);
     else
       MIRBuilder.buildMerge(DstReg, DstRegs);
     MI.eraseFromParent();
     return Legalized;
   }
   case TargetOpcode::G_CONSTANT: {
     LLT Ty = MRI.getType(MI.getOperand(0).getReg());

llvm/test/CodeGen/AMDGPU/GlobalISel/legalize-implicit-def-s1025.mir

+# RUN: not --crash llc -O0 -mtriple=amdgcn-mesa-mesa3d -mcpu=tahiti -run-pass=legalizer %s -o - 2>&1 | FileCheck %s
+# RUN: not --crash llc -O0 -mtriple=amdgcn-mesa-mesa3d -mcpu=fiji -run-pass=legalizer %s -o - 2>&1 | FileCheck %s
+
+# This test is not legalizable and produces more than 9000 instructions for it
+# before it fails, including legalizer artifacts like
+# %foo:_(s65600) = G_MERGE_VALUES. Since it is not really feasible to have that
+# many CHECK-lines, only the presence of the error is checked.
+
+---
+name: test_implicit_def_s1025
+body: |
+  bb.0:
+    ; CHECK: LLVM ERROR: unable to legalize instruction: %{{[0-9]+}}:_(s65600) = G_MERGE_VALUES
+    %0:_(s1025) = G_IMPLICIT_DEF
+    %1:_(s32) = G_TRUNC %0
+    $vgpr0 = COPY %1
+...

llvm/test/CodeGen/AMDGPU/GlobalISel/legalize-implicit-def.mir

bb.0:
     ; CHECK: [[EXTRACT:%[0-9]+]]:_(s32) = G_EXTRACT [[DEF]](s1024), 0
     ; CHECK: $vgpr0 = COPY [[EXTRACT]](s32)
     %0:_(s1024) = G_IMPLICIT_DEF
     %1:_(s32) = G_EXTRACT %0, 0
     $vgpr0 = COPY %1
 ...
 
 ---
-name: test_implicit_def_s1025
-body: |
-  bb.0:
-
-    ; CHECK-LABEL: name: test_implicit_def_s1025
-    ; CHECK: [[DEF:%[0-9]+]]:_(s1025) = G_IMPLICIT_DEF
-    ; CHECK: [[TRUNC:%[0-9]+]]:_(s32) = G_TRUNC [[DEF]](s1025)
-    ; CHECK: $vgpr0 = COPY [[TRUNC]](s32)
-    %0:_(s1025) = G_IMPLICIT_DEF
-    %1:_(s32) = G_TRUNC %0
-    $vgpr0 = COPY %1
-...
-
----
 name: test_implicit_def_s1056
 body: |
   bb.0:
 
     ; CHECK-LABEL: name: test_implicit_def_s1056
-    ; CHECK: [[DEF:%[0-9]+]]:_(s1056) = G_IMPLICIT_DEF
-    ; CHECK: [[TRUNC:%[0-9]+]]:_(s32) = G_TRUNC [[DEF]](s1056)
-    ; CHECK: $vgpr0 = COPY [[TRUNC]](s32)
+    ; CHECK: [[DEF:%[0-9]+]]:_(s1024) = G_IMPLICIT_DEF
+    ; CHECK: [[UV:%[0-9]+]]:_(s32), [[UV1:%[0-9]+]]:_(s32), [[UV2:%[0-9]+]]:_(s32), [[UV3:%[0-9]+]]:_(s32), [[UV4:%[0-9]+]]:_(s32), [[UV5:%[0-9]+]]:_(s32), [[UV6:%[0-9]+]]:_(s32), [[UV7:%[0-9]+]]:_(s32), [[UV8:%[0-9]+]]:_(s32), [[UV9:%[0-9]+]]:_(s32), [[UV10:%[0-9]+]]:_(s32), [[UV11:%[0-9]+]]:_(s32), [[UV12:%[0-9]+]]:_(s32), [[UV13:%[0-9]+]]:_(s32), [[UV14:%[0-9]+]]:_(s32), [[UV15:%[0-9]+]]:_(s32), [[UV16:%[0-9]+]]:_(s32), [[UV17:%[0-9]+]]:_(s32), [[UV18:%[0-9]+]]:_(s32), [[UV19:%[0-9]+]]:_(s32), [[UV20:%[0-9]+]]:_(s32), [[UV21:%[0-9]+]]:_(s32), [[UV22:%[0-9]+]]:_(s32), [[UV23:%[0-9]+]]:_(s32), [[UV24:%[0-9]+]]:_(s32), [[UV25:%[0-9]+]]:_(s32), [[UV26:%[0-9]+]]:_(s32), [[UV27:%[0-9]+]]:_(s32), [[UV28:%[0-9]+]]:_(s32), [[UV29:%[0-9]+]]:_(s32), [[UV30:%[0-9]+]]:_(s32), [[UV31:%[0-9]+]]:_(s32) = G_UNMERGE_VALUES [[DEF]](s1024)
+    ; CHECK: [[MV:%[0-9]+]]:_(s64) = G_MERGE_VALUES [[UV]](s32), [[UV1]](s32)
+    ; CHECK: [[MV1:%[0-9]+]]:_(s64) = G_MERGE_VALUES [[UV2]](s32), [[UV3]](s32)
+    ; CHECK: [[MV2:%[0-9]+]]:_(s64) = G_MERGE_VALUES [[UV4]](s32), [[UV5]](s32)
+    ; CHECK: [[MV3:%[0-9]+]]:_(s64) = G_MERGE_VALUES [[UV6]](s32), [[UV7]](s32)
+    ; CHECK: [[MV4:%[0-9]+]]:_(s64) = G_MERGE_VALUES [[UV8]](s32), [[UV9]](s32)
+    ; CHECK: [[MV5:%[0-9]+]]:_(s64) = G_MERGE_VALUES [[UV10]](s32), [[UV11]](s32)
+    ; CHECK: [[MV6:%[0-9]+]]:_(s64) = G_MERGE_VALUES [[UV12]](s32), [[UV13]](s32)
+    ; CHECK: [[MV7:%[0-9]+]]:_(s64) = G_MERGE_VALUES [[UV14]](s32), [[UV15]](s32)
+    ; CHECK: [[MV8:%[0-9]+]]:_(s64) = G_MERGE_VALUES [[UV16]](s32), [[UV17]](s32)
+    ; CHECK: [[MV9:%[0-9]+]]:_(s64) = G_MERGE_VALUES [[UV18]](s32), [[UV19]](s32)
+    ; CHECK: [[MV10:%[0-9]+]]:_(s64) = G_MERGE_VALUES [[UV20]](s32), [[UV21]](s32)
+    ; CHECK: [[MV11:%[0-9]+]]:_(s64) = G_MERGE_VALUES [[UV22]](s32), [[UV23]](s32)
+    ; CHECK: [[MV12:%[0-9]+]]:_(s64) = G_MERGE_VALUES [[UV24]](s32), [[UV25]](s32)
+    ; CHECK: [[MV13:%[0-9]+]]:_(s64) = G_MERGE_VALUES [[UV26]](s32), [[UV27]](s32)
+    ; CHECK: [[MV14:%[0-9]+]]:_(s64) = G_MERGE_VALUES [[UV28]](s32), [[UV29]](s32)
+    ; CHECK: [[MV15:%[0-9]+]]:_(s64) = G_MERGE_VALUES [[UV30]](s32), [[UV31]](s32)
+    ; CHECK: [[DEF1:%[0-9]+]]:_(s64) = G_IMPLICIT_DEF
+    ; CHECK: [[MV16:%[0-9]+]]:_(s2112) = G_MERGE_VALUES [[MV]](s64), [[MV1]](s64), [[MV2]](s64), [[MV3]](s64), [[MV4]](s64), [[MV5]](s64), [[MV6]](s64), [[MV7]](s64), [[MV8]](s64), [[MV9]](s64), [[MV10]](s64), [[MV11]](s64), [[MV12]](s64), [[MV13]](s64), [[MV14]](s64), [[MV15]](s64), [[DEF1]](s64), [[DEF1]](s64), [[DEF1]](s64), [[DEF1]](s64), [[DEF1]](s64), [[DEF1]](s64), [[DEF1]](s64), [[DEF1]](s64), [[DEF1]](s64), [[DEF1]](s64), [[DEF1]](s64), [[DEF1]](s64), [[DEF1]](s64), [[DEF1]](s64), [[DEF1]](s64), [[DEF1]](s64), [[DEF1]](s64)
+    ; CHECK: [[TRUNC:%[0-9]+]]:_(s1056) = G_TRUNC [[MV16]](s2112)
+    ; CHECK: [[TRUNC1:%[0-9]+]]:_(s32) = G_TRUNC [[TRUNC]](s1056)
+    ; CHECK: $vgpr0 = COPY [[TRUNC1]](s32)
     %0:_(s1056) = G_IMPLICIT_DEF
     %1:_(s32) = G_TRUNC %0
     $vgpr0 = COPY %1
 ...
 
 ---
 name: test_implicit_def_s2048
 body: |

llvm/unittests/CodeGen/GlobalISel/LegalizerHelperTest.cpp

 //===- LegalizerHelperTest.cpp
 //-----------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
TEST_F(AArch64GISelMITest, CreateLibcall) {
   CHECK: BL &abort
   CHECK: ADJCALLSTACKUP 0, 0, implicit-def $sp, implicit $sp
   )";
 
   // Check
   EXPECT_TRUE(CheckMachineFunction(*MF, CheckStr)) << *MF;
 }
 
+// Test narrowing of G_IMPLICIT_DEF
+TEST_F(GISelMITest, NarrowImplicitDef) {
+  setUp();
+  if (!TM)
+    return;
+
+  DefineLegalizerInfo(A, {});
+
+  // Make sure that G_IMPLICIT_DEF can be narrowed if the original size is not a
+  // multiple of narrow size
+  LLT S32{LLT::scalar(32)};
+  LLT S48{LLT::scalar(48)};
+  LLT S64{LLT::scalar(64)};
+  LLT V2S64{{LLT::vector(2, 64)}};
+
+  auto Implicit1 = B.buildUndef(S64);
+  auto Implicit2 = B.buildUndef(S64);
+  auto Implicit3 = B.buildUndef(V2S64);
+  auto Implicit4 = B.buildUndef(V2S64);
+
+  AInfo Info(MF->getSubtarget());
+  DummyGISelObserver Observer;
+  LegalizerHelper Helper(*MF, Info, Observer, B);
+
+  // Perform Legalization
+  EXPECT_EQ(LegalizerHelper::LegalizeResult::Legalized,
+            Helper.narrowScalar(*Implicit1, 0, S48));
+  EXPECT_EQ(LegalizerHelper::LegalizeResult::Legalized,
+            Helper.narrowScalar(*Implicit2, 0, S32));
+  EXPECT_EQ(LegalizerHelper::LegalizeResult::Legalized,
+            Helper.narrowScalar(*Implicit3, 0, S48));
+  EXPECT_EQ(LegalizerHelper::LegalizeResult::Legalized,
+            Helper.narrowScalar(*Implicit4, 0, S32));
+
+  const auto *CheckStr = R"(
+  CHECK: [[DEF:%[0-9]+]]:_(s48) = G_IMPLICIT_DEF
+  CHECK: [[ANYEXT:%[0-9]+]]:_(s64) = G_ANYEXT [[DEF]]
+
+  CHECK: [[DEF:%[0-9]+]]:_(s32) = G_IMPLICIT_DEF
+  CHECK: [[DEF1:%[0-9]+]]:_(s32) = G_IMPLICIT_DEF
+  CHECK: [[MV:%[0-9]+]]:_(s64) = G_MERGE_VALUES [[DEF]]:_(s32), [[DEF1]]
+
+  CHECK: [[DEF:%[0-9]+]]:_(<2 x s48>) = G_IMPLICIT_DEF
+  CHECK: [[ANYEXT:%[0-9]+]]:_(<2 x s64>) = G_ANYEXT [[DEF]]
+
+  CHECK: [[DEF:%[0-9]+]]:_(s32) = G_IMPLICIT_DEF
+  CHECK: [[DEF1:%[0-9]+]]:_(s32) = G_IMPLICIT_DEF
+  CHECK: [[DEF2:%[0-9]+]]:_(s32) = G_IMPLICIT_DEF
+  CHECK: [[DEF3:%[0-9]+]]:_(s32) = G_IMPLICIT_DEF
+  CHECK: [[BV:%[0-9]+]]:_(<2 x s64>) = G_BUILD_VECTOR [[DEF]]:_(s32), [[DEF1]]:_(s32), [[DEF2]]:_(s32), [[DEF3]]:_(s32)
+  )";
+
+  // Check
+  EXPECT_TRUE(CheckMachineFunction(*MF, CheckStr)) << *MF;
+}
+
 } // namespace