From: Richard Biener <richard.guenther@gmail.com>
To: kugan <kugan.vivekanandarajah@linaro.org>
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: Fri, 12 Aug 2016 10:43:00 -0000 [thread overview]
Message-ID: <CAFiYyc2pd6CQrE1NWZ7YAp1F_+nvn9tHwa1BYYa0jZm=cbxJnw@mail.gmail.com> (raw)
In-Reply-To: <48e42d0c-057c-312a-4e41-cd78c8b38b5e@linaro.org>
On Wed, Aug 3, 2016 at 3:17 AM, kugan <kugan.vivekanandarajah@linaro.org> wrote:
> 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.vivekanandarajah@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.
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.
+
no please, this is automatically supported via -fdisable-
@@ -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);
why do you need these changes? I think I already told you you need to
initialize the lattice to sth else than VR_UNDEFINED and that you can't
fully re-use update_value_range. If you don't want to do that then instead
of doing changes all over the place do it in get_value_range and have a
global flag.
@@ -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;
remove these kind of no-op changes.
+/* 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;
+
split the function instead.
@@ -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);
+}
as said the refactoring that would be appreciated is to split out the
update_value_range calls
from the worker functions so you can call the respective functions
from the DOM implementations.
That they are globbed in vrp_visit_stmt currently is due to the API of
the SSA propagator.
@@ -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;
+ }
+
eh... ok, so another way to attack this is, instead of initializing
the lattice to sth else
than VR_UNDEFINED, make sure to drop the lattice to varying for all PHI args on
yet unvisited incoming edges (you're not doing optimistic VRP). That's the only
place you _have_ to do it.
Richard.
> Thanks,
> Kugan
>
>
next prev parent reply other threads:[~2016-08-12 10:43 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 [this message]
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
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='CAFiYyc2pd6CQrE1NWZ7YAp1F_+nvn9tHwa1BYYa0jZm=cbxJnw@mail.gmail.com' \
--to=richard.guenther@gmail.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=hubicka@ucw.cz \
--cc=kugan.vivekanandarajah@linaro.org \
--cc=mjambor@suse.cz \
--cc=pinskia@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).