[RFC][IPA-VRP] Early VRP Implementation

[kugan]

Hi,



This patch adds a very simple early vrp implementation. This visits the 
basic blocks in the dominance order and set the Value Ranges (VR) for


SSA_NAMEs in the scope. Use this VR to discover more VRs. Restore the 
old VR once the scope is exit.




Thanks,

Kugan





gcc/ChangeLog:



2016-07-14  Kugan Vivekanandarajah  



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

* common.opt: New option -ftree-evrp.

* doc/invoke.texi: Document -ftree-evrp.

* passes.def: Define new pass_early_vrp.

* timevar.def: Define new TV_TREE_EARLY_VRP.

* tree-early-vrp.c: New file.

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



gcc/testsuite/ChangeLog:



2016-07-14  Kugan Vivekanandarajah  



* gcc.dg/tree-ssa/evrp1.c: New test.

* gcc.dg/tree-ssa/evrp2.c: New test.

* gcc.dg/tree-ssa/evrp3.c: New test.

* g++.dg/tree-ssa/pr31146-2.C: Run with -fno-tree-evrp as evrp also

does the same transformation.

* gcc.dg/tree-ssa/pr20318.c: Check for the pattern in evrp dump.

* gcc.dg/tree-ssa/pr22117.c: Likewise.

* gcc.dg/tree-ssa/pr25382.c: Likewise.

* gcc.dg/tree-ssa/pr68431.c: LIkewise.

* gcc.dg/tree-ssa/vrp19.c: Likewise.

* gcc.dg/tree-ssa/vrp23.c: Likewise.

* gcc.dg/tree-ssa/vrp24.c: Likewise.

* gcc.dg/tree-ssa/vrp58.c: Likewise.

* gcc.dg/tree-ssa/vrp67.c: Likewise.

* gcc.dg/tree-ssa/vrp98.c: Likewise.





>From d73d443762e1741b810143b2333801cf952c8f17 Mon Sep 17 00:00:00 2001
From: Kugan Vivekanandarajah 
Date: Fri, 24 Jun 2016 14:45:24 +1000
Subject: [PATCH 4/6] Add early vrp

---
 gcc/Makefile.in   |   1 +
 gcc/common.opt|   4 +
 gcc/doc/invoke.texi   |   9 +
 gcc/passes.def|   1 +
 gcc/testsuite/g++.dg/tree-ssa/pr31146-2.C |   2 +-
 gcc/testsuite/gcc.dg/tree-ssa/evrp1.c |  13 ++
 gcc/testsuite/gcc.dg/tree-ssa/evrp2.c |  18 ++
 gcc/testsuite/gcc.dg/tree-ssa/evrp3.c |  15 ++
 gcc/testsuite/gcc.dg/tree-ssa/pr20318.c   |   4 +-
 gcc/testsuite/gcc.dg/tree-ssa/pr22117.c   |   4 +-
 gcc/testsuite/gcc.dg/tree-ssa/pr25382.c   |   4 +-
 gcc/testsuite/gcc.dg/tree-ssa/pr68431.c   |   4 +-
 gcc/testsuite/gcc.dg/tree-ssa/vrp19.c |   6 +-
 gcc/testsuite/gcc.dg/tree-ssa/vrp23.c |   4 +-
 gcc/testsuite/gcc.dg/tree-ssa/vrp24.c |   5 +-
 gcc/testsuite/gcc.dg/tree-ssa/vrp58.c |   4 +-
 gcc/testsuite/gcc.dg/tree-ssa/vrp67.c |   4 +-
 gcc/testsuite/gcc.dg/tree-ssa/vrp98.c |   6 +-
 gcc/timevar.def   |   1 +
 gcc/tree-early-vrp.c  | 324 ++
 gcc/tree-pass.h   |   1 +
 21 files changed, 411 insertions(+), 23 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/evrp1.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/evrp2.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/evrp3.c
 create mode 100644 gcc/tree-early-vrp.c

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 776f6d7..1804632 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1528,6 +1528,7 @@ OBJS = \
 	tree-vect-loop-manip.o \
 	tree-vect-slp.o \
 	tree-vectorizer.o \
+	tree-early-vrp.o \
 	tree-vrp.o \
 	tree.o \
 	valtrack.o \
diff --git a/gcc/common.opt b/gcc/common.opt
index f0d7196..29d0e4d 100644
--- a/gcc/common.opt
+++ b/gcc/common.opt
@@ -2471,6 +2471,10 @@ ftree-vrp
 Common Report Var(flag_tree_vrp) Init(0) Optimization
 Perform Value Range Propagation on trees.
 
+ftree-evrp
+Common Report Var(flag_tree_early_vrp) Init(1) Optimization
+Perform Early Value Range Propagation on trees.
+
 fsplit-paths
 Common Report Var(flag_split_paths) Init(0) Optimization
 Split paths leading to loop backedges.
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index e000218..f4dc88d 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -7665,6 +7665,10 @@ enabled by default at @option{-O2} and higher.  Null pointer check
 elimination is only done if @option{-fdelete-null-pointer-checks} is
 enabled.
 
+@item -ftree-evrp
+@opindex ftree-evrp
+Perform Early Value Range Propagation on trees.
+
 @item -fsplit-paths
 @opindex fsplit-paths
 Split paths leading to loop backedges.  This can improve dead code
@@ -12270,6 +12274,11 @@ is made by appending @file{.slp} to the source file name.
 Dump each function after Value Range Propagation (VRP).  The file name
 is made by appending @file{.vrp} to the source file name.
 
+@item early vrp
+@opindex fdump-tree-evrp
+Dump each function after Early Value Range Propagation (EVRP).  The file name
+is made by appending @file{.evrp} to the source file name.
+
 @item oaccdevlow
 @opindex fdump-tree-oaccdevlow
 Dump each function after applying device-specific OpenACC transformations.
diff --git a/gcc/passes.def b/gcc/passes.def
index 3647e90..1e59d45 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -102,6 +102

Re: [RFC][IPA-VRP] Early VRP Implementation

[kugan]

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?


