gcc/tree-ssa-copy.cc

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