This is an archive of the discontinued LLVM Phabricator instance.

[LLD][ELF] Add support for multiple passes to createThunks()
ClosedPublic

Authored by peter.smith on Jun 27 2017, 8:17 AM.

Details

Summary

This change allows Thunks to be added on multiple passes. To do this we must merge only the thunks added in each pass, and deal with thunks that have
drifted out of range of their callers. A thunk may end out of range of its caller if enough thunks are added in between the caller and the thunk. To handle this we create another thunk.

This is patch 9/11 of range thunks. It is dependent on all previous patches D34691 and its dependencies. It is the last implementation patch, the remaining couple are test cases.

The most important changes are:

  • If a call to an existing thunk created on the last pass is now out of range, we redirect the relocation back to the original caller
  • With multiple passes we may be inserting Thunks into existing ThunkSections without creating any new ThunkSections so we can't use a count of created thunk sections to determine if we need another pass.

Diff Detail

Repository
rL LLVM

Event Timeline

peter.smith created this revision.Jun 27 2017, 8:17 AM

Rebased, no other changes.

ruiu edited edge metadata.Jul 11 2017, 4:45 PM

This is getting a bit tricky. I think creating thunks is by nature a bit tricky, so it is perhaps unavoidable, but I think writing a document (or a document style comment) that describes the overview of the thunk creation would help. My file comment in https://github.com/llvm-project/llvm-project-20170507/blob/master/lld/ELF/ICF.cpp is an example. The other example is https://github.com/llvm-project/llvm-project-20170507/blob/master/lld/ELF/Threads.h.

Understood. I'll attempt to write a comment in the code first. If it gets too big then I suppose it could go into docs as an rst file. I'll update as soon as it is ready.

I've added a large summary comment, as well as updating some more of the comments to better explain the Thunk Implementation. I've also added in the remainder of the tests from D31665 that need this patch to work correctly.

ruiu added a comment.Jul 13 2017, 5:26 PM

Thank you for writing these large summary comments! They are extremely helpful to understand the code.

