Page MenuHomePhabricator

Extending debug ranges
ClosedPublic

Authored by tvvikram on Aug 11 2015, 3:21 AM.

Details

Summary

This patch is an early implementation to extend debug ranges and provide multiple location support for debug variables. This work is based on the idea put forward in the mail thread: http://lists.cs.uiuc.edu/pipermail/llvmdev/2015-June/087109.html

A. Debug Range Extension: Currently, the debug ranges in LLVM end prematurely at the end of every basic block. This patch tries to extend them across basic blocks such that when two predecessors of a basic block have the same variable residing in the same location, a new debug value representing the variable and the location is added at the start of the current basic block.

Example: Consider the following partial code containing only DBG_VALUE instructions:
BB#3:
.
DBG_VALUE %EBX, %noreg, !"n", <!17>; line no:8
.
JMP_1 <BB#5>

BB#4:
.
DBG_VALUE %EBX, %noreg, !"n", <!17>; line no:8
.

BB#5: ; preds - BB#3, BB#4
DBG_VALUE %EBX, %noreg, !"n", <!17>; line no:8 <-- newly inserted
.

Here, BB#5 is a successor of both BB#3 and BB#4. Source variable "n" resides in %EBX on both paths. So a new DBG_VALUE instruction will be added at the start of BB#5 for "n" at location %EBX.

