GCC Middle and Back End API Reference
tree-scalar-evolution.cc File Reference
#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"
Include dependency graph for tree-scalar-evolution.cc:

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 }
 

Functions

static tree analyze_scalar_evolution_1 (class loop *, tree)
 
static tree analyze_scalar_evolution_for_address_of (class loop *loop, tree var)
 
static struct scev_info_strnew_scev_info_str (basic_block instantiated_below, tree var)
 
static treefind_var_scev_info (basic_block instantiated_below, tree var)
 
static bool loop_phi_node_p (gimple *phi)
 
tree compute_overall_effect_of_inner_loop (class loop *loop, tree evolution_fn)
 
static void set_scalar_evolution (basic_block instantiated_below, tree scalar, tree chrec)
 
static tree get_scalar_evolution (basic_block instantiated_below, tree scalar)
 
static bool backedge_phi_arg_p (gphi *phi, int i)
 
gcondget_loop_exit_condition (const class loop *loop)
 
gcondget_loop_exit_condition (const_edge exit_edge)
 
static tree simplify_peeled_chrec (class loop *loop, tree arg, tree init_cond)
 
static tree analyze_evolution_in_loop (gphi *loop_phi_node, tree init_cond)
 
static tree follow_copies_to_constant (tree var)
 
static tree analyze_initial_condition (gphi *loop_phi_node)
 
static tree interpret_loop_phi (class loop *loop, gphi *loop_phi_node)
 
static tree interpret_condition_phi (class loop *loop, gphi *condition_phi)
 
static tree interpret_rhs_expr (class loop *loop, gimple *at_stmt, tree type, tree rhs1, enum tree_code code, tree rhs2)
 
static tree interpret_expr (class loop *loop, gimple *at_stmt, tree expr)
 
static tree interpret_gimple_assign (class loop *loop, gimple *stmt)
 
tree analyze_scalar_evolution (class loop *loop, tree var)
 
void record_nonwrapping_chrec (tree chrec)
 
bool nonwrapping_chrec_p (tree chrec)
 
static tree analyze_scalar_evolution_in_loop (class loop *wrto_loop, class loop *use_loop, tree version, bool *folded_casts)
 
static hashval_t hash_idx_scev_info (const void *elt_)
 
static int eq_idx_scev_info (const void *e1, const void *e2)
 
static unsigned get_instantiated_value_entry (instantiate_cache_type &cache, tree name, edge instantiate_below)
 
static tree loop_closed_phi_def (tree var)
 
static tree instantiate_scev_r (edge, class loop *, class loop *, tree, bool *, int)
 
static tree instantiate_scev_name (edge instantiate_below, class loop *evolution_loop, class loop *inner_loop, tree chrec, bool *fold_conversions, int size_expr)
 
static tree instantiate_scev_poly (edge instantiate_below, class loop *evolution_loop, class loop *, tree chrec, bool *fold_conversions, int size_expr)
 
static tree instantiate_scev_binary (edge instantiate_below, class loop *evolution_loop, class loop *inner_loop, tree chrec, enum tree_code code, tree type, tree c0, tree c1, bool *fold_conversions, int size_expr)
 
static tree instantiate_scev_convert (edge instantiate_below, class loop *evolution_loop, class loop *inner_loop, tree chrec, tree type, tree op, bool *fold_conversions, int size_expr)
 
static tree instantiate_scev_not (edge instantiate_below, class loop *evolution_loop, class loop *inner_loop, tree chrec, enum tree_code code, tree type, tree op, bool *fold_conversions, int size_expr)
 
tree instantiate_scev (edge instantiate_below, class loop *evolution_loop, tree chrec)
 
tree resolve_mixers (class loop *loop, tree chrec, bool *folded_casts)
 
tree number_of_latch_executions (class loop *loop)
 
static void reset_chrecs_counters (struct chrec_stats *stats)
 
static void dump_chrecs_stats (FILE *file, struct chrec_stats *stats)
 
static void gather_chrec_stats (tree chrec, struct chrec_stats *stats)
 
void gather_stats_on_scev_database (void)
 
void scev_initialize (void)
 
bool scev_initialized_p (void)
 
void scev_reset_htab (void)
 
void scev_reset (void)
 
bool iv_can_overflow_p (class loop *loop, tree type, tree base, tree step)
 
static tree derive_simple_iv_with_niters (tree ev, tree *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)
 
bool simple_iv (class loop *wrto_loop, class loop *use_loop, tree op, affine_iv *iv, bool allow_nonconstant_step)
 
void scev_finalize (void)
 
static bool expression_expensive_p (tree expr, bool *cond_overflow_p, hash_map< tree, uint64_t > &cache, uint64_t &cost)
 
bool expression_expensive_p (tree expr, bool *cond_overflow_p)
 
bool gimple_bitwise_induction_p (tree, tree *, tree(*)(tree))
 
static tree analyze_and_compute_bitwise_induction_effect (class loop *loop, tree phidef, unsigned HOST_WIDE_INT niter)
 
bool gimple_bitop_with_inv_p (tree, tree *, tree(*)(tree))
 
static tree analyze_and_compute_bitop_with_inv_effect (class loop *loop, tree phidef, tree niter)
 
bool final_value_replacement_loop (class loop *loop)
 

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_typeglobal_cache
 

Enumeration Type Documentation

◆ t_bool

Depth first search algorithm.   
Enumerator
t_false 
t_true 
t_dont_know 

Function Documentation

◆ analyze_and_compute_bitop_with_inv_effect()

