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