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)
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/>. */
23 #include "coretypes.h"
28 #include "basic-block.h"
30 #include "diagnostic.h"
32 #include "tree-flow.h"
34 #include "tree-inline.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.
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
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:
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:
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
88 Copy propagation is done in a forward direction, and if we can propagate
89 through the copy, we end up with:
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:
101 which copy propagation would then turn into:
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. */
113 copy_rename_partition_coalesce (var_map map
, tree var1
, tree var2
, FILE *debug
)
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
));
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
);
149 fprintf (debug
, " : Already coalesced.\n");
153 /* Don't coalesce if one of the variables occurs in an abnormal PHI. */
154 abnorm
= (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep1
)
155 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep2
));
159 fprintf (debug
, " : Abnormal PHI barrier. No coalesce.\n");
163 /* Partitions already have the same root, simply merge them. */
166 p1
= partition_union (map
->var_partition
, p1
, p2
);
168 fprintf (debug
, " : Same root, coalesced --> P%d.\n", p1
);
172 /* Never attempt to coalesce 2 difference parameters. */
173 if (TREE_CODE (root1
) == PARM_DECL
&& TREE_CODE (root2
) == PARM_DECL
)
176 fprintf (debug
, " : 2 different PARM_DECLS. No coalesce.\n");
180 if ((TREE_CODE (root1
) == RESULT_DECL
) != (TREE_CODE (root2
) == RESULT_DECL
))
183 fprintf (debug
, " : One root a RESULT_DECL. No coalesce.\n");
187 ign1
= TREE_CODE (root1
) == VAR_DECL
&& DECL_IGNORED_P (root1
);
188 ign2
= TREE_CODE (root2
) == VAR_DECL
&& DECL_IGNORED_P (root2
);
190 /* Never attempt to coalesce 2 user variables unless one is an inline
194 if (DECL_FROM_INLINE (root2
))
196 else if (DECL_FROM_INLINE (root1
))
201 fprintf (debug
, " : 2 different USER vars. No coalesce.\n");
206 /* If both values have default defs, we can't coalesce. If only one has a
207 tag, make sure that variable is the new root partition. */
208 if (gimple_default_def (cfun
, root1
))
210 if (gimple_default_def (cfun
, root2
))
213 fprintf (debug
, " : 2 default defs. No coalesce.\n");
222 else if (gimple_default_def (cfun
, root2
))
228 /* Don't coalesce if the two variables aren't type compatible. */
229 if (!types_compatible_p (TREE_TYPE (root1
), TREE_TYPE (root2
)))
232 fprintf (debug
, " : Incompatible types. No coalesce.\n");
236 /* Merge the two partitions. */
237 p3
= partition_union (map
->var_partition
, p1
, p2
);
239 /* Set the root variable of the partition to the better choice, if there is
242 replace_ssa_name_symbol (partition_to_var (map
, p3
), root2
);
244 replace_ssa_name_symbol (partition_to_var (map
, p3
), root1
);
248 fprintf (debug
, " --> P%d ", p3
);
249 print_generic_expr (debug
, SSA_NAME_VAR (partition_to_var (map
, p3
)),
251 fprintf (debug
, "\n");
257 /* This function will make a pass through the IL, and attempt to coalesce any
258 SSA versions which occur in PHI's or copies. Coalescing is accomplished by
259 changing the underlying root variable of all coalesced version. This will
260 then cause the SSA->normal pass to attempt to coalesce them all to the same
264 rename_ssa_copies (void)
268 gimple_stmt_iterator gsi
;
273 bool updated
= false;
275 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
280 map
= init_var_map (num_ssa_names
);
284 /* Scan for real copies. */
285 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
287 stmt
= gsi_stmt (gsi
);
288 if (gimple_assign_ssa_name_copy_p (stmt
))
290 tree lhs
= gimple_assign_lhs (stmt
);
291 tree rhs
= gimple_assign_rhs1 (stmt
);
293 updated
|= copy_rename_partition_coalesce (map
, lhs
, rhs
, debug
);
300 /* Treat PHI nodes as copies between the result and each argument. */
301 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
306 phi
= gsi_stmt (gsi
);
307 res
= gimple_phi_result (phi
);
309 /* Do not process virtual SSA_NAMES. */
310 if (!is_gimple_reg (SSA_NAME_VAR (res
)))
313 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
315 tree arg
= gimple_phi_arg (phi
, i
)->def
;
316 if (TREE_CODE (arg
) == SSA_NAME
)
317 updated
|= copy_rename_partition_coalesce (map
, res
, arg
, debug
);
323 dump_var_map (debug
, map
);
325 /* Now one more pass to make all elements of a partition share the same
328 for (x
= 1; x
< num_ssa_names
; x
++)
330 part_var
= partition_to_var (map
, x
);
336 if (SSA_NAME_VAR (var
) != SSA_NAME_VAR (part_var
))
338 fprintf (debug
, "Coalesced ");
339 print_generic_expr (debug
, var
, TDF_SLIM
);
340 fprintf (debug
, " to ");
341 print_generic_expr (debug
, part_var
, TDF_SLIM
);
342 fprintf (debug
, "\n");
345 replace_ssa_name_symbol (var
, SSA_NAME_VAR (part_var
));
348 delete_var_map (map
);
349 return updated
? TODO_remove_unused_locals
: 0;
352 /* Return true if copy rename is to be performed. */
355 gate_copyrename (void)
357 return flag_tree_copyrename
!= 0;
360 struct gimple_opt_pass pass_rename_ssa_copies
=
364 "copyrename", /* name */
365 gate_copyrename
, /* gate */
366 rename_ssa_copies
, /* execute */
369 0, /* static_pass_number */
370 TV_TREE_COPY_RENAME
, /* tv_id */
371 PROP_cfg
| PROP_ssa
, /* properties_required */
372 0, /* properties_provided */
373 0, /* properties_destroyed */
374 0, /* todo_flags_start */
375 TODO_dump_func
| TODO_verify_ssa
/* todo_flags_finish */