<html><head><meta http-equiv="Content-Type" content="text/html charset=windows-1252"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"><br><div><div>On Mar 21, 2014, at 3:45 PM, Rui Ueyama <<a href="mailto:ruiu@google.com">ruiu@google.com</a>> wrote:</div><br class="Apple-interchange-newline"><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></div></div></blockquote></div><br><div>If you only have layout-after, it will run into problems with dead code stripping. (Ex, say A has a layout-after to B and only B is referenced by anything else. Since A is now unreferenced, it can get dead code stripped).</div><div><br></div><div>If you only have layout-before, the actual layout is hard because you don’t know what if any atom needs to come next.</div><div><br></div><div>That said, yes what we have is too complicated. Maybe this can be merged with the group concept, where for ELF all atoms in a section are by default in some “group”. Having a group keeps them all atoms in a group either all dead or all live. The layout engine just sorts by original address to sort atoms in a group, so the keep their relative position...</div><div><br></div><div>-Nick</div><div><br></div><div><br></div></body></html>