contrib/gcc-5.0/gcc/tree-call-cdce.c

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