GCC Middle and Back End API Reference
tree-ssa-loop-niter.cc File Reference
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "rtl.h"
#include "tree.h"
#include "gimple.h"
#include "tree-pass.h"
#include "ssa.h"
#include "gimple-pretty-print.h"
#include "diagnostic-core.h"
#include "stor-layout.h"
#include "fold-const.h"
#include "calls.h"
#include "intl.h"
#include "gimplify.h"
#include "gimple-iterator.h"
#include "tree-cfg.h"
#include "tree-ssa-loop-ivopts.h"
#include "tree-ssa-loop-niter.h"
#include "tree-ssa-loop.h"
#include "cfgloop.h"
#include "tree-chrec.h"
#include "tree-scalar-evolution.h"
#include "tree-dfa.h"
#include "internal-fn.h"
#include "gimple-range.h"
#include "sreal.h"
Include dependency graph for tree-ssa-loop-niter.cc:

Data Structures

struct  bounds
 
struct  ilb_data
 

Macros

#define MAX_DOMINATORS_TO_WALK   8
 
#define MAX_ITERATIONS_TO_TRACK    ((unsigned) param_max_iterations_to_track)
 

Functions

static void split_to_var_and_offset (tree expr, tree *var, mpz_t offset)
 
static void refine_value_range_using_guard (tree type, tree var, tree c0, enum tree_code cmp, tree c1, mpz_t below, mpz_t up)
 
static void determine_value_range (class loop *loop, tree type, tree var, mpz_t off, mpz_t min, mpz_t max)
 
static void bound_difference_of_offsetted_base (tree type, mpz_t x, mpz_t y, bounds *bnds)
 
static void refine_bounds_using_guard (tree type, tree varx, mpz_t offx, tree vary, mpz_t offy, tree c0, enum tree_code cmp, tree c1, bounds *bnds)
 
static void bound_difference (class loop *loop, tree x, tree y, bounds *bnds)
 
static void bounds_add (bounds *bnds, const widest_int &delta, tree type)
 
static void bounds_negate (bounds *bnds)
 
static tree inverse (tree x, tree mask)
 
static void number_of_iterations_ne_max (mpz_t bnd, bool no_overflow, tree c, tree s, bounds *bnds, bool exit_must_be_taken)
 
static bool number_of_iterations_ne (class loop *loop, tree type, affine_iv *iv, tree final, class tree_niter_desc *niter, bool exit_must_be_taken, bounds *bnds)
 
static bool number_of_iterations_lt_to_ne (tree type, affine_iv *iv0, affine_iv *iv1, class tree_niter_desc *niter, tree *delta, tree step, bool exit_must_be_taken, bounds *bnds)
 
static bool assert_no_overflow_lt (tree type, affine_iv *iv0, affine_iv *iv1, class tree_niter_desc *niter, tree step)
 
static void assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1, class tree_niter_desc *niter, bounds *bnds)
 
static bool number_of_iterations_until_wrap (class loop *loop, tree type, affine_iv *iv0, affine_iv *iv1, class tree_niter_desc *niter)
 
static bool number_of_iterations_lt (class loop *loop, tree type, affine_iv *iv0, affine_iv *iv1, class tree_niter_desc *niter, bool exit_must_be_taken, bounds *bnds)
 
static bool number_of_iterations_le (class loop *loop, tree type, affine_iv *iv0, affine_iv *iv1, class tree_niter_desc *niter, bool exit_must_be_taken, bounds *bnds)
 
static void dump_affine_iv (FILE *file, affine_iv *iv)
 
static bool number_of_iterations_cond (class loop *loop, tree type, affine_iv *iv0, enum tree_code code, affine_iv *iv1, class tree_niter_desc *niter, bool only_exit, bool every_iteration)
 
static tree build_popcount_expr (tree src)
 
static bool ssa_defined_by_minus_one_stmt_p (tree op, tree val)
 
static bool number_of_iterations_popcount (loop_p loop, edge exit, enum tree_code code, class tree_niter_desc *niter)
 
static tree build_cltz_expr (tree src, bool leading, bool define_at_zero)
 
static bool number_of_iterations_cltz (loop_p loop, edge exit, enum tree_code code, class tree_niter_desc *niter)
 
static bool number_of_iterations_cltz_complement (loop_p loop, edge exit, enum tree_code code, class tree_niter_desc *niter)
 
static bool number_of_iterations_bitcount (loop_p loop, edge exit, enum tree_code code, class tree_niter_desc *niter)
 
tree simplify_replace_tree (tree expr, tree old, tree new_tree, tree(*valueize)(tree, void *), void *context, bool do_fold)
 
static tree expand_simple_operations (tree expr, tree stop, hash_map< tree, tree > &cache)
 
tree expand_simple_operations (tree expr, tree stop)
 
static tree tree_simplify_using_condition_1 (tree cond, tree expr)
 
static tree tree_simplify_using_condition (tree cond, tree expr)
 
tree simplify_using_initial_conditions (class loop *loop, tree expr)
 
static tree simplify_using_outer_evolutions (class loop *loop, tree expr)
 
bool loop_only_exit_p (const class loop *loop, basic_block *body, const_edge exit)
 
bool number_of_iterations_exit_assumptions (class loop *loop, edge exit, class tree_niter_desc *niter, gcond **at_stmt, bool every_iteration, basic_block *body)
 
bool number_of_iterations_exit (class loop *loop, edge exit, class tree_niter_desc *niter, bool warn, bool every_iteration, basic_block *body)
 
tree find_loop_niter (class loop *loop, edge *exit)
 
bool finite_loop_p (class loop *loop)
 
static gphichain_of_csts_start (class loop *loop, tree x)
 
static gphiget_base_for (class loop *loop, tree x)
 
static tree get_val_for (tree x, tree base)
 
tree loop_niter_by_eval (class loop *loop, edge exit)
 
tree find_loop_niter_by_eval (class loop *loop, edge *exit)
 
static widest_int derive_constant_upper_bound_ops (tree, tree, enum tree_code, tree)
 
static widest_int derive_constant_upper_bound_assign (gimple *stmt)
 
static widest_int derive_constant_upper_bound (tree val)
 
static void do_warn_aggressive_loop_optimizations (class loop *loop, widest_int i_bound, gimple *stmt)
 
static void record_estimate (class loop *loop, tree bound, const widest_int &i_bound, gimple *at_stmt, bool is_exit, bool realistic, bool upper)
 
static void record_control_iv (class loop *loop, class tree_niter_desc *niter)
 
static bool get_cst_init_from_scev (tree var, wide_int *init, bool is_min)
 
static void record_nonwrapping_iv (class loop *loop, tree base, tree step, gimple *stmt, tree low, tree high, bool realistic, bool upper)
 
static bool idx_infer_loop_bounds (tree base, tree *idx, void *dta)
 
static void infer_loop_bounds_from_ref (class loop *loop, gimple *stmt, tree ref)
 
static void infer_loop_bounds_from_array (class loop *loop, gimple *stmt)
 
static void infer_loop_bounds_from_pointer_arith (class loop *loop, gimple *stmt)
 
static void infer_loop_bounds_from_signedness (class loop *loop, gimple *stmt)
 
