This is the mail archive of the
mailing list for the GCC project.
Re: Combined top-down and bottom-up instruction scheduler
- From: Sebastian Pop <sebpop at gmail dot com>
- To: Segher Boessenkool <segher at kernel dot crashing dot org>
- Cc: Aditya K <hiraditya at msn dot com>, "gcc at gcc dot gnu dot org" <gcc at gcc dot gnu dot org>, "vmakarov at redhat dot com" <vmakarov at redhat dot com>, "law at redhat dot com" <law at redhat dot com>
- Date: Tue, 8 Sep 2015 19:24:23 +0000
- Subject: Re: Combined top-down and bottom-up instruction scheduler
- Authentication-results: sourceware.org; auth=none
- References: <BLU179-W6188AF5C5B442B4282F2F0B6530 at phx dot gbl> <20150908184823 dot GA12480 at gate dot crashing dot org>
Segher Boessenkool wrote:
> On Tue, Sep 08, 2015 at 06:39:19PM +0000, Aditya K wrote:
> > IIUC, in the haifa-sched.c, the default scheduling algorithm seems to be top-down (before reload).
> > Is there a way to schedule the other way (bottom up), or both ways?
> > As a use case for bottom-up or some other heuristic:
> > Currently, the first priority in the selection is given to the longest path, in some cases this may produce code with stalls at the end of the basic block. Whereas in the case of combined top-down + bottom-up scheduling we would end up having stalls in the middle of the basic block.
> Why would that be better?
Top-down scheduling does a good job at the beginning of a basic block.
Bottom-up does a good job at the end of a basic block and then a poor job at the
beginning of the basic block.
When you combine the two (like in the swing scheduler, schedule one insn at the
top, then one insn at the bottom, and alternate), the result is good code at the
top, good code at the bottom, and in the middle you may have some poor code.
We have seen an example where GCC does a poor job at scheduling at the end of a
block, and we do not have a way to improve the situation, because we don't have
enough insns outside the critical path to be scheduled towards the end of the bb.