Functions
static bool	is_not_constant_evolution ()
static tree	chrec_fold_poly_cst (enum tree_code code, tree type, tree poly, tree cst)
static tree	chrec_fold_plus_poly_poly (enum tree_code code, tree type, tree poly0, tree poly1)
static tree	chrec_fold_multiply_poly_poly (tree type, tree poly0, tree poly1)
static tree	chrec_fold_automatically_generated_operands (tree op0, tree op1)
static tree	chrec_fold_plus_1 (enum tree_code code, tree type, tree op0, tree op1)
tree	chrec_fold_plus (tree type, tree op0, tree op1)
tree	chrec_fold_minus (tree type, tree op0, tree op1)
tree	chrec_fold_multiply (tree type, tree op0, tree op1)
static tree	tree_fold_binomial ()
static tree	chrec_evaluate ()
tree	chrec_apply (unsigned var, tree chrec, tree x)
tree	chrec_apply_map ()
tree	chrec_replace_initial_condition (tree chrec, tree init_cond)
tree	initial_condition ()
tree	hide_evolution_in_other_loops_than_loop (tree chrec, unsigned loop_num)
static tree	chrec_component_in_loop_num (tree chrec, unsigned loop_num, bool right)
tree	evolution_part_in_loop_num (tree chrec, unsigned loop_num)
tree	initial_condition_in_loop_num (tree chrec, unsigned loop_num)
tree	reset_evolution_in_loop (unsigned loop_num, tree chrec, tree new_evol)
tree	chrec_merge (tree chrec1, tree chrec2)
static bool	is_multivariate_chrec_rec ()
bool	is_multivariate_chrec ()
bool	chrec_contains_symbols ()
bool	chrec_contains_undetermined ()
bool	tree_contains_chrecs ()
static bool	evolution_function_is_invariant_rec_p ()
bool	evolution_function_is_invariant_p ()
bool	evolution_function_is_affine_multivariate_p ()
bool	evolution_function_is_univariate_p ()
unsigned	nb_vars_in_chrec ()
static tree	chrec_convert_1 (tree, tree, gimple, bool)
bool	convert_affine_scev (struct loop loop, tree type, tree base, tree *step, gimple at_stmt, bool use_overflow_semantics)
tree	chrec_convert_rhs ()
tree	chrec_convert ()
tree	chrec_convert_aggressive ()
bool	eq_evolutions_p ()
enum ev_direction	scev_direction ()
void	for_each_scev_op (tree scev, bool(cbck)(tree , void ), void *data)
static bool	operator_is_linear ()
bool	scev_is_linear_expression ()
bool	evolution_function_right_is_integer_cst ()

Function Documentation

tree chrec_apply	(	unsigned	var,
		tree	chrec,
		tree	x
	)

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_polynomial_chrec(), build_real_from_int_cst(), 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_type(), dump_file, dump_flags, evolution_function_is_affine_p(), print_generic_expr(), and tree_int_cst_sgn().

Referenced by chrec_apply(), chrec_apply_map(), chrec_is_positive(), and compute_overall_effect_of_inner_loop().

tree 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().

Referenced by rename_uses().

static tree chrec_component_in_loop_num	(	tree	chrec,
		unsigned	loop_num,
		bool	right
	)

static

Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
   true, otherwise returns the initial condition in LOOP_NUM.

References automatically_generated_chrec_p(), build_polynomial_chrec(), cfun, flow_loop_nested_p(), get_chrec_loop(), and get_loop().

Referenced by evolution_part_in_loop_num(), and initial_condition_in_loop_num().

bool chrec_contains_symbols ( )

Determines whether the chrec contains symbolic names or not.

Referenced by analyze_miv_subscript(), analyze_overlapping_iterations(), analyze_siv_subscript(), can_use_analyze_subscript_affine_affine(), find_scop_parameters(), graphite_can_represent_init(), graphite_can_represent_scev(), and scan_tree_for_params().

bool chrec_contains_undetermined ( )

Determines whether the chrec contains undetermined coefficients.

References chrec_dont_know.