static void infer_loop_bounds_from_undefined (class loop *loop, basic_block *bbs)
 
static int wide_int_cmp (const void *p1, const void *p2)
 
static int bound_index (const vec< bound_wide_int > &bounds, const bound_wide_int &bound)
 
static void discover_iteration_bound_by_body_walk (class loop *loop)
 
static void maybe_lower_iteration_bound (class loop *loop)
 
static tree get_upper_bound_based_on_builtin_expr_with_prob (gcond *cond)
 
void estimate_numbers_of_iterations (class loop *loop)
 
bool estimated_loop_iterations (class loop *loop, widest_int *nit)
 
HOST_WIDE_INT estimated_loop_iterations_int (class loop *loop)
 
bool max_loop_iterations (class loop *loop, widest_int *nit)
 
HOST_WIDE_INT max_loop_iterations_int (class loop *loop)
 
bool likely_max_loop_iterations (class loop *loop, widest_int *nit)
 
HOST_WIDE_INT likely_max_loop_iterations_int (class loop *loop)
 
HOST_WIDE_INT estimated_stmt_executions_int (class loop *loop)
 
bool max_stmt_executions (class loop *loop, widest_int *nit)
 
bool likely_max_stmt_executions (class loop *loop, widest_int *nit)
 
bool estimated_stmt_executions (class loop *loop, widest_int *nit)
 
void estimate_numbers_of_iterations (function *fn)
 
bool stmt_dominates_stmt_p (gimple *s1, gimple *s2)
 
static bool n_of_executions_at_most (gimple *stmt, class nb_iter_bound *niter_bound, tree niter)
 
bool nowrap_type_p (tree type)
 
static bool loop_exits_before_overflow (tree base, tree step, gimple *at_stmt, class loop *loop)
 
static bool scev_var_range_cant_overflow (tree var, tree step, class loop *loop)
 
bool scev_probably_wraps_p (tree var, tree base, tree step, gimple *at_stmt, class loop *loop, bool use_overflow_semantics)
 
void free_numbers_of_iterations_estimates (class loop *loop)
 
void free_numbers_of_iterations_estimates (function *fn)
 
void substitute_in_loop_info (class loop *loop, tree name, tree val)
 

Macro Definition Documentation

◆ MAX_DOMINATORS_TO_WALK

#define MAX_DOMINATORS_TO_WALK   8
Functions to determine/estimate number of iterations of a loop.
   Copyright (C) 2004-2024 Free Software Foundation, Inc.

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the
Free Software Foundation; either version 3, or (at your option) any
later version.

GCC is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3.  If not see
<http://www.gnu.org/licenses/>.   
The maximum number of dominator BBs we search for conditions
of loop header copies we use for simplifying a conditional
expression.   

Referenced by bound_difference(), determine_value_range(), and simplify_using_initial_conditions().

◆ MAX_ITERATIONS_TO_TRACK

#define MAX_ITERATIONS_TO_TRACK    ((unsigned) param_max_iterations_to_track)
Bound on the number of iterations we try to evaluate.   

Referenced by loop_niter_by_eval().

Function Documentation

◆ assert_loop_rolls_lt()

static void assert_loop_rolls_lt ( tree type,
affine_iv * iv0,
affine_iv * iv1,
class tree_niter_desc * niter,
bounds * bnds )
static
Add an assumption to NITER that a loop whose ending condition
is IV0 < IV1 rolls.  TYPE is the type of the control iv.  BNDS
bounds the value of IV1->base - IV0->base.   

References tree_niter_desc::assumptions, bounds::below, boolean_true_node, boolean_type_node, build_int_cst(), fold_build2, fold_convert, ggc_alloc(), integer_nonzerop(), tree_niter_desc::may_be_zero, wi::minus_one(), POINTER_TYPE_P, wi::sext(), sizetype, wi::to_mpz(), wi::to_widest(), type(), TYPE_MAX_VALUE, TYPE_MIN_VALUE, TYPE_PRECISION, UNSIGNED, and bounds::up.

Referenced by number_of_iterations_lt().

◆ assert_no_overflow_lt()

static bool assert_no_overflow_lt ( tree type,
affine_iv * iv0,
affine_iv * iv1,
class tree_niter_desc * niter,
tree step )
static
Add assertions to NITER that ensure that the control variable of the loop
with ending condition IV0 < IV1 does not overflow.  Types of IV0 and IV1
are TYPE.  Returns false if we can prove that there is an overflow, true
otherwise.  STEP is the absolute value of the step.   

References tree_niter_desc::assumptions, boolean_type_node, build_int_cst(), fold_build2, fold_convert, ggc_alloc(), integer_nonzerop(), integer_zerop(), TREE_CODE, TREE_TYPE, TYPE_MAX_VALUE, and TYPE_MIN_VALUE.

Referenced by number_of_iterations_lt().

◆ bound_difference()

static void bound_difference ( class loop * loop,
tree x,
tree y,
bounds * bnds )
static
Stores the bounds on the value of the expression X - Y in LOOP to BNDS.
The subtraction is considered to be performed in arbitrary precision,
without overflows.

We do not attempt to be too clever regarding the value ranges of X and
Y; most of the time, they are just integers or ssa names offsetted by
integer.  However, we try to use the information contained in the
comparisons before the loop (usually created by loop header copying).   

References bounds::below, bound_difference_of_offsetted_base(), CDI_DOMINATORS, cfun, determine_value_range(), end(), ENTRY_BLOCK_PTR_FOR_FN, get_immediate_dominator(), ggc_alloc(), gimple_cond_code(), gimple_cond_lhs(), gimple_cond_rhs(), gsi_last_bb(), loop::header, integer_zerop(), invert_tree_comparison(), MAX_DOMINATORS_TO_WALK, operand_equal_p(), refine_bounds_using_guard(), single_pred_edge(), single_pred_p(), split_to_var_and_offset(), STRIP_SIGN_NOPS, TREE_TYPE, bounds::up, and y.

Referenced by number_of_iterations_cond().

◆ bound_difference_of_offsetted_base()

static void bound_difference_of_offsetted_base ( tree type,
mpz_t x,
mpz_t y,
bounds * bnds )
static
Stores the bounds on the difference of the values of the expressions
(var + X) and (var + Y), computed in TYPE, to BNDS.   

References bounds::below, ggc_alloc(), wi::minus_one(), nowrap_type_p(), wi::to_mpz(), TYPE_PRECISION, UNSIGNED, bounds::up, and y.

Referenced by bound_difference().

◆ bound_index()

static int bound_index ( const vec< bound_wide_int > & bounds,
const bound_wide_int & bound )
static
Return index of BOUND in BOUNDS array sorted in increasing order.
Lookup by binary search.   

References begin(), end(), gcc_unreachable, ggc_alloc(), and wi::ltu_p().

Referenced by discover_iteration_bound_by_body_walk().

◆ bounds_add()

static void bounds_add ( bounds * bnds,
const widest_int & delta,
tree type )
static
Update the bounds in BNDS that restrict the value of X to the bounds
that restrict the value of X + DELTA.  X can be obtained as a
difference of two values in TYPE.   

