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

[Rui Ueyama]

On Fri, Mar 21, 2014 at 4:45 PM, Shankar Easwaran
<shankare at codeaurora.org>wrote:

>  Hi Rui,
>
> 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.
>

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.

Thanks
>
> Shankar Easwaran
>
>
> On 3/21/2014 6:38 PM, Rui Ueyama wrote:
>
>  Thank you for quick responses!
>
>  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.
>
>  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.
>
>  I'll try to modify the dead-stripping pass as I described above. Any
> concerns?
>
> On Fri, Mar 21, 2014 at 4:10 PM, Shankar Easwaran <shankare at codeaurora.org
> > wrote:
>
>>  Hi Rui,
>>
>> ELF uses layout-after and in-group references now. It no longer uses
>> layout-before.
>>
>> 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.
>>
>> Thanks
>>
>> Shankar Easwaran
>>
>>
>> On 3/21/2014 5:45 PM, Rui Ueyama 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?
>>>
>>
>>
>>
>>   --
>> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by the Linux Foundation
>>
>>
>
>
> --
> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by the Linux Foundation
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140321/7d134153/attachment.html>