diff mbox

[RFC,IPA-VRP] Early VRP Implementation

Message ID 2fc6782e-fbb8-c955-c3a7-f2e9b8845134@linaro.org
State New
Headers show

Commit Message

Kugan Vivekanandarajah Sept. 20, 2016, 2:05 a.m. UTC 
Hi Richard,

Thanks for the review.

On 19/09/16 22:56, Richard Biener wrote:
> On Sun, Sep 18, 2016 at 10:50 PM, kugan

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

>> Hi Richard,

>>

>>

>>

>> On 16/09/16 20:21, Richard Biener wrote:

>>>

>>> On Fri, Sep 16, 2016 at 7:59 AM, kugan

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

>>>>

>>>> Hi Richard,

>>>>

>>>> Thanks for the review.

>>>>

>>>> On 14/09/16 22:04, Richard Biener wrote:

>>>>>

>>>>>

>>>>> On Tue, Aug 23, 2016 at 4:11 AM, Kugan Vivekanandarajah

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

>>>>>>

>>>>>>

>>>>>> Hi,

>>>>>>

>>>>>> On 19 August 2016 at 21:41, Richard Biener <richard.guenther@gmail.com>

>>>>>> wrote:

>>>>>>>

>>>>>>>

>>>>>>> On Tue, Aug 16, 2016 at 9:45 AM, kugan

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

>>>>>>>>

>>>>>>>>

>>>>>>>> Hi Richard,

>>>>

>>>>

>>>>

>>>>>>>> I am now having -ftree-evrp which is enabled all the time. But This

>>>>>>>> will

>>>>>>>> only be used for disabling the early-vrp. That is, early-vrp will be

>>>>>>>> run

>>>>>>>> when ftree-vrp is enabled and ftree-evrp is not explicitly disabled.

>>>>>>>> Is

>>>>>>>> this

>>>>>>>> OK?

>>>>>>>

>>>>>>>

>>>>>>>

>>>>>>> Why would one want to disable early-vrp?  I see you do this in the

>>>>>>> testsuite

>>>>>>> for non-early VRP unit-tests but using -fdisable-tree-evrp1 there

>>>>>>> would be ok as well.

>>>>>>

>>>>>>

>>>>>>

>>>>>> Removed it altogether. I though that you wanted a way to disable

>>>>>> early-vrp for testing purposes.

>>>>>

>>>>>

>>>>>

>>>>> But there is via the generic -fdisable-tree-DUMPFILE way.

>>>>

>>>>

>>>>

>>>> OK. I didnt know about that.

>>>>

>>>>

>>>>>>> Note that you want to have a custom valueize function instead of just

>>>>>>> follow_single_use_edges as you want to valueize all SSA names

>>>>>>> according

>>>>>>> to their lattice value (if it has a single value).  You can use

>>>>>>> vrp_valueize

>>>>>>> for this though that gets you non-single-use edge following as well.

>>>>>>> Eventually it's going to be cleaner to do what the SSA propagator does

>>>>>>> and

>>>>>>> before folding do

>>>>>>>

>>>>>>>    did_replace = replace_uses_in (stmt, vrp_valueize);

>>>>>>>    if (fold_stmt (&gsi, follow_single_use_edges)

>>>>>>>        || did_replace)

>>>>>>>      update_stmt (gsi_stmt (gsi));

>>>>>>>

>>>>>>> exporting replace_uses_in for this is ok.  I guess I prefer this for

>>>>>>> now.

>>>>>>

>>>>>>

>>>>>>

>>>>>> I also added the above.  I noticed that I need

>>>>>> recompute_tree_invariant_for_addr_expr as in ssa_propagate. My initial

>>>>>> implementation also had gimple_purge_all_dead_eh_edges and

>>>>>> fixup_noreturn_call as in ssa_propagat but I thinj that is not needed

>>>>>> as it would be done at the end of the pass.

>>>>>

>>>>>

>>>>>

>>>>> I don't see this being done at the end of the pass.  So please

>>>>> re-instantiate

>>>>> that parts.

>>>>

>>>>

>>>>

>>>> I have copied these part as well.

>>>>

>>>>>> With this I noticed more stmts are folded before vrp1. This required

>>>>>> me to adjust some testcases.

>>>>>>

>>>>>>>

>>>>>>> Overall this now looks good apart from the folding and the

>>>>>>> VR_INITIALIZER thing.

>>>>>>>

>>>>>>> You can commit the already approved refactoring changes and combine

>>>>>>> this

>>>>>>> patch with the struct value_range move, this way I can more easily

>>>>>>> look

>>>>>>> into

>>>>>>> issues with the UNDEFINED thing if you can come up with a testcase

>>>>>>> that

>>>>>>> doesn't work.

>>>>>>>

>>>>>>

>>>>>> I have now committed all the dependent patches.

>>>>>>

>>>>>> Attached patch passes regression and bootstrap except pr33738.C. This

>>>>>> is an unrelated issue as discussed in

>>>>>> https://gcc.gnu.org/ml/gcc-patches/2016-08/msg01386.html

>>>>>>

>>>>>> Is this OK?

>>>>>

>>>>>

>>>>>