References bounds::below, ggc_alloc(), wi::minus_one(), SIGNED, wi::to_mpz(), TYPE_PRECISION, UNSIGNED, and bounds::up.

Referenced by number_of_iterations_le(), and number_of_iterations_lt_to_ne().

◆ bounds_negate()

static void bounds_negate ( bounds * bnds)
static
Update the bounds in BNDS that restrict the value of X to the bounds
that restrict the value of -X.   

References bounds::below, ggc_alloc(), and bounds::up.

Referenced by number_of_iterations_ne().

◆ build_cltz_expr()

static tree build_cltz_expr ( tree src,
bool leading,
bool define_at_zero )
static
Return an expression that counts the leading/trailing zeroes of src.

If define_at_zero is true, then the built expression will be defined to
return the precision of src when src == 0 (using either a conditional
expression or a suitable internal function).
Otherwise, we can elide the conditional expression and let src = 0 invoke
undefined behaviour.   

References boolean_type_node, build_call_expr(), build_call_expr_internal_loc(), build_int_cst(), build_zero_cst(), builtin_decl_implicit(), CLZ_DEFINED_VALUE_AT_ZERO, CTZ_DEFINED_VALUE_AT_ZERO, direct_internal_fn_supported_p(), fold_build2, fold_build3, fold_convert, ggc_alloc(), integer_type_node, long_integer_type_node, long_long_integer_type_node, long_long_unsigned_type_node, NULL_TREE, OPTIMIZE_FOR_BOTH, SCALAR_INT_TYPE_MODE, TREE_TYPE, TYPE_PRECISION, UNKNOWN_LOCATION, unshare_expr(), unsigned_type_for(), and unsigned_type_node.

Referenced by number_of_iterations_cltz(), and number_of_iterations_cltz_complement().

◆ build_popcount_expr()

◆ chain_of_csts_start()

static gphi * chain_of_csts_start ( class loop * loop,
tree x )
static
Returns the loop phi node of LOOP such that ssa name X is derived from its
result by a chain of operations such that all but exactly one of their
operands are constants.   

References chain_of_csts_start(), flow_bb_inside_loop_p(), ggc_alloc(), gimple_assign_rhs1(), gimple_assign_rhs_class(), gimple_assign_rhs_code(), gimple_bb(), gimple_references_memory_p(), GIMPLE_TERNARY_RHS, loop::header, is_gimple_min_invariant(), NULL, NULL_TREE, SINGLE_SSA_TREE_OPERAND, SSA_NAME_DEF_STMT, SSA_OP_USE, tcc_reference, and TREE_CODE_CLASS.

Referenced by chain_of_csts_start(), and get_base_for().

◆ derive_constant_upper_bound()

static widest_int derive_constant_upper_bound ( tree val)
static
Returns a constant upper bound on the value of expression VAL.  VAL
is considered to be unsigned.  If its type is signed, its value must
be nonnegative.   

References derive_constant_upper_bound_ops(), extract_ops_from_tree(), and TREE_TYPE.

Referenced by derive_constant_upper_bound_ops(), estimate_numbers_of_iterations(), and record_nonwrapping_iv().

◆ derive_constant_upper_bound_assign()

static widest_int derive_constant_upper_bound_assign ( gimple * stmt)
static
Returns a constant upper bound on the value of the right-hand side of
an assignment statement STMT.   

References derive_constant_upper_bound_ops(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), and TREE_TYPE.

Referenced by derive_constant_upper_bound_ops().

◆ derive_constant_upper_bound_ops()

◆ determine_value_range()

◆ discover_iteration_bound_by_body_walk()

static void discover_iteration_bound_by_body_walk ( class loop * loop)
static
We recorded loop bounds only for statements dominating loop latch (and thus
executed each loop iteration).  If there are any bounds on statements not
dominating the loop latch we can improve the estimate by walking the loop
body and seeing if every path from loop header to loop latch contains
some bounded statement.   

References loop::any_upper_bound, nb_iter_bound::bound, bound_index(), loop::bounds, dump_file, dump_flags, FOR_EACH_EDGE, gcc_assert, ggc_alloc(), gimple_bb(), loop::header, insert(), nb_iter_bound::is_exit, loop_exit_edge_p(), loop_latch_edge(), wi::ltu_p(), loop::nb_iterations_upper_bound, nb_iter_bound::next, print_decu(), queue, record_niter_bound(), SIGNED, nb_iter_bound::stmt, basic_block_def::succs, TDF_DETAILS, vNULL, and wide_int_cmp().

Referenced by estimate_numbers_of_iterations().

◆ do_warn_aggressive_loop_optimizations()

◆ dump_affine_iv()

static void dump_affine_iv ( FILE * file,
affine_iv * iv )
static
Dumps description of affine induction variable IV to FILE.   

References iv::base, dump_file, ggc_alloc(), integer_zerop(), iv::no_overflow, print_generic_expr(), iv::step, and TDF_SLIM.

Referenced by number_of_iterations_cond().

◆ estimate_numbers_of_iterations() [1/2]

◆ estimate_numbers_of_iterations() [2/2]

void estimate_numbers_of_iterations ( function * fn)
Records estimates on numbers of iterations of loops.   

References estimate_numbers_of_iterations(), fold_defer_overflow_warnings(), and fold_undefer_and_ignore_overflow_warnings().

◆ estimated_loop_iterations()

bool estimated_loop_iterations ( class loop * loop,
widest_int * nit )
Sets NIT to the estimated number of executions of the latch of the
LOOP.  If CONSERVATIVE is true, we must be sure that NIT is at least as
large as the number of iterations.  If we have no reliable estimate,
the function returns false, otherwise returns true.   

References estimate_numbers_of_iterations(), get_estimated_loop_iterations(), ggc_alloc(), and scev_initialized_p().

Referenced by estimated_loop_iterations_int(), and estimated_stmt_executions().

◆ estimated_loop_iterations_int()

HOST_WIDE_INT estimated_loop_iterations_int ( class loop * loop)
Similar to estimated_loop_iterations, but returns the estimate only
if it fits to HOST_WIDE_INT.  If this is not the case, or the estimate
on the number of iterations of LOOP could not be derived, returns -1.   

References estimated_loop_iterations(), wi::fits_shwi_p(), and ggc_alloc().

Referenced by estimated_stmt_executions_int(), loop_distribution::execute(), parallelize_loops(), tree_ssa_unswitch_loops(), tree_unswitch_outer_loop(), and try_peel_loop().

◆ estimated_stmt_executions()

bool estimated_stmt_executions ( class loop * loop,
widest_int * nit )
Sets NIT to the estimated number of executions of the latch of the
LOOP, plus one.  If we have no reliable estimate, the function returns
false, otherwise returns true.   

References estimated_loop_iterations(), ggc_alloc(), and wi::gtu_p().

Referenced by predict_loops(), and vect_create_loop_vinfo().

◆ estimated_stmt_executions_int()

HOST_WIDE_INT estimated_stmt_executions_int ( class loop * loop)
Returns an estimate for the number of executions of statements
in the LOOP.  For statements before the loop exit, this exceeds
the number of execution of the latch by one.   

References estimated_loop_iterations_int(), and ggc_alloc().

