This is an archive of the discontinued LLVM Phabricator instance.

[DebugInfo] Improve handling of clobbered fragments
ClosedPublic

Authored by dstenb on Mar 28 2019, 8:53 AM.

Details

Summary

Currently the DbgValueHistorymap only keeps track of clobbered registers
for the last debug value that it has encountered. This could lead to
preceding register-described debug values living on longer in the
location lists than they should. See PR40283 for an example. This
patch does not introduce tracking of multiple registers, but changes
the DbgValueHistoryMap structure to allow for that in a follow-up
patch. This patch is not NFC, as it at least fixes two bugs in
DwarfDebug (both are covered in the new clobbered-fragments.mir test):

  • If a debug value was clobbered (its End pointer set), the value would still be added to OpenRanges, meaning that the succeeding location list entries could potentially contain stale values.
  • If a debug value was clobbered, and there were non-overlapping fragments that were still live after the clobbering, DwarfDebug would not create a location list entry starting directly after the clobbering instruction. This meant that the location list could have a gap until the next debug value for the variable was encountered.

Before this patch, the history map was represented by <Begin, End>
pairs, where a new pair was created for each new debug value. When
dealing with partially overlapping register-described debug values, such
as in the following example:

DBG_VALUE $reg2, $noreg, !1, !DIExpression(DW_OP_LLVM_fragment, 32, 32)
[...]
DBG_VALUE $reg3, $noreg, !1, !DIExpression(DW_OP_LLVM_fragment, 64, 32)
[...]
$reg2 = insn1
[...]
$reg3 = insn2

the history map would then contain the entries [<DV1, insn1>, [<DV2, insn2>].
This would leave it up to the users of the map to be aware of
the relative order of the instructions, which e.g. could make
DwarfDebug::buildLocationList() needlessly complex. Instead, this patch
makes the history map structure monotonically increasing by dropping the
End pointer, and replacing that with explicit clobbering entries in the
vector. Each debug value has an "end index", which if set, points to the
entry in the vector that ends the debug value. The ending entry can
either be an overlapping debug value, or an instruction which clobbers
the register that the debug value is described by. The ending entry's
instruction can thus either be excluded or included in the debug value's
range. If the end index is not set, the debug value that the entry
introduces is valid until the end of the function.

Changes to test cases:

  • DebugInfo/X86/pieces-3.ll: The range of the first DBG_VALUE, which describes that the fragment (0, 64) is located in RDI, was incorrectly ended by the clobbering of RAX, which the second (non-overlapping) DBG_VALUE was described by. With this patch we get a second entry that only describes RDI after that clobbering.
  • DebugInfo/ARM/partial-subreg.ll: This test seems to indiciate a bug in LiveDebugValues that is caused by it not being aware of fragments. I have added some comments in the test case about that. Also, before this patch DwarfDebug would incorrectly include a register-described debug value from a preceding block in a location list entry.

Diff Detail

Repository
rL LLVM

Event Timeline

dstenb created this revision.Mar 28 2019, 8:53 AM

This patch depends on four preceding refactoring commits. I avoided adding reviewers to two of them (I should perhaps have done the same for the other two) to avoid spamming all of you (who probably deals with enough revisions as it is), but they are up for review.

What's the performance impact of this change? Specifically, I'd be interested in the wall clock time difference for building an RelWithDebInfo+asan build of clang.

include/llvm/CodeGen/DbgEntityHistoryCalculator.h
26 ↗(On Diff #192645)

///

28 ↗(On Diff #192645)

This should be the second paragraph of the class doxygen comment above (i.e., the non-brief part).

44 ↗(On Diff #192645)

/// etc..

lib/CodeGen/AsmPrinter/DbgEntityHistoryCalculator.cpp
111 ↗(On Diff #192645)

Do we really need the properties of a std::map here and in the line above?
So far every time I tried using a std::map in AsmPrinter a std::vector + std::sort turned out to be faster and to use less memory.

152 ↗(On Diff #192645)

/// and \p Var

(Asan created really large basic blocks and is therefore a great stress test for dbg value handling)

dstenb added a comment.Apr 2 2019, 1:07 AM

What's the performance impact of this change? Specifically, I'd be interested in the wall clock time difference for building an RelWithDebInfo+asan build of clang.

I applied the whole patch series (including the follow-up patch, D59942), and ran through five compilations with respectively without the patches using the following Cmake configuration:

cmake -G Ninja -DCMAKE_BUILD_TYPE=RelWithDebInfo -DLLVM_USE_SANITIZER=Address -DLLVM_TARGETS_TO_BUILD='X86' -DLLVM_PARALLEL_LINK_JOBS=4 -DLLVM_USE_LINKER=gold

I ran the compilations on an 8-thread i7-8650U machine with 32 GBs of RAM.

This gave the following measurements:

Master:
real time: 37m34s, 37m32s, 37m31s, 37m30s, 37m28s
average real time: 37m31s

Patched:
real time: 37m40s, 37m38s, 41m43s, 37m34s, 37m37s
average real time: 38m26s

As seen, the wall clock for four of the five patched runs is increased by a few seconds compared to master. The run that increases by four minutes I suspect is simply due to some scheduled work during the night.

dstenb updated this revision to Diff 193286.Apr 2 2019, 7:30 AM
dstenb marked 2 inline comments as done.

Doxygenize comments.

dstenb marked 3 inline comments as done.Apr 2 2019, 7:32 AM
dstenb added inline comments.
lib/CodeGen/AsmPrinter/DbgEntityHistoryCalculator.cpp
111 ↗(On Diff #192645)

There is at least be no need for iterators to be valid after insertion/deletion, nor is the iteration order important for determinism, which I guess is the two of the main benefits of std::map compared to LLVM's own map implementations. I tried switching both to DenseMap, but I did at least not see any effect on the build time when building the RelWithDebInfo+asan clang binary, but I'm not sure what conclusions I should draw from that.

I will look into switching both to sorted vectors.

aprantl added inline comments.Apr 2 2019, 4:33 PM
lib/CodeGen/AsmPrinter/DbgEntityHistoryCalculator.cpp
111 ↗(On Diff #192645)

... or sorted llvm::SmallVectors.

dblaikie added inline comments.Apr 2 2019, 4:40 PM
lib/CodeGen/AsmPrinter/DbgEntityHistoryCalculator.cpp
111 ↗(On Diff #192645)

Usually the issue for this tradeoff (map/set (be it standard or LLVM's custom data structures) versus sorted vector (be it std::vector or SmallVector)) is whether or not there's a separate "gather" and "lookup" phase.

If lookups are required while the data structure is also growing, then it's probably inefficient to keep resorting the data structure to keep those lookups efficient.

if there's a defined point where all building is done (& no querying - so you probably know/can guarantee you aren't inserting duplicates without having to test), a single sort and then purely lookup from that point on.

Is that the case here?

dstenb marked an inline comment as done.Apr 3 2019, 6:52 AM
dstenb added inline comments.
lib/CodeGen/AsmPrinter/DbgEntityHistoryCalculator.cpp
111 ↗(On Diff #192645)

I don't think this is the case here. There is not really separate "gather" and "lookup" phases for the maps, and instead the insertion and querying is interleaved. Both maps may grow/shrink when encountering new debug values or clobbering instructions throughout the iteration of the machine function, so there is not really a defined point where we know we are done building the maps.

aprantl accepted this revision.Apr 8 2019, 11:39 AM
This revision is now accepted and ready to land.Apr 8 2019, 11:39 AM