[DebugInfo] Add replaceArg function for removing duplicates from DBG_VALUE_LIST expressions

[StephenTozer]

Summary

This patch continues the work discussed in the RFC[0] for DBG_VALUE_LIST.

This is a very simple patch that is not needed for the basic addition of the DBG_VALUE_LIST instruction, but is needed for both the LiveDebugValues and LiveDebugVariables patches that follow it.

When a DBG_VALUE_LIST contains 2 or more identical debug operands, at certain passes we want to be able to remove the duplicate operands; the purpose of the replaceArg function is to modify a DIExpression by removing a duplicated operand. This means given a base operand x and a duplicate operand y, replacing each instance of DW_OP_LLVM_arg y with DW_OP_LLVM_arg x, and decrementing all arg > y as the operand array indices shift. For example, if we have:

DBG_VALUE_LIST "x", DIExpression(DW_OP_LLVM_arg 0, DW_OP_LLVM_arg 1, DW_OP_plus, DW_OP_LLVM_arg 2, DW_OP_mul), %0, %0, %1

The debug operands 0 and 1 are the same, so we can remove debug operand 1 and replace its uses with debug operand 0, giving us:

DBG_VALUE_LIST "x", DIExpression(DW_OP_LLVM_arg 0, DW_OP_LLVM_arg 0, DW_OP_plus, DW_OP_LLVM_arg 1, DW_OP_mul), %0, %1

This isn't necessary when handling the instruction in generic passes, but when we perform more in-depth analysis on debug value liveness (as in LiveDebugValues and LiveDebugVariables) having the same location appear more than once in a variable location is an issue, so we remove duplicates only as we enter those passes.

[0] http://lists.llvm.org/pipermail/llvm-dev/2020-February/139376.html

[aprantl]

Could you please add a unit test for this?

llvm/include/llvm/IR/DebugInfoMetadata.h

10

I see the comment of the function above makes the same mistake: This is creating a copy of Expr, not modifying it.

[StephenTozer]

Add a simple unit test for the new function.

[aprantl]

llvm/include/llvm/IR/DebugInfoMetadata.h

9–1

would you mind fixing this, too?

[StephenTozer]

Rebased to recent master, no actual changes.

llvm/include/llvm/IR/DebugInfoMetadata.h

 //===- llvm/IR/DebugInfoMetadata.h - Debug info metadata --------*- C++ -*-===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
 // Declarations for metadata specific to debug info.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_IR_DEBUGINFOMETADATA_H
 #define LLVM_IR_DEBUGINFOMETADATA_H
 
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/BitmaskEnum.h"
 #include "llvm/ADT/None.h"
public:
   /// Create a copy of \p Expr by appending the given list of \p Ops to each
   /// instance of the operand `DW_OP_LLVM_arg, \p ArgNo`. This is used to
   /// modify a specific location used by \p Expr, such as when salvaging that
   /// location.
   static DIExpression *appendOpsToArg(const DIExpression *Expr,
                                       ArrayRef<uint64_t> Ops, unsigned ArgNo,
                                       bool StackValue = false);
 
+  /// Create a copy of \p Expr with each instance of
+  /// `DW_OP_LLVM_arg, \p OldArg` replaced with `DW_OP_LLVM_arg, \p NewArg`,
+  /// and each instance of `DW_OP_LLVM_arg, Arg` with `DW_OP_LLVM_arg, Arg - 1`
+  /// for all Arg > \p OldArg.
+  /// This is used when replacing one of the operands of a debug value list
+  /// with another operand in the same list and deleting the old operand.
+  static DIExpression *replaceArg(const DIExpression *Expr, uint64_t OldArg,
+                                  uint64_t NewArg);
+
   /// Create a DIExpression to describe one part of an aggregate variable that
   /// is fragmented across multiple Values. The DW_OP_LLVM_fragment operation
   /// will be appended to the elements of \c Expr. If \c Expr already contains
   /// a \c DW_OP_LLVM_fragment \c OffsetInBits is interpreted as an offset
   /// into the existing fragment.
   ///
   /// \param OffsetInBits Offset of the piece in bits.
   /// \param SizeInBits   Size of the piece in bits.

llvm/lib/IR/DebugInfoMetadata.cpp

for (auto Op : Expr->expr_ops()) {
     Op.appendToVector(NewOps);
     if (Op.getOp() == dwarf::DW_OP_LLVM_arg && Op.getArg(0) == ArgNo)
       NewOps.insert(NewOps.end(), Ops.begin(), Ops.end());
   }
 
   return DIExpression::get(Expr->getContext(), NewOps);
 }
 