ELF/Relocations.cpp
1034 ↗(On Diff #106438)

Section -> ThunkSection

1085 ↗(On Diff #106438)

nit: remove else after return.

1249 ↗(On Diff #106438)

This function returns false if a given relocation does not point to a thunk. Is this correct? I thought that this function is expected to return false only when it undo previous thunk creations.

1281 ↗(On Diff #106438)

Can you clear this vector at end of this function instead? I think "discarding when it is no longer needed" is easier to understand.

1285 ↗(On Diff #106438)

Error messages should start with lowercase letter.

1286 ↗(On Diff #106438)

nit: add {}

ELF/Relocations.h
156 ↗(On Diff #106438)

This is not directly related to this patch, but I believe we should move this to SymbolBody to eliminate the cost of hash table lookup.

peter.smith marked 6 inline comments as done.

Thanks very much for the comments. I've made the suggested changes apart from moving the mapping from Symbol to Thunk to SymbolBody. I'll submit a separate review for that.

ELF/Relocations.cpp
1249 ↗(On Diff #106438)

Yes it is intentional, I've updated the comment. The intention is that if the target of the relocation is an in range thunk we are done and can continue. If false then we are not pointing to a thunk and may need to generate a new one.

I'm on the fence about whether it is a good idea to use a function here as it is quite difficult to find a name for it. What I originally had in createThunks() was something like:

if (target is Thunk) {
  if (Thunk is in Range)
    continue;
  else
    revert to original target
}

I used a function to try and avoid createThunks() getting too large. It may be better to remove the function.

ELF/Relocations.h
156 ↗(On Diff #106438)

I'll submit this in a separate review. It would increase the memory usage for Targets that don't use Thunks so I think it would be best to keep it separate.

grimar added a subscriber: grimar.Jul 17 2017, 2:13 AM

This is a copy of a comment from D34689.

It is possible that a precreated thunk section stays empty in the first pass, but is used in the next pass. In that case, it isn't added into ISR in ThunkCreator::mergeThunks(). For example:

$ cat a.s
	.global _start, foo
.section .text.start,"ax",%progbits
_start:
	bl _start
.section .text.dummy1,"ax",%progbits
.space 0xfffffe
.section .text.foo,"ax",%progbits
foo:
	bl _start
$ llvm-mc -filetype=obj -triple=thumbv7a-none-linux-gnueabi a.s -o a.o
$ ld.lld a.o -o a.out
$ objdump -d a.out
a.out:     file format elf32-littlearm


Disassembly of section .text:

00011000 <_start>:
   11000:	f7ff effe 	blx	11000 <_start>

00011004 <__Thumbv7ABSLongThunk__start>:
   11004:	f241 0c00 	movw	ip, #4096	; 0x1000
   11008:	f2c0 0c01 	movt	ip, #1
   1100c:	4760      	bx	ip
	...

01011002 <__Thumbv7ABSLongThunk__start>:
	...

0101100c <foo>:
 101100c:	f7ff fff9 	bl	1011002 <__Thumbv7ABSLongThunk__start>

Rebased to account for r308056 and r308057. I've also updated mergeThunks() to account for Igor's test case (thanks very much Igor!). I've taken the simple solution of making sure that the empty ThunkSections are removed from ThunkSections and NewThunkSections, a test case derived from Igor's has been added to make sure this doesn't regress. My expectation is that the vast majority of Thunks will be added in the first pass so the lack of pre-created sections in later passes shouldn't make a significant difference.

Rebased to account for "r308300 [ELF] - Fix member name: alignment -> Alignment. NFC.". No other changes to patch.

Rebased to account for r309311 Merge OutputSectionCommand and OutputSection. No other changes.

smeenai added inline comments.Aug 4 2017, 9:54 PM
ELF/Relocations.cpp
975 ↗(On Diff #108617)

I believe "branch islands" is a pretty common term as well.

982 ↗(On Diff #108617)

Space before .

Thanks for the comments, I've updated the diff to add branch islands and corrected the space before the full stop. No other changes to the code.

Rebasing after changes to use llvm::erase_if in D34689

Rebased to account for changes in D34689

ruiu added inline comments.Sep 7 2017, 5:48 PM
ELF/Relocations.cpp
1299–1303 ↗(On Diff #114184)

I think it feels more natural if you move this piece of code after needsThunk check.

ELF/Relocations.h
179 ↗(On Diff #114184)

Using a std::vector<T> * as a key seems a bit odd to me. IIUC, this vector is a member of InputSection, so we can attach a vector of ThunkSections to InputSections, no?

ELF/Thunks.h
52 ↗(On Diff #114184)

Offset = 0

Mostly nits again. The logic looks good to me, though I'm far from being completely familiar with all parts of the existing code.

ELF/Relocations.cpp
977 ↗(On Diff #114184)

Grammar nit: such as the caller and the callee being out of range

983 ↗(On Diff #114184)

Grammar nit: the comma should be a semicolon, and there should be a comma after furthermore.

1011 ↗(On Diff #114184)

Grammar nit: the comma should be either a colon or a semicolon, and there should be a period at the end of the sentence.

1022 ↗(On Diff #114184)

Grammar nit: In lld, for the first pass, ...

1025 ↗(On Diff #114184)

I think "previous" sounds clearer than "last" here.

1039 ↗(On Diff #114184)

Grammar nit: in a pre-created ThunkSection; when this happens, ...

1055 ↗(On Diff #114184)

Grammar nit: comma should be semicolon.

1100 ↗(On Diff #114184)

Nit: period at the end.

1259 ↗(On Diff #114184)

Nit: Period at the end.

1284 ↗(On Diff #114184)

Grammar nit: comma ->semicolon.

ELF/Relocations.h
172 ↗(On Diff #114184)

I think it would be clearer to put a period at the end of InputSectionRange above, and make this line its own sentence, i.e. "This will contain ...".

178 ↗(On Diff #114184)

"All the ThunkSections that we have created in the current pass", perhaps? The comment as it stands doesn't make the difference between ThunkSections and NewThunkSections apparent.

Nit: period at the end of the sentence.

peter.smith marked 13 inline comments as done.

I've made the straightforward and comment changes.

ELF/Relocations.cpp
1299–1303 ↗(On Diff #114184)

Unfortunately it can't as normalizeExistingThunk() will reset the relocation Rel to the original target if the original Thunk has gone out of range, this prompts needsThunk to create a new Thunk to the original target. If it is moved the needsThunk will be testing against a different Target Symbol.

ELF/Relocations.h
179 ↗(On Diff #114184)

The NewThunkSections is just the subset of ThunkSections that we've created this pass. We need to check all the existing ThunkSections to see if we can reuse them for a new Thunk, however we only want to insert the ThunkSections we've created this pass (the others have already been inserted).

Both NewThunkSections and ThunkSections could be made members of InputSectionDescription, but this would make a local mapping table globally visible to all Targets.

I think that these could be potentially made into flat vectors of ThunkSections, at the cost of some logic of separating all the ThunkSections to go into a particular InputSectionDescription later.

Rebased to account for changes in D34689, D34691 and D37627 no other changes.

Using a std::vector<T> * as a key seems a bit odd to me. IIUC, this vector is a member of InputSection, so we can attach a vector of ThunkSections to InputSections, no?

I've had a think about this a bit more. I think that there is an alternative way to represent ThunkSections and NewThunkSections:

  • Store a vector of std::pair<ThunkSection*, uint32_t> where the second member of the pair is the Pass that the ThunkSection was added in.
  • When the first Thunk is added to a ThunkSection for the first time we record the Pass.
  • When merging Thunks into InputSectionDescription for Pass P we extract the Thunks with size > 0 that were created on Pass P and merge them in.

This would require quite a bit of changes to the existing code, for example we'd need to iterate through InputSectionDescriptions and not std::vector<InputSection *> in both createThunks() and mergeThunks(). I'm going to have a go at implementing it but will post as a separate review.

Using a std::vector<T> * as a key seems a bit odd to me. IIUC, this vector is a member of InputSection, so we can attach a vector of ThunkSections to InputSections, no?

I've had a think about this a bit more. I think that there is an alternative way to represent ThunkSections and NewThunkSections:

  • Store a vector of std::pair<ThunkSection*, uint32_t> where the second member of the pair is the Pass that the ThunkSection was added in.
  • When the first Thunk is added to a ThunkSection for the first time we record the Pass.
  • When merging Thunks into InputSectionDescription for Pass P we extract the Thunks with size > 0 that were created on Pass P and merge them in.

This would require quite a bit of changes to the existing code, for example we'd need to iterate through InputSectionDescriptions and not std::vector<InputSection *> in both createThunks() and mergeThunks(). I'm going to have a go at implementing it but will post as a separate review.

All of this wouldn't be necessary if you made these vectors members of InputSectionDescription, as @ruiu suggested in D34689, correct?

Updated diff to implement the idea to use the pass number the ThunkSection was created in to indicate the ThunkSections that need to be merged (those created this pass). This has the advantage of only having one vector in InputSectionDescription.

All of this wouldn't be necessary if you made these vectors members of InputSectionDescription, as @ruiu suggested in https://reviews.llvm.org/D34689, correct?

As I understand it we need some means to identify the existing ThunkSections that have already been inserted and the ThunkSections we have just created but not inserted yet. In the original implementation I used ThunkSections and the subset NewThunkSections to record the difference. I have a slight preference for recording the pass number in ThunkSections as this lessens the chance of ThunkSections and NewThunkSections being used inconsistently. I'm open to suggestions for better ways of doing this. One potential idea is to store the index or an iterator into the ThunkSections that records what has been inserted so far.

Rebased to account for r314797 addition of thunks for microMIPS code. No other changes.

ruiu accepted this revision.Oct 25 2017, 7:38 PM

OK, let's land this first. I'm really sorry to take that long to review this patch, I apologize for that. I hoped that I could have refactored Relocations.cpp before landing more code there, but apparently I couldn't be a roadblock anymore for this change. I'll try to reduce complexity of relocation handling after you submit this patch.

This revision is now accepted and ready to land.Oct 25 2017, 7:38 PM

At the developer meeting @peter.smith had said the thunks implementation could be moved out into its own file provided one relocation function was available to it. If it's easy enough to do, perhaps we want to do that before landing, to alleviate the concerns around the relocations code becoming even more complicated?

ruiu added a comment.Oct 25 2017, 7:58 PM

We can do that, that can easily be done later. The complexity exists in the logic of the existing functions, and file layout is not a concern.

In D34692#907451, @ruiu wrote:

OK, let's land this first. I'm really sorry to take that long to review this patch, I apologize for that. I hoped that I could have refactored Relocations.cpp before landing more code there, but apparently I couldn't be a roadblock anymore for this change. I'll try to reduce complexity of relocation handling after you submit this patch.

Thank you very much for the approval. As some of the approved patches depend on D34689 I'll wait until that one clears and commit all the patches at once.

This revision was automatically updated to reflect the committed changes.

Thank you for being flexible on these, @ruiu! It makes our life a lot easier downstream :)