Lines Matching +full:non +full:- +full:identical
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))
166 // but are semantically read-only.
167 if ((s->flags & SHF_WRITE) && s->name != ".data.rel.ro" &&
168 !s->name.starts_with(".data.rel.ro."))
173 if (s->flags & SHF_LINK_ORDER)
184 if (s->name == ".init" || s->name == ".fini")
190 if (isValidCIdentifier(s->name))
218 size_t mid = bound - sections.begin();
225 sections[i]->eqClass[next] = eqClassBase + mid;
244 if (rai->r_offset != rbi->r_offset ||
245 rai->getType(config->isMips64EL) != rbi->getType(config->isMips64EL))
251 Symbol &sa = secA->file->getRelocTargetSym(*rai);
252 Symbol &sb = secB->file->getRelocTargetSym(*rbi);
264 if (!da || !db || da->scriptDefined || db->scriptDefined)
269 // considered different. This is because even if the sections are identical
271 if (da->isPreemptible || db->isPreemptible)
274 // Relocations referring to absolute symbols are constant-equal if their
276 if (!da->section && !db->section && da->value + addA == db->value + addB)
278 if (!da->section || !db->section)
281 if (da->section->kind() != db->section->kind())
284 // Relocations referring to InputSections are constant-equal if their
286 if (isa<InputSection>(da->section)) {
287 if (da->value + addA == db->value + addB)
292 // Relocations referring to MergeInputSections are constant-equal if their
294 auto *x = dyn_cast<MergeInputSection>(da->section);
297 auto *y = cast<MergeInputSection>(db->section);
298 if (x->getParent() != y->getParent())
302 sa.isSection() ? x->getOffset(addA) : x->getOffset(da->value) + addA;
304 sb.isSection() ? y->getOffset(addB) : y->getOffset(db->value) + addB;
312 // Compare "non-moving" part of two InputSections, namely everything
316 if (a->flags != b->flags || a->getSize() != b->getSize() ||
317 a->content() != b->content())
321 assert(a->getParent() && b->getParent());
322 if (a->getParent() != b->getParent())
325 const RelsOrRelas<ELFT> ra = a->template relsOrRelas<ELFT>();
326 const RelsOrRelas<ELFT> rb = b->template relsOrRelas<ELFT>();
344 // The two sections must be identical.
345 Symbol &sa = secA->file->getRelocTargetSym(*rai);
346 Symbol &sb = secB->file->getRelocTargetSym(*rbi);
353 // We already dealt with absolute and non-InputSection symbols in
356 if (!da->section)
358 auto *x = dyn_cast<InputSection>(da->section);
361 auto *y = cast<InputSection>(db->section);
365 if (x->eqClass[current] == 0)
367 if (x->eqClass[current] != y->eqClass[current])
377 const RelsOrRelas<ELFT> ra = a->template relsOrRelas<ELFT>();
378 const RelsOrRelas<ELFT> rb = b->template relsOrRelas<ELFT>();
387 uint32_t eqClass = sections[begin]->eqClass[current];
389 if (eqClass != sections[i]->eqClass[current])
423 // Shard into non-overlapping intervals, and call Fn in parallel.
434 boundaries[i] = findBoundary((i - 1) * step, sections.size());
438 if (boundaries[i - 1] < boundaries[i])
439 forEachClassRange(boundaries[i - 1], boundaries[i], fn);
449 uint32_t hash = isec->eqClass[cnt % 2];
451 Symbol &s = isec->file->getRelocTargetSym(rel);
453 if (auto *relSec = dyn_cast_or_null<InputSection>(d->section))
454 hash += relSec->eqClass[cnt % 2];
457 isec->eqClass[(cnt + 1) % 2] = hash | (1U << 31);
461 if (config->printIcfSections)
470 if (config->hasDynSymTab)
472 sym->isPreemptible = computeIsPreemptible(*sym);
474 // Two text sections may have identical content and relocations but different
480 // If two .gcc_except_table have identical semantics (usually identical
481 // content with PC-relative encoding), we will lose folding opportunity.
484 part.ehFrame->iterateFDEWithLSDA<ELFT>(
490 if (s && s->eqClass[0] == 0) {
496 s->eqClass[0] = s->eqClass[1] = ++uniqueId;
503 s->eqClass[0] = xxh3_64bits(s->content()) | (1U << 31);
511 const RelsOrRelas<ELFT> rels = s->template relsOrRelas<ELFT>();
524 return a->eqClass[0] < b->eqClass[0];
547 if (end - begin == 1)
551 print(" removing identical section " + toString(sections[i]));
552 sections[begin]->replace(sections[i]);
554 // At this point we know sections merged are fully identical and hence
557 for (InputSection *isec : sections[i]->dependentSections)
558 isec->markDead();
565 if (auto *sec = dyn_cast_or_null<InputSection>(d->section))
566 if (sec->repl != d->section) {
567 d->section = sec->repl;
568 d->folded = true;
574 for (Symbol *sym : file->getLocalSymbols())
580 for (SectionCommand *cmd : script->sectionCommands)
582 for (SectionCommand *subCmd : osd->osec.commands)
584 llvm::erase_if(isd->sections,
585 [](InputSection *isec) { return !isec->isLive(); });