GlobalISel: Try to combine G_[SU]DIV and G_[SU]REM

[cdevadas]

Summary

It is good to have a combined divrem instruction when the
div and rem are computed from identical input operands.
Some targets can lower them through a single expansion that
computes both division and remainder. It effectively reduces
the number of instructions than individually expanding them.

[arsenm]

The legalizer should also get the code to split this back into the separate opcodes

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

944

This needs to have some kind of legalization check. We should only do this if either the combined divrem is legal or legalizable, or before legaliation

946–948

This can probably be an assert, the opcode should come from the tablegen opcode list

974

Should not construct single use MIRBuilders. There should be one available in the combiner state

llvm/lib/Target/AMDGPU/AMDGPUPreLegalizerCombiner.cpp

72–76

Should be called by the generic tablegen code in include/llvm/Target/GlobalISel/Combine.td

llvm/test/CodeGen/AMDGPU/GlobalISel/prelegalizer-combiner-divrem.mir

4

Should add some vector tests. Also cases with other uses, and negative cases with mismatched signed/unsigned pairs

[paquette]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

946

Maybe something like this?

switch(Opcode) {
  default:
     llvm_unreachable("Unexpected opcode!");
  case TargetOpcode::G_SDIV:
  case TargetOpcode::G_UDIV:
      IsSigned = Opcode == TargetOpcode::G_SDIV;
      IsDiv = true;
      break;
  case TargetOpcode::G_SREM:
  case TargetOpcode::G_UREM:
     ...
}

955

Why not use Opcode? If it's a div, then Opcode == DivOpcode. If it's a rem, then Opcode == RemOpcode.

977

This part should go in a MatchInfo parameter like in the other combines. That should be passed along to an apply function which should perform the actual combine.

984

I think this should go in an applyCombineDivRem function like the other combines.

[cdevadas]

I am making it a generic pattern that comes from the Combine.td. Will update the patch soon.

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

955

Based on the signness of MI, here I am trying to get the other opcode to match.
And the check below matches the (sdiv, srem) or (udiv, urem) pair irrespective of their position.

[cdevadas]

Addressed the review comments:

Made the combiner pattern generic.
Added the necessary legalization check.
Legalized the G_[SU]DIVREM instruction.
Added vector tests and some negative tests.
Added two new tests for post-legalizer and legalizer-helper.

[arsenm]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

1006–1007

Should just use the regular getVRegDef

1026

I'm worried about what happens if multiple div/rem users exist. Can you add some tests for that?

[paquette]

Can you add an entry for G_SDIVREM and G_UDIVREM to docs/GlobalISel/GenericOpcode.rst?

llvm/lib/CodeGen/GlobalISel/LegalizerHelper.cpp

6277 ↗

