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

Go to the source code of this file.

Functions

tree number_of_latch_executions (class loop *)
 
gcondget_loop_exit_condition (const class loop *)
 
gcondget_loop_exit_condition (const_edge)
 
void scev_initialize (void)
 
bool scev_initialized_p (void)
 
void scev_reset (void)
 
void scev_reset_htab (void)
 
void scev_finalize (void)
 
tree analyze_scalar_evolution (class loop *, tree)
 
tree instantiate_scev (edge, class loop *, tree)
 
tree resolve_mixers (class loop *, tree, bool *)
 
void gather_stats_on_scev_database (void)
 
bool final_value_replacement_loop (class loop *)
 
unsigned int scev_const_prop (void)
 
bool expression_expensive_p (tree, bool *)
 
bool simple_iv_with_niters (class loop *, class loop *, tree, struct affine_iv *, tree *, bool)
 
bool simple_iv (class loop *, class loop *, tree, struct affine_iv *, bool)
 
bool iv_can_overflow_p (class loop *, tree, tree, tree)
 
tree compute_overall_effect_of_inner_loop (class loop *, tree)
 
void record_nonwrapping_chrec (tree)
 
bool nonwrapping_chrec_p (tree)
 
basic_block block_before_loop (loop_p loop)
 
tree instantiate_parameters (class loop *loop, tree chrec)
 
class loopget_chrec_loop (const_tree chrec)
 

Function Documentation

◆ analyze_scalar_evolution()

tree analyze_scalar_evolution ( class loop * loop,
tree var )
extern
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(), 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().

◆ block_before_loop()

basic_block block_before_loop ( loop_p loop)
inline
Returns the basic block preceding LOOP, or the CFG entry block when
the loop is function's body.   

References cfun, ENTRY_BLOCK_PTR_FOR_FN, and loop_preheader_edge().

Referenced by analyze_scalar_evolution(), and analyze_scalar_evolution_1().

◆ compute_overall_effect_of_inner_loop()

tree compute_overall_effect_of_inner_loop ( class loop * loop,
tree evolution_fn )
extern
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(), 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().

◆ expression_expensive_p()

bool expression_expensive_p ( tree expr,
bool * cond_overflow_p )
extern

References cache, and expression_expensive_p().

◆ final_value_replacement_loop()

◆ gather_stats_on_scev_database()

void gather_stats_on_scev_database ( void )
extern

◆ get_chrec_loop()

◆ get_loop_exit_condition() [1/2]

gcond * get_loop_exit_condition ( const class loop * loop)
extern
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)
extern
If the statement just before the EXIT_EDGE contains a condition then
return the condition, otherwise NULL.  

References dump_file, dump_flags, gsi_last_bb(), NULL, print_gimple_stmt(), safe_dyn_cast(), and TDF_SCEV.

◆ instantiate_parameters()

tree instantiate_parameters ( class loop * loop,
tree chrec )
inline

◆ instantiate_scev()

tree instantiate_scev ( edge instantiate_below,
class loop * evolution_loop,
tree chrec )
extern
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, global_cache, instantiate_scev_r(), NULL, loop::num, 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().

◆ iv_can_overflow_p()

bool iv_can_overflow_p ( class loop * loop,
tree type,
tree base,
tree step )
extern
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(), 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().

◆ nonwrapping_chrec_p()

bool nonwrapping_chrec_p ( tree chrec)
extern
Return true if CHREC's nonwrapping flag is set.   

References CHREC_NOWRAP, and TREE_CODE.

Referenced by scev_probably_wraps_p().

◆ number_of_latch_executions()

tree number_of_latch_executions ( class loop * loop)
extern
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/>.   
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, 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()

void record_nonwrapping_chrec ( tree chrec)
extern

◆ resolve_mixers()

tree resolve_mixers ( class loop * loop,
tree chrec,
bool * folded_casts )
extern
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 global_cache, instantiate_scev_r(), loop_preheader_edge(), and NULL.

Referenced by analyze_scalar_evolution_in_loop().

◆ scev_const_prop()

unsigned int scev_const_prop ( void )
extern

◆ scev_finalize()

◆ scev_initialize()

◆ scev_initialized_p()

◆ scev_reset()

◆ scev_reset_htab()

void scev_reset_htab ( void )
extern
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().

◆ simple_iv()

◆ 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 )
extern
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, integer_zerop(), INTEGRAL_TYPE_P, iv_can_overflow_p(), wi::max_value(), wi::min_value(), iv::no_overflow, nowrap_type_p(), NULL, NULL_TREE, loop::num, 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().