Fix a crash when emitting DIEs for variable-length arrays

[aprantl]

Summary

VLAs may refer to a previous DIE to express the DW_AT_count of their type. Clang generates an artificial "vla_expr" variable for this. If this DIE hasn't been created yet LLVM asserts. This patch fixes this by sorting the local variables so that dependencies come before they are needed. It also replaces the linear scan in DWARFFile with a std::map, which can be faster.

[davide]

lib/CodeGen/AsmPrinter/DwarfFile.h

52 ↗

(On Diff #132923)

Do you really need std::map<> here? Can't you use an LLVM container?

[aprantl]

lib/CodeGen/AsmPrinter/DwarfFile.h

52 ↗

(On Diff #132923)

Is there a better container for this? I need something that allows me to

1. check whether an element already exists while building the list
2. traverse all elements in order at the end.

DenseMap doesn't support (2), so the only other alternative I could come up with was a SmallVector or a std::list that is kept sorted after each insert by using std::lower_bound to look up the insertion point. Using a std::list instead the SmallVector would be more memory efficient than the std::map. Using a SmallVector would use least memory, but has quadratic worst-case behavior. Any preferences/suggestions?

[davide]

Some comments inline, but this is almost good to go IMHO.

lib/CodeGen/AsmPrinter/DwarfCompileUnit.cpp

573–583 ↗

(On Diff #132923)

I think the logic here is correct, but I don't necessarily like all this level of nesting.
Can you try to use something like llvm::any_of or reduce indentations with early exits?
i.e.

DICompositeType *Array = dyn_cast<>();
if (!Array)
  return false
[...]

586 ↗

(On Diff #132923)

that variables that variables :)

lib/CodeGen/AsmPrinter/DwarfFile.h

52 ↗

(On Diff #132923)

I think a map is fine, but I'd add a comment here explaining the rationale, if you don't mind.

[aprantl]

Address review feedback from Davide.

[davide]

LGTM. One minor comment inline. Feel free to decide whether you want to address & commit (no need for another round trip)

lib/CodeGen/AsmPrinter/DwarfCompileUnit.cpp

576 ↗

(On Diff #133070)

Terrific, looks much better now :)

604 ↗

(On Diff #133070)

sortLocalVars can be an inline lambda, but hey, up to you.

[aprantl]

smaller testcase (thanks Volodymyr!)

[vsapsai]

llvm/trunk/lib/CodeGen/AsmPrinter/DwarfCompileUnit.cpp

590

std::stable_sort requires comparison function object to satisfy Compare concept. It is mentioned that comp(a, b) establishes strict weak ordering relation. One of the requirements of this ordering is transitivity of incomparability, i.e. if x <> y and y <> z then it should be x <> z. But with dependency relation it is possible that x and y are independent, y and z are independent, but x depends on z.

During my testing I had DbgVariable in the following order

array
count
vla_expr

and the sorting proceeded as

is [1] < [0] => false, no swapping
is [2] < [1] => false, no swapping
finish sort

We didn't even check that array depends on vla_expr.

Looks like for dependency relation something like stable topological sorting is more appropriate.

llvm/trunk/lib/CodeGen/AsmPrinter/DwarfCompileUnit.cpp

DIE *DwarfCompileUnit::constructVariableDIE(DbgVariable &DV,
                                             const LexicalScope &Scope,
                                             DIE *&ObjectPointer) {
   auto Var = constructVariableDIE(DV, Scope.isAbstractScope());
   if (DV.isObjectPointer())
     ObjectPointer = Var;
   return Var;
 }
 
+/// Determine whether a variable appears in a count: expression.
+static bool dependsOn(DbgVariable *A, DbgVariable *B) {
+  auto *Array = dyn_cast<DICompositeType>(A->getType());
+  if (!Array || Array->getTag() != dwarf::DW_TAG_array_type)
+    return false;
+  return llvm::any_of(Array->getElements(), [&](DINode *El) {
+    if (auto *Subrange = dyn_cast<DISubrange>(El)) {
+      auto Count = Subrange->getCount();
+      if (auto *Var = Count.dyn_cast<DIVariable *>())
+        return Var == B->getVariable();
+    }
+    return false;
+  });
+}
+
+/// Sort local variables so that variables appearing inside of helper
+/// expressions come first.
+static bool sortLocalVars(DbgVariable *A, DbgVariable *B) {
+  return dependsOn(B, A);
+}
+
 DIE *DwarfCompileUnit::createScopeChildrenDIE(LexicalScope *Scope,
                                               SmallVectorImpl<DIE *> &Children,
                                               bool *HasNonScopeChildren) {
   assert(Children.empty());
   DIE *ObjectPointer = nullptr;
 
-  for (DbgVariable *DV : DU->getScopeVariables().lookup(Scope))
+  // Emit function arguments (order is significant).
+  auto Vars = DU->getScopeVariables().lookup(Scope);
+  for (auto &DV : Vars.Args)
+    Children.push_back(constructVariableDIE(*DV.second, *Scope, ObjectPointer));
+
+  // Emit local variables.
+  std::stable_sort(Vars.Locals.begin(), Vars.Locals.end(), sortLocalVars);
+  for (DbgVariable *DV : Vars.Locals)
     Children.push_back(constructVariableDIE(*DV, *Scope, ObjectPointer));
 
   // Skip imported directives in gmlt-like data.
   if (!includeMinimalInlineScopes()) {
     // There is no need to emit empty lexical block DIE.
     for (const auto *IE : ImportedEntities[Scope->getScopeNode()])
       Children.push_back(
           constructImportedEntityDIE(cast<DIImportedEntity>(IE)));

llvm/trunk/lib/CodeGen/AsmPrinter/DwarfFile.h

 
 #include "DwarfStringPool.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/CodeGen/DIE.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/Support/Allocator.h"
+#include <map>
 #include <memory>
 #include <utility>
 
 namespace llvm {
 
 class AsmPrinter;
 class DbgVariable;
 class DwarfCompileUnit;
class DwarfFile {
   SmallVector<std::unique_ptr<DwarfCompileUnit>, 1> CUs;
 
   DwarfStringPool StrPool;
 
   /// DWARF v5: The symbol that designates the start of the contribution to
   /// the string offsets table. The contribution is shared by all units.
   MCSymbol *StringOffsetsStartSym = nullptr;
 
-  // Collection of dbg variables of a scope.
-  DenseMap<LexicalScope *, SmallVector<DbgVariable *, 8>> ScopeVariables;
+  /// The variables of a lexical scope.
+  struct ScopeVars {
+    /// We need to sort Args by ArgNo and check for duplicates. This could also
+    /// be implemented as a list or vector + std::lower_bound().
+    std::map<unsigned, DbgVariable *> Args;
+    SmallVector<DbgVariable *, 8> Locals;
+  };
+  /// Collection of DbgVariables of each lexical scope.
+  DenseMap<LexicalScope *, ScopeVars> ScopeVariables;
 
   // Collection of abstract subprogram DIEs.
   DenseMap<const MDNode *, DIE *> AbstractSPDies;
   DenseMap<const MDNode *, std::unique_ptr<DbgVariable>> AbstractVariables;
 
   /// Maps MDNodes for type system with the corresponding DIEs. These DIEs can
   /// be shared across CUs, that is why we keep the map here instead
   /// of in DwarfCompileUnit.
public:
 
   MCSymbol *getStringOffsetsStartSym() const { return StringOffsetsStartSym; }
 
   void setStringOffsetsStartSym(MCSymbol *Sym) { StringOffsetsStartSym = Sym; }
 
   /// \returns false if the variable was merged with a previous one.
   bool addScopeVariable(LexicalScope *LS, DbgVariable *Var);
 
-  DenseMap<LexicalScope *, SmallVector<DbgVariable *, 8>> &getScopeVariables() {
+  DenseMap<LexicalScope *, ScopeVars> &getScopeVariables() {
     return ScopeVariables;
   }
 
   DenseMap<const MDNode *, DIE *> &getAbstractSPDies() {
     return AbstractSPDies;
   }
 
   DenseMap<const MDNode *, std::unique_ptr<DbgVariable>> &getAbstractVariables() {

llvm/trunk/lib/CodeGen/AsmPrinter/DwarfFile.cpp

 
 // Emit strings into a string section.
 void DwarfFile::emitStrings(MCSection *StrSection, MCSection *OffsetSection,
                             bool UseRelativeOffsets) {
   StrPool.emit(*Asm, StrSection, OffsetSection, UseRelativeOffsets);
 }
 
 bool DwarfFile::addScopeVariable(LexicalScope *LS, DbgVariable *Var) {
-  SmallVectorImpl<DbgVariable *> &Vars = ScopeVariables[LS];
+  auto &ScopeVars = ScopeVariables[LS];
   const DILocalVariable *DV = Var->getVariable();
-  // Variables with positive arg numbers are parameters.
   if (unsigned ArgNum = DV->getArg()) {
-    // Keep all parameters in order at the start of the variable list to ensure
-    // function types are correct (no out-of-order parameters)
-    //
-    // This could be improved by only doing it for optimized builds (unoptimized
-    // builds have the right order to begin with), searching from the back (this
-    // would catch the unoptimized case quickly), or doing a binary search
-    // rather than linear search.
-    auto I = Vars.begin();
-    while (I != Vars.end()) {
-      unsigned CurNum = (*I)->getVariable()->getArg();
-      // A local (non-parameter) variable has been found, insert immediately
-      // before it.
-      if (CurNum == 0)
-        break;
-      // A later indexed parameter has been found, insert immediately before it.
-      if (CurNum > ArgNum)
-        break;
-      if (CurNum == ArgNum) {
-        (*I)->addMMIEntry(*Var);
-        return false;
-      }
-      ++I;
-    }
-    Vars.insert(I, Var);
-    return true;
-  }
-
-  Vars.push_back(Var);
+    auto Cached = ScopeVars.Args.find(ArgNum);
+    if (Cached == ScopeVars.Args.end())
+      ScopeVars.Args[ArgNum] = Var;
+    else {
+      Cached->second->addMMIEntry(*Var);
+  } else {
+    ScopeVars.Locals.push_back(Var);
+  }    
   return true;
 }

llvm/trunk/test/DebugInfo/X86/vla-dependencies.ll

+; RUN: llc -mtriple=x86_64-apple-darwin %s -o - -filetype=obj | llvm-dwarfdump - | FileCheck %s
+; CHECK:  DW_TAG_subprogram
+; CHECK:    DW_AT_name  ("h")
+; CHECK: 0x00000[[VLAEXPR:.*]]:     DW_TAG_variable
+; CHECK-NEXT:                DW_AT_name ("vla_expr")
+;0x000000b1:   DW_TAG_array_type
+;                DW_AT_type (cu + 0x0066 "unsigned char")
+;
+;0x000000b6:     DW_TAG_subrange_type
+;                  DW_AT_type (cu + 0x0079 "sizetype")
+;                  DW_AT_count  (cu + 0x[[VLAEXPR]])
+;
+;
+; Generated from:
+;
+; #define DECLARE_ARRAY(type, var_name, size) type var_name[size]
+;  
+; void h(void);
+; void k(void *);
+;  
+; void g() {
+;   h();
+; }
+;  
+; void h() {
+;   int count = 2;
+;   DECLARE_ARRAY(int, array, count);
+;   k((void *)array);
+; }
+source_filename = "/tmp/test.c"
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.13.0"
+
+; Function Attrs: nounwind ssp uwtable
+define void @g() local_unnamed_addr #0 !dbg !10 {
+entry:
+  %vla2.i = alloca [2 x i32], align 16, !dbg !13
+  call void @llvm.dbg.declare(metadata [2 x i32]* %vla2.i, metadata !20, metadata !DIExpression(DW_OP_stack_value)), !dbg !13
+  %0 = bitcast [2 x i32]* %vla2.i to i8*, !dbg !25
+  call void @llvm.lifetime.start.p0i8(i64 8, i8* nonnull %0), !dbg !25
+  call void @llvm.dbg.value(metadata i32 2, metadata !16, metadata !DIExpression()) #3, !dbg !25
+  call void @llvm.dbg.value(metadata i64 2, metadata !18, metadata !DIExpression()) #3, !dbg !13
+  call void @k(i8* nonnull %0) #3, !dbg !26
+  call void @llvm.lifetime.end.p0i8(i64 8, i8* nonnull %0), !dbg !27
+  ret void, !dbg !28
+}
+
+; Function Attrs: nounwind readnone speculatable
+declare void @llvm.dbg.declare(metadata, metadata, metadata) #1
+
+declare void @k(i8*) local_unnamed_addr
+
+; Function Attrs: nounwind readnone speculatable
+declare void @llvm.dbg.value(metadata, metadata, metadata) #1
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.lifetime.start.p0i8(i64, i8* nocapture) #2
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.lifetime.end.p0i8(i64, i8* nocapture) #2
+
+attributes #0 = { nounwind ssp uwtable }
+attributes #1 = { nounwind readnone speculatable }
+attributes #2 = { argmemonly nounwind }
+attributes #3 = { nounwind }
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!5, !6, !7, !8}
+!llvm.ident = !{!9}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 7.0.0 (trunk 324259) (llvm/trunk 324261)", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, retainedTypes: !3)
+!1 = !DIFile(filename: "/tmp/test.c", directory: "/")
+!2 = !{}
+!3 = !{!4}
+!4 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: null, size: 64)
+!5 = !{i32 2, !"Dwarf Version", i32 4}
+!6 = !{i32 2, !"Debug Info Version", i32 3}
+!7 = !{i32 1, !"wchar_size", i32 4}
+!8 = !{i32 7, !"PIC Level", i32 2}
+!9 = !{!"clang version 7.0.0 (trunk 324259) (llvm/trunk 324261)"}
+!10 = distinct !DISubprogram(name: "g", scope: !1, file: !1, line: 6, type: !11, isLocal: false, isDefinition: true, scopeLine: 6, isOptimized: true, unit: !0, variables: !2)
+!11 = !DISubroutineType(types: !12)
+!12 = !{null}
+!13 = !DILocation(line: 12, column: 3, scope: !14, inlinedAt: !24)
+!14 = distinct !DISubprogram(name: "h", scope: !1, file: !1, line: 10, type: !11, isLocal: false, isDefinition: true, scopeLine: 10, flags: DIFlagPrototyped, isOptimized: true, unit: !0, variables: !15)
+!15 = !{!16, !18, !20}
+!16 = !DILocalVariable(name: "count", scope: !14, file: !1, line: 11, type: !17)
+!17 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+!18 = !DILocalVariable(name: "vla_expr", scope: !14, file: !1, line: 12, type: !19)
+!19 = !DIBasicType(name: "long unsigned int", size: 64, encoding: DW_ATE_unsigned)
+!20 = !DILocalVariable(name: "array", scope: !14, file: !1, line: 12, type: !21)
+!21 = !DICompositeType(tag: DW_TAG_array_type, baseType: !17, elements: !22)
+!22 = !{!23}
+!23 = !DISubrange(count: !18)
+!24 = distinct !DILocation(line: 7, column: 3, scope: !10)
+!25 = !DILocation(line: 11, column: 7, scope: !14, inlinedAt: !24)
+!26 = !DILocation(line: 13, column: 3, scope: !14, inlinedAt: !24)
+!27 = !DILocation(line: 14, column: 1, scope: !14, inlinedAt: !24)
+!28 = !DILocation(line: 8, column: 1, scope: !10)