From patchwork Thu Jul 21 11:27:53 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 651166 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 3rwBNc3d8Dz9sCy for ; Thu, 21 Jul 2016 21:28:16 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=gvmWsXY4; 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 :mime-version:in-reply-to:references:from:date:message-id :subject:to:cc:content-type; q=dns; s=default; b=Ym7LEHDiQiuBvVL MufH6fZgIQhD7h76tKwMuwX6A3HxsrxxRl9E7AYPLOPMFecIai2kdmB+cZ3eUbOx awjTjbPSNMzrvAkbevGt59CZGgPw4iy1WiWsT4orY7w6a4lgLC9CwxO3cF2FEu3q RQfs1LTOnZaH87P9fWL8U6VOiX48= 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=LxYVYimLqNVsAWeAIe5rJ eMcZdA=; b=gvmWsXY4AEJCr2PD1odzpqZjB2qZWseD1WzJ3PnPsuGMDZ5opZLfJ YJoKtgx5JosnNUfJ3KGqQmIRQ196LT5mWHrvwmkJmcEGUND7XAvbbm/e5oh6EPKu RzWXUh1Py4EtqhivVYcB/IU6nTwhyS+KRfG0a0G+DWPZi6lEERvtvg= Received: (qmail 44703 invoked by alias); 21 Jul 2016 11:28:08 -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 44682 invoked by uid 89); 21 Jul 2016 11:28:07 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.0 required=5.0 tests=AWL, BAYES_50, FREEMAIL_FROM, RCVD_IN_DNSWL_LOW, SPF_PASS autolearn=ham version=3.3.2 spammy=sk:!check_, sk:check_, Robin, disturb X-HELO: mail-wm0-f54.google.com Received: from mail-wm0-f54.google.com (HELO mail-wm0-f54.google.com) (74.125.82.54) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-GCM-SHA256 encrypted) ESMTPS; Thu, 21 Jul 2016 11:27:57 +0000 Received: by mail-wm0-f54.google.com with SMTP id i5so21293425wmg.0 for ; Thu, 21 Jul 2016 04:27:56 -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=t/SSVYAiSIQlS6e7RGxgTSYsLXNhI8I18TMyDhs479k=; b=AxHEn0wBUqWFhK8Rt/JVw6XCzFaGWOG8aZZuQ3c5PhMEcpsifWXRWKfbZqqP0VZvza e+vOdWkoTGRFC48PQeiG0PMYFePfABEX9MZbbTSRvEjiQWPirX5RkIZJg4bDxSkAv+Y7 LmUk0pQ0xJae2sJzanYFg+wyC9mU9H04+gcXMgiBn3Zuo/Yd/kbJ3UAspttLyqvhNuae vaPSeMeJTyFAQTotI+I+i24g5u3qLXJ3q1XctLrp4hpp4xDlrKWHLUhx7Mbwb7jqdJr5 jmP1VVBDVL9TAsqZBQ+Ff7gjNBoZXAQlW89ayK5S7C5eoLJLbNOwHRCcQ0WXctgu1vgH hF1w== X-Gm-Message-State: ALyK8tJXVnZq47FeFw4Hl26aup8FILOUtF7+vP1UMu/sfNz4Xzmh2OE34h/kaTb08U5ISZkhAAWQbhJiUrkkaA== X-Received: by 10.28.35.86 with SMTP id j83mr16153814wmj.18.1469100474038; Thu, 21 Jul 2016 04:27:54 -0700 (PDT) MIME-Version: 1.0 Received: by 10.28.137.202 with HTTP; Thu, 21 Jul 2016 04:27:53 -0700 (PDT) In-Reply-To: <5790A709.4060804@linux.vnet.ibm.com> References: <5790A709.4060804@linux.vnet.ibm.com> From: Richard Biener Date: Thu, 21 Jul 2016 13:27:53 +0200 Message-ID: Subject: Re: [PATCH] Tree-level fix for PR 69526 To: Robin Dapp Cc: GCC Patches X-IsSubscribed: yes On Thu, Jul 21, 2016 at 12:42 PM, Robin Dapp wrote: > As described in https://gcc.gnu.org/bugzilla/show_bug.cgi?id=69526, we > currently fail to simplify cases like > > (unsigned long)(a - 1) + 1 > > to > > (unsigned long)a > > when VRP knows that (a - 1) does not overflow. > > This patch introduces a match.pd pattern as well as a helper function > that checks for overflow in a binary operation using VRP information and > simplifies when no overflow is present. > > Some effort was put in to stay in the inner type in cases like this > > (unsigned long)(a + CST1) - CST2 > -> > (unsigned long)(a + CST3) rather than > (unsigned long)a + CST3 > > where abs(CST3) = abs(CST1 - CST) <= abs(CST1). I wonder if this is > warranted, i.e. if it is always advantageous or if the evaluation should > rather involve a cost estimation - e.g. distinguish between costs for > operations in int vs. in long. > > Absence of signed overflow is also exploited: > > (long)(a + 2) - 1 > -> > (long)(a + 1) > > Bootstrapped and regression tested on s390x and x86_64. I find this a bit hard to follow (looking at the match.pd pattern). + if (check_inner_ovf) + { + // check if the inner binop does not overflow i.e. we have VRP + // information and can prove prove it + inner_ovf = binop_overflow (inner_op, @0, @1, inner_type); + } if !inner_ovf (just set that to false if !check_inner_ovf to simplify checks please). you know it's valid to transform the op to (T)@0 innerop (T)@1 outerop @2 (if T is wider than the inner type which I think you should check and which should simplify things). You can then combine (T)@1 and @2 where I think you fail to handle mixed MINUS_EXPR/PLUS_EXPR (practically you'll see only PLUS_EXPRs for integers). So you have (T)@0 + combined-in-T which you then can either emit or check whether combined-in-T fits in the inner type and @0 + combined-in-T does not overflow in which case (T)(@0 + combined-in-T) is safe. I believe that for simplicity we want to split this transform into two - one doing (T)(a + CST) - CST -> (T)a + CST' and one doing (T)a + CST -> (T)(a + CST). The testcase is rather unspecific as to what testcases shoudl fold and what not given your very simple scan and mixing should/should-not simplify cases. Please consider splitting it up and make it a run test that verifies the bogus transforms do not take place. Doing +static bool +simplify_plus_or_minus_using_ranges (gimple_stmt_iterator *gsi, gimple *stmt) +{ + enum tree_code code = gimple_assign_rhs_code (stmt); + tree op0 = gimple_assign_rhs1 (stmt); + tree op1 = gimple_assign_rhs2 (stmt); + + if ((code == PLUS_EXPR || code == MINUS_EXPR) && + op0 != NULL && op1 != NULL) + { + gimple *stmt1 = SSA_NAME_DEF_STMT (op0); + if (gassign *def = dyn_cast (stmt1)) + { + if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def)) + && TREE_CODE (op1) == INTEGER_CST) + { + if (fold_stmt (gsi, follow_single_use_edges)) + return true; causes such stmts to be folded twice as substitute_and_fold does /* Some statements may be simplified using propagator specific information. Do this before propagating into the stmt to not disturb pass specific information. */ if (fold_fn && (*fold_fn)(&i)) { did_replace = true; prop_stats.num_stmts_folded++; stmt = gsi_stmt (i); update_stmt (stmt); } /* Replace real uses in the statement. */ did_replace |= replace_uses_in (stmt, get_value_fn); /* If we made a replacement, fold the statement. */ if (did_replace) { fold_stmt (&i, follow_single_use_edges); stmt = gsi_stmt (i); which is less than ideal. I think that given we have fold_stmt following SSA edges and thus not only stmts we propagated into are possibly interesting to fold (but also their single-uses, recursively), we should evaluate the compile-time cost of doing the fold_stmt unconditionally. diff --git a/gcc/tree.c b/gcc/tree.c index 2295111..bc477fa 100644 --- a/gcc/tree.c +++ b/gcc/tree.c @@ -1358,6 +1358,108 @@ force_fit_type (tree type, const wide_int_ref &cst, return wide_int_to_tree (type, cst); } +bool binop_overflow (enum tree_code op, tree t1, tree t2, tree type) +{ tree.c doesn't look like the best fit. I think putting it into tree-vrp.c is better and I think that extract_range_from_binary_expr_1 itself should compute what we want here as additional output. Conservative handling for all but plus/minus is ok with me. + if (t1 == NULL_TREE || t2 == NULL_TREE || type == NULL_TREE) + return true; + + if (TYPE_OVERFLOW_UNDEFINED (type)) + return false; + + if (!INTEGRAL_TYPE_P (type)) + return true; note that we'll ICE if you call TYPE_OVERFLOW_UNDEFINED on a type that is not ANY_INTEGRAL_TYPE_P, so better re-order the checks. Thanks, Richard. > Regards > Robin