Data Structures
struct	input_domain

Typedefs
typedef struct input_domain	inp_domain

Functions
static inp_domain	get_domain (int lb, bool has_lb, bool lb_inclusive, int ub, bool has_ub, bool ub_inclusive)
static bool	check_target_format ()
static bool	check_pow ()
static bool	check_builtin_call ()
static bool	is_call_dce_candidate ()
static void	gen_one_condition (tree arg, int lbub, enum tree_code tcode, const char temp_name1, const char temp_name2, vec< gimple > conds, unsigned *nconds)
static void	gen_conditions_for_domain (tree arg, inp_domain domain, vec< gimple > conds, unsigned *nconds)
static void	gen_conditions_for_pow_cst_base (tree base, tree expn, vec< gimple > conds, unsigned *nconds)
static void	gen_conditions_for_pow_int_base (tree base, tree expn, vec< gimple > conds, unsigned *nconds)
static void	gen_conditions_for_pow (gimple pow_call, vec< gimple > conds, unsigned *nconds)
static inp_domain	get_no_error_domain ()
static void	gen_shrink_wrap_conditions (gimple bi_call, vec< gimple > conds, unsigned int *nconds)
static bool	shrink_wrap_one_built_in_call ()
static bool	shrink_wrap_conditional_dead_built_in_calls ()
static unsigned int	tree_call_cdce ()
static bool	gate_call_cdce ()
gimple_opt_pass *	make_pass_call_cdce ()

Typedef Documentation

typedef struct input_domain inp_domain

@verbatim Conditional Dead Call Elimination pass for the GNU compiler.

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

Conditional dead call elimination

   Some builtin functions can set errno on error conditions, but they
   are otherwise pure.  If the result of a call to such a function is
   not used, the compiler can still not eliminate the call without
   powerful interprocedural analysis to prove that the errno is not
   checked.  However, if the conditions under which the error occurs
   are known, the compiler can conditionally dead code eliminate the
   calls by shrink-wrapping the semi-dead calls into the error condition:

        built_in_call (args)
          ==>
        if (error_cond (args))
             built_in_call (args)

    An actual simple example is :
         log (x);   // Mostly dead call
     ==>
         if (x < 0)
             log (x);
     With this change, call to log (x) is effectively eliminated, as
     in majority of the cases, log won't be called with x out of
     range.  The branch is totally predictable, so the branch cost
     is low.

   Note that library functions are not supposed to clear errno to zero without
   error.  See IEEE Std 1003.1, section 2.3 Error Numbers, and section 7.5:3 of
   ISO/IEC 9899 (C99).

   The condition wrapping the builtin call is conservatively set to avoid too
   aggressive (wrong) shrink wrapping.  The optimization is called conditional
   dead call elimination because the call is eliminated under the condition
   that the input arguments would not lead to domain or range error (for
   instance when x <= 0 for a log (x) call), however the chances that the error
   condition is hit is very low (those builtin calls which are conditionally
   dead are usually part of the C++ abstraction penalty exposed after
   inlining).

A structure for representing input domain of
   a function argument in integer.  If the lower
   bound is -inf, has_lb is set to false.  If the
   upper bound is +inf, has_ub is false.
   is_lb_inclusive and is_ub_inclusive are flags
   to indicate if lb and ub value are inclusive
   respectively.

Function Documentation

static bool check_builtin_call ( )

static

A helper function to help select candidate function calls that are
   suitable for conditional DCE.  Candidate functions must have single
   valid input domain in this implementation except for pow (see check_pow).
   Returns true if the function call is a candidate.

References check_target_format(), and gimple_call_arg().

Referenced by is_call_dce_candidate().

static bool check_pow ( )

static

References check_target_format(), dconst1, gimple_assign_rhs1(), gimple_assign_rhs_code(), gimple_call_arg(), gimple_call_num_args(), real_from_integer(), and type().

Referenced by gen_conditions_for_pow(), and is_call_dce_candidate().

static bool check_target_format ( )

static

A helper function to check the target format for the
   argument type. In this implementation, only IEEE formats
   are supported.  ARG is the call argument to be checked.
   Returns true if the format is supported.  To support other
   target formats,  function get_no_error_domain needs to be
   enhanced to have range bounds properly computed. Since
   the check is cheap (very small number of candidates
   to be checked), the result is not cached for each float type.

References ieee_double_format, ieee_extended_intel_128_format, ieee_extended_intel_96_format, ieee_extended_intel_96_round_53_format, ieee_extended_motorola_format, ieee_quad_format, ieee_single_format, mips_double_format, mips_quad_format, mips_single_format, motorola_double_format, motorola_single_format, and type().

Referenced by check_builtin_call(), and check_pow().

