lld/COFF/ICF.cpp

   1 //===- ICF.cpp ------------------------------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // ICF is short for Identical Code Folding. That is a size optimization to
  10 // identify and merge two or more read-only sections (typically functions)
  11 // that happened to have the same contents. It usually reduces output size
  12 // by a few percent.
  13 //
  14 // On Windows, ICF is enabled by default.
  15 //
  16 // See ELF/ICF.cpp for the details about the algorithm.
  17 //
  18 //===----------------------------------------------------------------------===//
  19
  20 #include "ICF.h"
  21 #include "COFFLinkerContext.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/TimeProfiler.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::coff {
  39
  40 class ICF {
  41 public:
  42   ICF(COFFLinkerContext &c) : ctx(c){};
  43   void run();
  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   bool isEligible(SectionChunk *c);
  54
  55   size_t findBoundary(size_t begin, size_t end);
  56
  57   void forEachClassRange(size_t begin, size_t end,
  58                          std::function<void(size_t, size_t)> fn);
  59
  60   void forEachClass(std::function<void(size_t, size_t)> fn);
  61
  62   std::vector<SectionChunk *> chunks;
  63   int cnt = 0;
  64   std::atomic<bool> repeat = {false};
  65
  66   COFFLinkerContext &ctx;
  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 also
  77 // merge read-only sections in a couple of cases where the address of the
  78 // section is insignificant to the user program and the behaviour matches that
  79 // of the Visual C++ linker.
  80 bool ICF::isEligible(SectionChunk *c) {
  81   // Non-comdat chunks, dead chunks, and writable chunks are not eligible.
  82   bool writable = c->getOutputCharacteristics() & llvm::COFF::IMAGE_SCN_MEM_WRITE;
  83   if (!c->isCOMDAT() || !c->live || writable)
  84     return false;
  85
  86   // Under regular (not safe) ICF, all code sections are eligible.
  87   if ((ctx.config.doICF == ICFLevel::All) &&
  88       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   const char *itaniumVtablePrefix =
  98       ctx.config.machine == I386 ? "__ZTV" : "_ZTV";
  99   if (c->sym && (c->sym->getName().starts_with("??_7") ||
 100                  c->sym->getName().starts_with(itaniumVtablePrefix)))
 101     return true;
 102
 103   // Anything else not in an address-significance table is eligible.
 104   return !c->keepUnique;
 105 }
 106
 107 // Split an equivalence class into smaller classes.
 108 void ICF::segregate(size_t begin, size_t end, bool constant) {
 109   while (begin < end) {
 110     // Divide [Begin, End) into two. Let Mid be the start index of the
 111     // second group.
 112     auto bound = std::stable_partition(
 113         chunks.begin() + begin + 1, chunks.begin() + end, [&](SectionChunk *s) {
 114           if (constant)
 115             return equalsConstant(chunks[begin], s);
 116           return equalsVariable(chunks[begin], s);
 117         });
 118     size_t mid = bound - chunks.begin();
 119
 120     // Split [Begin, End) into [Begin, Mid) and [Mid, End). We use Mid as an
 121     // equivalence class ID because every group ends with a unique index.
 122     for (size_t i = begin; i < mid; ++i)
 123       chunks[i]->eqClass[(cnt + 1) % 2] = mid;
 124
 125     // If we created a group, we need to iterate the main loop again.
 126     if (mid != end)
 127       repeat = true;
 128
 129     begin = mid;
 130   }
 131 }
 132
 133 // Returns true if two sections' associative children are equal.
 134 bool ICF::assocEquals(const SectionChunk *a, const SectionChunk *b) {
 135   // Ignore associated metadata sections that don't participate in ICF, such as
 136   // debug info and CFGuard metadata.
 137   auto considerForICF = [](const SectionChunk &assoc) {
 138     StringRef Name = assoc.getSectionName();
 139     return !(Name.starts_with(".debug") || Name == ".gfids$y" ||
 140              Name == ".giats$y" || Name == ".gljmp$y");
 141   };
 142   auto ra = make_filter_range(a->children(), considerForICF);
 143   auto rb = make_filter_range(b->children(), considerForICF);
 144   return std::equal(ra.begin(), ra.end(), rb.begin(), rb.end(),
 145                     [&](const SectionChunk &ia, const SectionChunk &ib) {
 146                       return ia.eqClass[cnt % 2] == ib.eqClass[cnt % 2];
 147                     });
 148 }
 149
 150 // Compare "non-moving" part of two sections, namely everything
 151 // except relocation targets.
 152 bool ICF::equalsConstant(const SectionChunk *a, const SectionChunk *b) {
 153   if (a->relocsSize != b->relocsSize)
 154     return false;
 155
 156   // Compare relocations.
 157   auto eq = [&](const coff_relocation &r1, const coff_relocation &r2) {
 158     if (r1.Type != r2.Type ||
 159         r1.VirtualAddress != r2.VirtualAddress) {
 160       return false;
 161     }
 162     Symbol *b1 = a->file->getSymbol(r1.SymbolTableIndex);
 163     Symbol *b2 = b->file->getSymbol(r2.SymbolTableIndex);
 164     if (b1 == b2)
 165       return true;
 166     if (auto *d1 = dyn_cast<DefinedRegular>(b1))
 167       if (auto *d2 = dyn_cast<DefinedRegular>(b2))
 168         return d1->getValue() == d2->getValue() &&
 169                d1->getChunk()->eqClass[cnt % 2] == d2->getChunk()->eqClass[cnt % 2];
 170     return false;
 171   };
 172   if (!std::equal(a->getRelocs().begin(), a->getRelocs().end(),
 173                   b->getRelocs().begin(), eq))
 174     return false;
 175
 176   // Compare section attributes and contents.
 177   return a->getOutputCharacteristics() == b->getOutputCharacteristics() &&
 178          a->getSectionName() == b->getSectionName() &&
 179          a->header->SizeOfRawData == b->header->SizeOfRawData &&
 180          a->checksum == b->checksum && a->getContents() == b->getContents() &&
 181          a->getMachine() == b->getMachine() && assocEquals(a, b);
 182 }
 183
 184 // Compare "moving" part of two sections, namely relocation targets.
 185 bool ICF::equalsVariable(const SectionChunk *a, const SectionChunk *b) {
 186   // Compare relocations.
 187   auto eqSym = [&](Symbol *b1, Symbol *b2) {
 188     if (b1 == b2)
 189       return true;
 190     if (auto *d1 = dyn_cast<DefinedRegular>(b1))
 191       if (auto *d2 = dyn_cast<DefinedRegular>(b2))
 192         return d1->getChunk()->eqClass[cnt % 2] == d2->getChunk()->eqClass[cnt % 2];
 193     return false;
 194   };
 195   auto eq = [&](const coff_relocation &r1, const coff_relocation &r2) {
 196     Symbol *b1 = a->file->getSymbol(r1.SymbolTableIndex);
 197     Symbol *b2 = b->file->getSymbol(r2.SymbolTableIndex);
 198     return eqSym(b1, b2);
 199   };
 200
 201   Symbol *e1 = a->getEntryThunk();
 202   Symbol *e2 = b->getEntryThunk();
 203   if ((e1 || e2) && (!e1 || !e2 || !eqSym(e1, e2)))
 204     return false;
 205
 206   return std::equal(a->getRelocs().begin(), a->getRelocs().end(),
 207                     b->getRelocs().begin(), eq) &&
 208          assocEquals(a, b);
 209 }
 210
 211 // Find the first Chunk after Begin that has a different class from Begin.
 212 size_t ICF::findBoundary(size_t begin, size_t end) {
 213   for (size_t i = begin + 1; i < end; ++i)
 214     if (chunks[begin]->eqClass[cnt % 2] != chunks[i]->eqClass[cnt % 2])
 215       return i;
 216   return end;
 217 }
 218
 219 void ICF::forEachClassRange(size_t begin, size_t end,
 220                             std::function<void(size_t, size_t)> fn) {
 221   while (begin < end) {
 222     size_t mid = findBoundary(begin, end);
 223     fn(begin, mid);
 224     begin = mid;
 225   }
 226 }
 227
 228 // Call Fn on each class group.
 229 void ICF::forEachClass(std::function<void(size_t, size_t)> fn) {
 230   // If the number of sections are too small to use threading,
 231   // call Fn sequentially.
 232   if (chunks.size() < 1024) {
 233     forEachClassRange(0, chunks.size(), fn);
 234     ++cnt;
 235     return;
 236   }
 237
 238   // Shard into non-overlapping intervals, and call Fn in parallel.
 239   // The sharding must be completed before any calls to Fn are made
 240   // so that Fn can modify the Chunks in its shard without causing data
 241   // races.
 242   const size_t numShards = 256;
 243   size_t step = chunks.size() / numShards;
 244   size_t boundaries[numShards + 1];
 245   boundaries[0] = 0;
 246   boundaries[numShards] = chunks.size();
 247   parallelFor(1, numShards, [&](size_t i) {
 248     boundaries[i] = findBoundary((i - 1) * step, chunks.size());
 249   });
 250   parallelFor(1, numShards + 1, [&](size_t i) {
 251     if (boundaries[i - 1] < boundaries[i]) {
 252       forEachClassRange(boundaries[i - 1], boundaries[i], fn);
 253     }
 254   });
 255   ++cnt;
 256 }
 257
 258 // Merge identical COMDAT sections.
 259 // Two sections are considered the same if their section headers,
 260 // contents and relocations are all the same.
 261 void ICF::run() {
 262   llvm::TimeTraceScope timeScope("ICF");
 263   ScopedTimer t(ctx.icfTimer);
 264
 265   // Collect only mergeable sections and group by hash value.
 266   uint32_t nextId = 1;
 267   for (Chunk *c : ctx.symtab.getChunks()) {
 268     if (auto *sc = dyn_cast<SectionChunk>(c)) {
 269       if (isEligible(sc))
 270         chunks.push_back(sc);
 271       else
 272         sc->eqClass[0] = nextId++;
 273     }
 274   }
 275
 276   // Make sure that ICF doesn't merge sections that are being handled by string
 277   // tail merging.
 278   for (MergeChunk *mc : ctx.mergeChunkInstances)
 279     if (mc)
 280       for (SectionChunk *sc : mc->sections)
 281         sc->eqClass[0] = nextId++;
 282
 283   // Initially, we use hash values to partition sections.
 284   parallelForEach(chunks, [&](SectionChunk *sc) {
 285     sc->eqClass[0] = xxh3_64bits(sc->getContents());
 286   });
 287
 288   // Combine the hashes of the sections referenced by each section into its
 289   // hash.
 290   for (unsigned cnt = 0; cnt != 2; ++cnt) {
 291     parallelForEach(chunks, [&](SectionChunk *sc) {
 292       uint32_t hash = sc->eqClass[cnt % 2];
 293       for (Symbol *b : sc->symbols())
 294         if (auto *sym = dyn_cast_or_null<DefinedRegular>(b))
 295           hash += sym->getChunk()->eqClass[cnt % 2];
 296       // Set MSB to 1 to avoid collisions with non-hash classes.
 297       sc->eqClass[(cnt + 1) % 2] = hash | (1U << 31);
 298     });
 299   }
 300
 301   // From now on, sections in Chunks are ordered so that sections in
 302   // the same group are consecutive in the vector.
 303   llvm::stable_sort(chunks, [](const SectionChunk *a, const SectionChunk *b) {
 304     return a->eqClass[0] < b->eqClass[0];
 305   });
 306
 307   // Compare static contents and assign unique IDs for each static content.
 308   forEachClass([&](size_t begin, size_t end) { segregate(begin, end, true); });
 309
 310   // Split groups by comparing relocations until convergence is obtained.
 311   do {
 312     repeat = false;
 313     forEachClass(
 314         [&](size_t begin, size_t end) { segregate(begin, end, false); });
 315   } while (repeat);
 316
 317   log("ICF needed " + Twine(cnt) + " iterations");
 318
 319   // Merge sections in the same classes.
 320   forEachClass([&](size_t begin, size_t end) {
 321     if (end - begin == 1)
 322       return;
 323
 324     log("Selected " + chunks[begin]->getDebugName());
 325     for (size_t i = begin + 1; i < end; ++i) {
 326       log("  Removed " + chunks[i]->getDebugName());
 327       chunks[begin]->replace(chunks[i]);
 328     }
 329   });
 330 }
 331
 332 // Entry point to ICF.
 333 void doICF(COFFLinkerContext &ctx) { ICF(ctx).run(); }
 334
 335 } // namespace lld::coff