Create thunks before regular relocation scan

[• rafael]

Summary

We will need to do something like this to support range extension
thunks since that process is iterative.

Doing this also has the advantage that when doing the regular
relocation scan the offset in the output section is known and we can
just store that. This reduces the number of times we have to run
getOffset and I think will allow a more specialized .eh_frame
representation.

By itself this is already a performance win.

firefox

master 7.295045737
patch  7.209466989 0.98826892235

chromium

master 4.531254468
patch  4.509221804 0.995137623774

chromium fast

master 1.836928973
patch  1.823805241 0.992855612714

the gold plugin

master 0.379768791
patch  0.380043405 1.00072310839

clang

master 0.642698284
patch  0.642215663 0.999249070657

llvm-as

master 0.036665467
patch  0.036456225 0.994293213284

the gold plugin fsds

master 0.40395817
patch  0.404384555 1.0010555177

clang fsds

master 0.722045545
patch  0.720946135 0.998477367518

llvm-as fsds

master 0.03292646
patch  0.032759965 0.994943428477

scylla

master 3.427376378
patch  3.368316181 0.98276810292

Cheers,
Rafael

[ruiu]

LGTM

ELF/Relocations.cpp

552

Please add a comment for this block of code.

557

You don't need ().

693

RI is short for relocation iterator, so Rel would be a better name.

[peter.smith]

Looks good to me too. I think splitting out thunk creation is the right thing to do.

Range extension thunks are likely to need some changes in order as the generation of any content by scanRelocations could in theory affect the decision on whether a range extension thunk is needed. However that is best resolved at the time range extension thunks are implemented.

[Eugene.Zelenko]

Committed in r276146.

ELF/InputSection.cpp

for (const Elf_Shdr *RelSec : IS->RelocSections) {
       else
         IS->relocateNonAlloc(Buf, IS->File->getObj().rels(RelSec));
     }
     return;
   }
 
   const unsigned Bits = sizeof(uintX_t) * 8;
   for (const Relocation<ELFT> &Rel : Relocations) {
-    uintX_t Offset = Rel.InputSec->getOffset(Rel.Offset);
+    uintX_t Offset = Rel.Offset;
     uint8_t *BufLoc = Buf + Offset;
     uint32_t Type = Rel.Type;
     uintX_t A = Rel.Addend;
 
     uintX_t AddrLoc = OutSec->getVA() + Offset;
     RelExpr Expr = Rel.Expr;
     uint64_t SymVA =
         SignExtend64<Bits>(getSymVA<ELFT>(Type, A, AddrLoc, *Rel.Sym, Expr));

ELF/OutputSections.cpp

for (StringRef S : Strings) {
     Buf += S.size() + 1;
   }
 }
 
 template <class ELFT>
 typename ELFT::uint DynamicReloc<ELFT>::getOffset() const {
   if (OutputSec)
     return OutputSec->getVA() + OffsetInSec;
-  return InputSec->OutSec->getVA() + InputSec->getOffset(OffsetInSec);
+  return InputSec->OutSec->getVA() + OffsetInSec;
 }
 
 template <class ELFT>
 typename ELFT::uint DynamicReloc<ELFT>::getAddend() const {
   if (UseSymVA)
     return Sym->getVA<ELFT>(Addend);
   return Addend;
 }

ELF/Relocations.h

template <class ELFT> struct Relocation {
   RelExpr Expr;
   uint32_t Type;
   InputSectionBase<ELFT> *InputSec;
   uint64_t Offset;
   uint64_t Addend;
   SymbolBody *Sym;
 };
 
-template <class ELFT> void scanRelocations(InputSection<ELFT> &);
-
 template <class ELFT>
 void scanRelocations(InputSectionBase<ELFT> &, const typename ELFT::Shdr &);
 
 template <class ELFT>
+void createThunks(InputSectionBase<ELFT> &, const typename ELFT::Shdr &);
+
+template <class ELFT>
 static inline typename ELFT::uint getAddend(const typename ELFT::Rel &Rel) {
   return 0;
 }
 
 template <class ELFT>
 static inline typename ELFT::uint getAddend(const typename ELFT::Rela &Rel) {
   return Rel.r_addend;
 }
 }
 }
 
 #endif

