diff mbox

[RFC,VRP] Improve intersect_ranges

Message ID 696145ed-2801-b342-ce7a-9e458ccb6909@linaro.org
State New
Headers show

Commit Message

Kugan Vivekanandarajah Oct. 12, 2016, 6:35 a.m. UTC 
Hi Richard,

On 12/10/16 00:14, Richard Biener wrote:
> On Tue, Oct 11, 2016 at 2:57 AM, kugan

> <kugan.vivekanandarajah@linaro.org> wrote:

>> Hi Richard,

>>Hi Richard,

>>

>> On 10/10/16 20:13, Richard Biener wrote:

>>>

>>> On Sat, Oct 8, 2016 at 9:38 PM, kugan <kugan.vivekanandarajah@linaro.org>

>>> wrote:

>>>>

>>>> Hi Richard,

>>>>

>>>> Thanks for the review.

>>>> On 07/10/16 20:11, Richard Biener wrote:

>>>>>

>>>>>

>>>>> On Fri, Oct 7, 2016 at 12:00 AM, kugan

>>>>> <kugan.vivekanandarajah@linaro.org> wrote:

>>>>>>

>>>>>>

>>>>>> Hi,

>>>>>>

>>>>>> In vrp intersect_ranges, Richard recently changed it to create integer

>>>>>> value

>>>>>> ranges when it is integer singleton.

>>>>>>

>>>>>> Maybe we should do the same when the other range is a complex ranges

>>>>>> with

>>>>>> SSA_NAME (like [x+2, +INF])?

>>>>>>

>>>>>> Attached patch tries to do this. There are cases where it will be

>>>>>> beneficial

>>>>>> as the  testcase in the patch. (For this testcase to work with Early

>>>>>> VRP,

>>>>>> we

>>>>>> need the patch posted at

>>>>>> https://gcc.gnu.org/ml/gcc-patches/2016-10/msg00413.html)

>>>>>>

>>>>>> Bootstrapped and regression tested on x86_64-linux-gnu with no new

>>>>>> regressions.

>>>>>

>>>>>

>>>>>

>>>>> This is not clearly a win, in fact it can completely lose an ASSERT_EXPR

>>>>> because there is no way to add its effect back as an equivalence.  The

>>>>> current choice of always using the "left" keeps the ASSERT_EXPR range

>>>>> and is able to record the other range via an equivalence.

>>>>

>>>>

>>>>

>>>> How about changing the order in Early VRP when we are dealing with the

>>>> same

>>>> SSA_NAME in inner and outer scope. Here is a patch that does this. Is

>>>> this

>>>> OK if no new regressions?

>>>

>>>

>>> I'm not sure if this is a good way forward.  The failure with the testcase

>>> is

>>> that we don't extract a range for k from if (j < k) which I believe

>>> another

>>> patch from you addresses?

>>

>>

>> Yes,  I have committed that. I am trying to add test cases for this and

>> thats when I stumbled on this:

>>

>> For:

>> foo (int k, int j)

>> {

>>    <bb 2>:

>>    if (j_1(D) > 9)

>>      goto <bb 3>;

>>    else

>>      goto <bb 6>;

>>

>>    <bb 3>:

>>    if (j_1(D) < k_2(D))

>>      goto <bb 4>;

>>    else

>>      goto <bb 6>;

>>

>>    <bb 4>:

>>    k_3 = k_2(D) + 1;

>>    if (k_2(D) <= 8)

>>      goto <bb 5>;

>>    else

>>      goto <bb 6>;

>>

>>    <bb 5>:

>>    abort ();

>>

>>    <bb 6>:

>>    return j_1(D);

>>

>> }

>>

>> Before we look at - if (j_1(D) < k_2(D))

>> j_1 (D) has [10, +INF]  EQUIVALENCES: { j_1(D) } (1 elements)

>>

>> When we look at  if (j_1(D) < k_2(D))

>> The range is [-INF, k_2(D) + -1]  EQUIVALENCES: { j_1(D) } (1 elements)

>>

>> We intersect:

>> [-INF, k_2(D) + -1]  EQUIVALENCES: { j_1(D) } (1 elements)

>> and

>> [10, +INF]  EQUIVALENCES: { j_1(D) } (1 elements)

>>

>> to

>> [-INF, k_2(D) + -1]  EQUIVALENCES: { j_1(D) } (1 elements)

>>

>> Due to this, in if (j_1(D) < k_2(D)) , we get pessimistic value range for

>> k_2(D)

>

> Ah, but that is because when generating the range for k from j < k we

> use the updated range for j.  That obviously doens't make too much sense.

>

> @@ -10650,7 +10661,7 @@ public:

>    virtual void after_dom_children (basic_block);

>    void push_value_range (const_tree var, value_range *vr);

>    value_range *pop_value_range (const_tree var);

> -  void try_add_new_range (tree op, tree_code code, tree limit);

> +  value_range *try_add_new_range (tree op, tree_code code, tree limit);

>

>    /* Cond_stack holds the old VR.  */

>    auto_vec<std::pair <const_tree, value_range*> > stack;

> @@ -10661,7 +10672,7 @@ public:

>

>  /*  Add new range to OP such that (OP CODE LIMIT) is true.  */

>

> -void

> +value_range *

>  evrp_dom_walker::try_add_new_range (tree op, tree_code code, tree limit)

>  {

>    value_range vr = VR_INITIALIZER;

> @@ -10678,8 +10689,9 @@ evrp_dom_walker::try_add_new_range (tree

>      {

>        value_range *new_vr = vrp_value_range_pool.allocate ();

>        *new_vr = vr;

> -      push_value_range (op, new_vr);

> +      return new_vr;

>      }

> +  return NULL;

>  }

>

>  /* See if there is any new scope is entered with new VR and set that VR to

> @@ -10715,7 +10727,7 @@ evrp_dom_walker::before_dom_children (ba

>             code = invert_tree_comparison (gimple_cond_code (stmt),

>                                            HONOR_NANS (op0));

>           /* Add VR when (OP0 CODE OP1) condition is true.  */

> -         try_add_new_range (op0, code, op1);

> +         value_range *op0_range = try_add_new_range (op0, code, op1);

>

>           /* Register ranges for y in x < y where

>              y might have ranges that are useful.  */

> @@ -10728,8 +10740,13 @@ evrp_dom_walker::before_dom_children (ba

>                                                           &new_code, &limit))

>             {

>               /* Add VR when (OP1 NEW_CODE LIMIT) condition is true.  */

> -             try_add_new_range (op1, new_code, limit);

> +             value_range *op1_range = try_add_new_range (op1, new_code, limit);

> +             if (op1_range)

> +               push_value_range (op1, op1_range);

>             }

> +

> +         if (op0_range)

> +           push_value_range (op0, op0_range);

>         }

