[PATCH] CSE negated multiplications and divisions

[PATCH] CSE negated multiplications and divisions

[Richard Biener]

This adds the capability to look for available negated multiplications
and divisions, replacing them with cheaper negates.

Bootstrapped and tested on x86_64-unknown-linux-gnu, pushed.

2020-09-17  Richard Biener  <rguenther@suse.de>

	* tree-ssa-sccvn.c (visit_nary_op): Value-number multiplications
	and divisions to negates of available negated forms.

	* gcc.dg/tree-ssa/ssa-fre-88.c: New testcase.
---
 gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-88.c | 18 +++++++++++
 gcc/tree-ssa-sccvn.c                       | 35 ++++++++++++++++++++++
 2 files changed, 53 insertions(+)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-88.c

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-88.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-88.c
new file mode 100644
index 00000000000..15d2ca05e65
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-88.c
@@ -0,0 +1,18 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-fre1" } */
+
+double y[2];
+void foo (double x)
+{
+  y[0] = x * -3.;
+  y[1] = x * 3.;
+}
+void bar (double x, double z)
+{
+  y[0] = -z / x;
+  y[1] = z / x;
+}
+
+/* { dg-final { scan-tree-dump-times " \\* " 1 "fre1" } } */
+/* { dg-final { scan-tree-dump-times " / " 1 "fre1" } } */
+/* { dg-final { scan-tree-dump-times "= -_" 2 "fre1" } } */
diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c
index 8fbb1dd46d1..64f1e8c9160 100644
--- a/gcc/tree-ssa-sccvn.c
+++ b/gcc/tree-ssa-sccvn.c
@@ -4824,6 +4824,40 @@ visit_nary_op (tree lhs, gassign *stmt)
 	    }
 	}
       break;
+    case RDIV_EXPR:
+    case TRUNC_DIV_EXPR:
+    case MULT_EXPR:
+      /* Match up ([-]a){/,*}([-])b with v=a{/,*}b, replacing it with -v.  */
+      if (! HONOR_SIGN_DEPENDENT_ROUNDING (type))
+	{
+	  tree rhs[2];
+	  rhs[0] = rhs1;
+	  rhs[1] = gimple_assign_rhs2 (stmt);
+	  for (unsigned i = 0; i <= 1; ++i)
+	    {
+	      unsigned j = i == 0 ? 1 : 0;
+	      tree ops[2];
+	      gimple_match_op match_op (gimple_match_cond::UNCOND,
+					NEGATE_EXPR, type, rhs[i]);
+	      ops[i] = vn_nary_build_or_lookup_1 (&match_op, false);
+	      ops[j] = rhs[j];
+	      if (ops[i]
+		  && (ops[0] = vn_nary_op_lookup_pieces (2, code,
+							 type, ops, NULL)))
+		{
+		  gimple_match_op match_op (gimple_match_cond::UNCOND,
+					    NEGATE_EXPR, type, ops[0]);
+		  result = vn_nary_build_or_lookup (&match_op);
+		  if (result)
+		    {
+		      bool changed = set_ssa_val_to (lhs, result);
+		      vn_nary_op_insert_stmt (stmt, result);
+		      return changed;
+		    }
+		}
+	    }
+	}
+      break;
     default:
       break;
     }
@@ -5739,6 +5773,7 @@ eliminate_dom_walker::eliminate_insert (basic_block bb,
   if (!stmt
       || (!CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt))
 	  && gimple_assign_rhs_code (stmt) != VIEW_CONVERT_EXPR
+	  && gimple_assign_rhs_code (stmt) != NEGATE_EXPR
 	  && gimple_assign_rhs_code (stmt) != BIT_FIELD_REF
 	  && (gimple_assign_rhs_code (stmt) != BIT_AND_EXPR
 	      || TREE_CODE (gimple_assign_rhs2 (stmt)) != INTEGER_CST)))
-- 
2.26.2

Re: [PATCH] CSE negated multiplications and divisions

[Christophe Lyon]

On Thu, 17 Sep 2020 at 13:20, Richard Biener <rguenther@suse.de> wrote:
>
> This adds the capability to look for available negated multiplications
> and divisions, replacing them with cheaper negates.
>
> Bootstrapped and tested on x86_64-unknown-linux-gnu, pushed.
>

This patch caused a regression in fortran, I filed
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97109


