#include "config.h"#include "system.h"#include "coretypes.h"#include "backend.h"#include "rtl.h"#include "tree.h"#include "gimple.h"#include "tree-pass.h"#include "ssa.h"#include "gimple-pretty-print.h"#include "diagnostic-core.h"#include "stor-layout.h"#include "fold-const.h"#include "calls.h"#include "intl.h"#include "gimplify.h"#include "gimple-iterator.h"#include "tree-cfg.h"#include "tree-ssa-loop-ivopts.h"#include "tree-ssa-loop-niter.h"#include "tree-ssa-loop.h"#include "cfgloop.h"#include "tree-chrec.h"#include "tree-scalar-evolution.h"#include "tree-dfa.h"#include "internal-fn.h"#include "gimple-range.h"#include "sreal.h"
Data Structures | |
| struct | bounds |
| struct | ilb_data |
Macros | |
| #define | MAX_DOMINATORS_TO_WALK 8 |
| #define | MAX_ITERATIONS_TO_TRACK ((unsigned) param_max_iterations_to_track) |
Macro Definition Documentation
◆ MAX_DOMINATORS_TO_WALK
| #define MAX_DOMINATORS_TO_WALK 8 |
Functions to determine/estimate number of iterations of a loop. Copyright (C) 2004-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/>.
The maximum number of dominator BBs we search for conditions of loop header copies we use for simplifying a conditional expression.
Referenced by bound_difference(), determine_value_range(), and simplify_using_initial_conditions().
◆ MAX_ITERATIONS_TO_TRACK
| #define MAX_ITERATIONS_TO_TRACK ((unsigned) param_max_iterations_to_track) |
Bound on the number of iterations we try to evaluate.
Referenced by loop_niter_by_eval().
Function Documentation
◆ assert_loop_rolls_lt()
|
static |
Add an assumption to NITER that a loop whose ending condition is IV0 < IV1 rolls. TYPE is the type of the control iv. BNDS bounds the value of IV1->base - IV0->base.
References tree_niter_desc::assumptions, affine_iv::base, bounds::below, boolean_true_node, boolean_type_node, build_int_cst(), fold_build2, fold_convert, integer_nonzerop(), tree_niter_desc::may_be_zero, wi::minus_one(), POINTER_TYPE_P, wi::sext(), sizetype, affine_iv::step, wi::to_mpz(), wi::to_widest(), type(), TYPE_MAX_VALUE, TYPE_MIN_VALUE, TYPE_PRECISION, UNSIGNED, and bounds::up.
Referenced by number_of_iterations_lt().
◆ assert_no_overflow_lt()
|
static |
Add assertions to NITER that ensure that the control variable of the loop with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1 are TYPE. Returns false if we can prove that there is an overflow, true otherwise. STEP is the absolute value of the step.
References tree_niter_desc::assumptions, affine_iv::base, boolean_type_node, build_int_cst(), fold_build2, fold_convert, integer_nonzerop(), integer_zerop(), affine_iv::no_overflow, affine_iv::step, TREE_CODE, TREE_TYPE, TYPE_MAX_VALUE, and TYPE_MIN_VALUE.
Referenced by number_of_iterations_lt().
◆ bound_difference()
Stores the bounds on the value of the expression X - Y in LOOP to BNDS. The subtraction is considered to be performed in arbitrary precision, without overflows. We do not attempt to be too clever regarding the value ranges of X and Y; most of the time, they are just integers or ssa names offsetted by integer. However, we try to use the information contained in the comparisons before the loop (usually created by loop header copying).
References as_a(), bounds::below, bound_difference_of_offsetted_base(), CDI_DOMINATORS, cfun, determine_value_range(), end(), ENTRY_BLOCK_PTR_FOR_FN, get_immediate_dominator(), gimple_cond_code(), gimple_cond_lhs(), gimple_cond_rhs(), gsi_last_bb(), loop::header, integer_zerop(), invert_tree_comparison(), MAX_DOMINATORS_TO_WALK, operand_equal_p(), refine_bounds_using_guard(), single_pred_edge(), single_pred_p(), split_to_var_and_offset(), STRIP_SIGN_NOPS, TREE_TYPE, bounds::up, and y.
Referenced by number_of_iterations_cond().
◆ bound_difference_of_offsetted_base()
|
static |
Stores the bounds on the difference of the values of the expressions (var + X) and (var + Y), computed in TYPE, to BNDS.
References bounds::below, wi::minus_one(), nowrap_type_p(), wi::to_mpz(), TYPE_PRECISION, UNSIGNED, bounds::up, and y.
Referenced by bound_difference().
◆ bound_index()
|
static |
Return index of BOUND in BOUNDS array sorted in increasing order. Lookup by binary search.
References begin(), end(), gcc_unreachable, and wi::ltu_p().
Referenced by discover_iteration_bound_by_body_walk().
◆ bounds_add()
|
static |
Update the bounds in BNDS that restrict the value of X to the bounds that restrict the value of X + DELTA. X can be obtained as a difference of two values in TYPE.
References bounds::below, wi::minus_one(), SIGNED, wi::to_mpz(), TYPE_PRECISION, UNSIGNED, and bounds::up.
Referenced by number_of_iterations_le(), and number_of_iterations_lt_to_ne().
◆ bounds_negate()
|
static |
Update the bounds in BNDS that restrict the value of X to the bounds that restrict the value of -X.
References bounds::below, and bounds::up.
Referenced by number_of_iterations_ne().
◆ build_cltz_expr()
Return an expression that counts the leading/trailing zeroes of src. If define_at_zero is true, then the built expression will be defined to return the precision of src when src == 0 (using either a conditional expression or a suitable internal function). Otherwise, we can elide the conditional expression and let src = 0 invoke undefined behaviour.
References boolean_type_node, build_call_expr(), build_call_expr_internal_loc(), build_int_cst(), build_zero_cst(), builtin_decl_implicit(), CLZ_DEFINED_VALUE_AT_ZERO, CTZ_DEFINED_VALUE_AT_ZERO, direct_internal_fn_supported_p(), fold_build2, fold_build3, fold_convert, integer_type_node, long_integer_type_node, long_long_integer_type_node, long_long_unsigned_type_node, NULL_TREE, OPTIMIZE_FOR_BOTH, SCALAR_INT_TYPE_MODE, TREE_TYPE, TYPE_PRECISION, UNKNOWN_LOCATION, unshare_expr(), unsigned_type_for(), and unsigned_type_node.
Referenced by number_of_iterations_cltz(), and number_of_iterations_cltz_complement().
◆ build_popcount_expr()
Return an expression that computes the popcount of src.
References build_call_expr(), build_call_expr_internal_loc(), build_int_cst(), builtin_decl_implicit(), direct_internal_fn_supported_p(), fold_build2, fold_convert, integer_type_node, long_integer_type_node, long_long_integer_type_node, long_long_unsigned_type_node, NULL_TREE, OPTIMIZE_FOR_BOTH, TREE_TYPE, TYPE_PRECISION, UNKNOWN_LOCATION, unshare_expr(), unsigned_type_for(), and unsigned_type_node.
Referenced by number_of_iterations_popcount().
◆ chain_of_csts_start()
Returns the loop phi node of LOOP such that ssa name X is derived from its result by a chain of operations such that all but exactly one of their operands are constants.
References as_a(), chain_of_csts_start(), flow_bb_inside_loop_p(), gimple_assign_rhs1(), gimple_assign_rhs_class(), gimple_assign_rhs_code(), gimple_bb(), gimple_references_memory_p(), GIMPLE_TERNARY_RHS, loop::header, is_gimple_min_invariant(), NULL, NULL_TREE, SINGLE_SSA_TREE_OPERAND, SSA_NAME_DEF_STMT, SSA_OP_USE, tcc_reference, and TREE_CODE_CLASS.
Referenced by chain_of_csts_start(), and get_base_for().
◆ derive_constant_upper_bound()
|
static |
Returns a constant upper bound on the value of expression VAL. VAL is considered to be unsigned. If its type is signed, its value must be nonnegative.
References derive_constant_upper_bound_ops(), extract_ops_from_tree(), and TREE_TYPE.
Referenced by derive_constant_upper_bound_ops(), estimate_numbers_of_iterations(), and record_nonwrapping_iv().
◆ derive_constant_upper_bound_assign()
|
static |
Returns a constant upper bound on the value of the right-hand side of an assignment statement STMT.
References derive_constant_upper_bound_ops(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), and TREE_TYPE.
Referenced by derive_constant_upper_bound_ops().
◆ derive_constant_upper_bound_ops()
|
static |
Returns a constant upper bound on the value of expression OP0 CODE OP1, whose type is TYPE. The expression is considered to be unsigned. If its type is signed, its value must be nonnegative.
References boolean_type_node, CASE_CONVERT, derive_constant_upper_bound(), derive_constant_upper_bound_assign(), fold_binary, gimple_assign_lhs(), integer_nonzerop(), INTEGRAL_TYPE_P, wi::leu_p(), wi::ltu_p(), tree_niter_desc::max, wi::neg_p(), wi::sext(), SSA_NAME_DEF_STMT, wi::to_widest(), TREE_CODE, tree_expr_nonnegative_p(), tree_int_cst_sign_bit(), TREE_TYPE, TYPE_MAX_VALUE, TYPE_PRECISION, TYPE_UNSIGNED, wi::udiv_floor(), upper_bound_in_type(), and wide_int_to_tree().
Referenced by derive_constant_upper_bound(), and derive_constant_upper_bound_assign().
◆ determine_value_range()
|
static |
Stores estimate on the minimum/maximum value of the expression VAR + OFF in TYPE to MIN and MAX.
References as_a(), CDI_DOMINATORS, cfun, ENTRY_BLOCK_PTR_FOR_FN, gcc_assert, get_immediate_dominator(), get_range_query(), get_type_static_bounds(), gimple_cond_code(), gimple_cond_lhs(), gimple_cond_rhs(), gimple_phi_result(), gsi_end_p(), gsi_last_bb(), gsi_next(), gsi_start_phis(), wi::gt_p(), loop::header, integer_zerop(), INTEGRAL_TYPE_P, invert_tree_comparison(), wi::le_p(), loop_preheader_edge(), irange::lower_bound(), wi::max(), MAX_DOMINATORS_TO_WALK, wi::min(), nowrap_type_p(), gphi_iterator::phi(), PHI_ARG_DEF_FROM_EDGE, path_range_query::range_of_expr(), refine_value_range_using_guard(), single_pred_edge(), single_pred_p(), wi::to_mpz(), TREE_CODE, TREE_TYPE, TYPE_SIGN, vrange::undefined_p(), irange::upper_bound(), vrange::varying_p(), VR_RANGE, and VR_VARYING.
Referenced by bound_difference().
◆ discover_iteration_bound_by_body_walk()
|
static |
We recorded loop bounds only for statements dominating loop latch (and thus executed each loop iteration). If there are any bounds on statements not dominating the loop latch we can improve the estimate by walking the loop body and seeing if every path from loop header to loop latch contains some bounded statement.
References loop::any_upper_bound, nb_iter_bound::bound, bound_index(), loop::bounds, dump_file, dump_flags, FOR_EACH_EDGE, gcc_assert, hash_map< KeyId, Value, Traits >::get(), gimple_bb(), loop::header, insert(), nb_iter_bound::is_exit, loop_exit_edge_p(), loop_latch_edge(), wi::ltu_p(), loop::nb_iterations_upper_bound, nb_iter_bound::next, print_decu(), hash_map< KeyId, Value, Traits >::put(), queue, record_niter_bound(), SIGNED, nb_iter_bound::stmt, basic_block_def::succs, TDF_DETAILS, vNULL, and wide_int_cmp().
Referenced by estimate_numbers_of_iterations().
◆ do_warn_aggressive_loop_optimizations()
|
static |
Emit a -Waggressive-loop-optimizations warning if needed.
References CDI_DOMINATORS, cfun, wi::cmpu(), dominated_by_p(), gimple_bb(), gimple_location(), inform(), last_nondebug_stmt(), loop::latch, loop::nb_iterations, NULL, print_dec(), print_dec_buf_size(), PROP_loops, single_exit(), wi::to_widest(), TREE_CODE, TREE_TYPE, TYPE_SIGN, loop::warned_aggressive_loop_optimizations, warning_at(), and WIDE_INT_PRINT_BUFFER_SIZE.
Referenced by record_estimate().
◆ dump_affine_iv()
|
static |
Dumps description of affine induction variable IV to FILE.
References iv::base, dump_file, integer_zerop(), iv::no_overflow, print_generic_expr(), iv::step, and TDF_SLIM.
Referenced by number_of_iterations_cond().
◆ estimate_numbers_of_iterations() [1/2]
| void estimate_numbers_of_iterations | ( | class loop * | loop | ) |
Records estimates on numbers of iterations of LOOP. If USE_UNDEFINED_P is true also use estimates derived from undefined behavior.
References loop::any_estimate, loop::any_upper_bound, tree_niter_desc::bound, build3(), build_int_cst(), derive_constant_upper_bound(), discover_iteration_bound_by_body_walk(), dump_file, dump_flags, dyn_cast(), EST_AVAILABLE, EST_NOT_COMPUTED, loop::estimate_state, expected_loop_iterations_by_profile(), FOR_EACH_VEC_ELT, free(), get_loop_body(), get_loop_exit_edges(), get_upper_bound_based_on_builtin_expr_with_prob(), gsi_last_bb(), i, infer_loop_bounds_from_undefined(), last_nondebug_stmt(), tree_niter_desc::max, maybe_lower_iteration_bound(), wi::min_precision(), loop::nb_iterations, loop::nb_iterations_upper_bound, niter_desc::niter, tree_niter_desc::niter, NULL, NULL_TREE, loop::num, number_of_iterations_exit(), number_of_latch_executions(), record_control_iv(), record_estimate(), record_niter_bound(), SIGNED, single_likely_exit(), TDF_DETAILS, sreal::to_nearest_int(), wi::to_widest(), TREE_CODE, TREE_TYPE, and type().
Referenced by canonicalize_induction_variables(), estimate_numbers_of_iterations(), estimated_loop_iterations(), likely_max_loop_iterations(), loop_exits_before_overflow(), max_loop_iterations(), and tree_unroll_loops_completely().
◆ estimate_numbers_of_iterations() [2/2]
| void estimate_numbers_of_iterations | ( | function * | fn | ) |
Records estimates on numbers of iterations of loops.
References estimate_numbers_of_iterations(), fold_defer_overflow_warnings(), and fold_undefer_and_ignore_overflow_warnings().
◆ estimated_loop_iterations()
| bool estimated_loop_iterations | ( | class loop * | loop, |
| widest_int * | nit ) |
Sets NIT to the estimated number of executions of the latch of the LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as large as the number of iterations. If we have no reliable estimate, the function returns false, otherwise returns true.
References estimate_numbers_of_iterations(), get_estimated_loop_iterations(), and scev_initialized_p().
Referenced by estimated_loop_iterations_int(), and estimated_stmt_executions().
◆ estimated_loop_iterations_int()
| HOST_WIDE_INT estimated_loop_iterations_int | ( | class loop * | loop | ) |
Similar to estimated_loop_iterations, but returns the estimate only if it fits to HOST_WIDE_INT. If this is not the case, or the estimate on the number of iterations of LOOP could not be derived, returns -1.
References estimated_loop_iterations(), wi::fits_shwi_p(), and generic_wide_int< storage >::to_shwi().
Referenced by estimated_stmt_executions_int(), loop_distribution::execute(), parallelize_loops(), tree_ssa_unswitch_loops(), tree_unswitch_outer_loop(), and try_peel_loop().
◆ estimated_stmt_executions()
| bool estimated_stmt_executions | ( | class loop * | loop, |
| widest_int * | nit ) |
Sets NIT to the estimated number of executions of the latch of the LOOP, plus one. If we have no reliable estimate, the function returns false, otherwise returns true.
References estimated_loop_iterations(), and wi::gtu_p().
Referenced by predict_loops(), and vect_create_loop_vinfo().
◆ estimated_stmt_executions_int()
| HOST_WIDE_INT estimated_stmt_executions_int | ( | class loop * | loop | ) |
Returns an estimate for the number of executions of statements in the LOOP. For statements before the loop exit, this exceeds the number of execution of the latch by one.
References estimated_loop_iterations_int().
Referenced by avg_loop_niter(), determine_loop_nest_reuse(), loop_prefetch_arrays(), and vect_analyze_loop_costing().
◆ expand_simple_operations() [1/2]
Header file for loop interation estimates. Copyright (C) 2013-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/>.
References cache, and expand_simple_operations().
◆ expand_simple_operations() [2/2]
|
static |
Expand definitions of ssa names in EXPR as long as they are simple enough, and return the new expression. If STOP is specified, stop expanding if EXPR equals to it.
References ANY_INTEGRAL_TYPE_P, cache, CASE_CONVERT, copy_node(), expand_simple_operations(), expr, fold(), fold_build1, fold_build2, fold_defer_overflow_warnings(), fold_undefer_and_ignore_overflow_warnings(), FOR_EACH_SSA_TREE_OPERAND, get_addr_base_and_unit_offset(), get_gimple_rhs_class(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), gimple_bb(), gimple_phi_num_args(), GIMPLE_SINGLE_RHS, i, IS_EXPR_CODE_CLASS, is_gimple_min_invariant(), basic_block_def::loop_father, mem_ref_offset(), NULL_TREE, offset, PHI_ARG_DEF, single_pred(), sizetype, SSA_NAME_DEF_STMT, SSA_NAME_OCCURS_IN_ABNORMAL_PHI, SSA_OP_USE, TREE_CODE, TREE_CODE_CLASS, TREE_OPERAND, TREE_OPERAND_LENGTH, TREE_TYPE, TYPE_OVERFLOW_TRAPS, and wide_int_to_tree().
Referenced by difference_cannot_overflow_p(), expand_simple_operations(), expand_simple_operations(), find_bivs(), find_givs_in_stmt_scev(), loop_exits_before_overflow(), number_of_iterations_exit_assumptions(), refine_bounds_using_guard(), refine_value_range_using_guard(), simplify_using_initial_conditions(), and tree_simplify_using_condition().
◆ find_loop_niter()
Try to determine the number of iterations of LOOP. If we succeed, expression giving number of iterations is returned and *EXIT is set to the edge from that the information is obtained. Otherwise chrec_dont_know is returned.
References build_int_cst(), chrec_dont_know, FOR_EACH_VEC_ELT, get_loop_exit_edges(), i, integer_nonzerop(), integer_zerop(), tree_niter_desc::may_be_zero, tree_niter_desc::niter, NULL, NULL_TREE, number_of_iterations_exit(), TREE_CODE, tree_int_cst_lt(), and unsigned_type_node.
Referenced by canonicalize_loop_induction_variables().
◆ find_loop_niter_by_eval()
Finds the exit of the LOOP by that the loop exits after a constant number of iterations and stores the exit edge to *EXIT. The constant giving the number of iterations of LOOP is returned. The number of iterations is determined using loop_niter_by_eval (i.e. by brute force evaluation). If we are unable to find the exit for that loop_niter_by_eval determines the number of iterations, chrec_dont_know is returned.
References chrec_contains_undetermined(), chrec_dont_know, FOR_EACH_VEC_ELT, get_loop_exit_edges(), i, just_once_each_iteration_p(), loop_niter_by_eval(), tree_niter_desc::niter, NULL, NULL_TREE, and tree_int_cst_lt().
Referenced by canonicalize_loop_induction_variables().
◆ finite_loop_p()
Return true if loop is known to have bounded number of iterations.
References loop::any_upper_bound, current_function_decl, dump_file, dump_flags, ECF_CONST, ECF_LOOPING_CONST_OR_PURE, ECF_PURE, loop::finite_p, flags_from_decl_or_type(), FOR_EACH_VEC_ELT, get_loop_exit_edges(), i, max_loop_iterations(), loop::num, and TDF_DETAILS.
Referenced by fill_always_executed_in_1(), find_always_executed_bbs(), find_obviously_necessary_stmts(), find_simple_exit(), and finite_function_p().
◆ free_numbers_of_iterations_estimates() [1/2]
| void free_numbers_of_iterations_estimates | ( | class loop * | loop | ) |
Frees the information on upper bounds on numbers of iterations of LOOP.
References nb_iter_bound::bound, loop::bounds, loop::control_ivs, EST_NOT_COMPUTED, loop::estimate_state, ggc_free(), loop::nb_iterations, control_iv::next, nb_iter_bound::next, and NULL.
Referenced by canonicalize_induction_variables(), cleanup_tree_cfg_noloop(), fini_copy_prop(), free_numbers_of_iterations_estimates(), gen_parallel_loop(), tree_loop_interchange::interchange_loops(), loop_optimizer_finalize(), move_sese_region_to_fn(), perform_tree_ssa_dce(), remove_bb(), remove_edge_and_dominated_blocks(), remove_forwarder_block_with_phi(), scev_finalize(), tree_ssa_iv_optimize(), tree_ssa_loop_done(), tree_unroll_loops_completely(), vect_analyze_loop(), and vect_free_loop_info_assumptions().
◆ free_numbers_of_iterations_estimates() [2/2]
| void free_numbers_of_iterations_estimates | ( | function * | fn | ) |
Frees the information on upper bounds on numbers of iterations of loops.
References free_numbers_of_iterations_estimates().
◆ get_base_for()
Determines whether the expression X is derived from a result of a phi node in header of LOOP such that * the derivation of X consists only from operations with constants * the initial value of the phi node is constant * the value of the phi node in the next iteration can be derived from the value in the current iteration by a chain of operations with constants, or is also a constant If such phi node exists, it is returned, otherwise NULL is returned.
References chain_of_csts_start(), is_gimple_min_invariant(), loop_latch_edge(), loop_preheader_edge(), NULL, PHI_ARG_DEF_FROM_EDGE, and TREE_CODE.
Referenced by loop_niter_by_eval().
◆ get_cst_init_from_scev()
This function returns TRUE if below conditions are satisfied:
1) VAR is SSA variable.
2) VAR is an IV:{base, step} in its defining loop.
3) IV doesn't overflow.
4) Both base and step are integer constants.
5) Base is the MIN/MAX value depends on IS_MIN.
Store value of base to INIT correspondingly.
References iv::base, loop_containing_stmt(), iv::no_overflow, NULL, simple_iv(), SSA_NAME_DEF_STMT, iv::step, wi::to_wide(), TREE_CODE, and tree_int_cst_sign_bit().
Referenced by record_nonwrapping_iv().
◆ get_upper_bound_based_on_builtin_expr_with_prob()
Get expected upper bound for number of loop iterations for BUILT_IN_EXPECT_WITH_PROBABILITY for a condition COND.
References build_int_cst(), build_real_from_int_cst(), dyn_cast(), fndecl_built_in_p(), fold_build2, gimple_call_arg(), gimple_call_fndecl(), gimple_call_num_args(), gimple_cond_code(), gimple_cond_lhs(), gimple_cond_rhs(), integer_one_node, integer_zerop(), NULL, NULL_TREE, r, real_to_integer(), SSA_NAME_DEF_STMT, nb_iter_bound::stmt, TREE_CODE, TREE_REAL_CST_PTR, and TREE_TYPE.
Referenced by estimate_numbers_of_iterations().
◆ get_val_for()
Given an expression X, then * if X is NULL_TREE, we return the constant BASE. * if X is a constant, we return the constant X. * otherwise X is a SSA name, whose value in the considered loop is derived by a chain of operations with constant from a result of a phi node in the header of the loop. Then we return value of X when the value of the result of this phi node is given by the constant BASE.
References fold_build1, fold_build2, gcc_checking_assert, gcc_unreachable, get_val_for(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_class(), gimple_assign_rhs_code(), gimple_assign_ssa_name_copy_p(), GIMPLE_BINARY_RHS, GIMPLE_UNARY_RHS, is_gimple_assign(), is_gimple_min_invariant(), SSA_NAME_DEF_STMT, TREE_CODE, and TREE_TYPE.
Referenced by get_val_for(), and loop_niter_by_eval().
◆ idx_infer_loop_bounds()
References analyze_scalar_evolution(), array_ref_flexible_size_p(), array_ref_low_bound(), array_ref_up_bound(), CDI_DOMINATORS, chrec_contains_symbols_defined_in_loop(), dominated_by_p(), evolution_part_in_loop_num(), fold_binary, fold_convert, gimple_bb(), initial_condition(), initial_condition_in_loop_num(), instantiate_parameters(), int_fits_type_p(), integer_zerop(), loop::latch, loop_containing_stmt(), loop::next, NULL, NULL_TREE, loop::num, operand_equal_p(), record_nonwrapping_chrec(), record_nonwrapping_iv(), scev_probably_wraps_p(), TREE_CODE, tree_contains_chrecs(), tree_int_cst_compare(), tree_int_cst_sign_bit(), TREE_TYPE, and type().
Referenced by infer_loop_bounds_from_ref().
◆ infer_loop_bounds_from_array()
Determine information about number of iterations of a LOOP from the way arrays are used in STMT. RELIABLE is true if STMT is guaranteed to be executed in every iteration of LOOP.
References gimple_assign_lhs(), gimple_assign_rhs1(), gimple_call_arg(), gimple_call_lhs(), gimple_call_num_args(), i, infer_loop_bounds_from_ref(), is_gimple_assign(), is_gimple_call(), REFERENCE_CLASS_P, and ilb_data::stmt.
Referenced by infer_loop_bounds_from_undefined().
◆ infer_loop_bounds_from_pointer_arith()
Determine information about number of iterations of a LOOP from the fact that pointer arithmetics in STMT does not overflow.
References analyze_scalar_evolution(), build_int_cstu(), chrec_contains_symbols_defined_in_loop(), chrec_contains_undetermined(), evolution_part_in_loop_num(), expr_invariant_in_loop_p(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), initial_condition_in_loop_num(), instantiate_parameters(), int_cst_value(), is_gimple_assign(), loop_containing_stmt(), lower_bound_in_type(), nowrap_type_p(), NULL, loop::num, record_nonwrapping_chrec(), record_nonwrapping_iv(), ilb_data::stmt, TREE_CODE, tree_contains_chrecs(), TREE_TYPE, type(), TYPE_ALIGN_UNIT, TYPE_PRECISION, and upper_bound_in_type().
Referenced by infer_loop_bounds_from_undefined().
◆ infer_loop_bounds_from_ref()
Determine information about number of iterations a LOOP from the bounds of arrays in the data reference REF accessed in STMT. RELIABLE is true if STMT is guaranteed to be executed in every iteration of LOOP.
References for_each_index(), idx_infer_loop_bounds(), ilb_data::loop, and ilb_data::stmt.
Referenced by infer_loop_bounds_from_array().
◆ infer_loop_bounds_from_signedness()
Determine information about number of iterations of a LOOP from the fact that signed arithmetics in STMT does not overflow.
References analyze_scalar_evolution(), cfun, chrec_contains_symbols_defined_in_loop(), chrec_contains_undetermined(), evolution_part_in_loop_num(), get_range_query(), gimple_assign_lhs(), initial_condition_in_loop_num(), instantiate_parameters(), INTEGRAL_TYPE_P, lower_bound_in_type(), NULL, loop::num, r, path_range_query::range_of_expr(), record_nonwrapping_chrec(), record_nonwrapping_iv(), TREE_CODE, tree_contains_chrecs(), TREE_TYPE, type(), TYPE_OVERFLOW_UNDEFINED, upper_bound_in_type(), and wide_int_to_tree().
Referenced by infer_loop_bounds_from_undefined().
◆ infer_loop_bounds_from_undefined()
|
static |
The following analyzers are extracting informations on the bounds
of LOOP from the following undefined behaviors:
- data references should not access elements over the statically
allocated size,
- signed variables should not overflow when flag_wrapv is not set.
References CDI_DOMINATORS, dominated_by_p(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_stmt(), i, infer_loop_bounds_from_array(), infer_loop_bounds_from_pointer_arith(), infer_loop_bounds_from_signedness(), loop::latch, and loop::num_nodes.
Referenced by estimate_numbers_of_iterations().
◆ inverse()
Returns inverse of X modulo 2^s, where MASK = 2^s-1.
References build_int_cst(), build_int_cst_type(), cst_and_fits_in_hwi(), gcc_assert, HOST_BITS_PER_WIDE_INT, int_const_binop(), int_cst_value(), tree_floor_log2(), TREE_TYPE, and TYPE_PRECISION.
Referenced by number_of_iterations_ne().
◆ is_lshift_by_1()
Returns true if STMT is equivalent to x << 1.
References gimple_assign_rhs2(), gimple_assign_rhs_code(), integer_onep(), tree_fits_shwi_p(), and tree_to_shwi().
Referenced by number_of_iterations_cltz(), and number_of_iterations_cltz_complement().
◆ is_rshift_by_1()
Returns true if STMT is equivalent to x >> 1.
References gimple_assign_lhs(), gimple_assign_rhs2(), gimple_assign_rhs_code(), integer_onep(), tree_fits_shwi_p(), tree_to_shwi(), TREE_TYPE, and TYPE_UNSIGNED.
Referenced by number_of_iterations_cltz(), and number_of_iterations_cltz_complement().
◆ likely_max_loop_iterations()
| bool likely_max_loop_iterations | ( | class loop * | loop, |
| widest_int * | nit ) |
Sets NIT to an likely upper bound for the maximum number of executions of the latch of the LOOP. If we have no reliable estimate, the function returns false, otherwise returns true.
References estimate_numbers_of_iterations(), get_likely_max_loop_iterations(), and scev_initialized_p().
Referenced by likely_max_loop_iterations_int(), and likely_max_stmt_executions().
◆ likely_max_loop_iterations_int()
| HOST_WIDE_INT likely_max_loop_iterations_int | ( | class loop * | loop | ) |
Similar to max_loop_iterations, but returns the estimate only if it fits to HOST_WIDE_INT. If this is not the case, or the estimate on the number of iterations of LOOP could not be derived, returns -1.
References wi::fits_shwi_p(), likely_max_loop_iterations(), and generic_wide_int< storage >::to_shwi().
Referenced by canonicalize_loop_induction_variables(), loop_distribution::execute(), predict_loops(), tree_ssa_unswitch_loops(), tree_unswitch_outer_loop(), and try_peel_loop().
◆ likely_max_stmt_executions()
| bool likely_max_stmt_executions | ( | class loop * | loop, |
| widest_int * | nit ) |
Sets NIT to the estimated maximum number of executions of the latch of the LOOP, plus one. If we have no likely estimate, the function returns false, otherwise returns true.
References wi::gtu_p(), and likely_max_loop_iterations().
Referenced by predict_loops().
◆ loop_exits_before_overflow()
|
static |
Return true if we can prove LOOP is exited before evolution of induction
variable {BASE, STEP} overflows with respect to its type bound.
References control_iv::base, boolean_type_node, nb_iter_bound::bound, loop::bounds, loop::control_ivs, element_precision(), estimate_numbers_of_iterations(), expand_simple_operations(), wi::fits_to_tree_p(), fold_binary, fold_build1, fold_build2, fold_convert, fold_defer_overflow_warnings(), fold_undefer_and_ignore_overflow_warnings(), integer_nonzerop(), integer_zerop(), lower_bound_in_type(), max_loop_iterations(), n_of_executions_at_most(), control_iv::next, tree_niter_desc::niter, NULL, operand_equal_p(), POINTER_TYPE_P, simplify_using_initial_conditions(), control_iv::step, TREE_CODE, tree_int_cst_sign_bit(), TREE_TYPE, TYPE_UNSIGNED, unsigned_type_for(), upper_bound_in_type(), and wide_int_to_tree().
Referenced by scev_probably_wraps_p().
◆ loop_niter_by_eval()
Tries to count the number of iterations of LOOP till it exits by EXIT by brute force -- i.e. by determining the value of the operands of the condition at EXIT in first few iterations of the loop (assuming that these values are constant) and determining the first one in that the condition is not satisfied. Returns the constant giving the number of the iterations of LOOP if successful, chrec_dont_know otherwise.
References boolean_type_node, build_int_cst(), chrec_dont_know, tree_niter_desc::cmp, dump_file, dump_flags, fold_binary, fold_defer_overflow_warnings(), fold_undefer_and_ignore_overflow_warnings(), get_base_for(), get_val_for(), gimple_cond_code(), gimple_cond_lhs(), gimple_cond_rhs(), gsi_last_bb(), i, integer_zerop(), invert_tree_comparison(), is_gimple_min_invariant(), loop_latch_edge(), loop_preheader_edge(), MAX_ITERATIONS_TO_TRACK, NULL_TREE, loop::num, PHI_ARG_DEF_FROM_EDGE, safe_dyn_cast(), TDF_DETAILS, and unsigned_type_node.
Referenced by find_loop_niter_by_eval(), and predict_loops().
◆ loop_only_exit_p()
| bool loop_only_exit_p | ( | const class loop * | loop, |
| basic_block * | body, | ||
| const_edge | exit ) |
Returns true if EXIT is the only possible exit from LOOP.
References gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_stmt(), i, loop::num_nodes, single_exit(), and stmt_can_terminate_bb_p().
Referenced by number_of_iterations_exit_assumptions(), and tree_ssa_iv_optimize_loop().
◆ max_loop_iterations()
| bool max_loop_iterations | ( | class loop * | loop, |
| widest_int * | nit ) |
Sets NIT to an upper bound for the maximum number of executions of the latch of the LOOP. If we have no reliable estimate, the function returns false, otherwise returns true.
References estimate_numbers_of_iterations(), get_max_loop_iterations(), and scev_initialized_p().
Referenced by finite_loop_p(), idx_within_array_bound(), loop_exits_before_overflow(), max_loop_iterations_int(), max_stmt_executions(), may_eliminate_iv(), range_of_var_in_loop(), try_transform_to_exit_first_loop_alt(), vect_iv_limit_for_partial_vectors(), vect_min_prec_for_max_niters(), vect_truncate_gather_scatter_offset(), and vectorizable_reduction().
◆ max_loop_iterations_int()
| HOST_WIDE_INT max_loop_iterations_int | ( | class loop * | loop | ) |
Similar to max_loop_iterations, but returns the estimate only if it fits to HOST_WIDE_INT. If this is not the case, or the estimate on the number of iterations of LOOP could not be derived, returns -1.
References wi::fits_shwi_p(), max_loop_iterations(), and generic_wide_int< storage >::to_shwi().
Referenced by canonicalize_loop_induction_variables(), and predict_loops().
◆ max_stmt_executions()
| bool max_stmt_executions | ( | class loop * | loop, |
| widest_int * | nit ) |
Sets NIT to the maximum number of executions of the latch of the LOOP, plus one. If we have no reliable estimate, the function returns false, otherwise returns true.
References wi::gtu_p(), and max_loop_iterations().
Referenced by is_nonwrapping_integer_induction(), and max_stmt_executions_tree().
◆ maybe_lower_iteration_bound()
|
static |
See if every path cross the loop goes through a statement that is known to not execute at the last iteration. In that case we can decrese iteration count by 1.
References hash_set< KeyId, Lazy, Traits >::add(), BITMAP_ALLOC, BITMAP_FREE, bitmap_set_bit, nb_iter_bound::bound, loop::bounds, hash_set< KeyId, Lazy, Traits >::contains(), dump_file, dump_flags, FOR_EACH_EDGE, gimple_has_side_effects(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_stmt(), loop::header, basic_block_def::index, nb_iter_bound::is_exit, loop_exit_edge_p(), loop_latch_edge(), wi::ltu_p(), loop::nb_iterations_upper_bound, nb_iter_bound::next, NULL, queue, record_niter_bound(), SIGNED, nb_iter_bound::stmt, basic_block_def::succs, TDF_DETAILS, and visited.
Referenced by estimate_numbers_of_iterations().
◆ n_of_executions_at_most()
|
static |
Returns true when we can prove that the number of executions of STMT in the loop is at most NITER, according to the bound on the number of executions of the statement NITER_BOUND->stmt recorded in NITER_BOUND and fact that NITER_BOUND->stmt dominate STMT. ??? This code can become quite a CPU hog - we can have many bounds, and large basic block forcing stmt_dominates_stmt_p to be queried many times on a large basic blocks, so the whole thing is O(n^2) for scev_probably_wraps_p invocation (that can be done n times). It would make more sense (and give better answers) to remember BB bounds computed by discover_iteration_bound_by_body_walk.
References boolean_type_node, nb_iter_bound::bound, tree_niter_desc::bound, tree_niter_desc::cmp, wi::fits_to_tree_p(), fold_binary, gcc_assert, gimple_bb(), gimple_has_side_effects(), gsi_for_stmt(), gsi_next(), gsi_stmt(), integer_nonzerop(), nb_iter_bound::is_exit, tree_niter_desc::niter, SIGNED, nb_iter_bound::stmt, stmt_dominates_stmt_p(), TREE_TYPE, TYPE_UNSIGNED, and wide_int_to_tree().
Referenced by loop_exits_before_overflow().
◆ nowrap_type_p()
Returns true if the arithmetics in TYPE can be assumed not to wrap.
References ANY_INTEGRAL_TYPE_P, POINTER_TYPE_P, and TYPE_OVERFLOW_UNDEFINED.
Referenced by bound_difference_of_offsetted_base(), convert_affine_scev(), determine_value_range(), difference_cannot_overflow_p(), idx_find_step(), infer_loop_bounds_from_pointer_arith(), iv_elimination_compare_lt(), refine_bounds_using_guard(), refine_value_range_using_guard(), scev_probably_wraps_p(), and simple_iv_with_niters().
◆ number_of_iterations_bitcount()
|
static |
See if LOOP contains a bit counting idiom. The idiom consists of two parts: 1. A modification to the induction variabler;. 2. A test to determine whether or not to exit the loop. These can come in either order - i.e.: <bb 3> iv_1 = PHI <src(2), iv_2(4)> if (test (iv_1)) goto <bb 4> else goto <bb 5> <bb 4> iv_2 = modify (iv_1) goto <bb 3> OR <bb 3> iv_1 = PHI <src(2), iv_2(4)> iv_2 = modify (iv_1) <bb 4> if (test (iv_2)) goto <bb 3> else goto <bb 5> The second form can be generated by copying the loop header out of the loop. In the first case, the number of latch executions will be equal to the number of induction variable modifications required before the test fails. In the second case (modify_before_test), if we assume that the number of modifications required before the test fails is nonzero, then the number of latch executions will be one less than this number. If we recognise the pattern, then we update niter accordingly, and return true.
References number_of_iterations_cltz(), number_of_iterations_cltz_complement(), and number_of_iterations_popcount().
Referenced by number_of_iterations_exit_assumptions().
◆ number_of_iterations_cltz()
|
static |
See comment below for number_of_iterations_bitcount. For c[lt]z, we have: modify: iv_2 = iv_1 << 1 OR iv_1 >> 1 test: if (iv & 1 << (prec-1)) OR (iv & 1) modification count: src precision - c[lt]z (src)
References as_a(), tree_niter_desc::assumptions, boolean_false_node, boolean_type_node, tree_niter_desc::bound, build_cltz_expr(), build_int_cst(), build_zero_cst(), tree_niter_desc::cmp, fold_build2, fold_convert, gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), gimple_bb(), gimple_cond_lhs(), gimple_cond_rhs(), gimple_phi_arg_def(), gimple_phi_num_args(), gsi_last_bb(), loop::header, integer_pow2p(), integer_type_node, integer_zerop(), is_gimple_assign(), is_lshift_by_1(), is_rshift_by_1(), loop_latch_edge(), loop_preheader_edge(), tree_niter_desc::max, tree_niter_desc::may_be_zero, tree_niter_desc::niter, NULL_TREE, safe_dyn_cast(), simplify_using_initial_conditions(), SSA_NAME_DEF_STMT, TREE_CODE, tree_log2(), tree_to_uhwi(), TREE_TYPE, TYPE_PRECISION, TYPE_UNSIGNED, and unsigned_type_node.
Referenced by number_of_iterations_bitcount(), and number_of_iterations_exit_assumptions().
◆ number_of_iterations_cltz_complement()
|
static |
See comment below for number_of_iterations_bitcount. For c[lt]z complement, we have: modify: iv_2 = iv_1 >> 1 OR iv_1 << 1 test: if (iv != 0) modification count: src precision - c[lt]z (src)
References as_a(), tree_niter_desc::assumptions, boolean_false_node, boolean_true_node, boolean_type_node, tree_niter_desc::bound, build_cltz_expr(), build_int_cst(), build_zero_cst(), tree_niter_desc::cmp, fold_build2, fold_convert, gimple_assign_rhs1(), gimple_bb(), gimple_cond_lhs(), gimple_cond_rhs(), gimple_phi_arg_def(), gimple_phi_num_args(), gsi_last_bb(), loop::header, integer_one_node, integer_type_node, integer_zerop(), is_gimple_assign(), is_lshift_by_1(), is_rshift_by_1(), loop_latch_edge(), loop_preheader_edge(), tree_niter_desc::max, tree_niter_desc::may_be_zero, tree_niter_desc::niter, NULL_TREE, safe_dyn_cast(), simplify_using_initial_conditions(), SSA_NAME_DEF_STMT, TREE_CODE, tree_to_uhwi(), TREE_TYPE, TYPE_PRECISION, and unsigned_type_node.
Referenced by number_of_iterations_bitcount().
◆ number_of_iterations_cond()
|
static |
Determine the number of iterations according to condition (for staying inside loop) which compares two induction variables using comparison operator CODE. The induction variable on left side of the comparison is IV0, the right-hand side is IV1. Both induction variables must have type TYPE, which must be an integer or pointer type. The steps of the ivs must be constants (or NULL_TREE, which is interpreted as constant zero). LOOP is the loop whose number of iterations we are determining. ONLY_EXIT is true if we are sure this is the only way the loop could be exited (including possibly non-returning function calls, exceptions, etc.) -- in this case we can use the information whether the control induction variables can overflow or not in a more efficient way. if EVERY_ITERATION is true, we know the test is executed on every iteration. The results (number of iterations and assumptions as described in comments at class tree_niter_desc in tree-ssa-loop.h) are stored to NITER. Returns false if it fails to determine number of iterations, true if it was determined (possibly with some assumptions).
References wi::abs(), tree_niter_desc::assumptions, affine_iv::base, bounds::below, boolean_false_node, boolean_true_node, boolean_type_node, tree_niter_desc::bound, bound_difference(), build_int_cst(), tree_niter_desc::cmp, dump_affine_iv(), dump_file, dump_flags, fold_binary, fold_binary_to_constant(), gcc_assert, gcc_unreachable, wi::gtu_p(), integer_nonzerop(), integer_zerop(), tree_niter_desc::max, tree_niter_desc::may_be_zero, tree_niter_desc::niter, affine_iv::no_overflow, NULL_TREE, loop::num, number_of_iterations_le(), number_of_iterations_lt(), number_of_iterations_ne(), POINTER_TYPE_P, print_decu(), print_generic_expr(), sizetype, affine_iv::step, swap_tree_comparison(), TDF_DETAILS, TDF_SLIM, wi::to_widest(), TREE_CODE, tree_int_cst_sign_bit(), type(), unsigned_type_for(), and bounds::up.
Referenced by number_of_iterations_exit_assumptions().
◆ number_of_iterations_exit()
| bool number_of_iterations_exit | ( | class loop * | loop, |
| edge | exit, | ||
| class tree_niter_desc * | niter, | ||
| bool | warn, | ||
| bool | every_iteration, | ||
| basic_block * | body ) |
Like number_of_iterations_exit_assumptions, but return TRUE only if the niter information holds unconditionally.
References tree_niter_desc::assumptions, dump_enabled_p(), dump_printf_loc(), integer_nonzerop(), MSG_MISSED_OPTIMIZATION, and number_of_iterations_exit_assumptions().
Referenced by analyze_function_body(), can_unroll_loop_p(), canonicalize_loop_induction_variables(), estimate_numbers_of_iterations(), find_loop_niter(), niter_for_exit(), number_of_latch_executions(), predict_loops(), remove_redundant_iv_tests(), split_loop(), try_get_loop_niter(), and unroll_jam_possible_p().
◆ number_of_iterations_exit_assumptions()
| bool number_of_iterations_exit_assumptions | ( | class loop * | loop, |
| edge | exit, | ||
| class tree_niter_desc * | niter, | ||
| gcond ** | at_stmt, | ||
| bool | every_iteration, | ||
| basic_block * | body ) |
Stores description of number of iterations of LOOP derived from EXIT (an exit edge of the LOOP) in NITER. Returns true if some useful information could be derived (and fields of NITER have meaning described in comments at class tree_niter_desc declaration), false otherwise. When EVERY_ITERATION is true, only tests that are known to be executed every iteration are considered (i.e. only test that alone bounds the loop). If AT_STMT is not NULL, this function stores LOOP's condition statement in it when returning true.
References tree_niter_desc::assumptions, affine_iv::base, boolean_false_node, boolean_true_node, boolean_type_node, CDI_DOMINATORS, tree_niter_desc::control, dominated_by_p(), expand_simple_operations(), fold_build2, fold_convert, fold_defer_overflow_warnings(), fold_undefer_and_ignore_overflow_warnings(), free(), get_loop_body(), gimple_cond_code(), gimple_cond_lhs(), gimple_cond_rhs(), gsi_last_bb(), integer_nonzerop(), integer_zerop(), invert_tree_comparison(), loop::latch, LOOP_C_FINITE, LOOP_C_INFINITE, loop_constraint_set_p(), loop_containing_stmt(), loop_only_exit_p(), tree_niter_desc::max, tree_niter_desc::may_be_zero, tree_niter_desc::niter, affine_iv::no_overflow, NULL, NULL_TREE, number_of_iterations_bitcount(), number_of_iterations_cltz(), number_of_iterations_cond(), POINTER_TYPE_P, safe_dyn_cast(), simple_iv_with_niters(), simplify_using_initial_conditions(), simplify_using_outer_evolutions(), affine_iv::step, wi::to_widest(), TREE_CODE, TREE_TYPE, and type().
Referenced by number_of_iterations_exit(), vec_init_loop_exit_info(), and vect_get_loop_niters().
◆ number_of_iterations_le()
|
static |
Determines number of iterations of loop whose ending condition is IV0 <= IV1. TYPE is the type of the iv. The number of iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if we know that this condition must eventually become false (we derived this earlier, and possibly set NITER->assumptions to make sure this is the case). BNDS bounds the difference IV1->base - IV0->base.
References tree_niter_desc::assumptions, affine_iv::base, boolean_type_node, bounds_add(), build_int_cst(), fold_build2, fold_build_pointer_plus_hwi, integer_nonzerop(), integer_zerop(), number_of_iterations_lt(), POINTER_TYPE_P, sizetype, affine_iv::step, type(), TYPE_MAX_VALUE, and TYPE_MIN_VALUE.
Referenced by number_of_iterations_cond().
◆ number_of_iterations_lt()
|
static |
Determines number of iterations of loop whose ending condition is IV0 < IV1. TYPE is the type of the iv. The number of iterations is stored to NITER. BNDS bounds the difference IV1->base - IV0->base. EXIT_MUST_BE_TAKEN is true if we know that the exit must be taken eventually.
References assert_loop_rolls_lt(), assert_no_overflow_lt(), affine_iv::base, bounds::below, boolean_type_node, tree_niter_desc::bound, build_int_cst(), tree_niter_desc::cmp, tree_niter_desc::control, fold_build1, fold_build2, fold_convert, wi::from_mpz(), integer_all_onesp(), integer_nonzerop(), integer_onep(), integer_zerop(), tree_niter_desc::max, tree_niter_desc::may_be_zero, tree_niter_desc::niter, affine_iv::no_overflow, number_of_iterations_lt_to_ne(), number_of_iterations_ne(), number_of_iterations_until_wrap(), affine_iv::step, wi::to_mpz(), wi::to_wide(), tree_int_cst_sign_bit(), TYPE_SIGN, UNSIGNED, unsigned_type_for(), and bounds::up.
Referenced by number_of_iterations_cond(), and number_of_iterations_le().
◆ number_of_iterations_lt_to_ne()
|
static |
Checks whether we can determine the final value of the control variable of the loop with ending condition IV0 < IV1 (computed in TYPE). DELTA is the difference IV1->base - IV0->base, STEP is the absolute value of the step. The assumptions necessary to ensure that the computation of the final value does not overflow are recorded in NITER. If we find the final value, we adjust DELTA and return TRUE. Otherwise we return false. BNDS bounds the value of IV1->base - IV0->base, and will be updated by the same amount as DELTA. EXIT_MUST_BE_TAKEN is true if we know that the exit must be taken eventually.
References tree_niter_desc::assumptions, affine_iv::base, bounds::below, boolean_false_node, boolean_true_node, boolean_type_node, bounds_add(), fold_build1, fold_build2, fold_build_pointer_plus, fold_convert, integer_nonzerop(), integer_zerop(), tree_niter_desc::may_be_zero, affine_iv::no_overflow, POINTER_TYPE_P, sizetype, affine_iv::step, wi::to_mpz(), wi::to_wide(), wi::to_widest(), TREE_CODE, TREE_TYPE, type(), TYPE_MAX_VALUE, TYPE_MIN_VALUE, and UNSIGNED.
Referenced by number_of_iterations_lt().
◆ number_of_iterations_ne()
|
static |
Determines number of iterations of loop whose ending condition is IV <> FINAL. TYPE is the type of the iv. The number of iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if we know that the exit must be taken eventually, i.e., that the IV ever reaches the value FINAL (we derived this earlier, and possibly set NITER->assumptions to make sure this is the case). BNDS contains the bounds on the difference FINAL - IV->base.
References tree_niter_desc::assumptions, iv::base, boolean_false_node, boolean_type_node, tree_niter_desc::bound, bounds_negate(), build_int_cst(), build_low_bits_mask(), tree_niter_desc::cmp, tree_niter_desc::control, fold_binary_to_constant(), fold_build1, fold_build2, fold_convert, wi::from_mpz(), integer_nonzerop(), integer_onep(), inverse(), tree_niter_desc::max, multiple_of_p(), tree_niter_desc::niter, affine_iv::no_overflow, iv::no_overflow, num_ending_zeros(), number_of_iterations_ne_max(), POINTER_TYPE_P, simplify_using_initial_conditions(), iv::step, TREE_CODE, tree_int_cst_sign_bit(), tree_to_uhwi(), type(), TYPE_MAX_VALUE, TYPE_MIN_VALUE, TYPE_PRECISION, TYPE_SIGN, and unsigned_type_for().
Referenced by number_of_iterations_cond(), and number_of_iterations_lt().
◆ number_of_iterations_ne_max()
|
static |
Derives the upper bound BND on the number of executions of loop with exit condition S * i <> C. If NO_OVERFLOW is true, then the control variable of the loop does not overflow. EXIT_MUST_BE_TAKEN is true if we are guaranteed that the loop ends through this exit, i.e., the induction variable ever reaches the value of C. The value C is equal to final - base, where final and base are the final and initial value of the actual induction variable in the analysed loop. BNDS bounds the value of this difference when computed in signed type with unbounded range, while the computation of C is performed in an unsigned type with the range matching the range of the type of the induction variable. In particular, BNDS.up contains an upper bound on C in the following cases: -- if the iv must reach its final value without overflow, i.e., if NO_OVERFLOW && EXIT_MUST_BE_TAKEN is true, or -- if final >= base, which we know to hold when BNDS.below >= 0.
References bounds::below, wi::ctz(), integer_onep(), wi::mask(), wi::minus_one(), wi::mod_trunc(), multiple_of_p(), wi::to_mpz(), wi::to_wide(), TREE_CODE, TREE_TYPE, TYPE_OVERFLOW_UNDEFINED, TYPE_PRECISION, TYPE_SIGN, UNSIGNED, and bounds::up.
Referenced by number_of_iterations_ne().
◆ number_of_iterations_popcount()
|
static |
See comment below for number_of_iterations_bitcount. For popcount, we have: modify: _1 = iv_1 + -1 iv_2 = iv_1 & _1 test: if (iv != 0) modification count: popcount (src)
References tree_niter_desc::assumptions, boolean_false_node, boolean_true_node, boolean_type_node, tree_niter_desc::bound, build_popcount_expr(), build_zero_cst(), tree_niter_desc::cmp, fold_build2, fold_convert, gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), gimple_bb(), gimple_cond_lhs(), gimple_cond_rhs(), gimple_phi_arg_def(), gimple_phi_num_args(), gsi_last_bb(), loop::header, integer_one_node, integer_type_node, integer_zerop(), is_gimple_assign(), loop_latch_edge(), loop_preheader_edge(), tree_niter_desc::max, tree_niter_desc::may_be_zero, tree_niter_desc::niter, NULL_TREE, safe_dyn_cast(), simplify_using_initial_conditions(), ssa_defined_by_minus_one_stmt_p(), SSA_NAME_DEF_STMT, TREE_CODE, tree_to_uhwi(), TREE_TYPE, TYPE_PRECISION, and unsigned_type_node.
Referenced by number_of_iterations_bitcount().
◆ number_of_iterations_until_wrap()
|
static |
Determines number of iterations of loop whose ending condition
is IV0 < IV1 which likes: {base, -C} < n, or n < {base, C}.
The number of iterations is stored to NITER.
References tree_niter_desc::assumptions, affine_iv::base, boolean_type_node, tree_niter_desc::bound, tree_niter_desc::cmp, tree_niter_desc::control, fold_build1, fold_build2, fold_convert, integer_nonzerop(), integer_onep(), integer_zerop(), last, tree_niter_desc::max, wi::max_value(), tree_niter_desc::may_be_zero, wi::min_value(), tree_niter_desc::niter, affine_iv::no_overflow, POINTER_TYPE_P, simplify_using_initial_conditions(), affine_iv::step, wi::to_wide(), wi::to_widest(), TREE_CODE, tree_int_cst_sign_bit(), TREE_OPERAND, TREE_TYPE, TYPE_MAX_VALUE, TYPE_PRECISION, TYPE_SIGN, wi::udiv_floor(), UNSIGNED, unsigned_type_for(), and wide_int_to_tree().
Referenced by number_of_iterations_lt().
◆ record_control_iv()
|
static |
Records the control iv analyzed in NITER for LOOP if the iv is valid and doesn't overflow.
References tree_niter_desc::assumptions, affine_iv::base, iv::base, tree_niter_desc::control, loop::control_ivs, ggc_alloc(), integer_onep(), affine_iv::no_overflow, affine_iv::step, and iv::step.
Referenced by estimate_numbers_of_iterations().
◆ record_estimate()
|
static |
Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT is true if the loop is exited immediately after STMT, and this exit is taken at last when the STMT is executed BOUND + 1 times. REALISTIC is true if BOUND is expected to be close to the real number of iterations. UPPER is true if we are sure the loop iterates at most BOUND times. I_BOUND is a widest_int upper estimate on BOUND.
References nb_iter_bound::bound, tree_niter_desc::bound, loop::bounds, CDI_DOMINATORS, do_warn_aggressive_loop_optimizations(), dominated_by_p(), dump_file, dump_flags, gcc_checking_assert, ggc_alloc(), gimple_bb(), nb_iter_bound::is_exit, loop::latch, wi::ltu_p(), wi::min_precision(), loop::nb_iterations, nb_iter_bound::next, NULL_TREE, loop::num, print_decu(), print_generic_expr(), print_gimple_stmt(), record_niter_bound(), SIGNED, nb_iter_bound::stmt, TDF_DETAILS, TDF_SLIM, wi::to_widest(), and TREE_CODE.
Referenced by estimate_numbers_of_iterations(), and record_nonwrapping_iv().
◆ record_nonwrapping_iv()
|
static |
Record the estimate on number of iterations of LOOP based on the fact that the induction variable BASE + STEP * i evaluated in STMT does not wrap and its values belong to the range <LOW, HIGH>. REALISTIC is true if the estimated number of iterations is expected to be close to the real one. UPPER is true if we are sure the induction variable does not wrap.
References CDI_DOMINATORS, cfun, derive_constant_upper_bound(), dominated_by_p(), dump_file, dump_flags, fold_build1, fold_build2, fold_convert, get_cst_init_from_scev(), get_range_query(), gimple_bb(), wi::gts_p(), integer_zerop(), INTEGRAL_TYPE_P, loop::latch, value_range::lbound(), loop::num, print_generic_expr(), print_gimple_stmt(), record_estimate(), TDF_DETAILS, TDF_SLIM, wi::to_wide(), TREE_CODE, tree_int_cst_sign_bit(), TREE_TYPE, value_range::ubound(), value_range::undefined_p(), unsigned_type_for(), value_range::varying_p(), and wide_int_to_tree().
Referenced by idx_infer_loop_bounds(), infer_loop_bounds_from_pointer_arith(), and infer_loop_bounds_from_signedness().
◆ refine_bounds_using_guard()
|
static |
From condition C0 CMP C1 derives information regarding the difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE, and stores it to BNDS.
References bounds::below, end(), expand_simple_operations(), fold_convert, integer_zerop(), INTEGRAL_TYPE_P, nowrap_type_p(), operand_equal_p(), split_to_var_and_offset(), STRIP_SIGN_NOPS, swap_tree_comparison(), TREE_CODE, TREE_TYPE, TYPE_MAX_VALUE, TYPE_MIN_VALUE, TYPE_PRECISION, bounds::up, and useless_type_conversion_p().
Referenced by bound_difference().
◆ refine_value_range_using_guard()
|
static |
From condition C0 CMP C1 derives information regarding the value range of VAR, which is of TYPE. Results are stored in to BELOW and UP.
References cfun, end(), expand_simple_operations(), fold_convert, gcc_assert, get_range_query(), get_type_static_bounds(), integer_zerop(), INTEGRAL_TYPE_P, wi::le_p(), wi::max_value(), wi::min_value(), nowrap_type_p(), operand_equal_p(), r, split_to_var_and_offset(), STRIP_SIGN_NOPS, swap_tree_comparison(), wi::to_mpz(), wi::to_wide(), TREE_CODE, TREE_TYPE, TYPE_PRECISION, TYPE_SIGN, and useless_type_conversion_p().
Referenced by determine_value_range().
◆ scev_probably_wraps_p()
| bool scev_probably_wraps_p | ( | tree | var, |
| tree | base, | ||
| tree | step, | ||
| gimple * | at_stmt, | ||
| class loop * | loop, | ||
| bool | use_overflow_semantics ) |
Return false only when the induction variable BASE + STEP * I is known to not overflow: i.e. when the number of iterations is small enough with respect to the step and initial condition in order to keep the evolution confined in TYPEs bounds. Return true when the iv is known to overflow or when the property is not computable. USE_OVERFLOW_SEMANTICS is true if this function should assume that the rules for overflow of the given language apply (e.g., that signed arithmetics in C does not overflow). If VAR is a ssa variable, this function also returns false if VAR can be proven not overflow with value range info.
References analyze_scalar_evolution(), chrec_contains_undetermined(), integer_zerop(), loop_exits_before_overflow(), nonwrapping_chrec_p(), nowrap_type_p(), scev_var_range_cant_overflow(), TREE_CODE, and TREE_TYPE.
Referenced by convert_affine_scev(), get_scev_info(), and idx_infer_loop_bounds().
◆ scev_var_range_cant_overflow()
VAR is scev variable whose evolution part is constant STEP, this function
proves that VAR can't overflow by using value range info. If VAR's value
range is [MIN, MAX], it can be proven by:
MAX + step doesn't overflow ; if step > 0
or
MIN + step doesn't underflow ; if step < 0.
We can only do this if var is computed in every loop iteration, i.e, var's
definition has to dominate loop latch. Consider below example:
{
unsigned int i;
<bb 3>:
<bb 4>:
# RANGE [0, 4294967294] NONZERO 65535
# i_21 = PHI <0(3), i_18(9)>
if (i_21 != 0)
goto <bb 6>;
else
goto <bb 8>;
<bb 6>:
# RANGE [0, 65533] NONZERO 65535
_6 = i_21 + 4294967295;
# RANGE [0, 65533] NONZERO 65535
_7 = (long unsigned int) _6;
# RANGE [0, 524264] NONZERO 524280
_8 = _7 * 8;
# PT = nonlocal escaped
_9 = a_14 + _8;
*_9 = 0;
<bb 8>:
# RANGE [1, 65535] NONZERO 65535
i_18 = i_21 + 1;
if (i_18 >= 65535)
goto <bb 10>;
else
goto <bb 9>;
<bb 9>:
goto <bb 4>;
<bb 10>:
return;
}
VAR _6 doesn't overflow only with pre-condition (i_21 != 0), here we
can't use _6 to prove no-overlfow for _7. In fact, var _7 takes value
sequence (4294967295, 0, 1, ..., 65533) in loop life time, rather than
(4294967295, 4294967296, ...).
References CDI_DOMINATORS, cfun, dominated_by_p(), get_range_query(), wi::geu_p(), gimple_bb(), INTEGRAL_TYPE_P, loop::latch, lower_bound_in_type(), r, path_range_query::range_of_expr(), SSA_NAME_DEF_STMT, wi::to_wide(), TREE_CODE, tree_int_cst_sign_bit(), TREE_TYPE, type(), and upper_bound_in_type().
Referenced by scev_probably_wraps_p().
◆ simplify_replace_tree()
| tree simplify_replace_tree | ( | tree | expr, |
| tree | old, | ||
| tree | new_tree, | ||
| tree(* | valueize )(tree, void *), | ||
| void * | context, | ||
| bool | do_fold ) |
Substitute NEW_TREE for OLD in EXPR and fold the result. If VALUEIZE is non-NULL then OLD and NEW_TREE are ignored and instead all SSA names are replaced with the result of calling the VALUEIZE function with the SSA name as argument.
References CONSTANT_CLASS_P, copy_node(), expr, EXPR_P, fold(), i, NULL_TREE, operand_equal_p(), simplify_replace_tree(), TREE_CODE, TREE_OPERAND, TREE_OPERAND_LENGTH, and unshare_expr().
Referenced by process_bb(), simplify_replace_tree(), substitute_in_loop_info(), tree_simplify_using_condition_1(), and update_epilogue_loop_vinfo().
◆ simplify_using_initial_conditions()
Tries to simplify EXPR using the conditions on entry to LOOP. Returns the simplified expression (or EXPR unchanged, if no simplification was possible).
References as_a(), boolean_type_node, CDI_DOMINATORS, cfun, ENTRY_BLOCK_PTR_FOR_FN, expand_simple_operations(), expr, fold_build2, get_immediate_dominator(), gimple_cond_code(), gimple_cond_lhs(), gimple_cond_rhs(), gsi_last_bb(), loop::header, integer_nonzerop(), integer_zerop(), invert_truthvalue, MAX_DOMINATORS_TO_WALK, operand_equal_p(), single_pred_edge(), single_pred_p(), TREE_CODE, and tree_simplify_using_condition().
Referenced by loop_exits_before_overflow(), number_of_iterations_cltz(), number_of_iterations_cltz_complement(), number_of_iterations_exit_assumptions(), number_of_iterations_ne(), number_of_iterations_popcount(), number_of_iterations_until_wrap(), and simple_iv_with_niters().
◆ simplify_using_outer_evolutions()
Tries to simplify EXPR using the evolutions of the loop invariants in the superloops of LOOP. Returns the simplified expression (or EXPR unchanged, if no simplification was possible).
References boolean_type_node, changed, expr, fold_build2, fold_build3, instantiate_parameters(), is_gimple_min_invariant(), NULL_TREE, simplify_using_outer_evolutions(), TREE_CODE, and TREE_OPERAND.
Referenced by number_of_iterations_exit_assumptions(), and simplify_using_outer_evolutions().
◆ split_to_var_and_offset()
Splits expression EXPR to a variable part VAR and constant OFFSET.
References build_int_cst_type(), expr, offset, SIGNED, wi::to_mpz(), wi::to_wide(), TREE_CODE, TREE_OPERAND, TREE_TYPE, and TYPE_SIGN.
Referenced by bound_difference(), refine_bounds_using_guard(), and refine_value_range_using_guard().
◆ ssa_defined_by_minus_one_stmt_p()
Utility function to check if OP is defined by a stmt that is a val - 1.
References gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), integer_minus_onep(), is_gimple_assign(), SSA_NAME_DEF_STMT, and TREE_CODE.
Referenced by number_of_iterations_popcount().
◆ stmt_dominates_stmt_p()
Returns true if statement S1 dominates statement S2.
References CDI_DOMINATORS, dominated_by_p(), gimple_bb(), gsi_next(), gsi_start_bb(), and gsi_stmt().
Referenced by n_of_executions_at_most().
◆ substitute_in_loop_info()
Substitute value VAL for ssa name NAME inside expressions held at LOOP.
References loop::nb_iterations, and simplify_replace_tree().
Referenced by replace_uses_by().
◆ tree_simplify_using_condition()
Tries to simplify EXPR using the condition COND. Returns the simplified expression (or EXPR unchanged, if no simplification was possible). Wrapper around tree_simplify_using_condition_1 that ensures that chains of simple operations in definitions of ssa names in COND are expanded, so that things like casts or incrementing the value of the bound before the loop do not cause us to fail.
References expand_simple_operations(), and tree_simplify_using_condition_1().
Referenced by simplify_using_initial_conditions().
◆ tree_simplify_using_condition_1()
Tries to simplify EXPR using the condition COND. Returns the simplified expression (or EXPR unchanged, if no simplification was possible).
References boolean_true_node, boolean_type_node, changed, expr, fold_binary, fold_build2, fold_build3, integer_nonzerop(), integer_zerop(), invert_truthvalue, NULL_TREE, simplify_replace_tree(), TREE_CODE, TREE_OPERAND, and tree_simplify_using_condition_1().
Referenced by tree_simplify_using_condition(), and tree_simplify_using_condition_1().
◆ wide_int_cmp()
|
static |
Compare wide ints, callback for qsort.
References wi::cmpu(), d1, and d2.
Referenced by discover_iteration_bound_by_body_walk().
