Patchwork gnulib: import count-one-bits module and use it

login
register
mail settings
Submitter Simon Marchi
Date Feb. 11, 2020, 5:09 p.m.
Message ID <20200211170902.4330-1-simon.marchi@efficios.com>
Download mbox | patch
Permalink /patch/37976/
State New
Headers show

Comments

Simon Marchi - Feb. 11, 2020, 5:09 p.m.
For a fix I intend to submit, I would need a function that counts the
number of set bits in a word.  There is  __builtin_popcount that is
supported by gcc and clang, but there is also a gnulib module that wraps
that and provides a fallback for other compilers, so I think it would be
good to use it.

I also noticed that there is a bitcount function in arch/arm.c, so I
thought that as a first step I would replace that one with the gnulib
count-one-bits module.  This is what this patch does.

The gnulib module provides multiple functions, with various parameter
length (unsigned int, unsigned long int, unsigned long long int), I
chose the one that made sense for each call site based on the argument
type.

gnulib/ChangeLog:

	* update-gnulib.sh (IMPORTED_GNULIB_MODULES): Import
	count-one-bits module.
	* configure: Re-generate.
	* aclocal.m4: Re-generate.
	* Makefile.in: Re-generate.
	* import/count-one-bits.c: New file.
	* import/count-one-bits.h: New file.
	* import/Makefile.am: Re-generate.
	* import/Makefile.in: Re-generate.
	* import/m4/gnulib-cache.m4: Re-generate.
	* import/m4/gnulib-comp.m4: Re-generate.
	* import/m4/count-one-bits.m4: New file.

gdb/ChangeLog:

	* arm-tdep.c: Include count-one-bits.h.
	(cleanup_block_store_pc): Use count_one_bits.
	(cleanup_block_load_pc): Use count_one_bits.
	(arm_copy_block_xfer): Use count_one_bits.
	(thumb2_copy_block_xfer): Use count_one_bits.
	(thumb_copy_pop_pc_16bit): Use count_one_bits.
	* arch/arm-get-next-pcs.c: Include count-one-bits.h.
	(thumb_get_next_pcs_raw): Use count_one_bits.
	(arm_get_next_pcs_raw): Use count_one_bits_l.
	* arch/arm.c (bitcount): Remove.
	* arch/arm.h (bitcount): Remove.
---
 gdb/arch/arm-get-next-pcs.c        |   9 +-
 gdb/arch/arm.c                     |  11 ---
 gdb/arch/arm.h                     |   3 -
 gdb/arm-tdep.c                     |  12 +--
 gnulib/Makefile.in                 |   5 +-
 gnulib/aclocal.m4                  |   1 +
 gnulib/configure                   | 118 +++++++++++++------------
 gnulib/import/Makefile.am          |   9 ++
 gnulib/import/Makefile.in          |  50 ++++++-----
 gnulib/import/count-one-bits.c     |   7 ++
 gnulib/import/count-one-bits.h     | 136 +++++++++++++++++++++++++++++
 gnulib/import/m4/count-one-bits.m4 |  12 +++
 gnulib/import/m4/gnulib-cache.m4   |   2 +
 gnulib/import/m4/gnulib-comp.m4    |   5 ++
 gnulib/update-gnulib.sh            |   1 +
 15 files changed, 276 insertions(+), 105 deletions(-)
 create mode 100644 gnulib/import/count-one-bits.c
 create mode 100644 gnulib/import/count-one-bits.h
 create mode 100644 gnulib/import/m4/count-one-bits.m4
Luis Machado - Feb. 14, 2020, 10:35 a.m.
Hi,

On 2/11/20 2:09 PM, Simon Marchi wrote:
> For a fix I intend to submit, I would need a function that counts the
> number of set bits in a word.  There is  __builtin_popcount that is
> supported by gcc and clang, but there is also a gnulib module that wraps
> that and provides a fallback for other compilers, so I think it would be
> good to use it.
> 
> I also noticed that there is a bitcount function in arch/arm.c, so I
> thought that as a first step I would replace that one with the gnulib
> count-one-bits module.  This is what this patch does.
> 
> The gnulib module provides multiple functions, with various parameter
> length (unsigned int, unsigned long int, unsigned long long int), I
> chose the one that made sense for each call site based on the argument
> type.

Thanks. One small nit below.

