This is an archive of the discontinued LLVM Phabricator instance.

[DebugInfo] Terminate more kinds of location-list ranges at the end of basic blocks
ClosedPublic

Authored by jmorse on Mar 15 2019, 1:12 PM.

Details

Summary

This patch fixes PR40795 [0] by preventing constant-value variable locations from flowing into nearby basic blocks during location-list calculation, and propagates constant-value locations in LiveDebugValues to compensate for lost variable coverage.

As documented in comment 8 of the PR, the range that a constant-value DBG_VALUE defines a variable location over does not currently terminate at the end of the basic block the DBG_VALUE is in. Instead, its range is valid across all basic blocks (as finally laid out) until another DBG_VALUE for the variable is seen. This often covers many instructions where the variable didn't actually have a location, and even down code paths where the variable was never assigned the constant value. Fix this by keeping a set of InlinedEntity's that are not register locations, and terminating them all at the end of the block. I believe this problem was also true for stack spill locations.

In addition to this, LiveDebugValues does not propagate constant-value variable locations, so with only that change we would lose constant-value variable locations outside of the defining basic block -- on a clang3.4 build this leads to a 2% drop in overall scope-bytes-covered (45% -> 43%). To get around this, I've fixed LiveDebugValues to also propagate constant values in the same way it does other values. There are zero algorithmic changes, it just propagates from one place to another better now, although now VarLoc::operator== does more work to compare CImmediate / FPImmediate objects, as I don't believe their pointers are uniqued.

This probably leads to greater memory use due to increased DBG_VALUE propagation / replication, although I haven't made any memory-usage measurements. I've timed a clang-3.4 build using llvm/clang r354569 with and without this patch; the time differences were negligible and well within the margin of error.

Test changes: due to constant-value DBG_VALUE propagation COFF/pieces.ll now gets several new .Ltmp labels, which I've updated accordingly. New lines 63-66 reflect the fact that a new basic block has a variable location for loop_csr:o now where previously it was missing (the constant-value location is legitimate). Line 46 gets a new & spurious constant-value DBG_VALUE -- I believe this is due to the LiveDebugValues-ignores-backedges problem in PR38997 [1].

MIR/AArch64/implicit-def-dead-scope.mir: I'm not sure what to make of this test: it runs after LiveDebugValues, drops a constant DBG_VALUE somewhere, and expects it to be promoted to being function-wide. That no longer happens (checks updated) and I'd argue that given the control flow merges mean that it shouldn't. Possibly some input required here.

X86/fission-ranges.ll: LiveDebugValues now detects and records stack spills in the large loop produced by this input, hence many more location entries. It doesn't fully cover the whole function as none of the phi's have dbg.values in the input.

Added test: this is four diamond-pattern if conditionals in MIR, with different combinations of DBG_VALUE with register/constant locations on the branches of the condition. The CHECKs test how LiveDebugValues propagates them when control flow merges (it should when the locations agree; not when they do not), while the RANGES checks test that DbgEntityHistoryCalculator correctly terminates the range of variable locations at the end of basic blocks.

[0] https://bugs.llvm.org/show_bug.cgi?id=40795
[1] https://bugs.llvm.org/show_bug.cgi?id=38997#c6

Diff Detail

Event Timeline

jmorse created this revision.Mar 15 2019, 1:12 PM

As documented in comment 8 of the PR, the range that a constant-value DBG_VALUE defines a variable location over does not currently terminate at the end of the basic block the DBG_VALUE is in. Instead, its range is valid across all basic blocks (as finally laid out) until another DBG_VALUE for the variable is seen. This often covers many instructions where the variable didn't actually have a location, and even down code paths where the variable was never assigned the constant value.

Isn't that a symptom of previous passes failing to insert a dbg.value(undef) when they deleted a dbg.value? I'm trying to figure out what a legitimate example for this would look like.

Isn't that a symptom of previous passes failing to insert a dbg.value(undef) when they deleted a dbg.value? I'm trying to figure out what a legitimate example for this would look like.

