[DwarfDebug] Improve single location detection in validThroughout (2/4)

[Orlando]

Summary

With this patch we're now accounting for two more cases which should be
considered 'valid throughout': First, where RangeEnd is ScopeEnd. Second, where
RangeEnd comes before ScopeEnd when including meta instructions, but are both
preceded by the same non-meta instruction.

CTMark shows a geomean binary size reduction of 1.5% for RelWithDebInfo builds.
llvm-locstats (using D85636) shows a very small variable location coverage
change in 2 of 10 binaries, but it is in the order of 10s of bytes which lines
up with my expectations.

I've added a test which checks both of these new cases. The first check in the
test isn't strictly necessary for this patch. But I'm not sure that it is
explicitly tested anywhere else, and is useful for the final patch in the
series.

[Orlando]

Just a note: This patch moves the InstructionOrdering class added in D86150 out from DbgEntityHistoryCalculator.cpp to DbgEntityHistoryCalculator.h so that we're able to use it in DebugHandlerBase.

llvm/include/llvm/CodeGen/DbgEntityHistoryCalculator.h

 
 class DILocalVariable;
 class DILocation;
 class DINode;
 class MachineFunction;
 class MachineInstr;
 class TargetRegisterInfo;
 
+/// Record instruction ordering so we can query their relative positions within
+/// a function. Meta instructions are given the same ordinal as the preceding
+/// non-meta instruction. Class state is invalid if MF is modified after
+/// calling initialize.
+class InstructionOrdering {
+public:
+  void initialize(const MachineFunction &MF);
+  void clear() { InstNumberMap.clear(); }
+
+  /// Check if instruction \p A comes before \p B, where \p A and \p B both
+  /// belong to the MachineFunction passed to initialize().
+  bool isBefore(const MachineInstr *A, const MachineInstr *B) const;
+
+private:
+  /// Each instruction is assigned an order number.
+  DenseMap<const MachineInstr *, unsigned> InstNumberMap;
+};
+
 /// For each user variable, keep a list of instruction ranges where this
 /// variable is accessible. The variables are listed in order of appearance.
 class DbgValueHistoryMap {
 public:
   /// Index in the entry vector.
   typedef size_t EntryIndex;
 
   /// Special value to indicate that an entry is valid until the end of the
public:
   EntryIndex startClobber(InlinedEntity Var, const MachineInstr &MI);
 
   Entry &getEntry(InlinedEntity Var, EntryIndex Index) {
     auto &Entries = VarEntries[Var];
     return Entries[Index];
   }
 
   /// Drop location ranges which exist entirely outside each variable's scope.
-  void trimLocationRanges(const MachineFunction &MF, LexicalScopes &LScopes);
+  void trimLocationRanges(const MachineFunction &MF, LexicalScopes &LScopes,
+                          const InstructionOrdering &Ordering);
   bool empty() const { return VarEntries.empty(); }
   void clear() { VarEntries.clear(); }
   EntriesMap::const_iterator begin() const { return VarEntries.begin(); }
   EntriesMap::const_iterator end() const { return VarEntries.end(); }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   LLVM_DUMP_METHOD void dump() const;
 #endif

llvm/include/llvm/CodeGen/DebugHandlerBase.h

protected:
   void requestLabelAfterInsn(const MachineInstr *MI) {
     LabelsAfterInsn.insert(std::make_pair(MI, nullptr));
   }
 
   virtual void beginFunctionImpl(const MachineFunction *MF) = 0;
   virtual void endFunctionImpl(const MachineFunction *MF) = 0;
   virtual void skippedNonDebugFunction() {}
 
+private:
+  InstructionOrdering InstOrdering;
+
   // AsmPrinterHandler overrides.
 public:
   void beginInstruction(const MachineInstr *MI) override;
   void endInstruction() override;
 
   void beginFunction(const MachineFunction *MF) override;
   void endFunction(const MachineFunction *MF) override;
 
   void beginBasicBlock(const MachineBasicBlock &MBB) override;
   void endBasicBlock(const MachineBasicBlock &MBB) override;
 
   /// Return Label preceding the instruction.
   MCSymbol *getLabelBeforeInsn(const MachineInstr *MI);
 
   /// Return Label immediately following the instruction.
   MCSymbol *getLabelAfterInsn(const MachineInstr *MI);
 
   /// If this type is derived from a base type then return base type size.
   static uint64_t getBaseTypeSize(const DIType *Ty);
+
+  const InstructionOrdering &getInstOrdering() const { return InstOrdering; }
 };
 
