This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: First scheduling pass
Richard Henderson wrote:
>
> On Thu, Mar 27, 2003 at 03:27:41PM +0530, Sanjiv Kumar Gupta, Noida wrote:
> > I plan to re-enable the scheduling *before* register allocation for
> > SH4. IMO, the number of spills can be reduced by applying some good
> > heuristic(s) to reorder the ready queue. Any ideas for a good solution?
>
> A new scheduler. There are lots of papers on this. A partial list:
>
> J. R. Goodman and W.-C. Hsu. Code Scheduling and Register Allocation
> in Large Basic Blocks. In Proc. of the 2nd International Conference
> on Supercomputing, pages 442╜452, 1988.
>
> R. Govindarajan, H. Yang, C. Zhang, and G. R. Gao. Minimum Register
> Instruction Sequence Problem: Revisiting Optimal Code Generation for
> DAGs. In Proc. of International Parallel and Distributed Processing
> Symposium, Apr. 2001.
>
It is very complicated method with unjustified results. Measurements are
made on simulators which are far away from real life.
That is a typical university research article which always states that
their approach is the greatest one. The goal of such researches is a
publication. The typical receipt of such researches is mix of well
known algorithms (like graph colouring and list insn scheduling). The
more publications, the better.
> T. Inagaki, H. Komatsu, and T. Nakatani. Integrated Prepass Scheduling
> for a Java Just-In-Time Compiler on the IA-64 Architecture. In Proc.
> of The International Symposium on Code Generation and Optimization,
> Mar. 2003.
>
That is article more interesting (personally i like backtracking) and
the method is implemented for a real processor. But they states 0.4%
improvement (with my point of view it is in measurement error range) in
comparison with the Govindarajan's method.
> The last paper I saw presented on Monday (and is where I got the other
> references from); it doesn't really have anything to do with Java or
> IA-64. One hope is that since the algorithm is intended for a JIT,
> it might be fast enough for use in a real compiler.
>
> In any case, these papers (or ones they reference) may be a good place
> to get ideas.
>
In whole, the methods are complicated and moreover they were implemented
only for BB. I think Morgan's approach (a limit pass before the 1st
register allocation) is more engineering approach. With my point of view
they goes in wrong direction (requiring 2 passes of insn scheduling). I
already wrote this in
http://gcc.gnu.org/ml/gcc-patches/2003-03/msg00248.html
Vlad