From 17ea87a0e47a0d2325376d6a66a3ff1d5d70c0b4 Mon Sep 17 00:00:00 2001
From: Kugan Vivekanandarajah <kugan.vivekanandarajah@linaro.org>
Date: Fri, 29 Jul 2016 21:37:20 +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   |   2 +-
 gcc/testsuite/gcc.dg/tree-ssa/vrp24.c     |   5 +-
 gcc/testsuite/gcc.dg/tree-ssa/vrp58.c     |   4 +-
 gcc/timevar.def                           |   1 +
 gcc/tree-pass.h                           |   1 +
 gcc/tree-vrp.c                            | 578 ++++++++++++++++++++++++------
 15 files changed, 540 insertions(+), 119 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 8a292ed..7028cd4 100644
--- a/gcc/common.opt
+++ b/gcc/common.opt
@@ -2482,6 +2482,10 @@ ftree-vrp
 Common Report Var(flag_tree_vrp) Init(0) Optimization
 Perform Value Range Propagation on trees.
 
+fdisable-tree-evrp
+Common Report Var(flag_disable_early_vrp) Init(0) Optimization
+Disable 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 22001f9..1d4910b 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -7715,6 +7715,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 -fdisable-tree-evrp
+@opindex fdisable-tree-evrp
+Disables Early Value Range Propagation on trees.
+
 @item -fsplit-paths
 @opindex fsplit-paths
 Split paths leading to loop backedges.  This can improve dead code
@@ -12338,6 +12342,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..6f95920 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-vrp  -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 "vrp" } } */
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..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/vrp24.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp24.c
index e740575..7da577b 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 "vrp1" } } */
 
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/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 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 4127e2e..b90d9571 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -1438,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);
 