>      }

>

>

>

> seems to fix that and the issue.

>


Here is your patch with slight name change and ChangeLog. Bootstrapped 
and regression tested on x86_64-linux-gnu with no regressions. Is this 
OK for trunk?

Thanks,
Kugan


gcc/ChangeLog:

2016-10-12  Richard Biener  <rguenther@suse.de>

	* tree-vrp.c (evrp_dom_walker::try_find_new_range): Renamed from
	try_add_new_range and made to return new range.
	(evrp_dom_walker::before_dom_children): Push op1 value range before
	pushing op0 value range.


gcc/testsuite/ChangeLog:

2016-10-12  Kugan Vivekanandarajah  <kuganv@linaro.org>

	* gcc.dg/tree-ssa/evrp6.c: New test.

>> Thanks,

>> Kugan

>>

>>

>>

>>> As said the issue is with the equivalence / value-range representation so

>>> you can't do sth like

>>>

>>>           /* Discover VR when condition is true.  */

>>>           extract_range_for_var_from_comparison_expr (op0, code, op0, op1,

>>> &vr);

>>>           if (old_vr->type == VR_RANGE || old_vr->type == VR_ANTI_RANGE)

>>>             vrp_intersect_ranges (&vr, old_vr);

>>>

>>>           /* If we found any usable VR, set the VR to ssa_name and create

>>> a

>>>              PUSH old value in the stack with the old VR.  */

>>>           if (vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE)

