llvm dev - May 2017 - RFC: Stop using redundant PHI node entries for multi-edge predecessors

Today, the IR requires that if you have multiple edges from A to B
(typically with a switch) any phi nodes in B must have an equal number of
entries for A, but that all of them must have the same value.

This seems rather annoying....
1) It creates multiple uses of values in A for no apparently good reason
2) It makes updating PHI nodes using sets of predecessors incredibly hard
3) There is no correspondence between the edges and the PHI node entries
other than number, making most of the code that does handle this very
ad-hoc "count off N repetitions of the same thing" style code, which
is
brittle and hard to test effectively.
4) I suspect bugs are quite common given that PHINode::removeIncomingValue
accepts a basic block but only removes the first incoming value, leaving
the others in place.

I can't see any serious use case for this symmetry either. These aren't
uses (and can't be), and there doesn't seem to be any lost functionality
if
we only have a single entry.

It also seems likely to open up more efficient in-memory representations if
it is possible at some point to build maps of these things.

Thoughts? It appears entirely possible to change the verifier to check that
we don't have duplicates, and to read bitcode with duplicates and merge
them so that there is no backwards compatibility issue.

-Chandler
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170501/e2213821/attachment.html>

On Mon, May 1, 2017 at 3:48 AM, Chandler Carruth via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Today, the IR requires that if you have multiple edges from A to B
> (typically with a switch) any phi nodes in B must have an equal number of
> entries for A, but that all of them must have the same value.
>
>
> This seems rather annoying....
> 1) It creates multiple uses of values in A for no apparently good reason
> 2) It makes updating PHI nodes using sets of predecessors incredibly hard
> 3) There is no correspondence between the edges and the PHI node entries
> other than number, making most of the code that does handle this very
> ad-hoc "count off N repetitions of the same thing" style code,
which is
> brittle and hard to test effectively.
>
Having written this code a few times, i'd agree.

> 4) I suspect bugs are quite common given that PHINode::removeIncomingValue
> accepts a basic block but only removes the first incoming value, leaving
> the others in place.
>

>
> I can't see any serious use case for this symmetry either. These
aren't
> uses (and can't be), and there doesn't seem to be any lost
functionality if
> we only have a single entry.http://lists.llvm.org/cgi-bin/
> mailman/listinfo/llvm-dev
>
> It also seems likely to open up more efficient in-memory representations
> if it is possible at some point to build maps of these things.
>
> Thoughts?
>

So would this lead to a case where PHI->getNumOperands()
!std::distance(pred_begin(phiblock), pred_end(phiblock))

If so, that would seem problematic to handle as well.
:(



> It appears entirely possible to change the verifier to check that we
don't
> have duplicates, and to read bitcode with duplicates and merge them so that
> there is no backwards compatibility issue.
>
> -Chandler
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170501/63052192/attachment.html>

Hi,

On Mon, May 1, 2017 at 8:47 AM, Daniel Berlin via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
>> Today, the IR requires that if you have multiple edges from A to B
>> (typically with a switch) any phi nodes in B must have an equal number
of
>> entries for A, but that all of them must have the same value.
>
>> This seems rather annoying....
>> 1) It creates multiple uses of values in A for no apparently good
reason
>> 2) It makes updating PHI nodes using sets of predecessors incredibly
hard
>> 3) There is no correspondence between the edges and the PHI node
entries
>> other than number, making most of the code that does handle this very
ad-hoc
>> "count off N repetitions of the same thing" style code, which
is brittle and
>> hard to test effectively.
>
> Having written this code a few times, i'd agree.
>
>>
>> 4) I suspect bugs are quite common given that
PHINode::removeIncomingValue
>> accepts a basic block but only removes the first incoming value,
leaving the
>> others in place.
>
>> I can't see any serious use case for this symmetry either. These
aren't
>> uses (and can't be), and there doesn't seem to be any lost
functionality if
>> we only have a single
>> entry.http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>> It also seems likely to open up more efficient in-memory
representations
>> if it is possible at some point to build maps of these things.
>>
>> Thoughts?
>
>
>
> So would this lead to a case where PHI->getNumOperands() !>
std::distance(pred_begin(phiblock), pred_end(phiblock))
>
> If so, that would seem problematic to handle as well.
> :(
Also, IIUC, today deleting an edge from A to B only requires
removeIncomingValue(A) on B's PHI nodes, but after this change you'll
have to check if you're deleting the last edge or not.

Can (2), (3) and (4) be fixed by changing the API instead of the
deeper IR change you're proposing?

-- Sanjoy

On Mon, May 1, 2017 at 8:47 AM Daniel Berlin via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> On Mon, May 1, 2017 at 3:48 AM, Chandler Carruth via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
>> Today, the IR requires that if you have multiple edges from A to B
>> (typically with a switch) any phi nodes in B must have an equal number
of
>> entries for A, but that all of them must have the same value.
>>
>
>
>>
>> This seems rather annoying....
>> 1) It creates multiple uses of values in A for no apparently good
reason
>> 2) It makes updating PHI nodes using sets of predecessors incredibly
hard
>> 3) There is no correspondence between the edges and the PHI node
entries
>> other than number, making most of the code that does handle this very
>> ad-hoc "count off N repetitions of the same thing" style
code, which is
>> brittle and hard to test effectively.
>>
>
> Having written this code a few times, i'd agree.
>
>
>> 4) I suspect bugs are quite common given that
>> PHINode::removeIncomingValue accepts a basic block but only removes the
>> first incoming value, leaving the others in place.
>>
>
>
>
>>
>> I can't see any serious use case for this symmetry either. These
aren't
>> uses (and can't be), and there doesn't seem to be any lost
functionality if
>> we only have a single entry.
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>
>> It also seems likely to open up more efficient in-memory
representations
>> if it is possible at some point to build maps of these things.
>>
>> Thoughts?
>>
>
>
> So would this lead to a case where PHI->getNumOperands() !>
std::distance(pred_begin(phiblock), pred_end(phiblock))
>
> If so, that would seem problematic to handle as well.
> :(
>
How problematic?

The places I've looked at that cared had to build a data structure anyways
(the verifier builds two vectors and sorts them). Having them build sets
wouldn't seem problematic.

But I've only looked at a couple of places, which is somewhat the point of
this email -- I'd like to know if we're doing this for good reasons, and
ideally understand those reasons.

>
>
>
>
>> It appears entirely possible to change the verifier to check that we
>> don't have duplicates, and to read bitcode with duplicates and
merge them
>> so that there is no backwards compatibility issue.
>>
>> -Chandler
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170501/4fe6e122/attachment.html>