llvm dev - Jan 2016 - Need to refactor relocation handlers in ELF LLD

We have fairly large and complex code to handle relocations in Writer.cpp,
Target.cpp, OutputSections.cpp and InputSections.cpp. They started with
simple code, but because each patch added a small piece of code to the
existing one, it is becoming out of control now. For example, we have lots
of entangled boolean flags in the functions that interfere with each other
in an obscure fashion. Even I don't understand all these interactions.

We need to clean this up to get it back to be manageable. The code in
SymbolTable.cpp is for example pretty much readable and in my opinion
beautiful. I want the relocation handlers to be as readable as that is.

I think there are a few things we can to do to fix the problem.

1. I'd like everybody to not add any more complexity to the relocation
handler until we clean this up because as we add more code, it gets harder
to refactor. Any patch to reduce complexity is welcome.

2. The fact that we don't create SymbolBodies for local symbols is one of
the major factors to contribute that complexity. I experimented on creating
them, and the performance penalty seemed to be within a few percent, so
that's a good trade-off. I'll try that. We can offset that degradation
with
optimizations in other places.

3. We probably want to separate relocation relaxation from relocation
application. Currently it is a unified pass, but theoretically we can split
it up into two, so that we do relaxation and then apply remaining
relocations.

4. Last but not least, any code that is not obvious needs explanation in
comment, so that first-time readers who have basic knowledge on ELF can
read and understand the code. Even if code is very simple, comment may be
needed, because readers may want to know not only what is to be done but
also why we want to do that for what.

My bar for readability may be a little bit high, but I strongly believe
that that will eventually increase overall productivity. I really need help
from LLD developers to keep it readable and hackable. I'd greatly
appreciate any patch to reduce complexity. Thanks!
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160121/8dc8b268/attachment.html>

On 21 January 2016 at 04:11, Rui Ueyama <ruiu at google.com>
wrote:
> We have fairly large and complex code to handle relocations in Writer.cpp,
> Target.cpp, OutputSections.cpp and InputSections.cpp. They started with
> simple code, but because each patch added a small piece of code to the
> existing one, it is becoming out of control now. For example, we have lots
> of entangled boolean flags in the functions that interfere with each other
> in an obscure fashion. Even I don't understand all these interactions.
>
> We need to clean this up to get it back to be manageable. The code in
> SymbolTable.cpp is for example pretty much readable and in my opinion
> beautiful. I want the relocation handlers to be as readable as that is.
>
> I think there are a few things we can to do to fix the problem.
>
> 1. I'd like everybody to not add any more complexity to the relocation
> handler until we clean this up because as we add more code, it gets harder
> to refactor. Any patch to reduce complexity is welcome.
I agree. A short moratorium while we experiment with refactoring
sounds reasonable.
> 2. The fact that we don't create SymbolBodies for local symbols is one
of
> the major factors to contribute that complexity. I experimented on creating
> them, and the performance penalty seemed to be within a few percent, so
> that's a good trade-off. I'll try that. We can offset that
degradation with
> optimizations in other places.
I would like to leave this as a last resort. Putting things that don't
take part in symbol resolution into the symbol resolution is confusing
IMHO.
> 3. We probably want to separate relocation relaxation from relocation
> application. Currently it is a unified pass, but theoretically we can split
> it up into two, so that we do relaxation and then apply remaining
> relocations.
I agree with this one. A similar comment applies for deciding if we
need a dynamic relocation and actually creating it.

> My bar for readability may be a little bit high, but I strongly believe
that
> that will eventually increase overall productivity. I really need help from
> LLD developers to keep it readable and hackable. I'd greatly appreciate
any
> patch to reduce complexity. Thanks!
Thanks a lot for the work at making lld easier to understand.

I was away from coding and catching up on code review, but I agree
that this is important and will try to improve things a bit in here
before going back to code review (and then LTO).

What I will probably try first is reordering output so that we don't
need to compute the size upfront. That should give us quite a bit of
flexibility in refactoring anything else. I don't know if it will be
too costly, but I will report on anything I find.

Cheers,
Rafael

??I will look at relocation relaxations closer tomorrow, may be will be able to
suggest something to reduce complexity a bit.?


Best regards,
George.
________________________________
От: Rui Ueyama <ruiu at google.com>
Отправлено: 21 января 2016 г. 12:11
Кому: llvm-dev; Rafael Avila de Espindola; George Rimar; Simon Atanasyan; Davide
Italiano
Тема: Need to refactor relocation handlers in ELF LLD

