diff --git a/bolt/include/bolt/Core/BinarySection.h b/bolt/include/bolt/Core/BinarySection.h
--- a/bolt/include/bolt/Core/BinarySection.h
+++ b/bolt/include/bolt/Core/BinarySection.h
@@ -275,6 +275,7 @@
   bool isTBSS() const { return isBSS() && isTLS(); }
   bool isVirtual() const { return ELFType == ELF::SHT_NOBITS; }
   bool isRela() const { return ELFType == ELF::SHT_RELA; }
+  bool isRelr() const { return ELFType == ELF::SHT_RELR; }
   bool isWritable() const { return (ELFFlags & ELF::SHF_WRITE); }
   bool isAllocatable() const {
     if (isELF()) {
diff --git a/bolt/include/bolt/Core/Relocation.h b/bolt/include/bolt/Core/Relocation.h
--- a/bolt/include/bolt/Core/Relocation.h
+++ b/bolt/include/bolt/Core/Relocation.h
@@ -109,6 +109,9 @@
   /// Return code for a ABS 8-byte relocation
   static uint64_t getAbs64();
 
+  /// Return code for a RELATIVE relocation
+  static uint64_t getRelative();
+
   /// Return true if this relocation is PC-relative. Return false otherwise.
   bool isPCRelative() const { return isPCRelative(Type); }
 
diff --git a/bolt/include/bolt/Rewrite/RewriteInstance.h b/bolt/include/bolt/Rewrite/RewriteInstance.h
--- a/bolt/include/bolt/Rewrite/RewriteInstance.h
+++ b/bolt/include/bolt/Rewrite/RewriteInstance.h
@@ -138,6 +138,9 @@
   /// Read relocations from a given section.
   void readDynamicRelocations(const object::SectionRef &Section, bool IsJmpRel);
 
+  /// Read relocations from a given RELR section.
+  void readDynamicRelrRelocations(BinarySection &Section);
+
   /// Print relocation information.
   void printRelocationInfo(const RelocationRef &Rel, StringRef SymbolName,
                            uint64_t SymbolAddress, uint64_t Addend,
@@ -312,6 +315,9 @@
   /// Patch allocatable relocation sections.
   ELF_FUNCTION(void, patchELFAllocatableRelaSections);
 
+  /// Patch allocatable relr section.
+  ELF_FUNCTION(void, patchELFAllocatableRelrSection);
+
   /// Finalize memory image of section header string table.
   ELF_FUNCTION(void, finalizeSectionStringTable);
 
@@ -486,6 +492,11 @@
   uint64_t DynamicRelocationsSize{0};
   uint64_t DynamicRelativeRelocationsCount{0};
 
+  // Location and size of .relr.dyn relocations.
+  std::optional<uint64_t> DynamicRelrAddress;
+  uint64_t DynamicRelrSize{0};
+  uint64_t DynamicRelrEntrySize{0};
+
   /// PLT relocations are special kind of dynamic relocations stored separately.
   std::optional<uint64_t> PLTRelocationsAddress;
   uint64_t PLTRelocationsSize{0};
diff --git a/bolt/lib/Core/Relocation.cpp b/bolt/lib/Core/Relocation.cpp
--- a/bolt/lib/Core/Relocation.cpp
+++ b/bolt/lib/Core/Relocation.cpp
@@ -642,6 +642,12 @@
   return ELF::R_X86_64_64;
 }
 
+uint64_t Relocation::getRelative() {
+  if (Arch == Triple::aarch64)
+    return ELF::R_AARCH64_RELATIVE;
+  return ELF::R_X86_64_RELATIVE;
+}
+
 size_t Relocation::emit(MCStreamer *Streamer) const {
   const size_t Size = getSizeForType(Type);
   MCContext &Ctx = Streamer->getContext();
diff --git a/bolt/lib/Rewrite/RewriteInstance.cpp b/bolt/lib/Rewrite/RewriteInstance.cpp
--- a/bolt/lib/Rewrite/RewriteInstance.cpp
+++ b/bolt/lib/Rewrite/RewriteInstance.cpp
@@ -2074,6 +2074,19 @@
 }
 
 void RewriteInstance::processDynamicRelocations() {
+  // Read .relr.dyn section containing compressed R_*_RELATIVE relocations.
+  if (DynamicRelrSize > 0) {
+    ErrorOr<BinarySection &> DynamicRelrSectionOrErr =
+        BC->getSectionForAddress(*DynamicRelrAddress);
+    if (!DynamicRelrSectionOrErr)
+      report_error("unable to find section corresponding to DT_RELR",
+                   DynamicRelrSectionOrErr.getError());
+    if (DynamicRelrSectionOrErr->getSize() != DynamicRelrSize)
+      report_error("section size mismatch for DT_RELRSZ",
+                   errc::executable_format_error);
+    readDynamicRelrRelocations(*DynamicRelrSectionOrErr);
+  }
+
   // Read relocations for PLT - DT_JMPREL.
   if (PLTRelocationsSize > 0) {
     ErrorOr<BinarySection &> PLTRelSectionOrErr =
@@ -2372,6 +2385,60 @@
   }
 }
 
+void RewriteInstance::readDynamicRelrRelocations(BinarySection &Section) {
+  assert(Section.isAllocatable() && "allocatable expected");
+
+  LLVM_DEBUG({
+    StringRef SectionName = Section.getName();
+    dbgs() << "BOLT-DEBUG: reading relocations in section " << SectionName
+           << ":\n";
+  });
+
+  const uint64_t RType = Relocation::getRelative();
+  const uint8_t PSize = BC->AsmInfo->getCodePointerSize();
+  const uint64_t MaxDelta = ((CHAR_BIT * DynamicRelrEntrySize) - 1) * PSize;
+
+  auto ExtractAddendValue = [&](uint64_t Address) -> uint64_t {
+    ErrorOr<BinarySection &> Section = BC->getSectionForAddress(Address);
+    assert(Section && "cannot get section for data address from RELR");
+    DataExtractor DE = DataExtractor(Section->getContents(),
+                                     BC->AsmInfo->isLittleEndian(), PSize);
+    uint64_t Offset = Address - Section->getAddress();
+    return DE.getUnsigned(&Offset, PSize);
+  };
+
+  auto AddRelocation = [&](uint64_t Address) {
+    uint64_t Addend = ExtractAddendValue(Address);
+    LLVM_DEBUG(dbgs() << "BOLT-DEBUG: R_*_RELATIVE relocation at 0x"
+                      << Twine::utohexstr(Address) << " to 0x"
+                      << Twine::utohexstr(Addend) << '\n';);
+    BC->addDynamicRelocation(Address, nullptr, RType, Addend);
+  };
+
+  DataExtractor DE = DataExtractor(Section.getContents(),
+                                   BC->AsmInfo->isLittleEndian(), PSize);
+  uint64_t Offset = 0, Address = 0;
+  uint64_t RelrCount = DynamicRelrSize / DynamicRelrEntrySize;
+  while (RelrCount--) {
+    assert(DE.isValidOffset(Offset));
+    uint64_t Entry = DE.getUnsigned(&Offset, DynamicRelrEntrySize);
+    if ((Entry & 1) == 0) {
+      AddRelocation(Entry);
+      Address = Entry + PSize;
+    } else {
+      const uint64_t StartAddress = Address;
+      while (Entry >>= 1) {
+        if (Entry & 1)
+          AddRelocation(Address);
+
+        Address += PSize;
+      }
+
+      Address = StartAddress + MaxDelta;
+    }
+  }
+}
+
 void RewriteInstance::printRelocationInfo(const RelocationRef &Rel,
                                           StringRef SymbolName,
                                           uint64_t SymbolAddress,
@@ -5203,6 +5270,101 @@
                                   ELF::SHT_STRTAB);
 }
 
+template <typename ELFT>
+void RewriteInstance::patchELFAllocatableRelrSection(
+    ELFObjectFile<ELFT> *File) {
+  if (!DynamicRelrAddress)
+    return;
+
+  raw_fd_ostream &OS = Out->os();
+  const uint8_t PSize = BC->AsmInfo->getCodePointerSize();
+  const uint64_t MaxDelta = ((CHAR_BIT * DynamicRelrEntrySize) - 1) * PSize;
+
+  auto FixAddend = [&](const BinarySection &Section, const Relocation &Rel) {
+    // Fix relocation symbol value in place if no static relocation found
+    // on the same address
+    if (Section.getRelocationAt(Rel.Offset))
+      return;
+
+    // No fixup needed if symbol address was not changed
+    const uint64_t Addend = getNewFunctionOrDataAddress(Rel.Addend);
+    if (!Addend)
+      return;
+
+    uint64_t FileOffset = Section.getOutputFileOffset();
+    if (!FileOffset)
+      FileOffset = Section.getInputFileOffset();
+
+    FileOffset += Rel.Offset;
+    OS.pwrite(reinterpret_cast<const char *>(&Addend), PSize, FileOffset);
+  };
+
+  // Fill new relative relocation offsets set
+  std::set<uint64_t> RelOffsets;
+  for (const BinarySection &Section : BC->allocatableSections()) {
+    const uint64_t SectionInputAddress = Section.getAddress();
+    uint64_t SectionAddress = Section.getOutputAddress();
+    if (!SectionAddress)
+      SectionAddress = SectionInputAddress;
+
+    for (const Relocation &Rel : Section.dynamicRelocations()) {
+      if (!Rel.isRelative())
+        continue;
+
+      uint64_t RelOffset =
+          getNewFunctionOrDataAddress(SectionInputAddress + Rel.Offset);
+
+      RelOffset = RelOffset == 0 ? SectionAddress + Rel.Offset : RelOffset;
+      assert((RelOffset & 1) == 0 && "Wrong relocation offset");
+      RelOffsets.emplace(RelOffset);
+      FixAddend(Section, Rel);
+    }
+  }
+
+  ErrorOr<BinarySection &> Section =
+      BC->getSectionForAddress(*DynamicRelrAddress);
+  assert(Section && "cannot get .relr.dyn section");
+  assert(Section->isRelr() && "Expected section to be SHT_RELR type");
+  uint64_t RelrDynOffset = Section->getInputFileOffset();
+  const uint64_t RelrDynEndOffset = RelrDynOffset + Section->getSize();
+
+  auto WriteRelr = [&](uint64_t Value) {
+    if (RelrDynOffset + DynamicRelrEntrySize > RelrDynEndOffset) {
+      errs() << "BOLT-ERROR: Offset overflow for relr.dyn section\n";
+      exit(1);
+    }
+
+    OS.pwrite(reinterpret_cast<const char *>(&Value), DynamicRelrEntrySize,
+              RelrDynOffset);
+    RelrDynOffset += DynamicRelrEntrySize;
+  };
+
+  for (auto RelIt = RelOffsets.begin(); RelIt != RelOffsets.end();) {
+    WriteRelr(*RelIt);
+    uint64_t Base = *RelIt++ + PSize;
+    while (1) {
+      uint64_t Bitmap = 0;
+      for (; RelIt != RelOffsets.end(); ++RelIt) {
+        const uint64_t Delta = *RelIt - Base;
+        if (Delta >= MaxDelta || Delta % PSize)
+          break;
+
+        Bitmap |= (1ULL << (Delta / PSize));
+      }
+
+      if (!Bitmap)
+        break;
+
+      WriteRelr((Bitmap << 1) | 1);
+      Base += MaxDelta;
+    }
+  }
+
+  // Fill the rest of the section with empty bitmap value
+  while (RelrDynOffset != RelrDynEndOffset)
+    WriteRelr(1);
+}
+
 template <typename ELFT>
 void
 RewriteInstance::patchELFAllocatableRelaSections(ELFObjectFile<ELFT> *File) {
@@ -5294,8 +5456,11 @@
     }
   };
 
