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

[peter.smith]

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.

[peter.smith]

Rebased, no other changes.

[ruiu]

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.

[peter.smith]

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.

[peter.smith]

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]

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]

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.

[ikudrin]

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>

[peter.smith]

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.

[peter.smith]

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

[peter.smith]

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

[smeenai]

ELF/Relocations.cpp

975 ↗

(On Diff #108617)

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

982 ↗

(On Diff #108617)

Space before .

[peter.smith]

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.

[peter.smith]

Rebasing after changes to use llvm::erase_if in D34689

[peter.smith]

Rebased to account for changes in D34689

[ruiu]

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

[smeenai]

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]

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.

[peter.smith]

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

[peter.smith]

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.

[smeenai]

In D34692#866448, @peter.smith wrote:

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?

[peter.smith]

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.

[peter.smith]

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

[ruiu]

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.

[smeenai]

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]

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.

[peter.smith]

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.

[smeenai]

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

lld/trunk/ELF/LinkerScript.h

struct InputSectionDescription : BaseCommand {
   StringMatcher FilePat;
 
   // Input sections that matches at least one of SectionPatterns
   // will be associated with this InputSectionDescription.
   std::vector<SectionPattern> SectionPatterns;
 
   std::vector<InputSection *> Sections;
 
-  // Temporary record of synthetic ThunkSection instances that we need to
-  // insert into Sections at the end of a createThunks() pass.
-  std::vector<ThunkSection *> ThunkSections;
+  // Temporary record of synthetic ThunkSection instances and the pass that
+  // they were created in. This is used to insert newly created ThunkSections
+  // into Sections at the end of a createThunks() pass.
+  std::vector<std::pair<ThunkSection *, uint32_t>> ThunkSections;
 };
 
 // Represents an ASSERT().
 struct AssertCommand : BaseCommand {
   AssertCommand(Expr E) : BaseCommand(AssertKind), Expression(E) {}
 
   static bool classof(const BaseCommand *C) { return C->Kind == AssertKind; }
 

lld/trunk/ELF/Relocations.h

void forEachInputSectionDescription(
       std::function<void(OutputSection *, InputSectionDescription *)> Fn);
 
   std::pair<Thunk *, bool> getThunk(SymbolBody &Body, RelType Type,
                                     uint64_t Src);
 
   ThunkSection *addThunkSection(OutputSection *OS, InputSectionDescription *,
                                 uint64_t Off);
 
+  bool normalizeExistingThunk(Relocation &Rel, uint64_t Src);
+
   // Record all the available Thunks for a Symbol
   llvm::DenseMap<SymbolBody *, std::vector<Thunk *>> ThunkedSymbols;
 
   // Find a Thunk from the Thunks symbol definition, we can use this to find
   // the Thunk from a relocation to the Thunks symbol definition.
   llvm::DenseMap<SymbolBody *, Thunk *> Thunks;
 
   // Track InputSections that have an inline ThunkSection placed in front

lld/trunk/ELF/Relocations.cpp

 
 template <class ELFT> void elf::scanRelocations(InputSectionBase &S) {
   if (S.AreRelocsRela)
     scanRelocs<ELFT>(S, S.relas<ELFT>());
   else
     scanRelocs<ELFT>(S, S.rels<ELFT>());
 }
 
-// Merge the ThunkSections created this pass into the InputSectionDescriptions.
+// Thunk Implementation
+//
+// Thunks (sometimes called stubs, veneers or branch islands) are small pieces
+// of code that the linker inserts inbetween a caller and a callee. The thunks
+// are added at link time rather than compile time as the decision on whether
+// a thunk is needed, such as the caller and callee being out of range, can only
+// be made at link time.
+//
+// It is straightforward to tell given the current state of the program when a
+// thunk is needed for a particular call. The more difficult part is that
+// the thunk needs to be placed in the program such that the caller can reach
+// the thunk and the thunk can reach the callee; furthermore, adding thunks to
+// the program alters addresses, which can mean more thunks etc.
+//
+// In lld we have a synthetic ThunkSection that can hold many Thunks.
+// The decision to have a ThunkSection act as a container means that we can
+// more easily handle the most common case of a single block of contiguous
+// Thunks by inserting just a single ThunkSection.
+//
+// The implementation of Thunks in lld is split across these areas
+// Relocations.cpp : Framework for creating and placing thunks
+// Thunks.cpp : The code generated for each supported thunk
+// Target.cpp : Target specific hooks that the framework uses to decide when
+//              a thunk is used
+// Synthetic.cpp : Implementation of ThunkSection
+// Writer.cpp : Iteratively call framework until no more Thunks added
+//
+// Thunk placement requirements:
+// Mips LA25 thunks. These must be placed immediately before the callee section
+// We can assume that the caller is in range of the Thunk. These are modelled
+// by Thunks that return the section they must precede with
+// getTargetInputSection().
+//
+// ARM interworking and range extension thunks. These thunks must be placed
+// within range of the caller. All implemented ARM thunks can always reach the
+// callee as they use an indirect jump via a register that has no range
+// restrictions.
+//
+// Thunk placement algorithm:
+// For Mips LA25 ThunkSections; the placement is explicit, it has to be before
+// getTargetInputSection().
+//
+// For thunks that must be placed within range of the caller there are many
+// possible choices given that the maximum range from the caller is usually
+// much larger than the average InputSection size. Desirable properties include:
+// - Maximize reuse of thunks by multiple callers
+// - Minimize number of ThunkSections to simplify insertion
+// - Handle impact of already added Thunks on addresses
+// - Simple to understand and implement
+//
+// In lld for the first pass, we pre-create one or more ThunkSections per
+// InputSectionDescription at Target specific intervals. A ThunkSection is
+// placed so that the estimated end of the ThunkSection is within range of the
+// start of the InputSectionDescription or the previous ThunkSection. For
+// example:
+// InputSectionDescription
+// Section 0
+// ...
+// Section N
+// ThunkSection 0
+// Section N + 1
+// ...
+// Section N + K
+// Thunk Section 1
+//
+// The intention is that we can add a Thunk to a ThunkSection that is well
+// spaced enough to service a number of callers without having to do a lot
+// of work. An important principle is that it is not an error if a Thunk cannot
+// be placed in a pre-created ThunkSection; when this happens we create a new
+// ThunkSection placed next to the caller. This allows us to handle the vast
+// majority of thunks simply, but also handle rare cases where the branch range
+// is smaller than the target specific spacing.
+//
+// The algorithm is expected to create all the thunks that are needed in a
+// single pass, with a small number of programs needing a second pass due to
+// the insertion of thunks in the first pass increasing the offset between
+// callers and callees that were only just in range.
+//
+// A consequence of allowing new ThunkSections to be created outside of the
+// pre-created ThunkSections is that in rare cases calls to Thunks that were in
+// range in pass K, are out of range in some pass > K due to the insertion of
+// more Thunks in between the caller and callee. When this happens we retarget
+// the relocation back to the original target and create another Thunk.
+
+// Remove ThunkSections that are empty, this should only be the initial set
+// precreated on pass 0.
+
+// Insert the Thunks for OutputSection OS into their designated place
+// in the Sections vector, and recalculate the InputSection output section
+// offsets.
+// This may invalidate any output section offsets stored outside of InputSection
 void ThunkCreator::mergeThunks(ArrayRef<OutputSection *> OutputSections) {
   forEachInputSectionDescription(
       OutputSections, [&](OutputSection *OS, InputSectionDescription *ISD) {
         if (ISD->ThunkSections.empty())
           return;
 
         // Remove any zero sized precreated Thunks.
-        llvm::erase_if(ISD->ThunkSections, [](const ThunkSection *TS) {
-          return TS->getSize() == 0;
+        llvm::erase_if(ISD->ThunkSections,
+                       [](const std::pair<ThunkSection *, uint32_t> &TS) {
+                         return TS.first->getSize() == 0;
                        });
-        // Order Thunks in ascending OutSecOff.
-        std::stable_sort(ISD->ThunkSections.begin(), ISD->ThunkSections.end(),
+        // ISD->ThunkSections contains all created ThunkSections, including
+        // those inserted in previous passes. Extract the Thunks created this
+        // pass and order them in ascending OutSecOff.
+        std::vector<ThunkSection *> NewThunks;
+        for (const std::pair<ThunkSection *, uint32_t> TS : ISD->ThunkSections)
+          if (TS.second == Pass)
+            NewThunks.push_back(TS.first);
+        std::stable_sort(NewThunks.begin(), NewThunks.end(),
                          [](const ThunkSection *A, const ThunkSection *B) {
                            return A->OutSecOff < B->OutSecOff;
                          });
 
         // Merge sorted vectors of Thunks and InputSections by OutSecOff
         std::vector<InputSection *> Tmp;
-        Tmp.reserve(ISD->Sections.size() + ISD->ThunkSections.size());
+        Tmp.reserve(ISD->Sections.size() + NewThunks.size());
         auto MergeCmp = [](const InputSection *A, const InputSection *B) {
           // std::merge requires a strict weak ordering.
           if (A->OutSecOff < B->OutSecOff)
             return true;
           if (A->OutSecOff == B->OutSecOff) {
             auto *TA = dyn_cast<ThunkSection>(A);
             auto *TB = dyn_cast<ThunkSection>(B);
             // Check if Thunk is immediately before any specific Target
             // InputSection for example Mips LA25 Thunks.
             if (TA && TA->getTargetInputSection() == B)
               return true;
             if (TA && !TB && !TA->getTargetInputSection())
               // Place Thunk Sections without specific targets before
               // non-Thunk Sections.
               return true;
           }
           return false;
         };
         std::merge(ISD->Sections.begin(), ISD->Sections.end(),
-                   ISD->ThunkSections.begin(), ISD->ThunkSections.end(),
-                   std::back_inserter(Tmp), MergeCmp);
+                   NewThunks.begin(), NewThunks.end(), std::back_inserter(Tmp),
+                   MergeCmp);
         ISD->Sections = std::move(Tmp);
-        ISD->ThunkSections.clear();
       });
 }
 
 // Find or create a ThunkSection within the InputSectionDescription (ISD) that
 // is in range of Src. An ISR maps to a range of InputSections described by a
 // linker script section pattern such as { .text .text.* }.
 ThunkSection *ThunkCreator::getISDThunkSec(OutputSection *OS, InputSection *IS,
                                            InputSectionDescription *ISD,
                                            uint32_t Type, uint64_t Src) {
-  for (ThunkSection *TS : ISD->ThunkSections) {
+  for (std::pair<ThunkSection *, uint32_t> TP : ISD->ThunkSections) {
+    ThunkSection *TS = TP.first;
     uint64_t TSBase = OS->Addr + TS->OutSecOff;
     uint64_t TSLimit = TSBase + TS->getSize();
     if (Target->inBranchRange(Type, Src, (Src > TSLimit) ? TSBase : TSLimit))
       return TS;
   }
 
   // No suitable ThunkSection exists. This can happen when there is a branch
   // with lower range than the ThunkSection spacing or when there are too
forEachInputSectionDescription(
         addThunkSection(OS, ISD, ISLimit);
       });
 }
 
 ThunkSection *ThunkCreator::addThunkSection(OutputSection *OS,
                                             InputSectionDescription *ISD,
                                             uint64_t Off) {
   auto *TS = make<ThunkSection>(OS, Off);
-  ISD->ThunkSections.push_back(TS);
+  ISD->ThunkSections.push_back(std::make_pair(TS, Pass));
   return TS;
 }
 
 std::pair<Thunk *, bool> ThunkCreator::getThunk(SymbolBody &Body, RelType Type,
                                                 uint64_t Src) {
   auto Res = ThunkedSymbols.insert({&Body, std::vector<Thunk *>()});
   if (!Res.second) {
     // Check existing Thunks for Body to see if they can be reused
for (OutputSection *OS : OutputSections) {
     if (!(OS->Flags & SHF_ALLOC) || !(OS->Flags & SHF_EXECINSTR))
       continue;
     for (BaseCommand *BC : OS->SectionCommands)
       if (auto *ISD = dyn_cast<InputSectionDescription>(BC))
         Fn(OS, ISD);
   }
 }
 
+// Return true if the relocation target is an in range Thunk.
+// Return false if the relocation is not to a Thunk. If the relocation target
+// was originally to a Thunk, but is no longer in range we revert the
+// relocation back to its original non-Thunk target.
+bool ThunkCreator::normalizeExistingThunk(Relocation &Rel, uint64_t Src) {
+  if (Thunk *ET = Thunks.lookup(Rel.Sym)) {
+    if (Target->inBranchRange(Rel.Type, Src, Rel.Sym->getVA()))
+      return true;
+    Rel.Sym = &ET->Destination;
+    if (Rel.Sym->isInPlt())
+      Rel.Expr = toPlt(Rel.Expr);
+  }
+  return false;
+}
+
 // Process all relocations from the InputSections that have been assigned
-// to InputSectionDescriptions and redirect through Thunks if needed.
-//
-// createThunks must be called after scanRelocs has created the Relocations for
-// each InputSection. It must be called before the static symbol table is
-// finalized. If any Thunks are added to an InputSectionDescription the
-// offsets within the OutputSection of the InputSections will change.
+// to InputSectionDescriptions and redirect through Thunks if needed. The
+// function should be called iteratively until it returns false.
 //
-// FIXME: Initial support for RangeThunks; only one pass supported.
+// PreConditions:
+// All InputSections that may need a Thunk are reachable from
+// OutputSectionCommands.
+//
+// All OutputSections have an address and all InputSections have an offset
+// within the OutputSection.
+//
+// The offsets between caller (relocation place) and callee
+// (relocation target) will not be modified outside of createThunks().
+//
+// PostConditions:
+// If return value is true then ThunkSections have been inserted into
+// OutputSections. All relocations that needed a Thunk based on the information
+// available to createThunks() on entry have been redirected to a Thunk. Note
+// that adding Thunks changes offsets between caller and callee so more Thunks
+// may be required.
+//
+// If return value is false then no more Thunks are needed, and createThunks has
+// made no changes. If the target requires range extension thunks, currently
+// ARM, then any future change in offset between caller and callee risks a
+// relocation out of range error.
 bool ThunkCreator::createThunks(ArrayRef<OutputSection *> OutputSections) {
   bool AddressesChanged = false;
   if (Pass == 0 && Target->ThunkSectionSpacing)
     createInitialThunkSections(OutputSections);
+  else if (Pass == 10)
+    // With Thunk Size much smaller than branch range we expect to
+    // converge quickly; if we get to 10 something has gone wrong.
+    fatal("thunk creation not converged");
 
   // Create all the Thunks and insert them into synthetic ThunkSections. The
   // ThunkSections are later inserted back into InputSectionDescriptions.
   // We separate the creation of ThunkSections from the insertion of the
   // ThunkSections as ThunkSections are not always inserted into the same
   // InputSectionDescription as the caller.
   forEachInputSectionDescription(
       OutputSections, [&](OutputSection *OS, InputSectionDescription *ISD) {
         for (InputSection *IS : ISD->Sections)
           for (Relocation &Rel : IS->Relocations) {
-            SymbolBody &Body = *Rel.Sym;
             uint64_t Src = OS->Addr + IS->OutSecOff + Rel.Offset;
-            if (Thunks.find(&Body) != Thunks.end() ||
-                !Target->needsThunk(Rel.Expr, Rel.Type, IS->File, Src, Body))
+
+            // If we are a relocation to an existing Thunk, check if it is
+            // still in range. If not then Rel will be altered to point to its
+            // original target so another Thunk can be generated.
+            if (Pass > 0 && normalizeExistingThunk(Rel, Src))
+              continue;
+
+            if (!Target->needsThunk(Rel.Expr, Rel.Type, IS->File, Src,
+                                    *Rel.Sym))
               continue;
             Thunk *T;
             bool IsNew;
-            std::tie(T, IsNew) = getThunk(Body, Rel.Type, Src);
+            std::tie(T, IsNew) = getThunk(*Rel.Sym, Rel.Type, Src);
             if (IsNew) {
               AddressesChanged = true;
               // Find or create a ThunkSection for the new Thunk
               ThunkSection *TS;
               if (auto *TIS = T->getTargetInputSection())
                 TS = getISThunkSec(TIS);
               else
                 TS = getISDThunkSec(OS, IS, ISD, Rel.Type, Src);

lld/trunk/ELF/Thunks.h

 // after executing transfers control to the callee. Typical uses of Thunks
 // include transferring control from non-pi to pi and changing state on
 // targets like ARM.
 //
 // Thunks can be created for DefinedRegular, Shared and Undefined Symbols.
 // Thunks are assigned to synthetic ThunkSections
 class Thunk {
 public:
-  Thunk(const SymbolBody &Destination);
+  Thunk(SymbolBody &Destination);
   virtual ~Thunk();
 
   virtual uint32_t size() const { return 0; }
   virtual void writeTo(uint8_t *Buf, ThunkSection &IS) const {}
 
   // All Thunks must define at least one symbol ThunkSym so that we can
   // redirect relocations to it.
   virtual void addSymbols(ThunkSection &IS) {}
 
   // Some Thunks must be placed immediately before their Target as they elide
   // a branch and fall through to the first Symbol in the Target.
   virtual InputSection *getTargetInputSection() const { return nullptr; }
 
   // To reuse a Thunk the caller as identified by the Type must be
   // compatible with it.
   virtual bool isCompatibleWith(RelType Type) const { return true; }
 
   // The alignment requirement for this Thunk, defaults to the size of the
   // typical code section alignment.
-  const SymbolBody &Destination;
+  SymbolBody &Destination;
   SymbolBody *ThunkSym;
-  uint64_t Offset;
+  uint64_t Offset = 0;
   uint32_t Alignment = 4;
 };
 
 // For a Relocation to symbol S create a Thunk to be added to a synthetic
 // ThunkSection. At present there are implementations for ARM and Mips Thunks.
 Thunk *addThunk(RelType Type, SymbolBody &S);
 
 } // namespace elf
 } // namespace lld
 
 #endif

lld/trunk/ELF/Thunks.cpp

 namespace elf {
 
 namespace {
 
 // Specific ARM Thunk implementations. The naming convention is:
 // Source State, TargetState, Target Requirement, ABS or PI, Range
 class ARMV7ABSLongThunk final : public Thunk {
 public:
-  ARMV7ABSLongThunk(const SymbolBody &Dest) : Thunk(Dest) {}
+  ARMV7ABSLongThunk(SymbolBody &Dest) : Thunk(Dest) {}
 
   uint32_t size() const override { return 12; }
   void writeTo(uint8_t *Buf, ThunkSection &IS) const override;
   void addSymbols(ThunkSection &IS) override;
   bool isCompatibleWith(RelType Type) const override;
 };
 
 class ARMV7PILongThunk final : public Thunk {
 public:
-  ARMV7PILongThunk(const SymbolBody &Dest) : Thunk(Dest) {}
+  ARMV7PILongThunk(SymbolBody &Dest) : Thunk(Dest) {}
 
   uint32_t size() const override { return 16; }
   void writeTo(uint8_t *Buf, ThunkSection &IS) const override;
   void addSymbols(ThunkSection &IS) override;
   bool isCompatibleWith(RelType Type) const override;
 };
 
 class ThumbV7ABSLongThunk final : public Thunk {
 public:
-  ThumbV7ABSLongThunk(const SymbolBody &Dest) : Thunk(Dest) { Alignment = 2; }
+  ThumbV7ABSLongThunk(SymbolBody &Dest) : Thunk(Dest) { Alignment = 2; }
 
   uint32_t size() const override { return 10; }
   void writeTo(uint8_t *Buf, ThunkSection &IS) const override;
   void addSymbols(ThunkSection &IS) override;
   bool isCompatibleWith(RelType Type) const override;
 };
 
 class ThumbV7PILongThunk final : public Thunk {
 public:
-  ThumbV7PILongThunk(const SymbolBody &Dest) : Thunk(Dest) { Alignment = 2; }
+  ThumbV7PILongThunk(SymbolBody &Dest) : Thunk(Dest) { Alignment = 2; }
 
   uint32_t size() const override { return 12; }
   void writeTo(uint8_t *Buf, ThunkSection &IS) const override;
   void addSymbols(ThunkSection &IS) override;
   bool isCompatibleWith(RelType Type) const override;
 };
 
 // MIPS LA25 thunk
 class MipsThunk final : public Thunk {
 public:
-  MipsThunk(const SymbolBody &Dest) : Thunk(Dest) {}
+  MipsThunk(SymbolBody &Dest) : Thunk(Dest) {}
 
   uint32_t size() const override { return 16; }
   void writeTo(uint8_t *Buf, ThunkSection &IS) const override;
   void addSymbols(ThunkSection &IS) override;
   InputSection *getTargetInputSection() const override;
 };
 
 // microMIPS R2-R5 LA25 thunk
 class MicroMipsThunk final : public Thunk {
 public:
-  MicroMipsThunk(const SymbolBody &Dest) : Thunk(Dest) {}
+  MicroMipsThunk(SymbolBody &Dest) : Thunk(Dest) {}
 
   uint32_t size() const override { return 14; }
   void writeTo(uint8_t *Buf, ThunkSection &IS) const override;
   void addSymbols(ThunkSection &IS) override;
   InputSection *getTargetInputSection() const override;
 };
 
 // microMIPS R6 LA25 thunk
 class MicroMipsR6Thunk final : public Thunk {
 public:
-  MicroMipsR6Thunk(const SymbolBody &Dest) : Thunk(Dest) {}
+  MicroMipsR6Thunk(SymbolBody &Dest) : Thunk(Dest) {}
 
   uint32_t size() const override { return 12; }
   void writeTo(uint8_t *Buf, ThunkSection &IS) const override;
   void addSymbols(ThunkSection &IS) override;
   InputSection *getTargetInputSection() const override;
 };
 
 } // end anonymous namespace
void MicroMipsR6Thunk::addSymbols(ThunkSection &IS) {
   ThunkSym->StOther |= STO_MIPS_MICROMIPS;
 }
 
 InputSection *MicroMipsR6Thunk::getTargetInputSection() const {
   auto *DR = dyn_cast<DefinedRegular>(&Destination);
   return dyn_cast<InputSection>(DR->Section);
 }
 
-Thunk::Thunk(const SymbolBody &D) : Destination(D), Offset(0) {}
+Thunk::Thunk(SymbolBody &D) : Destination(D), Offset(0) {}
 
 Thunk::~Thunk() = default;
 
 // Creates a thunk for Thumb-ARM interworking.
 static Thunk *addThunkArm(RelType Reloc, SymbolBody &S) {
   // ARM relocations need ARM to Thumb interworking Thunks.
   // Thumb relocations need Thumb to ARM relocations.
   // Use position independent Thunks if we require position independent code.

lld/trunk/ELF/Writer.cpp

if (!Script->HasSectionsCommand && !Config->Relocatable)
     fixSectionAlignments();
 
   // Some architectures use small displacements for jump instructions.
   // It is linker's responsibility to create thunks containing long
   // jump instructions if jump targets are too far. Create thunks.
   if (Target->NeedsThunks) {
     ThunkCreator TC;
     Script->assignAddresses();
-    if (TC.createThunks(OutputSections)) {
+    while (TC.createThunks(OutputSections)) {
       applySynthetic({InX::MipsGot},
                      [](SyntheticSection *SS) { SS->updateAllocSize(); });
       Script->assignAddresses();
-      if (TC.createThunks(OutputSections))
-        fatal("All non-range thunks should be created in first call");
     }
   }
 
   // Fill other section headers. The dynamic table is finalized
   // at the end because some tags like RELSZ depend on result
   // of finalizing other sections.
   for (OutputSection *Sec : OutputSections)
     Sec->finalize<ELFT>();

lld/trunk/test/ELF/arm-thumb-condbranch-thunk.s

+// REQUIRES: arm
+// RUN: llvm-mc -filetype=obj -triple=thumbv7a-none-linux-gnueabi %s -o %t
+// RUN: ld.lld %t -o %t2 2>&1
+// The output file is large, most of it zeroes. We dissassemble only the
+// parts we need to speed up the test and avoid a large output file
+// RUN: llvm-objdump -d %t2 -start-address=524288 -stop-address=524316 -triple=thumbv7a-linux-gnueabihf | FileCheck -check-prefix=CHECK1 %s
+// RUN: llvm-objdump -d %t2 -start-address=1048576 -stop-address=1048584 -triple=thumbv7a-linux-gnueabihf | FileCheck -check-prefix=CHECK2 %s
+// RUN: llvm-objdump -d %t2 -start-address=1572864 -stop-address=1572872 -triple=thumbv7a-linux-gnueabihf | FileCheck -check-prefix=CHECK3 %s
+// RUN: llvm-objdump -d %t2 -start-address=5242884 -stop-address=5242894 -triple=thumbv7a-linux-gnueabihf | FileCheck -check-prefix=CHECK4 %s
+// RUN: llvm-objdump -d %t2 -start-address=5767168 -stop-address=5767174 -triple=thumbv7a-linux-gnueabihf | FileCheck -check-prefix=CHECK5 %s
+// RUN: llvm-objdump -d %t2 -start-address=16777220 -stop-address=16777240 -triple=thumbv7a-linux-gnueabihf | FileCheck -check-prefix=CHECK6 %s
+// RUN: llvm-objdump -d %t2 -start-address=17825792 -stop-address=17825798 -triple=thumbv7a-linux-gnueabihf | FileCheck -check-prefix=CHECK7 %s
+// Test Range extension Thunks for the Thumb conditional branch instruction.
+// This instruction only has a range of 1Mb whereas all the other Thumb wide
+// Branch instructions have 16Mb range. We still place our pre-created Thunk
+// Sections at 16Mb intervals as conditional branches to a target defined
+// in a different section are rare.
+ .syntax unified
+// Define a function aligned on a half megabyte boundary
+ .macro FUNCTION suff
+ .section .text.\suff\(), "ax", %progbits
+ .thumb
+ .balign 0x80000
+ .globl tfunc\suff\()
+ .type  tfunc\suff\(), %function
+tfunc\suff\():
+ bx lr
+ .endm
+
+ .globl _start
+_start:
+ FUNCTION 00
+// Long Range Thunk needed for 16Mb range branch, can reach pre-created Thunk
+// Section
+ bl tfunc33
+// CHECK1: Disassembly of section .text:
+// CHECK1-NEXT: tfunc00:
+// CHECK1-NEXT:    80000:       70 47   bx      lr
+// CHECK1-NEXT:    80002:       7f f3 ff d7     bl      #16252926
+// CHECK1: __Thumbv7ABSLongThunk_tfunc05:
+// CHECK1-NEXT:    80008:       40 f2 01 0c     movw    r12, #1
+// CHECK1-NEXT:    8000c:       c0 f2 30 0c     movt    r12, #48
+// CHECK1-NEXT:    80010:       60 47   bx      r12
+// CHECK1: __Thumbv7ABSLongThunk_tfunc00:
+// CHECK1-NEXT:    80012:       40 f2 01 0c     movw    r12, #1
+// CHECK1-NEXT:    80016:       c0 f2 08 0c     movt    r12, #8
+// CHECK1-NEXT:    8001a:       60 47   bx      r12
+ FUNCTION 01
+// tfunc02 is within range of tfunc02
+ beq.w tfunc02
+// tfunc05 is out of range, and we can't reach the pre-created Thunk Section
+// create a new one.
+ bne.w tfunc05
+// CHECK2:  tfunc01:
+// CHECK2-NEXT:   100000:       70 47   bx      lr
+// CHECK2-NEXT:   100002:       3f f0 fd a7     beq.w   #524282 <tfunc02>
+// CHECK2-NEXT:   100006:       7f f4 ff a7     bne.w   #-524290 <__Thumbv7ABSLongThunk_tfunc05>
+ FUNCTION 02
+// We can reach the Thunk Section created for bne.w tfunc05
+ bne.w tfunc05
+ beq.w tfunc00
+// CHECK3:   180000:       70 47   bx      lr
+// CHECK3-NEXT:   180002:       40 f4 01 80     bne.w   #-1048574 <__Thumbv7ABSLongThunk_tfunc05>
+// CHECK3-NEXT:   180006:       00 f4 04 80     beq.w   #-1048568 <__Thumbv7ABSLongThunk_tfunc00>
+ FUNCTION 03
+ FUNCTION 04
+ FUNCTION 05
+ FUNCTION 06
+ FUNCTION 07
+ FUNCTION 08
+ FUNCTION 09
+// CHECK4:  __Thumbv7ABSLongThunk_tfunc03:
+// CHECK4-NEXT:   500004:       40 f2 01 0c     movw    r12, #1
+// CHECK4-NEXT:   500008:       c0 f2 20 0c     movt    r12, #32
+// CHECK4-NEXT:   50000c:       60 47   bx      r12
+ FUNCTION 10
+// We can't reach any Thunk Section, create a new one
+ beq.w tfunc03
+// CHECK5: tfunc10:
+// CHECK5-NEXT:   580000:       70 47   bx      lr
+// CHECK5-NEXT:   580002:       3f f4 ff a7     beq.w   #-524290 <__Thumbv7ABSLongThunk_tfunc03>
+ FUNCTION 11
+ FUNCTION 12
+ FUNCTION 13
+ FUNCTION 14
+ FUNCTION 15
+ FUNCTION 16
+ FUNCTION 17
+ FUNCTION 18
+ FUNCTION 19
+ FUNCTION 20
+ FUNCTION 21
+ FUNCTION 22
+ FUNCTION 23
+ FUNCTION 24
+ FUNCTION 25
+ FUNCTION 26
+ FUNCTION 27
+ FUNCTION 28
+ FUNCTION 29
+ FUNCTION 30
+ FUNCTION 31
+// CHECK6:  __Thumbv7ABSLongThunk_tfunc33:
+// CHECK6-NEXT:  1000004:       40 f2 01 0c     movw    r12, #1
+// CHECK6-NEXT:  1000008:       c0 f2 10 1c     movt    r12, #272
+// CHECK6-NEXT:  100000c:       60 47   bx      r12
+// CHECK6: __Thumbv7ABSLongThunk_tfunc00:
+// CHECK6-NEXT:  100000e:       40 f2 01 0c     movw    r12, #1
+// CHECK6-NEXT:  1000012:       c0 f2 08 0c     movt    r12, #8
+// CHECK6-NEXT:  1000016:       60 47   bx      r12
+ FUNCTION 32
+ FUNCTION 33
+ // We should be able to reach an existing ThunkSection.
+ b.w tfunc00
+// CHECK7: tfunc33:
+// CHECK7-NEXT:  1100000:       70 47   bx      lr
+// CHECK7-NEXT:  1100002:       00 f7 04 b8     b.w     #-1048568 <__Thumbv7ABSLongThunk_tfunc00>

lld/trunk/test/ELF/arm-thumb-thunk-empty-pass.s

+// REQUIRES: arm
+// RUN: llvm-mc -filetype=obj -triple=thumbv7a-none-linux-gnueabi %s -o %t
+// RUN: ld.lld %t -o %t2 2>&1
+// RUN: llvm-objdump -d %t2 -start-address=69632 -stop-address=69646 -triple=thumbv7a-linux-gnueabihf | FileCheck -check-prefix=CHECK1 %s
+// RUN: llvm-objdump -d %t2 -start-address=16846860 -stop-address=16846874 -triple=thumbv7a-linux-gnueabihf | FileCheck -check-prefix=CHECK2 %s
+ .syntax unified
+ .global _start, foo
+ .type _start, %function
+ .section .text.start,"ax",%progbits
+_start:
+ bl _start
+ .section .text.dummy1,"ax",%progbits
+ .space 0xfffffe
+ .section .text.foo,"ax",%progbits
+  .type foo, %function
+foo:
+ bl _start
+
+// CHECK1: Disassembly of section .text:
+// CHECK1-NEXT: _start:
+// CHECK1-NEXT:    11000:       ff f7 fe ff     bl      #-4
+// CHECK1: __Thumbv7ABSLongThunk__start:
+// CHECK1-NEXT:    11004:       41 f2 01 0c     movw    r12, #4097
+// CHECK1-NEXT:    11008:       c0 f2 01 0c     movt    r12, #1
+// CHECK1-NEXT:    1100c:       60 47   bx      r12
+
+// CHECK2: __Thumbv7ABSLongThunk__start:
+// CHECK2:       101100c:       41 f2 01 0c     movw    r12, #4097
+// CHECK2-NEXT:  1011010:       c0 f2 01 0c     movt    r12, #1
+// CHECK2-NEXT:  1011014:       60 47   bx      r12
+// CHECK2: foo:
+// CHECK2-NEXT:  1011016:       ff f7 f9 ff     bl      #-14

lld/trunk/test/ELF/arm-thunk-multipass.s

+// REQUIRES: arm
+// RUN: llvm-mc -filetype=obj -triple=armv7a-none-linux-gnueabi %s -o %t
+// RUN: ld.lld %t -o %t2 2>&1
+// The output file is large, most of it zeroes. We dissassemble only the
+// parts we need to speed up the test and avoid a large output file
+// RUN: llvm-objdump -d %t2 -start-address=1048578 -stop-address=1048586 -triple=thumbv7a-linux-gnueabihf  | FileCheck -check-prefix=CHECK1 %s
+// RUN: llvm-objdump -d %t2 -start-address=16777224 -stop-address=16777254 -triple=thumbv7a-linux-gnueabihf  | FileCheck -check-prefix=CHECK2 %s
+// RUN: llvm-objdump -d %t2 -start-address=17825818 -stop-address=17825828 -triple=thumbv7a-linux-gnueabihf  | FileCheck -check-prefix=CHECK3 %s
+// In this test case a branch that is in range and does not need its range
+// extended can be pushed out of range by another Thunk, necessitating another
+// pass
+
+ .macro FUNCTION suff
+ .section .text.\suff\(), "ax", %progbits
+ .thumb
+ .balign 0x100000
+ .globl tfunc\suff\()
+ .type  tfunc\suff\(), %function
+tfunc\suff\():
+ bx lr
+ .endm
+
+ FUNCTION 00
+ .globl _start
+_start:
+ bl target
+ b.w arm_target
+// arm_target is in range but needs an interworking thunk
+// CHECK1: _start:
+// CHECK1-NEXT:   100002:       00 f3 06 d0     bl      #15728652
+// CHECK1-NEXT:   100006:       ff f2 ff 97     b.w     #15728638 <__Thumbv7ABSLongThunk_arm_target>
+ nop
+ nop
+ nop
+ .globl target2
+ .type target2, %function
+        nop
+
+target2:
+ FUNCTION 01
+ FUNCTION 02
+ FUNCTION 03
+ FUNCTION 04
+ FUNCTION 05
+ FUNCTION 06
+ FUNCTION 07
+ FUNCTION 08
+ FUNCTION 09
+ FUNCTION 10
+ FUNCTION 11
+ FUNCTION 12
+ FUNCTION 13
+ FUNCTION 14
+ FUNCTION 15
+
+ .section .text.16, "ax", %progbits
+ .arm
+ .globl arm_target
+ .type arm_target, %function
+arm_target:
+ bx lr
+// CHECK2: __Thumbv7ABSLongThunk_arm_target:
+// CHECK2-NEXT:  1000008:       40 f2 02 0c     movw    r12, #2
+// CHECK2-NEXT:  100000c:       c0 f2 00 1c     movt    r12, #256
+// CHECK2-NEXT:  1000010:       60 47   bx      r12
+// CHECK2: __Thumbv7ABSLongThunk_target:
+// CHECK2-NEXT:  1000012:       40 f2 1b 0c     movw    r12, #27
+// CHECK2-NEXT:  1000016:       c0 f2 10 1c     movt    r12, #272
+// CHECK2-NEXT:  100001a:       60 47   bx      r12
+// CHECK2: __Thumbv7ABSLongThunk_target2:
+// CHECK2-NEXT:  100001c:       40 f2 13 0c     movw    r12, #19
+// CHECK2-NEXT:  1000020:       c0 f2 10 0c     movt    r12, #16
+// CHECK2-NEXT:  1000024:       60 47   bx      r12
+
+ .section .text.17, "ax", %progbits
+// Just enough space so that bl target is in range if no extension thunks are
+// generated.
+
+ .space 0x100000 - 12
+
+ .section .text.18, "ax", %progbits
+ .thumb
+ .globl target
+ .type target, %function
+// target is at maximum ARM branch range away from caller.
+target:
+// Similar case in the backwards direction
+ bl target2
+ nop
+ nop
+ bx lr
+// CHECK3: target:
+// CHECK3-NEXT:  110001a:       ff f6 ff ff     bl      #-1048578
+// CHECK3-NEXT:  110001e:       00 bf   nop
+// CHECK3-NEXT:  1100020:       00 bf   nop
+// CHECK3-NEXT:  1100022:       70 47   bx      lr

lld/trunk/test/ELF/arm-thunk-re-add.s

+// REQUIRES: arm
+// RUN: llvm-mc -filetype=obj -triple=thumbv7a-none-linux-gnueabi %s -o %t
+// RUN: ld.lld %t --shared -o %t.so
+// The output file is large, most of it zeroes. We dissassemble only the
+// parts we need to speed up the test and avoid a large output file
+// RUN: llvm-objdump -d %t.so -start-address=16777220 -stop-address=16777244 -triple=thumbv7a-linux-gnueabihf | FileCheck -check-prefix=CHECK1 %s
+// RUN: llvm-objdump -d %t.so -start-address=17825800 -stop-address=17825826 -triple=thumbv7a-linux-gnueabihf | FileCheck -check-prefix=CHECK2 %s
+// RUN: llvm-objdump -d %t.so -start-address=17825824 -stop-address=17825876 -triple=armv7a-linux-gnueabihf | FileCheck -check-prefix=CHECK3 %s
+
+// A branch to a Thunk that we create on pass N, can drift out of range if
+// other Thunks are added in between. In this case we must create a new Thunk
+// for the branch that is in range. We also need to make sure that if the
+// destination of the Thunk is in the PLT the new Thunk also targets the PLT
+ .syntax unified
+ .thumb
+
+ .macro FUNCTION suff
+ .section .text.\suff\(), "ax", %progbits
+ .thumb
+ .balign 0x80000
+ .globl tfunc\suff\()
+ .type  tfunc\suff\(), %function
+tfunc\suff\():
+ bx lr
+ .endm
+
+ .globl imported
+ .type imported, %function
+ .globl imported2
+ .type imported2, %function
+ .globl imported3
+ .type imported3, %function
+.globl imported4
+ .type imported4, %function
+ FUNCTION 00
+ FUNCTION 01
+ FUNCTION 02
+ FUNCTION 03
+ FUNCTION 04
+ FUNCTION 05
+ FUNCTION 06
+ FUNCTION 07
+ FUNCTION 08
+ FUNCTION 09
+ FUNCTION 10
+ FUNCTION 11
+ FUNCTION 12
+ FUNCTION 13
+ FUNCTION 14
+ FUNCTION 15
+ FUNCTION 16
+ FUNCTION 17
+ FUNCTION 18
+ FUNCTION 19
+ FUNCTION 20
+ FUNCTION 21
+ FUNCTION 22
+ FUNCTION 23
+ FUNCTION 24
+ FUNCTION 25
+ FUNCTION 26
+ FUNCTION 27
+ FUNCTION 28
+ FUNCTION 29
+ FUNCTION 30
+ FUNCTION 31
+// Precreated Thunk Pool goes here
+// CHECK1:  1000004:       40 f2 24 0c     movw    r12, #36
+// CHECK1-NEXT:  1000008:       c0 f2 10 0c     movt    r12, #16
+// CHECK1-NEXT:  100000c:       fc 44   add     r12, pc
+// CHECK1-NEXT:  100000e:       60 47   bx      r12
+// CHECK1: __ThumbV7PILongThunk_imported2:
+// CHECK1-NEXT:  1000010:       40 f2 28 0c     movw    r12, #40
+// CHECK1-NEXT:  1000014:       c0 f2 10 0c     movt    r12, #16
+// CHECK1-NEXT:  1000018:       fc 44   add     r12, pc
+// CHECK1-NEXT:  100001a:       60 47   bx      r12
+
+ .section .text.32, "ax", %progbits
+ .space 0x80000
+ .section .text.33, "ax", %progbits
+ .space 0x80000 - 0x14
+ .section .text.34, "ax", %progbits
+ // Need a Thunk to the PLT entry, can use precreated ThunkSection
+ .globl callers
+ .type callers, %function
+callers:
+ b.w imported
+ beq.w imported
+ b.w imported2
+// CHECK2: __ThumbV7PILongThunk_imported:
+// CHECK2-NEXT:  1100008:       40 f2 20 0c     movw    r12, #32
+// CHECK2-NEXT:  110000c:       c0 f2 00 0c     movt    r12, #0
+// CHECK2-NEXT:  1100010:       fc 44   add     r12, pc
+// CHECK2-NEXT:  1100012:       60 47   bx      r12
+// CHECK2: callers:
+// CHECK2-NEXT:  1100014:       ff f6 f6 bf     b.w     #-1048596 <__ThumbV7PILongThunk_imported>
+// CHECK2-NEXT:  1100018:       3f f4 f6 af     beq.w   #-20 <__ThumbV7PILongThunk_imported>
+// CHECK2-NEXT:  110001c:       ff f6 f8 bf     b.w     #-1048592 <__ThumbV7PILongThunk_imported2>
+
+// CHECK3: Disassembly of section .plt:
+// CHECK3-NEXT: $a:
+// CHECK3-NEXT:  1100020:       04 e0 2d e5     str     lr, [sp, #-4]!
+// CHECK3-NEXT:  1100024:       04 e0 9f e5     ldr     lr, [pc, #4]
+// CHECK3-NEXT:  1100028:       0e e0 8f e0     add     lr, pc, lr
+// CHECK3-NEXT:  110002c:       08 f0 be e5     ldr     pc, [lr, #8]!
+// CHECK3: $d:
+// CHECK3-NEXT:  1100030:       d0 0f 00 00     .word   0x00000fd0
+// CHECK3: $a:
+// CHECK3-NEXT:  1100034:       04 c0 9f e5     ldr     r12, [pc, #4]
+// CHECK3-NEXT:  1100038:       0f c0 8c e0     add     r12, r12, pc
+// CHECK3-NEXT:  110003c:       00 f0 9c e5     ldr     pc, [r12]
+// CHECK3: $d:
+// CHECK3-NEXT:  1100040:       cc 0f 00 00     .word   0x00000fcc
+// CHECK3: $a:
+// CHECK3-NEXT:  1100044:       04 c0 9f e5     ldr     r12, [pc, #4]
+// CHECK3-NEXT:  1100048:       0f c0 8c e0     add     r12, r12, pc
+// CHECK3-NEXT:  110004c:       00 f0 9c e5     ldr     pc, [r12]
+// CHECK3: $d:
+// CHECK3-NEXT:  1100050:       c0 0f 00 00     .word   0x00000fc0