B. Multiple locations: Moved to http://reviews.llvm.org/D11986.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
aprantl added inline comments.Aug 26 2015, 5:33 PM
lib/CodeGen/ExtendDebugRangeLocation.cpp
1 ↗(On Diff #32795)

Ranges are an implementation detail and probably shouldn't show up in the name.

10 ↗(On Diff #32795)

This should ideally be a doxygen comment.

10 ↗(On Diff #32795)

Instead of saying "Fixup", better say:
This pass implements a data flow analysis that propagates debug location information by inserting additional DBG_VALUE instructions into the machine instruction stream.

12 ↗(On Diff #32795)

"This pass internally builds debug location liveness ranges to determine the points where additional DBG_VALUEs need to be inserted."?

16 ↗(On Diff #32795)

Please only document what the code does and don't talk about future extensions.

18 ↗(On Diff #32795)

???

21 ↗(On Diff #32795)

This is not a sound argument. If this were implement in DbgValueHistoryCalculator we wouldn't need to emit any DBG_VALUE intrinsics, because we could just pass the ranges themselves to the backend.

Let's just say that this is a separate pass to facilitate testing and improve modularity.

57 ↗(On Diff #32795)

LLVM build with autobrief, so unless you want more than the first sentence to appear in the brief section, the \brief can/should be omitted from the Doxygen comments.

78 ↗(On Diff #32795)

///

80 ↗(On Diff #32795)

For better readability it might be worth considering using a struct with self-explaining named members instead of an opaque std::pair.

82 ↗(On Diff #32795)

Same here.

139 ↗(On Diff #32795)

Full sentences ending with "." are preferred. That said, this comment essentially repeats the function name... what it should say is that it expects DebugValues as inputs.

159 ↗(On Diff #32795)

Better: \return the instruction following \c MI.

161 ↗(On Diff #32795)

This could be split out into a separate patch and/or tested separately.

179 ↗(On Diff #32795)

Could this be written as a ranged-based for?

190 ↗(On Diff #32795)

Please run the path through clang-format.

238 ↗(On Diff #32795)

missing . at the end

239 ↗(On Diff #32795)

range-based for?

250 ↗(On Diff #32795)

remove the comment.

262 ↗(On Diff #32795)

doxygen

280 ↗(On Diff #32795)

doxygen. (the coding guidelines prefer only a single comment on the declaration, so they don't get out of sync).

281 ↗(On Diff #32795)

please remove references to multiple locations in this patch

289 ↗(On Diff #32795)

Why is this correct?

306 ↗(On Diff #32795)

Are constants and memory locations handled in a safe/correct way?

312 ↗(On Diff #32795)

The enclosing function is very long. I suggest splitting out certain pieces into separate functions with self-explanatory names so a reader can understand what the function does on a higher level. This looks like a good candidate for that.

tvvikram added a comment.EditedAug 27 2015, 5:09 AM

Thanks so far. I added a bunch of more detailed comments inline.

I will make the suggested changes and submit a new patch.

I am not sure about the name for the new pass. Please suggest.
I have a couple of names though - ImproveDebugValues.cpp, DebugValueDFA.cpp (DFA: DataFlow Analysis). Please confirm.

Thanks so far. I added a bunch of more detailed comments inline.

I will make the suggested changes and submit a new patch.

I am not sure about the name for the new pass. Please suggest.
I have a couple of names though - ImproveDebugValues.cpp, DebugValueDFA.cpp (DFA: DataFlow Analysis). Please confirm.

To prevent you from having to rename the file and pass more than once, let's defer this decision until the very end.
Another possible name is "DebugValuePropagation", although "LiveDebugValues", or "DebugValueLiveness" would actually be the most fitting, because we are doing a Liveness analysis. This conflicts with the existing LiveDebugVariables pass that consumes all DBG_VALUEs that describe vregs, builds a side-table that is used during register allocation and writes out new DBG_VALUEs with real registers after regalloc is done. Perhaps we could rename the old LiveDebugVariables to "MaterializeDebugValues", or "RegallocDebugValues?

To recap, my vision is that:

  • the old LiveDebugVariables becomes a simple and fast BB-local pass that emits the bare minimum of DBG_VALUEs and
  • this new pass then performs the control-flow-aware liveness DFA that extends their range beyond BB boundaries by inserting enough DBG_VALUEs that
  • the DWARF backend may again assume that DBG_VALUEs are BB-local (and only performs a very simple merging of adjacent ranges).

This way we will end up with small, understandable, and (via MIR) testable passes with a well-defined scope that do one task well.

tvvikram updated this revision to Diff 33700.Sep 1 2015, 9:22 AM
tvvikram marked 25 inline comments as done.

Made review comment changes.

Thanks so far. I added a bunch of more detailed comments inline.

I will make the suggested changes and submit a new patch.

I am not sure about the name for the new pass. Please suggest.
I have a couple of names though - ImproveDebugValues.cpp, DebugValueDFA.cpp (DFA: DataFlow Analysis). Please confirm.

To prevent you from having to rename the file and pass more than once, let's defer this decision until the very end.

Thanks.

Another possible name is "DebugValuePropagation", although "LiveDebugValues", or "DebugValueLiveness" would actually be the most fitting, because we are doing a Liveness analysis. This conflicts with the existing LiveDebugVariables pass that consumes all DBG_VALUEs that describe vregs, builds a side-table that is used during register allocation and writes out new DBG_VALUEs with real registers after regalloc is done. Perhaps we could rename the old LiveDebugVariables to "MaterializeDebugValues", or "RegallocDebugValues?

The new pass could be a place to do generic code changes related to DBG_VALUE instructions like inferring multiple locations, inserting missing DBG_VALUE instructions if possible, etc. If that is the case, I think we should name the pass with a generic name. Otherwise, I am okay with the name changes you suggested.

To recap, my vision is that:

  • the old LiveDebugVariables becomes a simple and fast BB-local pass that emits the bare minimum of DBG_VALUEs and
  • this new pass then performs the control-flow-aware liveness DFA that extends their range beyond BB boundaries by inserting enough DBG_VALUEs that
  • the DWARF backend may again assume that DBG_VALUEs are BB-local (and only performs a very simple merging of adjacent ranges).

    This way we will end up with small, understandable, and (via MIR) testable passes with a well-defined scope that do one task well.

Thanks for the high level view.

lib/CodeGen/ExtendDebugRangeLocation.cpp
16 ↗(On Diff #32795)

Removed.

18 ↗(On Diff #32795)

Removed. Initially, this file was meant to handle any code changes related to DBG_VALUE instructions.

159 ↗(On Diff #32795)

I am not sure about it. MI could already be the last instr in MBB. Anyway, I have removed this routine for now.

161 ↗(On Diff #32795)

Removed. I will submit a separate patch for this.

179 ↗(On Diff #32795)

I was not updating the iterators after erasing 'u' at line 221. I have rewritten the iterators but could not convert it to 'range-based for'.

289 ↗(On Diff #32795)

Unintended comment. Removed.

306 ↗(On Diff #32795)

AFAIK, yes as only register locations are handled now.

333 ↗(On Diff #32795)

Sorry. I had missed out removing this when I separated out the multiple locations patch. Removed.

359 ↗(On Diff #32795)

Removed. I meant that the current implementation support bbs with at most 2 predecessors.

393 ↗(On Diff #32795)

The comparison at line 397 prevented me in converting to 'range based for'.

Thanks, more comments inline!

Side note, the clang coding standards recommend to write every comment in the code as complete sentences, with a "." at the end.

lib/CodeGen/ExtendDebugRangeLocation.cpp
81 ↗(On Diff #33700)

OpenRanges should probably be a local variable in the while (!BBWorklist.empty()) loop in ExtendRanges().

300 ↗(On Diff #33700)

This loop is quadratic and only works for two predecessors. Off the top of my head, what about, e.g, having a SmallDenseMap that stores a separate IncomingLocs for each MBB?

IncomingLocs could be a sorted SmallVector or another SmallDenseMap of

struct IncomingLoc {
  DIVariable* Var;
  MachineInstr Loc;
};

A nullptr for Loc (or a missing entry) means that this value has been determined to be unknown.
Additionally each MBB gets a flag that indicates whether it has been visited or not.

At the end of each MBB, go through the list of successors and immediately join() the OutgoingLocs with the IncomingLocs of the successor. In the join function every input wins over the IncomingLocs of a not-yet-visited MBB, after the first visit the MBB is marked as visited. Likewise, a nullptr (or whatever we use to indicate the kill value) also wins against any other value.

360 ↗(On Diff #33700)

Ok. See my other comment about generalizing the algorithm.

362 ↗(On Diff #33700)

Typically in LLVM transfer functions return bool and this would be written as:

bool Changed = false;
Changed |= transfer(MI)

Thanks, more comments inline!

Side note, the clang coding standards recommend to write every comment in the code as complete sentences, with a "." at the end.

Thanks. I will make the changes and submit a new patch.

Thanks! Any updates?

Thanks! Any updates?

Sorry, I couldn't work on this for quite sometime. I will update and submit the patch as soon as possible.

tvvikram updated this revision to Diff 39892.Nov 11 2015, 3:13 AM

First, sorry for submitting this after a long gap.

The following changes have been made:
a. Make OpenRanges usage local to every mbb.
b. Rewrite 'join' routine - generic implementation by looking at all predecessors of an mbb to extend the debug value ranges across mbb by using IncomingLocs as suggested in the review comment. Previously, the implementation was limited to 1 and 2 predecessors.

tvvikram marked 3 inline comments as done.Nov 11 2015, 3:21 AM
tvvikram added inline comments.
lib/CodeGen/ExtendDebugRangeLocation.cpp
301 ↗(On Diff #39892)

I have maintained InLocs for every MBB. These InLocs will also represent the set of DBG_VALUE instructions already inserted. At every 'join' call, the incoming locations are calculated progressively over the predecessors of the MBB (as suggested). Any new DBG_VALUE instruction calculated is inserted at the start of the MBB as well as to the InLocs of this MBB.

Thanks of the update, this is starting to look really good. I have a couple of comments inline that are mostly about readability. I'll play with the patch and look at the correctness next. Did you make any compile time measurements with the new algorithm? For example, by compiling clang?

lib/CodeGen/ExtendDebugRangeLocation.cpp
67 ↗(On Diff #39892)

I found InlinedVariable to be misleading because the Inlined-At is optional. What about just calling it a DebugVariable and promoting it to a struct?

/// A potentially inlined instance of a variable.
struct DebugVar {
  const DILocalVariable &Var;
  const DILocation *InlinedAt;
}
79 ↗(On Diff #39892)

This should probably be a (Small)DenseSet (=hash map) instead of a std::map.

87 ↗(On Diff #39892)

Instead of having them as members that are cleared for each function, it would be better to make them local variables that are explicitly passed as arguments. It's less error-prone and makes the code easier to read because there is no global state.

199 ↗(On Diff #39892)

This entire loop could be replaced by a use of std::remove_if with the condition in a lambda. I believe it would be more readable this way.

222 ↗(On Diff #39892)

Again, this can be expressed more compactly with std::remove_if.

256 ↗(On Diff #39892)

Since this comparison is duplicated three times why not implement an operator== for VarLoc?

305 ↗(On Diff #39892)

With the operator== (see line 256) this pattern can probably also be collapsed to a std::remove_if.

test/DebugInfo/X86/sret.ll
7 ↗(On Diff #39892)

I believe, we actually want the dwo_id to be hardcoded in this one testcase, because it forces us to think why the hash changed, when it changed.

tvvikram updated this revision to Diff 40162.Nov 13 2015, 10:09 AM
tvvikram marked 9 inline comments as done.

I have made the suggested changes. In few of the test cases I checked using llc --time-passes, the time spent in this pass was <1%.

tvvikram added inline comments.Nov 13 2015, 10:10 AM
test/DebugInfo/X86/sret.ll
7 ↗(On Diff #39892)

I had noticed that the id had changed in one of previous patches. Fortunately, the id getting generated now is same as in trunk. So I have reverted this change in this patch.

I just manually verified that this indeed works as advertised on a couple of old bugreports with debug info + ASAN. Totally awesome!
Couple more inline comments and I think the only major thing left to do here is to agree on a name for the new pass :-)

It worries me a bit that none of the test cases exhibit the case with multiple predecessors that the join() function is implementing (nested ifs without else, switch stmts...). It would be good to add one.

lib/CodeGen/ExtendDebugRangeLocation.cpp
182 ↗(On Diff #40162)

What if MI is, e.g., constant 1 and V.MI is constant 2? Looks like the function would still return true because isDescribedByReg will return 0 of both. We should also compare the kind (const/reg/...) here.

Regression/Unit test that catches these corner cases?

284 ↗(On Diff #40162)

This can now be converted to a range-based for.

339 ↗(On Diff #40162)

Why is it necessary to push it into InLocs here? Wouldn't transfer pick it up automatically from the DBG_VALUE that we just inserted?

386 ↗(On Diff #40162)

This can now be converted to a range-based for.

tvvikram marked 2 inline comments as done.Nov 25 2015, 9:31 AM

I just manually verified that this indeed works as advertised on a couple of old bugreports with debug info + ASAN. Totally awesome!

Good to hear that!

Couple more inline comments and I think the only major thing left to do here is to agree on a name for the new pass :-)

I am okay with any of the names that you had suggested before. Please confirm. Also I will submit the current changes along with pass renaming.

It worries me a bit that none of the test cases exhibit the case with multiple predecessors that the join() function is implementing (nested ifs without else, switch stmts...). It would be good to add one.

I have come up with a test case that does join() with 3 predecessors. Will submit along with pass renaming.

lib/CodeGen/ExtendDebugRangeLocation.cpp
182 ↗(On Diff #40162)

As the TODO in line 203 says, I am handling DBG_VALUEs that describes a register. OpenRanges when built are guaranteed to describe a register.

339 ↗(On Diff #40162)

InLocs also represent the list of already inserted DBG_VALUEs; because we do not want to insert redundant DBG_VALUEs. Only new incoming locs that are calculated during each join() call for the MBB are inserted.

My vote is to call the pass LiveDbgValues. This is analogous to the well known "live variables" data-flow analysis and thus succinctly describes what this pass is doing (Compute the set of live DBG_VALUEs at each basic block and insert them).

Unless somebody else objects IMO this pass is good to land then.
On the road ahead there are several important things that need to be done in short order, but can/should be done in separate commits:

  • Remove the broken propagation in LiveDebugVariables (https://llvm.org/bugs/show_bug.cgi?id=24563) to fix the correctness issue noted in PR24563. This will also reclaim some of the performance we are spending in this new pass.
  • DbgValueHistoryCalculator contains a hack (collectChangingRegs()) to identify the frame pointer. With this pass in place, we should be able to remove it and rely on DBG_VALUEs without any loss of functionality.
  • Implement the missing location types (constant values, memory locations, fp constants ...)

thanks for all your work,
adrian

tvvikram updated this revision to Diff 41897.Dec 4 2015, 10:38 AM

Renamed the pass as "LiveDebugValues".

aprantl accepted this revision.Dec 8 2015, 8:33 AM
aprantl edited edge metadata.

This is ready to land now. Thanks again!

This revision is now accepted and ready to land.Dec 8 2015, 8:33 AM

Commit rL255096. Thank you!

jfb added a subscriber: jfb.Dec 8 2015, 11:57 PM

Hi Vikram,

This seems to break WebAssembly tests:

https://build.chromium.org/p/client.wasm.llvm/builders/linux/builds/726/steps/steps/logs/stdio

Other buildbots also look very sad:

http://lab.llvm.org:8011/console

Could you look into it?

Thanks,

JF

reverted r255101

@joker.eph Thanks for reverting.
@jfb I am looking into it.

tvvikram updated this revision to Diff 42538.Dec 11 2015, 10:27 AM
tvvikram edited edge metadata.

I got to know that I had built and tested only for certain targets (sorry that I didn't realize about it earlier). I had to make a couple of minor fixes to make the patch work for all targets.

Just to clarify, I am using cmake+Ninja build with the the following command to configure cmake:
cmake -G Ninja -DCMAKE_BUILD_TYPE="Debug" -DLLVM_TARGETS_TO_BUILD="all" -DLLVM_EXPERIMENTAL_TARGETS_TO_BUILD="WebAssembly" -DLLVM_BINUTILS_INCDIR=/usr/include -DBUILD_SHARED_LIBS=1 -DCMAKE_CXX_FLAGS=" -gdwarf-2 " /path/to/llvmsrc/

and got the following result with "ninja check":
[46/46] Running the LLVM regression tests

  • Testing: 15343 tests, 8 threads --

Testing: 0 .. 10.. 20.. 30.. 40.. 50.. 60.. 70.. 80.. 90..
Testing Time: 224.82s

Expected Passes    : 15157
Expected Failures  : 131
Unsupported Tests  : 55

I got similar results with Release build too. Please let me know if the results look fine and if I need to run any more tests before committing.

This sounds reasonable to me.
We can't test every possible configuration before committing anyway (Windows, Linux, OS X, etc.), this is why we revert easily.

Please go ahead and re-commit.