[GSoC] New static scheduler priority. Final status.

[Zhurichin Dmitry <zhur at ispras dot ru>]

Hi!  This is a final status update for my GSoC 2007 project.  The 
following patches contain code that implements two new approaches to 
static priority for Haifa scheduler.  

First approach is the speculative yield heuristic.  In details it is 
desribed in the article "Enhancing Intruction Level Parallelism through 
Compiler-Controlled Speculation" by R.A.Bringmann, PhD thesis, 1995 (see 
chapter 3.4.2) [ http://citeseer.ist.psu.edu/bringmann95enhancing.html ].  
Briefly, first critical path values to each of exits from current 
scheduling domain (region or EBB) are computed for each instruction in 
this domain.  Then priority is set to sum over all exits of this value 
multiplied by probability of taking corresponding exit.  This means that 
instruction which is earlier in path to an exit is prioritized over 
instruction which is later on this path; similarly, instruction which is 
on path to more probable exit is prioritized over instruction from 
path to less probable exit; and, instruction from many paths to different 
exits can be prioritized over instruction from lesser number of paths to 
some of those exits. 
This approach can be used when scheduling is done on regions as well as 
on EBBs.

Second approach is the G* heuristic, described in the article "Profile- 
Driven Instruction Level Parallel Scheduling with Application to Super 
Blocks" by C.Chekuri et al
[ http://citeseer.ist.psu.edu/chekuri96profiledriven.html ].  In few 
words, scheduling domain is split into several non-overlapping subsets, 
each of them being a subgraph of data dependence graph for 
scheduling domain rooted at some exit from this domain.  Such 
distribution is done iteratively, choosing on each iteration exit with 
best computational time required per unit of exit probability (i.e.  
exit with minimal ratio of time needed to issue this exit to sum of 
probabilities of all exits, including current, that are on paths leading 
to current exit).  Then all instructions, on which the chosen exit is 
dependent, are excluded from consideration, and procedure is repeated 
until each instruction was distributed into some subset.  After such order 
of subsets was created, each instruction is given a priority that is 
greater than priorities of instructions from previous subsets and lesser 
than priorities of instructions from the following subsets, and inside the 
same subset priority of instruction is calculated as critical path value 
to the last exit from the subset.
This approach is now working only on EBBs, but my future plans are to 
try make it work on regions too.

Attached patches are following: patch 0 contains all code in one file 
(other patches are additional in the sense that they are just for easier 
understanding of changes); patch 1 contains new flags for turning on 
or off those new features; patches 2 and 3 are context diffs and contain 
modified parts of scheduler drivers in sched-ebb.c and sched-rgn.c;   
patch 4 holds changes to sched-int.h; remaining patches contain diffs to 
haifa-sched.c, patch 5 being a context diff of function priority, patch 6 
being a common functions of both new approaches for finding exits from 
scheduling domain and debug and also contains speculative yield part of 
the project; the last patch is a G* heuristic implementation.

Patched version of GCC trunk bootstraps and passes check successfully, 
compiles SPEC CPU2000 on ia64, but unfortunately gives no significant 
improvements to performance.  My guess is that with such number of 
processor units, scheduling priority plays secondary factor.  Though I 
have not got enough time to study results thoroughly and plan to look at 
why new priorities do not give improvements on ia64 some time later.  In 
this context, I will appreciate much if someone can test my patches on 
some other platforms (where scheduler plays an important role).  Any other 
comments are welcome too.  Thanks!

Dmitry Zhurikhin

Attachment: 0.all.patch
Description: Text document

Attachment: 1.new-flags.patch
Description: Text document

Attachment: 2.ebb.patch
Description: Text document

Attachment: 3.rgn.patch
Description: Text document

Attachment: 4.header.patch
Description: Text document

Attachment: 5.priority.patch
Description: Text document

Attachment: 6.spec-yield.patch
Description: Text document

Attachment: 7.g-star.patch
Description: Text document