#include "config.h"#include "system.h"#include "coretypes.h"#include "backend.h"#include "target.h"#include "rtl.h"#include "optabs-query.h"#include "tree.h"#include "gimple.h"#include "ssa.h"#include "gimple-pretty-print.h"#include "fold-const.h"#include "gimplify.h"#include "gimple-iterator.h"#include "gimplify-me.h"#include "tree-cfg.h"#include "tree-ssa-loop-ivopts.h"#include "tree-ssa-loop-manip.h"#include "tree-ssa-loop-niter.h"#include "tree-ssa-loop.h"#include "tree-ssa.h"#include "cfgloop.h"#include "tree-chrec.h"#include "tree-affine.h"#include "tree-scalar-evolution.h"#include "dumpfile.h"#include "tree-ssa-propagate.h"#include "gimple-fold.h"#include "tree-into-ssa.h"#include "builtins.h"#include "case-cfn-macros.h"#include "gt-tree-scalar-evolution.h"
Data Structures | |
| struct | scev_info_str |
| struct | scev_info_hasher |
| class | instantiate_cache_type |
| class | scev_dfs |
| struct | chrec_stats |
Enumerations | |
| enum | t_bool { t_false , t_true , t_dont_know } |
Variables | |
| static unsigned | nb_set_scev = 0 |
| static unsigned | nb_get_scev = 0 |
| static hash_table< scev_info_hasher > * | scalar_evolution_info |
| static instantiate_cache_type * | global_cache |
Enumeration Type Documentation
◆ t_bool
Function Documentation
◆ analyze_and_compute_bitop_with_inv_effect()
|
static |
Return the inductive expression of bitop with invariant if possible, otherwise returns DEF.
References build_zero_cst(), expr_invariant_in_loop_p(), fold_build2, ggc_alloc(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), gimple_bb(), gimple_phi_num_args(), loop::header, is_gimple_assign(), loop_latch_edge(), loop_preheader_edge(), NULL, NULL_TREE, PHI_ARG_DEF_FROM_EDGE, SSA_NAME_DEF_STMT, TREE_CODE, tree_fits_uhwi_p(), tree_to_uhwi(), and TREE_TYPE.
Referenced by final_value_replacement_loop().
◆ analyze_and_compute_bitwise_induction_effect()
|
static |
Return the inductive expression of bitwise operation if possible, otherwise returns DEF.
References analyze_scalar_evolution(), wi::bit_not(), build_all_ones_cst(), build_zero_cst(), CHREC_LEFT, CHREC_RIGHT, fold_build2, gcc_assert, gcc_unreachable, ggc_alloc(), gimple_assign_rhs_code(), gimple_bb(), gimple_bitwise_induction_p(), gimple_phi_num_args(), loop::header, i, instantiate_parameters(), INTEGRAL_TYPE_P, loop_latch_edge(), loop_preheader_edge(), NULL, NULL_TREE, PHI_ARG_DEF_FROM_EDGE, wi::set_bit(), SSA_NAME_DEF_STMT, TREE_CODE, tree_fits_shwi_p(), tree_fits_uhwi_p(), tree_to_shwi(), tree_to_uhwi(), TREE_TYPE, TYPE_PRECISION, wide_int_to_tree(), and wi::zero().
Referenced by final_value_replacement_loop().
◆ analyze_evolution_in_loop()
Given a LOOP_PHI_NODE, this function determines the evolution function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop.
References chrec_dont_know, chrec_merge(), chrec_not_analyzed_yet, dump_file, dump_flags, flow_bb_inside_loop_p(), scev_dfs::get_ev(), ggc_alloc(), gimple_phi_arg_edge(), gimple_phi_num_args(), i, loop_containing_stmt(), no_evolution_in_loop_p(), loop::num, operand_equal_p(), PHI_ARG_DEF, print_generic_expr(), print_gimple_stmt(), simplify_peeled_chrec(), t_false, t_true, TDF_SCEV, and TREE_CODE.
Referenced by interpret_loop_phi().
◆ analyze_initial_condition()
Given a loop-phi-node, return the initial conditions of the variable on entry of the loop. When the CCP has propagated constants into the loop-phi-node, the initial condition is instantiated, otherwise the initial condition is kept symbolic. This analyzer does not analyze the evolution outside the current loop, and leaves this task to the on-demand tree reconstructor.
References chrec_dont_know, chrec_merge(), chrec_not_analyzed_yet, dump_file, dump_flags, flow_bb_inside_loop_p(), follow_copies_to_constant(), ggc_alloc(), gimple_phi_arg_edge(), gimple_phi_num_args(), i, loop_containing_stmt(), PHI_ARG_DEF, print_generic_expr(), print_gimple_stmt(), TDF_SCEV, and TREE_CODE.
Referenced by interpret_loop_phi().
◆ analyze_scalar_evolution()
Analyzes and returns the scalar evolution of the ssa_name VAR in LOOP. LOOP is the loop in which the variable is used. Example of use: having a pointer VAR to a SSA_NAME node, STMT a pointer to the statement that uses this variable, in order to determine the evolution function of the variable, use the following calls: loop_p loop = loop_containing_stmt (stmt); tree chrec_with_symbols = analyze_scalar_evolution (loop, var); tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
References analyze_scalar_evolution_1(), block_before_loop(), chrec_not_analyzed_yet, dump_file, dump_flags, get_scalar_evolution(), ggc_alloc(), global_cache, NULL, loop::num, print_generic_expr(), and TDF_SCEV.
Referenced by analyze_and_compute_bitwise_induction_effect(), loop_cand::analyze_carried_vars(), analyze_scalar_evolution_for_address_of(), analyze_scalar_evolution_in_loop(), compute_access_range(), compute_access_stride(), constant_after_peeling(), dr_analyze_indices(), scev_dfs::follow_ssa_edge_inner_loop_phi(), get_base_for_alignment_1(), get_scev_info(), idx_infer_loop_bounds(), idx_within_array_bound(), infer_loop_bounds_from_pointer_arith(), infer_loop_bounds_from_signedness(), instantiate_scev_name(), tree_loop_interchange::interchange_loops(), interpret_condition_phi(), interpret_rhs_expr(), predicate_scalar_phi(), scalar_evolution_in_region(), scev_probably_wraps_p(), simplify_peeled_chrec(), and vect_analyze_scalar_cycles_1().
◆ analyze_scalar_evolution_1()
Scalar evolution detector. Copyright (C) 2003-2024 Free Software Foundation, Inc. Contributed by Sebastian Pop <s.pop@laposte.net> 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 section contains all the entry points: - number_of_iterations_in_loop, - analyze_scalar_evolution, - instantiate_parameters.
Helper recursive function.
References analyze_scalar_evolution_1(), block_before_loop(), chrec_contains_symbols_defined_in_loop(), chrec_dont_know, compute_overall_effect_of_inner_loop(), flow_bb_inside_loop_p(), follow_copies_to_constant(), ggc_alloc(), gimple_bb(), interpret_condition_phi(), interpret_expr(), interpret_gimple_assign(), interpret_loop_phi(), loop_depth(), basic_block_def::loop_father, loop_phi_node_p(), NULL, loop::num, set_scalar_evolution(), SSA_NAME_DEF_STMT, superloop_at_depth(), and TREE_CODE.
Referenced by analyze_scalar_evolution(), and analyze_scalar_evolution_1().
◆ analyze_scalar_evolution_for_address_of()
Analyzes and returns the scalar evolution of VAR address in LOOP.
References analyze_scalar_evolution(), and build_fold_addr_expr.
Referenced by interpret_rhs_expr().
◆ analyze_scalar_evolution_in_loop()
|
static |
Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
WRTO_LOOP (which should be a superloop of USE_LOOP)
FOLDED_CASTS is set to true if resolve_mixers used
chrec_convert_aggressive (TODO -- not really, we are way too conservative
at the moment in order to keep things simple).
To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
example:
for (i = 0; i < 100; i++) -- loop 1
{
for (j = 0; j < 100; j++) -- loop 2
{
k1 = i;
k2 = j;
use2 (k1, k2);
for (t = 0; t < 100; t++) -- loop 3
use3 (k1, k2);
}
use1 (k1, k2);
}
Both k1 and k2 are invariants in loop3, thus
analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
As they are invariant, it does not matter whether we consider their
usage in loop 3 or loop 2, hence
analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
Similarly for their evolutions with respect to loop 1. The values of K2
in the use in loop 2 vary independently on loop 1, thus we cannot express
the evolution with respect to loop 1:
analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
The value of k2 in the use in loop 1 is known, though:
analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
References analyze_scalar_evolution(), chrec_dont_know, ggc_alloc(), loop_outer(), no_evolution_in_loop_p(), and resolve_mixers().
Referenced by final_value_replacement_loop(), and simple_iv_with_niters().
◆ backedge_phi_arg_p()
Checks whether the I-th argument of a PHI comes from a backedge.
References ggc_alloc(), gimple_phi_arg_edge(), and i.
Referenced by scev_dfs::follow_ssa_edge_in_condition_phi_branch(), and interpret_condition_phi().
◆ compute_overall_effect_of_inner_loop()
Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
In general, in the case of multivariate evolutions we want to get
the evolution in different loops. LOOP specifies the level for
which to get the evolution.
Example:
| for (j = 0; j < 100; j++)
| {
| for (k = 0; k < 100; k++)
| {
| i = k + j; - Here the value of i is a function of j, k.
| }
| ... = i - Here the value of i is a function of j.
| }
| ... = i - Here the value of i is a scalar.
Example:
| i_0 = ...
| loop_1 10 times
| i_1 = phi (i_0, i_2)
| i_2 = i_1 + 2
| endloop
This loop has the same effect as:
LOOP_1 has the same effect as:
| i_1 = i_0 + 20
The overall effect of the loop, "i_0 + 20" in the previous example,
is obtained by passing in the parameters: LOOP = 1,
EVOLUTION_FN = {i_0, +, 2}_1.
References chrec_apply(), chrec_contains_symbols_defined_in_loop(), chrec_dont_know, compute_overall_effect_of_inner_loop(), flow_loop_nested_p(), get_chrec_loop(), ggc_alloc(), instantiate_parameters(), no_evolution_in_loop_p(), loop::num, number_of_latch_executions(), and TREE_CODE.
Referenced by analyze_scalar_evolution_1(), compute_overall_effect_of_inner_loop(), final_value_replacement_loop(), scev_dfs::follow_ssa_edge_inner_loop_phi(), and instantiate_scev_name().
◆ derive_simple_iv_with_niters()
Given EV with form of "(type) {inner_base, inner_step}_loop", this
function tries to derive condition under which it can be simplified
into "{(type)inner_base, (type)inner_step}_loop". The condition is
the maximum number that inner iv can iterate.
References build_polynomial_chrec(), CHREC_LEFT, CHREC_RIGHT, CHREC_VARIABLE, CONVERT_EXPR_P, fold_build1, fold_build2, fold_convert, ggc_alloc(), integer_zerop(), lower_bound_in_type(), TREE_CODE, tree_int_cst_sign_bit(), TREE_OPERAND, TREE_TYPE, TYPE_PRECISION, and upper_bound_in_type().
Referenced by simple_iv_with_niters().
◆ dump_chrecs_stats()
|
static |
Dump the contents of a CHREC_STATS structure.
References ggc_alloc(), nb_get_scev, nb_set_scev, and scalar_evolution_info.
Referenced by gather_stats_on_scev_database().
◆ eq_idx_scev_info()
Compares database elements E1 and E2.
References instantiate_cache_type::entries, scev_info_hasher::equal(), ggc_alloc(), and global_cache.
Referenced by get_instantiated_value_entry().
◆ expression_expensive_p() [1/2]
References cache, expression_expensive_p(), and ggc_alloc().
◆ expression_expensive_p() [2/2]
|
static |
Returns true if the expression EXPR is considered to be too expensive for scev_const_prop. Sets *COND_OVERFLOW_P to true when the expression might contain a sub-expression that is subject to undefined overflow behavior and conditionally evaluated.
References cache, CALL_EXPR_ARG, CFN_LAST, EXPR_P, expression_expensive_p(), FOR_EACH_CALL_EXPR_ARG, FOR_EACH_WIDER_MODE, FOR_EACH_WIDER_MODE_FROM, generic_expr_could_trap_p(), get_call_combined_fn(), get_callee_fndecl(), GET_MODE_SIZE(), ggc_alloc(), integer_pow2p(), is_gimple_val(), is_inexpensive_builtin(), optab_handler(), tcc_binary, tcc_comparison, tcc_unary, TREE_CODE, TREE_CODE_CLASS, TREE_OPERAND, TREE_SIDE_EFFECTS, TREE_TYPE, TYPE_MODE, and word_mode.
Referenced by expression_expensive_p(), expression_expensive_p(), final_value_replacement_loop(), and may_eliminate_iv().
◆ final_value_replacement_loop()
Do final value replacement for LOOP, return true if we did anything.
References analyze_and_compute_bitop_with_inv_effect(), analyze_and_compute_bitwise_induction_effect(), analyze_scalar_evolution_in_loop(), ANY_INTEGRAL_TYPE_P, arith_code_with_undefined_signed_overflow(), chrec_contains_symbols_defined_in_loop(), chrec_dont_know, compute_overall_effect_of_inner_loop(), CONSTANT_CLASS_P, contains_abnormal_ssa_name_p(), dump_file, dump_flags, expression_expensive_p(), force_gimple_operand(), ggc_alloc(), gimple_assign_rhs_code(), gimple_build_assign(), gimple_phi_arg_location(), gimple_seq_add_stmt(), gimple_set_location(), gsi_after_labels(), gsi_end_p(), gsi_insert_seq_before(), gsi_next(), GSI_SAME_STMT, gsi_start(), gsi_start_phis(), gsi_stmt(), INTEGRAL_TYPE_P, is_gimple_assign(), loop_depth(), NULL_TREE, number_of_latch_executions(), gphi_iterator::phi(), PHI_ARG_DEF_FROM_EDGE, PHI_RESULT, POINTER_TYPE_P, print_generic_expr(), print_gimple_stmt(), remove_phi_node(), replace_uses_by(), rewrite_to_defined_overflow(), single_exit(), single_pred_p(), split_loop_exit_edge(), SSA_NAME_DEF_STMT, SSA_NAME_OCCURS_IN_ABNORMAL_PHI, superloop_at_depth(), TDF_DETAILS, tree_does_not_contain_chrecs(), tree_fits_uhwi_p(), tree_to_uhwi(), TREE_TYPE, TYPE_OVERFLOW_UNDEFINED, TYPE_PRECISION, unshare_expr(), and virtual_operand_p().
Referenced by try_create_reduction_list().
◆ find_var_scev_info()
|
static |
Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block. A first query on VAR returns chrec_not_analyzed_yet.
References scev_info_str::chrec, ggc_alloc(), scev_info_str::instantiated_below, new_scev_info_str(), scalar_evolution_info, and SSA_NAME_VERSION.
Referenced by get_scalar_evolution(), and set_scalar_evolution().
◆ follow_copies_to_constant()
Looks to see if VAR is a copy of a constant (via straightforward assignments or degenerate phi's). If so, returns the constant; else, returns VAR.
References CONSTANT_CLASS_P, degenerate_phi_result(), ggc_alloc(), gimple_assign_rhs1(), gimple_assign_single_p(), name_registered_for_update_p(), SSA_NAME_DEF_STMT, and TREE_CODE.
Referenced by analyze_initial_condition(), and analyze_scalar_evolution_1().
◆ gather_chrec_stats()
|
static |
Gather statistics about CHREC.
References chrec_contains_undetermined(), dump_file, dump_flags, evolution_function_is_affine_multivariate_p(), evolution_function_is_affine_p(), ggc_alloc(), NULL_TREE, print_generic_expr(), TDF_STATS, and TREE_CODE.
Referenced by gather_stats_on_scev_database().
◆ gather_stats_on_scev_database()
Classify the chrecs of the whole database.
References scev_info_str::chrec, dump_chrecs_stats(), dump_file, FOR_EACH_HASH_TABLE_ELEMENT, gather_chrec_stats(), reset_chrecs_counters(), and scalar_evolution_info.
◆ get_instantiated_value_entry()
|
static |
Returns from CACHE the slot number of the cached chrec for NAME.
References cache, scev_info_str::chrec, chrec_not_analyzed_yet, eq_idx_scev_info(), ggc_alloc(), scev_info_hasher::hash(), hash_idx_scev_info(), scev_info_str::instantiated_below, scev_info_str::name_version, NULL, and SSA_NAME_VERSION.
Referenced by instantiate_scev_name().
◆ get_loop_exit_condition() [1/2]
This section selects the loops that will be good candidates for the scalar evolution analysis. For the moment, greedily select all the loop nests we could analyze.
For a loop with a single exit edge, return the COND_EXPR that guards the exit edge. If the expression is too difficult to analyze, then give up.
References get_loop_exit_condition(), and single_exit().
Referenced by find_loop_location(), get_loop_exit_condition(), slpeel_can_duplicate_loop_p(), vec_init_loop_exit_info(), vect_get_loop_niters(), vect_set_loop_condition(), and vect_set_loop_condition_normal().
◆ get_loop_exit_condition() [2/2]
| gcond * get_loop_exit_condition | ( | const_edge | exit_edge | ) |
If the statement just before the EXIT_EDGE contains a condition then return the condition, otherwise NULL.
References dump_file, dump_flags, ggc_alloc(), gsi_last_bb(), NULL, print_gimple_stmt(), and TDF_SCEV.
◆ get_scalar_evolution()
|
static |
Retrieve the chrec associated to SCALAR instantiated below INSTANTIATED_BELOW block.
References chrec_not_analyzed_yet, dump_file, dump_flags, find_var_scev_info(), ggc_alloc(), nb_get_scev, print_generic_expr(), SSA_NAME_IS_DEFAULT_DEF, TDF_SCEV, TDF_STATS, TREE_CODE, TREE_TYPE, and VECTOR_TYPE_P.
Referenced by analyze_scalar_evolution().
◆ gimple_bitop_with_inv_p()
Match.pd function to match bitop with invariant expression .i.e. tmp_7 = _0 & _1;
◆ gimple_bitwise_induction_p()
Match.pd function to match bitwise inductive expression. .i.e. _2 = 1 << _1; _3 = ~_2; tmp_9 = _3 & tmp_12;
Referenced by analyze_and_compute_bitwise_induction_effect().
◆ hash_idx_scev_info()
Computes a hash function for database element ELT.
References instantiate_cache_type::entries, ggc_alloc(), global_cache, and scev_info_hasher::hash().
Referenced by get_instantiated_value_entry().
◆ instantiate_scev()
Analyze all the parameters of the chrec that were left under a symbolic form. INSTANTIATE_BELOW is the basic block that stops the recursive instantiation of parameters: a parameter is a variable that is defined in a basic block that dominates INSTANTIATE_BELOW or a function parameter.
References dump_file, dump_flags, ggc_alloc(), global_cache, instantiate_scev_r(), NULL, print_generic_expr(), and TDF_SCEV.
Referenced by loop_cand::analyze_carried_vars(), compute_access_stride(), dr_analyze_indices(), instantiate_parameters(), tree_loop_interchange::interchange_loops(), and scalar_evolution_in_region().
◆ instantiate_scev_binary()
|
static |
Analyze all the parameters of the chrec, between INSTANTIATE_BELOW and EVOLUTION_LOOP, that were left under a symbolic form. "C0 CODE C1" is a binary expression of type TYPE to be instantiated. CACHE is the cache of already instantiated values. Variable pointed by FOLD_CONVERSIONS is set to TRUE when the conversions that may wrap in signed/pointer type are folded, as long as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL then we don't do such fold. SIZE_EXPR is used for computing the size of the expression to be instantiated, and to stop if it exceeds some limit.
References chrec_convert(), chrec_convert_rhs(), chrec_dont_know, chrec_fold_minus(), chrec_fold_multiply(), chrec_fold_plus(), fold_build2, gcc_unreachable, ggc_alloc(), instantiate_scev_r(), and NULL.
Referenced by instantiate_scev_r().
◆ instantiate_scev_convert()
|
static |
Analyze all the parameters of the chrec, between INSTANTIATE_BELOW and EVOLUTION_LOOP, that were left under a symbolic form. "CHREC" that stands for a convert expression "(TYPE) OP" is to be instantiated. CACHE is the cache of already instantiated values. Variable pointed by FOLD_CONVERSIONS is set to TRUE when the conversions that may wrap in signed/pointer type are folded, as long as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL then we don't do such fold. SIZE_EXPR is used for computing the size of the expression to be instantiated, and to stop if it exceeds some limit.
References chrec_convert(), chrec_convert_aggressive(), chrec_dont_know, fold_convert, ggc_alloc(), instantiate_scev_r(), and NULL.
Referenced by instantiate_scev_r().
◆ instantiate_scev_name()
|
static |
Analyze all the parameters of the chrec, between INSTANTIATE_BELOW and EVOLUTION_LOOP, that were left under a symbolic form. CHREC is an SSA_NAME to be instantiated. CACHE is the cache of already instantiated values. Variable pointed by FOLD_CONVERSIONS is set to TRUE when the conversions that may wrap in signed/pointer type are folded, as long as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL then we don't do such fold. SIZE_EXPR is used for computing the size of the expression to be instantiated, and to stop if it exceeds some limit.
References analyze_scalar_evolution(), CDI_DOMINATORS, chrec_dont_know, chrec_not_analyzed_yet, compute_overall_effect_of_inner_loop(), dominated_by_p(), find_common_loop(), flow_loop_nested_p(), fold_build1, fold_build2, instantiate_cache_type::get(), get_instantiated_value_entry(), ggc_alloc(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_class(), gimple_assign_rhs_code(), gimple_bb(), GIMPLE_BINARY_RHS, GIMPLE_UNARY_RHS, global_cache, instantiate_scev_r(), loop_closed_phi_def(), loop_containing_stmt(), loop_depth(), NULL_TREE, instantiate_cache_type::set(), si, SSA_NAME_DEF_STMT, SSA_NAME_IS_DEFAULT_DEF, TREE_CODE, and TREE_TYPE.
Referenced by instantiate_scev_r().
◆ instantiate_scev_not()
|
static |
Analyze all the parameters of the chrec, between INSTANTIATE_BELOW and EVOLUTION_LOOP, that were left under a symbolic form. CHREC is a BIT_NOT_EXPR or a NEGATE_EXPR expression to be instantiated. Handle ~X as -1 - X. Handle -X as -1 * X. CACHE is the cache of already instantiated values. Variable pointed by FOLD_CONVERSIONS is set to TRUE when the conversions that may wrap in signed/pointer type are folded, as long as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL then we don't do such fold. SIZE_EXPR is used for computing the size of the expression to be instantiated, and to stop if it exceeds some limit.
References chrec_convert(), chrec_dont_know, chrec_fold_minus(), chrec_fold_multiply(), fold_build1, fold_convert, gcc_unreachable, ggc_alloc(), instantiate_scev_r(), integer_minus_one_node, and NULL.
Referenced by instantiate_scev_r().
◆ instantiate_scev_poly()
|
static |
Analyze all the parameters of the chrec, between INSTANTIATE_BELOW and EVOLUTION_LOOP, that were left under a symbolic form. CHREC is a polynomial chain of recurrence to be instantiated. CACHE is the cache of already instantiated values. Variable pointed by FOLD_CONVERSIONS is set to TRUE when the conversions that may wrap in signed/pointer type are folded, as long as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL then we don't do such fold. SIZE_EXPR is used for computing the size of the expression to be instantiated, and to stop if it exceeds some limit.
References build_polynomial_chrec(), chrec_convert_rhs(), chrec_dont_know, CHREC_LEFT, CHREC_RIGHT, chrec_type(), CHREC_VARIABLE, get_chrec_loop(), ggc_alloc(), instantiate_scev_r(), and NULL.
Referenced by instantiate_scev_r().
◆ instantiate_scev_r()
|
static |
Analyze all the parameters of the chrec, between INSTANTIATE_BELOW and EVOLUTION_LOOP, that were left under a symbolic form. CHREC is the scalar evolution to instantiate. CACHE is the cache of already instantiated values. Variable pointed by FOLD_CONVERSIONS is set to TRUE when the conversions that may wrap in signed/pointer type are folded, as long as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL then we don't do such fold. SIZE_EXPR is used for computing the size of the expression to be instantiated, and to stop if it exceeds some limit.
References automatically_generated_chrec_p(), CASE_CONVERT, chrec_dont_know, chrec_known, chrec_type(), CONSTANT_CLASS_P, ggc_alloc(), instantiate_scev_binary(), instantiate_scev_convert(), instantiate_scev_name(), instantiate_scev_not(), instantiate_scev_poly(), is_gimple_min_invariant(), NULL_TREE, TREE_CODE, TREE_OPERAND, and TREE_TYPE.
Referenced by instantiate_scev(), instantiate_scev_binary(), instantiate_scev_convert(), instantiate_scev_name(), instantiate_scev_not(), instantiate_scev_poly(), and resolve_mixers().
◆ interpret_condition_phi()
This function merges the branches of a condition-phi-node, contained in the outermost loop, and whose arguments are already analyzed.
References analyze_scalar_evolution(), backedge_phi_arg_p(), chrec_dont_know, chrec_merge(), chrec_not_analyzed_yet, ggc_alloc(), gimple_phi_num_args(), i, and PHI_ARG_DEF.
Referenced by analyze_scalar_evolution_1().
◆ interpret_expr()
Interpret the expression EXPR.
References automatically_generated_chrec_p(), chrec_dont_know, expr, extract_ops_from_tree(), get_gimple_rhs_class(), ggc_alloc(), GIMPLE_TERNARY_RHS, interpret_rhs_expr(), TREE_CODE, and TREE_TYPE.
Referenced by analyze_scalar_evolution_1().
◆ interpret_gimple_assign()
Interpret the rhs of the assignment STMT.
References gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), interpret_rhs_expr(), and TREE_TYPE.
Referenced by analyze_scalar_evolution_1().
◆ interpret_loop_phi()
Analyze the scalar evolution for LOOP_PHI_NODE.
References analyze_evolution_in_loop(), analyze_initial_condition(), gcc_assert, ggc_alloc(), and loop_containing_stmt().
Referenced by analyze_scalar_evolution_1().
◆ interpret_rhs_expr()
|
static |
Interpret the operation RHS1 OP RHS2. If we didn't analyze this node before, follow the definitions until ending either on an analyzed GIMPLE_ASSIGN, or on a loop-phi-node. On the return path, this function propagates evolutions (ala constant copy propagation). OPND1 is not a GIMPLE expression because we could analyze the effect of an inner loop: see interpret_loop_phi.
References analyze_scalar_evolution(), analyze_scalar_evolution_for_address_of(), build_int_cst(), build_nonstandard_integer_type(), CASE_CONVERT, CDI_DOMINATORS, chrec_convert(), chrec_dont_know, chrec_fold_minus(), chrec_fold_multiply(), chrec_fold_plus(), dominated_by_p(), exact_log2(), fold_build2, fold_convert, get_gimple_rhs_class(), get_inner_reference(), ggc_alloc(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), gimple_bb(), GIMPLE_SINGLE_RHS, handled_component_p(), instantiate_parameters(), integer_minus_one_node, INTEGRAL_TYPE_P, interpret_rhs_expr(), is_gimple_assign(), is_gimple_min_invariant(), loop::latch, NULL_TREE, offset, size_int, SSA_NAME_DEF_STMT, tcc_binary, TREE_CODE, TREE_CODE_CLASS, tree_fits_uhwi_p(), TREE_OPERAND, tree_to_uhwi(), TREE_TYPE, type(), TYPE_OVERFLOW_UNDEFINED, TYPE_OVERFLOW_WRAPS, TYPE_PRECISION, and unsigned_type_for().
Referenced by interpret_expr(), interpret_gimple_assign(), and interpret_rhs_expr().
◆ iv_can_overflow_p()
Return true if the IV calculation in TYPE can overflow based on the knowledge of the upper bound on the number of iterations of LOOP, the BASE and STEP of IV. We do not use information whether TYPE can overflow so it is safe to use this test even for derived IVs not computed every iteration or hypotetical IVs to be inserted into code.
References wi::add(), cfun, wide_int_storage::from(), gcc_checking_assert, wi::ge_p(), get_max_loop_iterations(), get_range_query(), ggc_alloc(), wi::gtu_p(), integer_zerop(), INTEGRAL_TYPE_P, wi::le_p(), wi::max_value(), wi::min_precision(), wi::min_value(), wi::mul(), wi::neg(), wi::neg_p(), wi::OVF_NONE, r, SIGNED, TREE_TYPE, TYPE_PRECISION, TYPE_SIGN, and UNSIGNED.
Referenced by alloc_iv(), and simple_iv_with_niters().
◆ loop_closed_phi_def()
Return the closed_loop_phi node for VAR. If there is none, return NULL_TREE.
References gsi_end_p(), gsi_next(), gsi_start_phis(), loop_containing_stmt(), NULL_TREE, gphi_iterator::phi(), PHI_ARG_DEF_FROM_EDGE, PHI_RESULT, single_exit(), SSA_NAME_DEF_STMT, and TREE_CODE.
Referenced by instantiate_scev_name().
◆ loop_phi_node_p()
Return true when PHI is a loop-phi-node.
References gimple_bb(), loop::header, and loop_containing_stmt().
Referenced by analyze_scalar_evolution_1(), and scev_dfs::follow_ssa_edge_expr().
◆ new_scev_info_str()
|
inlinestatic |
Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW.
References scev_info_str::chrec, chrec_not_analyzed_yet, ggc_alloc(), scev_info_str::instantiated_below, scev_info_str::name_version, and SSA_NAME_VERSION.
Referenced by find_var_scev_info().
◆ nonwrapping_chrec_p()
Return true if CHREC's nonwrapping flag is set.
References CHREC_NOWRAP, ggc_alloc(), and TREE_CODE.
Referenced by scev_probably_wraps_p().
◆ number_of_latch_executions()
Entry point for the analysis of the number of iterations pass.
This function tries to safely approximate the number of iterations
the loop will run. When this property is not decidable at compile
time, the result is chrec_dont_know. Otherwise the result is a
scalar or a symbolic parameter. When the number of iterations may
be equal to zero and the property cannot be determined at compile
time, the result is a COND_EXPR that represents in a symbolic form
the conditions under which the number of iterations is not zero.
Example of analysis: suppose that the loop has an exit condition:
"if (b > 49) goto end_loop;"
and that in a previous analysis we have determined that the
variable 'b' has an evolution function:
"EF = {23, +, 5}_2".
When we evaluate the function at the point 5, i.e. the value of the
variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
and EF (6) = 53. In this case the value of 'b' on exit is '53' and
the loop body has been executed 6 times.
References build_int_cst(), chrec_dont_know, COMPARISON_CLASS_P, dump_file, dump_flags, fold_build3, ggc_alloc(), integer_nonzerop(), integer_zerop(), tree_niter_desc::may_be_zero, loop::nb_iterations, niter_desc::niter, NULL_TREE, number_of_iterations_exit(), print_generic_expr(), single_exit(), TDF_SCEV, and TREE_TYPE.
Referenced by chrec_is_positive(), compute_access_range(), compute_alias_check_pairs(), compute_overall_effect_of_inner_loop(), estimate_numbers_of_iterations(), loop_distribution::execute(), final_value_replacement_loop(), tree_loop_interchange::interchange_loops(), is_inv_store_elimination_chain(), pcom_worker::prepare_finalizers_chain(), prepare_perfect_loop_nest(), and pcom_worker::split_data_refs_to_components().
◆ record_nonwrapping_chrec()
If CHREC doesn't overflow, set the nonwrapping flag.
References CHREC_NOWRAP, dump_file, dump_flags, ggc_alloc(), print_generic_expr(), and TDF_SCEV.
Referenced by idx_infer_loop_bounds(), infer_loop_bounds_from_pointer_arith(), and infer_loop_bounds_from_signedness().
◆ reset_chrecs_counters()
|
inlinestatic |
Reset the counters.
Referenced by gather_stats_on_scev_database().
◆ resolve_mixers()
Similar to instantiate_parameters, but does not introduce the evolutions in outer loops for LOOP invariants in CHREC, and does not care about causing overflows, as long as they do not affect value of an expression.
References ggc_alloc(), global_cache, instantiate_scev_r(), loop_preheader_edge(), and NULL.
Referenced by analyze_scalar_evolution_in_loop().
◆ scev_finalize()
Finalize the scalar evolution analysis.
References cfun, free_numbers_of_iterations_estimates(), NULL, and scalar_evolution_info.
Referenced by analyze_function_body(), debug_seed_ranger(), execute_ranger_vrp(), finite_function_p(), perform_tree_ssa_dce(), report_predictor_hitrates(), and tree_ssa_loop_done().
◆ scev_initialize()
Initialize the analysis of scalar evolutions for LOOPS.
References cfun, hash_table< Descriptor, Lazy, Allocator >::create_ggc(), gcc_assert, LOOPS_NORMAL, loops_state_satisfies_p(), loop::nb_iterations, NULL_TREE, scalar_evolution_info, and scev_initialized_p().
Referenced by analyze_function_body(), debug_seed_ranger(), execute_ranger_vrp(), finite_function_p(), perform_tree_ssa_dce(), and report_predictor_hitrates().
◆ scev_initialized_p()
Return true if SCEV is initialized.
References NULL, and scalar_evolution_info.
Referenced by cleanup_tree_cfg_noloop(), debug_seed_ranger(), estimated_loop_iterations(), fini_copy_prop(), fix_loop_structure(), likely_max_loop_iterations(), max_loop_iterations(), perform_tree_ssa_dce(), fold_using_range::range_of_phi(), scev_initialize(), tree_loop_unroll_and_jam(), and tree_ssa_split_loops().
◆ scev_reset()
Cleans up the information cached by the scalar evolutions analysis in the hash table and in the loop->nb_iterations.
References cfun, loop::nb_iterations, NULL_TREE, and scev_reset_htab().
Referenced by canonicalize_induction_variables(), loop_distribution::execute(), execute_ranger_vrp(), fini_copy_prop(), gen_parallel_loop(), gimple_duplicate_loop_body_to_header_edge(), perform_tree_ssa_dce(), remove_unreachable::remove_and_update_globals(), repair_loop_structures(), tree_loop_unroll_and_jam(), tree_predictive_commoning(), tree_ssa_prefetch_arrays(), tree_unroll_loops_completely(), and vect_do_peeling().
◆ scev_reset_htab()
Cleans up the information cached by the scalar evolutions analysis in the hash table.
References scalar_evolution_info.
Referenced by fix_loop_structure(), flush_ssaname_freelist(), tree_loop_interchange::interchange_loops(), scev_reset(), tree_ssa_iv_optimize(), vect_analyze_loop(), and vect_free_loop_info_assumptions().
◆ set_scalar_evolution()
|
static |
Associate CHREC to SCALAR.
References dump_file, dump_flags, find_var_scev_info(), ggc_alloc(), basic_block_def::index, nb_set_scev, print_generic_expr(), TDF_SCEV, TDF_STATS, and TREE_CODE.
Referenced by analyze_scalar_evolution_1().
◆ simple_iv()
| bool simple_iv | ( | class loop * | wrto_loop, |
| class loop * | use_loop, | ||
| tree | op, | ||
| affine_iv * | iv, | ||
| bool | allow_nonconstant_step ) |
Like simple_iv_with_niters, but return TRUE when OP behaves as a simple affine iv unconditionally.
References ggc_alloc(), NULL, and simple_iv_with_niters().
Referenced by analyze_function_body(), dr_analyze_innermost(), eliminate_dom_walker::eliminate_stmt(), find_bivs(), find_givs_in_stmt_scev(), gather_scalar_reductions(), get_cst_init_from_scev(), idx_analyze_ref(), is_comparison_with_loop_invariant_p(), rewrite_phi_with_iv(), split_at_bb_p(), loop_distribution::transform_reduction_loop(), try_create_reduction_list(), unroll_jam_possible_p(), and vectorizable_simd_clone_call().
◆ simple_iv_with_niters()
| bool simple_iv_with_niters | ( | class loop * | wrto_loop, |
| class loop * | use_loop, | ||
| tree | op, | ||
| affine_iv * | iv, | ||
| tree * | iv_niters, | ||
| bool | allow_nonconstant_step ) |
Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
respect to WRTO_LOOP and returns its base and step in IV if possible
(see analyze_scalar_evolution_in_loop for more details on USE_LOOP
and WRTO_LOOP). If ALLOW_NONCONSTANT_STEP is true, we want step to be
invariant in LOOP. Otherwise we require it to be an integer constant.
IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
because it is computed in signed arithmetics). Consequently, adding an
induction variable
for (i = IV->base; ; i += IV->step)
is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
false for the type of the induction variable, or you can prove that i does
not wrap by some other argument. Otherwise, this might introduce undefined
behavior, and
i = iv->base;
for (; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
must be used instead.
When IV_NITERS is not NULL, this function also checks case in which OP
is a conversion of an inner simple iv of below form:
(outer_type){inner_base, inner_step}_loop.
If type of inner iv has smaller precision than outer_type, it can't be
folded into {(outer_type)inner_base, (outer_type)inner_step}_loop because
the inner iv could overflow/wrap. In this case, we derive a condition
under which the inner iv won't overflow/wrap and do the simplification.
The derived condition normally is the maximum number the inner iv can
iterate, and will be stored in IV_NITERS. This is useful in loop niter
analysis, to derive break conditions when a loop must terminate, when is
infinite.
References analyze_scalar_evolution_in_loop(), iv::base, boolean_type_node, build_int_cst(), chrec_contains_symbols_defined_in_loop(), chrec_contains_undetermined(), CHREC_LEFT, CHREC_RIGHT, CHREC_VARIABLE, CONVERT_EXPR_P, derive_simple_iv_with_niters(), fold_build2, fold_convert, ggc_alloc(), integer_zerop(), INTEGRAL_TYPE_P, iv_can_overflow_p(), wi::max_value(), wi::min_value(), iv::no_overflow, nowrap_type_p(), NULL, NULL_TREE, wi::OVF_NONE, POINTER_TYPE_P, simplify_using_initial_conditions(), iv::step, wi::sub(), wi::to_wide(), TREE_CODE, tree_contains_chrecs(), tree_does_not_contain_chrecs(), tree_int_cst_equal(), tree_int_cst_sign_bit(), tree_nop_conversion_p(), TREE_OPERAND, TREE_TYPE, type(), TYPE_SIGN, useless_type_conversion_p(), and wide_int_to_tree().
Referenced by number_of_iterations_exit_assumptions(), and simple_iv().
◆ simplify_peeled_chrec()
Simplify PEELED_CHREC represented by (init_cond, arg) in LOOP.
Handle below case and return the corresponding POLYNOMIAL_CHREC:
# i_17 = PHI <i_13(5), 0(3)>
# _20 = PHI <_5(5), start_4(D)(3)>
...
i_13 = i_17 + 1;
_5 = start_4(D) + i_13;
Though variable _20 appears as a PEELED_CHREC in the form of
(start_4, _5)_LOOP, it's a POLYNOMIAL_CHREC like {start_4, 1}_LOOP.
See PR41488.
References aff_combination_add(), aff_combination_scale(), aff_combination_zero_p(), analyze_scalar_evolution(), build_polynomial_chrec(), chrec_dont_know, chrec_fold_plus(), CHREC_LEFT, CHREC_RIGHT, dump_file, dump_flags, free_affine_expand_cache(), ggc_alloc(), instantiate_parameters(), INTEGRAL_TYPE_P, NULL, NULL_TREE, loop::num, operand_equal_p(), POINTER_TYPE_P, TDF_SCEV, TREE_CODE, tree_to_aff_combination_expand(), TREE_TYPE, and type().
Referenced by analyze_evolution_in_loop().
Variable Documentation
◆ global_cache
|
static |
Cache to avoid infinite recursion when instantiating an SSA name. Live during the outermost analyze_scalar_evolution, instantiate_scev or resolve_mixers call.
Referenced by analyze_scalar_evolution(), eq_idx_scev_info(), hash_idx_scev_info(), instantiate_scev(), instantiate_scev_name(), and resolve_mixers().
◆ nb_get_scev
|
static |
Referenced by dump_chrecs_stats(), and get_scalar_evolution().
◆ nb_set_scev
|
static |
Counters for the scev database.
Referenced by dump_chrecs_stats(), and set_scalar_evolution().
◆ scalar_evolution_info
|
static |
