[Bug middle-end/38074] New: [4.4 Regression] missed inlining since IRA merge on Core2 Duo

[Bug middle-end/38074] New: [4.4 Regression] missed inlining since IRA merge on Core2 Duo

[dominiq at lps dot ens dot fr]

With gfortran 4.3.2 the functions ddx and ddy in the channel.90 polyhedron test
with:

gfortran -S -m64 -O3 -ffast-math -finline-limit=312 channel.f90

but not for -finline-limit=311.

Since the IRA merge, this is no longer the case even if I use
-finline-limit=6000. This causes a ~5% increase in the execution time (~2.4s
compared to ~2.3s, small but noticeable).

I suspect the same is true for the fatigue.f90 test.


-- 
           Summary: [4.4 Regression] missed inlining since IRA merge on
                    Core2 Duo
           Product: gcc
           Version: 4.4.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: middle-end
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: dominiq at lps dot ens dot fr
 GCC build triplet: i686-apple-darwin9
  GCC host triplet: i686-apple-darwin9
GCC target triplet: i686-apple-darwin9


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=38074

[Bug middle-end/38074] [4.4 Regression] missed inlining since IRA merge on Core2 Duo

[rguenth at gcc dot gnu dot org]

------- Comment #1 from rguenth at gcc dot gnu dot org  2008-11-11 20:21 -------
I don't see how there can be a connection to the IRA merge.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=38074

[Bug middle-end/38074] [4.4 Regression] missed inlining since IRA merge on Core2 Duo

[dominiq at lps dot ens dot fr]

------- Comment #2 from dominiq at lps dot ens dot fr  2008-11-11 20:37 -------
Subject: Re:  [4.4 Regression] missed inlining since IRA merge on Core2 Duo

> I don't see how there can be a connection to the IRA merge.

I don't see either, but the behavior changed between Aug 23 and
Sep  2. At this time the IRA merge was the major shaking and
I did not see what else can have caused that. The merge may have
exposed a latent bug.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=38074

[Bug middle-end/38074] [4.4 Regression] missed inlining since IRA merge on Core2 Duo

[jakub at gcc dot gnu dot org]

------- Comment #3 from jakub at gcc dot gnu dot org  2008-11-11 21:18 -------
There were many changes, mainly from Jan, in that time range that could have
caused it.  The most likely thing I'd say is that the basic blocks where those
functions are called are considered by gcc to be cold and thus considers
inlining it not desirable.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=38074

[Bug middle-end/38074] [4.4 Regression] missed inlining since IRA merge on Core2 Duo

[rguenth at gcc dot gnu dot org]

-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
   Target Milestone|---                         |4.4.0


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=38074

[Bug middle-end/38074] [4.4 Regression] missed inlining since IRA merge on Core2 Duo

[jakub at gcc dot gnu dot org]

------- Comment #4 from jakub at gcc dot gnu dot org  2008-11-28 11:06 -------
On x86_64-linux at -O3 with channel.f90 I get:
Deciding on smaller functions:
Considering inline candidate ddx.
Considering inline candidate ddy.

Considering ddx with 77 insns
 to be inlined into sw
 Estimated growth after inlined into all callees is +49 insns.
 Estimated badness is 16177, frequency 0.00.
 inline_failed:call is unlikely and code size would grow.

Considering ddy with 77 insns
 to be inlined into sw
 Estimated growth after inlined into all callees is +49 insns.
 Estimated badness is 16177, frequency 0.00.
 inline_failed:call is unlikely and code size would grow.

Considering ddy with 77 insns
 to be inlined into sw
 Estimated growth after inlined into all callees is +49 insns.
 Estimated badness is 16177, frequency 0.00.
 inline_failed:call is unlikely and code size would grow.

Considering ddx with 77 insns
 to be inlined into sw
 Estimated growth after inlined into all callees is +49 insns.
 Estimated badness is 16177, frequency 0.00.
 inline_failed:call is unlikely and code size would grow.

