tree-vrp.cc File Reference

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "basic-block.h"
#include "bitmap.h"
#include "sbitmap.h"
#include "options.h"
#include "dominance.h"
#include "function.h"
#include "cfg.h"
#include "tree.h"
#include "gimple.h"
#include "tree-pass.h"
#include "ssa.h"
#include "gimple-pretty-print.h"
#include "fold-const.h"
#include "cfganal.h"
#include "gimple-iterator.h"
#include "tree-cfg.h"
#include "tree-ssa-loop-manip.h"
#include "tree-ssa-loop-niter.h"
#include "tree-into-ssa.h"
#include "cfgloop.h"
#include "tree-scalar-evolution.h"
#include "tree-ssa-propagate.h"
#include "domwalk.h"
#include "vr-values.h"
#include "gimple-array-bounds.h"
#include "gimple-range.h"
#include "gimple-range-path.h"
#include "value-pointer-equiv.h"
#include "gimple-fold.h"
#include "tree-dfa.h"
#include "tree-ssa-dce.h"
#include "alloc-pool.h"
#include "cgraph.h"
#include "symbol-summary.h"
#include "ipa-utils.h"
#include "sreal.h"
#include "ipa-cp.h"
#include "ipa-prop.h"
#include "attribs.h"

Include dependency graph for tree-vrp.cc:

Data Structures
class	remove_unreachable
struct	case_info
class	rvrp_folder
class	fvrp_folder

Functions
static bool	fully_replaceable (tree name, basic_block bb)
enum value_range_kind	intersect_range_with_nonzero_bits (enum value_range_kind vr_type, wide_int *min, wide_int *max, const wide_int &nonzero_bits, signop sgn)
static tree	get_single_symbol (tree t, bool *neg, tree *inv)
int	compare_values_warnv (tree val1, tree val2, bool *strict_overflow_p)
int	compare_values (tree val1, tree val2)
static bool	overflow_comparison_p_1 (enum tree_code code, tree op0, tree op1, bool reversed, tree *new_cst)
bool	overflow_comparison_p (tree_code code, tree name, tree val, tree *new_cst)
bool	find_case_label_index (gswitch *stmt, size_t start_idx, tree val, size_t *idx)
bool	find_case_label_range (gswitch *stmt, tree min, tree max, size_t *min_idx, size_t *max_idx)
tree	find_case_label_range (gswitch *switch_stmt, const irange *range_of_op)
unsigned int	execute_ranger_vrp (struct function *fun, bool warn_array_bounds_p, bool final_p)
unsigned int	execute_fast_vrp (struct function *fun)
gimple_opt_pass *	make_pass_vrp (gcc::context *ctxt)
gimple_opt_pass *	make_pass_early_vrp (gcc::context *ctxt)
gimple_opt_pass *	make_pass_fast_vrp (gcc::context *ctxt)
gimple_opt_pass *	make_pass_assumptions (gcc::context *ctx)

Function Documentation

compare_values()

int compare_values	(	tree	val1,
		tree	val2 )

Compare values like compare_values_warnv.   

References compare_values_warnv(), and ggc_alloc().

Referenced by test_for_singularity().

compare_values_warnv()

int compare_values_warnv	(	tree	val1,
		tree	val2,
		bool *	strict_overflow_p )

Compare two values VAL1 and VAL2.  Return

        -2 if VAL1 and VAL2 cannot be compared at compile-time,
        -1 if VAL1 < VAL2,
         0 if VAL1 == VAL2,
     +1 if VAL1 > VAL2, and
     +2 if VAL1 != VAL2

This is similar to tree_int_cst_compare but supports pointer values
and values that cannot be compared at compile time.

If STRICT_OVERFLOW_P is not NULL, then set *STRICT_OVERFLOW_P to
true if the return value is only valid if we assume that signed
overflow is undefined.   

References boolean_type_node, build_int_cst(), wi::cmp(), fold_binary_to_constant(), fold_convert, fold_defer_overflow_warnings(), fold_undefer_and_ignore_overflow_warnings(), gcc_assert, get_single_symbol(), ggc_alloc(), integer_onep(), INTEGRAL_TYPE_P, is_gimple_min_invariant(), known_eq, known_gt, known_lt, NULL, operand_equal_p(), POINTER_TYPE_P, poly_int_tree_p(), wi::to_poly_widest(), wi::to_wide(), TREE_CODE, tree_int_cst_compare(), TREE_OVERFLOW, TREE_TYPE, TYPE_OVERFLOW_UNDEFINED, TYPE_SIGN, useless_type_conversion_p(), and warning_suppressed_p().