◆ analyze_and_compute_bitwise_induction_effect()

◆ analyze_evolution_in_loop()

static tree analyze_evolution_in_loop ( gphi * loop_phi_node,
tree init_cond )
static

◆ analyze_initial_condition()

static tree analyze_initial_condition ( gphi * loop_phi_node)
static
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()

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

static tree analyze_scalar_evolution_1 ( class loop * loop,
tree var )
static
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()

static tree analyze_scalar_evolution_for_address_of ( class loop * loop,
tree var )
static
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 tree analyze_scalar_evolution_in_loop ( class loop * wrto_loop,
class loop * use_loop,
tree version,
bool * folded_casts )
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()

static bool backedge_phi_arg_p ( gphi * phi,
int i )
static
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()

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

static tree derive_simple_iv_with_niters ( tree ev,
tree * niters )
static
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 void dump_chrecs_stats ( FILE * file,
struct chrec_stats * 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()

static int eq_idx_scev_info ( const void * e1,
const void * e2 )
inlinestatic
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]

bool expression_expensive_p ( tree expr,
bool * cond_overflow_p )

◆ expression_expensive_p() [2/2]

static bool expression_expensive_p ( tree expr,
bool * cond_overflow_p,
hash_map< tree, uint64_t > & cache,
uint64_t & cost )
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, 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()

◆ find_var_scev_info()

static tree * find_var_scev_info ( basic_block instantiated_below,
tree var )
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()

static tree follow_copies_to_constant ( tree var)
static
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()

◆ gather_stats_on_scev_database()

void gather_stats_on_scev_database ( void )

◆ get_instantiated_value_entry()

static unsigned get_instantiated_value_entry ( instantiate_cache_type & cache,
tree name,
edge instantiate_below )
static

◆ get_loop_exit_condition() [1/2]

gcond * get_loop_exit_condition ( const class loop * loop)
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 tree get_scalar_evolution ( basic_block instantiated_below,
tree scalar )
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()

bool gimple_bitop_with_inv_p ( tree ,
tree * ,
tree(*)(tree)  )
extern
Match.pd function to match bitop with invariant expression
.i.e.
tmp_7 = _0 & _1;  

◆ gimple_bitwise_induction_p()

bool gimple_bitwise_induction_p ( tree ,
tree * ,
tree(*)(tree)  )
extern
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()

static hashval_t hash_idx_scev_info ( const void * elt_)
inlinestatic
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()

tree instantiate_scev ( edge instantiate_below,
class loop * evolution_loop,
tree chrec )
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 tree instantiate_scev_binary ( edge instantiate_below,
class loop * evolution_loop,
class loop * inner_loop,
tree chrec,
enum tree_code code,
tree type,
tree c0,
tree c1,
bool * fold_conversions,
int size_expr )
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 tree instantiate_scev_convert ( edge instantiate_below,
class loop * evolution_loop,
class loop * inner_loop,
tree chrec,
tree type,
tree op,
bool * fold_conversions,
int size_expr )
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 tree instantiate_scev_name ( edge instantiate_below,
class loop * evolution_loop,
class loop * inner_loop,
tree chrec,
bool * fold_conversions,
int size_expr )
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 tree instantiate_scev_not ( edge instantiate_below,
class loop * evolution_loop,
class loop * inner_loop,
tree chrec,
enum tree_code code,
tree type,
tree op,
bool * fold_conversions,
int size_expr )
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 tree instantiate_scev_poly ( edge instantiate_below,
class loop * evolution_loop,
class loop * ,
tree chrec,
bool * fold_conversions,
int size_expr )
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 tree instantiate_scev_r ( edge instantiate_below,
class loop * evolution_loop,
class loop * inner_loop,
tree chrec,
bool * fold_conversions,
int size_expr )
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()

static tree interpret_condition_phi ( class loop * loop,
gphi * condition_phi )
static
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_gimple_assign()

static tree interpret_gimple_assign ( class loop * loop,
gimple * stmt )
static

◆ interpret_loop_phi()

static tree interpret_loop_phi ( class loop * loop,
gphi * loop_phi_node )
static
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()

◆ iv_can_overflow_p()

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

static tree loop_closed_phi_def ( tree var)
static
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()

static bool loop_phi_node_p ( gimple * phi)
static
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()

static struct scev_info_str * new_scev_info_str ( basic_block instantiated_below,
tree var )
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()

bool nonwrapping_chrec_p ( tree chrec)
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()

tree number_of_latch_executions ( class loop * loop)
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()

void record_nonwrapping_chrec ( tree chrec)

◆ reset_chrecs_counters()

static void reset_chrecs_counters ( struct chrec_stats * stats)
inlinestatic
Reset the counters.   

Referenced by gather_stats_on_scev_database().

◆ resolve_mixers()

tree resolve_mixers ( class loop * loop,
tree chrec,
bool * folded_casts )
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()

◆ scev_initialize()

◆ scev_initialized_p()

◆ scev_reset()

◆ scev_reset_htab()

void scev_reset_htab ( void )
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 void set_scalar_evolution ( basic_block instantiated_below,
tree scalar,
tree chrec )
static

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

static tree simplify_peeled_chrec ( class loop * loop,
tree arg,
tree init_cond )
static
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

instantiate_cache_type* 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

unsigned nb_get_scev = 0
static

◆ nb_set_scev

unsigned nb_set_scev = 0
static
Counters for the scev database.   

Referenced by dump_chrecs_stats(), and set_scalar_evolution().

◆ scalar_evolution_info