gcc/tree-ssa-copy.c

   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 "rtl.h"
  28 #include "tm_p.h"
  29 #include "ggc.h"
  30 #include "basic-block.h"
  31 #include "output.h"
  32 #include "expr.h"
  33 #include "function.h"
  34 #include "diagnostic.h"
  35 #include "timevar.h"
  36 #include "tree-dump.h"
  37 #include "tree-flow.h"
  38 #include "tree-pass.h"
  39 #include "tree-ssa-propagate.h"
  40 #include "langhooks.h"
  41 #include "cfgloop.h"
  42
  43 /* This file implements the copy propagation pass and provides a
  44    handful of interfaces for performing const/copy propagation and
  45    simple expression replacement which keep variable annotations
  46    up-to-date.
  47
  48    We require that for any copy operation where the RHS and LHS have
  49    a non-null memory tag the memory tag be the same.   It is OK
  50    for one or both of the memory tags to be NULL.
  51
  52    We also require tracking if a variable is dereferenced in a load or
  53    store operation.
  54
  55    We enforce these requirements by having all copy propagation and
  56    replacements of one SSA_NAME with a different SSA_NAME to use the
  57    APIs defined in this file.  */
  58
  59 /* Return true if we may propagate ORIG into DEST, false otherwise.  */
  60
  61 bool
  62 may_propagate_copy (tree dest, tree orig)
  63 {
  64   tree type_d = TREE_TYPE (dest);
  65   tree type_o = TREE_TYPE (orig);
  66
  67   /* If ORIG flows in from an abnormal edge, it cannot be propagated.  */
  68   if (TREE_CODE (orig) == SSA_NAME
  69       && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig))
  70     return false;
  71
  72   /* If DEST is an SSA_NAME that flows from an abnormal edge, then it
  73      cannot be replaced.  */
  74   if (TREE_CODE (dest) == SSA_NAME
  75       && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (dest))
  76     return false;
  77
  78   /* Do not copy between types for which we *do* need a conversion.  */
  79   if (!useless_type_conversion_p (type_d, type_o))
  80     return false;
  81
  82   /* Propagating virtual operands is always ok.  */
  83   if (TREE_CODE (dest) == SSA_NAME && !is_gimple_reg (dest))
  84     {
  85       /* But only between virtual operands.  */
  86       gcc_assert (TREE_CODE (orig) == SSA_NAME && !is_gimple_reg (orig));
  87
  88       return true;
  89     }
  90
  91   /* Anything else is OK.  */
  92   return true;
  93 }
  94
  95 /* Like may_propagate_copy, but use as the destination expression
  96    the principal expression (typically, the RHS) contained in
  97    statement DEST.  This is more efficient when working with the
  98    gimple tuples representation.  */
  99
 100 bool
 101 may_propagate_copy_into_stmt (gimple dest, tree orig)
 102 {
 103   tree type_d;
 104   tree type_o;
 105
 106   /* If the statement is a switch or a single-rhs assignment,
 107      then the expression to be replaced by the propagation may
 108      be an SSA_NAME.  Fortunately, there is an explicit tree
 109      for the expression, so we delegate to may_propagate_copy.  */
 110
 111   if (gimple_assign_single_p (dest))
 112     return may_propagate_copy (gimple_assign_rhs1 (dest), orig);
 113   else if (gimple_code (dest) == GIMPLE_SWITCH)
 114     return may_propagate_copy (gimple_switch_index (dest), orig);
 115
 116   /* In other cases, the expression is not materialized, so there
 117      is no destination to pass to may_propagate_copy.  On the other
 118      hand, the expression cannot be an SSA_NAME, so the analysis
 119      is much simpler.  */
 120
 121   if (TREE_CODE (orig) == SSA_NAME
 122       && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig))
 123     return false;
 124
 125   if (is_gimple_assign (dest))
 126     type_d = TREE_TYPE (gimple_assign_lhs (dest));
 127   else if (gimple_code (dest) == GIMPLE_COND)
 128     type_d = boolean_type_node;
 129   else if (is_gimple_call (dest)
 130            && gimple_call_lhs (dest) != NULL_TREE)
 131     type_d = TREE_TYPE (gimple_call_lhs (dest));
 132   else
 133     gcc_unreachable ();
 134
 135   type_o = TREE_TYPE (orig);
 136
 137   if (!useless_type_conversion_p (type_d, type_o))
 138     return false;
 139
 140   return true;
 141 }
 142
 143 /* Similarly, but we know that we're propagating into an ASM_EXPR.  */
 144
 145 bool
 146 may_propagate_copy_into_asm (tree dest)
 147 {
 148   /* Hard register operands of asms are special.  Do not bypass.  */
 149   return !(TREE_CODE (dest) == SSA_NAME
 150            && TREE_CODE (SSA_NAME_VAR (dest)) == VAR_DECL
 151            && DECL_HARD_REGISTER (SSA_NAME_VAR (dest)));
 152 }
 153
 154
 155 /* Common code for propagate_value and replace_exp.
 156
 157    Replace use operand OP_P with VAL.  FOR_PROPAGATION indicates if the
 158    replacement is done to propagate a value or not.  */
 159
 160 static void
 161 replace_exp_1 (use_operand_p op_p, tree val,
 162                bool for_propagation ATTRIBUTE_UNUSED)
 163 {
 164 #if defined ENABLE_CHECKING
 165   tree op = USE_FROM_PTR (op_p);
 166
 167   gcc_assert (!(for_propagation
 168                 && TREE_CODE (op) == SSA_NAME
 169                 && TREE_CODE (val) == SSA_NAME
 170                 && !may_propagate_copy (op, val)));
 171 #endif
 172
 173   if (TREE_CODE (val) == SSA_NAME)
 174     SET_USE (op_p, val);
 175   else
 176     SET_USE (op_p, unsave_expr_now (val));
 177 }
 178
 179
 180 /* Propagate the value VAL (assumed to be a constant or another SSA_NAME)
 181    into the operand pointed to by OP_P.
 182
 183    Use this version for const/copy propagation as it will perform additional
 184    checks to ensure validity of the const/copy propagation.  */
 185
 186 void
 187 propagate_value (use_operand_p op_p, tree val)
 188 {
 189   replace_exp_1 (op_p, val, true);
 190 }
 191
 192 /* Replace *OP_P with value VAL (assumed to be a constant or another SSA_NAME).
 193
 194    Use this version when not const/copy propagating values.  For example,
 195    PRE uses this version when building expressions as they would appear
 196    in specific blocks taking into account actions of PHI nodes.  */
 197
 198 void
 199 replace_exp (use_operand_p op_p, tree val)
 200 {
 201   replace_exp_1 (op_p, val, false);
 202 }
 203
 204
 205 /* Propagate the value VAL (assumed to be a constant or another SSA_NAME)
 206    into the tree pointed to by OP_P.
 207
 208    Use this version for const/copy propagation when SSA operands are not
 209    available.  It will perform the additional checks to ensure validity of
 210    the const/copy propagation, but will not update any operand information.
 211    Be sure to mark the stmt as modified.  */
 212
 213 void
 214 propagate_tree_value (tree *op_p, tree val)
 215 {
 216 #if defined ENABLE_CHECKING
 217   gcc_assert (!(TREE_CODE (val) == SSA_NAME
 218                 && *op_p
 219                 && TREE_CODE (*op_p) == SSA_NAME
 220                 && !may_propagate_copy (*op_p, val)));
 221 #endif
 222
 223   if (TREE_CODE (val) == SSA_NAME)
 224     *op_p = val;
 225   else
 226     *op_p = unsave_expr_now (val);
 227 }
 228
 229
 230 /* Like propagate_tree_value, but use as the operand to replace
 231    the principal expression (typically, the RHS) contained in the
 232    statement referenced by iterator GSI.  Note that it is not
 233    always possible to update the statement in-place, so a new
 234    statement may be created to replace the original.  */
 235
 236 void
 237 propagate_tree_value_into_stmt (gimple_stmt_iterator *gsi, tree val)
 238 {
 239   gimple stmt = gsi_stmt (*gsi);
 240
 241   if (is_gimple_assign (stmt))
 242     {
 243       tree expr = NULL_TREE;
 244       if (gimple_assign_single_p (stmt))
 245         expr = gimple_assign_rhs1 (stmt);
 246       propagate_tree_value (&expr, val);
 247       gimple_assign_set_rhs_from_tree (gsi, expr);
 248       stmt = gsi_stmt (*gsi);
 249     }
 250   else if (gimple_code (stmt) == GIMPLE_COND)
 251     {
 252       tree lhs = NULL_TREE;
 253       tree rhs = fold_convert (TREE_TYPE (val), integer_zero_node);
 254       propagate_tree_value (&lhs, val);
 255       gimple_cond_set_code (stmt, NE_EXPR);
 256       gimple_cond_set_lhs (stmt, lhs);
 257       gimple_cond_set_rhs (stmt, rhs);
 258     }
 259   else if (is_gimple_call (stmt)
 260            && gimple_call_lhs (stmt) != NULL_TREE)
 261     {
 262       gimple new_stmt;
 263
 264       tree expr = NULL_TREE;
 265       propagate_tree_value (&expr, val);
 266       new_stmt = gimple_build_assign (gimple_call_lhs (stmt), expr);
 267       move_ssa_defining_stmt_for_defs (new_stmt, stmt);
 268       gsi_replace (gsi, new_stmt, false);
 269     }
 270   else if (gimple_code (stmt) == GIMPLE_SWITCH)
 271     propagate_tree_value (gimple_switch_index_ptr (stmt), val);
 272   else
 273     gcc_unreachable ();
 274 }
 275
 276 /*---------------------------------------------------------------------------
 277                                 Copy propagation
 278 ---------------------------------------------------------------------------*/
 279 /* During propagation, we keep chains of variables that are copies of
 280    one another.  If variable X_i is a copy of X_j and X_j is a copy of
 281    X_k, COPY_OF will contain:
 282
 283         COPY_OF[i].VALUE = X_j
 284         COPY_OF[j].VALUE = X_k
 285         COPY_OF[k].VALUE = X_k
 286
 287    After propagation, the copy-of value for each variable X_i is
 288    converted into the final value by walking the copy-of chains and
 289    updating COPY_OF[i].VALUE to be the last element of the chain.  */
 290 static prop_value_t *copy_of;
 291
 292 /* Used in set_copy_of_val to determine if the last link of a copy-of
 293    chain has changed.  */
 294 static tree *cached_last_copy_of;
 295
 296
 297 /* Return true if this statement may generate a useful copy.  */
 298
 299 static bool
 300 stmt_may_generate_copy (gimple stmt)
 301 {
 302   if (gimple_code (stmt) == GIMPLE_PHI)
 303     return !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (stmt));
 304
 305   if (gimple_code (stmt) != GIMPLE_ASSIGN)
 306     return false;
 307
 308   /* If the statement has volatile operands, it won't generate a
 309      useful copy.  */
 310   if (gimple_has_volatile_ops (stmt))
 311     return false;
 312
 313   /* Statements with loads and/or stores will never generate a useful copy.  */
 314   if (gimple_vuse (stmt))
 315     return false;
 316
 317   /* Otherwise, the only statements that generate useful copies are
 318      assignments whose RHS is just an SSA name that doesn't flow
 319      through abnormal edges.  */
 320   return (gimple_assign_rhs_code (stmt) == SSA_NAME
 321           && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt)));
 322 }
 323
 324
 325 /* Return the copy-of value for VAR.  */
 326
 327 static inline prop_value_t *
 328 get_copy_of_val (tree var)
 329 {
 330   prop_value_t *val = &copy_of[SSA_NAME_VERSION (var)];
 331
 332   if (val->value == NULL_TREE
 333       && !stmt_may_generate_copy (SSA_NAME_DEF_STMT (var)))
 334     {
 335       /* If the variable will never generate a useful copy relation,
 336          make it its own copy.  */
 337       val->value = var;
 338     }
 339
 340   return val;
 341 }
 342
 343
 344 /* Return last link in the copy-of chain for VAR.  */
 345
 346 static tree
 347 get_last_copy_of (tree var)
 348 {
 349   tree last;
 350   int i;
 351
 352   /* Traverse COPY_OF starting at VAR until we get to the last
 353      link in the chain.  Since it is possible to have cycles in PHI
 354      nodes, the copy-of chain may also contain cycles.
 355
 356      To avoid infinite loops and to avoid traversing lengthy copy-of
 357      chains, we artificially limit the maximum number of chains we are
 358      willing to traverse.
 359
 360      The value 5 was taken from a compiler and runtime library
 361      bootstrap and a mixture of C and C++ code from various sources.
 362      More than 82% of all copy-of chains were shorter than 5 links.  */
 363 #define LIMIT   5
 364
 365   last = var;
 366   for (i = 0; i < LIMIT; i++)
 367     {
 368       tree copy = copy_of[SSA_NAME_VERSION (last)].value;
 369       if (copy == NULL_TREE || copy == last)
 370         break;
 371       last = copy;
 372     }
 373
 374   /* If we have reached the limit, then we are either in a copy-of
 375      cycle or the copy-of chain is too long.  In this case, just
 376      return VAR so that it is not considered a copy of anything.  */
 377   return (i < LIMIT ? last : var);
 378 }
 379
 380
 381 /* Set FIRST to be the first variable in the copy-of chain for DEST.
 382    If DEST's copy-of value or its copy-of chain has changed, return
 383    true.
 384
 385    MEM_REF is the memory reference where FIRST is stored.  This is
 386    used when DEST is a non-register and we are copy propagating loads
 387    and stores.  */
 388
 389 static inline bool
 390 set_copy_of_val (tree dest, tree first)
 391 {
 392   unsigned int dest_ver = SSA_NAME_VERSION (dest);
 393   tree old_first, old_last, new_last;
 394
 395   /* Set FIRST to be the first link in COPY_OF[DEST].  If that
 396      changed, return true.  */
 397   old_first = copy_of[dest_ver].value;
 398   copy_of[dest_ver].value = first;
 399
 400   if (old_first != first)
 401     return true;
 402
 403   /* If FIRST and OLD_FIRST are the same, we need to check whether the
 404      copy-of chain starting at FIRST ends in a different variable.  If
 405      the copy-of chain starting at FIRST ends up in a different
 406      variable than the last cached value we had for DEST, then return
 407      true because DEST is now a copy of a different variable.
 408
 409      This test is necessary because even though the first link in the
 410      copy-of chain may not have changed, if any of the variables in
 411      the copy-of chain changed its final value, DEST will now be the
 412      copy of a different variable, so we have to do another round of
 413      propagation for everything that depends on DEST.  */
 414   old_last = cached_last_copy_of[dest_ver];
 415   new_last = get_last_copy_of (dest);
 416   cached_last_copy_of[dest_ver] = new_last;
 417
 418   return (old_last != new_last);
 419 }
 420
 421
 422 /* Dump the copy-of value for variable VAR to FILE.  */
 423
 424 static void
 425 dump_copy_of (FILE *file, tree var)
 426 {
 427   tree val;
 428   sbitmap visited;
 429
 430   print_generic_expr (file, var, dump_flags);
 431
 432   if (TREE_CODE (var) != SSA_NAME)
 433     return;
 434
 435   visited = sbitmap_alloc (num_ssa_names);
 436   sbitmap_zero (visited);
 437   SET_BIT (visited, SSA_NAME_VERSION (var));
 438
 439   fprintf (file, " copy-of chain: ");
 440
 441   val = var;
 442   print_generic_expr (file, val, 0);
 443   fprintf (file, " ");
 444   while (copy_of[SSA_NAME_VERSION (val)].value)
 445     {
 446       fprintf (file, "-> ");
 447       val = copy_of[SSA_NAME_VERSION (val)].value;
 448       print_generic_expr (file, val, 0);
 449       fprintf (file, " ");
 450       if (TEST_BIT (visited, SSA_NAME_VERSION (val)))
 451         break;
 452       SET_BIT (visited, SSA_NAME_VERSION (val));
 453     }
 454
 455   val = get_copy_of_val (var)->value;
 456   if (val == NULL_TREE)
 457     fprintf (file, "[UNDEFINED]");
 458   else if (val != var)
 459     fprintf (file, "[COPY]");
 460   else
 461     fprintf (file, "[NOT A COPY]");
 462
 463   sbitmap_free (visited);
 464 }
 465
 466
 467 /* Evaluate the RHS of STMT.  If it produces a valid copy, set the LHS
 468    value and store the LHS into *RESULT_P.  If STMT generates more
 469    than one name (i.e., STMT is an aliased store), it is enough to
 470    store the first name in the VDEF list into *RESULT_P.  After
 471    all, the names generated will be VUSEd in the same statements.  */
 472
 473 static enum ssa_prop_result
 474 copy_prop_visit_assignment (gimple stmt, tree *result_p)
 475 {
 476   tree lhs, rhs;
 477   prop_value_t *rhs_val;
 478
 479   lhs = gimple_assign_lhs (stmt);
 480   rhs = gimple_assign_rhs1 (stmt);
 481
 482
 483   gcc_assert (gimple_assign_rhs_code (stmt) == SSA_NAME);
 484
 485   rhs_val = get_copy_of_val (rhs);
 486
 487   if (TREE_CODE (lhs) == SSA_NAME)
 488     {
 489       /* Straight copy between two SSA names.  First, make sure that
 490          we can propagate the RHS into uses of LHS.  */
 491       if (!may_propagate_copy (lhs, rhs))
 492         return SSA_PROP_VARYING;
 493
 494       /* Notice that in the case of assignments, we make the LHS be a
 495          copy of RHS's value, not of RHS itself.  This avoids keeping
 496          unnecessary copy-of chains (assignments cannot be in a cycle
 497          like PHI nodes), speeding up the propagation process.
 498          This is different from what we do in copy_prop_visit_phi_node.
 499          In those cases, we are interested in the copy-of chains.  */
 500       *result_p = lhs;
 501       if (set_copy_of_val (*result_p, rhs_val->value))
 502         return SSA_PROP_INTERESTING;
 503       else
 504         return SSA_PROP_NOT_INTERESTING;
 505     }
 506
 507   return SSA_PROP_VARYING;
 508 }
 509
 510
 511 /* Visit the GIMPLE_COND STMT.  Return SSA_PROP_INTERESTING
 512    if it can determine which edge will be taken.  Otherwise, return
 513    SSA_PROP_VARYING.  */
 514
 515 static enum ssa_prop_result
 516 copy_prop_visit_cond_stmt (gimple stmt, edge *taken_edge_p)
 517 {
 518   enum ssa_prop_result retval = SSA_PROP_VARYING;
 519   location_t loc = gimple_location (stmt);
 520
 521   tree op0 = gimple_cond_lhs (stmt);
 522   tree op1 = gimple_cond_rhs (stmt);
 523
 524   /* The only conditionals that we may be able to compute statically
 525      are predicates involving two SSA_NAMEs.  */
 526   if (TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME)
 527     {
 528       op0 = get_last_copy_of (op0);
 529       op1 = get_last_copy_of (op1);
 530
 531       /* See if we can determine the predicate's value.  */
 532       if (dump_file && (dump_flags & TDF_DETAILS))
 533         {
 534           fprintf (dump_file, "Trying to determine truth value of ");
 535           fprintf (dump_file, "predicate ");
 536           print_gimple_stmt (dump_file, stmt, 0, 0);
 537         }
 538
 539       /* We can fold COND and get a useful result only when we have
 540          the same SSA_NAME on both sides of a comparison operator.  */
 541       if (op0 == op1)
 542         {
 543           tree folded_cond = fold_binary_loc (loc, gimple_cond_code (stmt),
 544                                           boolean_type_node, op0, op1);
 545           if (folded_cond)
 546             {
 547               basic_block bb = gimple_bb (stmt);
 548               *taken_edge_p = find_taken_edge (bb, folded_cond);
 549               if (*taken_edge_p)
 550                 retval = SSA_PROP_INTERESTING;
 551             }
 552         }
 553     }
 554
 555   if (dump_file && (dump_flags & TDF_DETAILS) && *taken_edge_p)
 556     fprintf (dump_file, "\nConditional will always take edge %d->%d\n",
 557              (*taken_edge_p)->src->index, (*taken_edge_p)->dest->index);
 558
 559   return retval;
 560 }
 561
 562
 563 /* Evaluate statement STMT.  If the statement produces a new output
 564    value, return SSA_PROP_INTERESTING and store the SSA_NAME holding
 565    the new value in *RESULT_P.
 566
 567    If STMT is a conditional branch and we can determine its truth
 568    value, set *TAKEN_EDGE_P accordingly.
 569
 570    If the new value produced by STMT is varying, return
 571    SSA_PROP_VARYING.  */
 572
 573 static enum ssa_prop_result
 574 copy_prop_visit_stmt (gimple stmt, edge *taken_edge_p, tree *result_p)
 575 {
 576   enum ssa_prop_result retval;
 577
 578   if (dump_file && (dump_flags & TDF_DETAILS))
 579     {
 580       fprintf (dump_file, "\nVisiting statement:\n");
 581       print_gimple_stmt (dump_file, stmt, 0, dump_flags);
 582       fprintf (dump_file, "\n");
 583     }
 584
 585   if (gimple_assign_single_p (stmt)
 586       && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME
 587       && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
 588     {
 589       /* If the statement is a copy assignment, evaluate its RHS to
 590          see if the lattice value of its output has changed.  */
 591       retval = copy_prop_visit_assignment (stmt, result_p);
 592     }
 593   else if (gimple_code (stmt) == GIMPLE_COND)
 594     {
 595       /* See if we can determine which edge goes out of a conditional
 596          jump.  */
 597       retval = copy_prop_visit_cond_stmt (stmt, taken_edge_p);
 598     }
 599   else
 600     retval = SSA_PROP_VARYING;
 601
 602   if (retval == SSA_PROP_VARYING)
 603     {
 604       tree def;
 605       ssa_op_iter i;
 606
 607       /* Any other kind of statement is not interesting for constant
 608          propagation and, therefore, not worth simulating.  */
 609       if (dump_file && (dump_flags & TDF_DETAILS))
 610         fprintf (dump_file, "No interesting values produced.\n");
 611
 612       /* The assignment is not a copy operation.  Don't visit this
 613          statement again and mark all the definitions in the statement
 614          to be copies of nothing.  */
 615       FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_ALL_DEFS)
 616         set_copy_of_val (def, def);
 617     }
 618
 619   return retval;
 620 }
 621
 622
 623 /* Visit PHI node PHI.  If all the arguments produce the same value,
 624    set it to be the value of the LHS of PHI.  */
 625
 626 static enum ssa_prop_result
 627 copy_prop_visit_phi_node (gimple phi)
 628 {
 629   enum ssa_prop_result retval;
 630   unsigned i;
 631   prop_value_t phi_val = { 0, NULL_TREE };
 632
 633   tree lhs = gimple_phi_result (phi);
 634
 635   if (dump_file && (dump_flags & TDF_DETAILS))
 636     {
 637       fprintf (dump_file, "\nVisiting PHI node: ");
 638       print_gimple_stmt (dump_file, phi, 0, dump_flags);
 639       fprintf (dump_file, "\n\n");
 640     }
 641
 642   for (i = 0; i < gimple_phi_num_args (phi); i++)
 643     {
 644       prop_value_t *arg_val;
 645       tree arg = gimple_phi_arg_def (phi, i);
 646       edge e = gimple_phi_arg_edge (phi, i);
 647
 648       /* We don't care about values flowing through non-executable
 649          edges.  */
 650       if (!(e->flags & EDGE_EXECUTABLE))
 651         continue;
 652
 653       /* Constants in the argument list never generate a useful copy.
 654          Similarly, names that flow through abnormal edges cannot be
 655          used to derive copies.  */
 656       if (TREE_CODE (arg) != SSA_NAME || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (arg))
 657         {
 658           phi_val.value = lhs;
 659           break;
 660         }
 661
 662       /* Avoid copy propagation from an inner into an outer loop.
 663          Otherwise, this may move loop variant variables outside of
 664          their loops and prevent coalescing opportunities.  If the
 665          value was loop invariant, it will be hoisted by LICM and
 666          exposed for copy propagation.  Not a problem for virtual
 667          operands though.  */
 668       if (is_gimple_reg (lhs)
 669           && loop_depth_of_name (arg) > loop_depth_of_name (lhs))
 670         {
 671           phi_val.value = lhs;
 672           break;
 673         }
 674
 675       /* If the LHS appears in the argument list, ignore it.  It is
 676          irrelevant as a copy.  */
 677       if (arg == lhs || get_last_copy_of (arg) == lhs)
 678         continue;
 679
 680       if (dump_file && (dump_flags & TDF_DETAILS))
 681         {
 682           fprintf (dump_file, "\tArgument #%d: ", i);
 683           dump_copy_of (dump_file, arg);
 684           fprintf (dump_file, "\n");
 685         }
 686
 687       arg_val = get_copy_of_val (arg);
 688
 689       /* If the LHS didn't have a value yet, make it a copy of the
 690          first argument we find.  Notice that while we make the LHS be
 691          a copy of the argument itself, we take the memory reference
 692          from the argument's value so that we can compare it to the
 693          memory reference of all the other arguments.  */
 694       if (phi_val.value == NULL_TREE)
 695         {
 696           phi_val.value = arg_val->value ? arg_val->value : arg;
 697           continue;
 698         }
 699
 700       /* If PHI_VAL and ARG don't have a common copy-of chain, then
 701          this PHI node cannot be a copy operation.  Also, if we are
 702          copy propagating stores and these two arguments came from
 703          different memory references, they cannot be considered
 704          copies.  */
 705       if (get_last_copy_of (phi_val.value) != get_last_copy_of (arg))
 706         {
 707           phi_val.value = lhs;
 708           break;
 709         }
 710     }
 711
 712   if (phi_val.value &&  may_propagate_copy (lhs, phi_val.value)
 713       && set_copy_of_val (lhs, phi_val.value))
 714     retval = (phi_val.value != lhs) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING;
 715   else
 716     retval = SSA_PROP_NOT_INTERESTING;
 717
 718   if (dump_file && (dump_flags & TDF_DETAILS))
 719     {
 720       fprintf (dump_file, "\nPHI node ");
 721       dump_copy_of (dump_file, lhs);
 722       fprintf (dump_file, "\nTelling the propagator to ");
 723       if (retval == SSA_PROP_INTERESTING)
 724         fprintf (dump_file, "add SSA edges out of this PHI and continue.");
 725       else if (retval == SSA_PROP_VARYING)
 726         fprintf (dump_file, "add SSA edges out of this PHI and never visit again.");
 727       else
 728         fprintf (dump_file, "do nothing with SSA edges and keep iterating.");
 729       fprintf (dump_file, "\n\n");
 730     }
 731
 732   return retval;
 733 }
 734
 735
 736 /* Initialize structures used for copy propagation.   PHIS_ONLY is true
 737    if we should only consider PHI nodes as generating copy propagation
 738    opportunities.  */
 739
 740 static void
 741 init_copy_prop (void)
 742 {
 743   basic_block bb;
 744
 745   copy_of = XCNEWVEC (prop_value_t, num_ssa_names);
 746
 747   cached_last_copy_of = XCNEWVEC (tree, num_ssa_names);
 748
 749   FOR_EACH_BB (bb)
 750     {
 751       gimple_stmt_iterator si;
 752       int depth = bb->loop_depth;
 753       bool loop_exit_p = false;
 754
 755       for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
 756         {
 757           gimple stmt = gsi_stmt (si);
 758           ssa_op_iter iter;
 759           tree def;
 760
 761           /* The only statements that we care about are those that may
 762              generate useful copies.  We also need to mark conditional
 763              jumps so that their outgoing edges are added to the work
 764              lists of the propagator.
 765
 766              Avoid copy propagation from an inner into an outer loop.
 767              Otherwise, this may move loop variant variables outside of
 768              their loops and prevent coalescing opportunities.  If the
 769              value was loop invariant, it will be hoisted by LICM and
 770              exposed for copy propagation.  */
 771           if (stmt_ends_bb_p (stmt))
 772             prop_set_simulate_again (stmt, true);
 773           else if (stmt_may_generate_copy (stmt)
 774                    /* Since we are iterating over the statements in
 775                       BB, not the phi nodes, STMT will always be an
 776                       assignment.  */
 777                    && loop_depth_of_name (gimple_assign_rhs1 (stmt)) <= depth)
 778             prop_set_simulate_again (stmt, true);
 779           else
 780             prop_set_simulate_again (stmt, false);
 781
 782           /* Mark all the outputs of this statement as not being
 783              the copy of anything.  */
 784           FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
 785             if (!prop_simulate_again_p (stmt))
 786               set_copy_of_val (def, def);
 787             else
 788               cached_last_copy_of[SSA_NAME_VERSION (def)] = def;
 789         }
 790
 791       /* In loop-closed SSA form do not copy-propagate through
 792          PHI nodes in blocks with a loop exit edge predecessor.  */
 793       if (current_loops
 794           && loops_state_satisfies_p (LOOP_CLOSED_SSA))
 795         {
 796           edge_iterator ei;
 797           edge e;
 798           FOR_EACH_EDGE (e, ei, bb->preds)
 799             if (loop_exit_edge_p (e->src->loop_father, e))
 800               loop_exit_p = true;
 801         }
 802
 803       for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
 804         {
 805           gimple phi = gsi_stmt (si);
 806           tree def;
 807
 808           def = gimple_phi_result (phi);
 809           if (!is_gimple_reg (def)
 810               || loop_exit_p)
 811             prop_set_simulate_again (phi, false);
 812           else
 813             prop_set_simulate_again (phi, true);
 814
 815           if (!prop_simulate_again_p (phi))
 816             set_copy_of_val (def, def);
 817           else
 818             cached_last_copy_of[SSA_NAME_VERSION (def)] = def;
 819         }
 820     }
 821 }
 822
 823
 824 /* Deallocate memory used in copy propagation and do final
 825    substitution.  */
 826
 827 static void
 828 fini_copy_prop (void)
 829 {
 830   size_t i;
 831   prop_value_t *tmp;
 832
 833   /* Set the final copy-of value for each variable by traversing the
 834      copy-of chains.  */
 835   tmp = XCNEWVEC (prop_value_t, num_ssa_names);
 836   for (i = 1; i < num_ssa_names; i++)
 837     {
 838       tree var = ssa_name (i);
 839       if (!var
 840           || !copy_of[i].value
 841           || copy_of[i].value == var)
 842         continue;
 843
 844       tmp[i].value = get_last_copy_of (var);
 845
 846       /* In theory the points-to solution of all members of the
 847          copy chain is their intersection.  For now we do not bother
 848          to compute this but only make sure we do not lose points-to
 849          information completely by setting the points-to solution
 850          of the representative to the first solution we find if
 851          it doesn't have one already.  */
 852       if (tmp[i].value != var
 853           && POINTER_TYPE_P (TREE_TYPE (var))
 854           && SSA_NAME_PTR_INFO (var)
 855           && !SSA_NAME_PTR_INFO (tmp[i].value))
 856         duplicate_ssa_name_ptr_info (tmp[i].value, SSA_NAME_PTR_INFO (var));
 857     }
 858
 859   substitute_and_fold (tmp, NULL);
 860
 861   free (cached_last_copy_of);
 862   free (copy_of);
 863   free (tmp);
 864 }
 865
 866
 867 /* Main entry point to the copy propagator.
 868
 869    PHIS_ONLY is true if we should only consider PHI nodes as generating
 870    copy propagation opportunities.
 871
 872    The algorithm propagates the value COPY-OF using ssa_propagate.  For
 873    every variable X_i, COPY-OF(X_i) indicates which variable is X_i created
 874    from.  The following example shows how the algorithm proceeds at a
 875    high level:
 876
 877             1   a_24 = x_1
 878             2   a_2 = PHI <a_24, x_1>
 879             3   a_5 = PHI <a_2>
 880             4   x_1 = PHI <x_298, a_5, a_2>
 881
 882    The end result should be that a_2, a_5, a_24 and x_1 are a copy of
 883    x_298.  Propagation proceeds as follows.
 884
 885    Visit #1: a_24 is copy-of x_1.  Value changed.
 886    Visit #2: a_2 is copy-of x_1.  Value changed.
 887    Visit #3: a_5 is copy-of x_1.  Value changed.
 888    Visit #4: x_1 is copy-of x_298.  Value changed.
 889    Visit #1: a_24 is copy-of x_298.  Value changed.
 890    Visit #2: a_2 is copy-of x_298.  Value changed.
 891    Visit #3: a_5 is copy-of x_298.  Value changed.
 892    Visit #4: x_1 is copy-of x_298.  Stable state reached.
 893
 894    When visiting PHI nodes, we only consider arguments that flow
 895    through edges marked executable by the propagation engine.  So,
 896    when visiting statement #2 for the first time, we will only look at
 897    the first argument (a_24) and optimistically assume that its value
 898    is the copy of a_24 (x_1).
 899
 900    The problem with this approach is that it may fail to discover copy
 901    relations in PHI cycles.  Instead of propagating copy-of
 902    values, we actually propagate copy-of chains.  For instance:
 903
 904                 A_3 = B_1;
 905                 C_9 = A_3;
 906                 D_4 = C_9;
 907                 X_i = D_4;
 908
 909    In this code fragment, COPY-OF (X_i) = { D_4, C_9, A_3, B_1 }.
 910    Obviously, we are only really interested in the last value of the
 911    chain, however the propagator needs to access the copy-of chain
 912    when visiting PHI nodes.
 913
 914    To represent the copy-of chain, we use the array COPY_CHAINS, which
 915    holds the first link in the copy-of chain for every variable.
 916    If variable X_i is a copy of X_j, which in turn is a copy of X_k,
 917    the array will contain:
 918
 919                 COPY_CHAINS[i] = X_j
 920                 COPY_CHAINS[j] = X_k
 921                 COPY_CHAINS[k] = X_k
 922
 923    Keeping copy-of chains instead of copy-of values directly becomes
 924    important when visiting PHI nodes.  Suppose that we had the
 925    following PHI cycle, such that x_52 is already considered a copy of
 926    x_53:
 927
 928             1   x_54 = PHI <x_53, x_52>
 929             2   x_53 = PHI <x_898, x_54>
 930
 931    Visit #1: x_54 is copy-of x_53 (because x_52 is copy-of x_53)
 932    Visit #2: x_53 is copy-of x_898 (because x_54 is a copy of x_53,
 933                                     so it is considered irrelevant
 934                                     as a copy).
 935    Visit #1: x_54 is copy-of nothing (x_53 is a copy-of x_898 and
 936                                       x_52 is a copy of x_53, so
 937                                       they don't match)
 938    Visit #2: x_53 is copy-of nothing
 939
 940    This problem is avoided by keeping a chain of copies, instead of
 941    the final copy-of value.  Propagation will now only keep the first
 942    element of a variable's copy-of chain.  When visiting PHI nodes,
 943    arguments are considered equal if their copy-of chains end in the
 944    same variable.  So, as long as their copy-of chains overlap, we
 945    know that they will be a copy of the same variable, regardless of
 946    which variable that may be).
 947
 948    Propagation would then proceed as follows (the notation a -> b
 949    means that a is a copy-of b):
 950
 951    Visit #1: x_54 = PHI <x_53, x_52>
 952                 x_53 -> x_53
 953                 x_52 -> x_53
 954                 Result: x_54 -> x_53.  Value changed.  Add SSA edges.
 955
 956    Visit #1: x_53 = PHI <x_898, x_54>
 957                 x_898 -> x_898
 958                 x_54 -> x_53
 959                 Result: x_53 -> x_898.  Value changed.  Add SSA edges.
 960
 961    Visit #2: x_54 = PHI <x_53, x_52>
 962                 x_53 -> x_898
 963                 x_52 -> x_53 -> x_898
 964                 Result: x_54 -> x_898.  Value changed.  Add SSA edges.
 965
 966    Visit #2: x_53 = PHI <x_898, x_54>
 967                 x_898 -> x_898
 968                 x_54 -> x_898
 969                 Result: x_53 -> x_898.  Value didn't change.  Stable state
 970
 971    Once the propagator stabilizes, we end up with the desired result
 972    x_53 and x_54 are both copies of x_898.  */
 973
 974 static unsigned int
 975 execute_copy_prop (void)
 976 {
 977   init_copy_prop ();
 978   ssa_propagate (copy_prop_visit_stmt, copy_prop_visit_phi_node);
 979   fini_copy_prop ();
 980   return 0;
 981 }
 982
 983 static bool
 984 gate_copy_prop (void)
 985 {
 986   return flag_tree_copy_prop != 0;
 987 }
 988
 989 struct gimple_opt_pass pass_copy_prop =
 990 {
 991  {
 992   GIMPLE_PASS,
 993   "copyprop",                           /* name */
 994   gate_copy_prop,                       /* gate */
 995   execute_copy_prop,                    /* execute */
 996   NULL,                                 /* sub */
 997   NULL,                                 /* next */
 998   0,                                    /* static_pass_number */
 999   TV_TREE_COPY_PROP,                    /* tv_id */
1000   PROP_ssa | PROP_cfg,                  /* properties_required */
1001   0,                                    /* properties_provided */
1002   0,                                    /* properties_destroyed */
1003   0,                                    /* todo_flags_start */
1004   TODO_cleanup_cfg
1005     | TODO_dump_func
1006     | TODO_ggc_collect
1007     | TODO_verify_ssa
1008     | TODO_update_ssa                   /* todo_flags_finish */
1009  }
1010 };