blob: e6b5d7eca6eb93f38f60c5b14adc24dfddd17de5 [file] [log] [blame]
// Access-related utilities for RTL SSA -*- C++ -*-
// Copyright (C) 2020-2021 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));
}
}