Avoid generating useless range info
diff mbox

Message ID 85de74ae-9680-1461-a289-42c915b5285a@redhat.com
State New
Headers show

Commit Message

Aldy Hernandez June 14, 2017, 4:41 p.m. UTC
Hi!

As discovered in my range class work, we seem to generate a significant 
amount of useless range info out of VRP.

Is there any reason why we can't avoid generating any range info that 
spans the entire domain, and yet contains nothing in the non-zero bitmask?

The attached patch passes bootstrap, and the one regression it causes is 
because now the -Walloca-larger-than= pass is better able to determine 
that there is no range information at all, and the testcase is 
unbounded.  So...win, win.

OK for trunk?

Aldy
gcc/

	* tree-vrp.c (vrp_finalize): Do not expose any useless range
	information.

gcc/testsuite/

	* gcc.dg/Walloca-14.c: Adapt test to recognize new complaint of
	unbounded use.

Comments

Richard Biener June 16, 2017, 8 a.m. UTC | #1
On Wed, Jun 14, 2017 at 6:41 PM, Aldy Hernandez <aldyh@redhat.com> wrote:
> Hi!
>
> As discovered in my range class work, we seem to generate a significant
> amount of useless range info out of VRP.
>
> Is there any reason why we can't avoid generating any range info that spans
> the entire domain, and yet contains nothing in the non-zero bitmask?
>
> The attached patch passes bootstrap, and the one regression it causes is
> because now the -Walloca-larger-than= pass is better able to determine that
> there is no range information at all, and the testcase is unbounded.
> So...win, win.
>
> OK for trunk?

Can you please do this in set_range_info itself?  Thus, if min ==
wi::min_value && max == wi::max_value
simply return?  (do not use TYPE_MIN?MAX_VALUE please)

Thanks,
Richard.

> Aldy
Aldy Hernandez June 23, 2017, 9:02 a.m. UTC | #2
[one more time, but without sending html which the list refuses :-/]

On Fri, Jun 16, 2017 at 4:00 AM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Wed, Jun 14, 2017 at 6:41 PM, Aldy Hernandez <aldyh@redhat.com> wrote:
>> Hi!
>>
>> As discovered in my range class work, we seem to generate a significant
>> amount of useless range info out of VRP.
>>
>> Is there any reason why we can't avoid generating any range info that spans
>> the entire domain, and yet contains nothing in the non-zero bitmask?
>>
>> The attached patch passes bootstrap, and the one regression it causes is
>> because now the -Walloca-larger-than= pass is better able to determine that
>> there is no range information at all, and the testcase is unbounded.
>> So...win, win.
>>
>> OK for trunk?
>
> Can you please do this in set_range_info itself?  Thus, if min ==
> wi::min_value && max == wi::max_value
> simply return?  (do not use TYPE_MIN?MAX_VALUE please)


The reason I did it in vrp_finalize is because if you do it in
set_range_info, you break set_nonzero_bits when setting bits on an SSA
that currently has no range info:

void
set_nonzero_bits (tree name, const wide_int_ref &mask)
{
  gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
  if (SSA_NAME_RANGE_INFO (name) == NULL)
    set_range_info (name, VR_RANGE,
   TYPE_MIN_VALUE (TREE_TYPE (name)),
   TYPE_MAX_VALUE (TREE_TYPE (name)));
  range_info_def *ri = SSA_NAME_RANGE_INFO (name);
  ri->set_nonzero_bits (mask);
}

Let me know how you'd like me to proceed.
Aldy

>
> Thanks,
> Richard.
>
>> Aldy
Richard Biener June 23, 2017, 10:24 a.m. UTC | #3
On Fri, Jun 23, 2017 at 10:59 AM, Aldy Hernandez <aldyh@redhat.com> wrote:
>
>
> On Fri, Jun 16, 2017 at 4:00 AM, Richard Biener <richard.guenther@gmail.com>
> wrote:
>>
>> On Wed, Jun 14, 2017 at 6:41 PM, Aldy Hernandez <aldyh@redhat.com> wrote:
>> > Hi!
>> >
>> > As discovered in my range class work, we seem to generate a significant
>> > amount of useless range info out of VRP.
>> >
>> > Is there any reason why we can't avoid generating any range info that
>> > spans
>> > the entire domain, and yet contains nothing in the non-zero bitmask?
>> >
>> > The attached patch passes bootstrap, and the one regression it causes is
>> > because now the -Walloca-larger-than= pass is better able to determine
>> > that
>> > there is no range information at all, and the testcase is unbounded.
>> > So...win, win.
>> >
>> > OK for trunk?
>>
>> Can you please do this in set_range_info itself?  Thus, if min ==
>> wi::min_value && max == wi::max_value
>> simply return?  (do not use TYPE_MIN?MAX_VALUE please)
>
>
> The reason I did it in vrp_finalize is because if you do it in
> set_range_info, you break set_nonzero_bits when setting bits on an SSA that
> currently has no range info:
>
> void
> set_nonzero_bits (tree name, const wide_int_ref &mask)
> {
>   gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
>   if (SSA_NAME_RANGE_INFO (name) == NULL)
>     set_range_info (name, VR_RANGE,
>    TYPE_MIN_VALUE (TREE_TYPE (name)),
>    TYPE_MAX_VALUE (TREE_TYPE (name)));
>   range_info_def *ri = SSA_NAME_RANGE_INFO (name);
>   ri->set_nonzero_bits (mask);
> }
>
> Let me know how you'd like me to proceed.

