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

Comments

Richard Biener Oct. 12, 2016, 7:03 a.m. UTC | #1 
On Wed, Oct 12, 2016 at 8:35 AM, kugan
<kugan.vivekanandarajah@linaro.org> wrote:
> 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?

Ok.

Richard.

> 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);
 	}
     }