gcc/tree-ssa-copy.c

   1 /* Copy propagation and SSA_NAME replacement support routines.
   2    Copyright (C) 2004, 2005, 2006, 2007, 2008, 2010
   3    Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "flags.h"
  27 #include "tm_p.h"
  28 #include "basic-block.h"
  29 #include "output.h"
  30 #include "function.h"
  31 #include "tree-pretty-print.h"
  32 #include "gimple-pretty-print.h"
  33 #include "timevar.h"
  34 #include "tree-dump.h"
  35 #include "tree-flow.h"
  36 #include "tree-pass.h"
  37 #include "tree-ssa-propagate.h"
  38 #include "langhooks.h"
  39 #include "cfgloop.h"
  40
  41 /* This file implements the copy propagation pass and provides a
  42    handful of interfaces for performing const/copy propagation and
  43    simple expression replacement which keep variable annotations
  44    up-to-date.
  45
  46    We require that for any copy operation where the RHS and LHS have
  47    a non-null memory tag the memory tag be the same.   It is OK
  48    for one or both of the memory tags to be NULL.
  49
  50    We also require tracking if a variable is dereferenced in a load or
  51    store operation.
  52
  53    We enforce these requirements by having all copy propagation and
  54    replacements of one SSA_NAME with a different SSA_NAME to use the
  55    APIs defined in this file.  */
  56
  57 /* Return true if we may propagate ORIG into DEST, false otherwise.  */
  58
  59 bool
  60 may_propagate_copy (tree dest, tree orig)
  61 {
  62   tree type_d = TREE_TYPE (dest);
  63   tree type_o = TREE_TYPE (orig);
  64
  65   /* If ORIG flows in from an abnormal edge, it cannot be propagated.  */
  66   if (TREE_CODE (orig) == SSA_NAME
  67       && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig))
  68     return false;
  69
  70   /* If DEST is an SSA_NAME that flows from an abnormal edge, then it
  71      cannot be replaced.  */
  72   if (TREE_CODE (dest) == SSA_NAME
  73       && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (dest))
  74     return false;
  75
  76   /* Do not copy between types for which we *do* need a conversion.  */
  77   if (!useless_type_conversion_p (type_d, type_o))
  78     return false;
  79
  80   /* Propagating virtual operands is always ok.  */
  81   if (TREE_CODE (dest) == SSA_NAME && !is_gimple_reg (dest))
  82     {
  83       /* But only between virtual operands.  */
  84       gcc_assert (TREE_CODE (orig) == SSA_NAME && !is_gimple_reg (orig));
  85
  86       return true;
  87     }
  88
  89   /* Anything else is OK.  */
  90   return true;
  91 }
  92
  93 /* Like may_propagate_copy, but use as the destination expression
  94    the principal expression (typically, the RHS) contained in
  95    statement DEST.  This is more efficient when working with the
  96    gimple tuples representation.  */
  97
  98 bool
  99 may_propagate_copy_into_stmt (gimple dest, tree orig)
 100 {
 101   tree type_d;
 102   tree type_o;
 103
 104   /* If the statement is a switch or a single-rhs assignment,
 105      then the expression to be replaced by the propagation may
 106      be an SSA_NAME.  Fortunately, there is an explicit tree
 107      for the expression, so we delegate to may_propagate_copy.  */
 108
 109   if (gimple_assign_single_p (dest))
 110     return may_propagate_copy (gimple_assign_rhs1 (dest), orig);
 111   else if (gimple_code (dest) == GIMPLE_SWITCH)
 112     return may_propagate_copy (gimple_switch_index (dest), orig);
 113
 114   /* In other cases, the expression is not materialized, so there
 115      is no destination to pass to may_propagate_copy.  On the other
 116      hand, the expression cannot be an SSA_NAME, so the analysis
 117      is much simpler.  */
 118
 119   if (TREE_CODE (orig) == SSA_NAME
 120       && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig))
 121     return false;
 122
 123   if (is_gimple_assign (dest))
 124     type_d = TREE_TYPE (gimple_assign_lhs (dest));
 125   else if (gimple_code (dest) == GIMPLE_COND)
 126     type_d = boolean_type_node;
 127   else if (is_gimple_call (dest)
 128            && gimple_call_lhs (dest) != NULL_TREE)
 129     type_d = TREE_TYPE (gimple_call_lhs (dest));
 130   else
 131     gcc_unreachable ();
 132
 133   type_o = TREE_TYPE (orig);
 134
 135   if (!useless_type_conversion_p (type_d, type_o))
 136     return false;
 137
 138   return true;
 139 }
 140
 141 /* Similarly, but we know that we're propagating into an ASM_EXPR.  */
 142
 143 bool
 144 may_propagate_copy_into_asm (tree dest)
 145 {
 146   /* Hard register operands of asms are special.  Do not bypass.  */
 147   return !(TREE_CODE (dest) == SSA_NAME
 148            && TREE_CODE (SSA_NAME_VAR (dest)) == VAR_DECL
 149            && DECL_HARD_REGISTER (SSA_NAME_VAR (dest)));
 150 }
 151
 152
 153 /* Common code for propagate_value and replace_exp.
 154
 155    Replace use operand OP_P with VAL.  FOR_PROPAGATION indicates if the
 156    replacement is done to propagate a value or not.  */
 157
 158 static void
 159 replace_exp_1 (use_operand_p op_p, tree val,
 160                bool for_propagation ATTRIBUTE_UNUSED)
 161 {
 162 #if defined ENABLE_CHECKING
 163   tree op = USE_FROM_PTR (op_p);
 164
 165   gcc_assert (!(for_propagation
 166                 && TREE_CODE (op) == SSA_NAME
 167                 && TREE_CODE (val) == SSA_NAME
 168                 && !may_propagate_copy (op, val)));
 169 #endif
 170
 171   if (TREE_CODE (val) == SSA_NAME)
 172     SET_USE (op_p, val);
 173   else
 174     SET_USE (op_p, unsave_expr_now (val));
 175 }
 176
 177
 178 /* Propagate the value VAL (assumed to be a constant or another SSA_NAME)
 179    into the operand pointed to by OP_P.
 180
 181    Use this version for const/copy propagation as it will perform additional
 182    checks to ensure validity of the const/copy propagation.  */
 183
 184 void
 185 propagate_value (use_operand_p op_p, tree val)
 186 {
 187   replace_exp_1 (op_p, val, true);
 188 }
 189
 190 /* Replace *OP_P with value VAL (assumed to be a constant or another SSA_NAME).
 191
 192    Use this version when not const/copy propagating values.  For example,
 193    PRE uses this version when building expressions as they would appear
 194    in specific blocks taking into account actions of PHI nodes.
 195
 196    The statement in which an expression has been replaced should be
 197    folded using fold_stmt_inplace.  */
 198
 199 void
 200 replace_exp (use_operand_p op_p, tree val)
 201 {
 202   replace_exp_1 (op_p, val, false);
 203 }
 204
 205
 206 /* Propagate the value VAL (assumed to be a constant or another SSA_NAME)
 207    into the tree pointed to by OP_P.
 208
 209    Use this version for const/copy propagation when SSA operands are not
 210    available.  It will perform the additional checks to ensure validity of
 211    the const/copy propagation, but will not update any operand information.
 212    Be sure to mark the stmt as modified.  */
 213
 214 void
 215 propagate_tree_value (tree *op_p, tree val)
 216 {
 217   gcc_checking_assert (!(TREE_CODE (val) == SSA_NAME
 218                          && *op_p
 219                          && TREE_CODE (*op_p) == SSA_NAME
 220                          && !may_propagate_copy (*op_p, val)));
 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 = build_zero_cst (TREE_TYPE (val));
 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 /* Lattice for copy-propagation.  The lattice is initialized to
 279    UNDEFINED (value == NULL) for SSA names that can become a copy
 280    of something or VARYING (value == self) if not (see get_copy_of_val
 281    and stmt_may_generate_copy).  Other values make the name a COPY
 282    of that value.
 283
 284    When visiting a statement or PHI node the lattice value for an
 285    SSA name can transition from UNDEFINED to COPY to VARYING.  */
 286
 287 struct prop_value_d {
 288     /* Copy-of value.  */
 289     tree value;
 290 };
 291 typedef struct prop_value_d prop_value_t;
 292
 293 static prop_value_t *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 /* Return the variable VAR is a copy of or VAR if VAR isn't the result
 343    of a copy.  */
 344
 345 static inline tree
 346 valueize_val (tree var)
 347 {
 348   if (TREE_CODE (var) == SSA_NAME)
 349     {
 350       tree val = get_copy_of_val (var)->value;
 351       if (val)
 352         return val;
 353     }
 354   return var;
 355 }
 356
 357 /* Set VAL to be the copy of VAR.  If that changed return true.  */
 358
 359 static inline bool
 360 set_copy_of_val (tree var, tree val)
 361 {
 362   unsigned int ver = SSA_NAME_VERSION (var);
 363   tree old;
 364
 365   /* Set FIRST to be the first link in COPY_OF[DEST].  If that
 366      changed, return true.  */
 367   old = copy_of[ver].value;
 368   copy_of[ver].value = val;
 369
 370   if (old != val
 371       || (val && !operand_equal_p (old, val, 0)))
 372     return true;
 373
 374   return false;
 375 }
 376
 377
 378 /* Dump the copy-of value for variable VAR to FILE.  */
 379
 380 static void
 381 dump_copy_of (FILE *file, tree var)
 382 {
 383   tree val;
 384
 385   print_generic_expr (file, var, dump_flags);
 386   if (TREE_CODE (var) != SSA_NAME)
 387     return;
 388
 389   val = copy_of[SSA_NAME_VERSION (var)].value;
 390   fprintf (file, " copy-of chain: ");
 391   print_generic_expr (file, var, 0);
 392   fprintf (file, " ");
 393   if (!val)
 394     fprintf (file, "[UNDEFINED]");
 395   else if (val == var)
 396     fprintf (file, "[NOT A COPY]");
 397   else
 398     {
 399       fprintf (file, "-> ");
 400       print_generic_expr (file, val, 0);
 401       fprintf (file, " ");
 402       fprintf (file, "[COPY]");
 403     }
 404 }
 405
 406
 407 /* Evaluate the RHS of STMT.  If it produces a valid copy, set the LHS
 408    value and store the LHS into *RESULT_P.  */
 409
 410 static enum ssa_prop_result
 411 copy_prop_visit_assignment (gimple stmt, tree *result_p)
 412 {
 413   tree lhs, rhs;
 414
 415   lhs = gimple_assign_lhs (stmt);
 416   rhs = valueize_val (gimple_assign_rhs1 (stmt));
 417
 418   if (TREE_CODE (lhs) == SSA_NAME)
 419     {
 420       /* Straight copy between two SSA names.  First, make sure that
 421          we can propagate the RHS into uses of LHS.  */
 422       if (!may_propagate_copy (lhs, rhs))
 423         return SSA_PROP_VARYING;
 424
 425       *result_p = lhs;
 426       if (set_copy_of_val (*result_p, rhs))
 427         return SSA_PROP_INTERESTING;
 428       else
 429         return SSA_PROP_NOT_INTERESTING;
 430     }
 431
 432   return SSA_PROP_VARYING;
 433 }
 434
 435
 436 /* Visit the GIMPLE_COND STMT.  Return SSA_PROP_INTERESTING
 437    if it can determine which edge will be taken.  Otherwise, return
 438    SSA_PROP_VARYING.  */
 439
 440 static enum ssa_prop_result
 441 copy_prop_visit_cond_stmt (gimple stmt, edge *taken_edge_p)
 442 {
 443   enum ssa_prop_result retval = SSA_PROP_VARYING;
 444   location_t loc = gimple_location (stmt);
 445
 446   tree op0 = gimple_cond_lhs (stmt);
 447   tree op1 = gimple_cond_rhs (stmt);
 448
 449   /* The only conditionals that we may be able to compute statically
 450      are predicates involving two SSA_NAMEs.  */
 451   if (TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME)
 452     {
 453       op0 = valueize_val (op0);
 454       op1 = valueize_val (op1);
 455
 456       /* See if we can determine the predicate's value.  */
 457       if (dump_file && (dump_flags & TDF_DETAILS))
 458         {
 459           fprintf (dump_file, "Trying to determine truth value of ");
 460           fprintf (dump_file, "predicate ");
 461           print_gimple_stmt (dump_file, stmt, 0, 0);
 462         }
 463
 464       /* We can fold COND and get a useful result only when we have
 465          the same SSA_NAME on both sides of a comparison operator.  */
 466       if (op0 == op1)
 467         {
 468           tree folded_cond = fold_binary_loc (loc, gimple_cond_code (stmt),
 469                                           boolean_type_node, op0, op1);
 470           if (folded_cond)
 471             {
 472               basic_block bb = gimple_bb (stmt);
 473               *taken_edge_p = find_taken_edge (bb, folded_cond);
 474               if (*taken_edge_p)
 475                 retval = SSA_PROP_INTERESTING;
 476             }
 477         }
 478     }
 479
 480   if (dump_file && (dump_flags & TDF_DETAILS) && *taken_edge_p)
 481     fprintf (dump_file, "\nConditional will always take edge %d->%d\n",
 482              (*taken_edge_p)->src->index, (*taken_edge_p)->dest->index);
 483
 484   return retval;
 485 }
 486
 487
 488 /* Evaluate statement STMT.  If the statement produces a new output
 489    value, return SSA_PROP_INTERESTING and store the SSA_NAME holding
 490    the new value in *RESULT_P.
 491
 492    If STMT is a conditional branch and we can determine its truth
 493    value, set *TAKEN_EDGE_P accordingly.
 494
 495    If the new value produced by STMT is varying, return
 496    SSA_PROP_VARYING.  */
 497
 498 static enum ssa_prop_result
 499 copy_prop_visit_stmt (gimple stmt, edge *taken_edge_p, tree *result_p)
 500 {
 501   enum ssa_prop_result retval;
 502
 503   if (dump_file && (dump_flags & TDF_DETAILS))
 504     {
 505       fprintf (dump_file, "\nVisiting statement:\n");
 506       print_gimple_stmt (dump_file, stmt, 0, dump_flags);
 507       fprintf (dump_file, "\n");
 508     }
 509
 510   if (gimple_assign_single_p (stmt)
 511       && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME
 512       && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
 513           || is_gimple_min_invariant (gimple_assign_rhs1 (stmt))))
 514     {
 515       /* If the statement is a copy assignment, evaluate its RHS to
 516          see if the lattice value of its output has changed.  */
 517       retval = copy_prop_visit_assignment (stmt, result_p);
 518     }
 519   else if (gimple_code (stmt) == GIMPLE_COND)
 520     {
 521       /* See if we can determine which edge goes out of a conditional
 522          jump.  */
 523       retval = copy_prop_visit_cond_stmt (stmt, taken_edge_p);
 524     }
 525   else
 526     retval = SSA_PROP_VARYING;
 527
 528   if (retval == SSA_PROP_VARYING)
 529     {
 530       tree def;
 531       ssa_op_iter i;
 532
 533       /* Any other kind of statement is not interesting for constant
 534          propagation and, therefore, not worth simulating.  */
 535       if (dump_file && (dump_flags & TDF_DETAILS))
 536         fprintf (dump_file, "No interesting values produced.\n");
 537
 538       /* The assignment is not a copy operation.  Don't visit this
 539          statement again and mark all the definitions in the statement
 540          to be copies of nothing.  */
 541       FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_ALL_DEFS)
 542         set_copy_of_val (def, def);
 543     }
 544
 545   return retval;
 546 }
 547
 548
 549 /* Visit PHI node PHI.  If all the arguments produce the same value,
 550    set it to be the value of the LHS of PHI.  */
 551
 552 static enum ssa_prop_result
 553 copy_prop_visit_phi_node (gimple phi)
 554 {
 555   enum ssa_prop_result retval;
 556   unsigned i;
 557   prop_value_t phi_val = { NULL_TREE };
 558
 559   tree lhs = gimple_phi_result (phi);
 560
 561   if (dump_file && (dump_flags & TDF_DETAILS))
 562     {
 563       fprintf (dump_file, "\nVisiting PHI node: ");
 564       print_gimple_stmt (dump_file, phi, 0, dump_flags);
 565     }
 566
 567   for (i = 0; i < gimple_phi_num_args (phi); i++)
 568     {
 569       prop_value_t *arg_val;
 570       tree arg = gimple_phi_arg_def (phi, i);
 571       edge e = gimple_phi_arg_edge (phi, i);
 572
 573       /* We don't care about values flowing through non-executable
 574          edges.  */
 575       if (!(e->flags & EDGE_EXECUTABLE))
 576         continue;
 577
 578       /* Constants in the argument list never generate a useful copy.
 579          Similarly, names that flow through abnormal edges cannot be
 580          used to derive copies.  */
 581       if (TREE_CODE (arg) != SSA_NAME || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (arg))
 582         {
 583           phi_val.value = lhs;
 584           break;
 585         }
 586
 587       /* Avoid copy propagation from an inner into an outer loop.
 588          Otherwise, this may move loop variant variables outside of
 589          their loops and prevent coalescing opportunities.  If the
 590          value was loop invariant, it will be hoisted by LICM and
 591          exposed for copy propagation.  Not a problem for virtual
 592          operands though.
 593          ???  The value will be always loop invariant.  */
 594       if (is_gimple_reg (lhs)
 595           && loop_depth_of_name (arg) > loop_depth_of_name (lhs))
 596         {
 597           phi_val.value = lhs;
 598           break;
 599         }
 600
 601       if (dump_file && (dump_flags & TDF_DETAILS))
 602         {
 603           fprintf (dump_file, "\tArgument #%d: ", i);
 604           dump_copy_of (dump_file, arg);
 605           fprintf (dump_file, "\n");
 606         }
 607
 608       arg_val = get_copy_of_val (arg);
 609
 610       /* If we didn't visit the definition of arg yet treat it as
 611          UNDEFINED.  This also handles PHI arguments that are the
 612          same as lhs.  We'll come here again.  */
 613       if (!arg_val->value)
 614         continue;
 615
 616       /* If the LHS didn't have a value yet, make it a copy of the
 617          first argument we find.   */
 618       if (phi_val.value == NULL_TREE)
 619         {
 620           phi_val.value = arg_val->value;
 621           continue;
 622         }
 623
 624       /* If PHI_VAL and ARG don't have a common copy-of chain, then
 625          this PHI node cannot be a copy operation.  */
 626       if (phi_val.value != arg_val->value
 627           && !operand_equal_p (phi_val.value, arg_val->value, 0))
 628         {
 629           phi_val.value = lhs;
 630           break;
 631         }
 632     }
 633
 634   if (phi_val.value
 635       && may_propagate_copy (lhs, phi_val.value)
 636       && set_copy_of_val (lhs, phi_val.value))
 637     retval = (phi_val.value != lhs) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING;
 638   else
 639     retval = SSA_PROP_NOT_INTERESTING;
 640
 641   if (dump_file && (dump_flags & TDF_DETAILS))
 642     {
 643       fprintf (dump_file, "PHI node ");
 644       dump_copy_of (dump_file, lhs);
 645       fprintf (dump_file, "\nTelling the propagator to ");
 646       if (retval == SSA_PROP_INTERESTING)
 647         fprintf (dump_file, "add SSA edges out of this PHI and continue.");
 648       else if (retval == SSA_PROP_VARYING)
 649         fprintf (dump_file, "add SSA edges out of this PHI and never visit again.");
 650       else
 651         fprintf (dump_file, "do nothing with SSA edges and keep iterating.");
 652       fprintf (dump_file, "\n\n");
 653     }
 654
 655   return retval;
 656 }
 657
 658
 659 /* Initialize structures used for copy propagation.  */
 660
 661 static void
 662 init_copy_prop (void)
 663 {
 664   basic_block bb;
 665
 666   copy_of = XCNEWVEC (prop_value_t, num_ssa_names);
 667
 668   FOR_EACH_BB (bb)
 669     {
 670       gimple_stmt_iterator si;
 671       int depth = bb->loop_depth;
 672       bool loop_exit_p = false;
 673
 674       for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
 675         {
 676           gimple stmt = gsi_stmt (si);
 677           ssa_op_iter iter;
 678           tree def;
 679
 680           /* The only statements that we care about are those that may
 681              generate useful copies.  We also need to mark conditional
 682              jumps so that their outgoing edges are added to the work
 683              lists of the propagator.
 684
 685              Avoid copy propagation from an inner into an outer loop.
 686              Otherwise, this may move loop variant variables outside of
 687              their loops and prevent coalescing opportunities.  If the
 688              value was loop invariant, it will be hoisted by LICM and
 689              exposed for copy propagation.
 690              ???  This doesn't make sense.  */
 691           if (stmt_ends_bb_p (stmt))
 692             prop_set_simulate_again (stmt, true);
 693           else if (stmt_may_generate_copy (stmt)
 694                    /* Since we are iterating over the statements in
 695                       BB, not the phi nodes, STMT will always be an
 696                       assignment.  */
 697                    && loop_depth_of_name (gimple_assign_rhs1 (stmt)) <= depth)
 698             prop_set_simulate_again (stmt, true);
 699           else
 700             prop_set_simulate_again (stmt, false);
 701
 702           /* Mark all the outputs of this statement as not being
 703              the copy of anything.  */
 704           FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
 705             if (!prop_simulate_again_p (stmt))
 706               set_copy_of_val (def, def);
 707         }
 708
 709       /* In loop-closed SSA form do not copy-propagate through
 710          PHI nodes in blocks with a loop exit edge predecessor.  */
 711       if (current_loops
 712           && loops_state_satisfies_p (LOOP_CLOSED_SSA))
 713         {
 714           edge_iterator ei;
 715           edge e;
 716           FOR_EACH_EDGE (e, ei, bb->preds)
 717             if (loop_exit_edge_p (e->src->loop_father, e))
 718               loop_exit_p = true;
 719         }
 720
 721       for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
 722         {
 723           gimple phi = gsi_stmt (si);
 724           tree def;
 725
 726           def = gimple_phi_result (phi);
 727           if (!is_gimple_reg (def)
 728               || loop_exit_p)
 729             prop_set_simulate_again (phi, false);
 730           else
 731             prop_set_simulate_again (phi, true);
 732
 733           if (!prop_simulate_again_p (phi))
 734             set_copy_of_val (def, def);
 735         }
 736     }
 737 }
 738
 739 /* Callback for substitute_and_fold to get at the final copy-of values.  */
 740
 741 static tree
 742 get_value (tree name)
 743 {
 744   tree val = copy_of[SSA_NAME_VERSION (name)].value;
 745   if (val && val != name)
 746     return val;
 747   return NULL_TREE;
 748 }
 749
 750 /* Deallocate memory used in copy propagation and do final
 751    substitution.  */
 752
 753 static void
 754 fini_copy_prop (void)
 755 {
 756   unsigned i;
 757
 758   /* Set the final copy-of value for each variable by traversing the
 759      copy-of chains.  */
 760   for (i = 1; i < num_ssa_names; i++)
 761     {
 762       tree var = ssa_name (i);
 763       if (!var
 764           || !copy_of[i].value
 765           || copy_of[i].value == var)
 766         continue;
 767
 768       /* In theory the points-to solution of all members of the
 769          copy chain is their intersection.  For now we do not bother
 770          to compute this but only make sure we do not lose points-to
 771          information completely by setting the points-to solution
 772          of the representative to the first solution we find if
 773          it doesn't have one already.  */
 774       if (copy_of[i].value != var
 775           && POINTER_TYPE_P (TREE_TYPE (var))
 776           && SSA_NAME_PTR_INFO (var)
 777           && !SSA_NAME_PTR_INFO (copy_of[i].value))
 778         duplicate_ssa_name_ptr_info (copy_of[i].value, SSA_NAME_PTR_INFO (var));
 779     }
 780
 781   /* Don't do DCE if we have loops.  That's the simplest way to not
 782      destroy the scev cache.  */
 783   substitute_and_fold (get_value, NULL, !current_loops);
 784
 785   free (copy_of);
 786 }
 787
 788
 789 /* Main entry point to the copy propagator.
 790
 791    PHIS_ONLY is true if we should only consider PHI nodes as generating
 792    copy propagation opportunities.
 793
 794    The algorithm propagates the value COPY-OF using ssa_propagate.  For
 795    every variable X_i, COPY-OF(X_i) indicates which variable is X_i created
 796    from.  The following example shows how the algorithm proceeds at a
 797    high level:
 798
 799             1   a_24 = x_1
 800             2   a_2 = PHI <a_24, x_1>
 801             3   a_5 = PHI <a_2>
 802             4   x_1 = PHI <x_298, a_5, a_2>
 803
 804    The end result should be that a_2, a_5, a_24 and x_1 are a copy of
 805    x_298.  Propagation proceeds as follows.
 806
 807    Visit #1: a_24 is copy-of x_1.  Value changed.
 808    Visit #2: a_2 is copy-of x_1.  Value changed.
 809    Visit #3: a_5 is copy-of x_1.  Value changed.
 810    Visit #4: x_1 is copy-of x_298.  Value changed.
 811    Visit #1: a_24 is copy-of x_298.  Value changed.
 812    Visit #2: a_2 is copy-of x_298.  Value changed.
 813    Visit #3: a_5 is copy-of x_298.  Value changed.
 814    Visit #4: x_1 is copy-of x_298.  Stable state reached.
 815
 816    When visiting PHI nodes, we only consider arguments that flow
 817    through edges marked executable by the propagation engine.  So,
 818    when visiting statement #2 for the first time, we will only look at
 819    the first argument (a_24) and optimistically assume that its value
 820    is the copy of a_24 (x_1).  */
 821
 822 static unsigned int
 823 execute_copy_prop (void)
 824 {
 825   init_copy_prop ();
 826   ssa_propagate (copy_prop_visit_stmt, copy_prop_visit_phi_node);
 827   fini_copy_prop ();
 828   return 0;
 829 }
 830
 831 static bool
 832 gate_copy_prop (void)
 833 {
 834   return flag_tree_copy_prop != 0;
 835 }
 836
 837 struct gimple_opt_pass pass_copy_prop =
 838 {
 839  {
 840   GIMPLE_PASS,
 841   "copyprop",                           /* name */
 842   gate_copy_prop,                       /* gate */
 843   execute_copy_prop,                    /* execute */
 844   NULL,                                 /* sub */
 845   NULL,                                 /* next */
 846   0,                                    /* static_pass_number */
 847   TV_TREE_COPY_PROP,                    /* tv_id */
 848   PROP_ssa | PROP_cfg,                  /* properties_required */
 849   0,                                    /* properties_provided */
 850   0,                                    /* properties_destroyed */
 851   0,                                    /* todo_flags_start */
 852   TODO_cleanup_cfg
 853     | TODO_dump_func
 854     | TODO_ggc_collect
 855     | TODO_verify_ssa
 856     | TODO_update_ssa                   /* todo_flags_finish */
 857  }
 858 };