Referenced by avg_loop_niter(), determine_loop_nest_reuse(), loop_prefetch_arrays(), and vect_analyze_loop_costing().

◆ expand_simple_operations() [1/2]

tree expand_simple_operations ( tree expr,
tree stop = NULL )
Header file for loop interation estimates.
   Copyright (C) 2013-2024 Free Software Foundation, Inc.

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/>.   

References cache, and expand_simple_operations().

◆ expand_simple_operations() [2/2]

◆ find_loop_niter()

tree find_loop_niter ( class loop * loop,
edge * exit )
Try to determine the number of iterations of LOOP.  If we succeed,
expression giving number of iterations is returned and *EXIT is
set to the edge from that the information is obtained.  Otherwise
chrec_dont_know is returned.   

References build_int_cst(), chrec_dont_know, FOR_EACH_VEC_ELT, get_loop_exit_edges(), ggc_alloc(), i, integer_nonzerop(), integer_zerop(), tree_niter_desc::may_be_zero, tree_niter_desc::niter, NULL, NULL_TREE, number_of_iterations_exit(), TREE_CODE, tree_int_cst_lt(), and unsigned_type_node.

Referenced by canonicalize_loop_induction_variables().

◆ find_loop_niter_by_eval()

tree find_loop_niter_by_eval ( class loop * loop,
edge * exit )
Finds the exit of the LOOP by that the loop exits after a constant
number of iterations and stores the exit edge to *EXIT.  The constant
giving the number of iterations of LOOP is returned.  The number of
iterations is determined using loop_niter_by_eval (i.e. by brute force
evaluation).  If we are unable to find the exit for that loop_niter_by_eval
determines the number of iterations, chrec_dont_know is returned.   

References chrec_contains_undetermined(), chrec_dont_know, FOR_EACH_VEC_ELT, get_loop_exit_edges(), ggc_alloc(), i, just_once_each_iteration_p(), loop_niter_by_eval(), tree_niter_desc::niter, NULL, NULL_TREE, and tree_int_cst_lt().

Referenced by canonicalize_loop_induction_variables().

◆ finite_loop_p()

◆ free_numbers_of_iterations_estimates() [1/2]

◆ free_numbers_of_iterations_estimates() [2/2]

void free_numbers_of_iterations_estimates ( function * fn)
Frees the information on upper bounds on numbers of iterations of loops.   

References free_numbers_of_iterations_estimates().

◆ get_base_for()

static gphi * get_base_for ( class loop * loop,
tree x )
static
Determines whether the expression X is derived from a result of a phi node
in header of LOOP such that

* the derivation of X consists only from operations with constants
* the initial value of the phi node is constant
* the value of the phi node in the next iteration can be derived from the
  value in the current iteration by a chain of operations with constants,
  or is also a constant

If such phi node exists, it is returned, otherwise NULL is returned.   

References chain_of_csts_start(), is_gimple_min_invariant(), loop_latch_edge(), loop_preheader_edge(), NULL, PHI_ARG_DEF_FROM_EDGE, and TREE_CODE.

Referenced by loop_niter_by_eval().

◆ get_cst_init_from_scev()

static bool get_cst_init_from_scev ( tree var,
wide_int * init,
bool is_min )
static
This function returns TRUE if below conditions are satisfied:
  1) VAR is SSA variable.
  2) VAR is an IV:{base, step} in its defining loop.
  3) IV doesn't overflow.
  4) Both base and step are integer constants.
  5) Base is the MIN/MAX value depends on IS_MIN.
Store value of base to INIT correspondingly.   

References iv::base, ggc_alloc(), loop_containing_stmt(), iv::no_overflow, NULL, simple_iv(), SSA_NAME_DEF_STMT, iv::step, wi::to_wide(), TREE_CODE, and tree_int_cst_sign_bit().

Referenced by record_nonwrapping_iv().

◆ get_upper_bound_based_on_builtin_expr_with_prob()

static tree get_upper_bound_based_on_builtin_expr_with_prob ( gcond * cond)
static

◆ get_val_for()

static tree get_val_for ( tree x,
tree base )
static
Given an expression X, then

* if X is NULL_TREE, we return the constant BASE.
* if X is a constant, we return the constant X.
* otherwise X is a SSA name, whose value in the considered loop is derived
  by a chain of operations with constant from a result of a phi node in
  the header of the loop.  Then we return value of X when the value of the
  result of this phi node is given by the constant BASE.   

