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. Regards -Ghassan On Tue, 10 Feb 2004, Jan Hubicka wrote: > > Vladimir Makarov wrote: > > > > >Ghassan Shobaki wrote: > > > > > >>Are there any documents describing the algorithm used in the > > >>superblock instruction scheduler? > > >> > > >I don't know one. > > > > > >>Does it use any (or a combination of) of published techniques such as > > >>critical path and speculative hedge and successive retirement ..etc? > > >>Or it just has its own algorithm? > > >> > > >> > > >> > > >It uses own algorithm which was grown from original haifa-scheduler. > > >Earlier it was one file which was divided. Superblock scheduler uses > > >code of sched-deps.c and haifa-sched.c and directs them through a few > > >hooks. > > > > > >Generally speaking suberblock is believed to be a basic block to which > > >list scheduling is applied. The superblock scheduler just checks that > > >the insn can be issued speculatively and prefer to issue more > > >frequently executed insns when the priority is the same (and now when > > >insn register weights are the same). But calculation of insn > > >priorities does not take basic block frequencies (or belonging to > > >different basic blocks) into account. So the algorithm is very simple. > > > > > >No more advanced approaches like heuristics based on critical path to > > >the last exit of superblock, dependence height and speculative yeild > > >(taking block excution probability into account when the insn priority > > >is calculated), sucessive retirment (preference of non-speculative > > >insn movement first), or speculative hedge aiming to achieve minimal > > >delay to all exits are used. > > > > > >So there are a lot of things to improve the code. But it will be not > > >easy to add them because big part of code is used by the region based > > >scheduler too. > > > > Sorry, I forgot too add that what I wrote is about extended basic block > > scheduler (file sched-ebb.c) which is used for Itanium as a default > > after the register allocation. If you are intersting in Jan Hubicka's > > trace scheduler, I think that Jan's answer will be more competent. > > I really didn't changed much in the algorithm. All I was interested in > was to make it work with CFG and plugged in the tail duplication pass. > So your description is still valid. > The code has little logic to avoid moving instructions too much up and > adding some extra heuristics shall not be that dificult, but I didn't > read the papers on topic very curefully :) > > > Honza > > > > Vlad > > >
