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   gcc_checking_assert (!(TREE_CODE (val) == SSA_NAME
 215                          && *op_p
 216                          && TREE_CODE (*op_p) == SSA_NAME
 217                          && !may_propagate_copy (*op_p, val)));
 218
 219   if (TREE_CODE (val) == SSA_NAME)
 220     *op_p = val;
 221   else
 222     *op_p = unsave_expr_now (val);
 223 }
 224
 225
 226 /* Like propagate_tree_value, but use as the operand to replace
 227    the principal expression (typically, the RHS) contained in the
 228    statement referenced by iterator GSI.  Note that it is not
 229    always possible to update the statement in-place, so a new
 230    statement may be created to replace the original.  */
 231
 232 void
 233 propagate_tree_value_into_stmt (gimple_stmt_iterator *gsi, tree val)
 234 {
 235   gimple stmt = gsi_stmt (*gsi);
 236
 237   if (is_gimple_assign (stmt))
 238     {
 239       tree expr = NULL_TREE;
 240       if (gimple_assign_single_p (stmt))
 241         expr = gimple_assign_rhs1 (stmt);
 242       propagate_tree_value (&expr, val);
 243       gimple_assign_set_rhs_from_tree (gsi, expr);
 244       stmt = gsi_stmt (*gsi);
 245     }
 246   else if (gimple_code (stmt) == GIMPLE_COND)
 247     {
 248       tree lhs = NULL_TREE;
 249       tree rhs = build_zero_cst (TREE_TYPE (val));
 250       propagate_tree_value (&lhs, val);
 251       gimple_cond_set_code (stmt, NE_EXPR);
 252       gimple_cond_set_lhs (stmt, lhs);
 253       gimple_cond_set_rhs (stmt, rhs);
 254     }
 255   else if (is_gimple_call (stmt)
 256            && gimple_call_lhs (stmt) != NULL_TREE)
 257     {
 258       gimple new_stmt;
 259
 260       tree expr = NULL_TREE;
 261       propagate_tree_value (&expr, val);
 262       new_stmt = gimple_build_assign (gimple_call_lhs (stmt), expr);
 263       move_ssa_defining_stmt_for_defs (new_stmt, stmt);
 264       gsi_replace (gsi, new_stmt, false);
 265     }
 266   else if (gimple_code (stmt) == GIMPLE_SWITCH)
 267     propagate_tree_value (gimple_switch_index_ptr (stmt), val);
 268   else
 269     gcc_unreachable ();
 270 }
 271
 272 /*---------------------------------------------------------------------------
 273                                 Copy propagation
 274 ---------------------------------------------------------------------------*/
 275 /* Lattice for copy-propagation.  The lattice is initialized to
 276    UNDEFINED (value == NULL) for SSA names that can become a copy
 277    of something or VARYING (value == self) if not (see get_copy_of_val
 278    and stmt_may_generate_copy).  Other values make the name a COPY
 279    of that value.
 280
 281    When visiting a statement or PHI node the lattice value for an
 282    SSA name can transition from UNDEFINED to COPY to VARYING.  */
 283
 284 struct prop_value_d {
 285     /* Copy-of value.  */
 286     tree value;
 287 };
 288 typedef struct prop_value_d prop_value_t;
 289
 290 static prop_value_t *copy_of;
 291
 292
 293 /* Return true if this statement may generate a useful copy.  */
 294
 295 static bool
 296 stmt_may_generate_copy (gimple stmt)
 297 {
 298   if (gimple_code (stmt) == GIMPLE_PHI)
 299     return !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (stmt));
 300
 301   if (gimple_code (stmt) != GIMPLE_ASSIGN)
 302     return false;
 303
 304   /* If the statement has volatile operands, it won't generate a
 305      useful copy.  */
 306   if (gimple_has_volatile_ops (stmt))
 307     return false;
 308
 309   /* Statements with loads and/or stores will never generate a useful copy.  */
 310   if (gimple_vuse (stmt))
 311     return false;
 312
 313   /* Otherwise, the only statements that generate useful copies are
 314      assignments whose RHS is just an SSA name that doesn't flow
 315      through abnormal edges.  */
 316   return (gimple_assign_rhs_code (stmt) == SSA_NAME
 317           && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt)));
 318 }
 319
 320
 321 /* Return the copy-of value for VAR.  */
 322
 323 static inline prop_value_t *
 324 get_copy_of_val (tree var)
 325 {
 326   prop_value_t *val = &copy_of[SSA_NAME_VERSION (var)];
 327
 328   if (val->value == NULL_TREE
 329       && !stmt_may_generate_copy (SSA_NAME_DEF_STMT (var)))
 330     {
 331       /* If the variable will never generate a useful copy relation,
 332          make it its own copy.  */
 333       val->value = var;
 334     }
 335
 336   return val;
 337 }
 338
 339 /* Return the variable VAR is a copy of or VAR if VAR isn't the result
 340    of a copy.  */
 341
 342 static inline tree
 343 valueize_val (tree var)
 344 {
 345   if (TREE_CODE (var) == SSA_NAME)
 346     {
 347       tree val = get_copy_of_val (var)->value;
 348       if (val)
 349         return val;
 350     }
 351   return var;
 352 }
 353
 354 /* Set VAL to be the copy of VAR.  If that changed return true.  */
 355
 356 static inline bool
 357 set_copy_of_val (tree var, tree val)
 358 {
 359   unsigned int ver = SSA_NAME_VERSION (var);
 360   tree old;
 361
 362   /* Set FIRST to be the first link in COPY_OF[DEST].  If that
 363      changed, return true.  */
 364   old = copy_of[ver].value;
 365   copy_of[ver].value = val;
 366
 367   if (old != val
 368       || (val && !operand_equal_p (old, val, 0)))
 369     return true;
 370
 371   return false;
 372 }
 373
 374
 375 /* Dump the copy-of value for variable VAR to FILE.  */
 376
 377 static void
 378 dump_copy_of (FILE *file, tree var)
 379 {
 380   tree val;
 381
 382   print_generic_expr (file, var, dump_flags);
 383   if (TREE_CODE (var) != SSA_NAME)
 384     return;
 385
 386   val = copy_of[SSA_NAME_VERSION (var)].value;
 387   fprintf (file, " copy-of chain: ");
 388   print_generic_expr (file, var, 0);
 389   fprintf (file, " ");
 390   if (!val)
 391     fprintf (file, "[UNDEFINED]");
 392   else if (val == var)
 393     fprintf (file, "[NOT A COPY]");
 394   else
 395     {
 396       fprintf (file, "-> ");
 397       print_generic_expr (file, val, 0);
 398       fprintf (file, " ");
 399       fprintf (file, "[COPY]");
 400     }
 401 }
 402
 403
 404 /* Evaluate the RHS of STMT.  If it produces a valid copy, set the LHS
 405    value and store the LHS into *RESULT_P.  */
 406
 407 static enum ssa_prop_result
 408 copy_prop_visit_assignment (gimple stmt, tree *result_p)
 409 {
 410   tree lhs, rhs;
 411
 412   lhs = gimple_assign_lhs (stmt);
 413   rhs = valueize_val (gimple_assign_rhs1 (stmt));
 414
 415   if (TREE_CODE (lhs) == SSA_NAME)
 416     {
 417       /* Straight copy between two SSA names.  First, make sure that
 418          we can propagate the RHS into uses of LHS.  */
 419       if (!may_propagate_copy (lhs, rhs))
 420         return SSA_PROP_VARYING;
 421
 422       *result_p = lhs;
 423       if (set_copy_of_val (*result_p, rhs))
 424         return SSA_PROP_INTERESTING;
 425       else
 426         return SSA_PROP_NOT_INTERESTING;
 427     }
 428
 429   return SSA_PROP_VARYING;
 430 }
 431
 432
 433 /* Visit the GIMPLE_COND STMT.  Return SSA_PROP_INTERESTING
 434    if it can determine which edge will be taken.  Otherwise, return
 435    SSA_PROP_VARYING.  */
 436
 437 static enum ssa_prop_result
 438 copy_prop_visit_cond_stmt (gimple stmt, edge *taken_edge_p)
 439 {
 440   enum ssa_prop_result retval = SSA_PROP_VARYING;
 441   location_t loc = gimple_location (stmt);
 442
 443   tree op0 = gimple_cond_lhs (stmt);
 444   tree op1 = gimple_cond_rhs (stmt);
 445
 446   /* The only conditionals that we may be able to compute statically
 447      are predicates involving two SSA_NAMEs.  */
 448   if (TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME)
 449     {
 450       op0 = valueize_val (op0);
 451       op1 = valueize_val (op1);
 452
 453       /* See if we can determine the predicate's value.  */
 454       if (dump_file && (dump_flags & TDF_DETAILS))
 455         {
 456           fprintf (dump_file, "Trying to determine truth value of ");
 457           fprintf (dump_file, "predicate ");
 458           print_gimple_stmt (dump_file, stmt, 0, 0);
 459         }
 460
 461       /* We can fold COND and get a useful result only when we have
 462          the same SSA_NAME on both sides of a comparison operator.  */
 463       if (op0 == op1)
 464         {
 465           tree folded_cond = fold_binary_loc (loc, gimple_cond_code (stmt),
 466                                           boolean_type_node, op0, op1);
 467           if (folded_cond)
 468             {
 469               basic_block bb = gimple_bb (stmt);
 470               *taken_edge_p = find_taken_edge (bb, folded_cond);
 471               if (*taken_edge_p)
 472                 retval = SSA_PROP_INTERESTING;
 473             }
 474         }
 475     }
 476
 477   if (dump_file && (dump_flags & TDF_DETAILS) && *taken_edge_p)
 478     fprintf (dump_file, "\nConditional will always take edge %d->%d\n",
 479              (*taken_edge_p)->src->index, (*taken_edge_p)->dest->index);
 480
 481   return retval;
 482 }
 483
 484
 485 /* Evaluate statement STMT.  If the statement produces a new output
 486    value, return SSA_PROP_INTERESTING and store the SSA_NAME holding
 487    the new value in *RESULT_P.
 488
 489    If STMT is a conditional branch and we can determine its truth
 490    value, set *TAKEN_EDGE_P accordingly.
 491
 492    If the new value produced by STMT is varying, return
 493    SSA_PROP_VARYING.  */
 494
 495 static enum ssa_prop_result
 496 copy_prop_visit_stmt (gimple stmt, edge *taken_edge_p, tree *result_p)
 497 {
 498   enum ssa_prop_result retval;
 499
 500   if (dump_file && (dump_flags & TDF_DETAILS))
 501     {
 502       fprintf (dump_file, "\nVisiting statement:\n");
 503       print_gimple_stmt (dump_file, stmt, 0, dump_flags);
 504       fprintf (dump_file, "\n");
 505     }
 506
 507   if (gimple_assign_single_p (stmt)
 508       && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME
 509       && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
 510           || is_gimple_min_invariant (gimple_assign_rhs1 (stmt))))
 511     {
 512       /* If the statement is a copy assignment, evaluate its RHS to
 513          see if the lattice value of its output has changed.  */
 514       retval = copy_prop_visit_assignment (stmt, result_p);
 515     }
 516   else if (gimple_code (stmt) == GIMPLE_COND)
 517     {
 518       /* See if we can determine which edge goes out of a conditional
 519          jump.  */
 520       retval = copy_prop_visit_cond_stmt (stmt, taken_edge_p);
 521     }
 522   else
 523     retval = SSA_PROP_VARYING;
 524
 525   if (retval == SSA_PROP_VARYING)
 526     {
 527       tree def;
 528       ssa_op_iter i;
 529
 530       /* Any other kind of statement is not interesting for constant
 531          propagation and, therefore, not worth simulating.  */
 532       if (dump_file && (dump_flags & TDF_DETAILS))
 533         fprintf (dump_file, "No interesting values produced.\n");
 534
 535       /* The assignment is not a copy operation.  Don't visit this
 536          statement again and mark all the definitions in the statement
 537          to be copies of nothing.  */
 538       FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_ALL_DEFS)
 539         set_copy_of_val (def, def);
 540     }
 541
 542   return retval;
 543 }
 544
 545
 546 /* Visit PHI node PHI.  If all the arguments produce the same value,
 547    set it to be the value of the LHS of PHI.  */
 548
 549 static enum ssa_prop_result
 550 copy_prop_visit_phi_node (gimple phi)
 551 {
 552   enum ssa_prop_result retval;
 553   unsigned i;
 554   prop_value_t phi_val = { NULL_TREE };
 555
 556   tree lhs = gimple_phi_result (phi);
 557
 558   if (dump_file && (dump_flags & TDF_DETAILS))
 559     {
 560       fprintf (dump_file, "\nVisiting PHI node: ");
 561       print_gimple_stmt (dump_file, phi, 0, dump_flags);
 562     }
 563
 564   for (i = 0; i < gimple_phi_num_args (phi); i++)
 565     {
 566       prop_value_t *arg_val;
 567       tree arg = gimple_phi_arg_def (phi, i);
 568       edge e = gimple_phi_arg_edge (phi, i);
 569
 570       /* We don't care about values flowing through non-executable
 571          edges.  */
 572       if (!(e->flags & EDGE_EXECUTABLE))
 573         continue;
 574
 575       /* Constants in the argument list never generate a useful copy.
 576          Similarly, names that flow through abnormal edges cannot be
 577          used to derive copies.  */
 578       if (TREE_CODE (arg) != SSA_NAME || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (arg))
 579         {
 580           phi_val.value = lhs;
 581           break;
 582         }
 583
 584       /* Avoid copy propagation from an inner into an outer loop.
 585          Otherwise, this may move loop variant variables outside of
 586          their loops and prevent coalescing opportunities.  If the
 587          value was loop invariant, it will be hoisted by LICM and
 588          exposed for copy propagation.  Not a problem for virtual
 589          operands though.
 590          ???  The value will be always loop invariant.  */
 591       if (is_gimple_reg (lhs)
 592           && loop_depth_of_name (arg) > loop_depth_of_name (lhs))
 593         {
 594           phi_val.value = lhs;
 595           break;
 596         }
 597
 598       if (dump_file && (dump_flags & TDF_DETAILS))
 599         {
 600           fprintf (dump_file, "\tArgument #%d: ", i);
 601           dump_copy_of (dump_file, arg);
 602           fprintf (dump_file, "\n");
 603         }
 604
 605       arg_val = get_copy_of_val (arg);
 606
 607       /* If we didn't visit the definition of arg yet treat it as
 608          UNDEFINED.  This also handles PHI arguments that are the
 609          same as lhs.  We'll come here again.  */
 610       if (!arg_val->value)
 611         continue;
 612
 613       /* If the LHS didn't have a value yet, make it a copy of the
 614          first argument we find.   */
 615       if (phi_val.value == NULL_TREE)
 616         {
 617           phi_val.value = arg_val->value;
 618           continue;
 619         }
 620
 621       /* If PHI_VAL and ARG don't have a common copy-of chain, then
 622          this PHI node cannot be a copy operation.  */
 623       if (phi_val.value != arg_val->value
 624           && !operand_equal_p (phi_val.value, arg_val->value, 0))
 625         {
 626           phi_val.value = lhs;
 627           break;
 628         }
 629     }
 630
 631   if (phi_val.value
 632       && may_propagate_copy (lhs, phi_val.value)
 633       && set_copy_of_val (lhs, phi_val.value))
 634     retval = (phi_val.value != lhs) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING;
 635   else
 636     retval = SSA_PROP_NOT_INTERESTING;
 637
 638   if (dump_file && (dump_flags & TDF_DETAILS))
 639     {
 640       fprintf (dump_file, "PHI node ");
 641       dump_copy_of (dump_file, lhs);
 642       fprintf (dump_file, "\nTelling the propagator to ");
 643       if (retval == SSA_PROP_INTERESTING)
 644         fprintf (dump_file, "add SSA edges out of this PHI and continue.");
 645       else if (retval == SSA_PROP_VARYING)
 646         fprintf (dump_file, "add SSA edges out of this PHI and never visit again.");
 647       else
 648         fprintf (dump_file, "do nothing with SSA edges and keep iterating.");
 649       fprintf (dump_file, "\n\n");
 650     }
 651
 652   return retval;
 653 }
 654
 655
 656 /* Initialize structures used for copy propagation.  */
 657
 658 static void
 659 init_copy_prop (void)
 660 {
 661   basic_block bb;
 662
 663   copy_of = XCNEWVEC (prop_value_t, num_ssa_names);
 664
 665   FOR_EACH_BB (bb)
 666     {
 667       gimple_stmt_iterator si;
 668       int depth = bb->loop_depth;
 669       bool loop_exit_p = false;
 670
 671       for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
 672         {
 673           gimple stmt = gsi_stmt (si);
 674           ssa_op_iter iter;
 675           tree def;
 676
 677           /* The only statements that we care about are those that may
 678              generate useful copies.  We also need to mark conditional
 679              jumps so that their outgoing edges are added to the work
 680              lists of the propagator.
 681
 682              Avoid copy propagation from an inner into an outer loop.
 683              Otherwise, this may move loop variant variables outside of
 684              their loops and prevent coalescing opportunities.  If the
 685              value was loop invariant, it will be hoisted by LICM and
 686              exposed for copy propagation.
 687              ???  This doesn't make sense.  */
 688           if (stmt_ends_bb_p (stmt))
 689             prop_set_simulate_again (stmt, true);
 690           else if (stmt_may_generate_copy (stmt)
 691                    /* Since we are iterating over the statements in
 692                       BB, not the phi nodes, STMT will always be an
 693                       assignment.  */
 694                    && loop_depth_of_name (gimple_assign_rhs1 (stmt)) <= depth)
 695             prop_set_simulate_again (stmt, true);
 696           else
 697             prop_set_simulate_again (stmt, false);
 698
 699           /* Mark all the outputs of this statement as not being
 700              the copy of anything.  */
 701           FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
 702             if (!prop_simulate_again_p (stmt))
 703               set_copy_of_val (def, def);
 704         }
 705
 706       /* In loop-closed SSA form do not copy-propagate through
 707          PHI nodes in blocks with a loop exit edge predecessor.  */
 708       if (current_loops
 709           && loops_state_satisfies_p (LOOP_CLOSED_SSA))
 710         {
 711           edge_iterator ei;
 712           edge e;
 713           FOR_EACH_EDGE (e, ei, bb->preds)
 714             if (loop_exit_edge_p (e->src->loop_father, e))
 715               loop_exit_p = true;
 716         }
 717
 718       for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
 719         {
 720           gimple phi = gsi_stmt (si);
 721           tree def;
 722
 723           def = gimple_phi_result (phi);
 724           if (!is_gimple_reg (def)
 725               || loop_exit_p)
 726             prop_set_simulate_again (phi, false);
 727           else
 728             prop_set_simulate_again (phi, true);
 729
 730           if (!prop_simulate_again_p (phi))
 731             set_copy_of_val (def, def);
 732         }
 733     }
 734 }
 735
 736 /* Callback for substitute_and_fold to get at the final copy-of values.  */
 737
 738 static tree
 739 get_value (tree name)
 740 {
 741   tree val = copy_of[SSA_NAME_VERSION (name)].value;
 742   if (val && val != name)
 743     return val;
 744   return NULL_TREE;
 745 }
 746
 747 /* Deallocate memory used in copy propagation and do final
 748    substitution.  */
 749
 750 static void
 751 fini_copy_prop (void)
 752 {
 753   unsigned i;
 754
 755   /* Set the final copy-of value for each variable by traversing the
 756      copy-of chains.  */
 757   for (i = 1; i < num_ssa_names; i++)
 758     {
 759       tree var = ssa_name (i);
 760       if (!var
 761           || !copy_of[i].value
 762           || copy_of[i].value == var)
 763         continue;
 764
 765       /* In theory the points-to solution of all members of the
 766          copy chain is their intersection.  For now we do not bother
 767          to compute this but only make sure we do not lose points-to
 768          information completely by setting the points-to solution
 769          of the representative to the first solution we find if
 770          it doesn't have one already.  */
 771       if (copy_of[i].value != var
 772           && POINTER_TYPE_P (TREE_TYPE (var))
 773           && SSA_NAME_PTR_INFO (var)
 774           && !SSA_NAME_PTR_INFO (copy_of[i].value))
 775         duplicate_ssa_name_ptr_info (copy_of[i].value, SSA_NAME_PTR_INFO (var));
 776     }
 777
 778   substitute_and_fold (get_value, NULL, true);
 779
 780   free (copy_of);
 781 }
 782
 783
 784 /* Main entry point to the copy propagator.
 785
 786    PHIS_ONLY is true if we should only consider PHI nodes as generating
 787    copy propagation opportunities.
 788
 789    The algorithm propagates the value COPY-OF using ssa_propagate.  For
 790    every variable X_i, COPY-OF(X_i) indicates which variable is X_i created
 791    from.  The following example shows how the algorithm proceeds at a
 792    high level:
 793
 794             1   a_24 = x_1
 795             2   a_2 = PHI <a_24, x_1>
 796             3   a_5 = PHI <a_2>
 797             4   x_1 = PHI <x_298, a_5, a_2>
 798
 799    The end result should be that a_2, a_5, a_24 and x_1 are a copy of
 800    x_298.  Propagation proceeds as follows.
 801
 802    Visit #1: a_24 is copy-of x_1.  Value changed.
 803    Visit #2: a_2 is copy-of x_1.  Value changed.
 804    Visit #3: a_5 is copy-of x_1.  Value changed.
 805    Visit #4: x_1 is copy-of x_298.  Value changed.
 806    Visit #1: a_24 is copy-of x_298.  Value changed.
 807    Visit #2: a_2 is copy-of x_298.  Value changed.
 808    Visit #3: a_5 is copy-of x_298.  Value changed.
 809    Visit #4: x_1 is copy-of x_298.  Stable state reached.
 810
 811    When visiting PHI nodes, we only consider arguments that flow
 812    through edges marked executable by the propagation engine.  So,
 813    when visiting statement #2 for the first time, we will only look at
 814    the first argument (a_24) and optimistically assume that its value
 815    is the copy of a_24 (x_1).  */
 816
 817 static unsigned int
 818 execute_copy_prop (void)
 819 {
 820   init_copy_prop ();
 821   ssa_propagate (copy_prop_visit_stmt, copy_prop_visit_phi_node);
 822   fini_copy_prop ();
 823   return 0;
 824 }
 825
 826 static bool
 827 gate_copy_prop (void)
 828 {
 829   return flag_tree_copy_prop != 0;
 830 }
 831
 832 struct gimple_opt_pass pass_copy_prop =
 833 {
 834  {
 835   GIMPLE_PASS,
 836   "copyprop",                           /* name */
 837   gate_copy_prop,                       /* gate */
 838   execute_copy_prop,                    /* execute */
 839   NULL,                                 /* sub */
 840   NULL,                                 /* next */
 841   0,                                    /* static_pass_number */
 842   TV_TREE_COPY_PROP,                    /* tv_id */
 843   PROP_ssa | PROP_cfg,                  /* properties_required */
 844   0,                                    /* properties_provided */
 845   0,                                    /* properties_destroyed */
 846   0,                                    /* todo_flags_start */
 847   TODO_cleanup_cfg
 848     | TODO_dump_func
 849     | TODO_ggc_collect
 850     | TODO_verify_ssa
 851     | TODO_update_ssa                   /* todo_flags_finish */
 852  }
 853 };