Referenced by analyze_all_data_dependences(), analyze_overlapping_iterations(), build_classic_dist_vector_1(), build_loop_iteration_domains(), canonicalize_loop_induction_variables(), chrec_is_positive(), find_loop_niter_by_eval(), gather_chrec_stats(), graphite_can_represent_loop(), graphite_can_represent_scev(), infer_loop_bounds_from_pointer_arith(), infer_loop_bounds_from_signedness(), number_of_exit_cond_executions(), predicate_scalar_phi(), rename_uses(), scev_analyzable_p(), scev_probably_wraps_p(), simple_iv(), and vect_analyze_loop_form().

tree chrec_convert ( )

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}

References chrec_convert_1().

Referenced by 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_fold_plus(), follow_ssa_edge_binary(), follow_ssa_edge_expr(), follow_ssa_edge_in_rhs(), initialize_matrix_A(), instantiate_scev_binary(), instantiate_scev_convert(), instantiate_scev_not(), interpret_rhs_expr(), and omega_setup_subscript().

static tree chrec_convert_1	(	tree	type,
		tree	chrec,
		gimple	at_stmt,
		bool	use_overflow_semantics
	)

static

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.

   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.

References automatically_generated_chrec_p(), build_polynomial_chrec(), chrec_dont_know, chrec_type(), convert_affine_scev(), evolution_function_is_affine_p(), get_chrec_loop(), int_fits_type_p(), loop::num, and unsigned_type_for().

Referenced by chrec_convert(), and convert_affine_scev().

tree 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.

References automatically_generated_chrec_p(), build_polynomial_chrec(), chrec_convert(), and type().

Referenced by instantiate_scev_convert().

tree 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().

Referenced by add_to_evolution_1(), chrec_apply(), instantiate_scev_binary(), and instantiate_scev_poly().

static tree chrec_evaluate ( )

static

Helper function.  Use the Newton's interpolating formula for
   evaluating the value of the evolution function.

References cfun, chrec_dont_know, chrec_fold_plus(), flow_loop_nested_p(), get_chrec_loop(), get_loop(), and tree_fold_binomial().

Referenced by chrec_apply().

static tree chrec_fold_automatically_generated_operands	(	tree	op0,
		tree	op1
	)

inlinestatic

When the operands are automatically_generated_chrec_p, the fold has
   to respect the semantics of the operands.

References chrec_dont_know, chrec_known, and chrec_not_analyzed_yet.

Referenced by chrec_fold_minus(), chrec_fold_multiply(), chrec_fold_plus(), and chrec_fold_plus_1().

tree chrec_fold_minus	(	tree	type,
		tree	op0,
		tree	op1
	)

Fold the subtraction of two chrecs.

References automatically_generated_chrec_p(), chrec_fold_automatically_generated_operands(), chrec_fold_plus_1(), 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_fold_poly_cst(), chrec_is_positive(), instantiate_scev_binary(), instantiate_scev_not(), interpret_rhs_expr(), and omega_setup_subscript().

tree chrec_fold_multiply	(	tree	type,
		tree	op0,
		tree	op1
	)

Fold the multiplication of two chrecs.

References automatically_generated_chrec_p(), build_int_cst(), build_polynomial_chrec(), chrec_dont_know, chrec_fold_automatically_generated_operands(), chrec_fold_multiply(), chrec_fold_multiply_poly_poly(), integer_onep(), integer_zerop(), and tree_contains_chrecs().

Referenced by 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(), chrec_fold_poly_cst(), instantiate_scev_binary(), instantiate_scev_not(), interpret_rhs_expr(), and omega_setup_subscript().

static tree chrec_fold_multiply_poly_poly	(	tree	type,
		tree	poly0,
		tree	poly1
	)

inlinestatic

Fold the multiplication of two polynomial functions.

References build_int_cst(), build_polynomial_chrec(), build_real(), chrec_fold_multiply(), chrec_fold_plus(), chrec_type(), dconst2, flow_loop_nested_p(), and get_chrec_loop().

Referenced by chrec_fold_multiply().

tree chrec_fold_plus	(	tree	type,
		tree	op0,
		tree	op1
	)

Fold the addition of two chrecs.

References automatically_generated_chrec_p(), chrec_convert(), chrec_fold_automatically_generated_operands(), chrec_fold_plus_1(), and integer_zerop().

Referenced by 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(), chrec_fold_poly_cst(), instantiate_scev_binary(), interpret_rhs_expr(), and number_of_exit_cond_executions().

static tree chrec_fold_plus_1	(	enum tree_code	code,
		tree	type,
		tree	op0,
		tree	op1
	)

static

Fold the addition of two chrecs.

References automatically_generated_chrec_p(), build_int_cst_type(), build_polynomial_chrec(), build_real(), chrec_dont_know, chrec_fold_automatically_generated_operands(), chrec_fold_minus(), chrec_fold_multiply(), chrec_fold_plus(), chrec_fold_plus_poly_poly(), dconstm1, and tree_contains_chrecs().

Referenced by chrec_fold_minus(), and chrec_fold_plus().

static tree chrec_fold_plus_poly_poly	(	enum tree_code	code,
		tree	type,
		tree	poly0,
		tree	poly1
	)

inlinestatic

Fold the addition of two polynomial functions.

References build_int_cst_type(), build_polynomial_chrec(), build_real(), chrec_fold_minus(), chrec_fold_multiply(), chrec_fold_plus(), chrec_type(), chrec_zerop(), dconstm1, flow_loop_nested_p(), get_chrec_loop(), ptrofftype_p(), and type().

Referenced by chrec_fold_plus_1().

static tree chrec_fold_poly_cst	(	enum tree_code	code,
		tree	type,
		tree	poly,
		tree	cst
	)

inlinestatic

Fold CODE for a polynomial function and a constant.

References build_polynomial_chrec(), chrec_dont_know, chrec_fold_minus(), chrec_fold_multiply(), chrec_fold_plus(), chrec_type(), and is_not_constant_evolution().

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, and eq_evolutions_p().

Referenced by analyze_evolution_in_loop(), analyze_initial_condition(), follow_ssa_edge_in_condition_phi(), and interpret_condition_phi().

tree chrec_replace_initial_condition	(	tree	chrec,
		tree	init_cond
	)

Replaces the initial condition in CHREC with INIT_COND.

References automatically_generated_chrec_p(), build_polynomial_chrec(), chrec_replace_initial_condition(), and chrec_type().

Referenced by chrec_replace_initial_condition(), and dr_analyze_indices().

bool convert_affine_scev	(	struct loop *	loop,
		tree	type,
		tree *	base,
		tree *	step,
		gimple	at_stmt,
		bool	use_overflow_semantics
	)

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.  Returns true if the
   conversion succeeded, false otherwise.

References automatically_generated_chrec_p(), build_nonstandard_integer_type(), chrec_convert_1(), nowrap_type_p(), scev_probably_wraps_p(), and type().

Referenced by chrec_convert_1(), and idx_find_step().

bool eq_evolutions_p ( )

Returns true when CHREC0 == CHREC1.

References operand_equal_p().

Referenced by analyze_miv_subscript(), analyze_overlapping_iterations(), analyze_subscript_affine_affine(), chrec_merge(), same_access_functions(), and same_data_refs().

bool evolution_function_is_affine_multivariate_p ( )

Determine whether the given tree is an affine multivariate
   evolution.

References evolution_function_is_invariant_rec_p().

Referenced by access_functions_are_affine_or_constant_p(), analyze_miv_subscript(), analyze_overlapping_iterations(), gather_chrec_stats(), and scev_is_linear_expression().

bool evolution_function_is_invariant_p ( )

Return true if CHREC is invariant in loop LOOPNUM, false otherwise.

References evolution_function_is_invariant_rec_p().

Referenced by access_functions_are_affine_or_constant_p(), evolution_function_is_affine_in_loop(), evolution_function_is_affine_p(), and reduction_phi_p().

static bool evolution_function_is_invariant_rec_p ( )

static

Recursive helper function.

References cfun, evolution_function_is_constant_p(), expr_invariant_in_loop_p(), flow_loop_nested_p(), get_chrec_loop(), and get_loop().

Referenced by evolution_function_is_affine_multivariate_p(), and evolution_function_is_invariant_p().

bool evolution_function_is_univariate_p ( )

Determine whether the given tree is a function in zero or one
   variables.

References tree_contains_chrecs().

