ssa_name_has_boolean_range vs signed-boolean:31 types

  This turns out to be a latent bug in ssa_name_has_boolean_range
where it would return true for all boolean types but all of the
uses of ssa_name_has_boolean_range was expecting 0/1 as the range
rather than [-1,0].
So when I fixed vector lower to do all comparisons in boolean_type
rather than still in the signed-boolean:31 type (to fix a different issue),
the pattern in match for `-(type)!A -> (type)A - 1.` would assume A (which
was signed-boolean:31) had a range of [0,1] which broke down and sometimes
gave us -1/-2 as values rather than what we were expecting of -1/0.

This was the simpliest patch I found while testing.

We have another way of matching [0,1] range which we could use instead
of ssa_name_has_boolean_range except that uses only the global ranges
rather than the local range (during VRP).
I tried to clean this up slightly by using gimple_match_zero_one_valuedp
inside ssa_name_has_boolean_range but that failed because due to using
only the global ranges. I then tried to change get_nonzero_bits to use
the local ranges at the optimization time but that failed also because
we would remove branches to __builtin_unreachable during evrp and lose
information as we don't set the global ranges during evrp.

OK? Bootstrapped and tested on x86_64-linux-gnu.

	PR 110817

gcc/ChangeLog:

	* tree-ssanames.cc (ssa_name_has_boolean_range): Remove the
	check for boolean type as they don't have "[0,1]" range.

gcc/testsuite/ChangeLog:

	* gcc.c-torture/execute/pr110817-1.c: New test.
	* gcc.c-torture/execute/pr110817-2.c: New test.
	* gcc.c-torture/execute/pr110817-3.c: New test.
---
 gcc/testsuite/gcc.c-torture/execute/pr110817-1.c | 13 +++++++++++++
 gcc/testsuite/gcc.c-torture/execute/pr110817-2.c | 16 ++++++++++++++++
 gcc/testsuite/gcc.c-torture/execute/pr110817-3.c | 14 ++++++++++++++
 gcc/tree-ssanames.cc                             |  4 ----
 4 files changed, 43 insertions(+), 4 deletions(-)
 create mode 100644 gcc/testsuite/gcc.c-torture/execute/pr110817-1.c
 create mode 100644 gcc/testsuite/gcc.c-torture/execute/pr110817-2.c
 create mode 100644 gcc/testsuite/gcc.c-torture/execute/pr110817-3.c
  

On 9/1/23 20:32, Andrew Pinski via Gcc-patches wrote:
> This turns out to be a latent bug in ssa_name_has_boolean_range
> where it would return true for all boolean types but all of the
> uses of ssa_name_has_boolean_range was expecting 0/1 as the range
> rather than [-1,0].
> So when I fixed vector lower to do all comparisons in boolean_type
> rather than still in the signed-boolean:31 type (to fix a different issue),
> the pattern in match for `-(type)!A -> (type)A - 1.` would assume A (which
> was signed-boolean:31) had a range of [0,1] which broke down and sometimes
> gave us -1/-2 as values rather than what we were expecting of -1/0.
> 
> This was the simpliest patch I found while testing.
> 
> We have another way of matching [0,1] range which we could use instead
> of ssa_name_has_boolean_range except that uses only the global ranges
> rather than the local range (during VRP).
> I tried to clean this up slightly by using gimple_match_zero_one_valuedp
> inside ssa_name_has_boolean_range but that failed because due to using
> only the global ranges. I then tried to change get_nonzero_bits to use
> the local ranges at the optimization time but that failed also because
> we would remove branches to __builtin_unreachable during evrp and lose
> information as we don't set the global ranges during evrp.
> 
> OK? Bootstrapped and tested on x86_64-linux-gnu.
> 
> 	PR 110817
> 
> gcc/ChangeLog:
> 
> 	* tree-ssanames.cc (ssa_name_has_boolean_range): Remove the
> 	check for boolean type as they don't have "[0,1]" range.
> 
> gcc/testsuite/ChangeLog:
> 
> 	* gcc.c-torture/execute/pr110817-1.c: New test.
> 	* gcc.c-torture/execute/pr110817-2.c: New test.
> 	* gcc.c-torture/execute/pr110817-3.c: New test.
I'm a bit surprised this didn't trigger any regressions.  Though maybe 
all the existing testcases were capturing cases where non-boolean types 
were known to have a 0/1 value.


OK.
jeff
  