+DIExpression *DIExpression::replaceArg(const DIExpression *Expr,
+                                       uint64_t OldArg, uint64_t NewArg) {
+  assert(Expr && "Can't replace args in this expression");
+
+  SmallVector<uint64_t, 8> NewOps;
+
+  for (auto Op : Expr->expr_ops()) {
+    if (Op.getOp() != dwarf::DW_OP_LLVM_arg || Op.getArg(0) < OldArg) {
+      Op.appendToVector(NewOps);
+      continue;
+    }
+    NewOps.push_back(dwarf::DW_OP_LLVM_arg);
+    uint64_t Arg = Op.getArg(0) == OldArg ? NewArg : Op.getArg(0);
+    // OldArg has been deleted from the Op list, so decrement all indices
+    // greater than it.
+    if (Arg > OldArg)
+      --Arg;
+    NewOps.push_back(Arg);
+  }
+  return DIExpression::get(Expr->getContext(), NewOps);
+}
+
 DIExpression *DIExpression::prependOpcodes(const DIExpression *Expr,
                                            SmallVectorImpl<uint64_t> &Ops,
                                            bool StackValue,
                                            bool EntryValue) {
   assert(Expr && "Can't prepend ops to this expression");
 
   if (EntryValue) {
     Ops.push_back(dwarf::DW_OP_LLVM_entry_value);

llvm/unittests/IR/MetadataTest.cpp

#define EXPECT_INVALID_FRAGMENT(Offset, Size, ...)                             \
   EXPECT_INVALID_FRAGMENT(0, 32, dwarf::DW_OP_constu, 16, dwarf::DW_OP_shl);
   EXPECT_INVALID_FRAGMENT(0, 32, dwarf::DW_OP_constu, 16, dwarf::DW_OP_shra);
   EXPECT_INVALID_FRAGMENT(0, 32, dwarf::DW_OP_plus_uconst, 6);
 
 #undef EXPECT_VALID_FRAGMENT
 #undef EXPECT_INVALID_FRAGMENT
 }
 
+TEST_F(DIExpressionTest, replaceArg) {
+#define EXPECT_REPLACE_ARG_EQ(Expr, OldArg, NewArg, ...)                       \
+  do {                                                                         \
+    uint64_t Elements[] = {__VA_ARGS__};                                       \
+    ArrayRef<uint64_t> Expected = Elements;                                    \
+    DIExpression *Expression = DIExpression::replaceArg(Expr, OldArg, NewArg); \
+    EXPECT_EQ(Expression->getElements(), Expected);                            \
+  } while (false)
+
+  auto N = DIExpression::get(
+      Context, {dwarf::DW_OP_LLVM_arg, 0, dwarf::DW_OP_LLVM_arg, 1,
+                dwarf::DW_OP_plus, dwarf::DW_OP_LLVM_arg, 2, dwarf::DW_OP_mul});
+  EXPECT_REPLACE_ARG_EQ(N, 0, 1, dwarf::DW_OP_LLVM_arg, 0,
+                        dwarf::DW_OP_LLVM_arg, 0, dwarf::DW_OP_plus,
+                        dwarf::DW_OP_LLVM_arg, 1, dwarf::DW_OP_mul);
+  EXPECT_REPLACE_ARG_EQ(N, 0, 2, dwarf::DW_OP_LLVM_arg, 1,
+                        dwarf::DW_OP_LLVM_arg, 0, dwarf::DW_OP_plus,
+                        dwarf::DW_OP_LLVM_arg, 1, dwarf::DW_OP_mul);
+  EXPECT_REPLACE_ARG_EQ(N, 2, 0, dwarf::DW_OP_LLVM_arg, 0,
+                        dwarf::DW_OP_LLVM_arg, 1, dwarf::DW_OP_plus,
+                        dwarf::DW_OP_LLVM_arg, 0, dwarf::DW_OP_mul);
+  EXPECT_REPLACE_ARG_EQ(N, 2, 1, dwarf::DW_OP_LLVM_arg, 0,
+                        dwarf::DW_OP_LLVM_arg, 1, dwarf::DW_OP_plus,
+                        dwarf::DW_OP_LLVM_arg, 1, dwarf::DW_OP_mul);
+
+#undef EXPECT_REPLACE_ARG_EQ
+}
+
 typedef MetadataTest DIObjCPropertyTest;
 
 TEST_F(DIObjCPropertyTest, get) {
   StringRef Name = "name";
   DIFile *File = getFile();
   unsigned Line = 5;
   StringRef GetterName = "getter";
   StringRef SetterName = "setter";