>>>>> +/* Initialize local data structures for VRP.  If DOM_P is true,

>>>>> +   we will be calling this from early_vrp where value range propagation

>>>>> +   is done by visiting stmts in dominator tree.  ssa_propagate engine

>>>>> +   is not used in this case and that part of the ininitialization will

>>>>> +   be skipped.  */

>>>>> +

>>>>> +static void

>>>>> +vrp_initialize ()

>>>>>

>>>>> comment needs updating now.

>>>>>

>>>> Done.

>>>>

>>>>>

>>>>>  static void

>>>>> -extract_range_from_phi_node (gphi *phi, value_range *vr_result)

>>>>> +extract_range_from_phi_node (gphi *phi, value_range *vr_result,

>>>>> +                            bool early_vrp_p)

>>>>>  {

>>>>>

>>>>>

>>>>> I don't think you need this changes now that you have

>>>>> stmt_visit_phi_node_in_dom_p

>>>>> guarding its call.

>>>>

>>>>

>>>>

>>>> OK removed it. That also mean I had to put scev_* in the early_vrp.

>>>>

>>>>

>>>>

>>>>> +static bool

>>>>> +stmt_visit_phi_node_in_dom_p (gphi *phi)

>>>>> +{

>>>>> +  ssa_op_iter iter;

>>>>> +  use_operand_p oprnd;

>>>>> +  tree op;

>>>>> +  value_range *vr;

>>>>> +  FOR_EACH_PHI_ARG (oprnd, phi, iter, SSA_OP_USE)

>>>>> +    {

>>>>> +      op = USE_FROM_PTR (oprnd);

>>>>> +      if (TREE_CODE (op) == SSA_NAME)

>>>>> +       {

>>>>> +         vr = get_value_range (op);

>>>>> +         if (vr->type == VR_UNDEFINED)

>>>>> +           return false;

>>>>> +       }

>>>>> +    }

>>>>>

>>>>> I think this is overly conservative in never allowing UNDEFINED on PHI

>>>>> node args (even if the def was actually visited).  I think that the most

>>>>> easy way to improve this bit would be to actually track visited blocks.

>>>>> You already set the EDGE_EXECUTABLE flag on edges so you could

>>>>> clear BB_VISITED on all blocks and set it in the before_dom_children

>>>>> hook (at the end).  Then the above can be folded into the PHI visiting:

>>>>>

>>>>>     bool has_unvisited_pred = false;

>>>>>     FOR_EACH_EDGE (e, ei, bb->preds)

>>>>>        if (!(e->src->flags & BB_VISITED))

>>>>>          {

>>>>>             has_unvisited_preds = true;

>>>>>             break;

>>>>>          }

>>>>>

>>>> OK done.

>>>>

>>>> I also had to check for uninitialized variables that will have

>>>> VR_UNDEFINED

>>>> as range. We do not visit GIMPLE_NOP.

>>>

>>>

>>> But VR_UNDEFINED of uninitialized variables is fine to use.

>>

>>

>> Indeed. I was really trying to fix another problem with this.

>>

>> The real problem I am facing is:

>>

>> When we have a PHI stmt with one argument as symbolic VR_RANGE and another

>> as VR_UNDEFINED, we will copy VR_RANGE to the PHI result.

>>

>> When we fold the uses of the PHI result with vrp_valueize, we will assign

>> the symbol from VR_RANGE if that is of the form [a, a].

>>

>> However, in replace_uses_in, we dont see if the SSA definition dominates the

>> gimple that uses it. This some times results in ICE.

>

> Indeed -- ccp_lattice_meet avoids this by not merging UNDEF and SSA to SSA.

>

> VRP uses op_with_constant_singleton_value_range for the valueization at

> substitute_and_fold time which only substitutes constants.

>

>> For now, in the vrp_valueize, I have commented out the SSA_NAME part (as

>> shown in the attached patch). With that I can bootstrap and regression test

>> the patch.

>>

>> The fix is to either:

>>

>> 1. Remove SSA_NAME from vrp_valueize. Currently we use vrp_valueize with

>> gimple_fold_stmt_to_constant_1 and accepts only is_gimple_min_invariant.

>> Therefore maybe SSA_NAME is not needed?

>

> Yeah, technically it is not needed.

>

>> 2. Or, in replace_uses_in, see if the stmt dominates operand definition

>> before replacing.

>

> We need to treat the valueization as a "value number" and separately

> keep track of available DEFs we can substitute.  See for example how

> FRE/PRE handle this in eliminate_dom_walker.  The substitute-and-fold

> DOM walker would need to be adjusted similarly (and your copy of it

> in DOM VRP).

>

> Short-cutting this at vrp_valueize will remove some valid foldings to

> constants but I think you can simply use op_with_constant_singleton_value_range

> for the replace_uses_in call.

>

> The patch is ok with that change.


Attached is the patch based on the above comments. I have marked 
gcc/testsuite/g++.dg/warn/pr33738.C as XFAIL and will try to fix this 
based on the discussion from 
https://gcc.gnu.org/ml/gcc-patches/2016-08/msg01386.html

I will commit it after fresh bootstrap and regression testing.

Thanks,
Kugan


>

> Thanks,

> Richard.

>

>>>>

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

>>>>> +      tree lhs = PHI_RESULT (phi);

>>>>> +      value_range vr_result = VR_INITIALIZER;

>>>>> +      if (! has_unvisived_preds

>>>>>            && stmt_interesting_for_vrp (phi)

>>>>> +         && stmt_visit_phi_node_in_dom_p (phi))

>>>

>>>

>>> failed to remove this call to stmt_visit_phi_node_in_dom_p -- whether we

>>> need to

>>> drop to varying is a property that is the same for all PHI nodes in a

>>> block.

>>>

>> Done.

>>

>>>>> +       extract_range_from_phi_node (phi, &vr_result, true);

>>>>> +      else

>>>>> +       set_value_range_to_varying (&vr_result);

>>>>> +      update_value_range (lhs, &vr_result);

>>>>> +    }

>>>>>

>>>>> due to a bug in IRA you need to make sure to un-set BB_VISITED after

>>>>> early-vrp is finished again.

>>>>

>>>>

>>>> OK. Done.

>>>

>>>

>>> You set BB_VISITED in after_dom_children -- that is too late, please

>>> set it at the end

>>> of before_dom_children.  Otherwise it pessimizes handling of the PHIs

>>> in the merge

>>> block of a diamond in case the PHI args are defined in the immediate

>>> dominator.

>>>

>>> As said you need to clear BB_VISITED at the start of evrp as well

>>> (clearing at the end

>>> is just a workaround for a IRA bug).

>>

>> Done.

>>

>>>>>

>>>>> +         /* Try folding stmts with the VR discovered.  */

>>>>> +         bool did_replace = replace_uses_in (stmt, evrp_valueize);

>>>>> +         if (fold_stmt (&gsi, follow_single_use_edges)

>>>>> +             || did_replace)

>>>>> +           update_stmt (gsi_stmt (gsi));

>>>>>

>>>>> you should be able to re-use vrp_valueize here.

>>>>

>>>>

>>>> This issue is vrp_valueize accepts ranges such as [VAR + CST, VAR + CST]

>>>> which we can not set.

>>>

>>>

>>> Oh - that looks like sth we need to fix anyway then.  May I suggest to

>>> change

>>> vrp_valueize to do

>>>

>>>          && (TREE_CODE (vr->min) == SSA_NAME

>>>                 || is_gimple_min_invariant (TREE_CODE (vr->min)))

>>>

>>> which also allows [&a, &a] like constants.

>>

>>

>> Please see the error above.

>>

>>

>>>>>

>>>>> +         def_operand_p def_p = SINGLE_SSA_DEF_OPERAND (stmt,

>>>>> SSA_OP_DEF);

>>>>> +         /* Set the SSA with the value range.  */

>>>>> +         if (def_p

>>>>> +             && TREE_CODE (DEF_FROM_PTR (def_p)) == SSA_NAME

>>>>> +             && INTEGRAL_TYPE_P (TREE_TYPE (DEF_FROM_PTR (def_p))))

>>>>> +           {

>>>>> +             tree def = DEF_FROM_PTR (def_p);

>>>>> +             unsigned ver = SSA_NAME_VERSION (def);

>>>>> +             if ((vr_value[ver]->type == VR_RANGE

>>>>>

>>>>> Use get_value_range () please, not direct access to vr_value.

>>>>>

>>>> Done.

>>>>

>>>>> +                  || vr_value[ver]->type == VR_ANTI_RANGE)

>>>>> +                 && (TREE_CODE (vr_value[ver]->min) == INTEGER_CST)

>>>>> +                 && (TREE_CODE (vr_value[ver]->max) == INTEGER_CST))

>>>>> +               set_range_info (def, vr_value[ver]->type,

>>>>> vr_value[ver]->min,

>>>>> +                               vr_value[ver]->max);

>>>>> +           }

>>>>>

>>>>> Otherwise the patch looks good now (with a lot of improvement

>>>>> possibilities of course).

>>>>

>>>>

>>>> I will work on the improvement after this goes in.

>>>>

>>>> Bootstrapped and regression tested on x86_64-linux-gnu. Does this looks

>>>> OK?

>>>

>>>

>>> Please remove no-op changes like

>>

>> Done.

>>

>>

>>> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr22117.c

>>> b/gcc/testsuite/gcc.dg/tree-ssa/pr22117.c

>>> index 7efdd63..3a433d6 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  -fdump-tree-vrp1" } */

>>>

>>>  void link_error (void);

>>>

>>> @@ -21,4 +21,4 @@ foo (int *p, int q)

>>>      }

