How to prevent common sub-expression elimination (CSE) with GHC

Question

Given the program:

import Debug.Trace
main = print $ trace "hit" 1 + trace "hit" 1

If I compile with ghc -O (7.0.1 or higher) I get the output:

hit
2

i.e. GHC has used common sub-expression elimination (CSE) to rewrite my program as:

main = print $ let x = trace "hit" 1 in x + x

If I compile with -fno-cse then I see hit appearing twice.

Is it possible to avoid CSE by modifying the program? Is there any sub-expression e for which I can guarantee e + e will not be CSE'd? I know about lazy, but can't find anything designed to inhibit CSE.

The background of this question is the cmdargs library, where CSE breaks the library (due to impurity in the library). One solution is to ask users of the library to specify -fno-cse, but I'd prefer to modify the library.

• Peter Wortmann: Hm, long shot, but this reminds me that I wanted to try to make the assert magic user-visible somehow. In case that turned out to be possible, it could also act as a tag preventing GHC from CSE-ing specific function invocations.
• Neil Mitchell: @Peter: I did try the assert stuff, but that then required -fno-ignore-asserts to work.
• Don Stewart: (due to impurity in the library). Obviously, since doing that breaks Haskell's semantics, the compilers will get confused. Is there no way to refactor your code to be referentially transparent in a way the compiler can understand? E.g. ST monad or make it pure?
• augustss: You used unsafePerformIO, you got what you deserved.
• Peter Wortmann: @Don Stewart:This is used to extract annotations like opt "example" from user code (see here). As user code can be just about anything, this has to break referential transparency by design. A pretty cool hack, but very fragile.

Answer 1

How about removing the source of the trouble -- the implicit effect -- by using a sequencing monad that introduces that effect? E.g. the strict identity monad with tracing:

data Eval a = Done a
 | Trace String a
instance Monad Eval where
 return x = Done x
 Done x >>= k = k x
 Trace s a >>= k = trace s (k a)
runEval :: Eval a -> a
runEval (Done x) = x
track = Trace

now we can write stuff with a guaranteed ordering of the trace calls:

main = print $ runEval $ do
 t1 <- track "hit" 1
 t2 <- track "hit" 1
 return (t1 + t2)

while still being pure code, and GHC won't try to get to clever, even with -O2:

 $ ./A
 hit
 hit
 2

So we introduce just the computation effect (tracing) sufficient to teach GHC the semantics we want.

This is extremely robust to compile optimizations. So much so that GHC optimizes the math to 2 at compile time, yet still retains the ordering of the trace statements.

---

As evidence of how robust this approach is, here's the core with -O2 and aggressive inlining:

main2 =
 case Debug.Trace.trace string trace2 of
 Done x -> case x of 
 I# i# -> $wshowSignedInt 0 i# []
 Trace _ _ -> err
trace2 = Debug.Trace.trace string d
d :: Eval Int
d = Done n
n :: Int
n = I# 2
string :: [Char]
string = unpackCString# "hit"

So GHC has done everything it could to optimize the code -- including computing the math statically -- while still retaining the correct tracing.

---

References: the useful Eval monad for sequencing was introduced by Simon Marlow.

• Neil Mitchell: Unsuitable for my particular application, but of course, this is exactly how it should be done in almost all cases. For real code you should probably use putStrLn instead of trace, and have runEval return in the IO monad.
• Don Stewart: I'm not so sure picking up the IO sledgehammer is so obviously the solution in production. We get nice optimization benefits from the not-overly-sequenced tracing monad, and it is pure, so it composes more easily. I suspect it has some uses.
• augustss: Neil's use of unsafePerformIO is actually rather clever and not at all performance critical (command line argument decoding). I don't know of any way to do it quite as conveniently as it is with unsafePerformIO. But I'm willing to pay a price in inconvenience for purity.

Answer 2

Reading the source code to GHC, the only expressions that aren't eligible for CSE are those which fail the exprIsBig test. Currently that means the Expr values Note, Let and Case, and expressions which contain those.

Therefore, an answer to the above question would be:

unit = reverse "" `seq` ()
main = print $ trace "hit" (case unit of () -> 1) +
 trace "hit" (case unit of () -> 1)

Here we create a value unit which resolves to (), but which GHC can't determine the value for (by using a recursive function GHC can't optimise away - reverse is just a simple one to hand). This means GHC can't CSE the trace function and it's 2 arguments, and we get hit printed twice. This works with both GHC 6.12.4 and 7.0.3 at -O2.

• Tener: Answering your own question? Cool!
• Neil Mitchell: @augustss Indeed, I suspect the reverse "" will fall to constructor specialisation before the CSE changes - I am sure eventually I'll be outwitted by the compiler.
• Neil Mitchell: @Tener I didn't have an answer when I posted it - and I hold out the hope that someone may still have a better answer than mine, which is most robust to future GHC improvements.
• augustss: The answer is not to use unsafePerformIO. The way you are using it is wrong, because what you are doing is not implementing an pure function in an impure way. You are actually using the side effects. That's not what Haskell is for.

Answer 3

I think you can specify the -fno-cse option in the source file, i.e. by putting a pragma

{-# OPTIONS_GHC -fno-cse #-}

on top.

Another method to avoid common subexpression elimination or let floating in general is to introduce dummy arguments. For example, you can try

let x () = trace "hi" 1 in x () + x ()

This particular example won't necessarily work; ideally, you should specify a data dependency via dummy arguments. For instance, the following is likely to work:

let
 x dummy = trace "hi" $ dummy `seq` 1
 x1 = x ()
 x2 = x x1 
in x1 + x2

The result of x now "depends" on the argument dummy and there is no longer a common subexpression.

• Neil Mitchell: -fno-cse in my source file won't work - it has to be in the source file of the person using my library, which makes it less desirable. There is no actual data dependency, so I'd have force the end user to add fake data dependencies, making the library API really ugly. These are both useful answers to anyone who isn't writing a library and comes across this problem.

Answer 4

I'm a bit unsure about Don's sequencing monad (posting this as answer because the site doesn't let me add comments). Modifying the example a bit:

main :: IO ()
main = print $ runEval $ do
 t1 <- track "hit 1" (trace "really hit 1" 1)
 t2 <- track "hit 2" 2
 return (t1 + t2)

This gives us the following output:

hit 1
hit 2
really hit 1

That is, the first trace fires when the t1 <- ... statement is executed, not when t1 is actually evaluated in return (t1 + t2). If we define the monadic bind operator as

Done x >>= k = k x
Trace s a >>= k = k (trace s a)

instead, the output will reflect the actual evaluation order:

hit 1
really hit 1
hit 2

That is, the traces will fire when the (t1 + t2) statement is executed, which is (IMO) what we really want. For example, if we change (t1 + t2) to (t2 + t1), this solution produces the following output:

hit 2
really hit 2
hit 1

The output of the original version remains unchanged, and we don't see when our terms are really evaluated:

hit 1
hit 2
really hit 2

Like the original solution, this also works with -O3 (tested on GHC 7.0.3).