On Tue, Sep 5, 2023 at 12:09 AM Jeff Law via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
>
>
> On 9/1/23 20:32, Andrew Pinski via Gcc-patches wrote:
> > This turns out to be a latent bug in ssa_name_has_boolean_range
> > where it would return true for all boolean types but all of the
> > uses of ssa_name_has_boolean_range was expecting 0/1 as the range
> > rather than [-1,0].
> > So when I fixed vector lower to do all comparisons in boolean_type
> > rather than still in the signed-boolean:31 type (to fix a different issue),
> > the pattern in match for `-(type)!A -> (type)A - 1.` would assume A (which
> > was signed-boolean:31) had a range of [0,1] which broke down and sometimes
> > gave us -1/-2 as values rather than what we were expecting of -1/0.
> >
> > This was the simpliest patch I found while testing.
> >
> > We have another way of matching [0,1] range which we could use instead
> > of ssa_name_has_boolean_range except that uses only the global ranges
> > rather than the local range (during VRP).
> > I tried to clean this up slightly by using gimple_match_zero_one_valuedp
> > inside ssa_name_has_boolean_range but that failed because due to using
> > only the global ranges. I then tried to change get_nonzero_bits to use
> > the local ranges at the optimization time but that failed also because
> > we would remove branches to __builtin_unreachable during evrp and lose
> > information as we don't set the global ranges during evrp.
> >
> > OK? Bootstrapped and tested on x86_64-linux-gnu.
> >
> >       PR 110817
> >
> > gcc/ChangeLog:
> >
> >       * tree-ssanames.cc (ssa_name_has_boolean_range): Remove the
> >       check for boolean type as they don't have "[0,1]" range.
> >
> > gcc/testsuite/ChangeLog:
> >
> >       * gcc.c-torture/execute/pr110817-1.c: New test.
> >       * gcc.c-torture/execute/pr110817-2.c: New test.
> >       * gcc.c-torture/execute/pr110817-3.c: New test.
> I'm a bit surprised this didn't trigger any regressions.  Though maybe
> all the existing testcases were capturing cases where non-boolean types
> were known to have a 0/1 value.

Well except ssa_name_has_boolean_range will return true for `An
[unsigned] integral type with a single bit of precision` which the
normal boolean type for C is. So the only case where this makes a
difference is signed booleans. Vectors and Ada are the only 2 places I
know of which use signed booleans even.

This came up before too;
https://inbox.sourceware.org/gcc-patches/CAFiYyc23ZMEvy6i9g1WpmPP7purcUzatG1QpwF2D_8n6F22QHQ@mail.gmail.com/
.
Anyways the 3 uses of ssa_name_has_boolean_range in match.pd are:
 /* X / bool_range_Y is X.  */
which is not true for signed booleans; though division for boolean
types is not well defined
/* 1 - a is a ^ 1 if a had a bool range. */
Which is broken for signed booleans; though it might not show up in IR
for non 1-bit boolean types.
/* -(type)!A -> (type)A - 1.  */
 This one 100 % requires `A` and `A == 0` to be [0,1] range.

The other uses of ssa_name_has_boolean_range are in DOM.
The first 2 uses of ssa_name_has_boolean_range use
build_one_cst/build_one_cst which is definitely wrong there. should
have been constant_boolean_node for N-bit signed boolean types.
The use `A COND_EXPR may create equivalences too.` actually does the
correct thing and uses constant_boolean_node.

Now maybe we miss some optimizations with Ada code with this change; I
am not 100% sure. Maybe the change should just add && TYPE_UNSIGNED
(type) to the check of boolean type and that will fix the issue too.

>
>
> OK.
> jeff
  

On Sat, Sep 2, 2023 at 4:33 AM Andrew Pinski via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> This turns out to be a latent bug in ssa_name_has_boolean_range
> where it would return true for all boolean types but all of the
> uses of ssa_name_has_boolean_range was expecting 0/1 as the range
> rather than [-1,0].
> So when I fixed vector lower to do all comparisons in boolean_type
> rather than still in the signed-boolean:31 type (to fix a different issue),
> the pattern in match for `-(type)!A -> (type)A - 1.` would assume A (which
> was signed-boolean:31) had a range of [0,1] which broke down and sometimes
> gave us -1/-2 as values rather than what we were expecting of -1/0.
>
> This was the simpliest patch I found while testing.
>
> We have another way of matching [0,1] range which we could use instead
> of ssa_name_has_boolean_range except that uses only the global ranges
> rather than the local range (during VRP).
> I tried to clean this up slightly by using gimple_match_zero_one_valuedp
> inside ssa_name_has_boolean_range but that failed because due to using
> only the global ranges. I then tried to change get_nonzero_bits to use
> the local ranges at the optimization time but that failed also because
> we would remove branches to __builtin_unreachable during evrp and lose
> information as we don't set the global ranges during evrp.
>
> OK? Bootstrapped and tested on x86_64-linux-gnu.

