Index: lld/ELF/SyntheticSections.cpp =================================================================== --- lld/ELF/SyntheticSections.cpp +++ lld/ELF/SyntheticSections.cpp @@ -1679,6 +1679,56 @@ relativeGroups.emplace_back(std::move(group)); } + // For non-relative relocations, we would like to: + // 1. Have relocations with the same symbol offset to be consecutive, so + // that the runtime linker can speed-up symbol lookup by implementing an + // 1-entry cache. + // 2. Group relocations by r_info to reduce the size of the relocation + // section. + // Since the symbol offset is the high bits in r_info, sorting by r_info + // allows us to do both. + // + // For Rela, we also want to sort by r_addend when r_info is the same. This + // enables us to group by r_addend as well. + llvm::stable_sort(nonRelatives, [](const Elf_Rela &a, const Elf_Rela &b) { + if (a.r_info != b.r_info) + return a.r_info < b.r_info; + if (config->isRela) + return a.r_addend < b.r_addend; + return false; + }); + + // Group relocations with the same r_info. Note that each group emits a group + // header and that may make the relocation section larger. It is hard to + // estimate the size of a group header as the encoded size of that varies + // based on r_info. However, we can approximate this trade-off by the number + // of values encoded. Each group header contains 3 values, and each + // relocation in a group encodes one less value, as compared to when it is + // not grouped. Therefore, we only group relocations if there are 3 or more + // of them with the same r_info. + // + // For Rela, the addend for most non-relative relocations is zero, and thus + // we can usually get a smaller relocation section if we group by addend + // as well. + std::vector ungroupedNonRelatives; + std::vector> nonRelativeGroups; + for (auto i = nonRelatives.begin(), e = nonRelatives.end(); i != e;) { + auto j = i + 1; + while (j != e && i->r_info == j->r_info && + (!config->isRela || i->r_addend == j->r_addend)) + ++j; + if (j - i < 3) + ungroupedNonRelatives.insert(ungroupedNonRelatives.end(), i, j); + else + nonRelativeGroups.emplace_back(i, j); + i = j; + } + + // Sort ungrouped relocations by offset to minimize the encoded length. + llvm::sort(ungroupedNonRelatives, [](const Elf_Rela &a, const Elf_Rela &b) { + return a.r_offset < b.r_offset; + }); + unsigned hasAddendIfRela = config->isRela ? RELOCATION_GROUP_HAS_ADDEND_FLAG : 0; @@ -1733,14 +1783,30 @@ } } - // Finally the non-relative relocations. - llvm::sort(nonRelatives, [](const Elf_Rela &a, const Elf_Rela &b) { - return a.r_offset < b.r_offset; - }); - if (!nonRelatives.empty()) { - add(nonRelatives.size()); + const unsigned groupedByAddendIfRela = + config->isRela ? RELOCATION_GROUPED_BY_ADDEND_FLAG : 0; + + // Grouped non-relatives. + for (std::vector &g : nonRelativeGroups) { + add(g.size()); + add(RELOCATION_GROUPED_BY_INFO_FLAG | hasAddendIfRela | + groupedByAddendIfRela); + add(g[0].r_info); + if (config->isRela) { + add(g[0].r_addend - addend); + addend = g[0].r_addend; + } + for (Elf_Rela &r : g) { + add(r.r_offset - offset); + offset = r.r_offset; + } + } + + // Finally the ungrouped non-relative relocations. + if (!ungroupedNonRelatives.empty()) { + add(ungroupedNonRelatives.size()); add(hasAddendIfRela); - for (Elf_Rela &r : nonRelatives) { + for (Elf_Rela &r : ungroupedNonRelatives) { add(r.r_offset - offset); offset = r.r_offset; add(r.r_info); Index: lld/test/ELF/pack-dyn-relocs.s =================================================================== --- lld/test/ELF/pack-dyn-relocs.s +++ lld/test/ELF/pack-dyn-relocs.s @@ -25,7 +25,6 @@ // UNPACKED32-NEXT: 0x2038 R_ARM_RELATIVE - 0x0 // UNPACKED32-NEXT: 0x203C R_ARM_RELATIVE - 0x0 -// UNPACKED32-NEXT: 0x2044 R_ARM_RELATIVE - 0x0 // UNPACKED32-NEXT: 0x2048 R_ARM_RELATIVE - 0x0 // UNPACKED32-NEXT: 0x204C R_ARM_RELATIVE - 0x0 // UNPACKED32-NEXT: 0x2050 R_ARM_RELATIVE - 0x0 @@ -34,9 +33,16 @@ // UNPACKED32-NEXT: 0x205C R_ARM_RELATIVE - 0x0 // UNPACKED32-NEXT: 0x2060 R_ARM_RELATIVE - 0x0 // UNPACKED32-NEXT: 0x2064 R_ARM_RELATIVE - 0x0 +// UNPACKED32-NEXT: 0x2068 R_ARM_RELATIVE - 0x0 -// UNPACKED32-NEXT: 0x2069 R_ARM_RELATIVE - 0x0 +// UNPACKED32-NEXT: 0x206D R_ARM_RELATIVE - 0x0 // UNPACKED32-NEXT: 0x2020 R_ARM_ABS32 bar2 0x0 +// UNPACKED32-NEXT: 0x2044 R_ARM_ABS32 bar2 0x0 +// UNPACKED32-NEXT: 0x2071 R_ARM_ABS32 bar2 0x0 +// UNPACKED32-NEXT: 0x2075 R_ARM_ABS32 bar2 0x0 +// UNPACKED32-NEXT: 0x2079 R_ARM_ABS32 bar2 0x0 +// UNPACKED32-NEXT: 0x207D R_ARM_ABS32 bar2 0x0 +// UNPACKED32-NEXT: 0x2081 R_ARM_ABS32 bar2 0x0 // UNPACKED32-NEXT: 0x2040 R_ARM_ABS32 zed2 0x0 // UNPACKED32-NEXT: } @@ -75,7 +81,6 @@ // ANDROID32-NEXT: 0x2018 R_ARM_RELATIVE - 0x0 // ANDROID32-NEXT: 0x201C R_ARM_RELATIVE - 0x0 -// ANDROID32-NEXT: 0x2044 R_ARM_RELATIVE - 0x0 // ANDROID32-NEXT: 0x2048 R_ARM_RELATIVE - 0x0 // ANDROID32-NEXT: 0x204C R_ARM_RELATIVE - 0x0 // ANDROID32-NEXT: 0x2050 R_ARM_RELATIVE - 0x0 @@ -84,6 +89,7 @@ // ANDROID32-NEXT: 0x205C R_ARM_RELATIVE - 0x0 // ANDROID32-NEXT: 0x2060 R_ARM_RELATIVE - 0x0 // ANDROID32-NEXT: 0x2064 R_ARM_RELATIVE - 0x0 +// ANDROID32-NEXT: 0x2068 R_ARM_RELATIVE - 0x0 // ANDROID32-NEXT: 0x2024 R_ARM_RELATIVE - 0x0 // ANDROID32-NEXT: 0x2028 R_ARM_RELATIVE - 0x0 @@ -93,8 +99,16 @@ // ANDROID32-NEXT: 0x2038 R_ARM_RELATIVE - 0x0 // ANDROID32-NEXT: 0x203C R_ARM_RELATIVE - 0x0 -// ANDROID32-NEXT: 0x2069 R_ARM_RELATIVE - 0x0 +// ANDROID32-NEXT: 0x206D R_ARM_RELATIVE - 0x0 + // ANDROID32-NEXT: 0x2020 R_ARM_ABS32 bar2 0x0 +// ANDROID32-NEXT: 0x2044 R_ARM_ABS32 bar2 0x0 +// ANDROID32-NEXT: 0x2071 R_ARM_ABS32 bar2 0x0 +// ANDROID32-NEXT: 0x2075 R_ARM_ABS32 bar2 0x0 +// ANDROID32-NEXT: 0x2079 R_ARM_ABS32 bar2 0x0 +// ANDROID32-NEXT: 0x207D R_ARM_ABS32 bar2 0x0 +// ANDROID32-NEXT: 0x2081 R_ARM_ABS32 bar2 0x0 + // ANDROID32-NEXT: 0x2040 R_ARM_ABS32 zed2 0x0 // ANDROID32-NEXT: } @@ -127,15 +141,21 @@ // encoding the offsets for relative relocation. // RAW-RELR32: Section ({{.+}}) .relr.dyn { // RAW-RELR32-NEXT: 0x2000 -// RAW-RELR32-NEXT: 0x3FEFEFF +// RAW-RELR32-NEXT: 0x7FCFEFF // RAW-RELR32-NEXT: } // Decoded SHT_RELR section is same as UNPACKED, // but contains only the relative relocations. // Any relative relocations with odd offset stay in SHT_REL. // RELR32: Section ({{.+}}) .rel.dyn { -// RELR32-NEXT: 0x2069 R_ARM_RELATIVE - 0x0 +// RELR32-NEXT: 0x206D R_ARM_RELATIVE - 0x0 // RELR32-NEXT: 0x2020 R_ARM_ABS32 bar2 0x0 +// RELR32-NEXT: 0x2044 R_ARM_ABS32 bar2 0x0 +// RELR32-NEXT: 0x2071 R_ARM_ABS32 bar2 0x0 +// RELR32-NEXT: 0x2075 R_ARM_ABS32 bar2 0x0 +// RELR32-NEXT: 0x2079 R_ARM_ABS32 bar2 0x0 +// RELR32-NEXT: 0x207D R_ARM_ABS32 bar2 0x0 +// RELR32-NEXT: 0x2081 R_ARM_ABS32 bar2 0x0 // RELR32-NEXT: 0x2040 R_ARM_ABS32 zed2 0x0 // RELR32-NEXT: } // RELR32-NEXT: Section ({{.+}}) .relr.dyn { @@ -156,7 +176,6 @@ // RELR32-NEXT: 0x2038 R_ARM_RELATIVE - 0x0 // RELR32-NEXT: 0x203C R_ARM_RELATIVE - 0x0 -// RELR32-NEXT: 0x2044 R_ARM_RELATIVE - 0x0 // RELR32-NEXT: 0x2048 R_ARM_RELATIVE - 0x0 // RELR32-NEXT: 0x204C R_ARM_RELATIVE - 0x0 // RELR32-NEXT: 0x2050 R_ARM_RELATIVE - 0x0 @@ -165,6 +184,7 @@ // RELR32-NEXT: 0x205C R_ARM_RELATIVE - 0x0 // RELR32-NEXT: 0x2060 R_ARM_RELATIVE - 0x0 // RELR32-NEXT: 0x2064 R_ARM_RELATIVE - 0x0 +// RELR32-NEXT: 0x2068 R_ARM_RELATIVE - 0x0 // RELR32-NEXT: } // RUN: llvm-mc -filetype=obj -triple=aarch64-unknown-linux %p/Inputs/shared2.s -o %t.a64.so.o @@ -191,18 +211,24 @@ // UNPACKED64-NEXT: 0x20070 R_AARCH64_RELATIVE - 0x6 // UNPACKED64-NEXT: 0x20078 R_AARCH64_RELATIVE - 0x7 -// UNPACKED64-NEXT: 0x20088 R_AARCH64_RELATIVE - 0x1 -// UNPACKED64-NEXT: 0x20090 R_AARCH64_RELATIVE - 0x2 -// UNPACKED64-NEXT: 0x20098 R_AARCH64_RELATIVE - 0x3 -// UNPACKED64-NEXT: 0x200A0 R_AARCH64_RELATIVE - 0x4 -// UNPACKED64-NEXT: 0x200A8 R_AARCH64_RELATIVE - 0x5 -// UNPACKED64-NEXT: 0x200B0 R_AARCH64_RELATIVE - 0x6 -// UNPACKED64-NEXT: 0x200B8 R_AARCH64_RELATIVE - 0x7 -// UNPACKED64-NEXT: 0x200C0 R_AARCH64_RELATIVE - 0x8 -// UNPACKED64-NEXT: 0x200C8 R_AARCH64_RELATIVE - 0x9 - -// UNPACKED64-NEXT: 0x200D1 R_AARCH64_RELATIVE - 0xA +// UNPACKED64-NEXT: 0x20090 R_AARCH64_RELATIVE - 0x1 +// UNPACKED64-NEXT: 0x20098 R_AARCH64_RELATIVE - 0x2 +// UNPACKED64-NEXT: 0x200A0 R_AARCH64_RELATIVE - 0x3 +// UNPACKED64-NEXT: 0x200A8 R_AARCH64_RELATIVE - 0x4 +// UNPACKED64-NEXT: 0x200B0 R_AARCH64_RELATIVE - 0x5 +// UNPACKED64-NEXT: 0x200B8 R_AARCH64_RELATIVE - 0x6 +// UNPACKED64-NEXT: 0x200C0 R_AARCH64_RELATIVE - 0x7 +// UNPACKED64-NEXT: 0x200C8 R_AARCH64_RELATIVE - 0x8 +// UNPACKED64-NEXT: 0x200D0 R_AARCH64_RELATIVE - 0x9 + +// UNPACKED64-NEXT: 0x200D9 R_AARCH64_RELATIVE - 0xA // UNPACKED64-NEXT: 0x20040 R_AARCH64_ABS64 bar2 0x1 +// UNPACKED64-NEXT: 0x20088 R_AARCH64_ABS64 bar2 0x1 +// UNPACKED64-NEXT: 0x200E1 R_AARCH64_ABS64 bar2 0x1 +// UNPACKED64-NEXT: 0x200E9 R_AARCH64_ABS64 bar2 0x3 +// UNPACKED64-NEXT: 0x200F1 R_AARCH64_ABS64 bar2 0x3 +// UNPACKED64-NEXT: 0x200F9 R_AARCH64_ABS64 bar2 0x3 +// UNPACKED64-NEXT: 0x20101 R_AARCH64_ABS64 bar2 0x1 // UNPACKED64-NEXT: 0x20080 R_AARCH64_ABS64 zed2 0x0 // UNPACKED64-NEXT: } @@ -239,15 +265,15 @@ // ANDROID64-NEXT: 0x20030 R_AARCH64_RELATIVE - 0x7 // ANDROID64-NEXT: 0x20038 R_AARCH64_RELATIVE - 0x8 -// ANDROID64-NEXT: 0x20088 R_AARCH64_RELATIVE - 0x1 -// ANDROID64-NEXT: 0x20090 R_AARCH64_RELATIVE - 0x2 -// ANDROID64-NEXT: 0x20098 R_AARCH64_RELATIVE - 0x3 -// ANDROID64-NEXT: 0x200A0 R_AARCH64_RELATIVE - 0x4 -// ANDROID64-NEXT: 0x200A8 R_AARCH64_RELATIVE - 0x5 -// ANDROID64-NEXT: 0x200B0 R_AARCH64_RELATIVE - 0x6 -// ANDROID64-NEXT: 0x200B8 R_AARCH64_RELATIVE - 0x7 -// ANDROID64-NEXT: 0x200C0 R_AARCH64_RELATIVE - 0x8 -// ANDROID64-NEXT: 0x200C8 R_AARCH64_RELATIVE - 0x9 +// ANDROID64-NEXT: 0x20090 R_AARCH64_RELATIVE - 0x1 +// ANDROID64-NEXT: 0x20098 R_AARCH64_RELATIVE - 0x2 +// ANDROID64-NEXT: 0x200A0 R_AARCH64_RELATIVE - 0x3 +// ANDROID64-NEXT: 0x200A8 R_AARCH64_RELATIVE - 0x4 +// ANDROID64-NEXT: 0x200B0 R_AARCH64_RELATIVE - 0x5 +// ANDROID64-NEXT: 0x200B8 R_AARCH64_RELATIVE - 0x6 +// ANDROID64-NEXT: 0x200C0 R_AARCH64_RELATIVE - 0x7 +// ANDROID64-NEXT: 0x200C8 R_AARCH64_RELATIVE - 0x8 +// ANDROID64-NEXT: 0x200D0 R_AARCH64_RELATIVE - 0x9 // ANDROID64-NEXT: 0x20048 R_AARCH64_RELATIVE - 0x1 // ANDROID64-NEXT: 0x20050 R_AARCH64_RELATIVE - 0x2 @@ -257,8 +283,17 @@ // ANDROID64-NEXT: 0x20070 R_AARCH64_RELATIVE - 0x6 // ANDROID64-NEXT: 0x20078 R_AARCH64_RELATIVE - 0x7 -// ANDROID64-NEXT: 0x200D1 R_AARCH64_RELATIVE - 0xA +// ANDROID64-NEXT: 0x200D9 R_AARCH64_RELATIVE - 0xA + // ANDROID64-NEXT: 0x20040 R_AARCH64_ABS64 bar2 0x1 +// ANDROID64-NEXT: 0x20088 R_AARCH64_ABS64 bar2 0x1 +// ANDROID64-NEXT: 0x200E1 R_AARCH64_ABS64 bar2 0x1 +// ANDROID64-NEXT: 0x20101 R_AARCH64_ABS64 bar2 0x1 + +// ANDROID64-NEXT: 0x200E9 R_AARCH64_ABS64 bar2 0x3 +// ANDROID64-NEXT: 0x200F1 R_AARCH64_ABS64 bar2 0x3 +// ANDROID64-NEXT: 0x200F9 R_AARCH64_ABS64 bar2 0x3 + // ANDROID64-NEXT: 0x20080 R_AARCH64_ABS64 zed2 0x0 // ANDROID64-NEXT: } @@ -291,15 +326,21 @@ // encoding the offsets for relative relocation. // RAW-RELR64: Section ({{.+}}) .relr.dyn { // RAW-RELR64-NEXT: 0x20000 -// RAW-RELR64-NEXT: 0x3FEFEFF +// RAW-RELR64-NEXT: 0x7FCFEFF // RAW-RELR64-NEXT: } // Decoded SHT_RELR section is same as UNPACKED, // but contains only the relative relocations. // Any relative relocations with odd offset stay in SHT_RELA. // RELR64: Section ({{.+}}) .rela.dyn { -// RELR64-NEXT: 0x200D1 R_AARCH64_RELATIVE - 0xA +// RELR64-NEXT: 0x200D9 R_AARCH64_RELATIVE - 0xA // RELR64-NEXT: 0x20040 R_AARCH64_ABS64 bar2 0x1 +// RELR64-NEXT: 0x20088 R_AARCH64_ABS64 bar2 0x1 +// RELR64-NEXT: 0x200E1 R_AARCH64_ABS64 bar2 0x1 +// RELR64-NEXT: 0x200E9 R_AARCH64_ABS64 bar2 0x3 +// RELR64-NEXT: 0x200F1 R_AARCH64_ABS64 bar2 0x3 +// RELR64-NEXT: 0x200F9 R_AARCH64_ABS64 bar2 0x3 +// RELR64-NEXT: 0x20101 R_AARCH64_ABS64 bar2 0x1 // RELR64-NEXT: 0x20080 R_AARCH64_ABS64 zed2 0x0 // RELR64-NEXT: } // RELR64-NEXT: Section ({{.+}}) .relr.dyn { @@ -320,7 +361,6 @@ // RELR64-NEXT: 0x20070 R_AARCH64_RELATIVE - 0x0 // RELR64-NEXT: 0x20078 R_AARCH64_RELATIVE - 0x0 -// RELR64-NEXT: 0x20088 R_AARCH64_RELATIVE - 0x0 // RELR64-NEXT: 0x20090 R_AARCH64_RELATIVE - 0x0 // RELR64-NEXT: 0x20098 R_AARCH64_RELATIVE - 0x0 // RELR64-NEXT: 0x200A0 R_AARCH64_RELATIVE - 0x0 @@ -329,6 +369,7 @@ // RELR64-NEXT: 0x200B8 R_AARCH64_RELATIVE - 0x0 // RELR64-NEXT: 0x200C0 R_AARCH64_RELATIVE - 0x0 // RELR64-NEXT: 0x200C8 R_AARCH64_RELATIVE - 0x0 +// RELR64-NEXT: 0x200D0 R_AARCH64_RELATIVE - 0x0 // RELR64-NEXT: } .data @@ -351,6 +392,7 @@ .dc.a __ehdr_start + 6 .dc.a __ehdr_start + 7 .dc.a zed2 +.dc.a bar2 + 1 .dc.a __ehdr_start + 1 .dc.a __ehdr_start + 2 @@ -363,3 +405,8 @@ .dc.a __ehdr_start + 9 .byte 00 .dc.a __ehdr_start + 10 +.dc.a bar2 + 1 +.dc.a bar2 + 3 +.dc.a bar2 + 3 +.dc.a bar2 + 3 +.dc.a bar2 + 1