1 /* Copy propagation and SSA_NAME replacement support routines. 2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2010 3 Free Software Foundation, Inc. 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify 8 it under the terms of the GNU General Public License as published by 9 the Free Software Foundation; either version 3, or (at your option) 10 any later version. 11 12 GCC is distributed in the hope that it will be useful, 13 but WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 GNU General Public License for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING3. If not see 19 <http://www.gnu.org/licenses/>. */ 20 21 #include "config.h" 22 #include "system.h" 23 #include "coretypes.h" 24 #include "tm.h" 25 #include "tree.h" 26 #include "flags.h" 27 #include "tm_p.h" 28 #include "basic-block.h" 29 #include "output.h" 30 #include "function.h" 31 #include "tree-pretty-print.h" 32 #include "gimple-pretty-print.h" 33 #include "timevar.h" 34 #include "tree-dump.h" 35 #include "tree-flow.h" 36 #include "tree-pass.h" 37 #include "tree-ssa-propagate.h" 38 #include "langhooks.h" 39 #include "cfgloop.h" 40 41 /* This file implements the copy propagation pass and provides a 42 handful of interfaces for performing const/copy propagation and 43 simple expression replacement which keep variable annotations 44 up-to-date. 45 46 We require that for any copy operation where the RHS and LHS have 47 a non-null memory tag the memory tag be the same. It is OK 48 for one or both of the memory tags to be NULL. 49 50 We also require tracking if a variable is dereferenced in a load or 51 store operation. 52 53 We enforce these requirements by having all copy propagation and 54 replacements of one SSA_NAME with a different SSA_NAME to use the 55 APIs defined in this file. */ 56 57 /* Return true if we may propagate ORIG into DEST, false otherwise. */ 58 59 bool 60 may_propagate_copy (tree dest, tree orig) 61 { 62 tree type_d = TREE_TYPE (dest); 63 tree type_o = TREE_TYPE (orig); 64 65 /* If ORIG flows in from an abnormal edge, it cannot be propagated. */ 66 if (TREE_CODE (orig) == SSA_NAME 67 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig)) 68 return false; 69 70 /* If DEST is an SSA_NAME that flows from an abnormal edge, then it 71 cannot be replaced. */ 72 if (TREE_CODE (dest) == SSA_NAME 73 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (dest)) 74 return false; 75 76 /* Do not copy between types for which we *do* need a conversion. */ 77 if (!useless_type_conversion_p (type_d, type_o)) 78 return false; 79 80 /* Propagating virtual operands is always ok. */ 81 if (TREE_CODE (dest) == SSA_NAME && !is_gimple_reg (dest)) 82 { 83 /* But only between virtual operands. */ 84 gcc_assert (TREE_CODE (orig) == SSA_NAME && !is_gimple_reg (orig)); 85 86 return true; 87 } 88 89 /* Anything else is OK. */ 90 return true; 91 } 92 93 /* Like may_propagate_copy, but use as the destination expression 94 the principal expression (typically, the RHS) contained in 95 statement DEST. This is more efficient when working with the 96 gimple tuples representation. */ 97 98 bool 99 may_propagate_copy_into_stmt (gimple dest, tree orig) 100 { 101 tree type_d; 102 tree type_o; 103 104 /* If the statement is a switch or a single-rhs assignment, 105 then the expression to be replaced by the propagation may 106 be an SSA_NAME. Fortunately, there is an explicit tree 107 for the expression, so we delegate to may_propagate_copy. */ 108 109 if (gimple_assign_single_p (dest)) 110 return may_propagate_copy (gimple_assign_rhs1 (dest), orig); 111 else if (gimple_code (dest) == GIMPLE_SWITCH) 112 return may_propagate_copy (gimple_switch_index (dest), orig); 113 114 /* In other cases, the expression is not materialized, so there 115 is no destination to pass to may_propagate_copy. On the other 116 hand, the expression cannot be an SSA_NAME, so the analysis 117 is much simpler. */ 118 119 if (TREE_CODE (orig) == SSA_NAME 120 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig)) 121 return false; 122 123 if (is_gimple_assign (dest)) 124 type_d = TREE_TYPE (gimple_assign_lhs (dest)); 125 else if (gimple_code (dest) == GIMPLE_COND) 126 type_d = boolean_type_node; 127 else if (is_gimple_call (dest) 128 && gimple_call_lhs (dest) != NULL_TREE) 129 type_d = TREE_TYPE (gimple_call_lhs (dest)); 130 else 131 gcc_unreachable (); 132 133 type_o = TREE_TYPE (orig); 134 135 if (!useless_type_conversion_p (type_d, type_o)) 136 return false; 137 138 return true; 139 } 140 141 /* Similarly, but we know that we're propagating into an ASM_EXPR. */ 142 143 bool 144 may_propagate_copy_into_asm (tree dest) 145 { 146 /* Hard register operands of asms are special. Do not bypass. */ 147 return !(TREE_CODE (dest) == SSA_NAME 148 && TREE_CODE (SSA_NAME_VAR (dest)) == VAR_DECL 149 && DECL_HARD_REGISTER (SSA_NAME_VAR (dest))); 150 } 151 152 153 /* Common code for propagate_value and replace_exp. 154 155 Replace use operand OP_P with VAL. FOR_PROPAGATION indicates if the 156 replacement is done to propagate a value or not. */ 157 158 static void 159 replace_exp_1 (use_operand_p op_p, tree val, 160 bool for_propagation ATTRIBUTE_UNUSED) 161 { 162 #if defined ENABLE_CHECKING 163 tree op = USE_FROM_PTR (op_p); 164 165 gcc_assert (!(for_propagation 166 && TREE_CODE (op) == SSA_NAME 167 && TREE_CODE (val) == SSA_NAME 168 && !may_propagate_copy (op, val))); 169 #endif 170 171 if (TREE_CODE (val) == SSA_NAME) 172 SET_USE (op_p, val); 173 else 174 SET_USE (op_p, unsave_expr_now (val)); 175 } 176 177 178 /* Propagate the value VAL (assumed to be a constant or another SSA_NAME) 179 into the operand pointed to by OP_P. 180 181 Use this version for const/copy propagation as it will perform additional 182 checks to ensure validity of the const/copy propagation. */ 183 184 void 185 propagate_value (use_operand_p op_p, tree val) 186 { 187 replace_exp_1 (op_p, val, true); 188 } 189 190 /* Replace *OP_P with value VAL (assumed to be a constant or another SSA_NAME). 191 192 Use this version when not const/copy propagating values. For example, 193 PRE uses this version when building expressions as they would appear 194 in specific blocks taking into account actions of PHI nodes. 195 196 The statement in which an expression has been replaced should be 197 folded using fold_stmt_inplace. */ 198 199 void 200 replace_exp (use_operand_p op_p, tree val) 201 { 202 replace_exp_1 (op_p, val, false); 203 } 204 205 206 /* Propagate the value VAL (assumed to be a constant or another SSA_NAME) 207 into the tree pointed to by OP_P. 208 209 Use this version for const/copy propagation when SSA operands are not 210 available. It will perform the additional checks to ensure validity of 211 the const/copy propagation, but will not update any operand information. 212 Be sure to mark the stmt as modified. */ 213 214 void 215 propagate_tree_value (tree *op_p, tree val) 216 { 217 gcc_checking_assert (!(TREE_CODE (val) == SSA_NAME 218 && *op_p 219 && TREE_CODE (*op_p) == SSA_NAME 220 && !may_propagate_copy (*op_p, val))); 221 222 if (TREE_CODE (val) == SSA_NAME) 223 *op_p = val; 224 else 225 *op_p = unsave_expr_now (val); 226 } 227 228 229 /* Like propagate_tree_value, but use as the operand to replace 230 the principal expression (typically, the RHS) contained in the 231 statement referenced by iterator GSI. Note that it is not 232 always possible to update the statement in-place, so a new 233 statement may be created to replace the original. */ 234 235 void 236 propagate_tree_value_into_stmt (gimple_stmt_iterator *gsi, tree val) 237 { 238 gimple stmt = gsi_stmt (*gsi); 239 240 if (is_gimple_assign (stmt)) 241 { 242 tree expr = NULL_TREE; 243 if (gimple_assign_single_p (stmt)) 244 expr = gimple_assign_rhs1 (stmt); 245 propagate_tree_value (&expr, val); 246 gimple_assign_set_rhs_from_tree (gsi, expr); 247 } 248 else if (gimple_code (stmt) == GIMPLE_COND) 249 { 250 tree lhs = NULL_TREE; 251 tree rhs = build_zero_cst (TREE_TYPE (val)); 252 propagate_tree_value (&lhs, val); 253 gimple_cond_set_code (stmt, NE_EXPR); 254 gimple_cond_set_lhs (stmt, lhs); 255 gimple_cond_set_rhs (stmt, rhs); 256 } 257 else if (is_gimple_call (stmt) 258 && gimple_call_lhs (stmt) != NULL_TREE) 259 { 260 gimple new_stmt; 261 262 tree expr = NULL_TREE; 263 propagate_tree_value (&expr, val); 264 new_stmt = gimple_build_assign (gimple_call_lhs (stmt), expr); 265 move_ssa_defining_stmt_for_defs (new_stmt, stmt); 266 gsi_replace (gsi, new_stmt, false); 267 } 268 else if (gimple_code (stmt) == GIMPLE_SWITCH) 269 propagate_tree_value (gimple_switch_index_ptr (stmt), val); 270 else 271 gcc_unreachable (); 272 } 273 274 /*--------------------------------------------------------------------------- 275 Copy propagation 276 ---------------------------------------------------------------------------*/ 277 /* Lattice for copy-propagation. The lattice is initialized to 278 UNDEFINED (value == NULL) for SSA names that can become a copy 279 of something or VARYING (value == self) if not (see get_copy_of_val 280 and stmt_may_generate_copy). Other values make the name a COPY 281 of that value. 282 283 When visiting a statement or PHI node the lattice value for an 284 SSA name can transition from UNDEFINED to COPY to VARYING. */ 285 286 struct prop_value_d { 287 /* Copy-of value. */ 288 tree value; 289 }; 290 typedef struct prop_value_d prop_value_t; 291 292 static prop_value_t *copy_of; 293 294 295 /* Return true if this statement may generate a useful copy. */ 296 297 static bool 298 stmt_may_generate_copy (gimple stmt) 299 { 300 if (gimple_code (stmt) == GIMPLE_PHI) 301 return !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (stmt)); 302 303 if (gimple_code (stmt) != GIMPLE_ASSIGN) 304 return false; 305 306 /* If the statement has volatile operands, it won't generate a 307 useful copy. */ 308 if (gimple_has_volatile_ops (stmt)) 309 return false; 310 311 /* Statements with loads and/or stores will never generate a useful copy. */ 312 if (gimple_vuse (stmt)) 313 return false; 314 315 /* Otherwise, the only statements that generate useful copies are 316 assignments whose RHS is just an SSA name that doesn't flow 317 through abnormal edges. */ 318 return ((gimple_assign_rhs_code (stmt) == SSA_NAME 319 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt))) 320 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt))); 321 } 322 323 324 /* Return the copy-of value for VAR. */ 325 326 static inline prop_value_t * 327 get_copy_of_val (tree var) 328 { 329 prop_value_t *val = ©_of[SSA_NAME_VERSION (var)]; 330 331 if (val->value == NULL_TREE 332 && !stmt_may_generate_copy (SSA_NAME_DEF_STMT (var))) 333 { 334 /* If the variable will never generate a useful copy relation, 335 make it its own copy. */ 336 val->value = var; 337 } 338 339 return val; 340 } 341 342 /* Return the variable VAR is a copy of or VAR if VAR isn't the result 343 of a copy. */ 344 345 static inline tree 346 valueize_val (tree var) 347 { 348 if (TREE_CODE (var) == SSA_NAME) 349 { 350 tree val = get_copy_of_val (var)->value; 351 if (val) 352 return val; 353 } 354 return var; 355 } 356 357 /* Set VAL to be the copy of VAR. If that changed return true. */ 358 359 static inline bool 360 set_copy_of_val (tree var, tree val) 361 { 362 unsigned int ver = SSA_NAME_VERSION (var); 363 tree old; 364 365 /* Set FIRST to be the first link in COPY_OF[DEST]. If that 366 changed, return true. */ 367 old = copy_of[ver].value; 368 copy_of[ver].value = val; 369 370 if (old != val 371 || (val && !operand_equal_p (old, val, 0))) 372 return true; 373 374 return false; 375 } 376 377 378 /* Dump the copy-of value for variable VAR to FILE. */ 379 380 static void 381 dump_copy_of (FILE *file, tree var) 382 { 383 tree val; 384 385 print_generic_expr (file, var, dump_flags); 386 if (TREE_CODE (var) != SSA_NAME) 387 return; 388 389 val = copy_of[SSA_NAME_VERSION (var)].value; 390 fprintf (file, " copy-of chain: "); 391 print_generic_expr (file, var, 0); 392 fprintf (file, " "); 393 if (!val) 394 fprintf (file, "[UNDEFINED]"); 395 else if (val == var) 396 fprintf (file, "[NOT A COPY]"); 397 else 398 { 399 fprintf (file, "-> "); 400 print_generic_expr (file, val, 0); 401 fprintf (file, " "); 402 fprintf (file, "[COPY]"); 403 } 404 } 405 406 407 /* Evaluate the RHS of STMT. If it produces a valid copy, set the LHS 408 value and store the LHS into *RESULT_P. */ 409 410 static enum ssa_prop_result 411 copy_prop_visit_assignment (gimple stmt, tree *result_p) 412 { 413 tree lhs, rhs; 414 415 lhs = gimple_assign_lhs (stmt); 416 rhs = valueize_val (gimple_assign_rhs1 (stmt)); 417 418 if (TREE_CODE (lhs) == SSA_NAME) 419 { 420 /* Straight copy between two SSA names. First, make sure that 421 we can propagate the RHS into uses of LHS. */ 422 if (!may_propagate_copy (lhs, rhs)) 423 return SSA_PROP_VARYING; 424 425 *result_p = lhs; 426 if (set_copy_of_val (*result_p, rhs)) 427 return SSA_PROP_INTERESTING; 428 else 429 return SSA_PROP_NOT_INTERESTING; 430 } 431 432 return SSA_PROP_VARYING; 433 } 434 435 436 /* Visit the GIMPLE_COND STMT. Return SSA_PROP_INTERESTING 437 if it can determine which edge will be taken. Otherwise, return 438 SSA_PROP_VARYING. */ 439 440 static enum ssa_prop_result 441 copy_prop_visit_cond_stmt (gimple stmt, edge *taken_edge_p) 442 { 443 enum ssa_prop_result retval = SSA_PROP_VARYING; 444 location_t loc = gimple_location (stmt); 445 446 tree op0 = gimple_cond_lhs (stmt); 447 tree op1 = gimple_cond_rhs (stmt); 448 449 /* The only conditionals that we may be able to compute statically 450 are predicates involving two SSA_NAMEs. */ 451 if (TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME) 452 { 453 op0 = valueize_val (op0); 454 op1 = valueize_val (op1); 455 456 /* See if we can determine the predicate's value. */ 457 if (dump_file && (dump_flags & TDF_DETAILS)) 458 { 459 fprintf (dump_file, "Trying to determine truth value of "); 460 fprintf (dump_file, "predicate "); 461 print_gimple_stmt (dump_file, stmt, 0, 0); 462 } 463 464 /* We can fold COND and get a useful result only when we have 465 the same SSA_NAME on both sides of a comparison operator. */ 466 if (op0 == op1) 467 { 468 tree folded_cond = fold_binary_loc (loc, gimple_cond_code (stmt), 469 boolean_type_node, op0, op1); 470 if (folded_cond) 471 { 472 basic_block bb = gimple_bb (stmt); 473 *taken_edge_p = find_taken_edge (bb, folded_cond); 474 if (*taken_edge_p) 475 retval = SSA_PROP_INTERESTING; 476 } 477 } 478 } 479 480 if (dump_file && (dump_flags & TDF_DETAILS) && *taken_edge_p) 481 fprintf (dump_file, "\nConditional will always take edge %d->%d\n", 482 (*taken_edge_p)->src->index, (*taken_edge_p)->dest->index); 483 484 return retval; 485 } 486 487 488 /* Evaluate statement STMT. If the statement produces a new output 489 value, return SSA_PROP_INTERESTING and store the SSA_NAME holding 490 the new value in *RESULT_P. 491 492 If STMT is a conditional branch and we can determine its truth 493 value, set *TAKEN_EDGE_P accordingly. 494 495 If the new value produced by STMT is varying, return 496 SSA_PROP_VARYING. */ 497 498 static enum ssa_prop_result 499 copy_prop_visit_stmt (gimple stmt, edge *taken_edge_p, tree *result_p) 500 { 501 enum ssa_prop_result retval; 502 503 if (dump_file && (dump_flags & TDF_DETAILS)) 504 { 505 fprintf (dump_file, "\nVisiting statement:\n"); 506 print_gimple_stmt (dump_file, stmt, 0, dump_flags); 507 fprintf (dump_file, "\n"); 508 } 509 510 if (gimple_assign_single_p (stmt) 511 && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME 512 && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME 513 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))) 514 { 515 /* If the statement is a copy assignment, evaluate its RHS to 516 see if the lattice value of its output has changed. */ 517 retval = copy_prop_visit_assignment (stmt, result_p); 518 } 519 else if (gimple_code (stmt) == GIMPLE_COND) 520 { 521 /* See if we can determine which edge goes out of a conditional 522 jump. */ 523 retval = copy_prop_visit_cond_stmt (stmt, taken_edge_p); 524 } 525 else 526 retval = SSA_PROP_VARYING; 527 528 if (retval == SSA_PROP_VARYING) 529 { 530 tree def; 531 ssa_op_iter i; 532 533 /* Any other kind of statement is not interesting for constant 534 propagation and, therefore, not worth simulating. */ 535 if (dump_file && (dump_flags & TDF_DETAILS)) 536 fprintf (dump_file, "No interesting values produced.\n"); 537 538 /* The assignment is not a copy operation. Don't visit this 539 statement again and mark all the definitions in the statement 540 to be copies of nothing. */ 541 FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_ALL_DEFS) 542 set_copy_of_val (def, def); 543 } 544 545 return retval; 546 } 547 548 549 /* Visit PHI node PHI. If all the arguments produce the same value, 550 set it to be the value of the LHS of PHI. */ 551 552 static enum ssa_prop_result 553 copy_prop_visit_phi_node (gimple phi) 554 { 555 enum ssa_prop_result retval; 556 unsigned i; 557 prop_value_t phi_val = { NULL_TREE }; 558 559 tree lhs = gimple_phi_result (phi); 560 561 if (dump_file && (dump_flags & TDF_DETAILS)) 562 { 563 fprintf (dump_file, "\nVisiting PHI node: "); 564 print_gimple_stmt (dump_file, phi, 0, dump_flags); 565 } 566 567 for (i = 0; i < gimple_phi_num_args (phi); i++) 568 { 569 prop_value_t *arg_val; 570 tree arg_value; 571 tree arg = gimple_phi_arg_def (phi, i); 572 edge e = gimple_phi_arg_edge (phi, i); 573 574 /* We don't care about values flowing through non-executable 575 edges. */ 576 if (!(e->flags & EDGE_EXECUTABLE)) 577 continue; 578 579 /* Names that flow through abnormal edges cannot be used to 580 derive copies. */ 581 if (TREE_CODE (arg) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (arg)) 582 { 583 phi_val.value = lhs; 584 break; 585 } 586 587 if (dump_file && (dump_flags & TDF_DETAILS)) 588 { 589 fprintf (dump_file, "\tArgument #%d: ", i); 590 dump_copy_of (dump_file, arg); 591 fprintf (dump_file, "\n"); 592 } 593 594 if (TREE_CODE (arg) == SSA_NAME) 595 { 596 arg_val = get_copy_of_val (arg); 597 598 /* If we didn't visit the definition of arg yet treat it as 599 UNDEFINED. This also handles PHI arguments that are the 600 same as lhs. We'll come here again. */ 601 if (!arg_val->value) 602 continue; 603 604 arg_value = arg_val->value; 605 } 606 else 607 arg_value = valueize_val (arg); 608 609 /* Avoid copy propagation from an inner into an outer loop. 610 Otherwise, this may move loop variant variables outside of 611 their loops and prevent coalescing opportunities. If the 612 value was loop invariant, it will be hoisted by LICM and 613 exposed for copy propagation. 614 ??? The value will be always loop invariant. 615 In loop-closed SSA form do not copy-propagate through 616 PHI nodes in blocks with a loop exit edge predecessor. */ 617 if (current_loops 618 && TREE_CODE (arg_value) == SSA_NAME 619 && (loop_depth_of_name (arg_value) > loop_depth_of_name (lhs) 620 || (loops_state_satisfies_p (LOOP_CLOSED_SSA) 621 && loop_exit_edge_p (e->src->loop_father, e)))) 622 { 623 phi_val.value = lhs; 624 break; 625 } 626 627 /* If the LHS didn't have a value yet, make it a copy of the 628 first argument we find. */ 629 if (phi_val.value == NULL_TREE) 630 { 631 phi_val.value = arg_value; 632 continue; 633 } 634 635 /* If PHI_VAL and ARG don't have a common copy-of chain, then 636 this PHI node cannot be a copy operation. */ 637 if (phi_val.value != arg_value 638 && !operand_equal_p (phi_val.value, arg_value, 0)) 639 { 640 phi_val.value = lhs; 641 break; 642 } 643 } 644 645 if (phi_val.value 646 && may_propagate_copy (lhs, phi_val.value) 647 && set_copy_of_val (lhs, phi_val.value)) 648 retval = (phi_val.value != lhs) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING; 649 else 650 retval = SSA_PROP_NOT_INTERESTING; 651 652 if (dump_file && (dump_flags & TDF_DETAILS)) 653 { 654 fprintf (dump_file, "PHI node "); 655 dump_copy_of (dump_file, lhs); 656 fprintf (dump_file, "\nTelling the propagator to "); 657 if (retval == SSA_PROP_INTERESTING) 658 fprintf (dump_file, "add SSA edges out of this PHI and continue."); 659 else if (retval == SSA_PROP_VARYING) 660 fprintf (dump_file, "add SSA edges out of this PHI and never visit again."); 661 else 662 fprintf (dump_file, "do nothing with SSA edges and keep iterating."); 663 fprintf (dump_file, "\n\n"); 664 } 665 666 return retval; 667 } 668 669 670 /* Initialize structures used for copy propagation. */ 671 672 static void 673 init_copy_prop (void) 674 { 675 basic_block bb; 676 677 copy_of = XCNEWVEC (prop_value_t, num_ssa_names); 678 679 FOR_EACH_BB (bb) 680 { 681 gimple_stmt_iterator si; 682 int depth = bb->loop_depth; 683 684 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si)) 685 { 686 gimple stmt = gsi_stmt (si); 687 ssa_op_iter iter; 688 tree def; 689 690 /* The only statements that we care about are those that may 691 generate useful copies. We also need to mark conditional 692 jumps so that their outgoing edges are added to the work 693 lists of the propagator. 694 695 Avoid copy propagation from an inner into an outer loop. 696 Otherwise, this may move loop variant variables outside of 697 their loops and prevent coalescing opportunities. If the 698 value was loop invariant, it will be hoisted by LICM and 699 exposed for copy propagation. 700 ??? This doesn't make sense. */ 701 if (stmt_ends_bb_p (stmt)) 702 prop_set_simulate_again (stmt, true); 703 else if (stmt_may_generate_copy (stmt) 704 /* Since we are iterating over the statements in 705 BB, not the phi nodes, STMT will always be an 706 assignment. */ 707 && loop_depth_of_name (gimple_assign_rhs1 (stmt)) <= depth) 708 prop_set_simulate_again (stmt, true); 709 else 710 prop_set_simulate_again (stmt, false); 711 712 /* Mark all the outputs of this statement as not being 713 the copy of anything. */ 714 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS) 715 if (!prop_simulate_again_p (stmt)) 716 set_copy_of_val (def, def); 717 } 718 719 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si)) 720 { 721 gimple phi = gsi_stmt (si); 722 tree def; 723 724 def = gimple_phi_result (phi); 725 if (!is_gimple_reg (def)) 726 prop_set_simulate_again (phi, false); 727 else 728 prop_set_simulate_again (phi, true); 729 730 if (!prop_simulate_again_p (phi)) 731 set_copy_of_val (def, def); 732 } 733 } 734 } 735 736 /* Callback for substitute_and_fold to get at the final copy-of values. */ 737 738 static tree 739 get_value (tree name) 740 { 741 tree val = copy_of[SSA_NAME_VERSION (name)].value; 742 if (val && val != name) 743 return val; 744 return NULL_TREE; 745 } 746 747 /* Deallocate memory used in copy propagation and do final 748 substitution. */ 749 750 static void 751 fini_copy_prop (void) 752 { 753 unsigned i; 754 755 /* Set the final copy-of value for each variable by traversing the 756 copy-of chains. */ 757 for (i = 1; i < num_ssa_names; i++) 758 { 759 tree var = ssa_name (i); 760 if (!var 761 || !copy_of[i].value 762 || copy_of[i].value == var) 763 continue; 764 765 /* In theory the points-to solution of all members of the 766 copy chain is their intersection. For now we do not bother 767 to compute this but only make sure we do not lose points-to 768 information completely by setting the points-to solution 769 of the representative to the first solution we find if 770 it doesn't have one already. */ 771 if (copy_of[i].value != var 772 && TREE_CODE (copy_of[i].value) == SSA_NAME 773 && POINTER_TYPE_P (TREE_TYPE (var)) 774 && SSA_NAME_PTR_INFO (var) 775 && !SSA_NAME_PTR_INFO (copy_of[i].value)) 776 duplicate_ssa_name_ptr_info (copy_of[i].value, SSA_NAME_PTR_INFO (var)); 777 } 778 779 /* Don't do DCE if we have loops. That's the simplest way to not 780 destroy the scev cache. */ 781 substitute_and_fold (get_value, NULL, !current_loops); 782 783 free (copy_of); 784 } 785 786 787 /* Main entry point to the copy propagator. 788 789 PHIS_ONLY is true if we should only consider PHI nodes as generating 790 copy propagation opportunities. 791 792 The algorithm propagates the value COPY-OF using ssa_propagate. For 793 every variable X_i, COPY-OF(X_i) indicates which variable is X_i created 794 from. The following example shows how the algorithm proceeds at a 795 high level: 796 797 1 a_24 = x_1 798 2 a_2 = PHI <a_24, x_1> 799 3 a_5 = PHI <a_2> 800 4 x_1 = PHI <x_298, a_5, a_2> 801 802 The end result should be that a_2, a_5, a_24 and x_1 are a copy of 803 x_298. Propagation proceeds as follows. 804 805 Visit #1: a_24 is copy-of x_1. Value changed. 806 Visit #2: a_2 is copy-of x_1. Value changed. 807 Visit #3: a_5 is copy-of x_1. Value changed. 808 Visit #4: x_1 is copy-of x_298. Value changed. 809 Visit #1: a_24 is copy-of x_298. Value changed. 810 Visit #2: a_2 is copy-of x_298. Value changed. 811 Visit #3: a_5 is copy-of x_298. Value changed. 812 Visit #4: x_1 is copy-of x_298. Stable state reached. 813 814 When visiting PHI nodes, we only consider arguments that flow 815 through edges marked executable by the propagation engine. So, 816 when visiting statement #2 for the first time, we will only look at 817 the first argument (a_24) and optimistically assume that its value 818 is the copy of a_24 (x_1). */ 819 820 static unsigned int 821 execute_copy_prop (void) 822 { 823 init_copy_prop (); 824 ssa_propagate (copy_prop_visit_stmt, copy_prop_visit_phi_node); 825 fini_copy_prop (); 826 return 0; 827 } 828 829 static bool 830 gate_copy_prop (void) 831 { 832 return flag_tree_copy_prop != 0; 833 } 834 835 struct gimple_opt_pass pass_copy_prop = 836 { 837 { 838 GIMPLE_PASS, 839 "copyprop", /* name */ 840 gate_copy_prop, /* gate */ 841 execute_copy_prop, /* execute */ 842 NULL, /* sub */ 843 NULL, /* next */ 844 0, /* static_pass_number */ 845 TV_TREE_COPY_PROP, /* tv_id */ 846 PROP_ssa | PROP_cfg, /* properties_required */ 847 0, /* properties_provided */ 848 0, /* properties_destroyed */ 849 0, /* todo_flags_start */ 850 TODO_cleanup_cfg 851 | TODO_ggc_collect 852 | TODO_verify_ssa 853 | TODO_update_ssa /* todo_flags_finish */ 854 } 855 }; 856