+/* 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?


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?

Thanks,
Kugan


Btw, you don't want to call vrp_initialize in evrp either, this is setting
SSA propagator state which you do not want to do.  Please factor
out lattice allocation/deallocation instead.  I see that might require
really factoring vrp_visit_stmt into a function that omits updating
the lattice and just returns a range for the single DEF.

That said, a good refactoring is to split the SSA propagator callback
implementations (vrp_visit_stmt and vrp_visit_phi_node) into workers
returning a value range and the callback that does the update_value_range
call plus returing a SSA propgator state.  You can then re-use the worker.

Thanks,
Richard.


I  have tested the last set of patch separately.

I will do more testing on this patch based on your feedback. Does this look
better?

Thanks,
Kugan

Re: [RFC][IPA-VRP] Early VRP Implementation

[Richard Biener]

On Thu, Jul 28, 2016 at 9:35 AM, kugan
 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 ;)

Richard.

> Thanks,
> Kugan
>
>
>> Btw, you don't want to call vrp_initialize in evrp either, this is setting
>> SSA propagator state which you do not want to do.  Please factor
>> out lattice allocation/deallocation instead.  I see that might require
>> really factoring vrp_visit_stmt into a function that omits updating
>> the lattice and just returns a range for the single DEF.
>>
>> That said, a good refactoring is to split the SSA propagator callback
>> implementations (vrp_visit_stmt and vrp_visit_phi_node) into workers
>> returning a value range and the callback that does the update_value_range
>> call plus returing a SSA propgator state.  You can then re-use the worker.
>>
>> T

Re: [RFC][IPA-VRP] Early VRP Implementation

[kugan]

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
 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 
Date: Fri, 29 Jul 2016 2

Re: [RFC][IPA-VRP] Early VRP Implementation

[Richard Biener]

On Wed, Aug 3, 2016 at 3:17 AM, kugan  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
>>  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 

Re: [RFC][IPA-VRP] Early VRP Implementation

[kugan]

Hi Richard,

On 12/08/16 20:43, Richard Biener wrote:

On Wed, Aug 3, 2016 at 3:17 AM, kugan  wrote:


[SNIP]



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-


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?




@@ -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.


I have now added a global early_vrp_p and use this to initialize 
VR_INITIALIZER and get_value_range default to VR_VARYING.





@@ -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.


Done.



+/* 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  (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.

Sent this as separate patch for easy reviewing and testing.



@@ -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.


Even when it is initialize (as I am doing now), we can still end up with 
VR_UNDEFINED durin

Re: [RFC][IPA-VRP] Early VRP Implementation

[Richard Biener]

On Tue, Aug 16, 2016 at 9:45 AM, kugan
 wrote:
> Hi Richard,
>
> On 12/08/16 20:43, Richard Biener wrote:
>>
>> On Wed, Aug 3, 2016 at 3:17 AM, kugan 
>> wrote:
>
>
> [SNIP]
>
>>
>> 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-
>
>
> 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.

>>
>> @@ -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.
>
>
> I have now added a global early_vrp_p and use this to initialize
> VR_INITIALIZER and get_value_range default to VR_VARYING.

ICK.  Ok, I see that this works, but it is quite ugly, so (see below)

>>
>>
>> @@ -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.
>
>
> Done.
>
>
>>
>> +/* 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  (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.
>
> Sent this as separate patch for easy reviewing and testing.

Thank

Re: [RFC][IPA-VRP] Early VRP Implementation

[Kugan Vivekanandarajah]

Hi,

On 19 August 2016 at 21:41, Richard Biener  wrote:
> On Tue, Aug 16, 2016 at 9:45 AM, kugan
>  wrote:
>> Hi Richard,
>>
>> On 12/08/16 20:43, Richard Biener wrote:
>>>
>>> On Wed, Aug 3, 2016 at 3:17 AM, kugan 
>>> wrote:
>>
>>
>> [SNIP]
>>
>>>
>>> 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-
>>
>>
>> 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.

>>>
>>> @@ -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.
>>
>>
>> I have now added a global early_vrp_p and use this to initialize
>> VR_INITIALIZER and get_value_range default to VR_VARYING.
>
> ICK.  Ok, I see that this works, but it is quite ugly, so (see below)
>
>>>
>>>
>>> @@ -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.
>>
>>
>> Done.
>>
>>
>>>
>>> +/* 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  (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 ou

Re: [RFC][IPA-VRP] Early VRP Implementation

[Kugan Vivekanandarajah]

Ping ?

Thanks,
Kugan

On 23 August 2016 at 12:11, Kugan Vivekanandarajah
 wrote:
> Hi,
>
> On 19 August 2016 at 21:41, Richard Biener  wrote:
>> On Tue, Aug 16, 2016 at 9:45 AM, kugan
>>  wrote:
>>> Hi Richard,
>>>
>>> On 12/08/16 20:43, Richard Biener wrote:

 On Wed, Aug 3, 2016 at 3:17 AM, kugan 
 wrote:
>>>
>>>
>>> [SNIP]
>>>

 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-
>>>
>>>
>>> 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.
>

 @@ -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.
>>>
>>>
>>> I have now added a global early_vrp_p and use this to initialize
>>> VR_INITIALIZER and get_value_range default to VR_VARYING.
>>
>> ICK.  Ok, I see that this works, but it is quite ugly, so (see below)
>>


 @@ -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.
>>>
>>>
>>> Done.
>>>
>>>

 +/* 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  (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
>

Re: [RFC][IPA-VRP] Early VRP Implementation

[Richard Biener]

On Tue, Aug 23, 2016 at 4:11 AM, Kugan Vivekanandarajah
 wrote:
> Hi,
>
> On 19 August 2016 at 21:41, Richard Biener  wrote:
>> On Tue, Aug 16, 2016 at 9:45 AM, kugan
>>  wrote:
>>> Hi Richard,
>>>
>>> On 12/08/16 20:43, Richard Biener wrote:

 On Wed, Aug 3, 2016 at 3:17 AM, kugan 
 wrote:
>>>
>>>
>>> [SNIP]
>>>

 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-
>>>
>>>
>>> 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.


 @@ -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.
>>>
>>>
>>> I have now added a global early_vrp_p and use this to initialize
>>> VR_INITIALIZER and get_value_range default to VR_VARYING.
>>
>> ICK.  Ok, I see that this works, but it is quite ugly, so (see below)
>>


 @@ -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.
>>>
>>>
>>> Done.
>>>
>>>

 +/* 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  (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;
  }

Re: [RFC][IPA-VRP] Early VRP Implementation

[Jan Hubicka]

> +  /* 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))
> +   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.
How IRA bugs affects early passes?

Honza

Re: [RFC][IPA-VRP] Early VRP Implementation

[Richard Biener]

On September 14, 2016 11:36:16 PM GMT+02:00, Jan Hubicka  wrote:
>> +  /* 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))
>> +   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.
>How IRA bugs affects early passes?

IRA bogously relies on BB_VISITED being cleared at pass start.

Richard.

>Honza

Re: [RFC][IPA-VRP] Early VRP Implementation

[Jeff Law]

On 09/14/2016 11:55 PM, Richard Biener wrote:

On September 14, 2016 11:36:16 PM GMT+02:00, Jan Hubicka  wrote:

+  /* 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))
+   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.

How IRA bugs affects early passes?


IRA bogously relies on BB_VISITED being cleared at pass start.
Seems like IRA ought to be fixed to clear BB_VISITED on every block as 
part of its initialization.


Jeff

Re: [RFC][IPA-VRP] Early VRP Implementation

[kugan]

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
 wrote:

Hi,

On 19 August 2016 at 21:41, Richard Biener  wrote:

On Tue, Aug 16, 2016 at 9:45 AM, kugan
 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.




+  /* 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))
+   extract_range_from_phi_node (phi, &vr_result, true);
+  else
+   set_value_range_to_varying (&vr_result);
+  updat

Re: [RFC][IPA-VRP] Early VRP Implementation

[Richard Biener]

On Thu, Sep 15, 2016 at 4:45 PM, Jeff Law  wrote:
> On 09/14/2016 11:55 PM, Richard Biener wrote:
>>
>> On September 14, 2016 11:36:16 PM GMT+02:00, Jan Hubicka 
>> wrote:

 +  /* 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))
 +   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.
>>>
>>> How IRA bugs affects early passes?
>>
>>
>> IRA bogously relies on BB_VISITED being cleared at pass start.
>
> Seems like IRA ought to be fixed to clear BB_VISITED on every block as part
> of its initialization.

Agreed but I didn't find the time to track down an appropriate place to do that.

Richard.

> Jeff
>

Re: [RFC][IPA-VRP] Early VRP Implementation

[Richard Biener]

On Fri, Sep 16, 2016 at 7:59 AM, kugan
 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
>>  wrote:
>>>
>>> Hi,
>>>
>>> On 19 August 2016 at 21:41, Richard Biener 
>>> wrote:

 On Tue, Aug 16, 2016 at 9:45 AM, kugan
  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 visi

Re: [RFC][IPA-VRP] Early VRP Implementation

[kugan]

Hi Richard,


On 16/09/16 20:21, Richard Biener wrote:

On Fri, Sep 16, 2016 at 7:59 AM, kugan
 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
 wrote:


Hi,

On 19 August 2016 at 21:41, Richard Biener 
wrote:


On Tue, Aug 16, 2016 at 9:45 AM, kugan
 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_

Re: [RFC][IPA-VRP] Early VRP Implementation

[Richard Biener]

On Sun, Sep 18, 2016 at 10:50 PM, kugan
 wrote:
> Hi Richard,
>
>
>
> On 16/09/16 20:21, Richard Biener wrote:
>>
>> On Fri, Sep 16, 2016 at 7:59 AM, kugan
>>  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
  wrote:
>
>
> Hi,
>
> On 19 August 2016 at 21:41, Richard Biener 
> wrote:
>>
>>
>> On Tue, Aug 16, 2016 at 9:45 AM, kugan
>>  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

Re: [RFC][IPA-VRP] Early VRP Implementation

[kugan]

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
 wrote:

Hi Richard,



On 16/09/16 20:21, Richard Biener wrote:


On Fri, Sep 16, 2016 at 7:59 AM, kugan
 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
 wrote:



Hi,

On 19 August 2016 at 21:41, Richard Biener 
wrote:



On Tue, Aug 16, 2016 at 9:45 AM, kugan
 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 

Re: [RFC][IPA-VRP] Early VRP Implementation

[Andrew Pinski]

On Thu, Jul 14, 2016 at 9:45 PM, kugan
 wrote:
>
> Hi,
>
>
>
> This patch adds a very simple early vrp implementation. This visits the
> basic blocks in the dominance order and set the Value Ranges (VR) for
>
> SSA_NAMEs in the scope. Use this VR to discover more VRs. Restore the old VR
> once the scope is exit.


Why separate out early VRP from tree-vrp?  Just a little curious.
Also it seems like if you are going to do that, putting the following
functions in a class would be better:
+extern void vrp_initialize (void);
+extern void vrp_finalize (bool update, bool warn_array_bounds_p);
+extern void vrp_intersect_ranges (value_range *vr0, value_range *vr1);
+extern void vrp_meet (value_range *vr0, value_range *vr1);
+extern enum ssa_prop_result vrp_visit_stmt (gimple *stmt,
+edge *taken_edge_p,
+tree *output_p);
+extern enum ssa_prop_result vrp_visit_phi_node (gphi *phi);
+extern bool stmt_interesting_for_vrp (gimple *stmt);
+
+extern void extract_range_from_assert (value_range *vr_p, tree expr);
+extern bool update_value_range (const_tree var, value_range *vr);
+extern value_range *get_value_range (const_tree var);
+extern void set_value_range (value_range *vr, enum value_range_type t,
+ tree min, tree max, bitmap equiv);
+extern void change_value_range (const_tree var, value_range *new_vr);
+
+extern void dump_value_range (FILE *, value_range *);

That is vrp_initialize becomes the constructor and vrp_finalize
becomes the deconstructor.
With both jump_thread and warn_array_bounds_p being variables you set
while running your pass.

Thanks,
Andrew

>
>
>
> Thanks,
>
> Kugan
>
>
>
>
>
> gcc/ChangeLog:
>
>
>
> 2016-07-14  Kugan Vivekanandarajah  
>
>
>
> * Makefile.in: Add tree-early-vrp.o.
>
> * common.opt: New option -ftree-evrp.
>
> * doc/invoke.texi: Document -ftree-evrp.
>
> * passes.def: Define new pass_early_vrp.
>
> * timevar.def: Define new TV_TREE_EARLY_VRP.
>
> * tree-early-vrp.c: New file.
>
> * tree-pass.h (make_pass_early_vrp): New.
>
>
>
> gcc/testsuite/ChangeLog:
>
>
>
> 2016-07-14  Kugan Vivekanandarajah  
>
>
>
> * gcc.dg/tree-ssa/evrp1.c: New test.
>
> * gcc.dg/tree-ssa/evrp2.c: New test.
>
> * gcc.dg/tree-ssa/evrp3.c: New test.
>
> * g++.dg/tree-ssa/pr31146-2.C: Run with -fno-tree-evrp as evrp also
>
> does the same transformation.
>
> * gcc.dg/tree-ssa/pr20318.c: Check for the pattern in evrp dump.
>
> * gcc.dg/tree-ssa/pr22117.c: Likewise.
>
> * gcc.dg/tree-ssa/pr25382.c: Likewise.
>
> * gcc.dg/tree-ssa/pr68431.c: LIkewise.
>
> * gcc.dg/tree-ssa/vrp19.c: Likewise.
>
> * gcc.dg/tree-ssa/vrp23.c: Likewise.
>
> * gcc.dg/tree-ssa/vrp24.c: Likewise.
>
> * gcc.dg/tree-ssa/vrp58.c: Likewise.
>
> * gcc.dg/tree-ssa/vrp67.c: Likewise.
>
> * gcc.dg/tree-ssa/vrp98.c: Likewise.
>
>
>
>
>

Re: [RFC][IPA-VRP] Early VRP Implementation

[kugan]

Hi Andrew,


Why separate out early VRP from tree-vrp?  Just a little curious.


It is based on the discussion in 
https://gcc.gnu.org/ml/gcc/2016-01/msg00069.html.
In summary, conclusion (based on my understanding) was to implement a 
simplified VRP algorithm that doesn't require ASSERT_EXPR insertion.




Also it seems like if you are going to do that, putting the following
functions in a class would be better:
+extern void vrp_initialize (void);
+extern void vrp_finalize (bool update, bool warn_array_bounds_p);
+extern void vrp_intersect_ranges (value_range *vr0, value_range *vr1);
+extern void vrp_meet (value_range *vr0, value_range *vr1);
+extern enum ssa_prop_result vrp_visit_stmt (gimple *stmt,
+edge *taken_edge_p,
+tree *output_p);
+extern enum ssa_prop_result vrp_visit_phi_node (gphi *phi);
+extern bool stmt_interesting_for_vrp (gimple *stmt);
+
+extern void extract_range_from_assert (value_range *vr_p, tree expr);
+extern bool update_value_range (const_tree var, value_range *vr);
+extern value_range *get_value_range (const_tree var);
+extern void set_value_range (value_range *vr, enum value_range_type t,
+ tree min, tree max, bitmap equiv);
+extern void change_value_range (const_tree var, value_range *new_vr);
+
+extern void dump_value_range (FILE *, value_range *);

That is vrp_initialize becomes the constructor and vrp_finalize
becomes the deconstructor.
With both jump_thread and warn_array_bounds_p being variables you set
while running your pass.


I will give this a try.

Thanks,
Kugan

Re: [RFC][IPA-VRP] Early VRP Implementation

[Andrew Pinski]

On Fri, Jul 15, 2016 at 12:08 AM, kugan
 wrote:
> Hi Andrew,
>
>> Why separate out early VRP from tree-vrp?  Just a little curious.
>
>
> It is based on the discussion in
> https://gcc.gnu.org/ml/gcc/2016-01/msg00069.html.
> In summary, conclusion (based on my understanding) was to implement a
> simplified VRP algorithm that doesn't require ASSERT_EXPR insertion.

But I don't see why you are moving it from tree-vrp.c .  That was my
question, you pointing to that discussion does not say to split it
into a new file and expose these interfaces.

Thanks,
Andrew Pinski

>
>
>> Also it seems like if you are going to do that, putting the following
>> functions in a class would be better:
>> +extern void vrp_initialize (void);
>> +extern void vrp_finalize (bool update, bool warn_array_bounds_p);
>> +extern void vrp_intersect_ranges (value_range *vr0, value_range *vr1);
>> +extern void vrp_meet (value_range *vr0, value_range *vr1);
>> +extern enum ssa_prop_result vrp_visit_stmt (gimple *stmt,
>> +edge *taken_edge_p,
>> +tree *output_p);
>> +extern enum ssa_prop_result vrp_visit_phi_node (gphi *phi);
>> +extern bool stmt_interesting_for_vrp (gimple *stmt);
>> +
>> +extern void extract_range_from_assert (value_range *vr_p, tree expr);
>> +extern bool update_value_range (const_tree var, value_range *vr);
>> +extern value_range *get_value_range (const_tree var);
>> +extern void set_value_range (value_range *vr, enum value_range_type t,
>> + tree min, tree max, bitmap equiv);
>> +extern void change_value_range (const_tree var, value_range *new_vr);
>> +
>> +extern void dump_value_range (FILE *, value_range *);
>>
>> That is vrp_initialize becomes the constructor and vrp_finalize
>> becomes the deconstructor.
>> With both jump_thread and warn_array_bounds_p being variables you set
>> while running your pass.
>
>
> I will give this a try.
>
> Thanks,
> Kugan

Re: [RFC][IPA-VRP] Early VRP Implementation

[kugan]

Hi Andrew,

On 15/07/16 17:28, Andrew Pinski wrote:

On Fri, Jul 15, 2016 at 12:08 AM, kugan
 wrote:

Hi Andrew,


Why separate out early VRP from tree-vrp?  Just a little curious.



It is based on the discussion in
https://gcc.gnu.org/ml/gcc/2016-01/msg00069.html.
In summary, conclusion (based on my understanding) was to implement a
simplified VRP algorithm that doesn't require ASSERT_EXPR insertion.


But I don't see why you are moving it from tree-vrp.c .  That was my
question, you pointing to that discussion does not say to split it
into a new file and expose these interfaces.



Are you saying that I should keep this part of tree-vrp.c. I am happy to 
do that if this is considered the best approach.


Thanks,
Kugan

Re: [RFC][IPA-VRP] Early VRP Implementation

[Richard Biener]

On Fri, Jul 15, 2016 at 9:33 AM, kugan
 wrote:
> Hi Andrew,
>
> On 15/07/16 17:28, Andrew Pinski wrote:
>>
>> On Fri, Jul 15, 2016 at 12:08 AM, kugan
>>  wrote:
>>>
>>> Hi Andrew,
>>>
 Why separate out early VRP from tree-vrp?  Just a little curious.
>>>
>>>
>>>
>>> It is based on the discussion in
>>> https://gcc.gnu.org/ml/gcc/2016-01/msg00069.html.
>>> In summary, conclusion (based on my understanding) was to implement a
>>> simplified VRP algorithm that doesn't require ASSERT_EXPR insertion.
>>
>>
>> But I don't see why you are moving it from tree-vrp.c .  That was my
>> question, you pointing to that discussion does not say to split it
>> into a new file and expose these interfaces.
>>
>
> Are you saying that I should keep this part of tree-vrp.c. I am happy to do
> that if this is considered the best approach.

Yes, I think that's the best approach.

Can you, as a refactoring before your patch, please change VRP to use
an alloc-pool
for allocating value_range?  The DOM-based VRP will add a lot of
malloc/free churn
otherwise.

Generally watch coding-style such as  missed function comments.

As you do a non-iterating VRP and thus do not visit back-edges you don't need
to initialize loops or SCEV nor do you need loop-closed SSA.

As you do a DOM-based VRP using SSA propagator stuff like ssa_prop_result
doesn't make any sense.

+edge evrp_dom_walker::before_dom_children (basic_block bb)
+{
+  /* If we are going out of scope, restore the old VR.  */
+  while (!cond_stack.is_empty ()
+&& !dominated_by_p (CDI_DOMINATORS, bb, cond_stack.last ().first))
+{
+  tree var = cond_stack.last ().second.first;
+  value_range *vr = cond_stack.last ().second.second;
+  value_range *vr_to_del = get_value_range (var);
+  XDELETE (vr_to_del);
+  change_value_range (var, vr);
+  cond_stack.pop ();
+}

