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-data-ref.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 is_lshift_by_1 (gassign *stmt)
static bool is_rshift_by_1 (gassign *stmt)
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-2025 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()

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, affine_iv::base, bounds::below, boolean_true_node, boolean_type_node, build_int_cst(), fold_build2, fold_convert, integer_nonzerop(), tree_niter_desc::may_be_zero, wi::minus_one(), POINTER_TYPE_P, wi::sext(), sizetype, affine_iv::step, wi::to_mpz(), wi::to_widest(), TYPE_MAX_VALUE, TYPE_MIN_VALUE, TYPE_PRECISION, UNSIGNED, and bounds::up.

Referenced by number_of_iterations_lt().

◆ assert_no_overflow_lt()

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, affine_iv::base, boolean_type_node, build_int_cst(), fold_build2, fold_convert, integer_nonzerop(), integer_zerop(), affine_iv::no_overflow, affine_iv::step, TREE_CODE, TREE_TYPE, TYPE_MAX_VALUE, and TYPE_MIN_VALUE.

Referenced by number_of_iterations_lt().

◆ bound_difference()

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 as_a(), bounds::below, bound_difference_of_offsetted_base(), CDI_DOMINATORS, cfun, determine_value_range(), end(), ENTRY_BLOCK_PTR_FOR_FN, get_immediate_dominator(), 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()

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, wi::minus_one(), nowrap_type_p(), wi::to_mpz(), TYPE_PRECISION, UNSIGNED, bounds::up, and y.

Referenced by bound_difference().

◆ bound_index()

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, and wi::ltu_p().

Referenced by discover_iteration_bound_by_body_walk().

◆ bounds_add()

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

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, and bounds::up.

Referenced by number_of_iterations_ne().

◆ build_cltz_expr()

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

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 as_a(), chain_of_csts_start(), flow_bb_inside_loop_p(), 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()

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

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

widest_int derive_constant_upper_bound_ops ( tree type,
tree op0,
enum tree_code code,
tree op1 )
static

◆ determine_value_range()

◆ discover_iteration_bound_by_body_walk()

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, hash_map< KeyId, Value, Traits >::get(), 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(), hash_map< KeyId, Value, Traits >::put(), 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()

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

References iv::base, dump_file, 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(), 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 generic_wide_int< storage >::to_shwi().

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

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-2025 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(), 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(), 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()

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

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

tree get_upper_bound_based_on_builtin_expr_with_prob ( gcond * cond)
static

◆ get_val_for()

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

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

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(), and ilb_data::stmt.

Referenced by infer_loop_bounds_from_array().

◆ infer_loop_bounds_from_signedness()

◆ infer_loop_bounds_from_undefined()

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

tree inverse ( tree x,
tree mask )
static

◆ is_lshift_by_1()

bool is_lshift_by_1 ( gassign * stmt)
static

◆ is_rshift_by_1()

◆ 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(), 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(), likely_max_loop_iterations(), and generic_wide_int< storage >::to_shwi().

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 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 iv::base, boolean_type_node, build_int_cst(), char_type_node, chrec_dont_know, tree_niter_desc::cmp, compare_tree_int(), dump_file, dump_flags, dyn_cast(), fold_binary, fold_defer_overflow_warnings(), fold_undefer_and_ignore_overflow_warnings(), get_base_for(), get_val_for(), gimple_assign_rhs1(), gimple_assign_rhs_code(), 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, safe_dyn_cast(), simple_iv(), split_constant_offset(), SSA_NAME_DEF_STMT, iv::step, STRIP_NOPS, TDF_DETAILS, TREE_CODE, tree_fits_uhwi_p(), TREE_OPERAND, TREE_STRING_LENGTH, TREE_STRING_POINTER, tree_to_uhwi(), TREE_TYPE, TYPE_MODE, 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 )
Returns true if EXIT is the only possible exit from LOOP.

References gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_stmt(), i, loop::num_nodes, single_exit(), and stmt_can_terminate_bb_p().

Referenced by number_of_iterations_exit_assumptions(), and tree_ssa_iv_optimize_loop().

◆ max_loop_iterations()

bool max_loop_iterations ( class loop * loop,
widest_int * nit )

◆ 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(), max_loop_iterations(), and generic_wide_int< storage >::to_shwi().

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

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, nb_iter_bound::bound, tree_niter_desc::bound, tree_niter_desc::cmp, wi::fits_to_tree_p(), fold_binary, gcc_assert, gimple_bb(), gimple_has_side_effects(), gsi_for_stmt(), gsi_next(), gsi_stmt(), integer_nonzerop(), nb_iter_bound::is_exit, tree_niter_desc::niter, SIGNED, nb_iter_bound::stmt, 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()

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

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, affine_iv::base, 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, wi::gtu_p(), integer_nonzerop(), integer_zerop(), tree_niter_desc::max, tree_niter_desc::may_be_zero, tree_niter_desc::niter, affine_iv::no_overflow, 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, affine_iv::step, swap_tree_comparison(), TDF_DETAILS, TDF_SLIM, wi::to_widest(), TREE_CODE, tree_int_cst_sign_bit(), 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(), 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, safe_dyn_cast(), simple_iv_with_niters(), simplify_using_initial_conditions(), simplify_using_outer_evolutions(), affine_iv::step, wi::to_widest(), TREE_CODE, and TREE_TYPE.

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

◆ number_of_iterations_le()

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, affine_iv::base, boolean_type_node, bounds_add(), build_int_cst(), fold_build2, fold_build_pointer_plus_hwi, integer_nonzerop(), integer_zerop(), number_of_iterations_lt(), POINTER_TYPE_P, sizetype, affine_iv::step, TYPE_MAX_VALUE, and TYPE_MIN_VALUE.

Referenced by number_of_iterations_cond().

◆ number_of_iterations_lt()

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

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, affine_iv::base, bounds::below, boolean_false_node, boolean_true_node, boolean_type_node, bounds_add(), fold_build2, fold_convert, integer_nonzerop(), integer_zerop(), tree_niter_desc::may_be_zero, affine_iv::no_overflow, POINTER_TYPE_P, sizetype, affine_iv::step, wi::to_mpz(), wi::to_wide(), wi::to_widest(), TREE_CODE, TREE_TYPE, TYPE_MAX_VALUE, TYPE_MIN_VALUE, and UNSIGNED.

Referenced by number_of_iterations_lt().

◆ number_of_iterations_ne()

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(), integer_nonzerop(), integer_onep(), inverse(), tree_niter_desc::max, multiple_of_p(), tree_niter_desc::niter, affine_iv::no_overflow, 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_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()

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(), integer_onep(), wi::mask(), 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()

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, affine_iv::base, iv::base, tree_niter_desc::control, loop::control_ivs, ggc_alloc(), integer_onep(), affine_iv::no_overflow, affine_iv::step, and iv::step.

Referenced by estimate_numbers_of_iterations().

◆ record_estimate()

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

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(), gimple_bb(), wi::gts_p(), integer_zerop(), INTEGRAL_TYPE_P, loop::latch, value_range::lbound(), 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, value_range::ubound(), value_range::undefined_p(), unsigned_type_for(), value_range::varying_p(), 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()

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

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

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(), 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, 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(* valueize )(tree, void *),
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_P, fold(), 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()

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, fold_build2, fold_build3, 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()

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

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

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

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, fold_binary, fold_build2, fold_build3, 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()

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

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

Referenced by discover_iteration_bound_by_body_walk().