From patchwork Thu May 5 01:57:27 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kugan Vivekanandarajah X-Patchwork-Id: 67191 Delivered-To: patch@linaro.org Received: by 10.140.92.199 with SMTP id b65csp502781qge; Wed, 4 May 2016 18:58:38 -0700 (PDT) X-Received: by 10.66.184.40 with SMTP id er8mr16911639pac.134.1462413518593; Wed, 04 May 2016 18:58:38 -0700 (PDT) Return-Path: Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id 12si7875555pft.105.2016.05.04.18.58.38 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 04 May 2016 18:58:38 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-return-426619-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-426619-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-426619-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=K1KMdBBZZ+sk5c0HR CxiQVP9oCtHTGVbrD+RS99PYNje8m7QivJx2ZaxKZKt2kR08ogxHbtpeae9TuBc8 xNSSVBn6o1EkmdB0POaTOcRhsIa7xBnwLO1Lp0atp1eKSk3dqc98bVx19jaaIUmb CBl5fo5rs92/4OA912qfpsTgCU= 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=IDCbC69djdVIhiebFoMg/4n b5nc=; b=G4xj5b/kMLInpO045ovY7Lgy1hBh2rrfmfGtntp1WzAE5/tKICpXT3S ZOWoJUtKtQd4Y/rcavRgZ1AkHV93s8ddUKmA558FhvxAvsnm4o+RPybjUIHn/+3z I1PtQED8C+InfzYqEoVmIK7J7g2QTzYgjdLF0RvlqXXV2uCQT7Ys= Received: (qmail 26887 invoked by alias); 5 May 2016 01:58:06 -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 26833 invoked by uid 89); 5 May 2016 01:58:04 -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, GAPPY_SUBJECT, RCVD_IN_DNSWL_LOW, SPF_PASS autolearn=no version=3.3.2 spammy=scans, sk:insert_, sk:transfo, our 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, 05 May 2016 01:57:54 +0000 Received: by mail-pf0-f174.google.com with SMTP id y69so31447431pfb.1 for ; Wed, 04 May 2016 18:57:54 -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=AeZL0JKAw7+AEReGynoIgksMS7zmHYWjKylvmCCEuYQ=; b=SciGZRIjto3zF4AxLY9nAn91ye5l42UbkhdGx9yFV9R2fCrLA4ibbj226wFPExOAsl dEBGkcjmgvzg9X+YNUQQIigDKJCT0V0pFNk5GI60/aLoXSIpbjdvgk5iTYqnpKYz8hcu vEs8ik68GZw5WkdZm57QMOj9MxdCHoxvXmyNBqE2UDKifQuh/kE+eD+8ekOEJ6BMZjx2 J1REt8SFSgk8L8O52njspIg5ThPsbNzu6TFnht+U8661RPoZq7NZ3Ve1JJLzn3Jw/ivh bhIGMmwTaOxECenm7VNLC45aW3wl3QI3s8Xw9OUU/8mGQMw1TOcOz3vOHPSZf/eSE2mi Sj+A== X-Gm-Message-State: AOPr4FX5aul4XbxAepbHw22DkyPrSZIFaUAN/wZi/LweY6mucHmpxwrtimuJ1JrUdEkaWd0G X-Received: by 10.98.104.133 with SMTP id d127mr16842336pfc.112.1462413471914; Wed, 04 May 2016 18:57:51 -0700 (PDT) Received: from [10.1.1.8] (58-6-183-210.dyn.iinet.net.au. [58.6.183.210]) by smtp.googlemail.com with ESMTPSA id w125sm8935722pfb.53.2016.05.04.18.57.49 (version=TLSv1/SSLv3 cipher=OTHER); Wed, 04 May 2016 18:57:51 -0700 (PDT) Subject: Re: [RFC][PATCH][PR63586] Convert x+x+x+x into 4*x To: Richard Biener References: <56CFC059.40108@linaro.org> <56D3C8D9.5020508@linaro.org> <571BF10E.2060809@linaro.org> Cc: Christophe Lyon , "gcc-patches@gcc.gnu.org" From: kugan Message-ID: <572AA887.7060408@linaro.org> Date: Thu, 5 May 2016 11:57:27 +1000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.5.1 MIME-Version: 1.0 In-Reply-To: X-IsSubscribed: yes Hi Richard, > > maybe instert_stmt_after will help here, I don't think you got the insertion > logic correct, thus insert_stmt_after (mul_stmt, def_stmt) which I think > misses GIMPLE_NOP handling. At least > > + if (SSA_NAME_VAR (op) != NULL > > huh? I suppose you could have tested SSA_NAME_IS_DEFAULT_DEF > but just the GIMPLE_NOP def-stmt test should be enough. > > + && gimple_code (def_stmt) == GIMPLE_NOP) > + { > + gsi = gsi_after_labels (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun))); > + stmt = gsi_stmt (gsi); > + gsi_insert_before (&gsi, mul_stmt, GSI_NEW_STMT); > > not sure if that is the best insertion point choice, it un-does all > code-sinking done > (and no further sinking is run after the last reassoc pass). We do know we > are handling all uses of op in our chain so inserting before the plus-expr > chain root should work here (thus 'stmt' in the caller context). I'd > use that here instead. > I think I'd use that unconditionally even if it works and not bother > finding something > more optimal. > I now tried using instert_stmt_after with special handling for GIMPLE_PHI as you described. > Apart from this this now looks ok to me. > > But the testcases need some work > > > --- a/gcc/testsuite/gcc.dg/tree-ssa/pr63586-2.c > +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr63586-2.c > @@ -0,0 +1,29 @@ > +/* { dg-do compile } */ > ... > + > +/* { dg-final { scan-tree-dump-times "\\\*" 4 "reassoc1" } } */ > > I would have expected 3. We now have an additional _15 = x_1(D) * 2 Also please check for \\\* 5 for example > to be more specific (and change the cases so you get different constants > for the different functions). > > That said, please make the scans more specific. I have now changes the test-cases to scan more specific multiplication scan as you wanted. Does this now look better? Thanks, Kugan diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr63586-2.c b/gcc/testsuite/gcc.dg/tree-ssa/pr63586-2.c index e69de29..0dcfe32 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/pr63586-2.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr63586-2.c @@ -0,0 +1,32 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -ffast-math -fdump-tree-reassoc1" } */ + +float f1_float (float x, float z) +{ + float y = x + z; + y = y + x; + y = y + x; + y = y + x; + y = y + x; + y = y + x; + y = y + x; + y = y + x; + return y; +} + +float f1_float2 (float x) +{ + float y = x + 3 * x + x; + return y; +} + +int f1_int (int x) +{ + int y = x + 4 * x + x; + return y; +} + +/* { dg-final { scan-tree-dump-times "\\\* 8\\\.0e\\\+0" 1 "reassoc1" } } */ +/* { dg-final { scan-tree-dump-times "\\\* 5\\\.0e\\\+0" 1 "reassoc1" } } */ +/* { dg-final { scan-tree-dump-times "\\\* 6" 1 "reassoc1" } } */ + diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr63586.c b/gcc/testsuite/gcc.dg/tree-ssa/pr63586.c index e69de29..470be8c 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/pr63586.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr63586.c @@ -0,0 +1,70 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-reassoc1" } */ + +unsigned f1 (unsigned x, unsigned z) +{ + unsigned y = x + z; + y = y + x; + y = y + x; + y = y + x; + y = y + x; + y = y + x; + y = y + x; + return y; +} + +/* { dg-final { scan-tree-dump-times "\\\* 7" 1 "reassoc1" } } */ + +unsigned f2 (unsigned x, unsigned z) +{ + unsigned y = x + z; + y = y + x; + y = y + x; + y = y + x; + y = y + z; + y = y + z; + y = y + z; + y = y + z; + return y; +} + +/* { dg-final { scan-tree-dump-times "\\\* 5" 1 "reassoc1" } } */ +/* { dg-final { scan-tree-dump-times "\\\* 4" 1 "reassoc1" } } */ + +unsigned f3 (unsigned x, unsigned z, unsigned k) +{ + unsigned y = x + z; + y = y + x; + y = y + z; + y = y + z; + y = y + k; + return y; +} + +/* { dg-final { scan-tree-dump-times "\\\* 2" 1 "reassoc1" } } */ +/* { dg-final { scan-tree-dump-times "\\\* 3" 1 "reassoc1" } } */ + +unsigned f4 (unsigned x, unsigned z, unsigned k) +{ + unsigned y = k + x; + y = y + z; + y = y + z; + y = y + z; + y = y + z; + y = y + z; + y = y + z; + y = y + z; + y = y + z; + return y; +} +/* { dg-final { scan-tree-dump-times "\\\* 8" 1 "reassoc1" } } */ + +unsigned f5 (unsigned x, unsigned y, unsigned z) +{ + return x + y + y + y + y + y \ + + y + z + z + z + z + z + z + z + z + z; +} + +/* { dg-final { scan-tree-dump-times "\\\* 6" 1 "reassoc1" } } */ +/* { dg-final { scan-tree-dump-times "\\\* 9" 1 "reassoc1" } } */ + diff --git a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-14.c b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-14.c index 62802d1..16ebc86 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-14.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-14.c @@ -19,6 +19,7 @@ unsigned int test2 (unsigned int x, unsigned int y, unsigned int z, return tmp1 + tmp2 + tmp3; } -/* There should be one multiplication left in test1 and three in test2. */ +/* There should be two multiplication left in test1 (inculding one generated + when converting addition to multiplication) and three in test2. */ -/* { dg-final { scan-tree-dump-times "\\\*" 4 "reassoc1" } } */ +/* { dg-final { scan-tree-dump-times "\\\*" 5 "reassoc1" } } */ diff --git a/gcc/tree-ssa-reassoc.c b/gcc/tree-ssa-reassoc.c index d23dabd..cd7e588 100644 --- a/gcc/tree-ssa-reassoc.c +++ b/gcc/tree-ssa-reassoc.c @@ -1756,6 +1756,81 @@ eliminate_redundant_comparison (enum tree_code opcode, return false; } +/* Transform repeated addition of same values into multiply with + constant. */ +static bool +transform_add_to_multiply (gimple *stmt, vec *ops) +{ + operand_entry *oe; + tree op = NULL_TREE; + int j; + int i, start = -1, end = 0, count = 0; + vec > indxs = vNULL; + bool changed = false; + + if (!INTEGRAL_TYPE_P (TREE_TYPE ((*ops)[0]->op)) + && !flag_unsafe_math_optimizations) + return false; + + /* Look for repeated operands. */ + FOR_EACH_VEC_ELT (*ops, i, oe) + { + if (start == -1) + { + count = 1; + op = oe->op; + start = i; + } + else if (operand_equal_p (oe->op, op, 0)) + { + count++; + end = i; + } + else + { + if (count > 1) + indxs.safe_push (std::make_pair (start, end)); + count = 1; + op = oe->op; + start = i; + } + } + + if (count > 1) + indxs.safe_push (std::make_pair (start, end)); + + for (j = indxs.length () - 1; j >= 0; --j) + { + /* Convert repeated operand addition to multiplication. */ + start = indxs[j].first; + end = indxs[j].second; + op = (*ops)[start]->op; + count = end - start + 1; + for (i = end; i >= start; --i) + ops->unordered_remove (i); + tree tmp = make_ssa_name (TREE_TYPE (op)); + tree cst = build_int_cst (integer_type_node, count); + gimple *def_stmt = SSA_NAME_DEF_STMT (op); + gassign *mul_stmt + = gimple_build_assign (tmp, MULT_EXPR, + op, fold_convert (TREE_TYPE (op), cst)); + if (gimple_code (def_stmt) == GIMPLE_NOP) + { + gimple_stmt_iterator gsi = gsi_for_stmt (stmt); + gimple_set_uid (mul_stmt, gimple_uid (stmt)); + gsi_insert_before (&gsi, mul_stmt, GSI_NEW_STMT); + } + else + insert_stmt_after (mul_stmt, def_stmt); + gimple_set_visited (mul_stmt, true); + add_to_ops_vec (ops, tmp); + changed = true; + } + + return changed; +} + + /* Perform various identities and other optimizations on the list of operand entries, stored in OPS. The tree code for the binary operation between all the operands is OPCODE. */ @@ -5118,6 +5193,10 @@ reassociate_bb (basic_block bb) optimize_range_tests (rhs_code, &ops); } + if (rhs_code == PLUS_EXPR + && transform_add_to_multiply (stmt, &ops)) + ops.qsort (sort_by_operand_rank); + if (rhs_code == MULT_EXPR && !is_vector) { attempt_builtin_copysign (&ops);