gcc/tree-call-cdce.c

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