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