[AMDGPU] Fix DPP combiner check for exec modification

[foad]

Summary

r363675 changed the exec modification helper function, now called
execMayBeModifiedBeforeUse, so that if no UseMI is specified it checks
all instructions in the basic block, even beyond the last use. That
meant that the DPP combiner no longer worked in any basic block that
ended with a control flow instruction, and in particular it didn't work
on code sequences generated by the atomic optimizer.

Fix it by changing execMayBeModifiedBeforeUse to require UseMI and
changing the DPP combiner to check each use individually.

[vpykhtin]

I missed r363675 commit and I think the original semantics of isEXECMaskConstantBetweenDefAndUses should be restored: there should be no scan after the last use.

execMayBeModifiedBeforeUse should be called as it was originally to check all uses at once to prevent rollback.

[arsenm]

Checking all uses is unreasonable. There needs to be some search bounds to manage compile time

llvm/test/CodeGen/AMDGPU/atomic_optimizations_local_pointer.ll

203–204

Can you add some cases with multiple uses independent of the atomic optimizer?

[foad]

Try a different approach.

Reinstate the old behaviour but in a separate helper function with
limits on the number of instructions scanned, and update the atomic
optimizer tests to more consistently check that the DPP combiner is
working on them.

llvm/test/CodeGen/AMDGPU/atomic_optimizations_local_pointer.ll

203–204

See existing dpp_seq test in dpp_combine.mir.

[vpykhtin]

Matt, I'm not against using scan limiter, just about aborting the scan after the last use.

Jay, I'm ok with your patch, just a note that the prt set can be avoided if we count the number of use instructions and use the count to limit the scan.

[foad]

In D64393#1578035, @vpykhtin wrote:

Jay, I'm ok with your patch, just a note that the prt set can be avoided if we count the number of use instructions and use the count to limit the scan.

I did think of that but I wasn't confident that I could implement it correctly. Does MRI.use_nodbg_instructions() guarantee not to repeat instructions, even if one instruction has multiple uses of the register?

[vpykhtin]

Yea, I thought there is a guaranty on unique instructions, but looking into defusechain_instr_iterator I don't see how this can be true, so let's continue using the set.

[vpykhtin]

Sorry, there is a code for returnining unique instr, so we can use the count:

defusechain_instr_iterator &operator++() {          // Preincrement
      assert(Op && "Cannot increment end iterator!");
      if (ByOperand)
        advance();
      else if (ByInstr) {
        MachineInstr *P = Op->getParent();
        do {
          advance();
        } while (Op && Op->getParent() == P); // <- removes duplicates

[foad]

In D64393#1578090, @vpykhtin wrote:

Sorry, there is a code for returnining unique instr, so we can use the count:

defusechain_instr_iterator &operator++() {          // Preincrement
      assert(Op && "Cannot increment end iterator!");
      if (ByOperand)
        advance();
      else if (ByInstr) {
        MachineInstr *P = Op->getParent();
        do {
          advance();
        } while (Op && Op->getParent() == P); // <- removes duplicates

But is it guaranteed that multiple uses by a single instruction will be adjacent in the list?

[vpykhtin]

But is it guaranteed that multiple uses by a single instruction will be adjacent in the list?

I can't prove it but I think there would be no sense otherwise.

[arsenm]

llvm/lib/Target/AMDGPU/SIInstrInfo.cpp

6088

This should now be mandatory, and a reference

6102–6105

This should probably be a backwards scan, but that can be a separate change

6104–6105

Why is this erasing the use as it iterates?

llvm/lib/Target/AMDGPU/SIInstrInfo.h

1014 ↗

(On Diff #208900)

Might as well update this to use Register

1022 ↗

(On Diff #208900)

Should use Register

llvm/test/CodeGen/AMDGPU/atomic_optimizations_local_pointer.ll

203–204

They weren't catching this issue

[foad]

llvm/lib/Target/AMDGPU/SIInstrInfo.cpp

6102–6105

What's the advantage?

6104–6105

So we can exit the loop when Uses.empty().

[foad]

Address some review comments.

[foad]

I'll add tests tomorrow.

[arsenm]

llvm/lib/Target/AMDGPU/SIInstrInfo.cpp

6102–6105

I was thinking about kills, but it doesn't matter in SSA

6104–6105

I mean, this usage of a set doesn't make sense to me. Why can't you just increment a seen use count?

[foad]

Count non-debug use operands of non-debug instructions instead of using
a SmallPtrSet.

[foad]

Add a DPP combiner test that would have caught the problem.

[vpykhtin]

llvm/lib/Target/AMDGPU/SIInstrInfo.cpp

6116

Now I recall why I used the set originally - to detect use instruction fast. Matt, is there other way to detect whether the instruction use a register without scanning its operands?

[vpykhtin]

llvm/lib/Target/AMDGPU/SIInstrInfo.cpp

6116

and without scanning whether an instruction is in the use list for a register.

[foad]

llvm/lib/Target/AMDGPU/SIInstrInfo.cpp

6116

We have to scan the operands of every instruction anyway, in order to test I->modifiesRegister(AMDGPU::EXEC, TRI). Your original code did that too.

[vpykhtin]

llvm/lib/Target/AMDGPU/SIInstrInfo.cpp

6116

Good point. BTW you can probably use readsRegister instead of the loop.

[foad]

llvm/lib/Target/AMDGPU/SIInstrInfo.cpp

6116

readsRegister doesn't appear to ignore debug operands.

[vpykhtin]

I think we can submit this.

[arsenm]

llvm/lib/Target/AMDGPU/SIInstrInfo.cpp

6116

debug uses should only appear on the debug pseudo-instructions, which you already skipped with the ->isDebugInstr check

[foad]

llvm/lib/Target/AMDGPU/SIInstrInfo.cpp

6116

OK, if that is guaranteed (I wasn't sure) I could remove the !Op.isDebug() test. Do you want me to? But I still can't use readsRegister because I need to decrement NumUse multiple times if there are multiple operands that read the register.

I could also fold the check for modifying EXEC into the same loop, so that we don't have to do two separate loops over the operands of each instruction. But I don't know if it's worth it.

[vpykhtin]

llvm/lib/Target/AMDGPU/SIInstrInfo.cpp

6116

You can calculate NumUse as a number of use_nodbg_instructions in the first loop

[foad]

llvm/lib/Target/AMDGPU/SIInstrInfo.cpp

6116

We've discussed that before. It only works if use_nodbg_instructions doesn't repeat instructions, which is only true if multiple uses by the same instruction are adjacent in the use list, which I'm not sure is necessarily true.

[foad]

Remove unnecessary check for debug operands.

[vpykhtin]

llvm/lib/Target/AMDGPU/SIInstrInfo.cpp

6116

Again, there would be no sence if use_nodbg_instructions repeat instructions. Trust it and use :)

[foad]

Count instructions instead of uses.

[vpykhtin]

Looks good, thank you!

[vpykhtin]

I've found the case when execMayBeModifiedBeforeAnyUse randomly leads to a coredump, which is hard to debug. Most likely it's because an instruction beyond the end of a basic block is accessed. This means that the first loop calculates some instructions twice and I was wrong assuming use_nodbg_instructions doesn't repeat them. In fact there is no code in MachineRegisterInfo::verifyUseList that ensures that uses belonging to one instruction should be sequent in the use list nor the traces of such ordering can be found in MachineRegisterInfo::addRegOperandToUseList. I'm going to fix this code.

[foad]

In D64393#2324102, @vpykhtin wrote:

I've found the case when execMayBeModifiedBeforeAnyUse randomly leads to a coredump, which is hard to debug. Most likely it's because an instruction beyond the end of a basic block is accessed. This means that the first loop calculates some instructions twice and I was wrong assuming use_nodbg_instructions doesn't repeat them. In fact there is no code in MachineRegisterInfo::verifyUseList that ensures that uses belonging to one instruction should be sequent in the use list nor the traces of such ordering can be found in MachineRegisterInfo::addRegOperandToUseList. I'm going to fix this code.

:)

I think "Diff 6" of this patch should handle that case correctly.

llvm/lib/Target/AMDGPU/GCNDPPCombine.cpp

 
 bool GCNDPPCombine::combineDPPMov(MachineInstr &MovMI) const {
   assert(MovMI.getOpcode() == AMDGPU::V_MOV_B32_dpp);
   LLVM_DEBUG(dbgs() << "\nDPP combine: " << MovMI);
 
   auto *DstOpnd = TII->getNamedOperand(MovMI, AMDGPU::OpName::vdst);
   assert(DstOpnd && DstOpnd->isReg());
   auto DPPMovReg = DstOpnd->getReg();
-  if (execMayBeModifiedBeforeUse(*MRI, DPPMovReg, MovMI)) {
-    LLVM_DEBUG(dbgs() << "  failed: EXEC mask should remain the same"
-                         " for all uses\n");
-    return false;
-  }
 
   auto *RowMaskOpnd = TII->getNamedOperand(MovMI, AMDGPU::OpName::row_mask);
   assert(RowMaskOpnd && RowMaskOpnd->isImm());
   auto *BankMaskOpnd = TII->getNamedOperand(MovMI, AMDGPU::OpName::bank_mask);
   assert(BankMaskOpnd && BankMaskOpnd->isImm());
   const bool MaskAllLanes = RowMaskOpnd->getImm() == 0xF &&
                             BankMaskOpnd->getImm() == 0xF;
 
bool GCNDPPCombine::combineDPPMov(MachineInstr &MovMI) const {
   OrigMIs.push_back(&MovMI);
   bool Rollback = true;
   for (auto &Use : MRI->use_nodbg_operands(DPPMovReg)) {
     Rollback = true;
 
     auto &OrigMI = *Use.getParent();
     LLVM_DEBUG(dbgs() << "  try: " << OrigMI);
 
+    if (execMayBeModifiedBeforeUse(*MRI, DPPMovReg, MovMI, &OrigMI)) {
+      LLVM_DEBUG(dbgs() << "  failed: EXEC mask should remain the same"
+                 " for all uses\n");
+      break;
+    }
+
     auto OrigOp = OrigMI.getOpcode();
     if (TII->isVOP3(OrigOp)) {
       if (!TII->hasVALU32BitEncoding(OrigOp)) {
         LLVM_DEBUG(dbgs() << "  failed: VOP3 hasn't e32 equivalent\n");
         break;
       }
       // check if other than abs|neg modifiers are set (opsel for example)
       const int64_t Mask = ~(SISrcMods::ABS | SISrcMods::NEG);

llvm/lib/Target/AMDGPU/SIInstrInfo.cpp

if (!DefInst)
       return MI;
   }
   return nullptr;
 }
 
 bool llvm::execMayBeModifiedBeforeUse(const MachineRegisterInfo &MRI,
                                       unsigned VReg,
                                       const MachineInstr &DefMI,
                                       const MachineInstr *UseMI) {
   assert(MRI.isSSA() && "Must be run on SSA");
 
   auto *TRI = MRI.getTargetRegisterInfo();
   auto *DefBB = DefMI.getParent();
 
-  if (UseMI) {
-    // Don't bother searching between blocks, although it is possible this block
-    // doesn't modify exec.
-    if (UseMI->getParent() != DefBB)
-      return true;
-  } else {
-    int NumUse = 0;
-    const int MaxUseScan = 10;
-
-    for (auto &UseInst : MRI.use_nodbg_instructions(VReg)) {
-      if (UseInst.getParent() != DefBB)
-        return true;
-
-      if (NumUse++ > MaxUseScan)
-        return true;
-    }
-  }
 
   const int MaxInstScan = 20;
   int NumScan = 0;
 
   // Stop scan at the use if known.
-  auto E = UseMI ? UseMI->getIterator() : DefBB->end();
+  auto E = UseMI->getIterator();
   for (auto I = std::next(DefMI.getIterator()); I != E; ++I) {
     if (I->isDebugInstr())
       continue;
 
     if (NumScan++ > MaxInstScan)
       return true;
 
     if (I->modifiesRegister(AMDGPU::EXEC, TRI))
       return true;
   }
 
   return false;
 }

llvm/test/CodeGen/AMDGPU/atomic_optimizations_local_pointer.ll

 define amdgpu_kernel void @sub_i64_varying(i64 addrspace(1)* %out) {
 entry:
   %lane = call i32 @llvm.amdgcn.workitem.id.x()
   %zext = zext i32 %lane to i64
   %old = atomicrmw sub i64 addrspace(3)* @local_var64, i64 %zext acq_rel
   store i64 %old, i64 addrspace(1)* %out
   ret void
 }
+
+; Check that the DPP combiner works on the code generated by the atomic optimizer.
+
+; GFX8MORE-LABEL: add_i32_varying_dpp:
+; GFX8MORE: v_add_u32_dpp
+; GFX8MORE: v_add_u32_dpp
+; GFX8MORE: v_add_u32_dpp
+; GFX8MORE: v_add_u32_dpp
+; GFX8MORE: v_add_u32_dpp
+define amdgpu_kernel void @add_i32_varying_dpp() {
+  %lane = call i32 @llvm.amdgcn.workitem.id.x()
+  %old = atomicrmw add i32 addrspace(3)* @local_var32, i32 %lane acq_rel
+  ret void
+}