static bool gate_call_cdce ( )

static

References cfun, and optimize_function_for_speed_p().

static void gen_conditions_for_domain	(	tree	arg,
		inp_domain	domain,
		vec< gimple >	conds,
		unsigned *	nconds
	)

static

A helper function to generate GIMPLE statements for
   out of input domain check.  ARG is the call argument
   to be runtime checked, DOMAIN holds the valid domain
   for the given function, CONDS points to the vector
   holding the result GIMPLE statements.  *NCONDS is
   the number of logical comparisons.  This function
   produces no more than two logical comparisons, one
   for lower bound check, one for upper bound check.

References gen_one_condition(), input_domain::has_lb, input_domain::has_ub, input_domain::is_lb_inclusive, input_domain::is_ub_inclusive, input_domain::lb, and input_domain::ub.

Referenced by gen_conditions_for_pow_cst_base(), gen_conditions_for_pow_int_base(), and gen_shrink_wrap_conditions().

static void gen_conditions_for_pow	(	gimple	pow_call,
		vec< gimple >	conds,
		unsigned *	nconds
	)

static

Method to generate conditional statements for guarding conditionally
   dead calls to pow.  One or more statements can be generated for
   each logical condition.  Statement groups of different conditions
   are separated by a NULL tree and they are stored in the vec
   conds.  The number of logical conditions are stored in *nconds.

   See C99 standard, 7.12.7.4:2, for description of pow (x, y).
   The precise condition for domain errors are complex.  In this
   implementation, a simplified (but conservative) valid domain
   for x and y are used: x is positive to avoid dom errors, while
   y is smaller than a upper bound (depending on x) to avoid range
   errors.  Runtime code is generated to check x (if not constant)
   and y against the valid domain.  If it is out, jump to the call,
   otherwise the call is bypassed.  POW_CALL is the call statement,
   *CONDS is a vector holding the resulting condition statements,
   and *NCONDS is the number of logical conditions.

References check_pow(), gen_conditions_for_pow_cst_base(), gen_conditions_for_pow_int_base(), and gimple_call_arg().

Referenced by gen_shrink_wrap_conditions().

static void gen_conditions_for_pow_cst_base	(	tree	base,
		tree	expn,
		vec< gimple >	conds,
		unsigned *	nconds
	)

static

A helper function to generate condition
   code for the y argument in call pow (some_const, y).
   See candidate selection in check_pow.  Since the
   candidates' base values have a limited range,
   the guarded code generated for y are simple:
   if (y > max_y)
     pow (const, y);
   Note max_y can be computed separately for each
   const base, but in this implementation, we
   choose to compute it using the max base
   in the allowed range for the purpose of
   simplicity.  BASE is the constant base value,
   EXPN is the expression for the exponent argument,
   *CONDS is the vector to hold resulting statements,
   and *NCONDS is the number of logical conditions.

References dconst1, gen_conditions_for_domain(), get_domain(), and real_from_integer().

Referenced by gen_conditions_for_pow().

static void gen_conditions_for_pow_int_base	(	tree	base,
		tree	expn,
		vec< gimple >	conds,
		unsigned *	nconds
	)

static

Generate error condition code for pow calls with
   non constant base values.  The candidates selected
   have their base argument value converted from
   integer (see check_pow) value (1, 2, 4 bytes), and
   the max exp value is computed based on the size
   of the integer type (i.e. max possible base value).
   The resulting input domain for exp argument is thus
   conservative (smaller than the max value allowed by
   the runtime value of the base).  BASE is the integer
   base value, EXPN is the expression for the exponent
   argument, *CONDS is the vector to hold resulting
   statements, and *NCONDS is the number of logical
   conditions.

References build_int_cst(), create_tmp_var(), gen_conditions_for_domain(), get_domain(), gimple_assign_rhs1(), gimple_assign_set_lhs(), gimple_build_cond(), and make_ssa_name().

Referenced by gen_conditions_for_pow().

static void gen_one_condition	(	tree	arg,
		int	lbub,
		enum tree_code	tcode,
		const char *	temp_name1,
		const char *	temp_name2,
		vec< gimple >	conds,
		unsigned *	nconds
	)

static

A helper function to generate gimple statements for
   one bound comparison.  ARG is the call argument to
   be compared with the bound, LBUB is the bound value
   in integer, TCODE is the tree_code of the comparison,
   TEMP_NAME1/TEMP_NAME2 are names of the temporaries,
   CONDS is a vector holding the produced GIMPLE statements,
   and NCONDS points to the variable holding the number
   of logical comparisons.  CONDS is either empty or
   a list ended with a null tree.

