[WIP][DebugInfo] LiveDebugValues should allow different variable fragments to have different locations

[jmorse]

Summary

[Work in progress, not really up for review]

Here's a patch that makes LiveDebugValues recognise different variable fragments as having different locations, allowing it to propagate fragments independently (see: the regression test).

There's an obvious flaw with this : *overlapping* fragments will be recognised as being different fragments, and will get propagated, leading to unsound locations being extended. What's not clear to me is whether this is best dealt with at a different layer, which I'll write up in the bug report at https://bugs.llvm.org/show_bug.cgi?id=41979

[jmorse]

Superceeded by D62904, I felt it cleaner to upload a new review req.

include/llvm/IR/DebugInfoMetadata.h

public:
   /// Check if fragments overlap between this DIExpression and \p Other.
   bool fragmentsOverlap(const DIExpression *Other) const {
     if (!isFragment() || !Other->isFragment())
       return true;
     return fragmentCmp(Other) == 0;
   }
 };
 
+inline bool operator==(const DIExpression::FragmentInfo &A,
+                       const struct DIExpression::FragmentInfo &B) {
+  return std::tie(A.SizeInBits, A.OffsetInBits) ==
+         std::tie(B.SizeInBits, B.OffsetInBits);
+}
+
+inline bool operator<(const struct DIExpression::FragmentInfo &A,
+                      const struct DIExpression::FragmentInfo &B) {
+  return std::tie(A.SizeInBits, A.OffsetInBits) <
+         std::tie(B.SizeInBits, B.OffsetInBits);
+}
+
+template <> struct DenseMapInfo<struct DIExpression::FragmentInfo> {
+  using FragInfo = struct DIExpression::FragmentInfo;
+  static const uint64_t MaxVal = std::numeric_limits<uint64_t>::max();
+
+  static inline FragInfo getEmptyKey() { return {MaxVal, MaxVal}; }
+
+  static inline FragInfo getTombstoneKey() { return {MaxVal - 1, MaxVal - 1}; }
+
+  static unsigned getHashValue(const FragInfo &Frag) {
+    return hash_value(std::make_pair(Frag.SizeInBits, Frag.OffsetInBits));
+  }
+
+  static bool isEqual(const FragInfo &A, const FragInfo &B) { return A == B; }
+};
+
 /// Global variables.
 ///
 /// TODO: Remove DisplayName.  It's always equal to Name.
 class DIGlobalVariable : public DIVariable {
   friend class LLVMContextImpl;
   friend class MDNode;
 
   bool IsLocalToUnit;

lib/CodeGen/LiveDebugValues.cpp

 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <cassert>
 #include <cstdint>
 #include <functional>
 #include <queue>
+#include <tuple>
 #include <utility>
 #include <vector>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "livedebugvalues"
 
 STATISTIC(NumInserted, "Number of DBG_VALUE instructions inserted");
public:
     bool dominates(MachineBasicBlock *MBB) {
       if (LBlocks.empty())
         LS.getMachineBasicBlocks(DL, LBlocks);
       return LBlocks.count(MBB) != 0 || LS.dominates(DL, MBB);
     }
   };
 
   /// Based on std::pair so it can be used as an index into a DenseMap.
+  using FragInfo = DIExpression::FragmentInfo;
+  using OptFragInfo = Optional<DIExpression::FragmentInfo>;
   using DebugVariableBase =
