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