re PR testsuite/40567 (Revision 149002 caused many failures)
[official-gcc.git] / gcc / tree-ssa-copyrename.c
blobed221c2f3e08565a0291cc3831ec8a6c05023dba
1 /* Rename SSA copies.
2 Copyright (C) 2004, 2006, 2007, 2008 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 "diagnostic.h"
31 #include "bitmap.h"
32 #include "tree-flow.h"
33 #include "gimple.h"
34 #include "tree-inline.h"
35 #include "timevar.h"
36 #include "hashtab.h"
37 #include "tree-dump.h"
38 #include "tree-ssa-live.h"
39 #include "tree-pass.h"
40 #include "langhooks.h"
42 /* The following routines implement the SSA copy renaming phase.
44 This optimization looks for copies between 2 SSA_NAMES, either through a
45 direct copy, or an implicit one via a PHI node result and its arguments.
47 Each copy is examined to determine if it is possible to rename the base
48 variable of one of the operands to the same variable as the other operand.
49 i.e.
50 T.3_5 = <blah>
51 a_1 = T.3_5
53 If this copy couldn't be copy propagated, it could possibly remain in the
54 program throughout the optimization phases. After SSA->normal, it would
55 become:
57 T.3 = <blah>
58 a = T.3
60 Since T.3_5 is distinct from all other SSA versions of T.3, there is no
61 fundamental reason why the base variable needs to be T.3, subject to
62 certain restrictions. This optimization attempts to determine if we can
63 change the base variable on copies like this, and result in code such as:
65 a_5 = <blah>
66 a_1 = a_5
68 This gives the SSA->normal pass a shot at coalescing a_1 and a_5. If it is
69 possible, the copy goes away completely. If it isn't possible, a new temp
70 will be created for a_5, and you will end up with the exact same code:
72 a.8 = <blah>
73 a = a.8
75 The other benefit of performing this optimization relates to what variables
76 are chosen in copies. Gimplification of the program uses temporaries for
77 a lot of things. expressions like
79 a_1 = <blah>
80 <blah2> = a_1
82 get turned into
84 T.3_5 = <blah>
85 a_1 = T.3_5
86 <blah2> = a_1
88 Copy propagation is done in a forward direction, and if we can propagate
89 through the copy, we end up with:
91 T.3_5 = <blah>
92 <blah2> = T.3_5
94 The copy is gone, but so is all reference to the user variable 'a'. By
95 performing this optimization, we would see the sequence:
97 a_5 = <blah>
98 a_1 = a_5
99 <blah2> = a_1
101 which copy propagation would then turn into:
103 a_5 = <blah>
104 <blah2> = a_5
106 and so we still retain the user variable whenever possible. */
109 /* Coalesce the partitions in MAP representing VAR1 and VAR2 if it is valid.
110 Choose a representative for the partition, and send debug info to DEBUG. */
112 static bool
113 copy_rename_partition_coalesce (var_map map, tree var1, tree var2, FILE *debug)
115 int p1, p2, p3;
116 tree root1, root2;
117 tree rep1, rep2;
118 bool ign1, ign2, abnorm;
120 gcc_assert (TREE_CODE (var1) == SSA_NAME);
121 gcc_assert (TREE_CODE (var2) == SSA_NAME);
123 register_ssa_partition (map, var1);
124 register_ssa_partition (map, var2);
126 p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1));
127 p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2));
129 if (debug)
131 fprintf (debug, "Try : ");
132 print_generic_expr (debug, var1, TDF_SLIM);
133 fprintf (debug, "(P%d) & ", p1);
134 print_generic_expr (debug, var2, TDF_SLIM);
135 fprintf (debug, "(P%d)", p2);
138 gcc_assert (p1 != NO_PARTITION);
139 gcc_assert (p2 != NO_PARTITION);
141 rep1 = partition_to_var (map, p1);
142 rep2 = partition_to_var (map, p2);
143 root1 = SSA_NAME_VAR (rep1);
144 root2 = SSA_NAME_VAR (rep2);
146 if (p1 == p2)
148 if (debug)
149 fprintf (debug, " : Already coalesced.\n");
150 return false;
153 /* Don't coalesce if one of the variables occurs in an abnormal PHI. */
154 abnorm = (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep1)
155 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep2));
156 if (abnorm)
158 if (debug)
159 fprintf (debug, " : Abnormal PHI barrier. No coalesce.\n");
160 return false;
163 /* Partitions already have the same root, simply merge them. */
164 if (root1 == root2)
166 p1 = partition_union (map->var_partition, p1, p2);
167 if (debug)
168 fprintf (debug, " : Same root, coalesced --> P%d.\n", p1);
169 return false;
172 /* Never attempt to coalesce 2 difference parameters. */
173 if (TREE_CODE (root1) == PARM_DECL && TREE_CODE (root2) == PARM_DECL)
175 if (debug)
176 fprintf (debug, " : 2 different PARM_DECLS. No coalesce.\n");
177 return false;
180 if ((TREE_CODE (root1) == RESULT_DECL) != (TREE_CODE (root2) == RESULT_DECL))
182 if (debug)
183 fprintf (debug, " : One root a RESULT_DECL. No coalesce.\n");
184 return false;
187 ign1 = TREE_CODE (root1) == VAR_DECL && DECL_IGNORED_P (root1);
188 ign2 = TREE_CODE (root2) == VAR_DECL && DECL_IGNORED_P (root2);
190 /* Never attempt to coalesce 2 user variables unless one is an inline
191 variable. */
192 if (!ign1 && !ign2)
194 if (DECL_FROM_INLINE (root2))
195 ign2 = true;
196 else if (DECL_FROM_INLINE (root1))
197 ign1 = true;
198 else
200 if (debug)
201 fprintf (debug, " : 2 different USER vars. No coalesce.\n");
202 return false;
206 /* If both values have default defs, we can't coalesce. If only one has a
207 tag, make sure that variable is the new root partition. */
208 if (gimple_default_def (cfun, root1))
210 if (gimple_default_def (cfun, root2))
212 if (debug)
213 fprintf (debug, " : 2 default defs. No coalesce.\n");
214 return false;
216 else
218 ign2 = true;
219 ign1 = false;
222 else if (gimple_default_def (cfun, root2))
224 ign1 = true;
225 ign2 = false;
228 /* Don't coalesce if the two variables aren't type compatible. */
229 if (!types_compatible_p (TREE_TYPE (root1), TREE_TYPE (root2)))
231 if (debug)
232 fprintf (debug, " : Incompatible types. No coalesce.\n");
233 return false;
236 /* Merge the two partitions. */
237 p3 = partition_union (map->var_partition, p1, p2);
239 /* Set the root variable of the partition to the better choice, if there is
240 one. */
241 if (!ign2)
242 replace_ssa_name_symbol (partition_to_var (map, p3), root2);
243 else if (!ign1)
244 replace_ssa_name_symbol (partition_to_var (map, p3), root1);
246 if (debug)
248 fprintf (debug, " --> P%d ", p3);
249 print_generic_expr (debug, SSA_NAME_VAR (partition_to_var (map, p3)),
250 TDF_SLIM);
251 fprintf (debug, "\n");
253 return true;
257 /* This function will make a pass through the IL, and attempt to coalesce any
258 SSA versions which occur in PHI's or copies. Coalescing is accomplished by
259 changing the underlying root variable of all coalesced version. This will
260 then cause the SSA->normal pass to attempt to coalesce them all to the same
261 variable. */
263 static unsigned int
264 rename_ssa_copies (void)
266 var_map map;
267 basic_block bb;
268 gimple_stmt_iterator gsi;
269 tree var, part_var;
270 gimple stmt, phi;
271 unsigned x;
272 FILE *debug;
273 bool updated = false;
275 if (dump_file && (dump_flags & TDF_DETAILS))
276 debug = dump_file;
277 else
278 debug = NULL;
280 map = init_var_map (num_ssa_names);
282 FOR_EACH_BB (bb)
284 /* Scan for real copies. */
285 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
287 stmt = gsi_stmt (gsi);
288 if (gimple_assign_ssa_name_copy_p (stmt))
290 tree lhs = gimple_assign_lhs (stmt);
291 tree rhs = gimple_assign_rhs1 (stmt);
293 updated |= copy_rename_partition_coalesce (map, lhs, rhs, debug);
298 FOR_EACH_BB (bb)
300 /* Treat PHI nodes as copies between the result and each argument. */
301 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
303 size_t i;
304 tree res;
306 phi = gsi_stmt (gsi);
307 res = gimple_phi_result (phi);
309 /* Do not process virtual SSA_NAMES. */
310 if (!is_gimple_reg (SSA_NAME_VAR (res)))
311 continue;
313 for (i = 0; i < gimple_phi_num_args (phi); i++)
315 tree arg = gimple_phi_arg (phi, i)->def;
316 if (TREE_CODE (arg) == SSA_NAME)
317 updated |= copy_rename_partition_coalesce (map, res, arg, debug);
322 if (debug)
323 dump_var_map (debug, map);
325 /* Now one more pass to make all elements of a partition share the same
326 root variable. */
328 for (x = 1; x < num_ssa_names; x++)
330 part_var = partition_to_var (map, x);
331 if (!part_var)
332 continue;
333 var = ssa_name (x);
334 if (debug)
336 if (SSA_NAME_VAR (var) != SSA_NAME_VAR (part_var))
338 fprintf (debug, "Coalesced ");
339 print_generic_expr (debug, var, TDF_SLIM);
340 fprintf (debug, " to ");
341 print_generic_expr (debug, part_var, TDF_SLIM);
342 fprintf (debug, "\n");
345 replace_ssa_name_symbol (var, SSA_NAME_VAR (part_var));
348 delete_var_map (map);
349 return updated ? TODO_remove_unused_locals : 0;
352 /* Return true if copy rename is to be performed. */
354 static bool
355 gate_copyrename (void)
357 return flag_tree_copyrename != 0;
360 struct gimple_opt_pass pass_rename_ssa_copies =
363 GIMPLE_PASS,
364 "copyrename", /* name */
365 gate_copyrename, /* gate */
366 rename_ssa_copies, /* execute */
367 NULL, /* sub */
368 NULL, /* next */
369 0, /* static_pass_number */
370 TV_TREE_COPY_RENAME, /* tv_id */
371 PROP_cfg | PROP_ssa, /* properties_required */
372 0, /* properties_provided */
373 0, /* properties_destroyed */
374 0, /* todo_flags_start */
375 TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */