diff mbox

[RFC,IPA-VRP] Early VRP Implementation

Message ID e7d718c3-405a-ddd3-45be-e16f989bc91c@linaro.org
State New
Headers show

Commit Message

Kugan Vivekanandarajah July 22, 2016, 12:10 p.m. UTC 
Hi Richard,

Thanks for the review.

On 18/07/16 21:51, Richard Biener wrote:
> On Fri, Jul 15, 2016 at 9:33 AM, kugan
> <kugan.vivekanandarajah@linaro.org> wrote:
>> Hi Andrew,
>>
>> On 15/07/16 17:28, Andrew Pinski wrote:
>>>
>>> On Fri, Jul 15, 2016 at 12:08 AM, kugan
>>> <kugan.vivekanandarajah@linaro.org> wrote:
>>>>
>>>> Hi Andrew,
>>>>
>>>>> Why separate out early VRP from tree-vrp?  Just a little curious.
>>>>
>>>>
>>>>
>>>> It is based on the discussion in
>>>> https://gcc.gnu.org/ml/gcc/2016-01/msg00069.html.
>>>> In summary, conclusion (based on my understanding) was to implement a
>>>> simplified VRP algorithm that doesn't require ASSERT_EXPR insertion.
>>>
>>>
>>> But I don't see why you are moving it from tree-vrp.c .  That was my
>>> question, you pointing to that discussion does not say to split it
>>> into a new file and expose these interfaces.
>>>
>>
>> Are you saying that I should keep this part of tree-vrp.c. I am happy to do
>> that if this is considered the best approach.
>
> Yes, I think that's the best approach.
>
Thanks. Moved it into tree-vrp.c now.

> Can you, as a refactoring before your patch, please change VRP to use
> an alloc-pool
> for allocating value_range?  The DOM-based VRP will add a lot of
> malloc/free churn
> otherwise.
>
> Generally watch coding-style such as  missed function comments.
>
> As you do a non-iterating VRP and thus do not visit back-edges you don't need
> to initialize loops or SCEV nor do you need loop-closed SSA.
>
> As you do a DOM-based VRP using SSA propagator stuff like ssa_prop_result
> doesn't make any sense.