(On Diff #322343)

Can the Legalizer changes come in a follow-up patch?

[cdevadas]

I will make an entry for the new opcodes in docs/GlobalISel/GenericOpcode.rst

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

1026

This patch currently performs a one-to-one match. It doesn't look for multiple div/rem users.
For example, it won't optimally match the following pattern:
G_SDIV x, y, G_SREM x, y and an extra G_SDIV x, y
The first div/rem pair will be combined and the second div will be retained.
Instead, it should have generated d, r = G_SDIVREM x, y ; replace all users of the second G_SDIV with 'd' and then delete the extra G_SDIV as well.
I will rework this part.

llvm/lib/CodeGen/GlobalISel/LegalizerHelper.cpp

6277 ↗

(On Diff #322343)

I thought about it initially. But it makes more sense to legalize the operations along with the patch that introduces the opcodes.

[cdevadas]

Improved the matcher function to identify a div/rem pair and any number of matching div and/or rem instructions.
Documented the new instructions in docs/GlobalISel/GenericOpcode.rst

[arsenm]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

1026

I don't think this should be collecting a vector of other instructions and looking for redundant div/rems. It just needs to not crash if one of these extras exist

[cdevadas]

Reverting the recent changes to combine any matching extra div and rem instructions alongside the divrem instruction. The presence of the extra instruction shouldn't crash. Added tests to ensure that.

[cdevadas]

Used MachineInstr as the MatchInfo instead of the Register.
With this, the other matching MI will be directly available in the apply function.

[arsenm]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

1019

I still suspect something is wrong with the insertion. I don't believe it's guaranteed that the first instruction you find will dominate the second, so you don't know where to place the insert point.

llvm/test/CodeGen/AMDGPU/GlobalISel/prelegalizer-combiner-divrem.mir

382–383

You can shorten the test by just copying tuple registers, we just lower arguments with the separate copies

[cdevadas]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

1019

The instructions are visited in the top-down order and MI will always dominate the otherMI.

[cdevadas]

Addressed the review comments:
Used the dominance check to find the Insertion point.
Added a negative test when the dominance check fails to identify the insertion point.
Simplified the vector tests.

[arsenm]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

1019

The combiner visits bottom up.

Actually if you check that these are in the same block, you can just use OtherMI as the insert point

1025

I'd rather keep all legality checks in the match function. But also I realized it should work if you check if the parent blocks are the same and then you can assume otherMI is earlier

[cdevadas]

The div/rem pair coming from different BB will have many scenarios that can complicate the match/apply functions and it is beyond the scope of the Combiner.
I will limit the pattern to match it for the pair coming from the same BB.

[cdevadas]

Match the div & rem only when they are from the same Basic Block.

[cdevadas]

ping

llvm/include/llvm/CodeGen/GlobalISel/CombinerHelper.h

public:
 
   bool matchSextTruncSextLoad(MachineInstr &MI);
   bool applySextTruncSextLoad(MachineInstr &MI);
 
   /// Match sext_inreg(load p), imm -> sextload p
   bool matchSextInRegOfLoad(MachineInstr &MI, std::tuple<Register, unsigned> &MatchInfo);
   bool applySextInRegOfLoad(MachineInstr &MI, std::tuple<Register, unsigned> &MatchInfo);
 
+  /// Try to combine G_[SU]DIV and G_[SU]REM into a single G_[SU]DIVREM
+  /// when their source operands are identical.
+  bool tryCombineDivRem(MachineInstr &MI);
+
   /// If a brcond's true block is not the fallthrough, make it so by inverting
   /// the condition and swapping operands.
   bool matchOptBrCondByInvertingCond(MachineInstr &MI);
   void applyOptBrCondByInvertingCond(MachineInstr &MI);
 
   /// If \p MI is G_CONCAT_VECTORS, try to combine it.
   /// Returns true if MI changed.
   /// Right now, we support:

llvm/include/llvm/Support/TargetOpcodes.def

 HANDLE_TARGET_OPCODE(G_UDIV)
 
 // Generic signed remainder instruction.
 HANDLE_TARGET_OPCODE(G_SREM)
 
 // Generic unsigned remainder instruction.
 HANDLE_TARGET_OPCODE(G_UREM)
 
+// Generic signed divrem instruction.
+HANDLE_TARGET_OPCODE(G_SDIVREM)
+
+// Generic unsigned divrem instruction.
+HANDLE_TARGET_OPCODE(G_UDIVREM)
+
 /// Generic bitwise and instruction.
 HANDLE_TARGET_OPCODE(G_AND)
 
 /// Generic bitwise or instruction.
 HANDLE_TARGET_OPCODE(G_OR)
 
 /// Generic bitwise exclusive-or instruction.
 HANDLE_TARGET_OPCODE(G_XOR)

llvm/include/llvm/Target/GenericOpcodes.td

 // Generic unsigned remainder.
 def G_UREM : GenericInstruction {
   let OutOperandList = (outs type0:$dst);
   let InOperandList = (ins type0:$src1, type0:$src2);
   let hasSideEffects = false;
   let isCommutable = false;
 }
 
+// Generic signed division and remainder.
+def G_SDIVREM : GenericInstruction {
+  let OutOperandList = (outs type0:$div, type0:$rem);
+  let InOperandList = (ins type0:$src1, type0:$src2);
+  let hasSideEffects = false;
+  let isCommutable = false;
+}
+
+// Generic unsigned division and remainder.
+def G_UDIVREM : GenericInstruction {
+  let OutOperandList = (outs type0:$div, type0:$rem);
+  let InOperandList = (ins type0:$src1, type0:$src2);
+  let hasSideEffects = false;
+  let isCommutable = false;
+}
+
 // Generic bitwise and.
 def G_AND : GenericInstruction {
   let OutOperandList = (outs type0:$dst);
   let InOperandList = (ins type0:$src1, type0:$src2);
   let hasSideEffects = false;
   let isCommutable = true;
 }
 

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

void CombinerHelper::applyCombineIndexedLoadStore(
   MIB.addUse(MatchInfo.Offset);
   MIB.addImm(MatchInfo.IsPre);
   MI.eraseFromParent();
   AddrDef.eraseFromParent();
 
   LLVM_DEBUG(dbgs() << "    Combinined to indexed operation");
 }
 
+bool CombinerHelper::tryCombineDivRem(MachineInstr &MI) {
+  unsigned Opcode = MI.getOpcode();
+  if (Opcode != TargetOpcode::G_SDIV && Opcode != TargetOpcode::G_SREM &&
+      Opcode != TargetOpcode::G_UDIV && Opcode != TargetOpcode::G_UREM)
+    return false;
+
+  bool IsDiv = Opcode == TargetOpcode::G_SDIV || Opcode == TargetOpcode::G_UDIV;
+  bool IsSigned =
+      Opcode == TargetOpcode::G_SDIV || Opcode == TargetOpcode::G_SREM;
+  Register Src1 = MI.getOperand(1).getReg();
+  Register Src2 = MI.getOperand(2).getReg();
+  unsigned DivOpcode = IsSigned ? TargetOpcode::G_SDIV : TargetOpcode::G_UDIV;
+  unsigned RemOpcode = IsSigned ? TargetOpcode::G_SREM : TargetOpcode::G_UREM;
+
+  // Combine:
+  //   %div:_ = G_[SU]DIV %src1:_, %src2:_
+  //   %rem:_ = G_[SU]REM %src1:_, %src2:_
+  // into:
+  //  %div:_, %rem:_ = G_[SU]DIVREM %src1:_, %src2:_
+
+  // Combine:
+  //   %rem:_ = G_[SU]REM %src1:_, %src2:_
+  //   %div:_ = G_[SU]DIV %src1:_, %src2:_
+  // into:
+  //  %div:_, %rem:_ = G_[SU]DIVREM %src1:_, %src2:_
+
+  for (auto &UseMI : MRI.use_nodbg_instructions(Src1)) {
+    if (((IsDiv && UseMI.getOpcode() == RemOpcode) ||
+         (!IsDiv && UseMI.getOpcode() == DivOpcode)) &&
+        matchEqualDefs(MI.getOperand(2), UseMI.getOperand(2))) {
+      MachineIRBuilder MIRBuilder(MI);
+      Register DestDivReg, DestRemReg;
+      if (IsDiv) {
+        DestDivReg = MI.getOperand(0).getReg();
+        DestRemReg = UseMI.getOperand(0).getReg();
+      } else {
+        DestDivReg = UseMI.getOperand(0).getReg();
+        DestRemReg = MI.getOperand(0).getReg();
+      }
+
+      MIRBuilder.buildInstr(IsSigned ? TargetOpcode::G_SDIVREM
+                                     : TargetOpcode::G_UDIVREM,
+                            {DestDivReg, DestRemReg}, {Src1, Src2});
+      MI.eraseFromParent();
+      UseMI.eraseFromParent();
+
+      return true;
+    }
+  }
+
+  return false;
+}
+
 bool CombinerHelper::matchOptBrCondByInvertingCond(MachineInstr &MI) {
   if (MI.getOpcode() != TargetOpcode::G_BR)
     return false;
 
   // Try to match the following:
   // bb1:
   //   G_BRCOND %c1, %bb2
   //   G_BR %bb3
   // bb2:
   // ...
   // bb3:
 
   // The above pattern does not have a fall through to the successor bb2, always
   // resulting in a branch no matter which path is taken. Here we try to find
   // and replace that pattern with conditional branch to bb3 and otherwise
   // fallthrough to bb2. This is generally better for branch predictors.
 
   MachineBasicBlock *MBB = MI.getParent();
   MachineBasicBlock::iterator BrIt(MI);
   if (BrIt == MBB->begin())
     return false;
   assert(std::next(BrIt) == MBB->end() && "expected G_BR to be a terminator");
 
   MachineInstr *BrCond = &*std::prev(BrIt);
   if (BrCond->getOpcode() != TargetOpcode::G_BRCOND)
     return false;
 
   // Check that the next block is the conditional branch target. Also make sure
   // that it isn't the same as the G_BR's target (otherwise, this will loop.)
   MachineBasicBlock *BrCondTarget = BrCond->getOperand(1).getMBB();
   return BrCondTarget != MI.getOperand(0).getMBB() &&
          MBB->isLayoutSuccessor(BrCondTarget);
 }
 
 void CombinerHelper::applyOptBrCondByInvertingCond(MachineInstr &MI) {
   MachineBasicBlock *BrTarget = MI.getOperand(0).getMBB();
   MachineBasicBlock::iterator BrIt(MI);
   MachineInstr *BrCond = &*std::prev(BrIt);

llvm/lib/Target/AMDGPU/AMDGPUPreLegalizerCombiner.cpp

bool AMDGPUPreLegalizerCombinerInfo::combine(GISelChangeObserver &Observer,
   if (Generated.tryCombineAll(Observer, MI, B, Helper))
     return true;
 
   switch (MI.getOpcode()) {
   case TargetOpcode::G_CONCAT_VECTORS:
     return Helper.tryCombineConcatVectors(MI);
   case TargetOpcode::G_SHUFFLE_VECTOR:
     return Helper.tryCombineShuffleVector(MI);
+  case TargetOpcode::G_SDIV:
+  case TargetOpcode::G_SREM:
+  case TargetOpcode::G_UDIV:
+  case TargetOpcode::G_UREM:
+    return Helper.tryCombineDivRem(MI);
   }
 
   return false;
 }
 
 #define AMDGPUPRELEGALIZERCOMBINERHELPER_GENCOMBINERHELPER_CPP
 #include "AMDGPUGenPreLegalizeGICombiner.inc"
 #undef AMDGPUPRELEGALIZERCOMBINERHELPER_GENCOMBINERHELPER_CPP

llvm/test/CodeGen/AArch64/GlobalISel/legalizer-info-validation.mir

 # DEBUG-NEXT: .. the first uncovered type index: 1, OK
 # DEBUG-NEXT: .. the first uncovered imm index: 0, OK
 #
 # DEBUG-NEXT: G_UREM (opcode {{[0-9]+}}): 1 type index, 0 imm indices
 # DEBUG-NEXT: .. opcode {{[0-9]+}} is aliased to {{[0-9]+}}
 # DEBUG-NEXT: .. the first uncovered type index: 1, OK
 # DEBUG-NEXT: .. the first uncovered imm index: 0, OK
 #
+# DEBUG-NEXT: G_SDIVREM (opcode {{[0-9]+}}): 1 type index, 0 imm indices
+# DEBUG-NEXT: .. type index coverage check SKIPPED: no rules defined
+# DEBUG-NEXT: .. imm index coverage check SKIPPED: no rules defined
+#
+# DEBUG-NEXT: G_UDIVREM (opcode {{[0-9]+}}): 1 type index, 0 imm indices
+# DEBUG-NEXT: .. type index coverage check SKIPPED: no rules defined
+# DEBUG-NEXT: .. imm index coverage check SKIPPED: no rules defined
+#
 # DEBUG-NEXT: G_AND (opcode {{[0-9]+}}): 1 type index, 0 imm indices
 # DEBUG-NEXT: .. opcode {{[0-9]+}} is aliased to {{[0-9]+}}
 # DEBUG-NEXT: .. the first uncovered type index: 1, OK
 # DEBUG-NEXT: .. the first uncovered imm index: 0, OK
 #
 # DEBUG-NEXT: G_OR (opcode {{[0-9]+}}): 1 type index, 0 imm indices
 # DEBUG-NEXT: .. opcode {{[0-9]+}} is aliased to {{[0-9]+}}
 # DEBUG-NEXT: .. the first uncovered type index: 1, OK

llvm/test/CodeGen/AMDGPU/GlobalISel/prelegalizer-combiner-divrem.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -global-isel -mtriple=amdgcn-amd-amdhsa -mcpu=gfx900 -run-pass=amdgpu-prelegalizer-combiner -verify-machineinstrs -o - %s | FileCheck %s
+
+---
+name: test_sdiv_srem
+body: |
+  bb.0:
+    liveins: $vgpr0, $vgpr1, $vgpr2_vgpr3, $vgpr4_vgpr5
+    ; CHECK-LABEL: name: test_sdiv_srem
+    ; CHECK: %src1:_(s32) = COPY $vgpr0
+    ; CHECK: %src2:_(s32) = COPY $vgpr1
+    ; CHECK: %ptr1:_(p1) = COPY $vgpr2_vgpr3
+    ; CHECK: %ptr2:_(p1) = COPY $vgpr4_vgpr5
+    ; CHECK: %div:_(s32), %rem:_ = G_SDIVREM %src1, %src2
+    ; CHECK: G_STORE %div(s32), %ptr1(p1) :: (store 4, addrspace 1)
+    ; CHECK: G_STORE %rem(s32), %ptr2(p1) :: (store 4, addrspace 1)
+    %src1:_(s32) = COPY $vgpr0
+    %src2:_(s32) = COPY $vgpr1
+    %ptr1:_(p1) = COPY $vgpr2_vgpr3
+    %ptr2:_(p1) = COPY $vgpr4_vgpr5
+    %div:_(s32) = G_SDIV %src1:_(s32), %src2:_(s32)
+    G_STORE %div:_(s32), %ptr1:_(p1) :: (store 4, addrspace 1, align 4)
+    %rem:_(s32) = G_SREM %src1:_(s32), %src2:_(s32)
+    G_STORE %rem:_(s32), %ptr2:_(p1) :: (store 4, addrspace 1, align 4)
+...
+---
+name: test_srem_sdiv
+body: |
+  bb.0:
+    liveins: $vgpr0, $vgpr1, $vgpr2_vgpr3, $vgpr4_vgpr5
+    ; CHECK-LABEL: name: test_srem_sdiv
+    ; CHECK: %src1:_(s32) = COPY $vgpr0
+    ; CHECK: %src2:_(s32) = COPY $vgpr1
+    ; CHECK: %ptr1:_(p1) = COPY $vgpr2_vgpr3
+    ; CHECK: %ptr2:_(p1) = COPY $vgpr4_vgpr5
+    ; CHECK: %div:_(s32), %rem:_ = G_SDIVREM %src1, %src2
+    ; CHECK: G_STORE %rem(s32), %ptr1(p1) :: (store 4, addrspace 1)
+    ; CHECK: G_STORE %div(s32), %ptr2(p1) :: (store 4, addrspace 1)
+    %src1:_(s32) = COPY $vgpr0
+    %src2:_(s32) = COPY $vgpr1
+    %ptr1:_(p1) = COPY $vgpr2_vgpr3
+    %ptr2:_(p1) = COPY $vgpr4_vgpr5
+    %rem:_(s32) = G_SREM %src1:_(s32), %src2:_(s32)
+    G_STORE %rem:_(s32), %ptr1:_(p1) :: (store 4, addrspace 1, align 4)
+    %div:_(s32) = G_SDIV %src1:_(s32), %src2:_(s32)
+    G_STORE %div:_(s32), %ptr2:_(p1) :: (store 4, addrspace 1, align 4)
+...
+---
+name: test_udiv_urem
+body: |
+  bb.0:
+    liveins: $vgpr0, $vgpr1, $vgpr2_vgpr3, $vgpr4_vgpr5
+    ; CHECK-LABEL: name: test_udiv_urem
+    ; CHECK: %src1:_(s32) = COPY $vgpr0
+    ; CHECK: %src2:_(s32) = COPY $vgpr1
+    ; CHECK: %ptr1:_(p1) = COPY $vgpr2_vgpr3
+    ; CHECK: %ptr2:_(p1) = COPY $vgpr4_vgpr5
+    ; CHECK: %div:_(s32), %rem:_ = G_UDIVREM %src1, %src2
+    ; CHECK: G_STORE %div(s32), %ptr1(p1) :: (store 4, addrspace 1)
+    ; CHECK: G_STORE %rem(s32), %ptr2(p1) :: (store 4, addrspace 1)
+    %src1:_(s32) = COPY $vgpr0
+    %src2:_(s32) = COPY $vgpr1
+    %ptr1:_(p1) = COPY $vgpr2_vgpr3
+    %ptr2:_(p1) = COPY $vgpr4_vgpr5
+    %div:_(s32) = G_UDIV %src1:_(s32), %src2:_(s32)
+    G_STORE %div:_(s32), %ptr1:_(p1) :: (store 4, addrspace 1, align 4)
+    %rem:_(s32) = G_UREM %src1:_(s32), %src2:_(s32)
+    G_STORE %rem:_(s32), %ptr2:_(p1) :: (store 4, addrspace 1, align 4)
+...
+---
+name: test_urem_udiv
+body: |
+  bb.0:
+    liveins: $vgpr0, $vgpr1, $vgpr2_vgpr3, $vgpr4_vgpr5
+    ; CHECK-LABEL: name: test_urem_udiv
+    ; CHECK: %src1:_(s32) = COPY $vgpr0
+    ; CHECK: %src2:_(s32) = COPY $vgpr1
+    ; CHECK: %ptr1:_(p1) = COPY $vgpr2_vgpr3
+    ; CHECK: %ptr2:_(p1) = COPY $vgpr4_vgpr5
+    ; CHECK: %div:_(s32), %rem:_ = G_UDIVREM %src1, %src2
+    ; CHECK: G_STORE %rem(s32), %ptr1(p1) :: (store 4, addrspace 1)
+    ; CHECK: G_STORE %div(s32), %ptr2(p1) :: (store 4, addrspace 1)
+    %src1:_(s32) = COPY $vgpr0
+    %src2:_(s32) = COPY $vgpr1
+    %ptr1:_(p1) = COPY $vgpr2_vgpr3
+    %ptr2:_(p1) = COPY $vgpr4_vgpr5
+    %rem:_(s32) = G_UREM %src1:_(s32), %src2:_(s32)
+    G_STORE %rem:_(s32), %ptr1:_(p1) :: (store 4, addrspace 1, align 4)
+    %div:_(s32) = G_UDIV %src1:_(s32), %src2:_(s32)
+    G_STORE %div:_(s32), %ptr2:_(p1) :: (store 4, addrspace 1, align 4)
+...