This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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

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.



commit 4f9aa7bd1066267eee92f622ff29d78534158e20
Author: Aldy Hernandez <>
Date:   Fri Jun 28 11:34:19 2019 +0200

     Do not try to further refine a VR_UNDEFINED result when intersecting

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  <>
+	* 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

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]

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 :).

commit f9f6ae7188d0cf45d817f46e46b34c639d29993f
Author: Aldy Hernandez <>
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)
   /* 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;

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]