[v2,10/11] Add new bbitmap<N> class

This class provides a constant-size bitmap that can be used as almost a
drop-in replacement for bitmaps stored in integer types.  The
implementation is entirely within the header file and uses recursive
templated operations to support effective optimisation and usage in
constexpr expressions.

This initial implementation hardcodes the choice of uint64_t elements
for storage and initialisation, but this could instead be specified via
a second template parameter.

gcc/ChangeLog:

	* bbitmap.h: New file.

Andrew Carlotti <andrew.carlotti@arm.com> writes:
> This class provides a constant-size bitmap that can be used as almost a
> drop-in replacement for bitmaps stored in integer types.  The
> implementation is entirely within the header file and uses recursive
> templated operations to support effective optimisation and usage in
> constexpr expressions.
>
> This initial implementation hardcodes the choice of uint64_t elements
> for storage and initialisation, but this could instead be specified via
> a second template parameter.
>
> gcc/ChangeLog:
>
> 	* bbitmap.h: New file.
>
>
> diff --git a/gcc/bbitmap.h b/gcc/bbitmap.h
> new file mode 100644
> index 0000000000000000000000000000000000000000..108ac1bf9e6042f5ae16988bc1688fe0045a3293
> --- /dev/null
> +++ b/gcc/bbitmap.h
> @@ -0,0 +1,238 @@
> +/* Functions to support fixed-length bitmaps.
> +   Copyright (C) 2024 Free Software Foundation, Inc.
> +
> +This file is part of GCC.
> +
> +GCC 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, or (at your option) any later
> +version.
> +
> +GCC 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 GCC; see the file COPYING3.  If not see
> +<http://www.gnu.org/licenses/>.  */
> +
> +#ifndef GCC_BBITMAP_H
> +#define GCC_BBITMAP_H
> +
> +/* Implementation of bounded (fixed length) bitmaps.
> +
> +   This provides a drop-in replacement for bitmaps that have outgrown the
> +   storage capacity of a single integer.
> +
> +   Sets are stored as a fixed length array of uint64_t elements.  The length of
> +   this array is given as a template parameter.  */
> +
> +template<int M>
> +struct bbitmap_operators
> +{

I think some comments would help here.  Suggestions below:

  /* Return a Result that maps binary operator OP to elements [0, M) of
     X and Y and takes the remaining elements from REST.  */


> +  template<typename Result, typename Operator, typename Arg, typename ...Rest>
> +  static constexpr Result binary(Operator op, const Arg &x, const Arg &y,
> +				 Rest ...rest)
> +  {
> +    return bbitmap_operators<M - 1>::template binary<Result, Operator, Arg>
> +      (op, x, y, op (x.val[M - 1], y.val[M - 1]), rest...);
> +  }
> +
> +  template<typename Operator, typename Arg, typename ...Rest>
> +  static void compound(Operator op, Arg &x, const Arg &y)
> +  {
> +    bbitmap_operators<M - 1>::template compound<Operator, Arg> (op, x, y);
> +    x.val[M - 1] = op (x.val[M - 1], y.val[M - 1]);
> +  }

I'm not sure this one is worth having, since it isn't needed to create
a constexpr.  Seems easier to use a loop in the caller instead.

> +

  /* Return a Result that contains the bitwise inverse of elements [0, M)
     of X and takes the remaining elements from REST.  */

> +  template<typename Result, typename Arg, typename ...Rest>
> +  static constexpr Result bit_not(const Arg &x, Rest ...rest)
> +  {
> +    return bbitmap_operators<M - 1>::template bit_not<Result, Arg>
> +      (x, ~(x.val[M - 1]), rest...);
> +  }
> +

  /* Return true if any element [0, M) of X is nonzero.  */

> +  template<typename Arg>
> +  static constexpr bool non_zero(const Arg &x)
> +  {
> +    return (bool) x.val[M - 1]
> +      || bbitmap_operators<M - 1>::template non_zero<Arg> (x);
> +  }
> +

  /* Return true if elements [0, M) of X are equal to the corresponding
     elements of Y.  */

> +  template<typename Arg>
> +  static constexpr bool equal(const Arg &x, const Arg &y)
> +  {
> +    return x.val[M - 1] == y.val[M - 1]
> +      && bbitmap_operators<M - 1>::template equal<Arg> (x, y);
> +  }
> +
> +#define SUB_INDEX(i) (i - (M - 1) * 64)
> +#define IN_SUB_RANGE(i) (SUB_INDEX (i) >= 0 && SUB_INDEX (i) < 64)
> +

This is the one that motivated the ask for comments :)

  /* If bit index INDEX selects a bit in the first M elements, return a
     Result with that bit set and the other bits of the leading M elements
     clear.  Clear the leading M elements otherwise.  Take the remaining
     elements of the Result from REST.  */

