PR sanitizer/65400
[official-gcc.git] / gcc / tree-ssa-copyrename.c
blobf3cb56ef5f96fdbfdac026f61edb2d28a0695403
1 /* Rename SSA copies.
2 Copyright (C) 2004-2015 Free Software Foundation, Inc.
3 Contributed by Andrew MacLeod <amacleod@redhat.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
10 any later version.
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "hash-set.h"
26 #include "machmode.h"
27 #include "vec.h"
28 #include "double-int.h"
29 #include "input.h"
30 #include "alias.h"
31 #include "symtab.h"
32 #include "wide-int.h"
33 #include "inchash.h"
34 #include "tree.h"
35 #include "fold-const.h"
36 #include "predict.h"
37 #include "hard-reg-set.h"
38 #include "function.h"
39 #include "dominance.h"
40 #include "cfg.h"
41 #include "basic-block.h"
42 #include "tree-ssa-alias.h"
43 #include "internal-fn.h"
44 #include "gimple-expr.h"
45 #include "is-a.h"
46 #include "gimple.h"
47 #include "gimple-iterator.h"
48 #include "flags.h"
49 #include "tree-pretty-print.h"
50 #include "bitmap.h"
51 #include "gimple-ssa.h"
52 #include "stringpool.h"
53 #include "tree-ssanames.h"
54 #include "hashtab.h"
55 #include "rtl.h"
56 #include "statistics.h"
57 #include "real.h"
58 #include "fixed-value.h"
59 #include "insn-config.h"
60 #include "expmed.h"
61 #include "dojump.h"
62 #include "explow.h"
63 #include "calls.h"
64 #include "emit-rtl.h"
65 #include "varasm.h"
66 #include "stmt.h"
67 #include "expr.h"
68 #include "tree-dfa.h"
69 #include "tree-inline.h"
70 #include "tree-ssa-live.h"
71 #include "tree-pass.h"
72 #include "langhooks.h"
74 static struct
76 /* Number of copies coalesced. */
77 int coalesced;
78 } stats;
80 /* The following routines implement the SSA copy renaming phase.
82 This optimization looks for copies between 2 SSA_NAMES, either through a
83 direct copy, or an implicit one via a PHI node result and its arguments.
85 Each copy is examined to determine if it is possible to rename the base
86 variable of one of the operands to the same variable as the other operand.
87 i.e.
88 T.3_5 = <blah>
89 a_1 = T.3_5
91 If this copy couldn't be copy propagated, it could possibly remain in the
92 program throughout the optimization phases. After SSA->normal, it would
93 become:
95 T.3 = <blah>
96 a = T.3
98 Since T.3_5 is distinct from all other SSA versions of T.3, there is no
99 fundamental reason why the base variable needs to be T.3, subject to
100 certain restrictions. This optimization attempts to determine if we can
101 change the base variable on copies like this, and result in code such as:
103 a_5 = <blah>
104 a_1 = a_5
106 This gives the SSA->normal pass a shot at coalescing a_1 and a_5. If it is
107 possible, the copy goes away completely. If it isn't possible, a new temp
108 will be created for a_5, and you will end up with the exact same code:
110 a.8 = <blah>
111 a = a.8
113 The other benefit of performing this optimization relates to what variables
114 are chosen in copies. Gimplification of the program uses temporaries for
115 a lot of things. expressions like
117 a_1 = <blah>
118 <blah2> = a_1
120 get turned into
122 T.3_5 = <blah>
123 a_1 = T.3_5
124 <blah2> = a_1
126 Copy propagation is done in a forward direction, and if we can propagate
127 through the copy, we end up with:
129 T.3_5 = <blah>
130 <blah2> = T.3_5
132 The copy is gone, but so is all reference to the user variable 'a'. By
133 performing this optimization, we would see the sequence:
135 a_5 = <blah>
136 a_1 = a_5
137 <blah2> = a_1
139 which copy propagation would then turn into:
141 a_5 = <blah>
142 <blah2> = a_5
144 and so we still retain the user variable whenever possible. */
147 /* Coalesce the partitions in MAP representing VAR1 and VAR2 if it is valid.
148 Choose a representative for the partition, and send debug info to DEBUG. */
150 static void
151 copy_rename_partition_coalesce (var_map map, tree var1, tree var2, FILE *debug)
153 int p1, p2, p3;
154 tree root1, root2;
155 tree rep1, rep2;
156 bool ign1, ign2, abnorm;
158 gcc_assert (TREE_CODE (var1) == SSA_NAME);
159 gcc_assert (TREE_CODE (var2) == SSA_NAME);
161 register_ssa_partition (map, var1);
162 register_ssa_partition (map, var2);
164 p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1));
165 p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2));
167 if (debug)
169 fprintf (debug, "Try : ");
170 print_generic_expr (debug, var1, TDF_SLIM);
171 fprintf (debug, "(P%d) & ", p1);
172 print_generic_expr (debug, var2, TDF_SLIM);
173 fprintf (debug, "(P%d)", p2);
176 gcc_assert (p1 != NO_PARTITION);
177 gcc_assert (p2 != NO_PARTITION);
179 if (p1 == p2)
181 if (debug)
182 fprintf (debug, " : Already coalesced.\n");
183 return;
186 rep1 = partition_to_var (map, p1);
187 rep2 = partition_to_var (map, p2);
188 root1 = SSA_NAME_VAR (rep1);
189 root2 = SSA_NAME_VAR (rep2);
190 if (!root1 && !root2)
191 return;
193 /* Don't coalesce if one of the variables occurs in an abnormal PHI. */
194 abnorm = (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep1)
195 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep2));
196 if (abnorm)
198 if (debug)
199 fprintf (debug, " : Abnormal PHI barrier. No coalesce.\n");
200 return;
203 /* Partitions already have the same root, simply merge them. */
204 if (root1 == root2)
206 p1 = partition_union (map->var_partition, p1, p2);
207 if (debug)
208 fprintf (debug, " : Same root, coalesced --> P%d.\n", p1);
209 return;
212 /* Never attempt to coalesce 2 different parameters. */
213 if ((root1 && TREE_CODE (root1) == PARM_DECL)
214 && (root2 && TREE_CODE (root2) == PARM_DECL))
216 if (debug)
217 fprintf (debug, " : 2 different PARM_DECLS. No coalesce.\n");
218 return;
221 if ((root1 && TREE_CODE (root1) == RESULT_DECL)
222 != (root2 && TREE_CODE (root2) == RESULT_DECL))
224 if (debug)
225 fprintf (debug, " : One root a RESULT_DECL. No coalesce.\n");
226 return;
229 ign1 = !root1 || (TREE_CODE (root1) == VAR_DECL && DECL_IGNORED_P (root1));
230 ign2 = !root2 || (TREE_CODE (root2) == VAR_DECL && DECL_IGNORED_P (root2));
232 /* Refrain from coalescing user variables, if requested. */
233 if (!ign1 && !ign2)
235 if (flag_ssa_coalesce_vars && DECL_FROM_INLINE (root2))
236 ign2 = true;
237 else if (flag_ssa_coalesce_vars && DECL_FROM_INLINE (root1))
238 ign1 = true;
239 else if (flag_ssa_coalesce_vars != 2)
241 if (debug)
242 fprintf (debug, " : 2 different USER vars. No coalesce.\n");
243 return;
245 else
246 ign2 = true;
249 /* If both values have default defs, we can't coalesce. If only one has a
250 tag, make sure that variable is the new root partition. */
251 if (root1 && ssa_default_def (cfun, root1))
253 if (root2 && ssa_default_def (cfun, root2))
255 if (debug)
256 fprintf (debug, " : 2 default defs. No coalesce.\n");
257 return;
259 else
261 ign2 = true;
262 ign1 = false;
265 else if (root2 && ssa_default_def (cfun, root2))
267 ign1 = true;
268 ign2 = false;
271 /* Do not coalesce if we cannot assign a symbol to the partition. */
272 if (!(!ign2 && root2)
273 && !(!ign1 && root1))
275 if (debug)
276 fprintf (debug, " : Choosen variable has no root. No coalesce.\n");
277 return;
280 /* Don't coalesce if the new chosen root variable would be read-only.
281 If both ign1 && ign2, then the root var of the larger partition
282 wins, so reject in that case if any of the root vars is TREE_READONLY.
283 Otherwise reject only if the root var, on which replace_ssa_name_symbol
284 will be called below, is readonly. */
285 if (((root1 && TREE_READONLY (root1)) && ign2)
286 || ((root2 && TREE_READONLY (root2)) && ign1))
288 if (debug)
289 fprintf (debug, " : Readonly variable. No coalesce.\n");
290 return;
293 /* Don't coalesce if the two variables aren't type compatible . */
294 if (!types_compatible_p (TREE_TYPE (var1), TREE_TYPE (var2))
295 /* There is a disconnect between the middle-end type-system and
296 VRP, avoid coalescing enum types with different bounds. */
297 || ((TREE_CODE (TREE_TYPE (var1)) == ENUMERAL_TYPE
298 || TREE_CODE (TREE_TYPE (var2)) == ENUMERAL_TYPE)
299 && TREE_TYPE (var1) != TREE_TYPE (var2)))
301 if (debug)
302 fprintf (debug, " : Incompatible types. No coalesce.\n");
303 return;
306 /* Merge the two partitions. */
307 p3 = partition_union (map->var_partition, p1, p2);
309 /* Set the root variable of the partition to the better choice, if there is
310 one. */
311 if (!ign2 && root2)
312 replace_ssa_name_symbol (partition_to_var (map, p3), root2);
313 else if (!ign1 && root1)
314 replace_ssa_name_symbol (partition_to_var (map, p3), root1);
315 else
316 gcc_unreachable ();
318 if (debug)
320 fprintf (debug, " --> P%d ", p3);
321 print_generic_expr (debug, SSA_NAME_VAR (partition_to_var (map, p3)),
322 TDF_SLIM);
323 fprintf (debug, "\n");
328 namespace {
330 const pass_data pass_data_rename_ssa_copies =
332 GIMPLE_PASS, /* type */
333 "copyrename", /* name */
334 OPTGROUP_NONE, /* optinfo_flags */
335 TV_TREE_COPY_RENAME, /* tv_id */
336 ( PROP_cfg | PROP_ssa ), /* properties_required */
337 0, /* properties_provided */
338 0, /* properties_destroyed */
339 0, /* todo_flags_start */
340 0, /* todo_flags_finish */
343 class pass_rename_ssa_copies : public gimple_opt_pass
345 public:
346 pass_rename_ssa_copies (gcc::context *ctxt)
347 : gimple_opt_pass (pass_data_rename_ssa_copies, ctxt)
350 /* opt_pass methods: */
351 opt_pass * clone () { return new pass_rename_ssa_copies (m_ctxt); }
352 virtual bool gate (function *) { return flag_tree_copyrename != 0; }
353 virtual unsigned int execute (function *);
355 }; // class pass_rename_ssa_copies
357 /* This function will make a pass through the IL, and attempt to coalesce any
358 SSA versions which occur in PHI's or copies. Coalescing is accomplished by
359 changing the underlying root variable of all coalesced version. This will
360 then cause the SSA->normal pass to attempt to coalesce them all to the same
361 variable. */
363 unsigned int
364 pass_rename_ssa_copies::execute (function *fun)
366 var_map map;
367 basic_block bb;
368 tree var, part_var;
369 gimple stmt;
370 unsigned x;
371 FILE *debug;
373 memset (&stats, 0, sizeof (stats));
375 if (dump_file && (dump_flags & TDF_DETAILS))
376 debug = dump_file;
377 else
378 debug = NULL;
380 map = init_var_map (num_ssa_names);
382 FOR_EACH_BB_FN (bb, fun)
384 /* Scan for real copies. */
385 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
386 gsi_next (&gsi))
388 stmt = gsi_stmt (gsi);
389 if (gimple_assign_ssa_name_copy_p (stmt))
391 tree lhs = gimple_assign_lhs (stmt);
392 tree rhs = gimple_assign_rhs1 (stmt);
394 copy_rename_partition_coalesce (map, lhs, rhs, debug);
399 FOR_EACH_BB_FN (bb, fun)
401 /* Treat PHI nodes as copies between the result and each argument. */
402 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
403 gsi_next (&gsi))
405 size_t i;
406 tree res;
407 gphi *phi = gsi.phi ();
408 res = gimple_phi_result (phi);
410 /* Do not process virtual SSA_NAMES. */
411 if (virtual_operand_p (res))
412 continue;
414 /* Make sure to only use the same partition for an argument
415 as the result but never the other way around. */
416 if (SSA_NAME_VAR (res)
417 && !DECL_IGNORED_P (SSA_NAME_VAR (res)))
418 for (i = 0; i < gimple_phi_num_args (phi); i++)
420 tree arg = PHI_ARG_DEF (phi, i);
421 if (TREE_CODE (arg) == SSA_NAME)
422 copy_rename_partition_coalesce (map, res, arg,
423 debug);
425 /* Else if all arguments are in the same partition try to merge
426 it with the result. */
427 else
429 int all_p_same = -1;
430 int p = -1;
431 for (i = 0; i < gimple_phi_num_args (phi); i++)
433 tree arg = PHI_ARG_DEF (phi, i);
434 if (TREE_CODE (arg) != SSA_NAME)
436 all_p_same = 0;
437 break;
439 else if (all_p_same == -1)
441 p = partition_find (map->var_partition,
442 SSA_NAME_VERSION (arg));
443 all_p_same = 1;
445 else if (all_p_same == 1
446 && p != partition_find (map->var_partition,
447 SSA_NAME_VERSION (arg)))
449 all_p_same = 0;
450 break;
453 if (all_p_same == 1)
454 copy_rename_partition_coalesce (map, res,
455 PHI_ARG_DEF (phi, 0),
456 debug);
461 if (debug)
462 dump_var_map (debug, map);
464 /* Now one more pass to make all elements of a partition share the same
465 root variable. */
467 for (x = 1; x < num_ssa_names; x++)
469 part_var = partition_to_var (map, x);
470 if (!part_var)
471 continue;
472 var = ssa_name (x);
473 if (SSA_NAME_VAR (var) == SSA_NAME_VAR (part_var))
474 continue;
475 if (debug)
477 fprintf (debug, "Coalesced ");
478 print_generic_expr (debug, var, TDF_SLIM);
479 fprintf (debug, " to ");
480 print_generic_expr (debug, part_var, TDF_SLIM);
481 fprintf (debug, "\n");
483 stats.coalesced++;
484 replace_ssa_name_symbol (var, SSA_NAME_VAR (part_var));
487 statistics_counter_event (fun, "copies coalesced",
488 stats.coalesced);
489 delete_var_map (map);
490 return 0;
493 } // anon namespace
495 gimple_opt_pass *
496 make_pass_rename_ssa_copies (gcc::context *ctxt)
498 return new pass_rename_ssa_copies (ctxt);