Re: [RFC][IPA-VRP] Early VRP Implementation

[kugan <kugan.vivekanandarajah@linaro.org>]

[-- Attachment #1: Type: text/plain, Size: 7362 bytes --]



Hi Riachard,

Thanks for the review. Here is an updated patch with comments below.

> +/* Restore/Pop all the old VRs maintained in the cond_stack.  */
> +
> +void evrp_dom_walker::finalize_dom_walker ()
> +{
> +  while (!cond_stack.is_empty ())
> +    {
> +      tree var = cond_stack.last ().second;
> +      pop_value_range (var);
> +      cond_stack.pop ();
> +    }
>
> why is this necessary at all?  Looks like a waste of time (and the
> stack should be empty here
> anyway).  I think you leak cond_stack as well, I suppose using
> auto_vec might work here,
> you have to check.
Done.

>
>>>
>>> +         /* Discover VR when condition is true.  */
>>> +         if (te == e
>>> +             && !TREE_OVERFLOW_P (op0)
>>> +             && !TREE_OVERFLOW_P (op1))
>>
>>
>> This is mainly to handle gcc.dg/pr38934.c. This would result in ICE from
>> set_value_range otherwise:
>>
>> gcc_assert ((!TREE_OVERFLOW_P (min) || is_overflow_infinity (min))
>>                   && (!TREE_OVERFLOW_P (max) || is_overflow_infinity
>> (max)));
>
> Ok, instead make sure to remove the overflow flag via
>
>   if (TREE_OVERFLOW_P (op0))
>     op0 = drop_tree_overflow (op0);
  ...
Done.

>
> it looks like you want to merge the if ( & EDGE_TRUE_VALUE) and FALSE_VALUE
> cases and only invert the tree comparison for the false edge.
Done.

>
> +             tree cond = build2 (code, boolean_type_node, op0, op1);
> +             extract_range_for_var_from_comparison_expr (&vr, op0, cond);
>
> no wasteful tree building here please.  Instead of cond pass in code,
> op0 and op1
> as separate arguments.
Done.

>
> +         /* If we found any usable VR, set the VR to ssa_name and create a
> +            PUSH old value in the cond_stack with the old VR.  */
> +         if (vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE)
> +           {
> +             value_range *new_vr = vrp_value_range_pool.allocate ();
> +             memset (new_vr, 0, sizeof (*new_vr));
> +             *new_vr = vr;
> +             cond_stack.safe_push (std::make_pair (bb, op0));
>
> the memset looks redundant given you copy-assing from vr anyway.
Done.

>
> You seem to miss the chance to register ranges for x_2 in i_1 < x_2 where
> both i_1 and x_2 might have ranges that are useful.
I will address this once the basic structure is in place if that is OK 
with you.

>
> push and pop_value_range should be methods in the dom walker class
> and vrp_stack and cond_stack should be a single stack.  You can omit
> basic_block if you use a "magic" NULL_TREE var as marker (simply
> push a NULL_TREE, NULL pair at the end of before_dom_children).
>
Done.

>>>
>>> you can use e->flags & EDGE_TRUE_VALUE/EDGE_FALSE_VALUE
>>>
>>> why do you need those TREE_OVERFLOW checks?
>>>
>>> +             tree cond = build2 (code, boolean_type_node, op0, op1);
>>> +             tree a = build2 (ASSERT_EXPR, TREE_TYPE (op0), op0, cond);
>>> +             extract_range_from_assert (&vr, a);
>>>
>>> so I was hoping that the "refactoring" patch in the series would expose a
>>> more
>>> useful interface than extract_range_from_assert ... namely one that can
>>> extract a range from the comparison directly and does not require building
>>> a scratch ASSERT_EXPR.
>>
>>
>> I have split extract_range_from_assert into
>> extract_range_for_var_from_comparison_expr and using it now. Is that better?
>
> See above.
>
>>>
>>>
>>> +         /* If we found any usable VR, set the VR to ssa_name and create
>>> a
>>> +            restore point in the cond_stack with the  old VR. */
>>> +         if (vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE)
>>> +           {
>>> +             value_range *new_vr = XCNEW (value_range);
>>> +             *new_vr = vr;
>>> +             cond_stack.safe_push (std::make_pair (bb,
>>> +                                                   std::make_pair (op0,
>>> +
>>> old_vr)));
>>> +             change_value_range (op0, new_vr);
>>>
>>> I don't like 'change_value_range' as interface, please integrate that into
>>> a push/pop_value_range style interface instead.
>>
>>
>> Tried using push/pop interface.
>>>
>>>
>>> +       vrp_visit_stmt (stmt, &taken_edge_p, &output_p);
>>> +    }
>>> +
>>> +  return NULL;
>>>
>>> you should return taken_edge_p (misnamed as it isn't a pointer) and take
>>> advantage of EDGE_EXECUTABLE.  Again see DOM/SCCVN (might want to
>>> defer this as a followup improvement).
>>
>>
>> I have added a TODO to this effect and will comeback to it.
>>>
>>>
>>> Note that the advantage of a DOM-based VRP is that backtracking is easy
>>> to implement (you don't do that yet).  That is, after DEF got a (better)
>>> value-range you can simply re-visit all the defs of its uses (and
>>> recursively).
>>> I think you have to be careful with stmts that might prematurely leave a
>>> BB
>>> though (like via EH).  So sth for a followup as well.
>>
>>
>> Is this OK now. Bootstrapped and regression tested on x86_64-linux  with no
>> new regressions.
>
> Better, still not perfect.
>
> I'm also arguing on the pass placement now - you put it where it may make sense
> for IPA VRP (but then IPA VRP could simply do this in its analysis phase) but
> not so much where it makes sense during the early pipeline.  I think it makes
> sense after FRE.
>
> Looking at how you finalize I see several issues with simply re-using
> vrp_finalize.
>
> First of all the loop doing the set_range_info will turn up with
> nothing as you've
> popped off all value-ranges from the lattice.  Same for substitute-and-fold (or
> jump-threading).
I am not sure understanding you. I am poping the value ranges for scope 
when we leave them. Other value ranges which lives in all the regions 
will remain.

>
> What you instead need to do with the DOM scheme is at the point you
> call vrp_visit_stmt do sth like
>
>      vrp_visit_stmt (....);
>      if (fold_stmt (&gsi, follow_single_use_edges))
>        update_stmt ();
I have added this. I think this will be good as we would be able to 
optimize with value ranges that is valid within the scope.

>      tree def = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF);
>      if (def
>          && INTEGRAL_TYPE_P (TREE_TYPE (def))
>          && (TREE_CODE (vr_value[i]->min) == INTEGER_CST)
>           && (TREE_CODE (vr_value[i]->max) == INTEGER_CST)
>           && (vr_value[i]->type == VR_RANGE
>               || vr_value[i]->type == VR_ANTI_RANGE))
>         set_range_info (name, vr_value[i]->type, vr_value[i]->min,
>                         vr_value[i]->max);
>
I am not sure if this is needed. I dont know if my push/pop value range 
implementation is not what you wanted. If you still prefer, I am happy 
to add this.

> thus please split vrp_finalize into two parts, one of it with the memory
> freeing which is the one you'd call.
>
> Note that EVRP is not enabled by default at any optimization level
> it seems so bootstrap / test of it would be useless (did you only
> test with the full series?  I never looked at the IPA VRP part)
>
I have:

+ftree-evrp
+Common Report Var(flag_tree_early_vrp) Init(1) Optimization
+Perform Early Value Range Propagation on trees.

I would like to run this only for -O2 and above but for now I am using 
this to test.

I  have tested the last set of patch separately.

I will do more testing on this patch based on your feedback. Does this 
look better?

Thanks,
Kugan



[-- Attachment #2: 0005-Add-early-vrp.patch --]
[-- Type: text/x-patch, Size: 27023 bytes --]

From eefcd1c5444cf5dd9f121e8bd04148d324d06ffc Mon Sep 17 00:00:00 2001
From: Kugan Vivekanandarajah <kugan.vivekanandarajah@linaro.org>
Date: Fri, 24 Jun 2016 14:45:24 +1000
Subject: [PATCH 5/7] Add early vrp

---
 gcc/common.opt                            |   4 +
 gcc/doc/invoke.texi                       |   9 +
 gcc/passes.def                            |   1 +
 gcc/testsuite/g++.dg/tree-ssa/pr31146-2.C |   2 +-
 gcc/testsuite/gcc.dg/tree-ssa/evrp1.c     |  13 ++
 gcc/testsuite/gcc.dg/tree-ssa/evrp2.c     |  18 ++
 gcc/testsuite/gcc.dg/tree-ssa/evrp3.c     |  15 ++
 gcc/testsuite/gcc.dg/tree-ssa/pr20318.c   |   4 +-
 gcc/testsuite/gcc.dg/tree-ssa/pr22117.c   |   2 +-
 gcc/testsuite/gcc.dg/tree-ssa/pr25382.c   |   4 +-
 gcc/testsuite/gcc.dg/tree-ssa/pr68431.c   |   4 +-
 gcc/testsuite/gcc.dg/tree-ssa/vrp19.c     |   6 +-
 gcc/testsuite/gcc.dg/tree-ssa/vrp23.c     |   4 +-
 gcc/testsuite/gcc.dg/tree-ssa/vrp24.c     |   5 +-
 gcc/testsuite/gcc.dg/tree-ssa/vrp58.c     |   4 +-
 gcc/testsuite/gcc.dg/tree-ssa/vrp67.c     |   4 +-
 gcc/testsuite/gcc.dg/tree-ssa/vrp98.c     |   6 +-
 gcc/timevar.def                           |   1 +
 gcc/tree-pass.h                           |   1 +
 gcc/tree-vrp.c                            | 354 ++++++++++++++++++++++++++----
 20 files changed, 397 insertions(+), 64 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/evrp1.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/evrp2.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/evrp3.c

diff --git a/gcc/common.opt b/gcc/common.opt
index f0d7196..29d0e4d 100644
--- a/gcc/common.opt
+++ b/gcc/common.opt
@@ -2471,6 +2471,10 @@ ftree-vrp
 Common Report Var(flag_tree_vrp) Init(0) Optimization
 Perform Value Range Propagation on trees.
 
+ftree-evrp
+Common Report Var(flag_tree_early_vrp) Init(1) Optimization
+Perform Early Value Range Propagation on trees.
+
 fsplit-paths
 Common Report Var(flag_split_paths) Init(0) Optimization
 Split paths leading to loop backedges.
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index e000218..f4dc88d 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -7665,6 +7665,10 @@ enabled by default at @option{-O2} and higher.  Null pointer check
 elimination is only done if @option{-fdelete-null-pointer-checks} is
 enabled.
 
+@item -ftree-evrp
+@opindex ftree-evrp
+Perform Early Value Range Propagation on trees.
+
 @item -fsplit-paths
 @opindex fsplit-paths
 Split paths leading to loop backedges.  This can improve dead code
@@ -12270,6 +12274,11 @@ is made by appending @file{.slp} to the source file name.
 Dump each function after Value Range Propagation (VRP).  The file name
 is made by appending @file{.vrp} to the source file name.
 
+@item early vrp
+@opindex fdump-tree-evrp
+Dump each function after Early Value Range Propagation (EVRP).  The file name
+is made by appending @file{.evrp} to the source file name.
+
 @item oaccdevlow
 @opindex fdump-tree-oaccdevlow
 Dump each function after applying device-specific OpenACC transformations.
diff --git a/gcc/passes.def b/gcc/passes.def
index 3647e90..ebd360b 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -89,6 +89,7 @@ along with GCC; see the file COPYING3.  If not see
 	     execute TODO_rebuild_alias at this point.  */
 	  NEXT_PASS (pass_build_ealias);
 	  NEXT_PASS (pass_fre);
+	  NEXT_PASS (pass_early_vrp);
 	  NEXT_PASS (pass_merge_phi);
           NEXT_PASS (pass_dse);
 	  NEXT_PASS (pass_cd_dce);
diff --git a/gcc/testsuite/g++.dg/tree-ssa/pr31146-2.C b/gcc/testsuite/g++.dg/tree-ssa/pr31146-2.C
index 5e09583..dce05d6 100644
--- a/gcc/testsuite/g++.dg/tree-ssa/pr31146-2.C
+++ b/gcc/testsuite/g++.dg/tree-ssa/pr31146-2.C
@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O -fdump-tree-forwprop1" } */
+/* { dg-options "-O -fno-tree-evrp -fdump-tree-forwprop1" } */
 
 #include <new>
 
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/evrp1.c b/gcc/testsuite/gcc.dg/tree-ssa/evrp1.c
new file mode 100644
index 0000000..8c6e4e6
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/evrp1.c
@@ -0,0 +1,13 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-evrp" } */
+
+int foo (int i);
+int bar (int j)
+{
+  if (j > 2)
+    return foo (j + 2);
+  else
+    return j;
+}
+
+/* { dg-final { scan-tree-dump "\\\[5, \\+INF" "evrp" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/evrp2.c b/gcc/testsuite/gcc.dg/tree-ssa/evrp2.c
new file mode 100644
index 0000000..e6d4235
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/evrp2.c
@@ -0,0 +1,18 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-evrp" } */
+
+int foo (int i);
+int bar2 (int j)
+{
+  if (j > 2)
+    {
+      if (j < 7)
+	return foo (j + 1);
+      else
+	return foo (j + 2);
+    }
+  return j;
+}
+
+
+/* { dg-final { scan-tree-dump "\\\[4, 7\\\]" "evrp" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/evrp3.c b/gcc/testsuite/gcc.dg/tree-ssa/evrp3.c
new file mode 100644
index 0000000..1a3bbd5
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/evrp3.c
@@ -0,0 +1,15 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-evrp" } */
+
+int foo (int i);
+void bar (int j)
+{
+  unsigned int i;
+  for (i = 0; i < 10; ++i)
+    {
+      bar (i + 1);
+    }
+}
+
+/* { dg-final { scan-tree-dump "\\\[1, 10\\\]" "evrp" } } */
+
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr20318.c b/gcc/testsuite/gcc.dg/tree-ssa/pr20318.c
index 41f569e..8c12863 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr20318.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr20318.c
@@ -1,5 +1,5 @@
 /* { dg-do compile { target { ! keeps_null_pointer_checks } } } */
-/* { dg-options "-O2 -fdump-tree-original -fdump-tree-vrp1 -fdelete-null-pointer-checks" } */
+/* { dg-options "-O2 -fdump-tree-original -fdump-tree-evrp  -fdelete-null-pointer-checks" } */
 
 extern int* f(int) __attribute__((returns_nonnull));
 extern void eliminate ();
@@ -14,4 +14,4 @@ void h () {
 }
 
 /* { dg-final { scan-tree-dump-times "== 0" 1 "original" } } */
-/* { dg-final { scan-tree-dump-times "Folding predicate\[^\\n\]*to 0" 1 "vrp1" } } */
+/* { dg-final { scan-tree-dump-times "Folding predicate\[^\\n\]*to 0" 1 "evrp" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr22117.c b/gcc/testsuite/gcc.dg/tree-ssa/pr22117.c
index 7efdd63..43cea0b 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr22117.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr22117.c
@@ -3,7 +3,7 @@
    known to be zero after entering the first two "if" statements.  */
 
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-vrp1" } */
+/* { dg-options "-O2 -fno-tree-evrp -fdump-tree-vrp" } */
 
 void link_error (void);
 
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr25382.c b/gcc/testsuite/gcc.dg/tree-ssa/pr25382.c
index dcf9148..0d19d0d 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr25382.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr25382.c
@@ -3,7 +3,7 @@
    Check that VRP now gets ranges from BIT_AND_EXPRs.  */
 
 /* { dg-do compile } */
-/* { dg-options "-O2 -fno-tree-ccp -fdump-tree-vrp1" } */
+/* { dg-options "-O2 -fno-tree-ccp -fdump-tree-evrp" } */
 
 int
 foo (int a)
@@ -15,4 +15,4 @@ foo (int a)
     return 1;
 }
 
-/* { dg-final { scan-tree-dump-times "Folding predicate b_.* > 300 to 0" 1 "vrp1" } } */
+/* { dg-final { scan-tree-dump-times "Folding predicate b_.* > 300 to 0" 1 "evrp" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr68431.c b/gcc/testsuite/gcc.dg/tree-ssa/pr68431.c
index 3bd3843..a73aa00 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr68431.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr68431.c
@@ -1,5 +1,5 @@
 /* PR tree-optimization/68431 */
-/* { dg-options "-O2 -fdump-tree-vrp1-details" } */
+/* { dg-options "-O2 -fdump-tree-evrp-details" } */
 
 unsigned int x = 1;
 int
@@ -13,4 +13,4 @@ main (void)
   return 0;
 }
 
-/* { dg-final { scan-tree-dump-times "Folding predicate .*to 0" 1 "vrp1" } } */
+/* { dg-final { scan-tree-dump-times "Folding predicate .*to 0" 1 "evrp" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp19.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp19.c
index cecacb6..3d47bfd 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/vrp19.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp19.c
@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-fwrapv -O1 -ftree-vrp -fdump-tree-vrp1" } */
+/* { dg-options "-fwrapv -O1 -ftree-vrp -fdump-tree-evrp" } */
 
 #include <limits.h>
 extern void abort ();
@@ -22,5 +22,5 @@ int g (int b) {
 	}
 	return 1;
 }
-/* { dg-final { scan-tree-dump "Folding predicate a_. < 0 to 0" "vrp1" } } */
-/* { dg-final { scan-tree-dump "Folding predicate b_. >= 0 to 1" "vrp1" } } */
+/* { dg-final { scan-tree-dump "Folding predicate a_. < 0 to 0" "evrp" } } */
+/* { dg-final { scan-tree-dump "Folding predicate b_. >= 0 to 1" "evrp" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp23.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp23.c
index b877ccc..a6d2a24 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/vrp23.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp23.c
@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-vrp1-details" } */
+/* { dg-options "-O2 -fdump-tree-evrp-details" } */
 
 void aa (void);
 void aos (void);
@@ -45,5 +45,5 @@ L8:
 /* The n_sets > 0 test can be simplified into n_sets == 1 since the
    only way to reach the test is when n_sets <= 1, and the only value
    which satisfies both conditions is n_sets == 1.  */
-/* { dg-final { scan-tree-dump-times "Simplified relational" 1 "vrp1" } } */
+/* { dg-final { scan-tree-dump-times "Simplified relational" 1 "evrp" } } */
 
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp24.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp24.c
index e740575..0e1e69c 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/vrp24.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp24.c
@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-vrp1-details" } */
+/* { dg-options "-O2 -fdump-tree-evrp-details -fdump-tree-vrp1-details" } */
 
 
 struct rtx_def;
@@ -91,5 +91,6 @@ L7:
    The second n_sets > 0 test can also be simplified into n_sets == 1
    as the only way to reach the tests is when n_sets <= 1 and the only
    value which satisfies both conditions is n_sets == 1.  */
-/* { dg-final { scan-tree-dump-times "Simplified relational" 2 "vrp1" } } */
+/* { dg-final { scan-tree-dump-times "Simplified relational" 1 "vrp1" } } */
+/* { dg-final { scan-tree-dump-times "Simplified relational" 1 "evrp" } } */
 
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp58.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp58.c
index 5b44ae2..6df91ca 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/vrp58.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp58.c
@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-vrp1-details" } */
+/* { dg-options "-O2 -fdump-tree-evrp-details" } */
 
 long long
 foo (long long a, signed char b, signed char c)
@@ -9,4 +9,4 @@ foo (long long a, signed char b, signed char c)
 }
 
 /* { dg-final { scan-tree-dump "Folded into" "vrp1" { target int32plus } } } */
-/* { dg-final { scan-tree-dump "Folding statement: _\[0-9\]\* = \\(long long int\\) bc_\[0-9\]\*;" "vrp1" { target int16 } } } */
+/* { dg-final { scan-tree-dump "Folding statement: _\[0-9\]\* = \\(long long int\\) bc_\[0-9\]\*;" "evrp" { target int16 } } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp67.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp67.c
index ef5e8f9..b19b546 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/vrp67.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp67.c
@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-vrp1" } */
+/* { dg-options "-O2 -fdump-tree-evrp" } */
 
 extern void link_error (void);
 
@@ -36,4 +36,4 @@ unsigned baz (unsigned i)
   return i;
 }
 