References fold_build1, fold_build2, gcc_checking_assert, gcc_unreachable, get_val_for(), ggc_alloc(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_class(), gimple_assign_rhs_code(), gimple_assign_ssa_name_copy_p(), GIMPLE_BINARY_RHS, GIMPLE_UNARY_RHS, is_gimple_assign(), is_gimple_min_invariant(), SSA_NAME_DEF_STMT, TREE_CODE, and TREE_TYPE.

Referenced by get_val_for(), and loop_niter_by_eval().

◆ idx_infer_loop_bounds()

◆ infer_loop_bounds_from_array()

static void infer_loop_bounds_from_array ( class loop * loop,
gimple * stmt )
static
Determine information about number of iterations of a LOOP from the way
arrays are used in STMT.  RELIABLE is true if STMT is guaranteed to be
executed in every iteration of LOOP.   

References gimple_assign_lhs(), gimple_assign_rhs1(), gimple_call_arg(), gimple_call_lhs(), gimple_call_num_args(), i, infer_loop_bounds_from_ref(), is_gimple_assign(), is_gimple_call(), REFERENCE_CLASS_P, and ilb_data::stmt.

Referenced by infer_loop_bounds_from_undefined().

◆ infer_loop_bounds_from_pointer_arith()

◆ infer_loop_bounds_from_ref()

static void infer_loop_bounds_from_ref ( class loop * loop,
gimple * stmt,
tree ref )
static
Determine information about number of iterations a LOOP from the bounds
of arrays in the data reference REF accessed in STMT.  RELIABLE is true if
STMT is guaranteed to be executed in every iteration of LOOP. 

References for_each_index(), idx_infer_loop_bounds(), ilb_data::loop, and ilb_data::stmt.

Referenced by infer_loop_bounds_from_array().

◆ infer_loop_bounds_from_signedness()

◆ infer_loop_bounds_from_undefined()

static void infer_loop_bounds_from_undefined ( class loop * loop,
basic_block * bbs )
static
The following analyzers are extracting informations on the bounds
  of LOOP from the following undefined behaviors:

  - data references should not access elements over the statically
    allocated size,

  - signed variables should not overflow when flag_wrapv is not set.

References CDI_DOMINATORS, dominated_by_p(), ggc_alloc(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_stmt(), i, infer_loop_bounds_from_array(), infer_loop_bounds_from_pointer_arith(), infer_loop_bounds_from_signedness(), loop::latch, and loop::num_nodes.

Referenced by estimate_numbers_of_iterations().

◆ inverse()

◆ likely_max_loop_iterations()

bool likely_max_loop_iterations ( class loop * loop,
widest_int * nit )
Sets NIT to an likely upper bound for the maximum number of executions of the
latch of the LOOP.  If we have no reliable estimate, the function returns
false, otherwise returns true.   

References estimate_numbers_of_iterations(), get_likely_max_loop_iterations(), ggc_alloc(), and scev_initialized_p().

Referenced by likely_max_loop_iterations_int(), and likely_max_stmt_executions().

◆ likely_max_loop_iterations_int()

HOST_WIDE_INT likely_max_loop_iterations_int ( class loop * loop)
Similar to max_loop_iterations, but returns the estimate only
if it fits to HOST_WIDE_INT.  If this is not the case, or the estimate
on the number of iterations of LOOP could not be derived, returns -1.   

References wi::fits_shwi_p(), ggc_alloc(), and likely_max_loop_iterations().

Referenced by canonicalize_loop_induction_variables(), loop_distribution::execute(), predict_loops(), tree_ssa_unswitch_loops(), tree_unswitch_outer_loop(), and try_peel_loop().

◆ likely_max_stmt_executions()

bool likely_max_stmt_executions ( class loop * loop,
widest_int * nit )
Sets NIT to the estimated maximum number of executions of the latch of the
LOOP, plus one.  If we have no likely estimate, the function returns
false, otherwise returns true.   

References ggc_alloc(), wi::gtu_p(), and likely_max_loop_iterations().

Referenced by predict_loops().

◆ loop_exits_before_overflow()

◆ loop_niter_by_eval()

tree loop_niter_by_eval ( class loop * loop,
edge exit )
Tries to count the number of iterations of LOOP till it exits by EXIT
by brute force -- i.e. by determining the value of the operands of the
condition at EXIT in first few iterations of the loop (assuming that
these values are constant) and determining the first one in that the
condition is not satisfied.  Returns the constant giving the number
of the iterations of LOOP if successful, chrec_dont_know otherwise.   

References boolean_type_node, build_int_cst(), chrec_dont_know, tree_niter_desc::cmp, dump_file, dump_flags, fold_binary, fold_defer_overflow_warnings(), fold_undefer_and_ignore_overflow_warnings(), get_base_for(), get_val_for(), ggc_alloc(), gimple_cond_code(), gimple_cond_lhs(), gimple_cond_rhs(), gsi_last_bb(), i, integer_zerop(), invert_tree_comparison(), is_gimple_min_invariant(), loop_latch_edge(), loop_preheader_edge(), MAX_ITERATIONS_TO_TRACK, NULL_TREE, loop::num, PHI_ARG_DEF_FROM_EDGE, TDF_DETAILS, and unsigned_type_node.

Referenced by find_loop_niter_by_eval(), and predict_loops().

◆ loop_only_exit_p()

bool loop_only_exit_p ( const class loop * loop,
basic_block * body,
const_edge exit )

◆ max_loop_iterations()

◆ max_loop_iterations_int()

HOST_WIDE_INT max_loop_iterations_int ( class loop * loop)
Similar to max_loop_iterations, but returns the estimate only
if it fits to HOST_WIDE_INT.  If this is not the case, or the estimate
on the number of iterations of LOOP could not be derived, returns -1.   

References wi::fits_shwi_p(), ggc_alloc(), and max_loop_iterations().

Referenced by canonicalize_loop_induction_variables(), and predict_loops().

◆ max_stmt_executions()

bool max_stmt_executions ( class loop * loop,
widest_int * nit )
Sets NIT to the maximum number of executions of the latch of the
LOOP, plus one.  If we have no reliable estimate, the function returns
false, otherwise returns true.   

References ggc_alloc(), wi::gtu_p(), and max_loop_iterations().

Referenced by is_nonwrapping_integer_induction(), and max_stmt_executions_tree().

◆ maybe_lower_iteration_bound()

◆ n_of_executions_at_most()

static bool n_of_executions_at_most ( gimple * stmt,
class nb_iter_bound * niter_bound,
tree niter )
static
Returns true when we can prove that the number of executions of
STMT in the loop is at most NITER, according to the bound on
the number of executions of the statement NITER_BOUND->stmt recorded in
NITER_BOUND and fact that NITER_BOUND->stmt dominate STMT.

??? This code can become quite a CPU hog - we can have many bounds,
and large basic block forcing stmt_dominates_stmt_p to be queried
many times on a large basic blocks, so the whole thing is O(n^2)
for scev_probably_wraps_p invocation (that can be done n times).

It would make more sense (and give better answers) to remember BB
bounds computed by discover_iteration_bound_by_body_walk.   

References boolean_type_node, tree_niter_desc::bound, tree_niter_desc::cmp, wi::fits_to_tree_p(), fold_binary, gcc_assert, ggc_alloc(), gimple_bb(), gimple_has_side_effects(), gsi_for_stmt(), gsi_next(), gsi_stmt(), integer_nonzerop(), tree_niter_desc::niter, SIGNED, stmt_dominates_stmt_p(), TREE_TYPE, TYPE_UNSIGNED, and wide_int_to_tree().

Referenced by loop_exits_before_overflow().

◆ nowrap_type_p()

◆ number_of_iterations_bitcount()

static bool number_of_iterations_bitcount ( loop_p loop,
edge exit,
enum tree_code code,
class tree_niter_desc * niter )
static
See if LOOP contains a bit counting idiom. The idiom consists of two parts:
1. A modification to the induction variabler;.
2. A test to determine whether or not to exit the loop.

These can come in either order - i.e.:

<bb 3>
iv_1 = PHI <src(2), iv_2(4)>
if (test (iv_1))
  goto <bb 4>
else
  goto <bb 5>

<bb 4>
iv_2 = modify (iv_1)
goto <bb 3>

OR

<bb 3>
iv_1 = PHI <src(2), iv_2(4)>
iv_2 = modify (iv_1)

<bb 4>
if (test (iv_2))
  goto <bb 3>
else
  goto <bb 5>

The second form can be generated by copying the loop header out of the loop.

In the first case, the number of latch executions will be equal to the
number of induction variable modifications required before the test fails.

In the second case (modify_before_test), if we assume that the number of
modifications required before the test fails is nonzero, then the number of
latch executions will be one less than this number.

If we recognise the pattern, then we update niter accordingly, and return
true.   

References number_of_iterations_cltz(), number_of_iterations_cltz_complement(), and number_of_iterations_popcount().

Referenced by number_of_iterations_exit_assumptions().

◆ number_of_iterations_cltz()

◆ number_of_iterations_cltz_complement()

◆ number_of_iterations_cond()

static bool number_of_iterations_cond ( class loop * loop,
tree type,
affine_iv * iv0,
enum tree_code code,
affine_iv * iv1,
class tree_niter_desc * niter,
bool only_exit,
bool every_iteration )
static
Determine the number of iterations according to condition (for staying
inside loop) which compares two induction variables using comparison
operator CODE.  The induction variable on left side of the comparison
is IV0, the right-hand side is IV1.  Both induction variables must have
type TYPE, which must be an integer or pointer type.  The steps of the
ivs must be constants (or NULL_TREE, which is interpreted as constant zero).

LOOP is the loop whose number of iterations we are determining.

ONLY_EXIT is true if we are sure this is the only way the loop could be
exited (including possibly non-returning function calls, exceptions, etc.)
-- in this case we can use the information whether the control induction
variables can overflow or not in a more efficient way.

if EVERY_ITERATION is true, we know the test is executed on every iteration.

The results (number of iterations and assumptions as described in
comments at class tree_niter_desc in tree-ssa-loop.h) are stored to NITER.
Returns false if it fails to determine number of iterations, true if it
was determined (possibly with some assumptions).   

References wi::abs(), tree_niter_desc::assumptions, bounds::below, boolean_false_node, boolean_true_node, boolean_type_node, tree_niter_desc::bound, bound_difference(), build_int_cst(), tree_niter_desc::cmp, dump_affine_iv(), dump_file, dump_flags, fold_binary, fold_binary_to_constant(), gcc_assert, gcc_unreachable, ggc_alloc(), wi::gtu_p(), integer_nonzerop(), integer_zerop(), tree_niter_desc::max, tree_niter_desc::may_be_zero, tree_niter_desc::niter, NULL_TREE, loop::num, number_of_iterations_le(), number_of_iterations_lt(), number_of_iterations_ne(), POINTER_TYPE_P, print_decu(), print_generic_expr(), sizetype, swap_tree_comparison(), TDF_DETAILS, TDF_SLIM, wi::to_widest(), TREE_CODE, tree_int_cst_sign_bit(), type(), unsigned_type_for(), and bounds::up.

Referenced by number_of_iterations_exit_assumptions().

◆ number_of_iterations_exit()

◆ number_of_iterations_exit_assumptions()

bool number_of_iterations_exit_assumptions ( class loop * loop,
edge exit,
class tree_niter_desc * niter,
gcond ** at_stmt,
bool every_iteration,
basic_block * body )
Stores description of number of iterations of LOOP derived from
EXIT (an exit edge of the LOOP) in NITER.  Returns true if some useful
information could be derived (and fields of NITER have meaning described
in comments at class tree_niter_desc declaration), false otherwise.
When EVERY_ITERATION is true, only tests that are known to be executed
every iteration are considered (i.e. only test that alone bounds the loop).
If AT_STMT is not NULL, this function stores LOOP's condition statement in
it when returning true.   

References tree_niter_desc::assumptions, affine_iv::base, boolean_false_node, boolean_true_node, boolean_type_node, CDI_DOMINATORS, tree_niter_desc::control, dominated_by_p(), expand_simple_operations(), fold_build2, fold_convert, fold_defer_overflow_warnings(), fold_undefer_and_ignore_overflow_warnings(), free(), get_loop_body(), ggc_alloc(), gimple_cond_code(), gimple_cond_lhs(), gimple_cond_rhs(), gsi_last_bb(), integer_nonzerop(), integer_zerop(), invert_tree_comparison(), loop::latch, LOOP_C_FINITE, LOOP_C_INFINITE, loop_constraint_set_p(), loop_containing_stmt(), loop_only_exit_p(), tree_niter_desc::max, tree_niter_desc::may_be_zero, tree_niter_desc::niter, affine_iv::no_overflow, NULL, NULL_TREE, number_of_iterations_bitcount(), number_of_iterations_cltz(), number_of_iterations_cond(), POINTER_TYPE_P, simple_iv_with_niters(), simplify_using_initial_conditions(), simplify_using_outer_evolutions(), affine_iv::step, wi::to_widest(), TREE_CODE, TREE_TYPE, and type().

Referenced by number_of_iterations_exit(), vec_init_loop_exit_info(), and vect_get_loop_niters().

◆ number_of_iterations_le()

static bool number_of_iterations_le ( class loop * loop,
tree type,
affine_iv * iv0,
affine_iv * iv1,
class tree_niter_desc * niter,
bool exit_must_be_taken,
bounds * bnds )
static
Determines number of iterations of loop whose ending condition
is IV0 <= IV1.  TYPE is the type of the iv.  The number of
iterations is stored to NITER.  EXIT_MUST_BE_TAKEN is true if
we know that this condition must eventually become false (we derived this
earlier, and possibly set NITER->assumptions to make sure this
is the case).  BNDS bounds the difference IV1->base - IV0->base.   

References tree_niter_desc::assumptions, boolean_type_node, bounds_add(), build_int_cst(), fold_build2, fold_build_pointer_plus_hwi, ggc_alloc(), integer_nonzerop(), integer_zerop(), number_of_iterations_lt(), POINTER_TYPE_P, sizetype, type(), TYPE_MAX_VALUE, and TYPE_MIN_VALUE.

Referenced by number_of_iterations_cond().

◆ number_of_iterations_lt()

static bool number_of_iterations_lt ( class loop * loop,
tree type,
affine_iv * iv0,
affine_iv * iv1,
class tree_niter_desc * niter,
bool exit_must_be_taken,
bounds * bnds )
static

◆ number_of_iterations_lt_to_ne()

static bool number_of_iterations_lt_to_ne ( tree type,
affine_iv * iv0,
affine_iv * iv1,
class tree_niter_desc * niter,
tree * delta,
tree step,
bool exit_must_be_taken,
bounds * bnds )
static
Checks whether we can determine the final value of the control variable
of the loop with ending condition IV0 < IV1 (computed in TYPE).
DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
of the step.  The assumptions necessary to ensure that the computation
of the final value does not overflow are recorded in NITER.  If we
find the final value, we adjust DELTA and return TRUE.  Otherwise
we return false.  BNDS bounds the value of IV1->base - IV0->base,
and will be updated by the same amount as DELTA.  EXIT_MUST_BE_TAKEN is
true if we know that the exit must be taken eventually.   

References tree_niter_desc::assumptions, bounds::below, boolean_false_node, boolean_true_node, boolean_type_node, bounds_add(), fold_build1, fold_build2, fold_build_pointer_plus, fold_convert, ggc_alloc(), integer_nonzerop(), integer_zerop(), tree_niter_desc::may_be_zero, POINTER_TYPE_P, sizetype, wi::to_mpz(), wi::to_wide(), wi::to_widest(), TREE_CODE, TREE_TYPE, type(), TYPE_MAX_VALUE, TYPE_MIN_VALUE, and UNSIGNED.

Referenced by number_of_iterations_lt().

◆ number_of_iterations_ne()

static bool number_of_iterations_ne ( class loop * loop,
tree type,
affine_iv * iv,
tree final,
class tree_niter_desc * niter,
bool exit_must_be_taken,
bounds * bnds )
static
Determines number of iterations of loop whose ending condition
is IV <> FINAL.  TYPE is the type of the iv.  The number of
iterations is stored to NITER.  EXIT_MUST_BE_TAKEN is true if
we know that the exit must be taken eventually, i.e., that the IV
ever reaches the value FINAL (we derived this earlier, and possibly set
NITER->assumptions to make sure this is the case).  BNDS contains the
bounds on the difference FINAL - IV->base.   

References tree_niter_desc::assumptions, iv::base, boolean_false_node, boolean_type_node, tree_niter_desc::bound, bounds_negate(), build_int_cst(), build_low_bits_mask(), tree_niter_desc::cmp, tree_niter_desc::control, fold_binary_to_constant(), fold_build1, fold_build2, fold_convert, wi::from_mpz(), ggc_alloc(), integer_nonzerop(), integer_onep(), inverse(), tree_niter_desc::max, multiple_of_p(), tree_niter_desc::niter, iv::no_overflow, affine_iv::no_overflow, num_ending_zeros(), number_of_iterations_ne_max(), POINTER_TYPE_P, simplify_using_initial_conditions(), iv::step, TREE_CODE, tree_int_cst_sign_bit(), tree_to_uhwi(), type(), TYPE_MAX_VALUE, TYPE_MIN_VALUE, TYPE_PRECISION, TYPE_SIGN, and unsigned_type_for().

Referenced by number_of_iterations_cond(), and number_of_iterations_lt().

◆ number_of_iterations_ne_max()

static void number_of_iterations_ne_max ( mpz_t bnd,
bool no_overflow,
tree c,
tree s,
bounds * bnds,
bool exit_must_be_taken )
static
Derives the upper bound BND on the number of executions of loop with exit
condition S * i <> C.  If NO_OVERFLOW is true, then the control variable of
the loop does not overflow.  EXIT_MUST_BE_TAKEN is true if we are guaranteed
that the loop ends through this exit, i.e., the induction variable ever
reaches the value of C.  

The value C is equal to final - base, where final and base are the final and
initial value of the actual induction variable in the analysed loop.  BNDS
bounds the value of this difference when computed in signed type with
unbounded range, while the computation of C is performed in an unsigned
type with the range matching the range of the type of the induction variable.
In particular, BNDS.up contains an upper bound on C in the following cases:
-- if the iv must reach its final value without overflow, i.e., if
   NO_OVERFLOW && EXIT_MUST_BE_TAKEN is true, or
-- if final >= base, which we know to hold when BNDS.below >= 0.   

References bounds::below, wi::ctz(), ggc_alloc(), integer_onep(), wi::minus_one(), wi::mod_trunc(), multiple_of_p(), wi::to_mpz(), wi::to_wide(), TREE_CODE, TREE_TYPE, TYPE_OVERFLOW_UNDEFINED, TYPE_PRECISION, TYPE_SIGN, UNSIGNED, and bounds::up.

Referenced by number_of_iterations_ne().

◆ number_of_iterations_popcount()

◆ number_of_iterations_until_wrap()

◆ record_control_iv()

static void record_control_iv ( class loop * loop,
class tree_niter_desc * niter )
static
Records the control iv analyzed in NITER for LOOP if the iv is valid
and doesn't overflow.   

References tree_niter_desc::assumptions, iv::base, affine_iv::base, tree_niter_desc::control, loop::control_ivs, ggc_alloc(), integer_onep(), affine_iv::no_overflow, iv::step, and affine_iv::step.

Referenced by estimate_numbers_of_iterations().

◆ record_estimate()

static void record_estimate ( class loop * loop,
tree bound,
const widest_int & i_bound,
gimple * at_stmt,
bool is_exit,
bool realistic,
bool upper )
static
Records that AT_STMT is executed at most BOUND + 1 times in LOOP.  IS_EXIT
is true if the loop is exited immediately after STMT, and this exit
is taken at last when the STMT is executed BOUND + 1 times.
REALISTIC is true if BOUND is expected to be close to the real number
of iterations.  UPPER is true if we are sure the loop iterates at most
BOUND times.  I_BOUND is a widest_int upper estimate on BOUND.   

References nb_iter_bound::bound, tree_niter_desc::bound, loop::bounds, CDI_DOMINATORS, do_warn_aggressive_loop_optimizations(), dominated_by_p(), dump_file, dump_flags, gcc_checking_assert, ggc_alloc(), gimple_bb(), nb_iter_bound::is_exit, loop::latch, wi::ltu_p(), wi::min_precision(), loop::nb_iterations, nb_iter_bound::next, NULL_TREE, loop::num, print_decu(), print_generic_expr(), print_gimple_stmt(), record_niter_bound(), SIGNED, nb_iter_bound::stmt, TDF_DETAILS, TDF_SLIM, wi::to_widest(), and TREE_CODE.

Referenced by estimate_numbers_of_iterations(), and record_nonwrapping_iv().

◆ record_nonwrapping_iv()

static void record_nonwrapping_iv ( class loop * loop,
tree base,
tree step,
gimple * stmt,
tree low,
tree high,
bool realistic,
bool upper )
static
Record the estimate on number of iterations of LOOP based on the fact that
the induction variable BASE + STEP * i evaluated in STMT does not wrap and
its values belong to the range <LOW, HIGH>.  REALISTIC is true if the
estimated number of iterations is expected to be close to the real one.
UPPER is true if we are sure the induction variable does not wrap.   

References CDI_DOMINATORS, cfun, derive_constant_upper_bound(), dominated_by_p(), dump_file, dump_flags, fold_build1, fold_build2, fold_convert, get_cst_init_from_scev(), get_range_query(), ggc_alloc(), gimple_bb(), wi::gts_p(), integer_zerop(), INTEGRAL_TYPE_P, loop::latch, loop::num, print_generic_expr(), print_gimple_stmt(), record_estimate(), TDF_DETAILS, TDF_SLIM, wi::to_wide(), TREE_CODE, tree_int_cst_sign_bit(), TREE_TYPE, unsigned_type_for(), and wide_int_to_tree().

Referenced by idx_infer_loop_bounds(), infer_loop_bounds_from_pointer_arith(), and infer_loop_bounds_from_signedness().

◆ refine_bounds_using_guard()

static void refine_bounds_using_guard ( tree type,
tree varx,
mpz_t offx,
tree vary,
mpz_t offy,
tree c0,
enum tree_code cmp,
tree c1,
bounds * bnds )
static
From condition C0 CMP C1 derives information regarding the
difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE,
and stores it to BNDS.   

References bounds::below, end(), expand_simple_operations(), fold_convert, ggc_alloc(), integer_zerop(), INTEGRAL_TYPE_P, nowrap_type_p(), operand_equal_p(), split_to_var_and_offset(), STRIP_SIGN_NOPS, swap_tree_comparison(), TREE_CODE, TREE_TYPE, TYPE_MAX_VALUE, TYPE_MIN_VALUE, TYPE_PRECISION, bounds::up, and useless_type_conversion_p().

Referenced by bound_difference().

◆ refine_value_range_using_guard()

static void refine_value_range_using_guard ( tree type,
tree var,
tree c0,
enum tree_code cmp,
tree c1,
mpz_t below,
mpz_t up )
static

◆ scev_probably_wraps_p()

bool scev_probably_wraps_p ( tree var,
tree base,
tree step,
gimple * at_stmt,
class loop * loop,
bool use_overflow_semantics )
Return false only when the induction variable BASE + STEP * I is
known to not overflow: i.e. when the number of iterations is small
enough with respect to the step and initial condition in order to
keep the evolution confined in TYPEs bounds.  Return true when the
iv is known to overflow or when the property is not computable.

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).

If VAR is a ssa variable, this function also returns false if VAR can
be proven not overflow with value range info.   

References analyze_scalar_evolution(), chrec_contains_undetermined(), ggc_alloc(), integer_zerop(), loop_exits_before_overflow(), nonwrapping_chrec_p(), nowrap_type_p(), scev_var_range_cant_overflow(), TREE_CODE, and TREE_TYPE.

Referenced by convert_affine_scev(), get_scev_info(), and idx_infer_loop_bounds().

◆ scev_var_range_cant_overflow()

static bool scev_var_range_cant_overflow ( tree var,
tree step,
class loop * loop )
static
VAR is scev variable whose evolution part is constant STEP, this function
proves that VAR can't overflow by using value range info.  If VAR's value
range is [MIN, MAX], it can be proven by:
  MAX + step doesn't overflow    ; if step > 0
or
  MIN + step doesn't underflow   ; if step < 0.

We can only do this if var is computed in every loop iteration, i.e, var's
definition has to dominate loop latch.  Consider below example:

  {
    unsigned int i;

    <bb 3>:

    <bb 4>:
    # RANGE [0, 4294967294] NONZERO 65535
    # i_21 = PHI <0(3), i_18(9)>
    if (i_21 != 0)
      goto <bb 6>;
    else
      goto <bb 8>;

    <bb 6>:
    # RANGE [0, 65533] NONZERO 65535
    _6 = i_21 + 4294967295;
    # RANGE [0, 65533] NONZERO 65535
    _7 = (long unsigned int) _6;
    # RANGE [0, 524264] NONZERO 524280
    _8 = _7 * 8;
    # PT = nonlocal escaped
    _9 = a_14 + _8;
    *_9 = 0;

    <bb 8>:
    # RANGE [1, 65535] NONZERO 65535
    i_18 = i_21 + 1;
    if (i_18 >= 65535)
      goto <bb 10>;
    else
      goto <bb 9>;

    <bb 9>:
    goto <bb 4>;

    <bb 10>:
    return;
  }

VAR _6 doesn't overflow only with pre-condition (i_21 != 0), here we
can't use _6 to prove no-overlfow for _7.  In fact, var _7 takes value
sequence (4294967295, 0, 1, ..., 65533) in loop life time, rather than
(4294967295, 4294967296, ...).   

References CDI_DOMINATORS, cfun, dominated_by_p(), get_range_query(), wi::geu_p(), ggc_alloc(), gimple_bb(), INTEGRAL_TYPE_P, loop::latch, lower_bound_in_type(), r, path_range_query::range_of_expr(), SSA_NAME_DEF_STMT, wi::to_wide(), TREE_CODE, tree_int_cst_sign_bit(), TREE_TYPE, type(), and upper_bound_in_type().

Referenced by scev_probably_wraps_p().

◆ simplify_replace_tree()

tree simplify_replace_tree ( tree expr,
tree old,
tree new_tree,
tree(*)(tree, void *) valueize,
void * context,
bool do_fold )
Substitute NEW_TREE for OLD in EXPR and fold the result.
If VALUEIZE is non-NULL then OLD and NEW_TREE are ignored and instead
all SSA names are replaced with the result of calling the VALUEIZE
function with the SSA name as argument.   

References CONSTANT_CLASS_P, copy_node(), expr, EXPR_P, fold(), ggc_alloc(), i, NULL_TREE, operand_equal_p(), simplify_replace_tree(), TREE_CODE, TREE_OPERAND, TREE_OPERAND_LENGTH, and unshare_expr().

Referenced by process_bb(), simplify_replace_tree(), substitute_in_loop_info(), tree_simplify_using_condition_1(), and update_epilogue_loop_vinfo().

◆ simplify_using_initial_conditions()

◆ simplify_using_outer_evolutions()

static tree simplify_using_outer_evolutions ( class loop * loop,
tree expr )
static
Tries to simplify EXPR using the evolutions of the loop invariants
in the superloops of LOOP.  Returns the simplified expression
(or EXPR unchanged, if no simplification was possible).   

References boolean_type_node, changed, expr, fold_build2, fold_build3, ggc_alloc(), instantiate_parameters(), is_gimple_min_invariant(), NULL_TREE, simplify_using_outer_evolutions(), TREE_CODE, and TREE_OPERAND.

Referenced by number_of_iterations_exit_assumptions(), and simplify_using_outer_evolutions().

◆ split_to_var_and_offset()

static void split_to_var_and_offset ( tree expr,
tree * var,
mpz_t offset )
static
Splits expression EXPR to a variable part VAR and constant OFFSET.   

References build_int_cst_type(), expr, ggc_alloc(), offset, SIGNED, wi::to_mpz(), wi::to_wide(), TREE_CODE, TREE_OPERAND, TREE_TYPE, and TYPE_SIGN.

Referenced by bound_difference(), refine_bounds_using_guard(), and refine_value_range_using_guard().

◆ ssa_defined_by_minus_one_stmt_p()

static bool ssa_defined_by_minus_one_stmt_p ( tree op,
tree val )
static
Utility function to check if OP is defined by a stmt
that is a val - 1.   

References ggc_alloc(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), integer_minus_onep(), is_gimple_assign(), SSA_NAME_DEF_STMT, and TREE_CODE.

Referenced by number_of_iterations_popcount().

◆ stmt_dominates_stmt_p()

bool stmt_dominates_stmt_p ( gimple * s1,
gimple * s2 )
Returns true if statement S1 dominates statement S2.   

References CDI_DOMINATORS, dominated_by_p(), ggc_alloc(), gimple_bb(), gsi_next(), gsi_start_bb(), and gsi_stmt().

Referenced by n_of_executions_at_most().

◆ substitute_in_loop_info()

void substitute_in_loop_info ( class loop * loop,
tree name,
tree val )
Substitute value VAL for ssa name NAME inside expressions held
at LOOP.   

References loop::nb_iterations, and simplify_replace_tree().

Referenced by replace_uses_by().

◆ tree_simplify_using_condition()

static tree tree_simplify_using_condition ( tree cond,
tree expr )
static
Tries to simplify EXPR using the condition COND.  Returns the simplified
expression (or EXPR unchanged, if no simplification was possible).
Wrapper around tree_simplify_using_condition_1 that ensures that chains
of simple operations in definitions of ssa names in COND are expanded,
so that things like casts or incrementing the value of the bound before
the loop do not cause us to fail.   

References expand_simple_operations(), and tree_simplify_using_condition_1().

Referenced by simplify_using_initial_conditions().

◆ tree_simplify_using_condition_1()

static tree tree_simplify_using_condition_1 ( tree cond,
tree expr )
static
Tries to simplify EXPR using the condition COND.  Returns the simplified
expression (or EXPR unchanged, if no simplification was possible).   

References boolean_true_node, boolean_type_node, changed, expr, fold_binary, fold_build2, fold_build3, ggc_alloc(), integer_nonzerop(), integer_zerop(), invert_truthvalue, NULL_TREE, simplify_replace_tree(), TREE_CODE, TREE_OPERAND, and tree_simplify_using_condition_1().

Referenced by tree_simplify_using_condition(), and tree_simplify_using_condition_1().

◆ wide_int_cmp()

static int wide_int_cmp ( const void * p1,
const void * p2 )
static
Compare wide ints, callback for qsort.   

References wi::cmpu(), d1, d2, and ggc_alloc().

Referenced by discover_iteration_bound_by_body_walk().