Superblock Scheduling Alg in GCC

[Vladimir Makarov]

Ghassan Shobaki wrote:

>Guys,
>
>I have done some experiments on two different heuristics for superblock 
>scheduling by comparing them with optimal scheduling. The two heuristics 
>are simple critical path CP (priority is the CP from the last branch only) 
>and weighted critical path WCP (priority is a weighted sum of critical pahts 
>from all branches below an instruction, with the branch weight being the 
>probability of exiting the superblock at that branch). On the simple 
>machine model that I am using, I got the following results: 
>
>fp2000 benchmark: CP is optimal on 72% of the superblocks and WCP is 
>optimal on 84% of the superblocks
>
>int2000 benchmark: CP is optimal on 83% of the superblocks and WCP is 
>optimal on 94% of the superblocks
>
>These numbers do not necessarily reflect actual run-time performance 
>improvements, since they were collected in a standalone setup were 
>superblock data dependence graphs were extracted from gcc and scheduled
>separately for a simple machine model (dual issue in which one int and one 
>fp instruction can issue in each cycle). However, these results 
>do suggest that the WCP heuristic is significantly better than the simple CP.
>
>The reference for the WCP heuristic is:
>R. Bringmann, Compiler-Controlled Speculation, PHD thesis, Dept. of CS, 
>UIUC, IL 1995. (where the technique is called Dependence Height and 
>Speculative Yield DHASY).
>
>However, you don't really need to go there since the heuristic itself is 
>so simple and intuitive that my description above is almost sufficient. 
>Let me know if you are interested and I'll give you the details and 
>explain one particular subtility about it.
>
>  
>
Yes, I am interesting in this.  Could you give me the reference to WCP 
details (I can not find the document on the Internet).   I could give it 
a try.  May be this approach will work.

Vlad