[AMDGPU] Speedup GCNDownwardRPTracker::advanceBeforeNext

[vpykhtin]

Summary

The function makes liveness tests for the entire live register set for every instruction it passes by.
This becomes very slow on high RP regions such as ASAN enabled code.

Instead only uses of last tracked instruction should be tested and this greatly improves compilation time.

This patch revealed few bugs in SIFormMemoryClauses and PreRARematStage::sinkTriviallyRematInsts which should
be fixed first.

[arsenm]

llvm/lib/Target/AMDGPU/GCNRegPressure.cpp

360

Can you defer this until after skipDebugInstructionsForward?

387

I don't understand why LiveRegs is a map in the first place

[vpykhtin]

llvm/lib/Target/AMDGPU/GCNRegPressure.cpp

387

The map consists of pairs register:lanemask

[arsenm]

llvm/lib/Target/AMDGPU/GCNRegPressure.cpp

360

I guess that doesn't make sense.

387

Yes, but tracking it this way doesn't really make sense to me. Does this really need to be erased?

[vpykhtin]

llvm/lib/Target/AMDGPU/GCNRegPressure.cpp

360

Well it can save some time at the end of the block

387

I'm not sure: do you mean leaving zero lanemask instead of erasing?

[arsenm]

llvm/lib/Target/AMDGPU/GCNRegPressure.cpp

387

