Enable ranger for ipa-prop

Hi,
as shown in the testcase (which would eventually be useful for
optimizing std::vector's push_back), ipa-prop can use context dependent ranger
queries for better value range info.

Bootstrapped/regtested x86_64-linux, OK?

Honza

gcc/ChangeLog:

	PR middle-end/110377
	* ipa-prop.cc (ipa_compute_jump_functions_for_edge): Add ranger
	parameter; use ranger instance for rnage queries.
	(ipa_compute_jump_functions_for_bb): Pass around ranger.
	(analysis_dom_walker::before_dom_children): Enable ranger.

gcc/testsuite/ChangeLog:

	PR middle-end/110377
	* gcc.dg/tree-ssa/pr110377.c: New test.

On 6/27/23 09:19, Jan Hubicka wrote:
> Hi,
> as shown in the testcase (which would eventually be useful for
> optimizing std::vector's push_back), ipa-prop can use context dependent ranger
> queries for better value range info.
>
> Bootstrapped/regtested x86_64-linux, OK?

Quick question.

When you call enable_ranger(), its gives you a ranger back, but it also 
sets the range query for the specified context to that same instance.  
So from that point forward  all existing calls to get_range_query(fun) 
will now use the context ranger

enable_ranger (struct function *fun, bool use_imm_uses)
<...>
   gcc_checking_assert (!fun->x_range_query);
   r = new gimple_ranger (use_imm_uses);
   fun->x_range_query = r;
   return r;

So you probably dont have to pass a ranger around?  or is that ranger 
you are passing for a different context?


Andrew

On Tue, Jun 27 2023, Jan Hubicka wrote:
> Hi,
> as shown in the testcase (which would eventually be useful for
> optimizing std::vector's push_back), ipa-prop can use context dependent ranger
> queries for better value range info.
>
> Bootstrapped/regtested x86_64-linux, OK?
>
> Honza
>
> gcc/ChangeLog:
>
> 	PR middle-end/110377
> 	* ipa-prop.cc (ipa_compute_jump_functions_for_edge): Add ranger
> 	parameter; use ranger instance for rnage queries.
> 	(ipa_compute_jump_functions_for_bb): Pass around ranger.
> 	(analysis_dom_walker::before_dom_children): Enable ranger.

Looks good to me (with or without passing a ranger parameter around).

Martin


>
> gcc/testsuite/ChangeLog:
>
> 	PR middle-end/110377
> 	* gcc.dg/tree-ssa/pr110377.c: New test.
>
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr110377.c b/gcc/testsuite/gcc.dg/tree-ssa/pr110377.c
> new file mode 100644
> index 00000000000..cbe3441caea
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr110377.c
> @@ -0,0 +1,16 @@
> +/* { dg-do compile */
> +/* { dg-options "-O2 -fdump-ipa-fnsummary" } */
> +int test3(int);
> +__attribute__ ((noinline))
> +void test2(int a)
> +{
> +	test3(a);
> +}
> +void
> +test(int n)
> +{
> +        if (n > 5)
> +          __builtin_unreachable ();
> +        test2(n);
> +}
> +/* { dg-final { scan-tree-dump "-INF, 5-INF" "fnsummary" } }  */
> diff --git a/gcc/ipa-prop.cc b/gcc/ipa-prop.cc
> index 41c812194ca..693d4805d93 100644
> --- a/gcc/ipa-prop.cc
> +++ b/gcc/ipa-prop.cc
> @@ -2341,7 +2341,8 @@ ipa_set_jfunc_vr (ipa_jump_func *jf, const ipa_vr &vr)
>  
>  static void
>  ipa_compute_jump_functions_for_edge (struct ipa_func_body_info *fbi,
> -				     struct cgraph_edge *cs)
> +				     struct cgraph_edge *cs,
> +				     gimple_ranger *ranger)
>  {
>    ipa_node_params *info = ipa_node_params_sum->get (cs->caller);
>    ipa_edge_args *args = ipa_edge_args_sum->get_create (cs);
> @@ -2386,7 +2387,7 @@ ipa_compute_jump_functions_for_edge (struct ipa_func_body_info *fbi,
>  
>  	  if (TREE_CODE (arg) == SSA_NAME
>  	      && param_type
> -	      && get_range_query (cfun)->range_of_expr (vr, arg)
> +	      && get_range_query (cfun)->range_of_expr (vr, arg, cs->call_stmt)
>  	      && vr.nonzero_p ())
>  	    addr_nonzero = true;
>  	  else if (tree_single_nonzero_warnv_p (arg, &strict_overflow))
> @@ -2408,7 +2409,7 @@ ipa_compute_jump_functions_for_edge (struct ipa_func_body_info *fbi,
>  	      && Value_Range::supports_type_p (param_type)
>  	      && irange::supports_p (TREE_TYPE (arg))
>  	      && irange::supports_p (param_type)
> -	      && get_range_query (cfun)->range_of_expr (vr, arg)
> +	      && ranger->range_of_expr (vr, arg, cs->call_stmt)
>  	      && !vr.undefined_p ())
>  	    {
>  	      Value_Range resvr (vr);
> @@ -2517,7 +2518,8 @@ ipa_compute_jump_functions_for_edge (struct ipa_func_body_info *fbi,
>     from BB.  */
>  
>  static void
> -ipa_compute_jump_functions_for_bb (struct ipa_func_body_info *fbi, basic_block bb)
> +ipa_compute_jump_functions_for_bb (struct ipa_func_body_info *fbi, basic_block bb,
> +				   gimple_ranger *ranger)
>  {
>    struct ipa_bb_info *bi = ipa_get_bb_info (fbi, bb);
>    int i;
> @@ -2536,7 +2538,7 @@ ipa_compute_jump_functions_for_bb (struct ipa_func_body_info *fbi, basic_block b
>  	      && !gimple_call_fnspec (cs->call_stmt).known_p ())
>  	    continue;
>  	}
> -      ipa_compute_jump_functions_for_edge (fbi, cs);
> +      ipa_compute_jump_functions_for_edge (fbi, cs, ranger);
>      }
>  }
>  
> @@ -3110,19 +3112,27 @@ class analysis_dom_walker : public dom_walker
>  {
>  public:
>    analysis_dom_walker (struct ipa_func_body_info *fbi)
> -    : dom_walker (CDI_DOMINATORS), m_fbi (fbi) {}
> +    : dom_walker (CDI_DOMINATORS), m_fbi (fbi)
> +  {
> +    m_ranger = enable_ranger (cfun, false);
> +  }
> +  ~analysis_dom_walker ()
> +  {
> +    disable_ranger (cfun);
> +  }
>  
>    edge before_dom_children (basic_block) final override;
>  
>  private:
>    struct ipa_func_body_info *m_fbi;
> +  gimple_ranger *m_ranger;
>  };
>  
>  edge
>  analysis_dom_walker::before_dom_children (basic_block bb)
>  {
>    ipa_analyze_params_uses_in_bb (m_fbi, bb);
> -  ipa_compute_jump_functions_for_bb (m_fbi, bb);
> +  ipa_compute_jump_functions_for_bb (m_fbi, bb, m_ranger);
>    return NULL;
>  }
>

> 
> On 6/27/23 09:19, Jan Hubicka wrote:
> > Hi,
> > as shown in the testcase (which would eventually be useful for
> > optimizing std::vector's push_back), ipa-prop can use context dependent ranger
> > queries for better value range info.
> > 
> > Bootstrapped/regtested x86_64-linux, OK?
> 
> Quick question.
> 
> When you call enable_ranger(), its gives you a ranger back, but it also sets
> the range query for the specified context to that same instance.  So from
> that point forward  all existing calls to get_range_query(fun) will now use
> the context ranger
> 
> enable_ranger (struct function *fun, bool use_imm_uses)
> <...>
>   gcc_checking_assert (!fun->x_range_query);
>   r = new gimple_ranger (use_imm_uses);
>   fun->x_range_query = r;
>   return r;
> 
> So you probably dont have to pass a ranger around?  or is that ranger you
> are passing for a different context?

I don't need passing ranger around - I just did not know that.  I tought
the default one is the context insensitive one, I will simplify the
patch.  I need to look more into how ranger works.

Honza
> 
> 
> Andrew
> 
>

On 6/27/23 12:24, Jan Hubicka wrote:
>> On 6/27/23 09:19, Jan Hubicka wrote:
>>> Hi,
>>> as shown in the testcase (which would eventually be useful for
>>> optimizing std::vector's push_back), ipa-prop can use context dependent ranger
>>> queries for better value range info.
>>>
>>> Bootstrapped/regtested x86_64-linux, OK?
>> Quick question.
>>
>> When you call enable_ranger(), its gives you a ranger back, but it also sets
>> the range query for the specified context to that same instance.  So from
>> that point forward  all existing calls to get_range_query(fun) will now use
>> the context ranger
>>
>> enable_ranger (struct function *fun, bool use_imm_uses)
>> <...>
>>    gcc_checking_assert (!fun->x_range_query);
>>    r = new gimple_ranger (use_imm_uses);
>>    fun->x_range_query = r;
>>    return r;
>>
>> So you probably dont have to pass a ranger around?  or is that ranger you
>> are passing for a different context?
> I don't need passing ranger around - I just did not know that.  I tought
> the default one is the context insensitive one, I will simplify the
> patch.  I need to look more into how ranger works.
>
>
No need. Its magic!

Andrew


PS. well, we tried to provide an interface to make it as seamless as 
possible with the whole range-query thing.
10,000 foot view:

The range_query object (value-range.h) replaces the old 
SSA_NAME_RANGE_INFO macros.  It adds the ability to provide an optional 
context in the form of a stmt or edge to any query.  If no context is 
provided, it simply provides the global value. There are basically 3 
queries:

   virtual bool range_of_expr (vrange &r, tree expr, gimple * = NULL) ;
   virtual bool range_on_edge (vrange &r, edge, tree expr);
   virtual bool range_of_stmt (vrange &r, gimple *, tree name = NULL);

- range_of_stmt evaluates the DEF of the stmt, but can also evaluate 
things like  "if (x < y)" that have an implicit boolean LHS.  If NAME is 
provided, it needs to match the DEF. Thats mostly flexibility for 
dealing with something like multiple defs, you can specify which def.
- range_on_edge provides the range of an ssa-name as it would be valued 
on a specific edge.
- range_of_expr is used to ask for the range of any ssa_name or tree 
expression as it occurs on entry to a specific stmt. Normally we use 
this to ask for the range of an ssa-name as its used on a stmt,  but it 
can evaluate expression trees as well.

These requests are not limited to names which occur on a stmt.. we can 
recompute values by asking for the range of value as they occur at other 
locations in the IL.  ie
x_2 = b_3 + 5
<...>
if (b_3 > 7)
    blah (x_2)
When we ask for the range of x_2 at the call to blah, ranger actually 
recomputes x_2 = b_3 + 5 at the call site by asking for the range of b_3 
on the outgoing edge leading to the block with the call to blah, and 
thus uses b_3 == [8, +INF] to re-evaluate x_2

Internally, ranger uses the exact same API to evaluate everything that 
external clients use.


The default query object is global_range_query, which ignores any 
location (stmt or edge) information provided, and simply returns the 
global value. This amounts to an identical result as the old 
SSA_NAME_RANGE_INFO request, and when get_range_query () is called, this 
is the default range_query that is provided.

When a pass calls enable_ranger(), the default query is changed to this 
new instance (which supports context information), and any further calls 
to get_range_query() will now invoke ranger instead of the 
global_range_query.  It uses its on-demand support to go and answer the 
range question by looking at only what it needs to in order to answer 
the question.  This is the exact same ranger code base that all the VRP 
passes use, so you get almost the same level of power to answer 
questions.  There are just a couple of little things that VRP enables 
because it does a DOM walk, but they are fairly minor for most cases.

if you use the range_query API, and do not provide a stmt or an edge, 
then we can't provide contextual range information, and you'll go back 
to getting just global information again.

I think Aldy has converted everything to the new range_query API...  
which means any pass that could benefit from contextual range 
information , in theory, only needs to enable_ranger() and provide a 
context stmt or edge on the range query call.

Just remember to disable it when done :-)

Andrew

> 
> On 6/27/23 12:24, Jan Hubicka wrote:
> > > On 6/27/23 09:19, Jan Hubicka wrote:
> > > > Hi,
> > > > as shown in the testcase (which would eventually be useful for
> > > > optimizing std::vector's push_back), ipa-prop can use context dependent ranger
> > > > queries for better value range info.
> > > > 
> > > > Bootstrapped/regtested x86_64-linux, OK?
> > > Quick question.
> > > 
> > > When you call enable_ranger(), its gives you a ranger back, but it also sets
> > > the range query for the specified context to that same instance.  So from
> > > that point forward  all existing calls to get_range_query(fun) will now use
> > > the context ranger
> > > 
> > > enable_ranger (struct function *fun, bool use_imm_uses)
> > > <...>
> > >    gcc_checking_assert (!fun->x_range_query);
> > >    r = new gimple_ranger (use_imm_uses);
> > >    fun->x_range_query = r;
> > >    return r;
> > > 
> > > So you probably dont have to pass a ranger around?  or is that ranger you
> > > are passing for a different context?
> > I don't need passing ranger around - I just did not know that.  I tought
> > the default one is the context insensitive one, I will simplify the
> > patch.  I need to look more into how ranger works.
> > 
> > 
> No need. Its magic!
Cool, thanks for the explanation!
I pushed the following simplified version of the patch.  Now back to
getting push_back faster :)

gcc/ChangeLog:

	PR tree-optimization/110377
	* ipa-prop.cc (ipa_compute_jump_functions_for_edge): Pass statement to
	the ranger query.
	(ipa_analyze_node): Enable ranger.

gcc/testsuite/ChangeLog:

	PR tree-optimization/110377
	* gcc.dg/ipa/pr110377.c: New test.

diff --git a/gcc/ipa-prop.cc b/gcc/ipa-prop.cc
index 41c812194ca..33bda8288fc 100644
--- a/gcc/ipa-prop.cc
+++ b/gcc/ipa-prop.cc
@@ -2386,7 +2386,7 @@ ipa_compute_jump_functions_for_edge (struct ipa_func_body_info *fbi,
 
 	  if (TREE_CODE (arg) == SSA_NAME
 	      && param_type
-	      && get_range_query (cfun)->range_of_expr (vr, arg)
+	      && get_range_query (cfun)->range_of_expr (vr, arg, cs->call_stmt)
 	      && vr.nonzero_p ())
 	    addr_nonzero = true;
 	  else if (tree_single_nonzero_warnv_p (arg, &strict_overflow))
@@ -2408,7 +2408,7 @@ ipa_compute_jump_functions_for_edge (struct ipa_func_body_info *fbi,
 	      && Value_Range::supports_type_p (param_type)
 	      && irange::supports_p (TREE_TYPE (arg))
 	      && irange::supports_p (param_type)
-	      && get_range_query (cfun)->range_of_expr (vr, arg)
+	      && get_range_query (cfun)->range_of_expr (vr, arg, cs->call_stmt)
 	      && !vr.undefined_p ())
 	    {
 	      Value_Range resvr (vr);
@@ -3190,7 +3190,9 @@ ipa_analyze_node (struct cgraph_node *node)
       bi->cg_edges.safe_push (cs);
     }
 
+  enable_ranger (cfun, false);
   analysis_dom_walker (&fbi).walk (ENTRY_BLOCK_PTR_FOR_FN (cfun));
+  disable_ranger (cfun);
 
   ipa_release_body_info (&fbi);
   free_dominance_info (CDI_DOMINATORS);
diff --git a/gcc/testsuite/gcc.dg/ipa/pr110377.c b/gcc/testsuite/gcc.dg/ipa/pr110377.c
new file mode 100644
index 00000000000..63120a97bd0
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/ipa/pr110377.c
@@ -0,0 +1,16 @@
+/* { dg-do compile */
+/* { dg-options "-O2 -fdump-ipa-cp" } */
+int test3(int);
+__attribute__ ((noinline))
+void test2(int a)
+{
+	test3(a);
+}
+void
+test(int n)
+{
+        if (n > 5)
+          __builtin_unreachable ();
+        test2(n);
+}
+/* { dg-final { scan-ipa-dump "-INF, 5" "cp" } }  */