We have fairly large and complex code to handle relocations in Writer.cpp,
Target.cpp, OutputSections.cpp and InputSections.cpp. They started with simple
code, but because each patch added a small piece of code to the existing one, it
is becoming out of control now. For example, we have lots of entangled boolean
flags in the functions that interfere with each other in an obscure fashion.
Even I don't understand all these interactions.

We need to clean this up to get it back to be manageable. The code in
SymbolTable.cpp is for example pretty much readable and in my opinion beautiful.
I want the relocation handlers to be as readable as that is.

I think there are a few things we can to do to fix the problem.

1. I'd like everybody to not add any more complexity to the relocation
handler until we clean this up because as we add more code, it gets harder to
refactor. Any patch to reduce complexity is welcome.

2. The fact that we don't create SymbolBodies for local symbols is one of
the major factors to contribute that complexity. I experimented on creating
them, and the performance penalty seemed to be within a few percent, so
that's a good trade-off. I'll try that. We can offset that degradation
with optimizations in other places.

3. We probably want to separate relocation relaxation from relocation
application. Currently it is a unified pass, but theoretically we can split it
up into two, so that we do relaxation and then apply remaining relocations.

4. Last but not least, any code that is not obvious needs explanation in
comment, so that first-time readers who have basic knowledge on ELF can read and
understand the code. Even if code is very simple, comment may be needed, because
readers may want to know not only what is to be done but also why we want to do
that for what.

My bar for readability may be a little bit high, but I strongly believe that
that will eventually increase overall productivity. I really need help from LLD
developers to keep it readable and hackable. I'd greatly appreciate any
patch to reduce complexity. Thanks!
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160121/ac191ba1/attachment.html>

On Thu, Jan 21, 2016 at 6:10 AM, Rafael Espíndola <
rafael.espindola at gmail.com> wrote:
> On 21 January 2016 at 04:11, Rui Ueyama <ruiu at google.com> wrote:
> > We have fairly large and complex code to handle relocations in
> Writer.cpp,
> > Target.cpp, OutputSections.cpp and InputSections.cpp. They started
with
> > simple code, but because each patch added a small piece of code to the
> > existing one, it is becoming out of control now. For example, we have
> lots
> > of entangled boolean flags in the functions that interfere with each
> other
> > in an obscure fashion. Even I don't understand all these
interactions.
> >
> > We need to clean this up to get it back to be manageable. The code in
> > SymbolTable.cpp is for example pretty much readable and in my opinion
> > beautiful. I want the relocation handlers to be as readable as that
is.
> >
> > I think there are a few things we can to do to fix the problem.
> >
> > 1. I'd like everybody to not add any more complexity to the
relocation
> > handler until we clean this up because as we add more code, it gets
> harder
> > to refactor. Any patch to reduce complexity is welcome.
>
> I agree. A short moratorium while we experiment with refactoring
> sounds reasonable.
>
> > 2. The fact that we don't create SymbolBodies for local symbols is
one of
> > the major factors to contribute that complexity. I experimented on
> creating
> > them, and the performance penalty seemed to be within a few percent,
so
> > that's a good trade-off. I'll try that. We can offset that
degradation
> with
> > optimizations in other places.
>
> I would like to leave this as a last resort. Putting things that don't
> take part in symbol resolution into the symbol resolution is confusing
> IMHO.
>
I don't think so, as the symbol plays a major role not only in symbol
resolution but also in relocation application. It is easier to model that
all relocations point to symbols. That is true in ELF so that's a direct
modeling of the ELF structure. Let me try to experiment -- we can abandon
the idea if it becomes clear that that doesn't worth.

>
> > 3. We probably want to separate relocation relaxation from relocation
> > application. Currently it is a unified pass, but theoretically we can
> split
> > it up into two, so that we do relaxation and then apply remaining
> > relocations.
>
> I agree with this one. A similar comment applies for deciding if we
> need a dynamic relocation and actually creating it.

Good point. Looks like visiting relocations sequentially is pretty fast
because they are continuous in memory, so I expect that the cost of
iterating over them a few times is marginal.
> My bar for readability may be a little bit high, but I strongly believe
> that
> > that will eventually increase overall productivity. I really need help
> from
> > LLD developers to keep it readable and hackable. I'd greatly
appreciate
> any
> > patch to reduce complexity. Thanks!
>
> Thanks a lot for the work at making lld easier to understand.
>
> I was away from coding and catching up on code review, but I agree
> that this is important and will try to improve things a bit in here
> before going back to code review (and then LTO).
>
> What I will probably try first is reordering output so that we don't
> need to compute the size upfront. That should give us quite a bit of
> flexibility in refactoring anything else. I don't know if it will be
> too costly, but I will report on anything I find.
>
I don't know if computing the size upfront increased complexity. Was it?
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160121/e9138e46/attachment-0001.html>