Page MenuHomePhabricator

[DebugInfo] LiveDebugValues: don't create transfer records for potentially invalid locations
Needs ReviewPublic

Authored by jmorse on Sep 12 2019, 7:43 AM.

Details

Summary

This patch is the counter-part to D67393, and aims to solve the second problem mentioned there, that transfers which are found to be invalid after location propagation occurs should not be inserted. The solution is simple: just don't record transfers until the in-locations are all known to be correct, and then reprocess all instructions a final time creating transfers.

This involves touching every instruction in the program again, which is unfortunate, but an alternate implementation I wrote adds ~150 lines of code to try and unwind chains of transfers, involving a lot of additional complexity. IMO, this is a reasonable trade-off. As a bonus though, because we don't generate a transfer every time we look at a block, we don't generate redundant identical DBG_VALUEs if we re-visit a block.

There's a fractional reduction in scope-bytes-covered with this patch (<0.1%), all which must have been invalid.

(I'll have some asan-build-time measurements of this in a couple of hours).

Diff Detail

Event Timeline

jmorse created this revision.Sep 12 2019, 7:43 AM
Herald added a project: Restricted Project. · View Herald TranscriptSep 12 2019, 7:43 AM
jmorse marked an inline comment as done.
jmorse added inline comments.
test/DebugInfo/MIR/X86/live-debug-values-bad-transfer.mir
17–19

I forgot to say in the summary: the absence of this incorrect DBG_VALUE is checked by the --implicit-check-not given to FileCheck.

just don't record transfers until the in-locations are all known to be correct

I'm having trouble with this statement conceptually. Aren't in-locations coming in through join() always correct, just that we didn't reach a fixpoint yet? I'm assuming that at the beginning all in-locations are unknown and only when all incoming basic blocks have outgoing locations, join() adds new incoming locations to be processed. I guess this boils down to how we are not really modeling "unknown" currently?

lib/CodeGen/LiveDebugValues.cpp
488

When is Transfers null?

I'm assuming that at the beginning all in-locations are unknown and only when all incoming basic blocks have outgoing locations, join() adds new incoming locations to be processed.

Ah, this is where the implementation diverges, in fact if all incoming blocks have the same outgoing location *or* unknown for a variable, join() will consider it a valid live-in location. I think it has to be this way because of loops -- for a location that is live throughout a loop, there's a circular dependency between the outgoing location for the back-edge and the live-in location for the loop header. Right now we assume the location is correct for any unknown blocks, and have to invalidate locations later if that doesn't turn out to be true. See for example D66599.

I guess this boils down to how we are not really modeling "unknown" currently?

It turns out to be even more exciting than that -- consider this IR [0] which has badly behaved, but completely legal control flow. It's illustrated in this highly sophisticated diagram [1]. A single variable location (toast==0) is created in the entry block, and then invalidated with an undef dbg.value in loop 3. Because every non-entry/non-exit block is reachable from every other block, the location-invalidation has to be propagated to them all. However, it takes at least one LiveDebugValues iteration for the invalidation to traverse a back-edge, so it takes two LiveDebugvalues iterations for the invalidation to move up the CFG and reach loop1. In that time, all the "unknown" blocks have been processed, and as a result locations have to transition from "true" to "false", rather than "unknown" to "false". It might be possible to generate a situation where something transitions from "false" to "true" too, but I haven't looked closely at that yet.

I think the fact that this is happening means I've made LiveDebugValues depart from peoples expectations, you wrote in the 2016 mailing list dicsussion [2]

the information at the nodes can only move in one direction in the lattice and can change at most once.

which isn't true any more because of D66599 removing locations. I suspect I've turned LiveDebugValues into a data-flow-like algorithm rather than a joining-lattices algorithm. Whether this is a good idea or not probably needs discussing; it's all been in aid of getting rid of invalid locations though.

[0] https://reviews.llvm.org/P8163
[1] https://imgur.com/a/YdE9kN7
[2] https://groups.google.com/forum/#!search/llvm-dev/llvm-dev/nlgxIfDQnhs/4zsGbuoTAAAJ

jmorse marked an inline comment as done.Sep 13 2019, 7:43 AM
jmorse added inline comments.
lib/CodeGen/LiveDebugValues.cpp
488

I've made the main loop (line 1392 on this patch) pass null to signify it doesn't want transfers recording.

A few revisions ago LiveDebugValues was passing enum values "transferChanges", "dontTransferChanges" to indicate whether transfers should be examined, we could do something similar here to make it clearer?

I'm assuming that at the beginning all in-locations are unknown and only when all incoming basic blocks have outgoing locations, join() adds new incoming locations to be processed.

Ah, this is where the implementation diverges, in fact if all incoming blocks have the same outgoing location *or* unknown for a variable, join() will consider it a valid live-in location. I think it has to be this way because of loops -- for a location that is live throughout a loop, there's a circular dependency between the outgoing location for the back-edge and the live-in location for the loop header. Right now we assume the location is correct for any unknown blocks, and have to invalidate locations later if that doesn't turn out to be true. See for example D66599.

I guess this boils down to how we are not really modeling "unknown" currently?

It turns out to be even more exciting than that -- consider this IR [0] which has badly behaved, but completely legal control flow. It's illustrated in this highly sophisticated diagram [1]. A single variable location (toast==0) is created in the entry block, and then invalidated with an undef dbg.value in loop 3. Because every non-entry/non-exit block is reachable from every other block, the location-invalidation has to be propagated to them all. However, it takes at least one LiveDebugValues iteration for the invalidation to traverse a back-edge, so it takes two LiveDebugvalues iterations for the invalidation to move up the CFG and reach loop1. In that time, all the "unknown" blocks have been processed, and as a result locations have to transition from "true" to "false", rather than "unknown" to "false". It might be possible to generate a situation where something transitions from "false" to "true" too, but I haven't looked closely at that yet.

I think the fact that this is happening means I've made LiveDebugValues depart from peoples expectations, you wrote in the 2016 mailing list dicsussion [2]

the information at the nodes can only move in one direction in the lattice and can change at most once.

which isn't true any more because of D66599 removing locations. I suspect I've turned LiveDebugValues into a data-flow-like algorithm rather than a joining-lattices algorithm. Whether this is a good idea or not probably needs discussing; it's all been in aid of getting rid of invalid locations though.

[0] https://reviews.llvm.org/P8163
[1] https://imgur.com/a/YdE9kN7
[2] https://groups.google.com/forum/#!search/llvm-dev/llvm-dev/nlgxIfDQnhs/4zsGbuoTAAAJ

Thanks for the thoughtful explanation. I don't think this is good. I re-read D66599 and it sounds like it is also operating on the pre-D66663 premise that the first iteration is special to prime that values. That's really bad because it makes reasoning about the algorithm very hard (as evidenced by our conversation ;-) and also turns the algorithm from a bitvector problem to something much more expensive all the way to the point that I'm not even sure if it will always terminate. I think the reason why D66599 needs to remove values is because we implemented join() and the unknown value incorrectly.

Is there a fundamental reason why we couldn't model LiveDebugValues to monotonically move results up the lattice until a fixpoint is reached? Looking at your CFG in [1], if we (conceptually) initialized every VarLoc with unknown and implement join such that join(unknown, X) == unknown, we should get an initial set of out-locs for each basic block that is derived just from the info we have for sure *within* each basic block and gradually more info gets propagated until we may or may not have a join function that produces new in-locs for a basic block. My assumption is that new in-locs would never result in an out-loc flipping from true->false but only in one flipping from unknown->something.

Maybe this assumption is wrong, but if it isn't, we should try hard to get LiveDebugValues to behave that way.

jmorse added a subscriber: Orlando.Mon, Sep 16, 7:27 AM

Adrian wrote:

I don't think this is good.

Cool;

Is there a fundamental reason why we couldn't model LiveDebugValues to monotonically move results up the lattice until a fixpoint is reached? Looking at your CFG in [1], if we (conceptually) initialized every VarLoc with unknown and implement join such that join(unknown, X) == unknown, we should get an initial set of out-locs for each basic block that is derived just from the info we have for sure *within* each basic block and gradually more info gets propagated until we may or may not have a join function that produces new in-locs for a basic block. My assumption is that new in-locs would never result in an out-loc flipping from true->false but only in one flipping from unknown->something.

I think that idea works -- but it seems very close to the "Available Expressions" dataflow algorithm, which (I think) you're suggesting is too expensive, or at least undesirable right? Just to justify why I think they're similar: my understanding of available-expressions is that it initialises all possible expressions (here VarLocs) to true, then iteratively sets them to false as operands are killed (here clobbered), reaching a fixedpoint of expression availability (here variable locations) from their operand definitions (DBG_VALUEs or transfers) to kills (clobbers).

I think we would have difficulty with the fact that, even if we only implicitly made all locations "unknown" to begin with, we would still end up tracking a large number of "false" locations. Imagine the example in [0,1] were written in MIR, and that the entry variable-location were a register, which was clobbered in loop3 rather than being explicitly undef'd. There would be (AFAIUI) no way of telling that the register clobber in loop3 invalidated a variable location we cared about; we would have to track all register clobbers as "false" locations on the off-chance they clobbered a real variable location. (This would work though, be well defined, and will definitely complete).

I think the root cause is the circular dependency of locations in loops that I suggested above; we have to either

  • Speculatively consider a location true (until it's invalidated), which is what I've wound up doing, or
  • Collect the total set of invalidated locations

to break that loop.

~

I pointed @Orlando at this to see what he thought, he suggested that I've effectively downgraded "true" locations into being "explicitly unknown" or "maybe" locations that can later be found to be false; and that a true location is just a "maybe" location that never gets invalidated. I'm going to take a shot at proving that the current situation can't turn "false" locations true, which would make me feel better.

~

Alas, I'm also out of the office for the next two weeks so can't reply much further. I'll be at the conference though, in case this is best left on the backburner until then.