2 Copyright (C) 2004, 2006, 2007, 2008, 2009, 2010, 2011
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"
37 #include "tree-ssa-live.h"
38 #include "tree-pass.h"
39 #include "langhooks.h"
43 /* Number of copies coalesced. */
47 /* The following routines implement the SSA copy renaming phase.
49 This optimization looks for copies between 2 SSA_NAMES, either through a
50 direct copy, or an implicit one via a PHI node result and its arguments.
52 Each copy is examined to determine if it is possible to rename the base
53 variable of one of the operands to the same variable as the other operand.
58 If this copy couldn't be copy propagated, it could possibly remain in the
59 program throughout the optimization phases. After SSA->normal, it would
65 Since T.3_5 is distinct from all other SSA versions of T.3, there is no
66 fundamental reason why the base variable needs to be T.3, subject to
67 certain restrictions. This optimization attempts to determine if we can
68 change the base variable on copies like this, and result in code such as:
73 This gives the SSA->normal pass a shot at coalescing a_1 and a_5. If it is
74 possible, the copy goes away completely. If it isn't possible, a new temp
75 will be created for a_5, and you will end up with the exact same code:
80 The other benefit of performing this optimization relates to what variables
81 are chosen in copies. Gimplification of the program uses temporaries for
82 a lot of things. expressions like
93 Copy propagation is done in a forward direction, and if we can propagate
94 through the copy, we end up with:
99 The copy is gone, but so is all reference to the user variable 'a'. By
100 performing this optimization, we would see the sequence:
106 which copy propagation would then turn into:
111 and so we still retain the user variable whenever possible. */
114 /* Coalesce the partitions in MAP representing VAR1 and VAR2 if it is valid.
115 Choose a representative for the partition, and send debug info to DEBUG. */
118 copy_rename_partition_coalesce (var_map map
, tree var1
, tree var2
, FILE *debug
)
123 bool ign1
, ign2
, abnorm
;
125 gcc_assert (TREE_CODE (var1
) == SSA_NAME
);
126 gcc_assert (TREE_CODE (var2
) == SSA_NAME
);
128 register_ssa_partition (map
, var1
);
129 register_ssa_partition (map
, var2
);
131 p1
= partition_find (map
->var_partition
, SSA_NAME_VERSION (var1
));
132 p2
= partition_find (map
->var_partition
, SSA_NAME_VERSION (var2
));
136 fprintf (debug
, "Try : ");
137 print_generic_expr (debug
, var1
, TDF_SLIM
);
138 fprintf (debug
, "(P%d) & ", p1
);
139 print_generic_expr (debug
, var2
, TDF_SLIM
);
140 fprintf (debug
, "(P%d)", p2
);
143 gcc_assert (p1
!= NO_PARTITION
);
144 gcc_assert (p2
!= NO_PARTITION
);
146 rep1
= partition_to_var (map
, p1
);
147 rep2
= partition_to_var (map
, p2
);
148 root1
= SSA_NAME_VAR (rep1
);
149 root2
= SSA_NAME_VAR (rep2
);
154 fprintf (debug
, " : Already coalesced.\n");
158 /* Don't coalesce if one of the variables occurs in an abnormal PHI. */
159 abnorm
= (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep1
)
160 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep2
));
164 fprintf (debug
, " : Abnormal PHI barrier. No coalesce.\n");
168 /* Partitions already have the same root, simply merge them. */
171 p1
= partition_union (map
->var_partition
, p1
, p2
);
173 fprintf (debug
, " : Same root, coalesced --> P%d.\n", p1
);
177 /* Never attempt to coalesce 2 different parameters. */
178 if (TREE_CODE (root1
) == PARM_DECL
&& TREE_CODE (root2
) == PARM_DECL
)
181 fprintf (debug
, " : 2 different PARM_DECLS. No coalesce.\n");
185 if ((TREE_CODE (root1
) == RESULT_DECL
) != (TREE_CODE (root2
) == RESULT_DECL
))
188 fprintf (debug
, " : One root a RESULT_DECL. No coalesce.\n");
192 ign1
= TREE_CODE (root1
) == VAR_DECL
&& DECL_IGNORED_P (root1
);
193 ign2
= TREE_CODE (root2
) == VAR_DECL
&& DECL_IGNORED_P (root2
);
195 /* Refrain from coalescing user variables, if requested. */
198 if (flag_ssa_coalesce_vars
&& DECL_FROM_INLINE (root2
))
200 else if (flag_ssa_coalesce_vars
&& DECL_FROM_INLINE (root1
))
202 else if (flag_ssa_coalesce_vars
!= 2)
205 fprintf (debug
, " : 2 different USER vars. No coalesce.\n");
212 /* If both values have default defs, we can't coalesce. If only one has a
213 tag, make sure that variable is the new root partition. */
214 if (gimple_default_def (cfun
, root1
))
216 if (gimple_default_def (cfun
, root2
))
219 fprintf (debug
, " : 2 default defs. No coalesce.\n");
228 else if (gimple_default_def (cfun
, root2
))
234 /* Don't coalesce if the new chosen root variable would be read-only.
235 If both ign1 && ign2, then the root var of the larger partition
236 wins, so reject in that case if any of the root vars is TREE_READONLY.
237 Otherwise reject only if the root var, on which replace_ssa_name_symbol
238 will be called below, is readonly. */
239 if ((TREE_READONLY (root1
) && ign2
) || (TREE_READONLY (root2
) && ign1
))
242 fprintf (debug
, " : Readonly variable. No coalesce.\n");
246 /* Don't coalesce if the two variables aren't type compatible . */
247 if (!types_compatible_p (TREE_TYPE (root1
), TREE_TYPE (root2
))
248 /* There is a disconnect between the middle-end type-system and
249 VRP, avoid coalescing enum types with different bounds. */
250 || ((TREE_CODE (TREE_TYPE (root1
)) == ENUMERAL_TYPE
251 || TREE_CODE (TREE_TYPE (root2
)) == ENUMERAL_TYPE
)
252 && TREE_TYPE (root1
) != TREE_TYPE (root2
)))
255 fprintf (debug
, " : Incompatible types. No coalesce.\n");
259 /* Merge the two partitions. */
260 p3
= partition_union (map
->var_partition
, p1
, p2
);
262 /* Set the root variable of the partition to the better choice, if there is
265 replace_ssa_name_symbol (partition_to_var (map
, p3
), root2
);
267 replace_ssa_name_symbol (partition_to_var (map
, p3
), root1
);
271 fprintf (debug
, " --> P%d ", p3
);
272 print_generic_expr (debug
, SSA_NAME_VAR (partition_to_var (map
, p3
)),
274 fprintf (debug
, "\n");
280 /* This function will make a pass through the IL, and attempt to coalesce any
281 SSA versions which occur in PHI's or copies. Coalescing is accomplished by
282 changing the underlying root variable of all coalesced version. This will
283 then cause the SSA->normal pass to attempt to coalesce them all to the same
287 rename_ssa_copies (void)
291 gimple_stmt_iterator gsi
;
296 bool updated
= false;
298 memset (&stats
, 0, sizeof (stats
));
300 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
305 map
= init_var_map (num_ssa_names
);
309 /* Scan for real copies. */
310 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
312 stmt
= gsi_stmt (gsi
);
313 if (gimple_assign_ssa_name_copy_p (stmt
))
315 tree lhs
= gimple_assign_lhs (stmt
);
316 tree rhs
= gimple_assign_rhs1 (stmt
);
318 updated
|= copy_rename_partition_coalesce (map
, lhs
, rhs
, debug
);
325 /* Treat PHI nodes as copies between the result and each argument. */
326 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
331 phi
= gsi_stmt (gsi
);
332 res
= gimple_phi_result (phi
);
334 /* Do not process virtual SSA_NAMES. */
335 if (!is_gimple_reg (SSA_NAME_VAR (res
)))
338 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
340 tree arg
= gimple_phi_arg (phi
, i
)->def
;
341 if (TREE_CODE (arg
) == SSA_NAME
)
342 updated
|= copy_rename_partition_coalesce (map
, res
, arg
, debug
);
348 dump_var_map (debug
, map
);
350 /* Now one more pass to make all elements of a partition share the same
353 for (x
= 1; x
< num_ssa_names
; x
++)
355 part_var
= partition_to_var (map
, x
);
359 if (SSA_NAME_VAR (var
) == SSA_NAME_VAR (part_var
))
363 fprintf (debug
, "Coalesced ");
364 print_generic_expr (debug
, var
, TDF_SLIM
);
365 fprintf (debug
, " to ");
366 print_generic_expr (debug
, part_var
, TDF_SLIM
);
367 fprintf (debug
, "\n");
370 replace_ssa_name_symbol (var
, SSA_NAME_VAR (part_var
));
373 statistics_counter_event (cfun
, "copies coalesced",
375 delete_var_map (map
);
376 return updated
? TODO_remove_unused_locals
: 0;
379 /* Return true if copy rename is to be performed. */
382 gate_copyrename (void)
384 return flag_tree_copyrename
!= 0;
387 struct gimple_opt_pass pass_rename_ssa_copies
=
391 "copyrename", /* name */
392 gate_copyrename
, /* gate */
393 rename_ssa_copies
, /* execute */
396 0, /* static_pass_number */
397 TV_TREE_COPY_RENAME
, /* tv_id */
398 PROP_cfg
| PROP_ssa
, /* properties_required */
399 0, /* properties_provided */
400 0, /* properties_destroyed */
401 0, /* todo_flags_start */
402 TODO_verify_ssa
/* todo_flags_finish */