1 /* Conditional Dead Call Elimination pass for the GNU compiler. 2 Copyright (C) 2008-2016 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 "backend.h" 25 #include "tree.h" 26 #include "gimple.h" 27 #include "cfghooks.h" 28 #include "tree-pass.h" 29 #include "ssa.h" 30 #include "gimple-pretty-print.h" 31 #include "fold-const.h" 32 #include "stor-layout.h" 33 #include "gimple-iterator.h" 34 #include "tree-cfg.h" 35 #include "tree-into-ssa.h" 36 #include "builtins.h" 37 #include "internal-fn.h" 38 39 40 /* This pass serves two closely-related purposes: 41 42 1. It conditionally executes calls that set errno if (a) the result of 43 the call is unused and (b) a simple range check on the arguments can 44 detect most cases where errno does not need to be set. 45 46 This is the "conditional dead-code elimination" that gave the pass 47 its original name, since the call is dead for most argument values. 48 The calls for which it helps are usually part of the C++ abstraction 49 penalty exposed after inlining. 50 51 2. It looks for calls to built-in functions that set errno and whose 52 result is used. It checks whether there is an associated internal 53 function that doesn't set errno and whether the target supports 54 that internal function. If so, the pass uses the internal function 55 to compute the result of the built-in function but still arranges 56 for errno to be set when necessary. There are two ways of setting 57 errno: 58 59 a. by protecting the original call with the same argument checks as (1) 60 61 b. by protecting the original call with a check that the result 62 of the internal function is not equal to itself (i.e. is NaN). 63 64 (b) requires that NaNs are the only erroneous results. It is not 65 appropriate for functions like log, which returns ERANGE for zero 66 arguments. (b) is also likely to perform worse than (a) because it 67 requires the result to be calculated first. The pass therefore uses 68 (a) when it can and uses (b) as a fallback. 69 70 For (b) the pass can replace the original call with a call to 71 IFN_SET_EDOM, if the target supports direct assignments to errno. 72 73 In both cases, arguments that require errno to be set should occur 74 rarely in practice. Checks of the errno result should also be rare, 75 but the compiler would need powerful interprocedural analysis to 76 prove that errno is not checked. It's much easier to add argument 77 checks or result checks instead. 78 79 An example of (1) is: 80 81 log (x); // Mostly dead call 82 ==> 83 if (__builtin_islessequal (x, 0)) 84 log (x); 85 86 With this change, call to log (x) is effectively eliminated, as 87 in the majority of the cases, log won't be called with x out of 88 range. The branch is totally predictable, so the branch cost 89 is low. 90 91 An example of (2) is: 92 93 y = sqrt (x); 94 ==> 95 y = IFN_SQRT (x); 96 if (__builtin_isless (x, 0)) 97 sqrt (x); 98 99 In the vast majority of cases we should then never need to call sqrt. 100 101 Note that library functions are not supposed to clear errno to zero without 102 error. See IEEE Std 1003.1, section 2.3 Error Numbers, and section 7.5:3 of 103 ISO/IEC 9899 (C99). 104 105 The condition wrapping the builtin call is conservatively set to avoid too 106 aggressive (wrong) shrink wrapping. */ 107 108 109 /* A structure for representing input domain of 110 a function argument in integer. If the lower 111 bound is -inf, has_lb is set to false. If the 112 upper bound is +inf, has_ub is false. 113 is_lb_inclusive and is_ub_inclusive are flags 114 to indicate if lb and ub value are inclusive 115 respectively. */ 116 117 struct inp_domain 118 { 119 int lb; 120 int ub; 121 bool has_lb; 122 bool has_ub; 123 bool is_lb_inclusive; 124 bool is_ub_inclusive; 125 }; 126 127 /* A helper function to construct and return an input 128 domain object. LB is the lower bound, HAS_LB is 129 a boolean flag indicating if the lower bound exists, 130 and LB_INCLUSIVE is a boolean flag indicating if the 131 lower bound is inclusive or not. UB, HAS_UB, and 132 UB_INCLUSIVE have the same meaning, but for upper 133 bound of the domain. */ 134 135 static inp_domain 136 get_domain (int lb, bool has_lb, bool lb_inclusive, 137 int ub, bool has_ub, bool ub_inclusive) 138 { 139 inp_domain domain; 140 domain.lb = lb; 141 domain.has_lb = has_lb; 142 domain.is_lb_inclusive = lb_inclusive; 143 domain.ub = ub; 144 domain.has_ub = has_ub; 145 domain.is_ub_inclusive = ub_inclusive; 146 return domain; 147 } 148 149 /* A helper function to check the target format for the 150 argument type. In this implementation, only IEEE formats 151 are supported. ARG is the call argument to be checked. 152 Returns true if the format is supported. To support other 153 target formats, function get_no_error_domain needs to be 154 enhanced to have range bounds properly computed. Since 155 the check is cheap (very small number of candidates 156 to be checked), the result is not cached for each float type. */ 157 158 static bool 159 check_target_format (tree arg) 160 { 161 tree type; 162 machine_mode mode; 163 const struct real_format *rfmt; 164 165 type = TREE_TYPE (arg); 166 mode = TYPE_MODE (type); 167 rfmt = REAL_MODE_FORMAT (mode); 168 if ((mode == SFmode 169 && (rfmt == &ieee_single_format || rfmt == &mips_single_format 170 || rfmt == &motorola_single_format)) 171 || (mode == DFmode 172 && (rfmt == &ieee_double_format || rfmt == &mips_double_format 173 || rfmt == &motorola_double_format)) 174 /* For long double, we can not really check XFmode 175 which is only defined on intel platforms. 176 Candidate pre-selection using builtin function 177 code guarantees that we are checking formats 178 for long double modes: double, quad, and extended. */ 179 || (mode != SFmode && mode != DFmode 180 && (rfmt == &ieee_quad_format 181 || rfmt == &mips_quad_format 182 || rfmt == &ieee_extended_motorola_format 183 || rfmt == &ieee_extended_intel_96_format 184 || rfmt == &ieee_extended_intel_128_format 185 || rfmt == &ieee_extended_intel_96_round_53_format))) 186 return true; 187 188 return false; 189 } 190 191 192 /* A helper function to help select calls to pow that are suitable for 193 conditional DCE transformation. It looks for pow calls that can be 194 guided with simple conditions. Such calls either have constant base 195 values or base values converted from integers. Returns true if 196 the pow call POW_CALL is a candidate. */ 197 198 /* The maximum integer bit size for base argument of a pow call 199 that is suitable for shrink-wrapping transformation. */ 200 #define MAX_BASE_INT_BIT_SIZE 32 201 202 static bool 203 check_pow (gcall *pow_call) 204 { 205 tree base, expn; 206 enum tree_code bc, ec; 207 208 if (gimple_call_num_args (pow_call) != 2) 209 return false; 210 211 base = gimple_call_arg (pow_call, 0); 212 expn = gimple_call_arg (pow_call, 1); 213 214 if (!check_target_format (expn)) 215 return false; 216 217 bc = TREE_CODE (base); 218 ec = TREE_CODE (expn); 219 220 /* Folding candidates are not interesting. 221 Can actually assert that it is already folded. */ 222 if (ec == REAL_CST && bc == REAL_CST) 223 return false; 224 225 if (bc == REAL_CST) 226 { 227 /* Only handle a fixed range of constant. */ 228 REAL_VALUE_TYPE mv; 229 REAL_VALUE_TYPE bcv = TREE_REAL_CST (base); 230 if (real_equal (&bcv, &dconst1)) 231 return false; 232 if (real_less (&bcv, &dconst1)) 233 return false; 234 real_from_integer (&mv, TYPE_MODE (TREE_TYPE (base)), 256, UNSIGNED); 235 if (real_less (&mv, &bcv)) 236 return false; 237 return true; 238 } 239 else if (bc == SSA_NAME) 240 { 241 tree base_val0, type; 242 gimple *base_def; 243 int bit_sz; 244 245 /* Only handles cases where base value is converted 246 from integer values. */ 247 base_def = SSA_NAME_DEF_STMT (base); 248 if (gimple_code (base_def) != GIMPLE_ASSIGN) 249 return false; 250 251 if (gimple_assign_rhs_code (base_def) != FLOAT_EXPR) 252 return false; 253 base_val0 = gimple_assign_rhs1 (base_def); 254 255 type = TREE_TYPE (base_val0); 256 if (TREE_CODE (type) != INTEGER_TYPE) 257 return false; 258 bit_sz = TYPE_PRECISION (type); 259 /* If the type of the base is too wide, 260 the resulting shrink wrapping condition 261 will be too conservative. */ 262 if (bit_sz > MAX_BASE_INT_BIT_SIZE) 263 return false; 264 265 return true; 266 } 267 else 268 return false; 269 } 270 271 /* A helper function to help select candidate function calls that are 272 suitable for conditional DCE. Candidate functions must have single 273 valid input domain in this implementation except for pow (see check_pow). 274 Returns true if the function call is a candidate. */ 275 276 static bool 277 check_builtin_call (gcall *bcall) 278 { 279 tree arg; 280 281 arg = gimple_call_arg (bcall, 0); 282 return check_target_format (arg); 283 } 284 285 /* Return true if built-in function call CALL calls a math function 286 and if we know how to test the range of its arguments to detect _most_ 287 situations in which errno is not set. The test must err on the side 288 of treating non-erroneous values as potentially erroneous. */ 289 290 static bool 291 can_test_argument_range (gcall *call) 292 { 293 switch (DECL_FUNCTION_CODE (gimple_call_fndecl (call))) 294 { 295 /* Trig functions. */ 296 CASE_FLT_FN (BUILT_IN_ACOS): 297 CASE_FLT_FN (BUILT_IN_ASIN): 298 /* Hyperbolic functions. */ 299 CASE_FLT_FN (BUILT_IN_ACOSH): 300 CASE_FLT_FN (BUILT_IN_ATANH): 301 CASE_FLT_FN (BUILT_IN_COSH): 302 CASE_FLT_FN (BUILT_IN_SINH): 303 /* Log functions. */ 304 CASE_FLT_FN (BUILT_IN_LOG): 305 CASE_FLT_FN (BUILT_IN_LOG2): 306 CASE_FLT_FN (BUILT_IN_LOG10): 307 CASE_FLT_FN (BUILT_IN_LOG1P): 308 /* Exp functions. */ 309 CASE_FLT_FN (BUILT_IN_EXP): 310 CASE_FLT_FN (BUILT_IN_EXP2): 311 CASE_FLT_FN (BUILT_IN_EXP10): 312 CASE_FLT_FN (BUILT_IN_EXPM1): 313 CASE_FLT_FN (BUILT_IN_POW10): 314 /* Sqrt. */ 315 CASE_FLT_FN (BUILT_IN_SQRT): 316 return check_builtin_call (call); 317 /* Special one: two argument pow. */ 318 case BUILT_IN_POW: 319 return check_pow (call); 320 default: 321 break; 322 } 323 324 return false; 325 } 326 327 /* Return true if CALL can produce a domain error (EDOM) but can never 328 produce a pole, range overflow or range underflow error (all ERANGE). 329 This means that we can tell whether a function would have set errno 330 by testing whether the result is a NaN. */ 331 332 static bool 333 edom_only_function (gcall *call) 334 { 335 switch (DECL_FUNCTION_CODE (gimple_call_fndecl (call))) 336 { 337 CASE_FLT_FN (BUILT_IN_ACOS): 338 CASE_FLT_FN (BUILT_IN_ASIN): 339 CASE_FLT_FN (BUILT_IN_ATAN): 340 CASE_FLT_FN (BUILT_IN_COS): 341 CASE_FLT_FN (BUILT_IN_SIGNIFICAND): 342 CASE_FLT_FN (BUILT_IN_SIN): 343 CASE_FLT_FN (BUILT_IN_SQRT): 344 CASE_FLT_FN (BUILT_IN_FMOD): 345 CASE_FLT_FN (BUILT_IN_REMAINDER): 346 return true; 347 348 default: 349 return false; 350 } 351 } 352 353 /* A helper function to generate gimple statements for one bound 354 comparison, so that the built-in function is called whenever 355 TCODE <ARG, LBUB> is *false*. TEMP_NAME1/TEMP_NAME2 are names 356 of the temporaries, CONDS is a vector holding the produced GIMPLE 357 statements, and NCONDS points to the variable holding the number of 358 logical comparisons. CONDS is either empty or a list ended with a 359 null tree. */ 360 361 static void 362 gen_one_condition (tree arg, int lbub, 363 enum tree_code tcode, 364 const char *temp_name1, 365 const char *temp_name2, 366 vec<gimple *> conds, 367 unsigned *nconds) 368 { 369 tree lbub_real_cst, lbub_cst, float_type; 370 tree temp, tempn, tempc, tempcn; 371 gassign *stmt1; 372 gassign *stmt2; 373 gcond *stmt3; 374 375 float_type = TREE_TYPE (arg); 376 lbub_cst = build_int_cst (integer_type_node, lbub); 377 lbub_real_cst = build_real_from_int_cst (float_type, lbub_cst); 378 379 temp = create_tmp_var (float_type, temp_name1); 380 stmt1 = gimple_build_assign (temp, arg); 381 tempn = make_ssa_name (temp, stmt1); 382 gimple_assign_set_lhs (stmt1, tempn); 383 384 tempc = create_tmp_var (boolean_type_node, temp_name2); 385 stmt2 = gimple_build_assign (tempc, 386 fold_build2 (tcode, 387 boolean_type_node, 388 tempn, lbub_real_cst)); 389 tempcn = make_ssa_name (tempc, stmt2); 390 gimple_assign_set_lhs (stmt2, tempcn); 391 392 stmt3 = gimple_build_cond_from_tree (tempcn, NULL_TREE, NULL_TREE); 393 conds.quick_push (stmt1); 394 conds.quick_push (stmt2); 395 conds.quick_push (stmt3); 396 (*nconds)++; 397 } 398 399 /* A helper function to generate GIMPLE statements for 400 out of input domain check. ARG is the call argument 401 to be runtime checked, DOMAIN holds the valid domain 402 for the given function, CONDS points to the vector 403 holding the result GIMPLE statements. *NCONDS is 404 the number of logical comparisons. This function 405 produces no more than two logical comparisons, one 406 for lower bound check, one for upper bound check. */ 407 408 static void 409 gen_conditions_for_domain (tree arg, inp_domain domain, 410 vec<gimple *> conds, 411 unsigned *nconds) 412 { 413 if (domain.has_lb) 414 gen_one_condition (arg, domain.lb, 415 (domain.is_lb_inclusive 416 ? UNGE_EXPR : UNGT_EXPR), 417 "DCE_COND_LB", "DCE_COND_LB_TEST", 418 conds, nconds); 419 420 if (domain.has_ub) 421 { 422 /* Now push a separator. */ 423 if (domain.has_lb) 424 conds.quick_push (NULL); 425 426 gen_one_condition (arg, domain.ub, 427 (domain.is_ub_inclusive 428 ? UNLE_EXPR : UNLT_EXPR), 429 "DCE_COND_UB", "DCE_COND_UB_TEST", 430 conds, nconds); 431 } 432 } 433 434 435 /* A helper function to generate condition 436 code for the y argument in call pow (some_const, y). 437 See candidate selection in check_pow. Since the 438 candidates' base values have a limited range, 439 the guarded code generated for y are simple: 440 if (__builtin_isgreater (y, max_y)) 441 pow (const, y); 442 Note max_y can be computed separately for each 443 const base, but in this implementation, we 444 choose to compute it using the max base 445 in the allowed range for the purpose of 446 simplicity. BASE is the constant base value, 447 EXPN is the expression for the exponent argument, 448 *CONDS is the vector to hold resulting statements, 449 and *NCONDS is the number of logical conditions. */ 450 451 static void 452 gen_conditions_for_pow_cst_base (tree base, tree expn, 453 vec<gimple *> conds, 454 unsigned *nconds) 455 { 456 inp_domain exp_domain; 457 /* Validate the range of the base constant to make 458 sure it is consistent with check_pow. */ 459 REAL_VALUE_TYPE mv; 460 REAL_VALUE_TYPE bcv = TREE_REAL_CST (base); 461 gcc_assert (!real_equal (&bcv, &dconst1) 462 && !real_less (&bcv, &dconst1)); 463 real_from_integer (&mv, TYPE_MODE (TREE_TYPE (base)), 256, UNSIGNED); 464 gcc_assert (!real_less (&mv, &bcv)); 465 466 exp_domain = get_domain (0, false, false, 467 127, true, false); 468 469 gen_conditions_for_domain (expn, exp_domain, 470 conds, nconds); 471 } 472 473 /* Generate error condition code for pow calls with 474 non constant base values. The candidates selected 475 have their base argument value converted from 476 integer (see check_pow) value (1, 2, 4 bytes), and 477 the max exp value is computed based on the size 478 of the integer type (i.e. max possible base value). 479 The resulting input domain for exp argument is thus 480 conservative (smaller than the max value allowed by 481 the runtime value of the base). BASE is the integer 482 base value, EXPN is the expression for the exponent 483 argument, *CONDS is the vector to hold resulting 484 statements, and *NCONDS is the number of logical 485 conditions. */ 486 487 static void 488 gen_conditions_for_pow_int_base (tree base, tree expn, 489 vec<gimple *> conds, 490 unsigned *nconds) 491 { 492 gimple *base_def; 493 tree base_val0; 494 tree int_type; 495 tree temp, tempn; 496 tree cst0; 497 gimple *stmt1, *stmt2; 498 int bit_sz, max_exp; 499 inp_domain exp_domain; 500 501 base_def = SSA_NAME_DEF_STMT (base); 502 base_val0 = gimple_assign_rhs1 (base_def); 503 int_type = TREE_TYPE (base_val0); 504 bit_sz = TYPE_PRECISION (int_type); 505 gcc_assert (bit_sz > 0 506 && bit_sz <= MAX_BASE_INT_BIT_SIZE); 507 508 /* Determine the max exp argument value according to 509 the size of the base integer. The max exp value 510 is conservatively estimated assuming IEEE754 double 511 precision format. */ 512 if (bit_sz == 8) 513 max_exp = 128; 514 else if (bit_sz == 16) 515 max_exp = 64; 516 else 517 { 518 gcc_assert (bit_sz == MAX_BASE_INT_BIT_SIZE); 519 max_exp = 32; 520 } 521 522 /* For pow ((double)x, y), generate the following conditions: 523 cond 1: 524 temp1 = x; 525 if (__builtin_islessequal (temp1, 0)) 526 527 cond 2: 528 temp2 = y; 529 if (__builtin_isgreater (temp2, max_exp_real_cst)) */ 530 531 /* Generate condition in reverse order -- first 532 the condition for the exp argument. */ 533 534 exp_domain = get_domain (0, false, false, 535 max_exp, true, true); 536 537 gen_conditions_for_domain (expn, exp_domain, 538 conds, nconds); 539 540 /* Now generate condition for the base argument. 541 Note it does not use the helper function 542 gen_conditions_for_domain because the base 543 type is integer. */ 544 545 /* Push a separator. */ 546 conds.quick_push (NULL); 547 548 temp = create_tmp_var (int_type, "DCE_COND1"); 549 cst0 = build_int_cst (int_type, 0); 550 stmt1 = gimple_build_assign (temp, base_val0); 551 tempn = make_ssa_name (temp, stmt1); 552 gimple_assign_set_lhs (stmt1, tempn); 553 stmt2 = gimple_build_cond (GT_EXPR, tempn, cst0, NULL_TREE, NULL_TREE); 554 555 conds.quick_push (stmt1); 556 conds.quick_push (stmt2); 557 (*nconds)++; 558 } 559 560 /* Method to generate conditional statements for guarding conditionally 561 dead calls to pow. One or more statements can be generated for 562 each logical condition. Statement groups of different conditions 563 are separated by a NULL tree and they are stored in the vec 564 conds. The number of logical conditions are stored in *nconds. 565 566 See C99 standard, 7.12.7.4:2, for description of pow (x, y). 567 The precise condition for domain errors are complex. In this 568 implementation, a simplified (but conservative) valid domain 569 for x and y are used: x is positive to avoid dom errors, while 570 y is smaller than a upper bound (depending on x) to avoid range 571 errors. Runtime code is generated to check x (if not constant) 572 and y against the valid domain. If it is out, jump to the call, 573 otherwise the call is bypassed. POW_CALL is the call statement, 574 *CONDS is a vector holding the resulting condition statements, 575 and *NCONDS is the number of logical conditions. */ 576 577 static void 578 gen_conditions_for_pow (gcall *pow_call, vec<gimple *> conds, 579 unsigned *nconds) 580 { 581 tree base, expn; 582 enum tree_code bc; 583 584 gcc_checking_assert (check_pow (pow_call)); 585 586 *nconds = 0; 587 588 base = gimple_call_arg (pow_call, 0); 589 expn = gimple_call_arg (pow_call, 1); 590 591 bc = TREE_CODE (base); 592 593 if (bc == REAL_CST) 594 gen_conditions_for_pow_cst_base (base, expn, conds, nconds); 595 else if (bc == SSA_NAME) 596 gen_conditions_for_pow_int_base (base, expn, conds, nconds); 597 else 598 gcc_unreachable (); 599 } 600 601 /* A helper routine to help computing the valid input domain 602 for a builtin function. See C99 7.12.7 for details. In this 603 implementation, we only handle single region domain. The 604 resulting region can be conservative (smaller) than the actual 605 one and rounded to integers. Some of the bounds are documented 606 in the standard, while other limit constants are computed 607 assuming IEEE floating point format (for SF and DF modes). 608 Since IEEE only sets minimum requirements for long double format, 609 different long double formats exist under different implementations 610 (e.g, 64 bit double precision (DF), 80 bit double-extended 611 precision (XF), and 128 bit quad precision (QF) ). For simplicity, 612 in this implementation, the computed bounds for long double assume 613 64 bit format (DF), and are therefore conservative. Another 614 assumption is that single precision float type is always SF mode, 615 and double type is DF mode. This function is quite 616 implementation specific, so it may not be suitable to be part of 617 builtins.c. This needs to be revisited later to see if it can 618 be leveraged in x87 assembly expansion. */ 619 620 static inp_domain 621 get_no_error_domain (enum built_in_function fnc) 622 { 623 switch (fnc) 624 { 625 /* Trig functions: return [-1, +1] */ 626 CASE_FLT_FN (BUILT_IN_ACOS): 627 CASE_FLT_FN (BUILT_IN_ASIN): 628 return get_domain (-1, true, true, 629 1, true, true); 630 /* Hyperbolic functions. */ 631 CASE_FLT_FN (BUILT_IN_ACOSH): 632 /* acosh: [1, +inf) */ 633 return get_domain (1, true, true, 634 1, false, false); 635 CASE_FLT_FN (BUILT_IN_ATANH): 636 /* atanh: (-1, +1) */ 637 return get_domain (-1, true, false, 638 1, true, false); 639 case BUILT_IN_COSHF: 640 case BUILT_IN_SINHF: 641 /* coshf: (-89, +89) */ 642 return get_domain (-89, true, false, 643 89, true, false); 644 case BUILT_IN_COSH: 645 case BUILT_IN_SINH: 646 case BUILT_IN_COSHL: 647 case BUILT_IN_SINHL: 648 /* cosh: (-710, +710) */ 649 return get_domain (-710, true, false, 650 710, true, false); 651 /* Log functions: (0, +inf) */ 652 CASE_FLT_FN (BUILT_IN_LOG): 653 CASE_FLT_FN (BUILT_IN_LOG2): 654 CASE_FLT_FN (BUILT_IN_LOG10): 655 return get_domain (0, true, false, 656 0, false, false); 657 CASE_FLT_FN (BUILT_IN_LOG1P): 658 return get_domain (-1, true, false, 659 0, false, false); 660 /* Exp functions. */ 661 case BUILT_IN_EXPF: 662 case BUILT_IN_EXPM1F: 663 /* expf: (-inf, 88) */ 664 return get_domain (-1, false, false, 665 88, true, false); 666 case BUILT_IN_EXP: 667 case BUILT_IN_EXPM1: 668 case BUILT_IN_EXPL: 669 case BUILT_IN_EXPM1L: 670 /* exp: (-inf, 709) */ 671 return get_domain (-1, false, false, 672 709, true, false); 673 case BUILT_IN_EXP2F: 674 /* exp2f: (-inf, 128) */ 675 return get_domain (-1, false, false, 676 128, true, false); 677 case BUILT_IN_EXP2: 678 case BUILT_IN_EXP2L: 679 /* exp2: (-inf, 1024) */ 680 return get_domain (-1, false, false, 681 1024, true, false); 682 case BUILT_IN_EXP10F: 683 case BUILT_IN_POW10F: 684 /* exp10f: (-inf, 38) */ 685 return get_domain (-1, false, false, 686 38, true, false); 687 case BUILT_IN_EXP10: 688 case BUILT_IN_POW10: 689 case BUILT_IN_EXP10L: 690 case BUILT_IN_POW10L: 691 /* exp10: (-inf, 308) */ 692 return get_domain (-1, false, false, 693 308, true, false); 694 /* sqrt: [0, +inf) */ 695 CASE_FLT_FN (BUILT_IN_SQRT): 696 return get_domain (0, true, true, 697 0, false, false); 698 default: 699 gcc_unreachable (); 700 } 701 702 gcc_unreachable (); 703 } 704 705 /* The function to generate shrink wrap conditions for a partially 706 dead builtin call whose return value is not used anywhere, 707 but has to be kept live due to potential error condition. 708 BI_CALL is the builtin call, CONDS is the vector of statements 709 for condition code, NCODES is the pointer to the number of 710 logical conditions. Statements belonging to different logical 711 condition are separated by NULL tree in the vector. */ 712 713 static void 714 gen_shrink_wrap_conditions (gcall *bi_call, vec<gimple *> conds, 715 unsigned int *nconds) 716 { 717 gcall *call; 718 tree fn; 719 enum built_in_function fnc; 720 721 gcc_assert (nconds && conds.exists ()); 722 gcc_assert (conds.length () == 0); 723 gcc_assert (is_gimple_call (bi_call)); 724 725 call = bi_call; 726 fn = gimple_call_fndecl (call); 727 gcc_assert (fn && DECL_BUILT_IN (fn)); 728 fnc = DECL_FUNCTION_CODE (fn); 729 *nconds = 0; 730 731 if (fnc == BUILT_IN_POW) 732 gen_conditions_for_pow (call, conds, nconds); 733 else 734 { 735 tree arg; 736 inp_domain domain = get_no_error_domain (fnc); 737 *nconds = 0; 738 arg = gimple_call_arg (bi_call, 0); 739 gen_conditions_for_domain (arg, domain, conds, nconds); 740 } 741 742 return; 743 } 744 745 746 /* Probability of the branch (to the call) is taken. */ 747 #define ERR_PROB 0.01 748 749 /* Shrink-wrap BI_CALL so that it is only called when one of the NCONDS 750 conditions in CONDS is false. 751 752 Return true on success, in which case the cfg will have been updated. */ 753 754 static bool 755 shrink_wrap_one_built_in_call_with_conds (gcall *bi_call, vec <gimple *> conds, 756 unsigned int nconds) 757 { 758 gimple_stmt_iterator bi_call_bsi; 759 basic_block bi_call_bb, join_tgt_bb, guard_bb; 760 edge join_tgt_in_edge_from_call, join_tgt_in_edge_fall_thru; 761 edge bi_call_in_edge0, guard_bb_in_edge; 762 unsigned tn_cond_stmts; 763 unsigned ci; 764 gimple *cond_expr = NULL; 765 gimple *cond_expr_start; 766 767 /* The cfg we want to create looks like this: 768 769 [guard n-1] <- guard_bb (old block) 770 | \ 771 | [guard n-2] } 772 | / \ } 773 | / ... } new blocks 774 | / [guard 0] } 775 | / / | } 776 [ call ] | <- bi_call_bb } 777 | \ | 778 | \ | 779 | [ join ] <- join_tgt_bb (old iff call must end bb) 780 | 781 possible EH edges (only if [join] is old) 782 783 When [join] is new, the immediate dominators for these blocks are: 784 785 1. [guard n-1]: unchanged 786 2. [call]: [guard n-1] 787 3. [guard m]: [guard m+1] for 0 <= m <= n-2 788 4. [join]: [guard n-1] 789 790 We punt for the more complex case case of [join] being old and 791 simply free the dominance info. We also punt on postdominators, 792 which aren't expected to be available at this point anyway. */ 793 bi_call_bb = gimple_bb (bi_call); 794 795 /* Now find the join target bb -- split bi_call_bb if needed. */ 796 if (stmt_ends_bb_p (bi_call)) 797 { 798 /* If the call must be the last in the bb, don't split the block, 799 it could e.g. have EH edges. */ 800 join_tgt_in_edge_from_call = find_fallthru_edge (bi_call_bb->succs); 801 if (join_tgt_in_edge_from_call == NULL) 802 return false; 803 free_dominance_info (CDI_DOMINATORS); 804 /* We don't want to handle PHIs. */ 805 if (EDGE_COUNT (join_tgt_in_edge_from_call->dest->preds) > 1) 806 join_tgt_bb = split_edge (join_tgt_in_edge_from_call); 807 else 808 { 809 join_tgt_bb = join_tgt_in_edge_from_call->dest; 810 /* We may have degenerate PHIs in the destination. Propagate 811 those out. */ 812 for (gphi_iterator i = gsi_start_phis (join_tgt_bb); !gsi_end_p (i);) 813 { 814 gphi *phi = i.phi (); 815 replace_uses_by (gimple_phi_result (phi), 816 gimple_phi_arg_def (phi, 0)); 817 remove_phi_node (&i, true); 818 } 819 } 820 } 821 else 822 { 823 join_tgt_in_edge_from_call = split_block (bi_call_bb, bi_call); 824 join_tgt_bb = join_tgt_in_edge_from_call->dest; 825 } 826 827 bi_call_bsi = gsi_for_stmt (bi_call); 828 829 /* Now it is time to insert the first conditional expression 830 into bi_call_bb and split this bb so that bi_call is 831 shrink-wrapped. */ 832 tn_cond_stmts = conds.length (); 833 cond_expr = NULL; 834 cond_expr_start = conds[0]; 835 for (ci = 0; ci < tn_cond_stmts; ci++) 836 { 837 gimple *c = conds[ci]; 838 gcc_assert (c || ci != 0); 839 if (!c) 840 break; 841 gsi_insert_before (&bi_call_bsi, c, GSI_SAME_STMT); 842 cond_expr = c; 843 } 844 ci++; 845 gcc_assert (cond_expr && gimple_code (cond_expr) == GIMPLE_COND); 846 847 typedef std::pair<edge, edge> edge_pair; 848 auto_vec<edge_pair, 8> edges; 849 850 bi_call_in_edge0 = split_block (bi_call_bb, cond_expr); 851 bi_call_in_edge0->flags &= ~EDGE_FALLTHRU; 852 bi_call_in_edge0->flags |= EDGE_FALSE_VALUE; 853 guard_bb = bi_call_bb; 854 bi_call_bb = bi_call_in_edge0->dest; 855 join_tgt_in_edge_fall_thru = make_edge (guard_bb, join_tgt_bb, 856 EDGE_TRUE_VALUE); 857 858 edges.reserve (nconds); 859 edges.quick_push (edge_pair (bi_call_in_edge0, join_tgt_in_edge_fall_thru)); 860 861 /* Code generation for the rest of the conditions */ 862 for (unsigned int i = 1; i < nconds; ++i) 863 { 864 unsigned ci0; 865 edge bi_call_in_edge; 866 gimple_stmt_iterator guard_bsi = gsi_for_stmt (cond_expr_start); 867 ci0 = ci; 868 cond_expr_start = conds[ci0]; 869 for (; ci < tn_cond_stmts; ci++) 870 { 871 gimple *c = conds[ci]; 872 gcc_assert (c || ci != ci0); 873 if (!c) 874 break; 875 gsi_insert_before (&guard_bsi, c, GSI_SAME_STMT); 876 cond_expr = c; 877 } 878 ci++; 879 gcc_assert (cond_expr && gimple_code (cond_expr) == GIMPLE_COND); 880 guard_bb_in_edge = split_block (guard_bb, cond_expr); 881 guard_bb_in_edge->flags &= ~EDGE_FALLTHRU; 882 guard_bb_in_edge->flags |= EDGE_TRUE_VALUE; 883 884 bi_call_in_edge = make_edge (guard_bb, bi_call_bb, EDGE_FALSE_VALUE); 885 edges.quick_push (edge_pair (bi_call_in_edge, guard_bb_in_edge)); 886 } 887 888 /* Now update the probability and profile information, processing the 889 guards in order of execution. 890 891 There are two approaches we could take here. On the one hand we 892 could assign a probability of X to the call block and distribute 893 that probability among its incoming edges. On the other hand we 894 could assign a probability of X to each individual call edge. 895 896 The choice only affects calls that have more than one condition. 897 In those cases, the second approach would give the call block 898 a greater probability than the first. However, the difference 899 is only small, and our chosen X is a pure guess anyway. 900 901 Here we take the second approach because it's slightly simpler 902 and because it's easy to see that it doesn't lose profile counts. */ 903 bi_call_bb->count = 0; 904 bi_call_bb->frequency = 0; 905 while (!edges.is_empty ()) 906 { 907 edge_pair e = edges.pop (); 908 edge call_edge = e.first; 909 edge nocall_edge = e.second; 910 basic_block src_bb = call_edge->src; 911 gcc_assert (src_bb == nocall_edge->src); 912 913 call_edge->probability = REG_BR_PROB_BASE * ERR_PROB; 914 call_edge->count = apply_probability (src_bb->count, 915 call_edge->probability); 916 nocall_edge->probability = inverse_probability (call_edge->probability); 917 nocall_edge->count = src_bb->count - call_edge->count; 918 919 unsigned int call_frequency = apply_probability (src_bb->frequency, 920 call_edge->probability); 921 922 bi_call_bb->count += call_edge->count; 923 bi_call_bb->frequency += call_frequency; 924 925 if (nocall_edge->dest != join_tgt_bb) 926 { 927 nocall_edge->dest->count = nocall_edge->count; 928 nocall_edge->dest->frequency = src_bb->frequency - call_frequency; 929 } 930 } 931 932 if (dom_info_available_p (CDI_DOMINATORS)) 933 { 934 /* The split_blocks leave [guard 0] as the immediate dominator 935 of [call] and [call] as the immediate dominator of [join]. 936 Fix them up. */ 937 set_immediate_dominator (CDI_DOMINATORS, bi_call_bb, guard_bb); 938 set_immediate_dominator (CDI_DOMINATORS, join_tgt_bb, guard_bb); 939 } 940 941 if (dump_file && (dump_flags & TDF_DETAILS)) 942 { 943 location_t loc; 944 loc = gimple_location (bi_call); 945 fprintf (dump_file, 946 "%s:%d: note: function call is shrink-wrapped" 947 " into error conditions.\n", 948 LOCATION_FILE (loc), LOCATION_LINE (loc)); 949 } 950 951 return true; 952 } 953 954 /* Shrink-wrap BI_CALL so that it is only called when it might set errno 955 (but is always called if it would set errno). 956 957 Return true on success, in which case the cfg will have been updated. */ 958 959 static bool 960 shrink_wrap_one_built_in_call (gcall *bi_call) 961 { 962 unsigned nconds = 0; 963 auto_vec<gimple *, 12> conds; 964 gen_shrink_wrap_conditions (bi_call, conds, &nconds); 965 /* This can happen if the condition generator decides 966 it is not beneficial to do the transformation. Just 967 return false and do not do any transformation for 968 the call. */ 969 if (nconds == 0) 970 return false; 971 return shrink_wrap_one_built_in_call_with_conds (bi_call, conds, nconds); 972 } 973 974 /* Return true if built-in function call CALL could be implemented using 975 a combination of an internal function to compute the result and a 976 separate call to set errno. */ 977 978 static bool 979 can_use_internal_fn (gcall *call) 980 { 981 /* Only replace calls that set errno. */ 982 if (!gimple_vdef (call)) 983 return false; 984 985 /* Punt if we can't conditionalize the call. */ 986 basic_block bb = gimple_bb (call); 987 if (stmt_ends_bb_p (call) && !find_fallthru_edge (bb->succs)) 988 return false; 989 990 /* See whether there is an internal function for this built-in. */ 991 if (replacement_internal_fn (call) == IFN_LAST) 992 return false; 993 994 /* See whether we can catch all cases where errno would be set, 995 while still avoiding the call in most cases. */ 996 if (!can_test_argument_range (call) 997 && !edom_only_function (call)) 998 return false; 999 1000 return true; 1001 } 1002 1003 /* Implement built-in function call CALL using an internal function. 1004 Return true on success, in which case the cfg will have changed. */ 1005 1006 static bool 1007 use_internal_fn (gcall *call) 1008 { 1009 unsigned nconds = 0; 1010 auto_vec<gimple *, 12> conds; 1011 if (can_test_argument_range (call)) 1012 gen_shrink_wrap_conditions (call, conds, &nconds); 1013 if (nconds == 0 && !edom_only_function (call)) 1014 return false; 1015 1016 internal_fn ifn = replacement_internal_fn (call); 1017 gcc_assert (ifn != IFN_LAST); 1018 1019 /* Construct the new call, with the same arguments as the original one. */ 1020 auto_vec <tree, 16> args; 1021 unsigned int nargs = gimple_call_num_args (call); 1022 for (unsigned int i = 0; i < nargs; ++i) 1023 args.safe_push (gimple_call_arg (call, i)); 1024 gcall *new_call = gimple_build_call_internal_vec (ifn, args); 1025 gimple_set_location (new_call, gimple_location (call)); 1026 1027 /* Transfer the LHS to the new call. */ 1028 tree lhs = gimple_call_lhs (call); 1029 gimple_call_set_lhs (new_call, lhs); 1030 gimple_call_set_lhs (call, NULL_TREE); 1031 SSA_NAME_DEF_STMT (lhs) = new_call; 1032 1033 /* Insert the new call. */ 1034 gimple_stmt_iterator gsi = gsi_for_stmt (call); 1035 gsi_insert_before (&gsi, new_call, GSI_SAME_STMT); 1036 1037 if (nconds == 0) 1038 { 1039 /* Skip the call if LHS == LHS. If we reach here, EDOM is the only 1040 valid errno value and it is used iff the result is NaN. */ 1041 conds.quick_push (gimple_build_cond (EQ_EXPR, lhs, lhs, 1042 NULL_TREE, NULL_TREE)); 1043 nconds++; 1044 1045 /* Try replacing the original call with a direct assignment to 1046 errno, via an internal function. */ 1047 if (set_edom_supported_p () && !stmt_ends_bb_p (call)) 1048 { 1049 gimple_stmt_iterator gsi = gsi_for_stmt (call); 1050 gcall *new_call = gimple_build_call_internal (IFN_SET_EDOM, 0); 1051 gimple_set_vuse (new_call, gimple_vuse (call)); 1052 gimple_set_vdef (new_call, gimple_vdef (call)); 1053 SSA_NAME_DEF_STMT (gimple_vdef (new_call)) = new_call; 1054 gimple_set_location (new_call, gimple_location (call)); 1055 gsi_replace (&gsi, new_call, false); 1056 call = new_call; 1057 } 1058 } 1059 1060 if (!shrink_wrap_one_built_in_call_with_conds (call, conds, nconds)) 1061 /* It's too late to back out now. */ 1062 gcc_unreachable (); 1063 return true; 1064 } 1065 1066 /* The top level function for conditional dead code shrink 1067 wrapping transformation. */ 1068 1069 static bool 1070 shrink_wrap_conditional_dead_built_in_calls (vec<gcall *> calls) 1071 { 1072 bool changed = false; 1073 unsigned i = 0; 1074 1075 unsigned n = calls.length (); 1076 if (n == 0) 1077 return false; 1078 1079 for (; i < n ; i++) 1080 { 1081 gcall *bi_call = calls[i]; 1082 if (gimple_call_lhs (bi_call)) 1083 changed |= use_internal_fn (bi_call); 1084 else 1085 changed |= shrink_wrap_one_built_in_call (bi_call); 1086 } 1087 1088 return changed; 1089 } 1090 1091 namespace { 1092 1093 const pass_data pass_data_call_cdce = 1094 { 1095 GIMPLE_PASS, /* type */ 1096 "cdce", /* name */ 1097 OPTGROUP_NONE, /* optinfo_flags */ 1098 TV_TREE_CALL_CDCE, /* tv_id */ 1099 ( PROP_cfg | PROP_ssa ), /* properties_required */ 1100 0, /* properties_provided */ 1101 0, /* properties_destroyed */ 1102 0, /* todo_flags_start */ 1103 0, /* todo_flags_finish */ 1104 }; 1105 1106 class pass_call_cdce : public gimple_opt_pass 1107 { 1108 public: 1109 pass_call_cdce (gcc::context *ctxt) 1110 : gimple_opt_pass (pass_data_call_cdce, ctxt) 1111 {} 1112 1113 /* opt_pass methods: */ 1114 virtual bool gate (function *) 1115 { 1116 /* The limit constants used in the implementation 1117 assume IEEE floating point format. Other formats 1118 can be supported in the future if needed. */ 1119 return flag_tree_builtin_call_dce != 0; 1120 } 1121 1122 virtual unsigned int execute (function *); 1123 1124 }; // class pass_call_cdce 1125 1126 unsigned int 1127 pass_call_cdce::execute (function *fun) 1128 { 1129 basic_block bb; 1130 gimple_stmt_iterator i; 1131 bool something_changed = false; 1132 auto_vec<gcall *> cond_dead_built_in_calls; 1133 FOR_EACH_BB_FN (bb, fun) 1134 { 1135 /* Skip blocks that are being optimized for size, since our 1136 transformation always increases code size. */ 1137 if (optimize_bb_for_size_p (bb)) 1138 continue; 1139 1140 /* Collect dead call candidates. */ 1141 for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i)) 1142 { 1143 gcall *stmt = dyn_cast <gcall *> (gsi_stmt (i)); 1144 if (stmt 1145 && gimple_call_builtin_p (stmt, BUILT_IN_NORMAL) 1146 && (gimple_call_lhs (stmt) 1147 ? can_use_internal_fn (stmt) 1148 : can_test_argument_range (stmt))) 1149 { 1150 if (dump_file && (dump_flags & TDF_DETAILS)) 1151 { 1152 fprintf (dump_file, "Found conditional dead call: "); 1153 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 1154 fprintf (dump_file, "\n"); 1155 } 1156 if (!cond_dead_built_in_calls.exists ()) 1157 cond_dead_built_in_calls.create (64); 1158 cond_dead_built_in_calls.safe_push (stmt); 1159 } 1160 } 1161 } 1162 1163 if (!cond_dead_built_in_calls.exists ()) 1164 return 0; 1165 1166 something_changed 1167 = shrink_wrap_conditional_dead_built_in_calls (cond_dead_built_in_calls); 1168 1169 if (something_changed) 1170 { 1171 free_dominance_info (CDI_POST_DOMINATORS); 1172 /* As we introduced new control-flow we need to insert PHI-nodes 1173 for the call-clobbers of the remaining call. */ 1174 mark_virtual_operands_for_renaming (fun); 1175 return TODO_update_ssa; 1176 } 1177 1178 return 0; 1179 } 1180 1181 } // anon namespace 1182 1183 gimple_opt_pass * 1184 make_pass_call_cdce (gcc::context *ctxt) 1185 { 1186 return new pass_call_cdce (ctxt); 1187 } 1188