Referenced by compare_values().

execute_fast_vrp()

unsigned int execute_fast_vrp

(

struct function *

fun

)

References calculate_dominance_info(), CDI_DOMINATORS, gcc_checking_assert, ggc_alloc(), NULL, and function::x_range_query.

execute_ranger_vrp()

unsigned int execute_ranger_vrp	(	struct function *	fun,
		bool	warn_array_bounds_p,
		bool	final_p )

Main entry point for a VRP pass using just ranger. This can be called
from anywhere to perform a VRP pass, including from EVRP.   

References cgraph_node::add_detected_attribute(), calculate_dominance_info(), CDI_DOMINATORS, cfun, gimple_ranger::const_query(), current_function_decl, DECL_ATTRIBUTES, disable_ranger(), gimple_ranger::dump(), dump_file, dump_flags, enable_ranger(), EXIT_BLOCK_PTR_FOR_FN, FOR_ALL_BB_FN, FOR_EACH_EDGE, cgraph_node::get(), ggc_alloc(), gimple_return_retval(), gsi_last_bb(), ipa_record_return_value_range(), lookup_attribute(), loop_optimizer_finalize(), loop_optimizer_init(), LOOPS_HAVE_RECORDED_EXITS, LOOPS_NORMAL, gimple_ranger::non_executable_edge_flag, NULL, phi_analysis_finalize(), phi_analysis_initialize(), POINTER_TYPE_P, r, gimple_ranger::range_of_expr(), ranger, rewrite_into_loop_closed_ssa(), scev_finalize(), scev_initialize(), scev_reset(), set_all_edges_as_executable(), basic_block_def::succs, Value_Range::supports_type_p(), TDF_DETAILS, TODO_update_ssa, TREE_TYPE, and warn_function_returns_nonnull().

find_case_label_index()

bool find_case_label_index	(	gswitch *	stmt,
		size_t	start_idx,
		tree	val,
		size_t *	idx )

Searches the case label vector VEC for the index *IDX of the CASE_LABEL
that includes the value VAL.  The search is restricted to the range
[START_IDX, n - 1] where n is the size of VEC.

If there is a CASE_LABEL for VAL, its index is placed in IDX and true is
returned.

If there is no CASE_LABEL for VAL and there is one that is larger than VAL,
it is placed in IDX and false is returned.

If VAL is larger than any CASE_LABEL, n is placed on IDX and false is
returned.  

References CASE_HIGH, CASE_LOW, ggc_alloc(), gimple_switch_label(), gimple_switch_num_labels(), i, NULL, and tree_int_cst_compare().

Referenced by find_case_label_range(), and simplify_using_ranges::simplify_switch_using_ranges().

find_case_label_range() [1/2]

bool find_case_label_range	(	gswitch *	stmt,
		tree	min,
		tree	max,
		size_t *	min_idx,
		size_t *	max_idx )

Searches the case label vector VEC for the range of CASE_LABELs that is used
for values between MIN and MAX. The first index is placed in MIN_IDX. The
last index is placed in MAX_IDX. If the range of CASE_LABELs is empty
then MAX_IDX < MIN_IDX.
Returns true if the default label is not needed.  

References CASE_HIGH, CASE_LOW, find_case_label_index(), ggc_alloc(), gimple_switch_label(), i, int_const_binop(), and integer_onep().

Referenced by find_case_label_range(), find_case_label_ranges(), back_threader::find_taken_edge_switch(), hybrid_jt_simplifier::simplify(), and simplify_using_ranges::simplify_switch_using_ranges().

find_case_label_range() [2/2]

tree find_case_label_range	(	gswitch *	switch_stmt,
		const irange *	range_of_op )

Given a SWITCH_STMT, return the case label that encompasses the
known possible values for the switch operand.  RANGE_OF_OP is a
range for the known values of the switch operand.   

References CASE_HIGH, CASE_LOW, find_case_label_range(), ggc_alloc(), gimple_switch_index(), gimple_switch_label(), gimple_switch_num_labels(), i, NULL_TREE, range_cast(), wi::to_wide(), TREE_TYPE, types_compatible_p(), and wide_int_to_tree().

