[ELF] Implement infrastructure for thunk code creation

[atanasyan]

Summary

Some targets might require creation of thunks. For example, MIPS targets require stubs to call PIC code from non-PIC one. The patch implements infrastructure for thunk code creation and provides support for MIPS LA25 stubs. Any MIPS PIC code function is invoked with its address in register $t9. So if we have a branch instruction from non-PIC code to the PIC one we cannot make the jump directly and need to create a small stub to save the target function address.
See page 3-38 ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf

• In relocation scanning phase we ask target about thunk creation necessity by calling TagetInfo::needsThunk method. The InputSection class maintains list of Symbols requires thunk creation.

• Reassigning offsets performed for each input sections after relocation scanning complete because position of each section might change due thunk creation.

• The patch introduces new dedicated value for DefinedSynthetic symbols DefinedSynthetic::SectionEnd. Synthetic symbol with that value always points to the end of the corresponding output section. That allows to escape updating synthetic symbols if output sections sizes changes after relocation scanning due thunk creation.

• In the InputSection::writeTo method we write thunks after corresponding input section. Each thunk is written by calling TargetInfo::writeThunk method.

• The patch supports the only type of thunk code for each target. For now, it is enough.

[ruiu]

I'm still reading this patch, but does it work for all cases? When you want to create a thunk for a short-range jump instruction, you want to locate that thunk within the range of the instruction. Output sections can be large. Putting thunks at end of each output section will work?

[atanasyan]

In D17934#369150, @ruiu wrote:

I'm still reading this patch, but does it work for all cases? When you want to create a thunk for a short-range jump instruction, you want to locate that thunk within the range of the instruction. Output sections can be large. Putting thunks at end of each output section will work?

I had a solution which puts stubs in the beginning of the corresponding input section. In that case the risk to get too long jump is smaller. But this solution seemed to me over-complicated a bit. Let me think again till tomorrow. Maybe I revert that solution.

[ruiu]

This is just an idea and I'm not suggesting that that is better, but you
can scan a list of input sections and insert stub sections to the list,
instead of appending stub sections to input/output sections.

[atanasyan]

Write thunks before corresponding InputSection's to reduce risk of getting too long jump.

[ruiu]

ELF/OutputSections.cpp

806

Using a hash table feels a bit tricky. Can you add a pointer to SymbolBody to point to a thunk?

ELF/Target.cpp

1690–1707

Needs a comment.

1729

Please run clang-format-diff.

1741

We have using namespace llvm::ELF.

1743

We usually name an object of type Elf_Sym ElfSym. In this case, the return type of RHS is still our own symbol type, so I'd name differently, say just Sym, D, Defined or something like that.

1747–1753

This can be

return (ElfSym->Section->getFile()->getObj().getHeader()->e_flags & EF_MIPS_PIC) ||
       (ElfSym->Sym.st_other & STO_MIPS_MIPS16) == STO_MIPS_PIC;

ELF/Writer.cpp

345–351

I don't like to add new code to this function because this function is overloaded. Particularly, when this code will be executed is not very obvious because if a condition above is true and it reaches a continue, this code will be skipped. Will this code be skipped for all correct cases?

Can you create a new loop over relocations and move this code there?

1042–1043

This seems a bit odd.

If we always reassign offsets, then we don't want to reassign offsets at all. Instead, we want to assign offsets right here only once.

1060–1064

I don't understand what this is supposed to do?

1175

What is this change for?

[atanasyan]

ELF/OutputSections.cpp

806

I need a link between input section and corresponding set of thunks to put the thunks in the right place during a "write" phase. I can add pointer to ThunkChunk to the InputSectionBase class. That will allow to remove this DenseMap. Is it acceptable to you?

ELF/Target.cpp

1690–1707

Will do

1729

OK

1741

OK

1743

OK

1747–1753

OK

ELF/Writer.cpp

345–351

OK. I will try to do so.

1042–1043

You are right. The assignOffsets is better name.

1060–1064

This and the next change are related. Now we add synthetic symbols pointing to beginning and end of output sections before relocation scanning phase. In this patch output section size might change during the relocation scanning. So synthetic symbols point to the end of sections need to be updated. There is a couple of possible solutions:

• Add synthetic symbols after the relocation scanning. Not sure that this does not affect something in relocation scanning phase.
• Use special value DefinedSynthetic<ELFT>::End to mark symbol that need to point to the end of sections. Update such symbols with the correct value later.

In this patch I use the second solution. Do you think it is safe to add synthetic symbols after the relocation scanning?

[ruiu]

ELF/OutputSections.cpp

806

I think that instead of attaching a chunk to an InputSection, we may be able to define a new type of (synthesized) InputSection for a thunk. Then we can keep OutputSection to have a flat list of InputSections instead of InputSections + their attachment. It may be cleaner approach IMO.

In that design, we can make a symbol have a pointer to a thunk input section. getThunkVA() returns the VA of the thunk input section, so it just have to call getVA on the thunk section.

What do you think? I'm not sure if this is really cleaner, but I'd think it's worth to try.

ELF/Writer.cpp

1060–1064

OK. So if we keep the output section to have a flat list of input sections instead of input sections + their chunks, the size of the output section wouldn't change during relocation scanning phase, right?

[atanasyan]

ELF/OutputSections.cpp

806

Now the root of input section hierarchy InputSectionBase class is tightly related to ELF input section. Its constructor requires reference to ObjectFile and Elf_Shdr. If we want to introduce something like SyntheticInputSection which is unrelated to and file and ELF header we have to create new root base class and inherit SyntheticInputSection and InputSectionBase. One more problem is that OutputSection::Sections container contains pointers to InputSection objects and it is not clear how to mix InputSection and SyntheticInputSection in the same container.

ELF/Writer.cpp

1060–1064

Before the scanning phase we know nothing about thunks. During the scanning we either add chunks to OutputSections or create synthetic input sections and add them to OutputSections too. In any case the size will change.

[atanasyan]

Fixed minor issues found on review. The open questions are updating synthetic symbols values and necessity to introduce new SyntheticInputSction class.

[atanasyan]

Rebased the patch.

[ruiu]

This looks still a bit too intrusive. The code to handles thunks appears too many places.

