[Bug c/37807] New: Exponential compile time with MMX builtins.

[Bug c/37807] New: Exponential compile time with MMX builtins.

[suckfish at ihug dot co dot nz]

Using MMX bultins in a sizeable but not extreme function leads to exponential
compile time.

Attached code will take an excessive compile time [I think hours].

Similar code using SSE compiles quickly for me.

$ gcc --version
gcc (GCC) 4.3.2 20081007 (Red Hat 4.3.2-6)
Copyright (C) 2008 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.


-- 
           Summary: Exponential compile time with MMX builtins.
           Product: gcc
           Version: 4.3.2
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: suckfish at ihug dot co dot nz
 GCC build triplet: x86-64
  GCC host triplet: x86-64
GCC target triplet: x86-64


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

[Bug c/37807] Exponential compile time with MMX builtins.

[suckfish at ihug dot co dot nz]

------- Comment #1 from suckfish at ihug dot co dot nz  2008-10-11 21:21 -------
Created an attachment (id=16482)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=16482&action=view)
Code showing exponential compile time.


-- 


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

[Bug c/37807] Exponential compile time with MMX builtins.

[suckfish at ihug dot co dot nz]

------- Comment #2 from suckfish at ihug dot co dot nz  2008-10-11 21:35 -------
Using '-da' it looks like the 'combine' pass is the culprit:

$ pidof cc1
6410
$ ls -l /proc/6410/fd
... 4 -> ... slow.c.162r.combine
$ ls -s slow.c.162r.combine
0 slow.c.162r.combine

[is there an easier way to get cc1 to tell me what pass it's running when?]


-- 


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

[Bug c/37807] Exponential compile time with MMX builtins.

[rguenth at gcc dot gnu dot org]

------- Comment #3 from rguenth at gcc dot gnu dot org  2008-10-11 22:06 -------
On the trunk it's fast if you fix the testcase to do

static INLINE value_t ROTATE_LEFT (value_t a, unsigned count)
{
    return OR (LEFT (a, ((value_t){count, count})), RIGHT (a,
((value_t){32-count,32-count})));
}


-- 


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

[Bug c/37807] Exponential compile time with MMX builtins.

[suckfish at ihug dot co dot nz]

------- Comment #4 from suckfish at ihug dot co dot nz  2008-10-11 22:23 -------
BTW, __builtin_ia32_psrld and __builtin_ia32_pslld are not documented on the
'X86 built-in functions' page of the manual.


-- 


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

[Bug c/37807] Exponential compile time with MMX builtins.

[suckfish at ihug dot co dot nz]

------- Comment #5 from suckfish at ihug dot co dot nz  2008-10-11 23:02 -------
It looks like nonzero_bits1 in rtlanal.c is going into an exponential
recursion.

AFAICS, that function doesn't deal properly with vector arithmetic anyway?


-- 


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

[Bug c/37807] Exponential compile time with MMX builtins.

[suckfish at ihug dot co dot nz]

------- Comment #6 from suckfish at ihug dot co dot nz  2008-10-11 23:24 -------
I think this function actually gets miscompiled:


typedef int v2si __attribute__ ((vector_size (8)));

v2si foo (v2si x)
{
    x &= (v2si) 0xffffffffll;
    x = __builtin_ia32_psrad (x, 1);
    x &= (v2si) 0x80000000ll;
    return x;
}

to

foo:
        pxor    %xmm0, %xmm0
        ret

The psrad is preserving the sign bit we are returning, so the compiler should
not assume it to be zero.


-- 


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

[Bug c/37807] Exponential compile time with MMX builtins.

[suckfish at ihug dot co dot nz]

------- Comment #7 from suckfish at ihug dot co dot nz  2008-10-12 02:39 -------
Bug 37809 opened for the issue in internal comment 6, as it is different.


-- 


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

[Bug c/37807] Exponential compile time with MMX builtins.

[suckfish at ihug dot co dot nz]

------- Comment #8 from suckfish at ihug dot co dot nz  2008-10-12 04:46 -------
Created an attachment (id=16484)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=16484&action=view)
Test-case modfied to take exponential time on trunk too.

It turns out that it was fast on trunk because inlining is less aggressive
there.

Making some functions inline causes compile time to blow up with trunk also.

Updated test case attached also.

PS.  The correct fix for the rotate on trunk was to use
__builtin_ia32_psrldi/pslldi.


-- 

suckfish at ihug dot co dot nz changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #16482|0                           |1
        is obsolete|                            |


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

[Bug c/37807] Exponential compile time with MMX builtins.

[suckfish at ihug dot co dot nz]

------- Comment #9 from suckfish at ihug dot co dot nz  2008-10-12 05:22 -------
Created an attachment (id=16486)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=16486&action=view)
Possible fix for 37807

Patch above essentially stops nonzero_bits1 and num_sign_bit_copies1 processing
vector types.

This fixes the problem & looking at those functions, they were not written with
vector types in mind.


-- 


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

[Bug c/37807] Exponential compile time with MMX builtins.

[suckfish at ihug dot co dot nz]

