[Bug optimization/6585] useless memory store instructions on x86

[Bug optimization/6585] useless memory store instructions on x86

[steven at gcc dot gnu dot org]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

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


steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|0000-00-00 00:00:00         |2003-07-04 11:09:34
               date|                            |
   Target Milestone|---                         |3.4


------- Additional Comments From steven at gcc dot gnu dot org  2003-07-04 11:09 -------
AFAICT this looks a little better, but still not optimal:

        .file   "6585.c"
# GNU C version 3.4 20030703 (experimental) (i686-pc-linux-gnu)
#       compiled by GNU C version 3.4 20030703 (experimental).
# GGC heuristics: --param ggc-min-expand=47 --param ggc-min-heapsize=31916
# options passed:  -O3 -fverbose-asm -march=i686 -mtune=i686
# -fomit-frame-pointer
# options enabled:  -feliminate-unused-debug-types -fdefer-pop
# -fomit-frame-pointer -foptimize-sibling-calls -funit-at-a-time
# -fcse-follow-jumps -fcse-skip-blocks -fexpensive-optimizations
# -fthread-jumps -fstrength-reduce -funswitch-loops -fpeephole -fforce-mem
# -ffunction-cse -fkeep-static-consts -fcaller-saves -fpcc-struct-return
# -fgcse -fgcse-lm -fgcse-sm -floop-optimize -fcrossjumping -fif-conversion
# -fif-conversion2 -frerun-cse-after-loop -frerun-loop-opt
# -fdelete-null-pointer-checks -fschedule-insns2 -fsched-interblock
# -fsched-spec -fbranch-count-reg -freorder-blocks -freorder-functions
# -frename-registers -fcprop-registers -fcommon -fverbose-asm -fgnu-linker
# -fregmove -foptimize-register-move -fargument-alias -fstrict-aliasing
# -fmerge-constants -fzero-initialized-in-bss -fident -fpeephole2
# -fguess-branch-probability -fmath-errno -ftrapping-math -m80387
# -mhard-float -mno-soft-float -mieee-fp -mfp-ret-in-387
# -maccumulate-outgoing-args -mno-red-zone -mtls-direct-seg-refs
# -mtune=i686 -march=i686
                                                                       
        .text
        .p2align 4,,15
.globl mul
        .type   mul, @function
mul:
        subl    $20, %esp       #
        movl    32(%esp), %ecx  # load b0 in ecx
        movl    %edi, 12(%esp)  # save %edi
        movl    24(%esp), %eax  # load a0 in eax
        movl    %ebx, 8(%esp)   # save %ebx
        movl    36(%esp), %edi  # load b1 in edi
        movl    %ebp, 16(%esp)  # save %ebp             !!! USELESS
        movl    16(%esp), %ebp  # restore %ebp          !!! USELESS
        mull    %ecx            # %edx:%eax := a0*b0
        movl    %edx, %ebx      # save high part (==%edx) in %ebx
        movl    28(%esp), %edx  # load a1 in %edx
        movl    %eax, (%esp)    # save %eax (now a0*b0 in ebx:(%esp))
        movl    24(%esp), %eax  # load a0 in eax
        imull   %edx, %ecx      # %eax := a1*b0
        imull   %edi, %eax      # %eax := b1*%eax
        movl    12(%esp), %edi  # restore edi
        addl    %eax, %ebx      # compute final result...
        leal    (%ebx,%ecx), %eax       #...
        movl    8(%esp), %ebx   # restore ebx
        movl    %eax, 4(%esp)   # Why not just: movl %eax,%edx
        movl    4(%esp), %edx   # !!! USELESS
        movl    (%esp), %eax    # movl  (%esp), %eax
        addl    $20, %esp       #
        ret
        .size   mul, .-mul
        .section        .note.GNU-stack,"",@progbits
        .ident  "GCC: (GNU) 3.4 20030703 (experimental)"

Especially the last "USELESS" is surprising.  Why go through the stack here?!

[Bug optimization/6585] Reduntant store/load instruction pairs on ix86

[steven at gcc dot gnu dot org]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

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


steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|useless memory store        |Reduntant store/load
                   |instructions on x86         |instruction pairs on ix86


------- Additional Comments From steven at gcc dot gnu dot org  2003-07-10 20:09 -------
After looking into this a bit further and after consulting with Zdenek, I
believe we should blaim this bug on something in the register allocator.  But
then again the same problem exists with -fnew-ra, so maybe it's something in the
i386 backend (register sets???).  Maybe someone can try on a different 32bits
target and see if the problem exists there as well.

Anyway, before register allocation it
looks reasonable, but after global reg alloc we get this insns:

(insn 39 18 24 0 (set (mem:SI (plus:SI (reg/f:SI 7 esp)
                (const_int 4 [0x4])) [3 S4 A8])
        (reg:SI 2 ecx)) 39 {*movsi_1_nointernunit} (nil)
    (nil))
 
(note:HI 24 39 27 0 NOTE_INSN_FUNCTION_END)
 
(insn:HI 27 24 30 0 (set (reg/i:DI 0 rax [ <result> ])
        (mem:DI (reg/f:SI 7 esp) [3 S8 A8])) 60 {*movdi_2} (insn_list 18
(nil))
    (nil))

%ecx is put in the stack and subsequently loaded into %edx when the
result insn is expanded.  (After some black magic apparently %ecx is
replaced with %ebx post reload...)

[Bug optimization/6585] Redundant store/load instruction pairs on ix86

[dhazeghi at yahoo dot com]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

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


dhazeghi at yahoo dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|3.4                         |---

[Bug optimization/6585] Redundant store/load instruction pairs on ix86

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement
   Last reconfirmed|2003-07-04 11:09:34         |2003-11-25 07:51:11
               date|                            |


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

[Bug optimization/6585] Redundant store/load instruction pairs on ix86

[kazu at cs dot umass dot edu]

------- Additional Comments From kazu at cs dot umass dot edu  2004-03-17 08:03 -------
With -O3 -fnew-ra -march=i686 -mtune=i686 -fomit-frame-pointer, I get:

mul:
	subl	$20, %esp
	movl	%esi, 12(%esp)	; save %esi
	movl	24(%esp), %eax
	movl	32(%esp), %esi
	movl	28(%esp), %ecx
	movl	%edi, 16(%esp)	; save %edi
	movl	36(%esp), %edi
	movl	%eax, (%esp)
	mull	%esi
	movl	%ecx, 4(%esp)
	movl	%ebx, 8(%esp)
	movl	%eax, %ecx
	movl	(%esp), %eax
	imull	%eax, %edi
	movl	4(%esp), %eax
	imull	%esi, %eax
	movl	12(%esp), %esi	; restore %esi
	leal	(%edx,%edi), %edi
	leal	(%edi,%eax), %ebx
	movl	16(%esp), %edi	; restore %edi
	movl	%ecx, %eax
	movl	%ebx, %edx
	movl	8(%esp), %ebx	; restore %ebx
	addl	$20, %esp
	ret

Note that those "why not" instructions are gone.
"USELESS" instructions are gone even without -fnew-ra as of today's mainline.


-- 


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

[Bug optimization/6585] Redundant store/load instruction pairs on ix86

[bruno at clisp dot org]

------- Additional Comments From bruno at clisp dot org  2004-03-17 12:10 -------
This result is much better, indeed. Still there is room for two more optimizations: 
 
1) The final "movl %ebx, %edx" instruction could be removed if the preceding lea 
instruction would write its results into %edx, not into %ebx. 
 
2) Storing a0 and a1 in temporary stack locations is useless since a0 and a1 
already come from the stack, and data analysis could find out that they are 
read-only. 
 
Commented listing: 
 
mul: 
	subl	$20, %esp 
	movl	%esi, 12(%esp)				; save %esi 
	movl	24(%esp), %eax		a0 
	movl	32(%esp), %esi		b0 
	movl	28(%esp), %ecx		a1 
	movl	%edi, 16(%esp)				; save %edi 
	movl	36(%esp), %edi		b1 
	movl	%eax, (%esp)				USELESS! Use 24(%esp) instead 
	mull	%esi			%edx:%eax := a0*b0 
	movl	%ecx, 4(%esp)				USELESS! Use 28(%esp) instead 
	movl	%ebx, 8(%esp)				; save %ebx 
	movl	%eax, %ecx 
	movl	(%esp), %eax 
	imull	%eax, %edi		a0*b1 
	movl	4(%esp), %eax 
	imull	%esi, %eax		a1*b0 
	movl	12(%esp), %esi				; restore %esi 
	leal	(%edx,%edi), %edi	hi+a0*b1 
	leal	(%edi,%eax), %ebx	hi+a0*b1+a1*b0	COULD BE SIMPLIFIED 
	movl	16(%esp), %edi				; restore %edi 
	movl	%ecx, %eax		lo 
	movl	%ebx, %edx				USELESS! 
	movl	8(%esp), %ebx				; restore %ebx 
	addl	$20, %esp 
	ret 
 

-- 


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

[Bug rtl-optimization/6585] Redundant store/load instruction pairs on ix86

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-10-11 02:57 -------
Here is the latest asm from the mainline:
mul:
        subl    $20, %esp
        movl    32(%esp), %ecx
        movl    24(%esp), %eax
        movl    %ebx, 8(%esp)
        movl    36(%esp), %ebx
        movl    %edi, 12(%esp)
        movl    24(%esp), %edi
        movl    %ebp, 16(%esp)
        mull    %ecx
        imull   28(%esp), %ecx
        imull   %ebx, %edi
        movl    8(%esp), %ebx
        movl    %edx, %ebp
        movl    %eax, (%esp)
        addl    %edi, %ebp
        movl    (%esp), %eax
        leal    (%ebp,%ecx), %ecx
        movl    12(%esp), %edi
        movl    %ecx, 4(%esp)
        movl    16(%esp), %ebp
        movl    4(%esp), %edx
        addl    $20, %esp
        ret

-- 


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

[Bug rtl-optimization/6585] Redundant store/load instruction pairs on ix86

[bruno at clisp dot org]

------- Additional Comments From bruno at clisp dot org  2004-10-11 11:55 -------
This result is even better: shorter than the previous ones, and there are 
no useless moves between registers any more. 
 
However, there are more useless moves from register to stack slot and back 
from stack slot to register. They could be eliminated. 
 
Commented listing: 
 
mul: 
        subl    $20, %esp 
        movl    32(%esp), %ecx		b0 
        movl    24(%esp), %eax		a0 
        movl    %ebx, 8(%esp)				; save %ebx 
        movl    36(%esp), %ebx		b1 
        movl    %edi, 12(%esp)				; save %edi 
        movl    24(%esp), %edi		a0 
        movl    %ebp, 16(%esp)				; save %ebp 
        mull    %ecx			%edx:%eax := a0*b0 
        imull   28(%esp), %ecx		a1*b0 
        imull   %ebx, %edi		a0*b1 
        movl    8(%esp), %ebx				; restore %ebx 
        movl    %edx, %ebp		hi 
        movl    %eax, (%esp)				USELESS! 
        addl    %edi, %ebp		hi+a0*b1 
        movl    (%esp), %eax				USELESS! 
        leal    (%ebp,%ecx), %ecx	hi+a0*b1+a1*b0	COULD GO INTO %edx 
DIRECTLY 
        movl    12(%esp), %edi				; restore %edi 
        movl    %ecx, 4(%esp)				USELESS! 
        movl    16(%esp), %ebp				; restore %ebp 
        movl    4(%esp), %edx				USELESS! 
        addl    $20, %esp 
        ret 
 

-- 


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

[Bug rtl-optimization/6585] Redundant store/load instruction pairs on ix86

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2005-06-26 13:35 -------
Today's results ("-O2 -m32 -march=i686 -mtune=i686 -fomit-frame-pointer"): 
 
        .file   "t.c" 
        .text 
        .p2align 4,,15 
.globl mul 
        .type   mul, @function 
mul: 
        subl    $12, %esp               # get space to save three registers 
        movl    %ebx, (%esp)            # save %ebx 
        movl    20(%esp), %edx          # %edx <- a1  COULD GO INTO %esi 
        movl    28(%esp), %ebx          # %ebx <- b1  COULD GO INTO %edi 
        movl    16(%esp), %eax          # %eax <- a0 
        movl    24(%esp), %ecx          # %ecx <- b0 
        movl    %esi, 4(%esp)           # save %esi 
        movl    %edx, %esi              # %esi <- a1 
        movl    %edi, 8(%esp)           # save %edi 
        movl    %ebx, %edi              # %edi <- b1 
        movl    (%esp), %ebx            # restore %ebx 
        imull   %eax, %edi              # %edi <- a0*b1 
        imull   %ecx, %esi              # %esi <- b0*a1 
        mull    %ecx                    # %edx:%eax := a0*b0 
        addl    %edi, %esi              # %esi <- a0*b1 + b0*a1 
        movl    8(%esp), %edi           # restore %edi 
        leal    (%esi,%edx), %edx       # %edx <- a0*b1 + b0*a1 + hi(a0*b0) 
        movl    4(%esp), %esi           # %restore %esi 
        addl    $12, %esp               # free stack space 
        ret                             # return result in %edx:%eax 
        .size   mul, .-mul 
        .ident  "GCC: (GNU) 4.1.0 20050626 (experimental)" 
        .section        .note.GNU-stack,"",@progbits 
 
There are still the questionable moves through %ebx and %edx, but it is 
still better than before. 
 

-- 


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

[Bug rtl-optimization/6585] Redundant store/load instruction pairs on ix86

[bruno at clisp dot org]

------- Additional Comments From bruno at clisp dot org  2005-06-27 11:50 -------
Indeed, the result is much better now, nearly optimal. 
As you say, the only further optimization possible is that a better 
register allocation could get rid of the 
      movl    %edx, %esi 
and 
      movl    %ebx, %edi 
instructions. 
 

-- 


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

[Bug rtl-optimization/6585] Redundant store/load instruction pairs on ix86

[ismail at pardus dot org dot tr]

------- Comment #13 from ismail at pardus dot org dot tr  2007-11-23 06:02 -------
Mainline now looks like :

[~]> cat mul.s
        .file   "mul.c"
        .text
        .p2align 4,,15
.globl mul
        .type   mul, @function
mul:
        subl    $8, %esp
        movl    %ebx, (%esp)
        movl    24(%esp), %ecx
        movl    12(%esp), %ebx
        movl    %esi, 4(%esp)
        movl    16(%esp), %eax
        movl    20(%esp), %esi
        imull   %ebx, %ecx
        imull   %esi, %eax
        addl    %eax, %ecx
        movl    %esi, %eax
        mull    %ebx
        movl    (%esp), %ebx
        leal    (%ecx,%edx), %esi
        movl    %esi, %edx
        movl    4(%esp), %esi
        addl    $8, %esp
        ret
        .size   mul, .-mul
        .ident  "GCC: (GNU) 4.3.0 20071120 (experimental)"
        .section        .note.GNU-stack,"",@progbits

I think the bug can be closed as fixed now.


-- 

ismail at pardus dot org dot tr changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ismail at pardus dot org dot
                   |                            |tr


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

[Bug rtl-optimization/6585] Redundant store/load instruction pairs on ix86

[steven at gcc dot gnu dot org]

------- Comment #14 from steven at gcc dot gnu dot org  2007-11-23 07:36 -------
.


-- 

steven at gcc dot gnu dot org changed:

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


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

[Bug rtl-optimization/6585] Redundant store/load instruction pairs on ix86

[ubizjak at gmail dot com]