I have removed it.
>
> +edge evrp_dom_walker::before_dom_children (basic_block bb)
> +{
> +  /* If we are going out of scope, restore the old VR.  */
> +  while (!cond_stack.is_empty ()
> +        && !dominated_by_p (CDI_DOMINATORS, bb, cond_stack.last ().first))
> +    {
> +      tree var = cond_stack.last ().second.first;
> +      value_range *vr = cond_stack.last ().second.second;
> +      value_range *vr_to_del = get_value_range (var);
> +      XDELETE (vr_to_del);
> +      change_value_range (var, vr);
> +      cond_stack.pop ();
> +    }
>
> that should be in after_dom_children I think and use a marker instead
> of a DOM query.
> See other examples like DOM itself or SCCVN.
>

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

>
> 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?
>
> +         /* 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.

Thanks,
Kugan

gcc/ChangeLog:

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

	* common.opt: New option -ftree-evrp.
	* doc/invoke.texi: Document -ftree-evrp.
	* passes.def: Define new pass_early_vrp.
	* timevar.def: Define new TV_TREE_EARLY_VRP.
	* tree-pass.h (make_pass_early_vrp): New.
	* tree-vrp.c (extract_range_for_var_from_comparison_expr): New.
	(extract_range_from_assert): Call
	extract_range_for_var_from_comparison_expr.
	(push_value_range): New.
	(pop_value_range): Likewise.
	(evrp_visit_phi_node_local): Likewise.
	(edge evrp_dom_walker::before_dom_children): Likewise.
	(void evrp_dom_walker::after_dom_children): Likewise.
	(void evrp_dom_walker::finalize_dom_walker): Likewise.
	(execute_early_vrp): Likewise.
	(make_pass_early_vrp): Likewise.


gcc/testsuite/ChangeLog:

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

	* gcc.dg/tree-ssa/evrp1.c: New test.
	* gcc.dg/tree-ssa/evrp2.c: New test.
	* gcc.dg/tree-ssa/evrp3.c: New test.
	* g++.dg/tree-ssa/pr31146-2.C: Run with -fno-tree-evrp as evrp also
	does the same transformation.
	* gcc.dg/tree-ssa/pr20318.c: Likewise.
	* gcc.dg/tree-ssa/pr25382.c: Likewise.
	* gcc.dg/tree-ssa/pr68431.c: Likewise.
	* gcc.dg/tree-ssa/vrp19.c: Likewise.
	* gcc.dg/tree-ssa/vrp23.c: Likewise.
	* gcc.dg/tree-ssa/vrp24.c: Likewise.
	* gcc.dg/tree-ssa/vrp58.c: Likewise.
	* gcc.dg/tree-ssa/vrp67.c: Likewise.
	* gcc.dg/tree-ssa/vrp98.c: Likewise.
	* gcc.dg/tree-ssa/vrp19.c: Likewise.
	* gcc.dg/tree-ssa/vrp23.c: Likewise.
	* gcc.dg/tree-ssa/vrp24.c: Likewise.
	* gcc.dg/tree-ssa/vrp58.c: Likewise.
	* gcc.dg/tree-ssa/vrp67.c: Likewise.
	* gcc.dg/tree-ssa/vrp98.c: Likewise.
	* gcc.dg/tree-ssa/pr22117.c: Run with -fno-tree-evrp as predicate is
	optimized away before vrp1.

Comments

Richard Biener July 25, 2016, 11:18 a.m. UTC | #1 
On Fri, Jul 22, 2016 at 2:10 PM, kugan
<kugan.vivekanandarajah@linaro.org> wrote:
> Hi Richard,
>
> Thanks for the review.
>
> On 18/07/16 21:51, Richard Biener wrote:
>>
>> On Fri, Jul 15, 2016 at 9:33 AM, kugan
>> <kugan.vivekanandarajah@linaro.org> wrote:
>>>
>>> Hi Andrew,
>>>
>>> On 15/07/16 17:28, Andrew Pinski wrote:
>>>>
>>>>
>>>> On Fri, Jul 15, 2016 at 12:08 AM, kugan
>>>> <kugan.vivekanandarajah@linaro.org> wrote:
>>>>>
>>>>>
>>>>> Hi Andrew,
>>>>>
>>>>>> Why separate out early VRP from tree-vrp?  Just a little curious.
>>>>>
>>>>>
>>>>>
>>>>>
>>>>> It is based on the discussion in
>>>>> https://gcc.gnu.org/ml/gcc/2016-01/msg00069.html.
>>>>> In summary, conclusion (based on my understanding) was to implement a
>>>>> simplified VRP algorithm that doesn't require ASSERT_EXPR insertion.
>>>>
>>>>
>>>>
>>>> But I don't see why you are moving it from tree-vrp.c .  That was my
>>>> question, you pointing to that discussion does not say to split it
>>>> into a new file and expose these interfaces.
>>>>
>>>
>>> Are you saying that I should keep this part of tree-vrp.c. I am happy to
>>> do
>>> that if this is considered the best approach.
>>
>>
>> Yes, I think that's the best approach.
>>
> Thanks. Moved it into tree-vrp.c now.
>
>> Can you, as a refactoring before your patch, please change VRP to use
>> an alloc-pool
>> for allocating value_range?  The DOM-based VRP will add a lot of
>> malloc/free churn
>> otherwise.
>>
>> Generally watch coding-style such as  missed function comments.
>>
>> As you do a non-iterating VRP and thus do not visit back-edges you don't
>> need
>> to initialize loops or SCEV nor do you need loop-closed SSA.
>>
>> As you do a DOM-based VRP using SSA propagator stuff like ssa_prop_result
>> doesn't make any sense.
>
>
> I have removed it.
>>
>>
>> +edge evrp_dom_walker::before_dom_children (basic_block bb)
>> +{
>> +  /* If we are going out of scope, restore the old VR.  */
>> +  while (!cond_stack.is_empty ()
>> +        && !dominated_by_p (CDI_DOMINATORS, bb, cond_stack.last
>> ().first))
>> +    {
>> +      tree var = cond_stack.last ().second.first;
>> +      value_range *vr = cond_stack.last ().second.second;
>> +      value_range *vr_to_del = get_value_range (var);
>> +      XDELETE (vr_to_del);
>> +      change_value_range (var, vr);
>> +      cond_stack.pop ();
>> +    }
>>
>> that should be in after_dom_children I think and use a marker instead
>> of a DOM query.
>> See other examples like DOM itself or SCCVN.
>>
>
> Done.

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

>>
>> +         /* 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);
...

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.

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

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

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.

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

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

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

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)

Thanks,
Richard.


> Thanks,
> Kugan
>
> gcc/ChangeLog:
>
> 2016-07-22  Kugan Vivekanandarajah  <kuganv@linaro.org>
>
>         * common.opt: New option -ftree-evrp.
>         * doc/invoke.texi: Document -ftree-evrp.
>         * passes.def: Define new pass_early_vrp.
>         * timevar.def: Define new TV_TREE_EARLY_VRP.
>         * tree-pass.h (make_pass_early_vrp): New.
>         * tree-vrp.c (extract_range_for_var_from_comparison_expr): New.
>         (extract_range_from_assert): Call
>         extract_range_for_var_from_comparison_expr.
>         (push_value_range): New.
>         (pop_value_range): Likewise.
>         (evrp_visit_phi_node_local): Likewise.
>         (edge evrp_dom_walker::before_dom_children): Likewise.
>         (void evrp_dom_walker::after_dom_children): Likewise.
>         (void evrp_dom_walker::finalize_dom_walker): Likewise.
>         (execute_early_vrp): Likewise.
>         (make_pass_early_vrp): Likewise.
>
>
> gcc/testsuite/ChangeLog:
>
> 2016-07-22  Kugan Vivekanandarajah  <kuganv@linaro.org>
>
>         * gcc.dg/tree-ssa/evrp1.c: New test.
>         * gcc.dg/tree-ssa/evrp2.c: New test.
>         * gcc.dg/tree-ssa/evrp3.c: New test.
>         * g++.dg/tree-ssa/pr31146-2.C: Run with -fno-tree-evrp as evrp also
>         does the same transformation.
>         * gcc.dg/tree-ssa/pr20318.c: Likewise.
>         * gcc.dg/tree-ssa/pr25382.c: Likewise.
>         * gcc.dg/tree-ssa/pr68431.c: Likewise.
>         * gcc.dg/tree-ssa/vrp19.c: Likewise.
>         * gcc.dg/tree-ssa/vrp23.c: Likewise.
>         * gcc.dg/tree-ssa/vrp24.c: Likewise.
>         * gcc.dg/tree-ssa/vrp58.c: Likewise.
>         * gcc.dg/tree-ssa/vrp67.c: Likewise.
>         * gcc.dg/tree-ssa/vrp98.c: Likewise.
>         * gcc.dg/tree-ssa/vrp19.c: Likewise.
>         * gcc.dg/tree-ssa/vrp23.c: Likewise.
>         * gcc.dg/tree-ssa/vrp24.c: Likewise.
>         * gcc.dg/tree-ssa/vrp58.c: Likewise.
>         * gcc.dg/tree-ssa/vrp67.c: Likewise.
>         * gcc.dg/tree-ssa/vrp98.c: Likewise.
>         * gcc.dg/tree-ssa/pr22117.c: Run with -fno-tree-evrp as predicate is
>         optimized away before vrp1.
diff mbox

Patch

From d2b49fe0fc7d3b2b1f130e448834ffee0deb981a 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                            | 303 +++++++++++++++++++++++++++++-
 20 files changed, 382 insertions(+), 28 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..1e59d45 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -102,6 +102,7 @@  along with GCC; see the file COPYING3.  If not see
 	     early optimizations again.  It is thus good idea to do this
 	      late.  */
 	  NEXT_PASS (pass_split_functions);
+	  NEXT_PASS (pass_early_vrp);
       POP_INSERT_PASSES ()
       NEXT_PASS (pass_release_ssa_names);
       NEXT_PASS (pass_rebuild_cgraph_edges);
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 a318d39..20b4a33 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -60,6 +60,7 @@  along with GCC; see the file COPYING3.  If not see
 #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,19 +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
+/* Extract value range information for VAR when COND 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 (value_range *vr_p,
+					    tree var, tree cond)
 {
-  tree var, cond, limit, min, max, type;
+  tree limit, 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.  */
@@ -1709,6 +1708,16 @@  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);
+  extract_range_for_var_from_comparison_expr (vr_p, var, cond);
+}
 
 /* Extract range information from SSA name VAR and store it in VR.  If
    VAR has an interesting range, use it.  Otherwise, create the
@@ -10201,6 +10210,250 @@  vrp_finalize (bool jump_thread_p, bool warn_array_bounds_p)
 }
 
 
+/* vrp_stack for maintaining value ranges in the scope and to update.  The
+   order in which variable are pushed and poped must be the same.
+   I.e. if a VR for variable VAR is pushed, it must be poped first.  */
+
+static vec<std::pair <const_tree, value_range*> > vrp_stack (vNULL);
+
+/* Push the Value Range of VAR to the stack and upadate it with new VR.  */
+
+void push_value_range (const_tree var, value_range *vr)
+{
+  unsigned ver = SSA_NAME_VERSION (var);
+  gcc_checking_assert (vr_value);
+  vrp_stack.safe_push (std::make_pair (var, vr_value[ver]));
+
+  if (ver < num_vr_values)
+    vr_value[ver] = vr;
+}
+
+/* Pop the Value Range from the vrp_stack and update VAR with it.  */
+
+value_range *pop_value_range (const_tree var)
+{
+  unsigned ver = SSA_NAME_VERSION (var);
+  value_range *vr = vrp_stack.last ().second;
+  gcc_checking_assert (var == vrp_stack.last ().first);
+  vrp_stack.pop ();
+  gcc_checking_assert (vr_value);
+
+  if (ver < num_vr_values)
+      vr_value[ver] = vr;
+  return vr;
+}
+
+/* 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), cond_stack (vNULL) {}
+
+  void finalize_dom_walker ();
+  virtual edge before_dom_children (basic_block);
+  virtual void after_dom_children (basic_block);
+
+  /* Cond_stack holds the old VR.  */
+  vec<std::pair <basic_block, tree> > cond_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)
+{
+  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))))
+	{
+	  tree 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);
+
+	  /* Discover VR when condition is true.  */
+	  if (e->flags & EDGE_TRUE_VALUE
+	      && !TREE_OVERFLOW_P (op0)
+	      && !TREE_OVERFLOW_P (op1))
+	    {
+	      tree cond = build2 (code, boolean_type_node, op0, op1);
+	      extract_range_for_var_from_comparison_expr (&vr, op0, cond);
+	      if (old_vr->type == VR_RANGE || old_vr->type == VR_ANTI_RANGE)
+		vrp_intersect_ranges (&vr, old_vr);
+	    }
+	  /* Discover VR when condition is false.  */
+	  else if (e->flags & EDGE_FALSE_VALUE
+	      && !TREE_OVERFLOW_P (op0)
+	      && !TREE_OVERFLOW_P (op1))
+	    {
+	      tree_code code
+		= invert_tree_comparison (gimple_cond_code (stmt),
+					  HONOR_NANS (op0));
+	      tree cond = build2 (code, boolean_type_node, op0, op1);
+	      extract_range_for_var_from_comparison_expr (&vr, op0, cond);
+	      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 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));
+	      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);
+    }
+  return NULL;
+}
+
+/* Restore/Pop VRs valid only for BB when we leave BB.  */
+
+void evrp_dom_walker::after_dom_children (basic_block bb)
+{
+  if (!cond_stack.is_empty ()
+      && bb == cond_stack.last ().first)
+    {
+      tree var = cond_stack.last ().second;
+      pop_value_range (var);
+      cond_stack.pop ();
+    }
+}
+
+/* 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 ();
+    }
+}
+
+/* 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));
+  walker.finalize_dom_walker ();
+
+  vrp_finalize (false, 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
@@ -10368,3 +10621,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