[v2] Fix incorrect loop exit edge probability [PR103270]

  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
  

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"} } */
>