contrib/llvm/tools/lld/COFF/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 // ICF is short for Identical Code Folding. That is a size optimization to
  11 // identify and merge two or more read-only sections (typically functions)
  12 // that happened to have the same contents. It usually reduces output size
  13 // by a few percent.
  14 //
  15 // On Windows, ICF is enabled by default.
  16 //
  17 // See ELF/ICF.cpp for the details about the algortihm.
  18 //
  19 //===----------------------------------------------------------------------===//
  20
  21 #include "ICF.h"
  22 #include "Chunks.h"
  23 #include "Symbols.h"
  24 #include "lld/Common/ErrorHandler.h"
  25 #include "lld/Common/Timer.h"
  26 #include "llvm/ADT/Hashing.h"
  27 #include "llvm/Support/Debug.h"
  28 #include "llvm/Support/Parallel.h"
  29 #include "llvm/Support/raw_ostream.h"
  30 #include <algorithm>
  31 #include <atomic>
  32 #include <vector>
  33
  34 using namespace llvm;
  35
  36 namespace lld {
  37 namespace coff {
  38
  39 static Timer ICFTimer("ICF", Timer::root());
  40
  41 class ICF {
  42 public:
  43   void run(ArrayRef<Chunk *> V);
  44
  45 private:
  46   void segregate(size_t Begin, size_t End, bool Constant);
  47
  48   bool assocEquals(const SectionChunk *A, const SectionChunk *B);
  49
  50   bool equalsConstant(const SectionChunk *A, const SectionChunk *B);
  51   bool equalsVariable(const SectionChunk *A, const SectionChunk *B);
  52
  53   uint32_t getHash(SectionChunk *C);
  54   bool isEligible(SectionChunk *C);
  55
  56   size_t findBoundary(size_t Begin, size_t End);
  57
  58   void forEachClassRange(size_t Begin, size_t End,
  59                          std::function<void(size_t, size_t)> Fn);
  60
  61   void forEachClass(std::function<void(size_t, size_t)> Fn);
  62
  63   std::vector<SectionChunk *> Chunks;
  64   int Cnt = 0;
  65   std::atomic<bool> Repeat = {false};
  66 };
  67
  68 // Returns a hash value for S.
  69 uint32_t ICF::getHash(SectionChunk *C) {
  70   return hash_combine(C->getOutputCharacteristics(), C->SectionName,
  71                       C->Relocs.size(), uint32_t(C->Header->SizeOfRawData),
  72                       C->Checksum, C->getContents());
  73 }
  74
  75 // Returns true if section S is subject of ICF.
  76 //
  77 // Microsoft's documentation
  78 // (https://msdn.microsoft.com/en-us/library/bxwfs976.aspx; visited April
  79 // 2017) says that /opt:icf folds both functions and read-only data.
  80 // Despite that, the MSVC linker folds only functions. We found
  81 // a few instances of programs that are not safe for data merging.
  82 // Therefore, we merge only functions just like the MSVC tool. However, we also
  83 // merge read-only sections in a couple of cases where the address of the
  84 // section is insignificant to the user program and the behaviour matches that
  85 // of the Visual C++ linker.
  86 bool ICF::isEligible(SectionChunk *C) {
  87   // Non-comdat chunks, dead chunks, and writable chunks are not elegible.
  88   bool Writable = C->getOutputCharacteristics() & llvm::COFF::IMAGE_SCN_MEM_WRITE;
  89   if (!C->isCOMDAT() || !C->isLive() || Writable)
  90     return false;
  91
  92   // Code sections are eligible.
  93   if (C->getOutputCharacteristics() & llvm::COFF::IMAGE_SCN_MEM_EXECUTE)
  94     return true;
  95
  96   // .pdata and .xdata unwind info sections are eligible.
  97   StringRef OutSecName = C->getSectionName().split('$').first;
  98   if (OutSecName == ".pdata" || OutSecName == ".xdata")
  99     return true;
 100
 101   // So are vtables.
 102   return C->Sym && C->Sym->getName().startswith("??_7");
 103 }
 104
 105 // Split an equivalence class into smaller classes.
 106 void ICF::segregate(size_t Begin, size_t End, bool Constant) {
 107   while (Begin < End) {
 108     // Divide [Begin, End) into two. Let Mid be the start index of the
 109     // second group.
 110     auto Bound = std::stable_partition(
 111         Chunks.begin() + Begin + 1, Chunks.begin() + End, [&](SectionChunk *S) {
 112           if (Constant)
 113             return equalsConstant(Chunks[Begin], S);
 114           return equalsVariable(Chunks[Begin], S);
 115         });
 116     size_t Mid = Bound - Chunks.begin();
 117
 118     // Split [Begin, End) into [Begin, Mid) and [Mid, End). We use Mid as an
 119     // equivalence class ID because every group ends with a unique index.
 120     for (size_t I = Begin; I < Mid; ++I)
 121       Chunks[I]->Class[(Cnt + 1) % 2] = Mid;
 122
 123     // If we created a group, we need to iterate the main loop again.
 124     if (Mid != End)
 125       Repeat = true;
 126
 127     Begin = Mid;
 128   }
 129 }
 130
 131 // Returns true if two sections' associative children are equal.
 132 bool ICF::assocEquals(const SectionChunk *A, const SectionChunk *B) {
 133   auto ChildClasses = [&](const SectionChunk *SC) {
 134     std::vector<uint32_t> Classes;
 135     for (const SectionChunk *C : SC->children())
 136       if (!C->SectionName.startswith(".debug") &&
 137           C->SectionName != ".gfids$y" && C->SectionName != ".gljmp$y")
 138         Classes.push_back(C->Class[Cnt % 2]);
 139     return Classes;
 140   };
 141   return ChildClasses(A) == ChildClasses(B);
 142 }
 143
 144 // Compare "non-moving" part of two sections, namely everything
 145 // except relocation targets.
 146 bool ICF::equalsConstant(const SectionChunk *A, const SectionChunk *B) {
 147   if (A->Relocs.size() != B->Relocs.size())
 148     return false;
 149
 150   // Compare relocations.
 151   auto Eq = [&](const coff_relocation &R1, const coff_relocation &R2) {
 152     if (R1.Type != R2.Type ||
 153         R1.VirtualAddress != R2.VirtualAddress) {
 154       return false;
 155     }
 156     Symbol *B1 = A->File->getSymbol(R1.SymbolTableIndex);
 157     Symbol *B2 = B->File->getSymbol(R2.SymbolTableIndex);
 158     if (B1 == B2)
 159       return true;
 160     if (auto *D1 = dyn_cast<DefinedRegular>(B1))
 161       if (auto *D2 = dyn_cast<DefinedRegular>(B2))
 162         return D1->getValue() == D2->getValue() &&
 163                D1->getChunk()->Class[Cnt % 2] == D2->getChunk()->Class[Cnt % 2];
 164     return false;
 165   };
 166   if (!std::equal(A->Relocs.begin(), A->Relocs.end(), B->Relocs.begin(), Eq))
 167     return false;
 168
 169   // Compare section attributes and contents.
 170   return A->getOutputCharacteristics() == B->getOutputCharacteristics() &&
 171          A->SectionName == B->SectionName &&
 172          A->Header->SizeOfRawData == B->Header->SizeOfRawData &&
 173          A->Checksum == B->Checksum && A->getContents() == B->getContents() &&
 174          assocEquals(A, B);
 175 }
 176
 177 // Compare "moving" part of two sections, namely relocation targets.
 178 bool ICF::equalsVariable(const SectionChunk *A, const SectionChunk *B) {
 179   // Compare relocations.
 180   auto Eq = [&](const coff_relocation &R1, const coff_relocation &R2) {
 181     Symbol *B1 = A->File->getSymbol(R1.SymbolTableIndex);
 182     Symbol *B2 = B->File->getSymbol(R2.SymbolTableIndex);
 183     if (B1 == B2)
 184       return true;
 185     if (auto *D1 = dyn_cast<DefinedRegular>(B1))
 186       if (auto *D2 = dyn_cast<DefinedRegular>(B2))
 187         return D1->getChunk()->Class[Cnt % 2] == D2->getChunk()->Class[Cnt % 2];
 188     return false;
 189   };
 190   return std::equal(A->Relocs.begin(), A->Relocs.end(), B->Relocs.begin(),
 191                     Eq) &&
 192          assocEquals(A, B);
 193 }
 194
 195 // Find the first Chunk after Begin that has a different class from Begin.
 196 size_t ICF::findBoundary(size_t Begin, size_t End) {
 197   for (size_t I = Begin + 1; I < End; ++I)
 198     if (Chunks[Begin]->Class[Cnt % 2] != Chunks[I]->Class[Cnt % 2])
 199       return I;
 200   return End;
 201 }
 202
 203 void ICF::forEachClassRange(size_t Begin, size_t End,
 204                             std::function<void(size_t, size_t)> Fn) {
 205   while (Begin < End) {
 206     size_t Mid = findBoundary(Begin, End);
 207     Fn(Begin, Mid);
 208     Begin = Mid;
 209   }
 210 }
 211
 212 // Call Fn on each class group.
 213 void ICF::forEachClass(std::function<void(size_t, size_t)> Fn) {
 214   // If the number of sections are too small to use threading,
 215   // call Fn sequentially.
 216   if (Chunks.size() < 1024) {
 217     forEachClassRange(0, Chunks.size(), Fn);
 218     ++Cnt;
 219     return;
 220   }
 221
 222   // Shard into non-overlapping intervals, and call Fn in parallel.
 223   // The sharding must be completed before any calls to Fn are made
 224   // so that Fn can modify the Chunks in its shard without causing data
 225   // races.
 226   const size_t NumShards = 256;
 227   size_t Step = Chunks.size() / NumShards;
 228   size_t Boundaries[NumShards + 1];
 229   Boundaries[0] = 0;
 230   Boundaries[NumShards] = Chunks.size();
 231   for_each_n(parallel::par, size_t(1), NumShards, [&](size_t I) {
 232     Boundaries[I] = findBoundary((I - 1) * Step, Chunks.size());
 233   });
 234   for_each_n(parallel::par, size_t(1), NumShards + 1, [&](size_t I) {
 235     if (Boundaries[I - 1] < Boundaries[I]) {
 236       forEachClassRange(Boundaries[I - 1], Boundaries[I], Fn);
 237     }
 238   });
 239   ++Cnt;
 240 }
 241
 242 // Merge identical COMDAT sections.
 243 // Two sections are considered the same if their section headers,
 244 // contents and relocations are all the same.
 245 void ICF::run(ArrayRef<Chunk *> Vec) {
 246   ScopedTimer T(ICFTimer);
 247
 248   // Collect only mergeable sections and group by hash value.
 249   uint32_t NextId = 1;
 250   for (Chunk *C : Vec) {
 251     if (auto *SC = dyn_cast<SectionChunk>(C)) {
 252       if (isEligible(SC))
 253         Chunks.push_back(SC);
 254       else
 255         SC->Class[0] = NextId++;
 256     }
 257   }
 258
 259   // Make sure that ICF doesn't merge sections that are being handled by string
 260   // tail merging.
 261   for (auto &P : MergeChunk::Instances)
 262     for (SectionChunk *SC : P.second->Sections)
 263       SC->Class[0] = NextId++;
 264
 265   // Initially, we use hash values to partition sections.
 266   for_each(parallel::par, Chunks.begin(), Chunks.end(), [&](SectionChunk *SC) {
 267     // Set MSB to 1 to avoid collisions with non-hash classs.
 268     SC->Class[0] = getHash(SC) | (1 << 31);
 269   });
 270
 271   // From now on, sections in Chunks are ordered so that sections in
 272   // the same group are consecutive in the vector.
 273   std::stable_sort(Chunks.begin(), Chunks.end(),
 274                    [](SectionChunk *A, SectionChunk *B) {
 275                      return A->Class[0] < B->Class[0];
 276                    });
 277
 278   // Compare static contents and assign unique IDs for each static content.
 279   forEachClass([&](size_t Begin, size_t End) { segregate(Begin, End, true); });
 280
 281   // Split groups by comparing relocations until convergence is obtained.
 282   do {
 283     Repeat = false;
 284     forEachClass(
 285         [&](size_t Begin, size_t End) { segregate(Begin, End, false); });
 286   } while (Repeat);
 287
 288   log("ICF needed " + Twine(Cnt) + " iterations");
 289
 290   // Merge sections in the same classs.
 291   forEachClass([&](size_t Begin, size_t End) {
 292     if (End - Begin == 1)
 293       return;
 294
 295     log("Selected " + Chunks[Begin]->getDebugName());
 296     for (size_t I = Begin + 1; I < End; ++I) {
 297       log("  Removed " + Chunks[I]->getDebugName());
 298       Chunks[Begin]->replace(Chunks[I]);
 299     }
 300   });
 301 }
 302
 303 // Entry point to ICF.
 304 void doICF(ArrayRef<Chunk *> Chunks) { ICF().run(Chunks); }
 305
 306 } // namespace coff
 307 } // namespace lld