1 /* Copy propagation and SSA_NAME replacement support routines. 2 Copyright (C) 2004-2018 Free Software Foundation, Inc. 3 4 This file is part of GCC. 5 6 GCC is free software; you can redistribute it and/or modify 7 it under the terms of the GNU General Public License as published by 8 the Free Software Foundation; either version 3, or (at your option) 9 any later version. 10 11 GCC is distributed in the hope that it will be useful, 12 but WITHOUT ANY WARRANTY; without even the implied warranty of 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 GNU General Public License for more details. 15 16 You should have received a copy of the GNU General Public License 17 along 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 66 struct prop_value_t { 67 /* Copy-of value. */ 68 tree value; 69 }; 70 71 class 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 78 static prop_value_t *copy_of; 79 static unsigned n_copy_of; 80 81 82 /* Return true if this statement may generate a useful copy. */ 83 84 static bool 85 stmt_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 113 static inline prop_value_t * 114 get_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 132 static inline tree 133 valueize_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 146 static inline bool 147 set_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 167 static void 168 dump_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 197 static enum ssa_prop_result 198 copy_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 227 static enum ssa_prop_result 228 copy_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 273 enum ssa_prop_result 274 copy_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 327 enum ssa_prop_result 328 copy_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 439 static void 440 init_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 492 class 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 500 tree 501 copy_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 515 static bool 516 fini_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 alignment info might be cfg sensitive, if it 549 e.g. is derived from VRP derived non-zero bits. 550 So, do not copy alignment info if the two SSA_NAMEs 551 aren't defined in the same basic block. */ 552 if (var_bb != copy_of_bb) 553 mark_ptr_info_alignment_unknown 554 (SSA_NAME_PTR_INFO (copy_of[i].value)); 555 } 556 else if (!POINTER_TYPE_P (TREE_TYPE (var)) 557 && SSA_NAME_RANGE_INFO (var) 558 && !SSA_NAME_RANGE_INFO (copy_of[i].value) 559 && var_bb == copy_of_bb) 560 duplicate_ssa_name_range_info (copy_of[i].value, 561 SSA_NAME_RANGE_TYPE (var), 562 SSA_NAME_RANGE_INFO (var)); 563 } 564 } 565 566 class copy_folder copy_folder; 567 bool changed = copy_folder.substitute_and_fold (); 568 if (changed) 569 { 570 free_numbers_of_iterations_estimates (cfun); 571 if (scev_initialized_p ()) 572 scev_reset (); 573 } 574 575 free (copy_of); 576 577 return changed; 578 } 579 580 581 /* Main entry point to the copy propagator. 582 583 PHIS_ONLY is true if we should only consider PHI nodes as generating 584 copy propagation opportunities. 585 586 The algorithm propagates the value COPY-OF using ssa_propagate. For 587 every variable X_i, COPY-OF(X_i) indicates which variable is X_i created 588 from. The following example shows how the algorithm proceeds at a 589 high level: 590 591 1 a_24 = x_1 592 2 a_2 = PHI <a_24, x_1> 593 3 a_5 = PHI <a_2> 594 4 x_1 = PHI <x_298, a_5, a_2> 595 596 The end result should be that a_2, a_5, a_24 and x_1 are a copy of 597 x_298. Propagation proceeds as follows. 598 599 Visit #1: a_24 is copy-of x_1. Value changed. 600 Visit #2: a_2 is copy-of x_1. Value changed. 601 Visit #3: a_5 is copy-of x_1. Value changed. 602 Visit #4: x_1 is copy-of x_298. Value changed. 603 Visit #1: a_24 is copy-of x_298. Value changed. 604 Visit #2: a_2 is copy-of x_298. Value changed. 605 Visit #3: a_5 is copy-of x_298. Value changed. 606 Visit #4: x_1 is copy-of x_298. Stable state reached. 607 608 When visiting PHI nodes, we only consider arguments that flow 609 through edges marked executable by the propagation engine. So, 610 when visiting statement #2 for the first time, we will only look at 611 the first argument (a_24) and optimistically assume that its value 612 is the copy of a_24 (x_1). */ 613 614 static unsigned int 615 execute_copy_prop (void) 616 { 617 init_copy_prop (); 618 class copy_prop copy_prop; 619 copy_prop.ssa_propagate (); 620 if (fini_copy_prop ()) 621 return TODO_cleanup_cfg; 622 return 0; 623 } 624 625 namespace { 626 627 const pass_data pass_data_copy_prop = 628 { 629 GIMPLE_PASS, /* type */ 630 "copyprop", /* name */ 631 OPTGROUP_NONE, /* optinfo_flags */ 632 TV_TREE_COPY_PROP, /* tv_id */ 633 ( PROP_ssa | PROP_cfg ), /* properties_required */ 634 0, /* properties_provided */ 635 0, /* properties_destroyed */ 636 0, /* todo_flags_start */ 637 0, /* todo_flags_finish */ 638 }; 639 640 class pass_copy_prop : public gimple_opt_pass 641 { 642 public: 643 pass_copy_prop (gcc::context *ctxt) 644 : gimple_opt_pass (pass_data_copy_prop, ctxt) 645 {} 646 647 /* opt_pass methods: */ 648 opt_pass * clone () { return new pass_copy_prop (m_ctxt); } 649 virtual bool gate (function *) { return flag_tree_copy_prop != 0; } 650 virtual unsigned int execute (function *) { return execute_copy_prop (); } 651 652 }; // class pass_copy_prop 653 654 } // anon namespace 655 656 gimple_opt_pass * 657 make_pass_copy_prop (gcc::context *ctxt) 658 { 659 return new pass_copy_prop (ctxt); 660 } 661