------- Comment #10 from suckfish at ihug dot co dot nz  2008-10-12 05:27 -------
Changelog for patch if accepted [will do full bootstrap & make test]:

2008-10-12  Ralph Loader  <suckfish@ihug.co.nz>

        PR 37807
        * rtlanal.c (numzero_bits1): Return early on vector types, avoiding
        exponential time recursion.
        (num_sign_bit_copies1): Likewise.


-- 


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

[Bug middle-end/37807] Exponential compile time with MMX builtins.

[rguenth at gcc dot gnu dot org]

------- Comment #11 from rguenth at gcc dot gnu dot org  2008-10-12 10:29 -------
Note that we stopped documenting most of the x86 specific SSE/MMX builtins
because you should use the SSE/MMX intrinsics instead (the x86 specific
builtins can go away or change without further notice between releases).

Btw, your patch looks reasonable.  Minor code-style nit is that the || goes to
the next line.  If the patch passes bootstrap/test please post it to
gcc-patches@gcc.gnu.org.

Thanks,
Richard.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
          Component|c                           |middle-end
     Ever Confirmed|0                           |1
           Keywords|                            |compile-time-hog
   Last reconfirmed|0000-00-00 00:00:00         |2008-10-12 10:29:35
               date|                            |


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

[Bug middle-end/37807] Exponential compile time with MMX builtins.

[uros at gcc dot gnu dot org]

------- Comment #12 from uros at gcc dot gnu dot org  2008-11-10 09:09 -------
Subject: Bug 37807

Author: uros
Date: Mon Nov 10 09:08:15 2008
New Revision: 141732

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=141732
Log:
        PR middle-end/37807
        PR middle-end/37809
        * combine.c (force_to_mode): Do not process vector types.

        * rtlanal.c (nonzero_bits1): Do not process vector types.
        (num_sign_bit_copies1): Likewise.

testsuite/ChangeLog

        PR middle-end/37807
        PR middle-end/37809
        * gcc/testsuite/gcc.target/i386/mmx-8.c: New test.


Added:
    trunk/gcc/testsuite/gcc.target/i386/mmx-8.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/combine.c
    trunk/gcc/rtlanal.c
    trunk/gcc/testsuite/ChangeLog


-- 


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

[Bug middle-end/37807] Exponential compile time with MMX builtins.

[uros at gcc dot gnu dot org]

------- Comment #13 from uros at gcc dot gnu dot org  2008-11-10 10:45 -------
Subject: Bug 37807

Author: uros
Date: Mon Nov 10 10:43:35 2008
New Revision: 141734

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=141734
Log:
        PR middle-end/37807
        PR middle-end/37809
        * combine.c (force_to_mode): Do not process vector types.

        * rtlanal.c (nonzero_bits1): Do not process vector types.
        (num_sign_bit_copies1): Likewise.

testsuite/ChangeLog:

        PR middle-end/37807
        PR middle-end/37809
        * gcc/testsuite/gcc.target/i386/mmx-8.c: New test.


Added:
    branches/gcc-4_3-branch/gcc/testsuite/gcc.target/i386/mmx-8.c
      - copied unchanged from r141732,
trunk/gcc/testsuite/gcc.target/i386/mmx-8.c
Modified:
    branches/gcc-4_3-branch/gcc/ChangeLog
    branches/gcc-4_3-branch/gcc/combine.c
    branches/gcc-4_3-branch/gcc/rtlanal.c
    branches/gcc-4_3-branch/gcc/testsuite/ChangeLog


-- 


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

[Bug middle-end/37807] Exponential compile time with MMX builtins.

[uros at gcc dot gnu dot org]

------- Comment #14 from uros at gcc dot gnu dot org  2008-11-10 12:22 -------
Subject: Bug 37807

Author: uros
Date: Mon Nov 10 12:20:55 2008
New Revision: 141737

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=141737
Log:
        Backport from mainline:
        2008-11-10  Ralph Loader  <suckfish@ihug.co.nz>

        PR middle-end/37807
        PR middle-end/37809
        * combine.c (force_to_mode): Do not process vector types.

        * rtlanal.c (nonzero_bits1): Do not process vector types.
        (num_sign_bit_copies1): Likewise.

testsuite/ChangeLog:

        Backport from mainline:
        2008-11-10  Ralph Loader  <suckfish@ihug.co.nz>

        PR middle-end/37807
        PR middle-end/37809
        * gcc/testsuite/gcc.target/i386/mmx-8.c: New test.


Added:
    branches/gcc-4_2-branch/gcc/testsuite/gcc.target/i386/mmx-8.c
Modified:
    branches/gcc-4_2-branch/gcc/ChangeLog
    branches/gcc-4_2-branch/gcc/combine.c
    branches/gcc-4_2-branch/gcc/rtlanal.c
    branches/gcc-4_2-branch/gcc/testsuite/ChangeLog


-- 


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

[Bug middle-end/37807] Exponential compile time with MMX builtins.

[ubizjak at gmail dot com]

------- Comment #15 from ubizjak at gmail dot com  2008-11-10 12:24 -------
Fixed.


-- 

ubizjak at gmail dot com changed:

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


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