Ping: [PATCH v2] Fix incorrect loop exit edge probability [PR103270]

[Xionghu Luo]

Hi Honza,

Gentle ping for this :), thanks.

https://gcc.gnu.org/pipermail/gcc-patches/2021-November/585289.html


On 2021/11/24 13:03, Xionghu Luo via Gcc-patches wrote:
> On 2021/11/23 17:50, Jan Hubicka wrote:
>>> On Tue, Nov 23, 2021 at 6:52 AM Xionghu Luo <luoxhu@linux.ibm.com> wrote:
>>>>
>>>> r12-4526 cancelled jump thread path rotates loop. It exposes a issue in
>>>> profile-estimate when predict_extra_loop_exits, outer loop's exit edge
>>>> is marked as inner loop's extra loop exit and set with incorrect
>>>> prediction, then a hot inner loop will become cold loop finally through
>>>> optimizations, this patch ignores the EDGE_DFS_BACK edge when searching
>>>> extra exit edges to avoid unexpected predict_edge.
>>>
>>> Not sure how outer vs. inner loop exit correlates with EDGE_DFS_BACK,
>>> I have expected a check based on which loop is exited by the edge instead?
>>> A backedge should never be an exit, no?
>>>
>>> Note that the profile pass does not yet mark backedges so EDGE_DFS_BACK
>>> settings are unreliable.
>>
>> So we have two nested loops and an exit which goes from inner loop and
>> exists both loops.  While processing outer loop we set pretty high exit
>> probability that is not good for inner loop?
> 
> No, the edge only belongs to outer loop only.  Can an exit edge belongs to
> two different loops at the same time?
> Exit edges are iterated with LI_FROM_INNERMOST in predict_loops, if an edge
> already has prediction by querying edge_predicted_by_p, maybe_predict_edge
> will early return to not set it again.
> 
> The CFG is:
> 
> 2
> |
> 8<----     // l1
> | \   |
> 10 9  |
> |     |
>   ----7
> 6 <----    // l2
> |     | 
> 11    | 
> |     |
> 4<-   |    // l3
> | \|  |
> 5  3  |
> |     |
> ------
> 
> l2's edge (6->11,6->7) is set to (33%,67%) by l3 unexpectedly.
> 
> FYI: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103270#c5
> 
>>
>> I guess we could just check if exit edge source basic block has same
>> loop depth as the loop we are processing?
>>
> 
> 
> Thanks for the suggestion, it works.  Loop checks already existed in
> predict_paths_for_bb, just need pass down the loop argument.
> Updated as v2 patch.
> 
> 
> v2-0001-Fix-incorrect-loop-exit-edge-probability-PR103270.patch
> 
> r12-4526 cancelled jump thread path rotates loop. It exposes a issue in
> profile-estimate when predict_extra_loop_exits, outer loop's exit edge
> is marked as inner loop's extra loop exit and set with incorrect
> prediction, then a hot inner loop will become cold loop finally through
> optimizations, this patch add loop check when searching extra exit edges
> to avoid unexpected predict_edge from predict_paths_for_bb.
> 
> Regression tested pass on P8 & x86, OK for master?
> 
> gcc/ChangeLog:
> 
> 	PR middle-end/103270
> 	* predict.c (predict_extra_loop_exits): Add loop parameter.
> 	(predict_loops): Call with loop argument.
> 
> gcc/testsuite/ChangeLog:
> 
> 	PR middle-end/103270
> 	* gcc.dg/pr103270.c: New test.
> ---
>  gcc/predict.c                   | 10 ++++++----
>  gcc/testsuite/gcc.dg/pr103270.c | 19 +++++++++++++++++++
>  2 files changed, 25 insertions(+), 4 deletions(-)
>  create mode 100644 gcc/testsuite/gcc.dg/pr103270.c
> 
> diff --git a/gcc/predict.c b/gcc/predict.c
> index 68b11135680..082782ec4e9 100644
> --- a/gcc/predict.c
> +++ b/gcc/predict.c
> @@ -1859,7 +1859,7 @@ predict_iv_comparison (class loop *loop, basic_block bb,
>     exits to predict them using PRED_LOOP_EXTRA_EXIT.  */
> 
>  static void
> -predict_extra_loop_exits (edge exit_edge)
> +predict_extra_loop_exits (class loop *loop, edge exit_edge)
>  {
>    unsigned i;
>    bool check_value_one;
> @@ -1912,12 +1912,14 @@ predict_extra_loop_exits (edge exit_edge)
>  	continue;
>        if (EDGE_COUNT (e->src->succs) != 1)
>  	{
> -	  predict_paths_leading_to_edge (e, PRED_LOOP_EXTRA_EXIT, NOT_TAKEN);
> +	  predict_paths_leading_to_edge (e, PRED_LOOP_EXTRA_EXIT, NOT_TAKEN,
> +					 loop);
>  	  continue;
>  	}
> 
>        FOR_EACH_EDGE (e1, ei, e->src->preds)
> -	predict_paths_leading_to_edge (e1, PRED_LOOP_EXTRA_EXIT, NOT_TAKEN);
> +	predict_paths_leading_to_edge (e1, PRED_LOOP_EXTRA_EXIT, NOT_TAKEN,
> +				       loop);
>      }
>  }
> 
> @@ -2009,7 +2011,7 @@ predict_loops (void)
>  			 ex->src->index, ex->dest->index);
>  	      continue;
>  	    }
> -	  predict_extra_loop_exits (ex);
> +	  predict_extra_loop_exits (loop, ex);
> 
>  	  if (number_of_iterations_exit (loop, ex, &niter_desc, false, false))
>  	    niter = niter_desc.niter;
> diff --git a/gcc/testsuite/gcc.dg/pr103270.c b/gcc/testsuite/gcc.dg/pr103270.c
> new file mode 100644
> index 00000000000..819310e360e
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/pr103270.c
> @@ -0,0 +1,19 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
> +
> +void test(int a, int* i)
> +{
> +  for (; a < 5; ++a)
> +    {
> +      int b = 0;
> +      int c = 0;
> +      for (; b != -11; b--)
> +	for (int d = 0; d ==0; d++)
> +	  {
> +	    *i += c & a;
> +	    c = b;
> +	  }
> +    }
> +}
> +
> +/* { dg-final { scan-tree-dump-not "extra loop exit heuristics of edge\[^:\]*:" "profile_estimate"} } */
> 

-- 
Thanks,
Xionghu