gcc/tree-call-cdce.c

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