ELF/Relocations.cpp

for (auto I = Rels.begin(), E = Rels.end(); I != E; ++I) {
     if (HasError)
       continue;
 
     // Skip a relocation that points to a dead piece
     // in a eh_frame section.
     while (PieceI != PieceE &&
            (PieceI->InputOff + PieceI->size() <= RI.r_offset))
       ++PieceI;
-    if (PieceI != PieceE && PieceI->InputOff <= RI.r_offset &&
-        PieceI->OutputOff == (uintX_t)-1)
+
+    uintX_t Offset;
+    if (PieceI != PieceE) {
+      assert(PieceI->InputOff <= RI.r_offset && "Relocation not in any piece");
+      if (PieceI->OutputOff == (uintX_t)-1)
         continue;
+      Offset = PieceI->OutputOff + (RI.r_offset - PieceI->InputOff);
+      assert(Offset == C.getOffset(RI.r_offset));
+    } else {
+      Offset = C.getOffset(RI.r_offset);
+    }
 
     // This relocation does not require got entry, but it is relative to got and
     // needs it to be created. Here we request for that.
     if (Expr == R_GOTONLY_PC || Expr == R_GOTREL || Expr == R_PPC_TOC)
       Out<ELFT>::Got->HasGotOffRel = true;
 
     uintX_t Addend = computeAddend(File, Buf, E, RI, Expr, Body);
 
-    if (unsigned Processed = handleTlsRelocation<ELFT>(
-            Type, Body, C, RI.r_offset, Addend, Expr)) {
+    if (unsigned Processed =
+            handleTlsRelocation<ELFT>(Type, Body, C, Offset, Addend, Expr)) {
       I += (Processed - 1);
       continue;
     }
 
     // Ignore "hint" relocation because it is for optional code optimization.
     if (Expr == R_HINT)
       continue;
 
     if (needsPlt(Expr) || Expr == R_THUNK_ABS || Expr == R_THUNK_PC ||
         Expr == R_THUNK_PLT_PC || refersToGotEntry(Expr) ||
         !isPreemptible(Body, Type)) {
       // If the relocation points to something in the file, we can process it.
       bool Constant = isStaticLinkTimeConstant<ELFT>(Expr, Type, Body);
 
       // If the output being produced is position independent, the final value
       // is still not known. In that case we still need some help from the
       // dynamic linker. We can however do better than just copying the incoming
       // relocation. We can process some of it and and just ask the dynamic
       // linker to add the load address.
       if (!Constant)
-        AddDyn({Target->RelativeRel, &C, RI.r_offset, true, &Body, Addend});
+        AddDyn({Target->RelativeRel, &C, Offset, true, &Body, Addend});
 
       // If the produced value is a constant, we just remember to write it
       // when outputting this section. We also have to do it if the format
       // uses Elf_Rel, since in that case the written value is the addend.
       if (Constant || !RelTy::IsRela)
-        C.Relocations.push_back({Expr, Type, &C, RI.r_offset, Addend, &Body});
+        C.Relocations.push_back({Expr, Type, &C, Offset, Addend, &Body});
     } else {
       // We don't know anything about the finaly symbol. Just ask the dynamic
       // linker to handle the relocation for us.
-      AddDyn({Target->getDynRel(Type), &C, RI.r_offset, false, &Body, Addend});
+      AddDyn({Target->getDynRel(Type), &C, Offset, false, &Body, Addend});
       // MIPS ABI turns using of GOT and dynamic relocations inside out.
       // While regular ABI uses dynamic relocations to fill up GOT entries
       // MIPS ABI requires dynamic linker to fills up GOT entries using
       // specially sorted dynamic symbol table. This affects even dynamic
       // relocations against symbols which do not require GOT entries
       // creation explicitly, i.e. do not have any GOT-relocations. So if
       // a preemptible symbol has a dynamic relocation we anyway have
       // to create a GOT entry for it.
       // If a non-preemptible symbol has a dynamic relocation against it,
       // dynamic linker takes it st_value, adds offset and writes down
       // result of the dynamic relocation. In case of preemptible symbol
       // dynamic linker performs symbol resolution, writes the symbol value
       // to the GOT entry and reads the GOT entry when it needs to perform
       // a dynamic relocation.
       // ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf p.4-19
       if (Config->EMachine == EM_MIPS)
         Out<ELFT>::Got->addMipsEntry(Body, Addend, Expr);
       continue;
     }
 
-    // Some targets might require creation of thunks for relocations.
-    // Now we support only MIPS which requires LA25 thunk to call PIC
-    // code from non-PIC one, and ARM which requires interworking.
-    if (Expr == R_THUNK_ABS || Expr == R_THUNK_PC || Expr == R_THUNK_PLT_PC) {
-      auto *Sec = cast<InputSection<ELFT>>(&C);
-      addThunk<ELFT>(Type, Body, *Sec);
-    }
-
     // At this point we are done with the relocated position. Some relocations
     // also require us to create a got or plt entry.
 
     // If a relocation needs PLT, we create a PLT and a GOT slot for the symbol.
     if (needsPlt(Expr)) {
       if (Body.isInPlt())
         continue;
       Out<ELFT>::Plt->addEntry(Body);
if (refersToGotEntry(Expr)) {
         AddDyn({DynType, Out<ELFT>::Got, Body.getGotOffset<ELFT>(),
                 !Preemptible, &Body, 0});
       }
       continue;
     }
   }
 }
 
