Lines Matching +full:coexist +full:- +full:support
1 //===- ICF.cpp ------------------------------------------------------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
18 #include "llvm/Support/LEB128.h"
19 #include "llvm/Support/Parallel.h"
20 #include "llvm/Support/TimeProfiler.h"
21 #include "llvm/Support/xxhash.h"
49 // ICF needs a copy of the inputs vector because its equivalence-class
84 // The __DATA segment is read/write at the MMU, and as application-writeable
90 // FIXME(gkm): implement keep-unique attributes
91 // FIXME(gkm): implement address-significance tables for MachO object files
93 // Compare "non-moving" parts of two ConcatInputSections, namely everything
100 if (ia->parent != ib->parent) in equalsConstant()
102 if (ia->data.size() != ib->data.size()) in equalsConstant()
104 if (ia->data != ib->data) in equalsConstant()
106 if (ia->relocs.size() != ib->relocs.size()) in equalsConstant()
127 if (sa->kind() != sb->kind()) in equalsConstant()
136 if (!da->isec() || !db->isec()) { in equalsConstant()
137 assert(da->isAbsolute() && db->isAbsolute()); in equalsConstant()
138 return da->value + ra.addend == db->value + rb.addend; in equalsConstant()
140 isecA = da->isec(); in equalsConstant()
141 valueA = da->value; in equalsConstant()
142 isecB = db->isec(); in equalsConstant()
143 valueB = db->value; in equalsConstant()
149 if (isecA->parent != isecB->parent) in equalsConstant()
152 assert(isecA->kind() == isecB->kind()); in equalsConstant()
162 return isecA->getOffset(valueA) == isecB->getOffset(valueB) && in equalsConstant()
167 return isecA->getOffset(ra.addend) == isecB->getOffset(rb.addend); in equalsConstant()
170 return std::equal(ia->relocs.begin(), ia->relocs.end(), ib->relocs.begin(), in equalsConstant()
174 // Compare the "moving" parts of two ConcatInputSections -- i.e. everything not
180 assert(ia->relocs.size() == ib->relocs.size()); in equalsVariable()
188 // identical-referent check above. Non-matching DylibSymbols were filtered in equalsVariable()
192 if (da->isAbsolute()) in equalsVariable()
194 isecA = dyn_cast<ConcatInputSection>(da->isec()); in equalsVariable()
197 isecB = cast<ConcatInputSection>(db->isec()); in equalsVariable()
206 return isecA->icfEqClass[icfPass % 2] == isecB->icfEqClass[icfPass % 2]; in equalsVariable()
208 if (!std::equal(ia->relocs.begin(), ia->relocs.end(), ib->relocs.begin(), f)) in equalsVariable()
215 auto hasUnwind = [](Defined *d) { return d->unwindEntry() != nullptr; }; in equalsVariable()
216 const auto *itA = llvm::find_if(ia->symbols, hasUnwind); in equalsVariable()
217 const auto *itB = llvm::find_if(ib->symbols, hasUnwind); in equalsVariable()
218 if (itA == ia->symbols.end()) in equalsVariable()
219 return itB == ib->symbols.end(); in equalsVariable()
220 if (itB == ib->symbols.end()) in equalsVariable()
224 if (da->unwindEntry()->icfEqClass[icfPass % 2] != in equalsVariable()
225 db->unwindEntry()->icfEqClass[icfPass % 2] || in equalsVariable()
226 da->value != 0 || db->value != 0) in equalsVariable()
228 auto isZero = [](Defined *d) { return d->value == 0; }; in equalsVariable()
229 return std::find_if_not(std::next(itA), ia->symbols.end(), isZero) == in equalsVariable()
230 ia->symbols.end() && in equalsVariable()
231 std::find_if_not(std::next(itB), ib->symbols.end(), isZero) == in equalsVariable()
232 ib->symbols.end(); in equalsVariable()
237 uint64_t beginHash = icfInputs[begin]->icfEqClass[icfPass % 2]; in findBoundary()
239 if (beginHash != icfInputs[i]->icfEqClass[icfPass % 2]) in findBoundary()
265 // Shard into non-overlapping intervals, and call FUNC in parallel. The in forEachClass()
274 boundaries[i] = findBoundary((i - 1) * step, icfInputs.size()); in forEachClass()
277 if (boundaries[i - 1] < boundaries[i]) { in forEachClass()
278 forEachClassRange(boundaries[i - 1], boundaries[i], func); in forEachClass()
285 // Into each origin-section hash, combine all reloc referent section hashes. in run()
288 uint32_t hash = isec->icfEqClass[icfPass % 2]; in run()
289 for (const Reloc &r : isec->relocs) { in run()
292 if (defined->isec()) { in run()
294 dyn_cast<ConcatInputSection>(defined->isec())) in run()
295 hash += defined->value + referentIsec->icfEqClass[icfPass % 2]; in run()
297 hash += defined->isec()->kind() + in run()
298 defined->isec()->getOffset(defined->value); in run()
300 hash += defined->value; in run()
308 // Set MSB to 1 to avoid collisions with non-hashed classes. in run()
309 isec->icfEqClass[(icfPass + 1) % 2] = hash | (1ull << 31); in run()
315 return a->icfEqClass[0] < b->icfEqClass[0]; in run()
336 if (end - begin < 2) in run()
340 beginIsec->foldIdentical(icfInputs[i]); in run()
352 return (this->*equals)(icfInputs[begin], isec); in segregate()
354 size_t mid = bound - icfInputs.begin(); in segregate()
359 icfInputs[i]->icfEqClass[(icfPass + 1) % 2] = mid; in segregate()
371 if (d->isec()) in markSymAsAddrSig()
372 d->isec()->keepUnique = true; in markSymAsAddrSig()
382 Section *addrSigSection = obj->addrSigSection; in markAddrSigSymbols()
385 assert(addrSigSection->subsections.size() == 1); in markAddrSigSymbols()
387 const InputSection *isec = addrSigSection->subsections[0].isec; in markAddrSigSymbols()
389 for (const Reloc &r : isec->relocs) { in markAddrSigSymbols()
400 // The ICF equivalence-class segregation algorithm relies on pre-computed in foldIdenticalSections()
408 // it into an unfoldable singleton equivalence class. Begin the unique-ID in foldIdenticalSections()
410 // equivalence-class IDs which begin at 0. Since hashes & unique IDs never in foldIdenticalSections()
411 // coexist with equivalence-class IDs, this is not necessary, but might help in foldIdenticalSections()
423 sectionType(isec->getFlags()) == MachO::S_REGULAR); in foldIdenticalSections()
424 // FIXME: consider non-code __text sections as foldable? in foldIdenticalSections()
428 !isec->keepUnique && !isec->hasAltEntry && in foldIdenticalSections()
429 !isec->shouldOmitFromOutput() && hasFoldableFlags; in foldIdenticalSections()
432 for (Defined *d : isec->symbols) in foldIdenticalSections()
433 if (d->unwindEntry()) in foldIdenticalSections()
434 foldable.push_back(d->unwindEntry()); in foldIdenticalSections()
443 // thread-safe. FIXME: Make a thread-safe allocator. in foldIdenticalSections()
444 MutableArrayRef<uint8_t> copy = isec->data.copy(bAlloc()); in foldIdenticalSections()
445 for (const Reloc &r : isec->relocs) in foldIdenticalSections()
446 target->relocateOne(copy.data() + r.offset, r, /*va=*/0, in foldIdenticalSections()
448 isec->data = copy; in foldIdenticalSections()
453 isec->icfEqClass[0] = ++icfUniqueID; in foldIdenticalSections()
457 assert(isec->icfEqClass[0] == 0); // don't overwrite a unique ID! in foldIdenticalSections()
458 // Turn-on the top bit to guarantee that valid hashes have no collisions in foldIdenticalSections()
459 // with the small-integer unique IDs for ICF-ineligible sections in foldIdenticalSections()
460 isec->icfEqClass[0] = xxh3_64bits(isec->data) | (1ull << 31); in foldIdenticalSections()