| 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. The hash |
| 36 | // covers section contents and relocations. A relocation to another ICF |
| 37 | // candidate contributes the target's hash, propagated for a few rounds, |
| 38 | // so the hash also covers sections a few relocation hops away. |
| 39 | // |
| 40 | // 2. Next, we split each equivalence class by comparing everything except |
| 41 | // relocation targets (equalsConstant). These properties never change, so |
| 42 | // this step runs once. |
| 43 | // |
| 44 | // 3. Then we split classes by comparing relocation targets (equalsVariable), |
| 45 | // which are considered equivalent if they are in the same equivalence |
| 46 | // class. A split may make two relocations that targeted the same class |
| 47 | // target different classes, so we repeat this step until no class splits. |
| 48 | // |
| 49 | // 4. For each equivalence class C, pick an arbitrary section in C, and |
| 50 | // merge all the other sections in C with it. |
| 51 | // |
| 52 | // Step 1 must give identical sections the same hash. A collision only costs |
| 53 | // step 2 time, and the more relocation hops step 1 covers, the fewer |
| 54 | // iterations step 3 needs. |
| 55 | // |
| 56 | // We parallelize each step so that multiple threads can work on different |
| 57 | // equivalence classes concurrently. |
| 58 | // |
| 59 | //===----------------------------------------------------------------------===// |
| 60 | |
| 61 | #include "ICF.h" |
| 62 | #include "Config.h" |
| 63 | #include "InputFiles.h" |
| 64 | #include "LinkerScript.h" |
| 65 | #include "OutputSections.h" |
| 66 | #include "SymbolTable.h" |
| 67 | #include "Symbols.h" |
| 68 | #include "SyntheticSections.h" |
| 69 | #include "llvm/BinaryFormat/ELF.h" |
| 70 | #include "llvm/Support/Parallel.h" |
| 71 | #include "llvm/Support/TimeProfiler.h" |
| 72 | #include "llvm/Support/xxhash.h" |
| 73 | #include <algorithm> |
| 74 | #include <atomic> |
| 75 | |
| 76 | using namespace llvm; |
| 77 | using namespace llvm::ELF; |
| 78 | using namespace llvm::object; |
| 79 | using namespace lld; |
| 80 | using namespace lld::elf; |
| 81 | |
| 82 | namespace { |
| 83 | template <class ELFT> class ICF { |
| 84 | public: |
| 85 | ICF(Ctx &ctx) : ctx(ctx) {} |
| 86 | void run(); |
| 87 | |
| 88 | private: |
| 89 | void segregate(size_t begin, size_t end, uint32_t eqClassBase, bool constant); |
| 90 | |
| 91 | template <class RelTy> |
| 92 | bool constantEq(const InputSection *a, Relocs<RelTy> relsA, |
| 93 | const InputSection *b, Relocs<RelTy> relsB); |
| 94 | |
| 95 | template <class RelTy> |
| 96 | void hashRelocs(const InputSection &sec, uint64_t &h, |
| 97 | SmallVectorImpl<uint32_t> &edges, uint32_t eqClassBase, |
| 98 | Relocs<RelTy> rels); |
| 99 | |
| 100 | template <class RelTy> |
| 101 | bool variableEq(const InputSection *a, Relocs<RelTy> relsA, |
| 102 | const InputSection *b, Relocs<RelTy> relsB); |
| 103 | |
| 104 | bool equalsConstant(const InputSection *a, const InputSection *b); |
| 105 | bool equalsVariable(const InputSection *a, const InputSection *b); |
| 106 | |
| 107 | size_t findBoundary(size_t begin, size_t end); |
| 108 | |
| 109 | void forEachClassRange(size_t begin, size_t end, |
| 110 | llvm::function_ref<void(size_t, size_t)> fn); |
| 111 | |
| 112 | void parallelForEachClass(llvm::function_ref<void(size_t, size_t)> fn); |
| 113 | |
| 114 | Ctx &ctx; |
| 115 | SmallVector<InputSection *, 0> sections; |
| 116 | |
| 117 | // We repeat the main loop while `Repeat` is true. |
| 118 | std::atomic<bool> repeat; |
| 119 | |
| 120 | // The main loop counter. |
| 121 | int cnt = 0; |
| 122 | |
| 123 | // We have two locations for equivalence classes. On the first iteration |
| 124 | // of the main loop, Class[0] has a valid value, and Class[1] contains |
| 125 | // garbage. We read equivalence classes from slot 0 and write to slot 1. |
| 126 | // So, Class[0] represents the current class, and Class[1] represents |
| 127 | // the next class. On each iteration, we switch their roles and use them |
| 128 | // alternately. |
| 129 | // |
| 130 | // Why are we doing this? Recall that other threads may be working on |
| 131 | // other equivalence classes in parallel. They may read sections that we |
| 132 | // are updating. We cannot update equivalence classes in place because |
| 133 | // it breaks the invariance that all possibly-identical sections must be |
| 134 | // in the same equivalence class at any moment. In other words, the for |
| 135 | // loop to update equivalence classes is not atomic, and that is |
| 136 | // observable from other threads. By writing new classes to other |
| 137 | // places, we can keep the invariance. |
| 138 | // |
| 139 | // Below, `Current` has the index of the current class, and `Next` has |
| 140 | // the index of the next class. If threading is enabled, they are either |
| 141 | // (0, 1) or (1, 0). |
| 142 | // |
| 143 | // Note on single-thread: if that's the case, they are always (0, 0) |
| 144 | // because we can safely read the next class without worrying about race |
| 145 | // conditions. Using the same location makes this algorithm converge |
| 146 | // faster because it uses results of the same iteration earlier. |
| 147 | int current = 0; |
| 148 | int next = 0; |
| 149 | }; |
| 150 | } // namespace |
| 151 | |
| 152 | // Returns true if section S is subject of ICF. |
| 153 | static bool isEligible(InputSection *s) { |
| 154 | if (!s->isLive() || s->keepUnique || !(s->flags & SHF_ALLOC)) |
| 155 | return false; |
| 156 | |
| 157 | // Don't merge writable sections. .data.rel.ro sections are marked as writable |
| 158 | // but are semantically read-only. |
| 159 | if ((s->flags & SHF_WRITE) && s->name != ".data.rel.ro" && |
| 160 | !s->name.starts_with(Prefix: ".data.rel.ro." )) |
| 161 | return false; |
| 162 | |
| 163 | // SHF_LINK_ORDER sections are ICF'd as a unit with their dependent sections, |
| 164 | // so we don't consider them for ICF individually. |
| 165 | if (s->flags & SHF_LINK_ORDER) |
| 166 | return false; |
| 167 | |
| 168 | // Don't merge synthetic sections as their Data member is not valid and empty. |
| 169 | // The Data member needs to be valid for ICF as it is used by ICF to determine |
| 170 | // the equality of section contents. |
| 171 | if (isa<SyntheticSection>(Val: s)) |
| 172 | return false; |
| 173 | |
| 174 | // .init and .fini contains instructions that must be executed to initialize |
| 175 | // and finalize the process. They cannot and should not be merged. |
| 176 | if (s->name == ".init" || s->name == ".fini" ) |
| 177 | return false; |
| 178 | |
| 179 | // A user program may enumerate sections named with a C identifier using |
| 180 | // __start_* and __stop_* symbols. We cannot ICF any such sections because |
| 181 | // that could change program semantics. |
| 182 | if (isValidCIdentifier(s: s->name)) |
| 183 | return false; |
| 184 | |
| 185 | return true; |
| 186 | } |
| 187 | |
| 188 | // Split an equivalence class into smaller classes. |
| 189 | template <class ELFT> |
| 190 | void ICF<ELFT>::segregate(size_t begin, size_t end, uint32_t eqClassBase, |
| 191 | bool constant) { |
| 192 | // This loop rearranges sections in [Begin, End) so that all sections |
| 193 | // that are equal in terms of equals{Constant,Variable} are contiguous |
| 194 | // in [Begin, End). |
| 195 | // |
| 196 | // The algorithm is quadratic in the worst case, but that is not an |
| 197 | // issue in practice because the number of the distinct sections in |
| 198 | // each range is usually very small. |
| 199 | |
| 200 | while (begin < end) { |
| 201 | // Divide [Begin, End) into two. Let Mid be the start index of the |
| 202 | // second group. |
| 203 | auto bound = |
| 204 | std::stable_partition(sections.begin() + begin + 1, |
| 205 | sections.begin() + end, [&](InputSection *s) { |
| 206 | if (constant) |
| 207 | return equalsConstant(a: sections[begin], b: s); |
| 208 | return equalsVariable(a: sections[begin], b: s); |
| 209 | }); |
| 210 | size_t mid = bound - sections.begin(); |
| 211 | |
| 212 | // Now we split [Begin, End) into [Begin, Mid) and [Mid, End) by |
| 213 | // updating the sections in [Begin, Mid). We use Mid as the basis for |
| 214 | // the equivalence class ID because every group ends with a unique index. |
| 215 | // Add this to eqClassBase to avoid equality with unique IDs. |
| 216 | for (size_t i = begin; i < mid; ++i) |
| 217 | sections[i]->eqClass[next] = eqClassBase + mid; |
| 218 | |
| 219 | // If we created a group, we need to iterate the main loop again. |
| 220 | if (mid != end) |
| 221 | repeat = true; |
| 222 | |
| 223 | begin = mid; |
| 224 | } |
| 225 | } |
| 226 | |
| 227 | // Propagation mixes a self-referencing section's hash with itself, so mix(h, h) |
| 228 | // must not be a constant. |
| 229 | static uint64_t mix(uint64_t h, uint64_t v) { |
| 230 | return (h + v) * 0x9e3779b97f4a7c15; |
| 231 | } |
| 232 | |
| 233 | // Different symbols compare equal only if both values are final: not a linker |
| 234 | // script placeholder (assigned later) and not preemptible. |
| 235 | static Defined *getComparableDef(Symbol &sym) { |
| 236 | auto *d = dyn_cast<Defined>(Val: &sym); |
| 237 | return d && !d->scriptDefined && !d->isPreemptible ? d : nullptr; |
| 238 | } |
| 239 | |
| 240 | // A section symbol's addend is not validated until getSymVA. Return nullopt |
| 241 | // to conservatively disable folding for such an out-of-range offset. |
| 242 | static std::optional<uint64_t> getMergeOffset(const Defined &d, |
| 243 | uint64_t addend) { |
| 244 | auto &ms = cast<MergeInputSection>(Val&: *d.section); |
| 245 | if (!d.isSection()) |
| 246 | return ms.getOffset(offset: d.value) + addend; |
| 247 | if (addend >= ms.content().size()) |
| 248 | return std::nullopt; |
| 249 | return ms.getOffset(offset: addend); |
| 250 | } |
| 251 | |
| 252 | // Compare two lists of relocations. |
| 253 | template <class ELFT> |
| 254 | template <class RelTy> |
| 255 | bool ICF<ELFT>::constantEq(const InputSection *secA, Relocs<RelTy> ra, |
| 256 | const InputSection *secB, Relocs<RelTy> rb) { |
| 257 | if (ra.size() != rb.size()) |
| 258 | return false; |
| 259 | auto rai = ra.begin(), rae = ra.end(), rbi = rb.begin(); |
| 260 | for (; rai != rae; ++rai, ++rbi) { |
| 261 | if (rai->r_offset != rbi->r_offset || |
| 262 | rai->getType(ctx.arg.isMips64EL) != rbi->getType(ctx.arg.isMips64EL)) |
| 263 | return false; |
| 264 | |
| 265 | uint64_t addA = getAddend<ELFT>(*rai); |
| 266 | uint64_t addB = getAddend<ELFT>(*rbi); |
| 267 | |
| 268 | Symbol &sa = secA->file->getRelocTargetSym(*rai); |
| 269 | Symbol &sb = secB->file->getRelocTargetSym(*rbi); |
| 270 | if (&sa == &sb && addA == addB) |
| 271 | continue; |
| 272 | |
| 273 | Defined *da = getComparableDef(sym&: sa), *db = getComparableDef(sym&: sb); |
| 274 | if (!da || !db) |
| 275 | return false; |
| 276 | |
| 277 | // Relocations referring to absolute symbols are constant-equal if their |
| 278 | // values are equal. |
| 279 | if (!da->section && !db->section && da->value + addA == db->value + addB) |
| 280 | continue; |
| 281 | if (!da->section || !db->section) |
| 282 | return false; |
| 283 | |
| 284 | if (da->section->kind() != db->section->kind()) |
| 285 | return false; |
| 286 | |
| 287 | // Relocations referring to InputSections are constant-equal if their |
| 288 | // section offsets are equal. |
| 289 | if (isa<InputSection>(Val: da->section)) { |
| 290 | if (da->value + addA == db->value + addB) |
| 291 | continue; |
| 292 | return false; |
| 293 | } |
| 294 | |
| 295 | // Relocations referring to MergeInputSections are constant-equal if their |
| 296 | // offsets in the output section are equal. |
| 297 | auto *x = dyn_cast<MergeInputSection>(Val: da->section); |
| 298 | if (!x) |
| 299 | return false; |
| 300 | auto *y = cast<MergeInputSection>(Val: db->section); |
| 301 | if (x->getParent() != y->getParent()) |
| 302 | return false; |
| 303 | |
| 304 | auto offA = getMergeOffset(d: *da, addend: addA); |
| 305 | if (!offA || offA != getMergeOffset(d: *db, addend: addB)) |
| 306 | return false; |
| 307 | } |
| 308 | |
| 309 | return true; |
| 310 | } |
| 311 | |
| 312 | // Hash what constantEq compares, plus the class of a non-candidate target, |
| 313 | // which never changes. Candidate targets are recorded as edges instead. |
| 314 | template <class ELFT> |
| 315 | template <class RelTy> |
| 316 | void ICF<ELFT>::hashRelocs(const InputSection &sec, uint64_t &h, |
| 317 | SmallVectorImpl<uint32_t> &edges, |
| 318 | uint32_t eqClassBase, Relocs<RelTy> rels) { |
| 319 | for (const RelTy &rel : rels) { |
| 320 | h = mix(h, rel.r_offset); |
| 321 | h = mix(h, rel.getType(ctx.arg.isMips64EL)); |
| 322 | uint64_t addend = getAddend<ELFT>(rel); |
| 323 | Symbol &sym = sec.file->getRelocTargetSym(rel); |
| 324 | Defined *d = getComparableDef(sym); |
| 325 | if (!d) { |
| 326 | h = mix(h, v: xxh3_64bits(data: sym.getName())); |
| 327 | h = mix(h, v: addend); |
| 328 | continue; |
| 329 | } |
| 330 | if (isa_and_nonnull<MergeInputSection>(Val: d->section)) { |
| 331 | h = mix(h, v: getMergeOffset(d: *d, addend).value_or(u: -1)); |
| 332 | continue; |
| 333 | } |
| 334 | h = mix(h, v: d->value + addend); |
| 335 | auto *is = dyn_cast_or_null<InputSection>(Val: d->section); |
| 336 | if (!is) |
| 337 | continue; |
| 338 | // A candidate's eqClass[0] - eqClassBase is its index in sections. |
| 339 | if (is->eqClass[0] >= eqClassBase) |
| 340 | edges.push_back(Elt: is->eqClass[0] - eqClassBase); |
| 341 | else |
| 342 | h = mix(h, v: is->eqClass[0]); |
| 343 | } |
| 344 | } |
| 345 | |
| 346 | // Compare "non-moving" part of two InputSections, namely everything |
| 347 | // except relocation targets. |
| 348 | template <class ELFT> |
| 349 | bool ICF<ELFT>::equalsConstant(const InputSection *a, const InputSection *b) { |
| 350 | if (a->flags != b->flags || a->content() != b->content()) |
| 351 | return false; |
| 352 | |
| 353 | // If two sections have different output sections, we cannot merge them. |
| 354 | assert(a->getParent() && b->getParent()); |
| 355 | if (a->getParent() != b->getParent()) |
| 356 | return false; |
| 357 | |
| 358 | const RelsOrRelas<ELFT> ra = a->template relsOrRelas<ELFT>(); |
| 359 | const RelsOrRelas<ELFT> rb = b->template relsOrRelas<ELFT>(); |
| 360 | if (ra.areRelocsCrel() || rb.areRelocsCrel()) |
| 361 | return constantEq(a, ra.crels, b, rb.crels); |
| 362 | return ra.areRelocsRel() || rb.areRelocsRel() |
| 363 | ? constantEq(a, ra.rels, b, rb.rels) |
| 364 | : constantEq(a, ra.relas, b, rb.relas); |
| 365 | } |
| 366 | |
| 367 | // Compare two lists of relocations. Returns true if all pairs of |
| 368 | // relocations point to the same section in terms of ICF. |
| 369 | template <class ELFT> |
| 370 | template <class RelTy> |
| 371 | bool ICF<ELFT>::variableEq(const InputSection *secA, Relocs<RelTy> ra, |
| 372 | const InputSection *secB, Relocs<RelTy> rb) { |
| 373 | assert(ra.size() == rb.size()); |
| 374 | |
| 375 | auto rai = ra.begin(), rae = ra.end(), rbi = rb.begin(); |
| 376 | for (; rai != rae; ++rai, ++rbi) { |
| 377 | // The two sections must be identical. |
| 378 | Symbol &sa = secA->file->getRelocTargetSym(*rai); |
| 379 | Symbol &sb = secB->file->getRelocTargetSym(*rbi); |
| 380 | if (&sa == &sb) |
| 381 | continue; |
| 382 | |
| 383 | auto *da = cast<Defined>(Val: &sa); |
| 384 | auto *db = cast<Defined>(Val: &sb); |
| 385 | |
| 386 | // We already dealt with absolute and non-InputSection symbols in |
| 387 | // constantEq, and for InputSections we have already checked everything |
| 388 | // except the equivalence class. |
| 389 | auto *x = dyn_cast_or_null<InputSection>(Val: da->section); |
| 390 | if (!x) |
| 391 | continue; |
| 392 | auto *y = cast<InputSection>(Val: db->section); |
| 393 | |
| 394 | // Sections that are in the special equivalence class 0, can never be the |
| 395 | // same in terms of the equivalence class. |
| 396 | if (x->eqClass[current] == 0) |
| 397 | return false; |
| 398 | if (x->eqClass[current] != y->eqClass[current]) |
| 399 | return false; |
| 400 | } |
| 401 | |
| 402 | return true; |
| 403 | } |
| 404 | |
| 405 | // Compare "moving" part of two InputSections, namely relocation targets. |
| 406 | template <class ELFT> |
| 407 | bool ICF<ELFT>::equalsVariable(const InputSection *a, const InputSection *b) { |
| 408 | const RelsOrRelas<ELFT> ra = a->template relsOrRelas<ELFT>(); |
| 409 | const RelsOrRelas<ELFT> rb = b->template relsOrRelas<ELFT>(); |
| 410 | if (ra.areRelocsCrel() || rb.areRelocsCrel()) |
| 411 | return variableEq(a, ra.crels, b, rb.crels); |
| 412 | return ra.areRelocsRel() || rb.areRelocsRel() |
| 413 | ? variableEq(a, ra.rels, b, rb.rels) |
| 414 | : variableEq(a, ra.relas, b, rb.relas); |
| 415 | } |
| 416 | |
| 417 | template <class ELFT> size_t ICF<ELFT>::findBoundary(size_t begin, size_t end) { |
| 418 | uint32_t eqClass = sections[begin]->eqClass[current]; |
| 419 | for (size_t i = begin + 1; i < end; ++i) |
| 420 | if (eqClass != sections[i]->eqClass[current]) |
| 421 | return i; |
| 422 | return end; |
| 423 | } |
| 424 | |
| 425 | // Sections in the same equivalence class are contiguous in Sections |
| 426 | // vector. Therefore, Sections vector can be considered as contiguous |
| 427 | // groups of sections, grouped by the class. |
| 428 | // |
| 429 | // This function calls Fn on every group within [Begin, End). |
| 430 | template <class ELFT> |
| 431 | void ICF<ELFT>::forEachClassRange(size_t begin, size_t end, |
| 432 | llvm::function_ref<void(size_t, size_t)> fn) { |
| 433 | while (begin < end) { |
| 434 | size_t mid = findBoundary(begin, end); |
| 435 | fn(begin, mid); |
| 436 | begin = mid; |
| 437 | } |
| 438 | } |
| 439 | |
| 440 | // Call Fn on each equivalence class. |
| 441 | |
| 442 | template <class ELFT> |
| 443 | void ICF<ELFT>::parallelForEachClass( |
| 444 | llvm::function_ref<void(size_t, size_t)> fn) { |
| 445 | // If threading is disabled or the number of sections are |
| 446 | // too small to use threading, call Fn sequentially. |
| 447 | if (parallel::strategy.ThreadsRequested == 1 || sections.size() < 1024) { |
| 448 | forEachClassRange(begin: 0, end: sections.size(), fn); |
| 449 | ++cnt; |
| 450 | return; |
| 451 | } |
| 452 | |
| 453 | current = cnt % 2; |
| 454 | next = (cnt + 1) % 2; |
| 455 | |
| 456 | // Shard into non-overlapping intervals, and call Fn in parallel. |
| 457 | // The sharding must be completed before any calls to Fn are made |
| 458 | // so that Fn can modify the Chunks in its shard without causing data |
| 459 | // races. |
| 460 | const size_t numShards = 256; |
| 461 | size_t step = sections.size() / numShards; |
| 462 | size_t boundaries[numShards + 1]; |
| 463 | boundaries[0] = 0; |
| 464 | boundaries[numShards] = sections.size(); |
| 465 | |
| 466 | parallelFor(1, numShards, [&](size_t i) { |
| 467 | boundaries[i] = findBoundary(begin: (i - 1) * step, end: sections.size()); |
| 468 | }); |
| 469 | |
| 470 | parallelFor(1, numShards + 1, [&](size_t i) { |
| 471 | if (boundaries[i - 1] < boundaries[i]) |
| 472 | forEachClassRange(begin: boundaries[i - 1], end: boundaries[i], fn); |
| 473 | }); |
| 474 | ++cnt; |
| 475 | } |
| 476 | |
| 477 | // The main function of ICF. |
| 478 | template <class ELFT> void ICF<ELFT>::run() { |
| 479 | // Two text sections may have identical content and relocations but different |
| 480 | // LSDA, e.g. the two functions may have catch blocks of different types. If a |
| 481 | // text section is referenced by a .eh_frame FDE with LSDA, it is not |
| 482 | // eligible. This is implemented by iterating over CIE/FDE and setting |
| 483 | // eqClass[0] to the referenced text section from a live FDE. |
| 484 | // |
| 485 | // If two .gcc_except_table have identical semantics (usually identical |
| 486 | // content with PC-relative encoding), we will lose folding opportunity. |
| 487 | uint32_t uniqueId = 1; |
| 488 | ctx.in.ehFrame->iterateFDEWithLSDA( |
| 489 | fn: [&](InputSection &s) { s.eqClass[0] = s.eqClass[1] = uniqueId++; }); |
| 490 | |
| 491 | // Assign a temporary class ID (eqClassBase) to eligible sections and assign |
| 492 | // unique IDs to ineligible sections. Use eqClassBase as the base for class |
| 493 | // IDs. Each ineligible section belongs to an equivalence class of its own. |
| 494 | constexpr size_t chunkSize = 1024; |
| 495 | ArrayRef<InputSectionBase *> inputs = ctx.inputSections; |
| 496 | size_t numInputChunks = divideCeil(Numerator: inputs.size(), Denominator: chunkSize); |
| 497 | auto chunkRange = [&](size_t c, size_t total) { |
| 498 | auto begin = c * chunkSize; |
| 499 | return std::make_pair(x&: begin, y: std::min(a: begin + chunkSize, b: total)); |
| 500 | }; |
| 501 | uint32_t eqClassBase = uniqueId + inputs.size(); |
| 502 | SmallVector<uint32_t, 0> firstIdx(numInputChunks); |
| 503 | parallelFor(0, numInputChunks, [&](size_t c) { |
| 504 | auto [begin, end] = chunkRange(c, inputs.size()); |
| 505 | uint32_t n = 0; |
| 506 | for (size_t i = begin; i != end; ++i) { |
| 507 | auto *s = dyn_cast<InputSection>(Val: inputs[i]); |
| 508 | if (s && s->eqClass[0] == 0) { |
| 509 | if (isEligible(s)) { |
| 510 | s->eqClass[0] = eqClassBase; |
| 511 | ++n; |
| 512 | } else { |
| 513 | s->eqClass[0] = s->eqClass[1] = uniqueId + i; |
| 514 | } |
| 515 | } |
| 516 | } |
| 517 | // Temporarily store the number of sections per chunk. |
| 518 | firstIdx[c] = n; |
| 519 | }); |
| 520 | |
| 521 | // Compute the total number of eligible sections and each chunk's left index. |
| 522 | size_t numSections = 0; |
| 523 | for (size_t c = 0; c != numInputChunks; ++c) { |
| 524 | auto n = std::exchange(obj&: firstIdx[c], new_val&: numSections); |
| 525 | numSections += n; |
| 526 | } |
| 527 | sections.resize_for_overwrite(N: numSections); |
| 528 | // Update temporary class ID above the unique IDs so that hashRelocs() can |
| 529 | // tell them apart. |
| 530 | assert(uint64_t(eqClassBase) + numSections <= UINT32_MAX); |
| 531 | parallelFor(0, numInputChunks, [&](size_t c) { |
| 532 | auto [begin, end] = chunkRange(c, inputs.size()); |
| 533 | auto idx = firstIdx[c]; |
| 534 | for (size_t i = begin; i != end; ++i) { |
| 535 | auto *s = dyn_cast<InputSection>(Val: inputs[i]); |
| 536 | if (s && s->eqClass[0] == eqClassBase) { |
| 537 | s->eqClass[0] += idx; |
| 538 | sections[idx++] = s; |
| 539 | } |
| 540 | } |
| 541 | }); |
| 542 | |
| 543 | // Hash sections in chunks. An edge is a relocation to a candidate, recorded |
| 544 | // as the target's index. Each chunk appends its sections' edges to its own |
| 545 | // buffer; edgeEnd[i] is where section i's edges end within that buffer. |
| 546 | size_t numChunks = divideCeil(Numerator: numSections, Denominator: chunkSize); |
| 547 | SmallVector<uint64_t, 0> hashes(numSections, llvm::for_overwrite); |
| 548 | SmallVector<uint32_t, 0> edgeEnd(numSections, llvm::for_overwrite); |
| 549 | SmallVector<SmallVector<uint32_t, 0>, 0> chunkEdges(numChunks); |
| 550 | parallelFor(0, numChunks, [&](size_t c) { |
| 551 | SmallVectorImpl<uint32_t> &edges = chunkEdges[c]; |
| 552 | auto [begin, end] = chunkRange(c, numSections); |
| 553 | for (size_t i = begin; i != end; ++i) { |
| 554 | InputSection *s = sections[i]; |
| 555 | uint64_t h = xxh3_64bits(data: s->content()); |
| 556 | invokeOnRelocs(*s, hashRelocs, *s, h, edges, eqClassBase); |
| 557 | hashes[i] = h; |
| 558 | edgeEnd[i] = edges.size(); |
| 559 | } |
| 560 | }); |
| 561 | |
| 562 | // Propagate hashes over edges for 7 rounds. Each round saves up to one |
| 563 | // segregate() pass. 7 is empirical: even Chromium then needs just two passes. |
| 564 | SmallVector<uint64_t, 0> nextHashes(numSections, llvm::for_overwrite); |
| 565 | for (int round = 7; round--;) { |
| 566 | parallelFor(0, numChunks, [&](size_t c) { |
| 567 | ArrayRef<uint32_t> edges = chunkEdges[c]; |
| 568 | auto [begin, end] = chunkRange(c, numSections); |
| 569 | size_t j = 0; |
| 570 | for (size_t i = begin; i != end; ++i) { |
| 571 | uint64_t h = hashes[i]; |
| 572 | for (size_t e = edgeEnd[i]; j != e; ++j) |
| 573 | h = mix(h, v: hashes[edges[j]]); |
| 574 | nextHashes[i] = h; |
| 575 | } |
| 576 | }); |
| 577 | std::swap(LHS&: hashes, RHS&: nextHashes); |
| 578 | } |
| 579 | |
| 580 | // Order sections so that those in the same equivalence class are consecutive. |
| 581 | SmallVector<uint64_t, 0> keys(numSections, llvm::for_overwrite); |
| 582 | parallelFor(0, numSections, [&](size_t i) { |
| 583 | // mix()'s low bits depend only on the inputs' low bits. Fold the high half. |
| 584 | uint32_t h = hashes[i] ^ hashes[i] >> 32; |
| 585 | sections[i]->eqClass[0] = h; |
| 586 | keys[i] = uint64_t(h) << 32 | i; |
| 587 | }); |
| 588 | parallelSort(Start: keys.begin(), End: keys.end()); |
| 589 | SmallVector<InputSection *, 0> sorted(numSections, llvm::for_overwrite); |
| 590 | parallelFor(0, numSections, |
| 591 | [&](size_t i) { sorted[i] = sections[uint32_t(keys[i])]; }); |
| 592 | sections = std::move(sorted); |
| 593 | |
| 594 | // Compare static contents and assign unique equivalence class IDs for each |
| 595 | // static content. Use a base offset for these IDs to ensure no overlap with |
| 596 | // the unique IDs already assigned. |
| 597 | parallelForEachClass(fn: [&](size_t begin, size_t end) { |
| 598 | segregate(begin, end, eqClassBase, constant: true); |
| 599 | }); |
| 600 | |
| 601 | // Split groups by comparing relocations until convergence is obtained. |
| 602 | do { |
| 603 | repeat = false; |
| 604 | parallelForEachClass(fn: [&](size_t begin, size_t end) { |
| 605 | segregate(begin, end, eqClassBase, constant: false); |
| 606 | }); |
| 607 | } while (repeat); |
| 608 | |
| 609 | Log(ctx) << "ICF needed " << cnt << " iterations" ; |
| 610 | |
| 611 | // Merge sections by the equivalence class. |
| 612 | parallelForEachClass(fn: [&](size_t begin, size_t end) { |
| 613 | for (size_t i = begin + 1; i < end; ++i) { |
| 614 | sections[begin]->replace(other: sections[i]); |
| 615 | |
| 616 | // At this point we know sections merged are fully identical and hence |
| 617 | // we want to remove duplicate implicit dependencies such as link order |
| 618 | // and relocation sections. |
| 619 | for (InputSection *isec : sections[i]->dependentSections) |
| 620 | isec->markDead(); |
| 621 | } |
| 622 | }); |
| 623 | |
| 624 | // Print classes in input order, independent of the hash. |
| 625 | if (ctx.arg.printIcfSections) { |
| 626 | DenseMap<InputSection *, SmallVector<InputSection *, 0>> folded; |
| 627 | for (InputSectionBase *sec : ctx.inputSections) |
| 628 | if (auto *s = dyn_cast<InputSection>(Val: sec); s && s->repl != s) |
| 629 | folded[s->repl].push_back(Elt: s); |
| 630 | for (InputSectionBase *sec : ctx.inputSections) { |
| 631 | auto it = folded.find(Val: dyn_cast<InputSection>(Val: sec)); |
| 632 | if (it == folded.end()) |
| 633 | continue; |
| 634 | Msg(ctx) << "selected section " << sec; |
| 635 | for (InputSection *s : it->second) |
| 636 | Msg(ctx) << " removing identical section " << s; |
| 637 | } |
| 638 | } |
| 639 | |
| 640 | // Change Defined symbol's section field to the canonical one. |
| 641 | auto fold = [](Symbol *sym) { |
| 642 | if (auto *d = dyn_cast<Defined>(Val: sym)) |
| 643 | if (auto *sec = dyn_cast_or_null<InputSection>(Val: d->section)) |
| 644 | if (sec->repl != d->section) { |
| 645 | d->section = sec->repl; |
| 646 | d->folded = true; |
| 647 | } |
| 648 | }; |
| 649 | parallelForEach(ctx.symtab->getSymbols(), fold); |
| 650 | parallelForEach(ctx.objectFiles, [&](ELFFileBase *file) { |
| 651 | for (Symbol *sym : file->getLocalSymbols()) |
| 652 | fold(sym); |
| 653 | }); |
| 654 | |
| 655 | // InputSectionDescription::sections is populated by processSectionCommands(). |
| 656 | // ICF may fold some input sections assigned to output sections. Remove them. |
| 657 | for (SectionCommand *cmd : ctx.script->sectionCommands) |
| 658 | if (auto *osd = dyn_cast<OutputDesc>(Val: cmd)) |
| 659 | for (SectionCommand *subCmd : osd->osec.commands) |
| 660 | if (auto *isd = dyn_cast<InputSectionDescription>(Val: subCmd)) |
| 661 | llvm::erase_if(isd->sections, |
| 662 | [](InputSection *isec) { return !isec->isLive(); }); |
| 663 | } |
| 664 | |
| 665 | // ICF entry point function. |
| 666 | template <class ELFT> void elf::doIcf(Ctx &ctx) { |
| 667 | llvm::TimeTraceScope timeScope("ICF" ); |
| 668 | ICF<ELFT>(ctx).run(); |
| 669 | } |
| 670 | |
| 671 | template void elf::doIcf<ELF32LE>(Ctx &); |
| 672 | template void elf::doIcf<ELF32BE>(Ctx &); |
| 673 | template void elf::doIcf<ELF64LE>(Ctx &); |
| 674 | template void elf::doIcf<ELF64BE>(Ctx &); |
| 675 | |