> 
> gnulib/ChangeLog:
> 
> 	* update-gnulib.sh (IMPORTED_GNULIB_MODULES): Import
> 	count-one-bits module.
> 	* configure: Re-generate.
> 	* aclocal.m4: Re-generate.
> 	* Makefile.in: Re-generate.
> 	* import/count-one-bits.c: New file.
> 	* import/count-one-bits.h: New file.
> 	* import/Makefile.am: Re-generate.
> 	* import/Makefile.in: Re-generate.
> 	* import/m4/gnulib-cache.m4: Re-generate.
> 	* import/m4/gnulib-comp.m4: Re-generate.
> 	* import/m4/count-one-bits.m4: New file.
> 
> gdb/ChangeLog:
> 
> 	* arm-tdep.c: Include count-one-bits.h.
> 	(cleanup_block_store_pc): Use count_one_bits.
> 	(cleanup_block_load_pc): Use count_one_bits.
> 	(arm_copy_block_xfer): Use count_one_bits.
> 	(thumb2_copy_block_xfer): Use count_one_bits.
> 	(thumb_copy_pop_pc_16bit): Use count_one_bits.
> 	* arch/arm-get-next-pcs.c: Include count-one-bits.h.
> 	(thumb_get_next_pcs_raw): Use count_one_bits.
> 	(arm_get_next_pcs_raw): Use count_one_bits_l.
> 	* arch/arm.c (bitcount): Remove.
> 	* arch/arm.h (bitcount): Remove.
> ---
>   gdb/arch/arm-get-next-pcs.c        |   9 +-
>   gdb/arch/arm.c                     |  11 ---
>   gdb/arch/arm.h                     |   3 -
>   gdb/arm-tdep.c                     |  12 +--
>   gnulib/Makefile.in                 |   5 +-
>   gnulib/aclocal.m4                  |   1 +
>   gnulib/configure                   | 118 +++++++++++++------------
>   gnulib/import/Makefile.am          |   9 ++
>   gnulib/import/Makefile.in          |  50 ++++++-----
>   gnulib/import/count-one-bits.c     |   7 ++
>   gnulib/import/count-one-bits.h     | 136 +++++++++++++++++++++++++++++
>   gnulib/import/m4/count-one-bits.m4 |  12 +++
>   gnulib/import/m4/gnulib-cache.m4   |   2 +
>   gnulib/import/m4/gnulib-comp.m4    |   5 ++
>   gnulib/update-gnulib.sh            |   1 +
>   15 files changed, 276 insertions(+), 105 deletions(-)
>   create mode 100644 gnulib/import/count-one-bits.c
>   create mode 100644 gnulib/import/count-one-bits.h
>   create mode 100644 gnulib/import/m4/count-one-bits.m4
> 
> diff --git a/gdb/arch/arm-get-next-pcs.c b/gdb/arch/arm-get-next-pcs.c
> index fc541332aabd..0c49a77245bf 100644
> --- a/gdb/arch/arm-get-next-pcs.c
> +++ b/gdb/arch/arm-get-next-pcs.c
> @@ -22,6 +22,7 @@
>   #include "gdbsupport/common-regcache.h"
>   #include "arm.h"
>   #include "arm-get-next-pcs.h"
> +#include "count-one-bits.h"
>   
>   /* See arm-get-next-pcs.h.  */
>   
> @@ -408,8 +409,8 @@ thumb_get_next_pcs_raw (struct arm_get_next_pcs *self)
>   
>         /* Fetch the saved PC from the stack.  It's stored above
>            all of the other registers.  */
> -      unsigned long offset = bitcount (bits (inst1, 0, 7))
> -			     * ARM_INT_REGISTER_SIZE;
> +      unsigned long offset
> +	= count_one_bits (bits (inst1, 0, 7)) * ARM_INT_REGISTER_SIZE;
>         sp = regcache_raw_get_unsigned (regcache, ARM_SP_REGNUM);
>         nextpc = self->ops->read_mem_uint (sp + offset, 4, byte_order);
>       }
> @@ -496,7 +497,7 @@ thumb_get_next_pcs_raw (struct arm_get_next_pcs *self)
>   	      /* LDMIA or POP */
>   	      if (!bit (inst2, 15))
>   		load_pc = 0;
> -	      offset = bitcount (inst2) * 4 - 4;
> +	      offset = count_one_bits (inst2) * 4 - 4;
>   	    }
>   	  else if (!bit (inst1, 7) && bit (inst1, 8))
>   	    {
> @@ -864,7 +865,7 @@ arm_get_next_pcs_raw (struct arm_get_next_pcs *self)
>   		    {
>   		      /* up */
>   		      unsigned long reglist = bits (this_instr, 0, 14);
> -		      offset = bitcount (reglist) * 4;
> +		      offset = count_one_bits_l (reglist) * 4;
>   		      if (bit (this_instr, 24))		/* pre */
>   			offset += 4;
>   		    }
> diff --git a/gdb/arch/arm.c b/gdb/arch/arm.c
> index 60d9f85889db..faa2b4fbd4b2 100644
> --- a/gdb/arch/arm.c
> +++ b/gdb/arch/arm.c
> @@ -41,17 +41,6 @@ thumb_insn_size (unsigned short inst1)
>   
>   /* See arm.h.  */
>   
> -int
> -bitcount (unsigned long val)
> -{
> -  int nbits;
> -  for (nbits = 0; val != 0; nbits++)
> -    val &= val - 1;		/* Delete rightmost 1-bit in val.  */
> -  return nbits;
> -}
> -
> -/* See arm.h.  */
> -
>   int
>   condition_true (unsigned long cond, unsigned long status_reg)
>   {
> diff --git a/gdb/arch/arm.h b/gdb/arch/arm.h
> index 13f030af82ca..2bffb11a4a3f 100644
> --- a/gdb/arch/arm.h
> +++ b/gdb/arch/arm.h
> @@ -159,9 +159,6 @@ int thumb_insn_size (unsigned short inst1);
>   /* Returns true if the condition evaluates to true.  */
>   int condition_true (unsigned long cond, unsigned long status_reg);
>   
> -/* Return number of 1-bits in VAL.  */
> -int bitcount (unsigned long val);
> -
>   /* Return 1 if THIS_INSTR might change control flow, 0 otherwise.  */
>   int arm_instruction_changes_pc (uint32_t this_instr);
>   
> diff --git a/gdb/arm-tdep.c b/gdb/arm-tdep.c
> index d4fed8977e70..8e647e2e2a8e 100644
> --- a/gdb/arm-tdep.c
> +++ b/gdb/arm-tdep.c
> @@ -45,6 +45,7 @@
>   #include "target-descriptions.h"
>   #include "user-regs.h"
>   #include "observable.h"
> +#include "count-one-bits.h"
>   
>   #include "arch/arm.h"
>   #include "arch/arm-get-next-pcs.h"
> @@ -5798,7 +5799,8 @@ cleanup_block_store_pc (struct gdbarch *gdbarch, struct regcache *regs,
>   {
>     uint32_t status = displaced_read_reg (regs, dsc, ARM_PS_REGNUM);
>     int store_executed = condition_true (dsc->u.block.cond, status);
> -  CORE_ADDR pc_stored_at, transferred_regs = bitcount (dsc->u.block.regmask);
> +  CORE_ADDR pc_stored_at, transferred_regs
> +    = count_one_bits (dsc->u.block.regmask);
>     CORE_ADDR stm_insn_addr;
>     uint32_t pc_val;
>     long offset;
> @@ -5850,7 +5852,7 @@ cleanup_block_load_pc (struct gdbarch *gdbarch,
>     uint32_t status = displaced_read_reg (regs, dsc, ARM_PS_REGNUM);
>     int load_executed = condition_true (dsc->u.block.cond, status);
>     unsigned int mask = dsc->u.block.regmask, write_reg = ARM_PC_REGNUM;
> -  unsigned int regs_loaded = bitcount (mask);
> +  unsigned int regs_loaded = count_one_bits (mask);
>     unsigned int num_to_shuffle = regs_loaded, clobbered;
>   
>     /* The method employed here will fail if the register list is fully populated
> @@ -5982,7 +5984,7 @@ arm_copy_block_xfer (struct gdbarch *gdbarch, uint32_t insn,
>   	     contiguous chunk r0...rX before doing the transfer, then shuffling
>   	     registers into the correct places in the cleanup routine.  */
>   	  unsigned int regmask = insn & 0xffff;
> -	  unsigned int num_in_list = bitcount (regmask), new_regmask;
> +	  unsigned int num_in_list = count_one_bits (regmask), new_regmask;
>   	  unsigned int i;
>   
>   	  for (i = 0; i < num_in_list; i++)
> @@ -6084,7 +6086,7 @@ thumb2_copy_block_xfer (struct gdbarch *gdbarch, uint16_t insn1, uint16_t insn2,
>         else
>   	{
>   	  unsigned int regmask = dsc->u.block.regmask;
> -	  unsigned int num_in_list = bitcount (regmask), new_regmask;
> +	  unsigned int num_in_list = count_one_bits (regmask), new_regmask;
>   	  unsigned int i;
>   
>   	  for (i = 0; i < num_in_list; i++)
> @@ -7102,7 +7104,7 @@ thumb_copy_pop_pc_16bit (struct gdbarch *gdbarch, uint16_t insn1,
>       }
>     else
>       {
> -      unsigned int num_in_list = bitcount (dsc->u.block.regmask);
> +      unsigned int num_in_list = count_one_bits (dsc->u.block.regmask);
>         unsigned int i;
>         unsigned int new_regmask;
>   
> diff --git a/gnulib/Makefile.in b/gnulib/Makefile.in
> index 8530f3dcf527..67045edc785c 100644
> --- a/gnulib/Makefile.in
> +++ b/gnulib/Makefile.in
> @@ -1,7 +1,7 @@
>   # Makefile.in generated by automake 1.15.1 from Makefile.am.
>   # @configure_input@
>   
> -# Copyright (C) 1994-2020 Free Software Foundation, Inc.
> +# Copyright (C) 1994-2017 Free Software Foundation, Inc.

The year interval was reverted. Is that a problem?

Otherwise the rest LGTM.
Simon Marchi - Feb. 14, 2020, 7:43 p.m.
On 2020-02-14 5:35 a.m., Luis Machado wrote:
>> --- a/gnulib/Makefile.in
>> +++ b/gnulib/Makefile.in
>> @@ -1,7 +1,7 @@
>>   # Makefile.in generated by automake 1.15.1 from Makefile.am.
>>   # @configure_input@
>>   -# Copyright (C) 1994-2020 Free Software Foundation, Inc.
>> +# Copyright (C) 1994-2017 Free Software Foundation, Inc.
> 
> The year interval was reverted. Is that a problem?

Not really.  The year was changed to 2020 by commit:

  Update copyright year range in all GDB files.
  b811d2c2920ddcb1adcd438da38e90912b31f45f

which updates the copyright years in all of GDB source files at the
beginning of year.  The commit shouldn't have touched this file
though, as it's a generated file.

By re-importing gnulib, it just reverts to the expected value.

Note that in the master branch, it has already been changed back
to 2017 by my other commit:

  gdbsupport: rename source files to .cc
  06b3c5bdb018262d7c09cda9d4637015c7ebe779

I guess it must have been a mistake on my part, as it looks like an
otherwise unrelated change.

> Otherwise the rest LGTM.

Thanks, I'll push it once I confirm it still builds.

Simon

Patch

diff --git a/gdb/arch/arm-get-next-pcs.c b/gdb/arch/arm-get-next-pcs.c
index fc541332aabd..0c49a77245bf 100644
--- a/gdb/arch/arm-get-next-pcs.c
+++ b/gdb/arch/arm-get-next-pcs.c
@@ -22,6 +22,7 @@ 
 #include "gdbsupport/common-regcache.h"
 #include "arm.h"
 #include "arm-get-next-pcs.h"
+#include "count-one-bits.h"
 
 /* See arm-get-next-pcs.h.  */
 
@@ -408,8 +409,8 @@  thumb_get_next_pcs_raw (struct arm_get_next_pcs *self)
 
       /* Fetch the saved PC from the stack.  It's stored above
          all of the other registers.  */
-      unsigned long offset = bitcount (bits (inst1, 0, 7))
-			     * ARM_INT_REGISTER_SIZE;
+      unsigned long offset
+	= count_one_bits (bits (inst1, 0, 7)) * ARM_INT_REGISTER_SIZE;
       sp = regcache_raw_get_unsigned (regcache, ARM_SP_REGNUM);
       nextpc = self->ops->read_mem_uint (sp + offset, 4, byte_order);
     }
@@ -496,7 +497,7 @@  thumb_get_next_pcs_raw (struct arm_get_next_pcs *self)
 	      /* LDMIA or POP */
 	      if (!bit (inst2, 15))
 		load_pc = 0;
-	      offset = bitcount (inst2) * 4 - 4;
+	      offset = count_one_bits (inst2) * 4 - 4;
 	    }
 	  else if (!bit (inst1, 7) && bit (inst1, 8))
 	    {
@@ -864,7 +865,7 @@  arm_get_next_pcs_raw (struct arm_get_next_pcs *self)
 		    {
 		      /* up */
 		      unsigned long reglist = bits (this_instr, 0, 14);
-		      offset = bitcount (reglist) * 4;
+		      offset = count_one_bits_l (reglist) * 4;
 		      if (bit (this_instr, 24))		/* pre */
 			offset += 4;
 		    }
diff --git a/gdb/arch/arm.c b/gdb/arch/arm.c
index 60d9f85889db..faa2b4fbd4b2 100644
--- a/gdb/arch/arm.c
+++ b/gdb/arch/arm.c
@@ -41,17 +41,6 @@  thumb_insn_size (unsigned short inst1)
 
 /* See arm.h.  */
 
-int
-bitcount (unsigned long val)
-{
-  int nbits;
-  for (nbits = 0; val != 0; nbits++)
-    val &= val - 1;		/* Delete rightmost 1-bit in val.  */
-  return nbits;
-}
-
-/* See arm.h.  */
-
 int
 condition_true (unsigned long cond, unsigned long status_reg)
 {
diff --git a/gdb/arch/arm.h b/gdb/arch/arm.h
index 13f030af82ca..2bffb11a4a3f 100644
--- a/gdb/arch/arm.h
+++ b/gdb/arch/arm.h
@@ -159,9 +159,6 @@  int thumb_insn_size (unsigned short inst1);
 /* Returns true if the condition evaluates to true.  */
 int condition_true (unsigned long cond, unsigned long status_reg);
 
-/* Return number of 1-bits in VAL.  */
-int bitcount (unsigned long val);
-
 /* Return 1 if THIS_INSTR might change control flow, 0 otherwise.  */
 int arm_instruction_changes_pc (uint32_t this_instr);
 
diff --git a/gdb/arm-tdep.c b/gdb/arm-tdep.c
index d4fed8977e70..8e647e2e2a8e 100644
--- a/gdb/arm-tdep.c
+++ b/gdb/arm-tdep.c
@@ -45,6 +45,7 @@ 
 #include "target-descriptions.h"
 #include "user-regs.h"
 #include "observable.h"
+#include "count-one-bits.h"
 
 #include "arch/arm.h"
 #include "arch/arm-get-next-pcs.h"
@@ -5798,7 +5799,8 @@  cleanup_block_store_pc (struct gdbarch *gdbarch, struct regcache *regs,
 {
   uint32_t status = displaced_read_reg (regs, dsc, ARM_PS_REGNUM);
   int store_executed = condition_true (dsc->u.block.cond, status);
-  CORE_ADDR pc_stored_at, transferred_regs = bitcount (dsc->u.block.regmask);
+  CORE_ADDR pc_stored_at, transferred_regs
+    = count_one_bits (dsc->u.block.regmask);
   CORE_ADDR stm_insn_addr;
   uint32_t pc_val;
   long offset;
@@ -5850,7 +5852,7 @@  cleanup_block_load_pc (struct gdbarch *gdbarch,
   uint32_t status = displaced_read_reg (regs, dsc, ARM_PS_REGNUM);
   int load_executed = condition_true (dsc->u.block.cond, status);
   unsigned int mask = dsc->u.block.regmask, write_reg = ARM_PC_REGNUM;
-  unsigned int regs_loaded = bitcount (mask);
+  unsigned int regs_loaded = count_one_bits (mask);
   unsigned int num_to_shuffle = regs_loaded, clobbered;
 
   /* The method employed here will fail if the register list is fully populated
@@ -5982,7 +5984,7 @@  arm_copy_block_xfer (struct gdbarch *gdbarch, uint32_t insn,
 	     contiguous chunk r0...rX before doing the transfer, then shuffling
 	     registers into the correct places in the cleanup routine.  */
 	  unsigned int regmask = insn & 0xffff;
-	  unsigned int num_in_list = bitcount (regmask), new_regmask;
+	  unsigned int num_in_list = count_one_bits (regmask), new_regmask;
 	  unsigned int i;
 
 	  for (i = 0; i < num_in_list; i++)
@@ -6084,7 +6086,7 @@  thumb2_copy_block_xfer (struct gdbarch *gdbarch, uint16_t insn1, uint16_t insn2,
       else
 	{
 	  unsigned int regmask = dsc->u.block.regmask;
-	  unsigned int num_in_list = bitcount (regmask), new_regmask;
+	  unsigned int num_in_list = count_one_bits (regmask), new_regmask;
 	  unsigned int i;
 
 	  for (i = 0; i < num_in_list; i++)
@@ -7102,7 +7104,7 @@  thumb_copy_pop_pc_16bit (struct gdbarch *gdbarch, uint16_t insn1,
     }
   else
     {
-      unsigned int num_in_list = bitcount (dsc->u.block.regmask);
+      unsigned int num_in_list = count_one_bits (dsc->u.block.regmask);
       unsigned int i;
       unsigned int new_regmask;
 
diff --git a/gnulib/Makefile.in b/gnulib/Makefile.in
index 8530f3dcf527..67045edc785c 100644
--- a/gnulib/Makefile.in
+++ b/gnulib/Makefile.in
@@ -1,7 +1,7 @@ 
 # Makefile.in generated by automake 1.15.1 from Makefile.am.
 # @configure_input@
 
-# Copyright (C) 1994-2020 Free Software Foundation, Inc.
+# Copyright (C) 1994-2017 Free Software Foundation, Inc.
 
 # This Makefile.in is free software; the Free Software Foundation
 # gives unlimited permission to copy and/or distribute it,
@@ -14,7 +14,7 @@ 
 
 @SET_MAKE@
 
-# Copyright (C) 2019 Free Software Foundation, Inc.
+# Copyright (C) 2019-2020 Free Software Foundation, Inc.
 
 # This file is part of GDB.
 
@@ -123,6 +123,7 @@  am__aclocal_m4_deps = $(top_srcdir)/../config/depstand.m4 \
 	$(top_srcdir)/import/m4/close.m4 \
 	$(top_srcdir)/import/m4/closedir.m4 \
 	$(top_srcdir)/import/m4/codeset.m4 \
+	$(top_srcdir)/import/m4/count-one-bits.m4 \
 	$(top_srcdir)/import/m4/d-ino.m4 \
 	$(top_srcdir)/import/m4/d-type.m4 \
 	$(top_srcdir)/import/m4/dirent_h.m4 \
diff --git a/gnulib/aclocal.m4 b/gnulib/aclocal.m4
index ed1f4f7659c4..4ad6a3dcc867 100644
--- a/gnulib/aclocal.m4
+++ b/gnulib/aclocal.m4
@@ -1195,6 +1195,7 @@  m4_include([import/m4/chdir-long.m4])
 m4_include([import/m4/close.m4])
 m4_include([import/m4/closedir.m4])
 m4_include([import/m4/codeset.m4])
+m4_include([import/m4/count-one-bits.m4])
 m4_include([import/m4/d-ino.m4])
 m4_include([import/m4/d-type.m4])
 m4_include([import/m4/dirent_h.m4])
diff --git a/gnulib/configure b/gnulib/configure
index a0fb5c6b6c6c..90513dc143b9 100644
--- a/gnulib/configure
+++ b/gnulib/configure
@@ -6234,6 +6234,7 @@  fi
   # Code from module cloexec:
   # Code from module close:
   # Code from module closedir:
+  # Code from module count-one-bits:
   # Code from module d-ino:
   # Code from module d-type:
   # Code from module dirent:
@@ -7779,6 +7780,63 @@  $as_echo "#define HAVE_MSVC_INVALID_PARAMETER_HANDLER 1" >>confdefs.h
   REPLACE_FDOPENDIR=0;
 
 
+  { $as_echo "$as_me:${as_lineno-$LINENO}: checking for unsigned long long int" >&5
+$as_echo_n "checking for unsigned long long int... " >&6; }
+if ${ac_cv_type_unsigned_long_long_int+:} false; then :
+  $as_echo_n "(cached) " >&6
+else
+  ac_cv_type_unsigned_long_long_int=yes
+     if test "x${ac_cv_prog_cc_c99-no}" = xno; then
+       cat confdefs.h - <<_ACEOF >conftest.$ac_ext
+/* end confdefs.h.  */
+
+  /* For now, do not test the preprocessor; as of 2007 there are too many
+         implementations with broken preprocessors.  Perhaps this can
+         be revisited in 2012.  In the meantime, code should not expect
+         #if to work with literals wider than 32 bits.  */
+      /* Test literals.  */
+      long long int ll = 9223372036854775807ll;
+      long long int nll = -9223372036854775807LL;
+      unsigned long long int ull = 18446744073709551615ULL;
+      /* Test constant expressions.   */
+      typedef int a[((-9223372036854775807LL < 0 && 0 < 9223372036854775807ll)
+                     ? 1 : -1)];
+      typedef int b[(18446744073709551615ULL <= (unsigned long long int) -1
+                     ? 1 : -1)];
+      int i = 63;
+int
+main ()
+{
+/* Test availability of runtime routines for shift and division.  */
+      long long int llmax = 9223372036854775807ll;
+      unsigned long long int ullmax = 18446744073709551615ull;
+      return ((ll << 63) | (ll >> 63) | (ll < i) | (ll > i)
+              | (llmax / ll) | (llmax % ll)
+              | (ull << 63) | (ull >> 63) | (ull << i) | (ull >> i)
+              | (ullmax / ull) | (ullmax % ull));
+  ;
+  return 0;
+}
+
+_ACEOF
+if ac_fn_c_try_link "$LINENO"; then :
+
+else
+  ac_cv_type_unsigned_long_long_int=no
+fi
+rm -f core conftest.err conftest.$ac_objext \
+    conftest$ac_exeext conftest.$ac_ext
+     fi
+fi
+{ $as_echo "$as_me:${as_lineno-$LINENO}: result: $ac_cv_type_unsigned_long_long_int" >&5
+$as_echo "$ac_cv_type_unsigned_long_long_int" >&6; }
+  if test $ac_cv_type_unsigned_long_long_int = yes; then
+
+$as_echo "#define HAVE_UNSIGNED_LONG_LONG_INT 1" >>confdefs.h
+
+  fi
+
+
 
 
 
@@ -11015,63 +11073,6 @@  $as_echo "$gl_cv_type_wint_t_too_small" >&6; }
 
 
 
-  { $as_echo "$as_me:${as_lineno-$LINENO}: checking for unsigned long long int" >&5
-$as_echo_n "checking for unsigned long long int... " >&6; }
-if ${ac_cv_type_unsigned_long_long_int+:} false; then :
-  $as_echo_n "(cached) " >&6
-else
-  ac_cv_type_unsigned_long_long_int=yes
-     if test "x${ac_cv_prog_cc_c99-no}" = xno; then
-       cat confdefs.h - <<_ACEOF >conftest.$ac_ext
-/* end confdefs.h.  */
-
-  /* For now, do not test the preprocessor; as of 2007 there are too many
-         implementations with broken preprocessors.  Perhaps this can
-         be revisited in 2012.  In the meantime, code should not expect
-         #if to work with literals wider than 32 bits.  */
-      /* Test literals.  */
-      long long int ll = 9223372036854775807ll;
-      long long int nll = -9223372036854775807LL;
-      unsigned long long int ull = 18446744073709551615ULL;
-      /* Test constant expressions.   */
-      typedef int a[((-9223372036854775807LL < 0 && 0 < 9223372036854775807ll)
-                     ? 1 : -1)];
-      typedef int b[(18446744073709551615ULL <= (unsigned long long int) -1
-                     ? 1 : -1)];
-      int i = 63;
-int
-main ()
-{
-/* Test availability of runtime routines for shift and division.  */
-      long long int llmax = 9223372036854775807ll;
-      unsigned long long int ullmax = 18446744073709551615ull;
-      return ((ll << 63) | (ll >> 63) | (ll < i) | (ll > i)
-              | (llmax / ll) | (llmax % ll)
-              | (ull << 63) | (ull >> 63) | (ull << i) | (ull >> i)
-              | (ullmax / ull) | (ullmax % ull));
-  ;
-  return 0;
-}
-
-_ACEOF
-if ac_fn_c_try_link "$LINENO"; then :
-
-else
-  ac_cv_type_unsigned_long_long_int=no
-fi
-rm -f core conftest.err conftest.$ac_objext \
-    conftest$ac_exeext conftest.$ac_ext
-     fi
-fi
-{ $as_echo "$as_me:${as_lineno-$LINENO}: result: $ac_cv_type_unsigned_long_long_int" >&5
-$as_echo "$ac_cv_type_unsigned_long_long_int" >&6; }
-  if test $ac_cv_type_unsigned_long_long_int = yes; then
-
-$as_echo "#define HAVE_UNSIGNED_LONG_LONG_INT 1" >>confdefs.h
-
-  fi
-
-
 
   { $as_echo "$as_me:${as_lineno-$LINENO}: checking for long long int" >&5
 $as_echo_n "checking for long long int... " >&6; }
@@ -16279,6 +16280,9 @@  $as_echo "#define GNULIB_TEST_CLOSEDIR 1" >>confdefs.h
 
 
 
+
+
+
       { $as_echo "$as_me:${as_lineno-$LINENO}: checking for d_ino member in directory struct" >&5
 $as_echo_n "checking for d_ino member in directory struct... " >&6; }
 if ${gl_cv_struct_dirent_d_ino+:} false; then :
diff --git a/gnulib/import/Makefile.am b/gnulib/import/Makefile.am
index 4ddaf4fb5836..094447360b63 100644
--- a/gnulib/import/Makefile.am
+++ b/gnulib/import/Makefile.am
@@ -35,6 +35,7 @@ 
 #  --no-vc-files \
 #  alloca \
 #  canonicalize-lgpl \
+#  count-one-bits \
 #  dirent \
 #  dirfd \
 #  errno \
@@ -236,6 +237,14 @@  EXTRA_libgnu_a_SOURCES += closedir.c
 
 ## end   gnulib module closedir
 
+## begin gnulib module count-one-bits
+
+libgnu_a_SOURCES += count-one-bits.c
+
+EXTRA_DIST += count-one-bits.h
+
+## end   gnulib module count-one-bits
+
 ## begin gnulib module dirent
 
 BUILT_SOURCES += dirent.h
diff --git a/gnulib/import/Makefile.in b/gnulib/import/Makefile.in
index 7059d4c361d0..f5ad783ddb2f 100644
--- a/gnulib/import/Makefile.in
+++ b/gnulib/import/Makefile.in
@@ -49,6 +49,7 @@ 
 #  --no-vc-files \
 #  alloca \
 #  canonicalize-lgpl \
+#  count-one-bits \
 #  dirent \
 #  dirfd \
 #  errno \
@@ -178,6 +179,7 @@  am__aclocal_m4_deps = $(top_srcdir)/../config/depstand.m4 \
 	$(top_srcdir)/import/m4/close.m4 \
 	$(top_srcdir)/import/m4/closedir.m4 \
 	$(top_srcdir)/import/m4/codeset.m4 \
+	$(top_srcdir)/import/m4/count-one-bits.m4 \
 	$(top_srcdir)/import/m4/d-ino.m4 \
 	$(top_srcdir)/import/m4/d-type.m4 \
 	$(top_srcdir)/import/m4/dirent_h.m4 \
@@ -326,14 +328,15 @@  am__v_AR_1 =
 libgnu_a_AR = $(AR) $(ARFLAGS)
 am__DEPENDENCIES_1 =
 am__dirstamp = $(am__leading_dot)dirstamp
-am_libgnu_a_OBJECTS = cloexec.$(OBJEXT) dirname-lgpl.$(OBJEXT) \
-	basename-lgpl.$(OBJEXT) stripslash.$(OBJEXT) \
-	exitfail.$(OBJEXT) fd-hook.$(OBJEXT) fd-safer-flag.$(OBJEXT) \
-	dup-safer-flag.$(OBJEXT) filenamecat-lgpl.$(OBJEXT) \
-	getprogname.$(OBJEXT) hard-locale.$(OBJEXT) \
-	localcharset.$(OBJEXT) glthread/lock.$(OBJEXT) \
-	malloca.$(OBJEXT) math.$(OBJEXT) openat-die.$(OBJEXT) \
-	save-cwd.$(OBJEXT) malloc/scratch_buffer_grow.$(OBJEXT) \
+am_libgnu_a_OBJECTS = cloexec.$(OBJEXT) count-one-bits.$(OBJEXT) \
+	dirname-lgpl.$(OBJEXT) basename-lgpl.$(OBJEXT) \
+	stripslash.$(OBJEXT) exitfail.$(OBJEXT) fd-hook.$(OBJEXT) \
+	fd-safer-flag.$(OBJEXT) dup-safer-flag.$(OBJEXT) \
+	filenamecat-lgpl.$(OBJEXT) getprogname.$(OBJEXT) \
+	hard-locale.$(OBJEXT) localcharset.$(OBJEXT) \
+	glthread/lock.$(OBJEXT) malloca.$(OBJEXT) math.$(OBJEXT) \
+	openat-die.$(OBJEXT) save-cwd.$(OBJEXT) \
+	malloc/scratch_buffer_grow.$(OBJEXT) \
 	malloc/scratch_buffer_grow_preserve.$(OBJEXT) \
 	malloc/scratch_buffer_set_array_size.$(OBJEXT) \
 	stat-time.$(OBJEXT) strnlen1.$(OBJEXT) sys_socket.$(OBJEXT) \
@@ -1620,15 +1623,15 @@  noinst_LTLIBRARIES =
 EXTRA_DIST = m4/gnulib-cache.m4 alloca.c alloca.in.h arpa_inet.in.h \
 	assure.h openat-priv.h openat-proc.c canonicalize-lgpl.c \
 	chdir-long.c chdir-long.h cloexec.h close.c closedir.c \
-	dirent-private.h dirent.in.h dirfd.c dirname.h dosname.h dup.c \
-	dup2.c errno.in.h error.c error.h exitfail.h fchdir.c fcntl.c \
-	fcntl.in.h fd-hook.h fdopendir.c filename.h filenamecat.h \
-	flexmember.h float.c float.in.h itold.c fnmatch.c \
-	fnmatch_loop.c fnmatch.in.h fpucw.h frexp.c frexp.c frexpl.c \
-	fstat.c stat-w32.c stat-w32.h at-func.c fstatat.c getcwd.c \
-	getcwd-lgpl.c getdtablesize.c getlogin_r.c gettimeofday.c \
-	glob.c glob_internal.h glob_pattern_p.c globfree.c glob-libc.h \
-	glob.in.h hard-locale.h \
+	dirent-private.h count-one-bits.h dirent.in.h dirfd.c \
+	dirname.h dosname.h dup.c dup2.c errno.in.h error.c error.h \
+	exitfail.h fchdir.c fcntl.c fcntl.in.h fd-hook.h fdopendir.c \
+	filename.h filenamecat.h flexmember.h float.c float.in.h \
+	itold.c fnmatch.c fnmatch_loop.c fnmatch.in.h fpucw.h frexp.c \
+	frexp.c frexpl.c fstat.c stat-w32.c stat-w32.h at-func.c \
+	fstatat.c getcwd.c getcwd-lgpl.c getdtablesize.c getlogin_r.c \
+	gettimeofday.c glob.c glob_internal.h glob_pattern_p.c \
+	globfree.c glob-libc.h glob.in.h hard-locale.h \
 	$(top_srcdir)/import/extra/config.rpath inet_ntop.c intprops.h \
 	inttypes.in.h float+.h isnan.c isnand-nolibm.h isnand.c \
 	float+.h isnan.c isnanl-nolibm.h isnanl.c cdefs.h \
@@ -1682,12 +1685,12 @@  DISTCLEANFILES =
 MAINTAINERCLEANFILES = 
 AM_CPPFLAGS = 
 AM_CFLAGS = 
-libgnu_a_SOURCES = cloexec.c dirname-lgpl.c basename-lgpl.c \
-	stripslash.c exitfail.c fd-hook.c fd-safer-flag.c \
-	dup-safer-flag.c filenamecat-lgpl.c getprogname.h \
-	getprogname.c gettext.h hard-locale.c localcharset.c \
-	glthread/lock.h glthread/lock.c malloca.c math.c openat-die.c \
-	save-cwd.c malloc/scratch_buffer_grow.c \
+libgnu_a_SOURCES = cloexec.c count-one-bits.c dirname-lgpl.c \
+	basename-lgpl.c stripslash.c exitfail.c fd-hook.c \
+	fd-safer-flag.c dup-safer-flag.c filenamecat-lgpl.c \
+	getprogname.h getprogname.c gettext.h hard-locale.c \
+	localcharset.c glthread/lock.h glthread/lock.c malloca.c \
+	math.c openat-die.c save-cwd.c malloc/scratch_buffer_grow.c \
 	malloc/scratch_buffer_grow_preserve.c \
 	malloc/scratch_buffer_set_array_size.c stat-time.c strnlen1.h \
 	strnlen1.c sys_socket.c tempname.c glthread/threadlib.c \
@@ -1827,6 +1830,7 @@  distclean-compile:
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/cloexec.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/close.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/closedir.Po@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/count-one-bits.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/dirfd.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/dirname-lgpl.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/dup-safer-flag.Po@am__quote@
diff --git a/gnulib/import/count-one-bits.c b/gnulib/import/count-one-bits.c
new file mode 100644
index 000000000000..66341d77cda8
--- /dev/null
+++ b/gnulib/import/count-one-bits.c
@@ -0,0 +1,7 @@ 
+#include <config.h>
+#define COUNT_ONE_BITS_INLINE _GL_EXTERN_INLINE
+#include "count-one-bits.h"
+
+#if 1500 <= _MSC_VER && (defined _M_IX86 || defined _M_X64)
+int popcount_support = -1;
+#endif
diff --git a/gnulib/import/count-one-bits.h b/gnulib/import/count-one-bits.h
new file mode 100644
index 000000000000..00569941885d
--- /dev/null
+++ b/gnulib/import/count-one-bits.h
@@ -0,0 +1,136 @@ 
+/* count-one-bits.h -- counts the number of 1-bits in a word.
+   Copyright (C) 2007-2019 Free Software Foundation, Inc.
+
+   This program is free software: you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 3 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
+
+/* Written by Ben Pfaff.  */
+
+#ifndef COUNT_ONE_BITS_H
+#define COUNT_ONE_BITS_H 1
+
+#include <limits.h>
+#include <stdlib.h>
+
+#ifndef _GL_INLINE_HEADER_BEGIN
+ #error "Please include config.h first."
+#endif
+_GL_INLINE_HEADER_BEGIN
+#ifndef COUNT_ONE_BITS_INLINE
+# define COUNT_ONE_BITS_INLINE _GL_INLINE
+#endif
+
+/* Expand to code that computes the number of 1-bits of the local
+   variable 'x' of type TYPE (an unsigned integer type) and return it
+   from the current function.  */
+#define COUNT_ONE_BITS_GENERIC(TYPE)                                   \
+    do                                                                  \
+      {                                                                 \
+        int count = 0;                                                  \
+        int bits;                                                       \
+        for (bits = 0; bits < sizeof (TYPE) * CHAR_BIT; bits += 32)     \
+          {                                                             \
+            count += count_one_bits_32 (x);                             \
+            x = x >> 31 >> 1;                                           \
+          }                                                             \
+        return count;                                                   \
+      }                                                                 \
+    while (0)
+
+/* Assuming the GCC builtin is BUILTIN and the MSC builtin is MSC_BUILTIN,
+   expand to code that computes the number of 1-bits of the local
+   variable 'x' of type TYPE (an unsigned integer type) and return it
+   from the current function.  */
+#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
+# define COUNT_ONE_BITS(BUILTIN, MSC_BUILTIN, TYPE) return BUILTIN (x)
+#else
+
+/* Compute and return the number of 1-bits set in the least
+   significant 32 bits of X. */
+COUNT_ONE_BITS_INLINE int
+count_one_bits_32 (unsigned int x)
+{
+  x = ((x & 0xaaaaaaaaU) >> 1) + (x & 0x55555555U);
+  x = ((x & 0xccccccccU) >> 2) + (x & 0x33333333U);
+  x = (x >> 16) + (x & 0xffff);
+  x = ((x & 0xf0f0) >> 4) + (x & 0x0f0f);
+  return (x >> 8) + (x & 0x00ff);
+}
+
+# if 1500 <= _MSC_VER && (defined _M_IX86 || defined _M_X64)
+
+/* While gcc falls back to its own generic code if the machine
+   on which it's running doesn't support popcount, with Microsoft's
+   compiler we need to detect and fallback ourselves.  */
+#  pragma intrinsic __cpuid
+#  pragma intrinsic __popcnt
+#  pragma intrinsic __popcnt64
+
+/* Return nonzero if popcount is supported.  */
+
+/* 1 if supported, 0 if not supported, -1 if unknown.  */
+extern int popcount_support;
+
+COUNT_ONE_BITS_INLINE int
+popcount_supported (void)
+{
+  if (popcount_support < 0)
+    {
+      int cpu_info[4];
+      __cpuid (cpu_info, 1);
+      popcount_support = (cpu_info[2] >> 23) & 1;  /* See MSDN.  */
+    }
+  return popcount_support;
+}
+
+#  define COUNT_ONE_BITS(BUILTIN, MSC_BUILTIN, TYPE)    \
+     do                                                 \
+       {                                                \
+         if (popcount_supported ())                     \
+           return MSC_BUILTIN (x);                      \
+         else                                           \
+           COUNT_ONE_BITS_GENERIC (TYPE);               \
+       }                                                \
+     while (0)
+# else
+#  define COUNT_ONE_BITS(BUILTIN, MSC_BUILTIN, TYPE)	\
+     COUNT_ONE_BITS_GENERIC (TYPE)
+# endif
+#endif
+
+/* Compute and return the number of 1-bits set in X. */
+COUNT_ONE_BITS_INLINE int
+count_one_bits (unsigned int x)
+{
+  COUNT_ONE_BITS (__builtin_popcount, __popcnt, unsigned int);
+}
+
+/* Compute and return the number of 1-bits set in X. */
+COUNT_ONE_BITS_INLINE int
+count_one_bits_l (unsigned long int x)
+{
+  COUNT_ONE_BITS (__builtin_popcountl, __popcnt, unsigned long int);
+}
+
+#if HAVE_UNSIGNED_LONG_LONG_INT
+/* Compute and return the number of 1-bits set in X. */
+COUNT_ONE_BITS_INLINE int
+count_one_bits_ll (unsigned long long int x)
+{
+  COUNT_ONE_BITS (__builtin_popcountll, __popcnt64, unsigned long long int);
+}
+#endif
+
+_GL_INLINE_HEADER_END
+
+#endif /* COUNT_ONE_BITS_H */
diff --git a/gnulib/import/m4/count-one-bits.m4 b/gnulib/import/m4/count-one-bits.m4
new file mode 100644
index 000000000000..b4721b549cc3
--- /dev/null
+++ b/gnulib/import/m4/count-one-bits.m4
@@ -0,0 +1,12 @@ 
+# count-one-bits.m4 serial 3
+dnl Copyright (C) 2007, 2009-2019 Free Software Foundation, Inc.
+dnl This file is free software; the Free Software Foundation
+dnl gives unlimited permission to copy and/or distribute it,
+dnl with or without modifications, as long as this notice is preserved.
+
+AC_DEFUN([gl_COUNT_ONE_BITS],
+[
+  dnl We don't need (and can't compile) count_one_bits_ll
+  dnl unless the type 'unsigned long long int' exists.
+  AC_REQUIRE([AC_TYPE_UNSIGNED_LONG_LONG_INT])
+])
diff --git a/gnulib/import/m4/gnulib-cache.m4 b/gnulib/import/m4/gnulib-cache.m4
index 428f5c965f35..03101b642070 100644
--- a/gnulib/import/m4/gnulib-cache.m4
+++ b/gnulib/import/m4/gnulib-cache.m4
@@ -40,6 +40,7 @@ 
 #  --no-vc-files \
 #  alloca \
 #  canonicalize-lgpl \
+#  count-one-bits \
 #  dirent \
 #  dirfd \
 #  errno \
@@ -79,6 +80,7 @@  gl_LOCAL_DIR([])
 gl_MODULES([
   alloca
   canonicalize-lgpl
+  count-one-bits
   dirent
   dirfd
   errno
diff --git a/gnulib/import/m4/gnulib-comp.m4 b/gnulib/import/m4/gnulib-comp.m4
index be1fd390272b..fe1da67d4c75 100644
--- a/gnulib/import/m4/gnulib-comp.m4
+++ b/gnulib/import/m4/gnulib-comp.m4
@@ -57,6 +57,7 @@  AC_DEFUN([gl_EARLY],
   # Code from module cloexec:
   # Code from module close:
   # Code from module closedir:
+  # Code from module count-one-bits:
   # Code from module d-ino:
   # Code from module d-type:
   # Code from module dirent:
@@ -250,6 +251,7 @@  AC_DEFUN([gl_INIT],
     AC_LIBOBJ([closedir])
   fi
   gl_DIRENT_MODULE_INDICATOR([closedir])
+  gl_COUNT_ONE_BITS
   gl_CHECK_TYPE_STRUCT_DIRENT_D_INO
   gl_CHECK_TYPE_STRUCT_DIRENT_D_TYPE
   gl_DIRENT_H
@@ -855,6 +857,8 @@  AC_DEFUN([gl_FILE_LIST], [
   lib/cloexec.h
   lib/close.c
   lib/closedir.c
+  lib/count-one-bits.c
+  lib/count-one-bits.h
   lib/dirent-private.h
   lib/dirent.in.h
   lib/dirfd.c
@@ -1045,6 +1049,7 @@  AC_DEFUN([gl_FILE_LIST], [
   m4/close.m4
   m4/closedir.m4
   m4/codeset.m4
+  m4/count-one-bits.m4
   m4/d-ino.m4
   m4/d-type.m4
   m4/dirent_h.m4
diff --git a/gnulib/update-gnulib.sh b/gnulib/update-gnulib.sh
index 6fa7a56ce2f1..5e4608096864 100755
--- a/gnulib/update-gnulib.sh
+++ b/gnulib/update-gnulib.sh
@@ -32,6 +32,7 @@ 
 IMPORTED_GNULIB_MODULES="\
     alloca \
     canonicalize-lgpl \
+    count-one-bits \
     dirent \
     dirfd \
     errno \