>>>  }

>>>

>>> -/* { dg-final { scan-tree-dump-times "Folding predicate r_.* != 0B to

>>> 0" 1 "vrp1" } } */

>>> +/* { dg-final { scan-tree-dump-times "link_error" 0 "vrp1" } } */

>>> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr25382.c

>>> b/gcc/testsuite/gcc.dg/tree-ssa/pr25382.c

>>> index dcf9148..c4fda8b 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-vrp" } */

>>>

>>>  int

>>>  foo (int a)

>>>

>>>

>>> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp46.c

>>> b/gcc/testsuite/gcc.dg/tree-ssa/vrp46.c

>>> index d3c9ed1..5b279a1 100644

>>> --- a/gcc/testsuite/gcc.dg/tree-ssa/vrp46.c

>>> +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp46.c

>>> @@ -27,6 +27,5 @@ func_18 ( int t )

>>>      }

>>>  }

>>>

>>> -/* There should be a single if left.  */

>>>

>>> -/* { dg-final { scan-tree-dump-times "if" 1 "vrp1" } } */

>>> +/* { dg-final { scan-tree-dump-times "if" 0 "vrp1" } } */

>>>

>>> I'm curious -- this is not a dg-run testcase but did you investigate this

>>> isn't generating wrong code now?  At least I can't see how

