From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 24994 invoked by alias); 7 Jun 2013 09:14:26 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 24978 invoked by uid 89); 7 Jun 2013 09:14:23 -0000 X-Spam-SWARE-Status: No, score=-3.2 required=5.0 tests=AWL,BAYES_00,FREEMAIL_FROM,KHOP_THREADED,RCVD_IN_DNSWL_LOW,RCVD_IN_HOSTKARMA_YE,SPF_PASS,TW_TM autolearn=ham version=3.3.1 Received: from mail-wi0-f173.google.com (HELO mail-wi0-f173.google.com) (209.85.212.173) by sourceware.org (qpsmtpd/0.84/v0.84-167-ge50287c) with ESMTP; Fri, 07 Jun 2013 09:14:21 +0000 Received: by mail-wi0-f173.google.com with SMTP id hi5so1152178wib.12 for ; Fri, 07 Jun 2013 02:14:19 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.194.104.105 with SMTP id gd9mr35205920wjb.1.1370596459513; Fri, 07 Jun 2013 02:14:19 -0700 (PDT) Received: by 10.194.19.168 with HTTP; Fri, 7 Jun 2013 02:14:19 -0700 (PDT) In-Reply-To: <51B178BA.1000802@redhat.com> References: <51B178BA.1000802@redhat.com> Date: Fri, 07 Jun 2013 09:14:00 -0000 Message-ID: Subject: Re: Improve uncprop and coalescing From: Richard Biener To: Jeff Law Cc: gcc-patches Content-Type: text/plain; charset=ISO-8859-1 X-SW-Source: 2013-06/txt/msg00384.txt.bz2 On Fri, Jun 7, 2013 at 8:07 AM, Jeff Law 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" } } */ > + >