This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [rtlopt] Store motion rewrite

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
the rtlopt-branch?
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.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]