optimization - 如何使用 GHC 防止常见子表达式消除 (CSE)

Question

给定程序:

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

如果我用 ghc -O 编译(7.0.1 或更高版本)我得到输出:

hit
2

即 GHC 使用通用子表达式消除 (CSE) 将我的程序重写为:

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

如果我用 -fno-cse 编译然后我看到 hit出现两次。

是否可以通过修改程序来避免 CSE？有没有子表达式 e我可以保证 e + e不会是CSE的吗？我知道 lazy ，但找不到任何旨在抑制 CSE 的东西。

这个问题的背景是 cmdargs库，其中 CSE 破坏了库(由于库中的杂质)。一种解决方案是要求图书馆的用户指定 -fno-cse。 ，但我更愿意修改库。

Answer 1

如何通过使用引入该效果的排序单子(monad)来消除问题的根源——隐含的效果？例如。带追踪的严格身份单子(monad):

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

现在我们可以写出保证 trace 顺序的东西。调用:

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

虽然仍然是纯代码，但 GHC 不会尝试变得聪明，即使使用 -O2 :

    $ ./A
    hit
    hit
    2

所以我们只引入足以教 GHC 我们想要的语义的计算效果(跟踪)。

这对于编译优化非常健壮。以至于 GHC 将数学优化为 2在编译时，仍然保留 trace 的顺序陈述。

作为这种方法有多强大的证据，这里是 -O2 的核心和激进的内联:

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"

因此，GHC 已尽其所能优化代码——包括静态计算数学——同时仍保留正确的跟踪。

引用:有用的 Eval Simon Marlow 引入了用于测序的 monad .