From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 26107 invoked by alias); 23 Nov 2005 20:43:26 -0000 Received: (qmail 26097 invoked by uid 22791); 23 Nov 2005 20:43:25 -0000 X-Spam-Check-By: sourceware.org Received: from yosemite.airs.com (HELO yosemite.airs.com) (205.217.158.180) by sourceware.org (qpsmtpd/0.31) with SMTP; Wed, 23 Nov 2005 20:43:24 +0000 Received: (qmail 18101 invoked by uid 10); 23 Nov 2005 20:43:23 -0000 Received: (qmail 17725 invoked by uid 500); 23 Nov 2005 20:43:14 -0000 To: Andrew MacLeod Cc: gcc mailing list Subject: Re: Register Allocation References: <1132246411.10098.153.camel@localhost.localdomain> <1132765629.28830.195.camel@localhost.localdomain> From: Ian Lance Taylor Date: Wed, 23 Nov 2005 20:43:00 -0000 In-Reply-To: <1132765629.28830.195.camel@localhost.localdomain> Message-ID: User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.4 MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-IsSubscribed: yes 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 X-SW-Source: 2005-11/txt/msg01163.txt.bz2 Andrew MacLeod writes: > > The current reload pass includes general heuristics to handle > > reloading memory addresses. This code knows things like "if stack > > pointer plus displacement is not a valid memory address, try loading > > the displacement into a register." Many targets currently rely on > > those heuristics to generate valid code. I haven't been able to quite > > pin down where this happens in your proposal. For example, it's easy > > for an address to use the frame pointer and be valid before reload, > > and then for reload to eliminate the frame pointer (in fact, in your > > scheme, what does frame pointer elimination?) and produce an offset > > from the stack pointer which is invalid. That is, spill code or frame > > pointer elimination can generate invalid address, and something needs > > to fix them up. Where does that happen, and how? > > > > > To be fair, I haven't given register elimination a lot of thought yet. I > was presuming it could be inserted as a pass or as a separate component > of the spiller. Let me get back to you, I must investigate the > issues :-). A couple of prime examples would be helpful :-) I'll write > up a new section for it. The way gcc currently works, register elimination can not always be a separate pass (naturally that might be different in your proposal). The MIPS16, for example, requires a frame pointer if the frame size does not fit in a signed 16-bit offset. But the frame size can change during the spilling process. So you when you start spilling you might think that you can use the stack pointer for all references to the stack frame, and you might use the frame pointer as a general register. But then spilling might cause the stack frame to be 32768 bytes or larger. So then you need to do the spilling (or, really, global register allocation) all over again, but this time you can't use the frame pointer. However, in fairness, for most targets register elimination is based on factors that don't change during the register allocation process, like whether the function is a leaf or not. In those cases you can decide at the start of the spilling process exactly which registers you can eliminate, and you could eliminate them in a separate pass. Either way, register elimination can cause addresses which were valid to become invalid, typically because valid offsets from the frame pointer become invalid offsets from the stack pointer. So that needs to be cleaned up somewhere. In current gcc, it's handled inside reload, because it is a special case of the general case of pushing constants into memory due to register constraints, or rematerializing values from the stack or from global variables. Waving my hands wildly, it seems to me that it's not quite enough to have descriptions of how to spill every register class. It seems to me that you also need descriptions of how to handle each addressing mode, and in particular how to convert invalid addresses generated during the register elimination or spilling process into valid addresses. This is straightforward for most CPUs, but can get moderately ugly for something like 68020 (where you have a lot of choices) or SH (where practically everything needs to use r0). > Scheduling should be able to use heuristics and perhaps some of the > tools of the allocator (such as register pressure and number of register > available) to prevent itself from being too stupid if so desired. The way gcc currently works, it's really hard for the scheduler to have decent, portable, register pressure heuristics, because we haven't done instruction selection and we haven't generated spill code. I spent a lot of time optimizing for XScale, and having reload insert an unexpected register spill can be a 10% performance hit. I think that what I would like to see out of the scheduler would be some way to say things like "if you find you have to spill at instruction X, try moving instruction Y from before instruction X to after instruction X and see if that gives you better register allocation." But this is pie in the sky stuff anyhow. Thanks for your reply. Ian