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

[Rui Ueyama]

+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?
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140321/635987ef/attachment.html>