[LLD][ELF] Introduce Thunk reuse compatibility

[peter.smith]

Summary

On ARM the interworking thunks are only produced for branch instructions that can't be changed into a blx instruction so only Thumb callers would call Thumb thunks and only ARM callers would call ARM thunks. With range extension thunks branch and link instructions may need a Thunk. These instructions can be rewritten as a blx and can use either ARM or Thumb thunks.

We introduce a compatibleWith() function so that a caller can check if an existing Thunk is compatible before reusing it. With the currently supported interworking thunks all the thunks are reusable by construction so there will be no impact on the tests.

[peter.smith]

Is there any more I can do to explain this patch?

In the current Thunk implementation we only permit 1 Thunk per Target symbol and by construction all callers to that symbol are compatible with the Thunk. Once we have range extension thunks this will no longer be the case. For example we might have ARM and Thumb branches (can't use blx) to a target symbol S, these callers cannot share the same Thunk.

This patch by construction will return true for all the currently supported thunks.

[evgeny777]

@ruiu , can you please look at this?

[peter.smith]

At least one person has asked me when range thunks for ARM will be ready. I'd like to post the full feature for review and maintain it so that if anyone wants to play about with it they can.
This is patch 1 of 11 of range thunks.

I've posted the full range thunks implementation in a single patch for them in https://reviews.llvm.org/D34634 . This can be used for context on how I'm intending the final code to look.

[peter.smith]

Is there anything I can do to help get the Range Thunks patches looked at? To avoid pinging 11 separate patches I've listed all the reviews here and what the intention behind them is. I'm happy to restructure these in a different way if that would help?

There are 11 patches to get to a full implementation.
These two don't need to touch anything outside of the Thunk implementation, they don't add any functionality, but do prepare some of the groundwork.
D34035 [LLD][ELF] Introduce Thunk reuse compatibility
D34037 [LLD][ELF] Allow multiple thunks to be added for a symbol.

These two are the only significant changes outside of the Thunk implementation, for range thunks what I need to do is to be able to calculate addresses in order to check ranges. This is just one approach to get to that point, I'm happy to go for a different approach or help in any refactoring.
D34344 [LLD][ELF] Extract allocateHeaders() from assignAddresses()
D34345 [LLD][ELF] Reset any accumulated state before calculating addresses
D34688 [LLD][ELF] Add call to assignAddresses() before createThunks() [NFC]

These patches apart from one small change to Writer.cpp to enable multiple passes in D34692 are all within the Thunk implementation. The design for range thunks is to use the address information to pre-create one or more ThunkSections per InputSectionDescription that we can use place Thunks in range of their callers. D34691 is enough for simple cases, D34692 deals with corner cases that can occur if you are unlucky.
D34689 [LLD][ELF] Pre-create ThunkSections at Target specific intervals
D34690 [LLD][ELF] Introduce target specific inBranchRange() function
D34691 [LLD][ELF] Introduce range extension thunks for ARM
D34692 [LLD][ELF] Add support for multiple passes to createThunks()

I've separated out the test cases as they are by far the largest amount of changes. The majority need all the changes in D34692 to run successfully. I could extract some of these tests for 34691
D31665 [LLD][ELF] Add test cases for range extension thunks (no linkerscripts)
D31666 [LLD][ELF] Add test cases for range extension thunks using linker scripts

lld/trunk/ELF/Relocations.cpp

ThunkSection *ThunkCreator::addThunkSection(OutputSection *OS,
   ThunkSections[ISR].push_back(TS);
   return TS;
 }
 
 
 std::pair<Thunk *, bool> ThunkCreator::getThunk(SymbolBody &Body,
                                                 uint32_t Type) {
   auto res = ThunkedSymbols.insert({&Body, nullptr});
-  if (res.second)
+  if (res.second || !res.first->second->isCompatibleWith(Type))
     res.first->second = addThunk(Type, Body);
   return std::make_pair(res.first->second, res.second);
 }
 
 // Call Fn on every executable InputSection accessed via the linker script
 // InputSectionDescription::Sections.
 void ThunkCreator::forEachExecInputSection(
     ArrayRef<OutputSectionCommand *> OutputSections,

lld/trunk/ELF/Thunks.h

public:
   // 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 RelocType must be
+  // compatible with it.
+  virtual bool isCompatibleWith(uint32_t RelocType) const { return true; }
+
   // The alignment requirement for this Thunk, defaults to the size of the
   // typical code section alignment.
   const SymbolBody &Destination;
   SymbolBody *ThunkSym;
   uint64_t Offset;
   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(uint32_t RelocType, SymbolBody &S);
 
 } // namespace elf
 } // namespace lld
 
 #endif

