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

[Shankar Easwaran]

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.

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 <mailto: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
>>     <mailto: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/8544f801/attachment.html>