gcc/tree-ssa-copy.c

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