llvm dev - Jun 2015 - [LLVMdev] Improving the quality of debug locations / DbgValueHistoryCalculator

Here is a proposal for improving DbgValueHistoryCalculator and the
overall quality of debug locations.

Focus: This is about lowering the DBG_VALUE machine instructions to
DWARF location lists.

Non-focus: This is not about (typical -O0) variables that permanently
reside at a frame index and are described with dbg.declare intrinsics
in the IR. These variables are stored in the MMI side-table and
processed separately.


The semantics of DBG_VALUE
=========================
Examples:

	DBG_VALUE %EAX, %noreg, !"a", <<0x7fd4bbc17470>>; line
no:3
        DBG_VALUE %RBX, 56, !"a", <<0x7ffd5ac3b3c0>>; line
no:4 indirect
        DBG_VALUE 0, 0, !"a", <<0x7fd4bbc17470>>; line
no:3

The DBG_VALUE machine instruction informs us that a variable (or a
piece of it) is henceforth stored in a specific location or has a
constant value. This is valid until the next DBG_VALUE instruction
describing the same variable or the location is being clobbered.

Lowering today
=============
1. DbgValueHistoryCalculator takes the MachineFunction graph and
   produces a list of live ranges for each variable (the
   DbgValueHistoryMap).

   Note: Variable live ranges are to be consumed by a debugger. They
   refer to the physical addresses and are agnostic of control flow.

   The live ranges produced by DbgValueHistoryCalculator are pairs of
   MachineInstructions, the first of which is always the DBG_VALUE
   describing the variable and location.

   The ranges are calculated as follows:
   - If the location is a register the range extends until the
     register is clobbered or until the end of the basic block.

   - If the location is a constant the range extends until the next
     DBG_VALUE instruction describing the same variable.

   - If the location is indirect and the register is not clobbered
     outside the function prologue and epilogue the the range is the
     entire function. This is a heuristic to make stack
     frame-allocated variables work better. Otherwise the range
     extends until the next DBG_VALUE or the end of the basic block.
   
2. The buildLocationList() function takes the list of ranges of one
   variable and builds a location list. A variable may consist of many
   pieces which have their own live ranges. A live ranges for a piece
   is split up so that no piece's live range starts or ends in the
   middle of another piece's live range.  Any two consecutive ranges
   with identical location contents are merged.  Labels are requested
   for start and end of each range.
   
3. The location list is finalized by lowering it into DWARF and
   emitted into a buffer.

Shortcomings with the current apporach
=====================================   
Problems with the current approach include inaccurate live ranges for
constant values, ranges ending too early (usually at basic block
boundaries), poor handling of frame-register-indirect variables that
were introduced by spill code, poor handling of variables that are in
more than one location at once.



A better DbgValueHistoryCalculator
=================================
Currently DbgValueHistoryCalculator does a very simple, linear pass
through all MachineInstructions, with a couple of heuristics to make
common cases such as the frame index variables work.

It would be possible to address many of the current problems by having
earlier passes emit many more DBG_VALUE instructions. There are
several problem with this approach though: It distributes the
complexity across many more passes and thus imposes a maintenance
burden on authors of prior passes, increases machine code size, and
stores a lot of redundant information.

What I'm proposing instead is to make DbgValueHistoryCalculator
smarter at creating ranges. The goal is to make hack^H^H^Heuristics such as
the frame index handling unnecessary by correctly propagating DBG_VALUE
liveness across basic block boundaries.

To illustrate what I mean I'll use a notation where
DbgValueHistoryCalculator is defined in terms of a data-flow analysis.

First a couple of data types used in the following pseudo code:
- A range is a pair of MachineInstructions (start, end) that both belong
  to the same basic block.
- range[var] is the final list of live ranges for a variable.
- open_ranges[BB][var] is the list of not-yet-terminated ranges for
  var inside the current basic block BB.
- outgoing_loc[BB][var] is the list of locations for var valid at
  the end of a basic block BB.

// This code is probably buggy because I didn't run it through a
// compiler yet, but I hope it serves to illustrate my point.
  
// Visit a machine instruction.
transfer(MInsn) {
  // A DBG_VALUE marks the beginning of a new range.
  if (MInsn is a DBG_VALUE(var, loc)) {

    for ((rvar, start) : open_ranges[BB])
      // A DBG_VALUE terminates a range started by a previous
      // DBG_VALUE for the same variable, if the described pieces
      // overlap.
      if (var == rvar && piece_overlaps(MInsn, start)) {
        ranges[var].push_back((start, MInsn));
        open_ranges[BB][rvar].remove(start));
      }
    open_ranges[BB][var].push_back(MInsn)
  }

  // A def of a register may mark the end of a range.
  if (MInsn is a def(reg)) {
    for ((var, start) : open_ranges[BB])
      if (start.loc == reg) {
        ranges[var].push_back((start, MInsn));
        open_ranges[BB][var].remove(start));
      }

  // End all ranges in the current basic block.
  if (MInsn.isTerminator())
    for (range : open_ranges[BB]) {
      ranges[var].push_back(range);
      open_ranges[BB].remove(range);
      outgoing_loc[BB][range.var].push_back(range.loc);
      changed = true;
   }
}

// Visit the beginning of a basic block BB with two predecessors.
join(BB, BB1, BB2) {
  for ((var1, loc1) : outgoing_loc[BB1])
    for (loc2 : outgoing_loc[BB2][var1])
      // It's only safe to propagate a range if all predecessors end
      // with the same location.
      if (loc1.kind == loc2.kind &&
          loc1.val  == loc2.val)
        // Not sure how to best implement this.
        open_ranges[BB][var].push_back(new DBG_VALUE(loc1));
}