that should be in after_dom_children I think and use a marker instead
of a DOM query.
See other examples like DOM itself or SCCVN.

+ /* Discover VR when condition is true.  */
+ if (te == e
+ && !TREE_OVERFLOW_P (op0)
+ && !TREE_OVERFLOW_P (op1))

you can use e->flags & EDGE_TRUE_VALUE/EDGE_FALSE_VALUE

why do you need those TREE_OVERFLOW checks?

+ tree cond = build2 (code, boolean_type_node, op0, op1);
+ tree a = build2 (ASSERT_EXPR, TREE_TYPE (op0), op0, cond);
+ extract_range_from_assert (&vr, a);

so I was hoping that the "refactoring" patch in the series would expose a more
useful interface than extract_range_from_assert ... namely one that can
extract a range from the comparison directly and does not require building
a scratch ASSERT_EXPR.

+ /* If we found any usable VR, set the VR to ssa_name and create a
+restore point in the cond_stack with the  old VR. */
+ if (vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE)
+   {
+ value_range *new_vr = XCNEW (value_range);
+ *new_vr = vr;
+ cond_stack.safe_push (std::make_pair (bb,
+   std::make_pair (op0,
+   old_vr)));
+ change_value_range (op0, new_vr);

I don't like 'change_value_range' as interface, please integrate that into
a push/pop_value_range style interface instead.

+   vrp_visit_stmt (stmt, &taken_edge_p, &output_p);
+}
+
+  return NULL;

