From 476dd0ce18abee7581ab669bb9d5b80dcac09d82 Mon Sep 17 00:00:00 2001 From: Richard Sandiford Date: Thu, 28 Aug 2014 06:20:12 +0000 Subject: [PATCH] rtl-iter.h: New file. gcc/ * rtl-iter.h: New file. * rtlanal.c: Include it. (rtx_all_subrtx_bounds, rtx_nonconst_subrtx_bounds): New variables. (generic_subrtx_iterator ::add_single_to_queue) (generic_subrtx_iterator ::add_subrtxes_to_queue) (generic_subrtx_iterator ::free_array): New functions. (generic_subrtx_iterator ::LOCAL_ELEMS): Define. (generic_subrtx_iterator ) (generic_subrtx_iterator (generic_subrtx_iterator ): Instantiate. (setup_reg_subrtx_bounds): New function. (init_rtlanal): Call it. From-SVN: r214618 --- gcc/ChangeLog | 15 +++ gcc/rtl-iter.h | 291 +++++++++++++++++++++++++++++++++++++++++++++++++ gcc/rtlanal.c | 131 +++++++++++++++++++++- 3 files changed, 436 insertions(+), 1 deletion(-) create mode 100644 gcc/rtl-iter.h diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 9cb7fe3170d..aefa4507598 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,18 @@ +2014-08-28 Richard Sandiford + + * rtl-iter.h: New file. + * rtlanal.c: Include it. + (rtx_all_subrtx_bounds, rtx_nonconst_subrtx_bounds): New variables. + (generic_subrtx_iterator ::add_single_to_queue) + (generic_subrtx_iterator ::add_subrtxes_to_queue) + (generic_subrtx_iterator ::free_array): New functions. + (generic_subrtx_iterator ::LOCAL_ELEMS): Define. + (generic_subrtx_iterator ) + (generic_subrtx_iterator + (generic_subrtx_iterator ): Instantiate. + (setup_reg_subrtx_bounds): New function. + (init_rtlanal): Call it. + 2014-08-27 Kaz Kojima PR target/62261 diff --git a/gcc/rtl-iter.h b/gcc/rtl-iter.h new file mode 100644 index 00000000000..958999b00ee --- /dev/null +++ b/gcc/rtl-iter.h @@ -0,0 +1,291 @@ +/* RTL iterators + Copyright (C) 2014 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 +. */ + +/* This structure describes the subrtxes of an rtx as follows: + + - if the rtx has no subrtxes, START and COUNT are both 0. + + - if all the subrtxes of an rtx are stored in a contiguous block + of XEXPs ("e"s), START is the index of the first XEXP and COUNT + is the number of them. + + - otherwise START is arbitrary and COUNT is UCHAR_MAX. + + rtx_all_subrtx_bounds applies to all codes. rtx_nonconst_subrtx_bounds + is like rtx_all_subrtx_bounds except that all constant rtxes are treated + as having no subrtxes. */ +struct rtx_subrtx_bound_info { + unsigned char start; + unsigned char count; +}; +extern rtx_subrtx_bound_info rtx_all_subrtx_bounds[]; +extern rtx_subrtx_bound_info rtx_nonconst_subrtx_bounds[]; + +/* Return true if CODE has no subrtxes. */ + +static inline bool +leaf_code_p (enum rtx_code code) +{ + return rtx_all_subrtx_bounds[code].count == 0; +} + +/* Used to iterate over subrtxes of an rtx. T abstracts the type of + access. */ +template +class generic_subrtx_iterator +{ + static const size_t LOCAL_ELEMS = 16; + typedef typename T::value_type value_type; + typedef typename T::rtx_type rtx_type; + typedef typename T::rtunion_type rtunion_type; + +public: + struct array_type + { + array_type (); + ~array_type (); + value_type stack[LOCAL_ELEMS]; + vec *heap; + }; + generic_subrtx_iterator (array_type &, value_type, + const rtx_subrtx_bound_info *); + + value_type operator * () const; + bool at_end () const; + void next (); + void skip_subrtxes (); + void substitute (value_type); + +private: + /* The bounds to use for iterating over subrtxes. */ + const rtx_subrtx_bound_info *m_bounds; + + /* The storage used for the worklist. */ + array_type &m_array; + + /* The current rtx. */ + value_type m_current; + + /* The base of the current worklist. */ + value_type *m_base; + + /* The number of subrtxes in M_BASE. */ + size_t m_end; + + /* The following booleans shouldn't end up in registers or memory + but just direct control flow. */ + + /* True if the iteration is over. */ + bool m_done; + + /* True if we should skip the subrtxes of M_CURRENT. */ + bool m_skip; + + /* True if M_CURRENT has been replaced with a different rtx. */ + bool m_substitute; + + static void free_array (array_type &); + static size_t add_subrtxes_to_queue (array_type &, value_type *, size_t, + rtx_type); + static value_type *add_single_to_queue (array_type &, value_type *, size_t, + value_type); +}; + +template +inline generic_subrtx_iterator ::array_type::array_type () : heap (0) {} + +template +inline generic_subrtx_iterator ::array_type::~array_type () +{ + if (__builtin_expect (heap != 0, false)) + free_array (*this); +} + +/* Iterate over X and its subrtxes, in arbitrary order. Use ARRAY to + store the worklist. We use an external array in order to avoid + capturing the fields of this structure when taking the address of + the array. Use BOUNDS to find the bounds of simple "e"-string codes. */ + +template +inline generic_subrtx_iterator :: +generic_subrtx_iterator (array_type &array, value_type x, + const rtx_subrtx_bound_info *bounds) + : m_bounds (bounds), + m_array (array), + m_current (x), + m_base (m_array.stack), + m_end (0), + m_done (false), + m_skip (false), + m_substitute (false) +{ +} + +/* Return the current subrtx. */ + +template +inline typename T::value_type +generic_subrtx_iterator ::operator * () const +{ + return m_current; +} + +/* Return true if the iteration has finished. */ + +template +inline bool +generic_subrtx_iterator ::at_end () const +{ + return m_done; +} + +/* Move on to the next subrtx. */ + +template +inline void +generic_subrtx_iterator ::next () +{ + if (m_substitute) + { + m_substitute = false; + m_skip = false; + return; + } + if (!m_skip) + { + /* Add the subrtxes of M_CURRENT. */ + rtx_type x = T::get_rtx (m_current); + if (__builtin_expect (x != 0, true)) + { + enum rtx_code code = GET_CODE (x); + ssize_t count = m_bounds[code].count; + if (count > 0) + { + /* Handle the simple case of a single "e" block that is known + to fit into the current array. */ + if (__builtin_expect (m_end + count <= LOCAL_ELEMS + 1, true)) + { + /* Set M_CURRENT to the first subrtx and queue the rest. */ + ssize_t start = m_bounds[code].start; + rtunion_type *src = &x->u.fld[start]; + if (__builtin_expect (count > 2, false)) + m_base[m_end++] = T::get_value (src[2].rt_rtx); + if (count > 1) + m_base[m_end++] = T::get_value (src[1].rt_rtx); + m_current = T::get_value (src[0].rt_rtx); + return; + } + /* Handle cases which aren't simple "e" sequences or where + the sequence might overrun M_BASE. */ + count = add_subrtxes_to_queue (m_array, m_base, m_end, x); + if (count > 0) + { + m_end += count; + if (m_end > LOCAL_ELEMS) + m_base = m_array.heap->address (); + m_current = m_base[--m_end]; + return; + } + } + } + } + else + m_skip = false; + if (m_end == 0) + m_done = true; + else + m_current = m_base[--m_end]; +} + +/* Skip the subrtxes of the current rtx. */ + +template +inline void +generic_subrtx_iterator ::skip_subrtxes () +{ + m_skip = true; +} + +/* Ignore the subrtxes of the current rtx and look at X instead. */ + +template +inline void +generic_subrtx_iterator ::substitute (value_type x) +{ + m_substitute = true; + m_current = x; +} + +/* Iterators for const_rtx. */ +struct const_rtx_accessor +{ + typedef const_rtx value_type; + typedef const_rtx rtx_type; + typedef const rtunion rtunion_type; + static rtx_type get_rtx (value_type x) { return x; } + static value_type get_value (rtx_type x) { return x; } +}; +typedef generic_subrtx_iterator subrtx_iterator; + +/* Iterators for non-constant rtx. */ +struct rtx_var_accessor +{ + typedef rtx value_type; + typedef rtx rtx_type; + typedef rtunion rtunion_type; + static rtx_type get_rtx (value_type x) { return x; } + static value_type get_value (rtx_type x) { return x; } +}; +typedef generic_subrtx_iterator subrtx_var_iterator; + +/* Iterators for rtx *. */ +struct rtx_ptr_accessor +{ + typedef rtx *value_type; + typedef rtx rtx_type; + typedef rtunion rtunion_type; + static rtx_type get_rtx (value_type ptr) { return *ptr; } + static value_type get_value (rtx_type &x) { return &x; } +}; +typedef generic_subrtx_iterator subrtx_ptr_iterator; + +#define ALL_BOUNDS rtx_all_subrtx_bounds +#define NONCONST_BOUNDS rtx_nonconst_subrtx_bounds + +/* Use ITER to iterate over const_rtx X and its recursive subrtxes, + using subrtx_iterator::array ARRAY as the storage for the worklist. + ARRAY can be reused for multiple consecutive iterations but shouldn't + be shared by two concurrent iterations. TYPE is ALL if all subrtxes + are of interest or NONCONST if it is safe to ignore subrtxes of + constants. */ +#define FOR_EACH_SUBRTX(ITER, ARRAY, X, TYPE) \ + for (subrtx_iterator ITER (ARRAY, X, TYPE##_BOUNDS); !ITER.at_end (); \ + ITER.next ()) + +/* Like FOR_EACH_SUBRTX, but iterate over subrtxes of an rtx X. */ +#define FOR_EACH_SUBRTX_VAR(ITER, ARRAY, X, TYPE) \ + for (subrtx_var_iterator ITER (ARRAY, X, TYPE##_BOUNDS); !ITER.at_end (); \ + ITER.next ()) + +/* Like FOR_EACH_SUBRTX, but iterate over subrtx pointers of rtx pointer X. + For example, if X is &PATTERN (insn) and the pattern is a SET, iterate + over &PATTERN (insn), &SET_DEST (PATTERN (insn)), etc. */ +#define FOR_EACH_SUBRTX_PTR(ITER, ARRAY, X, TYPE) \ + for (subrtx_ptr_iterator ITER (ARRAY, X, TYPE##_BOUNDS); !ITER.at_end (); \ + ITER.next ()) diff --git a/gcc/rtlanal.c b/gcc/rtlanal.c index 297ca418b06..e6e13a60162 100644 --- a/gcc/rtlanal.c +++ b/gcc/rtlanal.c @@ -37,6 +37,7 @@ along with GCC; see the file COPYING3. If not see #include "tree.h" #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */ #include "addresses.h" +#include "rtl-iter.h" /* Forward declarations */ static void set_of_1 (rtx, const_rtx, void *); @@ -62,6 +63,9 @@ static unsigned int num_sign_bit_copies1 (const_rtx, enum machine_mode, const_rt -1 if a code has no such operand. */ static int non_rtx_starting_operands[NUM_RTX_CODE]; +rtx_subrtx_bound_info rtx_all_subrtx_bounds[NUM_RTX_CODE]; +rtx_subrtx_bound_info rtx_nonconst_subrtx_bounds[NUM_RTX_CODE]; + /* Truncation narrows the mode from SOURCE mode to DESTINATION mode. If TARGET_MODE_REP_EXTENDED (DESTINATION, DESTINATION_REP) is SIGN_EXTEND then while narrowing we also have to enforce the @@ -78,6 +82,93 @@ static int non_rtx_starting_operands[NUM_RTX_CODE]; static unsigned int num_sign_bit_copies_in_rep[MAX_MODE_INT + 1][MAX_MODE_INT + 1]; +/* Store X into index I of ARRAY. ARRAY is known to have at least I + elements. Return the new base of ARRAY. */ + +template +typename T::value_type * +generic_subrtx_iterator ::add_single_to_queue (array_type &array, + value_type *base, + size_t i, value_type x) +{ + if (base == array.stack) + { + if (i < LOCAL_ELEMS) + { + base[i] = x; + return base; + } + gcc_checking_assert (i == LOCAL_ELEMS); + vec_safe_grow (array.heap, i + 1); + base = array.heap->address (); + memcpy (base, array.stack, sizeof (array.stack)); + base[LOCAL_ELEMS] = x; + return base; + } + unsigned int length = array.heap->length (); + if (length > i) + { + gcc_checking_assert (base == array.heap->address ()); + base[i] = x; + return base; + } + else + { + gcc_checking_assert (i == length); + vec_safe_push (array.heap, x); + return array.heap->address (); + } +} + +/* Add the subrtxes of X to worklist ARRAY, starting at END. Return the + number of elements added to the worklist. */ + +template +size_t +generic_subrtx_iterator ::add_subrtxes_to_queue (array_type &array, + value_type *base, + size_t end, rtx_type x) +{ + const char *format = GET_RTX_FORMAT (GET_CODE (x)); + size_t orig_end = end; + for (int i = 0; format[i]; ++i) + if (format[i] == 'e') + { + value_type subx = T::get_value (x->u.fld[i].rt_rtx); + if (__builtin_expect (end < LOCAL_ELEMS, true)) + base[end++] = subx; + else + base = add_single_to_queue (array, base, end++, subx); + } + else if (format[i] == 'E') + { + int length = GET_NUM_ELEM (x->u.fld[i].rt_rtvec); + rtx *vec = x->u.fld[i].rt_rtvec->elem; + if (__builtin_expect (end + length <= LOCAL_ELEMS, true)) + for (int j = 0; j < length; j++) + base[end++] = T::get_value (vec[j]); + else + for (int j = 0; j < length; j++) + base = add_single_to_queue (array, base, end++, + T::get_value (vec[j])); + } + return end - orig_end; +} + +template +void +generic_subrtx_iterator ::free_array (array_type &array) +{ + vec_free (array.heap); +} + +template +const size_t generic_subrtx_iterator ::LOCAL_ELEMS; + +template class generic_subrtx_iterator ; +template class generic_subrtx_iterator ; +template class generic_subrtx_iterator ; + /* Return 1 if the value of X is unstable (would be different at a different point in the program). The frame pointer, arg pointer, etc. are considered stable @@ -5346,8 +5437,42 @@ truncated_to_mode (enum machine_mode mode, const_rtx x) return false; } +/* Return true if RTX code CODE has a single sequence of zero or more + "e" operands and no rtvec operands. Initialize its rtx_all_subrtx_bounds + entry in that case. */ + +static bool +setup_reg_subrtx_bounds (unsigned int code) +{ + const char *format = GET_RTX_FORMAT ((enum rtx_code) code); + unsigned int i = 0; + for (; format[i] != 'e'; ++i) + { + if (!format[i]) + /* No subrtxes. Leave start and count as 0. */ + return true; + if (format[i] == 'E' || format[i] == 'V') + return false; + } + + /* Record the sequence of 'e's. */ + rtx_all_subrtx_bounds[code].start = i; + do + ++i; + while (format[i] == 'e'); + rtx_all_subrtx_bounds[code].count = i - rtx_all_subrtx_bounds[code].start; + /* rtl-iter.h relies on this. */ + gcc_checking_assert (rtx_all_subrtx_bounds[code].count <= 3); + + for (; format[i]; ++i) + if (format[i] == 'E' || format[i] == 'V' || format[i] == 'e') + return false; + + return true; +} + /* Initialize non_rtx_starting_operands, which is used to speed up - for_each_rtx. */ + for_each_rtx, and rtx_all_subrtx_bounds. */ void init_rtlanal (void) { @@ -5357,6 +5482,10 @@ init_rtlanal (void) const char *format = GET_RTX_FORMAT (i); const char *first = strpbrk (format, "eEV"); non_rtx_starting_operands[i] = first ? first - format : -1; + if (!setup_reg_subrtx_bounds (i)) + rtx_all_subrtx_bounds[i].count = UCHAR_MAX; + if (GET_RTX_CLASS (i) != RTX_CONST_OBJ) + rtx_nonconst_subrtx_bounds[i] = rtx_all_subrtx_bounds[i]; } init_num_sign_bit_copies_in_rep (); -- 2.30.2