[Bug target/23971] New: Compilation takes a long time with -O2 option

[Bug target/23971] New: Compilation takes a long time with -O2 option

[tsv at solvo dot ru]

gcc version 4.1.0 20050918 (experimental)

Compilation of attached file takes a long time with -O2 option.
If I use "-O0" or "-O2 -fno-ivopts" it takes just 6 secs to complete (the
cross-compiler for alpha on x86-64 "gcc version 4.0.1 20050727 (Red Hat
4.0.1-5)" takes about 200 secs, but the native version compiles less then a second).

Thank you,

-- 
           Summary: Compilation takes a long time with -O2 option
           Product: gcc
           Version: 4.1.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: target
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: tsv at solvo dot ru
                CC: gcc-bugs at gcc dot gnu dot org
 GCC build triplet: alpha-unknown-linux-gnu
  GCC host triplet: alpha-unknown-linux-gnu
GCC target triplet: alpha-unknown-linux-gnu


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23971

[Bug target/23971] Compilation takes a long time with -O2 option

[tsv at solvo dot ru]

------- Additional Comments From tsv at solvo dot ru  2005-09-19 19:21 -------
Created an attachment (id=9775)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=9775&action=view)
testcase


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23971

[Bug tree-optimization/23971] Compilation takes a long time with -O2 option

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rakdver at gcc dot gnu dot
                   |                            |org
          Component|target                      |tree-optimization
           Keywords|                            |compile-time-hog


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23971

[Bug tree-optimization/23971] Compilation takes a long time with -O2 option

[falk at debian dot org]

------- Additional Comments From falk at debian dot org  2005-09-19 21:18 -------
Confirmed. Test case:

void rgb_ycc_start(long *rgb_ycc_tab) {
    long i;
    for (i = 0; i <= 255; i++)
	rgb_ycc_tab[i] = 19595 * i;
}

These 4 lines take 27 seconds to compile, nearly all of which is spent
in synth_mult. Problem only occurs with -mcpu=ev4.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23971

[Bug middle-end/23971] Compilation takes a long time with -O2 option

[falk at debian dot org]

------- Additional Comments From falk at debian dot org  2005-09-20 12:45 -------
Slightly simplified test case:

unsigned long f(unsigned long x) { return x * 5445825408751490200UL; }

(compile time 33.49s)

So it's just synth_mult running amok, and this has nothing to do with ivopts.


-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|tree-optimization           |middle-end


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23971

[Bug middle-end/23971] [4.0, 4.1 regression] synth_mult running amok

[falk at debian dot org]

------- Additional Comments From falk at debian dot org  2005-09-20 13:01 -------
This is also reproducible with 4.0.2 20050913, but not 3.4.5 20050821 (well, it
takes 0.5 seconds there, which also seems quite excessive).


-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |critical
            Summary|Compilation takes a long    |[4.0, 4.1 regression]
                   |time with -O2 option        |synth_mult running amok


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23971

[Bug middle-end/23971] [4.0, 4.1 regression] synth_mult running amok

[bonzini at gcc dot gnu dot org]

------- Additional Comments From bonzini at gcc dot gnu dot org  2005-09-20 13:33 -------
This one is reproducible everywhere:

long long f(long long x) { return x * 5445825408751490200ULL; }


-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bonzini at gcc dot gnu dot
                   |                            |org
  GCC build triplet|alpha-unknown-linux-gnu     |*-*-*
   GCC host triplet|alpha-unknown-linux-gnu     |*-*-*
 GCC target triplet|alpha-unknown-linux-gnu     |*-*-*


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23971

[Bug middle-end/23971] [4.0, 4.1 regression] synth_mult running amok

[bonzini at gcc dot gnu dot org]

------- Additional Comments From bonzini at gcc dot gnu dot org  2005-09-20 13:38 -------
no, it's not, sorry for the noise.  it "only" does 210 synth_mult calls.

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23971

[Bug middle-end/23971] [4.0/4.1 Regression] synth_mult running amok

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-09-20 14:55 -------
CCing Roger since he understands synth_mult.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |sayle at gcc dot gnu dot org
  GCC build triplet|alpha-unknown-linux-gnu     |alpha-*-linux-gnu
   GCC host triplet|alpha-unknown-linux-gnu     |alpha-*-linux-gnu
 GCC target triplet|alpha-unknown-linux-gnu     |alpha-*-linux-gnu
            Summary|[4.0, 4.1 regression]       |[4.0/4.1 Regression]
                   |synth_mult running amok     |synth_mult running amok


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23971

[Bug middle-end/23971] [4.0/4.1 Regression] synth_mult running amok

[kazu at gcc dot gnu dot org]

------- Additional Comments From kazu at gcc dot gnu dot org  2005-09-20 19:28 -------
On alpha-linux-gnu, synth_mult is called 20 million times.

I've got one idea that might or might not work.

Currently, synth_mult records successful cases in it hash/cache.
That is, if synth_mult determines that "var * N" should be implemented
as "var * log_2 (N-1) + var" for example, synth_mult records that
into one entry of cache.