I guess the name of 'ssa_name_has_boolean_range' is unfortunate here.

We also lack documenting BOOLEAN_TYPE with [-1,0], neither tree.def
nor generic.texi elaborate on those.  build_nonstandard_boolean_type
simply calls fixup_signed_type which will end up setting MIN/MAX value
to [INT_MIN, INT_MAX].

Iff ssa_name_has_boolean_range really checks for zero_one we should
maybe rename it.

Iff _all_ signed BOOLEAN_TYPE have a true value of -1 (signed:8 can
very well represent [0, 1] as well) then we should document that.  (No,
I don't think we want TYPE_MIN/MAX_VALUE to specify this)

At some point the middle-end was very conservative and only considered
unsigned BOOLEAN_TYPE with 1 bit precision to have a [0,1] range.

I think that a more general 'boolean range' (not [0, 1]) query is only
possible if we hand in context.

The patch is definitely correct - not all BOOLEAN_TYPE types have a [0, 1]
range, thus OK.

Does Ada have signed booleans that are BOOLEAN_TYPE but do _not_
have [-1, 0] as range?  I think documenting [0, 1] for (single-bit precision?)
unsigned BOOLEAN_TYPE and [-1, 1] for signed BOOLEAN_TYPE would
be conservative.

Thanks,
Richard.

>         PR 110817
>
> gcc/ChangeLog:
>
>         * tree-ssanames.cc (ssa_name_has_boolean_range): Remove the
>         check for boolean type as they don't have "[0,1]" range.
>
> gcc/testsuite/ChangeLog:
>
>         * gcc.c-torture/execute/pr110817-1.c: New test.
>         * gcc.c-torture/execute/pr110817-2.c: New test.
>         * gcc.c-torture/execute/pr110817-3.c: New test.
> ---
>  gcc/testsuite/gcc.c-torture/execute/pr110817-1.c | 13 +++++++++++++
>  gcc/testsuite/gcc.c-torture/execute/pr110817-2.c | 16 ++++++++++++++++
>  gcc/testsuite/gcc.c-torture/execute/pr110817-3.c | 14 ++++++++++++++
>  gcc/tree-ssanames.cc                             |  4 ----
>  4 files changed, 43 insertions(+), 4 deletions(-)
>  create mode 100644 gcc/testsuite/gcc.c-torture/execute/pr110817-1.c
>  create mode 100644 gcc/testsuite/gcc.c-torture/execute/pr110817-2.c
>  create mode 100644 gcc/testsuite/gcc.c-torture/execute/pr110817-3.c
>
> diff --git a/gcc/testsuite/gcc.c-torture/execute/pr110817-1.c b/gcc/testsuite/gcc.c-torture/execute/pr110817-1.c
> new file mode 100644
> index 00000000000..1d33fa9a207
> --- /dev/null
> +++ b/gcc/testsuite/gcc.c-torture/execute/pr110817-1.c
> @@ -0,0 +1,13 @@
> +typedef unsigned long __attribute__((__vector_size__ (8))) V;
> +
> +
> +V c;
> +
> +int
> +main (void)
> +{
> +  V v = ~((V) { } <=0);
> +  if (v[0])
> +    __builtin_abort ();
> +  return 0;
> +}
> diff --git a/gcc/testsuite/gcc.c-torture/execute/pr110817-2.c b/gcc/testsuite/gcc.c-torture/execute/pr110817-2.c
> new file mode 100644
> index 00000000000..1f759178425
> --- /dev/null
> +++ b/gcc/testsuite/gcc.c-torture/execute/pr110817-2.c
> @@ -0,0 +1,16 @@
> +
> +typedef unsigned char u8;
> +typedef unsigned __attribute__((__vector_size__ (8))) V;
> +
> +V v;
> +unsigned char c;
> +
> +int
> +main (void)
> +{
> +  V x = (v > 0) > (v != c);
> + // V x = foo ();
> +  if (x[0] || x[1])
> +    __builtin_abort ();
> +  return 0;
> +}
> diff --git a/gcc/testsuite/gcc.c-torture/execute/pr110817-3.c b/gcc/testsuite/gcc.c-torture/execute/pr110817-3.c
> new file mode 100644
> index 00000000000..36f09c88dd9
> --- /dev/null
> +++ b/gcc/testsuite/gcc.c-torture/execute/pr110817-3.c
> @@ -0,0 +1,14 @@
> +typedef unsigned __attribute__((__vector_size__ (1*sizeof(unsigned)))) V;
> +
> +V v;
> +unsigned char c;
> +
> +int
> +main (void)
> +{
> +  V x = (v > 0) > (v != c);
> +  volatile signed int t = x[0];
> +  if (t)
> +    __builtin_abort ();
> +  return 0;
> +}
> diff --git a/gcc/tree-ssanames.cc b/gcc/tree-ssanames.cc
> index 23387b90fe3..6c362995c1a 100644
> --- a/gcc/tree-ssanames.cc
> +++ b/gcc/tree-ssanames.cc
> @@ -521,10 +521,6 @@ ssa_name_has_boolean_range (tree op)
>  {
>    gcc_assert (TREE_CODE (op) == SSA_NAME);
>
> -  /* Boolean types always have a range [0..1].  */
> -  if (TREE_CODE (TREE_TYPE (op)) == BOOLEAN_TYPE)
> -    return true;
> -
>    /* An integral type with a single bit of precision.  */
>    if (INTEGRAL_TYPE_P (TREE_TYPE (op))
>        && TYPE_UNSIGNED (TREE_TYPE (op))
> --
> 2.31.1
>
  

> Does Ada have signed booleans that are BOOLEAN_TYPE but do _not_
> have [-1, 0] as range?  I think documenting [0, 1] for (single-bit
> precision?) unsigned BOOLEAN_TYPE and [-1, 1] for signed BOOLEAN_TYPE would
> be conservative.

All BOOLEAN_TYPEs are unsigned in Ada but may have precision > 1, typically 8.
  

On 9/5/23 01:46, Andrew Pinski wrote:
> On Tue, Sep 5, 2023 at 12:09 AM Jeff Law via Gcc-patches
> <gcc-patches@gcc.gnu.org> wrote:
>>
>>
>>
>> On 9/1/23 20:32, Andrew Pinski via Gcc-patches wrote:
>>> This turns out to be a latent bug in ssa_name_has_boolean_range
>>> where it would return true for all boolean types but all of the
>>> uses of ssa_name_has_boolean_range was expecting 0/1 as the range
>>> rather than [-1,0].
>>> So when I fixed vector lower to do all comparisons in boolean_type
>>> rather than still in the signed-boolean:31 type (to fix a different issue),
>>> the pattern in match for `-(type)!A -> (type)A - 1.` would assume A (which
>>> was signed-boolean:31) had a range of [0,1] which broke down and sometimes
>>> gave us -1/-2 as values rather than what we were expecting of -1/0.
>>>
>>> This was the simpliest patch I found while testing.
>>>
>>> We have another way of matching [0,1] range which we could use instead
>>> of ssa_name_has_boolean_range except that uses only the global ranges
>>> rather than the local range (during VRP).
>>> I tried to clean this up slightly by using gimple_match_zero_one_valuedp
>>> inside ssa_name_has_boolean_range but that failed because due to using
>>> only the global ranges. I then tried to change get_nonzero_bits to use
>>> the local ranges at the optimization time but that failed also because
>>> we would remove branches to __builtin_unreachable during evrp and lose
>>> information as we don't set the global ranges during evrp.
>>>
>>> OK? Bootstrapped and tested on x86_64-linux-gnu.
>>>
>>>        PR 110817
>>>
>>> gcc/ChangeLog:
>>>
>>>        * tree-ssanames.cc (ssa_name_has_boolean_range): Remove the
>>>        check for boolean type as they don't have "[0,1]" range.
>>>
>>> gcc/testsuite/ChangeLog:
>>>
>>>        * gcc.c-torture/execute/pr110817-1.c: New test.
>>>        * gcc.c-torture/execute/pr110817-2.c: New test.
>>>        * gcc.c-torture/execute/pr110817-3.c: New test.
>> I'm a bit surprised this didn't trigger any regressions.  Though maybe
>> all the existing testcases were capturing cases where non-boolean types
>> were known to have a 0/1 value.
> 
> Well except ssa_name_has_boolean_range will return true for `An
> [unsigned] integral type with a single bit of precision` which the
> normal boolean type for C is. So the only case where this makes a
> difference is signed booleans. Vectors and Ada are the only 2 places I
> know of which use signed booleans even.
Ah.  That would explain things well.  When we added that stuff we were 
mostly focused on cases that would have fallen under unsigned integral 
types with a single bit of precision.



> 
> The other uses of ssa_name_has_boolean_range are in DOM.
Right.  That was the original client of this code.

> The first 2 uses of ssa_name_has_boolean_range use
> build_one_cst/build_one_cst which is definitely wrong there. should
> have been constant_boolean_node for N-bit signed boolean types.
ACK.  Feel free to fix these.  Consider it pre-approved if it passes 
testing.



jeff