[binutils-gdb] bfd: optimize bfd_elf_hash

[binutils-gdb] bfd: optimize bfd_elf_hash

[Nathan Sidwell]

https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;h=0481d5dce311303025c6e55cd584db1870ad2492

commit 0481d5dce311303025c6e55cd584db1870ad2492
Author: Nathan Sidwell <nathan@acm.org>
Date:   Tue Apr 11 17:47:31 2023 -0400

    bfd: optimize bfd_elf_hash
    
    The bfd_elf_hash loop is taken straight from the sysV document, but it
    is poorly optimized. This refactoring removes about 5 x86 insns from
    the 15 insn loop.
    
    1) The if (..) is meaningless -- we're xoring with that value, and of
    course xor 0 is a nop. On x86 (at least) we actually compute the xor'd
    value and then cmov.  Removing the if test removes the cmov.
    
    2) The 'h ^ g' to clear the top 4 bits is not needed, as those 4 bits
    will be shifted out in the next iteration.  All we need to do is sink
    a mask of those 4 bits out of the loop.
    
    3) anding with 0xf0 after shifting by 24 bits can allow betterin
    encoding on RISC ISAs than masking with '0xf0 << 24' before shifting.
    RISC ISAs often require materializing larger constants.
    
            bfd/
            * elf.c (bfd_elf_hash): Refactor to optimize loop.
            (bfd_elf_gnu_hash): Refactor to use 32-bit type.

Diff:
---
 bfd/elf.c | 31 +++++++++++--------------------
 1 file changed, 11 insertions(+), 20 deletions(-)

diff --git a/bfd/elf.c b/bfd/elf.c
index 185028cbd97..0e2ae6dae1c 100644
--- a/bfd/elf.c
+++ b/bfd/elf.c
@@ -196,23 +196,15 @@ _bfd_elf_swap_versym_out (bfd *abfd,
 unsigned long
 bfd_elf_hash (const char *namearg)
 {
-  const unsigned char *name = (const unsigned char *) namearg;
-  unsigned long h = 0;
-  unsigned long g;
-  int ch;
+  uint32_t h = 0;
 
-  while ((ch = *name++) != '\0')
+  for (const unsigned char *name = (const unsigned char *) namearg;
+       *name; name++)
     {
-      h = (h << 4) + ch;
-      if ((g = (h & 0xf0000000)) != 0)
-	{
-	  h ^= g >> 24;
-	  /* The ELF ABI says `h &= ~g', but this is equivalent in
-	     this case and on some machines one insn instead of two.  */
-	  h ^= g;
-	}
+      h = (h << 4) + *name;
+      h ^= (h >> 24) & 0xf0;
     }
-  return h & 0xffffffff;
+  return h & 0x0fffffff;
 }
 
 /* DT_GNU_HASH hash function.  Do not change this function; you will
@@ -221,13 +213,12 @@ bfd_elf_hash (const char *namearg)
 unsigned long
 bfd_elf_gnu_hash (const char *namearg)
 {
-  const unsigned char *name = (const unsigned char *) namearg;
-  unsigned long h = 5381;
-  unsigned char ch;
+  uint32_t h = 5381;
 
-  while ((ch = *name++) != '\0')
-    h = (h << 5) + h + ch;
-  return h & 0xffffffff;
+  for (const unsigned char *name = (const unsigned char *) namearg;
+       *name; name++)
+    h = (h << 5) + h + *name;
+  return h;
 }
 
 /* Create a tdata field OBJECT_SIZE bytes in length, zeroed out and with