[PATCH] PR/27733, synth_mult cache missing too much

[Paolo Bonzini]

Hello,

this patch fixes PR27733, where synth_mult takes definitely too much to 
find the best way to multiply a 64-bit by a very large number (the 
inverse of 23).

synth_mult's algorithm is known to explode in some cases, and for this 
reason in http://gcc.gnu.org/ml/gcc-patches/2004-11/msg01420.html
Kazu added a cache to it.  Later on, he also reworked a bit the 
algorithm to improve the effectiveness of the cache and to have a lower 
branching factor, and fixed PR23971 with these changes.

However, all this very effective and appreciated hacking of synth_mult 
had a little oversight:

/* The entry for our multiplication cache/hash table.  */
struct alg_hash_entry {
  /* The number we are multiplying by.  */
  unsigned int t;
  ...


Gotcha!  :-P  The factor is stored as a 32-bit value only, while the 
argument of synth_mult is a HOST_WIDE_INT.  While this could even be the 
cause of a wrong-code regression, this is extremely unlikely to happen.  
It is more likely, even in real-world cases like PR27733, that it causes 
a *lot* of cache misses.  In fact, the PR is almost fixed by changing 
the type of this field.

The compilation time however is still pretty high.  I'm therefore 
proposing to also tune a bit the cache, making it bigger for 64-bit 
hosts than it is for 32-bit hosts.  This because multiplications by 
50-60 bit factors are frequent because of the expansion of 
EXACT_DIV_EXPR, and they take up a lot of cache entries.  With a size of 
2069, and with a -O0-built compiler, the PR's testcase compilation time 
is down to 0.3s, and with a size of 1031 it is down to 0.8s.

The attached patch, bootstrapped on i686-pc-linux-gnu, picks the smaller 
size.  Of course, if the reviewer will consider it better, it can be 
changed to the bigger size.  Both sizes are prime numbers of course.

I am regtesting the patch now, but the additional coverage is zero 
because the patch has absolutely no effect on hosts with 32-bit and 
sizeof (HOST_WIDE_INT) == sizeof (int).  Ok for mainline?  What about 4.1?

Paolo
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: pr27733.patch
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20060608/84797d08/attachment.ksh>