<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Dec 30, 2016 at 11:55 PM, Sanjoy Das <span dir="ltr"><<a href="mailto:sanjoy@playingwithpointers.com" target="_blank">sanjoy@playingwithpointers.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hi Daniel,<br>
<span class="gmail-"><br>
On Fri, Dec 30, 2016 at 10:55 PM, Daniel Berlin <<a href="mailto:dberlin@dberlin.org">dberlin@dberlin.org</a>> wrote:<br>
>> Right, but we are talking about "when, in the intermediate state, can i<br>
>> transform an undef to a different value".<br>
>><br>
>> Remember you can only go down the lattice. So you can't make undef<br>
>> constant, and then discover it's wrong, and go back up :)<br>
>> IE  can't change phi undef, undef to constant value 50, , discover 50<br>
>> doesn't work, and say, well actually, let's make it undef again for an<br>
>> iteration :)<br>
<br>
</span>If the kind of simplification (I think) you've mentioned is allowed,<br>
then I think even Davide's lattice is problematic.  Say we have:<br>
<br>
loop:<br>
  X = phi(entry: undef, loop: T)<br>
  ...<br>
  T = undef<br>
  if C then br loop else br outside<br>
<br>
When we first visit X then we'll compute its state as (Undef MEET<br>
Unknown) = Undef. </blockquote><div>Yes</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"> My guess is that you're implying that the Undef<br>
lattice state (or some other computation hanging off of it) can be<br>
folded immediately to, say, 50, but once we mark the backedge as<br>
executable we'll set it to undef (or mark it as 49)?</blockquote><div>Yes</div><div> <br></div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">  And both of<br>
these are bad because you're making a non-monotonic transition? </blockquote><div>Yes</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"> Given<br>
this, I'm not sure what prevents the bad transform from happening even<br>
if we have separate Unknown and Undef states.</blockquote><div><br></div><div>You can always get *out* of the bad transform by dropping to overdefined if you discover it doesn't work.</div><div>The question is more one of "what is the optimal time to  try to figure out a constant value that works".<br></div><div>If you drop too early, you have to go overdefined when you may have been able to figure out a constant to use to replace the undef.</div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"> </blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
If the solution is to not fold X into undef (which, by assumption, can<br>
"spontaneously decay" into any value) until you're sure every incoming<br>
value is also undef then I suppose we'll need some special handling<br>
for undef values to prevent breaking cases like (as shown earlier):<br>
<br>
loop:<br>
  X = phi(entry: 10, loop: T)<br>
  if X == 10 then br outside else br loop<br>
<br>
=><br>
<br>
loop:<br>
  X = phi(entry: 10, loop: T)<br>
  br outside<br>
<br>
(i.e. to keep the algorithm properly optimistic)?<br></blockquote><div><br></div><div>Right.  This is precisely the unknown part, or at least, that was my thinking.</div><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
And if we do have a way of keeping undefs as undefs (i.e. prevent X<br>
from decaying into 50 when we first visit the first loop) then why<br>
can't we re-use the same mechanism to avoid spuriously decaying "phi<br>
undef undef-but-actually-unknown" to "50"?<br></blockquote><div>That mechanism is the "all executable paths leading to our operands visited" bit, which is .. the unknown vs undef state.</div><div><br>IE we only mark the operand undef when we visit it from a reachable edge.</div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><br>
Another way of stating my suggestion is that, if you agree that this<br>
is a correct lattice (different from Davide's proposal) and pretend<br>
the "spontaneous undef decay" problem does not exist, then:<br>
<span class="gmail-"><br>
digraph G {<br>
  Unknown -> Undef<br>
  Undef -> Constant1<br>
  Undef -> Constant2<br>
  Undef -> Constant3<br>
  Constant1 -> Bottom<br>
  Constant2 -> Bottom<br>
  Constant3-> Bottom<br>
}<br>
<br>
</span>then it should be legal / correct to first drop every lattice element<br>
from "Unknown" to "Undef" before running the algorithm.  The only<br>
cases where this would give us a conservative result is a place where<br>
we'd have otherwise gotten "Unknown" for a used value; and the<br>
algorithm should never have terminated in such a state.<br></blockquote><div><br></div><div>It is definitely *legal* to do this or the algorithm is broken otherwise (you should just end up in overdefined more).</div><div><br></div><div>I'm not sure i believe the last part though.  I have to think about it.</div><div><br></div><div><br></div><div>FWIW: My initial proposal to all of this was "stop caring about trying to optimize undef here at all". Remove it from the lattice, and treat undef as overdefined if we see it. If we want to optimize undef, before SCCP solving, build SCCs of the parts of the SSA graph that contain undef, choose correct values for those subgraphs, then mark them constant *before* the solver sees it". </div><div><br></div><div> This is pre-solve instead of post-solve or iterative solve. We already do this for arguments by solving them to overdefined. IPCP also works much the same way by pre-solving arguments constants</div><div><br></div><div>This is precisely because this stuff is non-trivial to reason about, and unclear to me that it's really worth it.  If *it* is worth it, we can do better than we do now (and contain the mess *entirely* to the presolver), and if it's not, we shouldn't have complicated reasoning to try to make it work well.</div><div><br></div><div>Right now we have the worst of all worlds.  We have a mess in both places (the resolver and the solver both step on each other and differ in behavior), it's hard to reason about (though provably not correct), and it doesn't even give you the best answers it can *anyway*</div><div><br></div><div>(generally, at the point where we have a bunch of very smart people racking their heads about whether something is really going to work algorithmically or not, i take it as a sign that maybe we have the wrong path.  Obviously, there are some really complex problems, but ... this should not be one of them :P)</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">
<span class="gmail-HOEnZb"><font color="#888888"><br>
-- Sanjoy<br>
</font></span></blockquote></div><br></div></div>