Index: lld/COFF/ICF.cpp =================================================================== --- lld/COFF/ICF.cpp +++ lld/COFF/ICF.cpp @@ -41,8 +41,8 @@ private: void segregate(size_t Begin, size_t End, bool Constant); - bool equalsConstant(const SectionChunk *A, const SectionChunk *B); - bool equalsVariable(const SectionChunk *A, const SectionChunk *B); + bool lessConstant(const SectionChunk *A, const SectionChunk *B); + bool lessVariable(const SectionChunk *A, const SectionChunk *B); uint32_t getHash(SectionChunk *C); bool isEligible(SectionChunk *C); @@ -86,78 +86,117 @@ // Split an equivalence class into smaller classes. void ICF::segregate(size_t Begin, size_t End, bool Constant) { + auto Less = [&](SectionChunk *L, SectionChunk *R) { + if (Constant) + return lessConstant(L, R); + return lessVariable(L, R); + }; + + // Group equal chunks together and then split [Begin, End) range into smaller + // ranges with equal values + std::stable_sort(Chunks.begin() + Begin, Chunks.begin() + End, Less); + while (Begin < End) { - // Divide [Begin, End) into two. Let Mid be the start index of the - // second group. - auto Bound = std::stable_partition( - Chunks.begin() + Begin + 1, Chunks.begin() + End, [&](SectionChunk *S) { - if (Constant) - return equalsConstant(Chunks[Begin], S); - return equalsVariable(Chunks[Begin], S); - }); - size_t Mid = Bound - Chunks.begin(); - - // Split [Begin, End) into [Begin, Mid) and [Mid, End). We use Mid as an + // Find a sequence of elements that belong to the same equivalence class. + size_t I = Begin + 1; + while (I < End && !Less(Chunks[Begin], Chunks[I])) + ++I; + + // Split [Begin, End) into [Begin, I) and [I, End). We use I as an // equivalence class ID because every group ends with a unique index. - for (size_t I = Begin; I < Mid; ++I) - Chunks[I]->Class[(Cnt + 1) % 2] = Mid; + for (size_t J = Begin; J < I; ++J) + Chunks[J]->Class[(Cnt + 1) % 2] = I; // If we created a group, we need to iterate the main loop again. - if (Mid != End) + if (I != End) Repeat = true; - - Begin = Mid; + Begin = I; } } // Compare "non-moving" part of two sections, namely everything // except relocation targets. -bool ICF::equalsConstant(const SectionChunk *A, const SectionChunk *B) { +bool ICF::lessConstant(const SectionChunk *A, const SectionChunk *B) { if (A->NumRelocs != B->NumRelocs) - return false; + return A->NumRelocs < B->NumRelocs; + + if (A->getPermissions() != B->getPermissions()) + return A->getPermissions() < B->getPermissions(); + + if (A->SectionName != B->SectionName) + return A->SectionName < B->SectionName; + + if (A->getAlign() != B->getAlign()) + return A->getAlign() < B->getAlign(); + + if (A->Header->SizeOfRawData != B->Header->SizeOfRawData) + return A->Header->SizeOfRawData < B->Header->SizeOfRawData; + + if (A->Checksum != B->Checksum) + return A->Checksum < B->Checksum; + + if (int X = + toStringRef(A->getContents()).compare(toStringRef(B->getContents()))) + return X < 0; // Compare relocations. - auto Eq = [&](const coff_relocation &R1, const coff_relocation &R2) { - if (R1.Type != R2.Type || - R1.VirtualAddress != R2.VirtualAddress) { - return false; - } + for (size_t I = 0; I != A->NumRelocs; ++I) { + const coff_relocation &R1 = *(A->Relocs.begin() + I); + const coff_relocation &R2 = *(B->Relocs.begin() + I); + + if (R1.Type != R2.Type) + return R1.Type < R2.Type; + if (R1.VirtualAddress != R2.VirtualAddress) + return R1.VirtualAddress < R2.VirtualAddress; + SymbolBody *B1 = A->File->getSymbolBody(R1.SymbolTableIndex); SymbolBody *B2 = B->File->getSymbolBody(R2.SymbolTableIndex); if (B1 == B2) - return true; - if (auto *D1 = dyn_cast(B1)) - if (auto *D2 = dyn_cast(B2)) - return D1->getValue() == D2->getValue() && - D1->getChunk()->Class[Cnt % 2] == D2->getChunk()->Class[Cnt % 2]; - return false; - }; - if (!std::equal(A->Relocs.begin(), A->Relocs.end(), B->Relocs.begin(), Eq)) - return false; - - // Compare section attributes and contents. - return A->getPermissions() == B->getPermissions() && - A->SectionName == B->SectionName && - A->getAlign() == B->getAlign() && - A->Header->SizeOfRawData == B->Header->SizeOfRawData && - A->Checksum == B->Checksum && - A->getContents() == B->getContents(); + continue; + + auto *D1 = dyn_cast(B1); + auto *D2 = dyn_cast(B2); + + if (!D1 || !D2) + return B1 < B2; + + if (D1->getValue() != D2->getValue()) + return D1->getValue() < D2->getValue(); + + uint32_t C1 = D1->getChunk()->Class[Cnt % 2]; + uint32_t C2 = D2->getChunk()->Class[Cnt % 2]; + if (C1 != C2) + return C1 < C2; + } + + return false; } // Compare "moving" part of two sections, namely relocation targets. -bool ICF::equalsVariable(const SectionChunk *A, const SectionChunk *B) { +bool ICF::lessVariable(const SectionChunk *A, const SectionChunk *B) { // Compare relocations. - auto Eq = [&](const coff_relocation &R1, const coff_relocation &R2) { + for (size_t I = 0; I != A->NumRelocs; ++I) { + const coff_relocation &R1 = *(A->Relocs.begin() + I); + const coff_relocation &R2 = *(B->Relocs.begin() + I); + SymbolBody *B1 = A->File->getSymbolBody(R1.SymbolTableIndex); SymbolBody *B2 = B->File->getSymbolBody(R2.SymbolTableIndex); if (B1 == B2) - return true; - if (auto *D1 = dyn_cast(B1)) - if (auto *D2 = dyn_cast(B2)) - return D1->getChunk()->Class[Cnt % 2] == D2->getChunk()->Class[Cnt % 2]; - return false; - }; - return std::equal(A->Relocs.begin(), A->Relocs.end(), B->Relocs.begin(), Eq); + continue; + + auto *D1 = dyn_cast(B1); + auto *D2 = dyn_cast(B2); + + if (!D1 || !D2) + return B1 < B2; + + uint32_t C1 = D1->getChunk()->Class[Cnt % 2]; + uint32_t C2 = D2->getChunk()->Class[Cnt % 2]; + if (C1 != C2) + return C1 < C2; + } + + return false; } size_t ICF::findBoundary(size_t Begin, size_t End) { @@ -169,11 +208,8 @@ void ICF::forEachClassRange(size_t Begin, size_t End, std::function Fn) { - if (Begin > 0) - Begin = findBoundary(Begin - 1, End); - while (Begin < End) { - size_t Mid = findBoundary(Begin, Chunks.size()); + size_t Mid = findBoundary(Begin, End); Fn(Begin, Mid); Begin = Mid; } @@ -190,11 +226,21 @@ } // Split sections into 256 shards and call Fn in parallel. - size_t NumShards = 256; + constexpr size_t NumShards = 256; size_t Step = Chunks.size() / NumShards; + std::array Bounds; + for (size_t I = 0; I < NumShards; I++) { + size_t Bound = I * Step; + if (Bound > 0) + Bound = findBoundary(Bound - 1, Chunks.size()); + + Bounds[I] = Bound; + }; + + Bounds[NumShards] = Chunks.size(); + for_each_n(parallel::par, size_t(0), NumShards, [&](size_t I) { - size_t End = (I == NumShards - 1) ? Chunks.size() : (I + 1) * Step; - forEachClassRange(I * Step, End, Fn); + forEachClassRange(Bounds[I], Bounds[I + 1], Fn); }); ++Cnt; }