analyze(MF) {
  for (BB : MF)
    workset.push_back(BB);

  while (!workset.empty()) {
    changed = false;
    for (MI : workset.pop_front())
      transfer(MI)
    if (changed)
      workset.append(BB.successors())
   }
}

A couple of observations about the pseudo-code above: The analysis
terminates, because ranges is write-only, making this effectively a
bit-vector problem. It is also safe, because we are only propagating
ranges into the next basic block if all predecessors have the same
outgoing location for a variable piece.

One problem that is not addressed by the approach above is how to
become better at handling variables that are in more than one location
at once: As Keno noted on llvm-commits recently, the fundamental
problem is that DbgValueHistoryCalculator cannot safely distinguish
between a DBG_VALUE that provides an additional valid location and one
describing an updated location for a variable. IMO this is best
addressed on a case-by-case basis in the pass that introduces the second
DBG_VALUE, either by marking it as alternative location or not emitting
it at all, but I’m open for suggestions.

Comments?

-- adrian

Hi Adrian,
I've been down this road in past lives, hopefully I can contribute
meaningful review.  I'll certainly try.
> -----Original Message-----
> From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at
cs.uiuc.edu] On
> Behalf Of Adrian Prantl
> Sent: Tuesday, June 23, 2015 4:42 PM
> To: LLVM Developers Mailing List
> Cc: Keno Fischer; Alexey Samsonov
> Subject: [LLVMdev] Improving the quality of debug locations /
> DbgValueHistoryCalculator
> 
> Here is a proposal for improving DbgValueHistoryCalculator and the
> overall quality of debug locations.
> 
> Focus: This is about lowering the DBG_VALUE machine instructions to
> DWARF location lists.
> 
> Non-focus: This is not about (typical -O0) variables that permanently
> reside at a frame index and are described with dbg.declare intrinsics
> in the IR. These variables are stored in the MMI side-table and
> processed separately.
> 
> 
> The semantics of DBG_VALUE
> =========================> 
> Examples:
> 
> 	DBG_VALUE %EAX, %noreg, !"a", <<0x7fd4bbc17470>>;
line no:3
>         DBG_VALUE %RBX, 56, !"a", <<0x7ffd5ac3b3c0>>;
line no:4 indirect
>         DBG_VALUE 0, 0, !"a", <<0x7fd4bbc17470>>;
line no:3
> 
> The DBG_VALUE machine instruction informs us that a variable (or a
> piece of it) is henceforth stored in a specific location or has a
> constant value. This is valid until the next DBG_VALUE instruction
> describing the same variable or the location is being clobbered.
I could wish that these annotations weren't done as separate instructions
but that's a horse for another day.
> 
> Lowering today
> =============> 
> 1. DbgValueHistoryCalculator takes the MachineFunction graph and
>    produces a list of live ranges for each variable (the
>    DbgValueHistoryMap).
> 
>    Note: Variable live ranges are to be consumed by a debugger. They
>    refer to the physical addresses and are agnostic of control flow.
For those keeping score at home, this means you can't convert live
ranges to final DWARF until after block layout is done.  We can compute
ranges within a block before that point, and paste them together later
if we need to.
> 
>    The live ranges produced by DbgValueHistoryCalculator are pairs of
>    MachineInstructions, the first of which is always the DBG_VALUE
>    describing the variable and location.
> 
>    The ranges are calculated as follows:
>    - If the location is a register the range extends until the
>      register is clobbered or until the end of the basic block.
> 
>    - If the location is a constant the range extends until the next
>      DBG_VALUE instruction describing the same variable.
> 
>    - If the location is indirect and the register is not clobbered
>      outside the function prologue and epilogue the the range is the
>      entire function. This is a heuristic to make stack
>      frame-allocated variables work better. Otherwise the range
>      extends until the next DBG_VALUE or the end of the basic block.
> 
> 2. The buildLocationList() function takes the list of ranges of one
>    variable and builds a location list. A variable may consist of many
>    pieces which have their own live ranges. A live ranges for a piece
>    is split up so that no piece's live range starts or ends in the
>    middle of another piece's live range.  Any two consecutive ranges
>    with identical location contents are merged.  Labels are requested
>    for start and end of each range.
> 
> 3. The location list is finalized by lowering it into DWARF and
>    emitted into a buffer.
> 
> Shortcomings with the current apporach
> =====================================> 
> Problems with the current approach include inaccurate live ranges for
> constant values, ranges ending too early (usually at basic block
> boundaries), poor handling of frame-register-indirect variables that
> were introduced by spill code, poor handling of variables that are in
> more than one location at once.
Right, spill-restore is different from having a stack home.  That
was a bear... maybe if the first DBG_VALUE gives a stack location,
that's a homed variable, but if it starts in a register and moves
to the stack, that's just a spill?  There must be a better way to
annotate this.
> 
> 
> 
> A better DbgValueHistoryCalculator
> =================================> 
> Currently DbgValueHistoryCalculator does a very simple, linear pass
> through all MachineInstructions, with a couple of heuristics to make
> common cases such as the frame index variables work.
> 
> It would be possible to address many of the current problems by having
> earlier passes emit many more DBG_VALUE instructions. There are
> several problem with this approach though: It distributes the
> complexity across many more passes and thus imposes a maintenance
> burden on authors of prior passes, increases machine code size, and
> stores a lot of redundant information.
> 
> What I'm proposing instead is to make DbgValueHistoryCalculator
> smarter at creating ranges. The goal is to make hack^H^H^Heuristics such
> as
> the frame index handling unnecessary by correctly propagating DBG_VALUE
> liveness across basic block boundaries.
> 
> To illustrate what I mean I'll use a notation where
> DbgValueHistoryCalculator is defined in terms of a data-flow analysis.
Data-flow is the right way to do this.
> 
> First a couple of data types used in the following pseudo code:
> - A range is a pair of MachineInstructions (start, end) that both belong
>   to the same basic block.
> - range[var] is the final list of live ranges for a variable.
> - open_ranges[BB][var] is the list of not-yet-terminated ranges for
>   var inside the current basic block BB.
> - outgoing_loc[BB][var] is the list of locations for var valid at
>   the end of a basic block BB.
This would be exactly the open_ranges at the end of the BB?
> 
> // This code is probably buggy because I didn't run it through a
> // compiler yet, but I hope it serves to illustrate my point.
> 
> // Visit a machine instruction.
> transfer(MInsn) {
>   // A DBG_VALUE marks the beginning of a new range.
>   if (MInsn is a DBG_VALUE(var, loc)) {
> 
>     for ((rvar, start) : open_ranges[BB])
>       // A DBG_VALUE terminates a range started by a previous
>       // DBG_VALUE for the same variable, if the described pieces
>       // overlap.
>       if (var == rvar && piece_overlaps(MInsn, start)) {
>         ranges[var].push_back((start, MInsn));
>         open_ranges[BB][rvar].remove(start));
>       }
>     open_ranges[BB][var].push_back(MInsn)
>   }
> 
>   // A def of a register may mark the end of a range.
>   if (MInsn is a def(reg)) {
>     for ((var, start) : open_ranges[BB])
>       if (start.loc == reg) {
>         ranges[var].push_back((start, MInsn));
>         open_ranges[BB][var].remove(start));
>       }
How are implicit clobbers described/detected?  For example a 'call'
must be assumed to clobber all registers not defined as callee-saved
by the ABI. As written it looks like you're thinking that a given
instruction clobbers at most one reg, but that's not universally true.
> 
>   // End all ranges in the current basic block.
>   if (MInsn.isTerminator())
>     for (range : open_ranges[BB]) {
>       ranges[var].push_back(range);
>       open_ranges[BB].remove(range);
>       outgoing_loc[BB][range.var].push_back(range.loc);
>       changed = true;
And outgoing_loc = open_ranges at the end of the BB! Awesome.

I'm not convinced this is the right place to set 'changed' though.
You'd set it whenever a block had live-outs?  Wouldn't that tend
to be the same each time you processed the block?
>    }
> }
> 
> // Visit the beginning of a basic block BB with two predecessors.
> join(BB, BB1, BB2) {
>   for ((var1, loc1) : outgoing_loc[BB1])
>     for (loc2 : outgoing_loc[BB2][var1])
>       // It's only safe to propagate a range if all predecessors end
>       // with the same location.
>       if (loc1.kind == loc2.kind &&
>           loc1.val  == loc2.val)
>         // Not sure how to best implement this.
>         open_ranges[BB][var].push_back(new DBG_VALUE(loc1));
> }
Live-in at the top of BB is the intersection of live-outs of all
predecessors (maybe more than two!).  This is way simpler if you have
bitvectors where each bit represents a unique (var, loc) tuple.
> 
> analyze(MF) {
>   for (BB : MF)
>     workset.push_back(BB);
> 
>   while (!workset.empty()) {
>     changed = false;
>     for (MI : workset.pop_front())
>       transfer(MI)
>     if (changed)
>       workset.append(BB.successors())
>    }
> }
You're not showing the join() part here...  seems like you'd
want to do the join() part on a block first, before going
into the instruction loop, to get your initial live-in set.
That works best if your initial pass through the blocks is in
some reasonable control-flow-like order.

