From patchwork Tue Mar 29 11:23:48 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Palka X-Patchwork-Id: 602853 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 3qZ7hY3b79z9s3v for ; Tue, 29 Mar 2016 22:24:13 +1100 (AEDT) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=ZX8ijceW; 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:from :date:to:cc:subject:in-reply-to:message-id:references :mime-version:content-type; q=dns; s=default; b=PMLWyEgRAT8H0S5I sw1kNBTThfzMKi91IPfMVQAjAldjG67szcE/VxHQyXbVVFfVK4eyMVwYZFvFkWLK XlbzMlchUlJeznzCMMH5gxRWMXRZuOVSsw6Yg4SMCRYG4aP3Bsr+9s7CUXspry/h /y0GoynXDFBuxrZKmGGw9G8ulMs= 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:from :date:to:cc:subject:in-reply-to:message-id:references :mime-version:content-type; s=default; bh=vKV2WwrxlxsQsH/Ik5WO90 5bHSI=; b=ZX8ijceWkYpEDdegZMPYpHPtBByCvgY11hsE41HG/9aeEf9wRHNugL G2qXxOqdH2G2b2cQHrq1AYr4ZXJ4dQHjL5xl4ImNrXR8oH+brzzpH2c9geMYbEfw +Sz3UQx6bgVJT0fcx4FRZzeGwkfYZUnG0jRtNvmtf6pmZtwsuPb+0= Received: (qmail 39023 invoked by alias); 29 Mar 2016 11:24:04 -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 38988 invoked by uid 89); 29 Mar 2016 11:24:02 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.6 required=5.0 tests=BAYES_00, RCVD_IN_DNSWL_LOW autolearn=ham version=3.3.2 spammy=cst, CST, patrick@parcs.ath.cx, patrickparcsathcx X-HELO: mail-qk0-f176.google.com Received: from mail-qk0-f176.google.com (HELO mail-qk0-f176.google.com) (209.85.220.176) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-GCM-SHA256 encrypted) ESMTPS; Tue, 29 Mar 2016 11:23:52 +0000 Received: by mail-qk0-f176.google.com with SMTP id x64so4336253qkd.1 for ; Tue, 29 Mar 2016 04:23:51 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:date:to:cc:subject:in-reply-to:message-id :references:user-agent:mime-version; bh=xQdYXP4hGQxv6Fa8fpfwwTYpYWfIAqnnONsuC530M5k=; b=PEiUujAjcMKJOLezszlGId49f0UQNg7j6rkYmiRBCBjWlwHJK5H0aNqgTwvxlw0lsX kJwiraIGd93kQyoNeYHY/EcnPRPm4fNqCx7EDRVdN5TzOvL7rIqDD0iGI9CQYc+eZl8b 11z1RpDZub4KifDKL5QrxkiacFER4pZTdt9MPxLJQIerP1nIhgqdI2nmZWiVTBmPflfn HBSWVgdcKl6LyWxGqhuaGPIgw3GfFNCWB+KbNBFygNfuKBMZ35TCYYHr1tPjPxQHCsCD T7g6eqlO/VfSnIKN0jUTFKbt8Wvso4YKasPotB2TKeNnd209jupqZ9CTdxgZJiRf/GCM TQXw== X-Gm-Message-State: AD7BkJLdTHeU/hem+3Prgm69rnUUdIBBTukSc75u10qa4v+O9DytcH2o0CuVJXTDekbjxw== X-Received: by 10.55.73.199 with SMTP id w190mr1842055qka.77.1459250630147; Tue, 29 Mar 2016 04:23:50 -0700 (PDT) Received: from [192.168.1.130] (ool-4353abbc.dyn.optonline.net. [67.83.171.188]) by smtp.gmail.com with ESMTPSA id s8sm13572731qhb.20.2016.03.29.04.23.49 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 29 Mar 2016 04:23:49 -0700 (PDT) From: Patrick Palka X-Google-Original-From: Patrick Palka Date: Tue, 29 Mar 2016 07:23:48 -0400 (EDT) To: Richard Biener cc: Patrick Palka , GCC Patches Subject: Re: [PATCH] Fix PR tree-optimization/59124 (bogus -Warray-bounds warning) In-Reply-To: Message-ID: References: <1459105083-24035-1-git-send-email-patrick@parcs.ath.cx> User-Agent: Alpine 2.20.11 (DEB 116 2015-12-14) MIME-Version: 1.0 On Tue, 29 Mar 2016, Richard Biener wrote: > On Sun, Mar 27, 2016 at 11:37 PM, Patrick Palka wrote: > > On Sun, 27 Mar 2016, Patrick Palka wrote: > > > >> In unrolling of the inner loop in the test case below we introduce > >> unreachable code that otherwise contains out-of-bounds array accesses. > >> This is because the estimation of the maximum number of iterations of > >> the inner loop is too conservative: we assume 6 iterations instead of > >> the actual 4. > >> > >> Nonetheless, VRP should be able to tell that the code is unreachable so > >> that it doesn't warn about it. The only thing holding VRP back is that > >> it doesn't look through conditionals of the form > >> > >> if (j_10 != CST1) where j_10 = j_9 + CST2 > >> > >> so that it could add the assertion > >> > >> j_9 != (CST1 - CST2) > >> > >> This patch teaches VRP to detect such conditionals and to add such > >> assertions, so that it could remove instead of warn about the > >> unreachable code created during loop unrolling. > >> > >> What this addition does with the test case below is something like this: > >> > >> ASSERT_EXPR (i <= 5); > >> for (i = 1; i < 6; i++) > >> { > >> j = i - 1; > >> if (j == 0) > >> break; > >> // ASSERT_EXPR (i != 1) > >> bar[j] = baz[j]; > >> > >> j = i - 2 > >> if (j == 0) > >> break; > >> // ASSERT_EXPR (i != 2) > >> bar[j] = baz[j]; > >> > >> j = i - 3 > >> if (j == 0) > >> break; > >> // ASSERT_EXPR (i != 3) > >> bar[j] = baz[j]; > >> > >> j = i - 4 > >> if (j == 0) > >> break; > >> // ASSERT_EXPR (i != 4) > >> bar[j] = baz[j]; > >> > >> j = i - 5 > >> if (j == 0) > >> break; > >> // ASSERT_EXPR (i != 5) > >> bar[j] = baz[j]; > >> > >> j = i - 6 > >> if (j == 0) > >> break; > >> // ASSERT_EXPR (i != 6) > >> bar[j] = baz[j]; // unreachable because (i != 6 && i <= 5) is always false > >> } > >> > >> (I think the patch I sent a year ago that improved the > >> register_edge_assert stuff would have fixed this too. I'll try to > >> post it again during next stage 1. > >> https://gcc.gnu.org/ml/gcc-patches/2014-11/msg00908.html) > >> > >> Bootstrap + regtest in progress on x86_64-pc-linux-gnu, does this look > >> OK to commit after testing? > >> > >> gcc/ChangeLog: > >> > >> PR tree-optimization/59124 > >> * tree-vrp.c (register_edge_assert_for): For NAME != CST1 > >> where NAME = A + CST2 add the assertion A != (CST1 - CST2). > >> > >> gcc/testsuite/ChangeLog: > >> > >> PR tree-optimization/59124 > >> * gcc.dg/Warray-bounds-19.c: New test. > >> --- > >> gcc/testsuite/gcc.dg/Warray-bounds-19.c | 17 +++++++++++++++++ > >> gcc/tree-vrp.c | 22 ++++++++++++++++++++++ > >> 2 files changed, 39 insertions(+) > >> create mode 100644 gcc/testsuite/gcc.dg/Warray-bounds-19.c > >> > >> diff --git a/gcc/testsuite/gcc.dg/Warray-bounds-19.c b/gcc/testsuite/gcc.dg/Warray-bounds-19.c > >> new file mode 100644 > >> index 0000000..e2f9661 > >> --- /dev/null > >> +++ b/gcc/testsuite/gcc.dg/Warray-bounds-19.c > >> @@ -0,0 +1,17 @@ > >> +/* PR tree-optimization/59124 */ > >> +/* { dg-options "-O3 -Warray-bounds" } */ > >> + > >> +unsigned baz[6]; > >> + > >> +void foo(unsigned *bar, unsigned n) > >> +{ > >> + unsigned i, j; > >> + > >> + if (n > 6) > >> + n = 6; > >> + > >> + for (i = 1; i < n; i++) > >> + for (j = i - 1; j > 0; j--) > >> + bar[j - 1] = baz[j - 1]; > >> +} > >> + > >> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c > >> index b5654c5..31bd575 100644 > >> --- a/gcc/tree-vrp.c > >> +++ b/gcc/tree-vrp.c > >> @@ -5820,6 +5820,28 @@ register_edge_assert_for (tree name, edge e, gimple_stmt_iterator si, > >> } > >> } > >> > >> + /* In the case of NAME != CST1 where NAME = A + CST2 we can > >> + assert that NAME != (CST1 - CST2). */ > > > > This should say A != (...) not NAME != (...) > > > >> + if ((comp_code == EQ_EXPR || comp_code == NE_EXPR) > >> + && TREE_CODE (val) == INTEGER_CST) > >> + { > >> + gimple *def_stmt = SSA_NAME_DEF_STMT (name); > >> + > >> + if (is_gimple_assign (def_stmt) > >> + && gimple_assign_rhs_code (def_stmt) == PLUS_EXPR) > >> + { > >> + tree op0 = gimple_assign_rhs1 (def_stmt); > >> + tree op1 = gimple_assign_rhs2 (def_stmt); > >> + if (TREE_CODE (op0) == SSA_NAME > >> + && TREE_CODE (op1) == INTEGER_CST) > >> + { > >> + op1 = int_const_binop (MINUS_EXPR, val, op1); > >> + register_edge_assert_for_2 (op0, e, si, comp_code, > >> + op0, op1, is_else_edge); > > > > The last argument to register_edge_assert_for_2() should be false not > > is_else_edge since comp_code is already inverted. > > > > Consider these two things fixed. Also I moved down the new code so that > > it's at the very bottom of register_edge_assert_for. Here's an updated > > patch that passes bootstrap + regtest. > > > > -- 8< -- > > > > gcc/ChangeLog: > > > > PR tree-optimization/59124 > > * tree-vrp.c (register_edge_assert_for): For NAME != CST1 > > where NAME = A + CST2 add the assertion A != (CST1 - CST2). > > > > gcc/testsuite/ChangeLog: > > > > PR tree-optimization/59124 > > * gcc.dg/Warray-bounds-19.c: New test. > > --- > > gcc/testsuite/gcc.dg/Warray-bounds-19.c | 17 +++++++++++++++++ > > gcc/tree-vrp.c | 22 ++++++++++++++++++++++ > > 2 files changed, 39 insertions(+) > > create mode 100644 gcc/testsuite/gcc.dg/Warray-bounds-19.c > > > > diff --git a/gcc/testsuite/gcc.dg/Warray-bounds-19.c b/gcc/testsuite/gcc.dg/Warray-bounds-19.c > > new file mode 100644 > > index 0000000..e2f9661 > > --- /dev/null > > +++ b/gcc/testsuite/gcc.dg/Warray-bounds-19.c > > @@ -0,0 +1,17 @@ > > +/* PR tree-optimization/59124 */ > > +/* { dg-options "-O3 -Warray-bounds" } */ > > + > > +unsigned baz[6]; > > + > > +void foo(unsigned *bar, unsigned n) > > +{ > > + unsigned i, j; > > + > > + if (n > 6) > > + n = 6; > > + > > + for (i = 1; i < n; i++) > > + for (j = i - 1; j > 0; j--) > > + bar[j - 1] = baz[j - 1]; > > +} > > + > > diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c > > index b5654c5..a009f7a 100644 > > --- a/gcc/tree-vrp.c > > +++ b/gcc/tree-vrp.c > > @@ -5841,6 +5841,28 @@ register_edge_assert_for (tree name, edge e, gimple_stmt_iterator si, > > register_edge_assert_for_1 (op1, EQ_EXPR, e, si); > > } > > } > > + > > + /* In the case of NAME != CST1 where NAME = A + CST2 we can > > + assert that A != (CST1 - CST2). */ > > + if ((comp_code == EQ_EXPR || comp_code == NE_EXPR) > > + && TREE_CODE (val) == INTEGER_CST) > > + { > > + gimple *def_stmt = SSA_NAME_DEF_STMT (name); > > + > > + if (is_gimple_assign (def_stmt) > > + && gimple_assign_rhs_code (def_stmt) == PLUS_EXPR) > > + { > > + tree op0 = gimple_assign_rhs1 (def_stmt); > > + tree op1 = gimple_assign_rhs2 (def_stmt); > > + if (TREE_CODE (op0) == SSA_NAME > > + && TREE_CODE (op1) == INTEGER_CST) > > + { > > + op1 = int_const_binop (MINUS_EXPR, val, op1); > > Please add > > if (TREE_OVERFLOW_P (op1)) > op1 = drop_tree_overflow (op1); > > here. Done. > > > + register_edge_assert_for_2 (op0, e, si, comp_code, > > + op0, op1, false); > > I wonder why you recurse to register_edge_assert_for_2 here rather than > calling register_new_assert_for which is what the cases in > register_edge_assert_for_2 > do. And incidentially a more generic case of this pattern is handled > there, so why > not add this code in register_edge_assert_for_2 in the first place? There is > > > if (TREE_CODE_CLASS (comp_code) == tcc_comparison > && TREE_CODE (val) == INTEGER_CST) > { > gimple *def_stmt = SSA_NAME_DEF_STMT (name); > ... > > the case itself is simple enough to be worth adding to fix the regression. Done. I figured recursing would help to identify other useful assertions to add but it's not necessary to fix the test case. > > I also wonder why we don't have a match.pd / fold-const case for this, > the forwprop pass between cunrolli and vrp1 should have simplified > this then. fold_comparison has it (so it didn't get moved to match.pd): > > /* Transform comparisons of the form X +- C1 CMP C2 to X CMP C2 -+ C1. */ > if ((TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR) > && (equality_code > ... > > it's also more general in that it handles non-equality compares when overflow > is undefined. Note that at this stage I'm more comfortable with doing the > VRP trick than adding a new match.pd pattern (even if only handling the > equality compare case) - we'd need to think about what to exactly do > for a non-single-use case (probably depends on C2, if that's zero then > X +- C1 might set CC codes properly already). The operands in question are not single-use and C2 is zero so we'd already be hitting the edge case :( Here's an updated patch that calls drop_tree_overflow and moves it all to register_edge_assert_for_2. Does this look OK to commit after bootstrap and regtest? -- >8 -- gcc/ChangeLog: PR tree-optimization/59124 * tree-vrp.c (register_edge_assert_for_2): For NAME != CST1 where NAME = A + CST2 add the assertion A != (CST1 - CST2). gcc/testsuite/ChangeLog: PR tree-optimization/59124 * gcc.dg/Warray-bounds-19.c: New test. --- gcc/testsuite/gcc.dg/Warray-bounds-19.c | 17 +++++++++++++++++ gcc/tree-vrp.c | 19 +++++++++++++++++++ 2 files changed, 36 insertions(+) create mode 100644 gcc/testsuite/gcc.dg/Warray-bounds-19.c diff --git a/gcc/testsuite/gcc.dg/Warray-bounds-19.c b/gcc/testsuite/gcc.dg/Warray-bounds-19.c new file mode 100644 index 0000000..e2f9661 --- /dev/null +++ b/gcc/testsuite/gcc.dg/Warray-bounds-19.c @@ -0,0 +1,17 @@ +/* PR tree-optimization/59124 */ +/* { dg-options "-O3 -Warray-bounds" } */ + +unsigned baz[6]; + +void foo(unsigned *bar, unsigned n) +{ + unsigned i, j; + + if (n > 6) + n = 6; + + for (i = 1; i < n; i++) + for (j = i - 1; j > 0; j--) + bar[j - 1] = baz[j - 1]; +} + diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index b5654c5..87db548 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -5310,6 +5310,25 @@ register_edge_assert_for_2 (tree name, edge e, gimple_stmt_iterator bsi, if (is_gimple_assign (def_stmt)) rhs_code = gimple_assign_rhs_code (def_stmt); + /* In the case of NAME != CST1 where NAME = A + CST2 we can + assert that A != (CST1 - CST2). */ + if ((comp_code == EQ_EXPR || comp_code == NE_EXPR) + && rhs_code == PLUS_EXPR) + { + tree op0 = gimple_assign_rhs1 (def_stmt); + tree op1 = gimple_assign_rhs2 (def_stmt); + if (TREE_CODE (op0) == SSA_NAME + && TREE_CODE (op1) == INTEGER_CST + && live_on_edge (e, op0) + && !has_single_use (op0)) + { + op1 = int_const_binop (MINUS_EXPR, val, op1); + if (TREE_OVERFLOW (op1)) + op1 = drop_tree_overflow (op1); + register_new_assert_for (op0, op0, comp_code, op1, NULL, e, bsi); + } + } + /* Add asserts for NAME cmp CST and NAME being defined as NAME = (int) NAME2. */ if (!TYPE_UNSIGNED (TREE_TYPE (val))