Referenced by add_other_self_distances(), and siv_subscript_p().

bool evolution_function_right_is_integer_cst ( )

Determines whether the expression CHREC contains only interger consts
   in the right parts.

Referenced by graphite_can_represent_scev().

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 adjust_range_with_scev(), idx_infer_loop_bounds(), infer_loop_bounds_from_pointer_arith(), infer_loop_bounds_from_signedness(), vect_analyze_scalar_cycles_1(), vect_is_simple_iv_evolution(), and vrp_var_may_overflow().

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().

Referenced by for_each_scev_op().

tree hide_evolution_in_other_loops_than_loop	(	tree	chrec,
		unsigned	loop_num
	)

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, flow_loop_nested_p(), get_chrec_loop(), get_loop(), hide_evolution_in_other_loops_than_loop(), and initial_condition().

Referenced by hide_evolution_in_other_loops_than_loop(), and no_evolution_in_loop_p().

tree initial_condition ( )

Returns the initial condition of a given CHREC.

References automatically_generated_chrec_p().

Referenced by analyze_siv_subscript_cst_affine(), dr_analyze_indices(), hide_evolution_in_other_loops_than_loop(), and idx_infer_loop_bounds().

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 adjust_range_with_scev(), idx_infer_loop_bounds(), infer_loop_bounds_from_pointer_arith(), infer_loop_bounds_from_signedness(), nb_vars_in_chrec(), vect_is_simple_iv_evolution(), and vrp_var_may_overflow().

bool is_multivariate_chrec ( )

Determine whether the given chrec is multivariate or not.

References is_multivariate_chrec_rec().

static bool is_multivariate_chrec_rec ( )

static

Observers.

Helper function for is_multivariate_chrec.

Referenced by is_multivariate_chrec().

static bool is_not_constant_evolution ( )

inlinestatic

@verbatim Chains of recurrences.

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with GCC; see the file COPYING3. If not see http://www.gnu.org/licenses/.

This file implements operations on chains of recurrences.  Chains
   of recurrences are used for modeling evolution functions of scalar
   variables.

Extended folder for chrecs.

Determines whether CST is not a constant evolution.

Referenced by chrec_fold_poly_cst().

unsigned 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 initial_condition_in_loop_num().

Referenced by analyze_subscript_affine_affine().

static bool operator_is_linear ( )

inlinestatic

Returns true when the operation can be part of a linear
   expression.

Referenced by scev_is_linear_expression().

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_type(), flow_loop_nested_p(), get_chrec_loop(), get_loop(), ptrofftype_p(), and reset_evolution_in_loop().

Referenced by reset_evolution_in_loop().

enum ev_direction scev_direction ( )

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 EV_DIR_DECREASES, EV_DIR_GROWS, EV_DIR_UNKNOWN, evolution_function_is_affine_p(), and tree_int_cst_sign_bit().

Referenced by adjust_range_with_scev().

bool 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 evolution_function_is_affine_multivariate_p(), operator_is_linear(), and tree_contains_chrecs().

Referenced by graphite_can_represent_scev().

bool tree_contains_chrecs ( )

Determines whether the tree EXPR contains chrecs, and increment
   SIZE if it is not a NULL pointer by an estimation of the depth of
   the tree.

References tree_is_chrec().

Referenced by chrec_fold_multiply(), chrec_fold_plus_1(), evolution_function_is_univariate_p(), idx_infer_loop_bounds(), infer_loop_bounds_from_pointer_arith(), infer_loop_bounds_from_signedness(), no_evolution_in_loop_p(), remove_invariant_phi(), rename_uses(), rewrite_cross_bb_scalar_deps(), scev_is_linear_expression(), simple_iv(), and tree_does_not_contain_chrecs().

static tree tree_fold_binomial ( )

static

Operations.

Evaluate the binomial coefficient.  Return NULL_TREE if the intermediate
   calculation overflows, otherwise return C(n,k) with type TYPE.

References build_int_cst(), build_int_cst_wide(), double_int::div(), double_int::from_uhwi(), double_int::high, int_fits_type_p(), double_int::low, double_int::mul_with_sign(), loop::num, and double_int::ult().

Referenced by chrec_evaluate().

Functions

Function Documentation