1/* Reassociation for trees. 2 Copyright (C) 2005 Free Software Foundation, Inc. 3 Contributed by Daniel Berlin <dan@dberlin.org> 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify 8it under the terms of the GNU General Public License as published by 9the Free Software Foundation; either version 2, or (at your option) 10any later version. 11 12GCC is distributed in the hope that it will be useful, 13but WITHOUT ANY WARRANTY; without even the implied warranty of 14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15GNU General Public License for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING. If not, write to 19the Free Software Foundation, 51 Franklin Street, Fifth Floor, 20Boston, MA 02110-1301, USA. */ 21 22#include "config.h" 23#include "system.h" 24#include "coretypes.h" 25#include "tm.h" 26#include "errors.h" 27#include "ggc.h" 28#include "tree.h" 29#include "basic-block.h" 30#include "diagnostic.h" 31#include "tree-inline.h" 32#include "tree-flow.h" 33#include "tree-gimple.h" 34#include "tree-dump.h" 35#include "timevar.h" 36#include "tree-iterator.h" 37#include "tree-pass.h" 38#include "alloc-pool.h" 39#include "vec.h" 40#include "langhooks.h" 41 42/* This is a simple global reassociation pass. It is, in part, based 43 on the LLVM pass of the same name (They do some things more/less 44 than we do, in different orders, etc). 45 46 It consists of five steps: 47 48 1. Breaking up subtract operations into addition + negate, where 49 it would promote the reassociation of adds. 50 51 2. Left linearization of the expression trees, so that (A+B)+(C+D) 52 becomes (((A+B)+C)+D), which is easier for us to rewrite later. 53 During linearization, we place the operands of the binary 54 expressions into a vector of operand_entry_t 55 56 3. Optimization of the operand lists, eliminating things like a + 57 -a, a & a, etc. 58 59 4. Rewrite the expression trees we linearized and optimized so 60 they are in proper rank order. 61 62 5. Repropagate negates, as nothing else will clean it up ATM. 63 64 A bit of theory on #4, since nobody seems to write anything down 65 about why it makes sense to do it the way they do it: 66 67 We could do this much nicer theoretically, but don't (for reasons 68 explained after how to do it theoretically nice :P). 69 70 In order to promote the most redundancy elimination, you want 71 binary expressions whose operands are the same rank (or 72 preferably, the same value) exposed to the redundancy eliminator, 73 for possible elimination. 74 75 So the way to do this if we really cared, is to build the new op 76 tree from the leaves to the roots, merging as you go, and putting the 77 new op on the end of the worklist, until you are left with one 78 thing on the worklist. 79 80 IE if you have to rewrite the following set of operands (listed with 81 rank in parentheses), with opcode PLUS_EXPR: 82 83 a (1), b (1), c (1), d (2), e (2) 84 85 86 We start with our merge worklist empty, and the ops list with all of 87 those on it. 88 89 You want to first merge all leaves of the same rank, as much as 90 possible. 91 92 So first build a binary op of 93 94 mergetmp = a + b, and put "mergetmp" on the merge worklist. 95 96 Because there is no three operand form of PLUS_EXPR, c is not going to 97 be exposed to redundancy elimination as a rank 1 operand. 98 99 So you might as well throw it on the merge worklist (you could also 100 consider it to now be a rank two operand, and merge it with d and e, 101 but in this case, you then have evicted e from a binary op. So at 102 least in this situation, you can't win.) 103 104 Then build a binary op of d + e 105 mergetmp2 = d + e 106 107 and put mergetmp2 on the merge worklist. 108 109 so merge worklist = {mergetmp, c, mergetmp2} 110 111 Continue building binary ops of these operations until you have only 112 one operation left on the worklist. 113 114 So we have 115 116 build binary op 117 mergetmp3 = mergetmp + c 118 119 worklist = {mergetmp2, mergetmp3} 120 121 mergetmp4 = mergetmp2 + mergetmp3 122 123 worklist = {mergetmp4} 124 125 because we have one operation left, we can now just set the original 126 statement equal to the result of that operation. 127 128 This will at least expose a + b and d + e to redundancy elimination 129 as binary operations. 130 131 For extra points, you can reuse the old statements to build the 132 mergetmps, since you shouldn't run out. 133 134 So why don't we do this? 135 136 Because it's expensive, and rarely will help. Most trees we are 137 reassociating have 3 or less ops. If they have 2 ops, they already 138 will be written into a nice single binary op. If you have 3 ops, a 139 single simple check suffices to tell you whether the first two are of the 140 same rank. If so, you know to order it 141 142 mergetmp = op1 + op2 143 newstmt = mergetmp + op3 144 145 instead of 146 mergetmp = op2 + op3 147 newstmt = mergetmp + op1 148 149 If all three are of the same rank, you can't expose them all in a 150 single binary operator anyway, so the above is *still* the best you 151 can do. 152 153 Thus, this is what we do. When we have three ops left, we check to see 154 what order to put them in, and call it a day. As a nod to vector sum 155 reduction, we check if any of ops are a really a phi node that is a 156 destructive update for the associating op, and keep the destructive 157 update together for vector sum reduction recognition. */ 158 159 160/* Statistics */ 161static struct 162{ 163 int linearized; 164 int constants_eliminated; 165 int ops_eliminated; 166 int rewritten; 167} reassociate_stats; 168 169/* Operator, rank pair. */ 170typedef struct operand_entry 171{ 172 unsigned int rank; 173 tree op; 174} *operand_entry_t; 175 176static alloc_pool operand_entry_pool; 177 178 179/* Starting rank number for a given basic block, so that we can rank 180 operations using unmovable instructions in that BB based on the bb 181 depth. */ 182static unsigned int *bb_rank; 183 184/* Operand->rank hashtable. */ 185static htab_t operand_rank; 186 187 188/* Look up the operand rank structure for expression E. */ 189 190static operand_entry_t 191find_operand_rank (tree e) 192{ 193 void **slot; 194 struct operand_entry vrd; 195 196 vrd.op = e; 197 slot = htab_find_slot (operand_rank, &vrd, NO_INSERT); 198 if (!slot) 199 return NULL; 200 return ((operand_entry_t) *slot); 201} 202 203/* Insert {E,RANK} into the operand rank hashtable. */ 204 205static void 206insert_operand_rank (tree e, unsigned int rank) 207{ 208 void **slot; 209 operand_entry_t new_pair = pool_alloc (operand_entry_pool); 210 211 new_pair->op = e; 212 new_pair->rank = rank; 213 slot = htab_find_slot (operand_rank, new_pair, INSERT); 214 gcc_assert (*slot == NULL); 215 *slot = new_pair; 216} 217 218/* Return the hash value for a operand rank structure */ 219 220static hashval_t 221operand_entry_hash (const void *p) 222{ 223 const operand_entry_t vr = (operand_entry_t) p; 224 return iterative_hash_expr (vr->op, 0); 225} 226 227/* Return true if two operand rank structures are equal. */ 228 229static int 230operand_entry_eq (const void *p1, const void *p2) 231{ 232 const operand_entry_t vr1 = (operand_entry_t) p1; 233 const operand_entry_t vr2 = (operand_entry_t) p2; 234 return vr1->op == vr2->op; 235} 236 237/* Given an expression E, return the rank of the expression. */ 238 239static unsigned int 240get_rank (tree e) 241{ 242 operand_entry_t vr; 243 244 /* Constants have rank 0. */ 245 if (is_gimple_min_invariant (e)) 246 return 0; 247 248 /* SSA_NAME's have the rank of the expression they are the result 249 of. 250 For globals and uninitialized values, the rank is 0. 251 For function arguments, use the pre-setup rank. 252 For PHI nodes, stores, asm statements, etc, we use the rank of 253 the BB. 254 For simple operations, the rank is the maximum rank of any of 255 its operands, or the bb_rank, whichever is less. 256 I make no claims that this is optimal, however, it gives good 257 results. */ 258 259 if (TREE_CODE (e) == SSA_NAME) 260 { 261 tree stmt; 262 tree rhs; 263 unsigned int rank, maxrank; 264 int i; 265 266 if (TREE_CODE (SSA_NAME_VAR (e)) == PARM_DECL 267 && e == default_def (SSA_NAME_VAR (e))) 268 return find_operand_rank (e)->rank; 269 270 stmt = SSA_NAME_DEF_STMT (e); 271 if (bb_for_stmt (stmt) == NULL) 272 return 0; 273 274 if (TREE_CODE (stmt) != MODIFY_EXPR 275 || !ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS)) 276 return bb_rank[bb_for_stmt (stmt)->index]; 277 278 /* If we already have a rank for this expression, use that. */ 279 vr = find_operand_rank (e); 280 if (vr) 281 return vr->rank; 282 283 /* Otherwise, find the maximum rank for the operands, or the bb 284 rank, whichever is less. */ 285 rank = 0; 286 maxrank = bb_rank[bb_for_stmt(stmt)->index]; 287 rhs = TREE_OPERAND (stmt, 1); 288 if (TREE_CODE_LENGTH (TREE_CODE (rhs)) == 0) 289 rank = MAX (rank, get_rank (rhs)); 290 else 291 { 292 for (i = 0; 293 i < TREE_CODE_LENGTH (TREE_CODE (rhs)) 294 && TREE_OPERAND (rhs, i) 295 && rank != maxrank; 296 i++) 297 rank = MAX(rank, get_rank (TREE_OPERAND (rhs, i))); 298 } 299 300 if (dump_file && (dump_flags & TDF_DETAILS)) 301 { 302 fprintf (dump_file, "Rank for "); 303 print_generic_expr (dump_file, e, 0); 304 fprintf (dump_file, " is %d\n", (rank + 1)); 305 } 306 307 /* Note the rank in the hashtable so we don't recompute it. */ 308 insert_operand_rank (e, (rank + 1)); 309 return (rank + 1); 310 } 311 312 /* Globals, etc, are rank 0 */ 313 return 0; 314} 315 316DEF_VEC_P(operand_entry_t); 317DEF_VEC_ALLOC_P(operand_entry_t, heap); 318 319/* We want integer ones to end up last no matter what, since they are 320 the ones we can do the most with. */ 321#define INTEGER_CONST_TYPE 1 << 3 322#define FLOAT_CONST_TYPE 1 << 2 323#define OTHER_CONST_TYPE 1 << 1 324 325/* Classify an invariant tree into integer, float, or other, so that 326 we can sort them to be near other constants of the same type. */ 327static inline int 328constant_type (tree t) 329{ 330 if (INTEGRAL_TYPE_P (TREE_TYPE (t))) 331 return INTEGER_CONST_TYPE; 332 else if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (t))) 333 return FLOAT_CONST_TYPE; 334 else 335 return OTHER_CONST_TYPE; 336} 337 338/* qsort comparison function to sort operand entries PA and PB by rank 339 so that the sorted array is ordered by rank in decreasing order. */ 340static int 341sort_by_operand_rank (const void *pa, const void *pb) 342{ 343 const operand_entry_t oea = *(const operand_entry_t *)pa; 344 const operand_entry_t oeb = *(const operand_entry_t *)pb; 345 346 /* It's nicer for optimize_expression if constants that are likely 347 to fold when added/multiplied//whatever are put next to each 348 other. Since all constants have rank 0, order them by type. */ 349 if (oeb->rank == 0 && oea->rank == 0) 350 return constant_type (oeb->op) - constant_type (oea->op); 351 352 /* Lastly, make sure the versions that are the same go next to each 353 other. We use SSA_NAME_VERSION because it's stable. */ 354 if ((oeb->rank - oea->rank == 0) 355 && TREE_CODE (oea->op) == SSA_NAME 356 && TREE_CODE (oeb->op) == SSA_NAME) 357 return SSA_NAME_VERSION (oeb->op) - SSA_NAME_VERSION (oea->op); 358 359 return oeb->rank - oea->rank; 360} 361 362/* Add an operand entry to *OPS for the tree operand OP. */ 363 364static void 365add_to_ops_vec (VEC(operand_entry_t, heap) **ops, tree op) 366{ 367 operand_entry_t oe = pool_alloc (operand_entry_pool); 368 369 oe->op = op; 370 oe->rank = get_rank (op); 371 VEC_safe_push (operand_entry_t, heap, *ops, oe); 372} 373 374/* Return true if STMT is reassociable operation containing a binary 375 operation with tree code CODE. */ 376 377static bool 378is_reassociable_op (tree stmt, enum tree_code code) 379{ 380 if (!IS_EMPTY_STMT (stmt) 381 && TREE_CODE (stmt) == MODIFY_EXPR 382 && TREE_CODE (TREE_OPERAND (stmt, 1)) == code 383 && has_single_use (TREE_OPERAND (stmt, 0))) 384 return true; 385 return false; 386} 387 388 389/* Given NAME, if NAME is defined by a unary operation OPCODE, return the 390 operand of the negate operation. Otherwise, return NULL. */ 391 392static tree 393get_unary_op (tree name, enum tree_code opcode) 394{ 395 tree stmt = SSA_NAME_DEF_STMT (name); 396 tree rhs; 397 398 if (TREE_CODE (stmt) != MODIFY_EXPR) 399 return NULL_TREE; 400 401 rhs = TREE_OPERAND (stmt, 1); 402 if (TREE_CODE (rhs) == opcode) 403 return TREE_OPERAND (rhs, 0); 404 return NULL_TREE; 405} 406 407/* If CURR and LAST are a pair of ops that OPCODE allows us to 408 eliminate through equivalences, do so, remove them from OPS, and 409 return true. Otherwise, return false. */ 410 411static bool 412eliminate_duplicate_pair (enum tree_code opcode, 413 VEC (operand_entry_t, heap) **ops, 414 bool *all_done, 415 unsigned int i, 416 operand_entry_t curr, 417 operand_entry_t last) 418{ 419 420 /* If we have two of the same op, and the opcode is & |, min, or max, 421 we can eliminate one of them. 422 If we have two of the same op, and the opcode is ^, we can 423 eliminate both of them. */ 424 425 if (last && last->op == curr->op) 426 { 427 switch (opcode) 428 { 429 case MAX_EXPR: 430 case MIN_EXPR: 431 case BIT_IOR_EXPR: 432 case BIT_AND_EXPR: 433 if (dump_file && (dump_flags & TDF_DETAILS)) 434 { 435 fprintf (dump_file, "Equivalence: "); 436 print_generic_expr (dump_file, curr->op, 0); 437 fprintf (dump_file, " [&|minmax] "); 438 print_generic_expr (dump_file, last->op, 0); 439 fprintf (dump_file, " -> "); 440 print_generic_stmt (dump_file, last->op, 0); 441 } 442 443 VEC_ordered_remove (operand_entry_t, *ops, i); 444 reassociate_stats.ops_eliminated ++; 445 446 return true; 447 448 case BIT_XOR_EXPR: 449 if (dump_file && (dump_flags & TDF_DETAILS)) 450 { 451 fprintf (dump_file, "Equivalence: "); 452 print_generic_expr (dump_file, curr->op, 0); 453 fprintf (dump_file, " ^ "); 454 print_generic_expr (dump_file, last->op, 0); 455 fprintf (dump_file, " -> nothing\n"); 456 } 457 458 reassociate_stats.ops_eliminated += 2; 459 460 if (VEC_length (operand_entry_t, *ops) == 2) 461 { 462 VEC_free (operand_entry_t, heap, *ops); 463 *ops = NULL; 464 add_to_ops_vec (ops, fold_convert (TREE_TYPE (last->op), 465 integer_zero_node)); 466 *all_done = true; 467 } 468 else 469 { 470 VEC_ordered_remove (operand_entry_t, *ops, i-1); 471 VEC_ordered_remove (operand_entry_t, *ops, i-1); 472 } 473 474 return true; 475 476 default: 477 break; 478 } 479 } 480 return false; 481} 482 483/* If OPCODE is PLUS_EXPR, CURR->OP is really a negate expression, 484 look in OPS for a corresponding positive operation to cancel it 485 out. If we find one, remove the other from OPS, replace 486 OPS[CURRINDEX] with 0, and return true. Otherwise, return 487 false. */ 488 489static bool 490eliminate_plus_minus_pair (enum tree_code opcode, 491 VEC (operand_entry_t, heap) **ops, 492 unsigned int currindex, 493 operand_entry_t curr) 494{ 495 tree negateop; 496 unsigned int i; 497 operand_entry_t oe; 498 499 if (opcode != PLUS_EXPR || TREE_CODE (curr->op) != SSA_NAME) 500 return false; 501 502 negateop = get_unary_op (curr->op, NEGATE_EXPR); 503 if (negateop == NULL_TREE) 504 return false; 505 506 /* Any non-negated version will have a rank that is one less than 507 the current rank. So once we hit those ranks, if we don't find 508 one, we can stop. */ 509 510 for (i = currindex + 1; 511 VEC_iterate (operand_entry_t, *ops, i, oe) 512 && oe->rank >= curr->rank - 1 ; 513 i++) 514 { 515 if (oe->op == negateop) 516 { 517 518 if (dump_file && (dump_flags & TDF_DETAILS)) 519 { 520 fprintf (dump_file, "Equivalence: "); 521 print_generic_expr (dump_file, negateop, 0); 522 fprintf (dump_file, " + -"); 523 print_generic_expr (dump_file, oe->op, 0); 524 fprintf (dump_file, " -> 0\n"); 525 } 526 527 VEC_ordered_remove (operand_entry_t, *ops, i); 528 add_to_ops_vec (ops, fold_convert(TREE_TYPE (oe->op), 529 integer_zero_node)); 530 VEC_ordered_remove (operand_entry_t, *ops, currindex); 531 reassociate_stats.ops_eliminated ++; 532 533 return true; 534 } 535 } 536 537 return false; 538} 539 540/* If OPCODE is BIT_IOR_EXPR, BIT_AND_EXPR, and, CURR->OP is really a 541 bitwise not expression, look in OPS for a corresponding operand to 542 cancel it out. If we find one, remove the other from OPS, replace 543 OPS[CURRINDEX] with 0, and return true. Otherwise, return 544 false. */ 545 546static bool 547eliminate_not_pairs (enum tree_code opcode, 548 VEC (operand_entry_t, heap) **ops, 549 unsigned int currindex, 550 operand_entry_t curr) 551{ 552 tree notop; 553 unsigned int i; 554 operand_entry_t oe; 555 556 if ((opcode != BIT_IOR_EXPR && opcode != BIT_AND_EXPR) 557 || TREE_CODE (curr->op) != SSA_NAME) 558 return false; 559 560 notop = get_unary_op (curr->op, BIT_NOT_EXPR); 561 if (notop == NULL_TREE) 562 return false; 563 564 /* Any non-not version will have a rank that is one less than 565 the current rank. So once we hit those ranks, if we don't find 566 one, we can stop. */ 567 568 for (i = currindex + 1; 569 VEC_iterate (operand_entry_t, *ops, i, oe) 570 && oe->rank >= curr->rank - 1; 571 i++) 572 { 573 if (oe->op == notop) 574 { 575 if (dump_file && (dump_flags & TDF_DETAILS)) 576 { 577 fprintf (dump_file, "Equivalence: "); 578 print_generic_expr (dump_file, notop, 0); 579 if (opcode == BIT_AND_EXPR) 580 fprintf (dump_file, " & ~"); 581 else if (opcode == BIT_IOR_EXPR) 582 fprintf (dump_file, " | ~"); 583 print_generic_expr (dump_file, oe->op, 0); 584 if (opcode == BIT_AND_EXPR) 585 fprintf (dump_file, " -> 0\n"); 586 else if (opcode == BIT_IOR_EXPR) 587 fprintf (dump_file, " -> -1\n"); 588 } 589 590 if (opcode == BIT_AND_EXPR) 591 oe->op = fold_convert (TREE_TYPE (oe->op), integer_zero_node); 592 else if (opcode == BIT_IOR_EXPR) 593 oe->op = build_low_bits_mask (TREE_TYPE (oe->op), 594 TYPE_PRECISION (TREE_TYPE (oe->op))); 595 596 reassociate_stats.ops_eliminated 597 += VEC_length (operand_entry_t, *ops) - 1; 598 VEC_free (operand_entry_t, heap, *ops); 599 *ops = NULL; 600 VEC_safe_push (operand_entry_t, heap, *ops, oe); 601 return true; 602 } 603 } 604 605 return false; 606} 607 608/* Use constant value that may be present in OPS to try to eliminate 609 operands. Note that this function is only really used when we've 610 eliminated ops for other reasons, or merged constants. Across 611 single statements, fold already does all of this, plus more. There 612 is little point in duplicating logic, so I've only included the 613 identities that I could ever construct testcases to trigger. */ 614 615static void 616eliminate_using_constants (enum tree_code opcode, 617 VEC(operand_entry_t, heap) **ops) 618{ 619 operand_entry_t oelast = VEC_last (operand_entry_t, *ops); 620 621 if (oelast->rank == 0 && INTEGRAL_TYPE_P (TREE_TYPE (oelast->op))) 622 { 623 switch (opcode) 624 { 625 case BIT_AND_EXPR: 626 if (integer_zerop (oelast->op)) 627 { 628 if (VEC_length (operand_entry_t, *ops) != 1) 629 { 630 if (dump_file && (dump_flags & TDF_DETAILS)) 631 fprintf (dump_file, "Found & 0, removing all other ops\n"); 632 633 reassociate_stats.ops_eliminated 634 += VEC_length (operand_entry_t, *ops) - 1; 635 636 VEC_free (operand_entry_t, heap, *ops); 637 *ops = NULL; 638 VEC_safe_push (operand_entry_t, heap, *ops, oelast); 639 return; 640 } 641 } 642 else if (integer_all_onesp (oelast->op)) 643 { 644 if (VEC_length (operand_entry_t, *ops) != 1) 645 { 646 if (dump_file && (dump_flags & TDF_DETAILS)) 647 fprintf (dump_file, "Found & -1, removing\n"); 648 VEC_pop (operand_entry_t, *ops); 649 reassociate_stats.ops_eliminated++; 650 } 651 } 652 break; 653 case BIT_IOR_EXPR: 654 if (integer_all_onesp (oelast->op)) 655 { 656 if (VEC_length (operand_entry_t, *ops) != 1) 657 { 658 if (dump_file && (dump_flags & TDF_DETAILS)) 659 fprintf (dump_file, "Found | -1, removing all other ops\n"); 660 661 reassociate_stats.ops_eliminated 662 += VEC_length (operand_entry_t, *ops) - 1; 663 664 VEC_free (operand_entry_t, heap, *ops); 665 *ops = NULL; 666 VEC_safe_push (operand_entry_t, heap, *ops, oelast); 667 return; 668 } 669 } 670 else if (integer_zerop (oelast->op)) 671 { 672 if (VEC_length (operand_entry_t, *ops) != 1) 673 { 674 if (dump_file && (dump_flags & TDF_DETAILS)) 675 fprintf (dump_file, "Found | 0, removing\n"); 676 VEC_pop (operand_entry_t, *ops); 677 reassociate_stats.ops_eliminated++; 678 } 679 } 680 break; 681 case MULT_EXPR: 682 if (integer_zerop (oelast->op)) 683 { 684 if (VEC_length (operand_entry_t, *ops) != 1) 685 { 686 if (dump_file && (dump_flags & TDF_DETAILS)) 687 fprintf (dump_file, "Found * 0, removing all other ops\n"); 688 689 reassociate_stats.ops_eliminated 690 += VEC_length (operand_entry_t, *ops) - 1; 691 VEC_free (operand_entry_t, heap, *ops); 692 *ops = NULL; 693 VEC_safe_push (operand_entry_t, heap, *ops, oelast); 694 return; 695 } 696 } 697 else if (integer_onep (oelast->op)) 698 { 699 if (VEC_length (operand_entry_t, *ops) != 1) 700 { 701 if (dump_file && (dump_flags & TDF_DETAILS)) 702 fprintf (dump_file, "Found * 1, removing\n"); 703 VEC_pop (operand_entry_t, *ops); 704 reassociate_stats.ops_eliminated++; 705 return; 706 } 707 } 708 break; 709 case BIT_XOR_EXPR: 710 case PLUS_EXPR: 711 case MINUS_EXPR: 712 if (integer_zerop (oelast->op)) 713 { 714 if (VEC_length (operand_entry_t, *ops) != 1) 715 { 716 if (dump_file && (dump_flags & TDF_DETAILS)) 717 fprintf (dump_file, "Found [|^+] 0, removing\n"); 718 VEC_pop (operand_entry_t, *ops); 719 reassociate_stats.ops_eliminated++; 720 return; 721 } 722 } 723 break; 724 default: 725 break; 726 } 727 } 728} 729 730/* Perform various identities and other optimizations on the list of 731 operand entries, stored in OPS. The tree code for the binary 732 operation between all the operands is OPCODE. */ 733 734static void 735optimize_ops_list (enum tree_code opcode, 736 VEC (operand_entry_t, heap) **ops) 737{ 738 unsigned int length = VEC_length (operand_entry_t, *ops); 739 unsigned int i; 740 operand_entry_t oe; 741 operand_entry_t oelast = NULL; 742 bool iterate = false; 743 744 if (length == 1) 745 return; 746 747 oelast = VEC_last (operand_entry_t, *ops); 748 749 /* If the last two are constants, pop the constants off, merge them 750 and try the next two. */ 751 if (oelast->rank == 0 && is_gimple_min_invariant (oelast->op)) 752 { 753 operand_entry_t oelm1 = VEC_index (operand_entry_t, *ops, length - 2); 754 755 if (oelm1->rank == 0 756 && is_gimple_min_invariant (oelm1->op) 757 && lang_hooks.types_compatible_p (TREE_TYPE (oelm1->op), 758 TREE_TYPE (oelast->op))) 759 { 760 tree folded = fold_binary (opcode, TREE_TYPE (oelm1->op), 761 oelm1->op, oelast->op); 762 763 if (folded && is_gimple_min_invariant (folded)) 764 { 765 if (dump_file && (dump_flags & TDF_DETAILS)) 766 fprintf (dump_file, "Merging constants\n"); 767 768 VEC_pop (operand_entry_t, *ops); 769 VEC_pop (operand_entry_t, *ops); 770 771 add_to_ops_vec (ops, folded); 772 reassociate_stats.constants_eliminated++; 773 774 optimize_ops_list (opcode, ops); 775 return; 776 } 777 } 778 } 779 780 eliminate_using_constants (opcode, ops); 781 oelast = NULL; 782 783 for (i = 0; VEC_iterate (operand_entry_t, *ops, i, oe);) 784 { 785 bool done = false; 786 787 if (eliminate_not_pairs (opcode, ops, i, oe)) 788 return; 789 if (eliminate_duplicate_pair (opcode, ops, &done, i, oe, oelast) 790 || (!done && eliminate_plus_minus_pair (opcode, ops, i, oe))) 791 { 792 if (done) 793 return; 794 iterate = true; 795 oelast = NULL; 796 continue; 797 } 798 oelast = oe; 799 i++; 800 } 801 802 length = VEC_length (operand_entry_t, *ops); 803 oelast = VEC_last (operand_entry_t, *ops); 804 805 if (iterate) 806 optimize_ops_list (opcode, ops); 807} 808 809/* Return true if OPERAND is defined by a PHI node which uses the LHS 810 of STMT in it's operands. This is also known as a "destructive 811 update" operation. */ 812 813static bool 814is_phi_for_stmt (tree stmt, tree operand) 815{ 816 tree def_stmt; 817 tree lhs = TREE_OPERAND (stmt, 0); 818 use_operand_p arg_p; 819 ssa_op_iter i; 820 821 if (TREE_CODE (operand) != SSA_NAME) 822 return false; 823 824 def_stmt = SSA_NAME_DEF_STMT (operand); 825 if (TREE_CODE (def_stmt) != PHI_NODE) 826 return false; 827 828 FOR_EACH_PHI_ARG (arg_p, def_stmt, i, SSA_OP_USE) 829 if (lhs == USE_FROM_PTR (arg_p)) 830 return true; 831 return false; 832} 833 834/* Recursively rewrite our linearized statements so that the operators 835 match those in OPS[OPINDEX], putting the computation in rank 836 order. */ 837 838static void 839rewrite_expr_tree (tree stmt, unsigned int opindex, 840 VEC(operand_entry_t, heap) * ops) 841{ 842 tree rhs = TREE_OPERAND (stmt, 1); 843 operand_entry_t oe; 844 845 /* If we have three operands left, then we want to make sure the one 846 that gets the double binary op are the ones with the same rank. 847 848 The alternative we try is to see if this is a destructive 849 update style statement, which is like: 850 b = phi (a, ...) 851 a = c + b; 852 In that case, we want to use the destructive update form to 853 expose the possible vectorizer sum reduction opportunity. 854 In that case, the third operand will be the phi node. 855 856 We could, of course, try to be better as noted above, and do a 857 lot of work to try to find these opportunities in >3 operand 858 cases, but it is unlikely to be worth it. */ 859 if (opindex + 3 == VEC_length (operand_entry_t, ops)) 860 { 861 operand_entry_t oe1, oe2, oe3; 862 863 oe1 = VEC_index (operand_entry_t, ops, opindex); 864 oe2 = VEC_index (operand_entry_t, ops, opindex + 1); 865 oe3 = VEC_index (operand_entry_t, ops, opindex + 2); 866 867 if ((oe1->rank == oe2->rank 868 && oe2->rank != oe3->rank) 869 || (is_phi_for_stmt (stmt, oe3->op) 870 && !is_phi_for_stmt (stmt, oe1->op) 871 && !is_phi_for_stmt (stmt, oe2->op))) 872 { 873 struct operand_entry temp = *oe3; 874 oe3->op = oe1->op; 875 oe3->rank = oe1->rank; 876 oe1->op = temp.op; 877 oe1->rank= temp.rank; 878 } 879 } 880 881 /* The final recursion case for this function is that you have 882 exactly two operations left. 883 If we had one exactly one op in the entire list to start with, we 884 would have never called this function, and the tail recursion 885 rewrites them one at a time. */ 886 if (opindex + 2 == VEC_length (operand_entry_t, ops)) 887 { 888 operand_entry_t oe1, oe2; 889 890 oe1 = VEC_index (operand_entry_t, ops, opindex); 891 oe2 = VEC_index (operand_entry_t, ops, opindex + 1); 892 893 if (TREE_OPERAND (rhs, 0) != oe1->op 894 || TREE_OPERAND (rhs, 1) != oe2->op) 895 { 896 897 if (dump_file && (dump_flags & TDF_DETAILS)) 898 { 899 fprintf (dump_file, "Transforming "); 900 print_generic_expr (dump_file, rhs, 0); 901 } 902 903 TREE_OPERAND (rhs, 0) = oe1->op; 904 TREE_OPERAND (rhs, 1) = oe2->op; 905 update_stmt (stmt); 906 907 if (dump_file && (dump_flags & TDF_DETAILS)) 908 { 909 fprintf (dump_file, " into "); 910 print_generic_stmt (dump_file, rhs, 0); 911 } 912 913 } 914 return; 915 } 916 917 /* If we hit here, we should have 3 or more ops left. */ 918 gcc_assert (opindex + 2 < VEC_length (operand_entry_t, ops)); 919 920 /* Rewrite the next operator. */ 921 oe = VEC_index (operand_entry_t, ops, opindex); 922 923 if (oe->op != TREE_OPERAND (rhs, 1)) 924 { 925 926 if (dump_file && (dump_flags & TDF_DETAILS)) 927 { 928 fprintf (dump_file, "Transforming "); 929 print_generic_expr (dump_file, rhs, 0); 930 } 931 932 TREE_OPERAND (rhs, 1) = oe->op; 933 update_stmt (stmt); 934 935 if (dump_file && (dump_flags & TDF_DETAILS)) 936 { 937 fprintf (dump_file, " into "); 938 print_generic_stmt (dump_file, rhs, 0); 939 } 940 } 941 /* Recurse on the LHS of the binary operator, which is guaranteed to 942 be the non-leaf side. */ 943 rewrite_expr_tree (SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0)), 944 opindex + 1, ops); 945} 946 947/* Transform STMT, which is really (A +B) + (C + D) into the left 948 linear form, ((A+B)+C)+D. 949 Recurse on D if necessary. */ 950 951static void 952linearize_expr (tree stmt) 953{ 954 block_stmt_iterator bsinow, bsirhs; 955 tree rhs = TREE_OPERAND (stmt, 1); 956 enum tree_code rhscode = TREE_CODE (rhs); 957 tree binrhs = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 1)); 958 tree binlhs = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0)); 959 tree newbinrhs = NULL_TREE; 960 961 gcc_assert (is_reassociable_op (binlhs, TREE_CODE (rhs)) 962 && is_reassociable_op (binrhs, TREE_CODE (rhs))); 963 964 bsinow = bsi_for_stmt (stmt); 965 bsirhs = bsi_for_stmt (binrhs); 966 bsi_move_before (&bsirhs, &bsinow); 967 968 TREE_OPERAND (rhs, 1) = TREE_OPERAND (TREE_OPERAND (binrhs, 1), 0); 969 if (TREE_CODE (TREE_OPERAND (rhs, 1)) == SSA_NAME) 970 newbinrhs = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 1)); 971 TREE_OPERAND (TREE_OPERAND (binrhs, 1), 0) = TREE_OPERAND (binlhs, 0); 972 TREE_OPERAND (rhs, 0) = TREE_OPERAND (binrhs, 0); 973 974 if (dump_file && (dump_flags & TDF_DETAILS)) 975 { 976 fprintf (dump_file, "Linearized: "); 977 print_generic_stmt (dump_file, rhs, 0); 978 } 979 980 reassociate_stats.linearized++; 981 update_stmt (binrhs); 982 update_stmt (binlhs); 983 update_stmt (stmt); 984 TREE_VISITED (binrhs) = 1; 985 TREE_VISITED (binlhs) = 1; 986 TREE_VISITED (stmt) = 1; 987 988 /* Tail recurse on the new rhs if it still needs reassociation. */ 989 if (newbinrhs && is_reassociable_op (newbinrhs, rhscode)) 990 linearize_expr (stmt); 991 992} 993 994/* If LHS has a single immediate use that is a MODIFY_EXPR, return 995 it. Otherwise, return NULL. */ 996 997static tree 998get_single_immediate_use (tree lhs) 999{ 1000 use_operand_p immuse; 1001 tree immusestmt; 1002 1003 if (TREE_CODE (lhs) == SSA_NAME 1004 && single_imm_use (lhs, &immuse, &immusestmt)) 1005 { 1006 if (TREE_CODE (immusestmt) == RETURN_EXPR) 1007 immusestmt = TREE_OPERAND (immusestmt, 0); 1008 if (TREE_CODE (immusestmt) == MODIFY_EXPR) 1009 return immusestmt; 1010 } 1011 return NULL_TREE; 1012} 1013static VEC(tree, heap) *broken_up_subtracts; 1014 1015 1016/* Recursively negate the value of TONEGATE, and return the SSA_NAME 1017 representing the negated value. Insertions of any necessary 1018 instructions go before BSI. 1019 This function is recursive in that, if you hand it "a_5" as the 1020 value to negate, and a_5 is defined by "a_5 = b_3 + b_4", it will 1021 transform b_3 + b_4 into a_5 = -b_3 + -b_4. */ 1022 1023static tree 1024negate_value (tree tonegate, block_stmt_iterator *bsi) 1025{ 1026 tree negatedef = tonegate; 1027 tree resultofnegate; 1028 1029 if (TREE_CODE (tonegate) == SSA_NAME) 1030 negatedef = SSA_NAME_DEF_STMT (tonegate); 1031 1032 /* If we are trying to negate a name, defined by an add, negate the 1033 add operands instead. */ 1034 if (TREE_CODE (tonegate) == SSA_NAME 1035 && TREE_CODE (negatedef) == MODIFY_EXPR 1036 && TREE_CODE (TREE_OPERAND (negatedef, 0)) == SSA_NAME 1037 && has_single_use (TREE_OPERAND (negatedef, 0)) 1038 && TREE_CODE (TREE_OPERAND (negatedef, 1)) == PLUS_EXPR) 1039 { 1040 block_stmt_iterator bsi; 1041 tree binop = TREE_OPERAND (negatedef, 1); 1042 1043 bsi = bsi_for_stmt (negatedef); 1044 TREE_OPERAND (binop, 0) = negate_value (TREE_OPERAND (binop, 0), 1045 &bsi); 1046 bsi = bsi_for_stmt (negatedef); 1047 TREE_OPERAND (binop, 1) = negate_value (TREE_OPERAND (binop, 1), 1048 &bsi); 1049 update_stmt (negatedef); 1050 return TREE_OPERAND (negatedef, 0); 1051 } 1052 1053 tonegate = fold_build1 (NEGATE_EXPR, TREE_TYPE (tonegate), tonegate); 1054 resultofnegate = force_gimple_operand_bsi (bsi, tonegate, true, 1055 NULL_TREE); 1056 VEC_safe_push (tree, heap, broken_up_subtracts, resultofnegate); 1057 return resultofnegate; 1058 1059} 1060 1061/* Return true if we should break up the subtract in STMT into an add 1062 with negate. This is true when we the subtract operands are really 1063 adds, or the subtract itself is used in an add expression. In 1064 either case, breaking up the subtract into an add with negate 1065 exposes the adds to reassociation. */ 1066 1067static bool 1068should_break_up_subtract (tree stmt) 1069{ 1070 1071 tree lhs = TREE_OPERAND (stmt, 0); 1072 tree rhs = TREE_OPERAND (stmt, 1); 1073 tree binlhs = TREE_OPERAND (rhs, 0); 1074 tree binrhs = TREE_OPERAND (rhs, 1); 1075 tree immusestmt; 1076 1077 if (TREE_CODE (binlhs) == SSA_NAME 1078 && is_reassociable_op (SSA_NAME_DEF_STMT (binlhs), PLUS_EXPR)) 1079 return true; 1080 1081 if (TREE_CODE (binrhs) == SSA_NAME 1082 && is_reassociable_op (SSA_NAME_DEF_STMT (binrhs), PLUS_EXPR)) 1083 return true; 1084 1085 if (TREE_CODE (lhs) == SSA_NAME 1086 && (immusestmt = get_single_immediate_use (lhs)) 1087 && TREE_CODE (TREE_OPERAND (immusestmt, 1)) == PLUS_EXPR) 1088 return true; 1089 return false; 1090 1091} 1092 1093/* Transform STMT from A - B into A + -B. */ 1094 1095static void 1096break_up_subtract (tree stmt, block_stmt_iterator *bsi) 1097{ 1098 tree rhs = TREE_OPERAND (stmt, 1); 1099 1100 if (dump_file && (dump_flags & TDF_DETAILS)) 1101 { 1102 fprintf (dump_file, "Breaking up subtract "); 1103 print_generic_stmt (dump_file, stmt, 0); 1104 } 1105 1106 TREE_SET_CODE (TREE_OPERAND (stmt, 1), PLUS_EXPR); 1107 TREE_OPERAND (rhs, 1) = negate_value (TREE_OPERAND (rhs, 1), bsi); 1108 1109 update_stmt (stmt); 1110} 1111 1112/* Recursively linearize a binary expression that is the RHS of STMT. 1113 Place the operands of the expression tree in the vector named OPS. */ 1114 1115static void 1116linearize_expr_tree (VEC(operand_entry_t, heap) **ops, tree stmt) 1117{ 1118 block_stmt_iterator bsinow, bsilhs; 1119 tree rhs = TREE_OPERAND (stmt, 1); 1120 tree binrhs = TREE_OPERAND (rhs, 1); 1121 tree binlhs = TREE_OPERAND (rhs, 0); 1122 tree binlhsdef, binrhsdef; 1123 bool binlhsisreassoc = false; 1124 bool binrhsisreassoc = false; 1125 enum tree_code rhscode = TREE_CODE (rhs); 1126 1127 TREE_VISITED (stmt) = 1; 1128 1129 if (TREE_CODE (binlhs) == SSA_NAME) 1130 { 1131 binlhsdef = SSA_NAME_DEF_STMT (binlhs); 1132 binlhsisreassoc = is_reassociable_op (binlhsdef, rhscode); 1133 } 1134 1135 if (TREE_CODE (binrhs) == SSA_NAME) 1136 { 1137 binrhsdef = SSA_NAME_DEF_STMT (binrhs); 1138 binrhsisreassoc = is_reassociable_op (binrhsdef, rhscode); 1139 } 1140 1141 /* If the LHS is not reassociable, but the RHS is, we need to swap 1142 them. If neither is reassociable, there is nothing we can do, so 1143 just put them in the ops vector. If the LHS is reassociable, 1144 linearize it. If both are reassociable, then linearize the RHS 1145 and the LHS. */ 1146 1147 if (!binlhsisreassoc) 1148 { 1149 tree temp; 1150 1151 if (!binrhsisreassoc) 1152 { 1153 add_to_ops_vec (ops, binrhs); 1154 add_to_ops_vec (ops, binlhs); 1155 return; 1156 } 1157 1158 if (dump_file && (dump_flags & TDF_DETAILS)) 1159 { 1160 fprintf (dump_file, "swapping operands of "); 1161 print_generic_expr (dump_file, stmt, 0); 1162 } 1163 1164 swap_tree_operands (stmt, &TREE_OPERAND (rhs, 0), 1165 &TREE_OPERAND (rhs, 1)); 1166 update_stmt (stmt); 1167 1168 if (dump_file && (dump_flags & TDF_DETAILS)) 1169 { 1170 fprintf (dump_file, " is now "); 1171 print_generic_stmt (dump_file, stmt, 0); 1172 } 1173 1174 /* We want to make it so the lhs is always the reassociative op, 1175 so swap. */ 1176 temp = binlhs; 1177 binlhs = binrhs; 1178 binrhs = temp; 1179 } 1180 else if (binrhsisreassoc) 1181 { 1182 linearize_expr (stmt); 1183 gcc_assert (rhs == TREE_OPERAND (stmt, 1)); 1184 binlhs = TREE_OPERAND (rhs, 0); 1185 binrhs = TREE_OPERAND (rhs, 1); 1186 } 1187 1188 gcc_assert (TREE_CODE (binrhs) != SSA_NAME 1189 || !is_reassociable_op (SSA_NAME_DEF_STMT (binrhs), rhscode)); 1190 bsinow = bsi_for_stmt (stmt); 1191 bsilhs = bsi_for_stmt (SSA_NAME_DEF_STMT (binlhs)); 1192 bsi_move_before (&bsilhs, &bsinow); 1193 linearize_expr_tree (ops, SSA_NAME_DEF_STMT (binlhs)); 1194 add_to_ops_vec (ops, binrhs); 1195} 1196 1197/* Repropagate the negates back into subtracts, since no other pass 1198 currently does it. */ 1199 1200static void 1201repropagate_negates (void) 1202{ 1203 unsigned int i = 0; 1204 tree negate; 1205 1206 for (i = 0; VEC_iterate (tree, broken_up_subtracts, i, negate); i++) 1207 { 1208 tree user = get_single_immediate_use (negate); 1209 1210 /* The negate operand can be either operand of a PLUS_EXPR 1211 (it can be the LHS if the RHS is a constant for example). 1212 1213 Force the negate operand to the RHS of the PLUS_EXPR, then 1214 transform the PLUS_EXPR into a MINUS_EXPR. */ 1215 if (user 1216 && TREE_CODE (user) == MODIFY_EXPR 1217 && TREE_CODE (TREE_OPERAND (user, 1)) == PLUS_EXPR) 1218 { 1219 tree rhs = TREE_OPERAND (user, 1); 1220 1221 /* If the negated operand appears on the LHS of the 1222 PLUS_EXPR, exchange the operands of the PLUS_EXPR 1223 to force the negated operand to the RHS of the PLUS_EXPR. */ 1224 if (TREE_OPERAND (TREE_OPERAND (user, 1), 0) == negate) 1225 { 1226 tree temp = TREE_OPERAND (rhs, 0); 1227 TREE_OPERAND (rhs, 0) = TREE_OPERAND (rhs, 1); 1228 TREE_OPERAND (rhs, 1) = temp; 1229 } 1230 1231 /* Now transform the PLUS_EXPR into a MINUS_EXPR and replace 1232 the RHS of the PLUS_EXPR with the operand of the NEGATE_EXPR. */ 1233 if (TREE_OPERAND (TREE_OPERAND (user, 1), 1) == negate) 1234 { 1235 TREE_SET_CODE (rhs, MINUS_EXPR); 1236 TREE_OPERAND (rhs, 1) = get_unary_op (negate, NEGATE_EXPR); 1237 update_stmt (user); 1238 } 1239 } 1240 } 1241} 1242 1243/* Break up subtract operations in block BB. 1244 1245 We do this top down because we don't know whether the subtract is 1246 part of a possible chain of reassociation except at the top. 1247 1248 IE given 1249 d = f + g 1250 c = a + e 1251 b = c - d 1252 q = b - r 1253 k = t - q 1254 1255 we want to break up k = t - q, but we won't until we've transformed q 1256 = b - r, which won't be broken up until we transform b = c - d. */ 1257 1258static void 1259break_up_subtract_bb (basic_block bb) 1260{ 1261 block_stmt_iterator bsi; 1262 basic_block son; 1263 1264 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 1265 { 1266 tree stmt = bsi_stmt (bsi); 1267 1268 if (TREE_CODE (stmt) == MODIFY_EXPR) 1269 { 1270 tree lhs = TREE_OPERAND (stmt, 0); 1271 tree rhs = TREE_OPERAND (stmt, 1); 1272 1273 TREE_VISITED (stmt) = 0; 1274 /* If unsafe math optimizations we can do reassociation for 1275 non-integral types. */ 1276 if ((!INTEGRAL_TYPE_P (TREE_TYPE (lhs)) 1277 || !INTEGRAL_TYPE_P (TREE_TYPE (rhs))) 1278 && (!SCALAR_FLOAT_TYPE_P (TREE_TYPE (rhs)) 1279 || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(lhs)) 1280 || !flag_unsafe_math_optimizations)) 1281 continue; 1282 1283 /* Check for a subtract used only in an addition. If this 1284 is the case, transform it into add of a negate for better 1285 reassociation. IE transform C = A-B into C = A + -B if C 1286 is only used in an addition. */ 1287 if (TREE_CODE (rhs) == MINUS_EXPR) 1288 if (should_break_up_subtract (stmt)) 1289 break_up_subtract (stmt, &bsi); 1290 } 1291 } 1292 for (son = first_dom_son (CDI_DOMINATORS, bb); 1293 son; 1294 son = next_dom_son (CDI_DOMINATORS, son)) 1295 break_up_subtract_bb (son); 1296} 1297 1298/* Reassociate expressions in basic block BB and its post-dominator as 1299 children. */ 1300 1301static void 1302reassociate_bb (basic_block bb) 1303{ 1304 block_stmt_iterator bsi; 1305 basic_block son; 1306 1307 for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi)) 1308 { 1309 tree stmt = bsi_stmt (bsi); 1310 1311 if (TREE_CODE (stmt) == MODIFY_EXPR) 1312 { 1313 tree lhs = TREE_OPERAND (stmt, 0); 1314 tree rhs = TREE_OPERAND (stmt, 1); 1315 1316 /* If this was part of an already processed tree, we don't 1317 need to touch it again. */ 1318 if (TREE_VISITED (stmt)) 1319 continue; 1320 1321 /* If unsafe math optimizations we can do reassociation for 1322 non-integral types. */ 1323 if ((!INTEGRAL_TYPE_P (TREE_TYPE (lhs)) 1324 || !INTEGRAL_TYPE_P (TREE_TYPE (rhs))) 1325 && (!SCALAR_FLOAT_TYPE_P (TREE_TYPE (rhs)) 1326 || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(lhs)) 1327 || !flag_unsafe_math_optimizations)) 1328 continue; 1329 1330 if (associative_tree_code (TREE_CODE (rhs))) 1331 { 1332 VEC(operand_entry_t, heap) *ops = NULL; 1333 1334 /* There may be no immediate uses left by the time we 1335 get here because we may have eliminated them all. */ 1336 if (TREE_CODE (lhs) == SSA_NAME && has_zero_uses (lhs)) 1337 continue; 1338 1339 TREE_VISITED (stmt) = 1; 1340 linearize_expr_tree (&ops, stmt); 1341 qsort (VEC_address (operand_entry_t, ops), 1342 VEC_length (operand_entry_t, ops), 1343 sizeof (operand_entry_t), 1344 sort_by_operand_rank); 1345 optimize_ops_list (TREE_CODE (rhs), &ops); 1346 1347 if (VEC_length (operand_entry_t, ops) == 1) 1348 { 1349 if (dump_file && (dump_flags & TDF_DETAILS)) 1350 { 1351 fprintf (dump_file, "Transforming "); 1352 print_generic_expr (dump_file, rhs, 0); 1353 } 1354 TREE_OPERAND (stmt, 1) = VEC_last (operand_entry_t, ops)->op; 1355 update_stmt (stmt); 1356 1357 if (dump_file && (dump_flags & TDF_DETAILS)) 1358 { 1359 fprintf (dump_file, " into "); 1360 print_generic_stmt (dump_file, 1361 TREE_OPERAND (stmt, 1), 0); 1362 } 1363 } 1364 else 1365 { 1366 rewrite_expr_tree (stmt, 0, ops); 1367 } 1368 1369 VEC_free (operand_entry_t, heap, ops); 1370 } 1371 } 1372 } 1373 for (son = first_dom_son (CDI_POST_DOMINATORS, bb); 1374 son; 1375 son = next_dom_son (CDI_POST_DOMINATORS, son)) 1376 reassociate_bb (son); 1377} 1378 1379void dump_ops_vector (FILE *file, VEC (operand_entry_t, heap) *ops); 1380void debug_ops_vector (VEC (operand_entry_t, heap) *ops); 1381 1382/* Dump the operand entry vector OPS to FILE. */ 1383 1384void 1385dump_ops_vector (FILE *file, VEC (operand_entry_t, heap) *ops) 1386{ 1387 operand_entry_t oe; 1388 unsigned int i; 1389 1390 for (i = 0; VEC_iterate (operand_entry_t, ops, i, oe); i++) 1391 { 1392 fprintf (file, "Op %d -> rank: %d, tree: ", i, oe->rank); 1393 print_generic_stmt (file, oe->op, 0); 1394 } 1395} 1396 1397/* Dump the operand entry vector OPS to STDERR. */ 1398 1399void 1400debug_ops_vector (VEC (operand_entry_t, heap) *ops) 1401{ 1402 dump_ops_vector (stderr, ops); 1403} 1404 1405static void 1406do_reassoc (void) 1407{ 1408 break_up_subtract_bb (ENTRY_BLOCK_PTR); 1409 reassociate_bb (EXIT_BLOCK_PTR); 1410} 1411 1412/* Initialize the reassociation pass. */ 1413 1414static void 1415init_reassoc (void) 1416{ 1417 int i; 1418 unsigned int rank = 2; 1419 tree param; 1420 int *bbs = XNEWVEC (int, last_basic_block + 1); 1421 1422 memset (&reassociate_stats, 0, sizeof (reassociate_stats)); 1423 1424 operand_entry_pool = create_alloc_pool ("operand entry pool", 1425 sizeof (struct operand_entry), 30); 1426 1427 /* Reverse RPO (Reverse Post Order) will give us something where 1428 deeper loops come later. */ 1429 pre_and_rev_post_order_compute (NULL, bbs, false); 1430 bb_rank = XCNEWVEC (unsigned int, last_basic_block + 1); 1431 1432 operand_rank = htab_create (511, operand_entry_hash, 1433 operand_entry_eq, 0); 1434 1435 /* Give each argument a distinct rank. */ 1436 for (param = DECL_ARGUMENTS (current_function_decl); 1437 param; 1438 param = TREE_CHAIN (param)) 1439 { 1440 if (default_def (param) != NULL) 1441 { 1442 tree def = default_def (param); 1443 insert_operand_rank (def, ++rank); 1444 } 1445 } 1446 1447 /* Give the chain decl a distinct rank. */ 1448 if (cfun->static_chain_decl != NULL) 1449 { 1450 tree def = default_def (cfun->static_chain_decl); 1451 if (def != NULL) 1452 insert_operand_rank (def, ++rank); 1453 } 1454 1455 /* Set up rank for each BB */ 1456 for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; i++) 1457 bb_rank[bbs[i]] = ++rank << 16; 1458 1459 free (bbs); 1460 calculate_dominance_info (CDI_DOMINATORS); 1461 calculate_dominance_info (CDI_POST_DOMINATORS); 1462 broken_up_subtracts = NULL; 1463} 1464 1465/* Cleanup after the reassociation pass, and print stats if 1466 requested. */ 1467 1468static void 1469fini_reassoc (void) 1470{ 1471 1472 if (dump_file && (dump_flags & TDF_STATS)) 1473 { 1474 fprintf (dump_file, "Reassociation stats:\n"); 1475 fprintf (dump_file, "Linearized: %d\n", 1476 reassociate_stats.linearized); 1477 fprintf (dump_file, "Constants eliminated: %d\n", 1478 reassociate_stats.constants_eliminated); 1479 fprintf (dump_file, "Ops eliminated: %d\n", 1480 reassociate_stats.ops_eliminated); 1481 fprintf (dump_file, "Statements rewritten: %d\n", 1482 reassociate_stats.rewritten); 1483 } 1484 htab_delete (operand_rank); 1485 1486 free_alloc_pool (operand_entry_pool); 1487 free (bb_rank); 1488 VEC_free (tree, heap, broken_up_subtracts); 1489 free_dominance_info (CDI_POST_DOMINATORS); 1490} 1491 1492/* Gate and execute functions for Reassociation. */ 1493 1494static unsigned int 1495execute_reassoc (void) 1496{ 1497 init_reassoc (); 1498 1499 do_reassoc (); 1500 repropagate_negates (); 1501 1502 fini_reassoc (); 1503 return 0; 1504} 1505 1506struct tree_opt_pass pass_reassoc = 1507{ 1508 "reassoc", /* name */ 1509 NULL, /* gate */ 1510 execute_reassoc, /* execute */ 1511 NULL, /* sub */ 1512 NULL, /* next */ 1513 0, /* static_pass_number */ 1514 TV_TREE_REASSOC, /* tv_id */ 1515 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ 1516 0, /* properties_provided */ 1517 0, /* properties_destroyed */ 1518 0, /* todo_flags_start */ 1519 TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */ 1520 0 /* letter */ 1521}; 1522