Nit, not clear whether "workset" is BBs or MIs.  Maybe it's
    for (BB : workset.pop_front())
      for (MI: BB)
        transfer(MI)
?
> 
> A couple of observations about the pseudo-code above: The analysis
> terminates, because ranges is write-only, making this effectively a
> bit-vector problem. It is also safe, because we are only propagating
> ranges into the next basic block if all predecessors have the same
> outgoing location for a variable piece.
Well, yes, but the second time you process a block you're going to
be duplicating entries in ranges (the ones that don't cross a block
boundary).  A more bona-fide dataflow seems like it would work better,
it's going to converge anyway, and then you compute ranges at the end.
> 
> One problem that is not addressed by the approach above is how to
> become better at handling variables that are in more than one location
> at once: As Keno noted on llvm-commits recently, the fundamental
> problem is that DbgValueHistoryCalculator cannot safely distinguish
> between a DBG_VALUE that provides an additional valid location and one
> describing an updated location for a variable. IMO this is best
> addressed on a case-by-case basis in the pass that introduces the second
> DBG_VALUE, either by marking it as alternative location or not emitting
> it at all, but I’m open for suggestions.
Naively a def is not a kill.  Beyond that sweeping statement, things get
fuzzy pretty quickly.

The most common situation is a stack-homed variable that temporarily moves
into a register but when the register gets clobbered you'd like to revert
to the stack location.  On the other hand, if it's in a register and the
user tells the debugger to modify the variable, is the debugger smart
enough to update both locations?  Most compilers don't know how to track
multiple locations for a variable so I have no intuition to offer here...
sorry.

Thanks for diving into this!
--paulr
> 
> Comments?
> 
> -- adrian
> 
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

Hi Adrian,

You might want to take a look at abandoned http://reviews.llvm.org/D2658,
where I tried to implement something similar.
Looks like we're now at the point where we *do* require complicated
solution and analysis in DbgValueHistoryCalculator...