>>> the if (1 & (t % rhs)) test could vanish.

>>

>> Indeed.This was a mistake and fixed it.

>>

>>

>>> I hope we'll get GIMPLE unit testing finished for GCC 7 so we can add

>>> separate

>>> unit-tests for VRP and EVRP.

>>

>>

>> I will have a look at it.

>>

>> Thanks,

>> Kugan

>>

>>

>>> Thanks,

>>> Richard.

>>>

>>>

>>>> Thanks,

>>>> Kugan

>>>>

>>>>

>>>>

>>>>>

>>>>> Thanks and sorry for the delay,

>>>>> Richard.

>>>>>

>>>>>> Thanks,

>>>>>> Kugan

>>>>>>

>>>>>>

>>>>>>> Thanks,

>>>>>>> Richard.

>>>>>>>

>>>>>>>> I also noticed that g++.dg/warn/pr33738.C testcase is now failing.

>>>>>>>> This

>>>>>>>> is

>>>>>>>> because, with early-vrp setting value range ccp2 is optimizing

>>>>>>>> without

>>>>>>>> issuing a warning. I will look into it.

>>>>>>>>

>>>>>>>> bootstrap and regression testing is in progress.

>>>>>>>>

>>>>>>>> Thanks,

>>>>>>>> Kugan
gcc/ChangeLog:

2016-09-20  Kugan Vivekanandarajah  <kuganv@linaro.org>

	* doc/invoke.texi: Document -fdump-tree-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-ssa-propagate.c: Make replace_uses_in non static.
	* tree-ssa-propagate.h: Export replace_uses_in.
	* tree-vrp.c (extract_range_for_var_from_comparison_expr): New.
	(extract_range_from_assert): Factor out
	extract_range_for_var_from_comparison_expr.
	(vrp_initialize_lattice): New.
	(vrp_initialize): Factor out vrp_initialize_lattice.
	(vrp_valueize): Fix it to reject complex value ranges.
	(vrp_free_lattice): New.
	(evrp_dom_walker::before_dom_children): Likewise.
	(evrp_dom_walker::after_dom_children): Likewise.
	(evrp_dom_walker::push_value_range): Likewise.
	(evrp_dom_walker::pop_value_range): Likewise.
	(execute_early_vrp): Likewise.
	(execute_vrp): Call vrp_initialize_lattice and
	vrp_free_lattice.
	(make_pass_early_vrp): New.


gcc/testsuite/ChangeLog:

2016-09-20  Kugan Vivekanandarajah  <kuganv@linaro.org>

	* g++.dg/tree-ssa/pr31146-2.C: Run with -fno-tree-evrp as evrp also
	does the same transformation.
	* g++.dg/warn/pr33738.C: XFAIL as optimization now happens in ccp.
	* gcc.dg/tree-ssa/evrp1.c: New test.
	* gcc.dg/tree-ssa/evrp2.c: New test.
	* gcc.dg/tree-ssa/evrp3.c: New test.
	* gcc.dg/tree-ssa/pr20657.c: Check for the pattern in evrp dump.
	* gcc.dg/tree-ssa/pr22117.c: Likewise.
	* gcc.dg/tree-ssa/pr61839_2.c: Likewise.
	* gcc.dg/tree-ssa/pr64130.c: Likewise.
	* gcc.dg/tree-ssa/pr37508.c: Change the pattern to be checked as foldong
	now happens early.
	* gcc.dg/tree-ssa/vrp04.c: Likewise.
	* gcc.dg/tree-ssa/vrp06.c: Likewise.
	* gcc.dg/tree-ssa/vrp16.c: Likewise.
	* gcc.dg/tree-ssa/vrp25.c: Likewise.
	* gcc.dg/tree-ssa/vrp67.c: Likewise.
diff mbox

Patch

From 42cef3f7abc956ece46e4303e3a6d68464dde99c Mon Sep 17 00:00:00 2001
From: Kugan Vivekanandarajah <kugan.vivekanandarajah@linaro.org>
Date: Tue, 23 Aug 2016 16:18:30 +1000
Subject: [PATCH 1/3] Add early-vrp

