From patchwork Wed Jul 20 22:07:29 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Prathamesh Kulkarni X-Patchwork-Id: 72518 Delivered-To: patch@linaro.org Received: by 10.140.29.52 with SMTP id a49csp107301qga; Wed, 20 Jul 2016 15:08:22 -0700 (PDT) X-Received: by 10.66.41.133 with SMTP id f5mr79448672pal.70.1469052502603; Wed, 20 Jul 2016 15:08:22 -0700 (PDT) Return-Path: Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id k4si5569790pfj.91.2016.07.20.15.08.22 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 20 Jul 2016 15:08:22 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-return-432156-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) client-ip=209.132.180.131; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org; spf=pass (google.com: domain of gcc-patches-return-432156-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-432156-patch=linaro.org@gcc.gnu.org; dmarc=fail (p=NONE dis=NONE) header.from=linaro.org DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :mime-version:in-reply-to:references:from:date:message-id :subject:to:cc:content-type; q=dns; s=default; b=mMjjDc4O0GX69/3 3jDNCv+PtngMjwF1kMPGAA+4JoZ04Ilp4xAds75la/B5Ddek4Fn3PKR9YnxvvusT 2m5vxX595MiPpbvJvvfQlT9BXBQDpNQo+1LEGlLNbUyhCUW38jXFc+uz2YAJQpfN JJUMcMS3rGjscm119JGB7jcZAKWU= 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 :mime-version:in-reply-to:references:from:date:message-id :subject:to:cc:content-type; s=default; bh=bgXF+kqFAEnznQJmBwwGU RN7T5E=; b=uyG0kOVuj8Ic2q6awz16sXvhvR5PoZ/bbjDKVbDtJBmOVZTmPpJMD mYdO6/SDRUPHgRIzIIu6BLcIpCeHUvwCEv5BdQwgo7r40yWG+uWNGC/T3xtd4flM gMju9mpmKGvUDqLss2p2uqiWh86wUZR8lrgUX290mL0KimQhrA/bkc= Received: (qmail 21438 invoked by alias); 20 Jul 2016 22:07:43 -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 21337 invoked by uid 89); 20 Jul 2016 22:07:42 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.1 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_LOW, SPF_PASS autolearn=ham version=3.3.2 spammy=his X-HELO: mail-it0-f48.google.com Received: from mail-it0-f48.google.com (HELO mail-it0-f48.google.com) (209.85.214.48) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-GCM-SHA256 encrypted) ESMTPS; Wed, 20 Jul 2016 22:07:32 +0000 Received: by mail-it0-f48.google.com with SMTP id u186so826551ita.0 for ; Wed, 20 Jul 2016 15:07:31 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=1v5K15CY7g7/ZYQ45bzq+I48x4m/klfVOL1EwpUQnGU=; b=K1dqKqEN7Z8KkOH36cdcR6aIYzHavDccXfJWtM4NbGECa/tdqQPFcXdr0nmD6s1O+M sOjq2SdoYdLzhvcl0zmHBF+5p09WB+qBwbiT8VQb/OQNM1tvpb8skNcH5q8PePegxwq7 BIuBoOJS0h58Yjipj+T2LkRALzkFQDdcGd99M6UVDpl8w+tq5tnWMyKNO/gkwlbyhiR9 wpcNUyKJtErjjyjcP+o1nirtCYLVpaB5Ccna4MQYWWXVYgVsfnXQIanNhF8JqWaNmlhA rnMg4ZSTslm9KFcH8/obhn31dO6tEo/pwWJ8r9h6S/aK2nIFtmcqcF7H+1sbAzpUNmX7 NEWA== X-Gm-Message-State: ALyK8tJdpoWceCAF92Swi1pRewsKAcjvOmSFjOpxaZtxvBXZ9tLLoWby7TX+DveScQRYLgAzrKfZ2DrSmDTwikJS X-Received: by 10.36.120.150 with SMTP id p144mr926597itc.44.1469052449764; Wed, 20 Jul 2016 15:07:29 -0700 (PDT) MIME-Version: 1.0 Received: by 10.36.48.197 with HTTP; Wed, 20 Jul 2016 15:07:29 -0700 (PDT) In-Reply-To: References: From: Prathamesh Kulkarni Date: Wed, 20 Jul 2016 23:07:29 +0100 Message-ID: Subject: Re: fold x ^ y to 0 if x == y To: Richard Biener Cc: gcc Patches , Jeff Law X-IsSubscribed: yes On 20 July 2016 at 16:35, Richard Biener wrote: > On Wed, 20 Jul 2016, Prathamesh Kulkarni wrote: > >> On 8 July 2016 at 12:29, Richard Biener wrote: >> > On Fri, 8 Jul 2016, Richard Biener wrote: >> > >> >> On Fri, 8 Jul 2016, Prathamesh Kulkarni wrote: >> >> >> >> > Hi Richard, >> >> > For the following test-case: >> >> > >> >> > int f(int x, int y) >> >> > { >> >> > int ret; >> >> > >> >> > if (x == y) >> >> > ret = x ^ y; >> >> > else >> >> > ret = 1; >> >> > >> >> > return ret; >> >> > } >> >> > >> >> > I was wondering if x ^ y should be folded to 0 since >> >> > it's guarded by condition x == y ? >> >> > >> >> > optimized dump shows: >> >> > f (int x, int y) >> >> > { >> >> > int iftmp.0_1; >> >> > int iftmp.0_4; >> >> > >> >> > : >> >> > if (x_2(D) == y_3(D)) >> >> > goto ; >> >> > else >> >> > goto ; >> >> > >> >> > : >> >> > iftmp.0_4 = x_2(D) ^ y_3(D); >> >> > >> >> > : >> >> > # iftmp.0_1 = PHI >> >> > return iftmp.0_1; >> >> > >> >> > } >> >> > >> >> > The attached patch tries to fold for above case. >> >> > I am checking if op0 and op1 are equal using: >> >> > if (bitmap_intersect_p (vr1->equiv, vr2->equiv) >> >> > && operand_equal_p (vr1->min, vr1->max) >> >> > && operand_equal_p (vr2->min, vr2->max)) >> >> > { /* equal /* } >> >> > >> >> > I suppose intersection would check if op0 and op1 have equivalent ranges, >> >> > and added operand_equal_p check to ensure that there is only one >> >> > element within the range. Does that look correct ? >> >> > Bootstrap+test in progress on x86_64-unknown-linux-gnu. >> >> >> >> I think VRP is the wrong place to catch this and DOM should have but it >> >> does >> >> >> >> Optimizing block #3 >> >> >> >> 1>>> STMT 1 = x_2(D) le_expr y_3(D) >> >> 1>>> STMT 1 = x_2(D) ge_expr y_3(D) >> >> 1>>> STMT 1 = x_2(D) eq_expr y_3(D) >> >> 1>>> STMT 0 = x_2(D) ne_expr y_3(D) >> >> 0>>> COPY x_2(D) = y_3(D) >> >> 0>>> COPY y_3(D) = x_2(D) >> >> Optimizing statement ret_4 = x_2(D) ^ y_3(D); >> >> Replaced 'x_2(D)' with variable 'y_3(D)' >> >> Replaced 'y_3(D)' with variable 'x_2(D)' >> >> Folded to: ret_4 = x_2(D) ^ y_3(D); >> >> LKUP STMT ret_4 = x_2(D) bit_xor_expr y_3(D) >> >> >> >> heh, registering both reqivalencies is obviously not going to help... >> >> >> >> The 2nd equivalence is from doing >> >> >> >> /* We already recorded that LHS = RHS, with canonicalization, >> >> value chain following, etc. >> >> >> >> We also want to record RHS = LHS, but without any >> >> canonicalization >> >> or value chain following. */ >> >> if (TREE_CODE (rhs) == SSA_NAME) >> >> const_and_copies->record_const_or_copy_raw (rhs, lhs, >> >> SSA_NAME_VALUE (rhs)); >> >> >> >> generally recording both is not helpful. Jeff? This seems to be >> >> r233207 (fix for PR65917) which must have regressed this testcase. >> > >> > Just verified it works fine on the GCC 5 branch: >> > >> > Optimizing block #3 >> > >> > 0>>> COPY y_3(D) = x_2(D) >> > 1>>> STMT 1 = x_2(D) le_expr y_3(D) >> > 1>>> STMT 1 = x_2(D) ge_expr y_3(D) >> > 1>>> STMT 1 = x_2(D) eq_expr y_3(D) >> > 1>>> STMT 0 = x_2(D) ne_expr y_3(D) >> > Optimizing statement ret_4 = x_2(D) ^ y_3(D); >> > Replaced 'y_3(D)' with variable 'x_2(D)' >> > Applying pattern match.pd:240, gimple-match.c:11346 >> > gimple_simplified to ret_4 = 0; >> > Folded to: ret_4 = 0; >> I have reported it as PR71947. >> Could you help me point out how to fix this ? > > Not record both equivalences. This might break the testcase it was > introduced for (obviously). Which is why I CCed Jeff for his opinion. Well, folding happens for x - y, if x == y. int f(int x, int y) { int ret; if (x == y) ret = x - y; else ret = 1; return ret; } For the above test-case, extract_range_from_binary_expr_1() determines that range of ret = [0, 0] and propagates it. vrp1 dump: f (int x, int y) { int ret; : if (x_2(D) == y_3(D)) goto ; else goto ; : ret_4 = x_2(D) - y_3(D); : # ret_1 = PHI <0(3), 10(2)> return ret_1; } Then the dce pass removes ret_4 = x_2(D) - y_3(D) since it's redundant. However it appears vrp fails to notice the equality for the following test-case, and sets range for ret to VARYING. int f(int x, int y, int a, int b) { int ret = 10; if (a == x && b == y && a == b) ret = x - y; return ret; } Looking at the vrp dump, shows the following form after inserting ASSERT_EXPR: SSA form after inserting ASSERT_EXPRs f (int x, int y, int a, int b) { int ret; _Bool _1; _Bool _2; _Bool _3; : _1 = a_5(D) == x_6(D); _2 = b_7(D) == y_8(D); _3 = _1 & _2; if (_3 != 0) goto ; else goto ; : a_11 = ASSERT_EXPR ; x_12 = ASSERT_EXPR ; b_13 = ASSERT_EXPR ; y_14 = ASSERT_EXPR ; if (a_11 == b_13) goto ; else goto ; : ret_9 = x_12 ^ y_14; : # ret_4 = PHI <10(2), 10(3), ret_9(4)> return ret_4; } Shouldn't there also be a range assertion for a_11 == b_13 ? Should we modify extract_range_from_binary_expr_1 to handle this case for bit_xor_expr so similar to minus_expr case, the range [0, 0] would get propagated and make ret = x ^ y redundant which will then be removed by dce pass ? I have attached untested patch for that. Does it look OK ? (It also doesn't handle a == x && b == y && a == b case). Thanks, Prathamesh > > Richard. > > -- > Richard Biener > SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg) diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index 4333d60..ef00ee2 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -2250,6 +2250,7 @@ extract_range_from_binary_expr_1 (value_range *vr, TODO, we may be able to derive anti-ranges in some cases. */ if (code != BIT_AND_EXPR && code != BIT_IOR_EXPR + && code != BIT_XOR_EXPR && code != TRUNC_DIV_EXPR && code != FLOOR_DIV_EXPR && code != CEIL_DIV_EXPR @@ -3104,6 +3105,19 @@ extract_range_from_binary_expr_1 (value_range *vr, ; else max = min = NULL_TREE; + + /* Set range 0 for r, where r = op0 ^ op1 and op0 equals op1. */ + /* FIXME: I am using bitmap_intersect_p() to determine if vr0 + and vr1 are equivalent and operand_equal_p() to ensure + that range has only one symbol. Is this correct ?. */ + if (TREE_CODE (vr0.min) == SSA_NAME + && TREE_CODE (vr0.max) == SSA_NAME + && TREE_CODE (vr1.min) == SSA_NAME + && TREE_CODE (vr1.max) == SSA_NAME + && vr0.equiv && vr1.equiv + && bitmap_intersect_p (vr0.equiv, vr1.equiv) + && operand_equal_p (vr0.min, vr0.max, 0)) + max = min = build_int_cst (expr_type, 0); } } else