1 //===- ICF.cpp ------------------------------------------------------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
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
17 // relocation types, values, and if they point to the same sections *in
20 // Here is an example. If foo and bar defined below are compiled to the
22 // their relocations point to each other.
27 // If you merge the two, their relocations point to the same section and
29 // mergeable in the first place? This is not an easy problem to solve.
31 // What we are doing in LLD is to partition sections into equivalence
41 // 2. Next, for each equivalence class, we visit sections to compare
55 // For small programs, this algorithm needs 3-5 iterations. For large
64 // or GNU gold takes 10-20 seconds to apply ICF on Chromium, whose output
73 //===----------------------------------------------------------------------===//
133   // garbage. We read equivalence classes from slot 0 and write to slot 1.
141   // it breaks the invariance that all possibly-identical sections must be
143   // loop to update equivalence classes is not atomic, and that is
144   // observable from other threads. By writing new classes to other
151   // Note on single-thread: if that's the case, they are always (0, 0)
162   if (!s->isLive() || s->keepUnique || !(s->flags & SHF_ALLOC))  in isEligible()
166   // but are semantically read-only.  in isEligible()
167   if ((s->flags & SHF_WRITE) && s->name != ".data.rel.ro" &&  in isEligible()
168       !s->name.starts_with(".data.rel.ro."))  in isEligible()
173   if (s->flags & SHF_LINK_ORDER)  in isEligible()
177   // The Data member needs to be valid for ICF as it is used by ICF to determine  in isEligible()
182   // .init and .fini contains instructions that must be executed to initialize  in isEligible()
184   if (s->name == ".init" || s->name == ".fini")  in isEligible()
190   if (isValidCIdentifier(s->name))  in isEligible()
209     // Divide [Begin, End) into two. Let Mid be the start index of the  in segregate()
218     size_t mid = bound - sections.begin();  in segregate()  local
220     // Now we split [Begin, End) into [Begin, Mid) and [Mid, End) by  in segregate()
221     // updating the sections in [Begin, Mid). We use Mid as the basis for  in segregate()
223     // Add this to eqClassBase to avoid equality with unique IDs.  in segregate()
224     for (size_t i = begin; i < mid; ++i)  in segregate()
225       sections[i]->eqClass[next] = eqClassBase + mid;  in segregate()
227     // If we created a group, we need to iterate the main loop again.  in segregate()
228     if (mid != end)  in segregate()
231     begin = mid;  in segregate()
244     if (rai->r_offset != rbi->r_offset ||  in constantEq()
245         rai->getType(config->isMips64EL) != rbi->getType(config->isMips64EL))  in constantEq()
251     Symbol &sa = secA->file->getRelocTargetSym(*rai);  in constantEq()
252     Symbol &sb = secB->file->getRelocTargetSym(*rbi);  in constantEq()
264     if (!da || !db || da->scriptDefined || db->scriptDefined)  in constantEq()
267     // When comparing a pair of relocations, if they refer to different symbols,  in constantEq()
271     if (da->isPreemptible || db->isPreemptible)  in constantEq()
274     // Relocations referring to absolute symbols are constant-equal if their  in constantEq()
276     if (!da->section && !db->section && da->value + addA == db->value + addB)  in constantEq()
278     if (!da->section || !db->section)  in constantEq()
281     if (da->section->kind() != db->section->kind())  in constantEq()
284     // Relocations referring to InputSections are constant-equal if their  in constantEq()
286     if (isa<InputSection>(da->section)) {  in constantEq()
287       if (da->value + addA == db->value + addB)  in constantEq()
292     // Relocations referring to MergeInputSections are constant-equal if their  in constantEq()
294     auto *x = dyn_cast<MergeInputSection>(da->section);  in constantEq()
297     auto *y = cast<MergeInputSection>(db->section);  in constantEq()
298     if (x->getParent() != y->getParent())  in constantEq()
302         sa.isSection() ? x->getOffset(addA) : x->getOffset(da->value) + addA;  in constantEq()
304         sb.isSection() ? y->getOffset(addB) : y->getOffset(db->value) + addB;  in constantEq()
312 // Compare "non-moving" part of two InputSections, namely everything
316   if (a->flags != b->flags || a->getSize() != b->getSize() ||  in equalsConstant()
317       a->content() != b->content())  in equalsConstant()
321   assert(a->getParent() && b->getParent());  in equalsConstant()
322   if (a->getParent() != b->getParent())  in equalsConstant()
325   const RelsOrRelas<ELFT> ra = a->template relsOrRelas<ELFT>();  in equalsConstant()
326   const RelsOrRelas<ELFT> rb = b->template relsOrRelas<ELFT>();  in equalsConstant()
335 // relocations point to the same section in terms of ICF.
345     Symbol &sa = secA->file->getRelocTargetSym(*rai);  in variableEq()
346     Symbol &sb = secB->file->getRelocTargetSym(*rbi);  in variableEq()
353     // We already dealt with absolute and non-InputSection symbols in  in variableEq()
356     if (!da->section)  in variableEq()
358     auto *x = dyn_cast<InputSection>(da->section);  in variableEq()
361     auto *y = cast<InputSection>(db->section);  in variableEq()
365     if (x->eqClass[current] == 0)  in variableEq()
367     if (x->eqClass[current] != y->eqClass[current])  in variableEq()
377   const RelsOrRelas<ELFT> ra = a->template relsOrRelas<ELFT>();  in equalsVariable()
378   const RelsOrRelas<ELFT> rb = b->template relsOrRelas<ELFT>();  in equalsVariable()
387   uint32_t eqClass = sections[begin]->eqClass[current];  in findBoundary()
389     if (eqClass != sections[i]->eqClass[current])  in findBoundary()
403     size_t mid = findBoundary(begin, end);  in forEachClassRange()  local
404     fn(begin, mid);  in forEachClassRange()
405     begin = mid;  in forEachClassRange()
413   // too small to use threading, call Fn sequentially.  in forEachClass()
423   // Shard into non-overlapping intervals, and call Fn in parallel.  in forEachClass()
424   // The sharding must be completed before any calls to Fn are made  in forEachClass()
434     boundaries[i] = findBoundary((i - 1) * step, sections.size());  in forEachClass()
438     if (boundaries[i - 1] < boundaries[i])  in forEachClass()
439       forEachClassRange(boundaries[i - 1], boundaries[i], fn);  in forEachClass()
449   uint32_t hash = isec->eqClass[cnt % 2];  in combineRelocHashes()
451     Symbol &s = isec->file->getRelocTargetSym(rel);  in combineRelocHashes()
453       if (auto *relSec = dyn_cast_or_null<InputSection>(d->section))  in combineRelocHashes()
454         hash += relSec->eqClass[cnt % 2];  in combineRelocHashes()
456   // Set MSB to 1 to avoid collisions with unique IDs.  in combineRelocHashes()
457   isec->eqClass[(cnt + 1) % 2] = hash | (1U << 31);  in combineRelocHashes()
461   if (config->printIcfSections)  in print()
467   // Compute isPreemptible early. We may add more symbols later, so this loop  in run()
470   if (config->hasDynSymTab)  in run()
472       sym->isPreemptible = computeIsPreemptible(*sym);  in run()
478   // eqClass[0] to the referenced text section from a live FDE.  in run()
481   // content with PC-relative encoding), we will lose folding opportunity.  in run()
484     part.ehFrame->iterateFDEWithLSDA<ELFT>(  in run()
487   // Collect sections to merge.  in run()
490     if (s && s->eqClass[0] == 0) {  in run()
495         // belongs to an equivalence class of its own.  in run()
496         s->eqClass[0] = s->eqClass[1] = ++uniqueId;  in run()
500   // Initially, we use hash values to partition sections.  in run()
502     // Set MSB to 1 to avoid collisions with unique IDs.  in run()
503     s->eqClass[0] = xxh3_64bits(s->content()) | (1U << 31);  in run()
506   // Perform 2 rounds of relocation hash propagation. 2 is an empirical value to  in run()
508   // a large time complexity will have less work to do.  in run()
511       const RelsOrRelas<ELFT> rels = s->template relsOrRelas<ELFT>();  in run()
524     return a->eqClass[0] < b->eqClass[0];  in run()
528   // static content. Use a base offset for these IDs to ensure no overlap with  in run()
547     if (end - begin == 1)  in run()
552       sections[begin]->replace(sections[i]);  in run()
555       // we want to remove duplicate implicit dependencies such as link order  in run()
557       for (InputSection *isec : sections[i]->dependentSections)  in run()
558         isec->markDead();  in run()
562   // Change Defined symbol's section field to the canonical one.  in run()
565       if (auto *sec = dyn_cast_or_null<InputSection>(d->section))  in run()
566         if (sec->repl != d->section) {  in run()
567           d->section = sec->repl;  in run()
568           d->folded = true;  in run()
574     for (Symbol *sym : file->getLocalSymbols())  in run()
579   // ICF may fold some input sections assigned to output sections. Remove them.  in run()
580   for (SectionCommand *cmd : script->sectionCommands)  in run()
582       for (SectionCommand *subCmd : osd->osec.commands)  in run()
584           llvm::erase_if(isd->sections,  in run()
585                          [](InputSection *isec) { return !isec->isLive(); });  in run()