From patchwork Mon Feb 29 04:28:09 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kugan Vivekanandarajah X-Patchwork-Id: 63174 Delivered-To: patch@linaro.org Received: by 10.112.199.169 with SMTP id jl9csp1032654lbc; Sun, 28 Feb 2016 20:28:31 -0800 (PST) X-Received: by 10.98.8.80 with SMTP id c77mr19340199pfd.42.1456720111471; Sun, 28 Feb 2016 20:28:31 -0800 (PST) Return-Path: Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id rc17si16999208pab.120.2016.02.28.20.28.31 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sun, 28 Feb 2016 20:28:31 -0800 (PST) Received-SPF: pass (google.com: domain of gcc-patches-return-422354-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; spf=pass (google.com: domain of gcc-patches-return-422354-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-422354-patch=linaro.org@gcc.gnu.org; dkim=pass header.i=@gcc.gnu.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=aL2DHlRYGUtz8Hiqn rIACjmnaIZBIsfeOPKrr4kxcHSsBUl3sxgR92qAiGjwNF717iRh75O9RtbeI2LU1 chSn1qidm8Ob26RKPTXWnbxYy6L97TiU8ev5vS/Ehpuuze9Bgxjq7Z/SPe0PriRq /AspVy6ZZTb2Ts3FY9O+WVKEG4= 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=iij1Xt4cYE1YK7U9eDEFOrQ Dq/A=; b=X6sWCVdBgnXz1ZEO2paTXT8/yw7/21lH2GYAPscXUzfufUCFMZIKVAM e/qOKIh1LhvLgxZqCd+xiyBYWvQdXSaicDALFQ0wC0LuRH6dD+tJYh0cNRmSyVUy R3hoJ8JcneJhwnG8v6hz7FDIVJGnlFknqFMEUmZrvmfd9P2mRwwk= Received: (qmail 114850 invoked by alias); 29 Feb 2016 04:28:19 -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 114834 invoked by uid 89); 29 Feb 2016 04:28:18 -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=sk:unorder, test1, consumed, tmp3 X-HELO: mail-pa0-f54.google.com Received: from mail-pa0-f54.google.com (HELO mail-pa0-f54.google.com) (209.85.220.54) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-GCM-SHA256 encrypted) ESMTPS; Mon, 29 Feb 2016 04:28:17 +0000 Received: by mail-pa0-f54.google.com with SMTP id yy13so84778846pab.3 for ; Sun, 28 Feb 2016 20:28:17 -0800 (PST) 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=by6AHarEmDrQ/t6dkcqqAXLx+AVcFbeGkcBiOb7U514=; b=lZCgjjQiyeLq0vMk39sXZE6FjDt9HKdMDEAdqqBtzCAio1vXtuE42NHcs9Us4+K98p x4kmZrOY9CqipnYVkv918FlmC+icaE50xNabtE8P8930YvXc1kBWHdBE1JvIso+l7Yzt XssAjllif7QMiSg9aXNmrIrYpeMeJnfd2aznVA3Jb2fQXL7mBKnI7dJ/ZuERMkzUqchZ b4+weefQX2CciQYlGuWeIvOu9+H7ztucCByY8/C15bC7JAIV4RRBr3iN9cm41gtPpXfJ ikEB2B/++2MHKHlmEii+ChOZqHkNlHEtdj0yb+MLvwKNcFN21vGB9ELjfrl23ZapiqyI 1VfA== X-Gm-Message-State: AD7BkJL4wlI3AKefkxO976ymHUmPu2CAcHxCs37/C0af/tgnLzyr9TQR64xi3KOrBbfdNCV7 X-Received: by 10.66.55.73 with SMTP id q9mr19478668pap.50.1456720095822; Sun, 28 Feb 2016 20:28:15 -0800 (PST) Received: from [10.1.1.5] (58-6-183-210.dyn.iinet.net.au. [58.6.183.210]) by smtp.googlemail.com with ESMTPSA id k14sm34123776pfj.0.2016.02.28.20.28.12 (version=TLSv1/SSLv3 cipher=OTHER); Sun, 28 Feb 2016 20:28:14 -0800 (PST) Subject: Re: [RFC][PATCH][PR63586] Convert x+x+x+x into 4*x To: Richard Biener References: <56CFC059.40108@linaro.org> Cc: "gcc-patches@gcc.gnu.org" From: kugan Message-ID: <56D3C8D9.5020508@linaro.org> Date: Mon, 29 Feb 2016 15:28:09 +1100 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 > That looks better, but I think the unordered_remove will break operand sorting > and thus you probably don't handle x + x + x + x + y + y + y + y + y + > y + z + z + z + z > optimally. > > I'd say you simply want to avoid the recursion and collect a vector of > [start, end] pairs > before doing any modification to the ops vector. Hi Richard, Is the attached patch looks better? Thanks, Kugan diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr63586.c b/gcc/testsuite/gcc.dg/tree-ssa/pr63586.c index e69de29..a002bdd 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 17eb64f..0a43faf 100644 --- a/gcc/tree-ssa-reassoc.c +++ b/gcc/tree-ssa-reassoc.c @@ -1698,6 +1698,79 @@ eliminate_redundant_comparison (enum tree_code opcode, return false; } +/* Transoform repeated addition of same values into multiply with + constant. */ +static void +transform_add_to_multiply (gimple_stmt_iterator *gsi, gimple *stmt, vec *ops) +{ + operand_entry *oe; + tree op = NULL_TREE; + int j; + int i, start = -1, end = 0, count = 0; + vec start_inds = vNULL; + vec end_inds = vNULL; + vec op_list = vNULL; + + /* 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) + { + start_inds.safe_push (start); + end_inds.safe_push (end); + op_list.safe_push (op); + } + count = 1; + op = oe->op; + start = i; + } + } + + if (count > 1) + { + start_inds.safe_push (start); + end_inds.safe_push (end); + op_list.safe_push (op); + } + + for (j = start_inds.length () - 1; j >= 0; --j) + { + /* Convert repeated operand addition to multiplication. */ + start = start_inds[j]; + end = end_inds[j]; + op = op_list[j]; + count = end - start + 1; + for (i = end; i >= start; --i) + ops->unordered_remove (i); + 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)); + 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); + oe = operand_entry_pool.allocate (); + oe->op = tmp; + oe->rank = get_rank (op) * count; + oe->id = 0; + oe->count = 1; + ops->safe_push (oe); + } +} + + /* 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. */ @@ -4922,6 +4995,12 @@ reassociate_bb (basic_block bb) && flag_unsafe_math_optimizations) powi_result = attempt_builtin_powi (stmt, &ops); + if (rhs_code == PLUS_EXPR) + { + transform_add_to_multiply (&gsi, stmt, &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)