Re: [PATCH] Improve scheduling at the end of basic blocks

[Maxim Kuvyrkov <maxim at codesourcery dot com>]

Vladimir Makarov wrote:
> Maxim Kuvyrkov wrote:
> >  
> >
> > The first attached patch improves scheduling at the end of basic 
> > blocks by making scheduler take into account the fact that some 
> > instructions force end of the cycle (the last instruction of a basic 
> > blocks being the most common case).
> >
> > OK for trunk?
>
>  Maxim, sorry for the delay with the review.  The changes were so not
> obvious to me that it took some time to investigate them.
>
>  As for the first patch.  I added abort before 'return true' in
> sched-rgn::rgn_insn_finishes_block_p and I've never get abort on
> compilation of big set of programs (about 1M lines of C) on ppc64.
> The reason is in that schedule_more_p already checks this before
> max_issue.  So the patch is useless.

Well, funny thing, the patch is *not* useless for everything /except for 
PPC/.  The reason it is a nop on PPC is because of setting issue_rate to 
1 during first scheduling pass to <quote>decrease degradation</quote>. 
I've checked and none of the other important architectures use this trick.

A bit of background.  The patch was originally written to fix 
performance regression on one of the MIPS processors.  As I remember, 
there the generic pipeline model and the issue rate of *1* produced 
better code then a rather accurate model of the particular processor 
with the issue rate of 4.

The problem turned out to be in max_issue() assigning equal goodness to 
the both following solutions:

Solution1:

insn1 // last in basic block
<bb end>
insn2 // can be scheduled at the same cycle as insn1

Solution2:

insn2 // is scheduled at the same cycle as insn1
insn1 // ends basic block
<bb end>


In Solution1 max_issue decides to issue insn1 and then, on the same 
cycle, issue insn2.  But due to schedule_more_p returning 'false' after 
insn1 was scheduled, this doesn't happen.

The patch fixes this and max_issue will no longer be lead to believe 
that the instructions will be scheduled on the same cycle when, in 
reality, they don't.

Returning to PPC, I wonder why issue_rate was set to 1 for the first 
scheduling pass.  Heck, maybe it was [at least in part] due to this very 
issue.  If anyone having a benchmark PPC box is interested, it may be 
educating to remove the setting of issue rate to 1 before reload and run 
 some tests with this patch applied.


>  As for the second patch, you incorrectly understand df_look_ahead.
> It is just a constraint to the local search being done.  Comments to
> max_lookahead_tries say about this constraint by defining worst
> algorithm complexity.  Probably because you did not correctly
> understand the parameter meaning.

I was suspecting that I was missing something about dfa_lookahead.  I 
still have several question about it (particularly, why search is not 
terminated on state_dead_lock_p), but I need some time to absorb your 
comments.  In any case, I agree that increasing scheduling time is 
certainly wrong.

--
Maxim