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