Index: lib/CodeGen/AsmPrinter/DwarfCompileUnit.cpp =================================================================== --- lib/CodeGen/AsmPrinter/DwarfCompileUnit.cpp +++ lib/CodeGen/AsmPrinter/DwarfCompileUnit.cpp @@ -568,25 +568,79 @@ return Var; } -/// Determine whether a variable appears in a count: expression. -static bool dependsOn(DbgVariable *A, DbgVariable *B) { - auto *Array = dyn_cast(A->getType()); +/// Return all DIVariables that appear in count: expressions. +static SmallVector dependencies(DbgVariable *Var) { + SmallVector Result; + auto *Array = dyn_cast(Var->getType()); if (!Array || Array->getTag() != dwarf::DW_TAG_array_type) - return false; - return llvm::any_of(Array->getElements(), [&](DINode *El) { + return Result; + for (auto *El : Array->getElements()) { if (auto *Subrange = dyn_cast(El)) { auto Count = Subrange->getCount(); - if (auto *Var = Count.dyn_cast()) - return Var == B->getVariable(); + if (auto *Dependency = Count.dyn_cast()) + Result.push_back(Dependency); } - return false; - }); + } + return Result; } /// Sort local variables so that variables appearing inside of helper /// expressions come first. -static bool sortLocalVars(DbgVariable *A, DbgVariable *B) { - return dependsOn(B, A); +static SmallVector +sortLocalVars(SmallVectorImpl &Input) { + SmallVector Result; + SmallVector, 8> WorkList; + // Map back from a DIVariable to its containing DbgVariable. + SmallDenseMap DbgVar; + // Set of DbgVariables in Result. + SmallDenseSet Visited; + // For cycle detection. + SmallDenseSet Visiting; + + // Initialize the worklist and the DIVariable lookup table. + for (auto Var : reverse(Input)) { + DbgVar.insert({Var->getVariable(), Var}); + WorkList.push_back({Var, 0}); + } + + // Perform a stable topological sort by doing a DFS. + while (!WorkList.empty()) { + auto Item = WorkList.back(); + DbgVariable *Var = Item.getPointer(); + bool visitedAllDependencies = Item.getInt(); + WorkList.pop_back(); + + // Dependency is in a different lexical scope or a global. + if (!Var) + continue; + + // Already handled. + if (Visited.count(Var)) + continue; + + // Add to Result if all dependencies are visited. + if (visitedAllDependencies) { + Visited.insert(Var); + Result.push_back(Var); + continue; + } + + // Detect cycles. + auto Res = Visiting.insert(Var); + if (!Res.second) { + assert(false && "dependency cycle in local variables"); + return Result; + } + + // Push dependencies and this node onto the worklist, so that this node is + // visited again after all of its dependencies are handled. + WorkList.push_back({Var, 1}); + for (auto *Dependency : dependencies(Var)) { + auto Dep = dyn_cast_or_null(Dependency); + WorkList.push_back({DbgVar[Dep], 0}); + } + } + return Result; } DIE *DwarfCompileUnit::createScopeChildrenDIE(LexicalScope *Scope, @@ -601,8 +655,8 @@ 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) + auto Locals = sortLocalVars(Vars.Locals); + for (DbgVariable *DV : Locals) Children.push_back(constructVariableDIE(*DV, *Scope, ObjectPointer)); // Skip imported directives in gmlt-like data. Index: test/DebugInfo/X86/vla-dependencies.ll =================================================================== --- test/DebugInfo/X86/vla-dependencies.ll +++ test/DebugInfo/X86/vla-dependencies.ll @@ -2,16 +2,16 @@ ; 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") +; CHECK-NEXT: DW_AT_name ("vla_expr") +; CHECK: DW_TAG_array_type +; CHECK-NEXT: DW_AT_type {{.*}}"int" +; CHECK-NOT: DW_TAG +; CHECK: DW_TAG_subrange_type +; CHECK-NEXT: DW_AT_type {{.*}}"sizetype" +; CHECK-NEXT: DW_AT_count (cu + 0x0[[VLAEXPR]]) ; -;0x000000b6: DW_TAG_subrange_type -; DW_AT_type (cu + 0x0079 "sizetype") -; DW_AT_count (cu + 0x[[VLAEXPR]]) ; -; -; Generated from: +; Generated from (and then modified): ; ; #define DECLARE_ARRAY(type, var_name, size) type var_name[size] ; @@ -40,6 +40,8 @@ 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 @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 Index: test/DebugInfo/X86/vla-global.ll =================================================================== --- /dev/null +++ test/DebugInfo/X86/vla-global.ll @@ -0,0 +1,65 @@ +; RUN: llc -mtriple=x86_64-apple-darwin %s -o - -filetype=obj | llvm-dwarfdump - | FileCheck %s +; CHECK: 0x00000[[G:.*]]: DW_TAG_variable +; CHECK-NEXT: DW_AT_name ("g") +; CHECK: DW_TAG_array_type +; CHECK-NEXT: DW_AT_type (cu + {{.*}} "int") +; CHECK-NOT: DW_TAG +; CHECK: DW_TAG_subrange_type +; CHECK-NEXT: DW_AT_type (cu + {{.*}} "sizetype") +; CHECK-NEXT: DW_AT_count (cu + 0x0[[G]]) +; Test that a VLA referring to a global variable is handled correctly. +; Clang doesn't generate this, but the verifier allows it. +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" + +@g = common local_unnamed_addr global i32 0, align 4, !dbg !0 + +define void @f() !dbg !12 { +entry: + %0 = load i32, i32* @g, align 4, !dbg !22 + %1 = zext i32 %0 to i64, !dbg !22 + %vla = alloca i32, i64 %1, align 16, !dbg !22 + call void @llvm.dbg.declare(metadata i32* %vla, metadata !16, metadata !DIExpression()), !dbg !22 + call void @llvm.dbg.value(metadata i32 2, metadata !21, metadata !DIExpression()), !dbg !22 + %call = call i32 (i32*, ...) bitcast (i32 (...)* @use to i32 (i32*, ...)*)(i32* nonnull %vla), !dbg !22 + ret void, !dbg !22 +} + +; Function Attrs: nounwind readnone speculatable +declare void @llvm.dbg.declare(metadata, metadata, metadata) #0 + +declare i32 @use(...) local_unnamed_addr + +; Function Attrs: nounwind readnone speculatable +declare void @llvm.dbg.value(metadata, metadata, metadata) #0 + +attributes #0 = { nounwind readnone speculatable } + +!llvm.dbg.cu = !{!2} +!llvm.module.flags = !{!7, !8, !9, !10} +!llvm.ident = !{!11} + +!0 = !DIGlobalVariableExpression(var: !1, expr: !DIExpression()) +!1 = distinct !DIGlobalVariable(name: "g", scope: !2, file: !3, line: 1, type: !6, isLocal: false, isDefinition: true) +!2 = distinct !DICompileUnit(language: DW_LANG_C99, file: !3, producer: "clang version 7.0.0 (trunk 324259) (llvm/trunk 324261)", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !4, globals: !5) +!3 = !DIFile(filename: "/tmp/test.c", directory: "/") +!4 = !{} +!5 = !{!0} +!6 = !DIBasicType(name: "unsigned int", size: 32, encoding: DW_ATE_unsigned) +!7 = !{i32 2, !"Dwarf Version", i32 4} +!8 = !{i32 2, !"Debug Info Version", i32 3} +!9 = !{i32 1, !"wchar_size", i32 4} +!10 = !{i32 7, !"PIC Level", i32 2} +!11 = !{!"clang version 7.0.0 (trunk 324259) (llvm/trunk 324261)"} +!12 = distinct !DISubprogram(name: "f", scope: !3, file: !3, line: 3, type: !13, isLocal: false, isDefinition: true, scopeLine: 3, isOptimized: true, unit: !2, variables: !15) +!13 = !DISubroutineType(types: !14) +!14 = !{null} +!15 = !{!16, !21} +!16 = !DILocalVariable(name: "array", scope: !12, file: !3, line: 4, type: !17) +!17 = !DICompositeType(tag: DW_TAG_array_type, baseType: !18, elements: !19) +!18 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed) +!19 = !{!20} +!20 = !DISubrange(count: !1) +!21 = !DILocalVariable(name: "count", scope: !12, file: !3, line: 5, type: !18) +!22 = !DILocation(line: 7, column: 1, scope: !12) Index: test/DebugInfo/X86/vla-multi.ll =================================================================== --- /dev/null +++ test/DebugInfo/X86/vla-multi.ll @@ -0,0 +1,136 @@ +; RUN: llc -mtriple=x86_64-apple-darwin %s -o - -filetype=obj | llvm-dwarfdump - | FileCheck %s +; Test debug info for multidimensional arrays. +; +; void f(int i, int j, int k, int r) { +; int tensor1[i][j][k][r]; +; int tensor2[i][j][k][r]; +; use(tensor1, tensor2); +;} +; +; CHECK: DW_TAG_array_type +; CHECK-NEXT: DW_AT_type (cu + 0x00f8 "int") +; CHECK-NOT: TAG +; CHECK: DW_TAG_subrange_type +; CHECK-NEXT: DW_AT_type (cu + {{.*}}"sizetype") +; CHECK-NEXT: DW_AT_count (cu + {{.*}}) +; CHECK-NOT: TAG +; CHECK: DW_TAG_subrange_type +; CHECK-NEXT: DW_AT_type (cu + {{.*}} "sizetype") +; CHECK-NEXT: DW_AT_count (cu + {{.*}}) +; CHECK-NOT: TAG +; CHECK: DW_TAG_subrange_type +; CHECK-NEXT: DW_AT_type (cu + {{.*}} "sizetype") +; CHECK-NEXT: DW_AT_count (cu + {{.*}}) +; CHECK-NOT: TAG +; CHECK: DW_TAG_subrange_type +; CHECK-NEXT: DW_AT_type (cu + {{.*}} "sizetype") +; CHECK-NEXT: DW_AT_count (cu + {{.*}}) +; CHECK: DW_TAG_array_type +; CHECK-NEXT: DW_AT_type (cu + 0x00f8 "int") +; CHECK-NOT: TAG +; CHECK: DW_TAG_subrange_type +; CHECK-NEXT: DW_AT_type (cu + {{.*}}"sizetype") +; CHECK-NEXT: DW_AT_count (cu + {{.*}}) +; CHECK-NOT: TAG +; CHECK: DW_TAG_subrange_type +; CHECK-NEXT: DW_AT_type (cu + {{.*}} "sizetype") +; CHECK-NEXT: DW_AT_count (cu + {{.*}}) +; CHECK-NOT: TAG +; CHECK: DW_TAG_subrange_type +; CHECK-NEXT: DW_AT_type (cu + {{.*}} "sizetype") +; CHECK-NEXT: DW_AT_count (cu + {{.*}}) +; CHECK-NOT: TAG +; CHECK: DW_TAG_subrange_type +; CHECK-NEXT: DW_AT_type (cu + {{.*}} "sizetype") +; CHECK-NEXT: DW_AT_count (cu + {{.*}}) + + +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" + +define void @f(i32 %i, i32 %j, i32 %k, i32 %r) !dbg !8 { +entry: + call void @llvm.dbg.value(metadata i32 %i, metadata !39, metadata !DIExpression()), !dbg !40 + call void @llvm.dbg.value(metadata i32 %j, metadata !38, metadata !DIExpression()), !dbg !40 + call void @llvm.dbg.value(metadata i32 %k, metadata !37, metadata !DIExpression()), !dbg !40 + call void @llvm.dbg.value(metadata i32 %r, metadata !36, metadata !DIExpression()), !dbg !40 + %0 = zext i32 %i to i64, !dbg !40 + %1 = zext i32 %j to i64, !dbg !40 + %2 = zext i32 %k to i64, !dbg !40 + %3 = zext i32 %r to i64, !dbg !40 + %4 = mul nuw i64 %1, %0, !dbg !40 + %5 = mul nuw i64 %4, %2, !dbg !40 + %6 = mul nuw i64 %5, %3, !dbg !40 + %vla = alloca i32, i64 %6, align 16, !dbg !40 + call void @llvm.dbg.declare(metadata i32* %vla, metadata !25, metadata !DIExpression()), !dbg !40 + call void @llvm.dbg.declare(metadata i32* %vla4, metadata !13, metadata !DIExpression()), !dbg !40 + %vla4 = alloca i32, i64 %6, align 16, !dbg !40 + call void @llvm.dbg.value(metadata i32 %i, metadata !29, metadata !DIExpression()), !dbg !40 + call void @llvm.dbg.value(metadata i32 %j, metadata !31, metadata !DIExpression()), !dbg !40 + call void @llvm.dbg.value(metadata i32 %k, metadata !33, metadata !DIExpression()), !dbg !40 + call void @llvm.dbg.value(metadata i32 %r, metadata !35, metadata !DIExpression()), !dbg !40 + call void @llvm.dbg.value(metadata i32 %i, metadata !17, metadata !DIExpression()), !dbg !40 + call void @llvm.dbg.value(metadata i32 %j, metadata !20, metadata !DIExpression()), !dbg !40 + call void @llvm.dbg.value(metadata i32 %k, metadata !22, metadata !DIExpression()), !dbg !40 + call void @llvm.dbg.value(metadata i64 %3, metadata !24, metadata !DIExpression()), !dbg !40 + %call = call i32 (i32*, i32*, ...) bitcast (i32 (...)* @use to i32 (i32*, i32*, ...)*)(i32* nonnull %vla, i32* nonnull %vla4) #1, !dbg !40 + ret void, !dbg !40 +} + +; Function Attrs: nounwind readnone speculatable +declare void @llvm.dbg.declare(metadata, metadata, metadata) #0 + +declare i32 @use(...) local_unnamed_addr + +; Function Attrs: nounwind readnone speculatable +declare void @llvm.dbg.value(metadata, metadata, metadata) #0 + +attributes #0 = { nounwind readnone speculatable } +attributes #1 = { minsize nounwind optsize } + +!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 7.0.0 (trunk 324259) (llvm/trunk 324261)", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2) +!1 = !DIFile(filename: "/tmp/test.c", directory: "/") +!2 = !{} +!3 = !{i32 2, !"Dwarf Version", i32 4} +!4 = !{i32 2, !"Debug Info Version", i32 3} +!5 = !{i32 1, !"wchar_size", i32 4} +!6 = !{i32 7, !"PIC Level", i32 2} +!7 = !{!"clang version 7.0.0 (trunk 324259) (llvm/trunk 324261)"} +!8 = distinct !DISubprogram(name: "f", scope: !1, file: !1, line: 1, type: !9, isLocal: false, isDefinition: true, scopeLine: 1, flags: DIFlagPrototyped, isOptimized: true, unit: !0, variables: !12) +!9 = !DISubroutineType(types: !10) +!10 = !{null, !11, !11, !11, !11} +!11 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed) +!12 = !{!13, !24, !22, !20, !17, !25, !35, !33, !31, !29, !36, !37, !38, !39} +!13 = !DILocalVariable(name: "tensor2", scope: !8, file: !1, line: 3, type: !14) +!14 = !DICompositeType(tag: DW_TAG_array_type, baseType: !11, elements: !15) +!15 = !{!16, !19, !21, !23} +!16 = !DISubrange(count: !17) +!17 = !DILocalVariable(name: "vla_expr5", scope: !8, file: !1, line: 3, type: !18) +!18 = !DIBasicType(name: "long unsigned int", size: 64, encoding: DW_ATE_unsigned) +!19 = !DISubrange(count: !20) +!20 = !DILocalVariable(name: "vla_expr6", scope: !8, file: !1, line: 3, type: !18) +!21 = !DISubrange(count: !22) +!22 = !DILocalVariable(name: "vla_expr7", scope: !8, file: !1, line: 3, type: !18) +!23 = !DISubrange(count: !24) +!24 = !DILocalVariable(name: "vla_expr8", scope: !8, file: !1, line: 3, type: !18) +!25 = !DILocalVariable(name: "tensor1", scope: !8, file: !1, line: 2, type: !26) +!26 = !DICompositeType(tag: DW_TAG_array_type, baseType: !11, elements: !27) +!27 = !{!28, !30, !32, !34} +!28 = !DISubrange(count: !29) +!29 = !DILocalVariable(name: "vla_expr", scope: !8, file: !1, line: 2, type: !18) +!30 = !DISubrange(count: !31) +!31 = !DILocalVariable(name: "vla_expr1", scope: !8, file: !1, line: 2, type: !18) +!32 = !DISubrange(count: !33) +!33 = !DILocalVariable(name: "vla_expr2", scope: !8, file: !1, line: 2, type: !18) +!34 = !DISubrange(count: !35) +!35 = !DILocalVariable(name: "vla_expr3", scope: !8, file: !1, line: 2, type: !18) +!36 = !DILocalVariable(name: "r", arg: 4, scope: !8, file: !1, line: 1, type: !11) +!37 = !DILocalVariable(name: "k", arg: 3, scope: !8, file: !1, line: 1, type: !11) +!38 = !DILocalVariable(name: "j", arg: 2, scope: !8, file: !1, line: 1, type: !11) +!39 = !DILocalVariable(name: "i", arg: 1, scope: !8, file: !1, line: 1, type: !11) +!40 = !DILocation(line: 2, column: 3, scope: !8)