Progress in instruction scheduling?

Hi,

the compiler optimization "instruction scheduling" is a quite old
technique that can be found in many modern compilers. From some
standard compiler books, I got to know that many schedulers are based
on "list scheduling" which seems to be the standard approach. An
advanced approach based on profiling is "trace scheduling".

I would like to hear your opinion if there is/was any progress in the
last years concerning instruction scheduling leading to more advanced
techniques now considered to be standard or if scheduling based on
list scheduling is still state-of-the with no major deviations?

The reason I'm asking is that I want to write a master's thesis about
instruction scheduling for a research compiler. The compiler is for an
TI DSP which has two pipelines (integer and load/store pipeline) and
I'm looking for some challenges that should go beyond the standard
approaches which can be found in standard compiler books and thus
easily adapted. So, any advices are appreciated.

Regards,
Christian

There is some recent work on optimal scheduling which compares with
the list scheduling heuristic.  The problem is that the list scheduler
is very close to optimal and much faster than the optimal one.

Abid M. Malik, Jim McInnes, and Peter van B. Optimal basic block
instruction scheduling for multiple-issue processors using constraint
programming. Proceedings of the 18th IEEE International Conference on
Tools with Artificial Intelligence,  Washington, DC, 279-287,
November, 2006. A longer version appears in the International J. of AI
Tools, 17:37-54, 2008.

> Abid M. Malik, Jim McInnes, and Peter van B. Optimal basic block
> instruction scheduling for multiple-issue processors using constraint
> programming. Proceedings of the 18th IEEE International Conference on
> Tools with Artificial Intelligence,  Washington, DC, 279-287,
> November, 2006.

http://www.cs.uwaterloo.ca/research.../CS-2005-19.pdf

--
Ivan Boldyrev

Signature is under construction.