1/* Reassociation for trees. 2 Copyright (C) 2005 Free Software Foundation, Inc. 3 Contributed by Daniel Berlin <dan@dberlin.org> 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify 8it under the terms of the GNU General Public License as published by 9the Free Software Foundation; either version 2, or (at your option) 10any later version. 11 12GCC is distributed in the hope that it will be useful, 13but WITHOUT ANY WARRANTY; without even the implied warranty of 14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15GNU General Public License for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING. If not, write to 19the Free Software Foundation, 51 Franklin Street, Fifth Floor, 20Boston, MA 02110-1301, USA. */ 21 22#include "config.h" 23#include "system.h" 24#include "coretypes.h" 25#include "tm.h" 26#include "errors.h" 27#include "ggc.h" 28#include "tree.h" 29#include "basic-block.h" 30#include "diagnostic.h" 31#include "tree-inline.h" 32#include "tree-flow.h" 33#include "tree-gimple.h" 34#include "tree-dump.h" 35#include "timevar.h" 36#include "hashtab.h" 37#include "tree-iterator.h" 38#include "tree-pass.h" 39 40/* This is a simple global reassociation pass that uses a combination 41 of heuristics and a hashtable to try to expose more operations to 42 CSE. 43 44 The basic idea behind the heuristic is to rank expressions by 45 depth of the computation tree and loop depth, and try to produce 46 expressions consisting of small rank operations, as they are more 47 likely to reoccur. In addition, we use a hashtable to try to see 48 if we can transpose an operation into something we have seen 49 before. 50 51 Note that the way the hashtable is structured will sometimes find 52 matches that will not expose additional redundancies, since it is 53 not unwound as we traverse back up one branch of the dominator 54 tree and down another. However, the cost of improving this is 55 probably not worth the additional benefits it will bring. */ 56 57/* Statistics */ 58static struct 59{ 60 int reassociated_by_rank; 61 int reassociated_by_match; 62} reassociate_stats; 63 64 65 66/* Seen binary operator hashtable. */ 67static htab_t seen_binops; 68 69/* Binary operator struct. */ 70 71typedef struct seen_binop_d 72{ 73 tree op1; 74 tree op2; 75} *seen_binop_t; 76 77/* Return a SEEN_BINOP_T if we have seen an associative binary 78 operator with OP1 and OP2 in it. */ 79 80static seen_binop_t 81find_seen_binop (tree op1, tree op2) 82{ 83 void **slot; 84 struct seen_binop_d sbd; 85 sbd.op1 = op1; 86 sbd.op2 = op2; 87 slot = htab_find_slot (seen_binops, &sbd, NO_INSERT); 88 if (!slot) 89 return NULL; 90 return ((seen_binop_t) *slot); 91} 92 93/* Insert a binary operator consisting of OP1 and OP2 into the 94 SEEN_BINOP table. */ 95 96static void 97insert_seen_binop (tree op1, tree op2) 98{ 99 void **slot; 100 seen_binop_t new_pair = xmalloc (sizeof (*new_pair)); 101 new_pair->op1 = op1; 102 new_pair->op2 = op2; 103 slot = htab_find_slot (seen_binops, new_pair, INSERT); 104 if (*slot != NULL) 105 free (*slot); 106 *slot = new_pair; 107} 108 109/* Return the hash value for a seen binop structure pointed to by P. 110 Because all the binops we consider are associative, we just add the 111 hash value for op1 and op2. */ 112 113static hashval_t 114seen_binop_hash (const void *p) 115{ 116 const seen_binop_t sb = (seen_binop_t) p; 117 return iterative_hash_expr (sb->op1, 0) + iterative_hash_expr (sb->op2, 0); 118} 119 120/* Return true if two seen binop structures pointed to by P1 and P2 are equal. 121 We have to check the operators both ways because we don't know what 122 order they appear in the table. */ 123 124static int 125seen_binop_eq (const void *p1, const void *p2) 126{ 127 const seen_binop_t sb1 = (seen_binop_t) p1; 128 const seen_binop_t sb2 = (seen_binop_t) p2; 129 return (sb1->op1 == sb2->op1 && sb1->op2 == sb2->op2) 130 || (sb1->op2 == sb2->op1 && sb1->op1 == sb2->op2); 131} 132 133/* Value rank structure. */ 134 135typedef struct valrank_d 136{ 137 tree e; 138 unsigned int rank; 139} *valrank_t; 140 141/* Starting rank number for a given basic block, so that we can rank 142 operations using unmovable instructions in that BB based on the bb 143 depth. */ 144static unsigned int *bb_rank; 145 146/* Value rank hashtable. */ 147static htab_t value_rank; 148 149 150/* Look up the value rank structure for expression E. */ 151 152static valrank_t 153find_value_rank (tree e) 154{ 155 void **slot; 156 struct valrank_d vrd; 157 vrd.e = e; 158 slot = htab_find_slot (value_rank, &vrd, NO_INSERT); 159 if (!slot) 160 return NULL; 161 return ((valrank_t) *slot); 162} 163 164/* Insert {E,RANK} into the value rank hashtable. */ 165 166static void 167insert_value_rank (tree e, unsigned int rank) 168{ 169 void **slot; 170 valrank_t new_pair = xmalloc (sizeof (*new_pair)); 171 new_pair->e = e; 172 new_pair->rank = rank; 173 slot = htab_find_slot (value_rank, new_pair, INSERT); 174 gcc_assert (*slot == NULL); 175 *slot = new_pair; 176 177} 178 179 180/* Return the hash value for a value rank structure */ 181 182static hashval_t 183valrank_hash (const void *p) 184{ 185 const valrank_t vr = (valrank_t) p; 186 return iterative_hash_expr (vr->e, 0); 187} 188 189/* Return true if two value rank structures are equal. */ 190 191static int 192valrank_eq (const void *p1, const void *p2) 193{ 194 const valrank_t vr1 = (valrank_t) p1; 195 const valrank_t vr2 = (valrank_t) p2; 196 return vr1->e == vr2->e; 197} 198 199 200/* Initialize the reassociation pass. */ 201 202static void 203init_reassoc (void) 204{ 205 int i; 206 unsigned int rank = 2; 207 208 tree param; 209 int *bbs = xmalloc ((last_basic_block + 1) * sizeof (int)); 210 211 memset (&reassociate_stats, 0, sizeof (reassociate_stats)); 212 213 /* Reverse RPO (Reverse Post Order) will give us something where 214 deeper loops come later. */ 215 flow_reverse_top_sort_order_compute (bbs); 216 bb_rank = xcalloc (last_basic_block + 1, sizeof (unsigned int)); 217 value_rank = htab_create (511, valrank_hash, 218 valrank_eq, free); 219 seen_binops = htab_create (511, seen_binop_hash, 220 seen_binop_eq, free); 221 222 /* Give each argument a distinct rank. */ 223 for (param = DECL_ARGUMENTS (current_function_decl); 224 param; 225 param = TREE_CHAIN (param)) 226 { 227 if (default_def (param) != NULL) 228 { 229 tree def = default_def (param); 230 insert_value_rank (def, ++rank); 231 } 232 } 233 /* Give the chain decl a distinct rank. */ 234 if (cfun->static_chain_decl != NULL) 235 { 236 tree def = default_def (cfun->static_chain_decl); 237 if (def != NULL) 238 insert_value_rank (def, ++rank); 239 } 240 241 /* Set up rank for each BB */ 242 for (i = 0; i < n_basic_blocks; i++) 243 bb_rank[bbs[i]] = ++rank << 16; 244 245 free (bbs); 246 calculate_dominance_info (CDI_DOMINATORS); 247 248} 249 250/* Cleanup after the reassociation pass, and print stats if 251 requested. */ 252 253static void 254fini_reassoc (void) 255{ 256 257 if (dump_file && (dump_flags & TDF_STATS)) 258 { 259 fprintf (dump_file, "Reassociation stats:\n"); 260 fprintf (dump_file, "Reassociated by rank: %d\n", reassociate_stats.reassociated_by_rank); 261 fprintf (dump_file, "Reassociated by match: %d\n", reassociate_stats.reassociated_by_match); 262 } 263 htab_delete (value_rank); 264 htab_delete (seen_binops); 265 free (bb_rank); 266} 267 268/* Given an expression E, return the rank of the expression. */ 269 270static unsigned int 271get_rank (tree e) 272{ 273 valrank_t vr; 274 275 /* Constants have rank 0. */ 276 if (is_gimple_min_invariant (e)) 277 return 0; 278 279 /* SSA_NAME's have the rank of the expression they are the result 280 of. 281 For globals and uninitialized values, the rank is 0. 282 For function arguments, use the pre-setup rank. 283 For PHI nodes, stores, asm statements, etc, we use the rank of 284 the BB. 285 For simple operations, the rank is the maximum rank of any of 286 its operands, or the bb_rank, whichever is less. 287 I make no claims that this is optimal, however, it gives good 288 results. */ 289 290 if (TREE_CODE (e) == SSA_NAME) 291 { 292 tree stmt; 293 tree rhs; 294 unsigned int rank, maxrank; 295 int i; 296 297 if (TREE_CODE (SSA_NAME_VAR (e)) == PARM_DECL 298 && e == default_def (SSA_NAME_VAR (e))) 299 return find_value_rank (e)->rank; 300 301 stmt = SSA_NAME_DEF_STMT (e); 302 if (bb_for_stmt (stmt) == NULL) 303 return 0; 304 305 if (TREE_CODE (stmt) != MODIFY_EXPR 306 || !ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS)) 307 return bb_rank[bb_for_stmt (stmt)->index]; 308 309 /* If we already have a rank for this expression, use that. */ 310 vr = find_value_rank (e); 311 if (vr) 312 return vr->rank; 313 314 /* Otherwise, find the maximum rank for the operands, or the bb 315 rank, whichever is less. */ 316 rank = 0; 317 maxrank = bb_rank[bb_for_stmt(stmt)->index]; 318 rhs = TREE_OPERAND (stmt, 1); 319 if (TREE_CODE_LENGTH (TREE_CODE (rhs)) == 0) 320 rank = MAX (rank, get_rank (rhs)); 321 else 322 { 323 for (i = 0; 324 i < TREE_CODE_LENGTH (TREE_CODE (rhs)) 325 && TREE_OPERAND (rhs, i) 326 && rank != maxrank; i++) 327 rank = MAX(rank, get_rank (TREE_OPERAND (rhs, i))); 328 } 329 330 if (dump_file && (dump_flags & TDF_DETAILS)) 331 { 332 fprintf (dump_file, "Rank for "); 333 print_generic_expr (dump_file, e, 0); 334 fprintf (dump_file, " is %d\n", (rank + 1)); 335 } 336 337 /* Note the rank in the hashtable so we don't recompute it. */ 338 insert_value_rank (e, (rank + 1)); 339 return (rank + 1); 340 } 341 342 /* Globals, etc, are rank 0 */ 343 return 0; 344} 345 346 347/* Decide whether we should transpose RHS and some operand of 348 LHSDEFOP. 349 If yes, then return true and set TAKEOP to the operand number of LHSDEFOP to 350 switch RHS for. 351 Otherwise, return false. */ 352 353static bool 354should_transpose (tree rhs ATTRIBUTE_UNUSED, 355 unsigned int rhsrank, 356 tree lhsdefop, unsigned int *takeop) 357{ 358 /* Attempt to expose the low ranked 359 arguments to CSE if we have something like: 360 a = <rank 2> + c (rank 1) 361 b = a (rank 3) + d (rank 1) 362 We want to transform this into: 363 a = c + d 364 b = <rank 2> + <rank 3> 365 366 The op finding part wouldn't be necessary if 367 we could swap the operands above and not have 368 update_stmt change them back on us. 369 */ 370 unsigned int lowrankop; 371 unsigned int lowrank; 372 unsigned int highrank; 373 unsigned int highrankop; 374 unsigned int temp; 375 376 lowrankop = 0; 377 *takeop = 1; 378 lowrank = get_rank (TREE_OPERAND (lhsdefop, 0)); 379 temp = get_rank (TREE_OPERAND (lhsdefop, 1)); 380 highrank = temp; 381 highrankop = 1; 382 if (temp < lowrank) 383 { 384 lowrankop = 1; 385 highrankop = 0; 386 *takeop = 0; 387 highrank = lowrank; 388 lowrank = temp; 389 } 390 391 /* If highrank == lowrank, then we had something 392 like: 393 a = <rank 1> + <rank 1> 394 already, so there is no guarantee that 395 swapping our argument in is going to be 396 better. 397 If we run reassoc twice, we could probably 398 have a flag that switches this behavior on, 399 so that we try once without it, and once with 400 it, so that redundancy elimination sees it 401 both ways. 402 */ 403 404 if (lowrank == rhsrank && highrank != lowrank) 405 return true; 406 407 /* Also, see if the LHS's high ranked op should be switched with our 408 RHS simply because it is greater in rank than our current RHS. */ 409 if (TREE_CODE (TREE_OPERAND (lhsdefop, highrankop)) == SSA_NAME) 410 { 411 tree iop = SSA_NAME_DEF_STMT (TREE_OPERAND (lhsdefop, highrankop)); 412 if (TREE_CODE (iop) == MODIFY_EXPR) 413 iop = TREE_OPERAND (iop, 1); 414 if (TREE_CODE (iop) == TREE_CODE (lhsdefop)) 415 *takeop = 1; 416 if (rhsrank < get_rank (TREE_OPERAND (lhsdefop, *takeop))) 417 return true; 418 } 419 420 return false; 421} 422 423/* Attempt to reassociate the associative binary operator BEXPR, which 424 is in the statement pointed to by CURRBSI. Return true if we 425 changed the statement. */ 426 427static bool 428reassociate_expr (tree bexpr, block_stmt_iterator *currbsi) 429{ 430 tree lhs = TREE_OPERAND (bexpr, 0); 431 tree rhs = TREE_OPERAND (bexpr, 1); 432 tree lhsdef; 433 tree lhsi; 434 bool changed = false; 435 unsigned int lhsrank = get_rank (lhs); 436 unsigned int rhsrank = get_rank (rhs); 437 438 /* If unsafe math optimizations we can do reassociation for non-integral 439 types. */ 440 if ((!INTEGRAL_TYPE_P (TREE_TYPE (lhs)) 441 || !INTEGRAL_TYPE_P (TREE_TYPE (rhs))) 442 && (!SCALAR_FLOAT_TYPE_P (TREE_TYPE (rhs)) 443 || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(lhs)) 444 || !flag_unsafe_math_optimizations)) 445 return false; 446 447 /* We want the greater ranked operand to be our "LHS" for simplicity 448 sake. There is no point in actually modifying the expression, as 449 update_stmt will simply resort the operands anyway. */ 450 if (lhsrank < rhsrank) 451 { 452 tree temp; 453 unsigned int temp1; 454 temp = lhs; 455 lhs = rhs; 456 rhs = temp; 457 temp1 = lhsrank; 458 lhsrank = rhsrank; 459 rhsrank = temp1; 460 } 461 462 /* If the high ranked operand is an SSA_NAME, and the binary 463 operator is not something we've already seen somewhere else 464 (i.e., it may be redundant), attempt to reassociate it. 465 466 We can't reassociate expressions unless the expression we are 467 going to reassociate with is only used in our current expression, 468 or else we may screw up other computations, like so: 469 470 a = b + c 471 e = a + d 472 473 g = a + f 474 475 We cannot reassociate and rewrite the "a = ..." , 476 because that would change the value of the computation of 477 "g = a + f". */ 478 if (TREE_CODE (lhs) == SSA_NAME && !find_seen_binop (lhs, rhs)) 479 { 480 lhsdef = SSA_NAME_DEF_STMT (lhs); 481 if (TREE_CODE (lhsdef) == MODIFY_EXPR) 482 { 483 lhsi = TREE_OPERAND (lhsdef, 1); 484 if (TREE_CODE (lhsi) == TREE_CODE (bexpr)) 485 { 486 use_operand_p use; 487 tree usestmt; 488 if (single_imm_use (lhs, &use, &usestmt)) 489 { 490 unsigned int takeop = 0; 491 unsigned int otherop = 1; 492 bool foundmatch = false; 493 bool foundrank = false; 494 495 /* If we can easily transpose this into an operation 496 we've already seen, let's do that. 497 otherwise, let's try to expose low ranked ops to 498 CSE. */ 499 if (find_seen_binop (TREE_OPERAND (lhsi, 1), rhs)) 500 { 501 takeop = 0; 502 otherop = 1; 503 foundmatch = true; 504 } 505 else if (find_seen_binop (TREE_OPERAND (lhsi, 0), 506 rhs)) 507 { 508 takeop = 1; 509 otherop = 0; 510 foundmatch = true; 511 } 512 else if (should_transpose (rhs, rhsrank, lhsi, 513 &takeop)) 514 { 515 foundrank = true; 516 } 517 if (foundmatch || foundrank) 518 { 519 block_stmt_iterator lhsbsi = bsi_for_stmt (lhsdef); 520 if (dump_file && (dump_flags & TDF_DETAILS)) 521 { 522 fprintf (dump_file, "Reassociating by %s\n", 523 foundmatch ? "match" : "rank"); 524 fprintf (dump_file, "Before LHS:"); 525 print_generic_stmt (dump_file, lhsi, 0); 526 fprintf (dump_file, "Before curr expr:"); 527 print_generic_stmt (dump_file, bexpr, 0); 528 } 529 TREE_OPERAND (bexpr, 0) = TREE_OPERAND (lhsi, takeop); 530 TREE_OPERAND (lhsi, takeop) = rhs; 531 TREE_OPERAND (bexpr, 1) = TREE_OPERAND (lhsdef, 0); 532 if (dump_file && (dump_flags & TDF_DETAILS)) 533 { 534 fprintf (dump_file, "After LHS:"); 535 print_generic_stmt (dump_file, lhsi, 0); 536 fprintf (dump_file, "After curr expr:"); 537 print_generic_stmt (dump_file, bexpr, 0); 538 } 539 bsi_move_before (&lhsbsi, currbsi); 540 update_stmt (lhsdef); 541 update_stmt (bsi_stmt (*currbsi)); 542 lhsbsi = bsi_for_stmt (lhsdef); 543 update_stmt (bsi_stmt (lhsbsi)); 544 545 /* If update_stmt didn't reorder our operands, 546 we'd like to recurse on the expression we 547 just reassociated and reassociate it 548 top-down, exposing further opportunities. 549 Unfortunately, update_stmt does reorder them, 550 so we can't do this cheaply. */ 551 if (!foundmatch) 552 reassociate_stats.reassociated_by_rank++; 553 else 554 reassociate_stats.reassociated_by_match++; 555 return true; 556 } 557 } 558 } 559 } 560 } 561 return changed; 562} 563 564/* Reassociate expressions in basic block BB and its dominator as 565 children , return true if any 566 expressions changed. */ 567 568static bool 569reassociate_bb (basic_block bb) 570{ 571 bool changed = false; 572 block_stmt_iterator bsi; 573 basic_block son; 574 575 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 576 { 577 tree stmt = bsi_stmt (bsi); 578 579 if (TREE_CODE (stmt) == MODIFY_EXPR) 580 { 581 tree rhs = TREE_OPERAND (stmt, 1); 582 if (associative_tree_code (TREE_CODE (rhs))) 583 { 584 if (reassociate_expr (rhs, &bsi)) 585 { 586 changed = true; 587 update_stmt (stmt); 588 } 589 insert_seen_binop (TREE_OPERAND (rhs, 0), 590 TREE_OPERAND (rhs, 1)); 591 } 592 } 593 } 594 for (son = first_dom_son (CDI_DOMINATORS, bb); 595 son; 596 son = next_dom_son (CDI_DOMINATORS, son)) 597 { 598 changed |= reassociate_bb (son); 599 } 600 return changed; 601} 602 603 604static bool 605do_reassoc (void) 606{ 607 bool changed = false; 608 609 changed = reassociate_bb (ENTRY_BLOCK_PTR); 610 611 return changed; 612} 613 614 615/* Gate and execute functions for Reassociation. */ 616 617static void 618execute_reassoc (void) 619{ 620 init_reassoc (); 621 do_reassoc (); 622 fini_reassoc (); 623} 624 625struct tree_opt_pass pass_reassoc = 626{ 627 "reassoc", /* name */ 628 NULL, /* gate */ 629 execute_reassoc, /* execute */ 630 NULL, /* sub */ 631 NULL, /* next */ 632 0, /* static_pass_number */ 633 TV_TREE_REASSOC, /* tv_id */ 634 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ 635 0, /* properties_provided */ 636 0, /* properties_destroyed */ 637 0, /* todo_flags_start */ 638 TODO_update_ssa | TODO_dump_func 639 | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */ 640 0 /* letter */ 641}; 642