From patchwork Thu Oct 28 10:39:49 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Jelinek X-Patchwork-Id: 46734 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 7BCA53858410 for ; Thu, 28 Oct 2021 10:40:27 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 7BCA53858410 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1635417627; bh=Fko2HZ079Wej0978T+3MYCQzMWXjCHtykxSs0leJONs=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:Cc:From; b=b3Zt/W71VuYBIsbvKe4I2uuv7VOkVJsDtvKDtBEgvD99jOl4soOdl7XnSeVJfb4O6 0LitP4E6mflR4gbP4tpxo6+6rNAQRiD3lU8shTdeCMhHc6IGQWu4bPJkeRBnuPY2VK z9kOCbGDU44EflFYj+qvsKVHn58HiWP593fF3Fc8= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id 39F0A3858D35 for ; Thu, 28 Oct 2021 10:39:56 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 39F0A3858D35 Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-148-EPxhQJ4SMCaRiFVzUpyczw-1; Thu, 28 Oct 2021 06:39:54 -0400 X-MC-Unique: EPxhQJ4SMCaRiFVzUpyczw-1 Received: from smtp.corp.redhat.com (int-mx06.intmail.prod.int.phx2.redhat.com [10.5.11.16]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 9825318125C0; Thu, 28 Oct 2021 10:39:53 +0000 (UTC) Received: from tucnak.zalov.cz (unknown [10.39.193.172]) by smtp.corp.redhat.com (Postfix) with ESMTPS id ECD025FC23; Thu, 28 Oct 2021 10:39:52 +0000 (UTC) Received: from tucnak.zalov.cz (localhost [127.0.0.1]) by tucnak.zalov.cz (8.16.1/8.16.1) with ESMTPS id 19SAdo8Y2069105 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Thu, 28 Oct 2021 12:39:50 +0200 Received: (from jakub@localhost) by tucnak.zalov.cz (8.16.1/8.16.1/Submit) id 19SAdn7v2069104; Thu, 28 Oct 2021 12:39:49 +0200 Date: Thu, 28 Oct 2021 12:39:49 +0200 To: Richard Biener Subject: [PATCH] match.pd: Optimize MIN_EXPR etc. addr1 < addr2 would be simplified [PR102951] Message-ID: <20211028103949.GN304296@tucnak> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.79 on 10.5.11.16 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Disposition: inline X-Spam-Status: No, score=-5.4 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Jakub Jelinek via Gcc-patches From: Jakub Jelinek Reply-To: Jakub Jelinek Cc: gcc-patches@gcc.gnu.org Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" Hi! This patch outlines the decision whether address comparison can be folded or not from the match.pd simple comparison simplification and uses it both there and in a new minmax simplification, such that we fold e.g. MAX (&a[2], &a[1]) etc. Some of the Wstringop-overflow-62.c changes might look weird, but that seems to be mainly due to gimple_fold_builtin_memset not bothering to copy over location, will fix that incrementally. Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk? 2021-10-28 Jakub Jelinek PR tree-optimization/102951 * fold-const.h (address_compare): Declare. * fold-const.c (address_compare): New function. * match.pd (cmp (convert1?@2 addr@0) (convert2? addr@1)): Use address_compare helper. (minmax cmp (convert1?@2 addr@0) (convert2?@3 addr@1)): New simplification. * gcc.dg/tree-ssa/pr102951.c: New test. * gcc.dg/Wstringop-overflow-62.c: Adjust expected diagnostics. Jakub --- gcc/fold-const.h.jj 2021-06-14 12:27:18.572411152 +0200 +++ gcc/fold-const.h 2021-10-27 11:54:50.781412075 +0200 @@ -213,6 +213,8 @@ extern bool negate_mathfn_p (combined_fn extern const char *getbyterep (tree, unsigned HOST_WIDE_INT *); extern const char *c_getstr (tree); extern wide_int tree_nonzero_bits (const_tree); +extern int address_compare (tree_code, tree, tree, tree, tree &, tree &, + poly_int64 &, poly_int64 &, bool); /* Return OFF converted to a pointer offset type suitable as offset for POINTER_PLUS_EXPR. Use location LOC for this conversion. */ --- gcc/fold-const.c.jj 2021-08-11 23:43:59.195893727 +0200 +++ gcc/fold-const.c 2021-10-27 12:16:26.504267476 +0200 @@ -16473,6 +16473,132 @@ tree_nonzero_bits (const_tree t) return wi::shwi (-1, TYPE_PRECISION (TREE_TYPE (t))); } +/* Helper function for address compare simplifications in match.pd. + OP0 and OP1 are ADDR_EXPR operands being compared by CODE. + BASE0, BASE1, OFF0 and OFF1 are set by the function. + GENERIC is true if GENERIC folding and false for GIMPLE folding. + Returns 0 if OP0 is known to be unequal to OP1 regardless of OFF{0,1}, + 1 if bases are known to be equal and OP0 cmp OP1 depends on OFF0 cmp OFF1, + and 2 if unknown. */ + +int +address_compare (tree_code code, tree type, tree op0, tree op1, + tree &base0, tree &base1, poly_int64 &off0, poly_int64 &off1, + bool generic) +{ + gcc_checking_assert (TREE_CODE (op0) == ADDR_EXPR); + gcc_checking_assert (TREE_CODE (op1) == ADDR_EXPR); + base0 = get_addr_base_and_unit_offset (TREE_OPERAND (op0, 0), &off0); + base1 = get_addr_base_and_unit_offset (TREE_OPERAND (op1, 0), &off1); + if (base0 && TREE_CODE (base0) == MEM_REF) + { + off0 += mem_ref_offset (base0).force_shwi (); + base0 = TREE_OPERAND (base0, 0); + } + if (base1 && TREE_CODE (base1) == MEM_REF) + { + off1 += mem_ref_offset (base1).force_shwi (); + base1 = TREE_OPERAND (base1, 0); + } + if (base0 == NULL_TREE || base1 == NULL_TREE) + return 2; + + int equal = 2; + /* Punt in GENERIC on variables with value expressions; + the value expressions might point to fields/elements + of other vars etc. */ + if (generic + && ((VAR_P (base0) && DECL_HAS_VALUE_EXPR_P (base0)) + || (VAR_P (base1) && DECL_HAS_VALUE_EXPR_P (base1)))) + return 2; + else if (decl_in_symtab_p (base0) && decl_in_symtab_p (base1)) + { + symtab_node *node0 = symtab_node::get_create (base0); + symtab_node *node1 = symtab_node::get_create (base1); + equal = node0->equal_address_to (node1); + } + else if ((DECL_P (base0) + || TREE_CODE (base0) == SSA_NAME + || TREE_CODE (base0) == STRING_CST) + && (DECL_P (base1) + || TREE_CODE (base1) == SSA_NAME + || TREE_CODE (base1) == STRING_CST)) + equal = (base0 == base1); + if (equal == 1) + { + if (code == EQ_EXPR + || code == NE_EXPR + /* If the offsets are equal we can ignore overflow. */ + || known_eq (off0, off1) + || TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (op0)) + /* Or if we compare using pointers to decls or strings. */ + || (POINTER_TYPE_P (type) + && (DECL_P (base0) || TREE_CODE (base0) == STRING_CST))) + return 1; + return 2; + } + if (equal != 0) + return equal; + if (code != EQ_EXPR && code != NE_EXPR) + return 2; + + HOST_WIDE_INT ioff0 = -1, ioff1 = -1; + off0.is_constant (&ioff0); + off1.is_constant (&ioff1); + if ((DECL_P (base0) && TREE_CODE (base1) == STRING_CST) + || (TREE_CODE (base0) == STRING_CST && DECL_P (base1)) + || (TREE_CODE (base0) == STRING_CST + && TREE_CODE (base1) == STRING_CST + && ioff0 >= 0 && ioff1 >= 0 + && ioff0 < TREE_STRING_LENGTH (base0) + && ioff1 < TREE_STRING_LENGTH (base1) + /* This is a too conservative test that the STRING_CSTs + will not end up being string-merged. */ + && strncmp (TREE_STRING_POINTER (base0) + ioff0, + TREE_STRING_POINTER (base1) + ioff1, + MIN (TREE_STRING_LENGTH (base0) - ioff0, + TREE_STRING_LENGTH (base1) - ioff1)) != 0)) + ; + else if (!DECL_P (base0) || !DECL_P (base1)) + return 2; + /* If this is a pointer comparison, ignore for now even + valid equalities where one pointer is the offset zero + of one object and the other to one past end of another one. */ + else if (!INTEGRAL_TYPE_P (type)) + ; + /* Assume that automatic variables can't be adjacent to global + variables. */ + else if (is_global_var (base0) != is_global_var (base1)) + ; + else + { + tree sz0 = DECL_SIZE_UNIT (base0); + tree sz1 = DECL_SIZE_UNIT (base1); + /* If sizes are unknown, e.g. VLA or not representable, punt. */ + if (!tree_fits_poly_int64_p (sz0) || !tree_fits_poly_int64_p (sz1)) + return 2; + + poly_int64 size0 = tree_to_poly_int64 (sz0); + poly_int64 size1 = tree_to_poly_int64 (sz1); + /* If one offset is pointing (or could be) to the beginning of one + object and the other is pointing to one past the last byte of the + other object, punt. */ + if (maybe_eq (off0, 0) && maybe_eq (off1, size1)) + equal = 2; + else if (maybe_eq (off1, 0) && maybe_eq (off0, size0)) + equal = 2; + /* If both offsets are the same, there are some cases we know that are + ok. Either if we know they aren't zero, or if we know both sizes + are no zero. */ + if (equal == 2 + && known_eq (off0, off1) + && (known_ne (off0, 0) + || (known_ne (size0, 0) && known_ne (size1, 0)))) + equal = 0; + } + return equal; +} + #if CHECKING_P namespace selftest { --- gcc/match.pd.jj 2021-10-27 09:00:28.000000000 +0200 +++ gcc/match.pd 2021-10-27 12:10:15.713455445 +0200 @@ -3009,6 +3009,30 @@ (define_operator_list COND_TERNARY @0 @2))) +/* Simplify min (&var[off0], &var[off1]) etc. depending on whether + the addresses are known to be less, equal or greater. */ +(for minmax (min max) + cmp (lt gt) + (simplify + (minmax (convert1?@2 addr@0) (convert2?@3 addr@1)) + (with + { + poly_int64 off0, off1; + tree base0, base1; + int equal = address_compare (cmp, TREE_TYPE (@2), @0, @1, base0, base1, + off0, off1, GENERIC); + } + (if (equal == 1) + (if (minmax == MIN_EXPR) + (if (known_le (off0, off1)) + @2 + (if (known_gt (off0, off1)) + @3)) + (if (known_ge (off0, off1)) + @2 + (if (known_lt (off0, off1)) + @3))))))) + /* (convert (minmax ((convert (x) c)))) -> minmax (x c) if x is promoted and the outer convert demotes the expression back to x's type. */ (for minmax (min max) @@ -5291,132 +5315,30 @@ (define_operator_list COND_TERNARY (with { poly_int64 off0, off1; - tree base0 = get_addr_base_and_unit_offset (TREE_OPERAND (@0, 0), &off0); - tree base1 = get_addr_base_and_unit_offset (TREE_OPERAND (@1, 0), &off1); - if (base0 && TREE_CODE (base0) == MEM_REF) - { - off0 += mem_ref_offset (base0).force_shwi (); - base0 = TREE_OPERAND (base0, 0); - } - if (base1 && TREE_CODE (base1) == MEM_REF) - { - off1 += mem_ref_offset (base1).force_shwi (); - base1 = TREE_OPERAND (base1, 0); - } + tree base0, base1; + int equal = address_compare (cmp, TREE_TYPE (@2), @0, @1, base0, base1, + off0, off1, GENERIC); } - (if (base0 && base1) - (with - { - int equal = 2; - /* Punt in GENERIC on variables with value expressions; - the value expressions might point to fields/elements - of other vars etc. */ - if (GENERIC - && ((VAR_P (base0) && DECL_HAS_VALUE_EXPR_P (base0)) - || (VAR_P (base1) && DECL_HAS_VALUE_EXPR_P (base1)))) - ; - else if (decl_in_symtab_p (base0) - && decl_in_symtab_p (base1)) - equal = symtab_node::get_create (base0) - ->equal_address_to (symtab_node::get_create (base1)); - else if ((DECL_P (base0) - || TREE_CODE (base0) == SSA_NAME - || TREE_CODE (base0) == STRING_CST) - && (DECL_P (base1) - || TREE_CODE (base1) == SSA_NAME - || TREE_CODE (base1) == STRING_CST)) - equal = (base0 == base1); - if (equal == 0) - { - HOST_WIDE_INT ioff0 = -1, ioff1 = -1; - off0.is_constant (&ioff0); - off1.is_constant (&ioff1); - if ((DECL_P (base0) && TREE_CODE (base1) == STRING_CST) - || (TREE_CODE (base0) == STRING_CST && DECL_P (base1)) - || (TREE_CODE (base0) == STRING_CST - && TREE_CODE (base1) == STRING_CST - && ioff0 >= 0 && ioff1 >= 0 - && ioff0 < TREE_STRING_LENGTH (base0) - && ioff1 < TREE_STRING_LENGTH (base1) - /* This is a too conservative test that the STRING_CSTs - will not end up being string-merged. */ - && strncmp (TREE_STRING_POINTER (base0) + ioff0, - TREE_STRING_POINTER (base1) + ioff1, - MIN (TREE_STRING_LENGTH (base0) - ioff0, - TREE_STRING_LENGTH (base1) - ioff1)) != 0)) - ; - else if (!DECL_P (base0) || !DECL_P (base1)) - equal = 2; - else if (cmp != EQ_EXPR && cmp != NE_EXPR) - equal = 2; - /* If this is a pointer comparison, ignore for now even - valid equalities where one pointer is the offset zero - of one object and the other to one past end of another one. */ - else if (!INTEGRAL_TYPE_P (TREE_TYPE (@2))) - ; - /* Assume that automatic variables can't be adjacent to global - variables. */ - else if (is_global_var (base0) != is_global_var (base1)) - ; - else - { - tree sz0 = DECL_SIZE_UNIT (base0); - tree sz1 = DECL_SIZE_UNIT (base1); - /* If sizes are unknown, e.g. VLA or not representable, - punt. */ - if (!tree_fits_poly_int64_p (sz0) - || !tree_fits_poly_int64_p (sz1)) - equal = 2; - else - { - poly_int64 size0 = tree_to_poly_int64 (sz0); - poly_int64 size1 = tree_to_poly_int64 (sz1); - /* If one offset is pointing (or could be) to the beginning - of one object and the other is pointing to one past the - last byte of the other object, punt. */ - if (maybe_eq (off0, 0) && maybe_eq (off1, size1)) - equal = 2; - else if (maybe_eq (off1, 0) && maybe_eq (off0, size0)) - equal = 2; - /* If both offsets are the same, there are some cases - we know that are ok. Either if we know they aren't - zero, or if we know both sizes are no zero. */ - if (equal == 2 - && known_eq (off0, off1) - && (known_ne (off0, 0) - || (known_ne (size0, 0) && known_ne (size1, 0)))) - equal = 0; - } - } - } - } - (if (equal == 1 - && (cmp == EQ_EXPR || cmp == NE_EXPR - /* If the offsets are equal we can ignore overflow. */ - || known_eq (off0, off1) - || TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (@0)) - /* Or if we compare using pointers to decls or strings. */ - || (POINTER_TYPE_P (TREE_TYPE (@2)) - && (DECL_P (base0) || TREE_CODE (base0) == STRING_CST)))) - (switch - (if (cmp == EQ_EXPR && (known_eq (off0, off1) || known_ne (off0, off1))) - { constant_boolean_node (known_eq (off0, off1), type); }) - (if (cmp == NE_EXPR && (known_eq (off0, off1) || known_ne (off0, off1))) - { constant_boolean_node (known_ne (off0, off1), type); }) - (if (cmp == LT_EXPR && (known_lt (off0, off1) || known_ge (off0, off1))) - { constant_boolean_node (known_lt (off0, off1), type); }) - (if (cmp == LE_EXPR && (known_le (off0, off1) || known_gt (off0, off1))) - { constant_boolean_node (known_le (off0, off1), type); }) - (if (cmp == GE_EXPR && (known_ge (off0, off1) || known_lt (off0, off1))) - { constant_boolean_node (known_ge (off0, off1), type); }) - (if (cmp == GT_EXPR && (known_gt (off0, off1) || known_le (off0, off1))) - { constant_boolean_node (known_gt (off0, off1), type); })) - (if (equal == 0) - (switch - (if (cmp == EQ_EXPR) - { constant_boolean_node (false, type); }) - (if (cmp == NE_EXPR) - { constant_boolean_node (true, type); }))))))))) + (if (equal == 1) + (switch + (if (cmp == EQ_EXPR && (known_eq (off0, off1) || known_ne (off0, off1))) + { constant_boolean_node (known_eq (off0, off1), type); }) + (if (cmp == NE_EXPR && (known_eq (off0, off1) || known_ne (off0, off1))) + { constant_boolean_node (known_ne (off0, off1), type); }) + (if (cmp == LT_EXPR && (known_lt (off0, off1) || known_ge (off0, off1))) + { constant_boolean_node (known_lt (off0, off1), type); }) + (if (cmp == LE_EXPR && (known_le (off0, off1) || known_gt (off0, off1))) + { constant_boolean_node (known_le (off0, off1), type); }) + (if (cmp == GE_EXPR && (known_ge (off0, off1) || known_lt (off0, off1))) + { constant_boolean_node (known_ge (off0, off1), type); }) + (if (cmp == GT_EXPR && (known_gt (off0, off1) || known_le (off0, off1))) + { constant_boolean_node (known_gt (off0, off1), type); })) + (if (equal == 0) + (switch + (if (cmp == EQ_EXPR) + { constant_boolean_node (false, type); }) + (if (cmp == NE_EXPR) + { constant_boolean_node (true, type); }))))))) /* Simplify pointer equality compares using PTA. */ (for neeq (ne eq) --- gcc/testsuite/gcc.dg/tree-ssa/pr102951.c.jj 2021-10-27 12:33:16.586143898 +0200 +++ gcc/testsuite/gcc.dg/tree-ssa/pr102951.c 2021-10-27 12:33:00.880363448 +0200 @@ -0,0 +1,41 @@ +/* PR tree-optimization/102951 */ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-ccp1" } */ +/* { dg-final { scan-tree-dump-times "return \&a\\\[1\\\];" 2 "ccp1" } } */ +/* { dg-final { scan-tree-dump-times "return \&a\\\[4\\\];" 2 "ccp1" } } */ +/* { dg-final { scan-tree-dump-not "MIN_EXPR" "ccp1" } } */ +/* { dg-final { scan-tree-dump-not "MAX_EXPR" "ccp1" } } */ + +extern int a[5]; + +int * +foo (void) +{ + int *p1 = &a[1]; + int *p2 = &a[2]; + return p1 < p2 ? p1 : p2; +} + +int * +bar (void) +{ + int *p1 = &a[1]; + int *p2 = &a[2]; + return p1 <= p2 ? p1 : p2; +} + +int * +baz (void) +{ + int *p1 = &a[3]; + int *p2 = &a[4]; + return p1 > p2 ? p1 : p2; +} + +int * +qux (void) +{ + int *p1 = &a[3]; + int *p2 = &a[4]; + return p1 >= p2 ? p1 : p2; +} --- gcc/testsuite/gcc.dg/Wstringop-overflow-62.c.jj 2021-09-18 09:44:31.000000000 +0200 +++ gcc/testsuite/gcc.dg/Wstringop-overflow-62.c 2021-10-28 12:24:21.909780099 +0200 @@ -217,14 +217,14 @@ void test_max (void) { /* Exercise both pointers pointing to the same object plus constant offset. */ - char a2[2]; // { dg-message "at offset 1 into destination object 'a2' of size 2" "note" } + char a2[2]; char *pi = a2 + 1; char *pj = a2 + 2; char *q = MAX (pi, pj); - memset (q, 0, 1); - memset (q, 0, 2); // { dg-warning "writing 2 bytes into a region of size 1 " } + memset (q, 0, 1); // { dg-warning "writing 1 byte into a region of size 0 " "" { target *-*-* } 0 } + memset (q, 0, 2); // { dg-warning "writing 2 bytes into a region of size 0 " } } { @@ -345,7 +345,7 @@ void test_max (void) not reflected in the determaxed offset). */ char *q = MAX (p1, p2); - memset (q, 0, 1); // { dg-warning "writing 1 byte into a region of size 0 " } + memset (q, 0, 1); } {