* Improve uncprop and coalescing
@ 2013-06-07 6:08 Jeff Law
2013-06-07 8:30 ` Steven Bosscher
2013-06-07 9:14 ` Richard Biener
0 siblings, 2 replies; 7+ messages in thread
From: Jeff Law @ 2013-06-07 6:08 UTC (permalink / raw)
To: gcc-patches
[-- Attachment #1: Type: text/plain, Size: 1564 bytes --]
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?
[-- Attachment #2: patch --]
[-- Type: text/plain, Size: 11272 bytes --]
* 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" } } */
+
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: Improve uncprop and coalescing
2013-06-07 6:08 Improve uncprop and coalescing Jeff Law
@ 2013-06-07 8:30 ` Steven Bosscher
2013-06-07 12:50 ` Jeff Law
2013-06-07 9:14 ` Richard Biener
1 sibling, 1 reply; 7+ messages in thread
From: Steven Bosscher @ 2013-06-07 8:30 UTC (permalink / raw)
To: Jeff Law; +Cc: gcc-patches
On Fri, Jun 7, 2013 at 8:07 AM, Jeff Law wrote:
> 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.
Hmm... Can't you use types_compatible_p?
Ciao!
Steven
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: Improve uncprop and coalescing
2013-06-07 6:08 Improve uncprop and coalescing Jeff Law
2013-06-07 8:30 ` Steven Bosscher
@ 2013-06-07 9:14 ` Richard Biener
2013-06-12 4:44 ` Jeff Law
2013-06-12 16:04 ` Jeff Law
1 sibling, 2 replies; 7+ messages in thread
From: Richard Biener @ 2013-06-07 9:14 UTC (permalink / raw)
To: Jeff Law; +Cc: gcc-patches
On Fri, Jun 7, 2013 at 8:07 AM, Jeff Law <law@redhat.com> wrote:
>
> 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?
>
>
>
>
> * 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;
> }
Missing vertical space here
> +/* 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))
Please use types_compatible_p (t1, t2) here, that's the correct API to use
here.
> + 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));
eh, but it's made complicated here ... so above do
if (TYPE_CANONICAL (t1) && TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2)
&& types_compatible_p (t1, t2))
because looking at useless_type_conversion_p it looks like pointer types
with different address-spaces may have the same canonical type. A comment
on why we check both, refering to var_map_base_init should also be added.
Ok with that change.
Thanks,
Richard.
> /* 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" } } */
> +
>
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: Improve uncprop and coalescing
2013-06-07 8:30 ` Steven Bosscher
@ 2013-06-07 12:50 ` Jeff Law
0 siblings, 0 replies; 7+ messages in thread
From: Jeff Law @ 2013-06-07 12:50 UTC (permalink / raw)
To: Steven Bosscher; +Cc: gcc-patches
On 06/07/13 02:30, Steven Bosscher wrote:
> On Fri, Jun 7, 2013 at 8:07 AM, Jeff Law wrote:
>> 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.
>
> Hmm... Can't you use types_compatible_p?
No. That was my first inclination.
jeff
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: Improve uncprop and coalescing
2013-06-07 9:14 ` Richard Biener
@ 2013-06-12 4:44 ` Jeff Law
2013-06-12 16:04 ` Jeff Law
1 sibling, 0 replies; 7+ messages in thread
From: Jeff Law @ 2013-06-12 4:44 UTC (permalink / raw)
To: Richard Biener; +Cc: gcc-patches
On 06/07/13 03:14, Richard Biener wrote:
>
>
>> +/* 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))
>
> Please use types_compatible_p (t1, t2) here, that's the correct API to use
> here.
No it isn't. types_compatible_p is far too permissive in this context
without more surgery to tree-ssa-live.c.
So let's take two objects, P1 and P2 which are pointers to types T1 and
T2 where T1 != T2. Assume P1 and P2 are somehow connected by a copy or
PHI node and that they are anonymously named objects.
types_compatible_p will return true for (T1, T2) unless T1 or T2 is a
pointer to a function. So if we used types_compatible_p we will try to
coalesce P1 and P2 (which is seemingly a good thing).
Now in tree-ssa-live.c::var_map_base_init we have:
/* Build the base variable list, and point partitions at their bases. */
for (x = 0; x < num_part; x++)
{
...
if (SSA_NAME_VAR (var))
m->base.from = SSA_NAME_VAR (var);
else
/* This restricts what anonymous SSA names we can coalesce
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);
...
}
The way we set up base.from in var_map_base_init imposes requirements on
what objects can be added to the coalescing lists. We can only allow
coalescing of objects with the same underlying SSA_NAME_VAR or anonymous
objects with the same underlying TREE_TYPE (as the code is written
today). That's a side effect of restricting the sets we compute
conflicts for. If we don't compute the conflicts, then we'll assume P1
and P2 don't conflict and happily coalesce them, regardless of whether
or not they actually do conflict.
To use types_compatible_p to drive decisions in tree-ssa-coalesce.c,
ISTM we'd have to change this code from tree-ssa-live.c to put all
anonymous objects with a compatible type in the same hash entry. I
don't see a good way to do that without iterating over the hash table
entries looking for a compatible match or completely reimplementing the
hash.
By first checking if an anonymous variable's type has an underlying
canonical type and using that instead to key decisions in
var_map_base_init, we can allow more objects onto the coalescing lists
in tree-ssa-coalesce.c. In particular we can allow two anonymous
objects where both have an underlying TYPE_CANONICAL that is the same.
>
>
> if (TYPE_CANONICAL (t1) && TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2)
> && types_compatible_p (t1, t2))
>
> because looking at useless_type_conversion_p it looks like pointer types
> with different address-spaces may have the same canonical type. A comment
> on why we check both, refering to var_map_base_init should also be added.
>
> Ok with that change.
Seems to make sense. Though we still have a point of contention around
whether or not we can use types_compatible_p to drive decisions in
tree-ssa-coalesce.c. I'm pretty sure we can't without some significant
surgery in tree-ssa-live.c.
Jeff
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: Improve uncprop and coalescing
2013-06-07 9:14 ` Richard Biener
2013-06-12 4:44 ` Jeff Law
@ 2013-06-12 16:04 ` Jeff Law
2013-08-30 10:06 ` Richard Biener
1 sibling, 1 reply; 7+ messages in thread
From: Jeff Law @ 2013-06-12 16:04 UTC (permalink / raw)
To: Richard Biener; +Cc: gcc-patches
On 06/07/13 03:14, Richard Biener wrote:
>> +/* 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))
>
> Please use types_compatible_p (t1, t2) here, that's the correct API to use
> here.
>
>> + 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));
>
> eh, but it's made complicated here ... so above do
>
>
> if (TYPE_CANONICAL (t1) && TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2)
> && types_compatible_p (t1, t2))
>
> because looking at useless_type_conversion_p it looks like pointer types
> with different address-spaces may have the same canonical type. A comment
> on why we check both, refering to var_map_base_init should also be added.
Reading this again after a night of sleep, it appears you're agreeing
that we can't just use types_compatible_p to drive what objects are put
on the coalesce list. The only code change you're asking for is to make
sure we properly reject pointer types with different address spaces
(which can be done via types_compatible_p).
Right?
jeff
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: Improve uncprop and coalescing
2013-06-12 16:04 ` Jeff Law
@ 2013-08-30 10:06 ` Richard Biener
0 siblings, 0 replies; 7+ messages in thread
From: Richard Biener @ 2013-08-30 10:06 UTC (permalink / raw)
To: Jeff Law; +Cc: gcc-patches
On Wed, Jun 12, 2013 at 6:04 PM, Jeff Law <law@redhat.com> wrote:
>
> On 06/07/13 03:14, Richard Biener wrote:
>
>>> +/* 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))
>>
>>
>> Please use types_compatible_p (t1, t2) here, that's the correct API to use
>> here.
>>
>>> + 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));
>>
>>
>> eh, but it's made complicated here ... so above do
>>
>>
>> if (TYPE_CANONICAL (t1) && TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2)
>> && types_compatible_p (t1, t2))
>>
>> because looking at useless_type_conversion_p it looks like pointer types
>> with different address-spaces may have the same canonical type. A comment
>> on why we check both, refering to var_map_base_init should also be added.
>
> Reading this again after a night of sleep, it appears you're agreeing that
> we can't just use types_compatible_p to drive what objects are put on the
> coalesce list. The only code change you're asking for is to make sure we
> properly reject pointer types with different address spaces (which can be
> done via types_compatible_p).
>
>
> Right?
Yes, if I remember correctly after this long time ;)
Richard.
> jeff
>
>
^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2013-08-30 9:50 UTC | newest]
Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2013-06-07 6:08 Improve uncprop and coalescing Jeff Law
2013-06-07 8:30 ` Steven Bosscher
2013-06-07 12:50 ` Jeff Law
2013-06-07 9:14 ` Richard Biener
2013-06-12 4:44 ` Jeff Law
2013-06-12 16:04 ` Jeff Law
2013-08-30 10:06 ` Richard Biener
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).