Go to the source code of this file.
Enumerations | |
| enum | ev_direction { EV_DIR_GROWS, EV_DIR_DECREASES, EV_DIR_UNKNOWN } |
Variables | |
| tree | chrec_not_analyzed_yet |
| tree | chrec_dont_know |
| tree | chrec_known |
Enumeration Type Documentation
| enum ev_direction |
Function Documentation
|
inlinestatic |
After having added an automatically generated element, please include it in the following function.
Referenced by chrec_evaluate(), chrec_fold_automatically_generated_operands(), and chrec_fold_plus().
Build a polynomial chain of recurrence.
Types of left and right sides of a chrec should be compatible, but pointer CHRECs are special in that the evolution is of ptroff type.
Pointer types should occur only on the left hand side, i.e. in
the base of the chrec, and not in the step.
Referenced by chrec_evaluate(), chrec_replace_initial_condition(), and hide_evolution_in_other_loops_than_loop().
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 * {10}{0} + 4 * {10}{1}.
When the symbols are defined in an outer loop, it is possible
to symbolically compute the apply, since the symbols are
constants with respect to the varying loop.
"{a, +, b} (x)" -> "a + b*x". testsuite/.../ssa-chrec-38.c.
Referenced by analyze_ziv_subscript(), chrec_evaluate(), and compute_overall_effect_of_inner_loop().
| bool chrec_contains_symbols | ( | const_tree | ) |
| bool chrec_contains_symbols_defined_in_loop | ( | const_tree | , |
| unsigned | |||
| ) |
| bool chrec_contains_undetermined | ( | const_tree | ) |
Fold the subtraction of two chrecs.
Referenced by analyze_ziv_subscript(), instantiate_scev_binary(), and max_stmt_executions_tree().
Fold the multiplication of two chrecs.
Referenced by chrec_evaluate(), and instantiate_scev_binary().
|
inlinestatic |
Chrec folding functions.
Fold the addition of two chrecs.
References automatically_generated_chrec_p(), chrec_fold_automatically_generated_operands(), chrec_fold_plus_1(), and integer_zerop().
Referenced by chrec_evaluate(), and tree_does_not_contain_chrecs().
Merges two evolution functions that were found by following two alternate paths of a conditional expression.
Referenced by analyze_evolution_in_loop().
Replaces the initial condition in CHREC with INIT_COND.
References build_polynomial_chrec(), CHREC_LEFT, CHREC_RIGHT, flow_loop_nested_p(), gcc_assert, get_chrec_loop(), hide_evolution_in_other_loops_than_loop(), and initial_condition().
|
inlinestatic |
Returns the type of the chrec.
Referenced by chrec_evaluate(), and instantiate_scev_3().
|
inlinestatic |
Determines whether CHREC is equal to zero.
| 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.
In general,
(TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE – sign extend) STEP * i,
but we must check some assumptions.
1) If [BASE, +, STEP] wraps, the equation is not valid when precision
of CT is smaller than the precision of TYPE. For example, when we
cast unsigned char [254, +, 1] to unsigned, the values on left side
are 254, 255, 0, 1, ..., but those on the right side are
254, 255, 256, 257, ...
2) In case that we must also preserve the fact that signed ivs do not
overflow, we must additionally check that the new iv does not wrap.
For example, unsigned char [125, +, 1] casted to signed char could
become a wrapping variable with values 125, 126, 127, -128, -127, ...,
which would confuse optimizers that assume that this does not
happen.
We can avoid checking whether the result overflows in the following
cases:
– must_check_src_overflow is true, and the range of TYPE is superset
of the range of CT – i.e., in all cases except if CT signed and
TYPE unsigned.
– both CT and TYPE have the same precision and signedness, and we
verify instead that the source does not overflow (this may be
easier than verifying it for the result, as we may use the
information about the semantics of overflow in CT). The step must be sign extended, regardless of the signedness of CT and TYPE. This only needs to be handled specially when CT is unsigned – to avoid e.g. unsigned char [100, +, 255] (with values 100, 99, 98, ...) from becoming signed or unsigned [100, +, 255] with values 100, 355, ...; the sign-extension is performed by default when CT is signed.
Note that in this case we cannot use the fact that signed variables
do not overflow, as this is what we are verifying for the new iv.
| bool eq_evolutions_p | ( | const_tree | , |
| const_tree | |||
| ) |
Observers.
|
inlinestatic |
Determine whether CHREC is an affine evolution function in LOOPNUM.
| bool evolution_function_is_affine_multivariate_p | ( | const_tree | , |
| int | |||
| ) |
|
inlinestatic |
Determine whether CHREC is an affine evolution function or not.
Referenced by analyze_ziv_subscript(), and chrec_evaluate().
|
inlinestatic |
Determines whether the expression CHREC is a constant.
Referenced by free_conflict_function().
| bool evolution_function_is_univariate_p | ( | const_tree | ) |
| bool evolution_function_right_is_integer_cst | ( | const_tree | ) |
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
Referenced by extract_range_from_comparison().
Iterates over all the components of SCEV, and calls CBCK.
Returns a univariate function that represents the evolution in LOOP_NUM. Mask the evolution of any other loop.
There is no evolution in this loop.
References build_polynomial_chrec(), chrec_component_in_loop_num(), CHREC_LEFT, CHREC_RIGHT, CHREC_VARIABLE, flow_loop_nested_p(), gcc_assert, get_chrec_loop(), NULL_TREE, and TREE_CODE.
Referenced by chrec_replace_initial_condition().
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
Referenced by extract_range_from_comparison().
| bool is_multivariate_chrec | ( | const_tree | ) |
| unsigned nb_vars_in_chrec | ( | tree | ) |
|
inlinestatic |
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.
Referenced by analyze_scalar_evolution().
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.
| enum ev_direction scev_direction | ( | const_tree | ) |
| bool tree_contains_chrecs | ( | const_tree | , |
| int * | |||
| ) |
|
inlinestatic |
Determines whether EXPR does not contains chrec expressions.
References chrec_fold_plus().
|
inlinestatic |
The tree nodes aka. CHRECs.
Referenced by vect_can_advance_ivs_p().
Variable Documentation
| tree chrec_dont_know |
Reserved to the cases where the analyzer has detected an undecidable property at compile time.
Referenced by affine_fn_univar(), analyze_evolution_in_loop(), analyze_miv_subscript(), analyze_scalar_evolution(), chrec_evaluate(), follow_ssa_edge_binary(), initialize_data_dependence_relation(), initialize_matrix_A(), instantiate_array_ref(), instantiate_scev_3(), instantiate_scev_binary(), instantiate_scev_not(), instantiate_scev_poly(), lambda_matrix_row_exchange(), loop_phi_node_p(), same_access_functions(), and vect_analyze_scalar_cycles().
| tree chrec_known |
When the analyzer has detected that a property will never happen, then it qualifies it with chrec_known.
Referenced by analyze_overlapping_iterations(), instantiate_scev_3(), omega_extract_distance_vectors(), and vect_analyze_data_ref_dependences().
| tree chrec_not_analyzed_yet |
Chains of recurrences. Copyright (C) 2003-2013 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.
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. The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE.
Referenced by analyze_evolution_in_loop().