---
 gcc/doc/invoke.texi                       |   5 +
 gcc/passes.def                            |   1 +
 gcc/testsuite/g++.dg/tree-ssa/pr31146-2.C |   2 +-
 gcc/testsuite/g++.dg/warn/pr33738.C       |   4 +-
 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/pr20657.c   |   4 +-
 gcc/testsuite/gcc.dg/tree-ssa/pr22117.c   |   2 +-
 gcc/testsuite/gcc.dg/tree-ssa/pr37508.c   |   2 +-
 gcc/testsuite/gcc.dg/tree-ssa/pr61839_2.c |   8 +-
 gcc/testsuite/gcc.dg/tree-ssa/pr64130.c   |   6 +-
 gcc/testsuite/gcc.dg/tree-ssa/vrp04.c     |   2 +-
 gcc/testsuite/gcc.dg/tree-ssa/vrp06.c     |   4 +-
 gcc/testsuite/gcc.dg/tree-ssa/vrp16.c     |   4 +-
 gcc/testsuite/gcc.dg/tree-ssa/vrp25.c     |   4 +-
 gcc/testsuite/gcc.dg/tree-ssa/vrp67.c     |   2 +-
 gcc/timevar.def                           |   1 +
 gcc/tree-pass.h                           |   1 +
 gcc/tree-ssa-propagate.c                  |   2 +-
 gcc/tree-ssa-propagate.h                  |   1 +
 gcc/tree-vrp.c                            | 467 ++++++++++++++++++++++++++----
 22 files changed, 492 insertions(+), 76 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/doc/invoke.texi b/gcc/doc/invoke.texi
index 87da1f1..9ed9c24 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -12454,6 +12454,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 533157d..9759fed 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..cf4ed33 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-vrp -fdump-tree-forwprop1" } */
 
 #include <new>
 