However, if synth_mult cannot determine the best way to implement "var * N"
with in a given cost limit, it does nothing but return to the caller.

What we can do here is to record failures, saying "I don't know
the best way to implement multiplication by N within cost limit of M."
Then next time synth_mult is asked to find the best way to implmenent
multiplication by N within cost limit of M or less, we know that
we don't have any way of meeting the limit.

For example, in this particular test case, synth_mult is asked to synthesize
multiplication by 3381213428 as many as 14,705 times.
Most of these invocations come with similar cost limits.
So we should be able to save many many recursive calls.

Take 1193369444 as another example.  synth_mult is called with this number
4485 times.  Again, we should be able to save many recursive calls.

I'm going to give this idea a try some time this week.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23971

[Bug middle-end/23971] [4.0/4.1 Regression] synth_mult running amok

[kazu at gcc dot gnu dot org]

------- Additional Comments From kazu at gcc dot gnu dot org  2005-09-20 22:12 -------
OK, with my idea I can cut down the number of calls to synth_mult to
1.4 million.

I may be able to improve further by recording the cost in successful cases.


-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |kazu at gcc dot gnu dot org
                   |dot org                     |
             Status|NEW                         |ASSIGNED


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23971

[Bug middle-end/23971] [4.0/4.1 Regression] synth_mult running amok

[cvs-commit at gcc dot gnu dot org]

------- Additional Comments From cvs-commit at gcc dot gnu dot org  2005-09-21 16:48 -------
Subject: Bug 23971

CVSROOT:	/cvs/gcc
Module name:	gcc
Changes by:	kazu@gcc.gnu.org	2005-09-21 16:47:47

Modified files:
	gcc            : ChangeLog 

Log message:
	PR middle-end/23971
	* expmed.c (alg_code): Add alg_impossible.
	(alg_hash_entry): Add cost.
	(synth_mult): Record alg_impossible in the hash table if
	multiplication by a given integer is impossble within the
	limit.  Speed up using alg_impossible.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&r1=2.9997&r2=2.9998



-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23971

[Bug middle-end/23971] [4.0/4.1 Regression] synth_mult running amok

[kazu at gcc dot gnu dot org]

------- Additional Comments From kazu at gcc dot gnu dot org  2005-09-21 16:50 -------
Just checked in a patch.


-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23971

[Bug middle-end/23971] [4.0/4.1 Regression] synth_mult running amok

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |4.1.0


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23971

[Bug middle-end/23971] [4.0/4.1 Regression] synth_mult running amok

[tsv at solvo dot ru]

------- Additional Comments From tsv at solvo dot ru  2005-09-24 20:29 -------
It takes about 10 minutes to compile attached testcase with -O2 -mcpu=ev4 and
about 2 minutes for -O2 -mcpu=ev5 (compiled on EV45 233Mhz).
The difference is in cost of multiply op - 100 for ev4 and about 54 for ev5.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23971

[Bug middle-end/23971] [4.0/4.1 Regression] synth_mult running amok

[kazu at gcc dot gnu dot org]

------- Additional Comments From kazu at gcc dot gnu dot org  2005-09-24 23:58 -------
(In reply to comment #12)
> It takes about 10 minutes to compile attached testcase with -O2 -mcpu=ev4 and
> about 2 minutes for -O2 -mcpu=ev5 (compiled on EV45 233Mhz).
> The difference is in cost of multiply op - 100 for ev4 and about 54 for ev5.

What gcc are you using?  Mainline with my patch on 2005-09-21?

I posted another one at

http://gcc.gnu.org/ml/gcc-patches/2005-09/msg01384.html

to further speed up synth_mult in expmed.c, so you might want to try that.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23971

[Bug middle-end/23971] [4.0/4.1 Regression] synth_mult running amok

[tsv at solvo dot ru]

------- Additional Comments From tsv at solvo dot ru  2005-09-27 18:42 -------
Yes, I tested the reported gcc version just with your patch. After trying to
trace  "synth_mult" I started to think that there should be a simplier way. :)
In my testcase the "choose_mult_variant" was called with following params:
#16 0x000000012019b1f0 in choose_mult_variant (mode=DImode,
    val=1696403818363083032, alg=0x11fefb178, variant=0x11fefb150,
    mult_cost=100) at ../../gcc/expmed.c:2845

The attempt to do multiplication by shifts and adds/subs for that "huge" val was
interesting. :)

I'll give a try to your new patch.

Thank you.

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23971

[Bug middle-end/23971] [4.0/4.1 Regression] synth_mult running amok

[tsv at solvo dot ru]

------- Additional Comments From tsv at solvo dot ru  2005-09-28 18:07 -------
Retested in idle machine:
patch1 -O2 -mcpu=ev4 - 7 minutes
patch2 -O2 -mcpu=ev4 - 1.30 minutes

patch1 -O2 -mcpu=ev5 - 30 secs
patch2 -O2 -mcpu=ev5 - 13.6 secs

It does make a difference. :)
Thank you.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23971