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 /* Don't coalesce if the aliasing sets of the types are different. */
237 if (POINTER_TYPE_P (TREE_TYPE (root1
))
238 && POINTER_TYPE_P (TREE_TYPE (root2
))
239 && ((get_alias_set (TREE_TYPE (TREE_TYPE (root1
)))
240 != get_alias_set (TREE_TYPE (TREE_TYPE (root2
))))
241 || (DECL_P (root1
) && DECL_P (root2
)
242 && DECL_NO_TBAA_P (root1
) != DECL_NO_TBAA_P (root2
))))
245 fprintf (debug
, " : 2 different aliasing sets. No coalesce.\n");
250 /* Merge the two partitions. */
251 p3
= partition_union (map
->var_partition
, p1
, p2
);
253 /* Set the root variable of the partition to the better choice, if there is
256 replace_ssa_name_symbol (partition_to_var (map
, p3
), root2
);
258 replace_ssa_name_symbol (partition_to_var (map
, p3
), root1
);
262 fprintf (debug
, " --> P%d ", p3
);
263 print_generic_expr (debug
, SSA_NAME_VAR (partition_to_var (map
, p3
)),
265 fprintf (debug
, "\n");
271 /* This function will make a pass through the IL, and attempt to coalesce any
272 SSA versions which occur in PHI's or copies. Coalescing is accomplished by
273 changing the underlying root variable of all coalesced version. This will
274 then cause the SSA->normal pass to attempt to coalesce them all to the same
278 rename_ssa_copies (void)
282 gimple_stmt_iterator gsi
;
287 bool updated
= false;
289 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
294 map
= init_var_map (num_ssa_names
);
298 /* Scan for real copies. */
299 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
301 stmt
= gsi_stmt (gsi
);
302 if (gimple_assign_ssa_name_copy_p (stmt
))
304 tree lhs
= gimple_assign_lhs (stmt
);
305 tree rhs
= gimple_assign_rhs1 (stmt
);
307 updated
|= copy_rename_partition_coalesce (map
, lhs
, rhs
, debug
);
314 /* Treat PHI nodes as copies between the result and each argument. */
315 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
320 phi
= gsi_stmt (gsi
);
321 res
= gimple_phi_result (phi
);
323 /* Do not process virtual SSA_NAMES. */
324 if (!is_gimple_reg (SSA_NAME_VAR (res
)))
327 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
329 tree arg
= gimple_phi_arg (phi
, i
)->def
;
330 if (TREE_CODE (arg
) == SSA_NAME
)
331 updated
|= copy_rename_partition_coalesce (map
, res
, arg
, debug
);
337 dump_var_map (debug
, map
);
339 /* Now one more pass to make all elements of a partition share the same
342 for (x
= 1; x
< num_ssa_names
; x
++)
344 part_var
= partition_to_var (map
, x
);
350 if (SSA_NAME_VAR (var
) != SSA_NAME_VAR (part_var
))
352 fprintf (debug
, "Coalesced ");
353 print_generic_expr (debug
, var
, TDF_SLIM
);
354 fprintf (debug
, " to ");
355 print_generic_expr (debug
, part_var
, TDF_SLIM
);
356 fprintf (debug
, "\n");
359 replace_ssa_name_symbol (var
, SSA_NAME_VAR (part_var
));
362 delete_var_map (map
);
363 return updated
? TODO_remove_unused_locals
: 0;
366 /* Return true if copy rename is to be performed. */
369 gate_copyrename (void)
371 return flag_tree_copyrename
!= 0;
374 struct gimple_opt_pass pass_rename_ssa_copies
=
378 "copyrename", /* name */
379 gate_copyrename
, /* gate */
380 rename_ssa_copies
, /* execute */
383 0, /* static_pass_number */
384 TV_TREE_COPY_RENAME
, /* tv_id */
385 PROP_cfg
| PROP_ssa
, /* properties_required */
386 0, /* properties_provided */
387 0, /* properties_destroyed */
388 0, /* todo_flags_start */
389 TODO_dump_func
| TODO_verify_ssa
/* todo_flags_finish */