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