Go to the source code of this file.
Enumerations | |
| enum | ev_direction { EV_DIR_GROWS , EV_DIR_DECREASES , EV_DIR_UNKNOWN } |
Enumeration Type Documentation
◆ ev_direction
Function Documentation
◆ automatically_generated_chrec_p()
|
inline |
Chains of recurrences. Copyright (C) 2003-2024 Free Software Foundation, Inc. Contributed by Sebastian Pop <pop@cri.ensmp.fr> 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 following trees are unique elements. Thus the comparison of another element to these elements should be done on the pointer to these trees, and not on their value. extern tree chrec_not_analyzed_yet; extern tree chrec_dont_know; extern tree chrec_known; chrec_not_analyzed_yet is NULL_TREE and the others are defined in global_trees[].
After having added an automatically generated element, please include it in the following function.
References chrec_dont_know, and chrec_known.
Referenced by chrec_apply(), chrec_component_in_loop_num(), chrec_convert_1(), chrec_convert_aggressive(), chrec_fold_minus(), chrec_fold_multiply(), chrec_fold_plus(), chrec_fold_plus_1(), chrec_replace_initial_condition(), chrec_type(), convert_affine_scev(), hide_evolution_in_other_loops_than_loop(), initial_condition(), instantiate_scev_r(), interpret_expr(), and tree_is_chrec().
◆ build_polynomial_chrec()
Build a polynomial chain of recurrence.
References build2(), chrec_dont_know, CHREC_VARIABLE, chrec_zerop(), gcc_checking_assert, ggc_alloc(), no_evolution_in_loop_p(), POINTER_TYPE_P, ptrofftype_p(), TREE_TYPE, and types_compatible_p().
Referenced by scev_dfs::add_to_evolution_1(), can_use_analyze_subscript_affine_affine(), chrec_apply(), chrec_component_in_loop_num(), chrec_convert_1(), chrec_convert_aggressive(), chrec_fold_multiply(), chrec_fold_multiply_poly_poly(), chrec_fold_plus_1(), chrec_fold_plus_poly_poly(), chrec_replace_initial_condition(), derive_simple_iv_with_niters(), hide_evolution_in_other_loops_than_loop(), instantiate_scev_poly(), reset_evolution_in_loop(), and simplify_peeled_chrec().
◆ chrec_apply()
Operations.
Evaluates "CHREC (X)" when the varying variable is VAR.
Example: Given the following parameters,
var = 1
chrec = {3, +, 4}_1
x = 10
The result is given by the Newton's interpolating formula:
3 * \binom{10}{0} + 4 * \binom{10}{1}.
References automatically_generated_chrec_p(), build_int_cst(), build_polynomial_chrec(), build_real_from_int_cst(), CASE_CONVERT, chrec_apply(), chrec_contains_symbols_defined_in_loop(), chrec_convert(), chrec_convert_rhs(), chrec_dont_know, chrec_evaluate(), chrec_fold_multiply(), chrec_fold_plus(), CHREC_LEFT, CHREC_RIGHT, chrec_type(), CHREC_VARIABLE, dump_file, dump_flags, evolution_function_is_affine_p(), ggc_alloc(), int_fits_type_p(), integer_all_onesp(), INTEGRAL_TYPE_P, NULL, operand_equal_p(), POINTER_TYPE_P, print_generic_expr(), SCALAR_FLOAT_TYPE_P, TDF_SCEV, TREE_CODE, tree_int_cst_sgn(), TREE_OPERAND, TREE_TYPE, TYPE_OVERFLOW_WRAPS, TYPE_PRECISION, and unsigned_type_for().
Referenced by chrec_apply(), chrec_apply_map(), chrec_is_positive(), and compute_overall_effect_of_inner_loop().
◆ chrec_apply_map()
For a given CHREC and an induction variable map IV_MAP that maps (loop->num, expr) for every loop number of the current_loops an expression, calls chrec_apply when the expression is not NULL.
References chrec_apply(), expr, FOR_EACH_VEC_ELT, ggc_alloc(), and i.
◆ chrec_contains_symbols()
|
extern |
Return true if CHREC contains any symbols. If LOOP is not NULL, check if CHREC contains any chrec which is invariant wrto the loop (nest), in other words, chrec defined by outer loops of loop, so from LOOP's point of view, the chrec is considered as a SYMBOL.
References chrec_contains_symbols(), and visited.
◆ chrec_contains_symbols_defined_in_loop()
|
extern |
Return true when CHREC contains symbolic names defined in LOOP_NB.
References chrec_contains_symbols_defined_in_loop(), ggc_alloc(), and visited.
Referenced by no_evolution_in_loop_p().
◆ chrec_contains_undetermined()
|
extern |
References chrec_contains_undetermined(), and visited.
◆ chrec_convert()
|
extern |
Convert CHREC to TYPE. When the analyzer knows the context in
which the CHREC is built, it sets AT_STMT to the statement that
contains the definition of the analyzed variable, otherwise the
conversion is less accurate: the information is used for
determining a more accurate estimation of the number of iterations.
By default AT_STMT could be safely set to NULL_TREE.
The following rule is always true: TREE_TYPE (chrec) ==
TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
An example of what could happen when adding two chrecs and the type
of the CHREC_RIGHT is different than CHREC_LEFT is:
{(uint) 0, +, (uchar) 10} +
{(uint) 0, +, (uchar) 250}
that would produce a wrong result if CHREC_RIGHT is not (uint):
{(uint) 0, +, (uchar) 4}
instead of
{(uint) 0, +, (uint) 260}
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) -- i.e., to use them to avoid
unnecessary tests, but also to enforce that the result follows them.
FROM is the source variable converted if it's not NULL.
References chrec_convert_1(), and ggc_alloc().
Referenced by scev_dfs::add_to_evolution_1(), analyze_miv_subscript(), analyze_siv_subscript_cst_affine(), analyze_ziv_subscript(), can_use_analyze_subscript_affine_affine(), chrec_apply(), chrec_convert_aggressive(), chrec_convert_rhs(), chrec_evaluate(), chrec_fold_multiply(), chrec_fold_plus(), chrec_fold_plus_1(), convert_affine_scev(), scev_dfs::follow_ssa_edge_binary(), scev_dfs::follow_ssa_edge_expr(), initialize_matrix_A(), instantiate_scev_binary(), instantiate_scev_convert(), instantiate_scev_not(), and interpret_rhs_expr().
◆ chrec_convert_aggressive()
Convert CHREC to TYPE, without regard to signed overflows. Returns the new chrec if something else than what chrec_convert would do happens, NULL_TREE otherwise. This function set TRUE to variable pointed by FOLD_CONVERSIONS if the result chrec may overflow.
References automatically_generated_chrec_p(), build_polynomial_chrec(), chrec_convert(), chrec_convert_aggressive(), CHREC_LEFT, CHREC_RIGHT, CHREC_VARIABLE, convert_affine_scev(), evolution_function_is_affine_p(), gcc_assert, get_chrec_loop(), ggc_alloc(), NULL, NULL_TREE, loop::num, POINTER_TYPE_P, sizetype, TREE_CODE, TREE_TYPE, type(), TYPE_PRECISION, and useless_type_conversion_p().
Referenced by chrec_convert_aggressive(), and instantiate_scev_convert().
◆ chrec_convert_rhs()
Convert CHREC for the right hand side of a CHREC. The increment for a pointer type is always sizetype.
References chrec_convert(), ggc_alloc(), POINTER_TYPE_P, and sizetype.
Referenced by scev_dfs::add_to_evolution_1(), chrec_apply(), chrec_fold_multiply(), instantiate_scev_binary(), and instantiate_scev_poly().
◆ chrec_fold_minus()
Fold the subtraction of two chrecs.
References automatically_generated_chrec_p(), chrec_fold_automatically_generated_operands(), chrec_fold_plus_1(), ggc_alloc(), and integer_zerop().
Referenced by analyze_miv_subscript(), analyze_siv_subscript_cst_affine(), analyze_ziv_subscript(), can_use_analyze_subscript_affine_affine(), chrec_fold_op(), chrec_fold_plus_1(), chrec_fold_plus_poly_poly(), chrec_is_positive(), instantiate_scev_binary(), instantiate_scev_not(), and interpret_rhs_expr().
◆ chrec_fold_multiply()
Fold the multiplication of two chrecs.
References automatically_generated_chrec_p(), build_int_cst(), build_polynomial_chrec(), CASE_CONVERT, chrec_contains_symbols_defined_in_loop(), chrec_convert(), chrec_convert_rhs(), chrec_dont_know, chrec_fold_automatically_generated_operands(), chrec_fold_multiply(), chrec_fold_multiply_poly_poly(), CHREC_LEFT, CHREC_RIGHT, CHREC_VARIABLE, fold_build2, gcc_checking_assert, gcc_unreachable, ggc_alloc(), integer_onep(), integer_zerop(), INTEGRAL_TYPE_P, wi::mul(), NULL, wi::OVF_NONE, wi::to_wide(), TREE_CODE, tree_contains_chrecs(), tree_nop_conversion_p(), TREE_OPERAND, TREE_TYPE, TYPE_OVERFLOW_UNDEFINED, TYPE_SIGN, TYPE_UNSIGNED, and unsigned_type_for().
Referenced by scev_dfs::add_to_evolution(), chrec_apply(), chrec_fold_multiply(), chrec_fold_multiply_poly_poly(), chrec_fold_op(), chrec_fold_plus_1(), chrec_fold_plus_poly_poly(), instantiate_scev_binary(), instantiate_scev_not(), and interpret_rhs_expr().
◆ chrec_fold_op()
References chrec_fold_minus(), chrec_fold_multiply(), chrec_fold_plus(), gcc_unreachable, and ggc_alloc().
Referenced by initialize_matrix_A().
◆ chrec_fold_plus()
Chrec folding functions.
Fold the addition of two chrecs.
References automatically_generated_chrec_p(), chrec_convert(), chrec_fold_automatically_generated_operands(), chrec_fold_plus_1(), ggc_alloc(), integer_zerop(), NULL, and POINTER_TYPE_P.
Referenced by scev_dfs::add_to_evolution_1(), chrec_apply(), chrec_evaluate(), chrec_fold_multiply_poly_poly(), chrec_fold_op(), chrec_fold_plus_1(), chrec_fold_plus_poly_poly(), instantiate_scev_binary(), interpret_rhs_expr(), and simplify_peeled_chrec().
◆ chrec_merge()
Merges two evolution functions that were found by following two alternate paths of a conditional expression.
References chrec_dont_know, chrec_known, chrec_not_analyzed_yet, eq_evolutions_p(), and ggc_alloc().
Referenced by analyze_evolution_in_loop(), analyze_initial_condition(), scev_dfs::follow_ssa_edge_in_condition_phi(), and interpret_condition_phi().
◆ chrec_replace_initial_condition()
Replaces the initial condition in CHREC with INIT_COND.
References automatically_generated_chrec_p(), build_polynomial_chrec(), CHREC_LEFT, chrec_replace_initial_condition(), CHREC_RIGHT, chrec_type(), CHREC_VARIABLE, gcc_assert, ggc_alloc(), and TREE_CODE.
Referenced by chrec_replace_initial_condition(), and dr_analyze_indices().
◆ chrec_type()
|
inline |
Returns the type of the chrec.
References automatically_generated_chrec_p(), NULL_TREE, and TREE_TYPE.
Referenced by scev_dfs::add_to_evolution(), scev_dfs::add_to_evolution_1(), can_use_analyze_subscript_affine_affine(), chrec_apply(), chrec_convert_1(), chrec_fold_multiply_poly_poly(), chrec_fold_plus_poly_poly(), chrec_replace_initial_condition(), initialize_matrix_A(), instantiate_scev_poly(), instantiate_scev_r(), and reset_evolution_in_loop().
◆ chrec_zerop()
|
inline |
Determines whether CHREC is equal to zero.
References ggc_alloc(), integer_zerop(), NULL_TREE, and TREE_CODE.
Referenced by build_polynomial_chrec(), and chrec_fold_plus_poly_poly().
◆ convert_affine_scev()
|
extern |
Converts BASE and STEP of affine scev to TYPE. LOOP is the loop whose iv the scev corresponds to. AT_STMT is the statement at that the scev is evaluated. 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) -- i.e., to use them to avoid unnecessary tests, but also to enforce that the result follows them. FROM is the source variable converted if it's not NULL. Returns true if the conversion succeeded, false otherwise.
References automatically_generated_chrec_p(), build_nonstandard_integer_type(), chrec_convert(), ggc_alloc(), nowrap_type_p(), NULL_TREE, POINTER_TYPE_P, scev_probably_wraps_p(), sizetype, TREE_TYPE, type(), TYPE_PRECISION, and TYPE_UNSIGNED.
Referenced by chrec_convert_1(), chrec_convert_aggressive(), and idx_find_step().
◆ eq_evolutions_p()
|
extern |
Observers.
Returns true when CHREC0 == CHREC1.
References CASE_CONVERT, CHREC_LEFT, CHREC_RIGHT, CHREC_VARIABLE, eq_evolutions_p(), ggc_alloc(), NULL_TREE, operand_equal_p(), TREE_CODE, TREE_OPERAND, TREE_TYPE, and types_compatible_p().
Referenced by analyze_miv_subscript(), analyze_overlapping_iterations(), analyze_subscript_affine_affine(), chrec_merge(), eq_evolutions_p(), same_access_functions(), and same_data_refs().
◆ evolution_function_is_affine_in_loop()
|
inline |
Determine whether CHREC is an affine evolution function in LOOPNUM.
References CHREC_LEFT, CHREC_RIGHT, evolution_function_is_invariant_p(), ggc_alloc(), NULL_TREE, and TREE_CODE.
Referenced by analyze_miv_subscript(), and analyze_siv_subscript().
◆ evolution_function_is_affine_multivariate_p()
|
extern |
Determine whether the given tree is an affine multivariate evolution.
References CHREC_LEFT, CHREC_RIGHT, CHREC_VARIABLE, evolution_function_is_affine_multivariate_p(), evolution_function_is_invariant_rec_p(), ggc_alloc(), NULL_TREE, and TREE_CODE.
Referenced by access_functions_are_affine_or_constant_p(), analyze_miv_subscript(), analyze_overlapping_iterations(), evolution_function_is_affine_multivariate_p(), gather_chrec_stats(), and scev_is_linear_expression().
◆ evolution_function_is_affine_p()
|
inline |
Determine whether CHREC is an affine evolution function or not.
References CHREC_RIGHT, CHREC_VARIABLE, evolution_function_is_affine_p(), evolution_function_is_invariant_p(), ggc_alloc(), and TREE_CODE.
Referenced by chrec_apply(), chrec_convert_1(), chrec_convert_aggressive(), chrec_is_positive(), evolution_function_is_affine_p(), gather_chrec_stats(), and scev_direction().
◆ evolution_function_is_constant_p()
|
inline |
Determines whether the expression CHREC is a constant.
References is_gimple_min_invariant(), and NULL_TREE.
Referenced by analyze_miv_subscript(), analyze_siv_subscript(), can_use_analyze_subscript_affine_affine(), evolution_function_is_invariant_rec_p(), scev_is_linear_expression(), siv_subscript_p(), and ziv_subscript_p().
◆ evolution_function_is_invariant_p()
Return true if CHREC is invariant in loop LOOPNUM, false otherwise.
References evolution_function_is_invariant_rec_p(), and ggc_alloc().
Referenced by access_functions_are_affine_or_constant_p(), any_access_function_variant_p(), evolution_function_is_affine_in_loop(), evolution_function_is_affine_p(), and invariant_access_functions().
◆ evolution_function_is_univariate_p()
|
extern |
Determine whether the given tree is a function in zero or one variables with respect to loop specified by LOOPNUM. Note only positive LOOPNUM stands for a real loop.
References cfun, CHREC_LEFT, CHREC_RIGHT, CHREC_VARIABLE, evolution_function_is_univariate_p(), flow_loop_nested_p(), get_chrec_loop(), get_loop(), ggc_alloc(), NULL, NULL_TREE, TREE_CODE, and tree_contains_chrecs().
Referenced by add_other_self_distances(), evolution_function_is_univariate_p(), and siv_subscript_p().
◆ evolution_function_right_is_integer_cst()
|
extern |
Determines whether the expression CHREC contains only interger consts in the right parts.
References CASE_CONVERT, CHREC_LEFT, CHREC_RIGHT, evolution_function_right_is_integer_cst(), ggc_alloc(), NULL_TREE, TREE_CODE, and TREE_OPERAND.
Referenced by evolution_function_right_is_integer_cst().
◆ evolution_part_in_loop_num()
Returns the evolution part in LOOP_NUM. Example: the call
evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
{1, +, 2}_1
References chrec_component_in_loop_num().
Referenced by get_scev_info(), idx_infer_loop_bounds(), idx_within_array_bound(), infer_loop_bounds_from_pointer_arith(), infer_loop_bounds_from_signedness(), vect_analyze_scalar_cycles_1(), and vect_is_simple_iv_evolution().
◆ for_each_scev_op()
Iterates over all the components of SCEV, and calls CBCK.
References for_each_scev_op(), ggc_alloc(), TREE_CODE, TREE_CODE_LENGTH, and TREE_OPERAND.
Referenced by for_each_scev_op().
◆ hide_evolution_in_other_loops_than_loop()
Returns a univariate function that represents the evolution in LOOP_NUM. Mask the evolution of any other loop.
References automatically_generated_chrec_p(), build_polynomial_chrec(), cfun, chrec_dont_know, CHREC_LEFT, CHREC_RIGHT, flow_loop_nested_p(), get_chrec_loop(), get_loop(), ggc_alloc(), hide_evolution_in_other_loops_than_loop(), initial_condition(), and TREE_CODE.
Referenced by hide_evolution_in_other_loops_than_loop(), and no_evolution_in_loop_p().
◆ initial_condition()
Returns the initial condition of a given CHREC.
References automatically_generated_chrec_p(), CHREC_LEFT, ggc_alloc(), initial_condition(), and TREE_CODE.
Referenced by analyze_siv_subscript_cst_affine(), dr_analyze_indices(), hide_evolution_in_other_loops_than_loop(), idx_infer_loop_bounds(), idx_within_array_bound(), and initial_condition().
◆ initial_condition_in_loop_num()
Returns the initial condition in LOOP_NUM. Example: the call
initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
{0, +, 1}_1
References chrec_component_in_loop_num().
Referenced by get_scev_info(), idx_infer_loop_bounds(), infer_loop_bounds_from_pointer_arith(), infer_loop_bounds_from_signedness(), nb_vars_in_chrec(), vect_analyze_scalar_cycles_1(), and vect_is_simple_iv_evolution().
◆ is_multivariate_chrec()
|
extern |
Determine whether the given chrec is multivariate or not.
References CHREC_LEFT, CHREC_RIGHT, CHREC_VARIABLE, ggc_alloc(), is_multivariate_chrec_rec(), NULL_TREE, and TREE_CODE.
◆ nb_vars_in_chrec()
Returns the number of variables of CHREC. Example: the call
nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2.
References CHREC_VARIABLE, ggc_alloc(), initial_condition_in_loop_num(), nb_vars_in_chrec(), NULL_TREE, and TREE_CODE.
Referenced by analyze_subscript_affine_affine(), and nb_vars_in_chrec().
◆ no_evolution_in_loop_p()
Determines whether CHREC is a loop invariant with respect to LOOP_NUM. Set the result in RES and return true when the property can be computed.
References chrec_contains_symbols_defined_in_loop(), chrec_dont_know, chrec_not_analyzed_yet, ggc_alloc(), hide_evolution_in_other_loops_than_loop(), NULL, STRIP_NOPS, and tree_contains_chrecs().
Referenced by analyze_evolution_in_loop(), analyze_scalar_evolution_in_loop(), build_polynomial_chrec(), and compute_overall_effect_of_inner_loop().
◆ reset_evolution_in_loop()
Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM. This function is essentially used for setting the evolution to chrec_dont_know, for example after having determined that it is impossible to say how many times a loop will execute.
References build_polynomial_chrec(), cfun, CHREC_LEFT, CHREC_RIGHT, chrec_type(), CHREC_VARIABLE, flow_loop_nested_p(), gcc_assert, get_chrec_loop(), get_loop(), ggc_alloc(), POINTER_TYPE_P, ptrofftype_p(), reset_evolution_in_loop(), and TREE_CODE.
Referenced by reset_evolution_in_loop().
◆ scev_direction()
| enum ev_direction scev_direction | ( | const_tree | chrec | ) |
Returns EV_GROWS if CHREC grows (assuming that it does not overflow), EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine which of these cases happens.
References CHREC_RIGHT, EV_DIR_DECREASES, EV_DIR_GROWS, EV_DIR_UNKNOWN, evolution_function_is_affine_p(), ggc_alloc(), TREE_CODE, and tree_int_cst_sign_bit().
Referenced by compute_access_range(), and get_scev_info().
◆ scev_is_linear_expression()
Return true when SCEV is a linear expression. Linear expressions can contain additions, substractions and multiplications. Multiplications are restricted to constant scaling: "cst * x".
References CHREC_VARIABLE, evolution_function_is_affine_multivariate_p(), evolution_function_is_constant_p(), ggc_alloc(), NULL, operator_is_linear(), scev_is_linear_expression(), TREE_CODE, TREE_CODE_LENGTH, tree_contains_chrecs(), and TREE_OPERAND.
Referenced by scev_analyzable_p(), and scev_is_linear_expression().
◆ tree_contains_chrecs()
|
extern |
References tree_contains_chrecs(), and visited.
Referenced by no_evolution_in_loop_p(), and tree_does_not_contain_chrecs().
◆ tree_does_not_contain_chrecs()
|
inline |
Determines whether EXPR does not contains chrec expressions.
References NULL, and tree_contains_chrecs().
Referenced by loop_cand::analyze_induction_var(), final_value_replacement_loop(), and simple_iv_with_niters().
◆ tree_is_chrec()
|
inline |
The tree nodes aka. CHRECs.
References automatically_generated_chrec_p(), ggc_alloc(), and TREE_CODE.
Referenced by split_constant_offset(), tree_contains_chrecs(), vect_can_advance_ivs_p(), vect_is_simple_iv_evolution(), and vect_update_ivs_after_vectorizer().