-/* { dg-final { scan-tree-dump-times "Folding predicate" 3 "vrp1" } } */
+/* { dg-final { scan-tree-dump-times "Folding predicate" 3 "evrp" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp98.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp98.c
index 982f091..7ad818c 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/vrp98.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp98.c
@@ -1,6 +1,6 @@
 /* { dg-do compile } */
 /* { dg-require-effective-target int128 } */
-/* { dg-options "-Os -fdump-tree-vrp1-details" } */
+/* { dg-options "-Os -fdump-tree-evrp-details" } */
 
 #include <stdint.h>
 #include <limits.h>
@@ -36,6 +36,6 @@ foo (bigger_than_word a, word b, uint8_t c)
   return ret;
 }
 
-/* { dg-final { scan-tree-dump "Folded into: if \\(_\[0-9\]+ == 1\\)" "vrp1" } } */
+/* { dg-final { scan-tree-dump "Folded into: if \\(_\[0-9\]+ == 1\\)" "evrp" } } */
 /* { dg-final { scan-tree-dump-not "Folded into: if \\(_\[0-9\]+ == 2\\)" "vrp1" } } */
-/* { dg-final { scan-tree-dump "Folded into: if \\(_\[0-9\]+ == 3\\)" "vrp1" } } */
+/* { dg-final { scan-tree-dump "Folded into: if \\(_\[0-9\]+ == 3\\)" "evrp" } } */
diff --git a/gcc/timevar.def b/gcc/timevar.def
index 362aa6e..8d308ac 100644
--- a/gcc/timevar.def
+++ b/gcc/timevar.def
@@ -147,6 +147,7 @@ DEFTIMEVAR (TV_TREE_CFG		     , "tree CFG construction")
 DEFTIMEVAR (TV_TREE_CLEANUP_CFG	     , "tree CFG cleanup")
 DEFTIMEVAR (TV_TREE_TAIL_MERGE       , "tree tail merge")
 DEFTIMEVAR (TV_TREE_VRP              , "tree VRP")
