[PATCH] Checking undefined_p before using the vr

[PATCH] Checking undefined_p before using the vr

[Jiufu Guo]

Hi,

As discussed in PR111303:

For pattern "(X + C) / N": "div (plus@3 @0 INTEGER_CST@1) INTEGER_CST@2)",
Even if "X" has value-range and "X + C" does not overflow, "@3" may still
be undefined. Like below example:

_3 = _2 + -5;
if (0 != 0)
  goto <bb 3>; [34.00%]
else
  goto <bb 4>; [66.00%]
;;  succ:       3
;;              4

;; basic block 3, loop depth 0
;;  pred:       2
_5 = _3 / 5; 
;;  succ:       4

The whole pattern "(_2 + -5 ) / 5" is in "bb 3", but "bb 3" would be
unreachable (because "if (0 != 0)" is always false).
And "get_range_query (cfun)->range_of_expr (vr3, @3)" is checked in
"bb 3", "range_of_expr" gets an "undefined vr3". Where "@3" is "_5".

So, before using "vr3", it would be safe to check "!vr3.undefined_p ()".

Bootstrap & regtest pass on ppc64{,le} and x86_64.
Is this ok for trunk?

BR,
Jeff (Jiufu Guo)

	PR middle-end/111303

gcc/ChangeLog:

	* match.pd ((X - N * M) / N): Add undefined_p checking.
	(X + N * M) / N): Likewise.
	((X + C) div_rshift N): Likewise.

gcc/testsuite/ChangeLog:

	* gcc.dg/pr111303.c: New test.

---
 gcc/match.pd                    |  3 +++
 gcc/testsuite/gcc.dg/pr111303.c | 11 +++++++++++
 2 files changed, 14 insertions(+)
 create mode 100644 gcc/testsuite/gcc.dg/pr111303.c

diff --git a/gcc/match.pd b/gcc/match.pd
index 801edb128f9..e2583ca7960 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -975,6 +975,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
        /* "X+(N*M)" doesn't overflow.  */
        && range_op_handler (PLUS_EXPR).overflow_free_p (vr0, vr3)
        && get_range_query (cfun)->range_of_expr (vr4, @4)
+       && !vr4.undefined_p ()
        /* "X+N*M" is not with opposite sign as "X".  */
        && (TYPE_UNSIGNED (type)
 	   || (vr0.nonnegative_p () && vr4.nonnegative_p ())
@@ -995,6 +996,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
        /* "X - (N*M)" doesn't overflow.  */
        && range_op_handler (MINUS_EXPR).overflow_free_p (vr0, vr3)
        && get_range_query (cfun)->range_of_expr (vr4, @4)
+       && !vr4.undefined_p ()
        /* "X-N*M" is not with opposite sign as "X".  */
        && (TYPE_UNSIGNED (type)
 	   || (vr0.nonnegative_p () && vr4.nonnegative_p ())
@@ -1025,6 +1027,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
 	  /* "X+C" doesn't overflow.  */
 	  && range_op_handler (PLUS_EXPR).overflow_free_p (vr0, vr1)
 	  && get_range_query (cfun)->range_of_expr (vr3, @3)
+	  && !vr3.undefined_p ()
 	  /* "X+C" and "X" are not of opposite sign.  */
 	  && (TYPE_UNSIGNED (type)
 	      || (vr0.nonnegative_p () && vr3.nonnegative_p ())
diff --git a/gcc/testsuite/gcc.dg/pr111303.c b/gcc/testsuite/gcc.dg/pr111303.c
new file mode 100644
index 00000000000..eaabe55c105
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr111303.c
@@ -0,0 +1,11 @@
+/* { dg-do compile } */
+/* { dg-options "-O2" } */
+
+/* Make sure no ICE. */
+unsigned char a;
+int b(int c) {
+  if (c >= 5000)
+    return c / 5;
+}
+void d() { b(a - 5); }
+int main() {}
-- 
2.25.1

Re: [PATCH] Checking undefined_p before using the vr

[Richard Biener]

On Thu, 7 Sep 2023, Jiufu Guo wrote:

> Hi,
> 
> As discussed in PR111303:
> 
> For pattern "(X + C) / N": "div (plus@3 @0 INTEGER_CST@1) INTEGER_CST@2)",
> Even if "X" has value-range and "X + C" does not overflow, "@3" may still
> be undefined. Like below example:
> 
> _3 = _2 + -5;
> if (0 != 0)
>   goto <bb 3>; [34.00%]
> else
>   goto <bb 4>; [66.00%]
> ;;  succ:       3
> ;;              4
> 
> ;; basic block 3, loop depth 0
> ;;  pred:       2
> _5 = _3 / 5; 
> ;;  succ:       4
> 
> The whole pattern "(_2 + -5 ) / 5" is in "bb 3", but "bb 3" would be
> unreachable (because "if (0 != 0)" is always false).
> And "get_range_query (cfun)->range_of_expr (vr3, @3)" is checked in
> "bb 3", "range_of_expr" gets an "undefined vr3". Where "@3" is "_5".
> 
> So, before using "vr3", it would be safe to check "!vr3.undefined_p ()".
> 
> Bootstrap & regtest pass on ppc64{,le} and x86_64.
> Is this ok for trunk?

OK, but I wonder why ->range_of_expr () doesn't return false for
undefined_p ()?  While "undefined" technically means we can treat
it as nonnegative_p (or not, maybe but maybe not both), we seem to
not want to do that.  So why expose it at all to ranger users
(yes, internally we in some places want to handle undefined).

Richard.

> BR,
> Jeff (Jiufu Guo)
> 
> 	PR middle-end/111303
> 
> gcc/ChangeLog:
> 
> 	* match.pd ((X - N * M) / N): Add undefined_p checking.
> 	(X + N * M) / N): Likewise.
> 	((X + C) div_rshift N): Likewise.
> 
> gcc/testsuite/ChangeLog:
> 
> 	* gcc.dg/pr111303.c: New test.
> 
> ---
>  gcc/match.pd                    |  3 +++
>  gcc/testsuite/gcc.dg/pr111303.c | 11 +++++++++++
>  2 files changed, 14 insertions(+)
>  create mode 100644 gcc/testsuite/gcc.dg/pr111303.c
> 
> diff --git a/gcc/match.pd b/gcc/match.pd
> index 801edb128f9..e2583ca7960 100644
> --- a/gcc/match.pd
> +++ b/gcc/match.pd
> @@ -975,6 +975,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>         /* "X+(N*M)" doesn't overflow.  */
>         && range_op_handler (PLUS_EXPR).overflow_free_p (vr0, vr3)
>         && get_range_query (cfun)->range_of_expr (vr4, @4)
> +       && !vr4.undefined_p ()
>         /* "X+N*M" is not with opposite sign as "X".  */
>         && (TYPE_UNSIGNED (type)
>  	   || (vr0.nonnegative_p () && vr4.nonnegative_p ())
> @@ -995,6 +996,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>         /* "X - (N*M)" doesn't overflow.  */
>         && range_op_handler (MINUS_EXPR).overflow_free_p (vr0, vr3)
>         && get_range_query (cfun)->range_of_expr (vr4, @4)
> +       && !vr4.undefined_p ()
>         /* "X-N*M" is not with opposite sign as "X".  */
>         && (TYPE_UNSIGNED (type)
>  	   || (vr0.nonnegative_p () && vr4.nonnegative_p ())
> @@ -1025,6 +1027,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>  	  /* "X+C" doesn't overflow.  */
>  	  && range_op_handler (PLUS_EXPR).overflow_free_p (vr0, vr1)
>  	  && get_range_query (cfun)->range_of_expr (vr3, @3)
> +	  && !vr3.undefined_p ()
>  	  /* "X+C" and "X" are not of opposite sign.  */
>  	  && (TYPE_UNSIGNED (type)
>  	      || (vr0.nonnegative_p () && vr3.nonnegative_p ())
> diff --git a/gcc/testsuite/gcc.dg/pr111303.c b/gcc/testsuite/gcc.dg/pr111303.c
> new file mode 100644
> index 00000000000..eaabe55c105
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/pr111303.c
> @@ -0,0 +1,11 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2" } */
> +
> +/* Make sure no ICE. */
> +unsigned char a;
> +int b(int c) {
> +  if (c >= 5000)
> +    return c / 5;
> +}
> +void d() { b(a - 5); }
> +int main() {}
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE Software Solutions Germany GmbH,
Frankenstrasse 146, 90461 Nuernberg, Germany;
GF: Ivo Totev, Andrew McDonald, Werner Knoblich; (HRB 36809, AG Nuernberg)

Re: [PATCH] Checking undefined_p before using the vr

[Jiufu Guo]

Hi,

Richard Biener <rguenther@suse.de> writes:

> On Thu, 7 Sep 2023, Jiufu Guo wrote:
>
>> Hi,
>> 
>> As discussed in PR111303:
>> 
>> For pattern "(X + C) / N": "div (plus@3 @0 INTEGER_CST@1) INTEGER_CST@2)",
>> Even if "X" has value-range and "X + C" does not overflow, "@3" may still
>> be undefined. Like below example:
>> 
>> _3 = _2 + -5;
>> if (0 != 0)
>>   goto <bb 3>; [34.00%]
>> else
>>   goto <bb 4>; [66.00%]
>> ;;  succ:       3
>> ;;              4
>> 
>> ;; basic block 3, loop depth 0
>> ;;  pred:       2
>> _5 = _3 / 5; 
>> ;;  succ:       4
>> 
>> The whole pattern "(_2 + -5 ) / 5" is in "bb 3", but "bb 3" would be
>> unreachable (because "if (0 != 0)" is always false).
>> And "get_range_query (cfun)->range_of_expr (vr3, @3)" is checked in
>> "bb 3", "range_of_expr" gets an "undefined vr3". Where "@3" is "_5".
>> 
>> So, before using "vr3", it would be safe to check "!vr3.undefined_p ()".
>> 
>> Bootstrap & regtest pass on ppc64{,le} and x86_64.
>> Is this ok for trunk?
>
> OK, but I wonder why ->range_of_expr () doesn't return false for
> undefined_p ()?  While "undefined" technically means we can treat
> it as nonnegative_p (or not, maybe but maybe not both), we seem to
> not want to do that.  So why expose it at all to ranger users
> (yes, internally we in some places want to handle undefined).

I guess, currently, it returns true and then lets the user check
undefined_p, maybe because it tries to only return false if the
type of EXPR is unsupported.

Let "range_of_expr" return false for undefined_p would save checking
undefined_p again when using the APIs.

Committed va r14-3913.

BR,
Jeff (Jiufu Guo)

>
> Richard.
>
>> BR,
>> Jeff (Jiufu Guo)
>> 
>> 	PR middle-end/111303
>> 
>> gcc/ChangeLog:
>> 
>> 	* match.pd ((X - N * M) / N): Add undefined_p checking.
>> 	(X + N * M) / N): Likewise.
>> 	((X + C) div_rshift N): Likewise.
>> 
>> gcc/testsuite/ChangeLog:
>> 
>> 	* gcc.dg/pr111303.c: New test.
>> 
>> ---
>>  gcc/match.pd                    |  3 +++
>>  gcc/testsuite/gcc.dg/pr111303.c | 11 +++++++++++
>>  2 files changed, 14 insertions(+)
>>  create mode 100644 gcc/testsuite/gcc.dg/pr111303.c
>> 
>> diff --git a/gcc/match.pd b/gcc/match.pd
>> index 801edb128f9..e2583ca7960 100644
>> --- a/gcc/match.pd
>> +++ b/gcc/match.pd
>> @@ -975,6 +975,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>>         /* "X+(N*M)" doesn't overflow.  */
>>         && range_op_handler (PLUS_EXPR).overflow_free_p (vr0, vr3)
>>         && get_range_query (cfun)->range_of_expr (vr4, @4)
>> +       && !vr4.undefined_p ()
>>         /* "X+N*M" is not with opposite sign as "X".  */
>>         && (TYPE_UNSIGNED (type)
>>  	   || (vr0.nonnegative_p () && vr4.nonnegative_p ())
>> @@ -995,6 +996,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>>         /* "X - (N*M)" doesn't overflow.  */
>>         && range_op_handler (MINUS_EXPR).overflow_free_p (vr0, vr3)
>>         && get_range_query (cfun)->range_of_expr (vr4, @4)
>> +       && !vr4.undefined_p ()
>>         /* "X-N*M" is not with opposite sign as "X".  */
>>         && (TYPE_UNSIGNED (type)
>>  	   || (vr0.nonnegative_p () && vr4.nonnegative_p ())
>> @@ -1025,6 +1027,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>>  	  /* "X+C" doesn't overflow.  */
>>  	  && range_op_handler (PLUS_EXPR).overflow_free_p (vr0, vr1)
>>  	  && get_range_query (cfun)->range_of_expr (vr3, @3)
>> +	  && !vr3.undefined_p ()
>>  	  /* "X+C" and "X" are not of opposite sign.  */
>>  	  && (TYPE_UNSIGNED (type)
>>  	      || (vr0.nonnegative_p () && vr3.nonnegative_p ())
>> diff --git a/gcc/testsuite/gcc.dg/pr111303.c b/gcc/testsuite/gcc.dg/pr111303.c
>> new file mode 100644
>> index 00000000000..eaabe55c105
>> --- /dev/null
>> +++ b/gcc/testsuite/gcc.dg/pr111303.c
>> @@ -0,0 +1,11 @@
>> +/* { dg-do compile } */
>> +/* { dg-options "-O2" } */
>> +
>> +/* Make sure no ICE. */
>> +unsigned char a;
>> +int b(int c) {
>> +  if (c >= 5000)
>> +    return c / 5;
>> +}
>> +void d() { b(a - 5); }
>> +int main() {}
>> 

Re: [PATCH] Checking undefined_p before using the vr

[Andrew MacLeod]

On 9/12/23 21:42, Jiufu Guo wrote:
> Hi,
>
> Richard Biener <rguenther@suse.de> writes:
>
>> On Thu, 7 Sep 2023, Jiufu Guo wrote:
>>
>>> Hi,
>>>
>>> As discussed in PR111303:
>>>
>>> For pattern "(X + C) / N": "div (plus@3 @0 INTEGER_CST@1) INTEGER_CST@2)",
>>> Even if "X" has value-range and "X + C" does not overflow, "@3" may still
>>> be undefined. Like below example:
>>>
>>> _3 = _2 + -5;
>>> if (0 != 0)
>>>    goto <bb 3>; [34.00%]
>>> else
>>>    goto <bb 4>; [66.00%]
>>> ;;  succ:       3
>>> ;;              4
>>>
>>> ;; basic block 3, loop depth 0
>>> ;;  pred:       2
>>> _5 = _3 / 5;
>>> ;;  succ:       4
>>>
>>> The whole pattern "(_2 + -5 ) / 5" is in "bb 3", but "bb 3" would be
>>> unreachable (because "if (0 != 0)" is always false).
>>> And "get_range_query (cfun)->range_of_expr (vr3, @3)" is checked in
>>> "bb 3", "range_of_expr" gets an "undefined vr3". Where "@3" is "_5".
>>>
>>> So, before using "vr3", it would be safe to check "!vr3.undefined_p ()".
>>>
>>> Bootstrap & regtest pass on ppc64{,le} and x86_64.
>>> Is this ok for trunk?
>> OK, but I wonder why ->range_of_expr () doesn't return false for
>> undefined_p ()?  While "undefined" technically means we can treat
>> it as nonnegative_p (or not, maybe but maybe not both), we seem to
>> not want to do that.  So why expose it at all to ranger users
>> (yes, internally we in some places want to handle undefined).
> I guess, currently, it returns true and then lets the user check
> undefined_p, maybe because it tries to only return false if the
> type of EXPR is unsupported.

false is returned if no range can be calculated for any reason. The most 
common ones are unsupported types or in some cases, statements that are 
not understood.  FALSE means you cannot use the range being passed in.


> Let "range_of_expr" return false for undefined_p would save checking
> undefined_p again when using the APIs.
>
undefined is a perfectly acceptable range.  It can be used to represent 
either values which has not been initialized, or more frequently it 
identifies values that cannot occur due to conflicting/unreachable 
code.  VARYING means it can be any range, UNDEFINED means this is 
unusable, so treat it accordingly.  Its propagated like any other range.

The only reason you are having issues is you are then asking for the 
type of the range, and an undefined range currently has no type, for 
historical reasons.

Andrew

Andrew

Re: [PATCH] Checking undefined_p before using the vr

[Jiufu Guo]

Hi,

Andrew MacLeod <amacleod@redhat.com> writes:

> On 9/12/23 21:42, Jiufu Guo wrote:
>> Hi,
>>
>> Richard Biener <rguenther@suse.de> writes:
>>
>>> On Thu, 7 Sep 2023, Jiufu Guo wrote:
>>>
>>>> Hi,
>>>>
>>>> As discussed in PR111303:
>>>>
>>>> For pattern "(X + C) / N": "div (plus@3 @0 INTEGER_CST@1) INTEGER_CST@2)",
>>>> Even if "X" has value-range and "X + C" does not overflow, "@3" may still
>>>> be undefined. Like below example:
>>>>
>>>> _3 = _2 + -5;
>>>> if (0 != 0)
>>>>    goto <bb 3>; [34.00%]
>>>> else
>>>>    goto <bb 4>; [66.00%]
>>>> ;;  succ:       3
>>>> ;;              4
>>>>
>>>> ;; basic block 3, loop depth 0
>>>> ;;  pred:       2
>>>> _5 = _3 / 5;
>>>> ;;  succ:       4
>>>>
>>>> The whole pattern "(_2 + -5 ) / 5" is in "bb 3", but "bb 3" would be
>>>> unreachable (because "if (0 != 0)" is always false).
>>>> And "get_range_query (cfun)->range_of_expr (vr3, @3)" is checked in
>>>> "bb 3", "range_of_expr" gets an "undefined vr3". Where "@3" is "_5".
>>>>
>>>> So, before using "vr3", it would be safe to check "!vr3.undefined_p ()".
>>>>
>>>> Bootstrap & regtest pass on ppc64{,le} and x86_64.
>>>> Is this ok for trunk?
>>> OK, but I wonder why ->range_of_expr () doesn't return false for
>>> undefined_p ()?  While "undefined" technically means we can treat
>>> it as nonnegative_p (or not, maybe but maybe not both), we seem to
>>> not want to do that.  So why expose it at all to ranger users
>>> (yes, internally we in some places want to handle undefined).
>> I guess, currently, it returns true and then lets the user check
>> undefined_p, maybe because it tries to only return false if the
>> type of EXPR is unsupported.
>
> false is returned if no range can be calculated for any reason. The
> most common ones are unsupported types or in some cases, statements
> that are not understood.  FALSE means you cannot use the range being
> passed in.

Thanks a lot for the explaination! "false" means no ranger returned:
we cannot use the range argument after call.

>
>
>> Let "range_of_expr" return false for undefined_p would save checking
>> undefined_p again when using the APIs.
>>
> undefined is a perfectly acceptable range.  It can be used to
> represent either values which has not been initialized, or more
> frequently it identifies values that cannot occur due to
> conflicting/unreachable code.  VARYING means it can be any range,
> UNDEFINED means this is unusable, so treat it accordingly.  Its
> propagated like any other range.

"undefined" means the ranger is unusable. So, for this ranger, it
seems only "undefined_p ()" can be checked, and it seems no other
functions of this ranger can be called.

I'm thinking that it may be ok to let "range_of_expr" return false
if the "vr" is "undefined_p".  I know this may change the meaning
of "range_of_expr" slightly :) 

>
> The only reason you are having issues is you are then asking for the
> type of the range, and an undefined range currently has no type, for
> historical reasons.

Yeap, thanks for pointing out this!

BR,
Jeff (Jiufu Guo)

>
> Andrew
>
> Andrew

Re: [PATCH] Checking undefined_p before using the vr

[Andrew MacLeod]

On 9/14/23 22:07, Jiufu Guo wrote:
>>
>> undefined is a perfectly acceptable range.  It can be used to
>> represent either values which has not been initialized, or more
>> frequently it identifies values that cannot occur due to
>> conflicting/unreachable code.  VARYING means it can be any range,
>> UNDEFINED means this is unusable, so treat it accordingly.  Its
>> propagated like any other range.
> "undefined" means the ranger is unusable. So, for this ranger, it
> seems only "undefined_p ()" can be checked, and it seems no other
> functions of this ranger can be called.

not at all. It means ranger has determined that there is no valid range 
for the item you are asking about probably due to conflicting 
conditions, which imparts important information about the range.. or 
lack of range :-)

Quite frequently it means you are looking at a block of code that ranger 
knows is unreachable, but a pass of the compiler which removes such 
blocks has not been called yet.. so the awareness imparted is that there 
isn't much point in doing optimizations on it because its probably going 
to get thrown away by a following pass.

>
> I'm thinking that it may be ok to let "range_of_expr" return false
> if the "vr" is "undefined_p".  I know this may change the meaning
> of "range_of_expr" slightly :)

No.  That would be like saying NULL is not a valid value for a pointer.  
undefined_p has very specific meaning that we use.. it just has no type.

Andrew

Re: [PATCH] Checking undefined_p before using the vr

[Jiufu Guo]

Hi Andrew,

Thanks for your explain! And sorry for later reply.

Andrew MacLeod <amacleod@redhat.com> writes:

> On 9/14/23 22:07, Jiufu Guo wrote:
>>>
>>> undefined is a perfectly acceptable range.  It can be used to
>>> represent either values which has not been initialized, or more
>>> frequently it identifies values that cannot occur due to
>>> conflicting/unreachable code.  VARYING means it can be any range,
>>> UNDEFINED means this is unusable, so treat it accordingly.  Its
>>> propagated like any other range.
>> "undefined" means the ranger is unusable. So, for this ranger, it
>> seems only "undefined_p ()" can be checked, and it seems no other
>> functions of this ranger can be called.
>
> not at all. It means ranger has determined that there is no valid
> range for the item you are asking about probably due to conflicting
> conditions, which imparts important information about the range.. or
> lack of range :-)
>
> Quite frequently it means you are looking at a block of code that
> ranger knows is unreachable, but a pass of the compiler which removes
> such blocks has not been called yet.. so the awareness imparted is
> that there isn't much point in doing optimizations on it because its
> probably going to get thrown away by a following pass.
>
>>
>> I'm thinking that it may be ok to let "range_of_expr" return false
>> if the "vr" is "undefined_p".  I know this may change the meaning
>> of "range_of_expr" slightly :)
>
> No.  That would be like saying NULL is not a valid value for a
> pointer.  undefined_p has very specific meaning that we use.. it just
> has no type.

Oh, get it.:)

BR,
Jeff (Jiufu Guo)
>
> Andrew