Re: DFA lookahead confusion

[law at redhat dot com]

In message <20020514.211327.04690352.davem@redhat.com>, "David S. Miller" writes:
 > 
 > Reading the documentation for target hook:
 > 
 > TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DFA_LOOKAHEAD
 > 
 > I have a hard time coming to conclusions :-)
 > 
 > Alpha and Pentium are using a value that seems to be dependant upon
 > the width of the processor.
 > 
 > However, as I read the documentation there is no direct correlation
 > between width of the processor and the value to use for DFA lookahead.
 > Even if processor width is 2 (as on some Alpha's) you can still get
 > better schedules when using larger values for DFA lookahead.
 > 
 > For example, consider a ready list ordered like this:
 > 
 > 	INT_OP0
 > 	INT_OP1
 > 	INT_OP2
 > 	INT_OP3
 > 	FPU_OP0
 > 	FPU_OP1	/* inputs depend upon retults of FPU_OP0 */
 > 	FPU_OP2 /* inputs depend upon retults of FPU_OP1 */
 > 	FPU_OP3 /* inputs depend upon retults of FPU_OP2 */
 > 
 > Let us assume that processor may execute 2 instructions per cycle,
 > there are two INT units and 1 FPU units, plus FPU latency is 1 cycle
 > (yes I know this processor is stupidly designed, it's just for example
 > purposes :-)
It's not that stupid -- the PA7100LC has similar characteristics.   It can
dual-issue most integer instructions, or integer+fp but it can't dual-issue
two FP instructions.

Anyway, if this is how the ready list is sorted, then something is
dreadfully wrong :-)  FPU_OP1, FPU_OP2, and FPU_OP3 can't be in the
ready list yet as their dependencies have not been resolved.   So let's
pretend they're not in the ready list yet, but will be added at the
appropriate time.

The ordering you've given indicates that from the standpoint of optimizing
total latency on the critical path that the integer operations are
more important than the FPU operations.  This is critical to keep in
mind.  If the FPU ops were that important to the critical path, then
they would have a higher priority than the integer instructions.  So
delaying those integer instructions too long probably doesn't make
a lot of sense as it lengthens the critical path.


Additionally the lookahead code, as best as I understand it, is designed
to try and maximize issue bandwidth for the current cycle guaranteeing
that the highest priority instruction fires.  It does not try to maximize
issue bandwidth across cycles.

I've toyed in the past with biasing the priorities and the like based
on stuff like issue characteristics to deal with stuff like having dual
ALUs, but a single FPU.  I never came up with anything that I could consider
good.

You might be able to do something with instruction replacement using
the DFA and reverse DFA.  With a simple replacement model you could
probably get

  INT_OP0, INT_OP1
  INT_OP2, FP_OP0
  INT_OP3, FP_OP1
  FP_OP2
  FP_OP3

Still not what you wanted, but better from an issue standpoint.

 > Optimal schedule would be something like:
 > 
 > 	INT_OP0
 > 	FPU_OP0
 > 	INT_OP1
 > 	FPU_OP1	/* inputs depend upon retults of FPU_OP0 */
 > 	INT_OP2
 > 	FPU_OP2 /* inputs depend upon retults of FPU_OP1 */
 > 	INT_OP3
 > 	FPU_OP3 /* inputs depend upon retults of FPU_OP2 */
 > 
 > The documentation suggests that if DFA lookahead is set to
 > non-positive value the scheduler will begin executing like this:
Not if those integer ops were more important to fire than the
FP ops (as your sorted ready list indicated).   Your schedule
maximizes issue bandwidth at the expense of delaying 3 of the
integer insns (which are higher priority according to your
ready list).

 > The same language is used in the x86 Pentium implementation.
Simply because I copied it from the Alpha.

Jeff