0
|
1 /* Conditional Dead Call Elimination pass for the GNU compiler.
|
|
2 Copyright (C) 2008
|
|
3 Free Software Foundation, Inc.
|
|
4 Contributed by Xinliang David Li <davidxl@google.com>
|
|
5
|
|
6 This file is part of GCC.
|
|
7
|
|
8 GCC is free software; you can redistribute it and/or modify it
|
|
9 under the terms of the GNU General Public License as published by the
|
|
10 Free Software Foundation; either version 3, or (at your option) any
|
|
11 later version.
|
|
12
|
|
13 GCC is distributed in the hope that it will be useful, but WITHOUT
|
|
14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
|
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
16 for more details.
|
|
17
|
|
18 You should have received a copy of the GNU General Public License
|
|
19 along with GCC; see the file COPYING3. If not see
|
|
20 <http://www.gnu.org/licenses/>. */
|
|
21
|
|
22 #include "config.h"
|
|
23 #include "system.h"
|
|
24 #include "coretypes.h"
|
|
25 #include "tm.h"
|
|
26 #include "ggc.h"
|
|
27
|
|
28 /* These RTL headers are needed for basic-block.h. */
|
|
29 #include "rtl.h"
|
|
30 #include "tm_p.h"
|
|
31 #include "hard-reg-set.h"
|
|
32 #include "obstack.h"
|
|
33 #include "basic-block.h"
|
|
34
|
|
35 #include "tree.h"
|
|
36 #include "diagnostic.h"
|
|
37 #include "tree-flow.h"
|
|
38 #include "gimple.h"
|
|
39 #include "tree-dump.h"
|
|
40 #include "tree-pass.h"
|
|
41 #include "timevar.h"
|
|
42 #include "flags.h"
|
|
43
|
|
44
|
|
45 /* Conditional dead call elimination
|
|
46
|
|
47 Some builtin functions can set errno on error conditions, but they
|
|
48 are otherwise pure. If the result of a call to such a function is
|
|
49 not used, the compiler can still not eliminate the call without
|
|
50 powerful interprocedural analysis to prove that the errno is not
|
|
51 checked. However, if the conditions under which the error occurs
|
|
52 are known, the compiler can conditionally dead code eliminate the
|
|
53 calls by shrink-wrapping the semi-dead calls into the error condition:
|
|
54
|
|
55 built_in_call (args)
|
|
56 ==>
|
|
57 if (error_cond (args))
|
|
58 built_in_call (args)
|
|
59
|
|
60 An actual simple example is :
|
|
61 log (x); // Mostly dead call
|
|
62 ==>
|
|
63 if (x < 0)
|
|
64 log (x);
|
|
65 With this change, call to log (x) is effectively eliminated, as
|
|
66 in majority of the cases, log won't be called with x out of
|
|
67 range. The branch is totally predictable, so the branch cost
|
|
68 is low.
|
|
69
|
|
70 Note that library functions are not supposed to clear errno to zero without
|
|
71 error. See IEEE Std 1003.1, section 2.3 Error Numbers, and section 7.5:3 of
|
|
72 ISO/IEC 9899 (C99).
|
|
73
|
|
74 The condition wrapping the builtin call is conservatively set to avoid too
|
|
75 aggressive (wrong) shrink wrapping. The optimization is called conditional
|
|
76 dead call elimination because the call is eliminated under the condition
|
|
77 that the input arguments would not lead to domain or range error (for
|
|
78 instance when x <= 0 for a log (x) call), however the chances that the error
|
|
79 condition is hit is very low (those builtin calls which are conditionally
|
|
80 dead are usually part of the C++ abstraction penalty exposed after
|
|
81 inlining). */
|
|
82
|
|
83
|
|
84 /* A structure for representing input domain of
|
|
85 a function argument in integer. If the lower
|
|
86 bound is -inf, has_lb is set to false. If the
|
|
87 upper bound is +inf, has_ub is false.
|
|
88 is_lb_inclusive and is_ub_inclusive are flags
|
|
89 to indicate if lb and ub value are inclusive
|
|
90 respectively. */
|
|
91
|
|
92 typedef struct input_domain
|
|
93 {
|
|
94 int lb;
|
|
95 int ub;
|
|
96 bool has_lb;
|
|
97 bool has_ub;
|
|
98 bool is_lb_inclusive;
|
|
99 bool is_ub_inclusive;
|
|
100 } inp_domain;
|
|
101
|
|
102 /* A helper function to construct and return an input
|
|
103 domain object. LB is the lower bound, HAS_LB is
|
|
104 a boolean flag indicating if the lower bound exists,
|
|
105 and LB_INCLUSIVE is a boolean flag indicating if the
|
|
106 lower bound is inclusive or not. UB, HAS_UB, and
|
|
107 UB_INCLUSIVE have the same meaning, but for upper
|
|
108 bound of the domain. */
|
|
109
|
|
110 static inp_domain
|
|
111 get_domain (int lb, bool has_lb, bool lb_inclusive,
|
|
112 int ub, bool has_ub, bool ub_inclusive)
|
|
113 {
|
|
114 inp_domain domain;
|
|
115 domain.lb = lb;
|
|
116 domain.has_lb = has_lb;
|
|
117 domain.is_lb_inclusive = lb_inclusive;
|
|
118 domain.ub = ub;
|
|
119 domain.has_ub = has_ub;
|
|
120 domain.is_ub_inclusive = ub_inclusive;
|
|
121 return domain;
|
|
122 }
|
|
123
|
|
124 /* A helper function to check the target format for the
|
|
125 argument type. In this implementation, only IEEE formats
|
|
126 are supported. ARG is the call argument to be checked.
|
|
127 Returns true if the format is supported. To support other
|
|
128 target formats, function get_no_error_domain needs to be
|
|
129 enhanced to have range bounds properly computed. Since
|
|
130 the check is cheap (very small number of candidates
|
|
131 to be checked), the result is not cached for each float type. */
|
|
132
|
|
133 static bool
|
|
134 check_target_format (tree arg)
|
|
135 {
|
|
136 tree type;
|
|
137 enum machine_mode mode;
|
|
138 const struct real_format *rfmt;
|
|
139
|
|
140 type = TREE_TYPE (arg);
|
|
141 mode = TYPE_MODE (type);
|
|
142 rfmt = REAL_MODE_FORMAT (mode);
|
|
143 if ((mode == SFmode
|
|
144 && (rfmt == &ieee_single_format || rfmt == &mips_single_format
|
|
145 || rfmt == &motorola_single_format))
|
|
146 || (mode == DFmode
|
|
147 && (rfmt == &ieee_double_format || rfmt == &mips_double_format
|
|
148 || rfmt == &motorola_double_format))
|
|
149 /* For long double, we can not really check XFmode
|
|
150 which is only defined on intel platforms.
|
|
151 Candidate pre-selection using builtin function
|
|
152 code guarantees that we are checking formats
|
|
153 for long double modes: double, quad, and extended. */
|
|
154 || (mode != SFmode && mode != DFmode
|
|
155 && (rfmt == &ieee_quad_format
|
|
156 || rfmt == &mips_quad_format
|
|
157 || rfmt == &ieee_extended_motorola_format
|
|
158 || rfmt == &ieee_extended_intel_96_format
|
|
159 || rfmt == &ieee_extended_intel_128_format
|
|
160 || rfmt == &ieee_extended_intel_96_round_53_format)))
|
|
161 return true;
|
|
162
|
|
163 return false;
|
|
164 }
|
|
165
|
|
166
|
|
167 /* A helper function to help select calls to pow that are suitable for
|
|
168 conditional DCE transformation. It looks for pow calls that can be
|
|
169 guided with simple conditions. Such calls either have constant base
|
|
170 values or base values converted from integers. Returns true if
|
|
171 the pow call POW_CALL is a candidate. */
|
|
172
|
|
173 /* The maximum integer bit size for base argument of a pow call
|
|
174 that is suitable for shrink-wrapping transformation. */
|
|
175 #define MAX_BASE_INT_BIT_SIZE 32
|
|
176
|
|
177 static bool
|
|
178 check_pow (gimple pow_call)
|
|
179 {
|
|
180 tree base, expn;
|
|
181 enum tree_code bc, ec;
|
|
182
|
|
183 if (gimple_call_num_args (pow_call) != 2)
|
|
184 return false;
|
|
185
|
|
186 base = gimple_call_arg (pow_call, 0);
|
|
187 expn = gimple_call_arg (pow_call, 1);
|
|
188
|
|
189 if (!check_target_format (expn))
|
|
190 return false;
|
|
191
|
|
192 bc = TREE_CODE (base);
|
|
193 ec = TREE_CODE (expn);
|
|
194
|
|
195 /* Folding candidates are not interesting.
|
|
196 Can actually assert that it is already folded. */
|
|
197 if (ec == REAL_CST && bc == REAL_CST)
|
|
198 return false;
|
|
199
|
|
200 if (bc == REAL_CST)
|
|
201 {
|
|
202 /* Only handle a fixed range of constant. */
|
|
203 REAL_VALUE_TYPE mv;
|
|
204 REAL_VALUE_TYPE bcv = TREE_REAL_CST (base);
|
|
205 if (REAL_VALUES_EQUAL (bcv, dconst1))
|
|
206 return false;
|
|
207 if (REAL_VALUES_LESS (bcv, dconst1))
|
|
208 return false;
|
|
209 real_from_integer (&mv, TYPE_MODE (TREE_TYPE (base)), 256, 0, 1);
|
|
210 if (REAL_VALUES_LESS (mv, bcv))
|
|
211 return false;
|
|
212 return true;
|
|
213 }
|
|
214 else if (bc == SSA_NAME)
|
|
215 {
|
|
216 tree base_val0, base_var, type;
|
|
217 gimple base_def;
|
|
218 int bit_sz;
|
|
219
|
|
220 /* Only handles cases where base value is converted
|
|
221 from integer values. */
|
|
222 base_def = SSA_NAME_DEF_STMT (base);
|
|
223 if (gimple_code (base_def) != GIMPLE_ASSIGN)
|
|
224 return false;
|
|
225
|
|
226 if (gimple_assign_rhs_code (base_def) != FLOAT_EXPR)
|
|
227 return false;
|
|
228 base_val0 = gimple_assign_rhs1 (base_def);
|
|
229
|
|
230 base_var = SSA_NAME_VAR (base_val0);
|
|
231 if (!DECL_P (base_var))
|
|
232 return false;
|
|
233
|
|
234 type = TREE_TYPE (base_var);
|
|
235 if (TREE_CODE (type) != INTEGER_TYPE)
|
|
236 return false;
|
|
237 bit_sz = TYPE_PRECISION (type);
|
|
238 /* If the type of the base is too wide,
|
|
239 the resulting shrink wrapping condition
|
|
240 will be too conservative. */
|
|
241 if (bit_sz > MAX_BASE_INT_BIT_SIZE)
|
|
242 return false;
|
|
243
|
|
244 return true;
|
|
245 }
|
|
246 else
|
|
247 return false;
|
|
248 }
|
|
249
|
|
250 /* A helper function to help select candidate function calls that are
|
|
251 suitable for conditional DCE. Candidate functions must have single
|
|
252 valid input domain in this implementation except for pow (see check_pow).
|
|
253 Returns true if the function call is a candidate. */
|
|
254
|
|
255 static bool
|
|
256 check_builtin_call (gimple bcall)
|
|
257 {
|
|
258 tree arg;
|
|
259
|
|
260 arg = gimple_call_arg (bcall, 0);
|
|
261 return check_target_format (arg);
|
|
262 }
|
|
263
|
|
264 /* A helper function to determine if a builtin function call is a
|
|
265 candidate for conditional DCE. Returns true if the builtin call
|
|
266 is a candidate. */
|
|
267
|
|
268 static bool
|
|
269 is_call_dce_candidate (gimple call)
|
|
270 {
|
|
271 tree fn;
|
|
272 enum built_in_function fnc;
|
|
273
|
|
274 /* Only potentially dead calls are considered. */
|
|
275 if (gimple_call_lhs (call))
|
|
276 return false;
|
|
277
|
|
278 fn = gimple_call_fndecl (call);
|
|
279 if (!fn
|
|
280 || !DECL_BUILT_IN (fn)
|
|
281 || (DECL_BUILT_IN_CLASS (fn) != BUILT_IN_NORMAL))
|
|
282 return false;
|
|
283
|
|
284 fnc = DECL_FUNCTION_CODE (fn);
|
|
285 switch (fnc)
|
|
286 {
|
|
287 /* Trig functions. */
|
|
288 CASE_FLT_FN (BUILT_IN_ACOS):
|
|
289 CASE_FLT_FN (BUILT_IN_ASIN):
|
|
290 /* Hyperbolic functions. */
|
|
291 CASE_FLT_FN (BUILT_IN_ACOSH):
|
|
292 CASE_FLT_FN (BUILT_IN_ATANH):
|
|
293 CASE_FLT_FN (BUILT_IN_COSH):
|
|
294 CASE_FLT_FN (BUILT_IN_SINH):
|
|
295 /* Log functions. */
|
|
296 CASE_FLT_FN (BUILT_IN_LOG):
|
|
297 CASE_FLT_FN (BUILT_IN_LOG2):
|
|
298 CASE_FLT_FN (BUILT_IN_LOG10):
|
|
299 CASE_FLT_FN (BUILT_IN_LOG1P):
|
|
300 /* Exp functions. */
|
|
301 CASE_FLT_FN (BUILT_IN_EXP):
|
|
302 CASE_FLT_FN (BUILT_IN_EXP2):
|
|
303 CASE_FLT_FN (BUILT_IN_EXP10):
|
|
304 CASE_FLT_FN (BUILT_IN_EXPM1):
|
|
305 CASE_FLT_FN (BUILT_IN_POW10):
|
|
306 /* Sqrt. */
|
|
307 CASE_FLT_FN (BUILT_IN_SQRT):
|
|
308 return check_builtin_call (call);
|
|
309 /* Special one: two argument pow. */
|
|
310 case BUILT_IN_POW:
|
|
311 return check_pow (call);
|
|
312 default:
|
|
313 break;
|
|
314 }
|
|
315
|
|
316 return false;
|
|
317 }
|
|
318
|
|
319
|
|
320 /* A helper function to generate gimple statements for
|
|
321 one bound comparison. ARG is the call argument to
|
|
322 be compared with the bound, LBUB is the bound value
|
|
323 in integer, TCODE is the tree_code of the comparison,
|
|
324 TEMP_NAME1/TEMP_NAME2 are names of the temporaries,
|
|
325 CONDS is a vector holding the produced GIMPLE statements,
|
|
326 and NCONDS points to the variable holding the number
|
|
327 of logical comparisons. CONDS is either empty or
|
|
328 a list ended with a null tree. */
|
|
329
|
|
330 static void
|
|
331 gen_one_condition (tree arg, int lbub,
|
|
332 enum tree_code tcode,
|
|
333 const char *temp_name1,
|
|
334 const char *temp_name2,
|
|
335 VEC (gimple, heap) *conds,
|
|
336 unsigned *nconds)
|
|
337 {
|
|
338 tree lbub_real_cst, lbub_cst, float_type;
|
|
339 tree temp, tempn, tempc, tempcn;
|
|
340 gimple stmt1, stmt2, stmt3;
|
|
341
|
|
342 float_type = TREE_TYPE (arg);
|
|
343 lbub_cst = build_int_cst (integer_type_node, lbub);
|
|
344 lbub_real_cst = build_real_from_int_cst (float_type, lbub_cst);
|
|
345
|
|
346 temp = create_tmp_var (float_type, temp_name1);
|
|
347 stmt1 = gimple_build_assign (temp, arg);
|
|
348 tempn = make_ssa_name (temp, stmt1);
|
|
349 gimple_assign_set_lhs (stmt1, tempn);
|
|
350
|
|
351 tempc = create_tmp_var (boolean_type_node, temp_name2);
|
|
352 stmt2 = gimple_build_assign (tempc,
|
|
353 fold_build2 (tcode,
|
|
354 boolean_type_node,
|
|
355 tempn, lbub_real_cst));
|
|
356 tempcn = make_ssa_name (tempc, stmt2);
|
|
357 gimple_assign_set_lhs (stmt2, tempcn);
|
|
358
|
|
359 stmt3 = gimple_build_cond_from_tree (tempcn, NULL_TREE, NULL_TREE);
|
|
360 VEC_quick_push (gimple, conds, stmt1);
|
|
361 VEC_quick_push (gimple, conds, stmt2);
|
|
362 VEC_quick_push (gimple, conds, stmt3);
|
|
363 (*nconds)++;
|
|
364 }
|
|
365
|
|
366 /* A helper function to generate GIMPLE statements for
|
|
367 out of input domain check. ARG is the call argument
|
|
368 to be runtime checked, DOMAIN holds the valid domain
|
|
369 for the given function, CONDS points to the vector
|
|
370 holding the result GIMPLE statements. *NCONDS is
|
|
371 the number of logical comparisons. This function
|
|
372 produces no more than two logical comparisons, one
|
|
373 for lower bound check, one for upper bound check. */
|
|
374
|
|
375 static void
|
|
376 gen_conditions_for_domain (tree arg, inp_domain domain,
|
|
377 VEC (gimple, heap) *conds,
|
|
378 unsigned *nconds)
|
|
379 {
|
|
380 if (domain.has_lb)
|
|
381 gen_one_condition (arg, domain.lb,
|
|
382 (domain.is_lb_inclusive
|
|
383 ? LT_EXPR : LE_EXPR),
|
|
384 "DCE_COND_LB", "DCE_COND_LB_TEST",
|
|
385 conds, nconds);
|
|
386
|
|
387 if (domain.has_ub)
|
|
388 {
|
|
389 /* Now push a separator. */
|
|
390 if (domain.has_lb)
|
|
391 VEC_quick_push (gimple, conds, NULL);
|
|
392
|
|
393 gen_one_condition (arg, domain.ub,
|
|
394 (domain.is_ub_inclusive
|
|
395 ? GT_EXPR : GE_EXPR),
|
|
396 "DCE_COND_UB", "DCE_COND_UB_TEST",
|
|
397 conds, nconds);
|
|
398 }
|
|
399 }
|
|
400
|
|
401
|
|
402 /* A helper function to generate condition
|
|
403 code for the y argument in call pow (some_const, y).
|
|
404 See candidate selection in check_pow. Since the
|
|
405 candidates' base values have a limited range,
|
|
406 the guarded code generated for y are simple:
|
|
407 if (y > max_y)
|
|
408 pow (const, y);
|
|
409 Note max_y can be computed separately for each
|
|
410 const base, but in this implementation, we
|
|
411 choose to compute it using the max base
|
|
412 in the allowed range for the purpose of
|
|
413 simplicity. BASE is the constant base value,
|
|
414 EXPN is the expression for the exponent argument,
|
|
415 *CONDS is the vector to hold resulting statements,
|
|
416 and *NCONDS is the number of logical conditions. */
|
|
417
|
|
418 static void
|
|
419 gen_conditions_for_pow_cst_base (tree base, tree expn,
|
|
420 VEC (gimple, heap) *conds,
|
|
421 unsigned *nconds)
|
|
422 {
|
|
423 inp_domain exp_domain;
|
|
424 /* Validate the range of the base constant to make
|
|
425 sure it is consistent with check_pow. */
|
|
426 REAL_VALUE_TYPE mv;
|
|
427 REAL_VALUE_TYPE bcv = TREE_REAL_CST (base);
|
|
428 gcc_assert (!REAL_VALUES_EQUAL (bcv, dconst1)
|
|
429 && !REAL_VALUES_LESS (bcv, dconst1));
|
|
430 real_from_integer (&mv, TYPE_MODE (TREE_TYPE (base)), 256, 0, 1);
|
|
431 gcc_assert (!REAL_VALUES_LESS (mv, bcv));
|
|
432
|
|
433 exp_domain = get_domain (0, false, false,
|
|
434 127, true, false);
|
|
435
|
|
436 gen_conditions_for_domain (expn, exp_domain,
|
|
437 conds, nconds);
|
|
438 }
|
|
439
|
|
440 /* Generate error condition code for pow calls with
|
|
441 non constant base values. The candidates selected
|
|
442 have their base argument value converted from
|
|
443 integer (see check_pow) value (1, 2, 4 bytes), and
|
|
444 the max exp value is computed based on the size
|
|
445 of the integer type (i.e. max possible base value).
|
|
446 The resulting input domain for exp argument is thus
|
|
447 conservative (smaller than the max value allowed by
|
|
448 the runtime value of the base). BASE is the integer
|
|
449 base value, EXPN is the expression for the exponent
|
|
450 argument, *CONDS is the vector to hold resulting
|
|
451 statements, and *NCONDS is the number of logical
|
|
452 conditions. */
|
|
453
|
|
454 static void
|
|
455 gen_conditions_for_pow_int_base (tree base, tree expn,
|
|
456 VEC (gimple, heap) *conds,
|
|
457 unsigned *nconds)
|
|
458 {
|
|
459 gimple base_def;
|
|
460 tree base_nm, base_val0;
|
|
461 tree base_var, int_type;
|
|
462 tree temp, tempn;
|
|
463 tree cst0;
|
|
464 gimple stmt1, stmt2;
|
|
465 int bit_sz, max_exp;
|
|
466 inp_domain exp_domain;
|
|
467
|
|
468 base_def = SSA_NAME_DEF_STMT (base);
|
|
469 base_nm = gimple_assign_lhs (base_def);
|
|
470 base_val0 = gimple_assign_rhs1 (base_def);
|
|
471 base_var = SSA_NAME_VAR (base_val0);
|
|
472 int_type = TREE_TYPE (base_var);
|
|
473 bit_sz = TYPE_PRECISION (int_type);
|
|
474 gcc_assert (bit_sz > 0
|
|
475 && bit_sz <= MAX_BASE_INT_BIT_SIZE);
|
|
476
|
|
477 /* Determine the max exp argument value according to
|
|
478 the size of the base integer. The max exp value
|
|
479 is conservatively estimated assuming IEEE754 double
|
|
480 precision format. */
|
|
481 if (bit_sz == 8)
|
|
482 max_exp = 128;
|
|
483 else if (bit_sz == 16)
|
|
484 max_exp = 64;
|
|
485 else
|
|
486 {
|
|
487 gcc_assert (bit_sz == MAX_BASE_INT_BIT_SIZE);
|
|
488 max_exp = 32;
|
|
489 }
|
|
490
|
|
491 /* For pow ((double)x, y), generate the following conditions:
|
|
492 cond 1:
|
|
493 temp1 = x;
|
|
494 if (temp1 <= 0)
|
|
495
|
|
496 cond 2:
|
|
497 temp2 = y;
|
|
498 if (temp2 > max_exp_real_cst) */
|
|
499
|
|
500 /* Generate condition in reverse order -- first
|
|
501 the condition for the exp argument. */
|
|
502
|
|
503 exp_domain = get_domain (0, false, false,
|
|
504 max_exp, true, true);
|
|
505
|
|
506 gen_conditions_for_domain (expn, exp_domain,
|
|
507 conds, nconds);
|
|
508
|
|
509 /* Now generate condition for the base argument.
|
|
510 Note it does not use the helper function
|
|
511 gen_conditions_for_domain because the base
|
|
512 type is integer. */
|
|
513
|
|
514 /* Push a separator. */
|
|
515 VEC_quick_push (gimple, conds, NULL);
|
|
516
|
|
517 temp = create_tmp_var (int_type, "DCE_COND1");
|
|
518 cst0 = build_int_cst (int_type, 0);
|
|
519 stmt1 = gimple_build_assign (temp, base_val0);
|
|
520 tempn = make_ssa_name (temp, stmt1);
|
|
521 gimple_assign_set_lhs (stmt1, tempn);
|
|
522 stmt2 = gimple_build_cond (LE_EXPR, tempn, cst0, NULL_TREE, NULL_TREE);
|
|
523
|
|
524 VEC_quick_push (gimple, conds, stmt1);
|
|
525 VEC_quick_push (gimple, conds, stmt2);
|
|
526 (*nconds)++;
|
|
527 }
|
|
528
|
|
529 /* Method to generate conditional statements for guarding conditionally
|
|
530 dead calls to pow. One or more statements can be generated for
|
|
531 each logical condition. Statement groups of different conditions
|
|
532 are separated by a NULL tree and they are stored in the VEC
|
|
533 conds. The number of logical conditions are stored in *nconds.
|
|
534
|
|
535 See C99 standard, 7.12.7.4:2, for description of pow (x, y).
|
|
536 The precise condition for domain errors are complex. In this
|
|
537 implementation, a simplified (but conservative) valid domain
|
|
538 for x and y are used: x is positive to avoid dom errors, while
|
|
539 y is smaller than a upper bound (depending on x) to avoid range
|
|
540 errors. Runtime code is generated to check x (if not constant)
|
|
541 and y against the valid domain. If it is out, jump to the call,
|
|
542 otherwise the call is bypassed. POW_CALL is the call statement,
|
|
543 *CONDS is a vector holding the resulting condition statements,
|
|
544 and *NCONDS is the number of logical conditions. */
|
|
545
|
|
546 static void
|
|
547 gen_conditions_for_pow (gimple pow_call, VEC (gimple, heap) *conds,
|
|
548 unsigned *nconds)
|
|
549 {
|
|
550 tree base, expn;
|
|
551 enum tree_code bc, ec;
|
|
552
|
|
553 #ifdef ENABLE_CHECKING
|
|
554 gcc_assert (check_pow (pow_call));
|
|
555 #endif
|
|
556
|
|
557 *nconds = 0;
|
|
558
|
|
559 base = gimple_call_arg (pow_call, 0);
|
|
560 expn = gimple_call_arg (pow_call, 1);
|
|
561
|
|
562 bc = TREE_CODE (base);
|
|
563 ec = TREE_CODE (expn);
|
|
564
|
|
565 if (bc == REAL_CST)
|
|
566 gen_conditions_for_pow_cst_base (base, expn, conds, nconds);
|
|
567 else if (bc == SSA_NAME)
|
|
568 gen_conditions_for_pow_int_base (base, expn, conds, nconds);
|
|
569 else
|
|
570 gcc_unreachable ();
|
|
571 }
|
|
572
|
|
573 /* A helper routine to help computing the valid input domain
|
|
574 for a builtin function. See C99 7.12.7 for details. In this
|
|
575 implementation, we only handle single region domain. The
|
|
576 resulting region can be conservative (smaller) than the actual
|
|
577 one and rounded to integers. Some of the bounds are documented
|
|
578 in the standard, while other limit constants are computed
|
|
579 assuming IEEE floating point format (for SF and DF modes).
|
|
580 Since IEEE only sets minimum requirements for long double format,
|
|
581 different long double formats exist under different implementations
|
|
582 (e.g, 64 bit double precision (DF), 80 bit double-extended
|
|
583 precision (XF), and 128 bit quad precision (QF) ). For simplicity,
|
|
584 in this implementation, the computed bounds for long double assume
|
|
585 64 bit format (DF), and are therefore conservative. Another
|
|
586 assumption is that single precision float type is always SF mode,
|
|
587 and double type is DF mode. This function is quite
|
|
588 implementation specific, so it may not be suitable to be part of
|
|
589 builtins.c. This needs to be revisited later to see if it can
|
|
590 be leveraged in x87 assembly expansion. */
|
|
591
|
|
592 static inp_domain
|
|
593 get_no_error_domain (enum built_in_function fnc)
|
|
594 {
|
|
595 switch (fnc)
|
|
596 {
|
|
597 /* Trig functions: return [-1, +1] */
|
|
598 CASE_FLT_FN (BUILT_IN_ACOS):
|
|
599 CASE_FLT_FN (BUILT_IN_ASIN):
|
|
600 return get_domain (-1, true, true,
|
|
601 1, true, true);
|
|
602 /* Hyperbolic functions. */
|
|
603 CASE_FLT_FN (BUILT_IN_ACOSH):
|
|
604 /* acosh: [1, +inf) */
|
|
605 return get_domain (1, true, true,
|
|
606 1, false, false);
|
|
607 CASE_FLT_FN (BUILT_IN_ATANH):
|
|
608 /* atanh: (-1, +1) */
|
|
609 return get_domain (-1, true, false,
|
|
610 1, true, false);
|
|
611 case BUILT_IN_COSHF:
|
|
612 case BUILT_IN_SINHF:
|
|
613 /* coshf: (-89, +89) */
|
|
614 return get_domain (-89, true, false,
|
|
615 89, true, false);
|
|
616 case BUILT_IN_COSH:
|
|
617 case BUILT_IN_SINH:
|
|
618 case BUILT_IN_COSHL:
|
|
619 case BUILT_IN_SINHL:
|
|
620 /* cosh: (-710, +710) */
|
|
621 return get_domain (-710, true, false,
|
|
622 710, true, false);
|
|
623 /* Log functions: (0, +inf) */
|
|
624 CASE_FLT_FN (BUILT_IN_LOG):
|
|
625 CASE_FLT_FN (BUILT_IN_LOG2):
|
|
626 CASE_FLT_FN (BUILT_IN_LOG10):
|
|
627 return get_domain (0, true, false,
|
|
628 0, false, false);
|
|
629 CASE_FLT_FN (BUILT_IN_LOG1P):
|
|
630 return get_domain (-1, true, false,
|
|
631 0, false, false);
|
|
632 /* Exp functions. */
|
|
633 case BUILT_IN_EXPF:
|
|
634 case BUILT_IN_EXPM1F:
|
|
635 /* expf: (-inf, 88) */
|
|
636 return get_domain (-1, false, false,
|
|
637 88, true, false);
|
|
638 case BUILT_IN_EXP:
|
|
639 case BUILT_IN_EXPM1:
|
|
640 case BUILT_IN_EXPL:
|
|
641 case BUILT_IN_EXPM1L:
|
|
642 /* exp: (-inf, 709) */
|
|
643 return get_domain (-1, false, false,
|
|
644 709, true, false);
|
|
645 case BUILT_IN_EXP2F:
|
|
646 /* exp2f: (-inf, 128) */
|
|
647 return get_domain (-1, false, false,
|
|
648 128, true, false);
|
|
649 case BUILT_IN_EXP2:
|
|
650 case BUILT_IN_EXP2L:
|
|
651 /* exp2: (-inf, 1024) */
|
|
652 return get_domain (-1, false, false,
|
|
653 1024, true, false);
|
|
654 case BUILT_IN_EXP10F:
|
|
655 case BUILT_IN_POW10F:
|
|
656 /* exp10f: (-inf, 38) */
|
|
657 return get_domain (-1, false, false,
|
|
658 38, true, false);
|
|
659 case BUILT_IN_EXP10:
|
|
660 case BUILT_IN_POW10:
|
|
661 case BUILT_IN_EXP10L:
|
|
662 case BUILT_IN_POW10L:
|
|
663 /* exp10: (-inf, 308) */
|
|
664 return get_domain (-1, false, false,
|
|
665 308, true, false);
|
|
666 /* sqrt: [0, +inf) */
|
|
667 CASE_FLT_FN (BUILT_IN_SQRT):
|
|
668 return get_domain (0, true, true,
|
|
669 0, false, false);
|
|
670 default:
|
|
671 gcc_unreachable ();
|
|
672 }
|
|
673
|
|
674 gcc_unreachable ();
|
|
675 }
|
|
676
|
|
677 /* The function to generate shrink wrap conditions for a partially
|
|
678 dead builtin call whose return value is not used anywhere,
|
|
679 but has to be kept live due to potential error condition.
|
|
680 BI_CALL is the builtin call, CONDS is the vector of statements
|
|
681 for condition code, NCODES is the pointer to the number of
|
|
682 logical conditions. Statements belonging to different logical
|
|
683 condition are separated by NULL tree in the vector. */
|
|
684
|
|
685 static void
|
|
686 gen_shrink_wrap_conditions (gimple bi_call, VEC (gimple, heap) *conds,
|
|
687 unsigned int *nconds)
|
|
688 {
|
|
689 gimple call;
|
|
690 tree fn;
|
|
691 enum built_in_function fnc;
|
|
692
|
|
693 gcc_assert (nconds && conds);
|
|
694 gcc_assert (VEC_length (gimple, conds) == 0);
|
|
695 gcc_assert (is_gimple_call (bi_call));
|
|
696
|
|
697 call = bi_call;
|
|
698 fn = gimple_call_fndecl (call);
|
|
699 gcc_assert (fn && DECL_BUILT_IN (fn));
|
|
700 fnc = DECL_FUNCTION_CODE (fn);
|
|
701 *nconds = 0;
|
|
702
|
|
703 if (fnc == BUILT_IN_POW)
|
|
704 gen_conditions_for_pow (call, conds, nconds);
|
|
705 else
|
|
706 {
|
|
707 tree arg;
|
|
708 inp_domain domain = get_no_error_domain (fnc);
|
|
709 *nconds = 0;
|
|
710 arg = gimple_call_arg (bi_call, 0);
|
|
711 gen_conditions_for_domain (arg, domain, conds, nconds);
|
|
712 }
|
|
713
|
|
714 return;
|
|
715 }
|
|
716
|
|
717
|
|
718 /* Probability of the branch (to the call) is taken. */
|
|
719 #define ERR_PROB 0.01
|
|
720
|
|
721 /* The function to shrink wrap a partially dead builtin call
|
|
722 whose return value is not used anywhere, but has to be kept
|
|
723 live due to potential error condition. Returns true if the
|
|
724 transformation actually happens. */
|
|
725
|
|
726 static bool
|
|
727 shrink_wrap_one_built_in_call (gimple bi_call)
|
|
728 {
|
|
729 gimple_stmt_iterator bi_call_bsi;
|
|
730 basic_block bi_call_bb, join_tgt_bb, guard_bb, guard_bb0;
|
|
731 edge join_tgt_in_edge_from_call, join_tgt_in_edge_fall_thru;
|
|
732 edge bi_call_in_edge0, guard_bb_in_edge;
|
|
733 VEC (gimple, heap) *conds;
|
|
734 unsigned tn_cond_stmts, nconds;
|
|
735 unsigned ci;
|
|
736 gimple cond_expr = NULL;
|
|
737 gimple cond_expr_start;
|
|
738 tree bi_call_label_decl;
|
|
739 gimple bi_call_label;
|
|
740
|
|
741 conds = VEC_alloc (gimple, heap, 12);
|
|
742 gen_shrink_wrap_conditions (bi_call, conds, &nconds);
|
|
743
|
|
744 /* This can happen if the condition generator decides
|
|
745 it is not beneficial to do the transformation. Just
|
|
746 return false and do not do any transformation for
|
|
747 the call. */
|
|
748 if (nconds == 0)
|
|
749 return false;
|
|
750
|
|
751 bi_call_bb = gimple_bb (bi_call);
|
|
752
|
|
753 /* Now find the join target bb -- split
|
|
754 bi_call_bb if needed. */
|
|
755 bi_call_bsi = gsi_for_stmt (bi_call);
|
|
756
|
|
757 join_tgt_in_edge_from_call = split_block (bi_call_bb, bi_call);
|
|
758 bi_call_bsi = gsi_for_stmt (bi_call);
|
|
759
|
|
760 join_tgt_bb = join_tgt_in_edge_from_call->dest;
|
|
761
|
|
762 /* Now it is time to insert the first conditional expression
|
|
763 into bi_call_bb and split this bb so that bi_call is
|
|
764 shrink-wrapped. */
|
|
765 tn_cond_stmts = VEC_length (gimple, conds);
|
|
766 cond_expr = NULL;
|
|
767 cond_expr_start = VEC_index (gimple, conds, 0);
|
|
768 for (ci = 0; ci < tn_cond_stmts; ci++)
|
|
769 {
|
|
770 gimple c = VEC_index (gimple, conds, ci);
|
|
771 gcc_assert (c || ci != 0);
|
|
772 if (!c)
|
|
773 break;
|
|
774 gsi_insert_before (&bi_call_bsi, c, GSI_SAME_STMT);
|
|
775 cond_expr = c;
|
|
776 }
|
|
777 nconds--;
|
|
778 ci++;
|
|
779 gcc_assert (cond_expr && gimple_code (cond_expr) == GIMPLE_COND);
|
|
780
|
|
781 /* Now the label. */
|
|
782 bi_call_label_decl = create_artificial_label ();
|
|
783 bi_call_label = gimple_build_label (bi_call_label_decl);
|
|
784 gsi_insert_before (&bi_call_bsi, bi_call_label, GSI_SAME_STMT);
|
|
785
|
|
786 bi_call_in_edge0 = split_block (bi_call_bb, cond_expr);
|
|
787 bi_call_in_edge0->flags &= ~EDGE_FALLTHRU;
|
|
788 bi_call_in_edge0->flags |= EDGE_TRUE_VALUE;
|
|
789 guard_bb0 = bi_call_bb;
|
|
790 bi_call_bb = bi_call_in_edge0->dest;
|
|
791 join_tgt_in_edge_fall_thru = make_edge (guard_bb0, join_tgt_bb,
|
|
792 EDGE_FALSE_VALUE);
|
|
793
|
|
794 bi_call_in_edge0->probability = REG_BR_PROB_BASE * ERR_PROB;
|
|
795 join_tgt_in_edge_fall_thru->probability =
|
|
796 REG_BR_PROB_BASE - bi_call_in_edge0->probability;
|
|
797
|
|
798 /* Code generation for the rest of the conditions */
|
|
799 guard_bb = guard_bb0;
|
|
800 while (nconds > 0)
|
|
801 {
|
|
802 unsigned ci0;
|
|
803 edge bi_call_in_edge;
|
|
804 gimple_stmt_iterator guard_bsi = gsi_for_stmt (cond_expr_start);
|
|
805 ci0 = ci;
|
|
806 cond_expr_start = VEC_index (gimple, conds, ci0);
|
|
807 for (; ci < tn_cond_stmts; ci++)
|
|
808 {
|
|
809 gimple c = VEC_index (gimple, conds, ci);
|
|
810 gcc_assert (c || ci != ci0);
|
|
811 if (!c)
|
|
812 break;
|
|
813 gsi_insert_before (&guard_bsi, c, GSI_SAME_STMT);
|
|
814 cond_expr = c;
|
|
815 }
|
|
816 nconds--;
|
|
817 ci++;
|
|
818 gcc_assert (cond_expr && gimple_code (cond_expr) == GIMPLE_COND);
|
|
819 guard_bb_in_edge = split_block (guard_bb, cond_expr);
|
|
820 guard_bb_in_edge->flags &= ~EDGE_FALLTHRU;
|
|
821 guard_bb_in_edge->flags |= EDGE_FALSE_VALUE;
|
|
822
|
|
823 bi_call_in_edge = make_edge (guard_bb, bi_call_bb, EDGE_TRUE_VALUE);
|
|
824
|
|
825 bi_call_in_edge->probability = REG_BR_PROB_BASE * ERR_PROB;
|
|
826 guard_bb_in_edge->probability =
|
|
827 REG_BR_PROB_BASE - bi_call_in_edge->probability;
|
|
828 }
|
|
829
|
|
830 VEC_free (gimple, heap, conds);
|
|
831 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
832 {
|
|
833 location_t loc;
|
|
834 loc = gimple_location (bi_call);
|
|
835 fprintf (dump_file,
|
|
836 "%s:%d: note: function call is shrink-wrapped"
|
|
837 " into error conditions.\n",
|
|
838 LOCATION_FILE (loc), LOCATION_LINE (loc));
|
|
839 }
|
|
840
|
|
841 return true;
|
|
842 }
|
|
843
|
|
844 /* The top level function for conditional dead code shrink
|
|
845 wrapping transformation. */
|
|
846
|
|
847 static bool
|
|
848 shrink_wrap_conditional_dead_built_in_calls (VEC (gimple, heap) *calls)
|
|
849 {
|
|
850 bool changed = false;
|
|
851 unsigned i = 0;
|
|
852
|
|
853 unsigned n = VEC_length (gimple, calls);
|
|
854 if (n == 0)
|
|
855 return false;
|
|
856
|
|
857 for (; i < n ; i++)
|
|
858 {
|
|
859 gimple bi_call = VEC_index (gimple, calls, i);
|
|
860 changed |= shrink_wrap_one_built_in_call (bi_call);
|
|
861 }
|
|
862
|
|
863 return changed;
|
|
864 }
|
|
865
|
|
866 /* Pass entry points. */
|
|
867
|
|
868 static unsigned int
|
|
869 tree_call_cdce (void)
|
|
870 {
|
|
871 basic_block bb;
|
|
872 gimple_stmt_iterator i;
|
|
873 bool something_changed = false;
|
|
874 VEC (gimple, heap) *cond_dead_built_in_calls = NULL;
|
|
875 FOR_EACH_BB (bb)
|
|
876 {
|
|
877 /* Collect dead call candidates. */
|
|
878 for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
|
|
879 {
|
|
880 gimple stmt = gsi_stmt (i);
|
|
881 if (is_gimple_call (stmt)
|
|
882 && is_call_dce_candidate (stmt))
|
|
883 {
|
|
884 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
885 {
|
|
886 fprintf (dump_file, "Found conditional dead call: ");
|
|
887 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
|
|
888 fprintf (dump_file, "\n");
|
|
889 }
|
|
890 if (cond_dead_built_in_calls == NULL)
|
|
891 cond_dead_built_in_calls = VEC_alloc (gimple, heap, 64);
|
|
892 VEC_safe_push (gimple, heap, cond_dead_built_in_calls, stmt);
|
|
893 }
|
|
894 }
|
|
895 }
|
|
896
|
|
897 if (cond_dead_built_in_calls == NULL)
|
|
898 return 0;
|
|
899
|
|
900 something_changed
|
|
901 = shrink_wrap_conditional_dead_built_in_calls (cond_dead_built_in_calls);
|
|
902
|
|
903 VEC_free (gimple, heap, cond_dead_built_in_calls);
|
|
904
|
|
905 if (something_changed)
|
|
906 {
|
|
907 free_dominance_info (CDI_DOMINATORS);
|
|
908 free_dominance_info (CDI_POST_DOMINATORS);
|
|
909 return (TODO_update_ssa | TODO_cleanup_cfg | TODO_ggc_collect
|
|
910 | TODO_remove_unused_locals);
|
|
911 }
|
|
912 else
|
|
913 return 0;
|
|
914 }
|
|
915
|
|
916 static bool
|
|
917 gate_call_cdce (void)
|
|
918 {
|
|
919 /* The limit constants used in the implementation
|
|
920 assume IEEE floating point format. Other formats
|
|
921 can be supported in the future if needed. */
|
|
922 return flag_tree_builtin_call_dce != 0 && optimize_function_for_speed_p (cfun);
|
|
923 }
|
|
924
|
|
925 struct gimple_opt_pass pass_call_cdce =
|
|
926 {
|
|
927 {
|
|
928 GIMPLE_PASS,
|
|
929 "cdce", /* name */
|
|
930 gate_call_cdce, /* gate */
|
|
931 tree_call_cdce, /* execute */
|
|
932 NULL, /* sub */
|
|
933 NULL, /* next */
|
|
934 0, /* static_pass_number */
|
|
935 TV_TREE_CALL_CDCE, /* tv_id */
|
|
936 PROP_cfg | PROP_ssa, /* properties_required */
|
|
937 0, /* properties_provided */
|
|
938 0, /* properties_destroyed */
|
|
939 0, /* todo_flags_start */
|
|
940 TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */
|
|
941 }
|
|
942 };
|