https://gcc.gnu.org/g:92b4552f64a1a065e6c20cdf55c8465faf3159cc
commit 92b4552f64a1a065e6c20cdf55c8465faf3159cc
Author: Andrew Carlotti <andrew.carlo...@arm.com>
Date: Fri Jun 21 18:59:25 2024 +0100
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.
Diff:
---
gcc/bbitmap.h | 236 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 236 insertions(+)
diff --git a/gcc/bbitmap.h b/gcc/bbitmap.h
new file mode 100644
index 000000000000..716c013b1035
--- /dev/null
+++ b/gcc/bbitmap.h
@@ -0,0 +1,236 @@
+/* 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. */
+
+/* Use recusive templated functions to define constexpr operations. */
+template<int M>
+struct bbitmap_operators
+{
+ /* 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...);
+ }
+
+ /* 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 all 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);
+ }
+
+ /* 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,
+ uint64_t ((index - (M - 1) * 64) == (index & 63)) << (index & 63),
+ rest...);
+ }
+};
+
+/* These functions form the base for the recursive functions above. They
+ return either bitmap containing the elements passed in REST, or a default
+ bool result. */
+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 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)
+ {
+ for (int i = 0; i < N; i++)
+ val[i] |= other.val[i];
+
+ 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)
+ {
+ for (int i = 0; i < N; i++)
+ val[i] &= other.val[i];
+
+ 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)
+ {
+ for (int i = 0; i < N; i++)
+ val[i] ^= other.val[i];
+
+ 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);
+ }
+};
+
+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
