| Message ID | 51B178BA.1000802@redhat.com |
|---|---|
| State | New |
| Headers | show |
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
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" } } */ > + >
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
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
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
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 > >
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" } } */ +