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