gcc/tree-call-cdce.c

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