Awkwardly yes and no -- the pass that doesn't insert dbg.value(undef) is mem2reg constructing SSA IR (example below). However LiveDebugValues and DbgEntityHistoryCalculator normally cover for this issue and appear to be designed to do so. I'm having a hard time describing what's wrong here, so I'm going to state two beliefs; explain how they works with register variable locations right now; and then how it doesn't work with constant variable locations (hence this patch). It's my (additional) belief that fixing these things at the LLVM-IR level would require an infeasibly large number of dbg.value intrinsics to be inserted, in the order of "maximal SSA".

The two beliefs are:

  • We eventually get (and need) a DBG_VALUE for every source variable in every basic block recording its location for that block, and
  • When control flow merges, we infer variable locations from the parent blocks, or terminate locations if they're inconsistent.

The first seems obvious: to make linear ranges of locations for DWARF location lists, we need to scan the machine code and record variable locations. However AFAIUI the IR has no control over how the target backend will chose to lay out blocks. Consider this example where I've reversed the control flow:

define dso_local i32 @_Z3foob(i1 %cond) #0 !dbg !12 {
entry:
  br label %bb2

exit: 
  ret i32 %value, !dbg !30

bb1: 
  br label %exit, !dbg !26

bb2:
  %value = select i1 %cond, i32 0, i32 1 
  call void @llvm.dbg.value(metadata i32 %value, metadata !23, metadata !DIExpression()), !dbg !24
  br label %bb1
}

