[llvm-dev] Adding Extended-SSA to LLVM

[Daniel Berlin via llvm-dev]

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>