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