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