This is the mail archive of the gcc-patches@gcc.gnu.org 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: operand scan speedups for PR 18587


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.
> 
> Andrew
> 
> 
> 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
overkill?

jeff



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