[v1] Vect: Distribute truncation into .SAT_SUB operands

Message ID 20240630031259.3505352-1-pan2.li@intel.com New [v1] Vect: Distribute truncation into .SAT_SUB operands |

Checks

Context Check Description
linaro-tcwg-bot/tcwg_gcc_build--master-arm success Build passed
linaro-tcwg-bot/tcwg_gcc_build--master-aarch64 success Build passed
linaro-tcwg-bot/tcwg_gcc_check--master-arm success Test passed
linaro-tcwg-bot/tcwg_gcc_check--master-aarch64 success Test passed

Commit Message

Li, Pan2 June 30, 2024, 3:12 a.m. UTC
```  From: Pan Li <pan2.li@intel.com>

To get better vectorized code of .SAT_SUB,  we would like to avoid the
truncated operation for the assignment.  For example, as below.

unsigned int _1;
unsigned int _2;
_9 = (unsigned short int).SAT_SUB (_1, _2);

If we make sure that the _1 is in the range of unsigned short int.  Such
as a def similar to:

_1 = (unsigned short int)_4;

Then we can do the distribute the truncation operation to:

_3 = MIN_EXPR (_2, 65535);
_9 = .SAT_SUB ((unsigned short int)_1, (unsigned short int)_3);

Let's take RISC-V vector as example to tell the changes.  For below
sample code:

__attribute__((noinline))
void test (uint16_t *x, unsigned b, unsigned n)
{
unsigned a = 0;
uint16_t *p = x;

do {
a = *--p;
*p = (uint16_t)(a >= b ? a - b : 0);
} while (--n);
}

Before this patch:
...
.L3:
vle16.v	v1,0(a3)
vrsub.vx	v5,v2,t1
mv	t3,a4
vrgather.vv	v3,v1,v5
vsetvli	zero,zero,e32,m1,ta,ma
vzext.vf2	v1,v3
vssubu.vx	v1,v1,a1
vsetvli	zero,zero,e16,mf2,ta,ma
vncvt.x.x.w	v1,v1
vrgather.vv	v3,v1,v5
vse16.v	v3,0(a3)
sub	a3,a3,t4
bgtu	t6,a4,.L3
...

After this patch:
test:
...
.L3:
vle16.v	v3,0(a3)
vrsub.vx	v5,v2,a6
mv	a7,a4
vrgather.vv	v1,v3,v5
vssubu.vv	v1,v1,v6
vrgather.vv	v3,v1,v5
vse16.v	v3,0(a3)
sub	a3,a3,t1
bgtu	t4,a4,.L3
...

The below test suites are passed for this patch:
1. The rv64gcv fully regression tests.
2. The rv64gcv build with glibc.
3. The x86 bootstrap tests.
4. The x86 fully regression tests.

gcc/ChangeLog:

* tree-vect-patterns.cc (vect_recog_sat_sub_pattern_distribute):
Add new func impl to perform the truncation distribution.
(vect_recog_sat_sub_pattern): Perform above optimize before
generate .SAT_SUB call.

Signed-off-by: Pan Li <pan2.li@intel.com>
---
gcc/tree-vect-patterns.cc | 73 +++++++++++++++++++++++++++++++++++++++
1 file changed, 73 insertions(+)
```

