AMDGPU: Fix infinite searches in SIFixSGPRCopies

[kerbowa]

Summary

Two conditions could lead to infinite loops when processing PHI nodes in
SIFixSGPRCopies.

The first condition involves a REG_SEQUENCE that uses registers defined by both
a PHI and a COPY.

The second condition arises when a physical register is copied to a virtual
register which is then used in a PHI node. If the same virtual register is
copied to the same physical register, the result is an endless loop.

%0:sgpr_64 = COPY $sgpr0_sgpr1
%2 = PHI %0, %bb.0, %1, %bb.1
$sgpr0_sgpr1 = COPY %0

[rampitec]

llvm/lib/Target/AMDGPU/SIFixSGPRCopies.cpp

700

SmallSet maybe instead?

[nhaehnle]

Thanks for tracking that down. I agree with Stas that SmallSet should be a better choice here. Also some minor comments on the tests, apart from that looks good to me.

llvm/test/CodeGen/AMDGPU/fix-sgpr-copies.mir

70–73

You should be able to remove this and instead write %2:sgpr_64 = PHI ... below.

99–103

Analogous to above, you should be able to remove this by adding the register class constraints to the defining instruction below.

[kerbowa]

Incorporate reviewer comments.

[kerbowa]

Cleanup test.

[rampitec]

LGTM

[arsenm]

llvm/lib/Target/AMDGPU/SIFixSGPRCopies.cpp

699–702

Worklist is a SetVector already, so why does this need another set?

[kerbowa]

llvm/lib/Target/AMDGPU/SIFixSGPRCopies.cpp

699–702

Instructions are removed from the worklist. It's to avoid adding the same ones again.

llvm/lib/Target/AMDGPU/SIFixSGPRCopies.cpp

bool SIFixSGPRCopies::runOnMachineFunction(MachineFunction &MF) {
   if (MF.getTarget().getOptLevel() > CodeGenOpt::None && EnableM0Merge)
     hoistAndMergeSGPRInits(AMDGPU::M0, *MRI, TRI, *MDT, TII);
 
   return true;
 }
 
 void SIFixSGPRCopies::processPHINode(MachineInstr &MI) {
   unsigned numVGPRUses = 0;
   SetVector<const MachineInstr *> worklist;
+  SmallSet<const MachineInstr *, 4> Visited;
   worklist.insert(&MI);
+  Visited.insert(&MI);
   while (!worklist.empty()) {
     const MachineInstr *Instr = worklist.pop_back_val();
     unsigned Reg = Instr->getOperand(0).getReg();
     for (const auto &Use : MRI->use_operands(Reg)) {
       const MachineInstr *UseMI = Use.getParent();
       if (UseMI->isCopy() || UseMI->isRegSequence()) {
         if (UseMI->isCopy() &&
           UseMI->getOperand(0).getReg().isPhysical() &&
           !TRI->isSGPRReg(*MRI, UseMI->getOperand(0).getReg())) {
           numVGPRUses++;
         }
+        if (Visited.insert(UseMI).second)
           worklist.insert(UseMI);
+
         continue;
       }
 
       if (UseMI->isPHI()) {
         const TargetRegisterClass *UseRC = MRI->getRegClass(Use.getReg());
         if (!TRI->isSGPRReg(*MRI, Use.getReg()) &&
           UseRC != &AMDGPU::VReg_1RegClass)
           numVGPRUses++;

llvm/lib/Target/AMDGPU/SIInstrInfo.cpp

if (!Def)
     return;
 
   // Try to eliminate the copy if it is copying an immediate value.
   if (Def->isMoveImmediate() && DstRC != &AMDGPU::VReg_1RegClass)
     FoldImmediate(*Copy, *Def, OpReg, &MRI);
 
   bool ImpDef = Def->isImplicitDef();
   while (!ImpDef && Def && Def->isCopy()) {
+    if (Def->getOperand(1).getReg().isPhysical())
+      break;
     Def = MRI.getUniqueVRegDef(Def->getOperand(1).getReg());
     ImpDef = Def && Def->isImplicitDef();
   }
   if (!RI.isSGPRClass(DstRC) && !Copy->readsRegister(AMDGPU::EXEC, &RI) &&
       !ImpDef)
     Copy->addOperand(MachineOperand::CreateReg(AMDGPU::EXEC, false, true));
 }
 

llvm/test/CodeGen/AMDGPU/fix-sgpr-copies.mir

body:               |
 
   bb.3:
     %2:sreg_64 = PHI %0:sreg_64, %bb.1, %1:sreg_64, %bb.2
     S_CBRANCH_SCC1 %bb.7, implicit undef $scc
     S_BRANCH %bb.4
 
   bb.8:
 ...
+
+# Avoid infinite loop in SIInstrInfo::legalizeGenericOperand when checking for ImpDef.
+# GCN-LABEL: name: legalize-operand-search-each-def-once
+# GCN-NOT: sreg_64 PHI
+---
+name: legalize-operand-search-each-def-once
+tracksRegLiveness: true
+body:               |
+  bb.0:
+    successors: %bb.1, %bb.2
+    liveins: $sgpr0_sgpr1
+
+    %0:sgpr_64 = COPY $sgpr0_sgpr1
+    S_CBRANCH_VCCZ %bb.2, implicit undef $vcc
+    S_BRANCH %bb.1
+
+  bb.1:
+    %1:vreg_64 = IMPLICIT_DEF
+    S_BRANCH %bb.2
+
+  bb.2:
+    %2:sgpr_64 = PHI %0, %bb.0, %1, %bb.1
+    $sgpr0_sgpr1 = COPY %0
+...
+
+# A REG_SEQUENCE that uses registers defined by both a PHI and a COPY could
+# result in an endless search.
+# GCN-LABEL: name: process-phi-search-each-use-once
+# GCN-NOT: sreg_32 PHI
+---
+name: process-phi-search-each-use-once
+tracksRegLiveness: true
+body:               |
+  bb.0:
+    successors: %bb.1, %bb.2
+    liveins: $vgpr3
+
+    %0:vgpr_32 = COPY $vgpr3
+    S_CBRANCH_VCCZ %bb.2, implicit undef $vcc
+    S_BRANCH %bb.1
+
+  bb.1:
+    %1:sgpr_32 = IMPLICIT_DEF
+    S_BRANCH %bb.2
+
+  bb.2:
+    %2:sgpr_32 = PHI %0, %bb.0, %1, %bb.1
+    %3:vreg_64 = REG_SEQUENCE %2, %subreg.sub0, %0, %subreg.sub1
+    $vgpr3 = COPY %3.sub0
+...