lld/trunk/ELF/Thunks.cpp

 // Source State, TargetState, Target Requirement, ABS or PI, Range
 class ARMV7ABSLongThunk final : public Thunk {
 public:
   ARMV7ABSLongThunk(const 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(uint32_t RelocType) const override;
 };
 
 class ARMV7PILongThunk final : public Thunk {
 public:
   ARMV7PILongThunk(const 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(uint32_t RelocType) const override;
 };
 
 class ThumbV7ABSLongThunk final : public Thunk {
 public:
   ThumbV7ABSLongThunk(const 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(uint32_t RelocType) const override;
 };
 
 class ThumbV7PILongThunk final : public Thunk {
 public:
   ThumbV7PILongThunk(const 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(uint32_t RelocType) const override;
 };
 
 // MIPS LA25 thunk
 class MipsThunk final : public Thunk {
 public:
   MipsThunk(const SymbolBody &Dest) : Thunk(Dest) {}
 
   uint32_t size() const override { return 16; }

 
 void ARMV7ABSLongThunk::addSymbols(ThunkSection &IS) {
   ThunkSym = addSyntheticLocal(
       Saver.save("__ARMv7ABSLongThunk_" + Destination.getName()), STT_FUNC,
       Offset, size(), &IS);
   addSyntheticLocal("$a", STT_NOTYPE, Offset, 0, &IS);
 }
 
+bool ARMV7ABSLongThunk::isCompatibleWith(uint32_t RelocType) const {
+  // Thumb branch relocations can't use BLX
+  return RelocType != R_ARM_THM_JUMP19 && RelocType != R_ARM_THM_JUMP24;
+}
+
 void ThumbV7ABSLongThunk::writeTo(uint8_t *Buf, ThunkSection &IS) const {
   const uint8_t Data[] = {
       0x40, 0xf2, 0x00, 0x0c, // movw         ip, :lower16:S
       0xc0, 0xf2, 0x00, 0x0c, // movt         ip, :upper16:S
       0x60, 0x47,             // bx   ip
   };
   uint64_t S = getARMThunkDestVA(Destination);
   memcpy(Buf, Data, sizeof(Data));
   Target->relocateOne(Buf, R_ARM_THM_MOVW_ABS_NC, S);
   Target->relocateOne(Buf + 4, R_ARM_THM_MOVT_ABS, S);
 }
 
 void ThumbV7ABSLongThunk::addSymbols(ThunkSection &IS) {
   ThunkSym = addSyntheticLocal(
       Saver.save("__Thumbv7ABSLongThunk_" + Destination.getName()), STT_FUNC,
       Offset | 0x1, size(), &IS);
   addSyntheticLocal("$t", STT_NOTYPE, Offset, 0, &IS);
 }
 
+bool ThumbV7ABSLongThunk::isCompatibleWith(uint32_t RelocType) const {
+  // ARM branch relocations can't use BLX
+  return RelocType != R_ARM_JUMP24 && RelocType != R_ARM_PC24 &&
+         RelocType != R_ARM_PLT32;
+}
+
 void ARMV7PILongThunk::writeTo(uint8_t *Buf, ThunkSection &IS) const {
   const uint8_t Data[] = {
       0xf0, 0xcf, 0x0f, 0xe3, // P:  movw ip,:lower16:S - (P + (L1-P) +8)
       0x00, 0xc0, 0x40, 0xe3, //     movt ip,:upper16:S - (P + (L1-P+4) +8)
       0x0f, 0xc0, 0x8c, 0xe0, // L1: add ip, ip, pc
       0x1c, 0xff, 0x2f, 0xe1, //     bx r12
   };
   uint64_t S = getARMThunkDestVA(Destination);
   uint64_t P = ThunkSym->getVA();
   memcpy(Buf, Data, sizeof(Data));
   Target->relocateOne(Buf, R_ARM_MOVW_PREL_NC, S - P - 16);
   Target->relocateOne(Buf + 4, R_ARM_MOVT_PREL, S - P - 12);
 }
 
 void ARMV7PILongThunk::addSymbols(ThunkSection &IS) {
   ThunkSym = addSyntheticLocal(
       Saver.save("__ARMV7PILongThunk_" + Destination.getName()), STT_FUNC,
       Offset, size(), &IS);
   addSyntheticLocal("$a", STT_NOTYPE, Offset, 0, &IS);
 }
 
+bool ARMV7PILongThunk::isCompatibleWith(uint32_t RelocType) const {
+  // Thumb branch relocations can't use BLX
+  return RelocType != R_ARM_THM_JUMP19 && RelocType != R_ARM_THM_JUMP24;
+}
+
 void ThumbV7PILongThunk::writeTo(uint8_t *Buf, ThunkSection &IS) const {
   const uint8_t Data[] = {
       0x4f, 0xf6, 0xf4, 0x7c, // P:  movw ip,:lower16:S - (P + (L1-P) + 4)
       0xc0, 0xf2, 0x00, 0x0c, //     movt ip,:upper16:S - (P + (L1-P+4) + 4)
       0xfc, 0x44,             // L1: add  r12, pc
       0x60, 0x47,             //     bx   r12
   };
   uint64_t S = getARMThunkDestVA(Destination);
   uint64_t P = ThunkSym->getVA() & ~0x1;
   memcpy(Buf, Data, sizeof(Data));
   Target->relocateOne(Buf, R_ARM_THM_MOVW_PREL_NC, S - P - 12);
   Target->relocateOne(Buf + 4, R_ARM_THM_MOVT_PREL, S - P - 8);
 }
 
 void ThumbV7PILongThunk::addSymbols(ThunkSection &IS) {
   ThunkSym = addSyntheticLocal(
       Saver.save("__ThumbV7PILongThunk_" + Destination.getName()), STT_FUNC,
       Offset | 0x1, size(), &IS);
   addSyntheticLocal("$t", STT_NOTYPE, Offset, 0, &IS);
 }
 
+bool ThumbV7PILongThunk::isCompatibleWith(uint32_t RelocType) const {
+  // ARM branch relocations can't use BLX
+  return RelocType != R_ARM_JUMP24 && RelocType != R_ARM_PC24 &&
+         RelocType != R_ARM_PLT32;
+}
+
 // Write MIPS LA25 thunk code to call PIC function from the non-PIC one.
 void MipsThunk::writeTo(uint8_t *Buf, ThunkSection &) const {
   uint64_t S = Destination.getVA();
   write32(Buf, 0x3c190000, Config->Endianness);                // lui   $25, %hi(func)
   write32(Buf + 4, 0x08000000 | (S >> 2), Config->Endianness); // j     func
   write32(Buf + 8, 0x27390000, Config->Endianness);            // addiu $25, $25, %lo(func)
   write32(Buf + 12, 0x00000000, Config->Endianness);           // nop
   Target->relocateOne(Buf, R_MIPS_HI16, S);