2 Copyright (C) 2004-2014 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"
26 #include "basic-block.h"
27 #include "tree-ssa-alias.h"
28 #include "internal-fn.h"
29 #include "gimple-expr.h"
32 #include "gimple-iterator.h"
38 #include "hard-reg-set.h"
41 #include "tree-pretty-print.h"
43 #include "gimple-ssa.h"
44 #include "stringpool.h"
45 #include "tree-ssanames.h"
48 #include "tree-inline.h"
49 #include "tree-ssa-live.h"
50 #include "tree-pass.h"
51 #include "langhooks.h"
55 /* Number of copies coalesced. */
59 /* The following routines implement the SSA copy renaming phase.
61 This optimization looks for copies between 2 SSA_NAMES, either through a
62 direct copy, or an implicit one via a PHI node result and its arguments.
64 Each copy is examined to determine if it is possible to rename the base
65 variable of one of the operands to the same variable as the other operand.
70 If this copy couldn't be copy propagated, it could possibly remain in the
71 program throughout the optimization phases. After SSA->normal, it would
77 Since T.3_5 is distinct from all other SSA versions of T.3, there is no
78 fundamental reason why the base variable needs to be T.3, subject to
79 certain restrictions. This optimization attempts to determine if we can
80 change the base variable on copies like this, and result in code such as:
85 This gives the SSA->normal pass a shot at coalescing a_1 and a_5. If it is
86 possible, the copy goes away completely. If it isn't possible, a new temp
87 will be created for a_5, and you will end up with the exact same code:
92 The other benefit of performing this optimization relates to what variables
93 are chosen in copies. Gimplification of the program uses temporaries for
94 a lot of things. expressions like
105 Copy propagation is done in a forward direction, and if we can propagate
106 through the copy, we end up with:
111 The copy is gone, but so is all reference to the user variable 'a'. By
112 performing this optimization, we would see the sequence:
118 which copy propagation would then turn into:
123 and so we still retain the user variable whenever possible. */
126 /* Coalesce the partitions in MAP representing VAR1 and VAR2 if it is valid.
127 Choose a representative for the partition, and send debug info to DEBUG. */
130 copy_rename_partition_coalesce (var_map map
, tree var1
, tree var2
, FILE *debug
)
135 bool ign1
, ign2
, abnorm
;
137 gcc_assert (TREE_CODE (var1
) == SSA_NAME
);
138 gcc_assert (TREE_CODE (var2
) == SSA_NAME
);
140 register_ssa_partition (map
, var1
);
141 register_ssa_partition (map
, var2
);
143 p1
= partition_find (map
->var_partition
, SSA_NAME_VERSION (var1
));
144 p2
= partition_find (map
->var_partition
, SSA_NAME_VERSION (var2
));
148 fprintf (debug
, "Try : ");
149 print_generic_expr (debug
, var1
, TDF_SLIM
);
150 fprintf (debug
, "(P%d) & ", p1
);
151 print_generic_expr (debug
, var2
, TDF_SLIM
);
152 fprintf (debug
, "(P%d)", p2
);
155 gcc_assert (p1
!= NO_PARTITION
);
156 gcc_assert (p2
!= NO_PARTITION
);
161 fprintf (debug
, " : Already coalesced.\n");
165 rep1
= partition_to_var (map
, p1
);
166 rep2
= partition_to_var (map
, p2
);
167 root1
= SSA_NAME_VAR (rep1
);
168 root2
= SSA_NAME_VAR (rep2
);
169 if (!root1
&& !root2
)
172 /* Don't coalesce if one of the variables occurs in an abnormal PHI. */
173 abnorm
= (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep1
)
174 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep2
));
178 fprintf (debug
, " : Abnormal PHI barrier. No coalesce.\n");
182 /* Partitions already have the same root, simply merge them. */
185 p1
= partition_union (map
->var_partition
, p1
, p2
);
187 fprintf (debug
, " : Same root, coalesced --> P%d.\n", p1
);
191 /* Never attempt to coalesce 2 different parameters. */
192 if ((root1
&& TREE_CODE (root1
) == PARM_DECL
)
193 && (root2
&& TREE_CODE (root2
) == PARM_DECL
))
196 fprintf (debug
, " : 2 different PARM_DECLS. No coalesce.\n");
200 if ((root1
&& TREE_CODE (root1
) == RESULT_DECL
)
201 != (root2
&& TREE_CODE (root2
) == RESULT_DECL
))
204 fprintf (debug
, " : One root a RESULT_DECL. No coalesce.\n");
208 ign1
= !root1
|| (TREE_CODE (root1
) == VAR_DECL
&& DECL_IGNORED_P (root1
));
209 ign2
= !root2
|| (TREE_CODE (root2
) == VAR_DECL
&& DECL_IGNORED_P (root2
));
211 /* Refrain from coalescing user variables, if requested. */
214 if (flag_ssa_coalesce_vars
&& DECL_FROM_INLINE (root2
))
216 else if (flag_ssa_coalesce_vars
&& DECL_FROM_INLINE (root1
))
218 else if (flag_ssa_coalesce_vars
!= 2)
221 fprintf (debug
, " : 2 different USER vars. No coalesce.\n");
228 /* If both values have default defs, we can't coalesce. If only one has a
229 tag, make sure that variable is the new root partition. */
230 if (root1
&& ssa_default_def (cfun
, root1
))
232 if (root2
&& ssa_default_def (cfun
, root2
))
235 fprintf (debug
, " : 2 default defs. No coalesce.\n");
244 else if (root2
&& ssa_default_def (cfun
, root2
))
250 /* Do not coalesce if we cannot assign a symbol to the partition. */
251 if (!(!ign2
&& root2
)
252 && !(!ign1
&& root1
))
255 fprintf (debug
, " : Choosen variable has no root. No coalesce.\n");
259 /* Don't coalesce if the new chosen root variable would be read-only.
260 If both ign1 && ign2, then the root var of the larger partition
261 wins, so reject in that case if any of the root vars is TREE_READONLY.
262 Otherwise reject only if the root var, on which replace_ssa_name_symbol
263 will be called below, is readonly. */
264 if (((root1
&& TREE_READONLY (root1
)) && ign2
)
265 || ((root2
&& TREE_READONLY (root2
)) && ign1
))
268 fprintf (debug
, " : Readonly variable. No coalesce.\n");
272 /* Don't coalesce if the two variables aren't type compatible . */
273 if (!types_compatible_p (TREE_TYPE (var1
), TREE_TYPE (var2
))
274 /* There is a disconnect between the middle-end type-system and
275 VRP, avoid coalescing enum types with different bounds. */
276 || ((TREE_CODE (TREE_TYPE (var1
)) == ENUMERAL_TYPE
277 || TREE_CODE (TREE_TYPE (var2
)) == ENUMERAL_TYPE
)
278 && TREE_TYPE (var1
) != TREE_TYPE (var2
)))
281 fprintf (debug
, " : Incompatible types. No coalesce.\n");
285 /* Merge the two partitions. */
286 p3
= partition_union (map
->var_partition
, p1
, p2
);
288 /* Set the root variable of the partition to the better choice, if there is
291 replace_ssa_name_symbol (partition_to_var (map
, p3
), root2
);
292 else if (!ign1
&& root1
)
293 replace_ssa_name_symbol (partition_to_var (map
, p3
), root1
);
299 fprintf (debug
, " --> P%d ", p3
);
300 print_generic_expr (debug
, SSA_NAME_VAR (partition_to_var (map
, p3
)),
302 fprintf (debug
, "\n");
309 const pass_data pass_data_rename_ssa_copies
=
311 GIMPLE_PASS
, /* type */
312 "copyrename", /* name */
313 OPTGROUP_NONE
, /* optinfo_flags */
314 TV_TREE_COPY_RENAME
, /* tv_id */
315 ( PROP_cfg
| PROP_ssa
), /* properties_required */
316 0, /* properties_provided */
317 0, /* properties_destroyed */
318 0, /* todo_flags_start */
319 0, /* todo_flags_finish */
322 class pass_rename_ssa_copies
: public gimple_opt_pass
325 pass_rename_ssa_copies (gcc::context
*ctxt
)
326 : gimple_opt_pass (pass_data_rename_ssa_copies
, ctxt
)
329 /* opt_pass methods: */
330 opt_pass
* clone () { return new pass_rename_ssa_copies (m_ctxt
); }
331 virtual bool gate (function
*) { return flag_tree_copyrename
!= 0; }
332 virtual unsigned int execute (function
*);
334 }; // class pass_rename_ssa_copies
336 /* This function will make a pass through the IL, and attempt to coalesce any
337 SSA versions which occur in PHI's or copies. Coalescing is accomplished by
338 changing the underlying root variable of all coalesced version. This will
339 then cause the SSA->normal pass to attempt to coalesce them all to the same
343 pass_rename_ssa_copies::execute (function
*fun
)
347 gimple_stmt_iterator gsi
;
353 memset (&stats
, 0, sizeof (stats
));
355 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
360 map
= init_var_map (num_ssa_names
);
362 FOR_EACH_BB_FN (bb
, fun
)
364 /* Scan for real copies. */
365 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
367 stmt
= gsi_stmt (gsi
);
368 if (gimple_assign_ssa_name_copy_p (stmt
))
370 tree lhs
= gimple_assign_lhs (stmt
);
371 tree rhs
= gimple_assign_rhs1 (stmt
);
373 copy_rename_partition_coalesce (map
, lhs
, rhs
, debug
);
378 FOR_EACH_BB_FN (bb
, fun
)
380 /* Treat PHI nodes as copies between the result and each argument. */
381 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
386 phi
= gsi_stmt (gsi
);
387 res
= gimple_phi_result (phi
);
389 /* Do not process virtual SSA_NAMES. */
390 if (virtual_operand_p (res
))
393 /* Make sure to only use the same partition for an argument
394 as the result but never the other way around. */
395 if (SSA_NAME_VAR (res
)
396 && !DECL_IGNORED_P (SSA_NAME_VAR (res
)))
397 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
399 tree arg
= PHI_ARG_DEF (phi
, i
);
400 if (TREE_CODE (arg
) == SSA_NAME
)
401 copy_rename_partition_coalesce (map
, res
, arg
,
404 /* Else if all arguments are in the same partition try to merge
405 it with the result. */
410 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
412 tree arg
= PHI_ARG_DEF (phi
, i
);
413 if (TREE_CODE (arg
) != SSA_NAME
)
418 else if (all_p_same
== -1)
420 p
= partition_find (map
->var_partition
,
421 SSA_NAME_VERSION (arg
));
424 else if (all_p_same
== 1
425 && p
!= partition_find (map
->var_partition
,
426 SSA_NAME_VERSION (arg
)))
433 copy_rename_partition_coalesce (map
, res
,
434 PHI_ARG_DEF (phi
, 0),
441 dump_var_map (debug
, map
);
443 /* Now one more pass to make all elements of a partition share the same
446 for (x
= 1; x
< num_ssa_names
; x
++)
448 part_var
= partition_to_var (map
, x
);
452 if (SSA_NAME_VAR (var
) == SSA_NAME_VAR (part_var
))
456 fprintf (debug
, "Coalesced ");
457 print_generic_expr (debug
, var
, TDF_SLIM
);
458 fprintf (debug
, " to ");
459 print_generic_expr (debug
, part_var
, TDF_SLIM
);
460 fprintf (debug
, "\n");
463 replace_ssa_name_symbol (var
, SSA_NAME_VAR (part_var
));
466 statistics_counter_event (fun
, "copies coalesced",
468 delete_var_map (map
);
475 make_pass_rename_ssa_copies (gcc::context
*ctxt
)
477 return new pass_rename_ssa_copies (ctxt
);