<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Dec 30, 2016 at 10:01 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:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi Daniel,<br>
<span class=""><br>
On Fri, Dec 30, 2016 at 9:47 PM, Daniel Berlin <<a href="mailto:dberlin@dberlin.org">dberlin@dberlin.org</a>> wrote:<br>
>><br>
>>>   Is there a case in your algorithm in which treating an<br>
>>> unknown as an undef will be a problem?<br>
>>><br>
</span><span class="">> Yes, if you try to optimize undefs in any way, no if you move them to<br>
> overdefined :)<br>
><br>
> IE given phi [a, undef, undef, undef]<br>
><br>
> with just as many back edges, you will visit this node 4 times.<br>
><br>
> If you start out with<br>
><br>
> phi [a, undef, undef, undef], you may think "I know, i will make  these<br>
> undef's a".<br>
><br>
> So you move everything to value<br>
><br>
> phi [a, a, a, a]<br>
><br>
> But remember, you really haven't visited the other 4 edges yet, so you don't<br>
> know if this is a valid value for undef (because of the rules around<br>
> and/or/etc, see <a href="http://llvm.org/docs/LangRef.html#undefined-values" rel="noreferrer" target="_blank">http://llvm.org/docs/LangRef.<wbr>html#undefined-values</a>).<br>
<br>
</span>But that's the same as case as:<br>
<br>
  %x = phi [a, <unknown>]<br>
<br></blockquote><div> <br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Unless I know for sure that <unknown> is a, the *final result* can't<br>
report the phi as a. </blockquote><div>Right, but we are talking about "when, in the intermediate state, can i transform an undef to a different value".</div><div><br>Remember you can only go down the lattice. So you can't make undef constant, and then discover it's wrong, and go back up :)</div><div>IE  can't change phi undef, undef to constant value 50, , discover 50 doesn't work, and say, well actually, let's make it undef again for an iteration :)</div><div><br></div><div>So you need to know the point, *in the intermediate state*, when it is safe to change the undefs.</div><div>That point is when all unknowns disappear because you have completed visiting the entire CFG..</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
However, the I thought the algorithm we're talking about here is<br>
optimistic, and we will initially fold %x to `a`, and then "try to<br>
see" if other edges are viable or not.  You're allowed to incorrectly<br>
optimistic results in the midst of the algorithm run (by design).<br></blockquote><div><br></div><div>Yes, but, again, you still can't shove things back up the lattice :)</div><div><br></div><div>Maybe this will help:<br>In the past, the resolver forced things to be constant.  This is shoving them down the lattice too far.  There was, as i said no way to push them back up the lattice when they turned out wrong (and this  happened often due to the iteration order differences).  </div><div>If you want to do the stuff the resolver did, but do it at the right time, you need the bit to tell you when you *can* shove them down to a constant.</div><div><br></div><div>You can store that bit however you want. You can store a bit that all operands of an operation were visited at least once.</div><div>That is equivalent to "all operands != unknown".</div><div>But you can't dual purpose the bit with undef, because undef is an actual value state. it tells you nothing about visited or unvisited, only the value.</div><div><br></div><div><br></div></div></div></div>