[MLIR][LLVM] Recursion importer handle repeated self-references (#87295)

Followup to this discussion:
https://github.com/llvm/llvm-project/pull/80251#discussion_r1535599920.

The previous debug importer was correct but inefficient. For cases with
mutual recursion that contain more than one back-edge, each back-edge
would result in a new translated instance. This is because the previous
implementation never caches any translated result with unbounded
self-references. This means all translation inside a recursive context
is performed from scratch, which will incur repeated run-time cost as
well as repeated attribute sub-trees in the translated IR (differing
only in their `recId`s).

This PR refactors the importer to handle caching inside a recursive
context.
- In the presence of unbound self-refs, the translation result is cached
in a separate cache that keeps track of the set of dependent unbound
self-refs.
- A dependent cache entry is valid only when all the unbound self-refs
are in scope. Whenever a cached entry goes out of scope, it will be
removed the next time it is looked up.

5 files changed, 398 insertions, 79 deletions

diff --git a/mlir/lib/Target/LLVMIR/DebugImporter.cpp b/mlir/lib/Target/LLVMIR/DebugImporter.cpp
index 779ad26..3dc2d4e 100644
--- a/mlir/lib/Target/LLVMIR/DebugImporter.cpp
+++ b/mlir/lib/Target/LLVMIR/DebugImporter.cpp
@@ -13,6 +13,7 @@
 #include "mlir/IR/Location.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/ScopeExit.h"
+#include "llvm/ADT/SetOperations.h"
 #include "llvm/ADT/TypeSwitch.h"
 #include "llvm/BinaryFormat/Dwarf.h"
 #include "llvm/IR/Constants.h"
@@ -25,6 +26,10 @@ using namespace mlir;
 using namespace mlir::LLVM;
 using namespace mlir::LLVM::detail;
 
+DebugImporter::DebugImporter(ModuleOp mlirModule)
+    : recursionPruner(mlirModule.getContext()),
+      context(mlirModule.getContext()), mlirModule(mlirModule) {}
+
 Location DebugImporter::translateFuncLocation(llvm::Function *func) {
   llvm::DISubprogram *subprogram = func->getSubprogram();
   if (!subprogram)
@@ -246,42 +251,13 @@ DINodeAttr DebugImporter::translate(llvm::DINode *node) {
   if (DINodeAttr attr = nodeToAttr.lookup(node))
     return attr;
 
-  // If the node type is capable of being recursive, check if it's seen before.
-  auto recSelfCtor = getRecSelfConstructor(node);
-  if (recSelfCtor) {
-    // If a cyclic dependency is detected since the same node is being traversed
-    // twice, emit a recursive self type, and mark the duplicate node on the
-    // translationStack so it can emit a recursive decl type.
-    auto [iter, inserted] = translationStack.try_emplace(node, nullptr);
-    if (!inserted) {
-      // The original node may have already been assigned a recursive ID from
-      // a different self-reference. Use that if possible.
-      DistinctAttr recId = iter->second;
-      if (!recId) {
-        recId = DistinctAttr::create(UnitAttr::get(context));
-        iter->second = recId;
-      }
-      unboundRecursiveSelfRefs.back().insert(recId);
-      return cast<DINodeAttr>(recSelfCtor(recId));
-    }
-  }
-
-  unboundRecursiveSelfRefs.emplace_back();
-
-  auto guard = llvm::make_scope_exit([&]() {
-    if (recSelfCtor)
-      translationStack.pop_back();
+  // Register with the recursive translator. If it can be handled without
+  // recursing into it, return the result immediately.
+  if (DINodeAttr attr = recursionPruner.pruneOrPushTranslationStack(node))
+    return attr;
 
-    // Copy unboundRecursiveSelfRefs down to the previous level.
-    if (unboundRecursiveSelfRefs.size() == 1)
-      assert(unboundRecursiveSelfRefs.back().empty() &&
-             "internal error: unbound recursive self reference at top level.");
-    else
-      unboundRecursiveSelfRefs[unboundRecursiveSelfRefs.size() - 2].insert(
-          unboundRecursiveSelfRefs.back().begin(),
-          unboundRecursiveSelfRefs.back().end());
-    unboundRecursiveSelfRefs.pop_back();
-  });
+  auto guard = llvm::make_scope_exit(
+      [&]() { recursionPruner.popTranslationStack(node); });
 
   // Convert the debug metadata if possible.
   auto translateNode = [this](llvm::DINode *node) -> DINodeAttr {
@@ -318,22 +294,130 @@ DINodeAttr DebugImporter::translate(llvm::DINode *node) {
     return nullptr;
   };
   if (DINodeAttr attr = translateNode(node)) {
-    // If this node was marked as recursive, set its recId.
-    if (auto recType = dyn_cast<DIRecursiveTypeAttrInterface>(attr)) {
-      if (DistinctAttr recId = translationStack.lookup(node)) {
-        attr = cast<DINodeAttr>(recType.withRecId(recId));
-        // Remove the unbound recursive ID from the set of unbound self
-        // references in the translation stack.
-        unboundRecursiveSelfRefs.back().erase(recId);
+    auto [result, isSelfContained] =
+        recursionPruner.finalizeTranslation(node, attr);
+    // Only cache fully self-contained nodes.
+    if (isSelfContained)
+      nodeToAttr.try_emplace(node, result);
+    return result;
+  }
+  return nullptr;
+}
+
+//===----------------------------------------------------------------------===//
+// RecursionPruner
+//===----------------------------------------------------------------------===//
+
+/// Get the `getRecSelf` constructor for the translated type of `node` if its
+/// translated DITypeAttr supports recursion. Otherwise, returns nullptr.
+static function_ref<DIRecursiveTypeAttrInterface(DistinctAttr)>
+getRecSelfConstructor(llvm::DINode *node) {
+  using CtorType = function_ref<DIRecursiveTypeAttrInterface(DistinctAttr)>;
+  return TypeSwitch<llvm::DINode *, CtorType>(node)
+      .Case([&](llvm::DICompositeType *) {
+        return CtorType(DICompositeTypeAttr::getRecSelf);
+      })
+      .Default(CtorType());
+}
+
+DINodeAttr DebugImporter::RecursionPruner::pruneOrPushTranslationStack(
+    llvm::DINode *node) {
+  // If the node type is capable of being recursive, check if it's seen
+  // before.
+  auto recSelfCtor = getRecSelfConstructor(node);
+  if (recSelfCtor) {
+    // If a cyclic dependency is detected since the same node is being
+    // traversed twice, emit a recursive self type, and mark the duplicate
+    // node on the translationStack so it can emit a recursive decl type.
+    auto [iter, inserted] = translationStack.try_emplace(node);
+    if (!inserted) {
+      // The original node may have already been assigned a recursive ID from
+      // a different self-reference. Use that if possible.
+      DIRecursiveTypeAttrInterface recSelf = iter->second.recSelf;
+      if (!recSelf) {
+        DistinctAttr recId = nodeToRecId.lookup(node);
+        if (!recId) {
+          recId = DistinctAttr::create(UnitAttr::get(context));
+          nodeToRecId[node] = recId;
+        }
+        recSelf = recSelfCtor(recId);
+        iter->second.recSelf = recSelf;
       }
+      // Inject the self-ref into the previous layer.
+      translationStack.back().second.unboundSelfRefs.insert(recSelf);
+      return cast<DINodeAttr>(recSelf);
     }
+  }
 
-    // Only cache fully self-contained nodes.
-    if (unboundRecursiveSelfRefs.back().empty())
-      nodeToAttr.try_emplace(node, attr);
-    return attr;
+  return lookup(node);
+}
+
+std::pair<DINodeAttr, bool>
+DebugImporter::RecursionPruner::finalizeTranslation(llvm::DINode *node,
+                                                    DINodeAttr result) {
+  // If `node` is not a potentially recursive type, it will not be on the
+  // translation stack. Nothing to set in this case.
+  if (translationStack.empty())
+    return {result, true};
+  if (translationStack.back().first != node)
+    return {result, translationStack.back().second.unboundSelfRefs.empty()};
+
+  TranslationState &state = translationStack.back().second;
+
+  // If this node is actually recursive, set the recId onto `result`.
+  if (DIRecursiveTypeAttrInterface recSelf = state.recSelf) {
+    auto recType = cast<DIRecursiveTypeAttrInterface>(result);
+    result = cast<DINodeAttr>(recType.withRecId(recSelf.getRecId()));
+    // Remove this recSelf from the set of unbound selfRefs.
+    state.unboundSelfRefs.erase(recSelf);
   }
-  return nullptr;
+
+  // Insert the result into our internal cache if it's not self-contained.
+  if (!state.unboundSelfRefs.empty()) {
+    auto [_, inserted] = dependentCache.try_emplace(
+        node, DependentTranslation{result, state.unboundSelfRefs});
+    assert(inserted && "invalid state: caching the same DINode twice");
+    return {result, false};
+  }
+  return {result, true};
+}
+
+void DebugImporter::RecursionPruner::popTranslationStack(llvm::DINode *node) {
+  // If `node` is not a potentially recursive type, it will not be on the
+  // translation stack. Nothing to handle in this case.
+  if (translationStack.empty() || translationStack.back().first != node)
+    return;
+
+  // At the end of the stack, all unbound self-refs must be resolved already,
+  // and the entire cache should be accounted for.
+  TranslationState &currLayerState = translationStack.back().second;
+  if (translationStack.size() == 1) {
+    assert(currLayerState.unboundSelfRefs.empty() &&
+           "internal error: unbound recursive self reference at top level.");
+    translationStack.pop_back();
+    return;
+  }
+
+  // Copy unboundSelfRefs down to the previous level.
+  TranslationState &nextLayerState = (++translationStack.rbegin())->second;
+  nextLayerState.unboundSelfRefs.insert(currLayerState.unboundSelfRefs.begin(),
+                                        currLayerState.unboundSelfRefs.end());
+  translationStack.pop_back();
+}
+
+DINodeAttr DebugImporter::RecursionPruner::lookup(llvm::DINode *node) {
+  auto cacheIter = dependentCache.find(node);
+  if (cacheIter == dependentCache.end())
+    return {};
+
+  DependentTranslation &entry = cacheIter->second;
+  if (llvm::set_is_subset(entry.unboundSelfRefs,
+                          translationStack.back().second.unboundSelfRefs))
+    return entry.attr;
+
+  // Stale cache entry.
+  dependentCache.erase(cacheIter);
+  return {};
 }
 
 //===----------------------------------------------------------------------===//
@@ -394,13 +478,3 @@ DistinctAttr DebugImporter::getOrCreateDistinctID(llvm::DINode *node) {
     id = DistinctAttr::create(UnitAttr::get(context));
   return id;
 }
-
-function_ref<DIRecursiveTypeAttrInterface(DistinctAttr)>
-DebugImporter::getRecSelfConstructor(llvm::DINode *node) {
-  using CtorType = function_ref<DIRecursiveTypeAttrInterface(DistinctAttr)>;
-  return TypeSwitch<llvm::DINode *, CtorType>(node)
-      .Case([&](llvm::DICompositeType *concreteNode) {
-        return CtorType(DICompositeTypeAttr::getRecSelf);
-      })
-      .Default(CtorType());
-}
diff --git a/mlir/lib/Target/LLVMIR/DebugImporter.h b/mlir/lib/Target/LLVMIR/DebugImporter.h
index bcf628f..8b22dc6 100644
--- a/mlir/lib/Target/LLVMIR/DebugImporter.h
+++ b/mlir/lib/Target/LLVMIR/DebugImporter.h
@@ -29,8 +29,7 @@ namespace detail {
 
 class DebugImporter {
 public:
-  DebugImporter(ModuleOp mlirModule)
-      : context(mlirModule.getContext()), mlirModule(mlirModule) {}
+  DebugImporter(ModuleOp mlirModule);
 
   /// Translates the given LLVM debug location to an MLIR location.
   Location translateLoc(llvm::DILocation *loc);
@@ -86,24 +85,102 @@ private:
   /// for it, or create a new one if not.
   DistinctAttr getOrCreateDistinctID(llvm::DINode *node);
 
-  /// Get the `getRecSelf` constructor for the translated type of `node` if its
-  /// translated DITypeAttr supports recursion. Otherwise, returns nullptr.
-  function_ref<DIRecursiveTypeAttrInterface(DistinctAttr)>
-  getRecSelfConstructor(llvm::DINode *node);
-
   /// A mapping between LLVM debug metadata and the corresponding attribute.
   DenseMap<llvm::DINode *, DINodeAttr> nodeToAttr;
   /// A mapping between distinct LLVM debug metadata nodes and the corresponding
   /// distinct id attribute.
   DenseMap<llvm::DINode *, DistinctAttr> nodeToDistinctAttr;
 
-  /// A stack that stores the metadata nodes that are being traversed. The stack
-  /// is used to detect cyclic dependencies during the metadata translation.
-  /// A node is pushed with a null value. If it is ever seen twice, it is given
-  /// a recursive id attribute, indicating that it is a recursive node.
-  llvm::MapVector<llvm::DINode *, DistinctAttr> translationStack;
-  /// All the unbound recursive self references in the translation stack.
-  SmallVector<DenseSet<DistinctAttr>> unboundRecursiveSelfRefs;
+  /// Translation helper for recursive DINodes.
+  /// Works alongside a stack-based DINode translator (the "main translator")
+  /// for gracefully handling DINodes that are recursive.
+  ///
+  /// Usage:
+  /// - Before translating a node, call `pruneOrPushTranslationStack` to see if
+  ///   the pruner can preempt this translation. If this is a node that the
+  ///   pruner already knows how to handle, it will return the translated
+  ///   DINodeAttr.
+  /// - After a node is successfully translated by the main translator, call
+  ///   `finalizeTranslation` to save the translated result with the pruner, and
+  ///   give it a chance to further modify the result.
+  /// - Regardless of success or failure by the main translator, always call
+  ///   `popTranslationStack` at the end of translating a node. This is
+  ///   necessary to keep the internal book-keeping in sync.
+  ///
+  /// This helper maintains an internal cache so that no recursive type will
+  /// be translated more than once by the main translator.
+  /// This internal cache is different from the cache maintained by the main
+  /// translator because it may store nodes that are not self-contained (i.e.
+  /// contain unbounded recursive self-references).
+  class RecursionPruner {
+  public:
+    RecursionPruner(MLIRContext *context) : context(context) {}
+
+    /// If this node is a recursive instance that was previously seen, returns a
+    /// self-reference. If this node was previously cached, returns the cached
+    /// result. Otherwise, returns null attr, and a translation stack frame is
+    /// created for this node. Expects `finalizeTranslation` &
+    /// `popTranslationStack` to be called on this node later.
+    DINodeAttr pruneOrPushTranslationStack(llvm::DINode *node);
+
+    /// Register the translated result of `node`. Returns the finalized result
+    /// (with recId if recursive) and whether the result is self-contained
+    /// (i.e. contains no unbound self-refs).
+    std::pair<DINodeAttr, bool> finalizeTranslation(llvm::DINode *node,
+                                                    DINodeAttr result);
+
+    /// Pop off a frame from the translation stack after a node is done being
+    /// translated.
+    void popTranslationStack(llvm::DINode *node);
+
+  private:
+    /// Returns the cached result (if exists) or null.
+    /// The cache entry will be removed if not all of its dependent self-refs
+    /// exists.
+    DINodeAttr lookup(llvm::DINode *node);
+
+    MLIRContext *context;
+
+    /// A cached translation that contains the translated attribute as well
+    /// as any unbound self-references that it depends on.
+    struct DependentTranslation {
+      /// The translated attr. May contain unbound self-references for other
+      /// recursive attrs.
+      DINodeAttr attr;
+      /// The set of unbound self-refs that this cached entry refers to. All
+      /// these self-refs must exist for the cached entry to be valid.
+      DenseSet<DIRecursiveTypeAttrInterface> unboundSelfRefs;
+    };
+    /// A mapping between LLVM debug metadata and the corresponding attribute.
+    /// Only contains those with unboundSelfRefs. Fully self-contained attrs
+    /// will be cached by the outer main translator.
+    DenseMap<llvm::DINode *, DependentTranslation> dependentCache;
+
+    /// Each potentially recursive node will have a TranslationState pushed onto
+    /// the `translationStack` to keep track of whether this node is actually
+    /// recursive (i.e. has self-references inside), and other book-keeping.
+    struct TranslationState {
+      /// The rec-self if this node is indeed a recursive node (i.e. another
+      /// instance of itself is seen while translating it). Null if this node
+      /// has not been seen again deeper in the translation stack.
+      DIRecursiveTypeAttrInterface recSelf;
+      /// All the unbound recursive self references in this layer of the
+      /// translation stack.
+      DenseSet<DIRecursiveTypeAttrInterface> unboundSelfRefs;
+    };
+    /// A stack that stores the metadata nodes that are being traversed. The
+    /// stack is used to handle cyclic dependencies during metadata translation.
+    /// Each node is pushed with an empty TranslationState. If it is ever seen
+    /// later when the stack is deeper, the node is recursive, and its
+    /// TranslationState is assigned a recSelf.
+    llvm::MapVector<llvm::DINode *, TranslationState> translationStack;
+
+    /// A mapping between DINodes that are recursive, and their assigned recId.
+    /// This is kept so that repeated occurrences of the same node can reuse the
+    /// same ID and be deduplicated.
+    DenseMap<llvm::DINode *, DistinctAttr> nodeToRecId;
+  };
+  RecursionPruner recursionPruner;
 
   MLIRContext *context;
   ModuleOp mlirModule;
diff --git a/mlir/lib/Target/LLVMIR/DebugTranslation.cpp b/mlir/lib/Target/LLVMIR/DebugTranslation.cpp
index 642359a..f6e05e2 100644
--- a/mlir/lib/Target/LLVMIR/DebugTranslation.cpp
+++ b/mlir/lib/Target/LLVMIR/DebugTranslation.cpp
@@ -216,18 +216,15 @@ DebugTranslation::translateImpl(DIGlobalVariableAttr attr) {
 llvm::DIType *
 DebugTranslation::translateRecursive(DIRecursiveTypeAttrInterface attr) {
   DistinctAttr recursiveId = attr.getRecId();
-  if (attr.isRecSelf()) {
-    auto *iter = recursiveTypeMap.find(recursiveId);
-    assert(iter != recursiveTypeMap.end() && "unbound DI recursive self type");
+  if (auto *iter = recursiveTypeMap.find(recursiveId);
+      iter != recursiveTypeMap.end()) {
     return iter->second;
+  } else {
+    assert(!attr.isRecSelf() && "unbound DI recursive self type");
   }
 
   auto setRecursivePlaceholder = [&](llvm::DIType *placeholder) {
-    [[maybe_unused]] auto [iter, inserted] =
-        recursiveTypeMap.try_emplace(recursiveId, placeholder);
-    (void)iter;
-    (void)inserted;
-    assert(inserted && "illegal reuse of recursive id");
+    recursiveTypeMap.try_emplace(recursiveId, placeholder);
   };
 
   llvm::DIType *result =
diff --git a/mlir/test/Target/LLVMIR/Import/debug-info.ll b/mlir/test/Target/LLVMIR/Import/debug-info.ll
index 959a5a1..e2ef946 100644
--- a/mlir/test/Target/LLVMIR/Import/debug-info.ll
+++ b/mlir/test/Target/LLVMIR/Import/debug-info.ll
@@ -607,3 +607,146 @@ declare !dbg !1 void @declaration()
 !0 = !{i32 2, !"Debug Info Version", i32 3}
 !1 = !DISubprogram(name: "declaration", scope: !2, file: !2, flags: DIFlagPrototyped, spFlags: 0)
 !2 = !DIFile(filename: "debug-info.ll", directory: "/")
+
+; // -----
+
+; Ensure that repeated occurence of recursive subtree does not result in
+; duplicate MLIR entries.
+;
+; +--> B:B1 ----+
+; |     ^       v
+; A <---+------ B
+; |     v       ^
+; +--> B:B2 ----+
+; This should result in only one B instance.
+
+; CHECK-DAG: #[[B1_INNER:.+]] = #llvm.di_derived_type<{{.*}}name = "B:B1", baseType = #[[B_SELF:.+]]>
+; CHECK-DAG: #[[B2_INNER:.+]] = #llvm.di_derived_type<{{.*}}name = "B:B2", baseType = #[[B_SELF]]>
+; CHECK-DAG: #[[B_INNER:.+]] = #llvm.di_composite_type<{{.*}}recId = [[B_RECID:.+]], {{.*}}name = "B", {{.*}}elements = #[[B1_INNER]], #[[B2_INNER]]
+
+; CHECK-DAG: #[[B1_OUTER:.+]] = #llvm.di_derived_type<{{.*}}name = "B:B1", baseType = #[[B_INNER]]>
+; CHECK-DAG: #[[B2_OUTER:.+]] = #llvm.di_derived_type<{{.*}}name = "B:B2", baseType = #[[B_INNER]]>
+; CHECK-DAG: #[[A_OUTER:.+]] = #llvm.di_composite_type<{{.*}}recId = [[A_RECID:.+]], {{.*}}name = "A", {{.*}}elements = #[[B1_OUTER]], #[[B2_OUTER]]
+
+; CHECK-DAG: #[[A_SELF:.+]] = #llvm.di_composite_type<{{.*}}recId = [[A_RECID]]
+; CHECK-DAG: #[[B_SELF:.+]] = #llvm.di_composite_type<{{.*}}recId = [[B_RECID]]
+
+; CHECK: #llvm.di_subprogram<{{.*}}scope = #[[A_OUTER]]
+
+define void @class_field(ptr %arg1) !dbg !18 {
+  ret void
+}
+
+!llvm.dbg.cu = !{!1}
+!llvm.module.flags = !{!0}
+!0 = !{i32 2, !"Debug Info Version", i32 3}
+!1 = distinct !DICompileUnit(language: DW_LANG_C, file: !2)
+!2 = !DIFile(filename: "debug-info.ll", directory: "/")
+
+!3 = !DICompositeType(tag: DW_TAG_class_type, name: "A", file: !2, line: 42, flags: DIFlagTypePassByReference | DIFlagNonTrivial, elements: !4)
+!4 = !{!7, !8}
+
+!5 = !DICompositeType(tag: DW_TAG_class_type, name: "B", scope: !3, file: !2, line: 42, flags: DIFlagTypePassByReference | DIFlagNonTrivial, elements: !9)
+!7 = !DIDerivedType(tag: DW_TAG_member, name: "B:B1", file: !2, baseType: !5)
+!8 = !DIDerivedType(tag: DW_TAG_member, name: "B:B2", file: !2, baseType: !5)
+!9 = !{!7, !8}
+
+!18 = distinct !DISubprogram(name: "A", scope: !3, file: !2, spFlags: DISPFlagDefinition, unit: !1)
+
+; // -----
+
+; Ensure that recursive cycles with multiple entry points are cached correctly.
+;
+; +---- A ----+
+; v           v
+; B <-------> C
+; This should result in a cached instance of B --> C --> B_SELF to be reused
+; when visiting B from C (after visiting B from A).
+
+; CHECK-DAG: #[[A:.+]] = #llvm.di_composite_type<{{.*}}name = "A", {{.*}}elements = #[[TO_B_OUTER:.+]], #[[TO_C_OUTER:.+]]>
+; CHECK-DAG: #llvm.di_subprogram<{{.*}}scope = #[[A]],
+
+; CHECK-DAG: #[[TO_B_OUTER]] = #llvm.di_derived_type<{{.*}}name = "->B", {{.*}}baseType = #[[B_OUTER:.+]]>
+; CHECK-DAG: #[[B_OUTER]] = #llvm.di_composite_type<{{.*}}recId = [[B_RECID:.+]], {{.*}}name = "B", {{.*}}elements = #[[TO_C_INNER:.+]]>
+; CHECK-DAG: #[[TO_C_INNER]] = #llvm.di_derived_type<{{.*}}name = "->C", {{.*}}baseType = #[[C_INNER:.+]]>
+; CHECK-DAG: #[[C_INNER]] = #llvm.di_composite_type<{{.*}}name = "C", {{.*}}elements = #[[TO_B_SELF:.+]]>
+; CHECK-DAG: #[[TO_B_SELF]] = #llvm.di_derived_type<{{.*}}name = "->B", {{.*}}baseType = #[[B_SELF:.+]]>
+; CHECK-DAG: #[[B_SELF]] = #llvm.di_composite_type<{{.*}}recId = [[B_RECID]]>
+
+; CHECK-DAG: #[[TO_C_OUTER]] = #llvm.di_derived_type<{{.*}}name = "->C", {{.*}}baseType = #[[C_OUTER:.+]]>
+; CHECK-DAG: #[[C_OUTER]] = #llvm.di_composite_type<{{.*}}name = "C", {{.*}}elements = #[[TO_B_OUTER]]>
+
+define void @class_field(ptr %arg1) !dbg !18 {
+  ret void
+}
+
+!llvm.dbg.cu = !{!1}
+!llvm.module.flags = !{!0}
+!0 = !{i32 2, !"Debug Info Version", i32 3}
+!1 = distinct !DICompileUnit(language: DW_LANG_C, file: !2)
+!2 = !DIFile(filename: "debug-info.ll", directory: "/")
+
+!3 = !DICompositeType(tag: DW_TAG_class_type, name: "A", file: !2, line: 42, flags: DIFlagTypePassByReference | DIFlagNonTrivial, elements: !4)
+!5 = !DICompositeType(tag: DW_TAG_class_type, name: "B", file: !2, line: 42, flags: DIFlagTypePassByReference | DIFlagNonTrivial, elements: !10)
+!6 = !DICompositeType(tag: DW_TAG_class_type, name: "C", file: !2, line: 42, flags: DIFlagTypePassByReference | DIFlagNonTrivial, elements: !9)
+
+!7 = !DIDerivedType(tag: DW_TAG_member, name: "->B", file: !2, baseType: !5)
+!8 = !DIDerivedType(tag: DW_TAG_member, name: "->C", file: !2, baseType: !6)
+!4 = !{!7, !8}
+!9 = !{!7}
+!10 = !{!8}
+
+!18 = distinct !DISubprogram(name: "SP", scope: !3, file: !2, spFlags: DISPFlagDefinition, unit: !1)
+
+; // -----
+
+; Ensures that replacing a nested mutually recursive decl does not result in
+; nested duplicate recursive decls.
+;
+; A ---> B <--> C
+; ^             ^
+; +-------------+
+
+; CHECK-DAG: #[[A:.+]] = #llvm.di_composite_type<{{.*}}recId = [[A_RECID:.+]], {{.*}}name = "A", {{.*}}elements = #[[A_TO_B:.+]], #[[A_TO_C:.+]]>
+; CHECK-DAG: #llvm.di_subprogram<{{.*}}scope = #[[A]],
+; CHECK-DAG: #[[A_TO_B]] = #llvm.di_derived_type<{{.*}}name = "->B", {{.*}}baseType = #[[B_FROM_A:.+]]>
+; CHECK-DAG: #[[A_TO_C]] = #llvm.di_derived_type<{{.*}}name = "->C", {{.*}}baseType = #[[C_FROM_A:.+]]>
+
+; CHECK-DAG: #[[B_FROM_A]] = #llvm.di_composite_type<{{.*}}recId = [[B_RECID:.+]], {{.*}}name = "B", {{.*}}elements = #[[B_TO_C:.+]]>
+; CHECK-DAG: #[[B_TO_C]] = #llvm.di_derived_type<{{.*}}name = "->C", {{.*}}baseType = #[[C_FROM_B:.+]]>
+; CHECK-DAG: #[[C_FROM_B]] = #llvm.di_composite_type<{{.*}}recId = [[C_RECID:.+]], {{.*}}name = "C", {{.*}}elements = #[[TO_A_SELF:.+]], #[[TO_B_SELF:.+]], #[[TO_C_SELF:.+]]>
+
+; CHECK-DAG: #[[C_FROM_A]] = #llvm.di_composite_type<{{.*}}recId = [[C_RECID]], {{.*}}name = "C", {{.*}}elements = #[[TO_A_SELF]], #[[TO_B_INNER:.+]], #[[TO_C_SELF]]
+; CHECK-DAG: #[[TO_B_INNER]] = #llvm.di_derived_type<{{.*}}name = "->B", {{.*}}baseType = #[[B_INNER:.+]]>
+; CHECK-DAG: #[[B_INNER]] = #llvm.di_composite_type<{{.*}}name = "B", {{.*}}elements = #[[TO_C_SELF]]>
+
+; CHECK-DAG: #[[TO_A_SELF]] = #llvm.di_derived_type<{{.*}}name = "->A", {{.*}}baseType = #[[A_SELF:.+]]>
+; CHECK-DAG: #[[TO_B_SELF]] = #llvm.di_derived_type<{{.*}}name = "->B", {{.*}}baseType = #[[B_SELF:.+]]>
+; CHECK-DAG: #[[TO_C_SELF]] = #llvm.di_derived_type<{{.*}}name = "->C", {{.*}}baseType = #[[C_SELF:.+]]>
+; CHECK-DAG: #[[A_SELF]] = #llvm.di_composite_type<{{.*}}recId = [[A_RECID]]>
+; CHECK-DAG: #[[B_SELF]] = #llvm.di_composite_type<{{.*}}recId = [[B_RECID]]>
+; CHECK-DAG: #[[C_SELF]] = #llvm.di_composite_type<{{.*}}recId = [[C_RECID]]>
+
+define void @class_field(ptr %arg1) !dbg !18 {
+  ret void
+}
+
+!llvm.dbg.cu = !{!1}
+!llvm.module.flags = !{!0}
+!0 = !{i32 2, !"Debug Info Version", i32 3}
+!1 = distinct !DICompileUnit(language: DW_LANG_C, file: !2)
+!2 = !DIFile(filename: "debug-info.ll", directory: "/")
+
+!3 = !DICompositeType(tag: DW_TAG_class_type, name: "A", file: !2, line: 42, flags: DIFlagTypePassByReference | DIFlagNonTrivial, elements: !9)
+!4 = !DICompositeType(tag: DW_TAG_class_type, name: "B", file: !2, line: 42, flags: DIFlagTypePassByReference | DIFlagNonTrivial, elements: !10)
+!5 = !DICompositeType(tag: DW_TAG_class_type, name: "C", file: !2, line: 42, flags: DIFlagTypePassByReference | DIFlagNonTrivial, elements: !11)
+
+!6 = !DIDerivedType(tag: DW_TAG_member, name: "->A", file: !2, baseType: !3)
+!7 = !DIDerivedType(tag: DW_TAG_member, name: "->B", file: !2, baseType: !4)
+!8 = !DIDerivedType(tag: DW_TAG_member, name: "->C", file: !2, baseType: !5)
+
+!9 = !{!7, !8} ; A -> B, C
+!10 = !{!8} ; B -> C
+!11 = !{!6, !7, !8} ; C -> A, B, C
+
+!18 = distinct !DISubprogram(name: "SP", scope: !3, file: !2, spFlags: DISPFlagDefinition, unit: !1)
diff --git a/mlir/test/Target/LLVMIR/llvmir-debug.mlir b/mlir/test/Target/LLVMIR/llvmir-debug.mlir
index 785a525..c4ca0e8 100644
--- a/mlir/test/Target/LLVMIR/llvmir-debug.mlir
+++ b/mlir/test/Target/LLVMIR/llvmir-debug.mlir
@@ -423,3 +423,31 @@ llvm.mlir.global @global_variable() {dbg_expr = #di_global_variable_expression}
 // CHECK: ![[SCOPE]] = !DISubprogram({{.*}}type: ![[SUBROUTINE:[0-9]+]],
 // CHECK: ![[SUBROUTINE]] = !DISubroutineType(types: ![[SR_TYPES:[0-9]+]])
 // CHECK: ![[SR_TYPES]] = !{![[COMP]]}
+
+// -----
+
+// Ensures nested recursive decls work.
+// The output should be identical to if the inner composite type decl was
+// replaced with the recursive self reference.
+
+#di_file = #llvm.di_file<"test.mlir" in "/">
+#di_composite_type_self = #llvm.di_composite_type<tag = DW_TAG_null, recId = distinct[0]<>>
+
+#di_subroutine_type_inner = #llvm.di_subroutine_type<types = #di_composite_type_self>
+#di_subprogram_inner = #llvm.di_subprogram<scope = #di_file, file = #di_file, subprogramFlags = Optimized, type = #di_subroutine_type_inner>
+#di_composite_type_inner = #llvm.di_composite_type<tag = DW_TAG_class_type, recId = distinct[0]<>, scope = #di_subprogram_inner>
+
+#di_subroutine_type = #llvm.di_subroutine_type<types = #di_composite_type_inner>
+#di_subprogram = #llvm.di_subprogram<scope = #di_file, file = #di_file, subprogramFlags = Optimized, type = #di_subroutine_type>
+#di_composite_type = #llvm.di_composite_type<tag = DW_TAG_class_type, recId = distinct[0]<>, scope = #di_subprogram>
+
+#di_global_variable = #llvm.di_global_variable<file = #di_file, line = 1, type = #di_composite_type>
+#di_global_variable_expression = #llvm.di_global_variable_expression<var = #di_global_variable>
+
+llvm.mlir.global @global_variable() {dbg_expr = #di_global_variable_expression} : !llvm.struct<()>
+
+// CHECK: distinct !DIGlobalVariable({{.*}}type: ![[COMP:[0-9]+]],
+// CHECK: ![[COMP]] = distinct !DICompositeType({{.*}}scope: ![[SCOPE:[0-9]+]],
+// CHECK: ![[SCOPE]] = !DISubprogram({{.*}}type: ![[SUBROUTINE:[0-9]+]],
+// CHECK: ![[SUBROUTINE]] = !DISubroutineType(types: ![[SR_TYPES:[0-9]+]])
+// CHECK: ![[SR_TYPES]] = !{![[COMP]]}