[GlobalISel] Fix DIVREM combine from inserting a divrem before its operands' defs.

[aemerson]

Summary

In some rare corner cases where in between the div/rem pair there's a def of
the second instruction's source (but a different vreg due to the combine's
eqivalence checks), it will place the DIVREM at the first instruction's point,
causing a use-before-def. There wasn't an obvious fix that stood out to me
without doing more involved analysis than a combine should really be doing.

Fixes issue #60516

I'm open to new suggestions on how to approach this, as I'm not too happy
at bailing out here. It's not the first time we run into issues with value liveness
that the DAG world isn't affected by.

[arsenm]

This feels way more complicated than necessary but I don't really have a better suggestion

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

1202

This will miss implicit defs if a non-G_* instruction ends up in the middle somehow

[aemerson]

Check all defs.

[aemerson]

ping

[efriedma]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

1237

The reason this breaks is that you're using MI.getOperand(1).getReg(), and that doesn't dominate the insertion position, right? But OtherMI->getOperand(1).getReg() is equivalent, and if we're inserting at the position of OtherMI, it should dominate the insert position, I think?

[aemerson]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

1237

Might have misunderstood your comment, but we're not necessarily inserting at OtherMI. We have to insert at whichever of the pair is first in block order to not break use-defs. If any def of second's sources are dominated by the first, then there's no safe place to choose (without more careful analysis).

[efriedma]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

1237

We're inserting at either MI or OtherMI, right? If we're inserting at OtherMI, the operands of OtherMI dominate the insert point, so we can use the operands of OtherMI. If we're inserting at MI, the operands of MI dominate the insert point, so we can use the operands of MI. (The operands of MI are equivalent to the operands of OtherMI, so we can choose whichever operands make the dominance work.)

[aemerson]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

1237

Oh right, I see what you mean now. Yes I think that works, I'll check it does and revert/change this.

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

