[llvm-dev] Adding Extended-SSA to LLVM

[Daniel Berlin via llvm-dev]

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>