#include "config.h"#include "system.h"#include "coretypes.h"#include "tree-pass.h"#include "backend.h"#include "tree.h"#include "gimple.h"#include "ssa.h"#include "fold-const.h"#include "tree-cfg.h"#include "tree-ssa.h"#include "tree-ssa-loop-niter.h"#include "tree-ssa-loop.h"#include "tree-ssa-loop-manip.h"#include "cfgloop.h"#include "tree-scalar-evolution.h"#include "gimple-iterator.h"#include "cfghooks.h"#include "tree-data-ref.h"#include "tree-ssa-loop-ivopts.h"#include "tree-vectorizer.h"#include "tree-ssa-sccvn.h"#include "tree-cfgcleanup.h"
Functions | |
| static void | merge_loop_tree (class loop *loop, class loop *old) |
| static bool | bb_prevents_fusion_p (basic_block bb) |
| static bool | unroll_jam_possible_p (class loop *outer, class loop *loop) |
| static void | fuse_loops (class loop *loop) |
| static bool | any_access_function_variant_p (const struct data_reference *a, const class loop *loop_nest) |
| static bool | adjust_unroll_factor (class loop *inner, struct data_dependence_relation *ddr, unsigned *unroll, unsigned *profit_unroll, unsigned *removed) |
| static unsigned int | tree_loop_unroll_and_jam (void) |
| gimple_opt_pass * | make_pass_loop_jam (gcc::context *ctxt) |
Function Documentation
◆ adjust_unroll_factor()
|
static |
Returns true if the distance in DDR can be determined and adjusts the unroll factor in *UNROLL to make unrolling valid for that distance. Otherwise return false. DDR is with respect to the outer loop of INNER. If this data dep can lead to a removed memory reference, increment *REMOVED and adjust *PROFIT_UNROLL to be the necessary unroll factor for this to happen.
References any_access_function_variant_p(), chrec_known, DDR_A, DDR_ARE_DEPENDENT, DDR_B, DDR_DIST_VECTS, DDR_NB_LOOPS, DDR_NUM_DIST_VECTS, DR_IS_READ, FOR_EACH_VEC_ELT, gcc_unreachable, ggc_alloc(), i, loop::inner, lambda_vector_lexico_pos(), lambda_vector_zerop(), MAX, and loop::unroll.
Referenced by tree_loop_unroll_and_jam().
◆ any_access_function_variant_p()
|
static |
Return true if any of the access functions for dataref A isn't invariant with respect to loop LOOP_NEST.
References a, DR_ACCESS_FNS, evolution_function_is_invariant_p(), and loop::num.
Referenced by adjust_unroll_factor().
◆ bb_prevents_fusion_p()
|
static |
BB is part of the outer loop of an unroll-and-jam situation. Check if any statements therein would prevent the transformation.
References g, gimple_has_side_effects(), gimple_vdef(), gsi_end_p(), gsi_next(), gsi_start_bb(), and gsi_stmt().
Referenced by unroll_jam_possible_p().
◆ fuse_loops()
Fuse LOOP with all further neighbors. The loops are expected to be in appropriate form.
References add_phi_arg(), delete_basic_block(), delete_loop(), EDGE_COUNT, flush_pending_stmts(), gcc_assert, ggc_alloc(), gimple_location(), gimple_phi_result(), gsi_end_p(), gsi_next(), gsi_start_phis(), loop::header, loop::latch, loop_latch_edge(), merge_loop_tree(), loop::next, NULL, loop::num_nodes, basic_block_def::preds, redirect_edge_and_branch(), remove_branch(), single_pred_edge(), and virtual_operand_p().
Referenced by tree_loop_unroll_and_jam().
◆ make_pass_loop_jam()
| gimple_opt_pass * make_pass_loop_jam | ( | gcc::context * | ctxt | ) |
References ggc_alloc().
◆ merge_loop_tree()
Loop unroll-and-jam. Copyright (C) 2017-2024 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/>.
Unroll and Jam transformation
This is a combination of two transformations, where the second
is not always valid. It's applicable if a loop nest has redundancies
over the iterations of an outer loop while not having that with
an inner loop.
Given this nest:
for (i) {
for (j) {
B(i,j)
}
}
first unroll:
for (i by 2) {
for (j) {
B(i,j)
}
for (j) {
B(i+1,j)
}
}
then fuse the two adjacent inner loops resulting from that:
for (i by 2) {
for (j) {
B(i,j)
B(i+1,j)
}
}
As the order of evaluations of the body B changes this is valid
only in certain situations: all distance vectors need to be forward.
Additionally if there are multiple induction variables than just
a counting control IV (j above) we can also deal with some situations.
The validity is checked by unroll_jam_possible_p, and the data-dep
testing below.
A trivial example where the fusion is wrong would be when
B(i,j) == x[j-1] = x[j];
for (i by 2) {
for (j) {
x[j-1] = x[j];
}
for (j) {
x[j-1] = x[j];
}
} effect: move content to front by two elements
-->
for (i by 2) {
for (j) {
x[j-1] = x[j];
x[j-1] = x[j];
}
} effect: move content to front by one element
Modify the loop tree for the fact that all code once belonging to the OLD loop or the outer loop of OLD now is inside LOOP.
References add_bb_to_loop(), cfun, flow_loop_tree_node_add(), flow_loop_tree_node_remove(), FOR_EACH_EDGE, free(), get_loop_body_with_size(), ggc_alloc(), i, loop_depth(), basic_block_def::loop_father, loop_outer(), n_basic_blocks_for_fn, loop::num_nodes, remove_bb_from_loops(), and rescan_loop_exit().
Referenced by fuse_loops().
◆ tree_loop_unroll_and_jam()
Main entry point for the unroll-and-jam transformation described above.
References adjust_unroll_factor(), bitmap_set_bit, can_unroll_loop_p(), CDI_DOMINATORS, cfun, chrec_dont_know, chrec_known, cleanup_tree_cfg(), compute_data_dependences_for_loop(), DDR_A, DDR_ARE_DEPENDENT, DDR_B, do_rpo_vn(), DR_ACCESS_FNS, DR_IS_WRITE, dump_data_dependence_relations(), dump_enabled_p(), dump_file, dump_flags, dump_printf_loc(), find_loop_location(), FOR_EACH_VEC_ELT, free_data_refs(), free_dependence_relations(), free_dominance_info(), free_original_copy_tables(), fuse_loops(), gcc_assert, ggc_alloc(), i, initialize_original_copy_tables(), loop::inner, is_empty(), LI_ONLY_INNERMOST, loop_depth(), loop_outer(), loop_preheader_edge(), MAX, MSG_OPTIMIZED_LOCATIONS, NULL, optimize_loop_nest_for_size_p(), rewrite_into_loop_closed_ssa(), scev_initialized_p(), scev_reset(), single_exit(), TDF_DETAILS, todo, TODO_cleanup_cfg, tree_unroll_loop(), unroll_jam_possible_p(), and vNULL.
◆ unroll_jam_possible_p()
Given an inner loop LOOP (of some OUTER loop) determine if we can safely fuse copies of it (generated by outer unrolling). If so return true, otherwise return false.
References iv::base, bb_prevents_fusion_p(), CDI_DOMINATORS, cfun, dominated_by_p(), empty_block_p(), expr_invariant_in_loop_p(), flow_bb_inside_loop_p(), FOR_EACH_IMM_USE_FAST, free(), get_loop_body_with_size(), ggc_alloc(), gimple_bb(), gimple_phi_result(), gsi_end_p(), gsi_next(), gsi_start_phis(), loop::header, i, loop::inner, integer_zerop(), is_gimple_debug(), loop::latch, loop_exits_from_bb_p(), n_basic_blocks_for_fn, loop::next, tree_niter_desc::niter, number_of_iterations_exit(), gphi_iterator::phi(), simple_iv(), single_exit(), iv::step, USE_STMT, and virtual_operand_p().
Referenced by tree_loop_unroll_and_jam().
