[RFC,VRP] Improve intersect_ranges

Message ID 881b2805-15ec-ad68-96a5-e2debd2fb850@linaro.org
State New
Headers show

Commit Message

Kugan Vivekanandarajah Oct. 8, 2016, 7:38 p.m.
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?

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

Kugan Vivekanandarajah Oct. 11, 2016, 12:57 a.m. | #1
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)

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.

>>>>

>>>>

>>>>

>>

Patch hide | download patch | download mbox

From 54e92b7ddc47f6986e4dc79402d6808bb9c30c69 Mon Sep 17 00:00:00 2001
From: Kugan Vivekanandarajah <kugan.vivekanandarajah@linaro.org>
Date: Sat, 8 Oct 2016 15:09:09 +1100
Subject: [PATCH 4/7] Revese value range before calling interset_range

---
 gcc/testsuite/gcc.dg/tree-ssa/evrp6.c | 22 ++++++++++++++++++++++
 gcc/tree-vrp.c                        | 16 +++++++++++++++-
 2 files changed, 37 insertions(+), 1 deletion(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/evrp6.c

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/evrp6.c b/gcc/testsuite/gcc.dg/tree-ssa/evrp6.c
new file mode 100644
index 0000000..35d4d74
--- /dev/null
+++ 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 160adb5..c18c86f 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -10664,7 +10664,21 @@  evrp_dom_walker::try_add_new_range (tree op, tree_code code, tree limit)
   extract_range_for_var_from_comparison_expr (op, code, op,
 					      limit, &vr);
   if (old_vr->type == VR_RANGE || old_vr->type == VR_ANTI_RANGE)
-    vrp_intersect_ranges (&vr, old_vr);
+    {
+      if (range_int_cst_p (old_vr)
+	  && !range_int_cst_p (&vr))
+	{
+	  /* intersect_range will use the left value range to keeps the
+	     ASSERT_EXPR range and record the other range via an equivalence.
+	     In this case, we are tracking value_ranges for same SSA_NAME in
+	     different scope, so reverse it for better result. */
+	  value_range other_vr = vr;
+	  vr = *old_vr;
+	  vrp_intersect_ranges (&vr, &other_vr);
+	}
+      else
+	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)
-- 
2.7.4