-  // The dynamic linker expects R_*_RELATIVE relocations to be emitted first
-  writeRelocations(/* PatchRelative */ true);
+  // Place R_*_RELATIVE relocations in RELA section if RELR is not presented.
+  // The dynamic linker expects all R_*_RELATIVE relocations in RELA
+  // to be emitted first.
+  if (!DynamicRelrAddress)
+    writeRelocations(/* PatchRelative */ true);
   writeRelocations(/* PatchRelative */ false);
 
   auto fillNone = [&](uint64_t &Offset, uint64_t EndOffset) {
@@ -5501,6 +5666,15 @@
     case ELF::DT_RELACOUNT:
       DynamicRelativeRelocationsCount = Dyn.getVal();
       break;
+    case ELF::DT_RELR:
+      DynamicRelrAddress = Dyn.getPtr();
+      break;
+    case ELF::DT_RELRSZ:
+      DynamicRelrSize = Dyn.getVal();
+      break;
+    case ELF::DT_RELRENT:
+      DynamicRelrEntrySize = Dyn.getVal();
+      break;
     }
   }
 
@@ -5513,6 +5687,20 @@
     PLTRelocationsAddress.reset();
     PLTRelocationsSize = 0;
   }
+
+  if (!DynamicRelrAddress || !DynamicRelrSize) {
+    DynamicRelrAddress.reset();
+    DynamicRelrSize = 0;
+  } else if (!DynamicRelrEntrySize) {
+    errs() << "BOLT-ERROR: expected DT_RELRENT to be presented "
+           << "in DYNAMIC section\n";
+    exit(1);
+  } else if (DynamicRelrSize % DynamicRelrEntrySize) {
+    errs() << "BOLT-ERROR: expected RELR table size to be divisible "
+           << "by RELR entry size\n";
+    exit(1);
+  }
+
   return Error::success();
 }
 
