contrib/llvm/tools/lld/ELF/ICF.cpp

   1 //===- ICF.cpp ------------------------------------------------------------===//
   2 //
   3 //                             The LLVM Linker
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // Identical Code Folding is a feature to merge sections not by name (which
  11 // is regular comdat handling) but by contents. If two non-writable sections
  12 // have the same data, relocations, attributes, etc., then the two
  13 // are considered identical and merged by the linker. This optimization
  14 // makes outputs smaller.
  15 //
  16 // ICF is theoretically a problem of reducing graphs by merging as many
  17 // identical subgraphs as possible if we consider sections as vertices and
  18 // relocations as edges. It may sound simple, but it is a bit more
  19 // complicated than you might think. The order of processing sections
  20 // matters because merging two sections can make other sections, whose
  21 // relocations now point to the same section, mergeable. Graphs may contain
  22 // cycles. We need a sophisticated algorithm to do this properly and
  23 // efficiently.
  24 //
  25 // What we do in this file is this. We split sections into groups. Sections
  26 // in the same group are considered identical.
  27 //
  28 // We begin by optimistically putting all sections into a single equivalence
  29 // class. Then we apply a series of checks that split this initial
  30 // equivalence class into more and more refined equivalence classes based on
  31 // the properties by which a section can be distinguished.
  32 //
  33 // We begin by checking that the section contents and flags are the
  34 // same. This only needs to be done once since these properties don't depend
  35 // on the current equivalence class assignment.
  36 //
  37 // Then we split the equivalence classes based on checking that their
  38 // relocations are the same, where relocation targets are compared by their
  39 // equivalence class, not the concrete section. This may need to be done
  40 // multiple times because as the equivalence classes are refined, two
  41 // sections that had a relocation target in the same equivalence class may
  42 // now target different equivalence classes, and hence these two sections
  43 // must be put in different equivalence classes (whereas in the previous
  44 // iteration they were not since the relocation target was the same.)
  45 //
  46 // Our algorithm is smart enough to merge the following mutually-recursive
  47 // functions.
  48 //
  49 //   void foo() { bar(); }
  50 //   void bar() { foo(); }
  51 //
  52 // This algorithm is so-called "optimistic" algorithm described in
  53 // http://research.google.com/pubs/pub36912.html. (Note that what GNU
  54 // gold implemented is different from the optimistic algorithm.)
  55 //
  56 //===----------------------------------------------------------------------===//
  57
  58 #include "ICF.h"
  59 #include "Config.h"
  60 #include "OutputSections.h"
  61 #include "SymbolTable.h"
  62
  63 #include "llvm/ADT/Hashing.h"
  64 #include "llvm/Object/ELF.h"
  65 #include "llvm/Support/ELF.h"
  66 #include "llvm/Support/raw_ostream.h"
  67
  68 using namespace lld;
  69 using namespace lld::elf;
  70 using namespace llvm;
  71 using namespace llvm::ELF;
  72 using namespace llvm::object;
  73
  74 namespace lld {
  75 namespace elf {
  76 template <class ELFT> class ICF {
  77   typedef typename ELFT::Shdr Elf_Shdr;
  78   typedef typename ELFT::Sym Elf_Sym;
  79   typedef typename ELFT::uint uintX_t;
  80   typedef Elf_Rel_Impl<ELFT, false> Elf_Rel;
  81
  82   using Comparator = std::function<bool(const InputSection<ELFT> *,
  83                                         const InputSection<ELFT> *)>;
  84
  85 public:
  86   void run();
  87
  88 private:
  89   uint64_t NextId = 1;
  90
  91   static void setLive(SymbolTable<ELFT> *S);
  92   static uint64_t relSize(InputSection<ELFT> *S);
  93   static uint64_t getHash(InputSection<ELFT> *S);
  94   static bool isEligible(InputSectionBase<ELFT> *Sec);
  95   static std::vector<InputSection<ELFT> *> getSections();
  96
  97   void segregate(InputSection<ELFT> **Begin, InputSection<ELFT> **End,
  98                  Comparator Eq);
  99
 100   void forEachGroup(std::vector<InputSection<ELFT> *> &V, Comparator Eq);
 101
 102   template <class RelTy>
 103   static bool relocationEq(ArrayRef<RelTy> RA, ArrayRef<RelTy> RB);
 104
 105   template <class RelTy>
 106   static bool variableEq(const InputSection<ELFT> *A,
 107                          const InputSection<ELFT> *B, ArrayRef<RelTy> RA,
 108                          ArrayRef<RelTy> RB);
 109
 110   static bool equalsConstant(const InputSection<ELFT> *A,
 111                              const InputSection<ELFT> *B);
 112
 113   static bool equalsVariable(const InputSection<ELFT> *A,
 114                              const InputSection<ELFT> *B);
 115 };
 116 }
 117 }
 118
 119 // Returns a hash value for S. Note that the information about
 120 // relocation targets is not included in the hash value.
 121 template <class ELFT> uint64_t ICF<ELFT>::getHash(InputSection<ELFT> *S) {
 122   uint64_t Flags = S->getSectionHdr()->sh_flags;
 123   uint64_t H = hash_combine(Flags, S->getSize());
 124   for (const Elf_Shdr *Rel : S->RelocSections)
 125     H = hash_combine(H, (uint64_t)Rel->sh_size);
 126   return H;
 127 }
 128
 129 // Returns true if Sec is subject of ICF.
 130 template <class ELFT> bool ICF<ELFT>::isEligible(InputSectionBase<ELFT> *Sec) {
 131   if (!Sec || Sec == &InputSection<ELFT>::Discarded || !Sec->Live)
 132     return false;
 133   auto *S = dyn_cast<InputSection<ELFT>>(Sec);
 134   if (!S)
 135     return false;
 136
 137   // .init and .fini contains instructions that must be executed to
 138   // initialize and finalize the process. They cannot and should not
 139   // be merged.
 140   StringRef Name = S->getSectionName();
 141   if (Name == ".init" || Name == ".fini")
 142     return false;
 143
 144   const Elf_Shdr &H = *S->getSectionHdr();
 145   return (H.sh_flags & SHF_ALLOC) && (~H.sh_flags & SHF_WRITE);
 146 }
 147
 148 template <class ELFT>
 149 std::vector<InputSection<ELFT> *> ICF<ELFT>::getSections() {
 150   std::vector<InputSection<ELFT> *> V;
 151   for (const std::unique_ptr<ObjectFile<ELFT>> &F :
 152        Symtab<ELFT>::X->getObjectFiles())
 153     for (InputSectionBase<ELFT> *S : F->getSections())
 154       if (isEligible(S))
 155         V.push_back(cast<InputSection<ELFT>>(S));
 156   return V;
 157 }
 158
 159 // All sections between Begin and End must have the same group ID before
 160 // you call this function. This function compare sections between Begin
 161 // and End using Eq and assign new group IDs for new groups.
 162 template <class ELFT>
 163 void ICF<ELFT>::segregate(InputSection<ELFT> **Begin, InputSection<ELFT> **End,
 164                           Comparator Eq) {
 165   // This loop rearranges [Begin, End) so that all sections that are
 166   // equal in terms of Eq are contiguous. The algorithm is quadratic in
 167   // the worst case, but that is not an issue in practice because the
 168   // number of distinct sections in [Begin, End) is usually very small.
 169   InputSection<ELFT> **I = Begin;
 170   for (;;) {
 171     InputSection<ELFT> *Head = *I;
 172     auto Bound = std::stable_partition(
 173         I + 1, End, [&](InputSection<ELFT> *S) { return Eq(Head, S); });
 174     if (Bound == End)
 175       return;
 176     uint64_t Id = NextId++;
 177     for (; I != Bound; ++I)
 178       (*I)->GroupId = Id;
 179   }
 180 }
 181
 182 template <class ELFT>
 183 void ICF<ELFT>::forEachGroup(std::vector<InputSection<ELFT> *> &V,
 184                              Comparator Eq) {
 185   for (InputSection<ELFT> **I = V.data(), **E = I + V.size(); I != E;) {
 186     InputSection<ELFT> *Head = *I;
 187     auto Bound = std::find_if(I + 1, E, [&](InputSection<ELFT> *S) {
 188       return S->GroupId != Head->GroupId;
 189     });
 190     segregate(I, Bound, Eq);
 191     I = Bound;
 192   }
 193 }
 194
 195 // Compare two lists of relocations.
 196 template <class ELFT>
 197 template <class RelTy>
 198 bool ICF<ELFT>::relocationEq(ArrayRef<RelTy> RelsA, ArrayRef<RelTy> RelsB) {
 199   const RelTy *IA = RelsA.begin();
 200   const RelTy *EA = RelsA.end();
 201   const RelTy *IB = RelsB.begin();
 202   const RelTy *EB = RelsB.end();
 203   if (EA - IA != EB - IB)
 204     return false;
 205   for (; IA != EA; ++IA, ++IB)
 206     if (IA->r_offset != IB->r_offset ||
 207         IA->getType(Config->Mips64EL) != IB->getType(Config->Mips64EL) ||
 208         getAddend<ELFT>(*IA) != getAddend<ELFT>(*IB))
 209       return false;
 210   return true;
 211 }
 212
 213 // Compare "non-moving" part of two InputSections, namely everything
 214 // except relocation targets.
 215 template <class ELFT>
 216 bool ICF<ELFT>::equalsConstant(const InputSection<ELFT> *A,
 217                                const InputSection<ELFT> *B) {
 218   if (A->RelocSections.size() != B->RelocSections.size())
 219     return false;
 220
 221   for (size_t I = 0, E = A->RelocSections.size(); I != E; ++I) {
 222     const Elf_Shdr *RA = A->RelocSections[I];
 223     const Elf_Shdr *RB = B->RelocSections[I];
 224     ELFFile<ELFT> &FileA = A->File->getObj();
 225     ELFFile<ELFT> &FileB = B->File->getObj();
 226     if (RA->sh_type == SHT_RELA) {
 227       if (!relocationEq(FileA.relas(RA), FileB.relas(RB)))
 228         return false;
 229     } else {
 230       if (!relocationEq(FileA.rels(RA), FileB.rels(RB)))
 231         return false;
 232     }
 233   }
 234
 235   return A->getSectionHdr()->sh_flags == B->getSectionHdr()->sh_flags &&
 236          A->getSize() == B->getSize() &&
 237          A->getSectionData() == B->getSectionData();
 238 }
 239
 240 template <class ELFT>
 241 template <class RelTy>
 242 bool ICF<ELFT>::variableEq(const InputSection<ELFT> *A,
 243                            const InputSection<ELFT> *B, ArrayRef<RelTy> RelsA,
 244                            ArrayRef<RelTy> RelsB) {
 245   const RelTy *IA = RelsA.begin();
 246   const RelTy *EA = RelsA.end();
 247   const RelTy *IB = RelsB.begin();
 248   for (; IA != EA; ++IA, ++IB) {
 249     SymbolBody &SA = A->File->getRelocTargetSym(*IA);
 250     SymbolBody &SB = B->File->getRelocTargetSym(*IB);
 251     if (&SA == &SB)
 252       continue;
 253
 254     // Or, the symbols should be pointing to the same section
 255     // in terms of the group ID.
 256     auto *DA = dyn_cast<DefinedRegular<ELFT>>(&SA);
 257     auto *DB = dyn_cast<DefinedRegular<ELFT>>(&SB);
 258     if (!DA || !DB)
 259       return false;
 260     if (DA->Value != DB->Value)
 261       return false;
 262     InputSection<ELFT> *X = dyn_cast<InputSection<ELFT>>(DA->Section);
 263     InputSection<ELFT> *Y = dyn_cast<InputSection<ELFT>>(DB->Section);
 264     if (X && Y && X->GroupId && X->GroupId == Y->GroupId)
 265       continue;
 266     return false;
 267   }
 268   return true;
 269 }
 270
 271 // Compare "moving" part of two InputSections, namely relocation targets.
 272 template <class ELFT>
 273 bool ICF<ELFT>::equalsVariable(const InputSection<ELFT> *A,
 274                                const InputSection<ELFT> *B) {
 275   for (size_t I = 0, E = A->RelocSections.size(); I != E; ++I) {
 276     const Elf_Shdr *RA = A->RelocSections[I];
 277     const Elf_Shdr *RB = B->RelocSections[I];
 278     ELFFile<ELFT> &FileA = A->File->getObj();
 279     ELFFile<ELFT> &FileB = B->File->getObj();
 280     if (RA->sh_type == SHT_RELA) {
 281       if (!variableEq(A, B, FileA.relas(RA), FileB.relas(RB)))
 282         return false;
 283     } else {
 284       if (!variableEq(A, B, FileA.rels(RA), FileB.rels(RB)))
 285         return false;
 286     }
 287   }
 288   return true;
 289 }
 290
 291 // The main function of ICF.
 292 template <class ELFT> void ICF<ELFT>::run() {
 293   // Initially, we use hash values as section group IDs. Therefore,
 294   // if two sections have the same ID, they are likely (but not
 295   // guaranteed) to have the same static contents in terms of ICF.
 296   std::vector<InputSection<ELFT> *> V = getSections();
 297   for (InputSection<ELFT> *S : V)
 298     // Set MSB on to avoid collisions with serial group IDs
 299     S->GroupId = getHash(S) | (uint64_t(1) << 63);
 300
 301   // From now on, sections in V are ordered so that sections in
 302   // the same group are consecutive in the vector.
 303   std::stable_sort(V.begin(), V.end(),
 304                    [](InputSection<ELFT> *A, InputSection<ELFT> *B) {
 305                      return A->GroupId < B->GroupId;
 306                    });
 307
 308   // Compare static contents and assign unique IDs for each static content.
 309   forEachGroup(V, equalsConstant);
 310
 311   // Split groups by comparing relocations until we get a convergence.
 312   int Cnt = 1;
 313   for (;;) {
 314     ++Cnt;
 315     uint64_t Id = NextId;
 316     forEachGroup(V, equalsVariable);
 317     if (Id == NextId)
 318       break;
 319   }
 320   log("ICF needed " + Twine(Cnt) + " iterations.");
 321
 322   // Merge sections in the same group.
 323   for (auto I = V.begin(), E = V.end(); I != E;) {
 324     InputSection<ELFT> *Head = *I++;
 325     auto Bound = std::find_if(I, E, [&](InputSection<ELFT> *S) {
 326       return Head->GroupId != S->GroupId;
 327     });
 328     if (I == Bound)
 329       continue;
 330     log("selected " + Head->getSectionName());
 331     while (I != Bound) {
 332       InputSection<ELFT> *S = *I++;
 333       log("  removed " + S->getSectionName());
 334       Head->replace(S);
 335     }
 336   }
 337 }
 338
 339 // ICF entry point function.
 340 template <class ELFT> void elf::doIcf() { ICF<ELFT>().run(); }
 341
 342 template void elf::doIcf<ELF32LE>();
 343 template void elf::doIcf<ELF32BE>();
 344 template void elf::doIcf<ELF64LE>();
 345 template void elf::doIcf<ELF64BE>();