From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 111856 invoked by alias); 30 May 2019 16:20:41 -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 111848 invoked by uid 89); 30 May 2019 16:20:40 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-17.0 required=5.0 tests=AWL,BAYES_00,GIT_PATCH_0,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,SPF_PASS autolearn=ham version=3.3.1 spammy=H*UA:https, picked, dse1, teaching X-HELO: mx1.suse.de Received: from mx2.suse.de (HELO mx1.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Thu, 30 May 2019 16:20:37 +0000 X-Amavis-Alert: BAD HEADER SECTION, Duplicate header field: "Cc" Received: from relay2.suse.de (unknown [195.135.220.254]) by mx1.suse.de (Postfix) with ESMTP id 952F4AFE7; Thu, 30 May 2019 16:20:35 +0000 (UTC) From: Martin Jambor To: Jan Hubicka , Richard Biener Cc: Richard Biener , GCC Patches , d@dcepelik.cz Cc: Subject: Re: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors In-Reply-To: <20190529140804.bfxc7c3t3xgd5avy@kam.mff.cuni.cz> References: <20190524111433.mv5z33ysiatlxmxz@kam.mff.cuni.cz> <20190524131856.zduvz27dbjfy6yqw@kam.mff.cuni.cz> <20190527082804.uxp3ugxulvdray5z@kam.mff.cuni.cz> <20190529132057.ivcrg3upxubuaazh@kam.mff.cuni.cz> <20190529140804.bfxc7c3t3xgd5avy@kam.mff.cuni.cz> User-Agent: Notmuch/0.28.4 (https://notmuchmail.org) Emacs/26.2 (x86_64-suse-linux-gnu) Date: Thu, 30 May 2019 16:23:00 -0000 Message-ID: MIME-Version: 1.0 Content-Type: text/plain X-IsSubscribed: yes X-SW-Source: 2019-05/txt/msg02027.txt.bz2 Hi, On Wed, May 29 2019, Jan Hubicka wrote: >> > but we do not optimize it. I.e. optimized dump has: >> > >> > test () >> > { >> > struct bar * barptr.0_1; >> > struct foo * fooptr.1_2; >> > int _6; >> > >> > [local count: 1073741824]: >> > barptr.0_1 = barptr; >> > barptr.0_1->val2 = 1; >> > fooptr.1_2 = fooptr; >> > MEM[(struct foo *)fooptr.1_2] = 0; >> > _6 = barptr.0_1->val2; >> > return _6; >> > } >> > >> > I see no reason why we should not constant propagate the return value. >> >> Indeed a good example. Make it work and add it to the testsuite ;) > > I think Martin Jambor is working on it. One needs -fno-tree-sra to > get this optimized :) > Othewise we punt on the check that both types in MEM_REF are the same. > I'd like to fix this with the following patch which passes bootstrap but I have just found that it makes the following three tests fail: gcc.dg/tree-ssa/ssa-dse-26.c scan-tree-dump-times dse1 "Deleted dead store: x = " 1 gcc.dg/tree-ssa/ssa-dse-26.c scan-tree-dump-times dse1 "Deleted dead store: y = " 1 gnat.dg/opt39.adb scan-tree-dump-times optimized "MEM" 1 Hopefully all require only adjusting the testcase somehow, but it's still something I need to look at tomorrow. The patch can then be incrementally improved to also work with one-element arrays which are however indexed with an SSA_NAME. As far as alias oracle statistics are concerned, the patch (on top of r271763) improves from: Alias oracle query stats: refs_may_alias_p: 3792598 disambiguations, 4181030 queries ref_maybe_used_by_call_p: 8291 disambiguations, 3829922 queries call_may_clobber_ref_p: 1092 disambiguations, 1092 queries aliasing_component_ref_p: 192 disambiguations, 18684 queries TBAA oracle: 1820750 disambiguations 3584527 queries 778806 are in alias set 0 723538 queries asked about the same object 0 queries asked about the same alias set 0 access volatile 261267 are dependent in the DAG 166 are aritificially in conflict with void * to: Alias oracle query stats: refs_may_alias_p: 3786679 disambiguations, 4174429 queries ref_maybe_used_by_call_p: 8285 disambiguations, 3824058 queries call_may_clobber_ref_p: 1092 disambiguations, 1092 queries aliasing_component_ref_p: 362 disambiguations, 19215 queries TBAA oracle: 1822975 disambiguations 3579314 queries 775069 are in alias set 0 727061 queries asked about the same object 0 queries asked about the same alias set 0 access volatile 254043 are dependent in the DAG 166 are aritificially in conflict with void * Martin Subject: [PATCH] Make SRA re-construct orginal memory accesses when easy 2019-05-30 Martin Jambor * tree-sra.c (struct access): New field grp_same_access_path. (dump_access): Dump it. (build_reconstructed_reference): New function. (build_ref_for_model): Use it if possible. (path_comparable_for_same_access): New function. (same_access_path_p): Likewise. (sort_and_splice_var_accesses): Set the new flag. (analyze_access_subtree): Likewise. (propagate_subaccesses_across_link): Propagate zero value of the new flag down the access tree. testsuite/ * gcc.dg/tree-ssa/alias-access-path-1.c: Remove -fno-tree-sra option. --- .../gcc.dg/tree-ssa/alias-access-path-1.c | 2 +- gcc/tree-sra.c | 197 +++++++++++++++++- 2 files changed, 190 insertions(+), 9 deletions(-) diff --git a/gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-1.c b/gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-1.c index 264f72aff0a..ba90b56fe5c 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-1.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-1.c @@ -1,5 +1,5 @@ /* { dg-do compile } */ -/* { dg-options "-O2 -fdump-tree-fre3 -fno-tree-sra" } */ +/* { dg-options "-O2 -fdump-tree-fre3" } */ struct foo { int val; diff --git a/gcc/tree-sra.c b/gcc/tree-sra.c index fd51a3d0323..dc2a776d66c 100644 --- a/gcc/tree-sra.c +++ b/gcc/tree-sra.c @@ -242,6 +242,10 @@ struct access access tree. */ unsigned grp_unscalarized_data : 1; + /* Set if all accesses in the group consist of the same chain of + COMPONENT_REFs and ARRAY_REFs. */ + unsigned grp_same_access_path : 1; + /* Does this access and/or group contain a write access through a BIT_FIELD_REF? */ unsigned grp_partial_lhs : 1; @@ -443,16 +447,18 @@ dump_access (FILE *f, struct access *access, bool grp) "grp_scalar_write = %d, grp_total_scalarization = %d, " "grp_hint = %d, grp_covered = %d, " "grp_unscalarizable_region = %d, grp_unscalarized_data = %d, " - "grp_partial_lhs = %d, grp_to_be_replaced = %d, " - "grp_to_be_debug_replaced = %d, grp_maybe_modified = %d, " + "grp_same_access_path = %d, grp_partial_lhs = %d, " + "grp_to_be_replaced = %d, grp_to_be_debug_replaced = %d, " + "grp_maybe_modified = %d, " "grp_not_necessarilly_dereferenced = %d\n", access->grp_read, access->grp_write, access->grp_assignment_read, access->grp_assignment_write, access->grp_scalar_read, access->grp_scalar_write, access->grp_total_scalarization, access->grp_hint, access->grp_covered, access->grp_unscalarizable_region, access->grp_unscalarized_data, - access->grp_partial_lhs, access->grp_to_be_replaced, - access->grp_to_be_debug_replaced, access->grp_maybe_modified, + access->grp_same_access_path, access->grp_partial_lhs, + access->grp_to_be_replaced, access->grp_to_be_debug_replaced, + access->grp_maybe_modified, access->grp_not_necessarilly_dereferenced); else fprintf (f, ", write = %d, grp_total_scalarization = %d, " @@ -1795,6 +1801,41 @@ build_ref_for_offset (location_t loc, tree base, poly_int64 offset, return mem_ref; } +/* Construct and return a memory reference that is equal to a portion of + MODEL->expr but is based on BASE. If this cannot be done, return NULL. */ + +static tree +build_reconstructed_reference (location_t loc, tree base, struct access *model) +{ + auto_vec model_comps; + tree expr = model->expr; + while (!types_compatible_p (TREE_TYPE (expr), TREE_TYPE (base))) + { + if (TREE_CODE (expr) != COMPONENT_REF + && TREE_CODE (expr) != ARRAY_REF) + return NULL; + model_comps.safe_push (expr); + expr = TREE_OPERAND (expr, 0); + } + + tree ref = unshare_expr (base); + while (!model_comps.is_empty ()) + { + tree t = model_comps.pop (); + if (TREE_CODE (t) == COMPONENT_REF) + ref = build3_loc (loc, COMPONENT_REF, TREE_TYPE (t), ref, + TREE_OPERAND (t, 1), TREE_OPERAND (t, 2)); + else if (TREE_CODE (t) == ARRAY_REF) + ref = build4_loc (loc, ARRAY_REF, TREE_TYPE (t), ref, + TREE_OPERAND (t, 1), TREE_OPERAND (t, 2), + TREE_OPERAND (t, 3)); + else + gcc_unreachable (); + } + + return ref; +} + /* Construct a memory reference to a part of an aggregate BASE at the given OFFSET and of the same type as MODEL. In case this is a reference to a bit-field, the function will replicate the last component_ref of model's @@ -1822,9 +1863,19 @@ build_ref_for_model (location_t loc, tree base, HOST_WIDE_INT offset, NULL_TREE); } else - return - build_ref_for_offset (loc, base, offset, model->reverse, model->type, - gsi, insert_after); + { + tree res; + if (model->grp_same_access_path + && offset <= model->offset + && get_object_alignment (base) >= TYPE_ALIGN (TREE_TYPE (base)) + /* build_reconstructed_reference can still fail if we have already + massaged BASE because of another type incompatibility. */ + && (res = build_reconstructed_reference (loc, base, model))) + return res; + else + return build_ref_for_offset (loc, base, offset, model->reverse, + model->type, gsi, insert_after); + } } /* Attempt to build a memory reference that we could but into a gimple @@ -2076,6 +2127,121 @@ find_var_candidates (void) return ret; } +/* Return true if EXP is a reference chain of COMPONENT_REFs and AREAY_REFs + ending either with a DECL or a MEM_REF with zero offset. */ + +static bool +path_comparable_for_same_access (tree expr) +{ + while (handled_component_p (expr)) + { + if (TREE_CODE (expr) == ARRAY_REF) + { + /* SSA name indices can occur here too when the array is of sie one. + But we cannot just re-use array_refs with SSA names elsewhere in + the function, so disallow non-constant indices. TODO: Remove this + limitation after teaching build_reconstructed_reference to replace + the index with the index type lower bound. */ + if (TREE_CODE (TREE_OPERAND (expr, 1)) != INTEGER_CST) + return false; + } + else if (TREE_CODE (expr) != COMPONENT_REF) + return false; + + expr = TREE_OPERAND (expr, 0); + } + + if (TREE_CODE (expr) == MEM_REF) + { + if (!zerop (TREE_OPERAND (expr, 1))) + return false; + } + else + gcc_assert (DECL_P (expr)); + + return true; +} + +/* Assuming that EXP1 consists of only COMPONENT_REFs and ARRAY_REFs, return + true if the chain of these handled components are exactly the same as EXP2 + and the expression under them is the same DECL or an equivalent MEM_REF. + The reference picked by compare_access_positions must go to EXP1. */ + +static bool +same_access_path_p (tree exp1, tree exp2) +{ + while (handled_component_p (exp1)) + { + if (TREE_CODE (exp1) != TREE_CODE (exp2)) + { + /* Special case single-field structures loaded sometimes as the field + and sometimes as the structure. If the field is of a scalar type, + compare_access_positions will put it into exp1. + + TODO: The gimple register type condition can be removed if teach + compare_access_positions to put inner types first. */ + if (is_gimple_reg_type (TREE_TYPE (exp1)) + && TREE_CODE (exp1) == COMPONENT_REF + && (TYPE_MAIN_VARIANT (TREE_TYPE (TREE_OPERAND (exp1, 0))) + == TYPE_MAIN_VARIANT (TREE_TYPE (exp2)))) + { + exp1 = TREE_OPERAND (exp1, 0); + continue; + } + return false; + } + + if (TREE_CODE (exp1) == COMPONENT_REF) + { + if (TREE_OPERAND (exp1, 1) != TREE_OPERAND (exp2, 1) + || !tree_int_cst_equal (TREE_OPERAND (exp1, 2), + TREE_OPERAND (exp2, 2))) + return false; + } + else if (TREE_CODE (exp1) == ARRAY_REF) + { + if (!tree_int_cst_equal (TREE_OPERAND (exp1, 1), + TREE_OPERAND (exp2, 1)) + || !tree_int_cst_equal (array_ref_low_bound (exp1), + array_ref_low_bound (exp2)) + || !tree_int_cst_equal (array_ref_element_size (exp1), + array_ref_element_size (exp2))) + return false; + } + else + gcc_unreachable (); + + exp1 = TREE_OPERAND (exp1, 0); + exp2 = TREE_OPERAND (exp2, 0); + } + + if (TREE_CODE (exp1) != TREE_CODE (exp2)) + return false; + + if (DECL_P (exp1)) + { + gcc_assert (exp1 == exp2); + return true; + } + else if (TREE_CODE (exp1) == MEM_REF) + { + gcc_assert (TREE_CODE (TREE_OPERAND (exp1, 0)) == ADDR_EXPR + && TREE_CODE (TREE_OPERAND (exp2, 0)) == ADDR_EXPR + && DECL_P (TREE_OPERAND (TREE_OPERAND (exp1, 0), 0)) + && (TREE_OPERAND (TREE_OPERAND (exp1, 0), 0) + == TREE_OPERAND (TREE_OPERAND (exp1, 0), 0)) + && tree_int_cst_equal (TREE_OPERAND (exp1, 1), + TREE_OPERAND (exp2, 1))); + + return ((TYPE_MAIN_VARIANT (TREE_TYPE (exp1)) + == TYPE_MAIN_VARIANT (TREE_TYPE (exp2))) + && (TYPE_MAIN_VARIANT (reference_alias_ptr_type (exp1)) + == TYPE_MAIN_VARIANT (reference_alias_ptr_type (exp2)))); + } + else + return false; +} + /* Sort all accesses for the given variable, check for partial overlaps and return NULL if there are any. If there are none, pick a representative for each combination of offset and size and create a linked list out of them. @@ -2116,6 +2282,7 @@ sort_and_splice_var_accesses (tree var) bool grp_partial_lhs = access->grp_partial_lhs; bool first_scalar = is_gimple_reg_type (access->type); bool unscalarizable_region = access->grp_unscalarizable_region; + bool grp_same_access_path = true; bool bf_non_full_precision = (INTEGRAL_TYPE_P (access->type) && TYPE_PRECISION (access->type) != access->size @@ -2134,6 +2301,8 @@ sort_and_splice_var_accesses (tree var) gcc_assert (access->offset >= low && access->offset + access->size <= high); + grp_same_access_path = path_comparable_for_same_access (access->expr); + j = i + 1; while (j < access_count) { @@ -2184,6 +2353,11 @@ sort_and_splice_var_accesses (tree var) } unscalarizable_region = true; } + + if (grp_same_access_path + && !same_access_path_p (access->expr, ac2->expr)) + grp_same_access_path = false; + ac2->group_representative = access; j++; } @@ -2202,6 +2376,7 @@ sort_and_splice_var_accesses (tree var) access->grp_total_scalarization = total_scalarization; access->grp_partial_lhs = grp_partial_lhs; access->grp_unscalarizable_region = unscalarizable_region; + access->grp_same_access_path = grp_same_access_path; *prev_acc_ptr = access; prev_acc_ptr = &access->next_grp; @@ -2471,6 +2646,8 @@ analyze_access_subtree (struct access *root, struct access *parent, root->grp_assignment_write = 1; if (parent->grp_total_scalarization) root->grp_total_scalarization = 1; + if (!parent->grp_same_access_path) + root->grp_same_access_path = 0; } if (root->grp_unscalarizable_region) @@ -2721,13 +2898,17 @@ propagate_subaccesses_across_link (struct access *lacc, struct access *racc) lacc->type = racc->type; if (build_user_friendly_ref_for_offset (&t, TREE_TYPE (t), lacc->offset, racc->type)) - lacc->expr = t; + { + lacc->expr = t; + lacc->grp_same_access_path = true; + } else { lacc->expr = build_ref_for_model (EXPR_LOCATION (lacc->base), lacc->base, lacc->offset, racc, NULL, false); lacc->grp_no_warning = true; + lacc->grp_same_access_path = false; } } return ret; -- 2.21.0