GCC Middle and Back End API Reference
tree-chrec.h File Reference
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.




bool automatically_generated_chrec_p (const_tree chrec)
bool tree_is_chrec (const_tree expr)
enum ev_direction scev_direction (const_tree)
tree chrec_fold_plus (tree, tree, tree)
tree chrec_fold_minus (tree, tree, tree)
tree chrec_fold_multiply (tree, tree, tree)
tree chrec_convert (tree, tree, gimple *, bool=true, tree=NULL)
tree chrec_convert_rhs (tree, tree, gimple *=NULL)
tree chrec_convert_aggressive (tree, tree, bool *)
tree chrec_apply (unsigned, tree, tree)
tree chrec_apply_map (tree, vec< tree >)
tree chrec_replace_initial_condition (tree, tree)
tree initial_condition (tree)
tree initial_condition_in_loop_num (tree, unsigned)
tree evolution_part_in_loop_num (tree, unsigned)
tree hide_evolution_in_other_loops_than_loop (tree, unsigned)
tree reset_evolution_in_loop (unsigned, tree, tree)
tree chrec_merge (tree, tree)
void for_each_scev_op (tree *, bool(*)(tree *, void *), void *)
bool convert_affine_scev (class loop *, tree, tree *, tree *, gimple *, bool, tree=NULL)
bool eq_evolutions_p (const_tree, const_tree)
bool is_multivariate_chrec (const_tree)
bool chrec_contains_symbols (const_tree, class loop *=NULL)
bool chrec_contains_symbols_defined_in_loop (const_tree, unsigned)
bool chrec_contains_undetermined (const_tree)
bool tree_contains_chrecs (const_tree, int *)
bool evolution_function_is_affine_multivariate_p (const_tree, int)
bool evolution_function_is_univariate_p (const_tree, int=0)
unsigned nb_vars_in_chrec (tree)
bool evolution_function_is_invariant_p (tree, int)
bool scev_is_linear_expression (tree)
bool evolution_function_right_is_integer_cst (const_tree)
bool chrec_zerop (const_tree chrec)
bool no_evolution_in_loop_p (tree chrec, unsigned loop_num, bool *res)
tree build_polynomial_chrec (unsigned loop_num, tree left, tree right)
bool evolution_function_is_constant_p (const_tree chrec)
bool evolution_function_is_affine_in_loop (const_tree chrec, int loopnum)
bool evolution_function_is_affine_p (const_tree chrec)
bool tree_does_not_contain_chrecs (const_tree expr)
tree chrec_type (const_tree chrec)
tree chrec_fold_op (enum tree_code code, tree type, tree op0, tree op1)

Enumeration Type Documentation

◆ ev_direction


Function Documentation

◆ automatically_generated_chrec_p()

bool automatically_generated_chrec_p ( const_tree chrec)
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

GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
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
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()

◆ chrec_apply()

◆ chrec_apply_map()

tree chrec_apply_map ( tree chrec,
vec< tree > iv_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()

bool chrec_contains_symbols ( const_tree chrec,
class loop * loop )
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()

bool chrec_contains_symbols_defined_in_loop ( const_tree chrec,
unsigned loop_nb )
Return true when CHREC contains symbolic names defined in

References chrec_contains_symbols_defined_in_loop(), ggc_alloc(), and visited.

Referenced by no_evolution_in_loop_p().

◆ chrec_contains_undetermined()

bool chrec_contains_undetermined ( const_tree chrec)

◆ chrec_convert()

tree chrec_convert ( tree type,
tree chrec,
gimple * at_stmt,
bool use_overflow_semantics,
tree from )
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) ==
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()

tree chrec_convert_aggressive ( tree type,
tree chrec,
bool * fold_conversions )
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()

tree chrec_convert_rhs ( tree type,
tree chrec,
gimple * at_stmt )
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()

◆ chrec_fold_multiply()

◆ chrec_fold_op()

tree chrec_fold_op ( enum tree_code code,
tree type,
tree op0,
tree op1 )

◆ chrec_fold_plus()

◆ chrec_merge()

tree chrec_merge ( tree chrec1,
tree chrec2 )
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()

tree chrec_replace_initial_condition ( tree chrec,
tree init_cond )

◆ chrec_type()

◆ chrec_zerop()

bool chrec_zerop ( const_tree chrec)
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()

bool convert_affine_scev ( class loop * loop,
tree type,
tree * base,
tree * step,
gimple * at_stmt,
bool use_overflow_semantics,
tree from )
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()

◆ evolution_function_is_affine_in_loop()

bool evolution_function_is_affine_in_loop ( const_tree chrec,
int loopnum )
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()

◆ evolution_function_is_affine_p()

◆ evolution_function_is_constant_p()

bool evolution_function_is_constant_p ( const_tree chrec)

◆ evolution_function_is_invariant_p()

bool evolution_function_is_invariant_p ( tree chrec,
int loopnum )

◆ evolution_function_is_univariate_p()

bool evolution_function_is_univariate_p ( const_tree chrec,
int loopnum )
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()

bool evolution_function_right_is_integer_cst ( const_tree chrec)
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()

tree evolution_part_in_loop_num ( tree chrec,
unsigned 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()

void for_each_scev_op ( tree * scev,
bool(*)(tree *, void *) cbck,
void * data )
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()

tree hide_evolution_in_other_loops_than_loop ( tree chrec,
unsigned loop_num )

◆ initial_condition()

◆ initial_condition_in_loop_num()

tree initial_condition_in_loop_num ( tree chrec,
unsigned 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()

bool is_multivariate_chrec ( const_tree chrec)
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()

unsigned nb_vars_in_chrec ( tree 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()

bool no_evolution_in_loop_p ( tree chrec,
unsigned loop_num,
bool * res )
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()

tree reset_evolution_in_loop ( unsigned loop_num,
tree chrec,
tree new_evol )
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()

bool scev_is_linear_expression ( tree scev)
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()

bool tree_contains_chrecs ( const_tree expr,
int * size )

◆ tree_does_not_contain_chrecs()

bool tree_does_not_contain_chrecs ( const_tree expr)
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()