> +  template<typename Result, typename ...Rest>
> +  static constexpr Result from_index(int index, Rest ...rest)
> +  {
> +    return bbitmap_operators<M - 1>::template from_index<Result>
> +      (index,
> +       (IN_SUB_RANGE (index)
> +	? (uint64_t (1) << (IN_SUB_RANGE (index) ? SUB_INDEX (index) : 0))
> +	: uint64_t (0)),

FWIW, a perhaps overly cutesy way of writing this would be:

    uint64_t ((index & 63) == (index - (M - 1) * 64)) << (index & 63),

which at least avoids the macros.

> +       rest...);
> +  }
> +
> +#undef IN_SUB_RANGE
> +#undef SUB_INDEX
> +
> +};
> +
> +template<>
> +struct bbitmap_operators<0>
> +{
> +  template<typename Result, typename Operator, typename Arg, typename ...Rest>
> +  static constexpr Result binary(Operator, const Arg, const Arg,
> +				 Rest ...rest)
> +  {
> +    return Result { rest... };
> +  }
> +
> +  template<typename Operator, typename Arg, typename ...Rest>
> +  static void compound(Operator, Arg, const Arg)
> +  {
> +    return;
> +  }
> +
> +  template<typename Result, typename Arg, typename ...Rest>
> +  static constexpr Result bit_not(const Arg, Rest ...rest)
> +  {
> +    return Result { rest... };
> +  }
> +
> +  template<typename Arg>
> +  static constexpr bool non_zero(const Arg)
> +  {
> +    return false;
> +  }
> +
> +  template<typename Arg>
> +  static constexpr bool equal(const Arg, const Arg)
> +  {
> +    return true;
> +  }
> +
> +  template<typename Result, typename ...Rest>
> +  static constexpr Result from_index(int, Rest ...rest)
> +  {
> +    return Result { rest... };
> +  }
> +};
> +
> +template<typename T>
> +constexpr T bbitmap_element_or(T x, T y) { return x | y;}
> +
> +template<typename T>
> +constexpr T bbitmap_element_and(T x, T y) { return x & y;}
> +
> +template<typename T>
> +constexpr T bbitmap_element_xor(T x, T y) { return x ^ y;}
> +
> +
> +
> +template <int N>
> +class GTY((user)) bbitmap
> +{
> +public:
> +  uint64_t val[N];
> +
> +  template<typename... Rest>
> +  constexpr bbitmap(Rest ...rest) : val{(uint64_t) rest...} {}
> +
> +  constexpr bbitmap<N> operator|(const bbitmap<N> other) const
> +    {
> +      return bbitmap_operators<N>::template binary<bbitmap<N>>(bbitmap_element_or<uint64_t>,
> +						       *this, other);
> +    }

Very minor nit, but the formatting in the earlier classes is AIUI correct,
with no extra indentation on the "{" and "}" relative to the function
declaration.  Also, the lines are too long:

  constexpr bbitmap<N> operator|(const bbitmap<N> other) const
  {
    return bbitmap_operators<N>::template binary<bbitmap<N>>
      (bbitmap_element_or<uint64_t>, *this, other);
  }

Same for the others.

> +
> +  bbitmap<N> operator|=(const bbitmap<N> other)
> +    {
> +      bbitmap_operators<N>::template compound (bbitmap_element_or<uint64_t>,
> +						  *this, other);
> +      return this;
> +    }
> +
> +  constexpr bbitmap<N> operator&(const bbitmap<N> other) const
> +    {
> +      return bbitmap_operators<N>::template binary<bbitmap<N>>(bbitmap_element_and<uint64_t>,
> +						       *this, other);
> +    }
> +
> +  bbitmap<N> operator&=(const bbitmap<N> other)
> +    {
> +      bbitmap_operators<N>::template compound (bbitmap_element_and<uint64_t>,
> +						  *this, other);
> +      return this;
> +    }
> +
> +  constexpr bbitmap<N> operator^(const bbitmap<N> other) const
> +    {
> +      return bbitmap_operators<N>::template binary<bbitmap<N>>(bbitmap_element_xor<uint64_t>,
> +						       *this, other);
> +    }
> +
> +  bbitmap<N> operator^=(const bbitmap<N> other)
> +    {
> +      bbitmap_operators<N>::template compound (bbitmap_element_xor<uint64_t>,
> +						  *this, other);
> +      return this;
> +    }
> +
> +  constexpr bbitmap<N> operator~() const
> +    {
> +      return bbitmap_operators<N>::template bit_not<bbitmap<N>>(*this);
> +    }
> +
> +  constexpr bool operator!() const
> +    {
> +      return !(bbitmap_operators<N>::template non_zero<bbitmap<N>>(*this));
> +    }
> +
> +  constexpr explicit operator bool() const
> +    {
> +      return bbitmap_operators<N>::template non_zero<bbitmap<N>>(*this);
> +    }
> +
> +  constexpr bool operator==(const bbitmap<N> other) const
> +    {
> +      return bbitmap_operators<N>::template equal<bbitmap<N>>(*this, other);
> +    }
> +
> +  constexpr bool operator!=(const bbitmap<N> other) const
> +    {
> +      return !(bbitmap_operators<N>::template equal<bbitmap<N>>(*this, other));
> +    }
> +

  /* Return a bitmap with bit INDEX set and all other bits clear.  */

> +  static constexpr bbitmap<N> from_index (int index)
> +    {
> +      return bbitmap_operators<N>::template from_index<bbitmap<N>> (index);
> +    }

OK with those changes, thanks.

Richard

> +};
> +
> +template<int N>
> +void
> +gt_ggc_mx (bbitmap<N> *)
> +{
> +}
> +
> +template<int N>
> +void
> +gt_pch_nx (bbitmap<N> *)
> +{
> +}
> +
> +template<int N>
> +void
> +gt_pch_nx (bbitmap<N> *, gt_pointer_operator, void *)
> +{
> +}
> +
> +#endif

