[llvm-dev] RFC: Representing unions in TBAA

[Hal Finkel via llvm-dev]

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>