On Tue, Jun 23, 2015 at 4:41 PM, Adrian Prantl <aprantl at apple.com>
wrote:
> Here is a proposal for improving DbgValueHistoryCalculator and the
> overall quality of debug locations.
>
> Focus: This is about lowering the DBG_VALUE machine instructions to
> DWARF location lists.
>
> Non-focus: This is not about (typical -O0) variables that permanently
> reside at a frame index and are described with dbg.declare intrinsics
> in the IR. These variables are stored in the MMI side-table and
> processed separately.
>
>
> The semantics of DBG_VALUE
> =========================>
> Examples:
>
>         DBG_VALUE %EAX, %noreg, !"a",
<<0x7fd4bbc17470>>; line no:3
>         DBG_VALUE %RBX, 56, !"a", <<0x7ffd5ac3b3c0>>;
line no:4 indirect
>         DBG_VALUE 0, 0, !"a", <<0x7fd4bbc17470>>;
line no:3
>
> The DBG_VALUE machine instruction informs us that a variable (or a
> piece of it) is henceforth stored in a specific location or has a
> constant value. This is valid until the next DBG_VALUE instruction
> describing the same variable or the location is being clobbered.
>
> Lowering today
> =============>
> 1. DbgValueHistoryCalculator takes the MachineFunction graph and
>    produces a list of live ranges for each variable (the
>    DbgValueHistoryMap).
>
>    Note: Variable live ranges are to be consumed by a debugger. They
>    refer to the physical addresses and are agnostic of control flow.
>
>    The live ranges produced by DbgValueHistoryCalculator are pairs of
>    MachineInstructions, the first of which is always the DBG_VALUE
>    describing the variable and location.
>
>    The ranges are calculated as follows:
>    - If the location is a register the range extends until the
>      register is clobbered or until the end of the basic block.
>
>    - If the location is a constant the range extends until the next
>      DBG_VALUE instruction describing the same variable.
>
>    - If the location is indirect and the register is not clobbered
>      outside the function prologue and epilogue the the range is the
>      entire function. This is a heuristic to make stack
>      frame-allocated variables work better. Otherwise the range
>      extends until the next DBG_VALUE or the end of the basic block.
>
> 2. The buildLocationList() function takes the list of ranges of one
>    variable and builds a location list. A variable may consist of many
>    pieces which have their own live ranges. A live ranges for a piece
>    is split up so that no piece's live range starts or ends in the
>    middle of another piece's live range.  Any two consecutive ranges
>    with identical location contents are merged.  Labels are requested
>    for start and end of each range.
>
> 3. The location list is finalized by lowering it into DWARF and
>    emitted into a buffer.
>
> Shortcomings with the current apporach
> =====================================>
> Problems with the current approach include inaccurate live ranges for
> constant values, ranges ending too early (usually at basic block
> boundaries), poor handling of frame-register-indirect variables that
> were introduced by spill code, poor handling of variables that are in
> more than one location at once.
>
>
>
> A better DbgValueHistoryCalculator
> =================================>
> Currently DbgValueHistoryCalculator does a very simple, linear pass
> through all MachineInstructions, with a couple of heuristics to make
> common cases such as the frame index variables work.
>
> It would be possible to address many of the current problems by having
> earlier passes emit many more DBG_VALUE instructions. There are
> several problem with this approach though: It distributes the
> complexity across many more passes and thus imposes a maintenance
> burden on authors of prior passes, increases machine code size, and
> stores a lot of redundant information.
>
> What I'm proposing instead is to make DbgValueHistoryCalculator
> smarter at creating ranges. The goal is to make hack^H^H^Heuristics such as
> the frame index handling unnecessary by correctly propagating DBG_VALUE
> liveness across basic block boundaries.
>
> To illustrate what I mean I'll use a notation where
> DbgValueHistoryCalculator is defined in terms of a data-flow analysis.
>
> First a couple of data types used in the following pseudo code:
> - A range is a pair of MachineInstructions (start, end) that both belong
>   to the same basic block.
> - range[var] is the final list of live ranges for a variable.
>
How come you never remove ranges from range[var]? What if you have smth.
like
BB1:
  DBG_VALUE %RAX, %noreg, !"a"
  jmp BB2
BB2:
  // more minsns
  clobber %RAX
BB3:
  clobber %RAX
  DBG_VALUE %RBX, %noreg, !"a"
  jmp BB2

Looks like you would handle BB1, then BB2, and create a range for "a"
from
the beginning of BB2 to clobber instruction.
But this might be incorrect - if we have jumped to BB2 from BB3, then the
location of "a" is anything but %RAX.

I think you should respect the control flow somehow, and consider locations
of "a" at the beginning of basic block BB only
if you are certain that locations of "a" at the end of all BB's
predecessors don't contradict.

- open_ranges[BB][var] is the list of not-yet-terminated ranges
for
>
  var inside the current basic block BB.
> - outgoing_loc[BB][var] is the list of locations for var valid at
>   the end of a basic block BB.
>
> // This code is probably buggy because I didn't run it through a
> // compiler yet, but I hope it serves to illustrate my point.
>
> // Visit a machine instruction.
>
I'm kind of concerned about the runtime cost of this. Looks like this can
be at least
O(number_of_minsn * number_of_local_variables), which is already
significant. And it seems
that you can iterate over the same basic block several times.


