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