From 3313b84481f3caa36cee3071d1379f8b9a028715 Mon Sep 17 00:00:00 2001 From: Jez Ng Date: Fri, 23 Jul 2021 11:33:28 -0400 Subject: [PATCH] [lld-macho] ICF: Do more work in equalsConstant, less in equalsVariable In particular, relocations to absolute symbols or literal sections can be handled in equalsConstant(), since their output addresses will not change across each iteration of ICF. Offsets and addends can also be dealt with entirely in equalsConstant(), making the code somewhat easier to reason about. Only ConcatInputSections need to be handled in equalsVariable(). LLD-ELF's implementation takes a similar approach. Although this should make ICF do less work, in practice it seems like there is no stat sig difference in time taken when linking chromium_framework. This refactor is motivated by an upcoming diff which improves ICF's handling of addends. Reviewed By: #lld-macho, gkm Differential Revision: https://reviews.llvm.org/D106212 --- lld/MachO/ICF.cpp | 107 +++++++++++++++++++++++++++++++----------------------- 1 file changed, 61 insertions(+), 46 deletions(-) diff --git a/lld/MachO/ICF.cpp b/lld/MachO/ICF.cpp index 9a41bb2..370a325 100644 --- a/lld/MachO/ICF.cpp +++ b/lld/MachO/ICF.cpp @@ -77,7 +77,8 @@ ICF::ICF(std::vector &inputs) { static unsigned icfPass = 0; static std::atomic icfRepeat{false}; -// Compare everything except the relocation referents +// Compare "non-moving" parts of two ConcatInputSections, namely everything +// except references to other ConcatInputSections. static bool equalsConstant(const ConcatInputSection *ia, const ConcatInputSection *ib) { // We can only fold within the same OutputSection. @@ -89,7 +90,7 @@ static bool equalsConstant(const ConcatInputSection *ia, return false; if (ia->relocs.size() != ib->relocs.size()) return false; - auto f = [&](const Reloc &ra, const Reloc &rb) { + auto f = [](const Reloc &ra, const Reloc &rb) { if (ra.type != rb.type) return false; if (ra.pcrel != rb.pcrel) @@ -101,65 +102,79 @@ static bool equalsConstant(const ConcatInputSection *ia, if (ra.addend != rb.addend) return false; if (ra.referent.is() != rb.referent.is()) - return false; // a nice place to breakpoint - return true; - }; - return std::equal(ia->relocs.begin(), ia->relocs.end(), ib->relocs.begin(), - f); -} + return false; -// Compare only the relocation referents -static bool equalsVariable(const ConcatInputSection *ia, - const ConcatInputSection *ib) { - assert(ia->relocs.size() == ib->relocs.size()); - auto f = [&](const Reloc &ra, const Reloc &rb) { - if (ra.referent == rb.referent) - return true; + InputSection *isecA, *isecB; if (ra.referent.is()) { const auto *sa = ra.referent.get(); const auto *sb = rb.referent.get(); if (sa->kind() != sb->kind()) return false; if (isa(sa)) { - const auto *da = dyn_cast(sa); - const auto *db = dyn_cast(sb); + const auto *da = cast(sa); + const auto *db = cast(sb); if (da->isec && db->isec) { - if (da->isec->kind() != db->isec->kind()) - return false; - if (const auto *isecA = dyn_cast(da->isec)) { - const auto *isecB = cast(db->isec); - return da->value == db->value && isecA->icfEqClass[icfPass % 2] == - isecB->icfEqClass[icfPass % 2]; - } - // Else we have two literal sections. References to them are - // constant-equal if their offsets in the output section are equal. - return da->isec->parent == db->isec->parent && - da->isec->getOffset(da->value) == - db->isec->getOffset(db->value); + isecA = da->isec; + isecB = db->isec; + } else { + assert(da->isAbsolute() && db->isAbsolute()); + return da->value == db->value; } - assert(da->isAbsolute() && db->isAbsolute()); - return da->value == db->value; - } else if (isa(sa)) { - // There is one DylibSymbol per gotIndex and we already checked for - // symbol equality, thus we know that these must be different. - return false; } else { - llvm_unreachable("equalsVariable symbol kind"); + assert(isa(sa)); + return sa == sb; } } else { + isecA = ra.referent.get(); + isecB = rb.referent.get(); + } + + if (isecA->parent != isecB->parent) + return false; + // Sections with identical parents should be of the same kind. + assert(isecA->kind() == isecB->kind()); + // We will compare ConcatInputSection contents in equalsVariable. + if (isa(isecA)) + return true; + // Else we have two literal sections. References to them are equal iff their + // offsets in the output section are equal. + return isecA->getOffset(ra.addend) == isecB->getOffset(rb.addend); + }; + return std::equal(ia->relocs.begin(), ia->relocs.end(), ib->relocs.begin(), + f); +} + +// Compare the "moving" parts of two ConcatInputSections -- i.e. everything not +// handled by equalsConstant(). +static bool equalsVariable(const ConcatInputSection *ia, + const ConcatInputSection *ib) { + assert(ia->relocs.size() == ib->relocs.size()); + auto f = [](const Reloc &ra, const Reloc &rb) { + // We already filtered out mismatching values/addends in equalsConstant. + if (ra.referent == rb.referent) + return true; + const ConcatInputSection *isecA, *isecB; + if (ra.referent.is()) { + // Matching DylibSymbols are already filtered out by the + // identical-referent check above. Non-matching DylibSymbols were filtered + // out in equalsConstant(). So we can safely cast to Defined here. + const auto *da = cast(ra.referent.get()); + const auto *db = cast(rb.referent.get()); + if (da->isAbsolute()) + return true; + isecA = dyn_cast(da->isec); + if (!isecA) + return true; // literal sections were checked in equalsConstant. + isecB = cast(db->isec); + } else { const auto *sa = ra.referent.get(); const auto *sb = rb.referent.get(); - if (sa->kind() != sb->kind()) - return false; - if (const auto *isecA = dyn_cast(sa)) { - const auto *isecB = cast(sb); - return isecA->icfEqClass[icfPass % 2] == isecB->icfEqClass[icfPass % 2]; - } else { - assert(isa(sa) || - isa(sa)); - return sa->getOffset(ra.addend) == sb->getOffset(rb.addend); - } + isecA = dyn_cast(sa); + if (!isecA) + return true; + isecB = cast(sb); } + return isecA->icfEqClass[icfPass % 2] == isecB->icfEqClass[icfPass % 2]; }; return std::equal(ia->relocs.begin(), ia->relocs.end(), ib->relocs.begin(), f); -- 2.7.4