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

[Adrian Prantl via llvm-dev]

> On Sep 21, 2016, at 2:23 PM, Daniel Berlin <dberlin at dberlin.org> wrote:
> 
> 
> 
>   // 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)
> 
> This is actually non-trivial to fix, IMHO.
> 
> For example, the following looks kinda right:
>   
> for (auto p : MBB.predecessors()) {
>     if (p is not visited)
>      continue;
>     auto OL = OutLocs.find(p);
>     // Join is null in case of empty OutLocs from any of the pred.
>     if (OL == OutLocs.end())
>       return false;
> 
> (and will work in a lot of cases)
> 
> This can be wrong, however, if you have more than a single backedge in the program.
> (it may be possible to have a block that has multiple uninited predecessors that will require multiple iterations to resolve)
> 
> The problem here is that to get the maximal answer in an intersection problem, you *must* initialize the sets to contain every value.  You can look at dataflow algorithm papers for formal proofs if you want.
> 
> So you *actually* have to treat the default state of every unvisited block as the equivalent of "containing every value" to get the maximal answer.
> 
> How to achieve this for real is ... not obvious at a glance.
> 

I had to construct an example to see the problem, but my example is bit contrived (it depends on starting in the middle of the graph) so I wonder if there is a better counterexample.

BB0:y   BB1:x,y
 |        |
BB2:⊥  BB3:⊥  BB4:⊥
 |    /   |    /
BB5:x     |   /  
      \   |  /
        BB6: ?
         |
         +-> back-edge to BB1, BB4

BB5 has a definition for x but neither kills nor defines y. No block ever kills y. Let's assume we for whatever reason started in BB5. The first join() at BB6 will yield the set [x] (BB3 and BB4 are unvisited and thus skipped, just as if they contained every value). This causes BB2 and BB4 to be added to the working set. If we now visit BB4 first, it will see only [x] and it will be impossible for y be propagated to BB6.

Is there a better example?

-- adrian