Daily bump.
[official-gcc.git] / gcc / tree-ssa-copyrename.c
blobabee6b9407fbabb74cf0adb64e1c1b1ab67485eb
1 /* Rename SSA copies.
2 Copyright (C) 2004, 2006, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
4 Contributed by Andrew MacLeod <amacleod@redhat.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
11 any later version.
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "tree.h"
27 #include "gimple.h"
28 #include "flags.h"
29 #include "basic-block.h"
30 #include "function.h"
31 #include "tree-pretty-print.h"
32 #include "bitmap.h"
33 #include "tree-flow.h"
34 #include "gimple.h"
35 #include "tree-inline.h"
36 #include "timevar.h"
37 #include "hashtab.h"
38 #include "tree-dump.h"
39 #include "tree-ssa-live.h"
40 #include "tree-pass.h"
41 #include "langhooks.h"
43 /* The following routines implement the SSA copy renaming phase.
45 This optimization looks for copies between 2 SSA_NAMES, either through a
46 direct copy, or an implicit one via a PHI node result and its arguments.
48 Each copy is examined to determine if it is possible to rename the base
49 variable of one of the operands to the same variable as the other operand.
50 i.e.
51 T.3_5 = <blah>
52 a_1 = T.3_5
54 If this copy couldn't be copy propagated, it could possibly remain in the
55 program throughout the optimization phases. After SSA->normal, it would
56 become:
58 T.3 = <blah>
59 a = T.3
61 Since T.3_5 is distinct from all other SSA versions of T.3, there is no
62 fundamental reason why the base variable needs to be T.3, subject to
63 certain restrictions. This optimization attempts to determine if we can
64 change the base variable on copies like this, and result in code such as:
66 a_5 = <blah>
67 a_1 = a_5
69 This gives the SSA->normal pass a shot at coalescing a_1 and a_5. If it is
70 possible, the copy goes away completely. If it isn't possible, a new temp
71 will be created for a_5, and you will end up with the exact same code:
73 a.8 = <blah>
74 a = a.8
76 The other benefit of performing this optimization relates to what variables
77 are chosen in copies. Gimplification of the program uses temporaries for
78 a lot of things. expressions like
80 a_1 = <blah>
81 <blah2> = a_1
83 get turned into
85 T.3_5 = <blah>
86 a_1 = T.3_5
87 <blah2> = a_1
89 Copy propagation is done in a forward direction, and if we can propagate
90 through the copy, we end up with:
92 T.3_5 = <blah>
93 <blah2> = T.3_5
95 The copy is gone, but so is all reference to the user variable 'a'. By
96 performing this optimization, we would see the sequence:
98 a_5 = <blah>
99 a_1 = a_5
100 <blah2> = a_1
102 which copy propagation would then turn into:
104 a_5 = <blah>
105 <blah2> = a_5
107 and so we still retain the user variable whenever possible. */
110 /* Coalesce the partitions in MAP representing VAR1 and VAR2 if it is valid.
111 Choose a representative for the partition, and send debug info to DEBUG. */
113 static bool
114 copy_rename_partition_coalesce (var_map map, tree var1, tree var2, FILE *debug)
116 int p1, p2, p3;
117 tree root1, root2;
118 tree rep1, rep2;
119 bool ign1, ign2, abnorm;
121 gcc_assert (TREE_CODE (var1) == SSA_NAME);
122 gcc_assert (TREE_CODE (var2) == SSA_NAME);
124 register_ssa_partition (map, var1);
125 register_ssa_partition (map, var2);
127 p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1));
128 p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2));
130 if (debug)
132 fprintf (debug, "Try : ");
133 print_generic_expr (debug, var1, TDF_SLIM);
134 fprintf (debug, "(P%d) & ", p1);
135 print_generic_expr (debug, var2, TDF_SLIM);
136 fprintf (debug, "(P%d)", p2);
139 gcc_assert (p1 != NO_PARTITION);
140 gcc_assert (p2 != NO_PARTITION);
142 rep1 = partition_to_var (map, p1);
143 rep2 = partition_to_var (map, p2);
144 root1 = SSA_NAME_VAR (rep1);
145 root2 = SSA_NAME_VAR (rep2);
147 if (p1 == p2)
149 if (debug)
150 fprintf (debug, " : Already coalesced.\n");
151 return false;
154 /* Don't coalesce if one of the variables occurs in an abnormal PHI. */
155 abnorm = (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep1)
156 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep2));
157 if (abnorm)
159 if (debug)
160 fprintf (debug, " : Abnormal PHI barrier. No coalesce.\n");
161 return false;
164 /* Partitions already have the same root, simply merge them. */
165 if (root1 == root2)
167 p1 = partition_union (map->var_partition, p1, p2);
168 if (debug)
169 fprintf (debug, " : Same root, coalesced --> P%d.\n", p1);
170 return false;
173 /* Never attempt to coalesce 2 difference parameters. */
174 if (TREE_CODE (root1) == PARM_DECL && TREE_CODE (root2) == PARM_DECL)
176 if (debug)
177 fprintf (debug, " : 2 different PARM_DECLS. No coalesce.\n");
178 return false;
181 if ((TREE_CODE (root1) == RESULT_DECL) != (TREE_CODE (root2) == RESULT_DECL))
183 if (debug)
184 fprintf (debug, " : One root a RESULT_DECL. No coalesce.\n");
185 return false;
188 ign1 = TREE_CODE (root1) == VAR_DECL && DECL_IGNORED_P (root1);
189 ign2 = TREE_CODE (root2) == VAR_DECL && DECL_IGNORED_P (root2);
191 /* Never attempt to coalesce 2 user variables unless one is an inline
192 variable. */
193 if (!ign1 && !ign2)
195 if (DECL_FROM_INLINE (root2))
196 ign2 = true;
197 else if (DECL_FROM_INLINE (root1))
198 ign1 = true;
199 else
201 if (debug)
202 fprintf (debug, " : 2 different USER vars. No coalesce.\n");
203 return false;
207 /* If both values have default defs, we can't coalesce. If only one has a
208 tag, make sure that variable is the new root partition. */
209 if (gimple_default_def (cfun, root1))
211 if (gimple_default_def (cfun, root2))
213 if (debug)
214 fprintf (debug, " : 2 default defs. No coalesce.\n");
215 return false;
217 else
219 ign2 = true;
220 ign1 = false;
223 else if (gimple_default_def (cfun, root2))
225 ign1 = true;
226 ign2 = false;
229 /* Don't coalesce if the two variables are not of the same type. */
230 if (TREE_TYPE (root1) != TREE_TYPE (root2))
232 if (debug)
233 fprintf (debug, " : Different types. No coalesce.\n");
234 return false;
237 /* Merge the two partitions. */
238 p3 = partition_union (map->var_partition, p1, p2);
240 /* Set the root variable of the partition to the better choice, if there is
241 one. */
242 if (!ign2)
243 replace_ssa_name_symbol (partition_to_var (map, p3), root2);
244 else if (!ign1)
245 replace_ssa_name_symbol (partition_to_var (map, p3), root1);
247 if (debug)
249 fprintf (debug, " --> P%d ", p3);
250 print_generic_expr (debug, SSA_NAME_VAR (partition_to_var (map, p3)),
251 TDF_SLIM);
252 fprintf (debug, "\n");
254 return true;
258 /* This function will make a pass through the IL, and attempt to coalesce any
259 SSA versions which occur in PHI's or copies. Coalescing is accomplished by
260 changing the underlying root variable of all coalesced version. This will
261 then cause the SSA->normal pass to attempt to coalesce them all to the same
262 variable. */
264 static unsigned int
265 rename_ssa_copies (void)
267 var_map map;
268 basic_block bb;
269 gimple_stmt_iterator gsi;
270 tree var, part_var;
271 gimple stmt, phi;
272 unsigned x;
273 FILE *debug;
274 bool updated = false;
276 if (dump_file && (dump_flags & TDF_DETAILS))
277 debug = dump_file;
278 else
279 debug = NULL;
281 map = init_var_map (num_ssa_names);
283 FOR_EACH_BB (bb)
285 /* Scan for real copies. */
286 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
288 stmt = gsi_stmt (gsi);
289 if (gimple_assign_ssa_name_copy_p (stmt))
291 tree lhs = gimple_assign_lhs (stmt);
292 tree rhs = gimple_assign_rhs1 (stmt);
294 updated |= copy_rename_partition_coalesce (map, lhs, rhs, debug);
299 FOR_EACH_BB (bb)
301 /* Treat PHI nodes as copies between the result and each argument. */
302 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
304 size_t i;
305 tree res;
307 phi = gsi_stmt (gsi);
308 res = gimple_phi_result (phi);
310 /* Do not process virtual SSA_NAMES. */
311 if (!is_gimple_reg (SSA_NAME_VAR (res)))
312 continue;
314 for (i = 0; i < gimple_phi_num_args (phi); i++)
316 tree arg = gimple_phi_arg (phi, i)->def;
317 if (TREE_CODE (arg) == SSA_NAME)
318 updated |= copy_rename_partition_coalesce (map, res, arg, debug);
323 if (debug)
324 dump_var_map (debug, map);
326 /* Now one more pass to make all elements of a partition share the same
327 root variable. */
329 for (x = 1; x < num_ssa_names; x++)
331 part_var = partition_to_var (map, x);
332 if (!part_var)
333 continue;
334 var = ssa_name (x);
335 if (debug)
337 if (SSA_NAME_VAR (var) != SSA_NAME_VAR (part_var))
339 fprintf (debug, "Coalesced ");
340 print_generic_expr (debug, var, TDF_SLIM);
341 fprintf (debug, " to ");
342 print_generic_expr (debug, part_var, TDF_SLIM);
343 fprintf (debug, "\n");
346 replace_ssa_name_symbol (var, SSA_NAME_VAR (part_var));
349 delete_var_map (map);
350 return updated ? TODO_remove_unused_locals : 0;
353 /* Return true if copy rename is to be performed. */
355 static bool
356 gate_copyrename (void)
358 return flag_tree_copyrename != 0;
361 struct gimple_opt_pass pass_rename_ssa_copies =
364 GIMPLE_PASS,
365 "copyrename", /* name */
366 gate_copyrename, /* gate */
367 rename_ssa_copies, /* execute */
368 NULL, /* sub */
369 NULL, /* next */
370 0, /* static_pass_number */
371 TV_TREE_COPY_RENAME, /* tv_id */
372 PROP_cfg | PROP_ssa, /* properties_required */
373 0, /* properties_provided */
374 0, /* properties_destroyed */
375 0, /* todo_flags_start */
376 TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */