This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[RFC][IPA-VRP] Early VRP Implementation
- From: kugan <kugan dot vivekanandarajah at linaro dot org>
- To: "gcc-patches at gcc dot gnu dot org" <gcc-patches at gcc dot gnu dot org>
- Cc: Richard Biener <richard dot guenther at gmail dot com>, Jan Hubicka <hubicka at ucw dot cz>, Martin Jambor <mjambor at suse dot cz>
- Date: Fri, 15 Jul 2016 14:45:37 +1000
- Subject: [RFC][IPA-VRP] Early VRP Implementation
- Authentication-results: sourceware.org; auth=none
- References: <57886949.8010300@linaro.org>
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.
>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