[Bug c++/55393] New: gcc/g++ multiplies two unsigned integers using the IMULQ instruction

[Bug c++/55393] New: gcc/g++ multiplies two unsigned integers using the IMULQ instruction

[cosmos at claycon dot org]

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

             Bug #: 55393
           Summary: gcc/g++ multiplies two unsigned integers using the
                    IMULQ instruction
    Classification: Unclassified
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: cosmos@claycon.org


g++ -Wall -Wextra -O2 -o mult mult.cpp
g++ (GCC) 4.7.2 20120921 (Red Hat 4.7.2-2)
64bit

mult.cpp:

#include <iostream>

void
display(
        unsigned long int num,
        unsigned long int mult)
{
        unsigned long int tmp = num * mult;
        std::cout << "mult " << mult << "\n num " << num
                << "\n tmp " << tmp << std::endl;

        if (tmp < num)
                std::cout << "overflow" << std::endl;
}

int
main(
        int /* argc */,
        char ** /* argv */)
{
        unsigned long int num = 999999999999999999;
        unsigned long int mult = 1024;

        display(num, mult);
        return 0;
}

Problem:
"overflow" is not displayed as expected.

Analysis:
gcc generates an IMULQ instruction to calculate the value of tmp.
The value of num has bit 63 set.  Since IMULQ sees that argument
as signed, it results in an incorrect number that happens to be
greater than num.

IMULQ will generate the wrong result when the result just fits
into 64 bits too, even though the result would have been correct
(with no overflow) had the proper instruction been used.

Fix:
Whenever the multiplication operands are both unsigned, gcc should
generate an unsigned multiply instruction (MULQ in this case), unless
it can prove that the result would fit into 63 bits.

[Bug rtl-optimization/55393] gcc/g++ multiplies two unsigned integers using the IMULQ instruction

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #1 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-11-19 14:02:38 UTC ---
999999999999999999UL is 0xde0b6b3a763ffffUL, that definitely doesn't have bit
63 set, and that times 1024UL is 0x82dace9d8ffffc00UL which is bigger than
0xde0b6b3a763ffffUL, so can you shed some light why you think it should print
overflow?  I don't see any bug in the generated code, only in your assumptions.

[Bug rtl-optimization/55393] gcc/g++ multiplies two unsigned integers using the IMULQ instruction

[cosmos at claycon dot org]

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

--- Comment #2 from Clay Harris <cosmos at claycon dot org> 2012-11-20 07:46:15 UTC ---
I shouldn't write bug reports when I've been awake for 24 hours.

The bit 63 reference was for one more 9 in num, which got missed
with a cut & paste error.  In any case, the IMUL instruction is doing
what its supposed to for the C code (and executes faster than MUL).
The handling of the sign bit would be wrong, except that we're
throwing away the upper half of the product, where the discrepancy
would occur.

It would be very convenient for overflow testing to have the upper
half (or at least the Carry flag), but alas gcc doesn't seem to have
a way to do that since long long int stopped being 128 bits in 64bit
mode.

Please close this bug as INVALID.

[Bug rtl-optimization/55393] gcc/g++ multiplies two unsigned integers using the IMULQ instruction

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

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

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-11-20 07:56:32 UTC ---
long long never stopped being 128-bit on x86_64 and other 64-bit architectures
GCC supports, it simply always used to be 64-bit.  If you want 128-bit type,
there is unsigned __int128 supported in newer versions of GCC, so you can do
something like:
   if (((unsigned __int128) num * mult) >> 64)
      std::cout << "overflow" << std::endl;