From patchwork Thu Aug 11 04:11:37 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kugan Vivekanandarajah X-Patchwork-Id: 73704 Delivered-To: patch@linaro.org Received: by 10.140.29.52 with SMTP id a49csp712113qga; Wed, 10 Aug 2016 21:12:11 -0700 (PDT) X-Received: by 10.98.59.70 with SMTP id i67mr13305759pfa.45.1470888731112; Wed, 10 Aug 2016 21:12:11 -0700 (PDT) Return-Path: Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id i5si995482pae.80.2016.08.10.21.12.10 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 10 Aug 2016 21:12:11 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-return-433753-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-433753-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-433753-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 :subject:to:references:cc:from:message-id:date:mime-version :in-reply-to:content-type; q=dns; s=default; b=f2hADhOpXBVx7tAQp gW2WX6CsfiUsyoAg9klpJ1cS53JayODC0LhdTIJ7ewZp+kWs2HlXalixZyxcb3aV xmGHJd3N5q5skfTfgnqrKzg+WN0Ulqe8vBssfo6shg+JeHKu1Ly6bqypqhKIVUQK cx2DNE1cR84aqmGxBN5b6rsonU= 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 :subject:to:references:cc:from:message-id:date:mime-version :in-reply-to:content-type; s=default; bh=kMChljiY11TgPaoiNctFo2P DcMA=; b=hhKOZ5Bt6O49v61+I6AtgfCrct8ciggcWWPoeqy33rFedr7OiU9boVF BcqnURUOxrgUlXo5aZolT72nvBFV9zHY5Efxe6xSqzV+e/K3apImnjrKlRwy6fAt V0gwoWpqeD7Ej5qG8yK8l7FDZnBCt543U0AnmQ0Bd+HdhVFZrdEw= Received: (qmail 57867 invoked by alias); 11 Aug 2016 04:11:57 -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 57855 invoked by uid 89); 11 Aug 2016 04:11:56 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.4 required=5.0 tests=AWL, BAYES_00, LOTS_OF_MONEY, RCVD_IN_DNSWL_LOW, SPF_PASS autolearn=no version=3.3.2 spammy=divide, profitability, 1111, $24 X-HELO: mail-pf0-f174.google.com Received: from mail-pf0-f174.google.com (HELO mail-pf0-f174.google.com) (209.85.192.174) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-GCM-SHA256 encrypted) ESMTPS; Thu, 11 Aug 2016 04:11:46 +0000 Received: by mail-pf0-f174.google.com with SMTP id h186so22346805pfg.3 for ; Wed, 10 Aug 2016 21:11:46 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:subject:to:references:cc:from:message-id:date :user-agent:mime-version:in-reply-to; bh=S4KRzrxJzQjYEbrgW84mlauxjnZaAvgWsjgB++a7GPk=; b=h6sX8JpwxGjgACYuInA5k0QiQRZX1gP/4G3CHNcDthnHpr7Rm+91dt5V9It9Xj9bQu yiRdMx87kAsZ9E5EdBhnYWwaWwSQOqHXCQrfePOa1Yon5i5ktrcFP6k6fNgwAS7DeC0i kfDsMNLxlBVSXD1DDltPpXYQjgaYXNmm04I6xJbF/pnmHp95kYSYxgVtIdJOw8pMAqfI 0HgBSxP9bRH+P1N5qJg25d1Lr2LmShZkdht5TAiwym7cmdNGBtVaJcgd8FGTFWi2dsCu zAijjVJWiJZER5FWGVU8xW159SJp5T3TRO1WFg42jrjo+27rnS1N4QQVJC3EYOYCIDGz exgA== X-Gm-Message-State: AEkoouuvOXEz76Ckl9gtzepnEM33VgAgtCFu3b7H6qTqEJGYpixVNfdUUXej3IblfCTIfk9l X-Received: by 10.98.64.193 with SMTP id f62mr13360299pfd.141.1470888704261; Wed, 10 Aug 2016 21:11:44 -0700 (PDT) Received: from [10.1.1.4] (58-6-183-210.dyn.iinet.net.au. [58.6.183.210]) by smtp.gmail.com with ESMTPSA id yp10sm785018pab.25.2016.08.10.21.11.42 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 10 Aug 2016 21:11:43 -0700 (PDT) Subject: Re: [RFC][PR61839]Convert CST BINOP COND_EXPR to COND_EXPR ? (CST BINOP 1) : (CST BINOP 0) To: Richard Biener References: <5712C739.4080101@linaro.org> Cc: "gcc-patches@gcc.gnu.org" From: kugan Message-ID: <028aa472-0193-1077-bad3-d1dba1b324e2@linaro.org> Date: Thu, 11 Aug 2016 14:11:37 +1000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.2.0 MIME-Version: 1.0 In-Reply-To: X-IsSubscribed: yes Hi Richard, On 09/08/16 20:22, Richard Biener wrote: > On Tue, Aug 9, 2016 at 4:51 AM, Kugan Vivekanandarajah > wrote: >> Hi Richard, >> >> Thanks for the review. >> >> On 29 April 2016 at 20:47, Richard Biener wrote: >>> On Sun, Apr 17, 2016 at 1:14 AM, kugan >>> wrote: >>>> As explained in PR61839, >>>> >>>> Following difference results in extra instructions: >>>> - c = b != 0 ? 486097858 : 972195717; >>>> + c = a + 972195718 >> (b != 0); >>>> >>>> As suggested in PR, attached patch converts CST BINOP COND_EXPR to COND_EXPR >>>> ? (CST BINOP 1) : (CST BINOP 0). >>>> >>>> Bootstrapped and regression tested for x86-64-linux-gnu with no new >>>> regression. Is this OK for statege-1. >>> >>> You are missing a testcase. >>> >>> I think the transform can be generalized to any two-value value-range by >>> instead of >>> >>> lhs = cond_res ? (cst binop 1) : (cst binop 0) >>> >>> emitting >>> >>> lhs = tmp == val1 ? (cst binop val1) : (cst binop val2); >>> >>> In the PR I asked the transform to be only carried out if cond_res and >>> tmp have a single use (and thus they'd eventually vanish). >>> >>> I'm not sure if a general two-value "constant" propagation is profitable >>> which is why I was originally asking for the pattern to only apply >>> if the resulting value is used in a comparison which we could then >>> in turn simplify by substituting COND_RES (or ! COND_RES) for it. >>> For the general two-value case we'd substitute it with tmp [=!]= val[12] >>> dependent on which constant is cheaper to test for. >>> >>> So I think this needs some exploring work on which way to go >>> and which transform is profitable in the end. I think the general >>> two-value case feeding a condition will be always profitable. >> >> >> Please find a modified version which checks for two-valued variable >> and uses this to optimize. In the attached test case (in function >> bar), we end up doing the conversion twice. >> >> Bootstrapped and regression tested on x86_64-linux-gnu without no new >> regressions. Is this OK for trunk? > > +/* Return true if VAR is a two-valued variable. Set MIN and MAX when it is > + true. Return false otherwise. */ > + > +static bool > +two_valued_val_range_p (tree var, tree *min, tree *max) > +{ > > I'd use A and B, not MIN/MAX given it's two values, not necessarily > a two-valued range (for example for ~[1, UINT_MAX-1] which you I have changed this. I don't think this would be the only VR_ANTI_RANGE. Others like TYPE_MIN + 1, TYPE_MIN + 2 should come as VR_RANGE. > don't handle). In theory VRP might get a more sophisticated range > representation to also allow a range consisting of just 3 and 7 for example. > I am not sure how this will be represented as value range. Is this for enum types where thhere is no valid values between 3 and 7 ? > + tree tmp > + = int_const_binop (PLUS_EXPR, > + vr->min, > + build_int_cst_type (TREE_TYPE (var), 1)); > + if (0 != compare_values (tmp, vr->max)) > + return false; > > I think simply > > if (wi::sub (vr->max, vr->min) == 1) I have changed this. > > might work as well and avoid building a tree node. > > + /* Convert: > + LHS = CST BINOP VAR > + where VAR is two-valued. > + > + To: > + LHS = VAR == VAL1 ? (CST BINOP VAL1) : (CST BINOP VAL2) */ > + > + if (TREE_CODE_CLASS (rhs_code) == tcc_binary > + && TREE_CODE (rhs1) == INTEGER_CST > + && TREE_CODE (rhs2) == SSA_NAME > > Note that for all commutative tcc_binary operators the constant will be on the > other operand. I think you need to handle the constant appearing in both places > (and for division for example watch out for a zero divisor). I have now canonicalized it in the beginning. I don't think it will affect other simplifications that comes after this transformation. > > + && has_single_use (rhs2) > + && two_valued_val_range_p (rhs2, &min, &max)) > + > + { > + tree cond = build2 (EQ_EXPR, TREE_TYPE (rhs2), rhs2, min); > + tree new_rhs1 = int_const_binop (rhs_code, rhs1, min); > + tree new_rhs2 = int_const_binop (rhs_code, rhs1, max); > > too many spaces after '='. Done. > > + > + if (new_rhs1 && new_rhs2) > > You didn't address my point about profitability - you test for a single use > but not for the kind of use. Please instead use I checked with some simple test-cases. In those cases it either improves or no difference. > > && single_imm_use (rhs2, &use_p, &use_stmt) > && gimple_code (use_stmt) == GIMPLE_COND Done. > > The testcase won't work on targets with small integers thus please > require int32plus. With the existing scan-dumps it's not obvious Done. > what transform it is testing for - please add a comment before > the dump scan reflecting the desired transform. Maybe also scan > "optimized" instead to also verify that followup transforms trigger. > Done. ASM difference for x86-64 is @@ -11,11 +11,7 @@ movl $1, 12(%rsp) movl 12(%rsp), %eax testl %eax, %eax - movl $972195717, %eax - setne %cl - sarl %cl, %eax - cmpl $486097858, %eax - jne .L5 + je .L5 xorl %eax, %eax addq $24, %rsp .cfi_remember_state function bar in the test-case is already optimized so no difference. I just added to make sure that the operation is correct. Bootstrapped and regression tested on x86_64-linux-gn with no new regressions. Is this OK for trunk now. Thanks, Kugan > Thanks, > Richard. > >> Thanks, >> Kugan >> >> gcc/testsuite/ChangeLog: >> >> 2016-08-09 Kugan Vivekanandarajah >> >> PR tree-optimization/61839 >> * gcc.dg/tree-ssa/pr61839.c: New test. >> >> gcc/ChangeLog: >> >> 2016-08-09 Kugan Vivekanandarajah >> >> PR tree-optimization/61839 >> * tree-vrp.c (two_valued_val_range_p): New. >> (simplify_stmt_using_ranges): Convert CST BINOP VAR where VAR is >> two-valued to VAR == VAL1 ? (CST BINOP VAL1) : (CST BINOP VAL2). diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr61839.c b/gcc/testsuite/gcc.dg/tree-ssa/pr61839.c index e69de29..abe46a0 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/pr61839.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr61839.c @@ -0,0 +1,44 @@ +/* PR tree-optimization/61839. */ +/* { dg-do run } */ +/* { dg-options "-O2 -fdump-tree-vrp1 -fdump-tree-optimized" } */ +/* { dg-require-effective-target int32plus } */ + +__attribute__ ((noinline)) +int foo () +{ + int a = -1; + volatile unsigned b = 1U; + int c = 1; + c = (a + 972195718) >> (1LU <= b); + if (c == 486097858) + ; + else + __builtin_abort (); + return 0; +} + +__attribute__ ((noinline)) +int bar () +{ + int a = -1; + volatile unsigned b = 1U; + int c = 1; + c = (a + 972195718) >> (b ? 2 : 3); + if (c == 243048929) + ; + else + __builtin_abort (); + return 0; +} + +int main () +{ + foo (); + bar (); +} + +/* Scan for c = 972195717) >> [0, 1] in function foo. */ +/* { dg-final { scan-tree-dump-times "972195717 : 486097858" 1 "vrp1" } } */ +/* Scan for c = 972195717) >> [2, 3] in function bar. */ +/* { dg-final { scan-tree-dump-times "243048929 : 121524464" 2 "vrp1" } } */ +/* { dg-final { scan-tree-dump-times "486097858" 0 "optimized" } } */ diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index 7c7ad91..b9013b3 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -10004,6 +10004,39 @@ simplify_internal_call_using_ranges (gimple_stmt_iterator *gsi, gimple *stmt) return true; } +/* Return true if VAR is a two-valued variable. Set a and b with the + two-values when it is true. Return false otherwise. */ + +static bool +two_valued_val_range_p (tree var, tree *a, tree *b) +{ + value_range *vr = get_value_range (var); + if ((vr->type != VR_RANGE + && vr->type != VR_ANTI_RANGE) + || !range_int_cst_p (vr)) + return false; + + if (vr->type == VR_RANGE + && wi::sub (vr->max, vr->min) == 1) + { + *a = vr->min; + *b = vr->max; + return true; + } + + /* ~[TYPE_MIN + 1, TYPE_MAX - 1] */ + if (vr->type == VR_ANTI_RANGE + && wi::sub (vr->min, wi::min_value (TREE_TYPE (var))) == 1 + && wi::sub (wi::max_value (TREE_TYPE (var)), vr->max) == 1) + { + *a = TYPE_MIN_VALUE (TREE_TYPE (var)); + *b = TYPE_MAX_VALUE (TREE_TYPE (var)); + return true; + } + + return false; +} + /* Simplify STMT using ranges if possible. */ static bool @@ -10014,6 +10047,61 @@ simplify_stmt_using_ranges (gimple_stmt_iterator *gsi) { enum tree_code rhs_code = gimple_assign_rhs_code (stmt); tree rhs1 = gimple_assign_rhs1 (stmt); + tree rhs2 = gimple_assign_rhs2 (stmt); + tree lhs = gimple_assign_lhs (stmt); + tree val1 = NULL_TREE, val2 = NULL_TREE; + use_operand_p use_p; + gimple *use_stmt; + + /* First canonicalize to simplify tests. */ + if (commutative_tree_code (rhs_code) + && TREE_CODE (rhs2) == INTEGER_CST) + std::swap (rhs1, rhs2); + + /* Convert: + LHS = CST BINOP VAR + Where VAR is two-valued and LHS is used in GIMPLE_COND only + To: + LHS = VAR == VAL1 ? (CST BINOP VAL1) : (CST BINOP VAL2) */ + + if (TREE_CODE_CLASS (rhs_code) == tcc_binary + && TREE_CODE (rhs1) == INTEGER_CST + && TREE_CODE (rhs2) == SSA_NAME + && single_imm_use (lhs, &use_p, &use_stmt) + && gimple_code (use_stmt) == GIMPLE_COND + && two_valued_val_range_p (rhs2, &val1, &val2)) + + { + tree new_rhs1 = NULL_TREE; + tree new_rhs2 = NULL_TREE; + switch (rhs_code) + { + case TRUNC_DIV_EXPR: + case CEIL_DIV_EXPR: + case FLOOR_DIV_EXPR: + case ROUND_DIV_EXPR: + case EXACT_DIV_EXPR: + /* Prevent divide by zero. */ + if (integer_zerop (val1) + || integer_zerop (val2)) + break; + default: + new_rhs1 = int_const_binop (rhs_code, rhs1, val1); + new_rhs2 = int_const_binop (rhs_code, rhs1, val2); + break; + } + + if (new_rhs1 && new_rhs2) + { + tree cond = build2 (EQ_EXPR, TREE_TYPE (rhs2), rhs2, val1); + gimple_assign_set_rhs_with_ops (gsi, + COND_EXPR, cond, + new_rhs1, + new_rhs2); + update_stmt (gsi_stmt (*gsi)); + return true; + } + } switch (rhs_code) {