Re: First scheduling pass

[Richard Henderson <rth at redhat dot com>]

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.

    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.

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.


r~