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. This 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// In ICF, two sections are considered identical if they have the same 15// section flags, section data, and relocations. Relocations are tricky, 16// because two relocations are considered the same if they have the same 17// relocation types, values, and if they point to the same sections *in 18// terms of ICF*. 19// 20// Here is an example. If foo and bar defined below are compiled to the 21// same machine instructions, ICF can and should merge the two, although 22// their relocations point to each other. 23// 24// void foo() { bar(); } 25// void bar() { foo(); } 26// 27// If you merge the two, their relocations point to the same section and 28// thus you know they are mergeable, but how do you know they are 29// mergeable in the first place? This is not an easy problem to solve. 30// 31// What we are doing in LLD is to partition sections into equivalence 32// classes. Sections in the same equivalence class when the algorithm 33// terminates are considered identical. Here are details: 34// 35// 1. First, we partition sections using their hash values as keys. Hash 36// values contain section types, section contents and numbers of 37// relocations. During this step, relocation targets are not taken into 38// account. We just put sections that apparently differ into different 39// equivalence classes. 40// 41// 2. Next, for each equivalence class, we visit sections to compare 42// relocation targets. Relocation targets are considered equivalent if 43// their targets are in the same equivalence class. Sections with 44// different relocation targets are put into different equivalence 45// classes. 46// 47// 3. If we split an equivalence class in step 2, two relocations 48// previously target the same equivalence class may now target 49// different equivalence classes. Therefore, we repeat step 2 until a 50// convergence is obtained. 51// 52// 4. For each equivalence class C, pick an arbitrary section in C, and 53// merge all the other sections in C with it. 54// 55// For small programs, this algorithm needs 3-5 iterations. For large 56// programs such as Chromium, it takes more than 20 iterations. 57// 58// This algorithm was mentioned as an "optimistic algorithm" in [1], 59// though gold implements a different algorithm than this. 60// 61// We parallelize each step so that multiple threads can work on different 62// equivalence classes concurrently. That gave us a large performance 63// boost when applying ICF on large programs. For example, MSVC link.exe 64// or GNU gold takes 10-20 seconds to apply ICF on Chromium, whose output 65// size is about 1.5 GB, but LLD can finish it in less than 2 seconds on a 66// 2.8 GHz 40 core machine. Even without threading, LLD's ICF is still 67// faster than MSVC or gold though. 68// 69// [1] Safe ICF: Pointer Safe and Unwinding aware Identical Code Folding 70// in the Gold Linker 71// http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/36912.pdf 72// 73//===----------------------------------------------------------------------===// 74 75#include "ICF.h" 76#include "Config.h" 77#include "InputFiles.h" 78#include "LinkerScript.h" 79#include "OutputSections.h" 80#include "SymbolTable.h" 81#include "Symbols.h" 82#include "SyntheticSections.h" 83#include "llvm/BinaryFormat/ELF.h" 84#include "llvm/Object/ELF.h" 85#include "llvm/Support/Parallel.h" 86#include "llvm/Support/TimeProfiler.h" 87#include "llvm/Support/xxhash.h" 88#include <algorithm> 89#include <atomic> 90 91using namespace llvm; 92using namespace llvm::ELF; 93using namespace llvm::object; 94using namespace lld; 95using namespace lld::elf; 96 97namespace { 98template <class ELFT> class ICF { 99public: 100 void run(); 101 102private: 103 void segregate(size_t begin, size_t end, uint32_t eqClassBase, bool constant); 104 105 template <class RelTy> 106 bool constantEq(const InputSection *a, ArrayRef<RelTy> relsA, 107 const InputSection *b, ArrayRef<RelTy> relsB); 108 109 template <class RelTy> 110 bool variableEq(const InputSection *a, ArrayRef<RelTy> relsA, 111 const InputSection *b, ArrayRef<RelTy> relsB); 112 113 bool equalsConstant(const InputSection *a, const InputSection *b); 114 bool equalsVariable(const InputSection *a, const InputSection *b); 115 116 size_t findBoundary(size_t begin, size_t end); 117 118 void forEachClassRange(size_t begin, size_t end, 119 llvm::function_ref<void(size_t, size_t)> fn); 120 121 void forEachClass(llvm::function_ref<void(size_t, size_t)> fn); 122 123 SmallVector<InputSection *, 0> sections; 124 125 // We repeat the main loop while `Repeat` is true. 126 std::atomic<bool> repeat; 127 128 // The main loop counter. 129 int cnt = 0; 130 131 // We have two locations for equivalence classes. On the first iteration 132 // of the main loop, Class[0] has a valid value, and Class[1] contains 133 // garbage. We read equivalence classes from slot 0 and write to slot 1. 134 // So, Class[0] represents the current class, and Class[1] represents 135 // the next class. On each iteration, we switch their roles and use them 136 // alternately. 137 // 138 // Why are we doing this? Recall that other threads may be working on 139 // other equivalence classes in parallel. They may read sections that we 140 // are updating. We cannot update equivalence classes in place because 141 // it breaks the invariance that all possibly-identical sections must be 142 // in the same equivalence class at any moment. In other words, the for 143 // loop to update equivalence classes is not atomic, and that is 144 // observable from other threads. By writing new classes to other 145 // places, we can keep the invariance. 146 // 147 // Below, `Current` has the index of the current class, and `Next` has 148 // the index of the next class. If threading is enabled, they are either 149 // (0, 1) or (1, 0). 150 // 151 // Note on single-thread: if that's the case, they are always (0, 0) 152 // because we can safely read the next class without worrying about race 153 // conditions. Using the same location makes this algorithm converge 154 // faster because it uses results of the same iteration earlier. 155 int current = 0; 156 int next = 0; 157}; 158} 159 160// Returns true if section S is subject of ICF. 161static bool isEligible(InputSection *s) { 162 if (!s->isLive() || s->keepUnique || !(s->flags & SHF_ALLOC)) 163 return false; 164 165 // Don't merge writable sections. .data.rel.ro sections are marked as writable 166 // but are semantically read-only. 167 if ((s->flags & SHF_WRITE) && s->name != ".data.rel.ro" && 168 !s->name.startswith(".data.rel.ro.")) 169 return false; 170 171 // SHF_LINK_ORDER sections are ICF'd as a unit with their dependent sections, 172 // so we don't consider them for ICF individually. 173 if (s->flags & SHF_LINK_ORDER) 174 return false; 175 176 // Don't merge synthetic sections as their Data member is not valid and empty. 177 // The Data member needs to be valid for ICF as it is used by ICF to determine 178 // the equality of section contents. 179 if (isa<SyntheticSection>(s)) 180 return false; 181 182 // .init and .fini contains instructions that must be executed to initialize 183 // and finalize the process. They cannot and should not be merged. 184 if (s->name == ".init" || s->name == ".fini") 185 return false; 186 187 // A user program may enumerate sections named with a C identifier using 188 // __start_* and __stop_* symbols. We cannot ICF any such sections because 189 // that could change program semantics. 190 if (isValidCIdentifier(s->name)) 191 return false; 192 193 return true; 194} 195 196// Split an equivalence class into smaller classes. 197template <class ELFT> 198void ICF<ELFT>::segregate(size_t begin, size_t end, uint32_t eqClassBase, 199 bool constant) { 200 // This loop rearranges sections in [Begin, End) so that all sections 201 // that are equal in terms of equals{Constant,Variable} are contiguous 202 // in [Begin, End). 203 // 204 // The algorithm is quadratic in the worst case, but that is not an 205 // issue in practice because the number of the distinct sections in 206 // each range is usually very small. 207 208 while (begin < end) { 209 // Divide [Begin, End) into two. Let Mid be the start index of the 210 // second group. 211 auto bound = 212 std::stable_partition(sections.begin() + begin + 1, 213 sections.begin() + end, [&](InputSection *s) { 214 if (constant) 215 return equalsConstant(sections[begin], s); 216 return equalsVariable(sections[begin], s); 217 }); 218 size_t mid = bound - sections.begin(); 219 220 // Now we split [Begin, End) into [Begin, Mid) and [Mid, End) by 221 // updating the sections in [Begin, Mid). We use Mid as the basis for 222 // the equivalence class ID because every group ends with a unique index. 223 // Add this to eqClassBase to avoid equality with unique IDs. 224 for (size_t i = begin; i < mid; ++i) 225 sections[i]->eqClass[next] = eqClassBase + mid; 226 227 // If we created a group, we need to iterate the main loop again. 228 if (mid != end) 229 repeat = true; 230 231 begin = mid; 232 } 233} 234 235// Compare two lists of relocations. 236template <class ELFT> 237template <class RelTy> 238bool ICF<ELFT>::constantEq(const InputSection *secA, ArrayRef<RelTy> ra, 239 const InputSection *secB, ArrayRef<RelTy> rb) { 240 if (ra.size() != rb.size()) 241 return false; 242 for (size_t i = 0; i < ra.size(); ++i) { 243 if (ra[i].r_offset != rb[i].r_offset || 244 ra[i].getType(config->isMips64EL) != rb[i].getType(config->isMips64EL)) 245 return false; 246 247 uint64_t addA = getAddend<ELFT>(ra[i]); 248 uint64_t addB = getAddend<ELFT>(rb[i]); 249 250 Symbol &sa = secA->template getFile<ELFT>()->getRelocTargetSym(ra[i]); 251 Symbol &sb = secB->template getFile<ELFT>()->getRelocTargetSym(rb[i]); 252 if (&sa == &sb) { 253 if (addA == addB) 254 continue; 255 return false; 256 } 257 258 auto *da = dyn_cast<Defined>(&sa); 259 auto *db = dyn_cast<Defined>(&sb); 260 261 // Placeholder symbols generated by linker scripts look the same now but 262 // may have different values later. 263 if (!da || !db || da->scriptDefined || db->scriptDefined) 264 return false; 265 266 // When comparing a pair of relocations, if they refer to different symbols, 267 // and either symbol is preemptible, the containing sections should be 268 // considered different. This is because even if the sections are identical 269 // in this DSO, they may not be after preemption. 270 if (da->isPreemptible || db->isPreemptible) 271 return false; 272 273 // Relocations referring to absolute symbols are constant-equal if their 274 // values are equal. 275 if (!da->section && !db->section && da->value + addA == db->value + addB) 276 continue; 277 if (!da->section || !db->section) 278 return false; 279 280 if (da->section->kind() != db->section->kind()) 281 return false; 282 283 // Relocations referring to InputSections are constant-equal if their 284 // section offsets are equal. 285 if (isa<InputSection>(da->section)) { 286 if (da->value + addA == db->value + addB) 287 continue; 288 return false; 289 } 290 291 // Relocations referring to MergeInputSections are constant-equal if their 292 // offsets in the output section are equal. 293 auto *x = dyn_cast<MergeInputSection>(da->section); 294 if (!x) 295 return false; 296 auto *y = cast<MergeInputSection>(db->section); 297 if (x->getParent() != y->getParent()) 298 return false; 299 300 uint64_t offsetA = 301 sa.isSection() ? x->getOffset(addA) : x->getOffset(da->value) + addA; 302 uint64_t offsetB = 303 sb.isSection() ? y->getOffset(addB) : y->getOffset(db->value) + addB; 304 if (offsetA != offsetB) 305 return false; 306 } 307 308 return true; 309} 310 311// Compare "non-moving" part of two InputSections, namely everything 312// except relocation targets. 313template <class ELFT> 314bool ICF<ELFT>::equalsConstant(const InputSection *a, const InputSection *b) { 315 if (a->flags != b->flags || a->getSize() != b->getSize() || 316 a->content() != b->content()) 317 return false; 318 319 // If two sections have different output sections, we cannot merge them. 320 assert(a->getParent() && b->getParent()); 321 if (a->getParent() != b->getParent()) 322 return false; 323 324 const RelsOrRelas<ELFT> ra = a->template relsOrRelas<ELFT>(); 325 const RelsOrRelas<ELFT> rb = b->template relsOrRelas<ELFT>(); 326 return ra.areRelocsRel() || rb.areRelocsRel() 327 ? constantEq(a, ra.rels, b, rb.rels) 328 : constantEq(a, ra.relas, b, rb.relas); 329} 330 331// Compare two lists of relocations. Returns true if all pairs of 332// relocations point to the same section in terms of ICF. 333template <class ELFT> 334template <class RelTy> 335bool ICF<ELFT>::variableEq(const InputSection *secA, ArrayRef<RelTy> ra, 336 const InputSection *secB, ArrayRef<RelTy> rb) { 337 assert(ra.size() == rb.size()); 338 339 for (size_t i = 0; i < ra.size(); ++i) { 340 // The two sections must be identical. 341 Symbol &sa = secA->template getFile<ELFT>()->getRelocTargetSym(ra[i]); 342 Symbol &sb = secB->template getFile<ELFT>()->getRelocTargetSym(rb[i]); 343 if (&sa == &sb) 344 continue; 345 346 auto *da = cast<Defined>(&sa); 347 auto *db = cast<Defined>(&sb); 348 349 // We already dealt with absolute and non-InputSection symbols in 350 // constantEq, and for InputSections we have already checked everything 351 // except the equivalence class. 352 if (!da->section) 353 continue; 354 auto *x = dyn_cast<InputSection>(da->section); 355 if (!x) 356 continue; 357 auto *y = cast<InputSection>(db->section); 358 359 // Sections that are in the special equivalence class 0, can never be the 360 // same in terms of the equivalence class. 361 if (x->eqClass[current] == 0) 362 return false; 363 if (x->eqClass[current] != y->eqClass[current]) 364 return false; 365 }; 366 367 return true; 368} 369 370// Compare "moving" part of two InputSections, namely relocation targets. 371template <class ELFT> 372bool ICF<ELFT>::equalsVariable(const InputSection *a, const InputSection *b) { 373 const RelsOrRelas<ELFT> ra = a->template relsOrRelas<ELFT>(); 374 const RelsOrRelas<ELFT> rb = b->template relsOrRelas<ELFT>(); 375 return ra.areRelocsRel() || rb.areRelocsRel() 376 ? variableEq(a, ra.rels, b, rb.rels) 377 : variableEq(a, ra.relas, b, rb.relas); 378} 379 380template <class ELFT> size_t ICF<ELFT>::findBoundary(size_t begin, size_t end) { 381 uint32_t eqClass = sections[begin]->eqClass[current]; 382 for (size_t i = begin + 1; i < end; ++i) 383 if (eqClass != sections[i]->eqClass[current]) 384 return i; 385 return end; 386} 387 388// Sections in the same equivalence class are contiguous in Sections 389// vector. Therefore, Sections vector can be considered as contiguous 390// groups of sections, grouped by the class. 391// 392// This function calls Fn on every group within [Begin, End). 393template <class ELFT> 394void ICF<ELFT>::forEachClassRange(size_t begin, size_t end, 395 llvm::function_ref<void(size_t, size_t)> fn) { 396 while (begin < end) { 397 size_t mid = findBoundary(begin, end); 398 fn(begin, mid); 399 begin = mid; 400 } 401} 402 403// Call Fn on each equivalence class. 404template <class ELFT> 405void ICF<ELFT>::forEachClass(llvm::function_ref<void(size_t, size_t)> fn) { 406 // If threading is disabled or the number of sections are 407 // too small to use threading, call Fn sequentially. 408 if (parallel::strategy.ThreadsRequested == 1 || sections.size() < 1024) { 409 forEachClassRange(0, sections.size(), fn); 410 ++cnt; 411 return; 412 } 413 414 current = cnt % 2; 415 next = (cnt + 1) % 2; 416 417 // Shard into non-overlapping intervals, and call Fn in parallel. 418 // The sharding must be completed before any calls to Fn are made 419 // so that Fn can modify the Chunks in its shard without causing data 420 // races. 421 const size_t numShards = 256; 422 size_t step = sections.size() / numShards; 423 size_t boundaries[numShards + 1]; 424 boundaries[0] = 0; 425 boundaries[numShards] = sections.size(); 426 427 parallelFor(1, numShards, [&](size_t i) { 428 boundaries[i] = findBoundary((i - 1) * step, sections.size()); 429 }); 430 431 parallelFor(1, numShards + 1, [&](size_t i) { 432 if (boundaries[i - 1] < boundaries[i]) 433 forEachClassRange(boundaries[i - 1], boundaries[i], fn); 434 }); 435 ++cnt; 436} 437 438// Combine the hashes of the sections referenced by the given section into its 439// hash. 440template <class ELFT, class RelTy> 441static void combineRelocHashes(unsigned cnt, InputSection *isec, 442 ArrayRef<RelTy> rels) { 443 uint32_t hash = isec->eqClass[cnt % 2]; 444 for (RelTy rel : rels) { 445 Symbol &s = isec->template getFile<ELFT>()->getRelocTargetSym(rel); 446 if (auto *d = dyn_cast<Defined>(&s)) 447 if (auto *relSec = dyn_cast_or_null<InputSection>(d->section)) 448 hash += relSec->eqClass[cnt % 2]; 449 } 450 // Set MSB to 1 to avoid collisions with unique IDs. 451 isec->eqClass[(cnt + 1) % 2] = hash | (1U << 31); 452} 453 454static void print(const Twine &s) { 455 if (config->printIcfSections) 456 message(s); 457} 458 459// The main function of ICF. 460template <class ELFT> void ICF<ELFT>::run() { 461 // Compute isPreemptible early. We may add more symbols later, so this loop 462 // cannot be merged with the later computeIsPreemptible() pass which is used 463 // by scanRelocations(). 464 if (config->hasDynSymTab) 465 for (Symbol *sym : symtab.getSymbols()) 466 sym->isPreemptible = computeIsPreemptible(*sym); 467 468 // Two text sections may have identical content and relocations but different 469 // LSDA, e.g. the two functions may have catch blocks of different types. If a 470 // text section is referenced by a .eh_frame FDE with LSDA, it is not 471 // eligible. This is implemented by iterating over CIE/FDE and setting 472 // eqClass[0] to the referenced text section from a live FDE. 473 // 474 // If two .gcc_except_table have identical semantics (usually identical 475 // content with PC-relative encoding), we will lose folding opportunity. 476 uint32_t uniqueId = 0; 477 for (Partition &part : partitions) 478 part.ehFrame->iterateFDEWithLSDA<ELFT>( 479 [&](InputSection &s) { s.eqClass[0] = s.eqClass[1] = ++uniqueId; }); 480 481 // Collect sections to merge. 482 for (InputSectionBase *sec : ctx.inputSections) { 483 auto *s = dyn_cast<InputSection>(sec); 484 if (s && s->eqClass[0] == 0) { 485 if (isEligible(s)) 486 sections.push_back(s); 487 else 488 // Ineligible sections are assigned unique IDs, i.e. each section 489 // belongs to an equivalence class of its own. 490 s->eqClass[0] = s->eqClass[1] = ++uniqueId; 491 } 492 } 493 494 // Initially, we use hash values to partition sections. 495 parallelForEach(sections, [&](InputSection *s) { 496 // Set MSB to 1 to avoid collisions with unique IDs. 497 s->eqClass[0] = xxHash64(s->content()) | (1U << 31); 498 }); 499 500 // Perform 2 rounds of relocation hash propagation. 2 is an empirical value to 501 // reduce the average sizes of equivalence classes, i.e. segregate() which has 502 // a large time complexity will have less work to do. 503 for (unsigned cnt = 0; cnt != 2; ++cnt) { 504 parallelForEach(sections, [&](InputSection *s) { 505 const RelsOrRelas<ELFT> rels = s->template relsOrRelas<ELFT>(); 506 if (rels.areRelocsRel()) 507 combineRelocHashes<ELFT>(cnt, s, rels.rels); 508 else 509 combineRelocHashes<ELFT>(cnt, s, rels.relas); 510 }); 511 } 512 513 // From now on, sections in Sections vector are ordered so that sections 514 // in the same equivalence class are consecutive in the vector. 515 llvm::stable_sort(sections, [](const InputSection *a, const InputSection *b) { 516 return a->eqClass[0] < b->eqClass[0]; 517 }); 518 519 // Compare static contents and assign unique equivalence class IDs for each 520 // static content. Use a base offset for these IDs to ensure no overlap with 521 // the unique IDs already assigned. 522 uint32_t eqClassBase = ++uniqueId; 523 forEachClass([&](size_t begin, size_t end) { 524 segregate(begin, end, eqClassBase, true); 525 }); 526 527 // Split groups by comparing relocations until convergence is obtained. 528 do { 529 repeat = false; 530 forEachClass([&](size_t begin, size_t end) { 531 segregate(begin, end, eqClassBase, false); 532 }); 533 } while (repeat); 534 535 log("ICF needed " + Twine(cnt) + " iterations"); 536 537 // Merge sections by the equivalence class. 538 forEachClassRange(0, sections.size(), [&](size_t begin, size_t end) { 539 if (end - begin == 1) 540 return; 541 print("selected section " + toString(sections[begin])); 542 for (size_t i = begin + 1; i < end; ++i) { 543 print(" removing identical section " + toString(sections[i])); 544 sections[begin]->replace(sections[i]); 545 546 // At this point we know sections merged are fully identical and hence 547 // we want to remove duplicate implicit dependencies such as link order 548 // and relocation sections. 549 for (InputSection *isec : sections[i]->dependentSections) 550 isec->markDead(); 551 } 552 }); 553 554 // Change Defined symbol's section field to the canonical one. 555 auto fold = [](Symbol *sym) { 556 if (auto *d = dyn_cast<Defined>(sym)) 557 if (auto *sec = dyn_cast_or_null<InputSection>(d->section)) 558 if (sec->repl != d->section) { 559 d->section = sec->repl; 560 d->folded = true; 561 } 562 }; 563 for (Symbol *sym : symtab.getSymbols()) 564 fold(sym); 565 parallelForEach(ctx.objectFiles, [&](ELFFileBase *file) { 566 for (Symbol *sym : file->getLocalSymbols()) 567 fold(sym); 568 }); 569 570 // InputSectionDescription::sections is populated by processSectionCommands(). 571 // ICF may fold some input sections assigned to output sections. Remove them. 572 for (SectionCommand *cmd : script->sectionCommands) 573 if (auto *osd = dyn_cast<OutputDesc>(cmd)) 574 for (SectionCommand *subCmd : osd->osec.commands) 575 if (auto *isd = dyn_cast<InputSectionDescription>(subCmd)) 576 llvm::erase_if(isd->sections, 577 [](InputSection *isec) { return !isec->isLive(); }); 578} 579 580// ICF entry point function. 581template <class ELFT> void elf::doIcf() { 582 llvm::TimeTraceScope timeScope("ICF"); 583 ICF<ELFT>().run(); 584} 585 586template void elf::doIcf<ELF32LE>(); 587template void elf::doIcf<ELF32BE>(); 588template void elf::doIcf<ELF64LE>(); 589template void elf::doIcf<ELF64BE>(); 590