Re: [range-ops] patch 05/04: bonus round!

[Aldy Hernandez <aldyh at redhat dot com>]

On 7/3/19 7:12 PM, Jeff Law wrote:
> On 7/1/19 4:24 AM, Aldy Hernandez wrote:
> > This is completely unrelated to range-ops itself, but may yield better
> > results in value_range intersections.  It's just something I found while
> > working on VRP, and have been dragging around on our branch.
> >
> > If we know the intersection of two ranges is the empty set, there is no
> > need to conservatively add anything to the result.
> >
> > Tested on x86-64 Linux with --enable-languages=all.
> >
> > Aldy
> >
> > range-ops-intersect-undefined.patch
> >
> > commit 4f9aa7bd1066267eee92f622ff29d78534158e20
> > Author: Aldy Hernandez <aldyh@redhat.com>
> > Date:   Fri Jun 28 11:34:19 2019 +0200
> >
> >      Do not try to further refine a VR_UNDEFINED result when intersecting
> >      value_ranges.
> >
> > diff --git a/gcc/ChangeLog b/gcc/ChangeLog
> > index 01fb97cedb2..b0d78ee6871 100644
> > --- a/gcc/ChangeLog
> > +++ b/gcc/ChangeLog
> > @@ -1,3 +1,9 @@
> > +2019-07-01  Aldy Hernandez  <aldyh@redhat.com>
> > +
> > +	* tree-vrp.c (intersect_ranges): If we know the intersection is
> > +	empty, there is no need to conservatively add anything else to
> > +	the set.
> Do we have a test where this improves the code or at least the computed
> ranges?

I have long since lost the testcase, but a little hacking around to dump 
all the cases where we are trying to conservatively refine a 
VR_UNDEFINED, yields tons of hits.  See attached hack.

By far, the most common is the intersection of ~[0,0] and [0,0], which 
yields VR_UNDEFINED.  We then conservatively drop to VR1, which is 
[0,0], basically pessimizing the result.

Other examples include:

unsigned char [38, +INF], unsigned char [22, 22]
unsigned char [4, 4], unsigned char [1, 1]
unsigned char [4, 4], unsigned char [2, 2]
unsigned int [0, 64], unsigned int [128, 128]
unsigned int [0, 6], unsigned int [4294967275, 4294967275]
unsigned int ~[35, 35], unsigned int [35, 35]
unsigned int [46, 52], unsigned int [25, 25]
etc

Within 7 minutes of building a compiler (up to stage2), this incorrect 
refinement of VR_UNDEFINED has been triggered 29000 times.

If we know it's VR_UNDEFINED (the empty set), I think we should leave it 
empty :).

Aldy

commit f9f6ae7188d0cf45d817f46e46b34c639d29993f
Author: Aldy Hernandez <aldyh@redhat.com>
Date:   Thu Jul 4 11:21:28 2019 +0200

    WIP: UNDEFINED refine

diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 5caea6d3593..5390a916d2f 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -6150,6 +6150,9 @@ intersect_ranges (enum value_range_kind *vr0type,
 		  enum value_range_kind vr1type,
 		  tree vr1min, tree vr1max)
 {
+  value_range_base t0 (*vr0type, *vr0min, *vr0max);
+  value_range_base t1 (vr1type, vr1min, vr1max);
+
   bool mineq = vrp_operand_equal_p (*vr0min, vr1min);
   bool maxeq = vrp_operand_equal_p (*vr0max, vr1max);
 
@@ -6445,10 +6448,12 @@ intersect_ranges (enum value_range_kind *vr0type,
 	gcc_unreachable ();
     }
 
+#if 0
   /* If we know the intersection is empty, there's no need to
      conservatively add anything else to the set.  */
   if (*vr0type == VR_UNDEFINED)
     return;
+#endif
 
   /* As a fallback simply use { *VRTYPE, *VR0MIN, *VR0MAX } as
      result for the intersection.  That's always a conservative
@@ -6458,6 +6463,16 @@ intersect_ranges (enum value_range_kind *vr0type,
       && is_gimple_min_invariant (vr1min)
       && vrp_operand_equal_p (vr1min, vr1max))
     {
+      if (*vr0type == VR_UNDEFINED)
+	{
+	  FILE *out = fopen("/tmp/asdf.aldy", "a");
+	  fprintf(out, "intersect_ranges about to refine VR_UNDEFINED\n");
+	  t0.dump(out);
+	  fprintf(out, ",");
+	  t1.dump(out);
+	  fprintf(out, "\n");
+	  fclose(out);
+	}
       *vr0type = vr1type;
       *vr0min = vr1min;
       *vr0max = vr1max;