#include "config.h"#include "system.h"#include "coretypes.h"#include "backend.h"#include "target.h"#include "rtl.h"#include "tree.h"#include "cfghooks.h"#include "memmodel.h"#include "optabs.h"#include "emit-rtl.h"#include "recog.h"#include "profile.h"#include "cfgrtl.h"#include "cfgloop.h"#include "dojump.h"#include "expr.h"#include "dumpfile.h"
Data Structures | |
| struct | iv_to_split |
| struct | var_to_expand |
| struct | iv_split_hasher |
| struct | var_expand_hasher |
| struct | opt_info |
Function Documentation
◆ allocate_basic_variable()
|
static |
Allocate basic variable for the induction variable chain.
References iv_to_split::base_var, gen_reg_rtx(), GET_MODE, iv_to_split::insn, SET_SRC, and single_set().
Referenced by apply_opt_in_copies().
◆ analyze_insn_to_expand_var()
|
static |
Determine whether INSN contains an accumulator
which can be expanded into separate copies,
one for each copy of the LOOP body.
for (i = 0 ; i < n; i++)
sum += a[i];
==>
sum += a[i]
....
i = i+1;
sum1 += a[i]
....
i = i+1
sum2 += a[i];
....
Return NULL if INSN contains no opportunity for expansion of accumulator.
Otherwise, allocate a VAR_TO_EXPAND structure, fill it with the relevant
information and return a pointer to it.
References copy_rtx(), dump_file, var_to_expand::expansion_count, FLOAT_MODE_P, GET_CODE, GET_MODE, have_insn_for(), var_to_expand::insn, var_to_expand::next, NULL, var_to_expand::op, print_rtl(), referenced_in_one_insn_in_loop_p(), var_to_expand::reg, REG_P, reset_debug_uses_in_loop(), var_to_expand::reuse_expansion, rtx_equal_p(), rtx_referenced_p(), SET_DEST, SET_SRC, single_set(), SUBREG_REG, var_to_expand::var_expansions, and XEXP.
Referenced by analyze_insns_in_loop().
◆ analyze_insns_in_loop()
Determines which of insns in LOOP can be optimized. Return a OPT_INFO struct with the relevant hash tables filled with all insns to be optimized. The FIRST_NEW_BLOCK field is undefined for the return value.
References analyze_insn_to_expand_var(), analyze_iv_to_split_insn(), CDI_DOMINATORS, dominated_by_p(), EDGE_COMPLEX, hash_table< Descriptor, Lazy, Allocator >::find_slot(), FOR_BB_INSNS, free(), gcc_assert, get_loop_body(), get_loop_exit_edges(), i, var_to_expand::insn, INSN_P, opt_info::insns_to_split, opt_info::insns_with_var_to_expand, iv_analysis_loop_init(), opt_info::iv_to_split_head, opt_info::iv_to_split_tail, loop::latch, opt_info::loop_exit, opt_info::loop_preheader, loop_preheader_edge(), iv_to_split::next, var_to_expand::next, NULL, loop::num_nodes, split_edge(), opt_info::var_to_expand_head, and opt_info::var_to_expand_tail.
Referenced by unroll_loop_constant_iterations(), unroll_loop_runtime_iterations(), and unroll_loop_stupid().
◆ analyze_iv_to_split_insn()
|
static |
Determine whether there is an induction variable in INSN that we would like to split during unrolling. I.e. replace i = i + 1; ... i = i + 1; ... i = i + 1; ... type chains by i0 = i + 1 ... i = i0 + 1 ... i = i0 + 2 ... Return NULL if INSN contains no interesting IVs. Otherwise, allocate an IV_TO_SPLIT structure, fill it with the relevant information and return a pointer to it.
References iv_to_split::base_var, biv_p(), const0_rtx, GET_MODE, iv_to_split::insn, is_a(), iv_analyze_result(), iv_to_split::next, NULL, NULL_RTX, iv_to_split::orig_var, REG_P, SET_DEST, single_set(), iv::step, and iv_to_split::step.
Referenced by analyze_insns_in_loop().
◆ apply_opt_in_copies()
|
static |
Apply loop optimizations in loop copies using the data which gathered during the unrolling. Structure OPT_INFO record that data. UNROLLING is true if we unrolled (not peeled) the loop. REWRITE_ORIGINAL_BODY is true if we should also rewrite the original body of the loop (as it should happen in complete unrolling, but not in ordinary peeling of the loop).
References allocate_basic_variable(), basic_block_def::aux, BASIC_BLOCK_FOR_FN, BB_END, BB_HEAD, cfun, combine_var_copies_in_loop_exit(), DEBUG_BIND_INSN_P, determine_split_iv_delta(), expand_var_during_unrolling(), hash_table< Descriptor, Lazy, Allocator >::find(), opt_info::first_new_block, FOR_BB_INSNS_SAFE, gcc_assert, get_bb_copy(), get_bb_original(), GET_CODE, i, insert_base_initialization(), insert_var_expansion_initialization(), iv_to_split::insn, var_to_expand::insn, INSN_P, INSN_VAR_LOCATION_DECL, opt_info::insns_to_split, opt_info::insns_with_var_to_expand, opt_info::iv_to_split_head, last_basic_block_for_fn, opt_info::loop_exit, opt_info::loop_preheader, maybe_strip_eq_note_for_split_iv(), iv_to_split::next, var_to_expand::next, NEXT_INSN(), PATTERN(), split_iv(), TREE_CODE, and opt_info::var_to_expand_head.
Referenced by unroll_loop_constant_iterations(), unroll_loop_runtime_iterations(), and unroll_loop_stupid().
◆ combine_var_copies_in_loop_exit()
|
static |
Combine the variable expansions at the loop exit. PLACE is the loop exit basic block where the summation of the expansions should take place.
References BB_HEAD, copy_rtx(), emit_insn_after(), emit_move_insn(), end_sequence(), FOR_EACH_VEC_ELT, force_operand(), gcc_unreachable, GET_MODE, i, var_to_expand::insn, NEXT_INSN(), NOTE_INSN_BASIC_BLOCK_P, var_to_expand::op, var_to_expand::reg, simplify_gen_binary(), start_sequence(), and var_to_expand::var_expansions.
Referenced by apply_opt_in_copies().
◆ compare_and_jump_seq()
|
static |
Prepare a sequence comparing OP0 with OP1 using COMP and jumping to LABEL if true, with probability PROB. If CINSN is not NULL, it is the insn to copy in order to create a jump.
References add_reg_br_prob_note(), as_a(), comp, copy_insn(), do_compare_rtx_and_jump(), emit_jump_insn(), end_sequence(), force_operand(), gcc_assert, GET_CODE, get_last_insn(), GET_MODE, GET_MODE_CLASS, profile_probability::initialized_p(), JUMP_LABEL, LABEL_NUSES, niter_desc::mode, NULL, NULL_RTX, PATTERN(), pc_set(), redirect_jump(), rtx_equal_p(), rtx_jump_insn::set_jump_target(), SET_SRC, start_sequence(), profile_probability::uninitialized(), and XEXP.
Referenced by unroll_loop_runtime_iterations().
◆ decide_unroll_constant_iterations()
|
static |
Decide whether to unroll LOOP iterating constant number of times and how much.
References niter_desc::assumptions, loop::av_ninsns, niter_desc::const_iter, lpt_decision::decision, dump_enabled_p(), dump_file, dump_printf(), get_estimated_loop_iterations(), get_likely_max_loop_iterations(), get_simple_loop_desc(), i, loop_exit_at_end_p(), loop::lpt_decision, LPT_UNROLL_CONSTANT, wi::ltu_p(), MSG_NOTE, loop::ninsns, niter_desc::niter, niter_desc::noloop_assumptions, NULL_RTX, niter_desc::simple_p, targetm, lpt_decision::times, UAP_UNROLL, loop::unroll, and USHRT_MAX.
Referenced by decide_unrolling().
◆ decide_unroll_runtime_iterations()
|
static |
Decide whether to unroll LOOP iterating runtime computable number of times and how much.
References niter_desc::assumptions, loop::av_ninsns, niter_desc::const_iter, lpt_decision::decision, dump_enabled_p(), dump_file, dump_printf(), get_estimated_loop_iterations(), get_likely_max_loop_iterations(), get_simple_loop_desc(), i, loop::lpt_decision, LPT_UNROLL_RUNTIME, wi::ltu_p(), MSG_NOTE, loop::ninsns, niter_desc::simple_p, targetm, lpt_decision::times, UAP_UNROLL, loop::unroll, and USHRT_MAX.
Referenced by decide_unrolling().
◆ decide_unroll_stupid()
|
static |
Decide whether to unroll LOOP stupidly and how much.
References niter_desc::assumptions, loop::av_ninsns, lpt_decision::decision, dump_enabled_p(), dump_file, dump_printf(), get_estimated_loop_iterations(), get_likely_max_loop_iterations(), get_simple_loop_desc(), i, loop::lpt_decision, LPT_UNROLL_STUPID, wi::ltu_p(), MSG_NOTE, loop::ninsns, num_loop_branches(), niter_desc::simple_p, targetm, lpt_decision::times, UAP_UNROLL_ALL, loop::unroll, and USHRT_MAX.
Referenced by decide_unrolling().
◆ decide_unrolling()
|
static |
Decide whether unroll loops and how much.
References loop::av_ninsns, average_num_loop_insns(), can_duplicate_loop_p(), cfun, decide_unroll_constant_iterations(), decide_unroll_runtime_iterations(), decide_unroll_stupid(), lpt_decision::decision, dump_enabled_p(), dump_file, dump_printf_loc(), get_loop_location(), loop::header, basic_block_def::index, loop::inner, LI_FROM_INNERMOST, loop::lpt_decision, LPT_NONE, MSG_NOTE, loop::ninsns, loop::num, num_loop_insns(), optimize_loop_for_size_p(), report_unroll(), and loop::unroll.
Referenced by unroll_loops().
◆ determine_split_iv_delta()
|
static |
Determine the number of iterations between initialization of the base variable and the current copy (N_COPY). N_COPIES is the total number of newly created copies. UNROLLING is true if we are unrolling (not peeling) the loop.
Referenced by apply_opt_in_copies().
◆ expand_var_during_unrolling()
|
static |
Given INSN replace the uses of the accumulator recorded in VE with a new register.
References apply_change_group(), var_to_expand::expansion_count, gcc_assert, gen_reg_rtx(), get_expansion(), GET_MODE, var_to_expand::insn, var_to_expand::reg, SET_DEST, single_set(), validate_replace_rtx_group(), and var_to_expand::var_expansions.
Referenced by apply_opt_in_copies().
◆ free_opt_info()
|
static |
Release OPT_INFO.
References free(), opt_info::insns_to_split, opt_info::insns_with_var_to_expand, var_to_expand::next, NULL, var_to_expand::var_expansions, and opt_info::var_to_expand_head.
Referenced by unroll_loop_constant_iterations(), unroll_loop_runtime_iterations(), and unroll_loop_stupid().
◆ get_expansion()
|
static |
Return one expansion of the accumulator recorded in struct VE.
References var_to_expand::reg, var_to_expand::reuse_expansion, and var_to_expand::var_expansions.
Referenced by expand_var_during_unrolling().
◆ insert_base_initialization()
|
static |
Insert initialization of basic variable of IVTS before INSN, taking the initial value from INSN.
References iv_to_split::base_var, copy_rtx(), emit_insn_before(), emit_move_insn(), end_sequence(), force_operand(), var_to_expand::insn, SET_SRC, single_set(), and start_sequence().
Referenced by apply_opt_in_copies().
◆ insert_var_expansion_initialization()
|
static |
Initialize the variable expansions in loop preheader. PLACE is the loop-preheader basic block where the initialization of the expansions should take place. The expansions are initialized with (-0) when the operation is plus or minus to honor sign zero. This way we can prevent cases where the sign of the final result is effected by the sign of the expansion. Here is an example to demonstrate this: for (i = 0 ; i < n; i++) sum += something; ==> sum += something .... i = i+1; sum1 += something .... i = i+1 sum2 += something; .... When SUM is initialized with -zero and SOMETHING is also -zero; the final result of sum should be -zero thus the expansions sum1 and sum2 should be initialized with -zero as well (otherwise we will get +zero as the final result).
References BB_END, CONST0_RTX, CONST1_RTX, emit_insn_after(), emit_move_insn(), end_sequence(), FOR_EACH_VEC_ELT, gcc_unreachable, GET_MODE, i, MODE_HAS_SIGNED_ZEROS, var_to_expand::op, var_to_expand::reg, simplify_gen_unary(), start_sequence(), and var_to_expand::var_expansions.
Referenced by apply_opt_in_copies().
◆ loop_exit_at_end_p()
Check whether exit of the LOOP is at the end of loop body.
References active_insn_p(), FOR_BB_INSNS, gcc_assert, get_simple_loop_desc(), loop::header, niter_desc::in_edge, INSN_P, and loop::latch.
Referenced by decide_unroll_constant_iterations(), unroll_loop_constant_iterations(), and unroll_loop_runtime_iterations().
◆ maybe_strip_eq_note_for_split_iv()
Strip away REG_EQUAL notes for IVs we're splitting. Updating REG_EQUAL notes for IVs we split is tricky: We cannot tell until after unrolling, DF-rescanning, and liveness updating, whether an EQ_USE is reached by the split IV while the IV reg is still live. See PR55006. ??? We cannot use remove_reg_equal_equiv_notes_for_regno, because RTL loop-iv requires us to defer rescanning insns and any notes attached to them. So resort to old techniques...
References find_reg_equal_equiv_note(), iv_to_split::insn, opt_info::iv_to_split_head, iv_to_split::next, iv_to_split::orig_var, reg_mentioned_p(), and remove_note().
Referenced by apply_opt_in_copies().
◆ opt_info_start_duplication()
|
static |
Called just before loop duplication. Records start of duplicated area to OPT_INFO.
References cfun, opt_info::first_new_block, and last_basic_block_for_fn.
Referenced by unroll_loop_constant_iterations(), unroll_loop_runtime_iterations(), and unroll_loop_stupid().
◆ referenced_in_one_insn_in_loop_p()
Returns true if REG is referenced in one nondebug insn in LOOP. Set *DEBUG_USES to the number of debug insns that reference the variable.
References DEBUG_INSN_P, FOR_BB_INSNS, free(), get_loop_body(), i, loop::num_nodes, and rtx_referenced_p().
Referenced by analyze_insn_to_expand_var().
◆ report_unroll()
|
static |
Emit a message summarizing the unroll that will be performed for LOOP, along with the loop's location LOCUS, if appropriate given the dump or -fopt-info settings.
References basic_block_def::count, lpt_decision::decision, dump_enabled_p(), dump_printf(), dump_printf_loc(), dump_location_t::get_impl_location(), dump_location_t::get_user_location(), loop::header, profile_count::initialized_p(), loop::lpt_decision, LPT_NONE, MSG_OPTIMIZED_LOCATIONS, profile_info, TDF_DETAILS, lpt_decision::times, and profile_count::to_gcov_type().
Referenced by decide_unrolling().
◆ reset_debug_uses_in_loop()
Reset the DEBUG_USES debug insns in LOOP that reference REG.
References DEBUG_INSN_P, FOR_BB_INSNS, free(), gen_rtx_UNKNOWN_VAR_LOC, get_loop_body(), i, INSN_VAR_LOCATION_LOC, loop::num_nodes, rtx_referenced_p(), and validate_change().
Referenced by analyze_insn_to_expand_var().
◆ split_edge_and_insert()
| basic_block split_edge_and_insert | ( | edge | e, |
| rtx_insn * | insns ) |
Splits edge E and inserts the sequence of instructions INSNS on it, and returns the newly created block. If INSNS is NULL_RTX, nothing is changed and NULL is returned instead.
References BB_END, emit_insn_after(), insns, NULL, and split_edge().
Referenced by add_test(), and unroll_loop_runtime_iterations().
◆ split_iv()
|
static |
Replace the use of induction variable described in IVTS in INSN by base variable + DELTA * step.
References iv_to_split::base_var, copy_rtx(), delete_insn(), emit_insn_before(), emit_move_insn(), end_sequence(), force_operand(), gcc_assert, gen_int_mode(), gen_reg_rtx(), GET_MODE, var_to_expand::insn, SET_DEST, SET_SRC, simplify_gen_binary(), single_set(), start_sequence(), iv_to_split::step, and validate_change().
Referenced by apply_opt_in_copies().
◆ unroll_loop_constant_iterations()
|
static |
Unroll LOOP with constant number of iterations LOOP->LPT_DECISION.TIMES times.
The transformation does this:
for (i = 0; i < 102; i++)
body;
==> (LOOP->LPT_DECISION.TIMES == 3)
i = 0;
body; i++;
body; i++;
while (i < 102)
{
body; i++;
body; i++;
body; i++;
body; i++;
}
References analyze_insns_in_loop(), loop::any_estimate, loop::any_likely_upper_bound, apply_opt_in_copies(), bitmap_clear_bit(), bitmap_ones(), bitmap_set_bit, DLTHE_FLAG_FLAT_PROFILE, DLTHE_FLAG_UPDATE_FREQ, DLTHE_RECORD_COPY_NUMBER, dump_file, duplicate_loop_body_to_header_edge(), EDGE_SUCC, FOR_EACH_VEC_ELT, free_opt_info(), gcc_assert, gen_int_mode(), get_bb_copy(), get_simple_loop_desc(), i, niter_desc::in_edge, wi::leu_p(), loop_exit_at_end_p(), loop_latch_edge(), loop_preheader_edge(), loop::lpt_decision, maybe_flat_loop_profile(), niter_desc::mode, loop::nb_iterations_estimate, loop::nb_iterations_likely_upper_bound, loop::nb_iterations_upper_bound, niter_desc::niter, niter_desc::niter_expr, niter_desc::noloop_assumptions, NULL, NULL_RTX, num_loop_insns(), opt_info_start_duplication(), niter_desc::out_edge, remove_path(), lpt_decision::times, wi::udiv_trunc(), update_br_prob_note(), and update_loop_exit_probability_scale_dom_bbs().
Referenced by unroll_loops().
◆ unroll_loop_runtime_iterations()
|
static |
Unroll LOOP for which we are able to count number of iterations in
runtime LOOP->LPT_DECISION.TIMES times. The times value must be a
power of two. The transformation does this (with some extra care
for case n < 0):
for (i = 0; i < n; i++)
body;
==> (LOOP->LPT_DECISION.TIMES == 3)
i = 0;
mod = n % 4;
switch (mod)
{
case 3:
body; i++;
case 2:
body; i++;
case 1:
body; i++;
case 0: ;
}
while (i < n)
{
body; i++;
body; i++;
body; i++;
body; i++;
}
References profile_probability::always(), analyze_insns_in_loop(), loop::any_estimate, loop::any_likely_upper_bound, apply_opt_in_copies(), bitmap_clear(), bitmap_clear_bit(), bitmap_ones(), bitmap_set_bit, block_label(), CDI_DOMINATORS, compare_and_jump_seq(), const0_rtx, const1_rtx, niter_desc::const_iter, copy_rtx(), basic_block_def::count, DLTHE_FLAG_UPDATE_FREQ, DLTHE_RECORD_COPY_NUMBER, dump_file, duplicate_loop_body_to_header_edge(), EDGE_SUCC, emit_move_insn(), end_sequence(), expand_simple_binop(), flow_bb_inside_loop_p(), FOR_EACH_VEC_ELT, force_operand(), free(), free_opt_info(), gcc_assert, gen_int_mode(), gen_reg_rtx(), get_bb_copy(), get_dominated_by(), get_loop_body(), get_simple_loop_desc(), i, niter_desc::in_edge, profile_probability::invert(), iterate_fix_dominators(), loop_exit_at_end_p(), loop_latch_edge(), loop_preheader_edge(), loop::lpt_decision, make_edge(), niter_desc::mode, loop::nb_iterations_estimate, loop::nb_iterations_likely_upper_bound, loop::nb_iterations_upper_bound, niter_desc::niter, niter_desc::niter_expr, niter_desc::noloop_assumptions, NULL, NULL_RTX, num_loop_insns(), loop::num_nodes, opt_info_start_duplication(), OPTAB_LIB_WIDEN, niter_desc::out_edge, remove_path(), set_immediate_dominator(), simplify_gen_binary(), single_pred_edge(), single_succ_edge(), split_edge(), split_edge_and_insert(), start_sequence(), lpt_decision::times, wi::udiv_trunc(), and unshare_all_rtl_in_chain().
Referenced by unroll_loops().
◆ unroll_loop_stupid()
|
static |
Unroll a LOOP LOOP->LPT_DECISION.TIMES times. The transformation does this:
while (cond)
body;
==> (LOOP->LPT_DECISION.TIMES == 3)
while (cond)
{
body;
if (!cond) break;
body;
if (!cond) break;
body;
if (!cond) break;
body;
}
References analyze_insns_in_loop(), apply_opt_in_copies(), bitmap_clear(), DLTHE_FLAG_UPDATE_FREQ, DLTHE_RECORD_COPY_NUMBER, dump_file, duplicate_loop_body_to_header_edge(), free_opt_info(), gcc_assert, get_simple_loop_desc(), loop_latch_edge(), loop::lpt_decision, NULL, num_loop_insns(), opt_info_start_duplication(), niter_desc::simple_p, and lpt_decision::times.
Referenced by unroll_loops().
◆ unroll_loops()
| void unroll_loops | ( | int | flags | ) |
Unroll LOOPS.
References calculate_dominance_info(), CDI_DOMINATORS, cfun, changed, decide_unrolling(), lpt_decision::decision, fix_loop_structure(), gcc_unreachable, iv_analysis_done(), LI_FROM_INNERMOST, loop::lpt_decision, LPT_NONE, LPT_UNROLL_CONSTANT, LPT_UNROLL_RUNTIME, LPT_UNROLL_STUPID, NULL, unroll_loop_constant_iterations(), unroll_loop_runtime_iterations(), and unroll_loop_stupid().