> transfer(MInsn) {
>   // A DBG_VALUE marks the beginning of a new range.
>   if (MInsn is a DBG_VALUE(var, loc)) {
>
>     for ((rvar, start) : open_ranges[BB])
>       // A DBG_VALUE terminates a range started by a previous
>       // DBG_VALUE for the same variable, if the described pieces
>       // overlap.
>       if (var == rvar && piece_overlaps(MInsn, start)) {
>         ranges[var].push_back((start, MInsn));
>         open_ranges[BB][rvar].remove(start));
>       }
>     open_ranges[BB][var].push_back(MInsn)
>   }
>
>   // A def of a register may mark the end of a range.
>   if (MInsn is a def(reg)) {
>     for ((var, start) : open_ranges[BB])
>       if (start.loc == reg) {
>         ranges[var].push_back((start, MInsn));
>         open_ranges[BB][var].remove(start));
>       }
>
>   // End all ranges in the current basic block.
>   if (MInsn.isTerminator())
>     for (range : open_ranges[BB]) {
>       ranges[var].push_back(range);
>       open_ranges[BB].remove(range);
>       outgoing_loc[BB][range.var].push_back(range.loc);
>       changed = true;
>    }
> }
>
> // Visit the beginning of a basic block BB with two predecessors.
> join(BB, BB1, BB2) {
>   for ((var1, loc1) : outgoing_loc[BB1])
>     for (loc2 : outgoing_loc[BB2][var1])
>       // It's only safe to propagate a range if all predecessors end
>       // with the same location.
>       if (loc1.kind == loc2.kind &&
>           loc1.val  == loc2.val)
>         // Not sure how to best implement this.
>         open_ranges[BB][var].push_back(new DBG_VALUE(loc1));
>
Yep, that's kind of problem, we can't modify MachineFunction at this
point.

> }
>
> analyze(MF) {
>   for (BB : MF)
>     workset.push_back(BB);
>
>   while (!workset.empty()) {
>     changed = false;
>     for (MI : workset.pop_front())
>       transfer(MI)
>     if (changed)
>       workset.append(BB.successors())
>    }
> }
>
> A couple of observations about the pseudo-code above: The analysis
> terminates, because ranges is write-only, making this effectively a
> bit-vector problem. It is also safe, because we are only propagating
> ranges into the next basic block if all predecessors have the same
> outgoing location for a variable piece.
>
> One problem that is not addressed by the approach above is how to
> become better at handling variables that are in more than one location
> at once: As Keno noted on llvm-commits recently, the fundamental
> problem is that DbgValueHistoryCalculator cannot safely distinguish
> between a DBG_VALUE that provides an additional valid location and one
> describing an updated location for a variable. IMO this is best
> addressed on a case-by-case basis in the pass that introduces the second
> DBG_VALUE, either by marking it as alternative location or not emitting
> it at all, but I’m open for suggestions.
>
> Comments?
>
> -- adrian
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>


-- 
Alexey Samsonov
vonosmas at gmail.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150624/b1ba4400/attachment.html>

Hi All,

I will also be working on improving DbgValueHistoryCalculator and
the overall quality of debug locations as part of my project in Julia for
improving debug information. I currently don't have an absolute plan for
improvement as I am still working on the basics of DbgValueHistoryCalculator.
I will update you again after getting a proper understanding of
DbgValueHistoryCalculator about the things I can contribute to it.

I agree with the improvements required as mentioned by Adrian but
am fairly new to the debug information in LLVM to give any useful comments.

Thanks,
Ambuj

