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