[RemoveRedundantDebugValues] Introduce a MIR pass that removes redundant DBG_VALUEs

[djtodoro]

Summary

This new MIR pass removes redundant DBG_VALUEs.

After the register allocator is done, more precisely, after the Virtual Register Rewriter, we end up having duplicated DBG_VALUEs, since some virtual registers are being rewritten into the same physical register as some of existing DBG_VALUEs. Each DBG_VALUE should indicate (at least before the LiveDebugValues) variables assignment, but it is being clobbered for function parameters during the SelectionDAG since it generates new DBG_VALUEs after COPY instructions, even though the parameter has no assignment. For example, if we had a DBG_VALUE $regX as an entry debug value representing the parameter, and a COPY and after the COPY, DBG_VALUE $virt_reg, and after the virtregrewrite the $virt_reg gets rewritten into $regX, we'd end up having redundant DBG_VALUE.

This breaks the definition of the DBG_VALUE since some analysis passes might be built on top of that premise..., and this patch tries to fix the MIR with the respect to that.

This first patch performs bacward scan, by trying to detect a sequence of consecutive DBG_VALUEs, and to remove all DBG_VALUEs describing one variable but the last one:

For example:

(1) DBG_VALUE $edi, !"var1", ...
(2) DBG_VALUE $esi, !"var2", ...
(3) DBG_VALUE $edi, !"var1", ...
 ...

in this case, we can remove (1).

By combining the forward scan that will be introduced in the next patch (from this stack), by inspecting the statistics, the RemoveRedundantDebugValues removes 15032 instructions by using gdb-7.11 as a testbed.

[djtodoro]

• remove some unwanted newlines

[djtodoro]

NOTE: This pass can be invoked multiple times in the pipeline, in the case we find some other place it is worth using.

[Orlando]

LGTM with a few inline nits (mostly about comments). I'd prefer to wait a little and see if anyone else has comments before hitting Accept. Note to other reviewers: there is a discussion about the stats/impact of this patch-set on D105280.

llvm/docs/SourceLevelDebugging.rst

773–776

nit: this feels maybe a bit clunky? Here is a possible alternative.

llvm/lib/CodeGen/RemoveRedundantDebugValues.cpp

23

70–73

nit/suggestion: possible rewording

// This analysis aims to remove redundant DBG_VALUEs by going backward
// in the basic block and removing all but the last DBG_VALUE for any
// given variable in a set of consecutive DBG_VALUE instructions.

llvm/test/DebugInfo/X86/livedebugvars-avoid-duplicates.ll

4 ↗