Just factor out a set_range_info_raw and call that then from here.

Richard.

> Aldy
>
>>
>> Thanks,
>> Richard.
>>
>> > Aldy
>
>
Jakub Jelinek June 23, 2017, 10:32 a.m. UTC | #4
On Fri, Jun 23, 2017 at 12:24:25PM +0200, Richard Biener wrote:
> > void
> > set_nonzero_bits (tree name, const wide_int_ref &mask)
> > {
> >   gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
> >   if (SSA_NAME_RANGE_INFO (name) == NULL)
> >     set_range_info (name, VR_RANGE,
> >    TYPE_MIN_VALUE (TREE_TYPE (name)),
> >    TYPE_MAX_VALUE (TREE_TYPE (name)));
> >   range_info_def *ri = SSA_NAME_RANGE_INFO (name);
> >   ri->set_nonzero_bits (mask);
> > }
> >
> > Let me know how you'd like me to proceed.
> 
> Just factor out a set_range_info_raw and call that then from here.

And don't call it if the mask is all ones.  Perhaps set_range_info
and set_nonzero_bits even should ggc_free and clear earlier range_info_def
if the range is all values and nonzero bit mask is all ones.
Or do we share range_info_def between multiple SSA_NAMEs?  If yes, of course
we shouldn't use ggc_free.

	Jakub
Richard Biener June 23, 2017, 11:01 a.m. UTC | #5
On Fri, Jun 23, 2017 at 12:32 PM, Jakub Jelinek <jakub@redhat.com> wrote:
> On Fri, Jun 23, 2017 at 12:24:25PM +0200, Richard Biener wrote:
>> > void
>> > set_nonzero_bits (tree name, const wide_int_ref &mask)
>> > {
>> >   gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
>> >   if (SSA_NAME_RANGE_INFO (name) == NULL)
>> >     set_range_info (name, VR_RANGE,
>> >    TYPE_MIN_VALUE (TREE_TYPE (name)),
>> >    TYPE_MAX_VALUE (TREE_TYPE (name)));
>> >   range_info_def *ri = SSA_NAME_RANGE_INFO (name);
>> >   ri->set_nonzero_bits (mask);
>> > }
>> >
>> > Let me know how you'd like me to proceed.
>>
>> Just factor out a set_range_info_raw and call that then from here.
>
> And don't call it if the mask is all ones.  Perhaps set_range_info
> and set_nonzero_bits even should ggc_free and clear earlier range_info_def
> if the range is all values and nonzero bit mask is all ones.
> Or do we share range_info_def between multiple SSA_NAMEs?  If yes, of course
> we shouldn't use ggc_free.

We shouldn't as we don't copy on change.  We do for points-to but only for the
bitmap pointer IIRC.

Richard,

>
>         Jakub
Aldy Hernandez June 27, 2017, 10:26 a.m. UTC | #6
On Fri, Jun 23, 2017 at 6:24 AM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Fri, Jun 23, 2017 at 10:59 AM, Aldy Hernandez <aldyh@redhat.com> wrote:
>>
>>
>> On Fri, Jun 16, 2017 at 4:00 AM, Richard Biener <richard.guenther@gmail.com>
>> wrote:
>>>
>>> On Wed, Jun 14, 2017 at 6:41 PM, Aldy Hernandez <aldyh@redhat.com> wrote:
>>> > Hi!
>>> >
>>> > As discovered in my range class work, we seem to generate a significant
>>> > amount of useless range info out of VRP.
>>> >
>>> > Is there any reason why we can't avoid generating any range info that
>>> > spans
>>> > the entire domain, and yet contains nothing in the non-zero bitmask?
>>> >
>>> > The attached patch passes bootstrap, and the one regression it causes is
>>> > because now the -Walloca-larger-than= pass is better able to determine
>>> > that
>>> > there is no range information at all, and the testcase is unbounded.
>>> > So...win, win.
>>> >
>>> > OK for trunk?
>>>
>>> Can you please do this in set_range_info itself?  Thus, if min ==
>>> wi::min_value && max == wi::max_value
>>> simply return?  (do not use TYPE_MIN?MAX_VALUE please)
>>
>>
>> The reason I did it in vrp_finalize is because if you do it in
>> set_range_info, you break set_nonzero_bits when setting bits on an SSA that
>> currently has no range info:
>>
>> void
>> set_nonzero_bits (tree name, const wide_int_ref &mask)
>> {
>>   gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
>>   if (SSA_NAME_RANGE_INFO (name) == NULL)
>>     set_range_info (name, VR_RANGE,
>>    TYPE_MIN_VALUE (TREE_TYPE (name)),
>>    TYPE_MAX_VALUE (TREE_TYPE (name)));
>>   range_info_def *ri = SSA_NAME_RANGE_INFO (name);
>>   ri->set_nonzero_bits (mask);
>> }
>>
>> Let me know how you'd like me to proceed.
>
> Just factor out a set_range_info_raw and call that then from here.

