gcc/tree-ssa-copy.c

   1 /* Copy propagation and SSA_NAME replacement support routines.
   2    Copyright (C) 2004-2016 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 "backend.h"
  24 #include "tree.h"
  25 #include "gimple.h"
  26 #include "tree-pass.h"
  27 #include "ssa.h"
  28 #include "gimple-pretty-print.h"
  29 #include "fold-const.h"
  30 #include "gimple-iterator.h"
  31 #include "tree-cfg.h"
  32 #include "tree-ssa-propagate.h"
  33 #include "cfgloop.h"
  34 #include "tree-scalar-evolution.h"
  35 #include "tree-ssa-loop-niter.h"
  36
  37
  38 /* This file implements the copy propagation pass and provides a
  39    handful of interfaces for performing const/copy propagation and
  40    simple expression replacement which keep variable annotations
  41    up-to-date.
  42
  43    We require that for any copy operation where the RHS and LHS have
  44    a non-null memory tag the memory tag be the same.   It is OK
  45    for one or both of the memory tags to be NULL.
  46
  47    We also require tracking if a variable is dereferenced in a load or
  48    store operation.
  49
  50    We enforce these requirements by having all copy propagation and
  51    replacements of one SSA_NAME with a different SSA_NAME to use the
  52    APIs defined in this file.  */
  53
  54 /*---------------------------------------------------------------------------
  55                                 Copy propagation
  56 ---------------------------------------------------------------------------*/
  57 /* Lattice for copy-propagation.  The lattice is initialized to
  58    UNDEFINED (value == NULL) for SSA names that can become a copy
  59    of something or VARYING (value == self) if not (see get_copy_of_val
  60    and stmt_may_generate_copy).  Other values make the name a COPY
  61    of that value.
  62
  63    When visiting a statement or PHI node the lattice value for an
  64    SSA name can transition from UNDEFINED to COPY to VARYING.  */
  65
  66 struct prop_value_t {
  67     /* Copy-of value.  */
  68     tree value;
  69 };
  70
  71 static prop_value_t *copy_of;
  72 static unsigned n_copy_of;
  73
  74
  75 /* Return true if this statement may generate a useful copy.  */
  76
  77 static bool
  78 stmt_may_generate_copy (gimple *stmt)
  79 {
  80   if (gimple_code (stmt) == GIMPLE_PHI)
  81     return !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (stmt));
  82
  83   if (gimple_code (stmt) != GIMPLE_ASSIGN)
  84     return false;
  85
  86   /* If the statement has volatile operands, it won't generate a
  87      useful copy.  */
  88   if (gimple_has_volatile_ops (stmt))
  89     return false;
  90
  91   /* Statements with loads and/or stores will never generate a useful copy.  */
  92   if (gimple_vuse (stmt))
  93     return false;
  94
  95   /* Otherwise, the only statements that generate useful copies are
  96      assignments whose RHS is just an SSA name that doesn't flow
  97      through abnormal edges.  */
  98   return ((gimple_assign_rhs_code (stmt) == SSA_NAME
  99            && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt)))
 100           || is_gimple_min_invariant (gimple_assign_rhs1 (stmt)));
 101 }
 102
 103
 104 /* Return the copy-of value for VAR.  */
 105
 106 static inline prop_value_t *
 107 get_copy_of_val (tree var)
 108 {
 109   prop_value_t *val = &copy_of[SSA_NAME_VERSION (var)];
 110
 111   if (val->value == NULL_TREE
 112       && !stmt_may_generate_copy (SSA_NAME_DEF_STMT (var)))
 113     {
 114       /* If the variable will never generate a useful copy relation,
 115          make it its own copy.  */
 116       val->value = var;
 117     }
 118
 119   return val;
 120 }
 121
 122 /* Return the variable VAR is a copy of or VAR if VAR isn't the result
 123    of a copy.  */
 124
 125 static inline tree
 126 valueize_val (tree var)
 127 {
 128   if (TREE_CODE (var) == SSA_NAME)
 129     {
 130       tree val = get_copy_of_val (var)->value;
 131       if (val)
 132         return val;
 133     }
 134   return var;
 135 }
 136
 137 /* Set VAL to be the copy of VAR.  If that changed return true.  */
 138
 139 static inline bool
 140 set_copy_of_val (tree var, tree val)
 141 {
 142   unsigned int ver = SSA_NAME_VERSION (var);
 143   tree old;
 144
 145   /* Set FIRST to be the first link in COPY_OF[DEST].  If that
 146      changed, return true.  */
 147   old = copy_of[ver].value;
 148   copy_of[ver].value = val;
 149
 150   if (old != val
 151       || (val && !operand_equal_p (old, val, 0)))
 152     return true;
 153
 154   return false;
 155 }
 156
 157
 158 /* Dump the copy-of value for variable VAR to FILE.  */
 159
 160 static void
 161 dump_copy_of (FILE *file, tree var)
 162 {
 163   tree val;
 164
 165   print_generic_expr (file, var, dump_flags);
 166   if (TREE_CODE (var) != SSA_NAME)
 167     return;
 168
 169   val = copy_of[SSA_NAME_VERSION (var)].value;
 170   fprintf (file, " copy-of chain: ");
 171   print_generic_expr (file, var, 0);
 172   fprintf (file, " ");
 173   if (!val)
 174     fprintf (file, "[UNDEFINED]");
 175   else if (val == var)
 176     fprintf (file, "[NOT A COPY]");
 177   else
 178     {
 179       fprintf (file, "-> ");
 180       print_generic_expr (file, val, 0);
 181       fprintf (file, " ");
 182       fprintf (file, "[COPY]");
 183     }
 184 }
 185
 186
 187 /* Evaluate the RHS of STMT.  If it produces a valid copy, set the LHS
 188    value and store the LHS into *RESULT_P.  */
 189
 190 static enum ssa_prop_result
 191 copy_prop_visit_assignment (gimple *stmt, tree *result_p)
 192 {
 193   tree lhs, rhs;
 194
 195   lhs = gimple_assign_lhs (stmt);
 196   rhs = valueize_val (gimple_assign_rhs1 (stmt));
 197
 198   if (TREE_CODE (lhs) == SSA_NAME)
 199     {
 200       /* Straight copy between two SSA names.  First, make sure that
 201          we can propagate the RHS into uses of LHS.  */
 202       if (!may_propagate_copy (lhs, rhs))
 203         return SSA_PROP_VARYING;
 204
 205       *result_p = lhs;
 206       if (set_copy_of_val (*result_p, rhs))
 207         return SSA_PROP_INTERESTING;
 208       else
 209         return SSA_PROP_NOT_INTERESTING;
 210     }
 211
 212   return SSA_PROP_VARYING;
 213 }
 214
 215
 216 /* Visit the GIMPLE_COND STMT.  Return SSA_PROP_INTERESTING
 217    if it can determine which edge will be taken.  Otherwise, return
 218    SSA_PROP_VARYING.  */
 219
 220 static enum ssa_prop_result
 221 copy_prop_visit_cond_stmt (gimple *stmt, edge *taken_edge_p)
 222 {
 223   enum ssa_prop_result retval = SSA_PROP_VARYING;
 224   location_t loc = gimple_location (stmt);
 225
 226   tree op0 = valueize_val (gimple_cond_lhs (stmt));
 227   tree op1 = valueize_val (gimple_cond_rhs (stmt));
 228
 229   /* See if we can determine the predicate's value.  */
 230   if (dump_file && (dump_flags & TDF_DETAILS))
 231     {
 232       fprintf (dump_file, "Trying to determine truth value of ");
 233       fprintf (dump_file, "predicate ");
 234       print_gimple_stmt (dump_file, stmt, 0, 0);
 235     }
 236
 237   /* Fold COND and see whether we get a useful result.  */
 238   tree folded_cond = fold_binary_loc (loc, gimple_cond_code (stmt),
 239                                       boolean_type_node, op0, op1);
 240   if (folded_cond)
 241     {
 242       basic_block bb = gimple_bb (stmt);
 243       *taken_edge_p = find_taken_edge (bb, folded_cond);
 244       if (*taken_edge_p)
 245         retval = SSA_PROP_INTERESTING;
 246     }
 247
 248   if (dump_file && (dump_flags & TDF_DETAILS) && *taken_edge_p)
 249     fprintf (dump_file, "\nConditional will always take edge %d->%d\n",
 250              (*taken_edge_p)->src->index, (*taken_edge_p)->dest->index);
 251
 252   return retval;
 253 }
 254
 255
 256 /* Evaluate statement STMT.  If the statement produces a new output
 257    value, return SSA_PROP_INTERESTING and store the SSA_NAME holding
 258    the new value in *RESULT_P.
 259
 260    If STMT is a conditional branch and we can determine its truth
 261    value, set *TAKEN_EDGE_P accordingly.
 262
 263    If the new value produced by STMT is varying, return
 264    SSA_PROP_VARYING.  */
 265
 266 static enum ssa_prop_result
 267 copy_prop_visit_stmt (gimple *stmt, edge *taken_edge_p, tree *result_p)
 268 {
 269   enum ssa_prop_result retval;
 270
 271   if (dump_file && (dump_flags & TDF_DETAILS))
 272     {
 273       fprintf (dump_file, "\nVisiting statement:\n");
 274       print_gimple_stmt (dump_file, stmt, 0, dump_flags);
 275       fprintf (dump_file, "\n");
 276     }
 277
 278   if (gimple_assign_single_p (stmt)
 279       && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME
 280       && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
 281           || is_gimple_min_invariant (gimple_assign_rhs1 (stmt))))
 282     {
 283       /* If the statement is a copy assignment, evaluate its RHS to
 284          see if the lattice value of its output has changed.  */
 285       retval = copy_prop_visit_assignment (stmt, result_p);
 286     }
 287   else if (gimple_code (stmt) == GIMPLE_COND)
 288     {
 289       /* See if we can determine which edge goes out of a conditional
 290          jump.  */
 291       retval = copy_prop_visit_cond_stmt (stmt, taken_edge_p);
 292     }
 293   else
 294     retval = SSA_PROP_VARYING;
 295
 296   if (retval == SSA_PROP_VARYING)
 297     {
 298       tree def;
 299       ssa_op_iter i;
 300
 301       /* Any other kind of statement is not interesting for constant
 302          propagation and, therefore, not worth simulating.  */
 303       if (dump_file && (dump_flags & TDF_DETAILS))
 304         fprintf (dump_file, "No interesting values produced.\n");
 305
 306       /* The assignment is not a copy operation.  Don't visit this
 307          statement again and mark all the definitions in the statement
 308          to be copies of nothing.  */
 309       FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_ALL_DEFS)
 310         set_copy_of_val (def, def);
 311     }
 312
 313   return retval;
 314 }
 315
 316
 317 /* Visit PHI node PHI.  If all the arguments produce the same value,
 318    set it to be the value of the LHS of PHI.  */
 319
 320 static enum ssa_prop_result
 321 copy_prop_visit_phi_node (gphi *phi)
 322 {
 323   enum ssa_prop_result retval;
 324   unsigned i;
 325   prop_value_t phi_val = { NULL_TREE };
 326
 327   tree lhs = gimple_phi_result (phi);
 328
 329   if (dump_file && (dump_flags & TDF_DETAILS))
 330     {
 331       fprintf (dump_file, "\nVisiting PHI node: ");
 332       print_gimple_stmt (dump_file, phi, 0, dump_flags);
 333     }
 334
 335   for (i = 0; i < gimple_phi_num_args (phi); i++)
 336     {
 337       prop_value_t *arg_val;
 338       tree arg_value;
 339       tree arg = gimple_phi_arg_def (phi, i);
 340       edge e = gimple_phi_arg_edge (phi, i);
 341
 342       /* We don't care about values flowing through non-executable
 343          edges.  */
 344       if (!(e->flags & EDGE_EXECUTABLE))
 345         continue;
 346
 347       /* Names that flow through abnormal edges cannot be used to
 348          derive copies.  */
 349       if (TREE_CODE (arg) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (arg))
 350         {
 351           phi_val.value = lhs;
 352           break;
 353         }
 354
 355       if (dump_file && (dump_flags & TDF_DETAILS))
 356         {
 357           fprintf (dump_file, "\tArgument #%d: ", i);
 358           dump_copy_of (dump_file, arg);
 359           fprintf (dump_file, "\n");
 360         }
 361
 362       if (TREE_CODE (arg) == SSA_NAME)
 363         {
 364           arg_val = get_copy_of_val (arg);
 365
 366           /* If we didn't visit the definition of arg yet treat it as
 367              UNDEFINED.  This also handles PHI arguments that are the
 368              same as lhs.  We'll come here again.  */
 369           if (!arg_val->value)
 370             continue;
 371
 372           arg_value = arg_val->value;
 373         }
 374       else
 375         arg_value = valueize_val (arg);
 376
 377       /* In loop-closed SSA form do not copy-propagate SSA-names across
 378          loop exit edges.  */
 379       if (loops_state_satisfies_p (LOOP_CLOSED_SSA)
 380           && TREE_CODE (arg_value) == SSA_NAME
 381           && loop_exit_edge_p (e->src->loop_father, e))
 382         {
 383           phi_val.value = lhs;
 384           break;
 385         }
 386
 387       /* If the LHS didn't have a value yet, make it a copy of the
 388          first argument we find.   */
 389       if (phi_val.value == NULL_TREE)
 390         {
 391           phi_val.value = arg_value;
 392           continue;
 393         }
 394
 395       /* If PHI_VAL and ARG don't have a common copy-of chain, then
 396          this PHI node cannot be a copy operation.  */
 397       if (phi_val.value != arg_value
 398           && !operand_equal_p (phi_val.value, arg_value, 0))
 399         {
 400           phi_val.value = lhs;
 401           break;
 402         }
 403     }
 404
 405   if (phi_val.value
 406       && may_propagate_copy (lhs, phi_val.value)
 407       && set_copy_of_val (lhs, phi_val.value))
 408     retval = (phi_val.value != lhs) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING;
 409   else
 410     retval = SSA_PROP_NOT_INTERESTING;
 411
 412   if (dump_file && (dump_flags & TDF_DETAILS))
 413     {
 414       fprintf (dump_file, "PHI node ");
 415       dump_copy_of (dump_file, lhs);
 416       fprintf (dump_file, "\nTelling the propagator to ");
 417       if (retval == SSA_PROP_INTERESTING)
 418         fprintf (dump_file, "add SSA edges out of this PHI and continue.");
 419       else if (retval == SSA_PROP_VARYING)
 420         fprintf (dump_file, "add SSA edges out of this PHI and never visit again.");
 421       else
 422         fprintf (dump_file, "do nothing with SSA edges and keep iterating.");
 423       fprintf (dump_file, "\n\n");
 424     }
 425
 426   return retval;
 427 }
 428
 429
 430 /* Initialize structures used for copy propagation.  */
 431
 432 static void
 433 init_copy_prop (void)
 434 {
 435   basic_block bb;
 436
 437   n_copy_of = num_ssa_names;
 438   copy_of = XCNEWVEC (prop_value_t, n_copy_of);
 439
 440   FOR_EACH_BB_FN (bb, cfun)
 441     {
 442       for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si);
 443            gsi_next (&si))
 444         {
 445           gimple *stmt = gsi_stmt (si);
 446           ssa_op_iter iter;
 447           tree def;
 448
 449           /* The only statements that we care about are those that may
 450              generate useful copies.  We also need to mark conditional
 451              jumps so that their outgoing edges are added to the work
 452              lists of the propagator.  */
 453           if (stmt_ends_bb_p (stmt))
 454             prop_set_simulate_again (stmt, true);
 455           else if (stmt_may_generate_copy (stmt))
 456             prop_set_simulate_again (stmt, true);
 457           else
 458             prop_set_simulate_again (stmt, false);
 459
 460           /* Mark all the outputs of this statement as not being
 461              the copy of anything.  */
 462           FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
 463             if (!prop_simulate_again_p (stmt))
 464               set_copy_of_val (def, def);
 465         }
 466
 467       for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);
 468            gsi_next (&si))
 469         {
 470           gphi *phi = si.phi ();
 471           tree def;
 472
 473           def = gimple_phi_result (phi);
 474           if (virtual_operand_p (def))
 475             prop_set_simulate_again (phi, false);
 476           else
 477             prop_set_simulate_again (phi, true);
 478
 479           if (!prop_simulate_again_p (phi))
 480             set_copy_of_val (def, def);
 481         }
 482     }
 483 }
 484
 485 /* Callback for substitute_and_fold to get at the final copy-of values.  */
 486
 487 static tree
 488 get_value (tree name)
 489 {
 490   tree val;
 491   if (SSA_NAME_VERSION (name) >= n_copy_of)
 492     return NULL_TREE;
 493   val = copy_of[SSA_NAME_VERSION (name)].value;
 494   if (val && val != name)
 495     return val;
 496   return NULL_TREE;
 497 }
 498
 499 /* Deallocate memory used in copy propagation and do final
 500    substitution.  */
 501
 502 static bool
 503 fini_copy_prop (void)
 504 {
 505   unsigned i;
 506
 507   /* Set the final copy-of value for each variable by traversing the
 508      copy-of chains.  */
 509   for (i = 1; i < num_ssa_names; i++)
 510     {
 511       tree var = ssa_name (i);
 512       if (!var
 513           || !copy_of[i].value
 514           || copy_of[i].value == var)
 515         continue;
 516
 517       /* In theory the points-to solution of all members of the
 518          copy chain is their intersection.  For now we do not bother
 519          to compute this but only make sure we do not lose points-to
 520          information completely by setting the points-to solution
 521          of the representative to the first solution we find if
 522          it doesn't have one already.  */
 523       if (copy_of[i].value != var
 524           && TREE_CODE (copy_of[i].value) == SSA_NAME)
 525         {
 526           basic_block copy_of_bb
 527             = gimple_bb (SSA_NAME_DEF_STMT (copy_of[i].value));
 528           basic_block var_bb = gimple_bb (SSA_NAME_DEF_STMT (var));
 529           if (POINTER_TYPE_P (TREE_TYPE (var))
 530               && SSA_NAME_PTR_INFO (var)
 531               && !SSA_NAME_PTR_INFO (copy_of[i].value))
 532             {
 533               duplicate_ssa_name_ptr_info (copy_of[i].value,
 534                                            SSA_NAME_PTR_INFO (var));
 535               /* Points-to information is cfg insensitive,
 536                  but alignment info might be cfg sensitive, if it
 537                  e.g. is derived from VRP derived non-zero bits.
 538                  So, do not copy alignment info if the two SSA_NAMEs
 539                  aren't defined in the same basic block.  */
 540               if (var_bb != copy_of_bb)
 541                 mark_ptr_info_alignment_unknown
 542                                 (SSA_NAME_PTR_INFO (copy_of[i].value));
 543             }
 544           else if (!POINTER_TYPE_P (TREE_TYPE (var))
 545                    && SSA_NAME_RANGE_INFO (var)
 546                    && !SSA_NAME_RANGE_INFO (copy_of[i].value)
 547                    && var_bb == copy_of_bb)
 548             duplicate_ssa_name_range_info (copy_of[i].value,
 549                                            SSA_NAME_RANGE_TYPE (var),
 550                                            SSA_NAME_RANGE_INFO (var));
 551         }
 552     }
 553
 554   bool changed = substitute_and_fold (get_value, NULL, true);
 555   if (changed)
 556     {
 557       free_numbers_of_iterations_estimates (cfun);
 558       if (scev_initialized_p ())
 559         scev_reset ();
 560     }
 561
 562   free (copy_of);
 563
 564   return changed;
 565 }
 566
 567
 568 /* Main entry point to the copy propagator.
 569
 570    PHIS_ONLY is true if we should only consider PHI nodes as generating
 571    copy propagation opportunities.
 572
 573    The algorithm propagates the value COPY-OF using ssa_propagate.  For
 574    every variable X_i, COPY-OF(X_i) indicates which variable is X_i created
 575    from.  The following example shows how the algorithm proceeds at a
 576    high level:
 577
 578             1   a_24 = x_1
 579             2   a_2 = PHI <a_24, x_1>
 580             3   a_5 = PHI <a_2>
 581             4   x_1 = PHI <x_298, a_5, a_2>
 582
 583    The end result should be that a_2, a_5, a_24 and x_1 are a copy of
 584    x_298.  Propagation proceeds as follows.
 585
 586    Visit #1: a_24 is copy-of x_1.  Value changed.
 587    Visit #2: a_2 is copy-of x_1.  Value changed.
 588    Visit #3: a_5 is copy-of x_1.  Value changed.
 589    Visit #4: x_1 is copy-of x_298.  Value changed.
 590    Visit #1: a_24 is copy-of x_298.  Value changed.
 591    Visit #2: a_2 is copy-of x_298.  Value changed.
 592    Visit #3: a_5 is copy-of x_298.  Value changed.
 593    Visit #4: x_1 is copy-of x_298.  Stable state reached.
 594
 595    When visiting PHI nodes, we only consider arguments that flow
 596    through edges marked executable by the propagation engine.  So,
 597    when visiting statement #2 for the first time, we will only look at
 598    the first argument (a_24) and optimistically assume that its value
 599    is the copy of a_24 (x_1).  */
 600
 601 static unsigned int
 602 execute_copy_prop (void)
 603 {
 604   init_copy_prop ();
 605   ssa_propagate (copy_prop_visit_stmt, copy_prop_visit_phi_node);
 606   if (fini_copy_prop ())
 607     return TODO_cleanup_cfg;
 608   return 0;
 609 }
 610
 611 namespace {
 612
 613 const pass_data pass_data_copy_prop =
 614 {
 615   GIMPLE_PASS, /* type */
 616   "copyprop", /* name */
 617   OPTGROUP_NONE, /* optinfo_flags */
 618   TV_TREE_COPY_PROP, /* tv_id */
 619   ( PROP_ssa | PROP_cfg ), /* properties_required */
 620   0, /* properties_provided */
 621   0, /* properties_destroyed */
 622   0, /* todo_flags_start */
 623   0, /* todo_flags_finish */
 624 };
 625
 626 class pass_copy_prop : public gimple_opt_pass
 627 {
 628 public:
 629   pass_copy_prop (gcc::context *ctxt)
 630     : gimple_opt_pass (pass_data_copy_prop, ctxt)
 631   {}
 632
 633   /* opt_pass methods: */
 634   opt_pass * clone () { return new pass_copy_prop (m_ctxt); }
 635   virtual bool gate (function *) { return flag_tree_copy_prop != 0; }
 636   virtual unsigned int execute (function *) { return execute_copy_prop (); }
 637
 638 }; // class pass_copy_prop
 639
 640 } // anon namespace
 641
 642 gimple_opt_pass *
 643 make_pass_copy_prop (gcc::context *ctxt)
 644 {
 645   return new pass_copy_prop (ctxt);
 646 }