#include "config.h"#include "system.h"#include "coretypes.h"#include "tree.h"#include "tree-pretty-print.h"#include "cfgloop.h"#include "gimple.h"#include "tree-ssa-loop-ivopts.h"#include "tree-ssa-loop-niter.h"#include "tree-chrec.h"#include "dumpfile.h"#include "params.h"#include "tree-scalar-evolution.h"
Function Documentation
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().
| 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.
Returns the evolution part of CHREC in LOOP_NUM when RIGHT is true, otherwise returns the initial condition in LOOP_NUM.
There is no evolution part in this loop.
Referenced by hide_evolution_in_other_loops_than_loop().
| bool chrec_contains_symbols | ( | ) |
Determines whether the chrec contains symbolic names or not.
| bool chrec_contains_undetermined | ( | ) |
Determines whether the chrec contains undetermined coefficients.
References cfun, CHREC_LEFT, CHREC_RIGHT, CHREC_VARIABLE, evolution_function_is_invariant_rec_p(), flow_loop_nested_p(), get_chrec_loop(), and get_loop().
Referenced by analyze_overlapping_iterations(), analyze_ziv_subscript(), gcd_of_steps_may_divide_p(), and loop_niter_by_eval().
| 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}
Referenced by follow_ssa_edge_binary(), instantiate_scev_binary(), instantiate_scev_poly(), interpret_loop_phi(), and max_stmt_executions_tree().
|
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.
If we cannot propagate the cast inside the chrec, just keep the cast.
Fold will not canonicalize (long)(i - 1) to (long)i - 1 because that may be more expensive. We do want to perform this optimization here though for canonicalization reasons.
Similar perform the trick that (signed char)((int)x + 2) can be narrowed to (signed char)((unsigned char)x + 2).
Don't propagate overflows.
But reject constants that don't fit in their type after conversion. This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the natural values associated with TYPE_PRECISION and TYPE_UNSIGNED, and can cause problems later when computing niters of loops. Note that we don't do the check before converting because we don't want to reject conversions of negative chrecs to unsigned types.
| 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.
Referenced by instantiate_scev_poly().
| tree chrec_convert_rhs | ( | ) |
Convert CHREC for the right hand side of a CHREC. The increment for a pointer type is always sizetype.
Referenced by chrec_evaluate().
|
static |
Helper function. Use the Newton's interpolating formula for evaluating the value of the evolution function.
References automatically_generated_chrec_p(), build_polynomial_chrec(), build_real_from_int_cst(), chrec_apply(), chrec_contains_symbols_defined_in_loop(), chrec_convert_rhs(), chrec_dont_know, chrec_fold_multiply(), chrec_fold_plus(), CHREC_LEFT, CHREC_RIGHT, chrec_type(), CHREC_VARIABLE, dump_file, dump_flags, evolution_function_is_affine_p(), NULL, SCALAR_FLOAT_TYPE_P, TDF_SCEV, TREE_CODE, and TREE_TYPE.
When the operands are automatically_generated_chrec_p, the fold has to respect the semantics of the operands.
The default case produces a safe result.
References automatically_generated_chrec_p(), chrec_contains_symbols_defined_in_loop(), chrec_fold_plus_poly_poly(), CHREC_VARIABLE, gcc_checking_assert, and TREE_CODE.
Referenced by chrec_fold_plus().
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().
Fold the multiplication of two polynomial functions.
{a, +, b}_1 * {c, +, d}_2 -> {c*{a, +, b}_1, +, d}_2,
{a, +, b}_2 * {c, +, d}_1 -> {a*{c, +, d}_1, +, b}_2,
{a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x.
poly0 is a constant wrt. poly1.
poly1 is a constant wrt. poly0.
poly0 and poly1 are two polynomials in the same variable,
{a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. "a*c".
"a*d + b*c".
"b*d".
"a*d + b*c + b*d".
"2*b*d".
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().
Fold the addition of two chrecs.
Referenced by chrec_fold_plus().
|
inlinestatic |
Fold the addition of two polynomial functions.
This function should never be called for chrecs of loops that do not belong to the same loop nest.
Referenced by chrec_fold_automatically_generated_operands().
|
inlinestatic |
Fold CODE for a polynomial function and a constant.
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().
| 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 | ( | ) |
Returns true when CHREC0 == CHREC1.
References CASE_CONVERT, and TREE_CODE.
Referenced by lambda_matrix_row_exchange().
| bool evolution_function_is_affine_multivariate_p | ( | ) |
Determine whether the given tree is an affine multivariate evolution.
Referenced by evolution_function_is_invariant_rec_p().
| bool evolution_function_is_invariant_p | ( | ) |
Return true if CHREC is invariant in loop LOOPNUM, false otherwise.
References CHREC_LEFT, CHREC_VARIABLE, evolution_function_is_univariate_p(), and TREE_CODE.
|
static |
Recursive helper function.
References CHREC_LEFT, CHREC_RIGHT, CHREC_VARIABLE, evolution_function_is_affine_multivariate_p(), and TREE_CODE.
Referenced by chrec_contains_undetermined().
| bool evolution_function_is_univariate_p | ( | ) |
Determine whether the given tree is a function in zero or one variables.
Referenced by evolution_function_is_invariant_p(), and free_conflict_function().
| bool evolution_function_right_is_integer_cst | ( | ) |
Determines whether the expression CHREC contains only interger consts in the right parts.
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().
| tree initial_condition | ( | ) |
Returns the initial condition of a given CHREC.
Referenced by chrec_replace_initial_condition(), and max_stmt_executions_tree().
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 | ( | ) |
Determine whether the given chrec is multivariate or not.
|
static |
Observers. Helper function for is_multivariate_chrec.
|
inlinestatic |
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/. 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.
| 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 TYPE_UNSIGNED.
|
inlinestatic |
Returns true when the operation can be part of a linear expression.
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 | ( | ) |
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 scev_is_linear_expression(), and TREE_OPERAND.
| 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".
Referenced by scev_direction().
| 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.
|
static |
Operations. Evaluate the binomial coefficient. Return NULL_TREE if the intermediate calculation overflows, otherwise return C(n,k) with type TYPE.
Handle the most frequent cases.
Numerator = n.
Check that k <= n.
Denominator = 2.
Index = Numerator-1.
Numerator = Numerator*Index = n*(n-1).
Index–.
Numerator *= Index.
Denominator *= i.
Result = Numerator / Denominator.
References double_int::from_uhwi(), double_int::mul_with_sign(), and NULL_TREE.