Maybe we should handle thunks as a separate output section? Then we don't need to add addThunk to the regular output section class and we don't have to update the code to calculate section size and offsets.

[atanasyan]

In D17934#374020, @ruiu wrote:

This looks still a bit too intrusive. The code to handles thunks appears too many places.

Maybe we should handle thunks as a separate output section? Then we don't need to add addThunk to the regular output section class and we don't have to update the code to calculate section size and offsets.

I see some problems here:

• We can get a really long out-of-range jumps. I remember that my initial solution had the same problem but it was my mistake.
• The output section should have a name. Putting all thunks into the separate output section is in fact ABI extension because we have to choose dedicated unique name for such section. Moreover if somebody have a linker script to put output sections in exact places (common case for embedded software developers), it will be surprise that he or she have to handle one more unusual output section.
• There is optimization used by bfd and gold linkers - if input section contains the only function and we need to create a thunk for it, we can place the thunk in the beginning of the section and use just two assembly instructions to save the function address into the $25 registers and do not use additional jump instructions at all. My patch does not implement this optimization yet but moving all thunks into the separate output section make such optimization impossible at all.

I think the less intrusive solution is to concentrate the thunk handling in the InputSection class. We can add a vector of SymbolBody pointers right to this class. In that case only InputSection and TargetInfo descendant will know about synthetic code.

BTW MIPS is not the only target uses thunks. AFAIK ARM has concept of veneer.

[atanasyan]

• Isolated almost all thunk handling code in the InputSection class
• Reduced number of auxiliary classes, containers etc

[atanasyan]

Ping?

[atanasyan]

Ping?

[atanasyan]

Rebase the patch.

[ruiu]

I'm sorry that I missed this one. Taking a look now.

[ruiu]

ELF/InputSection.cpp

42–45

I feel like this is slightly more readable.

if (auto *D = dyn_cast<InputSection<ELFT>>(this))
  if (D->getThunksSize() > 0)
    return D->getThunkOff() + D->getThunksSize();
return Header->sh_size;

117

Is the thunk need to be aligned? If so, does it have the same alignment as the original section?

271

This needs a comment.

326

This needs a comment, saying that a section may have attached data that needs to be written after the section, and that data is usually a thunk to jump to a location that is too far to fit in a short jump instruction.

ELF/InputSection.h

172 ↗