diff --git a/gcc/testsuite/g++.dg/warn/pr33738.C b/gcc/testsuite/g++.dg/warn/pr33738.C
index 60ee0b4..73e98d5 100644
--- a/gcc/testsuite/g++.dg/warn/pr33738.C
+++ b/gcc/testsuite/g++.dg/warn/pr33738.C
@@ -15,11 +15,11 @@  int GetM1() {
 
 int main() {
  a2 = static_cast<Alpha>(GetM1());
- if (a2 == -1) {	// { dg-warning "always false due" }
+ if (a2 == -1) {	// { dg-warning "always false due" "" { xfail *-*-* } } */
     link_error ();
  }
  a2 = static_cast<Alpha>(GetM1());
- if (-1 == a2) {	// { dg-warning "always false due" }
+ if (-1 == a2) {	// { dg-warning "always false due" "" { xfail *-*-* } } */
     link_error ();
  }
  return 0;
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/pr20657.c b/gcc/testsuite/gcc.dg/tree-ssa/pr20657.c
index 727ca4c..e678231 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr20657.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr20657.c
@@ -3,7 +3,7 @@ 
    statement, which was needed to eliminate the second "if" statement.  */
 
 /* { dg-do compile } */
-/* { dg-options "-O2 -fno-tree-dominator-opts -fno-tree-fre -fdump-tree-vrp1-details" } */
+/* { dg-options "-O2 -fno-tree-dominator-opts -fno-tree-fre -fdump-tree-evrp" } */
 
 int
 foo (int a)
@@ -14,4 +14,4 @@  foo (int a)
   return 0;
 }
 
-/* { dg-final { scan-tree-dump-times "Folding predicate" 1 "vrp1"} } */
+/* { dg-final { scan-tree-dump-times "if" 1 "evrp"} } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr22117.c b/gcc/testsuite/gcc.dg/tree-ssa/pr22117.c
index 7efdd63..01cd33e 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr22117.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr22117.c
@@ -21,4 +21,4 @@  foo (int *p, int q)
     }
 }
 
-/* { dg-final { scan-tree-dump-times "Folding predicate r_.* != 0B to 0" 1 "vrp1" } } */
+/* { dg-final { scan-tree-dump-times "link_error" 0 "vrp1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr37508.c b/gcc/testsuite/gcc.dg/tree-ssa/pr37508.c
index 0963cd9..2ba09af 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr37508.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr37508.c
@@ -46,4 +46,4 @@  int test4 (struct foo2 *x)
   return 0;
 }
 
-/* { dg-final { scan-tree-dump-times "Folding" 2 "vrp1" } } */
+/* { dg-final { scan-tree-dump-times "if" 2 "vrp1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr61839_2.c b/gcc/testsuite/gcc.dg/tree-ssa/pr61839_2.c
index ffa00a7..e44dc57 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr61839_2.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr61839_2.c
@@ -1,6 +1,6 @@ 
 /* PR tree-optimization/61839.  */
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-vrp1" } */
+/* { dg-options "-O2 -fdump-tree-evrp" } */
 /* { dg-require-effective-target int32plus } */
 
 __attribute__ ((noinline))
@@ -47,8 +47,8 @@  int bar2 ()
 
 
 /* Dont optimize 972195717 / 0 in function foo.  */
-/* { dg-final { scan-tree-dump-times "972195717 / _" 1  "vrp1" } } */
+/* { dg-final { scan-tree-dump-times "972195717 / _" 1  "evrp" } } */
 /* Dont optimize 972195717 % 0 in function bar.  */
-/* { dg-final { scan-tree-dump-times "972195717 % _" 1 "vrp1" } } */
+/* { dg-final { scan-tree-dump-times "972195717 % _" 1 "evrp" } } */
 /* Optimize in function bar2.  */
-/* { dg-final { scan-tree-dump-times "972195715 % _" 0 "vrp1" } } */
+/* { dg-final { scan-tree-dump-times "972195715 % _" 0 "evrp" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr64130.c b/gcc/testsuite/gcc.dg/tree-ssa/pr64130.c
index 0b25466..f39bd17 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr64130.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr64130.c
@@ -1,6 +1,6 @@ 
 
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-vrp1" } */
+/* { dg-options "-O2 -fdump-tree-evrp" } */
 
 int funsigned (unsigned a)
 {
@@ -13,6 +13,6 @@  int funsigned2 (unsigned a)
   return (-1 * 0x1ffffffffL) / a == 0;
 }
 
-/* { dg-final { scan-tree-dump ": \\\[2, 8589934591\\\]" "vrp1" } } */
-/* { dg-final { scan-tree-dump ": \\\[-8589934591, -2\\\]" "vrp1" } } */
+/* { dg-final { scan-tree-dump ": \\\[2, 8589934591\\\]" "evrp" } } */
+/* { dg-final { scan-tree-dump ": \\\[-8589934591, -2\\\]" "evrp" } } */
 
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp04.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp04.c
index 61b7a47..67f8f01 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/vrp04.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp04.c
@@ -10,4 +10,4 @@  foo (int a, int b)
       return a + b;
 }
 
-/* { dg-final { scan-tree-dump-times "Folding predicate a_.*to 1" 1 "vrp1" } } */
+/* { dg-final { scan-tree-dump-times "if" 1 "vrp1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp06.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp06.c
index cdad534..c4ce170 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/vrp06.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp06.c
@@ -28,6 +28,6 @@  foo (int i, int j, int a)
   return i + a + j;
 }
 
-/* { dg-final { scan-tree-dump-times "Folding predicate i_\[0-9\]+.*0 to 0" 1 "vrp1" } } */
-/* { dg-final { scan-tree-dump-times "Folding predicate j_\[0-9\]+.*0 to 1" 1 "vrp1" } } */
+/* { dg-final { scan-tree-dump-times "Folding predicate \[i|j\]_\[0-9\]+.*0 to 0" 1 "vrp1" } } */
+/* { dg-final { scan-tree-dump-times "Folding predicate \[i|j\]_\[0-9\]+.*0 to 1" 1 "vrp1" } } */
 /* { dg-final { scan-tree-dump-times "Folding predicate i_\[0-9]+.*j_\[0-9\]+.* to 0" 1 "vrp1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp16.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp16.c
index 8f5d5c8..d09f3ae 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/vrp16.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp16.c
@@ -1,5 +1,5 @@ 
 /* { dg-do compile } */
-/* { dg-options "-O2 -fno-tree-fre -fdump-tree-vrp1-details" } */
+/* { dg-options "-O2 -fno-tree-fre -fdump-tree-evrp" } */
 
 
 extern void abort (void) __attribute__ ((__noreturn__));
@@ -19,5 +19,5 @@  nonlocal_mentioned_p (rtx x)
 	abort ();
 }
 
-/* { dg-final { scan-tree-dump-times "Folding predicate .*to 0" 1 "vrp1" } } */
+/* { dg-final { scan-tree-dump-times "if" 0 "evrp" } } */
 
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp25.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp25.c
index cbc4ec3..a49f079 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/vrp25.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp25.c
@@ -1,5 +1,5 @@ 
 /* { dg-do compile } */
-/* { dg-options "-O2 -fno-tree-fre -fdump-tree-vrp1-details" } */
+/* { dg-options "-O2 -fno-tree-fre -fdump-tree-vrp1" } */
 
 extern void abort ();
 extern void arf ();
@@ -49,5 +49,5 @@  L9:
 /* The second test of (code1 != 53) and the test (D18670 <= 2) are
    both totally subsumed by earlier tests and thus should be folded
    away using VRP.  */
-/* { dg-final { scan-tree-dump-times "Folding predicate" 2 "vrp1" } } */
+/* { dg-final { scan-tree-dump-times "if" 3 "vrp1" } } */
 
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp67.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp67.c
index ef5e8f9..5155f7b 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/vrp67.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp67.c
@@ -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 "if" 3 "vrp1" } } */
diff --git a/gcc/timevar.def b/gcc/timevar.def
index 5f12118..8837832 100644
--- a/gcc/timevar.def
+++ b/gcc/timevar.def
@@ -149,6 +149,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 c0059de..86d797e 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-ssa-propagate.c b/gcc/tree-ssa-propagate.c
index c8cf078..97cfde5 100644
--- a/gcc/tree-ssa-propagate.c
+++ b/gcc/tree-ssa-propagate.c
@@ -863,7 +863,7 @@  static struct prop_stats_d prop_stats;
 /* Replace USE references in statement STMT with the values stored in
    PROP_VALUE. Return true if at least one reference was replaced.  */
 
-static bool
+bool
 replace_uses_in (gimple *stmt, ssa_prop_get_value_fn get_value)
 {
   bool replaced = false;
diff --git a/gcc/tree-ssa-propagate.h b/gcc/tree-ssa-propagate.h
index 30d66a9..1a96976 100644
--- a/gcc/tree-ssa-propagate.h
+++ b/gcc/tree-ssa-propagate.h
@@ -84,5 +84,6 @@  extern void propagate_value (use_operand_p, tree);
 extern void replace_exp (use_operand_p, tree);
 extern void propagate_tree_value (tree *, tree);
 extern void propagate_tree_value_into_stmt (gimple_stmt_iterator *, tree);
+extern bool replace_uses_in (gimple *stmt, ssa_prop_get_value_fn get_value);
 
 #endif /* _TREE_SSA_PROPAGATE_H  */
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 45882c4..c8481c9 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -60,6 +60,8 @@  along with GCC; see the file COPYING3.  If not see
 #include "case-cfn-macros.h"
 #include "params.h"
 #include "alloc-pool.h"
+#include "domwalk.h"
+#include "tree-cfgcleanup.h"
 
 #define VR_INITIALIZER { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }
 
@@ -1455,44 +1457,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);
 
@@ -1538,15 +1513,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
 	{
@@ -1730,6 +1705,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
@@ -6947,19 +6957,24 @@  stmt_interesting_for_vrp (gimple *stmt)
   return false;
 }
 
-
-/* Initialize local data structures for VRP.  */
+/* Initialize VRP lattice.  */
 
 static void
-vrp_initialize (void)
+vrp_initialize_lattice ()
 {
-  basic_block bb;
-
   values_propagated = false;
   num_vr_values = num_ssa_names;
   vr_value = XCNEWVEC (value_range *, num_vr_values);
   vr_phi_edge_counts = XCNEWVEC (int, num_ssa_names);
   bitmap_obstack_initialize (&vrp_equiv_obstack);
+}
+
+/* Initialization required by ssa_propagate engine.  */
+
+static void
+vrp_initialize ()
+{
+  basic_block bb;
 
   FOR_EACH_BB_FN (bb, cfun)
     {
@@ -7010,6 +7025,8 @@  vrp_valueize (tree name)
     {
       value_range *vr = get_value_range (name);
       if (vr->type == VR_RANGE
+	  && (TREE_CODE (vr->min) == SSA_NAME
+	      || is_gimple_min_invariant (vr->min))
 	  && vrp_operand_equal_p (vr->min, vr->max))
 	return vr->min;
     }
@@ -10500,6 +10517,22 @@  finalize_jump_threads (void)
   delete equiv_stack;
 }
 
+/* Free VRP lattice.  */
+
+static void
+vrp_free_lattice ()
+{
+  /* Free allocated memory.  */
+  free (vr_value);
+  free (vr_phi_edge_counts);
+  bitmap_obstack_release (&vrp_equiv_obstack);
+  vrp_value_range_pool.release ();
+
+  /* So that we can distinguish between VRP data being available
+     and not available.  */
+  vr_value = NULL;
+  vr_phi_edge_counts = NULL;
+}
 
 /* Traverse all the blocks folding conditionals with known ranges.  */
 
@@ -10546,17 +10579,302 @@  vrp_finalize (bool warn_array_bounds_p)
   /* We must identify jump threading opportunities before we release
      the datastructures built by VRP.  */
   identify_jump_threads ();
+}
 
-  /* Free allocated memory.  */
-  free (vr_value);
-  free (vr_phi_edge_counts);
-  bitmap_obstack_release (&vrp_equiv_obstack);
-  vrp_value_range_pool.release ();
+/* 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.  */
 
