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

Xionghu Luo luoxhu@linux.ibm.com
Wed Nov 24 05:03:35 GMT 2021


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






More information about the Gcc-patches mailing list