From patchwork Wed May 27 05:28:50 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Hubicka X-Patchwork-Id: 476919 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 6E12E14029D for ; Wed, 27 May 2015 15:29:05 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=UOP1EIFk; dkim-atps=neutral DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; q=dns; s= default; b=wH3Hic/uTbW43SBaNQvoAujyG68w/K3Znmsp5zkyF5YLIfzTo5ecM tktHt18W4uqTurH5MxVLRJmUhw1NM+w3/sUoiNcwhmk04wZZweDiMhlohKivlSO0 RmElm2vkhQaJUQ0Epyo5AZ2dBKz1kdn3wjihq4wK4u/36x60aSm0z4= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; s= default; bh=TCkUcUQ+hs41QtAvO0pMtYl9PYc=; b=UOP1EIFkBwfP134Uq+rb cZSJSkAU4ZYB/o09kG7AA8CQW56io0VgWN7SZQ8FEa99TY/N+SQQz9lGAUIyzkMU tiaz4tjL72MtyFciYb9Fh9WKodju86XFTpbnqtxN3LAps0s+yfpv8LKiD7hPSuru 3ofxRZhT7FiB6JW8vlzMg1Y= Received: (qmail 34579 invoked by alias); 27 May 2015 05:28:58 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 34564 invoked by uid 89); 27 May 2015 05:28:56 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-0.0 required=5.0 tests=AWL, BAYES_50, KAM_LAZY_DOMAIN_SECURITY, T_RP_MATCHES_RCVD autolearn=no version=3.3.2 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 (AES256-GCM-SHA384 encrypted) ESMTPS; Wed, 27 May 2015 05:28:54 +0000 Received: by nikam.ms.mff.cuni.cz (Postfix, from userid 16202) id 0AA7B5431AC; Wed, 27 May 2015 07:28:50 +0200 (CEST) Date: Wed, 27 May 2015 07:28:50 +0200 From: Jan Hubicka To: gcc-patches@gcc.gnu.org, rguenther@suse.de Subject: Do less generous pointer globbing in alias.c Message-ID: <20150527052850.GB88897@kam.mff.cuni.cz> MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.5.21 (2010-09-15) Hi, this patch makes it possible for non-LTO alias oracle to TBAA disambiguate pointer types. It makes void * conflicting with all of them and does not put it to alias set 0. It also preserves the property that qualifiers of pointer-to type should not matter to determine the alias set and that pointer to array is same as pointer to array element. Finally it makes pointer void * to be equivalent to void ** (and more *) and to types with structural equality only. I think those are all globbing rules we discussed for the non-LTO patch. It does two things. First is kind of "canonicalization" where for a given pointer it looks for non-pointer pointed-to type and then rebuilds is without qualifiers. This is fast, because build_pointer_type will reuse existing types. It makes void * to conflict with everyting by making its alias set to be subset of alias set of any other pointer. This means that writes to void * conflict with writes to any other pointer without really need to glob all the pointers to one equivalence class. This patch makes quite some difference on C++. For example on deal II the TBAA stats reports 4344358 disambiguations and 7008576 queries, while with the patch we get 5368737 and 5687399 queries (I did not chose deal II for reason, it is just random C++ file) The patch bootstrap and regtests ppc64le-linux with the following testsuite differences: @@ -30,7 +30,9 @@ FAIL: c-c++-common/asan/null-deref-1.c -O3 -g output pattern test, is ASAN:SIGSEGV FAIL: c-c++-common/asan/null-deref-1.c -Os output pattern test, is ASAN:SIGSEGV FAIL: gcc.dg/cpp/_Pragma3.c (test for excess errors) +XPASS: gcc.dg/alias-8.c (test for warnings, line 11) FAIL: gcc.dg/loop-8.c scan-rtl-dump-times loop2_invariant "Decided" 1 +FAIL: gcc.dg/pr62167.c scan-tree-dump-not pre "Removing basic block" FAIL: gcc.dg/sms-4.c scan-rtl-dump-times sms "SMS succeeded" 1 XPASS: gcc.dg/guality/example.c -O0 execution test XPASS: gcc.dg/guality/example.c -O1 execution test @@ -304,6 +306,9 @@ FAIL: c-c++-common/asan/null-deref-1.c -O3 -g output pattern test, is ASAN:SIGSEGV FAIL: g++.dg/cpp1y/vla-initlist1.C -std=gnu++11 execution test FAIL: g++.dg/cpp1y/vla-initlist1.C -std=gnu++14 execution test +FAIL: g++.dg/ipa/ipa-icf-4.C -std=gnu++11 scan-ipa-dump icf "Equal symbols: [67]" +FAIL: g++.dg/ipa/ipa-icf-4.C -std=gnu++14 scan-ipa-dump icf "Equal symbols: [67]" +FAIL: g++.dg/ipa/ipa-icf-4.C -std=gnu++98 scan-ipa-dump icf "Equal symbols: [67]" ipa-icf-4 is about alias info now being more perceptive to block the merging. pr62167 seems just confused. The template checks that memory stores are not unified. It looks for BB removal message, but with the patch we get: : node.next = 0B; head.0_4 = head; node.prev = head.0_4; head.0_4->first = &node; k.1_7 = k; h_8 = &heads[k.1_7]; heads[2].first = 0B; if (head.0_4 == h_8) goto ; else goto ; : goto ; : p_10 = MEM[(struct head *)&heads][k.1_7].first; : # p_1 = PHI _11 = p_1 != 0B; _12 = (int) _11; return _12; before PR, the message is about the bb 5 sitting at critical edge removed. The TBAA incompatible load it looks for is optimized away by FRE: head->first = &node; struct node *n = head->first; struct head *h = &heads[k]; heads[2].first = n->next; if ((void*)n->prev == (void *)h) p = h->first; else /* Dead tbaa-unsafe load from ((struct node *)&heads[2])->next. */ p = n->prev->next; here n is known to be head->first that is known to be &node. The testcase runtime checks that result is Ok and passes. Bootstrapped/regtested ppc64le-linux. * alias.c (get_alias_set): Do not glob all pointer types into one; just produce euqivalence classes based on canonical type of pointed type type; make void * equivalent to void **. (record_component_aliases): Make void * to conflict with all other pointer types. Index: alias.c =================================================================== --- alias.c (revision 223633) +++ alias.c (working copy) @@ -903,35 +906,79 @@ get_alias_set (tree t) the pointed-to types. This issue has been reported to the C++ committee. - In addition to the above canonicalization issue, with LTO - we should also canonicalize `T (*)[]' to `T *' avoiding - alias issues with pointer-to element types and pointer-to - array types. - - Likewise we need to deal with the situation of incomplete - pointed-to types and make `*(struct X **)&a' and - `*(struct X {} **)&a' alias. Otherwise we will have to - guarantee that all pointer-to incomplete type variants - will be replaced by pointer-to complete type variants if - they are available. - - With LTO the convenient situation of using `void *' to - access and store any pointer type will also become - more apparent (and `void *' is just another pointer-to - incomplete type). Assigning alias-set zero to `void *' - and all pointer-to incomplete types is a not appealing - solution. Assigning an effective alias-set zero only - affecting pointers might be - by recording proper subset - relationships of all pointer alias-sets. - - Pointer-to function types are another grey area which - needs caution. Globbing them all into one alias-set - or the above effective zero set would work. - - For now just assign the same alias-set to all pointers. - That's simple and avoids all the above problems. */ - else if (POINTER_TYPE_P (t) - && t != ptr_type_node) + For this reason go to canonical type of the unqalified pointer type. + Until GCC 6 this code set all pointers sets to have alias set of + ptr_type_node but that is a bad idea, because it prevents disabiguations + in between pointers. For Firefox this accounts about 20% of all + disambiguations in the program. */ + else if (POINTER_TYPE_P (t) && t != ptr_type_node && !in_lto_p) + { + tree p; + auto_vec reference; + + /* Unnest all pointers and references. + We also want to make pointer to array equivalent to pointer to its + element. So skip all array types, too. */ + for (p = t; POINTER_TYPE_P (p) + || (TREE_CODE (p) == ARRAY_TYPE && !TYPE_NONALIASED_COMPONENT (p)); + p = TREE_TYPE (p)) + { + if (TREE_CODE (p) == REFERENCE_TYPE) + reference.safe_push (true); + if (TREE_CODE (p) == POINTER_TYPE) + reference.safe_push (false); + } + p = TYPE_MAIN_VARIANT (p); + + /* Make void * compatible with char * and also void **. + Programs are commonly violating TBAA by this. + + We also make void * to conflict with every pointer + (see record_component_aliases) and thus it is safe it to use it for + pointers to types with TYPE_STRUCTURAL_EQUALITY_P. */ + if (TREE_CODE (p) == VOID_TYPE || TYPE_STRUCTURAL_EQUALITY_P (p)) + set = get_alias_set (ptr_type_node); + else + { + /* Rebuild pointer type from starting from canonical types using + unqualified pointers and references only. This way all such + pointers will have the same alias set and will conflict with + each other. + + Most of time we already have pointers or references of a given type. + If not build new one just to be sure that if someone later (probably + only middle-end can, as we should assign all alias classes only after + finishing translation unit) builds the pointer type, the canonical type + will match. */ + p = TYPE_CANONICAL (p); + while (!reference.is_empty ()) + { + if (reference.pop ()) + p = build_reference_type (p); + else + p = build_pointer_type (p); + p = TYPE_CANONICAL (TYPE_MAIN_VARIANT (p)); + } + gcc_checking_assert (TYPE_CANONICAL (p) == p); + + /* Assign the alias set to both p and t. + We can not call get_alias_set (p) here as that would triger + infinite recursion when p == t. + In other cases it would just trigger unnecesary legwork of + rebuilding the pointer again. */ + if (TYPE_ALIAS_SET_KNOWN_P (p)) + /* Return early; we do not need to record component aliases. */ + return TYPE_ALIAS_SET (t) = TYPE_ALIAS_SET (p); + else + { + set = new_alias_set (); + TYPE_ALIAS_SET (p) = set; + } + } + } + /* In LTO the rules above needs to be part of canonical type machinery. + For now just punt. */ + else if (POINTER_TYPE_P (t) && t != ptr_type_node && in_lto_p) set = get_alias_set (ptr_type_node); /* Otherwise make a new alias set for this type. */ @@ -950,7 +997,8 @@ get_alias_set (tree t) /* If this is an aggregate type or a complex type, we must record any component aliasing information. */ - if (AGGREGATE_TYPE_P (t) || TREE_CODE (t) == COMPLEX_TYPE) + if (AGGREGATE_TYPE_P (t) || TREE_CODE (t) == COMPLEX_TYPE + || TREE_CODE (t) == POINTER_TYPE) record_component_aliases (t); return set; @@ -1050,6 +1098,26 @@ record_component_aliases (tree type) switch (TREE_CODE (type)) { + /* We want void * to be compatible with any other pointer without really + dropping it to alias set 0. Doing so would make it compatible with + all non-pointer types too. + + Make thus ptr_type_node to be a component of every pointer type. + Tus memory operations of type "void *" conflict with operations of type + "T *" without impossing a conflict with memory operations of type "Q *" + in case T and Q do not conflict. + + This is not strictly necessary by the language standards, but avoids + common type punning mistakes. In addition to that, we need the existence + of such universal pointer to implement Fortran's C_PTR type (which is + defined as type compatible with all C pointers) and we use it in + get_alias_set to give alias set to pointers to types without + canonical types (those are typically nameless incomplete types) + that needs to be also compatible with each other and with pointers to + complete types. */ + case POINTER_TYPE: + record_alias_subset (superset, get_alias_set (ptr_type_node)); + break; case RECORD_TYPE: case UNION_TYPE: case QUAL_UNION_TYPE: