[DebugInfo] Prevent infinite recursion for malformed DWARF

This prevents infinite recursion in DWARFDie::findRecursively for
malformed DWARF where a DIE references itself.

This fixes PR36257.

Differential revision: https://reviews.llvm.org/D43092

llvm-svn: 331200

1 files changed, 30 insertions, 10 deletions

diff --git a/llvm/lib/DebugInfo/DWARF/DWARFDie.cpp b/llvm/lib/DebugInfo/DWARF/DWARFDie.cpp
index 7ae38e6e053..0d045c5d4bc 100644
--- a/llvm/lib/DebugInfo/DWARF/DWARFDie.cpp
+++ b/llvm/lib/DebugInfo/DWARF/DWARFDie.cpp
@@ -10,6 +10,7 @@
 #include "llvm/DebugInfo/DWARF/DWARFDie.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/Optional.h"
+#include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/BinaryFormat/Dwarf.h"
 #include "llvm/DebugInfo/DWARF/DWARFAbbreviationDeclaration.h"
@@ -295,18 +296,37 @@ DWARFDie::find(ArrayRef<dwarf::Attribute> Attrs) const {
 
 Optional<DWARFFormValue>
 DWARFDie::findRecursively(ArrayRef<dwarf::Attribute> Attrs) const {
-  if (!isValid())
-    return None;
-  if (auto Value = find(Attrs))
-    return Value;
-  if (auto Die = getAttributeValueAsReferencedDie(DW_AT_abstract_origin)) {
-    if (auto Value = Die.findRecursively(Attrs))
-      return Value;
-  }
-  if (auto Die = getAttributeValueAsReferencedDie(DW_AT_specification)) {
-    if (auto Value = Die.findRecursively(Attrs))
+  std::vector<DWARFDie> Worklist;
+  Worklist.push_back(*this);
+
+  // Keep track if DIEs already seen to prevent infinite recursion.
+  // Empirically we rarely see a depth of more than 3 when dealing with valid
+  // DWARF. This corresponds to following the DW_AT_abstract_origin and
+  // DW_AT_specification just once.
+  SmallSet<DWARFDie, 3> Seen;
+
+  while (!Worklist.empty()) {
+    DWARFDie Die = Worklist.back();
+    Worklist.pop_back();
+
+    if (!Die.isValid())
+      continue;
+
+    if (Seen.count(Die))
+      continue;
+
+    Seen.insert(Die);
+
+    if (auto Value = Die.find(Attrs))
       return Value;
+
+    if (auto D = Die.getAttributeValueAsReferencedDie(DW_AT_abstract_origin))
+      Worklist.push_back(D);
+
+    if (auto D = Die.getAttributeValueAsReferencedDie(DW_AT_specification))
+      Worklist.push_back(D);
   }
+
   return None;
 }