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)
14 // In ICF, two sections are considered identical if they have the same
33 // terminates are considered identical. Here are details:
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
69 // [1] Safe ICF: Pointer Safe and Unwinding aware Identical Code Folding
73 //===----------------------------------------------------------------------===//
141   // it breaks the invariance that all possibly-identical sections must be
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()
184   if (s->name == ".init" || s->name == ".fini")  in isEligible()
190   if (isValidCIdentifier(s->name))  in isEligible()
218     size_t mid = bound - sections.begin();  in segregate()
225       sections[i]->eqClass[next] = eqClassBase + 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()
269     // considered different. This is because even if the sections are identical  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()
344     // The two sections must be identical.  in variableEq()
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()
423   // Shard into non-overlapping intervals, and call Fn in parallel.  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()
457   isec->eqClass[(cnt + 1) % 2] = hash | (1U << 31);  in combineRelocHashes()
461   if (config->printIcfSections)  in print()
470   if (config->hasDynSymTab)  in run()
472       sym->isPreemptible = computeIsPreemptible(*sym);  in run()
474   // Two text sections may have identical content and relocations but different  in run()
480   // If two .gcc_except_table have identical semantics (usually identical  in run()
481   // content with PC-relative encoding), we will lose folding opportunity.  in run()
484     part.ehFrame->iterateFDEWithLSDA<ELFT>(  in run()
490     if (s && s->eqClass[0] == 0) {  in run()
496         s->eqClass[0] = s->eqClass[1] = ++uniqueId;  in run()
503     s->eqClass[0] = xxh3_64bits(s->content()) | (1U << 31);  in run()
511       const RelsOrRelas<ELFT> rels = s->template relsOrRelas<ELFT>();  in run()
524     return a->eqClass[0] < b->eqClass[0];  in run()
547     if (end - begin == 1)  in run()
551       print("  removing identical section " + toString(sections[i]));  in run()
552       sections[begin]->replace(sections[i]);  in run()
554       // At this point we know sections merged are fully identical and hence  in run()
557       for (InputSection *isec : sections[i]->dependentSections)  in run()
558         isec->markDead();  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()
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()