1 /* Routines for performing Temporary Expression Replacement (TER) in SSA trees. 2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011 3 Free Software Foundation, Inc. 4 Contributed by Andrew MacLeod <amacleod@redhat.com> 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 23 #include "config.h" 24 #include "system.h" 25 #include "coretypes.h" 26 #include "tm.h" 27 #include "tree.h" 28 #include "tree-pretty-print.h" 29 #include "gimple-pretty-print.h" 30 #include "bitmap.h" 31 #include "tree-flow.h" 32 #include "tree-dump.h" 33 #include "tree-ssa-live.h" 34 #include "flags.h" 35 36 37 /* Temporary Expression Replacement (TER) 38 39 Replace SSA version variables during out-of-ssa with their defining 40 expression if there is only one use of the variable. 41 42 This pass is required in order for the RTL expansion pass to see larger 43 chunks of code. This allows it to make better choices on RTL pattern 44 selection. When expand is rewritten and merged with out-of-ssa, and 45 understands SSA, this should be eliminated. 46 47 A pass is made through the function, one block at a time. No cross block 48 information is tracked. 49 50 Variables which only have one use, and whose defining stmt is considered 51 a replaceable expression (see is_replaceable_p) are tracked to see whether 52 they can be replaced at their use location. 53 54 n_12 = C * 10 55 a_2 = b_5 + 6 56 v_9 = a_2 * n_12 57 58 if there are the only use of n_12 and a_2, TER will substitute in their 59 expressions in v_9, and end up with: 60 61 v_9 = (b_5 + 6) * (C * 10) 62 63 which will then have the ssa_name assigned to regular variables, and the 64 resulting code which will be passed to the expander looks something like: 65 66 v = (b + 6) * (C * 10) 67 68 69 This requires ensuring that none of the variables used by the expression 70 change between the def point and where it is used. Furthermore, if any 71 of the ssa_names used in this expression are themselves replaceable, we 72 have to ensure none of that expressions' arguments change either. 73 Although SSA_NAMES themselves don't change, this pass is performed after 74 coalescing has coalesced different SSA_NAMES together, so there could be a 75 definition of an SSA_NAME which is coalesced with a use that causes a 76 problem, i.e., 77 78 PHI b_5 = <b_8(2), b_14(1)> 79 <...> 80 a_2 = b_5 + 6 81 b_8 = c_4 + 4 82 v_9 = a_2 * n_12 83 <...> 84 85 If b_5, b_8 and b_14 are all coalesced together... 86 The expression b_5 + 6 CANNOT replace the use in the statement defining v_9 87 because b_8 is in fact killing the value of b_5 since they share a partition 88 and will be assigned the same memory or register location. 89 90 TER implements this but stepping through the instructions in a block and 91 tracking potential expressions for replacement, and the partitions they are 92 dependent on. Expressions are represented by the SSA_NAME_VERSION of the 93 DEF on the LHS of a GIMPLE_ASSIGN and the expression is the RHS. 94 95 When a stmt is determined to be a possible replacement expression, the 96 following steps are taken: 97 98 EXPR_DECL_UID bitmap is allocated and set to the base variable UID of the 99 def and any uses in the expression. non-NULL means the expression is being 100 tracked. The UID's themselves are used to prevent TER substitution into 101 accumulating sequences, i.e., 102 103 x = x + y 104 x = x + z 105 x = x + w 106 etc. 107 this can result in very large expressions which don't accomplish anything 108 see PR tree-optimization/17549. 109 110 PARTITION_DEPENDENCIES is another bitmap array, and it has a bit set for any 111 partition which is used in the expression. This is primarily used to remove 112 an expression from the partition kill lists when a decision is made whether 113 to replace it or not. This is indexed by ssa version number as well, and 114 indicates a partition number. virtual operands are not tracked individually, 115 but they are summarized by an artificial partition called VIRTUAL_PARTITION. 116 This means a MAY or MUST def will kill *ALL* expressions that are dependent 117 on a virtual operand. 118 Note that the EXPR_DECL_UID and this bitmap represent very similar 119 information, but the info in one is not easy to obtain from the other. 120 121 KILL_LIST is yet another bitmap array, this time it is indexed by partition 122 number, and represents a list of active expressions which will will no 123 longer be valid if a definition into this partition takes place. 124 125 PARTITION_IN_USE is simply a bitmap which is used to track which partitions 126 currently have something in their kill list. This is used at the end of 127 a block to clear out the KILL_LIST bitmaps at the end of each block. 128 129 NEW_REPLACEABLE_DEPENDENCIES is used as a temporary place to store 130 dependencies which will be reused by the current definition. All the uses 131 on an expression are processed before anything else is done. If a use is 132 determined to be a replaceable expression AND the current stmt is also going 133 to be replaceable, all the dependencies of this replaceable use will be 134 picked up by the current stmt's expression. Rather than recreate them, they 135 are simply copied here and then copied into the new expression when it is 136 processed. 137 138 a_2 = b_5 + 6 139 v_8 = a_2 + c_4 140 141 a_2's expression 'b_5 + 6' is determined to be replaceable at the use 142 location. It is dependent on the partition 'b_5' is in. This is cached into 143 the NEW_REPLACEABLE_DEPENDENCIES bitmap, and when v_8 is examined for 144 replaceability, it is a candidate, and it is dependent on the partition 145 b_5 is in *NOT* a_2, as well as c_4's partition. 146 147 if v_8 is also replaceable: 148 149 x_9 = v_8 * 5 150 151 x_9 is dependent on partitions b_5, and c_4 152 153 if a statement is found which has either of those partitions written to 154 before x_9 is used, then x_9 itself is NOT replaceable. */ 155 156 157 /* Temporary Expression Replacement (TER) table information. */ 158 159 typedef struct temp_expr_table_d 160 { 161 var_map map; 162 bitmap *partition_dependencies; /* Partitions expr is dependent on. */ 163 bitmap replaceable_expressions; /* Replacement expression table. */ 164 bitmap *expr_decl_uids; /* Base uids of exprs. */ 165 bitmap *kill_list; /* Expr's killed by a partition. */ 166 int virtual_partition; /* Pseudo partition for virtual ops. */ 167 bitmap partition_in_use; /* Partitions with kill entries. */ 168 bitmap new_replaceable_dependencies; /* Holding place for pending dep's. */ 169 int *num_in_part; /* # of ssa_names in a partition. */ 170 int *call_cnt; /* Call count at definition. */ 171 } *temp_expr_table_p; 172 173 /* Used to indicate a dependency on VDEFs. */ 174 #define VIRTUAL_PARTITION(table) (table->virtual_partition) 175 176 #ifdef ENABLE_CHECKING 177 extern void debug_ter (FILE *, temp_expr_table_p); 178 #endif 179 180 181 /* Create a new TER table for MAP. */ 182 183 static temp_expr_table_p 184 new_temp_expr_table (var_map map) 185 { 186 temp_expr_table_p t; 187 unsigned x; 188 189 t = XNEW (struct temp_expr_table_d); 190 t->map = map; 191 192 t->partition_dependencies = XCNEWVEC (bitmap, num_ssa_names + 1); 193 t->expr_decl_uids = XCNEWVEC (bitmap, num_ssa_names + 1); 194 t->kill_list = XCNEWVEC (bitmap, num_var_partitions (map) + 1); 195 196 t->partition_in_use = BITMAP_ALLOC (NULL); 197 198 t->virtual_partition = num_var_partitions (map); 199 t->new_replaceable_dependencies = BITMAP_ALLOC (NULL); 200 201 t->replaceable_expressions = NULL; 202 t->num_in_part = XCNEWVEC (int, num_var_partitions (map)); 203 for (x = 1; x < num_ssa_names; x++) 204 { 205 int p; 206 tree name = ssa_name (x); 207 if (!name) 208 continue; 209 p = var_to_partition (map, name); 210 if (p != NO_PARTITION) 211 t->num_in_part[p]++; 212 } 213 t->call_cnt = XCNEWVEC (int, num_ssa_names + 1); 214 215 return t; 216 } 217 218 219 /* Free TER table T. If there are valid replacements, return the expression 220 vector. */ 221 222 static bitmap 223 free_temp_expr_table (temp_expr_table_p t) 224 { 225 bitmap ret = NULL; 226 227 #ifdef ENABLE_CHECKING 228 unsigned x; 229 for (x = 0; x <= num_var_partitions (t->map); x++) 230 gcc_assert (!t->kill_list[x]); 231 for (x = 0; x < num_ssa_names; x++) 232 { 233 gcc_assert (t->expr_decl_uids[x] == NULL); 234 gcc_assert (t->partition_dependencies[x] == NULL); 235 } 236 #endif 237 238 BITMAP_FREE (t->partition_in_use); 239 BITMAP_FREE (t->new_replaceable_dependencies); 240 241 free (t->expr_decl_uids); 242 free (t->kill_list); 243 free (t->partition_dependencies); 244 free (t->num_in_part); 245 free (t->call_cnt); 246 247 if (t->replaceable_expressions) 248 ret = t->replaceable_expressions; 249 250 free (t); 251 return ret; 252 } 253 254 255 /* Return TRUE if VERSION is to be replaced by an expression in TAB. */ 256 257 static inline bool 258 version_to_be_replaced_p (temp_expr_table_p tab, int version) 259 { 260 if (!tab->replaceable_expressions) 261 return false; 262 return bitmap_bit_p (tab->replaceable_expressions, version); 263 } 264 265 266 /* Add partition P to the list if partitions VERSION is dependent on. TAB is 267 the expression table */ 268 269 static inline void 270 make_dependent_on_partition (temp_expr_table_p tab, int version, int p) 271 { 272 if (!tab->partition_dependencies[version]) 273 tab->partition_dependencies[version] = BITMAP_ALLOC (NULL); 274 275 bitmap_set_bit (tab->partition_dependencies[version], p); 276 } 277 278 279 /* Add VER to the kill list for P. TAB is the expression table */ 280 281 static inline void 282 add_to_partition_kill_list (temp_expr_table_p tab, int p, int ver) 283 { 284 if (!tab->kill_list[p]) 285 { 286 tab->kill_list[p] = BITMAP_ALLOC (NULL); 287 bitmap_set_bit (tab->partition_in_use, p); 288 } 289 bitmap_set_bit (tab->kill_list[p], ver); 290 } 291 292 293 /* Remove VER from the partition kill list for P. TAB is the expression 294 table. */ 295 296 static inline void 297 remove_from_partition_kill_list (temp_expr_table_p tab, int p, int version) 298 { 299 gcc_checking_assert (tab->kill_list[p]); 300 bitmap_clear_bit (tab->kill_list[p], version); 301 if (bitmap_empty_p (tab->kill_list[p])) 302 { 303 bitmap_clear_bit (tab->partition_in_use, p); 304 BITMAP_FREE (tab->kill_list[p]); 305 } 306 } 307 308 309 /* Add a dependency between the def of ssa VERSION and VAR. If VAR is 310 replaceable by an expression, add a dependence each of the elements of the 311 expression. These are contained in the new_replaceable list. TAB is the 312 expression table. */ 313 314 static void 315 add_dependence (temp_expr_table_p tab, int version, tree var) 316 { 317 int i; 318 bitmap_iterator bi; 319 unsigned x; 320 321 i = SSA_NAME_VERSION (var); 322 if (version_to_be_replaced_p (tab, i)) 323 { 324 if (!bitmap_empty_p (tab->new_replaceable_dependencies)) 325 { 326 /* Version will now be killed by a write to any partition the 327 substituted expression would have been killed by. */ 328 EXECUTE_IF_SET_IN_BITMAP (tab->new_replaceable_dependencies, 0, x, bi) 329 add_to_partition_kill_list (tab, x, version); 330 331 /* Rather than set partition_dependencies and in_use lists bit by 332 bit, simply OR in the new_replaceable_dependencies bits. */ 333 if (!tab->partition_dependencies[version]) 334 tab->partition_dependencies[version] = BITMAP_ALLOC (NULL); 335 bitmap_ior_into (tab->partition_dependencies[version], 336 tab->new_replaceable_dependencies); 337 bitmap_ior_into (tab->partition_in_use, 338 tab->new_replaceable_dependencies); 339 /* It is only necessary to add these once. */ 340 bitmap_clear (tab->new_replaceable_dependencies); 341 } 342 } 343 else 344 { 345 i = var_to_partition (tab->map, var); 346 gcc_checking_assert (i != NO_PARTITION); 347 gcc_checking_assert (tab->num_in_part[i] != 0); 348 /* Only dependencies on ssa_names which are coalesced with something need 349 to be tracked. Partitions with containing only a single SSA_NAME 350 *cannot* have their value changed. */ 351 if (tab->num_in_part[i] > 1) 352 { 353 add_to_partition_kill_list (tab, i, version); 354 make_dependent_on_partition (tab, version, i); 355 } 356 } 357 } 358 359 360 /* Return TRUE if expression STMT is suitable for replacement. 361 TER is true if is_replaceable_p is called from within TER, false 362 when used from within stmt_is_replaceable_p, i.e. EXPAND_INITIALIZER 363 expansion. The differences are that with !TER some tests are skipped 364 to make it more aggressive (doesn't require the same bb, or for -O0 365 same locus and same BLOCK), on the other side never considers memory 366 loads as replaceable, because those don't ever lead into constant 367 expressions. */ 368 369 static inline bool 370 is_replaceable_p (gimple stmt, bool ter) 371 { 372 use_operand_p use_p; 373 tree def; 374 gimple use_stmt; 375 location_t locus1, locus2; 376 tree block1, block2; 377 378 /* Only consider modify stmts. */ 379 if (!is_gimple_assign (stmt)) 380 return false; 381 382 /* If the statement may throw an exception, it cannot be replaced. */ 383 if (stmt_could_throw_p (stmt)) 384 return false; 385 386 /* Punt if there is more than 1 def. */ 387 def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF); 388 if (!def) 389 return false; 390 391 /* Only consider definitions which have a single use. */ 392 if (!single_imm_use (def, &use_p, &use_stmt)) 393 return false; 394 395 /* If the use isn't in this block, it wont be replaced either. */ 396 if (ter && gimple_bb (use_stmt) != gimple_bb (stmt)) 397 return false; 398 399 locus1 = gimple_location (stmt); 400 block1 = gimple_block (stmt); 401 402 if (gimple_code (use_stmt) == GIMPLE_PHI) 403 { 404 locus2 = 0; 405 block2 = NULL_TREE; 406 } 407 else 408 { 409 locus2 = gimple_location (use_stmt); 410 block2 = gimple_block (use_stmt); 411 } 412 413 if (!optimize 414 && ter 415 && ((locus1 && locus1 != locus2) || (block1 && block1 != block2))) 416 return false; 417 418 /* Used in this block, but at the TOP of the block, not the end. */ 419 if (gimple_code (use_stmt) == GIMPLE_PHI) 420 return false; 421 422 /* There must be no VDEFs. */ 423 if (gimple_vdef (stmt)) 424 return false; 425 426 /* Without alias info we can't move around loads. */ 427 if ((!optimize || !ter) 428 && gimple_assign_single_p (stmt) 429 && !is_gimple_val (gimple_assign_rhs1 (stmt))) 430 return false; 431 432 /* Float expressions must go through memory if float-store is on. */ 433 if (flag_float_store 434 && FLOAT_TYPE_P (gimple_expr_type (stmt))) 435 return false; 436 437 /* An assignment with a register variable on the RHS is not 438 replaceable. */ 439 if (gimple_assign_rhs_code (stmt) == VAR_DECL 440 && DECL_HARD_REGISTER (gimple_assign_rhs1 (stmt))) 441 return false; 442 443 /* No function calls can be replaced. */ 444 if (is_gimple_call (stmt)) 445 return false; 446 447 /* Leave any stmt with volatile operands alone as well. */ 448 if (gimple_has_volatile_ops (stmt)) 449 return false; 450 451 return true; 452 } 453 454 455 /* Variant of is_replaceable_p test for use in EXPAND_INITIALIZER 456 expansion. */ 457 458 bool 459 stmt_is_replaceable_p (gimple stmt) 460 { 461 return is_replaceable_p (stmt, false); 462 } 463 464 465 /* This function will remove the expression for VERSION from replacement 466 consideration in table TAB. If FREE_EXPR is true, then remove the 467 expression from consideration as well by freeing the decl uid bitmap. */ 468 469 static void 470 finished_with_expr (temp_expr_table_p tab, int version, bool free_expr) 471 { 472 unsigned i; 473 bitmap_iterator bi; 474 475 /* Remove this expression from its dependent lists. The partition dependence 476 list is retained and transfered later to whomever uses this version. */ 477 if (tab->partition_dependencies[version]) 478 { 479 EXECUTE_IF_SET_IN_BITMAP (tab->partition_dependencies[version], 0, i, bi) 480 remove_from_partition_kill_list (tab, i, version); 481 BITMAP_FREE (tab->partition_dependencies[version]); 482 } 483 if (free_expr) 484 BITMAP_FREE (tab->expr_decl_uids[version]); 485 } 486 487 488 /* Create an expression entry for a replaceable expression. */ 489 490 static void 491 process_replaceable (temp_expr_table_p tab, gimple stmt, int call_cnt) 492 { 493 tree var, def, basevar; 494 int version; 495 ssa_op_iter iter; 496 bitmap def_vars, use_vars; 497 498 gcc_checking_assert (is_replaceable_p (stmt, true)); 499 500 def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF); 501 version = SSA_NAME_VERSION (def); 502 basevar = SSA_NAME_VAR (def); 503 def_vars = BITMAP_ALLOC (NULL); 504 505 bitmap_set_bit (def_vars, DECL_UID (basevar)); 506 507 /* Add this expression to the dependency list for each use partition. */ 508 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE) 509 { 510 int var_version = SSA_NAME_VERSION (var); 511 512 use_vars = tab->expr_decl_uids[var_version]; 513 add_dependence (tab, version, var); 514 if (use_vars) 515 { 516 bitmap_ior_into (def_vars, use_vars); 517 BITMAP_FREE (tab->expr_decl_uids[var_version]); 518 } 519 else 520 bitmap_set_bit (def_vars, DECL_UID (SSA_NAME_VAR (var))); 521 } 522 tab->expr_decl_uids[version] = def_vars; 523 524 /* If there are VUSES, add a dependence on virtual defs. */ 525 if (gimple_vuse (stmt)) 526 { 527 make_dependent_on_partition (tab, version, VIRTUAL_PARTITION (tab)); 528 add_to_partition_kill_list (tab, VIRTUAL_PARTITION (tab), version); 529 } 530 531 tab->call_cnt[version] = call_cnt; 532 } 533 534 535 /* This function removes any expression in TAB which is dependent on PARTITION 536 from consideration, making it not replaceable. */ 537 538 static inline void 539 kill_expr (temp_expr_table_p tab, int partition) 540 { 541 unsigned version; 542 543 /* Mark every active expr dependent on this var as not replaceable. 544 finished_with_expr can modify the bitmap, so we can't execute over it. */ 545 while (tab->kill_list[partition]) 546 { 547 version = bitmap_first_set_bit (tab->kill_list[partition]); 548 finished_with_expr (tab, version, true); 549 } 550 551 gcc_checking_assert (!tab->kill_list[partition]); 552 } 553 554 555 /* This function kills all expressions in TAB which are dependent on virtual 556 partitions. */ 557 558 static inline void 559 kill_virtual_exprs (temp_expr_table_p tab) 560 { 561 kill_expr (tab, VIRTUAL_PARTITION (tab)); 562 } 563 564 565 /* Mark the expression associated with VAR as replaceable, and enter 566 the defining stmt into the partition_dependencies table TAB. If 567 MORE_REPLACING is true, accumulate the pending partition dependencies. */ 568 569 static void 570 mark_replaceable (temp_expr_table_p tab, tree var, bool more_replacing) 571 { 572 int version = SSA_NAME_VERSION (var); 573 574 /* Move the dependence list to the pending listpending. */ 575 if (more_replacing && tab->partition_dependencies[version]) 576 bitmap_ior_into (tab->new_replaceable_dependencies, 577 tab->partition_dependencies[version]); 578 579 finished_with_expr (tab, version, !more_replacing); 580 581 /* Set the replaceable expression. */ 582 if (!tab->replaceable_expressions) 583 tab->replaceable_expressions = BITMAP_ALLOC (NULL); 584 bitmap_set_bit (tab->replaceable_expressions, version); 585 } 586 587 588 /* This function processes basic block BB, and looks for variables which can 589 be replaced by their expressions. Results are stored in the table TAB. */ 590 591 static void 592 find_replaceable_in_bb (temp_expr_table_p tab, basic_block bb) 593 { 594 gimple_stmt_iterator bsi; 595 gimple stmt; 596 tree def, use, fndecl; 597 int partition; 598 var_map map = tab->map; 599 ssa_op_iter iter; 600 bool stmt_replaceable; 601 int cur_call_cnt = 0; 602 603 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) 604 { 605 stmt = gsi_stmt (bsi); 606 607 if (is_gimple_debug (stmt)) 608 continue; 609 610 stmt_replaceable = is_replaceable_p (stmt, true); 611 612 /* Determine if this stmt finishes an existing expression. */ 613 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) 614 { 615 unsigned ver = SSA_NAME_VERSION (use); 616 617 /* If this use is a potential replacement variable, process it. */ 618 if (tab->expr_decl_uids[ver]) 619 { 620 bool same_root_var = false; 621 ssa_op_iter iter2; 622 bitmap vars = tab->expr_decl_uids[ver]; 623 624 /* See if the root variables are the same. If they are, we 625 do not want to do the replacement to avoid problems with 626 code size, see PR tree-optimization/17549. */ 627 if (!bitmap_empty_p (vars)) 628 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter2, SSA_OP_DEF) 629 { 630 if (bitmap_bit_p (vars, DECL_UID (SSA_NAME_VAR (def)))) 631 { 632 same_root_var = true; 633 break; 634 } 635 } 636 637 /* If the stmt does a memory store and the replacement 638 is a load aliasing it avoid creating overlapping 639 assignments which we cannot expand correctly. */ 640 if (gimple_vdef (stmt) 641 && gimple_assign_single_p (stmt)) 642 { 643 gimple def_stmt = SSA_NAME_DEF_STMT (use); 644 while (is_gimple_assign (def_stmt) 645 && gimple_assign_rhs_code (def_stmt) == SSA_NAME) 646 def_stmt 647 = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (def_stmt)); 648 if (gimple_vuse (def_stmt) 649 && gimple_assign_single_p (def_stmt) 650 && refs_may_alias_p (gimple_assign_lhs (stmt), 651 gimple_assign_rhs1 (def_stmt))) 652 same_root_var = true; 653 } 654 655 /* Mark expression as replaceable unless stmt is volatile, or the 656 def variable has the same root variable as something in the 657 substitution list, or the def and use span a call such that 658 we'll expand lifetimes across a call. */ 659 if (gimple_has_volatile_ops (stmt) || same_root_var 660 || (tab->call_cnt[ver] != cur_call_cnt 661 && SINGLE_SSA_USE_OPERAND (SSA_NAME_DEF_STMT (use), SSA_OP_USE) 662 == NULL_USE_OPERAND_P)) 663 finished_with_expr (tab, ver, true); 664 else 665 mark_replaceable (tab, use, stmt_replaceable); 666 } 667 } 668 669 /* Next, see if this stmt kills off an active expression. */ 670 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF) 671 { 672 partition = var_to_partition (map, def); 673 if (partition != NO_PARTITION && tab->kill_list[partition]) 674 kill_expr (tab, partition); 675 } 676 677 /* Increment counter if this is a non BUILT_IN call. We allow 678 replacement over BUILT_IN calls since many will expand to inline 679 insns instead of a true call. */ 680 if (is_gimple_call (stmt) 681 && !((fndecl = gimple_call_fndecl (stmt)) 682 && DECL_BUILT_IN (fndecl))) 683 cur_call_cnt++; 684 685 /* Now see if we are creating a new expression or not. */ 686 if (stmt_replaceable) 687 process_replaceable (tab, stmt, cur_call_cnt); 688 689 /* Free any unused dependency lists. */ 690 bitmap_clear (tab->new_replaceable_dependencies); 691 692 /* A V_{MAY,MUST}_DEF kills any expression using a virtual operand, 693 including the current stmt. */ 694 if (gimple_vdef (stmt)) 695 kill_virtual_exprs (tab); 696 } 697 } 698 699 700 /* This function is the driver routine for replacement of temporary expressions 701 in the SSA->normal phase, operating on MAP. If there are replaceable 702 expressions, a table is returned which maps SSA versions to the 703 expressions they should be replaced with. A NULL_TREE indicates no 704 replacement should take place. If there are no replacements at all, 705 NULL is returned by the function, otherwise an expression vector indexed 706 by SSA_NAME version numbers. */ 707 708 extern bitmap 709 find_replaceable_exprs (var_map map) 710 { 711 basic_block bb; 712 temp_expr_table_p table; 713 bitmap ret; 714 715 table = new_temp_expr_table (map); 716 FOR_EACH_BB (bb) 717 { 718 find_replaceable_in_bb (table, bb); 719 gcc_checking_assert (bitmap_empty_p (table->partition_in_use)); 720 } 721 722 ret = free_temp_expr_table (table); 723 return ret; 724 } 725 726 /* Dump TER expression table EXPR to file F. */ 727 728 void 729 dump_replaceable_exprs (FILE *f, bitmap expr) 730 { 731 tree var; 732 unsigned x; 733 734 fprintf (f, "\nReplacing Expressions\n"); 735 for (x = 0; x < num_ssa_names; x++) 736 if (bitmap_bit_p (expr, x)) 737 { 738 var = ssa_name (x); 739 print_generic_expr (f, var, TDF_SLIM); 740 fprintf (f, " replace with --> "); 741 print_gimple_stmt (f, SSA_NAME_DEF_STMT (var), 0, TDF_SLIM); 742 fprintf (f, "\n"); 743 } 744 fprintf (f, "\n"); 745 } 746 747 748 #ifdef ENABLE_CHECKING 749 /* Dump the status of the various tables in the expression table. This is used 750 exclusively to debug TER. F is the place to send debug info and T is the 751 table being debugged. */ 752 753 DEBUG_FUNCTION void 754 debug_ter (FILE *f, temp_expr_table_p t) 755 { 756 unsigned x, y; 757 bitmap_iterator bi; 758 759 fprintf (f, "\nDumping current state of TER\n virtual partition = %d\n", 760 VIRTUAL_PARTITION (t)); 761 if (t->replaceable_expressions) 762 dump_replaceable_exprs (f, t->replaceable_expressions); 763 fprintf (f, "Currently tracking the following expressions:\n"); 764 765 for (x = 1; x < num_ssa_names; x++) 766 if (t->expr_decl_uids[x]) 767 { 768 print_generic_expr (f, ssa_name (x), TDF_SLIM); 769 fprintf (f, " dep-parts : "); 770 if (t->partition_dependencies[x] 771 && !bitmap_empty_p (t->partition_dependencies[x])) 772 { 773 EXECUTE_IF_SET_IN_BITMAP (t->partition_dependencies[x], 0, y, bi) 774 fprintf (f, "P%d ",y); 775 } 776 fprintf (f, " basedecls: "); 777 EXECUTE_IF_SET_IN_BITMAP (t->expr_decl_uids[x], 0, y, bi) 778 fprintf (f, "%d ",y); 779 fprintf (f, " call_cnt : %d",t->call_cnt[x]); 780 fprintf (f, "\n"); 781 } 782 783 bitmap_print (f, t->partition_in_use, "Partitions in use ", 784 "\npartition KILL lists:\n"); 785 786 for (x = 0; x <= num_var_partitions (t->map); x++) 787 if (t->kill_list[x]) 788 { 789 fprintf (f, "Partition %d : ", x); 790 EXECUTE_IF_SET_IN_BITMAP (t->kill_list[x], 0, y, bi) 791 fprintf (f, "_%d ",y); 792 } 793 794 fprintf (f, "\n----------\n"); 795 } 796 #endif 797