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