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