#include "config.h"#include "system.h"#include "coretypes.h"#include "tm.h"#include "basic-block.h"#include "tree.h"#include "gimple-pretty-print.h"#include "gimple.h"#include "gimple-ssa.h"#include "tree-cfg.h"#include "tree-ssanames.h"#include "tree-into-ssa.h"#include "tree-pass.h"#include "flags.h"
Data Structures | |
| struct | input_domain |
Macros | |
| #define | MAX_BASE_INT_BIT_SIZE 32 |
| #define | ERR_PROB 0.01 |
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 () |
Macro Definition Documentation
| #define ERR_PROB 0.01 |
Probability of the branch (to the call) is taken.
| #define MAX_BASE_INT_BIT_SIZE 32 |
A helper function to help select calls to pow that are suitable for conditional DCE transformation. It looks for pow calls that can be guided with simple conditions. Such calls either have constant base values or base values converted from integers. Returns true if the pow call POW_CALL is a candidate. The maximum integer bit size for base argument of a pow call that is suitable for shrink-wrapping transformation.
Referenced by gen_conditions_for_pow_cst_base(), and gen_conditions_for_pow_int_base().
Typedef Documentation
| typedef struct input_domain inp_domain |
Conditional Dead Call Elimination pass for the GNU compiler. Copyright (C) 2008-2013 Free Software Foundation, Inc. Contributed by Xinliang David Li davidxl@google.com
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 |
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 BUILT_IN_NORMAL, DECL_BUILT_IN, DECL_BUILT_IN_CLASS, gimple_call_fndecl(), and gimple_call_lhs().
|
static |
Folding candidates are not interesting. Can actually assert that it is already folded.
Only handle a fixed range of constant.
Only handles cases where base value is converted
from integer values. If the type of the base is too wide,
the resulting shrink wrapping condition
will be too conservative.
|
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.
For long double, we can not really check XFmode which is only defined on intel platforms. Candidate pre-selection using builtin function code guarantees that we are checking formats for long double modes: double, quad, and extended.
|
static |
The limit constants used in the implementation assume IEEE floating point format. Other formats can be supported in the future if needed.
Referenced by tree_call_cdce().
|
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.
Now push a separator.
|
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 CASE_FLT_FN, and get_domain().
|
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.
Validate the range of the base constant to make sure it is consistent with check_pow.
References gcc_assert, gimple_assign_rhs1(), MAX_BASE_INT_BIT_SIZE, SSA_NAME_DEF_STMT, TREE_TYPE, and TYPE_PRECISION.
|
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.
Determine the max exp argument value according to the size of the base integer. The max exp value is conservatively estimated assuming IEEE754 double precision format.
For pow ((double)x, y), generate the following conditions: cond 1: temp1 = x; if (temp1 <= 0) cond 2: temp2 = y; if (temp2 > max_exp_real_cst)
Generate condition in reverse order – first the condition for the exp argument.
Now generate condition for the base argument. Note it does not use the helper function gen_conditions_for_domain because the base type is integer.
Push a separator.
References gcc_assert, and MAX_BASE_INT_BIT_SIZE.
|
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.
|
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.
|
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.
Referenced by gen_conditions_for_pow().
|
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.
Trig functions: return [-1, +1]
Hyperbolic functions.
acosh: [1, +inf)
atanh: (-1, +1)
coshf: (-89, +89)
cosh: (-710, +710)
Log functions: (0, +inf)
Exp functions.
expf: (-inf, 88)
exp: (-inf, 709)
exp2f: (-inf, 128)
exp2: (-inf, 1024)
exp10f: (-inf, 38)
exp10: (-inf, 308)
sqrt: [0, +inf)
|
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.
Only potentially dead calls are considered.
Trig functions.
Hyperbolic functions.
Log functions.
Exp functions.
Sqrt.
Special one: two argument pow.
| gimple_opt_pass* make_pass_call_cdce | ( | ) |
|
static |
The top level function for conditional dead code shrink wrapping transformation.
|
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.
This can happen if the condition generator decides it is not beneficial to do the transformation. Just return false and do not do any transformation for the call.
Now find the join target bb – split bi_call_bb if needed.
If the call must be the last in the bb, don't split the block,
it could e.g. have EH edges. Now it is time to insert the first conditional expression into bi_call_bb and split this bb so that bi_call is shrink-wrapped.
Now the label.
Code generation for the rest of the conditions
References gcc_assert, gsi_insert_before(), and GSI_SAME_STMT.
|
static |
Pass entry points.
Collect dead call candidates.
As we introduced new control-flow we need to insert PHI-nodes
for the call-clobbers of the remaining call.
References execute(), gate_call_cdce(), GIMPLE_PASS, OPTGROUP_NONE, PROP_cfg, PROP_ssa, and TODO_verify_ssa.
