[ELF] - Implemented basic location counter support.

[grimar]

Summary

This patch implements location counter support.
It also separates assign addresses for sections to assignAddressesScript() if it scipt exists.

Main testcase is test/ELF/linkerscript-locationcounter.s, It contains some work with location counter. It is basic now.
Implemented location counter assignment and '+' operations.

[ruiu]

ELF/LinkerScript.h

71 ↗

(On Diff #52364)

Why do you need this function? If the linker script directly assign VAs to sections, we don't need this.

[grimar]

• Addressed review comments.

ELF/LinkerScript.h

71 ↗

(On Diff #52394)

If so - yes.

ELF/Writer.cpp

1417 ↗

(On Diff #52394)

Misunderstanding :) I thought you want to have Script->getSecVA() method.
Without that all life is easier of course.
Removed whole method.

1421–1425 ↗

(On Diff #52394)

Nope. Removed.

[ruiu]

ELF/LinkerScript.cpp

36 ↗

(On Diff #52399)

It seems that we don't need this class because this class has only one member, LocCounter and you always reset LocCounter before calling evaluate. This class can just be a function that takes the current VA and an expression and returns a new VA.

72 ↗

(On Diff #52399)

It is better to move this variable inside LinkerScript.

109 ↗

(On Diff #52399)

Does this have to be a lambda?

125 ↗

(On Diff #52399)

Why do you have to remove the element here?

267–270 ↗

(On Diff #52399)

The concept of dummy sections seems a bit confusing. Could you improve it?

ELF/LinkerScript.h

52–54 ↗

(On Diff #52399)

I wouldn't use the same variable for completely different purposes. I'd define two fields, Expr and SectionName, instead.

[grimar]

ELF/LinkerScript.cpp

109 ↗

(On Diff #52399)

Please see answer in below comment.

125 ↗

(On Diff #52399)

I need to visit all output sections to assign addresses for each.
Script can mention only some of them.
There were 2 choices I saw:

1. Make this lambda and do 2 iterations. First iteration visits everything that was directly mentioned in script. During that it removes the sections if found from global list. After that we will have all unvisited sections in this global list. Then second iteration visits them all.

That gives 2 iterations, but complexity is O(n) in total.

2. In this variant it is possible to insert all sections that were not mentioned in script to Locations list at the begining of method and avoid using lambda. That would be one loop. Problem here that is that if we have OutputSectionBase list and have Locations lists then how to find those sections for which LocationNode was not created to vizit ?

That would be something like (pseudocode):

for (OutputSectionBase<ELFT> *Sec : S) {
  if (S NOT IN Locations) {
    Locations.push_back(create location for S);
  }
}

That is O(N^2) part of code that can be inserted at the begining of this method, that can help to get rid of labmda and do all in one iteration.

[ruiu]

ELF/LinkerScript.cpp

125 ↗

(On Diff #52399)

This is a bit too convoluted. It'd need a few trial-and-errors, but it should be able to be written in a straightforward way. I'd probably start making this lambda a separate function.

610 ↗

(On Diff #52399)

Exist -> Exists

629 ↗

(On Diff #52399)

Remove S.

ELF/LinkerScript.h

48 ↗

(On Diff #52399)

I'd make this a enum class and rename members as shown below.

LocNodeType -> Command
LocSet -> Expr
LocOutSet -> Section

ELF/Writer.cpp

228 ↗

(On Diff #52399)

Let's name this assignAddresses for consistency with the Writer.

[grimar]

Ok, thank you for review, I`ll address this all later today/tomorrow I think (except dummies).

ELF/LinkerScript.cpp

267–270 ↗

(On Diff #52399)

I guess you mean not only for this patch but whole dummies approach, right ?
We can probably just get rid of them, like we had before ?

[ruiu]

ELF/LinkerScript.cpp

267–270 ↗

(On Diff #52399)

Yes, I'm talking about the approach itself. I'm not sure what you mean by "just get rid of them" (can we do that? I think we need some replacements for them,) but the point is that the code here for the dummy sections seem a bit too complex, so it needs to be improved.

[grimar]

ELF/LinkerScript.cpp

267–270 ↗

(On Diff #52399)

Ok. When I say "get rid" I mean that some time ago they were not sections. So we definetely can do that and just the question "how to do this better now ?" left. I`ll try to suggest some patch to change that.

[grimar]

ELF/LinkerScript.cpp

267–270 ↗

(On Diff #52399)

So, my suggestion patch about dummies sections is D18743.

[grimar]

I`ll update/rebase this as soon as D18743 be landed (If will). The last one can help to simplify the code of this I think.

[grimar]

• Addressed review comments.

ELF/LinkerScript.cpp

36 ↗

(On Diff #52399)

Done.

72 ↗

(On Diff #52399)

Since that class not exist, variable also not exist anymore.

125 ↗

(On Diff #52399)

Done. Made lambda as separate function + refactored code to have only one iteration.

610 ↗

(On Diff #52399)

Done.

629 ↗

(On Diff #52399)

Done.

ELF/LinkerScript.h

48 ↗

(On Diff #52399)

Done.

52–54 ↗

(On Diff #52399)

Done.

ELF/Writer.cpp

228 ↗

(On Diff #52399)

Done.

[grimar]

• Rebased

[ruiu]

ELF/LinkerScript.cpp

424 ↗

(On Diff #53242)

I think you should remove addLocation function and directly add new elements to Locations vector since you intentionally merge two different control flow into one function and dispatch again using the first argument. That's just confusing.

ELF/LinkerScript.h

47 ↗

(On Diff #53242)

Let's make this an enum class because it currently adds "Section" and "Expr" to lld::elf namespace.

48 ↗

(On Diff #53242)

Add blank line before this struct definition.

74 ↗

(On Diff #53242)

Arg -> Args

[grimar]

• Addressed review comments.

ELF/LinkerScript.cpp

424 ↗

(On Diff #53242)

Removed.

ELF/LinkerScript.h

47 ↗

(On Diff #53242)

Done.

48 ↗

(On Diff #53242)

Done.

74 ↗

(On Diff #53242)

There is no such method anymore.

[ruiu]

ELF/LinkerScript.cpp

51–65 ↗

(On Diff #53374)

Define this method

uint64_t getInteger(StringRef S) {
  uint64_t V;
  if (S.getAsInteger(0, V)) {
    setError("malformed number: " + V);
    return 0;
 }
  retrurn V;
}

Then you can simplify this to

StringRef Tok = Tokens[I];
if (Tok == ".")
  Result += LocCounter;
else
  Result += getInteger(Tok);

94 ↗

(On Diff #53374)

Are you aware of the fact that StringMap copies keys? Maybe DenseMap is more efficient because it doesn't copy StringRefs?

113 ↗

(On Diff #53374)

Needs () around &.

131 ↗

(On Diff #53374)

This function seems a bit too complicated. This function construct temporary data to feed to setSectionsAddresses. Do we really need to do that? Isn't there any way to make it simpler?

154 ↗

(On Diff #53374)

Flip the condition and use early continue.

[grimar]

• Addressed review comments.

ELF/LinkerScript.cpp

51–65 ↗

(On Diff #53374)

Done.
Btw, few iterations ago I had code like this.
http://reviews.llvm.org/D18499?id=52399#inline-156527
Looks when you requested to make a single function from whole class I understood this too straightforward (combined exactly into one function) :)

94 ↗

(On Diff #53374)

I missed that fact. Thanks for pointing on that.
There is no such method and variable anymore.

113 ↗

(On Diff #53374)

Done.

131 ↗

(On Diff #53374)

Reimplemented in much more straighforward way.

154 ↗

(On Diff #53374)

There is no such code anymore.

[grimar]

ELF/LinkerScript.cpp

95 ↗

(On Diff #53563)

At the same time if we talk about perfomance then I think most narrow place is lookup and not creation of container.
So I can guess StringMap still was faster since it does not recompute hash during lookup.
I didn't check since code was cut off.

[ruiu]

ELF/LinkerScript.cpp

98–99 ↗

(On Diff #53563)

Although it is technically correct that what we are doing here is different from the doc, I don't think it necessarily mean it needs to be marked as "FIXME". My impression is that if you control section layout using linker scripts, you need to give complete layout. So please remove "FIXME" label from this comment and just state the fact:

Orphan sections are sections present in the input files which are not explicitly placed into the output file by the linker script. We place orphan sections at end of file. Other linkers places them using some heuristics as described in https://sourceware.org/binutils/docs/ld/Orphan-Sections.html#Orphan-Sections.

ELF/LinkerScript.h

69 ↗

(On Diff #53563)

fixUp -> fixup

[grimar]

• Addressed review comments.

ELF/LinkerScript.cpp

98–99 ↗

(On Diff #53563)

My impression is that if you control section layout using linker scripts, you need to give complete layout.

Perfect, done ! I was thinking about the same often. For me it was always a bit wierd that linker do something on his own when script is given. That complicates the whole things at the same time privides no strict rules, but only heuristics, what can be confusing.
I was not sure that is acceptable to change that behavior though.

ELF/LinkerScript.h

69 ↗

(On Diff #53563)

Done.

[ruiu]

Please update the commit message. This is not a prototype even though its feature is limited. This is a patch that will be committed as part of the linker.

ELF/LinkerScript.cpp

40 ↗

(On Diff #53682)

You probably have to do this

error("malformed number: " + Twine(V))

115 ↗

(On Diff #53682)

Call fixupLocations here instead of exporting it and call it from the Writer.

129–130 ↗

(On Diff #53682)

This shouldn't happen now, no?

485–492 ↗

(On Diff #53682)

Remove.

ELF/LinkerScript.h

68–69 ↗

(On Diff #53682)

Make it private.

[grimar]

• Addressed review comment.

ELF/LinkerScript.cpp

40 ↗

(On Diff #53682)

I think what I want is:

error("malformed number: " + S);

Updated testcase.

115 ↗

(On Diff #53682)

Done.

129–130 ↗

(On Diff #53682)

This can happen. Imagine asm code:

.global _start
_start:
 nop

and script that contains section description, but this section is absent in code above:

SECTIONS {
 .stub : { *(.stub) }
}

Since there is no such section, OutputSections list will not contain it, but location node will still be created and needs to be skipped then.

485–492 ↗

(On Diff #53682)

Done.

ELF/LinkerScript.h

68–69 ↗

(On Diff #53682)

Done.

[grimar]

About D19107 and SectionOrder vector.
What about landing this and eliminating the SectionOrder at all ?

At fact when we have Locations structure, SectionOrder is just a subset. We can use
Locations instead to sort sections in compareSections.

The only problem then - that fixupLocations() should be called much earlier then.
I think previous iteration was better for such purposes.

[grimar]

• Fixed clang warning.

[ruiu]

LGTM

[grimar]

In D18499#402693, @ruiu wrote:

LGTM

Thank you for all these reviews of that !