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"
37 #include "tree-dump.h"
38 #include "tree-ssa-live.h"
39 #include "tree-pass.h"
40 #include "langhooks.h"
42 extern void rename_ssa_copies (void);
44 /* The following routines implement the SSA copy renaming phase.
46 This optimization looks for copies between 2 SSA_NAMES, either through a
47 direct copy, or an implicit one via a PHI node result and its arguments.
49 Each copy is examined to determine if it is possible to rename the base
50 variable of one of the operands to the same variable as the other operand.
55 If this copy couldn't be copy propagated, it could possibly remain in the
56 program throughout the optimization phases. After SSA->normal, it would
62 Since T.3_5 is distinct from all other SSA versions of T.3, there is no
63 fundamental reason why the base variable needs to be T.3, subject to
64 certain restrictions. This optimization attempts to determine if we can
65 change the base variable on copies like this, and result in code such as:
70 This gives the SSA->normal pass a shot at coalescing a_1 and a_5. If it is
71 possible, the copy goes away completely. If it isn't possible, a new temp
72 will be created for a_5, and you will end up with the exact same code:
77 The other benefit of performing this optimization relates to what variables
78 are chosen in copies. Gimplification of the program uses temporaries for
79 a lot of things. expressions like
90 Copy propagation is done in a forward direction, and if we can propagate
91 through the copy, we end up with:
96 The copy is gone, but so is all reference to the user variable 'a'. By
97 performing this optimization, we would see the sequence:
103 which copy propagation would then turn into:
108 and so we still retain the user variable whenever possible. */
111 /* Coalesce the partitions in MAP representing VAR1 and VAR2 if it is valid.
112 Choose a representative for the partition, and send debug info to DEBUG. */
115 copy_rename_partition_coalesce (var_map map
, tree var1
, tree var2
, FILE *debug
)
119 var_ann_t ann1
, ann2
, ann3
;
122 gcc_assert (TREE_CODE (var1
) == SSA_NAME
);
123 gcc_assert (TREE_CODE (var2
) == SSA_NAME
);
125 register_ssa_partition (map
, var1
, false);
126 register_ssa_partition (map
, var2
, true);
128 p1
= partition_find (map
->var_partition
, SSA_NAME_VERSION (var1
));
129 p2
= partition_find (map
->var_partition
, SSA_NAME_VERSION (var2
));
133 fprintf (debug
, "Try : ");
134 print_generic_expr (debug
, var1
, TDF_SLIM
);
135 fprintf (debug
, "(P%d) & ", p1
);
136 print_generic_expr (debug
, var2
, TDF_SLIM
);
137 fprintf (debug
, "(P%d)", p2
);
140 gcc_assert (p1
!= NO_PARTITION
);
141 gcc_assert (p2
!= NO_PARTITION
);
143 root1
= SSA_NAME_VAR (partition_to_var (map
, p1
));
144 root2
= SSA_NAME_VAR (partition_to_var (map
, p2
));
146 if (DECL_HARD_REGISTER (root1
) || DECL_HARD_REGISTER (root2
))
150 if (DECL_HARD_REGISTER (root1
))
151 print_generic_expr (debug
, var1
, TDF_SLIM
);
153 print_generic_expr (debug
, var2
, TDF_SLIM
);
154 fprintf (debug
, " is a hardware register. No Coalescing.\n");
159 ann1
= var_ann (root1
);
160 ann2
= var_ann (root2
);
165 fprintf (debug
, " : Already coalesced.\n");
169 /* Partitions already have the same root, simply merge them. */
172 p1
= partition_union (map
->var_partition
, p1
, p2
);
174 fprintf (debug
, " : Same root, coalesced --> P%d.\n", p1
);
178 /* Never attempt to coalesce 2 difference parameters. */
179 if (TREE_CODE (root1
) == PARM_DECL
&& TREE_CODE (root2
) == PARM_DECL
)
182 fprintf (debug
, " : 2 different PARM_DECLS. No coalesce.\n");
186 if ((TREE_CODE (root1
) == RESULT_DECL
) != (TREE_CODE (root2
) == RESULT_DECL
))
189 fprintf (debug
, " : One root a RESULT_DECL. No coalesce.\n");
193 ign1
= TREE_CODE (root1
) == VAR_DECL
&& DECL_IGNORED_P (root1
);
194 ign2
= TREE_CODE (root2
) == VAR_DECL
&& DECL_IGNORED_P (root2
);
196 /* Never attempt to coalesce 2 user variables unless one is an inline
200 if (DECL_FROM_INLINE (root2
))
202 else if (DECL_FROM_INLINE (root1
))
207 fprintf (debug
, " : 2 different USER vars. No coalesce.\n");
212 /* Don't coalesce if there are two different memory tags. */
213 if (ann1
->type_mem_tag
&& ann2
->type_mem_tag
214 && ann1
->type_mem_tag
!= ann2
->type_mem_tag
)
217 fprintf (debug
, " : 2 memory tags. No coalesce.\n");
221 /* If both values have default defs, we can't coalesce. If only one has a
222 tag, make sure that variable is the new root partition. */
223 if (default_def (root1
))
225 if (default_def (root2
))
228 fprintf (debug
, " : 2 default defs. No coalesce.\n");
237 else if (default_def (root2
))
243 /* Don't coalesce if the two variables aren't type compatible. */
244 if (!lang_hooks
.types_compatible_p (TREE_TYPE (root1
), TREE_TYPE (root2
)))
247 fprintf (debug
, " : Incompatible types. No coalesce.\n");
251 /* Merge the two partitions. */
252 p3
= partition_union (map
->var_partition
, p1
, p2
);
254 /* Set the root variable of the partition to the better choice, if there is
257 replace_ssa_name_symbol (partition_to_var (map
, p3
), root2
);
259 replace_ssa_name_symbol (partition_to_var (map
, p3
), root1
);
261 /* Update the various flag widgitry of the current base representative. */
262 ann3
= var_ann (SSA_NAME_VAR (partition_to_var (map
, p3
)));
263 if (ann1
->type_mem_tag
)
264 ann3
->type_mem_tag
= ann1
->type_mem_tag
;
266 ann3
->type_mem_tag
= ann2
->type_mem_tag
;
270 fprintf (debug
, " --> P%d ", p3
);
271 print_generic_expr (debug
, SSA_NAME_VAR (partition_to_var (map
, p3
)),
273 fprintf (debug
, "\n");
278 /* This function will make a pass through the IL, and attempt to coalesce any
279 SSA versions which occur in PHI's or copies. Coalescing is accomplished by
280 changing the underlying root variable of all coalesced version. This will
281 then cause the SSA->normal pass to attempt to coalesce them all to the same
285 rename_ssa_copies (void)
289 block_stmt_iterator bsi
;
290 tree phi
, stmt
, var
, part_var
;
294 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
299 map
= init_var_map (num_ssa_names
+ 1);
303 /* Scan for real copies. */
304 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
306 stmt
= bsi_stmt (bsi
);
307 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
309 tree lhs
= TREE_OPERAND (stmt
, 0);
310 tree rhs
= TREE_OPERAND (stmt
, 1);
312 if (TREE_CODE (lhs
) == SSA_NAME
&& TREE_CODE (rhs
) == SSA_NAME
)
313 copy_rename_partition_coalesce (map
, lhs
, rhs
, debug
);
320 /* Treat PHI nodes as copies between the result and each argument. */
321 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
324 tree res
= PHI_RESULT (phi
);
326 /* Do not process virtual SSA_NAMES. */
327 if (!is_gimple_reg (SSA_NAME_VAR (res
)))
330 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
332 tree arg
= PHI_ARG_DEF (phi
, i
);
333 if (TREE_CODE (arg
) == SSA_NAME
)
334 copy_rename_partition_coalesce (map
, res
, arg
, debug
);
340 dump_var_map (debug
, map
);
342 /* Now one more pass to make all elements of a partition share the same
345 for (x
= 1; x
<= num_ssa_names
; x
++)
347 part_var
= partition_to_var (map
, x
);
350 var
= map
->partition_to_var
[x
];
353 if (SSA_NAME_VAR (var
) != SSA_NAME_VAR (part_var
))
355 fprintf (debug
, "Coalesced ");
356 print_generic_expr (debug
, var
, TDF_SLIM
);
357 fprintf (debug
, " to ");
358 print_generic_expr (debug
, part_var
, TDF_SLIM
);
359 fprintf (debug
, "\n");
362 replace_ssa_name_symbol (var
, SSA_NAME_VAR (part_var
));
365 delete_var_map (map
);
368 /* Return true if copy rename is to be performed. */
371 gate_copyrename (void)
373 return flag_tree_copyrename
!= 0;
376 struct tree_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
| PROP_alias
, /* 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 */