-  /* So that we can distinguish between VRP data being available
-     and not available.  */
-  vr_value = NULL;
-  vr_phi_edge_counts = NULL;
+class evrp_dom_walker : public dom_walker
+{
+public:
+  evrp_dom_walker ()
+    : dom_walker (CDI_DOMINATORS), stack (10)
+    {
+      stmts_to_fixup.create (0);
+      need_eh_cleanup = BITMAP_ALLOC (NULL);
+    }
+  ~evrp_dom_walker ()
+    {
+      stmts_to_fixup.release ();
+      BITMAP_FREE (need_eh_cleanup);
+    }
+  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*> > stack;
+  bitmap need_eh_cleanup;
+  vec<gimple *> stmts_to_fixup;
+};
+
+/* 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;
+
+  push_value_range (NULL_TREE, NULL);
+  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
+	  && (op0 = gimple_cond_lhs (stmt))
+	  && TREE_CODE (op0) == SSA_NAME
+	  && INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt))))
+	{
+	  /* Entering a new scope.  Try to see if we can find a VR
+	     here.  */
+	  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;
+  edge e;
+  edge_iterator ei;
+  bool has_unvisived_preds = false;
+
+  FOR_EACH_EDGE (e, ei, bb->preds)
+    if (!(e->src->flags & BB_VISITED))
+      {
+	has_unvisived_preds = true;
+	break;
+      }
+
+  for (gphi_iterator gpi = gsi_start_phis (bb);
+       !gsi_end_p (gpi); gsi_next (&gpi))
+    {
+      gphi *phi = gpi.phi ();
+      tree lhs = PHI_RESULT (phi);
+      value_range vr_result = VR_INITIALIZER;
+      if (!has_unvisived_preds
+	  && stmt_interesting_for_vrp (phi))
+	extract_range_from_phi_node (phi, &vr_result);
+      else
+	set_value_range_to_varying (&vr_result);
+      update_value_range (lhs, &vr_result);
+    }
+
+  /* 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 = NULL_TREE;
+      gimple *old_stmt = stmt;
+      bool was_noreturn = (is_gimple_call (stmt)
+			   && gimple_call_noreturn_p (stmt));
+
+      /* 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))
+	{
+	  value_range vr = VR_INITIALIZER;
+	  extract_range_from_stmt (stmt, &taken_edge, &output, &vr);
+	  if (output
+	      && (vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE))
+	    update_value_range (output, &vr);
+	  else
+	    {
+	      tree def;
+	      ssa_op_iter iter;
+	      FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
+		set_value_range_to_varying (get_value_range (def));
+	    }
+
+	  /* Try folding stmts with the VR discovered.  */
+	  bool did_replace
+	    = replace_uses_in (stmt,
+			       op_with_constant_singleton_value_range);
+	  if (fold_stmt (&gsi, follow_single_use_edges)
+	      || did_replace)
+	    update_stmt (gsi_stmt (gsi));
+
+	  if (did_replace)
+	    {
+	      /* If we cleaned up EH information from the statement,
+		 remove EH edges.  */
+	      if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
+		bitmap_set_bit (need_eh_cleanup, bb->index);
+
+	      /* If we turned a not noreturn call into a noreturn one
+		 schedule it for fixup.  */
+	      if (!was_noreturn
+		  && is_gimple_call (stmt)
+		  && gimple_call_noreturn_p (stmt))
+		stmts_to_fixup.safe_push (stmt);
+
+	      if (gimple_assign_single_p (stmt))
+		{
+		  tree rhs = gimple_assign_rhs1 (stmt);
+		  if (TREE_CODE (rhs) == ADDR_EXPR)
+		    recompute_tree_invariant_for_addr_expr (rhs);
+		}
+	    }
+
+	  def_operand_p def_p = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF);
+	  /* Set the SSA with the value range.  */
+	  if (def_p
+	      && TREE_CODE (DEF_FROM_PTR (def_p)) == SSA_NAME
+	      && INTEGRAL_TYPE_P (TREE_TYPE (DEF_FROM_PTR (def_p))))
+	    {
+	      tree def = DEF_FROM_PTR (def_p);
+	      value_range *vr = get_value_range (def);
+
+	      if ((vr->type == VR_RANGE
+		   || vr->type == VR_ANTI_RANGE)
+		  && (TREE_CODE (vr->min) == INTEGER_CST)
+		  && (TREE_CODE (vr->max) == INTEGER_CST))
+		set_range_info (def, vr->type, vr->min, vr->max);
+	    }
+	}
+      else
+	{
+	  tree def;
+	  ssa_op_iter iter;
+	  FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
+	    set_value_range_to_varying (get_value_range (def));
+	}
+    }
+  bb->flags |= BB_VISITED;
+  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 ());
+  while (stack.last ().first != NULL_TREE)
+    pop_value_range (stack.last ().first);
+  pop_value_range (stack.last ().first);
+}
+
+/* Push the Value Range of VAR to the stack and update 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 where basic blocks are visited in dominance order.  Value
+   ranges discovered in early vrp will also be used by ipa-vrp.  */
+
+static unsigned int
+execute_early_vrp ()
+{
+  edge e;
+  edge_iterator ei;
+  basic_block bb;
+
+  loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
+  rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
+  scev_initialize ();
+  calculate_dominance_info (CDI_DOMINATORS);
+  FOR_EACH_BB_FN (bb, cfun)
+    {
+      bb->flags &= ~BB_VISITED;
+      FOR_EACH_EDGE (e, ei, bb->preds)
+	e->flags |= EDGE_EXECUTABLE;
+    }
+  vrp_initialize_lattice ();
+
+  /* Walk stmts in dominance order and propagate VRP.  */
+  evrp_dom_walker walker;
+  walker.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun));
+
+  if (!bitmap_empty_p (walker.need_eh_cleanup))
+    gimple_purge_all_dead_eh_edges (walker.need_eh_cleanup);
+
+  /* Fixup stmts that became noreturn calls.  This may require splitting
+     blocks and thus isn't possible during the dominator walk.  Do this
+     in reverse order so we don't inadvertedly remove a stmt we want to
+     fixup by visiting a dominating now noreturn call first.  */
+  while (!walker.stmts_to_fixup.is_empty ())
+    {
+      gimple *stmt = walker.stmts_to_fixup.pop ();
+      fixup_noreturn_call (stmt);
+    }
+
+  if (dump_file)
+    {
+      fprintf (dump_file, "\nValue ranges after Early VRP:\n\n");
+      dump_all_value_ranges (dump_file);
+      fprintf (dump_file, "\n");
+    }
+  vrp_free_lattice ();
+  scev_finalize ();
+  loop_optimizer_finalize ();
+  FOR_EACH_BB_FN (bb, cfun)
+    bb->flags &= ~BB_VISITED;
+  return 0;
 }
 
 
@@ -10627,9 +10945,11 @@  execute_vrp (bool warn_array_bounds_p)
   /* For visiting PHI nodes we need EDGE_DFS_BACK computed.  */
   mark_dfs_back_edges ();
 
+  vrp_initialize_lattice ();
   vrp_initialize ();
   ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node);
   vrp_finalize (warn_array_bounds_p);
+  vrp_free_lattice ();
 
   free_numbers_of_iterations_estimates (cfun);
 
@@ -10727,3 +11047,44 @@  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_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);
+}
+
-- 
2.7.4