llvm dev - May 2017 - RFC: Representing unions in TBAA

>
>
> I don't agree, but this is because I fail to see how the two
> representations (the GCC-like one you've outlined and the current one
with
> the proposed extension) aren't completely isomorphic. Your proposal is:
>
>
Lots of data structures are completely isomorphic in the same way,  and in
plenty of those cases, one is completely unusable, and the other functions
quite well.

Your below is basically "one is drawn in one direction, and the other is
drawn the other".
This is entirely true.

You want to argue that this means they will be exactly as efficient or easy
to understand as each other.
This is where you and I disagree.
I disagree because i rarely see parent-linked graph structures (outside of
union-find ) that are implemented or used well.
People often screw up the algorithms, they tend to be harder to reason
about, etc.
This is why, for example, despite having both parent and child links,
roughly all of our dominator tree graph algorithms walk children instead of
parents, even though you could equivalently do them using only the parent
links (even the depth first algorithms).

Past that I'm not sure what you want me to say here.
If y'all come up with an implementation that works as well as the ones
i'm
familiar with, i'll be as happy as anyone else?
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170514/4083c368/attachment.html>

On 05/14/2017 09:00 PM, Daniel Berlin wrote:
>
>
>     I don't agree, but this is because I fail to see how the two
>     representations (the GCC-like one you've outlined and the current
>     one with the proposed extension) aren't completely isomorphic.
>     Your proposal is:
>
>
> Lots of data structures are completely isomorphic in the same way, 
>  and in plenty of those cases, one is completely unusable, and the 
> other functions quite well.
Fair point. I suppose I was saying something stronger...
> Your below is basically "one is drawn in one direction, and the other 
> is drawn the other".
> This is entirely true.
>
> You want to argue that this means they will be exactly as efficient or 
> easy to understand as each other.
> This is where you and I disagree.
> I disagree because i rarely see parent-linked graph structures 
> (outside of union-find ) that are implemented or used well
I don't think that we're on the same page here. AFAIKT, in both schemes,
the links go in the same direction: from struct nodes to member-type 
nodes. We call these parent links in our scheme and you call them child 
links in your scheme, but the sense in the DAG is the same.

Maybe an example will help, you said:
> Given
> union {int a, short b};
>
> GCC's will be:
>
>  union
>   /   \
> short int
>
>
> Everything is implicitly a subset of alias set 0 (which for C/C++ is 
> char) just to avoid representing it.
Let's expand this, and also explicitly represent char, does the graph 
look like in the GCC-like scheme?

union1 {int a; short b;};
union2 {int a; float f;};

  union1          union2
    /      \            /     \
short  int      int float
    \        |         |       /
     \       |         |      /
      (         char      )

Thanks again,
Hal
> People often screw up the algorithms, they tend to be harder to reason 
> about, etc.
> This is why, for example, despite having both parent and child links, 
> roughly all of our dominator tree graph algorithms walk children 
> instead of parents, even though you could equivalently do them using 
> only the parent links (even the depth first algorithms).
>
> Past that I'm not sure what you want me to say here.
> If y'all come up with an implementation that works as well as the ones 
> i'm familiar with, i'll be as happy as anyone else?
-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170515/6a83889f/attachment.html>

On Mon, May 15, 2017 at 8:29 AM, Hal Finkel <hfinkel at anl.gov> wrote:
>
> On 05/14/2017 09:00 PM, Daniel Berlin wrote:
>
>
>> I don't agree, but this is because I fail to see how the two
>> representations (the GCC-like one you've outlined and the current
one with
>> the proposed extension) aren't completely isomorphic. Your proposal
is:
>>
>>
> Lots of data structures are completely isomorphic in the same way,  and in
> plenty of those cases, one is completely unusable, and the other functions
> quite well.
>
>
> Fair point. I suppose I was saying something stronger...
>
>
> Your below is basically "one is drawn in one direction, and the other
is
> drawn the other".
> This is entirely true.
>
> You want to argue that this means they will be exactly as efficient or
> easy to understand as each other.
> This is where you and I disagree.
> I disagree because i rarely see parent-linked graph structures (outside of
> union-find ) that are implemented or used well
>
>
> I don't think that we're on the same page here. AFAIKT, in both
schemes,
> the links go in the same direction:
>



> from struct nodes to member-type nodes. We call these parent links in our
> scheme and you call them child links in your scheme, but the sense in the
> DAG is the same.
>
Except not because of what you've chosen explicitly as the root :)

we have

 root (char)
 /   \
int  short
|      /
struct A


gcc has


<forest>
struct A
 /       \
int    short

(note the lack of char here too)

So you would be right if it wasn't rooted.
But we've explicitly chosen to make it rooted in what GCC would consider a
leaf:)

It is true you can rewrite one into the other, but ...
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170515/c290cdae/attachment.html>