On Wed, Jun 24, 2015 at 8:12 PM, Alexey Samsonov <vonosmas at gmail.com>
wrote:
> Hi Adrian,
>
> You might want to take a look at abandoned http://reviews.llvm.org/D2658
>
<https://urldefense.proofpoint.com/v2/url?u=http-3A__reviews.llvm.org_D2658&d=AwMFaQ&c=8hUWFZcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMHA&m=IqQBBCcBRPH-kKonQYRP02sTtNcvjEY0gVezAM-zYxM&s=5KCjLrFnE3ZfuFwjyCGDBNxojW2I8Hz9Xus_8AFY1CI&e=>,
> where I tried to implement something similar.
> Looks like we're now at the point where we *do* require complicated
> solution and analysis in DbgValueHistoryCalculator...
>
> On Tue, Jun 23, 2015 at 4:41 PM, Adrian Prantl <aprantl at apple.com>
wrote:
>
>> Here is a proposal for improving DbgValueHistoryCalculator and the
>> overall quality of debug locations.
>>
>> Focus: This is about lowering the DBG_VALUE machine instructions to
>> DWARF location lists.
>>
>> Non-focus: This is not about (typical -O0) variables that permanently
>> reside at a frame index and are described with dbg.declare intrinsics
>> in the IR. These variables are stored in the MMI side-table and
>> processed separately.
>>
>>
>> The semantics of DBG_VALUE
>> =========================>>
>> Examples:
>>
>>         DBG_VALUE %EAX, %noreg, !"a",
<<0x7fd4bbc17470>>; line no:3
>>         DBG_VALUE %RBX, 56, !"a",
<<0x7ffd5ac3b3c0>>; line no:4 indirect
>>         DBG_VALUE 0, 0, !"a", <<0x7fd4bbc17470>>;
line no:3
>>
>> The DBG_VALUE machine instruction informs us that a variable (or a
>> piece of it) is henceforth stored in a specific location or has a
>> constant value. This is valid until the next DBG_VALUE instruction
>> describing the same variable or the location is being clobbered.
>>
>> Lowering today
>> =============>>
>> 1. DbgValueHistoryCalculator takes the MachineFunction graph and
>>    produces a list of live ranges for each variable (the
>>    DbgValueHistoryMap).
>>
>>    Note: Variable live ranges are to be consumed by a debugger. They
>>    refer to the physical addresses and are agnostic of control flow.
>>
>>    The live ranges produced by DbgValueHistoryCalculator are pairs of
>>    MachineInstructions, the first of which is always the DBG_VALUE
>>    describing the variable and location.
>>
>>    The ranges are calculated as follows:
>>    - If the location is a register the range extends until the
>>      register is clobbered or until the end of the basic block.
>>
>>    - If the location is a constant the range extends until the next
>>      DBG_VALUE instruction describing the same variable.
>>
>>    - If the location is indirect and the register is not clobbered
>>      outside the function prologue and epilogue the the range is the
>>      entire function. This is a heuristic to make stack
>>      frame-allocated variables work better. Otherwise the range
>>      extends until the next DBG_VALUE or the end of the basic block.
>>
>> 2. The buildLocationList() function takes the list of ranges of one
>>    variable and builds a location list. A variable may consist of many
>>    pieces which have their own live ranges. A live ranges for a piece
>>    is split up so that no piece's live range starts or ends in the
>>    middle of another piece's live range.  Any two consecutive
ranges
>>    with identical location contents are merged.  Labels are requested
>>    for start and end of each range.
>>
>> 3. The location list is finalized by lowering it into DWARF and
>>    emitted into a buffer.
>>
>> Shortcomings with the current apporach
>> =====================================>>
>> Problems with the current approach include inaccurate live ranges for
>> constant values, ranges ending too early (usually at basic block
>> boundaries), poor handling of frame-register-indirect variables that
>> were introduced by spill code, poor handling of variables that are in
>> more than one location at once.
>>
>>
>>
>> A better DbgValueHistoryCalculator
>> =================================>>
>> Currently DbgValueHistoryCalculator does a very simple, linear pass
>> through all MachineInstructions, with a couple of heuristics to make
>> common cases such as the frame index variables work.
>>
>> It would be possible to address many of the current problems by having
>> earlier passes emit many more DBG_VALUE instructions. There are
>> several problem with this approach though: It distributes the
>> complexity across many more passes and thus imposes a maintenance
>> burden on authors of prior passes, increases machine code size, and
>> stores a lot of redundant information.
>>
>> What I'm proposing instead is to make DbgValueHistoryCalculator
>> smarter at creating ranges. The goal is to make hack^H^H^Heuristics
such
>> as
>> the frame index handling unnecessary by correctly propagating DBG_VALUE
>> liveness across basic block boundaries.
>>
>> To illustrate what I mean I'll use a notation where
>> DbgValueHistoryCalculator is defined in terms of a data-flow analysis.
>>
>> First a couple of data types used in the following pseudo code:
>> - A range is a pair of MachineInstructions (start, end) that both
belong
>>   to the same basic block.
>> - range[var] is the final list of live ranges for a variable.
>>
>
> How come you never remove ranges from range[var]? What if you have smth.
> like
> BB1:
>   DBG_VALUE %RAX, %noreg, !"a"
>   jmp BB2
> BB2:
>   // more minsns
>   clobber %RAX
> BB3:
>   clobber %RAX
>   DBG_VALUE %RBX, %noreg, !"a"
>   jmp BB2
>
> Looks like you would handle BB1, then BB2, and create a range for
"a" from
> the beginning of BB2 to clobber instruction.
> But this might be incorrect - if we have jumped to BB2 from BB3, then the
> location of "a" is anything but %RAX.
>
> I think you should respect the control flow somehow, and consider
> locations of "a" at the beginning of basic block BB only
> if you are certain that locations of "a" at the end of all
BB's
> predecessors don't contradict.
>
> - open_ranges[BB][var] is the list of not-yet-terminated ranges for
>>
>   var inside the current basic block BB.
>> - outgoing_loc[BB][var] is the list of locations for var valid at
>>   the end of a basic block BB.
>>
>> // This code is probably buggy because I didn't run it through a
>> // compiler yet, but I hope it serves to illustrate my point.
>>
>> // Visit a machine instruction.
>>
>
> I'm kind of concerned about the runtime cost of this. Looks like this
can
> be at least
> O(number_of_minsn * number_of_local_variables), which is already
> significant. And it seems
> that you can iterate over the same basic block several times.
>
>
>
>> transfer(MInsn) {
>>   // A DBG_VALUE marks the beginning of a new range.
>>   if (MInsn is a DBG_VALUE(var, loc)) {
>>
>>     for ((rvar, start) : open_ranges[BB])
>>       // A DBG_VALUE terminates a range started by a previous
>>       // DBG_VALUE for the same variable, if the described pieces
>>       // overlap.
>>       if (var == rvar && piece_overlaps(MInsn, start)) {
>>         ranges[var].push_back((start, MInsn));
>>         open_ranges[BB][rvar].remove(start));
>>       }
>>     open_ranges[BB][var].push_back(MInsn)
>>   }
>>
>>   // A def of a register may mark the end of a range.
>>   if (MInsn is a def(reg)) {
>>     for ((var, start) : open_ranges[BB])
>>       if (start.loc == reg) {
>>         ranges[var].push_back((start, MInsn));
>>         open_ranges[BB][var].remove(start));
>>       }
>>
>>   // End all ranges in the current basic block.
>>   if (MInsn.isTerminator())
>>     for (range : open_ranges[BB]) {
>>       ranges[var].push_back(range);
>>       open_ranges[BB].remove(range);
>>       outgoing_loc[BB][range.var].push_back(range.loc);
>>       changed = true;
>>    }
>> }
>>
>> // Visit the beginning of a basic block BB with two predecessors.
>> join(BB, BB1, BB2) {
>>   for ((var1, loc1) : outgoing_loc[BB1])
>>     for (loc2 : outgoing_loc[BB2][var1])
>>       // It's only safe to propagate a range if all predecessors
end
>>       // with the same location.
>>       if (loc1.kind == loc2.kind &&
>>           loc1.val  == loc2.val)
>>         // Not sure how to best implement this.
>>         open_ranges[BB][var].push_back(new DBG_VALUE(loc1));
>>
>
> Yep, that's kind of problem, we can't modify MachineFunction at
this point.
>
>
>> }
>>
>> analyze(MF) {
>>   for (BB : MF)
>>     workset.push_back(BB);
>>
>>   while (!workset.empty()) {
>>     changed = false;
>>     for (MI : workset.pop_front())
>>       transfer(MI)
>>     if (changed)
>>       workset.append(BB.successors())
>>    }
>> }
>>
>> A couple of observations about the pseudo-code above: The analysis
>> terminates, because ranges is write-only, making this effectively a
>> bit-vector problem. It is also safe, because we are only propagating
>> ranges into the next basic block if all predecessors have the same
>> outgoing location for a variable piece.
>>
>> One problem that is not addressed by the approach above is how to
>> become better at handling variables that are in more than one location
>> at once: As Keno noted on llvm-commits recently, the fundamental
>> problem is that DbgValueHistoryCalculator cannot safely distinguish
>> between a DBG_VALUE that provides an additional valid location and one
>> describing an updated location for a variable. IMO this is best
>> addressed on a case-by-case basis in the pass that introduces the
second
>> DBG_VALUE, either by marking it as alternative location or not emitting
>> it at all, but I’m open for suggestions.
>>
>> Comments?
>>
>> -- adrian
>>
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>
>
>
>
> --
> Alexey Samsonov
> vonosmas at gmail.com
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150628/4df90a6c/attachment.html>

