1 /* Global, SSA-based optimizations using mathematical identities. 2 Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012 3 Free Software Foundation, Inc. 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 /* Currently, the only mini-pass in this file tries to CSE reciprocal 22 operations. These are common in sequences such as this one: 23 24 modulus = sqrt(x*x + y*y + z*z); 25 x = x / modulus; 26 y = y / modulus; 27 z = z / modulus; 28 29 that can be optimized to 30 31 modulus = sqrt(x*x + y*y + z*z); 32 rmodulus = 1.0 / modulus; 33 x = x * rmodulus; 34 y = y * rmodulus; 35 z = z * rmodulus; 36 37 We do this for loop invariant divisors, and with this pass whenever 38 we notice that a division has the same divisor multiple times. 39 40 Of course, like in PRE, we don't insert a division if a dominator 41 already has one. However, this cannot be done as an extension of 42 PRE for several reasons. 43 44 First of all, with some experiments it was found out that the 45 transformation is not always useful if there are only two divisions 46 hy the same divisor. This is probably because modern processors 47 can pipeline the divisions; on older, in-order processors it should 48 still be effective to optimize two divisions by the same number. 49 We make this a param, and it shall be called N in the remainder of 50 this comment. 51 52 Second, if trapping math is active, we have less freedom on where 53 to insert divisions: we can only do so in basic blocks that already 54 contain one. (If divisions don't trap, instead, we can insert 55 divisions elsewhere, which will be in blocks that are common dominators 56 of those that have the division). 57 58 We really don't want to compute the reciprocal unless a division will 59 be found. To do this, we won't insert the division in a basic block 60 that has less than N divisions *post-dominating* it. 61 62 The algorithm constructs a subset of the dominator tree, holding the 63 blocks containing the divisions and the common dominators to them, 64 and walk it twice. The first walk is in post-order, and it annotates 65 each block with the number of divisions that post-dominate it: this 66 gives information on where divisions can be inserted profitably. 67 The second walk is in pre-order, and it inserts divisions as explained 68 above, and replaces divisions by multiplications. 69 70 In the best case, the cost of the pass is O(n_statements). In the 71 worst-case, the cost is due to creating the dominator tree subset, 72 with a cost of O(n_basic_blocks ^ 2); however this can only happen 73 for n_statements / n_basic_blocks statements. So, the amortized cost 74 of creating the dominator tree subset is O(n_basic_blocks) and the 75 worst-case cost of the pass is O(n_statements * n_basic_blocks). 76 77 More practically, the cost will be small because there are few 78 divisions, and they tend to be in the same basic block, so insert_bb 79 is called very few times. 80 81 If we did this using domwalk.c, an efficient implementation would have 82 to work on all the variables in a single pass, because we could not 83 work on just a subset of the dominator tree, as we do now, and the 84 cost would also be something like O(n_statements * n_basic_blocks). 85 The data structures would be more complex in order to work on all the 86 variables in a single pass. */ 87 88 #include "config.h" 89 #include "system.h" 90 #include "coretypes.h" 91 #include "tm.h" 92 #include "flags.h" 93 #include "tree.h" 94 #include "tree-flow.h" 95 #include "timevar.h" 96 #include "tree-pass.h" 97 #include "alloc-pool.h" 98 #include "basic-block.h" 99 #include "target.h" 100 #include "gimple-pretty-print.h" 101 102 /* FIXME: RTL headers have to be included here for optabs. */ 103 #include "rtl.h" /* Because optabs.h wants enum rtx_code. */ 104 #include "expr.h" /* Because optabs.h wants sepops. */ 105 #include "optabs.h" 106 107 /* This structure represents one basic block that either computes a 108 division, or is a common dominator for basic block that compute a 109 division. */ 110 struct occurrence { 111 /* The basic block represented by this structure. */ 112 basic_block bb; 113 114 /* If non-NULL, the SSA_NAME holding the definition for a reciprocal 115 inserted in BB. */ 116 tree recip_def; 117 118 /* If non-NULL, the GIMPLE_ASSIGN for a reciprocal computation that 119 was inserted in BB. */ 120 gimple recip_def_stmt; 121 122 /* Pointer to a list of "struct occurrence"s for blocks dominated 123 by BB. */ 124 struct occurrence *children; 125 126 /* Pointer to the next "struct occurrence"s in the list of blocks 127 sharing a common dominator. */ 128 struct occurrence *next; 129 130 /* The number of divisions that are in BB before compute_merit. The 131 number of divisions that are in BB or post-dominate it after 132 compute_merit. */ 133 int num_divisions; 134 135 /* True if the basic block has a division, false if it is a common 136 dominator for basic blocks that do. If it is false and trapping 137 math is active, BB is not a candidate for inserting a reciprocal. */ 138 bool bb_has_division; 139 }; 140 141 static struct 142 { 143 /* Number of 1.0/X ops inserted. */ 144 int rdivs_inserted; 145 146 /* Number of 1.0/FUNC ops inserted. */ 147 int rfuncs_inserted; 148 } reciprocal_stats; 149 150 static struct 151 { 152 /* Number of cexpi calls inserted. */ 153 int inserted; 154 } sincos_stats; 155 156 static struct 157 { 158 /* Number of hand-written 32-bit bswaps found. */ 159 int found_32bit; 160 161 /* Number of hand-written 64-bit bswaps found. */ 162 int found_64bit; 163 } bswap_stats; 164 165 static struct 166 { 167 /* Number of widening multiplication ops inserted. */ 168 int widen_mults_inserted; 169 170 /* Number of integer multiply-and-accumulate ops inserted. */ 171 int maccs_inserted; 172 173 /* Number of fp fused multiply-add ops inserted. */ 174 int fmas_inserted; 175 } widen_mul_stats; 176 177 /* The instance of "struct occurrence" representing the highest 178 interesting block in the dominator tree. */ 179 static struct occurrence *occ_head; 180 181 /* Allocation pool for getting instances of "struct occurrence". */ 182 static alloc_pool occ_pool; 183 184 185 186 /* Allocate and return a new struct occurrence for basic block BB, and 187 whose children list is headed by CHILDREN. */ 188 static struct occurrence * 189 occ_new (basic_block bb, struct occurrence *children) 190 { 191 struct occurrence *occ; 192 193 bb->aux = occ = (struct occurrence *) pool_alloc (occ_pool); 194 memset (occ, 0, sizeof (struct occurrence)); 195 196 occ->bb = bb; 197 occ->children = children; 198 return occ; 199 } 200 201 202 /* Insert NEW_OCC into our subset of the dominator tree. P_HEAD points to a 203 list of "struct occurrence"s, one per basic block, having IDOM as 204 their common dominator. 205 206 We try to insert NEW_OCC as deep as possible in the tree, and we also 207 insert any other block that is a common dominator for BB and one 208 block already in the tree. */ 209 210 static void 211 insert_bb (struct occurrence *new_occ, basic_block idom, 212 struct occurrence **p_head) 213 { 214 struct occurrence *occ, **p_occ; 215 216 for (p_occ = p_head; (occ = *p_occ) != NULL; ) 217 { 218 basic_block bb = new_occ->bb, occ_bb = occ->bb; 219 basic_block dom = nearest_common_dominator (CDI_DOMINATORS, occ_bb, bb); 220 if (dom == bb) 221 { 222 /* BB dominates OCC_BB. OCC becomes NEW_OCC's child: remove OCC 223 from its list. */ 224 *p_occ = occ->next; 225 occ->next = new_occ->children; 226 new_occ->children = occ; 227 228 /* Try the next block (it may as well be dominated by BB). */ 229 } 230 231 else if (dom == occ_bb) 232 { 233 /* OCC_BB dominates BB. Tail recurse to look deeper. */ 234 insert_bb (new_occ, dom, &occ->children); 235 return; 236 } 237 238 else if (dom != idom) 239 { 240 gcc_assert (!dom->aux); 241 242 /* There is a dominator between IDOM and BB, add it and make 243 two children out of NEW_OCC and OCC. First, remove OCC from 244 its list. */ 245 *p_occ = occ->next; 246 new_occ->next = occ; 247 occ->next = NULL; 248 249 /* None of the previous blocks has DOM as a dominator: if we tail 250 recursed, we would reexamine them uselessly. Just switch BB with 251 DOM, and go on looking for blocks dominated by DOM. */ 252 new_occ = occ_new (dom, new_occ); 253 } 254 255 else 256 { 257 /* Nothing special, go on with the next element. */ 258 p_occ = &occ->next; 259 } 260 } 261 262 /* No place was found as a child of IDOM. Make BB a sibling of IDOM. */ 263 new_occ->next = *p_head; 264 *p_head = new_occ; 265 } 266 267 /* Register that we found a division in BB. */ 268 269 static inline void 270 register_division_in (basic_block bb) 271 { 272 struct occurrence *occ; 273 274 occ = (struct occurrence *) bb->aux; 275 if (!occ) 276 { 277 occ = occ_new (bb, NULL); 278 insert_bb (occ, ENTRY_BLOCK_PTR, &occ_head); 279 } 280 281 occ->bb_has_division = true; 282 occ->num_divisions++; 283 } 284 285 286 /* Compute the number of divisions that postdominate each block in OCC and 287 its children. */ 288 289 static void 290 compute_merit (struct occurrence *occ) 291 { 292 struct occurrence *occ_child; 293 basic_block dom = occ->bb; 294 295 for (occ_child = occ->children; occ_child; occ_child = occ_child->next) 296 { 297 basic_block bb; 298 if (occ_child->children) 299 compute_merit (occ_child); 300 301 if (flag_exceptions) 302 bb = single_noncomplex_succ (dom); 303 else 304 bb = dom; 305 306 if (dominated_by_p (CDI_POST_DOMINATORS, bb, occ_child->bb)) 307 occ->num_divisions += occ_child->num_divisions; 308 } 309 } 310 311 312 /* Return whether USE_STMT is a floating-point division by DEF. */ 313 static inline bool 314 is_division_by (gimple use_stmt, tree def) 315 { 316 return is_gimple_assign (use_stmt) 317 && gimple_assign_rhs_code (use_stmt) == RDIV_EXPR 318 && gimple_assign_rhs2 (use_stmt) == def 319 /* Do not recognize x / x as valid division, as we are getting 320 confused later by replacing all immediate uses x in such 321 a stmt. */ 322 && gimple_assign_rhs1 (use_stmt) != def; 323 } 324 325 /* Walk the subset of the dominator tree rooted at OCC, setting the 326 RECIP_DEF field to a definition of 1.0 / DEF that can be used in 327 the given basic block. The field may be left NULL, of course, 328 if it is not possible or profitable to do the optimization. 329 330 DEF_BSI is an iterator pointing at the statement defining DEF. 331 If RECIP_DEF is set, a dominator already has a computation that can 332 be used. */ 333 334 static void 335 insert_reciprocals (gimple_stmt_iterator *def_gsi, struct occurrence *occ, 336 tree def, tree recip_def, int threshold) 337 { 338 tree type; 339 gimple new_stmt; 340 gimple_stmt_iterator gsi; 341 struct occurrence *occ_child; 342 343 if (!recip_def 344 && (occ->bb_has_division || !flag_trapping_math) 345 && occ->num_divisions >= threshold) 346 { 347 /* Make a variable with the replacement and substitute it. */ 348 type = TREE_TYPE (def); 349 recip_def = make_rename_temp (type, "reciptmp"); 350 new_stmt = gimple_build_assign_with_ops (RDIV_EXPR, recip_def, 351 build_one_cst (type), def); 352 353 if (occ->bb_has_division) 354 { 355 /* Case 1: insert before an existing division. */ 356 gsi = gsi_after_labels (occ->bb); 357 while (!gsi_end_p (gsi) && !is_division_by (gsi_stmt (gsi), def)) 358 gsi_next (&gsi); 359 360 gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT); 361 } 362 else if (def_gsi && occ->bb == def_gsi->bb) 363 { 364 /* Case 2: insert right after the definition. Note that this will 365 never happen if the definition statement can throw, because in 366 that case the sole successor of the statement's basic block will 367 dominate all the uses as well. */ 368 gsi_insert_after (def_gsi, new_stmt, GSI_NEW_STMT); 369 } 370 else 371 { 372 /* Case 3: insert in a basic block not containing defs/uses. */ 373 gsi = gsi_after_labels (occ->bb); 374 gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT); 375 } 376 377 reciprocal_stats.rdivs_inserted++; 378 379 occ->recip_def_stmt = new_stmt; 380 } 381 382 occ->recip_def = recip_def; 383 for (occ_child = occ->children; occ_child; occ_child = occ_child->next) 384 insert_reciprocals (def_gsi, occ_child, def, recip_def, threshold); 385 } 386 387 388 /* Replace the division at USE_P with a multiplication by the reciprocal, if 389 possible. */ 390 391 static inline void 392 replace_reciprocal (use_operand_p use_p) 393 { 394 gimple use_stmt = USE_STMT (use_p); 395 basic_block bb = gimple_bb (use_stmt); 396 struct occurrence *occ = (struct occurrence *) bb->aux; 397 398 if (optimize_bb_for_speed_p (bb) 399 && occ->recip_def && use_stmt != occ->recip_def_stmt) 400 { 401 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt); 402 gimple_assign_set_rhs_code (use_stmt, MULT_EXPR); 403 SET_USE (use_p, occ->recip_def); 404 fold_stmt_inplace (&gsi); 405 update_stmt (use_stmt); 406 } 407 } 408 409 410 /* Free OCC and return one more "struct occurrence" to be freed. */ 411 412 static struct occurrence * 413 free_bb (struct occurrence *occ) 414 { 415 struct occurrence *child, *next; 416 417 /* First get the two pointers hanging off OCC. */ 418 next = occ->next; 419 child = occ->children; 420 occ->bb->aux = NULL; 421 pool_free (occ_pool, occ); 422 423 /* Now ensure that we don't recurse unless it is necessary. */ 424 if (!child) 425 return next; 426 else 427 { 428 while (next) 429 next = free_bb (next); 430 431 return child; 432 } 433 } 434 435 436 /* Look for floating-point divisions among DEF's uses, and try to 437 replace them by multiplications with the reciprocal. Add 438 as many statements computing the reciprocal as needed. 439 440 DEF must be a GIMPLE register of a floating-point type. */ 441 442 static void 443 execute_cse_reciprocals_1 (gimple_stmt_iterator *def_gsi, tree def) 444 { 445 use_operand_p use_p; 446 imm_use_iterator use_iter; 447 struct occurrence *occ; 448 int count = 0, threshold; 449 450 gcc_assert (FLOAT_TYPE_P (TREE_TYPE (def)) && is_gimple_reg (def)); 451 452 FOR_EACH_IMM_USE_FAST (use_p, use_iter, def) 453 { 454 gimple use_stmt = USE_STMT (use_p); 455 if (is_division_by (use_stmt, def)) 456 { 457 register_division_in (gimple_bb (use_stmt)); 458 count++; 459 } 460 } 461 462 /* Do the expensive part only if we can hope to optimize something. */ 463 threshold = targetm.min_divisions_for_recip_mul (TYPE_MODE (TREE_TYPE (def))); 464 if (count >= threshold) 465 { 466 gimple use_stmt; 467 for (occ = occ_head; occ; occ = occ->next) 468 { 469 compute_merit (occ); 470 insert_reciprocals (def_gsi, occ, def, NULL, threshold); 471 } 472 473 FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, def) 474 { 475 if (is_division_by (use_stmt, def)) 476 { 477 FOR_EACH_IMM_USE_ON_STMT (use_p, use_iter) 478 replace_reciprocal (use_p); 479 } 480 } 481 } 482 483 for (occ = occ_head; occ; ) 484 occ = free_bb (occ); 485 486 occ_head = NULL; 487 } 488 489 static bool 490 gate_cse_reciprocals (void) 491 { 492 return optimize && flag_reciprocal_math; 493 } 494 495 /* Go through all the floating-point SSA_NAMEs, and call 496 execute_cse_reciprocals_1 on each of them. */ 497 static unsigned int 498 execute_cse_reciprocals (void) 499 { 500 basic_block bb; 501 tree arg; 502 503 occ_pool = create_alloc_pool ("dominators for recip", 504 sizeof (struct occurrence), 505 n_basic_blocks / 3 + 1); 506 507 memset (&reciprocal_stats, 0, sizeof (reciprocal_stats)); 508 calculate_dominance_info (CDI_DOMINATORS); 509 calculate_dominance_info (CDI_POST_DOMINATORS); 510 511 #ifdef ENABLE_CHECKING 512 FOR_EACH_BB (bb) 513 gcc_assert (!bb->aux); 514 #endif 515 516 for (arg = DECL_ARGUMENTS (cfun->decl); arg; arg = DECL_CHAIN (arg)) 517 if (gimple_default_def (cfun, arg) 518 && FLOAT_TYPE_P (TREE_TYPE (arg)) 519 && is_gimple_reg (arg)) 520 execute_cse_reciprocals_1 (NULL, gimple_default_def (cfun, arg)); 521 522 FOR_EACH_BB (bb) 523 { 524 gimple_stmt_iterator gsi; 525 gimple phi; 526 tree def; 527 528 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 529 { 530 phi = gsi_stmt (gsi); 531 def = PHI_RESULT (phi); 532 if (FLOAT_TYPE_P (TREE_TYPE (def)) 533 && is_gimple_reg (def)) 534 execute_cse_reciprocals_1 (NULL, def); 535 } 536 537 for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 538 { 539 gimple stmt = gsi_stmt (gsi); 540 541 if (gimple_has_lhs (stmt) 542 && (def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF)) != NULL 543 && FLOAT_TYPE_P (TREE_TYPE (def)) 544 && TREE_CODE (def) == SSA_NAME) 545 execute_cse_reciprocals_1 (&gsi, def); 546 } 547 548 if (optimize_bb_for_size_p (bb)) 549 continue; 550 551 /* Scan for a/func(b) and convert it to reciprocal a*rfunc(b). */ 552 for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 553 { 554 gimple stmt = gsi_stmt (gsi); 555 tree fndecl; 556 557 if (is_gimple_assign (stmt) 558 && gimple_assign_rhs_code (stmt) == RDIV_EXPR) 559 { 560 tree arg1 = gimple_assign_rhs2 (stmt); 561 gimple stmt1; 562 563 if (TREE_CODE (arg1) != SSA_NAME) 564 continue; 565 566 stmt1 = SSA_NAME_DEF_STMT (arg1); 567 568 if (is_gimple_call (stmt1) 569 && gimple_call_lhs (stmt1) 570 && (fndecl = gimple_call_fndecl (stmt1)) 571 && (DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL 572 || DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_MD)) 573 { 574 enum built_in_function code; 575 bool md_code, fail; 576 imm_use_iterator ui; 577 use_operand_p use_p; 578 579 code = DECL_FUNCTION_CODE (fndecl); 580 md_code = DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_MD; 581 582 fndecl = targetm.builtin_reciprocal (code, md_code, false); 583 if (!fndecl) 584 continue; 585 586 /* Check that all uses of the SSA name are divisions, 587 otherwise replacing the defining statement will do 588 the wrong thing. */ 589 fail = false; 590 FOR_EACH_IMM_USE_FAST (use_p, ui, arg1) 591 { 592 gimple stmt2 = USE_STMT (use_p); 593 if (is_gimple_debug (stmt2)) 594 continue; 595 if (!is_gimple_assign (stmt2) 596 || gimple_assign_rhs_code (stmt2) != RDIV_EXPR 597 || gimple_assign_rhs1 (stmt2) == arg1 598 || gimple_assign_rhs2 (stmt2) != arg1) 599 { 600 fail = true; 601 break; 602 } 603 } 604 if (fail) 605 continue; 606 607 gimple_replace_lhs (stmt1, arg1); 608 gimple_call_set_fndecl (stmt1, fndecl); 609 update_stmt (stmt1); 610 reciprocal_stats.rfuncs_inserted++; 611 612 FOR_EACH_IMM_USE_STMT (stmt, ui, arg1) 613 { 614 gimple_stmt_iterator gsi = gsi_for_stmt (stmt); 615 gimple_assign_set_rhs_code (stmt, MULT_EXPR); 616 fold_stmt_inplace (&gsi); 617 update_stmt (stmt); 618 } 619 } 620 } 621 } 622 } 623 624 statistics_counter_event (cfun, "reciprocal divs inserted", 625 reciprocal_stats.rdivs_inserted); 626 statistics_counter_event (cfun, "reciprocal functions inserted", 627 reciprocal_stats.rfuncs_inserted); 628 629 free_dominance_info (CDI_DOMINATORS); 630 free_dominance_info (CDI_POST_DOMINATORS); 631 free_alloc_pool (occ_pool); 632 return 0; 633 } 634 635 struct gimple_opt_pass pass_cse_reciprocals = 636 { 637 { 638 GIMPLE_PASS, 639 "recip", /* name */ 640 gate_cse_reciprocals, /* gate */ 641 execute_cse_reciprocals, /* execute */ 642 NULL, /* sub */ 643 NULL, /* next */ 644 0, /* static_pass_number */ 645 TV_NONE, /* tv_id */ 646 PROP_ssa, /* properties_required */ 647 0, /* properties_provided */ 648 0, /* properties_destroyed */ 649 0, /* todo_flags_start */ 650 TODO_update_ssa | TODO_verify_ssa 651 | TODO_verify_stmts /* todo_flags_finish */ 652 } 653 }; 654 655 /* Records an occurrence at statement USE_STMT in the vector of trees 656 STMTS if it is dominated by *TOP_BB or dominates it or this basic block 657 is not yet initialized. Returns true if the occurrence was pushed on 658 the vector. Adjusts *TOP_BB to be the basic block dominating all 659 statements in the vector. */ 660 661 static bool 662 maybe_record_sincos (VEC(gimple, heap) **stmts, 663 basic_block *top_bb, gimple use_stmt) 664 { 665 basic_block use_bb = gimple_bb (use_stmt); 666 if (*top_bb 667 && (*top_bb == use_bb 668 || dominated_by_p (CDI_DOMINATORS, use_bb, *top_bb))) 669 VEC_safe_push (gimple, heap, *stmts, use_stmt); 670 else if (!*top_bb 671 || dominated_by_p (CDI_DOMINATORS, *top_bb, use_bb)) 672 { 673 VEC_safe_push (gimple, heap, *stmts, use_stmt); 674 *top_bb = use_bb; 675 } 676 else 677 return false; 678 679 return true; 680 } 681 682 /* Look for sin, cos and cexpi calls with the same argument NAME and 683 create a single call to cexpi CSEing the result in this case. 684 We first walk over all immediate uses of the argument collecting 685 statements that we can CSE in a vector and in a second pass replace 686 the statement rhs with a REALPART or IMAGPART expression on the 687 result of the cexpi call we insert before the use statement that 688 dominates all other candidates. */ 689 690 static bool 691 execute_cse_sincos_1 (tree name) 692 { 693 gimple_stmt_iterator gsi; 694 imm_use_iterator use_iter; 695 tree fndecl, res, type; 696 gimple def_stmt, use_stmt, stmt; 697 int seen_cos = 0, seen_sin = 0, seen_cexpi = 0; 698 VEC(gimple, heap) *stmts = NULL; 699 basic_block top_bb = NULL; 700 int i; 701 bool cfg_changed = false; 702 703 type = TREE_TYPE (name); 704 FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, name) 705 { 706 if (gimple_code (use_stmt) != GIMPLE_CALL 707 || !gimple_call_lhs (use_stmt) 708 || !(fndecl = gimple_call_fndecl (use_stmt)) 709 || DECL_BUILT_IN_CLASS (fndecl) != BUILT_IN_NORMAL) 710 continue; 711 712 switch (DECL_FUNCTION_CODE (fndecl)) 713 { 714 CASE_FLT_FN (BUILT_IN_COS): 715 seen_cos |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0; 716 break; 717 718 CASE_FLT_FN (BUILT_IN_SIN): 719 seen_sin |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0; 720 break; 721 722 CASE_FLT_FN (BUILT_IN_CEXPI): 723 seen_cexpi |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0; 724 break; 725 726 default:; 727 } 728 } 729 730 if (seen_cos + seen_sin + seen_cexpi <= 1) 731 { 732 VEC_free(gimple, heap, stmts); 733 return false; 734 } 735 736 /* Simply insert cexpi at the beginning of top_bb but not earlier than 737 the name def statement. */ 738 fndecl = mathfn_built_in (type, BUILT_IN_CEXPI); 739 if (!fndecl) 740 return false; 741 res = create_tmp_reg (TREE_TYPE (TREE_TYPE (fndecl)), "sincostmp"); 742 stmt = gimple_build_call (fndecl, 1, name); 743 res = make_ssa_name (res, stmt); 744 gimple_call_set_lhs (stmt, res); 745 746 def_stmt = SSA_NAME_DEF_STMT (name); 747 if (!SSA_NAME_IS_DEFAULT_DEF (name) 748 && gimple_code (def_stmt) != GIMPLE_PHI 749 && gimple_bb (def_stmt) == top_bb) 750 { 751 gsi = gsi_for_stmt (def_stmt); 752 gsi_insert_after (&gsi, stmt, GSI_SAME_STMT); 753 } 754 else 755 { 756 gsi = gsi_after_labels (top_bb); 757 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT); 758 } 759 update_stmt (stmt); 760 sincos_stats.inserted++; 761 762 /* And adjust the recorded old call sites. */ 763 for (i = 0; VEC_iterate(gimple, stmts, i, use_stmt); ++i) 764 { 765 tree rhs = NULL; 766 fndecl = gimple_call_fndecl (use_stmt); 767 768 switch (DECL_FUNCTION_CODE (fndecl)) 769 { 770 CASE_FLT_FN (BUILT_IN_COS): 771 rhs = fold_build1 (REALPART_EXPR, type, res); 772 break; 773 774 CASE_FLT_FN (BUILT_IN_SIN): 775 rhs = fold_build1 (IMAGPART_EXPR, type, res); 776 break; 777 778 CASE_FLT_FN (BUILT_IN_CEXPI): 779 rhs = res; 780 break; 781 782 default:; 783 gcc_unreachable (); 784 } 785 786 /* Replace call with a copy. */ 787 stmt = gimple_build_assign (gimple_call_lhs (use_stmt), rhs); 788 789 gsi = gsi_for_stmt (use_stmt); 790 gsi_replace (&gsi, stmt, true); 791 if (gimple_purge_dead_eh_edges (gimple_bb (stmt))) 792 cfg_changed = true; 793 } 794 795 VEC_free(gimple, heap, stmts); 796 797 return cfg_changed; 798 } 799 800 /* To evaluate powi(x,n), the floating point value x raised to the 801 constant integer exponent n, we use a hybrid algorithm that 802 combines the "window method" with look-up tables. For an 803 introduction to exponentiation algorithms and "addition chains", 804 see section 4.6.3, "Evaluation of Powers" of Donald E. Knuth, 805 "Seminumerical Algorithms", Vol. 2, "The Art of Computer Programming", 806 3rd Edition, 1998, and Daniel M. Gordon, "A Survey of Fast Exponentiation 807 Methods", Journal of Algorithms, Vol. 27, pp. 129-146, 1998. */ 808 809 /* Provide a default value for POWI_MAX_MULTS, the maximum number of 810 multiplications to inline before calling the system library's pow 811 function. powi(x,n) requires at worst 2*bits(n)-2 multiplications, 812 so this default never requires calling pow, powf or powl. */ 813 814 #ifndef POWI_MAX_MULTS 815 #define POWI_MAX_MULTS (2*HOST_BITS_PER_WIDE_INT-2) 816 #endif 817 818 /* The size of the "optimal power tree" lookup table. All 819 exponents less than this value are simply looked up in the 820 powi_table below. This threshold is also used to size the 821 cache of pseudo registers that hold intermediate results. */ 822 #define POWI_TABLE_SIZE 256 823 824 /* The size, in bits of the window, used in the "window method" 825 exponentiation algorithm. This is equivalent to a radix of 826 (1<<POWI_WINDOW_SIZE) in the corresponding "m-ary method". */ 827 #define POWI_WINDOW_SIZE 3 828 829 /* The following table is an efficient representation of an 830 "optimal power tree". For each value, i, the corresponding 831 value, j, in the table states than an optimal evaluation 832 sequence for calculating pow(x,i) can be found by evaluating 833 pow(x,j)*pow(x,i-j). An optimal power tree for the first 834 100 integers is given in Knuth's "Seminumerical algorithms". */ 835 836 static const unsigned char powi_table[POWI_TABLE_SIZE] = 837 { 838 0, 1, 1, 2, 2, 3, 3, 4, /* 0 - 7 */ 839 4, 6, 5, 6, 6, 10, 7, 9, /* 8 - 15 */ 840 8, 16, 9, 16, 10, 12, 11, 13, /* 16 - 23 */ 841 12, 17, 13, 18, 14, 24, 15, 26, /* 24 - 31 */ 842 16, 17, 17, 19, 18, 33, 19, 26, /* 32 - 39 */ 843 20, 25, 21, 40, 22, 27, 23, 44, /* 40 - 47 */ 844 24, 32, 25, 34, 26, 29, 27, 44, /* 48 - 55 */ 845 28, 31, 29, 34, 30, 60, 31, 36, /* 56 - 63 */ 846 32, 64, 33, 34, 34, 46, 35, 37, /* 64 - 71 */ 847 36, 65, 37, 50, 38, 48, 39, 69, /* 72 - 79 */ 848 40, 49, 41, 43, 42, 51, 43, 58, /* 80 - 87 */ 849 44, 64, 45, 47, 46, 59, 47, 76, /* 88 - 95 */ 850 48, 65, 49, 66, 50, 67, 51, 66, /* 96 - 103 */ 851 52, 70, 53, 74, 54, 104, 55, 74, /* 104 - 111 */ 852 56, 64, 57, 69, 58, 78, 59, 68, /* 112 - 119 */ 853 60, 61, 61, 80, 62, 75, 63, 68, /* 120 - 127 */ 854 64, 65, 65, 128, 66, 129, 67, 90, /* 128 - 135 */ 855 68, 73, 69, 131, 70, 94, 71, 88, /* 136 - 143 */ 856 72, 128, 73, 98, 74, 132, 75, 121, /* 144 - 151 */ 857 76, 102, 77, 124, 78, 132, 79, 106, /* 152 - 159 */ 858 80, 97, 81, 160, 82, 99, 83, 134, /* 160 - 167 */ 859 84, 86, 85, 95, 86, 160, 87, 100, /* 168 - 175 */ 860 88, 113, 89, 98, 90, 107, 91, 122, /* 176 - 183 */ 861 92, 111, 93, 102, 94, 126, 95, 150, /* 184 - 191 */ 862 96, 128, 97, 130, 98, 133, 99, 195, /* 192 - 199 */ 863 100, 128, 101, 123, 102, 164, 103, 138, /* 200 - 207 */ 864 104, 145, 105, 146, 106, 109, 107, 149, /* 208 - 215 */ 865 108, 200, 109, 146, 110, 170, 111, 157, /* 216 - 223 */ 866 112, 128, 113, 130, 114, 182, 115, 132, /* 224 - 231 */ 867 116, 200, 117, 132, 118, 158, 119, 206, /* 232 - 239 */ 868 120, 240, 121, 162, 122, 147, 123, 152, /* 240 - 247 */ 869 124, 166, 125, 214, 126, 138, 127, 153, /* 248 - 255 */ 870 }; 871 872 873 /* Return the number of multiplications required to calculate 874 powi(x,n) where n is less than POWI_TABLE_SIZE. This is a 875 subroutine of powi_cost. CACHE is an array indicating 876 which exponents have already been calculated. */ 877 878 static int 879 powi_lookup_cost (unsigned HOST_WIDE_INT n, bool *cache) 880 { 881 /* If we've already calculated this exponent, then this evaluation 882 doesn't require any additional multiplications. */ 883 if (cache[n]) 884 return 0; 885 886 cache[n] = true; 887 return powi_lookup_cost (n - powi_table[n], cache) 888 + powi_lookup_cost (powi_table[n], cache) + 1; 889 } 890 891 /* Return the number of multiplications required to calculate 892 powi(x,n) for an arbitrary x, given the exponent N. This 893 function needs to be kept in sync with powi_as_mults below. */ 894 895 static int 896 powi_cost (HOST_WIDE_INT n) 897 { 898 bool cache[POWI_TABLE_SIZE]; 899 unsigned HOST_WIDE_INT digit; 900 unsigned HOST_WIDE_INT val; 901 int result; 902 903 if (n == 0) 904 return 0; 905 906 /* Ignore the reciprocal when calculating the cost. */ 907 val = (n < 0) ? -n : n; 908 909 /* Initialize the exponent cache. */ 910 memset (cache, 0, POWI_TABLE_SIZE * sizeof (bool)); 911 cache[1] = true; 912 913 result = 0; 914 915 while (val >= POWI_TABLE_SIZE) 916 { 917 if (val & 1) 918 { 919 digit = val & ((1 << POWI_WINDOW_SIZE) - 1); 920 result += powi_lookup_cost (digit, cache) 921 + POWI_WINDOW_SIZE + 1; 922 val >>= POWI_WINDOW_SIZE; 923 } 924 else 925 { 926 val >>= 1; 927 result++; 928 } 929 } 930 931 return result + powi_lookup_cost (val, cache); 932 } 933 934 /* Recursive subroutine of powi_as_mults. This function takes the 935 array, CACHE, of already calculated exponents and an exponent N and 936 returns a tree that corresponds to CACHE[1]**N, with type TYPE. */ 937 938 static tree 939 powi_as_mults_1 (gimple_stmt_iterator *gsi, location_t loc, tree type, 940 HOST_WIDE_INT n, tree *cache, tree target) 941 { 942 tree op0, op1, ssa_target; 943 unsigned HOST_WIDE_INT digit; 944 gimple mult_stmt; 945 946 if (n < POWI_TABLE_SIZE && cache[n]) 947 return cache[n]; 948 949 ssa_target = make_ssa_name (target, NULL); 950 951 if (n < POWI_TABLE_SIZE) 952 { 953 cache[n] = ssa_target; 954 op0 = powi_as_mults_1 (gsi, loc, type, n - powi_table[n], cache, target); 955 op1 = powi_as_mults_1 (gsi, loc, type, powi_table[n], cache, target); 956 } 957 else if (n & 1) 958 { 959 digit = n & ((1 << POWI_WINDOW_SIZE) - 1); 960 op0 = powi_as_mults_1 (gsi, loc, type, n - digit, cache, target); 961 op1 = powi_as_mults_1 (gsi, loc, type, digit, cache, target); 962 } 963 else 964 { 965 op0 = powi_as_mults_1 (gsi, loc, type, n >> 1, cache, target); 966 op1 = op0; 967 } 968 969 mult_stmt = gimple_build_assign_with_ops (MULT_EXPR, ssa_target, op0, op1); 970 gimple_set_location (mult_stmt, loc); 971 gsi_insert_before (gsi, mult_stmt, GSI_SAME_STMT); 972 973 return ssa_target; 974 } 975 976 /* Convert ARG0**N to a tree of multiplications of ARG0 with itself. 977 This function needs to be kept in sync with powi_cost above. */ 978 979 static tree 980 powi_as_mults (gimple_stmt_iterator *gsi, location_t loc, 981 tree arg0, HOST_WIDE_INT n) 982 { 983 tree cache[POWI_TABLE_SIZE], result, type = TREE_TYPE (arg0), target; 984 gimple div_stmt; 985 986 if (n == 0) 987 return build_real (type, dconst1); 988 989 memset (cache, 0, sizeof (cache)); 990 cache[1] = arg0; 991 992 target = create_tmp_reg (type, "powmult"); 993 add_referenced_var (target); 994 995 result = powi_as_mults_1 (gsi, loc, type, (n < 0) ? -n : n, cache, target); 996 997 if (n >= 0) 998 return result; 999 1000 /* If the original exponent was negative, reciprocate the result. */ 1001 target = make_ssa_name (target, NULL); 1002 div_stmt = gimple_build_assign_with_ops (RDIV_EXPR, target, 1003 build_real (type, dconst1), 1004 result); 1005 gimple_set_location (div_stmt, loc); 1006 gsi_insert_before (gsi, div_stmt, GSI_SAME_STMT); 1007 1008 return target; 1009 } 1010 1011 /* ARG0 and N are the two arguments to a powi builtin in GSI with 1012 location info LOC. If the arguments are appropriate, create an 1013 equivalent sequence of statements prior to GSI using an optimal 1014 number of multiplications, and return an expession holding the 1015 result. */ 1016 1017 static tree 1018 gimple_expand_builtin_powi (gimple_stmt_iterator *gsi, location_t loc, 1019 tree arg0, HOST_WIDE_INT n) 1020 { 1021 /* Avoid largest negative number. */ 1022 if (n != -n 1023 && ((n >= -1 && n <= 2) 1024 || (optimize_function_for_speed_p (cfun) 1025 && powi_cost (n) <= POWI_MAX_MULTS))) 1026 return powi_as_mults (gsi, loc, arg0, n); 1027 1028 return NULL_TREE; 1029 } 1030 1031 /* Build a gimple call statement that calls FN with argument ARG. 1032 Set the lhs of the call statement to a fresh SSA name for 1033 variable VAR. If VAR is NULL, first allocate it. Insert the 1034 statement prior to GSI's current position, and return the fresh 1035 SSA name. */ 1036 1037 static tree 1038 build_and_insert_call (gimple_stmt_iterator *gsi, location_t loc, 1039 tree *var, tree fn, tree arg) 1040 { 1041 gimple call_stmt; 1042 tree ssa_target; 1043 1044 if (!*var) 1045 { 1046 *var = create_tmp_reg (TREE_TYPE (arg), "powroot"); 1047 add_referenced_var (*var); 1048 } 1049 1050 call_stmt = gimple_build_call (fn, 1, arg); 1051 ssa_target = make_ssa_name (*var, NULL); 1052 gimple_set_lhs (call_stmt, ssa_target); 1053 gimple_set_location (call_stmt, loc); 1054 gsi_insert_before (gsi, call_stmt, GSI_SAME_STMT); 1055 1056 return ssa_target; 1057 } 1058 1059 /* Build a gimple binary operation with the given CODE and arguments 1060 ARG0, ARG1, assigning the result to a new SSA name for variable 1061 TARGET. Insert the statement prior to GSI's current position, and 1062 return the fresh SSA name.*/ 1063 1064 static tree 1065 build_and_insert_binop (gimple_stmt_iterator *gsi, location_t loc, 1066 tree target, enum tree_code code, tree arg0, tree arg1) 1067 { 1068 tree result = make_ssa_name (target, NULL); 1069 gimple stmt = gimple_build_assign_with_ops (code, result, arg0, arg1); 1070 gimple_set_location (stmt, loc); 1071 gsi_insert_before (gsi, stmt, GSI_SAME_STMT); 1072 return result; 1073 } 1074 1075 /* Build a gimple reference operation with the given CODE and argument 1076 ARG, assigning the result to a new SSA name for variable TARGET. 1077 Insert the statement prior to GSI's current position, and return 1078 the fresh SSA name. */ 1079 1080 static inline tree 1081 build_and_insert_ref (gimple_stmt_iterator *gsi, location_t loc, tree type, 1082 tree target, enum tree_code code, tree arg0) 1083 { 1084 tree result = make_ssa_name (target, NULL); 1085 gimple stmt = gimple_build_assign (result, build1 (code, type, arg0)); 1086 gimple_set_location (stmt, loc); 1087 gsi_insert_before (gsi, stmt, GSI_SAME_STMT); 1088 return result; 1089 } 1090 1091 /* Build a gimple assignment to cast VAL to TARGET. Insert the statement 1092 prior to GSI's current position, and return the fresh SSA name. */ 1093 1094 static tree 1095 build_and_insert_cast (gimple_stmt_iterator *gsi, location_t loc, 1096 tree target, tree val) 1097 { 1098 return build_and_insert_binop (gsi, loc, target, CONVERT_EXPR, val, NULL); 1099 } 1100 1101 /* ARG0 and ARG1 are the two arguments to a pow builtin call in GSI 1102 with location info LOC. If possible, create an equivalent and 1103 less expensive sequence of statements prior to GSI, and return an 1104 expession holding the result. */ 1105 1106 static tree 1107 gimple_expand_builtin_pow (gimple_stmt_iterator *gsi, location_t loc, 1108 tree arg0, tree arg1) 1109 { 1110 REAL_VALUE_TYPE c, cint, dconst1_4, dconst3_4, dconst1_3, dconst1_6; 1111 REAL_VALUE_TYPE c2, dconst3; 1112 HOST_WIDE_INT n; 1113 tree type, sqrtfn, cbrtfn, sqrt_arg0, sqrt_sqrt, result, cbrt_x, powi_cbrt_x; 1114 tree target = NULL_TREE; 1115 enum machine_mode mode; 1116 bool hw_sqrt_exists, c_is_int, c2_is_int; 1117 1118 /* If the exponent isn't a constant, there's nothing of interest 1119 to be done. */ 1120 if (TREE_CODE (arg1) != REAL_CST) 1121 return NULL_TREE; 1122 1123 /* If the exponent is equivalent to an integer, expand to an optimal 1124 multiplication sequence when profitable. */ 1125 c = TREE_REAL_CST (arg1); 1126 n = real_to_integer (&c); 1127 real_from_integer (&cint, VOIDmode, n, n < 0 ? -1 : 0, 0); 1128 c_is_int = real_identical (&c, &cint); 1129 1130 if (c_is_int 1131 && ((n >= -1 && n <= 2) 1132 || (flag_unsafe_math_optimizations 1133 && optimize_insn_for_speed_p () 1134 && powi_cost (n) <= POWI_MAX_MULTS))) 1135 return gimple_expand_builtin_powi (gsi, loc, arg0, n); 1136 1137 /* Attempt various optimizations using sqrt and cbrt. */ 1138 type = TREE_TYPE (arg0); 1139 mode = TYPE_MODE (type); 1140 sqrtfn = mathfn_built_in (type, BUILT_IN_SQRT); 1141 1142 /* Optimize pow(x,0.5) = sqrt(x). This replacement is always safe 1143 unless signed zeros must be maintained. pow(-0,0.5) = +0, while 1144 sqrt(-0) = -0. */ 1145 if (sqrtfn 1146 && REAL_VALUES_EQUAL (c, dconsthalf) 1147 && !HONOR_SIGNED_ZEROS (mode)) 1148 return build_and_insert_call (gsi, loc, &target, sqrtfn, arg0); 1149 1150 /* Optimize pow(x,0.25) = sqrt(sqrt(x)). Assume on most machines that 1151 a builtin sqrt instruction is smaller than a call to pow with 0.25, 1152 so do this optimization even if -Os. Don't do this optimization 1153 if we don't have a hardware sqrt insn. */ 1154 dconst1_4 = dconst1; 1155 SET_REAL_EXP (&dconst1_4, REAL_EXP (&dconst1_4) - 2); 1156 hw_sqrt_exists = optab_handler (sqrt_optab, mode) != CODE_FOR_nothing; 1157 1158 if (flag_unsafe_math_optimizations 1159 && sqrtfn 1160 && REAL_VALUES_EQUAL (c, dconst1_4) 1161 && hw_sqrt_exists) 1162 { 1163 /* sqrt(x) */ 1164 sqrt_arg0 = build_and_insert_call (gsi, loc, &target, sqrtfn, arg0); 1165 1166 /* sqrt(sqrt(x)) */ 1167 return build_and_insert_call (gsi, loc, &target, sqrtfn, sqrt_arg0); 1168 } 1169 1170 /* Optimize pow(x,0.75) = sqrt(x) * sqrt(sqrt(x)) unless we are 1171 optimizing for space. Don't do this optimization if we don't have 1172 a hardware sqrt insn. */ 1173 real_from_integer (&dconst3_4, VOIDmode, 3, 0, 0); 1174 SET_REAL_EXP (&dconst3_4, REAL_EXP (&dconst3_4) - 2); 1175 1176 if (flag_unsafe_math_optimizations 1177 && sqrtfn 1178 && optimize_function_for_speed_p (cfun) 1179 && REAL_VALUES_EQUAL (c, dconst3_4) 1180 && hw_sqrt_exists) 1181 { 1182 /* sqrt(x) */ 1183 sqrt_arg0 = build_and_insert_call (gsi, loc, &target, sqrtfn, arg0); 1184 1185 /* sqrt(sqrt(x)) */ 1186 sqrt_sqrt = build_and_insert_call (gsi, loc, &target, sqrtfn, sqrt_arg0); 1187 1188 /* sqrt(x) * sqrt(sqrt(x)) */ 1189 return build_and_insert_binop (gsi, loc, target, MULT_EXPR, 1190 sqrt_arg0, sqrt_sqrt); 1191 } 1192 1193 /* Optimize pow(x,1./3.) = cbrt(x). This requires unsafe math 1194 optimizations since 1./3. is not exactly representable. If x 1195 is negative and finite, the correct value of pow(x,1./3.) is 1196 a NaN with the "invalid" exception raised, because the value 1197 of 1./3. actually has an even denominator. The correct value 1198 of cbrt(x) is a negative real value. */ 1199 cbrtfn = mathfn_built_in (type, BUILT_IN_CBRT); 1200 dconst1_3 = real_value_truncate (mode, dconst_third ()); 1201 1202 if (flag_unsafe_math_optimizations 1203 && cbrtfn 1204 && (gimple_val_nonnegative_real_p (arg0) || !HONOR_NANS (mode)) 1205 && REAL_VALUES_EQUAL (c, dconst1_3)) 1206 return build_and_insert_call (gsi, loc, &target, cbrtfn, arg0); 1207 1208 /* Optimize pow(x,1./6.) = cbrt(sqrt(x)). Don't do this optimization 1209 if we don't have a hardware sqrt insn. */ 1210 dconst1_6 = dconst1_3; 1211 SET_REAL_EXP (&dconst1_6, REAL_EXP (&dconst1_6) - 1); 1212 1213 if (flag_unsafe_math_optimizations 1214 && sqrtfn 1215 && cbrtfn 1216 && (gimple_val_nonnegative_real_p (arg0) || !HONOR_NANS (mode)) 1217 && optimize_function_for_speed_p (cfun) 1218 && hw_sqrt_exists 1219 && REAL_VALUES_EQUAL (c, dconst1_6)) 1220 { 1221 /* sqrt(x) */ 1222 sqrt_arg0 = build_and_insert_call (gsi, loc, &target, sqrtfn, arg0); 1223 1224 /* cbrt(sqrt(x)) */ 1225 return build_and_insert_call (gsi, loc, &target, cbrtfn, sqrt_arg0); 1226 } 1227 1228 /* Optimize pow(x,c), where n = 2c for some nonzero integer n 1229 and c not an integer, into 1230 1231 sqrt(x) * powi(x, n/2), n > 0; 1232 1.0 / (sqrt(x) * powi(x, abs(n/2))), n < 0. 1233 1234 Do not calculate the powi factor when n/2 = 0. */ 1235 real_arithmetic (&c2, MULT_EXPR, &c, &dconst2); 1236 n = real_to_integer (&c2); 1237 real_from_integer (&cint, VOIDmode, n, n < 0 ? -1 : 0, 0); 1238 c2_is_int = real_identical (&c2, &cint); 1239 1240 if (flag_unsafe_math_optimizations 1241 && sqrtfn 1242 && c2_is_int 1243 && !c_is_int 1244 && optimize_function_for_speed_p (cfun)) 1245 { 1246 tree powi_x_ndiv2 = NULL_TREE; 1247 1248 /* Attempt to fold powi(arg0, abs(n/2)) into multiplies. If not 1249 possible or profitable, give up. Skip the degenerate case when 1250 n is 1 or -1, where the result is always 1. */ 1251 if (absu_hwi (n) != 1) 1252 { 1253 powi_x_ndiv2 = gimple_expand_builtin_powi (gsi, loc, arg0, 1254 abs_hwi (n / 2)); 1255 if (!powi_x_ndiv2) 1256 return NULL_TREE; 1257 } 1258 1259 /* Calculate sqrt(x). When n is not 1 or -1, multiply it by the 1260 result of the optimal multiply sequence just calculated. */ 1261 sqrt_arg0 = build_and_insert_call (gsi, loc, &target, sqrtfn, arg0); 1262 1263 if (absu_hwi (n) == 1) 1264 result = sqrt_arg0; 1265 else 1266 result = build_and_insert_binop (gsi, loc, target, MULT_EXPR, 1267 sqrt_arg0, powi_x_ndiv2); 1268 1269 /* If n is negative, reciprocate the result. */ 1270 if (n < 0) 1271 result = build_and_insert_binop (gsi, loc, target, RDIV_EXPR, 1272 build_real (type, dconst1), result); 1273 return result; 1274 } 1275 1276 /* Optimize pow(x,c), where 3c = n for some nonzero integer n, into 1277 1278 powi(x, n/3) * powi(cbrt(x), n%3), n > 0; 1279 1.0 / (powi(x, abs(n)/3) * powi(cbrt(x), abs(n)%3)), n < 0. 1280 1281 Do not calculate the first factor when n/3 = 0. As cbrt(x) is 1282 different from pow(x, 1./3.) due to rounding and behavior with 1283 negative x, we need to constrain this transformation to unsafe 1284 math and positive x or finite math. */ 1285 real_from_integer (&dconst3, VOIDmode, 3, 0, 0); 1286 real_arithmetic (&c2, MULT_EXPR, &c, &dconst3); 1287 real_round (&c2, mode, &c2); 1288 n = real_to_integer (&c2); 1289 real_from_integer (&cint, VOIDmode, n, n < 0 ? -1 : 0, 0); 1290 real_arithmetic (&c2, RDIV_EXPR, &cint, &dconst3); 1291 real_convert (&c2, mode, &c2); 1292 1293 if (flag_unsafe_math_optimizations 1294 && cbrtfn 1295 && (gimple_val_nonnegative_real_p (arg0) || !HONOR_NANS (mode)) 1296 && real_identical (&c2, &c) 1297 && !c2_is_int 1298 && optimize_function_for_speed_p (cfun) 1299 && powi_cost (n / 3) <= POWI_MAX_MULTS) 1300 { 1301 tree powi_x_ndiv3 = NULL_TREE; 1302 1303 /* Attempt to fold powi(arg0, abs(n/3)) into multiplies. If not 1304 possible or profitable, give up. Skip the degenerate case when 1305 abs(n) < 3, where the result is always 1. */ 1306 if (absu_hwi (n) >= 3) 1307 { 1308 powi_x_ndiv3 = gimple_expand_builtin_powi (gsi, loc, arg0, 1309 abs_hwi (n / 3)); 1310 if (!powi_x_ndiv3) 1311 return NULL_TREE; 1312 } 1313 1314 /* Calculate powi(cbrt(x), n%3). Don't use gimple_expand_builtin_powi 1315 as that creates an unnecessary variable. Instead, just produce 1316 either cbrt(x) or cbrt(x) * cbrt(x). */ 1317 cbrt_x = build_and_insert_call (gsi, loc, &target, cbrtfn, arg0); 1318 1319 if (absu_hwi (n) % 3 == 1) 1320 powi_cbrt_x = cbrt_x; 1321 else 1322 powi_cbrt_x = build_and_insert_binop (gsi, loc, target, MULT_EXPR, 1323 cbrt_x, cbrt_x); 1324 1325 /* Multiply the two subexpressions, unless powi(x,abs(n)/3) = 1. */ 1326 if (absu_hwi (n) < 3) 1327 result = powi_cbrt_x; 1328 else 1329 result = build_and_insert_binop (gsi, loc, target, MULT_EXPR, 1330 powi_x_ndiv3, powi_cbrt_x); 1331 1332 /* If n is negative, reciprocate the result. */ 1333 if (n < 0) 1334 result = build_and_insert_binop (gsi, loc, target, RDIV_EXPR, 1335 build_real (type, dconst1), result); 1336 1337 return result; 1338 } 1339 1340 /* No optimizations succeeded. */ 1341 return NULL_TREE; 1342 } 1343 1344 /* ARG is the argument to a cabs builtin call in GSI with location info 1345 LOC. Create a sequence of statements prior to GSI that calculates 1346 sqrt(R*R + I*I), where R and I are the real and imaginary components 1347 of ARG, respectively. Return an expression holding the result. */ 1348 1349 static tree 1350 gimple_expand_builtin_cabs (gimple_stmt_iterator *gsi, location_t loc, tree arg) 1351 { 1352 tree target, real_part, imag_part, addend1, addend2, sum, result; 1353 tree type = TREE_TYPE (TREE_TYPE (arg)); 1354 tree sqrtfn = mathfn_built_in (type, BUILT_IN_SQRT); 1355 enum machine_mode mode = TYPE_MODE (type); 1356 1357 if (!flag_unsafe_math_optimizations 1358 || !optimize_bb_for_speed_p (gimple_bb (gsi_stmt (*gsi))) 1359 || !sqrtfn 1360 || optab_handler (sqrt_optab, mode) == CODE_FOR_nothing) 1361 return NULL_TREE; 1362 1363 target = create_tmp_reg (type, "cabs"); 1364 add_referenced_var (target); 1365 1366 real_part = build_and_insert_ref (gsi, loc, type, target, 1367 REALPART_EXPR, arg); 1368 addend1 = build_and_insert_binop (gsi, loc, target, MULT_EXPR, 1369 real_part, real_part); 1370 imag_part = build_and_insert_ref (gsi, loc, type, target, 1371 IMAGPART_EXPR, arg); 1372 addend2 = build_and_insert_binop (gsi, loc, target, MULT_EXPR, 1373 imag_part, imag_part); 1374 sum = build_and_insert_binop (gsi, loc, target, PLUS_EXPR, addend1, addend2); 1375 result = build_and_insert_call (gsi, loc, &target, sqrtfn, sum); 1376 1377 return result; 1378 } 1379 1380 /* Go through all calls to sin, cos and cexpi and call execute_cse_sincos_1 1381 on the SSA_NAME argument of each of them. Also expand powi(x,n) into 1382 an optimal number of multiplies, when n is a constant. */ 1383 1384 static unsigned int 1385 execute_cse_sincos (void) 1386 { 1387 basic_block bb; 1388 bool cfg_changed = false; 1389 1390 calculate_dominance_info (CDI_DOMINATORS); 1391 memset (&sincos_stats, 0, sizeof (sincos_stats)); 1392 1393 FOR_EACH_BB (bb) 1394 { 1395 gimple_stmt_iterator gsi; 1396 bool cleanup_eh = false; 1397 1398 for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 1399 { 1400 gimple stmt = gsi_stmt (gsi); 1401 tree fndecl; 1402 1403 /* Only the last stmt in a bb could throw, no need to call 1404 gimple_purge_dead_eh_edges if we change something in the middle 1405 of a basic block. */ 1406 cleanup_eh = false; 1407 1408 if (is_gimple_call (stmt) 1409 && gimple_call_lhs (stmt) 1410 && (fndecl = gimple_call_fndecl (stmt)) 1411 && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL) 1412 { 1413 tree arg, arg0, arg1, result; 1414 HOST_WIDE_INT n; 1415 location_t loc; 1416 1417 switch (DECL_FUNCTION_CODE (fndecl)) 1418 { 1419 CASE_FLT_FN (BUILT_IN_COS): 1420 CASE_FLT_FN (BUILT_IN_SIN): 1421 CASE_FLT_FN (BUILT_IN_CEXPI): 1422 /* Make sure we have either sincos or cexp. */ 1423 if (!TARGET_HAS_SINCOS && !TARGET_C99_FUNCTIONS) 1424 break; 1425 1426 arg = gimple_call_arg (stmt, 0); 1427 if (TREE_CODE (arg) == SSA_NAME) 1428 cfg_changed |= execute_cse_sincos_1 (arg); 1429 break; 1430 1431 CASE_FLT_FN (BUILT_IN_POW): 1432 arg0 = gimple_call_arg (stmt, 0); 1433 arg1 = gimple_call_arg (stmt, 1); 1434 1435 loc = gimple_location (stmt); 1436 result = gimple_expand_builtin_pow (&gsi, loc, arg0, arg1); 1437 1438 if (result) 1439 { 1440 tree lhs = gimple_get_lhs (stmt); 1441 gimple new_stmt = gimple_build_assign (lhs, result); 1442 gimple_set_location (new_stmt, loc); 1443 unlink_stmt_vdef (stmt); 1444 gsi_replace (&gsi, new_stmt, true); 1445 cleanup_eh = true; 1446 } 1447 break; 1448 1449 CASE_FLT_FN (BUILT_IN_POWI): 1450 arg0 = gimple_call_arg (stmt, 0); 1451 arg1 = gimple_call_arg (stmt, 1); 1452 if (!host_integerp (arg1, 0)) 1453 break; 1454 1455 n = TREE_INT_CST_LOW (arg1); 1456 loc = gimple_location (stmt); 1457 result = gimple_expand_builtin_powi (&gsi, loc, arg0, n); 1458 1459 if (result) 1460 { 1461 tree lhs = gimple_get_lhs (stmt); 1462 gimple new_stmt = gimple_build_assign (lhs, result); 1463 gimple_set_location (new_stmt, loc); 1464 unlink_stmt_vdef (stmt); 1465 gsi_replace (&gsi, new_stmt, true); 1466 cleanup_eh = true; 1467 } 1468 break; 1469 1470 CASE_FLT_FN (BUILT_IN_CABS): 1471 arg0 = gimple_call_arg (stmt, 0); 1472 loc = gimple_location (stmt); 1473 result = gimple_expand_builtin_cabs (&gsi, loc, arg0); 1474 1475 if (result) 1476 { 1477 tree lhs = gimple_get_lhs (stmt); 1478 gimple new_stmt = gimple_build_assign (lhs, result); 1479 gimple_set_location (new_stmt, loc); 1480 unlink_stmt_vdef (stmt); 1481 gsi_replace (&gsi, new_stmt, true); 1482 cleanup_eh = true; 1483 } 1484 break; 1485 1486 default:; 1487 } 1488 } 1489 } 1490 if (cleanup_eh) 1491 cfg_changed |= gimple_purge_dead_eh_edges (bb); 1492 } 1493 1494 statistics_counter_event (cfun, "sincos statements inserted", 1495 sincos_stats.inserted); 1496 1497 free_dominance_info (CDI_DOMINATORS); 1498 return cfg_changed ? TODO_cleanup_cfg : 0; 1499 } 1500 1501 static bool 1502 gate_cse_sincos (void) 1503 { 1504 /* We no longer require either sincos or cexp, since powi expansion 1505 piggybacks on this pass. */ 1506 return optimize; 1507 } 1508 1509 struct gimple_opt_pass pass_cse_sincos = 1510 { 1511 { 1512 GIMPLE_PASS, 1513 "sincos", /* name */ 1514 gate_cse_sincos, /* gate */ 1515 execute_cse_sincos, /* execute */ 1516 NULL, /* sub */ 1517 NULL, /* next */ 1518 0, /* static_pass_number */ 1519 TV_NONE, /* tv_id */ 1520 PROP_ssa, /* properties_required */ 1521 0, /* properties_provided */ 1522 0, /* properties_destroyed */ 1523 0, /* todo_flags_start */ 1524 TODO_update_ssa | TODO_verify_ssa 1525 | TODO_verify_stmts /* todo_flags_finish */ 1526 } 1527 }; 1528 1529 /* A symbolic number is used to detect byte permutation and selection 1530 patterns. Therefore the field N contains an artificial number 1531 consisting of byte size markers: 1532 1533 0 - byte has the value 0 1534 1..size - byte contains the content of the byte 1535 number indexed with that value minus one */ 1536 1537 struct symbolic_number { 1538 unsigned HOST_WIDEST_INT n; 1539 int size; 1540 }; 1541 1542 /* Perform a SHIFT or ROTATE operation by COUNT bits on symbolic 1543 number N. Return false if the requested operation is not permitted 1544 on a symbolic number. */ 1545 1546 static inline bool 1547 do_shift_rotate (enum tree_code code, 1548 struct symbolic_number *n, 1549 int count) 1550 { 1551 if (count % 8 != 0) 1552 return false; 1553 1554 /* Zero out the extra bits of N in order to avoid them being shifted 1555 into the significant bits. */ 1556 if (n->size < (int)sizeof (HOST_WIDEST_INT)) 1557 n->n &= ((unsigned HOST_WIDEST_INT)1 << (n->size * BITS_PER_UNIT)) - 1; 1558 1559 switch (code) 1560 { 1561 case LSHIFT_EXPR: 1562 n->n <<= count; 1563 break; 1564 case RSHIFT_EXPR: 1565 n->n >>= count; 1566 break; 1567 case LROTATE_EXPR: 1568 n->n = (n->n << count) | (n->n >> ((n->size * BITS_PER_UNIT) - count)); 1569 break; 1570 case RROTATE_EXPR: 1571 n->n = (n->n >> count) | (n->n << ((n->size * BITS_PER_UNIT) - count)); 1572 break; 1573 default: 1574 return false; 1575 } 1576 /* Zero unused bits for size. */ 1577 if (n->size < (int)sizeof (HOST_WIDEST_INT)) 1578 n->n &= ((unsigned HOST_WIDEST_INT)1 << (n->size * BITS_PER_UNIT)) - 1; 1579 return true; 1580 } 1581 1582 /* Perform sanity checking for the symbolic number N and the gimple 1583 statement STMT. */ 1584 1585 static inline bool 1586 verify_symbolic_number_p (struct symbolic_number *n, gimple stmt) 1587 { 1588 tree lhs_type; 1589 1590 lhs_type = gimple_expr_type (stmt); 1591 1592 if (TREE_CODE (lhs_type) != INTEGER_TYPE) 1593 return false; 1594 1595 if (TYPE_PRECISION (lhs_type) != n->size * BITS_PER_UNIT) 1596 return false; 1597 1598 return true; 1599 } 1600 1601 /* find_bswap_1 invokes itself recursively with N and tries to perform 1602 the operation given by the rhs of STMT on the result. If the 1603 operation could successfully be executed the function returns the 1604 tree expression of the source operand and NULL otherwise. */ 1605 1606 static tree 1607 find_bswap_1 (gimple stmt, struct symbolic_number *n, int limit) 1608 { 1609 enum tree_code code; 1610 tree rhs1, rhs2 = NULL; 1611 gimple rhs1_stmt, rhs2_stmt; 1612 tree source_expr1; 1613 enum gimple_rhs_class rhs_class; 1614 1615 if (!limit || !is_gimple_assign (stmt)) 1616 return NULL_TREE; 1617 1618 rhs1 = gimple_assign_rhs1 (stmt); 1619 1620 if (TREE_CODE (rhs1) != SSA_NAME) 1621 return NULL_TREE; 1622 1623 code = gimple_assign_rhs_code (stmt); 1624 rhs_class = gimple_assign_rhs_class (stmt); 1625 rhs1_stmt = SSA_NAME_DEF_STMT (rhs1); 1626 1627 if (rhs_class == GIMPLE_BINARY_RHS) 1628 rhs2 = gimple_assign_rhs2 (stmt); 1629 1630 /* Handle unary rhs and binary rhs with integer constants as second 1631 operand. */ 1632 1633 if (rhs_class == GIMPLE_UNARY_RHS 1634 || (rhs_class == GIMPLE_BINARY_RHS 1635 && TREE_CODE (rhs2) == INTEGER_CST)) 1636 { 1637 if (code != BIT_AND_EXPR 1638 && code != LSHIFT_EXPR 1639 && code != RSHIFT_EXPR 1640 && code != LROTATE_EXPR 1641 && code != RROTATE_EXPR 1642 && code != NOP_EXPR 1643 && code != CONVERT_EXPR) 1644 return NULL_TREE; 1645 1646 source_expr1 = find_bswap_1 (rhs1_stmt, n, limit - 1); 1647 1648 /* If find_bswap_1 returned NULL STMT is a leaf node and we have 1649 to initialize the symbolic number. */ 1650 if (!source_expr1) 1651 { 1652 /* Set up the symbolic number N by setting each byte to a 1653 value between 1 and the byte size of rhs1. The highest 1654 order byte is set to n->size and the lowest order 1655 byte to 1. */ 1656 n->size = TYPE_PRECISION (TREE_TYPE (rhs1)); 1657 if (n->size % BITS_PER_UNIT != 0) 1658 return NULL_TREE; 1659 n->size /= BITS_PER_UNIT; 1660 n->n = (sizeof (HOST_WIDEST_INT) < 8 ? 0 : 1661 (unsigned HOST_WIDEST_INT)0x08070605 << 32 | 0x04030201); 1662 1663 if (n->size < (int)sizeof (HOST_WIDEST_INT)) 1664 n->n &= ((unsigned HOST_WIDEST_INT)1 << 1665 (n->size * BITS_PER_UNIT)) - 1; 1666 1667 source_expr1 = rhs1; 1668 } 1669 1670 switch (code) 1671 { 1672 case BIT_AND_EXPR: 1673 { 1674 int i; 1675 unsigned HOST_WIDEST_INT val = widest_int_cst_value (rhs2); 1676 unsigned HOST_WIDEST_INT tmp = val; 1677 1678 /* Only constants masking full bytes are allowed. */ 1679 for (i = 0; i < n->size; i++, tmp >>= BITS_PER_UNIT) 1680 if ((tmp & 0xff) != 0 && (tmp & 0xff) != 0xff) 1681 return NULL_TREE; 1682 1683 n->n &= val; 1684 } 1685 break; 1686 case LSHIFT_EXPR: 1687 case RSHIFT_EXPR: 1688 case LROTATE_EXPR: 1689 case RROTATE_EXPR: 1690 if (!do_shift_rotate (code, n, (int)TREE_INT_CST_LOW (rhs2))) 1691 return NULL_TREE; 1692 break; 1693 CASE_CONVERT: 1694 { 1695 int type_size; 1696 1697 type_size = TYPE_PRECISION (gimple_expr_type (stmt)); 1698 if (type_size % BITS_PER_UNIT != 0) 1699 return NULL_TREE; 1700 1701 if (type_size / BITS_PER_UNIT < (int)(sizeof (HOST_WIDEST_INT))) 1702 { 1703 /* If STMT casts to a smaller type mask out the bits not 1704 belonging to the target type. */ 1705 n->n &= ((unsigned HOST_WIDEST_INT)1 << type_size) - 1; 1706 } 1707 n->size = type_size / BITS_PER_UNIT; 1708 } 1709 break; 1710 default: 1711 return NULL_TREE; 1712 }; 1713 return verify_symbolic_number_p (n, stmt) ? source_expr1 : NULL; 1714 } 1715 1716 /* Handle binary rhs. */ 1717 1718 if (rhs_class == GIMPLE_BINARY_RHS) 1719 { 1720 struct symbolic_number n1, n2; 1721 tree source_expr2; 1722 1723 if (code != BIT_IOR_EXPR) 1724 return NULL_TREE; 1725 1726 if (TREE_CODE (rhs2) != SSA_NAME) 1727 return NULL_TREE; 1728 1729 rhs2_stmt = SSA_NAME_DEF_STMT (rhs2); 1730 1731 switch (code) 1732 { 1733 case BIT_IOR_EXPR: 1734 source_expr1 = find_bswap_1 (rhs1_stmt, &n1, limit - 1); 1735 1736 if (!source_expr1) 1737 return NULL_TREE; 1738 1739 source_expr2 = find_bswap_1 (rhs2_stmt, &n2, limit - 1); 1740 1741 if (source_expr1 != source_expr2 1742 || n1.size != n2.size) 1743 return NULL_TREE; 1744 1745 n->size = n1.size; 1746 n->n = n1.n | n2.n; 1747 1748 if (!verify_symbolic_number_p (n, stmt)) 1749 return NULL_TREE; 1750 1751 break; 1752 default: 1753 return NULL_TREE; 1754 } 1755 return source_expr1; 1756 } 1757 return NULL_TREE; 1758 } 1759 1760 /* Check if STMT completes a bswap implementation consisting of ORs, 1761 SHIFTs and ANDs. Return the source tree expression on which the 1762 byte swap is performed and NULL if no bswap was found. */ 1763 1764 static tree 1765 find_bswap (gimple stmt) 1766 { 1767 /* The number which the find_bswap result should match in order to 1768 have a full byte swap. The number is shifted to the left according 1769 to the size of the symbolic number before using it. */ 1770 unsigned HOST_WIDEST_INT cmp = 1771 sizeof (HOST_WIDEST_INT) < 8 ? 0 : 1772 (unsigned HOST_WIDEST_INT)0x01020304 << 32 | 0x05060708; 1773 1774 struct symbolic_number n; 1775 tree source_expr; 1776 int limit; 1777 1778 /* The last parameter determines the depth search limit. It usually 1779 correlates directly to the number of bytes to be touched. We 1780 increase that number by three here in order to also 1781 cover signed -> unsigned converions of the src operand as can be seen 1782 in libgcc, and for initial shift/and operation of the src operand. */ 1783 limit = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (gimple_expr_type (stmt))); 1784 limit += 1 + (int) ceil_log2 ((unsigned HOST_WIDE_INT) limit); 1785 source_expr = find_bswap_1 (stmt, &n, limit); 1786 1787 if (!source_expr) 1788 return NULL_TREE; 1789 1790 /* Zero out the extra bits of N and CMP. */ 1791 if (n.size < (int)sizeof (HOST_WIDEST_INT)) 1792 { 1793 unsigned HOST_WIDEST_INT mask = 1794 ((unsigned HOST_WIDEST_INT)1 << (n.size * BITS_PER_UNIT)) - 1; 1795 1796 n.n &= mask; 1797 cmp >>= (sizeof (HOST_WIDEST_INT) - n.size) * BITS_PER_UNIT; 1798 } 1799 1800 /* A complete byte swap should make the symbolic number to start 1801 with the largest digit in the highest order byte. */ 1802 if (cmp != n.n) 1803 return NULL_TREE; 1804 1805 return source_expr; 1806 } 1807 1808 /* Find manual byte swap implementations and turn them into a bswap 1809 builtin invokation. */ 1810 1811 static unsigned int 1812 execute_optimize_bswap (void) 1813 { 1814 basic_block bb; 1815 bool bswap32_p, bswap64_p; 1816 bool changed = false; 1817 tree bswap32_type = NULL_TREE, bswap64_type = NULL_TREE; 1818 1819 if (BITS_PER_UNIT != 8) 1820 return 0; 1821 1822 if (sizeof (HOST_WIDEST_INT) < 8) 1823 return 0; 1824 1825 bswap32_p = (builtin_decl_explicit_p (BUILT_IN_BSWAP32) 1826 && optab_handler (bswap_optab, SImode) != CODE_FOR_nothing); 1827 bswap64_p = (builtin_decl_explicit_p (BUILT_IN_BSWAP64) 1828 && (optab_handler (bswap_optab, DImode) != CODE_FOR_nothing 1829 || (bswap32_p && word_mode == SImode))); 1830 1831 if (!bswap32_p && !bswap64_p) 1832 return 0; 1833 1834 /* Determine the argument type of the builtins. The code later on 1835 assumes that the return and argument type are the same. */ 1836 if (bswap32_p) 1837 { 1838 tree fndecl = builtin_decl_explicit (BUILT_IN_BSWAP32); 1839 bswap32_type = TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl))); 1840 } 1841 1842 if (bswap64_p) 1843 { 1844 tree fndecl = builtin_decl_explicit (BUILT_IN_BSWAP64); 1845 bswap64_type = TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl))); 1846 } 1847 1848 memset (&bswap_stats, 0, sizeof (bswap_stats)); 1849 1850 FOR_EACH_BB (bb) 1851 { 1852 gimple_stmt_iterator gsi; 1853 1854 /* We do a reverse scan for bswap patterns to make sure we get the 1855 widest match. As bswap pattern matching doesn't handle 1856 previously inserted smaller bswap replacements as sub- 1857 patterns, the wider variant wouldn't be detected. */ 1858 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi)) 1859 { 1860 gimple stmt = gsi_stmt (gsi); 1861 tree bswap_src, bswap_type; 1862 tree bswap_tmp; 1863 tree fndecl = NULL_TREE; 1864 int type_size; 1865 gimple call; 1866 1867 if (!is_gimple_assign (stmt) 1868 || gimple_assign_rhs_code (stmt) != BIT_IOR_EXPR) 1869 continue; 1870 1871 type_size = TYPE_PRECISION (gimple_expr_type (stmt)); 1872 1873 switch (type_size) 1874 { 1875 case 32: 1876 if (bswap32_p) 1877 { 1878 fndecl = builtin_decl_explicit (BUILT_IN_BSWAP32); 1879 bswap_type = bswap32_type; 1880 } 1881 break; 1882 case 64: 1883 if (bswap64_p) 1884 { 1885 fndecl = builtin_decl_explicit (BUILT_IN_BSWAP64); 1886 bswap_type = bswap64_type; 1887 } 1888 break; 1889 default: 1890 continue; 1891 } 1892 1893 if (!fndecl) 1894 continue; 1895 1896 bswap_src = find_bswap (stmt); 1897 1898 if (!bswap_src) 1899 continue; 1900 1901 changed = true; 1902 if (type_size == 32) 1903 bswap_stats.found_32bit++; 1904 else 1905 bswap_stats.found_64bit++; 1906 1907 bswap_tmp = bswap_src; 1908 1909 /* Convert the src expression if necessary. */ 1910 if (!useless_type_conversion_p (TREE_TYPE (bswap_tmp), bswap_type)) 1911 { 1912 gimple convert_stmt; 1913 1914 bswap_tmp = create_tmp_var (bswap_type, "bswapsrc"); 1915 add_referenced_var (bswap_tmp); 1916 bswap_tmp = make_ssa_name (bswap_tmp, NULL); 1917 1918 convert_stmt = gimple_build_assign_with_ops ( 1919 CONVERT_EXPR, bswap_tmp, bswap_src, NULL); 1920 gsi_insert_before (&gsi, convert_stmt, GSI_SAME_STMT); 1921 } 1922 1923 call = gimple_build_call (fndecl, 1, bswap_tmp); 1924 1925 bswap_tmp = gimple_assign_lhs (stmt); 1926 1927 /* Convert the result if necessary. */ 1928 if (!useless_type_conversion_p (TREE_TYPE (bswap_tmp), bswap_type)) 1929 { 1930 gimple convert_stmt; 1931 1932 bswap_tmp = create_tmp_var (bswap_type, "bswapdst"); 1933 add_referenced_var (bswap_tmp); 1934 bswap_tmp = make_ssa_name (bswap_tmp, NULL); 1935 convert_stmt = gimple_build_assign_with_ops ( 1936 CONVERT_EXPR, gimple_assign_lhs (stmt), bswap_tmp, NULL); 1937 gsi_insert_after (&gsi, convert_stmt, GSI_SAME_STMT); 1938 } 1939 1940 gimple_call_set_lhs (call, bswap_tmp); 1941 1942 if (dump_file) 1943 { 1944 fprintf (dump_file, "%d bit bswap implementation found at: ", 1945 (int)type_size); 1946 print_gimple_stmt (dump_file, stmt, 0, 0); 1947 } 1948 1949 gsi_insert_after (&gsi, call, GSI_SAME_STMT); 1950 gsi_remove (&gsi, true); 1951 } 1952 } 1953 1954 statistics_counter_event (cfun, "32-bit bswap implementations found", 1955 bswap_stats.found_32bit); 1956 statistics_counter_event (cfun, "64-bit bswap implementations found", 1957 bswap_stats.found_64bit); 1958 1959 return (changed ? TODO_update_ssa | TODO_verify_ssa 1960 | TODO_verify_stmts : 0); 1961 } 1962 1963 static bool 1964 gate_optimize_bswap (void) 1965 { 1966 return flag_expensive_optimizations && optimize; 1967 } 1968 1969 struct gimple_opt_pass pass_optimize_bswap = 1970 { 1971 { 1972 GIMPLE_PASS, 1973 "bswap", /* name */ 1974 gate_optimize_bswap, /* gate */ 1975 execute_optimize_bswap, /* execute */ 1976 NULL, /* sub */ 1977 NULL, /* next */ 1978 0, /* static_pass_number */ 1979 TV_NONE, /* tv_id */ 1980 PROP_ssa, /* properties_required */ 1981 0, /* properties_provided */ 1982 0, /* properties_destroyed */ 1983 0, /* todo_flags_start */ 1984 0 /* todo_flags_finish */ 1985 } 1986 }; 1987 1988 /* Return true if RHS is a suitable operand for a widening multiplication, 1989 assuming a target type of TYPE. 1990 There are two cases: 1991 1992 - RHS makes some value at least twice as wide. Store that value 1993 in *NEW_RHS_OUT if so, and store its type in *TYPE_OUT. 1994 1995 - RHS is an integer constant. Store that value in *NEW_RHS_OUT if so, 1996 but leave *TYPE_OUT untouched. */ 1997 1998 static bool 1999 is_widening_mult_rhs_p (tree type, tree rhs, tree *type_out, 2000 tree *new_rhs_out) 2001 { 2002 gimple stmt; 2003 tree type1, rhs1; 2004 enum tree_code rhs_code; 2005 2006 if (TREE_CODE (rhs) == SSA_NAME) 2007 { 2008 stmt = SSA_NAME_DEF_STMT (rhs); 2009 if (is_gimple_assign (stmt)) 2010 { 2011 rhs_code = gimple_assign_rhs_code (stmt); 2012 if (TREE_CODE (type) == INTEGER_TYPE 2013 ? !CONVERT_EXPR_CODE_P (rhs_code) 2014 : rhs_code != FIXED_CONVERT_EXPR) 2015 rhs1 = rhs; 2016 else 2017 { 2018 rhs1 = gimple_assign_rhs1 (stmt); 2019 2020 if (TREE_CODE (rhs1) == INTEGER_CST) 2021 { 2022 *new_rhs_out = rhs1; 2023 *type_out = NULL; 2024 return true; 2025 } 2026 } 2027 } 2028 else 2029 rhs1 = rhs; 2030 2031 type1 = TREE_TYPE (rhs1); 2032 2033 if (TREE_CODE (type1) != TREE_CODE (type) 2034 || TYPE_PRECISION (type1) * 2 > TYPE_PRECISION (type)) 2035 return false; 2036 2037 *new_rhs_out = rhs1; 2038 *type_out = type1; 2039 return true; 2040 } 2041 2042 if (TREE_CODE (rhs) == INTEGER_CST) 2043 { 2044 *new_rhs_out = rhs; 2045 *type_out = NULL; 2046 return true; 2047 } 2048 2049 return false; 2050 } 2051 2052 /* Return true if STMT performs a widening multiplication, assuming the 2053 output type is TYPE. If so, store the unwidened types of the operands 2054 in *TYPE1_OUT and *TYPE2_OUT respectively. Also fill *RHS1_OUT and 2055 *RHS2_OUT such that converting those operands to types *TYPE1_OUT 2056 and *TYPE2_OUT would give the operands of the multiplication. */ 2057 2058 static bool 2059 is_widening_mult_p (gimple stmt, 2060 tree *type1_out, tree *rhs1_out, 2061 tree *type2_out, tree *rhs2_out) 2062 { 2063 tree type = TREE_TYPE (gimple_assign_lhs (stmt)); 2064 2065 if (TREE_CODE (type) != INTEGER_TYPE 2066 && TREE_CODE (type) != FIXED_POINT_TYPE) 2067 return false; 2068 2069 if (!is_widening_mult_rhs_p (type, gimple_assign_rhs1 (stmt), type1_out, 2070 rhs1_out)) 2071 return false; 2072 2073 if (!is_widening_mult_rhs_p (type, gimple_assign_rhs2 (stmt), type2_out, 2074 rhs2_out)) 2075 return false; 2076 2077 if (*type1_out == NULL) 2078 { 2079 if (*type2_out == NULL || !int_fits_type_p (*rhs1_out, *type2_out)) 2080 return false; 2081 *type1_out = *type2_out; 2082 } 2083 2084 if (*type2_out == NULL) 2085 { 2086 if (!int_fits_type_p (*rhs2_out, *type1_out)) 2087 return false; 2088 *type2_out = *type1_out; 2089 } 2090 2091 /* Ensure that the larger of the two operands comes first. */ 2092 if (TYPE_PRECISION (*type1_out) < TYPE_PRECISION (*type2_out)) 2093 { 2094 tree tmp; 2095 tmp = *type1_out; 2096 *type1_out = *type2_out; 2097 *type2_out = tmp; 2098 tmp = *rhs1_out; 2099 *rhs1_out = *rhs2_out; 2100 *rhs2_out = tmp; 2101 } 2102 2103 return true; 2104 } 2105 2106 /* Process a single gimple statement STMT, which has a MULT_EXPR as 2107 its rhs, and try to convert it into a WIDEN_MULT_EXPR. The return 2108 value is true iff we converted the statement. */ 2109 2110 static bool 2111 convert_mult_to_widen (gimple stmt, gimple_stmt_iterator *gsi) 2112 { 2113 tree lhs, rhs1, rhs2, type, type1, type2, tmp = NULL; 2114 enum insn_code handler; 2115 enum machine_mode to_mode, from_mode, actual_mode; 2116 optab op; 2117 int actual_precision; 2118 location_t loc = gimple_location (stmt); 2119 bool from_unsigned1, from_unsigned2; 2120 2121 lhs = gimple_assign_lhs (stmt); 2122 type = TREE_TYPE (lhs); 2123 if (TREE_CODE (type) != INTEGER_TYPE) 2124 return false; 2125 2126 if (!is_widening_mult_p (stmt, &type1, &rhs1, &type2, &rhs2)) 2127 return false; 2128 2129 to_mode = TYPE_MODE (type); 2130 from_mode = TYPE_MODE (type1); 2131 from_unsigned1 = TYPE_UNSIGNED (type1); 2132 from_unsigned2 = TYPE_UNSIGNED (type2); 2133 2134 if (from_unsigned1 && from_unsigned2) 2135 op = umul_widen_optab; 2136 else if (!from_unsigned1 && !from_unsigned2) 2137 op = smul_widen_optab; 2138 else 2139 op = usmul_widen_optab; 2140 2141 handler = find_widening_optab_handler_and_mode (op, to_mode, from_mode, 2142 0, &actual_mode); 2143 2144 if (handler == CODE_FOR_nothing) 2145 { 2146 if (op != smul_widen_optab) 2147 { 2148 /* We can use a signed multiply with unsigned types as long as 2149 there is a wider mode to use, or it is the smaller of the two 2150 types that is unsigned. Note that type1 >= type2, always. */ 2151 if ((TYPE_UNSIGNED (type1) 2152 && TYPE_PRECISION (type1) == GET_MODE_PRECISION (from_mode)) 2153 || (TYPE_UNSIGNED (type2) 2154 && TYPE_PRECISION (type2) == GET_MODE_PRECISION (from_mode))) 2155 { 2156 from_mode = GET_MODE_WIDER_MODE (from_mode); 2157 if (GET_MODE_SIZE (to_mode) <= GET_MODE_SIZE (from_mode)) 2158 return false; 2159 } 2160 2161 op = smul_widen_optab; 2162 handler = find_widening_optab_handler_and_mode (op, to_mode, 2163 from_mode, 0, 2164 &actual_mode); 2165 2166 if (handler == CODE_FOR_nothing) 2167 return false; 2168 2169 from_unsigned1 = from_unsigned2 = false; 2170 } 2171 else 2172 return false; 2173 } 2174 2175 /* Ensure that the inputs to the handler are in the correct precison 2176 for the opcode. This will be the full mode size. */ 2177 actual_precision = GET_MODE_PRECISION (actual_mode); 2178 if (actual_precision != TYPE_PRECISION (type1) 2179 || from_unsigned1 != TYPE_UNSIGNED (type1)) 2180 { 2181 tmp = create_tmp_var (build_nonstandard_integer_type 2182 (actual_precision, from_unsigned1), 2183 NULL); 2184 rhs1 = build_and_insert_cast (gsi, loc, tmp, rhs1); 2185 } 2186 if (actual_precision != TYPE_PRECISION (type2) 2187 || from_unsigned2 != TYPE_UNSIGNED (type2)) 2188 { 2189 /* Reuse the same type info, if possible. */ 2190 if (!tmp || from_unsigned1 != from_unsigned2) 2191 tmp = create_tmp_var (build_nonstandard_integer_type 2192 (actual_precision, from_unsigned2), 2193 NULL); 2194 rhs2 = build_and_insert_cast (gsi, loc, tmp, rhs2); 2195 } 2196 2197 /* Handle constants. */ 2198 if (TREE_CODE (rhs1) == INTEGER_CST) 2199 rhs1 = fold_convert (type1, rhs1); 2200 if (TREE_CODE (rhs2) == INTEGER_CST) 2201 rhs2 = fold_convert (type2, rhs2); 2202 2203 gimple_assign_set_rhs1 (stmt, rhs1); 2204 gimple_assign_set_rhs2 (stmt, rhs2); 2205 gimple_assign_set_rhs_code (stmt, WIDEN_MULT_EXPR); 2206 update_stmt (stmt); 2207 widen_mul_stats.widen_mults_inserted++; 2208 return true; 2209 } 2210 2211 /* Process a single gimple statement STMT, which is found at the 2212 iterator GSI and has a either a PLUS_EXPR or a MINUS_EXPR as its 2213 rhs (given by CODE), and try to convert it into a 2214 WIDEN_MULT_PLUS_EXPR or a WIDEN_MULT_MINUS_EXPR. The return value 2215 is true iff we converted the statement. */ 2216 2217 static bool 2218 convert_plusminus_to_widen (gimple_stmt_iterator *gsi, gimple stmt, 2219 enum tree_code code) 2220 { 2221 gimple rhs1_stmt = NULL, rhs2_stmt = NULL; 2222 gimple conv1_stmt = NULL, conv2_stmt = NULL, conv_stmt; 2223 tree type, type1, type2, optype, tmp = NULL; 2224 tree lhs, rhs1, rhs2, mult_rhs1, mult_rhs2, add_rhs; 2225 enum tree_code rhs1_code = ERROR_MARK, rhs2_code = ERROR_MARK; 2226 optab this_optab; 2227 enum tree_code wmult_code; 2228 enum insn_code handler; 2229 enum machine_mode to_mode, from_mode, actual_mode; 2230 location_t loc = gimple_location (stmt); 2231 int actual_precision; 2232 bool from_unsigned1, from_unsigned2; 2233 2234 lhs = gimple_assign_lhs (stmt); 2235 type = TREE_TYPE (lhs); 2236 if (TREE_CODE (type) != INTEGER_TYPE 2237 && TREE_CODE (type) != FIXED_POINT_TYPE) 2238 return false; 2239 2240 if (code == MINUS_EXPR) 2241 wmult_code = WIDEN_MULT_MINUS_EXPR; 2242 else 2243 wmult_code = WIDEN_MULT_PLUS_EXPR; 2244 2245 rhs1 = gimple_assign_rhs1 (stmt); 2246 rhs2 = gimple_assign_rhs2 (stmt); 2247 2248 if (TREE_CODE (rhs1) == SSA_NAME) 2249 { 2250 rhs1_stmt = SSA_NAME_DEF_STMT (rhs1); 2251 if (is_gimple_assign (rhs1_stmt)) 2252 rhs1_code = gimple_assign_rhs_code (rhs1_stmt); 2253 } 2254 2255 if (TREE_CODE (rhs2) == SSA_NAME) 2256 { 2257 rhs2_stmt = SSA_NAME_DEF_STMT (rhs2); 2258 if (is_gimple_assign (rhs2_stmt)) 2259 rhs2_code = gimple_assign_rhs_code (rhs2_stmt); 2260 } 2261 2262 /* Allow for one conversion statement between the multiply 2263 and addition/subtraction statement. If there are more than 2264 one conversions then we assume they would invalidate this 2265 transformation. If that's not the case then they should have 2266 been folded before now. */ 2267 if (CONVERT_EXPR_CODE_P (rhs1_code)) 2268 { 2269 conv1_stmt = rhs1_stmt; 2270 rhs1 = gimple_assign_rhs1 (rhs1_stmt); 2271 if (TREE_CODE (rhs1) == SSA_NAME) 2272 { 2273 rhs1_stmt = SSA_NAME_DEF_STMT (rhs1); 2274 if (is_gimple_assign (rhs1_stmt)) 2275 rhs1_code = gimple_assign_rhs_code (rhs1_stmt); 2276 } 2277 else 2278 return false; 2279 } 2280 if (CONVERT_EXPR_CODE_P (rhs2_code)) 2281 { 2282 conv2_stmt = rhs2_stmt; 2283 rhs2 = gimple_assign_rhs1 (rhs2_stmt); 2284 if (TREE_CODE (rhs2) == SSA_NAME) 2285 { 2286 rhs2_stmt = SSA_NAME_DEF_STMT (rhs2); 2287 if (is_gimple_assign (rhs2_stmt)) 2288 rhs2_code = gimple_assign_rhs_code (rhs2_stmt); 2289 } 2290 else 2291 return false; 2292 } 2293 2294 /* If code is WIDEN_MULT_EXPR then it would seem unnecessary to call 2295 is_widening_mult_p, but we still need the rhs returns. 2296 2297 It might also appear that it would be sufficient to use the existing 2298 operands of the widening multiply, but that would limit the choice of 2299 multiply-and-accumulate instructions. */ 2300 if (code == PLUS_EXPR 2301 && (rhs1_code == MULT_EXPR || rhs1_code == WIDEN_MULT_EXPR)) 2302 { 2303 if (!is_widening_mult_p (rhs1_stmt, &type1, &mult_rhs1, 2304 &type2, &mult_rhs2)) 2305 return false; 2306 add_rhs = rhs2; 2307 conv_stmt = conv1_stmt; 2308 } 2309 else if (rhs2_code == MULT_EXPR || rhs2_code == WIDEN_MULT_EXPR) 2310 { 2311 if (!is_widening_mult_p (rhs2_stmt, &type1, &mult_rhs1, 2312 &type2, &mult_rhs2)) 2313 return false; 2314 add_rhs = rhs1; 2315 conv_stmt = conv2_stmt; 2316 } 2317 else 2318 return false; 2319 2320 to_mode = TYPE_MODE (type); 2321 from_mode = TYPE_MODE (type1); 2322 from_unsigned1 = TYPE_UNSIGNED (type1); 2323 from_unsigned2 = TYPE_UNSIGNED (type2); 2324 optype = type1; 2325 2326 /* There's no such thing as a mixed sign madd yet, so use a wider mode. */ 2327 if (from_unsigned1 != from_unsigned2) 2328 { 2329 if (!INTEGRAL_TYPE_P (type)) 2330 return false; 2331 /* We can use a signed multiply with unsigned types as long as 2332 there is a wider mode to use, or it is the smaller of the two 2333 types that is unsigned. Note that type1 >= type2, always. */ 2334 if ((from_unsigned1 2335 && TYPE_PRECISION (type1) == GET_MODE_PRECISION (from_mode)) 2336 || (from_unsigned2 2337 && TYPE_PRECISION (type2) == GET_MODE_PRECISION (from_mode))) 2338 { 2339 from_mode = GET_MODE_WIDER_MODE (from_mode); 2340 if (GET_MODE_SIZE (from_mode) >= GET_MODE_SIZE (to_mode)) 2341 return false; 2342 } 2343 2344 from_unsigned1 = from_unsigned2 = false; 2345 optype = build_nonstandard_integer_type (GET_MODE_PRECISION (from_mode), 2346 false); 2347 } 2348 2349 /* If there was a conversion between the multiply and addition 2350 then we need to make sure it fits a multiply-and-accumulate. 2351 The should be a single mode change which does not change the 2352 value. */ 2353 if (conv_stmt) 2354 { 2355 /* We use the original, unmodified data types for this. */ 2356 tree from_type = TREE_TYPE (gimple_assign_rhs1 (conv_stmt)); 2357 tree to_type = TREE_TYPE (gimple_assign_lhs (conv_stmt)); 2358 int data_size = TYPE_PRECISION (type1) + TYPE_PRECISION (type2); 2359 bool is_unsigned = TYPE_UNSIGNED (type1) && TYPE_UNSIGNED (type2); 2360 2361 if (TYPE_PRECISION (from_type) > TYPE_PRECISION (to_type)) 2362 { 2363 /* Conversion is a truncate. */ 2364 if (TYPE_PRECISION (to_type) < data_size) 2365 return false; 2366 } 2367 else if (TYPE_PRECISION (from_type) < TYPE_PRECISION (to_type)) 2368 { 2369 /* Conversion is an extend. Check it's the right sort. */ 2370 if (TYPE_UNSIGNED (from_type) != is_unsigned 2371 && !(is_unsigned && TYPE_PRECISION (from_type) > data_size)) 2372 return false; 2373 } 2374 /* else convert is a no-op for our purposes. */ 2375 } 2376 2377 /* Verify that the machine can perform a widening multiply 2378 accumulate in this mode/signedness combination, otherwise 2379 this transformation is likely to pessimize code. */ 2380 this_optab = optab_for_tree_code (wmult_code, optype, optab_default); 2381 handler = find_widening_optab_handler_and_mode (this_optab, to_mode, 2382 from_mode, 0, &actual_mode); 2383 2384 if (handler == CODE_FOR_nothing) 2385 return false; 2386 2387 /* Ensure that the inputs to the handler are in the correct precison 2388 for the opcode. This will be the full mode size. */ 2389 actual_precision = GET_MODE_PRECISION (actual_mode); 2390 if (actual_precision != TYPE_PRECISION (type1) 2391 || from_unsigned1 != TYPE_UNSIGNED (type1)) 2392 { 2393 tmp = create_tmp_var (build_nonstandard_integer_type 2394 (actual_precision, from_unsigned1), 2395 NULL); 2396 mult_rhs1 = build_and_insert_cast (gsi, loc, tmp, mult_rhs1); 2397 } 2398 if (actual_precision != TYPE_PRECISION (type2) 2399 || from_unsigned2 != TYPE_UNSIGNED (type2)) 2400 { 2401 if (!tmp || from_unsigned1 != from_unsigned2) 2402 tmp = create_tmp_var (build_nonstandard_integer_type 2403 (actual_precision, from_unsigned2), 2404 NULL); 2405 mult_rhs2 = build_and_insert_cast (gsi, loc, tmp, mult_rhs2); 2406 } 2407 2408 if (!useless_type_conversion_p (type, TREE_TYPE (add_rhs))) 2409 add_rhs = build_and_insert_cast (gsi, loc, create_tmp_var (type, NULL), 2410 add_rhs); 2411 2412 /* Handle constants. */ 2413 if (TREE_CODE (mult_rhs1) == INTEGER_CST) 2414 mult_rhs1 = fold_convert (type1, mult_rhs1); 2415 if (TREE_CODE (mult_rhs2) == INTEGER_CST) 2416 mult_rhs2 = fold_convert (type2, mult_rhs2); 2417 2418 gimple_assign_set_rhs_with_ops_1 (gsi, wmult_code, mult_rhs1, mult_rhs2, 2419 add_rhs); 2420 update_stmt (gsi_stmt (*gsi)); 2421 widen_mul_stats.maccs_inserted++; 2422 return true; 2423 } 2424 2425 /* Combine the multiplication at MUL_STMT with operands MULOP1 and MULOP2 2426 with uses in additions and subtractions to form fused multiply-add 2427 operations. Returns true if successful and MUL_STMT should be removed. */ 2428 2429 static bool 2430 convert_mult_to_fma (gimple mul_stmt, tree op1, tree op2) 2431 { 2432 tree mul_result = gimple_get_lhs (mul_stmt); 2433 tree type = TREE_TYPE (mul_result); 2434 gimple use_stmt, neguse_stmt, fma_stmt; 2435 use_operand_p use_p; 2436 imm_use_iterator imm_iter; 2437 2438 if (FLOAT_TYPE_P (type) 2439 && flag_fp_contract_mode == FP_CONTRACT_OFF) 2440 return false; 2441 2442 /* We don't want to do bitfield reduction ops. */ 2443 if (INTEGRAL_TYPE_P (type) 2444 && (TYPE_PRECISION (type) 2445 != GET_MODE_PRECISION (TYPE_MODE (type)))) 2446 return false; 2447 2448 /* If the target doesn't support it, don't generate it. We assume that 2449 if fma isn't available then fms, fnma or fnms are not either. */ 2450 if (optab_handler (fma_optab, TYPE_MODE (type)) == CODE_FOR_nothing) 2451 return false; 2452 2453 /* If the multiplication has zero uses, it is kept around probably because 2454 of -fnon-call-exceptions. Don't optimize it away in that case, 2455 it is DCE job. */ 2456 if (has_zero_uses (mul_result)) 2457 return false; 2458 2459 /* Make sure that the multiplication statement becomes dead after 2460 the transformation, thus that all uses are transformed to FMAs. 2461 This means we assume that an FMA operation has the same cost 2462 as an addition. */ 2463 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, mul_result) 2464 { 2465 enum tree_code use_code; 2466 tree result = mul_result; 2467 bool negate_p = false; 2468 2469 use_stmt = USE_STMT (use_p); 2470 2471 if (is_gimple_debug (use_stmt)) 2472 continue; 2473 2474 /* For now restrict this operations to single basic blocks. In theory 2475 we would want to support sinking the multiplication in 2476 m = a*b; 2477 if () 2478 ma = m + c; 2479 else 2480 d = m; 2481 to form a fma in the then block and sink the multiplication to the 2482 else block. */ 2483 if (gimple_bb (use_stmt) != gimple_bb (mul_stmt)) 2484 return false; 2485 2486 if (!is_gimple_assign (use_stmt)) 2487 return false; 2488 2489 use_code = gimple_assign_rhs_code (use_stmt); 2490 2491 /* A negate on the multiplication leads to FNMA. */ 2492 if (use_code == NEGATE_EXPR) 2493 { 2494 ssa_op_iter iter; 2495 use_operand_p usep; 2496 2497 result = gimple_assign_lhs (use_stmt); 2498 2499 /* Make sure the negate statement becomes dead with this 2500 single transformation. */ 2501 if (!single_imm_use (gimple_assign_lhs (use_stmt), 2502 &use_p, &neguse_stmt)) 2503 return false; 2504 2505 /* Make sure the multiplication isn't also used on that stmt. */ 2506 FOR_EACH_PHI_OR_STMT_USE (usep, neguse_stmt, iter, SSA_OP_USE) 2507 if (USE_FROM_PTR (usep) == mul_result) 2508 return false; 2509 2510 /* Re-validate. */ 2511 use_stmt = neguse_stmt; 2512 if (gimple_bb (use_stmt) != gimple_bb (mul_stmt)) 2513 return false; 2514 if (!is_gimple_assign (use_stmt)) 2515 return false; 2516 2517 use_code = gimple_assign_rhs_code (use_stmt); 2518 negate_p = true; 2519 } 2520 2521 switch (use_code) 2522 { 2523 case MINUS_EXPR: 2524 if (gimple_assign_rhs2 (use_stmt) == result) 2525 negate_p = !negate_p; 2526 break; 2527 case PLUS_EXPR: 2528 break; 2529 default: 2530 /* FMA can only be formed from PLUS and MINUS. */ 2531 return false; 2532 } 2533 2534 /* We can't handle a * b + a * b. */ 2535 if (gimple_assign_rhs1 (use_stmt) == gimple_assign_rhs2 (use_stmt)) 2536 return false; 2537 2538 /* While it is possible to validate whether or not the exact form 2539 that we've recognized is available in the backend, the assumption 2540 is that the transformation is never a loss. For instance, suppose 2541 the target only has the plain FMA pattern available. Consider 2542 a*b-c -> fma(a,b,-c): we've exchanged MUL+SUB for FMA+NEG, which 2543 is still two operations. Consider -(a*b)-c -> fma(-a,b,-c): we 2544 still have 3 operations, but in the FMA form the two NEGs are 2545 independant and could be run in parallel. */ 2546 } 2547 2548 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, mul_result) 2549 { 2550 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt); 2551 enum tree_code use_code; 2552 tree addop, mulop1 = op1, result = mul_result; 2553 bool negate_p = false; 2554 2555 if (is_gimple_debug (use_stmt)) 2556 continue; 2557 2558 use_code = gimple_assign_rhs_code (use_stmt); 2559 if (use_code == NEGATE_EXPR) 2560 { 2561 result = gimple_assign_lhs (use_stmt); 2562 single_imm_use (gimple_assign_lhs (use_stmt), &use_p, &neguse_stmt); 2563 gsi_remove (&gsi, true); 2564 release_defs (use_stmt); 2565 2566 use_stmt = neguse_stmt; 2567 gsi = gsi_for_stmt (use_stmt); 2568 use_code = gimple_assign_rhs_code (use_stmt); 2569 negate_p = true; 2570 } 2571 2572 if (gimple_assign_rhs1 (use_stmt) == result) 2573 { 2574 addop = gimple_assign_rhs2 (use_stmt); 2575 /* a * b - c -> a * b + (-c) */ 2576 if (gimple_assign_rhs_code (use_stmt) == MINUS_EXPR) 2577 addop = force_gimple_operand_gsi (&gsi, 2578 build1 (NEGATE_EXPR, 2579 type, addop), 2580 true, NULL_TREE, true, 2581 GSI_SAME_STMT); 2582 } 2583 else 2584 { 2585 addop = gimple_assign_rhs1 (use_stmt); 2586 /* a - b * c -> (-b) * c + a */ 2587 if (gimple_assign_rhs_code (use_stmt) == MINUS_EXPR) 2588 negate_p = !negate_p; 2589 } 2590 2591 if (negate_p) 2592 mulop1 = force_gimple_operand_gsi (&gsi, 2593 build1 (NEGATE_EXPR, 2594 type, mulop1), 2595 true, NULL_TREE, true, 2596 GSI_SAME_STMT); 2597 2598 fma_stmt = gimple_build_assign_with_ops3 (FMA_EXPR, 2599 gimple_assign_lhs (use_stmt), 2600 mulop1, op2, 2601 addop); 2602 gsi_replace (&gsi, fma_stmt, true); 2603 widen_mul_stats.fmas_inserted++; 2604 } 2605 2606 return true; 2607 } 2608 2609 /* Find integer multiplications where the operands are extended from 2610 smaller types, and replace the MULT_EXPR with a WIDEN_MULT_EXPR 2611 where appropriate. */ 2612 2613 static unsigned int 2614 execute_optimize_widening_mul (void) 2615 { 2616 basic_block bb; 2617 bool cfg_changed = false; 2618 2619 memset (&widen_mul_stats, 0, sizeof (widen_mul_stats)); 2620 2621 FOR_EACH_BB (bb) 2622 { 2623 gimple_stmt_iterator gsi; 2624 2625 for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi);) 2626 { 2627 gimple stmt = gsi_stmt (gsi); 2628 enum tree_code code; 2629 2630 if (is_gimple_assign (stmt)) 2631 { 2632 code = gimple_assign_rhs_code (stmt); 2633 switch (code) 2634 { 2635 case MULT_EXPR: 2636 if (!convert_mult_to_widen (stmt, &gsi) 2637 && convert_mult_to_fma (stmt, 2638 gimple_assign_rhs1 (stmt), 2639 gimple_assign_rhs2 (stmt))) 2640 { 2641 gsi_remove (&gsi, true); 2642 release_defs (stmt); 2643 continue; 2644 } 2645 break; 2646 2647 case PLUS_EXPR: 2648 case MINUS_EXPR: 2649 convert_plusminus_to_widen (&gsi, stmt, code); 2650 break; 2651 2652 default:; 2653 } 2654 } 2655 else if (is_gimple_call (stmt) 2656 && gimple_call_lhs (stmt)) 2657 { 2658 tree fndecl = gimple_call_fndecl (stmt); 2659 if (fndecl 2660 && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL) 2661 { 2662 switch (DECL_FUNCTION_CODE (fndecl)) 2663 { 2664 case BUILT_IN_POWF: 2665 case BUILT_IN_POW: 2666 case BUILT_IN_POWL: 2667 if (TREE_CODE (gimple_call_arg (stmt, 1)) == REAL_CST 2668 && REAL_VALUES_EQUAL 2669 (TREE_REAL_CST (gimple_call_arg (stmt, 1)), 2670 dconst2) 2671 && convert_mult_to_fma (stmt, 2672 gimple_call_arg (stmt, 0), 2673 gimple_call_arg (stmt, 0))) 2674 { 2675 unlink_stmt_vdef (stmt); 2676 gsi_remove (&gsi, true); 2677 release_defs (stmt); 2678 if (gimple_purge_dead_eh_edges (bb)) 2679 cfg_changed = true; 2680 continue; 2681 } 2682 break; 2683 2684 default:; 2685 } 2686 } 2687 } 2688 gsi_next (&gsi); 2689 } 2690 } 2691 2692 statistics_counter_event (cfun, "widening multiplications inserted", 2693 widen_mul_stats.widen_mults_inserted); 2694 statistics_counter_event (cfun, "widening maccs inserted", 2695 widen_mul_stats.maccs_inserted); 2696 statistics_counter_event (cfun, "fused multiply-adds inserted", 2697 widen_mul_stats.fmas_inserted); 2698 2699 return cfg_changed ? TODO_cleanup_cfg : 0; 2700 } 2701 2702 static bool 2703 gate_optimize_widening_mul (void) 2704 { 2705 return flag_expensive_optimizations && optimize; 2706 } 2707 2708 struct gimple_opt_pass pass_optimize_widening_mul = 2709 { 2710 { 2711 GIMPLE_PASS, 2712 "widening_mul", /* name */ 2713 gate_optimize_widening_mul, /* gate */ 2714 execute_optimize_widening_mul, /* execute */ 2715 NULL, /* sub */ 2716 NULL, /* next */ 2717 0, /* static_pass_number */ 2718 TV_NONE, /* tv_id */ 2719 PROP_ssa, /* properties_required */ 2720 0, /* properties_provided */ 2721 0, /* properties_destroyed */ 2722 0, /* todo_flags_start */ 2723 TODO_verify_ssa 2724 | TODO_verify_stmts 2725 | TODO_update_ssa /* todo_flags_finish */ 2726 } 2727 }; 2728