1/* Copy propagation and SSA_NAME replacement support routines. 2 Copyright (C) 2004-2015 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify 7it under the terms of the GNU General Public License as published by 8the Free Software Foundation; either version 3, or (at your option) 9any later version. 10 11GCC is distributed in the hope that it will be useful, 12but WITHOUT ANY WARRANTY; without even the implied warranty of 13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14GNU General Public License for more details. 15 16You should have received a copy of the GNU General Public License 17along with GCC; see the file COPYING3. If not see 18<http://www.gnu.org/licenses/>. */ 19 20#include "config.h" 21#include "system.h" 22#include "coretypes.h" 23#include "tm.h" 24#include "hash-set.h" 25#include "machmode.h" 26#include "vec.h" 27#include "double-int.h" 28#include "input.h" 29#include "alias.h" 30#include "symtab.h" 31#include "wide-int.h" 32#include "inchash.h" 33#include "tree.h" 34#include "fold-const.h" 35#include "flags.h" 36#include "tm_p.h" 37#include "predict.h" 38#include "hard-reg-set.h" 39#include "input.h" 40#include "function.h" 41#include "dominance.h" 42#include "cfg.h" 43#include "basic-block.h" 44#include "gimple-pretty-print.h" 45#include "tree-ssa-alias.h" 46#include "internal-fn.h" 47#include "gimple-expr.h" 48#include "is-a.h" 49#include "gimple.h" 50#include "gimple-iterator.h" 51#include "gimple-ssa.h" 52#include "tree-cfg.h" 53#include "tree-phinodes.h" 54#include "ssa-iterators.h" 55#include "stringpool.h" 56#include "tree-ssanames.h" 57#include "tree-pass.h" 58#include "tree-ssa-propagate.h" 59#include "langhooks.h" 60#include "cfgloop.h" 61#include "tree-scalar-evolution.h" 62#include "tree-ssa-dom.h" 63#include "tree-ssa-loop-niter.h" 64 65 66/* This file implements the copy propagation pass and provides a 67 handful of interfaces for performing const/copy propagation and 68 simple expression replacement which keep variable annotations 69 up-to-date. 70 71 We require that for any copy operation where the RHS and LHS have 72 a non-null memory tag the memory tag be the same. It is OK 73 for one or both of the memory tags to be NULL. 74 75 We also require tracking if a variable is dereferenced in a load or 76 store operation. 77 78 We enforce these requirements by having all copy propagation and 79 replacements of one SSA_NAME with a different SSA_NAME to use the 80 APIs defined in this file. */ 81 82/*--------------------------------------------------------------------------- 83 Copy propagation 84---------------------------------------------------------------------------*/ 85/* Lattice for copy-propagation. The lattice is initialized to 86 UNDEFINED (value == NULL) for SSA names that can become a copy 87 of something or VARYING (value == self) if not (see get_copy_of_val 88 and stmt_may_generate_copy). Other values make the name a COPY 89 of that value. 90 91 When visiting a statement or PHI node the lattice value for an 92 SSA name can transition from UNDEFINED to COPY to VARYING. */ 93 94struct prop_value_t { 95 /* Copy-of value. */ 96 tree value; 97}; 98 99static prop_value_t *copy_of; 100static unsigned n_copy_of; 101 102 103/* Return true if this statement may generate a useful copy. */ 104 105static bool 106stmt_may_generate_copy (gimple stmt) 107{ 108 if (gimple_code (stmt) == GIMPLE_PHI) 109 return !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (stmt)); 110 111 if (gimple_code (stmt) != GIMPLE_ASSIGN) 112 return false; 113 114 /* If the statement has volatile operands, it won't generate a 115 useful copy. */ 116 if (gimple_has_volatile_ops (stmt)) 117 return false; 118 119 /* Statements with loads and/or stores will never generate a useful copy. */ 120 if (gimple_vuse (stmt)) 121 return false; 122 123 /* Otherwise, the only statements that generate useful copies are 124 assignments whose RHS is just an SSA name that doesn't flow 125 through abnormal edges. */ 126 return ((gimple_assign_rhs_code (stmt) == SSA_NAME 127 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt))) 128 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt))); 129} 130 131 132/* Return the copy-of value for VAR. */ 133 134static inline prop_value_t * 135get_copy_of_val (tree var) 136{ 137 prop_value_t *val = ©_of[SSA_NAME_VERSION (var)]; 138 139 if (val->value == NULL_TREE 140 && !stmt_may_generate_copy (SSA_NAME_DEF_STMT (var))) 141 { 142 /* If the variable will never generate a useful copy relation, 143 make it its own copy. */ 144 val->value = var; 145 } 146 147 return val; 148} 149 150/* Return the variable VAR is a copy of or VAR if VAR isn't the result 151 of a copy. */ 152 153static inline tree 154valueize_val (tree var) 155{ 156 if (TREE_CODE (var) == SSA_NAME) 157 { 158 tree val = get_copy_of_val (var)->value; 159 if (val) 160 return val; 161 } 162 return var; 163} 164 165/* Set VAL to be the copy of VAR. If that changed return true. */ 166 167static inline bool 168set_copy_of_val (tree var, tree val) 169{ 170 unsigned int ver = SSA_NAME_VERSION (var); 171 tree old; 172 173 /* Set FIRST to be the first link in COPY_OF[DEST]. If that 174 changed, return true. */ 175 old = copy_of[ver].value; 176 copy_of[ver].value = val; 177 178 if (old != val 179 || (val && !operand_equal_p (old, val, 0))) 180 return true; 181 182 return false; 183} 184 185 186/* Dump the copy-of value for variable VAR to FILE. */ 187 188static void 189dump_copy_of (FILE *file, tree var) 190{ 191 tree val; 192 193 print_generic_expr (file, var, dump_flags); 194 if (TREE_CODE (var) != SSA_NAME) 195 return; 196 197 val = copy_of[SSA_NAME_VERSION (var)].value; 198 fprintf (file, " copy-of chain: "); 199 print_generic_expr (file, var, 0); 200 fprintf (file, " "); 201 if (!val) 202 fprintf (file, "[UNDEFINED]"); 203 else if (val == var) 204 fprintf (file, "[NOT A COPY]"); 205 else 206 { 207 fprintf (file, "-> "); 208 print_generic_expr (file, val, 0); 209 fprintf (file, " "); 210 fprintf (file, "[COPY]"); 211 } 212} 213 214 215/* Evaluate the RHS of STMT. If it produces a valid copy, set the LHS 216 value and store the LHS into *RESULT_P. */ 217 218static enum ssa_prop_result 219copy_prop_visit_assignment (gimple stmt, tree *result_p) 220{ 221 tree lhs, rhs; 222 223 lhs = gimple_assign_lhs (stmt); 224 rhs = valueize_val (gimple_assign_rhs1 (stmt)); 225 226 if (TREE_CODE (lhs) == SSA_NAME) 227 { 228 /* Straight copy between two SSA names. First, make sure that 229 we can propagate the RHS into uses of LHS. */ 230 if (!may_propagate_copy (lhs, rhs)) 231 return SSA_PROP_VARYING; 232 233 *result_p = lhs; 234 if (set_copy_of_val (*result_p, rhs)) 235 return SSA_PROP_INTERESTING; 236 else 237 return SSA_PROP_NOT_INTERESTING; 238 } 239 240 return SSA_PROP_VARYING; 241} 242 243 244/* Visit the GIMPLE_COND STMT. Return SSA_PROP_INTERESTING 245 if it can determine which edge will be taken. Otherwise, return 246 SSA_PROP_VARYING. */ 247 248static enum ssa_prop_result 249copy_prop_visit_cond_stmt (gimple stmt, edge *taken_edge_p) 250{ 251 enum ssa_prop_result retval = SSA_PROP_VARYING; 252 location_t loc = gimple_location (stmt); 253 254 tree op0 = valueize_val (gimple_cond_lhs (stmt)); 255 tree op1 = valueize_val (gimple_cond_rhs (stmt)); 256 257 /* See if we can determine the predicate's value. */ 258 if (dump_file && (dump_flags & TDF_DETAILS)) 259 { 260 fprintf (dump_file, "Trying to determine truth value of "); 261 fprintf (dump_file, "predicate "); 262 print_gimple_stmt (dump_file, stmt, 0, 0); 263 } 264 265 /* Fold COND and see whether we get a useful result. */ 266 tree folded_cond = fold_binary_loc (loc, gimple_cond_code (stmt), 267 boolean_type_node, op0, op1); 268 if (folded_cond) 269 { 270 basic_block bb = gimple_bb (stmt); 271 *taken_edge_p = find_taken_edge (bb, folded_cond); 272 if (*taken_edge_p) 273 retval = SSA_PROP_INTERESTING; 274 } 275 276 if (dump_file && (dump_flags & TDF_DETAILS) && *taken_edge_p) 277 fprintf (dump_file, "\nConditional will always take edge %d->%d\n", 278 (*taken_edge_p)->src->index, (*taken_edge_p)->dest->index); 279 280 return retval; 281} 282 283 284/* Evaluate statement STMT. If the statement produces a new output 285 value, return SSA_PROP_INTERESTING and store the SSA_NAME holding 286 the new value in *RESULT_P. 287 288 If STMT is a conditional branch and we can determine its truth 289 value, set *TAKEN_EDGE_P accordingly. 290 291 If the new value produced by STMT is varying, return 292 SSA_PROP_VARYING. */ 293 294static enum ssa_prop_result 295copy_prop_visit_stmt (gimple stmt, edge *taken_edge_p, tree *result_p) 296{ 297 enum ssa_prop_result retval; 298 299 if (dump_file && (dump_flags & TDF_DETAILS)) 300 { 301 fprintf (dump_file, "\nVisiting statement:\n"); 302 print_gimple_stmt (dump_file, stmt, 0, dump_flags); 303 fprintf (dump_file, "\n"); 304 } 305 306 if (gimple_assign_single_p (stmt) 307 && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME 308 && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME 309 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))) 310 { 311 /* If the statement is a copy assignment, evaluate its RHS to 312 see if the lattice value of its output has changed. */ 313 retval = copy_prop_visit_assignment (stmt, result_p); 314 } 315 else if (gimple_code (stmt) == GIMPLE_COND) 316 { 317 /* See if we can determine which edge goes out of a conditional 318 jump. */ 319 retval = copy_prop_visit_cond_stmt (stmt, taken_edge_p); 320 } 321 else 322 retval = SSA_PROP_VARYING; 323 324 if (retval == SSA_PROP_VARYING) 325 { 326 tree def; 327 ssa_op_iter i; 328 329 /* Any other kind of statement is not interesting for constant 330 propagation and, therefore, not worth simulating. */ 331 if (dump_file && (dump_flags & TDF_DETAILS)) 332 fprintf (dump_file, "No interesting values produced.\n"); 333 334 /* The assignment is not a copy operation. Don't visit this 335 statement again and mark all the definitions in the statement 336 to be copies of nothing. */ 337 FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_ALL_DEFS) 338 set_copy_of_val (def, def); 339 } 340 341 return retval; 342} 343 344 345/* Visit PHI node PHI. If all the arguments produce the same value, 346 set it to be the value of the LHS of PHI. */ 347 348static enum ssa_prop_result 349copy_prop_visit_phi_node (gphi *phi) 350{ 351 enum ssa_prop_result retval; 352 unsigned i; 353 prop_value_t phi_val = { NULL_TREE }; 354 355 tree lhs = gimple_phi_result (phi); 356 357 if (dump_file && (dump_flags & TDF_DETAILS)) 358 { 359 fprintf (dump_file, "\nVisiting PHI node: "); 360 print_gimple_stmt (dump_file, phi, 0, dump_flags); 361 } 362 363 for (i = 0; i < gimple_phi_num_args (phi); i++) 364 { 365 prop_value_t *arg_val; 366 tree arg_value; 367 tree arg = gimple_phi_arg_def (phi, i); 368 edge e = gimple_phi_arg_edge (phi, i); 369 370 /* We don't care about values flowing through non-executable 371 edges. */ 372 if (!(e->flags & EDGE_EXECUTABLE)) 373 continue; 374 375 /* Names that flow through abnormal edges cannot be used to 376 derive copies. */ 377 if (TREE_CODE (arg) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (arg)) 378 { 379 phi_val.value = lhs; 380 break; 381 } 382 383 if (dump_file && (dump_flags & TDF_DETAILS)) 384 { 385 fprintf (dump_file, "\tArgument #%d: ", i); 386 dump_copy_of (dump_file, arg); 387 fprintf (dump_file, "\n"); 388 } 389 390 if (TREE_CODE (arg) == SSA_NAME) 391 { 392 arg_val = get_copy_of_val (arg); 393 394 /* If we didn't visit the definition of arg yet treat it as 395 UNDEFINED. This also handles PHI arguments that are the 396 same as lhs. We'll come here again. */ 397 if (!arg_val->value) 398 continue; 399 400 arg_value = arg_val->value; 401 } 402 else 403 arg_value = valueize_val (arg); 404 405 /* In loop-closed SSA form do not copy-propagate SSA-names across 406 loop exit edges. */ 407 if (loops_state_satisfies_p (LOOP_CLOSED_SSA) 408 && TREE_CODE (arg_value) == SSA_NAME 409 && loop_exit_edge_p (e->src->loop_father, e)) 410 { 411 phi_val.value = lhs; 412 break; 413 } 414 415 /* If the LHS didn't have a value yet, make it a copy of the 416 first argument we find. */ 417 if (phi_val.value == NULL_TREE) 418 { 419 phi_val.value = arg_value; 420 continue; 421 } 422 423 /* If PHI_VAL and ARG don't have a common copy-of chain, then 424 this PHI node cannot be a copy operation. */ 425 if (phi_val.value != arg_value 426 && !operand_equal_p (phi_val.value, arg_value, 0)) 427 { 428 phi_val.value = lhs; 429 break; 430 } 431 } 432 433 if (phi_val.value 434 && may_propagate_copy (lhs, phi_val.value) 435 && set_copy_of_val (lhs, phi_val.value)) 436 retval = (phi_val.value != lhs) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING; 437 else 438 retval = SSA_PROP_NOT_INTERESTING; 439 440 if (dump_file && (dump_flags & TDF_DETAILS)) 441 { 442 fprintf (dump_file, "PHI node "); 443 dump_copy_of (dump_file, lhs); 444 fprintf (dump_file, "\nTelling the propagator to "); 445 if (retval == SSA_PROP_INTERESTING) 446 fprintf (dump_file, "add SSA edges out of this PHI and continue."); 447 else if (retval == SSA_PROP_VARYING) 448 fprintf (dump_file, "add SSA edges out of this PHI and never visit again."); 449 else 450 fprintf (dump_file, "do nothing with SSA edges and keep iterating."); 451 fprintf (dump_file, "\n\n"); 452 } 453 454 return retval; 455} 456 457 458/* Initialize structures used for copy propagation. */ 459 460static void 461init_copy_prop (void) 462{ 463 basic_block bb; 464 465 n_copy_of = num_ssa_names; 466 copy_of = XCNEWVEC (prop_value_t, n_copy_of); 467 468 FOR_EACH_BB_FN (bb, cfun) 469 { 470 for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si); 471 gsi_next (&si)) 472 { 473 gimple stmt = gsi_stmt (si); 474 ssa_op_iter iter; 475 tree def; 476 477 /* The only statements that we care about are those that may 478 generate useful copies. We also need to mark conditional 479 jumps so that their outgoing edges are added to the work 480 lists of the propagator. */ 481 if (stmt_ends_bb_p (stmt)) 482 prop_set_simulate_again (stmt, true); 483 else if (stmt_may_generate_copy (stmt)) 484 prop_set_simulate_again (stmt, true); 485 else 486 prop_set_simulate_again (stmt, false); 487 488 /* Mark all the outputs of this statement as not being 489 the copy of anything. */ 490 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS) 491 if (!prop_simulate_again_p (stmt)) 492 set_copy_of_val (def, def); 493 } 494 495 for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si); 496 gsi_next (&si)) 497 { 498 gphi *phi = si.phi (); 499 tree def; 500 501 def = gimple_phi_result (phi); 502 if (virtual_operand_p (def)) 503 prop_set_simulate_again (phi, false); 504 else 505 prop_set_simulate_again (phi, true); 506 507 if (!prop_simulate_again_p (phi)) 508 set_copy_of_val (def, def); 509 } 510 } 511} 512 513/* Callback for substitute_and_fold to get at the final copy-of values. */ 514 515static tree 516get_value (tree name) 517{ 518 tree val; 519 if (SSA_NAME_VERSION (name) >= n_copy_of) 520 return NULL_TREE; 521 val = copy_of[SSA_NAME_VERSION (name)].value; 522 if (val && val != name) 523 return val; 524 return NULL_TREE; 525} 526 527/* Deallocate memory used in copy propagation and do final 528 substitution. */ 529 530static bool 531fini_copy_prop (void) 532{ 533 unsigned i; 534 535 /* Set the final copy-of value for each variable by traversing the 536 copy-of chains. */ 537 for (i = 1; i < num_ssa_names; i++) 538 { 539 tree var = ssa_name (i); 540 if (!var 541 || !copy_of[i].value 542 || copy_of[i].value == var) 543 continue; 544 545 /* In theory the points-to solution of all members of the 546 copy chain is their intersection. For now we do not bother 547 to compute this but only make sure we do not lose points-to 548 information completely by setting the points-to solution 549 of the representative to the first solution we find if 550 it doesn't have one already. */ 551 if (copy_of[i].value != var 552 && TREE_CODE (copy_of[i].value) == SSA_NAME) 553 { 554 basic_block copy_of_bb 555 = gimple_bb (SSA_NAME_DEF_STMT (copy_of[i].value)); 556 basic_block var_bb = gimple_bb (SSA_NAME_DEF_STMT (var)); 557 if (POINTER_TYPE_P (TREE_TYPE (var)) 558 && SSA_NAME_PTR_INFO (var) 559 && !SSA_NAME_PTR_INFO (copy_of[i].value)) 560 { 561 duplicate_ssa_name_ptr_info (copy_of[i].value, 562 SSA_NAME_PTR_INFO (var)); 563 /* Points-to information is cfg insensitive, 564 but alignment info might be cfg sensitive, if it 565 e.g. is derived from VRP derived non-zero bits. 566 So, do not copy alignment info if the two SSA_NAMEs 567 aren't defined in the same basic block. */ 568 if (var_bb != copy_of_bb) 569 mark_ptr_info_alignment_unknown 570 (SSA_NAME_PTR_INFO (copy_of[i].value)); 571 } 572 else if (!POINTER_TYPE_P (TREE_TYPE (var)) 573 && SSA_NAME_RANGE_INFO (var) 574 && !SSA_NAME_RANGE_INFO (copy_of[i].value) 575 && var_bb == copy_of_bb) 576 duplicate_ssa_name_range_info (copy_of[i].value, 577 SSA_NAME_RANGE_TYPE (var), 578 SSA_NAME_RANGE_INFO (var)); 579 } 580 } 581 582 bool changed = substitute_and_fold (get_value, NULL, true); 583 if (changed) 584 { 585 free_numbers_of_iterations_estimates (); 586 if (scev_initialized_p ()) 587 scev_reset (); 588 } 589 590 free (copy_of); 591 592 return changed; 593} 594 595 596/* Main entry point to the copy propagator. 597 598 PHIS_ONLY is true if we should only consider PHI nodes as generating 599 copy propagation opportunities. 600 601 The algorithm propagates the value COPY-OF using ssa_propagate. For 602 every variable X_i, COPY-OF(X_i) indicates which variable is X_i created 603 from. The following example shows how the algorithm proceeds at a 604 high level: 605 606 1 a_24 = x_1 607 2 a_2 = PHI <a_24, x_1> 608 3 a_5 = PHI <a_2> 609 4 x_1 = PHI <x_298, a_5, a_2> 610 611 The end result should be that a_2, a_5, a_24 and x_1 are a copy of 612 x_298. Propagation proceeds as follows. 613 614 Visit #1: a_24 is copy-of x_1. Value changed. 615 Visit #2: a_2 is copy-of x_1. Value changed. 616 Visit #3: a_5 is copy-of x_1. Value changed. 617 Visit #4: x_1 is copy-of x_298. Value changed. 618 Visit #1: a_24 is copy-of x_298. Value changed. 619 Visit #2: a_2 is copy-of x_298. Value changed. 620 Visit #3: a_5 is copy-of x_298. Value changed. 621 Visit #4: x_1 is copy-of x_298. Stable state reached. 622 623 When visiting PHI nodes, we only consider arguments that flow 624 through edges marked executable by the propagation engine. So, 625 when visiting statement #2 for the first time, we will only look at 626 the first argument (a_24) and optimistically assume that its value 627 is the copy of a_24 (x_1). */ 628 629static unsigned int 630execute_copy_prop (void) 631{ 632 init_copy_prop (); 633 ssa_propagate (copy_prop_visit_stmt, copy_prop_visit_phi_node); 634 if (fini_copy_prop ()) 635 return TODO_cleanup_cfg; 636 return 0; 637} 638 639namespace { 640 641const pass_data pass_data_copy_prop = 642{ 643 GIMPLE_PASS, /* type */ 644 "copyprop", /* name */ 645 OPTGROUP_NONE, /* optinfo_flags */ 646 TV_TREE_COPY_PROP, /* tv_id */ 647 ( PROP_ssa | PROP_cfg ), /* properties_required */ 648 0, /* properties_provided */ 649 0, /* properties_destroyed */ 650 0, /* todo_flags_start */ 651 0, /* todo_flags_finish */ 652}; 653 654class pass_copy_prop : public gimple_opt_pass 655{ 656public: 657 pass_copy_prop (gcc::context *ctxt) 658 : gimple_opt_pass (pass_data_copy_prop, ctxt) 659 {} 660 661 /* opt_pass methods: */ 662 opt_pass * clone () { return new pass_copy_prop (m_ctxt); } 663 virtual bool gate (function *) { return flag_tree_copy_prop != 0; } 664 virtual unsigned int execute (function *) { return execute_copy_prop (); } 665 666}; // class pass_copy_prop 667 668} // anon namespace 669 670gimple_opt_pass * 671make_pass_copy_prop (gcc::context *ctxt) 672{ 673 return new pass_copy_prop (ctxt); 674} 675