-template <class ELFT> void scanRelocations(InputSection<ELFT> &C) {
-  typedef typename ELFT::Shdr Elf_Shdr;
-
-  // Scan all relocations. Each relocation goes through a series
-  // of tests to determine if it needs special treatment, such as
-  // creating GOT, PLT, copy relocations, etc.
-  // Note that relocations for non-alloc sections are directly
-  // processed by InputSection::relocateNonAlloc.
-  if (C.getSectionHdr()->sh_flags & SHF_ALLOC)
-    for (const Elf_Shdr *RelSec : C.RelocSections)
-      scanRelocations(C, *RelSec);
-}
-
 template <class ELFT>
 void scanRelocations(InputSectionBase<ELFT> &S,
                      const typename ELFT::Shdr &RelSec) {
   ELFFile<ELFT> &EObj = S.getFile()->getObj();
   if (RelSec.sh_type == SHT_RELA)
     scanRelocs(S, EObj.relas(&RelSec));
   else
     scanRelocs(S, EObj.rels(&RelSec));
 }
 
-template void scanRelocations<ELF32LE>(InputSection<ELF32LE> &);
-template void scanRelocations<ELF32BE>(InputSection<ELF32BE> &);
-template void scanRelocations<ELF64LE>(InputSection<ELF64LE> &);
-template void scanRelocations<ELF64BE>(InputSection<ELF64BE> &);
+template <class ELFT, class RelTy>
+static void createThunks(InputSectionBase<ELFT> &C, ArrayRef<RelTy> Rels) {
+  const elf::ObjectFile<ELFT> &File = *C.getFile();
+  for (auto I = Rels.begin(), E = Rels.end(); I != E; ++I) {
+    const RelTy &RI = *I;
+    SymbolBody &Body = File.getRelocTargetSym(RI);
+    uint32_t Type = RI.getType(Config->Mips64EL);
+    RelExpr Expr = Target->getRelExpr(Type, Body);
+    if (!isPreemptible(Body, Type) && needsPlt(Expr))
+      Expr = fromPlt(Expr);
+    Expr = Target->getThunkExpr(Expr, Type, File, Body);
+    // Some targets might require creation of thunks for relocations.
+    // Now we support only MIPS which requires LA25 thunk to call PIC
+    // code from non-PIC one, and ARM which requires interworking.
+    if (Expr == R_THUNK_ABS || Expr == R_THUNK_PC || Expr == R_THUNK_PLT_PC) {
+      auto *Sec = cast<InputSection<ELFT>>(&C);
+      addThunk<ELFT>(Type, Body, *Sec);
+    }
+  }
+}
+
+template <class ELFT>
+void createThunks(InputSectionBase<ELFT> &S,
+                  const typename ELFT::Shdr &RelSec) {
+  ELFFile<ELFT> &EObj = S.getFile()->getObj();
+  if (RelSec.sh_type == SHT_RELA)
+    createThunks(S, EObj.relas(&RelSec));
+  else
+    createThunks(S, EObj.rels(&RelSec));
+}
 
 template void scanRelocations<ELF32LE>(InputSectionBase<ELF32LE> &,
                                        const ELF32LE::Shdr &);
 template void scanRelocations<ELF32BE>(InputSectionBase<ELF32BE> &,
                                        const ELF32BE::Shdr &);
 template void scanRelocations<ELF64LE>(InputSectionBase<ELF64LE> &,
                                        const ELF64LE::Shdr &);
 template void scanRelocations<ELF64BE>(InputSectionBase<ELF64BE> &,
                                        const ELF64BE::Shdr &);
