Teach ipa-cp to propagate value ranges over binary operaitons too

Hi,
this patch adds propagation of value ranges through binary operations.
This is disabled for value ranges within SCC to avoid infinite loop during
propagation.  I am bit worried about types here.  As far as I can say we
have something like

VR in lattice of type1
foo (type1 param)
{
  bar ((type3)((type2)param+(type2)4))
}
bar (type4 param)
{
   use param....
}

Now in code type1 is called "operand_type" and type4 is called param_type.
The arithmetics always happens in operand_type but I do not see why these
needs to be necessarily the same?  Anyway this immitates what 
constant jump functions does.

Also I noticed that we use NOP_EXPR to convert from type1 all the way to type4
while ipa-fnsummary uses VIEW_CONVERT_EXPR to convert type3 to type4 that seems
more valid here. However VR folders always returns varying on VIEW_CONVERT_EXPR
(which is probably something that can be fixed)

Bootstrapped/regtested x86_64-linux. Does this look OK?

Honza
	* ipa-cp.c (propagate_vr_across_jump_function): Also propagate
	binary operations.

On Tue, 12 Nov 2019, Jan Hubicka wrote:

> Hi,
> this patch adds propagation of value ranges through binary operations.
> This is disabled for value ranges within SCC to avoid infinite loop during
> propagation.  I am bit worried about types here.  As far as I can say we
> have something like
> 
> VR in lattice of type1
> foo (type1 param)
> {
>   bar ((type3)((type2)param+(type2)4))
> }
> bar (type4 param)
> {
>    use param....
> }
> 
> Now in code type1 is called "operand_type" and type4 is called param_type.
> The arithmetics always happens in operand_type but I do not see why these
> needs to be necessarily the same?  Anyway this immitates what 
> constant jump functions does.
> 
> Also I noticed that we use NOP_EXPR to convert from type1 all the way to type4
> while ipa-fnsummary uses VIEW_CONVERT_EXPR to convert type3 to type4 that seems
> more valid here. However VR folders always returns varying on VIEW_CONVERT_EXPR
> (which is probably something that can be fixed)
> 
> Bootstrapped/regtested x86_64-linux. Does this look OK?
> 
> Honza
> 	* ipa-cp.c (propagate_vr_across_jump_function): Also propagate
> 	binary operations.
> 
> Index: ipa-cp.c
> ===================================================================
> --- ipa-cp.c	(revision 278094)
> +++ ipa-cp.c	(working copy)
> @@ -1974,23 +2039,51 @@ propagate_vr_across_jump_function (cgrap
>    if (jfunc->type == IPA_JF_PASS_THROUGH)
>      {
>        enum tree_code operation = ipa_get_jf_pass_through_operation (jfunc);
> +      class ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
> +      int src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
> +      class ipcp_param_lattices *src_lats
> +	= ipa_get_parm_lattices (caller_info, src_idx);
> +      tree operand_type = ipa_get_type (caller_info, src_idx);
>  
> +      if (src_lats->m_value_range.bottom_p ())
> +	return dest_lat->set_to_bottom ();
> +
> +      value_range vr;
>        if (TREE_CODE_CLASS (operation) == tcc_unary)
>  	{
> -	  class ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
> -	  int src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
> -	  tree operand_type = ipa_get_type (caller_info, src_idx);
> -	  class ipcp_param_lattices *src_lats
> -	    = ipa_get_parm_lattices (caller_info, src_idx);
> -
> -	  if (src_lats->m_value_range.bottom_p ())
> -	    return dest_lat->set_to_bottom ();
> -	  value_range vr;
> -	  if (ipa_vr_operation_and_type_effects (&vr,
> -						 &src_lats->m_value_range.m_vr,
> -						 operation, param_type,
> -						 operand_type))
> -	    return dest_lat->meet_with (&vr);
> +	  ipa_vr_operation_and_type_effects (&vr,
> +					     &src_lats->m_value_range.m_vr,
> +					     operation, param_type,
> +					     operand_type);
> +	}
> +      /* A crude way to prevent unbounded number of value range updates
> +	 in SCC components.  We should allow limited number of updates within
> +	 SCC, too.  */
> +      else if (!ipa_edge_within_scc (cs))
> +	{
> +	  tree op = ipa_get_jf_pass_through_operand (jfunc);
> +	  value_range op_vr (op, op);
> +	  value_range op_res,res;
> +

Do we really know operation is tcc_binary here?

> +	  range_fold_binary_expr (&op_res, operation, operand_type,
> +				  &src_lats->m_value_range.m_vr, &op_vr);
> +	  ipa_vr_operation_and_type_effects (&vr,
> +					     &op_res,
> +					     NOP_EXPR, param_type,
> +					     operand_type);

I hope this one deals with undefined/varying/etc. properly.

I'm also worried about types here - but I know too little about
how we construct the jump function to say whether it's OK.

> +	}
> +      if (!vr.undefined_p () && !vr.varying_p ())
> +	{
> +	  if (jfunc->m_vr)
> +	    {
> +	      value_range jvr;
> +	      if (ipa_vr_operation_and_type_effects (&jvr, jfunc->m_vr,
> +						     NOP_EXPR,
> +						     param_type,
> +						     jfunc->m_vr->type ()))
> +		vr.intersect (*jfunc->m_vr);
> +	    }
> +	  return dest_lat->meet_with (&vr);
>  	}
>      }
>    else if (jfunc->type == IPA_JF_CONST)
>

> > +	  tree op = ipa_get_jf_pass_through_operand (jfunc);
> > +	  value_range op_vr (op, op);
> > +	  value_range op_res,res;
> > +
> 
> Do we really know operation is tcc_binary here?
Constant propagation already assumes that at the same spot:

  if (TREE_CODE_CLASS (opcode) == tcc_unary)
    res = fold_unary (opcode, res_type, input);
  else
    res = fold_binary (opcode, res_type, input,
                       ipa_get_jf_pass_through_operand (jfunc));


> 
> > +	  range_fold_binary_expr (&op_res, operation, operand_type,
> > +				  &src_lats->m_value_range.m_vr, &op_vr);
> > +	  ipa_vr_operation_and_type_effects (&vr,
> > +					     &op_res,
> > +					     NOP_EXPR, param_type,
> > +					     operand_type);
> 
> I hope this one deals with undefined/varying/etc. properly.

ipa_vr_operation will return false if result is varying/undefined which
I ignore here, but then...
> 
> I'm also worried about types here - but I know too little about
> how we construct the jump function to say whether it's OK.
> 
> > +	}
> > +      if (!vr.undefined_p () && !vr.varying_p ())
> > +	{
> > +	  if (jfunc->m_vr)
> > +	    {
> > +	      value_range jvr;
> > +	      if (ipa_vr_operation_and_type_effects (&jvr, jfunc->m_vr,
> > +						     NOP_EXPR,
> > +						     param_type,
> > +						     jfunc->m_vr->type ()))
> > +		vr.intersect (*jfunc->m_vr);
> > +	    }
> > +	  return dest_lat->meet_with (&vr);
Return will not happen here and we will end up at the same path as
before assuming we know nothing.
> >  	}
> >      }
> >    else if (jfunc->type == IPA_JF_CONST)
> > 
> 
> -- 
> Richard Biener <rguenther@suse.de>
> SUSE Software Solutions Germany GmbH, Maxfeldstrasse 5, 90409 Nuernberg,
> Germany; GF: Felix Imendörffer; HRB 36809 (AG Nuernberg)