On Thu, Jul 11, 2024 at 2:18 PM Andrew Carlotti <andrew.carlotti@arm.com> wrote:
>
> This class provides a constant-size bitmap that can be used as almost a
> drop-in replacement for bitmaps stored in integer types.  The
> implementation is entirely within the header file and uses recursive
> templated operations to support effective optimisation and usage in
> constexpr expressions.
>
> This initial implementation hardcodes the choice of uint64_t elements
> for storage and initialisation, but this could instead be specified via
> a second template parameter.

Just an additional comment - so this is a compile-time constant sbitmap.

I wonder iff bbitmap could "transform" itself to a sbitmap and thus get
access to the full sbitmap API this way?

Considering we have

struct simple_bitmap_def
{
  unsigned int n_bits;          /* Number of bits.  */
  unsigned int size;            /* Size in elements.  */
  SBITMAP_ELT_TYPE elms[1];     /* The elements.  */
};

with no indirection to 'elms' this looks a bit complicated.  Still I
see the relation
to sbitmap and so wonder if C++ magicans can figure out a way to "constexpr"
them?

That said, it also feels like a deja-vu - I wondered if we not already
have something
like bbitmap ...

Richard.

> gcc/ChangeLog:
>
>         * bbitmap.h: New file.
>
>
> diff --git a/gcc/bbitmap.h b/gcc/bbitmap.h
> new file mode 100644
> index 0000000000000000000000000000000000000000..108ac1bf9e6042f5ae16988bc1688fe0045a3293
> --- /dev/null
> +++ b/gcc/bbitmap.h
> @@ -0,0 +1,238 @@
> +/* Functions to support fixed-length bitmaps.
> +   Copyright (C) 2024 Free Software Foundation, Inc.
> +
> +This file is part of GCC.
> +
> +GCC 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, or (at your option) any later
> +version.
> +
> +GCC 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 GCC; see the file COPYING3.  If not see
> +<http://www.gnu.org/licenses/>.  */
> +
> +#ifndef GCC_BBITMAP_H
> +#define GCC_BBITMAP_H
> +
> +/* Implementation of bounded (fixed length) bitmaps.
> +
> +   This provides a drop-in replacement for bitmaps that have outgrown the
> +   storage capacity of a single integer.
> +
> +   Sets are stored as a fixed length array of uint64_t elements.  The length of
> +   this array is given as a template parameter.  */
> +
> +template<int M>
> +struct bbitmap_operators
> +{
> +  template<typename Result, typename Operator, typename Arg, typename ...Rest>
> +  static constexpr Result binary(Operator op, const Arg &x, const Arg &y,
> +                                Rest ...rest)
> +  {
> +    return bbitmap_operators<M - 1>::template binary<Result, Operator, Arg>
> +      (op, x, y, op (x.val[M - 1], y.val[M - 1]), rest...);
> +  }
> +
> +  template<typename Operator, typename Arg, typename ...Rest>
> +  static void compound(Operator op, Arg &x, const Arg &y)
> +  {
> +    bbitmap_operators<M - 1>::template compound<Operator, Arg> (op, x, y);
> +    x.val[M - 1] = op (x.val[M - 1], y.val[M - 1]);
> +  }
> +
> +  template<typename Result, typename Arg, typename ...Rest>
> +  static constexpr Result bit_not(const Arg &x, Rest ...rest)
> +  {
> +    return bbitmap_operators<M - 1>::template bit_not<Result, Arg>
> +      (x, ~(x.val[M - 1]), rest...);
> +  }
> +
> +  template<typename Arg>
> +  static constexpr bool non_zero(const Arg &x)
> +  {
> +    return (bool) x.val[M - 1]
> +      || bbitmap_operators<M - 1>::template non_zero<Arg> (x);
> +  }
> +
> +  template<typename Arg>
> +  static constexpr bool equal(const Arg &x, const Arg &y)
> +  {
> +    return x.val[M - 1] == y.val[M - 1]
> +      && bbitmap_operators<M - 1>::template equal<Arg> (x, y);
> +  }
> +
> +#define SUB_INDEX(i) (i - (M - 1) * 64)
> +#define IN_SUB_RANGE(i) (SUB_INDEX (i) >= 0 && SUB_INDEX (i) < 64)
> +
> +  template<typename Result, typename ...Rest>
> +  static constexpr Result from_index(int index, Rest ...rest)
> +  {
> +    return bbitmap_operators<M - 1>::template from_index<Result>
> +      (index,
> +       (IN_SUB_RANGE (index)
> +       ? (uint64_t (1) << (IN_SUB_RANGE (index) ? SUB_INDEX (index) : 0))
> +       : uint64_t (0)),
> +       rest...);
> +  }
> +
> +#undef IN_SUB_RANGE
> +#undef SUB_INDEX
> +
> +};
> +
> +template<>
> +struct bbitmap_operators<0>
> +{
> +  template<typename Result, typename Operator, typename Arg, typename ...Rest>
> +  static constexpr Result binary(Operator, const Arg, const Arg,
> +                                Rest ...rest)
> +  {
> +    return Result { rest... };
> +  }
> +
> +  template<typename Operator, typename Arg, typename ...Rest>
> +  static void compound(Operator, Arg, const Arg)
> +  {
> +    return;
> +  }
> +
> +  template<typename Result, typename Arg, typename ...Rest>
> +  static constexpr Result bit_not(const Arg, Rest ...rest)
> +  {
> +    return Result { rest... };
> +  }
> +
> +  template<typename Arg>
> +  static constexpr bool non_zero(const Arg)
> +  {
> +    return false;
> +  }
> +
> +  template<typename Arg>
> +  static constexpr bool equal(const Arg, const Arg)
> +  {
> +    return true;
> +  }
> +
> +  template<typename Result, typename ...Rest>
> +  static constexpr Result from_index(int, Rest ...rest)
> +  {
> +    return Result { rest... };
> +  }
> +};
> +
> +template<typename T>
> +constexpr T bbitmap_element_or(T x, T y) { return x | y;}
> +
> +template<typename T>
> +constexpr T bbitmap_element_and(T x, T y) { return x & y;}
> +
> +template<typename T>
> +constexpr T bbitmap_element_xor(T x, T y) { return x ^ y;}
> +
> +
> +
> +template <int N>
> +class GTY((user)) bbitmap
> +{
> +public:
> +  uint64_t val[N];
> +
> +  template<typename... Rest>
> +  constexpr bbitmap(Rest ...rest) : val{(uint64_t) rest...} {}
> +
> +  constexpr bbitmap<N> operator|(const bbitmap<N> other) const
> +    {
> +      return bbitmap_operators<N>::template binary<bbitmap<N>>(bbitmap_element_or<uint64_t>,
> +                                                      *this, other);
> +    }
> +
> +  bbitmap<N> operator|=(const bbitmap<N> other)
> +    {
> +      bbitmap_operators<N>::template compound (bbitmap_element_or<uint64_t>,
> +                                                 *this, other);
> +      return this;
> +    }
> +
> +  constexpr bbitmap<N> operator&(const bbitmap<N> other) const
> +    {
> +      return bbitmap_operators<N>::template binary<bbitmap<N>>(bbitmap_element_and<uint64_t>,
> +                                                      *this, other);
> +    }
> +
> +  bbitmap<N> operator&=(const bbitmap<N> other)
> +    {
> +      bbitmap_operators<N>::template compound (bbitmap_element_and<uint64_t>,
> +                                                 *this, other);
> +      return this;
> +    }
> +
> +  constexpr bbitmap<N> operator^(const bbitmap<N> other) const
> +    {
> +      return bbitmap_operators<N>::template binary<bbitmap<N>>(bbitmap_element_xor<uint64_t>,
> +                                                      *this, other);
> +    }
> +
> +  bbitmap<N> operator^=(const bbitmap<N> other)
> +    {
> +      bbitmap_operators<N>::template compound (bbitmap_element_xor<uint64_t>,
> +                                                 *this, other);
> +      return this;
> +    }
> +
> +  constexpr bbitmap<N> operator~() const
> +    {
> +      return bbitmap_operators<N>::template bit_not<bbitmap<N>>(*this);
> +    }
> +
> +  constexpr bool operator!() const
> +    {
> +      return !(bbitmap_operators<N>::template non_zero<bbitmap<N>>(*this));
> +    }
> +
> +  constexpr explicit operator bool() const
> +    {
> +      return bbitmap_operators<N>::template non_zero<bbitmap<N>>(*this);
> +    }
> +
> +  constexpr bool operator==(const bbitmap<N> other) const
> +    {
> +      return bbitmap_operators<N>::template equal<bbitmap<N>>(*this, other);
> +    }
> +
> +  constexpr bool operator!=(const bbitmap<N> other) const
> +    {
> +      return !(bbitmap_operators<N>::template equal<bbitmap<N>>(*this, other));
> +    }
> +
> +  static constexpr bbitmap<N> from_index (int index)
> +    {
> +      return bbitmap_operators<N>::template from_index<bbitmap<N>> (index);
> +    }
> +};
> +
> +template<int N>
> +void
> +gt_ggc_mx (bbitmap<N> *)
> +{
> +}
> +
> +template<int N>
> +void
> +gt_pch_nx (bbitmap<N> *)
> +{
> +}
> +
> +template<int N>
> +void
> +gt_pch_nx (bbitmap<N> *, gt_pointer_operator, void *)
> +{
> +}
> +
> +#endif