> 2020-09-17  Richard Biener  <rguenther@suse.de>
>
>         * tree-ssa-sccvn.c (visit_nary_op): Value-number multiplications
>         and divisions to negates of available negated forms.
>
>         * gcc.dg/tree-ssa/ssa-fre-88.c: New testcase.
> ---
>  gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-88.c | 18 +++++++++++
>  gcc/tree-ssa-sccvn.c                       | 35 ++++++++++++++++++++++
>  2 files changed, 53 insertions(+)
>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-88.c
>
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-88.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-88.c
> new file mode 100644
> index 00000000000..15d2ca05e65
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-88.c
> @@ -0,0 +1,18 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-fre1" } */
> +
> +double y[2];
> +void foo (double x)
> +{
> +  y[0] = x * -3.;
> +  y[1] = x * 3.;
> +}
> +void bar (double x, double z)
> +{
> +  y[0] = -z / x;
> +  y[1] = z / x;
> +}
> +
> +/* { dg-final { scan-tree-dump-times " \\* " 1 "fre1" } } */
> +/* { dg-final { scan-tree-dump-times " / " 1 "fre1" } } */
> +/* { dg-final { scan-tree-dump-times "= -_" 2 "fre1" } } */
> diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c
> index 8fbb1dd46d1..64f1e8c9160 100644
> --- a/gcc/tree-ssa-sccvn.c
> +++ b/gcc/tree-ssa-sccvn.c
> @@ -4824,6 +4824,40 @@ visit_nary_op (tree lhs, gassign *stmt)
>             }
>         }
>        break;
> +    case RDIV_EXPR:
> +    case TRUNC_DIV_EXPR:
> +    case MULT_EXPR:
> +      /* Match up ([-]a){/,*}([-])b with v=a{/,*}b, replacing it with -v.  */
> +      if (! HONOR_SIGN_DEPENDENT_ROUNDING (type))
> +       {
> +         tree rhs[2];
> +         rhs[0] = rhs1;
> +         rhs[1] = gimple_assign_rhs2 (stmt);
> +         for (unsigned i = 0; i <= 1; ++i)
> +           {
> +             unsigned j = i == 0 ? 1 : 0;
> +             tree ops[2];
> +             gimple_match_op match_op (gimple_match_cond::UNCOND,
> +                                       NEGATE_EXPR, type, rhs[i]);
> +             ops[i] = vn_nary_build_or_lookup_1 (&match_op, false);
> +             ops[j] = rhs[j];
> +             if (ops[i]
> +                 && (ops[0] = vn_nary_op_lookup_pieces (2, code,
> +                                                        type, ops, NULL)))
> +               {
> +                 gimple_match_op match_op (gimple_match_cond::UNCOND,
> +                                           NEGATE_EXPR, type, ops[0]);
> +                 result = vn_nary_build_or_lookup (&match_op);
> +                 if (result)
> +                   {
> +                     bool changed = set_ssa_val_to (lhs, result);
> +                     vn_nary_op_insert_stmt (stmt, result);
> +                     return changed;
> +                   }
> +               }
> +           }
> +       }
> +      break;
>      default:
>        break;
>      }
> @@ -5739,6 +5773,7 @@ eliminate_dom_walker::eliminate_insert (basic_block bb,
>    if (!stmt
>        || (!CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt))
>           && gimple_assign_rhs_code (stmt) != VIEW_CONVERT_EXPR
> +         && gimple_assign_rhs_code (stmt) != NEGATE_EXPR
>           && gimple_assign_rhs_code (stmt) != BIT_FIELD_REF
>           && (gimple_assign_rhs_code (stmt) != BIT_AND_EXPR
>               || TREE_CODE (gimple_assign_rhs2 (stmt)) != INTEGER_CST)))
> --
> 2.26.2

Re: [PATCH] CSE negated multiplications and divisions

[Segher Boessenkool]

Hi!

On Thu, Sep 17, 2020 at 01:20:35PM +0200, Richard Biener wrote:
> This adds the capability to look for available negated multiplications
> and divisions, replacing them with cheaper negates.

It is longer latency than the original insns.  Combine will try to undo
this, because of that (it depends on the insn costs if that can
succeed).  On gimple it is always cheaper, of course.


Segher

Re: [PATCH] CSE negated multiplications and divisions

[Richard Biener]

On Fri, 18 Sep 2020, Segher Boessenkool wrote:

> Hi!
> 
> On Thu, Sep 17, 2020 at 01:20:35PM +0200, Richard Biener wrote:
> > This adds the capability to look for available negated multiplications
> > and divisions, replacing them with cheaper negates.
> 
> It is longer latency than the original insns.

If there's sufficient compute resources yes, it might be.  But only
if the un-CSEd instructions are close together.  If the first multiply
is already done the negate will be faster than another multiply.

> Combine will try to undo
> this, because of that (it depends on the insn costs if that can
> succeed).

That's fine I guess.

> On gimple it is always cheaper, of course.

Yep, and we'll also hope of followup transform that will eat the
negate and combine it with a followup transform.

Richard.