From b9d977b0ca60c54f11615ca9d144c9f08b29fd85 Mon Sep 17 00:00:00 2001 From: Jeremy Morse Date: Wed, 8 Jul 2020 10:01:14 +0100 Subject: [PATCH] [DWARF] Add cuttoff guarding quadratic validThroughout behaviour Occasionally we see absolutely massive basic blocks, typically in global constructors that are vulnerable to heavy inlining. When these blocks are dense with DBG_VALUE instructions, we can hit near quadratic complexity in DwarfDebug's validThroughout function. The problem is caused by: * validThroughout having to step through all instructions in the block to examine their lexical scope, * and a high proportion of instructions in that block being DBG_VALUEs for a unique variable fragment, Leading to us stepping through every instruction in the block, for (nearly) each instruction in the block. By adding this guard, we force variables in large blocks to use a location list rather than a single-location expression, as shown in the added test. This shouldn't change the meaning of the output DWARF at all: instead we use a less efficient DWARF encoding to avoid a poor-performance code path. Differential Revision: https://reviews.llvm.org/D83236 --- llvm/lib/CodeGen/AsmPrinter/DwarfDebug.cpp | 34 +++++++++-- llvm/lib/CodeGen/AsmPrinter/DwarfDebug.h | 6 +- .../DebugInfo/MIR/X86/singlelocation-cutoffs.mir | 65 ++++++++++++++++++++++ 3 files changed, 97 insertions(+), 8 deletions(-) create mode 100644 llvm/test/DebugInfo/MIR/X86/singlelocation-cutoffs.mir diff --git a/llvm/lib/CodeGen/AsmPrinter/DwarfDebug.cpp b/llvm/lib/CodeGen/AsmPrinter/DwarfDebug.cpp index 80935f8..45ed525 100644 --- a/llvm/lib/CodeGen/AsmPrinter/DwarfDebug.cpp +++ b/llvm/lib/CodeGen/AsmPrinter/DwarfDebug.cpp @@ -167,6 +167,11 @@ static cl::opt "Abstract subprograms")), cl::init(DefaultLinkageNames)); +static cl::opt LocationAnalysisSizeLimit( + "singlevarlocation-input-bb-limit", + cl::desc("Maximum block size to analyze for single-location variables"), + cl::init(30000), cl::Hidden); + static const char *const DWARFGroupName = "dwarf"; static const char *const DWARFGroupDescription = "DWARF Emission"; static const char *const DbgTimerName = "writer"; @@ -1637,8 +1642,10 @@ static bool validThroughout(LexicalScopes &LScopes, // [1-3) [(reg0, fragment 0, 32), (reg1, fragment 32, 32)] // [3-4) [(reg1, fragment 32, 32), (123, fragment 64, 32)] // [4-) [(@g, fragment 0, 96)] -bool DwarfDebug::buildLocationList(SmallVectorImpl &DebugLoc, - const DbgValueHistoryMap::Entries &Entries) { +bool DwarfDebug::buildLocationList( + SmallVectorImpl &DebugLoc, + const DbgValueHistoryMap::Entries &Entries, + DenseSet &VeryLargeBlocks) { using OpenRange = std::pair; SmallVector OpenRanges; @@ -1734,8 +1741,14 @@ bool DwarfDebug::buildLocationList(SmallVectorImpl &DebugLoc, DebugLoc.pop_back(); } - return DebugLoc.size() == 1 && isSafeForSingleLocation && - validThroughout(LScopes, StartDebugMI, EndMI); + // If there's a single entry, safe for a single location, and not part of + // an over-sized basic block, then ask validThroughout whether this + // location can be represented as a single variable location. + if (DebugLoc.size() != 1 || !isSafeForSingleLocation) + return false; + if (VeryLargeBlocks.count(StartDebugMI->getParent())) + return false; + return validThroughout(LScopes, StartDebugMI, EndMI); } DbgEntity *DwarfDebug::createConcreteEntity(DwarfCompileUnit &TheCU, @@ -1767,6 +1780,13 @@ void DwarfDebug::collectEntityInfo(DwarfCompileUnit &TheCU, // Grab the variable info that was squirreled away in the MMI side-table. collectVariableInfoFromMFTable(TheCU, Processed); + // Identify blocks that are unreasonably sized, so that we can later + // skip lexical scope analysis over them. + DenseSet VeryLargeBlocks; + for (const auto &MBB : *CurFn) + if (MBB.size() > LocationAnalysisSizeLimit) + VeryLargeBlocks.insert(&MBB); + for (const auto &I : DbgValues) { InlinedEntity IV = I.first; if (Processed.count(IV)) @@ -1803,7 +1823,8 @@ void DwarfDebug::collectEntityInfo(DwarfCompileUnit &TheCU, if (HistSize == 1 || SingleValueWithClobber) { const auto *End = SingleValueWithClobber ? HistoryMapEntries[1].getInstr() : nullptr; - if (validThroughout(LScopes, MInsn, End)) { + if (VeryLargeBlocks.count(MInsn->getParent()) == 0 && + validThroughout(LScopes, MInsn, End)) { RegVar->initializeDbgValue(MInsn); continue; } @@ -1818,7 +1839,8 @@ void DwarfDebug::collectEntityInfo(DwarfCompileUnit &TheCU, // Build the location list for this variable. SmallVector Entries; - bool isValidSingleLocation = buildLocationList(Entries, HistoryMapEntries); + bool isValidSingleLocation = + buildLocationList(Entries, HistoryMapEntries, VeryLargeBlocks); // Check whether buildLocationList managed to merge all locations to one // that is valid throughout the variable's scope. If so, produce single diff --git a/llvm/lib/CodeGen/AsmPrinter/DwarfDebug.h b/llvm/lib/CodeGen/AsmPrinter/DwarfDebug.h index bb0f550..d7a4b2a 100644 --- a/llvm/lib/CodeGen/AsmPrinter/DwarfDebug.h +++ b/llvm/lib/CodeGen/AsmPrinter/DwarfDebug.h @@ -592,8 +592,10 @@ class DwarfDebug : public DebugHandlerBase { /// function that describe the same variable. If the resulting /// list has only one entry that is valid for entire variable's /// scope return true. - bool buildLocationList(SmallVectorImpl &DebugLoc, - const DbgValueHistoryMap::Entries &Entries); + bool buildLocationList( + SmallVectorImpl &DebugLoc, + const DbgValueHistoryMap::Entries &Entries, + DenseSet &VeryLargeBlocks); /// Collect variable information from the side table maintained by MF. void collectVariableInfoFromMFTable(DwarfCompileUnit &TheCU, diff --git a/llvm/test/DebugInfo/MIR/X86/singlelocation-cutoffs.mir b/llvm/test/DebugInfo/MIR/X86/singlelocation-cutoffs.mir new file mode 100644 index 0000000..6ad64d9 --- /dev/null +++ b/llvm/test/DebugInfo/MIR/X86/singlelocation-cutoffs.mir @@ -0,0 +1,65 @@ +# Test cutoffs for single-location variable analysis. +# Disable validThroughout if the input size exceeds the specified limit + +# RUN: llc %s -o - -start-after=livedebugvalues -mtriple=x86_64-unknown-unknown \ +# RUN: --singlevarlocation-input-bb-limit=0 -filetype=obj\ +# RUN: | llvm-dwarfdump -v -\ +# RUN: | FileCheck %s -check-prefix=LIMITED + +# RUN: llc %s -o - -start-after=livedebugvalues -mtriple=x86_64-unknown-unknown \ +# RUN: --singlevarlocation-input-bb-limit=20 -filetype=obj | llvm-dwarfdump -v -\ +# RUN: | FileCheck %s -check-prefix=UNLIMITED + +# LIMITED: DW_AT_location [DW_FORM_sec_offset] + +# UNLIMITED: DW_AT_location [DW_FORM_exprloc] + +--- | + target datalayout = "e-m:o-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128" + + declare i32 @use(i32) + + define i32 @foo(i32 %x) !dbg !6 { + entry: + ret i32 1, !dbg !15 + } + + declare void @llvm.dbg.value(metadata, metadata, metadata) + + !llvm.dbg.cu = !{!0} + !llvm.debugify = !{!3, !4} + !llvm.module.flags = !{!5} + + !0 = distinct !DICompileUnit(language: DW_LANG_C, file: !1, producer: "debugify", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2) + !1 = !DIFile(filename: "/tmp/t.ll", directory: "/") + !2 = !{} + !3 = !{i32 4} + !4 = !{i32 2} + !5 = !{i32 2, !"Debug Info Version", i32 3} + !6 = distinct !DISubprogram(name: "foo", linkageName: "foo", scope: null, file: !1, line: 1, type: !7, scopeLine: 1, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !8) + !7 = !DISubroutineType(types: !2) + !8 = !{!9, !11} + !9 = !DILocalVariable(name: "1", scope: !6, file: !1, line: 1, type: !10) + !10 = !DIBasicType(name: "ty32", size: 32, encoding: DW_ATE_unsigned) + !11 = !DILocalVariable(name: "2", scope: !6, file: !1, line: 3, type: !10) + !12 = !DILocation(line: 1, column: 1, scope: !6) + !13 = !DILocation(line: 2, column: 1, scope: !6) + !14 = !DILocation(line: 3, column: 1, scope: !6) + !15 = !DILocation(line: 4, column: 1, scope: !6) + +... +--- +name: foo +liveins: + - { reg: '$edi', virtual-reg: '' } +stack: + - { id: 0, name: '', type: spill-slot, offset: -12, size: 4, alignment: 4, + stack-id: default, callee-saved-register: '', callee-saved-restored: true, + debug-info-variable: '', debug-info-expression: '', debug-info-location: '' } +body: | + bb.0.entry: + liveins: $edi + DBG_VALUE renamable $edi, $noreg, !11, !DIExpression(), debug-location !14 + RETQ debug-location !14 + +... -- 2.7.4