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