Daily bump.
[official-gcc.git] / gcc / tree-ssa-copyrename.c
blob46b33143cb025f34528e41919b89b6e59dae9807
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 "flags.h"
27 #include "basic-block.h"
28 #include "function.h"
29 #include "diagnostic.h"
30 #include "bitmap.h"
31 #include "tree-flow.h"
32 #include "tree-gimple.h"
33 #include "tree-inline.h"
34 #include "timevar.h"
35 #include "hashtab.h"
36 #include "tree-dump.h"
37 #include "tree-ssa-live.h"
38 #include "tree-pass.h"
39 #include "langhooks.h"
41 /* The following routines implement the SSA copy renaming phase.
43 This optimization looks for copies between 2 SSA_NAMES, either through a
44 direct copy, or an implicit one via a PHI node result and its arguments.
46 Each copy is examined to determine if it is possible to rename the base
47 variable of one of the operands to the same variable as the other operand.
48 i.e.
49 T.3_5 = <blah>
50 a_1 = T.3_5
52 If this copy couldn't be copy propagated, it could possibly remain in the
53 program throughout the optimization phases. After SSA->normal, it would
54 become:
56 T.3 = <blah>
57 a = T.3
59 Since T.3_5 is distinct from all other SSA versions of T.3, there is no
60 fundamental reason why the base variable needs to be T.3, subject to
61 certain restrictions. This optimization attempts to determine if we can
62 change the base variable on copies like this, and result in code such as:
64 a_5 = <blah>
65 a_1 = a_5
67 This gives the SSA->normal pass a shot at coalescing a_1 and a_5. If it is
68 possible, the copy goes away completely. If it isn't possible, a new temp
69 will be created for a_5, and you will end up with the exact same code:
71 a.8 = <blah>
72 a = a.8
74 The other benefit of performing this optimization relates to what variables
75 are chosen in copies. Gimplification of the program uses temporaries for
76 a lot of things. expressions like
78 a_1 = <blah>
79 <blah2> = a_1
81 get turned into
83 T.3_5 = <blah>
84 a_1 = T.3_5
85 <blah2> = a_1
87 Copy propagation is done in a forward direction, and if we can propagate
88 through the copy, we end up with:
90 T.3_5 = <blah>
91 <blah2> = T.3_5
93 The copy is gone, but so is all reference to the user variable 'a'. By
94 performing this optimization, we would see the sequence:
96 a_5 = <blah>
97 a_1 = a_5
98 <blah2> = a_1
100 which copy propagation would then turn into:
102 a_5 = <blah>
103 <blah2> = a_5
105 and so we still retain the user variable whenever possible. */
108 /* Coalesce the partitions in MAP representing VAR1 and VAR2 if it is valid.
109 Choose a representative for the partition, and send debug info to DEBUG. */
111 static bool
112 copy_rename_partition_coalesce (var_map map, tree var1, tree var2, FILE *debug)
114 int p1, p2, p3;
115 tree root1, root2;
116 tree rep1, rep2;
117 var_ann_t ann1, ann2, ann3;
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 ann1 = var_ann (root1);
147 ann2 = var_ann (root2);
149 if (p1 == p2)
151 if (debug)
152 fprintf (debug, " : Already coalesced.\n");
153 return false;
156 /* Don't coalesce if one of the variables occurs in an abnormal PHI. */
157 abnorm = (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep1)
158 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep2));
159 if (abnorm)
161 if (debug)
162 fprintf (debug, " : Abnormal PHI barrier. No coalesce.\n");
163 return false;
166 /* Partitions already have the same root, simply merge them. */
167 if (root1 == root2)
169 p1 = partition_union (map->var_partition, p1, p2);
170 if (debug)
171 fprintf (debug, " : Same root, coalesced --> P%d.\n", p1);
172 return false;
175 /* Never attempt to coalesce 2 difference parameters. */
176 if (TREE_CODE (root1) == PARM_DECL && TREE_CODE (root2) == PARM_DECL)
178 if (debug)
179 fprintf (debug, " : 2 different PARM_DECLS. No coalesce.\n");
180 return false;
183 if ((TREE_CODE (root1) == RESULT_DECL) != (TREE_CODE (root2) == RESULT_DECL))
185 if (debug)
186 fprintf (debug, " : One root a RESULT_DECL. No coalesce.\n");
187 return false;
190 ign1 = TREE_CODE (root1) == VAR_DECL && DECL_IGNORED_P (root1);
191 ign2 = TREE_CODE (root2) == VAR_DECL && DECL_IGNORED_P (root2);
193 /* Never attempt to coalesce 2 user variables unless one is an inline
194 variable. */
195 if (!ign1 && !ign2)
197 if (DECL_FROM_INLINE (root2))
198 ign2 = true;
199 else if (DECL_FROM_INLINE (root1))
200 ign1 = true;
201 else
203 if (debug)
204 fprintf (debug, " : 2 different USER vars. No coalesce.\n");
205 return false;
209 /* Don't coalesce if there are two different memory tags. */
210 if (ann1->symbol_mem_tag
211 && ann2->symbol_mem_tag
212 && ann1->symbol_mem_tag != ann2->symbol_mem_tag)
214 if (debug)
215 fprintf (debug, " : 2 memory tags. No coalesce.\n");
216 return false;
219 /* If both values have default defs, we can't coalesce. If only one has a
220 tag, make sure that variable is the new root partition. */
221 if (gimple_default_def (cfun, root1))
223 if (gimple_default_def (cfun, root2))
225 if (debug)
226 fprintf (debug, " : 2 default defs. No coalesce.\n");
227 return false;
229 else
231 ign2 = true;
232 ign1 = false;
235 else if (gimple_default_def (cfun, root2))
237 ign1 = true;
238 ign2 = false;
241 /* Don't coalesce if the two variables aren't type compatible. */
242 if (!types_compatible_p (TREE_TYPE (root1), TREE_TYPE (root2)))
244 if (debug)
245 fprintf (debug, " : Incompatible types. No coalesce.\n");
246 return false;
249 /* Don't coalesce if the aliasing sets of the types are different. */
250 if (POINTER_TYPE_P (TREE_TYPE (root1))
251 && POINTER_TYPE_P (TREE_TYPE (root2))
252 && ((get_alias_set (TREE_TYPE (TREE_TYPE (root1)))
253 != get_alias_set (TREE_TYPE (TREE_TYPE (root2))))
254 || ((DECL_P (root1) && !MTAG_P (root1))
255 && (DECL_P (root2) && !MTAG_P (root2))
256 && DECL_NO_TBAA_P (root1) != DECL_NO_TBAA_P (root2))))
258 if (debug)
259 fprintf (debug, " : 2 different aliasing sets. No coalesce.\n");
260 return false;
264 /* Merge the two partitions. */
265 p3 = partition_union (map->var_partition, p1, p2);
267 /* Set the root variable of the partition to the better choice, if there is
268 one. */
269 if (!ign2)
270 replace_ssa_name_symbol (partition_to_var (map, p3), root2);
271 else if (!ign1)
272 replace_ssa_name_symbol (partition_to_var (map, p3), root1);
274 /* Update the various flag widgitry of the current base representative. */
275 ann3 = var_ann (SSA_NAME_VAR (partition_to_var (map, p3)));
276 if (ann1->symbol_mem_tag)
277 ann3->symbol_mem_tag = ann1->symbol_mem_tag;
278 else
279 ann3->symbol_mem_tag = ann2->symbol_mem_tag;
281 if (debug)
283 fprintf (debug, " --> P%d ", p3);
284 print_generic_expr (debug, SSA_NAME_VAR (partition_to_var (map, p3)),
285 TDF_SLIM);
286 fprintf (debug, "\n");
288 return true;
292 /* This function will make a pass through the IL, and attempt to coalesce any
293 SSA versions which occur in PHI's or copies. Coalescing is accomplished by
294 changing the underlying root variable of all coalesced version. This will
295 then cause the SSA->normal pass to attempt to coalesce them all to the same
296 variable. */
298 static unsigned int
299 rename_ssa_copies (void)
301 var_map map;
302 basic_block bb;
303 block_stmt_iterator bsi;
304 tree phi, stmt, var, part_var;
305 unsigned x;
306 FILE *debug;
307 bool updated = false;
309 if (dump_file && (dump_flags & TDF_DETAILS))
310 debug = dump_file;
311 else
312 debug = NULL;
314 map = init_var_map (num_ssa_names + 1);
316 FOR_EACH_BB (bb)
318 /* Scan for real copies. */
319 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
321 stmt = bsi_stmt (bsi);
322 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
324 tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
325 tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
327 if (TREE_CODE (lhs) == SSA_NAME && TREE_CODE (rhs) == SSA_NAME)
328 updated |= copy_rename_partition_coalesce (map, lhs, rhs, debug);
333 FOR_EACH_BB (bb)
335 /* Treat PHI nodes as copies between the result and each argument. */
336 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
338 int i;
339 tree res = PHI_RESULT (phi);
341 /* Do not process virtual SSA_NAMES. */
342 if (!is_gimple_reg (SSA_NAME_VAR (res)))
343 continue;
345 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
347 tree arg = PHI_ARG_DEF (phi, i);
348 if (TREE_CODE (arg) == SSA_NAME)
349 updated |= copy_rename_partition_coalesce (map, res, arg, debug);
354 if (debug)
355 dump_var_map (debug, map);
357 /* Now one more pass to make all elements of a partition share the same
358 root variable. */
360 for (x = 1; x <= num_ssa_names; x++)
362 part_var = partition_to_var (map, x);
363 if (!part_var)
364 continue;
365 var = map->partition_to_var[x];
366 if (debug)
368 if (SSA_NAME_VAR (var) != SSA_NAME_VAR (part_var))
370 fprintf (debug, "Coalesced ");
371 print_generic_expr (debug, var, TDF_SLIM);
372 fprintf (debug, " to ");
373 print_generic_expr (debug, part_var, TDF_SLIM);
374 fprintf (debug, "\n");
377 replace_ssa_name_symbol (var, SSA_NAME_VAR (part_var));
380 delete_var_map (map);
381 return updated ? TODO_remove_unused_locals : 0;
384 /* Return true if copy rename is to be performed. */
386 static bool
387 gate_copyrename (void)
389 return flag_tree_copyrename != 0;
392 struct gimple_opt_pass pass_rename_ssa_copies =
395 GIMPLE_PASS,
396 "copyrename", /* name */
397 gate_copyrename, /* gate */
398 rename_ssa_copies, /* execute */
399 NULL, /* sub */
400 NULL, /* next */
401 0, /* static_pass_number */
402 TV_TREE_COPY_RENAME, /* tv_id */
403 PROP_cfg | PROP_ssa, /* properties_required */
404 0, /* properties_provided */
405 0, /* properties_destroyed */
406 0, /* todo_flags_start */
407 TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */