GCC makes a mess

Following up on a report aboutFFmpeg being slower at MPEG audio decoding thanMAD, I compared the speed of the two decoders on a few machines. FFmpeg came out somewhat ahead of MAD on most of my test systems with the exception of 32-bit PowerPC. On the PPC MAD was nearly twice as fast as FFmpeg, suggesting something was going badly wrong in the compilation.

A session with oprofile exposes multiplication as the root of the problem. The MPEG audio decoder in FFmpeg includes many operations of the forma += b * c whereb andc are 32 bits in size anda is 64-bit. 64-bit maths on a 32-bit CPU is not handled well by GCC, even when good hardware support is available. A couple of examples compiled with GCC 4.3.3 illustrate this.

Suppose you need the high 32 bits from the 64-bit result of multiplying two 32-bit numbers. This is most easily written in C like this:

int mulh(int a, int b){    return ((int64_t)a * (int64_t)b) >> 32;}

It doesn’t take much thinking to see that the PowerPCmulhw instruction performs exactly this operation. Indeed, GCC knows of this instruction and uses it. But can we bereally sure that those low 32 bits are not needed? GCC seems unconvinced:

mulhw   r9,  r4,  r3mullw   r10, r4,  r3srawi   r11, r9,  31srawi   r12, r9,  0mr      r3,  r12blr

The second example is slightly more complicated:

int64_t mac(int64_t a, int b, int c, int d){    a += (int64_t)b * (int64_t)c;    a += (int64_t)b * (int64_t)d;    return a;}

This can, of course, be done with four multiplications and four additions. GCC, however, likes to be thorough, and uses twice the number of both instructions, plus some loads, stores and shifts for completeness:

stwu    r1,  -32(r1)srawi   r0,  r6,  31mullw   r0,  r0,  r5srawi   r8,  r7,  31stw     r29, 20(r1)srawi   r29, r5,  31stw     r27, 12(r1)stw     r28, 16(r1)mullw   r11, r29, r6mulhwu  r9,  r6,  r5add     r0,  r0,  r11mullw   r10, r6,  r5add     r9,  r0,  r9mullw   r29, r29, r7addc    r28, r10, r4adde    r27, r9,  r3mullw   r8,  r8,  r5mulhwu  r9,  r7,  r5add     r8,  r8,  r29lwz     r29, 20(r1)mullw   r10, r7,  r5add     r9,  r8,  r9addc    r12, r28, r10adde    r11, r27, r9lwz     r27, 12(r1)mr      r4,  r12lwz     r28, 16(r1)mr      r3,  r11addi    r1,  r1,  32blr

Fortunately, this madness is easily fixed with a little inline assembler, more than doubling the speed of the decoder, thus making FFmpeg significantly faster than MAD also on PowerPC.

Bookmark thepermalink.

35 Responses toGCC makes a mess

  1. Adrian Bunksays:

    gcc 4.4.0 gives

       0:   7d 24 18 96     mulhw   r9,r4,r3   4:   7d 23 4b 78     mr      r3,r9   8:   4e 80 00 20     blr

    resp.

       0:   7c ec 3b 78     mr      r12,r7   4:   7c eb fe 70     srawi   r11,r7,31   8:   7c ca 33 78     mr      r10,r6   c:   7c c9 fe 70     srawi   r9,r6,31  10:   7d 4a 60 14     addc    r10,r10,r12  14:   7d 29 59 14     adde    r9,r9,r11  18:   7c ab fe 70     srawi   r11,r5,31  1c:   7c 09 29 d6     mullw   r0,r9,r5  20:   7d 6b 51 d6     mullw   r11,r11,r10  24:   7d 0a 29 d6     mullw   r8,r10,r5  28:   7c ea 28 16     mulhwu  r7,r10,r5  2c:   7c 00 5a 14     add     r0,r0,r11  30:   7d 06 43 78     mr      r6,r8  34:   7c a0 3a 14     add     r5,r0,r7  38:   7c c6 20 14     addc    r6,r6,r4  3c:   7c a5 19 14     adde    r5,r5,r3  40:   7c c4 33 78     mr      r4,r6  44:   7c a3 2b 78     mr      r3,r5  48:   4e 80 00 20     blr
  2. Manssays:

    That’s certainly an improvement, going from five times to only twice the optimal code size in the first case and from 3.6x to 2.25x in the second.

    Too bad gcc 4.4 is unable to compile a working FFmpeg on PPC, seehttp://fate.multimedia.cx/

  3. Adrian Bunksays:

    Is anyone reporting all the bugs (both miscompilations and inefficient code) you discover to the gcc Bugzilla?

    The “gcc 4.4 is unable to compile a working FFmpeg on PPC” even looks like a regression that is likely to be fixed in later 4.4 releases if reported.

  4. Adrian Bunksays:

    I just read through the whole bug, and in it’s context this statement sounds reasonable (syntactically correct code can cause trouble for gcc’s register allocator).

    Wrong code generation is a very different issue than the issue discussed there.

  5. compnsays:

    i was going to ask about mad being an int-only decoder but i see ffmpeg mpeg audio decoder has had an int-only version since 0.4.6…

    was the original bugreport on ppc ?

  6. ami_stuffsays:

    Is there a way to fix it with generic C code without asm inlines (probably no one will add m68k code)? If so, I can test it.

  7. ami_stuffsays:
    int64_t mac(int64_t a, int b, int c, int d){    a += (int64_t)b * (int64_t)c;    a += (int64_t)b * (int64_t)d;    return a;}

    GCC 3.4 (-m68060 -fomit-frame-pointer -s -O3):

    #NO_APP.text.even.globl_mac_mac:moveml #0x3c20,sp@-movel sp@(24),d2movel sp@(28),d3movel sp@(32),d5smi d4extbl d4lea ___muldi3,a2movel sp@(36),d1smi d0extbl d0movel d1,sp@-movel d0,sp@-movel d5,sp@-movel d4,sp@-jbsr a2@lea sp@(16),spaddl d1,d3addxl d0,d2movel sp@(40),d1smi d0extbl d0movel d1,sp@-movel d0,sp@-movel d5,sp@-movel d4,sp@-jbsr a2@lea sp@(16),spaddl d3,d1addxl d2,d0moveml sp@+,#0x43crts

    GCC 4.3.2 (-m68060 -fomit-frame-pointer -s -O3):

    #NO_APP.text.even.globl_mac_mac:movem.l #15392,-(sp)move.l 32(sp),d3smi d2extb.l d2lea ___muldi3,a2move.l d3,-(sp)move.l d2,-(sp)move.l 44(sp),-(sp)smi d0extb.l d0move.l d0,-(sp)jsr (a2)lea (16,sp),spmove.l 24(sp),d4move.l 28(sp),d5add.l d1,d5addx.l d0,d4move.l d3,-(sp)move.l d2,-(sp)move.l 48(sp),-(sp)smi d0extb.l d0move.l d0,-(sp)jsr (a2)lea (16,sp),spadd.l d1,d5addx.l d0,d4move.l d4,d0move.l d5,d1movem.l (sp)+,#1084rts

    GCC 4.4 alpha 20081212 (-m68060 -fomit-frame-pointer -s -O3):

    #NO_APP.text.even.globl_mac_mac:movem.l #15360,-(sp)move.l 36(sp),d3smi d2extb.l d2move.l 32(sp),d1smi d0extb.l d0move.l 28(sp),-(sp)smi d4extb.l d4move.l d4,-(sp)move.l d2,d4move.l d3,d5add.l d1,d5addx.l d0,d4move.l d5,-(sp)move.l d4,-(sp)jsr ___muldi3lea (16,sp),spmove.l d1,d2move.l d0,d1move.l 20(sp),d5add.l 24(sp),d2addx.l d5,d1move.l d1,d0move.l d2,d1movem.l (sp)+,#60rts
    • Manssays:

      Try this:

      int64_t MAC64(int64_t d, int a, int b){       union { int64_t x; int hl[2]; } x = { d };    int h, l;    __asm__ ("muls.l %5, %2, %3  \n\t"             "add.l  %3, %1      \n\t"             "addx.l %2, %0      \n\t"             : "+dm"(x.hl[0]), "+dm"(x.hl[1]),               "=d"(h), "=&d"(l)             : "3"(a), "g"(b));    return x.x;}

      BTW, gcc 4.3 and above for m68k all ICE in various places building FFmpeg.

  8. ami_stuffsays:

    @Mans:

    Try WinUAE – Amiga’s emulator. It supports 68040+FPU:

    http://www.winuae.net/

    PS. Right now site is down, but the latest executable is here:

    http://eab.abime.net/showthread.php?t=40738&page=16

  9. Manssays:

    UAE is a full system emulator. It would be much easier to test things with Qemu userspace emulation. Real hardware would be even more fun of course. What hardware are you using?

  10. ami_stuffsays:

    WinUAE, but most of the time I get right timings – the same results I get from users of a real hardware (which binary file is faster, which is slower), so when something is faster on WinUAE, it is probably faster on a real hardware too.

  11. ami_stuffsays:

    Hmm, something is wrong:

    #define int64_t  long longint64_t MAC64(int64_t d, int a, int b){    union { int64_t x; int hl[2]; } x = { d };    int h, l;    __asm__ ("muls.l %5, %2, %3  \n\t"             "add.l  %3, %1      \n\t"             "addx.l %2, %0      \n\t"             : "+dm"(x.hl[0]), "+dm"(x.hl[1]),               "=d"(h), "=&d"(l)             : "3"(a), "g"(b));    return x.x;}

    GCC 4.4 error:

    libavcodec/mpegaudiodec.c:54 error: expected identifier or '(' before 'long'libavcodec/mpegaudiodec.c:54 error: expected ')' before '+=' token

    Line 54 is “int64_t MAC64(int64_t d, int a, int b)”.

  12. Bernd_afasays:

    intresting at least on 68k gcc4.4.0 experimental need only 1 muldi3 and older compilers need 2.

    now i compile gcc4.4.0 release and i send it to amistuff

    if there is need of a 68k system easy to use and know from amiga in the past, here is a modern preconfig system work on linux and windows.only kickrom images of a amiga are need.

    http://amikit.amiga.sk/what-is-it.htm

  13. Bernd_afasays:
    __asm__ ("muls.l %5, %2, %3  \n\t"             "add.l  %3, %1      \n\t"             "addx.l %2, %0      \n\t"             : "+dm"(x.hl[0]), "+dm"(x.hl[1]),

    muls does only support 2 parameters on 68k the result is in 2. register
    but i cant fix it, i have problems to understand the gcc to register syntax

  14. Manssays:

    My code generates correct-looking machine code when compiled with gcc/gas. I just can’t test it.

  15. ami_stuffsays:

    Mans@

    C:\>ffmpeg -i test.mp3
    FFmpeg version SVN-r18696, Copyright (c) 2000-2009 Fabrice Bellard, et al.
    configuration: –enable-memalign-hack –prefix=/mingw –cross-prefix=i686-ming
    w32- –cc=ccache-i686-mingw32-gcc –target-os=mingw32 –arch=i686 –cpu=i686 –e
    nable-avisynth –enable-gpl –enable-zlib –enable-bzlib –enable-libgsm –enabl
    e-libfaac –enable-libfaad –enable-pthreads –enable-libvorbis –enable-libtheo
    ra –enable-libspeex –enable-libmp3lame –enable-libopenjpeg –enable-libxvid –
    -enable-libschroedinger –enable-libx264
    libavutil 50. 3. 0 / 50. 3. 0
    libavcodec 52.27. 0 / 52.27. 0
    libavformat 52.32. 0 / 52.32. 0
    libavdevice 52. 2. 0 / 52. 2. 0
    libswscale 0. 7. 1 / 0. 7. 1
    built on Apr 27 2009 04:01:39, gcc: 4.2.4
    Input #0, mp3, from ‘test.mp3’:
    Duration: 00:04:53.06, start: 0.000000, bitrate: 236 kb/s
    Stream #0.0: Audio: mp3, 44100 Hz, stereo, s16, 192 kb/s
    At least one output file must be specified

    ffmpeg -i test.mp3 test.wav (MPEGAUDIO_HP)

    noasm version: 1:24m
    asm version: 1:14m

    More m68k optimalizations please! :)

  16. Bernd_afasays:

    I think i find now out how gcc work with 64 bit.in gcc file gcc4.4.0/gcc/longlong.h must be valid asm code for gcc or libgcc is used.

    for 68020 it is here.but 68060 have no 32*32 bit with 64 bit result instruction so 68060 use code in libgcc2.c

    the code in longlong.h is this.
    it seem gcc support only umul udiv and sdiv on all platforms but no smul.

    /* The '020, '030, '040, '060 and CPU32 have 32x32->64 and 64/32->32q-32r.  */#if (defined (__mc68020__) && !defined (__mc68060__))#define umul_ppmm(w1, w0, u, v) \  __asm__ ("mulu%.l %3,%1:%0"\   : "=d" ((USItype) (w0)),\     "=d" ((USItype) (w1))\   : "%0" ((USItype) (u)),\     "dmi" ((USItype) (v)))#define UMUL_TIME 45#define udiv_qrnnd(q, r, n1, n0, d) \  __asm__ ("divu%.l %4,%1:%0"\   : "=d" ((USItype) (q)),\     "=d" ((USItype) (r))\   : "0" ((USItype) (n0)),\     "1" ((USItype) (n1)),\     "dmi" ((USItype) (d)))#define UDIV_TIME 90#define sdiv_qrnnd(q, r, n1, n0, d) \  __asm__ ("divs%.l %4,%1:%0"\   : "=d" ((USItype) (q)),\     "=d" ((USItype) (r))\   : "0" ((USItype) (n0)),\     "1" ((USItype) (n1)),\     "dmi" ((USItype) (d)))

    I need closer check if it work as exspectet.

  17. Bernd_afasays:

    here is what is possible in longlong.h
    /* Define auxiliary asm macros.

    1) umul_ppmm(high_prod, low_prod, multiplier, multiplicand) multiplies two
    UWtype integers MULTIPLIER and MULTIPLICAND, and generates a two UWtype
    word product in HIGH_PROD and LOW_PROD.

    2) __umulsidi3(a,b) multiplies two UWtype integers A and B, and returns a
    UDWtype product. This is just a variant of umul_ppmm.

    3) udiv_qrnnd(quotient, remainder, high_numerator, low_numerator,
    denominator) divides a UDWtype, composed by the UWtype integers
    HIGH_NUMERATOR and LOW_NUMERATOR, by DENOMINATOR and places the quotient
    in QUOTIENT and the remainder in REMAINDER. HIGH_NUMERATOR must be less
    than DENOMINATOR for correct operation. If, in addition, the most
    significant bit of DENOMINATOR must be 1, then the pre-processor symbol
    UDIV_NEEDS_NORMALIZATION is defined to 1.

    4) sdiv_qrnnd(quotient, remainder, high_numerator, low_numerator,
    denominator). Like udiv_qrnnd but the numbers are signed. The quotient
    is rounded towards 0.

    5) count_leading_zeros(count, x) counts the number of zero-bits from the
    msb to the first nonzero bit in the UWtype X. This is the number of
    steps X needs to be shifted left to set the msb. Undefined for X == 0,
    unless the symbol COUNT_LEADING_ZEROS_0 is defined to some value.

    6) count_trailing_zeros(count, x) like count_leading_zeros, but counts
    from the least significant end.

    7) add_ssaaaa(high_sum, low_sum, high_addend_1, low_addend_1,
    high_addend_2, low_addend_2) adds two UWtype integers, composed by
    HIGH_ADDEND_1 and LOW_ADDEND_1, and HIGH_ADDEND_2 and LOW_ADDEND_2
    respectively. The result is placed in HIGH_SUM and LOW_SUM. Overflow
    (i.e. carry out) is not stored anywhere, and is lost.

    8) sub_ddmmss(high_difference, low_difference, high_minuend, low_minuend,
    high_subtrahend, low_subtrahend) subtracts two two-word UWtype integers,
    composed by HIGH_MINUEND_1 and LOW_MINUEND_1, and HIGH_SUBTRAHEND_2 and
    LOW_SUBTRAHEND_2 respectively. The result is placed in HIGH_DIFFERENCE
    and LOW_DIFFERENCE. Overflow (i.e. carry out) is not stored anywhere,
    and is lost.

    If any of these macros are left undefined for a particular CPU,
    C macros are used. */

  18. ami_stuffsays:

    I compiled second example with GCC 4.4 final and asm output is identicial to 4.4 alpha, so no changes for m68k.

    I see that “ppc/mathops.h” have optimized versions of MULH, MLS64, MUL16, MAC16 and all of this stuff is used by “libavcodec/mpegaudiodec.c” file.
    Amiga compiler misses also llrint() function which I see is used by decoder, so this slow downs decoding process too.
    There are also no asm optimized round() and roundf() functions.

    If you know Mans how implement these functions as GCC’s m68k asm inlines, it would be really great and it would probably speedup FFmpeg’s decoder a lot.

  19. ami_stuffsays:

    Holly shit! Only 29 sec. now!

  20. ami_stuffsays:

    It beats libmad by 1 sec. With more optimizations like asm llrint() it will be even faster.

    Is there a way to asm optimized code for 68060 build too?

  21. Manssays:

    What hardware are you running this on? Can you confirm that the decoded output is correct, please?

    68060 doesn’t have the 32×32->64 multiply instruction, but I’m sure it’s not too hard to beat gcc even without it.

    The floating point rounding functions are not used in speed-critical places so there is no need to optimise them.

  22. ami_stuffsays:

    I’m running it on WinUAE emulator. I hear no different, but “find dups” program don’t recognize file decoded with standard FFmpeg and asm-optimized as identicial. I can decode some short file and send it to you to mail if you want, so you can analyze it.

  23. Manssays:

    Could you try disabling the asm functions one at a time and see which causes the discrepancy?

  24. ami_stuffsays:

    Bad News. This all speedup was because I compared 68060 build of FFmpeg with 68040 build. 68060 build needs to emulate “muls” instruction – here is a speedup. Also, 68040 build generates different wav file compared to 68060 build.

    When I compile with your MAC64 & MLS64 functions I get only 1 sec. speedup.

    MULH don’t want to compile – statement ‘mul.l (a6),d2:d1’ ignored etc.

  25. ami_stuffsays:

    so for 68060 CPU libmad is the best choice

  26. Bernd_afasays:

    I test this
    -03 -m68020
    -m68040 same result

    int64_t MULH(int a, int b)
    {
    return ((int64_t)(a) * (int64_t)(b))>>32;
    }

    main(int argc, char *argv[])
    {

    printf (“%ld\n”,MULH(argc,(long)argv));
    }

    the code for 68060 is very inefficent, because there is no asm macro in longlong.h
    the command MULS.L D4,D2:D6 is also not support on the UAE JIT and is slow execute by interpreter.

    i think in gcc longlong.h is miss code for 68060.
    I see coldfire code, but this code is too so complex, is a 32 bit *32 bit -> 64 bit result not easier possible ?

    gcc 3.4.0
    MOVE.L 8(A5),D7
    MOVE.L $C(A5),D4
    BSR.L ___main ;
    MOVE.L D7,D6
    MULS.L D4,D2:D6
    MOVE.L D2,-(A7)
    SMI D0
    EXTB.L D0
    MOVE.L D0,-(A7)
    PEA _MAC64+$2E(PC)
    LEA _printf,A3 ;

    gcc 4.3.2

    MOVE.L $C(A5),D1
    MULS.L 8(A5),D0:D1
    MOVE.L D0,-(A7)
    SMI D2
    EXTB.L D2
    MOVE.L D2,-(A7)
    PEA _time_delay+$F8(PC)
    LEA _printf,A3 ;10F94

    gcc 4.4.0

    MOVE.L 8(A5),D2
    MOVE.L $C(A5),D3
    JSR ___main ;10FD50
    MOVE.L D3,D1
    MULS.L D2,D0:D1
    MOVE.L D0,-(A7)
    SMI D2
    EXTB.L D2
    MOVE.L D2,-(A7)
    PEA _time_delay+$FA(PC)
    LEA _printf,A3 ;10FD53

    now with -m68060

    MOVE.L 8(A5),-(A7)
    SMI D0
    EXTB.L D0
    MOVE.L D0,-(A7)
    MOVE.L $C(A5),-(A7)
    SMI D2
    EXTB.L D2
    MOVE.L D2,-(A7)
    JSR ___muldi3 ;110504
    LEA $10(A7),A7
    MOVE.L D0,-(A7)
    SMI D2
    EXTB.L D2
    MOVE.L D2,-(A7)
    PEA _time_delay+$FA(PC)
    LEA _printf,A3 ;110508
    JSR (A3)

    ……

    ___muldi3
    110504A8: MOVE.L A5,-(A7)
    110504AA: MOVEA.L A7,A5
    110504AC: MOVEM.L D2-D7/A2,-(A7)
    110504B0: MOVE.L $C(A5),D5
    110504B4: MOVE.L $14(A5),D6
    110504B8: MOVEA.L 8(A5),A2
    110504BC: MOVE.L $10(A5),D7
    110504C0: MOVE.L D5,D0
    110504C2: MOVE.L D6,D1
    110504C4: MOVE.L D0,D2
    110504C6: SWAP D0
    110504C8: MOVE.L D1,D3
    110504CA: SWAP D1
    110504CC: MOVE D2,D4
    110504CE: MULU D3,D4
    110504D0: MULU D1,D2
    110504D2: MULU D0,D3
    110504D4: MULU D0,D1
    110504D6: MOVE.L D4,D0
    110504D8: EOR D0,D0
    110504DA: SWAP D0
    110504DC: ADD.L D0,D2
    110504DE: ADD.L D3,D2
    110504E0: BCC.S ___muldi3+$40 ;110504E8
    110504E2: ADDI.L #$10000,D1
    110504E8: SWAP D2
    110504EA: MOVEQ #0,D0
    110504EC: MOVE D2,D0
    110504EE: MOVE D4,D2
    110504F0: MOVEA.L D2,A1
    110504F2: ADD.L D1,D0
    110504F4: MOVEA.L D0,A0
    110504F6: MOVE.L A1,D1
    110504F8: MULS.L D7,D5
    110504FC: MOVE.L A2,D2
    110504FE: MULS.L D2,D6
    11050502: ADD.L D6,D5
    11050504: ADD.L A0,D5
    11050506: MOVE.L D5,D0
    11050508: MOVEM.L (A7)+,D2-D7/A2
    1105050C: UNLK A5
    1105050E: RTS

  27. ami_stuffsays:

    Mans, could you try to create code for 68060? This way we will know if this slowdown is because of slow GCC asm generated code or maybe it’s normal without hardware 32×32->64 and there is nothing what can be done without re-design of the mpegaudio decoder? Thanks

  28. Pingback:Lenguaje ensamblador – Fuente: Wikipedia. « zarateblog.wordpress.com