Index: lld/ELF/SyntheticSections.cpp =================================================================== --- lld/ELF/SyntheticSections.cpp +++ lld/ELF/SyntheticSections.cpp @@ -1679,12 +1679,81 @@ relativeGroups.emplace_back(std::move(group)); } - unsigned hasAddendIfRela = + // 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 || i->r_addend != 0) + 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; + }); + + const unsigned hasAddendIfRela = config->isRela ? RELOCATION_GROUP_HAS_ADDEND_FLAG : 0; + const unsigned groupedByAddendIfRela = + config->isRela ? RELOCATION_GROUPED_BY_ADDEND_FLAG : 0; uint64_t offset = 0; uint64_t addend = 0; + // Emit the encoding for the groups of non-relative relocations first. We + // require relocations to have zero addend to be grouped, so emitting them + // first simplifies addend handling a little bit. + 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(0); + } + for (Elf_Rela &r : g) { + add(r.r_offset - offset); + offset = r.r_offset; + } + } + // Emit the run-length encoding for the groups of adjacent relative // relocations. Each group is represented using two groups in the packed // format. The first is used to set the current offset to the start of the @@ -1733,14 +1802,11 @@ } } - // 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()); + // 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: } @@ -63,9 +69,18 @@ // ANDROID32-HEADERS: 0x6000000F ANDROID_REL [[ADDR]] // ANDROID32-HEADERS: 0x60000010 ANDROID_RELSZ [[SIZE]] -// Packed should have the larger groups of relative relocations first, -// i.e. the 8 and 9 followed by the 7. +// Packed should have the groups of non-relative reloations first, followed +// by the larger groups of relative relocations (i.e. the 8 and 9 followed +// by the 7.) // ANDROID32: Section ({{.+}}) .rel.dyn { +// 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: 0x2000 R_ARM_RELATIVE - 0x0 // ANDROID32-NEXT: 0x2004 R_ARM_RELATIVE - 0x0 // ANDROID32-NEXT: 0x2008 R_ARM_RELATIVE - 0x0 @@ -75,7 +90,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 +98,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 +108,8 @@ // ANDROID32-NEXT: 0x2038 R_ARM_RELATIVE - 0x0 // ANDROID32-NEXT: 0x203C R_ARM_RELATIVE - 0x0 -// ANDROID32-NEXT: 0x2069 R_ARM_RELATIVE - 0x0 -// ANDROID32-NEXT: 0x2020 R_ARM_ABS32 bar2 0x0 +// ANDROID32-NEXT: 0x206D R_ARM_RELATIVE - 0x0 + // ANDROID32-NEXT: 0x2040 R_ARM_ABS32 zed2 0x0 // ANDROID32-NEXT: } @@ -127,15 +142,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 +177,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 +185,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 +212,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 0x0 +// UNPACKED64-NEXT: 0x200E1 R_AARCH64_ABS64 bar2 0x0 +// UNPACKED64-NEXT: 0x200E9 R_AARCH64_ABS64 bar2 0x0 +// UNPACKED64-NEXT: 0x200F1 R_AARCH64_ABS64 bar2 0x1 +// UNPACKED64-NEXT: 0x200F9 R_AARCH64_ABS64 bar2 0x1 +// UNPACKED64-NEXT: 0x20101 R_AARCH64_ABS64 bar2 0x0 // UNPACKED64-NEXT: 0x20080 R_AARCH64_ABS64 zed2 0x0 // UNPACKED64-NEXT: } @@ -230,6 +257,11 @@ // ANDROID64-HEADERS: 0x0000000060000012 ANDROID_RELASZ [[SIZE]] // ANDROID64: Section ({{.+}}) .rela.dyn { +// ANDROID64-NEXT: 0x20088 R_AARCH64_ABS64 bar2 0x0 +// ANDROID64-NEXT: 0x200E1 R_AARCH64_ABS64 bar2 0x0 +// ANDROID64-NEXT: 0x200E9 R_AARCH64_ABS64 bar2 0x0 +// ANDROID64-NEXT: 0x20101 R_AARCH64_ABS64 bar2 0x0 + // ANDROID64-NEXT: 0x20000 R_AARCH64_RELATIVE - 0x1 // ANDROID64-NEXT: 0x20008 R_AARCH64_RELATIVE - 0x2 // ANDROID64-NEXT: 0x20010 R_AARCH64_RELATIVE - 0x3 @@ -239,15 +271,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,9 +289,12 @@ // 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: 0x20080 R_AARCH64_ABS64 zed2 0x0 +// ANDROID64-NEXT: 0x200F1 R_AARCH64_ABS64 bar2 0x1 +// ANDROID64-NEXT: 0x200F9 R_AARCH64_ABS64 bar2 0x1 // ANDROID64-NEXT: } // RUN: ld.lld -pie --pack-dyn-relocs=relr %t.a64 %t.a64.so -o %t4.a64 @@ -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 0x0 +// RELR64-NEXT: 0x200E1 R_AARCH64_ABS64 bar2 0x0 +// RELR64-NEXT: 0x200E9 R_AARCH64_ABS64 bar2 0x0 +// RELR64-NEXT: 0x200F1 R_AARCH64_ABS64 bar2 0x1 +// RELR64-NEXT: 0x200F9 R_AARCH64_ABS64 bar2 0x1 +// RELR64-NEXT: 0x20101 R_AARCH64_ABS64 bar2 0x0 // 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 .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 +.dc.a bar2 +.dc.a bar2 + 1 +.dc.a bar2 + 1 +.dc.a bar2