Common subexpression ellimination fails to detect common suexpression
For the following program:
{-# LANGUAGE MagicHash #-}
{-# Language UnboxedTuples #-}
module Magic (sq, sumSq) where
import GHC.Exts
sq :: Int# -> (# Int#, Int# #)
sq x = (# x *# x, x *# x #)
sumSq :: Int# -> Int# -> Int#
sumSq x y =
case sq x of
(# a1, a2 #) ->
case sq y of
(# b1, b2 #) ->
a1 +# a2 +# b1 +# b2
ghc (version 8.8.4, with -O2) produces the following Core for function sumSq
:
sumSq
= \ (x_awb :: Int#) (y_awc :: Int#) ->
+# (+# (*# 2# (*# x_awb x_awb)) (*# y_awc y_awc)) (*# y_awc y_awc)
Here expression (*# y_awc y_awc)
is evaluated twice. Surprisingly ghc is able to share the calculation of (*# x_awb x_awb)
. We can see the issue all the way to assembly language (see below) where there are 3 imul
instead of the optimal 2.
.globl Magic_sumSq_info
.type Magic_sumSq_info, @function
Magic_sumSq_info:
.Lc1fC:
movq %rsi,%rax
imulq %rsi,%rax
movq %rsi,%rbx
imulq %rsi,%rbx
addq %rax,%rbx
movq %rbx,%rax
movq %r14,%rbx
imulq %r14,%rbx
shlq $1,%rbx
addq %rax,%rbx
jmp *(%rbp)