[RemoveRedundantDebugValues] Track registers to efficiently handle many DBG_VALUEs.

[rupprecht]

Summary

When checking if instructions clobber any locations, we do so by looking at each entry in VariableMap and call MI.modifiesRegister() on that variable. If the size of VariableMap is large, this can be very slow, because modifiesRegister isn't very fast.

Instead, we track just the specified registers, and only call MI.modifiesRegister() for each entry in that much smaller set. If there are no matches, we avoid needing to iterate over VariableMap entirely. If there are any matches, we can then iterate over VariableMap and do the much cheaper equality comparison for registers to decide if remove it.

This brings compilation of a seemingly-simle file from 5 minutes to 10 seconds. The stats added in this patch show the relative sizes of data sets:

$ llc -run-pass=removeredundantdebugvalues /tmp/repro.O3.mir -o /dev/null -stats
===-------------------------------------------------------------------------===
                          ... Statistics Collected ...
===-------------------------------------------------------------------------===

     6 removeredundantdebugvalues - Maximum size of RegisterSet (forward scan)
183077 removeredundantdebugvalues - Maximum size of VariableMap (forward scan)

This patch is purely a compile time improvement. It is not intended to have any visible effect on the output IR.

[rupprecht]

Trying to get an actual reduction to share in case this isn't the right approach. The source is basically this:

#include <string>
#include <map>

static auto* kFoo = new std::map<std::string, std::string>({
#include "values.inc"
});

where values.inc is a super long list like:

{"key_1", "value_1" },
{"key_2", "value_2" },
{"key_3", "value_3" },
{"key_4", "value_4" },
{"key_5", "value_5" },
{"key_6", "value_6" },
{"key_7", "value_7" },
{"key_8", "value_8" },
{"key_9", "value_9" },
{"key_10", "value_10" },
...

(~3000 lines long)

But it still isn't reproducing like that, so I'm trying to figure out what else is different compared to the internal build.

[djtodoro]

Thanks for this!

So, currently you are trying to find a counterexample where this does not improve the build time, right?

llvm/lib/CodeGen/RemoveRedundantDebugValues.cpp

143

&Reg : ``` instead?

144

an early exit here?

llvm/lib/CodeGen/RemoveRedundantDebugValues.cpp

 //===- RemoveRedundantDebugValues.cpp - Remove Redundant Debug Value MIs --===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/Register.h"
 #include "llvm/CodeGen/TargetSubtargetInfo.h"
 #include "llvm/IR/DebugInfoMetadata.h"
 #include "llvm/IR/Function.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Pass.h"
 #include "llvm/PassRegistry.h"
 
 /// \file RemoveRedundantDebugValues.cpp
 ///
 /// The RemoveRedundantDebugValues pass removes redundant DBG_VALUEs that
 /// appear in MIR after the register allocator.
 
 #define DEBUG_TYPE "removeredundantdebugvalues"
 
 using namespace llvm;
 
 STATISTIC(NumRemovedBackward, "Number of DBG_VALUEs removed (backward scan)");
 STATISTIC(NumRemovedForward, "Number of DBG_VALUEs removed (forward scan)");
+STATISTIC(PeakVariableMapSize, "Maximum size of VariableMap (forward scan)");
+STATISTIC(PeakRegisterSetSize, "Maximum size of RegisterSet (forward scan)");
 
 namespace {
 
 class RemoveRedundantDebugValues : public MachineFunctionPass {
 public:
   static char ID;
 
   RemoveRedundantDebugValues();

 static bool reduceDbgValsForwardScan(MachineBasicBlock &MBB) {
   LLVM_DEBUG(dbgs() << "\n == Forward Scan == \n");
 
   SmallVector<MachineInstr *, 8> DbgValsToBeRemoved;
   DenseMap<DebugVariable, std::pair<MachineOperand *, const DIExpression *>>
       VariableMap;
   const auto *TRI = MBB.getParent()->getSubtarget().getRegisterInfo();
 
+  // Checking if an MI modifies a register is not trivial, so instead of
+  // directly checking the register of everything in VariableMap, we collect all
+  // the registers here and only check this set. If any register is clobbered,
+  // we can do a trivial register comparison to remove it from VariableMap.
+  DenseSet<Register> RegisterSet;
   for (auto &MI : MBB) {
     if (MI.isDebugValue()) {
       DebugVariable Var(MI.getDebugVariable(), std::nullopt,
                         MI.getDebugLoc()->getInlinedAt());
       auto VMI = VariableMap.find(Var);
       // Just stop tracking this variable, until we cover DBG_VALUE_LIST.
       // 1  DBG_VALUE $rax, "x", DIExpression()
       // ...
if (MI.isDebugValue()) {
         continue;
       }
 
       // We have found a new value for a variable.
       if (VMI == VariableMap.end() ||
           VMI->second.first->getReg() != Loc.getReg() ||
           VMI->second.second != MI.getDebugExpression()) {
         VariableMap[Var] = {&Loc, MI.getDebugExpression()};
+        PeakVariableMapSize.updateMax(VariableMap.size());
+
+        RegisterSet.insert(Loc.getReg());
+        PeakRegisterSetSize.updateMax(RegisterSet.size());
         continue;
       }
 
       // Found an identical DBG_VALUE, so it can be considered
       // for later removal.
       DbgValsToBeRemoved.push_back(&MI);
     }
 
     if (MI.isMetaInstruction())
       continue;
 
     // Stop tracking any location that is clobbered by this instruction.
+    for (const Register reg : RegisterSet) {
+      if (MI.modifiesRegister(reg, TRI)) {
         for (auto &Var : VariableMap) {
-      auto &LocOp = Var.second.first;
-      if (MI.modifiesRegister(LocOp->getReg(), TRI))
+          const auto &LocOp = Var.second.first;
+          if (LocOp->getReg() == reg)
             VariableMap.erase(Var.first);
         }
+        RegisterSet.erase(reg);
+      }
+    }
   }
 
   for (auto &Instr : DbgValsToBeRemoved) {
     LLVM_DEBUG(dbgs() << "removing "; Instr->dump());
     Instr->eraseFromParent();
     ++NumRemovedForward;
   }