From patchwork Tue Aug 9 02:51:23 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kugan Vivekanandarajah X-Patchwork-Id: 73512 Delivered-To: patch@linaro.org Received: by 10.140.29.52 with SMTP id a49csp263804qga; Mon, 8 Aug 2016 19:51:58 -0700 (PDT) X-Received: by 10.98.10.157 with SMTP id 29mr145490082pfk.62.1470711118537; Mon, 08 Aug 2016 19:51:58 -0700 (PDT) Return-Path: Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id j12si40140328pat.285.2016.08.08.19.51.58 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 08 Aug 2016 19:51:58 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-return-433526-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-433526-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-433526-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=gF24QWszJmRaAul 1v0PNgM/UDWidfQItPTag4mwk6rXHG7V1TCAAZ6PN0zYOvdUlVC5I3MLD2IKnlUZ eiEEsBDbIfA71AdYwhnzu1+Lb6W80XqleNzDyRMciJ8Gx40be+BSa9HgnwMEAAVm ZrAPCMiWnPAgu+iS+j5phhI72LF0= 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=eUa4sbWjxvk2hj4II7vcP ZRR4OI=; b=ty0Ra6swSCzzb0sGB04SqYIhkCCWs7LD12FX2hnOFS5xy4R72GiRN CJDKLF1TuhDWA9bhNjAXxNLsH1N51tEr3py0wWoOweoNZaxVtoloYunwph2Q1LkX swXwagmDTjgktEf5lkXg6z8Z0A10JVZhqZHob/ki4aUkZP1GpyFwIk= Received: (qmail 7783 invoked by alias); 9 Aug 2016 02:51:45 -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 7764 invoked by uid 89); 9 Aug 2016 02:51:39 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.6 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_LOW, SPF_PASS autolearn=ham version=3.3.2 spammy=val1, cst, CST, 2016-08-09 X-HELO: mail-qk0-f178.google.com Received: from mail-qk0-f178.google.com (HELO mail-qk0-f178.google.com) (209.85.220.178) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-GCM-SHA256 encrypted) ESMTPS; Tue, 09 Aug 2016 02:51:27 +0000 Received: by mail-qk0-f178.google.com with SMTP id t7so1274282qkh.0 for ; Mon, 08 Aug 2016 19:51:26 -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=mzCoMRZc4NmI6MkqZJWw6bq/DOWDZYFxgvr4Q4w/IKE=; b=LIJuTgg8vO3VN4BvUB71dHhuOBf4kaoP9r3X72rh4ngwN2W/kQzUdn0UxJeu9aTbB5 KW57+j6Wjh0FXoaFgfkqz98hW35zXgCO4BhruTC/L+UHyjZGp1UWksAtDEdexou5Q2ML gH7AjR+/rxqyAhGe/25McAKNfc5uszNAjYh/rBHqqYSW00YOxS2hWsGqxrlH0y+gJEF3 U7LTwoWdrzinGQVtRBW95Nb85Dmnd8988pjUlvjlbMkMwaH7x+/lT3m/ycywq/qO6FG4 U7D9NtmQM7Z0daR78MX60zo7ClQw78GfvtiL2G4x9FUJsdE38Vm/n/2gMbmWA7BxkMyU yhOw== X-Gm-Message-State: AEkoous5m0M8HJ0LDL/4eUAADOCulv7jUlZcc5lcucz49ldem84kD41Cc6RY4gDQ3UEIfmqJOkBv49LQRlzUjOQQ X-Received: by 10.55.31.198 with SMTP id n67mr33074972qkh.238.1470711084872; Mon, 08 Aug 2016 19:51:24 -0700 (PDT) MIME-Version: 1.0 Received: by 10.200.53.49 with HTTP; Mon, 8 Aug 2016 19:51:23 -0700 (PDT) In-Reply-To: References: <5712C739.4080101@linaro.org> From: Kugan Vivekanandarajah Date: Tue, 9 Aug 2016 12:51:23 +1000 Message-ID: Subject: Re: [RFC][PR61839]Convert CST BINOP COND_EXPR to COND_EXPR ? (CST BINOP 1) : (CST BINOP 0) To: Richard Biener Cc: "gcc-patches@gcc.gnu.org" X-IsSubscribed: yes 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? 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..1bb77d1 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/pr61839.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr61839.c @@ -0,0 +1,40 @@ +/* PR tree-optimization/61839 */ +/* { dg-do run } */ +/* { dg-options "-O2 -fdump-tree-vrp1" } */ + +__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 (); +} + +/* { dg-final { scan-tree-dump-times "486097858 : 972195717" 1 "vrp1" } } */ +/* { dg-final { scan-tree-dump-times "243048929 : 121524464" 2 "vrp1" } } */ diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index 7c7ad91..d5e2fc3 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -10004,6 +10004,27 @@ simplify_internal_call_using_ranges (gimple_stmt_iterator *gsi, gimple *stmt) return true; } +/* 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) +{ + value_range *vr = get_value_range (var); + if (vr->type != VR_RANGE + || !range_int_cst_p (vr)) + return false; + 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; + *min = vr->min; + *max = vr->max; + return true; +} + /* Simplify STMT using ranges if possible. */ static bool @@ -10014,6 +10035,38 @@ 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 min, max; + + /* 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 + && 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); + + if (new_rhs1 && new_rhs2) + { + gimple_assign_set_rhs_with_ops (gsi, + COND_EXPR, cond, + new_rhs1, + new_rhs2); + update_stmt (gsi_stmt (*gsi)); + return true; + } + } switch (rhs_code) {