[PATCH] Use proper type in linear transformation in tree-switch-conversion (PR tree-optimization/88753).

[PATCH] Use proper type in linear transformation in tree-switch-conversion (PR tree-optimization/88753).

[Martin Liška]

[-- Attachment #1: Type: text/plain, Size: 588 bytes --]

Hi.

As seen in the PR, when doing switch convert linear transformation,
one needs to first convert to unsigned type for constructor values.

Patch survives regression tests and bootstrap on x86_64-linux-gnu.
Ready for trunk?
Thanks,
Martin


gcc/ChangeLog:

2019-01-08  Martin Liska  <mliska@suse.cz>

	PR tree-optimization/88753
	* tree-switch-conversion.c (switch_conversion::build_one_array):
	Come up with local variable constructor.  Convert first to
	type of constructor values.
---
 gcc/tree-switch-conversion.c | 11 ++++++-----
 1 file changed, 6 insertions(+), 5 deletions(-)



[-- Attachment #2: 0001-Use-proper-type-in-linear-transformation-in-tree-swi.patch --]
[-- Type: text/x-patch, Size: 1697 bytes --]

diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c
index 614c450dd4d..de41050f317 100644
--- a/gcc/tree-switch-conversion.c
+++ b/gcc/tree-switch-conversion.c
@@ -600,9 +600,9 @@ switch_conversion::build_one_array (int num, tree arr_index_type,
   name = copy_ssa_name (PHI_RESULT (phi));
   m_target_inbound_names[num] = name;
 
+  vec<constructor_elt, va_gc> *constructor = m_constructors[num];
   wide_int coeff_a, coeff_b;
-  bool linear_p = contains_linear_function_p (m_constructors[num], &coeff_a,
-					      &coeff_b);
+  bool linear_p = contains_linear_function_p (constructor, &coeff_a, &coeff_b);
   if (linear_p)
     {
       if (dump_file && coeff_a.to_uhwi () > 0)
@@ -610,7 +610,8 @@ switch_conversion::build_one_array (int num, tree arr_index_type,
 		 " and B = %" PRId64 "\n", coeff_a.to_shwi (),
 		 coeff_b.to_shwi ());
 
-      tree t = unsigned_type_for (TREE_TYPE (m_index_expr));
+      /* We must use type of constructor values.  */
+      tree t = unsigned_type_for (TREE_TYPE ((*constructor)[0].value));
       gimple_seq seq = NULL;
       tree tmp = gimple_convert (&seq, t, m_index_expr);
       tree tmp2 = gimple_build (&seq, MULT_EXPR, t,
@@ -633,10 +634,10 @@ switch_conversion::build_one_array (int num, tree arr_index_type,
 	  unsigned int i;
 	  constructor_elt *elt;
 
-	  FOR_EACH_VEC_SAFE_ELT (m_constructors[num], i, elt)
+	  FOR_EACH_VEC_SAFE_ELT (constructor, i, elt)
 	    elt->value = fold_convert (value_type, elt->value);
 	}
-      ctor = build_constructor (array_type, m_constructors[num]);
+      ctor = build_constructor (array_type, constructor);
       TREE_CONSTANT (ctor) = true;
       TREE_STATIC (ctor) = true;
 

Re: [PATCH] Use proper type in linear transformation in tree-switch-conversion (PR tree-optimization/88753).

[Jakub Jelinek]

On Tue, Jan 08, 2019 at 01:40:41PM +0100, Martin Liška wrote:
> As seen in the PR, when doing switch convert linear transformation,
> one needs to first convert to unsigned type for constructor values.
> 
> Patch survives regression tests and bootstrap on x86_64-linux-gnu.
> Ready for trunk?
> Thanks,
> Martin
> 
> 
> gcc/ChangeLog:
> 
> 2019-01-08  Martin Liska  <mliska@suse.cz>
> 
> 	PR tree-optimization/88753
> 	* tree-switch-conversion.c (switch_conversion::build_one_array):
> 	Come up with local variable constructor.  Convert first to
> 	type of constructor values.

Why is the testcase missing?

Otherwise LGTM.

Also, note contains_linear_function_p
  wide_int range_min = wi::to_wide (fold_convert (TREE_TYPE (elt0),
                                                  m_range_min));
could be written on wide_ints directly:
  wide_int range_min
    = wide_int::from (wi::to_wide (m_range_min),
		      TYPE_PRECISION (TREE_TYPE (elt0)),
		      TYPE_SIGN (TREE_TYPE (m_range_min)));

	Jakub

Re: [PATCH] Use proper type in linear transformation in tree-switch-conversion (PR tree-optimization/88753).

[Jakub Jelinek]

On Tue, Jan 08, 2019 at 01:52:35PM +0100, Jakub Jelinek wrote:
> > 2019-01-08  Martin Liska  <mliska@suse.cz>
> > 
> > 	PR tree-optimization/88753
> > 	* tree-switch-conversion.c (switch_conversion::build_one_array):
> > 	Come up with local variable constructor.  Convert first to
> > 	type of constructor values.
> 
> Why is the testcase missing?

Oh, one more thing.  What happens if the index is wider (higher precision)
than the type of the constructor elts?  At least for the two_value_replacement
optimization in phiopt, I'm using the wider of the two types for the
arithmetics (conditionally unsigned if not proven not to overflow).
Shouldn't that be the case in this optimization too?

With using just the constructor elt type, do you count on the analysis to
fail if starting with casting the index to the elt type (or unsigned variant
thereof) affects the computation?

	Jakub

Re: [PATCH] Use proper type in linear transformation in tree-switch-conversion (PR tree-optimization/88753).

[Martin Liška]

[-- Attachment #1: Type: text/plain, Size: 1254 bytes --]

On 1/8/19 1:52 PM, Jakub Jelinek wrote:
> On Tue, Jan 08, 2019 at 01:40:41PM +0100, Martin Liška wrote:
>> As seen in the PR, when doing switch convert linear transformation,
>> one needs to first convert to unsigned type for constructor values.
>>
>> Patch survives regression tests and bootstrap on x86_64-linux-gnu.
>> Ready for trunk?
>> Thanks,
>> Martin
>>
>>
>> gcc/ChangeLog:
>>
>> 2019-01-08  Martin Liska  <mliska@suse.cz>
>>
>> 	PR tree-optimization/88753
>> 	* tree-switch-conversion.c (switch_conversion::build_one_array):
>> 	Come up with local variable constructor.  Convert first to
>> 	type of constructor values.
> 
> Why is the testcase missing?

Because I forgot to call git add ;)

> 
> Otherwise LGTM.
> 
> Also, note contains_linear_function_p
>   wide_int range_min = wi::to_wide (fold_convert (TREE_TYPE (elt0),
>                                                   m_range_min));
> could be written on wide_ints directly:
>   wide_int range_min
>     = wide_int::from (wi::to_wide (m_range_min),
> 		      TYPE_PRECISION (TREE_TYPE (elt0)),
> 		      TYPE_SIGN (TREE_TYPE (m_range_min)));
> 
> 	Jakub
> 

Changed that. I verified that tree-ssa.exp tests work fine. May I install the hunk you suggested
without testing?

Martin

[-- Attachment #2: 0001-Use-proper-type-in-linear-transformation-in-tree-swi.patch --]
[-- Type: text/x-patch, Size: 4419 bytes --]

From 52f8961361f894cca35c616a38486f69c48c194c Mon Sep 17 00:00:00 2001
From: marxin <mliska@suse.cz>
Date: Tue, 8 Jan 2019 12:56:03 +0100
Subject: [PATCH] Use proper type in linear transformation in
 tree-switch-conversion (PR tree-optimization/88753).

gcc/ChangeLog:

2019-01-08  Martin Liska  <mliska@suse.cz>

	PR tree-optimization/88753
	* tree-switch-conversion.c (switch_conversion::build_one_array):
	Come up with local variable constructor.  Convert first to
	type of constructor values.

gcc/testsuite/ChangeLog:

2019-01-08  Martin Liska  <mliska@suse.cz>

	* gcc.dg/tree-ssa/pr88753.c: New test.
---
 gcc/testsuite/gcc.dg/tree-ssa/pr88753.c | 57 +++++++++++++++++++++++++
 gcc/tree-switch-conversion.c            | 17 +++++---
 2 files changed, 67 insertions(+), 7 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr88753.c

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr88753.c b/gcc/testsuite/gcc.dg/tree-ssa/pr88753.c
new file mode 100644
index 00000000000..eaefc38962f
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr88753.c
@@ -0,0 +1,57 @@
+/* PR tree-optimization/88753 */
+/* { dg-options "-O2 -fdump-tree-switchconv" } */
+/* { dg-do run { target nonpic } } */
+
+typedef unsigned short int uint16_t;
+typedef unsigned char uint8_t;
+
+uint16_t length;
+uint16_t enc_method_global;
+
+uint8_t
+__attribute__((noipa))
+_zip_buffer_get_8(int buffer)
+{
+  return buffer;
+}
+
+  int
+  __attribute__((noipa))
+foo(int v)
+{
+  uint16_t enc_method;
+  switch (_zip_buffer_get_8(v)) {
+    case 1:
+      enc_method = 0x0101;
+      break;
+    case 2:
+      enc_method = 0x0102;
+      break;
+    case 3:
+      enc_method = 0x0103;
+      break;
+    default:
+      __builtin_abort ();
+  }
+
+  enc_method_global = enc_method;
+}
+
+int main(int argc, char **argv)
+{
+  foo (1);
+  if (enc_method_global != 0x0101)
+    __builtin_abort ();
+
+  foo (2);
+  if (enc_method_global != 0x0102)
+    __builtin_abort ();
+
+  foo (3);
+  if (enc_method_global != 0x0103)
+    __builtin_abort ();
+
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "Linear transformation with A = 1 and B = 256" 1 "switchconv" } } */
diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c
index 614c450dd4d..c3f2baf39d7 100644
--- a/gcc/tree-switch-conversion.c
+++ b/gcc/tree-switch-conversion.c
@@ -473,8 +473,10 @@ switch_conversion::contains_linear_function_p (vec<constructor_elt, va_gc> *vec,
   if (TREE_CODE (elt0) != INTEGER_CST || TREE_CODE (elt1) != INTEGER_CST)
     return false;
 
-  wide_int range_min = wi::to_wide (fold_convert (TREE_TYPE (elt0),
-						  m_range_min));
+  wide_int range_min
+    = wide_int::from (wi::to_wide (m_range_min),
+		      TYPE_PRECISION (TREE_TYPE (elt0)),
+		      TYPE_SIGN (TREE_TYPE (m_range_min)));
   wide_int y1 = wi::to_wide (elt0);
   wide_int y2 = wi::to_wide (elt1);
   wide_int a = y2 - y1;
@@ -600,9 +602,9 @@ switch_conversion::build_one_array (int num, tree arr_index_type,
   name = copy_ssa_name (PHI_RESULT (phi));
   m_target_inbound_names[num] = name;
 
+  vec<constructor_elt, va_gc> *constructor = m_constructors[num];
   wide_int coeff_a, coeff_b;
-  bool linear_p = contains_linear_function_p (m_constructors[num], &coeff_a,
-					      &coeff_b);
+  bool linear_p = contains_linear_function_p (constructor, &coeff_a, &coeff_b);
   if (linear_p)
     {
       if (dump_file && coeff_a.to_uhwi () > 0)
@@ -610,7 +612,8 @@ switch_conversion::build_one_array (int num, tree arr_index_type,
 		 " and B = %" PRId64 "\n", coeff_a.to_shwi (),
 		 coeff_b.to_shwi ());
 
-      tree t = unsigned_type_for (TREE_TYPE (m_index_expr));
+      /* We must use type of constructor values.  */
+      tree t = unsigned_type_for (TREE_TYPE ((*constructor)[0].value));
       gimple_seq seq = NULL;
       tree tmp = gimple_convert (&seq, t, m_index_expr);
       tree tmp2 = gimple_build (&seq, MULT_EXPR, t,
@@ -633,10 +636,10 @@ switch_conversion::build_one_array (int num, tree arr_index_type,
 	  unsigned int i;
 	  constructor_elt *elt;
 
-	  FOR_EACH_VEC_SAFE_ELT (m_constructors[num], i, elt)
+	  FOR_EACH_VEC_SAFE_ELT (constructor, i, elt)
 	    elt->value = fold_convert (value_type, elt->value);
 	}
-      ctor = build_constructor (array_type, m_constructors[num]);
+      ctor = build_constructor (array_type, constructor);
       TREE_CONSTANT (ctor) = true;
       TREE_STATIC (ctor) = true;
 
-- 
2.20.1

Re: [PATCH] Use proper type in linear transformation in tree-switch-conversion (PR tree-optimization/88753).

[Jakub Jelinek]

On Tue, Jan 08, 2019 at 02:09:28PM +0100, Martin Liška wrote:
> Changed that. I verified that tree-ssa.exp tests work fine. May I install the hunk you suggested
> without testing?

I think better would be commit without that hunk and when you bootstrap next
time, test that and commit (preapproved) that hunk.

That said, have you looked at the other mail I've posted (TYPE_PRECISION
(index_type) > TYPE_PRECISION (elt0))?
The way contains_linear_function_p is written it does the checks in the type
that will do it at runtime, so I'm just wondering if there are cases where
doing it in the wider type could optimize something that the narrower one
can't.  Perhaps there are none.

	Jakub

Re: [PATCH] Use proper type in linear transformation in tree-switch-conversion (PR tree-optimization/88753).

[Martin Liška]

On 1/8/19 2:08 PM, Jakub Jelinek wrote:
> On Tue, Jan 08, 2019 at 01:52:35PM +0100, Jakub Jelinek wrote:
>>> 2019-01-08  Martin Liska  <mliska@suse.cz>
>>>
>>> 	PR tree-optimization/88753
>>> 	* tree-switch-conversion.c (switch_conversion::build_one_array):
>>> 	Come up with local variable constructor.  Convert first to
>>> 	type of constructor values.
>>
>> Why is the testcase missing?
> 
> Oh, one more thing.  What happens if the index is wider (higher precision)
> than the type of the constructor elts?  At least for the two_value_replacement
> optimization in phiopt, I'm using the wider of the two types for the
> arithmetics (conditionally unsigned if not proven not to overflow).
> Shouldn't that be the case in this optimization too?

I've been running for quite some GCC bootstrap with:

diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c
index c3f2baf39d7..c774350b497 100644
--- a/gcc/tree-switch-conversion.c
+++ b/gcc/tree-switch-conversion.c
@@ -100,6 +100,7 @@ switch_conversion::collect (gswitch *swtch)
   max_case = gimple_switch_label (swtch, branch_num - 1);
 
   m_range_min = CASE_LOW (min_case);
+  gcc_assert (operand_equal_p (TYPE_SIZE (TREE_TYPE (m_range_min)), TYPE_SIZE (TREE_TYPE (m_index_expr)), 0));
   if (CASE_HIGH (max_case) != NULL_TREE)
     m_range_max = CASE_HIGH (max_case);
   else

and I haven't triggered the assert.

> 
> With using just the constructor elt type, do you count on the analysis to
> fail if starting with casting the index to the elt type (or unsigned variant
> thereof) affects the computation?

So hopefully the situation can't happen. Note that if it happens we should not
generate wrong-code, but we miss an opportunity.

Martin

> 
> 	Jakub
> 

Re: [PATCH] Use proper type in linear transformation in tree-switch-conversion (PR tree-optimization/88753).

[Martin Liška]

On 1/8/19 2:50 PM, Jakub Jelinek wrote:
> On Tue, Jan 08, 2019 at 02:09:28PM +0100, Martin Liška wrote:
>> Changed that. I verified that tree-ssa.exp tests work fine. May I install the hunk you suggested
>> without testing?
> 
> I think better would be commit without that hunk and when you bootstrap next
> time, test that and commit (preapproved) that hunk.

I'll re-run the bootstrap with the hunk.

> 
> That said, have you looked at the other mail I've posted (TYPE_PRECISION
> (index_type) > TYPE_PRECISION (elt0))?
> The way contains_linear_function_p is written it does the checks in the type
> that will do it at runtime, so I'm just wondering if there are cases where
> doing it in the wider type could optimize something that the narrower one
> can't.  Perhaps there are none.

I replied that in previous email.

Martin

> 
> 	Jakub
> 

Re: [PATCH] Use proper type in linear transformation in tree-switch-conversion (PR tree-optimization/88753).

[Jakub Jelinek]

On Tue, Jan 08, 2019 at 02:56:44PM +0100, Martin Liška wrote:
> --- a/gcc/tree-switch-conversion.c
> +++ b/gcc/tree-switch-conversion.c
> @@ -100,6 +100,7 @@ switch_conversion::collect (gswitch *swtch)
>    max_case = gimple_switch_label (swtch, branch_num - 1);
>  
>    m_range_min = CASE_LOW (min_case);
> +  gcc_assert (operand_equal_p (TYPE_SIZE (TREE_TYPE (m_range_min)), TYPE_SIZE (TREE_TYPE (m_index_expr)), 0));
>    if (CASE_HIGH (max_case) != NULL_TREE)
>      m_range_max = CASE_HIGH (max_case);
>    else
> 
> and I haven't triggered the assert.
> 
> > 
> > With using just the constructor elt type, do you count on the analysis to
> > fail if starting with casting the index to the elt type (or unsigned variant
> > thereof) affects the computation?
> 
> So hopefully the situation can't happen. Note that if it happens we should not
> generate wrong-code, but we miss an opportunity.

The situation can happen very easily, just use
int foo (long long x) { int ret; switch (x) { case 1234567LL: ret = 123; break; ... } }

What I was wondering if doing the computation in the wider (index) type and then
casting to the narrower (ctor value) type could ever optimize something
that doing it on the narrower type can't.

Say, if index type is unsigned int and elt0 type is unsigned char, if
(a * i + b) % 256 could be the ctor sequence, but one couldn't find
c, d in [0, 255] that (c * (i % 256) + d) % 256 == (a * i + b) % 256.
But don't c = a % 256 and d = b % 256 satisfy that?

	Jakub

Re: [PATCH] Use proper type in linear transformation in tree-switch-conversion (PR tree-optimization/88753).

[Martin Liška]

On 1/8/19 3:14 PM, Jakub Jelinek wrote:
> On Tue, Jan 08, 2019 at 02:56:44PM +0100, Martin Liška wrote:
>> --- a/gcc/tree-switch-conversion.c
>> +++ b/gcc/tree-switch-conversion.c
>> @@ -100,6 +100,7 @@ switch_conversion::collect (gswitch *swtch)
>>    max_case = gimple_switch_label (swtch, branch_num - 1);
>>  
>>    m_range_min = CASE_LOW (min_case);
>> +  gcc_assert (operand_equal_p (TYPE_SIZE (TREE_TYPE (m_range_min)), TYPE_SIZE (TREE_TYPE (m_index_expr)), 0));
>>    if (CASE_HIGH (max_case) != NULL_TREE)
>>      m_range_max = CASE_HIGH (max_case);
>>    else
>>
>> and I haven't triggered the assert.
>>
>>>
>>> With using just the constructor elt type, do you count on the analysis to
>>> fail if starting with casting the index to the elt type (or unsigned variant
>>> thereof) affects the computation?
>>
>> So hopefully the situation can't happen. Note that if it happens we should not
>> generate wrong-code, but we miss an opportunity.
> 
> The situation can happen very easily, just use
> int foo (long long x) { int ret; switch (x) { case 1234567LL: ret = 123; break; ... } }
> 
> What I was wondering if doing the computation in the wider (index) type and then
> casting to the narrower (ctor value) type could ever optimize something
> that doing it on the narrower type can't.
> 
> Say, if index type is unsigned int and elt0 type is unsigned char, if
> (a * i + b) % 256 could be the ctor sequence, but one couldn't find
> c, d in [0, 255] that (c * (i % 256) + d) % 256 == (a * i + b) % 256.
> But don't c = a % 256 and d = b % 256 satisfy that?

Yep, that can be an improvement. I can return to it in next stage1.

Martin

> 
> 	Jakub
> 

Re: [PATCH] Use proper type in linear transformation in tree-switch-conversion (PR tree-optimization/88753).

[Martin Liška]

On 1/8/19 2:57 PM, Martin Liška wrote:
> I'll re-run the bootstrap with the hunk.

Bootstraps&regtests, thus I'm going to install it.

Martin