From: kugan <kugan.vivekanandarajah@linaro.org>
To: Richard Biener <richard.guenther@gmail.com>
Cc: Andrew Pinski <pinskia@gmail.com>,
"gcc-patches@gcc.gnu.org" <gcc-patches@gcc.gnu.org>,
Jan Hubicka <hubicka@ucw.cz>, Martin Jambor <mjambor@suse.cz>
Subject: Re: [RFC][IPA-VRP] Early VRP Implementation
Date: Tue, 20 Sep 2016 05:48:00 -0000 [thread overview]
Message-ID: <2fc6782e-fbb8-c955-c3a7-f2e9b8845134@linaro.org> (raw)
In-Reply-To: <CAFiYyc2gZAjfgxCgfT9_nTxBpBGbMg1-_Ck=6mR9ufEWaG_8tw@mail.gmail.com>
[-- Attachment #1: Type: text/plain, Size: 14554 bytes --]
Hi Richard,
Thanks for the review.
On 19/09/16 22:56, Richard Biener wrote:
> On Sun, Sep 18, 2016 at 10:50 PM, kugan
> <kugan.vivekanandarajah@linaro.org> wrote:
>> Hi Richard,
>>
>>
>>
>> On 16/09/16 20:21, Richard Biener wrote:
>>>
>>> On Fri, Sep 16, 2016 at 7:59 AM, kugan
>>> <kugan.vivekanandarajah@linaro.org> wrote:
>>>>
>>>> Hi Richard,
>>>>
>>>> Thanks for the review.
>>>>
>>>> On 14/09/16 22:04, Richard Biener wrote:
>>>>>
>>>>>
>>>>> On Tue, Aug 23, 2016 at 4:11 AM, Kugan Vivekanandarajah
>>>>> <kugan.vivekanandarajah@linaro.org> wrote:
>>>>>>
>>>>>>
>>>>>> Hi,
>>>>>>
>>>>>> On 19 August 2016 at 21:41, Richard Biener <richard.guenther@gmail.com>
>>>>>> wrote:
>>>>>>>
>>>>>>>
>>>>>>> On Tue, Aug 16, 2016 at 9:45 AM, kugan
>>>>>>> <kugan.vivekanandarajah@linaro.org> wrote:
>>>>>>>>
>>>>>>>>
>>>>>>>> Hi Richard,
>>>>
>>>>
>>>>
>>>>>>>> I am now having -ftree-evrp which is enabled all the time. But This
>>>>>>>> will
>>>>>>>> only be used for disabling the early-vrp. That is, early-vrp will be
>>>>>>>> run
>>>>>>>> when ftree-vrp is enabled and ftree-evrp is not explicitly disabled.
>>>>>>>> Is
>>>>>>>> this
>>>>>>>> OK?
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> Why would one want to disable early-vrp? I see you do this in the
>>>>>>> testsuite
>>>>>>> for non-early VRP unit-tests but using -fdisable-tree-evrp1 there
>>>>>>> would be ok as well.
>>>>>>
>>>>>>
>>>>>>
>>>>>> Removed it altogether. I though that you wanted a way to disable
>>>>>> early-vrp for testing purposes.
>>>>>
>>>>>
>>>>>
>>>>> But there is via the generic -fdisable-tree-DUMPFILE way.
>>>>
>>>>
>>>>
>>>> OK. I didnt know about that.
>>>>
>>>>
>>>>>>> Note that you want to have a custom valueize function instead of just
>>>>>>> follow_single_use_edges as you want to valueize all SSA names
>>>>>>> according
>>>>>>> to their lattice value (if it has a single value). You can use
>>>>>>> vrp_valueize
>>>>>>> for this though that gets you non-single-use edge following as well.
>>>>>>> Eventually it's going to be cleaner to do what the SSA propagator does
>>>>>>> and
>>>>>>> before folding do
>>>>>>>
>>>>>>> did_replace = replace_uses_in (stmt, vrp_valueize);
>>>>>>> if (fold_stmt (&gsi, follow_single_use_edges)
>>>>>>> || did_replace)
>>>>>>> update_stmt (gsi_stmt (gsi));
>>>>>>>
>>>>>>> exporting replace_uses_in for this is ok. I guess I prefer this for
>>>>>>> now.
>>>>>>
>>>>>>
>>>>>>
>>>>>> I also added the above. I noticed that I need
>>>>>> recompute_tree_invariant_for_addr_expr as in ssa_propagate. My initial
>>>>>> implementation also had gimple_purge_all_dead_eh_edges and
>>>>>> fixup_noreturn_call as in ssa_propagat but I thinj that is not needed
>>>>>> as it would be done at the end of the pass.
>>>>>
>>>>>
>>>>>
>>>>> I don't see this being done at the end of the pass. So please
>>>>> re-instantiate
>>>>> that parts.
>>>>
>>>>
>>>>
>>>> I have copied these part as well.
>>>>
>>>>>> With this I noticed more stmts are folded before vrp1. This required
>>>>>> me to adjust some testcases.
>>>>>>
>>>>>>>
>>>>>>> Overall this now looks good apart from the folding and the
>>>>>>> VR_INITIALIZER thing.
>>>>>>>
>>>>>>> You can commit the already approved refactoring changes and combine
>>>>>>> this
>>>>>>> patch with the struct value_range move, this way I can more easily
>>>>>>> look
>>>>>>> into
>>>>>>> issues with the UNDEFINED thing if you can come up with a testcase
>>>>>>> that
>>>>>>> doesn't work.
>>>>>>>
>>>>>>
>>>>>> I have now committed all the dependent patches.
>>>>>>
>>>>>> Attached patch passes regression and bootstrap except pr33738.C. This
>>>>>> is an unrelated issue as discussed in
>>>>>> https://gcc.gnu.org/ml/gcc-patches/2016-08/msg01386.html
>>>>>>
>>>>>> Is this OK?
>>>>>
>>>>>
>>>>>
>>>>> +/* Initialize local data structures for VRP. If DOM_P is true,
>>>>> + we will be calling this from early_vrp where value range propagation
>>>>> + is done by visiting stmts in dominator tree. ssa_propagate engine
>>>>> + is not used in this case and that part of the ininitialization will
>>>>> + be skipped. */
>>>>> +
>>>>> +static void
>>>>> +vrp_initialize ()
>>>>>
>>>>> comment needs updating now.
>>>>>
>>>> Done.
>>>>
>>>>>
>>>>> static void
>>>>> -extract_range_from_phi_node (gphi *phi, value_range *vr_result)
>>>>> +extract_range_from_phi_node (gphi *phi, value_range *vr_result,
>>>>> + bool early_vrp_p)
>>>>> {
>>>>>
>>>>>
>>>>> I don't think you need this changes now that you have
>>>>> stmt_visit_phi_node_in_dom_p
>>>>> guarding its call.
>>>>
>>>>
>>>>
>>>> OK removed it. That also mean I had to put scev_* in the early_vrp.
>>>>
>>>>
>>>>
>>>>> +static bool
>>>>> +stmt_visit_phi_node_in_dom_p (gphi *phi)
>>>>> +{
>>>>> + ssa_op_iter iter;
>>>>> + use_operand_p oprnd;
>>>>> + tree op;
>>>>> + value_range *vr;
>>>>> + FOR_EACH_PHI_ARG (oprnd, phi, iter, SSA_OP_USE)
>>>>> + {
>>>>> + op = USE_FROM_PTR (oprnd);
>>>>> + if (TREE_CODE (op) == SSA_NAME)
>>>>> + {
>>>>> + vr = get_value_range (op);
>>>>> + if (vr->type == VR_UNDEFINED)
>>>>> + return false;
>>>>> + }
>>>>> + }
>>>>>
>>>>> I think this is overly conservative in never allowing UNDEFINED on PHI
>>>>> node args (even if the def was actually visited). I think that the most
>>>>> easy way to improve this bit would be to actually track visited blocks.
>>>>> You already set the EDGE_EXECUTABLE flag on edges so you could
>>>>> clear BB_VISITED on all blocks and set it in the before_dom_children
>>>>> hook (at the end). Then the above can be folded into the PHI visiting:
>>>>>
>>>>> bool has_unvisited_pred = false;
>>>>> FOR_EACH_EDGE (e, ei, bb->preds)
>>>>> if (!(e->src->flags & BB_VISITED))
>>>>> {
>>>>> has_unvisited_preds = true;
>>>>> break;
>>>>> }
>>>>>
>>>> OK done.
>>>>
>>>> I also had to check for uninitialized variables that will have
>>>> VR_UNDEFINED
>>>> as range. We do not visit GIMPLE_NOP.
>>>
>>>
>>> But VR_UNDEFINED of uninitialized variables is fine to use.
>>
>>
>> Indeed. I was really trying to fix another problem with this.
>>
>> The real problem I am facing is:
>>
>> When we have a PHI stmt with one argument as symbolic VR_RANGE and another
>> as VR_UNDEFINED, we will copy VR_RANGE to the PHI result.
>>
>> When we fold the uses of the PHI result with vrp_valueize, we will assign
>> the symbol from VR_RANGE if that is of the form [a, a].
>>
>> However, in replace_uses_in, we dont see if the SSA definition dominates the
>> gimple that uses it. This some times results in ICE.
>
> Indeed -- ccp_lattice_meet avoids this by not merging UNDEF and SSA to SSA.
>
> VRP uses op_with_constant_singleton_value_range for the valueization at
> substitute_and_fold time which only substitutes constants.
>
>> For now, in the vrp_valueize, I have commented out the SSA_NAME part (as
>> shown in the attached patch). With that I can bootstrap and regression test
>> the patch.
>>
>> The fix is to either:
>>
>> 1. Remove SSA_NAME from vrp_valueize. Currently we use vrp_valueize with
>> gimple_fold_stmt_to_constant_1 and accepts only is_gimple_min_invariant.
>> Therefore maybe SSA_NAME is not needed?
>
> Yeah, technically it is not needed.
>
>> 2. Or, in replace_uses_in, see if the stmt dominates operand definition
>> before replacing.
>
> We need to treat the valueization as a "value number" and separately
> keep track of available DEFs we can substitute. See for example how
> FRE/PRE handle this in eliminate_dom_walker. The substitute-and-fold
> DOM walker would need to be adjusted similarly (and your copy of it
> in DOM VRP).
>
> Short-cutting this at vrp_valueize will remove some valid foldings to
> constants but I think you can simply use op_with_constant_singleton_value_range
> for the replace_uses_in call.
>
> The patch is ok with that change.
Attached is the patch based on the above comments. I have marked
gcc/testsuite/g++.dg/warn/pr33738.C as XFAIL and will try to fix this
based on the discussion from
https://gcc.gnu.org/ml/gcc-patches/2016-08/msg01386.html
I will commit it after fresh bootstrap and regression testing.
Thanks,
Kugan
>
> Thanks,
> Richard.
>
>>>>
>>>>> + /* Visit PHI stmts and discover any new VRs possible. */
>>>>> + gimple_stmt_iterator gsi;
>>>>> + for (gphi_iterator gpi = gsi_start_phis (bb);
>>>>> + !gsi_end_p (gpi); gsi_next (&gpi))
>>>>> + {
>>>>> + gphi *phi = gpi.phi ();
>>>>> + tree lhs = PHI_RESULT (phi);
>>>>> + value_range vr_result = VR_INITIALIZER;
>>>>> + if (! has_unvisived_preds
>>>>> && stmt_interesting_for_vrp (phi)
>>>>> + && stmt_visit_phi_node_in_dom_p (phi))
>>>
>>>
>>> failed to remove this call to stmt_visit_phi_node_in_dom_p -- whether we
>>> need to
>>> drop to varying is a property that is the same for all PHI nodes in a
>>> block.
>>>
>> Done.
>>
>>>>> + extract_range_from_phi_node (phi, &vr_result, true);
>>>>> + else
>>>>> + set_value_range_to_varying (&vr_result);
>>>>> + update_value_range (lhs, &vr_result);
>>>>> + }
>>>>>
>>>>> due to a bug in IRA you need to make sure to un-set BB_VISITED after
>>>>> early-vrp is finished again.
>>>>
>>>>
>>>> OK. Done.
>>>
>>>
>>> You set BB_VISITED in after_dom_children -- that is too late, please
>>> set it at the end
>>> of before_dom_children. Otherwise it pessimizes handling of the PHIs
>>> in the merge
>>> block of a diamond in case the PHI args are defined in the immediate
>>> dominator.
>>>
>>> As said you need to clear BB_VISITED at the start of evrp as well
>>> (clearing at the end
>>> is just a workaround for a IRA bug).
>>
>> Done.
>>
>>>>>
>>>>> + /* Try folding stmts with the VR discovered. */
>>>>> + bool did_replace = replace_uses_in (stmt, evrp_valueize);
>>>>> + if (fold_stmt (&gsi, follow_single_use_edges)
>>>>> + || did_replace)
>>>>> + update_stmt (gsi_stmt (gsi));
>>>>>
>>>>> you should be able to re-use vrp_valueize here.
>>>>
>>>>
>>>> This issue is vrp_valueize accepts ranges such as [VAR + CST, VAR + CST]
>>>> which we can not set.
>>>
>>>
>>> Oh - that looks like sth we need to fix anyway then. May I suggest to
>>> change
>>> vrp_valueize to do
>>>
>>> && (TREE_CODE (vr->min) == SSA_NAME
>>> || is_gimple_min_invariant (TREE_CODE (vr->min)))
>>>
>>> which also allows [&a, &a] like constants.
>>
>>
>> Please see the error above.
>>
>>
>>>>>
>>>>> + def_operand_p def_p = SINGLE_SSA_DEF_OPERAND (stmt,
>>>>> SSA_OP_DEF);
>>>>> + /* Set the SSA with the value range. */
>>>>> + if (def_p
>>>>> + && TREE_CODE (DEF_FROM_PTR (def_p)) == SSA_NAME
>>>>> + && INTEGRAL_TYPE_P (TREE_TYPE (DEF_FROM_PTR (def_p))))
>>>>> + {
>>>>> + tree def = DEF_FROM_PTR (def_p);
>>>>> + unsigned ver = SSA_NAME_VERSION (def);
>>>>> + if ((vr_value[ver]->type == VR_RANGE
>>>>>
>>>>> Use get_value_range () please, not direct access to vr_value.
>>>>>
>>>> Done.
>>>>
>>>>> + || vr_value[ver]->type == VR_ANTI_RANGE)
>>>>> + && (TREE_CODE (vr_value[ver]->min) == INTEGER_CST)
>>>>> + && (TREE_CODE (vr_value[ver]->max) == INTEGER_CST))
>>>>> + set_range_info (def, vr_value[ver]->type,
>>>>> vr_value[ver]->min,
>>>>> + vr_value[ver]->max);
>>>>> + }
>>>>>
>>>>> Otherwise the patch looks good now (with a lot of improvement
>>>>> possibilities of course).
>>>>
>>>>
>>>> I will work on the improvement after this goes in.
>>>>
>>>> Bootstrapped and regression tested on x86_64-linux-gnu. Does this looks
>>>> OK?
>>>
>>>
>>> Please remove no-op changes like
>>
>> Done.
>>
>>
>>> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr22117.c
>>> b/gcc/testsuite/gcc.dg/tree-ssa/pr22117.c
>>> index 7efdd63..3a433d6 100644
>>> --- a/gcc/testsuite/gcc.dg/tree-ssa/pr22117.c
>>> +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr22117.c
>>> @@ -3,7 +3,7 @@
>>> known to be zero after entering the first two "if" statements. */
>>>
>>> /* { dg-do compile } */
>>> -/* { dg-options "-O2 -fdump-tree-vrp1" } */
>>> +/* { dg-options "-O2 -fdump-tree-vrp1" } */
>>>
>>> void link_error (void);
>>>
>>> @@ -21,4 +21,4 @@ foo (int *p, int q)
>>> }
>>> }
>>>
>>> -/* { dg-final { scan-tree-dump-times "Folding predicate r_.* != 0B to
>>> 0" 1 "vrp1" } } */
>>> +/* { dg-final { scan-tree-dump-times "link_error" 0 "vrp1" } } */
>>> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr25382.c
>>> b/gcc/testsuite/gcc.dg/tree-ssa/pr25382.c
>>> index dcf9148..c4fda8b 100644
>>> --- a/gcc/testsuite/gcc.dg/tree-ssa/pr25382.c
>>> +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr25382.c
>>> @@ -3,7 +3,7 @@
>>> Check that VRP now gets ranges from BIT_AND_EXPRs. */
>>>
>>> /* { dg-do compile } */
>>> -/* { dg-options "-O2 -fno-tree-ccp -fdump-tree-vrp1" } */
>>> +/* { dg-options "-O2 -fno-tree-ccp -fdump-tree-vrp" } */
>>>
>>> int
>>> foo (int a)
>>>
>>>
>>> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp46.c
>>> b/gcc/testsuite/gcc.dg/tree-ssa/vrp46.c
>>> index d3c9ed1..5b279a1 100644
>>> --- a/gcc/testsuite/gcc.dg/tree-ssa/vrp46.c
>>> +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp46.c
>>> @@ -27,6 +27,5 @@ func_18 ( int t )
>>> }
>>> }
>>>
>>> -/* There should be a single if left. */
>>>
>>> -/* { dg-final { scan-tree-dump-times "if" 1 "vrp1" } } */
>>> +/* { dg-final { scan-tree-dump-times "if" 0 "vrp1" } } */
>>>
>>> I'm curious -- this is not a dg-run testcase but did you investigate this
>>> isn't generating wrong code now? At least I can't see how
>>> the if (1 & (t % rhs)) test could vanish.
>>
>> Indeed.This was a mistake and fixed it.
>>
>>
>>> I hope we'll get GIMPLE unit testing finished for GCC 7 so we can add
>>> separate
>>> unit-tests for VRP and EVRP.
>>
>>
>> I will have a look at it.
>>
>> Thanks,
>> Kugan
>>
>>
>>> Thanks,
>>> Richard.
>>>
>>>
>>>> Thanks,
>>>> Kugan
>>>>
>>>>
>>>>
>>>>>
>>>>> Thanks and sorry for the delay,
>>>>> Richard.
>>>>>
>>>>>> Thanks,
>>>>>> Kugan
>>>>>>
>>>>>>
>>>>>>> Thanks,
>>>>>>> Richard.
>>>>>>>
>>>>>>>> I also noticed that g++.dg/warn/pr33738.C testcase is now failing.
>>>>>>>> This
>>>>>>>> is
>>>>>>>> because, with early-vrp setting value range ccp2 is optimizing
>>>>>>>> without
>>>>>>>> issuing a warning. I will look into it.
>>>>>>>>
>>>>>>>> bootstrap and regression testing is in progress.
>>>>>>>>
>>>>>>>> Thanks,
>>>>>>>> Kugan
[-- Attachment #2: 0001-Add-early-vrp.patch --]
[-- Type: text/x-patch, Size: 30599 bytes --]
From 42cef3f7abc956ece46e4303e3a6d68464dde99c Mon Sep 17 00:00:00 2001
From: Kugan Vivekanandarajah <kugan.vivekanandarajah@linaro.org>
Date: Tue, 23 Aug 2016 16:18:30 +1000
Subject: [PATCH 1/3] Add early-vrp
---
gcc/doc/invoke.texi | 5 +
gcc/passes.def | 1 +
gcc/testsuite/g++.dg/tree-ssa/pr31146-2.C | 2 +-
gcc/testsuite/g++.dg/warn/pr33738.C | 4 +-
gcc/testsuite/gcc.dg/tree-ssa/evrp1.c | 13 +
gcc/testsuite/gcc.dg/tree-ssa/evrp2.c | 18 ++
gcc/testsuite/gcc.dg/tree-ssa/evrp3.c | 15 +
gcc/testsuite/gcc.dg/tree-ssa/pr20657.c | 4 +-
gcc/testsuite/gcc.dg/tree-ssa/pr22117.c | 2 +-
gcc/testsuite/gcc.dg/tree-ssa/pr37508.c | 2 +-
gcc/testsuite/gcc.dg/tree-ssa/pr61839_2.c | 8 +-
gcc/testsuite/gcc.dg/tree-ssa/pr64130.c | 6 +-
gcc/testsuite/gcc.dg/tree-ssa/vrp04.c | 2 +-
gcc/testsuite/gcc.dg/tree-ssa/vrp06.c | 4 +-
gcc/testsuite/gcc.dg/tree-ssa/vrp16.c | 4 +-
gcc/testsuite/gcc.dg/tree-ssa/vrp25.c | 4 +-
gcc/testsuite/gcc.dg/tree-ssa/vrp67.c | 2 +-
gcc/timevar.def | 1 +
gcc/tree-pass.h | 1 +
gcc/tree-ssa-propagate.c | 2 +-
gcc/tree-ssa-propagate.h | 1 +
gcc/tree-vrp.c | 467 ++++++++++++++++++++++++++----
22 files changed, 492 insertions(+), 76 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/evrp1.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/evrp2.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/evrp3.c
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index 87da1f1..9ed9c24 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -12454,6 +12454,11 @@ is made by appending @file{.slp} to the source file name.
Dump each function after Value Range Propagation (VRP). The file name
is made by appending @file{.vrp} to the source file name.
+@item early vrp
+@opindex fdump-tree-evrp
+Dump each function after Early Value Range Propagation (EVRP). The file name
+is made by appending @file{.evrp} to the source file name.
+
@item oaccdevlow
@opindex fdump-tree-oaccdevlow
Dump each function after applying device-specific OpenACC transformations.
diff --git a/gcc/passes.def b/gcc/passes.def
index 533157d..9759fed 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -89,6 +89,7 @@ along with GCC; see the file COPYING3. If not see
execute TODO_rebuild_alias at this point. */
NEXT_PASS (pass_build_ealias);
NEXT_PASS (pass_fre);
+ NEXT_PASS (pass_early_vrp);
NEXT_PASS (pass_merge_phi);
NEXT_PASS (pass_dse);
NEXT_PASS (pass_cd_dce);
diff --git a/gcc/testsuite/g++.dg/tree-ssa/pr31146-2.C b/gcc/testsuite/g++.dg/tree-ssa/pr31146-2.C
index 5e09583..cf4ed33 100644
--- a/gcc/testsuite/g++.dg/tree-ssa/pr31146-2.C
+++ b/gcc/testsuite/g++.dg/tree-ssa/pr31146-2.C
@@ -1,5 +1,5 @@
/* { dg-do compile } */
-/* { dg-options "-O -fdump-tree-forwprop1" } */
+/* { dg-options "-O -fno-tree-vrp -fdump-tree-forwprop1" } */
#include <new>
diff --git a/gcc/testsuite/g++.dg/warn/pr33738.C b/gcc/testsuite/g++.dg/warn/pr33738.C
index 60ee0b4..73e98d5 100644
--- a/gcc/testsuite/g++.dg/warn/pr33738.C
+++ b/gcc/testsuite/g++.dg/warn/pr33738.C
@@ -15,11 +15,11 @@ int GetM1() {
int main() {
a2 = static_cast<Alpha>(GetM1());
- if (a2 == -1) { // { dg-warning "always false due" }
+ if (a2 == -1) { // { dg-warning "always false due" "" { xfail *-*-* } } */
link_error ();
}
a2 = static_cast<Alpha>(GetM1());
- if (-1 == a2) { // { dg-warning "always false due" }
+ if (-1 == a2) { // { dg-warning "always false due" "" { xfail *-*-* } } */
link_error ();
}
return 0;
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/evrp1.c b/gcc/testsuite/gcc.dg/tree-ssa/evrp1.c
new file mode 100644
index 0000000..8c6e4e6
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/evrp1.c
@@ -0,0 +1,13 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-evrp" } */
+
+int foo (int i);
+int bar (int j)
+{
+ if (j > 2)
+ return foo (j + 2);
+ else
+ return j;
+}
+
+/* { dg-final { scan-tree-dump "\\\[5, \\+INF" "evrp" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/evrp2.c b/gcc/testsuite/gcc.dg/tree-ssa/evrp2.c
new file mode 100644
index 0000000..e6d4235
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/evrp2.c
@@ -0,0 +1,18 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-evrp" } */
+
+int foo (int i);
+int bar2 (int j)
+{
+ if (j > 2)
+ {
+ if (j < 7)
+ return foo (j + 1);
+ else
+ return foo (j + 2);
+ }
+ return j;
+}
+
+
+/* { dg-final { scan-tree-dump "\\\[4, 7\\\]" "evrp" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/evrp3.c b/gcc/testsuite/gcc.dg/tree-ssa/evrp3.c
new file mode 100644
index 0000000..1a3bbd5
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/evrp3.c
@@ -0,0 +1,15 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-evrp" } */
+
+int foo (int i);
+void bar (int j)
+{
+ unsigned int i;
+ for (i = 0; i < 10; ++i)
+ {
+ bar (i + 1);
+ }
+}
+
+/* { dg-final { scan-tree-dump "\\\[1, 10\\\]" "evrp" } } */
+
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr20657.c b/gcc/testsuite/gcc.dg/tree-ssa/pr20657.c
index 727ca4c..e678231 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr20657.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr20657.c
@@ -3,7 +3,7 @@
statement, which was needed to eliminate the second "if" statement. */
/* { dg-do compile } */
-/* { dg-options "-O2 -fno-tree-dominator-opts -fno-tree-fre -fdump-tree-vrp1-details" } */
+/* { dg-options "-O2 -fno-tree-dominator-opts -fno-tree-fre -fdump-tree-evrp" } */
int
foo (int a)
@@ -14,4 +14,4 @@ foo (int a)
return 0;
}
-/* { dg-final { scan-tree-dump-times "Folding predicate" 1 "vrp1"} } */
+/* { dg-final { scan-tree-dump-times "if" 1 "evrp"} } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr22117.c b/gcc/testsuite/gcc.dg/tree-ssa/pr22117.c
index 7efdd63..01cd33e 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr22117.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr22117.c
@@ -21,4 +21,4 @@ foo (int *p, int q)
}
}
-/* { dg-final { scan-tree-dump-times "Folding predicate r_.* != 0B to 0" 1 "vrp1" } } */
+/* { dg-final { scan-tree-dump-times "link_error" 0 "vrp1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr37508.c b/gcc/testsuite/gcc.dg/tree-ssa/pr37508.c
index 0963cd9..2ba09af 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr37508.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr37508.c
@@ -46,4 +46,4 @@ int test4 (struct foo2 *x)
return 0;
}
-/* { dg-final { scan-tree-dump-times "Folding" 2 "vrp1" } } */
+/* { dg-final { scan-tree-dump-times "if" 2 "vrp1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr61839_2.c b/gcc/testsuite/gcc.dg/tree-ssa/pr61839_2.c
index ffa00a7..e44dc57 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr61839_2.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr61839_2.c
@@ -1,6 +1,6 @@
/* PR tree-optimization/61839. */
/* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-vrp1" } */
+/* { dg-options "-O2 -fdump-tree-evrp" } */
/* { dg-require-effective-target int32plus } */
__attribute__ ((noinline))
@@ -47,8 +47,8 @@ int bar2 ()
/* Dont optimize 972195717 / 0 in function foo. */
-/* { dg-final { scan-tree-dump-times "972195717 / _" 1 "vrp1" } } */
+/* { dg-final { scan-tree-dump-times "972195717 / _" 1 "evrp" } } */
/* Dont optimize 972195717 % 0 in function bar. */
-/* { dg-final { scan-tree-dump-times "972195717 % _" 1 "vrp1" } } */
+/* { dg-final { scan-tree-dump-times "972195717 % _" 1 "evrp" } } */
/* Optimize in function bar2. */
-/* { dg-final { scan-tree-dump-times "972195715 % _" 0 "vrp1" } } */
+/* { dg-final { scan-tree-dump-times "972195715 % _" 0 "evrp" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr64130.c b/gcc/testsuite/gcc.dg/tree-ssa/pr64130.c
index 0b25466..f39bd17 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr64130.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr64130.c
@@ -1,6 +1,6 @@
/* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-vrp1" } */
+/* { dg-options "-O2 -fdump-tree-evrp" } */
int funsigned (unsigned a)
{
@@ -13,6 +13,6 @@ int funsigned2 (unsigned a)
return (-1 * 0x1ffffffffL) / a == 0;
}
-/* { dg-final { scan-tree-dump ": \\\[2, 8589934591\\\]" "vrp1" } } */
-/* { dg-final { scan-tree-dump ": \\\[-8589934591, -2\\\]" "vrp1" } } */
+/* { dg-final { scan-tree-dump ": \\\[2, 8589934591\\\]" "evrp" } } */
+/* { dg-final { scan-tree-dump ": \\\[-8589934591, -2\\\]" "evrp" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp04.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp04.c
index 61b7a47..67f8f01 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/vrp04.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp04.c
@@ -10,4 +10,4 @@ foo (int a, int b)
return a + b;
}
-/* { dg-final { scan-tree-dump-times "Folding predicate a_.*to 1" 1 "vrp1" } } */
+/* { dg-final { scan-tree-dump-times "if" 1 "vrp1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp06.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp06.c
index cdad534..c4ce170 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/vrp06.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp06.c
@@ -28,6 +28,6 @@ foo (int i, int j, int a)
return i + a + j;
}
-/* { dg-final { scan-tree-dump-times "Folding predicate i_\[0-9\]+.*0 to 0" 1 "vrp1" } } */
-/* { dg-final { scan-tree-dump-times "Folding predicate j_\[0-9\]+.*0 to 1" 1 "vrp1" } } */
+/* { dg-final { scan-tree-dump-times "Folding predicate \[i|j\]_\[0-9\]+.*0 to 0" 1 "vrp1" } } */
+/* { dg-final { scan-tree-dump-times "Folding predicate \[i|j\]_\[0-9\]+.*0 to 1" 1 "vrp1" } } */
/* { dg-final { scan-tree-dump-times "Folding predicate i_\[0-9]+.*j_\[0-9\]+.* to 0" 1 "vrp1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp16.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp16.c
index 8f5d5c8..d09f3ae 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/vrp16.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp16.c
@@ -1,5 +1,5 @@
/* { dg-do compile } */
-/* { dg-options "-O2 -fno-tree-fre -fdump-tree-vrp1-details" } */
+/* { dg-options "-O2 -fno-tree-fre -fdump-tree-evrp" } */
extern void abort (void) __attribute__ ((__noreturn__));
@@ -19,5 +19,5 @@ nonlocal_mentioned_p (rtx x)
abort ();
}
-/* { dg-final { scan-tree-dump-times "Folding predicate .*to 0" 1 "vrp1" } } */
+/* { dg-final { scan-tree-dump-times "if" 0 "evrp" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp25.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp25.c
index cbc4ec3..a49f079 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/vrp25.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp25.c
@@ -1,5 +1,5 @@
/* { dg-do compile } */
-/* { dg-options "-O2 -fno-tree-fre -fdump-tree-vrp1-details" } */
+/* { dg-options "-O2 -fno-tree-fre -fdump-tree-vrp1" } */
extern void abort ();
extern void arf ();
@@ -49,5 +49,5 @@ L9:
/* The second test of (code1 != 53) and the test (D18670 <= 2) are
both totally subsumed by earlier tests and thus should be folded
away using VRP. */
-/* { dg-final { scan-tree-dump-times "Folding predicate" 2 "vrp1" } } */
+/* { dg-final { scan-tree-dump-times "if" 3 "vrp1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp67.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp67.c
index ef5e8f9..5155f7b 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/vrp67.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp67.c
@@ -36,4 +36,4 @@ unsigned baz (unsigned i)
return i;
}
-/* { dg-final { scan-tree-dump-times "Folding predicate" 3 "vrp1" } } */
+/* { dg-final { scan-tree-dump-times "if" 3 "vrp1" } } */
diff --git a/gcc/timevar.def b/gcc/timevar.def
index 5f12118..8837832 100644
--- a/gcc/timevar.def
+++ b/gcc/timevar.def
@@ -149,6 +149,7 @@ DEFTIMEVAR (TV_TREE_CFG , "tree CFG construction")
DEFTIMEVAR (TV_TREE_CLEANUP_CFG , "tree CFG cleanup")
DEFTIMEVAR (TV_TREE_TAIL_MERGE , "tree tail merge")
DEFTIMEVAR (TV_TREE_VRP , "tree VRP")
+DEFTIMEVAR (TV_TREE_EARLY_VRP , "tree Early VRP")
DEFTIMEVAR (TV_TREE_COPY_PROP , "tree copy propagation")
DEFTIMEVAR (TV_FIND_REFERENCED_VARS , "tree find ref. vars")
DEFTIMEVAR (TV_TREE_PTA , "tree PTA")
diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
index c0059de..86d797e 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -440,6 +440,7 @@ extern gimple_opt_pass *make_pass_fre (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_check_data_deps (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_copy_prop (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_isolate_erroneous_paths (gcc::context *ctxt);
+extern gimple_opt_pass *make_pass_early_vrp (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_vrp (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_uncprop (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_return_slot (gcc::context *ctxt);
diff --git a/gcc/tree-ssa-propagate.c b/gcc/tree-ssa-propagate.c
index c8cf078..97cfde5 100644
--- a/gcc/tree-ssa-propagate.c
+++ b/gcc/tree-ssa-propagate.c
@@ -863,7 +863,7 @@ static struct prop_stats_d prop_stats;
/* Replace USE references in statement STMT with the values stored in
PROP_VALUE. Return true if at least one reference was replaced. */
-static bool
+bool
replace_uses_in (gimple *stmt, ssa_prop_get_value_fn get_value)
{
bool replaced = false;
diff --git a/gcc/tree-ssa-propagate.h b/gcc/tree-ssa-propagate.h
index 30d66a9..1a96976 100644
--- a/gcc/tree-ssa-propagate.h
+++ b/gcc/tree-ssa-propagate.h
@@ -84,5 +84,6 @@ extern void propagate_value (use_operand_p, tree);
extern void replace_exp (use_operand_p, tree);
extern void propagate_tree_value (tree *, tree);
extern void propagate_tree_value_into_stmt (gimple_stmt_iterator *, tree);
+extern bool replace_uses_in (gimple *stmt, ssa_prop_get_value_fn get_value);
#endif /* _TREE_SSA_PROPAGATE_H */
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 45882c4..c8481c9 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -60,6 +60,8 @@ along with GCC; see the file COPYING3. If not see
#include "case-cfn-macros.h"
#include "params.h"
#include "alloc-pool.h"
+#include "domwalk.h"
+#include "tree-cfgcleanup.h"
#define VR_INITIALIZER { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }
@@ -1455,44 +1457,17 @@ op_with_boolean_value_range_p (tree op)
&& integer_onep (vr->max));
}
-/* Extract value range information from an ASSERT_EXPR EXPR and store
- it in *VR_P. */
+/* Extract value range information for VAR when (OP COND_CODE LIMIT) is
+ true and store it in *VR_P. */
static void
-extract_range_from_assert (value_range *vr_p, tree expr)
+extract_range_for_var_from_comparison_expr (tree var, enum tree_code cond_code,
+ tree op, tree limit,
+ value_range *vr_p)
{
- tree var, cond, limit, min, max, type;
+ tree min, max, type;
value_range *limit_vr;
- enum tree_code cond_code;
-
- var = ASSERT_EXPR_VAR (expr);
- cond = ASSERT_EXPR_COND (expr);
-
- gcc_assert (COMPARISON_CLASS_P (cond));
-
- /* Find VAR in the ASSERT_EXPR conditional. */
- if (var == TREE_OPERAND (cond, 0)
- || TREE_CODE (TREE_OPERAND (cond, 0)) == PLUS_EXPR
- || TREE_CODE (TREE_OPERAND (cond, 0)) == NOP_EXPR)
- {
- /* If the predicate is of the form VAR COMP LIMIT, then we just
- take LIMIT from the RHS and use the same comparison code. */
- cond_code = TREE_CODE (cond);
- limit = TREE_OPERAND (cond, 1);
- cond = TREE_OPERAND (cond, 0);
- }
- else
- {
- /* If the predicate is of the form LIMIT COMP VAR, then we need
- to flip around the comparison code to create the proper range
- for VAR. */
- cond_code = swap_tree_comparison (TREE_CODE (cond));
- limit = TREE_OPERAND (cond, 0);
- cond = TREE_OPERAND (cond, 1);
- }
-
limit = avoid_overflow_infinity (limit);
-
type = TREE_TYPE (var);
gcc_assert (limit != var);
@@ -1538,15 +1513,15 @@ extract_range_from_assert (value_range *vr_p, tree expr)
as well build the range [b_4, +INF] for it.
One special case we handle is extracting a range from a
range test encoded as (unsigned)var + CST <= limit. */
- if (TREE_CODE (cond) == NOP_EXPR
- || TREE_CODE (cond) == PLUS_EXPR)
+ if (TREE_CODE (op) == NOP_EXPR
+ || TREE_CODE (op) == PLUS_EXPR)
{
- if (TREE_CODE (cond) == PLUS_EXPR)
+ if (TREE_CODE (op) == PLUS_EXPR)
{
- min = fold_build1 (NEGATE_EXPR, TREE_TYPE (TREE_OPERAND (cond, 1)),
- TREE_OPERAND (cond, 1));
+ min = fold_build1 (NEGATE_EXPR, TREE_TYPE (TREE_OPERAND (op, 1)),
+ TREE_OPERAND (op, 1));
max = int_const_binop (PLUS_EXPR, limit, min);
- cond = TREE_OPERAND (cond, 0);
+ op = TREE_OPERAND (op, 0);
}
else
{
@@ -1730,6 +1705,41 @@ extract_range_from_assert (value_range *vr_p, tree expr)
vrp_intersect_ranges (vr_p, get_value_range (var));
}
+/* Extract value range information from an ASSERT_EXPR EXPR and store
+ it in *VR_P. */
+
+static void
+extract_range_from_assert (value_range *vr_p, tree expr)
+{
+ tree var = ASSERT_EXPR_VAR (expr);
+ tree cond = ASSERT_EXPR_COND (expr);
+ tree limit, op;
+ enum tree_code cond_code;
+ gcc_assert (COMPARISON_CLASS_P (cond));
+
+ /* Find VAR in the ASSERT_EXPR conditional. */
+ if (var == TREE_OPERAND (cond, 0)
+ || TREE_CODE (TREE_OPERAND (cond, 0)) == PLUS_EXPR
+ || TREE_CODE (TREE_OPERAND (cond, 0)) == NOP_EXPR)
+ {
+ /* If the predicate is of the form VAR COMP LIMIT, then we just
+ take LIMIT from the RHS and use the same comparison code. */
+ cond_code = TREE_CODE (cond);
+ limit = TREE_OPERAND (cond, 1);
+ op = TREE_OPERAND (cond, 0);
+ }
+ else
+ {
+ /* If the predicate is of the form LIMIT COMP VAR, then we need
+ to flip around the comparison code to create the proper range
+ for VAR. */
+ cond_code = swap_tree_comparison (TREE_CODE (cond));
+ limit = TREE_OPERAND (cond, 0);
+ op = TREE_OPERAND (cond, 1);
+ }
+ extract_range_for_var_from_comparison_expr (var, cond_code, op,
+ limit, vr_p);
+}
/* Extract range information from SSA name VAR and store it in VR. If
VAR has an interesting range, use it. Otherwise, create the
@@ -6947,19 +6957,24 @@ stmt_interesting_for_vrp (gimple *stmt)
return false;
}
-
-/* Initialize local data structures for VRP. */
+/* Initialize VRP lattice. */
static void
-vrp_initialize (void)
+vrp_initialize_lattice ()
{
- basic_block bb;
-
values_propagated = false;
num_vr_values = num_ssa_names;
vr_value = XCNEWVEC (value_range *, num_vr_values);
vr_phi_edge_counts = XCNEWVEC (int, num_ssa_names);
bitmap_obstack_initialize (&vrp_equiv_obstack);
+}
+
+/* Initialization required by ssa_propagate engine. */
+
+static void
+vrp_initialize ()
+{
+ basic_block bb;
FOR_EACH_BB_FN (bb, cfun)
{
@@ -7010,6 +7025,8 @@ vrp_valueize (tree name)
{
value_range *vr = get_value_range (name);
if (vr->type == VR_RANGE
+ && (TREE_CODE (vr->min) == SSA_NAME
+ || is_gimple_min_invariant (vr->min))
&& vrp_operand_equal_p (vr->min, vr->max))
return vr->min;
}
@@ -10500,6 +10517,22 @@ finalize_jump_threads (void)
delete equiv_stack;
}
+/* Free VRP lattice. */
+
+static void
+vrp_free_lattice ()
+{
+ /* Free allocated memory. */
+ free (vr_value);
+ free (vr_phi_edge_counts);
+ bitmap_obstack_release (&vrp_equiv_obstack);
+ vrp_value_range_pool.release ();
+
+ /* So that we can distinguish between VRP data being available
+ and not available. */
+ vr_value = NULL;
+ vr_phi_edge_counts = NULL;
+}
/* Traverse all the blocks folding conditionals with known ranges. */
@@ -10546,17 +10579,302 @@ vrp_finalize (bool warn_array_bounds_p)
/* We must identify jump threading opportunities before we release
the datastructures built by VRP. */
identify_jump_threads ();
+}
- /* Free allocated memory. */
- free (vr_value);
- free (vr_phi_edge_counts);
- bitmap_obstack_release (&vrp_equiv_obstack);
- vrp_value_range_pool.release ();
+/* evrp_dom_walker visits the basic blocks in the dominance order and set
+ the Value Ranges (VR) for SSA_NAMEs in the scope. Use this VR to
+ discover more VRs. */
- /* So that we can distinguish between VRP data being available
- and not available. */
- vr_value = NULL;
- vr_phi_edge_counts = NULL;
+class evrp_dom_walker : public dom_walker
+{
+public:
+ evrp_dom_walker ()
+ : dom_walker (CDI_DOMINATORS), stack (10)
+ {
+ stmts_to_fixup.create (0);
+ need_eh_cleanup = BITMAP_ALLOC (NULL);
+ }
+ ~evrp_dom_walker ()
+ {
+ stmts_to_fixup.release ();
+ BITMAP_FREE (need_eh_cleanup);
+ }
+ virtual edge before_dom_children (basic_block);
+ virtual void after_dom_children (basic_block);
+ void push_value_range (const_tree var, value_range *vr);
+ value_range *pop_value_range (const_tree var);
+
+ /* Cond_stack holds the old VR. */
+ auto_vec<std::pair <const_tree, value_range*> > stack;
+ bitmap need_eh_cleanup;
+ vec<gimple *> stmts_to_fixup;
+};
+
+/* See if there is any new scope is entered with new VR and set that VR to
+ ssa_name before visiting the statements in the scope. */
+
+edge
+evrp_dom_walker::before_dom_children (basic_block bb)
+{
+ value_range *new_vr = NULL;
+ tree op0 = NULL_TREE;
+
+ push_value_range (NULL_TREE, NULL);
+ if (single_pred_p (bb))
+ {
+ edge e = single_pred_edge (bb);
+ value_range vr = VR_INITIALIZER;
+ gimple *stmt = last_stmt (e->src);
+ if (stmt
+ && gimple_code (stmt) == GIMPLE_COND
+ && (op0 = gimple_cond_lhs (stmt))
+ && TREE_CODE (op0) == SSA_NAME
+ && INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt))))
+ {
+ /* Entering a new scope. Try to see if we can find a VR
+ here. */
+ tree op1 = gimple_cond_rhs (stmt);
+ tree_code code = gimple_cond_code (stmt);
+ value_range *old_vr = get_value_range (op0);
+
+ if (TREE_OVERFLOW_P (op1))
+ op1 = drop_tree_overflow (op1);
+
+ /* If condition is false, invert the cond. */
+ if (e->flags & EDGE_FALSE_VALUE)
+ code = invert_tree_comparison (gimple_cond_code (stmt),
+ HONOR_NANS (op0));
+ /* Discover VR when condition is true. */
+ extract_range_for_var_from_comparison_expr (op0, code, op0, op1, &vr);
+ if (old_vr->type == VR_RANGE || old_vr->type == VR_ANTI_RANGE)
+ vrp_intersect_ranges (&vr, old_vr);
+
+ /* If we found any usable VR, set the VR to ssa_name and create a
+ PUSH old value in the stack with the old VR. */
+ if (vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE)
+ {
+ new_vr = vrp_value_range_pool.allocate ();
+ *new_vr = vr;
+ push_value_range (op0, new_vr);
+ }
+ }
+ }
+
+ /* Visit PHI stmts and discover any new VRs possible. */
+ gimple_stmt_iterator gsi;
+ edge e;
+ edge_iterator ei;
+ bool has_unvisived_preds = false;
+
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ if (!(e->src->flags & BB_VISITED))
+ {
+ has_unvisived_preds = true;
+ break;
+ }
+
+ for (gphi_iterator gpi = gsi_start_phis (bb);
+ !gsi_end_p (gpi); gsi_next (&gpi))
+ {
+ gphi *phi = gpi.phi ();
+ tree lhs = PHI_RESULT (phi);
+ value_range vr_result = VR_INITIALIZER;
+ if (!has_unvisived_preds
+ && stmt_interesting_for_vrp (phi))
+ extract_range_from_phi_node (phi, &vr_result);
+ else
+ set_value_range_to_varying (&vr_result);
+ update_value_range (lhs, &vr_result);
+ }
+
+ /* Visit all other stmts and discover any new VRs possible. */
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ gimple *stmt = gsi_stmt (gsi);
+ edge taken_edge;
+ tree output = NULL_TREE;
+ gimple *old_stmt = stmt;
+ bool was_noreturn = (is_gimple_call (stmt)
+ && gimple_call_noreturn_p (stmt));
+
+ /* TODO, if found taken_edge, we should visit (return it) and travel
+ again to improve VR as done in DOM/SCCVN optimizations. It should
+ be done carefully as stmts might prematurely leave a BB like
+ in EH. */
+ if (stmt_interesting_for_vrp (stmt))
+ {
+ value_range vr = VR_INITIALIZER;
+ extract_range_from_stmt (stmt, &taken_edge, &output, &vr);
+ if (output
+ && (vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE))
+ update_value_range (output, &vr);
+ else
+ {
+ tree def;
+ ssa_op_iter iter;
+ FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
+ set_value_range_to_varying (get_value_range (def));
+ }
+
+ /* Try folding stmts with the VR discovered. */
+ bool did_replace
+ = replace_uses_in (stmt,
+ op_with_constant_singleton_value_range);
+ if (fold_stmt (&gsi, follow_single_use_edges)
+ || did_replace)
+ update_stmt (gsi_stmt (gsi));
+
+ if (did_replace)
+ {
+ /* If we cleaned up EH information from the statement,
+ remove EH edges. */
+ if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
+ bitmap_set_bit (need_eh_cleanup, bb->index);
+
+ /* If we turned a not noreturn call into a noreturn one
+ schedule it for fixup. */
+ if (!was_noreturn
+ && is_gimple_call (stmt)
+ && gimple_call_noreturn_p (stmt))
+ stmts_to_fixup.safe_push (stmt);
+
+ if (gimple_assign_single_p (stmt))
+ {
+ tree rhs = gimple_assign_rhs1 (stmt);
+ if (TREE_CODE (rhs) == ADDR_EXPR)
+ recompute_tree_invariant_for_addr_expr (rhs);
+ }
+ }
+
+ def_operand_p def_p = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF);
+ /* Set the SSA with the value range. */
+ if (def_p
+ && TREE_CODE (DEF_FROM_PTR (def_p)) == SSA_NAME
+ && INTEGRAL_TYPE_P (TREE_TYPE (DEF_FROM_PTR (def_p))))
+ {
+ tree def = DEF_FROM_PTR (def_p);
+ value_range *vr = get_value_range (def);
+
+ if ((vr->type == VR_RANGE
+ || vr->type == VR_ANTI_RANGE)
+ && (TREE_CODE (vr->min) == INTEGER_CST)
+ && (TREE_CODE (vr->max) == INTEGER_CST))
+ set_range_info (def, vr->type, vr->min, vr->max);
+ }
+ }
+ else
+ {
+ tree def;
+ ssa_op_iter iter;
+ FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
+ set_value_range_to_varying (get_value_range (def));
+ }
+ }
+ bb->flags |= BB_VISITED;
+ return NULL;
+}
+
+/* Restore/pop VRs valid only for BB when we leave BB. */
+
+void
+evrp_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
+{
+ gcc_checking_assert (!stack.is_empty ());
+ while (stack.last ().first != NULL_TREE)
+ pop_value_range (stack.last ().first);
+ pop_value_range (stack.last ().first);
+}
+
+/* Push the Value Range of VAR to the stack and update it with new VR. */
+
+void
+evrp_dom_walker::push_value_range (const_tree var, value_range *vr)
+{
+ if (vr != NULL)
+ {
+ unsigned ver = SSA_NAME_VERSION (var);
+ gcc_checking_assert (vr_value);
+ stack.safe_push (std::make_pair (var, vr_value[ver]));
+
+ if (ver < num_vr_values)
+ vr_value[ver] = vr;
+ }
+ else
+ stack.safe_push (std::make_pair (var, vr));
+}
+
+/* Pop the Value Range from the vrp_stack and update VAR with it. */
+
+value_range *
+evrp_dom_walker::pop_value_range (const_tree var)
+{
+ value_range *vr = stack.last ().second;
+ if (vr != NULL)
+ {
+ unsigned ver = SSA_NAME_VERSION (var);
+ gcc_checking_assert (var == stack.last ().first);
+ gcc_checking_assert (vr_value);
+
+ if (ver < num_vr_values)
+ vr_value[ver] = vr;
+ }
+ stack.pop ();
+ return vr;
+}
+
+
+/* Main entry point for the early vrp pass which is a simplified non-iterative
+ version of vrp where basic blocks are visited in dominance order. Value
+ ranges discovered in early vrp will also be used by ipa-vrp. */
+
+static unsigned int
+execute_early_vrp ()
+{
+ edge e;
+ edge_iterator ei;
+ basic_block bb;
+
+ loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
+ rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
+ scev_initialize ();
+ calculate_dominance_info (CDI_DOMINATORS);
+ FOR_EACH_BB_FN (bb, cfun)
+ {
+ bb->flags &= ~BB_VISITED;
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ e->flags |= EDGE_EXECUTABLE;
+ }
+ vrp_initialize_lattice ();
+
+ /* Walk stmts in dominance order and propagate VRP. */
+ evrp_dom_walker walker;
+ walker.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun));
+
+ if (!bitmap_empty_p (walker.need_eh_cleanup))
+ gimple_purge_all_dead_eh_edges (walker.need_eh_cleanup);
+
+ /* Fixup stmts that became noreturn calls. This may require splitting
+ blocks and thus isn't possible during the dominator walk. Do this
+ in reverse order so we don't inadvertedly remove a stmt we want to
+ fixup by visiting a dominating now noreturn call first. */
+ while (!walker.stmts_to_fixup.is_empty ())
+ {
+ gimple *stmt = walker.stmts_to_fixup.pop ();
+ fixup_noreturn_call (stmt);
+ }
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "\nValue ranges after Early VRP:\n\n");
+ dump_all_value_ranges (dump_file);
+ fprintf (dump_file, "\n");
+ }
+ vrp_free_lattice ();
+ scev_finalize ();
+ loop_optimizer_finalize ();
+ FOR_EACH_BB_FN (bb, cfun)
+ bb->flags &= ~BB_VISITED;
+ return 0;
}
@@ -10627,9 +10945,11 @@ execute_vrp (bool warn_array_bounds_p)
/* For visiting PHI nodes we need EDGE_DFS_BACK computed. */
mark_dfs_back_edges ();
+ vrp_initialize_lattice ();
vrp_initialize ();
ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node);
vrp_finalize (warn_array_bounds_p);
+ vrp_free_lattice ();
free_numbers_of_iterations_estimates (cfun);
@@ -10727,3 +11047,44 @@ make_pass_vrp (gcc::context *ctxt)
{
return new pass_vrp (ctxt);
}
+
+namespace {
+
+const pass_data pass_data_early_vrp =
+{
+ GIMPLE_PASS, /* type */
+ "evrp", /* name */
+ OPTGROUP_NONE, /* optinfo_flags */
+ TV_TREE_EARLY_VRP, /* tv_id */
+ PROP_ssa, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ ( TODO_cleanup_cfg | TODO_update_ssa | TODO_verify_all ),
+};
+
+class pass_early_vrp : public gimple_opt_pass
+{
+public:
+ pass_early_vrp (gcc::context *ctxt)
+ : gimple_opt_pass (pass_data_early_vrp, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ opt_pass * clone () { return new pass_early_vrp (m_ctxt); }
+ virtual bool gate (function *)
+ {
+ return flag_tree_vrp != 0;
+ }
+ virtual unsigned int execute (function *)
+ { return execute_early_vrp (); }
+
+}; // class pass_vrp
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_early_vrp (gcc::context *ctxt)
+{
+ return new pass_early_vrp (ctxt);
+}
+
--
2.7.4
[-- Attachment #3: log1.txt --]
[-- Type: text/plain, Size: 1841 bytes --]
gcc/ChangeLog:
2016-09-20 Kugan Vivekanandarajah <kuganv@linaro.org>
* doc/invoke.texi: Document -fdump-tree-evrp.
* passes.def: Define new pass_early_vrp.
* timevar.def: Define new TV_TREE_EARLY_VRP.
* tree-pass.h (make_pass_early_vrp): New.
* tree-ssa-propagate.c: Make replace_uses_in non static.
* tree-ssa-propagate.h: Export replace_uses_in.
* tree-vrp.c (extract_range_for_var_from_comparison_expr): New.
(extract_range_from_assert): Factor out
extract_range_for_var_from_comparison_expr.
(vrp_initialize_lattice): New.
(vrp_initialize): Factor out vrp_initialize_lattice.
(vrp_valueize): Fix it to reject complex value ranges.
(vrp_free_lattice): New.
(evrp_dom_walker::before_dom_children): Likewise.
(evrp_dom_walker::after_dom_children): Likewise.
(evrp_dom_walker::push_value_range): Likewise.
(evrp_dom_walker::pop_value_range): Likewise.
(execute_early_vrp): Likewise.
(execute_vrp): Call vrp_initialize_lattice and
vrp_free_lattice.
(make_pass_early_vrp): New.
gcc/testsuite/ChangeLog:
2016-09-20 Kugan Vivekanandarajah <kuganv@linaro.org>
* g++.dg/tree-ssa/pr31146-2.C: Run with -fno-tree-evrp as evrp also
does the same transformation.
* g++.dg/warn/pr33738.C: XFAIL as optimization now happens in ccp.
* gcc.dg/tree-ssa/evrp1.c: New test.
* gcc.dg/tree-ssa/evrp2.c: New test.
* gcc.dg/tree-ssa/evrp3.c: New test.
* gcc.dg/tree-ssa/pr20657.c: Check for the pattern in evrp dump.
* gcc.dg/tree-ssa/pr22117.c: Likewise.
* gcc.dg/tree-ssa/pr61839_2.c: Likewise.
* gcc.dg/tree-ssa/pr64130.c: Likewise.
* gcc.dg/tree-ssa/pr37508.c: Change the pattern to be checked as foldong
now happens early.
* gcc.dg/tree-ssa/vrp04.c: Likewise.
* gcc.dg/tree-ssa/vrp06.c: Likewise.
* gcc.dg/tree-ssa/vrp16.c: Likewise.
* gcc.dg/tree-ssa/vrp25.c: Likewise.
* gcc.dg/tree-ssa/vrp67.c: Likewise.
next prev parent reply other threads:[~2016-09-20 2:05 UTC|newest]
Thread overview: 67+ messages / expand[flat|nested] mbox.gz Atom feed top
2016-07-15 4:41 [RFC][IPA-VRP] IPA " kugan
2016-07-15 4:42 ` [RFC][IPA-VRP] Disable setting param of __builtin_constant_p to null kugan
2016-07-15 8:43 ` Jan Hubicka
2016-07-25 6:59 ` kugan
2016-07-25 10:02 ` Richard Biener
2016-07-15 4:43 ` [RFC][IPA-VRP] Check for POINTER_TYPE_P before accessing SSA_NAME_PTR_INFO in tree-inline kugan
2016-07-15 4:47 ` Andrew Pinski
2016-07-15 7:03 ` kugan
2016-07-15 7:03 ` Jakub Jelinek
2016-07-15 7:32 ` Richard Biener
2016-07-15 4:44 ` [RFC][IPA-VRP] Re-factor tree-vrp to factor out common code kugan
2016-07-15 4:47 ` [RFC][IPA-VRP] Add support for IPA VRP in ipa-cp/ipa-prop kugan
2016-07-15 12:23 ` Martin Jambor
2016-07-19 8:22 ` kugan
2016-07-19 21:27 ` kugan
2016-07-21 12:54 ` Jan Hubicka
2016-08-30 5:21 ` Kugan Vivekanandarajah
2016-08-30 18:12 ` Prathamesh Kulkarni
2016-08-30 21:10 ` kugan
2016-09-02 12:31 ` Jan Hubicka
2016-07-17 13:24 ` Prathamesh Kulkarni
2016-07-22 12:27 ` [RFC][IPA-VRP] Re-factor tree-vrp to factor out common code kugan
2016-07-22 12:49 ` Richard Biener
2016-07-22 14:34 ` kugan
2016-07-23 10:12 ` kugan
2016-08-16 8:09 ` kugan
2016-08-16 11:56 ` Richard Biener
2016-08-16 22:20 ` kugan
2016-08-17 2:50 ` kugan
2016-08-17 13:46 ` Richard Biener
2016-07-15 4:45 ` [RFC][IPA-VRP] Early VRP Implementation kugan
2016-07-15 4:52 ` Andrew Pinski
2016-07-15 7:08 ` kugan
2016-07-15 7:28 ` Andrew Pinski
2016-07-15 7:33 ` kugan
2016-07-18 11:51 ` Richard Biener
2016-07-22 12:10 ` kugan
2016-07-25 11:18 ` Richard Biener
2016-07-26 12:27 ` kugan
2016-07-26 13:37 ` Richard Biener
2016-07-28 7:36 ` kugan
2016-07-28 11:34 ` Richard Biener
2016-08-03 1:17 ` kugan
2016-08-12 10:43 ` Richard Biener
2016-08-16 7:39 ` [RFC][IPA-VRP] splits out the update_value_range calls from vrp_visit_stmt kugan
2016-08-16 10:58 ` Richard Biener
2016-08-17 2:27 ` kugan
2016-08-17 13:44 ` Richard Biener
2016-08-16 7:45 ` [RFC][IPA-VRP] Early VRP Implementation kugan
2016-08-19 11:41 ` Richard Biener
2016-08-23 2:12 ` Kugan Vivekanandarajah
2016-09-02 8:11 ` Kugan Vivekanandarajah
2016-09-14 12:11 ` Richard Biener
2016-09-14 21:47 ` Jan Hubicka
2016-09-15 7:23 ` Richard Biener
2016-09-15 14:57 ` Jeff Law
2016-09-16 8:59 ` Richard Biener
2016-09-16 6:37 ` kugan
2016-09-16 10:26 ` Richard Biener
2016-09-18 23:40 ` kugan
2016-09-19 13:30 ` Richard Biener
2016-09-20 5:48 ` kugan [this message]
2016-07-19 16:19 ` Jeff Law
2016-07-19 18:35 ` Richard Biener
2016-07-19 20:14 ` Jeff Law
2016-07-15 4:47 ` [RFC][IPA-VRP] Teach tree-vrp to use the VR set in params kugan
2016-07-18 11:33 ` Richard Biener
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=2fc6782e-fbb8-c955-c3a7-f2e9b8845134@linaro.org \
--to=kugan.vivekanandarajah@linaro.org \
--cc=gcc-patches@gcc.gnu.org \
--cc=hubicka@ucw.cz \
--cc=mjambor@suse.cz \
--cc=pinskia@gmail.com \
--cc=richard.guenther@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).