From patchwork Wed Aug 10 23:09:08 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kugan Vivekanandarajah X-Patchwork-Id: 73702 Delivered-To: patch@linaro.org Received: by 10.140.29.52 with SMTP id a49csp631114qga; Wed, 10 Aug 2016 16:09:43 -0700 (PDT) X-Received: by 10.98.200.29 with SMTP id z29mr11343837pff.143.1470870583333; Wed, 10 Aug 2016 16:09:43 -0700 (PDT) Return-Path: Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id wn3si50685788pab.33.2016.08.10.16.09.43 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 10 Aug 2016 16:09:43 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-return-433747-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-433747-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-433747-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=T/AYkAPhhVJlRAzUe 5Wq1WRbOxi+D9K5iTM1OpvALdDQXSS2AxAKwlyu4xgfm6i6NNDoMR2jVvoum0BmW wksSJxN1SM7uwwKlTWAVkBzEcZ8jyP/yK+C0SAx2hJudwrxVpkhnD/DvkTEyr5Ia I/LyR0KyS+uRiOOm8VbjKyKzdU= 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=Eg/UH5fwKIS9iEQEjLAq55c hCDE=; b=KrzjuRL3093uN3qn7JbrETVWQ2M51nWbTncoyAlRrOzuBJ3c3J52wPI nc0QBtn3rcSLDVxKDxwLhsvEehfDLwoUNFrfCVDRtCHvqkMoXHnB0QewJVfBlpr5 CYK+z5vUOuGhpdkIXJqZigqGMjNJKc78b2/zKfTJ5ghkilI2g5uQ= Received: (qmail 108428 invoked by alias); 10 Aug 2016 23:09:29 -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 108417 invoked by uid 89); 10 Aug 2016 23:09:29 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.4 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_LOW, SPF_PASS autolearn=ham version=3.3.2 spammy=starts, MULT_EXPR, mult_expr, Bootstrapped X-HELO: mail-pf0-f177.google.com Received: from mail-pf0-f177.google.com (HELO mail-pf0-f177.google.com) (209.85.192.177) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-GCM-SHA256 encrypted) ESMTPS; Wed, 10 Aug 2016 23:09:18 +0000 Received: by mail-pf0-f177.google.com with SMTP id p64so20212893pfb.1 for ; Wed, 10 Aug 2016 16:09:18 -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=YUUKMCqQYinAqGpAvTshcf4Z5TMRQz+4NkcNyQrd75U=; b=VwdjZs+NHyenL1RsnyUtUS2hJGMgr/ruob9Dt3qamNVtB8KjuJ+iiAVhGMMLWmnrIB PRl54AzQdaQ10+a3QnpoIkQ3lzZ6qqP9o95Q7ou5WUB72e9Hrv/Bj3kYlfdUqPehmJYY 3CQVw7Wsd2oRuScJjLwhwGCxZIqH64oeYz1AZKWeZkGoM1+MppGTTOJi9A63LZudTZzS bTgJ8MvFAuVLjg0A+i1wukhEUxDhT4z7EijLXaMiGjHKGeOxAMD93BQ39ZUx1prfPCbF A8NVIwXj+OhJLBKXtq8wnbSUtsDmiNjftQo6TggxEpENy7s671ZpgFzq8X2TUg55nP5F hxIw== X-Gm-Message-State: AEkoousinCI5slmMxR0+Eo+l37Xed6/CQkQHerMRwHGIVkzhrcjeQWBx32ATDiDz7fcm7xZK X-Received: by 10.98.60.20 with SMTP id j20mr11482462pfa.114.1470870556529; Wed, 10 Aug 2016 16:09:16 -0700 (PDT) Received: from [10.1.1.4] (58-6-183-210.dyn.iinet.net.au. [58.6.183.210]) by smtp.gmail.com with ESMTPSA id xx7sm66598790pac.3.2016.08.10.16.09.13 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 10 Aug 2016 16:09:15 -0700 (PDT) Subject: Re: [PR72835] Incorrect arithmetic optimization involving bitfield arguments To: Richard Biener , Jakub Jelinek 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: "gcc-patches@gcc.gnu.org" From: kugan Message-ID: Date: Thu, 11 Aug 2016 09:09:08 +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, 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. Thanks, Kugan gcc/testsuite/ChangeLog: 2016-08-10 Kugan Vivekanandarajah PR tree-optimization/72835 * gcc.dg/tree-ssa/pr72835.c: New test. gcc/ChangeLog: 2016-08-10 Kugan Vivekanandarajah PR tree-optimization/72835 * tree-ssa-reassoc.c (zero_one_operation): Incase of NEGATE_EXPR create and use new SSA_NAME. (try_special_add_to_ops): Return true if we changed the value in operands. (linearize_expr_tree): Return true if try_special_add_top_ops set ops_changed to true. (undistribute_ops_list): Likewise. (reassociate_bb): Pass ops_changed returned by linearlize_expr_tree to rewrite_expr_tree. whil cif we change the operands such that the /zero_one_operation diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr72835.c b/gcc/testsuite/gcc.dg/tree-ssa/pr72835.c index e69de29..049eddc 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/pr72835.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr72835.c @@ -0,0 +1,36 @@ +/* PR tree-optimization/72835. */ +/* { dg-do run } */ +/* { dg-options "-O2" } */ + +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..038da41 100644 --- a/gcc/tree-ssa-reassoc.c +++ b/gcc/tree-ssa-reassoc.c @@ -1039,7 +1039,7 @@ eliminate_using_constants (enum tree_code opcode, static void linearize_expr_tree (vec *, gimple *, - bool, bool); + bool, bool, bool *); /* Structure for tracking and counting operands. */ struct oecount { @@ -1183,7 +1183,7 @@ propagate_op_to_single_use (tree op, gimple *stmt, tree *def) is updated if there is only one operand but no operation left. */ static void -zero_one_operation (tree *def, enum tree_code opcode, tree op) +zero_one_operation (tree *def, enum tree_code opcode, tree op, bool ops_changed) { gimple *stmt = SSA_NAME_DEF_STMT (*def); @@ -1193,6 +1193,27 @@ zero_one_operation (tree *def, enum tree_code opcode, tree op) if (opcode == MULT_EXPR) { + /* In this case, the result in the *def will be different as + compared to how it was. Therefore, to avoid having SSA + which will have range_info and debug that reflects old + operation, create a new SSA and use it (PR72835). */ + if (ops_changed) + { + imm_use_iterator iter; + use_operand_p use_p; + gimple *use_stmt; + tree lhs = gimple_assign_lhs (stmt); + tree new_lhs = make_ssa_name (TREE_TYPE (lhs)); + FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs) + { + FOR_EACH_IMM_USE_ON_STMT (use_p, iter) + SET_USE (use_p, new_lhs); + update_stmt (use_stmt); + } + if (*def == lhs) + *def = new_lhs; + gimple_set_lhs (stmt, new_lhs); + } if (stmt_is_power_of_op (stmt, op)) { if (decrement_power (stmt) == 1) @@ -1241,6 +1262,26 @@ zero_one_operation (tree *def, enum tree_code opcode, tree op) && has_single_use (gimple_assign_rhs2 (stmt))) { gimple *stmt2 = SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt)); + /* In this case the result in the op will be + different as compared to how it was. Therefore, to avoid + having SSA which will have range_info and debug that + reflects old operation, create a new SSA and use + it (PR72835). */ + if (ops_changed) + { + imm_use_iterator iter; + use_operand_p use_p; + gimple *use_stmt; + tree lhs = gimple_assign_lhs (stmt2); + tree new_lhs = make_ssa_name (TREE_TYPE (lhs)); + FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs) + { + FOR_EACH_IMM_USE_ON_STMT (use_p, iter) + SET_USE (use_p, new_lhs); + update_stmt (use_stmt); + } + gimple_set_lhs (stmt2, new_lhs); + } if (stmt_is_power_of_op (stmt2, op)) { if (decrement_power (stmt2) == 1) @@ -1453,7 +1494,8 @@ build_and_add_sum (tree type, tree op1, tree op2, enum tree_code opcode) static bool undistribute_ops_list (enum tree_code opcode, - vec *ops, struct loop *loop) + vec *ops, struct loop *loop, + bool *ops_changed) { unsigned int length = ops->length (); operand_entry *oe1; @@ -1521,7 +1563,7 @@ undistribute_ops_list (enum tree_code opcode, oedef = SSA_NAME_DEF_STMT ((*ops)[i]->op); oecode = gimple_assign_rhs_code (oedef); linearize_expr_tree (&subops[i], oedef, - associative_tree_code (oecode), false); + associative_tree_code (oecode), false, ops_changed); FOR_EACH_VEC_ELT (subops[i], j, oe1) { @@ -1617,7 +1659,7 @@ undistribute_ops_list (enum tree_code opcode, fprintf (dump_file, "Building ("); print_generic_expr (dump_file, oe1->op, 0); } - zero_one_operation (&oe1->op, c->oecode, c->op); + zero_one_operation (&oe1->op, c->oecode, c->op, *ops_changed); EXECUTE_IF_SET_IN_BITMAP (candidates2, first+1, i, sbi0) { gimple *sum; @@ -1627,7 +1669,7 @@ undistribute_ops_list (enum tree_code opcode, fprintf (dump_file, " + "); print_generic_expr (dump_file, oe2->op, 0); } - zero_one_operation (&oe2->op, c->oecode, c->op); + zero_one_operation (&oe2->op, c->oecode, c->op, *ops_changed); sum = build_and_add_sum (TREE_TYPE (oe1->op), oe1->op, oe2->op, opcode); oe2->op = build_zero_cst (TREE_TYPE (oe2->op)); @@ -4456,12 +4498,16 @@ acceptable_pow_call (gcall *stmt, tree *base, HOST_WIDE_INT *exponent) } /* Try to derive and add operand entry for OP to *OPS. Return false if - unsuccessful. */ + unsuccessful. If we changed the operands such that the (intermediate) + results can be different (as in the case of NEGATE_EXPR converted to + multiplication by -1), set ops_changed to true so that we will not + reuse the SSA (PR72835). */ static bool try_special_add_to_ops (vec *ops, enum tree_code code, - tree op, gimple* def_stmt) + tree op, gimple* def_stmt, + bool *ops_changed) { tree base = NULL_TREE; HOST_WIDE_INT exponent = 0; @@ -4492,6 +4538,8 @@ try_special_add_to_ops (vec *ops, add_to_ops_vec (ops, rhs1); add_to_ops_vec (ops, cst); gimple_set_visited (def_stmt, true); + if (ops_changed) + *ops_changed = true; return true; } @@ -4499,11 +4547,12 @@ try_special_add_to_ops (vec *ops, } /* Recursively linearize a binary expression that is the RHS of STMT. - Place the operands of the expression tree in the vector named OPS. */ + Place the operands of the expression tree in the vector named OPS. + Return TRUE if try_special_add_to_ops has set ops_changed to TRUE. */ static void linearize_expr_tree (vec *ops, gimple *stmt, - bool is_associative, bool set_visited) + bool is_associative, bool set_visited, bool *ops_changed) { tree binlhs = gimple_assign_rhs1 (stmt); tree binrhs = gimple_assign_rhs2 (stmt); @@ -4547,10 +4596,12 @@ linearize_expr_tree (vec *ops, gimple *stmt, if (!binrhsisreassoc) { - if (!try_special_add_to_ops (ops, rhscode, binrhs, binrhsdef)) + if (!try_special_add_to_ops (ops, rhscode, binrhs, + binrhsdef, ops_changed)) add_to_ops_vec (ops, binrhs); - if (!try_special_add_to_ops (ops, rhscode, binlhs, binlhsdef)) + if (!try_special_add_to_ops (ops, rhscode, binlhs, + binlhsdef, ops_changed)) add_to_ops_vec (ops, binlhs); return; @@ -4588,9 +4639,9 @@ linearize_expr_tree (vec *ops, gimple *stmt, || !is_reassociable_op (SSA_NAME_DEF_STMT (binrhs), rhscode, loop)); linearize_expr_tree (ops, SSA_NAME_DEF_STMT (binlhs), - is_associative, set_visited); + is_associative, set_visited, ops_changed); - if (!try_special_add_to_ops (ops, rhscode, binrhs, binrhsdef)) + if (!try_special_add_to_ops (ops, rhscode, binrhs, binrhsdef, ops_changed)) add_to_ops_vec (ops, binrhs); } @@ -5322,12 +5373,20 @@ reassociate_bb (basic_block bb) if (TREE_CODE (lhs) == SSA_NAME && has_zero_uses (lhs)) continue; + bool ops_changed = false; gimple_set_visited (stmt, true); - linearize_expr_tree (&ops, stmt, true, true); + linearize_expr_tree (&ops, stmt, true, true, NULL); ops.qsort (sort_by_operand_rank); optimize_ops_list (rhs_code, &ops); + /* While in undistribute_ops_list, NEGATE_EXPR is factored out, + operands to the reassociated stmts will be different + compared to how it was. In this case, to avoid having SSA + which will have range_info and debug that reflects old + operation, rewrite_expr_tree has to be called with + changed = true (PR72835). */ if (undistribute_ops_list (rhs_code, &ops, - loop_containing_stmt (stmt))) + loop_containing_stmt (stmt), + &ops_changed)) { ops.qsort (sort_by_operand_rank); optimize_ops_list (rhs_code, &ops); @@ -5415,7 +5474,8 @@ reassociate_bb (basic_block bb) new_lhs = rewrite_expr_tree (stmt, 0, ops, powi_result != NULL - || negate_result); + || negate_result + || ops_changed); } /* If we combined some repeated factors into a