+
+template void createThunks<ELF32LE>(InputSectionBase<ELF32LE> &,
+                                    const ELF32LE::Shdr &);
+template void createThunks<ELF32BE>(InputSectionBase<ELF32BE> &,
+                                    const ELF32BE::Shdr &);
+template void createThunks<ELF64LE>(InputSectionBase<ELF64LE> &,
+                                    const ELF64LE::Shdr &);
+template void createThunks<ELF64BE>(InputSectionBase<ELF64BE> &,
+                                    const ELF64BE::Shdr &);
 }
 }

ELF/Target.h

public:
 
   // At least on x86_64 positions 1 and 2 are used by the first plt entry
   // to support lazy loading.
   unsigned GotPltHeaderEntriesNum = 3;
 
   // Set to 0 for variant 2
   unsigned TcbSize = 0;
 
+  bool NeedsThunks = false;
+
   virtual RelExpr adjustRelaxExpr(uint32_t Type, const uint8_t *Data,
                                   RelExpr Expr) const;
   virtual void relaxGot(uint8_t *Loc, uint64_t Val) const;
   virtual void relaxTlsGdToIe(uint8_t *Loc, uint32_t Type, uint64_t Val) const;
   virtual void relaxTlsGdToLe(uint8_t *Loc, uint32_t Type, uint64_t Val) const;
   virtual void relaxTlsIeToLe(uint8_t *Loc, uint32_t Type, uint64_t Val) const;
   virtual void relaxTlsLdToLe(uint8_t *Loc, uint32_t Type, uint64_t Val) const;
 };

ELF/Target.cpp

