From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 34275 invoked by alias); 24 May 2019 12:57:20 -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 34266 invoked by uid 89); 24 May 2019 12:57:20 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-13.5 required=5.0 tests=AWL,BAYES_00,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,SPF_PASS autolearn=ham version=3.3.1 spammy=apples, Honza 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; Fri, 24 May 2019 12:57:18 +0000 Received: from relay2.suse.de (unknown [195.135.220.254]) by mx1.suse.de (Postfix) with ESMTP id E64D5AD4C; Fri, 24 May 2019 12:57:15 +0000 (UTC) Date: Fri, 24 May 2019 12:57:00 -0000 From: Richard Biener To: Jan Hubicka cc: gcc-patches@gcc.gnu.org, d@dcepelik.cz Subject: Re: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors In-Reply-To: <20190524111433.mv5z33ysiatlxmxz@kam.mff.cuni.cz> Message-ID: References: <20190524111433.mv5z33ysiatlxmxz@kam.mff.cuni.cz> User-Agent: Alpine 2.20 (LSU 67 2015-01-07) MIME-Version: 1.0 Content-Type: multipart/mixed; BOUNDARY="-1609908220-1633990198-1558702635=:10704" X-SW-Source: 2019-05/txt/msg01687.txt.bz2 This message is in MIME format. The first part should be readable text, while the remaining parts are likely unreadable without MIME-aware tools. ---1609908220-1633990198-1558702635=:10704 Content-Type: text/plain; charset=ISO-8859-15 Content-Transfer-Encoding: 8BIT Content-length: 7973 On Fri, 24 May 2019, Jan Hubicka wrote: > Hi, > this patch implements basic structura compare so same_type_for_tbaa does > not return -1 for all arrays, vectors and pointers with LTO. > The current TBAA stats for tramp3d are: > > Alias oracle query stats: > refs_may_alias_p: 3016393 disambiguations, 3316783 queries > ref_maybe_used_by_call_p: 7112 disambiguations, 3041993 queries > call_may_clobber_ref_p: 817 disambiguations, 817 queries > aliasing_component_ref_p: 652 disambiguations, 19720 queries > TBAA oracle: 1420658 disambiguations 2918622 queries > 552186 are in alias set 0 > 569271 queries asked about the same object > 0 queries asked about the same alias set > 0 access volatile > 260166 are dependent in the DAG > 116341 are aritificially in conflict with void * > > compared to: > Alias oracle query stats: > refs_may_alias_p: 3013166 disambiguations, 3313523 queries > ref_maybe_used_by_call_p: 7112 disambiguations, 3038766 queries > call_may_clobber_ref_p: 817 disambiguations, 817 queries > aliasing_component_ref_p: 124 disambiguations, 12414 queries > TBAA oracle: 1417999 disambiguations 2914624 queries > 552182 are in alias set 0 > 569275 queries asked about the same object > 0 queries asked about the same alias set > 0 access volatile > 258909 are dependent in the DAG > 116259 are aritificially in conflict with void * > > so about 5 times increase of alias_components_refs_p disambiguations. Note the number of queries also changes so it's "somewhat" comparing apples and oranges (possibly the alias walk doesn't have to give up and thus we walk more and do more queries). > > The basic idea is simple - pointers are same if points-to types are same > and similarly for arrays/vector. > > I have noticed that a lot of -1s come from comparing void pointers to non-void > because void is structural type we consider incomparable with everyting. > I think for pointers it is OK to return either 0 or 1 and never care about > undecided cases that matters only in the middle of paths. > For this I track if we compare pointers and return this. > > For arrays situation is slightly different - we can only disprove array > equivalence but we do not want to return 1 because we support partial overlaps > on them. The logic about arrays is bit sloppy: some users of > types_same_for_tbaa_p explicitly disallow them while others doesn't and there > are cases where the function returns 1 w/o LTO. We can also handle matches when > array is not the outer type of whole reference which is a common case. > I plan to clean it up incrementally. > > lto-bootstrapped/regtested x86_64-linux, OK? > > Honza > > * tree-ssa-alias.c (same_type_for_tbaa): Handle structural comparison > of pointers, arrays and vectors. > Index: tree-ssa-alias.c > =================================================================== > --- tree-ssa-alias.c (revision 271292) > +++ tree-ssa-alias.c (working copy) > @@ -745,21 +767,87 @@ same_type_for_tbaa (tree type1, tree typ > type1 = TYPE_MAIN_VARIANT (type1); > type2 = TYPE_MAIN_VARIANT (type2); > > - /* If we would have to do structural comparison bail out. */ > - if (TYPE_STRUCTURAL_EQUALITY_P (type1) > - || TYPE_STRUCTURAL_EQUALITY_P (type2)) > - return -1; > + /* If same_type_for_tbaa returns true we make an assumption that pointers to > + TYPE1 and TYPE2 can either point to same copy of the type or completely > + different. > + > + This is not necessarily true for arrays where overlap can be partial > + as in gcc.dg/torture/alias-2.c. So we can only prove that arrays are > + disjoint becuase they are derived from different types but we can not > + prove they are same. > + > + On the other hand for pointers we can always consider them to be same > + unless we can prove that pointed-to types are different. What about different address-spaces and/or pointer sizes? > + So normally return values are > + 0 if types are known to be different > + 1 if types are same and there is no partial overlap > + -1 otherwise. > + > + However if comparing two pointers return values are > + 0 if pointed to types are known to be different > + 1 otherwise (because partial overlaps do not happen). Doesn't this apply to all non-composite types? (the "partial overlaps do not happen"?) > + If comparing array or vector to other type return values are > + 0 if types array/vector are derived from are known to be different > + -1 otherwise (to watch for partial overlaps). */ > + > + bool in_ptr = false; > + bool in_array = false; > + > + if (type1 == type2) > + return 1; > + > + /* Do structural comparsion for types that have no canonical types in LTO. */ > + while (TYPE_STRUCTURAL_EQUALITY_P (type1) > + || TYPE_STRUCTURAL_EQUALITY_P (type2)) > + { > + /* Pointer types are same if they point to same types. */ > + if (POINTER_TYPE_P (type1) && POINTER_TYPE_P (type2)) > + { > + type1 = TYPE_MAIN_VARIANT (TREE_TYPE (type1)); > + type2 = TYPE_MAIN_VARIANT (TREE_TYPE (type2)); > + if (!in_array) > + in_ptr = true; Don't you run into unrelated types when visiting pointed-to types here? Why would we care for the pointed-to type anwyways? That is, the loop should just handle composite types and after it compare non-composite types with types_compatible_p for example? Maybe even do that change independently. > + } > + /* Peel out arrays and vector to compare inner types. */ > + else if ((TREE_CODE (type1) == ARRAY_TYPE > + || TREE_CODE (type1) == VECTOR_TYPE) > + && TYPE_STRUCTURAL_EQUALITY_P (type1)) > + { > + type1 = TYPE_MAIN_VARIANT (TREE_TYPE (type1)); > + if (!in_ptr) > + in_array = true; > + } > + else if ((TREE_CODE (type2) == ARRAY_TYPE > + || TREE_CODE (type2) == VECTOR_TYPE) > + && TYPE_STRUCTURAL_EQUALITY_P (type2)) > + { > + type2 = TYPE_MAIN_VARIANT (TREE_TYPE (type2)); > + if (!in_ptr) > + in_array = true; > + } I don't think it works like this, peeling arrays/vectors from types individually instead of in lock-step? I think for better testing coverage you want to force TYPE_STRUCTURAL_EQUALITY on all types here - this shouldn't make things invalid but otherwise these code-paths are not tested very well. > + else > + { > + if (POINTER_TYPE_P (type1) != POINTER_TYPE_P (type2)) > + return 0; > + return in_ptr ? 1 : -1; > + } > + > + if (type1 == type2) > + return in_array ? -1 : 1; > + } > > /* Compare the canonical types. */ > if (TYPE_CANONICAL (type1) == TYPE_CANONICAL (type2)) > - return 1; > + return in_array ? -1 : 1; > > /* ??? Array types are not properly unified in all cases as we have > spurious changes in the index types for example. Removing this > causes all sorts of problems with the Fortran frontend. */ > if (TREE_CODE (type1) == ARRAY_TYPE > && TREE_CODE (type2) == ARRAY_TYPE) > - return -1; > + return in_ptr ? 1 : -1; > > /* ??? In Ada, an lvalue of an unconstrained type can be used to access an > object of one of its constrained subtypes, e.g. when a function with an > @@ -770,7 +858,7 @@ same_type_for_tbaa (tree type1, tree typ > not (e.g. type and subtypes can have different modes). So, in the end, > they are only guaranteed to have the same alias set. */ > if (get_alias_set (type1) == get_alias_set (type2)) > - return -1; > + return in_ptr ? 1 : -1; > > /* The types are known to be not equal. */ > return 0; > -- Richard Biener SUSE Linux GmbH, Maxfeldstrasse 5, 90409 Nuernberg, Germany; GF: Felix Imendörffer, Mary Higgins, Sri Rasiah; HRB 21284 (AG Nürnberg) ---1609908220-1633990198-1558702635=:10704--