diff options
Diffstat (limited to 'gcc/rtl-ssa/access-utils.h')
| -rw-r--r-- | gcc/rtl-ssa/access-utils.h | 553 |
1 files changed, 553 insertions, 0 deletions
diff --git a/gcc/rtl-ssa/access-utils.h b/gcc/rtl-ssa/access-utils.h new file mode 100644 index 0000000..634f99b --- /dev/null +++ b/gcc/rtl-ssa/access-utils.h @@ -0,0 +1,553 @@ +// Access-related utilities for RTL SSA -*- C++ -*- +// Copyright (C) 2020 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/>. + +namespace rtl_ssa { + +// Return a referene to the whole of register REGNO. +inline resource_info +full_register (unsigned int regno) +{ + return { GET_MODE (regno_reg_rtx[regno]), regno }; +} + +// Return true if sorted array ACCESSES includes an access to hard registers. +inline bool +accesses_include_hard_registers (const access_array &accesses) +{ + return accesses.size () && HARD_REGISTER_NUM_P (accesses.front ()->regno ()); +} + +// Return true if sorted array ACCESSES includes an access to memory. +inline bool +accesses_include_memory (const access_array &accesses) +{ + return accesses.size () && accesses.back ()->is_mem (); +} + +// If sorted array ACCESSES includes an access to memory, return the access, +// otherwise return null. +template<typename T> +inline auto +memory_access (T accesses) -> decltype (accesses[0]) +{ + if (accesses.size () && accesses.back ()->is_mem ()) + return accesses.back (); + return nullptr; +} + +// If sorted array ACCESSES includes a reference to REGNO, return the +// access, otherwise return null. +template<typename T> +inline auto +find_access (T accesses, unsigned int regno) -> decltype (accesses[0]) +{ + unsigned int start = 0; + unsigned int end = accesses.size (); + while (start < end) + { + unsigned int mid = (start + end) / 2; + unsigned int found = accesses[mid]->regno (); + if (found == regno) + return accesses[mid]; + if (found < regno) + start = mid + 1; + else + end = mid; + } + return nullptr; +} + +// If sorted array ACCESSES includes a reference to REGNO, return the +// index of the access, otherwise return -1. +inline int +find_access_index (access_array accesses, unsigned int regno) +{ + unsigned int start = 0; + unsigned int end = accesses.size (); + while (start < end) + { + unsigned int mid = (start + end) / 2; + unsigned int found = accesses[mid]->regno (); + if (found == regno) + return mid; + if (found < regno) + start = mid + 1; + else + end = mid; + } + return -1; +} + +// If ACCESS is a set whose result is used by at least one instruction, +// return the access as a set_info, otherwise return null. +inline const set_info * +set_with_nondebug_insn_uses (const access_info *access) +{ + if (access->is_set_with_nondebug_insn_uses ()) + // No need for as_a; this test is just as definitive. + return static_cast<const set_info *> (access); + return nullptr; +} + +// A non-const version of the above. +inline set_info * +set_with_nondebug_insn_uses (access_info *access) +{ + if (access->is_set_with_nondebug_insn_uses ()) + return static_cast<set_info *> (access); + return nullptr; +} + +// Return true if SET is the only set of SET->resource () and if it +// dominates all uses (excluding uses of SET->resource () at points +// where SET->resource () is always undefined). +inline bool +is_single_dominating_def (const set_info *set) +{ + return set->is_first_def () && set->is_last_def (); +} + +// SET is known to be available on entry to BB. Return true if it is +// also available on exit from BB. (The value might or might not be live.) +inline bool +remains_available_on_exit (const set_info *set, bb_info *bb) +{ + return (set->is_last_def () + || *set->next_def ()->insn () > *bb->end_insn ()); +} + +// ACCESS is known to be associated with an instruction rather than +// a phi node. Return which instruction that is. +inline insn_info * +access_insn (const access_info *access) +{ + // In release builds this function reduces to a single pointer reference. + if (auto *def = dyn_cast<const def_info *> (access)) + return def->insn (); + return as_a<const use_info *> (access)->insn (); +} + +// If ACCESS records a use, return the value that it uses. If ACCESS records +// a set, return that set. If ACCESS records a clobber, return null. +inline const set_info * +access_value (const access_info *access) +{ + if (!access) + return nullptr; + + if (auto *use = dyn_cast<const use_info *> (access)) + return use->def (); + + return dyn_cast<const set_info *> (access); +} + +// A non-const version of the above. +inline set_info * +access_value (access_info *access) +{ + auto *const_access = const_cast<const access_info *> (access); + return const_cast<set_info *> (access_value (const_access)); +} + +// If ACCESS is a degenerate phi, return the set_info that defines its input, +// otherwise return ACCESS itself. +template<typename T> +inline const T * +look_through_degenerate_phi (const T *access) +{ + if (auto *phi = dyn_cast<const phi_info *> (access)) + if (phi->is_degenerate ()) + return phi->input_value (0); + return access; +} + +// A non-const version of the above. +template<typename T> +inline T * +look_through_degenerate_phi (T *access) +{ + auto *const_access = const_cast<const T *> (access); + return const_cast<T *> (look_through_degenerate_phi (const_access)); +} + +// If CLOBBER is in a group, return the first clobber in the group, +// otherwise return CLOBBER itself. +inline clobber_info * +first_clobber_in_group (clobber_info *clobber) +{ + if (clobber->is_in_group ()) + return clobber->group ()->first_clobber (); + return clobber; +} + +// If CLOBBER is in a group, return the last clobber in the group, +// otherwise return CLOBBER itself. +inline clobber_info * +last_clobber_in_group (clobber_info *clobber) +{ + if (clobber->is_in_group ()) + return clobber->group ()->last_clobber (); + return clobber; +} + +// If DEF is a clobber in a group, return the containing group, +// otherwise return DEF. +inline def_mux +clobber_group_or_single_def (def_info *def) +{ + if (auto *clobber = dyn_cast<clobber_info *> (def)) + if (clobber->is_in_group ()) + return clobber->group (); + return def; +} + +// Return the first definition associated with NODE. If NODE holds +// a single set, the result is that set. If NODE holds a clobber_group, +// the result is the first clobber in the group. +inline def_info * +first_def (def_node *node) +{ + return node->first_def (); +} + +// Likewise for something that is either a node or a single definition. +inline def_info * +first_def (def_mux mux) +{ + return mux.first_def (); +} + +// Return the last definition associated with NODE. If NODE holds +// a single set, the result is that set. If NODE holds a clobber_group, +// the result is the last clobber in the group. +inline def_info * +last_def (def_node *node) +{ + if (auto *group = dyn_cast<clobber_group *> (node)) + return group->last_clobber (); + return node->first_def (); +} + +// Likewise for something that is either a node or a single definition. +inline def_info * +last_def (def_mux mux) +{ + return mux.last_def (); +} + +int lookup_use (splay_tree<use_info *> &, insn_info *); +int lookup_def (def_splay_tree &, insn_info *); +int lookup_clobber (clobber_tree &, insn_info *); +int lookup_call_clobbers (insn_call_clobbers_tree &, insn_info *); + +// Search backwards from immediately before INSN for the first instruction +// recorded in TREE, ignoring any instruction I for which IGNORE (I) is true. +// Return null if no such instruction exists. +template<typename IgnorePredicate> +insn_info * +prev_call_clobbers_ignoring (insn_call_clobbers_tree &tree, insn_info *insn, + IgnorePredicate ignore) +{ + if (!tree) + return nullptr; + + int comparison = lookup_call_clobbers (tree, insn); + while (comparison <= 0 || ignore (tree->insn ())) + { + if (!tree.splay_prev_node ()) + return nullptr; + + comparison = 1; + } + return tree->insn (); +} + +// Search forwards from immediately after INSN for the first instruction +// recorded in TREE, ignoring any instruction I for which IGNORE (I) is true. +// Return null if no such instruction exists. +template<typename IgnorePredicate> +insn_info * +next_call_clobbers_ignoring (insn_call_clobbers_tree &tree, insn_info *insn, + IgnorePredicate ignore) +{ + if (!tree) + return nullptr; + + int comparison = lookup_call_clobbers (tree, insn); + while (comparison >= 0 || ignore (tree->insn ())) + { + if (!tree.splay_next_node ()) + return nullptr; + + comparison = -1; + } + return tree->insn (); +} + +// If ACCESS is a set, return the first use of ACCESS by a nondebug insn I +// for which IGNORE (I) is false. Return null if ACCESS is not a set or if +// no such use exists. +template<typename IgnorePredicate> +inline use_info * +first_nondebug_insn_use_ignoring (const access_info *access, + IgnorePredicate ignore) +{ + if (const set_info *set = set_with_nondebug_insn_uses (access)) + { + // Written this way to emphasize to the compiler that first_use + // must be nonnull in this situation. + use_info *use = set->first_use (); + do + { + if (!ignore (use->insn ())) + return use; + use = use->next_nondebug_insn_use (); + } + while (use); + } + return nullptr; +} + +// If ACCESS is a set, return the last use of ACCESS by a nondebug insn I for +// which IGNORE (I) is false. Return null if ACCESS is not a set or if no +// such use exists. +template<typename IgnorePredicate> +inline use_info * +last_nondebug_insn_use_ignoring (const access_info *access, + IgnorePredicate ignore) +{ + if (const set_info *set = set_with_nondebug_insn_uses (access)) + { + // Written this way to emphasize to the compiler that + // last_nondebug_insn_use must be nonnull in this situation. + use_info *use = set->last_nondebug_insn_use (); + do + { + if (!ignore (use->insn ())) + return use; + use = use->prev_use (); + } + while (use); + } + return nullptr; +} + +// If DEF is null, return null. +// +// Otherwise, search backwards for an access to DEF->resource (), starting at +// the end of DEF's live range. Ignore clobbers if IGNORE_CLOBBERS_SETTING +// is YES, otherwise treat them like any other access. Also ignore any +// access A for which IGNORE (access_insn (A)) is true. +// +// Thus if DEF is a set that is used by nondebug insns, the first access +// that the function considers is the last such use of the set. Otherwise, +// the first access that the function considers is DEF itself. +// +// Return the access found, or null if there is no access that meets +// the criteria. +// +// Note that this function does not consider separately-recorded call clobbers, +// although such clobbers are only relevant if IGNORE_CLOBBERS_SETTING is NO. +template<typename IgnorePredicate> +access_info * +last_access_ignoring (def_info *def, ignore_clobbers ignore_clobbers_setting, + IgnorePredicate ignore) +{ + while (def) + { + auto *clobber = dyn_cast<clobber_info *> (def); + if (clobber && ignore_clobbers_setting == ignore_clobbers::YES) + def = first_clobber_in_group (clobber); + else + { + if (use_info *use = last_nondebug_insn_use_ignoring (def, ignore)) + return use; + + insn_info *insn = def->insn (); + if (!ignore (insn)) + return def; + } + def = def->prev_def (); + } + return nullptr; +} + +// Search backwards for an access to DEF->resource (), starting +// immediately before the point at which DEF occurs. Ignore clobbers +// if IGNORE_CLOBBERS_SETTING is YES, otherwise treat them like any other +// access. Also ignore any access A for which IGNORE (access_insn (A)) +// is true. +// +// Thus if DEF->insn () uses DEF->resource (), that use is the first access +// that the function considers, since an instruction's uses occur strictly +// before its definitions. +// +// Note that this function does not consider separately-recorded call clobbers, +// although such clobbers are only relevant if IGNORE_CLOBBERS_SETTING is NO. +template<typename IgnorePredicate> +inline access_info * +prev_access_ignoring (def_info *def, ignore_clobbers ignore_clobbers_setting, + IgnorePredicate ignore) +{ + return last_access_ignoring (def->prev_def (), ignore_clobbers_setting, + ignore); +} + +// If DEF is null, return null. +// +// Otherwise, search forwards for a definition of DEF->resource (), +// starting at DEF itself. Ignore clobbers if IGNORE_CLOBBERS_SETTING +// is YES, otherwise treat them like any other access. Also ignore any +// definition D for which IGNORE (D->insn ()) is true. +// +// Return the definition found, or null if there is no access that meets +// the criteria. +// +// Note that this function does not consider separately-recorded call clobbers, +// although such clobbers are only relevant if IGNORE_CLOBBERS_SETTING is NO. +template<typename IgnorePredicate> +def_info * +first_def_ignoring (def_info *def, ignore_clobbers ignore_clobbers_setting, + IgnorePredicate ignore) +{ + while (def) + { + auto *clobber = dyn_cast<clobber_info *> (def); + if (clobber && ignore_clobbers_setting == ignore_clobbers::YES) + def = last_clobber_in_group (clobber); + else if (!ignore (def->insn ())) + return def; + + def = def->next_def (); + } + return nullptr; +} + +// Search forwards for the next access to DEF->resource (), +// starting immediately after DEF's instruction. Ignore clobbers if +// IGNORE_CLOBBERS_SETTING is YES, otherwise treat them like any other access. +// Also ignore any access A for which IGNORE (access_insn (A)) is true; +// in this context, ignoring a set includes ignoring all uses of the set. +// +// Thus if DEF is a set with uses by nondebug insns, the first access that the +// function considers is the first such use of the set. +// +// Return the access found, or null if there is no access that meets the +// criteria. +// +// Note that this function does not consider separately-recorded call clobbers, +// although such clobbers are only relevant if IGNORE_CLOBBERS_SETTING is NO. +template<typename IgnorePredicate> +access_info * +next_access_ignoring (def_info *def, ignore_clobbers ignore_clobbers_setting, + IgnorePredicate ignore) +{ + if (use_info *use = first_nondebug_insn_use_ignoring (def, ignore)) + return use; + + return first_def_ignoring (def->next_def (), ignore_clobbers_setting, + ignore); +} + +// Return true if ACCESS1 should before ACCESS2 in an access_array. +inline bool +compare_access_infos (const access_info *access1, const access_info *access2) +{ + gcc_checking_assert (access1 == access2 + || access1->regno () != access2->regno ()); + return access1->regno () < access2->regno (); +} + +// Sort [BEGIN, END) into ascending regno order. The sequence must have +// at most one access to a given a regno. +inline void +sort_accesses (access_info **begin, access_info **end) +{ + auto count = end - begin; + if (count <= 1) + return; + + if (count == 2) + { + gcc_checking_assert (begin[0]->regno () != begin[1]->regno ()); + if (begin[0]->regno () > begin[1]->regno ()) + std::swap (begin[0], begin[1]); + return; + } + + std::sort (begin, end, compare_access_infos); +} + +// Sort the accesses in CONTAINER, which contains pointers to access_infos. +template<typename T> +inline void +sort_accesses (T &container) +{ + return sort_accesses (container.begin (), container.end ()); +} + +// The underlying non-template implementation of merge_access_arrays. +access_array merge_access_arrays_base (obstack_watermark &, access_array, + access_array); +// Merge access arrays ACCESSES1 and ACCESSES2, including the allocation +// in the area governed by WATERMARK. Return an invalid access_array if +// ACCESSES1 and ACCESSES2 contain conflicting accesses to the same resource. +// +// T can be an access_array, a def_array or a use_array. +template<typename T> +inline T +merge_access_arrays (obstack_watermark &watermark, T accesses1, T accesses2) +{ + return T (merge_access_arrays_base (watermark, accesses1, accesses2)); +} + +// The underlying non-template implementation of insert_access. +access_array insert_access_base (obstack_watermark &, access_info *, + access_array); + +// Return a new access_array that contains the result of inserting ACCESS1 +// into sorted access array ACCESSES2. Allocate the returned array in the +// area governed by WATERMARK. Return an invalid access_array if ACCESSES2 +// contains a conflicting access to the same resource as ACCESS1. +// +// T can be an access_array, a def_array or a use_array. +template<typename T> +inline T +insert_access (obstack_watermark &watermark, + typename T::value_type access1, T accesses2) +{ + return T (insert_access_base (watermark, access1, accesses2)); +} + +// The underlying non-template implementation of remove_note_accesses. +access_array remove_note_accesses_base (obstack_watermark &, access_array); + +// If ACCESSES contains accesses that only occur in notes, return a new +// array without such accesses, allocating it in the area governed by +// WATERMARK. Return ACCESSES itself otherwise. +// +// T can be an access_array, a def_array or a use_array. +template<typename T> +inline T +remove_note_accesses (obstack_watermark &watermark, T accesses) +{ + return T (remove_note_accesses_base (watermark, accesses)); +} + +} |