From patchwork Sun Sep 18 20:21:46 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kugan Vivekanandarajah X-Patchwork-Id: 76493 Delivered-To: patch@linaro.org Received: by 10.140.106.72 with SMTP id d66csp646771qgf; Sun, 18 Sep 2016 13:22:18 -0700 (PDT) X-Received: by 10.98.20.137 with SMTP id 131mr21800510pfu.11.1474230138775; Sun, 18 Sep 2016 13:22:18 -0700 (PDT) Return-Path: Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id aj7si18748473pad.125.2016.09.18.13.22.18 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sun, 18 Sep 2016 13:22:18 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-return-436174-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-436174-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-436174-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=eTAw8llm+z6g+E9RH AtgKXORowy92cUz3l3J4Gxf+4zB+g34B/lT0JxhbIqsElXGZ7SdyXIsviYA9rBLp tgneyX0YeMHKObf1d79odbtNGJfTZCkgGqDB7AoXfT0U5k/aIuDUnt05kJ84DFML J8GT46NvW/ayT0C3UOjvO/mBDc= 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=uUlul7fiENHb3g64lBRFA2d 73YQ=; b=p6ssKrnWTKLEKyt2KKY9RjLHd0AUqVp7r928DRy0uF3Me0DOWz/R2mW 6T6f8ZOLoHkfcdTSa69P98q7FwHBWf5HAp3b6zyIx6Ab+Hpc2kOCuCilhVe1lP7Z gnAHgsj0GcbioSm9JiSZ2iUZ8L1Stfp3D5iCFyvAQl54sj86t0nk= Received: (qmail 94480 invoked by alias); 18 Sep 2016 20:22: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 94434 invoked by uid 89); 18 Sep 2016 20:22:04 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.1 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_LOW, RCVD_IN_SORBS_SPAM, SPF_PASS autolearn=ham version=3.3.2 spammy=ongoing, STMT, Though, visited X-HELO: mail-pa0-f44.google.com Received: from mail-pa0-f44.google.com (HELO mail-pa0-f44.google.com) (209.85.220.44) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Sun, 18 Sep 2016 20:21:53 +0000 Received: by mail-pa0-f44.google.com with SMTP id wk8so41497142pab.1 for ; Sun, 18 Sep 2016 13:21: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:subject:to:references:cc:from:message-id:date :user-agent:mime-version:in-reply-to; bh=rSGqSiHiiwTF7fV1ZNpY6yBPSA6o/WLsYXWx5XiRrWg=; b=R+dj8BQdNqHYdXd4SC/c2NTaRBAO9jGoQ9pTlRk0C8IBhGgYXdX+RvoCETEGz94vY2 6+KaBc3b8y2UKZfNEqZKzshskhTaafvSiUpODF1Vv926Wd8MUIEWAFUYwGIda7lUTdnz pLy6CKw/YEpMVKVoPhknKwEJkWcHhxIs5BPjr/25+WU9vjR2haht8XvArEHLOXXBq/5j JZDP/PowG84ElsKyDokIh+LGZtwqeWuh1LPgSBHNqv4qUMAC3FwJkWAWRo6L+GkdKr1Y mt3/Nw/M0Xpz1ngWXno2iZFwfh/0uWGWtoqE2Q65h2a32bNW0pACM5gAQkPRkAfUkCz7 eXLA== X-Gm-Message-State: AE9vXwNicmLwh57dXuNlz4qFAG1FP9lW0E4FPCTrJbhm4in+ehu5kT8ewNMaku/vWyTYa7cN X-Received: by 10.67.23.41 with SMTP id hx9mr14525247pad.147.1474230111907; Sun, 18 Sep 2016 13:21:51 -0700 (PDT) Received: from [10.1.1.7] (58-6-183-210.dyn.iinet.net.au. [58.6.183.210]) by smtp.gmail.com with ESMTPSA id u64sm66067809pfi.0.2016.09.18.13.21.49 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sun, 18 Sep 2016 13:21:50 -0700 (PDT) Subject: Re: [PR72835] Incorrect arithmetic optimization involving bitfield arguments To: Richard Biener References: <0a1eaaf8-3ede-cd56-ffb5-40b25f94e46e@linaro.org> <98613cff-7c48-1a56-0014-6d87c35a8f26@linaro.org> <20160809214617.GB14857@tucnak.redhat.com> <7210cceb-be3b-44b1-13b7-4152e89d2a4f@linaro.org> <20160809215527.GC14857@tucnak.redhat.com> <0c53b0f3-4af6-387c-9350-95b1ae85850d@linaro.org> <20160810085703.GH14857@tucnak.redhat.com> Cc: Jakub Jelinek , "gcc-patches@gcc.gnu.org" From: kugan Message-ID: <0f3b4359-f5ff-d14c-1b15-2ae647e6fd3a@linaro.org> Date: Mon, 19 Sep 2016 06:21:46 +1000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.2.0 MIME-Version: 1.0 In-Reply-To: X-IsSubscribed: yes Hi Richard, On 14/09/16 21:31, Richard Biener wrote: > On Fri, Sep 2, 2016 at 10:09 AM, Kugan Vivekanandarajah > wrote: >> Hi Richard, >> >> On 25 August 2016 at 22:24, Richard Biener wrote: >>> On Thu, Aug 11, 2016 at 1:09 AM, kugan >>> wrote: >>>> Hi, >>>> >>>> >>>> On 10/08/16 20:28, Richard Biener wrote: >>>>> >>>>> On Wed, Aug 10, 2016 at 10:57 AM, Jakub Jelinek wrote: >>>>>> >>>>>> On Wed, Aug 10, 2016 at 08:51:32AM +1000, kugan wrote: >>>>>>> >>>>>>> I see it now. The problem is we are just looking at (-1) being in the >>>>>>> ops >>>>>>> list for passing changed to rewrite_expr_tree in the case of >>>>>>> multiplication >>>>>>> by negate. If we have combined (-1), as in the testcase, we will not >>>>>>> have >>>>>>> the (-1) and will pass changed=false to rewrite_expr_tree. >>>>>>> >>>>>>> We should set changed based on what happens in try_special_add_to_ops. >>>>>>> Attached patch does this. Bootstrap and regression testing are ongoing. >>>>>>> Is >>>>>>> this OK for trunk if there is no regression. >>>>>> >>>>>> >>>>>> I think the bug is elsewhere. In particular in >>>>>> undistribute_ops_list/zero_one_operation/decrement_power. >>>>>> All those look problematic in this regard, they change RHS of statements >>>>>> to something that holds a different value, while keeping the LHS. >>>>>> So, generally you should instead just add a new stmt next to the old one, >>>>>> and adjust data structures (replace the old SSA_NAME in some ->op with >>>>>> the new one). decrement_power might be a problem here, dunno if all the >>>>>> builtins are const in all cases that DSE would kill the old one, >>>>>> Richard, any preferences for that? reset flow sensitive info + reset >>>>>> debug >>>>>> stmt uses, or something different? Though, replacing the LHS with a new >>>>>> anonymous SSA_NAME might be needed too, in case it is before SSA_NAME of >>>>>> a >>>>>> user var that doesn't yet have any debug stmts. >>>>> >>>>> >>>>> I'd say replacing the LHS is the way to go, with calling the appropriate >>>>> helper >>>>> on the old stmt to generate a debug stmt for it / its uses (would need >>>>> to look it >>>>> up here). >>>>> >>>> >>>> Here is an attempt to fix it. The problem arises when in >>>> undistribute_ops_list, we linearize_expr_tree such that NEGATE_EXPR is added >>>> (-1) MULT_EXPR (OP). Real problem starts when we handle this in >>>> zero_one_operation. Unlike what was done earlier, we now change the stmt >>>> (with propagate_op_to_signle use or by directly) such that the value >>>> computed by stmt is no longer what it used to be. Because of this, what is >>>> computed in undistribute_ops_list and rewrite_expr_tree are also changed. >>>> >>>> undistribute_ops_list already expects this but rewrite_expr_tree will not if >>>> we dont pass the changed as an argument. >>>> >>>> The way I am fixing this now is, in linearize_expr_tree, I set ops_changed >>>> to true if we change NEGATE_EXPR to (-1) MULT_EXPR (OP). Then when we call >>>> zero_one_operation with ops_changed = true, I replace all the LHS in >>>> zero_one_operation with the new SSA and replace all the uses. I also call >>>> the rewrite_expr_tree with changed = false in this case. >>>> >>>> Does this make sense? Bootstrapped and regression tested for >>>> x86_64-linux-gnu without any new regressions. >>> >>> I don't think this solves the issue. zero_one_operation associates the >>> chain starting at the first *def and it will change the intermediate values >>> of _all_ of the stmts visited until the operation to be removed is found. >>> Note that this is independent of whether try_special_add_to_ops did anything. >>> >>> Even for the regular undistribution cases we get this wrong. >>> >>> So we need to back-track in zero_one_operation, replacing each LHS >>> and in the end the op in the opvector of the main chain. That's basically >>> the same as if we'd do a regular re-assoc operation on the sub-chains. >>> Take their subops, simulate zero_one_operation by >>> appending the cancelling operation and optimizing the oplist, and then >>> materializing the associated ops via rewrite_expr_tree. >>> >> Here is a draft patch which records the stmt chain when in >> zero_one_operation and then fixes it when OP is removed. when we >> update *def, that will update the ops vector. Does this looks sane? > > Yes. A few comments below > > + /* PR72835 - Record the stmt chain that has to be updated such that > + we dont use the same LHS when the values computed are different. */ > + auto_vec stmts_to_fix; > > use auto_vec here so we get stack allocation only most > of the times Done. > if (stmt_is_power_of_op (stmt, op)) > { > + make_new_ssa_for_all_defs (def, op, stmts_to_fix); > if (decrement_power (stmt) == 1) > propagate_op_to_single_use (op, stmt, def); > > for the cases you end up with propagate_op_to_single_use its argument > stmt is handled superfluosly in the new SSA making, I suggest to pop it > from the stmts_to_fix vector in that case. I suggest to break; instead > of return in all cases and do the make_new_ssa_for_all_defs call at > the function end instead. > Done. > @@ -1253,14 +1305,18 @@ zero_one_operation (tree *def, enum tree_code > opcode, tree op) > if (gimple_assign_rhs1 (stmt2) == op) > { > tree cst = build_minus_one_cst (TREE_TYPE (op)); > + stmts_to_fix.safe_push (stmt2); > + make_new_ssa_for_all_defs (def, op, stmts_to_fix); > propagate_op_to_single_use (cst, stmt2, def); > return; > > this safe_push should be unnecessary for the above reason (others are > conditionally unnecessary). > Done. Bootstrapped and regression tested on X86_64-linux-gnu with no new regression. Is this OK? Thanks, Kugan > I thought about simplifying the whole thing by instead of clearing an > op from the chain pre-pend > one that does the job by means of visiting the chain from reassoc > itself but that doesn't work out > for RDIV_EXPR nor does it play well with undistribute handling > mutliple opportunities on the same > chain. > > Thanks, > Richard. > > >> >> Bootstrapped and regression tested on x86_64-linux-gnu with no new regressions. >> >> Thanks, >> Kugan diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr72835.c b/gcc/testsuite/gcc.dg/tree-ssa/pr72835.c index e69de29..468e0f0 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/pr72835.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr72835.c @@ -0,0 +1,37 @@ +/* PR tree-optimization/72835. */ +/* { dg-do run } */ +/* { dg-options "-O2" } */ +/* { dg-require-effective-target int32plus } */ + +struct struct_1 { + unsigned int m1 : 6 ; + unsigned int m2 : 24 ; + unsigned int m3 : 6 ; +}; + +unsigned short var_32 = 0x2d10; + +struct struct_1 s1; + +void init () +{ + s1.m1 = 4; + s1.m2 = 0x7ca4b8; + s1.m3 = 24; +} + +void foo () +{ + unsigned int c + = ((unsigned int) s1.m2) * (-((unsigned int) s1.m3)) + + (var_32) * (-((unsigned int) (s1.m1))); + if (c != 4098873984) + __builtin_abort (); +} + +int main () +{ + init (); + foo (); + return 0; +} diff --git a/gcc/tree-ssa-reassoc.c b/gcc/tree-ssa-reassoc.c index 7fd7550..24e9dd6 100644 --- a/gcc/tree-ssa-reassoc.c +++ b/gcc/tree-ssa-reassoc.c @@ -1148,6 +1148,52 @@ decrement_power (gimple *stmt) } } +/* Replace SSA defined by STMT and replace all its uses with new + SSA. Also return the new SSA. */ + +static tree +make_new_ssa_for_def (gimple *stmt) +{ + gimple *use_stmt; + use_operand_p use; + imm_use_iterator iter; + tree new_lhs; + tree lhs = gimple_assign_lhs (stmt); + + new_lhs = make_ssa_name (TREE_TYPE (lhs)); + gimple_set_lhs (stmt, new_lhs); + + /* Also need to update GIMPLE_DEBUGs. */ + FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs) + { + FOR_EACH_IMM_USE_ON_STMT (use, iter) + SET_USE (use, new_lhs); + update_stmt (use_stmt); + } + return new_lhs; +} + +/* Replace all SSAs defined in STMTS_TO_FIX and replace its + uses with new SSAs. Also do this for the stmt that defines DEF + if *DEF is not OP. */ + +static void +make_new_ssa_for_all_defs (tree *def, tree op, + auto_vec &stmts_to_fix) +{ + unsigned i; + gimple *stmt; + + if (*def != op + && TREE_CODE (*def) == SSA_NAME + && (stmt = SSA_NAME_DEF_STMT (*def)) + && gimple_code (stmt) != GIMPLE_NOP) + *def = make_new_ssa_for_def (stmt); + + FOR_EACH_VEC_ELT (stmts_to_fix, i, stmt) + make_new_ssa_for_def (stmt); +} + /* Find the single immediate use of STMT's LHS, and replace it with OP. Remove STMT. If STMT's LHS is the same as *DEF, replace *DEF with OP as well. */ @@ -1186,6 +1232,9 @@ static void zero_one_operation (tree *def, enum tree_code opcode, tree op) { gimple *stmt = SSA_NAME_DEF_STMT (*def); + /* PR72835 - Record the stmt chain that has to be updated such that + we dont use the same LHS when the values computed are different. */ + auto_vec stmts_to_fix; do { @@ -1196,23 +1245,29 @@ zero_one_operation (tree *def, enum tree_code opcode, tree op) if (stmt_is_power_of_op (stmt, op)) { if (decrement_power (stmt) == 1) - propagate_op_to_single_use (op, stmt, def); - return; + { + if (stmts_to_fix.length () > 0) + stmts_to_fix.pop (); + propagate_op_to_single_use (op, stmt, def); + } + break; } else if (gimple_assign_rhs_code (stmt) == NEGATE_EXPR) { if (gimple_assign_rhs1 (stmt) == op) { tree cst = build_minus_one_cst (TREE_TYPE (op)); + if (stmts_to_fix.length () > 0) + stmts_to_fix.pop (); propagate_op_to_single_use (cst, stmt, def); - return; + break; } else if (integer_minus_onep (op) || real_minus_onep (op)) { gimple_assign_set_rhs_code (stmt, TREE_CODE (gimple_assign_rhs1 (stmt))); - return; + break; } } } @@ -1228,8 +1283,10 @@ zero_one_operation (tree *def, enum tree_code opcode, tree op) { if (name == op) name = gimple_assign_rhs2 (stmt); + if (stmts_to_fix.length () > 0) + stmts_to_fix.pop (); propagate_op_to_single_use (name, stmt, def); - return; + break; } /* We might have a multiply of two __builtin_pow* calls, and @@ -1245,7 +1302,9 @@ zero_one_operation (tree *def, enum tree_code opcode, tree op) { if (decrement_power (stmt2) == 1) propagate_op_to_single_use (op, stmt2, def); - return; + else + stmts_to_fix.safe_push (stmt2); + break; } else if (is_gimple_assign (stmt2) && gimple_assign_rhs_code (stmt2) == NEGATE_EXPR) @@ -1254,14 +1313,15 @@ zero_one_operation (tree *def, enum tree_code opcode, tree op) { tree cst = build_minus_one_cst (TREE_TYPE (op)); propagate_op_to_single_use (cst, stmt2, def); - return; + break; } else if (integer_minus_onep (op) || real_minus_onep (op)) { + stmts_to_fix.safe_push (stmt2); gimple_assign_set_rhs_code (stmt2, TREE_CODE (gimple_assign_rhs1 (stmt2))); - return; + break; } } } @@ -1270,8 +1330,12 @@ zero_one_operation (tree *def, enum tree_code opcode, tree op) gcc_assert (name != op && TREE_CODE (name) == SSA_NAME); stmt = SSA_NAME_DEF_STMT (name); + stmts_to_fix.safe_push (stmt); } while (1); + + if (stmts_to_fix.length () > 0) + make_new_ssa_for_all_defs (def, op, stmts_to_fix); } /* Returns true if statement S1 dominates statement S2. Like