How about this?

Aldy
Jakub Jelinek June 27, 2017, 10:38 a.m. UTC | #7
On Tue, Jun 27, 2017 at 06:26:46AM -0400, Aldy Hernandez wrote:
> How about this?

@@ -360,6 +363,22 @@ set_range_info (tree name, enum value_range_type range_type,
     }
 }
 
+/* Store range information RANGE_TYPE, MIN, and MAX to tree ssa_name
+   NAME while making sure we don't store useless range info.  */
+
+void
+set_range_info (tree name, enum value_range_type range_type,
+		const wide_int_ref &min, const wide_int_ref &max)
+{
+  /* A range of the entire domain is really no range at all.  */
+  tree type = TREE_TYPE (name);
+  if (min == wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type))
+      && max == wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type)))
+    return;
+
+  set_range_info_raw (name, range_type, min, max);
+}
+

Won't this misbehave if we have a narrower range on some SSA_NAME and
call set_range_info to make it VARYING?
In that case (i.e. SSA_NAME_RANGE_INFO (name) != NULL), we should either
set_range_info_raw too (if nonzero_bits is not all ones) or clear
SSA_NAME_RANGE_INFO (otherwise).
 
 /* Gets range information MIN, MAX and returns enum value_range_type
    corresponding to tree ssa_name NAME.  enum value_range_type returned
@@ -419,9 +438,13 @@ set_nonzero_bits (tree name, const wide_int_ref &mask)
 {
   gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
   if (SSA_NAME_RANGE_INFO (name) == NULL)
-    set_range_info (name, VR_RANGE,
-		    TYPE_MIN_VALUE (TREE_TYPE (name)),
-		    TYPE_MAX_VALUE (TREE_TYPE (name)));
+    {
+      if (mask == -1)
+	return;
+      set_range_info_raw (name, VR_RANGE,
+			  TYPE_MIN_VALUE (TREE_TYPE (name)),
+			  TYPE_MAX_VALUE (TREE_TYPE (name)));
+    }
   range_info_def *ri = SSA_NAME_RANGE_INFO (name);
   ri->set_nonzero_bits (mask);

Similarly, if SSA_NAME_RANGE_INFO is previously non-NULL, but min/max
are VARYING and the new mask is -1, shouldn't we free it rather than
set it to the default?

If we consider the cases rare enough to worry about, at least your
above
  if (min == wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type))
      && max == wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type)))
should be
  gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
  if (SSA_NAME_RANGE_INFO (name) == NULL
      && min == wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type))
      && max == wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type)))
We'd then not misbehave, just might in some rare cases keep
SSA_NAME_RANGE_INFO non-NULL even if it contains the default stuff.

	Jakub

Patch
diff mbox

diff --git a/gcc/testsuite/gcc.dg/Walloca-14.c b/gcc/testsuite/gcc.dg/Walloca-14.c
index 723dbe5..f3e3f57 100644
--- a/gcc/testsuite/gcc.dg/Walloca-14.c
+++ b/gcc/testsuite/gcc.dg/Walloca-14.c
@@ -9,5 +9,6 @@  g (int *p)
   extern void f (void *);
 
   void *q = __builtin_alloca (p); /* { dg-warning "passing argument 1" } */
+  /* { dg-warning "unbounded use of 'alloca'" "unbounded" { target *-*-* } 11 } */
   f (q);
 }
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 716a7c2..8442b1f 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -10708,8 +10708,24 @@  vrp_finalize (bool warn_array_bounds_p)
 					      vr_value[i]->max) == 1)))
 	  set_ptr_nonnull (name);
 	else if (!POINTER_TYPE_P (TREE_TYPE (name)))
-	  set_range_info (name, vr_value[i]->type, vr_value[i]->min,
-			  vr_value[i]->max);
+	  {
+	    range_info_def *ri = SSA_NAME_RANGE_INFO (name);
+	    tree type = TREE_TYPE (name);
+	    unsigned precision = TYPE_PRECISION (type);
+	    /* If the range covers the entire domain and there is
+	       nothing in the non-zero bits mask, there is no sense in
+	       storing anything.  */
+	    if (vr_value[i]->min == TYPE_MIN_VALUE (type)
+		&& vr_value[i]->max == TYPE_MAX_VALUE (type)
+		&& vr_value[i]->type == VR_RANGE
+		&& (!ri
+		    || ri->get_nonzero_bits () == wi::shwi (-1, precision)))
+	      SSA_NAME_RANGE_INFO (name) = NULL;
+	    else
+	      set_range_info (name, vr_value[i]->type, vr_value[i]->min,
+			      vr_value[i]->max);
+	  }
+}
       }
 
   substitute_and_fold (op_with_constant_singleton_value_range, vrp_fold_stmt);