Richard Biener July 3, 2024, 9:02 a.m. UTC | #1
```On Sun, Jun 30, 2024 at 5:13 AM <pan2.li@intel.com> wrote:
>
> From: Pan Li <pan2.li@intel.com>
>
> To get better vectorized code of .SAT_SUB,  we would like to avoid the
> truncated operation for the assignment.  For example, as below.
>
> unsigned int _1;
> unsigned int _2;
> _9 = (unsigned short int).SAT_SUB (_1, _2);
>
> If we make sure that the _1 is in the range of unsigned short int.  Such
> as a def similar to:
>
> _1 = (unsigned short int)_4;
>
> Then we can do the distribute the truncation operation to:
>
> _3 = MIN_EXPR (_2, 65535);
> _9 = .SAT_SUB ((unsigned short int)_1, (unsigned short int)_3);
>
> Let's take RISC-V vector as example to tell the changes.  For below
> sample code:
>
> __attribute__((noinline))
> void test (uint16_t *x, unsigned b, unsigned n)
> {
>   unsigned a = 0;
>   uint16_t *p = x;
>
>   do {
>     a = *--p;
>     *p = (uint16_t)(a >= b ? a - b : 0);
>   } while (--n);
> }
>
> Before this patch:
>   ...
>   .L3:
>   vle16.v       v1,0(a3)
>   vrsub.vx      v5,v2,t1
>   mv    t3,a4
>   vrgather.vv   v3,v1,v5
>   vsetvli       zero,zero,e32,m1,ta,ma
>   vzext.vf2     v1,v3
>   vssubu.vx     v1,v1,a1
>   vsetvli       zero,zero,e16,mf2,ta,ma
>   vncvt.x.x.w   v1,v1
>   vrgather.vv   v3,v1,v5
>   vse16.v       v3,0(a3)
>   sub   a3,a3,t4
>   bgtu  t6,a4,.L3
>   ...
>
> After this patch:
> test:
>   ...
>   .L3:
>   vle16.v       v3,0(a3)
>   vrsub.vx      v5,v2,a6
>   mv    a7,a4
>   vrgather.vv   v1,v3,v5
>   vssubu.vv     v1,v1,v6
>   vrgather.vv   v3,v1,v5
>   vse16.v       v3,0(a3)
>   sub   a3,a3,t1
>   bgtu  t4,a4,.L3
>   ...
>
> The below test suites are passed for this patch:
> 1. The rv64gcv fully regression tests.
> 2. The rv64gcv build with glibc.
> 3. The x86 bootstrap tests.
> 4. The x86 fully regression tests.
>
> gcc/ChangeLog:
>
>         * tree-vect-patterns.cc (vect_recog_sat_sub_pattern_distribute):
>         Add new func impl to perform the truncation distribution.
>         (vect_recog_sat_sub_pattern): Perform above optimize before
>         generate .SAT_SUB call.
>
> Signed-off-by: Pan Li <pan2.li@intel.com>
> ---
>  gcc/tree-vect-patterns.cc | 73 +++++++++++++++++++++++++++++++++++++++
>  1 file changed, 73 insertions(+)
>
> diff --git a/gcc/tree-vect-patterns.cc b/gcc/tree-vect-patterns.cc
> index 519d15f2a43..7329ecec2c4 100644
> --- a/gcc/tree-vect-patterns.cc
> +++ b/gcc/tree-vect-patterns.cc
> @@ -4565,6 +4565,77 @@ vect_recog_sat_add_pattern (vec_info *vinfo, stmt_vec_info stmt_vinfo,
>    return NULL;
>  }
>
> +/*
> + * Try to distribute the truncation for .SAT_SUB pattern,  mostly occurs in
> + * the benchmark zip.  Aka:
> + *
> + *   unsigned int _1;
> + *   unsigned int _2;
> + *   _9 = (unsigned short int).SAT_SUB (_1, _2);
> + *
> + *   if _1 is known to be in the range of unsigned short int.  For example
> + *   there is a def _1 = (unsigned short int)_4.  Then we can distribute the
> + *   truncation to:
> + *
> + *   _3 = MIN (65535, _2);
> + *   _9 = .SAT_SUB ((unsigned short int)_1, (unsigned short int)_3);
> + *
> + *   Then,  we can better vectorized code and avoid the unnecessary narrowing
> + *   stmt during vectorization.
> + */
> +static void
> +vect_recog_sat_sub_pattern_distribute (vec_info *vinfo,
> +                                      stmt_vec_info stmt_vinfo,
> +                                      gimple *stmt, tree lhs, tree *ops)
> +{
> +  tree otype = TREE_TYPE (lhs);
> +  tree itype = TREE_TYPE (ops[0]);
> +
> +  if (types_compatible_p (otype, itype))
> +    return;
> +
> +  unsigned itype_prec = TYPE_PRECISION (itype);
> +  unsigned otype_prec = TYPE_PRECISION (otype);
> +
> +  if (otype_prec >= itype_prec)
> +    return;
> +
> +  int_range_max r;
> +  gimple_ranger granger;
> +
> +  if (granger.range_of_expr (r, ops[0], stmt) && !r.undefined_p ())
> +    {
> +      wide_int bound = r.upper_bound ();
> +      wide_int otype_max = wi::mask (otype_prec, /* negate */false, itype_prec);
> +
> +      if (bound != otype_max)

Isn't bound < otype_max OK as well?

vect_look_through_possible_promotion?  Because ...

> +       return;
> +
> +      tree v_otype = get_vectype_for_scalar_type (vinfo, otype);
> +      tree v_itype = get_vectype_for_scalar_type (vinfo, itype);
> +
> +      /* 1. Build truncated op_0  */
> +      tree op_0_out = vect_recog_temp_ssa_var (otype, NULL);
> +      gimple *op_0_cast = gimple_build_assign (op_0_out, NOP_EXPR, ops[0]);
> +      append_pattern_def_seq (vinfo, stmt_vinfo, op_0_cast, v_otype);

.. if you do it like this the widened op is still there and vectorized
and the whole
point is to make it possible to use a smaller vectorization factor?

> +      /* 2. Build MIN_EXPR (op_1, 65536)  */
> +      tree max = wide_int_to_tree (itype, otype_max);
> +      tree op_1_in = vect_recog_temp_ssa_var (itype, NULL);
> +      gimple *op_1_min = gimple_build_assign (op_1_in, MIN_EXPR, ops[1], max);

I think you want to check that the target supports vectorizing
MIN_EXPR in this type.

> +      append_pattern_def_seq (vinfo, stmt_vinfo, op_1_min, v_itype);
> +
> +      /* 3. Build truncated op_1  */
> +      tree op_1_out = vect_recog_temp_ssa_var (otype, NULL);
> +      gimple *op_1_cast = gimple_build_assign (op_1_out, NOP_EXPR, op_1_in);
> +      append_pattern_def_seq (vinfo, stmt_vinfo, op_1_cast, v_otype);
> +
> +      /* 4. Update the ops  */
> +      ops[0] = op_0_out;
> +      ops[1] = op_1_out;
> +    }
> +}
> +
>  /*
>   * Try to detect saturation sub pattern (SAT_ADD), aka below gimple:
>   *   _7 = _1 >= _2;
> @@ -4590,6 +4661,8 @@ vect_recog_sat_sub_pattern (vec_info *vinfo, stmt_vec_info stmt_vinfo,
>
>    if (gimple_unsigned_integer_sat_sub (lhs, ops, NULL))
>      {
> +      vect_recog_sat_sub_pattern_distribute (vinfo, stmt_vinfo, last_stmt,
> +                                            lhs, ops);
>        gimple *stmt = vect_recog_build_binary_gimple_stmt (vinfo, stmt_vinfo,
>                                                           IFN_SAT_SUB, type_out,
>                                                           lhs, ops[0], ops[1]);
> --
> 2.34.1
>
```
Li, Pan2 July 3, 2024, 1:32 p.m. UTC | #2
```Thanks Richard for comments.

> Isn't bound < otype_max OK as well?

Yes, less than or equal is OK as well.

> Given your example I wonder if you instead want to use
> vect_look_through_possible_promotion?  Because ...

> .. if you do it like this the widened op is still there and vectorized
> and the whole
> point is to make it possible to use a smaller vectorization factor?

Got it, will have a try thru vect_look_through_possible_promotion.

> I think you want to check that the target supports vectorizing
> MIN_EXPR in this type.

Sure.

Pan

-----Original Message-----
From: Richard Biener <richard.guenther@gmail.com>
Sent: Wednesday, July 3, 2024 5:03 PM
To: Li, Pan2 <pan2.li@intel.com>
Cc: gcc-patches@gcc.gnu.org; juzhe.zhong@rivai.ai; kito.cheng@gmail.com; tamar.christina@arm.com; jeffreyalaw@gmail.com; rdapp.gcc@gmail.com
Subject: Re: [PATCH v1] Vect: Distribute truncation into .SAT_SUB operands

On Sun, Jun 30, 2024 at 5:13 AM <pan2.li@intel.com> wrote:
>
> From: Pan Li <pan2.li@intel.com>
>
> To get better vectorized code of .SAT_SUB,  we would like to avoid the
> truncated operation for the assignment.  For example, as below.
>
> unsigned int _1;
> unsigned int _2;
> _9 = (unsigned short int).SAT_SUB (_1, _2);
>
> If we make sure that the _1 is in the range of unsigned short int.  Such
> as a def similar to:
>
> _1 = (unsigned short int)_4;
>
> Then we can do the distribute the truncation operation to:
>
> _3 = MIN_EXPR (_2, 65535);
> _9 = .SAT_SUB ((unsigned short int)_1, (unsigned short int)_3);
>
> Let's take RISC-V vector as example to tell the changes.  For below
> sample code:
>
> __attribute__((noinline))
> void test (uint16_t *x, unsigned b, unsigned n)
> {
>   unsigned a = 0;
>   uint16_t *p = x;
>
>   do {
>     a = *--p;
>     *p = (uint16_t)(a >= b ? a - b : 0);
>   } while (--n);
> }
>
> Before this patch:
>   ...
>   .L3:
>   vle16.v       v1,0(a3)
>   vrsub.vx      v5,v2,t1
>   mv    t3,a4
>   vrgather.vv   v3,v1,v5
>   vsetvli       zero,zero,e32,m1,ta,ma
>   vzext.vf2     v1,v3
>   vssubu.vx     v1,v1,a1
>   vsetvli       zero,zero,e16,mf2,ta,ma
>   vncvt.x.x.w   v1,v1
>   vrgather.vv   v3,v1,v5
>   vse16.v       v3,0(a3)
>   sub   a3,a3,t4
>   bgtu  t6,a4,.L3
>   ...
>
> After this patch:
> test:
>   ...
>   .L3:
>   vle16.v       v3,0(a3)
>   vrsub.vx      v5,v2,a6
>   mv    a7,a4
>   vrgather.vv   v1,v3,v5
>   vssubu.vv     v1,v1,v6
>   vrgather.vv   v3,v1,v5
>   vse16.v       v3,0(a3)
>   sub   a3,a3,t1
>   bgtu  t4,a4,.L3
>   ...
>
> The below test suites are passed for this patch:
> 1. The rv64gcv fully regression tests.
> 2. The rv64gcv build with glibc.
> 3. The x86 bootstrap tests.
> 4. The x86 fully regression tests.
>
> gcc/ChangeLog:
>
>         * tree-vect-patterns.cc (vect_recog_sat_sub_pattern_distribute):
>         Add new func impl to perform the truncation distribution.
>         (vect_recog_sat_sub_pattern): Perform above optimize before
>         generate .SAT_SUB call.
>
> Signed-off-by: Pan Li <pan2.li@intel.com>
> ---
>  gcc/tree-vect-patterns.cc | 73 +++++++++++++++++++++++++++++++++++++++
>  1 file changed, 73 insertions(+)
>
> diff --git a/gcc/tree-vect-patterns.cc b/gcc/tree-vect-patterns.cc
> index 519d15f2a43..7329ecec2c4 100644
> --- a/gcc/tree-vect-patterns.cc
> +++ b/gcc/tree-vect-patterns.cc
> @@ -4565,6 +4565,77 @@ vect_recog_sat_add_pattern (vec_info *vinfo, stmt_vec_info stmt_vinfo,
>    return NULL;
>  }
>
> +/*
> + * Try to distribute the truncation for .SAT_SUB pattern,  mostly occurs in
> + * the benchmark zip.  Aka:
> + *
> + *   unsigned int _1;
> + *   unsigned int _2;
> + *   _9 = (unsigned short int).SAT_SUB (_1, _2);
> + *
> + *   if _1 is known to be in the range of unsigned short int.  For example
> + *   there is a def _1 = (unsigned short int)_4.  Then we can distribute the
> + *   truncation to:
> + *
> + *   _3 = MIN (65535, _2);
> + *   _9 = .SAT_SUB ((unsigned short int)_1, (unsigned short int)_3);
> + *
> + *   Then,  we can better vectorized code and avoid the unnecessary narrowing
> + *   stmt during vectorization.
> + */
> +static void
> +vect_recog_sat_sub_pattern_distribute (vec_info *vinfo,
> +                                      stmt_vec_info stmt_vinfo,
> +                                      gimple *stmt, tree lhs, tree *ops)
> +{
> +  tree otype = TREE_TYPE (lhs);
> +  tree itype = TREE_TYPE (ops[0]);
> +
> +  if (types_compatible_p (otype, itype))
> +    return;
> +
> +  unsigned itype_prec = TYPE_PRECISION (itype);
> +  unsigned otype_prec = TYPE_PRECISION (otype);
> +
> +  if (otype_prec >= itype_prec)
> +    return;
> +
> +  int_range_max r;
> +  gimple_ranger granger;
> +
> +  if (granger.range_of_expr (r, ops[0], stmt) && !r.undefined_p ())
> +    {
> +      wide_int bound = r.upper_bound ();
> +      wide_int otype_max = wi::mask (otype_prec, /* negate */false, itype_prec);
> +
> +      if (bound != otype_max)

Isn't bound < otype_max OK as well?

vect_look_through_possible_promotion?  Because ...

> +       return;
> +
> +      tree v_otype = get_vectype_for_scalar_type (vinfo, otype);
> +      tree v_itype = get_vectype_for_scalar_type (vinfo, itype);
> +
> +      /* 1. Build truncated op_0  */
> +      tree op_0_out = vect_recog_temp_ssa_var (otype, NULL);
> +      gimple *op_0_cast = gimple_build_assign (op_0_out, NOP_EXPR, ops[0]);
> +      append_pattern_def_seq (vinfo, stmt_vinfo, op_0_cast, v_otype);

.. if you do it like this the widened op is still there and vectorized
and the whole
point is to make it possible to use a smaller vectorization factor?

> +      /* 2. Build MIN_EXPR (op_1, 65536)  */
> +      tree max = wide_int_to_tree (itype, otype_max);
> +      tree op_1_in = vect_recog_temp_ssa_var (itype, NULL);
> +      gimple *op_1_min = gimple_build_assign (op_1_in, MIN_EXPR, ops[1], max);

I think you want to check that the target supports vectorizing
MIN_EXPR in this type.

> +      append_pattern_def_seq (vinfo, stmt_vinfo, op_1_min, v_itype);
> +
> +      /* 3. Build truncated op_1  */
> +      tree op_1_out = vect_recog_temp_ssa_var (otype, NULL);
> +      gimple *op_1_cast = gimple_build_assign (op_1_out, NOP_EXPR, op_1_in);
> +      append_pattern_def_seq (vinfo, stmt_vinfo, op_1_cast, v_otype);
> +
> +      /* 4. Update the ops  */
> +      ops[0] = op_0_out;
> +      ops[1] = op_1_out;
> +    }
> +}
> +
>  /*
>   * Try to detect saturation sub pattern (SAT_ADD), aka below gimple:
>   *   _7 = _1 >= _2;
> @@ -4590,6 +4661,8 @@ vect_recog_sat_sub_pattern (vec_info *vinfo, stmt_vec_info stmt_vinfo,
>
>    if (gimple_unsigned_integer_sat_sub (lhs, ops, NULL))
>      {
> +      vect_recog_sat_sub_pattern_distribute (vinfo, stmt_vinfo, last_stmt,
> +                                            lhs, ops);
>        gimple *stmt = vect_recog_build_binary_gimple_stmt (vinfo, stmt_vinfo,
>                                                           IFN_SAT_SUB, type_out,
>                                                           lhs, ops[0], ops[1]);
> --
> 2.34.1
>
```

