1 /* Global, SSA-based optimizations using mathematical identities. 2 Copyright (C) 2005-2018 Free Software Foundation, Inc. 3 4 This file is part of GCC. 5 6 GCC is free software; you can redistribute it and/or modify it 7 under the terms of the GNU General Public License as published by the 8 Free Software Foundation; either version 3, or (at your option) any 9 later version. 10 11 GCC is distributed in the hope that it will be useful, but WITHOUT 12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with GCC; see the file COPYING3. If not see 18 <http://www.gnu.org/licenses/>. */ 19 20 /* Currently, the only mini-pass in this file tries to CSE reciprocal 21 operations. These are common in sequences such as this one: 22 23 modulus = sqrt(x*x + y*y + z*z); 24 x = x / modulus; 25 y = y / modulus; 26 z = z / modulus; 27 28 that can be optimized to 29 30 modulus = sqrt(x*x + y*y + z*z); 31 rmodulus = 1.0 / modulus; 32 x = x * rmodulus; 33 y = y * rmodulus; 34 z = z * rmodulus; 35 36 We do this for loop invariant divisors, and with this pass whenever 37 we notice that a division has the same divisor multiple times. 38 39 Of course, like in PRE, we don't insert a division if a dominator 40 already has one. However, this cannot be done as an extension of 41 PRE for several reasons. 42 43 First of all, with some experiments it was found out that the 44 transformation is not always useful if there are only two divisions 45 by the same divisor. This is probably because modern processors 46 can pipeline the divisions; on older, in-order processors it should 47 still be effective to optimize two divisions by the same number. 48 We make this a param, and it shall be called N in the remainder of 49 this comment. 50 51 Second, if trapping math is active, we have less freedom on where 52 to insert divisions: we can only do so in basic blocks that already 53 contain one. (If divisions don't trap, instead, we can insert 54 divisions elsewhere, which will be in blocks that are common dominators 55 of those that have the division). 56 57 We really don't want to compute the reciprocal unless a division will 58 be found. To do this, we won't insert the division in a basic block 59 that has less than N divisions *post-dominating* it. 60 61 The algorithm constructs a subset of the dominator tree, holding the 62 blocks containing the divisions and the common dominators to them, 63 and walk it twice. The first walk is in post-order, and it annotates 64 each block with the number of divisions that post-dominate it: this 65 gives information on where divisions can be inserted profitably. 66 The second walk is in pre-order, and it inserts divisions as explained 67 above, and replaces divisions by multiplications. 68 69 In the best case, the cost of the pass is O(n_statements). In the 70 worst-case, the cost is due to creating the dominator tree subset, 71 with a cost of O(n_basic_blocks ^ 2); however this can only happen 72 for n_statements / n_basic_blocks statements. So, the amortized cost 73 of creating the dominator tree subset is O(n_basic_blocks) and the 74 worst-case cost of the pass is O(n_statements * n_basic_blocks). 75 76 More practically, the cost will be small because there are few 77 divisions, and they tend to be in the same basic block, so insert_bb 78 is called very few times. 79 80 If we did this using domwalk.c, an efficient implementation would have 81 to work on all the variables in a single pass, because we could not 82 work on just a subset of the dominator tree, as we do now, and the 83 cost would also be something like O(n_statements * n_basic_blocks). 84 The data structures would be more complex in order to work on all the 85 variables in a single pass. */ 86 87 #include "config.h" 88 #include "system.h" 89 #include "coretypes.h" 90 #include "backend.h" 91 #include "target.h" 92 #include "rtl.h" 93 #include "tree.h" 94 #include "gimple.h" 95 #include "predict.h" 96 #include "alloc-pool.h" 97 #include "tree-pass.h" 98 #include "ssa.h" 99 #include "optabs-tree.h" 100 #include "gimple-pretty-print.h" 101 #include "alias.h" 102 #include "fold-const.h" 103 #include "gimple-fold.h" 104 #include "gimple-iterator.h" 105 #include "gimplify.h" 106 #include "gimplify-me.h" 107 #include "stor-layout.h" 108 #include "tree-cfg.h" 109 #include "tree-dfa.h" 110 #include "tree-ssa.h" 111 #include "builtins.h" 112 #include "params.h" 113 #include "internal-fn.h" 114 #include "case-cfn-macros.h" 115 #include "optabs-libfuncs.h" 116 #include "tree-eh.h" 117 #include "targhooks.h" 118 #include "domwalk.h" 119 120 /* This structure represents one basic block that either computes a 121 division, or is a common dominator for basic block that compute a 122 division. */ 123 struct occurrence { 124 /* The basic block represented by this structure. */ 125 basic_block bb; 126 127 /* If non-NULL, the SSA_NAME holding the definition for a reciprocal 128 inserted in BB. */ 129 tree recip_def; 130 131 /* If non-NULL, the SSA_NAME holding the definition for a squared 132 reciprocal inserted in BB. */ 133 tree square_recip_def; 134 135 /* If non-NULL, the GIMPLE_ASSIGN for a reciprocal computation that 136 was inserted in BB. */ 137 gimple *recip_def_stmt; 138 139 /* Pointer to a list of "struct occurrence"s for blocks dominated 140 by BB. */ 141 struct occurrence *children; 142 143 /* Pointer to the next "struct occurrence"s in the list of blocks 144 sharing a common dominator. */ 145 struct occurrence *next; 146 147 /* The number of divisions that are in BB before compute_merit. The 148 number of divisions that are in BB or post-dominate it after 149 compute_merit. */ 150 int num_divisions; 151 152 /* True if the basic block has a division, false if it is a common 153 dominator for basic blocks that do. If it is false and trapping 154 math is active, BB is not a candidate for inserting a reciprocal. */ 155 bool bb_has_division; 156 }; 157 158 static struct 159 { 160 /* Number of 1.0/X ops inserted. */ 161 int rdivs_inserted; 162 163 /* Number of 1.0/FUNC ops inserted. */ 164 int rfuncs_inserted; 165 } reciprocal_stats; 166 167 static struct 168 { 169 /* Number of cexpi calls inserted. */ 170 int inserted; 171 } sincos_stats; 172 173 static struct 174 { 175 /* Number of widening multiplication ops inserted. */ 176 int widen_mults_inserted; 177 178 /* Number of integer multiply-and-accumulate ops inserted. */ 179 int maccs_inserted; 180 181 /* Number of fp fused multiply-add ops inserted. */ 182 int fmas_inserted; 183 184 /* Number of divmod calls inserted. */ 185 int divmod_calls_inserted; 186 } widen_mul_stats; 187 188 /* The instance of "struct occurrence" representing the highest 189 interesting block in the dominator tree. */ 190 static struct occurrence *occ_head; 191 192 /* Allocation pool for getting instances of "struct occurrence". */ 193 static object_allocator<occurrence> *occ_pool; 194 195 196 197 /* Allocate and return a new struct occurrence for basic block BB, and 198 whose children list is headed by CHILDREN. */ 199 static struct occurrence * 200 occ_new (basic_block bb, struct occurrence *children) 201 { 202 struct occurrence *occ; 203 204 bb->aux = occ = occ_pool->allocate (); 205 memset (occ, 0, sizeof (struct occurrence)); 206 207 occ->bb = bb; 208 occ->children = children; 209 return occ; 210 } 211 212 213 /* Insert NEW_OCC into our subset of the dominator tree. P_HEAD points to a 214 list of "struct occurrence"s, one per basic block, having IDOM as 215 their common dominator. 216 217 We try to insert NEW_OCC as deep as possible in the tree, and we also 218 insert any other block that is a common dominator for BB and one 219 block already in the tree. */ 220 221 static void 222 insert_bb (struct occurrence *new_occ, basic_block idom, 223 struct occurrence **p_head) 224 { 225 struct occurrence *occ, **p_occ; 226 227 for (p_occ = p_head; (occ = *p_occ) != NULL; ) 228 { 229 basic_block bb = new_occ->bb, occ_bb = occ->bb; 230 basic_block dom = nearest_common_dominator (CDI_DOMINATORS, occ_bb, bb); 231 if (dom == bb) 232 { 233 /* BB dominates OCC_BB. OCC becomes NEW_OCC's child: remove OCC 234 from its list. */ 235 *p_occ = occ->next; 236 occ->next = new_occ->children; 237 new_occ->children = occ; 238 239 /* Try the next block (it may as well be dominated by BB). */ 240 } 241 242 else if (dom == occ_bb) 243 { 244 /* OCC_BB dominates BB. Tail recurse to look deeper. */ 245 insert_bb (new_occ, dom, &occ->children); 246 return; 247 } 248 249 else if (dom != idom) 250 { 251 gcc_assert (!dom->aux); 252 253 /* There is a dominator between IDOM and BB, add it and make 254 two children out of NEW_OCC and OCC. First, remove OCC from 255 its list. */ 256 *p_occ = occ->next; 257 new_occ->next = occ; 258 occ->next = NULL; 259 260 /* None of the previous blocks has DOM as a dominator: if we tail 261 recursed, we would reexamine them uselessly. Just switch BB with 262 DOM, and go on looking for blocks dominated by DOM. */ 263 new_occ = occ_new (dom, new_occ); 264 } 265 266 else 267 { 268 /* Nothing special, go on with the next element. */ 269 p_occ = &occ->next; 270 } 271 } 272 273 /* No place was found as a child of IDOM. Make BB a sibling of IDOM. */ 274 new_occ->next = *p_head; 275 *p_head = new_occ; 276 } 277 278 /* Register that we found a division in BB. 279 IMPORTANCE is a measure of how much weighting to give 280 that division. Use IMPORTANCE = 2 to register a single 281 division. If the division is going to be found multiple 282 times use 1 (as it is with squares). */ 283 284 static inline void 285 register_division_in (basic_block bb, int importance) 286 { 287 struct occurrence *occ; 288 289 occ = (struct occurrence *) bb->aux; 290 if (!occ) 291 { 292 occ = occ_new (bb, NULL); 293 insert_bb (occ, ENTRY_BLOCK_PTR_FOR_FN (cfun), &occ_head); 294 } 295 296 occ->bb_has_division = true; 297 occ->num_divisions += importance; 298 } 299 300 301 /* Compute the number of divisions that postdominate each block in OCC and 302 its children. */ 303 304 static void 305 compute_merit (struct occurrence *occ) 306 { 307 struct occurrence *occ_child; 308 basic_block dom = occ->bb; 309 310 for (occ_child = occ->children; occ_child; occ_child = occ_child->next) 311 { 312 basic_block bb; 313 if (occ_child->children) 314 compute_merit (occ_child); 315 316 if (flag_exceptions) 317 bb = single_noncomplex_succ (dom); 318 else 319 bb = dom; 320 321 if (dominated_by_p (CDI_POST_DOMINATORS, bb, occ_child->bb)) 322 occ->num_divisions += occ_child->num_divisions; 323 } 324 } 325 326 327 /* Return whether USE_STMT is a floating-point division by DEF. */ 328 static inline bool 329 is_division_by (gimple *use_stmt, tree def) 330 { 331 return is_gimple_assign (use_stmt) 332 && gimple_assign_rhs_code (use_stmt) == RDIV_EXPR 333 && gimple_assign_rhs2 (use_stmt) == def 334 /* Do not recognize x / x as valid division, as we are getting 335 confused later by replacing all immediate uses x in such 336 a stmt. */ 337 && gimple_assign_rhs1 (use_stmt) != def; 338 } 339 340 /* Return whether USE_STMT is DEF * DEF. */ 341 static inline bool 342 is_square_of (gimple *use_stmt, tree def) 343 { 344 if (gimple_code (use_stmt) == GIMPLE_ASSIGN 345 && gimple_assign_rhs_code (use_stmt) == MULT_EXPR) 346 { 347 tree op0 = gimple_assign_rhs1 (use_stmt); 348 tree op1 = gimple_assign_rhs2 (use_stmt); 349 350 return op0 == op1 && op0 == def; 351 } 352 return 0; 353 } 354 355 /* Return whether USE_STMT is a floating-point division by 356 DEF * DEF. */ 357 static inline bool 358 is_division_by_square (gimple *use_stmt, tree def) 359 { 360 if (gimple_code (use_stmt) == GIMPLE_ASSIGN 361 && gimple_assign_rhs_code (use_stmt) == RDIV_EXPR 362 && gimple_assign_rhs1 (use_stmt) != gimple_assign_rhs2 (use_stmt)) 363 { 364 tree denominator = gimple_assign_rhs2 (use_stmt); 365 if (TREE_CODE (denominator) == SSA_NAME) 366 { 367 return is_square_of (SSA_NAME_DEF_STMT (denominator), def); 368 } 369 } 370 return 0; 371 } 372 373 /* Walk the subset of the dominator tree rooted at OCC, setting the 374 RECIP_DEF field to a definition of 1.0 / DEF that can be used in 375 the given basic block. The field may be left NULL, of course, 376 if it is not possible or profitable to do the optimization. 377 378 DEF_BSI is an iterator pointing at the statement defining DEF. 379 If RECIP_DEF is set, a dominator already has a computation that can 380 be used. 381 382 If should_insert_square_recip is set, then this also inserts 383 the square of the reciprocal immediately after the definition 384 of the reciprocal. */ 385 386 static void 387 insert_reciprocals (gimple_stmt_iterator *def_gsi, struct occurrence *occ, 388 tree def, tree recip_def, tree square_recip_def, 389 int should_insert_square_recip, int threshold) 390 { 391 tree type; 392 gassign *new_stmt, *new_square_stmt; 393 gimple_stmt_iterator gsi; 394 struct occurrence *occ_child; 395 396 if (!recip_def 397 && (occ->bb_has_division || !flag_trapping_math) 398 /* Divide by two as all divisions are counted twice in 399 the costing loop. */ 400 && occ->num_divisions / 2 >= threshold) 401 { 402 /* Make a variable with the replacement and substitute it. */ 403 type = TREE_TYPE (def); 404 recip_def = create_tmp_reg (type, "reciptmp"); 405 new_stmt = gimple_build_assign (recip_def, RDIV_EXPR, 406 build_one_cst (type), def); 407 408 if (should_insert_square_recip) 409 { 410 square_recip_def = create_tmp_reg (type, "powmult_reciptmp"); 411 new_square_stmt = gimple_build_assign (square_recip_def, MULT_EXPR, 412 recip_def, recip_def); 413 } 414 415 if (occ->bb_has_division) 416 { 417 /* Case 1: insert before an existing division. */ 418 gsi = gsi_after_labels (occ->bb); 419 while (!gsi_end_p (gsi) 420 && (!is_division_by (gsi_stmt (gsi), def)) 421 && (!is_division_by_square (gsi_stmt (gsi), def))) 422 gsi_next (&gsi); 423 424 gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT); 425 if (should_insert_square_recip) 426 gsi_insert_before (&gsi, new_square_stmt, GSI_SAME_STMT); 427 } 428 else if (def_gsi && occ->bb == def_gsi->bb) 429 { 430 /* Case 2: insert right after the definition. Note that this will 431 never happen if the definition statement can throw, because in 432 that case the sole successor of the statement's basic block will 433 dominate all the uses as well. */ 434 gsi_insert_after (def_gsi, new_stmt, GSI_NEW_STMT); 435 if (should_insert_square_recip) 436 gsi_insert_after (def_gsi, new_square_stmt, GSI_NEW_STMT); 437 } 438 else 439 { 440 /* Case 3: insert in a basic block not containing defs/uses. */ 441 gsi = gsi_after_labels (occ->bb); 442 gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT); 443 if (should_insert_square_recip) 444 gsi_insert_before (&gsi, new_square_stmt, GSI_SAME_STMT); 445 } 446 447 reciprocal_stats.rdivs_inserted++; 448 449 occ->recip_def_stmt = new_stmt; 450 } 451 452 occ->recip_def = recip_def; 453 occ->square_recip_def = square_recip_def; 454 for (occ_child = occ->children; occ_child; occ_child = occ_child->next) 455 insert_reciprocals (def_gsi, occ_child, def, recip_def, 456 square_recip_def, should_insert_square_recip, 457 threshold); 458 } 459 460 /* Replace occurrences of expr / (x * x) with expr * ((1 / x) * (1 / x)). 461 Take as argument the use for (x * x). */ 462 static inline void 463 replace_reciprocal_squares (use_operand_p use_p) 464 { 465 gimple *use_stmt = USE_STMT (use_p); 466 basic_block bb = gimple_bb (use_stmt); 467 struct occurrence *occ = (struct occurrence *) bb->aux; 468 469 if (optimize_bb_for_speed_p (bb) && occ->square_recip_def 470 && occ->recip_def) 471 { 472 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt); 473 gimple_assign_set_rhs_code (use_stmt, MULT_EXPR); 474 gimple_assign_set_rhs2 (use_stmt, occ->square_recip_def); 475 SET_USE (use_p, occ->square_recip_def); 476 fold_stmt_inplace (&gsi); 477 update_stmt (use_stmt); 478 } 479 } 480 481 482 /* Replace the division at USE_P with a multiplication by the reciprocal, if 483 possible. */ 484 485 static inline void 486 replace_reciprocal (use_operand_p use_p) 487 { 488 gimple *use_stmt = USE_STMT (use_p); 489 basic_block bb = gimple_bb (use_stmt); 490 struct occurrence *occ = (struct occurrence *) bb->aux; 491 492 if (optimize_bb_for_speed_p (bb) 493 && occ->recip_def && use_stmt != occ->recip_def_stmt) 494 { 495 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt); 496 gimple_assign_set_rhs_code (use_stmt, MULT_EXPR); 497 SET_USE (use_p, occ->recip_def); 498 fold_stmt_inplace (&gsi); 499 update_stmt (use_stmt); 500 } 501 } 502 503 504 /* Free OCC and return one more "struct occurrence" to be freed. */ 505 506 static struct occurrence * 507 free_bb (struct occurrence *occ) 508 { 509 struct occurrence *child, *next; 510 511 /* First get the two pointers hanging off OCC. */ 512 next = occ->next; 513 child = occ->children; 514 occ->bb->aux = NULL; 515 occ_pool->remove (occ); 516 517 /* Now ensure that we don't recurse unless it is necessary. */ 518 if (!child) 519 return next; 520 else 521 { 522 while (next) 523 next = free_bb (next); 524 525 return child; 526 } 527 } 528 529 530 /* Look for floating-point divisions among DEF's uses, and try to 531 replace them by multiplications with the reciprocal. Add 532 as many statements computing the reciprocal as needed. 533 534 DEF must be a GIMPLE register of a floating-point type. */ 535 536 static void 537 execute_cse_reciprocals_1 (gimple_stmt_iterator *def_gsi, tree def) 538 { 539 use_operand_p use_p, square_use_p; 540 imm_use_iterator use_iter, square_use_iter; 541 tree square_def; 542 struct occurrence *occ; 543 int count = 0; 544 int threshold; 545 int square_recip_count = 0; 546 int sqrt_recip_count = 0; 547 548 gcc_assert (FLOAT_TYPE_P (TREE_TYPE (def)) && TREE_CODE (def) == SSA_NAME); 549 threshold = targetm.min_divisions_for_recip_mul (TYPE_MODE (TREE_TYPE (def))); 550 551 /* If DEF is a square (x * x), count the number of divisions by x. 552 If there are more divisions by x than by (DEF * DEF), prefer to optimize 553 the reciprocal of x instead of DEF. This improves cases like: 554 def = x * x 555 t0 = a / def 556 t1 = b / def 557 t2 = c / x 558 Reciprocal optimization of x results in 1 division rather than 2 or 3. */ 559 gimple *def_stmt = SSA_NAME_DEF_STMT (def); 560 561 if (is_gimple_assign (def_stmt) 562 && gimple_assign_rhs_code (def_stmt) == MULT_EXPR 563 && TREE_CODE (gimple_assign_rhs1 (def_stmt)) == SSA_NAME 564 && gimple_assign_rhs1 (def_stmt) == gimple_assign_rhs2 (def_stmt)) 565 { 566 tree op0 = gimple_assign_rhs1 (def_stmt); 567 568 FOR_EACH_IMM_USE_FAST (use_p, use_iter, op0) 569 { 570 gimple *use_stmt = USE_STMT (use_p); 571 if (is_division_by (use_stmt, op0)) 572 sqrt_recip_count++; 573 } 574 } 575 576 FOR_EACH_IMM_USE_FAST (use_p, use_iter, def) 577 { 578 gimple *use_stmt = USE_STMT (use_p); 579 if (is_division_by (use_stmt, def)) 580 { 581 register_division_in (gimple_bb (use_stmt), 2); 582 count++; 583 } 584 585 if (is_square_of (use_stmt, def)) 586 { 587 square_def = gimple_assign_lhs (use_stmt); 588 FOR_EACH_IMM_USE_FAST (square_use_p, square_use_iter, square_def) 589 { 590 gimple *square_use_stmt = USE_STMT (square_use_p); 591 if (is_division_by (square_use_stmt, square_def)) 592 { 593 /* This is executed twice for each division by a square. */ 594 register_division_in (gimple_bb (square_use_stmt), 1); 595 square_recip_count++; 596 } 597 } 598 } 599 } 600 601 /* Square reciprocals were counted twice above. */ 602 square_recip_count /= 2; 603 604 /* If it is more profitable to optimize 1 / x, don't optimize 1 / (x * x). */ 605 if (sqrt_recip_count > square_recip_count) 606 goto out; 607 608 /* Do the expensive part only if we can hope to optimize something. */ 609 if (count + square_recip_count >= threshold && count >= 1) 610 { 611 gimple *use_stmt; 612 for (occ = occ_head; occ; occ = occ->next) 613 { 614 compute_merit (occ); 615 insert_reciprocals (def_gsi, occ, def, NULL, NULL, 616 square_recip_count, threshold); 617 } 618 619 FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, def) 620 { 621 if (is_division_by (use_stmt, def)) 622 { 623 FOR_EACH_IMM_USE_ON_STMT (use_p, use_iter) 624 replace_reciprocal (use_p); 625 } 626 else if (square_recip_count > 0 && is_square_of (use_stmt, def)) 627 { 628 FOR_EACH_IMM_USE_ON_STMT (use_p, use_iter) 629 { 630 /* Find all uses of the square that are divisions and 631 * replace them by multiplications with the inverse. */ 632 imm_use_iterator square_iterator; 633 gimple *powmult_use_stmt = USE_STMT (use_p); 634 tree powmult_def_name = gimple_assign_lhs (powmult_use_stmt); 635 636 FOR_EACH_IMM_USE_STMT (powmult_use_stmt, 637 square_iterator, powmult_def_name) 638 FOR_EACH_IMM_USE_ON_STMT (square_use_p, square_iterator) 639 { 640 gimple *powmult_use_stmt = USE_STMT (square_use_p); 641 if (is_division_by (powmult_use_stmt, powmult_def_name)) 642 replace_reciprocal_squares (square_use_p); 643 } 644 } 645 } 646 } 647 } 648 649 out: 650 for (occ = occ_head; occ; ) 651 occ = free_bb (occ); 652 653 occ_head = NULL; 654 } 655 656 /* Return an internal function that implements the reciprocal of CALL, 657 or IFN_LAST if there is no such function that the target supports. */ 658 659 internal_fn 660 internal_fn_reciprocal (gcall *call) 661 { 662 internal_fn ifn; 663 664 switch (gimple_call_combined_fn (call)) 665 { 666 CASE_CFN_SQRT: 667 CASE_CFN_SQRT_FN: 668 ifn = IFN_RSQRT; 669 break; 670 671 default: 672 return IFN_LAST; 673 } 674 675 tree_pair types = direct_internal_fn_types (ifn, call); 676 if (!direct_internal_fn_supported_p (ifn, types, OPTIMIZE_FOR_SPEED)) 677 return IFN_LAST; 678 679 return ifn; 680 } 681 682 /* Go through all the floating-point SSA_NAMEs, and call 683 execute_cse_reciprocals_1 on each of them. */ 684 namespace { 685 686 const pass_data pass_data_cse_reciprocals = 687 { 688 GIMPLE_PASS, /* type */ 689 "recip", /* name */ 690 OPTGROUP_NONE, /* optinfo_flags */ 691 TV_TREE_RECIP, /* tv_id */ 692 PROP_ssa, /* properties_required */ 693 0, /* properties_provided */ 694 0, /* properties_destroyed */ 695 0, /* todo_flags_start */ 696 TODO_update_ssa, /* todo_flags_finish */ 697 }; 698 699 class pass_cse_reciprocals : public gimple_opt_pass 700 { 701 public: 702 pass_cse_reciprocals (gcc::context *ctxt) 703 : gimple_opt_pass (pass_data_cse_reciprocals, ctxt) 704 {} 705 706 /* opt_pass methods: */ 707 virtual bool gate (function *) { return optimize && flag_reciprocal_math; } 708 virtual unsigned int execute (function *); 709 710 }; // class pass_cse_reciprocals 711 712 unsigned int 713 pass_cse_reciprocals::execute (function *fun) 714 { 715 basic_block bb; 716 tree arg; 717 718 occ_pool = new object_allocator<occurrence> ("dominators for recip"); 719 720 memset (&reciprocal_stats, 0, sizeof (reciprocal_stats)); 721 calculate_dominance_info (CDI_DOMINATORS); 722 calculate_dominance_info (CDI_POST_DOMINATORS); 723 724 if (flag_checking) 725 FOR_EACH_BB_FN (bb, fun) 726 gcc_assert (!bb->aux); 727 728 for (arg = DECL_ARGUMENTS (fun->decl); arg; arg = DECL_CHAIN (arg)) 729 if (FLOAT_TYPE_P (TREE_TYPE (arg)) 730 && is_gimple_reg (arg)) 731 { 732 tree name = ssa_default_def (fun, arg); 733 if (name) 734 execute_cse_reciprocals_1 (NULL, name); 735 } 736 737 FOR_EACH_BB_FN (bb, fun) 738 { 739 tree def; 740 741 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi); 742 gsi_next (&gsi)) 743 { 744 gphi *phi = gsi.phi (); 745 def = PHI_RESULT (phi); 746 if (! virtual_operand_p (def) 747 && FLOAT_TYPE_P (TREE_TYPE (def))) 748 execute_cse_reciprocals_1 (NULL, def); 749 } 750 751 for (gimple_stmt_iterator gsi = gsi_after_labels (bb); !gsi_end_p (gsi); 752 gsi_next (&gsi)) 753 { 754 gimple *stmt = gsi_stmt (gsi); 755 756 if (gimple_has_lhs (stmt) 757 && (def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF)) != NULL 758 && FLOAT_TYPE_P (TREE_TYPE (def)) 759 && TREE_CODE (def) == SSA_NAME) 760 execute_cse_reciprocals_1 (&gsi, def); 761 } 762 763 if (optimize_bb_for_size_p (bb)) 764 continue; 765 766 /* Scan for a/func(b) and convert it to reciprocal a*rfunc(b). */ 767 for (gimple_stmt_iterator gsi = gsi_after_labels (bb); !gsi_end_p (gsi); 768 gsi_next (&gsi)) 769 { 770 gimple *stmt = gsi_stmt (gsi); 771 772 if (is_gimple_assign (stmt) 773 && gimple_assign_rhs_code (stmt) == RDIV_EXPR) 774 { 775 tree arg1 = gimple_assign_rhs2 (stmt); 776 gimple *stmt1; 777 778 if (TREE_CODE (arg1) != SSA_NAME) 779 continue; 780 781 stmt1 = SSA_NAME_DEF_STMT (arg1); 782 783 if (is_gimple_call (stmt1) 784 && gimple_call_lhs (stmt1)) 785 { 786 bool fail; 787 imm_use_iterator ui; 788 use_operand_p use_p; 789 tree fndecl = NULL_TREE; 790 791 gcall *call = as_a <gcall *> (stmt1); 792 internal_fn ifn = internal_fn_reciprocal (call); 793 if (ifn == IFN_LAST) 794 { 795 fndecl = gimple_call_fndecl (call); 796 if (!fndecl 797 || DECL_BUILT_IN_CLASS (fndecl) != BUILT_IN_MD) 798 continue; 799 fndecl = targetm.builtin_reciprocal (fndecl); 800 if (!fndecl) 801 continue; 802 } 803 804 /* Check that all uses of the SSA name are divisions, 805 otherwise replacing the defining statement will do 806 the wrong thing. */ 807 fail = false; 808 FOR_EACH_IMM_USE_FAST (use_p, ui, arg1) 809 { 810 gimple *stmt2 = USE_STMT (use_p); 811 if (is_gimple_debug (stmt2)) 812 continue; 813 if (!is_gimple_assign (stmt2) 814 || gimple_assign_rhs_code (stmt2) != RDIV_EXPR 815 || gimple_assign_rhs1 (stmt2) == arg1 816 || gimple_assign_rhs2 (stmt2) != arg1) 817 { 818 fail = true; 819 break; 820 } 821 } 822 if (fail) 823 continue; 824 825 gimple_replace_ssa_lhs (call, arg1); 826 if (gimple_call_internal_p (call) != (ifn != IFN_LAST)) 827 { 828 auto_vec<tree, 4> args; 829 for (unsigned int i = 0; 830 i < gimple_call_num_args (call); i++) 831 args.safe_push (gimple_call_arg (call, i)); 832 gcall *stmt2; 833 if (ifn == IFN_LAST) 834 stmt2 = gimple_build_call_vec (fndecl, args); 835 else 836 stmt2 = gimple_build_call_internal_vec (ifn, args); 837 gimple_call_set_lhs (stmt2, arg1); 838 if (gimple_vdef (call)) 839 { 840 gimple_set_vdef (stmt2, gimple_vdef (call)); 841 SSA_NAME_DEF_STMT (gimple_vdef (stmt2)) = stmt2; 842 } 843 gimple_call_set_nothrow (stmt2, 844 gimple_call_nothrow_p (call)); 845 gimple_set_vuse (stmt2, gimple_vuse (call)); 846 gimple_stmt_iterator gsi2 = gsi_for_stmt (call); 847 gsi_replace (&gsi2, stmt2, true); 848 } 849 else 850 { 851 if (ifn == IFN_LAST) 852 gimple_call_set_fndecl (call, fndecl); 853 else 854 gimple_call_set_internal_fn (call, ifn); 855 update_stmt (call); 856 } 857 reciprocal_stats.rfuncs_inserted++; 858 859 FOR_EACH_IMM_USE_STMT (stmt, ui, arg1) 860 { 861 gimple_stmt_iterator gsi = gsi_for_stmt (stmt); 862 gimple_assign_set_rhs_code (stmt, MULT_EXPR); 863 fold_stmt_inplace (&gsi); 864 update_stmt (stmt); 865 } 866 } 867 } 868 } 869 } 870 871 statistics_counter_event (fun, "reciprocal divs inserted", 872 reciprocal_stats.rdivs_inserted); 873 statistics_counter_event (fun, "reciprocal functions inserted", 874 reciprocal_stats.rfuncs_inserted); 875 876 free_dominance_info (CDI_DOMINATORS); 877 free_dominance_info (CDI_POST_DOMINATORS); 878 delete occ_pool; 879 return 0; 880 } 881 882 } // anon namespace 883 884 gimple_opt_pass * 885 make_pass_cse_reciprocals (gcc::context *ctxt) 886 { 887 return new pass_cse_reciprocals (ctxt); 888 } 889 890 /* Records an occurrence at statement USE_STMT in the vector of trees 891 STMTS if it is dominated by *TOP_BB or dominates it or this basic block 892 is not yet initialized. Returns true if the occurrence was pushed on 893 the vector. Adjusts *TOP_BB to be the basic block dominating all 894 statements in the vector. */ 895 896 static bool 897 maybe_record_sincos (vec<gimple *> *stmts, 898 basic_block *top_bb, gimple *use_stmt) 899 { 900 basic_block use_bb = gimple_bb (use_stmt); 901 if (*top_bb 902 && (*top_bb == use_bb 903 || dominated_by_p (CDI_DOMINATORS, use_bb, *top_bb))) 904 stmts->safe_push (use_stmt); 905 else if (!*top_bb 906 || dominated_by_p (CDI_DOMINATORS, *top_bb, use_bb)) 907 { 908 stmts->safe_push (use_stmt); 909 *top_bb = use_bb; 910 } 911 else 912 return false; 913 914 return true; 915 } 916 917 /* Look for sin, cos and cexpi calls with the same argument NAME and 918 create a single call to cexpi CSEing the result in this case. 919 We first walk over all immediate uses of the argument collecting 920 statements that we can CSE in a vector and in a second pass replace 921 the statement rhs with a REALPART or IMAGPART expression on the 922 result of the cexpi call we insert before the use statement that 923 dominates all other candidates. */ 924 925 static bool 926 execute_cse_sincos_1 (tree name) 927 { 928 gimple_stmt_iterator gsi; 929 imm_use_iterator use_iter; 930 tree fndecl, res, type; 931 gimple *def_stmt, *use_stmt, *stmt; 932 int seen_cos = 0, seen_sin = 0, seen_cexpi = 0; 933 auto_vec<gimple *> stmts; 934 basic_block top_bb = NULL; 935 int i; 936 bool cfg_changed = false; 937 938 type = TREE_TYPE (name); 939 FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, name) 940 { 941 if (gimple_code (use_stmt) != GIMPLE_CALL 942 || !gimple_call_lhs (use_stmt)) 943 continue; 944 945 switch (gimple_call_combined_fn (use_stmt)) 946 { 947 CASE_CFN_COS: 948 seen_cos |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0; 949 break; 950 951 CASE_CFN_SIN: 952 seen_sin |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0; 953 break; 954 955 CASE_CFN_CEXPI: 956 seen_cexpi |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0; 957 break; 958 959 default:; 960 } 961 } 962 963 if (seen_cos + seen_sin + seen_cexpi <= 1) 964 return false; 965 966 /* Simply insert cexpi at the beginning of top_bb but not earlier than 967 the name def statement. */ 968 fndecl = mathfn_built_in (type, BUILT_IN_CEXPI); 969 if (!fndecl) 970 return false; 971 stmt = gimple_build_call (fndecl, 1, name); 972 res = make_temp_ssa_name (TREE_TYPE (TREE_TYPE (fndecl)), stmt, "sincostmp"); 973 gimple_call_set_lhs (stmt, res); 974 975 def_stmt = SSA_NAME_DEF_STMT (name); 976 if (!SSA_NAME_IS_DEFAULT_DEF (name) 977 && gimple_code (def_stmt) != GIMPLE_PHI 978 && gimple_bb (def_stmt) == top_bb) 979 { 980 gsi = gsi_for_stmt (def_stmt); 981 gsi_insert_after (&gsi, stmt, GSI_SAME_STMT); 982 } 983 else 984 { 985 gsi = gsi_after_labels (top_bb); 986 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT); 987 } 988 sincos_stats.inserted++; 989 990 /* And adjust the recorded old call sites. */ 991 for (i = 0; stmts.iterate (i, &use_stmt); ++i) 992 { 993 tree rhs = NULL; 994 995 switch (gimple_call_combined_fn (use_stmt)) 996 { 997 CASE_CFN_COS: 998 rhs = fold_build1 (REALPART_EXPR, type, res); 999 break; 1000 1001 CASE_CFN_SIN: 1002 rhs = fold_build1 (IMAGPART_EXPR, type, res); 1003 break; 1004 1005 CASE_CFN_CEXPI: 1006 rhs = res; 1007 break; 1008 1009 default:; 1010 gcc_unreachable (); 1011 } 1012 1013 /* Replace call with a copy. */ 1014 stmt = gimple_build_assign (gimple_call_lhs (use_stmt), rhs); 1015 1016 gsi = gsi_for_stmt (use_stmt); 1017 gsi_replace (&gsi, stmt, true); 1018 if (gimple_purge_dead_eh_edges (gimple_bb (stmt))) 1019 cfg_changed = true; 1020 } 1021 1022 return cfg_changed; 1023 } 1024 1025 /* To evaluate powi(x,n), the floating point value x raised to the 1026 constant integer exponent n, we use a hybrid algorithm that 1027 combines the "window method" with look-up tables. For an 1028 introduction to exponentiation algorithms and "addition chains", 1029 see section 4.6.3, "Evaluation of Powers" of Donald E. Knuth, 1030 "Seminumerical Algorithms", Vol. 2, "The Art of Computer Programming", 1031 3rd Edition, 1998, and Daniel M. Gordon, "A Survey of Fast Exponentiation 1032 Methods", Journal of Algorithms, Vol. 27, pp. 129-146, 1998. */ 1033 1034 /* Provide a default value for POWI_MAX_MULTS, the maximum number of 1035 multiplications to inline before calling the system library's pow 1036 function. powi(x,n) requires at worst 2*bits(n)-2 multiplications, 1037 so this default never requires calling pow, powf or powl. */ 1038 1039 #ifndef POWI_MAX_MULTS 1040 #define POWI_MAX_MULTS (2*HOST_BITS_PER_WIDE_INT-2) 1041 #endif 1042 1043 /* The size of the "optimal power tree" lookup table. All 1044 exponents less than this value are simply looked up in the 1045 powi_table below. This threshold is also used to size the 1046 cache of pseudo registers that hold intermediate results. */ 1047 #define POWI_TABLE_SIZE 256 1048 1049 /* The size, in bits of the window, used in the "window method" 1050 exponentiation algorithm. This is equivalent to a radix of 1051 (1<<POWI_WINDOW_SIZE) in the corresponding "m-ary method". */ 1052 #define POWI_WINDOW_SIZE 3 1053 1054 /* The following table is an efficient representation of an 1055 "optimal power tree". For each value, i, the corresponding 1056 value, j, in the table states than an optimal evaluation 1057 sequence for calculating pow(x,i) can be found by evaluating 1058 pow(x,j)*pow(x,i-j). An optimal power tree for the first 1059 100 integers is given in Knuth's "Seminumerical algorithms". */ 1060 1061 static const unsigned char powi_table[POWI_TABLE_SIZE] = 1062 { 1063 0, 1, 1, 2, 2, 3, 3, 4, /* 0 - 7 */ 1064 4, 6, 5, 6, 6, 10, 7, 9, /* 8 - 15 */ 1065 8, 16, 9, 16, 10, 12, 11, 13, /* 16 - 23 */ 1066 12, 17, 13, 18, 14, 24, 15, 26, /* 24 - 31 */ 1067 16, 17, 17, 19, 18, 33, 19, 26, /* 32 - 39 */ 1068 20, 25, 21, 40, 22, 27, 23, 44, /* 40 - 47 */ 1069 24, 32, 25, 34, 26, 29, 27, 44, /* 48 - 55 */ 1070 28, 31, 29, 34, 30, 60, 31, 36, /* 56 - 63 */ 1071 32, 64, 33, 34, 34, 46, 35, 37, /* 64 - 71 */ 1072 36, 65, 37, 50, 38, 48, 39, 69, /* 72 - 79 */ 1073 40, 49, 41, 43, 42, 51, 43, 58, /* 80 - 87 */ 1074 44, 64, 45, 47, 46, 59, 47, 76, /* 88 - 95 */ 1075 48, 65, 49, 66, 50, 67, 51, 66, /* 96 - 103 */ 1076 52, 70, 53, 74, 54, 104, 55, 74, /* 104 - 111 */ 1077 56, 64, 57, 69, 58, 78, 59, 68, /* 112 - 119 */ 1078 60, 61, 61, 80, 62, 75, 63, 68, /* 120 - 127 */ 1079 64, 65, 65, 128, 66, 129, 67, 90, /* 128 - 135 */ 1080 68, 73, 69, 131, 70, 94, 71, 88, /* 136 - 143 */ 1081 72, 128, 73, 98, 74, 132, 75, 121, /* 144 - 151 */ 1082 76, 102, 77, 124, 78, 132, 79, 106, /* 152 - 159 */ 1083 80, 97, 81, 160, 82, 99, 83, 134, /* 160 - 167 */ 1084 84, 86, 85, 95, 86, 160, 87, 100, /* 168 - 175 */ 1085 88, 113, 89, 98, 90, 107, 91, 122, /* 176 - 183 */ 1086 92, 111, 93, 102, 94, 126, 95, 150, /* 184 - 191 */ 1087 96, 128, 97, 130, 98, 133, 99, 195, /* 192 - 199 */ 1088 100, 128, 101, 123, 102, 164, 103, 138, /* 200 - 207 */ 1089 104, 145, 105, 146, 106, 109, 107, 149, /* 208 - 215 */ 1090 108, 200, 109, 146, 110, 170, 111, 157, /* 216 - 223 */ 1091 112, 128, 113, 130, 114, 182, 115, 132, /* 224 - 231 */ 1092 116, 200, 117, 132, 118, 158, 119, 206, /* 232 - 239 */ 1093 120, 240, 121, 162, 122, 147, 123, 152, /* 240 - 247 */ 1094 124, 166, 125, 214, 126, 138, 127, 153, /* 248 - 255 */ 1095 }; 1096 1097 1098 /* Return the number of multiplications required to calculate 1099 powi(x,n) where n is less than POWI_TABLE_SIZE. This is a 1100 subroutine of powi_cost. CACHE is an array indicating 1101 which exponents have already been calculated. */ 1102 1103 static int 1104 powi_lookup_cost (unsigned HOST_WIDE_INT n, bool *cache) 1105 { 1106 /* If we've already calculated this exponent, then this evaluation 1107 doesn't require any additional multiplications. */ 1108 if (cache[n]) 1109 return 0; 1110 1111 cache[n] = true; 1112 return powi_lookup_cost (n - powi_table[n], cache) 1113 + powi_lookup_cost (powi_table[n], cache) + 1; 1114 } 1115 1116 /* Return the number of multiplications required to calculate 1117 powi(x,n) for an arbitrary x, given the exponent N. This 1118 function needs to be kept in sync with powi_as_mults below. */ 1119 1120 static int 1121 powi_cost (HOST_WIDE_INT n) 1122 { 1123 bool cache[POWI_TABLE_SIZE]; 1124 unsigned HOST_WIDE_INT digit; 1125 unsigned HOST_WIDE_INT val; 1126 int result; 1127 1128 if (n == 0) 1129 return 0; 1130 1131 /* Ignore the reciprocal when calculating the cost. */ 1132 val = (n < 0) ? -n : n; 1133 1134 /* Initialize the exponent cache. */ 1135 memset (cache, 0, POWI_TABLE_SIZE * sizeof (bool)); 1136 cache[1] = true; 1137 1138 result = 0; 1139 1140 while (val >= POWI_TABLE_SIZE) 1141 { 1142 if (val & 1) 1143 { 1144 digit = val & ((1 << POWI_WINDOW_SIZE) - 1); 1145 result += powi_lookup_cost (digit, cache) 1146 + POWI_WINDOW_SIZE + 1; 1147 val >>= POWI_WINDOW_SIZE; 1148 } 1149 else 1150 { 1151 val >>= 1; 1152 result++; 1153 } 1154 } 1155 1156 return result + powi_lookup_cost (val, cache); 1157 } 1158 1159 /* Recursive subroutine of powi_as_mults. This function takes the 1160 array, CACHE, of already calculated exponents and an exponent N and 1161 returns a tree that corresponds to CACHE[1]**N, with type TYPE. */ 1162 1163 static tree 1164 powi_as_mults_1 (gimple_stmt_iterator *gsi, location_t loc, tree type, 1165 HOST_WIDE_INT n, tree *cache) 1166 { 1167 tree op0, op1, ssa_target; 1168 unsigned HOST_WIDE_INT digit; 1169 gassign *mult_stmt; 1170 1171 if (n < POWI_TABLE_SIZE && cache[n]) 1172 return cache[n]; 1173 1174 ssa_target = make_temp_ssa_name (type, NULL, "powmult"); 1175 1176 if (n < POWI_TABLE_SIZE) 1177 { 1178 cache[n] = ssa_target; 1179 op0 = powi_as_mults_1 (gsi, loc, type, n - powi_table[n], cache); 1180 op1 = powi_as_mults_1 (gsi, loc, type, powi_table[n], cache); 1181 } 1182 else if (n & 1) 1183 { 1184 digit = n & ((1 << POWI_WINDOW_SIZE) - 1); 1185 op0 = powi_as_mults_1 (gsi, loc, type, n - digit, cache); 1186 op1 = powi_as_mults_1 (gsi, loc, type, digit, cache); 1187 } 1188 else 1189 { 1190 op0 = powi_as_mults_1 (gsi, loc, type, n >> 1, cache); 1191 op1 = op0; 1192 } 1193 1194 mult_stmt = gimple_build_assign (ssa_target, MULT_EXPR, op0, op1); 1195 gimple_set_location (mult_stmt, loc); 1196 gsi_insert_before (gsi, mult_stmt, GSI_SAME_STMT); 1197 1198 return ssa_target; 1199 } 1200 1201 /* Convert ARG0**N to a tree of multiplications of ARG0 with itself. 1202 This function needs to be kept in sync with powi_cost above. */ 1203 1204 static tree 1205 powi_as_mults (gimple_stmt_iterator *gsi, location_t loc, 1206 tree arg0, HOST_WIDE_INT n) 1207 { 1208 tree cache[POWI_TABLE_SIZE], result, type = TREE_TYPE (arg0); 1209 gassign *div_stmt; 1210 tree target; 1211 1212 if (n == 0) 1213 return build_real (type, dconst1); 1214 1215 memset (cache, 0, sizeof (cache)); 1216 cache[1] = arg0; 1217 1218 result = powi_as_mults_1 (gsi, loc, type, (n < 0) ? -n : n, cache); 1219 if (n >= 0) 1220 return result; 1221 1222 /* If the original exponent was negative, reciprocate the result. */ 1223 target = make_temp_ssa_name (type, NULL, "powmult"); 1224 div_stmt = gimple_build_assign (target, RDIV_EXPR, 1225 build_real (type, dconst1), result); 1226 gimple_set_location (div_stmt, loc); 1227 gsi_insert_before (gsi, div_stmt, GSI_SAME_STMT); 1228 1229 return target; 1230 } 1231 1232 /* ARG0 and N are the two arguments to a powi builtin in GSI with 1233 location info LOC. If the arguments are appropriate, create an 1234 equivalent sequence of statements prior to GSI using an optimal 1235 number of multiplications, and return an expession holding the 1236 result. */ 1237 1238 static tree 1239 gimple_expand_builtin_powi (gimple_stmt_iterator *gsi, location_t loc, 1240 tree arg0, HOST_WIDE_INT n) 1241 { 1242 /* Avoid largest negative number. */ 1243 if (n != -n 1244 && ((n >= -1 && n <= 2) 1245 || (optimize_function_for_speed_p (cfun) 1246 && powi_cost (n) <= POWI_MAX_MULTS))) 1247 return powi_as_mults (gsi, loc, arg0, n); 1248 1249 return NULL_TREE; 1250 } 1251 1252 /* Build a gimple call statement that calls FN with argument ARG. 1253 Set the lhs of the call statement to a fresh SSA name. Insert the 1254 statement prior to GSI's current position, and return the fresh 1255 SSA name. */ 1256 1257 static tree 1258 build_and_insert_call (gimple_stmt_iterator *gsi, location_t loc, 1259 tree fn, tree arg) 1260 { 1261 gcall *call_stmt; 1262 tree ssa_target; 1263 1264 call_stmt = gimple_build_call (fn, 1, arg); 1265 ssa_target = make_temp_ssa_name (TREE_TYPE (arg), NULL, "powroot"); 1266 gimple_set_lhs (call_stmt, ssa_target); 1267 gimple_set_location (call_stmt, loc); 1268 gsi_insert_before (gsi, call_stmt, GSI_SAME_STMT); 1269 1270 return ssa_target; 1271 } 1272 1273 /* Build a gimple binary operation with the given CODE and arguments 1274 ARG0, ARG1, assigning the result to a new SSA name for variable 1275 TARGET. Insert the statement prior to GSI's current position, and 1276 return the fresh SSA name.*/ 1277 1278 static tree 1279 build_and_insert_binop (gimple_stmt_iterator *gsi, location_t loc, 1280 const char *name, enum tree_code code, 1281 tree arg0, tree arg1) 1282 { 1283 tree result = make_temp_ssa_name (TREE_TYPE (arg0), NULL, name); 1284 gassign *stmt = gimple_build_assign (result, code, arg0, arg1); 1285 gimple_set_location (stmt, loc); 1286 gsi_insert_before (gsi, stmt, GSI_SAME_STMT); 1287 return result; 1288 } 1289 1290 /* Build a gimple reference operation with the given CODE and argument 1291 ARG, assigning the result to a new SSA name of TYPE with NAME. 1292 Insert the statement prior to GSI's current position, and return 1293 the fresh SSA name. */ 1294 1295 static inline tree 1296 build_and_insert_ref (gimple_stmt_iterator *gsi, location_t loc, tree type, 1297 const char *name, enum tree_code code, tree arg0) 1298 { 1299 tree result = make_temp_ssa_name (type, NULL, name); 1300 gimple *stmt = gimple_build_assign (result, build1 (code, type, arg0)); 1301 gimple_set_location (stmt, loc); 1302 gsi_insert_before (gsi, stmt, GSI_SAME_STMT); 1303 return result; 1304 } 1305 1306 /* Build a gimple assignment to cast VAL to TYPE. Insert the statement 1307 prior to GSI's current position, and return the fresh SSA name. */ 1308 1309 static tree 1310 build_and_insert_cast (gimple_stmt_iterator *gsi, location_t loc, 1311 tree type, tree val) 1312 { 1313 tree result = make_ssa_name (type); 1314 gassign *stmt = gimple_build_assign (result, NOP_EXPR, val); 1315 gimple_set_location (stmt, loc); 1316 gsi_insert_before (gsi, stmt, GSI_SAME_STMT); 1317 return result; 1318 } 1319 1320 struct pow_synth_sqrt_info 1321 { 1322 bool *factors; 1323 unsigned int deepest; 1324 unsigned int num_mults; 1325 }; 1326 1327 /* Return true iff the real value C can be represented as a 1328 sum of powers of 0.5 up to N. That is: 1329 C == SUM<i from 1..N> (a[i]*(0.5**i)) where a[i] is either 0 or 1. 1330 Record in INFO the various parameters of the synthesis algorithm such 1331 as the factors a[i], the maximum 0.5 power and the number of 1332 multiplications that will be required. */ 1333 1334 bool 1335 representable_as_half_series_p (REAL_VALUE_TYPE c, unsigned n, 1336 struct pow_synth_sqrt_info *info) 1337 { 1338 REAL_VALUE_TYPE factor = dconsthalf; 1339 REAL_VALUE_TYPE remainder = c; 1340 1341 info->deepest = 0; 1342 info->num_mults = 0; 1343 memset (info->factors, 0, n * sizeof (bool)); 1344 1345 for (unsigned i = 0; i < n; i++) 1346 { 1347 REAL_VALUE_TYPE res; 1348 1349 /* If something inexact happened bail out now. */ 1350 if (real_arithmetic (&res, MINUS_EXPR, &remainder, &factor)) 1351 return false; 1352 1353 /* We have hit zero. The number is representable as a sum 1354 of powers of 0.5. */ 1355 if (real_equal (&res, &dconst0)) 1356 { 1357 info->factors[i] = true; 1358 info->deepest = i + 1; 1359 return true; 1360 } 1361 else if (!REAL_VALUE_NEGATIVE (res)) 1362 { 1363 remainder = res; 1364 info->factors[i] = true; 1365 info->num_mults++; 1366 } 1367 else 1368 info->factors[i] = false; 1369 1370 real_arithmetic (&factor, MULT_EXPR, &factor, &dconsthalf); 1371 } 1372 return false; 1373 } 1374 1375 /* Return the tree corresponding to FN being applied 1376 to ARG N times at GSI and LOC. 1377 Look up previous results from CACHE if need be. 1378 cache[0] should contain just plain ARG i.e. FN applied to ARG 0 times. */ 1379 1380 static tree 1381 get_fn_chain (tree arg, unsigned int n, gimple_stmt_iterator *gsi, 1382 tree fn, location_t loc, tree *cache) 1383 { 1384 tree res = cache[n]; 1385 if (!res) 1386 { 1387 tree prev = get_fn_chain (arg, n - 1, gsi, fn, loc, cache); 1388 res = build_and_insert_call (gsi, loc, fn, prev); 1389 cache[n] = res; 1390 } 1391 1392 return res; 1393 } 1394 1395 /* Print to STREAM the repeated application of function FNAME to ARG 1396 N times. So, for FNAME = "foo", ARG = "x", N = 2 it would print: 1397 "foo (foo (x))". */ 1398 1399 static void 1400 print_nested_fn (FILE* stream, const char *fname, const char* arg, 1401 unsigned int n) 1402 { 1403 if (n == 0) 1404 fprintf (stream, "%s", arg); 1405 else 1406 { 1407 fprintf (stream, "%s (", fname); 1408 print_nested_fn (stream, fname, arg, n - 1); 1409 fprintf (stream, ")"); 1410 } 1411 } 1412 1413 /* Print to STREAM the fractional sequence of sqrt chains 1414 applied to ARG, described by INFO. Used for the dump file. */ 1415 1416 static void 1417 dump_fractional_sqrt_sequence (FILE *stream, const char *arg, 1418 struct pow_synth_sqrt_info *info) 1419 { 1420 for (unsigned int i = 0; i < info->deepest; i++) 1421 { 1422 bool is_set = info->factors[i]; 1423 if (is_set) 1424 { 1425 print_nested_fn (stream, "sqrt", arg, i + 1); 1426 if (i != info->deepest - 1) 1427 fprintf (stream, " * "); 1428 } 1429 } 1430 } 1431 1432 /* Print to STREAM a representation of raising ARG to an integer 1433 power N. Used for the dump file. */ 1434 1435 static void 1436 dump_integer_part (FILE *stream, const char* arg, HOST_WIDE_INT n) 1437 { 1438 if (n > 1) 1439 fprintf (stream, "powi (%s, " HOST_WIDE_INT_PRINT_DEC ")", arg, n); 1440 else if (n == 1) 1441 fprintf (stream, "%s", arg); 1442 } 1443 1444 /* Attempt to synthesize a POW[F] (ARG0, ARG1) call using chains of 1445 square roots. Place at GSI and LOC. Limit the maximum depth 1446 of the sqrt chains to MAX_DEPTH. Return the tree holding the 1447 result of the expanded sequence or NULL_TREE if the expansion failed. 1448 1449 This routine assumes that ARG1 is a real number with a fractional part 1450 (the integer exponent case will have been handled earlier in 1451 gimple_expand_builtin_pow). 1452 1453 For ARG1 > 0.0: 1454 * For ARG1 composed of a whole part WHOLE_PART and a fractional part 1455 FRAC_PART i.e. WHOLE_PART == floor (ARG1) and 1456 FRAC_PART == ARG1 - WHOLE_PART: 1457 Produce POWI (ARG0, WHOLE_PART) * POW (ARG0, FRAC_PART) where 1458 POW (ARG0, FRAC_PART) is expanded as a product of square root chains 1459 if it can be expressed as such, that is if FRAC_PART satisfies: 1460 FRAC_PART == <SUM from i = 1 until MAX_DEPTH> (a[i] * (0.5**i)) 1461 where integer a[i] is either 0 or 1. 1462 1463 Example: 1464 POW (x, 3.625) == POWI (x, 3) * POW (x, 0.625) 1465 --> POWI (x, 3) * SQRT (x) * SQRT (SQRT (SQRT (x))) 1466 1467 For ARG1 < 0.0 there are two approaches: 1468 * (A) Expand to 1.0 / POW (ARG0, -ARG1) where POW (ARG0, -ARG1) 1469 is calculated as above. 1470 1471 Example: 1472 POW (x, -5.625) == 1.0 / POW (x, 5.625) 1473 --> 1.0 / (POWI (x, 5) * SQRT (x) * SQRT (SQRT (SQRT (x)))) 1474 1475 * (B) : WHOLE_PART := - ceil (abs (ARG1)) 1476 FRAC_PART := ARG1 - WHOLE_PART 1477 and expand to POW (x, FRAC_PART) / POWI (x, WHOLE_PART). 1478 Example: 1479 POW (x, -5.875) == POW (x, 0.125) / POWI (X, 6) 1480 --> SQRT (SQRT (SQRT (x))) / (POWI (x, 6)) 1481 1482 For ARG1 < 0.0 we choose between (A) and (B) depending on 1483 how many multiplications we'd have to do. 1484 So, for the example in (B): POW (x, -5.875), if we were to 1485 follow algorithm (A) we would produce: 1486 1.0 / POWI (X, 5) * SQRT (X) * SQRT (SQRT (X)) * SQRT (SQRT (SQRT (X))) 1487 which contains more multiplications than approach (B). 1488 1489 Hopefully, this approach will eliminate potentially expensive POW library 1490 calls when unsafe floating point math is enabled and allow the compiler to 1491 further optimise the multiplies, square roots and divides produced by this 1492 function. */ 1493 1494 static tree 1495 expand_pow_as_sqrts (gimple_stmt_iterator *gsi, location_t loc, 1496 tree arg0, tree arg1, HOST_WIDE_INT max_depth) 1497 { 1498 tree type = TREE_TYPE (arg0); 1499 machine_mode mode = TYPE_MODE (type); 1500 tree sqrtfn = mathfn_built_in (type, BUILT_IN_SQRT); 1501 bool one_over = true; 1502 1503 if (!sqrtfn) 1504 return NULL_TREE; 1505 1506 if (TREE_CODE (arg1) != REAL_CST) 1507 return NULL_TREE; 1508 1509 REAL_VALUE_TYPE exp_init = TREE_REAL_CST (arg1); 1510 1511 gcc_assert (max_depth > 0); 1512 tree *cache = XALLOCAVEC (tree, max_depth + 1); 1513 1514 struct pow_synth_sqrt_info synth_info; 1515 synth_info.factors = XALLOCAVEC (bool, max_depth + 1); 1516 synth_info.deepest = 0; 1517 synth_info.num_mults = 0; 1518 1519 bool neg_exp = REAL_VALUE_NEGATIVE (exp_init); 1520 REAL_VALUE_TYPE exp = real_value_abs (&exp_init); 1521 1522 /* The whole and fractional parts of exp. */ 1523 REAL_VALUE_TYPE whole_part; 1524 REAL_VALUE_TYPE frac_part; 1525 1526 real_floor (&whole_part, mode, &exp); 1527 real_arithmetic (&frac_part, MINUS_EXPR, &exp, &whole_part); 1528 1529 1530 REAL_VALUE_TYPE ceil_whole = dconst0; 1531 REAL_VALUE_TYPE ceil_fract = dconst0; 1532 1533 if (neg_exp) 1534 { 1535 real_ceil (&ceil_whole, mode, &exp); 1536 real_arithmetic (&ceil_fract, MINUS_EXPR, &ceil_whole, &exp); 1537 } 1538 1539 if (!representable_as_half_series_p (frac_part, max_depth, &synth_info)) 1540 return NULL_TREE; 1541 1542 /* Check whether it's more profitable to not use 1.0 / ... */ 1543 if (neg_exp) 1544 { 1545 struct pow_synth_sqrt_info alt_synth_info; 1546 alt_synth_info.factors = XALLOCAVEC (bool, max_depth + 1); 1547 alt_synth_info.deepest = 0; 1548 alt_synth_info.num_mults = 0; 1549 1550 if (representable_as_half_series_p (ceil_fract, max_depth, 1551 &alt_synth_info) 1552 && alt_synth_info.deepest <= synth_info.deepest 1553 && alt_synth_info.num_mults < synth_info.num_mults) 1554 { 1555 whole_part = ceil_whole; 1556 frac_part = ceil_fract; 1557 synth_info.deepest = alt_synth_info.deepest; 1558 synth_info.num_mults = alt_synth_info.num_mults; 1559 memcpy (synth_info.factors, alt_synth_info.factors, 1560 (max_depth + 1) * sizeof (bool)); 1561 one_over = false; 1562 } 1563 } 1564 1565 HOST_WIDE_INT n = real_to_integer (&whole_part); 1566 REAL_VALUE_TYPE cint; 1567 real_from_integer (&cint, VOIDmode, n, SIGNED); 1568 1569 if (!real_identical (&whole_part, &cint)) 1570 return NULL_TREE; 1571 1572 if (powi_cost (n) + synth_info.num_mults > POWI_MAX_MULTS) 1573 return NULL_TREE; 1574 1575 memset (cache, 0, (max_depth + 1) * sizeof (tree)); 1576 1577 tree integer_res = n == 0 ? build_real (type, dconst1) : arg0; 1578 1579 /* Calculate the integer part of the exponent. */ 1580 if (n > 1) 1581 { 1582 integer_res = gimple_expand_builtin_powi (gsi, loc, arg0, n); 1583 if (!integer_res) 1584 return NULL_TREE; 1585 } 1586 1587 if (dump_file) 1588 { 1589 char string[64]; 1590 1591 real_to_decimal (string, &exp_init, sizeof (string), 0, 1); 1592 fprintf (dump_file, "synthesizing pow (x, %s) as:\n", string); 1593 1594 if (neg_exp) 1595 { 1596 if (one_over) 1597 { 1598 fprintf (dump_file, "1.0 / ("); 1599 dump_integer_part (dump_file, "x", n); 1600 if (n > 0) 1601 fprintf (dump_file, " * "); 1602 dump_fractional_sqrt_sequence (dump_file, "x", &synth_info); 1603 fprintf (dump_file, ")"); 1604 } 1605 else 1606 { 1607 dump_fractional_sqrt_sequence (dump_file, "x", &synth_info); 1608 fprintf (dump_file, " / ("); 1609 dump_integer_part (dump_file, "x", n); 1610 fprintf (dump_file, ")"); 1611 } 1612 } 1613 else 1614 { 1615 dump_fractional_sqrt_sequence (dump_file, "x", &synth_info); 1616 if (n > 0) 1617 fprintf (dump_file, " * "); 1618 dump_integer_part (dump_file, "x", n); 1619 } 1620 1621 fprintf (dump_file, "\ndeepest sqrt chain: %d\n", synth_info.deepest); 1622 } 1623 1624 1625 tree fract_res = NULL_TREE; 1626 cache[0] = arg0; 1627 1628 /* Calculate the fractional part of the exponent. */ 1629 for (unsigned i = 0; i < synth_info.deepest; i++) 1630 { 1631 if (synth_info.factors[i]) 1632 { 1633 tree sqrt_chain = get_fn_chain (arg0, i + 1, gsi, sqrtfn, loc, cache); 1634 1635 if (!fract_res) 1636 fract_res = sqrt_chain; 1637 1638 else 1639 fract_res = build_and_insert_binop (gsi, loc, "powroot", MULT_EXPR, 1640 fract_res, sqrt_chain); 1641 } 1642 } 1643 1644 tree res = NULL_TREE; 1645 1646 if (neg_exp) 1647 { 1648 if (one_over) 1649 { 1650 if (n > 0) 1651 res = build_and_insert_binop (gsi, loc, "powroot", MULT_EXPR, 1652 fract_res, integer_res); 1653 else 1654 res = fract_res; 1655 1656 res = build_and_insert_binop (gsi, loc, "powrootrecip", RDIV_EXPR, 1657 build_real (type, dconst1), res); 1658 } 1659 else 1660 { 1661 res = build_and_insert_binop (gsi, loc, "powroot", RDIV_EXPR, 1662 fract_res, integer_res); 1663 } 1664 } 1665 else 1666 res = build_and_insert_binop (gsi, loc, "powroot", MULT_EXPR, 1667 fract_res, integer_res); 1668 return res; 1669 } 1670 1671 /* ARG0 and ARG1 are the two arguments to a pow builtin call in GSI 1672 with location info LOC. If possible, create an equivalent and 1673 less expensive sequence of statements prior to GSI, and return an 1674 expession holding the result. */ 1675 1676 static tree 1677 gimple_expand_builtin_pow (gimple_stmt_iterator *gsi, location_t loc, 1678 tree arg0, tree arg1) 1679 { 1680 REAL_VALUE_TYPE c, cint, dconst1_3, dconst1_4, dconst1_6; 1681 REAL_VALUE_TYPE c2, dconst3; 1682 HOST_WIDE_INT n; 1683 tree type, sqrtfn, cbrtfn, sqrt_arg0, result, cbrt_x, powi_cbrt_x; 1684 machine_mode mode; 1685 bool speed_p = optimize_bb_for_speed_p (gsi_bb (*gsi)); 1686 bool hw_sqrt_exists, c_is_int, c2_is_int; 1687 1688 dconst1_4 = dconst1; 1689 SET_REAL_EXP (&dconst1_4, REAL_EXP (&dconst1_4) - 2); 1690 1691 /* If the exponent isn't a constant, there's nothing of interest 1692 to be done. */ 1693 if (TREE_CODE (arg1) != REAL_CST) 1694 return NULL_TREE; 1695 1696 /* Don't perform the operation if flag_signaling_nans is on 1697 and the operand is a signaling NaN. */ 1698 if (HONOR_SNANS (TYPE_MODE (TREE_TYPE (arg1))) 1699 && ((TREE_CODE (arg0) == REAL_CST 1700 && REAL_VALUE_ISSIGNALING_NAN (TREE_REAL_CST (arg0))) 1701 || REAL_VALUE_ISSIGNALING_NAN (TREE_REAL_CST (arg1)))) 1702 return NULL_TREE; 1703 1704 /* If the exponent is equivalent to an integer, expand to an optimal 1705 multiplication sequence when profitable. */ 1706 c = TREE_REAL_CST (arg1); 1707 n = real_to_integer (&c); 1708 real_from_integer (&cint, VOIDmode, n, SIGNED); 1709 c_is_int = real_identical (&c, &cint); 1710 1711 if (c_is_int 1712 && ((n >= -1 && n <= 2) 1713 || (flag_unsafe_math_optimizations 1714 && speed_p 1715 && powi_cost (n) <= POWI_MAX_MULTS))) 1716 return gimple_expand_builtin_powi (gsi, loc, arg0, n); 1717 1718 /* Attempt various optimizations using sqrt and cbrt. */ 1719 type = TREE_TYPE (arg0); 1720 mode = TYPE_MODE (type); 1721 sqrtfn = mathfn_built_in (type, BUILT_IN_SQRT); 1722 1723 /* Optimize pow(x,0.5) = sqrt(x). This replacement is always safe 1724 unless signed zeros must be maintained. pow(-0,0.5) = +0, while 1725 sqrt(-0) = -0. */ 1726 if (sqrtfn 1727 && real_equal (&c, &dconsthalf) 1728 && !HONOR_SIGNED_ZEROS (mode)) 1729 return build_and_insert_call (gsi, loc, sqrtfn, arg0); 1730 1731 hw_sqrt_exists = optab_handler (sqrt_optab, mode) != CODE_FOR_nothing; 1732 1733 /* Optimize pow(x,1./3.) = cbrt(x). This requires unsafe math 1734 optimizations since 1./3. is not exactly representable. If x 1735 is negative and finite, the correct value of pow(x,1./3.) is 1736 a NaN with the "invalid" exception raised, because the value 1737 of 1./3. actually has an even denominator. The correct value 1738 of cbrt(x) is a negative real value. */ 1739 cbrtfn = mathfn_built_in (type, BUILT_IN_CBRT); 1740 dconst1_3 = real_value_truncate (mode, dconst_third ()); 1741 1742 if (flag_unsafe_math_optimizations 1743 && cbrtfn 1744 && (!HONOR_NANS (mode) || tree_expr_nonnegative_p (arg0)) 1745 && real_equal (&c, &dconst1_3)) 1746 return build_and_insert_call (gsi, loc, cbrtfn, arg0); 1747 1748 /* Optimize pow(x,1./6.) = cbrt(sqrt(x)). Don't do this optimization 1749 if we don't have a hardware sqrt insn. */ 1750 dconst1_6 = dconst1_3; 1751 SET_REAL_EXP (&dconst1_6, REAL_EXP (&dconst1_6) - 1); 1752 1753 if (flag_unsafe_math_optimizations 1754 && sqrtfn 1755 && cbrtfn 1756 && (!HONOR_NANS (mode) || tree_expr_nonnegative_p (arg0)) 1757 && speed_p 1758 && hw_sqrt_exists 1759 && real_equal (&c, &dconst1_6)) 1760 { 1761 /* sqrt(x) */ 1762 sqrt_arg0 = build_and_insert_call (gsi, loc, sqrtfn, arg0); 1763 1764 /* cbrt(sqrt(x)) */ 1765 return build_and_insert_call (gsi, loc, cbrtfn, sqrt_arg0); 1766 } 1767 1768 1769 /* Attempt to expand the POW as a product of square root chains. 1770 Expand the 0.25 case even when otpimising for size. */ 1771 if (flag_unsafe_math_optimizations 1772 && sqrtfn 1773 && hw_sqrt_exists 1774 && (speed_p || real_equal (&c, &dconst1_4)) 1775 && !HONOR_SIGNED_ZEROS (mode)) 1776 { 1777 unsigned int max_depth = speed_p 1778 ? PARAM_VALUE (PARAM_MAX_POW_SQRT_DEPTH) 1779 : 2; 1780 1781 tree expand_with_sqrts 1782 = expand_pow_as_sqrts (gsi, loc, arg0, arg1, max_depth); 1783 1784 if (expand_with_sqrts) 1785 return expand_with_sqrts; 1786 } 1787 1788 real_arithmetic (&c2, MULT_EXPR, &c, &dconst2); 1789 n = real_to_integer (&c2); 1790 real_from_integer (&cint, VOIDmode, n, SIGNED); 1791 c2_is_int = real_identical (&c2, &cint); 1792 1793 /* Optimize pow(x,c), where 3c = n for some nonzero integer n, into 1794 1795 powi(x, n/3) * powi(cbrt(x), n%3), n > 0; 1796 1.0 / (powi(x, abs(n)/3) * powi(cbrt(x), abs(n)%3)), n < 0. 1797 1798 Do not calculate the first factor when n/3 = 0. As cbrt(x) is 1799 different from pow(x, 1./3.) due to rounding and behavior with 1800 negative x, we need to constrain this transformation to unsafe 1801 math and positive x or finite math. */ 1802 real_from_integer (&dconst3, VOIDmode, 3, SIGNED); 1803 real_arithmetic (&c2, MULT_EXPR, &c, &dconst3); 1804 real_round (&c2, mode, &c2); 1805 n = real_to_integer (&c2); 1806 real_from_integer (&cint, VOIDmode, n, SIGNED); 1807 real_arithmetic (&c2, RDIV_EXPR, &cint, &dconst3); 1808 real_convert (&c2, mode, &c2); 1809 1810 if (flag_unsafe_math_optimizations 1811 && cbrtfn 1812 && (!HONOR_NANS (mode) || tree_expr_nonnegative_p (arg0)) 1813 && real_identical (&c2, &c) 1814 && !c2_is_int 1815 && optimize_function_for_speed_p (cfun) 1816 && powi_cost (n / 3) <= POWI_MAX_MULTS) 1817 { 1818 tree powi_x_ndiv3 = NULL_TREE; 1819 1820 /* Attempt to fold powi(arg0, abs(n/3)) into multiplies. If not 1821 possible or profitable, give up. Skip the degenerate case when 1822 abs(n) < 3, where the result is always 1. */ 1823 if (absu_hwi (n) >= 3) 1824 { 1825 powi_x_ndiv3 = gimple_expand_builtin_powi (gsi, loc, arg0, 1826 abs_hwi (n / 3)); 1827 if (!powi_x_ndiv3) 1828 return NULL_TREE; 1829 } 1830 1831 /* Calculate powi(cbrt(x), n%3). Don't use gimple_expand_builtin_powi 1832 as that creates an unnecessary variable. Instead, just produce 1833 either cbrt(x) or cbrt(x) * cbrt(x). */ 1834 cbrt_x = build_and_insert_call (gsi, loc, cbrtfn, arg0); 1835 1836 if (absu_hwi (n) % 3 == 1) 1837 powi_cbrt_x = cbrt_x; 1838 else 1839 powi_cbrt_x = build_and_insert_binop (gsi, loc, "powroot", MULT_EXPR, 1840 cbrt_x, cbrt_x); 1841 1842 /* Multiply the two subexpressions, unless powi(x,abs(n)/3) = 1. */ 1843 if (absu_hwi (n) < 3) 1844 result = powi_cbrt_x; 1845 else 1846 result = build_and_insert_binop (gsi, loc, "powroot", MULT_EXPR, 1847 powi_x_ndiv3, powi_cbrt_x); 1848 1849 /* If n is negative, reciprocate the result. */ 1850 if (n < 0) 1851 result = build_and_insert_binop (gsi, loc, "powroot", RDIV_EXPR, 1852 build_real (type, dconst1), result); 1853 1854 return result; 1855 } 1856 1857 /* No optimizations succeeded. */ 1858 return NULL_TREE; 1859 } 1860 1861 /* ARG is the argument to a cabs builtin call in GSI with location info 1862 LOC. Create a sequence of statements prior to GSI that calculates 1863 sqrt(R*R + I*I), where R and I are the real and imaginary components 1864 of ARG, respectively. Return an expression holding the result. */ 1865 1866 static tree 1867 gimple_expand_builtin_cabs (gimple_stmt_iterator *gsi, location_t loc, tree arg) 1868 { 1869 tree real_part, imag_part, addend1, addend2, sum, result; 1870 tree type = TREE_TYPE (TREE_TYPE (arg)); 1871 tree sqrtfn = mathfn_built_in (type, BUILT_IN_SQRT); 1872 machine_mode mode = TYPE_MODE (type); 1873 1874 if (!flag_unsafe_math_optimizations 1875 || !optimize_bb_for_speed_p (gimple_bb (gsi_stmt (*gsi))) 1876 || !sqrtfn 1877 || optab_handler (sqrt_optab, mode) == CODE_FOR_nothing) 1878 return NULL_TREE; 1879 1880 real_part = build_and_insert_ref (gsi, loc, type, "cabs", 1881 REALPART_EXPR, arg); 1882 addend1 = build_and_insert_binop (gsi, loc, "cabs", MULT_EXPR, 1883 real_part, real_part); 1884 imag_part = build_and_insert_ref (gsi, loc, type, "cabs", 1885 IMAGPART_EXPR, arg); 1886 addend2 = build_and_insert_binop (gsi, loc, "cabs", MULT_EXPR, 1887 imag_part, imag_part); 1888 sum = build_and_insert_binop (gsi, loc, "cabs", PLUS_EXPR, addend1, addend2); 1889 result = build_and_insert_call (gsi, loc, sqrtfn, sum); 1890 1891 return result; 1892 } 1893 1894 /* Go through all calls to sin, cos and cexpi and call execute_cse_sincos_1 1895 on the SSA_NAME argument of each of them. Also expand powi(x,n) into 1896 an optimal number of multiplies, when n is a constant. */ 1897 1898 namespace { 1899 1900 const pass_data pass_data_cse_sincos = 1901 { 1902 GIMPLE_PASS, /* type */ 1903 "sincos", /* name */ 1904 OPTGROUP_NONE, /* optinfo_flags */ 1905 TV_TREE_SINCOS, /* tv_id */ 1906 PROP_ssa, /* properties_required */ 1907 PROP_gimple_opt_math, /* properties_provided */ 1908 0, /* properties_destroyed */ 1909 0, /* todo_flags_start */ 1910 TODO_update_ssa, /* todo_flags_finish */ 1911 }; 1912 1913 class pass_cse_sincos : public gimple_opt_pass 1914 { 1915 public: 1916 pass_cse_sincos (gcc::context *ctxt) 1917 : gimple_opt_pass (pass_data_cse_sincos, ctxt) 1918 {} 1919 1920 /* opt_pass methods: */ 1921 virtual bool gate (function *) 1922 { 1923 /* We no longer require either sincos or cexp, since powi expansion 1924 piggybacks on this pass. */ 1925 return optimize; 1926 } 1927 1928 virtual unsigned int execute (function *); 1929 1930 }; // class pass_cse_sincos 1931 1932 unsigned int 1933 pass_cse_sincos::execute (function *fun) 1934 { 1935 basic_block bb; 1936 bool cfg_changed = false; 1937 1938 calculate_dominance_info (CDI_DOMINATORS); 1939 memset (&sincos_stats, 0, sizeof (sincos_stats)); 1940 1941 FOR_EACH_BB_FN (bb, fun) 1942 { 1943 gimple_stmt_iterator gsi; 1944 bool cleanup_eh = false; 1945 1946 for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 1947 { 1948 gimple *stmt = gsi_stmt (gsi); 1949 1950 /* Only the last stmt in a bb could throw, no need to call 1951 gimple_purge_dead_eh_edges if we change something in the middle 1952 of a basic block. */ 1953 cleanup_eh = false; 1954 1955 if (is_gimple_call (stmt) 1956 && gimple_call_lhs (stmt)) 1957 { 1958 tree arg, arg0, arg1, result; 1959 HOST_WIDE_INT n; 1960 location_t loc; 1961 1962 switch (gimple_call_combined_fn (stmt)) 1963 { 1964 CASE_CFN_COS: 1965 CASE_CFN_SIN: 1966 CASE_CFN_CEXPI: 1967 /* Make sure we have either sincos or cexp. */ 1968 if (!targetm.libc_has_function (function_c99_math_complex) 1969 && !targetm.libc_has_function (function_sincos)) 1970 break; 1971 1972 arg = gimple_call_arg (stmt, 0); 1973 if (TREE_CODE (arg) == SSA_NAME) 1974 cfg_changed |= execute_cse_sincos_1 (arg); 1975 break; 1976 1977 CASE_CFN_POW: 1978 arg0 = gimple_call_arg (stmt, 0); 1979 arg1 = gimple_call_arg (stmt, 1); 1980 1981 loc = gimple_location (stmt); 1982 result = gimple_expand_builtin_pow (&gsi, loc, arg0, arg1); 1983 1984 if (result) 1985 { 1986 tree lhs = gimple_get_lhs (stmt); 1987 gassign *new_stmt = gimple_build_assign (lhs, result); 1988 gimple_set_location (new_stmt, loc); 1989 unlink_stmt_vdef (stmt); 1990 gsi_replace (&gsi, new_stmt, true); 1991 cleanup_eh = true; 1992 if (gimple_vdef (stmt)) 1993 release_ssa_name (gimple_vdef (stmt)); 1994 } 1995 break; 1996 1997 CASE_CFN_POWI: 1998 arg0 = gimple_call_arg (stmt, 0); 1999 arg1 = gimple_call_arg (stmt, 1); 2000 loc = gimple_location (stmt); 2001 2002 if (real_minus_onep (arg0)) 2003 { 2004 tree t0, t1, cond, one, minus_one; 2005 gassign *stmt; 2006 2007 t0 = TREE_TYPE (arg0); 2008 t1 = TREE_TYPE (arg1); 2009 one = build_real (t0, dconst1); 2010 minus_one = build_real (t0, dconstm1); 2011 2012 cond = make_temp_ssa_name (t1, NULL, "powi_cond"); 2013 stmt = gimple_build_assign (cond, BIT_AND_EXPR, 2014 arg1, build_int_cst (t1, 1)); 2015 gimple_set_location (stmt, loc); 2016 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT); 2017 2018 result = make_temp_ssa_name (t0, NULL, "powi"); 2019 stmt = gimple_build_assign (result, COND_EXPR, cond, 2020 minus_one, one); 2021 gimple_set_location (stmt, loc); 2022 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT); 2023 } 2024 else 2025 { 2026 if (!tree_fits_shwi_p (arg1)) 2027 break; 2028 2029 n = tree_to_shwi (arg1); 2030 result = gimple_expand_builtin_powi (&gsi, loc, arg0, n); 2031 } 2032 2033 if (result) 2034 { 2035 tree lhs = gimple_get_lhs (stmt); 2036 gassign *new_stmt = gimple_build_assign (lhs, result); 2037 gimple_set_location (new_stmt, loc); 2038 unlink_stmt_vdef (stmt); 2039 gsi_replace (&gsi, new_stmt, true); 2040 cleanup_eh = true; 2041 if (gimple_vdef (stmt)) 2042 release_ssa_name (gimple_vdef (stmt)); 2043 } 2044 break; 2045 2046 CASE_CFN_CABS: 2047 arg0 = gimple_call_arg (stmt, 0); 2048 loc = gimple_location (stmt); 2049 result = gimple_expand_builtin_cabs (&gsi, loc, arg0); 2050 2051 if (result) 2052 { 2053 tree lhs = gimple_get_lhs (stmt); 2054 gassign *new_stmt = gimple_build_assign (lhs, result); 2055 gimple_set_location (new_stmt, loc); 2056 unlink_stmt_vdef (stmt); 2057 gsi_replace (&gsi, new_stmt, true); 2058 cleanup_eh = true; 2059 if (gimple_vdef (stmt)) 2060 release_ssa_name (gimple_vdef (stmt)); 2061 } 2062 break; 2063 2064 default:; 2065 } 2066 } 2067 } 2068 if (cleanup_eh) 2069 cfg_changed |= gimple_purge_dead_eh_edges (bb); 2070 } 2071 2072 statistics_counter_event (fun, "sincos statements inserted", 2073 sincos_stats.inserted); 2074 2075 return cfg_changed ? TODO_cleanup_cfg : 0; 2076 } 2077 2078 } // anon namespace 2079 2080 gimple_opt_pass * 2081 make_pass_cse_sincos (gcc::context *ctxt) 2082 { 2083 return new pass_cse_sincos (ctxt); 2084 } 2085 2086 /* Return true if stmt is a type conversion operation that can be stripped 2087 when used in a widening multiply operation. */ 2088 static bool 2089 widening_mult_conversion_strippable_p (tree result_type, gimple *stmt) 2090 { 2091 enum tree_code rhs_code = gimple_assign_rhs_code (stmt); 2092 2093 if (TREE_CODE (result_type) == INTEGER_TYPE) 2094 { 2095 tree op_type; 2096 tree inner_op_type; 2097 2098 if (!CONVERT_EXPR_CODE_P (rhs_code)) 2099 return false; 2100 2101 op_type = TREE_TYPE (gimple_assign_lhs (stmt)); 2102 2103 /* If the type of OP has the same precision as the result, then 2104 we can strip this conversion. The multiply operation will be 2105 selected to create the correct extension as a by-product. */ 2106 if (TYPE_PRECISION (result_type) == TYPE_PRECISION (op_type)) 2107 return true; 2108 2109 /* We can also strip a conversion if it preserves the signed-ness of 2110 the operation and doesn't narrow the range. */ 2111 inner_op_type = TREE_TYPE (gimple_assign_rhs1 (stmt)); 2112 2113 /* If the inner-most type is unsigned, then we can strip any 2114 intermediate widening operation. If it's signed, then the 2115 intermediate widening operation must also be signed. */ 2116 if ((TYPE_UNSIGNED (inner_op_type) 2117 || TYPE_UNSIGNED (op_type) == TYPE_UNSIGNED (inner_op_type)) 2118 && TYPE_PRECISION (op_type) > TYPE_PRECISION (inner_op_type)) 2119 return true; 2120 2121 return false; 2122 } 2123 2124 return rhs_code == FIXED_CONVERT_EXPR; 2125 } 2126 2127 /* Return true if RHS is a suitable operand for a widening multiplication, 2128 assuming a target type of TYPE. 2129 There are two cases: 2130 2131 - RHS makes some value at least twice as wide. Store that value 2132 in *NEW_RHS_OUT if so, and store its type in *TYPE_OUT. 2133 2134 - RHS is an integer constant. Store that value in *NEW_RHS_OUT if so, 2135 but leave *TYPE_OUT untouched. */ 2136 2137 static bool 2138 is_widening_mult_rhs_p (tree type, tree rhs, tree *type_out, 2139 tree *new_rhs_out) 2140 { 2141 gimple *stmt; 2142 tree type1, rhs1; 2143 2144 if (TREE_CODE (rhs) == SSA_NAME) 2145 { 2146 stmt = SSA_NAME_DEF_STMT (rhs); 2147 if (is_gimple_assign (stmt)) 2148 { 2149 if (! widening_mult_conversion_strippable_p (type, stmt)) 2150 rhs1 = rhs; 2151 else 2152 { 2153 rhs1 = gimple_assign_rhs1 (stmt); 2154 2155 if (TREE_CODE (rhs1) == INTEGER_CST) 2156 { 2157 *new_rhs_out = rhs1; 2158 *type_out = NULL; 2159 return true; 2160 } 2161 } 2162 } 2163 else 2164 rhs1 = rhs; 2165 2166 type1 = TREE_TYPE (rhs1); 2167 2168 if (TREE_CODE (type1) != TREE_CODE (type) 2169 || TYPE_PRECISION (type1) * 2 > TYPE_PRECISION (type)) 2170 return false; 2171 2172 *new_rhs_out = rhs1; 2173 *type_out = type1; 2174 return true; 2175 } 2176 2177 if (TREE_CODE (rhs) == INTEGER_CST) 2178 { 2179 *new_rhs_out = rhs; 2180 *type_out = NULL; 2181 return true; 2182 } 2183 2184 return false; 2185 } 2186 2187 /* Return true if STMT performs a widening multiplication, assuming the 2188 output type is TYPE. If so, store the unwidened types of the operands 2189 in *TYPE1_OUT and *TYPE2_OUT respectively. Also fill *RHS1_OUT and 2190 *RHS2_OUT such that converting those operands to types *TYPE1_OUT 2191 and *TYPE2_OUT would give the operands of the multiplication. */ 2192 2193 static bool 2194 is_widening_mult_p (gimple *stmt, 2195 tree *type1_out, tree *rhs1_out, 2196 tree *type2_out, tree *rhs2_out) 2197 { 2198 tree type = TREE_TYPE (gimple_assign_lhs (stmt)); 2199 2200 if (TREE_CODE (type) == INTEGER_TYPE) 2201 { 2202 if (TYPE_OVERFLOW_TRAPS (type)) 2203 return false; 2204 } 2205 else if (TREE_CODE (type) != FIXED_POINT_TYPE) 2206 return false; 2207 2208 if (!is_widening_mult_rhs_p (type, gimple_assign_rhs1 (stmt), type1_out, 2209 rhs1_out)) 2210 return false; 2211 2212 if (!is_widening_mult_rhs_p (type, gimple_assign_rhs2 (stmt), type2_out, 2213 rhs2_out)) 2214 return false; 2215 2216 if (*type1_out == NULL) 2217 { 2218 if (*type2_out == NULL || !int_fits_type_p (*rhs1_out, *type2_out)) 2219 return false; 2220 *type1_out = *type2_out; 2221 } 2222 2223 if (*type2_out == NULL) 2224 { 2225 if (!int_fits_type_p (*rhs2_out, *type1_out)) 2226 return false; 2227 *type2_out = *type1_out; 2228 } 2229 2230 /* Ensure that the larger of the two operands comes first. */ 2231 if (TYPE_PRECISION (*type1_out) < TYPE_PRECISION (*type2_out)) 2232 { 2233 std::swap (*type1_out, *type2_out); 2234 std::swap (*rhs1_out, *rhs2_out); 2235 } 2236 2237 return true; 2238 } 2239 2240 /* Check to see if the CALL statement is an invocation of copysign 2241 with 1. being the first argument. */ 2242 static bool 2243 is_copysign_call_with_1 (gimple *call) 2244 { 2245 gcall *c = dyn_cast <gcall *> (call); 2246 if (! c) 2247 return false; 2248 2249 enum combined_fn code = gimple_call_combined_fn (c); 2250 2251 if (code == CFN_LAST) 2252 return false; 2253 2254 if (builtin_fn_p (code)) 2255 { 2256 switch (as_builtin_fn (code)) 2257 { 2258 CASE_FLT_FN (BUILT_IN_COPYSIGN): 2259 CASE_FLT_FN_FLOATN_NX (BUILT_IN_COPYSIGN): 2260 return real_onep (gimple_call_arg (c, 0)); 2261 default: 2262 return false; 2263 } 2264 } 2265 2266 if (internal_fn_p (code)) 2267 { 2268 switch (as_internal_fn (code)) 2269 { 2270 case IFN_COPYSIGN: 2271 return real_onep (gimple_call_arg (c, 0)); 2272 default: 2273 return false; 2274 } 2275 } 2276 2277 return false; 2278 } 2279 2280 /* Try to expand the pattern x * copysign (1, y) into xorsign (x, y). 2281 This only happens when the the xorsign optab is defined, if the 2282 pattern is not a xorsign pattern or if expansion fails FALSE is 2283 returned, otherwise TRUE is returned. */ 2284 static bool 2285 convert_expand_mult_copysign (gimple *stmt, gimple_stmt_iterator *gsi) 2286 { 2287 tree treeop0, treeop1, lhs, type; 2288 location_t loc = gimple_location (stmt); 2289 lhs = gimple_assign_lhs (stmt); 2290 treeop0 = gimple_assign_rhs1 (stmt); 2291 treeop1 = gimple_assign_rhs2 (stmt); 2292 type = TREE_TYPE (lhs); 2293 machine_mode mode = TYPE_MODE (type); 2294 2295 if (HONOR_SNANS (type)) 2296 return false; 2297 2298 if (TREE_CODE (treeop0) == SSA_NAME && TREE_CODE (treeop1) == SSA_NAME) 2299 { 2300 gimple *call0 = SSA_NAME_DEF_STMT (treeop0); 2301 if (!has_single_use (treeop0) || !is_copysign_call_with_1 (call0)) 2302 { 2303 call0 = SSA_NAME_DEF_STMT (treeop1); 2304 if (!has_single_use (treeop1) || !is_copysign_call_with_1 (call0)) 2305 return false; 2306 2307 treeop1 = treeop0; 2308 } 2309 if (optab_handler (xorsign_optab, mode) == CODE_FOR_nothing) 2310 return false; 2311 2312 gcall *c = as_a<gcall*> (call0); 2313 treeop0 = gimple_call_arg (c, 1); 2314 2315 gcall *call_stmt 2316 = gimple_build_call_internal (IFN_XORSIGN, 2, treeop1, treeop0); 2317 gimple_set_lhs (call_stmt, lhs); 2318 gimple_set_location (call_stmt, loc); 2319 gsi_replace (gsi, call_stmt, true); 2320 return true; 2321 } 2322 2323 return false; 2324 } 2325 2326 /* Process a single gimple statement STMT, which has a MULT_EXPR as 2327 its rhs, and try to convert it into a WIDEN_MULT_EXPR. The return 2328 value is true iff we converted the statement. */ 2329 2330 static bool 2331 convert_mult_to_widen (gimple *stmt, gimple_stmt_iterator *gsi) 2332 { 2333 tree lhs, rhs1, rhs2, type, type1, type2; 2334 enum insn_code handler; 2335 scalar_int_mode to_mode, from_mode, actual_mode; 2336 optab op; 2337 int actual_precision; 2338 location_t loc = gimple_location (stmt); 2339 bool from_unsigned1, from_unsigned2; 2340 2341 lhs = gimple_assign_lhs (stmt); 2342 type = TREE_TYPE (lhs); 2343 if (TREE_CODE (type) != INTEGER_TYPE) 2344 return false; 2345 2346 if (!is_widening_mult_p (stmt, &type1, &rhs1, &type2, &rhs2)) 2347 return false; 2348 2349 to_mode = SCALAR_INT_TYPE_MODE (type); 2350 from_mode = SCALAR_INT_TYPE_MODE (type1); 2351 if (to_mode == from_mode) 2352 return false; 2353 2354 from_unsigned1 = TYPE_UNSIGNED (type1); 2355 from_unsigned2 = TYPE_UNSIGNED (type2); 2356 2357 if (from_unsigned1 && from_unsigned2) 2358 op = umul_widen_optab; 2359 else if (!from_unsigned1 && !from_unsigned2) 2360 op = smul_widen_optab; 2361 else 2362 op = usmul_widen_optab; 2363 2364 handler = find_widening_optab_handler_and_mode (op, to_mode, from_mode, 2365 &actual_mode); 2366 2367 if (handler == CODE_FOR_nothing) 2368 { 2369 if (op != smul_widen_optab) 2370 { 2371 /* We can use a signed multiply with unsigned types as long as 2372 there is a wider mode to use, or it is the smaller of the two 2373 types that is unsigned. Note that type1 >= type2, always. */ 2374 if ((TYPE_UNSIGNED (type1) 2375 && TYPE_PRECISION (type1) == GET_MODE_PRECISION (from_mode)) 2376 || (TYPE_UNSIGNED (type2) 2377 && TYPE_PRECISION (type2) == GET_MODE_PRECISION (from_mode))) 2378 { 2379 if (!GET_MODE_WIDER_MODE (from_mode).exists (&from_mode) 2380 || GET_MODE_SIZE (to_mode) <= GET_MODE_SIZE (from_mode)) 2381 return false; 2382 } 2383 2384 op = smul_widen_optab; 2385 handler = find_widening_optab_handler_and_mode (op, to_mode, 2386 from_mode, 2387 &actual_mode); 2388 2389 if (handler == CODE_FOR_nothing) 2390 return false; 2391 2392 from_unsigned1 = from_unsigned2 = false; 2393 } 2394 else 2395 return false; 2396 } 2397 2398 /* Ensure that the inputs to the handler are in the correct precison 2399 for the opcode. This will be the full mode size. */ 2400 actual_precision = GET_MODE_PRECISION (actual_mode); 2401 if (2 * actual_precision > TYPE_PRECISION (type)) 2402 return false; 2403 if (actual_precision != TYPE_PRECISION (type1) 2404 || from_unsigned1 != TYPE_UNSIGNED (type1)) 2405 rhs1 = build_and_insert_cast (gsi, loc, 2406 build_nonstandard_integer_type 2407 (actual_precision, from_unsigned1), rhs1); 2408 if (actual_precision != TYPE_PRECISION (type2) 2409 || from_unsigned2 != TYPE_UNSIGNED (type2)) 2410 rhs2 = build_and_insert_cast (gsi, loc, 2411 build_nonstandard_integer_type 2412 (actual_precision, from_unsigned2), rhs2); 2413 2414 /* Handle constants. */ 2415 if (TREE_CODE (rhs1) == INTEGER_CST) 2416 rhs1 = fold_convert (type1, rhs1); 2417 if (TREE_CODE (rhs2) == INTEGER_CST) 2418 rhs2 = fold_convert (type2, rhs2); 2419 2420 gimple_assign_set_rhs1 (stmt, rhs1); 2421 gimple_assign_set_rhs2 (stmt, rhs2); 2422 gimple_assign_set_rhs_code (stmt, WIDEN_MULT_EXPR); 2423 update_stmt (stmt); 2424 widen_mul_stats.widen_mults_inserted++; 2425 return true; 2426 } 2427 2428 /* Process a single gimple statement STMT, which is found at the 2429 iterator GSI and has a either a PLUS_EXPR or a MINUS_EXPR as its 2430 rhs (given by CODE), and try to convert it into a 2431 WIDEN_MULT_PLUS_EXPR or a WIDEN_MULT_MINUS_EXPR. The return value 2432 is true iff we converted the statement. */ 2433 2434 static bool 2435 convert_plusminus_to_widen (gimple_stmt_iterator *gsi, gimple *stmt, 2436 enum tree_code code) 2437 { 2438 gimple *rhs1_stmt = NULL, *rhs2_stmt = NULL; 2439 gimple *conv1_stmt = NULL, *conv2_stmt = NULL, *conv_stmt; 2440 tree type, type1, type2, optype; 2441 tree lhs, rhs1, rhs2, mult_rhs1, mult_rhs2, add_rhs; 2442 enum tree_code rhs1_code = ERROR_MARK, rhs2_code = ERROR_MARK; 2443 optab this_optab; 2444 enum tree_code wmult_code; 2445 enum insn_code handler; 2446 scalar_mode to_mode, from_mode, actual_mode; 2447 location_t loc = gimple_location (stmt); 2448 int actual_precision; 2449 bool from_unsigned1, from_unsigned2; 2450 2451 lhs = gimple_assign_lhs (stmt); 2452 type = TREE_TYPE (lhs); 2453 if (TREE_CODE (type) != INTEGER_TYPE 2454 && TREE_CODE (type) != FIXED_POINT_TYPE) 2455 return false; 2456 2457 if (code == MINUS_EXPR) 2458 wmult_code = WIDEN_MULT_MINUS_EXPR; 2459 else 2460 wmult_code = WIDEN_MULT_PLUS_EXPR; 2461 2462 rhs1 = gimple_assign_rhs1 (stmt); 2463 rhs2 = gimple_assign_rhs2 (stmt); 2464 2465 if (TREE_CODE (rhs1) == SSA_NAME) 2466 { 2467 rhs1_stmt = SSA_NAME_DEF_STMT (rhs1); 2468 if (is_gimple_assign (rhs1_stmt)) 2469 rhs1_code = gimple_assign_rhs_code (rhs1_stmt); 2470 } 2471 2472 if (TREE_CODE (rhs2) == SSA_NAME) 2473 { 2474 rhs2_stmt = SSA_NAME_DEF_STMT (rhs2); 2475 if (is_gimple_assign (rhs2_stmt)) 2476 rhs2_code = gimple_assign_rhs_code (rhs2_stmt); 2477 } 2478 2479 /* Allow for one conversion statement between the multiply 2480 and addition/subtraction statement. If there are more than 2481 one conversions then we assume they would invalidate this 2482 transformation. If that's not the case then they should have 2483 been folded before now. */ 2484 if (CONVERT_EXPR_CODE_P (rhs1_code)) 2485 { 2486 conv1_stmt = rhs1_stmt; 2487 rhs1 = gimple_assign_rhs1 (rhs1_stmt); 2488 if (TREE_CODE (rhs1) == SSA_NAME) 2489 { 2490 rhs1_stmt = SSA_NAME_DEF_STMT (rhs1); 2491 if (is_gimple_assign (rhs1_stmt)) 2492 rhs1_code = gimple_assign_rhs_code (rhs1_stmt); 2493 } 2494 else 2495 return false; 2496 } 2497 if (CONVERT_EXPR_CODE_P (rhs2_code)) 2498 { 2499 conv2_stmt = rhs2_stmt; 2500 rhs2 = gimple_assign_rhs1 (rhs2_stmt); 2501 if (TREE_CODE (rhs2) == SSA_NAME) 2502 { 2503 rhs2_stmt = SSA_NAME_DEF_STMT (rhs2); 2504 if (is_gimple_assign (rhs2_stmt)) 2505 rhs2_code = gimple_assign_rhs_code (rhs2_stmt); 2506 } 2507 else 2508 return false; 2509 } 2510 2511 /* If code is WIDEN_MULT_EXPR then it would seem unnecessary to call 2512 is_widening_mult_p, but we still need the rhs returns. 2513 2514 It might also appear that it would be sufficient to use the existing 2515 operands of the widening multiply, but that would limit the choice of 2516 multiply-and-accumulate instructions. 2517 2518 If the widened-multiplication result has more than one uses, it is 2519 probably wiser not to do the conversion. */ 2520 if (code == PLUS_EXPR 2521 && (rhs1_code == MULT_EXPR || rhs1_code == WIDEN_MULT_EXPR)) 2522 { 2523 if (!has_single_use (rhs1) 2524 || !is_widening_mult_p (rhs1_stmt, &type1, &mult_rhs1, 2525 &type2, &mult_rhs2)) 2526 return false; 2527 add_rhs = rhs2; 2528 conv_stmt = conv1_stmt; 2529 } 2530 else if (rhs2_code == MULT_EXPR || rhs2_code == WIDEN_MULT_EXPR) 2531 { 2532 if (!has_single_use (rhs2) 2533 || !is_widening_mult_p (rhs2_stmt, &type1, &mult_rhs1, 2534 &type2, &mult_rhs2)) 2535 return false; 2536 add_rhs = rhs1; 2537 conv_stmt = conv2_stmt; 2538 } 2539 else 2540 return false; 2541 2542 to_mode = SCALAR_TYPE_MODE (type); 2543 from_mode = SCALAR_TYPE_MODE (type1); 2544 if (to_mode == from_mode) 2545 return false; 2546 2547 from_unsigned1 = TYPE_UNSIGNED (type1); 2548 from_unsigned2 = TYPE_UNSIGNED (type2); 2549 optype = type1; 2550 2551 /* There's no such thing as a mixed sign madd yet, so use a wider mode. */ 2552 if (from_unsigned1 != from_unsigned2) 2553 { 2554 if (!INTEGRAL_TYPE_P (type)) 2555 return false; 2556 /* We can use a signed multiply with unsigned types as long as 2557 there is a wider mode to use, or it is the smaller of the two 2558 types that is unsigned. Note that type1 >= type2, always. */ 2559 if ((from_unsigned1 2560 && TYPE_PRECISION (type1) == GET_MODE_PRECISION (from_mode)) 2561 || (from_unsigned2 2562 && TYPE_PRECISION (type2) == GET_MODE_PRECISION (from_mode))) 2563 { 2564 if (!GET_MODE_WIDER_MODE (from_mode).exists (&from_mode) 2565 || GET_MODE_SIZE (from_mode) >= GET_MODE_SIZE (to_mode)) 2566 return false; 2567 } 2568 2569 from_unsigned1 = from_unsigned2 = false; 2570 optype = build_nonstandard_integer_type (GET_MODE_PRECISION (from_mode), 2571 false); 2572 } 2573 2574 /* If there was a conversion between the multiply and addition 2575 then we need to make sure it fits a multiply-and-accumulate. 2576 The should be a single mode change which does not change the 2577 value. */ 2578 if (conv_stmt) 2579 { 2580 /* We use the original, unmodified data types for this. */ 2581 tree from_type = TREE_TYPE (gimple_assign_rhs1 (conv_stmt)); 2582 tree to_type = TREE_TYPE (gimple_assign_lhs (conv_stmt)); 2583 int data_size = TYPE_PRECISION (type1) + TYPE_PRECISION (type2); 2584 bool is_unsigned = TYPE_UNSIGNED (type1) && TYPE_UNSIGNED (type2); 2585 2586 if (TYPE_PRECISION (from_type) > TYPE_PRECISION (to_type)) 2587 { 2588 /* Conversion is a truncate. */ 2589 if (TYPE_PRECISION (to_type) < data_size) 2590 return false; 2591 } 2592 else if (TYPE_PRECISION (from_type) < TYPE_PRECISION (to_type)) 2593 { 2594 /* Conversion is an extend. Check it's the right sort. */ 2595 if (TYPE_UNSIGNED (from_type) != is_unsigned 2596 && !(is_unsigned && TYPE_PRECISION (from_type) > data_size)) 2597 return false; 2598 } 2599 /* else convert is a no-op for our purposes. */ 2600 } 2601 2602 /* Verify that the machine can perform a widening multiply 2603 accumulate in this mode/signedness combination, otherwise 2604 this transformation is likely to pessimize code. */ 2605 this_optab = optab_for_tree_code (wmult_code, optype, optab_default); 2606 handler = find_widening_optab_handler_and_mode (this_optab, to_mode, 2607 from_mode, &actual_mode); 2608 2609 if (handler == CODE_FOR_nothing) 2610 return false; 2611 2612 /* Ensure that the inputs to the handler are in the correct precison 2613 for the opcode. This will be the full mode size. */ 2614 actual_precision = GET_MODE_PRECISION (actual_mode); 2615 if (actual_precision != TYPE_PRECISION (type1) 2616 || from_unsigned1 != TYPE_UNSIGNED (type1)) 2617 mult_rhs1 = build_and_insert_cast (gsi, loc, 2618 build_nonstandard_integer_type 2619 (actual_precision, from_unsigned1), 2620 mult_rhs1); 2621 if (actual_precision != TYPE_PRECISION (type2) 2622 || from_unsigned2 != TYPE_UNSIGNED (type2)) 2623 mult_rhs2 = build_and_insert_cast (gsi, loc, 2624 build_nonstandard_integer_type 2625 (actual_precision, from_unsigned2), 2626 mult_rhs2); 2627 2628 if (!useless_type_conversion_p (type, TREE_TYPE (add_rhs))) 2629 add_rhs = build_and_insert_cast (gsi, loc, type, add_rhs); 2630 2631 /* Handle constants. */ 2632 if (TREE_CODE (mult_rhs1) == INTEGER_CST) 2633 mult_rhs1 = fold_convert (type1, mult_rhs1); 2634 if (TREE_CODE (mult_rhs2) == INTEGER_CST) 2635 mult_rhs2 = fold_convert (type2, mult_rhs2); 2636 2637 gimple_assign_set_rhs_with_ops (gsi, wmult_code, mult_rhs1, mult_rhs2, 2638 add_rhs); 2639 update_stmt (gsi_stmt (*gsi)); 2640 widen_mul_stats.maccs_inserted++; 2641 return true; 2642 } 2643 2644 /* Given a result MUL_RESULT which is a result of a multiplication of OP1 and 2645 OP2 and which we know is used in statements that can be, together with the 2646 multiplication, converted to FMAs, perform the transformation. */ 2647 2648 static void 2649 convert_mult_to_fma_1 (tree mul_result, tree op1, tree op2) 2650 { 2651 tree type = TREE_TYPE (mul_result); 2652 gimple *use_stmt; 2653 imm_use_iterator imm_iter; 2654 gassign *fma_stmt; 2655 2656 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, mul_result) 2657 { 2658 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt); 2659 enum tree_code use_code; 2660 tree addop, mulop1 = op1, result = mul_result; 2661 bool negate_p = false; 2662 2663 if (is_gimple_debug (use_stmt)) 2664 continue; 2665 2666 use_code = gimple_assign_rhs_code (use_stmt); 2667 if (use_code == NEGATE_EXPR) 2668 { 2669 result = gimple_assign_lhs (use_stmt); 2670 use_operand_p use_p; 2671 gimple *neguse_stmt; 2672 single_imm_use (gimple_assign_lhs (use_stmt), &use_p, &neguse_stmt); 2673 gsi_remove (&gsi, true); 2674 release_defs (use_stmt); 2675 2676 use_stmt = neguse_stmt; 2677 gsi = gsi_for_stmt (use_stmt); 2678 use_code = gimple_assign_rhs_code (use_stmt); 2679 negate_p = true; 2680 } 2681 2682 if (gimple_assign_rhs1 (use_stmt) == result) 2683 { 2684 addop = gimple_assign_rhs2 (use_stmt); 2685 /* a * b - c -> a * b + (-c) */ 2686 if (gimple_assign_rhs_code (use_stmt) == MINUS_EXPR) 2687 addop = force_gimple_operand_gsi (&gsi, 2688 build1 (NEGATE_EXPR, 2689 type, addop), 2690 true, NULL_TREE, true, 2691 GSI_SAME_STMT); 2692 } 2693 else 2694 { 2695 addop = gimple_assign_rhs1 (use_stmt); 2696 /* a - b * c -> (-b) * c + a */ 2697 if (gimple_assign_rhs_code (use_stmt) == MINUS_EXPR) 2698 negate_p = !negate_p; 2699 } 2700 2701 if (negate_p) 2702 mulop1 = force_gimple_operand_gsi (&gsi, 2703 build1 (NEGATE_EXPR, 2704 type, mulop1), 2705 true, NULL_TREE, true, 2706 GSI_SAME_STMT); 2707 2708 fma_stmt = gimple_build_assign (gimple_assign_lhs (use_stmt), 2709 FMA_EXPR, mulop1, op2, addop); 2710 2711 if (dump_file && (dump_flags & TDF_DETAILS)) 2712 { 2713 fprintf (dump_file, "Generated FMA "); 2714 print_gimple_stmt (dump_file, fma_stmt, 0, 0); 2715 fprintf (dump_file, "\n"); 2716 } 2717 2718 gsi_replace (&gsi, fma_stmt, true); 2719 widen_mul_stats.fmas_inserted++; 2720 } 2721 } 2722 2723 /* Data necessary to perform the actual transformation from a multiplication 2724 and an addition to an FMA after decision is taken it should be done and to 2725 then delete the multiplication statement from the function IL. */ 2726 2727 struct fma_transformation_info 2728 { 2729 gimple *mul_stmt; 2730 tree mul_result; 2731 tree op1; 2732 tree op2; 2733 }; 2734 2735 /* Structure containing the current state of FMA deferring, i.e. whether we are 2736 deferring, whether to continue deferring, and all data necessary to come 2737 back and perform all deferred transformations. */ 2738 2739 class fma_deferring_state 2740 { 2741 public: 2742 /* Class constructor. Pass true as PERFORM_DEFERRING in order to actually 2743 do any deferring. */ 2744 2745 fma_deferring_state (bool perform_deferring) 2746 : m_candidates (), m_mul_result_set (), m_initial_phi (NULL), 2747 m_last_result (NULL_TREE), m_deferring_p (perform_deferring) {} 2748 2749 /* List of FMA candidates for which we the transformation has been determined 2750 possible but we at this point in BB analysis we do not consider them 2751 beneficial. */ 2752 auto_vec<fma_transformation_info, 8> m_candidates; 2753 2754 /* Set of results of multiplication that are part of an already deferred FMA 2755 candidates. */ 2756 hash_set<tree> m_mul_result_set; 2757 2758 /* The PHI that supposedly feeds back result of a FMA to another over loop 2759 boundary. */ 2760 gphi *m_initial_phi; 2761 2762 /* Result of the last produced FMA candidate or NULL if there has not been 2763 one. */ 2764 tree m_last_result; 2765 2766 /* If true, deferring might still be profitable. If false, transform all 2767 candidates and no longer defer. */ 2768 bool m_deferring_p; 2769 }; 2770 2771 /* Transform all deferred FMA candidates and mark STATE as no longer 2772 deferring. */ 2773 2774 static void 2775 cancel_fma_deferring (fma_deferring_state *state) 2776 { 2777 if (!state->m_deferring_p) 2778 return; 2779 2780 for (unsigned i = 0; i < state->m_candidates.length (); i++) 2781 { 2782 if (dump_file && (dump_flags & TDF_DETAILS)) 2783 fprintf (dump_file, "Generating deferred FMA\n"); 2784 2785 const fma_transformation_info &fti = state->m_candidates[i]; 2786 convert_mult_to_fma_1 (fti.mul_result, fti.op1, fti.op2); 2787 2788 gimple_stmt_iterator gsi = gsi_for_stmt (fti.mul_stmt); 2789 gsi_remove (&gsi, true); 2790 release_defs (fti.mul_stmt); 2791 } 2792 state->m_deferring_p = false; 2793 } 2794 2795 /* If OP is an SSA name defined by a PHI node, return the PHI statement. 2796 Otherwise return NULL. */ 2797 2798 static gphi * 2799 result_of_phi (tree op) 2800 { 2801 if (TREE_CODE (op) != SSA_NAME) 2802 return NULL; 2803 2804 return dyn_cast <gphi *> (SSA_NAME_DEF_STMT (op)); 2805 } 2806 2807 /* After processing statements of a BB and recording STATE, return true if the 2808 initial phi is fed by the last FMA candidate result ore one such result from 2809 previously processed BBs marked in LAST_RESULT_SET. */ 2810 2811 static bool 2812 last_fma_candidate_feeds_initial_phi (fma_deferring_state *state, 2813 hash_set<tree> *last_result_set) 2814 { 2815 ssa_op_iter iter; 2816 use_operand_p use; 2817 FOR_EACH_PHI_ARG (use, state->m_initial_phi, iter, SSA_OP_USE) 2818 { 2819 tree t = USE_FROM_PTR (use); 2820 if (t == state->m_last_result 2821 || last_result_set->contains (t)) 2822 return true; 2823 } 2824 2825 return false; 2826 } 2827 2828 /* Combine the multiplication at MUL_STMT with operands MULOP1 and MULOP2 2829 with uses in additions and subtractions to form fused multiply-add 2830 operations. Returns true if successful and MUL_STMT should be removed. 2831 2832 If STATE indicates that we are deferring FMA transformation, that means 2833 that we do not produce FMAs for basic blocks which look like: 2834 2835 <bb 6> 2836 # accumulator_111 = PHI <0.0(5), accumulator_66(6)> 2837 _65 = _14 * _16; 2838 accumulator_66 = _65 + accumulator_111; 2839 2840 or its unrolled version, i.e. with several FMA candidates that feed result 2841 of one into the addend of another. Instead, we add them to a list in STATE 2842 and if we later discover an FMA candidate that is not part of such a chain, 2843 we go back and perform all deferred past candidates. */ 2844 2845 static bool 2846 convert_mult_to_fma (gimple *mul_stmt, tree op1, tree op2, 2847 fma_deferring_state *state) 2848 { 2849 tree mul_result = gimple_get_lhs (mul_stmt); 2850 tree type = TREE_TYPE (mul_result); 2851 gimple *use_stmt, *neguse_stmt; 2852 use_operand_p use_p; 2853 imm_use_iterator imm_iter; 2854 2855 if (FLOAT_TYPE_P (type) 2856 && flag_fp_contract_mode == FP_CONTRACT_OFF) 2857 return false; 2858 2859 /* We don't want to do bitfield reduction ops. */ 2860 if (INTEGRAL_TYPE_P (type) 2861 && (!type_has_mode_precision_p (type) || TYPE_OVERFLOW_TRAPS (type))) 2862 return false; 2863 2864 /* If the target doesn't support it, don't generate it. We assume that 2865 if fma isn't available then fms, fnma or fnms are not either. */ 2866 if (optab_handler (fma_optab, TYPE_MODE (type)) == CODE_FOR_nothing) 2867 return false; 2868 2869 /* If the multiplication has zero uses, it is kept around probably because 2870 of -fnon-call-exceptions. Don't optimize it away in that case, 2871 it is DCE job. */ 2872 if (has_zero_uses (mul_result)) 2873 return false; 2874 2875 bool check_defer 2876 = (state->m_deferring_p 2877 && (tree_to_shwi (TYPE_SIZE (type)) 2878 <= PARAM_VALUE (PARAM_AVOID_FMA_MAX_BITS))); 2879 bool defer = check_defer; 2880 /* Make sure that the multiplication statement becomes dead after 2881 the transformation, thus that all uses are transformed to FMAs. 2882 This means we assume that an FMA operation has the same cost 2883 as an addition. */ 2884 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, mul_result) 2885 { 2886 enum tree_code use_code; 2887 tree result = mul_result; 2888 bool negate_p = false; 2889 2890 use_stmt = USE_STMT (use_p); 2891 2892 if (is_gimple_debug (use_stmt)) 2893 continue; 2894 2895 /* For now restrict this operations to single basic blocks. In theory 2896 we would want to support sinking the multiplication in 2897 m = a*b; 2898 if () 2899 ma = m + c; 2900 else 2901 d = m; 2902 to form a fma in the then block and sink the multiplication to the 2903 else block. */ 2904 if (gimple_bb (use_stmt) != gimple_bb (mul_stmt)) 2905 return false; 2906 2907 if (!is_gimple_assign (use_stmt)) 2908 return false; 2909 2910 use_code = gimple_assign_rhs_code (use_stmt); 2911 2912 /* A negate on the multiplication leads to FNMA. */ 2913 if (use_code == NEGATE_EXPR) 2914 { 2915 ssa_op_iter iter; 2916 use_operand_p usep; 2917 2918 result = gimple_assign_lhs (use_stmt); 2919 2920 /* Make sure the negate statement becomes dead with this 2921 single transformation. */ 2922 if (!single_imm_use (gimple_assign_lhs (use_stmt), 2923 &use_p, &neguse_stmt)) 2924 return false; 2925 2926 /* Make sure the multiplication isn't also used on that stmt. */ 2927 FOR_EACH_PHI_OR_STMT_USE (usep, neguse_stmt, iter, SSA_OP_USE) 2928 if (USE_FROM_PTR (usep) == mul_result) 2929 return false; 2930 2931 /* Re-validate. */ 2932 use_stmt = neguse_stmt; 2933 if (gimple_bb (use_stmt) != gimple_bb (mul_stmt)) 2934 return false; 2935 if (!is_gimple_assign (use_stmt)) 2936 return false; 2937 2938 use_code = gimple_assign_rhs_code (use_stmt); 2939 negate_p = true; 2940 } 2941 2942 switch (use_code) 2943 { 2944 case MINUS_EXPR: 2945 if (gimple_assign_rhs2 (use_stmt) == result) 2946 negate_p = !negate_p; 2947 break; 2948 case PLUS_EXPR: 2949 break; 2950 default: 2951 /* FMA can only be formed from PLUS and MINUS. */ 2952 return false; 2953 } 2954 2955 /* If the subtrahend (gimple_assign_rhs2 (use_stmt)) is computed 2956 by a MULT_EXPR that we'll visit later, we might be able to 2957 get a more profitable match with fnma. 2958 OTOH, if we don't, a negate / fma pair has likely lower latency 2959 that a mult / subtract pair. */ 2960 if (use_code == MINUS_EXPR && !negate_p 2961 && gimple_assign_rhs1 (use_stmt) == result 2962 && optab_handler (fms_optab, TYPE_MODE (type)) == CODE_FOR_nothing 2963 && optab_handler (fnma_optab, TYPE_MODE (type)) != CODE_FOR_nothing) 2964 { 2965 tree rhs2 = gimple_assign_rhs2 (use_stmt); 2966 2967 if (TREE_CODE (rhs2) == SSA_NAME) 2968 { 2969 gimple *stmt2 = SSA_NAME_DEF_STMT (rhs2); 2970 if (has_single_use (rhs2) 2971 && is_gimple_assign (stmt2) 2972 && gimple_assign_rhs_code (stmt2) == MULT_EXPR) 2973 return false; 2974 } 2975 } 2976 2977 tree use_rhs1 = gimple_assign_rhs1 (use_stmt); 2978 tree use_rhs2 = gimple_assign_rhs2 (use_stmt); 2979 /* We can't handle a * b + a * b. */ 2980 if (use_rhs1 == use_rhs2) 2981 return false; 2982 /* If deferring, make sure we are not looking at an instruction that 2983 wouldn't have existed if we were not. */ 2984 if (state->m_deferring_p 2985 && (state->m_mul_result_set.contains (use_rhs1) 2986 || state->m_mul_result_set.contains (use_rhs2))) 2987 return false; 2988 2989 if (check_defer) 2990 { 2991 tree use_lhs = gimple_assign_lhs (use_stmt); 2992 if (state->m_last_result) 2993 { 2994 if (use_rhs2 == state->m_last_result 2995 || use_rhs1 == state->m_last_result) 2996 defer = true; 2997 else 2998 defer = false; 2999 } 3000 else 3001 { 3002 gcc_checking_assert (!state->m_initial_phi); 3003 gphi *phi; 3004 if (use_rhs1 == result) 3005 phi = result_of_phi (use_rhs2); 3006 else 3007 { 3008 gcc_assert (use_rhs2 == result); 3009 phi = result_of_phi (use_rhs1); 3010 } 3011 3012 if (phi) 3013 { 3014 state->m_initial_phi = phi; 3015 defer = true; 3016 } 3017 else 3018 defer = false; 3019 } 3020 3021 state->m_last_result = use_lhs; 3022 check_defer = false; 3023 } 3024 else 3025 defer = false; 3026 3027 /* While it is possible to validate whether or not the exact form that 3028 we've recognized is available in the backend, the assumption is that 3029 if the deferring logic above did not trigger, the transformation is 3030 never a loss. For instance, suppose the target only has the plain FMA 3031 pattern available. Consider a*b-c -> fma(a,b,-c): we've exchanged 3032 MUL+SUB for FMA+NEG, which is still two operations. Consider 3033 -(a*b)-c -> fma(-a,b,-c): we still have 3 operations, but in the FMA 3034 form the two NEGs are independent and could be run in parallel. */ 3035 } 3036 3037 if (defer) 3038 { 3039 fma_transformation_info fti; 3040 fti.mul_stmt = mul_stmt; 3041 fti.mul_result = mul_result; 3042 fti.op1 = op1; 3043 fti.op2 = op2; 3044 state->m_candidates.safe_push (fti); 3045 state->m_mul_result_set.add (mul_result); 3046 3047 if (dump_file && (dump_flags & TDF_DETAILS)) 3048 { 3049 fprintf (dump_file, "Deferred generating FMA for multiplication "); 3050 print_gimple_stmt (dump_file, mul_stmt, 0, 0); 3051 fprintf (dump_file, "\n"); 3052 } 3053 3054 return false; 3055 } 3056 else 3057 { 3058 if (state->m_deferring_p) 3059 cancel_fma_deferring (state); 3060 convert_mult_to_fma_1 (mul_result, op1, op2); 3061 return true; 3062 } 3063 } 3064 3065 3066 /* Helper function of match_uaddsub_overflow. Return 1 3067 if USE_STMT is unsigned overflow check ovf != 0 for 3068 STMT, -1 if USE_STMT is unsigned overflow check ovf == 0 3069 and 0 otherwise. */ 3070 3071 static int 3072 uaddsub_overflow_check_p (gimple *stmt, gimple *use_stmt) 3073 { 3074 enum tree_code ccode = ERROR_MARK; 3075 tree crhs1 = NULL_TREE, crhs2 = NULL_TREE; 3076 if (gimple_code (use_stmt) == GIMPLE_COND) 3077 { 3078 ccode = gimple_cond_code (use_stmt); 3079 crhs1 = gimple_cond_lhs (use_stmt); 3080 crhs2 = gimple_cond_rhs (use_stmt); 3081 } 3082 else if (is_gimple_assign (use_stmt)) 3083 { 3084 if (gimple_assign_rhs_class (use_stmt) == GIMPLE_BINARY_RHS) 3085 { 3086 ccode = gimple_assign_rhs_code (use_stmt); 3087 crhs1 = gimple_assign_rhs1 (use_stmt); 3088 crhs2 = gimple_assign_rhs2 (use_stmt); 3089 } 3090 else if (gimple_assign_rhs_code (use_stmt) == COND_EXPR) 3091 { 3092 tree cond = gimple_assign_rhs1 (use_stmt); 3093 if (COMPARISON_CLASS_P (cond)) 3094 { 3095 ccode = TREE_CODE (cond); 3096 crhs1 = TREE_OPERAND (cond, 0); 3097 crhs2 = TREE_OPERAND (cond, 1); 3098 } 3099 else 3100 return 0; 3101 } 3102 else 3103 return 0; 3104 } 3105 else 3106 return 0; 3107 3108 if (TREE_CODE_CLASS (ccode) != tcc_comparison) 3109 return 0; 3110 3111 enum tree_code code = gimple_assign_rhs_code (stmt); 3112 tree lhs = gimple_assign_lhs (stmt); 3113 tree rhs1 = gimple_assign_rhs1 (stmt); 3114 tree rhs2 = gimple_assign_rhs2 (stmt); 3115 3116 switch (ccode) 3117 { 3118 case GT_EXPR: 3119 case LE_EXPR: 3120 /* r = a - b; r > a or r <= a 3121 r = a + b; a > r or a <= r or b > r or b <= r. */ 3122 if ((code == MINUS_EXPR && crhs1 == lhs && crhs2 == rhs1) 3123 || (code == PLUS_EXPR && (crhs1 == rhs1 || crhs1 == rhs2) 3124 && crhs2 == lhs)) 3125 return ccode == GT_EXPR ? 1 : -1; 3126 break; 3127 case LT_EXPR: 3128 case GE_EXPR: 3129 /* r = a - b; a < r or a >= r 3130 r = a + b; r < a or r >= a or r < b or r >= b. */ 3131 if ((code == MINUS_EXPR && crhs1 == rhs1 && crhs2 == lhs) 3132 || (code == PLUS_EXPR && crhs1 == lhs 3133 && (crhs2 == rhs1 || crhs2 == rhs2))) 3134 return ccode == LT_EXPR ? 1 : -1; 3135 break; 3136 default: 3137 break; 3138 } 3139 return 0; 3140 } 3141 3142 /* Recognize for unsigned x 3143 x = y - z; 3144 if (x > y) 3145 where there are other uses of x and replace it with 3146 _7 = SUB_OVERFLOW (y, z); 3147 x = REALPART_EXPR <_7>; 3148 _8 = IMAGPART_EXPR <_7>; 3149 if (_8) 3150 and similarly for addition. */ 3151 3152 static bool 3153 match_uaddsub_overflow (gimple_stmt_iterator *gsi, gimple *stmt, 3154 enum tree_code code) 3155 { 3156 tree lhs = gimple_assign_lhs (stmt); 3157 tree type = TREE_TYPE (lhs); 3158 use_operand_p use_p; 3159 imm_use_iterator iter; 3160 bool use_seen = false; 3161 bool ovf_use_seen = false; 3162 gimple *use_stmt; 3163 3164 gcc_checking_assert (code == PLUS_EXPR || code == MINUS_EXPR); 3165 if (!INTEGRAL_TYPE_P (type) 3166 || !TYPE_UNSIGNED (type) 3167 || has_zero_uses (lhs) 3168 || has_single_use (lhs) 3169 || optab_handler (code == PLUS_EXPR ? uaddv4_optab : usubv4_optab, 3170 TYPE_MODE (type)) == CODE_FOR_nothing) 3171 return false; 3172 3173 FOR_EACH_IMM_USE_FAST (use_p, iter, lhs) 3174 { 3175 use_stmt = USE_STMT (use_p); 3176 if (is_gimple_debug (use_stmt)) 3177 continue; 3178 3179 if (uaddsub_overflow_check_p (stmt, use_stmt)) 3180 ovf_use_seen = true; 3181 else 3182 use_seen = true; 3183 if (ovf_use_seen && use_seen) 3184 break; 3185 } 3186 3187 if (!ovf_use_seen || !use_seen) 3188 return false; 3189 3190 tree ctype = build_complex_type (type); 3191 tree rhs1 = gimple_assign_rhs1 (stmt); 3192 tree rhs2 = gimple_assign_rhs2 (stmt); 3193 gcall *g = gimple_build_call_internal (code == PLUS_EXPR 3194 ? IFN_ADD_OVERFLOW : IFN_SUB_OVERFLOW, 3195 2, rhs1, rhs2); 3196 tree ctmp = make_ssa_name (ctype); 3197 gimple_call_set_lhs (g, ctmp); 3198 gsi_insert_before (gsi, g, GSI_SAME_STMT); 3199 gassign *g2 = gimple_build_assign (lhs, REALPART_EXPR, 3200 build1 (REALPART_EXPR, type, ctmp)); 3201 gsi_replace (gsi, g2, true); 3202 tree ovf = make_ssa_name (type); 3203 g2 = gimple_build_assign (ovf, IMAGPART_EXPR, 3204 build1 (IMAGPART_EXPR, type, ctmp)); 3205 gsi_insert_after (gsi, g2, GSI_NEW_STMT); 3206 3207 FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs) 3208 { 3209 if (is_gimple_debug (use_stmt)) 3210 continue; 3211 3212 int ovf_use = uaddsub_overflow_check_p (stmt, use_stmt); 3213 if (ovf_use == 0) 3214 continue; 3215 if (gimple_code (use_stmt) == GIMPLE_COND) 3216 { 3217 gcond *cond_stmt = as_a <gcond *> (use_stmt); 3218 gimple_cond_set_lhs (cond_stmt, ovf); 3219 gimple_cond_set_rhs (cond_stmt, build_int_cst (type, 0)); 3220 gimple_cond_set_code (cond_stmt, ovf_use == 1 ? NE_EXPR : EQ_EXPR); 3221 } 3222 else 3223 { 3224 gcc_checking_assert (is_gimple_assign (use_stmt)); 3225 if (gimple_assign_rhs_class (use_stmt) == GIMPLE_BINARY_RHS) 3226 { 3227 gimple_assign_set_rhs1 (use_stmt, ovf); 3228 gimple_assign_set_rhs2 (use_stmt, build_int_cst (type, 0)); 3229 gimple_assign_set_rhs_code (use_stmt, 3230 ovf_use == 1 ? NE_EXPR : EQ_EXPR); 3231 } 3232 else 3233 { 3234 gcc_checking_assert (gimple_assign_rhs_code (use_stmt) 3235 == COND_EXPR); 3236 tree cond = build2 (ovf_use == 1 ? NE_EXPR : EQ_EXPR, 3237 boolean_type_node, ovf, 3238 build_int_cst (type, 0)); 3239 gimple_assign_set_rhs1 (use_stmt, cond); 3240 } 3241 } 3242 update_stmt (use_stmt); 3243 } 3244 return true; 3245 } 3246 3247 /* Return true if target has support for divmod. */ 3248 3249 static bool 3250 target_supports_divmod_p (optab divmod_optab, optab div_optab, machine_mode mode) 3251 { 3252 /* If target supports hardware divmod insn, use it for divmod. */ 3253 if (optab_handler (divmod_optab, mode) != CODE_FOR_nothing) 3254 return true; 3255 3256 /* Check if libfunc for divmod is available. */ 3257 rtx libfunc = optab_libfunc (divmod_optab, mode); 3258 if (libfunc != NULL_RTX) 3259 { 3260 /* If optab_handler exists for div_optab, perhaps in a wider mode, 3261 we don't want to use the libfunc even if it exists for given mode. */ 3262 machine_mode div_mode; 3263 FOR_EACH_MODE_FROM (div_mode, mode) 3264 if (optab_handler (div_optab, div_mode) != CODE_FOR_nothing) 3265 return false; 3266 3267 return targetm.expand_divmod_libfunc != NULL; 3268 } 3269 3270 return false; 3271 } 3272 3273 /* Check if stmt is candidate for divmod transform. */ 3274 3275 static bool 3276 divmod_candidate_p (gassign *stmt) 3277 { 3278 tree type = TREE_TYPE (gimple_assign_lhs (stmt)); 3279 machine_mode mode = TYPE_MODE (type); 3280 optab divmod_optab, div_optab; 3281 3282 if (TYPE_UNSIGNED (type)) 3283 { 3284 divmod_optab = udivmod_optab; 3285 div_optab = udiv_optab; 3286 } 3287 else 3288 { 3289 divmod_optab = sdivmod_optab; 3290 div_optab = sdiv_optab; 3291 } 3292 3293 tree op1 = gimple_assign_rhs1 (stmt); 3294 tree op2 = gimple_assign_rhs2 (stmt); 3295 3296 /* Disable the transform if either is a constant, since division-by-constant 3297 may have specialized expansion. */ 3298 if (CONSTANT_CLASS_P (op1) || CONSTANT_CLASS_P (op2)) 3299 return false; 3300 3301 /* Exclude the case where TYPE_OVERFLOW_TRAPS (type) as that should 3302 expand using the [su]divv optabs. */ 3303 if (TYPE_OVERFLOW_TRAPS (type)) 3304 return false; 3305 3306 if (!target_supports_divmod_p (divmod_optab, div_optab, mode)) 3307 return false; 3308 3309 return true; 3310 } 3311 3312 /* This function looks for: 3313 t1 = a TRUNC_DIV_EXPR b; 3314 t2 = a TRUNC_MOD_EXPR b; 3315 and transforms it to the following sequence: 3316 complex_tmp = DIVMOD (a, b); 3317 t1 = REALPART_EXPR(a); 3318 t2 = IMAGPART_EXPR(b); 3319 For conditions enabling the transform see divmod_candidate_p(). 3320 3321 The pass has three parts: 3322 1) Find top_stmt which is trunc_div or trunc_mod stmt and dominates all 3323 other trunc_div_expr and trunc_mod_expr stmts. 3324 2) Add top_stmt and all trunc_div and trunc_mod stmts dominated by top_stmt 3325 to stmts vector. 3326 3) Insert DIVMOD call just before top_stmt and update entries in 3327 stmts vector to use return value of DIMOVD (REALEXPR_PART for div, 3328 IMAGPART_EXPR for mod). */ 3329 3330 static bool 3331 convert_to_divmod (gassign *stmt) 3332 { 3333 if (stmt_can_throw_internal (stmt) 3334 || !divmod_candidate_p (stmt)) 3335 return false; 3336 3337 tree op1 = gimple_assign_rhs1 (stmt); 3338 tree op2 = gimple_assign_rhs2 (stmt); 3339 3340 imm_use_iterator use_iter; 3341 gimple *use_stmt; 3342 auto_vec<gimple *> stmts; 3343 3344 gimple *top_stmt = stmt; 3345 basic_block top_bb = gimple_bb (stmt); 3346 3347 /* Part 1: Try to set top_stmt to "topmost" stmt that dominates 3348 at-least stmt and possibly other trunc_div/trunc_mod stmts 3349 having same operands as stmt. */ 3350 3351 FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, op1) 3352 { 3353 if (is_gimple_assign (use_stmt) 3354 && (gimple_assign_rhs_code (use_stmt) == TRUNC_DIV_EXPR 3355 || gimple_assign_rhs_code (use_stmt) == TRUNC_MOD_EXPR) 3356 && operand_equal_p (op1, gimple_assign_rhs1 (use_stmt), 0) 3357 && operand_equal_p (op2, gimple_assign_rhs2 (use_stmt), 0)) 3358 { 3359 if (stmt_can_throw_internal (use_stmt)) 3360 continue; 3361 3362 basic_block bb = gimple_bb (use_stmt); 3363 3364 if (bb == top_bb) 3365 { 3366 if (gimple_uid (use_stmt) < gimple_uid (top_stmt)) 3367 top_stmt = use_stmt; 3368 } 3369 else if (dominated_by_p (CDI_DOMINATORS, top_bb, bb)) 3370 { 3371 top_bb = bb; 3372 top_stmt = use_stmt; 3373 } 3374 } 3375 } 3376 3377 tree top_op1 = gimple_assign_rhs1 (top_stmt); 3378 tree top_op2 = gimple_assign_rhs2 (top_stmt); 3379 3380 stmts.safe_push (top_stmt); 3381 bool div_seen = (gimple_assign_rhs_code (top_stmt) == TRUNC_DIV_EXPR); 3382 3383 /* Part 2: Add all trunc_div/trunc_mod statements domianted by top_bb 3384 to stmts vector. The 2nd loop will always add stmt to stmts vector, since 3385 gimple_bb (top_stmt) dominates gimple_bb (stmt), so the 3386 2nd loop ends up adding at-least single trunc_mod_expr stmt. */ 3387 3388 FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, top_op1) 3389 { 3390 if (is_gimple_assign (use_stmt) 3391 && (gimple_assign_rhs_code (use_stmt) == TRUNC_DIV_EXPR 3392 || gimple_assign_rhs_code (use_stmt) == TRUNC_MOD_EXPR) 3393 && operand_equal_p (top_op1, gimple_assign_rhs1 (use_stmt), 0) 3394 && operand_equal_p (top_op2, gimple_assign_rhs2 (use_stmt), 0)) 3395 { 3396 if (use_stmt == top_stmt 3397 || stmt_can_throw_internal (use_stmt) 3398 || !dominated_by_p (CDI_DOMINATORS, gimple_bb (use_stmt), top_bb)) 3399 continue; 3400 3401 stmts.safe_push (use_stmt); 3402 if (gimple_assign_rhs_code (use_stmt) == TRUNC_DIV_EXPR) 3403 div_seen = true; 3404 } 3405 } 3406 3407 if (!div_seen) 3408 return false; 3409 3410 /* Part 3: Create libcall to internal fn DIVMOD: 3411 divmod_tmp = DIVMOD (op1, op2). */ 3412 3413 gcall *call_stmt = gimple_build_call_internal (IFN_DIVMOD, 2, op1, op2); 3414 tree res = make_temp_ssa_name (build_complex_type (TREE_TYPE (op1)), 3415 call_stmt, "divmod_tmp"); 3416 gimple_call_set_lhs (call_stmt, res); 3417 /* We rejected throwing statements above. */ 3418 gimple_call_set_nothrow (call_stmt, true); 3419 3420 /* Insert the call before top_stmt. */ 3421 gimple_stmt_iterator top_stmt_gsi = gsi_for_stmt (top_stmt); 3422 gsi_insert_before (&top_stmt_gsi, call_stmt, GSI_SAME_STMT); 3423 3424 widen_mul_stats.divmod_calls_inserted++; 3425 3426 /* Update all statements in stmts vector: 3427 lhs = op1 TRUNC_DIV_EXPR op2 -> lhs = REALPART_EXPR<divmod_tmp> 3428 lhs = op1 TRUNC_MOD_EXPR op2 -> lhs = IMAGPART_EXPR<divmod_tmp>. */ 3429 3430 for (unsigned i = 0; stmts.iterate (i, &use_stmt); ++i) 3431 { 3432 tree new_rhs; 3433 3434 switch (gimple_assign_rhs_code (use_stmt)) 3435 { 3436 case TRUNC_DIV_EXPR: 3437 new_rhs = fold_build1 (REALPART_EXPR, TREE_TYPE (op1), res); 3438 break; 3439 3440 case TRUNC_MOD_EXPR: 3441 new_rhs = fold_build1 (IMAGPART_EXPR, TREE_TYPE (op1), res); 3442 break; 3443 3444 default: 3445 gcc_unreachable (); 3446 } 3447 3448 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt); 3449 gimple_assign_set_rhs_from_tree (&gsi, new_rhs); 3450 update_stmt (use_stmt); 3451 } 3452 3453 return true; 3454 } 3455 3456 /* Find integer multiplications where the operands are extended from 3457 smaller types, and replace the MULT_EXPR with a WIDEN_MULT_EXPR 3458 where appropriate. */ 3459 3460 namespace { 3461 3462 const pass_data pass_data_optimize_widening_mul = 3463 { 3464 GIMPLE_PASS, /* type */ 3465 "widening_mul", /* name */ 3466 OPTGROUP_NONE, /* optinfo_flags */ 3467 TV_TREE_WIDEN_MUL, /* tv_id */ 3468 PROP_ssa, /* properties_required */ 3469 0, /* properties_provided */ 3470 0, /* properties_destroyed */ 3471 0, /* todo_flags_start */ 3472 TODO_update_ssa, /* todo_flags_finish */ 3473 }; 3474 3475 class pass_optimize_widening_mul : public gimple_opt_pass 3476 { 3477 public: 3478 pass_optimize_widening_mul (gcc::context *ctxt) 3479 : gimple_opt_pass (pass_data_optimize_widening_mul, ctxt) 3480 {} 3481 3482 /* opt_pass methods: */ 3483 virtual bool gate (function *) 3484 { 3485 return flag_expensive_optimizations && optimize; 3486 } 3487 3488 virtual unsigned int execute (function *); 3489 3490 }; // class pass_optimize_widening_mul 3491 3492 /* Walker class to perform the transformation in reverse dominance order. */ 3493 3494 class math_opts_dom_walker : public dom_walker 3495 { 3496 public: 3497 /* Constructor, CFG_CHANGED is a pointer to a boolean flag that will be set 3498 if walking modidifes the CFG. */ 3499 3500 math_opts_dom_walker (bool *cfg_changed_p) 3501 : dom_walker (CDI_DOMINATORS), m_last_result_set (), 3502 m_cfg_changed_p (cfg_changed_p) {} 3503 3504 /* The actual actions performed in the walk. */ 3505 3506 virtual void after_dom_children (basic_block); 3507 3508 /* Set of results of chains of multiply and add statement combinations that 3509 were not transformed into FMAs because of active deferring. */ 3510 hash_set<tree> m_last_result_set; 3511 3512 /* Pointer to a flag of the user that needs to be set if CFG has been 3513 modified. */ 3514 bool *m_cfg_changed_p; 3515 }; 3516 3517 void 3518 math_opts_dom_walker::after_dom_children (basic_block bb) 3519 { 3520 gimple_stmt_iterator gsi; 3521 3522 fma_deferring_state fma_state (PARAM_VALUE (PARAM_AVOID_FMA_MAX_BITS) > 0); 3523 3524 for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi);) 3525 { 3526 gimple *stmt = gsi_stmt (gsi); 3527 enum tree_code code; 3528 3529 if (is_gimple_assign (stmt)) 3530 { 3531 code = gimple_assign_rhs_code (stmt); 3532 switch (code) 3533 { 3534 case MULT_EXPR: 3535 if (!convert_mult_to_widen (stmt, &gsi) 3536 && !convert_expand_mult_copysign (stmt, &gsi) 3537 && convert_mult_to_fma (stmt, 3538 gimple_assign_rhs1 (stmt), 3539 gimple_assign_rhs2 (stmt), 3540 &fma_state)) 3541 { 3542 gsi_remove (&gsi, true); 3543 release_defs (stmt); 3544 continue; 3545 } 3546 break; 3547 3548 case PLUS_EXPR: 3549 case MINUS_EXPR: 3550 if (!convert_plusminus_to_widen (&gsi, stmt, code)) 3551 match_uaddsub_overflow (&gsi, stmt, code); 3552 break; 3553 3554 case TRUNC_MOD_EXPR: 3555 convert_to_divmod (as_a<gassign *> (stmt)); 3556 break; 3557 3558 default:; 3559 } 3560 } 3561 else if (is_gimple_call (stmt)) 3562 { 3563 tree fndecl = gimple_call_fndecl (stmt); 3564 if (fndecl && gimple_call_builtin_p (stmt, BUILT_IN_NORMAL)) 3565 { 3566 switch (DECL_FUNCTION_CODE (fndecl)) 3567 { 3568 case BUILT_IN_POWF: 3569 case BUILT_IN_POW: 3570 case BUILT_IN_POWL: 3571 if (gimple_call_lhs (stmt) 3572 && TREE_CODE (gimple_call_arg (stmt, 1)) == REAL_CST 3573 && real_equal 3574 (&TREE_REAL_CST (gimple_call_arg (stmt, 1)), 3575 &dconst2) 3576 && convert_mult_to_fma (stmt, 3577 gimple_call_arg (stmt, 0), 3578 gimple_call_arg (stmt, 0), 3579 &fma_state)) 3580 { 3581 unlink_stmt_vdef (stmt); 3582 if (gsi_remove (&gsi, true) 3583 && gimple_purge_dead_eh_edges (bb)) 3584 *m_cfg_changed_p = true; 3585 release_defs (stmt); 3586 continue; 3587 } 3588 break; 3589 3590 default:; 3591 } 3592 } 3593 else 3594 cancel_fma_deferring (&fma_state); 3595 } 3596 gsi_next (&gsi); 3597 } 3598 if (fma_state.m_deferring_p 3599 && fma_state.m_initial_phi) 3600 { 3601 gcc_checking_assert (fma_state.m_last_result); 3602 if (!last_fma_candidate_feeds_initial_phi (&fma_state, 3603 &m_last_result_set)) 3604 cancel_fma_deferring (&fma_state); 3605 else 3606 m_last_result_set.add (fma_state.m_last_result); 3607 } 3608 } 3609 3610 3611 unsigned int 3612 pass_optimize_widening_mul::execute (function *fun) 3613 { 3614 bool cfg_changed = false; 3615 3616 memset (&widen_mul_stats, 0, sizeof (widen_mul_stats)); 3617 calculate_dominance_info (CDI_DOMINATORS); 3618 renumber_gimple_stmt_uids (); 3619 3620 math_opts_dom_walker (&cfg_changed).walk (ENTRY_BLOCK_PTR_FOR_FN (cfun)); 3621 3622 statistics_counter_event (fun, "widening multiplications inserted", 3623 widen_mul_stats.widen_mults_inserted); 3624 statistics_counter_event (fun, "widening maccs inserted", 3625 widen_mul_stats.maccs_inserted); 3626 statistics_counter_event (fun, "fused multiply-adds inserted", 3627 widen_mul_stats.fmas_inserted); 3628 statistics_counter_event (fun, "divmod calls inserted", 3629 widen_mul_stats.divmod_calls_inserted); 3630 3631 return cfg_changed ? TODO_cleanup_cfg : 0; 3632 } 3633 3634 } // anon namespace 3635 3636 gimple_opt_pass * 3637 make_pass_optimize_widening_mul (gcc::context *ctxt) 3638 { 3639 return new pass_optimize_widening_mul (ctxt); 3640 } 3641