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 "Chunks.h"
  22 #include "Symbols.h"
  23 #include "lld/Common/ErrorHandler.h"
  24 #include "llvm/ADT/Hashing.h"
  25 #include "llvm/Support/Debug.h"
  26 #include "llvm/Support/Parallel.h"
  27 #include "llvm/Support/raw_ostream.h"
  28 #include <algorithm>
  29 #include <atomic>
  30 #include <vector>
  31
  32 using namespace llvm;
  33
  34 namespace lld {
  35 namespace coff {
  36
  37 class ICF {
  38 public:
  39   void run(ArrayRef<Chunk *> V);
  40
  41 private:
  42   void segregate(size_t Begin, size_t End, bool Constant);
  43
  44   bool equalsConstant(const SectionChunk *A, const SectionChunk *B);
  45   bool equalsVariable(const SectionChunk *A, const SectionChunk *B);
  46
  47   uint32_t getHash(SectionChunk *C);
  48   bool isEligible(SectionChunk *C);
  49
  50   size_t findBoundary(size_t Begin, size_t End);
  51
  52   void forEachClassRange(size_t Begin, size_t End,
  53                          std::function<void(size_t, size_t)> Fn);
  54
  55   void forEachClass(std::function<void(size_t, size_t)> Fn);
  56
  57   std::vector<SectionChunk *> Chunks;
  58   int Cnt = 0;
  59   std::atomic<bool> Repeat = {false};
  60 };
  61
  62 // Returns a hash value for S.
  63 uint32_t ICF::getHash(SectionChunk *C) {
  64   return hash_combine(C->getPermissions(), C->SectionName, C->NumRelocs,
  65                       C->Alignment, uint32_t(C->Header->SizeOfRawData),
  66                       C->Checksum, C->getContents());
  67 }
  68
  69 // Returns true if section S is subject of ICF.
  70 //
  71 // Microsoft's documentation
  72 // (https://msdn.microsoft.com/en-us/library/bxwfs976.aspx; visited April
  73 // 2017) says that /opt:icf folds both functions and read-only data.
  74 // Despite that, the MSVC linker folds only functions. We found
  75 // a few instances of programs that are not safe for data merging.
  76 // Therefore, we merge only functions just like the MSVC tool. However, we merge
  77 // identical .xdata sections, because the address of unwind information is
  78 // insignificant to the user program and the Visual C++ linker does this.
  79 bool ICF::isEligible(SectionChunk *C) {
  80   // Non-comdat chunks, dead chunks, and writable chunks are not elegible.
  81   bool Writable = C->getPermissions() & llvm::COFF::IMAGE_SCN_MEM_WRITE;
  82   if (!C->isCOMDAT() || !C->isLive() || Writable)
  83     return false;
  84
  85   // Code sections are eligible.
  86   if (C->getPermissions() & llvm::COFF::IMAGE_SCN_MEM_EXECUTE)
  87     return true;
  88
  89   // .xdata unwind info sections are eligble.
  90   return C->getSectionName().split('$').first == ".xdata";
  91 }
  92
  93 // Split an equivalence class into smaller classes.
  94 void ICF::segregate(size_t Begin, size_t End, bool Constant) {
  95   while (Begin < End) {
  96     // Divide [Begin, End) into two. Let Mid be the start index of the
  97     // second group.
  98     auto Bound = std::stable_partition(
  99         Chunks.begin() + Begin + 1, Chunks.begin() + End, [&](SectionChunk *S) {
 100           if (Constant)
 101             return equalsConstant(Chunks[Begin], S);
 102           return equalsVariable(Chunks[Begin], S);
 103         });
 104     size_t Mid = Bound - Chunks.begin();
 105
 106     // Split [Begin, End) into [Begin, Mid) and [Mid, End). We use Mid as an
 107     // equivalence class ID because every group ends with a unique index.
 108     for (size_t I = Begin; I < Mid; ++I)
 109       Chunks[I]->Class[(Cnt + 1) % 2] = Mid;
 110
 111     // If we created a group, we need to iterate the main loop again.
 112     if (Mid != End)
 113       Repeat = true;
 114
 115     Begin = Mid;
 116   }
 117 }
 118
 119 // Compare "non-moving" part of two sections, namely everything
 120 // except relocation targets.
 121 bool ICF::equalsConstant(const SectionChunk *A, const SectionChunk *B) {
 122   if (A->NumRelocs != B->NumRelocs)
 123     return false;
 124
 125   // Compare relocations.
 126   auto Eq = [&](const coff_relocation &R1, const coff_relocation &R2) {
 127     if (R1.Type != R2.Type ||
 128         R1.VirtualAddress != R2.VirtualAddress) {
 129       return false;
 130     }
 131     Symbol *B1 = A->File->getSymbol(R1.SymbolTableIndex);
 132     Symbol *B2 = B->File->getSymbol(R2.SymbolTableIndex);
 133     if (B1 == B2)
 134       return true;
 135     if (auto *D1 = dyn_cast<DefinedRegular>(B1))
 136       if (auto *D2 = dyn_cast<DefinedRegular>(B2))
 137         return D1->getValue() == D2->getValue() &&
 138                D1->getChunk()->Class[Cnt % 2] == D2->getChunk()->Class[Cnt % 2];
 139     return false;
 140   };
 141   if (!std::equal(A->Relocs.begin(), A->Relocs.end(), B->Relocs.begin(), Eq))
 142     return false;
 143
 144   // Compare section attributes and contents.
 145   return A->getPermissions() == B->getPermissions() &&
 146          A->SectionName == B->SectionName && A->Alignment == B->Alignment &&
 147          A->Header->SizeOfRawData == B->Header->SizeOfRawData &&
 148          A->Checksum == B->Checksum && A->getContents() == B->getContents();
 149 }
 150
 151 // Compare "moving" part of two sections, namely relocation targets.
 152 bool ICF::equalsVariable(const SectionChunk *A, const SectionChunk *B) {
 153   // Compare relocations.
 154   auto Eq = [&](const coff_relocation &R1, const coff_relocation &R2) {
 155     Symbol *B1 = A->File->getSymbol(R1.SymbolTableIndex);
 156     Symbol *B2 = B->File->getSymbol(R2.SymbolTableIndex);
 157     if (B1 == B2)
 158       return true;
 159     if (auto *D1 = dyn_cast<DefinedRegular>(B1))
 160       if (auto *D2 = dyn_cast<DefinedRegular>(B2))
 161         return D1->getChunk()->Class[Cnt % 2] == D2->getChunk()->Class[Cnt % 2];
 162     return false;
 163   };
 164   return std::equal(A->Relocs.begin(), A->Relocs.end(), B->Relocs.begin(), Eq);
 165 }
 166
 167 size_t ICF::findBoundary(size_t Begin, size_t End) {
 168   for (size_t I = Begin + 1; I < End; ++I)
 169     if (Chunks[Begin]->Class[Cnt % 2] != Chunks[I]->Class[Cnt % 2])
 170       return I;
 171   return End;
 172 }
 173
 174 void ICF::forEachClassRange(size_t Begin, size_t End,
 175                             std::function<void(size_t, size_t)> Fn) {
 176   if (Begin > 0)
 177     Begin = findBoundary(Begin - 1, End);
 178
 179   while (Begin < End) {
 180     size_t Mid = findBoundary(Begin, Chunks.size());
 181     Fn(Begin, Mid);
 182     Begin = Mid;
 183   }
 184 }
 185
 186 // Call Fn on each class group.
 187 void ICF::forEachClass(std::function<void(size_t, size_t)> Fn) {
 188   // If the number of sections are too small to use threading,
 189   // call Fn sequentially.
 190   if (Chunks.size() < 1024) {
 191     forEachClassRange(0, Chunks.size(), Fn);
 192     ++Cnt;
 193     return;
 194   }
 195
 196   // Split sections into 256 shards and call Fn in parallel.
 197   size_t NumShards = 256;
 198   size_t Step = Chunks.size() / NumShards;
 199   for_each_n(parallel::par, size_t(0), NumShards, [&](size_t I) {
 200     size_t End = (I == NumShards - 1) ? Chunks.size() : (I + 1) * Step;
 201     forEachClassRange(I * Step, End, Fn);
 202   });
 203   ++Cnt;
 204 }
 205
 206 // Merge identical COMDAT sections.
 207 // Two sections are considered the same if their section headers,
 208 // contents and relocations are all the same.
 209 void ICF::run(ArrayRef<Chunk *> Vec) {
 210   // Collect only mergeable sections and group by hash value.
 211   uint32_t NextId = 1;
 212   for (Chunk *C : Vec) {
 213     if (auto *SC = dyn_cast<SectionChunk>(C)) {
 214       if (isEligible(SC))
 215         Chunks.push_back(SC);
 216       else
 217         SC->Class[0] = NextId++;
 218     }
 219   }
 220
 221   // Initially, we use hash values to partition sections.
 222   for_each(parallel::par, Chunks.begin(), Chunks.end(), [&](SectionChunk *SC) {
 223     // Set MSB to 1 to avoid collisions with non-hash classs.
 224     SC->Class[0] = getHash(SC) | (1 << 31);
 225   });
 226
 227   // From now on, sections in Chunks are ordered so that sections in
 228   // the same group are consecutive in the vector.
 229   std::stable_sort(Chunks.begin(), Chunks.end(),
 230                    [](SectionChunk *A, SectionChunk *B) {
 231                      return A->Class[0] < B->Class[0];
 232                    });
 233
 234   // Compare static contents and assign unique IDs for each static content.
 235   forEachClass([&](size_t Begin, size_t End) { segregate(Begin, End, true); });
 236
 237   // Split groups by comparing relocations until convergence is obtained.
 238   do {
 239     Repeat = false;
 240     forEachClass(
 241         [&](size_t Begin, size_t End) { segregate(Begin, End, false); });
 242   } while (Repeat);
 243
 244   log("ICF needed " + Twine(Cnt) + " iterations");
 245
 246   // Merge sections in the same classs.
 247   forEachClass([&](size_t Begin, size_t End) {
 248     if (End - Begin == 1)
 249       return;
 250
 251     log("Selected " + Chunks[Begin]->getDebugName());
 252     for (size_t I = Begin + 1; I < End; ++I) {
 253       log("  Removed " + Chunks[I]->getDebugName());
 254       Chunks[Begin]->replace(Chunks[I]);
 255     }
 256   });
 257 }
 258
 259 // Entry point to ICF.
 260 void doICF(ArrayRef<Chunk *> Chunks) { ICF().run(Chunks); }
 261
 262 } // namespace coff
 263 } // namespace lld