-      std::pair<const DILocalVariable *, const DILocation *>;
+      std::tuple<const DILocalVariable *, OptFragInfo, const DILocation *>;
+  friend struct llvm::DenseMapInfo<DebugVariableBase>;
+
   /// A potentially inlined instance of a variable.
   struct DebugVariable : public DebugVariableBase {
-    DebugVariable(const DILocalVariable *Var, const DILocation *InlinedAt)
-        : DebugVariableBase(Var, InlinedAt) {}
-
-    const DILocalVariable *getVar() const { return this->first; }
-    const DILocation *getInlinedAt() const { return this->second; }
-
-    bool operator<(const DebugVariable &DV) const {
-      if (getVar() == DV.getVar())
-        return getInlinedAt() < DV.getInlinedAt();
-      return getVar() < DV.getVar();
-    }
+    DebugVariable(const DILocalVariable *Var, const DIExpression *DIExpr,
+                  const DILocation *InlinedAt)
+        : DebugVariableBase(Var, DIExpr->getFragmentInfo(), InlinedAt) {}
+
+    DebugVariable(const MachineInstr &MI)
+        : DebugVariableBase(MI.getDebugVariable(),
+                            MI.getDebugExpression()->getFragmentInfo(),
+                            MI.getDebugLoc()->getInlinedAt()) {}
+
+    const DILocalVariable *getVar() const { return std::get<0>(*this); }
+    const OptFragInfo *getFrag() const { return &std::get<1>(*this); }
+    const DILocation *getInlinedAt() const { return std::get<2>(*this); }
   };
 
   /// A pair of debug variable and value location.
   struct VarLoc {
     // The location at which a spilled variable resides. It consists of a
     // register and an offset.
     struct SpillLoc {
       unsigned SpillBase;
struct VarLoc {
     /// extracting it from MI.
     union {
       uint64_t RegNo;
       SpillLoc SpillLocation;
       uint64_t Hash;
     } Loc;
 
     VarLoc(const MachineInstr &MI, LexicalScopes &LS)
-        : Var(MI.getDebugVariable(), MI.getDebugLoc()->getInlinedAt()), MI(MI),
-          UVS(MI.getDebugLoc(), LS) {
+        : Var(MI), MI(MI), UVS(MI.getDebugLoc(), LS) {
       static_assert((sizeof(Loc) == sizeof(uint64_t)),
                     "hash does not cover all members of Loc");
       assert(MI.isDebugValue() && "not a DBG_VALUE");
       assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE");
       if (int RegNo = isDbgValueDescribedByReg(MI)) {
         Kind = RegisterKind;
         Loc.RegNo = RegNo;
       }
     }
 
     /// The constructor for spill locations.
     VarLoc(const MachineInstr &MI, unsigned SpillBase, int SpillOffset,
            LexicalScopes &LS)
-        : Var(MI.getDebugVariable(), MI.getDebugLoc()->getInlinedAt()), MI(MI),
-          UVS(MI.getDebugLoc(), LS) {
+        : Var(MI), MI(MI), UVS(MI.getDebugLoc(), LS) {
       assert(MI.isDebugValue() && "not a DBG_VALUE");
       assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE");
       Kind = SpillLocKind;
       Loc.SpillLocation = {SpillBase, SpillOffset};
     }
 
     /// If this variable is described by a register, return it,
     /// otherwise return 0.
#endif
   class OpenRangesSet {
     VarLocSet VarLocs;
     SmallDenseMap<DebugVariableBase, unsigned, 8> Vars;
 
   public:
     const VarLocSet &getVarLocs() const { return VarLocs; }
 
     /// Terminate all open ranges for Var by removing it from the set.
-    void erase(DebugVariable Var) {
-      auto It = Vars.find(Var);
-      if (It != Vars.end()) {
-        unsigned ID = It->second;
-        VarLocs.reset(ID);
-        Vars.erase(It);
-      }
-    }
+    void erase(DebugVariable Var);
 
     /// Terminate all open ranges listed in \c KillSet by removing
     /// them from the set.
     void erase(const VarLocSet &KillSet, const VarLocMap &VarLocIDs) {
       VarLocs.intersectWithComplement(KillSet);
       for (unsigned ID : KillSet)
         Vars.erase(VarLocIDs[ID].Var);
     }
void printVarLocInMBB(const MachineFunction &MF, const VarLocInMBB &V,
                         raw_ostream &Out) const;
 
   /// Calculate the liveness information for the given machine function.
   bool runOnMachineFunction(MachineFunction &MF) override;
 };
 
 } // end anonymous namespace
 
+namespace llvm {
+
+template <> struct DenseMapInfo<LiveDebugValues::DebugVariableBase> {
+  using DVB = LiveDebugValues::DebugVariableBase;
+  using OptFragInfo = LiveDebugValues::OptFragInfo;
+  using FragInfo = LiveDebugValues::FragInfo;
+
+  static inline DVB getEmptyKey() {
+    return DVB(nullptr, OptFragInfo(), nullptr);
+  }
+
+  // Difference in tombstone is that the Optional is meaningful
+  static inline DVB getTombstoneKey() {
+    return DVB(nullptr, OptFragInfo({0, 0}), nullptr);
+  }
+
+  template <unsigned T, class B> static unsigned get_hash(const B &D) {
+    return hash_value(std::get<T>(D));
+  }
+
+  static unsigned getHashValue(const DVB &D) {
+    unsigned HV = 0;
+    const OptFragInfo &Frag = std::get<1>(D);
+    if (Frag)
+      HV = DenseMapInfo<FragInfo>::getHashValue(*Frag);
+
+    return hash_combine(get_hash<0>(D), HV, get_hash<2>(D));
+  }
+
+  static bool isEqual(const DVB &A, const DVB &B) { return A == B; }
+};
+
+}; // namespace llvm
+
 //===----------------------------------------------------------------------===//
 //            Implementation
 //===----------------------------------------------------------------------===//
 
 char LiveDebugValues::ID = 0;
 
 char &llvm::LiveDebugValuesID = LiveDebugValues::ID;
 
 INITIALIZE_PASS(LiveDebugValues, DEBUG_TYPE, "Live DEBUG_VALUE analysis",
                 false, false)
 
 /// Default construct and initialize the pass.
 LiveDebugValues::LiveDebugValues() : MachineFunctionPass(ID) {
   initializeLiveDebugValuesPass(*PassRegistry::getPassRegistry());
 }
 
 /// Tell the pass manager which passes we depend on and what information we
 /// preserve.
 void LiveDebugValues::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesCFG();
   MachineFunctionPass::getAnalysisUsage(AU);
 }
 
+void LiveDebugValues::OpenRangesSet::erase(DebugVariable Var) {
+  auto It = Vars.find(Var);
+  if (It != Vars.end()) {
+    unsigned ID = It->second;
+    VarLocs.reset(ID);
+    Vars.erase(It);
+  }
+}
+
 //===----------------------------------------------------------------------===//
 //            Debug Range Extension Implementation
 //===----------------------------------------------------------------------===//
 
 #ifndef NDEBUG
 void LiveDebugValues::printVarLocInMBB(const MachineFunction &MF,
                                        const VarLocInMBB &V,
                                        const VarLocMap &VarLocIDs,

 /// End all previous ranges related to @MI and start a new range from @MI
 /// if it is a DBG_VALUE instr.
 void LiveDebugValues::transferDebugValue(const MachineInstr &MI,
                                          OpenRangesSet &OpenRanges,
                                          VarLocMap &VarLocIDs) {
   if (!MI.isDebugValue())
     return;
   const DILocalVariable *Var = MI.getDebugVariable();
+  const DIExpression *Expr = MI.getDebugExpression();
   const DILocation *DebugLoc = MI.getDebugLoc();
   const DILocation *InlinedAt = DebugLoc->getInlinedAt();
   assert(Var->isValidLocationForIntrinsic(DebugLoc) &&
          "Expected inlined-at fields to agree");
 
   // End all previous ranges of Var.
-  DebugVariable V(Var, InlinedAt);
+  DebugVariable V(Var, Expr, InlinedAt);
   OpenRanges.erase(V);
 
   // Add the VarLoc to OpenRanges from this DBG_VALUE.
   // TODO: Currently handles DBG_VALUE which has only reg as location.
   if (isDbgValueDescribedByReg(MI)) {
     VarLoc VL(MI, LS);
     unsigned ID = VarLocIDs.insert(VL);
     OpenRanges.insert(ID, VL.Var);

test/DebugInfo/ARM/partial-subreg.ll

 ; RUN: llc %s -filetype=obj -o - | llvm-dwarfdump -v - | FileCheck %s
 ; This tests a fragment that partially covers subregister compositions.
 ;
 ; Our fragment is 96 bits long and lies in a 128-bit register, which
 ; in turn has to be composed out of its two 64-bit subregisters.
 
 ; CHECK: .debug_info
 ; CHECK: DW_TAG_subprogram
 ; CHECK:   DW_AT_name {{.*}}"subscript.get"
 ; CHECK:  DW_TAG_formal_parameter
 ; CHECK-NEXT: DW_AT_location [DW_FORM_sec_offset] ({{.*}}
 ; CHECK-NEXT:  [0x{{.*}}, 0x{{.*}}): DW_OP_regx D16, DW_OP_piece 0x8, DW_OP_regx D17, DW_OP_piece 0x4
-; CHECK-NEXT:  [0x{{.*}}, 0x{{.*}}): DW_OP_regx D16, DW_OP_piece 0x8, DW_OP_regx D17, DW_OP_piece 0x4
-
-; FIXME: The second location list entry should not be emitted.
-;
-; The input to LiveDebugValues is:
-;
-; bb.0.entry:
-;   [...]
-;   Bcc %bb.2, 1, killed $cpsr, debug-location !10; simd.swift:5900:12
-; bb.1:
-;   [...]
-;   DBG_VALUE $q8, $noreg, !"self", !DIExpression(DW_OP_LLVM_fragment, 0, 96)
-;   B %bb.3
-; bb.2.select.false:
-;   [...]
-;   DBG_VALUE $q8, $noreg, !"self", !DIExpression(DW_OP_LLVM_fragment, 0, 96)
-; bb.3.select.end:
-;   [...]
-;
-; The two DBG_VALUEs in the blocks describe different fragments of the
-; variable. However, LiveDebugValues is not aware of fragments, so it will
-; incorrectly insert a copy of the first DBG_VALUE in bb.3.select.end, since
-; the debug values in its predecessor blocks are described by the same
-; register.
 
 source_filename = "simd.ll"
 target datalayout = "e-m:o-p:32:32-f64:32:64-v64:32:64-v128:32:128-a:0:32-n32-S32"
 target triple = "armv7-apple-ios7.0"
 
 ; Function Attrs: nounwind readnone
 declare void @llvm.dbg.value(metadata, metadata, metadata) #0
 

test/DebugInfo/MIR/X86/live-debug-values-fragments.mir

+# RUN: llc %s -o - -run-pass=livedebugvalues | FileCheck %s
+#
+# This tests that, for two independent variable fragments defined in blocks
+# 1 and 2, _both_ their locations are propagated into the exit block.
+# LiveDebugValues previously ignored fragments and only propagated the last
+# variable location seen.
+#
+# CHECK-LABEL: bb.3.bb3:
+# CHECK:      DBG_VALUE $ebx, $noreg, !{{[0-9]}}, !DIExpression(DW_OP_LLVM_fragment, 32, 32)
+# CHECK-NEXT: DBG_VALUE $eax, $noreg, !{{[0-9]}}, !DIExpression(DW_OP_LLVM_fragment, 0, 32)
+# CHECK-NEXT: XOR32rr
+# CHECK-NEXT: RETQ
+--- |
+  target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+  
+  define i32 @foo(i32* %bees, i32* %output) !dbg !4 {
+  entry:
+    br label %bb1
+  bb1:
+    br label %bb2
+  bb2:
+    br label %bb3
+  bb3:
+    ret i32 0
+  }
+
+  !llvm.module.flags = !{!0, !100}
+  !llvm.dbg.cu = !{!1}
+  
+  !100 = !{i32 2, !"Dwarf Version", i32 4}
+  !0 = !{i32 2, !"Debug Info Version", i32 3}
+  !1 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !2, producer: "beards", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug)
+  !2 = !DIFile(filename: "bees.cpp", directory: ".")
+  !3 = !DILocalVariable(name: "flannel", scope: !4, file: !2, line: 1, type: !16)
+  !4 = distinct !DISubprogram(name: "nope", scope: !2, file: !2, line: 1, spFlags: DISPFlagDefinition, unit: !1, retainedNodes: !13, type: !14, isDefinition: true)
+  !8 = !DILocation(line: 4, scope: !4)
+  !13 = !{!3}
+  !14 = !DISubroutineType(types: !15)
+  !15 = !{!16}
+  !16 = !DIBasicType(name: "looong", size: 64, align: 64, encoding: DW_ATE_signed)
+
+...
+---
+name:            foo
+tracksRegLiveness: true
+registers:       []
+liveins:         
+  - { reg: '$rdi', virtual-reg: '' }
+body:             |
+  bb.0.entry:
+    successors: %bb.1
+    liveins: $rdi
+  
+    $ecx = XOR32rr undef $ecx, undef $ecx, implicit-def $eflags
+    JMP_1 %bb.1
+  
+  bb.1.bb1 (align 4):
+    successors: %bb.2
+    liveins: $ecx, $rdi
+  
+    $eax = MOV32rr killed $ecx, implicit-def $rax
+    DBG_VALUE $eax, $noreg, !3, !DIExpression(DW_OP_LLVM_fragment, 0, 32), debug-location !8
+    JMP_1 %bb.2
+  
+  bb.2.bb2:
+    successors: %bb.3
+    liveins: $eax
+  
+    $ebx = MOV32rr $eax
+    $ebx = ADD32ri8 $ebx, 3, implicit-def dead $eflags, implicit killed $rbx, implicit-def $rbx
+    DBG_VALUE $ebx, $noreg, !3, !DIExpression(DW_OP_LLVM_fragment, 32, 32), debug-location !8
+    JMP_1 %bb.3
+
+  bb.3.bb3:
+    liveins: $eax, $ebx
+    $eax = XOR32rr killed $eax, killed $ebx, implicit-def $eflags
+    RETQ $eax, debug-location !8
+
+...