Patch

```diff --git a/gcc/tree-vect-patterns.cc b/gcc/tree-vect-patterns.cc
index 519d15f2a43..7329ecec2c4 100644
--- a/gcc/tree-vect-patterns.cc
+++ b/gcc/tree-vect-patterns.cc
@@ -4565,6 +4565,77 @@  vect_recog_sat_add_pattern (vec_info *vinfo, stmt_vec_info stmt_vinfo,
return NULL;
}

+/*
+ * Try to distribute the truncation for .SAT_SUB pattern,  mostly occurs in
+ * the benchmark zip.  Aka:
+ *
+ *   unsigned int _1;
+ *   unsigned int _2;
+ *   _9 = (unsigned short int).SAT_SUB (_1, _2);
+ *
+ *   if _1 is known to be in the range of unsigned short int.  For example
+ *   there is a def _1 = (unsigned short int)_4.  Then we can distribute the
+ *   truncation to:
+ *
+ *   _3 = MIN (65535, _2);
+ *   _9 = .SAT_SUB ((unsigned short int)_1, (unsigned short int)_3);
+ *
+ *   Then,  we can better vectorized code and avoid the unnecessary narrowing
+ *   stmt during vectorization.
+ */
+static void
+vect_recog_sat_sub_pattern_distribute (vec_info *vinfo,
+				       stmt_vec_info stmt_vinfo,
+				       gimple *stmt, tree lhs, tree *ops)
+{
+  tree otype = TREE_TYPE (lhs);
+  tree itype = TREE_TYPE (ops[0]);
+
+  if (types_compatible_p (otype, itype))
+    return;
+
+  unsigned itype_prec = TYPE_PRECISION (itype);
+  unsigned otype_prec = TYPE_PRECISION (otype);
+
+  if (otype_prec >= itype_prec)
+    return;
+
+  int_range_max r;
+  gimple_ranger granger;
+
+  if (granger.range_of_expr (r, ops[0], stmt) && !r.undefined_p ())
+    {
+      wide_int bound = r.upper_bound ();
+      wide_int otype_max = wi::mask (otype_prec, /* negate */false, itype_prec);
+
+      if (bound != otype_max)
+	return;
+
+      tree v_otype = get_vectype_for_scalar_type (vinfo, otype);
+      tree v_itype = get_vectype_for_scalar_type (vinfo, itype);
+
+      /* 1. Build truncated op_0  */
+      tree op_0_out = vect_recog_temp_ssa_var (otype, NULL);
+      gimple *op_0_cast = gimple_build_assign (op_0_out, NOP_EXPR, ops[0]);
+      append_pattern_def_seq (vinfo, stmt_vinfo, op_0_cast, v_otype);
+
+      /* 2. Build MIN_EXPR (op_1, 65536)  */
+      tree max = wide_int_to_tree (itype, otype_max);
+      tree op_1_in = vect_recog_temp_ssa_var (itype, NULL);
+      gimple *op_1_min = gimple_build_assign (op_1_in, MIN_EXPR, ops[1], max);
+      append_pattern_def_seq (vinfo, stmt_vinfo, op_1_min, v_itype);
+
+      /* 3. Build truncated op_1  */
+      tree op_1_out = vect_recog_temp_ssa_var (otype, NULL);
+      gimple *op_1_cast = gimple_build_assign (op_1_out, NOP_EXPR, op_1_in);
+      append_pattern_def_seq (vinfo, stmt_vinfo, op_1_cast, v_otype);
+
+      /* 4. Update the ops  */
+      ops[0] = op_0_out;
+      ops[1] = op_1_out;
+    }
+}
+
/*
* Try to detect saturation sub pattern (SAT_ADD), aka below gimple:
*   _7 = _1 >= _2;
@@ -4590,6 +4661,8 @@  vect_recog_sat_sub_pattern (vec_info *vinfo, stmt_vec_info stmt_vinfo,

if (gimple_unsigned_integer_sat_sub (lhs, ops, NULL))
{
+      vect_recog_sat_sub_pattern_distribute (vinfo, stmt_vinfo, last_stmt,
+					     lhs, ops);
gimple *stmt = vect_recog_build_binary_gimple_stmt (vinfo, stmt_vinfo,
IFN_SAT_SUB, type_out,
lhs, ops[0], ops[1]);

```