Patchwork Fix the LOOP_BRANCH prediction

login
register
mail settings
Submitter Dehao Chen
Date July 31, 2012, 3:17 a.m.
Message ID <CAO2gOZWwv_UiVyr8FU8zeTJrk+CfTXPhtsT9eOpzbP4z-XUrQA@mail.gmail.com>
Download mbox | patch
Permalink /patch/174136/
State New
Headers show

Comments

Dehao Chen - July 31, 2012, 3:17 a.m.
Hi,

This patch fixed the problem when a LOOP_EXIT edge for the inner loop
happened to target at the LOOP_LATCH of the outer loop. As the outer
loop is processed first, the LOOP_BRANCH heuristic is honored
(first_match), thus the inner loop's trip count is 0. (The attached
unittest demonstrates this).

Bootstrapped and passed gcc regression test.

Is it ok for trunk?

Thanks,
Dehao

gcc/ChangeLog

2012-07-30  Dehao Chen  <dehao@google.com>

	* predict.c (predict_loops): Fix the prediction of LOOP_BRANCH.

gcc/testsuite/ChangeLog

2012-07-31  Dehao Chen  <dehao@google.com>

	* gcc.dg/predict-7.c: New test.
Richard Guenther - July 31, 2012, 9:18 a.m.
On Tue, Jul 31, 2012 at 5:17 AM, Dehao Chen <dehao@google.com> wrote:
> Hi,
>
> This patch fixed the problem when a LOOP_EXIT edge for the inner loop
> happened to target at the LOOP_LATCH of the outer loop. As the outer
> loop is processed first, the LOOP_BRANCH heuristic is honored
> (first_match), thus the inner loop's trip count is 0. (The attached
> unittest demonstrates this).
>
> Bootstrapped and passed gcc regression test.
>
> Is it ok for trunk?
>
> Thanks,
> Dehao
>
> gcc/ChangeLog
>
> 2012-07-30  Dehao Chen  <dehao@google.com>
>
>         * predict.c (predict_loops): Fix the prediction of LOOP_BRANCH.
>
> gcc/testsuite/ChangeLog
>
> 2012-07-31  Dehao Chen  <dehao@google.com>
>
>         * gcc.dg/predict-7.c: New test.
>
> Index: gcc/testsuite/gcc.dg/predict-7.c
> ===================================================================
> --- gcc/testsuite/gcc.dg/predict-7.c    (revision 0)
> +++ gcc/testsuite/gcc.dg/predict-7.c    (revision 0)
> @@ -0,0 +1,17 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
> +
> +extern int global;
> +
> +int bar (int);
> +
> +void foo (int base)
> +{
> +  int i;
> +  while (global < 10)
> +    for (i = base; i < 10; i++)
> +      bar (i);
> +}
> +
> +/* { dg-final { scan-tree-dump-times "loop branch heuristics" 0
> "profile_estimate"} } */
> +/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
> Index: gcc/predict.c
> ===================================================================
> --- gcc/predict.c       (revision 189835)
> +++ gcc/predict.c       (working copy)
> @@ -1404,7 +1404,7 @@
>
>           /* Loop branch heuristics - predict an edge back to a
>              loop's head as taken.  */
> -         if (bb == loop->latch)
> +         if (bb == loop->latch && bb->loop_father == loop)
>             {
>               e = find_edge (loop->latch, loop->header);
>               if (e)

I think this heuristic should instead move out of the loop iterating over loop
nodes and be done before like

  if (loop->latch)
    {
       e = find_edge (loop->latch, loop->header);
       ...
    }

which also makes header_found initialized before we visit loop blocks.

Instead the code

          /* Loop exit heuristics - predict an edge exiting the loop if the
             conditional has no loop header successors as not taken.  */
          if (!header_found
              /* If we already used more reliable loop exit predictors, do not
                 bother with PRED_LOOP_EXIT.  */
...
              FOR_EACH_EDGE (e, ei, bb->succs)
                if (e->dest->index < NUM_FIXED_BLOCKS
                    || !flow_bb_inside_loop_p (loop, e->dest))
                  predict_edge (e, PRED_LOOP_EXIT, probability);

looks wrong for bb's that are parts of an inner loop of loop - assuming we
only want to predicate exits from loop and not exits from an inner loop
that also happen to exit loop (we will do that when predicating the inner loop).

Is that what you experienced?

Thanks,
Richard.

Patch

Index: gcc/testsuite/gcc.dg/predict-7.c
===================================================================
--- gcc/testsuite/gcc.dg/predict-7.c	(revision 0)
+++ gcc/testsuite/gcc.dg/predict-7.c	(revision 0)
@@ -0,0 +1,17 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+extern int global;
+
+int bar (int);
+
+void foo (int base)
+{
+  int i;
+  while (global < 10)
+    for (i = base; i < 10; i++)
+      bar (i);
+}
+
+/* { dg-final { scan-tree-dump-times "loop branch heuristics" 0
"profile_estimate"} } */
+/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
Index: gcc/predict.c
===================================================================
--- gcc/predict.c	(revision 189835)
+++ gcc/predict.c	(working copy)
@@ -1404,7 +1404,7 @@ 

 	  /* Loop branch heuristics - predict an edge back to a
 	     loop's head as taken.  */
-	  if (bb == loop->latch)
+	  if (bb == loop->latch && bb->loop_father == loop)
 	    {
 	      e = find_edge (loop->latch, loop->header);
 	      if (e)