ARMTargetInfo::ARMTargetInfo() {
   TlsModuleIndexRel = R_ARM_TLS_DTPMOD32;
   TlsOffsetRel = R_ARM_TLS_DTPOFF32;
   GotEntrySize = 4;
   GotPltEntrySize = 4;
   PltEntrySize = 16;
   PltHeaderSize = 20;
   // ARM uses Variant 1 TLS
   TcbSize = 8;
+  NeedsThunks = true;
 }
 
 RelExpr ARMTargetInfo::getRelExpr(uint32_t Type, const SymbolBody &S) const {
   switch (Type) {
   default:
     return R_ABS;
   case R_ARM_THM_JUMP11:
     return R_PC;
template <class ELFT> MipsTargetInfo<ELFT>::MipsTargetInfo() {
   GotPltHeaderEntriesNum = 2;
   PageSize = 65536;
   GotEntrySize = sizeof(typename ELFT::uint);
   GotPltEntrySize = sizeof(typename ELFT::uint);
   PltEntrySize = 16;
   PltHeaderSize = 32;
   CopyRel = R_MIPS_COPY;
   PltRel = R_MIPS_JUMP_SLOT;
+  NeedsThunks = true;
   if (ELFT::Is64Bits) {
     RelativeRel = (R_MIPS_64 << 8) | R_MIPS_REL32;
     TlsGotRel = R_MIPS_TLS_TPREL64;
     TlsModuleIndexRel = R_MIPS_TLS_DTPMOD64;
     TlsOffsetRel = R_MIPS_TLS_DTPREL64;
   } else {
     RelativeRel = R_MIPS_REL32;
     TlsGotRel = R_MIPS_TLS_TPREL32;

ELF/Writer.cpp

public:
   void run();
 
 private:
   typedef PhdrEntry<ELFT> Phdr;
 
   void copyLocalSymbols();
   void addReservedSymbols();
   std::vector<std::unique_ptr<OutputSectionBase<ELFT>>> createSections();
+  void forEachRelSec(
+      std::function<void(InputSectionBase<ELFT> &, const typename ELFT::Shdr &)>
+          Fn);
   void finalizeSections();
   void addPredefinedSections();
   bool needsGot();
 
   void createPhdrs();
   void assignAddresses();
   void assignFileOffsets();
   void setPhdrs();

 
 // Sort input sections by the special rule for .ctors and .dtors.
 template <class ELFT> static void sortCtorsDtors(OutputSectionBase<ELFT> *S) {
   if (S)
     reinterpret_cast<OutputSection<ELFT> *>(S)->sortCtorsDtors();
 }
 
 template <class ELFT>
+void Writer<ELFT>::forEachRelSec(
+    std::function<void(InputSectionBase<ELFT> &, const typename ELFT::Shdr &)>
+        Fn) {
+  for (const std::unique_ptr<elf::ObjectFile<ELFT>> &F :
+       Symtab.getObjectFiles()) {
+    for (InputSectionBase<ELFT> *C : F->getSections()) {
+      if (isDiscarded(C))
+        continue;
+      // Scan all relocations. Each relocation goes through a series
+      // of tests to determine if it needs special treatment, such as
+      // creating GOT, PLT, copy relocations, etc.
+      // Note that relocations for non-alloc sections are directly
+      // processed by InputSection::relocateNonAlloc.
+      if (!(C->getSectionHdr()->sh_flags & SHF_ALLOC))
+        continue;
+      if (auto *S = dyn_cast<InputSection<ELFT>>(C)) {
+        for (const Elf_Shdr *RelSec : S->RelocSections)
+          Fn(*S, *RelSec);
+        continue;
+      }
+      if (auto *S = dyn_cast<EhInputSection<ELFT>>(C))
+        if (S->RelocSection)
+          Fn(*S, *S->RelocSection);
+    }
+  }
+}
+
+template <class ELFT>
 std::vector<std::unique_ptr<OutputSectionBase<ELFT>>>
 Writer<ELFT>::createSections() {
   std::vector<std::unique_ptr<OutputSectionBase<ELFT>>> Result;
 
   for (const std::unique_ptr<elf::ObjectFile<ELFT>> &F :
        Symtab.getObjectFiles()) {
     for (InputSectionBase<ELFT> *C : F->getSections()) {
       if (isDiscarded(C)) {
template <class ELFT> void Writer<ELFT>::finalizeSections() {
   // Real values will be assigned later
   Script<ELFT>::X->addScriptedSymbols();
 
   if (!Out<ELFT>::EhFrame->empty()) {
     OutputSections.push_back(Out<ELFT>::EhFrame);
     Out<ELFT>::EhFrame->finalize();
   }
 
-  // Scan relocations. This must be done after every symbol is declared so that
-  // we can correctly decide if a dynamic relocation is needed.
-  for (const std::unique_ptr<elf::ObjectFile<ELFT>> &F :
-       Symtab.getObjectFiles()) {
-    for (InputSectionBase<ELFT> *C : F->getSections()) {
-      if (isDiscarded(C))
-        continue;
-      if (auto *S = dyn_cast<InputSection<ELFT>>(C)) {
-        scanRelocations(*S);
-        continue;
-      }
-      if (auto *S = dyn_cast<EhInputSection<ELFT>>(C))
-        if (S->RelocSection)
-          scanRelocations(*S, *S->RelocSection);
-    }
-  }
+  if (Target->NeedsThunks)
+    forEachRelSec(createThunks<ELFT>);
 
   for (OutputSectionBase<ELFT> *Sec : OutputSections)
     Sec->assignOffsets();
 
+  // Scan relocations. This must be done after every symbol is declared so that
+  // we can correctly decide if a dynamic relocation is needed.
+  forEachRelSec(scanRelocations<ELFT>);
+
   // Now that we have defined all possible symbols including linker-
   // synthesized ones. Visit all symbols to give the finishing touches.
   std::vector<DefinedCommon *> CommonSymbols;
   for (Symbol *S : Symtab.getSymbols()) {
     SymbolBody *Body = S->body();
 
     // We only report undefined symbols in regular objects. This means that we
     // will accept an undefined reference in bitcode if it can be optimized out.