[RFC] ipa-cp: Fix PGO regression caused by r278808

The performance of exchange2 built with PGO will decrease ~28% by r278808
due to profile count set incorrectly.  The cloned nodes are updated to a
very small count caused later pass cunroll fail to unroll the recursive
function in exchange2, This patch enables adding orig_sum to the new nodes
for self recursive node.

digits_2 ->
digits_2.constprop.0, digits_2.constprop.1, etc.

gcc/ChangeLog:

	2019-12-10  Luo Xiong Hu  <luoxhu@linux.ibm.com>

	* ipa-pure-const.c (self_recursive_p): Move it from ...
	(propagate_pure_const): Use cgraph_node::self_recursive_p.
	(pass_nothrow::execute): Likewise.
	* cgraph.h (cgraph_node::self_recursive_p): to ... this.
	* ipa-cp.c (update_profiling_info): Check self_recursive_p node.
---
 gcc/cgraph.h         | 18 ++++++++++++++++++
 gcc/ipa-cp.c         |  5 ++++-
 gcc/ipa-pure-const.c | 19 ++-----------------
 3 files changed, 24 insertions(+), 18 deletions(-)

CC'ing Martin and Honza.

Martin

Hi,
I think the updating should treat self recursive edges as loops: that is
calculate SUM of counts incomming edges which are not self recursive,
calculate probability of self recursing and then set count as
SUM * (1/(1-probability_of_recursion))
we do same thing when computing counts withing loops.

Martin, I woner how updating works for indirectly self recursive edges?

Honza

Hi,

On Tue, Dec 10 2019, Jan Hubicka wrote:
> Hi,
> I think the updating should treat self recursive edges as loops: that is
> calculate SUM of counts incomming edges which are not self recursive,
> calculate probability of self recursing and then set count as
> SUM * (1/(1-probability_of_recursion))
> we do same thing when computing counts withing loops.
>
> Martin, I woner how updating works for indirectly self recursive edges?

It does not special-case them in any way, if that was the question.

Martin

> Hi,
> 
> On Tue, Dec 10 2019, Jan Hubicka wrote:
> > Hi,
> > I think the updating should treat self recursive edges as loops: that is
> > calculate SUM of counts incomming edges which are not self recursive,
> > calculate probability of self recursing and then set count as
> > SUM * (1/(1-probability_of_recursion))
> > we do same thing when computing counts withing loops.
> >
> > Martin, I woner how updating works for indirectly self recursive edges?
> 
> It does not special-case them in any way, if that was the question.

Well, it should, summing only frequencies of edges entering the SCC is
not going to give a good answer.
If SCC is having single entry and forms a loop the generalization of
algorithm above will work, but for general graphs this is hard problem.

I suppose we could special case self recurisve nodes (since they are
most common) and apply some fixed scale for other SCCs?

Also i wonder if the updating is done in RPO so we do not account edges
not updated yet?

Honza

> 
> Martin

Thanks Honza,

On 2019/12/10 19:06, Jan Hubicka wrote:
>> Hi,
>>
>> On Tue, Dec 10 2019, Jan Hubicka wrote:
>>> Hi,
>>> I think the updating should treat self recursive edges as loops: that is
>>> calculate SUM of counts incomming edges which are not self recursive,
>>> calculate probability of self recursing and then set count as
>>> SUM * (1/(1-probability_of_recursion))
>>> we do same thing when computing counts withing loops.
>>>
>>> Martin, I woner how updating works for indirectly self recursive edges?
>>
>> It does not special-case them in any way, if that was the question.
> 
> Well, it should, summing only frequencies of edges entering the SCC is
> not going to give a good answer.
> If SCC is having single entry and forms a loop the generalization of
> algorithm above will work, but for general graphs this is hard problem.
> 
> I suppose we could special case self recurisve nodes (since they are
> most common) and apply some fixed scale for other SCCs?
> 
> Also i wonder if the updating is done in RPO so we do not account edges
> not updated yet?

I have several questions with you comments.
1.  Where is the loops counts prob calculation code please?  And I am not
quite sure about the formula SUM * (1/(1-probability_of_recursion)).
At this moment, the self recursive node graph will be transformed as below:

            orig_node<-----
               |    |------| 
               |  
  caller ---> new_node

Assuming:		
e1: caller    ->  new_node:  count1
e2: orig_node -> orig_node:  count2
e3: new_node  -> orig_node:  count2 (same as back edge when cloned)

e3 is not considered to be a self recursive edge now?
So:
SUM = count2
probability_of_recursion should be count2/(count2 + count2)
=>
orig_node.count = SUM * (1/(1-probability_of_recursion)) = count2 * 2

But the count2 of e3 is not correct as it was copied when cloned which makes
the calculation inaccurate.  And the important thing is new_node.count is
still UNCERTAIN.

2.  Also, the orig_node_count is already inaccurate due to
ipa-cp.c:4289   orig_node_count = (orig_sum + new_sum).apply_scale (12, 10);
Since the parameter param_ipa_cp_max_recursive_depth defines how many nodes
are cloned, is it reasonable to update self_scc node as below to simplify the
calculation(replace self_recursive_p with info->node_is_self_scc)?

+  class ipa_node_params *info = IPA_NODE_REF (orig_node);
+  if (info && info->node_is_self_scc)
+    new_node->count
+      = (orig_sum + new_sum).apply_scale (1, param_ipa_cp_max_recursive_depth);
+  else
+    new_node->count = new_sum;

3.  The recursive ipa-cp will create multiple SCC nodes based on orig_node,
next new_node2 no need update previous new_node1, as each new_node takes
1/param_ipa_cp_max_recursive_depth execution count from orig_node.

BR
Xiong Hu

> 
> Honza
> 
>>
>> Martin