integer-gmp small Integer multiplication does two multiplications on x86

timesInteger begins thusly:

timesInteger :: Integer -> Integer -> Integer
timesInteger (S# i) (S# j)         = if isTrue# (mulIntMayOflo# i j ==# 0#)
                                     then S# (i *# j)
                                     else -- ...

The x86 backend implements mulIntMayOflo# as a (word, word) -> double word multiplication, followed by bit manipulation to test for overflow of the low word. Then, if there was no overflow, on the next line we multiply the operands again.

We should be able to do better here. We need a new primop that combines mulIntMayOflo# with the actual multiplication result, at least in the non-overflow case (though with some more work we might be able to turn the double word result directly into a large Integer), and then we need to update timesInteger to use it.

The LLVM backend probably has the same behavior, though it might be smart enough to notice that the multiplication is repeated; I haven't checked its assembly output.

Trac metadata

Trac field	Value
Version	7.9
Type	FeatureRequest
TypeOfFailure	OtherFailure
Priority	normal
Resolution	Unresolved
Component	Compiler
Test case
Differential revisions
BlockedBy
Related
Blocking
CC	hvr
Operating system
Architecture

changed weight to 5

added Tfeature request Trac import labels

It'd be interesting to know *why* mulIntMayOflo# was introduced instead of a version that'd output the non-overflowing result as well.

Update: mulIntMayOflo# was originally introduced in 7dee9e10

For reference, from libraries/integer-gmp2/src/GHC/Integer/Type.hs:

-- | Multiply two 'Integer's
 timesInteger :: Integer -> Integer -> Integer
 timesInteger _       (S# 0#) = S# 0#
 timesInteger (S# 0#) _       = S# 0#
 timesInteger x       (S# 1#) = x
 timesInteger (S# 1#) y       = y
 timesInteger x      (S# -1#) = negateInteger x
 timesInteger (S# -1#) y      = negateInteger y
 timesInteger (S# x#) (S# y#)
   = case mulIntMayOflo# x# y# of
     0# -> S# (x# *# y#)
     _  -> timesInt2Integer x# y#

Trac metadata

Trac field	Value
TypeOfFailure	OtherFailure → RuntimePerformance
Component	Compiler → Compiler (NCG)

added Pnormal label

We still lack an IntMul2Op primop:

timesInt2# :: Int# -> Int# -> (# Int#, Int#, Int# #)
timesInt2# x y = ... (# highNeeded, high, low #)

highNeeded is a cheap way to check if high is just a sign-extension of low

On x86 (32 or 64), the assembly would be something like:

XOR ecx, ecx  ; rcx <- 0
MOV eax, x
IMUL y        ; rdx:rax <- x*y
SETC cl       ; cl <- CF
return (# rcx, rdx, rax #) ; (# ecx, edx, eax #) for 32-bit width

If we ever implement this for Int8#:

XOR eax,eax
XOR ecx, ecx
MOV al, x
IMUL y        ; ax <- x*y
SETC cl       ; cl <- CF
return (# cl, ah, al #)

The generic version can be implemented by computing with half-width values.

assigned to @hsyl20

mentioned in merge request !1872 (closed)

mentioned in commit 98851ae8

mentioned in commit fbbe18a2

Fixed by fbbe18a2

closed