From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 20697 invoked by alias); 10 Feb 2004 20:10:39 -0000 Mailing-List: contact gcc-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Archive: List-Post: List-Help: Sender: gcc-owner@gcc.gnu.org Received: (qmail 20682 invoked from network); 10 Feb 2004 20:10:38 -0000 Received: from unknown (HELO fencepost.gnu.org) (199.232.76.164) by sources.redhat.com with SMTP; 10 Feb 2004 20:10:38 -0000 Received: from monty-python.gnu.org ([199.232.76.173]) by fencepost.gnu.org with esmtp (Exim 4.24) id 1AqeB4-000625-0l for gcc@gnu.org; Tue, 10 Feb 2004 15:08:14 -0500 Received: from mail by monty-python.gnu.org with spam-scanned (Exim 4.24) id 1AqeBb-0004t0-OU for gcc@gnu.org; Tue, 10 Feb 2004 15:09:18 -0500 Received: from [66.187.233.31] (helo=mx1.redhat.com) by monty-python.gnu.org with esmtp (Exim 4.24) id 1AqeBb-0004s2-FY for gcc@gnu.org; Tue, 10 Feb 2004 15:08:47 -0500 Received: from int-mx1.corp.redhat.com (int-mx1.corp.redhat.com [172.16.52.254]) by mx1.redhat.com (8.11.6/8.11.6) with ESMTP id i1AK8Xb08984; Tue, 10 Feb 2004 15:08:33 -0500 Received: from pobox.toronto.redhat.com (pobox.toronto.redhat.com [172.16.14.4]) by int-mx1.corp.redhat.com (8.11.6/8.11.6) with ESMTP id i1AK8Xi22609; Tue, 10 Feb 2004 15:08:33 -0500 Received: from redhat.com (torque.toronto.redhat.com [172.16.14.46]) by pobox.toronto.redhat.com (8.12.8/8.12.8) with ESMTP id i1AK8VXd010624; Tue, 10 Feb 2004 15:08:31 -0500 Message-ID: <40293A4D.5060502@redhat.com> Date: Tue, 10 Feb 2004 20:10:00 -0000 From: Vladimir Makarov User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.2.1) Gecko/20030225 MIME-Version: 1.0 To: Ghassan Shobaki CC: Jan Hubicka , Jan Hubicka , gcc-help@gcc.gnu.org, gcc@gnu.org Subject: Re: Superblock Scheduling Alg in GCC References: <3FCDEE2C.19E04DE3@redhat.com> <20031204000558.GD23084@atrey.karlin.mff.cuni.cz> <20040128122317.GI8094@kam.mff.cuni.cz> <20040129101203.GB30883@atrey.karlin.mff.cuni.cz> <20040201215520.GI30324@kam.mff.cuni.cz> In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Status: No, hits=-2.1 required=5.0 tests=EMAIL_ATTRIBUTION,IN_REP_TO,REFERENCES,REPLY_WITH_QUOTES, USER_AGENT_MOZILLA_UA,X_ACCEPT_LANG version=2.55 X-Spam-Level: X-Spam-Checker-Version: SpamAssassin 2.55 (1.174.2.19-2003-05-19-exp) X-SW-Source: 2004-02/txt/msg00624.txt.bz2 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.