diff options
Diffstat (limited to 'gcc/rtl-ssa/movement.h')
| -rw-r--r-- | gcc/rtl-ssa/movement.h | 335 |
1 files changed, 335 insertions, 0 deletions
diff --git a/gcc/rtl-ssa/movement.h b/gcc/rtl-ssa/movement.h new file mode 100644 index 0000000..3b0cbf9 --- /dev/null +++ b/gcc/rtl-ssa/movement.h @@ -0,0 +1,335 @@ +// RTL SSA utilities relating to instruction movement -*- 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 { + +// Restrict movement range RANGE so that the instruction is placed later +// than INSN. (The movement range is the range of instructions after which +// an instruction can be placed.) +inline insn_range_info +move_later_than (insn_range_info range, insn_info *insn) +{ + return { later_insn (range.first, insn), range.last }; +} + +// Restrict movement range RANGE so that the instruction is placed no earlier +// than INSN. (The movement range is the range of instructions after which +// an instruction can be placed.) +inline insn_range_info +move_no_earlier_than (insn_range_info range, insn_info *insn) +{ + insn_info *first = later_insn (range.first, insn->prev_nondebug_insn ()); + return { first, range.last }; +} + +// Restrict movement range RANGE so that the instruction is placed no later +// than INSN. (The movement range is the range of instructions after which +// an instruction can be placed.) +inline insn_range_info +move_no_later_than (insn_range_info range, insn_info *insn) +{ + return { range.first, earlier_insn (range.last, insn) }; +} + +// Restrict movement range RANGE so that the instruction is placed earlier +// than INSN. (The movement range is the range of instructions after which +// an instruction can be placed.) +inline insn_range_info +move_earlier_than (insn_range_info range, insn_info *insn) +{ + insn_info *last = earlier_insn (range.last, insn->prev_nondebug_insn ()); + return { range.first, last }; +} + +// Return true if it is possible to insert a new instruction after INSN. +inline bool +can_insert_after (insn_info *insn) +{ + return insn->is_bb_head () || (insn->is_real () && !insn->is_jump ()); +} + +// Try to restrict move range MOVE_RANGE so that it is possible to +// insert INSN after both of the end points. Return true on success, +// otherwise leave MOVE_RANGE in an invalid state. +inline bool +canonicalize_move_range (insn_range_info &move_range, insn_info *insn) +{ + while (move_range.first != insn && !can_insert_after (move_range.first)) + move_range.first = move_range.first->next_nondebug_insn (); + while (move_range.last != insn && !can_insert_after (move_range.last)) + move_range.last = move_range.last->prev_nondebug_insn (); + return bool (move_range); +} + +// Try to restrict movement range MOVE_RANGE of INSN so that it can set +// or clobber REGNO. Assume that if: +// +// - an instruction I2 contains another access A to REGNO; and +// - IGNORE (I2) is true +// +// then either: +// +// - A will be removed; or +// - something will ensure that the new definition of REGNO does not +// interfere with A, without this having to be enforced by I1's move range. +// +// Return true on success, otherwise leave MOVE_RANGE in an invalid state. +// +// This function only works correctly for instructions that remain within +// the same extended basic block. +template<typename IgnorePredicate> +bool +restrict_movement_for_dead_range (insn_range_info &move_range, + unsigned int regno, insn_info *insn, + IgnorePredicate ignore) +{ + // Find a definition at or neighboring INSN. + resource_info resource = full_register (regno); + def_lookup dl = crtl->ssa->find_def (resource, insn); + + def_info *prev = dl.prev_def (); + ebb_info *ebb = insn->ebb (); + if (!prev || prev->ebb () != ebb) + { + // REGNO is not defined or used in EBB before INSN, but it + // might be live on entry. To keep complexity under control, + // handle only these cases: + // + // - If the register is not live on entry to EBB, the register is + // free from the start of EBB to the first definition in EBB. + // + // - Otherwise, if the register is live on entry to BB, refuse + // to allocate the register. We could in principle try to move + // the instruction to later blocks in the EBB, but it's rarely + // worth the effort, and could lead to linear complexity. + // + // - Otherwise, don't allow INSN to move earlier than its current + // block. Again, we could in principle look backwards to find where + // REGNO dies, but it's rarely worth the effort. + bb_info *bb = insn->bb (); + insn_info *limit; + if (!bitmap_bit_p (DF_LR_IN (ebb->first_bb ()->cfg_bb ()), regno)) + limit = ebb->phi_insn (); + else if (bitmap_bit_p (DF_LR_IN (bb->cfg_bb ()), regno)) + return false; + else + limit = bb->head_insn (); + move_range = move_later_than (move_range, limit); + } + else + { + // Stop the instruction moving beyond the previous relevant access + // to REGNO. + access_info *prev_access + = last_access_ignoring (prev, ignore_clobbers::YES, ignore); + if (prev_access) + move_range = move_later_than (move_range, access_insn (prev_access)); + } + + // Stop the instruction moving beyond the next relevant definition of REGNO. + def_info *next = first_def_ignoring (dl.matching_or_next_def (), + ignore_clobbers::YES, ignore); + if (next) + move_range = move_earlier_than (move_range, next->insn ()); + + return canonicalize_move_range (move_range, insn); +} + +// Try to restrict movement range MOVE_RANGE so that it is possible for the +// instruction being moved ("instruction I1") to perform all the definitions +// in DEFS while still preserving dependencies between those definitions +// and surrounding instructions. Assume that if: +// +// - DEFS contains a definition D of resource R; +// - an instruction I2 contains another access A to R; and +// - IGNORE (I2) is true +// +// then either: +// +// - A will be removed; or +// - something will ensure that D and A maintain their current order, +// without this having to be enforced by I1's move range. +// +// Return true on success, otherwise leave MOVE_RANGE in an invalid state. +// +// This function only works correctly for instructions that remain within +// the same extended basic block. +template<typename IgnorePredicate> +bool +restrict_movement_for_defs_ignoring (insn_range_info &move_range, + def_array defs, IgnorePredicate ignore) +{ + for (def_info *def : defs) + { + // If the definition is a clobber, we can move it with respect + // to other clobbers. + // + // ??? We could also do this if a definition and all its uses + // are being moved at once. + bool is_clobber = is_a<clobber_info *> (def); + + // Search back for the first unfiltered use or definition of the + // same resource. + access_info *access; + access = prev_access_ignoring (def, ignore_clobbers (is_clobber), + ignore); + if (access) + move_range = move_later_than (move_range, access_insn (access)); + + // Search forward for the first unfiltered use of DEF, + // or the first unfiltered definition that follows DEF. + // + // We don't need to consider uses of following definitions, since + // if IGNORE (D->insn ()) is true for some definition D, the caller + // is guarantees that either + // + // - D will be removed, and thus its uses will be removed; or + // - D will occur after DEF, and thus D's uses will also occur + // after DEF. + // + // This is purely a simplification: we could also process D's uses, + // but we don't need to. + access = next_access_ignoring (def, ignore_clobbers (is_clobber), + ignore); + if (access) + move_range = move_earlier_than (move_range, access_insn (access)); + + // If DEF sets a hard register, take any call clobbers + // into account. + unsigned int regno = def->regno (); + if (!HARD_REGISTER_NUM_P (regno) || is_clobber) + continue; + + ebb_info *ebb = def->ebb (); + for (ebb_call_clobbers_info *call_group : ebb->call_clobbers ()) + { + if (!call_group->clobbers (def->resource ())) + continue; + + // Exit now if we've already failed, and if the splay accesses + // below would be wasted work. + if (!move_range) + return false; + + insn_info *insn; + insn = prev_call_clobbers_ignoring (*call_group, def->insn (), + ignore); + if (insn) + move_range = move_later_than (move_range, insn); + + insn = next_call_clobbers_ignoring (*call_group, def->insn (), + ignore); + if (insn) + move_range = move_earlier_than (move_range, insn); + } + } + + // Make sure that we don't move stores between basic blocks, since we + // don't have enough information to tell whether it's safe. + if (def_info *def = memory_access (defs)) + { + move_range = move_later_than (move_range, def->bb ()->head_insn ()); + move_range = move_earlier_than (move_range, def->bb ()->end_insn ()); + } + + return bool (move_range); +} + +// Like restrict_movement_for_defs_ignoring, but for the uses in USES. +template<typename IgnorePredicate> +bool +restrict_movement_for_uses_ignoring (insn_range_info &move_range, + use_array uses, IgnorePredicate ignore) +{ + for (const use_info *use : uses) + { + // Ignore uses of undefined values. + set_info *set = use->def (); + if (!set) + continue; + + // Ignore uses by debug instructions. Debug instructions are + // never supposed to move, and uses by debug instructions are + // never supposed to be transferred elsewhere, so we know that + // the caller must be changing the uses on the debug instruction + // and checking whether all new uses are available at the debug + // instruction's original location. + if (use->is_in_debug_insn ()) + continue; + + // If the used value is defined by an instruction I2 for which + // IGNORE (I2) is true, the caller guarantees that I2 will occur + // before change.insn (). Otherwise, make sure that the use occurs + // after the definition. + insn_info *insn = set->insn (); + if (!ignore (insn)) + move_range = move_later_than (move_range, insn); + + // Search forward for the first unfiltered definition that follows SET. + // + // We don't need to consider the uses of these definitions, since + // if IGNORE (D->insn ()) is true for some definition D, the caller + // is guarantees that either + // + // - D will be removed, and thus its uses will be removed; or + // - D will occur after USE, and thus D's uses will also occur + // after USE. + // + // This is purely a simplification: we could also process D's uses, + // but we don't need to. + def_info *def; + def = first_def_ignoring (set->next_def (), ignore_clobbers::NO, + ignore); + if (def) + move_range = move_earlier_than (move_range, def->insn ()); + + // If USE uses a hard register, take any call clobbers into account too. + // SET will necessarily occur after any previous call clobber, so we + // only need to check for later clobbers. + unsigned int regno = use->regno (); + if (!HARD_REGISTER_NUM_P (regno)) + continue; + + ebb_info *ebb = use->ebb (); + for (ebb_call_clobbers_info *call_group : ebb->call_clobbers ()) + { + if (!call_group->clobbers (use->resource ())) + continue; + + if (!move_range) + return false; + + insn_info *insn = next_call_clobbers_ignoring (*call_group, + use->insn (), ignore); + if (insn) + move_range = move_earlier_than (move_range, insn); + } + } + + // Make sure that we don't move loads into an earlier basic block. + // + // ??? It would be good to relax this for loads that can be safely + // speculated. + if (use_info *use = memory_access (uses)) + move_range = move_later_than (move_range, use->bb ()->head_insn ()); + + return bool (move_range); +} + +} |