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     return false;
 730
 731   bi_call_bb = gimple_bb (bi_call);
 732
 733   /* Now find the join target bb -- split
 734      bi_call_bb if needed.  */
 735   bi_call_bsi = gsi_for_stmt (bi_call);
 736
 737   join_tgt_in_edge_from_call = split_block (bi_call_bb, bi_call);
 738   bi_call_bsi = gsi_for_stmt (bi_call);
 739
 740   join_tgt_bb = join_tgt_in_edge_from_call->dest;
 741
 742   /* Now it is time to insert the first conditional expression
 743      into bi_call_bb and split this bb so that bi_call is
 744      shrink-wrapped.  */
 745   tn_cond_stmts = conds.length ();
 746   cond_expr = NULL;
 747   cond_expr_start = conds[0];
 748   for (ci = 0; ci < tn_cond_stmts; ci++)
 749     {
 750       gimple c = conds[ci];
 751       gcc_assert (c || ci != 0);
 752       if (!c)
 753         break;
 754       gsi_insert_before (&bi_call_bsi, c, GSI_SAME_STMT);
 755       cond_expr = c;
 756     }
 757   nconds--;
 758   ci++;
 759   gcc_assert (cond_expr && gimple_code (cond_expr) == GIMPLE_COND);
 760
 761   /* Now the label.  */
 762   bi_call_label_decl = create_artificial_label (gimple_location (bi_call));
 763   bi_call_label = gimple_build_label (bi_call_label_decl);
 764   gsi_insert_before (&bi_call_bsi, bi_call_label, GSI_SAME_STMT);
 765
 766   bi_call_in_edge0 = split_block (bi_call_bb, cond_expr);
 767   bi_call_in_edge0->flags &= ~EDGE_FALLTHRU;
 768   bi_call_in_edge0->flags |= EDGE_TRUE_VALUE;
 769   guard_bb0 = bi_call_bb;
 770   bi_call_bb = bi_call_in_edge0->dest;
 771   join_tgt_in_edge_fall_thru = make_edge (guard_bb0, join_tgt_bb,
 772                                           EDGE_FALSE_VALUE);
 773
 774   bi_call_in_edge0->probability = REG_BR_PROB_BASE * ERR_PROB;
 775   bi_call_in_edge0->count =
 776       apply_probability (guard_bb0->count,
 777                          bi_call_in_edge0->probability);
 778   join_tgt_in_edge_fall_thru->probability =
 779       inverse_probability (bi_call_in_edge0->probability);
 780   join_tgt_in_edge_fall_thru->count =
 781       guard_bb0->count - bi_call_in_edge0->count;
 782
 783   /* Code generation for the rest of the conditions  */
 784   guard_bb = guard_bb0;
 785   while (nconds > 0)
 786     {
 787       unsigned ci0;
 788       edge bi_call_in_edge;
 789       gimple_stmt_iterator guard_bsi = gsi_for_stmt (cond_expr_start);
 790       ci0 = ci;
 791       cond_expr_start = conds[ci0];
 792       for (; ci < tn_cond_stmts; ci++)
 793         {
 794           gimple c = conds[ci];
 795           gcc_assert (c || ci != ci0);
 796           if (!c)
 797             break;
 798           gsi_insert_before (&guard_bsi, c, GSI_SAME_STMT);
 799           cond_expr = c;
 800         }
 801       nconds--;
 802       ci++;
 803       gcc_assert (cond_expr && gimple_code (cond_expr) == GIMPLE_COND);
 804       guard_bb_in_edge = split_block (guard_bb, cond_expr);
 805       guard_bb_in_edge->flags &= ~EDGE_FALLTHRU;
 806       guard_bb_in_edge->flags |= EDGE_FALSE_VALUE;
 807
 808       bi_call_in_edge = make_edge (guard_bb, bi_call_bb, EDGE_TRUE_VALUE);
 809
 810       bi_call_in_edge->probability = REG_BR_PROB_BASE * ERR_PROB;
 811       bi_call_in_edge->count =
 812           apply_probability (guard_bb->count,
 813                              bi_call_in_edge->probability);
 814       guard_bb_in_edge->probability =
 815           inverse_probability (bi_call_in_edge->probability);
 816       guard_bb_in_edge->count = guard_bb->count - bi_call_in_edge->count;
 817     }
 818
 819   conds.release ();
 820   if (dump_file && (dump_flags & TDF_DETAILS))
 821     {
 822       location_t loc;
 823       loc = gimple_location (bi_call);
 824       fprintf (dump_file,
 825                "%s:%d: note: function call is shrink-wrapped"
 826                " into error conditions.\n",
 827                LOCATION_FILE (loc), LOCATION_LINE (loc));
 828     }
 829
 830   return true;
 831 }
 832
 833 /* The top level function for conditional dead code shrink
 834    wrapping transformation.  */
 835
 836 static bool
 837 shrink_wrap_conditional_dead_built_in_calls (vec<gimple> calls)
 838 {
 839   bool changed = false;
 840   unsigned i = 0;
 841
 842   unsigned n = calls.length ();
 843   if (n == 0)
 844     return false;
 845
 846   for (; i < n ; i++)
 847     {
 848       gimple bi_call = calls[i];
 849       changed |= shrink_wrap_one_built_in_call (bi_call);
 850     }
 851
 852   return changed;
 853 }
 854
 855 /* Pass entry points.  */
 856
 857 static unsigned int
 858 tree_call_cdce (void)
 859 {
 860   basic_block bb;
 861   gimple_stmt_iterator i;
 862   bool something_changed = false;
 863   vec<gimple> cond_dead_built_in_calls = vNULL;
 864   FOR_EACH_BB (bb)
 865     {
 866       /* Collect dead call candidates.  */
 867       for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
 868         {
 869           gimple stmt = gsi_stmt (i);
 870           if (is_gimple_call (stmt)
 871               && is_call_dce_candidate (stmt))
 872             {
 873               if (dump_file && (dump_flags & TDF_DETAILS))
 874                 {
 875                   fprintf (dump_file, "Found conditional dead call: ");
 876                   print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 877                   fprintf (dump_file, "\n");
 878                 }
 879               if (!cond_dead_built_in_calls.exists ())
 880                 cond_dead_built_in_calls.create (64);
 881               cond_dead_built_in_calls.safe_push (stmt);
 882             }
 883         }
 884     }
 885
 886   if (!cond_dead_built_in_calls.exists ())
 887     return 0;
 888
 889   something_changed
 890     = shrink_wrap_conditional_dead_built_in_calls (cond_dead_built_in_calls);
 891
 892   cond_dead_built_in_calls.release ();
 893
 894   if (something_changed)
 895     {
 896       free_dominance_info (CDI_DOMINATORS);
 897       free_dominance_info (CDI_POST_DOMINATORS);
 898       /* As we introduced new control-flow we need to insert PHI-nodes
 899          for the call-clobbers of the remaining call.  */
 900       mark_virtual_operands_for_renaming (cfun);
 901       return (TODO_update_ssa | TODO_cleanup_cfg | TODO_ggc_collect
 902               | TODO_remove_unused_locals);
 903     }
 904   else
 905     return 0;
 906 }
 907
 908 static bool
 909 gate_call_cdce (void)
 910 {
 911   /* The limit constants used in the implementation
 912      assume IEEE floating point format.  Other formats
 913      can be supported in the future if needed.  */
 914   return flag_tree_builtin_call_dce != 0 && optimize_function_for_speed_p (cfun);
 915 }
 916
 917 struct gimple_opt_pass pass_call_cdce =
 918 {
 919  {
 920   GIMPLE_PASS,
 921   "cdce",                               /* name */
 922   OPTGROUP_NONE,                        /* optinfo_flags */
 923   gate_call_cdce,                       /* gate */
 924   tree_call_cdce,                       /* execute */
 925   NULL,                                 /* sub */
 926   NULL,                                 /* next */
 927   0,                                    /* static_pass_number */
 928   TV_TREE_CALL_CDCE,                    /* tv_id */
 929   PROP_cfg | PROP_ssa,                  /* properties_required */
 930   0,                                    /* properties_provided */
 931   0,                                    /* properties_destroyed */
 932   0,                                    /* todo_flags_start */
 933   TODO_verify_ssa                       /* todo_flags_finish */
 934  }
 935 };