From patchwork Thu May 19 23:51:51 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Kugan Vivekanandarajah X-Patchwork-Id: 68206 Delivered-To: patch@linaro.org Received: by 10.140.92.199 with SMTP id b65csp3476308qge; Thu, 19 May 2016 16:52:17 -0700 (PDT) X-Received: by 10.66.122.175 with SMTP id lt15mr70218pab.51.1463701937433; Thu, 19 May 2016 16:52:17 -0700 (PDT) Return-Path: Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id i9si23325931paw.49.2016.05.19.16.52.17 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 19 May 2016 16:52:17 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-return-427843-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-427843-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-427843-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:date:message-id:subject :from:to:cc:content-type; q=dns; s=default; b=mW2XKE7Xb8fyiBByTB J3u+VV4iXz9Lswf+K6dD343PDZ2NichqegpWUqRpeEQmeDccpTERzkyp7vuvOx5p p3KcS1iwQvd8p6YtbB32H6dC80l3Z6zNajQdL7fyEEA+TyQoQdbF8xkIPIZPor00 8ONs65MFLgRGauJ7ncVgujj50= 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:date:message-id:subject :from:to:cc:content-type; s=default; bh=vUcpV6uPKYjeVJ3ik9co1BtJ Jpg=; b=bKXEPgM/wGQjZKm6sng5pbGK7tFy1yIA1dxNc7gYmQCszq8oKFm0Uq0I T0DeWGIZm9EJhAbZWhg/TOsvojMIJUHjJ1kL61qav58NPqntPGeuuPCRIjE27MrF kcMeo75tpSX8uuihUV+HUn5OZx/qvP7OjbkZ9FKXo7P1KVd0l4E= Received: (qmail 101128 invoked by alias); 19 May 2016 23:52:05 -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 101104 invoked by uid 89); 19 May 2016 23:52:04 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.6 required=5.0 tests=BAYES_00, RCVD_IN_DNSWL_LOW, SPF_PASS autolearn=ham version=3.3.2 spammy=2016-05-20, 20160520, GIMPLE_NOP, gimple_nop X-HELO: mail-qk0-f169.google.com Received: from mail-qk0-f169.google.com (HELO mail-qk0-f169.google.com) (209.85.220.169) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-GCM-SHA256 encrypted) ESMTPS; Thu, 19 May 2016 23:51:54 +0000 Received: by mail-qk0-f169.google.com with SMTP id y126so22558315qke.1 for ; Thu, 19 May 2016 16:51:53 -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:date :message-id:subject:from:to:cc; bh=AMkVhzxvUzZVNjms4VRHn5cnYVY/htUeSrFl+7WGa+g=; b=dH/EZlNJdcL4PluOedz9SrS3Zl4r0H/c28M+jGhDh0mFMJ3aDSQ3XfeI6jl5WRMyeo g9nsjmKJmwVpStnW4gnmt0IwbMpg2SoHWEUebVUOtDqd5JV+kGKY4/4nX14c5NnsTt4b L112qekdUel1tIj4bHZ7HeFctORHIaFRRcnFXsCBP/JzrYiT4zrOGDfYRGgyZdWxzkPv rbptiDFRKFFo/PqteAE4/X0jv6f5+FtGQ0ptrd5mKtPsvcX3JtBskzKqn342l2uAxhnS 6alpAv2S43WDqREX6MdqGhl8tCROEQSXuIEij8B2yPOpKMFWfMqYMH1WB/bb50ZY/8Qp UppA== X-Gm-Message-State: AOPr4FVQYW+b4iF4femqV74pI4FJjhVvfGM43XcxkHgrmeZIkLapKAcAN+kbo4SKyvDmf1q+pSKd5XjI/DI4bDfz MIME-Version: 1.0 X-Received: by 10.55.172.6 with SMTP id v6mr70636qke.98.1463701911863; Thu, 19 May 2016 16:51:51 -0700 (PDT) Received: by 10.200.42.71 with HTTP; Thu, 19 May 2016 16:51:51 -0700 (PDT) In-Reply-To: References: <573D7394.5050208@suse.cz> <573D78CE.6020900@linaro.org> Date: Fri, 20 May 2016 09:51:51 +1000 Message-ID: Subject: Re: [PATCH] Fix PR tree-optimization/71170 From: Kugan Vivekanandarajah To: Richard Biener Cc: =?UTF-8?Q?Martin_Li=C5=A1ka?= , GCC Patches X-IsSubscribed: yes Hi Richard, > I think it should have the same rank as op or op + 1 which is the current > behavior. Sth else doesn't work correctly here I think, like inserting the > multiplication not near the definition of op. > > Well, the whole "clever insertion" logic is simply flawed. What I meant to say was that the simple logic we have now wouldn’t work. "clever logic" is knowing where exactly where it is needed and inserting there. I think thats what you are suggesting below in a simple to implement way. > I'd say that ideally we would delay inserting the multiplication to > rewrite_expr_tree time. For example by adding a ops->stmt_to_insert > member. > Here is an implementation based on above. Bootstrap on x86-linux-gnu is OK. regression testing is ongoing. Thanks, Kugan gcc/ChangeLog: 2016-05-20 Kugan Vivekanandarajah * tree-ssa-reassoc.c (struct operand_entry): Add field stmt_to_insert. (add_to_ops_vec): Add stmt_to_insert. (add_repeat_to_ops_vec): Init stmt_to_insert. (transform_add_to_multiply): Remove mult_stmt insertion and add it to ops vector. (get_ops): Init stmt_to_insert. (maybe_optimize_range_tests): Likewise. (rewrite_expr_tree): Insert stmt_to_insert before use stmt. (rewrite_expr_tree_parallel): Likewise. diff --git a/gcc/tree-ssa-reassoc.c b/gcc/tree-ssa-reassoc.c index 3b5f36b..69441ce 100644 --- a/gcc/tree-ssa-reassoc.c +++ b/gcc/tree-ssa-reassoc.c @@ -195,6 +195,7 @@ struct operand_entry int id; tree op; unsigned int count; + gimple *stmt_to_insert; }; static object_allocator operand_entry_pool @@ -553,7 +554,7 @@ sort_by_operand_rank (const void *pa, const void *pb) /* Add an operand entry to *OPS for the tree operand OP. */ static void -add_to_ops_vec (vec *ops, tree op) +add_to_ops_vec (vec *ops, tree op, gimple *stmt_to_insert = NULL) { operand_entry *oe = operand_entry_pool.allocate (); @@ -561,6 +562,7 @@ add_to_ops_vec (vec *ops, tree op) oe->rank = get_rank (op); oe->id = next_operand_entry_id++; oe->count = 1; + oe->stmt_to_insert = stmt_to_insert; ops->safe_push (oe); } @@ -577,6 +579,7 @@ add_repeat_to_ops_vec (vec *ops, tree op, oe->rank = get_rank (op); oe->id = next_operand_entry_id++; oe->count = repeat; + oe->stmt_to_insert = NULL; ops->safe_push (oe); reassociate_stats.pows_encountered++; @@ -1810,21 +1813,12 @@ transform_add_to_multiply (gimple *stmt, vec *ops) 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_bb (stmt) != gimple_bb (def_stmt)) - { - 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_uid (mul_stmt, gimple_uid (stmt)); gimple_set_visited (mul_stmt, true); - add_to_ops_vec (ops, tmp); + add_to_ops_vec (ops, tmp, mul_stmt); changed = true; } @@ -3224,6 +3218,7 @@ get_ops (tree var, enum tree_code code, vec *ops, oe->rank = code; oe->id = 0; oe->count = 1; + oe->stmt_to_insert = NULL; ops->safe_push (oe); } return true; @@ -3464,6 +3459,7 @@ maybe_optimize_range_tests (gimple *stmt) oe->rank = code; oe->id = 0; oe->count = 1; + oe->stmt_to_insert = NULL; ops.safe_push (oe); bb_ent.last_idx++; } @@ -3501,6 +3497,7 @@ maybe_optimize_range_tests (gimple *stmt) is. */ oe->id = bb->index; oe->count = 1; + oe->stmt_to_insert = NULL; ops.safe_push (oe); bb_ent.op = NULL; bb_ent.last_idx++; @@ -3798,6 +3795,19 @@ rewrite_expr_tree (gimple *stmt, unsigned int opindex, oe1 = ops[opindex]; oe2 = ops[opindex + 1]; + /* If the stmt that defines operand has to be inserted, insert it + before the use. */ + if (oe1->stmt_to_insert) + { + gimple_stmt_iterator gsi = gsi_for_stmt (stmt); + gsi_insert_before (&gsi, oe1->stmt_to_insert, GSI_NEW_STMT); + } + if (oe2->stmt_to_insert) + { + gimple_stmt_iterator gsi = gsi_for_stmt (stmt); + gsi_insert_before (&gsi, oe2->stmt_to_insert, GSI_NEW_STMT); + } + if (rhs1 != oe1->op || rhs2 != oe2->op) { gimple_stmt_iterator gsi = gsi_for_stmt (stmt); @@ -3855,6 +3865,14 @@ rewrite_expr_tree (gimple *stmt, unsigned int opindex, /* Rewrite the next operator. */ oe = ops[opindex]; + /* If the stmt that defines operand has to be inserted, insert it + before the use. */ + if (oe->stmt_to_insert) + { + gimple_stmt_iterator gsi = gsi_for_stmt (stmt); + gsi_insert_before (&gsi, oe->stmt_to_insert, GSI_NEW_STMT); + } + /* Recurse on the LHS of the binary operator, which is guaranteed to be the non-leaf side. */ tree new_rhs1 @@ -3999,6 +4017,7 @@ rewrite_expr_tree_parallel (gassign *stmt, int width, int stmt_index = 0; int ready_stmts_end = 0; int i = 0; + gimple *stmt1 = NULL, *stmt2 = NULL; tree last_rhs1 = gimple_assign_rhs1 (stmt); /* We start expression rewriting from the top statements. @@ -4027,7 +4046,11 @@ rewrite_expr_tree_parallel (gassign *stmt, int width, if (ready_stmts_end > stmt_index) op2 = gimple_assign_lhs (stmts[stmt_index++]); else if (op_index >= 0) - op2 = ops[op_index--]->op; + { + operand_entry *oe = ops[op_index--]; + stmt2 = oe->stmt_to_insert; + op2 = oe->op; + } else { gcc_assert (stmt_index < i); @@ -4041,8 +4064,12 @@ rewrite_expr_tree_parallel (gassign *stmt, int width, { if (op_index > 1) swap_ops_for_binary_stmt (ops, op_index - 2, NULL); - op2 = ops[op_index--]->op; - op1 = ops[op_index--]->op; + operand_entry *oe2 = ops[op_index--]; + operand_entry *oe1 = ops[op_index--]; + op2 = oe2->op; + stmt2 = oe2->stmt_to_insert; + op1 = oe1->op; + stmt1 = oe1->stmt_to_insert; } /* If we emit the last statement then we should put @@ -4057,6 +4084,19 @@ rewrite_expr_tree_parallel (gassign *stmt, int width, print_gimple_stmt (dump_file, stmts[i], 0, 0); } + /* If the stmt that defines operand has to be inserted, insert it + before the use. */ + if (stmt1) + { + gimple_stmt_iterator gsi = gsi_for_stmt (stmts[i]); + gsi_insert_before (&gsi, stmt1, GSI_NEW_STMT); + } + if (stmt2) + { + gimple_stmt_iterator gsi = gsi_for_stmt (stmts[i]); + gsi_insert_before (&gsi, stmt2, GSI_NEW_STMT); + } + /* We keep original statement only for the last one. All others are recreated. */ if (i == stmt_num - 1)