Re: DFA lookahead confusion

[Vladimir Makarov <vmakarov at redhat dot com>]

Paul Koning wrote:
> 
> Excerpt of message (sent 14 May 2002) by David S. Miller:
> >
> > 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.
> 
> The way I interpreted it is that the "right" value is the issue width
> times the longest latency you want to deal with.  So, for example, in
> a MIPS processor I was trying this stuff out on, I set it to 16 --
> quad issue times 4 tick longest latency.  (I was ignoring Divide
> here...)
> 
> It did seem a bit cryptic, though.

  Yes, that is right.  It is not easy to describe what the parameter
means.  The goal of usage of the parameter is to constrain number of
queue permutation tries.  Generally speaking, the value bigger than
queue size will never give the improvement.  Maximal queue size is
depended on program not on processor characteristics.   I just
recommended to use it equal to maximal processor insn issues per clock
as a compromise between the code improvement and compilation time   But
it is only heuristic.  On my estimation the complexity of algorithm of
choosing an insn from the queue is O (lookahead ** processor width) if
queue size >> lookeahead or O (qs * (qs -1) * (qs-2) ...) if queue size
< lookahead where the number of multiplication is equal to the processor
width and qs is the queue size.

I think may be it is worth to define a machine independent `-f...'
option or recommend the description writer to define a machine dependent
option.  Just an idea.

Vlad