Re: DFA lookahead confusion

["Vladimir N. Makarov" <vmakarov at redhat dot com>]

> 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.

   That is right, Jeff.  The algorithm guarantees that the highest priority insn
will be issued on the current cycle (may be not the first on the cycle).  On the
other hand, it tries to maximize number of issued insns on the cycle.  So the next
priority insn might be not issued on the same cycle even if it could be issued with
the highest priority insn (but in this case the next priority insn will be issued on
the next cycle).

  Because the algorithm looks only at the current cycle, it is more important for
VLIW processors.  It is well known that taking VLIW packing into account results in
better insn scheduling (e.g. IA64 gcc port does this).  VLIW packing concerns only
about one cycle.

  So the algorithm is a compromise between heuristics based on critical path length
and ones based on maximal issued insns per cycle.  Both of them does not work well
separately in many cases (e.g. it is  mentioned in Muchnik's book).  If I were a
researcher, I could make a comparison of three algorithms and write a report.  But I
have no time for this.

 Actually, I look at the algorithm as an intermediate step to the algorithm making
optimal (or close to optimal) insn scheduling.

Vlad