Daily bump.
[official-gcc.git] / gcc / tree-ssa-copyrename.c
blob990598ef29ba8e4a2c73d4a18d29cf5569bf319f
1 /* Rename SSA copies.
2 Copyright (C) 2004-2013 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 "tree.h"
26 #include "gimple.h"
27 #include "flags.h"
28 #include "basic-block.h"
29 #include "function.h"
30 #include "tree-pretty-print.h"
31 #include "bitmap.h"
32 #include "tree-flow.h"
33 #include "gimple.h"
34 #include "tree-inline.h"
35 #include "hashtab.h"
36 #include "tree-ssa-live.h"
37 #include "tree-pass.h"
38 #include "langhooks.h"
40 static struct
42 /* Number of copies coalesced. */
43 int coalesced;
44 } stats;
46 /* The following routines implement the SSA copy renaming phase.
48 This optimization looks for copies between 2 SSA_NAMES, either through a
49 direct copy, or an implicit one via a PHI node result and its arguments.
51 Each copy is examined to determine if it is possible to rename the base
52 variable of one of the operands to the same variable as the other operand.
53 i.e.
54 T.3_5 = <blah>
55 a_1 = T.3_5
57 If this copy couldn't be copy propagated, it could possibly remain in the
58 program throughout the optimization phases. After SSA->normal, it would
59 become:
61 T.3 = <blah>
62 a = T.3
64 Since T.3_5 is distinct from all other SSA versions of T.3, there is no
65 fundamental reason why the base variable needs to be T.3, subject to
66 certain restrictions. This optimization attempts to determine if we can
67 change the base variable on copies like this, and result in code such as:
69 a_5 = <blah>
70 a_1 = a_5
72 This gives the SSA->normal pass a shot at coalescing a_1 and a_5. If it is
73 possible, the copy goes away completely. If it isn't possible, a new temp
74 will be created for a_5, and you will end up with the exact same code:
76 a.8 = <blah>
77 a = a.8
79 The other benefit of performing this optimization relates to what variables
80 are chosen in copies. Gimplification of the program uses temporaries for
81 a lot of things. expressions like
83 a_1 = <blah>
84 <blah2> = a_1
86 get turned into
88 T.3_5 = <blah>
89 a_1 = T.3_5
90 <blah2> = a_1
92 Copy propagation is done in a forward direction, and if we can propagate
93 through the copy, we end up with:
95 T.3_5 = <blah>
96 <blah2> = T.3_5
98 The copy is gone, but so is all reference to the user variable 'a'. By
99 performing this optimization, we would see the sequence:
101 a_5 = <blah>
102 a_1 = a_5
103 <blah2> = a_1
105 which copy propagation would then turn into:
107 a_5 = <blah>
108 <blah2> = a_5
110 and so we still retain the user variable whenever possible. */
113 /* Coalesce the partitions in MAP representing VAR1 and VAR2 if it is valid.
114 Choose a representative for the partition, and send debug info to DEBUG. */
116 static void
117 copy_rename_partition_coalesce (var_map map, tree var1, tree var2, FILE *debug)
119 int p1, p2, p3;
120 tree root1, root2;
121 tree rep1, rep2;
122 bool ign1, ign2, abnorm;
124 gcc_assert (TREE_CODE (var1) == SSA_NAME);
125 gcc_assert (TREE_CODE (var2) == SSA_NAME);
127 register_ssa_partition (map, var1);
128 register_ssa_partition (map, var2);
130 p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1));
131 p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2));
133 if (debug)
135 fprintf (debug, "Try : ");
136 print_generic_expr (debug, var1, TDF_SLIM);
137 fprintf (debug, "(P%d) & ", p1);
138 print_generic_expr (debug, var2, TDF_SLIM);
139 fprintf (debug, "(P%d)", p2);
142 gcc_assert (p1 != NO_PARTITION);
143 gcc_assert (p2 != NO_PARTITION);
145 if (p1 == p2)
147 if (debug)
148 fprintf (debug, " : Already coalesced.\n");
149 return;
152 rep1 = partition_to_var (map, p1);
153 rep2 = partition_to_var (map, p2);
154 root1 = SSA_NAME_VAR (rep1);
155 root2 = SSA_NAME_VAR (rep2);
156 if (!root1 && !root2)
157 return;
159 /* Don't coalesce if one of the variables occurs in an abnormal PHI. */
160 abnorm = (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep1)
161 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep2));
162 if (abnorm)
164 if (debug)
165 fprintf (debug, " : Abnormal PHI barrier. No coalesce.\n");
166 return;
169 /* Partitions already have the same root, simply merge them. */
170 if (root1 == root2)
172 p1 = partition_union (map->var_partition, p1, p2);
173 if (debug)
174 fprintf (debug, " : Same root, coalesced --> P%d.\n", p1);
175 return;
178 /* Never attempt to coalesce 2 different parameters. */
179 if ((root1 && TREE_CODE (root1) == PARM_DECL)
180 && (root2 && TREE_CODE (root2) == PARM_DECL))
182 if (debug)
183 fprintf (debug, " : 2 different PARM_DECLS. No coalesce.\n");
184 return;
187 if ((root1 && TREE_CODE (root1) == RESULT_DECL)
188 != (root2 && TREE_CODE (root2) == RESULT_DECL))
190 if (debug)
191 fprintf (debug, " : One root a RESULT_DECL. No coalesce.\n");
192 return;
195 ign1 = !root1 || (TREE_CODE (root1) == VAR_DECL && DECL_IGNORED_P (root1));
196 ign2 = !root2 || (TREE_CODE (root2) == VAR_DECL && DECL_IGNORED_P (root2));
198 /* Refrain from coalescing user variables, if requested. */
199 if (!ign1 && !ign2)
201 if (flag_ssa_coalesce_vars && DECL_FROM_INLINE (root2))
202 ign2 = true;
203 else if (flag_ssa_coalesce_vars && DECL_FROM_INLINE (root1))
204 ign1 = true;
205 else if (flag_ssa_coalesce_vars != 2)
207 if (debug)
208 fprintf (debug, " : 2 different USER vars. No coalesce.\n");
209 return;
211 else
212 ign2 = true;
215 /* If both values have default defs, we can't coalesce. If only one has a
216 tag, make sure that variable is the new root partition. */
217 if (root1 && ssa_default_def (cfun, root1))
219 if (root2 && ssa_default_def (cfun, root2))
221 if (debug)
222 fprintf (debug, " : 2 default defs. No coalesce.\n");
223 return;
225 else
227 ign2 = true;
228 ign1 = false;
231 else if (root2 && ssa_default_def (cfun, root2))
233 ign1 = true;
234 ign2 = false;
237 /* Do not coalesce if we cannot assign a symbol to the partition. */
238 if (!(!ign2 && root2)
239 && !(!ign1 && root1))
241 if (debug)
242 fprintf (debug, " : Choosen variable has no root. No coalesce.\n");
243 return;
246 /* Don't coalesce if the new chosen root variable would be read-only.
247 If both ign1 && ign2, then the root var of the larger partition
248 wins, so reject in that case if any of the root vars is TREE_READONLY.
249 Otherwise reject only if the root var, on which replace_ssa_name_symbol
250 will be called below, is readonly. */
251 if (((root1 && TREE_READONLY (root1)) && ign2)
252 || ((root2 && TREE_READONLY (root2)) && ign1))
254 if (debug)
255 fprintf (debug, " : Readonly variable. No coalesce.\n");
256 return;
259 /* Don't coalesce if the two variables aren't type compatible . */
260 if (!types_compatible_p (TREE_TYPE (var1), TREE_TYPE (var2))
261 /* There is a disconnect between the middle-end type-system and
262 VRP, avoid coalescing enum types with different bounds. */
263 || ((TREE_CODE (TREE_TYPE (var1)) == ENUMERAL_TYPE
264 || TREE_CODE (TREE_TYPE (var2)) == ENUMERAL_TYPE)
265 && TREE_TYPE (var1) != TREE_TYPE (var2)))
267 if (debug)
268 fprintf (debug, " : Incompatible types. No coalesce.\n");
269 return;
272 /* Merge the two partitions. */
273 p3 = partition_union (map->var_partition, p1, p2);
275 /* Set the root variable of the partition to the better choice, if there is
276 one. */
277 if (!ign2 && root2)
278 replace_ssa_name_symbol (partition_to_var (map, p3), root2);
279 else if (!ign1 && root1)
280 replace_ssa_name_symbol (partition_to_var (map, p3), root1);
281 else
282 gcc_unreachable ();
284 if (debug)
286 fprintf (debug, " --> P%d ", p3);
287 print_generic_expr (debug, SSA_NAME_VAR (partition_to_var (map, p3)),
288 TDF_SLIM);
289 fprintf (debug, "\n");
294 /* This function will make a pass through the IL, and attempt to coalesce any
295 SSA versions which occur in PHI's or copies. Coalescing is accomplished by
296 changing the underlying root variable of all coalesced version. This will
297 then cause the SSA->normal pass to attempt to coalesce them all to the same
298 variable. */
300 static unsigned int
301 rename_ssa_copies (void)
303 var_map map;
304 basic_block bb;
305 gimple_stmt_iterator gsi;
306 tree var, part_var;
307 gimple stmt, phi;
308 unsigned x;
309 FILE *debug;
311 memset (&stats, 0, sizeof (stats));
313 if (dump_file && (dump_flags & TDF_DETAILS))
314 debug = dump_file;
315 else
316 debug = NULL;
318 map = init_var_map (num_ssa_names);
320 FOR_EACH_BB (bb)
322 /* Scan for real copies. */
323 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
325 stmt = gsi_stmt (gsi);
326 if (gimple_assign_ssa_name_copy_p (stmt))
328 tree lhs = gimple_assign_lhs (stmt);
329 tree rhs = gimple_assign_rhs1 (stmt);
331 copy_rename_partition_coalesce (map, lhs, rhs, debug);
336 FOR_EACH_BB (bb)
338 /* Treat PHI nodes as copies between the result and each argument. */
339 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
341 size_t i;
342 tree res;
344 phi = gsi_stmt (gsi);
345 res = gimple_phi_result (phi);
347 /* Do not process virtual SSA_NAMES. */
348 if (virtual_operand_p (res))
349 continue;
351 /* Make sure to only use the same partition for an argument
352 as the result but never the other way around. */
353 if (SSA_NAME_VAR (res)
354 && !DECL_IGNORED_P (SSA_NAME_VAR (res)))
355 for (i = 0; i < gimple_phi_num_args (phi); i++)
357 tree arg = PHI_ARG_DEF (phi, i);
358 if (TREE_CODE (arg) == SSA_NAME)
359 copy_rename_partition_coalesce (map, res, arg,
360 debug);
362 /* Else if all arguments are in the same partition try to merge
363 it with the result. */
364 else
366 int all_p_same = -1;
367 int p = -1;
368 for (i = 0; i < gimple_phi_num_args (phi); i++)
370 tree arg = PHI_ARG_DEF (phi, i);
371 if (TREE_CODE (arg) != SSA_NAME)
373 all_p_same = 0;
374 break;
376 else if (all_p_same == -1)
378 p = partition_find (map->var_partition,
379 SSA_NAME_VERSION (arg));
380 all_p_same = 1;
382 else if (all_p_same == 1
383 && p != partition_find (map->var_partition,
384 SSA_NAME_VERSION (arg)))
386 all_p_same = 0;
387 break;
390 if (all_p_same == 1)
391 copy_rename_partition_coalesce (map, res,
392 PHI_ARG_DEF (phi, 0),
393 debug);
398 if (debug)
399 dump_var_map (debug, map);
401 /* Now one more pass to make all elements of a partition share the same
402 root variable. */
404 for (x = 1; x < num_ssa_names; x++)
406 part_var = partition_to_var (map, x);
407 if (!part_var)
408 continue;
409 var = ssa_name (x);
410 if (SSA_NAME_VAR (var) == SSA_NAME_VAR (part_var))
411 continue;
412 if (debug)
414 fprintf (debug, "Coalesced ");
415 print_generic_expr (debug, var, TDF_SLIM);
416 fprintf (debug, " to ");
417 print_generic_expr (debug, part_var, TDF_SLIM);
418 fprintf (debug, "\n");
420 stats.coalesced++;
421 replace_ssa_name_symbol (var, SSA_NAME_VAR (part_var));
424 statistics_counter_event (cfun, "copies coalesced",
425 stats.coalesced);
426 delete_var_map (map);
427 return 0;
430 /* Return true if copy rename is to be performed. */
432 static bool
433 gate_copyrename (void)
435 return flag_tree_copyrename != 0;
438 namespace {
440 const pass_data pass_data_rename_ssa_copies =
442 GIMPLE_PASS, /* type */
443 "copyrename", /* name */
444 OPTGROUP_NONE, /* optinfo_flags */
445 true, /* has_gate */
446 true, /* has_execute */
447 TV_TREE_COPY_RENAME, /* tv_id */
448 ( PROP_cfg | PROP_ssa ), /* properties_required */
449 0, /* properties_provided */
450 0, /* properties_destroyed */
451 0, /* todo_flags_start */
452 TODO_verify_ssa, /* todo_flags_finish */
455 class pass_rename_ssa_copies : public gimple_opt_pass
457 public:
458 pass_rename_ssa_copies(gcc::context *ctxt)
459 : gimple_opt_pass(pass_data_rename_ssa_copies, ctxt)
462 /* opt_pass methods: */
463 opt_pass * clone () { return new pass_rename_ssa_copies (ctxt_); }
464 bool gate () { return gate_copyrename (); }
465 unsigned int execute () { return rename_ssa_copies (); }
467 }; // class pass_rename_ssa_copies
469 } // anon namespace
471 gimple_opt_pass *
472 make_pass_rename_ssa_copies (gcc::context *ctxt)
474 return new pass_rename_ssa_copies (ctxt);