fully_replaceable()

static bool fully_replaceable ( tree name, basic_block bb )

static

References CDI_DOMINATORS, dominated_by_p(), FOR_EACH_IMM_USE_FAST, ggc_alloc(), gimple_bb(), gimple_vuse(), is_gimple_debug(), SSA_NAME_DEF_STMT, and USE_STMT.

Referenced by remove_unreachable::handle_early().

get_single_symbol()

static tree get_single_symbol ( tree t, bool * neg, tree * inv )

static

Return the single symbol (an SSA_NAME) contained in T if any, or NULL_TREE
otherwise.  We only handle additive operations and set NEG to true if the
symbol is negated and INV to the invariant part, if any.   

References drop_tree_overflow(), ggc_alloc(), is_gimple_min_invariant(), NULL_TREE, TREE_CODE, TREE_OPERAND, and TREE_OVERFLOW_P.

Referenced by compare_values_warnv().

intersect_range_with_nonzero_bits()

enum value_range_kind intersect_range_with_nonzero_bits	(	enum value_range_kind	vr_type,
		wide_int *	min,
		wide_int *	max,
		const wide_int &	nonzero_bits,
		signop	sgn )

VR_TYPE describes a range with minimum value *MIN and maximum
value *MAX.  Restrict the range to the set of values that have
no bits set outside NONZERO_BITS.  Update *MIN and *MAX and
return the new range type.

SGN gives the sign of the values described by the range.   

References gcc_checking_assert, wi::ge_p(), ggc_alloc(), wi::gt_p(), wi::le_p(), wi::max_value(), wi::min_value(), nonzero_bits(), wi::round_down_for_mask(), wi::round_up_for_mask(), VR_ANTI_RANGE, VR_RANGE, VR_UNDEFINED, and VR_VARYING.

Referenced by split_constant_offset(), and vect_get_range_info().

make_pass_assumptions()

gimple_opt_pass * make_pass_assumptions

(

gcc::context *

ctx

)

make_pass_early_vrp()

gimple_opt_pass * make_pass_early_vrp

(

gcc::context *

ctxt

)

References ggc_alloc().

make_pass_fast_vrp()

gimple_opt_pass * make_pass_fast_vrp

(

gcc::context *

ctxt

)

References ggc_alloc().

make_pass_vrp()

gimple_opt_pass * make_pass_vrp

(

gcc::context *

ctxt

)

References ggc_alloc().

overflow_comparison_p()

bool overflow_comparison_p	(	tree_code	code,
		tree	name,
		tree	val,
		tree *	new_cst )

OP0 CODE OP1 is a comparison.  Examine the comparison and potentially
OP1's defining statement to see if it ultimately has the form
OP0 CODE (OP0 PLUS INTEGER_CST)

If so, return TRUE indicating this is an overflow test and store into
*NEW_CST an updated constant that can be used in a narrowed range test.

These statements are left as-is in the IL to facilitate discovery of
{ADD,SUB}_OVERFLOW sequences later in the optimizer pipeline.  But
the alternate range representation is often useful within VRP.   

References ggc_alloc(), overflow_comparison_p_1(), and swap_tree_comparison().

Referenced by simplify_using_ranges::legacy_fold_cond_overflow().

overflow_comparison_p_1()

static bool overflow_comparison_p_1 ( enum tree_code code, tree op0, tree op1, bool reversed, tree * new_cst )

static

Helper for overflow_comparison_p

OP0 CODE OP1 is a comparison.  Examine the comparison and potentially
OP1's defining statement to see if it ultimately has the form
OP0 CODE (OP0 PLUS INTEGER_CST)

If so, return TRUE indicating this is an overflow test and store into
*NEW_CST an updated constant that can be used in a narrowed range test.

REVERSED indicates if the comparison was originally:

OP1 CODE' OP0.

This affects how we build the updated constant.   

References ggc_alloc(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), integer_zerop(), INTEGRAL_TYPE_P, is_gimple_assign(), wi::max_value(), SSA_NAME_DEF_STMT, wi::to_wide(), TREE_CODE, TREE_TYPE, TYPE_OVERFLOW_WRAPS, TYPE_PRECISION, TYPE_UNSIGNED, UNSIGNED, and wide_int_to_tree().

Referenced by overflow_comparison_p().