This is the mail archive of the
mailing list for the GCC project.
Re: operand scan speedups for PR 18587
- From: Jeffrey A Law <law at redhat dot com>
- To: Andrew MacLeod <amacleod at redhat dot com>
- Cc: gcc-patches <gcc-patches at gcc dot gnu dot org>
- Date: Thu, 25 Nov 2004 23:48:45 -0700
- Subject: Re: operand scan speedups for PR 18587
- Organization: Red Hat, Inc
- References: <1101410913.18842.49.camel@pain>
- Reply-to: law at redhat dot com
On Thu, 2004-11-25 at 14:28 -0500, Andrew MacLeod wrote:
> In response to the excessive time spend in operand scanning in PR 18587,
> the following two patches help.
> First, we eliminate the linear search for duplicates when building VUSES
> and VMAYDEFs. Instead, two bits are added to the var annotation and we
> use those bits to determine whether a given var is already in the list
> or not.
> I tried a few approaches, including bitmaps, but the overhead of
> searching and inserting into a bitmap works out pretty close to the time
> required to do the linear search most of the time. The average list is
> 7 items or less, and quite sparse. In any case, this appeared to have
> the best all round results.
> The other patch speeds up the code which adds virtual operands for the
> call clobbered bit vector at each call site. Every time we had a call,
> we iterated through the bitvector and built up an operand vector for
> those variables. Those variables dont change very often, so now we keep
> a cache of the operand vector that is built. The next time we need the
> clobbers for a call, we simply use the cache if it hasn't been
> invalidated by adding or removing global variables.
> The combined speedups from these two patches are pretty decent.
> Average of two runs USER time for operand scanning phase on a 1.8Ghz P4.
> orig patched
> cplusplus-grammer.ii 22.58 sec 10.35 sec
> tramp3d.ii 6.14 sec 4.03 sec
> generate3.4.ii 1.69 sec 1.23 sec
> all gcc .i files 6.72 sec 5.83 sec
> This has been bootstrapped on i686-pc-linux-gnu, and causes no new
> regressions on that platform.
> PS. The var-ann patch is responsible for the lion share of the speedup
> to cplusplus-grammer.ii, and the call clobber patch responsible for most
> of the rest of the gains.
FWIW, I was pondering using hash tables to build up the operand lists.
Did you happen to look at that solution, or in your opinion is that