<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Fri, Mar 21, 2014 at 4:45 PM, Shankar Easwaran <span dir="ltr"><<a href="mailto:shankare@codeaurora.org" target="_blank">shankare@codeaurora.org</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div text="#000000" bgcolor="#FFFFFF">
<div>Hi Rui,<br>
<br>
How would dead stripping know what atom comes before what other
atom ? I think it may be better to use in-group reference as it
simplified a lot for ELF.<br></div></div></blockquote><div><br></div><div>As I described, the dead stripping pass can create layout-after edges from layout-before edges by reversing the graph, just as we can do to any directed graph using a simple graph algorithm.</div>
<div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div text="#000000" bgcolor="#FFFFFF"><div>
Thanks<span class="HOEnZb"><font color="#888888"><br>
<br>
Shankar Easwaran</font></span><div><div class="h5"><br>
<br>
On 3/21/2014 6:38 PM, Rui Ueyama wrote:<br>
</div></div></div><div><div class="h5">
<blockquote type="cite">
<div dir="ltr">
<div class="gmail_extra">Thank you for quick responses!</div>
<div class="gmail_extra"><br>
</div>
<div class="gmail_extra">As to dead stripping, if dead stripping
is the only pass we need bi-directional edges, we might want
the dead stripping pass to construct internal data structure
by reversing the graph to construct layout-before edges from
layout-after edges. This should be less error prone than
maintaining two reverse-directional edges throughout all
passes. Of course it will make time for dead stripping
proportional to the number of all atoms, rather than live
ones. It looks traversing graph is surprisingly cheep so I
guess it wouldn't matter, but it needs investigation.</div>
<div class="gmail_extra"><br>
</div>
<div class="gmail_extra">It's interesting that ELF no longer
uses layout-before's. I agree that that would be simpler than
using both layout-after and layout-before.</div>
<div class="gmail_extra">
<br>
</div>
<div class="gmail_extra">I'll try to modify the dead-stripping
pass as I described above. Any concerns?</div>
<div class="gmail_extra"><br>
<div class="gmail_quote">On Fri, Mar 21, 2014 at 4:10 PM,
Shankar Easwaran <span dir="ltr"><<a href="mailto:shankare@codeaurora.org" target="_blank">shankare@codeaurora.org</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div text="#000000" bgcolor="#FFFFFF">
<div>Hi Rui,<br>
<br>
ELF uses layout-after and in-group references now. It
no longer uses layout-before.<br>
<br>
The reason that two references are used are to make
sure garbage collection treats the whole group of
atoms together when it wants to Garbage collect an
atom.<br>
<br>
Thanks<br>
<br>
Shankar Easwaran
<div>
<div><br>
<br>
On 3/21/2014 5:45 PM, Rui Ueyama wrote:<br>
</div>
</div>
</div>
<div>
<div>
<blockquote type="cite">
<div dir="ltr">
<div class="gmail_extra">+llvmdev<br>
<br>
<div class="gmail_quote">On Fri, Mar 21, 2014
at 3:43 PM, Rui Ueyama <span dir="ltr"><<a href="mailto:ruiu@google.com" target="_blank">ruiu@google.com</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr">Hi all,
<div><br>
</div>
<div>I'm trying to debug an issue that
LLD sometimes get into an infinite
loop in setChainRoot() in
LayoutPass.cpp. It looks like the
cause is either buildPrecededByTable()
handles layoutBefore edges in a wrong
way or we construct a contradictory
layout-before/layout-after graph.</div>
<div><br>
</div>
<div>At this point I started thinking
that I'm wasting time on data
structure that's more complicated than
it needs to be. LayoutPass.cpp is I
think the most complicated piece of
code in our code base and is also hard
to debug. If we can simplify it we
totally should do.</div>
<div><br>
</div>
<div>So, I'm planning to remove one of
layout-before or layout-after edges
from the graph. Currently, in LLD, if
node X has an outgoing layout-before
edge to Y, Y always has an outgoing
layout-after edge to X. In other words
it's doubly-linked. Doubly-linked edge
is useful if you need bi-directional
access, however, we don't need it in
LayoutPass. We only need one of two.</div>
<div><br>
</div>
<div>Removing one of
layout-before/layout-after edges has
three benefits:</div>
<div><br>
</div>
<div> 1. Reduces memory usage and
runtime overhead</div>
<div> 2. Simpler code and algorithm</div>
<div> 3. No need to maintain consistency
between layout-before/layout-after
edges, which is often a cause of nasty
bugs.</div>
<div><br>
</div>
<div>Does this sound good?</div>
</div>
</blockquote>
</div>
<br>
</div>
</div>
</blockquote>
<br>
<br>
</div>
</div>
<span><font color="#888888">
<pre cols="72">--
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by the Linux Foundation</pre>
</font></span></div>
</blockquote>
</div>
<br>
</div>
</div>
</blockquote>
<br>
<br>
<pre cols="72">--
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by the Linux Foundation</pre>
</div></div></div>
</blockquote></div><br></div></div>