Skip to content

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)
Edited by Neo
To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information