Daily bump.
[official-gcc.git] / gcc / tree-ssa-copyrename.c
blobe06de4caaf6894ccf55088241ea1f070ed60be70
1 /* Rename SSA copies.
2 Copyright (C) 2004 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 2, 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 COPYING. If not, write to
19 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
20 Boston, MA 02110-1301, USA. */
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "tree.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 "tree-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 var_ann_t ann1, ann2, ann3;
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 ann1 = var_ann (root1);
148 ann2 = var_ann (root2);
150 if (p1 == p2)
152 if (debug)
153 fprintf (debug, " : Already coalesced.\n");
154 return false;
157 /* Don't coalesce if one of the variables occurs in an abnormal PHI. */
158 abnorm = (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep1)
159 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep2));
160 if (abnorm)
162 if (debug)
163 fprintf (debug, " : Abnormal PHI barrier. No coalesce.\n");
164 return false;
167 /* Partitions already have the same root, simply merge them. */
168 if (root1 == root2)
170 p1 = partition_union (map->var_partition, p1, p2);
171 if (debug)
172 fprintf (debug, " : Same root, coalesced --> P%d.\n", p1);
173 return false;
176 /* Never attempt to coalesce 2 difference parameters. */
177 if (TREE_CODE (root1) == PARM_DECL && TREE_CODE (root2) == PARM_DECL)
179 if (debug)
180 fprintf (debug, " : 2 different PARM_DECLS. No coalesce.\n");
181 return false;
184 if ((TREE_CODE (root1) == RESULT_DECL) != (TREE_CODE (root2) == RESULT_DECL))
186 if (debug)
187 fprintf (debug, " : One root a RESULT_DECL. No coalesce.\n");
188 return false;
191 ign1 = TREE_CODE (root1) == VAR_DECL && DECL_IGNORED_P (root1);
192 ign2 = TREE_CODE (root2) == VAR_DECL && DECL_IGNORED_P (root2);
194 /* Never attempt to coalesce 2 user variables unless one is an inline
195 variable. */
196 if (!ign1 && !ign2)
198 if (DECL_FROM_INLINE (root2))
199 ign2 = true;
200 else if (DECL_FROM_INLINE (root1))
201 ign1 = true;
202 else
204 if (debug)
205 fprintf (debug, " : 2 different USER vars. No coalesce.\n");
206 return false;
210 /* Don't coalesce if there are two different memory tags. */
211 if (ann1->symbol_mem_tag
212 && ann2->symbol_mem_tag
213 && ann1->symbol_mem_tag != ann2->symbol_mem_tag)
215 if (debug)
216 fprintf (debug, " : 2 memory tags. No coalesce.\n");
217 return false;
220 /* If both values have default defs, we can't coalesce. If only one has a
221 tag, make sure that variable is the new root partition. */
222 if (gimple_default_def (cfun, root1))
224 if (gimple_default_def (cfun, root2))
226 if (debug)
227 fprintf (debug, " : 2 default defs. No coalesce.\n");
228 return false;
230 else
232 ign2 = true;
233 ign1 = false;
236 else if (gimple_default_def (cfun, root2))
238 ign1 = true;
239 ign2 = false;
242 /* Don't coalesce if the two variables aren't type compatible. */
243 if (!lang_hooks.types_compatible_p (TREE_TYPE (root1), TREE_TYPE (root2)))
245 if (debug)
246 fprintf (debug, " : Incompatible types. No coalesce.\n");
247 return false;
250 /* Don't coalesce if the aliasing sets of the types are different. */
251 if (POINTER_TYPE_P (TREE_TYPE (root1))
252 && POINTER_TYPE_P (TREE_TYPE (root2))
253 && get_alias_set (TREE_TYPE (TREE_TYPE (root1)))
254 != get_alias_set (TREE_TYPE (TREE_TYPE (root2))))
256 if (debug)
257 fprintf (debug, " : 2 different aliasing sets. No coalesce.\n");
258 return false;
262 /* Merge the two partitions. */
263 p3 = partition_union (map->var_partition, p1, p2);
265 /* Set the root variable of the partition to the better choice, if there is
266 one. */
267 if (!ign2)
268 replace_ssa_name_symbol (partition_to_var (map, p3), root2);
269 else if (!ign1)
270 replace_ssa_name_symbol (partition_to_var (map, p3), root1);
272 /* Update the various flag widgitry of the current base representative. */
273 ann3 = var_ann (SSA_NAME_VAR (partition_to_var (map, p3)));
274 if (ann1->symbol_mem_tag)
275 ann3->symbol_mem_tag = ann1->symbol_mem_tag;
276 else
277 ann3->symbol_mem_tag = ann2->symbol_mem_tag;
279 if (debug)
281 fprintf (debug, " --> P%d ", p3);
282 print_generic_expr (debug, SSA_NAME_VAR (partition_to_var (map, p3)),
283 TDF_SLIM);
284 fprintf (debug, "\n");
286 return true;
290 /* This function will make a pass through the IL, and attempt to coalesce any
291 SSA versions which occur in PHI's or copies. Coalescing is accomplished by
292 changing the underlying root variable of all coalesced version. This will
293 then cause the SSA->normal pass to attempt to coalesce them all to the same
294 variable. */
296 static unsigned int
297 rename_ssa_copies (void)
299 var_map map;
300 basic_block bb;
301 block_stmt_iterator bsi;
302 tree phi, stmt, var, part_var;
303 unsigned x;
304 FILE *debug;
305 bool updated = false;
307 if (dump_file && (dump_flags & TDF_DETAILS))
308 debug = dump_file;
309 else
310 debug = NULL;
312 map = init_var_map (num_ssa_names + 1);
314 FOR_EACH_BB (bb)
316 /* Scan for real copies. */
317 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
319 stmt = bsi_stmt (bsi);
320 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
322 tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
323 tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
325 if (TREE_CODE (lhs) == SSA_NAME && TREE_CODE (rhs) == SSA_NAME)
326 updated |= copy_rename_partition_coalesce (map, lhs, rhs, debug);
331 FOR_EACH_BB (bb)
333 /* Treat PHI nodes as copies between the result and each argument. */
334 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
336 int i;
337 tree res = PHI_RESULT (phi);
339 /* Do not process virtual SSA_NAMES. */
340 if (!is_gimple_reg (SSA_NAME_VAR (res)))
341 continue;
343 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
345 tree arg = PHI_ARG_DEF (phi, i);
346 if (TREE_CODE (arg) == SSA_NAME)
347 updated |= copy_rename_partition_coalesce (map, res, arg, debug);
352 if (debug)
353 dump_var_map (debug, map);
355 /* Now one more pass to make all elements of a partition share the same
356 root variable. */
358 for (x = 1; x <= num_ssa_names; x++)
360 part_var = partition_to_var (map, x);
361 if (!part_var)
362 continue;
363 var = map->partition_to_var[x];
364 if (debug)
366 if (SSA_NAME_VAR (var) != SSA_NAME_VAR (part_var))
368 fprintf (debug, "Coalesced ");
369 print_generic_expr (debug, var, TDF_SLIM);
370 fprintf (debug, " to ");
371 print_generic_expr (debug, part_var, TDF_SLIM);
372 fprintf (debug, "\n");
375 replace_ssa_name_symbol (var, SSA_NAME_VAR (part_var));
378 delete_var_map (map);
379 return updated ? TODO_remove_unused_locals : 0;
382 /* Return true if copy rename is to be performed. */
384 static bool
385 gate_copyrename (void)
387 return flag_tree_copyrename != 0;
390 struct tree_opt_pass pass_rename_ssa_copies =
392 "copyrename", /* name */
393 gate_copyrename, /* gate */
394 rename_ssa_copies, /* execute */
395 NULL, /* sub */
396 NULL, /* next */
397 0, /* static_pass_number */
398 TV_TREE_COPY_RENAME, /* tv_id */
399 PROP_cfg | PROP_ssa, /* properties_required */
400 0, /* properties_provided */
401 0, /* properties_destroyed */
402 0, /* todo_flags_start */
403 TODO_dump_func | TODO_verify_ssa, /* todo_flags_finish */
404 0 /* letter */