Go to the source code of this file.
Function Documentation
◆ analyze_scalar_evolution()
Analyzes and returns the scalar evolution of the ssa_name VAR in LOOP. LOOP is the loop in which the variable is used. Example of use: having a pointer VAR to a SSA_NAME node, STMT a pointer to the statement that uses this variable, in order to determine the evolution function of the variable, use the following calls: loop_p loop = loop_containing_stmt (stmt); tree chrec_with_symbols = analyze_scalar_evolution (loop, var); tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
References analyze_scalar_evolution_1(), block_before_loop(), chrec_not_analyzed_yet, dump_file, dump_flags, get_scalar_evolution(), global_cache, NULL, loop::num, print_generic_expr(), and TDF_SCEV.
Referenced by analyze_and_compute_bitwise_induction_effect(), loop_cand::analyze_carried_vars(), analyze_scalar_evolution_for_address_of(), analyze_scalar_evolution_in_loop(), compute_access_range(), compute_access_stride(), constant_after_peeling(), dr_analyze_indices(), scev_dfs::follow_ssa_edge_inner_loop_phi(), get_base_for_alignment_1(), get_scev_info(), idx_infer_loop_bounds(), idx_within_array_bound(), infer_loop_bounds_from_pointer_arith(), infer_loop_bounds_from_signedness(), instantiate_scev_name(), tree_loop_interchange::interchange_loops(), interpret_condition_phi(), interpret_rhs_expr(), predicate_scalar_phi(), scalar_evolution_in_region(), scev_probably_wraps_p(), simplify_peeled_chrec(), and vect_analyze_scalar_cycles_1().
◆ block_before_loop()
|
inline |
Returns the basic block preceding LOOP, or the CFG entry block when the loop is function's body.
References cfun, ENTRY_BLOCK_PTR_FOR_FN, and loop_preheader_edge().
Referenced by analyze_scalar_evolution(), and analyze_scalar_evolution_1().
◆ compute_overall_effect_of_inner_loop()
Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
In general, in the case of multivariate evolutions we want to get
the evolution in different loops. LOOP specifies the level for
which to get the evolution.
Example:
| for (j = 0; j < 100; j++)
| {
| for (k = 0; k < 100; k++)
| {
| i = k + j; - Here the value of i is a function of j, k.
| }
| ... = i - Here the value of i is a function of j.
| }
| ... = i - Here the value of i is a scalar.
Example:
| i_0 = ...
| loop_1 10 times
| i_1 = phi (i_0, i_2)
| i_2 = i_1 + 2
| endloop
This loop has the same effect as:
LOOP_1 has the same effect as:
| i_1 = i_0 + 20
The overall effect of the loop, "i_0 + 20" in the previous example,
is obtained by passing in the parameters: LOOP = 1,
EVOLUTION_FN = {i_0, +, 2}_1.
References chrec_apply(), chrec_contains_symbols_defined_in_loop(), chrec_dont_know, compute_overall_effect_of_inner_loop(), flow_loop_nested_p(), get_chrec_loop(), instantiate_parameters(), no_evolution_in_loop_p(), loop::num, number_of_latch_executions(), and TREE_CODE.
Referenced by analyze_scalar_evolution_1(), compute_overall_effect_of_inner_loop(), final_value_replacement_loop(), scev_dfs::follow_ssa_edge_inner_loop_phi(), and instantiate_scev_name().
◆ expression_expensive_p()
References cache, and expression_expensive_p().
◆ final_value_replacement_loop()
Do final value replacement for LOOP, return true if we did anything.
References analyze_and_compute_bitop_with_inv_effect(), analyze_and_compute_bitwise_induction_effect(), analyze_scalar_evolution_in_loop(), ANY_INTEGRAL_TYPE_P, arith_code_with_undefined_signed_overflow(), chrec_contains_symbols_defined_in_loop(), chrec_dont_know, compute_overall_effect_of_inner_loop(), CONSTANT_CLASS_P, contains_abnormal_ssa_name_p(), dump_file, dump_flags, expression_expensive_p(), force_gimple_operand(), gimple_assign_rhs_code(), gimple_build_assign(), gimple_phi_arg_location(), gimple_seq_add_stmt(), gimple_set_location(), gsi_after_labels(), gsi_end_p(), gsi_insert_seq_before(), gsi_next(), GSI_SAME_STMT, gsi_start(), gsi_start_phis(), gsi_stmt(), INTEGRAL_TYPE_P, is_gimple_assign(), loop_depth(), NULL_TREE, loop::num, number_of_latch_executions(), gphi_iterator::phi(), PHI_ARG_DEF_FROM_EDGE, PHI_RESULT, POINTER_TYPE_P, print_generic_expr(), print_gimple_stmt(), remove_phi_node(), replace_uses_by(), rewrite_to_defined_overflow(), single_exit(), single_pred_p(), split_loop_exit_edge(), SSA_NAME_DEF_STMT, SSA_NAME_OCCURS_IN_ABNORMAL_PHI, superloop_at_depth(), TDF_DETAILS, tree_does_not_contain_chrecs(), tree_fits_uhwi_p(), tree_to_uhwi(), TREE_TYPE, TYPE_OVERFLOW_UNDEFINED, TYPE_PRECISION, unshare_expr(), and virtual_operand_p().
Referenced by try_create_reduction_list().
◆ gather_stats_on_scev_database()
|
extern |
Classify the chrecs of the whole database.
References scev_info_str::chrec, dump_chrecs_stats(), dump_file, FOR_EACH_HASH_TABLE_ELEMENT, gather_chrec_stats(), reset_chrecs_counters(), and scalar_evolution_info.
◆ get_chrec_loop()
|
inline |
Returns the loop of the polynomial chrec CHREC.
References cfun, CHREC_VARIABLE, and get_loop().
Referenced by add_subscript_strides(), scev_dfs::add_to_evolution_1(), analyze_miv_subscript(), analyze_siv_subscript_cst_affine(), analyze_subscript_affine_affine(), chrec_component_in_loop_num(), chrec_contains_symbols(), chrec_convert_1(), chrec_convert_aggressive(), chrec_evaluate(), chrec_fold_multiply_poly_poly(), chrec_fold_plus_poly_poly(), chrec_is_positive(), compute_access_stride(), compute_overall_effect_of_inner_loop(), compute_overlap_steps_for_affine_1_2(), evolution_function_is_invariant_rec_p(), evolution_function_is_univariate_p(), get_scev_info(), hide_evolution_in_other_loops_than_loop(), instantiate_scev_poly(), and reset_evolution_in_loop().
◆ get_loop_exit_condition() [1/2]
This section selects the loops that will be good candidates for the scalar evolution analysis. For the moment, greedily select all the loop nests we could analyze.
For a loop with a single exit edge, return the COND_EXPR that guards the exit edge. If the expression is too difficult to analyze, then give up.
References get_loop_exit_condition(), and single_exit().
Referenced by find_loop_location(), get_loop_exit_condition(), slpeel_can_duplicate_loop_p(), vec_init_loop_exit_info(), vect_get_loop_niters(), vect_set_loop_condition(), and vect_set_loop_condition_normal().
◆ get_loop_exit_condition() [2/2]
|
extern |
If the statement just before the EXIT_EDGE contains a condition then return the condition, otherwise NULL.
References dump_file, dump_flags, gsi_last_bb(), NULL, print_gimple_stmt(), safe_dyn_cast(), and TDF_SCEV.
◆ instantiate_parameters()
Analyze all the parameters of the chrec that were left under a symbolic form. LOOP is the loop in which symbolic names have to be analyzed and instantiated.
References instantiate_scev(), and loop_preheader_edge().
Referenced by analyze_and_compute_bitwise_induction_effect(), compute_overall_effect_of_inner_loop(), get_scev_info(), idx_infer_loop_bounds(), idx_within_array_bound(), infer_loop_bounds_from_pointer_arith(), infer_loop_bounds_from_signedness(), interpret_rhs_expr(), simplify_peeled_chrec(), and simplify_using_outer_evolutions().
◆ instantiate_scev()
Analyze all the parameters of the chrec that were left under a symbolic form. INSTANTIATE_BELOW is the basic block that stops the recursive instantiation of parameters: a parameter is a variable that is defined in a basic block that dominates INSTANTIATE_BELOW or a function parameter.
References dump_file, dump_flags, global_cache, instantiate_scev_r(), NULL, loop::num, print_generic_expr(), and TDF_SCEV.
Referenced by loop_cand::analyze_carried_vars(), compute_access_stride(), dr_analyze_indices(), instantiate_parameters(), tree_loop_interchange::interchange_loops(), and scalar_evolution_in_region().
◆ iv_can_overflow_p()
Return true if the IV calculation in TYPE can overflow based on the knowledge of the upper bound on the number of iterations of LOOP, the BASE and STEP of IV. We do not use information whether TYPE can overflow so it is safe to use this test even for derived IVs not computed every iteration or hypotetical IVs to be inserted into code.
References wi::add(), cfun, wide_int_storage::from(), gcc_checking_assert, wi::ge_p(), get_max_loop_iterations(), get_range_query(), wi::gtu_p(), integer_zerop(), INTEGRAL_TYPE_P, wi::le_p(), wi::max_value(), wi::min_precision(), wi::min_value(), wi::mul(), wi::neg(), wi::neg_p(), wi::OVF_NONE, r, SIGNED, TREE_TYPE, TYPE_PRECISION, TYPE_SIGN, and UNSIGNED.
Referenced by alloc_iv(), and simple_iv_with_niters().
◆ nonwrapping_chrec_p()
Return true if CHREC's nonwrapping flag is set.
References CHREC_NOWRAP, and TREE_CODE.
Referenced by scev_probably_wraps_p().
◆ number_of_latch_executions()
Scalar evolution detector. Copyright (C) 2003-2024 Free Software Foundation, Inc. Contributed by Sebastian Pop <s.pop@laposte.net> 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/>.
Entry point for the analysis of the number of iterations pass.
This function tries to safely approximate the number of iterations
the loop will run. When this property is not decidable at compile
time, the result is chrec_dont_know. Otherwise the result is a
scalar or a symbolic parameter. When the number of iterations may
be equal to zero and the property cannot be determined at compile
time, the result is a COND_EXPR that represents in a symbolic form
the conditions under which the number of iterations is not zero.
Example of analysis: suppose that the loop has an exit condition:
"if (b > 49) goto end_loop;"
and that in a previous analysis we have determined that the
variable 'b' has an evolution function:
"EF = {23, +, 5}_2".
When we evaluate the function at the point 5, i.e. the value of the
variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
and EF (6) = 53. In this case the value of 'b' on exit is '53' and
the loop body has been executed 6 times.
References build_int_cst(), chrec_dont_know, COMPARISON_CLASS_P, dump_file, dump_flags, fold_build3, integer_nonzerop(), integer_zerop(), tree_niter_desc::may_be_zero, loop::nb_iterations, niter_desc::niter, NULL_TREE, number_of_iterations_exit(), print_generic_expr(), single_exit(), TDF_SCEV, and TREE_TYPE.
Referenced by chrec_is_positive(), compute_access_range(), compute_alias_check_pairs(), compute_overall_effect_of_inner_loop(), estimate_numbers_of_iterations(), loop_distribution::execute(), final_value_replacement_loop(), tree_loop_interchange::interchange_loops(), is_inv_store_elimination_chain(), pcom_worker::prepare_finalizers_chain(), prepare_perfect_loop_nest(), and pcom_worker::split_data_refs_to_components().
◆ record_nonwrapping_chrec()
|
extern |
If CHREC doesn't overflow, set the nonwrapping flag.
References CHREC_NOWRAP, dump_file, dump_flags, print_generic_expr(), and TDF_SCEV.
Referenced by idx_infer_loop_bounds(), infer_loop_bounds_from_pointer_arith(), and infer_loop_bounds_from_signedness().
◆ resolve_mixers()
Similar to instantiate_parameters, but does not introduce the evolutions in outer loops for LOOP invariants in CHREC, and does not care about causing overflows, as long as they do not affect value of an expression.
References global_cache, instantiate_scev_r(), loop_preheader_edge(), and NULL.
Referenced by analyze_scalar_evolution_in_loop().
◆ scev_const_prop()
|
extern |
◆ scev_finalize()
|
extern |
Finalize the scalar evolution analysis.
References cfun, free_numbers_of_iterations_estimates(), NULL, and scalar_evolution_info.
Referenced by analyze_function_body(), debug_seed_ranger(), execute_ranger_vrp(), finite_function_p(), perform_tree_ssa_dce(), report_predictor_hitrates(), and tree_ssa_loop_done().
◆ scev_initialize()
|
extern |
Initialize the analysis of scalar evolutions for LOOPS.
References cfun, hash_table< Descriptor, Lazy, Allocator >::create_ggc(), gcc_assert, LOOPS_NORMAL, loops_state_satisfies_p(), loop::nb_iterations, NULL_TREE, scalar_evolution_info, and scev_initialized_p().
Referenced by analyze_function_body(), debug_seed_ranger(), execute_ranger_vrp(), finite_function_p(), perform_tree_ssa_dce(), and report_predictor_hitrates().
◆ scev_initialized_p()
|
extern |
Return true if SCEV is initialized.
References NULL, and scalar_evolution_info.
Referenced by cleanup_tree_cfg_noloop(), debug_seed_ranger(), estimated_loop_iterations(), fini_copy_prop(), fix_loop_structure(), likely_max_loop_iterations(), max_loop_iterations(), perform_tree_ssa_dce(), fold_using_range::range_of_phi(), scev_initialize(), tree_loop_unroll_and_jam(), and tree_ssa_split_loops().
◆ scev_reset()
|
extern |
Cleans up the information cached by the scalar evolutions analysis in the hash table and in the loop->nb_iterations.
References cfun, loop::nb_iterations, NULL_TREE, and scev_reset_htab().
Referenced by canonicalize_induction_variables(), loop_distribution::execute(), execute_ranger_vrp(), fini_copy_prop(), gen_parallel_loop(), gimple_duplicate_loop_body_to_header_edge(), perform_tree_ssa_dce(), repair_loop_structures(), tree_loop_unroll_and_jam(), tree_predictive_commoning(), tree_ssa_prefetch_arrays(), tree_unroll_loops_completely(), and vect_do_peeling().
◆ scev_reset_htab()
|
extern |
Cleans up the information cached by the scalar evolutions analysis in the hash table.
References scalar_evolution_info.
Referenced by fix_loop_structure(), flush_ssaname_freelist(), tree_loop_interchange::interchange_loops(), scev_reset(), tree_ssa_iv_optimize(), vect_analyze_loop(), and vect_free_loop_info_assumptions().
◆ simple_iv()
|
extern |
Like simple_iv_with_niters, but return TRUE when OP behaves as a simple affine iv unconditionally.
References NULL, and simple_iv_with_niters().
Referenced by analyze_function_body(), dr_analyze_innermost(), eliminate_dom_walker::eliminate_stmt(), find_bivs(), find_givs_in_stmt_scev(), gather_scalar_reductions(), get_cst_init_from_scev(), idx_analyze_ref(), is_comparison_with_loop_invariant_p(), rewrite_phi_with_iv(), split_at_bb_p(), loop_distribution::transform_reduction_loop(), try_create_reduction_list(), unroll_jam_possible_p(), and vectorizable_simd_clone_call().
◆ simple_iv_with_niters()
|
extern |
Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
respect to WRTO_LOOP and returns its base and step in IV if possible
(see analyze_scalar_evolution_in_loop for more details on USE_LOOP
and WRTO_LOOP). If ALLOW_NONCONSTANT_STEP is true, we want step to be
invariant in LOOP. Otherwise we require it to be an integer constant.
IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
because it is computed in signed arithmetics). Consequently, adding an
induction variable
for (i = IV->base; ; i += IV->step)
is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
false for the type of the induction variable, or you can prove that i does
not wrap by some other argument. Otherwise, this might introduce undefined
behavior, and
i = iv->base;
for (; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
must be used instead.
When IV_NITERS is not NULL, this function also checks case in which OP
is a conversion of an inner simple iv of below form:
(outer_type){inner_base, inner_step}_loop.
If type of inner iv has smaller precision than outer_type, it can't be
folded into {(outer_type)inner_base, (outer_type)inner_step}_loop because
the inner iv could overflow/wrap. In this case, we derive a condition
under which the inner iv won't overflow/wrap and do the simplification.
The derived condition normally is the maximum number the inner iv can
iterate, and will be stored in IV_NITERS. This is useful in loop niter
analysis, to derive break conditions when a loop must terminate, when is
infinite.
References analyze_scalar_evolution_in_loop(), iv::base, boolean_type_node, build_int_cst(), chrec_contains_symbols_defined_in_loop(), chrec_contains_undetermined(), CHREC_LEFT, CHREC_RIGHT, CHREC_VARIABLE, CONVERT_EXPR_P, derive_simple_iv_with_niters(), fold_build2, fold_convert, integer_zerop(), INTEGRAL_TYPE_P, iv_can_overflow_p(), wi::max_value(), wi::min_value(), iv::no_overflow, nowrap_type_p(), NULL, NULL_TREE, loop::num, wi::OVF_NONE, POINTER_TYPE_P, simplify_using_initial_conditions(), sizetype, iv::step, wi::sub(), wi::to_wide(), TREE_CODE, tree_contains_chrecs(), tree_does_not_contain_chrecs(), tree_int_cst_equal(), tree_int_cst_sign_bit(), tree_nop_conversion_p(), TREE_OPERAND, TREE_TYPE, type(), TYPE_SIGN, useless_type_conversion_p(), and wide_int_to_tree().
Referenced by number_of_iterations_exit_assumptions(), and simple_iv().
