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