So I guess the question is why is this considered unlikely, given:
integer,parameter::             NSTEPS=6480
...
do istep=1,NSTEPS
    time = istep*dt

    ! ------ interior calculations ------ !

    dudx = ddx(u(:,:,mid))
    dvdy = ddy(v(:,:,mid))
    dhdx = ddx(h(:,:,mid))
    dhdy = ddy(h(:,:,mid))
...
end do


-- 

jakub at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |hubicka at gcc dot gnu dot
                   |                            |org
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2008-11-28 11:06:47
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=38074

[Bug middle-end/38074] [4.4 Regression] missed inlining since IRA merge on Core2 Duo

[rguenth at gcc dot gnu dot org]

------- Comment #5 from rguenth at gcc dot gnu dot org  2008-11-28 11:19 -------
Probably because the other doubly-nested loop bodies inside that loop are
considered way more hot.  Does using profile-feedback help?


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at gcc dot gnu dot
                   |                            |org


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=38074

[Bug middle-end/38074] [4.4 Regression] missed inlining since IRA merge on Core2 Duo

[jakub at gcc dot gnu dot org]

------- Comment #6 from jakub at gcc dot gnu dot org  2008-11-28 11:45 -------
All bb's in MAIN__ have frequency = 0, must be a bug in predict.c...


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=38074

[Bug middle-end/38074] [4.4 Regression] missed inlining since IRA merge on Core2 Duo

[jakub at gcc dot gnu dot org]

