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