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