void CombinerHelper::applyCombineIndexedLoadStore(
   MI.eraseFromParent();
   AddrDef.eraseFromParent();
 
   LLVM_DEBUG(dbgs() << "    Combinined to indexed operation");
 }
 
 bool CombinerHelper::matchCombineDivRem(MachineInstr &MI,
                                         MachineInstr *&OtherMI) {
+  OtherMI = nullptr;
   unsigned Opcode = MI.getOpcode();
   bool IsDiv, IsSigned;
 
   switch (Opcode) {
   default:
     llvm_unreachable("Unexpected opcode!");
   case TargetOpcode::G_SDIV:
   case TargetOpcode::G_UDIV: {
bool CombinerHelper::matchCombineDivRem(MachineInstr &MI,
 
   for (auto &UseMI : MRI.use_nodbg_instructions(Src1)) {
     if (MI.getParent() == UseMI.getParent() &&
         ((IsDiv && UseMI.getOpcode() == RemOpcode) ||
          (!IsDiv && UseMI.getOpcode() == DivOpcode)) &&
         matchEqualDefs(MI.getOperand(2), UseMI.getOperand(2)) &&
         matchEqualDefs(MI.getOperand(1), UseMI.getOperand(1))) {
       OtherMI = &UseMI;
-      return true;
+      break;
     }
   }
+  if (!OtherMI)
+    return false;
 
+  // We may have a situation like this:
+  //   %4:_(s32) = G_SEXT %2:_(s1)
+  //   %5:_(s32) = G_SEXT %2:_(s1)
+  //   %6:_(s32) = G_UDIV %4:_, %5:_
+  //   %8:_(s32) = G_SEXT %2:_(s1)
+  //   %9:_(s32) = G_UREM %5:_, %8:_
+  // and choosing the insertion point as the G_UDIV will cause it to use %8
+  // before the def. We check here if any of the operands of the later
+  // instruction (i.e. one of DIV/REM that is the second in the block) are
+  // dominated by the first instruction. In this case we check if %8 is
+  // dominated by the G_UDIV and bail out if so.
+
+  SmallSet<Register, 2> RegsToCheck;
+  MachineInstr *First, *Second;
+  if (dominates(MI, *OtherMI)) {
+    First = &MI;
+    Second = OtherMI;
+  } else {
+    First = OtherMI;
+    Second = &MI;
+  }
+  RegsToCheck.insert(Second->getOperand(1).getReg());
+  RegsToCheck.insert(Second->getOperand(2).getReg());
+  for (MachineBasicBlock::iterator II = std::next(First->getIterator());
+       II != Second->getIterator(); ++II) {
+    for (auto &MO : II->defs()) {
+      if (RegsToCheck.count(MO.getReg()) && dominates(*First, *II))
         return false;
     }
+  }
+  return true;
+}
 
 void CombinerHelper::applyCombineDivRem(MachineInstr &MI,
                                         MachineInstr *&OtherMI) {
   unsigned Opcode = MI.getOpcode();
   assert(OtherMI && "OtherMI shouldn't be empty.");
 
   Register DestDivReg, DestRemReg;
   if (Opcode == TargetOpcode::G_SDIV || Opcode == TargetOpcode::G_UDIV) {
void CombinerHelper::applyCombineDivRem(MachineInstr &MI,
   if (dominates(MI, *OtherMI))
     Builder.setInstrAndDebugLoc(MI);
   else
     Builder.setInstrAndDebugLoc(*OtherMI);
 
   Builder.buildInstr(IsSigned ? TargetOpcode::G_SDIVREM
                               : TargetOpcode::G_UDIVREM,
                      {DestDivReg, DestRemReg},
                      {MI.getOperand(1).getReg(), MI.getOperand(2).getReg()});
   MI.eraseFromParent();
   OtherMI->eraseFromParent();
 }
 
 bool CombinerHelper::matchOptBrCondByInvertingCond(MachineInstr &MI,
                                                    MachineInstr *&BrCond) {
   assert(MI.getOpcode() == TargetOpcode::G_BR);
 

llvm/test/CodeGen/AArch64/GlobalISel/prelegalizer-combiner-divrem-insertpt-conflict.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -mtriple aarch64 -run-pass=aarch64-prelegalizer-combiner -global-isel -verify-machineinstrs %s -o - | FileCheck %s
+
+# Check that we don't combine to G_UDIVREM if it would cause a use-before-def
+---
+name:            test
+alignment:       4
+tracksRegLiveness: true
+body:             |
+  bb.1:
+    ; CHECK-LABEL: name: test
+    ; CHECK: [[C:%[0-9]+]]:_(s1) = G_CONSTANT i1 true
+    ; CHECK-NEXT: [[SEXT:%[0-9]+]]:_(s32) = G_SEXT [[C]](s1)
+    ; CHECK-NEXT: [[SEXT1:%[0-9]+]]:_(s32) = G_SEXT [[C]](s1)
+    ; CHECK-NEXT: [[UDIV:%[0-9]+]]:_(s32) = G_UDIV [[SEXT]], [[SEXT1]]
+    ; CHECK-NEXT: [[SEXT2:%[0-9]+]]:_(s32) = G_SEXT [[C]](s1)
+    ; CHECK-NEXT: [[UREM:%[0-9]+]]:_(s32) = G_UREM [[SEXT1]], [[SEXT2]]
+    ; CHECK-NEXT: [[TRUNC:%[0-9]+]]:_(s8) = G_TRUNC [[UREM]](s32)
+    ; CHECK-NEXT: [[ZEXT:%[0-9]+]]:_(s64) = G_ZEXT [[UDIV]](s32)
+    ; CHECK-NEXT: [[SEXT3:%[0-9]+]]:_(s64) = G_SEXT [[TRUNC]](s8)
+    ; CHECK-NEXT: [[OR:%[0-9]+]]:_(s64) = G_OR [[ZEXT]], [[SEXT3]]
+    ; CHECK-NEXT: [[TRUNC1:%[0-9]+]]:_(s32) = G_TRUNC [[OR]](s64)
+    ; CHECK-NEXT: $w0 = COPY [[TRUNC1]](s32)
+    ; CHECK-NEXT: RET_ReallyLR implicit $w0
+    %0:_(s16) = G_CONSTANT i16 0
+    %2:_(s1) = G_CONSTANT i1 true
+    %1:_(s1) = G_ICMP intpred(sge), %0(s16), %0
+    %3:_(s8) = G_SEXT %2(s1)
+    %4:_(s32) = G_SEXT %3(s8)
+    %5:_(s32) = G_SEXT %1(s1)
+    %6:_(s32) = G_UDIV %4, %5
+    %7:_(s32) = COPY %5(s32)
+    %8:_(s32) = G_SEXT %2(s1)
+    %9:_(s32) = G_UREM %7, %8
+    %10:_(s8) = G_TRUNC %9(s32)
+    %11:_(s64) = G_ZEXT %6(s32)
+    %12:_(s64) = G_SEXT %10(s8)
+    %13:_(s64) = G_OR %11, %12
+    %14:_(s32) = G_TRUNC %13(s64)
+    $w0 = COPY %14(s32)
+    RET_ReallyLR implicit $w0
+
+...
+
+# Check with the div and rem the other way around
+---
+name:            test_inverted_div_rem
+alignment:       4
+tracksRegLiveness: true
+body:             |
+  bb.1:
+    ; CHECK-LABEL: name: test_inverted_div_rem
+    ; CHECK: [[C:%[0-9]+]]:_(s1) = G_CONSTANT i1 true
+    ; CHECK-NEXT: [[SEXT:%[0-9]+]]:_(s32) = G_SEXT [[C]](s1)
+    ; CHECK-NEXT: [[SEXT1:%[0-9]+]]:_(s32) = G_SEXT [[C]](s1)
+    ; CHECK-NEXT: [[UREM:%[0-9]+]]:_(s32) = G_UREM [[SEXT]], [[SEXT1]]
+    ; CHECK-NEXT: [[SEXT2:%[0-9]+]]:_(s32) = G_SEXT [[C]](s1)
+    ; CHECK-NEXT: [[UDIV:%[0-9]+]]:_(s32) = G_UDIV [[SEXT1]], [[SEXT2]]
+    ; CHECK-NEXT: [[TRUNC:%[0-9]+]]:_(s8) = G_TRUNC [[UDIV]](s32)
+    ; CHECK-NEXT: [[ZEXT:%[0-9]+]]:_(s64) = G_ZEXT [[UREM]](s32)
+    ; CHECK-NEXT: [[SEXT3:%[0-9]+]]:_(s64) = G_SEXT [[TRUNC]](s8)
+    ; CHECK-NEXT: [[OR:%[0-9]+]]:_(s64) = G_OR [[ZEXT]], [[SEXT3]]
+    ; CHECK-NEXT: [[TRUNC1:%[0-9]+]]:_(s32) = G_TRUNC [[OR]](s64)
+    ; CHECK-NEXT: $w0 = COPY [[TRUNC1]](s32)
+    ; CHECK-NEXT: RET_ReallyLR implicit $w0
+    %0:_(s16) = G_CONSTANT i16 0
+    %2:_(s1) = G_CONSTANT i1 true
+    %1:_(s1) = G_ICMP intpred(sge), %0(s16), %0
+    %3:_(s8) = G_SEXT %2(s1)
+    %4:_(s32) = G_SEXT %3(s8)
+    %5:_(s32) = G_SEXT %1(s1)
+    %6:_(s32) = G_UREM %4, %5
+    %7:_(s32) = COPY %5(s32)
+    %8:_(s32) = G_SEXT %2(s1)
+    %9:_(s32) = G_UDIV %7, %8
+    %10:_(s8) = G_TRUNC %9(s32)
+    %11:_(s64) = G_ZEXT %6(s32)
+    %12:_(s64) = G_SEXT %10(s8)
+    %13:_(s64) = G_OR %11, %12
+    %14:_(s32) = G_TRUNC %13(s64)
+    $w0 = COPY %14(s32)
+    RET_ReallyLR implicit $w0
+
+...
+---
+name:            ok_before_first
+alignment:       4
+tracksRegLiveness: true
+body:             |
+  bb.1:
+    ; CHECK-LABEL: name: ok_before_first
+    ; CHECK: [[C:%[0-9]+]]:_(s1) = G_CONSTANT i1 true
+    ; CHECK-NEXT: [[SEXT:%[0-9]+]]:_(s32) = G_SEXT [[C]](s1)
+    ; CHECK-NEXT: [[SEXT1:%[0-9]+]]:_(s32) = G_SEXT [[C]](s1)
+    ; CHECK-NEXT: [[UDIVREM:%[0-9]+]]:_(s32), [[UDIVREM1:%[0-9]+]]:_ = G_UDIVREM [[SEXT]], [[SEXT1]]
+    ; CHECK-NEXT: [[TRUNC:%[0-9]+]]:_(s8) = G_TRUNC [[UDIVREM1]](s32)
+    ; CHECK-NEXT: [[ZEXT:%[0-9]+]]:_(s64) = G_ZEXT [[UDIVREM]](s32)
+    ; CHECK-NEXT: [[SEXT2:%[0-9]+]]:_(s64) = G_SEXT [[TRUNC]](s8)
+    ; CHECK-NEXT: [[OR:%[0-9]+]]:_(s64) = G_OR [[ZEXT]], [[SEXT2]]
+    ; CHECK-NEXT: [[TRUNC1:%[0-9]+]]:_(s32) = G_TRUNC [[OR]](s64)
+    ; CHECK-NEXT: $w0 = COPY [[TRUNC1]](s32)
+    ; CHECK-NEXT: RET_ReallyLR implicit $w0
+    %0:_(s16) = G_CONSTANT i16 0
+    %2:_(s1) = G_CONSTANT i1 true
+    %1:_(s1) = G_ICMP intpred(sge), %0(s16), %0
+    %3:_(s8) = G_SEXT %2(s1)
+    %4:_(s32) = G_SEXT %3(s8)
+    %5:_(s32) = G_SEXT %1(s1)
+    %8:_(s32) = G_SEXT %2(s1)
+    %6:_(s32) = G_UDIV %4, %5
+    %7:_(s32) = COPY %5(s32)
+    %9:_(s32) = G_UREM %7, %8
+    %10:_(s8) = G_TRUNC %9(s32)
+    %11:_(s64) = G_ZEXT %6(s32)
+    %12:_(s64) = G_SEXT %10(s8)
+    %13:_(s64) = G_OR %11, %12
+    %14:_(s32) = G_TRUNC %13(s64)
+    $w0 = COPY %14(s32)
+    RET_ReallyLR implicit $w0
+
+...