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