[AMDGPU] Speedup SIFormMemoryClauses live-in register set calculation

[vpykhtin]

Summary

This patch uses the same approach used in GCNScheduleDAGMILive::getBBLiveInMap,
getLiveRegMap has complexity O(NumVirtRegs * averageLiveRangeSegmentsPerReg * lg(NumBB))

[vpykhtin]

rebase

[arsenm]

llvm/lib/Target/AMDGPU/SIFormMemoryClauses.cpp

280

You seem to be assuming a single clause per block. I'd expect to handle this a full clause in a time, within a single block.

[vpykhtin]

llvm/lib/Target/AMDGPU/SIFormMemoryClauses.cpp

280

Not quite, I just compute the live-in set for the first clause per BB to reset the RPTracker, then it is advanced to the next clause.

[rampitec]

LGTM

[arsenm]

llvm/lib/Target/AMDGPU/SIFormMemoryClauses.cpp

280

Can you do this per block, instead of calculating this for every block?

[vpykhtin]

llvm/lib/Target/AMDGPU/SIFormMemoryClauses.cpp

280

This is the whole point of doing that all at once:

1. Slot indexes of all clauses first instructions are collected and sorted.
2. For every virtual register's LiveRange we have two sorted sequences: Segments and SlotIndexes. We need to determine

which of SlotIndexes fall into Segments of the virtual register - that would mean the register is live at those SlotIndexes.

3. Since both sequences are sorted we progressively use two-way binary search: either SlotIndex that is contained by the Segment, or Segment containing the SlotIndex.

I now realize the complexity is not what I thought before, it should be (per register):

O( min ( NumSegments * lg(NumSlotIndexes), NumSlotIndexes * lg(NumSegments) )

See getLiveRegMap, LiveRange::findIndexesLiveAt.

[vpykhtin]

llvm/lib/Target/AMDGPU/SIFormMemoryClauses.cpp

280

Sorry I mean first instruction of a first clause per BB, following clauses are processed using 'advance'

[arsenm]

llvm/lib/Target/AMDGPU/SIFormMemoryClauses.cpp

286

Can you add a comment explaining this?

I'm still not following how you're doing it all at once, but subsequent clauses are handled later?

[arsenm]

Is this still relevant?

llvm/lib/Target/AMDGPU/SIFormMemoryClauses.cpp

bool SIFormMemoryClauses::runOnMachineFunction(MachineFunction &MF) {
   SlotIndexes *Ind = LIS->getSlotIndexes();
   bool Changed = false;
 
   MaxVGPRs = TRI->getAllocatableSet(MF, &AMDGPU::VGPR_32RegClass).count();
   MaxSGPRs = TRI->getAllocatableSet(MF, &AMDGPU::SGPR_32RegClass).count();
   unsigned FuncMaxClause = AMDGPU::getIntegerAttribute(
       MF.getFunction(), "amdgpu-max-memory-clause", MaxClause);
 
-  for (MachineBasicBlock &MBB : MF) {
-    GCNDownwardRPTracker RPT(*LIS);
+  SmallVector<MachineInstr *, 16> FirstBBClauseMI;
+  for (auto &MBB : MF) {
+    for (auto &MI : MBB) {
+      if (!MI.isMetaInstruction() &&
+          isValidClauseInst(MI, isVMEMClauseInst(MI))) {
+        FirstBBClauseMI.push_back(&MI);
+        break;
+      }
+    }
+  }
+  if (FirstBBClauseMI.empty())
+    return false;
+
+  auto LRM = getLiveRegMap(FirstBBClauseMI, false /*After*/, *LIS);
+
+  for (auto *FirstMI : FirstBBClauseMI) {
+    auto &MBB = *FirstMI->getParent();
+    RPT.reset(*FirstMI, &LRM[FirstMI]);
     MachineBasicBlock::instr_iterator Next;
-    for (auto I = MBB.instr_begin(), E = MBB.instr_end(); I != E; I = Next) {
+    for (auto I = MachineBasicBlock::instr_iterator(FirstMI),
+              E = MBB.instr_end();
+         I != E; I = Next) {
       MachineInstr &MI = *I;
       Next = std::next(I);
 
       if (MI.isMetaInstruction())
         continue;
 
       bool IsVMEM = isVMEMClauseInst(MI);
 
+      if (&MI != FirstMI) {
         if (!isValidClauseInst(MI, IsVMEM))
           continue;
 
-      if (!RPT.getNext().isValid())
-        RPT.reset(MI);
-      else { // Advance the state to the current MI.
+        // Advance the state to the current MI.
         RPT.advance(MachineBasicBlock::const_iterator(MI));
         RPT.advanceBeforeNext();
       }
 
       const GCNRPTracker::LiveRegSet LiveRegsCopy(RPT.getLiveRegs());
       RegUse Defs, Uses;
       if (!processRegUses(MI, Defs, Uses, RPT)) {
         RPT.reset(MI, &LiveRegsCopy);