[llvm-dev] RFC: Stop using redundant PHI node entries for multi-edge predecessors

[Chandler Carruth via llvm-dev]

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>