@@ -1521,15 +1494,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
 	{
@@ -1713,6 +1686,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
@@ -1728,11 +1736,12 @@ extract_range_from_assert (value_range *vr_p, tree expr)
     always false.  */
 
 static void
-extract_range_from_ssa_name (value_range *vr, tree var)
+extract_range_from_ssa_name (value_range *vr, bool dom_p, tree var)
 {
   value_range *var_vr = get_value_range (var);
 
-  if (var_vr->type != VR_VARYING)
+  if (var_vr->type != VR_VARYING
+      && (!dom_p || var_vr->type != VR_UNDEFINED))
     copy_value_range (vr, var_vr);
   else
     set_value_range (vr, VR_RANGE, var, var, NULL);
@@ -2136,6 +2145,7 @@ extract_range_from_multiplicative_op_1 (value_range *vr,
 
 static void
 extract_range_from_binary_expr_1 (value_range *vr,
+				  bool dom_p,
 				  enum tree_code code, tree expr_type,
 				  value_range *vr0_, value_range *vr1_)
 {
@@ -2152,6 +2162,15 @@ extract_range_from_binary_expr_1 (value_range *vr,
       return;
     }
 
+  /* If we are in dom based non iterative VRP and any of the input is
+     VR_UNDEGFINED, set the resylt to VR_VARYING.  */
+  if (dom_p
+      && (vr0.type == VR_UNDEFINED || vr1.type == VR_UNDEFINED))
+    {
+      set_value_range_to_varying (vr);
+      return;
+    }
+
   /* Not all binary expressions can be applied to ranges in a
      meaningful way.  Handle only arithmetic operations.  */
   if (code != PLUS_EXPR
@@ -2196,11 +2215,12 @@ extract_range_from_binary_expr_1 (value_range *vr,
   if (vr0.type == VR_ANTI_RANGE
       && ranges_from_anti_range (&vr0, &vrtem0, &vrtem1))
     {
-      extract_range_from_binary_expr_1 (vr, code, expr_type, &vrtem0, vr1_);
+      extract_range_from_binary_expr_1 (vr, dom_p, code, expr_type,
+					&vrtem0, vr1_);
       if (vrtem1.type != VR_UNDEFINED)
 	{
 	  value_range vrres = VR_INITIALIZER;
-	  extract_range_from_binary_expr_1 (&vrres, code, expr_type,
+	  extract_range_from_binary_expr_1 (&vrres, dom_p, code, expr_type,
 					    &vrtem1, vr1_);
 	  vrp_meet (vr, &vrres);
 	}
@@ -2210,11 +2230,12 @@ extract_range_from_binary_expr_1 (value_range *vr,
   if (vr1.type == VR_ANTI_RANGE
       && ranges_from_anti_range (&vr1, &vrtem0, &vrtem1))
     {
-      extract_range_from_binary_expr_1 (vr, code, expr_type, vr0_, &vrtem0);
+      extract_range_from_binary_expr_1 (vr, dom_p, code, expr_type,
+					vr0_, &vrtem0);
       if (vrtem1.type != VR_UNDEFINED)
 	{
 	  value_range vrres = VR_INITIALIZER;
-	  extract_range_from_binary_expr_1 (&vrres, code, expr_type,
+	  extract_range_from_binary_expr_1 (&vrres, dom_p, code, expr_type,
 					    vr0_, &vrtem1);
 	  vrp_meet (vr, &vrres);
 	}
@@ -2769,7 +2790,7 @@ extract_range_from_binary_expr_1 (value_range *vr,
 		 on lshifts is implementation defined in C89.  */
 	      saved_flag_wrapv = flag_wrapv;
 	      flag_wrapv = 1;
-	      extract_range_from_binary_expr_1 (vr, MULT_EXPR, expr_type,
+	      extract_range_from_binary_expr_1 (vr, dom_p, MULT_EXPR, expr_type,
 						&vr0, &vr1p);
 	      flag_wrapv = saved_flag_wrapv;
 	      return;
@@ -3154,6 +3175,7 @@ extract_range_from_binary_expr_1 (value_range *vr,
 
 static void
 extract_range_from_binary_expr (value_range *vr,
+				bool dom_p,
 				enum tree_code code,
 				tree expr_type, tree op0, tree op1)
 {
@@ -3176,7 +3198,7 @@ extract_range_from_binary_expr (value_range *vr,
   else
     set_value_range_to_varying (&vr1);
 
-  extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &vr1);
+  extract_range_from_binary_expr_1 (vr, dom_p, code, expr_type, &vr0, &vr1);
 
   /* Try harder for PLUS and MINUS if the range of one operand is symbolic
      and based on the other operand, for example if it was deduced from a
@@ -3204,7 +3226,8 @@ extract_range_from_binary_expr (value_range *vr,
       else
 	set_value_range (&n_vr1, VR_RANGE, op1, op1, NULL);
 
-      extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &n_vr1);
+      extract_range_from_binary_expr_1 (vr, dom_p, code, expr_type,
+					&vr0, &n_vr1);
     }
 
   if (vr->type == VR_VARYING
@@ -3228,7 +3251,8 @@ extract_range_from_binary_expr (value_range *vr,
       else
 	set_value_range (&n_vr0, VR_RANGE, op0, op0, NULL);
 
-      extract_range_from_binary_expr_1 (vr, code, expr_type, &n_vr0, &vr1);
+      extract_range_from_binary_expr_1 (vr, dom_p, code, expr_type,
+					&n_vr0, &vr1);
     }
 }
 
@@ -3238,6 +3262,7 @@ extract_range_from_binary_expr (value_range *vr,
 
 static void
 extract_range_from_unary_expr_1 (value_range *vr,
+				 bool dom_p,
 				 enum tree_code code, tree type,
 				 value_range *vr0_, tree op0_type)
 {
@@ -3253,6 +3278,14 @@ extract_range_from_unary_expr_1 (value_range *vr,
       return;
     }
 
+  /* If we are in dom based non iterative VRP and the input is
+     VR_UNDEGFINED, set the resylt to VR_VARYING.  */
+  if (dom_p && vr0.type == VR_UNDEFINED)
+    {
+      set_value_range_to_varying (vr);
+      return;
+    }
+
   /* If VR0 is UNDEFINED, so is the result.  */
   if (vr0.type == VR_UNDEFINED)
     {
@@ -3273,7 +3306,8 @@ extract_range_from_unary_expr_1 (value_range *vr,
          anti-ranges fine.  */
       value_range zero = VR_INITIALIZER;
       set_value_range_to_value (&zero, build_int_cst (type, 0), NULL);
-      extract_range_from_binary_expr_1 (vr, MINUS_EXPR, type, &zero, &vr0);
+      extract_range_from_binary_expr_1 (vr, dom_p, MINUS_EXPR,
+					type, &zero, &vr0);
       return;
     }
   else if (code == BIT_NOT_EXPR)
@@ -3282,7 +3316,7 @@ extract_range_from_unary_expr_1 (value_range *vr,
          anti-ranges fine.  */
       value_range minusone = VR_INITIALIZER;
       set_value_range_to_value (&minusone, build_int_cst (type, -1), NULL);
-      extract_range_from_binary_expr_1 (vr, MINUS_EXPR,
+      extract_range_from_binary_expr_1 (vr, dom_p, MINUS_EXPR,
 					type, &minusone, &vr0);
       return;
     }
@@ -3292,12 +3326,13 @@ extract_range_from_unary_expr_1 (value_range *vr,
   if (vr0.type == VR_ANTI_RANGE
       && ranges_from_anti_range (&vr0, &vrtem0, &vrtem1))
     {
-      extract_range_from_unary_expr_1 (vr, code, type, &vrtem0, op0_type);
+      extract_range_from_unary_expr_1 (vr, dom_p, code, type,
+				       &vrtem0, op0_type);
       if (vrtem1.type != VR_UNDEFINED)
 	{
 	  value_range vrres = VR_INITIALIZER;
-	  extract_range_from_unary_expr_1 (&vrres, code, type,
-					   &vrtem1, op0_type);
+	  extract_range_from_unary_expr_1 (&vrres, dom_p, code,
+					   type, &vrtem1, op0_type);
 	  vrp_meet (vr, &vrres);
 	}
       return;
@@ -3538,7 +3573,9 @@ extract_range_from_unary_expr_1 (value_range *vr,
    The resulting range is stored in *VR.  */
 
 static void
-extract_range_from_unary_expr (value_range *vr, enum tree_code code,
+extract_range_from_unary_expr (value_range *vr,
+			       bool dom_p,
+			       enum tree_code code,
 			       tree type, tree op0)
 {
   value_range vr0 = VR_INITIALIZER;
@@ -3552,7 +3589,8 @@ extract_range_from_unary_expr (value_range *vr, enum tree_code code,
   else
     set_value_range_to_varying (&vr0);
 
-  extract_range_from_unary_expr_1 (vr, code, type, &vr0, TREE_TYPE (op0));
+  extract_range_from_unary_expr_1 (vr, dom_p, code, type,
+				   &vr0, TREE_TYPE (op0));
 }
 
 
@@ -3560,7 +3598,9 @@ extract_range_from_unary_expr (value_range *vr, enum tree_code code,
    the ranges of each of its operands and the expression code.  */
 
 static void
-extract_range_from_cond_expr (value_range *vr, gassign *stmt)
+extract_range_from_cond_expr (value_range *vr,
+			      bool dom_p,
+			      gassign *stmt)
 {
   tree op0, op1;
   value_range vr0 = VR_INITIALIZER;
@@ -3584,6 +3624,15 @@ extract_range_from_cond_expr (value_range *vr, gassign *stmt)
   else
     set_value_range_to_varying (&vr1);
 
+  /* If we are in dom based non iterative VRP and any of the input is
+     VR_UNDEGFINED, set the resylt to VR_VARYING.  */
+  if (dom_p
+      && (vr0.type == VR_UNDEFINED || vr1.type == VR_UNDEFINED))
+    {
+      set_value_range_to_varying (vr);
+      return;
+    }
+
   /* The resulting value range is the union of the operand ranges */
   copy_value_range (vr, &vr0);
   vrp_meet (vr, &vr1);
@@ -3594,7 +3643,8 @@ extract_range_from_cond_expr (value_range *vr, gassign *stmt)
    on the range of its operand and the expression code.  */
 
 static void
-extract_range_from_comparison (value_range *vr, enum tree_code code,
+extract_range_from_comparison (value_range *vr,
+			       enum tree_code code,
 			       tree type, tree op0, tree op1)
 {
   bool sop = false;
@@ -3631,7 +3681,8 @@ extract_range_from_comparison (value_range *vr, enum tree_code code,
    overflow.  */
 
 static bool
-check_for_binary_op_overflow (enum tree_code subcode, tree type,
+check_for_binary_op_overflow (enum tree_code subcode,
+			      tree type,
 			      tree op0, tree op1, bool *ovf)
 {
   value_range vr0 = VR_INITIALIZER;
@@ -3736,7 +3787,9 @@ check_for_binary_op_overflow (enum tree_code subcode, tree type,
    Store the result in *VR */
 
 static void
-extract_range_basic (value_range *vr, gimple *stmt)
+extract_range_basic (value_range *vr,
+		     bool dom_p,
+		     gimple *stmt)
 {
   bool sop = false;
   tree type = gimple_expr_type (stmt);
@@ -3960,7 +4013,7 @@ extract_range_basic (value_range *vr, gimple *stmt)
 	     any overflow, we'll complain, but will actually do
 	     wrapping operation.  */
 	  flag_wrapv = 1;
-	  extract_range_from_binary_expr (vr, subcode, type,
+	  extract_range_from_binary_expr (vr, dom_p, subcode, type,
 					  gimple_call_arg (stmt, 0),
 					  gimple_call_arg (stmt, 1));
 	  flag_wrapv = saved_flag_wrapv;
@@ -4032,7 +4085,7 @@ extract_range_basic (value_range *vr, gimple *stmt)
 		      /* Pretend the arithmetics is wrapping.  If there is
 			 any overflow, IMAGPART_EXPR will be set.  */
 		      flag_wrapv = 1;
-		      extract_range_from_binary_expr (vr, subcode, type,
+		      extract_range_from_binary_expr (vr, dom_p, subcode, type,
 						      op0, op1);
 		      flag_wrapv = saved_flag_wrapv;
 		    }
@@ -4044,12 +4097,12 @@ extract_range_basic (value_range *vr, gimple *stmt)
 		      /* Pretend the arithmetics is wrapping.  If there is
 			 any overflow, IMAGPART_EXPR will be set.  */
 		      flag_wrapv = 1;
-		      extract_range_from_unary_expr (&vr0, NOP_EXPR,
+		      extract_range_from_unary_expr (&vr0, dom_p, NOP_EXPR,
 						     type, op0);
-		      extract_range_from_unary_expr (&vr1, NOP_EXPR,
+		      extract_range_from_unary_expr (&vr1, dom_p, NOP_EXPR,
 						     type, op1);
-		      extract_range_from_binary_expr_1 (vr, subcode, type,
-							&vr0, &vr1);
+		      extract_range_from_binary_expr_1 (vr, dom_p, subcode,
+							type, &vr0, &vr1);
 		      flag_wrapv = saved_flag_wrapv;
 		    }
 		  return;
@@ -4073,25 +4126,27 @@ extract_range_basic (value_range *vr, gimple *stmt)
    in *VR.  */
 
 static void
-extract_range_from_assignment (value_range *vr, gassign *stmt)
+extract_range_from_assignment (value_range *vr,
+			       bool dom_p,
+			       gassign *stmt)
 {
   enum tree_code code = gimple_assign_rhs_code (stmt);
 
   if (code == ASSERT_EXPR)
     extract_range_from_assert (vr, gimple_assign_rhs1 (stmt));
   else if (code == SSA_NAME)
-    extract_range_from_ssa_name (vr, gimple_assign_rhs1 (stmt));
+    extract_range_from_ssa_name (vr, dom_p, gimple_assign_rhs1 (stmt));
   else if (TREE_CODE_CLASS (code) == tcc_binary)
-    extract_range_from_binary_expr (vr, gimple_assign_rhs_code (stmt),
+    extract_range_from_binary_expr (vr, dom_p, gimple_assign_rhs_code (stmt),
 				    gimple_expr_type (stmt),
 				    gimple_assign_rhs1 (stmt),
 				    gimple_assign_rhs2 (stmt));
   else if (TREE_CODE_CLASS (code) == tcc_unary)
-    extract_range_from_unary_expr (vr, gimple_assign_rhs_code (stmt),
+    extract_range_from_unary_expr (vr, dom_p, gimple_assign_rhs_code (stmt),
 				   gimple_expr_type (stmt),
 				   gimple_assign_rhs1 (stmt));
   else if (code == COND_EXPR)
-    extract_range_from_cond_expr (vr, stmt);
+    extract_range_from_cond_expr (vr, dom_p, stmt);
   else if (TREE_CODE_CLASS (code) == tcc_comparison)
     extract_range_from_comparison (vr, gimple_assign_rhs_code (stmt),
 				   gimple_expr_type (stmt),
@@ -4104,7 +4159,7 @@ extract_range_from_assignment (value_range *vr, gassign *stmt)
     set_value_range_to_varying (vr);
 
   if (vr->type == VR_VARYING)
-    extract_range_basic (vr, stmt);
+    extract_range_basic (vr, dom_p, stmt);
 }
 
 /* Given a range VR, a LOOP and a variable VAR, determine whether it
@@ -4112,7 +4167,9 @@ extract_range_from_assignment (value_range *vr, gassign *stmt)
    for VAR.  If so, update VR with the new limits.  */
 
 static void
-adjust_range_with_scev (value_range *vr, struct loop *loop,
+adjust_range_with_scev (value_range *vr,
+			bool dom_p,
+			struct loop *loop,
 			gimple *stmt, tree var)
 {
   tree init, step, chrec, tmin, tmax, min, max, type, tem;
@@ -4207,7 +4264,7 @@ adjust_range_with_scev (value_range *vr, struct loop *loop,
 		  || wi::gts_p (wtmp, 0) == wi::gts_p (step, 0)))
 	    {
 	      tem = wide_int_to_tree (TREE_TYPE (init), wtmp);
-	      extract_range_from_binary_expr (&maxvr, PLUS_EXPR,
+	      extract_range_from_binary_expr (&maxvr, dom_p, PLUS_EXPR,
 					      TREE_TYPE (init), init, tem);
 	      /* Likewise if the addition did.  */
 	      if (maxvr.type == VR_RANGE)
@@ -6936,10 +6993,14 @@ stmt_interesting_for_vrp (gimple *stmt)
 }
 
 
-/* Initialize local data structures for VRP.  */
+/* 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 (void)
+vrp_initialize (bool dom_p)
 {
   basic_block bb;
 
@@ -6949,6 +7010,9 @@ vrp_initialize (void)
   vr_phi_edge_counts = XCNEWVEC (int, num_ssa_names);
   bitmap_obstack_initialize (&vrp_equiv_obstack);
 
+  if (dom_p)
+    return;
+
   FOR_EACH_BB_FN (bb, cfun)
     {
       for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);
@@ -7031,7 +7095,9 @@ vrp_valueize_1 (tree name)
    the SSA name in *OUTPUT_P.  */
 
 static enum ssa_prop_result
-vrp_visit_assignment_or_call (gimple *stmt, tree *output_p)
+vrp_visit_assignment_or_call (gimple *stmt,
+			      bool dom_p,
+			      tree *output_p)
 {
   tree def, lhs;
   ssa_op_iter iter;
@@ -7056,9 +7122,9 @@ vrp_visit_assignment_or_call (gimple *stmt, tree *output_p)
 	set_value_range_to_value (&new_vr, tem, NULL);
       /* Then dispatch to value-range extracting functions.  */
       else if (code == GIMPLE_CALL)
-	extract_range_basic (&new_vr, stmt);
+	extract_range_basic (&new_vr, dom_p, stmt);
       else
-	extract_range_from_assignment (&new_vr, as_a <gassign *> (stmt));
+	extract_range_from_assignment (&new_vr, dom_p, as_a <gassign *> (stmt));
 
       if (update_value_range (lhs, &new_vr))
 	{
@@ -7126,7 +7192,7 @@ vrp_visit_assignment_or_call (gimple *stmt, tree *output_p)
 		   {REAL,IMAG}PART_EXPR uses at all,
 		   return SSA_PROP_VARYING.  */
 		value_range new_vr = VR_INITIALIZER;
-		extract_range_basic (&new_vr, use_stmt);
+		extract_range_basic (&new_vr, dom_p, use_stmt);
 		value_range *old_vr = get_value_range (use_lhs);
 		if (old_vr->type != new_vr.type
 		    || !vrp_operand_equal_p (old_vr->min, new_vr.min)
@@ -7926,7 +7992,8 @@ vrp_visit_switch_stmt (gswitch *stmt, edge *taken_edge_p)
    If STMT produces a varying value, return SSA_PROP_VARYING.  */
 
 static enum ssa_prop_result
-vrp_visit_stmt (gimple *stmt, edge *taken_edge_p, tree *output_p)
+vrp_visit_stmt_worker (gimple *stmt, bool dom_p,  edge *taken_edge_p,
+		       tree *output_p)
 {
   tree def;
   ssa_op_iter iter;
@@ -7940,7 +8007,7 @@ vrp_visit_stmt (gimple *stmt, edge *taken_edge_p, tree *output_p)
   if (!stmt_interesting_for_vrp (stmt))
     gcc_assert (stmt_ends_bb_p (stmt));
   else if (is_gimple_assign (stmt) || is_gimple_call (stmt))
-    return vrp_visit_assignment_or_call (stmt, output_p);
+    return vrp_visit_assignment_or_call (stmt, dom_p, output_p);
   else if (gimple_code (stmt) == GIMPLE_COND)
     return vrp_visit_cond_stmt (as_a <gcond *> (stmt), taken_edge_p);
   else if (gimple_code (stmt) == GIMPLE_SWITCH)
@@ -7954,6 +8021,12 @@ vrp_visit_stmt (gimple *stmt, edge *taken_edge_p, tree *output_p)
   return SSA_PROP_VARYING;
 }
 
+static enum ssa_prop_result
+vrp_visit_stmt (gimple *stmt, edge *taken_edge_p, tree *output_p)
+{
+  return vrp_visit_stmt_worker (stmt, false, taken_edge_p, output_p);
+}
+
 /* Union the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
    { VR1TYPE, VR0MIN, VR0MAX } and store the result
    in { *VR0TYPE, *VR0MIN, *VR0MAX }.  This may not be the smallest
@@ -8679,7 +8752,8 @@ vrp_meet (value_range *vr0, const value_range *vr1)
    value ranges, set a new range for the LHS of PHI.  */
 
 static enum ssa_prop_result
-vrp_visit_phi_node (gphi *phi)
+vrp_visit_phi_node_worker (gphi *phi,
+			   bool dom_p)
 {
   size_t i;
   tree lhs = PHI_RESULT (phi);
@@ -8768,6 +8842,12 @@ vrp_visit_phi_node (gphi *phi)
 	      fprintf (dump_file, "\n");
 	    }
 
+	  if (dom_p && vr_arg.type == VR_UNDEFINED)
+	    {
+	      set_value_range_to_varying (&vr_result);
+	      break;
+	    }
+
 	  if (first)
 	    copy_value_range (&vr_result, &vr_arg);
 	  else
@@ -8794,6 +8874,7 @@ vrp_visit_phi_node (gphi *phi)
      which are not in a loop.  If the old value-range was VR_UNDEFINED
      use the updated range and iterate one more time.  */
   if (edges > 0
+      && !dom_p
       && gimple_phi_num_args (phi) > 1
       && edges == old_edges
       && lhs_vr->type != VR_UNDEFINED)
@@ -8881,9 +8962,10 @@ scev_check:
      scev_check can be reached from two paths, one is a fall through from above
      "varying" label, the other is direct goto from code block which tries to
      avoid infinite simulation.  */
-  if ((l = loop_containing_stmt (phi))
+  if (!dom_p
+      && (l = loop_containing_stmt (phi))
       && l->header == gimple_bb (phi))
-    adjust_range_with_scev (&vr_result, l, phi, lhs);
+    adjust_range_with_scev (&vr_result, false, l, phi, lhs);
 
 infinite_check:
   /* If we will end up with a (-INF, +INF) range, set it to
@@ -8899,6 +8981,12 @@ infinite_check:
   return SSA_PROP_VARYING;
 }
 
+static enum ssa_prop_result
+vrp_visit_phi_node (gphi *phi)
+{
+  return vrp_visit_phi_node_worker (phi, false);
+}
+
 /* Simplify boolean operations if the source is known
    to be already a boolean.  */
 static bool
@@ -9179,7 +9267,8 @@ simplify_abs_using_ranges (gimple *stmt)
    operation is redundant.  */
 
 static bool
-simplify_bit_ops_using_ranges (gimple_stmt_iterator *gsi, gimple *stmt)
+simplify_bit_ops_using_ranges (gimple_stmt_iterator *gsi,
+			       gimple *stmt)
 {
   tree op0 = gimple_assign_rhs1 (stmt);
   tree op1 = gimple_assign_rhs2 (stmt);
@@ -10082,7 +10171,7 @@ simplify_stmt_for_jump_threading (gimple *stmt, gimple *within_stmt,
 	  && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
 	      || POINTER_TYPE_P (TREE_TYPE (lhs))))
 	{
-	  extract_range_from_assignment (&new_vr, assign_stmt);
+	  extract_range_from_assignment (&new_vr, false, assign_stmt);
 	  if (range_int_cst_singleton_p (&new_vr))
 	    return new_vr.min;
 	}
@@ -10225,10 +10314,15 @@ finalize_jump_threads (void)
 }
 
 
-/* Traverse all the blocks folding conditionals with known ranges.  */
+/* Traverse all the blocks folding conditionals with known ranges.
+   If DOM_P is true this will be called from dominator based early_vrp.
+   In that case, value ranges would have been set for SSA_NAME as part
+   of the traversal.  And also, substitute_and_fold which is part of
+   the ssa_propagation engine will not be called.  Jump threading is also
+   not done during early_vrp.  */
 
 static void
-vrp_finalize (bool jump_thread_p, bool warn_array_bounds_p)
+vrp_finalize (bool dom_p, bool warn_array_bounds_p)
 {
   size_t i;
 
@@ -10242,34 +10336,36 @@ vrp_finalize (bool jump_thread_p, bool warn_array_bounds_p)
     }
 
   /* Set value range to non pointer SSA_NAMEs.  */
-  for (i  = 0; i < num_vr_values; i++)
-    if (vr_value[i])
-      {
-	tree name = ssa_name (i);
+  if (!dom_p)
+    for (i  = 0; i < num_vr_values; i++)
+      if (vr_value[i])
+	{
+	  tree name = ssa_name (i);
 
-      if (!name
-	  || POINTER_TYPE_P (TREE_TYPE (name))
-	  || (vr_value[i]->type == VR_VARYING)
-	  || (vr_value[i]->type == VR_UNDEFINED))
-	continue;
+	  if (!name
+	      || POINTER_TYPE_P (TREE_TYPE (name))
+	      || (vr_value[i]->type == VR_VARYING)
+	      || (vr_value[i]->type == VR_UNDEFINED))
+	    continue;
 
-      if ((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);
-      }
+	  if ((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);
+	}
 
-  substitute_and_fold (op_with_constant_singleton_value_range,
-		       vrp_fold_stmt, false);
+  if (!dom_p)
+    substitute_and_fold (op_with_constant_singleton_value_range,
+			 vrp_fold_stmt, false);
 
   if (warn_array_bounds && warn_array_bounds_p)
     check_all_array_refs ();
 
   /* We must identify jump threading opportunities before we release
      the datastructures built by VRP.  */
-  if (jump_thread_p)
+  if (!dom_p)
     identify_jump_threads ();
 
   /* Free allocated memory.  */
@@ -10285,6 +10381,227 @@ 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
+visit_phi_node_p (gphi *phi)
+{
+  for (unsigned int i = 0; i < gimple_phi_num_args (phi); i++)
+    {
+      edge e = gimple_phi_arg_edge (phi, i);
+      if (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX))
+	return false;
+    }
+  return true;
+}
+
+/* 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*> > 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;
+  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;
+  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))
+	{
+	  /* See if the PHI has any back edges.  If there is any
+	     backedges we will have to set the lattice to
+	     VR_VARYING as we will not be traversing it till it
+	     reach fix point.  */
+	  if (visit_phi_node_p (phi))
+	    vrp_visit_phi_node_worker (phi, true);
+	  else
+	    {
+	      tree lhs = PHI_RESULT (phi);
+	      value_range vr_result = VR_INITIALIZER;
+	      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;
+      /* 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_worker (stmt, true, &taken_edge, &output);
+	  /* Try folding stmts with the VR discovered.  */
+	  if (fold_stmt (&gsi, follow_single_use_edges))
+	    update_stmt (gsi_stmt (gsi));
+	  def_operand_p def_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
+		   || 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);
+	    }
+	}
+    }
+  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;
+
+  calculate_dominance_info (CDI_DOMINATORS);
+  FOR_EACH_BB_FN (bb, cfun)
+    {
+      FOR_EACH_EDGE (e, ei, bb->preds)
+	e->flags |= EDGE_EXECUTABLE;
+    }
+  vrp_initialize (true);
+
+  /* Walk stmts in dominance order and propagate VRP.  */
+  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
@@ -10352,9 +10669,9 @@ execute_vrp (bool warn_array_bounds_p)
   /* For visiting PHI nodes we need EDGE_DFS_BACK computed.  */
   mark_dfs_back_edges ();
 
-  vrp_initialize ();
+  vrp_initialize (false);
   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);
 
@@ -10452,3 +10769,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_disable_early_vrp && 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);
+}
+
-- 
1.9.1

