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