diff mbox

[RFC,IPA-VRP] Early VRP Implementation

Message ID 57886A71.6030103@linaro.org
State Superseded
Headers show

Commit Message

Kugan Vivekanandarajah July 15, 2016, 4:45 a.m. UTC
Hi,



This patch adds a very simple early vrp implementation. This 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. Restore the 
old VR once the scope is exit.



Thanks,

Kugan





gcc/ChangeLog:



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



         * Makefile.in: Add tree-early-vrp.o.

         * 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-early-vrp.c: New file.

         * tree-pass.h (make_pass_early_vrp): New.



gcc/testsuite/ChangeLog:



2016-07-14  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: Check for the pattern in evrp dump.

         * gcc.dg/tree-ssa/pr22117.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.

Comments

Kugan Vivekanandarajah July 15, 2016, 7:08 a.m. UTC | #1
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.


> Also it seems like if you are going to do that, putting the following

> functions in a class would be better:

> +extern void vrp_initialize (void);

> +extern void vrp_finalize (bool update, bool warn_array_bounds_p);

> +extern void vrp_intersect_ranges (value_range *vr0, value_range *vr1);

> +extern void vrp_meet (value_range *vr0, value_range *vr1);

> +extern enum ssa_prop_result vrp_visit_stmt (gimple *stmt,

> +    edge *taken_edge_p,

> +    tree *output_p);

> +extern enum ssa_prop_result vrp_visit_phi_node (gphi *phi);

> +extern bool stmt_interesting_for_vrp (gimple *stmt);

> +

> +extern void extract_range_from_assert (value_range *vr_p, tree expr);

> +extern bool update_value_range (const_tree var, value_range *vr);

> +extern value_range *get_value_range (const_tree var);

> +extern void set_value_range (value_range *vr, enum value_range_type t,

> +     tree min, tree max, bitmap equiv);

> +extern void change_value_range (const_tree var, value_range *new_vr);

> +

> +extern void dump_value_range (FILE *, value_range *);

>

> That is vrp_initialize becomes the constructor and vrp_finalize

> becomes the deconstructor.

> With both jump_thread and warn_array_bounds_p being variables you set

> while running your pass.


I will give this a try.

Thanks,
Kugan
Kugan Vivekanandarajah July 15, 2016, 7:33 a.m. UTC | #2
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.

Thanks,
Kugan
diff mbox

Patch

From d73d443762e1741b810143b2333801cf952c8f17 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 4/6] Add early vrp

---
 gcc/Makefile.in                           |   1 +
 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   |   4 +-
 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-early-vrp.c                      | 324 ++++++++++++++++++++++++++++++
 gcc/tree-pass.h                           |   1 +
 21 files changed, 411 insertions(+), 23 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
 create mode 100644 gcc/tree-early-vrp.c

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 776f6d7..1804632 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1528,6 +1528,7 @@  OBJS = \
 	tree-vect-loop-manip.o \
 	tree-vect-slp.o \
 	tree-vectorizer.o \
+	tree-early-vrp.o \
 	tree-vrp.o \
 	tree.o \
 	valtrack.o \
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..49a20bc 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-evrp" } */
 
 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 "Folding predicate r_.* != 0B to 0" 1 "evrp" } } */
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..6e3b15f 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 -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-early-vrp.c b/gcc/tree-early-vrp.c
new file mode 100644
index 0000000..adfcbe4
--- /dev/null
+++ b/gcc/tree-early-vrp.c
@@ -0,0 +1,324 @@ 
+/* Early Value Range Propagation (VRP) Implementation.
+   Copyright (C) 2016 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 3, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "backend.h"
+#include "insn-codes.h"
+#include "rtl.h"
+#include "tree.h"
+#include "gimple.h"
+#include "cfghooks.h"
+#include "tree-pass.h"
+#include "ssa.h"
+#include "optabs-tree.h"
+#include "gimple-pretty-print.h"
+#include "diagnostic-core.h"
+#include "flags.h"
+#include "fold-const.h"
+#include "stor-layout.h"
+#include "calls.h"
+#include "cfganal.h"
+#include "gimple-fold.h"
+#include "tree-eh.h"
+#include "gimple-iterator.h"
+#include "gimple-walk.h"
+#include "tree-cfg.h"
+#include "tree-ssa-loop-manip.h"
+#include "tree-ssa-loop-niter.h"
+#include "tree-ssa-loop.h"
+#include "tree-into-ssa.h"
+#include "tree-ssa.h"
+#include "intl.h"
+#include "cfgloop.h"
+#include "tree-scalar-evolution.h"
+#include "tree-ssa-propagate.h"
+#include "tree-chrec.h"
+#include "tree-ssa-threadupdate.h"
+#include "tree-ssa-scopedtables.h"
+#include "tree-ssa-threadedge.h"
+#include "omp-low.h"
+#include "target.h"
+#include "case-cfn-macros.h"
+#include "domwalk.h"
+#include "tree-vrp.h"
+
+/* A simplified non-iterative version of visit_phi_node which discovers
+   value ranges for PHI definition. I.e. whenever there is a backedge
+   in the PHI set the PHI definition to VARYING.  */
+
+static enum ssa_prop_result
+vrp_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
+	  || e->flags & EDGE_ABNORMAL)
+	{
+	  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_VARYING)
+	{
+	  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))
+    {
+      if (vr_result.type == VR_VARYING)
+	{
+	  set_value_range_to_varying (&vr_result);
+	  return SSA_PROP_VARYING;
+	}
+      return SSA_PROP_INTERESTING;
+    }
+
+  return SSA_PROP_NOT_INTERESTING;
+}
+
+/* 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.  */
+
+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);
+
+  /* Cond_stack holds the old VR.  */
+  vec<std::pair <basic_block, std::pair <tree, value_range*> > > cond_stack;
+};
+
+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 ();
+    }
+
+  /* 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.  */
+  if (single_pred_p (bb))
+    {
+      edge te = NULL, fe = NULL;
+      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))))
+	{
+	  extract_true_false_edges_from_block (e->src,
+					       &te, &fe);
+	  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 (te == e
+	      && !TREE_OVERFLOW_P (op0)
+	      && !TREE_OVERFLOW_P (op1))
+	    {
+	      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);
+	      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 (fe == e
+	      && !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);
+	      tree a = build2 (ASSERT_EXPR, TREE_TYPE (op0), op0, cond);
+	      extract_range_from_assert (&vr, a);
+	      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
+	     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);
+	    }
+	}
+    }
+
+  /* Visit  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))
+	vrp_visit_phi_node_local (phi);
+    }
+
+  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+    {
+      gimple *stmt = gsi_stmt (gsi);
+      edge taken_edge_p;
+      tree output_p;
+      if (stmt_interesting_for_vrp (stmt))
+	vrp_visit_stmt (stmt, &taken_edge_p, &output_p);
+    }
+
+  return NULL;
+}
+
+
+/* Restore 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.first;
+      value_range *vr_to_del = get_value_range (var);
+      XDELETE (vr_to_del);
+      value_range *vr = cond_stack.last ().second.second;
+      change_value_range (var, vr);
+      cond_stack.pop ();
+    }
+}
+
+static unsigned int
+execute_early_vrp ()
+{
+  basic_block bb;
+  edge e;
+  edge_iterator ei;
+
+  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);
+  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);
+  free_numbers_of_iterations_estimates (cfun);
+
+  scev_finalize ();
+  loop_optimizer_finalize ();
+  return 0;
+}
+
+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);
+}
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);
-- 
1.9.1