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)
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/>. */
24 #include "coretypes.h"
29 #include "basic-block.h"
31 #include "tree-pretty-print.h"
33 #include "tree-flow.h"
35 #include "tree-inline.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.
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
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:
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:
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
89 Copy propagation is done in a forward direction, and if we can propagate
90 through the copy, we end up with:
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:
102 which copy propagation would then turn into:
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. */
114 copy_rename_partition_coalesce (var_map map, tree var1, tree var2, FILE *debug)
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));
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);
150 fprintf (debug, " : Already coalesced.\n");
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));
160 fprintf (debug, " : Abnormal PHI barrier. No coalesce.\n");
164 /* Partitions already have the same root, simply merge them. */
167 p1 = partition_union (map->var_partition, p1, p2);
169 fprintf (debug, " : Same root, coalesced --> P%d.\n", p1);
173 /* Never attempt to coalesce 2 difference parameters. */
174 if (TREE_CODE (root1) == PARM_DECL && TREE_CODE (root2) == PARM_DECL)
177 fprintf (debug, " : 2 different PARM_DECLS. No coalesce.\n");
181 if ((TREE_CODE (root1) == RESULT_DECL) != (TREE_CODE (root2) == RESULT_DECL))
184 fprintf (debug, " : One root a RESULT_DECL. No coalesce.\n");
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
195 if (DECL_FROM_INLINE (root2))
197 else if (DECL_FROM_INLINE (root1))
202 fprintf (debug, " : 2 different USER vars. No coalesce.\n");
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))
214 fprintf (debug, " : 2 default defs. No coalesce.\n");
223 else if (gimple_default_def (cfun, root2))
229 /* Don't coalesce if the two variables aren't type compatible . */
230 if (!types_compatible_p (TREE_TYPE (root1), TREE_TYPE (root2))
231 /* There is a disconnect between the middle-end type-system and
232 VRP, avoid coalescing enum types with different bounds. */
233 || ((TREE_CODE (TREE_TYPE (root1)) == ENUMERAL_TYPE
234 || TREE_CODE (TREE_TYPE (root2)) == ENUMERAL_TYPE)
235 && TREE_TYPE (root1) != TREE_TYPE (root2)))
238 fprintf (debug, " : Incompatible types. No coalesce.\n");
242 /* Merge the two partitions. */
243 p3 = partition_union (map->var_partition, p1, p2);
245 /* Set the root variable of the partition to the better choice, if there is
248 replace_ssa_name_symbol (partition_to_var (map, p3), root2);
250 replace_ssa_name_symbol (partition_to_var (map, p3), root1);
254 fprintf (debug, " --> P%d ", p3);
255 print_generic_expr (debug, SSA_NAME_VAR (partition_to_var (map, p3)),
257 fprintf (debug, "\n");
263 /* This function will make a pass through the IL, and attempt to coalesce any
264 SSA versions which occur in PHI's or copies. Coalescing is accomplished by
265 changing the underlying root variable of all coalesced version. This will
266 then cause the SSA->normal pass to attempt to coalesce them all to the same
270 rename_ssa_copies (void)
274 gimple_stmt_iterator gsi;
279 bool updated = false;
281 if (dump_file && (dump_flags & TDF_DETAILS))
286 map = init_var_map (num_ssa_names);
290 /* Scan for real copies. */
291 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
293 stmt = gsi_stmt (gsi);
294 if (gimple_assign_ssa_name_copy_p (stmt))
296 tree lhs = gimple_assign_lhs (stmt);
297 tree rhs = gimple_assign_rhs1 (stmt);
299 updated |= copy_rename_partition_coalesce (map, lhs, rhs, debug);
306 /* Treat PHI nodes as copies between the result and each argument. */
307 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
312 phi = gsi_stmt (gsi);
313 res = gimple_phi_result (phi);
315 /* Do not process virtual SSA_NAMES. */
316 if (!is_gimple_reg (SSA_NAME_VAR (res)))
319 for (i = 0; i < gimple_phi_num_args (phi); i++)
321 tree arg = gimple_phi_arg (phi, i)->def;
322 if (TREE_CODE (arg) == SSA_NAME)
323 updated |= copy_rename_partition_coalesce (map, res, arg, debug);
329 dump_var_map (debug, map);
331 /* Now one more pass to make all elements of a partition share the same
334 for (x = 1; x < num_ssa_names; x++)
336 part_var = partition_to_var (map, x);
342 if (SSA_NAME_VAR (var) != SSA_NAME_VAR (part_var))
344 fprintf (debug, "Coalesced ");
345 print_generic_expr (debug, var, TDF_SLIM);
346 fprintf (debug, " to ");
347 print_generic_expr (debug, part_var, TDF_SLIM);
348 fprintf (debug, "\n");
351 replace_ssa_name_symbol (var, SSA_NAME_VAR (part_var));
354 delete_var_map (map);
355 return updated ? TODO_remove_unused_locals : 0;
358 /* Return true if copy rename is to be performed. */
361 gate_copyrename (void)
363 return flag_tree_copyrename != 0;
366 struct gimple_opt_pass pass_rename_ssa_copies =
370 "copyrename", /* name */
371 gate_copyrename, /* gate */
372 rename_ssa_copies, /* execute */
375 0, /* static_pass_number */
376 TV_TREE_COPY_RENAME, /* tv_id */
377 PROP_cfg | PROP_ssa, /* properties_required */
378 0, /* properties_provided */
379 0, /* properties_destroyed */
380 0, /* todo_flags_start */
381 TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */