Andrew Carlotti <andrew.carlo...@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
