gcc/tree-ssa-copy.c

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