This is the mail archive of the
mailing list for the GCC project.
Re: [rtlopt] Store motion rewrite
- From: Daniel Berlin <dberlin at dberlin dot org>
- To: David Edelsohn <dje at watson dot ibm dot com>
- Cc: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>, "" <gcc-patches at gcc dot gnu dot org>, Andreas Jaeger <aj at suse dot de>, Jan Hubicka <jh at suse dot cz>, Jeffrey Law <law at redhat dot com>
- Date: Thu, 13 Feb 2003 21:28:48 -0500 (EST)
- Subject: Re: [rtlopt] Store motion rewrite
- References: <200302140138.UAA21996@makai.watson.ibm.com>
On Thu, 13 Feb 2003, David Edelsohn wrote:
> Zdenek> from first glance it seems almost same in functionality and faster; why it
> Zdenek> is not in mainline yet?
> Let's try to merge the best features of both versions, make sure
> it works correctly, and submit it for inclusion in the trunk.
Zdenek, I assume you've bootstrapped/regtested this before putting it on
If so, it should be pretty easy to apply the speedup.
IIRC, the real killer is computing the kill and transparent table, because
we end up calling store_ops_ok a billion times.
Since most stores use the same registers, and the return value of
store_ops_okay's return value depends on two things:
1. Registers set in a bb and the registers the store uses
2. Some pre-defined answers (IE there are a few store that it will
return 0 or 1 for no matter what else you pass to it)
You can precompute the predefined answers once for stores that are
always killed without any trouble (just pass it a zero'd regs_set, and if it returns killed, the
store will be killed everwhere, since if it's killed with no registers
set in a block, it's certainly killed with some registers set).
Once that is done, the only thing the return value will depend on for
the remaining stores is the registers set you pass in.
Most stores use the same registers, and since it's return value now only
depends on what set of "set registers" (i quoted it so the sentence is
understandable) you pass in, and what registers the store uses, you can
just keep track of what the return value was for previous stores and
use it for stores whose registers are either the same, or a subset of the
ones your previous store was.
IE if we know the answer is killed in bb 5, 9, and 12 for a store that
uses only reg 12, the answer for any other store using that register will
at least include kills in bb 5, 9, and 12.
You can go further, too if that's not fast enough.
If you track that the reason a store with multiple registers was killed in
a bb was, say, because of reg 12, you can use the answer for *any* store using
reg 12, not just those with the same registers.
Once that is done, if you have answers already for all the regs in the
current store, you can just OR them together, and you get the answer for
the current store.
IE if we know that
stores with reg 12 are killed only in bb 6, 9, 12 because of reg 12
stores with reg 13 are killed only in bb 1, 3, 5 because of reg 13
Then given a store using both reg 12 and 13, we know the answer is 1,
3, 5, 6, 9, 12 without calling store_ops_okay at all.