AMDGPU: Limit the search in finding the instruction pattern for v_swap generation.

[cfang]

Summary

Current implementation of matchSwap in SIShrinkInstructions searches the entire use_nodbg_operands set to find the possible
pattern to generate v_swap instruction. This approach will lead to a O(N^3) in compile time for SIShrinkInstructions.

But in reality, the matching pattern only exists within nearby instructions in the same basic block. This work limits the search to a maximum of
16 instructions, and has a linear compile time comsumption.

[rampitec]

LGTM

[rampitec]

I have reverted it. It has resulted in 96 lit test failures. Please run make check before posting review.

[rampitec]

Please make sure it passes llvm check tests.

[cfang]

Where are these failing LIT tests located? I did LIT tests before posting for review and also before integrating.
Maybe my check is incomplete. Thanks.

[rampitec]

In D74180#1863114, @cfang wrote:

Where are these failing LIT tests located? I did LIT tests before posting for review and also before integrating.
Maybe my check is incomplete. Thanks.

This is our main codegen tests. Didn't you check a release build?

[cfang]

Fix the LIT test failures.
(Yes, I messed up with a release build check, Thanks for catching these).

llvm/lib/Target/AMDGPU/SIShrinkInstructions.cpp

static MachineInstr* matchSwap(MachineInstr &MovT, MachineRegisterInfo &MRI,
   unsigned Xsub = Xop.getSubReg();
 
   unsigned Size = TII->getOpSize(MovT, 0) / 4;
 
   const SIRegisterInfo &TRI = TII->getRegisterInfo();
   if (!TRI.isVGPR(MRI, X))
     return nullptr;
 
-  for (MachineOperand &YTop : MRI.use_nodbg_operands(T)) {
-    if (YTop.getSubReg() != Tsub)
+  const unsigned SearchLimit = 16;
+  unsigned Count = 0;
+  for (auto Iter = std::next(MovT.getIterator()),
+            E = MovT.getParent()->instr_end();
+       Iter != E && Count < SearchLimit; ++Iter, ++Count) {
+
+    MachineInstr *MovY = &*Iter;
+    if ((MovY->getOpcode() != AMDGPU::V_MOV_B32_e32 &&
+         MovY->getOpcode() != AMDGPU::COPY) ||
+        !MovY->getOperand(1).isReg()        ||
+        MovY->getOperand(1).getReg() != T   ||
+        MovY->getOperand(1).getSubReg() != Tsub)
       continue;
 
-    MachineInstr &MovY = *YTop.getParent();
-    if ((MovY.getOpcode() != AMDGPU::V_MOV_B32_e32 &&
-         MovY.getOpcode() != AMDGPU::COPY) ||
-        MovY.getOperand(1).getSubReg() != Tsub)
-      continue;
-
-    Register Y = MovY.getOperand(0).getReg();
-    unsigned Ysub = MovY.getOperand(0).getSubReg();
+    Register Y = MovY->getOperand(0).getReg();
+    unsigned Ysub = MovY->getOperand(0).getSubReg();
 
-    if (!TRI.isVGPR(MRI, Y) || MovT.getParent() != MovY.getParent())
+    if (!TRI.isVGPR(MRI, Y))
       continue;
 
     MachineInstr *MovX = nullptr;
-    auto I = std::next(MovT.getIterator()), E = MovT.getParent()->instr_end();
-    for (auto IY = MovY.getIterator(); I != E && I != IY; ++I) {
-      if (instReadsReg(&*I, X, Xsub, TRI) ||
+    for (auto IY = MovY->getIterator(), I = std::next(MovT.getIterator());
+         I != IY; ++I) {
+      if (instReadsReg(&*I, X, Xsub, TRI)    ||
           instModifiesReg(&*I, Y, Ysub, TRI) ||
           instModifiesReg(&*I, T, Tsub, TRI) ||
           (MovX && instModifiesReg(&*I, X, Xsub, TRI))) {
         MovX = nullptr;
         break;
       }
       if (!instReadsReg(&*I, Y, Ysub, TRI)) {
         if (!MovX && instModifiesReg(&*I, X, Xsub, TRI)) {
           MovX = nullptr;
           break;
         }
         continue;
       }
       if (MovX ||
           (I->getOpcode() != AMDGPU::V_MOV_B32_e32 &&
            I->getOpcode() != AMDGPU::COPY) ||
           I->getOperand(0).getReg() != X ||
           I->getOperand(0).getSubReg() != Xsub) {
         MovX = nullptr;
         break;
       }
       MovX = &*I;
     }
 
-    if (!MovX || I == E)
+    if (!MovX)
       continue;
 
     LLVM_DEBUG(dbgs() << "Matched v_swap_b32:\n" << MovT << *MovX << MovY);
 
     for (unsigned I = 0; I < Size; ++I) {
       TargetInstrInfo::RegSubRegPair X1, Y1;
       X1 = getSubRegForIndex(X, Xsub, I, TRI, MRI);
       Y1 = getSubRegForIndex(Y, Ysub, I, TRI, MRI);
       BuildMI(*MovT.getParent(), MovX->getIterator(), MovT.getDebugLoc(),
                 TII->get(AMDGPU::V_SWAP_B32))
         .addDef(X1.Reg, 0, X1.SubReg)
         .addDef(Y1.Reg, 0, Y1.SubReg)
         .addReg(Y1.Reg, 0, Y1.SubReg)
         .addReg(X1.Reg, 0, X1.SubReg).getInstr();
     }
     MovX->eraseFromParent();
-    MovY.eraseFromParent();
+    MovY->eraseFromParent();
     MachineInstr *Next = &*std::next(MovT.getIterator());
     if (MRI.use_nodbg_empty(T))
       MovT.eraseFromParent();
     else
       Xop.setIsKill(false);
 
     return Next;
   }

llvm/test/CodeGen/AMDGPU/v_swap_b32.mir

bb.0:
     %1 = IMPLICIT_DEF
     %2.sub0 = COPY %0.sub0
     %2.sub1 = COPY %0.sub1
     %0.sub0 = COPY %1.sub0, implicit %0
     %0.sub1 = COPY %1.sub1
     %1.sub0 = COPY %2.sub0
     S_ENDPGM 0
 ...
+
+# GCN-LABEL: name: swap_exact_max_insns_apart
+# GCN: bb.0:
+# GCN-NEXT: %0:vgpr_32 = IMPLICIT_DEF
+# GCN-NEXT: %1:vgpr_32 = IMPLICIT_DEF
+# GCN-NEXT: %3:vgpr_32 = IMPLICIT_DEF
+# GCN-NEXT: %4:vgpr_32 = COPY %3
+# GCN-NEXT: %3:vgpr_32 = COPY %4
+# GCN-NEXT: %4:vgpr_32 = COPY %3
+# GCN-NEXT: %3:vgpr_32 = COPY %4
+# GCN-NEXT: %4:vgpr_32 = COPY %3
+# GCN-NEXT: %3:vgpr_32 = COPY %4
+# GCN-NEXT: %4:vgpr_32 = COPY %3
+# GCN-NEXT: %3:vgpr_32 = COPY %4
+# GCN-NEXT: %4:vgpr_32 = COPY %3
+# GCN-NEXT: %3:vgpr_32 = COPY %4
+# GCN-NEXT: %4:vgpr_32 = COPY %3
+# GCN-NEXT: %3:vgpr_32 = COPY %4
+# GCN-NEXT: %4:vgpr_32 = COPY %3
+# GCN-NEXT: %0:vgpr_32, %1:vgpr_32 = V_SWAP_B32 %1, %0, implicit $exec
+# GCN-NEXT: S_ENDPGM 0
+
+---
+name:            swap_exact_max_insns_apart
+registers:
+  - { id: 0, class: vgpr_32 }
+  - { id: 1, class: vgpr_32 }
+  - { id: 2, class: vgpr_32 }
+  - { id: 3, class: vgpr_32 }
+  - { id: 4, class: vgpr_32 }
+body:             |
+  bb.0:
+    %0 = IMPLICIT_DEF
+    %1 = IMPLICIT_DEF
+    %2 = COPY %0
+    %3 = IMPLICIT_DEF
+    %4 = COPY %3
+    %3 = COPY %4
+    %4 = COPY %3
+    %3 = COPY %4
+    %4 = COPY %3
+    %3 = COPY %4
+    %4 = COPY %3
+    %3 = COPY %4
+    %4 = COPY %3
+    %3 = COPY %4
+    %4 = COPY %3
+    %3 = COPY %4
+    %4 = COPY %3
+    %0 = COPY %1
+    %1 = COPY %2
+    S_ENDPGM 0
+...
+
+# GCN-LABEL: name: swap_too_far
+# GCN: bb.0:
+# GCN-NEXT: %0:vgpr_32 = IMPLICIT_DEF
+# GCN-NEXT: %1:vgpr_32 = IMPLICIT_DEF
+# GCN-NEXT: %2:vgpr_32 = COPY %0
+# GCN-NEXT: %3:vgpr_32 = IMPLICIT_DEF
+# GCN-NEXT: %4:vgpr_32 = COPY %3
+# GCN-NEXT: %3:vgpr_32 = COPY %4
+# GCN-NEXT: %4:vgpr_32 = COPY %3
+# GCN-NEXT: %3:vgpr_32 = COPY %4
+# GCN-NEXT: %4:vgpr_32 = COPY %3
+# GCN-NEXT: %3:vgpr_32 = COPY %4
+# GCN-NEXT: %4:vgpr_32 = COPY %3
+# GCN-NEXT: %3:vgpr_32 = COPY %4
+# GCN-NEXT: %4:vgpr_32 = COPY %3
+# GCN-NEXT: %3:vgpr_32 = COPY %4
+# GCN-NEXT: %4:vgpr_32 = COPY %3
+# GCN-NEXT: %3:vgpr_32 = COPY %4
+# GCN-NEXT: %4:vgpr_32 = COPY %3
+# GCN-NEXT: %3:vgpr_32 = COPY %4
+# GCN-NEXT: %0:vgpr_32 = COPY %1
+# GCN-NEXT: %1:vgpr_32 = COPY %2
+# GCN-NEXT: S_ENDPGM 0
+
+---
+name:            swap_too_far
+registers:
+  - { id: 0, class: vgpr_32 }
+  - { id: 1, class: vgpr_32 }
+  - { id: 2, class: vgpr_32 }
+  - { id: 3, class: vgpr_32 }
+  - { id: 4, class: vgpr_32 }
+body:             |
+  bb.0:
+    %0 = IMPLICIT_DEF
+    %1 = IMPLICIT_DEF
+    %2 = COPY %0
+    %3 = IMPLICIT_DEF
+    %4 = COPY %3
+    %3 = COPY %4
+    %4 = COPY %3
+    %3 = COPY %4
+    %4 = COPY %3
+    %3 = COPY %4
+    %4 = COPY %3
+    %3 = COPY %4
+    %4 = COPY %3
+    %3 = COPY %4
+    %4 = COPY %3
+    %3 = COPY %4
+    %4 = COPY %3
+    %3 = COPY %4
+    %0 = COPY %1
+    %1 = COPY %2
+    S_ENDPGM 0
+...