- Generated by
1.8.1.1
|
GCC Middle and Back End API Reference
|
Data Structures | |
| struct | bounds |
| struct | ilb_data |
|
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, build_int_cst(), integer_nonzerop(), double_int::mask(), tree_niter_desc::may_be_zero, mpz_set_double_int(), double_int::sext(), affine_iv::step, tree_to_double_int(), type(), and bounds::up.
Referenced by number_of_iterations_lt().
|
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, build_int_cst(), integer_nonzerop(), integer_zerop(), affine_iv::no_overflow, and affine_iv::step.
Referenced by number_of_iterations_lt().
|
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, determine_value_range(), edge_def::flags, get_immediate_dominator(), gimple_cond_code(), gimple_cond_lhs(), gimple_cond_rhs(), loop::header, integer_zerop(), invert_tree_comparison(), last_stmt(), operand_equal_p(), refine_bounds_using_guard(), single_pred_edge(), single_pred_p(), split_to_var_and_offset(), edge_def::src, and bounds::up.
Referenced by number_of_iterations_cond().
|
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, double_int::mask(), mpz_set_double_int(), nowrap_type_p(), and bounds::up.
Referenced by bound_difference().
| int bound_index | ( | ) |
Return index of BOUND in BOUNDS array sorted in increasing order. Lookup by binary search.
References double_int::ult().
Referenced by discover_iteration_bound_by_body_walk().
|
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, double_int::mask(), mpz_set_double_int(), and bounds::up.
Referenced by number_of_iterations_le(), and number_of_iterations_lt_to_ne().
|
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().
|
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 flow_bb_inside_loop_p(), gimple_assign_rhs1(), gimple_assign_rhs_code(), gimple_bb(), gimple_references_memory_p(), loop::header, is_gimple_min_invariant(), and tcc_reference.
Referenced by get_base_for().
|
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(), and extract_ops_from_tree().
Referenced by derive_constant_upper_bound_ops(), and record_nonwrapping_iv().
|
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(), and gimple_assign_rhs_code().
Referenced by derive_constant_upper_bound_ops().
|
static |
Returns a constant upper bound on the value of expression OP0 CODE OP1, whose type is TYPE. The expression is considered to be unsigned. If its type is signed, its value must be nonnegative.
References derive_constant_upper_bound(), derive_constant_upper_bound_assign(), double_int_to_tree(), gimple_assign_lhs(), integer_nonzerop(), double_int::is_negative(), tree_niter_desc::max, double_int::sext(), tree_expr_nonnegative_p(), tree_int_cst_sign_bit(), tree_to_double_int(), double_int::udiv(), double_int::ugt(), double_int::ult(), and upper_bound_in_type().
Referenced by derive_constant_upper_bound(), and derive_constant_upper_bound_assign().
Stores estimate on the minimum/maximum value of the expression VAR + OFF in TYPE to MIN and MAX.
References get_type_static_bounds(), integer_zerop(), and nowrap_type_p().
Referenced by bound_difference().
|
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, edge_def::dest, double_int_cmp(), dump_double_int(), dump_file, dump_flags, loop::header, insert(), nb_iter_bound::is_exit, double_int::is_zero(), loop_exit_edge_p(), loop_latch_edge(), loop::nb_iterations_upper_bound, nb_iter_bound::next, pointer_map_contains(), pointer_map_create(), pointer_map_destroy(), pointer_map_insert(), queue, record_niter_bound(), nb_iter_bound::stmt, basic_block_def::succs, double_int::ult(), and vNULL.
Referenced by estimate_numbers_of_iterations_loop().
|
static |
Emit a -Waggressive-loop-optimizations warning if needed.
References CDI_DOMINATORS, cfun, function::curr_properties, dominated_by_p(), double_int_to_tree(), gimple_location(), inform(), last_stmt(), loop::latch, loop::nb_iterations, single_exit(), edge_def::src, tree_to_double_int(), double_int::ucmp(), loop::warned_aggressive_loop_optimizations, and warning_at().
Referenced by record_estimate().
| int double_int_cmp | ( | ) |
Compare double ints, callback for qsort.
References d1, d2, and double_int::ult().
Referenced by discover_iteration_bound_by_body_walk().
|
static |
Dumps description of affine induction variable IV to FILE.
References affine_iv::base, dump_file, integer_zerop(), affine_iv::no_overflow, print_generic_expr(), and affine_iv::step.
Referenced by number_of_iterations_cond().
| void estimate_numbers_of_iterations | ( | void | ) |
Records estimates on numbers of iterations of loops.
References estimate_numbers_of_iterations_loop(), fold_defer_overflow_warnings(), and fold_undefer_and_ignore_overflow_warnings().
Referenced by canonicalize_induction_variables(), tree_ssa_loop_bounds(), and tree_unroll_loops_completely().
| void estimate_numbers_of_iterations_loop | ( | ) |
Records estimates on numbers of iterations of LOOP. If USE_UNDEFINED_P is true also use estimates derived from undefined behavior.
References loop::any_estimate, loop::any_upper_bound, tree_niter_desc::bound, build_int_cst(), basic_block_def::count, discover_iteration_bound_by_body_walk(), EST_AVAILABLE, EST_NOT_COMPUTED, loop::estimate_state, expected_loop_iterations_unbounded(), gcov_type_to_double_int(), get_loop_exit_edges(), loop::header, infer_loop_bounds_from_undefined(), last_stmt(), tree_niter_desc::max, tree_niter_desc::may_be_zero, maybe_lower_iteration_bound(), loop::nb_iterations, loop::nb_iterations_upper_bound, tree_niter_desc::niter, number_of_iterations_exit(), number_of_latch_executions(), record_estimate(), record_niter_bound(), single_likely_exit(), tree_to_double_int(), and type().
| bool estimated_loop_iterations | ( | ) |
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 loop::any_estimate, basic_block_def::count, estimate_numbers_of_iterations_loop(), expected_loop_iterations_unbounded(), gcov_type_to_double_int(), loop::header, loop::nb_iterations_estimate, and scev_initialized_p().
| HOST_WIDE_INT estimated_loop_iterations_int | ( | ) |
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(), double_int::fits_shwi(), HOST_WIDE_INT, and double_int::to_shwi().
| bool estimated_stmt_executions | ( | ) |
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 double_int::ugt().
| HOST_WIDE_INT estimated_stmt_executions_int | ( | ) |
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 HOST_WIDE_INT.
| tree expand_simple_operations | ( | ) |
Expand definitions of ssa names in EXPR as long as they are simple enough, and return the new expression.
References copy_node(), expand_simple_operations(), fold(), fold_defer_overflow_warnings(), fold_undefer_and_ignore_overflow_warnings(), get_gimple_rhs_class(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), gimple_bb(), gimple_phi_num_args(), GIMPLE_SINGLE_RHS, is_gimple_min_invariant(), basic_block_def::loop_father, and single_pred().
| tree find_loop_niter | ( | ) |
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, loop::exits, get_loop_exit_edges(), integer_nonzerop(), integer_zerop(), tree_niter_desc::may_be_zero, tree_niter_desc::niter, number_of_iterations_exit(), and tree_int_cst_lt().
| tree find_loop_niter_by_eval | ( | ) |
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, get_loop_exit_edges(), just_once_each_iteration_p(), loop_niter_by_eval(), tree_niter_desc::niter, edge_def::src, and tree_int_cst_lt().
| bool finite_loop_p | ( | ) |
Return true if loop is known to have bounded number of iterations.
References loop::any_upper_bound, current_function_decl, dump_file, dump_flags, flags_from_decl_or_type(), max_loop_iterations(), and loop::num.
| void free_numbers_of_iterations_estimates | ( | void | ) |
Frees the information on upper bounds on numbers of iterations of loops.
References free_numbers_of_iterations_estimates_loop().
Referenced by canonicalize_induction_variables(), execute_vrp(), loop_optimizer_finalize(), tree_complete_unroll_inner(), tree_ssa_dce_loop(), tree_ssa_loop_done(), and tree_unroll_loops_completely().
| void free_numbers_of_iterations_estimates_loop | ( | ) |
Frees the information on upper bounds on numbers of iterations of LOOP.
References nb_iter_bound::bound, loop::bounds, EST_NOT_COMPUTED, loop::estimate_state, ggc_free(), loop::nb_iterations, and nb_iter_bound::next.
|
static |
Converts VAL to double_int.
References double_int::high, HOST_BITS_PER_WIDE_INT, HOST_WIDE_INT, and double_int::low.
Referenced by estimate_numbers_of_iterations_loop(), and estimated_loop_iterations().
|
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.
If such phi node exists, it is returned, otherwise NULL is returned.
References chain_of_csts_start(), is_gimple_min_invariant(), loop_latch_edge(), and loop_preheader_edge().
Referenced by loop_niter_by_eval().
|
static |
Given an expression X, then
* if X is NULL_TREE, we return the constant BASE.
* 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 gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_class(), gimple_assign_rhs_code(), gimple_assign_ssa_name_copy_p(), GIMPLE_BINARY_RHS, gimple_expr_type(), GIMPLE_UNARY_RHS, is_gimple_assign(), and is_gimple_min_invariant().
Referenced by loop_niter_by_eval().
|
static |
References analyze_scalar_evolution(), array_at_struct_end_p(), array_ref_low_bound(), array_ref_up_bound(), CDI_DOMINATORS, chrec_contains_symbols_defined_in_loop(), dominated_by_p(), evolution_part_in_loop_num(), initial_condition(), initial_condition_in_loop_num(), instantiate_parameters(), int_fits_type_p(), integer_zerop(), loop::latch, ilb_data::loop, loop_containing_stmt(), loop::num, operand_equal_p(), record_nonwrapping_iv(), scev_probably_wraps_p(), ilb_data::stmt, tree_contains_chrecs(), tree_int_cst_compare(), tree_int_cst_sign_bit(), and type().
Referenced by infer_loop_bounds_from_ref().
|
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(), infer_loop_bounds_from_ref(), is_gimple_assign(), and is_gimple_call().
Referenced by infer_loop_bounds_from_undefined().
|
static |
Determine information about number of iterations of a LOOP from the fact that pointer arithmetics in STMT does not overflow.
References analyze_scalar_evolution(), build_int_cstu(), chrec_contains_symbols_defined_in_loop(), chrec_contains_undetermined(), evolution_part_in_loop_num(), expr_invariant_in_loop_p(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), initial_condition_in_loop_num(), instantiate_parameters(), int_cst_value(), is_gimple_assign(), lower_bound_in_type(), nowrap_type_p(), loop::num, record_nonwrapping_iv(), tree_contains_chrecs(), type(), and upper_bound_in_type().
Referenced by infer_loop_bounds_from_undefined().
|
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().
|
static |
Determine information about number of iterations of a LOOP from the fact that signed arithmetics in STMT does not overflow.
References analyze_scalar_evolution(), chrec_contains_symbols_defined_in_loop(), chrec_contains_undetermined(), evolution_part_in_loop_num(), gimple_assign_lhs(), initial_condition_in_loop_num(), instantiate_parameters(), lower_bound_in_type(), loop::num, record_nonwrapping_iv(), tree_contains_chrecs(), type(), and upper_bound_in_type().
Referenced by infer_loop_bounds_from_undefined().
|
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(), free(), get_loop_body(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_stmt(), infer_loop_bounds_from_array(), infer_loop_bounds_from_pointer_arith(), infer_loop_bounds_from_signedness(), loop::latch, loop::num_nodes, and ilb_data::stmt.
Referenced by estimate_numbers_of_iterations_loop().
|
static |
Returns inverse of X modulo 2^s, where MASK = 2^s-1.
References build_int_cst(), build_int_cst_type(), cst_and_fits_in_hwi(), HOST_BITS_PER_WIDE_INT, HOST_WIDE_INT, int_const_binop(), int_cst_value(), and tree_floor_log2().
Referenced by number_of_iterations_ne().
| tree loop_niter_by_eval | ( | ) |
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 build_int_cst(), chrec_dont_know, tree_niter_desc::cmp, dump_file, dump_flags, edge_def::flags, fold_defer_overflow_warnings(), fold_undefer_and_ignore_overflow_warnings(), get_base_for(), get_val_for(), gimple_cond_code(), gimple_cond_lhs(), gimple_cond_rhs(), integer_zerop(), invert_tree_comparison(), is_gimple_min_invariant(), last_stmt(), loop_latch_edge(), loop_preheader_edge(), loop::num, and edge_def::src.
| bool loop_only_exit_p | ( | ) |
Returns true if EXIT is the only possible exit from LOOP.
References free(), get_loop_body(), gimple_has_side_effects(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_stmt(), loop::num_nodes, and single_exit().
| bool max_loop_iterations | ( | ) |
Sets NIT to an 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 loop::any_upper_bound, estimate_numbers_of_iterations_loop(), loop::nb_iterations_upper_bound, and scev_initialized_p().
| HOST_WIDE_INT max_loop_iterations_int | ( | ) |
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 double_int::fits_shwi(), HOST_WIDE_INT, max_loop_iterations(), and double_int::to_shwi().
| bool max_stmt_executions | ( | ) |
Sets NIT to the estimated 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 max_loop_iterations(), and double_int::ugt().
| HOST_WIDE_INT max_stmt_executions_int | ( | ) |
Returns an upper bound on 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 HOST_WIDE_INT, and max_loop_iterations_int().
|
static |
See if every path cross the loop goes through a statement that is known to not execute at the last iteration. In that case we can decrese iteration count by 1.
References bitmap_set_bit(), nb_iter_bound::bound, loop::bounds, edge_def::dest, dump_file, dump_flags, gimple_has_side_effects(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_stmt(), loop::header, basic_block_def::index, nb_iter_bound::is_exit, loop_exit_edge_p(), loop_latch_edge(), loop::nb_iterations_upper_bound, nb_iter_bound::next, pointer_set_contains(), pointer_set_create(), pointer_set_destroy(), pointer_set_insert(), queue, record_niter_bound(), nb_iter_bound::stmt, basic_block_def::succs, double_int::ult(), visited, and vNULL.
Referenced by estimate_numbers_of_iterations_loop().
|
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 nb_iter_bound::bound, double_int_fits_to_tree_p(), double_int_to_tree(), gimple_has_side_effects(), gsi_for_stmt(), gsi_next(), gsi_stmt(), integer_nonzerop(), nb_iter_bound::is_exit, double_int::is_zero(), nb_iter_bound::stmt, and stmt_dominates_stmt_p().
Referenced by scev_probably_wraps_p().
| bool nowrap_type_p | ( | ) |
Returns true if the arithmetics in TYPE can be assumed not to wrap.
|
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 struct tree_niter_desc in tree-flow.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 tree_niter_desc::assumptions, affine_iv::base, bounds::below, tree_niter_desc::bound, bound_difference(), build_int_cst(), tree_niter_desc::cmp, dump_affine_iv(), dump_double_int(), dump_file, dump_flags, fold_binary_to_constant(), integer_nonzerop(), integer_zerop(), tree_niter_desc::max, tree_niter_desc::may_be_zero, tree_niter_desc::niter, affine_iv::no_overflow, loop::num, number_of_iterations_le(), number_of_iterations_lt(), number_of_iterations_ne(), print_generic_expr(), affine_iv::step, swap_tree_comparison(), tree_int_cst_sign_bit(), type(), unsigned_type_for(), and bounds::up.
Referenced by number_of_iterations_exit().
| bool number_of_iterations_exit | ( | struct loop * | loop, |
| edge | exit, | ||
| struct tree_niter_desc * | niter, | ||
| bool | warn, | ||
| bool | every_iteration | ||
| ) |
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 has meaning described in comments at struct tree_niter_desc declaration), false otherwise. If WARN is true and -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use potentially unsafe assumptions. 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).
References tree_niter_desc::assumptions, affine_iv::base, CDI_DOMINATORS, dominated_by_p(), expand_simple_operations(), edge_def::flags, fold_defer_overflow_warnings(), fold_undefer_and_ignore_overflow_warnings(), gimple_cond_code(), gimple_cond_lhs(), gimple_cond_rhs(), gimple_location(), input_location, integer_all_onesp(), integer_onep(), integer_zerop(), invert_tree_comparison(), last_stmt(), loop::latch, loop_containing_stmt(), loop_only_exit_p(), tree_niter_desc::max, tree_niter_desc::may_be_zero, tree_niter_desc::niter, number_of_iterations_cond(), simple_iv(), simplify_using_initial_conditions(), simplify_using_outer_evolutions(), single_exit(), edge_def::src, affine_iv::step, tree_to_double_int(), type(), and warning_at().
Referenced by can_unroll_loop_p(), estimate_function_body_sizes(), estimate_numbers_of_iterations_loop(), find_loop_niter(), graphite_can_represent_loop(), niter_for_exit(), number_of_latch_executions(), predict_loops(), remove_redundant_iv_tests(), and try_get_loop_niter().
|
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, bounds_add(), build_int_cst(), integer_nonzerop(), integer_zerop(), number_of_iterations_lt(), affine_iv::step, and type().
Referenced by number_of_iterations_cond().
|
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. BNDS bounds the difference IV1->base - IV0->base. EXIT_MUST_BE_TAKEN is true if we know that the exit must be taken eventually.
References assert_loop_rolls_lt(), assert_no_overflow_lt(), affine_iv::base, bounds::below, tree_niter_desc::bound, build_int_cst(), tree_niter_desc::cmp, tree_niter_desc::control, integer_all_onesp(), integer_nonzerop(), integer_onep(), integer_zerop(), tree_niter_desc::max, tree_niter_desc::may_be_zero, mpz_get_double_int(), mpz_set_double_int(), tree_niter_desc::niter, affine_iv::no_overflow, number_of_iterations_lt_to_ne(), number_of_iterations_ne(), affine_iv::step, tree_to_double_int(), unsigned_type_for(), and bounds::up.
Referenced by number_of_iterations_cond(), and number_of_iterations_le().
|
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, bounds_add(), integer_nonzerop(), integer_zerop(), tree_niter_desc::may_be_zero, mpz_set_double_int(), affine_iv::no_overflow, affine_iv::step, tree_to_double_int(), and type().
Referenced by number_of_iterations_lt().
|
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, affine_iv::base, 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(), integer_nonzerop(), integer_onep(), inverse(), tree_niter_desc::max, mpz_get_double_int(), tree_niter_desc::niter, affine_iv::no_overflow, num_ending_zeros(), number_of_iterations_ne_max(), affine_iv::step, tree_int_cst_sign_bit(), tree_low_cst(), and unsigned_type_for().
Referenced by number_of_iterations_cond(), and number_of_iterations_lt().
|
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, integer_onep(), double_int::is_zero(), double_int::mask(), double_int::mod(), mpz_set_double_int(), multiple_of_p(), num_ending_zeros(), tree_low_cst(), tree_to_double_int(), and bounds::up.
Referenced by number_of_iterations_ne().
|
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 an unsigned double_int upper estimate on BOUND.
References nb_iter_bound::bound, loop::bounds, CDI_DOMINATORS, do_warn_aggressive_loop_optimizations(), dominated_by_p(), dump_double_int(), dump_file, dump_flags, nb_iter_bound::is_exit, loop::latch, loop::nb_iterations, nb_iter_bound::next, loop::num, print_generic_expr(), print_gimple_stmt(), record_niter_bound(), nb_iter_bound::stmt, tree_to_double_int(), and double_int::ult().
Referenced by estimate_numbers_of_iterations_loop(), and record_nonwrapping_iv().
| void record_niter_bound | ( | struct loop * | loop, |
| double_int | i_bound, | ||
| bool | realistic, | ||
| bool | upper | ||
| ) |
Records that every statement in LOOP is executed I_BOUND times. REALISTIC is true if I_BOUND is expected to be close to the real number of iterations. UPPER is true if we are sure the loop iterates at most I_BOUND times.
References loop::any_estimate, loop::any_upper_bound, loop::nb_iterations_estimate, loop::nb_iterations_upper_bound, and double_int::ult().
Referenced by canonicalize_loop_induction_variables(), discover_iteration_bound_by_body_walk(), estimate_numbers_of_iterations_loop(), iv_number_of_iterations(), maybe_lower_iteration_bound(), record_estimate(), vect_do_peeling_for_alignment(), and vect_do_peeling_for_loop_bound().
|
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 derive_constant_upper_bound(), dump_file, dump_flags, integer_zerop(), loop::num, print_generic_expr(), print_gimple_stmt(), record_estimate(), tree_int_cst_sign_bit(), and unsigned_type_for().
Referenced by idx_infer_loop_bounds(), infer_loop_bounds_from_pointer_arith(), and infer_loop_bounds_from_signedness().
|
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, expand_simple_operations(), integer_zerop(), nowrap_type_p(), operand_equal_p(), split_to_var_and_offset(), swap_tree_comparison(), bounds::up, and useless_type_conversion_p().
Referenced by bound_difference().
| bool scev_probably_wraps_p | ( | tree | base, |
| tree | step, | ||
| gimple | at_stmt, | ||
| struct 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).
References nb_iter_bound::bound, loop::bounds, chrec_contains_undetermined(), double_int_fits_to_tree_p(), double_int_to_tree(), estimate_numbers_of_iterations_loop(), fold_defer_overflow_warnings(), fold_undefer_and_ignore_overflow_warnings(), integer_nonzerop(), integer_zerop(), lower_bound_in_type(), max_loop_iterations(), n_of_executions_at_most(), nb_iter_bound::next, nowrap_type_p(), tree_int_cst_sign_bit(), unsigned_type_for(), and upper_bound_in_type().
Referenced by adjust_range_with_scev(), convert_affine_scev(), idx_infer_loop_bounds(), and vrp_var_may_overflow().
|
static |
Substitute NEW for OLD in EXPR and fold the result.
References copy_node(), fold(), operand_equal_p(), and unshare_expr().
Referenced by substitute_in_loop_info(), and tree_simplify_using_condition_1().
|
static |
Tries to simplify EXPR using the conditions on entry to LOOP. Returns the simplified expression (or EXPR unchanged, if no simplification was possible).
References CDI_DOMINATORS, edge_def::flags, get_immediate_dominator(), gimple_cond_code(), gimple_cond_lhs(), gimple_cond_rhs(), loop::header, last_stmt(), single_pred_edge(), single_pred_p(), edge_def::src, and tree_simplify_using_condition().
Referenced by number_of_iterations_exit().
|
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 changed, instantiate_parameters(), and is_gimple_min_invariant().
Referenced by number_of_iterations_exit().
|
static |
Splits expression EXPR to a variable part VAR and constant OFFSET.
References build_int_cst_type(), mpz_set_double_int(), double_int::sext(), and tree_to_double_int().
Referenced by bound_difference(), and refine_bounds_using_guard().
| bool stmt_dominates_stmt_p | ( | ) |
Returns true if statement S1 dominates statement S2.
References CDI_DOMINATORS, dominated_by_p(), gimple_bb(), gsi_next(), gsi_start_bb(), and gsi_stmt().
| void substitute_in_loop_info | ( | ) |
Substitute value VAL for ssa name NAME inside expressions held at LOOP.
References loop::nb_iterations, and simplify_replace_tree().
|
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().
|
static |
Tries to simplify EXPR using the condition COND. Returns the simplified expression (or EXPR unchanged, if no simplification was possible).
References changed, expand_simple_operations(), integer_nonzerop(), integer_zerop(), and simplify_replace_tree().
Referenced by tree_simplify_using_condition().
1.8.1.1