Improve uncprop and coalescing
Jeff Law
law@redhat.com
Fri Jun 7 06:08:00 GMT 2013
I stumbled over this while looking at regressions triggered when moving
certain branch-cost driven transformations from fold-const.c to a later
point in the pipeline.
The coalescing we do as part of the out-of-ssa process restricts itself
to only coalescing when the types of the underlying objects are the
same. Where same is currently defined as pointer equality on the type.
So if we have a copy or PHI node where the source & dest have
equivalent, but different types we will not currently coalesce the
source and destination.
We also have a pass which un-propagates certain equivalences appearing
as PHI args when the equivalence is derived from conditionals. This
un-propagation pass is primarily meant to improve coalescing and
ultimately eliminate silly constant initializations and useless copies.
That pass also used pointer equality of types when determining if
unpropagation was profitable.
Rather than using strict pointer equality, we can do better by looking
at TYPE_CANONICAL when it's available. Thus objects of the following
two types (T1 & T2) become candidates for coalescing if they are tied
together by a copy or PHI node.
typedef int t1;
typedef int t2;
This typically eliminates necessary copies and constant initializations,
which is good. The only regression I saw when reviewing the generated
code & dumps was a case where we got different register allocation on
one path which in turn inhibited a tail merging opportunity.
Bootstrapped and regression tested on x86_64-linux-gnu. OK for the trunk?
-------------- next part --------------
* gimple.h (gimple_can_coalesce_p): Prototype.
* tree-ssa-coalesce.c (gimple_can_coalesce_p): New function.
(create_outofssa_var_map, coalesce_partitions): Use it.
* tree-ssa-uncprop.c (uncprop_into_successor_phis): Similarly.
* tree-ssa-live.c (var_map_base_init): Use TYPE_CANONICAL
if it's available.
* gcc.dg/tree-ssa/coalesce-1.c: New test.
diff --git a/gcc/gimple.h b/gcc/gimple.h
index b4de403..8ae07c9 100644
--- a/gcc/gimple.h
+++ b/gcc/gimple.h
@@ -1101,6 +1101,9 @@ extern tree tree_ssa_strip_useless_type_conversions (tree);
extern bool useless_type_conversion_p (tree, tree);
extern bool types_compatible_p (tree, tree);
+/* In tree-ssa-coalesce.c */
+extern bool gimple_can_coalesce_p (tree, tree);
+
/* Return the first node in GIMPLE sequence S. */
static inline gimple_seq_node
diff --git a/gcc/tree-ssa-coalesce.c b/gcc/tree-ssa-coalesce.c
index 354b5f1..42bea5d 100644
--- a/gcc/tree-ssa-coalesce.c
+++ b/gcc/tree-ssa-coalesce.c
@@ -943,8 +943,7 @@ create_outofssa_var_map (coalesce_list_p cl, bitmap used_in_copy)
continue;
register_ssa_partition (map, arg);
- if ((SSA_NAME_VAR (arg) == SSA_NAME_VAR (res)
- && TREE_TYPE (arg) == TREE_TYPE (res))
+ if (gimple_can_coalesce_p (arg, res)
|| (e->flags & EDGE_ABNORMAL))
{
saw_copy = true;
@@ -985,8 +984,7 @@ create_outofssa_var_map (coalesce_list_p cl, bitmap used_in_copy)
if (gimple_assign_copy_p (stmt)
&& TREE_CODE (lhs) == SSA_NAME
&& TREE_CODE (rhs1) == SSA_NAME
- && SSA_NAME_VAR (lhs) == SSA_NAME_VAR (rhs1)
- && TREE_TYPE (lhs) == TREE_TYPE (rhs1))
+ && gimple_can_coalesce_p (lhs, rhs1))
{
v1 = SSA_NAME_VERSION (lhs);
v2 = SSA_NAME_VERSION (rhs1);
@@ -1037,8 +1035,7 @@ create_outofssa_var_map (coalesce_list_p cl, bitmap used_in_copy)
v1 = SSA_NAME_VERSION (outputs[match]);
v2 = SSA_NAME_VERSION (input);
- if (SSA_NAME_VAR (outputs[match]) == SSA_NAME_VAR (input)
- && TREE_TYPE (outputs[match]) == TREE_TYPE (input))
+ if (gimple_can_coalesce_p (outputs[match], input))
{
cost = coalesce_cost (REG_BR_PROB_BASE,
optimize_bb_for_size_p (bb));
@@ -1072,8 +1069,7 @@ create_outofssa_var_map (coalesce_list_p cl, bitmap used_in_copy)
first = var;
else
{
- gcc_assert (SSA_NAME_VAR (var) == SSA_NAME_VAR (first)
- && TREE_TYPE (var) == TREE_TYPE (first));
+ gcc_assert (gimple_can_coalesce_p (var, first));
v1 = SSA_NAME_VERSION (first);
v2 = SSA_NAME_VERSION (var);
bitmap_set_bit (used_in_copy, v1);
@@ -1210,8 +1206,7 @@ coalesce_partitions (var_map map, ssa_conflicts_p graph, coalesce_list_p cl,
var2 = ssa_name (y);
/* Assert the coalesces have the same base variable. */
- gcc_assert (SSA_NAME_VAR (var1) == SSA_NAME_VAR (var2)
- && TREE_TYPE (var1) == TREE_TYPE (var2));
+ gcc_assert (gimple_can_coalesce_p (var1, var2));
if (debug)
fprintf (debug, "Coalesce list: ");
@@ -1341,3 +1336,32 @@ coalesce_ssa_name (void)
return map;
}
+/* Given SSA_NAMEs NAME1 and NAME2, return true if they are candidates for
+ coalescing together, false otherwise.
+
+ This must stay consistent with the code in tree-ssa-live.c which
+ sets up base values in the var map. */
+
+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. */
+ if (SSA_NAME_VAR (name1) != SSA_NAME_VAR (name2))
+ return false;
+
+ /* Now check the types. If the types are the same, then we should
+ try to coalesce V1 and V2. */
+ tree t1 = TREE_TYPE (name1);
+ tree t2 = TREE_TYPE (name2);
+ if (t1 == t2)
+ return true;
+
+ /* If the types are not the same, check for a canonical type match. This
+ (for example) allows coalescing when the types are fundamentally the
+ same, but just have different names. */
+ if (TYPE_CANONICAL (t1) && TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2))
+ return true;
+
+ return false;
+}
diff --git a/gcc/tree-ssa-live.c b/gcc/tree-ssa-live.c
index 83a52a0..a624d00 100644
--- a/gcc/tree-ssa-live.c
+++ b/gcc/tree-ssa-live.c
@@ -111,8 +111,12 @@ var_map_base_init (var_map map)
as it restricts the sets we compute conflicts for.
Using TREE_TYPE to generate sets is the easies as
type equivalency also holds for SSA names with the same
- underlying decl. */
- m->base.from = TREE_TYPE (var);
+ underlying decl.
+
+ Check gimple_can_coalesce_p when changing this code. */
+ m->base.from = (TYPE_CANONICAL (TREE_TYPE (var))
+ ? TYPE_CANONICAL (TREE_TYPE (var))
+ : TREE_TYPE (var));
/* If base variable hasn't been seen, set it up. */
slot = tree_to_index.find_slot (m, INSERT);
if (!*slot)
diff --git a/gcc/tree-ssa-uncprop.c b/gcc/tree-ssa-uncprop.c
index 1fbc524..555485a 100644
--- a/gcc/tree-ssa-uncprop.c
+++ b/gcc/tree-ssa-uncprop.c
@@ -474,12 +474,11 @@ uncprop_into_successor_phis (basic_block bb)
equiv_hash_elt an_equiv_elt;
equiv_hash_elt **slot;
- /* If the argument is not an invariant, and refers to the same
- underlying variable as the PHI result, then there's no
- point in un-propagating the argument. */
+ /* If the argument is not an invariant and can be potentially
+ coalesced with the result, then there's no point in
+ un-propagating the argument. */
if (!is_gimple_min_invariant (arg)
- && (SSA_NAME_VAR (arg) == SSA_NAME_VAR (res)
- && TREE_TYPE (arg) == TREE_TYPE (res)))
+ && gimple_can_coalesce_p (arg, res))
continue;
/* Lookup this argument's value in the hash table. */
@@ -493,7 +492,7 @@ uncprop_into_successor_phis (basic_block bb)
int j;
/* Walk every equivalence with the same value. If we find
- one with the same underlying variable as the PHI result,
+ one that can potentially coalesce with the PHI rsult,
then replace the value in the argument with its equivalent
SSA_NAME. Use the most recent equivalence as hopefully
that results in shortest lifetimes. */
@@ -501,8 +500,7 @@ uncprop_into_successor_phis (basic_block bb)
{
tree equiv = elt->equivalences[j];
- if (SSA_NAME_VAR (equiv) == SSA_NAME_VAR (res)
- && TREE_TYPE (equiv) == TREE_TYPE (res))
+ if (gimple_can_coalesce_p (equiv, res))
{
SET_PHI_ARG_DEF (phi, e->dest_idx, equiv);
break;
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/coalesce-1.c b/gcc/testsuite/gcc.dg/tree-ssa/coalesce-1.c
new file mode 100644
index 0000000..5cae9ae
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/coalesce-1.c
@@ -0,0 +1,195 @@
+/* { dg-do compile } */
+
+/* { dg-options "-O2 -fdump-rtl-expand-details" } */
+
+typedef long unsigned int size_t;
+union tree_node;
+typedef union tree_node *tree;
+union gimple_statement_d;
+typedef union gimple_statement_d *gimple;
+typedef const union tree_node *const_tree;
+typedef const union gimple_statement_d *const_gimple;
+struct gimple_seq_d;
+typedef struct gimple_seq_d *gimple_seq;
+struct edge_def;
+typedef struct edge_def *edge;
+struct basic_block_def;
+typedef struct basic_block_def *basic_block;
+typedef const struct basic_block_def *const_basic_block;
+struct tree_exp
+{
+ tree operands[1];
+};
+typedef struct ssa_use_operand_d
+{
+ tree *use;
+} ssa_use_operand_t;
+struct phi_arg_d
+{
+ struct ssa_use_operand_d imm_use;
+};
+union tree_node
+{
+ struct tree_exp exp;
+};
+struct function
+{
+};
+extern struct function *cfun;
+struct edge_def
+{
+ unsigned int dest_idx;
+};
+static __inline__ void
+VEC_edge_must_be_pointer_type (void)
+{
+ (void) ((edge) 1 == (void *) 1);
+} typedef struct VEC_edge_base
+
+{
+ unsigned num;
+ unsigned alloc;
+ edge vec[1];
+} VEC_edge_base;
+typedef struct VEC_edge_none
+{
+ VEC_edge_base base;
+} VEC_edge_none;
+
+static __inline__ edge
+VEC_edge_base_index (const VEC_edge_base * vec_, unsigned ix_,
+ const char *file_, unsigned line_, const char *function_)
+{
+ return vec_->vec[ix_];
+}
+
+typedef struct VEC_edge_gc
+{
+ VEC_edge_base base;
+} VEC_edge_gc;
+struct basic_block_def
+{
+ VEC_edge_gc *succs;
+};
+static __inline__ edge
+single_succ_edge (const_basic_block bb)
+{
+ return (VEC_edge_base_index
+ ((((bb)->succs) ? &((bb)->succs)->base : 0), (0),
+ "/home/gcc/virgin-gcc/gcc/basic-block.h", 563, __FUNCTION__));
+}
+
+edge find_edge (basic_block, basic_block);
+typedef tree *def_operand_p;
+typedef ssa_use_operand_t *use_operand_p;
+struct gimple_seq_node_d;
+typedef struct gimple_seq_node_d *gimple_seq_node;
+struct gimple_seq_node_d
+{
+ gimple stmt;
+};
+typedef struct
+{
+ gimple_seq_node ptr;
+ gimple_seq seq;
+ basic_block bb;
+} gimple_stmt_iterator;
+struct gimple_statement_phi
+{
+ struct phi_arg_d args[1];
+};
+union gimple_statement_d
+{
+ struct gimple_statement_phi gimple_phi;
+};
+extern size_t const gimple_ops_offset_[];
+static __inline__ tree *
+gimple_ops (gimple gs)
+{
+ size_t off;
+ off = gimple_ops_offset_[gimple_statement_structure (gs)];
+ return (tree *) ((char *) gs + off);
+}
+
+static __inline__ tree
+gimple_op (const_gimple gs, unsigned i)
+{
+ return gimple_ops ((((union
+ {
+ const union gimple_statement_d * _q;
+ union gimple_statement_d * _nq;}) (((gs))))._nq))[i];
+}
+
+static __inline__ struct phi_arg_d *
+gimple_phi_arg (gimple gs, unsigned index)
+{
+ return &(gs->gimple_phi.args[index]);
+}
+
+static __inline__ tree
+gimple_switch_label (const_gimple gs, unsigned index)
+{
+ return gimple_op (gs, index + 1);
+}
+
+gimple_stmt_iterator gsi_start_phis (basic_block);
+extern basic_block label_to_block_fn (struct function *, tree);
+
+static __inline__ tree
+get_use_from_ptr (use_operand_p use)
+{
+ return *(use->use);
+}
+
+static __inline__ use_operand_p
+gimple_phi_arg_imm_use_ptr (gimple gs, int i)
+{
+ return &gimple_phi_arg (gs, i)->imm_use;
+}
+
+struct switch_conv_info
+{
+ basic_block final_bb;
+ basic_block switch_bb;
+ const char *reason;
+ tree *default_values;
+};
+static struct switch_conv_info info;
+
+static void
+gather_default_values (tree default_case)
+{
+ gimple_stmt_iterator gsi;
+ basic_block bb =
+ (label_to_block_fn ((cfun + 0), default_case->exp.operands[2]));
+ edge e;
+ int i = 0;
+ if (bb == info.final_bb)
+ e = find_edge (info.switch_bb, bb);
+ else
+ e = single_succ_edge (bb);
+ for (gsi = gsi_start_phis (info.final_bb);
+ gsi_gsi_start_phis (info.final_bb); gsi_next (&gsi))
+ {
+ gimple phi = gsi.ptr->stmt;
+ tree val = get_use_from_ptr (gimple_phi_arg_imm_use_ptr
+ ((((phi))), (((e)->dest_idx))));
+ info.default_values[i++] = val;
+ }
+}
+
+unsigned char
+process_switch (gimple swtch)
+{
+ unsigned int i, branch_num = gimple_switch_num_labels (swtch);
+ tree index_type;
+ info.reason = "switch has no labels\n";
+ gather_default_values (gimple_switch_label (swtch, 0));
+}
+
+/* Verify that out-of-ssa coalescing did its job by verifying there are not
+ any partition copies inserted. */
+
+/* { dg-final { scan-rtl-dump-not "partition copy" "expand"} } */
+/* { dg-final { cleanup-rtl-dump "expand" } } */
+
More information about the Gcc-patches
mailing list