Index: lld/COFF/ICF.cpp =================================================================== --- lld/COFF/ICF.cpp +++ lld/COFF/ICF.cpp @@ -41,8 +41,10 @@ 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); + int compareConstant(const SectionChunk *A, const SectionChunk *B, + bool NonRegularChunksAreEqual); + int compareVariable(const SectionChunk *A, const SectionChunk *B, + bool NonRegularChunksAreEqual); uint32_t getHash(SectionChunk *C); bool isEligible(SectionChunk *C); @@ -86,78 +88,168 @@ // 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; + // Group equal chunks together and then split [Begin, End) range into smaller + // ranges with equal values + // we need to treat all non-DefinedRegular chunks as equal for sorting + // to achieve determinism + std::stable_sort(Chunks.begin() + Begin, Chunks.begin() + End, + [&](SectionChunk *L, SectionChunk *R) { + if (Constant) + return compareConstant(L, R, true) < 0; + return compareVariable(L, R, true) < 0; + }); + + // we need to tread all non-DefinedRegular chunks as different here + auto Equal = [&](SectionChunk *L, SectionChunk *R) { + if (Constant) + return compareConstant(L, R, false) == 0; + return compareVariable(L, R, false) == 0; + }; + + size_t GroupBegin = Begin; + for (size_t Pos = Begin + 1; Pos < End; Pos++) { + if (Equal(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) { +// the result is -1, 0, or 1 if \p A less than, equal to, or greater than \p B +// if \p NonRegularChunksAreEqual is true treat all non-DefinedRegular +// relocation chunks as equal +int ICF::compareConstant(const SectionChunk *A, const SectionChunk *B, + bool NonRegularChunksAreEqual) { if (A->NumRelocs != B->NumRelocs) - return false; + return A->NumRelocs < B->NumRelocs ? -1 : 1; + + if (A->getPermissions() != B->getPermissions()) + return A->getPermissions() < B->getPermissions() ? -1 : 1; + + if (A->SectionName != B->SectionName) + return A->SectionName < B->SectionName ? -1 : 1; + + if (A->getAlign() != B->getAlign()) + return A->getAlign() < B->getAlign() ? -1 : 1; + + if (A->Header->SizeOfRawData != B->Header->SizeOfRawData) + return A->Header->SizeOfRawData < B->Header->SizeOfRawData ? -1 : 1; + + if (A->Checksum != B->Checksum) + return A->Checksum < B->Checksum ? -1 : 1; + + if (int X = + toStringRef(A->getContents()).compare(toStringRef(B->getContents()))) + return X; // 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 ? -1 : 1; + if (R1.VirtualAddress != R2.VirtualAddress) + return R1.VirtualAddress < R2.VirtualAddress ? -1 : 1; + 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); + + // We cannot compare non-DefinedRegular classes by anything meaningful other + // than a pointer + // But using pointers will lead to non-deterministic builds + // So we just make all non-DefinedRegular classes equal to each other and + // less than all DefinedRegular + // for the purposes of sorting and separate them later + if (!D1 && !D2) { + if (NonRegularChunksAreEqual) + continue; + + return B1 < B2 ? -1 : 1; + } + + if (!D1 || !D2) + return D1 < D2 ? -1 : 1; + + if (D1->getValue() != D2->getValue()) + return D1->getValue() < D2->getValue() ? -1 : 1; + + uint32_t C1 = D1->getChunk()->Class[Cnt % 2]; + uint32_t C2 = D2->getChunk()->Class[Cnt % 2]; + if (C1 != C2) + return C1 < C2 ? -1 : 1; + } + + return 0; } // Compare "moving" part of two sections, namely relocation targets. -bool ICF::equalsVariable(const SectionChunk *A, const SectionChunk *B) { +// the result is -1, 0, or 1 if \p A less than, equal to, or greater than \p B +// if \p NonRegularChunksAreEqual is true treat all non-DefinedRegular +// relocation chunks as equal +int ICF::compareVariable(const SectionChunk *A, const SectionChunk *B, + bool NonRegularChunksAreEqual) { // Compare relocations. - auto Eq = [&](const coff_relocation &R1, const coff_relocation &R2) { + if (A->NumRelocs != B->NumRelocs) + return A->NumRelocs < B->NumRelocs ? -1 : 1; + + 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); + + // We cannot compare non-DefinedRegular classes by anything meaningful other + // than a pointer + // But using pointers will lead to non-deterministic builds + // So we just make all non-DefinedRegular classes equal to each other and + // less than all DefinedRegular + // for the purposes of sorting and separate them later + if (!D1 && !D2) { + if (NonRegularChunksAreEqual) + continue; + + return B1 < B2 ? -1 : 1; + } + + if (!D1 || !D2) + return D1 < D2 ? -1 : 1; + + if (D1->getChunk()->Class[Cnt % 2] != D2->getChunk()->Class[Cnt % 2]) + return D1->getChunk()->Class[Cnt % 2] < D2->getChunk()->Class[Cnt % 2] + ? -1 + : 1; + } + + return 0; } size_t ICF::findBoundary(size_t Begin, size_t End) {