Yes (although I guess you aren't really changing the behavior here)

[vpykhtin]

llvm/lib/Target/AMDGPU/GCNRegPressure.cpp

387

It would require checking all dependent code and I don't think it makes big impact as a register is deleted by the iterator

[arsenm]

LGTM (still not sure about the debug instr handling)

[vpykhtin]

• Rebased.
• Replaced collectVirtualRegUses with operand walk.
• Replaced asserts with llvm_unreachable.

[arsenm]

llvm/lib/Target/AMDGPU/GCNRegPressure.cpp

377–378

Might as well use SmallSetVector?

[vpykhtin]

llvm/lib/Target/AMDGPU/GCNRegPressure.cpp

377–378

It's only used to avoid visiting already seen registers, so this is more like a set, not vector. I'm just not sure if it worth to use some kind of hashing sets here because the number of registers is usually small and it seems it may be faster to use just plain vector. I don't have strong opinion here, however.

[arsenm]

llvm/lib/Target/AMDGPU/GCNRegPressure.cpp

377–378

Then SmallSet or SmallSet vector. Both do the linear scan when the set is small

[vpykhtin]

• Replaced SmallVector with SmallSet.

[foad]

I'm now hitting an UNREACHABLE "register isn't live" in this somewhat reduced test case. Can you investigate/fix/revert as appropriate please? Thanks!

; RUN: llc -march=amdgcn -mcpu=gfx900 < %s

declare void @llvm.amdgcn.kill(i1)
declare <4 x float> @llvm.amdgcn.image.sample.2d.v4f32.f32(i32 immarg, float, float, <8 x i32>, <4 x i32>, i1 immarg, i32 immarg, i32 immarg)
declare <2 x half> @llvm.amdgcn.cvt.pkrtz(float, float)
declare void @llvm.amdgcn.exp.compr.v2f16(i32 immarg, i32 immarg, <2 x half>, <2 x half>, i1 immarg, i1 immarg)

define amdgpu_ps void @_amdgpu_ps_main(float %arg) {
bb:
  %i = fcmp olt float %arg, 0.000000e+00
  br i1 %i, label %bb5, label %bb1

bb1:
  %i2 = call <4 x float> @llvm.amdgcn.image.sample.2d.v4f32.f32(i32 15, float 0.000000e+00, float %arg, <8 x i32> zeroinitializer, <4 x i32> zeroinitializer, i1 false, i32 0, i32 0)
  %i3 = extractelement <4 x float> %i2, i64 1
  %i4 = extractelement <4 x float> %i2, i64 0
  br label %bb6

bb5:
  call void @llvm.amdgcn.kill(i1 false)
  br label %bb6

bb6:
  %i7 = phi float [ 0.000000e+00, %bb5 ], [ %i3, %bb1 ]
  %i8 = phi float [ 0.000000e+00, %bb5 ], [ 1.000000e+00, %bb1 ]
  %i9 = phi float [ undef, %bb5 ], [ %i4, %bb1 ]
  %i10 = call <2 x half> @llvm.amdgcn.cvt.pkrtz(float 0.000000e+00, float %i7)
  %i11 = call <2 x half> @llvm.amdgcn.cvt.pkrtz(float %i8, float %i9)
  call void @llvm.amdgcn.exp.compr.v2f16(i32 0, i32 0, <2 x half> %i10, <2 x half> %i11, i1 false, i1 false)
  ret void
}

[vpykhtin]

This patch depends on https://reviews.llvm.org/D136918 fix.

[vpykhtin]

• added regression test.
• rebased after the fix a999669982d0: [AMDGPU] Scheduler: fix RP calculation for a MBB with one successor

[arsenm]

llvm/test/CodeGen/AMDGPU/scheduler-rp-calc-one-successor-two-predecessors-bug.ll

2 ↗

(On Diff #503732)

Include generated checks?

[arsenm]

LGTM with test checks

[vpykhtin]

• added generated checks.

llvm/lib/Target/AMDGPU/GCNRegPressure.cpp

 //===- GCNRegPressure.cpp -------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 ///
bool GCNDownwardRPTracker::reset(const MachineInstr &MI,
   if (NextMI == MBBEnd)
     return false;
   GCNRPTracker::reset(*NextMI, LiveRegsCopy, false);
   return true;
 }
 
 bool GCNDownwardRPTracker::advanceBeforeNext() {
   assert(MRI && "call reset first");
+  if (!LastTrackedMI)
+    return true;
+
+  auto const RegUses = collectVirtualRegUses(*LastTrackedMI, LIS, *MRI);
+  // each RegUnit is unique in RegUses
 
   NextMI = skipDebugInstructionsForward(NextMI, MBBEnd);
   if (NextMI == MBBEnd)
     return false;
 
   SlotIndex SI = LIS.getInstructionIndex(*NextMI).getBaseIndex();
   assert(SI.isValid());
 
   // Remove dead registers or mask bits.
-  for (auto &It : LiveRegs) {
-    const LiveInterval &LI = LIS.getInterval(It.first);
+  for (auto &U : RegUses) {
+    const LiveInterval &LI = LIS.getInterval(U.RegUnit);
     if (LI.hasSubRanges()) {
+      auto It = LiveRegs.end();
       for (const auto &S : LI.subranges()) {
         if (!S.liveAt(SI)) {
-          auto PrevMask = It.second;
-          It.second &= ~S.LaneMask;
-          CurPressure.inc(It.first, PrevMask, It.second, *MRI);
+          if (It == LiveRegs.end()) {
+            It = LiveRegs.find(U.RegUnit);
+            assert(It != LiveRegs.end());
+          }
+          auto PrevMask = It->second;
+          It->second &= ~S.LaneMask;
+          CurPressure.inc(U.RegUnit, PrevMask, It->second, *MRI);
         }
       }
+      if (It != LiveRegs.end() && It->second.none())
+        LiveRegs.erase(It);
     } else if (!LI.liveAt(SI)) {
-      auto PrevMask = It.second;
-      It.second = LaneBitmask::getNone();
-      CurPressure.inc(It.first, PrevMask, It.second, *MRI);
+      auto It = LiveRegs.find(U.RegUnit);
+      assert(It != LiveRegs.end());
+      CurPressure.inc(U.RegUnit, It->second, LaneBitmask::getNone(), *MRI);
+      LiveRegs.erase(It);
     }
-    if (It.second.none())
-      LiveRegs.erase(It.first);
   }
 
   MaxPressure = max(MaxPressure, CurPressure);
 
   return true;
 }
 
 void GCNDownwardRPTracker::advanceToNext() {