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