From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 89833 invoked by alias); 24 May 2019 11:14:38 -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 89825 invoked by uid 89); 24 May 2019 11:14:38 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-12.3 required=5.0 tests=AWL,BAYES_00,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3 autolearn=ham version=3.3.1 spammy=TBAA, aritificially, sk:call_ma, disambiguations X-HELO: nikam.ms.mff.cuni.cz Received: from nikam.ms.mff.cuni.cz (HELO nikam.ms.mff.cuni.cz) (195.113.20.16) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 24 May 2019 11:14:36 +0000 Received: by nikam.ms.mff.cuni.cz (Postfix, from userid 16202) id B51FA2804E2; Fri, 24 May 2019 13:14:33 +0200 (CEST) Date: Fri, 24 May 2019 11:14:00 -0000 From: Jan Hubicka To: gcc-patches@gcc.gnu.org, rguenther@suse.de, d@dcepelik.cz Subject: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors Message-ID: <20190524111433.mv5z33ysiatlxmxz@kam.mff.cuni.cz> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: NeoMutt/20170113 (1.7.2) X-SW-Source: 2019-05/txt/msg01680.txt.bz2 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. 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. + + 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). + + 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; + } + /* 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; + } + 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;