gcc/tree-call-cdce.c

   1 /* Conditional Dead Call Elimination pass for the GNU compiler.
   2    Copyright (C) 2008-2013 Free Software Foundation, Inc.
   3    Contributed by Xinliang David Li <davidxl@google.com>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it
   8 under the terms of the GNU General Public License as published by the
   9 Free Software Foundation; either version 3, or (at your option) any
  10 later version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT
  13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "basic-block.h"
  26 #include "tree.h"
  27 #include "stor-layout.h"
  28 #include "gimple-pretty-print.h"
  29 #include "tree-ssa-alias.h"
  30 #include "internal-fn.h"
  31 #include "gimple-expr.h"
  32 #include "is-a.h"
  33 #include "gimple.h"
  34 #include "gimple-iterator.h"
  35 #include "gimple-ssa.h"
  36 #include "tree-cfg.h"
  37 #include "stringpool.h"
  38 #include "tree-ssanames.h"
  39 #include "tree-into-ssa.h"
  40 #include "tree-pass.h"
  41 #include "flags.h"
  42 \f
  43
  44 /* Conditional dead call elimination
  45
  46    Some builtin functions can set errno on error conditions, but they
  47    are otherwise pure.  If the result of a call to such a function is
  48    not used, the compiler can still not eliminate the call without
  49    powerful interprocedural analysis to prove that the errno is not
  50    checked.  However, if the conditions under which the error occurs
  51    are known, the compiler can conditionally dead code eliminate the
  52    calls by shrink-wrapping the semi-dead calls into the error condition:
  53
  54         built_in_call (args)
  55           ==>
  56         if (error_cond (args))
  57              built_in_call (args)
  58
  59     An actual simple example is :
  60          log (x);   // Mostly dead call
  61      ==>
  62          if (x < 0)
  63              log (x);
  64      With this change, call to log (x) is effectively eliminated, as
  65      in majority of the cases, log won't be called with x out of
  66      range.  The branch is totally predictable, so the branch cost
  67      is low.
  68
  69    Note that library functions are not supposed to clear errno to zero without
  70    error.  See IEEE Std 1003.1, section 2.3 Error Numbers, and section 7.5:3 of
  71    ISO/IEC 9899 (C99).
  72
  73    The condition wrapping the builtin call is conservatively set to avoid too
  74    aggressive (wrong) shrink wrapping.  The optimization is called conditional
  75    dead call elimination because the call is eliminated under the condition
  76    that the input arguments would not lead to domain or range error (for
  77    instance when x <= 0 for a log (x) call), however the chances that the error
  78    condition is hit is very low (those builtin calls which are conditionally
  79    dead are usually part of the C++ abstraction penalty exposed after
  80    inlining).  */
  81
  82
  83 /* A structure for representing input domain of
  84    a function argument in integer.  If the lower
  85    bound is -inf, has_lb is set to false.  If the
  86    upper bound is +inf, has_ub is false.
  87    is_lb_inclusive and is_ub_inclusive are flags
  88    to indicate if lb and ub value are inclusive
  89    respectively.  */
  90
  91 typedef struct input_domain
  92 {
  93   int lb;
  94   int ub;
  95   bool has_lb;
  96   bool has_ub;
  97   bool is_lb_inclusive;
  98   bool is_ub_inclusive;
  99 } inp_domain;
 100
 101 /* A helper function to construct and return an input
 102    domain object.  LB is the lower bound, HAS_LB is
 103    a boolean flag indicating if the lower bound exists,
 104    and LB_INCLUSIVE is a boolean flag indicating if the
 105    lower bound is inclusive or not.  UB, HAS_UB, and
 106    UB_INCLUSIVE have the same meaning, but for upper
 107    bound of the domain.  */
 108
 109 static inp_domain
 110 get_domain (int lb, bool has_lb, bool lb_inclusive,
 111             int ub, bool has_ub, bool ub_inclusive)
 112 {
 113   inp_domain domain;
 114   domain.lb = lb;
 115   domain.has_lb = has_lb;
 116   domain.is_lb_inclusive = lb_inclusive;
 117   domain.ub = ub;
 118   domain.has_ub = has_ub;
 119   domain.is_ub_inclusive = ub_inclusive;
 120   return domain;
 121 }
 122
 123 /* A helper function to check the target format for the
 124    argument type. In this implementation, only IEEE formats
 125    are supported.  ARG is the call argument to be checked.
 126    Returns true if the format is supported.  To support other
 127    target formats,  function get_no_error_domain needs to be
 128    enhanced to have range bounds properly computed. Since
 129    the check is cheap (very small number of candidates
 130    to be checked), the result is not cached for each float type.  */
 131
 132 static bool
 133 check_target_format (tree arg)
 134 {
 135   tree type;
 136   enum machine_mode mode;
 137   const struct real_format *rfmt;
 138
 139   type = TREE_TYPE (arg);
 140   mode = TYPE_MODE (type);
 141   rfmt = REAL_MODE_FORMAT (mode);
 142   if ((mode == SFmode
 143        && (rfmt == &ieee_single_format || rfmt == &mips_single_format
 144            || rfmt == &motorola_single_format))
 145       || (mode == DFmode
 146           && (rfmt == &ieee_double_format || rfmt == &mips_double_format
 147               || rfmt == &motorola_double_format))
 148       /* For long double, we can not really check XFmode
 149          which is only defined on intel platforms.
 150          Candidate pre-selection using builtin function
 151          code guarantees that we are checking formats
 152          for long double modes: double, quad, and extended.  */
 153       || (mode != SFmode && mode != DFmode
 154           && (rfmt == &ieee_quad_format
 155               || rfmt == &mips_quad_format
 156               || rfmt == &ieee_extended_motorola_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 (gimple pow_call)
 178 {
 179   tree base, expn;
 180   enum tree_code bc, ec;
 181
 182   if (gimple_call_num_args (pow_call) != 2)
 183     return false;
 184
 185   base = gimple_call_arg (pow_call, 0);
 186   expn = gimple_call_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_val0, type;
 216       gimple base_def;
 217       int bit_sz;
 218
 219       /* Only handles cases where base value is converted
 220          from integer values.  */
 221       base_def = SSA_NAME_DEF_STMT (base);
 222       if (gimple_code (base_def) != GIMPLE_ASSIGN)
 223         return false;
 224
 225       if (gimple_assign_rhs_code (base_def) != FLOAT_EXPR)
 226         return false;
 227       base_val0 = gimple_assign_rhs1 (base_def);
 228
 229       type = TREE_TYPE (base_val0);
 230       if (TREE_CODE (type) != INTEGER_TYPE)
 231         return false;
 232       bit_sz = TYPE_PRECISION (type);
 233       /* If the type of the base is too wide,
 234          the resulting shrink wrapping condition
 235          will be too conservative.  */
 236       if (bit_sz > MAX_BASE_INT_BIT_SIZE)
 237         return false;
 238
 239       return true;
 240     }
 241   else
 242     return false;
 243 }
 244
 245 /* A helper function to help select candidate function calls that are
 246    suitable for conditional DCE.  Candidate functions must have single
 247    valid input domain in this implementation except for pow (see check_pow).
 248    Returns true if the function call is a candidate.  */
 249
 250 static bool
 251 check_builtin_call (gimple bcall)
 252 {
 253   tree arg;
 254
 255   arg = gimple_call_arg (bcall, 0);
 256   return check_target_format (arg);
 257 }
 258
 259 /* A helper function to determine if a builtin function call is a
 260    candidate for conditional DCE.  Returns true if the builtin call
 261    is a candidate.  */
 262
 263 static bool
 264 is_call_dce_candidate (gimple call)
 265 {
 266   tree fn;
 267   enum built_in_function fnc;
 268
 269   /* Only potentially dead calls are considered.  */
 270   if (gimple_call_lhs (call))
 271     return false;
 272
 273   fn = gimple_call_fndecl (call);
 274   if (!fn
 275       || !DECL_BUILT_IN (fn)
 276       || (DECL_BUILT_IN_CLASS (fn) != BUILT_IN_NORMAL))
 277     return false;
 278
 279   fnc = DECL_FUNCTION_CODE (fn);
 280   switch (fnc)
 281     {
 282     /* Trig functions.  */
 283     CASE_FLT_FN (BUILT_IN_ACOS):
 284     CASE_FLT_FN (BUILT_IN_ASIN):
 285     /* Hyperbolic functions.  */
 286     CASE_FLT_FN (BUILT_IN_ACOSH):
 287     CASE_FLT_FN (BUILT_IN_ATANH):
 288     CASE_FLT_FN (BUILT_IN_COSH):
 289     CASE_FLT_FN (BUILT_IN_SINH):
 290     /* Log functions.  */
 291     CASE_FLT_FN (BUILT_IN_LOG):
 292     CASE_FLT_FN (BUILT_IN_LOG2):
 293     CASE_FLT_FN (BUILT_IN_LOG10):
 294     CASE_FLT_FN (BUILT_IN_LOG1P):
 295     /* Exp functions.  */
 296     CASE_FLT_FN (BUILT_IN_EXP):
 297     CASE_FLT_FN (BUILT_IN_EXP2):
 298     CASE_FLT_FN (BUILT_IN_EXP10):
 299     CASE_FLT_FN (BUILT_IN_EXPM1):
 300     CASE_FLT_FN (BUILT_IN_POW10):
 301     /* Sqrt.  */
 302     CASE_FLT_FN (BUILT_IN_SQRT):
 303       return check_builtin_call (call);
 304     /* Special one: two argument pow.  */
 305     case BUILT_IN_POW:
 306       return check_pow (call);
 307     default:
 308       break;
 309     }
 310
 311   return false;
 312 }
 313
 314 \f
 315 /* A helper function to generate gimple statements for
 316    one bound comparison.  ARG is the call argument to
 317    be compared with the bound, LBUB is the bound value
 318    in integer, TCODE is the tree_code of the comparison,
 319    TEMP_NAME1/TEMP_NAME2 are names of the temporaries,
 320    CONDS is a vector holding the produced GIMPLE statements,
 321    and NCONDS points to the variable holding the number
 322    of logical comparisons.  CONDS is either empty or
 323    a list ended with a null tree.  */
 324
 325 static void
 326 gen_one_condition (tree arg, int lbub,
 327                    enum tree_code tcode,
 328                    const char *temp_name1,
 329                    const char *temp_name2,
 330                    vec<gimple> conds,
 331                    unsigned *nconds)
 332 {
 333   tree lbub_real_cst, lbub_cst, float_type;
 334   tree temp, tempn, tempc, tempcn;
 335   gimple stmt1, stmt2, stmt3;
 336
 337   float_type = TREE_TYPE (arg);
 338   lbub_cst = build_int_cst (integer_type_node, lbub);
 339   lbub_real_cst = build_real_from_int_cst (float_type, lbub_cst);
 340
 341   temp = create_tmp_var (float_type, temp_name1);
 342   stmt1 = gimple_build_assign (temp, arg);
 343   tempn = make_ssa_name (temp, stmt1);
 344   gimple_assign_set_lhs (stmt1, tempn);
 345
 346   tempc = create_tmp_var (boolean_type_node, temp_name2);
 347   stmt2 = gimple_build_assign (tempc,
 348                                fold_build2 (tcode,
 349                                             boolean_type_node,
 350                                             tempn, lbub_real_cst));
 351   tempcn = make_ssa_name (tempc, stmt2);
 352   gimple_assign_set_lhs (stmt2, tempcn);
 353
 354   stmt3 = gimple_build_cond_from_tree (tempcn, NULL_TREE, NULL_TREE);
 355   conds.quick_push (stmt1);
 356   conds.quick_push (stmt2);
 357   conds.quick_push (stmt3);
 358   (*nconds)++;
 359 }
 360
 361 /* A helper function to generate GIMPLE statements for
 362    out of input domain check.  ARG is the call argument
 363    to be runtime checked, DOMAIN holds the valid domain
 364    for the given function, CONDS points to the vector
 365    holding the result GIMPLE statements.  *NCONDS is
 366    the number of logical comparisons.  This function
 367    produces no more than two logical comparisons, one
 368    for lower bound check, one for upper bound check.  */
 369
 370 static void
 371 gen_conditions_for_domain (tree arg, inp_domain domain,
 372                            vec<gimple> conds,
 373                            unsigned *nconds)
 374 {
 375   if (domain.has_lb)
 376     gen_one_condition (arg, domain.lb,
 377                        (domain.is_lb_inclusive
 378                         ? LT_EXPR : LE_EXPR),
 379                        "DCE_COND_LB", "DCE_COND_LB_TEST",
 380                        conds, nconds);
 381
 382   if (domain.has_ub)
 383     {
 384       /* Now push a separator.  */
 385       if (domain.has_lb)
 386         conds.quick_push (NULL);
 387
 388       gen_one_condition (arg, domain.ub,
 389                          (domain.is_ub_inclusive
 390                           ? GT_EXPR : GE_EXPR),
 391                          "DCE_COND_UB", "DCE_COND_UB_TEST",
 392                          conds, nconds);
 393     }
 394 }
 395
 396
 397 /* A helper function to generate condition
 398    code for the y argument in call pow (some_const, y).
 399    See candidate selection in check_pow.  Since the
 400    candidates' base values have a limited range,
 401    the guarded code generated for y are simple:
 402    if (y > max_y)
 403      pow (const, y);
 404    Note max_y can be computed separately for each
 405    const base, but in this implementation, we
 406    choose to compute it using the max base
 407    in the allowed range for the purpose of
 408    simplicity.  BASE is the constant base value,
 409    EXPN is the expression for the exponent argument,
 410    *CONDS is the vector to hold resulting statements,
 411    and *NCONDS is the number of logical conditions.  */
 412
 413 static void
 414 gen_conditions_for_pow_cst_base (tree base, tree expn,
 415                                  vec<gimple> conds,
 416                                  unsigned *nconds)
 417 {
 418   inp_domain exp_domain;
 419   /* Validate the range of the base constant to make
 420      sure it is consistent with check_pow.  */
 421   REAL_VALUE_TYPE mv;
 422   REAL_VALUE_TYPE bcv = TREE_REAL_CST (base);
 423   gcc_assert (!REAL_VALUES_EQUAL (bcv, dconst1)
 424               && !REAL_VALUES_LESS (bcv, dconst1));
 425   real_from_integer (&mv, TYPE_MODE (TREE_TYPE (base)), 256, 0, 1);
 426   gcc_assert (!REAL_VALUES_LESS (mv, bcv));
 427
 428   exp_domain = get_domain (0, false, false,
 429                            127, true, false);
 430
 431   gen_conditions_for_domain (expn, exp_domain,
 432                              conds, nconds);
 433 }
 434
 435 /* Generate error condition code for pow calls with
 436    non constant base values.  The candidates selected
 437    have their base argument value converted from
 438    integer (see check_pow) value (1, 2, 4 bytes), and
 439    the max exp value is computed based on the size
 440    of the integer type (i.e. max possible base value).
 441    The resulting input domain for exp argument is thus
 442    conservative (smaller than the max value allowed by
 443    the runtime value of the base).  BASE is the integer
 444    base value, EXPN is the expression for the exponent
 445    argument, *CONDS is the vector to hold resulting
 446    statements, and *NCONDS is the number of logical
 447    conditions.  */
 448
 449 static void
 450 gen_conditions_for_pow_int_base (tree base, tree expn,
 451                                  vec<gimple> conds,
 452                                  unsigned *nconds)
 453 {
 454   gimple base_def;
 455   tree base_val0;
 456   tree int_type;
 457   tree temp, tempn;
 458   tree cst0;
 459   gimple stmt1, stmt2;
 460   int bit_sz, max_exp;
 461   inp_domain exp_domain;
 462
 463   base_def = SSA_NAME_DEF_STMT (base);
 464   base_val0 = gimple_assign_rhs1 (base_def);
 465   int_type = TREE_TYPE (base_val0);
 466   bit_sz = TYPE_PRECISION (int_type);
 467   gcc_assert (bit_sz > 0
 468               && bit_sz <= MAX_BASE_INT_BIT_SIZE);
 469
 470   /* Determine the max exp argument value according to
 471      the size of the base integer.  The max exp value
 472      is conservatively estimated assuming IEEE754 double
 473      precision format.  */
 474   if (bit_sz == 8)
 475     max_exp = 128;
 476   else if (bit_sz == 16)
 477     max_exp = 64;
 478   else
 479     {
 480       gcc_assert (bit_sz == MAX_BASE_INT_BIT_SIZE);
 481       max_exp = 32;
 482     }
 483
 484   /* For pow ((double)x, y), generate the following conditions:
 485      cond 1:
 486      temp1 = x;
 487      if (temp1 <= 0)
 488
 489      cond 2:
 490      temp2 = y;
 491      if (temp2 > max_exp_real_cst)  */
 492
 493   /* Generate condition in reverse order -- first
 494      the condition for the exp argument.  */
 495
 496   exp_domain = get_domain (0, false, false,
 497                            max_exp, true, true);
 498
 499   gen_conditions_for_domain (expn, exp_domain,
 500                              conds, nconds);
 501
 502   /* Now generate condition for the base argument.
 503      Note it does not use the helper function
 504      gen_conditions_for_domain because the base
 505      type is integer.  */
 506
 507   /* Push a separator.  */
 508   conds.quick_push (NULL);
 509
 510   temp = create_tmp_var (int_type, "DCE_COND1");
 511   cst0 = build_int_cst (int_type, 0);
 512   stmt1 = gimple_build_assign (temp, base_val0);
 513   tempn = make_ssa_name (temp, stmt1);
 514   gimple_assign_set_lhs (stmt1, tempn);
 515   stmt2 = gimple_build_cond (LE_EXPR, tempn, cst0, NULL_TREE, NULL_TREE);
 516
 517   conds.quick_push (stmt1);
 518   conds.quick_push (stmt2);
 519   (*nconds)++;
 520 }
 521
 522 /* Method to generate conditional statements for guarding conditionally
 523    dead calls to pow.  One or more statements can be generated for
 524    each logical condition.  Statement groups of different conditions
 525    are separated by a NULL tree and they are stored in the vec
 526    conds.  The number of logical conditions are stored in *nconds.
 527
 528    See C99 standard, 7.12.7.4:2, for description of pow (x, y).
 529    The precise condition for domain errors are complex.  In this
 530    implementation, a simplified (but conservative) valid domain
 531    for x and y are used: x is positive to avoid dom errors, while
 532    y is smaller than a upper bound (depending on x) to avoid range
 533    errors.  Runtime code is generated to check x (if not constant)
 534    and y against the valid domain.  If it is out, jump to the call,
 535    otherwise the call is bypassed.  POW_CALL is the call statement,
 536    *CONDS is a vector holding the resulting condition statements,
 537    and *NCONDS is the number of logical conditions.  */
 538
 539 static void
 540 gen_conditions_for_pow (gimple pow_call, vec<gimple> conds,
 541                         unsigned *nconds)
 542 {
 543   tree base, expn;
 544   enum tree_code bc;
 545
 546   gcc_checking_assert (check_pow (pow_call));
 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> conds,
 677                             unsigned int *nconds)
 678 {
 679   gimple call;
 680   tree fn;
 681   enum built_in_function fnc;
 682
 683   gcc_assert (nconds && conds.exists ());
 684   gcc_assert (conds.length () == 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   unsigned tn_cond_stmts, nconds;
 724   unsigned ci;
 725   gimple cond_expr = NULL;
 726   gimple cond_expr_start;
 727   tree bi_call_label_decl;
 728   gimple bi_call_label;
 729
 730   stack_vec<gimple, 12> conds;
 731   gen_shrink_wrap_conditions (bi_call, conds, &nconds);
 732
 733   /* This can happen if the condition generator decides
 734      it is not beneficial to do the transformation.  Just
 735      return false and do not do any transformation for
 736      the call.  */
 737   if (nconds == 0)
 738     return false;
 739
 740   bi_call_bb = gimple_bb (bi_call);
 741
 742   /* Now find the join target bb -- split bi_call_bb if needed.  */
 743   if (stmt_ends_bb_p (bi_call))
 744     {
 745       /* If the call must be the last in the bb, don't split the block,
 746          it could e.g. have EH edges.  */
 747       join_tgt_in_edge_from_call = find_fallthru_edge (bi_call_bb->succs);
 748       if (join_tgt_in_edge_from_call == NULL)
 749         return false;
 750     }
 751   else
 752     join_tgt_in_edge_from_call = split_block (bi_call_bb, bi_call);
 753
 754   bi_call_bsi = gsi_for_stmt (bi_call);
 755
 756   join_tgt_bb = join_tgt_in_edge_from_call->dest;
 757
 758   /* Now it is time to insert the first conditional expression
 759      into bi_call_bb and split this bb so that bi_call is
 760      shrink-wrapped.  */
 761   tn_cond_stmts = conds.length ();
 762   cond_expr = NULL;
 763   cond_expr_start = conds[0];
 764   for (ci = 0; ci < tn_cond_stmts; ci++)
 765     {
 766       gimple c = conds[ci];
 767       gcc_assert (c || ci != 0);
 768       if (!c)
 769         break;
 770       gsi_insert_before (&bi_call_bsi, c, GSI_SAME_STMT);
 771       cond_expr = c;
 772     }
 773   nconds--;
 774   ci++;
 775   gcc_assert (cond_expr && gimple_code (cond_expr) == GIMPLE_COND);
 776
 777   /* Now the label.  */
 778   bi_call_label_decl = create_artificial_label (gimple_location (bi_call));
 779   bi_call_label = gimple_build_label (bi_call_label_decl);
 780   gsi_insert_before (&bi_call_bsi, bi_call_label, GSI_SAME_STMT);
 781
 782   bi_call_in_edge0 = split_block (bi_call_bb, cond_expr);
 783   bi_call_in_edge0->flags &= ~EDGE_FALLTHRU;
 784   bi_call_in_edge0->flags |= EDGE_TRUE_VALUE;
 785   guard_bb0 = bi_call_bb;
 786   bi_call_bb = bi_call_in_edge0->dest;
 787   join_tgt_in_edge_fall_thru = make_edge (guard_bb0, join_tgt_bb,
 788                                           EDGE_FALSE_VALUE);
 789
 790   bi_call_in_edge0->probability = REG_BR_PROB_BASE * ERR_PROB;
 791   bi_call_in_edge0->count =
 792       apply_probability (guard_bb0->count,
 793                          bi_call_in_edge0->probability);
 794   join_tgt_in_edge_fall_thru->probability =
 795       inverse_probability (bi_call_in_edge0->probability);
 796   join_tgt_in_edge_fall_thru->count =
 797       guard_bb0->count - bi_call_in_edge0->count;
 798
 799   /* Code generation for the rest of the conditions  */
 800   guard_bb = guard_bb0;
 801   while (nconds > 0)
 802     {
 803       unsigned ci0;
 804       edge bi_call_in_edge;
 805       gimple_stmt_iterator guard_bsi = gsi_for_stmt (cond_expr_start);
 806       ci0 = ci;
 807       cond_expr_start = conds[ci0];
 808       for (; ci < tn_cond_stmts; ci++)
 809         {
 810           gimple c = conds[ci];
 811           gcc_assert (c || ci != ci0);
 812           if (!c)
 813             break;
 814           gsi_insert_before (&guard_bsi, c, GSI_SAME_STMT);
 815           cond_expr = c;
 816         }
 817       nconds--;
 818       ci++;
 819       gcc_assert (cond_expr && gimple_code (cond_expr) == GIMPLE_COND);
 820       guard_bb_in_edge = split_block (guard_bb, cond_expr);
 821       guard_bb_in_edge->flags &= ~EDGE_FALLTHRU;
 822       guard_bb_in_edge->flags |= EDGE_FALSE_VALUE;
 823
 824       bi_call_in_edge = make_edge (guard_bb, bi_call_bb, EDGE_TRUE_VALUE);
 825
 826       bi_call_in_edge->probability = REG_BR_PROB_BASE * ERR_PROB;
 827       bi_call_in_edge->count =
 828           apply_probability (guard_bb->count,
 829                              bi_call_in_edge->probability);
 830       guard_bb_in_edge->probability =
 831           inverse_probability (bi_call_in_edge->probability);
 832       guard_bb_in_edge->count = guard_bb->count - bi_call_in_edge->count;
 833     }
 834
 835   if (dump_file && (dump_flags & TDF_DETAILS))
 836     {
 837       location_t loc;
 838       loc = gimple_location (bi_call);
 839       fprintf (dump_file,
 840                "%s:%d: note: function call is shrink-wrapped"
 841                " into error conditions.\n",
 842                LOCATION_FILE (loc), LOCATION_LINE (loc));
 843     }
 844
 845   return true;
 846 }
 847
 848 /* The top level function for conditional dead code shrink
 849    wrapping transformation.  */
 850
 851 static bool
 852 shrink_wrap_conditional_dead_built_in_calls (vec<gimple> calls)
 853 {
 854   bool changed = false;
 855   unsigned i = 0;
 856
 857   unsigned n = calls.length ();
 858   if (n == 0)
 859     return false;
 860
 861   for (; i < n ; i++)
 862     {
 863       gimple bi_call = calls[i];
 864       changed |= shrink_wrap_one_built_in_call (bi_call);
 865     }
 866
 867   return changed;
 868 }
 869
 870 /* Pass entry points.  */
 871
 872 static unsigned int
 873 tree_call_cdce (void)
 874 {
 875   basic_block bb;
 876   gimple_stmt_iterator i;
 877   bool something_changed = false;
 878   auto_vec<gimple> cond_dead_built_in_calls;
 879   FOR_EACH_BB_FN (bb, cfun)
 880     {
 881       /* Collect dead call candidates.  */
 882       for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
 883         {
 884           gimple stmt = gsi_stmt (i);
 885           if (is_gimple_call (stmt)
 886               && is_call_dce_candidate (stmt))
 887             {
 888               if (dump_file && (dump_flags & TDF_DETAILS))
 889                 {
 890                   fprintf (dump_file, "Found conditional dead call: ");
 891                   print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 892                   fprintf (dump_file, "\n");
 893                 }
 894               if (!cond_dead_built_in_calls.exists ())
 895                 cond_dead_built_in_calls.create (64);
 896               cond_dead_built_in_calls.safe_push (stmt);
 897             }
 898         }
 899     }
 900
 901   if (!cond_dead_built_in_calls.exists ())
 902     return 0;
 903
 904   something_changed
 905     = shrink_wrap_conditional_dead_built_in_calls (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       /* As we introduced new control-flow we need to insert PHI-nodes
 912          for the call-clobbers of the remaining call.  */
 913       mark_virtual_operands_for_renaming (cfun);
 914       return TODO_update_ssa;
 915     }
 916
 917   return 0;
 918 }
 919
 920 static bool
 921 gate_call_cdce (void)
 922 {
 923   /* The limit constants used in the implementation
 924      assume IEEE floating point format.  Other formats
 925      can be supported in the future if needed.  */
 926   return flag_tree_builtin_call_dce != 0 && optimize_function_for_speed_p (cfun);
 927 }
 928
 929 namespace {
 930
 931 const pass_data pass_data_call_cdce =
 932 {
 933   GIMPLE_PASS, /* type */
 934   "cdce", /* name */
 935   OPTGROUP_NONE, /* optinfo_flags */
 936   true, /* has_gate */
 937   true, /* has_execute */
 938   TV_TREE_CALL_CDCE, /* tv_id */
 939   ( PROP_cfg | PROP_ssa ), /* properties_required */
 940   0, /* properties_provided */
 941   0, /* properties_destroyed */
 942   0, /* todo_flags_start */
 943   TODO_verify_ssa, /* todo_flags_finish */
 944 };
 945
 946 class pass_call_cdce : public gimple_opt_pass
 947 {
 948 public:
 949   pass_call_cdce (gcc::context *ctxt)
 950     : gimple_opt_pass (pass_data_call_cdce, ctxt)
 951   {}
 952
 953   /* opt_pass methods: */
 954   bool gate () { return gate_call_cdce (); }
 955   unsigned int execute () { return tree_call_cdce (); }
 956
 957 }; // class pass_call_cdce
 958
 959 } // anon namespace
 960
 961 gimple_opt_pass *
 962 make_pass_call_cdce (gcc::context *ctxt)
 963 {
 964   return new pass_call_cdce (ctxt);
 965 }