From: Vladimir Makarov <vmakarov@redhat.com>
To: Ghassan Shobaki <gshobaki@ece.ucdavis.edu>
Cc: Jan Hubicka <jh@suse.cz>, Jan Hubicka <hubicka@ucw.cz>,
gcc-help@gcc.gnu.org, gcc@gnu.org
Subject: Re: Superblock Scheduling Alg in GCC
Date: Tue, 10 Feb 2004 20:08:00 -0000 [thread overview]
Message-ID: <40293A4D.5060502@redhat.com> (raw)
In-Reply-To: <Pine.LNX.4.58.0402101010420.9430@hawking.ece.ucdavis.edu>
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.
Vlad.
next prev parent reply other threads:[~2004-02-10 20:08 UTC|newest]
Thread overview: 33+ messages / expand[flat|nested] mbox.gz Atom feed top
2003-12-03 6:14 Superblock Instruction Scheduling " Ghassan Shobaki
2003-12-03 14:03 ` Vladimir N. Makarov
2003-12-04 0:06 ` Jan Hubicka
2003-12-04 1:26 ` Ghassan Shobaki
2003-12-04 10:25 ` Jan Hubicka
2003-12-04 15:54 ` Vladimir Makarov
2003-12-09 21:11 ` Ghassan Shobaki
2004-01-28 1:31 ` Superblock Instruction Scheduling in GCC 3.4 Ghassan Shobaki
2004-01-28 12:23 ` Jan Hubicka
2004-01-29 7:07 ` Ghassan Shobaki
2004-01-29 10:13 ` Jan Hubicka
2004-02-01 18:17 ` Ghassan Shobaki
2004-02-01 21:55 ` Jan Hubicka
2004-02-02 5:52 ` Ghassan Shobaki
2004-02-10 18:57 ` Superblock Scheduling Alg in GCC Ghassan Shobaki
2004-02-10 20:08 ` Vladimir Makarov [this message]
2004-02-10 20:17 ` Vladimir Makarov
2004-02-10 20:27 ` Jan Hubicka
2004-04-14 17:03 ` Ghassan Shobaki
2004-04-14 22:44 ` Vladimir Makarov
[not found] ` <Pine.LNX.4.58.0404142056120.4634@hawking.ece.ucdavis.edu>
2004-04-17 19:29 ` Ghassan Shobaki
2004-05-27 6:41 ` Ghassan Shobaki
2004-05-27 10:06 ` Tree-SSA: Grammer Sumit Jain
2004-05-27 12:56 ` llewelly
2005-02-11 16:55 ` Trace Scheduling in GCC Ghassan Shobaki
[not found] ` <4210D6C0.3030005@redhat.com>
2005-02-15 6:30 ` Vladimir Makarov
2006-11-24 18:42 ` Phase Ordering of Scheduling and Allocation " Ghassan Shobaki
2006-11-24 19:28 ` Vladimir N. Makarov
2005-02-15 7:45 ` Trace Scheduling " Jan Hubicka
2005-02-15 9:18 ` Ghassan Shobaki
2005-02-17 16:19 ` Jan Hubicka
2005-02-16 10:40 ` Vladimir Makarov
[not found] ` <Pine.GHP.4.58.0502150840080.14429@dante.ece.ucdavis.edu>
2005-02-16 11:19 ` Jan Hubicka
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=40293A4D.5060502@redhat.com \
--to=vmakarov@redhat.com \
--cc=gcc-help@gcc.gnu.org \
--cc=gcc@gnu.org \
--cc=gshobaki@ece.ucdavis.edu \
--cc=hubicka@ucw.cz \
--cc=jh@suse.cz \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).