> On Jun 24, 2015, at 12:12 PM, Alexey Samsonov <vonosmas at gmail.com>
wrote:
> 
> Hi Adrian,
> 
> You might want to take a look at abandoned http://reviews.llvm.org/D2658
<http://reviews.llvm.org/D2658>, where I tried to implement something
similar.
> Looks like we're now at the point where we *do* require complicated
solution and analysis in DbgValueHistoryCalculator...
> 
> On Tue, Jun 23, 2015 at 4:41 PM, Adrian Prantl <aprantl at apple.com
<mailto:aprantl at apple.com>> wrote:
> Here is a proposal for improving DbgValueHistoryCalculator and the
> overall quality of debug locations.
> 
> Focus: This is about lowering the DBG_VALUE machine instructions to
> DWARF location lists.
> 
> Non-focus: This is not about (typical -O0) variables that permanently
> reside at a frame index and are described with dbg.declare intrinsics
> in the IR. These variables are stored in the MMI side-table and
> processed separately.
> 
> 
> The semantics of DBG_VALUE
> =========================> 
> Examples:
> 
>         DBG_VALUE %EAX, %noreg, !"a",
<<0x7fd4bbc17470>>; line no:3
>         DBG_VALUE %RBX, 56, !"a", <<0x7ffd5ac3b3c0>>;
line no:4 indirect
>         DBG_VALUE 0, 0, !"a", <<0x7fd4bbc17470>>;
line no:3
> 
> The DBG_VALUE machine instruction informs us that a variable (or a
> piece of it) is henceforth stored in a specific location or has a
> constant value. This is valid until the next DBG_VALUE instruction
> describing the same variable or the location is being clobbered.
> 
> Lowering today
> =============> 
> 1. DbgValueHistoryCalculator takes the MachineFunction graph and
>    produces a list of live ranges for each variable (the
>    DbgValueHistoryMap).
> 
>    Note: Variable live ranges are to be consumed by a debugger. They
>    refer to the physical addresses and are agnostic of control flow.
> 
>    The live ranges produced by DbgValueHistoryCalculator are pairs of
>    MachineInstructions, the first of which is always the DBG_VALUE
>    describing the variable and location.
> 
>    The ranges are calculated as follows:
>    - If the location is a register the range extends until the
>      register is clobbered or until the end of the basic block.
> 
>    - If the location is a constant the range extends until the next
>      DBG_VALUE instruction describing the same variable.
> 
>    - If the location is indirect and the register is not clobbered
>      outside the function prologue and epilogue the the range is the
>      entire function. This is a heuristic to make stack
>      frame-allocated variables work better. Otherwise the range
>      extends until the next DBG_VALUE or the end of the basic block.
> 
> 2. The buildLocationList() function takes the list of ranges of one
>    variable and builds a location list. A variable may consist of many
>    pieces which have their own live ranges. A live ranges for a piece
>    is split up so that no piece's live range starts or ends in the
>    middle of another piece's live range.  Any two consecutive ranges
>    with identical location contents are merged.  Labels are requested
>    for start and end of each range.
> 
> 3. The location list is finalized by lowering it into DWARF and
>    emitted into a buffer.
> 
> Shortcomings with the current apporach
> =====================================> 
> Problems with the current approach include inaccurate live ranges for
> constant values, ranges ending too early (usually at basic block
> boundaries), poor handling of frame-register-indirect variables that
> were introduced by spill code, poor handling of variables that are in
> more than one location at once.
> 
> 
> 
> A better DbgValueHistoryCalculator
> =================================> 
> Currently DbgValueHistoryCalculator does a very simple, linear pass
> through all MachineInstructions, with a couple of heuristics to make
> common cases such as the frame index variables work.
> 
> It would be possible to address many of the current problems by having
> earlier passes emit many more DBG_VALUE instructions. There are
> several problem with this approach though: It distributes the
> complexity across many more passes and thus imposes a maintenance
> burden on authors of prior passes, increases machine code size, and
> stores a lot of redundant information.
> 
> What I'm proposing instead is to make DbgValueHistoryCalculator
> smarter at creating ranges. The goal is to make hack^H^H^Heuristics such as
> the frame index handling unnecessary by correctly propagating DBG_VALUE
> liveness across basic block boundaries.
> 
> To illustrate what I mean I'll use a notation where
> DbgValueHistoryCalculator is defined in terms of a data-flow analysis.
> 
> First a couple of data types used in the following pseudo code:
> - A range is a pair of MachineInstructions (start, end) that both belong
>   to the same basic block.
> - range[var] is the final list of live ranges for a variable.
> 
> How come you never remove ranges from range[var]? What if you have smth.
like
> BB1:
>   DBG_VALUE %RAX, %noreg, !"a"
>   jmp BB2
> BB2:
>   // more minsns
>   clobber %RAX
> BB3:
>   clobber %RAX
>   DBG_VALUE %RBX, %noreg, !"a"
>   jmp BB2
>  
> Looks like you would handle BB1, then BB2, and create a range for
"a" from the beginning of BB2 to clobber instruction.
> But this might be incorrect - if we have jumped to BB2 from BB3, then the
location of "a" is anything but %RAX.
To guarantee termination new ranges are only committed to ranges[var] when we
know they are valid on all paths.
BB1 is visited first and we record a range for a from the DBG_VALUE to the end
of BB1:
  ranges[a].push_back( (DBG_VALUE, BB2.first_insn) )
