From 703c872a4a64160cee299fae0144c9bf08949cc8 Mon Sep 17 00:00:00 2001
From: Rui Ueyama <ruiu@google.com>
Date: Mon, 9 Jul 2018 22:29:57 +0000
Subject: [PATCH] Simplify RelrSection<ELFT>::updateAllocSize.

This patch also speeds it up by making some constants compile-time
constants. Other than that, NFC.

Differential Revision: https://reviews.llvm.org/D49101

llvm-svn: 336614
---
 lld/ELF/SyntheticSections.cpp | 74 ++++++++++++++++++++-----------------------
 1 file changed, 34 insertions(+), 40 deletions(-)

diff --git a/lld/ELF/SyntheticSections.cpp b/lld/ELF/SyntheticSections.cpp
index ca8ef1d..f15102f 100644
--- a/lld/ELF/SyntheticSections.cpp
+++ b/lld/ELF/SyntheticSections.cpp
@@ -1745,53 +1745,47 @@ template <class ELFT> bool RelrSection<ELFT>::updateAllocSize() {
   size_t OldSize = RelrRelocs.size();
   RelrRelocs.clear();
 
+  // Same as Config->Wordsize but faster because this is a compile-time
+  // constant.
+  const size_t Wordsize = sizeof(typename ELFT::uint);
+
   // Number of bits to use for the relocation offsets bitmap.
-  // These many relative relocations can be encoded in a single entry.
-  const size_t NBits = 8 * Config->Wordsize - 1;
+  // Must be either 63 or 31.
+  const size_t NBits = Wordsize * 8 - 1;
 
   // Get offsets for all relative relocations and sort them.
   std::vector<uint64_t> Offsets;
-  for (const RelativeReloc &Rel : Relocs) {
+  for (const RelativeReloc &Rel : Relocs)
     Offsets.push_back(Rel.getOffset());
-  }
-  std::sort(Offsets.begin(), Offsets.end());
-
-  uint64_t Base = 0;
-  typename std::vector<uint64_t>::iterator Curr = Offsets.begin();
-  while (Curr != Offsets.end()) {
-    uint64_t Current = *Curr;
-    assert(Current % 2 == 0);
-
-    uint64_t Bits = 0;
-    typename std::vector<uint64_t>::iterator Next = Curr;
-    if (Base > 0 && Base <= Current) {
-      while (Next != Offsets.end()) {
-        uint64_t Delta = *Next - Base;
-        // If Next is too far out, it cannot be folded into Curr.
-        if (Delta >= NBits * Config->Wordsize)
-          break;
-        // If Next is not a multiple of wordsize away, it cannot
-        // be folded into Curr.
-        if (Delta % Config->Wordsize != 0)
-          break;
-        // Next can be folded into Curr, add it to the bitmap.
-        Bits |= 1ULL << (Delta / Config->Wordsize);
-        ++Next;
-      }
+  llvm::sort(Offsets.begin(), Offsets.end());
+
+  // For each leading relocation, find following ones that can be folded
+  // as a bitmap and fold them.
+  for (size_t I = 0, E = Offsets.size(); I < E;) {
+    // Add a leading relocation.
+    RelrRelocs.push_back(Elf_Relr(Offsets[I]));
+    ++I;
+
+    // Find foldable relocations to create a bitmap.
+    uint64_t Bitmap = 0;
+    for (size_t J = I; J < E; ++J) {
+      uint64_t Delta = Offsets[J] - Offsets[I];
+
+      // If it is too far, it cannot be folded.
+      if (Delta >= NBits * Wordsize)
+        break;
+
+      // If it is not a multiple of wordsize away, it cannot be folded.
+      if (Delta % Wordsize)
+        break;
+
+      // Fold it.
+      Bitmap |= 1ULL << (Delta / Wordsize);
     }
 
-    if (Bits == 0) {
-      RelrRelocs.push_back(Elf_Relr(Current));
-      // This is not a continuation entry, only one offset was
-      // consumed. Set base offset for subsequent bitmap entries.
-      Base = Current + Config->Wordsize;
-      ++Curr;
-    } else {
-      RelrRelocs.push_back(Elf_Relr((Bits << 1) | 1));
-      // This is a continuation entry encoding multiple offsets
-      // in a bitmap. Advance base offset by NBits words.
-      Base += NBits * Config->Wordsize;
-      Curr = Next;
+    if (Bitmap) {
+      RelrRelocs.push_back(Elf_Relr((Bitmap << 1) | 1));
+      I += NBits;
     }
   }
 
-- 
2.7.4