1 /* Reassociation for trees. 2 Copyright (C) 2005, 2007, 2008, 2009, 2010, 2011 3 Free Software Foundation, Inc. 4 Contributed by Daniel Berlin <dan@dberlin.org> 5 6 This file is part of GCC. 7 8 GCC is free software; you can redistribute it and/or modify 9 it under the terms of the GNU General Public License as published by 10 the Free Software Foundation; either version 3, or (at your option) 11 any later version. 12 13 GCC is distributed in the hope that it will be useful, 14 but WITHOUT ANY WARRANTY; without even the implied warranty of 15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 GNU General Public License for more details. 17 18 You should have received a copy of the GNU General Public License 19 along with GCC; see the file COPYING3. If not see 20 <http://www.gnu.org/licenses/>. */ 21 22 #include "config.h" 23 #include "system.h" 24 #include "coretypes.h" 25 #include "tm.h" 26 #include "tree.h" 27 #include "basic-block.h" 28 #include "tree-pretty-print.h" 29 #include "gimple-pretty-print.h" 30 #include "tree-inline.h" 31 #include "tree-flow.h" 32 #include "gimple.h" 33 #include "tree-dump.h" 34 #include "timevar.h" 35 #include "tree-iterator.h" 36 #include "tree-pass.h" 37 #include "alloc-pool.h" 38 #include "vec.h" 39 #include "langhooks.h" 40 #include "pointer-set.h" 41 #include "cfgloop.h" 42 #include "flags.h" 43 #include "target.h" 44 #include "params.h" 45 #include "diagnostic-core.h" 46 47 /* This is a simple global reassociation pass. It is, in part, based 48 on the LLVM pass of the same name (They do some things more/less 49 than we do, in different orders, etc). 50 51 It consists of five steps: 52 53 1. Breaking up subtract operations into addition + negate, where 54 it would promote the reassociation of adds. 55 56 2. Left linearization of the expression trees, so that (A+B)+(C+D) 57 becomes (((A+B)+C)+D), which is easier for us to rewrite later. 58 During linearization, we place the operands of the binary 59 expressions into a vector of operand_entry_t 60 61 3. Optimization of the operand lists, eliminating things like a + 62 -a, a & a, etc. 63 64 4. Rewrite the expression trees we linearized and optimized so 65 they are in proper rank order. 66 67 5. Repropagate negates, as nothing else will clean it up ATM. 68 69 A bit of theory on #4, since nobody seems to write anything down 70 about why it makes sense to do it the way they do it: 71 72 We could do this much nicer theoretically, but don't (for reasons 73 explained after how to do it theoretically nice :P). 74 75 In order to promote the most redundancy elimination, you want 76 binary expressions whose operands are the same rank (or 77 preferably, the same value) exposed to the redundancy eliminator, 78 for possible elimination. 79 80 So the way to do this if we really cared, is to build the new op 81 tree from the leaves to the roots, merging as you go, and putting the 82 new op on the end of the worklist, until you are left with one 83 thing on the worklist. 84 85 IE if you have to rewrite the following set of operands (listed with 86 rank in parentheses), with opcode PLUS_EXPR: 87 88 a (1), b (1), c (1), d (2), e (2) 89 90 91 We start with our merge worklist empty, and the ops list with all of 92 those on it. 93 94 You want to first merge all leaves of the same rank, as much as 95 possible. 96 97 So first build a binary op of 98 99 mergetmp = a + b, and put "mergetmp" on the merge worklist. 100 101 Because there is no three operand form of PLUS_EXPR, c is not going to 102 be exposed to redundancy elimination as a rank 1 operand. 103 104 So you might as well throw it on the merge worklist (you could also 105 consider it to now be a rank two operand, and merge it with d and e, 106 but in this case, you then have evicted e from a binary op. So at 107 least in this situation, you can't win.) 108 109 Then build a binary op of d + e 110 mergetmp2 = d + e 111 112 and put mergetmp2 on the merge worklist. 113 114 so merge worklist = {mergetmp, c, mergetmp2} 115 116 Continue building binary ops of these operations until you have only 117 one operation left on the worklist. 118 119 So we have 120 121 build binary op 122 mergetmp3 = mergetmp + c 123 124 worklist = {mergetmp2, mergetmp3} 125 126 mergetmp4 = mergetmp2 + mergetmp3 127 128 worklist = {mergetmp4} 129 130 because we have one operation left, we can now just set the original 131 statement equal to the result of that operation. 132 133 This will at least expose a + b and d + e to redundancy elimination 134 as binary operations. 135 136 For extra points, you can reuse the old statements to build the 137 mergetmps, since you shouldn't run out. 138 139 So why don't we do this? 140 141 Because it's expensive, and rarely will help. Most trees we are 142 reassociating have 3 or less ops. If they have 2 ops, they already 143 will be written into a nice single binary op. If you have 3 ops, a 144 single simple check suffices to tell you whether the first two are of the 145 same rank. If so, you know to order it 146 147 mergetmp = op1 + op2 148 newstmt = mergetmp + op3 149 150 instead of 151 mergetmp = op2 + op3 152 newstmt = mergetmp + op1 153 154 If all three are of the same rank, you can't expose them all in a 155 single binary operator anyway, so the above is *still* the best you 156 can do. 157 158 Thus, this is what we do. When we have three ops left, we check to see 159 what order to put them in, and call it a day. As a nod to vector sum 160 reduction, we check if any of the ops are really a phi node that is a 161 destructive update for the associating op, and keep the destructive 162 update together for vector sum reduction recognition. */ 163 164 165 /* Statistics */ 166 static struct 167 { 168 int linearized; 169 int constants_eliminated; 170 int ops_eliminated; 171 int rewritten; 172 } reassociate_stats; 173 174 /* Operator, rank pair. */ 175 typedef struct operand_entry 176 { 177 unsigned int rank; 178 int id; 179 tree op; 180 } *operand_entry_t; 181 182 static alloc_pool operand_entry_pool; 183 184 /* This is used to assign a unique ID to each struct operand_entry 185 so that qsort results are identical on different hosts. */ 186 static int next_operand_entry_id; 187 188 /* Starting rank number for a given basic block, so that we can rank 189 operations using unmovable instructions in that BB based on the bb 190 depth. */ 191 static long *bb_rank; 192 193 /* Operand->rank hashtable. */ 194 static struct pointer_map_t *operand_rank; 195 196 /* Forward decls. */ 197 static long get_rank (tree); 198 199 200 /* Bias amount for loop-carried phis. We want this to be larger than 201 the depth of any reassociation tree we can see, but not larger than 202 the rank difference between two blocks. */ 203 #define PHI_LOOP_BIAS (1 << 15) 204 205 /* Rank assigned to a phi statement. If STMT is a loop-carried phi of 206 an innermost loop, and the phi has only a single use which is inside 207 the loop, then the rank is the block rank of the loop latch plus an 208 extra bias for the loop-carried dependence. This causes expressions 209 calculated into an accumulator variable to be independent for each 210 iteration of the loop. If STMT is some other phi, the rank is the 211 block rank of its containing block. */ 212 static long 213 phi_rank (gimple stmt) 214 { 215 basic_block bb = gimple_bb (stmt); 216 struct loop *father = bb->loop_father; 217 tree res; 218 unsigned i; 219 use_operand_p use; 220 gimple use_stmt; 221 222 /* We only care about real loops (those with a latch). */ 223 if (!father->latch) 224 return bb_rank[bb->index]; 225 226 /* Interesting phis must be in headers of innermost loops. */ 227 if (bb != father->header 228 || father->inner) 229 return bb_rank[bb->index]; 230 231 /* Ignore virtual SSA_NAMEs. */ 232 res = gimple_phi_result (stmt); 233 if (!is_gimple_reg (SSA_NAME_VAR (res))) 234 return bb_rank[bb->index]; 235 236 /* The phi definition must have a single use, and that use must be 237 within the loop. Otherwise this isn't an accumulator pattern. */ 238 if (!single_imm_use (res, &use, &use_stmt) 239 || gimple_bb (use_stmt)->loop_father != father) 240 return bb_rank[bb->index]; 241 242 /* Look for phi arguments from within the loop. If found, bias this phi. */ 243 for (i = 0; i < gimple_phi_num_args (stmt); i++) 244 { 245 tree arg = gimple_phi_arg_def (stmt, i); 246 if (TREE_CODE (arg) == SSA_NAME 247 && !SSA_NAME_IS_DEFAULT_DEF (arg)) 248 { 249 gimple def_stmt = SSA_NAME_DEF_STMT (arg); 250 if (gimple_bb (def_stmt)->loop_father == father) 251 return bb_rank[father->latch->index] + PHI_LOOP_BIAS; 252 } 253 } 254 255 /* Must be an uninteresting phi. */ 256 return bb_rank[bb->index]; 257 } 258 259 /* If EXP is an SSA_NAME defined by a PHI statement that represents a 260 loop-carried dependence of an innermost loop, return TRUE; else 261 return FALSE. */ 262 static bool 263 loop_carried_phi (tree exp) 264 { 265 gimple phi_stmt; 266 long block_rank; 267 268 if (TREE_CODE (exp) != SSA_NAME 269 || SSA_NAME_IS_DEFAULT_DEF (exp)) 270 return false; 271 272 phi_stmt = SSA_NAME_DEF_STMT (exp); 273 274 if (gimple_code (SSA_NAME_DEF_STMT (exp)) != GIMPLE_PHI) 275 return false; 276 277 /* Non-loop-carried phis have block rank. Loop-carried phis have 278 an additional bias added in. If this phi doesn't have block rank, 279 it's biased and should not be propagated. */ 280 block_rank = bb_rank[gimple_bb (phi_stmt)->index]; 281 282 if (phi_rank (phi_stmt) != block_rank) 283 return true; 284 285 return false; 286 } 287 288 /* Return the maximum of RANK and the rank that should be propagated 289 from expression OP. For most operands, this is just the rank of OP. 290 For loop-carried phis, the value is zero to avoid undoing the bias 291 in favor of the phi. */ 292 static long 293 propagate_rank (long rank, tree op) 294 { 295 long op_rank; 296 297 if (loop_carried_phi (op)) 298 return rank; 299 300 op_rank = get_rank (op); 301 302 return MAX (rank, op_rank); 303 } 304 305 /* Look up the operand rank structure for expression E. */ 306 307 static inline long 308 find_operand_rank (tree e) 309 { 310 void **slot = pointer_map_contains (operand_rank, e); 311 return slot ? (long) (intptr_t) *slot : -1; 312 } 313 314 /* Insert {E,RANK} into the operand rank hashtable. */ 315 316 static inline void 317 insert_operand_rank (tree e, long rank) 318 { 319 void **slot; 320 gcc_assert (rank > 0); 321 slot = pointer_map_insert (operand_rank, e); 322 gcc_assert (!*slot); 323 *slot = (void *) (intptr_t) rank; 324 } 325 326 /* Given an expression E, return the rank of the expression. */ 327 328 static long 329 get_rank (tree e) 330 { 331 /* Constants have rank 0. */ 332 if (is_gimple_min_invariant (e)) 333 return 0; 334 335 /* SSA_NAME's have the rank of the expression they are the result 336 of. 337 For globals and uninitialized values, the rank is 0. 338 For function arguments, use the pre-setup rank. 339 For PHI nodes, stores, asm statements, etc, we use the rank of 340 the BB. 341 For simple operations, the rank is the maximum rank of any of 342 its operands, or the bb_rank, whichever is less. 343 I make no claims that this is optimal, however, it gives good 344 results. */ 345 346 /* We make an exception to the normal ranking system to break 347 dependences of accumulator variables in loops. Suppose we 348 have a simple one-block loop containing: 349 350 x_1 = phi(x_0, x_2) 351 b = a + x_1 352 c = b + d 353 x_2 = c + e 354 355 As shown, each iteration of the calculation into x is fully 356 dependent upon the iteration before it. We would prefer to 357 see this in the form: 358 359 x_1 = phi(x_0, x_2) 360 b = a + d 361 c = b + e 362 x_2 = c + x_1 363 364 If the loop is unrolled, the calculations of b and c from 365 different iterations can be interleaved. 366 367 To obtain this result during reassociation, we bias the rank 368 of the phi definition x_1 upward, when it is recognized as an 369 accumulator pattern. The artificial rank causes it to be 370 added last, providing the desired independence. */ 371 372 if (TREE_CODE (e) == SSA_NAME) 373 { 374 gimple stmt; 375 long rank; 376 int i, n; 377 tree op; 378 379 if (TREE_CODE (SSA_NAME_VAR (e)) == PARM_DECL 380 && SSA_NAME_IS_DEFAULT_DEF (e)) 381 return find_operand_rank (e); 382 383 stmt = SSA_NAME_DEF_STMT (e); 384 if (gimple_bb (stmt) == NULL) 385 return 0; 386 387 if (gimple_code (stmt) == GIMPLE_PHI) 388 return phi_rank (stmt); 389 390 if (!is_gimple_assign (stmt) 391 || gimple_vdef (stmt)) 392 return bb_rank[gimple_bb (stmt)->index]; 393 394 /* If we already have a rank for this expression, use that. */ 395 rank = find_operand_rank (e); 396 if (rank != -1) 397 return rank; 398 399 /* Otherwise, find the maximum rank for the operands. As an 400 exception, remove the bias from loop-carried phis when propagating 401 the rank so that dependent operations are not also biased. */ 402 rank = 0; 403 if (gimple_assign_single_p (stmt)) 404 { 405 tree rhs = gimple_assign_rhs1 (stmt); 406 n = TREE_OPERAND_LENGTH (rhs); 407 if (n == 0) 408 rank = propagate_rank (rank, rhs); 409 else 410 { 411 for (i = 0; i < n; i++) 412 { 413 op = TREE_OPERAND (rhs, i); 414 415 if (op != NULL_TREE) 416 rank = propagate_rank (rank, op); 417 } 418 } 419 } 420 else 421 { 422 n = gimple_num_ops (stmt); 423 for (i = 1; i < n; i++) 424 { 425 op = gimple_op (stmt, i); 426 gcc_assert (op); 427 rank = propagate_rank (rank, op); 428 } 429 } 430 431 if (dump_file && (dump_flags & TDF_DETAILS)) 432 { 433 fprintf (dump_file, "Rank for "); 434 print_generic_expr (dump_file, e, 0); 435 fprintf (dump_file, " is %ld\n", (rank + 1)); 436 } 437 438 /* Note the rank in the hashtable so we don't recompute it. */ 439 insert_operand_rank (e, (rank + 1)); 440 return (rank + 1); 441 } 442 443 /* Globals, etc, are rank 0 */ 444 return 0; 445 } 446 447 DEF_VEC_P(operand_entry_t); 448 DEF_VEC_ALLOC_P(operand_entry_t, heap); 449 450 /* We want integer ones to end up last no matter what, since they are 451 the ones we can do the most with. */ 452 #define INTEGER_CONST_TYPE 1 << 3 453 #define FLOAT_CONST_TYPE 1 << 2 454 #define OTHER_CONST_TYPE 1 << 1 455 456 /* Classify an invariant tree into integer, float, or other, so that 457 we can sort them to be near other constants of the same type. */ 458 static inline int 459 constant_type (tree t) 460 { 461 if (INTEGRAL_TYPE_P (TREE_TYPE (t))) 462 return INTEGER_CONST_TYPE; 463 else if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (t))) 464 return FLOAT_CONST_TYPE; 465 else 466 return OTHER_CONST_TYPE; 467 } 468 469 /* qsort comparison function to sort operand entries PA and PB by rank 470 so that the sorted array is ordered by rank in decreasing order. */ 471 static int 472 sort_by_operand_rank (const void *pa, const void *pb) 473 { 474 const operand_entry_t oea = *(const operand_entry_t *)pa; 475 const operand_entry_t oeb = *(const operand_entry_t *)pb; 476 477 /* It's nicer for optimize_expression if constants that are likely 478 to fold when added/multiplied//whatever are put next to each 479 other. Since all constants have rank 0, order them by type. */ 480 if (oeb->rank == 0 && oea->rank == 0) 481 { 482 if (constant_type (oeb->op) != constant_type (oea->op)) 483 return constant_type (oeb->op) - constant_type (oea->op); 484 else 485 /* To make sorting result stable, we use unique IDs to determine 486 order. */ 487 return oeb->id - oea->id; 488 } 489 490 /* Lastly, make sure the versions that are the same go next to each 491 other. We use SSA_NAME_VERSION because it's stable. */ 492 if ((oeb->rank - oea->rank == 0) 493 && TREE_CODE (oea->op) == SSA_NAME 494 && TREE_CODE (oeb->op) == SSA_NAME) 495 { 496 if (SSA_NAME_VERSION (oeb->op) != SSA_NAME_VERSION (oea->op)) 497 return SSA_NAME_VERSION (oeb->op) - SSA_NAME_VERSION (oea->op); 498 else 499 return oeb->id - oea->id; 500 } 501 502 if (oeb->rank != oea->rank) 503 return oeb->rank - oea->rank; 504 else 505 return oeb->id - oea->id; 506 } 507 508 /* Add an operand entry to *OPS for the tree operand OP. */ 509 510 static void 511 add_to_ops_vec (VEC(operand_entry_t, heap) **ops, tree op) 512 { 513 operand_entry_t oe = (operand_entry_t) pool_alloc (operand_entry_pool); 514 515 oe->op = op; 516 oe->rank = get_rank (op); 517 oe->id = next_operand_entry_id++; 518 VEC_safe_push (operand_entry_t, heap, *ops, oe); 519 } 520 521 /* Return true if STMT is reassociable operation containing a binary 522 operation with tree code CODE, and is inside LOOP. */ 523 524 static bool 525 is_reassociable_op (gimple stmt, enum tree_code code, struct loop *loop) 526 { 527 basic_block bb = gimple_bb (stmt); 528 529 if (gimple_bb (stmt) == NULL) 530 return false; 531 532 if (!flow_bb_inside_loop_p (loop, bb)) 533 return false; 534 535 if (is_gimple_assign (stmt) 536 && gimple_assign_rhs_code (stmt) == code 537 && has_single_use (gimple_assign_lhs (stmt))) 538 return true; 539 540 return false; 541 } 542 543 544 /* Given NAME, if NAME is defined by a unary operation OPCODE, return the 545 operand of the negate operation. Otherwise, return NULL. */ 546 547 static tree 548 get_unary_op (tree name, enum tree_code opcode) 549 { 550 gimple stmt = SSA_NAME_DEF_STMT (name); 551 552 if (!is_gimple_assign (stmt)) 553 return NULL_TREE; 554 555 if (gimple_assign_rhs_code (stmt) == opcode) 556 return gimple_assign_rhs1 (stmt); 557 return NULL_TREE; 558 } 559 560 /* If CURR and LAST are a pair of ops that OPCODE allows us to 561 eliminate through equivalences, do so, remove them from OPS, and 562 return true. Otherwise, return false. */ 563 564 static bool 565 eliminate_duplicate_pair (enum tree_code opcode, 566 VEC (operand_entry_t, heap) **ops, 567 bool *all_done, 568 unsigned int i, 569 operand_entry_t curr, 570 operand_entry_t last) 571 { 572 573 /* If we have two of the same op, and the opcode is & |, min, or max, 574 we can eliminate one of them. 575 If we have two of the same op, and the opcode is ^, we can 576 eliminate both of them. */ 577 578 if (last && last->op == curr->op) 579 { 580 switch (opcode) 581 { 582 case MAX_EXPR: 583 case MIN_EXPR: 584 case BIT_IOR_EXPR: 585 case BIT_AND_EXPR: 586 if (dump_file && (dump_flags & TDF_DETAILS)) 587 { 588 fprintf (dump_file, "Equivalence: "); 589 print_generic_expr (dump_file, curr->op, 0); 590 fprintf (dump_file, " [&|minmax] "); 591 print_generic_expr (dump_file, last->op, 0); 592 fprintf (dump_file, " -> "); 593 print_generic_stmt (dump_file, last->op, 0); 594 } 595 596 VEC_ordered_remove (operand_entry_t, *ops, i); 597 reassociate_stats.ops_eliminated ++; 598 599 return true; 600 601 case BIT_XOR_EXPR: 602 if (dump_file && (dump_flags & TDF_DETAILS)) 603 { 604 fprintf (dump_file, "Equivalence: "); 605 print_generic_expr (dump_file, curr->op, 0); 606 fprintf (dump_file, " ^ "); 607 print_generic_expr (dump_file, last->op, 0); 608 fprintf (dump_file, " -> nothing\n"); 609 } 610 611 reassociate_stats.ops_eliminated += 2; 612 613 if (VEC_length (operand_entry_t, *ops) == 2) 614 { 615 VEC_free (operand_entry_t, heap, *ops); 616 *ops = NULL; 617 add_to_ops_vec (ops, build_zero_cst (TREE_TYPE (last->op))); 618 *all_done = true; 619 } 620 else 621 { 622 VEC_ordered_remove (operand_entry_t, *ops, i-1); 623 VEC_ordered_remove (operand_entry_t, *ops, i-1); 624 } 625 626 return true; 627 628 default: 629 break; 630 } 631 } 632 return false; 633 } 634 635 static VEC(tree, heap) *plus_negates; 636 637 /* If OPCODE is PLUS_EXPR, CURR->OP is a negate expression or a bitwise not 638 expression, look in OPS for a corresponding positive operation to cancel 639 it out. If we find one, remove the other from OPS, replace 640 OPS[CURRINDEX] with 0 or -1, respectively, and return true. Otherwise, 641 return false. */ 642 643 static bool 644 eliminate_plus_minus_pair (enum tree_code opcode, 645 VEC (operand_entry_t, heap) **ops, 646 unsigned int currindex, 647 operand_entry_t curr) 648 { 649 tree negateop; 650 tree notop; 651 unsigned int i; 652 operand_entry_t oe; 653 654 if (opcode != PLUS_EXPR || TREE_CODE (curr->op) != SSA_NAME) 655 return false; 656 657 negateop = get_unary_op (curr->op, NEGATE_EXPR); 658 notop = get_unary_op (curr->op, BIT_NOT_EXPR); 659 if (negateop == NULL_TREE && notop == NULL_TREE) 660 return false; 661 662 /* Any non-negated version will have a rank that is one less than 663 the current rank. So once we hit those ranks, if we don't find 664 one, we can stop. */ 665 666 for (i = currindex + 1; 667 VEC_iterate (operand_entry_t, *ops, i, oe) 668 && oe->rank >= curr->rank - 1 ; 669 i++) 670 { 671 if (oe->op == negateop) 672 { 673 674 if (dump_file && (dump_flags & TDF_DETAILS)) 675 { 676 fprintf (dump_file, "Equivalence: "); 677 print_generic_expr (dump_file, negateop, 0); 678 fprintf (dump_file, " + -"); 679 print_generic_expr (dump_file, oe->op, 0); 680 fprintf (dump_file, " -> 0\n"); 681 } 682 683 VEC_ordered_remove (operand_entry_t, *ops, i); 684 add_to_ops_vec (ops, build_zero_cst (TREE_TYPE (oe->op))); 685 VEC_ordered_remove (operand_entry_t, *ops, currindex); 686 reassociate_stats.ops_eliminated ++; 687 688 return true; 689 } 690 else if (oe->op == notop) 691 { 692 tree op_type = TREE_TYPE (oe->op); 693 694 if (dump_file && (dump_flags & TDF_DETAILS)) 695 { 696 fprintf (dump_file, "Equivalence: "); 697 print_generic_expr (dump_file, notop, 0); 698 fprintf (dump_file, " + ~"); 699 print_generic_expr (dump_file, oe->op, 0); 700 fprintf (dump_file, " -> -1\n"); 701 } 702 703 VEC_ordered_remove (operand_entry_t, *ops, i); 704 add_to_ops_vec (ops, build_int_cst_type (op_type, -1)); 705 VEC_ordered_remove (operand_entry_t, *ops, currindex); 706 reassociate_stats.ops_eliminated ++; 707 708 return true; 709 } 710 } 711 712 /* CURR->OP is a negate expr in a plus expr: save it for later 713 inspection in repropagate_negates(). */ 714 if (negateop != NULL_TREE) 715 VEC_safe_push (tree, heap, plus_negates, curr->op); 716 717 return false; 718 } 719 720 /* If OPCODE is BIT_IOR_EXPR, BIT_AND_EXPR, and, CURR->OP is really a 721 bitwise not expression, look in OPS for a corresponding operand to 722 cancel it out. If we find one, remove the other from OPS, replace 723 OPS[CURRINDEX] with 0, and return true. Otherwise, return 724 false. */ 725 726 static bool 727 eliminate_not_pairs (enum tree_code opcode, 728 VEC (operand_entry_t, heap) **ops, 729 unsigned int currindex, 730 operand_entry_t curr) 731 { 732 tree notop; 733 unsigned int i; 734 operand_entry_t oe; 735 736 if ((opcode != BIT_IOR_EXPR && opcode != BIT_AND_EXPR) 737 || TREE_CODE (curr->op) != SSA_NAME) 738 return false; 739 740 notop = get_unary_op (curr->op, BIT_NOT_EXPR); 741 if (notop == NULL_TREE) 742 return false; 743 744 /* Any non-not version will have a rank that is one less than 745 the current rank. So once we hit those ranks, if we don't find 746 one, we can stop. */ 747 748 for (i = currindex + 1; 749 VEC_iterate (operand_entry_t, *ops, i, oe) 750 && oe->rank >= curr->rank - 1; 751 i++) 752 { 753 if (oe->op == notop) 754 { 755 if (dump_file && (dump_flags & TDF_DETAILS)) 756 { 757 fprintf (dump_file, "Equivalence: "); 758 print_generic_expr (dump_file, notop, 0); 759 if (opcode == BIT_AND_EXPR) 760 fprintf (dump_file, " & ~"); 761 else if (opcode == BIT_IOR_EXPR) 762 fprintf (dump_file, " | ~"); 763 print_generic_expr (dump_file, oe->op, 0); 764 if (opcode == BIT_AND_EXPR) 765 fprintf (dump_file, " -> 0\n"); 766 else if (opcode == BIT_IOR_EXPR) 767 fprintf (dump_file, " -> -1\n"); 768 } 769 770 if (opcode == BIT_AND_EXPR) 771 oe->op = build_zero_cst (TREE_TYPE (oe->op)); 772 else if (opcode == BIT_IOR_EXPR) 773 oe->op = build_low_bits_mask (TREE_TYPE (oe->op), 774 TYPE_PRECISION (TREE_TYPE (oe->op))); 775 776 reassociate_stats.ops_eliminated 777 += VEC_length (operand_entry_t, *ops) - 1; 778 VEC_free (operand_entry_t, heap, *ops); 779 *ops = NULL; 780 VEC_safe_push (operand_entry_t, heap, *ops, oe); 781 return true; 782 } 783 } 784 785 return false; 786 } 787 788 /* Use constant value that may be present in OPS to try to eliminate 789 operands. Note that this function is only really used when we've 790 eliminated ops for other reasons, or merged constants. Across 791 single statements, fold already does all of this, plus more. There 792 is little point in duplicating logic, so I've only included the 793 identities that I could ever construct testcases to trigger. */ 794 795 static void 796 eliminate_using_constants (enum tree_code opcode, 797 VEC(operand_entry_t, heap) **ops) 798 { 799 operand_entry_t oelast = VEC_last (operand_entry_t, *ops); 800 tree type = TREE_TYPE (oelast->op); 801 802 if (oelast->rank == 0 803 && (INTEGRAL_TYPE_P (type) || FLOAT_TYPE_P (type))) 804 { 805 switch (opcode) 806 { 807 case BIT_AND_EXPR: 808 if (integer_zerop (oelast->op)) 809 { 810 if (VEC_length (operand_entry_t, *ops) != 1) 811 { 812 if (dump_file && (dump_flags & TDF_DETAILS)) 813 fprintf (dump_file, "Found & 0, removing all other ops\n"); 814 815 reassociate_stats.ops_eliminated 816 += VEC_length (operand_entry_t, *ops) - 1; 817 818 VEC_free (operand_entry_t, heap, *ops); 819 *ops = NULL; 820 VEC_safe_push (operand_entry_t, heap, *ops, oelast); 821 return; 822 } 823 } 824 else if (integer_all_onesp (oelast->op)) 825 { 826 if (VEC_length (operand_entry_t, *ops) != 1) 827 { 828 if (dump_file && (dump_flags & TDF_DETAILS)) 829 fprintf (dump_file, "Found & -1, removing\n"); 830 VEC_pop (operand_entry_t, *ops); 831 reassociate_stats.ops_eliminated++; 832 } 833 } 834 break; 835 case BIT_IOR_EXPR: 836 if (integer_all_onesp (oelast->op)) 837 { 838 if (VEC_length (operand_entry_t, *ops) != 1) 839 { 840 if (dump_file && (dump_flags & TDF_DETAILS)) 841 fprintf (dump_file, "Found | -1, removing all other ops\n"); 842 843 reassociate_stats.ops_eliminated 844 += VEC_length (operand_entry_t, *ops) - 1; 845 846 VEC_free (operand_entry_t, heap, *ops); 847 *ops = NULL; 848 VEC_safe_push (operand_entry_t, heap, *ops, oelast); 849 return; 850 } 851 } 852 else if (integer_zerop (oelast->op)) 853 { 854 if (VEC_length (operand_entry_t, *ops) != 1) 855 { 856 if (dump_file && (dump_flags & TDF_DETAILS)) 857 fprintf (dump_file, "Found | 0, removing\n"); 858 VEC_pop (operand_entry_t, *ops); 859 reassociate_stats.ops_eliminated++; 860 } 861 } 862 break; 863 case MULT_EXPR: 864 if (integer_zerop (oelast->op) 865 || (FLOAT_TYPE_P (type) 866 && !HONOR_NANS (TYPE_MODE (type)) 867 && !HONOR_SIGNED_ZEROS (TYPE_MODE (type)) 868 && real_zerop (oelast->op))) 869 { 870 if (VEC_length (operand_entry_t, *ops) != 1) 871 { 872 if (dump_file && (dump_flags & TDF_DETAILS)) 873 fprintf (dump_file, "Found * 0, removing all other ops\n"); 874 875 reassociate_stats.ops_eliminated 876 += VEC_length (operand_entry_t, *ops) - 1; 877 VEC_free (operand_entry_t, heap, *ops); 878 *ops = NULL; 879 VEC_safe_push (operand_entry_t, heap, *ops, oelast); 880 return; 881 } 882 } 883 else if (integer_onep (oelast->op) 884 || (FLOAT_TYPE_P (type) 885 && !HONOR_SNANS (TYPE_MODE (type)) 886 && real_onep (oelast->op))) 887 { 888 if (VEC_length (operand_entry_t, *ops) != 1) 889 { 890 if (dump_file && (dump_flags & TDF_DETAILS)) 891 fprintf (dump_file, "Found * 1, removing\n"); 892 VEC_pop (operand_entry_t, *ops); 893 reassociate_stats.ops_eliminated++; 894 return; 895 } 896 } 897 break; 898 case BIT_XOR_EXPR: 899 case PLUS_EXPR: 900 case MINUS_EXPR: 901 if (integer_zerop (oelast->op) 902 || (FLOAT_TYPE_P (type) 903 && (opcode == PLUS_EXPR || opcode == MINUS_EXPR) 904 && fold_real_zero_addition_p (type, oelast->op, 905 opcode == MINUS_EXPR))) 906 { 907 if (VEC_length (operand_entry_t, *ops) != 1) 908 { 909 if (dump_file && (dump_flags & TDF_DETAILS)) 910 fprintf (dump_file, "Found [|^+] 0, removing\n"); 911 VEC_pop (operand_entry_t, *ops); 912 reassociate_stats.ops_eliminated++; 913 return; 914 } 915 } 916 break; 917 default: 918 break; 919 } 920 } 921 } 922 923 924 static void linearize_expr_tree (VEC(operand_entry_t, heap) **, gimple, 925 bool, bool); 926 927 /* Structure for tracking and counting operands. */ 928 typedef struct oecount_s { 929 int cnt; 930 int id; 931 enum tree_code oecode; 932 tree op; 933 } oecount; 934 935 DEF_VEC_O(oecount); 936 DEF_VEC_ALLOC_O(oecount,heap); 937 938 /* The heap for the oecount hashtable and the sorted list of operands. */ 939 static VEC (oecount, heap) *cvec; 940 941 /* Hash function for oecount. */ 942 943 static hashval_t 944 oecount_hash (const void *p) 945 { 946 const oecount *c = VEC_index (oecount, cvec, (size_t)p - 42); 947 return htab_hash_pointer (c->op) ^ (hashval_t)c->oecode; 948 } 949 950 /* Comparison function for oecount. */ 951 952 static int 953 oecount_eq (const void *p1, const void *p2) 954 { 955 const oecount *c1 = VEC_index (oecount, cvec, (size_t)p1 - 42); 956 const oecount *c2 = VEC_index (oecount, cvec, (size_t)p2 - 42); 957 return (c1->oecode == c2->oecode 958 && c1->op == c2->op); 959 } 960 961 /* Comparison function for qsort sorting oecount elements by count. */ 962 963 static int 964 oecount_cmp (const void *p1, const void *p2) 965 { 966 const oecount *c1 = (const oecount *)p1; 967 const oecount *c2 = (const oecount *)p2; 968 if (c1->cnt != c2->cnt) 969 return c1->cnt - c2->cnt; 970 else 971 /* If counts are identical, use unique IDs to stabilize qsort. */ 972 return c1->id - c2->id; 973 } 974 975 /* Walks the linear chain with result *DEF searching for an operation 976 with operand OP and code OPCODE removing that from the chain. *DEF 977 is updated if there is only one operand but no operation left. */ 978 979 static void 980 zero_one_operation (tree *def, enum tree_code opcode, tree op) 981 { 982 gimple stmt = SSA_NAME_DEF_STMT (*def); 983 984 do 985 { 986 tree name = gimple_assign_rhs1 (stmt); 987 988 /* If this is the operation we look for and one of the operands 989 is ours simply propagate the other operand into the stmts 990 single use. */ 991 if (gimple_assign_rhs_code (stmt) == opcode 992 && (name == op 993 || gimple_assign_rhs2 (stmt) == op)) 994 { 995 gimple use_stmt; 996 use_operand_p use; 997 gimple_stmt_iterator gsi; 998 if (name == op) 999 name = gimple_assign_rhs2 (stmt); 1000 gcc_assert (has_single_use (gimple_assign_lhs (stmt))); 1001 single_imm_use (gimple_assign_lhs (stmt), &use, &use_stmt); 1002 if (gimple_assign_lhs (stmt) == *def) 1003 *def = name; 1004 SET_USE (use, name); 1005 if (TREE_CODE (name) != SSA_NAME) 1006 update_stmt (use_stmt); 1007 gsi = gsi_for_stmt (stmt); 1008 gsi_remove (&gsi, true); 1009 release_defs (stmt); 1010 return; 1011 } 1012 1013 /* Continue walking the chain. */ 1014 gcc_assert (name != op 1015 && TREE_CODE (name) == SSA_NAME); 1016 stmt = SSA_NAME_DEF_STMT (name); 1017 } 1018 while (1); 1019 } 1020 1021 /* Builds one statement performing OP1 OPCODE OP2 using TMPVAR for 1022 the result. Places the statement after the definition of either 1023 OP1 or OP2. Returns the new statement. */ 1024 1025 static gimple 1026 build_and_add_sum (tree tmpvar, tree op1, tree op2, enum tree_code opcode) 1027 { 1028 gimple op1def = NULL, op2def = NULL; 1029 gimple_stmt_iterator gsi; 1030 tree op; 1031 gimple sum; 1032 1033 /* Create the addition statement. */ 1034 sum = gimple_build_assign_with_ops (opcode, tmpvar, op1, op2); 1035 op = make_ssa_name (tmpvar, sum); 1036 gimple_assign_set_lhs (sum, op); 1037 1038 /* Find an insertion place and insert. */ 1039 if (TREE_CODE (op1) == SSA_NAME) 1040 op1def = SSA_NAME_DEF_STMT (op1); 1041 if (TREE_CODE (op2) == SSA_NAME) 1042 op2def = SSA_NAME_DEF_STMT (op2); 1043 if ((!op1def || gimple_nop_p (op1def)) 1044 && (!op2def || gimple_nop_p (op2def))) 1045 { 1046 gsi = gsi_after_labels (single_succ (ENTRY_BLOCK_PTR)); 1047 gsi_insert_before (&gsi, sum, GSI_NEW_STMT); 1048 } 1049 else if ((!op1def || gimple_nop_p (op1def)) 1050 || (op2def && !gimple_nop_p (op2def) 1051 && stmt_dominates_stmt_p (op1def, op2def))) 1052 { 1053 if (gimple_code (op2def) == GIMPLE_PHI) 1054 { 1055 gsi = gsi_after_labels (gimple_bb (op2def)); 1056 gsi_insert_before (&gsi, sum, GSI_NEW_STMT); 1057 } 1058 else 1059 { 1060 if (!stmt_ends_bb_p (op2def)) 1061 { 1062 gsi = gsi_for_stmt (op2def); 1063 gsi_insert_after (&gsi, sum, GSI_NEW_STMT); 1064 } 1065 else 1066 { 1067 edge e; 1068 edge_iterator ei; 1069 1070 FOR_EACH_EDGE (e, ei, gimple_bb (op2def)->succs) 1071 if (e->flags & EDGE_FALLTHRU) 1072 gsi_insert_on_edge_immediate (e, sum); 1073 } 1074 } 1075 } 1076 else 1077 { 1078 if (gimple_code (op1def) == GIMPLE_PHI) 1079 { 1080 gsi = gsi_after_labels (gimple_bb (op1def)); 1081 gsi_insert_before (&gsi, sum, GSI_NEW_STMT); 1082 } 1083 else 1084 { 1085 if (!stmt_ends_bb_p (op1def)) 1086 { 1087 gsi = gsi_for_stmt (op1def); 1088 gsi_insert_after (&gsi, sum, GSI_NEW_STMT); 1089 } 1090 else 1091 { 1092 edge e; 1093 edge_iterator ei; 1094 1095 FOR_EACH_EDGE (e, ei, gimple_bb (op1def)->succs) 1096 if (e->flags & EDGE_FALLTHRU) 1097 gsi_insert_on_edge_immediate (e, sum); 1098 } 1099 } 1100 } 1101 update_stmt (sum); 1102 1103 return sum; 1104 } 1105 1106 /* Perform un-distribution of divisions and multiplications. 1107 A * X + B * X is transformed into (A + B) * X and A / X + B / X 1108 to (A + B) / X for real X. 1109 1110 The algorithm is organized as follows. 1111 1112 - First we walk the addition chain *OPS looking for summands that 1113 are defined by a multiplication or a real division. This results 1114 in the candidates bitmap with relevant indices into *OPS. 1115 1116 - Second we build the chains of multiplications or divisions for 1117 these candidates, counting the number of occurences of (operand, code) 1118 pairs in all of the candidates chains. 1119 1120 - Third we sort the (operand, code) pairs by number of occurence and 1121 process them starting with the pair with the most uses. 1122 1123 * For each such pair we walk the candidates again to build a 1124 second candidate bitmap noting all multiplication/division chains 1125 that have at least one occurence of (operand, code). 1126 1127 * We build an alternate addition chain only covering these 1128 candidates with one (operand, code) operation removed from their 1129 multiplication/division chain. 1130 1131 * The first candidate gets replaced by the alternate addition chain 1132 multiplied/divided by the operand. 1133 1134 * All candidate chains get disabled for further processing and 1135 processing of (operand, code) pairs continues. 1136 1137 The alternate addition chains built are re-processed by the main 1138 reassociation algorithm which allows optimizing a * x * y + b * y * x 1139 to (a + b ) * x * y in one invocation of the reassociation pass. */ 1140 1141 static bool 1142 undistribute_ops_list (enum tree_code opcode, 1143 VEC (operand_entry_t, heap) **ops, struct loop *loop) 1144 { 1145 unsigned int length = VEC_length (operand_entry_t, *ops); 1146 operand_entry_t oe1; 1147 unsigned i, j; 1148 sbitmap candidates, candidates2; 1149 unsigned nr_candidates, nr_candidates2; 1150 sbitmap_iterator sbi0; 1151 VEC (operand_entry_t, heap) **subops; 1152 htab_t ctable; 1153 bool changed = false; 1154 int next_oecount_id = 0; 1155 1156 if (length <= 1 1157 || opcode != PLUS_EXPR) 1158 return false; 1159 1160 /* Build a list of candidates to process. */ 1161 candidates = sbitmap_alloc (length); 1162 sbitmap_zero (candidates); 1163 nr_candidates = 0; 1164 FOR_EACH_VEC_ELT (operand_entry_t, *ops, i, oe1) 1165 { 1166 enum tree_code dcode; 1167 gimple oe1def; 1168 1169 if (TREE_CODE (oe1->op) != SSA_NAME) 1170 continue; 1171 oe1def = SSA_NAME_DEF_STMT (oe1->op); 1172 if (!is_gimple_assign (oe1def)) 1173 continue; 1174 dcode = gimple_assign_rhs_code (oe1def); 1175 if ((dcode != MULT_EXPR 1176 && dcode != RDIV_EXPR) 1177 || !is_reassociable_op (oe1def, dcode, loop)) 1178 continue; 1179 1180 SET_BIT (candidates, i); 1181 nr_candidates++; 1182 } 1183 1184 if (nr_candidates < 2) 1185 { 1186 sbitmap_free (candidates); 1187 return false; 1188 } 1189 1190 if (dump_file && (dump_flags & TDF_DETAILS)) 1191 { 1192 fprintf (dump_file, "searching for un-distribute opportunities "); 1193 print_generic_expr (dump_file, 1194 VEC_index (operand_entry_t, *ops, 1195 sbitmap_first_set_bit (candidates))->op, 0); 1196 fprintf (dump_file, " %d\n", nr_candidates); 1197 } 1198 1199 /* Build linearized sub-operand lists and the counting table. */ 1200 cvec = NULL; 1201 ctable = htab_create (15, oecount_hash, oecount_eq, NULL); 1202 subops = XCNEWVEC (VEC (operand_entry_t, heap) *, 1203 VEC_length (operand_entry_t, *ops)); 1204 EXECUTE_IF_SET_IN_SBITMAP (candidates, 0, i, sbi0) 1205 { 1206 gimple oedef; 1207 enum tree_code oecode; 1208 unsigned j; 1209 1210 oedef = SSA_NAME_DEF_STMT (VEC_index (operand_entry_t, *ops, i)->op); 1211 oecode = gimple_assign_rhs_code (oedef); 1212 linearize_expr_tree (&subops[i], oedef, 1213 associative_tree_code (oecode), false); 1214 1215 FOR_EACH_VEC_ELT (operand_entry_t, subops[i], j, oe1) 1216 { 1217 oecount c; 1218 void **slot; 1219 size_t idx; 1220 c.oecode = oecode; 1221 c.cnt = 1; 1222 c.id = next_oecount_id++; 1223 c.op = oe1->op; 1224 VEC_safe_push (oecount, heap, cvec, &c); 1225 idx = VEC_length (oecount, cvec) + 41; 1226 slot = htab_find_slot (ctable, (void *)idx, INSERT); 1227 if (!*slot) 1228 { 1229 *slot = (void *)idx; 1230 } 1231 else 1232 { 1233 VEC_pop (oecount, cvec); 1234 VEC_index (oecount, cvec, (size_t)*slot - 42)->cnt++; 1235 } 1236 } 1237 } 1238 htab_delete (ctable); 1239 1240 /* Sort the counting table. */ 1241 VEC_qsort (oecount, cvec, oecount_cmp); 1242 1243 if (dump_file && (dump_flags & TDF_DETAILS)) 1244 { 1245 oecount *c; 1246 fprintf (dump_file, "Candidates:\n"); 1247 FOR_EACH_VEC_ELT (oecount, cvec, j, c) 1248 { 1249 fprintf (dump_file, " %u %s: ", c->cnt, 1250 c->oecode == MULT_EXPR 1251 ? "*" : c->oecode == RDIV_EXPR ? "/" : "?"); 1252 print_generic_expr (dump_file, c->op, 0); 1253 fprintf (dump_file, "\n"); 1254 } 1255 } 1256 1257 /* Process the (operand, code) pairs in order of most occurence. */ 1258 candidates2 = sbitmap_alloc (length); 1259 while (!VEC_empty (oecount, cvec)) 1260 { 1261 oecount *c = VEC_last (oecount, cvec); 1262 if (c->cnt < 2) 1263 break; 1264 1265 /* Now collect the operands in the outer chain that contain 1266 the common operand in their inner chain. */ 1267 sbitmap_zero (candidates2); 1268 nr_candidates2 = 0; 1269 EXECUTE_IF_SET_IN_SBITMAP (candidates, 0, i, sbi0) 1270 { 1271 gimple oedef; 1272 enum tree_code oecode; 1273 unsigned j; 1274 tree op = VEC_index (operand_entry_t, *ops, i)->op; 1275 1276 /* If we undistributed in this chain already this may be 1277 a constant. */ 1278 if (TREE_CODE (op) != SSA_NAME) 1279 continue; 1280 1281 oedef = SSA_NAME_DEF_STMT (op); 1282 oecode = gimple_assign_rhs_code (oedef); 1283 if (oecode != c->oecode) 1284 continue; 1285 1286 FOR_EACH_VEC_ELT (operand_entry_t, subops[i], j, oe1) 1287 { 1288 if (oe1->op == c->op) 1289 { 1290 SET_BIT (candidates2, i); 1291 ++nr_candidates2; 1292 break; 1293 } 1294 } 1295 } 1296 1297 if (nr_candidates2 >= 2) 1298 { 1299 operand_entry_t oe1, oe2; 1300 tree tmpvar; 1301 gimple prod; 1302 int first = sbitmap_first_set_bit (candidates2); 1303 1304 /* Build the new addition chain. */ 1305 oe1 = VEC_index (operand_entry_t, *ops, first); 1306 if (dump_file && (dump_flags & TDF_DETAILS)) 1307 { 1308 fprintf (dump_file, "Building ("); 1309 print_generic_expr (dump_file, oe1->op, 0); 1310 } 1311 tmpvar = create_tmp_reg (TREE_TYPE (oe1->op), NULL); 1312 add_referenced_var (tmpvar); 1313 zero_one_operation (&oe1->op, c->oecode, c->op); 1314 EXECUTE_IF_SET_IN_SBITMAP (candidates2, first+1, i, sbi0) 1315 { 1316 gimple sum; 1317 oe2 = VEC_index (operand_entry_t, *ops, i); 1318 if (dump_file && (dump_flags & TDF_DETAILS)) 1319 { 1320 fprintf (dump_file, " + "); 1321 print_generic_expr (dump_file, oe2->op, 0); 1322 } 1323 zero_one_operation (&oe2->op, c->oecode, c->op); 1324 sum = build_and_add_sum (tmpvar, oe1->op, oe2->op, opcode); 1325 oe2->op = build_zero_cst (TREE_TYPE (oe2->op)); 1326 oe2->rank = 0; 1327 oe1->op = gimple_get_lhs (sum); 1328 } 1329 1330 /* Apply the multiplication/division. */ 1331 prod = build_and_add_sum (tmpvar, oe1->op, c->op, c->oecode); 1332 if (dump_file && (dump_flags & TDF_DETAILS)) 1333 { 1334 fprintf (dump_file, ") %s ", c->oecode == MULT_EXPR ? "*" : "/"); 1335 print_generic_expr (dump_file, c->op, 0); 1336 fprintf (dump_file, "\n"); 1337 } 1338 1339 /* Record it in the addition chain and disable further 1340 undistribution with this op. */ 1341 oe1->op = gimple_assign_lhs (prod); 1342 oe1->rank = get_rank (oe1->op); 1343 VEC_free (operand_entry_t, heap, subops[first]); 1344 1345 changed = true; 1346 } 1347 1348 VEC_pop (oecount, cvec); 1349 } 1350 1351 for (i = 0; i < VEC_length (operand_entry_t, *ops); ++i) 1352 VEC_free (operand_entry_t, heap, subops[i]); 1353 free (subops); 1354 VEC_free (oecount, heap, cvec); 1355 sbitmap_free (candidates); 1356 sbitmap_free (candidates2); 1357 1358 return changed; 1359 } 1360 1361 /* If OPCODE is BIT_IOR_EXPR or BIT_AND_EXPR and CURR is a comparison 1362 expression, examine the other OPS to see if any of them are comparisons 1363 of the same values, which we may be able to combine or eliminate. 1364 For example, we can rewrite (a < b) | (a == b) as (a <= b). */ 1365 1366 static bool 1367 eliminate_redundant_comparison (enum tree_code opcode, 1368 VEC (operand_entry_t, heap) **ops, 1369 unsigned int currindex, 1370 operand_entry_t curr) 1371 { 1372 tree op1, op2; 1373 enum tree_code lcode, rcode; 1374 gimple def1, def2; 1375 int i; 1376 operand_entry_t oe; 1377 1378 if (opcode != BIT_IOR_EXPR && opcode != BIT_AND_EXPR) 1379 return false; 1380 1381 /* Check that CURR is a comparison. */ 1382 if (TREE_CODE (curr->op) != SSA_NAME) 1383 return false; 1384 def1 = SSA_NAME_DEF_STMT (curr->op); 1385 if (!is_gimple_assign (def1)) 1386 return false; 1387 lcode = gimple_assign_rhs_code (def1); 1388 if (TREE_CODE_CLASS (lcode) != tcc_comparison) 1389 return false; 1390 op1 = gimple_assign_rhs1 (def1); 1391 op2 = gimple_assign_rhs2 (def1); 1392 1393 /* Now look for a similar comparison in the remaining OPS. */ 1394 for (i = currindex + 1; 1395 VEC_iterate (operand_entry_t, *ops, i, oe); 1396 i++) 1397 { 1398 tree t; 1399 1400 if (TREE_CODE (oe->op) != SSA_NAME) 1401 continue; 1402 def2 = SSA_NAME_DEF_STMT (oe->op); 1403 if (!is_gimple_assign (def2)) 1404 continue; 1405 rcode = gimple_assign_rhs_code (def2); 1406 if (TREE_CODE_CLASS (rcode) != tcc_comparison) 1407 continue; 1408 1409 /* If we got here, we have a match. See if we can combine the 1410 two comparisons. */ 1411 if (opcode == BIT_IOR_EXPR) 1412 t = maybe_fold_or_comparisons (lcode, op1, op2, 1413 rcode, gimple_assign_rhs1 (def2), 1414 gimple_assign_rhs2 (def2)); 1415 else 1416 t = maybe_fold_and_comparisons (lcode, op1, op2, 1417 rcode, gimple_assign_rhs1 (def2), 1418 gimple_assign_rhs2 (def2)); 1419 if (!t) 1420 continue; 1421 1422 /* maybe_fold_and_comparisons and maybe_fold_or_comparisons 1423 always give us a boolean_type_node value back. If the original 1424 BIT_AND_EXPR or BIT_IOR_EXPR was of a wider integer type, 1425 we need to convert. */ 1426 if (!useless_type_conversion_p (TREE_TYPE (curr->op), TREE_TYPE (t))) 1427 t = fold_convert (TREE_TYPE (curr->op), t); 1428 1429 if (TREE_CODE (t) != INTEGER_CST 1430 && !operand_equal_p (t, curr->op, 0)) 1431 { 1432 enum tree_code subcode; 1433 tree newop1, newop2; 1434 if (!COMPARISON_CLASS_P (t)) 1435 continue; 1436 extract_ops_from_tree (t, &subcode, &newop1, &newop2); 1437 STRIP_USELESS_TYPE_CONVERSION (newop1); 1438 STRIP_USELESS_TYPE_CONVERSION (newop2); 1439 if (!is_gimple_val (newop1) || !is_gimple_val (newop2)) 1440 continue; 1441 } 1442 1443 if (dump_file && (dump_flags & TDF_DETAILS)) 1444 { 1445 fprintf (dump_file, "Equivalence: "); 1446 print_generic_expr (dump_file, curr->op, 0); 1447 fprintf (dump_file, " %s ", op_symbol_code (opcode)); 1448 print_generic_expr (dump_file, oe->op, 0); 1449 fprintf (dump_file, " -> "); 1450 print_generic_expr (dump_file, t, 0); 1451 fprintf (dump_file, "\n"); 1452 } 1453 1454 /* Now we can delete oe, as it has been subsumed by the new combined 1455 expression t. */ 1456 VEC_ordered_remove (operand_entry_t, *ops, i); 1457 reassociate_stats.ops_eliminated ++; 1458 1459 /* If t is the same as curr->op, we're done. Otherwise we must 1460 replace curr->op with t. Special case is if we got a constant 1461 back, in which case we add it to the end instead of in place of 1462 the current entry. */ 1463 if (TREE_CODE (t) == INTEGER_CST) 1464 { 1465 VEC_ordered_remove (operand_entry_t, *ops, currindex); 1466 add_to_ops_vec (ops, t); 1467 } 1468 else if (!operand_equal_p (t, curr->op, 0)) 1469 { 1470 tree tmpvar; 1471 gimple sum; 1472 enum tree_code subcode; 1473 tree newop1; 1474 tree newop2; 1475 gcc_assert (COMPARISON_CLASS_P (t)); 1476 tmpvar = create_tmp_var (TREE_TYPE (t), NULL); 1477 add_referenced_var (tmpvar); 1478 extract_ops_from_tree (t, &subcode, &newop1, &newop2); 1479 STRIP_USELESS_TYPE_CONVERSION (newop1); 1480 STRIP_USELESS_TYPE_CONVERSION (newop2); 1481 gcc_checking_assert (is_gimple_val (newop1) 1482 && is_gimple_val (newop2)); 1483 sum = build_and_add_sum (tmpvar, newop1, newop2, subcode); 1484 curr->op = gimple_get_lhs (sum); 1485 } 1486 return true; 1487 } 1488 1489 return false; 1490 } 1491 1492 /* Perform various identities and other optimizations on the list of 1493 operand entries, stored in OPS. The tree code for the binary 1494 operation between all the operands is OPCODE. */ 1495 1496 static void 1497 optimize_ops_list (enum tree_code opcode, 1498 VEC (operand_entry_t, heap) **ops) 1499 { 1500 unsigned int length = VEC_length (operand_entry_t, *ops); 1501 unsigned int i; 1502 operand_entry_t oe; 1503 operand_entry_t oelast = NULL; 1504 bool iterate = false; 1505 1506 if (length == 1) 1507 return; 1508 1509 oelast = VEC_last (operand_entry_t, *ops); 1510 1511 /* If the last two are constants, pop the constants off, merge them 1512 and try the next two. */ 1513 if (oelast->rank == 0 && is_gimple_min_invariant (oelast->op)) 1514 { 1515 operand_entry_t oelm1 = VEC_index (operand_entry_t, *ops, length - 2); 1516 1517 if (oelm1->rank == 0 1518 && is_gimple_min_invariant (oelm1->op) 1519 && useless_type_conversion_p (TREE_TYPE (oelm1->op), 1520 TREE_TYPE (oelast->op))) 1521 { 1522 tree folded = fold_binary (opcode, TREE_TYPE (oelm1->op), 1523 oelm1->op, oelast->op); 1524 1525 if (folded && is_gimple_min_invariant (folded)) 1526 { 1527 if (dump_file && (dump_flags & TDF_DETAILS)) 1528 fprintf (dump_file, "Merging constants\n"); 1529 1530 VEC_pop (operand_entry_t, *ops); 1531 VEC_pop (operand_entry_t, *ops); 1532 1533 add_to_ops_vec (ops, folded); 1534 reassociate_stats.constants_eliminated++; 1535 1536 optimize_ops_list (opcode, ops); 1537 return; 1538 } 1539 } 1540 } 1541 1542 eliminate_using_constants (opcode, ops); 1543 oelast = NULL; 1544 1545 for (i = 0; VEC_iterate (operand_entry_t, *ops, i, oe);) 1546 { 1547 bool done = false; 1548 1549 if (eliminate_not_pairs (opcode, ops, i, oe)) 1550 return; 1551 if (eliminate_duplicate_pair (opcode, ops, &done, i, oe, oelast) 1552 || (!done && eliminate_plus_minus_pair (opcode, ops, i, oe)) 1553 || (!done && eliminate_redundant_comparison (opcode, ops, i, oe))) 1554 { 1555 if (done) 1556 return; 1557 iterate = true; 1558 oelast = NULL; 1559 continue; 1560 } 1561 oelast = oe; 1562 i++; 1563 } 1564 1565 length = VEC_length (operand_entry_t, *ops); 1566 oelast = VEC_last (operand_entry_t, *ops); 1567 1568 if (iterate) 1569 optimize_ops_list (opcode, ops); 1570 } 1571 1572 /* The following functions are subroutines to optimize_range_tests and allow 1573 it to try to change a logical combination of comparisons into a range 1574 test. 1575 1576 For example, both 1577 X == 2 || X == 5 || X == 3 || X == 4 1578 and 1579 X >= 2 && X <= 5 1580 are converted to 1581 (unsigned) (X - 2) <= 3 1582 1583 For more information see comments above fold_test_range in fold-const.c, 1584 this implementation is for GIMPLE. */ 1585 1586 struct range_entry 1587 { 1588 tree exp; 1589 tree low; 1590 tree high; 1591 bool in_p; 1592 bool strict_overflow_p; 1593 unsigned int idx, next; 1594 }; 1595 1596 /* This is similar to make_range in fold-const.c, but on top of 1597 GIMPLE instead of trees. */ 1598 1599 static void 1600 init_range_entry (struct range_entry *r, tree exp) 1601 { 1602 int in_p; 1603 tree low, high; 1604 bool is_bool, strict_overflow_p; 1605 1606 r->exp = NULL_TREE; 1607 r->in_p = false; 1608 r->strict_overflow_p = false; 1609 r->low = NULL_TREE; 1610 r->high = NULL_TREE; 1611 if (TREE_CODE (exp) != SSA_NAME || !INTEGRAL_TYPE_P (TREE_TYPE (exp))) 1612 return; 1613 1614 /* Start with simply saying "EXP != 0" and then look at the code of EXP 1615 and see if we can refine the range. Some of the cases below may not 1616 happen, but it doesn't seem worth worrying about this. We "continue" 1617 the outer loop when we've changed something; otherwise we "break" 1618 the switch, which will "break" the while. */ 1619 low = build_int_cst (TREE_TYPE (exp), 0); 1620 high = low; 1621 in_p = 0; 1622 strict_overflow_p = false; 1623 is_bool = false; 1624 if (TYPE_PRECISION (TREE_TYPE (exp)) == 1) 1625 { 1626 if (TYPE_UNSIGNED (TREE_TYPE (exp))) 1627 is_bool = true; 1628 else 1629 return; 1630 } 1631 else if (TREE_CODE (TREE_TYPE (exp)) == BOOLEAN_TYPE) 1632 is_bool = true; 1633 1634 while (1) 1635 { 1636 gimple stmt; 1637 enum tree_code code; 1638 tree arg0, arg1, exp_type; 1639 tree nexp; 1640 location_t loc; 1641 1642 if (TREE_CODE (exp) != SSA_NAME) 1643 break; 1644 1645 stmt = SSA_NAME_DEF_STMT (exp); 1646 if (!is_gimple_assign (stmt)) 1647 break; 1648 1649 code = gimple_assign_rhs_code (stmt); 1650 arg0 = gimple_assign_rhs1 (stmt); 1651 if (TREE_CODE (arg0) != SSA_NAME) 1652 break; 1653 arg1 = gimple_assign_rhs2 (stmt); 1654 exp_type = TREE_TYPE (exp); 1655 loc = gimple_location (stmt); 1656 switch (code) 1657 { 1658 case BIT_NOT_EXPR: 1659 if (TREE_CODE (TREE_TYPE (exp)) == BOOLEAN_TYPE) 1660 { 1661 in_p = !in_p; 1662 exp = arg0; 1663 continue; 1664 } 1665 break; 1666 case SSA_NAME: 1667 exp = arg0; 1668 continue; 1669 CASE_CONVERT: 1670 if (is_bool) 1671 goto do_default; 1672 if (TYPE_PRECISION (TREE_TYPE (arg0)) == 1) 1673 { 1674 if (TYPE_UNSIGNED (TREE_TYPE (arg0))) 1675 is_bool = true; 1676 else 1677 return; 1678 } 1679 else if (TREE_CODE (TREE_TYPE (arg0)) == BOOLEAN_TYPE) 1680 is_bool = true; 1681 goto do_default; 1682 case EQ_EXPR: 1683 case NE_EXPR: 1684 case LT_EXPR: 1685 case LE_EXPR: 1686 case GE_EXPR: 1687 case GT_EXPR: 1688 is_bool = true; 1689 /* FALLTHRU */ 1690 default: 1691 if (!is_bool) 1692 return; 1693 do_default: 1694 nexp = make_range_step (loc, code, arg0, arg1, exp_type, 1695 &low, &high, &in_p, 1696 &strict_overflow_p); 1697 if (nexp != NULL_TREE) 1698 { 1699 exp = nexp; 1700 gcc_assert (TREE_CODE (exp) == SSA_NAME); 1701 continue; 1702 } 1703 break; 1704 } 1705 break; 1706 } 1707 if (is_bool) 1708 { 1709 r->exp = exp; 1710 r->in_p = in_p; 1711 r->low = low; 1712 r->high = high; 1713 r->strict_overflow_p = strict_overflow_p; 1714 } 1715 } 1716 1717 /* Comparison function for qsort. Sort entries 1718 without SSA_NAME exp first, then with SSA_NAMEs sorted 1719 by increasing SSA_NAME_VERSION, and for the same SSA_NAMEs 1720 by increasing ->low and if ->low is the same, by increasing 1721 ->high. ->low == NULL_TREE means minimum, ->high == NULL_TREE 1722 maximum. */ 1723 1724 static int 1725 range_entry_cmp (const void *a, const void *b) 1726 { 1727 const struct range_entry *p = (const struct range_entry *) a; 1728 const struct range_entry *q = (const struct range_entry *) b; 1729 1730 if (p->exp != NULL_TREE && TREE_CODE (p->exp) == SSA_NAME) 1731 { 1732 if (q->exp != NULL_TREE && TREE_CODE (q->exp) == SSA_NAME) 1733 { 1734 /* Group range_entries for the same SSA_NAME together. */ 1735 if (SSA_NAME_VERSION (p->exp) < SSA_NAME_VERSION (q->exp)) 1736 return -1; 1737 else if (SSA_NAME_VERSION (p->exp) > SSA_NAME_VERSION (q->exp)) 1738 return 1; 1739 /* If ->low is different, NULL low goes first, then by 1740 ascending low. */ 1741 if (p->low != NULL_TREE) 1742 { 1743 if (q->low != NULL_TREE) 1744 { 1745 tree tem = fold_binary (LT_EXPR, boolean_type_node, 1746 p->low, q->low); 1747 if (tem && integer_onep (tem)) 1748 return -1; 1749 tem = fold_binary (GT_EXPR, boolean_type_node, 1750 p->low, q->low); 1751 if (tem && integer_onep (tem)) 1752 return 1; 1753 } 1754 else 1755 return 1; 1756 } 1757 else if (q->low != NULL_TREE) 1758 return -1; 1759 /* If ->high is different, NULL high goes last, before that by 1760 ascending high. */ 1761 if (p->high != NULL_TREE) 1762 { 1763 if (q->high != NULL_TREE) 1764 { 1765 tree tem = fold_binary (LT_EXPR, boolean_type_node, 1766 p->high, q->high); 1767 if (tem && integer_onep (tem)) 1768 return -1; 1769 tem = fold_binary (GT_EXPR, boolean_type_node, 1770 p->high, q->high); 1771 if (tem && integer_onep (tem)) 1772 return 1; 1773 } 1774 else 1775 return -1; 1776 } 1777 else if (p->high != NULL_TREE) 1778 return 1; 1779 /* If both ranges are the same, sort below by ascending idx. */ 1780 } 1781 else 1782 return 1; 1783 } 1784 else if (q->exp != NULL_TREE && TREE_CODE (q->exp) == SSA_NAME) 1785 return -1; 1786 1787 if (p->idx < q->idx) 1788 return -1; 1789 else 1790 { 1791 gcc_checking_assert (p->idx > q->idx); 1792 return 1; 1793 } 1794 } 1795 1796 /* Helper routine of optimize_range_test. 1797 [EXP, IN_P, LOW, HIGH, STRICT_OVERFLOW_P] is a merged range for 1798 RANGE and OTHERRANGE through OTHERRANGE + COUNT - 1 ranges, 1799 OPCODE and OPS are arguments of optimize_range_tests. Return 1800 true if the range merge has been successful. */ 1801 1802 static bool 1803 update_range_test (struct range_entry *range, struct range_entry *otherrange, 1804 unsigned int count, enum tree_code opcode, 1805 VEC (operand_entry_t, heap) **ops, tree exp, bool in_p, 1806 tree low, tree high, bool strict_overflow_p) 1807 { 1808 tree op = VEC_index (operand_entry_t, *ops, range->idx)->op; 1809 location_t loc = gimple_location (SSA_NAME_DEF_STMT (op)); 1810 tree tem = build_range_check (loc, TREE_TYPE (op), exp, in_p, low, high); 1811 enum warn_strict_overflow_code wc = WARN_STRICT_OVERFLOW_COMPARISON; 1812 gimple_stmt_iterator gsi; 1813 1814 if (tem == NULL_TREE) 1815 return false; 1816 1817 if (strict_overflow_p && issue_strict_overflow_warning (wc)) 1818 warning_at (loc, OPT_Wstrict_overflow, 1819 "assuming signed overflow does not occur " 1820 "when simplifying range test"); 1821 1822 if (dump_file && (dump_flags & TDF_DETAILS)) 1823 { 1824 struct range_entry *r; 1825 fprintf (dump_file, "Optimizing range tests "); 1826 print_generic_expr (dump_file, range->exp, 0); 1827 fprintf (dump_file, " %c[", range->in_p ? '+' : '-'); 1828 print_generic_expr (dump_file, range->low, 0); 1829 fprintf (dump_file, ", "); 1830 print_generic_expr (dump_file, range->high, 0); 1831 fprintf (dump_file, "]"); 1832 for (r = otherrange; r < otherrange + count; r++) 1833 { 1834 fprintf (dump_file, " and %c[", r->in_p ? '+' : '-'); 1835 print_generic_expr (dump_file, r->low, 0); 1836 fprintf (dump_file, ", "); 1837 print_generic_expr (dump_file, r->high, 0); 1838 fprintf (dump_file, "]"); 1839 } 1840 fprintf (dump_file, "\n into "); 1841 print_generic_expr (dump_file, tem, 0); 1842 fprintf (dump_file, "\n"); 1843 } 1844 1845 if (opcode == BIT_IOR_EXPR) 1846 tem = invert_truthvalue_loc (loc, tem); 1847 1848 tem = fold_convert_loc (loc, TREE_TYPE (op), tem); 1849 gsi = gsi_for_stmt (SSA_NAME_DEF_STMT (op)); 1850 tem = force_gimple_operand_gsi (&gsi, tem, true, NULL_TREE, true, 1851 GSI_SAME_STMT); 1852 1853 VEC_index (operand_entry_t, *ops, range->idx)->op = tem; 1854 range->exp = exp; 1855 range->low = low; 1856 range->high = high; 1857 range->in_p = in_p; 1858 range->strict_overflow_p = false; 1859 1860 for (range = otherrange; range < otherrange + count; range++) 1861 { 1862 VEC_index (operand_entry_t, *ops, range->idx)->op = error_mark_node; 1863 range->exp = NULL_TREE; 1864 } 1865 return true; 1866 } 1867 1868 /* Optimize range tests, similarly how fold_range_test optimizes 1869 it on trees. The tree code for the binary 1870 operation between all the operands is OPCODE. */ 1871 1872 static void 1873 optimize_range_tests (enum tree_code opcode, 1874 VEC (operand_entry_t, heap) **ops) 1875 { 1876 unsigned int length = VEC_length (operand_entry_t, *ops), i, j, first; 1877 operand_entry_t oe; 1878 struct range_entry *ranges; 1879 bool any_changes = false; 1880 1881 if (length == 1) 1882 return; 1883 1884 ranges = XNEWVEC (struct range_entry, length); 1885 for (i = 0; i < length; i++) 1886 { 1887 ranges[i].idx = i; 1888 init_range_entry (ranges + i, VEC_index (operand_entry_t, *ops, i)->op); 1889 /* For | invert it now, we will invert it again before emitting 1890 the optimized expression. */ 1891 if (opcode == BIT_IOR_EXPR) 1892 ranges[i].in_p = !ranges[i].in_p; 1893 } 1894 1895 qsort (ranges, length, sizeof (*ranges), range_entry_cmp); 1896 for (i = 0; i < length; i++) 1897 if (ranges[i].exp != NULL_TREE && TREE_CODE (ranges[i].exp) == SSA_NAME) 1898 break; 1899 1900 /* Try to merge ranges. */ 1901 for (first = i; i < length; i++) 1902 { 1903 tree low = ranges[i].low; 1904 tree high = ranges[i].high; 1905 int in_p = ranges[i].in_p; 1906 bool strict_overflow_p = ranges[i].strict_overflow_p; 1907 int update_fail_count = 0; 1908 1909 for (j = i + 1; j < length; j++) 1910 { 1911 if (ranges[i].exp != ranges[j].exp) 1912 break; 1913 if (!merge_ranges (&in_p, &low, &high, in_p, low, high, 1914 ranges[j].in_p, ranges[j].low, ranges[j].high)) 1915 break; 1916 strict_overflow_p |= ranges[j].strict_overflow_p; 1917 } 1918 1919 if (j == i + 1) 1920 continue; 1921 1922 if (update_range_test (ranges + i, ranges + i + 1, j - i - 1, opcode, 1923 ops, ranges[i].exp, in_p, low, high, 1924 strict_overflow_p)) 1925 { 1926 i = j - 1; 1927 any_changes = true; 1928 } 1929 /* Avoid quadratic complexity if all merge_ranges calls would succeed, 1930 while update_range_test would fail. */ 1931 else if (update_fail_count == 64) 1932 i = j - 1; 1933 else 1934 ++update_fail_count; 1935 } 1936 1937 /* Optimize X == CST1 || X == CST2 1938 if popcount (CST1 ^ CST2) == 1 into 1939 (X & ~(CST1 ^ CST2)) == (CST1 & ~(CST1 ^ CST2)). 1940 Similarly for ranges. E.g. 1941 X != 2 && X != 3 && X != 10 && X != 11 1942 will be transformed by the above loop into 1943 (X - 2U) <= 1U && (X - 10U) <= 1U 1944 and this loop can transform that into 1945 ((X & ~8) - 2U) <= 1U. */ 1946 for (i = first; i < length; i++) 1947 { 1948 tree lowi, highi, lowj, highj, type, lowxor, highxor, tem, exp; 1949 1950 if (ranges[i].exp == NULL_TREE || ranges[i].in_p) 1951 continue; 1952 type = TREE_TYPE (ranges[i].exp); 1953 if (!INTEGRAL_TYPE_P (type)) 1954 continue; 1955 lowi = ranges[i].low; 1956 if (lowi == NULL_TREE) 1957 lowi = TYPE_MIN_VALUE (type); 1958 highi = ranges[i].high; 1959 if (highi == NULL_TREE) 1960 continue; 1961 for (j = i + 1; j < length && j < i + 64; j++) 1962 { 1963 if (ranges[j].exp == NULL_TREE) 1964 continue; 1965 if (ranges[i].exp != ranges[j].exp) 1966 break; 1967 if (ranges[j].in_p) 1968 continue; 1969 lowj = ranges[j].low; 1970 if (lowj == NULL_TREE) 1971 continue; 1972 highj = ranges[j].high; 1973 if (highj == NULL_TREE) 1974 highj = TYPE_MAX_VALUE (type); 1975 tem = fold_binary (GT_EXPR, boolean_type_node, 1976 lowj, highi); 1977 if (tem == NULL_TREE || !integer_onep (tem)) 1978 continue; 1979 lowxor = fold_binary (BIT_XOR_EXPR, type, lowi, lowj); 1980 if (lowxor == NULL_TREE || TREE_CODE (lowxor) != INTEGER_CST) 1981 continue; 1982 gcc_checking_assert (!integer_zerop (lowxor)); 1983 tem = fold_binary (MINUS_EXPR, type, lowxor, 1984 build_int_cst (type, 1)); 1985 if (tem == NULL_TREE) 1986 continue; 1987 tem = fold_binary (BIT_AND_EXPR, type, lowxor, tem); 1988 if (tem == NULL_TREE || !integer_zerop (tem)) 1989 continue; 1990 highxor = fold_binary (BIT_XOR_EXPR, type, highi, highj); 1991 if (!tree_int_cst_equal (lowxor, highxor)) 1992 continue; 1993 tem = fold_build1 (BIT_NOT_EXPR, type, lowxor); 1994 exp = fold_build2 (BIT_AND_EXPR, type, ranges[i].exp, tem); 1995 lowj = fold_build2 (BIT_AND_EXPR, type, lowi, tem); 1996 highj = fold_build2 (BIT_AND_EXPR, type, highi, tem); 1997 if (update_range_test (ranges + i, ranges + j, 1, opcode, ops, exp, 1998 ranges[i].in_p, lowj, highj, 1999 ranges[i].strict_overflow_p 2000 || ranges[j].strict_overflow_p)) 2001 { 2002 any_changes = true; 2003 break; 2004 } 2005 } 2006 } 2007 2008 if (any_changes) 2009 { 2010 j = 0; 2011 FOR_EACH_VEC_ELT (operand_entry_t, *ops, i, oe) 2012 { 2013 if (oe->op == error_mark_node) 2014 continue; 2015 else if (i != j) 2016 VEC_replace (operand_entry_t, *ops, j, oe); 2017 j++; 2018 } 2019 VEC_truncate (operand_entry_t, *ops, j); 2020 } 2021 2022 XDELETEVEC (ranges); 2023 } 2024 2025 /* Return true if OPERAND is defined by a PHI node which uses the LHS 2026 of STMT in it's operands. This is also known as a "destructive 2027 update" operation. */ 2028 2029 static bool 2030 is_phi_for_stmt (gimple stmt, tree operand) 2031 { 2032 gimple def_stmt; 2033 tree lhs; 2034 use_operand_p arg_p; 2035 ssa_op_iter i; 2036 2037 if (TREE_CODE (operand) != SSA_NAME) 2038 return false; 2039 2040 lhs = gimple_assign_lhs (stmt); 2041 2042 def_stmt = SSA_NAME_DEF_STMT (operand); 2043 if (gimple_code (def_stmt) != GIMPLE_PHI) 2044 return false; 2045 2046 FOR_EACH_PHI_ARG (arg_p, def_stmt, i, SSA_OP_USE) 2047 if (lhs == USE_FROM_PTR (arg_p)) 2048 return true; 2049 return false; 2050 } 2051 2052 /* Remove def stmt of VAR if VAR has zero uses and recurse 2053 on rhs1 operand if so. */ 2054 2055 static void 2056 remove_visited_stmt_chain (tree var) 2057 { 2058 gimple stmt; 2059 gimple_stmt_iterator gsi; 2060 2061 while (1) 2062 { 2063 if (TREE_CODE (var) != SSA_NAME || !has_zero_uses (var)) 2064 return; 2065 stmt = SSA_NAME_DEF_STMT (var); 2066 if (!is_gimple_assign (stmt) 2067 || !gimple_visited_p (stmt)) 2068 return; 2069 var = gimple_assign_rhs1 (stmt); 2070 gsi = gsi_for_stmt (stmt); 2071 gsi_remove (&gsi, true); 2072 release_defs (stmt); 2073 } 2074 } 2075 2076 /* This function checks three consequtive operands in 2077 passed operands vector OPS starting from OPINDEX and 2078 swaps two operands if it is profitable for binary operation 2079 consuming OPINDEX + 1 abnd OPINDEX + 2 operands. 2080 2081 We pair ops with the same rank if possible. 2082 2083 The alternative we try is to see if STMT is a destructive 2084 update style statement, which is like: 2085 b = phi (a, ...) 2086 a = c + b; 2087 In that case, we want to use the destructive update form to 2088 expose the possible vectorizer sum reduction opportunity. 2089 In that case, the third operand will be the phi node. This 2090 check is not performed if STMT is null. 2091 2092 We could, of course, try to be better as noted above, and do a 2093 lot of work to try to find these opportunities in >3 operand 2094 cases, but it is unlikely to be worth it. */ 2095 2096 static void 2097 swap_ops_for_binary_stmt (VEC(operand_entry_t, heap) * ops, 2098 unsigned int opindex, gimple stmt) 2099 { 2100 operand_entry_t oe1, oe2, oe3; 2101 2102 oe1 = VEC_index (operand_entry_t, ops, opindex); 2103 oe2 = VEC_index (operand_entry_t, ops, opindex + 1); 2104 oe3 = VEC_index (operand_entry_t, ops, opindex + 2); 2105 2106 if ((oe1->rank == oe2->rank 2107 && oe2->rank != oe3->rank) 2108 || (stmt && is_phi_for_stmt (stmt, oe3->op) 2109 && !is_phi_for_stmt (stmt, oe1->op) 2110 && !is_phi_for_stmt (stmt, oe2->op))) 2111 { 2112 struct operand_entry temp = *oe3; 2113 oe3->op = oe1->op; 2114 oe3->rank = oe1->rank; 2115 oe1->op = temp.op; 2116 oe1->rank= temp.rank; 2117 } 2118 else if ((oe1->rank == oe3->rank 2119 && oe2->rank != oe3->rank) 2120 || (stmt && is_phi_for_stmt (stmt, oe2->op) 2121 && !is_phi_for_stmt (stmt, oe1->op) 2122 && !is_phi_for_stmt (stmt, oe3->op))) 2123 { 2124 struct operand_entry temp = *oe2; 2125 oe2->op = oe1->op; 2126 oe2->rank = oe1->rank; 2127 oe1->op = temp.op; 2128 oe1->rank= temp.rank; 2129 } 2130 } 2131 2132 /* Recursively rewrite our linearized statements so that the operators 2133 match those in OPS[OPINDEX], putting the computation in rank 2134 order. */ 2135 2136 static void 2137 rewrite_expr_tree (gimple stmt, unsigned int opindex, 2138 VEC(operand_entry_t, heap) * ops, bool moved) 2139 { 2140 tree rhs1 = gimple_assign_rhs1 (stmt); 2141 tree rhs2 = gimple_assign_rhs2 (stmt); 2142 operand_entry_t oe; 2143 2144 /* If we have three operands left, then we want to make sure the ones 2145 that get the double binary op are chosen wisely. */ 2146 if (opindex + 3 == VEC_length (operand_entry_t, ops)) 2147 swap_ops_for_binary_stmt (ops, opindex, stmt); 2148 2149 /* The final recursion case for this function is that you have 2150 exactly two operations left. 2151 If we had one exactly one op in the entire list to start with, we 2152 would have never called this function, and the tail recursion 2153 rewrites them one at a time. */ 2154 if (opindex + 2 == VEC_length (operand_entry_t, ops)) 2155 { 2156 operand_entry_t oe1, oe2; 2157 2158 oe1 = VEC_index (operand_entry_t, ops, opindex); 2159 oe2 = VEC_index (operand_entry_t, ops, opindex + 1); 2160 2161 if (rhs1 != oe1->op || rhs2 != oe2->op) 2162 { 2163 if (dump_file && (dump_flags & TDF_DETAILS)) 2164 { 2165 fprintf (dump_file, "Transforming "); 2166 print_gimple_stmt (dump_file, stmt, 0, 0); 2167 } 2168 2169 gimple_assign_set_rhs1 (stmt, oe1->op); 2170 gimple_assign_set_rhs2 (stmt, oe2->op); 2171 update_stmt (stmt); 2172 if (rhs1 != oe1->op && rhs1 != oe2->op) 2173 remove_visited_stmt_chain (rhs1); 2174 2175 if (dump_file && (dump_flags & TDF_DETAILS)) 2176 { 2177 fprintf (dump_file, " into "); 2178 print_gimple_stmt (dump_file, stmt, 0, 0); 2179 } 2180 2181 } 2182 return; 2183 } 2184 2185 /* If we hit here, we should have 3 or more ops left. */ 2186 gcc_assert (opindex + 2 < VEC_length (operand_entry_t, ops)); 2187 2188 /* Rewrite the next operator. */ 2189 oe = VEC_index (operand_entry_t, ops, opindex); 2190 2191 if (oe->op != rhs2) 2192 { 2193 if (!moved) 2194 { 2195 gimple_stmt_iterator gsinow, gsirhs1; 2196 gimple stmt1 = stmt, stmt2; 2197 unsigned int count; 2198 2199 gsinow = gsi_for_stmt (stmt); 2200 count = VEC_length (operand_entry_t, ops) - opindex - 2; 2201 while (count-- != 0) 2202 { 2203 stmt2 = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt1)); 2204 gsirhs1 = gsi_for_stmt (stmt2); 2205 gsi_move_before (&gsirhs1, &gsinow); 2206 gsi_prev (&gsinow); 2207 stmt1 = stmt2; 2208 } 2209 moved = true; 2210 } 2211 2212 if (dump_file && (dump_flags & TDF_DETAILS)) 2213 { 2214 fprintf (dump_file, "Transforming "); 2215 print_gimple_stmt (dump_file, stmt, 0, 0); 2216 } 2217 2218 gimple_assign_set_rhs2 (stmt, oe->op); 2219 update_stmt (stmt); 2220 2221 if (dump_file && (dump_flags & TDF_DETAILS)) 2222 { 2223 fprintf (dump_file, " into "); 2224 print_gimple_stmt (dump_file, stmt, 0, 0); 2225 } 2226 } 2227 /* Recurse on the LHS of the binary operator, which is guaranteed to 2228 be the non-leaf side. */ 2229 rewrite_expr_tree (SSA_NAME_DEF_STMT (rhs1), opindex + 1, ops, moved); 2230 } 2231 2232 /* Find out how many cycles we need to compute statements chain. 2233 OPS_NUM holds number os statements in a chain. CPU_WIDTH is a 2234 maximum number of independent statements we may execute per cycle. */ 2235 2236 static int 2237 get_required_cycles (int ops_num, int cpu_width) 2238 { 2239 int res; 2240 int elog; 2241 unsigned int rest; 2242 2243 /* While we have more than 2 * cpu_width operands 2244 we may reduce number of operands by cpu_width 2245 per cycle. */ 2246 res = ops_num / (2 * cpu_width); 2247 2248 /* Remained operands count may be reduced twice per cycle 2249 until we have only one operand. */ 2250 rest = (unsigned)(ops_num - res * cpu_width); 2251 elog = exact_log2 (rest); 2252 if (elog >= 0) 2253 res += elog; 2254 else 2255 res += floor_log2 (rest) + 1; 2256 2257 return res; 2258 } 2259 2260 /* Returns an optimal number of registers to use for computation of 2261 given statements. */ 2262 2263 static int 2264 get_reassociation_width (int ops_num, enum tree_code opc, 2265 enum machine_mode mode) 2266 { 2267 int param_width = PARAM_VALUE (PARAM_TREE_REASSOC_WIDTH); 2268 int width; 2269 int width_min; 2270 int cycles_best; 2271 2272 if (param_width > 0) 2273 width = param_width; 2274 else 2275 width = targetm.sched.reassociation_width (opc, mode); 2276 2277 if (width == 1) 2278 return width; 2279 2280 /* Get the minimal time required for sequence computation. */ 2281 cycles_best = get_required_cycles (ops_num, width); 2282 2283 /* Check if we may use less width and still compute sequence for 2284 the same time. It will allow us to reduce registers usage. 2285 get_required_cycles is monotonically increasing with lower width 2286 so we can perform a binary search for the minimal width that still 2287 results in the optimal cycle count. */ 2288 width_min = 1; 2289 while (width > width_min) 2290 { 2291 int width_mid = (width + width_min) / 2; 2292 2293 if (get_required_cycles (ops_num, width_mid) == cycles_best) 2294 width = width_mid; 2295 else if (width_min < width_mid) 2296 width_min = width_mid; 2297 else 2298 break; 2299 } 2300 2301 return width; 2302 } 2303 2304 /* Recursively rewrite our linearized statements so that the operators 2305 match those in OPS[OPINDEX], putting the computation in rank 2306 order and trying to allow operations to be executed in 2307 parallel. */ 2308 2309 static void 2310 rewrite_expr_tree_parallel (gimple stmt, int width, 2311 VEC(operand_entry_t, heap) * ops) 2312 { 2313 enum tree_code opcode = gimple_assign_rhs_code (stmt); 2314 int op_num = VEC_length (operand_entry_t, ops); 2315 int stmt_num = op_num - 1; 2316 gimple *stmts = XALLOCAVEC (gimple, stmt_num); 2317 int op_index = op_num - 1; 2318 int stmt_index = 0; 2319 int ready_stmts_end = 0; 2320 int i = 0; 2321 tree last_rhs1 = gimple_assign_rhs1 (stmt); 2322 tree lhs_var; 2323 2324 /* We start expression rewriting from the top statements. 2325 So, in this loop we create a full list of statements 2326 we will work with. */ 2327 stmts[stmt_num - 1] = stmt; 2328 for (i = stmt_num - 2; i >= 0; i--) 2329 stmts[i] = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmts[i+1])); 2330 2331 lhs_var = create_tmp_reg (TREE_TYPE (last_rhs1), NULL); 2332 add_referenced_var (lhs_var); 2333 2334 for (i = 0; i < stmt_num; i++) 2335 { 2336 tree op1, op2; 2337 2338 /* Determine whether we should use results of 2339 already handled statements or not. */ 2340 if (ready_stmts_end == 0 2341 && (i - stmt_index >= width || op_index < 1)) 2342 ready_stmts_end = i; 2343 2344 /* Now we choose operands for the next statement. Non zero 2345 value in ready_stmts_end means here that we should use 2346 the result of already generated statements as new operand. */ 2347 if (ready_stmts_end > 0) 2348 { 2349 op1 = gimple_assign_lhs (stmts[stmt_index++]); 2350 if (ready_stmts_end > stmt_index) 2351 op2 = gimple_assign_lhs (stmts[stmt_index++]); 2352 else if (op_index >= 0) 2353 op2 = VEC_index (operand_entry_t, ops, op_index--)->op; 2354 else 2355 { 2356 gcc_assert (stmt_index < i); 2357 op2 = gimple_assign_lhs (stmts[stmt_index++]); 2358 } 2359 2360 if (stmt_index >= ready_stmts_end) 2361 ready_stmts_end = 0; 2362 } 2363 else 2364 { 2365 if (op_index > 1) 2366 swap_ops_for_binary_stmt (ops, op_index - 2, NULL); 2367 op2 = VEC_index (operand_entry_t, ops, op_index--)->op; 2368 op1 = VEC_index (operand_entry_t, ops, op_index--)->op; 2369 } 2370 2371 /* If we emit the last statement then we should put 2372 operands into the last statement. It will also 2373 break the loop. */ 2374 if (op_index < 0 && stmt_index == i) 2375 i = stmt_num - 1; 2376 2377 if (dump_file && (dump_flags & TDF_DETAILS)) 2378 { 2379 fprintf (dump_file, "Transforming "); 2380 print_gimple_stmt (dump_file, stmts[i], 0, 0); 2381 } 2382 2383 /* We keep original statement only for the last one. All 2384 others are recreated. */ 2385 if (i == stmt_num - 1) 2386 { 2387 gimple_assign_set_rhs1 (stmts[i], op1); 2388 gimple_assign_set_rhs2 (stmts[i], op2); 2389 update_stmt (stmts[i]); 2390 } 2391 else 2392 stmts[i] = build_and_add_sum (lhs_var, op1, op2, opcode); 2393 2394 if (dump_file && (dump_flags & TDF_DETAILS)) 2395 { 2396 fprintf (dump_file, " into "); 2397 print_gimple_stmt (dump_file, stmts[i], 0, 0); 2398 } 2399 } 2400 2401 remove_visited_stmt_chain (last_rhs1); 2402 } 2403 2404 /* Transform STMT, which is really (A +B) + (C + D) into the left 2405 linear form, ((A+B)+C)+D. 2406 Recurse on D if necessary. */ 2407 2408 static void 2409 linearize_expr (gimple stmt) 2410 { 2411 gimple_stmt_iterator gsinow, gsirhs; 2412 gimple binlhs = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt)); 2413 gimple binrhs = SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt)); 2414 enum tree_code rhscode = gimple_assign_rhs_code (stmt); 2415 gimple newbinrhs = NULL; 2416 struct loop *loop = loop_containing_stmt (stmt); 2417 2418 gcc_assert (is_reassociable_op (binlhs, rhscode, loop) 2419 && is_reassociable_op (binrhs, rhscode, loop)); 2420 2421 gsinow = gsi_for_stmt (stmt); 2422 gsirhs = gsi_for_stmt (binrhs); 2423 gsi_move_before (&gsirhs, &gsinow); 2424 2425 gimple_assign_set_rhs2 (stmt, gimple_assign_rhs1 (binrhs)); 2426 gimple_assign_set_rhs1 (binrhs, gimple_assign_lhs (binlhs)); 2427 gimple_assign_set_rhs1 (stmt, gimple_assign_lhs (binrhs)); 2428 2429 if (TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME) 2430 newbinrhs = SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt)); 2431 2432 if (dump_file && (dump_flags & TDF_DETAILS)) 2433 { 2434 fprintf (dump_file, "Linearized: "); 2435 print_gimple_stmt (dump_file, stmt, 0, 0); 2436 } 2437 2438 reassociate_stats.linearized++; 2439 update_stmt (binrhs); 2440 update_stmt (binlhs); 2441 update_stmt (stmt); 2442 2443 gimple_set_visited (stmt, true); 2444 gimple_set_visited (binlhs, true); 2445 gimple_set_visited (binrhs, true); 2446 2447 /* Tail recurse on the new rhs if it still needs reassociation. */ 2448 if (newbinrhs && is_reassociable_op (newbinrhs, rhscode, loop)) 2449 /* ??? This should probably be linearize_expr (newbinrhs) but I don't 2450 want to change the algorithm while converting to tuples. */ 2451 linearize_expr (stmt); 2452 } 2453 2454 /* If LHS has a single immediate use that is a GIMPLE_ASSIGN statement, return 2455 it. Otherwise, return NULL. */ 2456 2457 static gimple 2458 get_single_immediate_use (tree lhs) 2459 { 2460 use_operand_p immuse; 2461 gimple immusestmt; 2462 2463 if (TREE_CODE (lhs) == SSA_NAME 2464 && single_imm_use (lhs, &immuse, &immusestmt) 2465 && is_gimple_assign (immusestmt)) 2466 return immusestmt; 2467 2468 return NULL; 2469 } 2470 2471 /* Recursively negate the value of TONEGATE, and return the SSA_NAME 2472 representing the negated value. Insertions of any necessary 2473 instructions go before GSI. 2474 This function is recursive in that, if you hand it "a_5" as the 2475 value to negate, and a_5 is defined by "a_5 = b_3 + b_4", it will 2476 transform b_3 + b_4 into a_5 = -b_3 + -b_4. */ 2477 2478 static tree 2479 negate_value (tree tonegate, gimple_stmt_iterator *gsi) 2480 { 2481 gimple negatedefstmt= NULL; 2482 tree resultofnegate; 2483 2484 /* If we are trying to negate a name, defined by an add, negate the 2485 add operands instead. */ 2486 if (TREE_CODE (tonegate) == SSA_NAME) 2487 negatedefstmt = SSA_NAME_DEF_STMT (tonegate); 2488 if (TREE_CODE (tonegate) == SSA_NAME 2489 && is_gimple_assign (negatedefstmt) 2490 && TREE_CODE (gimple_assign_lhs (negatedefstmt)) == SSA_NAME 2491 && has_single_use (gimple_assign_lhs (negatedefstmt)) 2492 && gimple_assign_rhs_code (negatedefstmt) == PLUS_EXPR) 2493 { 2494 gimple_stmt_iterator gsi; 2495 tree rhs1 = gimple_assign_rhs1 (negatedefstmt); 2496 tree rhs2 = gimple_assign_rhs2 (negatedefstmt); 2497 2498 gsi = gsi_for_stmt (negatedefstmt); 2499 rhs1 = negate_value (rhs1, &gsi); 2500 gimple_assign_set_rhs1 (negatedefstmt, rhs1); 2501 2502 gsi = gsi_for_stmt (negatedefstmt); 2503 rhs2 = negate_value (rhs2, &gsi); 2504 gimple_assign_set_rhs2 (negatedefstmt, rhs2); 2505 2506 update_stmt (negatedefstmt); 2507 return gimple_assign_lhs (negatedefstmt); 2508 } 2509 2510 tonegate = fold_build1 (NEGATE_EXPR, TREE_TYPE (tonegate), tonegate); 2511 resultofnegate = force_gimple_operand_gsi (gsi, tonegate, true, 2512 NULL_TREE, true, GSI_SAME_STMT); 2513 return resultofnegate; 2514 } 2515 2516 /* Return true if we should break up the subtract in STMT into an add 2517 with negate. This is true when we the subtract operands are really 2518 adds, or the subtract itself is used in an add expression. In 2519 either case, breaking up the subtract into an add with negate 2520 exposes the adds to reassociation. */ 2521 2522 static bool 2523 should_break_up_subtract (gimple stmt) 2524 { 2525 tree lhs = gimple_assign_lhs (stmt); 2526 tree binlhs = gimple_assign_rhs1 (stmt); 2527 tree binrhs = gimple_assign_rhs2 (stmt); 2528 gimple immusestmt; 2529 struct loop *loop = loop_containing_stmt (stmt); 2530 2531 if (TREE_CODE (binlhs) == SSA_NAME 2532 && is_reassociable_op (SSA_NAME_DEF_STMT (binlhs), PLUS_EXPR, loop)) 2533 return true; 2534 2535 if (TREE_CODE (binrhs) == SSA_NAME 2536 && is_reassociable_op (SSA_NAME_DEF_STMT (binrhs), PLUS_EXPR, loop)) 2537 return true; 2538 2539 if (TREE_CODE (lhs) == SSA_NAME 2540 && (immusestmt = get_single_immediate_use (lhs)) 2541 && is_gimple_assign (immusestmt) 2542 && (gimple_assign_rhs_code (immusestmt) == PLUS_EXPR 2543 || gimple_assign_rhs_code (immusestmt) == MULT_EXPR)) 2544 return true; 2545 return false; 2546 } 2547 2548 /* Transform STMT from A - B into A + -B. */ 2549 2550 static void 2551 break_up_subtract (gimple stmt, gimple_stmt_iterator *gsip) 2552 { 2553 tree rhs1 = gimple_assign_rhs1 (stmt); 2554 tree rhs2 = gimple_assign_rhs2 (stmt); 2555 2556 if (dump_file && (dump_flags & TDF_DETAILS)) 2557 { 2558 fprintf (dump_file, "Breaking up subtract "); 2559 print_gimple_stmt (dump_file, stmt, 0, 0); 2560 } 2561 2562 rhs2 = negate_value (rhs2, gsip); 2563 gimple_assign_set_rhs_with_ops (gsip, PLUS_EXPR, rhs1, rhs2); 2564 update_stmt (stmt); 2565 } 2566 2567 /* Recursively linearize a binary expression that is the RHS of STMT. 2568 Place the operands of the expression tree in the vector named OPS. */ 2569 2570 static void 2571 linearize_expr_tree (VEC(operand_entry_t, heap) **ops, gimple stmt, 2572 bool is_associative, bool set_visited) 2573 { 2574 tree binlhs = gimple_assign_rhs1 (stmt); 2575 tree binrhs = gimple_assign_rhs2 (stmt); 2576 gimple binlhsdef, binrhsdef; 2577 bool binlhsisreassoc = false; 2578 bool binrhsisreassoc = false; 2579 enum tree_code rhscode = gimple_assign_rhs_code (stmt); 2580 struct loop *loop = loop_containing_stmt (stmt); 2581 2582 if (set_visited) 2583 gimple_set_visited (stmt, true); 2584 2585 if (TREE_CODE (binlhs) == SSA_NAME) 2586 { 2587 binlhsdef = SSA_NAME_DEF_STMT (binlhs); 2588 binlhsisreassoc = (is_reassociable_op (binlhsdef, rhscode, loop) 2589 && !stmt_could_throw_p (binlhsdef)); 2590 } 2591 2592 if (TREE_CODE (binrhs) == SSA_NAME) 2593 { 2594 binrhsdef = SSA_NAME_DEF_STMT (binrhs); 2595 binrhsisreassoc = (is_reassociable_op (binrhsdef, rhscode, loop) 2596 && !stmt_could_throw_p (binrhsdef)); 2597 } 2598 2599 /* If the LHS is not reassociable, but the RHS is, we need to swap 2600 them. If neither is reassociable, there is nothing we can do, so 2601 just put them in the ops vector. If the LHS is reassociable, 2602 linearize it. If both are reassociable, then linearize the RHS 2603 and the LHS. */ 2604 2605 if (!binlhsisreassoc) 2606 { 2607 tree temp; 2608 2609 /* If this is not a associative operation like division, give up. */ 2610 if (!is_associative) 2611 { 2612 add_to_ops_vec (ops, binrhs); 2613 return; 2614 } 2615 2616 if (!binrhsisreassoc) 2617 { 2618 add_to_ops_vec (ops, binrhs); 2619 add_to_ops_vec (ops, binlhs); 2620 return; 2621 } 2622 2623 if (dump_file && (dump_flags & TDF_DETAILS)) 2624 { 2625 fprintf (dump_file, "swapping operands of "); 2626 print_gimple_stmt (dump_file, stmt, 0, 0); 2627 } 2628 2629 swap_tree_operands (stmt, 2630 gimple_assign_rhs1_ptr (stmt), 2631 gimple_assign_rhs2_ptr (stmt)); 2632 update_stmt (stmt); 2633 2634 if (dump_file && (dump_flags & TDF_DETAILS)) 2635 { 2636 fprintf (dump_file, " is now "); 2637 print_gimple_stmt (dump_file, stmt, 0, 0); 2638 } 2639 2640 /* We want to make it so the lhs is always the reassociative op, 2641 so swap. */ 2642 temp = binlhs; 2643 binlhs = binrhs; 2644 binrhs = temp; 2645 } 2646 else if (binrhsisreassoc) 2647 { 2648 linearize_expr (stmt); 2649 binlhs = gimple_assign_rhs1 (stmt); 2650 binrhs = gimple_assign_rhs2 (stmt); 2651 } 2652 2653 gcc_assert (TREE_CODE (binrhs) != SSA_NAME 2654 || !is_reassociable_op (SSA_NAME_DEF_STMT (binrhs), 2655 rhscode, loop)); 2656 linearize_expr_tree (ops, SSA_NAME_DEF_STMT (binlhs), 2657 is_associative, set_visited); 2658 add_to_ops_vec (ops, binrhs); 2659 } 2660 2661 /* Repropagate the negates back into subtracts, since no other pass 2662 currently does it. */ 2663 2664 static void 2665 repropagate_negates (void) 2666 { 2667 unsigned int i = 0; 2668 tree negate; 2669 2670 FOR_EACH_VEC_ELT (tree, plus_negates, i, negate) 2671 { 2672 gimple user = get_single_immediate_use (negate); 2673 2674 if (!user || !is_gimple_assign (user)) 2675 continue; 2676 2677 /* The negate operand can be either operand of a PLUS_EXPR 2678 (it can be the LHS if the RHS is a constant for example). 2679 2680 Force the negate operand to the RHS of the PLUS_EXPR, then 2681 transform the PLUS_EXPR into a MINUS_EXPR. */ 2682 if (gimple_assign_rhs_code (user) == PLUS_EXPR) 2683 { 2684 /* If the negated operand appears on the LHS of the 2685 PLUS_EXPR, exchange the operands of the PLUS_EXPR 2686 to force the negated operand to the RHS of the PLUS_EXPR. */ 2687 if (gimple_assign_rhs1 (user) == negate) 2688 { 2689 swap_tree_operands (user, 2690 gimple_assign_rhs1_ptr (user), 2691 gimple_assign_rhs2_ptr (user)); 2692 } 2693 2694 /* Now transform the PLUS_EXPR into a MINUS_EXPR and replace 2695 the RHS of the PLUS_EXPR with the operand of the NEGATE_EXPR. */ 2696 if (gimple_assign_rhs2 (user) == negate) 2697 { 2698 tree rhs1 = gimple_assign_rhs1 (user); 2699 tree rhs2 = get_unary_op (negate, NEGATE_EXPR); 2700 gimple_stmt_iterator gsi = gsi_for_stmt (user); 2701 gimple_assign_set_rhs_with_ops (&gsi, MINUS_EXPR, rhs1, rhs2); 2702 update_stmt (user); 2703 } 2704 } 2705 else if (gimple_assign_rhs_code (user) == MINUS_EXPR) 2706 { 2707 if (gimple_assign_rhs1 (user) == negate) 2708 { 2709 /* We have 2710 x = -a 2711 y = x - b 2712 which we transform into 2713 x = a + b 2714 y = -x . 2715 This pushes down the negate which we possibly can merge 2716 into some other operation, hence insert it into the 2717 plus_negates vector. */ 2718 gimple feed = SSA_NAME_DEF_STMT (negate); 2719 tree a = gimple_assign_rhs1 (feed); 2720 tree rhs2 = gimple_assign_rhs2 (user); 2721 gimple_stmt_iterator gsi = gsi_for_stmt (feed), gsi2; 2722 gimple_replace_lhs (feed, negate); 2723 gimple_assign_set_rhs_with_ops (&gsi, PLUS_EXPR, a, rhs2); 2724 update_stmt (gsi_stmt (gsi)); 2725 gsi2 = gsi_for_stmt (user); 2726 gimple_assign_set_rhs_with_ops (&gsi2, NEGATE_EXPR, negate, NULL); 2727 update_stmt (gsi_stmt (gsi2)); 2728 gsi_move_before (&gsi, &gsi2); 2729 VEC_safe_push (tree, heap, plus_negates, 2730 gimple_assign_lhs (gsi_stmt (gsi2))); 2731 } 2732 else 2733 { 2734 /* Transform "x = -a; y = b - x" into "y = b + a", getting 2735 rid of one operation. */ 2736 gimple feed = SSA_NAME_DEF_STMT (negate); 2737 tree a = gimple_assign_rhs1 (feed); 2738 tree rhs1 = gimple_assign_rhs1 (user); 2739 gimple_stmt_iterator gsi = gsi_for_stmt (user); 2740 gimple_assign_set_rhs_with_ops (&gsi, PLUS_EXPR, rhs1, a); 2741 update_stmt (gsi_stmt (gsi)); 2742 } 2743 } 2744 } 2745 } 2746 2747 /* Returns true if OP is of a type for which we can do reassociation. 2748 That is for integral or non-saturating fixed-point types, and for 2749 floating point type when associative-math is enabled. */ 2750 2751 static bool 2752 can_reassociate_p (tree op) 2753 { 2754 tree type = TREE_TYPE (op); 2755 if ((INTEGRAL_TYPE_P (type) && TYPE_OVERFLOW_WRAPS (type)) 2756 || NON_SAT_FIXED_POINT_TYPE_P (type) 2757 || (flag_associative_math && FLOAT_TYPE_P (type))) 2758 return true; 2759 return false; 2760 } 2761 2762 /* Break up subtract operations in block BB. 2763 2764 We do this top down because we don't know whether the subtract is 2765 part of a possible chain of reassociation except at the top. 2766 2767 IE given 2768 d = f + g 2769 c = a + e 2770 b = c - d 2771 q = b - r 2772 k = t - q 2773 2774 we want to break up k = t - q, but we won't until we've transformed q 2775 = b - r, which won't be broken up until we transform b = c - d. 2776 2777 En passant, clear the GIMPLE visited flag on every statement. */ 2778 2779 static void 2780 break_up_subtract_bb (basic_block bb) 2781 { 2782 gimple_stmt_iterator gsi; 2783 basic_block son; 2784 2785 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 2786 { 2787 gimple stmt = gsi_stmt (gsi); 2788 gimple_set_visited (stmt, false); 2789 2790 if (!is_gimple_assign (stmt) 2791 || !can_reassociate_p (gimple_assign_lhs (stmt))) 2792 continue; 2793 2794 /* Look for simple gimple subtract operations. */ 2795 if (gimple_assign_rhs_code (stmt) == MINUS_EXPR) 2796 { 2797 if (!can_reassociate_p (gimple_assign_rhs1 (stmt)) 2798 || !can_reassociate_p (gimple_assign_rhs2 (stmt))) 2799 continue; 2800 2801 /* Check for a subtract used only in an addition. If this 2802 is the case, transform it into add of a negate for better 2803 reassociation. IE transform C = A-B into C = A + -B if C 2804 is only used in an addition. */ 2805 if (should_break_up_subtract (stmt)) 2806 break_up_subtract (stmt, &gsi); 2807 } 2808 else if (gimple_assign_rhs_code (stmt) == NEGATE_EXPR 2809 && can_reassociate_p (gimple_assign_rhs1 (stmt))) 2810 VEC_safe_push (tree, heap, plus_negates, gimple_assign_lhs (stmt)); 2811 } 2812 for (son = first_dom_son (CDI_DOMINATORS, bb); 2813 son; 2814 son = next_dom_son (CDI_DOMINATORS, son)) 2815 break_up_subtract_bb (son); 2816 } 2817 2818 /* Reassociate expressions in basic block BB and its post-dominator as 2819 children. */ 2820 2821 static void 2822 reassociate_bb (basic_block bb) 2823 { 2824 gimple_stmt_iterator gsi; 2825 basic_block son; 2826 2827 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi)) 2828 { 2829 gimple stmt = gsi_stmt (gsi); 2830 2831 if (is_gimple_assign (stmt) 2832 && !stmt_could_throw_p (stmt)) 2833 { 2834 tree lhs, rhs1, rhs2; 2835 enum tree_code rhs_code = gimple_assign_rhs_code (stmt); 2836 2837 /* If this is not a gimple binary expression, there is 2838 nothing for us to do with it. */ 2839 if (get_gimple_rhs_class (rhs_code) != GIMPLE_BINARY_RHS) 2840 continue; 2841 2842 /* If this was part of an already processed statement, 2843 we don't need to touch it again. */ 2844 if (gimple_visited_p (stmt)) 2845 { 2846 /* This statement might have become dead because of previous 2847 reassociations. */ 2848 if (has_zero_uses (gimple_get_lhs (stmt))) 2849 { 2850 gsi_remove (&gsi, true); 2851 release_defs (stmt); 2852 /* We might end up removing the last stmt above which 2853 places the iterator to the end of the sequence. 2854 Reset it to the last stmt in this case which might 2855 be the end of the sequence as well if we removed 2856 the last statement of the sequence. In which case 2857 we need to bail out. */ 2858 if (gsi_end_p (gsi)) 2859 { 2860 gsi = gsi_last_bb (bb); 2861 if (gsi_end_p (gsi)) 2862 break; 2863 } 2864 } 2865 continue; 2866 } 2867 2868 lhs = gimple_assign_lhs (stmt); 2869 rhs1 = gimple_assign_rhs1 (stmt); 2870 rhs2 = gimple_assign_rhs2 (stmt); 2871 2872 /* For non-bit or min/max operations we can't associate 2873 all types. Verify that here. */ 2874 if (rhs_code != BIT_IOR_EXPR 2875 && rhs_code != BIT_AND_EXPR 2876 && rhs_code != BIT_XOR_EXPR 2877 && rhs_code != MIN_EXPR 2878 && rhs_code != MAX_EXPR 2879 && (!can_reassociate_p (lhs) 2880 || !can_reassociate_p (rhs1) 2881 || !can_reassociate_p (rhs2))) 2882 continue; 2883 2884 if (associative_tree_code (rhs_code)) 2885 { 2886 VEC(operand_entry_t, heap) *ops = NULL; 2887 2888 /* There may be no immediate uses left by the time we 2889 get here because we may have eliminated them all. */ 2890 if (TREE_CODE (lhs) == SSA_NAME && has_zero_uses (lhs)) 2891 continue; 2892 2893 gimple_set_visited (stmt, true); 2894 linearize_expr_tree (&ops, stmt, true, true); 2895 VEC_qsort (operand_entry_t, ops, sort_by_operand_rank); 2896 optimize_ops_list (rhs_code, &ops); 2897 if (undistribute_ops_list (rhs_code, &ops, 2898 loop_containing_stmt (stmt))) 2899 { 2900 VEC_qsort (operand_entry_t, ops, sort_by_operand_rank); 2901 optimize_ops_list (rhs_code, &ops); 2902 } 2903 2904 if (rhs_code == BIT_IOR_EXPR || rhs_code == BIT_AND_EXPR) 2905 optimize_range_tests (rhs_code, &ops); 2906 2907 if (VEC_length (operand_entry_t, ops) == 1) 2908 { 2909 if (dump_file && (dump_flags & TDF_DETAILS)) 2910 { 2911 fprintf (dump_file, "Transforming "); 2912 print_gimple_stmt (dump_file, stmt, 0, 0); 2913 } 2914 2915 rhs1 = gimple_assign_rhs1 (stmt); 2916 gimple_assign_set_rhs_from_tree (&gsi, 2917 VEC_last (operand_entry_t, 2918 ops)->op); 2919 update_stmt (stmt); 2920 remove_visited_stmt_chain (rhs1); 2921 2922 if (dump_file && (dump_flags & TDF_DETAILS)) 2923 { 2924 fprintf (dump_file, " into "); 2925 print_gimple_stmt (dump_file, stmt, 0, 0); 2926 } 2927 } 2928 else 2929 { 2930 enum machine_mode mode = TYPE_MODE (TREE_TYPE (lhs)); 2931 int ops_num = VEC_length (operand_entry_t, ops); 2932 int width = get_reassociation_width (ops_num, rhs_code, mode); 2933 2934 if (dump_file && (dump_flags & TDF_DETAILS)) 2935 fprintf (dump_file, 2936 "Width = %d was chosen for reassociation\n", width); 2937 2938 if (width > 1 2939 && VEC_length (operand_entry_t, ops) > 3) 2940 rewrite_expr_tree_parallel (stmt, width, ops); 2941 else 2942 rewrite_expr_tree (stmt, 0, ops, false); 2943 } 2944 2945 VEC_free (operand_entry_t, heap, ops); 2946 } 2947 } 2948 } 2949 for (son = first_dom_son (CDI_POST_DOMINATORS, bb); 2950 son; 2951 son = next_dom_son (CDI_POST_DOMINATORS, son)) 2952 reassociate_bb (son); 2953 } 2954 2955 void dump_ops_vector (FILE *file, VEC (operand_entry_t, heap) *ops); 2956 void debug_ops_vector (VEC (operand_entry_t, heap) *ops); 2957 2958 /* Dump the operand entry vector OPS to FILE. */ 2959 2960 void 2961 dump_ops_vector (FILE *file, VEC (operand_entry_t, heap) *ops) 2962 { 2963 operand_entry_t oe; 2964 unsigned int i; 2965 2966 FOR_EACH_VEC_ELT (operand_entry_t, ops, i, oe) 2967 { 2968 fprintf (file, "Op %d -> rank: %d, tree: ", i, oe->rank); 2969 print_generic_expr (file, oe->op, 0); 2970 } 2971 } 2972 2973 /* Dump the operand entry vector OPS to STDERR. */ 2974 2975 DEBUG_FUNCTION void 2976 debug_ops_vector (VEC (operand_entry_t, heap) *ops) 2977 { 2978 dump_ops_vector (stderr, ops); 2979 } 2980 2981 static void 2982 do_reassoc (void) 2983 { 2984 break_up_subtract_bb (ENTRY_BLOCK_PTR); 2985 reassociate_bb (EXIT_BLOCK_PTR); 2986 } 2987 2988 /* Initialize the reassociation pass. */ 2989 2990 static void 2991 init_reassoc (void) 2992 { 2993 int i; 2994 long rank = 2; 2995 tree param; 2996 int *bbs = XNEWVEC (int, last_basic_block + 1); 2997 2998 /* Find the loops, so that we can prevent moving calculations in 2999 them. */ 3000 loop_optimizer_init (AVOID_CFG_MODIFICATIONS); 3001 3002 memset (&reassociate_stats, 0, sizeof (reassociate_stats)); 3003 3004 operand_entry_pool = create_alloc_pool ("operand entry pool", 3005 sizeof (struct operand_entry), 30); 3006 next_operand_entry_id = 0; 3007 3008 /* Reverse RPO (Reverse Post Order) will give us something where 3009 deeper loops come later. */ 3010 pre_and_rev_post_order_compute (NULL, bbs, false); 3011 bb_rank = XCNEWVEC (long, last_basic_block + 1); 3012 operand_rank = pointer_map_create (); 3013 3014 /* Give each argument a distinct rank. */ 3015 for (param = DECL_ARGUMENTS (current_function_decl); 3016 param; 3017 param = DECL_CHAIN (param)) 3018 { 3019 if (gimple_default_def (cfun, param) != NULL) 3020 { 3021 tree def = gimple_default_def (cfun, param); 3022 insert_operand_rank (def, ++rank); 3023 } 3024 } 3025 3026 /* Give the chain decl a distinct rank. */ 3027 if (cfun->static_chain_decl != NULL) 3028 { 3029 tree def = gimple_default_def (cfun, cfun->static_chain_decl); 3030 if (def != NULL) 3031 insert_operand_rank (def, ++rank); 3032 } 3033 3034 /* Set up rank for each BB */ 3035 for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; i++) 3036 bb_rank[bbs[i]] = ++rank << 16; 3037 3038 free (bbs); 3039 calculate_dominance_info (CDI_POST_DOMINATORS); 3040 plus_negates = NULL; 3041 } 3042 3043 /* Cleanup after the reassociation pass, and print stats if 3044 requested. */ 3045 3046 static void 3047 fini_reassoc (void) 3048 { 3049 statistics_counter_event (cfun, "Linearized", 3050 reassociate_stats.linearized); 3051 statistics_counter_event (cfun, "Constants eliminated", 3052 reassociate_stats.constants_eliminated); 3053 statistics_counter_event (cfun, "Ops eliminated", 3054 reassociate_stats.ops_eliminated); 3055 statistics_counter_event (cfun, "Statements rewritten", 3056 reassociate_stats.rewritten); 3057 3058 pointer_map_destroy (operand_rank); 3059 free_alloc_pool (operand_entry_pool); 3060 free (bb_rank); 3061 VEC_free (tree, heap, plus_negates); 3062 free_dominance_info (CDI_POST_DOMINATORS); 3063 loop_optimizer_finalize (); 3064 } 3065 3066 /* Gate and execute functions for Reassociation. */ 3067 3068 static unsigned int 3069 execute_reassoc (void) 3070 { 3071 init_reassoc (); 3072 3073 do_reassoc (); 3074 repropagate_negates (); 3075 3076 fini_reassoc (); 3077 return 0; 3078 } 3079 3080 static bool 3081 gate_tree_ssa_reassoc (void) 3082 { 3083 return flag_tree_reassoc != 0; 3084 } 3085 3086 struct gimple_opt_pass pass_reassoc = 3087 { 3088 { 3089 GIMPLE_PASS, 3090 "reassoc", /* name */ 3091 gate_tree_ssa_reassoc, /* gate */ 3092 execute_reassoc, /* execute */ 3093 NULL, /* sub */ 3094 NULL, /* next */ 3095 0, /* static_pass_number */ 3096 TV_TREE_REASSOC, /* tv_id */ 3097 PROP_cfg | PROP_ssa, /* properties_required */ 3098 0, /* properties_provided */ 3099 0, /* properties_destroyed */ 3100 0, /* todo_flags_start */ 3101 TODO_verify_ssa 3102 | TODO_verify_flow 3103 | TODO_ggc_collect /* todo_flags_finish */ 3104 } 3105 }; 3106