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