Re: The DFA based scheduler.

[Vladimir Makarov <vmakarov at redhat dot com>]

Naveen Sharma wrote:
> 
> Hi,
> 
> I have been interested by the discussion on the new DFA based scheduler
> developed by you for gcc.I plan to study the implementation of the
> scheduler and would like to contribute further for the scheduler.
> My friend,Nitin Gupta,would  be joining me in the effort.
> At present we are interested in using the DFA based scheduler
> for SH4 target which might benefit from the new scheduler.
> 
> It would be helpful if you can answer some initial queries.
> 
> 1. What targets are tested till now &
>    What improvements in generated code were noticed?

  There are a lot of descriptions tested in RedHat (mips, powerpc, a
Fujitsu VLIW processor, even IA64).  They were tested for the
correctness of the DFA-based scheduler work mainly.

  I've seen some improvements for the Fujistu VLIW processor.  The dfa
based scheduler is used to solve VLIW insn packing too with the aid of
the code for multipass insn scheduling (see hook
TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DFA_LOOKAHEAD).

  I don't know about improvements for mips.  Probably there are no
improvement.  David Edelsohn reported that there is no improvement for
powerpc too.  As for IA64, I've seen improvement about 0.4-0.5% for all
SPECInt95  (although some SPECInt95 tests had degradation).  The DFA
based scheduler for IA64 was complicated and buggy (I had few time for
this).  May be the result can be improved (if the degradation of some
SPECint95 tests is eliminated).

  Because the current scheduler highest priority is the longest critical
path, description of the correct latency times of insns have the biggest
impact on the results.  The current processors also have less functional
unit irregularity than earlier ones.  So I'd not expect big effect of
the the current DFA based scheduler usage.

  As I already wrote the DFA based pipeline hazard recognizer is more
infrastructure for a better insn scheduler when you can try easily more
insn schedules for the same time to choose the best one.  Scheduler
algorithms are heuristic ones.  They were designed long ago.  Now modern
computers permit to try not single insn schedule but several ones.  The
heuristics are not perfect.  let us look at the problem reported by
Geoffrey Keating for powerpc 750.  There is a big basic block of of
pairs independent insns

I S  I S  I S ...

where I is an integer insn and S is store insn which writes the result
of the integer insns.   The current scheduler based on the longest
critical path as the most important heuristic will generate

I I   I I   I I  I I ...  S  S  S  S ...

Powerpc 750 has two integer units and one store unit.  So two integer
insns and one store can be issued per cycle and the last insn will be
started at time 1.5 * N where N is number of the pair.  But there is a
better insn schedule

I I   S I   S I   S I    ...  S I    S

with the last insn issued on N + 1 cycle.


The DFA based pipeline hazard recognizer is an important part of
resource constrained software pipelining where there are many searches
for and comparisons of all current and predicted functional unit
reservations.  The DFA approach is much faster and convenient.

  I am going to add RCSP to the branch.  David Edelsohn is also
frustrated about there is no improvement in usage of RCSP for powerpc. 
The current RCSP implementation is very constrained and many efforts to
improve it is still necessary.  I've wrote what to do in the RCSP
sources comments.

> 2. What sort of tests were chosen to confirm the results?
> 

For the Fujitsu VLIW processor that was small tests (sorting, matrix
multiplication) provided by Fujitsu.  These tests are typical for
embedded applications.

> Hope to have lot of information exchange in future.
>