On Sun, Feb 5, 2017 at 3:41 PM, Nuno Lopes <nunoplopes at sapo.pt> wrote:> Thanks for the answers! The plan makes sense to me. > > Regarding phis, what about diamonds, e.g.: >> > define i32 @f(i32 %x) { > br .., label %bb0, label %bb1 > bb0: > %cmp = icmp sge i32 %x, 0 ; x > 0 > br i1 %cmp, label %bb2, label %bb3 > bb1: > %x2 = add nsw nuw %x, 1 > %cmp2 = icmp sge i32 %x2, 2 ; x+1 > 2 / x > 1 > br i1 %cmp2, label %bb2, label %bb3 > bb2: > %x3 = phi i32 [ %x, %bb0 ], [ %x2, %bb1 ] > ; CVP says: %x3 is > 0 > ... > br label %bb3 > bb3: > ... > } > > CVP can infer that %x > 0 because the union of the intervals given to the > phi node imply that. > Sure, we can split those edges, but maybe adding the predicate info to > blocks bb0 & bb1 would solve the problem? >Right, and these are all critical edges, as you say :) I will actually try a trick where we insert the def twice and try to place them before phi node uses. We sort phi node uses by incoming block, so they should end up next to each other.> > > - 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: >>> if (a && b) { >>> ... >>> } else { >>> // holds: !a OR !b >>> use(a) >>> use(b) >>> } >>> >>> Right now it seems that the information that is attached to the else >>> branch is !a AND !b, which would be incorrect. >>> >> >> 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 :) >> Which is correct. >> >> It also chains the info to give you the entire string of comparisons that >> were applied. >> >> However, in practice you are right, and clients are not likely to get >> this right with what i've given them. >> >> 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. >> >> Unless you can see a case it makes sense to? >> > > For CVP there is. For example: > if (x > 2 && x < 5) { > ... > } else { > // known: x <= 2 || x >= 5 > // CVP produces a range for x: [5, 3) (no loss of information here at > all) > if (x == 4) ... // CVP folds this to false > } > > >Okay, so it does try to handle simple disjunctions.> 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. > 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. >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. Let me think about this as a followup, since it at least is now "correct" to obvious clients> > 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. >Note that with patches to do LVI in DFS postorder instead of BFS order, it actually should be close to ideal :) 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. Of course, it's still a mess, code wise, but ... -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170205/3fac8406/attachment.html>
D29606 (a patch on top of the current patch set) handles all the critical edge and diamond cases you mentioned here. 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. I have not yet started to link together conjuctive/disjunctive info in a way clients know that it is conjunctive/disjunctive (but that seems easy enough). On Sun, Feb 5, 2017 at 4:26 PM, Daniel Berlin <dberlin at dberlin.org> wrote:> > > On Sun, Feb 5, 2017 at 3:41 PM, Nuno Lopes <nunoplopes at sapo.pt> wrote: > >> Thanks for the answers! The plan makes sense to me. >> >> Regarding phis, what about diamonds, e.g.: >> > > > >> >> define i32 @f(i32 %x) { >> br .., label %bb0, label %bb1 >> bb0: >> %cmp = icmp sge i32 %x, 0 ; x > 0 >> br i1 %cmp, label %bb2, label %bb3 >> bb1: >> %x2 = add nsw nuw %x, 1 >> %cmp2 = icmp sge i32 %x2, 2 ; x+1 > 2 / x > 1 >> br i1 %cmp2, label %bb2, label %bb3 >> bb2: >> %x3 = phi i32 [ %x, %bb0 ], [ %x2, %bb1 ] >> ; CVP says: %x3 is > 0 >> ... >> br label %bb3 >> bb3: >> ... >> } >> >> CVP can infer that %x > 0 because the union of the intervals given to the >> phi node imply that. >> Sure, we can split those edges, but maybe adding the predicate info to >> blocks bb0 & bb1 would solve the problem? >> > > > Right, and these are all critical edges, as you say :) > I will actually try a trick where we insert the def twice and try to place > them before phi node uses. > We sort phi node uses by incoming block, so they should end up next to > each other. > > > >> >> >> - 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: >>>> if (a && b) { >>>> ... >>>> } else { >>>> // holds: !a OR !b >>>> use(a) >>>> use(b) >>>> } >>>> >>>> Right now it seems that the information that is attached to the else >>>> branch is !a AND !b, which would be incorrect. >>>> >>> >>> 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 :) >>> Which is correct. >>> >>> It also chains the info to give you the entire string of comparisons >>> that were applied. >>> >>> However, in practice you are right, and clients are not likely to get >>> this right with what i've given them. >>> >>> 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. >>> >>> Unless you can see a case it makes sense to? >>> >> >> For CVP there is. For example: >> if (x > 2 && x < 5) { >> ... >> } else { >> // known: x <= 2 || x >= 5 >> // CVP produces a range for x: [5, 3) (no loss of information here at >> all) >> if (x == 4) ... // CVP folds this to false >> } >> >> >> > Okay, so it does try to handle simple disjunctions. > > >> 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. >> 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. >> > > > 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. > > Let me think about this as a followup, since it at least is now "correct" > to obvious clients > > >> >> 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. >> > > Note that with patches to do LVI in DFS postorder instead of BFS order, it > actually should be close to ideal :) > > 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. > > Of course, it's still a mess, code wise, but ... > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170206/818570dd/attachment.html>
Cool, thanks!
I just read the tests and they look good. I'll review the algorithm changes
in the next few days, but feel free to commit the patch in the meantime.
Nuno
-----Original Message-----
From: Daniel Berlin
Sent: Monday, February 6, 2017 9:49 PM
To: Nuno Lopes
Cc: llvm-dev ; Chandler Carruth
Subject: Re: [llvm-dev] Adding Extended-SSA to LLVM
D29606 (a patch on top of the current patch set) handles all the critical
edge and diamond cases you mentioned here.
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.
I have not yet started to link together conjuctive/disjunctive info in a way
clients know that it is conjunctive/disjunctive
(but that seems easy enough).
On Sun, Feb 5, 2017 at 4:26 PM, Daniel Berlin <dberlin at dberlin.org>
wrote:
On Sun, Feb 5, 2017 at 3:41 PM, Nuno Lopes <nunoplopes at sapo.pt> wrote:
Thanks for the answers! The plan makes sense to me.
Regarding phis, what about diamonds, e.g.:
define i32 @f(i32 %x) {
br .., label %bb0, label %bb1
bb0:
%cmp = icmp sge i32 %x, 0 ; x > 0
br i1 %cmp, label %bb2, label %bb3
bb1:
%x2 = add nsw nuw %x, 1
%cmp2 = icmp sge i32 %x2, 2 ; x+1 > 2 / x > 1
br i1 %cmp2, label %bb2, label %bb3
bb2:
%x3 = phi i32 [ %x, %bb0 ], [ %x2, %bb1 ]
; CVP says: %x3 is > 0
...
br label %bb3
bb3:
...
}
CVP can infer that %x > 0 because the union of the intervals given to the
phi node imply that.
Sure, we can split those edges, but maybe adding the predicate info to
blocks bb0 & bb1 would solve the problem?
Right, and these are all critical edges, as you say :)
I will actually try a trick where we insert the def twice and try to place
them before phi node uses.
We sort phi node uses by incoming block, so they should end up next to each
other.
- 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:
if (a && b) {
...
} else {
// holds: !a OR !b
use(a)
use(b)
}
Right now it seems that the information that is attached to the else branch
is !a AND !b, which would be incorrect.
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 :)
Which is correct.
It also chains the info to give you the entire string of comparisons that
were applied.
However, in practice you are right, and clients are not likely to get this
right with what i've given them.
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.
Unless you can see a case it makes sense to?
For CVP there is. For example:
if (x > 2 && x < 5) {
...
} else {
// known: x <= 2 || x >= 5
// CVP produces a range for x: [5, 3) (no loss of information here at all)
if (x == 4) ... // CVP folds this to false
}
Okay, so it does try to handle simple disjunctions.
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.
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.
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.
Let me think about this as a followup, since it at least is now
"correct" to
obvious clients
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.
Note that with patches to do LVI in DFS postorder instead of BFS order, it
actually should be close to ideal :)
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.
Of course, it's still a mess, code wise, but ...