------- Comment #7 from jakub at gcc dot gnu dot org  2008-11-28 12:56 -------
One bug is IMHO in compute_call_stmt_bb_frequency, what it does doesn't make
any sense, as the condition in ?: is never true.
I guess
--- cgraphbuild.c.jj42008-10-23 13:21:39.000000000 +0200
+++ cgraphbuild.c2008-11-28 13:22:09.000000000 +0100
@@ -111,11 +111,12 @@ compute_call_stmt_bb_frequency (basic_bl
   int entry_freq = ENTRY_BLOCK_PTR->frequency;
   int freq;

+  if (!bb->frequency && !entry_freq)
+    return CGRAPH_FREQ_BASE;
+
   if (!entry_freq)
     entry_freq = 1;
-
-  freq = (!bb->frequency && !entry_freq ? CGRAPH_FREQ_BASE
-      : bb->frequency * CGRAPH_FREQ_BASE / entry_freq);
+  freq = bb->frequency * CGRAPH_FREQ_BASE / entry_freq;
   if (freq > CGRAPH_FREQ_MAX)
     freq = CGRAPH_FREQ_MAX;


was intended (as when entry_freq is 0, we don't know how many times more often
or less often bb is executed if it's frequency is 0).  Anyway, this doesn't
solve this, apparently I was wrong with all frequencies being 0.  entry block
has frequency 9, but the loop has frequency 0, which is definitely wrong.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=38074

[Bug middle-end/38074] [4.4 Regression] missed inlining on Core2 Duo due to apparent wrong branch prediction/profile

[rguenth at gcc dot gnu dot org]

------- Comment #8 from rguenth at gcc dot gnu dot org  2008-12-05 12:21 -------
Honza, can you have a look here?  I suspect the fortran decl issue prevent
proper profile distribution over the callgraph...


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=38074

[Bug middle-end/38074] [4.4 Regression] missed inlining on Core2 Duo due to apparent wrong branch prediction/profile

[hubicka at ucw dot cz]

------- Comment #9 from hubicka at ucw dot cz  2008-12-05 12:59 -------
Subject: Re:  [4.4 Regression] missed inlining on Core2 Duo due  to apparent
wrong branch prediction/profile

> Honza, can you have a look here?  I suspect the fortran decl issue prevent
Will do.  We however don't distribute profile over cgraph...  This looks
more like one of misguesses cases

Honza


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=38074

[Bug middle-end/38074] [4.4 Regression] missed inlining on Core2 Duo due to apparent wrong branch prediction/profile

[hubicka at gcc dot gnu dot org]

------- Comment #10 from hubicka at gcc dot gnu dot org  2008-12-05 17:08 -------
compute_call_stmt_bb_frequency test is indeed bit insane, but probably works in
practice.  I will fix this on pretty-ipa branch.
Looking at sw(__MAIN) just after profiling, profile is there and it is sort of
sane.

The reason for low probability of the internal loop being somewhat cold is
block
31 that is predicted via noreturn heuristics.
It looks like the code is leading to exit at error cases and to noreturn call
in common case that is confusing the predictors...

Block 31 starts with:
omega_178 = 6.28318530700000010824624041561037302017211914062e+0 /
period.151_177
v0 ={v} 1.0000000000000000555111512312
5782702118158340454e-1
dt_parm.51.common.filename ={v} &"channel.f90"[1]{lb: 1 sz: 1};

Perhaps if all paths through function leads to noreturn, one can disable the
heuristics... I will check if this works.

Honza


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=38074

[Bug middle-end/38074] [4.4 Regression] missed inlining on Core2 Duo due to apparent wrong branch prediction/profile

[hubicka at ucw dot cz]

------- Comment #11 from hubicka at ucw dot cz  2008-12-05 17:15 -------
Subject: Re:  [4.4 Regression] missed inlining on Core2 Duo due  to apparent
wrong branch prediction/profile

OK,
so the problem is that all the paths are leading to noreturn, so the
conditional deciding on what noreturn path will be taken is predictor by
same heuristic in both dirrections.
Our first math heuristic blindly picks the first one in row predicting
the "invalid command line parameters" path to be very likely and main
body to be very unlikely.

This patch fixes it in both ways: when all paths are leading to
noreturn, we disable the heuristics and when heuristics is taken
into consideration for first match we first check that it was not
confused and did not predict edge in both ways.

I also fixed nonsence in compute_call_stmt_bb_frequency noticed by
Jakub. To make frequencies at least little bit sane, I simply add 1 to
both values so we still get calls with higher frequency than 0 predicted
as more often.

Honza

        Jan Hubicka  <jh@suse.cz>
        Jakub Jelinek <jakub@redhat.com>
        * cgraphbuild.c (compute_call_stmt_bb_frequency): Fix handling of 0
        entry frequency.
        * predict.c (combine_predictions_for_bb): Ignore predictor predicting
        in both dirrection for first match heuristics.
        (tree_bb_level_predictions): Disable noreturn heuristic when there
        is no returning path.
Index: cgraphbuild.c
===================================================================
*** cgraphbuild.c       (revision 141929)
--- cgraphbuild.c       (working copy)
*************** int
*** 109,121 ****
  compute_call_stmt_bb_frequency (basic_block bb)
  {
    int entry_freq = ENTRY_BLOCK_PTR->frequency;
!   int freq;

    if (!entry_freq)
!     entry_freq = 1;

!   freq = (!bb->frequency && !entry_freq ? CGRAPH_FREQ_BASE
!             : bb->frequency * CGRAPH_FREQ_BASE / entry_freq);
    if (freq > CGRAPH_FREQ_MAX)
      freq = CGRAPH_FREQ_MAX;

--- 109,120 ----
  compute_call_stmt_bb_frequency (basic_block bb)
  {
    int entry_freq = ENTRY_BLOCK_PTR->frequency;
!   int freq = bb->frequency;

    if (!entry_freq)
!     entry_freq = 1, freq++;

!   freq = freq * CGRAPH_FREQ_BASE / entry_freq;
    if (freq > CGRAPH_FREQ_MAX)
      freq = CGRAPH_FREQ_MAX;

Index: predict.c
===================================================================
*** predict.c   (revision 141929)
--- predict.c   (working copy)
*************** combine_predictions_for_bb (basic_block 
*** 820,827 ****
            probability = REG_BR_PROB_BASE - probability;

          found = true;
          if (best_predictor > predictor)
!           best_probability = probability, best_predictor = predictor;

          d = (combined_probability * probability
               + (REG_BR_PROB_BASE - combined_probability)
--- 820,852 ----
            probability = REG_BR_PROB_BASE - probability;

          found = true;
+         /* First match heuristics would be widly confused if we predicted
+            both directions.  */
          if (best_predictor > predictor)
!           {
!               struct edge_prediction *pred2;
!             int prob = probability;
! 
!               for (pred2 = (struct edge_prediction *) *preds; pred2; pred2 =
pred2->ep_next)
!              if (pred2 != pred && pred2->ep_predictor == pred->ep_predictor)
!                {
!                  int probability2 = pred->ep_probability;
! 
!                  if (pred2->ep_edge != first)
!                    probability2 = REG_BR_PROB_BASE - probability2;
! 
!                  if ((probability < REG_BR_PROB_BASE / 2) != 
!                      (probability2 < REG_BR_PROB_BASE / 2))
!                    break;
! 
!                  /* If the same predictor later gave better result, go for
it! */
!                  if ((probability >= REG_BR_PROB_BASE / 2 && (probability2 >
probability))
!                      || (probability <= REG_BR_PROB_BASE / 2 && (probability2
< probability)))
!                    prob = probability2;
!                }
!             if (!pred2)
!               best_probability = prob, best_predictor = predictor;
!           }

          d = (combined_probability * probability
               + (REG_BR_PROB_BASE - combined_probability)
*************** static void
*** 1521,1526 ****
--- 1546,1561 ----
  tree_bb_level_predictions (void)
  {
    basic_block bb;
+   bool has_return_edges = false;
+   edge e;
+   edge_iterator ei;
+ 
+   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
+     if (!(e->flags & (EDGE_ABNORMAL | EDGE_FAKE | EDGE_EH)))
+       {
+         has_return_edges = true;
+       break;
+       }

    apply_return_prediction ();

*************** tree_bb_level_predictions (void)
*** 1535,1541 ****

          if (is_gimple_call (stmt))
            {
!             if (gimple_call_flags (stmt) & ECF_NORETURN)
                predict_paths_leading_to (bb, PRED_NORETURN,
                                          NOT_TAKEN);
              decl = gimple_call_fndecl (stmt);
--- 1570,1577 ----

          if (is_gimple_call (stmt))
            {
!             if ((gimple_call_flags (stmt) & ECF_NORETURN)
!                 && has_return_edges)
                predict_paths_leading_to (bb, PRED_NORETURN,
                                          NOT_TAKEN);
              decl = gimple_call_fndecl (stmt);


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=38074

[Bug middle-end/38074] [4.4 Regression] missed inlining on Core2 Duo due to apparent wrong branch prediction/profile

[hubicka at gcc dot gnu dot org]

------- Comment #12 from hubicka at gcc dot gnu dot org  2008-12-06 08:35 -------
Subject: Bug 38074

Author: hubicka
Date: Sat Dec  6 08:34:20 2008
New Revision: 142517

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=142517
Log:

        PR tree-optimization/38074
        * cgraphbuild.c (compute_call_stmt_bb_frequency): Fix handling of 0
        entry frequency.
        * predict.c (combine_predictions_for_bb): Ignore predictor predicting
        in both dirrection for first match heuristics.
        (tree_bb_level_predictions): Disable noreturn heuristic when there
        is no returning path.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/cgraphbuild.c
    trunk/gcc/predict.c


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=38074

[Bug middle-end/38074] [4.4 Regression] missed inlining on Core2 Duo due to apparent wrong branch prediction/profile

[jakub at gcc dot gnu dot org]

------- Comment #13 from jakub at gcc dot gnu dot org  2008-12-06 08:59 -------
Fixed, thanks.


-- 

jakub at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=38074