When compiled with llc -O0 the block layout is kept the same in assembly (although that's not guaranteed). The dbg.value dominates the 'bb1' and 'exit' blocks, and when using a register in the example here it's location is correctly propagated into those blocks. However if one replaces the dbg.value operand with a constant, the location list only covers the last jmp of the machine code in 'bb2'. Furthermore, if you put a dbg.value of a different constant in the 'entry' block, according to the IR it dominates only "br label %bb2" and the select, but in the location-lists it will cover the whole function up to the last jmp. The main message here is that IR dominance is manually preserved by LiveDebugValues/DbgEntityHistoryCalculator for registers, but not constants, and because block layout is under the targets control the IR cannot fix this without wholesale copying of dbg.values into all blocks.

Problem 2, what to do when control flow merges, can be demonstrated with this example C++:

extern int f();
int global = 0;
int foo(bool cond) {
    int bar;
    if (cond) {
        bar = f();
        global = bar;
    } else {
        bar = f();
        global = bar;
    }
    return bar;
}

The variable of interest is going to be "bar". If I compile it with the following chain of things, which I believe disables all optimisations except mem2reg, using a month-old r354365:

clang++ ./test.cpp -g -Xclang -disable-O0-optnone -Xclang -disable-llvm-optzns -emit-llvm -c -S -o - | opt -mem2reg -S | llc -o - -O0 -filetype=obj | llvm-dwarfdump-6.0 -

Then some fairly obvious things happen: we get a dbg.value for "bar" on each side of the conditional branch, a PHI node in the exit block to merge the two values of "bar", a dbg.value for the PHI, then a return instruction. This is unremarkable: but interesting things start happening if "return bar" is replaced by "return 0". In that case, the PHI node in the exit block disappears, as does the dbg.value in the exit block. We're left with this IR after mem2reg:

; <label>:4:
  %5 = call i32 @_Z1fv(), !dbg !21
  call void @llvm.dbg.value(metadata i32 %5, metadata !23, metadata !DIExpression()), !dbg !24
  store i32 %5, i32* @global, align 4, !dbg !25
  br label %9, !dbg !26

; <label>:6:
  %7 = call i32 @_Z1fv(), !dbg !27
  call void @llvm.dbg.value(metadata i32 %7, metadata !23, metadata !DIExpression()), !dbg !24
  store i32 %7, i32* @global, align 4, !dbg !29
  br label %8

; <label>:8:
  ret i32 0, !dbg !31

Here there's no explicit termination of the live range of values of "bar" in %5 and %7, either in IR or in debug intrinsics. "bar" isn't used after control flow merges into the exit/return block, hence no phi or dbg.value. However, there is also no dbg.value(undef) terminating the variable. Instead, for registers, LiveDebugValues determines where variable locations merge and either adds a DBG_VALUE for the merged location, or nothing if it can't determine a location, which implicitly terminates the location range. Neither the propagation nor the termination happen for constants (fixed by this patch).

If we were to fix mem2reg to insert dbg.value(undef) in these circumstances I believe we'd have to introduce a large number of these intrinsics on every control flow merge, and we'd effectively be embedding the early liveness properties of the program into the debug metadata, even if the liveness then changes over the course of optimisation. Plus, the design clearly works for registers right now, it's just not implemented for constants.

In summary, I think LiveDebugValues/DbgEntityHistoryCalculator are inferring facts about variable locations to avoid having to record all variable locations in all basic blocks at the start of compilation. However, their implementation is not complete, as they mostly ignore constant locations. IMO it's a better fix to make their implementation complete, rather than to increase the number of dbg.values that have to be recorded.

Thanks for the thoughtful writeup!

I think LiveDebugValues/DbgEntityHistoryCalculator are inferring facts about variable locations to avoid having to record all variable locations in all basic blocks at the start of compilation.

"at the start of compilation" really means in mem2reg, at least for Clang. As you pointed out, there is no way to preserve the dbg.value in the exit block in mem2reg without introducing an phi node, but doing so would change codegen, which is not an option. So I guess the answer to my question whether this is indicative of a bug in an earlier pass is: not necessarily. If we want to preserve our ability to get a chance of having debug info for bar in the exit block, we have to accept that mem2reg doesn't insert undefs. IMO, that is not elegant, but a good trade-off.

It would be great to include a section on mem2reg and your examples to SourceLevelDebugging.rst since this will no doubt come up again in the future!

If we go forward with this patch — the reason why we don't have dbg.values in the exit block in your example is because we can't introduce a new PHI for bar. But if bar is a *constant*, mem2reg could do a miniature version of LiveDebugValues that only applies to constants. Conceptually, we could move the ability to propagate constants from LiveDebugValues into mem2reg. I'm not sure if it will be worth the extra effort, but we can think about it.

So I guess the answer to my question whether this is indicative of a bug in an earlier pass is: not necessarily.

Indeed, I think it's an engineering compromise that seems to work fairly well, and requires the behaviour in LiveDebugValues/etc for correctness,

It would be great to include a section on mem2reg and your examples to SourceLevelDebugging.rst since this will no doubt come up again in the future!

I'll be doing this immediately to ensure everyone's on the same page, plus I think the way the backend debug-stuff works has now clicked in my mind.

If we go forward with this patch — the reason why we don't have dbg.values in the exit block in your example is because we can't introduce a new PHI for bar. But if bar is a *constant*, mem2reg could do a miniature version of LiveDebugValues that only applies to constants. Conceptually, we could move the ability to propagate constants from LiveDebugValues into mem2reg. I'm not sure if it will be worth the extra effort, but we can think about it.

(I'll get onto this once the docs for how this is supposed to work have been nailed down).

"at the start of compilation" really means in mem2reg, at least for Clang. As you pointed out, there is no way to preserve the dbg.value in the exit block in mem2reg without introducing an phi node, but doing so would change codegen, which is not an option.

Without wanting to stray too far off the topic at hand, this is the sort of thing we could consider doing if we had a dedicated -Og mode (and presumably a corresponding optdebug IR attribute akin to optsize/minsize). FWIW I'm going to organise a roundtable at EuroLLVM to try and kick off some discussion in that area, although obviously I'll reflect everything of importance back to the list for those who aren't able to attend.

aprantl added inline comments.Mar 21 2019, 8:54 AM
lib/CodeGen/AsmPrinter/DbgEntityHistoryCalculator.cpp
392

The title says "constant" but this seems to also affect memory locations. Is that intentional?

lib/CodeGen/LiveDebugValues.cpp
148

ConstantFPKind and ConstantIntKind ?

218

The fact that this code exists means that ConstantFP/Ints are not unique?

443

Can you add an &&"errormessage" to explain what is being asserted here?

jmorse marked 3 inline comments as done.Mar 22 2019, 9:08 AM
jmorse added inline comments.
lib/CodeGen/AsmPrinter/DbgEntityHistoryCalculator.cpp
392

It's intentional -- the "location falls through to subsequent blocks" issue described as problem 1 above, also applies to stack spills too. Plus in LiveDebugValues, stack spill DBG_VALUEs weren't propagated between basic blocks either (which this patch patches).

I think I missed it in the title as I was trying to compress what I was saying down into something readable, and wound up cutting out too much, curses.

lib/CodeGen/LiveDebugValues.cpp
148

Related to unique-ing, see comment below,

218

Hmmmmmm, I'd made the assumption that ConstantFP/Ints aren't unique'd as none of the constructors/static getters took an LLVMContext so couldn't be made unique. Digging further in however shows ConstantInt::get acquires a context through the passed-in type, and do get uniqued. I'll remove this in the next update.

dstenb added a subscriber: dstenb.Mar 28 2019, 9:14 AM
dstenb added inline comments.
lib/CodeGen/AsmPrinter/DbgEntityHistoryCalculator.cpp
291

Just as a small heads up, I uploaded D59941 and D59942 which aims to improve handling of fragments in DbgEntityHistoryCalculator and its users. If people think that the structure that those patches introduces is a good idea, then it should be possible to adapt this patch to that by using the LiveEntries map, which keeps indices for all currently open debug values. That way we can ensure that all open non-overlapping fragments are closed at the end of the basic block.

jmorse updated this revision to Diff 196646.Apr 25 2019, 9:01 AM
jmorse retitled this revision from [DebugInfo] Terminate constant-value location-list ranges at the end of basic blocks to [DebugInfo] Terminate more kinds of location-list ranges at the end of basic blocks.
jmorse added a reviewer: dstenb.

I've rebased this patch to be based on r358073, Davids improvements to DbgEntityHistoryCalculator. Rather than tracking non-register DBG_VALUEs separately, this patch now iterates over all open DBG_VALUE ranges and either terminates the constant ones, or clobbers the register ones. This should be the same behaviour as the previous patch.

There's some ongoing sketchyness with stack-slot referencing DBG_VALUEs: they refer to a register, but the stack pointer doesn't appear in the ChangingRegs set, and so they never get terminated. I'll open a PR for that rather than messing with it here.

In LiveDebugValues I've reduced the complexity of operator== as we can rely on constant-value uniquing, and thus pointer uniquing. I've added a comparison for the VarLoc Kind however, as I'm a little worried that a RegNo / Immediate-value collision could occur.

The COFF pieces.ll test has changed slightly further: the ranges of loop_csr:o now terminate at the end of the block where the "loopskip_start" label is, which is more correct than before.

I think I'm mostly fin with this now, thanks!

lib/CodeGen/AsmPrinter/DbgEntityHistoryCalculator.cpp
367

DMI -> DbgValue ?

372

This comment is sort of misleading because your test also triggers for values where isIndirectDebugValue() is true. I think the code does what you want, but the condition also triggers for register-indirect values.

dstenb added inline comments.Apr 25 2019, 12:22 PM
lib/CodeGen/AsmPrinter/DbgEntityHistoryCalculator.cpp
380

I think you can use Ent instead of DbgValues.getEntry(Pair.first, Idx) here?

dstenb added inline comments.Apr 25 2019, 2:47 PM
lib/CodeGen/AsmPrinter/DbgEntityHistoryCalculator.cpp
380

Oh, no. Sorry. As we may add an entry to the vector when creating the clobbering entry, Ent may be stale.

jmorse updated this revision to Diff 196820.Apr 26 2019, 2:31 AM

Rename variable, improve comment, sprinkle a little clang-format.

jmorse marked 11 inline comments as done.Apr 26 2019, 2:35 AM
jmorse added inline comments.
lib/CodeGen/AsmPrinter/DbgEntityHistoryCalculator.cpp
372

I've adjusted the comment to reflect reality; the termination of indirect DBG_VALUEs is the subject of some oddness (PR41600) that's preserved in this patch.

380

Alas, I found that out the hard way when writing it ._.

aprantl accepted this revision.Apr 26 2019, 2:50 PM
This revision is now accepted and ready to land.Apr 26 2019, 2:50 PM
This revision was automatically updated to reflect the committed changes.
jmorse marked 2 inline comments as done.