Index: ELF/InputSection.h =================================================================== --- ELF/InputSection.h +++ ELF/InputSection.h @@ -252,6 +252,7 @@ private: void splitStrings(ArrayRef A, size_t Size); + void splitStrings1(ArrayRef A); void splitNonStrings(ArrayRef A, size_t Size); }; Index: ELF/InputSection.cpp =================================================================== --- ELF/InputSection.cpp +++ ELF/InputSection.cpp @@ -856,10 +856,6 @@ } static size_t findNull(StringRef S, size_t EntSize) { - // Optimize the common case. - if (EntSize == 1) - return S.find(0); - for (unsigned I = 0, N = S.size(); I != N; I += EntSize) { const char *B = S.begin() + I; if (std::all_of(B, B + EntSize, [](char C) { return C == 0; })) @@ -872,6 +868,59 @@ return cast_or_null(Parent); } +// This helper function takes a null-terminated string and finds +// string size and Hash value. +static inline size_t findSizeAndHash(StringRef S, uint32_t &Hash) { + const char *Data = S.data(); + const char *const End = Data + S.size(); + + // We are going to calculate simple hash based on DJB hash below. Hash is + // calculated as the same time as we read the string bytes for speedup. + uint32_t H = 5381; + + // Load a word at a time and test if any of bytes is 0-byte. + while (End - Data > 4) { + uint32_t Word = read32(Data); + // This checks if at least one byte of a word is a null byte. + // If we found such case we want to break the loop and continue + // testing the single bytes to find the exact null byte position. + if ((Word - 0x01010101) & ~Word & 0x80808080) + break; + Data += 4; + H = H * 33 + Word; + } + + // Now find the exact position of the null byte. Do not forget to + // update the hash value too. + while (End - Data) { + H = H * 33 + *Data; + if (!*Data) { + Hash = H; + return Data - S.data() + 1; + } + ++Data; + } + + llvm_unreachable("string is not null terminated"); +} + +void MergeInputSection::splitStrings1(ArrayRef Data) { + if (Data.size() < 1 || Data.back() != 0) + fatal(toString(this) + ": string is too short or not null terminated"); + + size_t Off = 0; + bool IsAlloc = Flags & SHF_ALLOC; + StringRef S = toStringRef(Data); + + while (!S.empty()) { + uint32_t Hash; + size_t Size = findSizeAndHash(S, Hash); + Pieces.emplace_back(Off, Hash, !IsAlloc); + S = S.substr(Size); + Off += Size; + } +} + // Split SHF_STRINGS section. Such section is a sequence of // null-terminated strings. void MergeInputSection::splitStrings(ArrayRef Data, size_t EntSize) { @@ -925,10 +974,14 @@ void MergeInputSection::splitIntoPieces() { assert(Pieces.empty()); - if (Flags & SHF_STRINGS) - splitStrings(Data, Entsize); - else + if (Flags & SHF_STRINGS) { + if (Entsize == 1) + splitStrings1(Data); + else + splitStrings(Data, Entsize); + } else { splitNonStrings(Data, Entsize); + } OffsetMap.reserve(Pieces.size()); for (size_t I = 0, E = Pieces.size(); I != E; ++I) Index: test/ELF/comment-gc.s =================================================================== --- test/ELF/comment-gc.s +++ test/ELF/comment-gc.s @@ -5,7 +5,7 @@ # RUN: llvm-objdump -s %t1 | FileCheck %s # CHECK: Contents of section .comment: -# CHECK-NEXT: foo..LLD 1.0.bar +# CHECK-NEXT: .LLD 1.0.foo.bar .ident "foo" Index: test/ELF/compressed-debug-input.s =================================================================== --- test/ELF/compressed-debug-input.s +++ test/ELF/compressed-debug-input.s @@ -61,11 +61,11 @@ # DATA-NEXT: AddressAlignment: 1 # DATA-NEXT: EntrySize: 1 # DATA-NEXT: SectionData ( -# DATA-NEXT: 0000: 6C6F6E67 20756E73 69676E65 6420696E |long unsigned in| -# DATA-NEXT: 0010: 7400756E 7369676E 65642063 68617200 |t.unsigned char.| -# DATA-NEXT: 0020: 756E7369 676E6564 20696E74 00636861 |unsigned int.cha| -# DATA-NEXT: 0030: 72007368 6F727420 756E7369 676E6564 |r.short unsigned| -# DATA-NEXT: 0040: 20696E74 00 | int.| +# DATA-NEXT: 0000: 73686F72 7420756E 7369676E 65642069 |short unsigned i| +# DATA-NEXT: 0010: 6E74006C 6F6E6720 756E7369 676E6564 |nt.long unsigned| +# DATA-NEXT: 0020: 20696E74 00756E73 69676E65 6420696E | int.unsigned in| +# DATA-NEXT: 0030: 7400756E 7369676E 65642063 68617200 |t.unsigned char.| +# DATA-NEXT: 0040: 63686172 00 |char.| # DATA-NEXT: ) # DATA-NEXT: } Index: test/ELF/debug-gc.s =================================================================== --- test/ELF/debug-gc.s +++ test/ELF/debug-gc.s @@ -4,11 +4,11 @@ # RUN: llvm-objdump -s %t1 | FileCheck %s # CHECK: Contents of section .debug_str: -# CHECK-NEXT: 0000 41414100 43434300 42424200 AAA.CCC.BBB. +# CHECK-NEXT: 0000 41414100 42424200 43434300 AAA.BBB.CCC. # CHECK: Contents of section .foo: # CHECK-NEXT: 0000 2a000000 # CHECK: Contents of section .debug_info: -# CHECK-NEXT: 0000 00000000 08000000 +# CHECK-NEXT: 0000 00000000 04000000 .globl _start _start: Index: test/ELF/emit-relocs-mergeable-i386.s =================================================================== --- test/ELF/emit-relocs-mergeable-i386.s +++ test/ELF/emit-relocs-mergeable-i386.s @@ -5,7 +5,7 @@ ## Check lf we produce proper relocations when doing merging of SHF_MERGE sections. -## Check addends of relocations are: 0x0, 0x8, 0x8, 0x4 +## Check addends of relocations are: 0x0, 0x4, 0x4, 0x8 # CHECK: Section { # CHECK: Index: # CHECK: Name: .foo @@ -22,11 +22,11 @@ # CHECK-NEXT: AddressAlignment: # CHECK-NEXT: EntrySize: # CHECK-NEXT: SectionData ( -# CHECK-NEXT: 0000: 00000000 08000000 08000000 04000000 +# CHECK-NEXT: 0000: 00000000 04000000 04000000 08000000 # CHECK-NEXT: ) # CHECK-NEXT: } -## Check that offsets for AAA is 0x0, for BBB is 0x8 and CCC has offset 0x4. +## Check that offsets for AAA is 0x0, for BBB is 0x4 and CCC has offset 0x8. # CHECK: Section { # CHECK: Index: # CHECK: Name: .strings @@ -43,7 +43,7 @@ # CHECK-NEXT: AddressAlignment: # CHECK-NEXT: EntrySize: # CHECK-NEXT: SectionData ( -# CHECK-NEXT: |AAA.CCC.BBB.| +# CHECK-NEXT: |AAA.BBB.CCC.| # CHECK-NEXT: ) # CHECK-NEXT: } Index: test/ELF/emit-relocs-mergeable.s =================================================================== --- test/ELF/emit-relocs-mergeable.s +++ test/ELF/emit-relocs-mergeable.s @@ -21,16 +21,16 @@ # CHECK-NEXT: AddressAlignment: # CHECK-NEXT: EntrySize: # CHECK-NEXT: SectionData ( -# CHECK-NEXT: 0000: 41414100 43434300 42424200 |AAA.CCC.BBB.| +# CHECK-NEXT: 0000: 41414100 42424200 43434300 |AAA.BBB.CCC.| # CHECK-NEXT: ) # CHECK-NEXT: } # CHECK: Relocations [ # CHECK-NEXT: Section {{.*}} .rela.foo { # CHECK-NEXT: 0x201000 R_X86_64_64 .strings 0x0 -# CHECK-NEXT: 0x201008 R_X86_64_64 .strings 0x8 -# CHECK-NEXT: 0x201010 R_X86_64_64 .strings 0x8 -# CHECK-NEXT: 0x201018 R_X86_64_64 .strings 0x4 +# CHECK-NEXT: 0x201008 R_X86_64_64 .strings 0x4 +# CHECK-NEXT: 0x201010 R_X86_64_64 .strings 0x4 +# CHECK-NEXT: 0x201018 R_X86_64_64 .strings 0x8 # CHECK-NEXT: } # CHECK-NEXT: ] Index: test/ELF/merge-string-no-null.s =================================================================== --- test/ELF/merge-string-no-null.s +++ test/ELF/merge-string-no-null.s @@ -5,4 +5,4 @@ .section .rodata.str1.1,"aMS",@progbits,1 .ascii "abc" -// CHECK: string is not null terminated +// CHECK: string is too short or not null terminated Index: test/ELF/relocatable-compressed-input.s =================================================================== --- test/ELF/relocatable-compressed-input.s +++ test/ELF/relocatable-compressed-input.s @@ -24,11 +24,11 @@ # CHECK-NEXT: AddressAlignment: 1 # CHECK-NEXT: EntrySize: 1 # CHECK-NEXT: SectionData ( -# CHECK-NEXT: 0000: {{.*}} |long unsigned in| -# CHECK-NEXT: 0010: {{.*}} |t.unsigned char.| -# CHECK-NEXT: 0020: {{.*}} |unsigned int.cha| -# CHECK-NEXT: 0030: {{.*}} |r.short unsigned| -# CHECK-NEXT: 0040: {{.*}} | int.| +# CHECK-NEXT: 0000: {{.*}} |short unsigned i| +# CHECK-NEXT: 0010: {{.*}} |nt.long unsigned| +# CHECK-NEXT: 0020: {{.*}} | int.unsigned in| +# CHECK-NEXT: 0030: {{.*}} |t.unsigned char.| +# CHECK-NEXT: 0040: {{.*}} |char.| # CHECK-NEXT: ) # CHECK-NEXT: } Index: test/ELF/string-gc.s =================================================================== --- test/ELF/string-gc.s +++ test/ELF/string-gc.s @@ -14,7 +14,7 @@ // CHECK-NEXT: } // CHECK-NEXT: Symbol { // CHECK-NEXT: Name: s3 -// CHECK-NEXT: Value: 0x200120 +// CHECK-NEXT: Value: 0x200125 // CHECK-NEXT: Size: 0 // CHECK-NEXT: Binding: Local (0x0) // CHECK-NEXT: Type: Object (0x1) @@ -23,7 +23,7 @@ // CHECK-NEXT: } // CHECK-NEXT: Symbol { // CHECK-NEXT: Name: s1 -// CHECK-NEXT: Value: 0x200125 +// CHECK-NEXT: Value: 0x200120 // CHECK-NEXT: Size: 0 // CHECK-NEXT: Binding: Local (0x0) // CHECK-NEXT: Type: Object (0x1)