[Bug optimization/14255] New: i386 backend should be teached how to use divl

[Bug optimization/14255] New: i386 backend should be teached how to use divl

[bernie at develer dot com]

When dividing a 64bit integer by a 32bit integer,
GCC promotes everything to 64bits and generates
dumb code calling *both* __divdi3 and __moddi3.

A single divl instruction would have sufficed.
This missing optimization is the reason for
asm hacks such as linux/include/asm/div64.h.

This test case:

 long long a;
 long b, q, r;

 void foo(void)
 {
   q = a / b;
   r = a % b;
 }

Gets compiled to:

 foo:
        pushl   %ebp
        movl    b, %eax
        movl    %esp, %ebp
        pushl   %esi
        movl    %eax, %esi
        pushl   %ebx
        sarl    $31, %esi
        pushl   %esi
        pushl   %eax
        pushl   a+4
        pushl   a
        movl    %eax, %ebx
        call    __divdi3
        addl    $16, %esp
        pushl   %esi
        pushl   %ebx
        pushl   a+4
        pushl   a
        movl    %eax, q
        call    __moddi3
        movl    %eax, r
        addl    $16, %esp
        leal    -8(%ebp), %esp
        popl    %ebx
        popl    %esi
        leave
        ret

-- 
           Summary: i386 backend should be teached how to use divl
           Product: gcc
           Version: 3.5.0
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P2
         Component: optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: bernie at develer dot com
                CC: gcc-bugs at gcc dot gnu dot org


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

[Bug target/14255] i386 backend should be teached how to use divl

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-02-23 13:26 -------
Confirmed, not a regression.  Note this is related to bug 14224.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
  BugsThisDependsOn|                            |14224
             Status|UNCONFIRMED                 |NEW
          Component|optimization                |target
     Ever Confirmed|                            |1
           Keywords|                            |pessimizes-code
      Known to fail|                            |3.5.0
   Last reconfirmed|0000-00-00 00:00:00         |2004-02-23 13:26:46
               date|                            |


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

Re: [Bug optimization/14255] New: i386 backend should be teached how to use divl

[Zack Weinberg]

"bernie at develer dot com" <gcc-bugzilla@gcc.gnu.org> writes:

> When dividing a 64bit integer by a 32bit integer,
> GCC promotes everything to 64bits and generates
> dumb code calling *both* __divdi3 and __moddi3.

This ought to be addressable with a pattern of the form

  (parallel [
    (set (reg:SI quo)
         (truncate:SI (div:DI  (reg:DI dividend)
                               (zero_extend:DI (reg:SI divisor)))))
    (set (reg:SI rem)
         (truncate:SI (mod:DI  (reg:DI dividend)
                               (zero_extend:DI (reg:SI divisor)))))
    ])

but I am not sure where it goes in i386.md.

zw

[Bug target/14255] i386 backend should be teached how to use divl

[zack at codesourcery dot com]

------- Additional Comments From zack at codesourcery dot com  2004-02-23 17:10 -------
Subject: Re:  New: i386 backend should be teached
 how to use divl

"bernie at develer dot com" <gcc-bugzilla@gcc.gnu.org> writes:

> When dividing a 64bit integer by a 32bit integer,
> GCC promotes everything to 64bits and generates
> dumb code calling *both* __divdi3 and __moddi3.

This ought to be addressable with a pattern of the form

  (parallel [
    (set (reg:SI quo)
         (truncate:SI (div:DI  (reg:DI dividend)
                               (zero_extend:DI (reg:SI divisor)))))
    (set (reg:SI rem)
         (truncate:SI (mod:DI  (reg:DI dividend)
                               (zero_extend:DI (reg:SI divisor)))))
    ])

but I am not sure where it goes in i386.md.

zw


-- 


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

[Bug target/14255] i386 backend should be teached how to use divl

[bernie at develer dot com]

------- Additional Comments From bernie at develer dot com  2004-02-23 20:36 -------
Not needed.  The code generation pass already recognizes
the division/modulo combo and looks for a pattern named
"divmod??4".

On the m68k, 32/32 -> 32q+32r operations are nicely
converted to a single instruction:

(define_expand "divmodsi4"
  [(parallel
    [(set (match_operand:SI 0 "nonimmediate_operand" "")
          (div:SI (match_operand:SI 1 "general_operand" "")
                  (match_operand:SI 2 "general_src_operand" "")))
     (set (match_operand:SI 3 "nonimmediate_operand" "")
          (mod:SI (match_dup 1) (match_dup 2)))])]
  "TARGET_68020 || TARGET_CF_HWDIV"
  "")

(define_insn ""
  [(set (match_operand:SI 0 "nonimmediate_operand" "=d")
        (div:SI (match_operand:SI 1 "general_operand" "0")
                (match_operand:SI 2 "general_src_operand" "dmSTK")))
   (set (match_operand:SI 3 "nonimmediate_operand" "=d")
        (mod:SI (match_dup 1) (match_dup 2)))]
  "TARGET_68020"
{
  if (find_reg_note (insn, REG_UNUSED, operands[3]))
    return "divs%.l %2,%0";
  else
    return "divsl%.l %2,%3:%0";
})


-- 


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

[Bug target/14255] i386 backend should be teached how to use divl

[wilson at specifixinc dot com]

------- Additional Comments From wilson at specifixinc dot com  2004-02-25 03:08 -------
Subject: Re:  New: i386 backend should be teached
 how to use divl

bernie at develer dot com wrote:
> When dividing a 64bit integer by a 32bit integer,
> GCC promotes everything to 64bits and generates
> dumb code calling *both* __divdi3 and __moddi3.
> A single divl instruction would have sufficed.

It is more complicated than that.

The ISO C standard says that when you have 64b / 32b, the 32-bit value 
must be promoted to 64-bits, and we must perform a 64-bit operation 
yielding a 64-bit result.  If the user wants only a 32-bit result, then 
the 64-bit result is truncated to 32-bits.

Now we have the question of whether
	64b / 32b -> 32b result, 32b remainder
gives the same result as
	(32b) (64b / (64b) 32b)
for all possible input values.  I believe it doesn't, though I don't 
recall the details.  It is probably easier to prove this using 16b / 8b 
divides, where we can produce all values and check.  See the shorten 
code in build_binary_op in c-typeck.c for instance about another divide 
shortening problem.

Thus we can not easily generate the divl instruction directly.

If we are willing to diverge from the ISO C standard here, we could add 
an operation for this.  This would require adding new named patterns 
which are similar to the mulsidi3 patterns, except we would have 
divdisi3 or something like that.  This divergent behaviour would have to 
be enabled by an option.

We could provide a builtin (intrinsic) so that the user can generate the 
divl instruction is that is what they want.  Many architectures have an 
instruction like this, so this is generally useful.

If we have value range info for the operands, we might be able to prove 
that the two operations give the same result for this program.  I think 
the only inputs that fail are edge conditions like dividing by MIN_INT 
which are rare.  However, this requires some kind of value range 
tracking in the compiler.  I believe we have some now, but I don't know 
if it is good enough to help here.

Generating both the divide and modulo operations is stupid though.  We 
can perhaps fix that even if we can't generate the divl instruction.


-- 


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

[Bug target/14255] i386 backend should be teached how to use divl

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-06-03 03:56 -------
Actually this is just a dup of bug 14224.

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

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


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

[Bug target/14255] i386 backend should be teached how to use divl

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=14255
Bug 14255 depends on bug 14224, which changed state.

Bug 14224 Summary: GCC generates pessimizes code for integer division
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=14224

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