gcc/tree-ssa-copy.c

   1 /* Copy propagation and SSA_NAME replacement support routines.
   2    Copyright (C) 2004, 2005 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 2, 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 COPYING.  If not, write to
  18 the Free Software Foundation, 59 Temple Place - Suite 330,
  19 Boston, MA 02111-1307, USA.  */
  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 "rtl.h"
  28 #include "tm_p.h"
  29 #include "ggc.h"
  30 #include "basic-block.h"
  31 #include "output.h"
  32 #include "expr.h"
  33 #include "function.h"
  34 #include "diagnostic.h"
  35 #include "timevar.h"
  36 #include "tree-dump.h"
  37 #include "tree-flow.h"
  38 #include "tree-pass.h"
  39 #include "tree-ssa-propagate.h"
  40 #include "langhooks.h"
  41
  42 /* This file implements the copy propagation pass and provides a
  43    handful of interfaces for performing const/copy propagation and
  44    simple expression replacement which keep variable annotations
  45    up-to-date.
  46
  47    We require that for any copy operation where the RHS and LHS have
  48    a non-null memory tag the memory tag be the same.   It is OK
  49    for one or both of the memory tags to be NULL.
  50
  51    We also require tracking if a variable is dereferenced in a load or
  52    store operation.
  53
  54    We enforce these requirements by having all copy propagation and
  55    replacements of one SSA_NAME with a different SSA_NAME to use the
  56    APIs defined in this file.  */
  57
  58 /* Return true if we may propagate ORIG into DEST, false otherwise.  */
  59
  60 bool
  61 may_propagate_copy (tree dest, tree orig)
  62 {
  63   tree type_d = TREE_TYPE (dest);
  64   tree type_o = TREE_TYPE (orig);
  65
  66   /* Do not copy between types for which we *do* need a conversion.  */
  67   if (!tree_ssa_useless_type_conversion_1 (type_d, type_o))
  68     return false;
  69
  70   /* FIXME.  GIMPLE is allowing pointer assignments and comparisons of
  71      pointers that have different alias sets.  This means that these
  72      pointers will have different memory tags associated to them.
  73
  74      If we allow copy propagation in these cases, statements de-referencing
  75      the new pointer will now have a reference to a different memory tag
  76      with potentially incorrect SSA information.
  77
  78      This was showing up in libjava/java/util/zip/ZipFile.java with code
  79      like:
  80
  81         struct java.io.BufferedInputStream *T.660;
  82         struct java.io.BufferedInputStream *T.647;
  83         struct java.io.InputStream *is;
  84         struct java.io.InputStream *is.662;
  85         [ ... ]
  86         T.660 = T.647;
  87         is = T.660;     <-- This ought to be type-casted
  88         is.662 = is;
  89
  90      Also, f/name.c exposed a similar problem with a COND_EXPR predicate
  91      that was causing DOM to generate and equivalence with two pointers of
  92      alias-incompatible types:
  93
  94         struct _ffename_space *n;
  95         struct _ffename *ns;
  96         [ ... ]
  97         if (n == ns)
  98           goto lab;
  99         ...
 100         lab:
 101         return n;
 102
 103      I think that GIMPLE should emit the appropriate type-casts.  For the
 104      time being, blocking copy-propagation in these cases is the safe thing
 105      to do.  */
 106   if (TREE_CODE (dest) == SSA_NAME
 107       && TREE_CODE (orig) == SSA_NAME
 108       && POINTER_TYPE_P (type_d)
 109       && POINTER_TYPE_P (type_o))
 110     {
 111       tree mt_dest = var_ann (SSA_NAME_VAR (dest))->type_mem_tag;
 112       tree mt_orig = var_ann (SSA_NAME_VAR (orig))->type_mem_tag;
 113       if (mt_dest && mt_orig && mt_dest != mt_orig)
 114         return false;
 115       else if (!lang_hooks.types_compatible_p (type_d, type_o))
 116         return false;
 117       else if (get_alias_set (TREE_TYPE (type_d)) !=
 118                get_alias_set (TREE_TYPE (type_o)))
 119         return false;
 120     }
 121
 122   /* If the destination is a SSA_NAME for a virtual operand, then we have
 123      some special cases to handle.  */
 124   if (TREE_CODE (dest) == SSA_NAME && !is_gimple_reg (dest))
 125     {
 126       /* If both operands are SSA_NAMEs referring to virtual operands, then
 127          we can always propagate.  */
 128       if (TREE_CODE (orig) == SSA_NAME
 129           && !is_gimple_reg (orig))
 130         return true;
 131
 132       /* We have a "copy" from something like a constant into a virtual
 133          operand.  Reject these.  */
 134       return false;
 135     }
 136
 137   /* If ORIG flows in from an abnormal edge, it cannot be propagated.  */
 138   if (TREE_CODE (orig) == SSA_NAME
 139       && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig))
 140     return false;
 141
 142   /* If DEST is an SSA_NAME that flows from an abnormal edge, then it
 143      cannot be replaced.  */
 144   if (TREE_CODE (dest) == SSA_NAME
 145       && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (dest))
 146     return false;
 147
 148   /* Anything else is OK.  */
 149   return true;
 150 }
 151
 152 /* Similarly, but we know that we're propagating into an ASM_EXPR.  */
 153
 154 bool
 155 may_propagate_copy_into_asm (tree dest)
 156 {
 157   /* Hard register operands of asms are special.  Do not bypass.  */
 158   return !(TREE_CODE (dest) == SSA_NAME
 159            && TREE_CODE (SSA_NAME_VAR (dest)) == VAR_DECL
 160            && DECL_HARD_REGISTER (SSA_NAME_VAR (dest)));
 161 }
 162
 163
 164 /* Given two SSA_NAMEs pointers ORIG and NEW such that we are copy
 165    propagating NEW into ORIG, consolidate aliasing information so that
 166    they both share the same memory tags.  */
 167
 168 static void
 169 merge_alias_info (tree orig, tree new)
 170 {
 171   tree new_sym = SSA_NAME_VAR (new);
 172   tree orig_sym = SSA_NAME_VAR (orig);
 173   var_ann_t new_ann = var_ann (new_sym);
 174   var_ann_t orig_ann = var_ann (orig_sym);
 175
 176   gcc_assert (POINTER_TYPE_P (TREE_TYPE (orig)));
 177   gcc_assert (POINTER_TYPE_P (TREE_TYPE (new)));
 178
 179 #if defined ENABLE_CHECKING
 180   gcc_assert (lang_hooks.types_compatible_p (TREE_TYPE (orig),
 181                                              TREE_TYPE (new)));
 182
 183   /* If the pointed-to alias sets are different, these two pointers
 184      would never have the same memory tag.  In this case, NEW should
 185      not have been propagated into ORIG.  */
 186   gcc_assert (get_alias_set (TREE_TYPE (TREE_TYPE (new_sym)))
 187               == get_alias_set (TREE_TYPE (TREE_TYPE (orig_sym))));
 188 #endif
 189
 190   /* Synchronize the type tags.  If both pointers had a tag and they
 191      are different, then something has gone wrong.  */
 192   if (new_ann->type_mem_tag == NULL_TREE)
 193     new_ann->type_mem_tag = orig_ann->type_mem_tag;
 194   else if (orig_ann->type_mem_tag == NULL_TREE)
 195     orig_ann->type_mem_tag = new_ann->type_mem_tag;
 196   else
 197     gcc_assert (new_ann->type_mem_tag == orig_ann->type_mem_tag);
 198
 199   /* Synchronize the name tags.  If NEW did not have a name tag, get
 200      it from ORIG.  This happens when NEW is a compiler generated
 201      temporary which still hasn't had its points-to information filled
 202      in.  */
 203   if (SSA_NAME_PTR_INFO (orig))
 204     {
 205       struct ptr_info_def *orig_ptr_info = SSA_NAME_PTR_INFO (orig);
 206       struct ptr_info_def *new_ptr_info = SSA_NAME_PTR_INFO (new);
 207
 208       if (new_ptr_info == NULL)
 209         duplicate_ssa_name_ptr_info (new, orig_ptr_info);
 210       else if (orig_ptr_info->name_mem_tag
 211                && new_ptr_info->name_mem_tag
 212                && orig_ptr_info->pt_vars
 213                && new_ptr_info->pt_vars)
 214         {
 215           /* Note that pointer NEW may actually have a different set
 216              of pointed-to variables.  However, since NEW is being
 217              copy-propagated into ORIG, it must always be true that
 218              the pointed-to set for pointer NEW is the same, or a
 219              subset, of the pointed-to set for pointer ORIG.  If this
 220              isn't the case, we shouldn't have been able to do the
 221              propagation of NEW into ORIG.  */
 222           gcc_assert (bitmap_intersect_p (new_ptr_info->pt_vars,
 223                 orig_ptr_info->pt_vars));
 224         }
 225     }
 226 }
 227
 228
 229 /* Common code for propagate_value and replace_exp.
 230
 231    Replace use operand OP_P with VAL.  FOR_PROPAGATION indicates if the
 232    replacement is done to propagate a value or not.  */
 233
 234 static void
 235 replace_exp_1 (use_operand_p op_p, tree val,
 236                bool for_propagation ATTRIBUTE_UNUSED)
 237 {
 238   tree op = USE_FROM_PTR (op_p);
 239
 240 #if defined ENABLE_CHECKING
 241   gcc_assert (!(for_propagation
 242                 && TREE_CODE (op) == SSA_NAME
 243                 && TREE_CODE (val) == SSA_NAME
 244                 && !may_propagate_copy (op, val)));
 245 #endif
 246
 247   if (TREE_CODE (val) == SSA_NAME)
 248     {
 249       if (TREE_CODE (op) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (op)))
 250         merge_alias_info (op, val);
 251       SET_USE (op_p, val);
 252     }
 253   else
 254     SET_USE (op_p, unsave_expr_now (val));
 255 }
 256
 257
 258 /* Propagate the value VAL (assumed to be a constant or another SSA_NAME)
 259    into the operand pointed by OP_P.
 260
 261    Use this version for const/copy propagation as it will perform additional
 262    checks to ensure validity of the const/copy propagation.  */
 263
 264 void
 265 propagate_value (use_operand_p op_p, tree val)
 266 {
 267   replace_exp_1 (op_p, val, true);
 268 }
 269
 270
 271 /* Propagate the value VAL (assumed to be a constant or another SSA_NAME)
 272    into the tree pointed by OP_P.
 273
 274    Use this version for const/copy propagation when SSA operands are not
 275    available.  It will perform the additional checks to ensure validity of
 276    the const/copy propagation, but will not update any operand information.
 277    Be sure to mark the stmt as modified.  */
 278
 279 void
 280 propagate_tree_value (tree *op_p, tree val)
 281 {
 282 #if defined ENABLE_CHECKING
 283   gcc_assert (!(TREE_CODE (val) == SSA_NAME
 284                 && TREE_CODE (*op_p) == SSA_NAME
 285                 && !may_propagate_copy (*op_p, val)));
 286 #endif
 287
 288   if (TREE_CODE (val) == SSA_NAME)
 289     {
 290       if (TREE_CODE (*op_p) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (*op_p)))
 291         merge_alias_info (*op_p, val);
 292       *op_p = val;
 293     }
 294   else
 295     *op_p = unsave_expr_now (val);
 296 }
 297
 298
 299 /* Replace *OP_P with value VAL (assumed to be a constant or another SSA_NAME).
 300
 301    Use this version when not const/copy propagating values.  For example,
 302    PRE uses this version when building expressions as they would appear
 303    in specific blocks taking into account actions of PHI nodes.  */
 304
 305 void
 306 replace_exp (use_operand_p op_p, tree val)
 307 {
 308   replace_exp_1 (op_p, val, false);
 309 }
 310
 311
 312 /*---------------------------------------------------------------------------
 313                                 Copy propagation
 314 ---------------------------------------------------------------------------*/
 315 /* During propagation, we keep chains of variables that are copies of
 316    one another.  If variable X_i is a copy of X_j and X_j is a copy of
 317    X_k, COPY_OF will contain:
 318
 319         COPY_OF[i].VALUE = X_j
 320         COPY_OF[j].VALUE = X_k
 321         COPY_OF[k].VALUE = X_k
 322
 323    After propagation, the copy-of value for each variable X_i is
 324    converted into the final value by walking the copy-of chains and
 325    updating COPY_OF[i].VALUE to be the last element of the chain.  */
 326 static prop_value_t *copy_of;
 327
 328 /* Used in set_copy_of_val to determine if the last link of a copy-of
 329    chain has changed.  */
 330 static tree *cached_last_copy_of;
 331
 332 /* True if we are doing copy propagation on loads and stores.  */
 333 static bool do_store_copy_prop;
 334
 335
 336 /* Return true if this statement may generate a useful copy.  */
 337
 338 static bool
 339 stmt_may_generate_copy (tree stmt)
 340 {
 341   tree lhs, rhs;
 342   stmt_ann_t ann;
 343
 344   if (TREE_CODE (stmt) == PHI_NODE)
 345     return !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (stmt));
 346
 347   if (TREE_CODE (stmt) != MODIFY_EXPR)
 348     return false;
 349
 350   lhs = TREE_OPERAND (stmt, 0);
 351   rhs = TREE_OPERAND (stmt, 1);
 352   ann = stmt_ann (stmt);
 353
 354   /* If the statement has volatile operands, it won't generate a
 355      useful copy.  */
 356   if (ann->has_volatile_ops)
 357     return false;
 358
 359   /* If we are not doing store copy-prop, statements with loads and/or
 360      stores will never generate a useful copy.  */
 361   if (!do_store_copy_prop
 362       && !ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
 363     return false;
 364
 365   /* Otherwise, the only statements that generate useful copies are
 366      assignments whose RHS is just an SSA name that doesn't flow
 367      through abnormal edges.  */
 368   return TREE_CODE (rhs) == SSA_NAME && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs);
 369 }
 370
 371
 372 /* Return the copy-of value for VAR.  */
 373
 374 static inline prop_value_t *
 375 get_copy_of_val (tree var)
 376 {
 377   prop_value_t *val = &copy_of[SSA_NAME_VERSION (var)];
 378
 379   if (val->value == NULL_TREE
 380       && !stmt_may_generate_copy (SSA_NAME_DEF_STMT (var)))
 381     {
 382       /* If the variable will never generate a useful copy relation,
 383          make it its own copy.  */
 384       val->value = var;
 385       val->mem_ref = NULL_TREE;
 386     }
 387
 388   return val;
 389 }
 390
 391
 392 /* Return last link in the copy-of chain for VAR.  */
 393
 394 static tree
 395 get_last_copy_of (tree var)
 396 {
 397   tree last;
 398   int i;
 399
 400   /* Traverse COPY_OF starting at VAR until we get to the last
 401      link in the chain.  Since it is possible to have cycles in PHI
 402      nodes, the copy-of chain may also contain cycles.
 403
 404      To avoid infinite loops and to avoid traversing lengthy copy-of
 405      chains, we artificially limit the maximum number of chains we are
 406      willing to traverse.
 407
 408      The value 5 was taken from a compiler and runtime library
 409      bootstrap and a mixture of C and C++ code from various sources.
 410      More than 82% of all copy-of chains were shorter than 5 links.  */
 411 #define LIMIT   5
 412
 413   last = var;
 414   for (i = 0; i < LIMIT; i++)
 415     {
 416       tree copy = copy_of[SSA_NAME_VERSION (last)].value;
 417       if (copy == NULL_TREE || copy == last)
 418         break;
 419       last = copy;
 420     }
 421
 422   /* If we have reached the limit, then we are either in a copy-of
 423      cycle or the copy-of chain is too long.  In this case, just
 424      return VAR so that it is not considered a copy of anything.  */
 425   return (i < LIMIT ? last : var);
 426 }
 427
 428
 429 /* Set FIRST to be the first variable in the copy-of chain for DEST.
 430    If DEST's copy-of value or its copy-of chain has changed, return
 431    true.
 432
 433    MEM_REF is the memory reference where FIRST is stored.  This is
 434    used when DEST is a non-register and we are copy propagating loads
 435    and stores.  */
 436
 437 static inline bool
 438 set_copy_of_val (tree dest, tree first, tree mem_ref)
 439 {
 440   unsigned int dest_ver = SSA_NAME_VERSION (dest);
 441   tree old_first, old_last, new_last;
 442
 443   /* Set FIRST to be the first link in COPY_OF[DEST].  If that
 444      changed, return true.  */
 445   old_first = copy_of[dest_ver].value;
 446   copy_of[dest_ver].value = first;
 447   copy_of[dest_ver].mem_ref = mem_ref;
 448
 449   if (old_first != first)
 450     return true;
 451
 452   /* If FIRST and OLD_FIRST are the same, we need to check whether the
 453      copy-of chain starting at FIRST ends in a different variable.  If
 454      the copy-of chain starting at FIRST ends up in a different
 455      variable than the last cached value we had for DEST, then return
 456      true because DEST is now a copy of a different variable.
 457
 458      This test is necessary because even though the first link in the
 459      copy-of chain may not have changed, if any of the variables in
 460      the copy-of chain changed its final value, DEST will now be the
 461      copy of a different variable, so we have to do another round of
 462      propagation for everything that depends on DEST.  */
 463   old_last = cached_last_copy_of[dest_ver];
 464   new_last = get_last_copy_of (dest);
 465   cached_last_copy_of[dest_ver] = new_last;
 466
 467   return (old_last != new_last);
 468 }
 469
 470
 471 /* Dump the copy-of value for variable VAR to DUMP_FILE.  */
 472
 473 static void
 474 dump_copy_of (FILE *dump_file, tree var)
 475 {
 476   tree val;
 477   sbitmap visited;
 478
 479   print_generic_expr (dump_file, var, dump_flags);
 480
 481   if (TREE_CODE (var) != SSA_NAME)
 482     return;
 483
 484   visited = sbitmap_alloc (num_ssa_names);
 485   SET_BIT (visited, SSA_NAME_VERSION (var));
 486
 487   fprintf (dump_file, " copy-of chain: ");
 488
 489   val = var;
 490   print_generic_expr (dump_file, val, 0);
 491   fprintf (dump_file, " ");
 492   while (copy_of[SSA_NAME_VERSION (val)].value)
 493     {
 494       fprintf (dump_file, "-> ");
 495       val = copy_of[SSA_NAME_VERSION (val)].value;
 496       print_generic_expr (dump_file, val, 0);
 497       fprintf (dump_file, " ");
 498       if (TEST_BIT (visited, SSA_NAME_VERSION (val)))
 499         break;
 500       SET_BIT (visited, SSA_NAME_VERSION (val));
 501     }
 502
 503   val = get_copy_of_val (var)->value;
 504   if (val == NULL_TREE)
 505     fprintf (dump_file, "[UNDEFINED]");
 506   else if (val != var)
 507     fprintf (dump_file, "[COPY]");
 508   else
 509     fprintf (dump_file, "[NOT A COPY]");
 510
 511   sbitmap_free (visited);
 512 }
 513
 514
 515 /* Evaluate the RHS of STMT.  If it produces a valid copy, set the LHS
 516    value and store the LHS into *RESULT_P.  If STMT generates more
 517    than one name (i.e., STMT is an aliased store), it is enough to
 518    store the first name in the V_MAY_DEF list into *RESULT_P.  After
 519    all, the names generated will be VUSEd in the same statements.  */
 520
 521 static enum ssa_prop_result
 522 copy_prop_visit_assignment (tree stmt, tree *result_p)
 523 {
 524   tree lhs, rhs;
 525   prop_value_t *rhs_val;
 526
 527   lhs = TREE_OPERAND (stmt, 0);
 528   rhs = TREE_OPERAND (stmt, 1);
 529
 530   gcc_assert (TREE_CODE (rhs) == SSA_NAME);
 531
 532   rhs_val = get_copy_of_val (rhs);
 533
 534   if (TREE_CODE (lhs) == SSA_NAME)
 535     {
 536       /* Straight copy between two SSA names.  First, make sure that
 537          we can propagate the RHS into uses of LHS.  */
 538       if (!may_propagate_copy (lhs, rhs))
 539         return SSA_PROP_VARYING;
 540
 541       /* Avoid copy propagation from an inner into an outer loop.
 542          Otherwise, this may move loop variant variables outside of
 543          their loops and prevent coalescing opportunities.  If the
 544          value was loop invariant, it will be hoisted by LICM and
 545          exposed for copy propagation.  */
 546       if (loop_depth_of_name (rhs) > loop_depth_of_name (lhs))
 547         return SSA_PROP_VARYING;
 548
 549       /* Notice that in the case of assignments, we make the LHS be a
 550          copy of RHS's value, not of RHS itself.  This avoids keeping
 551          unnecessary copy-of chains (assignments cannot be in a cycle
 552          like PHI nodes), speeding up the propagation process.
 553          This is different from what we do in copy_prop_visit_phi_node.
 554          In those cases, we are interested in the copy-of chains.  */
 555       *result_p = lhs;
 556       if (set_copy_of_val (*result_p, rhs_val->value, rhs_val->mem_ref))
 557         return SSA_PROP_INTERESTING;
 558       else
 559         return SSA_PROP_NOT_INTERESTING;
 560     }
 561   else if (stmt_makes_single_store (stmt))
 562     {
 563       /* Otherwise, set the names in V_MAY_DEF/V_MUST_DEF operands
 564          to be a copy of RHS.  */
 565       ssa_op_iter i;
 566       tree vdef;
 567       bool changed;
 568
 569       /* This should only be executed when doing store copy-prop.  */
 570       gcc_assert (do_store_copy_prop);
 571
 572       /* Set the value of every VDEF to RHS_VAL.  */
 573       changed = false;
 574       FOR_EACH_SSA_TREE_OPERAND (vdef, stmt, i, SSA_OP_VIRTUAL_DEFS)
 575         changed |= set_copy_of_val (vdef, rhs_val->value, lhs);
 576
 577       /* Note that for propagation purposes, we are only interested in
 578          visiting statements that load the exact same memory reference
 579          stored here.  Those statements will have the exact same list
 580          of virtual uses, so it is enough to set the output of this
 581          statement to be its first virtual definition.  */
 582       *result_p = first_vdef (stmt);
 583
 584       if (changed)
 585         return SSA_PROP_INTERESTING;
 586       else
 587         return SSA_PROP_NOT_INTERESTING;
 588     }
 589
 590
 591   return SSA_PROP_VARYING;
 592 }
 593
 594
 595 /* Visit the COND_EXPR STMT.  Return SSA_PROP_INTERESTING
 596    if it can determine which edge will be taken.  Otherwise, return
 597    SSA_PROP_VARYING.  */
 598
 599 static enum ssa_prop_result
 600 copy_prop_visit_cond_stmt (tree stmt, edge *taken_edge_p)
 601 {
 602   enum ssa_prop_result retval;
 603   tree cond;
 604
 605   cond = COND_EXPR_COND (stmt);
 606   retval = SSA_PROP_VARYING;
 607
 608   /* The only conditionals that we may be able to compute statically
 609      are predicates involving two SSA_NAMEs.  */
 610   if (COMPARISON_CLASS_P (cond)
 611       && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME
 612       && TREE_CODE (TREE_OPERAND (cond, 1)) == SSA_NAME)
 613     {
 614       tree op0 = get_last_copy_of (TREE_OPERAND (cond, 0));
 615       tree op1 = get_last_copy_of (TREE_OPERAND (cond, 1));
 616
 617       /* See if we can determine the predicate's value.  */
 618       if (dump_file && (dump_flags & TDF_DETAILS))
 619         {
 620           fprintf (dump_file, "Trying to determine truth value of ");
 621           fprintf (dump_file, "predicate ");
 622           print_generic_stmt (dump_file, cond, 0);
 623         }
 624
 625       /* We can fold COND and get a useful result only when we have
 626          the same SSA_NAME on both sides of a comparison operator.  */
 627       if (op0 == op1)
 628         {
 629           tree folded_cond = fold_binary (TREE_CODE (cond), boolean_type_node,
 630                                           op0, op1);
 631           if (folded_cond)
 632             {
 633               basic_block bb = bb_for_stmt (stmt);
 634               *taken_edge_p = find_taken_edge (bb, folded_cond);
 635               if (*taken_edge_p)
 636                 retval = SSA_PROP_INTERESTING;
 637             }
 638         }
 639     }
 640
 641   if (dump_file && (dump_flags & TDF_DETAILS) && *taken_edge_p)
 642     fprintf (dump_file, "\nConditional will always take edge %d->%d\n",
 643              (*taken_edge_p)->src->index, (*taken_edge_p)->dest->index);
 644
 645   return retval;
 646 }
 647
 648
 649 /* Evaluate statement STMT.  If the statement produces a new output
 650    value, return SSA_PROP_INTERESTING and store the SSA_NAME holding
 651    the new value in *RESULT_P.
 652
 653    If STMT is a conditional branch and we can determine its truth
 654    value, set *TAKEN_EDGE_P accordingly.
 655
 656    If the new value produced by STMT is varying, return
 657    SSA_PROP_VARYING.  */
 658
 659 static enum ssa_prop_result
 660 copy_prop_visit_stmt (tree stmt, edge *taken_edge_p, tree *result_p)
 661 {
 662   stmt_ann_t ann;
 663   enum ssa_prop_result retval;
 664
 665   if (dump_file && (dump_flags & TDF_DETAILS))
 666     {
 667       fprintf (dump_file, "\nVisiting statement:\n");
 668       print_generic_stmt (dump_file, stmt, dump_flags);
 669       fprintf (dump_file, "\n");
 670     }
 671
 672   ann = stmt_ann (stmt);
 673
 674   if (TREE_CODE (stmt) == MODIFY_EXPR
 675       && TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME
 676       && (do_store_copy_prop
 677           || TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME))
 678     {
 679       /* If the statement is a copy assignment, evaluate its RHS to
 680          see if the lattice value of its output has changed.  */
 681       retval = copy_prop_visit_assignment (stmt, result_p);
 682     }
 683   else if (TREE_CODE (stmt) == COND_EXPR)
 684     {
 685       /* See if we can determine which edge goes out of a conditional
 686          jump.  */
 687       retval = copy_prop_visit_cond_stmt (stmt, taken_edge_p);
 688     }
 689   else
 690     retval = SSA_PROP_VARYING;
 691
 692   if (retval == SSA_PROP_VARYING)
 693     {
 694       tree def;
 695       ssa_op_iter i;
 696
 697       /* Any other kind of statement is not interesting for constant
 698          propagation and, therefore, not worth simulating.  */
 699       if (dump_file && (dump_flags & TDF_DETAILS))
 700         fprintf (dump_file, "No interesting values produced.\n");
 701
 702       /* The assignment is not a copy operation.  Don't visit this
 703          statement again and mark all the definitions in the statement
 704          to be copies of nothing.  */
 705       FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_ALL_DEFS)
 706         set_copy_of_val (def, def, NULL_TREE);
 707     }
 708
 709   return retval;
 710 }
 711
 712
 713 /* Visit PHI node PHI.  If all the arguments produce the same value,
 714    set it to be the value of the LHS of PHI.  */
 715
 716 static enum ssa_prop_result
 717 copy_prop_visit_phi_node (tree phi)
 718 {
 719   enum ssa_prop_result retval;
 720   int i;
 721   tree lhs;
 722   prop_value_t phi_val = { 0, NULL_TREE, NULL_TREE };
 723
 724   lhs = PHI_RESULT (phi);
 725
 726   if (dump_file && (dump_flags & TDF_DETAILS))
 727     {
 728       fprintf (dump_file, "\nVisiting PHI node: ");
 729       print_generic_expr (dump_file, phi, dump_flags);
 730       fprintf (dump_file, "\n\n");
 731     }
 732
 733   for (i = 0; i < PHI_NUM_ARGS (phi); i++)
 734     {
 735       prop_value_t *arg_val;
 736       tree arg = PHI_ARG_DEF (phi, i);
 737       edge e = PHI_ARG_EDGE (phi, i);
 738
 739       /* We don't care about values flowing through non-executable
 740          edges.  */
 741       if (!(e->flags & EDGE_EXECUTABLE))
 742         continue;
 743
 744       /* Constants in the argument list never generate a useful copy.
 745          Similarly, names that flow through abnormal edges cannot be
 746          used to derive copies.  */
 747       if (TREE_CODE (arg) != SSA_NAME || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (arg))
 748         {
 749           phi_val.value = lhs;
 750           break;
 751         }
 752
 753       /* Avoid copy propagation from an inner into an outer loop.
 754          Otherwise, this may move loop variant variables outside of
 755          their loops and prevent coalescing opportunities.  If the
 756          value was loop invariant, it will be hoisted by LICM and
 757          exposed for copy propagation.  */
 758       if (loop_depth_of_name (arg) > loop_depth_of_name (lhs))
 759         {
 760           phi_val.value = lhs;
 761           break;
 762         }
 763
 764       /* If the LHS appears in the argument list, ignore it.  It is
 765          irrelevant as a copy.  */
 766       if (arg == lhs || get_last_copy_of (arg) == lhs)
 767         continue;
 768
 769       if (dump_file && (dump_flags & TDF_DETAILS))
 770         {
 771           fprintf (dump_file, "\tArgument #%d: ", i);
 772           dump_copy_of (dump_file, arg);
 773           fprintf (dump_file, "\n");
 774         }
 775
 776       arg_val = get_copy_of_val (arg);
 777
 778       /* If the LHS didn't have a value yet, make it a copy of the
 779          first argument we find.  Notice that while we make the LHS be
 780          a copy of the argument itself, we take the memory reference
 781          from the argument's value so that we can compare it to the
 782          memory reference of all the other arguments.  */
 783       if (phi_val.value == NULL_TREE)
 784         {
 785           phi_val.value = arg;
 786           phi_val.mem_ref = arg_val->mem_ref;
 787           continue;
 788         }
 789
 790       /* If PHI_VAL and ARG don't have a common copy-of chain, then
 791          this PHI node cannot be a copy operation.  Also, if we are
 792          copy propagating stores and these two arguments came from
 793          different memory references, they cannot be considered
 794          copies.  */
 795       if (get_last_copy_of (phi_val.value) != get_last_copy_of (arg)
 796           || (do_store_copy_prop
 797               && phi_val.mem_ref
 798               && arg_val->mem_ref
 799               && simple_cst_equal (phi_val.mem_ref, arg_val->mem_ref) != 1))
 800         {
 801           phi_val.value = lhs;
 802           break;
 803         }
 804     }
 805
 806   if (phi_val.value && set_copy_of_val (lhs, phi_val.value, phi_val.mem_ref))
 807     retval = (phi_val.value != lhs) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING;
 808   else
 809     retval = SSA_PROP_NOT_INTERESTING;
 810
 811   if (dump_file && (dump_flags & TDF_DETAILS))
 812     {
 813       fprintf (dump_file, "\nPHI node ");
 814       dump_copy_of (dump_file, lhs);
 815       fprintf (dump_file, "\nTelling the propagator to ");
 816       if (retval == SSA_PROP_INTERESTING)
 817         fprintf (dump_file, "add SSA edges out of this PHI and continue.");
 818       else if (retval == SSA_PROP_VARYING)
 819         fprintf (dump_file, "add SSA edges out of this PHI and never visit again.");
 820       else
 821         fprintf (dump_file, "do nothing with SSA edges and keep iterating.");
 822       fprintf (dump_file, "\n\n");
 823     }
 824
 825   return retval;
 826 }
 827
 828
 829 /* Initialize structures used for copy propagation.  */
 830
 831 static void
 832 init_copy_prop (void)
 833 {
 834   basic_block bb;
 835
 836   copy_of = xmalloc (num_ssa_names * sizeof (*copy_of));
 837   memset (copy_of, 0, num_ssa_names * sizeof (*copy_of));
 838
 839   cached_last_copy_of = xmalloc (num_ssa_names * sizeof (*cached_last_copy_of));
 840   memset (cached_last_copy_of, 0, num_ssa_names * sizeof (*cached_last_copy_of));
 841
 842   FOR_EACH_BB (bb)
 843     {
 844       block_stmt_iterator si;
 845       tree phi;
 846
 847       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
 848         {
 849           tree stmt = bsi_stmt (si);
 850
 851           /* The only statements that we care about are those that may
 852              generate useful copies.  We also need to mark conditional
 853              jumps so that their outgoing edges are added to the work
 854              lists of the propagator.  */
 855           if (stmt_ends_bb_p (stmt))
 856             DONT_SIMULATE_AGAIN (stmt) = false;
 857           else if (stmt_may_generate_copy (stmt))
 858             DONT_SIMULATE_AGAIN (stmt) = false;
 859           else
 860             {
 861               tree def;
 862               ssa_op_iter iter;
 863
 864               /* No need to simulate this statement anymore.  */
 865               DONT_SIMULATE_AGAIN (stmt) = true;
 866
 867               /* Mark all the outputs of this statement as not being
 868                  the copy of anything.  */
 869               FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
 870                 set_copy_of_val (def, def, NULL_TREE);
 871             }
 872         }
 873
 874       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 875         DONT_SIMULATE_AGAIN (phi) = false;
 876     }
 877 }
 878
 879
 880 /* Deallocate memory used in copy propagation and do final
 881    substitution.  */
 882
 883 static void
 884 fini_copy_prop (void)
 885 {
 886   size_t i;
 887
 888   /* Set the final copy-of value for each variable by traversing the
 889      copy-of chains.  */
 890   for (i = 1; i < num_ssa_names; i++)
 891     {
 892       tree var = ssa_name (i);
 893       if (var && copy_of[i].value && copy_of[i].value != var)
 894         copy_of[i].value = get_last_copy_of (var);
 895     }
 896
 897   substitute_and_fold (copy_of);
 898
 899   free (cached_last_copy_of);
 900   free (copy_of);
 901 }
 902
 903
 904 /* Main entry point to the copy propagator.  The algorithm propagates
 905    the value COPY-OF using ssa_propagate.  For every variable X_i,
 906    COPY-OF(X_i) indicates which variable is X_i created from.  The
 907    following example shows how the algorithm proceeds at a high level:
 908
 909             1   a_24 = x_1
 910             2   a_2 = PHI <a_24, x_1>
 911             3   a_5 = PHI <a_2>
 912             4   x_1 = PHI <x_298, a_5, a_2>
 913
 914    The end result should be that a_2, a_5, a_24 and x_1 are a copy of
 915    x_298.  Propagation proceeds as follows.
 916
 917    Visit #1: a_24 is copy-of x_1.  Value changed.
 918    Visit #2: a_2 is copy-of x_1.  Value changed.
 919    Visit #3: a_5 is copy-of x_1.  Value changed.
 920    Visit #4: x_1 is copy-of x_298.  Value changed.
 921    Visit #1: a_24 is copy-of x_298.  Value changed.
 922    Visit #2: a_2 is copy-of x_298.  Value changed.
 923    Visit #3: a_5 is copy-of x_298.  Value changed.
 924    Visit #4: x_1 is copy-of x_298.  Stable state reached.
 925
 926    When visiting PHI nodes, we only consider arguments that flow
 927    through edges marked executable by the propagation engine.  So,
 928    when visiting statement #2 for the first time, we will only look at
 929    the first argument (a_24) and optimistically assume that its value
 930    is the copy of a_24 (x_1).
 931
 932    The problem with this approach is that it may fail to discover copy
 933    relations in PHI cycles.  Instead of propagating copy-of
 934    values, we actually propagate copy-of chains.  For instance:
 935
 936                 A_3 = B_1;
 937                 C_9 = A_3;
 938                 D_4 = C_9;
 939                 X_i = D_4;
 940
 941    In this code fragment, COPY-OF (X_i) = { D_4, C_9, A_3, B_1 }.
 942    Obviously, we are only really interested in the last value of the
 943    chain, however the propagator needs to access the copy-of chain
 944    when visiting PHI nodes.
 945
 946    To represent the copy-of chain, we use the array COPY_CHAINS, which
 947    holds the first link in the copy-of chain for every variable.
 948    If variable X_i is a copy of X_j, which in turn is a copy of X_k,
 949    the array will contain:
 950
 951                 COPY_CHAINS[i] = X_j
 952                 COPY_CHAINS[j] = X_k
 953                 COPY_CHAINS[k] = X_k
 954
 955    Keeping copy-of chains instead of copy-of values directly becomes
 956    important when visiting PHI nodes.  Suppose that we had the
 957    following PHI cycle, such that x_52 is already considered a copy of
 958    x_53:
 959
 960             1   x_54 = PHI <x_53, x_52>
 961             2   x_53 = PHI <x_898, x_54>
 962
 963    Visit #1: x_54 is copy-of x_53 (because x_52 is copy-of x_53)
 964    Visit #2: x_53 is copy-of x_898 (because x_54 is a copy of x_53,
 965                                     so it is considered irrelevant
 966                                     as a copy).
 967    Visit #1: x_54 is copy-of nothing (x_53 is a copy-of x_898 and
 968                                       x_52 is a copy of x_53, so
 969                                       they don't match)
 970    Visit #2: x_53 is copy-of nothing
 971
 972    This problem is avoided by keeping a chain of copies, instead of
 973    the final copy-of value.  Propagation will now only keep the first
 974    element of a variable's copy-of chain.  When visiting PHI nodes,
 975    arguments are considered equal if their copy-of chains end in the
 976    same variable.  So, as long as their copy-of chains overlap, we
 977    know that they will be a copy of the same variable, regardless of
 978    which variable that may be).
 979
 980    Propagation would then proceed as follows (the notation a -> b
 981    means that a is a copy-of b):
 982
 983    Visit #1: x_54 = PHI <x_53, x_52>
 984                 x_53 -> x_53
 985                 x_52 -> x_53
 986                 Result: x_54 -> x_53.  Value changed.  Add SSA edges.
 987
 988    Visit #1: x_53 = PHI <x_898, x_54>
 989                 x_898 -> x_898
 990                 x_54 -> x_53
 991                 Result: x_53 -> x_898.  Value changed.  Add SSA edges.
 992
 993    Visit #2: x_54 = PHI <x_53, x_52>
 994                 x_53 -> x_898
 995                 x_52 -> x_53 -> x_898
 996                 Result: x_54 -> x_898.  Value changed.  Add SSA edges.
 997
 998    Visit #2: x_53 = PHI <x_898, x_54>
 999                 x_898 -> x_898
1000                 x_54 -> x_898
1001                 Result: x_53 -> x_898.  Value didn't change.  Stable state
1002
1003    Once the propagator stabilizes, we end up with the desired result
1004    x_53 and x_54 are both copies of x_898.  */
1005
1006 static void
1007 execute_copy_prop (bool store_copy_prop)
1008 {
1009   do_store_copy_prop = store_copy_prop;
1010   init_copy_prop ();
1011   ssa_propagate (copy_prop_visit_stmt, copy_prop_visit_phi_node);
1012   fini_copy_prop ();
1013 }
1014
1015
1016 static bool
1017 gate_copy_prop (void)
1018 {
1019   return flag_tree_copy_prop != 0;
1020 }
1021
1022 static void
1023 do_copy_prop (void)
1024 {
1025   execute_copy_prop (false);
1026 }
1027
1028 struct tree_opt_pass pass_copy_prop =
1029 {
1030   "copyprop",                           /* name */
1031   gate_copy_prop,                       /* gate */
1032   do_copy_prop,                         /* execute */
1033   NULL,                                 /* sub */
1034   NULL,                                 /* next */
1035   0,                                    /* static_pass_number */
1036   TV_TREE_COPY_PROP,                    /* tv_id */
1037   PROP_ssa | PROP_alias | PROP_cfg,     /* properties_required */
1038   0,                                    /* properties_provided */
1039   0,                                    /* properties_destroyed */
1040   0,                                    /* todo_flags_start */
1041   TODO_cleanup_cfg
1042     | TODO_dump_func
1043     | TODO_ggc_collect
1044     | TODO_verify_ssa
1045     | TODO_update_ssa,                  /* todo_flags_finish */
1046   0                                     /* letter */
1047 };
1048
1049
1050 static bool
1051 gate_store_copy_prop (void)
1052 {
1053   /* STORE-COPY-PROP is enabled only with -ftree-store-copy-prop, but
1054      when -fno-tree-store-copy-prop is specified, we should run
1055      regular COPY-PROP. That's why the pass is enabled with either
1056      flag.  */
1057   return flag_tree_store_copy_prop != 0 || flag_tree_copy_prop != 0;
1058 }
1059
1060 static void
1061 store_copy_prop (void)
1062 {
1063   /* If STORE-COPY-PROP is not enabled, we just run regular COPY-PROP.  */
1064   execute_copy_prop (flag_tree_store_copy_prop != 0);
1065 }
1066
1067 struct tree_opt_pass pass_store_copy_prop =
1068 {
1069   "store_copyprop",                     /* name */
1070   gate_store_copy_prop,                 /* gate */
1071   store_copy_prop,                      /* execute */
1072   NULL,                                 /* sub */
1073   NULL,                                 /* next */
1074   0,                                    /* static_pass_number */
1075   TV_TREE_STORE_COPY_PROP,              /* tv_id */
1076   PROP_ssa | PROP_alias | PROP_cfg,     /* properties_required */
1077   0,                                    /* properties_provided */
1078   0,                                    /* properties_destroyed */
1079   0,                                    /* todo_flags_start */
1080   TODO_dump_func
1081     | TODO_cleanup_cfg
1082     | TODO_ggc_collect
1083     | TODO_verify_ssa
1084     | TODO_update_ssa,                  /* todo_flags_finish */
1085   0                                     /* letter */
1086 };