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