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)
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, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
24 #include "coretypes.h"
28 #include "basic-block.h"
30 #include "diagnostic.h"
32 #include "tree-flow.h"
33 #include "tree-gimple.h"
34 #include "tree-inline.h"
36 #include "tree-alias-common.h"
38 #include "tree-dump.h"
39 #include "tree-ssa-live.h"
40 #include "tree-pass.h"
41 #include "langhooks.h"
43 extern void rename_ssa_copies (void);
45 /* The following routines implement the SSA copy renaming phase.
47 This optimization looks for copies between 2 SSA_NAMES, either through a
48 direct copy, or an implicit one via a PHI node result and its arguments.
50 Each copy is examined to determine if it is possible to rename the base
51 variable of one of the operands to the same variable as the other operand.
56 If this copy couldn't be copy propagated, it could possibly remain in the
57 program throughout the optimization phases. After SSA->normal, it would
63 Since T.3_5 is distinct from all other SSA versions of T.3, there is no
64 fundamental reason why the base variable needs to be T.3, subject to
65 certain restrictions. This optimization attempts to determine if we can
66 change the base variable on copies like this, and result in code such as:
71 This gives the SSA->normal pass a shot at coalescing a_1 and a_5. If it is
72 possible, the copy goes away completely. If it isn't possible, a new temp
73 will be created for a_5, and you will end up with the exact same code:
78 The other benefit of performing this optimization relates to what variables
79 are chosen in copies. Gimplification of the program uses temporaries for
80 a lot of things. expressions like
91 Copy propagation is done in a forward direction, and if we can propagate
92 through the copy, we end up with:
97 The copy is gone, but so is all reference to the user variable 'a'. By
98 performing this optimization, we would see the sequence:
104 which copy propagation would then turn into:
109 and so we still retain the user variable whenever possible. */
112 /* Coalesce the partitions in MAP representing VAR1 and VAR2 if it is valid.
113 Choose a representative for the partition, and send debug info to DEBUG. */
116 copy_rename_partition_coalesce (var_map map, tree var1, tree var2, FILE *debug)
120 var_ann_t ann1, ann2, ann3;
123 gcc_assert (TREE_CODE (var1) == SSA_NAME);
124 gcc_assert (TREE_CODE (var2) == SSA_NAME);
126 register_ssa_partition (map, var1, false);
127 register_ssa_partition (map, var2, true);
129 p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1));
130 p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2));
134 fprintf (debug, "Try : ");
135 print_generic_expr (debug, var1, TDF_SLIM);
136 fprintf (debug, "(P%d) & ", p1);
137 print_generic_expr (debug, var2, TDF_SLIM);
138 fprintf (debug, "(P%d)", p2);
141 gcc_assert (p1 != NO_PARTITION);
142 gcc_assert (p2 != NO_PARTITION);
144 root1 = SSA_NAME_VAR (partition_to_var (map, p1));
145 root2 = SSA_NAME_VAR (partition_to_var (map, p2));
147 if (DECL_HARD_REGISTER (root1) || DECL_HARD_REGISTER (root2))
151 if (DECL_HARD_REGISTER (root1))
152 print_generic_expr (debug, var1, TDF_SLIM);
154 print_generic_expr (debug, var2, TDF_SLIM);
155 fprintf (debug, " is a hardware register. No Coalescing.\n");
160 ann1 = var_ann (root1);
161 ann2 = var_ann (root2);
166 fprintf (debug, " : Already coalesced.\n");
170 /* Partitions already have the same root, simply merge them. */
173 p1 = partition_union (map->var_partition, p1, p2);
175 fprintf (debug, " : Same root, coalesced --> P%d.\n", p1);
179 /* Never attempt to coalesce 2 difference parameters. */
180 if (TREE_CODE (root1) == PARM_DECL && TREE_CODE (root2) == PARM_DECL)
183 fprintf (debug, " : 2 different PARM_DECLS. No coalesce.\n");
187 if ((TREE_CODE (root1) == RESULT_DECL) != (TREE_CODE (root2) == RESULT_DECL))
190 fprintf (debug, " : One root a RESULT_DECL. No coalesce.\n");
194 ign1 = TREE_CODE (root1) == VAR_DECL && DECL_IGNORED_P (root1);
195 ign2 = TREE_CODE (root2) == VAR_DECL && DECL_IGNORED_P (root2);
197 /* Never attempt to coalesce 2 user variables unless one is an inline
201 if (DECL_FROM_INLINE (root2))
203 else if (DECL_FROM_INLINE (root1))
208 fprintf (debug, " : 2 different USER vars. No coalesce.\n");
213 /* Don't coalesce if there are two different memory tags. */
214 if (ann1->type_mem_tag && ann2->type_mem_tag
215 && ann1->type_mem_tag != ann2->type_mem_tag)
218 fprintf (debug, " : 2 memory tags. No coalesce.\n");
222 /* If both values have default defs, we can't coalesce. If only one has a
223 tag, make sure that variable is the new root partition. */
224 if (default_def (root1))
226 if (default_def (root2))
229 fprintf (debug, " : 2 default defs. No coalesce.\n");
238 else if (default_def (root2))
244 /* Don't coalesce if the two variables aren't type compatible. */
245 if (!lang_hooks.types_compatible_p (TREE_TYPE (root1), TREE_TYPE (root2)))
248 fprintf (debug, " : Incompatible types. No coalesce.\n");
252 /* Merge the two partitions. */
253 p3 = partition_union (map->var_partition, p1, p2);
255 /* Set the root variable of the partition to the better choice, if there is
258 replace_ssa_name_symbol (partition_to_var (map, p3), root2);
260 replace_ssa_name_symbol (partition_to_var (map, p3), root1);
262 /* Update the various flag widgitry of the current base representative. */
263 ann3 = var_ann (SSA_NAME_VAR (partition_to_var (map, p3)));
264 if (ann1->type_mem_tag)
265 ann3->type_mem_tag = ann1->type_mem_tag;
267 ann3->type_mem_tag = ann2->type_mem_tag;
271 fprintf (debug, " --> P%d ", p3);
272 print_generic_expr (debug, SSA_NAME_VAR (partition_to_var (map, p3)),
274 fprintf (debug, "\n");
279 /* This function will make a pass through the IL, and attempt to coalesce any
280 SSA versions which occur in PHI's or copies. Coalescing is accomplished by
281 changing the underlying root variable of all coalesced version. This will
282 then cause the SSA->normal pass to attempt to coalesce them all to the same
286 rename_ssa_copies (void)
290 block_stmt_iterator bsi;
291 tree phi, stmt, var, part_var;
295 if (dump_file && (dump_flags & TDF_DETAILS))
300 map = init_var_map (num_ssa_names + 1);
304 /* Scan for real copies. */
305 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
307 stmt = bsi_stmt (bsi);
308 if (TREE_CODE (stmt) == MODIFY_EXPR)
310 tree lhs = TREE_OPERAND (stmt, 0);
311 tree rhs = TREE_OPERAND (stmt, 1);
313 if (TREE_CODE (lhs) == SSA_NAME && TREE_CODE (rhs) == SSA_NAME)
314 copy_rename_partition_coalesce (map, lhs, rhs, debug);
321 /* Treat PHI nodes as copies between the result and each argument. */
322 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
325 tree res = PHI_RESULT (phi);
327 /* Do not process virtual SSA_NAMES. */
328 if (!is_gimple_reg (SSA_NAME_VAR (res)))
331 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
333 tree arg = PHI_ARG_DEF (phi, i);
334 if (TREE_CODE (arg) == SSA_NAME)
335 copy_rename_partition_coalesce (map, res, arg, debug);
341 dump_var_map (debug, map);
343 /* Now one more pass to make all elements of a partition share the same
346 for (x = 1; x <= num_ssa_names; x++)
348 part_var = partition_to_var (map, x);
351 var = map->partition_to_var[x];
354 if (SSA_NAME_VAR (var) != SSA_NAME_VAR (part_var))
356 fprintf (debug, "Coalesced ");
357 print_generic_expr (debug, var, TDF_SLIM);
358 fprintf (debug, " to ");
359 print_generic_expr (debug, part_var, TDF_SLIM);
360 fprintf (debug, "\n");
363 replace_ssa_name_symbol (var, SSA_NAME_VAR (part_var));
366 delete_var_map (map);
369 /* Return true if copy rename is to be performed. */
372 gate_copyrename (void)
374 return flag_tree_copyrename != 0;
377 struct tree_opt_pass pass_rename_ssa_copies =
379 "copyrename", /* name */
380 gate_copyrename, /* gate */
381 rename_ssa_copies, /* execute */
384 0, /* static_pass_number */
385 TV_TREE_COPY_RENAME, /* tv_id */
386 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
387 0, /* properties_provided */
388 0, /* properties_destroyed */
389 0, /* todo_flags_start */
390 TODO_dump_func | TODO_verify_ssa, /* todo_flags_finish */