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