Index: lld/ELF/Config.h
===================================================================
--- lld/ELF/Config.h
+++ lld/ELF/Config.h
@@ -103,6 +103,7 @@
   std::vector<SymbolVersion> VersionScriptLocals;
   std::vector<uint8_t> BuildIdVector;
   bool AllowMultipleDefinition;
+  bool AndroidPackRelocs;
   bool AsNeeded = false;
   bool Bsymbolic;
   bool BsymbolicFunctions;
Index: lld/ELF/Driver.cpp
===================================================================
--- lld/ELF/Driver.cpp
+++ lld/ELF/Driver.cpp
@@ -623,6 +623,7 @@
 void LinkerDriver::readConfigs(opt::InputArgList &Args) {
   Config->AllowMultipleDefinition =
       Args.hasArg(OPT_allow_multiple_definition) || hasZOption(Args, "muldefs");
+  Config->AndroidPackRelocs = Args.hasArg(OPT_android_pack_relocs);
   Config->AuxiliaryList = getArgs(Args, OPT_auxiliary);
   Config->Bsymbolic = Args.hasArg(OPT_Bsymbolic);
   Config->BsymbolicFunctions = Args.hasArg(OPT_Bsymbolic_functions);
Index: lld/ELF/Options.td
===================================================================
--- lld/ELF/Options.td
+++ lld/ELF/Options.td
@@ -12,6 +12,8 @@
   def _eq: Joined<["--", "-"], name # "=">, Alias<!cast<Separate>(NAME)>;
 }
 
+def android_pack_relocs: F<"android-pack-relocs">, HelpText<"Use the Android relocation packing format">;
+
 def auxiliary: S<"auxiliary">, HelpText<"Set DT_AUXILIARY field to the specified name">;
 
 def Bsymbolic: F<"Bsymbolic">, HelpText<"Bind defined symbols locally">;
Index: lld/ELF/SyntheticSections.h
===================================================================
--- lld/ELF/SyntheticSections.h
+++ lld/ELF/SyntheticSections.h
@@ -45,7 +45,7 @@
   virtual void finalizeContents() {}
   // If the section has the SHF_ALLOC flag and the size may be changed if
   // thunks are added, update the section size.
-  virtual void updateAllocSize() {}
+  virtual bool updateAllocSize() { return false; }
   // If any additional finalization of contents are needed post thunk creation.
   virtual void postThunkContents() {}
   virtual bool empty() const { return false; }
@@ -166,7 +166,7 @@
   MipsGotSection();
   void writeTo(uint8_t *Buf) override;
   size_t getSize() const override { return Size; }
-  void updateAllocSize() override;
+  bool updateAllocSize() override;
   void finalizeContents() override;
   bool empty() const override;
   void addEntry(SymbolBody &Sym, int64_t Addend, RelExpr Expr);
@@ -371,24 +371,52 @@
   uint64_t Size = 0;
 };
 
