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