[llvm-dev] Adding Extended-SSA to LLVM

[Nuno Lopes via llvm-dev]

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 ...