(On Diff #52145)

I'd also mention that you can ignore this if you are interested only in x86/x86-64.

190 ↗

(On Diff #52145)

TinyPtrVector is probably better as I expect this is empty in most cases.

ELF/Target.cpp

1734

It is probably better to just say that "see MipsTargetInfo::writeThunk for details" instead of copying the comment.

ELF/Writer.cpp

481–493

Please make this a separate function and call only for platforms that need thunks.

[atanasyan]

• Use TinyPtrVector to store in the InputSection class pointers to SymbolBody which requires thunk creation.
• Create separate Writer::scanRelocsForThunks method for scanning relocations
• Remove thunks alignment. We do not need to do that.
• Simplify InputSectionBase::getSize
• Fix some comments

[ruiu]

LGTM with a nit. I think it is now simple enough to submit. Thanks!

ELF/Writer.cpp

303

Invert the condition and use continue.

[atanasyan]

Thanks for review.

ELF/InputSection.cpp

InputSectionBase<ELFT>::InputSectionBase(ObjectFile<ELFT> *File,
   Live = !Config->GcSections;
 
   // The ELF spec states that a value of 0 means the section has
   // no alignment constraits.
   Align = std::max<uintX_t>(Header->sh_addralign, 1);
 }
 
 template <class ELFT> StringRef InputSectionBase<ELFT>::getSectionName() const {
   return check(File->getObj().getSectionName(this->Header));
 }
 
 template <class ELFT>
 ArrayRef<uint8_t> InputSectionBase<ELFT>::getSectionData() const {
   return check(this->File->getObj().getSectionContents(this->Header));
 }
 
 template <class ELFT>
 typename ELFFile<ELFT>::uintX_t
 InputSectionBase<ELFT>::getOffset(uintX_t Offset) {
   switch (SectionKind) {

 }
 
 // This is used for -r. We can't use memcpy to copy relocations because we need
 // to update symbol table offset and section index for each relocation. So we
 // copy relocations one by one.
 template <class ELFT>
 template <bool isRela>
 void InputSection<ELFT>::copyRelocations(uint8_t *Buf,
                                          RelIteratorRange<isRela> Rels) {
   typedef Elf_Rel_Impl<ELFT, isRela> RelType;
   InputSectionBase<ELFT> *RelocatedSection = getRelocatedSection();
 
   for (const RelType &Rel : Rels) {
     uint32_t SymIndex = Rel.getSymbol(Config->Mips64EL);
     uint32_t Type = Rel.getType(Config->Mips64EL);
     SymbolBody &Body = this->File->getSymbolBody(SymIndex).repl();
 
if (Target->needsPlt<ELFT>(Type, Body)) {
       if (Body.IsTls)
         Type = Target->getTlsGotRel(Type);
     } else if (Target->isSizeRel(Type) && CBP) {
       // A SIZE relocation is supposed to set a symbol size, but if a symbol
       // can be preempted, the size at runtime may be different than link time.
       // If that's the case, we leave the field alone rather than filling it
       // with a possibly incorrect value.
       continue;
+    } else if (Target->needsThunk(Type, *this->getFile(), Body)) {
+      SymVA = Body.getThunkVA<ELFT>();
     } else if (Config->EMachine == EM_MIPS) {
       if (Type == R_MIPS_HI16 && &Body == Config->MipsGpDisp) {
         SymVA = getMipsGpAddr<ELFT>() - AddrLoc + A;
       } else if (Type == R_MIPS_LO16 && &Body == Config->MipsGpDisp) {
         SymVA = getMipsGpAddr<ELFT>() - AddrLoc + 4 + A;
       } else if (&Body == Config->MipsLocalGp) {
         SymVA = getMipsGpAddr<ELFT>() + A;
       } else if (Type == R_MIPS_GPREL16 || Type == R_MIPS_GPREL32) {
template <class ELFT> void InputSection<ELFT>::writeTo(uint8_t *Buf) {
   // Iterate over all relocation sections that apply to this section.
   for (const Elf_Shdr *RelSec : this->RelocSections) {
     if (RelSec->sh_type == SHT_RELA)
       this->relocate(Buf, BufEnd, EObj.relas(RelSec));
     else
       this->relocate(Buf, BufEnd, EObj.rels(RelSec));
   }
 }
 
 template <class ELFT>
 void InputSection<ELFT>::replace(InputSection<ELFT> *Other) {
   this->Align = std::max(this->Align, Other->Align);
   Other->Repl = this->Repl;
   Other->Live = false;
 }
 
 template <class ELFT>

ELF/OutputSections.h

 template <class ELFT> class EHInputSection;
 template <class ELFT> class InputSection;
 template <class ELFT> class InputSectionBase;
 template <class ELFT> class MergeInputSection;
 template <class ELFT> class MipsReginfoInputSection;
 template <class ELFT> class OutputSection;
 template <class ELFT> class ObjectFile;
 template <class ELFT> class DefinedRegular;
+template <class ELFT> class ThunkChunk;
 
 template <class ELFT>
 static inline typename llvm::object::ELFFile<ELFT>::uintX_t
 getAddend(const typename llvm::object::ELFFile<ELFT>::Elf_Rel &Rel) {
   return 0;
 }
 
 template <class ELFT>
public:
   uintX_t getVA() const { return Header.sh_addr; }
   void setFileOffset(uintX_t Off) { Header.sh_offset = Off; }
   void setSHName(unsigned Val) { Header.sh_name = Val; }
   void writeHeaderTo(Elf_Shdr *SHdr);
   StringRef getName() { return Name; }
 
   virtual void addSection(InputSectionBase<ELFT> *C) {}
 
+  virtual void addThunk(const InputSectionBase<ELFT> &C, SymbolBody &S) {}
+  virtual uintX_t getThunkOffset(const InputSectionBase<ELFT> &C) { return 0; }
+
   unsigned SectionIndex;
 
   // Returns the size of the section in the output file.
   uintX_t getSize() const { return Header.sh_size; }
   void setSize(uintX_t Val) { Header.sh_size = Val; }
   uintX_t getFlags() { return Header.sh_flags; }
   uintX_t getFileOff() { return Header.sh_offset; }
   uintX_t getAlign() {
     // The ELF spec states that a value of 0 means the section has no alignment
     // constraits.
     return std::max<uintX_t>(Header.sh_addralign, 1);
   }
   uint32_t getType() { return Header.sh_type; }
   void updateAlign(uintX_t Align) {
     if (Align > Header.sh_addralign)
       Header.sh_addralign = Align;
   }
 
+  virtual void assignOffsets() {}
   virtual void finalize() {}
   virtual void writeTo(uint8_t *Buf) {}
   virtual ~OutputSectionBase() = default;
 
 protected:
   StringRef Name;
   Elf_Shdr Header;
 };

 public:
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Shdr Elf_Shdr;
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Sym Elf_Sym;
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Rel Elf_Rel;
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Rela Elf_Rela;
   typedef typename llvm::object::ELFFile<ELFT>::uintX_t uintX_t;
   OutputSection(StringRef Name, uint32_t Type, uintX_t Flags);
   void addSection(InputSectionBase<ELFT> *C) override;
+  void addThunk(const InputSectionBase<ELFT> &C, SymbolBody &S) override;
+  uintX_t getThunkOffset(const InputSectionBase<ELFT> &C) override;
   void sortInitFini();
   void sortCtorsDtors();
   void writeTo(uint8_t *Buf) override;
+  void assignOffsets() override;
   void finalize() override;
 
 private:
-  void reassignOffsets();
   std::vector<InputSection<ELFT> *> Sections;
+  llvm::DenseMap<const InputSectionBase<ELFT> *, ThunkChunk<ELFT>*> ThunkChunks;
+  llvm::BumpPtrAllocator Alloc;
 };
 
 template <class ELFT>
 class MergeOutputSection final : public OutputSectionBase<ELFT> {
   typedef typename OutputSectionBase<ELFT>::uintX_t uintX_t;
 
   bool shouldTailMerge() const;
 

ELF/OutputSections.cpp

 
 template <class ELFT> void EhFrameHeader<ELFT>::reserveFde() {
   // Each FDE entry is 8 bytes long:
   // The first four bytes are an offset to the initial PC value for the FDE. The
   // last four byte are an offset to the FDE data itself.
   this->Header.sh_size += 8;
 }
 
+template <class ELFT> class lld::elf::ThunkChunk {
+  typedef typename llvm::object::ELFFile<ELFT>::uintX_t uintX_t;
+
+public:
+  uintX_t OutSecOff = 0;
+
+  void addThunk(SymbolBody &S) {
+    S.ThunkIndex = Thunks.size();
+    Thunks.push_back(&S);
+  }
+
+  size_t getSize() const { return Target->ThunkSize * Thunks.size(); }
+
+  void writeTo(uint8_t *Buf) {
+    Buf += OutSecOff;
+    for (SymbolBody *S : Thunks) {
+      Target->writeThunk(Buf, S->getVA<ELFT>());
+      Buf += Target->ThunkSize;
+    }
+  }
+
+private:
+  std::vector<SymbolBody *> Thunks;
+};
+
 template <class ELFT>
 OutputSection<ELFT>::OutputSection(StringRef Name, uint32_t Type, uintX_t Flags)
     : OutputSectionBase<ELFT>(Name, Type, Flags) {
   if (Type == SHT_RELA)
     this->Header.sh_entsize = sizeof(Elf_Rela);
   else if (Type == SHT_REL)
     this->Header.sh_entsize = sizeof(Elf_Rel);
 }

 
 template <class ELFT>
 void OutputSection<ELFT>::addSection(InputSectionBase<ELFT> *C) {
   assert(C->Live);
   auto *S = cast<InputSection<ELFT>>(C);
   Sections.push_back(S);
   S->OutSec = this;
   this->updateAlign(S->Align);
+}
 
-  uintX_t Off = this->Header.sh_size;
-  Off = alignTo(Off, S->Align);
-  S->OutSecOff = Off;
-  Off += S->getSize();
-  this->Header.sh_size = Off;
+template <class ELFT>
+void OutputSection<ELFT>::addThunk(const InputSectionBase<ELFT> &C,
+                                   SymbolBody &S) {
+  ThunkChunk<ELFT> *&TC = ThunkChunks[&C];
+  if (!TC)
+    TC = new (Alloc) ThunkChunk<ELFT>();
+  TC->addThunk(S);
+}
+
+template <class ELFT>
+typename OutputSection<ELFT>::uintX_t
+OutputSection<ELFT>::getThunkOffset(const InputSectionBase<ELFT> &S) {
+  ThunkChunk<ELFT> *TC = ThunkChunks.lookup(&S);
+  assert(TC);
+  return TC->OutSecOff;
 }
 
 // If an input string is in the form of "foo.N" where N is a number,
 // return N. Otherwise, returns 65536, which is one greater than the
 // lowest priority.
 static int getPriority(StringRef S) {
   size_t Pos = S.rfind('.');
   if (Pos == StringRef::npos)
     return 65536;
   int V;
   if (S.substr(Pos + 1).getAsInteger(10, V))
     return 65536;
   return V;
 }
 
 // This function is called after we sort input sections
-// to update their offsets.
-template <class ELFT> void OutputSection<ELFT>::reassignOffsets() {
+// to setup their offsets.
+template <class ELFT> void OutputSection<ELFT>::assignOffsets() {
   uintX_t Off = 0;
   for (InputSection<ELFT> *S : Sections) {
     Off = alignTo(Off, S->Align);
+    if (ThunkChunk<ELFT> * TC = ThunkChunks.lookup(S)) {
+      TC->OutSecOff = Off;
+      Off += TC->getSize();
+    }
+    Off = alignTo(Off, S->Align);
     S->OutSecOff = Off;
     Off += S->getSize();
   }
   this->Header.sh_size = Off;
 }
 
 // Sorts input sections by section name suffixes, so that .foo.N comes
 // before .foo.M if N < M. Used to sort .{init,fini}_array.N sections.
 // We want to keep the original order if the priorities are the same
 // because the compiler keeps the original initialization order in a
 // translation unit and we need to respect that.
 // For more detail, read the section of the GCC's manual about init_priority.
 template <class ELFT> void OutputSection<ELFT>::sortInitFini() {
   // Sort sections by priority.
   typedef std::pair<int, InputSection<ELFT> *> Pair;
   auto Comp = [](const Pair &A, const Pair &B) { return A.first < B.first; };
 
   std::vector<Pair> V;
   for (InputSection<ELFT> *S : Sections)
     V.push_back({getPriority(S->getSectionName()), S});
   std::stable_sort(V.begin(), V.end(), Comp);
   Sections.clear();
   for (Pair &P : V)
     Sections.push_back(P.second);
-  reassignOffsets();
 }
 
 // Returns true if S matches /Filename.?\.o$/.
 static bool isCrtBeginEnd(StringRef S, StringRef Filename) {
   if (!S.endswith(".o"))
     return false;
   S = S.drop_back(2);
   if (S.endswith(Filename))
static bool compCtors(const InputSection<ELFT> *A,
   return X < Y;
 }
 
 // Sorts input sections by the special rules for .ctors and .dtors.
 // Unfortunately, the rules are different from the one for .{init,fini}_array.
 // Read the comment above.
 template <class ELFT> void OutputSection<ELFT>::sortCtorsDtors() {
   std::stable_sort(Sections.begin(), Sections.end(), compCtors<ELFT>);
-  reassignOffsets();
 }
 
 // Returns true if a symbol can be replaced at load-time by a symbol
 // with the same name defined in other ELF executable or DSO.
 bool elf::canBePreempted(const SymbolBody &Body) {
   if (Body.isLocal())
     return false;
 
for (; I + A.size() < Size; I += A.size())
     memcpy(Buf + I, A.data(), A.size());
   memcpy(Buf + I, A.data(), Size - I);
 }
 
 template <class ELFT> void OutputSection<ELFT>::writeTo(uint8_t *Buf) {
   ArrayRef<uint8_t> Filler = Script->getFiller(this->Name);
   if (!Filler.empty())
     fill(Buf, this->getSize(), Filler);
-  if (Config->Threads) {
-    parallel_for_each(Sections.begin(), Sections.end(),
-                      [=](InputSection<ELFT> *C) { C->writeTo(Buf); });
-  } else {
-    for (InputSection<ELFT> *C : Sections)
-      C->writeTo(Buf);
-  }
+  auto WriteSection = [=](InputSection<ELFT> *C) {
+    if (ThunkChunk<ELFT> *TC = ThunkChunks.lookup(C))
+      TC->writeTo(Buf);
+  };
+  if (Config->Threads)
+    parallel_for_each(Sections.begin(), Sections.end(), WriteSection);
+  else
+    std::for_each(Sections.begin(), Sections.end(), WriteSection);
 }
 
 template <class ELFT>
 EHOutputSection<ELFT>::EHOutputSection(StringRef Name, uint32_t Type,
                                        uintX_t Flags)
     : OutputSectionBase<ELFT>(Name, Type, Flags) {
   Out<ELFT>::EhFrameHdr->assignEhFrame(this);
 }

ELF/Symbols.h

public:
 
   uint8_t getVisibility() const { return Visibility; }
 
   unsigned DynsymIndex = 0;
   uint32_t GlobalDynIndex = -1;
   uint32_t GotIndex = -1;
   uint32_t GotPltIndex = -1;
   uint32_t PltIndex = -1;
+  uint32_t ThunkIndex = -1;
   bool hasGlobalDynIndex() { return GlobalDynIndex != uint32_t(-1); }
   bool isInGot() const { return GotIndex != -1U; }
   bool isInPlt() const { return PltIndex != -1U; }
+  bool hasThunk() const { return ThunkIndex != -1U; }
 
   template <class ELFT>
   typename llvm::object::ELFFile<ELFT>::uintX_t
   getVA(typename llvm::object::ELFFile<ELFT>::uintX_t Addend = 0) const;
   template <class ELFT>
   typename llvm::object::ELFFile<ELFT>::uintX_t getGotVA() const;
   template <class ELFT>
   typename llvm::object::ELFFile<ELFT>::uintX_t getGotPltVA() const;
   template <class ELFT>
   typename llvm::object::ELFFile<ELFT>::uintX_t getPltVA() const;
   template <class ELFT>
   typename llvm::object::ELFFile<ELFT>::uintX_t getSize() const;
+  template <class ELFT>
+  typename llvm::object::ELFFile<ELFT>::uintX_t getThunkVA() const;
 
   // A SymbolBody has a backreference to a Symbol. Originally they are
   // doubly-linked. A backreference will never change. But the pointer
   // in the Symbol may be mutated by the resolver. If you have a
   // pointer P to a SymbolBody and are not sure whether the resolver
   // has chosen the object among other objects having the same name,
   // you can access P->Backref->Body to get the resolver's result.
   void setBackref(Symbol *P) { Backref = P; }
public:
   typedef typename llvm::object::ELFFile<ELFT>::uintX_t uintX_t;
   DefinedSynthetic(StringRef N, uintX_t Value, OutputSectionBase<ELFT> &Section,
                    uint8_t Visibility);
 
   static bool classof(const SymbolBody *S) {
     return S->kind() == SymbolBody::DefinedSyntheticKind;
   }
 
+  // Special value designates that the symbol 'points'
+  // to the end of the section.
+  static const uintX_t End = uintX_t(-1);
+
   uintX_t Value;
   const OutputSectionBase<ELFT> &Section;
 };
 
 // Undefined symbol.
 class Undefined : public SymbolBody {
   typedef SymbolBody::Kind Kind;
   bool CanKeepUndefined;

ELF/Symbols.cpp

 
 template <class ELFT>
 typename ELFFile<ELFT>::uintX_t SymbolBody::getSize() const {
   if (auto *B = dyn_cast<DefinedElf<ELFT>>(this))
     return B->Sym.st_size;
   return 0;
 }
 
+template <class ELFT>
+typename ELFFile<ELFT>::uintX_t SymbolBody::getThunkVA() const {
+  auto *S = cast<DefinedRegular<ELFT>>(this)->Section;
+  return S->OutSec->getVA() + S->OutSec->getThunkOffset(*S) +
+         ThunkIndex * Target->ThunkSize;
+}
+
 static uint8_t getMinVisibility(uint8_t VA, uint8_t VB) {
   if (VA == STV_DEFAULT)
     return VB;
   if (VB == STV_DEFAULT)
     return VA;
   return std::min(VA, VB);
 }
 

 template uint64_t SymbolBody::template getPltVA<ELF64LE>() const;
 template uint64_t SymbolBody::template getPltVA<ELF64BE>() const;
 
 template uint32_t SymbolBody::template getSize<ELF32LE>() const;
 template uint32_t SymbolBody::template getSize<ELF32BE>() const;
 template uint64_t SymbolBody::template getSize<ELF64LE>() const;
 template uint64_t SymbolBody::template getSize<ELF64BE>() const;
 
+template uint32_t SymbolBody::template getThunkVA<ELF32LE>() const;
+template uint32_t SymbolBody::template getThunkVA<ELF32BE>() const;
+template uint64_t SymbolBody::template getThunkVA<ELF64LE>() const;
+template uint64_t SymbolBody::template getThunkVA<ELF64BE>() const;
+
 template int SymbolBody::compare<ELF32LE>(SymbolBody *Other);
 template int SymbolBody::compare<ELF32BE>(SymbolBody *Other);
 template int SymbolBody::compare<ELF64LE>(SymbolBody *Other);
 template int SymbolBody::compare<ELF64BE>(SymbolBody *Other);
 
 template class elf::UndefinedElf<ELF32LE>;
 template class elf::UndefinedElf<ELF32BE>;
 template class elf::UndefinedElf<ELF64LE>;
 template class elf::UndefinedElf<ELF64BE>;
 
 template class elf::DefinedSynthetic<ELF32LE>;
 template class elf::DefinedSynthetic<ELF32BE>;
 template class elf::DefinedSynthetic<ELF64LE>;
 template class elf::DefinedSynthetic<ELF64BE>;

ELF/Target.h

 
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Object/ELF.h"
 
 #include <memory>
 
 namespace lld {
 namespace elf {
+class InputFile;
 class SymbolBody;
 
 class TargetInfo {
 public:
   uint64_t getVAStart() const;
   virtual bool isTlsInitialExecRel(uint32_t Type) const;
   virtual bool pointsToLocalDynamicGotEntry(uint32_t Type) const;
   virtual bool isTlsLocalDynamicRel(uint32_t Type) const;
public:
   virtual bool needsDynRelative(uint32_t Type) const { return false; }
   virtual bool needsGot(uint32_t Type, SymbolBody &S) const;
   virtual bool refersToGotEntry(uint32_t Type) const;
 
   enum PltNeed { Plt_No, Plt_Explicit, Plt_Implicit };
   template <class ELFT>
   PltNeed needsPlt(uint32_t Type, const SymbolBody &S) const;
 
+  virtual bool needsThunk(uint32_t Type, const InputFile &File,
+                          const SymbolBody &S) const;
+
+  virtual void writeThunk(uint8_t *Buf, uint64_t S) const {}
+
   virtual void relocateOne(uint8_t *Loc, uint8_t *BufEnd, uint32_t Type,
                            uint64_t P, uint64_t SA, uint64_t ZA = 0,
                            uint8_t *PairedLoc = nullptr) const = 0;
   virtual bool isGotRelative(uint32_t Type) const;
   bool canRelaxTls(uint32_t Type, const SymbolBody *S) const;
   template <class ELFT>
   bool needsCopyRel(uint32_t Type, const SymbolBody &S) const;
   virtual size_t relaxTls(uint8_t *Loc, uint8_t *BufEnd, uint32_t Type,
public:
   uint32_t IRelativeRel;
   uint32_t TlsGotRel = 0;
   uint32_t TlsModuleIndexRel;
   uint32_t TlsOffsetRel;
   unsigned PltEntrySize = 8;
   unsigned PltZeroSize = 0;
   unsigned GotHeaderEntriesNum = 0;
   unsigned GotPltHeaderEntriesNum = 3;
+  uint32_t ThunkSize = 0;
   bool UseLazyBinding = false;
 
 private:
   virtual bool needsCopyRelImpl(uint32_t Type) const;
   virtual bool needsPltImpl(uint32_t Type) const;
 };
 
 uint64_t getPPC64TocBase();

ELF/Target.cpp

 //
 // Refer the ELF spec for the single letter varaibles, S, A or P, used
 // in this file. SA is S+A.
 //
 //===----------------------------------------------------------------------===//
 
 #include "Target.h"
 #include "Error.h"
+#include "InputFiles.h"
 #include "OutputSections.h"
 #include "Symbols.h"
 
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/Object/ELF.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/ELF.h"
 

 public:
   MipsTargetInfo();
   uint32_t getDynRel(uint32_t Type) const override;
   void writeGotPlt(uint8_t *Buf, uint64_t Plt) const override;
   void writePltZero(uint8_t *Buf) const override;
   void writePlt(uint8_t *Buf, uint64_t GotEntryAddr, uint64_t PltEntryAddr,
                 int32_t Index, unsigned RelOff) const override;
   void writeGotHeader(uint8_t *Buf) const override;
+  void writeThunk(uint8_t *Buf, uint64_t S) const override;
   bool needsCopyRelImpl(uint32_t Type) const override;
   bool needsGot(uint32_t Type, SymbolBody &S) const override;
   bool needsPltImpl(uint32_t Type) const override;
+  bool needsThunk(uint32_t Type, const InputFile &File,
+                  const SymbolBody &S) const override;
   void relocateOne(uint8_t *Loc, uint8_t *BufEnd, uint32_t Type, uint64_t P,
                    uint64_t S, uint64_t ZA = 0,
                    uint8_t *PairedLoc = nullptr) const override;
   bool isHintRel(uint32_t Type) const override;
   bool isRelRelative(uint32_t Type) const override;
   bool refersToGotEntry(uint32_t Type) const override;
 };
 } // anonymous namespace
TargetInfo::PltNeed TargetInfo::needsPlt(uint32_t Type,
   if (auto *SS = dyn_cast<SharedSymbol<ELFT>>(&S))
     if (!Config->Shared && SS->Sym.getType() == STT_FUNC &&
         !refersToGotEntry(Type))
       return Plt_Implicit;
 
   return Plt_No;
 }
 
+bool TargetInfo::needsThunk(uint32_t Type, const InputFile &File,
+                            const SymbolBody &S) const {
+  return false;
+}
+
 bool TargetInfo::isTlsInitialExecRel(uint32_t Type) const { return false; }
 
 bool TargetInfo::pointsToLocalDynamicGotEntry(uint32_t Type) const {
   return false;
 }
 
 bool TargetInfo::isTlsLocalDynamicRel(uint32_t Type) const { return false; }
 

 }
 
 template <class ELFT> MipsTargetInfo<ELFT>::MipsTargetInfo() {
   GotHeaderEntriesNum = 2;
   GotPltHeaderEntriesNum = 2;
   PageSize = 65536;
   PltEntrySize = 16;
   PltZeroSize = 32;
+  ThunkSize = 16;
   UseLazyBinding = true;
   CopyRel = R_MIPS_COPY;
   PltRel = R_MIPS_JUMP_SLOT;
   RelativeRel = R_MIPS_REL32;
 }
 
 template <class ELFT>
 uint32_t MipsTargetInfo<ELFT>::getDynRel(uint32_t Type) const {
void MipsTargetInfo<ELFT>::writePlt(uint8_t *Buf, uint64_t GotEntryAddr,
   write32<E>(Buf + 4, 0x8df90000);  // l[wd] $25, %lo(.got.plt entry)($15)
   write32<E>(Buf + 8, 0x03200008);  // jr    $25
   write32<E>(Buf + 12, 0x25f80000); // addiu $24, $15, %lo(.got.plt entry)
   writeMipsHi16<E>(Buf, GotEntryAddr);
   writeMipsLo16<E>(Buf + 4, GotEntryAddr);
   writeMipsLo16<E>(Buf + 12, GotEntryAddr);
 }
 
 template <class ELFT>
+void MipsTargetInfo<ELFT>::writeThunk(uint8_t *Buf, uint64_t S) const {
+  // Any MIPS PIC code function is invoked with its address in register $t9.
+  // So if we have a branch instruction from non-PIC code to the PIC one we
+  // cannot make the jump directly and need to create a stub to save the target
+  // function address.
+  // See page 3-38 ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf
+  const endianness E = ELFT::TargetEndianness;
+  write32<E>(Buf, 0x3c190000);      // lui   $25, %hi(func)
+  write32<E>(Buf + 4, 0x08000000);  // j     func
+  write32<E>(Buf + 8, 0x27390000);  // addiu $25, $25, %lo(func)
+  write32<E>(Buf + 12, 0x00000000); // nop
+  writeMipsHi16<E>(Buf, S);
+  write32<E>(Buf + 4, 0x08000000 | (S >> 2));
+  writeMipsLo16<E>(Buf + 8, S);
+}
+
+template <class ELFT>
 bool MipsTargetInfo<ELFT>::needsCopyRelImpl(uint32_t Type) const {
   return !isRelRelative(Type);
 }
 
 template <class ELFT>
 bool MipsTargetInfo<ELFT>::needsGot(uint32_t Type, SymbolBody &S) const {
   return needsPlt<ELFT>(Type, S) || refersToGotEntry(Type);
 }
 
 template <class ELFT>
 bool MipsTargetInfo<ELFT>::refersToGotEntry(uint32_t Type) const {
   return Type == R_MIPS_GOT16 || Type == R_MIPS_CALL16;
 }
 
 template <class ELFT>
 bool MipsTargetInfo<ELFT>::needsPltImpl(uint32_t Type) const {
   return Type == R_MIPS_26;
 }
 
 template <class ELFT>
+bool MipsTargetInfo<ELFT>::needsThunk(uint32_t Type, const InputFile &File,
+                                      const SymbolBody &S) const {
+  // Any MIPS PIC code function is invoked with its address in register $t9.
+  // So if we have a branch instruction from non-PIC code to the PIC one
+  // we cannot make the jump directly and need to create a small stubs
+  // to save the target function address.
+  // See page 3-38 ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf
+  if (Type != R_MIPS_26)
+    return false;
+  auto *F = dyn_cast<ELFFileBase<ELFT>>(&File);
+  if (!F)
+    return false;
+  // If current file has PIC code, LA25 stub is not required.
+  if (F->getObj().getHeader()->e_flags & EF_MIPS_PIC)
+    return false;
+  auto *D = dyn_cast<DefinedRegular<ELFT>>(&S);
+  if (!D || !D->Section)
+    return false;
+  // LA25 is required if target file has PIC code
+  // or target symbol is a PIC symbol.
+  return (D->Section->getFile()->getObj().getHeader()->e_flags & EF_MIPS_PIC) ||
+         (D->Sym.st_other & STO_MIPS_MIPS16) == STO_MIPS_PIC;
+}
+
+template <class ELFT>
 void MipsTargetInfo<ELFT>::relocateOne(uint8_t *Loc, uint8_t *BufEnd,
                                        uint32_t Type, uint64_t P, uint64_t S,
                                        uint64_t ZA, uint8_t *PairedLoc) const {
   const endianness E = ELFT::TargetEndianness;
   switch (Type) {
   case R_MIPS_32:
     add32<E>(Loc, S);
     break;
   case R_MIPS_26: {

ELF/Writer.cpp

 // * Write the allocated output sections, computing addresses.
 // * Apply relocations, recording which ones require a dynamic reloc.
 // * Write the dynamic relocations.
 // * Write the rest of the file.
 // This would have some drawbacks. For example, we would only know if .rela.dyn
 // is needed after applying relocations. If it is, it will go after rw and rx
 // sections. Given that it is ro, we will need an extra PT_LOAD. This
 // complicates things for the dynamic linker and means we would have to reserve
 // space for the extra PT_LOAD even if we end up not using it.
 template <class ELFT>
 template <bool isRela>
 void Writer<ELFT>::scanRelocs(
     InputSectionBase<ELFT> &C,
     iterator_range<const Elf_Rel_Impl<ELFT, isRela> *> Rels) {
   typedef Elf_Rel_Impl<ELFT, isRela> RelType;
   const ObjectFile<ELFT> &File = *C.getFile();
   for (const RelType &RI : Rels) {
for (const RelType &RI : Rels) {
     // MIPS has a special rule to create GOTs for local symbols.
     if (Config->EMachine == EM_MIPS && !CBP &&
         (Type == R_MIPS_GOT16 || Type == R_MIPS_CALL16)) {
       // FIXME (simon): Do not add so many redundant entries.
       Out<ELFT>::Got->addMipsLocalEntry();
       continue;
     }
 
     // If a symbol in a DSO is referenced directly instead of through GOT,
     // we need to create a copy relocation for the symbol.
     if (auto *B = dyn_cast_or_null<SharedSymbol<ELFT>>(&Body)) {
       if (B->needsCopy())
         continue;
       if (Target->needsCopyRel<ELFT>(Type, *B)) {
         B->NeedsCopyOrPltAddr = true;
         Out<ELFT>::RelaDyn->addReloc(
             {Target->CopyRel, DynamicReloc<ELFT>::Off_Bss, B});
         continue;
       }
     }
 
     // An STT_GNU_IFUNC symbol always uses a PLT entry, and all references
     // to the symbol go through the PLT. This is true even for a local
if (Config->EMachine == EM_PPC64 && RI.getType(false) == R_PPC64_TOC) {
       Out<ELFT>::RelaDyn->addReloc({R_PPC64_RELATIVE, &C, RI.r_offset, false,
                                     nullptr,
                                     (uintX_t)getPPC64TocBase() + Addend});
       continue;
     }
     Out<ELFT>::RelaDyn->addReloc(
         {Target->RelativeRel, &C, RI.r_offset, true, &Body, Addend});
   }
+
+  // Some targets might require creation of thunk for relocations.
+  // For example, MIPS needs LA25 thunk to local call PIC code from non-PIC.
+  for (const RelType &RI : Rels) {
+    uint32_t Type = RI.getType(Config->Mips64EL);
+    uint32_t SymIndex = RI.getSymbol(Config->Mips64EL);
+    SymbolBody &Body = File.getSymbolBody(SymIndex).repl();
+
+    if (!Body.hasThunk() && Target->needsThunk(Type, File, Body)) {
+      const InputSectionBase<ELFT> *Section =
+          cast<DefinedRegular<ELFT>>(&Body)->Section;
+      Section->OutSec->addThunk(*Section, Body);
+    }
+  }
 }
 
 template <class ELFT> void Writer<ELFT>::scanRelocs(InputSection<ELFT> &C) {
   if (C.getSectionHdr()->sh_flags & SHF_ALLOC)
     for (const Elf_Shdr *RelSec : C.RelocSections)
       scanRelocs(C, *RelSec);
 }
 
for (InputSectionBase<ELFT> *C : F->getSections()) {
       if (auto *S = dyn_cast<InputSection<ELFT>>(C))
         scanRelocs(*S);
       else if (auto *S = dyn_cast<EHInputSection<ELFT>>(C))
         if (S->RelocSection)
           scanRelocs(*S, *S->RelocSection);
     }
   }
 
+  for (OutputSectionBase<ELFT> *Sec : getSections())
+    Sec->assignOffsets();
+
   // Now that we have defined all possible symbols including linker-
   // synthesized ones. Visit all symbols to give the finishing touches.
   std::vector<DefinedCommon *> CommonSymbols;
   std::vector<SharedSymbol<ELFT> *> CopyRelSymbols;
   for (auto &P : Symtab.getSymbols()) {
     SymbolBody *Body = P.second->Body;
     if (auto *U = dyn_cast<Undefined>(Body))
       if (!U->isWeak() && !U->canKeepUndefined())
         reportUndefined<ELFT>(Symtab, Body);
 
     if (auto *C = dyn_cast<DefinedCommon>(Body))
       CommonSymbols.push_back(C);
     if (auto *SC = dyn_cast<SharedSymbol<ELFT>>(Body))
       if (SC->needsCopy())
         CopyRelSymbols.push_back(SC);
+    if (auto *SS = dyn_cast<DefinedSynthetic<ELFT>>(Body))
+      // Setup values of synthetic symbols that need
+      // to point to end of a section.
+      if (SS->Value == DefinedSynthetic<ELFT>::End)
+        SS->Value = SS->Section.getSize();
 
     if (!includeInSymtab<ELFT>(*Body))
       continue;
     if (Out<ELFT>::SymTab)
       Out<ELFT>::SymTab->addSymbol(Body);
 
     if (isOutputDynamic() && includeInDynsym(*Body))
       Out<ELFT>::DynSymTab->addSymbol(Body);

 
 // The linker is expected to define SECNAME_start and SECNAME_end
 // symbols for a few sections. This function defines them.
 template <class ELFT> void Writer<ELFT>::addStartEndSymbols() {
   auto Define = [&](StringRef Start, StringRef End,
                     OutputSectionBase<ELFT> *OS) {
     if (OS) {
       Symtab.addSynthetic(Start, *OS, 0, STV_DEFAULT);
-      Symtab.addSynthetic(End, *OS, OS->getSize(), STV_DEFAULT);
+      Symtab.addSynthetic(End, *OS, DefinedSynthetic<ELFT>::End, STV_DEFAULT);
     } else {
       Symtab.addIgnored(Start);
       Symtab.addIgnored(End);
     }
   };
 
   Define("__preinit_array_start", "__preinit_array_end",
          Out<ELFT>::Dynamic->PreInitArraySec);
void Writer<ELFT>::addStartStopSymbols(OutputSectionBase<ELFT> *Sec) {
   StringSaver Saver(Alloc);
   StringRef Start = Saver.save("__start_" + S);
   StringRef Stop = Saver.save("__stop_" + S);
   if (SymbolBody *B = Symtab.find(Start))
     if (B->isUndefined())
       Symtab.addSynthetic(Start, *Sec, 0, STV_DEFAULT);
   if (SymbolBody *B = Symtab.find(Stop))
     if (B->isUndefined())
-      Symtab.addSynthetic(Stop, *Sec, Sec->getSize(), STV_DEFAULT);
+      Symtab.addSynthetic(Stop, *Sec, DefinedSynthetic<ELFT>::End, STV_DEFAULT);
 }
 
 template <class ELFT> static bool needsPtLoad(OutputSectionBase<ELFT> *Sec) {
   if (!(Sec->getFlags() & SHF_ALLOC))
     return false;
 
   // Don't allocate VA space for TLS NOBITS sections. The PT_TLS PHDR is
   // responsible for allocating space for them, not the PT_LOAD that

test/ELF/Inputs/mips-pic.s

+  .option pic2
+
+  .section .text.1,"ax",@progbits
+  .align 4
+  .globl foo1a
+  .type foo1a, @function
+foo1a:
+  nop
+  .globl foo1b
+  .type foo1b, @function
+foo1b:
+  nop
+
+  .section .text.2,"ax",@progbits
+  .align 4
+  .globl foo2
+  .type foo2, @function
+foo2:
+  nop

test/ELF/mips-npic-call-pic.s

+# Check LA25 stubs creation. This stub code is necessary when
+# non-PIC code calls PIC function.
+
+# RUN: llvm-mc -filetype=obj -triple=mips-unknown-linux \
+# RUN:   %p/Inputs/mips-pic.s -o %t-pic.o
+# RUN: llvm-mc -filetype=obj -triple=mips-unknown-linux %s -o %t-npic.o
+# RUN: ld.lld %t-npic.o %t-pic.o -o %t.exe
+# RUN: llvm-objdump -d %t.exe | FileCheck %s
+
+# REQUIRES: mips
+
+# CHECK:     Disassembly of section .text:
+# CHECK-NEXT: __start:
+# CHECK-NEXT:    20000:       0c 00 80 08     jal     131104
+#                                                     ^-- 0x20020 .pic.foo1a
+# CHECK-NEXT:    20004:       00 00 00 00     nop
+# CHECK-NEXT:    20008:       0c 00 80 14     jal     131152
+#                                                     ^-- 0x20050 .pic.foo2
+# CHECK-NEXT:    2000c:       00 00 00 00     nop
+# CHECK-NEXT:    20010:       0c 00 80 0c     jal     131120
+#                                                     ^-- 0x20030 .pic.foo1b
+# CHECK-NEXT:    20014:       00 00 00 00     nop
+# CHECK-NEXT:    20018:       0c 00 80 14     jal     131152
+#                                                     ^-- 0x20050 .pic.foo2
+# CHECK-NEXT:    2001c:       00 00 00 00     nop
+# CHECK-NEXT:    20020:       3c 19 00 02     lui     $25, 2
+# CHECK-NEXT:    20024:       08 00 80 10     j       131136
+#                                                     ^-- 0x20040 foo1a
+# CHECK-NEXT:    20028:       27 39 00 40     addiu   $25, $25, 64
+# CHECK-NEXT:    2002c:       00 00 00 00     nop
+# CHECK-NEXT:    20030:       3c 19 00 02     lui     $25, 2
+# CHECK-NEXT:    20034:       08 00 80 11     j       131140
+#                                                     ^-- 0x20044 foo1b
+# CHECK-NEXT:    20038:       27 39 00 44     addiu   $25, $25, 68
+# CHECK-NEXT:    2003c:       00 00 00 00     nop
+#
+# CHECK:      foo1a:
+# CHECK-NEXT:    20040:       00 00 00 00     nop
+#
+# CHECK:      foo1b:
+# CHECK-NEXT:    20044:       00 00 00 00     nop
+# CHECK-NEXT:    20048:       00 00 00 00     nop
+# CHECK-NEXT:    2004c:       00 00 00 00     nop
+# CHECK-NEXT:    20050:       3c 19 00 02     lui     $25, 2
+# CHECK-NEXT:    20054:       08 00 80 18     j       131168
+#                                                     ^-- 0x20060 foo2
+# CHECK-NEXT:    20058:       27 39 00 60     addiu   $25, $25, 96
+# CHECK-NEXT:    2005c:       00 00 00 00     nop
+#
+# CHECK:      foo2:
+# CHECK-NEXT:    20060:       00 00 00 00     nop
+
+  .text
+  .globl __start
+__start:
+  jal foo1a
+  jal foo2
+  jal foo1b
+  jal foo2