<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<p><br>
</p>
<div class="moz-cite-prefix">On 05/14/2017 09:00 PM, Daniel Berlin
wrote:<br>
</div>
<blockquote
cite="mid:CAF4BwTWQr1BTAWuX+EAPY1apSGGsMOOdfLZaJixTuu31Uc3WNw@mail.gmail.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<blockquote class="gmail_quote" style="margin:0px 0px 0px
0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex">
<div bgcolor="#FFFFFF">
<div>
<div class="gmail-h5"><br>
</div>
</div>
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:<span
class="gmail-"><br>
<br>
</span></div>
</blockquote>
<div><br>
</div>
<div>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.</div>
</div>
</div>
</div>
</blockquote>
<br>
Fair point. I suppose I was saying something stronger...<br>
<br>
<blockquote
cite="mid:CAF4BwTWQr1BTAWuX+EAPY1apSGGsMOOdfLZaJixTuu31Uc3WNw@mail.gmail.com"
type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div> </div>
<div>Your below is basically "one is drawn in one direction,
and the other is drawn the other".</div>
<div>This is entirely true.</div>
<div><br>
</div>
<div>You want to argue that this means they will be exactly
as efficient or easy to understand as each other.</div>
<div>This is where you and I disagree.</div>
<div>I disagree because i rarely see parent-linked graph
structures (outside of union-find ) that are implemented
or used well</div>
</div>
</div>
</div>
</blockquote>
<br>
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.<br>
<br>
Maybe an example will help, you said:<br>
<br>
<blockquote type="cite">
<div>Given</div>
<div>union {int a, short b};</div>
<div><br>
</div>
<div>GCC's will be:</div>
<div><br>
</div>
<div> union</div>
<div> / \</div>
<div>short int</div>
<div><br>
</div>
<div><br>
</div>
<div>Everything is implicitly a subset of alias set 0 (which for
C/C++ is char) just to avoid representing it.</div>
</blockquote>
<br>
Let's expand this, and also explicitly represent char, does the
graph look like in the GCC-like scheme?<br>
<br>
union1 {int a; short b;};<br>
union2 {int a; float f;};<br>
<br>
union1 union2<br>
/ \ / \<br>
short int int float<br>
\ | | /<br>
\ | | /<br>
( char )<br>
<br>
Thanks again,<br>
Hal<br>
<br>
<blockquote
cite="mid:CAF4BwTWQr1BTAWuX+EAPY1apSGGsMOOdfLZaJixTuu31Uc3WNw@mail.gmail.com"
type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div>People often screw up the algorithms, they tend to be
harder to reason about, etc.</div>
<div>
<div>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).</div>
</div>
<div><br>
</div>
<div>Past that I'm not sure what you want me to say here. </div>
<div>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?<br>
</div>
</div>
</div>
</div>
</blockquote>
<br>
<pre class="moz-signature" cols="72">--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre>
</body>
</html>