From 148909bc700e4f52aa582346a29abc5bc51a9bda Mon Sep 17 00:00:00 2001 From: Richard Sandiford Date: Mon, 9 Sep 2019 18:01:47 +0000 Subject: [PATCH] Add "fast" conversions from arrays to bitmaps This patch adds a bitmap_view class that creates a read-only, on-stack bitmap representation of an array-like object X. The main use case is to allow HARD_REG_SETs to be used in REG_SET (i.e. bitmap) operations. For now it only handles constant-sized arrays, but I've tried to define the types in a way that could handle variable-sized arrays in future (although less efficiently). E.g. this might be useful for combining bitmaps and sbitmaps. For the read-only view to work as intended, I needed to make bitmap_bit_p take a const_bitmap instead of a bitmap. Logically the bitmap really is read-only, but we update the "current" and "indx" fields of the bitmap_head after doing a search. 2019-09-09 Richard Sandiford gcc/ * array-traits.h: New file. * coretypes.h (array_traits, bitmap_view): New types. * bitmap.h: Include "array-traits.h" (bitmap_bit_p): Take a const_bitmap instead of a bitmap. (base_bitmap_view, bitmap_view): New classes. * bitmap.c (bitmap_bit_p): Take a const_bitmap instead of a bitmap. * hard-reg-set.h: Include array-traits.h. (array_traits): New struct. * regset.h (IOR_REG_SET_HRS): New macro. * loop-iv.c (simplify_using_initial_values): Use IOR_REG_SET_HRS rather than iterating over each hard register. * sched-deps.c (sched_analyze_insn): Likewise. * sel-sched-ir.c (setup_id_implicit_regs): Likewise. From-SVN: r275536 --- gcc/ChangeLog | 16 ++++++ gcc/array-traits.h | 48 ++++++++++++++++++ gcc/bitmap.c | 8 +-- gcc/bitmap.h | 122 ++++++++++++++++++++++++++++++++++++++++++++- gcc/coretypes.h | 8 +++ gcc/hard-reg-set.h | 12 +++++ gcc/loop-iv.c | 10 +--- gcc/regset.h | 4 ++ gcc/sched-deps.c | 7 ++- gcc/sel-sched-ir.c | 5 +- 10 files changed, 219 insertions(+), 21 deletions(-) create mode 100644 gcc/array-traits.h diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 7ae8c4333f9..248c5a5ec4b 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,19 @@ +2019-09-09 Richard Sandiford + + * array-traits.h: New file. + * coretypes.h (array_traits, bitmap_view): New types. + * bitmap.h: Include "array-traits.h" + (bitmap_bit_p): Take a const_bitmap instead of a bitmap. + (base_bitmap_view, bitmap_view): New classes. + * bitmap.c (bitmap_bit_p): Take a const_bitmap instead of a bitmap. + * hard-reg-set.h: Include array-traits.h. + (array_traits): New struct. + * regset.h (IOR_REG_SET_HRS): New macro. + * loop-iv.c (simplify_using_initial_values): Use IOR_REG_SET_HRS + rather than iterating over each hard register. + * sched-deps.c (sched_analyze_insn): Likewise. + * sel-sched-ir.c (setup_id_implicit_regs): Likewise. + 2019-09-09 Richard Sandiford * ira-int.h (ior_hard_reg_conflicts): Take a const_hard_reg_set diff --git a/gcc/array-traits.h b/gcc/array-traits.h new file mode 100644 index 00000000000..eb65ede9458 --- /dev/null +++ b/gcc/array-traits.h @@ -0,0 +1,48 @@ +/* Descriptions of array-like objects. + Copyright (C) 2019 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 +. */ + +#ifndef GCC_ARRAY_TRAITS_H +#define GCC_ARRAY_TRAITS_H + +/* Implementation for single integers (and similar types). */ +template +struct scalar_array_traits +{ + typedef T element_type; + static const bool has_constant_size = true; + static const size_t constant_size = 1; + static const T *base (const T &x) { return &x; } + static size_t size (const T &) { return 1; } +}; + +template +struct array_traits : scalar_array_traits {}; + +/* Implementation for arrays with a static size. */ +template +struct array_traits +{ + typedef T element_type; + static const bool has_constant_size = true; + static const size_t constant_size = N; + static const T *base (const T (&x)[N]) { return x; } + static size_t size (const T (&x)[N]) { return N; } +}; + +#endif diff --git a/gcc/bitmap.c b/gcc/bitmap.c index ce68a628358..c6afa3f1835 100644 --- a/gcc/bitmap.c +++ b/gcc/bitmap.c @@ -979,17 +979,17 @@ bitmap_set_bit (bitmap head, int bit) /* Return whether a bit is set within a bitmap. */ int -bitmap_bit_p (bitmap head, int bit) +bitmap_bit_p (const_bitmap head, int bit) { unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS; - bitmap_element *ptr; + const bitmap_element *ptr; unsigned bit_num; unsigned word_num; if (!head->tree_form) - ptr = bitmap_list_find_element (head, indx); + ptr = bitmap_list_find_element (const_cast (head), indx); else - ptr = bitmap_tree_find_element (head, indx); + ptr = bitmap_tree_find_element (const_cast (head), indx); if (ptr == 0) return 0; diff --git a/gcc/bitmap.h b/gcc/bitmap.h index 5e080afd457..6502acbd2d7 100644 --- a/gcc/bitmap.h +++ b/gcc/bitmap.h @@ -210,6 +210,7 @@ along with GCC; see the file COPYING3. If not see on which many random-access membership tests will happen. */ #include "obstack.h" +#include "array-traits.h" /* Bitmap memory usage. */ class bitmap_usage: public mem_usage @@ -435,7 +436,7 @@ extern bool bitmap_clear_bit (bitmap, int); extern bool bitmap_set_bit (bitmap, int); /* Return true if a bit is set in a bitmap. */ -extern int bitmap_bit_p (bitmap, int); +extern int bitmap_bit_p (const_bitmap, int); /* Debug functions to print a bitmap. */ extern void debug_bitmap (const_bitmap); @@ -956,4 +957,123 @@ class auto_bitmap bitmap_head m_bits; }; +/* Base class for bitmap_view; see there for details. */ +template > +class base_bitmap_view +{ +public: + typedef typename Traits::element_type array_element_type; + + base_bitmap_view (const T &, bitmap_element *); + operator const_bitmap () const { return &m_head; } + +private: + base_bitmap_view (const base_bitmap_view &); + + bitmap_head m_head; +}; + +/* Provides a read-only bitmap view of a single integer bitmask or a + constant-sized array of integer bitmasks, or of a wrapper around such + bitmasks. */ +template +class bitmap_view : public base_bitmap_view +{ +public: + bitmap_view (const T &array) + : base_bitmap_view (array, m_bitmap_elements) {} + +private: + /* How many bitmap_elements we need to hold a full T. */ + static const size_t num_bitmap_elements + = CEIL (CHAR_BIT + * sizeof (typename Traits::element_type) + * Traits::constant_size, + BITMAP_ELEMENT_ALL_BITS); + bitmap_element m_bitmap_elements[num_bitmap_elements]; +}; + +/* Initialize the view for array ARRAY, using the array of bitmap + elements in BITMAP_ELEMENTS (which is known to contain enough + entries). */ +template +base_bitmap_view::base_bitmap_view (const T &array, + bitmap_element *bitmap_elements) +{ + m_head.obstack = NULL; + + /* The code currently assumes that each element of ARRAY corresponds + to exactly one bitmap_element. */ + const size_t array_element_bits = CHAR_BIT * sizeof (array_element_type); + STATIC_ASSERT (BITMAP_ELEMENT_ALL_BITS % array_element_bits == 0); + size_t array_step = BITMAP_ELEMENT_ALL_BITS / array_element_bits; + size_t array_size = Traits::size (array); + + /* Process each potential bitmap_element in turn. The loop is written + this way rather than per array element because usually there are + only a small number of array elements per bitmap element (typically + two or four). The inner loops should therefore unroll completely. */ + const array_element_type *array_elements = Traits::base (array); + unsigned int indx = 0; + for (size_t array_base = 0; + array_base < array_size; + array_base += array_step, indx += 1) + { + /* How many array elements are in this particular bitmap_element. */ + unsigned int array_count + = (STATIC_CONSTANT_P (array_size % array_step == 0) + ? array_step : MIN (array_step, array_size - array_base)); + + /* See whether we need this bitmap element. */ + array_element_type ior = array_elements[array_base]; + for (size_t i = 1; i < array_count; ++i) + ior |= array_elements[array_base + i]; + if (ior == 0) + continue; + + /* Grab the next bitmap element and chain it. */ + bitmap_element *bitmap_element = bitmap_elements++; + if (m_head.current) + m_head.current->next = bitmap_element; + else + m_head.first = bitmap_element; + bitmap_element->prev = m_head.current; + bitmap_element->next = NULL; + bitmap_element->indx = indx; + m_head.current = bitmap_element; + m_head.indx = indx; + + /* Fill in the bits of the bitmap element. */ + if (array_element_bits < BITMAP_WORD_BITS) + { + /* Multiple array elements fit in one element of + bitmap_element->bits. */ + size_t array_i = array_base; + for (unsigned int word_i = 0; word_i < BITMAP_ELEMENT_WORDS; + ++word_i) + { + BITMAP_WORD word = 0; + for (unsigned int shift = 0; + shift < BITMAP_WORD_BITS && array_i < array_size; + shift += array_element_bits) + word |= array_elements[array_i++] << shift; + bitmap_element->bits[word_i] = word; + } + } + else + { + /* Array elements are the same size as elements of + bitmap_element->bits, or are an exact multiple of that size. */ + unsigned int word_i = 0; + for (unsigned int i = 0; i < array_count; ++i) + for (unsigned int shift = 0; shift < array_element_bits; + shift += BITMAP_WORD_BITS) + bitmap_element->bits[word_i++] + = array_elements[array_base + i] >> shift; + while (word_i < BITMAP_ELEMENT_WORDS) + bitmap_element->bits[word_i++] = 0; + } + } +} + #endif /* GCC_BITMAP_H */ diff --git a/gcc/coretypes.h b/gcc/coretypes.h index eac2f3931aa..fc0e09b2000 100644 --- a/gcc/coretypes.h +++ b/gcc/coretypes.h @@ -153,6 +153,14 @@ struct cl_option_handlers; struct diagnostic_context; class pretty_printer; +template struct array_traits; + +/* Provides a read-only bitmap view of a single integer bitmask or an + array of integer bitmasks, or of a wrapper around such bitmasks. */ +template, + bool has_constant_size = Traits::has_constant_size> +class bitmap_view; + /* Address space number for named address space support. */ typedef unsigned char addr_space_t; diff --git a/gcc/hard-reg-set.h b/gcc/hard-reg-set.h index e59779dddd2..274956e1ec3 100644 --- a/gcc/hard-reg-set.h +++ b/gcc/hard-reg-set.h @@ -20,6 +20,8 @@ along with GCC; see the file COPYING3. If not see #ifndef GCC_HARD_REG_SET_H #define GCC_HARD_REG_SET_H +#include "array-traits.h" + /* Define the type of a set of hard registers. */ /* HARD_REG_ELT_TYPE is a typedef of the unsigned integral type which @@ -115,6 +117,16 @@ struct HARD_REG_SET }; typedef const HARD_REG_SET &const_hard_reg_set; +template<> +struct array_traits +{ + typedef HARD_REG_ELT_TYPE element_type; + static const bool has_constant_size = true; + static const size_t constant_size = HARD_REG_SET_LONGS; + static const element_type *base (const HARD_REG_SET &x) { return x.elts; } + static size_t size (const HARD_REG_SET &) { return HARD_REG_SET_LONGS; } +}; + #endif /* HARD_REG_SET wrapped into a structure, to make it possible to diff --git a/gcc/loop-iv.c b/gcc/loop-iv.c index 82b329f67a7..33be75add72 100644 --- a/gcc/loop-iv.c +++ b/gcc/loop-iv.c @@ -1972,14 +1972,8 @@ simplify_using_initial_values (class loop *loop, enum rtx_code op, rtx *expr) CLEAR_REG_SET (this_altered); note_stores (insn, mark_altered, this_altered); if (CALL_P (insn)) - { - /* Kill all call clobbered registers. */ - unsigned int i; - hard_reg_set_iterator hrsi; - EXECUTE_IF_SET_IN_HARD_REG_SET (regs_invalidated_by_call, - 0, i, hrsi) - SET_REGNO_REG_SET (this_altered, i); - } + /* Kill all call clobbered registers. */ + IOR_REG_SET_HRS (this_altered, regs_invalidated_by_call); if (suitable_set_for_replacement (insn, &dest, &src)) { diff --git a/gcc/regset.h b/gcc/regset.h index 34a9eb457b6..f5e3d390b14 100644 --- a/gcc/regset.h +++ b/gcc/regset.h @@ -64,6 +64,10 @@ typedef bitmap regset; /* Inclusive or a register set with a second register set. */ #define IOR_REG_SET(TO, FROM) bitmap_ior_into (TO, FROM) +/* Same, but with FROM being a HARD_REG_SET. */ +#define IOR_REG_SET_HRS(TO, FROM) \ + bitmap_ior_into (TO, bitmap_view (FROM)) + /* Exclusive or a register set with a second register set. */ #define XOR_REG_SET(TO, FROM) bitmap_xor_into (TO, FROM) diff --git a/gcc/sched-deps.c b/gcc/sched-deps.c index 36a6669f113..52db3cc1523 100644 --- a/gcc/sched-deps.c +++ b/gcc/sched-deps.c @@ -3332,10 +3332,9 @@ sched_analyze_insn (class deps_desc *deps, rtx x, rtx_insn *insn) IOR_REG_SET (&deps->reg_last_in_use, reg_pending_uses); IOR_REG_SET (&deps->reg_last_in_use, reg_pending_clobbers); IOR_REG_SET (&deps->reg_last_in_use, reg_pending_sets); - for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) - if (TEST_HARD_REG_BIT (implicit_reg_pending_uses, i) - || TEST_HARD_REG_BIT (implicit_reg_pending_clobbers, i)) - SET_REGNO_REG_SET (&deps->reg_last_in_use, i); + IOR_REG_SET_HRS (&deps->reg_last_in_use, + implicit_reg_pending_uses + | implicit_reg_pending_clobbers); /* Set up the pending barrier found. */ deps->last_reg_pending_barrier = reg_pending_barrier; diff --git a/gcc/sel-sched-ir.c b/gcc/sel-sched-ir.c index bb8016bb530..e4f5a454fdb 100644 --- a/gcc/sel-sched-ir.c +++ b/gcc/sel-sched-ir.c @@ -2661,12 +2661,9 @@ setup_id_implicit_regs (idata_t id, insn_t insn) return; HARD_REG_SET temp; - unsigned regno; - hard_reg_set_iterator hrsi; get_implicit_reg_pending_clobbers (&temp, insn); - EXECUTE_IF_SET_IN_HARD_REG_SET (temp, 0, regno, hrsi) - SET_REGNO_REG_SET (IDATA_REG_SETS (id), regno); + IOR_REG_SET_HRS (IDATA_REG_SETS (id), temp); } /* Setup register sets describing INSN in ID. */ -- 2.30.2