Index: lld/ELF/SyntheticSections.cpp
===================================================================
--- lld/ELF/SyntheticSections.cpp
+++ lld/ELF/SyntheticSections.cpp
@@ -1679,6 +1679,35 @@
       relativeGroups.emplace_back(std::move(group));
   }
 
+  // Sort by r_info first so that we can group relocations with the same r_info.
+  // The cost of each group varies based on r_info, but we can approximate the
+  // cost analysis by the number of values encoded.  Each group adds 3 values to
+  // be encoded, and each relocation in a group encodes one less value, so we
+  // only group relocations if there are 3 or more of them with the same r_info.
+  llvm::sort(nonRelatives, [](const Elf_Rela &a, const Elf_Rela &b) {
+    return a.r_info < b.r_info;
+  });
+
+  std::vector<Elf_Rela> ungroupedNonRelatives;
+  std::vector<std::vector<Elf_Rela>> nonRelativeGroups;
+  for (auto i = nonRelatives.begin(), e = nonRelatives.end(); i != e;) {
+    std::vector<Elf_Rela> group;
+    do {
+      group.push_back(*i++);
+    } while (i != e && (i - 1)->r_info == i->r_info);
+
+    if (group.size() < 3)
+      ungroupedNonRelatives.insert(ungroupedNonRelatives.end(), group.begin(),
+                                   group.end());
+    else
+      nonRelativeGroups.emplace_back(std::move(group));
+  }
+
+  // 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 +1762,26 @@
     }
   }
 
-  // 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());
+  // Grouped non-relatives.
+  for (std::vector<Elf_Rela> &g : nonRelativeGroups) {
+    add(g.size());
+    add(RELOCATION_GROUPED_BY_INFO_FLAG | hasAddendIfRela);
+    add(g[0].r_info);
+    for (Elf_Rela &r : g) {
+      add(r.r_offset - offset);
+      offset = r.r_offset;
+      if (config->isRela) {
+        add(r.r_addend - addend);
+        addend = r.r_addend;
+      }
+    }
+  }
+
+  // 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);