+DEFTIMEVAR (TV_TREE_EARLY_VRP        , "tree Early VRP")
 DEFTIMEVAR (TV_TREE_COPY_PROP        , "tree copy propagation")
 DEFTIMEVAR (TV_FIND_REFERENCED_VARS  , "tree find ref. vars")
 DEFTIMEVAR (TV_TREE_PTA		     , "tree PTA")
diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
index 36299a6..d836d57 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -440,6 +440,7 @@ extern gimple_opt_pass *make_pass_fre (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_check_data_deps (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_copy_prop (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_isolate_erroneous_paths (gcc::context *ctxt);
+extern gimple_opt_pass *make_pass_early_vrp (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_vrp (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_uncprop (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_return_slot (gcc::context *ctxt);
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 83579e3..de755bc 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -59,6 +59,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "target.h"
 #include "case-cfn-macros.h"
 #include "alloc-pool.h"
+#include "tree-vrp.h"
 #include "domwalk.h"
 
 #define VR_INITIALIZER { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }
@@ -1437,44 +1438,17 @@ op_with_boolean_value_range_p (tree op)
 	  && integer_onep (vr->max));
 }
 
-/* Extract value range information from an ASSERT_EXPR EXPR and store
-   it in *VR_P.  */
+/* Extract value range information for VAR when (OP COND_CODE LIMIT) is
+   true and store it in *VR_P.  */
 
 static void
-extract_range_from_assert (value_range *vr_p, tree expr)
+extract_range_for_var_from_comparison_expr (tree var, enum tree_code cond_code,
+					    tree op, tree limit,
+					    value_range *vr_p)
 {
-  tree var, cond, limit, min, max, type;
+  tree  min, max, type;
   value_range *limit_vr;
-  enum tree_code cond_code;
-
-  var = ASSERT_EXPR_VAR (expr);
-  cond = ASSERT_EXPR_COND (expr);
-
-  gcc_assert (COMPARISON_CLASS_P (cond));
-
-  /* Find VAR in the ASSERT_EXPR conditional.  */
-  if (var == TREE_OPERAND (cond, 0)
-      || TREE_CODE (TREE_OPERAND (cond, 0)) == PLUS_EXPR
-      || TREE_CODE (TREE_OPERAND (cond, 0)) == NOP_EXPR)
-    {
-      /* If the predicate is of the form VAR COMP LIMIT, then we just
-	 take LIMIT from the RHS and use the same comparison code.  */
-      cond_code = TREE_CODE (cond);
-      limit = TREE_OPERAND (cond, 1);
-      cond = TREE_OPERAND (cond, 0);
-    }
-  else
-    {
-      /* If the predicate is of the form LIMIT COMP VAR, then we need
-	 to flip around the comparison code to create the proper range
-	 for VAR.  */
-      cond_code = swap_tree_comparison (TREE_CODE (cond));
-      limit = TREE_OPERAND (cond, 0);
-      cond = TREE_OPERAND (cond, 1);
-    }
-
   limit = avoid_overflow_infinity (limit);
-
   type = TREE_TYPE (var);
   gcc_assert (limit != var);
 
@@ -1517,15 +1491,15 @@ extract_range_from_assert (value_range *vr_p, tree expr)
      as well build the range [b_4, +INF] for it.
      One special case we handle is extracting a range from a
      range test encoded as (unsigned)var + CST <= limit.  */
-  if (TREE_CODE (cond) == NOP_EXPR
-      || TREE_CODE (cond) == PLUS_EXPR)
+  if (TREE_CODE (op) == NOP_EXPR
+      || TREE_CODE (op) == PLUS_EXPR)
     {
-      if (TREE_CODE (cond) == PLUS_EXPR)
+      if (TREE_CODE (op) == PLUS_EXPR)
         {
-          min = fold_build1 (NEGATE_EXPR, TREE_TYPE (TREE_OPERAND (cond, 1)),
-			     TREE_OPERAND (cond, 1));
+          min = fold_build1 (NEGATE_EXPR, TREE_TYPE (TREE_OPERAND (op, 1)),
+			     TREE_OPERAND (op, 1));
           max = int_const_binop (PLUS_EXPR, limit, min);
-	  cond = TREE_OPERAND (cond, 0);
+	  op = TREE_OPERAND (op, 0);
 	}
       else
 	{
@@ -1709,6 +1683,41 @@ extract_range_from_assert (value_range *vr_p, tree expr)
   vrp_intersect_ranges (vr_p, get_value_range (var));
 }
 
+/* Extract value range information from an ASSERT_EXPR EXPR and store
+   it in *VR_P.  */
+
+static void
+extract_range_from_assert (value_range *vr_p, tree expr)
+{
+  tree var = ASSERT_EXPR_VAR (expr);
+  tree cond = ASSERT_EXPR_COND (expr);
+  tree limit, op;
+  enum tree_code cond_code;
+  gcc_assert (COMPARISON_CLASS_P (cond));
+
+  /* Find VAR in the ASSERT_EXPR conditional.  */
+  if (var == TREE_OPERAND (cond, 0)
+      || TREE_CODE (TREE_OPERAND (cond, 0)) == PLUS_EXPR
+      || TREE_CODE (TREE_OPERAND (cond, 0)) == NOP_EXPR)
+    {
+      /* If the predicate is of the form VAR COMP LIMIT, then we just
+	 take LIMIT from the RHS and use the same comparison code.  */
+      cond_code = TREE_CODE (cond);
+      limit = TREE_OPERAND (cond, 1);
+      op = TREE_OPERAND (cond, 0);
+    }
+  else
+    {
+      /* If the predicate is of the form LIMIT COMP VAR, then we need
+	 to flip around the comparison code to create the proper range
+	 for VAR.  */
+      cond_code = swap_tree_comparison (TREE_CODE (cond));
+      limit = TREE_OPERAND (cond, 0);
+      op = TREE_OPERAND (cond, 1);
+    }
+  extract_range_for_var_from_comparison_expr (var, cond_code, op,
+					      limit, vr_p);
+}
 
 /* Extract range information from SSA name VAR and store it in VR.  If
    VAR has an interesting range, use it.  Otherwise, create the
@@ -10144,7 +10153,7 @@ finalize_jump_threads (void)
 /* Traverse all the blocks folding conditionals with known ranges.  */
 
 static void
-vrp_finalize (bool jump_thread_p, bool warn_array_bounds_p)
+vrp_finalize (bool early_vrp_p, bool warn_array_bounds_p)
 {
   size_t i;
 
@@ -10185,7 +10194,7 @@ vrp_finalize (bool jump_thread_p, bool warn_array_bounds_p)
 
   /* We must identify jump threading opportunities before we release
      the datastructures built by VRP.  */
-  if (jump_thread_p)
+  if (!early_vrp_p)
     identify_jump_threads ();
 
   /* Free allocated memory.  */
@@ -10201,6 +10210,229 @@ vrp_finalize (bool jump_thread_p, bool warn_array_bounds_p)
 }
 
 
+/* Visit the basic blocks in the dominance order and set the Value Ranges (VR)
+   for SSA_NAMEs in the scope.  Use this VR to discover more VRs.  Restore the
+   old VR once the scope is exited.  */
+
+static bool
+evrp_visit_phi_node_local (gphi *phi)
+{
+  size_t i;
+  tree lhs = PHI_RESULT (phi);
+  value_range vr_result = VR_INITIALIZER;
+  bool first = true;
+  int edges;
+
+  edges = 0;
+  for (i = 0; i < gimple_phi_num_args (phi); i++)
+    {
+      edge e = gimple_phi_arg_edge (phi, i);
+      tree arg = PHI_ARG_DEF (phi, i);
+      value_range vr_arg = VR_INITIALIZER;
+      ++edges;
+
+      /* If there is a back-edge, set the result to VARYING.  */
+      if (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX))
+	{
+	  set_value_range_to_varying (&vr_result);
+	  break;
+	}
+
+      if (TREE_CODE (arg) == SSA_NAME)
+	vr_arg = *(get_value_range (arg));
+      else
+	set_value_range_to_varying (&vr_arg);
+
+      /* If any of the RHS value is VARYING, set the result to VARYING.  */
+      if ((vr_arg.type != VR_RANGE)
+	  && (vr_arg.type != VR_ANTI_RANGE))
+	{
+	  set_value_range_to_varying (&vr_result);
+	  break;
+	}
+
+      /* Set/meet the RHS value range with the result so far.  */
+      if (first)
+	set_value_range (&vr_result, vr_arg.type, vr_arg.min,
+			 vr_arg.max, vr_arg.equiv);
+      else
+	vrp_meet (&vr_result, &vr_arg);
+      first = false;
+      if (vr_result.type == VR_VARYING)
+	break;
+    }
+
+  /* Check if the value range has changed and return accordingly.  */
+  if (update_value_range (lhs, &vr_result))
+    return true;
+  else
+    return false;
+}
+
+/* evrp_dom_walker visits the basic blocks in the dominance order and set the
+   Value Ranges (VR) for SSA_NAMEs in the scope.  Use this VR to discover
+   more VRs.  */
+
+class evrp_dom_walker : public dom_walker
+{
+public:
+  evrp_dom_walker ()
+    : dom_walker (CDI_DOMINATORS), stack (10) {}
+
+  virtual edge before_dom_children (basic_block);
+  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);
+
+  /* Cond_stack holds the old VR.  */
+  auto_vec<std::pair <const_tree, value_range*>, 0 > stack;
+};
+
+/* See if there is any new scope is entered with new VR and set that VR to
+   ssa_name before visiting the statements in the scope.  */
+
+edge evrp_dom_walker::before_dom_children (basic_block bb)
+{
+  value_range *new_vr = NULL;
+  tree op0 = NULL_TREE;
+  if (single_pred_p (bb))
+    {
+      edge e = single_pred_edge (bb);
+      value_range vr = VR_INITIALIZER;
+      gimple *stmt = last_stmt (e->src);
+
+      if (stmt
+	  && gimple_code (stmt) == GIMPLE_COND
+	  && INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt))))
+	{
+	  op0 = gimple_cond_lhs (stmt);
+	  tree op1 = gimple_cond_rhs (stmt);
+	  tree_code code = gimple_cond_code (stmt);
+	  value_range *old_vr = get_value_range (op0);
+
+	  if (TREE_OVERFLOW_P (op1))
+	    op1 = drop_tree_overflow (op1);
+
+	  /* If condition is false, invert the cond.  */
+	  if (e->flags & EDGE_FALSE_VALUE)
+	    code = invert_tree_comparison (gimple_cond_code (stmt),
+					   HONOR_NANS (op0));
+	  /* 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);
+
+  /* Visit PHI stmts and discover any new VRs possible.  */
+  gimple_stmt_iterator gsi;
+  for (gphi_iterator gpi = gsi_start_phis (bb);
+       !gsi_end_p (gpi); gsi_next (&gpi))
+    {
+      gphi *phi = gpi.phi ();
+      if (stmt_interesting_for_vrp (phi))
+	evrp_visit_phi_node_local (phi);
+    }
+
+  /* Visit all other stmts and discover any new VRs possible.  */
+  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+    {
+      gimple *stmt = gsi_stmt (gsi);
+      edge taken_edge;
+      tree output;
+      /* TODO, if found taken_edge, we should visit (return it) and travel
+	 again to improve VR as done in DOM/SCCVN optimizations.  It should
+	 be done carefully as stmts might prematurely leave a BB like
+	 in EH.  */
+      if (stmt_interesting_for_vrp (stmt))
+	{
+	  vrp_visit_stmt (stmt, &taken_edge, &output);
+	  if (fold_stmt (&gsi, follow_single_use_edges))
+	    update_stmt (gsi_stmt (gsi));
+	}
+    }
+  return NULL;
+}
+
+/* Restore/Pop VRs valid only for BB when we leave BB.  */
+
+void evrp_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
+{
+  gcc_checking_assert (!stack.is_empty ());
+  const_tree var = stack.last ().first;
+  pop_value_range (var);
+}
+
+/* Push the Value Range of VAR to the stack and upadate it with new VR.  */
+
+void evrp_dom_walker::push_value_range (const_tree var, value_range *vr)
+{
+  if  (vr != NULL)
+    {
+      unsigned ver = SSA_NAME_VERSION (var);
+      gcc_checking_assert (vr_value);
+      stack.safe_push (std::make_pair (var, vr_value[ver]));
+
+      if (ver < num_vr_values)
+	vr_value[ver] = vr;
+    }
+  else
+    stack.safe_push (std::make_pair (var, vr));
+}
+
+/* Pop the Value Range from the vrp_stack and update VAR with it.  */
+
+value_range *evrp_dom_walker::pop_value_range (const_tree var)
+{
+  value_range *vr = stack.last ().second;
+  if (vr != NULL)
+    {
+      unsigned ver = SSA_NAME_VERSION (var);
+      gcc_checking_assert (var == stack.last ().first);
+      gcc_checking_assert (vr_value);
+
+      if (ver < num_vr_values)
+	vr_value[ver] = vr;
+    }
+  stack.pop ();
+  return vr;
+}
+
+
+/* Main entry point for the early vrp pass which is a simplified non-iterative
+   version of VRP.  Value ranges discovered in early vrp will be used by ipa-vrp.  */
+
+static unsigned int
+execute_early_vrp ()
+{
+  basic_block bb;
+  edge e;
+  edge_iterator ei;
+
+  calculate_dominance_info (CDI_DOMINATORS);
+  vrp_initialize ();
+  FOR_EACH_BB_FN (bb, cfun)
+    {
+      FOR_EACH_EDGE (e, ei, bb->preds)
+	e->flags |= EDGE_EXECUTABLE;
+    }
+
+  evrp_dom_walker walker;
+  walker.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun));
+
+  vrp_finalize (true, false);
+  return 0;
+}
+
 /* Main entry point to VRP (Value Range Propagation).  This pass is
    loosely based on J. R. C. Patterson, ``Accurate Static Branch
    Prediction by Value Range Propagation,'' in SIGPLAN Conference on
@@ -10270,7 +10502,7 @@ execute_vrp (bool warn_array_bounds_p)
 
   vrp_initialize ();
   ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node);
-  vrp_finalize (true, warn_array_bounds_p);
+  vrp_finalize (false, warn_array_bounds_p);
 
   free_numbers_of_iterations_estimates (cfun);
 
@@ -10368,3 +10600,41 @@ make_pass_vrp (gcc::context *ctxt)
 {
   return new pass_vrp (ctxt);
 }
+
+namespace {
+
+const pass_data pass_data_early_vrp =
+{
+  GIMPLE_PASS, /* type */
+  "evrp", /* name */
+  OPTGROUP_NONE, /* optinfo_flags */
+  TV_TREE_EARLY_VRP, /* tv_id */
+  PROP_ssa, /* properties_required */
+  0, /* properties_provided */
+  0, /* properties_destroyed */
+  0, /* todo_flags_start */
+  ( TODO_cleanup_cfg | TODO_update_ssa | TODO_verify_all ),
+};
+
+class pass_early_vrp : public gimple_opt_pass
+{
+public:
+  pass_early_vrp (gcc::context *ctxt)
+    : gimple_opt_pass (pass_data_early_vrp, ctxt)
+    {}
+
+  /* opt_pass methods: */
+  opt_pass * clone () { return new pass_early_vrp (m_ctxt); }
+  virtual bool gate (function *) { return flag_tree_early_vrp != 0; }
+  virtual unsigned int execute (function *)
+    { return execute_early_vrp (); }
+
+}; // class pass_vrp
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_early_vrp (gcc::context *ctxt)
+{
+  return new pass_early_vrp (ctxt);
+}
+
-- 
1.9.1