diff mbox

[PR72835] Incorrect arithmetic optimization involving bitfield arguments

Message ID CAELXzTNVFBjDxa5_cyYh1rL+dHjnrrrgKE=W3L2ZPeUXm3NiTg@mail.gmail.com
State New
Headers show

Commit Message

Kugan Vivekanandarajah Sept. 2, 2016, 8:09 a.m. UTC 
Hi Richard,

On 25 August 2016 at 22:24, Richard Biener <richard.guenther@gmail.com> wrote:
> On Thu, Aug 11, 2016 at 1:09 AM, kugan
> <kugan.vivekanandarajah@linaro.org> wrote:
>> Hi,
>>
>>
>> On 10/08/16 20:28, Richard Biener wrote:
>>>
>>> On Wed, Aug 10, 2016 at 10:57 AM, Jakub Jelinek <jakub@redhat.com> 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?


Bootstrapped and regression tested on x86_64-linux-gnu with no new regressions.

Thanks,
Kugan

Comments

Richard Biener Sept. 14, 2016, 11:31 a.m. UTC | #1 
On Fri, Sep 2, 2016 at 10:09 AM, Kugan Vivekanandarajah
<kugan.vivekanandarajah@linaro.org> wrote:
> Hi Richard,
>
> On 25 August 2016 at 22:24, Richard Biener <richard.guenther@gmail.com> wrote:
>> On Thu, Aug 11, 2016 at 1:09 AM, kugan
>> <kugan.vivekanandarajah@linaro.org> wrote:
>>> Hi,
>>>
>>>
>>> On 10/08/16 20:28, Richard Biener wrote:
>>>>
>>>> On Wed, Aug 10, 2016 at 10:57 AM, Jakub Jelinek <jakub@redhat.com> 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<gimple *> stmts_to_fix;

use auto_vec<gimple *, 64> here so we get stack allocation only most
of the times

          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.

@@ -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).

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 mbox

Patch

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..c7f6a66 100644
--- a/gcc/tree-ssa-reassoc.c
+++ b/gcc/tree-ssa-reassoc.c
@@ -1148,6 +1148,49 @@  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);
+  gcc_assert (has_single_use (lhs));
+
+  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<gimple *> &stmts_to_fix)
+{
+  unsigned i;
+  gimple *stmt = SSA_NAME_DEF_STMT (*def);
+  if (*def != op
+      && 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 +1229,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<gimple *> stmts_to_fix;
 
   do
     {
@@ -1195,6 +1241,7 @@  zero_one_operation (tree *def, enum tree_code opcode, tree op)
 	{
 	  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);
 	      return;
@@ -1204,6 +1251,7 @@  zero_one_operation (tree *def, enum tree_code opcode, tree op)
 	      if (gimple_assign_rhs1 (stmt) == op)
 		{
 		  tree cst = build_minus_one_cst (TREE_TYPE (op));
+		  make_new_ssa_for_all_defs (def, op, stmts_to_fix);
 		  propagate_op_to_single_use (cst, stmt, def);
 		  return;
 		}
@@ -1212,6 +1260,7 @@  zero_one_operation (tree *def, enum tree_code opcode, tree op)
 		{
 		  gimple_assign_set_rhs_code
 		    (stmt, TREE_CODE (gimple_assign_rhs1 (stmt)));
+		  make_new_ssa_for_all_defs (def, op, stmts_to_fix);
 		  return;
 		}
 	    }
@@ -1228,6 +1277,7 @@  zero_one_operation (tree *def, enum tree_code opcode, tree op)
 	{
 	  if (name == op)
 	    name = gimple_assign_rhs2 (stmt);
+	  make_new_ssa_for_all_defs (def, op, stmts_to_fix);
 	  propagate_op_to_single_use (name, stmt, def);
 	  return;
 	}
@@ -1243,6 +1293,8 @@  zero_one_operation (tree *def, enum tree_code opcode, tree op)
 	  gimple *stmt2 = SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt));
 	  if (stmt_is_power_of_op (stmt2, op))
 	    {
+	      stmts_to_fix.safe_push (stmt2);
+	      make_new_ssa_for_all_defs (def, op, stmts_to_fix);
 	      if (decrement_power (stmt2) == 1)
 		propagate_op_to_single_use (op, stmt2, def);
 	      return;
@@ -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;
 		}
 	      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)));
+		  make_new_ssa_for_all_defs (def, op, stmts_to_fix);
 		  return;
 		}
 	    }
@@ -1270,6 +1326,7 @@  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);
 }