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
