[LLVMdev] LLD: Layout-after and layout-before

[Nick Kledzik]

On Mar 21, 2014, at 3:45 PM, Rui Ueyama <ruiu at google.com> wrote:

> +llvmdev
> 
> On Fri, Mar 21, 2014 at 3:43 PM, Rui Ueyama <ruiu at google.com> wrote:
> Hi all,
> 
> 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.
> 
> 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.
> 
> 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.
> 
> Removing one of layout-before/layout-after edges has three benefits:
> 
>  1. Reduces memory usage and runtime overhead
>  2. Simpler code and algorithm
>  3. No need to maintain consistency between layout-before/layout-after edges, which is often a cause of nasty bugs.
> 
> Does this sound good?

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).

If you only have layout-before, the actual layout is hard because you don’t know what if any atom needs to come next.

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...

-Nick


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140321/27d19867/attachment.html>