From patchwork Sat Apr 23 22:02:54 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kugan Vivekanandarajah X-Patchwork-Id: 66531 Delivered-To: patch@linaro.org Received: by 10.140.93.198 with SMTP id d64csp338210qge; Sat, 23 Apr 2016 15:03:31 -0700 (PDT) X-Received: by 10.66.194.196 with SMTP id hy4mr38153854pac.43.1461449011707; Sat, 23 Apr 2016 15:03:31 -0700 (PDT) Return-Path: Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id te8si16676013pac.27.2016.04.23.15.03.31 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sat, 23 Apr 2016 15:03:31 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-return-425473-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-425473-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-425473-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:from :subject:to:references:cc:message-id:date:mime-version :in-reply-to:content-type; q=dns; s=default; b=hyUsHhjiGXX35bUVa T6SMwazYKjPiKh/tnLVc0UxUrtG4s0eZ8pNyNi/ASrPz4QH0ciJWt75pPD7oLklO mn0X9VZYzvSr0AZtoHb7nOeMvhYuvtpjSAiPLCezIhDJVGA1uLkT5r3f+ApNKvFb +8Madd9FXiklE1VvRF+4S0we+4= 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 :subject:to:references:cc:message-id:date:mime-version :in-reply-to:content-type; s=default; bh=l7DV2/MS/81uayVTOrSYN64 QXDY=; b=uvIH4aRZsg3B15d1pdm9FR7uRZyAgycscFsmIDJ81cAQFWhobzD6kIM iP8wAGFgOvBjy9TGU4HAaKp75pcXmEGiq5JXQGHb6eR/m1MQ8eEG2YfdDMk8pH9J nZMb23Q5xGXCi+gzdiTjDTjI+Ok8Vm1ZwZ2wndAs5dGxO6JNjdiY= Received: (qmail 44884 invoked by alias); 23 Apr 2016 22:03:18 -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 44875 invoked by uid 89); 23 Apr 2016 22:03:17 -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=20160424, 2016-04-24, sk:unorder, rank 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; Sat, 23 Apr 2016 22:03:07 +0000 Received: by mail-pf0-f174.google.com with SMTP id 206so3951997pfu.0 for ; Sat, 23 Apr 2016 15:03:07 -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:subject:to:references:cc:message-id:date :user-agent:mime-version:in-reply-to; bh=XaczeTaWL6/irkMHluXQdtcGnpjLa9rB9SX5VJ81Iig=; b=OvU+f1C10VE9GX33XAZX1DGI9QQuyoC924OczdpztS/fTPgVmE4x43GiVUutix55L6 Amg8NrY9SveMG2rPIyh4tY+DASSEu/+GgTW+MwizkTy5zbkkmZN3AJyTWdBAq1t0csvk lMYDQ1R8c1aGDoIjK5FRovjTgHv33uifdUhmN6XtdCjur4iL3cBuvfWnif10X8Hc/cuk wpC9YnjYos4lxX+kM2jcjKjZ6AG/bqtV4xEP5HrWAEMknE3UheSnd1BRbBmfYGNfjMrM j853YT6n9UMuNNPbsiKSQYFym0FesrvhFdYhFxcUtcm0vvGINaqeBqGr8npXpVV30Q7N +7ag== X-Gm-Message-State: AOPr4FU/4K+uJ4SgpdkBo4DggNCQihifxnIFE1U4A7yu3jyvSBqsh2avL4CAaSJ2tog4UNvG X-Received: by 10.98.1.69 with SMTP id 66mr39045376pfb.10.1461448985638; Sat, 23 Apr 2016 15:03:05 -0700 (PDT) Received: from [10.1.1.7] (58-6-183-210.dyn.iinet.net.au. [58.6.183.210]) by smtp.googlemail.com with ESMTPSA id c2sm6247106pfc.40.2016.04.23.15.03.02 (version=TLSv1/SSLv3 cipher=OTHER); Sat, 23 Apr 2016 15:03:04 -0700 (PDT) From: kugan Subject: Re: [RFC][PATCH][PR63586] Convert x+x+x+x into 4*x To: Richard Biener , Christophe Lyon References: <56CFC059.40108@linaro.org> <56D3C8D9.5020508@linaro.org> Cc: "gcc-patches@gcc.gnu.org" Message-ID: <571BF10E.2060809@linaro.org> Date: Sun, 24 Apr 2016 08:02:54 +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, As you have said in the other email, I tried implementing with the add_reapeats_to_ops_vec but the whole repeat vector is designed for MULT_EXPR chain. I tried changing it but it turned out to be not straightforward without lots of re-write. Therefore I tried to implement based on your review here. Please tell me what you think. >> +/* Transoform repeated addition of same values into multiply with >> + constant. */ >> >> Transform Done. >> >> +static void >> +transform_add_to_multiply (gimple_stmt_iterator *gsi, gimple *stmt, >> vec *ops) >> >> split the long line Done. >> >> op_list looks redundant - ops[start]->op gives you the desired value >> already and if you >> use a vec> you can have a more C++ish start,end pair. >> >> + tree tmp = make_temp_ssa_name (TREE_TYPE (op), NULL, "reassocmul"); >> + gassign *mul_stmt = gimple_build_assign (tmp, MULT_EXPR, >> + op, build_int_cst >> (TREE_TYPE(op), count)); >> >> this won't work for floating point or complex numbers - you need to use sth like >> fold_convert (TREE_TYPE (op), build_int_cst (integer_type_node, count)); Done. >> >> For FP types you need to guard the transform with flag_unsafe_math_optimizations Done. >> >> + gimple_set_location (mul_stmt, gimple_location (stmt)); >> + gimple_set_uid (mul_stmt, gimple_uid (stmt)); >> + gsi_insert_before (gsi, mul_stmt, GSI_SAME_STMT); >> >> I think you do not want to set the stmt uid assert in reassoc_stmt_dominates_p (gcc_assert (gimple_uid (s1) && gimple_uid (s2))) is failing. So I tried to add the uid of the adjacent stmt and it seems to work. >> and you want to insert the >> stmt right >> after the def of op (or at the original first add - though you can't >> get your hands at Done. >> that easily). You also don't want to set the location to the last stmt of the >> whole add sequence - simply leave it unset. >> >> + oe = operand_entry_pool.allocate (); >> + oe->op = tmp; >> + oe->rank = get_rank (op) * count; >> >> ? Why that? oe->rank should be get_rank (tmp). >> >> + oe->id = 0; >> >> other places use next_operand_entry_id++. I think you want to simply >> use add_to_ops_vec (oe, tmp); here for all of the above. Done. >> >> Please return whether you did any optimization and do the >> qsort of the operand vector only if you did sth. Done. >> Testcase with FP math missing. Likewise with complex or vector math. > > Btw, does it handle associating > > x + 3 * x + x > > to > > 5 * x > > ? Added this to the testcase and verified it is working. Regression tested and bootstrapped on x86-64-linux-gnu with no new regressions. Is this OK for trunk? Thanks, Kugan gcc/testsuite/ChangeLog: 2016-04-24 Kugan Vivekanandarajah PR middle-end/63586 * gcc.dg/tree-ssa/pr63586-2.c: New test. * gcc.dg/tree-ssa/pr63586.c: New test. * gcc.dg/tree-ssa/reassoc-14.c: Adjust multiplication count. gcc/ChangeLog: 2016-04-24 Kugan Vivekanandarajah PR middle-end/63586 * tree-ssa-reassoc.c (transform_add_to_multiply): New. (reassociate_bb): Call transform_add_to_multiply. diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr63586-2.c b/gcc/testsuite/gcc.dg/tree-ssa/pr63586-2.c index e69de29..2774fbd 100644 --- 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-options "-O2 -ffast-math -fdump-tree-reassoc1" } */ + +float f1_float (float x) +{ + float y = x + 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 + 3 * x + x; + return y; +} + +/* { dg-final { scan-tree-dump-times "\\\*" 4 "reassoc1" } } */ + diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr63586.c b/gcc/testsuite/gcc.dg/tree-ssa/pr63586.c index e69de29..a0f705b 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/pr63586.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr63586.c @@ -0,0 +1,59 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-reassoc1" } */ + +unsigned f1 (unsigned x) +{ + unsigned y = x + x; + y = y + x; + y = y + x; + y = y + x; + y = y + x; + y = y + x; + y = y + x; + return y; +} + +unsigned f2 (unsigned x, unsigned z) +{ + unsigned y = x + x; + y = y + x; + y = y + x; + y = y + z; + y = y + z; + y = y + z; + y = y + z; + return y; +} + +unsigned f3 (unsigned x, unsigned z, unsigned k) +{ + unsigned y = x + x; + y = y + x; + y = y + x; + y = y + z; + y = y + z; + y = y + z; + y = y + k; + return y; +} + +unsigned f4 (unsigned x, unsigned z, unsigned k) +{ + unsigned y = k + x; + y = y + x; + y = y + x; + y = y + z; + y = y + z; + y = y + z; + y = y + x; + return y; +} + +unsigned f5 (unsigned x, unsigned y, unsigned z) +{ + return x + x + x + x + y + y + y + y + y \ + + y + z + z + z + z; +} + +/* { dg-final { scan-tree-dump-times "\\\*" 10 "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..6e57d44 100644 --- a/gcc/tree-ssa-reassoc.c +++ b/gcc/tree-ssa-reassoc.c @@ -1756,6 +1756,95 @@ 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 (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; + gimple *stmt; + + 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)); + gimple_stmt_iterator gsi; + if (SSA_NAME_VAR (op) != NULL + && 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); + } + else if (gimple_code (def_stmt) == GIMPLE_PHI) + { + gsi = gsi_after_labels (gimple_bb (def_stmt)); + stmt = gsi_stmt (gsi); + gsi_insert_before (&gsi, mul_stmt, GSI_NEW_STMT); + } + else + { + gsi = gsi_for_stmt (def_stmt); + stmt = gsi_stmt (gsi); + gsi_insert_after (&gsi, mul_stmt, GSI_NEW_STMT); + } + gimple_set_uid (mul_stmt, gimple_uid (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. */ @@ -5127,6 +5216,10 @@ reassociate_bb (basic_block bb) powi_result = attempt_builtin_powi (stmt, &ops); } + if (rhs_code == PLUS_EXPR + && transform_add_to_multiply (&ops)) + ops.qsort (sort_by_operand_rank); + /* If the operand vector is now empty, all operands were consumed by the __builtin_powi optimization. */ if (ops.length () == 0)