Hi,

On Tue, Nov 12 2019, Richard Biener wrote:
> On Tue, 12 Nov 2019, Jan Hubicka wrote:
>
>> Hi,
>> this patch adds propagation of value ranges through binary operations.
>> This is disabled for value ranges within SCC to avoid infinite loop during
>> propagation.  I am bit worried about types here.  As far as I can say we
>> have something like
>> 
>> VR in lattice of type1
>> foo (type1 param)
>> {
>>   bar ((type3)((type2)param+(type2)4))
>> }
>> bar (type4 param)
>> {
>>    use param....
>> }
>> 
>> Now in code type1 is called "operand_type" and type4 is called param_type.
>> The arithmetics always happens in operand_type but I do not see why these
>> needs to be necessarily the same?  Anyway this immitates what 
>> constant jump functions does.

well, it all relies on the simple fact that arithmetic jump function
discovery does not cross NOP_EXPRs, or any chain of assignments, so they
are only constructed from things like

  _2 = param_2(D) + 4;
  bar (_2);

but not from

  _1 = (NOP_EXPR) param_2(D);
  _2 =  _1 + 4;
  bar (_2);

I understand that this is getting ever more fragile and that we may want
to remove this limitation.  But there is of course the tradeoff of how
many types we want to stream.  But currently there is no type2 or type3.