@@ -5724,6 +5912,7 @@
 
   if (BC->HasRelocations) {
     patchELFAllocatableRelaSections();
+    patchELFAllocatableRelrSection();
     patchELFGOT();
   }
 
diff --git a/bolt/test/AArch64/constant_island_pie_update.s b/bolt/test/AArch64/constant_island_pie_update.s
--- a/bolt/test/AArch64/constant_island_pie_update.s
+++ b/bolt/test/AArch64/constant_island_pie_update.s
@@ -1,29 +1,51 @@
-// This test checks that the constant island value is updated if it
-// has dynamic relocation.
+// This test checks that the constant island offset and value is updated if
+// it has dynamic relocation. The tests checks both .rela.dyn and relr.dyn
+// dynamic relocations.
 // Also check that we don't duplicate CI if it has dynamic relocations.
 
 # RUN: llvm-mc -filetype=obj -triple aarch64-unknown-unknown %s -o %t.o
+// .rela.dyn
 # RUN: %clang %cflags -fPIC -pie %t.o -o %t.rela.exe -nostdlib \
 # RUN:   -Wl,-q -Wl,-z,notext
 # RUN: llvm-bolt %t.rela.exe -o %t.rela.bolt --use-old-text=0 --lite=0
 # RUN: llvm-objdump -j .text -d %t.rela.bolt | FileCheck %s
 # RUN: llvm-readelf -rsW %t.rela.bolt | FileCheck --check-prefix=ELFCHECK %s