-}
+} // namespace llvm
 
 #endif

llvm/lib/CodeGen/AsmPrinter/DbgEntityHistoryCalculator.cpp

static Register isDescribedByReg(const MachineInstr &MI) {
   if (MI.getDebugExpression()->isEntryValue())
     return 0;
   // If location of variable is described using a register (directly or
   // indirectly), this register is always a first operand.
   return MI.getDebugOperand(0).isReg() ? MI.getDebugOperand(0).getReg()
                                        : Register();
 }
 
-/// Record instruction ordering so we can query their relative positions within
-/// a function. Meta instructions are given the same ordinal as the preceding
-/// non-meta instruction. Class state is invalid if MF is modified after
-/// calling initialize.
-class InstructionOrdering {
-public:
-  void initialize(const MachineFunction &MF);
-  void clear() { InstNumberMap.clear(); }
-
-  /// Check if instruction \p A comes before \p B, where \p A and \p B both
-  /// belong to the MachineFunction passed to initialize().
-  bool isBefore(const MachineInstr *A, const MachineInstr *B) const;
-
-private:
-  /// Each instruction is assigned an order number.
-  DenseMap<const MachineInstr *, unsigned> InstNumberMap;
-};
-
 void InstructionOrdering::initialize(const MachineFunction &MF) {
   // We give meta instructions the same ordinal as the preceding instruction
   // because this class is written for the task of comparing positions of
   // variable location ranges against scope ranges. To reflect what we'll see
   // in the binary, when we look at location ranges we must consider all
   // DBG_VALUEs between two real instructions at the same position. And a
   // scope range which ends on a meta instruction should be considered to end
   // at the last seen real instruction. E.g.
for (auto RangesI = Ranges.begin(), RangesE = Ranges.end();
     if (EndMI && !Ordering.isBefore(RangesI->second, EndMI))
       return RangesI;
     if (Ordering.isBefore(StartMI, RangesI->second))
       return RangesI;
   }
   return None;
 }
 
