#include "config.h"#include "system.h"#include "coretypes.h"#include "backend.h"#include "rtl.h"#include "tree.h"#include "gimple.h"#include "cfghooks.h"#include "tree-pass.h"#include "memmodel.h"#include "tm_p.h"#include "ssa.h"#include "expmed.h"#include "insn-config.h"#include "emit-rtl.h"#include "recog.h"#include "cgraph.h"#include "gimple-pretty-print.h"#include "alias.h"#include "fold-const.h"#include "stor-layout.h"#include "tree-eh.h"#include "gimplify.h"#include "gimple-iterator.h"#include "gimplify-me.h"#include "tree-cfg.h"#include "tree-ssa-loop-ivopts.h"#include "tree-ssa-loop-manip.h"#include "tree-ssa-loop-niter.h"#include "tree-ssa-loop.h"#include "explow.h"#include "expr.h"#include "tree-dfa.h"#include "tree-ssa.h"#include "cfgloop.h"#include "tree-scalar-evolution.h"#include "tree-affine.h"#include "tree-ssa-propagate.h"#include "tree-ssa-address.h"#include "builtins.h"#include "tree-vectorizer.h"#include "dbgcnt.h"#include "cfganal.h"#include "langhooks.h"#include "gt-tree-ssa-loop-ivopts.h"
Data Structures | |
| struct | iv |
| struct | version_info |
| class | comp_cost |
| class | cost_pair |
| struct | iv_use |
| struct | iv_group |
| struct | iv_cand |
| class | iv_common_cand |
| struct | iv_common_cand_hasher |
| struct | iv_inv_expr_ent |
| struct | iv_inv_expr_hasher |
| struct | ivopts_data |
| class | iv_ca |
| struct | iv_ca_delta |
| struct | ifs_ivopts_data |
| struct | walk_tree_data |
| struct | ainc_cost_data |
Macros | |
| #define | INFTY 1000000000 |
| #define | CONSIDER_ALL_CANDIDATES_BOUND ((unsigned) param_iv_consider_all_candidates_bound) |
| #define | MAX_CONSIDERED_GROUPS ((unsigned) param_iv_max_considered_uses) |
| #define | ALWAYS_PRUNE_CAND_SET_BOUND ((unsigned) param_iv_always_prune_cand_set_bound) |
| #define | COST_SCALING_FACTOR_BOUND (20) |
Enumerations | |
| enum | use_type { USE_NONLINEAR_EXPR , USE_REF_ADDRESS , USE_PTR_ADDRESS , USE_COMPARE } |
| enum | iv_position { IP_NORMAL , IP_END , IP_BEFORE_USE , IP_AFTER_USE , IP_ORIGINAL } |
| enum | comp_iv_rewrite { COMP_IV_NA , COMP_IV_EXPR , COMP_IV_EXPR_2 , COMP_IV_ELIM } |
| enum | ainc_type { AINC_PRE_INC , AINC_PRE_DEC , AINC_POST_INC , AINC_POST_DEC , AINC_NONE } |
Variables | |
| static const comp_cost | no_cost |
| static const comp_cost | infinite_cost (INFTY, 0, INFTY) |
| static vec< tree > | decl_rtl_to_reset |
| static vec< rtx, va_gc > * | addr_list |
Macro Definition Documentation
◆ ALWAYS_PRUNE_CAND_SET_BOUND
| #define ALWAYS_PRUNE_CAND_SET_BOUND ((unsigned) param_iv_always_prune_cand_set_bound) |
If there are at most this number of ivs in the set, try removing unnecessary ivs from the set always.
Referenced by iv_ca_replace(), and try_improve_iv_set().
◆ CONSIDER_ALL_CANDIDATES_BOUND
| #define CONSIDER_ALL_CANDIDATES_BOUND ((unsigned) param_iv_consider_all_candidates_bound) |
Bound on number of candidates below that all candidates are considered.
Referenced by record_important_candidates().
◆ COST_SCALING_FACTOR_BOUND
| #define COST_SCALING_FACTOR_BOUND (20) |
Determine cost scaling factor for basic blocks in loop.
Referenced by determine_scaling_factor().
◆ INFTY
| #define INFTY 1000000000 |
Induction variable optimizations. Copyright (C) 2003-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 pass tries to find the optimal set of induction variables for the loop.
It optimizes just the basic linear induction variables (although adding
support for other types should not be too hard). It includes the
optimizations commonly known as strength reduction, induction variable
coalescing and induction variable elimination. It does it in the
following steps:
1) The interesting uses of induction variables are found. This includes
-- uses of induction variables in non-linear expressions
-- addresses of arrays
-- comparisons of induction variables
Note the interesting uses are categorized and handled in group.
Generally, address type uses are grouped together if their iv bases
are different in constant offset.
2) Candidates for the induction variables are found. This includes
-- old induction variables
-- the variables defined by expressions derived from the "interesting
groups/uses" above
3) The optimal (w.r. to a cost function) set of variables is chosen. The
cost function assigns a cost to sets of induction variables and consists
of three parts:
-- The group/use costs. Each of the interesting groups/uses chooses
the best induction variable in the set and adds its cost to the sum.
The cost reflects the time spent on modifying the induction variables
value to be usable for the given purpose (adding base and offset for
arrays, etc.).
-- The variable costs. Each of the variables has a cost assigned that
reflects the costs associated with incrementing the value of the
variable. The original variables are somewhat preferred.
-- The set cost. Depending on the size of the set, extra cost may be
added to reflect register pressure.
All the costs are defined in a machine-specific way, using the target
hooks and machine descriptions to determine them.
4) The trees are transformed to use the new variables, the dead code is
removed.
All of this is done loop by loop. Doing it globally is theoretically
possible, it might give a better performance and it might enable us
to decide costs more precisely, but getting all the interactions right
would be complicated.
For the targets supporting low-overhead loops, IVOPTs has to take care of
the loops which will probably be transformed in RTL doloop optimization,
to try to make selected IV candidate set optimal. The process of doloop
support includes:
1) Analyze the current loop will be transformed to doloop or not, find and
mark its compare type IV use as doloop use (iv_group field doloop_p), and
set flag doloop_use_p of ivopts_data to notify subsequent processings on
doloop. See analyze_and_mark_doloop_use and its callees for the details.
The target hook predict_doloop_p can be used for target specific checks.
2) Add one doloop dedicated IV cand {(may_be_zero ? 1 : (niter + 1)), +, -1},
set flag doloop_p of iv_cand, step cost is set as zero and no extra cost
like biv. For cost determination between doloop IV cand and IV use, the
target hooks doloop_cost_for_generic and doloop_cost_for_address are
provided to add on extra costs for generic type and address type IV use.
Zero cost is assigned to the pair between doloop IV cand and doloop IV
use, and bound zero is set for IV elimination.
3) With the cost setting in step 2), the current cost model based IV
selection algorithm will process as usual, pick up doloop dedicated IV if
profitable. For lang_hooks.types.type_for_mode.
FIXME: Expressions are expanded to RTL in this pass to determine the cost of different addressing modes. This should be moved to a TBD interface between the GIMPLE and RTL worlds.
The infinite cost.
Referenced by adjust_setup_cost(), get_address_cost_ainc(), comp_cost::infinite_cost_p(), and comp_cost::operator+=().
◆ MAX_CONSIDERED_GROUPS
| #define MAX_CONSIDERED_GROUPS ((unsigned) param_iv_max_considered_uses) |
If there are more iv occurrences, we just give up (it is quite unlikely that optimizing such a loop would help, and it would take ages).
Referenced by tree_ssa_iv_optimize_loop().
Enumeration Type Documentation
◆ ainc_type
Returns cost of auto-modifying address expression in shape base + offset. AINC_STEP is step size of the address IV. AINC_OFFSET is offset of the address expression. The address expression has ADDR_MODE in addr space AS. The memory access has MEM_MODE. SPEED means we are optimizing for speed or size.
| Enumerator | |
|---|---|
| AINC_PRE_INC | |
| AINC_PRE_DEC | |
| AINC_POST_INC | |
| AINC_POST_DEC | |
| AINC_NONE | |
◆ comp_iv_rewrite
◆ iv_position
◆ use_type
Function Documentation
◆ add_autoinc_candidates()
|
static |
If possible, adds autoincrement candidates BASE + STEP * i based on use USE. Important field is set to IMPORTANT.
References add_candidate_1(), CDI_DOMINATORS, cfun, cst_and_fits_in_hwi(), dominated_by_p(), fold_build1, fold_build2, fold_convert, GET_MODE_SIZE(), ggc_alloc(), gimple_bb(), iv_cand::important, int_cst_value(), IP_AFTER_USE, IP_BEFORE_USE, known_eq, POINTER_TYPE_P, stmt_can_throw_internal(), TREE_TYPE, TYPE_MODE, USE_LOAD_POST_DECREMENT, USE_LOAD_POST_INCREMENT, USE_LOAD_PRE_DECREMENT, USE_LOAD_PRE_INCREMENT, USE_STORE_POST_DECREMENT, USE_STORE_POST_INCREMENT, USE_STORE_PRE_DECREMENT, and USE_STORE_PRE_INCREMENT.
Referenced by add_iv_candidate_for_use().
◆ add_candidate()
|
static |
Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and position to POS. If USE is not NULL, the candidate is set as related to it. The candidate computation is scheduled before exit condition and at the end of loop.
References add_candidate_1(), allow_ip_end_pos_p(), ggc_alloc(), iv_cand::important, IP_END, ip_end_pos(), IP_NORMAL, ip_normal_pos(), NULL, and iv_cand::orig_iv.
Referenced by add_iv_candidate_for_biv(), add_iv_candidate_for_doloop(), add_iv_candidate_for_use(), and add_standard_iv_candidates().
◆ add_candidate_1()
|
static |
Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and position to POS. If USE is not NULL, the candidate is set as related to it. If both BASE and STEP are NULL, we add a pseudocandidate for the replacement of the final value of the iv by a direct computation.
References alloc_iv(), BITMAP_ALLOC, bitmap_clear(), bitmap_set_bit, create_tmp_var_raw(), dump_cand(), dump_file, dump_flags, find_inv_vars(), find_ssa_undef(), fold_convert, gcc_assert, generic_type_for(), get_loop_invariant_expr(), ggc_alloc(), i, iv_cand::important, iv_cand::incremented_at, iv_cand::involves_undefs, IP_AFTER_USE, IP_BEFORE_USE, IP_ORIGINAL, NULL, operand_equal_p(), iv_cand::orig_iv, POINTER_TYPE_P, poly_int_tree_p(), iv_cand::pos, TDF_DETAILS, TREE_TYPE, type(), TYPE_PRECISION, and walk_tree.
Referenced by add_autoinc_candidates(), add_candidate(), add_iv_candidate_derived_from_uses(), and add_iv_candidate_for_biv().
◆ add_iv_candidate_derived_from_uses()
|
static |
Adds IV candidates based on common candidated recorded.
References add_candidate_1(), allow_ip_end_pos_p(), iv_common_cand::base, bitmap_set_bit, common_cand_cmp(), ggc_alloc(), i, IP_END, ip_end_pos(), IP_NORMAL, ip_normal_pos(), NULL, iv_group::related_cands, iv_common_cand::step, and iv_common_cand::uses.
Referenced by add_iv_candidate_for_groups().
◆ add_iv_candidate_for_biv()
Adds candidates bases on the old induction variable IV.
References add_candidate(), add_candidate_1(), iv::base, build_int_cst(), fold_convert, gcc_assert, ggc_alloc(), gimple_bb(), iv::have_address_use, INTEGRAL_TYPE_P, IP_ORIGINAL, loop_latch_edge(), iv::no_overflow, iv::nonlin_use, NULL, PHI_ARG_DEF_FROM_EDGE, POINTER_TYPE_P, size_int, sizetype, iv::ssa_name, SSA_NAME_DEF_STMT, iv::step, TREE_TYPE, and TYPE_PRECISION.
Referenced by add_iv_candidate_for_bivs().
◆ add_iv_candidate_for_bivs()
|
static |
Adds candidates based on the old induction variables.
References add_iv_candidate_for_biv(), iv::biv_p, EXECUTE_IF_SET_IN_BITMAP, i, integer_zerop(), version_info::iv, iv::step, and ver_info().
Referenced by find_iv_candidates().
◆ add_iv_candidate_for_doloop()
|
static |
Add one doloop dedicated IV candidate: - Base is (may_be_zero ? 1 : (niter + 1)). - Step is -1.
References add_candidate(), niter_desc::assumptions, build_int_cst(), COMPARISON_CLASS_P, compute_doloop_base_on_mode(), fold_build2, fold_build3, gcc_assert, ggc_alloc(), integer_zerop(), niter_desc::niter, niter_for_single_dom_exit(), NULL, NULL_TREE, rewrite_to_non_trapping_overflow(), targetm, TREE_CODE, TREE_TYPE, TYPE_MODE, and unshare_expr().
Referenced by find_iv_candidates().
◆ add_iv_candidate_for_groups()
|
static |
Adds candidates based on the uses.
References add_iv_candidate_derived_from_uses(), add_iv_candidate_for_use(), gcc_assert, i, NULL, and iv_group::vuses.
Referenced by find_iv_candidates().
◆ add_iv_candidate_for_use()
Adds candidates based on the value of USE's iv.
References add_autoinc_candidates(), add_candidate(), address_p(), iv::base, iv::base_object, build_int_cst(), fold_convert, ggc_alloc(), integer_zerop(), NULL, offset, optimize_loop_for_speed_p(), POINTER_TYPE_P, poly_int_tree_p(), preferred_mem_scale_factor(), record_common_cand(), size_int, sizetype, split_constant_offset(), iv::step, STRIP_NOPS, strip_offset(), TREE_CODE, TREE_OPERAND, TREE_TYPE, lang_hooks_for_types::type_for_mode, type_has_mode_precision_p(), TYPE_MODE, TYPE_UNSIGNED, lang_hooks::types, and wide_int_to_tree().
Referenced by add_iv_candidate_for_groups().
◆ add_standard_iv_candidates()
|
static |
Adds standard iv candidates.
References add_candidate(), BITS_PER_WORD, build_int_cst(), integer_one_node, integer_type_node, integer_zero_node, long_integer_type_node, long_long_integer_type_node, NULL, and TYPE_PRECISION.
Referenced by find_iv_candidates().
◆ addr_offset_valid_p()
|
static |
References addr_list, gen_int_mode(), gen_raw_REG(), GET_MODE, ggc_alloc(), LAST_VIRTUAL_REGISTER, memory_address_addr_space_p(), NULL_RTX, offset, targetm, TREE_TYPE, TYPE_ADDR_SPACE, TYPE_MODE, vec_safe_grow_cleared(), vec_safe_length(), and XEXP.
Referenced by split_address_groups().
◆ address_p()
Return true if uses of type TYPE represent some form of address.
References USE_PTR_ADDRESS, and USE_REF_ADDRESS.
Referenced by add_iv_candidate_for_use(), autoinc_possible_for_pair(), get_computation_cost(), get_constraint_for_1(), get_constraint_for_component_ref(), get_constraint_for_ssa_var(), record_group_use(), rewrite_groups(), split_address_groups(), and split_small_address_groups_p().
◆ adjust_iv_update_pos()
Performs a peephole optimization to reorder the iv update statement with
a mem ref to enable instruction combining in later phases. The mem ref uses
the iv value before the update, so the reordering transformation requires
adjustment of the offset. CAND is the selected IV_CAND.
Example:
t = MEM_REF (base, iv1, 8, 16); // base, index, stride, offset
iv2 = iv1 + 1;
if (t < val) (1)
goto L;
goto Head;
directly propagating t over to (1) will introduce overlapping live range
thus increase register pressure. This peephole transform it into:
iv2 = iv1 + 1;
t = MEM_REF (base, iv2, 8, 8);
if (t < val)
goto L;
goto Head;
References dump_file, dump_flags, ggc_alloc(), gimple_assign_lhs(), gimple_bb(), gsi_end_p(), gsi_for_stmt(), gsi_last_nondebug_bb(), gsi_move_before(), gsi_prev_nondebug(), gsi_stmt(), IP_BEFORE_USE, IP_NORMAL, print_gimple_stmt(), SSA_NAME_DEF_STMT, TDF_DETAILS, and TREE_CODE.
Referenced by rewrite_use_address().
◆ adjust_setup_cost()
|
static |
Adjust the cost COST for being in loop setup rather than loop body. If we're optimizing for space, the loop setup overhead is constant; if we're optimizing for speed, amortize it over the per-iteration cost. If ROUND_UP_P is true, the result is round up rather than to zero when optimizing for speed.
References avg_loop_niter(), ggc_alloc(), INFTY, and optimize_loop_for_speed_p().
Referenced by determine_group_iv_cost_cond(), determine_iv_cost(), get_address_cost(), and get_computation_cost().
◆ alloc_iv()
|
static |
Allocates an induction variable with given initial value BASE and step STEP for loop LOOP. NO_OVERFLOW implies the iv doesn't overflow.
References aff_combination_to_tree(), iv::base, iv::base_object, iv::biv_p, contain_complex_addr_expr(), DECL_P, determine_base_object(), fold_convert, gcc_assert, ggc_alloc(), iv::have_address_use, iv_can_overflow_p(), iv::no_overflow, iv::nonlin_use, NULL, NULL_TREE, iv::ssa_name, iv::step, STRIP_NOPS, TREE_CODE, TREE_OPERAND, tree_to_aff_combination(), and TREE_TYPE.
Referenced by add_candidate_1(), find_address_like_use(), find_interesting_uses_address(), and set_iv().
◆ alloc_use_cost_map()
|
static |
Allocates the data structure mapping the (use, candidate) pairs to costs. If consider_all_candidates is true, we use a two-dimensional array, otherwise we allocate a simple list to every use.
References bitmap_count_bits(), ceil_log2(), iv_group::cost_map, ggc_alloc(), i, iv_group::n_map_members, and iv_group::related_cands.
Referenced by determine_group_iv_costs().
◆ allow_ip_end_pos_p()
Returns true if incrementing the induction variable at the end of the LOOP is allowed. The purpose is to avoid splitting latch edge with a biv increment, thus creating a jump, possibly confusing other optimization passes and leaving less freedom to scheduler. So we allow IP_END only if IP_NORMAL is not available (so we do not have a better alternative), or if the latch edge is already nonempty.
References empty_block_p(), ip_end_pos(), and ip_normal_pos().
Referenced by add_candidate(), and add_iv_candidate_derived_from_uses().
◆ analyze_and_mark_doloop_use()
| void analyze_and_mark_doloop_use | ( | struct ivopts_data * | data | ) |
For the targets which support doloop, to predict whether later RTL doloop transformation will perform on this loop, further detect the doloop use and mark the flag doloop_use_p if predicted.
References dump_file, dump_flags, find_doloop_use(), flow_loop_dump(), generic_predict_doloop_p(), ggc_alloc(), NULL, loop::num, TDF_DETAILS, and USHRT_MAX.
Referenced by tree_ssa_iv_optimize_loop().
◆ autoinc_possible_for_pair()
|
static |
Return true if get_computation_cost indicates that autoincrement is a possibility for the pair of USE and CAND, false otherwise.
References address_p(), get_computation_cost(), ggc_alloc(), and NULL.
Referenced by set_autoinc_for_original_candidates().
◆ avg_loop_niter()
|
inlinestatic |
Returns the expected number of loop iterations for LOOP. The average trip count is computed from profile data if it exists.
References estimated_stmt_executions_int(), ggc_alloc(), and likely_max_stmt_executions_int().
Referenced by adjust_setup_cost(), and create_new_ivs().
◆ cand_value_at()
|
static |
Computes value of candidate CAND at position AT in iteration DESC->NITER, and stores it to VAL.
References aff_combination_add(), aff_combination_convert(), aff_combination_mult(), iv::base, affine_iv::base, tree_niter_desc::bound, tree_niter_desc::cmp, tree_niter_desc::control, ggc_alloc(), integer_onep(), tree_niter_desc::niter, affine_iv::no_overflow, POINTER_TYPE_P, sizetype, iv::step, affine_iv::step, stmt_after_increment(), TREE_CODE, TREE_OPERAND, tree_to_aff_combination(), TREE_TYPE, and unsigned_type_for().
Referenced by may_eliminate_iv().
◆ cheaper_cost_pair()
Returns true if A is a cheaper cost pair than B.
Referenced by cheaper_cost_with_cand(), compare_cost_pair(), and iv_ca_add_group().
◆ cheaper_cost_with_cand()
|
static |
Check if CAND_IDX is a candidate other than OLD_CAND and has cheaper local cost for GROUP than BEST_CP. Return pointer to the corresponding cost_pair, otherwise just return BEST_CP.
References cheaper_cost_pair(), gcc_assert, get_group_iv_cost(), ggc_alloc(), and NULL.
Referenced by iv_ca_replace().
◆ common_cand_cmp()
Comparison function used to sort common candidates.
References ggc_alloc().
Referenced by add_iv_candidate_derived_from_uses().
◆ compare_cost_pair()
Compare if A is a more expensive cost pair than B. Return 1, 0 and -1 for more expensive, equal and cheaper respectively.
References a, b, and cheaper_cost_pair().
Referenced by iv_ca_extend().
◆ computation_cost()
Determines cost of the computation of EXPR.
References address_cost(), crtl, current_function_decl, default_rtl_profile(), end_sequence(), expand_expr(), EXPAND_NORMAL, cgraph_node::frequency, cgraph_node::get(), get_insns(), ggc_alloc(), LAST_VIRTUAL_REGISTER, MEM_P, NODE_FREQUENCY_NORMAL, NULL, NULL_RTX, prepare_decl_rtl(), REG_P, seq_cost(), set_src_cost(), start_sequence(), TREE_TYPE, TYPE_ADDR_SPACE, TYPE_MODE, walk_tree, and XEXP.
Referenced by force_expr_to_var_cost().
◆ compute_doloop_base_on_mode()
|
static |
If PREFERRED_MODE is suitable and profitable, use the preferred PREFERRED_MODE to compute doloop iv base from niter: base = niter + 1.
References build_int_cst(), fold_build2, fold_convert, gcc_assert, ggc_alloc(), wi::ltu_p(), wi::max_value(), TREE_CODE, TREE_TYPE, lang_hooks_for_types::type_for_mode, TYPE_PRECISION, lang_hooks::types, unshare_expr(), and UNSIGNED.
Referenced by add_iv_candidate_for_doloop().
◆ constant_multiple_of()
|
static |
If we can prove that TOP = cst * BOT for some constant cst, store cst to MUL and return true. Otherwise return false. The returned value is always sign-extended, regardless of the signedness of TOP and BOT.
References constant_multiple_of(), wi::divmod_trunc(), ggc_alloc(), operand_equal_p(), POLY_INT_CST_P, wi::sext(), SIGNED, STRIP_NOPS, wi::to_poly_widest(), wi::to_wide(), wi::to_widest(), TREE_CODE, TREE_OPERAND, TREE_TYPE, and TYPE_PRECISION.
Referenced by constant_multiple_of(), get_computation_aff_1(), and get_debug_computation_at().
◆ contain_complex_addr_expr()
Return true if address expression with non-DECL_P operand appears in EXPR.
References contain_complex_addr_expr(), DECL_P, ggc_alloc(), STRIP_NOPS, TREE_CODE, and TREE_OPERAND.
Referenced by alloc_iv(), and contain_complex_addr_expr().
◆ contains_abnormal_ssa_name_p()
Returns true if EXPR contains a ssa name that occurs in an abnormal phi node.
References contains_abnormal_ssa_name_p_1(), NULL, NULL_TREE, and walk_tree_without_duplicates.
Referenced by can_unroll_loop_p(), final_value_replacement_loop(), find_bivs(), find_givs_in_stmt_scev(), and niter_for_exit().
◆ contains_abnormal_ssa_name_p_1()
walk_tree callback for contains_abnormal_ssa_name_p.
References EXPR_P, ggc_alloc(), NULL_TREE, SSA_NAME_OCCURS_IN_ABNORMAL_PHI, and TREE_CODE.
Referenced by contains_abnormal_ssa_name_p().
◆ create_new_iv()
Creates a new induction variable corresponding to CAND.
References create_iv(), find_edge(), find_interesting_uses_op(), gcc_assert, ggc_alloc(), gimple_add_tmp_var(), gsi_after_labels(), gsi_bb(), gsi_end_p(), gsi_for_stmt(), gsi_last_bb(), gsi_stmt(), IP_AFTER_USE, IP_BEFORE_USE, IP_END, ip_end_pos(), IP_NORMAL, ip_normal_pos(), IP_ORIGINAL, name_info(), NULL, version_info::preserve_biv, iv_group::selected, split_edge(), stmt_ends_bb_p(), and unshare_expr().
Referenced by create_new_ivs().
◆ create_new_ivs()
Creates new induction variables described in SET.
References avg_loop_niter(), bitmap_count_bits(), create_new_iv(), dump_cand(), dump_file, dump_flags, EXECUTE_IF_SET_IN_BITMAP, ggc_alloc(), HOST_WIDE_INT_PRINT_DEC, i, LOCATION_FILE, LOCATION_LINE, TDF_DETAILS, and UNKNOWN_LOCATION.
Referenced by tree_ssa_iv_optimize_loop().
◆ determine_base_object()
|
static |
Returns a memory object to that EXPR points with caching. Return NULL if we are able to determine that it does not point to any such object; specially return integer_zero_node if EXPR contains multiple base objects.
References determine_base_object_1(), ggc_alloc(), NULL, NULL_TREE, and walk_tree_without_duplicates.
Referenced by alloc_iv().
◆ determine_base_object_1()
walk_tree callback for determine_base_object.
References build_fold_addr_expr, EXPR_P, fold_convert, get_base_address(), ggc_alloc(), integer_zero_node, NULL_TREE, POINTER_TYPE_P, ptr_type_node, TREE_CODE, TREE_OPERAND, and TREE_TYPE.
Referenced by determine_base_object().
◆ determine_common_wider_type()
If A is (TYPE) BA and B is (TYPE) BB, and the types of BA and BB have the same precision that is at least as wide as the precision of TYPE, stores BA to A and BB to B, and returns the type of BA. Otherwise, returns the type of A and B.
References a, b, CONVERT_EXPR_P, ggc_alloc(), NULL, TREE_OPERAND, TREE_TYPE, and TYPE_PRECISION.
Referenced by get_computation_aff_1().
◆ determine_group_iv_cost()
|
static |
Determines cost of computing uses in GROUP with CAND. Returns false if USE cannot be represented with CAND.
References determine_group_iv_cost_address(), determine_group_iv_cost_cond(), determine_group_iv_cost_generic(), gcc_unreachable, iv_group::type, USE_COMPARE, USE_NONLINEAR_EXPR, USE_PTR_ADDRESS, and USE_REF_ADDRESS.
Referenced by determine_group_iv_costs().
◆ determine_group_iv_cost_address()
|
static |
Determines cost of computing uses in GROUP with CAND in addresses.
References BITMAP_ALLOC, bitmap_set_bit, get_computation_cost(), ggc_alloc(), i, infinite_cost, IP_AFTER_USE, IP_BEFORE_USE, no_cost, NULL, NULL_TREE, comp_cost::scratch, set_group_iv_cost(), and iv_group::vuses.
Referenced by determine_group_iv_cost().
◆ determine_group_iv_cost_cond()
|
static |
Determines cost of computing the use in GROUP with CAND in a condition.
References adjust_setup_cost(), BITMAP_ALLOC, bitmap_clear(), bitmap_count_bits(), BITMAP_FREE, bitmap_set_bit, tree_niter_desc::bound, comp, COMP_IV_ELIM, COMP_IV_NA, comp_cost::cost, iv_group::doloop_p, extract_cond_operands(), find_inv_vars(), force_var_cost(), gcc_assert, get_computation_cost(), get_loop_invariant_expr(), ggc_alloc(), infinite_cost, integer_zerop(), may_eliminate_iv(), no_cost, NULL, NULL_TREE, operand_equal_p(), parm_decl_cost(), set_group_iv_cost(), TREE_CODE, and iv_group::vuses.
Referenced by determine_group_iv_cost().
◆ determine_group_iv_cost_generic()
|
static |
Determines cost of computing the use in GROUP with CAND in a generic expression.
References BITMAP_ALLOC, bitmap_set_bit, get_computation_cost(), ggc_alloc(), comp_cost::infinite_cost_p(), IP_ORIGINAL, no_cost, NULL, NULL_TREE, operand_equal_p(), set_group_iv_cost(), and iv_group::vuses.
Referenced by determine_group_iv_cost().
◆ determine_group_iv_costs()
|
static |
Determines costs of computing use of iv with an iv candidate.
References alloc_use_cost_map(), BITMAP_ALLOC, bitmap_and_compl_into(), bitmap_clear(), bitmap_empty_p(), BITMAP_FREE, bitmap_print(), bitmap_set_bit, cost_pair::cand, comp_cost::complexity, comp_cost::cost, cost_pair::cost, iv_group::cost_map, determine_group_iv_cost(), dump_file, dump_flags, EXECUTE_IF_SET_IN_BITMAP, ggc_alloc(), version_info::has_nonlin_use, i, iv_cand::id, comp_cost::infinite_cost_p(), cost_pair::inv_exprs, version_info::inv_id, cost_pair::inv_vars, iv_group::n_map_members, version_info::name, NULL, PRId64, print_generic_expr(), iv_group::related_cands, sort_iv_inv_expr_ent(), TDF_DETAILS, TDF_SLIM, and ver_info().
Referenced by tree_ssa_iv_optimize_loop().
◆ determine_iv_cost()
Determines cost of the candidate CAND.
References add_cost(), adjust_setup_cost(), COSTS_N_INSNS, DECL_ARTIFICIAL, empty_block_p(), force_var_cost(), gcc_assert, ggc_alloc(), IP_END, ip_end_pos(), IP_ORIGINAL, NULL, SSA_NAME_VAR, TREE_TYPE, and TYPE_MODE.
Referenced by determine_iv_costs().
◆ determine_iv_costs()
|
static |
Determines costs of computation of the candidates.
References determine_iv_cost(), dump_file, dump_flags, ggc_alloc(), i, and TDF_DETAILS.
Referenced by tree_ssa_iv_optimize_loop().
◆ determine_scaling_factor()
|
static |
References basic_block_def::aux, cfun, COST_SCALING_FACTOR_BOUND, basic_block_def::count, count, ggc_alloc(), i, and profile_count::to_frequency().
Referenced by tree_ssa_iv_optimize_loop().
◆ determine_set_costs()
|
static |
For each size of the induction variable set determine the penalty.
References dump_file, dump_flags, EXECUTE_IF_SET_IN_BITMAP, get_iv(), ggc_alloc(), gsi_end_p(), gsi_next(), gsi_start_phis(), version_info::has_nonlin_use, loop::header, INTEGRAL_TYPE_P, version_info::inv_id, ivopts_estimate_reg_pressure(), gphi_iterator::phi(), PHI_RESULT, POINTER_TYPE_P, target_avail_regs, target_clobbered_regs, target_reg_cost, target_spill_cost, TDF_DETAILS, TREE_TYPE, ver_info(), and virtual_operand_p().
Referenced by tree_ssa_iv_optimize_loop().
◆ difference_cannot_overflow_p()
|
static |
Returns true if we can prove that BASE - OFFSET does not overflow. For now,
we only detect the situation that BASE = SOMETHING + OFFSET, where the
calculation is performed in non-wrapping type.
TODO: More generally, we could test for the situation that
BASE = SOMETHING + OFFSET' and OFFSET is between OFFSET' and zero.
This would require knowing the sign of OFFSET.
References aff_combination_add(), aff_combination_scale(), aff_combination_zero_p(), expand_simple_operations(), get_gimple_rhs_class(), ggc_alloc(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), GIMPLE_BINARY_RHS, nowrap_type_p(), offset, SSA_NAME_DEF_STMT, TREE_CODE, TREE_OPERAND, tree_to_aff_combination_expand(), and TREE_TYPE.
Referenced by iv_elimination_compare_lt().
◆ dump_cand()
Dumps information about induction variable candidate CAND to FILE.
References dump_bitmap(), dump_iv(), ggc_alloc(), IP_AFTER_USE, IP_BEFORE_USE, IP_END, IP_NORMAL, IP_ORIGINAL, print_generic_expr(), and TDF_SLIM.
Referenced by add_candidate_1(), and create_new_ivs().
◆ dump_groups()
| void dump_groups | ( | FILE * | file, |
| struct ivopts_data * | data ) |
Dumps information about the uses to FILE.
References dump_use(), gcc_assert, ggc_alloc(), i, iv_group::id, iv_group::type, USE_COMPARE, USE_NONLINEAR_EXPR, USE_PTR_ADDRESS, USE_REF_ADDRESS, and iv_group::vuses.
Referenced by find_interesting_uses().
◆ dump_iv()
Dumps information about the induction variable IV to FILE. Don't dump variable's name if DUMP_NAME is FALSE. The information is dumped with preceding spaces indicated by INDENT_LEVEL.
References iv::base, iv::base_object, iv::biv_p, ggc_alloc(), iv::no_overflow, print_generic_expr(), iv::ssa_name, iv::step, TDF_SLIM, and TREE_TYPE.
Referenced by dump_cand(), dump_use(), and find_induction_variables().
◆ dump_use()
Dumps information about the USE to FILE.
References dump_iv(), ggc_alloc(), print_generic_expr(), print_gimple_stmt(), and TDF_SLIM.
Referenced by dump_groups().
◆ expr_invariant_in_loop_p()
Returns true if expression EXPR is obviously invariant in LOOP, i.e. if all its operands are defined outside of the LOOP. LOOP should not be the function body.
References expr_invariant_in_loop_p(), EXPR_P, flow_bb_inside_loop_p(), gcc_assert, ggc_alloc(), gimple_bb(), i, is_gimple_min_invariant(), loop_depth(), SSA_NAME_DEF_STMT, TREE_CODE, TREE_OPERAND, and TREE_OPERAND_LENGTH.
Referenced by analyze_and_compute_bitop_with_inv_effect(), evolution_function_is_invariant_rec_p(), expr_invariant_in_loop_p(), gather_memory_references_ref(), idx_find_step(), ifcvt_can_hoist(), infer_loop_bounds_from_pointer_arith(), rewrite_use_nonlinear_expr(), unroll_jam_possible_p(), vect_analyze_loop_form(), vect_can_advance_ivs_p(), and vect_check_gather_scatter().
◆ extract_cond_operands()
|
static |
Given a condition in statement STMT, checks whether it is a compare of an induction variable and an invariant. If this is the case, CONTROL_VAR is set to location of the iv, BOUND to the location of the invariant, IV_VAR and IV_BOUND are set to the corresponding induction variable descriptions, and true is returned. If this is not the case, CONTROL_VAR and BOUND are set to the arguments of the condition and false is returned.
References COMP_IV_ELIM, COMP_IV_EXPR, COMP_IV_EXPR_2, COMP_IV_NA, end(), get_iv(), ggc_alloc(), gimple_assign_rhs1_ptr(), gimple_assign_rhs2_ptr(), gimple_cond_lhs_ptr(), gimple_cond_rhs_ptr(), integer_zero_node, integer_zerop(), and TREE_CODE.
Referenced by determine_group_iv_cost_cond(), and find_interesting_uses_cond().
◆ extract_single_var_from_expr()
Return the first non-invariant ssa var found in EXPR.
References expr, extract_single_var_from_expr(), ggc_alloc(), i, IS_EXPR_CODE_CLASS, is_gimple_min_invariant(), NULL, TREE_CODE, TREE_CODE_CLASS, TREE_OPERAND, and TREE_OPERAND_LENGTH.
Referenced by extract_single_var_from_expr(), find_bivs(), and find_givs_in_stmt_scev().
◆ find_address_like_use()
|
static |
IV is a (non-address) iv that describes operand *OP_P of STMT. Return true if the operand will become an address when STMT is expanded and record the associated address use if so.
References alloc_iv(), iv::base, iv::base_object, get_mem_type_for_internal_fn(), ggc_alloc(), gimple_call_internal_p(), NULL_TREE, record_group_use(), iv::step, ifs_ivopts_data::stmt, and USE_PTR_ADDRESS.
Referenced by find_interesting_uses_stmt().
◆ find_bivs()
|
static |
Finds basic ivs.
References iv::base, contains_abnormal_ssa_name_p(), convert_to_ptrofftype, expand_simple_operations(), extract_single_var_from_expr(), fold_convert, gsi_end_p(), gsi_next(), gsi_start_phis(), loop::header, integer_zerop(), loop_preheader_edge(), iv::no_overflow, gphi_iterator::phi(), PHI_ARG_DEF_FROM_EDGE, PHI_RESULT, POINTER_TYPE_P, set_iv(), simple_iv(), SSA_NAME_OCCURS_IN_ABNORMAL_PHI, iv::step, TREE_TYPE, type(), and virtual_operand_p().
Referenced by find_induction_variables().
◆ find_deriving_biv_for_expr()
Given expression EXPR which computes inductive values with respect to loop recorded in DATA, this function returns biv from which EXPR is derived by tracing definition chains of ssa variables in EXPR.
References iv::biv_p, CASE_CONVERT, find_deriving_biv_for_expr(), FOR_EACH_PHI_ARG, gcc_fallthrough, get_gimple_rhs_class(), get_iv(), ggc_alloc(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), gimple_bb(), gimple_phi_result(), GIMPLE_SINGLE_RHS, i, integer_zerop(), IS_EXPR_CODE_CLASS, is_gimple_min_invariant(), NULL, NULL_TREE, SSA_NAME_DEF_STMT, SSA_OP_USE, iv::step, TREE_CODE, TREE_CODE_CLASS, TREE_OPERAND, TREE_OPERAND_LENGTH, USE_FROM_PTR, and virtual_operand_p().
Referenced by find_deriving_biv_for_expr(), and idx_find_step().
◆ find_doloop_use()
|
static |
Find doloop comparison use and set its doloop_p on if found.
References iv_group::doloop_p, dump_file, dump_flags, empty_block_p(), extract_true_false_edges_from_block(), gcc_assert, ggc_alloc(), gimple_bb(), i, loop::latch, print_gimple_stmt(), iv_use::stmt, TDF_DETAILS, iv_group::type, USE_COMPARE, and iv_group::vuses.
Referenced by analyze_and_mark_doloop_use().
◆ find_givs()
|
static |
Finds general ivs.
References find_givs_in_bb(), i, and loop::num_nodes.
Referenced by find_induction_variables().
◆ find_givs_in_bb()
|
static |
Finds general ivs in basic block BB.
References find_givs_in_stmt(), ggc_alloc(), gsi_end_p(), gsi_next(), gsi_start_bb(), and gsi_stmt().
Referenced by find_givs().
◆ find_givs_in_stmt()
|
static |
Finds general ivs in statement STMT.
References iv::base, find_givs_in_stmt_scev(), gimple_assign_lhs(), iv::no_overflow, set_iv(), and iv::step.
Referenced by find_givs_in_bb().
◆ find_givs_in_stmt_scev()
|
static |
Checks whether STMT defines a linear induction variable and stores its parameters to IV.
References iv::base, cfun, contains_abnormal_ssa_name_p(), expand_simple_operations(), extract_single_var_from_expr(), ggc_alloc(), gimple_assign_lhs(), loop_containing_stmt(), NULL_TREE, simple_iv(), iv::step, stmt_could_throw_p(), and TREE_CODE.
Referenced by find_givs_in_stmt().
◆ find_induction_variables()
|
static |
For each ssa name defined in LOOP determines whether it is an induction variable and if so, its initial value and step.
References dump_file, dump_flags, dump_iv(), EXECUTE_IF_SET_IN_BITMAP, find_bivs(), find_givs(), ggc_alloc(), i, integer_zerop(), version_info::iv, mark_bivs(), tree_niter_desc::niter, niter_for_single_dom_exit(), print_generic_expr(), iv::step, TDF_DETAILS, TDF_SLIM, and ver_info().
Referenced by tree_ssa_iv_optimize_loop().
◆ find_interesting_uses()
|
static |
Finds uses of the induction variables that are interesting.
References cfun, dump_file, dump_flags, dump_groups(), EXIT_BLOCK_PTR_FOR_FN, find_interesting_uses_outside(), find_interesting_uses_stmt(), flow_bb_inside_loop_p(), FOR_EACH_EDGE, ggc_alloc(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_start_phis(), gsi_stmt(), i, is_gimple_debug(), split_address_groups(), basic_block_def::succs, and TDF_DETAILS.
Referenced by tree_ssa_iv_optimize_loop().
◆ find_interesting_uses_address()
|
static |
Finds addresses in *OP_P inside STMT.
References alloc_iv(), build_fold_addr_expr, build_pointer_type(), fold_binary, fold_build2, for_each_index(), get_iv(), ggc_alloc(), gimple_has_volatile_ops(), handled_component_p(), idx_find_step(), idx_record_use(), integer_zerop(), ifs_ivopts_data::ivopts_data, may_be_nonaddressable_p(), may_be_unaligned_p(), NULL_TREE, record_group_use(), size_zero_node, ifs_ivopts_data::step, ifs_ivopts_data::stmt, TMR_BASE, TMR_INDEX, TMR_INDEX2, TMR_STEP, TREE_CODE, tree_mem_ref_addr(), TREE_OPERAND, TREE_TYPE, unshare_expr(), and USE_REF_ADDRESS.
Referenced by find_interesting_uses_stmt().
◆ find_interesting_uses_cond()
|
static |
Checks whether the condition in STMT is interesting and if so, records it.
References COMP_IV_EXPR_2, COMP_IV_NA, extract_cond_operands(), find_interesting_uses_op(), ggc_alloc(), NULL_TREE, record_group_use(), and USE_COMPARE.
Referenced by find_interesting_uses_stmt().
◆ find_interesting_uses_op()
Checks whether the use OP is interesting and if so, records it.
References gcc_assert, get_iv(), ggc_alloc(), integer_zerop(), is_gimple_assign(), iv::nonlin_use, NULL, NULL_TREE, record_group_use(), record_invariant(), SSA_NAME_DEF_STMT, iv::step, iv_use::stmt, TREE_CODE, iv_use::type, and USE_NONLINEAR_EXPR.
Referenced by create_new_iv(), find_interesting_uses_cond(), find_interesting_uses_outside(), find_interesting_uses_stmt(), and idx_record_use().
◆ find_interesting_uses_outside()
|
static |
Finds interesting uses of induction variables outside of loops on loop exit edge EXIT.
References find_interesting_uses_op(), gsi_end_p(), gsi_next(), gsi_start_phis(), gphi_iterator::phi(), PHI_ARG_DEF_FROM_EDGE, and virtual_operand_p().
Referenced by find_interesting_uses().
◆ find_interesting_uses_stmt()
|
static |
Finds interesting uses of induction variables in the statement STMT.
References find_address_like_use(), find_interesting_uses_address(), find_interesting_uses_cond(), find_interesting_uses_op(), find_invariants_stmt(), FOR_EACH_PHI_OR_STMT_USE, get_gimple_rhs_class(), get_iv(), ggc_alloc(), gimple_assign_lhs_ptr(), gimple_assign_rhs1_ptr(), gimple_assign_rhs_code(), gimple_bb(), GIMPLE_SINGLE_RHS, integer_zerop(), is_gimple_assign(), is_gimple_val(), PHI_RESULT, REFERENCE_CLASS_P, SSA_OP_USE, iv::step, tcc_comparison, TREE_CODE, TREE_CODE_CLASS, and USE_FROM_PTR.
Referenced by find_interesting_uses().
◆ find_inv_vars()
|
inlinestatic |
Records invariants in *EXPR_P. INV_VARS is the bitmap to that we should store it.
References find_inv_vars_cb(), ggc_alloc(), walk_tree_data::inv_vars, NULL, and walk_tree.
Referenced by add_candidate_1(), determine_group_iv_cost_cond(), and force_var_cost().
◆ find_inv_vars_cb()
Callback function for walk_tree, it records invariants and symbol reference in *EXPR_P. DATA is the structure storing result info.
References BITMAP_ALLOC, bitmap_set_bit, build_int_cst(), flow_bb_inside_loop_p(), ggc_alloc(), gimple_bb(), version_info::has_nonlin_use, idata, version_info::inv_id, version_info::iv, name_info(), NULL, NULL_TREE, POINTER_TYPE_P, record_invariant(), set_iv(), sizetype, SSA_NAME_DEF_STMT, TREE_CODE, and TREE_TYPE.
Referenced by find_inv_vars().
◆ find_invariants_stmt()
|
static |
Finds and records invariants used in STMT.
References FOR_EACH_PHI_OR_STMT_USE, ggc_alloc(), record_invariant(), SSA_OP_USE, ifs_ivopts_data::stmt, and USE_FROM_PTR.
Referenced by find_interesting_uses_stmt().
◆ find_iv_candidates()
|
static |
Finds the candidates for the induction variables.
References add_iv_candidate_for_bivs(), add_iv_candidate_for_doloop(), add_iv_candidate_for_groups(), add_standard_iv_candidates(), dump_bitmap(), dump_file, dump_flags, ggc_alloc(), i, iv_group::id, record_important_candidates(), relate_compare_use_with_all_cands(), iv_group::related_cands, set_autoinc_for_original_candidates(), and TDF_DETAILS.
Referenced by tree_ssa_iv_optimize_loop().
◆ find_optimal_iv_set()
|
static |
References cost_pair::cand, comp_cost::complexity, comp_cost::cost, iv_ca::cost, dump_file, dump_flags, find_optimal_iv_set_1(), ggc_alloc(), i, infinite_cost, iv_ca_cand_for_group(), iv_ca_cost(), iv_ca_free(), NULL, PRId64, iv_group::selected, and TDF_DETAILS.
Referenced by tree_ssa_iv_optimize_loop().
◆ find_optimal_iv_set_1()
Attempts to find the optimal set of induction variables. We do simple greedy heuristic -- we try to replace at most one candidate in the selected solution and remove the unused ivs while this improves the cost.
References dump_file, dump_flags, get_initial_solution(), ggc_alloc(), iv_ca_cost(), iv_ca_dump(), iv_ca_free(), NULL, TDF_DETAILS, and try_improve_iv_set().
Referenced by find_optimal_iv_set().
◆ find_ssa_undef()
Return *TP if it is an SSA_NAME marked with TREE_VISITED, i.e., as unsuitable as ivopts candidates for potentially involving undefined behavior.
References EXPR_P, ggc_alloc(), NULL, ssa_name_any_use_dominates_bb_p(), ssa_name_maybe_undef_p(), and TREE_CODE.
Referenced by add_candidate_1().
◆ force_expr_to_var_cost()
Estimates cost of forcing expression EXPR into a variable.
References add_cost(), address_cost(), build1(), build_int_cst(), build_pointer_type(), CASE_CONVERT, computation_cost(), CONSTANT_CLASS_P, convert_cost(), create_tmp_var_raw(), cst_and_fits_in_hwi(), dump_file, dump_flags, fold_build_pointer_plus_hwi, force_expr_to_var_cost(), gcc_unreachable, get_shiftadd_cost(), ggc_alloc(), i, int_cst_value(), integer_pow2p(), integer_type_node, is_gimple_min_invariant(), mult, mult_by_coeff_cost(), no_cost, NULL, NULL_TREE, poly_int_tree_p(), produce_memory_decl_rtl(), SET_DECL_RTL, SSA_VAR_P, STRIP_NOPS, target_spill_cost, TDF_DETAILS, TREE_CODE, TREE_OPERAND, TREE_STATIC, TREE_TYPE, TYPE_MODE, and VAR_P.
Referenced by force_expr_to_var_cost(), force_var_cost(), and get_shiftadd_cost().
◆ force_var_cost()
Estimates cost of forcing EXPR into a variable. INV_VARS is a set of the invariants the computation depends on.
References find_inv_vars(), force_expr_to_var_cost(), and no_cost.
Referenced by determine_group_iv_cost_cond(), determine_iv_cost(), get_address_cost(), and get_computation_cost().
◆ free_loop_data()
|
static |
Frees data allocated by the optimization of a single loop.
References bitmap_clear(), BITMAP_FREE, iv_group::cost_map, decl_rtl_to_reset, EXECUTE_IF_SET_IN_BITMAP, FOR_EACH_VEC_ELT, free(), free_tree_niter_desc(), ggc_alloc(), version_info::has_nonlin_use, i, cost_pair::inv_exprs, version_info::inv_id, cost_pair::inv_vars, version_info::iv, iv_group::n_map_members, NULL, NULL_RTX, num_ssa_names, version_info::preserve_biv, iv_group::related_cands, SET_DECL_RTL, ver_info(), and iv_group::vuses.
Referenced by tree_ssa_iv_optimize_finalize(), and tree_ssa_iv_optimize_loop().
◆ free_tree_niter_desc()
Frees memory occupied by class tree_niter_desc in *VALUE. Callback for hash_map::traverse.
References free().
Referenced by free_loop_data().
◆ generic_predict_doloop_p()
|
static |
Predict whether the given loop will be transformed in the RTL doloop_optimize pass. Attempt to duplicate some doloop_optimize checks. This is only for target independent checks, see targetm.predict_doloop_p for the target dependent ones. Note that according to some initial investigation, some checks like costly niter check and invalid stmt scanning don't have much gains among general cases, so keep this as simple as possible first. Some RTL specific checks seems unable to be checked in gimple, if any new checks or easy checks _are_ missing here, please add them.
References dump_file, dump_flags, get_estimated_loop_iterations_int(), get_likely_max_loop_iterations_int(), ggc_alloc(), niter_for_exit(), single_dom_exit(), targetm, and TDF_DETAILS.
Referenced by analyze_and_mark_doloop_use().
◆ generic_type_for()
Returns variant of TYPE that can be used as base for different uses. We return unsigned type with the same precision, which avoids problems with overflows.
References POINTER_TYPE_P, type(), TYPE_UNSIGNED, and unsigned_type_for().
Referenced by add_candidate_1().
◆ get_address_cost()
|
static |
Return cost of computing USE's address expression by using CAND. AFF_INV and AFF_VAR represent invariant and variant parts of the address expression, respectively. If AFF_INV is simple, store the loop invariant variables which are depended by it in INV_VARS; if AFF_INV is complicated, handle it as a new invariant expression and record it in INV_EXPR. RATIO indicates multiple times between steps of USE and CAND. If CAN_AUTOINC is nonNULL, store boolean value to it indicating if this is an auto-increment address.
References add_cost(), addr_for_mem_ref(), address_cost(), adjust_setup_cost(), aff_combination_add_elt(), aff_combination_const_p(), aff_combination_singleton_var_p(), aff_combination_to_tree(), aff_combination_zero_p(), bitmap_clear(), force_var_cost(), gcc_assert, get_address_cost_ainc(), get_loop_invariant_expr(), ggc_alloc(), gimple_call_internal_fn(), gimple_call_internal_p(), integer_one_node, integer_zerop(), memory_address_addr_space_p(), move_fixed_address_to_symbol(), mult_by_coeff_cost(), no_cost, NULL, NULL_TREE, ptrdiff_tree_p(), sizetype, stmt_after_increment(), TREE_TYPE, TYPE_ADDR_SPACE, TYPE_MODE, USE_PTR_ADDRESS, valid_mem_ref_p(), and wide_int_to_tree().
Referenced by get_computation_cost().
◆ get_address_cost_ainc()
|
static |
References address_cost(), AINC_POST_DEC, AINC_POST_INC, AINC_PRE_DEC, AINC_PRE_INC, gcc_assert, gen_raw_REG(), GET_MODE_SIZE(), ggc_alloc(), infinite_cost, INFTY, known_eq, LAST_VIRTUAL_REGISTER, memory_address_addr_space_p(), NULL, USE_LOAD_POST_DECREMENT, USE_LOAD_POST_INCREMENT, USE_LOAD_PRE_DECREMENT, USE_LOAD_PRE_INCREMENT, USE_STORE_POST_DECREMENT, USE_STORE_POST_INCREMENT, USE_STORE_PRE_DECREMENT, and USE_STORE_PRE_INCREMENT.
Referenced by get_address_cost().
◆ get_alias_ptr_type_for_ptr_address()
Return the alias pointer type that should be used for a MEM_REF associated with USE, which has type USE_PTR_ADDRESS.
References gcc_assert, gcc_unreachable, ggc_alloc(), gimple_call_arg(), gimple_call_arg_ptr(), gimple_call_internal_fn(), and TREE_TYPE.
Referenced by rewrite_use_address().
◆ get_computation_aff()
|
static |
Determines the expression by that USE is expressed from induction variable CAND at statement AT in LOOP. The expression is stored in a decomposed form into AFF. Returns false if USE cannot be expressed using CAND.
References aff_combination_add(), get_computation_aff_1(), and ggc_alloc().
Referenced by get_computation_at(), and rewrite_use_address().
◆ get_computation_aff_1()
|
static |
Determines the expression by that USE is expressed from induction variable CAND at statement AT in LOOP. The expression is stored in two parts in a decomposed form. The invariant part is stored in AFF_INV; while variant part in AFF_VAR. Store ratio of CAND.step over USE.step in PRAT if it's non-null. Returns false if USE cannot be expressed using CAND.
References aff_combination_add(), aff_combination_convert(), aff_combination_scale(), constant_multiple_of(), CONVERT_EXPR_P, determine_common_wider_type(), fold_convert, gcc_assert, ggc_alloc(), gimple_assign_lhs(), IP_ORIGINAL, is_gimple_assign(), NULL, poly_int_tree_p(), stmt_after_increment(), TREE_OPERAND, tree_to_aff_combination(), TREE_TYPE, TYPE_PRECISION, unsigned_type_for(), and var_at_stmt().
Referenced by get_computation_aff(), get_computation_cost(), and rewrite_use_nonlinear_expr().
◆ get_computation_at()
|
static |
Determines the expression by that USE is expressed from induction variable CAND at statement AT in LOOP. The computation is unshared.
References aff_combination_to_tree(), fold_convert, get_computation_aff(), get_use_type(), ggc_alloc(), NULL_TREE, and unshare_aff_combination().
Referenced by get_debug_computation_at(), and rewrite_use_compare().
◆ get_computation_cost()
|
static |
Determines the cost of the computation by that USE is expressed from induction variable CAND. If ADDRESS_P is true, we just need to create an address from it, otherwise we want to get it into register. A set of invariants we depend on is stored in INV_VARS. If CAN_AUTOINC is nonnull, use it to record whether autoinc addressing is likely. If INV_EXPR is nonnull, record invariant expr entry in it.
References add_cost(), address_p(), adjust_setup_cost(), aff_combination_const_p(), aff_combination_convert(), aff_combination_singleton_var_p(), aff_combination_to_tree(), aff_combination_type(), aff_combination_zero_p(), bitmap_clear(), CONSTANT_CLASS_P, convert_cost(), comp_cost::cost, wi::fits_shwi_p(), force_var_cost(), get_address_cost(), get_computation_aff_1(), get_loop_invariant_expr(), get_scaled_computation_cost_at(), ggc_alloc(), gimple_bb(), infinite_cost, integer_zerop(), mult_by_coeff_cost(), no_cost, NULL, NULL_TREE, operand_equal_p(), optimize_bb_for_speed_p(), POINTER_TYPE_P, comp_cost::scratch, signed_type_for(), targetm, TREE_TYPE, TYPE_MODE, TYPE_PRECISION, and USE_NONLINEAR_EXPR.
Referenced by autoinc_possible_for_pair(), determine_group_iv_cost_address(), determine_group_iv_cost_cond(), and determine_group_iv_cost_generic().
◆ get_debug_computation_at()
|
static |
Like get_computation_at, but try harder, even if the computation is more expensive. Intended for debug stmts.
References constant_multiple_of(), wi::exact_log2(), wi::floor_log2(), fold_build1, fold_build2, fold_convert, get_computation_at(), ggc_alloc(), integer_pow2p(), wi::neg(), wi::neg_p(), NULL_TREE, POINTER_TYPE_P, sizetype, stmt_after_increment(), TREE_TYPE, TYPE_PRECISION, TYPE_UNSIGNED, unshare_expr(), unsigned_type_for(), var_at_stmt(), and wide_int_to_tree().
Referenced by remove_unused_ivs().
◆ get_group_iv_cost()
|
static |
Gets cost of (GROUP, CAND) pair.
References cost_pair::cand, iv_group::cost_map, ggc_alloc(), i, iv_group::n_map_members, and NULL.
Referenced by cheaper_cost_with_cand(), iv_ca_add_group(), iv_ca_extend(), iv_ca_narrow(), rewrite_use_compare(), and try_add_cand_for().
◆ get_initial_solution()
Finds an initial assignment of candidates to uses.
References ggc_alloc(), i, iv_ca_free(), iv_ca_new(), NULL, and try_add_cand_for().
Referenced by find_optimal_iv_set_1().
◆ get_iv()
Finds induction variable declaration for VAR.
References build_int_cst(), flow_bb_inside_loop_p(), gimple_bb(), INTEGRAL_TYPE_P, version_info::iv, name_info(), NULL, POINTER_TYPE_P, set_iv(), sizetype, SSA_NAME_DEF_STMT, and TREE_TYPE.
Referenced by determine_set_costs(), extract_cond_operands(), find_deriving_biv_for_expr(), find_interesting_uses_address(), find_interesting_uses_op(), find_interesting_uses_stmt(), idx_find_step(), mark_bivs(), and rewrite_use_nonlinear_expr().
◆ get_loop_invariant_expr()
|
static |
Get entry from invariant expr hash table for INV_EXPR. New entry
will be recorded if it doesn't exist yet. Given below two exprs:
inv_expr + cst1, inv_expr + cst2
It's hard to make decision whether constant part should be stripped
or not. We choose to not strip based on below facts:
1) We need to count ADD cost for constant part if it's stripped,
which isn't always trivial where this functions is called.
2) Stripping constant away may be conflict with following loop
invariant hoisting pass.
3) Not stripping constant away results in more invariant exprs,
which usually leads to decision preferring lower reg pressure.
References ggc_alloc(), iterative_hash_expr(), NULL, poly_int_tree_p(), STRIP_NOPS, and TREE_CODE.
Referenced by add_candidate_1(), determine_group_iv_cost_cond(), get_address_cost(), and get_computation_cost().
◆ get_mem_type_for_internal_fn()
CALL calls an internal function. If operand *OP_P will become an address when the call is expanded, return the type of the memory being addressed, otherwise return null.
References ggc_alloc(), gimple_call_arg(), gimple_call_arg_ptr(), gimple_call_internal_fn(), gimple_call_lhs(), internal_fn_stored_value_index(), NULL_TREE, and TREE_TYPE.
Referenced by find_address_like_use().
◆ get_scaled_computation_cost_at()
|
static |
Scale (multiply) the computed COST (except scratch part that should be hoisted out a loop) by header->frequency / AT->frequency, which makes expected cost more accurate.
References basic_block_def::aux, cfun, comp_cost::cost, dump_file, dump_flags, gcc_assert, ggc_alloc(), gimple_bb(), PRId64, comp_cost::scratch, and TDF_DETAILS.
Referenced by get_computation_cost().
◆ get_shiftadd_cost()
|
static |
Calculate the SPEED or size cost of shiftadd EXPR in MODE. MULT is the EXPR operand holding the shift. COST0 and COST1 are the costs for calculating the operands of EXPR. Returns true if successful, and returns the cost in COST.
References add_cost(), BITS_PER_WORD, exact_log2(), force_expr_to_var_cost(), GET_MODE_BITSIZE(), ggc_alloc(), int_cst_value(), is_gimple_val(), MIN, mult, operand_equal_p(), shift_cost(), shiftadd_cost(), shiftsub0_cost(), shiftsub1_cost(), STRIP_NOPS, TREE_CODE, and TREE_OPERAND.
Referenced by force_expr_to_var_cost().
◆ get_use_type()
Return the type of USE.
References build_pointer_type(), gcc_assert, ggc_alloc(), TREE_TYPE, type(), TYPE_ADDR_SPACE, and USE_REF_ADDRESS.
Referenced by get_computation_at(), rewrite_use_address(), and rewrite_use_nonlinear_expr().
◆ group_compare_offset()
Comparison function to sort group in ascending order of addr_offset.
References a, b, and ggc_alloc().
Referenced by split_small_address_groups_p().
◆ idx_find_step()
References array_ref_element_size(), array_ref_low_bound(), iv::base, iv::biv_p, component_ref_field_offset(), convert_affine_scev(), expr_invariant_in_loop_p(), find_deriving_biv_for_expr(), fold_build2, get_iv(), ggc_alloc(), integer_zerop(), iv::no_overflow, nowrap_type_p(), record_biv_for_address_use(), size_one_node, sizetype, iv::ssa_name, iv::step, TREE_CODE, TREE_TYPE, and TYPE_SIZE.
Referenced by find_interesting_uses_address().
◆ idx_record_use()
Records use in index IDX. Callback for for_each_index. Ivopts data object is passed to it in DATA.
References find_interesting_uses_op(), ggc_alloc(), TREE_CODE, and TREE_OPERAND.
Referenced by find_interesting_uses_address().
◆ iv_ca_add_group()
|
static |
Extend set IVS by expressing USE by some of the candidates in it if possible. Consider all important candidates if candidates in set IVS don't give any result.
References cheaper_cost_pair(), EXECUTE_IF_SET_IN_BITMAP, gcc_assert, get_group_iv_cost(), ggc_alloc(), i, iv_group::id, iv_ca_set_cp(), and NULL.
Referenced by try_add_cand_for().
◆ iv_ca_cand_for_group()
Returns candidate by that USE is expressed in IVS.
References ggc_alloc(), and iv_group::id.
Referenced by find_optimal_iv_set(), iv_ca_delta_commit(), iv_ca_dump(), iv_ca_extend(), iv_ca_narrow(), iv_ca_replace(), and try_add_cand_for().
◆ iv_ca_cand_used_p()
Returns true if CAND is used in IVS.
References ggc_alloc().
Referenced by try_add_cand_for(), and try_improve_iv_set().
◆ iv_ca_compare_deps()
|
static |
Compare if applying NEW_CP to GROUP for IVS introduces more invariants than OLD_CP. Return 1, 0 and -1 for more, equal and fewer invariants respectively.
References gcc_assert, ggc_alloc(), and iv_ca_set_cp().
Referenced by iv_ca_extend().
◆ iv_ca_cost()
Get cost for assignment IVS.
References ggc_alloc(), and infinite_cost.
Referenced by find_optimal_iv_set(), find_optimal_iv_set_1(), iv_ca_dump(), iv_ca_extend(), iv_ca_narrow(), iv_ca_prune(), iv_ca_replace(), try_add_cand_for(), and try_improve_iv_set().
◆ iv_ca_delta_add()
|
static |
Creates change of expressing GROUP by NEW_CP instead of OLD_CP and chains it before NEXT.
References ggc_alloc(), iv_ca_delta::group, iv_ca_delta::new_cp, iv_ca_delta::next, and iv_ca_delta::old_cp.
Referenced by iv_ca_extend(), iv_ca_narrow(), iv_ca_replace(), and try_add_cand_for().
◆ iv_ca_delta_commit()
|
static |
Commit changes in DELTA to IVS. If FORWARD is false, the changes are reverted instead.
References gcc_assert, ggc_alloc(), iv_ca_cand_for_group(), iv_ca_delta_reverse(), and iv_ca_set_cp().
Referenced by iv_ca_extend(), iv_ca_narrow(), iv_ca_prune(), iv_ca_replace(), try_add_cand_for(), and try_improve_iv_set().
◆ iv_ca_delta_free()
|
static |
Free the list of changes DELTA.
References free(), ggc_alloc(), iv_ca_delta::next, and NULL.
Referenced by iv_ca_narrow(), iv_ca_prune(), iv_ca_replace(), try_add_cand_for(), and try_improve_iv_set().
◆ iv_ca_delta_join()
|
static |
Joins two lists of changes L1 and L2. Destructive -- old lists are rewritten.
References ggc_alloc(), last, and filedep::next.
Referenced by iv_ca_prune(), iv_ca_replace(), and try_improve_iv_set().
◆ iv_ca_delta_reverse()
|
static |
Reverse the list of changes DELTA, forming the inverse to it.
References ggc_alloc(), iv_ca_delta::next, and NULL.
Referenced by iv_ca_delta_commit().
◆ iv_ca_dump()
Dumps IVS to FILE.
References bitmap_print(), comp_cost::complexity, comp_cost::cost, iv_ca::cost, ggc_alloc(), i, iv_group::id, iv_ca_cand_for_group(), iv_ca_cost(), ivopts_estimate_reg_pressure(), pref, and PRId64.
Referenced by find_optimal_iv_set_1().
◆ iv_ca_extend()
|
static |
Try changing candidate in IVS to CAND for each use. Return cost of the new set, and store differences in DELTA. Number of induction variables in the new set is stored to N_IVS. MIN_NCAND is a flag. When it is true the function will try to find a solution with mimimal iv candidates.
References cost_pair::cand, compare_cost_pair(), cost_pair::cost, get_group_iv_cost(), ggc_alloc(), i, iv_ca_cand_for_group(), iv_ca_compare_deps(), iv_ca_cost(), iv_ca_delta_add(), iv_ca_delta_commit(), iv_ca_n_cands(), and NULL.
Referenced by try_add_cand_for(), and try_improve_iv_set().
◆ iv_ca_free()
Free memory occupied by the set IVS.
References BITMAP_FREE, free(), ggc_alloc(), and NULL.
Referenced by find_optimal_iv_set(), find_optimal_iv_set_1(), get_initial_solution(), and tree_ssa_iv_optimize_loop().
◆ iv_ca_n_cands()
Returns number of induction variable candidates in the set IVS.
References ggc_alloc().
Referenced by iv_ca_extend().
◆ iv_ca_narrow()
|
static |
Try narrowing set IVS by removing CAND. Return the cost of the new set and store the differences in DELTA. START is the candidate with which we start narrowing.
References cost_pair::cand, iv_cand::cost, EXECUTE_IF_AND_IN_BITMAP, EXECUTE_IF_SET_IN_BITMAP, get_group_iv_cost(), ggc_alloc(), i, infinite_cost, iv_ca_cand_for_group(), iv_ca_cost(), iv_ca_delta_add(), iv_ca_delta_commit(), iv_ca_delta_free(), iv_ca_set_cp(), NULL, and iv_group::related_cands.
Referenced by iv_ca_prune().
◆ iv_ca_new()
|
static |
Allocates new iv candidates assignment.
References BITMAP_ALLOC, ggc_alloc(), no_cost, and NULL.
Referenced by get_initial_solution().
◆ iv_ca_prune()
|
static |
Try optimizing the set of candidates IVS by removing candidates different from to EXCEPT_CAND from it. Return cost of the new set, and store differences in DELTA.
References EXECUTE_IF_SET_IN_BITMAP, ggc_alloc(), i, iv_ca_cost(), iv_ca_delta_commit(), iv_ca_delta_free(), iv_ca_delta_join(), iv_ca_narrow(), iv_ca_prune(), and NULL.
Referenced by iv_ca_prune(), iv_ca_replace(), and try_improve_iv_set().
◆ iv_ca_recount_cost()
Computes the cost field of IVS structure.
References cost_pair::cost, ggc_alloc(), and ivopts_estimate_reg_pressure().
Referenced by iv_ca_set_cp(), and iv_ca_set_no_cp().
◆ iv_ca_replace()
|
static |
Try breaking local optimal fixed-point for IVS by replacing candidates which are used by more than one iv uses. For each of those candidates, this function tries to represent iv uses under that candidate using other ones with lower local cost, then tries to prune the new set. If the new set has lower cost, It returns the new cost after recording candidate replacement in list DELTA.
References ALWAYS_PRUNE_CAND_SET_BOUND, cost_pair::cand, cheaper_cost_with_cand(), EXECUTE_IF_SET_IN_BITMAP, ggc_alloc(), i, iv_ca_cand_for_group(), iv_ca_cost(), iv_ca_delta_add(), iv_ca_delta_commit(), iv_ca_delta_free(), iv_ca_delta_join(), iv_ca_prune(), NULL, and iv_group::related_cands.
Referenced by try_improve_iv_set().
◆ iv_ca_set_add_invs()
Add use of invariants in set INVS by increasing counter in N_INV_USES and IVS.
References EXECUTE_IF_SET_IN_BITMAP, gcc_assert, ggc_alloc(), and NULL.
Referenced by iv_ca_set_cp().
◆ iv_ca_set_cp()
|
static |
Set cost pair for GROUP in set IVS to CP.
References bitmap_set_bit, ggc_alloc(), iv_group::id, iv_ca_recount_cost(), iv_ca_set_add_invs(), iv_ca_set_no_cp(), and targetm.
Referenced by iv_ca_add_group(), iv_ca_compare_deps(), iv_ca_delta_commit(), iv_ca_narrow(), and try_add_cand_for().
◆ iv_ca_set_no_cp()
|
static |
Set USE not to be expressed by any candidate in IVS.
References bitmap_clear_bit(), ggc_alloc(), iv_group::id, iv_ca_recount_cost(), iv_ca_set_remove_invs(), NULL, and targetm.
Referenced by iv_ca_set_cp(), and try_add_cand_for().
◆ iv_ca_set_remove_invs()
Remove use of invariants in set INVS by decreasing counter in N_INV_USES and IVS.
References EXECUTE_IF_SET_IN_BITMAP, gcc_assert, ggc_alloc(), and NULL.
Referenced by iv_ca_set_no_cp().
◆ iv_elimination_compare()
|
static |
Returns the comparison operator used when eliminating the iv USE.
References EDGE_SUCC, flow_bb_inside_loop_p(), ggc_alloc(), and gimple_bb().
Referenced by may_eliminate_iv().
◆ iv_elimination_compare_lt()
|
static |
Tries to replace loop exit by one formulated in terms of a LT_EXPR
comparison with CAND. NITER describes the number of iterations of
the loops. If successful, the comparison in COMP_P is altered accordingly.
We aim to handle the following situation:
sometype *base, *p;
int a, b, i;
i = a;
p = p_0 = base + a;
do
{
bla (*p);
p++;
i++;
}
while (i < b);
Here, the number of iterations of the loop is (a + 1 > b) ? 0 : b - a - 1.
We aim to optimize this to
p = p_0 = base + a;
do
{
bla (*p);
p++;
}
while (p < p_0 - a + b);
This preserves the correctness, since the pointer arithmetics does not
overflow. More precisely:
1) if a + 1 <= b, then p_0 - a + b is the final value of p, hence there is no
overflow in computing it or the values of p.
2) if a + 1 > b, then we need to verify that the expression p_0 - a does not
overflow. To prove this, we use the fact that p_0 = base + a.
References a, aff_combination_add(), aff_combination_scale(), b, comp, cst_and_fits_in_hwi(), difference_cannot_overflow_p(), fold_build2, fold_convert, gcc_unreachable, ggc_alloc(), int_cst_value(), integer_onep(), invert_tree_comparison(), IP_ORIGINAL, tree_niter_desc::may_be_zero, tree_niter_desc::niter, nowrap_type_p(), offset, TREE_CODE, TREE_OPERAND, tree_to_aff_combination(), and TREE_TYPE.
Referenced by may_eliminate_iv().
◆ iv_period()
Returns period of induction variable iv.
References build_low_bits_mask(), gcc_assert, ggc_alloc(), num_ending_zeros(), iv::step, TREE_CODE, tree_to_uhwi(), TREE_TYPE, type(), TYPE_PRECISION, and unsigned_type_for().
Referenced by may_eliminate_iv().
◆ ivopts_estimate_reg_pressure()
|
static |
Estimate register pressure for loop having N_INVS invariants and N_CANDS induction variables. Note N_INVS includes both invariant variables and invariant expressions.
References iv_cand::cost, ggc_alloc(), target_avail_regs, target_clobbered_regs, target_reg_cost, target_res_regs, and target_spill_cost.
Referenced by determine_set_costs(), iv_ca_dump(), and iv_ca_recount_cost().
◆ loop_body_includes_call()
|
static |
Returns true if the loop body BODY includes any function calls.
References gimple_call_fndecl(), gimple_call_internal_p(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_stmt(), i, is_gimple_call(), and is_inexpensive_builtin().
Referenced by tree_ssa_iv_optimize_loop().
◆ mark_bivs()
|
static |
Marks basic ivs.
References iv::biv_p, get_iv(), ggc_alloc(), gimple_bb(), gsi_end_p(), gsi_next(), gsi_start_phis(), loop::header, loop_latch_edge(), iv::no_overflow, gphi_iterator::phi(), PHI_ARG_DEF_FROM_EDGE, PHI_RESULT, and SSA_NAME_DEF_STMT.
Referenced by find_induction_variables().
◆ may_be_nonaddressable_p()
Return true if EXPR may be non-addressable.
References CASE_CONVERT, DECL_HARD_REGISTER, DECL_NONADDRESSABLE_P, ggc_alloc(), is_gimple_addressable(), is_gimple_reg(), may_be_nonaddressable_p(), REF_REVERSE_STORAGE_ORDER, TREE_CODE, TREE_OPERAND, TREE_TYPE, and TYPE_REVERSE_STORAGE_ORDER.
Referenced by loop_distribution::create_rdg_vertices(), dr_analyze_innermost(), find_interesting_uses_address(), gather_memory_references_ref(), ifcvt_can_use_mask_load_store(), initialize_data_dependence_relation(), instrument_expr(), may_be_nonaddressable_p(), and vect_check_gather_scatter().
◆ may_be_unaligned_p()
Return true if memory reference REF with step STEP may be unaligned.
References GET_MODE_ALIGNMENT, get_object_alignment_1(), ggc_alloc(), HOST_BITS_PER_INT, TREE_CODE, tree_ctz(), TREE_TYPE, TYPE_ALIGN, and TYPE_MODE.
Referenced by find_interesting_uses_address().
◆ may_eliminate_iv()
|
static |
Check whether it is possible to express the condition in USE by comparison of candidate CAND. If so, store the value compared with to BOUND, and the comparison operator to COMP.
References aff_combination_to_tree(), tree_niter_desc::bound, build_int_cst(), cand_value_at(), CDI_DOMINATORS, comp, dominated_by_p(), EDGE_SUCC, expression_expensive_p(), flow_bb_inside_loop_p(), fold_convert, ggc_alloc(), gimple_bb(), wi::gtu_p(), integer_zerop(), iv_elimination_compare(), iv_elimination_compare_lt(), iv_period(), last_nondebug_stmt(), loop::latch, tree_niter_desc::max, max_loop_iterations(), tree_niter_desc::may_be_zero, tree_niter_desc::niter, niter_for_exit(), NULL, stmt_after_increment(), wi::to_widest(), TREE_CODE, tree_int_cst_lt(), and TREE_TYPE.
Referenced by determine_group_iv_cost_cond().
◆ name_info()
|
inlinestatic |
Returns the info for ssa name NAME.
References version_info::name, SSA_NAME_VERSION, and ver_info().
Referenced by create_new_iv(), find_inv_vars_cb(), get_iv(), record_invariant(), rewrite_use_nonlinear_expr(), and set_iv().
◆ niter_for_exit()
|
static |
Returns the structure describing number of iterations determined from EXIT of DATA->current_loop, or NULL if something goes wrong.
References contains_abnormal_ssa_name_p(), ggc_alloc(), tree_niter_desc::niter, NULL, and number_of_iterations_exit().
Referenced by generic_predict_doloop_p(), may_eliminate_iv(), and niter_for_single_dom_exit().
◆ niter_for_single_dom_exit()
|
static |
Returns the structure describing number of iterations determined from single dominating exit of DATA->current_loop, or NULL if something goes wrong.
References niter_for_exit(), NULL, and single_dom_exit().
Referenced by add_iv_candidate_for_doloop(), and find_induction_variables().
◆ operator+()
◆ operator-()
◆ operator<()
◆ operator<=()
◆ operator==()
◆ outermost_invariant_loop_for_expr()
Returns the outermost loop EXPR is obviously invariant in relative to the loop LOOP, i.e. if all its operands are defined outside of the returned loop. Returns NULL if EXPR is not even obviously invariant in LOOP.
References current_loops, EXPR_P, flow_bb_inside_loop_p(), ggc_alloc(), gimple_bb(), i, is_gimple_min_invariant(), loop_depth(), MAX, NULL, outermost_invariant_loop_for_expr(), SSA_NAME_DEF_STMT, superloop_at_depth(), TREE_CODE, TREE_OPERAND, and TREE_OPERAND_LENGTH.
Referenced by outermost_invariant_loop_for_expr(), vect_enhance_data_refs_alignment(), and vect_loop_versioning().
◆ parm_decl_cost()
|
static |
References tree_niter_desc::bound, COSTS_N_INSNS, ggc_alloc(), SSA_NAME_IS_DEFAULT_DEF, SSA_NAME_VAR, STRIP_NOPS, and TREE_CODE.
Referenced by determine_group_iv_cost_cond().
◆ prepare_decl_rtl()
Prepares decl_rtl for variables referred in *EXPR_P. Callback for walk_tree. DATA contains the actual fake register number.
References DECL_MODE, DECL_P, DECL_RTL_SET_P, decl_rtl_to_reset, gen_raw_REG(), ggc_alloc(), handled_component_p(), HAS_RTL_P, NULL_RTX, NULL_TREE, produce_memory_decl_rtl(), SET_DECL_RTL, SSA_NAME_VAR, TREE_CODE, and TREE_OPERAND.
Referenced by computation_cost().
◆ produce_memory_decl_rtl()
Produce DECL_RTL for object obj so it looks like it is stored in memory.
References DECL_ASSEMBLER_NAME, DECL_EXTERNAL, DECL_MODE, gcc_assert, gen_raw_REG(), gen_rtx_MEM(), ggc_alloc(), IDENTIFIER_POINTER, set_mem_addr_space(), SET_SYMBOL_REF_DECL, targetm, TREE_STATIC, TREE_TYPE, and TYPE_ADDR_SPACE.
Referenced by force_expr_to_var_cost(), and prepare_decl_rtl().
◆ record_biv_for_address_use()
Record BIV, its predecessor and successor that they are used in address type uses.
References iv::base, iv::biv_p, EXECUTE_IF_SET_IN_BITMAP, fold_build2, ggc_alloc(), iv::have_address_use, i, integer_zerop(), INTEGRAL_TYPE_P, version_info::iv, iv::no_overflow, operand_equal_p(), iv::step, TREE_TYPE, type(), and ver_info().
Referenced by idx_find_step().
◆ record_common_cand()
|
static |
Record common candidate {BASE, STEP} derived from USE in hashtable.
References iv_common_cand::base, gcc_assert, ggc_alloc(), iterative_hash_expr(), NULL, and iv_common_cand::step.
Referenced by add_iv_candidate_for_use().
◆ record_group()
Record a group of TYPE.
References BITMAP_ALLOC, iv_group::doloop_p, ggc_alloc(), iv_group::id, NULL, iv_group::related_cands, type(), iv_group::type, and iv_group::vuses.
Referenced by record_group_use(), and split_address_groups().
◆ record_group_use()
|
static |
Record a use of TYPE at *USE_P in STMT whose value is IV in a group. New group will be created if there is no existing group for the use. MEM_TYPE is the type of memory being addressed, or NULL if this isn't an address reference.
References iv_use::addr_base, iv_use::addr_offset, address_p(), iv::base, iv::base_object, gcc_assert, ggc_alloc(), i, int_cst_value(), iv_use::mem_type, NULL, operand_equal_p(), POINTER_TYPE_P, record_group(), record_use(), split_constant_offset(), iv::step, iv_use::stmt, TREE_TYPE, and iv_group::vuses.
Referenced by find_address_like_use(), find_interesting_uses_address(), find_interesting_uses_cond(), and find_interesting_uses_op().
◆ record_important_candidates()
|
static |
Record important candidates and add them to related_cands bitmaps.
References bitmap_ior_into(), bitmap_set_bit, CONSIDER_ALL_CANDIDATES_BOUND, i, and iv_group::related_cands.
Referenced by find_iv_candidates().
◆ record_invariant()
Checks whether OP is a loop-level invariant and if so, records it. NONLINEAR_USE is true if the invariant is used in a way we do not handle specially.
References bitmap_set_bit, flow_bb_inside_loop_p(), ggc_alloc(), gimple_bb(), version_info::has_nonlin_use, version_info::inv_id, version_info::name, name_info(), SSA_NAME_DEF_STMT, SSA_NAME_VERSION, TREE_CODE, and virtual_operand_p().
Referenced by find_interesting_uses_op(), find_inv_vars_cb(), and find_invariants_stmt().
◆ record_use()
|
static |
Records a use of TYPE at *USE_P in STMT whose value is IV in GROUP. For address type use, ADDR_BASE is the stripped IV base, ADDR_OFFSET is the const offset stripped from IV base and MEM_TYPE is the type of the memory being addressed. For uses of other types, ADDR_BASE and ADDR_OFFSET are zero by default and MEM_TYPE is NULL_TREE.
References iv_use::addr_base, iv_use::addr_offset, ggc_alloc(), iv_group::id, iv_use::iv, iv_use::mem_type, iv_use::stmt, type(), and iv_group::vuses.
Referenced by record_group_use().
◆ relate_compare_use_with_all_cands()
|
static |
Relate compare use with all candidates.
References bitmap_set_range(), count, i, iv_group::related_cands, iv_group::type, and USE_COMPARE.
Referenced by find_iv_candidates().
◆ remove_unused_ivs()
|
static |
Removes the ivs that are not used after rewriting.
References iv::base, bitmap_set_bit, build_debug_expr_decl(), comp, count, DECL_MODE, EXECUTE_IF_SET_IN_BITMAP, FOR_EACH_IMM_USE_ON_STMT, FOR_EACH_IMM_USE_STMT, get_debug_computation_at(), ggc_alloc(), gimple_bb(), gimple_build_debug_bind(), gimple_debug_bind_get_value(), gimple_debug_bind_p(), gsi_after_labels(), gsi_for_stmt(), gsi_insert_before(), GSI_SAME_STMT, i, integer_zerop(), version_info::inv_id, version_info::iv, MAY_HAVE_DEBUG_BIND_STMTS, iv::nonlin_use, NULL, NULL_TREE, operand_equal_p(), version_info::preserve_biv, SET_DECL_MODE, SET_USE, iv::ssa_name, SSA_NAME_DEF_STMT, SSA_NAME_VAR, SSA_NAME_VERSION, iv::step, TREE_CODE, TREE_TYPE, TYPE_MODE, unshare_expr(), update_stmt(), and ver_info().
Referenced by tree_ssa_iv_optimize_loop().
◆ rewrite_groups()
|
static |
Rewrite the groups using the selected induction variables.
References address_p(), gcc_assert, ggc_alloc(), i, rewrite_use_address(), rewrite_use_compare(), rewrite_use_nonlinear_expr(), iv_group::selected, iv_group::type, update_stmt(), USE_COMPARE, USE_NONLINEAR_EXPR, and iv_group::vuses.
Referenced by tree_ssa_iv_optimize_loop().
◆ rewrite_use_address()
|
static |
Rewrites USE (address that is an iv) using candidate CAND.
References adjust_iv_update_pos(), build2(), build_aligned_type(), build_pointer_type(), build_zero_cst(), copy_ref_info(), create_mem_ref(), fold_build1, fold_convert, force_gimple_operand_gsi(), gcc_assert, get_alias_ptr_type_for_ptr_address(), get_computation_aff(), get_object_alignment(), get_use_type(), ggc_alloc(), gsi_for_stmt(), GSI_SAME_STMT, integer_zerop(), NULL_TREE, reference_alias_ptr_type(), TMR_INDEX2, TREE_CODE, TREE_OPERAND, TREE_TYPE, TYPE_ALIGN, unshare_aff_combination(), USE_PTR_ADDRESS, and var_at_stmt().
Referenced by rewrite_groups().
◆ rewrite_use_compare()
|
static |
Rewrites USE (the condition such that one of the arguments is an iv) using candidate CAND.
References comp, dump_file, dump_flags, fold_convert, force_gimple_operand(), force_gimple_operand_gsi(), gcc_assert, get_computation_at(), get_group_iv_cost(), ggc_alloc(), gimple_cond_set_code(), gimple_cond_set_lhs(), gimple_cond_set_rhs(), gsi_for_stmt(), gsi_insert_seq_on_edge_immediate(), GSI_SAME_STMT, loop_preheader_edge(), NULL, NULL_TREE, print_gimple_stmt(), SSA_NAME_VAR, TDF_DETAILS, TDF_SLIM, TREE_TYPE, unshare_expr(), and var_at_stmt().
Referenced by rewrite_groups().
◆ rewrite_use_nonlinear_expr()
|
static |
Rewrites USE (definition of iv used in a nonlinear expression) using candidate CAND.
References aff_combination_to_tree(), comp, duplicate_ssa_name_ptr_info(), expr_invariant_in_loop_p(), fold_build2, fold_build_pointer_plus, fold_convert, force_gimple_operand(), gcc_assert, gcc_unreachable, get_computation_aff_1(), get_gimple_rhs_num_ops(), get_iv(), get_use_type(), ggc_alloc(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), gimple_assign_set_rhs_from_tree(), gimple_bb(), gimple_build_assign(), gimple_num_ops(), gimple_seq_add_seq(), gsi_after_labels(), gsi_for_stmt(), gsi_insert_before(), gsi_insert_seq_before(), GSI_SAME_STMT, gsi_stmt(), integer_zerop(), IP_ORIGINAL, is_gimple_assign(), mark_ptr_info_alignment_unknown(), name_info(), NULL, NULL_TREE, offset, PHI_RESULT, POINTER_TYPE_P, remove_phi_node(), sizetype, SSA_NAME_PTR_INFO, iv::step, TREE_CODE, TREE_TYPE, unshare_aff_combination(), and wide_int_to_tree().
Referenced by rewrite_groups().
◆ set_autoinc_for_original_candidates()
|
static |
Examine IP_ORIGINAL candidates to see if they are incremented next to a use that allows autoincrement, and set their AINC_USE if possible.
References autoinc_possible_for_pair(), ggc_alloc(), gimple_bb(), gimple_uid(), i, IP_ORIGINAL, NULL, and iv_group::vuses.
Referenced by find_iv_candidates().
◆ set_group_iv_cost()
|
static |
Sets cost of (GROUP, CAND) pair to COST and record that it depends on invariants INV_VARS and that the value used in expressing it is VALUE, and in case of iv elimination the comparison operator is COMP.
References BITMAP_FREE, cost_pair::cand, comp, cost_pair::comp, cost_pair::cost, iv_group::cost_map, gcc_unreachable, i, comp_cost::infinite_cost_p(), cost_pair::inv_exprs, cost_pair::inv_vars, iv_group::n_map_members, and cost_pair::value.
Referenced by determine_group_iv_cost_address(), determine_group_iv_cost_cond(), and determine_group_iv_cost_generic().
◆ set_iv()
|
static |
Sets STEP and BASE for induction variable IV. NO_OVERFLOW implies the IV doesn't overflow.
References alloc_iv(), bitmap_set_bit, gcc_assert, version_info::iv, name_info(), iv::ssa_name, and SSA_NAME_VERSION.
Referenced by find_bivs(), find_givs_in_stmt(), find_inv_vars_cb(), and get_iv().
◆ single_dom_exit()
The single loop exit if it dominates the latch, NULL otherwise.
References just_once_each_iteration_p(), NULL, and single_exit().
Referenced by can_unroll_loop_p(), canonicalize_loop_ivs(), create_parallel_loop(), gen_parallel_loop(), generic_predict_doloop_p(), niter_for_single_dom_exit(), parallelize_loops(), transform_to_exit_first_loop(), transform_to_exit_first_loop_alt(), tree_ssa_iv_optimize_loop(), tree_transform_and_unroll_loop(), try_create_reduction_list(), try_get_loop_niter(), and try_transform_to_exit_first_loop_alt().
◆ sort_iv_inv_expr_ent()
Sort iv_inv_expr_ent pair A and B by id field.
References a, b, and ggc_alloc().
Referenced by determine_group_iv_costs().
◆ split_address_groups()
|
static |
For each group of address type uses, this function further groups these uses according to the maximum offset supported by target's [base + offset] addressing mode.
References iv_use::addr_offset, addr_offset_valid_p(), address_p(), gcc_assert, ggc_alloc(), iv_use::group_id, i, iv_use::id, iv_group::id, NULL, offset, record_group(), split_small_address_groups_p(), iv_group::type, and iv_group::vuses.
Referenced by find_interesting_uses().
◆ split_small_address_groups_p()
|
static |
Check if small groups should be split. Return true if no group
contains more than two uses with distinct addr_offsets. Return
false otherwise. We want to split such groups because:
1) Small groups don't have much benefit and may interfer with
general candidate selection.
2) Size for problem with only small groups is usually small and
general algorithm can handle it well.
TODO -- Above claim may not hold when we want to merge memory
accesses with conseuctive addresses.
References iv_use::addr_offset, address_p(), gcc_assert, ggc_alloc(), group_compare_offset(), i, iv_group::type, and iv_group::vuses.
Referenced by split_address_groups().
◆ stmt_after_inc_pos()
Returns true if STMT if after the place where the original induction variable CAND is incremented. If TRUE_IF_EQUAL is set, we return true if the positions are identical.
References CDI_DOMINATORS, dominated_by_p(), ggc_alloc(), gimple_bb(), and gimple_uid().
Referenced by stmt_after_increment().
◆ stmt_after_increment()
Returns true if STMT if after the place where the induction variable CAND is incremented in LOOP.
References gcc_unreachable, IP_AFTER_USE, IP_BEFORE_USE, IP_END, IP_NORMAL, IP_ORIGINAL, stmt_after_inc_pos(), and stmt_after_ip_normal_pos().
Referenced by cand_value_at(), get_address_cost(), get_computation_aff_1(), get_debug_computation_at(), may_eliminate_iv(), and var_at_stmt().
◆ stmt_after_ip_normal_pos()
Returns true if STMT is after the place where the IP_NORMAL ivs will be emitted in LOOP.
References gcc_assert, ggc_alloc(), gimple_bb(), ip_normal_pos(), last_nondebug_stmt(), and loop::latch.
Referenced by stmt_after_increment().
◆ strip_offset()
|
static |
Strips constant offsets from EXPR and stores them to OFFSET.
References ggc_alloc(), offset, and strip_offset_1().
Referenced by add_iv_candidate_for_use().
◆ strip_offset_1()
|
static |
Strips constant offsets from EXPR and stores them to OFFSET. If INSIDE_ADDR is true, assume we are inside an address. If TOP_COMPREF is true, assume we are at the top-level of the processed address.
References abs_hwi(), array_ref_element_size(), build_fold_addr_expr, build_int_cst(), component_ref_field_offset(), copy_node(), cst_and_fits_in_hwi(), DECL_FIELD_BIT_OFFSET, expr, fold_build1, fold_build2, fold_convert, ggc_alloc(), int_cst_value(), integer_zerop(), NULL_TREE, offset, ptrdiff_tree_p(), STRIP_NOPS, strip_offset_1(), TREE_CODE, TREE_OPERAND, TREE_TYPE, type(), TYPE_OVERFLOW_UNDEFINED, and unsigned_type_for().
Referenced by strip_offset(), and strip_offset_1().
◆ tree_ssa_iv_optimize()
Main entry point. Optimizes induction variables in loops.
References cfun, dbg_cnt(), dump_file, dump_flags, flow_loop_dump(), free_numbers_of_iterations_estimates(), ggc_alloc(), LI_FROM_INNERMOST, mark_ssa_maybe_undefs(), NULL, release_defs_bitset(), scev_reset_htab(), TDF_DETAILS, tree_ssa_iv_optimize_finalize(), tree_ssa_iv_optimize_init(), and tree_ssa_iv_optimize_loop().
◆ tree_ssa_iv_optimize_finalize()
|
static |
Finalizes data structures used by the iv optimization pass. LOOPS is the loop tree.
References BITMAP_FREE, decl_rtl_to_reset, free(), free_affine_expand_cache(), free_loop_data(), ggc_alloc(), and NULL.
Referenced by tree_ssa_iv_optimize().
◆ tree_ssa_iv_optimize_init()
|
static |
Initializes data structures used by the iv optimization pass, stored in DATA.
References BITMAP_ALLOC, decl_rtl_to_reset, gcc_obstack_init, ggc_alloc(), NULL, and num_ssa_names.
Referenced by tree_ssa_iv_optimize().
◆ tree_ssa_iv_optimize_loop()
|
static |
Optimizes the LOOP. Returns true if anything changed.
References analyze_and_mark_doloop_use(), changed, create_new_ivs(), determine_group_iv_costs(), determine_iv_costs(), determine_scaling_factor(), determine_set_costs(), dump_file, dump_flags, find_induction_variables(), find_interesting_uses(), find_iv_candidates(), find_loop_location(), find_optimal_iv_set(), free(), free_loop_data(), gcc_assert, dump_user_location_t::get_location_t(), get_loop_body(), ggc_alloc(), gsi_last_bb(), i, iv_ca_free(), LOCATION_FILE, LOCATION_LINE, loop_body_includes_call(), loop_only_exit_p(), MAX_CONSIDERED_GROUPS, NULL, loop::num, loop::num_nodes, optimize_loop_for_speed_p(), print_gimple_stmt(), remove_unused_ivs(), renumber_gimple_stmt_uids_in_blocks(), rewrite_groups(), single_dom_exit(), TDF_DETAILS, TDF_SLIM, and UNKNOWN_LOCATION.
Referenced by tree_ssa_iv_optimize().
◆ try_add_cand_for()
|
static |
Tries to extend the sets IVS in the best possible way in order to express the GROUP. If ORIGINALP is true, prefer candidates from the original set of IVs, otherwise favor important candidates not based on any memory object.
References iv_group::cost_map, EXECUTE_IF_SET_IN_BITMAP, get_group_iv_cost(), ggc_alloc(), i, IP_ORIGINAL, iv_ca_add_group(), iv_ca_cand_for_group(), iv_ca_cand_used_p(), iv_ca_cost(), iv_ca_delta_add(), iv_ca_delta_commit(), iv_ca_delta_free(), iv_ca_extend(), iv_ca_set_cp(), iv_ca_set_no_cp(), iv_group::n_map_members, NULL, NULL_TREE, and iv_group::related_cands.
Referenced by get_initial_solution().
◆ try_improve_iv_set()
|
static |
Tries to improve set of induction variables IVS. TRY_REPLACE_P points to a bool variable, this function tries to break local optimal fixed-point by replacing candidates in IVS if it's true.
References ALWAYS_PRUNE_CAND_SET_BOUND, ggc_alloc(), i, iv_ca_cand_used_p(), iv_ca_cost(), iv_ca_delta_commit(), iv_ca_delta_free(), iv_ca_delta_join(), iv_ca_extend(), iv_ca_prune(), iv_ca_replace(), and NULL.
Referenced by find_optimal_iv_set_1().
◆ var_at_stmt()
Returns variable containing the value of candidate CAND at statement AT.
References stmt_after_increment().
Referenced by get_computation_aff_1(), get_debug_computation_at(), rewrite_use_address(), and rewrite_use_compare().
◆ ver_info()
|
inlinestatic |
Returns the info for ssa version VER.
References ggc_alloc().
Referenced by add_iv_candidate_for_bivs(), determine_group_iv_costs(), determine_set_costs(), find_induction_variables(), free_loop_data(), name_info(), record_biv_for_address_use(), and remove_unused_ivs().
Variable Documentation
◆ addr_list
Return TRUE if OFFSET is within the range of [base + offset] addressing mode for memory reference represented by USE.
Referenced by addr_offset_valid_p(), and new_elt_loc_list().
◆ decl_rtl_to_reset
The list of trees for that the decl_rtl field must be reset is stored here.
Referenced by free_loop_data(), prepare_decl_rtl(), tree_ssa_iv_optimize_finalize(), and tree_ssa_iv_optimize_init().