(There’s a bug in the pseudo-code doesn’t set the end of the range correctly,
but the comment conveys the intention.)
When BB2 is visited the data-flow analysis magic kicks in via the join()
function, which I (as Paul pointed out) left out from the pseudo-code. Sorry for
the extra confusion. Next time I write up such a proposal I should just
implement it so I can make sure that all the pieces are actually there and I
don’t just imagine them :-)
The first time BB2 is visited, we only have the information from BB1, so
join(BB2, /*pred1*/ BB1, /*pred2*/  BB3) returns an empty set. After BB3 is
visited join() will still come back with an empty set because the intersection
of the location for “a” coming from BB1 and BB3 is different.
> 
> I think you should respect the control flow somehow, and consider locations
of "a" at the beginning of basic block BB only
> if you are certain that locations of "a" at the end of all
BB's predecessors don't contradict.
It does take the control flow into account, but I left out the important part
from the pseudo-code and replaced it with a hand-wavy statement about it being a
data-flow analysis. Sorry about that!
> 
> - open_ranges[BB][var] is the list of not-yet-terminated ranges for
>   var inside the current basic block BB.
> - outgoing_loc[BB][var] is the list of locations for var valid at
>   the end of a basic block BB.
> 
> // This code is probably buggy because I didn't run it through a
> // compiler yet, but I hope it serves to illustrate my point.
> 
> // Visit a machine instruction.
> 
> I'm kind of concerned about the runtime cost of this. Looks like this
can be at least
> O(number_of_minsn * number_of_local_variables), which is already
significant. And it seems
> that you can iterate over the same basic block several times.
> 
Yes, we’ll have to benchmark it very carefully before deciding that the extra
complexity is worth it.

thanks for all the feedback
-- adrian
>  
> transfer(MInsn) {
>   // A DBG_VALUE marks the beginning of a new range.
>   if (MInsn is a DBG_VALUE(var, loc)) {
> 
>     for ((rvar, start) : open_ranges[BB])
>       // A DBG_VALUE terminates a range started by a previous
>       // DBG_VALUE for the same variable, if the described pieces
>       // overlap.
>       if (var == rvar && piece_overlaps(MInsn, start)) {
>         ranges[var].push_back((start, MInsn));
>         open_ranges[BB][rvar].remove(start));
>       }
>     open_ranges[BB][var].push_back(MInsn)
>   }
> 
>   // A def of a register may mark the end of a range.
>   if (MInsn is a def(reg)) {
>     for ((var, start) : open_ranges[BB])
>       if (start.loc == reg) {
>         ranges[var].push_back((start, MInsn));
>         open_ranges[BB][var].remove(start));
>       }
> 
>   // End all ranges in the current basic block.
>   if (MInsn.isTerminator())
>     for (range : open_ranges[BB]) {
>       ranges[var].push_back(range);
>       open_ranges[BB].remove(range);
>       outgoing_loc[BB][range.var].push_back(range.loc);
>       changed = true;
>    }
> }
> 
> // Visit the beginning of a basic block BB with two predecessors.
> join(BB, BB1, BB2) {
>   for ((var1, loc1) : outgoing_loc[BB1])
>     for (loc2 : outgoing_loc[BB2][var1])
>       // It's only safe to propagate a range if all predecessors end
>       // with the same location.
>       if (loc1.kind == loc2.kind &&
>           loc1.val  == loc2.val)
>         // Not sure how to best implement this.
>         open_ranges[BB][var].push_back(new DBG_VALUE(loc1));
> 
> Yep, that's kind of problem, we can't modify MachineFunction at
this point.
>  
> }
> 
> analyze(MF) {
>   for (BB : MF)
>     workset.push_back(BB);
> 
>   while (!workset.empty()) {
>     changed = false;
>     for (MI : workset.pop_front())
>       transfer(MI)
>     if (changed)
>       workset.append(BB.successors())
>    }
> }
> 
> A couple of observations about the pseudo-code above: The analysis
> terminates, because ranges is write-only, making this effectively a
> bit-vector problem. It is also safe, because we are only propagating
> ranges into the next basic block if all predecessors have the same
> outgoing location for a variable piece.
> 
> One problem that is not addressed by the approach above is how to
> become better at handling variables that are in more than one location
> at once: As Keno noted on llvm-commits recently, the fundamental
> problem is that DbgValueHistoryCalculator cannot safely distinguish
> between a DBG_VALUE that provides an additional valid location and one
> describing an updated location for a variable. IMO this is best
> addressed on a case-by-case basis in the pass that introduces the second
> DBG_VALUE, either by marking it as alternative location or not emitting
> it at all, but I’m open for suggestions.
> 
> Comments?
> 
> -- adrian
> 
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu <mailto:LLVMdev at cs.uiuc.edu>        
http://llvm.cs.uiuc.edu <http://llvm.cs.uiuc.edu/>
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
<http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev>
> 
> 
> 
> -- 
> Alexey Samsonov
> vonosmas at gmail.com <mailto:vonosmas at gmail.com>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150710/5c2c18b0/attachment.html>