-template <class ELFT> class RelocationSection final : public SyntheticSection {
+class RelocationBaseSection : public SyntheticSection {
+public:
+  RelocationBaseSection(StringRef Name, uint32_t Type, int32_t DynamicTag,
+                        int32_t SizeDynamicTag);
+  void addReloc(const DynamicReloc &Reloc);
+  bool empty() const override { return Relocs.empty(); }
+  size_t getSize() const override { return Relocs.size() * this->Entsize; }
+  size_t getRelativeRelocCount() const { return NumRelativeRelocs; }
+  int32_t DynamicTag, SizeDynamicTag;
+
+protected:
+  std::vector<DynamicReloc> Relocs;
+  size_t NumRelativeRelocs = 0;
+};
+
+template <class ELFT>
+class RelocationSection final : public RelocationBaseSection {
   typedef typename ELFT::Rel Elf_Rel;
   typedef typename ELFT::Rela Elf_Rela;
 
 public:
   RelocationSection(StringRef Name, bool Sort);
-  void addReloc(const DynamicReloc &Reloc);
   unsigned getRelocOffset();
   void finalizeContents() override;
   void writeTo(uint8_t *Buf) override;
-  bool empty() const override { return Relocs.empty(); }
-  size_t getSize() const override { return Relocs.size() * this->Entsize; }
-  size_t getRelativeRelocCount() const { return NumRelativeRelocs; }
 
 private:
   bool Sort;
-  size_t NumRelativeRelocs = 0;
-  std::vector<DynamicReloc> Relocs;
+};
+
+template <class ELFT>
+class AndroidRelocationSection final : public RelocationBaseSection {
+  typedef typename ELFT::Rel Elf_Rel;
+  typedef typename ELFT::Rela Elf_Rela;
+
+public:
+  AndroidRelocationSection(StringRef Name);
+
+  bool updateAllocSize() override;
+  size_t getSize() const override { return RelocData.size(); }
+  void writeTo(uint8_t *Buf) override {
+    std::copy(RelocData.begin(), RelocData.end(), Buf);
+  }
+
+private:
+  SmallVector<char, 0> RelocData;
 };
 
 struct SymbolTableEntry {
@@ -838,7 +866,7 @@
 template <class ELFT> struct In : public InX {
   static EhFrameHeader<ELFT> *EhFrameHdr;
   static EhFrameSection<ELFT> *EhFrame;
-  static RelocationSection<ELFT> *RelaDyn;
+  static RelocationBaseSection *RelaDyn;
   static RelocationSection<ELFT> *RelaPlt;
   static RelocationSection<ELFT> *RelaIplt;
   static VersionDefinitionSection<ELFT> *VerDef;
@@ -848,7 +876,7 @@
 
 template <class ELFT> EhFrameHeader<ELFT> *In<ELFT>::EhFrameHdr;
 template <class ELFT> EhFrameSection<ELFT> *In<ELFT>::EhFrame;
-template <class ELFT> RelocationSection<ELFT> *In<ELFT>::RelaDyn;
+template <class ELFT> RelocationBaseSection *In<ELFT>::RelaDyn;
 template <class ELFT> RelocationSection<ELFT> *In<ELFT>::RelaPlt;
 template <class ELFT> RelocationSection<ELFT> *In<ELFT>::RelaIplt;
 template <class ELFT> VersionDefinitionSection<ELFT> *In<ELFT>::VerDef;
Index: lld/ELF/SyntheticSections.cpp
===================================================================
--- lld/ELF/SyntheticSections.cpp
+++ lld/ELF/SyntheticSections.cpp
@@ -32,6 +32,7 @@
 #include "llvm/Object/Decompressor.h"
 #include "llvm/Object/ELFObjectFile.h"
 #include "llvm/Support/Endian.h"
+#include "llvm/Support/LEB128.h"
 #include "llvm/Support/MD5.h"
 #include "llvm/Support/RandomNumberGenerator.h"
 #include "llvm/Support/SHA1.h"
@@ -828,7 +829,7 @@
 
 void MipsGotSection::finalizeContents() { updateAllocSize(); }
 
-void MipsGotSection::updateAllocSize() {
+bool MipsGotSection::updateAllocSize() {
   PageEntriesNum = 0;
   for (std::pair<const OutputSection *, size_t> &P : PageIndexMap) {
     // For each output section referenced by GOT page relocations calculate
@@ -842,6 +843,7 @@
   }
   Size = (getLocalEntriesNum() + GlobalEntries.size() + TlsEntries.size()) *
          Config->Wordsize;
+  return false;
 }
 
 bool MipsGotSection::empty() const {
@@ -1087,10 +1089,11 @@
 
   this->Link = InX::DynStrTab->getParent()->SectionIndex;
   if (In<ELFT>::RelaDyn->getParent() && !In<ELFT>::RelaDyn->empty()) {
-    bool IsRela = Config->IsRela;
-    add({IsRela ? DT_RELA : DT_REL, In<ELFT>::RelaDyn});
-    add({IsRela ? DT_RELASZ : DT_RELSZ, In<ELFT>::RelaDyn->getParent(),
+    add({In<ELFT>::RelaDyn->DynamicTag, In<ELFT>::RelaDyn});
+    add({In<ELFT>::RelaDyn->SizeDynamicTag, In<ELFT>::RelaDyn->getParent(),
          Entry::SecSize});
+
+    bool IsRela = Config->IsRela;
     add({IsRela ? DT_RELAENT : DT_RELENT,
          uint64_t(IsRela ? sizeof(Elf_Rela) : sizeof(Elf_Rel))});
 
@@ -1103,6 +1106,7 @@
         add({IsRela ? DT_RELACOUNT : DT_RELCOUNT, NumRelativeRels});
     }
   }
+
   if (In<ELFT>::RelaPlt->getParent() && !In<ELFT>::RelaPlt->empty()) {
     add({DT_JMPREL, In<ELFT>::RelaPlt});
     add({DT_PLTRELSZ, In<ELFT>::RelaPlt->getParent(), Entry::SecSize});
@@ -1226,21 +1230,40 @@
   return 0;
 }
 
-template <class ELFT>
-RelocationSection<ELFT>::RelocationSection(StringRef Name, bool Sort)
-    : SyntheticSection(SHF_ALLOC, Config->IsRela ? SHT_RELA : SHT_REL,
-                       Config->Wordsize, Name),
-      Sort(Sort) {
-  this->Entsize = Config->IsRela ? sizeof(Elf_Rela) : sizeof(Elf_Rel);
-}
+RelocationBaseSection::RelocationBaseSection(StringRef Name, uint32_t Type,
+                                             int32_t DynamicTag,
+                                             int32_t SizeDynamicTag)
+    : SyntheticSection(SHF_ALLOC, Type, Config->Wordsize, Name),
+      DynamicTag(DynamicTag), SizeDynamicTag(SizeDynamicTag) {}
 
-template <class ELFT>
-void RelocationSection<ELFT>::addReloc(const DynamicReloc &Reloc) {
+void RelocationBaseSection::addReloc(const DynamicReloc &Reloc) {
   if (Reloc.Type == Target->RelativeRel)
     ++NumRelativeRelocs;
   Relocs.push_back(Reloc);
 }
 
+template <class ELFT>
+static void encodeReloc(typename ELFT::Rela *P, const DynamicReloc &Rel) {
+  if (Config->IsRela)
+    P->r_addend = Rel.getAddend();
+  P->r_offset = Rel.getOffset();
+  if (Config->EMachine == EM_MIPS && Rel.getInputSec() == InX::MipsGot)
+    // Dynamic relocation against MIPS GOT section make deal TLS entries
+    // allocated in the end of the GOT. We need to adjust the offset to take
+    // in account 'local' and 'global' GOT entries.
+    P->r_offset += InX::MipsGot->getTlsOffset();
+  P->setSymbolAndType(Rel.getSymIndex(), Rel.Type, Config->IsMips64EL);
+}
+
+template <class ELFT>
+RelocationSection<ELFT>::RelocationSection(StringRef Name, bool Sort)
+    : RelocationBaseSection(Name, Config->IsRela ? SHT_RELA : SHT_REL,
+                            Config->IsRela ? DT_RELA : DT_REL,
+                            Config->IsRela ? DT_RELASZ : DT_RELSZ),
+      Sort(Sort) {
+  this->Entsize = Config->IsRela ? sizeof(Elf_Rela) : sizeof(Elf_Rel);
+}
+
 template <class ELFT, class RelTy>
 static bool compRelocations(const RelTy &A, const RelTy &B) {
   bool AIsRel = A.getType(Config->IsMips64EL) == Target->RelativeRel;
@@ -1254,18 +1277,8 @@
 template <class ELFT> void RelocationSection<ELFT>::writeTo(uint8_t *Buf) {
   uint8_t *BufBegin = Buf;
   for (const DynamicReloc &Rel : Relocs) {
-    auto *P = reinterpret_cast<Elf_Rela *>(Buf);
+    encodeReloc<ELFT>(reinterpret_cast<Elf_Rela *>(Buf), Rel);
     Buf += Config->IsRela ? sizeof(Elf_Rela) : sizeof(Elf_Rel);
-
-    if (Config->IsRela)
-      P->r_addend = Rel.getAddend();
-    P->r_offset = Rel.getOffset();
-    if (Config->EMachine == EM_MIPS && Rel.getInputSec() == InX::MipsGot)
-      // Dynamic relocation against MIPS GOT section make deal TLS entries
-      // allocated in the end of the GOT. We need to adjust the offset to take
-      // in account 'local' and 'global' GOT entries.
-      P->r_offset += InX::MipsGot->getTlsOffset();
-    P->setSymbolAndType(Rel.getSymIndex(), Rel.Type, Config->IsMips64EL);
   }
 
   if (Sort) {
@@ -1291,6 +1304,138 @@
   getParent()->Link = this->Link;
 }
 
+template <class ELFT>
+AndroidRelocationSection<ELFT>::AndroidRelocationSection(StringRef Name)
+    : RelocationBaseSection(
+          Name, Config->IsRela ? SHT_ANDROID_RELA : SHT_ANDROID_REL,
+          Config->IsRela ? DT_ANDROID_RELA : DT_ANDROID_REL,
+          Config->IsRela ? DT_ANDROID_RELASZ : DT_ANDROID_RELSZ) {
+  this->Entsize = 1;
+}
+
+template <class ELFT> bool AndroidRelocationSection<ELFT>::updateAllocSize() {
+  // This function computes the contents of an Android-format packed relocation
+  // section. An overview of the format can be found in the Android source code:
+  // https://android.googlesource.com/platform/bionic/+/refs/heads/master/tools/relocation_packer/src/delta_encoder.h
+  enum {
+    RELOCATION_GROUPED_BY_INFO_FLAG = 1,
+    RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG = 2,
+    RELOCATION_GROUPED_BY_ADDEND_FLAG = 4,
+    RELOCATION_GROUP_HAS_ADDEND_FLAG = 8,
+  };
+
+  size_t OldSize = RelocData.size();
+
+  RelocData.clear();
+  RelocData.push_back('A');
+  RelocData.push_back('P');
+  RelocData.push_back('S');
+  RelocData.push_back('2');
+  raw_svector_ostream OS(RelocData);
+
+  if (Config->IsRela) {
+    assert(0);
+  } else {
+    std::vector<uint64_t> Relatives;
+    std::vector<Elf_Rel> OtherRelocs;
+
+    for (const DynamicReloc &Rel : Relocs) {
+      Elf_Rela R;
+      encodeReloc<ELFT>(&R, Rel);
+
+      if (R.getType(Config->IsMips64EL) == Target->RelativeRel)
+        Relatives.push_back(R.r_offset);
+      else
+        OtherRelocs.push_back(R);
+    }
+
+    std::sort(Relatives.begin(), Relatives.end());
+    std::sort(OtherRelocs.begin(), OtherRelocs.end(),
+              [](const Elf_Rel &A, const Elf_Rel &B) {
+                return A.r_offset < B.r_offset;
+              });
+
+    // Try to find groups of relative relocations which are spaced one word
+    // apart from one another. These generally correspond to vtable entries. The
+    // format allows these groups to be encoded using a sort of run-length
+    // encoding, but each group will cost 7 bytes in addition to the offset from
+    // the previous group, so it is only profitable to do this for groups of
+    // size 8 or larger.
+    std::vector<uint64_t> UngroupedRelatives;
+    std::vector<std::pair<uint64_t, uint64_t>> RelativeGroups;
+    for (auto I = Relatives.begin(), E = Relatives.end(); I != E;) {
+      size_t GroupStart = *I++;
+      size_t GroupSize = 1;
+      while (I != E && *(I - 1) + Config->Wordsize == *I) {
+        ++I;
+        ++GroupSize;
+      }
+
+      if (GroupSize < 8) {
+        for (unsigned J = 0; J != GroupSize; ++J)
+          UngroupedRelatives.push_back(GroupStart + J * Config->Wordsize);
+      } else {
+        RelativeGroups.push_back({GroupStart, GroupSize});
+      }
+    }
+
+    // The format header includes the number of relocations and the initial
+    // offset (which we set to zero).
+    encodeSLEB128(Relocs.size(), OS);
+    encodeSLEB128(0, OS);
+
+    uint64_t Offset = 0;
+    // 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
+    // group (and also encodes the first relocation), and the second encodes the
+    // remaining relocations.
+    for (auto &P : RelativeGroups) {
+      // The first relocation in the group.
+      encodeSLEB128(1, OS);
+      encodeSLEB128(RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG |
+                        RELOCATION_GROUPED_BY_INFO_FLAG,
+                    OS);
+      encodeSLEB128(P.first - Offset, OS);
+      encodeSLEB128(Target->RelativeRel, OS);
+
+      // The remaining relocations.
+      encodeSLEB128(P.second - 1, OS);
+      encodeSLEB128(RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG |
+                        RELOCATION_GROUPED_BY_INFO_FLAG,
+                    OS);
+      encodeSLEB128(Config->Wordsize, OS);
+      encodeSLEB128(Target->RelativeRel, OS);
+
+      Offset = P.first + (P.second - 1) * Config->Wordsize;
+    }
+
+    // Now the ungrouped relatives.
+    if (!UngroupedRelatives.empty()) {
+      encodeSLEB128(UngroupedRelatives.size(), OS);
+      encodeSLEB128(RELOCATION_GROUPED_BY_INFO_FLAG, OS);
+      encodeSLEB128(Target->RelativeRel, OS);
+      for (uint64_t R : UngroupedRelatives) {
+        encodeSLEB128(R - Offset, OS);
+        Offset = R;
+      }
+    }
+
+    // Finally the non-relative relocations.
+    if (!OtherRelocs.empty()) {
+      encodeSLEB128(OtherRelocs.size(), OS);
+      encodeSLEB128(0, OS);
+      for (Elf_Rel &R : OtherRelocs) {
+        encodeSLEB128(R.r_offset - Offset, OS);
+        Offset = R.r_offset;
+        encodeSLEB128(R.r_info, OS);
+      }
+    }
+  }
+
+  return RelocData.size() != OldSize;
+}
+
 SymbolTableBaseSection::SymbolTableBaseSection(StringTableSection &StrTabSec)
     : SyntheticSection(StrTabSec.isDynamic() ? (uint64_t)SHF_ALLOC : 0,
                        StrTabSec.isDynamic() ? SHT_DYNSYM : SHT_SYMTAB,
@@ -2485,6 +2630,11 @@
 template class elf::RelocationSection<ELF64LE>;
 template class elf::RelocationSection<ELF64BE>;
 
+template class elf::AndroidRelocationSection<ELF32LE>;
+template class elf::AndroidRelocationSection<ELF32BE>;
+template class elf::AndroidRelocationSection<ELF64LE>;
+template class elf::AndroidRelocationSection<ELF64BE>;
+
 template class elf::SymbolTableSection<ELF32LE>;
 template class elf::SymbolTableSection<ELF32BE>;
 template class elf::SymbolTableSection<ELF64LE>;
Index: lld/ELF/Writer.cpp
===================================================================
--- lld/ELF/Writer.cpp
+++ lld/ELF/Writer.cpp
@@ -258,8 +258,12 @@
 
   InX::DynStrTab = make<StringTableSection>(".dynstr", true);
   InX::Dynamic = make<DynamicSection<ELFT>>();
-  In<ELFT>::RelaDyn = make<RelocationSection<ELFT>>(
-      Config->IsRela ? ".rela.dyn" : ".rel.dyn", Config->ZCombreloc);
+  if (Config->AndroidPackRelocs)
+    In<ELFT>::RelaDyn = make<AndroidRelocationSection<ELFT>>(
+        Config->IsRela ? ".rela.dyn" : ".rel.dyn");
+  else
+    In<ELFT>::RelaDyn = make<RelocationSection<ELFT>>(
+        Config->IsRela ? ".rela.dyn" : ".rel.dyn", Config->ZCombreloc);
   InX::ShStrTab = make<StringTableSection>(".shstrtab", false);
 
   Out::ElfHeader = make<OutputSection>("", 0, SHF_ALLOC);
@@ -362,7 +366,9 @@
   // The RelaIplt immediately follows .rel.plt (.rel.dyn for ARM) to ensure
   // that the IRelative relocations are processed last by the dynamic loader
   In<ELFT>::RelaIplt = make<RelocationSection<ELFT>>(
-      (Config->EMachine == EM_ARM) ? ".rel.dyn" : In<ELFT>::RelaPlt->Name,
+      (Config->EMachine == EM_ARM && !Config->AndroidPackRelocs)
+          ? ".rel.dyn"
+          : In<ELFT>::RelaPlt->Name,
       false /*Sort*/);
   Add(In<ELFT>::RelaIplt);
 
@@ -1362,14 +1368,18 @@
   // Some architectures use small displacements for jump instructions.
   // It is linker's responsibility to create thunks containing long
   // jump instructions if jump targets are too far. Create thunks.
-  if (Target->NeedsThunks) {
+  if (Target->NeedsThunks || Config->AndroidPackRelocs) {
     ThunkCreator TC;
-    Script->assignAddresses();
-    while (TC.createThunks(OutputSections)) {
-      applySynthetic({InX::MipsGot},
-                     [](SyntheticSection *SS) { SS->updateAllocSize(); });
+    bool Changed;
+    do {
       Script->assignAddresses();
-    }
+      Changed = false;
+      if (Target->NeedsThunks)
+        Changed |= TC.createThunks(OutputSections);
+      if (InX::MipsGot)
+        InX::MipsGot->updateAllocSize();
+      Changed |= In<ELFT>::RelaDyn->updateAllocSize();
+    } while (Changed);
   }
 
   // Fill other section headers. The dynamic table is finalized
Index: llvm/include/llvm/BinaryFormat/ELF.h
===================================================================
--- llvm/include/llvm/BinaryFormat/ELF.h
+++ llvm/include/llvm/BinaryFormat/ELF.h
@@ -730,6 +730,8 @@
   SHT_GROUP = 17,                  // Section group.
   SHT_SYMTAB_SHNDX = 18,           // Indices for SHN_XINDEX entries.
   SHT_LOOS = 0x60000000,           // Lowest operating system-specific type.
+  SHT_ANDROID_REL = 0x60000001,
+  SHT_ANDROID_RELA = 0x60000002,
   SHT_LLVM_ODRTAB = 0x6fff4c00,    // LLVM ODR table.
   SHT_GNU_ATTRIBUTES = 0x6ffffff5, // Object attributes.
   SHT_GNU_HASH = 0x6ffffff6,       // GNU-style hash table.
@@ -1166,6 +1168,11 @@
   DT_LOPROC = 0x70000000, // Start of processor specific tags.
   DT_HIPROC = 0x7FFFFFFF, // End of processor specific tags.
 
+  DT_ANDROID_REL = 0x6000000F,
+  DT_ANDROID_RELSZ = 0x60000010,
+  DT_ANDROID_RELA = 0x60000011,
+  DT_ANDROID_RELASZ = 0x60000012,
+
   DT_GNU_HASH = 0x6FFFFEF5, // Reference to the GNU hash table.
   DT_TLSDESC_PLT =
       0x6FFFFEF6, // Location of PLT entry for TLS descriptor resolver calls.