[llvm-dev] Propagation of debug information for variable into basic blocks.

[Daniel Berlin via llvm-dev]

>
>
> Conceptually, the LiveDebugValues data flow analysis should be using
> three-valued logic arranged in a lattice
>
>     ⊥ (uninitialized / don't know)
>    / \
> true false (is (not) available)
>
> where join(x, ⊥) = x, otherwise it behaves like boolean &.
>
> All debug variable values are initialized to the bottom element first.
> After processing BB#0 we have var[b, reg23] = true. When we join this with
> the unknown ⊥ from BB#1, we propagate var[b, reg23] into BB#1. Next time we
> join at BB#2 we will have consistent information in both predecessors and
> the algorithm converges.



FWIW: GCC does this as a union, so you get the maximal info available. If
it's not available along a given path, it's simply not there for that path.
This will discard it if *any* path has missing info (not just inconsistent
info).

I'll skip whether this is or is not the right thing to do :)



> If, for example, BB#1 had conflicing information for b the next join at
> BB#2 would delete the information for b and the result would still be
> correct.
> This is guaranteed to terminate because the information at the nodes can
> only move in one direction in the lattice and can change at most once.
>
> I haven't thought this through entirely, but it looks like we could
> implement this by keeping track of which basic blocks we never visited
> before and special-casing previously unvisited basic blocks in join().
>

This is because you don't really init all the info to bottom for real. It
tries to be lazy.
Otherwise, they'd all have outlocs of bottom.
They are only theoretically initialized, so things get the wrong answer.

For example, this code is not right:


  // For all predecessors of this MBB, find the set of VarLocs that
  // can be joined.
  for (auto p : MBB.predecessors()) {
    auto OL = OutLocs.find(p);
    // Join is null in case of empty OutLocs from any of the pred.
    if (OL == OutLocs.end())
      return false;


This is wrong  if the block is unvisited (as you say)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160921/73ec80e2/attachment.html>