This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PR64164] drop copyrename, integrate into expand
- From: Alexandre Oliva <aoliva at redhat dot com>
- To: gcc-patches at gcc dot gnu dot org
- Date: Sat, 28 Mar 2015 16:21:55 -0300
- Subject: Re: [PR64164] drop copyrename, integrate into expand
- Authentication-results: sourceware.org; auth=none
- References: <orvbhmz59m dot fsf at livre dot home>
On Mar 27, 2015, Alexandre Oliva <aoliva@redhat.com> wrote:
> This patch reworks the out-of-ssa expander to enable coalescing of SSA
> partitions that don't share the same base name. This is done only when
> optimizing.
> The test we use to tell whether two partitions can be merged no longer
> demands them to have the same base variable when optimizing, so they
> become eligible for coalescing, as they would after copyrename. We then
> compute the partitioning we'd get if all coalescible partitions were
> coalesced, using this partition assignment to assign base vars numbers.
> These base var numbers are then used to identify conflicts, which used
> to be based on shared base vars or base types.
> We now propagate base var names during coalescing proper, only towards
> the leader variable. I'm no longer sure this is still needed, but
> something about handling variables and results led me this way and I
> didn't revisit it. I might rework that with a later patch, or a later
> revision of this patch; it would require other means to identify
> partitions holding result_decls during merging, or allow that and deal
> with param and result decls in a different way during expand proper.
> I had to fix two lingering bugs in order for the whole thing to work: we
> perform conflict detection after abnormal coalescing, but we computed
> live ranges involving only the partition leaders, so conflicts with
> other names already coalesced wouldn't be detected.
This early abnormal coalescing was only present for a few days in the
trunk, and I was lucky enough to start working on a tree that had it.
It turns out that the fix for it was thus rendered unnecessary, so I
dropped it. It was the fix for it, that didn't cover the live range
check, that caused the two ICEs I saw in the regressions tests. Since
the ultimate cause of the problem is gone, and the change that
introduced the check failures, both problems went *poof* after I updated
the tree, resolved the conflicts and dropped the redundant code.
> The other problem was that we didn't track default defs for parms as
> live at entry, so they might end up coalesced.
I improved this a little bit, using the bitmap of partitions containing
default params to check that we only process function-entry defs for
them, rather than for all param decls in case they end up in other
partitions.
> I guess none of these problems would have been exercised in practice,
> because we wouldn't even consider merging ssa names associated with
> different variables.
> In the end, I verified that this fixed the codegen regression in the
> PR64164 testcase, that failed to merge two partitions that could in
> theory be merged, but that wasn't even considered due to differences in
> the SSA var names.
> I'd agree that disregarding the var names and dropping 4 passes is too
> much of a change to fix this one problem, but... it's something we
> should have long tackled, and it gets this and other jobs done, so...
Regstrapped on x86_64-linux-gnu native and on i686-pc-linux-gnu native
on x86_64, so without lto plugin. The only regression is in
gcc.dg/guality/pr54200.c, that explicitly disables VTA. When
optimization is enabled, the different coalescing we perform now causes
VTA-less variable tracking to lose track of variable "z". This
regression in non-VTA var-tracking is expected and, as richi put it in
PR 64164, I guess we don't care about that, do we? :-)
The other guality regressions I mentioned in my other email turned out
not to be regressions, but preexisting failures that somehow did not
make to the test_summary of my earlier pristine build.
Is this ok to install?
for gcc/ChangeLog
PR rtl-optimization/64164
* Makefile.in (OBJS): Drop tree-ssa-copyrename.o.
* tree-ssa-copyrename.c: Removed.
* opts.c (default_options_table): Drop -ftree-copyrename.
* passes.def: Drop all occurrences of pass_rename_ssa_copies.
* common.opt (ftree-copyrename): Ignore.
(ftree-coalesce-vars, ftree-coalesce-inlined-vars): Likewise.
* doc/invoke.texi: Remove the ignored options above.
* gimple-expr.c (gimple_can_coalesce_p): Allow coalescing
across base variables when optimizing.
* tree-ssa-coalesce.c (build_ssa_conflict_graph): Add
param_defaults argument. Process PARM_DECLs's default defs at
the entry point.
(attempt_coalesce): Add param_defaults argument, and
track the presence of default defs for params in each
partition. Propagate base var to leader on merge, preferring
parms and results, named vars, ignored vars, and then anon
vars. Refuse to merge a RESULT_DECL partition with a default
PARM_DECL one.
(coalesce_partitions): Add param_defaults argument,
and pass it to attempt_coalesce.
(dump_part_var_map): New.
(compute_optimized_partition_bases): New, called by...
(coalesce_ssa_name): ... when optimizing, disabling
partition_view_bitmap's base assignment. Pass local
param_defaults to coalescer functions.
* tree-ssa-live.c (var_map_base_init): Note use only when not
optimizing.
---
gcc/Makefile.in | 1
gcc/common.opt | 12 +
gcc/doc/invoke.texi | 29 ---
gcc/gimple-expr.c | 7 -
gcc/opts.c | 1
gcc/passes.def | 5
gcc/tree-ssa-coalesce.c | 342 ++++++++++++++++++++++++++++++-
gcc/tree-ssa-copyrename.c | 499 ---------------------------------------------
gcc/tree-ssa-live.c | 5
9 files changed, 347 insertions(+), 554 deletions(-)
delete mode 100644 gcc/tree-ssa-copyrename.c
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index f924fb8..990c4e9 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1428,7 +1428,6 @@ OBJS = \
tree-ssa-ccp.o \
tree-ssa-coalesce.o \
tree-ssa-copy.o \
- tree-ssa-copyrename.o \
tree-ssa-dce.o \
tree-ssa-dom.o \
tree-ssa-dse.o \
diff --git a/gcc/common.opt b/gcc/common.opt
index b49ac46..fefaee7 100644
--- a/gcc/common.opt
+++ b/gcc/common.opt
@@ -2207,16 +2207,16 @@ Common Report Var(flag_tree_ch) Optimization
Enable loop header copying on trees
ftree-coalesce-inlined-vars
-Common Report Var(flag_ssa_coalesce_vars,1) Init(2) RejectNegative Optimization
-Enable coalescing of copy-related user variables that are inlined
+Common Ignore RejectNegative
+Does nothing. Preserved for backward compatibility.
ftree-coalesce-vars
-Common Report Var(flag_ssa_coalesce_vars,2) Optimization
-Enable coalescing of all copy-related user variables
+Common Ignore
+Does nothing. Preserved for backward compatibility.
ftree-copyrename
-Common Report Var(flag_tree_copyrename) Optimization
-Replace SSA temporaries with better names in copies
+Common Ignore
+Does nothing. Preserved for backward compatibility.
ftree-copy-prop
Common Report Var(flag_tree_copy_prop) Optimization
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index 9749727..5d2c516 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -442,8 +442,7 @@ Objective-C and Objective-C++ Dialects}.
-fstack-protector-explicit -fstdarg-opt -fstrict-aliasing @gol
-fstrict-overflow -fthread-jumps -ftracer -ftree-bit-ccp @gol
-ftree-builtin-call-dce -ftree-ccp -ftree-ch @gol
--ftree-coalesce-inline-vars -ftree-coalesce-vars -ftree-copy-prop @gol
--ftree-copyrename -ftree-dce -ftree-dominator-opts -ftree-dse @gol
+-ftree-copy-prop -ftree-dce -ftree-dominator-opts -ftree-dse @gol
-ftree-forwprop -ftree-fre -ftree-loop-if-convert @gol
-ftree-loop-if-convert-stores -ftree-loop-im @gol
-ftree-phiprop -ftree-loop-distribution -ftree-loop-distribute-patterns @gol
@@ -8822,32 +8821,6 @@ Perform scalar replacement of aggregates. This pass replaces structure
references with scalars to prevent committing structures to memory too
early. This flag is enabled by default at @option{-O} and higher.
-@item -ftree-copyrename
-@opindex ftree-copyrename
-Perform copy renaming on trees. This pass attempts to rename compiler
-temporaries to other variables at copy locations, usually resulting in
-variable names which more closely resemble the original variables. This flag
-is enabled by default at @option{-O} and higher.
-
-@item -ftree-coalesce-inlined-vars
-@opindex ftree-coalesce-inlined-vars
-Tell the copyrename pass (see @option{-ftree-copyrename}) to attempt to
-combine small user-defined variables too, but only if they are inlined
-from other functions. It is a more limited form of
-@option{-ftree-coalesce-vars}. This may harm debug information of such
-inlined variables, but it keeps variables of the inlined-into
-function apart from each other, such that they are more likely to
-contain the expected values in a debugging session.
-
-@item -ftree-coalesce-vars
-@opindex ftree-coalesce-vars
-Tell the copyrename pass (see @option{-ftree-copyrename}) to attempt to
-combine small user-defined variables too, instead of just compiler
-temporaries. This may severely limit the ability to debug an optimized
-program compiled with @option{-fno-var-tracking-assignments}. In the
-negated form, this flag prevents SSA coalescing of user variables,
-including inlined ones. This option is enabled by default.
-
@item -ftree-ter
@opindex ftree-ter
Perform temporary expression replacement during the SSA->normal phase. Single
diff --git a/gcc/gimple-expr.c b/gcc/gimple-expr.c
index efc93b7..62ae577 100644
--- a/gcc/gimple-expr.c
+++ b/gcc/gimple-expr.c
@@ -399,13 +399,14 @@ copy_var_decl (tree var, tree name, tree type)
bool
gimple_can_coalesce_p (tree name1, tree name2)
{
- /* First check the SSA_NAME's associated DECL. We only want to
- coalesce if they have the same DECL or both have no associated DECL. */
+ /* First check the SSA_NAME's associated DECL. Without
+ optimization, we only want to coalesce if they have the same DECL
+ or both have no associated DECL. */
tree var1 = SSA_NAME_VAR (name1);
tree var2 = SSA_NAME_VAR (name2);
var1 = (var1 && (!VAR_P (var1) || !DECL_IGNORED_P (var1))) ? var1 : NULL_TREE;
var2 = (var2 && (!VAR_P (var2) || !DECL_IGNORED_P (var2))) ? var2 : NULL_TREE;
- if (var1 != var2)
+ if (var1 != var2 && !optimize)
return false;
/* Now check the types. If the types are the same, then we should
diff --git a/gcc/opts.c b/gcc/opts.c
index 39c190d..8149421 100644
--- a/gcc/opts.c
+++ b/gcc/opts.c
@@ -453,7 +453,6 @@ static const struct default_options default_options_table[] =
{ OPT_LEVELS_1_PLUS, OPT_ftree_dse, NULL, 1 },
{ OPT_LEVELS_1_PLUS, OPT_ftree_ter, NULL, 1 },
{ OPT_LEVELS_1_PLUS_NOT_DEBUG, OPT_ftree_sra, NULL, 1 },
- { OPT_LEVELS_1_PLUS, OPT_ftree_copyrename, NULL, 1 },
{ OPT_LEVELS_1_PLUS, OPT_ftree_fre, NULL, 1 },
{ OPT_LEVELS_1_PLUS, OPT_ftree_copy_prop, NULL, 1 },
{ OPT_LEVELS_1_PLUS, OPT_ftree_sink, NULL, 1 },
diff --git a/gcc/passes.def b/gcc/passes.def
index 1d598b2..f8fd0ef 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -77,7 +77,6 @@ along with GCC; see the file COPYING3. If not see
NEXT_PASS (pass_all_early_optimizations);
PUSH_INSERT_PASSES_WITHIN (pass_all_early_optimizations)
NEXT_PASS (pass_remove_cgraph_callee_edges);
- NEXT_PASS (pass_rename_ssa_copies);
NEXT_PASS (pass_object_sizes);
NEXT_PASS (pass_ccp);
/* After CCP we rewrite no longer addressed locals into SSA
@@ -154,7 +153,6 @@ along with GCC; see the file COPYING3. If not see
/* Initial scalar cleanups before alias computation.
They ensure memory accesses are not indirect wherever possible. */
NEXT_PASS (pass_strip_predict_hints);
- NEXT_PASS (pass_rename_ssa_copies);
NEXT_PASS (pass_ccp);
/* After CCP we rewrite no longer addressed locals into SSA
form if possible. */
@@ -182,7 +180,6 @@ along with GCC; see the file COPYING3. If not see
NEXT_PASS (pass_stdarg);
NEXT_PASS (pass_lower_complex);
NEXT_PASS (pass_sra);
- NEXT_PASS (pass_rename_ssa_copies);
/* The dom pass will also resolve all __builtin_constant_p calls
that are still there to 0. This has to be done after some
propagations have already run, but before some more dead code
@@ -291,7 +288,6 @@ along with GCC; see the file COPYING3. If not see
NEXT_PASS (pass_fold_builtins);
NEXT_PASS (pass_optimize_widening_mul);
NEXT_PASS (pass_tail_calls);
- NEXT_PASS (pass_rename_ssa_copies);
/* FIXME: If DCE is not run before checking for uninitialized uses,
we may get false warnings (e.g., testsuite/gcc.dg/uninit-5.c).
However, this also causes us to misdiagnose cases that should be
@@ -326,7 +322,6 @@ along with GCC; see the file COPYING3. If not see
NEXT_PASS (pass_dce);
NEXT_PASS (pass_asan);
NEXT_PASS (pass_tsan);
- NEXT_PASS (pass_rename_ssa_copies);
/* ??? We do want some kind of loop invariant motion, but we possibly
need to adjust LIM to be more friendly towards preserving accurate
debug information here. */
diff --git a/gcc/tree-ssa-coalesce.c b/gcc/tree-ssa-coalesce.c
index 1afeefe..8557d84 100644
--- a/gcc/tree-ssa-coalesce.c
+++ b/gcc/tree-ssa-coalesce.c
@@ -825,13 +825,23 @@ live_track_clear_base_vars (live_track_p ptr)
base variable are added. */
static ssa_conflicts_p
-build_ssa_conflict_graph (tree_live_info_p liveinfo)
+build_ssa_conflict_graph (tree_live_info_p liveinfo, bitmap param_defaults)
{
ssa_conflicts_p graph;
var_map map;
basic_block bb;
ssa_op_iter iter;
live_track_p live;
+ basic_block entry;
+
+ /* If we are optimizing, we may attempt to coalesce variables from
+ different base variables, including different parameters, so we
+ have to make sure default defs live at the entry block conflict
+ with each other. */
+ if (optimize)
+ entry = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
+ else
+ entry = NULL;
map = live_var_map (liveinfo);
graph = ssa_conflicts_new (num_var_partitions (map));
@@ -890,6 +900,36 @@ build_ssa_conflict_graph (tree_live_info_p liveinfo)
live_track_process_def (live, result, graph);
}
+ /* Pretend there are defs for params' default defs at the start
+ of the (post-)entry block. We run after abnormal coalescing,
+ so we can't assume the leader variable is the default
+ definition, but because of SSA_NAME_VAR adjustments in
+ attempt_coalesce, we can assume that if there is any
+ PARM_DECL in the partition, it will be the leader's
+ SSA_NAME_VAR. */
+ if (bb == entry)
+ {
+ unsigned base;
+ bitmap_iterator bi;
+ EXECUTE_IF_SET_IN_BITMAP (live->live_base_var, 0, base, bi)
+ {
+ bitmap_iterator bi2;
+ unsigned part;
+ EXECUTE_IF_SET_IN_BITMAP (live->live_base_partitions[base],
+ 0, part, bi2)
+ {
+ tree var = partition_to_var (map, part);
+ if (!SSA_NAME_VAR (var)
+ || TREE_CODE (SSA_NAME_VAR (var)) != PARM_DECL
+ || !(SSA_NAME_IS_DEFAULT_DEF (var)
+ || (param_defaults
+ && bitmap_bit_p (param_defaults, part))))
+ continue;
+ live_track_process_def (live, var, graph);
+ }
+ }
+ }
+
live_track_clear_base_vars (live);
}
@@ -1126,11 +1166,12 @@ create_outofssa_var_map (coalesce_list_p cl, bitmap used_in_copy)
static inline bool
attempt_coalesce (var_map map, ssa_conflicts_p graph, int x, int y,
- FILE *debug)
+ bitmap param_defaults, FILE *debug)
{
int z;
tree var1, var2;
int p1, p2;
+ bool default_def = false;
p1 = var_to_partition (map, ssa_name (x));
p2 = var_to_partition (map, ssa_name (y));
@@ -1158,6 +1199,70 @@ attempt_coalesce (var_map map, ssa_conflicts_p graph, int x, int y,
{
var1 = partition_to_var (map, p1);
var2 = partition_to_var (map, p2);
+
+ tree leader;
+
+ if (var1 == var2 || !SSA_NAME_VAR (var2)
+ || SSA_NAME_VAR (var1) == SSA_NAME_VAR (var2))
+ {
+ leader = SSA_NAME_VAR (var1);
+ default_def = (leader && TREE_CODE (leader) == PARM_DECL
+ && (SSA_NAME_IS_DEFAULT_DEF (var1)
+ || bitmap_bit_p (param_defaults, p1)));
+ }
+ else if (!SSA_NAME_VAR (var1))
+ {
+ leader = SSA_NAME_VAR (var2);
+ default_def = (leader && TREE_CODE (leader) == PARM_DECL
+ && (SSA_NAME_IS_DEFAULT_DEF (var2)
+ || bitmap_bit_p (param_defaults, p2)));
+ }
+ else if ((TREE_CODE (SSA_NAME_VAR (var1)) == PARM_DECL
+ && (SSA_NAME_IS_DEFAULT_DEF (var1)
+ || bitmap_bit_p (param_defaults, p1)))
+ || TREE_CODE (SSA_NAME_VAR (var1)) == RESULT_DECL)
+ {
+ if ((TREE_CODE (SSA_NAME_VAR (var2)) == PARM_DECL
+ && (SSA_NAME_IS_DEFAULT_DEF (var2)
+ || bitmap_bit_p (param_defaults, p2)))
+ || TREE_CODE (SSA_NAME_VAR (var2)) == RESULT_DECL)
+ {
+ /* We only have one RESULT_DECL, and two PARM_DECL
+ DEFAULT_DEFs would have conflicted, so we know either
+ one of var1 or var2 is a PARM_DECL, and the other is
+ a RESULT_DECL. */
+ if (debug)
+ fprintf (debug, ": Cannot coalesce PARM_DECL and RESULT_DECL\n");
+ return false;
+ }
+ leader = SSA_NAME_VAR (var1);
+ default_def = TREE_CODE (leader) == PARM_DECL;
+ }
+ else if ((TREE_CODE (SSA_NAME_VAR (var2)) == PARM_DECL
+ && (SSA_NAME_IS_DEFAULT_DEF (var2)
+ || bitmap_bit_p (param_defaults, p2)))
+ || TREE_CODE (SSA_NAME_VAR (var2)) == RESULT_DECL)
+ {
+ leader = SSA_NAME_VAR (var2);
+ default_def = TREE_CODE (leader) == PARM_DECL;
+ }
+ else if (TREE_CODE (SSA_NAME_VAR (var1)) == PARM_DECL)
+ leader = SSA_NAME_VAR (var1);
+ else if (TREE_CODE (SSA_NAME_VAR (var2)) == PARM_DECL)
+ leader = SSA_NAME_VAR (var2);
+ else if (TREE_CODE (SSA_NAME_VAR (var1)) == VAR_DECL
+ && !DECL_IGNORED_P (SSA_NAME_VAR (var1)))
+ leader = SSA_NAME_VAR (var1);
+ else if (TREE_CODE (SSA_NAME_VAR (var2)) == VAR_DECL
+ && !DECL_IGNORED_P (SSA_NAME_VAR (var2)))
+ leader = SSA_NAME_VAR (var2);
+ else if (TREE_CODE (SSA_NAME_VAR (var1)) == VAR_DECL)
+ leader = SSA_NAME_VAR (var1);
+ else if (TREE_CODE (SSA_NAME_VAR (var2)) == VAR_DECL)
+ leader = SSA_NAME_VAR (var2);
+ else /* What else could it be? */
+ gcc_unreachable ();
+
z = var_union (map, var1, var2);
if (z == NO_PARTITION)
{
@@ -1173,8 +1278,46 @@ attempt_coalesce (var_map map, ssa_conflicts_p graph, int x, int y,
else
ssa_conflicts_merge (graph, p2, p1);
+ if (z == p1)
+ {
+ if (SSA_NAME_VAR (var1) != leader)
+ {
+ replace_ssa_name_symbol (var1, leader);
+ if (debug)
+ {
+ fprintf (debug, ": Renamed ");
+ print_generic_expr (debug, var1, TDF_SLIM);
+ }
+ }
+ if (default_def)
+ {
+ if (SSA_NAME_IS_DEFAULT_DEF (var2))
+ bitmap_clear_bit (param_defaults, p2);
+ bitmap_set_bit (param_defaults, p1);
+ }
+ }
+ else
+ {
+ if (SSA_NAME_VAR (var2) != leader)
+ {
+ replace_ssa_name_symbol (var2, leader);
+ if (debug)
+ {
+ fprintf (debug, ": Renamed ");
+ print_generic_expr (debug, var2, TDF_SLIM);
+ }
+ }
+ if (default_def)
+ {
+ if (SSA_NAME_IS_DEFAULT_DEF (var1))
+ bitmap_clear_bit (param_defaults, p1);
+ bitmap_set_bit (param_defaults, p2);
+ }
+ }
+
if (debug)
fprintf (debug, ": Success -> %d\n", z);
+
return true;
}
@@ -1190,7 +1333,7 @@ attempt_coalesce (var_map map, ssa_conflicts_p graph, int x, int y,
static void
coalesce_partitions (var_map map, ssa_conflicts_p graph, coalesce_list_p cl,
- FILE *debug)
+ bitmap param_defaults, FILE *debug)
{
int x = 0, y = 0;
tree var1, var2;
@@ -1226,7 +1369,7 @@ coalesce_partitions (var_map map, ssa_conflicts_p graph, coalesce_list_p cl,
if (debug)
fprintf (debug, "Abnormal coalesce: ");
- if (!attempt_coalesce (map, graph, v1, v2, debug))
+ if (!attempt_coalesce (map, graph, v1, v2, param_defaults, debug))
fail_abnormal_edge_coalesce (v1, v2);
}
}
@@ -1244,7 +1387,7 @@ coalesce_partitions (var_map map, ssa_conflicts_p graph, coalesce_list_p cl,
if (debug)
fprintf (debug, "Coalesce list: ");
- attempt_coalesce (map, graph, x, y, debug);
+ attempt_coalesce (map, graph, x, y, param_defaults, debug);
}
}
@@ -1272,6 +1415,178 @@ ssa_name_var_hash::equal (const value_type *n1, const compare_type *n2)
}
+/* Output partition map MAP with coalescing plan PART to file F. */
+
+void
+dump_part_var_map (FILE *f, partition part, var_map map)
+{
+ int t;
+ unsigned x, y;
+ int p;
+
+ fprintf (f, "\nCoalescible Partition map \n\n");
+
+ for (x = 0; x < map->num_partitions; x++)
+ {
+ if (map->view_to_partition != NULL)
+ p = map->view_to_partition[x];
+ else
+ p = x;
+
+ if (ssa_name (p) == NULL_TREE
+ || virtual_operand_p (ssa_name (p)))
+ continue;
+
+ t = 0;
+ for (y = 1; y < num_ssa_names; y++)
+ {
+ tree var = version_to_var (map, y);
+ if (!var)
+ continue;
+ int q = var_to_partition (map, var);
+ p = partition_find (part, q);
+ gcc_assert (map->partition_to_base_index[q]
+ == map->partition_to_base_index[p]);
+
+ if (p == (int)x)
+ {
+ if (t++ == 0)
+ {
+ fprintf (f, "Partition %d, base %d (", x,
+ map->partition_to_base_index[q]);
+ print_generic_expr (f, partition_to_var (map, q), TDF_SLIM);
+ fprintf (f, " - ");
+ }
+ fprintf (f, "%d ", y);
+ }
+ }
+ if (t != 0)
+ fprintf (f, ")\n");
+ }
+ fprintf (f, "\n");
+}
+
+/* Fill in MAP's partition_to_base_index, with one index for each
+ partition of SSA names USED_IN_COPIES and related by CL
+ coalesce possibilities. */
+
+static void
+compute_optimized_partition_bases (var_map map, bitmap used_in_copies,
+ coalesce_list_p cl)
+{
+ int parts = num_var_partitions (map);
+ partition tentative = partition_new (parts);
+
+ /* Partition the SSA versions so that, for each coalescible
+ pair, both of its members are in the same partition in
+ TENTATIVE. */
+ gcc_assert (!cl->sorted);
+ coalesce_pair_p node;
+ coalesce_iterator_type ppi;
+ FOR_EACH_PARTITION_PAIR (node, ppi, cl)
+ {
+ tree v1 = ssa_name (node->first_element);
+ int p1 = partition_find (tentative, var_to_partition (map, v1));
+ tree v2 = ssa_name (node->second_element);
+ int p2 = partition_find (tentative, var_to_partition (map, v2));
+
+ if (p1 == p2)
+ continue;
+
+ partition_union (tentative, p1, p2);
+ }
+
+ /* We have to deal with cost one pairs too. */
+ for (cost_one_pair_d *co = cl->cost_one_list; co; co = co->next)
+ {
+ tree v1 = ssa_name (co->first_element);
+ int p1 = partition_find (tentative, var_to_partition (map, v1));
+ tree v2 = ssa_name (co->second_element);
+ int p2 = partition_find (tentative, var_to_partition (map, v2));
+
+ if (p1 == p2)
+ continue;
+
+ partition_union (tentative, p1, p2);
+ }
+
+ /* And also with abnormal edges. */
+ basic_block bb;
+ edge e;
+ edge_iterator ei;
+ FOR_EACH_BB_FN (bb, cfun)
+ {
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ if (e->flags & EDGE_ABNORMAL)
+ {
+ gphi_iterator gsi;
+ for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
+ gsi_next (&gsi))
+ {
+ gphi *phi = gsi.phi ();
+ tree arg = PHI_ARG_DEF (phi, e->dest_idx);
+ if (SSA_NAME_IS_DEFAULT_DEF (arg)
+ && (!SSA_NAME_VAR (arg)
+ || TREE_CODE (SSA_NAME_VAR (arg)) != PARM_DECL))
+ continue;
+
+ tree res = PHI_RESULT (phi);
+
+ int p1 = partition_find (tentative, var_to_partition (map, res));
+ int p2 = partition_find (tentative, var_to_partition (map, arg));
+
+ if (p1 == p2)
+ continue;
+
+ partition_union (tentative, p1, p2);
+ }
+ }
+ }
+
+
+ map->partition_to_base_index = XCNEWVEC (int, parts);
+ auto_vec<unsigned int> index_map (parts);
+ if (parts)
+ index_map.quick_grow (parts);
+
+ const unsigned no_part = -1;
+ unsigned count = parts;
+ while (count)
+ index_map[--count] = no_part;
+
+ /* Initialize MAP's mapping from partition to base index, using
+ as base indices an enumeration of the TENTATIVE partitions in
+ which each SSA version ended up, so that we compute conflicts
+ between all SSA versions that ended up in the same potential
+ coalesce partition. */
+ bitmap_iterator bi;
+ unsigned i;
+ EXECUTE_IF_SET_IN_BITMAP (used_in_copies, 0, i, bi)
+ {
+ int pidx = var_to_partition (map, ssa_name (i));
+ int base = partition_find (tentative, pidx);
+ if (index_map[base] != no_part)
+ continue;
+ index_map[base] = count++;
+ }
+
+ map->num_basevars = count;
+
+ EXECUTE_IF_SET_IN_BITMAP (used_in_copies, 0, i, bi)
+ {
+ int pidx = var_to_partition (map, ssa_name (i));
+ int base = partition_find (tentative, pidx);
+ gcc_assert (index_map[base] < count);
+ map->partition_to_base_index[pidx] = index_map[base];
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ dump_part_var_map (dump_file, tentative, map);
+
+ partition_delete (tentative);
+}
+
+
/* Reduce the number of copies by coalescing variables in the function. Return
a partition map with the resulting coalesces. */
@@ -1332,7 +1647,12 @@ coalesce_ssa_name (void)
dump_var_map (dump_file, map);
/* Don't calculate live ranges for variables not in the coalesce list. */
- partition_view_bitmap (map, used_in_copies, true);
+ partition_view_bitmap (map, used_in_copies, !optimize);
+
+ /* If we are optimizing, compute the base indices ourselves. */
+ if (optimize)
+ compute_optimized_partition_bases (map, used_in_copies, cl);
+
BITMAP_FREE (used_in_copies);
if (num_var_partitions (map) < 1)
@@ -1341,6 +1661,8 @@ coalesce_ssa_name (void)
return map;
}
+ bitmap param_defaults = BITMAP_ALLOC (NULL);
+
if (dump_file && (dump_flags & TDF_DETAILS))
dump_var_map (dump_file, map);
@@ -1350,7 +1672,7 @@ coalesce_ssa_name (void)
dump_live_info (dump_file, liveinfo, LIVEDUMP_ENTRY);
/* Build a conflict graph. */
- graph = build_ssa_conflict_graph (liveinfo);
+ graph = build_ssa_conflict_graph (liveinfo, param_defaults);
delete_tree_live_info (liveinfo);
if (dump_file && (dump_flags & TDF_DETAILS))
ssa_conflicts_dump (dump_file, graph);
@@ -1370,10 +1692,10 @@ coalesce_ssa_name (void)
dump_var_map (dump_file, map);
/* Now coalesce everything in the list. */
- coalesce_partitions (map, graph, cl,
- ((dump_flags & TDF_DETAILS) ? dump_file
- : NULL));
+ coalesce_partitions (map, graph, cl, param_defaults,
+ ((dump_flags & TDF_DETAILS) ? dump_file : NULL));
+ BITMAP_FREE (param_defaults);
delete_coalesce_list (cl);
ssa_conflicts_delete (graph);
diff --git a/gcc/tree-ssa-copyrename.c b/gcc/tree-ssa-copyrename.c
deleted file mode 100644
index f3cb56e..0000000
--- a/gcc/tree-ssa-copyrename.c
+++ /dev/null
@@ -1,499 +0,0 @@
-/* Rename SSA copies.
- Copyright (C) 2004-2015 Free Software Foundation, Inc.
- Contributed by Andrew MacLeod <amacleod@redhat.com>
-
-This file is part of GCC.
-
-GCC is free software; you can redistribute it and/or modify
-it under the terms of the GNU General Public License as published by
-the Free Software Foundation; either version 3, or (at your option)
-any later version.
-
-GCC is distributed in the hope that it will be useful,
-but WITHOUT ANY WARRANTY; without even the implied warranty of
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-GNU General Public License for more details.
-
-You should have received a copy of the GNU General Public License
-along with GCC; see the file COPYING3. If not see
-<http://www.gnu.org/licenses/>. */
-
-#include "config.h"
-#include "system.h"
-#include "coretypes.h"
-#include "tm.h"
-#include "hash-set.h"
-#include "machmode.h"
-#include "vec.h"
-#include "double-int.h"
-#include "input.h"
-#include "alias.h"
-#include "symtab.h"
-#include "wide-int.h"
-#include "inchash.h"
-#include "tree.h"
-#include "fold-const.h"
-#include "predict.h"
-#include "hard-reg-set.h"
-#include "function.h"
-#include "dominance.h"
-#include "cfg.h"
-#include "basic-block.h"
-#include "tree-ssa-alias.h"
-#include "internal-fn.h"
-#include "gimple-expr.h"
-#include "is-a.h"
-#include "gimple.h"
-#include "gimple-iterator.h"
-#include "flags.h"
-#include "tree-pretty-print.h"
-#include "bitmap.h"
-#include "gimple-ssa.h"
-#include "stringpool.h"
-#include "tree-ssanames.h"
-#include "hashtab.h"
-#include "rtl.h"
-#include "statistics.h"
-#include "real.h"
-#include "fixed-value.h"
-#include "insn-config.h"
-#include "expmed.h"
-#include "dojump.h"
-#include "explow.h"
-#include "calls.h"
-#include "emit-rtl.h"
-#include "varasm.h"
-#include "stmt.h"
-#include "expr.h"
-#include "tree-dfa.h"
-#include "tree-inline.h"
-#include "tree-ssa-live.h"
-#include "tree-pass.h"
-#include "langhooks.h"
-
-static struct
-{
- /* Number of copies coalesced. */
- int coalesced;
-} stats;
-
-/* The following routines implement the SSA copy renaming phase.
-
- This optimization looks for copies between 2 SSA_NAMES, either through a
- direct copy, or an implicit one via a PHI node result and its arguments.
-
- Each copy is examined to determine if it is possible to rename the base
- variable of one of the operands to the same variable as the other operand.
- i.e.
- T.3_5 = <blah>
- a_1 = T.3_5
-
- If this copy couldn't be copy propagated, it could possibly remain in the
- program throughout the optimization phases. After SSA->normal, it would
- become:
-
- T.3 = <blah>
- a = T.3
-
- Since T.3_5 is distinct from all other SSA versions of T.3, there is no
- fundamental reason why the base variable needs to be T.3, subject to
- certain restrictions. This optimization attempts to determine if we can
- change the base variable on copies like this, and result in code such as:
-
- a_5 = <blah>
- a_1 = a_5
-
- This gives the SSA->normal pass a shot at coalescing a_1 and a_5. If it is
- possible, the copy goes away completely. If it isn't possible, a new temp
- will be created for a_5, and you will end up with the exact same code:
-
- a.8 = <blah>
- a = a.8
-
- The other benefit of performing this optimization relates to what variables
- are chosen in copies. Gimplification of the program uses temporaries for
- a lot of things. expressions like
-
- a_1 = <blah>
- <blah2> = a_1
-
- get turned into
-
- T.3_5 = <blah>
- a_1 = T.3_5
- <blah2> = a_1
-
- Copy propagation is done in a forward direction, and if we can propagate
- through the copy, we end up with:
-
- T.3_5 = <blah>
- <blah2> = T.3_5
-
- The copy is gone, but so is all reference to the user variable 'a'. By
- performing this optimization, we would see the sequence:
-
- a_5 = <blah>
- a_1 = a_5
- <blah2> = a_1
-
- which copy propagation would then turn into:
-
- a_5 = <blah>
- <blah2> = a_5
-
- and so we still retain the user variable whenever possible. */
-
-
-/* Coalesce the partitions in MAP representing VAR1 and VAR2 if it is valid.
- Choose a representative for the partition, and send debug info to DEBUG. */
-
-static void
-copy_rename_partition_coalesce (var_map map, tree var1, tree var2, FILE *debug)
-{
- int p1, p2, p3;
- tree root1, root2;
- tree rep1, rep2;
- bool ign1, ign2, abnorm;
-
- gcc_assert (TREE_CODE (var1) == SSA_NAME);
- gcc_assert (TREE_CODE (var2) == SSA_NAME);
-
- register_ssa_partition (map, var1);
- register_ssa_partition (map, var2);
-
- p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1));
- p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2));
-
- if (debug)
- {
- fprintf (debug, "Try : ");
- print_generic_expr (debug, var1, TDF_SLIM);
- fprintf (debug, "(P%d) & ", p1);
- print_generic_expr (debug, var2, TDF_SLIM);
- fprintf (debug, "(P%d)", p2);
- }
-
- gcc_assert (p1 != NO_PARTITION);
- gcc_assert (p2 != NO_PARTITION);
-
- if (p1 == p2)
- {
- if (debug)
- fprintf (debug, " : Already coalesced.\n");
- return;
- }
-
- rep1 = partition_to_var (map, p1);
- rep2 = partition_to_var (map, p2);
- root1 = SSA_NAME_VAR (rep1);
- root2 = SSA_NAME_VAR (rep2);
- if (!root1 && !root2)
- return;
-
- /* Don't coalesce if one of the variables occurs in an abnormal PHI. */
- abnorm = (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep1)
- || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep2));
- if (abnorm)
- {
- if (debug)
- fprintf (debug, " : Abnormal PHI barrier. No coalesce.\n");
- return;
- }
-
- /* Partitions already have the same root, simply merge them. */
- if (root1 == root2)
- {
- p1 = partition_union (map->var_partition, p1, p2);
- if (debug)
- fprintf (debug, " : Same root, coalesced --> P%d.\n", p1);
- return;
- }
-
- /* Never attempt to coalesce 2 different parameters. */
- if ((root1 && TREE_CODE (root1) == PARM_DECL)
- && (root2 && TREE_CODE (root2) == PARM_DECL))
- {
- if (debug)
- fprintf (debug, " : 2 different PARM_DECLS. No coalesce.\n");
- return;
- }
-
- if ((root1 && TREE_CODE (root1) == RESULT_DECL)
- != (root2 && TREE_CODE (root2) == RESULT_DECL))
- {
- if (debug)
- fprintf (debug, " : One root a RESULT_DECL. No coalesce.\n");
- return;
- }
-
- ign1 = !root1 || (TREE_CODE (root1) == VAR_DECL && DECL_IGNORED_P (root1));
- ign2 = !root2 || (TREE_CODE (root2) == VAR_DECL && DECL_IGNORED_P (root2));
-
- /* Refrain from coalescing user variables, if requested. */
- if (!ign1 && !ign2)
- {
- if (flag_ssa_coalesce_vars && DECL_FROM_INLINE (root2))
- ign2 = true;
- else if (flag_ssa_coalesce_vars && DECL_FROM_INLINE (root1))
- ign1 = true;
- else if (flag_ssa_coalesce_vars != 2)
- {
- if (debug)
- fprintf (debug, " : 2 different USER vars. No coalesce.\n");
- return;
- }
- else
- ign2 = true;
- }
-
- /* If both values have default defs, we can't coalesce. If only one has a
- tag, make sure that variable is the new root partition. */
- if (root1 && ssa_default_def (cfun, root1))
- {
- if (root2 && ssa_default_def (cfun, root2))
- {
- if (debug)
- fprintf (debug, " : 2 default defs. No coalesce.\n");
- return;
- }
- else
- {
- ign2 = true;
- ign1 = false;
- }
- }
- else if (root2 && ssa_default_def (cfun, root2))
- {
- ign1 = true;
- ign2 = false;
- }
-
- /* Do not coalesce if we cannot assign a symbol to the partition. */
- if (!(!ign2 && root2)
- && !(!ign1 && root1))
- {
- if (debug)
- fprintf (debug, " : Choosen variable has no root. No coalesce.\n");
- return;
- }
-
- /* Don't coalesce if the new chosen root variable would be read-only.
- If both ign1 && ign2, then the root var of the larger partition
- wins, so reject in that case if any of the root vars is TREE_READONLY.
- Otherwise reject only if the root var, on which replace_ssa_name_symbol
- will be called below, is readonly. */
- if (((root1 && TREE_READONLY (root1)) && ign2)
- || ((root2 && TREE_READONLY (root2)) && ign1))
- {
- if (debug)
- fprintf (debug, " : Readonly variable. No coalesce.\n");
- return;
- }
-
- /* Don't coalesce if the two variables aren't type compatible . */
- if (!types_compatible_p (TREE_TYPE (var1), TREE_TYPE (var2))
- /* There is a disconnect between the middle-end type-system and
- VRP, avoid coalescing enum types with different bounds. */
- || ((TREE_CODE (TREE_TYPE (var1)) == ENUMERAL_TYPE
- || TREE_CODE (TREE_TYPE (var2)) == ENUMERAL_TYPE)
- && TREE_TYPE (var1) != TREE_TYPE (var2)))
- {
- if (debug)
- fprintf (debug, " : Incompatible types. No coalesce.\n");
- return;
- }
-
- /* Merge the two partitions. */
- p3 = partition_union (map->var_partition, p1, p2);
-
- /* Set the root variable of the partition to the better choice, if there is
- one. */
- if (!ign2 && root2)
- replace_ssa_name_symbol (partition_to_var (map, p3), root2);
- else if (!ign1 && root1)
- replace_ssa_name_symbol (partition_to_var (map, p3), root1);
- else
- gcc_unreachable ();
-
- if (debug)
- {
- fprintf (debug, " --> P%d ", p3);
- print_generic_expr (debug, SSA_NAME_VAR (partition_to_var (map, p3)),
- TDF_SLIM);
- fprintf (debug, "\n");
- }
-}
-
-
-namespace {
-
-const pass_data pass_data_rename_ssa_copies =
-{
- GIMPLE_PASS, /* type */
- "copyrename", /* name */
- OPTGROUP_NONE, /* optinfo_flags */
- TV_TREE_COPY_RENAME, /* tv_id */
- ( PROP_cfg | PROP_ssa ), /* properties_required */
- 0, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- 0, /* todo_flags_finish */
-};
-
-class pass_rename_ssa_copies : public gimple_opt_pass
-{
-public:
- pass_rename_ssa_copies (gcc::context *ctxt)
- : gimple_opt_pass (pass_data_rename_ssa_copies, ctxt)
- {}
-
- /* opt_pass methods: */
- opt_pass * clone () { return new pass_rename_ssa_copies (m_ctxt); }
- virtual bool gate (function *) { return flag_tree_copyrename != 0; }
- virtual unsigned int execute (function *);
-
-}; // class pass_rename_ssa_copies
-
-/* This function will make a pass through the IL, and attempt to coalesce any
- SSA versions which occur in PHI's or copies. Coalescing is accomplished by
- changing the underlying root variable of all coalesced version. This will
- then cause the SSA->normal pass to attempt to coalesce them all to the same
- variable. */
-
-unsigned int
-pass_rename_ssa_copies::execute (function *fun)
-{
- var_map map;
- basic_block bb;
- tree var, part_var;
- gimple stmt;
- unsigned x;
- FILE *debug;
-
- memset (&stats, 0, sizeof (stats));
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- debug = dump_file;
- else
- debug = NULL;
-
- map = init_var_map (num_ssa_names);
-
- FOR_EACH_BB_FN (bb, fun)
- {
- /* Scan for real copies. */
- for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
- gsi_next (&gsi))
- {
- stmt = gsi_stmt (gsi);
- if (gimple_assign_ssa_name_copy_p (stmt))
- {
- tree lhs = gimple_assign_lhs (stmt);
- tree rhs = gimple_assign_rhs1 (stmt);
-
- copy_rename_partition_coalesce (map, lhs, rhs, debug);
- }
- }
- }
-
- FOR_EACH_BB_FN (bb, fun)
- {
- /* Treat PHI nodes as copies between the result and each argument. */
- for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
- gsi_next (&gsi))
- {
- size_t i;
- tree res;
- gphi *phi = gsi.phi ();
- res = gimple_phi_result (phi);
-
- /* Do not process virtual SSA_NAMES. */
- if (virtual_operand_p (res))
- continue;
-
- /* Make sure to only use the same partition for an argument
- as the result but never the other way around. */
- if (SSA_NAME_VAR (res)
- && !DECL_IGNORED_P (SSA_NAME_VAR (res)))
- for (i = 0; i < gimple_phi_num_args (phi); i++)
- {
- tree arg = PHI_ARG_DEF (phi, i);
- if (TREE_CODE (arg) == SSA_NAME)
- copy_rename_partition_coalesce (map, res, arg,
- debug);
- }
- /* Else if all arguments are in the same partition try to merge
- it with the result. */
- else
- {
- int all_p_same = -1;
- int p = -1;
- for (i = 0; i < gimple_phi_num_args (phi); i++)
- {
- tree arg = PHI_ARG_DEF (phi, i);
- if (TREE_CODE (arg) != SSA_NAME)
- {
- all_p_same = 0;
- break;
- }
- else if (all_p_same == -1)
- {
- p = partition_find (map->var_partition,
- SSA_NAME_VERSION (arg));
- all_p_same = 1;
- }
- else if (all_p_same == 1
- && p != partition_find (map->var_partition,
- SSA_NAME_VERSION (arg)))
- {
- all_p_same = 0;
- break;
- }
- }
- if (all_p_same == 1)
- copy_rename_partition_coalesce (map, res,
- PHI_ARG_DEF (phi, 0),
- debug);
- }
- }
- }
-
- if (debug)
- dump_var_map (debug, map);
-
- /* Now one more pass to make all elements of a partition share the same
- root variable. */
-
- for (x = 1; x < num_ssa_names; x++)
- {
- part_var = partition_to_var (map, x);
- if (!part_var)
- continue;
- var = ssa_name (x);
- if (SSA_NAME_VAR (var) == SSA_NAME_VAR (part_var))
- continue;
- if (debug)
- {
- fprintf (debug, "Coalesced ");
- print_generic_expr (debug, var, TDF_SLIM);
- fprintf (debug, " to ");
- print_generic_expr (debug, part_var, TDF_SLIM);
- fprintf (debug, "\n");
- }
- stats.coalesced++;
- replace_ssa_name_symbol (var, SSA_NAME_VAR (part_var));
- }
-
- statistics_counter_event (fun, "copies coalesced",
- stats.coalesced);
- delete_var_map (map);
- return 0;
-}
-
-} // anon namespace
-
-gimple_opt_pass *
-make_pass_rename_ssa_copies (gcc::context *ctxt)
-{
- return new pass_rename_ssa_copies (ctxt);
-}
diff --git a/gcc/tree-ssa-live.c b/gcc/tree-ssa-live.c
index e0c42669..46b1869 100644
--- a/gcc/tree-ssa-live.c
+++ b/gcc/tree-ssa-live.c
@@ -119,7 +119,10 @@ tree_int_map_hasher::equal (const value_type *v, const compare_type *c)
}
-/* This routine will initialize the basevar fields of MAP. */
+/* This routine will initialize the basevar fields of MAP with base
+ names, when we are not optimizing. When optimizing, we'll use
+ partition numbers as base index numbers, see coalesce_ssa_name in
+ tree-ssa-coalesce.c. */
static void
var_map_base_init (var_map map)
--
Alexandre Oliva, freedom fighter http://FSFLA.org/~lxoliva/
You must be the change you wish to see in the world. -- Gandhi
Be Free! -- http://FSFLA.org/ FSF Latin America board member
Free Software Evangelist|Red Hat Brasil GNU Toolchain Engineer