+// .relr.dyn
+# RUN: %clang %cflags -fPIC -pie %t.o -o %t.relr.exe -nostdlib \
+# RUN:   -Wl,-q -Wl,-z,notext -Wl,--pack-dyn-relocs=relr
+# RUN: llvm-bolt %t.relr.exe -o %t.relr.bolt --use-old-text=0 --lite=0
+# RUN: llvm-objdump -j .text -d %t.relr.bolt | FileCheck %s
+# RUN: llvm-readelf -rsW %t.relr.bolt | FileCheck --check-prefix=ELFCHECK %s
+# RUN: llvm-readelf -SW %t.relr.bolt | FileCheck --check-prefix=RELRSZCHECK %s
 
 // Check that the CI value was updated
 # CHECK: [[#%x,ADDR:]] <exitLocal>:
 # CHECK: {{.*}} <$d>:
 # CHECK-NEXT: {{.*}} .word 0x{{[0]+}}[[#ADDR]]
 # CHECK-NEXT: {{.*}} .word 0x00000000
+# CHECK-NEXT: {{.*}} .word 0x{{[0]+}}[[#ADDR]]
+# CHECK-NEXT: {{.*}} .word 0x00000000
+# CHECK-NEXT: {{.*}} .word 0x00000000
+# CHECK-NEXT: {{.*}} .word 0x00000000
+# CHECK-NEXT: {{.*}} .word 0x{{[0]+}}[[#ADDR]]
+# CHECK-NEXT: {{.*}} .word 0x00000000
+
 
 // Check that we've relaxed adr to adrp + add to refer external CI
 # CHECK: <addressDynCi>:
 # CHECK-NEXT: adrp
 # CHECK-NEXT: add
 
-// Check that relocation offset was updated
+// Check that relocation offsets were updated
 # ELFCHECK: [[#%x,OFF:]] [[#%x,INFO_DYN:]] R_AARCH64_RELATIVE
+# ELFCHECK-NEXT: [[#OFF + 8]] {{0*}}[[#INFO_DYN]] R_AARCH64_RELATIVE
+# ELFCHECK-NEXT: [[#OFF + 24]] {{0*}}[[#INFO_DYN]] R_AARCH64_RELATIVE
 # ELFCHECK: {{.*}}[[#OFF]] {{.*}} $d
 
+// Check that .relr.dyn size is 2 bytes to ensure that last 2 relocations were
+// encoded as a bitmap so the total section size for 3 relocations is 2 bytes.
+# RELRSZCHECK: .relr.dyn RELR [[#%x,ADDR:]] [[#%x,OFF:]] {{0*}}10
+
   .text
   .align 4
   .local exitLocal
@@ -47,6 +69,9 @@
   bl exitLocal
   nop
 .Lci:
+  .xword exitLocal
+  .xword exitLocal
+  .xword 0
   .xword exitLocal
   .size _start, .-_start