1 /* Rename SSA copies.
2 Copyright (C) 2004-2013 Free Software Foundation, Inc.
3 Contributed by Andrew MacLeod <amacleod@redhat.com>
4
5 This file is part of GCC.
6
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.
11
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.
16
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/>. */
20
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"
39
40 static struct
41 {
42 /* Number of copies coalesced. */
43 int coalesced;
44 } stats;
45
46 /* The following routines implement the SSA copy renaming phase.
47
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.
50
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
56
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:
60
61 T.3 = <blah>
62 a = T.3
63
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:
68
69 a_5 = <blah>
70 a_1 = a_5
71
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:
75
76 a.8 = <blah>
77 a = a.8
78
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
82
83 a_1 = <blah>
84 <blah2> = a_1
85
86 get turned into
87
88 T.3_5 = <blah>
89 a_1 = T.3_5
90 <blah2> = a_1
91
92 Copy propagation is done in a forward direction, and if we can propagate
93 through the copy, we end up with:
94
95 T.3_5 = <blah>
96 <blah2> = T.3_5
97
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:
100
101 a_5 = <blah>
102 a_1 = a_5
103 <blah2> = a_1
104
105 which copy propagation would then turn into:
106
107 a_5 = <blah>
108 <blah2> = a_5
109
110 and so we still retain the user variable whenever possible. */
111
112
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. */
115
116 static void
copy_rename_partition_coalesce(var_map map,tree var1,tree var2,FILE * debug)117 copy_rename_partition_coalesce (var_map map, tree var1, tree var2, FILE *debug)
118 {
119 int p1, p2, p3;
120 tree root1, root2;
121 tree rep1, rep2;
122 bool ign1, ign2, abnorm;
123
124 gcc_assert (TREE_CODE (var1) == SSA_NAME);
125 gcc_assert (TREE_CODE (var2) == SSA_NAME);
126
127 register_ssa_partition (map, var1);
128 register_ssa_partition (map, var2);
129
130 p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1));
131 p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2));
132
133 if (debug)
134 {
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);
140 }
141
142 gcc_assert (p1 != NO_PARTITION);
143 gcc_assert (p2 != NO_PARTITION);
144
145 if (p1 == p2)
146 {
147 if (debug)
148 fprintf (debug, " : Already coalesced.\n");
149 return;
150 }
151
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;
158
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)
163 {
164 if (debug)
165 fprintf (debug, " : Abnormal PHI barrier. No coalesce.\n");
166 return;
167 }
168
169 /* Partitions already have the same root, simply merge them. */
170 if (root1 == root2)
171 {
172 p1 = partition_union (map->var_partition, p1, p2);
173 if (debug)
174 fprintf (debug, " : Same root, coalesced --> P%d.\n", p1);
175 return;
176 }
177
178 /* Never attempt to coalesce 2 different parameters. */
179 if ((root1 && TREE_CODE (root1) == PARM_DECL)
180 && (root2 && TREE_CODE (root2) == PARM_DECL))
181 {
182 if (debug)
183 fprintf (debug, " : 2 different PARM_DECLS. No coalesce.\n");
184 return;
185 }
186
187 if ((root1 && TREE_CODE (root1) == RESULT_DECL)
188 != (root2 && TREE_CODE (root2) == RESULT_DECL))
189 {
190 if (debug)
191 fprintf (debug, " : One root a RESULT_DECL. No coalesce.\n");
192 return;
193 }
194
195 ign1 = !root1 || (TREE_CODE (root1) == VAR_DECL && DECL_IGNORED_P (root1));
196 ign2 = !root2 || (TREE_CODE (root2) == VAR_DECL && DECL_IGNORED_P (root2));
197
198 /* Refrain from coalescing user variables, if requested. */
199 if (!ign1 && !ign2)
200 {
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)
206 {
207 if (debug)
208 fprintf (debug, " : 2 different USER vars. No coalesce.\n");
209 return;
210 }
211 else
212 ign2 = true;
213 }
214
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))
218 {
219 if (root2 && ssa_default_def (cfun, root2))
220 {
221 if (debug)
222 fprintf (debug, " : 2 default defs. No coalesce.\n");
223 return;
224 }
225 else
226 {
227 ign2 = true;
228 ign1 = false;
229 }
230 }
231 else if (root2 && ssa_default_def (cfun, root2))
232 {
233 ign1 = true;
234 ign2 = false;
235 }
236
237 /* Do not coalesce if we cannot assign a symbol to the partition. */
238 if (!(!ign2 && root2)
239 && !(!ign1 && root1))
240 {
241 if (debug)
242 fprintf (debug, " : Choosen variable has no root. No coalesce.\n");
243 return;
244 }
245
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))
253 {
254 if (debug)
255 fprintf (debug, " : Readonly variable. No coalesce.\n");
256 return;
257 }
258
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)))
266 {
267 if (debug)
268 fprintf (debug, " : Incompatible types. No coalesce.\n");
269 return;
270 }
271
272 /* Merge the two partitions. */
273 p3 = partition_union (map->var_partition, p1, p2);
274
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 ();
283
284 if (debug)
285 {
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");
290 }
291 }
292
293
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. */
299
300 static unsigned int
rename_ssa_copies(void)301 rename_ssa_copies (void)
302 {
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;
310
311 memset (&stats, 0, sizeof (stats));
312
313 if (dump_file && (dump_flags & TDF_DETAILS))
314 debug = dump_file;
315 else
316 debug = NULL;
317
318 map = init_var_map (num_ssa_names);
319
320 FOR_EACH_BB (bb)
321 {
322 /* Scan for real copies. */
323 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
324 {
325 stmt = gsi_stmt (gsi);
326 if (gimple_assign_ssa_name_copy_p (stmt))
327 {
328 tree lhs = gimple_assign_lhs (stmt);
329 tree rhs = gimple_assign_rhs1 (stmt);
330
331 copy_rename_partition_coalesce (map, lhs, rhs, debug);
332 }
333 }
334 }
335
336 FOR_EACH_BB (bb)
337 {
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))
340 {
341 size_t i;
342 tree res;
343
344 phi = gsi_stmt (gsi);
345 res = gimple_phi_result (phi);
346
347 /* Do not process virtual SSA_NAMES. */
348 if (virtual_operand_p (res))
349 continue;
350
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++)
356 {
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);
361 }
362 /* Else if all arguments are in the same partition try to merge
363 it with the result. */
364 else
365 {
366 int all_p_same = -1;
367 int p = -1;
368 for (i = 0; i < gimple_phi_num_args (phi); i++)
369 {
370 tree arg = PHI_ARG_DEF (phi, i);
371 if (TREE_CODE (arg) != SSA_NAME)
372 {
373 all_p_same = 0;
374 break;
375 }
376 else if (all_p_same == -1)
377 {
378 p = partition_find (map->var_partition,
379 SSA_NAME_VERSION (arg));
380 all_p_same = 1;
381 }
382 else if (all_p_same == 1
383 && p != partition_find (map->var_partition,
384 SSA_NAME_VERSION (arg)))
385 {
386 all_p_same = 0;
387 break;
388 }
389 }
390 if (all_p_same == 1)
391 copy_rename_partition_coalesce (map, res,
392 PHI_ARG_DEF (phi, 0),
393 debug);
394 }
395 }
396 }
397
398 if (debug)
399 dump_var_map (debug, map);
400
401 /* Now one more pass to make all elements of a partition share the same
402 root variable. */
403
404 for (x = 1; x < num_ssa_names; x++)
405 {
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)
413 {
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");
419 }
420 stats.coalesced++;
421 replace_ssa_name_symbol (var, SSA_NAME_VAR (part_var));
422 }
423
424 statistics_counter_event (cfun, "copies coalesced",
425 stats.coalesced);
426 delete_var_map (map);
427 return 0;
428 }
429
430 /* Return true if copy rename is to be performed. */
431
432 static bool
gate_copyrename(void)433 gate_copyrename (void)
434 {
435 return flag_tree_copyrename != 0;
436 }
437
438 struct gimple_opt_pass pass_rename_ssa_copies =
439 {
440 {
441 GIMPLE_PASS,
442 "copyrename", /* name */
443 OPTGROUP_NONE, /* optinfo_flags */
444 gate_copyrename, /* gate */
445 rename_ssa_copies, /* execute */
446 NULL, /* sub */
447 NULL, /* next */
448 0, /* static_pass_number */
449 TV_TREE_COPY_RENAME, /* tv_id */
450 PROP_cfg | PROP_ssa, /* properties_required */
451 0, /* properties_provided */
452 0, /* properties_destroyed */
453 0, /* todo_flags_start */
454 TODO_verify_ssa /* todo_flags_finish */
455 }
456 };
457