<div dir="ltr">D29606 (a patch on top of the current patch set) handles all the critical edge and diamond cases you mentioned here.<div>It's a bit more complex to handle in one pass, so i did it as a patch set on top of the existing reviews so it can be reviewed separately.</div><div><br></div><div>I have not yet started to link together conjuctive/disjunctive info in a way clients know that it is conjunctive/disjunctive</div><div>(but that seems easy enough).</div><div><br></div><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Sun, Feb 5, 2017 at 4:26 PM, Daniel Berlin <span dir="ltr"><<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote"><span class="">On Sun, Feb 5, 2017 at 3:41 PM, Nuno Lopes <span dir="ltr"><<a href="mailto:nunoplopes@sapo.pt" target="_blank">nunoplopes@sapo.pt</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Thanks for the answers! The plan makes sense to me.<br>
<br>
Regarding phis, what about diamonds, e.g.:<br></blockquote><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
define i32 @f(i32 %x) {<br>
br .., label %bb0, label %bb1<br>
bb0:<br>
%cmp = icmp sge i32 %x, 0 ; x > 0<br>
br i1 %cmp, label %bb2, label %bb3<br>
bb1:<br>
%x2 = add nsw nuw %x, 1<br>
%cmp2 = icmp sge i32 %x2, 2 ; x+1 > 2 / x > 1<br>
br i1 %cmp2, label %bb2, label %bb3<br>
bb2:<br>
%x3 = phi i32 [ %x, %bb0 ], [ %x2, %bb1 ]<br>
; CVP says: %x3 is > 0<br>
...<br>
br label %bb3<br>
bb3:<br>
...<br>
}<br>
<br>
CVP can infer that %x > 0 because the union of the intervals given to the phi node imply that.<br>
Sure, we can split those edges, but maybe adding the predicate info to blocks bb0 & bb1 would solve the problem?<br></blockquote><div><br></div><div><br></div></span><div>Right, and these are all critical edges, as you say :)</div><div>I will actually try a trick where we insert the def twice and try to place them before phi node uses.<br></div><div>We sort phi node uses by incoming block, so they should end up next to each other.</div><span class=""><div><br></div><div> <br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
- In processBranch you also consider branches on ANDs/ORs of comparisons, and then each comparison is processed individually. However, this seems incorrect for one of the branches:<span><br>
if (a && b) {<br>
...<br>
} else {<br>
// holds: !a OR !b<br>
use(a)<br>
use(b)<br>
}<br>
<br>
Right now it seems that the information that is attached to the else branch is !a AND !b, which would be incorrect.<br>
</span></blockquote><span>
<br>
I could be pedantic and say the only information attached is a comparison, the branch, and whether the edge is the true edge or the false edge :)<br>
Which is correct.<br>
<br>
It also chains the info to give you the entire string of comparisons that were applied.<br>
<br>
However, in practice you are right, and clients are not likely to get this right with what i've given them.<br>
<br>
Since in practice, the only useful derived info is in the true branch of and, and the false branch of or, i'm going to make it not attach info to the other branch.<br>
<br>
Unless you can see a case it makes sense to?<br>
</span></blockquote>
<br>
For CVP there is. For example:<br>
if (x > 2 && x < 5) {<br>
...<br>
} else {<br>
// known: x <= 2 || x >= 5<br>
// CVP produces a range for x: [5, 3) (no loss of information here at all)<br>
if (x == 4) ... // CVP folds this to false<br>
}<br>
<br>
<br></blockquote><div><br></div></span><div>Okay, so it does try to handle simple disjunctions.</div><span class=""><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
So CVP can handle (simple) disjunctive information. Other ValueTracking analyses handle simple patterns as well, though probably at this time those can't use this new stuff unless we go all in with e-SSA.<br>
Not sure how to export the information to clients, though. Supporting arbitrary boolean combinations of comparisons seems tricky, but maybe sticking to just 1-level of and/or is ok.<br></blockquote><div><br></div><div><br></div></span><div>I mean, we can certainly mark and link the info however we want. I'm just not sure what the best way that clients want to use it is yet.</div><div><br></div><div>Let me think about this as a followup, since it at least is now "correct" to obvious clients</div><span class=""><div> <br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
I'm mentioning CVP because it *really* needs to be refactored to use e-SSA/SSI. The current code is slow, is very limited in scope (w/ somewhat arbitrary throttling), and is too complicated.<br></blockquote><div><br></div></span><div>Note that with patches to do LVI in DFS postorder instead of BFS order, it actually should be close to ideal :)</div><div><br></div><div>If CVP moves forward and queries LVI in RPO order, and LVI is doing PO, it should be as close to O(1) work per LVI call as you can get.</div><div><br></div><div>Of course, it's still a mess, code wise, but ...</div><div><br></div></div></div></div>
</blockquote></div><br></div>