>> 
>> Also I noticed that we use NOP_EXPR to convert from type1 all the way to type4
>> while ipa-fnsummary uses VIEW_CONVERT_EXPR to convert type3 to type4 that seems
>> more valid here.

Perhaps.

> However VR folders always returns varying on VIEW_CONVERT_EXPR
>> (which is probably something that can be fixed)
>> 
>> Bootstrapped/regtested x86_64-linux. Does this look OK?

Yes, it does.

>> 
>> Honza
>> 	* ipa-cp.c (propagate_vr_across_jump_function): Also propagate
>> 	binary operations.
>> 
>> Index: ipa-cp.c
>> ===================================================================
>> --- ipa-cp.c	(revision 278094)
>> +++ ipa-cp.c	(working copy)
>> @@ -1974,23 +2039,51 @@ propagate_vr_across_jump_function (cgrap
>>    if (jfunc->type == IPA_JF_PASS_THROUGH)
>>      {
>>        enum tree_code operation = ipa_get_jf_pass_through_operation (jfunc);
>> +      class ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
>> +      int src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
>> +      class ipcp_param_lattices *src_lats
>> +	= ipa_get_parm_lattices (caller_info, src_idx);
>> +      tree operand_type = ipa_get_type (caller_info, src_idx);
>>  
>> +      if (src_lats->m_value_range.bottom_p ())
>> +	return dest_lat->set_to_bottom ();
>> +
>> +      value_range vr;
>>        if (TREE_CODE_CLASS (operation) == tcc_unary)
>>  	{
>> -	  class ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
>> -	  int src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
>> -	  tree operand_type = ipa_get_type (caller_info, src_idx);
>> -	  class ipcp_param_lattices *src_lats
>> -	    = ipa_get_parm_lattices (caller_info, src_idx);
>> -
>> -	  if (src_lats->m_value_range.bottom_p ())
>> -	    return dest_lat->set_to_bottom ();
>> -	  value_range vr;
>> -	  if (ipa_vr_operation_and_type_effects (&vr,
>> -						 &src_lats->m_value_range.m_vr,
>> -						 operation, param_type,
>> -						 operand_type))
>> -	    return dest_lat->meet_with (&vr);
>> +	  ipa_vr_operation_and_type_effects (&vr,
>> +					     &src_lats->m_value_range.m_vr,
>> +					     operation, param_type,
>> +					     operand_type);
>> +	}
>> +      /* A crude way to prevent unbounded number of value range updates
>> +	 in SCC components.  We should allow limited number of updates within
>> +	 SCC, too.  */
>> +      else if (!ipa_edge_within_scc (cs))
>> +	{
>> +	  tree op = ipa_get_jf_pass_through_operand (jfunc);
>> +	  value_range op_vr (op, op);
>> +	  value_range op_res,res;
>> +
>
> Do we really know operation is tcc_binary here?

it is either NOP_EXPR (which in jump functions is basically a marker
that there really is no operation going on), or something coming from
GIMPLE_UNARY_RHS - which hopefully is tcc_unary and here we can
conveniently share the same path for NOP_EXPR too - or from
GIMPLE_BINARY_RHS, which hopefully is tcc_binary.  But an assert may be
reasonable here.

>
>> +	  range_fold_binary_expr (&op_res, operation, operand_type,
>> +				  &src_lats->m_value_range.m_vr, &op_vr);
>> +	  ipa_vr_operation_and_type_effects (&vr,
>> +					     &op_res,
>> +					     NOP_EXPR, param_type,
>> +					     operand_type);

Martin

> 
> well, it all relies on the simple fact that arithmetic jump function
> discovery does not cross NOP_EXPRs, or any chain of assignments, so they
> are only constructed from things like
> 
>   _2 = param_2(D) + 4;
>   bar (_2);
> 
> but not from
> 
>   _1 = (NOP_EXPR) param_2(D);
>   _2 =  _1 + 4;
>   bar (_2);
> 
> I understand that this is getting ever more fragile and that we may want
> to remove this limitation.  But there is of course the tradeoff of how
> many types we want to stream.  But currently there is no type2 or type3.

I see, so type2==type3==type1 and we need only one type conversion which
I do.

Note that since all types (modulo variadic ones which tends to be
horribly broken with LTO) go into global stream streaming an extra type
is basically costing you a pointer in memory and one index in stream.

Honza
> 
> >> 
> >> Also I noticed that we use NOP_EXPR to convert from type1 all the way to type4
> >> while ipa-fnsummary uses VIEW_CONVERT_EXPR to convert type3 to type4 that seems
> >> more valid here.
> 
> Perhaps.
> 
> > However VR folders always returns varying on VIEW_CONVERT_EXPR
> >> (which is probably something that can be fixed)
> >> 
> >> Bootstrapped/regtested x86_64-linux. Does this look OK?
> 
> Yes, it does.
> 
> >> 
> >> Honza
> >> 	* ipa-cp.c (propagate_vr_across_jump_function): Also propagate
> >> 	binary operations.
> >> 
> >> Index: ipa-cp.c
> >> ===================================================================
> >> --- ipa-cp.c	(revision 278094)
> >> +++ ipa-cp.c	(working copy)
> >> @@ -1974,23 +2039,51 @@ propagate_vr_across_jump_function (cgrap
> >>    if (jfunc->type == IPA_JF_PASS_THROUGH)
> >>      {
> >>        enum tree_code operation = ipa_get_jf_pass_through_operation (jfunc);
> >> +      class ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
> >> +      int src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
> >> +      class ipcp_param_lattices *src_lats
> >> +	= ipa_get_parm_lattices (caller_info, src_idx);
> >> +      tree operand_type = ipa_get_type (caller_info, src_idx);
> >>  
> >> +      if (src_lats->m_value_range.bottom_p ())
> >> +	return dest_lat->set_to_bottom ();
> >> +
> >> +      value_range vr;
> >>        if (TREE_CODE_CLASS (operation) == tcc_unary)
> >>  	{
> >> -	  class ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
> >> -	  int src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
> >> -	  tree operand_type = ipa_get_type (caller_info, src_idx);
> >> -	  class ipcp_param_lattices *src_lats
> >> -	    = ipa_get_parm_lattices (caller_info, src_idx);
> >> -
> >> -	  if (src_lats->m_value_range.bottom_p ())
> >> -	    return dest_lat->set_to_bottom ();
> >> -	  value_range vr;
> >> -	  if (ipa_vr_operation_and_type_effects (&vr,
> >> -						 &src_lats->m_value_range.m_vr,
> >> -						 operation, param_type,
> >> -						 operand_type))
> >> -	    return dest_lat->meet_with (&vr);
> >> +	  ipa_vr_operation_and_type_effects (&vr,
> >> +					     &src_lats->m_value_range.m_vr,
> >> +					     operation, param_type,
> >> +					     operand_type);
> >> +	}
> >> +      /* A crude way to prevent unbounded number of value range updates
> >> +	 in SCC components.  We should allow limited number of updates within
> >> +	 SCC, too.  */
> >> +      else if (!ipa_edge_within_scc (cs))
> >> +	{
> >> +	  tree op = ipa_get_jf_pass_through_operand (jfunc);
> >> +	  value_range op_vr (op, op);
> >> +	  value_range op_res,res;
> >> +
> >
> > Do we really know operation is tcc_binary here?
> 
> it is either NOP_EXPR (which in jump functions is basically a marker
> that there really is no operation going on), or something coming from
> GIMPLE_UNARY_RHS - which hopefully is tcc_unary and here we can
> conveniently share the same path for NOP_EXPR too - or from
> GIMPLE_BINARY_RHS, which hopefully is tcc_binary.  But an assert may be
> reasonable here.
> 
> >
> >> +	  range_fold_binary_expr (&op_res, operation, operand_type,
> >> +				  &src_lats->m_value_range.m_vr, &op_vr);
> >> +	  ipa_vr_operation_and_type_effects (&vr,
> >> +					     &op_res,
> >> +					     NOP_EXPR, param_type,
> >> +					     operand_type);
> 
> Martin