gcc/tree-ssa-copy.c

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