------- Comment #15 from ubizjak at gmail dot com  2007-11-23 07:43 -------
(In reply to comment #13)

> I think the bug can be closed as fixed now.

The problem of redundant stores has been fixed, but the code is far from
optimal. As evident from PR 17236, icc generates:

        movl      8(%esp), %ecx                                 #516.18
        imull     12(%esp), %ecx                                #516.18
        movl      16(%esp), %eax                                #516.18
        imull     4(%esp), %eax                                 #516.18
        addl      %eax, %ecx                                    #516.18
        movl      4(%esp), %eax                                 #516.18
        mull      12(%esp)                                      #516.18
        addl      %ecx, %edx                                    #516.18
        ret                                                     #516.18


-- 

ubizjak at gmail dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
OtherBugsDependingO|                            |17236
              nThis|                            |


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

[Bug rtl-optimization/6585] Redundant store/load instruction pairs on ix86

[rask at gcc dot gnu dot org]

------- Comment #16 from rask at gcc dot gnu dot org  2007-11-23 20:43 -------
(In reply to comment #

> I think the bug can be closed as fixed now.

   I'm not so convinced. This part

>	leal    (%ecx,%edx), %esi
>	movl    %esi, %edx
>	movl    4(%esp), %esi

should have been

        addl    %ecx, %edx
        movl    4(%esp), %esi

and using %esi instead of a stack slot doesn't fix the problem. Compare with
what we started with (comment #0):

>	movl    %edx, 4(%esp)       hi+a0*b1          ! Could be simplified
>	addl    %ecx, 4(%esp)       hi+a0*b1+a1*b0    ! to a single insn:
>	movl    4(%esp), %edx                         ! addl %ecx, $edx

The problem hasn't been fixed until we get that "addl %ecx, %edx" instruction.
One more example:
        movl    16(%esp), %eax  ->      movl    16(%esp), %esi
        movl    20(%esp), %esi  ->      movl    20(%esp), %eax
        imull   %ebx, %ecx
        imull   %esi, %eax      ->      imull   %eax, %esi
        addl    %eax, %ecx      ->      addl    %esi, %ecx
        movl    %esi, %eax      ->      -
        mull    %ebx

This is exactly what a register allocator is supposed to figure out: Register
allocation.


-- 

rask at gcc dot gnu dot org changed:

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


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

[Bug rtl-optimization/6585] Redundant store/load instruction pairs on ix86

[steven at gcc dot gnu dot org]

------- Comment #17 from steven at gcc dot gnu dot org  2007-11-23 20:48 -------
And we're not going to keep every ra bug open.  This just spoils bugzilla
search results.

*** This bug has been marked as a duplicate of 17236 ***


-- 

steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|REOPENED                    |RESOLVED
         Resolution|                            |DUPLICATE


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

[Bug rtl-optimization/6585] Redundant store/load instruction pairs on ix86

[rask at gcc dot gnu dot org]

------- Comment #18 from rask at gcc dot gnu dot org  2007-12-19 14:15 -------
Created an attachment (id=14795)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=14795&action=view)
(u)mulsidi3 patch

This patch (in testing) improves the register allocation, removing the last
redundant movl instructions:

mul:
        pushl   %ebx                    # 40    *pushsi2        [length = 1]
        movl    8(%esp), %ebx           # 28    *movsi_1/1      [length = 4]
        movl    16(%esp), %eax          # 30    *movsi_1/1      [length = 4]
        movl    20(%esp), %ecx          # 37    *movsi_1/1      [length = 4]
        movl    12(%esp), %edx          # 38    *movsi_1/1      [length = 4]
        imull   %ebx, %ecx              # 7     *mulsi3_1/3     [length = 3]
        imull   %eax, %edx              # 8     *mulsi3_1/3     [length = 3]
        addl    %edx, %ecx              # 9     *addsi_1/1      [length = 2]
        mull    %ebx                    # 33    *umulsidi3      [length = 2]
        popl    %ebx                    # 43    popsi1          [length = 1]
        leal    (%ecx,%edx), %edx       # 39    *lea_1          [length = 3]
        ret                             # 44    return_internal [length = 1]


-- 

rask at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |rask at gcc dot gnu dot org
                   |dot org                     |
             Status|RESOLVED                    |ASSIGNED
         Resolution|DUPLICATE                   |


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

[Bug rtl-optimization/6585] Redundant store/load instruction pairs on ix86

[ubizjak at gmail dot com]

------- Comment #19 from ubizjak at gmail dot com  2008-09-06 16:18 -------
Exact duplicate of PR 17236. Mainline gcc (4.4.0 20080906, IRA) generates:

        pushl   %ebx
        movl    8(%esp), %eax
        movl    16(%esp), %edx
        movl    20(%esp), %ecx
        movl    12(%esp), %ebx
        imull   %eax, %ecx
        imull   %edx, %ebx
        mull    %edx
        addl    %ebx, %ecx
        popl    %ebx
        leal    (%ecx,%edx), %edx


*** This bug has been marked as a duplicate of 17236 ***


-- 

ubizjak at gmail dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
OtherBugsDependingO|17236                       |
              nThis|                            |
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |DUPLICATE
   Target Milestone|---                         |4.4.0


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