#include "config.h"#include "system.h"#include "coretypes.h"#include "backend.h"#include "tree.h"#include "gimple.h"#include "tree-pass.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 "tree-into-ssa.h"#include "tree-inline.h"#include "tree-cfgcleanup.h"#include "cfgloop.h"#include "tree-scalar-evolution.h"#include "gimple-iterator.h"#include "gimple-pretty-print.h"#include "cfghooks.h"#include "gimple-fold.h"#include "gimplify-me.h"#include "print-tree.h"#include "value-query.h"#include "sreal.h"
Data Structures | |
| class | split_info |
Function Documentation
◆ branch_removable_p()
|
static |
Determine when conditional statement never transfers execution to one of its branch, whether we can remove the branch's leading basic block (BRANCH_BB) and those basic blocks dominated by BRANCH_BB.
References CDI_DOMINATORS, dominated_by_p(), FOR_EACH_EDGE, ggc_alloc(), and single_pred_p().
Referenced by get_cond_invariant_branch().
◆ compute_added_num_insns()
|
static |
Calculate increased code size measured by estimated insn number if applying loop split upon certain branch (BRANCH_EDGE) of a conditional statement.
References hash_set< KeyId, Lazy, Traits >::add(), loop::aux, bb_seq(), CDI_DOMINATORS, hash_set< KeyId, Lazy, Traits >::contains(), dominated_by_p(), EDGE_SUCC, eni_size_weights, estimate_num_insns(), estimate_num_insns_seq(), flow_bb_inside_loop_p(), FOR_EACH_IMM_USE_FAST, FOR_EACH_PHI_OR_STMT_USE, gcc_assert, ggc_alloc(), gimple_bb(), i, is_gimple_debug(), last_nondebug_stmt(), NULL, loop::num_nodes, SSA_NAME_DEF_STMT, SSA_NAME_IS_DEFAULT_DEF, SSA_OP_USE, TREE_CODE, USE_FROM_PTR, USE_STMT, and worklist.
Referenced by get_cond_branch_to_split_loop().
◆ compute_new_first_bound()
|
static |
This returns the new bound for iterations given the original iteration
space in NITER, an arbitrary new bound BORDER, assumed to be some
comparison value with a different IV, the initial value GUARD_INIT of
that other IV, and the comparison code GUARD_CODE that compares
that other IV with BORDER. We return an SSA name, and place any
necessary statements for that computation into *STMTS.
For example for such a loop:
for (i = beg, j = guard_init; i < end; i++, j++)
if (j < border) // this is supposed to be true/false
...
we want to return a new bound (on j) that makes the loop iterate
as long as the condition j < border stays true. We also don't want
to iterate more often than the original loop, so we have to introduce
some cut-off as well (via min/max), effectively resulting in:
newend = min (end+guard_init-beg, border)
for (i = beg; j = guard_init; j < newend; i++, j++)
if (j < c)
...
Depending on the direction of the IVs and if the exit tests
are strict or non-strict we need to use MIN or MAX,
and add or subtract 1. This routine computes newend above.
References affine_iv::base, tree_niter_desc::bound, build_int_cst(), tree_niter_desc::cmp, tree_niter_desc::control, end(), force_gimple_operand(), gcc_assert, ggc_alloc(), gimple_build(), gimple_convert(), gimple_seq_add_seq_without_update(), NULL_TREE, POINTER_TYPE_P, sizetype, affine_iv::step, and TREE_TYPE.
Referenced by split_loop().
◆ connect_loop_phis()
This function updates the SSA form after connect_loops made a new edge NEW_E leading from LOOP1 exit to LOOP2 (via in intermediate conditional). I.e. the second loop can now be entered either via the original entry or via NEW_E, so the entry values of LOOP2 phi nodes are either the original ones or those at the exit of LOOP1. Insert new phi nodes in LOOP2 pre-header reflecting this. The loops need to fulfill easy_exit_values().
References add_phi_arg(), copy_ssa_name(), create_phi_node(), EDGE_PRED, gcc_assert, ggc_alloc(), gsi_end_p(), gsi_next(), gsi_start_phis(), loop_latch_edge(), loop_preheader_edge(), make_temp_ssa_name(), loop::next, NULL, operand_equal_for_phi_arg_p(), PHI_ARG_DEF_FROM_EDGE, PHI_ARG_DEF_PTR_FROM_EDGE, SET_USE, TREE_CODE, TREE_TYPE, UNKNOWN_LOCATION, USE_FROM_PTR, and useless_type_conversion_p().
Referenced by do_split_loop_on_cond(), and split_loop().
◆ connect_loops()
The two loops LOOP1 and LOOP2 were just created by loop versioning,
they are still equivalent and placed in two arms of a diamond, like so:
.------if (cond)------.
v v
pre1 pre2
| |
.--->h1 h2<----.
| | | |
| ex1---. .---ex2 |
| / | | \ |
'---l1 X | l2---'
| |
| |
'--->join<---'
This function transforms the program such that LOOP1 is conditionally
falling through to LOOP2, or skipping it. This is done by splitting
the ex1->join edge at X in the diagram above, and inserting a condition
whose one arm goes to pre2, resulting in this situation:
.------if (cond)------.
v v
pre1 .---------->pre2
| | |
.--->h1 | h2<----.
| | | | |
| ex1---. | .---ex2 |
| / v | | \ |
'---l1 skip---' | l2---'
| |
| |
'--->join<---'
The condition used is the exit condition of LOOP1, which effectively means
that when the first loop exits (for whatever reason) but the real original
exit expression is still false the second loop will be entered.
The function returns the new edge cond->pre2.
This doesn't update the SSA form, see connect_loop_phis for that.
References EDGE_SUCC, ggc_alloc(), gimple_build_cond(), gimple_cond_code(), gimple_cond_lhs(), gimple_cond_rhs(), gsi_insert_after(), gsi_last_bb(), GSI_NEW_STMT, loop_preheader_edge(), make_edge(), NULL_TREE, single_exit(), split_edge(), and profile_probability::very_likely().
Referenced by split_loop().
◆ control_dep_semi_invariant_p()
|
static |
Check whether conditional predicates that BB is control-dependent on, are semi-invariant in LOOP. Basic blocks dominated by SKIP_HEAD (if non-NULL), are excluded from LOOP. Semi-invariant state of checked statement is cached in hash map STMT_STAT.
References find_control_dep_blocks(), ggc_alloc(), gsi_last_bb(), last, and stmt_semi_invariant_p_1().
Referenced by stmt_semi_invariant_p_1().
◆ do_split_loop_on_cond()
Given a loop (LOOP1) with a loop-invariant branch (INVAR_BRANCH) of some
conditional statement, perform loop split transformation illustrated
as the following graph.
.-------T------ if (true) ------F------.
| .---------------. |
| | | |
v | v v
pre-header | pre-header
| .------------. | | .------------.
| | | | | | |
| v | | | v |
header | | header |
| | | | |
.--- if (cond) ---. | | .--- if (true) ---. |
| | | | | | |
invariant | | | invariant | |
| | | | | | |
'---T--->.<---F---' | | '---T--->.<---F---' |
| | / | |
stmts | / stmts |
| F T | |
/ \ | / / \ |
.-------* * [ if (cond) ] .-------* * |
| | | | | |
| latch | | latch |
| | | | | |
| '------------' | '------------'
'------------------------. .-----------'
loop1 | | loop2
v v
exits
In the graph, loop1 represents the part derived from original one, and
loop2 is duplicated using loop_version (), which corresponds to the part
of original one being splitted out. In original latch edge of loop1, we
insert a new conditional statement duplicated from the semi-invariant cond,
and one of its branch goes back to loop1 header as a latch edge, and the
other branch goes to loop2 pre-header as an entry edge. And also in loop2,
we abandon the variant branch of the conditional statement by setting a
constant bool condition, based on which branch is semi-invariant.
References profile_probability::always(), boolean_true_node, connect_loop_phis(), dump_enabled_p(), dump_printf_loc(), extract_true_false_edges_from_block(), fix_loop_bb_probability(), free_original_copy_tables(), gcc_assert, get_bb_copy(), ggc_alloc(), gimple_build_cond(), gimple_cond_code(), gimple_cond_lhs(), gimple_cond_make_false(), gimple_cond_make_true(), gimple_cond_rhs(), gsi_insert_after(), gsi_last_bb(), GSI_NEW_STMT, initialize_original_copy_tables(), loop_latch_edge(), loop_preheader_edge(), loop_version(), make_edge(), MSG_OPTIMIZED_LOCATIONS, NULL, NULL_TREE, single_pred_edge(), single_succ_edge(), split_edge(), and update_stmt().
Referenced by split_loop_on_cond().
◆ easy_exit_values()
Returns true if the exit values of all loop phi nodes can be determined easily (i.e. that connect_loop_phis can determine them).
References CDI_DOMINATORS, dominated_by_p(), gimple_bb(), gsi_end_p(), gsi_next(), gsi_start_phis(), loop::header, loop::latch, loop_latch_edge(), loop::next, gphi_iterator::phi(), PHI_ARG_DEF_FROM_EDGE, single_exit(), SSA_NAME_DEF_STMT, and TREE_CODE.
Referenced by split_loop().
◆ find_control_dep_blocks()
|
static |
Given a BB in LOOP, find out all basic blocks in LOOP that BB is control- dependent on.
References basic_block_def::aux, loop::aux, CDI_DOMINATORS, CDI_POST_DOMINATORS, dominated_by_p(), FOR_EACH_EDGE, get_control_equiv_head_block(), get_immediate_dominator(), ggc_alloc(), loop::header, and NULL.
Referenced by control_dep_semi_invariant_p().
◆ find_or_create_guard_phi()
Give an induction variable GUARD_IV, and its affine descriptor IV, find the loop phi node in LOOP defining it directly, or create such phi node. Return that phi node.
References ggc_alloc(), gimple_bb(), loop::header, NULL, and SSA_NAME_DEF_STMT.
Referenced by split_loop().
◆ find_vdef_in_loop()
Find all statements with memory-write effect in LOOP, including memory store and non-pure function call, and keep those in a vector. This work is only done one time, for the vector should be constant during analysis stage of semi-invariant condition.
References loop::aux, bitmap_set_bit, flow_bb_inside_loop_p(), gcc_assert, get_virtual_phi(), ggc_alloc(), gimple_bb(), gimple_phi_arg_def(), gimple_phi_num_args(), gimple_phi_result(), gimple_vuse(), loop::header, i, last, loop_latch_edge(), split_info::memory_stores, split_info::need_init, NULL, PHI_ARG_DEF_FROM_EDGE, SSA_NAME_DEF_STMT, SSA_NAME_VERSION, visited, and worklist.
Referenced by vuse_semi_invariant_p().
◆ fix_loop_bb_probability()
|
static |
Fix the two loop's bb count after split based on the split edge probability, don't adjust the bbs dominated by true branches of that loop to avoid dropping 1s down.
References CDI_DOMINATORS, dominated_by_p(), free(), get_bb_copy(), get_loop_body(), ggc_alloc(), and single_pred_p().
Referenced by do_split_loop_on_cond(), and split_loop().
◆ get_cond_branch_to_split_loop()
Find out loop-invariant branch of a conditional statement (COND) if it has, and check whether it is eligible and profitable to perform loop split upon this branch in LOOP.
References profile_probability::always(), apply_scale(), compute_added_num_insns(), get_cond_invariant_branch(), ggc_alloc(), NULL, and profile_probability::reliable_p().
Referenced by split_loop_on_cond().
◆ get_cond_invariant_branch()
Find out which branch of a conditional statement (COND) is invariant in the execution context of LOOP. That is: once the branch is selected in certain iteration of the loop, any operand that contributes to computation of the conditional statement remains unchanged in all following iterations.
References branch_removable_p(), CDI_DOMINATORS, dominated_by_p(), EDGE_SUCC, flow_bb_inside_loop_p(), ggc_alloc(), gimple_bb(), i, loop::latch, NULL, and stmt_semi_invariant_p().
Referenced by get_cond_branch_to_split_loop().
◆ get_control_equiv_head_block()
|
static |
Two basic blocks have equivalent control dependency if one dominates to the other, and it is post-dominated by the latter. Given a basic block BB in LOOP, find farest equivalent dominating basic block. For BB, there is a constraint that BB does not post-dominate loop header of LOOP, this means BB is control-dependent on at least one basic block in LOOP.
References basic_block_def::aux, CDI_DOMINATORS, CDI_POST_DOMINATORS, dominated_by_p(), flow_bb_inside_loop_p(), gcc_checking_assert, get_immediate_dominator(), and ggc_alloc().
Referenced by find_control_dep_blocks().
◆ loop_iter_phi_semi_invariant_p()
|
static |
Check whether a loop iteration PHI node (LOOP_PHI) defines a value that is semi-invariant in LOOP. Basic blocks dominated by SKIP_HEAD (if non-NULL), are excluded from LOOP.
References CDI_DOMINATORS, dominated_by_p(), flow_bb_inside_loop_p(), gcc_checking_assert, ggc_alloc(), gimple_assign_rhs1(), gimple_assign_ssa_name_copy_p(), gimple_bb(), gimple_phi_arg_def(), gimple_phi_arg_edge(), gimple_phi_num_args(), gimple_phi_result(), i, loop_latch_edge(), NULL_TREE, operand_equal_p(), PHI_ARG_DEF_FROM_EDGE, SSA_NAME_DEF_STMT, and TREE_CODE.
Referenced by stmt_semi_invariant_p_1().
◆ make_pass_loop_split()
| gimple_opt_pass * make_pass_loop_split | ( | gcc::context * | ctxt | ) |
References ggc_alloc().
◆ patch_loop_exit()
|
static |
Given a GUARD conditional stmt inside LOOP, which we want to make always true or false depending on INITIAL_TRUE, and adjusted values NEXTVAL (a post-increment IV) and NEWBOUND (the comparator) adjust the loop exit test statement to loop back only if the GUARD statement will also be true/false in the next iteration.
References EDGE_SUCC, ggc_alloc(), gimple_cond_set_condition(), gsi_last_bb(), single_exit(), and update_stmt().
Referenced by split_loop().
◆ split_at_bb_p()
|
static |
Loop splitting. Copyright (C) 2015-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/>.
This file implements two kinds of loop splitting.
One transformation of loops like:
for (i = 0; i < 100; i++)
{
if (i < 50)
A;
else
B;
}
into:
for (i = 0; i < 50; i++)
{
A;
}
for (; i < 100; i++)
{
B;
} Return true when BB inside LOOP is a potential iteration space split point, i.e. ends with a condition like "IV < comp", which is true on one side of the iteration space and false on the other, and the split point can be computed. If so, also return the border point in *BORDER and the comparison induction variable in IV.
References iv::base, dump_file, dump_flags, get_global_range_query(), get_tree_code_name(), ggc_alloc(), gimple_cond_code(), gimple_cond_lhs(), gimple_cond_rhs(), gimple_cond_set_condition(), gsi_last_bb(), integer_zerop(), known_eq, loop_containing_stmt(), loop_exits_from_bb_p(), iv::no_overflow, NULL_TREE, operand_equal_p(), print_generic_expr(), print_gimple_stmt(), r, range_query::range_of_expr(), simple_iv(), iv::step, swap_tree_comparison(), TDF_DETAILS, TDF_SLIM, wi::to_wide(), TREE_CODE, tree_int_cst_sign_bit(), TREE_TYPE, and update_stmt().
Referenced by split_loop().
◆ split_loop()
Checks if LOOP contains an conditional block whose condition depends on which side in the iteration space it is, and if so splits the iteration space into two loops. Returns true if the loop was split. NITER must contain the iteration descriptor for the single exit of LOOP.
References profile_probability::always(), arith_code_with_undefined_signed_overflow(), boolean_type_node, can_copy_bbs_p(), CDI_DOMINATORS, changed, compute_new_first_bound(), connect_loop_phis(), connect_loops(), dominated_by_p(), dump_enabled_p(), dump_file, dump_flags, dump_printf_loc(), easy_exit_values(), EDGE_COUNT, empty_block_p(), extract_true_false_edges_from_block(), find_or_create_guard_phi(), wi::fits_shwi_p(), fix_loop_bb_probability(), fold_build1, fold_build2, force_gimple_operand(), free(), free_original_copy_tables(), gcc_assert, gcc_unreachable, get_bb_copy(), get_loop_body(), ggc_alloc(), gimple_assign_rhs_code(), gimple_cond_make_false(), gimple_cond_make_true(), gsi_end_p(), gsi_insert_seq_on_edge_immediate(), gsi_last_bb(), gsi_next(), gsi_start(), gsi_stmt(), i, initialize_original_copy_tables(), integer_onep(), is_gimple_assign(), loop_latch_edge(), loop_preheader_edge(), loop_version(), MAX, MSG_OPTIMIZED_LOCATIONS, tree_niter_desc::niter, NULL, NULL_TREE, number_of_iterations_exit(), patch_loop_exit(), PHI_ARG_DEF_FROM_EDGE, rewrite_to_defined_overflow(), single_exit(), single_pred_edge(), split_at_bb_p(), iv::step, TDF_DETAILS, profile_probability::to_sreal(), tree_int_cst_equal(), tree_int_cst_sign_bit(), update_loop_exit_probability_scale_dom_bbs(), update_stmt(), and profile_probability::very_likely().
Referenced by tree_ssa_split_loops().
◆ split_loop_on_cond()
Traverse all conditional statements in LOOP, to find out a good candidate upon which we can do loop split.
References loop::aux, split_info::bbs, CDI_DOMINATORS, do_split_loop_on_cond(), dominated_by_p(), basic_block_def::flags, get_cond_branch_to_split_loop(), get_loop_body(), ggc_alloc(), gsi_last_bb(), i, loop::latch, basic_block_def::loop_father, NULL, and loop::num_nodes.
Referenced by tree_ssa_split_loops().
◆ ssa_semi_invariant_p()
|
inlinestatic |
Suppose one condition branch, led by SKIP_HEAD, is not executed since certain iteration of LOOP, check whether an SSA name (NAME) remains unchanged in next iteration. We call this characteristic semi- invariantness. SKIP_HEAD might be NULL, if so, nothing excluded, all basic blocks and control flows in the loop will be considered. Semi-invariant state of checked statement is cached in hash map STMT_STAT to avoid redundant computation in possible following re-check.
References flow_bb_inside_loop_p(), ggc_alloc(), gimple_bb(), SSA_NAME_DEF_STMT, SSA_NAME_OCCURS_IN_ABNORMAL_PHI, and stmt_semi_invariant_p_1().
Referenced by stmt_semi_invariant_p_1().
◆ stmt_semi_invariant_p()
|
static |
A helper function to check whether STMT is semi-invariant in LOOP. Basic blocks dominated by SKIP_HEAD (if non-NULL), are excluded from LOOP.
References ggc_alloc(), and stmt_semi_invariant_p_1().
Referenced by get_cond_invariant_branch().
◆ stmt_semi_invariant_p_1()
|
static |
Forward declaration
Check whether STMT is semi-invariant in LOOP, iff all its operands are semi-invariant, consequently, all its defined values are semi-invariant. Basic blocks dominated by SKIP_HEAD (if non-NULL), are excluded from LOOP. Semi-invariant state of checked statement is cached in hash map STMT_STAT.
References control_dep_semi_invariant_p(), FOR_EACH_SSA_TREE_OPERAND, ggc_alloc(), gimple_bb(), gimple_has_side_effects(), gimple_phi_arg_def(), gimple_phi_arg_edge(), gimple_phi_num_args(), gimple_vuse(), loop::header, i, loop_iter_phi_semi_invariant_p(), loop_preheader_edge(), PHI_ARG_DEF_FROM_EDGE, SSA_NAME_DEF_STMT, SSA_NAME_OCCURS_IN_ABNORMAL_PHI, SSA_OP_USE, ssa_semi_invariant_p(), TREE_CODE, and vuse_semi_invariant_p().
Referenced by control_dep_semi_invariant_p(), ssa_semi_invariant_p(), and stmt_semi_invariant_p().
◆ tree_ssa_split_loops()
Main entry point. Perform loop splitting on all suitable loops.
References loop::aux, calculate_dominance_info(), CDI_POST_DOMINATORS, cfun, changed, clear_aux_for_blocks(), free_dominance_info(), gcc_assert, LI_FROM_INNERMOST, LI_INCLUDE_ROOT, loop_outer(), NULL, optimize_loop_for_size_p(), rewrite_into_loop_closed_ssa(), scev_initialized_p(), split_loop(), split_loop_on_cond(), TODO_cleanup_cfg, and TODO_update_ssa.
◆ vuse_semi_invariant_p()
|
static |
Given STMT, memory load or pure call statement, check whether it is impacted by some memory store in LOOP, excluding trace starting from SKIP_HEAD (the trace is composed of SKIP_HEAD and those basic block dominated by it, always corresponds to one branch of a conditional statement). If SKIP_HEAD is NULL, all basic blocks of LOOP are checked.
References ao_ref_init(), loop::aux, CDI_DOMINATORS, dominated_by_p(), find_vdef_in_loop(), FOR_EACH_VEC_ELT, ggc_alloc(), gimple_assign_rhs1(), gimple_bb(), i, is_gimple_assign(), split_info::memory_stores, split_info::need_init, NULL_TREE, ao_ref::ref, and stmt_may_clobber_ref_p_1().
Referenced by stmt_semi_invariant_p_1().