>>>             {

>>>               new_vr = vrp_value_range_pool.allocate ();

>>>               *new_vr = vr;

>>>               push_value_range (op0, new_vr);

>>>   ->>>  add equivalence to old_vr for new_vr.

>>>

>>> because old_vr and new_vr are the 'same' (they are associated with SSA

>>> name op0)

>>>

>>> Richard.

>>>

>>>> Thanks,

>>>> Kugan

>>>>

>>>>

>>>>

>>>>

>>>>

>>>>> My thought on this was that we need to separate "ranges" and associated

>>>>> SSA names so we can introduce new ranges w/o the need for an SSA name

>>>>> (and thus we can create an equivalence to the ASSERT_EXPR range).

>>>>> IIRC I started on this at some point but never finished it ...

>>>>>

>>>>> Richard.

>>>>>

>>>>>> Thanks,

>>>>>> Kugan

>>>>>>

>>>>>>

>>>>>> gcc/testsuite/ChangeLog:

>>>>>>

>>>>>> 2016-10-07  Kugan Vivekanandarajah  <kuganv@linaro.org>

>>>>>>

>>>>>>         * gcc.dg/tree-ssa/evrp6.c: New test.

>>>>>>

>>>>>> gcc/ChangeLog:

>>>>>>

>>>>>> 2016-10-07  Kugan Vivekanandarajah  <kuganv@linaro.org>

>>>>>>

>>>>>>         * tree-vrp.c (intersect_ranges): If we failed to handle

>>>>>>         the intersection and the other range involves computation with

>>>>>>         symbolic values, choose integer range if available.

>>>>>>

>>>>>>

>>>>>>

>>>>

>>
diff mbox

Patch

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/evrp6.c b/gcc/testsuite/gcc.dg/tree-ssa/evrp6.c
index e69de29..35d4d74 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/evrp6.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/evrp6.c
@@ -0,0 +1,22 @@ 
+
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-evrp" } */
+
+extern void abort (void);
+
+int
+foo (int k, int j)
+{
+  if (j >= 10)
+    {
+      if (j < k)
+	{
+	  k++;
+	  if (k < 10)
+	    abort ();
+	}
+    }
+
+  return j;
+}
+/* { dg-final { scan-tree-dump "\\\[12, \\+INF" "evrp" } } */
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 8a129c6..c794e76 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -10650,7 +10650,7 @@  public:
   virtual void after_dom_children (basic_block);
   void push_value_range (const_tree var, value_range *vr);
   value_range *pop_value_range (const_tree var);
-  void try_add_new_range (tree op, tree_code code, tree limit);
+  value_range *try_find_new_range (tree op, tree_code code, tree limit);
 
   /* Cond_stack holds the old VR.  */
   auto_vec<std::pair <const_tree, value_range*> > stack;
@@ -10659,10 +10659,10 @@  public:
 };
 
 
-/*  Add new range to OP such that (OP CODE LIMIT) is true.  */
+/*  Find new range for OP such that (OP CODE LIMIT) is true.  */
 
-void
-evrp_dom_walker::try_add_new_range (tree op, tree_code code, tree limit)
+value_range *
+evrp_dom_walker::try_find_new_range (tree op, tree_code code, tree limit)
 {
   value_range vr = VR_INITIALIZER;
   value_range *old_vr = get_value_range (op);
@@ -10678,8 +10678,9 @@  evrp_dom_walker::try_add_new_range (tree op, tree_code code, tree limit)
     {
       value_range *new_vr = vrp_value_range_pool.allocate ();
       *new_vr = vr;
-      push_value_range (op, new_vr);
+      return new_vr;
     }
+  return NULL;
 }
 
 /* See if there is any new scope is entered with new VR and set that VR to
@@ -10715,7 +10716,7 @@  evrp_dom_walker::before_dom_children (basic_block bb)
 	    code = invert_tree_comparison (gimple_cond_code (stmt),
 					   HONOR_NANS (op0));
 	  /* Add VR when (OP0 CODE OP1) condition is true.  */
-	  try_add_new_range (op0, code, op1);
+	  value_range *op0_range = try_find_new_range (op0, code, op1);
 
 	  /* Register ranges for y in x < y where
 	     y might have ranges that are useful.  */
@@ -10728,8 +10729,13 @@  evrp_dom_walker::before_dom_children (basic_block bb)
 							  &new_code, &limit))
 	    {
 	      /* Add VR when (OP1 NEW_CODE LIMIT) condition is true.  */
-	      try_add_new_range (op1, new_code, limit);
+	      value_range *op1_range = try_find_new_range (op1, new_code, limit);
+	      if (op1_range)
+		push_value_range (op1, op1_range);
 	    }
+
+	  if (op0_range)
+	    push_value_range (op0, op0_range);
 	}
     }