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 "Error.h"
  23 #include "Symbols.h"
  24 #include "lld/Core/Parallel.h"
  25 #include "llvm/ADT/Hashing.h"
  26 #include "llvm/Support/Debug.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(const std::vector<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 forEachColorRange(size_t Begin, size_t End,
  53                          std::function<void(size_t, size_t)> Fn);
  54
  55   void forEachColor(std::function<void(size_t, size_t)> Fn);
  56
  57   std::vector<SectionChunk *> Chunks;
  58   int Cnt = 0;
  59   std::atomic<uint32_t> NextId = {1};
  60   std::atomic<bool> Repeat = {false};
  61 };
  62
  63 // Returns a hash value for S.
  64 uint32_t ICF::getHash(SectionChunk *C) {
  65   return hash_combine(C->getPermissions(),
  66                       hash_value(C->SectionName),
  67                       C->NumRelocs,
  68                       C->getAlign(),
  69                       uint32_t(C->Header->SizeOfRawData),
  70                       C->Checksum);
  71 }
  72
  73 // Returns true if section S is subject of ICF.
  74 bool ICF::isEligible(SectionChunk *C) {
  75   bool Global = C->Sym && C->Sym->isExternal();
  76   bool Writable = C->getPermissions() & llvm::COFF::IMAGE_SCN_MEM_WRITE;
  77   return C->isCOMDAT() && C->isLive() && Global && !Writable;
  78 }
  79
  80 // Split a range into smaller ranges by recoloring sections
  81 void ICF::segregate(size_t Begin, size_t End, bool Constant) {
  82   while (Begin < End) {
  83     // Divide [Begin, End) into two. Let Mid be the start index of the
  84     // second group.
  85     auto Bound = std::stable_partition(
  86         Chunks.begin() + Begin + 1, Chunks.begin() + End, [&](SectionChunk *S) {
  87           if (Constant)
  88             return equalsConstant(Chunks[Begin], S);
  89           return equalsVariable(Chunks[Begin], S);
  90         });
  91     size_t Mid = Bound - Chunks.begin();
  92
  93     // Split [Begin, End) into [Begin, Mid) and [Mid, End).
  94     uint32_t Id = NextId++;
  95     for (size_t I = Begin; I < Mid; ++I)
  96       Chunks[I]->Color[(Cnt + 1) % 2] = Id;
  97
  98     // If we created a group, we need to iterate the main loop again.
  99     if (Mid != End)
 100       Repeat = true;
 101
 102     Begin = Mid;
 103   }
 104 }
 105
 106 // Compare "non-moving" part of two sections, namely everything
 107 // except relocation targets.
 108 bool ICF::equalsConstant(const SectionChunk *A, const SectionChunk *B) {
 109   if (A->NumRelocs != B->NumRelocs)
 110     return false;
 111
 112   // Compare relocations.
 113   auto Eq = [&](const coff_relocation &R1, const coff_relocation &R2) {
 114     if (R1.Type != R2.Type ||
 115         R1.VirtualAddress != R2.VirtualAddress) {
 116       return false;
 117     }
 118     SymbolBody *B1 = A->File->getSymbolBody(R1.SymbolTableIndex);
 119     SymbolBody *B2 = B->File->getSymbolBody(R2.SymbolTableIndex);
 120     if (B1 == B2)
 121       return true;
 122     if (auto *D1 = dyn_cast<DefinedRegular>(B1))
 123       if (auto *D2 = dyn_cast<DefinedRegular>(B2))
 124         return D1->getValue() == D2->getValue() &&
 125                D1->getChunk()->Color[Cnt % 2] == D2->getChunk()->Color[Cnt % 2];
 126     return false;
 127   };
 128   if (!std::equal(A->Relocs.begin(), A->Relocs.end(), B->Relocs.begin(), Eq))
 129     return false;
 130
 131   // Compare section attributes and contents.
 132   return A->getPermissions() == B->getPermissions() &&
 133          A->SectionName == B->SectionName &&
 134          A->getAlign() == B->getAlign() &&
 135          A->Header->SizeOfRawData == B->Header->SizeOfRawData &&
 136          A->Checksum == B->Checksum &&
 137          A->getContents() == B->getContents();
 138 }
 139
 140 // Compare "moving" part of two sections, namely relocation targets.
 141 bool ICF::equalsVariable(const SectionChunk *A, const SectionChunk *B) {
 142   // Compare relocations.
 143   auto Eq = [&](const coff_relocation &R1, const coff_relocation &R2) {
 144     SymbolBody *B1 = A->File->getSymbolBody(R1.SymbolTableIndex);
 145     SymbolBody *B2 = B->File->getSymbolBody(R2.SymbolTableIndex);
 146     if (B1 == B2)
 147       return true;
 148     if (auto *D1 = dyn_cast<DefinedRegular>(B1))
 149       if (auto *D2 = dyn_cast<DefinedRegular>(B2))
 150         return D1->getChunk()->Color[Cnt % 2] == D2->getChunk()->Color[Cnt % 2];
 151     return false;
 152   };
 153   return std::equal(A->Relocs.begin(), A->Relocs.end(), B->Relocs.begin(), Eq);
 154 }
 155
 156 size_t ICF::findBoundary(size_t Begin, size_t End) {
 157   for (size_t I = Begin + 1; I < End; ++I)
 158     if (Chunks[Begin]->Color[Cnt % 2] != Chunks[I]->Color[Cnt % 2])
 159       return I;
 160   return End;
 161 }
 162
 163 void ICF::forEachColorRange(size_t Begin, size_t End,
 164                             std::function<void(size_t, size_t)> Fn) {
 165   if (Begin > 0)
 166     Begin = findBoundary(Begin - 1, End);
 167
 168   while (Begin < End) {
 169     size_t Mid = findBoundary(Begin, Chunks.size());
 170     Fn(Begin, Mid);
 171     Begin = Mid;
 172   }
 173 }
 174
 175 // Call Fn on each color group.
 176 void ICF::forEachColor(std::function<void(size_t, size_t)> Fn) {
 177   // If the number of sections are too small to use threading,
 178   // call Fn sequentially.
 179   if (Chunks.size() < 1024) {
 180     forEachColorRange(0, Chunks.size(), Fn);
 181     return;
 182   }
 183
 184   // Split sections into 256 shards and call Fn in parallel.
 185   size_t NumShards = 256;
 186   size_t Step = Chunks.size() / NumShards;
 187   parallel_for(size_t(0), NumShards, [&](size_t I) {
 188     forEachColorRange(I * Step, (I + 1) * Step, Fn);
 189   });
 190   forEachColorRange(Step * NumShards, Chunks.size(), Fn);
 191 }
 192
 193 // Merge identical COMDAT sections.
 194 // Two sections are considered the same if their section headers,
 195 // contents and relocations are all the same.
 196 void ICF::run(const std::vector<Chunk *> &Vec) {
 197   // Collect only mergeable sections and group by hash value.
 198   for (Chunk *C : Vec) {
 199     auto *SC = dyn_cast<SectionChunk>(C);
 200     if (!SC)
 201       continue;
 202
 203     if (isEligible(SC)) {
 204       // Set MSB to 1 to avoid collisions with non-hash colors.
 205       SC->Color[0] = getHash(SC) | (1 << 31);
 206       Chunks.push_back(SC);
 207     } else {
 208       SC->Color[0] = NextId++;
 209     }
 210   }
 211
 212   if (Chunks.empty())
 213     return;
 214
 215   // From now on, sections in Chunks are ordered so that sections in
 216   // the same group are consecutive in the vector.
 217   std::stable_sort(Chunks.begin(), Chunks.end(),
 218                    [](SectionChunk *A, SectionChunk *B) {
 219                      return A->Color[0] < B->Color[0];
 220                    });
 221
 222   // Compare static contents and assign unique IDs for each static content.
 223   forEachColor([&](size_t Begin, size_t End) { segregate(Begin, End, true); });
 224   ++Cnt;
 225
 226   // Split groups by comparing relocations until convergence is obtained.
 227   do {
 228     Repeat = false;
 229     forEachColor(
 230         [&](size_t Begin, size_t End) { segregate(Begin, End, false); });
 231     ++Cnt;
 232   } while (Repeat);
 233
 234   if (Config->Verbose)
 235     outs() << "\nICF needed " << Cnt << " iterations\n";
 236
 237   // Merge sections in the same colors.
 238   forEachColor([&](size_t Begin, size_t End) {
 239     if (End - Begin == 1)
 240       return;
 241
 242     if (Config->Verbose)
 243       outs() << "Selected " << Chunks[Begin]->getDebugName() << "\n";
 244     for (size_t I = Begin + 1; I < End; ++I) {
 245       if (Config->Verbose)
 246         outs() << "  Removed " << Chunks[I]->getDebugName() << "\n";
 247       Chunks[Begin]->replace(Chunks[I]);
 248     }
 249   });
 250 }
 251
 252 // Entry point to ICF.
 253 void doICF(const std::vector<Chunk *> &Chunks) { ICF().run(Chunks); }
 254
 255 } // namespace coff
 256 } // namespace lld