<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span class="gmail-"><br>
</span>Conceptually, the LiveDebugValues data flow analysis should be using three-valued logic arranged in a lattice<br>
<br>
    ⊥ (uninitialized / don't know)<br>
   / \<br>
true false (is (not) available)<br>
<br>
where join(x, ⊥) = x, otherwise it behaves like boolean &.<br>
<br>
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. </blockquote><div><br></div><div><br></div><div>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.</div><div>This will discard it if *any* path has missing info (not just inconsistent info).</div><div><br></div><div>I'll skip whether this is or is not the right thing to do :)</div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">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.<br>
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.<br>
<br>
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().<br></blockquote><div><br></div><div>This is because you don't really init all the info to bottom for real. It tries to be lazy.</div><div>Otherwise, they'd all have outlocs of bottom.<br></div><div>They are only theoretically initialized, so things get the wrong answer.</div><div><br></div><div>For example, this code is not right:<br></div><div><br><div><div><br></div><div>  // For all predecessors of this MBB, find the set of VarLocs that</div><div>  // can be joined.</div><div>  for (auto p : MBB.predecessors()) {</div><div>    auto OL = OutLocs.find(p);</div><div>    // Join is null in case of empty OutLocs from any of the pred.</div><div>    if (OL == OutLocs.end())</div><div>      return false;</div></div></div><div><br></div><div><br></div><div>This is wrong  if the block is unvisited (as you say)<br></div><div><br></div><div><br></div><div><br></div></div></div></div>