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