-void DbgValueHistoryMap::trimLocationRanges(const MachineFunction &MF,
-                                            LexicalScopes &LScopes) {
-  InstructionOrdering Ordering;
-  Ordering.initialize(MF);
-
+void DbgValueHistoryMap::trimLocationRanges(
+    const MachineFunction &MF, LexicalScopes &LScopes,
+    const InstructionOrdering &Ordering) {
   // The indices of the entries we're going to remove for each variable.
   SmallVector<EntryIndex, 4> ToRemove;
   // Entry reference count for each variable. Clobbers left with no references
   // will be removed.
   SmallVector<int, 4> ReferenceCount;
   // Entries reference other entries by index. Offsets is used to remap these
   // references if any entries are removed.
   SmallVector<size_t, 4> Offsets;

llvm/lib/CodeGen/AsmPrinter/DebugHandlerBase.cpp

void DebugHandlerBase::beginFunction(const MachineFunction *MF) {
   // Make sure that each lexical scope will have a begin/end label.
   identifyScopeMarkers();
 
   // Calculate history for local variables.
   assert(DbgValues.empty() && "DbgValues map wasn't cleaned!");
   assert(DbgLabels.empty() && "DbgLabels map wasn't cleaned!");
   calculateDbgEntityHistory(MF, Asm->MF->getSubtarget().getRegisterInfo(),
                             DbgValues, DbgLabels);
+  InstOrdering.initialize(*MF);
   if (TrimVarLocs)
-    DbgValues.trimLocationRanges(*MF, LScopes);
+    DbgValues.trimLocationRanges(*MF, LScopes, InstOrdering);
   LLVM_DEBUG(DbgValues.dump());
 
   // Request labels for the full history.
   for (const auto &I : DbgValues) {
     const auto &Entries = I.second;
     if (Entries.empty())
       continue;
 

 
 void DebugHandlerBase::endFunction(const MachineFunction *MF) {
   if (hasDebugInfo(MMI, MF))
     endFunctionImpl(MF);
   DbgValues.clear();
   DbgLabels.clear();
   LabelsBeforeInsn.clear();
   LabelsAfterInsn.clear();
+  InstOrdering.clear();
 }
 
 void DebugHandlerBase::beginBasicBlock(const MachineBasicBlock &MBB) {
   if (!MBB.isBeginSection())
     return;
 
   PrevLabel = MBB.getSymbol();
 }
 
 void DebugHandlerBase::endBasicBlock(const MachineBasicBlock &MBB) {
   if (!MBB.isEndSection())
     return;
 
   PrevLabel = nullptr;
 }

llvm/lib/CodeGen/AsmPrinter/DwarfDebug.cpp

 }
 
 /// Determine whether a *singular* DBG_VALUE is valid for the entirety of its
 /// enclosing lexical scope. The check ensures there are no other instructions
 /// in the same lexical scope preceding the DBG_VALUE and that its range is
 /// either open or otherwise rolls off the end of the scope.
 static bool validThroughout(LexicalScopes &LScopes,
                             const MachineInstr *DbgValue,
-                            const MachineInstr *RangeEnd) {
+                            const MachineInstr *RangeEnd,
+                            const InstructionOrdering &Ordering) {
   assert(DbgValue->getDebugLoc() && "DBG_VALUE without a debug location");
   auto MBB = DbgValue->getParent();
   auto DL = DbgValue->getDebugLoc();
   auto *LScope = LScopes.findLexicalScope(DL);
   // Scope doesn't exist; this is a dead DBG_VALUE.
   if (!LScope)
     return false;
   auto &LSRange = LScope->getRanges();
static bool validThroughout(LexicalScopes &LScopes,
   // outside of the block we can ignore it; the location is just leaking outside
   // its scope.
   assert(LScopeEnd->getParent() == MBB && "Scope ends outside MBB");
   if (RangeEnd->getParent() != DbgValue->getParent())
     return true;
 
   // The location range and variable's enclosing scope are both contained within
   // MBB, test if location terminates before end of scope.
-  for (auto I = RangeEnd->getIterator(); I != MBB->end(); ++I)
-    if (&*I == LScopeEnd)
-      return false;
+  if (Ordering.isBefore(RangeEnd, LScopeEnd))
 
   // There's a single location which starts at the scope start, and ends at or
   // after the scope end.
   return true;
 }
 
 /// Build the location list for all DBG_VALUEs in the function that
 /// describe the same variable. The resulting DebugLocEntries will have
bool DwarfDebug::buildLocationList(
 
   // 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);
+  return validThroughout(LScopes, StartDebugMI, EndMI, getInstOrdering());
 }
 
 DbgEntity *DwarfDebug::createConcreteEntity(DwarfCompileUnit &TheCU,
                                             LexicalScope &Scope,
                                             const DINode *Node,
                                             const DILocation *Location,
                                             const MCSymbol *Sym) {
   ensureAbstractEntityIsCreatedIfScoped(TheCU, Node, Scope.getScopeNode());
for (const auto &I : DbgValues) {
     // additional entry which clobbers the debug value.
     size_t HistSize = HistoryMapEntries.size();
     bool SingleValueWithClobber =
         HistSize == 2 && HistoryMapEntries[1].isClobber();
     if (HistSize == 1 || SingleValueWithClobber) {
       const auto *End =
           SingleValueWithClobber ? HistoryMapEntries[1].getInstr() : nullptr;
       if (VeryLargeBlocks.count(MInsn->getParent()) == 0 &&
-          validThroughout(LScopes, MInsn, End)) {
+          validThroughout(LScopes, MInsn, End, getInstOrdering())) {
         RegVar->initializeDbgValue(MInsn);
         continue;
       }
     }
 
     // Do not emit location lists if .debug_loc secton is disabled.
     if (!useLocSection())
       continue;

llvm/test/DebugInfo/MIR/AArch64/implicit-def-dead-scope.mir

 # RUN: llc -emit-call-site-info -start-after=livedebugvalues -filetype=obj -o - %s \
 # RUN:   | llvm-dwarfdump -v - | FileCheck %s
 
 # This tests for a crash in DwarfDebug's singular DBG_VALUE range promotion when
 #  encountering an IMPLICIT_DEF in its own lexical scope.
 
 # CHECK: .debug_info contents:
-# CHECK:       DW_TAG_formal_parameter
-# CHECK:       DW_AT_location [DW_FORM_sec_offset]
-# CHECK-NEXT:                 DW_OP_lit0, DW_OP_stack_value
+# CHECK:       DW_TAG_formal_parameter [14]
+# CHECK-NEXT:  DW_AT_const_value [DW_FORM_udata]    (0)
 # CHECK-NEXT:  DW_AT_abstract_origin {{.*}} "name"
 --- |
   ; ModuleID = 't.ll'
   source_filename = "t.ll"
   target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
   target triple = "aarch64--linux-gnu"
   
   %class.v = type <{ i32, i8, i8, [2 x i8] }>

llvm/test/DebugInfo/MIR/X86/callsite-stack-value.mir

 # RUN: llc -start-after=livedebugvalues -mtriple=x86_64-apple-darwin -o - %s -filetype=obj \
 # RUN:   -emit-call-site-info | llvm-dwarfdump - | FileCheck %s -implicit-check-not=call_site_parameter
 
 # CHECK: DW_TAG_formal_parameter
-# CHECK-NEXT: DW_AT_location
-# CHECK-NEXT: DW_OP_reg17
+# CHECK-NEXT: DW_AT_location (DW_OP_reg17 XMM0)
 
 # struct S {
 #   float w;
 # };
 # void f(long w, long b);
 # void g(struct S s) {
 #   int w = s.w;
 #   f(w, w*4);

llvm/test/DebugInfo/X86/single-location-2.mir

+# RUN: llc %s --start-after=livedebugvalues -filetype=obj -o - \
+# RUN:     | llvm-dwarfdump - -name local* -regex \
+# RUN:     | FileCheck %s
+#
+## This tests certain single location detection functionality. The Test MIR
+## is hand written. Test directives and comments inline.
+
+--- |
+  target triple = "x86_64-unknown-linux-gnu"
+  define dso_local i32 @fun() local_unnamed_addr !dbg !7 {
+  entry:
+    ret i32 0
+  }
+
+  !llvm.dbg.cu = !{!0}
+  !llvm.module.flags = !{!3, !4, !5}
+  !llvm.ident = !{!6}
+
+  !0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 11.0.0", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, splitDebugInlining: false, nameTableKind: None)
+  !1 = !DIFile(filename: "example.c", directory: "/")
+  !3 = !{i32 7, !"Dwarf Version", i32 4}
+  !4 = !{i32 2, !"Debug Info Version", i32 3}
+  !5 = !{i32 1, !"wchar_size", i32 4}
+  !6 = !{!"clang version 11.0.0"}
+  !8 = !DISubroutineType(types: !9)
+  !9 = !{!10}
+  !10 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+  !22 = !DISubroutineType(types: !23)
+  !23 = !{!10, !10}
+  ; --- Important metadata ---
+  !7 = distinct !DISubprogram(name: "fun", scope: !1, file: !1, line: 2, type: !8, scopeLine: 2, flags: DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0)
+  !24 = distinct !DILexicalBlock(scope: !7, file: !1, line: 9, column: 3)
+  !14 = distinct !DILexicalBlock(scope: !7, file: !1, line: 4, column: 3)
+  !12 = !DILocalVariable(name: "locala", scope: !7, file: !1, line: 1, type: !10)
+  !13 = !DILocalVariable(name: "localb", scope: !14, file: !1, line: 2, type: !10)
+  !25 = !DILocalVariable(name: "localc", scope: !24, file: !1, line: 3, type: !10)
+  !27 = !DILocalVariable(name: "tmp",    scope: !14, file: !1, line: 2, type: !10)
+  !15 = !DILocation(line: 1, column: 0, scope: !7)
+  !18 = !DILocation(line: 2, column: 1, scope: !14)
+  !26 = !DILocation(line: 3, column: 1, scope: !24)
+...
+---
+name:            fun
+body:             |
+  bb.0.entry:
+    ;; This is the scope and variable structure:
+    ;; int fun() {       // scope fun !7
+    ;;   int locala;     // scope fun !7,        var locala !12, debug-location !15
+    ;;   { int localb;   // scope fun:block !14, var localb !13, debug-location !18
+    ;;     int tmp;    } // scope fun:block !14, var localb !27, debug-location !18
+    ;;   { int localc; } // scope fun:block !24, var localc !25, debug-location !26
+    ;; }
+    ;;
+    ;; (1) Check that frame-setup instructions are not counted against
+    ;;     locations being valid throughout the function call.
+    ;
+    ; CHECK:      DW_TAG_variable
+    ; CHECK-NEXT:   DW_AT_location (DW_OP_reg5 RDI)
+    ; CHECK-NEXT:   DW_AT_name ("locala")
+    $rbp = frame-setup MOV64rr $rsp
+    DBG_VALUE $edi, $noreg, !12, !DIExpression(), debug-location !15
+    $eax = MOV32ri 0, debug-location !15
+
+    ;; (2) The scope block ends with a meta instruction. A location range ends
+    ;;     with the final non-meta instruction in the scope. Check that
+    ;;     location is considered valid throughout.
+    ;
+    ; CHECK:      DW_TAG_variable
+    ; CHECK-NEXT:   DW_AT_location (DW_OP_reg2 RCX)
+    ; CHECK-NEXT:   DW_AT_name ("localb")
+    ;
+    ;; start scope, start location range
+    DBG_VALUE $ecx, $noreg, !13, !DIExpression(), debug-location !18
+    ;; end location range
+    $ecx = MOV32ri 1, debug-location !18
+    ;; end scope
+    DBG_VALUE $noreg, $noreg, !27, !DIExpression(), debug-location !18
+
+    ;; (3) The final instruction in the scope closes a location range. Check
+    ;;     that location is considered valid throughout.
+    ;
+    ; CHECK:      DW_TAG_variable
+    ; CHECK-NEXT:   DW_AT_location (DW_OP_reg4 RSI)
+    ; CHECK-NEXT:   DW_AT_name ("localc")
+    ;
+    ;; start scope, start location range
+    DBG_VALUE $esi, $noreg, !25, !DIExpression(), debug-location !26
+    ;; end scope, end location range
+    $esi = MOV32ri 2, debug-location !26
+
+    RETQ debug-location !15
+...

llvm/test/DebugInfo/X86/trim-var-locs.mir

bb.0.entry:
     DBG_VALUE $eax, $noreg, !13, !DIExpression(), debug-location !18
     ; localb range 1 clobber in scope fun !7
     $edi = MOV32ri 4, debug-location !15
 
     ; (3) Check that a variable location range which overlaps the entire lexical
     ;     block is not trimmed.
     ;
     ; CHECK:      DW_TAG_variable
-    ; CHECK-NEXT:   DW_AT_location
-    ; CHECK-NEXT:     DW_OP_reg5 RDI
+    ; CHECK-NEXT:   DW_AT_location (DW_OP_reg5 RDI)
     ; CHECK-NEXT:   DW_AT_name ("localb")
     ;
     ; localb range 2 clobber in scope fun !7 (outside block !14)
     DBG_VALUE $edi, $noreg, !13, !DIExpression(), debug-location !18
     ; scope block !14 start (and only instruction)
     $edi = MOV32ri 5, debug-location !18
 
     ; (4) Check that a variable location range in scope fun !7 (outside block