References build_int_cst(), build_real_from_int_cst(), create_tmp_var(), gimple_assign_set_lhs(), gimple_build_cond_from_tree(), and make_ssa_name().

Referenced by gen_conditions_for_domain().

static void gen_shrink_wrap_conditions	(	gimple	bi_call,
		vec< gimple >	conds,
		unsigned int *	nconds
	)

static

The function to generate shrink wrap conditions for a partially
   dead builtin call whose return value is not used anywhere,
   but has to be kept live due to potential error condition.
   BI_CALL is the builtin call, CONDS is the vector of statements
   for condition code, NCODES is the pointer to the number of
   logical conditions.  Statements belonging to different logical
   condition are separated by NULL tree in the vector.

References gen_conditions_for_domain(), gen_conditions_for_pow(), get_no_error_domain(), gimple_call_arg(), gimple_call_fndecl(), and is_gimple_call().

Referenced by shrink_wrap_one_built_in_call().

static inp_domain get_domain	(	int	lb,
		bool	has_lb,
		bool	lb_inclusive,
		int	ub,
		bool	has_ub,
		bool	ub_inclusive
	)

static

A helper function to construct and return an input
   domain object.  LB is the lower bound, HAS_LB is
   a boolean flag indicating if the lower bound exists,
   and LB_INCLUSIVE is a boolean flag indicating if the
   lower bound is inclusive or not.  UB, HAS_UB, and
   UB_INCLUSIVE have the same meaning, but for upper
   bound of the domain.

References input_domain::has_lb, input_domain::has_ub, input_domain::is_lb_inclusive, input_domain::is_ub_inclusive, input_domain::lb, and input_domain::ub.

Referenced by gen_conditions_for_pow_cst_base(), gen_conditions_for_pow_int_base(), and get_no_error_domain().

static inp_domain get_no_error_domain ( )

static

A helper routine to help computing the valid input domain
   for a builtin function.  See C99 7.12.7 for details.  In this
   implementation, we only handle single region domain.  The
   resulting region can be conservative (smaller) than the actual
   one and rounded to integers.  Some of the bounds are documented
   in the standard, while other limit constants are computed
   assuming IEEE floating point format (for SF and DF modes).
   Since IEEE only sets minimum requirements for long double format,
   different long double formats exist under different implementations
   (e.g, 64 bit double precision (DF), 80 bit double-extended
   precision (XF), and 128 bit quad precision (QF) ).  For simplicity,
   in this implementation, the computed bounds for long double assume
   64 bit format (DF), and are therefore conservative.  Another
   assumption is that single precision float type is always SF mode,
   and double type is DF mode.  This function is quite
   implementation specific, so it may not be suitable to be part of
   builtins.c.  This needs to be revisited later to see if it can
   be leveraged in x87 assembly expansion.

References get_domain().

Referenced by gen_shrink_wrap_conditions().

static bool is_call_dce_candidate ( )

static

A helper function to determine if a builtin function call is a
   candidate for conditional DCE.  Returns true if the builtin call
   is a candidate.

References BUILT_IN_NORMAL, check_builtin_call(), check_pow(), gimple_call_fndecl(), and gimple_call_lhs().

Referenced by tree_call_cdce().

gimple_opt_pass* make_pass_call_cdce ( )

static bool shrink_wrap_conditional_dead_built_in_calls ( )

static

The top level function for conditional dead code shrink
   wrapping transformation.

References changed, and shrink_wrap_one_built_in_call().

Referenced by tree_call_cdce().

static bool shrink_wrap_one_built_in_call ( )

static

The function to shrink wrap a partially dead builtin call
   whose return value is not used anywhere, but has to be kept
   live due to potential error condition.  Returns true if the
   transformation actually happens.

References apply_probability(), edge_def::count, basic_block_def::count, create_artificial_label(), edge_def::dest, dump_file, dump_flags, find_fallthru_edge(), edge_def::flags, gen_shrink_wrap_conditions(), gimple_bb(), gimple_build_label(), gimple_location(), gsi_for_stmt(), gsi_insert_before(), GSI_SAME_STMT, inverse_probability(), make_edge(), edge_def::probability, split_block(), stmt_ends_bb_p(), and basic_block_def::succs.

Referenced by shrink_wrap_conditional_dead_built_in_calls().

static unsigned int tree_call_cdce ( )

static

Pass entry points.

References CDI_DOMINATORS, CDI_POST_DOMINATORS, cfun, dump_file, dump_flags, free_dominance_info(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_stmt(), is_call_dce_candidate(), is_gimple_call(), mark_virtual_operands_for_renaming(), print_gimple_stmt(), shrink_wrap_conditional_dead_built_in_calls(), and vNULL.

Data Structures

Typedefs

Functions

Typedef Documentation

Function Documentation