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); @@ -55,6 +55,8 @@ void forEachClass(std::function Fn); std::vector Chunks; + llvm::DenseMap NonRegularSymbolIndex; + int Cnt = 0; std::atomic Repeat = {false}; }; @@ -86,78 +88,126 @@ // Split an equivalence class into smaller classes. void ICF::segregate(size_t Begin, size_t End, bool Constant) { - 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 - // 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; - - // If we created a group, we need to iterate the main loop again. - if (Mid != End) - Repeat = true; + if (Begin == End) + return; - Begin = Mid; + 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); + + size_t GroupBegin = Begin; + for (size_t Pos = Begin + 1; Pos < End; Pos++) { + if (!Less(Chunks[GroupBegin], Chunks[Pos])) + continue; + + // We use Pos as an equivalence class ID because every group ends with a + // unique index. + for (size_t I = GroupBegin; I < Pos; ++I) + Chunks[I]->Class[(Cnt + 1) % 2] = Pos; + + GroupBegin = Pos; } + + for (size_t I = GroupBegin; I < End; ++I) + Chunks[I]->Class[(Cnt + 1) % 2] = End; + + // If we created a group, we need to iterate the main loop again. + if (GroupBegin != Begin) + Repeat = true; } // 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 NonRegularSymbolIndex.lookup(B1) < + NonRegularSymbolIndex.lookup(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 0; } // 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) { + if (A->NumRelocs != B->NumRelocs) + return A->NumRelocs < B->NumRelocs; + + 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 NonRegularSymbolIndex.lookup(B1) < + NonRegularSymbolIndex.lookup(B2); + + if (D1->getChunk()->Class[Cnt % 2] != D2->getChunk()->Class[Cnt % 2]) + return D1->getChunk()->Class[Cnt % 2] < D2->getChunk()->Class[Cnt % 2]; + } + + return 0; } size_t ICF::findBoundary(size_t Begin, size_t End) { @@ -219,6 +269,23 @@ // Set MSB to 1 to avoid collisions with non-hash classs. SC->Class[0] = getHash(SC) | (1 << 31); + // Create a map from non-RegularSymbol symbols to indexes + // in order to segregate function to work deterministically + int Index = 0; + for (SectionChunk *SC : Chunks) { + for (size_t I = 0; I != SC->NumRelocs; ++I) { + const coff_relocation &R = *(SC->Relocs.begin() + I); + + SymbolBody *B = SC->File->getSymbolBody(R.SymbolTableIndex); + if (dyn_cast(B) != nullptr) + continue; + + auto ItAndSuccess = NonRegularSymbolIndex.insert(std::make_pair(B, 0)); + if (ItAndSuccess.second) + ItAndSuccess.first->second = Index++; + } + } + // From now on, sections in Chunks are ordered so that sections in // the same group are consecutive in the vector. std::stable_sort(Chunks.begin(), Chunks.end(),