you should return taken_edge_p (misnamed as it isn't a pointer) and take
advantage of EDGE_EXECUTABLE.  Again see DOM/SCCVN (might want to
defer this as a followup improvement).

Note that the advantage of a DOM-based VRP is that backtracking is easy
to implement (you don't do that yet).  That is, after DEF got a (better)
value-range you can simply re-visit all the defs of its uses (and recursively).
I think you have to be careful with stmts that might prematurely leave a BB
though (like via EH).  So sth for a followup as well.

Thanks,
Richard.


> Thanks,
> Kugan

Re: [RFC][IPA-VRP] Early VRP Implementation

[Jeff Law]

On 07/14/2016 10:52 PM, Andrew Pinski wrote:

On Thu, Jul 14, 2016 at 9:45 PM, kugan
 wrote:


Hi,



This patch adds a very simple early vrp implementation. This visits the
basic blocks in the dominance order and set the Value Ranges (VR) for

SSA_NAMEs in the scope. Use this VR to discover more VRs. Restore the old VR
once the scope is exit.



Why separate out early VRP from tree-vrp?  Just a little curious.
I wouldn't mind seeing tree-vrp broken down a little -- it's quite large 
and there's at least 4 distinct things going on in that file.


1. ASSERT_EXPR handling.

2. Arithmetic on ranges

3. Propagation engine setup, callbacks, etc

4. Range management

There may be others, but it seems at least some of that ought to be 
factored out.


Jeff

Re: [RFC][IPA-VRP] Early VRP Implementation

[Richard Biener]

On July 19, 2016 6:19:23 PM GMT+02:00, Jeff Law  wrote:
>On 07/14/2016 10:52 PM, Andrew Pinski wrote:
>> On Thu, Jul 14, 2016 at 9:45 PM, kugan
>>  wrote:
>>>
>>> Hi,
>>>
>>>
>>>
>>> This patch adds a very simple early vrp implementation. This visits
>the
>>> basic blocks in the dominance order and set the Value Ranges (VR)
>for
>>>
>>> SSA_NAMEs in the scope. Use this VR to discover more VRs. Restore
>the old VR
>>> once the scope is exit.
>>
>>
>> Why separate out early VRP from tree-vrp?  Just a little curious.
>I wouldn't mind seeing tree-vrp broken down a little -- it's quite
>large 
>and there's at least 4 distinct things going on in that file.
>
>1. ASSERT_EXPR handling.
>
>2. Arithmetic on ranges
>
>3. Propagation engine setup, callbacks, etc
>
>4. Range management
>
>There may be others, but it seems at least some of that ought to be 
>factored out.

Possibly, but not necessarily because of the proposed pass.

I'd like to see lattices and lattice entries becoming classes and the 
arithmetic on it being templated on it.

I do have some preliminary patches implementing a aggressive on-drmand VRP for 
the use in niter analysis and the
Lattice is what makes sharing code difficult (it's a hash-map instead of an 
array there).

Richard.


>
>Jeff

Re: [RFC][IPA-VRP] Early VRP Implementation

[Jeff Law]

On 07/19/2016 12:35 PM, Richard Biener wrote:

I wouldn't mind seeing tree-vrp broken down a little -- it's quite
large and there's at least 4 distinct things going on in that
file.

1. ASSERT_EXPR handling.

2. Arithmetic on ranges

3. Propagation engine setup, callbacks, etc

4. Range management

There may be others, but it seems at least some of that ought to be
 factored out.


Possibly, but not necessarily because of the proposed pass.
Right.  These are things that, in my mind ought to be done regardless of 
the introduction of IPA-VRP.




I'd like to see lattices and lattice entries becoming classes and the
arithmetic on it being templated on it.

Seems reasonable as well.



I do have some preliminary patches implementing a aggressive
on-drmand VRP for the use in niter analysis and the Lattice is what
makes sharing code difficult (it's a hash-map instead of an array
there).
It's interesting you mention an on-demand VRP.  I've asked Andrew to 
poke that that some too.  It's for a different need, but interesting 
that we're both looking to take things in that direction.


Jeff

Re: [RFC][IPA-VRP] Early VRP Implementation

[kugan]

Hi Richard,

Thanks for the review.

On 18/07/16 21:51, Richard Biener wrote:

On Fri, Jul 15, 2016 at 9:33 AM, kugan
 wrote:

Hi Andrew,

On 15/07/16 17:28, Andrew Pinski wrote:


On Fri, Jul 15, 2016 at 12:08 AM, kugan
 wrote:


Hi Andrew,


Why separate out early VRP from tree-vrp?  Just a little curious.




It is based on the discussion in
https://gcc.gnu.org/ml/gcc/2016-01/msg00069.html.
In summary, conclusion (based on my understanding) was to implement a
simplified VRP algorithm that doesn't require ASSERT_EXPR insertion.



But I don't see why you are moving it from tree-vrp.c .  That was my
question, you pointing to that discussion does not say to split it
into a new file and expose these interfaces.



Are you saying that I should keep this part of tree-vrp.c. I am happy to do
that if this is considered the best approach.


Yes, I think that's the best approach.


Thanks. Moved it into tree-vrp.c now.


Can you, as a refactoring before your patch, please change VRP to use
an alloc-pool
for allocating value_range?  The DOM-based VRP will add a lot of
malloc/free churn
otherwise.

Generally watch coding-style such as  missed function comments.

As you do a non-iterating VRP and thus do not visit back-edges you don't need
to initialize loops or SCEV nor do you need loop-closed SSA.

As you do a DOM-based VRP using SSA propagator stuff like ssa_prop_result
doesn't make any sense.


I have removed it.


+edge evrp_dom_walker::before_dom_children (basic_block bb)
+{
+  /* If we are going out of scope, restore the old VR.  */
+  while (!cond_stack.is_empty ()
+&& !dominated_by_p (CDI_DOMINATORS, bb, cond_stack.last ().first))
+{
+  tree var = cond_stack.last ().second.first;
+  value_range *vr = cond_stack.last ().second.second;
+  value_range *vr_to_del = get_value_range (var);
+  XDELETE (vr_to_del);
+  change_value_range (var, vr);
+  cond_stack.pop ();
+}

that should be in after_dom_children I think and use a marker instead
of a DOM query.
See other examples like DOM itself or SCCVN.



Done.

+ /* Discover VR when condition is true.  */
+ if (te == e
+ && !TREE_OVERFLOW_P (op0)
+ && !TREE_OVERFLOW_P (op1))


This is mainly to handle gcc.dg/pr38934.c. This would result in ICE from 
set_value_range otherwise:


gcc_assert ((!TREE_OVERFLOW_P (min) || is_overflow_infinity (min))
  && (!TREE_OVERFLOW_P (max) || is_overflow_infinity 
(max)));




you can use e->flags & EDGE_TRUE_VALUE/EDGE_FALSE_VALUE

why do you need those TREE_OVERFLOW checks?

+ tree cond = build2 (code, boolean_type_node, op0, op1);
+ tree a = build2 (ASSERT_EXPR, TREE_TYPE (op0), op0, cond);
+ extract_range_from_assert (&vr, a);

so I was hoping that the "refactoring" patch in the series would expose a more
useful interface than extract_range_from_assert ... namely one that can
extract a range from the comparison directly and does not require building
a scratch ASSERT_EXPR.


I have split extract_range_from_assert into 
extract_range_for_var_from_comparison_expr and using it now. Is that better?


+ /* If we found any usable VR, set the VR to ssa_name and create a
+restore point in the cond_stack with the  old VR. */
+ if (vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE)
+   {
+ value_range *new_vr = XCNEW (value_range);
+ *new_vr = vr;
+ cond_stack.safe_push (std::make_pair (bb,
+   std::make_pair (op0,
+   old_vr)));
+ change_value_range (op0, new_vr);

I don't like 'change_value_range' as interface, please integrate that into
a push/pop_value_range style interface instead.


Tried using push/pop interface.


+   vrp_visit_stmt (stmt, &taken_edge_p, &output_p);
+}
+
+  return NULL;

you should return taken_edge_p (misnamed as it isn't a pointer) and take
advantage of EDGE_EXECUTABLE.  Again see DOM/SCCVN (might want to
defer this as a followup improvement).


I have added a TODO to this effect and will comeback to it.


Note that the advantage of a DOM-based VRP is that backtracking is easy
to implement (you don't do that yet).  That is, after DEF got a (better)
value-range you can simply re-visit all the defs of its uses (and recursively).
I think you have to be careful with stmts that might prematurely leave a BB
though (like via EH).  So sth for a followup as well.


Is this OK now. Bootstrapped and regression tested on x86_64-linux  with 
no new regressions.


Thanks,
Kugan

gcc/ChangeLog:

2016-07-22  Kugan Vivekanandarajah  

* common.opt: New option -ftree-evrp.
* doc/invoke.texi: Document -ftree-evrp.
* passes.def: Define new pass_early_vrp.
* timevar.def: Define new TV_TREE_EARLY_VRP.
* tree-pass.h (make_pass_early_vrp): New.
* tree-vrp.c (ex

Re: [RFC][IPA-VRP] Early VRP Implementation

[Richard Biener]

On Fri, Jul 22, 2016 at 2:10 PM, kugan
 wrote:
> Hi Richard,
>
> Thanks for the review.
>
> On 18/07/16 21:51, Richard Biener wrote:
>>
>> On Fri, Jul 15, 2016 at 9:33 AM, kugan
>>  wrote:
>>>
>>> Hi Andrew,
>>>
>>> On 15/07/16 17:28, Andrew Pinski wrote:


 On Fri, Jul 15, 2016 at 12:08 AM, kugan
  wrote:
>
>
> Hi Andrew,
>
>> Why separate out early VRP from tree-vrp?  Just a little curious.
>
>
>
>
> It is based on the discussion in
> https://gcc.gnu.org/ml/gcc/2016-01/msg00069.html.
> In summary, conclusion (based on my understanding) was to implement a
> simplified VRP algorithm that doesn't require ASSERT_EXPR insertion.



 But I don't see why you are moving it from tree-vrp.c .  That was my
 question, you pointing to that discussion does not say to split it
 into a new file and expose these interfaces.

>>>
>>> Are you saying that I should keep this part of tree-vrp.c. I am happy to
>>> do
>>> that if this is considered the best approach.
>>
>>
>> Yes, I think that's the best approach.
>>
> Thanks. Moved it into tree-vrp.c now.
>
>> Can you, as a refactoring before your patch, please change VRP to use
>> an alloc-pool
>> for allocating value_range?  The DOM-based VRP will add a lot of
>> malloc/free churn
>> otherwise.
>>
>> Generally watch coding-style such as  missed function comments.
>>
>> As you do a non-iterating VRP and thus do not visit back-edges you don't
>> need
>> to initialize loops or SCEV nor do you need loop-closed SSA.
>>
>> As you do a DOM-based VRP using SSA propagator stuff like ssa_prop_result
>> doesn't make any sense.
>
>
> I have removed it.
>>
>>
>> +edge evrp_dom_walker::before_dom_children (basic_block bb)
>> +{
>> +  /* If we are going out of scope, restore the old VR.  */
>> +  while (!cond_stack.is_empty ()
>> +&& !dominated_by_p (CDI_DOMINATORS, bb, cond_stack.last
>> ().first))
>> +{
>> +  tree var = cond_stack.last ().second.first;
>> +  value_range *vr = cond_stack.last ().second.second;
>> +  value_range *vr_to_del = get_value_range (var);
>> +  XDELETE (vr_to_del);
>> +  change_value_range (var, vr);
>> +  cond_stack.pop ();
>> +}
>>
>> that should be in after_dom_children I think and use a marker instead
>> of a DOM query.
>> See other examples like DOM itself or SCCVN.
>>
>
> Done.

+/* Restore/Pop all the old VRs maintained in the cond_stack.  */
+
+void evrp_dom_walker::finalize_dom_walker ()
+{
+  while (!cond_stack.is_empty ())
+{
+  tree var = cond_stack.last ().second;
+  pop_value_range (var);
+  cond_stack.pop ();
+}

why is this necessary at all?  Looks like a waste of time (and the
stack should be empty here
anyway).  I think you leak cond_stack as well, I suppose using
auto_vec might work here,
you have to check.

>>
>> + /* Discover VR when condition is true.  */
>> + if (te == e
>> + && !TREE_OVERFLOW_P (op0)
>> + && !TREE_OVERFLOW_P (op1))
>
>
> This is mainly to handle gcc.dg/pr38934.c. This would result in ICE from
> set_value_range otherwise:
>
> gcc_assert ((!TREE_OVERFLOW_P (min) || is_overflow_infinity (min))
>   && (!TREE_OVERFLOW_P (max) || is_overflow_infinity
> (max)));

Ok, instead make sure to remove the overflow flag via

  if (TREE_OVERFLOW_P (op0))
op0 = drop_tree_overflow (op0);
...

it looks like you want to merge the if ( & EDGE_TRUE_VALUE) and FALSE_VALUE
cases and only invert the tree comparison for the false edge.

+ tree cond = build2 (code, boolean_type_node, op0, op1);
+ extract_range_for_var_from_comparison_expr (&vr, op0, cond);

no wasteful tree building here please.  Instead of cond pass in code,
op0 and op1
as separate arguments.

+ /* If we found any usable VR, set the VR to ssa_name and create a
+PUSH old value in the cond_stack with the old VR.  */
+ if (vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE)
+   {
+ value_range *new_vr = vrp_value_range_pool.allocate ();
+ memset (new_vr, 0, sizeof (*new_vr));
+ *new_vr = vr;
+ cond_stack.safe_push (std::make_pair (bb, op0));

the memset looks redundant given you copy-assing from vr anyway.

You seem to miss the chance to register ranges for x_2 in i_1 < x_2 where
both i_1 and x_2 might have ranges that are useful.

push and pop_value_range should be methods in the dom walker class
and vrp_stack and cond_stack should be a single stack.  You can omit
basic_block if you use a "magic" NULL_TREE var as marker (simply
push a NULL_TREE, NULL pair at the end of before_dom_children).

>>
>> you can use e->flags & EDGE_TRUE_VALUE/EDGE_FALSE_VALUE
>>
>> why do you need those TREE_OVERFLOW checks?
>>
>> + tree cond = build2 (code, boolean_type_node, op0, op1);
>> + tree a = build2 (ASSERT_EXPR, TREE_TYPE (op0), op0, cond);
>> + ex

Re: [RFC][IPA-VRP] Early VRP Implementation

[kugan]

Hi Riachard,

Thanks for the review. Here is an updated patch with comments below.


+/* Restore/Pop all the old VRs maintained in the cond_stack.  */
+
+void evrp_dom_walker::finalize_dom_walker ()
+{
+  while (!cond_stack.is_empty ())
+{
+  tree var = cond_stack.last ().second;
+  pop_value_range (var);
+  cond_stack.pop ();
+}

why is this necessary at all?  Looks like a waste of time (and the
stack should be empty here
anyway).  I think you leak cond_stack as well, I suppose using
auto_vec might work here,
you have to check.

Done.





+ /* Discover VR when condition is true.  */
+ if (te == e
+ && !TREE_OVERFLOW_P (op0)
+ && !TREE_OVERFLOW_P (op1))



This is mainly to handle gcc.dg/pr38934.c. This would result in ICE from
set_value_range otherwise:

gcc_assert ((!TREE_OVERFLOW_P (min) || is_overflow_infinity (min))
  && (!TREE_OVERFLOW_P (max) || is_overflow_infinity
(max)));


Ok, instead make sure to remove the overflow flag via

  if (TREE_OVERFLOW_P (op0))
op0 = drop_tree_overflow (op0);

 ...
Done.



it looks like you want to merge the if ( & EDGE_TRUE_VALUE) and FALSE_VALUE
cases and only invert the tree comparison for the false edge.

Done.



+ tree cond = build2 (code, boolean_type_node, op0, op1);
+ extract_range_for_var_from_comparison_expr (&vr, op0, cond);

no wasteful tree building here please.  Instead of cond pass in code,
op0 and op1
as separate arguments.

Done.



+ /* If we found any usable VR, set the VR to ssa_name and create a
+PUSH old value in the cond_stack with the old VR.  */
+ if (vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE)
+   {
+ value_range *new_vr = vrp_value_range_pool.allocate ();
+ memset (new_vr, 0, sizeof (*new_vr));
+ *new_vr = vr;
+ cond_stack.safe_push (std::make_pair (bb, op0));

the memset looks redundant given you copy-assing from vr anyway.

Done.



You seem to miss the chance to register ranges for x_2 in i_1 < x_2 where
both i_1 and x_2 might have ranges that are useful.
I will address this once the basic structure is in place if that is OK 
with you.




push and pop_value_range should be methods in the dom walker class
and vrp_stack and cond_stack should be a single stack.  You can omit
basic_block if you use a "magic" NULL_TREE var as marker (simply
push a NULL_TREE, NULL pair at the end of before_dom_children).


Done.



you can use e->flags & EDGE_TRUE_VALUE/EDGE_FALSE_VALUE

why do you need those TREE_OVERFLOW checks?

+ tree cond = build2 (code, boolean_type_node, op0, op1);
+ tree a = build2 (ASSERT_EXPR, TREE_TYPE (op0), op0, cond);
+ extract_range_from_assert (&vr, a);

so I was hoping that the "refactoring" patch in the series would expose a
more
useful interface than extract_range_from_assert ... namely one that can
extract a range from the comparison directly and does not require building
a scratch ASSERT_EXPR.



I have split extract_range_from_assert into
extract_range_for_var_from_comparison_expr and using it now. Is that better?


See above.




+ /* If we found any usable VR, set the VR to ssa_name and create
a
+restore point in the cond_stack with the  old VR. */
+ if (vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE)
+   {
+ value_range *new_vr = XCNEW (value_range);
+ *new_vr = vr;
+ cond_stack.safe_push (std::make_pair (bb,
+   std::make_pair (op0,
+
old_vr)));
+ change_value_range (op0, new_vr);

I don't like 'change_value_range' as interface, please integrate that into
a push/pop_value_range style interface instead.



Tried using push/pop interface.



+   vrp_visit_stmt (stmt, &taken_edge_p, &output_p);
+}
+
+  return NULL;

you should return taken_edge_p (misnamed as it isn't a pointer) and take
advantage of EDGE_EXECUTABLE.  Again see DOM/SCCVN (might want to
defer this as a followup improvement).



I have added a TODO to this effect and will comeback to it.



Note that the advantage of a DOM-based VRP is that backtracking is easy
to implement (you don't do that yet).  That is, after DEF got a (better)
value-range you can simply re-visit all the defs of its uses (and
recursively).
I think you have to be careful with stmts that might prematurely leave a
BB
though (like via EH).  So sth for a followup as well.



Is this OK now. Bootstrapped and regression tested on x86_64-linux  with no
new regressions.


Better, still not perfect.

I'm also arguing on the pass placement now - you put it where it may make sense
for IPA VRP (but then IPA VRP could simply do this in its analysis phase) but
not so much where it makes sense during the early pipeline.  I think it makes
sense after FRE.

Looking at how you finalize I see several issues with simply re-using
vrp_fin

Re: [RFC][IPA-VRP] Early VRP Implementation

[Richard Biener]

On Tue, Jul 26, 2016 at 2:27 PM, kugan
 wrote:
>
>
> Hi Riachard,
>
> Thanks for the review. Here is an updated patch with comments below.
>
>> +/* Restore/Pop all the old VRs maintained in the cond_stack.  */
>> +
>> +void evrp_dom_walker::finalize_dom_walker ()
>> +{
>> +  while (!cond_stack.is_empty ())
>> +{
>> +  tree var = cond_stack.last ().second;
>> +  pop_value_range (var);
>> +  cond_stack.pop ();
>> +}
>>
>> why is this necessary at all?  Looks like a waste of time (and the
>> stack should be empty here
>> anyway).  I think you leak cond_stack as well, I suppose using
>> auto_vec might work here,
>> you have to check.
>
> Done.
>
>>

 + /* Discover VR when condition is true.  */
 + if (te == e
 + && !TREE_OVERFLOW_P (op0)
 + && !TREE_OVERFLOW_P (op1))
>>>
>>>
>>>
>>> This is mainly to handle gcc.dg/pr38934.c. This would result in ICE from
>>> set_value_range otherwise:
>>>
>>> gcc_assert ((!TREE_OVERFLOW_P (min) || is_overflow_infinity (min))
>>>   && (!TREE_OVERFLOW_P (max) || is_overflow_infinity
>>> (max)));
>>
>>
>> Ok, instead make sure to remove the overflow flag via
>>
>>   if (TREE_OVERFLOW_P (op0))
>> op0 = drop_tree_overflow (op0);
>
>  ...
> Done.
>
>>
>> it looks like you want to merge the if ( & EDGE_TRUE_VALUE) and
>> FALSE_VALUE
>> cases and only invert the tree comparison for the false edge.
>
> Done.
>
>>
>> + tree cond = build2 (code, boolean_type_node, op0, op1);
>> + extract_range_for_var_from_comparison_expr (&vr, op0, cond);
>>
>> no wasteful tree building here please.  Instead of cond pass in code,
>> op0 and op1
>> as separate arguments.
>
> Done.
>
>>
>> + /* If we found any usable VR, set the VR to ssa_name and create
>> a
>> +PUSH old value in the cond_stack with the old VR.  */
>> + if (vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE)
>> +   {
>> + value_range *new_vr = vrp_value_range_pool.allocate ();
>> + memset (new_vr, 0, sizeof (*new_vr));
>> + *new_vr = vr;
>> + cond_stack.safe_push (std::make_pair (bb, op0));
>>
>> the memset looks redundant given you copy-assing from vr anyway.
>
> Done.
>
>>
>> You seem to miss the chance to register ranges for x_2 in i_1 < x_2 where
>> both i_1 and x_2 might have ranges that are useful.
>
> I will address this once the basic structure is in place if that is OK with
> you.

Sure.  Just note it down somewhere.

>>
>> push and pop_value_range should be methods in the dom walker class
>> and vrp_stack and cond_stack should be a single stack.  You can omit
>> basic_block if you use a "magic" NULL_TREE var as marker (simply
>> push a NULL_TREE, NULL pair at the end of before_dom_children).
>>
> Done.
>
>

 you can use e->flags & EDGE_TRUE_VALUE/EDGE_FALSE_VALUE

 why do you need those TREE_OVERFLOW checks?

 + tree cond = build2 (code, boolean_type_node, op0, op1);
 + tree a = build2 (ASSERT_EXPR, TREE_TYPE (op0), op0, cond);
 + extract_range_from_assert (&vr, a);

 so I was hoping that the "refactoring" patch in the series would expose
 a
 more
 useful interface than extract_range_from_assert ... namely one that can
 extract a range from the comparison directly and does not require
 building
 a scratch ASSERT_EXPR.
>>>
>>>
>>>
>>> I have split extract_range_from_assert into
>>> extract_range_for_var_from_comparison_expr and using it now. Is that
>>> better?
>>
>>
>> See above.
>>


 + /* If we found any usable VR, set the VR to ssa_name and
 create
 a
 +restore point in the cond_stack with the  old VR. */
 + if (vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE)
 +   {
 + value_range *new_vr = XCNEW (value_range);
 + *new_vr = vr;
 + cond_stack.safe_push (std::make_pair (bb,
 +   std::make_pair (op0,
 +
 old_vr)));
 + change_value_range (op0, new_vr);

 I don't like 'change_value_range' as interface, please integrate that
 into
 a push/pop_value_range style interface instead.
>>>
>>>
>>>
>>> Tried using push/pop interface.



 +   vrp_visit_stmt (stmt, &taken_edge_p, &output_p);
 +}
 +
 +  return NULL;

 you should return taken_edge_p (misnamed as it isn't a pointer) and take
 advantage of EDGE_EXECUTABLE.  Again see DOM/SCCVN (might want to
 defer this as a followup improvement).
>>>
>>>
>>>
>>> I have added a TODO to this effect and will comeback to it.



 Note that the advantage of a DOM-based VRP is that backtracking is easy
 to implement (you don't do that yet).  That is, after DEF got a (better)
 value-range you can simply re-visit all the de