* [PATCH] Use proper type in linear transformation in tree-switch-conversion (PR tree-optimization/88753). @ 2019-01-08 12:40 Martin Liška 2019-01-08 12:52 ` Jakub Jelinek 0 siblings, 1 reply; 10+ messages in thread From: Martin Liška @ 2019-01-08 12:40 UTC (permalink / raw) To: gcc-patches; +Cc: Jakub Jelinek [-- 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; ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH] Use proper type in linear transformation in tree-switch-conversion (PR tree-optimization/88753). 2019-01-08 12:40 [PATCH] Use proper type in linear transformation in tree-switch-conversion (PR tree-optimization/88753) Martin Liška @ 2019-01-08 12:52 ` Jakub Jelinek 2019-01-08 13:08 ` Jakub Jelinek 2019-01-08 13:09 ` Martin Liška 0 siblings, 2 replies; 10+ messages in thread From: Jakub Jelinek @ 2019-01-08 12:52 UTC (permalink / raw) To: Martin Liška; +Cc: gcc-patches 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH] Use proper type in linear transformation in tree-switch-conversion (PR tree-optimization/88753). 2019-01-08 12:52 ` Jakub Jelinek @ 2019-01-08 13:08 ` Jakub Jelinek 2019-01-08 13:56 ` Martin Liška 2019-01-08 13:09 ` Martin Liška 1 sibling, 1 reply; 10+ messages in thread From: Jakub Jelinek @ 2019-01-08 13:08 UTC (permalink / raw) To: Martin Liška; +Cc: gcc-patches 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH] Use proper type in linear transformation in tree-switch-conversion (PR tree-optimization/88753). 2019-01-08 13:08 ` Jakub Jelinek @ 2019-01-08 13:56 ` Martin Liška 2019-01-08 14:15 ` Jakub Jelinek 0 siblings, 1 reply; 10+ messages in thread From: Martin Liška @ 2019-01-08 13:56 UTC (permalink / raw) To: Jakub Jelinek; +Cc: gcc-patches 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 > ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH] Use proper type in linear transformation in tree-switch-conversion (PR tree-optimization/88753). 2019-01-08 13:56 ` Martin Liška @ 2019-01-08 14:15 ` Jakub Jelinek 2019-01-08 14:25 ` Martin Liška 0 siblings, 1 reply; 10+ messages in thread From: Jakub Jelinek @ 2019-01-08 14:15 UTC (permalink / raw) To: Martin Liška; +Cc: gcc-patches 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH] Use proper type in linear transformation in tree-switch-conversion (PR tree-optimization/88753). 2019-01-08 14:15 ` Jakub Jelinek @ 2019-01-08 14:25 ` Martin Liška 0 siblings, 0 replies; 10+ messages in thread From: Martin Liška @ 2019-01-08 14:25 UTC (permalink / raw) To: Jakub Jelinek; +Cc: gcc-patches 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 > ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH] Use proper type in linear transformation in tree-switch-conversion (PR tree-optimization/88753). 2019-01-08 12:52 ` Jakub Jelinek 2019-01-08 13:08 ` Jakub Jelinek @ 2019-01-08 13:09 ` Martin Liška 2019-01-08 13:50 ` Jakub Jelinek 1 sibling, 1 reply; 10+ messages in thread From: Martin Liška @ 2019-01-08 13:09 UTC (permalink / raw) To: Jakub Jelinek; +Cc: gcc-patches [-- 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH] Use proper type in linear transformation in tree-switch-conversion (PR tree-optimization/88753). 2019-01-08 13:09 ` Martin Liška @ 2019-01-08 13:50 ` Jakub Jelinek 2019-01-08 13:57 ` Martin Liška 0 siblings, 1 reply; 10+ messages in thread From: Jakub Jelinek @ 2019-01-08 13:50 UTC (permalink / raw) To: Martin Liška; +Cc: gcc-patches 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH] Use proper type in linear transformation in tree-switch-conversion (PR tree-optimization/88753). 2019-01-08 13:50 ` Jakub Jelinek @ 2019-01-08 13:57 ` Martin Liška 2019-01-08 14:41 ` Martin Liška 0 siblings, 1 reply; 10+ messages in thread From: Martin Liška @ 2019-01-08 13:57 UTC (permalink / raw) To: Jakub Jelinek; +Cc: gcc-patches 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 > ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH] Use proper type in linear transformation in tree-switch-conversion (PR tree-optimization/88753). 2019-01-08 13:57 ` Martin Liška @ 2019-01-08 14:41 ` Martin Liška 0 siblings, 0 replies; 10+ messages in thread From: Martin Liška @ 2019-01-08 14:41 UTC (permalink / raw) To: Jakub Jelinek; +Cc: gcc-patches On 1/8/19 2:57 PM, Martin LiÅ¡ka wrote: > I'll re-run the bootstrap with the hunk. Bootstraps®tests, thus I'm going to install it. Martin ^ permalink raw reply [flat|nested] 10+ messages in thread
end of thread, other threads:[~2019-01-08 14:41 UTC | newest] Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2019-01-08 12:40 [PATCH] Use proper type in linear transformation in tree-switch-conversion (PR tree-optimization/88753) Martin Liška 2019-01-08 12:52 ` Jakub Jelinek 2019-01-08 13:08 ` Jakub Jelinek 2019-01-08 13:56 ` Martin Liška 2019-01-08 14:15 ` Jakub Jelinek 2019-01-08 14:25 ` Martin Liška 2019-01-08 13:09 ` Martin Liška 2019-01-08 13:50 ` Jakub Jelinek 2019-01-08 13:57 ` Martin Liška 2019-01-08 14:41 ` Martin Liška
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).