(On Diff #355885)

You could add --implicit-check-not=DBG_VALUE to FileCheck so that the test fails if there are unexpected DBG_VALUEs?

[djtodoro]

@Orlando Thanks!

llvm/test/DebugInfo/X86/livedebugvars-avoid-duplicates.ll

4 ↗

(On Diff #355885)

I should have deleted this test now. We don’t need it any more.

[djtodoro]

• addressing comments

[StephenTozer]

llvm/lib/CodeGen/RemoveRedundantDebugValues.cpp

113

DBG_VALUE_LIST looks like it's already supported by this pass; since you aren't touching the actual debug operands, the interface between the two is identical, and the call to isDebugValue() is true for DBG_VALUE_LIST as well.

[djtodoro]

llvm/lib/CodeGen/RemoveRedundantDebugValues.cpp

113

Oh, I see... This should have been added in the next patch from the stack -- we should prevent calling the reduceDbgValsForwardScan() for the DBG_VALUE_LIST with the current implementation.

[djtodoro]

• removing the TODO marker for the DBG_VALUE_LIST, since it is safe for the backward scan

[aprantl]

You probably also considered adding this functionality to MIBuilder or LiveDebugVariables itself, to avoid inserting duplicates in the first place. Would that be possible, or is there no good place in the existing code where we could add this to?

llvm/test/DebugInfo/NVPTX/debug-loc-offset.ll

250 ↗

(On Diff #356945)

Why did this change, is it because the order in which the DBG_VALUEs are processed is different now?

[StephenTozer]

In D105279#2865319, @aprantl wrote:

You probably also considered adding this functionality to MIBuilder or LiveDebugVariables itself, to avoid inserting duplicates in the first place. Would that be possible, or is there no good place in the existing code where we could add this to?

There was a previous patch up to this effect (D105025) that was abandoned due to performance concerns; scanning (potentially) the full basic block at insertion for every DBG_VALUE would be a quadratic solution, while this pass is linear. It would be possible to produce an optimized version using caching in LiveDebugVariables/LiveDebugValues (although probably not MIBuilder), but since they would all be linear time anyway I'm happier with the solution that has less complexity and doesn't insert more into two passes that are already quite dense.

[djtodoro]

In D105279#2866384, @StephenTozer wrote:

In D105279#2865319, @aprantl wrote:

You probably also considered adding this functionality to MIBuilder or LiveDebugVariables itself, to avoid inserting duplicates in the first place. Would that be possible, or is there no good place in the existing code where we could add this to?

There was a previous patch up to this effect (D105025) that was abandoned due to performance concerns; scanning (potentially) the full basic block at insertion for every DBG_VALUE would be a quadratic solution, while this pass is linear. It would be possible to produce an optimized version using caching in LiveDebugVariables/LiveDebugValues (although probably not MIBuilder), but since they would all be linear time anyway I'm happier with the solution that has less complexity and doesn't insert more into two passes that are already quite dense.

Yep, +1.

llvm/test/DebugInfo/NVPTX/debug-loc-offset.ll

250 ↗

(On Diff #356945)

Now we have a new abbrev since the parameter becomes DW_AT_const_value:

...
  (1)  DBG_VALUE 0, $noreg, !13, !DIExpression(), debug-location !14
  (2) DBG_VALUE 1, $noreg, !13, !DIExpression(), debug-location !14
...

This will consider the (1) as redundant...is this OK?

[djtodoro]

llvm/test/DebugInfo/NVPTX/debug-loc-offset.ll

250 ↗

(On Diff #356945)

I’d say it isn’t good…We need to take into account the DBG_VALUEs with a constant as the first operand as a special case…

[djtodoro]

• handle constants in DBG_VALUEs, since it can be there due to a dead instruction that has been deleted due to some optimizations
• added a test for it

[StephenTozer]

I'm not sure whether the most recent change is necessary; on the one hand, I understand that this change is meant to NFC, so affecting the actual debug output feels like a mistake, and I can see this change as being justified solely for the sake of keeping this patch NFC. On the other hand, the fact that removing redundant debug values results in a change in the DWARF is more a fault of the DWARF emission step than this pass I think. If we don't need to use a constant DW_AT_location instead of a DW_AT_const_value, then a debug value that is never live shouldn't cause us to emit the former rather than the latter, and if there is a reason to pick one over the other then the distinguishing factor should be something more explicit than the presence of an otherwise unused debug instruction. But this patch shouldn't need to be held up by that concern, since it works fine as is.

LGTM, but preferably leave it open for a day to see if anyone else has thoughts about this change.

[djtodoro]

@StephenTozer Thanks!

I'd be happy if someone officially accepts the change.

[StephenTozer]

Looks like there's no further comments, LGTM.

[foad]

llvm/lib/CodeGen/TargetPassConfig.cpp

1126

Is the false here just a copy-and-paste? I assume there's no reason why machine verification should not work after this pass?

[djtodoro]

llvm/lib/CodeGen/TargetPassConfig.cpp

1126

oh, yes. Nice catch.

llvm/docs/SourceLevelDebugging.rst

 To avoid debug instructions interfering with the register allocator, the
 LiveDebugVariables pass extracts variable locations from a MIR function and
 deletes the corresponding DBG_VALUE instructions. Some localized copy
 propagation is performed within blocks. After register allocation, the
 VirtRegRewriter pass re-inserts DBG_VALUE instructions in their original
 positions, translating virtual register references into their physical
 machine locations. To avoid encoding incorrect variable locations, in this
 pass any DBG_VALUE of a virtual register that is not live, is replaced by
-the undefined location.
+the undefined location. The LiveDebugVariables may insert redundant DBG_VALUEs
+because of virtual register rewriting. These will be subsequently removed by
+the RemoveRedundantDebugValues pass.
 
 LiveDebugValues expansion of variable locations
 -----------------------------------------------
 
 After all optimizations have run and shortly before emission, the
 LiveDebugValues pass runs to achieve two aims:
 
 * To propagate the location of variables through copies and register spills,
 * For every block, to record every valid variable location in that block.

llvm/include/llvm/CodeGen/CodeGenPassBuilder.h

Error CodeGenPassBuilder<Derived>::addMachinePasses(
   } else {
     if (auto Err = derived().addFastRegAlloc(addPass))
       return Err;
   }
 
   // Run post-ra passes.
   derived().addPostRegAlloc(addPass);
 
+  addPass(RemoveRedundantDebugValuesPass());
+
   // Insert prolog/epilog code.  Eliminate abstract frame index references...
   if (getOptLevel() != CodeGenOpt::None) {
     addPass(PostRAMachineSinkingPass());
     addPass(ShrinkWrapPass());
   }
 
   addPass(PrologEpilogInserterPass());
 

llvm/include/llvm/CodeGen/MachinePassRegistry.def

 DUMMY_MACHINE_FUNCTION_PASS("post-RA-sched", PostRASchedulerPass, ())
 DUMMY_MACHINE_FUNCTION_PASS("fentry-insert", FEntryInserterPass, ())
 DUMMY_MACHINE_FUNCTION_PASS("xray-instrumentation", XRayInstrumentationPass, ())
 DUMMY_MACHINE_FUNCTION_PASS("patchable-function", PatchableFunctionPass, ())
 DUMMY_MACHINE_FUNCTION_PASS("reg-usage-propagation", RegUsageInfoPropagationPass, ())
 DUMMY_MACHINE_FUNCTION_PASS("reg-usage-collector", RegUsageInfoCollectorPass, ())
 DUMMY_MACHINE_FUNCTION_PASS("funclet-layout", FuncletLayoutPass, ())
 DUMMY_MACHINE_FUNCTION_PASS("stackmap-liveness", StackMapLivenessPass, ())
+DUMMY_MACHINE_FUNCTION_PASS("removeredundantdebugvalues", RemoveRedundantDebugValuesPass, ())
 DUMMY_MACHINE_FUNCTION_PASS("livedebugvalues", LiveDebugValuesPass, ())
 DUMMY_MACHINE_FUNCTION_PASS("early-tailduplication", EarlyTailDuplicatePass, ())
 DUMMY_MACHINE_FUNCTION_PASS("opt-phis", OptimizePHIsPass, ())
 DUMMY_MACHINE_FUNCTION_PASS("stack-coloring", StackColoringPass, ())
 DUMMY_MACHINE_FUNCTION_PASS("dead-mi-elimination", DeadMachineInstructionElimPass, ())
 DUMMY_MACHINE_FUNCTION_PASS("early-machinelicm", EarlyMachineLICMPass, ())
 DUMMY_MACHINE_FUNCTION_PASS("machinelicm", MachineLICMPass, ())
 DUMMY_MACHINE_FUNCTION_PASS("machine-cse", MachineCSEPass, ())

llvm/include/llvm/CodeGen/Passes.h

namespace llvm {
   /// bundles (created earlier, e.g. during pre-RA scheduling).
   extern char &FinalizeMachineBundlesID;
 
   /// StackMapLiveness - This pass analyses the register live-out set of
   /// stackmap/patchpoint intrinsics and attaches the calculated information to
   /// the intrinsic for later emission to the StackMap.
   extern char &StackMapLivenessID;
 
+  /// RemoveRedundantDebugValues pass.
+  extern char &RemoveRedundantDebugValuesID;
+
   /// LiveDebugValues pass
   extern char &LiveDebugValuesID;
 
   /// createJumpInstrTables - This pass creates jump-instruction tables.
   ModulePass *createJumpInstrTablesPass();
 
   /// InterleavedAccess Pass - This pass identifies and matches interleaved
   /// memory accesses to target specific intrinsics.

llvm/include/llvm/InitializePasses.h

 void initializeRegUsageInfoCollectorPass(PassRegistry&);
 void initializeRegUsageInfoPropagationPass(PassRegistry&);
 void initializeRegionInfoPassPass(PassRegistry&);
 void initializeRegionOnlyPrinterPass(PassRegistry&);
 void initializeRegionOnlyViewerPass(PassRegistry&);
 void initializeRegionPrinterPass(PassRegistry&);
 void initializeRegionViewerPass(PassRegistry&);
 void initializeRegisterCoalescerPass(PassRegistry&);
+void initializeRemoveRedundantDebugValuesPass(PassRegistry&);
 void initializeRenameIndependentSubregsPass(PassRegistry&);
 void initializeReplaceWithVeclibLegacyPass(PassRegistry &);
 void initializeResetMachineFunctionPass(PassRegistry&);
 void initializeReversePostOrderFunctionAttrsLegacyPassPass(PassRegistry&);
 void initializeRewriteStatepointsForGCLegacyPassPass(PassRegistry &);
 void initializeRewriteSymbolsLegacyPassPass(PassRegistry&);
 void initializeSCCPLegacyPassPass(PassRegistry&);
 void initializeSCEVAAWrapperPassPass(PassRegistry&);

llvm/lib/CodeGen/CMakeLists.txt

add_llvm_component_library(LLVMCodeGen
   RegAllocBasic.cpp
   RegAllocFast.cpp
   RegAllocGreedy.cpp
   RegAllocPBQP.cpp
   RegisterClassInfo.cpp
   RegisterCoalescer.cpp
   RegisterPressure.cpp
   RegisterScavenging.cpp
+  RemoveRedundantDebugValues.cpp
   RenameIndependentSubregs.cpp
   MachineStableHash.cpp
   MIRVRegNamerUtils.cpp
   MIRNamerPass.cpp
   MIRCanonicalizerPass.cpp
   RegisterUsageInfo.cpp
   RegUsageInfoCollector.cpp
   RegUsageInfoPropagate.cpp

llvm/lib/CodeGen/CodeGen.cpp

void llvm::initializeCodeGen(PassRegistry &Registry) {
   initializePreISelIntrinsicLoweringLegacyPassPass(Registry);
   initializeProcessImplicitDefsPass(Registry);
   initializeRABasicPass(Registry);
   initializeRAGreedyPass(Registry);
   initializeRegAllocFastPass(Registry);
   initializeRegUsageInfoCollectorPass(Registry);
   initializeRegUsageInfoPropagationPass(Registry);
   initializeRegisterCoalescerPass(Registry);
+  initializeRemoveRedundantDebugValuesPass(Registry);
   initializeRenameIndependentSubregsPass(Registry);
   initializeSafeStackLegacyPassPass(Registry);
   initializeShadowStackGCLoweringPass(Registry);
   initializeShrinkWrapPass(Registry);
   initializeSjLjEHPreparePass(Registry);
   initializeSlotIndexesPass(Registry);
   initializeStackColoringPass(Registry);
   initializeStackMapLivenessPass(Registry);

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/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/Passes.h"
+#include "llvm/IR/DebugInfoMetadata.h"
+#include "llvm/IR/Function.h"
+#include "llvm/InitializePasses.h"
+#include "llvm/Pass.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)");
+
+namespace {
+
+class RemoveRedundantDebugValues : public MachineFunctionPass {
+public:
+  static char ID;
+
+  RemoveRedundantDebugValues();
+
+  bool reduceDbgValues(MachineFunction &MF);
+
+  /// Remove redundant debug value MIs for the given machine function.
+  bool runOnMachineFunction(MachineFunction &MF) override;
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.setPreservesCFG();
+    MachineFunctionPass::getAnalysisUsage(AU);
+  }
+};
+
+} // namespace
+
+//===----------------------------------------------------------------------===//
+//            Implementation
+//===----------------------------------------------------------------------===//
+
+char RemoveRedundantDebugValues::ID = 0;
+
+char &llvm::RemoveRedundantDebugValuesID = RemoveRedundantDebugValues::ID;
+
+INITIALIZE_PASS(RemoveRedundantDebugValues, DEBUG_TYPE,
+                "Remove Redundant DEBUG_VALUE analysis", false, false)
+
+/// Default construct and initialize the pass.
+RemoveRedundantDebugValues::RemoveRedundantDebugValues()
+    : MachineFunctionPass(ID) {
+  initializeRemoveRedundantDebugValuesPass(*PassRegistry::getPassRegistry());
+}
+
+// This analysis aims to remove redundant DBG_VALUEs by going backward
+// in the basic block and removing all but the last DBG_VALUE for any
+// given variable in a set of consecutive DBG_VALUE instructions.
+// For example:
+//   (1) DBG_VALUE $edi, !"var1", ...
+//   (2) DBG_VALUE $esi, !"var2", ...
+//   (3) DBG_VALUE $edi, !"var1", ...
+//   ...
+// in this case, we can remove (1).
+static bool reduceDbgValsBackwardScan(MachineBasicBlock &MBB) {
+  LLVM_DEBUG(dbgs() << "\n == Backward Scan == \n");
+  SmallVector<MachineInstr *, 8> DbgValsToBeRemoved;
+  SmallDenseSet<DebugVariable> VariableSet;
+
+  for (MachineBasicBlock::reverse_iterator I = MBB.rbegin(), E = MBB.rend();
+       I != E; ++I) {
+    MachineInstr *MI = &*I;
+
+    if (MI->isDebugValue()) {
+      DebugVariable Var(MI->getDebugVariable(), MI->getDebugExpression(),
+                        MI->getDebugLoc()->getInlinedAt());
+      auto R = VariableSet.insert(Var);
+      // If it is a DBG_VALUE describing a constant as:
+      //   DBG_VALUE 0, ...
+      // we just don't consider such instructions as candidates
+      // for redundant removal.
+      if (MI->isNonListDebugValue()) {
+        MachineOperand &Loc = MI->getDebugOperand(0);
+        if (!Loc.isReg()) {
+          // If we have already encountered this variable, just stop
+          // tracking it.
+          if (!R.second)
+            VariableSet.erase(Var);
+          continue;
+        }
+      }
+
+      // We have already encountered the value for this variable,
+      // so this one can be deleted.
+      if (!R.second)
+        DbgValsToBeRemoved.push_back(MI);
+      continue;
+    }
+
+    // If we encountered a non-DBG_VALUE, try to find the next
+    // sequence with consecutive DBG_VALUE instructions.
+    VariableSet.clear();
+  }
+
+  for (auto &Instr : DbgValsToBeRemoved) {
+    LLVM_DEBUG(dbgs() << "removing "; Instr->dump());
+    Instr->eraseFromParent();
+    ++NumRemovedBackward;
+  }
+
+  return !DbgValsToBeRemoved.empty();
+}
+
+bool RemoveRedundantDebugValues::reduceDbgValues(MachineFunction &MF) {
+  LLVM_DEBUG(dbgs() << "\nDebug Value Reduction\n");
+
+  bool Changed = false;
+
+  for (auto &MBB : MF)
+    Changed |= reduceDbgValsBackwardScan(MBB);
+
+  return Changed;
+}
+
+bool RemoveRedundantDebugValues::runOnMachineFunction(MachineFunction &MF) {
+  // Skip functions without debugging information.
+  if (!MF.getFunction().getSubprogram())
+    return false;
+
+  // Skip functions from NoDebug compilation units.
+  if (MF.getFunction().getSubprogram()->getUnit()->getEmissionKind() ==
+      DICompileUnit::NoDebug)
+    return false;
+
+  bool Changed = reduceDbgValues(MF);
+  return Changed;
+}

llvm/lib/CodeGen/TargetPassConfig.cpp

void TargetPassConfig::addMachinePasses() {
   if (getOptimizeRegAlloc())
     addOptimizedRegAlloc();
   else
     addFastRegAlloc();
 
   // Run post-ra passes.
   addPostRegAlloc();
 
+  addPass(&RemoveRedundantDebugValuesID, false);
+
   addPass(&FixupStatepointCallerSavedID);
 
   // Insert prolog/epilog code.  Eliminate abstract frame index references...
   if (getOptLevel() != CodeGenOpt::None) {
     addPass(&PostRAMachineSinkingID);
     addPass(&ShrinkWrapID);
   }
 

llvm/test/CodeGen/AArch64/O0-pipeline.ll

 ; CHECK-NEXT:       InstructionSelect
 ; CHECK-NEXT:       ResetMachineFunction
 ; CHECK-NEXT:       AArch64 Instruction Selection
 ; CHECK-NEXT:       Finalize ISel and expand pseudo-instructions
 ; CHECK-NEXT:       Local Stack Slot Allocation
 ; CHECK-NEXT:       Eliminate PHI nodes for register allocation
 ; CHECK-NEXT:       Two-Address instruction pass
 ; CHECK-NEXT:       Fast Register Allocator
+; CHECK-NEXT:       Remove Redundant DEBUG_VALUE analysis
 ; CHECK-NEXT:       Fixup Statepoint Caller Saved
 ; CHECK-NEXT:       Lazy Machine Block Frequency Analysis
 ; CHECK-NEXT:       Machine Optimization Remark Emitter
 ; CHECK-NEXT:       Prologue/Epilogue Insertion & Frame Finalization
 ; CHECK-NEXT:       Post-RA pseudo instruction expansion pass
 ; CHECK-NEXT:       AArch64 pseudo instruction expansion pass
 ; CHECK-NEXT:       AArch64 speculation hardening pass
 ; CHECK-NEXT:       AArch64 Indirect Thunks

llvm/test/CodeGen/AArch64/O3-pipeline.ll

 ; CHECK-NEXT:       Machine Optimization Remark Emitter
 ; CHECK-NEXT:       Greedy Register Allocator
 ; CHECK-NEXT:       Virtual Register Rewriter
 ; CHECK-NEXT:       Stack Slot Coloring
 ; CHECK-NEXT:       Machine Copy Propagation Pass
 ; CHECK-NEXT:       Machine Loop Invariant Code Motion
 ; CHECK-NEXT:       AArch64 Redundant Copy Elimination
 ; CHECK-NEXT:       A57 FP Anti-dependency breaker
+; CHECK-NEXT:       Remove Redundant DEBUG_VALUE analysis
 ; CHECK-NEXT:       Fixup Statepoint Caller Saved
 ; CHECK-NEXT:       PostRA Machine Sink
 ; CHECK-NEXT:       MachineDominator Tree Construction
 ; CHECK-NEXT:       Machine Natural Loop Construction
 ; CHECK-NEXT:       Machine Block Frequency Analysis
 ; CHECK-NEXT:       MachinePostDominator Tree Construction
 ; CHECK-NEXT:       Lazy Machine Block Frequency Analysis
 ; CHECK-NEXT:       Machine Optimization Remark Emitter

llvm/test/CodeGen/AMDGPU/llc-pipeline.ll

 ; GCN-O0-NEXT:         SI Whole Quad Mode
 ; GCN-O0-NEXT:         Virtual Register Map
 ; GCN-O0-NEXT:         Live Register Matrix
 ; GCN-O0-NEXT:         SI Pre-allocate WWM Registers
 ; GCN-O0-NEXT:         Fast Register Allocator
 ; GCN-O0-NEXT:         SI lower SGPR spill instructions
 ; GCN-O0-NEXT:         Fast Register Allocator
 ; GCN-O0-NEXT:         SI Fix VGPR copies
+; GCN-O0-NEXT:         Remove Redundant DEBUG_VALUE analysis
 ; GCN-O0-NEXT:         Fixup Statepoint Caller Saved
 ; GCN-O0-NEXT:         Lazy Machine Block Frequency Analysis
 ; GCN-O0-NEXT:         Machine Optimization Remark Emitter
 ; GCN-O0-NEXT:         Prologue/Epilogue Insertion & Frame Finalization
 ; GCN-O0-NEXT:         Post-RA pseudo instruction expansion pass
 ; GCN-O0-NEXT:         SI post-RA bundler
 ; GCN-O0-NEXT:         Insert fentry calls
 ; GCN-O0-NEXT:         Insert XRay ops

 ; GCN-O1-NEXT:         Greedy Register Allocator
 ; GCN-O1-NEXT:         GCN NSA Reassign
 ; GCN-O1-NEXT:         Virtual Register Rewriter
 ; GCN-O1-NEXT:         Stack Slot Coloring
 ; GCN-O1-NEXT:         Machine Copy Propagation Pass
 ; GCN-O1-NEXT:         Machine Loop Invariant Code Motion
 ; GCN-O1-NEXT:         SI Fix VGPR copies
 ; GCN-O1-NEXT:         SI optimize exec mask operations
+; GCN-O1-NEXT:         Remove Redundant DEBUG_VALUE analysis
 ; GCN-O1-NEXT:         Fixup Statepoint Caller Saved
 ; GCN-O1-NEXT:         PostRA Machine Sink
 ; GCN-O1-NEXT:         MachineDominator Tree Construction
 ; GCN-O1-NEXT:         Machine Natural Loop Construction
 ; GCN-O1-NEXT:         Machine Block Frequency Analysis
 ; GCN-O1-NEXT:         MachinePostDominator Tree Construction
 ; GCN-O1-NEXT:         Lazy Machine Block Frequency Analysis
 ; GCN-O1-NEXT:         Machine Optimization Remark Emitter

 ; GCN-O1-OPTS-NEXT:         Greedy Register Allocator
 ; GCN-O1-OPTS-NEXT:         GCN NSA Reassign
 ; GCN-O1-OPTS-NEXT:         Virtual Register Rewriter
 ; GCN-O1-OPTS-NEXT:         Stack Slot Coloring
 ; GCN-O1-OPTS-NEXT:         Machine Copy Propagation Pass
 ; GCN-O1-OPTS-NEXT:         Machine Loop Invariant Code Motion
 ; GCN-O1-OPTS-NEXT:         SI Fix VGPR copies
 ; GCN-O1-OPTS-NEXT:         SI optimize exec mask operations
+; GCN-O1-OPTS-NEXT:         Remove Redundant DEBUG_VALUE analysis
 ; GCN-O1-OPTS-NEXT:         Fixup Statepoint Caller Saved
 ; GCN-O1-OPTS-NEXT:         PostRA Machine Sink
 ; GCN-O1-OPTS-NEXT:         MachineDominator Tree Construction
 ; GCN-O1-OPTS-NEXT:         Machine Natural Loop Construction
 ; GCN-O1-OPTS-NEXT:         Machine Block Frequency Analysis
 ; GCN-O1-OPTS-NEXT:         MachinePostDominator Tree Construction
 ; GCN-O1-OPTS-NEXT:         Lazy Machine Block Frequency Analysis
 ; GCN-O1-OPTS-NEXT:         Machine Optimization Remark Emitter

 ; GCN-O2-NEXT:         Greedy Register Allocator
 ; GCN-O2-NEXT:         GCN NSA Reassign
 ; GCN-O2-NEXT:         Virtual Register Rewriter
 ; GCN-O2-NEXT:         Stack Slot Coloring
 ; GCN-O2-NEXT:         Machine Copy Propagation Pass
 ; GCN-O2-NEXT:         Machine Loop Invariant Code Motion
 ; GCN-O2-NEXT:         SI Fix VGPR copies
 ; GCN-O2-NEXT:         SI optimize exec mask operations
+; GCN-O2-NEXT:         Remove Redundant DEBUG_VALUE analysis
 ; GCN-O2-NEXT:         Fixup Statepoint Caller Saved
 ; GCN-O2-NEXT:         PostRA Machine Sink
 ; GCN-O2-NEXT:         MachineDominator Tree Construction
 ; GCN-O2-NEXT:         Machine Natural Loop Construction
 ; GCN-O2-NEXT:         Machine Block Frequency Analysis
 ; GCN-O2-NEXT:         MachinePostDominator Tree Construction
 ; GCN-O2-NEXT:         Lazy Machine Block Frequency Analysis
 ; GCN-O2-NEXT:         Machine Optimization Remark Emitter

 ; GCN-O3-NEXT:         Greedy Register Allocator
 ; GCN-O3-NEXT:         GCN NSA Reassign
 ; GCN-O3-NEXT:         Virtual Register Rewriter
 ; GCN-O3-NEXT:         Stack Slot Coloring
 ; GCN-O3-NEXT:         Machine Copy Propagation Pass
 ; GCN-O3-NEXT:         Machine Loop Invariant Code Motion
 ; GCN-O3-NEXT:         SI Fix VGPR copies
 ; GCN-O3-NEXT:         SI optimize exec mask operations
+; GCN-O3-NEXT:         Remove Redundant DEBUG_VALUE analysis
 ; GCN-O3-NEXT:         Fixup Statepoint Caller Saved
 ; GCN-O3-NEXT:         PostRA Machine Sink
 ; GCN-O3-NEXT:         MachineDominator Tree Construction
 ; GCN-O3-NEXT:         Machine Natural Loop Construction
 ; GCN-O3-NEXT:         Machine Block Frequency Analysis
 ; GCN-O3-NEXT:         MachinePostDominator Tree Construction
 ; GCN-O3-NEXT:         Lazy Machine Block Frequency Analysis
 ; GCN-O3-NEXT:         Machine Optimization Remark Emitter

llvm/test/CodeGen/AMDGPU/ptr-arg-dbg-value.ll

 ; while the latter was emitted for the parameter copy to a virtual register inserted
 ; at the function entry by DAGBuilder.
 define hidden void @ptr_arg_split_reg_mem(<31 x i32>, %struct.A* %arg2) #0 !dbg !25 {
 ; CHECK-LABEL: ptr_arg_split_reg_mem:
 ; CHECK:       .Lfunc_begin1:
 ; CHECK-NEXT:    .loc 1 10 0 ; example.cpp:10:0
 ; CHECK-NEXT:    .cfi_startproc
 ; CHECK-NEXT:  ; %bb.0:
-; CHECK-NEXT:    ;DEBUG_VALUE: ptr_arg_split_reg_mem:b <- [$vgpr31+0]
+;; NOTE: One dbg_value (DEBUG_VALUE: ptr_arg_split_reg_mem:b <- [$vgpr31+0]) will be considered as
+;; redundant after the virtregrewrite, so it will be removed.
 ; CHECK-NEXT:    ;DEBUG_VALUE: ptr_arg_split_reg_mem:b <- [$vgpr31+0]
 ; CHECK-NEXT:    s_waitcnt vmcnt(0) expcnt(0) lgkmcnt(0)
 ; CHECK-NEXT:    buffer_load_dword v32, off, s[0:3], s32
 ; CHECK-NEXT:    v_mov_b32_e32 v0, 1
 ; CHECK-NEXT:  .Ltmp2:
 ; CHECK-NEXT:    .loc 1 12 13 prologue_end ; example.cpp:12:13
 ; CHECK-NEXT:    s_waitcnt vmcnt(0)
 ; CHECK-NEXT:    flat_store_dword v[31:32], v0 offset:396

llvm/test/CodeGen/ARM/O3-pipeline.ll

 ; CHECK-NEXT:      Spill Code Placement Analysis
 ; CHECK-NEXT:      Lazy Machine Block Frequency Analysis
 ; CHECK-NEXT:      Machine Optimization Remark Emitter
 ; CHECK-NEXT:      Greedy Register Allocator
 ; CHECK-NEXT:      Virtual Register Rewriter
 ; CHECK-NEXT:      Stack Slot Coloring
 ; CHECK-NEXT:      Machine Copy Propagation Pass
 ; CHECK-NEXT:      Machine Loop Invariant Code Motion
+; CHECK-NEXT:      Remove Redundant DEBUG_VALUE analysis
 ; CHECK-NEXT:      Fixup Statepoint Caller Saved
 ; CHECK-NEXT:      PostRA Machine Sink
 ; CHECK-NEXT:      Machine Block Frequency Analysis
 ; CHECK-NEXT:      MachineDominator Tree Construction
 ; CHECK-NEXT:      MachinePostDominator Tree Construction
 ; CHECK-NEXT:      Lazy Machine Block Frequency Analysis
 ; CHECK-NEXT:      Machine Optimization Remark Emitter
 ; CHECK-NEXT:      Shrink Wrapping analysis

llvm/test/CodeGen/PowerPC/O3-pipeline.ll

 ; CHECK-NEXT:       Spill Code Placement Analysis
 ; CHECK-NEXT:       Lazy Machine Block Frequency Analysis
 ; CHECK-NEXT:       Machine Optimization Remark Emitter
 ; CHECK-NEXT:       Greedy Register Allocator
 ; CHECK-NEXT:       Virtual Register Rewriter
 ; CHECK-NEXT:       Stack Slot Coloring
 ; CHECK-NEXT:       Machine Copy Propagation Pass
 ; CHECK-NEXT:       Machine Loop Invariant Code Motion
+; CHECK-NEXT:       Remove Redundant DEBUG_VALUE analysis
 ; CHECK-NEXT:       Fixup Statepoint Caller Saved
 ; CHECK-NEXT:       PostRA Machine Sink
 ; CHECK-NEXT:       Machine Block Frequency Analysis
 ; CHECK-NEXT:       MachineDominator Tree Construction
 ; CHECK-NEXT:       MachinePostDominator Tree Construction
 ; CHECK-NEXT:       Lazy Machine Block Frequency Analysis
 ; CHECK-NEXT:       Machine Optimization Remark Emitter
 ; CHECK-NEXT:       Shrink Wrapping analysis

 ; CHECK-NEXT:       Lazy Machine Block Frequency Analysis
 ; CHECK-NEXT:       Machine Optimization Remark Emitter
 ; CHECK-NEXT:       Linux PPC Assembly Printer
 ; CHECK-NEXT:       Free MachineFunction
 
 define void @f() {
   ret void
 }
 No newline at end of file

llvm/test/CodeGen/PowerPC/non-debug-mi-search-frspxsrsp.ll

 ; RUN: llc -verify-machineinstrs -mtriple=powerpc64le-unknown-linux-gnu < %s | FileCheck %s
 
 ; Function Attrs: nounwind
 define dso_local void @test(float* nocapture readonly %Fptr, <4 x float>* nocapture %Vptr) local_unnamed_addr #0 !dbg !10 {
 ; CHECK-LABEL: test:
 ; CHECK:       # %bb.0: # %entry
 ; CHECK-NEXT:          #DEBUG_VALUE: test:Fptr <- $x3
-; CHECK-NEXT:          #DEBUG_VALUE: test:Fptr <- $x3
 ; CHECK-NEXT:          #DEBUG_VALUE: test:Vptr <- $x4
 ; CHECK-NEXT:          addis 5, 2, .LCPI0_0@toc@ha
 ; CHECK-NEXT:  .Ltmp0:
 ; CHECK-NEXT:          .loc    1 2 38 prologue_end
 ; CHECK-NEXT:          lfsx 0, 0, 3
 ; CHECK-NEXT:          addis 3, 2, .LCPI0_1@toc@ha
 ; CHECK-NEXT:  .Ltmp1:
 ; CHECK-NEXT:          .loc    1 0 38 is_stmt 0

llvm/test/CodeGen/X86/O0-pipeline.ll

 ; CHECK-NEXT:       X86 WinAlloca Expander
 ; CHECK-NEXT:       Eliminate PHI nodes for register allocation
 ; CHECK-NEXT:       Two-Address instruction pass
 ; CHECK-NEXT:       Fast Register Allocator
 ; CHECK-NEXT:       Fast Tile Register Configure
 ; CHECK-NEXT:       X86 Lower Tile Copy
 ; CHECK-NEXT:       Bundle Machine CFG Edges
 ; CHECK-NEXT:       X86 FP Stackifier
+; CHECK-NEXT:       Remove Redundant DEBUG_VALUE analysis
 ; CHECK-NEXT:       Fixup Statepoint Caller Saved
 ; CHECK-NEXT:       Lazy Machine Block Frequency Analysis
 ; CHECK-NEXT:       Machine Optimization Remark Emitter
 ; CHECK-NEXT:       Prologue/Epilogue Insertion & Frame Finalization
 ; CHECK-NEXT:       Post-RA pseudo instruction expansion pass
 ; CHECK-NEXT:       X86 pseudo instruction expansion pass
 ; CHECK-NEXT:       Analyze Machine Code For Garbage Collection
 ; CHECK-NEXT:       Insert fentry calls

llvm/test/CodeGen/X86/opt-pipeline.ll

 ; CHECK-NEXT:       Machine Copy Propagation Pass
 ; CHECK-NEXT:       Machine Loop Invariant Code Motion
 ; CHECK-NEXT:       X86 Lower Tile Copy
 ; CHECK-NEXT:       Bundle Machine CFG Edges
 ; CHECK-NEXT:       X86 FP Stackifier
 ; CHECK-NEXT:       MachineDominator Tree Construction
 ; CHECK-NEXT:       Machine Dominance Frontier Construction
 ; CHECK-NEXT:       X86 Load Value Injection (LVI) Load Hardening
+; CHECK-NEXT:       Remove Redundant DEBUG_VALUE analysis
 ; CHECK-NEXT:       Fixup Statepoint Caller Saved
 ; CHECK-NEXT:       PostRA Machine Sink
 ; CHECK-NEXT:       Machine Block Frequency Analysis
 ; CHECK-NEXT:       MachinePostDominator Tree Construction
 ; CHECK-NEXT:       Lazy Machine Block Frequency Analysis
 ; CHECK-NEXT:       Machine Optimization Remark Emitter
 ; CHECK-NEXT:       Shrink Wrapping analysis
 ; CHECK-NEXT:       Prologue/Epilogue Insertion & Frame Finalization

llvm/test/DebugInfo/MIR/Hexagon/live-debug-values-bundled-entry-values.mir

 liveins:
   - { reg: '$r0' }
 body:             |
   bb.0.entry:
     successors: %bb.1
     liveins: $r0
 
     DBG_VALUE $r0, $noreg, !22, !DIExpression(), debug-location !23
-    DBG_VALUE $r0, $noreg, !22, !DIExpression(), debug-location !23
     BUNDLE implicit-def dead $p0, implicit-def $pc, implicit killed $r0, implicit killed $r31, debug-location !24 {
       renamable $p0 = C2_cmpeqi killed renamable $r0, 0, debug-location !24
       PS_jmprettnew internal killed $p0, killed $r31, implicit-def $pc, implicit-def $pc, implicit killed undef $r0, debug-location !27
     }
 
   bb.1.land.rhs:
     CFI_INSTRUCTION def_cfa $r30, 8
     CFI_INSTRUCTION offset $r31, -4

llvm/test/DebugInfo/MIR/X86/multiple-param-dbg-value-entry.mir

 tracksRegLiveness: true
 liveins:
   - { reg: '$edi' }
 body:             |
   bb.0.entry:
     liveins: $edi
 
     DBG_VALUE $edi, $noreg, !15, !DIExpression(), debug-location !18
-    DBG_VALUE $edi, $noreg, !15, !DIExpression(), debug-location !18
     DBG_VALUE $esi, $noreg, !16, !DIExpression(), debug-location !18
     DBG_VALUE $edx, $noreg, !17, !DIExpression(), debug-location !18
     renamable $edi = nsw INC32r killed renamable $edi, implicit-def dead $eflags, debug-location !18
     MOV32mr $rip, 1, $noreg, @global, $noreg, killed renamable $edi, debug-location !18 :: (store (s32) into @global)
     INLINEASM &"", 1, 12, implicit-def dead early-clobber $edi, 12, implicit-def dead early-clobber $esi, 12, implicit-def dead early-clobber $edx, 12, implicit-def dead early-clobber $df, 12, implicit-def dead early-clobber $fpsw, 12, implicit-def dead early-clobber $eflags, !19, debug-location !18
     $eax = MOV32ri 123, debug-location !18
     RETQ killed $eax, debug-location !18
 
 ...

llvm/test/DebugInfo/MIR/X86/remove-redundant-dbg-vals.mir

+# RUN: llc %s -o - -run-pass=removeredundantdebugvalues | FileCheck %s
+
+## This checks that the RemoveRedundantDebugValues removes redundant
+## DBG_VALUEs.
+
+# CHECK-LABEL: foo
+# CHECK-LABEL: bb.0.entry:
+# CHECK:      DBG_VALUE $edi
+# CHECK-NOT:  DBG_VALUE $edi
+# CHECK:      frame-setup PUSH64r
+
+# CHECK-LABEL: foo6
+# CHECK-LABEL: bb.0.entry:
+# CHECK:      DBG_VALUE 0
+# CHECK:      DBG_VALUE 1
+# CHECK:      frame-setup PUSH64r
+
+--- |
+  ; ModuleID = 'test.ll'
+  source_filename = "test.c"
+  target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+  target triple = "x86_64-unknown-linux-gnu"
+  
+  @side_effect = external dso_local local_unnamed_addr global i32, align 4
+  @value = external dso_local local_unnamed_addr global i32, align 4
+  
+  ; Function Attrs: nounwind uwtable
+  define dso_local i32 @foo(i32 %param) local_unnamed_addr !dbg !8 {
+  entry:
+    call void @llvm.dbg.value(metadata i32 %param, metadata !13, metadata !DIExpression()), !dbg !14
+    store i32 %param, i32* @side_effect, align 4, !dbg !15
+    %0 = load i32, i32* @value, align 4, !dbg !20
+    call void @llvm.dbg.value(metadata i32 %0, metadata !13, metadata !DIExpression()), !dbg !14
+    tail call void @bar(i32 %0), !dbg !21
+    ret i32 0, !dbg !22
+  }
+
+  define dso_local i32 @foo6(i32 %param) local_unnamed_addr !dbg !34 {
+  entry:
+    store i32 %param, i32* @side_effect, align 4, !dbg !35
+    %0 = load i32, i32* @value, align 4, !dbg !35
+    tail call void @bar(i32 %0), !dbg !35
+    ret i32 0, !dbg !35
+  }
+
+  declare !dbg !23 dso_local void @bar(i32) local_unnamed_addr
+  
+  ; Function Attrs: nofree nosync nounwind readnone speculatable willreturn
+  declare void @llvm.dbg.value(metadata, metadata, metadata)
+  
+  !llvm.dbg.cu = !{!0}
+  !llvm.module.flags = !{!3, !4, !5, !6}
+  !llvm.ident = !{!7}
+  
+  !0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 13.0.0", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, splitDebugInlining: false, nameTableKind: None)
+  !1 = !DIFile(filename: "test.c", directory: "/dir")
+  !2 = !{}
+  !3 = !{i32 7, !"Dwarf Version", i32 4}
+  !4 = !{i32 2, !"Debug Info Version", i32 3}
+  !5 = !{i32 1, !"wchar_size", i32 4}
+  !6 = !{i32 7, !"uwtable", i32 1}
+  !7 = !{!"clang version 13.0.0"}
+  !8 = distinct !DISubprogram(name: "foo", scope: !1, file: !1, line: 4, type: !9, scopeLine: 4, flags: DIFlagPrototyped | DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !12)
+  !9 = !DISubroutineType(types: !10)
+  !10 = !{!11, !11}
+  !11 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+  !12 = !{!13}
+  !13 = !DILocalVariable(name: "param", arg: 1, scope: !8, file: !1, line: 4, type: !11)
+  !14 = !DILocation(line: 0, scope: !8)
+  !15 = !DILocation(line: 5, column: 17, scope: !8)
+  !20 = !DILocation(line: 6, column: 13, scope: !8)
+  !21 = !DILocation(line: 7, column: 5, scope: !8)
+  !22 = !DILocation(line: 8, column: 5, scope: !8)
+  !23 = !DISubprogram(name: "bar", scope: !1, file: !1, line: 1, type: !24, flags: DIFlagPrototyped, spFlags: DISPFlagOptimized, retainedNodes: !2)
+  !24 = !DISubroutineType(types: !25)
+  !25 = !{null, !11}
+  !34 = distinct !DISubprogram(name: "foo6", scope: !1, file: !1, line: 4, type: !9, scopeLine: 4, flags: DIFlagPrototyped | DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !12)
+  !35 = !DILocation(line: 0, scope: !34)
+
+...
+---
+name:            foo
+alignment:       16
+liveins:
+  - { reg: '$edi', virtual-reg: '' }
+body:             |
+  bb.0.entry:
+    liveins: $edi, $esi
+  
+    DBG_VALUE $edi, $noreg, !13, !DIExpression(), debug-location !14
+    DBG_VALUE $edi, $noreg, !13, !DIExpression(), debug-location !14
+    frame-setup PUSH64r undef $rax, implicit-def $rsp, implicit $rsp
+    CFI_INSTRUCTION def_cfa_offset 16
+    MOV32mr $rip, 1, $noreg, @side_effect, $noreg, killed renamable $esi, debug-location !15 :: (store 4 into @side_effect)
+    DBG_VALUE $edi, $noreg, !13, !DIExpression(), debug-location !14
+    CALL64pcrel32 @bar, csr_64, implicit $rsp, implicit $ssp, implicit $edi, implicit-def $rsp, implicit-def $ssp, debug-location !21
+    $eax = XOR32rr undef $eax, undef $eax, implicit-def dead $eflags, debug-location !22
+    $rcx = frame-destroy POP64r implicit-def $rsp, implicit $rsp, debug-location !22
+    CFI_INSTRUCTION def_cfa_offset 8, debug-location !22
+    RETQ killed $eax, debug-location !22
+
+...
+---
+name:            foo6
+alignment:       16
+liveins:
+  - { reg: '$edi', virtual-reg: '' }
+body:             |
+  bb.0.entry:
+    liveins: $edi, $esi
+
+    DBG_VALUE 0, $noreg, !13, !DIExpression(), debug-location !14
+    DBG_VALUE 1, $noreg, !13, !DIExpression(), debug-location !14
+    frame-setup PUSH64r undef $rax, implicit-def $rsp, implicit $rsp
+    CFI_INSTRUCTION def_cfa_offset 16
+    MOV32mr $rip, 1, $noreg, @side_effect, $noreg, killed renamable $esi, debug-location !15 :: (store 4 into @side_effect)
+    renamable $esi = MOV32rm $rip, 1, $noreg, @value, $noreg, debug-location !20 :: (dereferenceable load 4 from @value)
+    $eax = XOR32rr undef $eax, undef $eax, implicit-def dead $eflags, debug-location !22
+    $rcx = frame-destroy POP64r implicit-def $rsp, implicit $rsp, debug-location !22
+    CFI_INSTRUCTION def_cfa_offset 8, debug-location !22
+    RETQ killed $eax, debug-location !22
+
+...

llvm/utils/gn/secondary/llvm/lib/CodeGen/BUILD.gn

sources = [
     "RegAllocPBQP.cpp",
     "RegUsageInfoCollector.cpp",
     "RegUsageInfoPropagate.cpp",
     "RegisterClassInfo.cpp",
     "RegisterCoalescer.cpp",
     "RegisterPressure.cpp",
     "RegisterScavenging.cpp",
     "RegisterUsageInfo.cpp",
+    "RemoveRedundantDebugValues.cpp",
     "RenameIndependentSubregs.cpp",
     "ReplaceWithVeclib.cpp",
     "ResetMachineFunctionPass.cpp",
     "SafeStack.cpp",
     "SafeStackLayout.cpp",
     "ScheduleDAG.cpp",
     "ScheduleDAGInstrs.cpp",
     "ScheduleDAGPrinter.cpp",