Hi Richard,
Thanks for the review.
On 28/07/16 21:34, Richard Biener wrote:
On Thu, Jul 28, 2016 at 9:35 AM, kugan
<kugan.vivekanandara...@linaro.org> wrote:
Hi Richard,
Thanks for the review.
It seems that in your pop_value_range you assume you only pop one
range per BB - while that's likely true at the moment it will be a
limitation
in the future. You want to pop ranges until you hit the NULL marker
in after_dom_children and unconditionally push a NULL marker.
I understand. Right now, I am adding only one assert based on the condition.
But in future, we will be adding more so this is needed. I will do that.
For example to match current VRPs behavior on say
i_2 = (int) j_3;
if (i_2 < 0)
...
which can register an assert for j_3 when i_2 < 0 is true we'd do that
by re-simulating DEFs of uses we figured out new ranges of (and all
their uses). All those ranges would be temporary as well, thus they'd
need to be pushed/popped. In my quick prototype this was done
using a worklist seeded by the names we can derive a range from from
conditionals and "SSA propagating" from it. Note that for this
the generic vrp_visit_stmt cannot be re-used as it doesn't push/pop,
factoring out the lattice update is what is needed here.
I dont think I understand this part. vrp_visit_stmt is going to add value
ranges for the variables defined in the if-block (in the example below it is
for t). If we push the value range for i_2 and j_3 when we enter if-block,
vrp_visit_stmt should compute "t" correctly. When we leave the if-block, we
will pop i_2 and j_3.
i_2 = (int) j_3;
if (i_2 < 0)
{
t = j_2 * 2;
}
Am I missing something here?
It works if you push the old value before calling vrp_visit_stmt, yes.
But I think
you want to do that only if the value-range changed to avoid too many changes
on the stack. I guess we can defer further refactoring and
optimization of this case
to the point where we consider looking back very aggressively.
+/* Visit the basic blocks in the dominance order and set the Value Ranges
(VR)
+ for SSA_NAMEs in the scope. Use this VR to discover more VRs.
Restore the
+ old VR once the scope is exited. */
+
+static bool
+evrp_visit_phi_node_local (gphi *phi)
+{
+ size_t i;
+ tree lhs = PHI_RESULT (phi);
+ value_range vr_result = VR_INITIALIZER;
+ bool first = true;
+ int edges;
+
+ edges = 0;
+ for (i = 0; i < gimple_phi_num_args (phi); i++)
+ {
+ edge e = gimple_phi_arg_edge (phi, i);
+ tree arg = PHI_ARG_DEF (phi, i);
+ value_range vr_arg = VR_INITIALIZER;
+ ++edges;
+
+ /* If there is a back-edge, set the result to VARYING. */
+ if (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX))
+ {
+ set_value_range_to_varying (&vr_result);
+ break;
+ }
...
+ /* If any of the RHS value is VARYING, set the result to VARYING.
*/
+ if ((vr_arg.type != VR_RANGE)
+ && (vr_arg.type != VR_ANTI_RANGE))
+ {
+ set_value_range_to_varying (&vr_result);
+ break;
+ }
this shows that you need to start conservative for a DOM based VRP,
thus with all lattice values initialized to VARYING (but undefined SSA
names of course still can be UNDEFINED) rather than UNDEFINED.
+ if (TREE_CODE (arg) == SSA_NAME)
+ vr_arg = *(get_value_range (arg));
+ else
+ set_value_range_to_varying (&vr_arg);
err - what about constants? When you initialize the lattice properly
you should be able to re-use vrp_visit_phi_node (maybe split out
its head to avoid using SCEV or the iteration limitation).
I also like re-using vrp_visit_phi_node but the issue is, we will have to
keep a work-list of nodes to be re-evaluated till the lattice reach a
fixpoint. Is that OK with you?
No, why would you need to iterate here? As said, the key point is to
initialize value-ranges as VARYING rather than UNDEFINED.
If we are to do this, we should be able to reuse the callbacks
vrp_visit_phi_node and vrp_visit_stmt as it is.
Do you have a reference to your DOM based prototype?
I never posted it I think, it's structure is similar to yours with lots
of ??? comments ;)
Here is an updated patch which addresses the earlier review comments.
Just to see the effectiveness of this, I did a simple test.
That is, I built gcc with --enable-languages=c,c++ --disable-bootstrap
--disable-multilib and added -fdump-ipa-cp to the compiler flag and
grepped for number of times ipa-vrp (with the ipa-vrp patch) is setting
the value range for argument. I also did the same with tree-vrp used in
place of tree-evrp as an early vrp. tree-evrp is setting 186 times
compared to tree-vrp which is setting 207 times. I didn't see the actual
value ranges which can also make lots of difference.
In future we might want to iterate on dom based vrp till fixed point is
reached if there is a need.
Thanks,
Kugan
>From 17ea87a0e47a0d2325376d6a66a3ff1d5d70c0b4 Mon Sep 17 00:00:00 2001
From: Kugan Vivekanandarajah <kugan.vivekanandara...@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
