[GOOGLE] Refactor the profile propagation for AutoFDO

[Xinliang David Li]

On Mon, Nov 25, 2013 at 10:23 AM, Dehao Chen <dehao@google.com> wrote:
> On Mon, Nov 25, 2013 at 10:08 AM, Diego Novillo <dnovillo@google.com> wrote:
>> Thanks, Deaho.
>>
>> One other thing that I've found on the LLVM implementation (that I'm
>> not sure happens in GCC): self-referential edges.  If a loop consists
>> of a single-basic block, the back edge will point to itself.  I
>> haven't been able to reproduce it with regular control flow constructs
>> in GCC.
>>
>> When this happens, and if we've visited the block itself already
>> (i.e., the block has weights), I've simply set the weight of the
>> self-referential edge to the weight of the block itself.  Do you see
>> any problems with that heuristic?
>
> In this case, the propagate_edge function will keep increasing the BB
> count. We set a threshold (PARAM_AUTOFDO_MAX_PROPAGATE_ITERATIONS) to
> prevent it from making BB count too large.

This is the infinite loop case ..

David
>
> Dehao
>
>>
>>
>> Thanks.  Diego.
>>
>> On Mon, Nov 25, 2013 at 12:56 PM, Dehao Chen <dehao@google.com> wrote:
>>> afdo_propagate_multi_edge can do everything afdo_propagate_single_edge
>>> does. So we refactor the code to keep only one afdo_propagate_edge
>>> function.
>>>
>>> Bootstrapped and passed all unittests and performance tests.
>>>
>>> OK for googlge branch?
>>>
>>> Thanks,
>>> Dehao
>>>
>>> Index: gcc/auto-profile.c
>>> ===================================================================
>>> --- gcc/auto-profile.c (revision 205354)
>>> +++ gcc/auto-profile.c (working copy)
>>> @@ -1069,44 +1069,6 @@ afdo_find_equiv_class (void)
>>>      }
>>>  }
>>>
>>> -/* If a baisk block only has one in/out edge, then the bb count and he
>>> -   edge count should be the same.
>>> -   IS_SUCC is true if the out edge of the basic block is examined.
>>> -   Return TRUE if any basic block/edge count is changed.  */
>>> -
>>> -static bool
>>> -afdo_propagate_single_edge (bool is_succ)
>>> -{
>>> -  basic_block bb;
>>> -  bool changed = false;
>>> -
>>> -  FOR_EACH_BB (bb)
>>> -    if (is_succ ? single_succ_p (bb) : single_pred_p (bb))
>>> -      {
>>> - edge e = is_succ ? single_succ_edge (bb) : single_pred_edge (bb);
>>> - if (((e->flags & EDGE_ANNOTATED) == 0)
>>> -    && ((bb->flags & BB_ANNOTATED) != 0))
>>> -  {
>>> -    e->count = bb->count;
>>> -    e->flags |= EDGE_ANNOTATED;
>>> -    changed = true;
>>> -  }
>>> - else if (((e->flags & EDGE_ANNOTATED) != 0)
>>> -    && ((bb->flags & BB_ANNOTATED) == 0))
>>> -  {
>>> -    bb->count = e->count;
>>> -    bb->flags |= BB_ANNOTATED;
>>> -    changed = true;
>>> -  }
>>> - else if (bb->count != e->count)
>>> -  {
>>> -    e->count = bb->count = MAX (bb->count, e->count);
>>> -    changed = true;
>>> -  }
>>> -      }
>>> -  return changed;
>>> -}
>>> -
>>>  /* If a basic block's count is known, and only one of its in/out edges' count
>>>     is unknown, its count can be calculated.
>>>     Meanwhile, if all of the in/out edges' counts are known, then the basic
>>> @@ -1115,7 +1077,7 @@ afdo_find_equiv_class (void)
>>>     Return TRUE if any basic block/edge count is changed.  */
>>>
>>>  static bool
>>> -afdo_propagate_multi_edge (bool is_succ)
>>> +afdo_propagate_edge (bool is_succ)
>>>  {
>>>    basic_block bb;
>>>    bool changed = false;
>>> @@ -1281,14 +1243,10 @@ afdo_propagate (void)
>>>      {
>>>        changed = false;
>>>
>>> -      if (afdo_propagate_single_edge (true))
>>> +      if (afdo_propagate_edge (true))
>>>   changed = true;
>>> -      if (afdo_propagate_single_edge (false))
>>> +      if (afdo_propagate_edge (false))
>>>   changed = true;
>>> -      if (afdo_propagate_multi_edge (true))
>>> - changed = true;
>>> -      if (afdo_propagate_multi_edge (false))
>>> - changed = true;
>>>        afdo_propagate_circuit ();
>>>      }
>>>  }